1 /* 2 * fs/f2fs/dir.c 3 * 4 * Copyright (c) 2012 Samsung Electronics Co., Ltd. 5 * http://www.samsung.com/ 6 * 7 * This program is free software; you can redistribute it and/or modify 8 * it under the terms of the GNU General Public License version 2 as 9 * published by the Free Software Foundation. 10 */ 11 #include <linux/fs.h> 12 #include <linux/f2fs_fs.h> 13 #include "f2fs.h" 14 #include "node.h" 15 #include "acl.h" 16 #include "xattr.h" 17 18 static unsigned long dir_blocks(struct inode *inode) 19 { 20 return ((unsigned long long) (i_size_read(inode) + PAGE_CACHE_SIZE - 1)) 21 >> PAGE_CACHE_SHIFT; 22 } 23 24 static unsigned int dir_buckets(unsigned int level) 25 { 26 if (level < MAX_DIR_HASH_DEPTH / 2) 27 return 1 << level; 28 else 29 return 1 << ((MAX_DIR_HASH_DEPTH / 2) - 1); 30 } 31 32 static unsigned int bucket_blocks(unsigned int level) 33 { 34 if (level < MAX_DIR_HASH_DEPTH / 2) 35 return 2; 36 else 37 return 4; 38 } 39 40 static unsigned char f2fs_filetype_table[F2FS_FT_MAX] = { 41 [F2FS_FT_UNKNOWN] = DT_UNKNOWN, 42 [F2FS_FT_REG_FILE] = DT_REG, 43 [F2FS_FT_DIR] = DT_DIR, 44 [F2FS_FT_CHRDEV] = DT_CHR, 45 [F2FS_FT_BLKDEV] = DT_BLK, 46 [F2FS_FT_FIFO] = DT_FIFO, 47 [F2FS_FT_SOCK] = DT_SOCK, 48 [F2FS_FT_SYMLINK] = DT_LNK, 49 }; 50 51 #define S_SHIFT 12 52 static unsigned char f2fs_type_by_mode[S_IFMT >> S_SHIFT] = { 53 [S_IFREG >> S_SHIFT] = F2FS_FT_REG_FILE, 54 [S_IFDIR >> S_SHIFT] = F2FS_FT_DIR, 55 [S_IFCHR >> S_SHIFT] = F2FS_FT_CHRDEV, 56 [S_IFBLK >> S_SHIFT] = F2FS_FT_BLKDEV, 57 [S_IFIFO >> S_SHIFT] = F2FS_FT_FIFO, 58 [S_IFSOCK >> S_SHIFT] = F2FS_FT_SOCK, 59 [S_IFLNK >> S_SHIFT] = F2FS_FT_SYMLINK, 60 }; 61 62 static void set_de_type(struct f2fs_dir_entry *de, struct inode *inode) 63 { 64 umode_t mode = inode->i_mode; 65 de->file_type = f2fs_type_by_mode[(mode & S_IFMT) >> S_SHIFT]; 66 } 67 68 static unsigned long dir_block_index(unsigned int level, unsigned int idx) 69 { 70 unsigned long i; 71 unsigned long bidx = 0; 72 73 for (i = 0; i < level; i++) 74 bidx += dir_buckets(i) * bucket_blocks(i); 75 bidx += idx * bucket_blocks(level); 76 return bidx; 77 } 78 79 static bool early_match_name(const char *name, size_t namelen, 80 f2fs_hash_t namehash, struct f2fs_dir_entry *de) 81 { 82 if (le16_to_cpu(de->name_len) != namelen) 83 return false; 84 85 if (de->hash_code != namehash) 86 return false; 87 88 return true; 89 } 90 91 static struct f2fs_dir_entry *find_in_block(struct page *dentry_page, 92 const char *name, size_t namelen, int *max_slots, 93 f2fs_hash_t namehash, struct page **res_page) 94 { 95 struct f2fs_dir_entry *de; 96 unsigned long bit_pos, end_pos, next_pos; 97 struct f2fs_dentry_block *dentry_blk = kmap(dentry_page); 98 int slots; 99 100 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 101 NR_DENTRY_IN_BLOCK, 0); 102 while (bit_pos < NR_DENTRY_IN_BLOCK) { 103 de = &dentry_blk->dentry[bit_pos]; 104 slots = GET_DENTRY_SLOTS(le16_to_cpu(de->name_len)); 105 106 if (early_match_name(name, namelen, namehash, de)) { 107 if (!memcmp(dentry_blk->filename[bit_pos], 108 name, namelen)) { 109 *res_page = dentry_page; 110 goto found; 111 } 112 } 113 next_pos = bit_pos + slots; 114 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 115 NR_DENTRY_IN_BLOCK, next_pos); 116 if (bit_pos >= NR_DENTRY_IN_BLOCK) 117 end_pos = NR_DENTRY_IN_BLOCK; 118 else 119 end_pos = bit_pos; 120 if (*max_slots < end_pos - next_pos) 121 *max_slots = end_pos - next_pos; 122 } 123 124 de = NULL; 125 kunmap(dentry_page); 126 found: 127 return de; 128 } 129 130 static struct f2fs_dir_entry *find_in_level(struct inode *dir, 131 unsigned int level, const char *name, size_t namelen, 132 f2fs_hash_t namehash, struct page **res_page) 133 { 134 int s = GET_DENTRY_SLOTS(namelen); 135 unsigned int nbucket, nblock; 136 unsigned int bidx, end_block; 137 struct page *dentry_page; 138 struct f2fs_dir_entry *de = NULL; 139 bool room = false; 140 int max_slots = 0; 141 142 BUG_ON(level > MAX_DIR_HASH_DEPTH); 143 144 nbucket = dir_buckets(level); 145 nblock = bucket_blocks(level); 146 147 bidx = dir_block_index(level, le32_to_cpu(namehash) % nbucket); 148 end_block = bidx + nblock; 149 150 for (; bidx < end_block; bidx++) { 151 /* no need to allocate new dentry pages to all the indices */ 152 dentry_page = find_data_page(dir, bidx, true); 153 if (IS_ERR(dentry_page)) { 154 room = true; 155 continue; 156 } 157 158 de = find_in_block(dentry_page, name, namelen, 159 &max_slots, namehash, res_page); 160 if (de) 161 break; 162 163 if (max_slots >= s) 164 room = true; 165 f2fs_put_page(dentry_page, 0); 166 } 167 168 if (!de && room && F2FS_I(dir)->chash != namehash) { 169 F2FS_I(dir)->chash = namehash; 170 F2FS_I(dir)->clevel = level; 171 } 172 173 return de; 174 } 175 176 /* 177 * Find an entry in the specified directory with the wanted name. 178 * It returns the page where the entry was found (as a parameter - res_page), 179 * and the entry itself. Page is returned mapped and unlocked. 180 * Entry is guaranteed to be valid. 181 */ 182 struct f2fs_dir_entry *f2fs_find_entry(struct inode *dir, 183 struct qstr *child, struct page **res_page) 184 { 185 const char *name = child->name; 186 size_t namelen = child->len; 187 unsigned long npages = dir_blocks(dir); 188 struct f2fs_dir_entry *de = NULL; 189 f2fs_hash_t name_hash; 190 unsigned int max_depth; 191 unsigned int level; 192 193 if (namelen > F2FS_NAME_LEN) 194 return NULL; 195 196 if (npages == 0) 197 return NULL; 198 199 *res_page = NULL; 200 201 name_hash = f2fs_dentry_hash(name, namelen); 202 max_depth = F2FS_I(dir)->i_current_depth; 203 204 for (level = 0; level < max_depth; level++) { 205 de = find_in_level(dir, level, name, 206 namelen, name_hash, res_page); 207 if (de) 208 break; 209 } 210 if (!de && F2FS_I(dir)->chash != name_hash) { 211 F2FS_I(dir)->chash = name_hash; 212 F2FS_I(dir)->clevel = level - 1; 213 } 214 return de; 215 } 216 217 struct f2fs_dir_entry *f2fs_parent_dir(struct inode *dir, struct page **p) 218 { 219 struct page *page; 220 struct f2fs_dir_entry *de; 221 struct f2fs_dentry_block *dentry_blk; 222 223 page = get_lock_data_page(dir, 0); 224 if (IS_ERR(page)) 225 return NULL; 226 227 dentry_blk = kmap(page); 228 de = &dentry_blk->dentry[1]; 229 *p = page; 230 unlock_page(page); 231 return de; 232 } 233 234 ino_t f2fs_inode_by_name(struct inode *dir, struct qstr *qstr) 235 { 236 ino_t res = 0; 237 struct f2fs_dir_entry *de; 238 struct page *page; 239 240 de = f2fs_find_entry(dir, qstr, &page); 241 if (de) { 242 res = le32_to_cpu(de->ino); 243 kunmap(page); 244 f2fs_put_page(page, 0); 245 } 246 247 return res; 248 } 249 250 void f2fs_set_link(struct inode *dir, struct f2fs_dir_entry *de, 251 struct page *page, struct inode *inode) 252 { 253 lock_page(page); 254 wait_on_page_writeback(page); 255 de->ino = cpu_to_le32(inode->i_ino); 256 set_de_type(de, inode); 257 kunmap(page); 258 set_page_dirty(page); 259 dir->i_mtime = dir->i_ctime = CURRENT_TIME; 260 mark_inode_dirty(dir); 261 262 /* update parent inode number before releasing dentry page */ 263 F2FS_I(inode)->i_pino = dir->i_ino; 264 265 f2fs_put_page(page, 1); 266 } 267 268 static void init_dent_inode(const struct qstr *name, struct page *ipage) 269 { 270 struct f2fs_node *rn; 271 272 /* copy name info. to this inode page */ 273 rn = F2FS_NODE(ipage); 274 rn->i.i_namelen = cpu_to_le32(name->len); 275 memcpy(rn->i.i_name, name->name, name->len); 276 set_page_dirty(ipage); 277 } 278 279 int update_dent_inode(struct inode *inode, const struct qstr *name) 280 { 281 struct f2fs_sb_info *sbi = F2FS_SB(inode->i_sb); 282 struct page *page; 283 284 page = get_node_page(sbi, inode->i_ino); 285 if (IS_ERR(page)) 286 return PTR_ERR(page); 287 288 init_dent_inode(name, page); 289 f2fs_put_page(page, 1); 290 291 return 0; 292 } 293 294 static int make_empty_dir(struct inode *inode, 295 struct inode *parent, struct page *page) 296 { 297 struct page *dentry_page; 298 struct f2fs_dentry_block *dentry_blk; 299 struct f2fs_dir_entry *de; 300 void *kaddr; 301 302 dentry_page = get_new_data_page(inode, page, 0, true); 303 if (IS_ERR(dentry_page)) 304 return PTR_ERR(dentry_page); 305 306 kaddr = kmap_atomic(dentry_page); 307 dentry_blk = (struct f2fs_dentry_block *)kaddr; 308 309 de = &dentry_blk->dentry[0]; 310 de->name_len = cpu_to_le16(1); 311 de->hash_code = 0; 312 de->ino = cpu_to_le32(inode->i_ino); 313 memcpy(dentry_blk->filename[0], ".", 1); 314 set_de_type(de, inode); 315 316 de = &dentry_blk->dentry[1]; 317 de->hash_code = 0; 318 de->name_len = cpu_to_le16(2); 319 de->ino = cpu_to_le32(parent->i_ino); 320 memcpy(dentry_blk->filename[1], "..", 2); 321 set_de_type(de, inode); 322 323 test_and_set_bit_le(0, &dentry_blk->dentry_bitmap); 324 test_and_set_bit_le(1, &dentry_blk->dentry_bitmap); 325 kunmap_atomic(kaddr); 326 327 set_page_dirty(dentry_page); 328 f2fs_put_page(dentry_page, 1); 329 return 0; 330 } 331 332 static struct page *init_inode_metadata(struct inode *inode, 333 struct inode *dir, const struct qstr *name) 334 { 335 struct page *page; 336 int err; 337 338 if (is_inode_flag_set(F2FS_I(inode), FI_NEW_INODE)) { 339 page = new_inode_page(inode, name); 340 if (IS_ERR(page)) 341 return page; 342 343 if (S_ISDIR(inode->i_mode)) { 344 err = make_empty_dir(inode, dir, page); 345 if (err) 346 goto error; 347 } 348 349 err = f2fs_init_acl(inode, dir); 350 if (err) 351 goto error; 352 353 err = f2fs_init_security(inode, dir, name, page); 354 if (err) 355 goto error; 356 357 wait_on_page_writeback(page); 358 } else { 359 page = get_node_page(F2FS_SB(dir->i_sb), inode->i_ino); 360 if (IS_ERR(page)) 361 return page; 362 363 wait_on_page_writeback(page); 364 set_cold_node(inode, page); 365 } 366 367 init_dent_inode(name, page); 368 369 /* 370 * This file should be checkpointed during fsync. 371 * We lost i_pino from now on. 372 */ 373 if (is_inode_flag_set(F2FS_I(inode), FI_INC_LINK)) { 374 file_lost_pino(inode); 375 inc_nlink(inode); 376 } 377 return page; 378 379 error: 380 f2fs_put_page(page, 1); 381 remove_inode_page(inode); 382 return ERR_PTR(err); 383 } 384 385 static void update_parent_metadata(struct inode *dir, struct inode *inode, 386 unsigned int current_depth) 387 { 388 if (is_inode_flag_set(F2FS_I(inode), FI_NEW_INODE)) { 389 if (S_ISDIR(inode->i_mode)) { 390 inc_nlink(dir); 391 set_inode_flag(F2FS_I(dir), FI_UPDATE_DIR); 392 } 393 clear_inode_flag(F2FS_I(inode), FI_NEW_INODE); 394 } 395 dir->i_mtime = dir->i_ctime = CURRENT_TIME; 396 if (F2FS_I(dir)->i_current_depth != current_depth) { 397 F2FS_I(dir)->i_current_depth = current_depth; 398 set_inode_flag(F2FS_I(dir), FI_UPDATE_DIR); 399 } 400 401 if (is_inode_flag_set(F2FS_I(dir), FI_UPDATE_DIR)) 402 update_inode_page(dir); 403 else 404 mark_inode_dirty(dir); 405 406 if (is_inode_flag_set(F2FS_I(inode), FI_INC_LINK)) 407 clear_inode_flag(F2FS_I(inode), FI_INC_LINK); 408 } 409 410 static int room_for_filename(struct f2fs_dentry_block *dentry_blk, int slots) 411 { 412 int bit_start = 0; 413 int zero_start, zero_end; 414 next: 415 zero_start = find_next_zero_bit_le(&dentry_blk->dentry_bitmap, 416 NR_DENTRY_IN_BLOCK, 417 bit_start); 418 if (zero_start >= NR_DENTRY_IN_BLOCK) 419 return NR_DENTRY_IN_BLOCK; 420 421 zero_end = find_next_bit_le(&dentry_blk->dentry_bitmap, 422 NR_DENTRY_IN_BLOCK, 423 zero_start); 424 if (zero_end - zero_start >= slots) 425 return zero_start; 426 427 bit_start = zero_end + 1; 428 429 if (zero_end + 1 >= NR_DENTRY_IN_BLOCK) 430 return NR_DENTRY_IN_BLOCK; 431 goto next; 432 } 433 434 /* 435 * Caller should grab and release a mutex by calling mutex_lock_op() and 436 * mutex_unlock_op(). 437 */ 438 int __f2fs_add_link(struct inode *dir, const struct qstr *name, struct inode *inode) 439 { 440 unsigned int bit_pos; 441 unsigned int level; 442 unsigned int current_depth; 443 unsigned long bidx, block; 444 f2fs_hash_t dentry_hash; 445 struct f2fs_dir_entry *de; 446 unsigned int nbucket, nblock; 447 size_t namelen = name->len; 448 struct page *dentry_page = NULL; 449 struct f2fs_dentry_block *dentry_blk = NULL; 450 int slots = GET_DENTRY_SLOTS(namelen); 451 struct page *page; 452 int err = 0; 453 int i; 454 455 dentry_hash = f2fs_dentry_hash(name->name, name->len); 456 level = 0; 457 current_depth = F2FS_I(dir)->i_current_depth; 458 if (F2FS_I(dir)->chash == dentry_hash) { 459 level = F2FS_I(dir)->clevel; 460 F2FS_I(dir)->chash = 0; 461 } 462 463 start: 464 if (current_depth == MAX_DIR_HASH_DEPTH) 465 return -ENOSPC; 466 467 /* Increase the depth, if required */ 468 if (level == current_depth) 469 ++current_depth; 470 471 nbucket = dir_buckets(level); 472 nblock = bucket_blocks(level); 473 474 bidx = dir_block_index(level, (le32_to_cpu(dentry_hash) % nbucket)); 475 476 for (block = bidx; block <= (bidx + nblock - 1); block++) { 477 dentry_page = get_new_data_page(dir, NULL, block, true); 478 if (IS_ERR(dentry_page)) 479 return PTR_ERR(dentry_page); 480 481 dentry_blk = kmap(dentry_page); 482 bit_pos = room_for_filename(dentry_blk, slots); 483 if (bit_pos < NR_DENTRY_IN_BLOCK) 484 goto add_dentry; 485 486 kunmap(dentry_page); 487 f2fs_put_page(dentry_page, 1); 488 } 489 490 /* Move to next level to find the empty slot for new dentry */ 491 ++level; 492 goto start; 493 add_dentry: 494 wait_on_page_writeback(dentry_page); 495 496 page = init_inode_metadata(inode, dir, name); 497 if (IS_ERR(page)) { 498 err = PTR_ERR(page); 499 goto fail; 500 } 501 de = &dentry_blk->dentry[bit_pos]; 502 de->hash_code = dentry_hash; 503 de->name_len = cpu_to_le16(namelen); 504 memcpy(dentry_blk->filename[bit_pos], name->name, name->len); 505 de->ino = cpu_to_le32(inode->i_ino); 506 set_de_type(de, inode); 507 for (i = 0; i < slots; i++) 508 test_and_set_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap); 509 set_page_dirty(dentry_page); 510 511 /* we don't need to mark_inode_dirty now */ 512 F2FS_I(inode)->i_pino = dir->i_ino; 513 update_inode(inode, page); 514 f2fs_put_page(page, 1); 515 516 update_parent_metadata(dir, inode, current_depth); 517 fail: 518 clear_inode_flag(F2FS_I(dir), FI_UPDATE_DIR); 519 kunmap(dentry_page); 520 f2fs_put_page(dentry_page, 1); 521 return err; 522 } 523 524 /* 525 * It only removes the dentry from the dentry page,corresponding name 526 * entry in name page does not need to be touched during deletion. 527 */ 528 void f2fs_delete_entry(struct f2fs_dir_entry *dentry, struct page *page, 529 struct inode *inode) 530 { 531 struct f2fs_dentry_block *dentry_blk; 532 unsigned int bit_pos; 533 struct address_space *mapping = page->mapping; 534 struct inode *dir = mapping->host; 535 struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb); 536 int slots = GET_DENTRY_SLOTS(le16_to_cpu(dentry->name_len)); 537 void *kaddr = page_address(page); 538 int i; 539 540 lock_page(page); 541 wait_on_page_writeback(page); 542 543 dentry_blk = (struct f2fs_dentry_block *)kaddr; 544 bit_pos = dentry - (struct f2fs_dir_entry *)dentry_blk->dentry; 545 for (i = 0; i < slots; i++) 546 test_and_clear_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap); 547 548 /* Let's check and deallocate this dentry page */ 549 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 550 NR_DENTRY_IN_BLOCK, 551 0); 552 kunmap(page); /* kunmap - pair of f2fs_find_entry */ 553 set_page_dirty(page); 554 555 dir->i_ctime = dir->i_mtime = CURRENT_TIME; 556 557 if (inode && S_ISDIR(inode->i_mode)) { 558 drop_nlink(dir); 559 update_inode_page(dir); 560 } else { 561 mark_inode_dirty(dir); 562 } 563 564 if (inode) { 565 inode->i_ctime = CURRENT_TIME; 566 drop_nlink(inode); 567 if (S_ISDIR(inode->i_mode)) { 568 drop_nlink(inode); 569 i_size_write(inode, 0); 570 } 571 update_inode_page(inode); 572 573 if (inode->i_nlink == 0) 574 add_orphan_inode(sbi, inode->i_ino); 575 else 576 release_orphan_inode(sbi); 577 } 578 579 if (bit_pos == NR_DENTRY_IN_BLOCK) { 580 truncate_hole(dir, page->index, page->index + 1); 581 clear_page_dirty_for_io(page); 582 ClearPageUptodate(page); 583 dec_page_count(sbi, F2FS_DIRTY_DENTS); 584 inode_dec_dirty_dents(dir); 585 } 586 f2fs_put_page(page, 1); 587 } 588 589 bool f2fs_empty_dir(struct inode *dir) 590 { 591 unsigned long bidx; 592 struct page *dentry_page; 593 unsigned int bit_pos; 594 struct f2fs_dentry_block *dentry_blk; 595 unsigned long nblock = dir_blocks(dir); 596 597 for (bidx = 0; bidx < nblock; bidx++) { 598 void *kaddr; 599 dentry_page = get_lock_data_page(dir, bidx); 600 if (IS_ERR(dentry_page)) { 601 if (PTR_ERR(dentry_page) == -ENOENT) 602 continue; 603 else 604 return false; 605 } 606 607 kaddr = kmap_atomic(dentry_page); 608 dentry_blk = (struct f2fs_dentry_block *)kaddr; 609 if (bidx == 0) 610 bit_pos = 2; 611 else 612 bit_pos = 0; 613 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 614 NR_DENTRY_IN_BLOCK, 615 bit_pos); 616 kunmap_atomic(kaddr); 617 618 f2fs_put_page(dentry_page, 1); 619 620 if (bit_pos < NR_DENTRY_IN_BLOCK) 621 return false; 622 } 623 return true; 624 } 625 626 static int f2fs_readdir(struct file *file, struct dir_context *ctx) 627 { 628 struct inode *inode = file_inode(file); 629 unsigned long npages = dir_blocks(inode); 630 unsigned int bit_pos = 0; 631 struct f2fs_dentry_block *dentry_blk = NULL; 632 struct f2fs_dir_entry *de = NULL; 633 struct page *dentry_page = NULL; 634 unsigned int n = ((unsigned long)ctx->pos / NR_DENTRY_IN_BLOCK); 635 unsigned char d_type = DT_UNKNOWN; 636 637 bit_pos = ((unsigned long)ctx->pos % NR_DENTRY_IN_BLOCK); 638 639 for ( ; n < npages; n++) { 640 dentry_page = get_lock_data_page(inode, n); 641 if (IS_ERR(dentry_page)) 642 continue; 643 644 dentry_blk = kmap(dentry_page); 645 while (bit_pos < NR_DENTRY_IN_BLOCK) { 646 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 647 NR_DENTRY_IN_BLOCK, 648 bit_pos); 649 if (bit_pos >= NR_DENTRY_IN_BLOCK) 650 break; 651 652 de = &dentry_blk->dentry[bit_pos]; 653 if (de->file_type < F2FS_FT_MAX) 654 d_type = f2fs_filetype_table[de->file_type]; 655 else 656 d_type = DT_UNKNOWN; 657 if (!dir_emit(ctx, 658 dentry_blk->filename[bit_pos], 659 le16_to_cpu(de->name_len), 660 le32_to_cpu(de->ino), d_type)) 661 goto stop; 662 663 bit_pos += GET_DENTRY_SLOTS(le16_to_cpu(de->name_len)); 664 ctx->pos = n * NR_DENTRY_IN_BLOCK + bit_pos; 665 } 666 bit_pos = 0; 667 ctx->pos = (n + 1) * NR_DENTRY_IN_BLOCK; 668 kunmap(dentry_page); 669 f2fs_put_page(dentry_page, 1); 670 dentry_page = NULL; 671 } 672 stop: 673 if (dentry_page && !IS_ERR(dentry_page)) { 674 kunmap(dentry_page); 675 f2fs_put_page(dentry_page, 1); 676 } 677 678 return 0; 679 } 680 681 const struct file_operations f2fs_dir_operations = { 682 .llseek = generic_file_llseek, 683 .read = generic_read_dir, 684 .iterate = f2fs_readdir, 685 .fsync = f2fs_sync_file, 686 .unlocked_ioctl = f2fs_ioctl, 687 }; 688