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