1 // SPDX-License-Identifier: GPL-2.0+ 2 /* 3 * NILFS directory entry operations 4 * 5 * Copyright (C) 2005-2008 Nippon Telegraph and Telephone Corporation. 6 * 7 * Modified for NILFS by Amagai Yoshiji. 8 */ 9 /* 10 * linux/fs/ext2/dir.c 11 * 12 * Copyright (C) 1992, 1993, 1994, 1995 13 * Remy Card (card@masi.ibp.fr) 14 * Laboratoire MASI - Institut Blaise Pascal 15 * Universite Pierre et Marie Curie (Paris VI) 16 * 17 * from 18 * 19 * linux/fs/minix/dir.c 20 * 21 * Copyright (C) 1991, 1992 Linus Torvalds 22 * 23 * ext2 directory handling functions 24 * 25 * Big-endian to little-endian byte-swapping/bitmaps by 26 * David S. Miller (davem@caip.rutgers.edu), 1995 27 * 28 * All code that works with directory layout had been switched to pagecache 29 * and moved here. AV 30 */ 31 32 #include <linux/pagemap.h> 33 #include "nilfs.h" 34 #include "page.h" 35 36 static inline unsigned int nilfs_rec_len_from_disk(__le16 dlen) 37 { 38 unsigned int len = le16_to_cpu(dlen); 39 40 #if (PAGE_SIZE >= 65536) 41 if (len == NILFS_MAX_REC_LEN) 42 return 1 << 16; 43 #endif 44 return len; 45 } 46 47 static inline __le16 nilfs_rec_len_to_disk(unsigned int len) 48 { 49 #if (PAGE_SIZE >= 65536) 50 if (len == (1 << 16)) 51 return cpu_to_le16(NILFS_MAX_REC_LEN); 52 53 BUG_ON(len > (1 << 16)); 54 #endif 55 return cpu_to_le16(len); 56 } 57 58 /* 59 * nilfs uses block-sized chunks. Arguably, sector-sized ones would be 60 * more robust, but we have what we have 61 */ 62 static inline unsigned int nilfs_chunk_size(struct inode *inode) 63 { 64 return inode->i_sb->s_blocksize; 65 } 66 67 static inline void nilfs_put_page(struct page *page) 68 { 69 kunmap(page); 70 put_page(page); 71 } 72 73 /* 74 * Return the offset into page `page_nr' of the last valid 75 * byte in that page, plus one. 76 */ 77 static unsigned int nilfs_last_byte(struct inode *inode, unsigned long page_nr) 78 { 79 unsigned int last_byte = inode->i_size; 80 81 last_byte -= page_nr << PAGE_SHIFT; 82 if (last_byte > PAGE_SIZE) 83 last_byte = PAGE_SIZE; 84 return last_byte; 85 } 86 87 static int nilfs_prepare_chunk(struct page *page, unsigned int from, 88 unsigned int to) 89 { 90 loff_t pos = page_offset(page) + from; 91 92 return __block_write_begin(page, pos, to - from, nilfs_get_block); 93 } 94 95 static void nilfs_commit_chunk(struct page *page, 96 struct address_space *mapping, 97 unsigned int from, unsigned int to) 98 { 99 struct inode *dir = mapping->host; 100 loff_t pos = page_offset(page) + from; 101 unsigned int len = to - from; 102 unsigned int nr_dirty, copied; 103 int err; 104 105 nr_dirty = nilfs_page_count_clean_buffers(page, from, to); 106 copied = block_write_end(NULL, mapping, pos, len, len, page, NULL); 107 if (pos + copied > dir->i_size) 108 i_size_write(dir, pos + copied); 109 if (IS_DIRSYNC(dir)) 110 nilfs_set_transaction_flag(NILFS_TI_SYNC); 111 err = nilfs_set_file_dirty(dir, nr_dirty); 112 WARN_ON(err); /* do not happen */ 113 unlock_page(page); 114 } 115 116 static bool nilfs_check_page(struct page *page) 117 { 118 struct inode *dir = page->mapping->host; 119 struct super_block *sb = dir->i_sb; 120 unsigned int chunk_size = nilfs_chunk_size(dir); 121 char *kaddr = page_address(page); 122 unsigned int offs, rec_len; 123 unsigned int limit = PAGE_SIZE; 124 struct nilfs_dir_entry *p; 125 char *error; 126 127 if ((dir->i_size >> PAGE_SHIFT) == page->index) { 128 limit = dir->i_size & ~PAGE_MASK; 129 if (limit & (chunk_size - 1)) 130 goto Ebadsize; 131 if (!limit) 132 goto out; 133 } 134 for (offs = 0; offs <= limit - NILFS_DIR_REC_LEN(1); offs += rec_len) { 135 p = (struct nilfs_dir_entry *)(kaddr + offs); 136 rec_len = nilfs_rec_len_from_disk(p->rec_len); 137 138 if (rec_len < NILFS_DIR_REC_LEN(1)) 139 goto Eshort; 140 if (rec_len & 3) 141 goto Ealign; 142 if (rec_len < NILFS_DIR_REC_LEN(p->name_len)) 143 goto Enamelen; 144 if (((offs + rec_len - 1) ^ offs) & ~(chunk_size-1)) 145 goto Espan; 146 } 147 if (offs != limit) 148 goto Eend; 149 out: 150 SetPageChecked(page); 151 return true; 152 153 /* Too bad, we had an error */ 154 155 Ebadsize: 156 nilfs_error(sb, 157 "size of directory #%lu is not a multiple of chunk size", 158 dir->i_ino); 159 goto fail; 160 Eshort: 161 error = "rec_len is smaller than minimal"; 162 goto bad_entry; 163 Ealign: 164 error = "unaligned directory entry"; 165 goto bad_entry; 166 Enamelen: 167 error = "rec_len is too small for name_len"; 168 goto bad_entry; 169 Espan: 170 error = "directory entry across blocks"; 171 bad_entry: 172 nilfs_error(sb, 173 "bad entry in directory #%lu: %s - offset=%lu, inode=%lu, rec_len=%d, name_len=%d", 174 dir->i_ino, error, (page->index << PAGE_SHIFT) + offs, 175 (unsigned long)le64_to_cpu(p->inode), 176 rec_len, p->name_len); 177 goto fail; 178 Eend: 179 p = (struct nilfs_dir_entry *)(kaddr + offs); 180 nilfs_error(sb, 181 "entry in directory #%lu spans the page boundary offset=%lu, inode=%lu", 182 dir->i_ino, (page->index << PAGE_SHIFT) + offs, 183 (unsigned long)le64_to_cpu(p->inode)); 184 fail: 185 SetPageError(page); 186 return false; 187 } 188 189 static void *nilfs_get_page(struct inode *dir, unsigned long n, 190 struct page **pagep) 191 { 192 struct address_space *mapping = dir->i_mapping; 193 struct page *page = read_mapping_page(mapping, n, NULL); 194 void *kaddr; 195 196 if (IS_ERR(page)) 197 return page; 198 199 kaddr = kmap(page); 200 if (unlikely(!PageChecked(page))) { 201 if (!nilfs_check_page(page)) 202 goto fail; 203 } 204 205 *pagep = page; 206 return kaddr; 207 208 fail: 209 nilfs_put_page(page); 210 return ERR_PTR(-EIO); 211 } 212 213 /* 214 * NOTE! unlike strncmp, nilfs_match returns 1 for success, 0 for failure. 215 * 216 * len <= NILFS_NAME_LEN and de != NULL are guaranteed by caller. 217 */ 218 static int 219 nilfs_match(int len, const unsigned char *name, struct nilfs_dir_entry *de) 220 { 221 if (len != de->name_len) 222 return 0; 223 if (!de->inode) 224 return 0; 225 return !memcmp(name, de->name, len); 226 } 227 228 /* 229 * p is at least 6 bytes before the end of page 230 */ 231 static struct nilfs_dir_entry *nilfs_next_entry(struct nilfs_dir_entry *p) 232 { 233 return (struct nilfs_dir_entry *)((char *)p + 234 nilfs_rec_len_from_disk(p->rec_len)); 235 } 236 237 static unsigned char 238 nilfs_filetype_table[NILFS_FT_MAX] = { 239 [NILFS_FT_UNKNOWN] = DT_UNKNOWN, 240 [NILFS_FT_REG_FILE] = DT_REG, 241 [NILFS_FT_DIR] = DT_DIR, 242 [NILFS_FT_CHRDEV] = DT_CHR, 243 [NILFS_FT_BLKDEV] = DT_BLK, 244 [NILFS_FT_FIFO] = DT_FIFO, 245 [NILFS_FT_SOCK] = DT_SOCK, 246 [NILFS_FT_SYMLINK] = DT_LNK, 247 }; 248 249 #define S_SHIFT 12 250 static unsigned char 251 nilfs_type_by_mode[(S_IFMT >> S_SHIFT) + 1] = { 252 [S_IFREG >> S_SHIFT] = NILFS_FT_REG_FILE, 253 [S_IFDIR >> S_SHIFT] = NILFS_FT_DIR, 254 [S_IFCHR >> S_SHIFT] = NILFS_FT_CHRDEV, 255 [S_IFBLK >> S_SHIFT] = NILFS_FT_BLKDEV, 256 [S_IFIFO >> S_SHIFT] = NILFS_FT_FIFO, 257 [S_IFSOCK >> S_SHIFT] = NILFS_FT_SOCK, 258 [S_IFLNK >> S_SHIFT] = NILFS_FT_SYMLINK, 259 }; 260 261 static void nilfs_set_de_type(struct nilfs_dir_entry *de, struct inode *inode) 262 { 263 umode_t mode = inode->i_mode; 264 265 de->file_type = nilfs_type_by_mode[(mode & S_IFMT)>>S_SHIFT]; 266 } 267 268 static int nilfs_readdir(struct file *file, struct dir_context *ctx) 269 { 270 loff_t pos = ctx->pos; 271 struct inode *inode = file_inode(file); 272 struct super_block *sb = inode->i_sb; 273 unsigned int offset = pos & ~PAGE_MASK; 274 unsigned long n = pos >> PAGE_SHIFT; 275 unsigned long npages = dir_pages(inode); 276 277 if (pos > inode->i_size - NILFS_DIR_REC_LEN(1)) 278 return 0; 279 280 for ( ; n < npages; n++, offset = 0) { 281 char *kaddr, *limit; 282 struct nilfs_dir_entry *de; 283 struct page *page; 284 285 kaddr = nilfs_get_page(inode, n, &page); 286 if (IS_ERR(kaddr)) { 287 nilfs_error(sb, "bad page in #%lu", inode->i_ino); 288 ctx->pos += PAGE_SIZE - offset; 289 return -EIO; 290 } 291 de = (struct nilfs_dir_entry *)(kaddr + offset); 292 limit = kaddr + nilfs_last_byte(inode, n) - 293 NILFS_DIR_REC_LEN(1); 294 for ( ; (char *)de <= limit; de = nilfs_next_entry(de)) { 295 if (de->rec_len == 0) { 296 nilfs_error(sb, "zero-length directory entry"); 297 nilfs_put_page(page); 298 return -EIO; 299 } 300 if (de->inode) { 301 unsigned char t; 302 303 if (de->file_type < NILFS_FT_MAX) 304 t = nilfs_filetype_table[de->file_type]; 305 else 306 t = DT_UNKNOWN; 307 308 if (!dir_emit(ctx, de->name, de->name_len, 309 le64_to_cpu(de->inode), t)) { 310 nilfs_put_page(page); 311 return 0; 312 } 313 } 314 ctx->pos += nilfs_rec_len_from_disk(de->rec_len); 315 } 316 nilfs_put_page(page); 317 } 318 return 0; 319 } 320 321 /* 322 * nilfs_find_entry() 323 * 324 * finds an entry in the specified directory with the wanted name. It 325 * returns the page in which the entry was found, and the entry itself 326 * (as a parameter - res_dir). Page is returned mapped and unlocked. 327 * Entry is guaranteed to be valid. 328 */ 329 struct nilfs_dir_entry * 330 nilfs_find_entry(struct inode *dir, const struct qstr *qstr, 331 struct page **res_page) 332 { 333 const unsigned char *name = qstr->name; 334 int namelen = qstr->len; 335 unsigned int reclen = NILFS_DIR_REC_LEN(namelen); 336 unsigned long start, n; 337 unsigned long npages = dir_pages(dir); 338 struct page *page = NULL; 339 struct nilfs_inode_info *ei = NILFS_I(dir); 340 struct nilfs_dir_entry *de; 341 342 if (npages == 0) 343 goto out; 344 345 /* OFFSET_CACHE */ 346 *res_page = NULL; 347 348 start = ei->i_dir_start_lookup; 349 if (start >= npages) 350 start = 0; 351 n = start; 352 do { 353 char *kaddr = nilfs_get_page(dir, n, &page); 354 355 if (!IS_ERR(kaddr)) { 356 de = (struct nilfs_dir_entry *)kaddr; 357 kaddr += nilfs_last_byte(dir, n) - reclen; 358 while ((char *) de <= kaddr) { 359 if (de->rec_len == 0) { 360 nilfs_error(dir->i_sb, 361 "zero-length directory entry"); 362 nilfs_put_page(page); 363 goto out; 364 } 365 if (nilfs_match(namelen, name, de)) 366 goto found; 367 de = nilfs_next_entry(de); 368 } 369 nilfs_put_page(page); 370 } 371 if (++n >= npages) 372 n = 0; 373 /* next page is past the blocks we've got */ 374 if (unlikely(n > (dir->i_blocks >> (PAGE_SHIFT - 9)))) { 375 nilfs_error(dir->i_sb, 376 "dir %lu size %lld exceeds block count %llu", 377 dir->i_ino, dir->i_size, 378 (unsigned long long)dir->i_blocks); 379 goto out; 380 } 381 } while (n != start); 382 out: 383 return NULL; 384 385 found: 386 *res_page = page; 387 ei->i_dir_start_lookup = n; 388 return de; 389 } 390 391 struct nilfs_dir_entry *nilfs_dotdot(struct inode *dir, struct page **p) 392 { 393 struct nilfs_dir_entry *de = nilfs_get_page(dir, 0, p); 394 395 if (IS_ERR(de)) 396 return NULL; 397 return nilfs_next_entry(de); 398 } 399 400 ino_t nilfs_inode_by_name(struct inode *dir, const struct qstr *qstr) 401 { 402 ino_t res = 0; 403 struct nilfs_dir_entry *de; 404 struct page *page; 405 406 de = nilfs_find_entry(dir, qstr, &page); 407 if (de) { 408 res = le64_to_cpu(de->inode); 409 kunmap(page); 410 put_page(page); 411 } 412 return res; 413 } 414 415 /* Releases the page */ 416 void nilfs_set_link(struct inode *dir, struct nilfs_dir_entry *de, 417 struct page *page, struct inode *inode) 418 { 419 unsigned int from = (char *)de - (char *)page_address(page); 420 unsigned int to = from + nilfs_rec_len_from_disk(de->rec_len); 421 struct address_space *mapping = page->mapping; 422 int err; 423 424 lock_page(page); 425 err = nilfs_prepare_chunk(page, from, to); 426 BUG_ON(err); 427 de->inode = cpu_to_le64(inode->i_ino); 428 nilfs_set_de_type(de, inode); 429 nilfs_commit_chunk(page, mapping, from, to); 430 nilfs_put_page(page); 431 dir->i_mtime = inode_set_ctime_current(dir); 432 } 433 434 /* 435 * Parent is locked. 436 */ 437 int nilfs_add_link(struct dentry *dentry, struct inode *inode) 438 { 439 struct inode *dir = d_inode(dentry->d_parent); 440 const unsigned char *name = dentry->d_name.name; 441 int namelen = dentry->d_name.len; 442 unsigned int chunk_size = nilfs_chunk_size(dir); 443 unsigned int reclen = NILFS_DIR_REC_LEN(namelen); 444 unsigned short rec_len, name_len; 445 struct page *page = NULL; 446 struct nilfs_dir_entry *de; 447 unsigned long npages = dir_pages(dir); 448 unsigned long n; 449 char *kaddr; 450 unsigned int from, to; 451 int err; 452 453 /* 454 * We take care of directory expansion in the same loop. 455 * This code plays outside i_size, so it locks the page 456 * to protect that region. 457 */ 458 for (n = 0; n <= npages; n++) { 459 char *dir_end; 460 461 kaddr = nilfs_get_page(dir, n, &page); 462 err = PTR_ERR(kaddr); 463 if (IS_ERR(kaddr)) 464 goto out; 465 lock_page(page); 466 dir_end = kaddr + nilfs_last_byte(dir, n); 467 de = (struct nilfs_dir_entry *)kaddr; 468 kaddr += PAGE_SIZE - reclen; 469 while ((char *)de <= kaddr) { 470 if ((char *)de == dir_end) { 471 /* We hit i_size */ 472 name_len = 0; 473 rec_len = chunk_size; 474 de->rec_len = nilfs_rec_len_to_disk(chunk_size); 475 de->inode = 0; 476 goto got_it; 477 } 478 if (de->rec_len == 0) { 479 nilfs_error(dir->i_sb, 480 "zero-length directory entry"); 481 err = -EIO; 482 goto out_unlock; 483 } 484 err = -EEXIST; 485 if (nilfs_match(namelen, name, de)) 486 goto out_unlock; 487 name_len = NILFS_DIR_REC_LEN(de->name_len); 488 rec_len = nilfs_rec_len_from_disk(de->rec_len); 489 if (!de->inode && rec_len >= reclen) 490 goto got_it; 491 if (rec_len >= name_len + reclen) 492 goto got_it; 493 de = (struct nilfs_dir_entry *)((char *)de + rec_len); 494 } 495 unlock_page(page); 496 nilfs_put_page(page); 497 } 498 BUG(); 499 return -EINVAL; 500 501 got_it: 502 from = (char *)de - (char *)page_address(page); 503 to = from + rec_len; 504 err = nilfs_prepare_chunk(page, from, to); 505 if (err) 506 goto out_unlock; 507 if (de->inode) { 508 struct nilfs_dir_entry *de1; 509 510 de1 = (struct nilfs_dir_entry *)((char *)de + name_len); 511 de1->rec_len = nilfs_rec_len_to_disk(rec_len - name_len); 512 de->rec_len = nilfs_rec_len_to_disk(name_len); 513 de = de1; 514 } 515 de->name_len = namelen; 516 memcpy(de->name, name, namelen); 517 de->inode = cpu_to_le64(inode->i_ino); 518 nilfs_set_de_type(de, inode); 519 nilfs_commit_chunk(page, page->mapping, from, to); 520 dir->i_mtime = inode_set_ctime_current(dir); 521 nilfs_mark_inode_dirty(dir); 522 /* OFFSET_CACHE */ 523 out_put: 524 nilfs_put_page(page); 525 out: 526 return err; 527 out_unlock: 528 unlock_page(page); 529 goto out_put; 530 } 531 532 /* 533 * nilfs_delete_entry deletes a directory entry by merging it with the 534 * previous entry. Page is up-to-date. Releases the page. 535 */ 536 int nilfs_delete_entry(struct nilfs_dir_entry *dir, struct page *page) 537 { 538 struct address_space *mapping = page->mapping; 539 struct inode *inode = mapping->host; 540 char *kaddr = page_address(page); 541 unsigned int from, to; 542 struct nilfs_dir_entry *de, *pde = NULL; 543 int err; 544 545 from = ((char *)dir - kaddr) & ~(nilfs_chunk_size(inode) - 1); 546 to = ((char *)dir - kaddr) + nilfs_rec_len_from_disk(dir->rec_len); 547 de = (struct nilfs_dir_entry *)(kaddr + from); 548 549 while ((char *)de < (char *)dir) { 550 if (de->rec_len == 0) { 551 nilfs_error(inode->i_sb, 552 "zero-length directory entry"); 553 err = -EIO; 554 goto out; 555 } 556 pde = de; 557 de = nilfs_next_entry(de); 558 } 559 if (pde) 560 from = (char *)pde - (char *)page_address(page); 561 lock_page(page); 562 err = nilfs_prepare_chunk(page, from, to); 563 BUG_ON(err); 564 if (pde) 565 pde->rec_len = nilfs_rec_len_to_disk(to - from); 566 dir->inode = 0; 567 nilfs_commit_chunk(page, mapping, from, to); 568 inode->i_mtime = inode_set_ctime_current(inode); 569 out: 570 nilfs_put_page(page); 571 return err; 572 } 573 574 /* 575 * Set the first fragment of directory. 576 */ 577 int nilfs_make_empty(struct inode *inode, struct inode *parent) 578 { 579 struct address_space *mapping = inode->i_mapping; 580 struct page *page = grab_cache_page(mapping, 0); 581 unsigned int chunk_size = nilfs_chunk_size(inode); 582 struct nilfs_dir_entry *de; 583 int err; 584 void *kaddr; 585 586 if (!page) 587 return -ENOMEM; 588 589 err = nilfs_prepare_chunk(page, 0, chunk_size); 590 if (unlikely(err)) { 591 unlock_page(page); 592 goto fail; 593 } 594 kaddr = kmap_atomic(page); 595 memset(kaddr, 0, chunk_size); 596 de = (struct nilfs_dir_entry *)kaddr; 597 de->name_len = 1; 598 de->rec_len = nilfs_rec_len_to_disk(NILFS_DIR_REC_LEN(1)); 599 memcpy(de->name, ".\0\0", 4); 600 de->inode = cpu_to_le64(inode->i_ino); 601 nilfs_set_de_type(de, inode); 602 603 de = (struct nilfs_dir_entry *)(kaddr + NILFS_DIR_REC_LEN(1)); 604 de->name_len = 2; 605 de->rec_len = nilfs_rec_len_to_disk(chunk_size - NILFS_DIR_REC_LEN(1)); 606 de->inode = cpu_to_le64(parent->i_ino); 607 memcpy(de->name, "..\0", 4); 608 nilfs_set_de_type(de, inode); 609 kunmap_atomic(kaddr); 610 nilfs_commit_chunk(page, mapping, 0, chunk_size); 611 fail: 612 put_page(page); 613 return err; 614 } 615 616 /* 617 * routine to check that the specified directory is empty (for rmdir) 618 */ 619 int nilfs_empty_dir(struct inode *inode) 620 { 621 struct page *page = NULL; 622 unsigned long i, npages = dir_pages(inode); 623 624 for (i = 0; i < npages; i++) { 625 char *kaddr; 626 struct nilfs_dir_entry *de; 627 628 kaddr = nilfs_get_page(inode, i, &page); 629 if (IS_ERR(kaddr)) 630 return 0; 631 632 de = (struct nilfs_dir_entry *)kaddr; 633 kaddr += nilfs_last_byte(inode, i) - NILFS_DIR_REC_LEN(1); 634 635 while ((char *)de <= kaddr) { 636 if (de->rec_len == 0) { 637 nilfs_error(inode->i_sb, 638 "zero-length directory entry (kaddr=%p, de=%p)", 639 kaddr, de); 640 goto not_empty; 641 } 642 if (de->inode != 0) { 643 /* check for . and .. */ 644 if (de->name[0] != '.') 645 goto not_empty; 646 if (de->name_len > 2) 647 goto not_empty; 648 if (de->name_len < 2) { 649 if (de->inode != 650 cpu_to_le64(inode->i_ino)) 651 goto not_empty; 652 } else if (de->name[1] != '.') 653 goto not_empty; 654 } 655 de = nilfs_next_entry(de); 656 } 657 nilfs_put_page(page); 658 } 659 return 1; 660 661 not_empty: 662 nilfs_put_page(page); 663 return 0; 664 } 665 666 const struct file_operations nilfs_dir_operations = { 667 .llseek = generic_file_llseek, 668 .read = generic_read_dir, 669 .iterate_shared = nilfs_readdir, 670 .unlocked_ioctl = nilfs_ioctl, 671 #ifdef CONFIG_COMPAT 672 .compat_ioctl = nilfs_compat_ioctl, 673 #endif /* CONFIG_COMPAT */ 674 .fsync = nilfs_sync_file, 675 676 }; 677