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