1 /** 2 * dir.c 3 * 4 * Many parts of codes are copied from Linux kernel/fs/f2fs. 5 * 6 * Copyright (C) 2015 Huawei Ltd. 7 * Witten by: 8 * Hou Pengyang <houpengyang (at) huawei.com> 9 * Liu Shuoran <liushuoran (at) huawei.com> 10 * Jaegeuk Kim <jaegeuk (at) kernel.org> 11 * 12 * This program is free software; you can redistribute it and/or modify 13 * it under the terms of the GNU General Public License version 2 as 14 * published by the Free Software Foundation. 15 */ 16 #include "fsck.h" 17 #include "node.h" 18 19 static int room_for_filename(const u8 *bitmap, int slots, int max_slots) 20 { 21 int bit_start = 0; 22 int zero_start, zero_end; 23 next: 24 zero_start = find_next_zero_bit_le(bitmap, max_slots, bit_start); 25 if (zero_start >= max_slots) 26 return max_slots; 27 28 zero_end = find_next_bit_le(bitmap, max_slots, zero_start + 1); 29 30 if (zero_end - zero_start >= slots) 31 return zero_start; 32 bit_start = zero_end; 33 goto next; 34 35 } 36 37 static void make_dentry_ptr(struct f2fs_dentry_ptr *d, void *src, int type) 38 { 39 if (type == 1) { 40 struct f2fs_dentry_block *t = (struct f2fs_dentry_block *)src; 41 d->max = NR_DENTRY_IN_BLOCK; 42 d->bitmap = t->dentry_bitmap; 43 d->dentry = t->dentry; 44 d->filename = t->filename; 45 } else { 46 struct f2fs_inline_dentry *t = (struct f2fs_inline_dentry *)src; 47 d->max = NR_INLINE_DENTRY; 48 d->bitmap = t->dentry_bitmap; 49 d->dentry = t->dentry; 50 d->filename = t->filename; 51 } 52 } 53 54 static struct f2fs_dir_entry *find_target_dentry(const u8 *name, 55 unsigned int len, f2fs_hash_t namehash, int *max_slots, 56 struct f2fs_dentry_ptr *d) 57 { 58 struct f2fs_dir_entry *de; 59 unsigned long bit_pos = 0; 60 int max_len = 0; 61 62 if (max_slots) 63 *max_slots = 0; 64 while (bit_pos < d->max) { 65 if (!test_bit_le(bit_pos, d->bitmap)) { 66 bit_pos++; 67 max_len++; 68 continue; 69 } 70 71 de = &d->dentry[bit_pos]; 72 if (le16_to_cpu(de->name_len) == len && 73 de->hash_code == namehash && 74 !memcmp(d->filename[bit_pos], name, len)) { 75 goto found; 76 } 77 78 if (max_slots && max_len > *max_slots) 79 *max_slots = max_len; 80 max_len = 0; 81 bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len)); 82 } 83 de = NULL; 84 found: 85 if (max_slots && max_len > *max_slots) 86 *max_slots = max_len; 87 return de; 88 } 89 90 static struct f2fs_dir_entry *find_in_block(void *block, 91 const u8 *name, int len, f2fs_hash_t namehash, 92 int *max_slots) 93 { 94 struct f2fs_dentry_ptr d; 95 96 make_dentry_ptr(&d, block, 1); 97 return find_target_dentry(name, len, namehash, max_slots, &d); 98 } 99 100 static int find_in_level(struct f2fs_sb_info *sbi,struct f2fs_node *dir, 101 unsigned int level, struct dentry *de) 102 { 103 unsigned int nbucket, nblock; 104 unsigned int bidx, end_block; 105 struct f2fs_dir_entry *dentry = NULL; 106 struct dnode_of_data dn = {0}; 107 void *dentry_blk; 108 int max_slots = 214; 109 nid_t ino = le32_to_cpu(dir->footer.ino); 110 f2fs_hash_t namehash; 111 unsigned int dir_level = dir->i.i_dir_level; 112 int ret = 0; 113 114 namehash = f2fs_dentry_hash(de->name, de->len); 115 116 nbucket = dir_buckets(level, dir_level); 117 nblock = bucket_blocks(level); 118 119 bidx = dir_block_index(level, dir_level, le32_to_cpu(namehash) % nbucket); 120 end_block = bidx + nblock; 121 122 dentry_blk = calloc(BLOCK_SZ, 1); 123 ASSERT(dentry_blk); 124 125 for (; bidx < end_block; bidx++) { 126 127 /* Firstly, we should know direct node of target data blk */ 128 if (dn.node_blk && dn.node_blk != dn.inode_blk) 129 free(dn.node_blk); 130 131 set_new_dnode(&dn, dir, NULL, ino); 132 get_dnode_of_data(sbi, &dn, bidx, LOOKUP_NODE); 133 if (dn.data_blkaddr == NULL_ADDR) 134 continue; 135 136 ret = dev_read_block(dentry_blk, dn.data_blkaddr); 137 ASSERT(ret >= 0); 138 139 dentry = find_in_block(dentry_blk, de->name, de->len, 140 namehash, &max_slots); 141 if (dentry) { 142 ret = 1; 143 de->ino = le32_to_cpu(dentry->ino); 144 break; 145 } 146 } 147 148 if (dn.node_blk && dn.node_blk != dn.inode_blk) 149 free(dn.node_blk); 150 free(dentry_blk); 151 152 return ret; 153 } 154 155 static int f2fs_find_entry(struct f2fs_sb_info *sbi, 156 struct f2fs_node *dir, struct dentry *de) 157 { 158 unsigned int max_depth; 159 unsigned int level; 160 161 max_depth = le32_to_cpu(dir->i.i_current_depth); 162 for (level = 0; level < max_depth; level ++) { 163 if (find_in_level(sbi, dir, level, de)) 164 return 1; 165 } 166 return 0; 167 } 168 169 static void f2fs_update_dentry(nid_t ino, int file_type, 170 struct f2fs_dentry_ptr *d, 171 const unsigned char *name, int len, f2fs_hash_t name_hash, 172 unsigned int bit_pos) 173 { 174 struct f2fs_dir_entry *de; 175 int slots = GET_DENTRY_SLOTS(len); 176 int i; 177 178 de = &d->dentry[bit_pos]; 179 de->name_len = cpu_to_le16(len); 180 de->hash_code = name_hash; 181 memcpy(d->filename[bit_pos], name, len); 182 d->filename[bit_pos][len] = 0; 183 de->ino = cpu_to_le32(ino); 184 de->file_type = file_type; 185 for (i = 0; i < slots; i++) 186 test_and_set_bit_le(bit_pos + i, d->bitmap); 187 } 188 189 /* 190 * f2fs_add_link - Add a new file(dir) to parent dir. 191 */ 192 static int f2fs_add_link(struct f2fs_sb_info *sbi, struct f2fs_node *parent, 193 const unsigned char *name, int name_len, nid_t ino, 194 int file_type, block_t p_blkaddr, int inc_link) 195 { 196 int level = 0, current_depth, bit_pos; 197 int nbucket, nblock, bidx, block; 198 int slots = GET_DENTRY_SLOTS(name_len); 199 f2fs_hash_t dentry_hash = f2fs_dentry_hash(name, name_len); 200 struct f2fs_dentry_block *dentry_blk; 201 struct f2fs_dentry_ptr d; 202 struct dnode_of_data dn = {0}; 203 nid_t pino = le32_to_cpu(parent->footer.ino); 204 unsigned int dir_level = parent->i.i_dir_level; 205 int ret; 206 207 if (parent == NULL) 208 return -EINVAL; 209 210 if (!pino) { 211 ERR_MSG("Wrong parent ino:%d \n", pino); 212 return -EINVAL; 213 } 214 215 dentry_blk = calloc(BLOCK_SZ, 1); 216 ASSERT(dentry_blk); 217 218 current_depth = le32_to_cpu(parent->i.i_current_depth); 219 start: 220 if (current_depth == MAX_DIR_HASH_DEPTH) { 221 free(dentry_blk); 222 ERR_MSG("\tError: MAX_DIR_HASH\n"); 223 return -ENOSPC; 224 } 225 226 /* Need a new dentry block */ 227 if (level == current_depth) 228 ++current_depth; 229 230 nbucket = dir_buckets(level, dir_level); 231 nblock = bucket_blocks(level); 232 bidx = dir_block_index(level, dir_level, le32_to_cpu(dentry_hash) % nbucket); 233 234 for (block = bidx; block <= (bidx + nblock - 1); block++) { 235 236 /* Firstly, we should know the direct node of target data blk */ 237 if (dn.node_blk && dn.node_blk != dn.inode_blk) 238 free(dn.node_blk); 239 240 set_new_dnode(&dn, parent, NULL, pino); 241 get_dnode_of_data(sbi, &dn, block, ALLOC_NODE); 242 243 if (dn.data_blkaddr == NULL_ADDR) { 244 new_data_block(sbi, dentry_blk, &dn, CURSEG_HOT_DATA); 245 } else { 246 ret = dev_read_block(dentry_blk, dn.data_blkaddr); 247 ASSERT(ret >= 0); 248 } 249 bit_pos = room_for_filename(dentry_blk->dentry_bitmap, 250 slots, NR_DENTRY_IN_BLOCK); 251 252 if (bit_pos < NR_DENTRY_IN_BLOCK) 253 goto add_dentry; 254 } 255 level ++; 256 goto start; 257 258 add_dentry: 259 make_dentry_ptr(&d, (void *)dentry_blk, 1); 260 f2fs_update_dentry(ino, file_type, &d, name, name_len, dentry_hash, bit_pos); 261 262 ret = dev_write_block(dentry_blk, dn.data_blkaddr); 263 ASSERT(ret >= 0); 264 265 /* 266 * Parent inode needs updating, because its inode info may be changed. 267 * such as i_current_depth and i_blocks. 268 */ 269 if (parent->i.i_current_depth != cpu_to_le32(current_depth)) { 270 parent->i.i_current_depth = cpu_to_le32(current_depth); 271 dn.idirty = 1; 272 } 273 274 /* Update parent's i_links info*/ 275 if (inc_link && (file_type == F2FS_FT_DIR)){ 276 u32 links = le32_to_cpu(parent->i.i_links); 277 parent->i.i_links = cpu_to_le32(links + 1); 278 dn.idirty = 1; 279 } 280 281 if ((block + 1) * F2FS_BLKSIZE > le64_to_cpu(parent->i.i_size)) { 282 parent->i.i_size = cpu_to_le64((block + 1) * F2FS_BLKSIZE); 283 dn.idirty = 1; 284 } 285 286 if (dn.ndirty) { 287 ret = dev_write_block(dn.node_blk, dn.node_blkaddr); 288 ASSERT(ret >= 0); 289 } 290 291 if (dn.idirty) { 292 ASSERT(parent == dn.inode_blk); 293 ret = dev_write_block(dn.inode_blk, p_blkaddr); 294 ASSERT(ret >= 0); 295 } 296 297 if (dn.node_blk != dn.inode_blk) 298 free(dn.node_blk); 299 free(dentry_blk); 300 return 0; 301 } 302 303 static void make_empty_dir(struct f2fs_sb_info *sbi, struct f2fs_node *inode) 304 { 305 struct f2fs_dentry_block *dent_blk; 306 nid_t ino = le32_to_cpu(inode->footer.ino); 307 nid_t pino = le32_to_cpu(inode->i.i_pino); 308 struct f2fs_summary sum; 309 struct node_info ni; 310 block_t blkaddr; 311 int ret; 312 313 get_node_info(sbi, ino, &ni); 314 315 dent_blk = calloc(BLOCK_SZ, 1); 316 ASSERT(dent_blk); 317 318 dent_blk->dentry[0].hash_code = 0; 319 dent_blk->dentry[0].ino = cpu_to_le32(ino); 320 dent_blk->dentry[0].name_len = cpu_to_le16(1); 321 dent_blk->dentry[0].file_type = F2FS_FT_DIR; 322 memcpy(dent_blk->filename[0], ".", 1); 323 324 dent_blk->dentry[1].hash_code = 0; 325 dent_blk->dentry[1].ino = cpu_to_le32(pino); 326 dent_blk->dentry[1].name_len = cpu_to_le16(2); 327 dent_blk->dentry[1].file_type = F2FS_FT_DIR; 328 memcpy(dent_blk->filename[1], "..", 2); 329 330 test_and_set_bit_le(0, dent_blk->dentry_bitmap); 331 test_and_set_bit_le(1, dent_blk->dentry_bitmap); 332 333 set_summary(&sum, ino, 0, ni.version); 334 reserve_new_block(sbi, &blkaddr, &sum, CURSEG_HOT_DATA); 335 336 ret = dev_write_block(dent_blk, blkaddr); 337 ASSERT(ret >= 0); 338 339 inode->i.i_addr[0] = cpu_to_le32(blkaddr); 340 free(dent_blk); 341 } 342 343 static void page_symlink(struct f2fs_sb_info *sbi, struct f2fs_node *inode, 344 const char *symname, int symlen) 345 { 346 nid_t ino = le32_to_cpu(inode->footer.ino); 347 struct f2fs_summary sum; 348 struct node_info ni; 349 char *data_blk; 350 block_t blkaddr; 351 int ret; 352 353 get_node_info(sbi, ino, &ni); 354 355 /* store into inline_data */ 356 if (symlen + 1 <= MAX_INLINE_DATA) { 357 inode->i.i_inline |= F2FS_INLINE_DATA; 358 inode->i.i_inline |= F2FS_DATA_EXIST; 359 memcpy(&inode->i.i_addr[1], symname, symlen); 360 return; 361 } 362 363 data_blk = calloc(BLOCK_SZ, 1); 364 ASSERT(data_blk); 365 366 memcpy(data_blk, symname, symlen); 367 368 set_summary(&sum, ino, 0, ni.version); 369 reserve_new_block(sbi, &blkaddr, &sum, CURSEG_WARM_DATA); 370 371 ret = dev_write_block(data_blk, blkaddr); 372 ASSERT(ret >= 0); 373 374 inode->i.i_addr[0] = cpu_to_le32(blkaddr); 375 free(data_blk); 376 } 377 378 static void init_inode_block(struct f2fs_sb_info *sbi, 379 struct f2fs_node *node_blk, struct dentry *de) 380 { 381 struct f2fs_checkpoint *ckpt = F2FS_CKPT(sbi); 382 mode_t mode = de->mode; 383 int links = 1; 384 unsigned int size; 385 int blocks = 1; 386 387 if (de->file_type == F2FS_FT_DIR) { 388 mode |= S_IFDIR; 389 size = 4096; 390 links++; 391 blocks++; 392 } else if (de->file_type == F2FS_FT_REG_FILE) { 393 mode |= S_IFREG; 394 size = 0; 395 } else if (de->file_type == F2FS_FT_SYMLINK) { 396 ASSERT(de->link); 397 mode |= S_IFLNK; 398 size = strlen(de->link); 399 if (size + 1 > MAX_INLINE_DATA) 400 blocks++; 401 } else { 402 ASSERT(0); 403 } 404 405 node_blk->i.i_mode = cpu_to_le16(mode); 406 node_blk->i.i_advise = 0; 407 node_blk->i.i_uid = cpu_to_le32(de->uid); 408 node_blk->i.i_gid = cpu_to_le32(de->gid); 409 node_blk->i.i_links = cpu_to_le32(links); 410 node_blk->i.i_size = cpu_to_le32(size); 411 node_blk->i.i_blocks = cpu_to_le32(blocks); 412 node_blk->i.i_atime = cpu_to_le64(de->mtime); 413 node_blk->i.i_ctime = cpu_to_le64(de->mtime); 414 node_blk->i.i_mtime = cpu_to_le64(de->mtime); 415 node_blk->i.i_atime_nsec = 0; 416 node_blk->i.i_ctime_nsec = 0; 417 node_blk->i.i_mtime_nsec = 0; 418 node_blk->i.i_generation = 0; 419 node_blk->i.i_current_depth = cpu_to_le32(1); 420 node_blk->i.i_xattr_nid = 0; 421 node_blk->i.i_flags = 0; 422 node_blk->i.i_inline = F2FS_INLINE_XATTR; 423 node_blk->i.i_pino = cpu_to_le32(de->pino); 424 node_blk->i.i_namelen = cpu_to_le32(de->len); 425 memcpy(node_blk->i.i_name, de->name, de->len); 426 node_blk->i.i_name[de->len] = 0; 427 428 node_blk->footer.ino = cpu_to_le32(de->ino); 429 node_blk->footer.nid = cpu_to_le32(de->ino); 430 node_blk->footer.flag = 0; 431 node_blk->footer.cp_ver = ckpt->checkpoint_ver; 432 433 if (S_ISDIR(mode)) 434 make_empty_dir(sbi, node_blk); 435 else if (S_ISLNK(mode)) 436 page_symlink(sbi, node_blk, de->link, size); 437 } 438 439 int convert_inline_dentry(struct f2fs_sb_info *sbi, struct f2fs_node *node, 440 block_t p_blkaddr) 441 { 442 struct f2fs_inode *inode = &(node->i); 443 unsigned int dir_level = node->i.i_dir_level; 444 nid_t ino = le32_to_cpu(node->footer.ino); 445 char inline_data[MAX_INLINE_DATA]; 446 struct dnode_of_data dn = {0}; 447 struct f2fs_dentry_ptr d; 448 unsigned long bit_pos = 0; 449 int ret = 0; 450 451 if (!(inode->i_inline & F2FS_INLINE_DENTRY)) 452 return 0; 453 454 memcpy(inline_data, inline_data_addr(node), MAX_INLINE_DATA); 455 memset(inline_data_addr(node), 0, MAX_INLINE_DATA); 456 inode->i_inline &= ~F2FS_INLINE_DENTRY; 457 458 ret = dev_write_block(node, p_blkaddr); 459 ASSERT(ret >= 0); 460 461 if (!dir_level) { 462 struct f2fs_inline_dentry *inline_dentry; 463 struct f2fs_dentry_block *dentry_blk; 464 465 dentry_blk = calloc(BLOCK_SZ, 1); 466 ASSERT(dentry_blk); 467 468 set_new_dnode(&dn, node, NULL, ino); 469 get_dnode_of_data(sbi, &dn, 0, ALLOC_NODE); 470 if (dn.data_blkaddr == NULL_ADDR) 471 new_data_block(sbi, dentry_blk, &dn, CURSEG_HOT_DATA); 472 473 inline_dentry = (struct f2fs_inline_dentry *)inline_data; 474 /* copy data from inline dentry block to new dentry block */ 475 memcpy(dentry_blk->dentry_bitmap, inline_dentry->dentry_bitmap, 476 INLINE_DENTRY_BITMAP_SIZE); 477 memset(dentry_blk->dentry_bitmap + INLINE_DENTRY_BITMAP_SIZE, 0, 478 SIZE_OF_DENTRY_BITMAP - INLINE_DENTRY_BITMAP_SIZE); 479 480 memcpy(dentry_blk->dentry, inline_dentry->dentry, 481 sizeof(struct f2fs_dir_entry) * NR_INLINE_DENTRY); 482 memcpy(dentry_blk->filename, inline_dentry->filename, 483 NR_INLINE_DENTRY * F2FS_SLOT_LEN); 484 485 ret = dev_write_block(dentry_blk, dn.data_blkaddr); 486 ASSERT(ret >= 0); 487 488 MSG(1, "%s: copy inline entry to block\n", __func__); 489 490 free(dentry_blk); 491 return ret; 492 } 493 494 make_empty_dir(sbi, node); 495 make_dentry_ptr(&d, (void *)inline_data, 2); 496 497 while (bit_pos < d.max) { 498 struct f2fs_dir_entry *de; 499 const unsigned char *filename; 500 int namelen; 501 502 if (!test_bit_le(bit_pos, d.bitmap)) { 503 bit_pos++; 504 continue; 505 } 506 507 de = &d.dentry[bit_pos]; 508 if (!de->name_len) { 509 bit_pos++; 510 continue; 511 } 512 513 filename = d.filename[bit_pos]; 514 namelen = le32_to_cpu(de->name_len); 515 516 if (is_dot_dotdot(filename, namelen)) { 517 bit_pos += GET_DENTRY_SLOTS(namelen); 518 continue; 519 } 520 521 ret = f2fs_add_link(sbi, node, filename, namelen, 522 le32_to_cpu(de->ino), 523 de->file_type, p_blkaddr, 0); 524 if (ret) 525 MSG(0, "Convert file \"%s\" ERR=%d\n", filename, ret); 526 else 527 MSG(1, "%s: add inline entry to block\n", __func__); 528 529 bit_pos += GET_DENTRY_SLOTS(namelen); 530 } 531 532 return 0; 533 } 534 535 int f2fs_create(struct f2fs_sb_info *sbi, struct dentry *de) 536 { 537 struct f2fs_node *parent, *child; 538 struct node_info ni; 539 struct f2fs_summary sum; 540 block_t blkaddr; 541 int ret; 542 543 /* Find if there is a */ 544 get_node_info(sbi, de->pino, &ni); 545 if (ni.blk_addr == NULL_ADDR) { 546 MSG(0, "No parent directory pino=%x\n", de->pino); 547 return -1; 548 } 549 550 parent = calloc(BLOCK_SZ, 1); 551 ASSERT(parent); 552 553 ret = dev_read_block(parent, ni.blk_addr); 554 ASSERT(ret >= 0); 555 556 /* Must convert inline dentry before the following opertions */ 557 ret = convert_inline_dentry(sbi, parent, ni.blk_addr); 558 if (ret) { 559 MSG(0, "Convert inline dentry for pino=%x failed.\n", de->pino); 560 return -1; 561 } 562 563 ret = f2fs_find_entry(sbi, parent, de); 564 if (ret) { 565 MSG(0, "Skip the existing \"%s\" pino=%x ERR=%d\n", 566 de->name, de->pino, ret); 567 if (de->file_type == F2FS_FT_REG_FILE) 568 de->ino = 0; 569 goto free_parent_dir; 570 } 571 572 child = calloc(BLOCK_SZ, 1); 573 ASSERT(child); 574 575 f2fs_alloc_nid(sbi, &de->ino, 1); 576 577 init_inode_block(sbi, child, de); 578 579 ret = f2fs_add_link(sbi, parent, child->i.i_name, 580 le32_to_cpu(child->i.i_namelen), 581 le32_to_cpu(child->footer.ino), 582 map_de_type(le16_to_cpu(child->i.i_mode)), 583 ni.blk_addr, 1); 584 if (ret) { 585 MSG(0, "Skip the existing \"%s\" pino=%x ERR=%d\n", 586 de->name, de->pino, ret); 587 goto free_child_dir; 588 } 589 590 /* write child */ 591 set_summary(&sum, de->ino, 0, ni.version); 592 reserve_new_block(sbi, &blkaddr, &sum, CURSEG_HOT_NODE); 593 594 /* update nat info */ 595 update_nat_blkaddr(sbi, de->ino, de->ino, blkaddr); 596 597 ret = dev_write_block(child, blkaddr); 598 ASSERT(ret >= 0); 599 600 update_free_segments(sbi); 601 MSG(1, "Info: Create \"%s\" type=%x, ino=%x / %x into \"%s\"\n", 602 de->full_path, de->file_type, 603 de->ino, de->pino, de->path); 604 free_child_dir: 605 free(child); 606 free_parent_dir: 607 free(parent); 608 return 0; 609 } 610 611 int f2fs_mkdir(struct f2fs_sb_info *sbi, struct dentry *de) 612 { 613 return f2fs_create(sbi, de); 614 } 615 616 int f2fs_symlink(struct f2fs_sb_info *sbi, struct dentry *de) 617 { 618 return f2fs_create(sbi, de); 619 } 620 621 int f2fs_find_path(struct f2fs_sb_info *sbi, char *path, nid_t *ino) 622 { 623 struct f2fs_node *parent; 624 struct node_info ni; 625 struct dentry de; 626 int err = 0; 627 int ret; 628 char *p; 629 630 if (path[0] != '/') 631 return -ENOENT; 632 633 *ino = F2FS_ROOT_INO(sbi); 634 parent = calloc(BLOCK_SZ, 1); 635 ASSERT(parent); 636 637 p = strtok(path, "/"); 638 while (p) { 639 de.name = (const u8 *)p; 640 de.len = strlen(p); 641 642 get_node_info(sbi, *ino, &ni); 643 if (ni.blk_addr == NULL_ADDR) { 644 err = -ENOENT; 645 goto err; 646 } 647 ret = dev_read_block(parent, ni.blk_addr); 648 ASSERT(ret >= 0); 649 650 ret = f2fs_find_entry(sbi, parent, &de); 651 if (!ret) { 652 err = -ENOENT; 653 goto err; 654 } 655 656 *ino = de.ino; 657 p = strtok(NULL, "/"); 658 } 659 err: 660 free(parent); 661 return err; 662 } 663
