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 mode_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); 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 (npages == 0) 193 return NULL; 194 195 *res_page = NULL; 196 197 name_hash = f2fs_dentry_hash(name, namelen); 198 max_depth = F2FS_I(dir)->i_current_depth; 199 200 for (level = 0; level < max_depth; level++) { 201 de = find_in_level(dir, level, name, 202 namelen, name_hash, res_page); 203 if (de) 204 break; 205 } 206 if (!de && F2FS_I(dir)->chash != name_hash) { 207 F2FS_I(dir)->chash = name_hash; 208 F2FS_I(dir)->clevel = level - 1; 209 } 210 return de; 211 } 212 213 struct f2fs_dir_entry *f2fs_parent_dir(struct inode *dir, struct page **p) 214 { 215 struct page *page = NULL; 216 struct f2fs_dir_entry *de = NULL; 217 struct f2fs_dentry_block *dentry_blk = NULL; 218 219 page = get_lock_data_page(dir, 0); 220 if (IS_ERR(page)) 221 return NULL; 222 223 dentry_blk = kmap(page); 224 de = &dentry_blk->dentry[1]; 225 *p = page; 226 unlock_page(page); 227 return de; 228 } 229 230 ino_t f2fs_inode_by_name(struct inode *dir, struct qstr *qstr) 231 { 232 ino_t res = 0; 233 struct f2fs_dir_entry *de; 234 struct page *page; 235 236 de = f2fs_find_entry(dir, qstr, &page); 237 if (de) { 238 res = le32_to_cpu(de->ino); 239 kunmap(page); 240 f2fs_put_page(page, 0); 241 } 242 243 return res; 244 } 245 246 void f2fs_set_link(struct inode *dir, struct f2fs_dir_entry *de, 247 struct page *page, struct inode *inode) 248 { 249 struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb); 250 251 mutex_lock_op(sbi, DENTRY_OPS); 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 mutex_unlock_op(sbi, DENTRY_OPS); 266 } 267 268 void init_dent_inode(const struct qstr *name, struct page *ipage) 269 { 270 struct f2fs_node *rn; 271 272 if (IS_ERR(ipage)) 273 return; 274 275 wait_on_page_writeback(ipage); 276 277 /* copy name info. to this inode page */ 278 rn = (struct f2fs_node *)page_address(ipage); 279 rn->i.i_namelen = cpu_to_le32(name->len); 280 memcpy(rn->i.i_name, name->name, name->len); 281 set_page_dirty(ipage); 282 } 283 284 static int init_inode_metadata(struct inode *inode, 285 struct inode *dir, const struct qstr *name) 286 { 287 if (is_inode_flag_set(F2FS_I(inode), FI_NEW_INODE)) { 288 int err; 289 err = new_inode_page(inode, name); 290 if (err) 291 return err; 292 293 if (S_ISDIR(inode->i_mode)) { 294 err = f2fs_make_empty(inode, dir); 295 if (err) { 296 remove_inode_page(inode); 297 return err; 298 } 299 } 300 301 err = f2fs_init_acl(inode, dir); 302 if (err) { 303 remove_inode_page(inode); 304 return err; 305 } 306 } else { 307 struct page *ipage; 308 ipage = get_node_page(F2FS_SB(dir->i_sb), inode->i_ino); 309 if (IS_ERR(ipage)) 310 return PTR_ERR(ipage); 311 set_cold_node(inode, ipage); 312 init_dent_inode(name, ipage); 313 f2fs_put_page(ipage, 1); 314 } 315 if (is_inode_flag_set(F2FS_I(inode), FI_INC_LINK)) { 316 inc_nlink(inode); 317 f2fs_write_inode(inode, NULL); 318 } 319 return 0; 320 } 321 322 static void update_parent_metadata(struct inode *dir, struct inode *inode, 323 unsigned int current_depth) 324 { 325 bool need_dir_update = false; 326 327 if (is_inode_flag_set(F2FS_I(inode), FI_NEW_INODE)) { 328 if (S_ISDIR(inode->i_mode)) { 329 inc_nlink(dir); 330 need_dir_update = true; 331 } 332 clear_inode_flag(F2FS_I(inode), FI_NEW_INODE); 333 } 334 dir->i_mtime = dir->i_ctime = CURRENT_TIME; 335 if (F2FS_I(dir)->i_current_depth != current_depth) { 336 F2FS_I(dir)->i_current_depth = current_depth; 337 need_dir_update = true; 338 } 339 340 if (need_dir_update) 341 f2fs_write_inode(dir, NULL); 342 else 343 mark_inode_dirty(dir); 344 345 if (is_inode_flag_set(F2FS_I(inode), FI_INC_LINK)) 346 clear_inode_flag(F2FS_I(inode), FI_INC_LINK); 347 } 348 349 static int room_for_filename(struct f2fs_dentry_block *dentry_blk, int slots) 350 { 351 int bit_start = 0; 352 int zero_start, zero_end; 353 next: 354 zero_start = find_next_zero_bit_le(&dentry_blk->dentry_bitmap, 355 NR_DENTRY_IN_BLOCK, 356 bit_start); 357 if (zero_start >= NR_DENTRY_IN_BLOCK) 358 return NR_DENTRY_IN_BLOCK; 359 360 zero_end = find_next_bit_le(&dentry_blk->dentry_bitmap, 361 NR_DENTRY_IN_BLOCK, 362 zero_start); 363 if (zero_end - zero_start >= slots) 364 return zero_start; 365 366 bit_start = zero_end + 1; 367 368 if (zero_end + 1 >= NR_DENTRY_IN_BLOCK) 369 return NR_DENTRY_IN_BLOCK; 370 goto next; 371 } 372 373 int __f2fs_add_link(struct inode *dir, const struct qstr *name, struct inode *inode) 374 { 375 unsigned int bit_pos; 376 unsigned int level; 377 unsigned int current_depth; 378 unsigned long bidx, block; 379 f2fs_hash_t dentry_hash; 380 struct f2fs_dir_entry *de; 381 unsigned int nbucket, nblock; 382 struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb); 383 size_t namelen = name->len; 384 struct page *dentry_page = NULL; 385 struct f2fs_dentry_block *dentry_blk = NULL; 386 int slots = GET_DENTRY_SLOTS(namelen); 387 int err = 0; 388 int i; 389 390 dentry_hash = f2fs_dentry_hash(name->name, name->len); 391 level = 0; 392 current_depth = F2FS_I(dir)->i_current_depth; 393 if (F2FS_I(dir)->chash == dentry_hash) { 394 level = F2FS_I(dir)->clevel; 395 F2FS_I(dir)->chash = 0; 396 } 397 398 start: 399 if (current_depth == MAX_DIR_HASH_DEPTH) 400 return -ENOSPC; 401 402 /* Increase the depth, if required */ 403 if (level == current_depth) 404 ++current_depth; 405 406 nbucket = dir_buckets(level); 407 nblock = bucket_blocks(level); 408 409 bidx = dir_block_index(level, (le32_to_cpu(dentry_hash) % nbucket)); 410 411 for (block = bidx; block <= (bidx + nblock - 1); block++) { 412 mutex_lock_op(sbi, DENTRY_OPS); 413 dentry_page = get_new_data_page(dir, block, true); 414 if (IS_ERR(dentry_page)) { 415 mutex_unlock_op(sbi, DENTRY_OPS); 416 return PTR_ERR(dentry_page); 417 } 418 419 dentry_blk = kmap(dentry_page); 420 bit_pos = room_for_filename(dentry_blk, slots); 421 if (bit_pos < NR_DENTRY_IN_BLOCK) 422 goto add_dentry; 423 424 kunmap(dentry_page); 425 f2fs_put_page(dentry_page, 1); 426 mutex_unlock_op(sbi, DENTRY_OPS); 427 } 428 429 /* Move to next level to find the empty slot for new dentry */ 430 ++level; 431 goto start; 432 add_dentry: 433 err = init_inode_metadata(inode, dir, name); 434 if (err) 435 goto fail; 436 437 wait_on_page_writeback(dentry_page); 438 439 de = &dentry_blk->dentry[bit_pos]; 440 de->hash_code = dentry_hash; 441 de->name_len = cpu_to_le16(namelen); 442 memcpy(dentry_blk->filename[bit_pos], name->name, name->len); 443 de->ino = cpu_to_le32(inode->i_ino); 444 set_de_type(de, inode); 445 for (i = 0; i < slots; i++) 446 test_and_set_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap); 447 set_page_dirty(dentry_page); 448 449 update_parent_metadata(dir, inode, current_depth); 450 451 /* update parent inode number before releasing dentry page */ 452 F2FS_I(inode)->i_pino = dir->i_ino; 453 fail: 454 kunmap(dentry_page); 455 f2fs_put_page(dentry_page, 1); 456 mutex_unlock_op(sbi, DENTRY_OPS); 457 return err; 458 } 459 460 /* 461 * It only removes the dentry from the dentry page,corresponding name 462 * entry in name page does not need to be touched during deletion. 463 */ 464 void f2fs_delete_entry(struct f2fs_dir_entry *dentry, struct page *page, 465 struct inode *inode) 466 { 467 struct f2fs_dentry_block *dentry_blk; 468 unsigned int bit_pos; 469 struct address_space *mapping = page->mapping; 470 struct inode *dir = mapping->host; 471 struct f2fs_sb_info *sbi = F2FS_SB(dir->i_sb); 472 int slots = GET_DENTRY_SLOTS(le16_to_cpu(dentry->name_len)); 473 void *kaddr = page_address(page); 474 int i; 475 476 mutex_lock_op(sbi, DENTRY_OPS); 477 478 lock_page(page); 479 wait_on_page_writeback(page); 480 481 dentry_blk = (struct f2fs_dentry_block *)kaddr; 482 bit_pos = dentry - (struct f2fs_dir_entry *)dentry_blk->dentry; 483 for (i = 0; i < slots; i++) 484 test_and_clear_bit_le(bit_pos + i, &dentry_blk->dentry_bitmap); 485 486 /* Let's check and deallocate this dentry page */ 487 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 488 NR_DENTRY_IN_BLOCK, 489 0); 490 kunmap(page); /* kunmap - pair of f2fs_find_entry */ 491 set_page_dirty(page); 492 493 dir->i_ctime = dir->i_mtime = CURRENT_TIME; 494 495 if (inode && S_ISDIR(inode->i_mode)) { 496 drop_nlink(dir); 497 f2fs_write_inode(dir, NULL); 498 } else { 499 mark_inode_dirty(dir); 500 } 501 502 if (inode) { 503 inode->i_ctime = CURRENT_TIME; 504 drop_nlink(inode); 505 if (S_ISDIR(inode->i_mode)) { 506 drop_nlink(inode); 507 i_size_write(inode, 0); 508 } 509 f2fs_write_inode(inode, NULL); 510 if (inode->i_nlink == 0) 511 add_orphan_inode(sbi, inode->i_ino); 512 } 513 514 if (bit_pos == NR_DENTRY_IN_BLOCK) { 515 truncate_hole(dir, page->index, page->index + 1); 516 clear_page_dirty_for_io(page); 517 ClearPageUptodate(page); 518 dec_page_count(sbi, F2FS_DIRTY_DENTS); 519 inode_dec_dirty_dents(dir); 520 } 521 f2fs_put_page(page, 1); 522 523 mutex_unlock_op(sbi, DENTRY_OPS); 524 } 525 526 int f2fs_make_empty(struct inode *inode, struct inode *parent) 527 { 528 struct page *dentry_page; 529 struct f2fs_dentry_block *dentry_blk; 530 struct f2fs_dir_entry *de; 531 void *kaddr; 532 533 dentry_page = get_new_data_page(inode, 0, true); 534 if (IS_ERR(dentry_page)) 535 return PTR_ERR(dentry_page); 536 537 kaddr = kmap_atomic(dentry_page); 538 dentry_blk = (struct f2fs_dentry_block *)kaddr; 539 540 de = &dentry_blk->dentry[0]; 541 de->name_len = cpu_to_le16(1); 542 de->hash_code = f2fs_dentry_hash(".", 1); 543 de->ino = cpu_to_le32(inode->i_ino); 544 memcpy(dentry_blk->filename[0], ".", 1); 545 set_de_type(de, inode); 546 547 de = &dentry_blk->dentry[1]; 548 de->hash_code = f2fs_dentry_hash("..", 2); 549 de->name_len = cpu_to_le16(2); 550 de->ino = cpu_to_le32(parent->i_ino); 551 memcpy(dentry_blk->filename[1], "..", 2); 552 set_de_type(de, inode); 553 554 test_and_set_bit_le(0, &dentry_blk->dentry_bitmap); 555 test_and_set_bit_le(1, &dentry_blk->dentry_bitmap); 556 kunmap_atomic(kaddr); 557 558 set_page_dirty(dentry_page); 559 f2fs_put_page(dentry_page, 1); 560 return 0; 561 } 562 563 bool f2fs_empty_dir(struct inode *dir) 564 { 565 unsigned long bidx; 566 struct page *dentry_page; 567 unsigned int bit_pos; 568 struct f2fs_dentry_block *dentry_blk; 569 unsigned long nblock = dir_blocks(dir); 570 571 for (bidx = 0; bidx < nblock; bidx++) { 572 void *kaddr; 573 dentry_page = get_lock_data_page(dir, bidx); 574 if (IS_ERR(dentry_page)) { 575 if (PTR_ERR(dentry_page) == -ENOENT) 576 continue; 577 else 578 return false; 579 } 580 581 kaddr = kmap_atomic(dentry_page); 582 dentry_blk = (struct f2fs_dentry_block *)kaddr; 583 if (bidx == 0) 584 bit_pos = 2; 585 else 586 bit_pos = 0; 587 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 588 NR_DENTRY_IN_BLOCK, 589 bit_pos); 590 kunmap_atomic(kaddr); 591 592 f2fs_put_page(dentry_page, 1); 593 594 if (bit_pos < NR_DENTRY_IN_BLOCK) 595 return false; 596 } 597 return true; 598 } 599 600 static int f2fs_readdir(struct file *file, void *dirent, filldir_t filldir) 601 { 602 unsigned long pos = file->f_pos; 603 struct inode *inode = file_inode(file); 604 unsigned long npages = dir_blocks(inode); 605 unsigned char *types = NULL; 606 unsigned int bit_pos = 0, start_bit_pos = 0; 607 int over = 0; 608 struct f2fs_dentry_block *dentry_blk = NULL; 609 struct f2fs_dir_entry *de = NULL; 610 struct page *dentry_page = NULL; 611 unsigned int n = 0; 612 unsigned char d_type = DT_UNKNOWN; 613 int slots; 614 615 types = f2fs_filetype_table; 616 bit_pos = (pos % NR_DENTRY_IN_BLOCK); 617 n = (pos / NR_DENTRY_IN_BLOCK); 618 619 for ( ; n < npages; n++) { 620 dentry_page = get_lock_data_page(inode, n); 621 if (IS_ERR(dentry_page)) 622 continue; 623 624 start_bit_pos = bit_pos; 625 dentry_blk = kmap(dentry_page); 626 while (bit_pos < NR_DENTRY_IN_BLOCK) { 627 d_type = DT_UNKNOWN; 628 bit_pos = find_next_bit_le(&dentry_blk->dentry_bitmap, 629 NR_DENTRY_IN_BLOCK, 630 bit_pos); 631 if (bit_pos >= NR_DENTRY_IN_BLOCK) 632 break; 633 634 de = &dentry_blk->dentry[bit_pos]; 635 if (types && de->file_type < F2FS_FT_MAX) 636 d_type = types[de->file_type]; 637 638 over = filldir(dirent, 639 dentry_blk->filename[bit_pos], 640 le16_to_cpu(de->name_len), 641 (n * NR_DENTRY_IN_BLOCK) + bit_pos, 642 le32_to_cpu(de->ino), d_type); 643 if (over) { 644 file->f_pos += bit_pos - start_bit_pos; 645 goto success; 646 } 647 slots = GET_DENTRY_SLOTS(le16_to_cpu(de->name_len)); 648 bit_pos += slots; 649 } 650 bit_pos = 0; 651 file->f_pos = (n + 1) * NR_DENTRY_IN_BLOCK; 652 kunmap(dentry_page); 653 f2fs_put_page(dentry_page, 1); 654 dentry_page = NULL; 655 } 656 success: 657 if (dentry_page && !IS_ERR(dentry_page)) { 658 kunmap(dentry_page); 659 f2fs_put_page(dentry_page, 1); 660 } 661 662 return 0; 663 } 664 665 const struct file_operations f2fs_dir_operations = { 666 .llseek = generic_file_llseek, 667 .read = generic_read_dir, 668 .readdir = f2fs_readdir, 669 .fsync = f2fs_sync_file, 670 .unlocked_ioctl = f2fs_ioctl, 671 }; 672