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 if (unlikely(p->inode && 147 NILFS_PRIVATE_INODE(le64_to_cpu(p->inode)))) 148 goto Einumber; 149 } 150 if (offs != limit) 151 goto Eend; 152 out: 153 SetPageChecked(page); 154 return true; 155 156 /* Too bad, we had an error */ 157 158 Ebadsize: 159 nilfs_error(sb, 160 "size of directory #%lu is not a multiple of chunk size", 161 dir->i_ino); 162 goto fail; 163 Eshort: 164 error = "rec_len is smaller than minimal"; 165 goto bad_entry; 166 Ealign: 167 error = "unaligned directory entry"; 168 goto bad_entry; 169 Enamelen: 170 error = "rec_len is too small for name_len"; 171 goto bad_entry; 172 Espan: 173 error = "directory entry across blocks"; 174 goto bad_entry; 175 Einumber: 176 error = "disallowed inode number"; 177 bad_entry: 178 nilfs_error(sb, 179 "bad entry in directory #%lu: %s - offset=%lu, inode=%lu, rec_len=%d, name_len=%d", 180 dir->i_ino, error, (page->index << PAGE_SHIFT) + offs, 181 (unsigned long)le64_to_cpu(p->inode), 182 rec_len, p->name_len); 183 goto fail; 184 Eend: 185 p = (struct nilfs_dir_entry *)(kaddr + offs); 186 nilfs_error(sb, 187 "entry in directory #%lu spans the page boundary offset=%lu, inode=%lu", 188 dir->i_ino, (page->index << PAGE_SHIFT) + offs, 189 (unsigned long)le64_to_cpu(p->inode)); 190 fail: 191 SetPageError(page); 192 return false; 193 } 194 195 static void *nilfs_get_page(struct inode *dir, unsigned long n, 196 struct page **pagep) 197 { 198 struct address_space *mapping = dir->i_mapping; 199 struct page *page = read_mapping_page(mapping, n, NULL); 200 void *kaddr; 201 202 if (IS_ERR(page)) 203 return page; 204 205 kaddr = kmap(page); 206 if (unlikely(!PageChecked(page))) { 207 if (!nilfs_check_page(page)) 208 goto fail; 209 } 210 211 *pagep = page; 212 return kaddr; 213 214 fail: 215 nilfs_put_page(page); 216 return ERR_PTR(-EIO); 217 } 218 219 /* 220 * NOTE! unlike strncmp, nilfs_match returns 1 for success, 0 for failure. 221 * 222 * len <= NILFS_NAME_LEN and de != NULL are guaranteed by caller. 223 */ 224 static int 225 nilfs_match(int len, const unsigned char *name, struct nilfs_dir_entry *de) 226 { 227 if (len != de->name_len) 228 return 0; 229 if (!de->inode) 230 return 0; 231 return !memcmp(name, de->name, len); 232 } 233 234 /* 235 * p is at least 6 bytes before the end of page 236 */ 237 static struct nilfs_dir_entry *nilfs_next_entry(struct nilfs_dir_entry *p) 238 { 239 return (struct nilfs_dir_entry *)((char *)p + 240 nilfs_rec_len_from_disk(p->rec_len)); 241 } 242 243 static unsigned char 244 nilfs_filetype_table[NILFS_FT_MAX] = { 245 [NILFS_FT_UNKNOWN] = DT_UNKNOWN, 246 [NILFS_FT_REG_FILE] = DT_REG, 247 [NILFS_FT_DIR] = DT_DIR, 248 [NILFS_FT_CHRDEV] = DT_CHR, 249 [NILFS_FT_BLKDEV] = DT_BLK, 250 [NILFS_FT_FIFO] = DT_FIFO, 251 [NILFS_FT_SOCK] = DT_SOCK, 252 [NILFS_FT_SYMLINK] = DT_LNK, 253 }; 254 255 #define S_SHIFT 12 256 static unsigned char 257 nilfs_type_by_mode[(S_IFMT >> S_SHIFT) + 1] = { 258 [S_IFREG >> S_SHIFT] = NILFS_FT_REG_FILE, 259 [S_IFDIR >> S_SHIFT] = NILFS_FT_DIR, 260 [S_IFCHR >> S_SHIFT] = NILFS_FT_CHRDEV, 261 [S_IFBLK >> S_SHIFT] = NILFS_FT_BLKDEV, 262 [S_IFIFO >> S_SHIFT] = NILFS_FT_FIFO, 263 [S_IFSOCK >> S_SHIFT] = NILFS_FT_SOCK, 264 [S_IFLNK >> S_SHIFT] = NILFS_FT_SYMLINK, 265 }; 266 267 static void nilfs_set_de_type(struct nilfs_dir_entry *de, struct inode *inode) 268 { 269 umode_t mode = inode->i_mode; 270 271 de->file_type = nilfs_type_by_mode[(mode & S_IFMT)>>S_SHIFT]; 272 } 273 274 static int nilfs_readdir(struct file *file, struct dir_context *ctx) 275 { 276 loff_t pos = ctx->pos; 277 struct inode *inode = file_inode(file); 278 struct super_block *sb = inode->i_sb; 279 unsigned int offset = pos & ~PAGE_MASK; 280 unsigned long n = pos >> PAGE_SHIFT; 281 unsigned long npages = dir_pages(inode); 282 283 if (pos > inode->i_size - NILFS_DIR_REC_LEN(1)) 284 return 0; 285 286 for ( ; n < npages; n++, offset = 0) { 287 char *kaddr, *limit; 288 struct nilfs_dir_entry *de; 289 struct page *page; 290 291 kaddr = nilfs_get_page(inode, n, &page); 292 if (IS_ERR(kaddr)) { 293 nilfs_error(sb, "bad page in #%lu", inode->i_ino); 294 ctx->pos += PAGE_SIZE - offset; 295 return -EIO; 296 } 297 de = (struct nilfs_dir_entry *)(kaddr + offset); 298 limit = kaddr + nilfs_last_byte(inode, n) - 299 NILFS_DIR_REC_LEN(1); 300 for ( ; (char *)de <= limit; de = nilfs_next_entry(de)) { 301 if (de->rec_len == 0) { 302 nilfs_error(sb, "zero-length directory entry"); 303 nilfs_put_page(page); 304 return -EIO; 305 } 306 if (de->inode) { 307 unsigned char t; 308 309 if (de->file_type < NILFS_FT_MAX) 310 t = nilfs_filetype_table[de->file_type]; 311 else 312 t = DT_UNKNOWN; 313 314 if (!dir_emit(ctx, de->name, de->name_len, 315 le64_to_cpu(de->inode), t)) { 316 nilfs_put_page(page); 317 return 0; 318 } 319 } 320 ctx->pos += nilfs_rec_len_from_disk(de->rec_len); 321 } 322 nilfs_put_page(page); 323 } 324 return 0; 325 } 326 327 /* 328 * nilfs_find_entry() 329 * 330 * finds an entry in the specified directory with the wanted name. It 331 * returns the page in which the entry was found, and the entry itself 332 * (as a parameter - res_dir). Page is returned mapped and unlocked. 333 * Entry is guaranteed to be valid. 334 */ 335 struct nilfs_dir_entry * 336 nilfs_find_entry(struct inode *dir, const struct qstr *qstr, 337 struct page **res_page) 338 { 339 const unsigned char *name = qstr->name; 340 int namelen = qstr->len; 341 unsigned int reclen = NILFS_DIR_REC_LEN(namelen); 342 unsigned long start, n; 343 unsigned long npages = dir_pages(dir); 344 struct page *page = NULL; 345 struct nilfs_inode_info *ei = NILFS_I(dir); 346 struct nilfs_dir_entry *de; 347 348 if (npages == 0) 349 goto out; 350 351 /* OFFSET_CACHE */ 352 *res_page = NULL; 353 354 start = ei->i_dir_start_lookup; 355 if (start >= npages) 356 start = 0; 357 n = start; 358 do { 359 char *kaddr = nilfs_get_page(dir, n, &page); 360 361 if (!IS_ERR(kaddr)) { 362 de = (struct nilfs_dir_entry *)kaddr; 363 kaddr += nilfs_last_byte(dir, n) - reclen; 364 while ((char *) de <= kaddr) { 365 if (de->rec_len == 0) { 366 nilfs_error(dir->i_sb, 367 "zero-length directory entry"); 368 nilfs_put_page(page); 369 goto out; 370 } 371 if (nilfs_match(namelen, name, de)) 372 goto found; 373 de = nilfs_next_entry(de); 374 } 375 nilfs_put_page(page); 376 } 377 if (++n >= npages) 378 n = 0; 379 /* next page is past the blocks we've got */ 380 if (unlikely(n > (dir->i_blocks >> (PAGE_SHIFT - 9)))) { 381 nilfs_error(dir->i_sb, 382 "dir %lu size %lld exceeds block count %llu", 383 dir->i_ino, dir->i_size, 384 (unsigned long long)dir->i_blocks); 385 goto out; 386 } 387 } while (n != start); 388 out: 389 return NULL; 390 391 found: 392 *res_page = page; 393 ei->i_dir_start_lookup = n; 394 return de; 395 } 396 397 struct nilfs_dir_entry *nilfs_dotdot(struct inode *dir, struct page **p) 398 { 399 struct nilfs_dir_entry *de = nilfs_get_page(dir, 0, p); 400 401 if (IS_ERR(de)) 402 return NULL; 403 return nilfs_next_entry(de); 404 } 405 406 ino_t nilfs_inode_by_name(struct inode *dir, const struct qstr *qstr) 407 { 408 ino_t res = 0; 409 struct nilfs_dir_entry *de; 410 struct page *page; 411 412 de = nilfs_find_entry(dir, qstr, &page); 413 if (de) { 414 res = le64_to_cpu(de->inode); 415 kunmap(page); 416 put_page(page); 417 } 418 return res; 419 } 420 421 /* Releases the page */ 422 void nilfs_set_link(struct inode *dir, struct nilfs_dir_entry *de, 423 struct page *page, struct inode *inode) 424 { 425 unsigned int from = (char *)de - (char *)page_address(page); 426 unsigned int to = from + nilfs_rec_len_from_disk(de->rec_len); 427 struct address_space *mapping = page->mapping; 428 int err; 429 430 lock_page(page); 431 err = nilfs_prepare_chunk(page, from, to); 432 BUG_ON(err); 433 de->inode = cpu_to_le64(inode->i_ino); 434 nilfs_set_de_type(de, inode); 435 nilfs_commit_chunk(page, mapping, from, to); 436 nilfs_put_page(page); 437 dir->i_mtime = inode_set_ctime_current(dir); 438 } 439 440 /* 441 * Parent is locked. 442 */ 443 int nilfs_add_link(struct dentry *dentry, struct inode *inode) 444 { 445 struct inode *dir = d_inode(dentry->d_parent); 446 const unsigned char *name = dentry->d_name.name; 447 int namelen = dentry->d_name.len; 448 unsigned int chunk_size = nilfs_chunk_size(dir); 449 unsigned int reclen = NILFS_DIR_REC_LEN(namelen); 450 unsigned short rec_len, name_len; 451 struct page *page = NULL; 452 struct nilfs_dir_entry *de; 453 unsigned long npages = dir_pages(dir); 454 unsigned long n; 455 char *kaddr; 456 unsigned int from, to; 457 int err; 458 459 /* 460 * We take care of directory expansion in the same loop. 461 * This code plays outside i_size, so it locks the page 462 * to protect that region. 463 */ 464 for (n = 0; n <= npages; n++) { 465 char *dir_end; 466 467 kaddr = nilfs_get_page(dir, n, &page); 468 err = PTR_ERR(kaddr); 469 if (IS_ERR(kaddr)) 470 goto out; 471 lock_page(page); 472 dir_end = kaddr + nilfs_last_byte(dir, n); 473 de = (struct nilfs_dir_entry *)kaddr; 474 kaddr += PAGE_SIZE - reclen; 475 while ((char *)de <= kaddr) { 476 if ((char *)de == dir_end) { 477 /* We hit i_size */ 478 name_len = 0; 479 rec_len = chunk_size; 480 de->rec_len = nilfs_rec_len_to_disk(chunk_size); 481 de->inode = 0; 482 goto got_it; 483 } 484 if (de->rec_len == 0) { 485 nilfs_error(dir->i_sb, 486 "zero-length directory entry"); 487 err = -EIO; 488 goto out_unlock; 489 } 490 err = -EEXIST; 491 if (nilfs_match(namelen, name, de)) 492 goto out_unlock; 493 name_len = NILFS_DIR_REC_LEN(de->name_len); 494 rec_len = nilfs_rec_len_from_disk(de->rec_len); 495 if (!de->inode && rec_len >= reclen) 496 goto got_it; 497 if (rec_len >= name_len + reclen) 498 goto got_it; 499 de = (struct nilfs_dir_entry *)((char *)de + rec_len); 500 } 501 unlock_page(page); 502 nilfs_put_page(page); 503 } 504 BUG(); 505 return -EINVAL; 506 507 got_it: 508 from = (char *)de - (char *)page_address(page); 509 to = from + rec_len; 510 err = nilfs_prepare_chunk(page, from, to); 511 if (err) 512 goto out_unlock; 513 if (de->inode) { 514 struct nilfs_dir_entry *de1; 515 516 de1 = (struct nilfs_dir_entry *)((char *)de + name_len); 517 de1->rec_len = nilfs_rec_len_to_disk(rec_len - name_len); 518 de->rec_len = nilfs_rec_len_to_disk(name_len); 519 de = de1; 520 } 521 de->name_len = namelen; 522 memcpy(de->name, name, namelen); 523 de->inode = cpu_to_le64(inode->i_ino); 524 nilfs_set_de_type(de, inode); 525 nilfs_commit_chunk(page, page->mapping, from, to); 526 dir->i_mtime = inode_set_ctime_current(dir); 527 nilfs_mark_inode_dirty(dir); 528 /* OFFSET_CACHE */ 529 out_put: 530 nilfs_put_page(page); 531 out: 532 return err; 533 out_unlock: 534 unlock_page(page); 535 goto out_put; 536 } 537 538 /* 539 * nilfs_delete_entry deletes a directory entry by merging it with the 540 * previous entry. Page is up-to-date. Releases the page. 541 */ 542 int nilfs_delete_entry(struct nilfs_dir_entry *dir, struct page *page) 543 { 544 struct address_space *mapping = page->mapping; 545 struct inode *inode = mapping->host; 546 char *kaddr = page_address(page); 547 unsigned int from, to; 548 struct nilfs_dir_entry *de, *pde = NULL; 549 int err; 550 551 from = ((char *)dir - kaddr) & ~(nilfs_chunk_size(inode) - 1); 552 to = ((char *)dir - kaddr) + nilfs_rec_len_from_disk(dir->rec_len); 553 de = (struct nilfs_dir_entry *)(kaddr + from); 554 555 while ((char *)de < (char *)dir) { 556 if (de->rec_len == 0) { 557 nilfs_error(inode->i_sb, 558 "zero-length directory entry"); 559 err = -EIO; 560 goto out; 561 } 562 pde = de; 563 de = nilfs_next_entry(de); 564 } 565 if (pde) 566 from = (char *)pde - (char *)page_address(page); 567 lock_page(page); 568 err = nilfs_prepare_chunk(page, from, to); 569 BUG_ON(err); 570 if (pde) 571 pde->rec_len = nilfs_rec_len_to_disk(to - from); 572 dir->inode = 0; 573 nilfs_commit_chunk(page, mapping, from, to); 574 inode->i_mtime = inode_set_ctime_current(inode); 575 out: 576 nilfs_put_page(page); 577 return err; 578 } 579 580 /* 581 * Set the first fragment of directory. 582 */ 583 int nilfs_make_empty(struct inode *inode, struct inode *parent) 584 { 585 struct address_space *mapping = inode->i_mapping; 586 struct page *page = grab_cache_page(mapping, 0); 587 unsigned int chunk_size = nilfs_chunk_size(inode); 588 struct nilfs_dir_entry *de; 589 int err; 590 void *kaddr; 591 592 if (!page) 593 return -ENOMEM; 594 595 err = nilfs_prepare_chunk(page, 0, chunk_size); 596 if (unlikely(err)) { 597 unlock_page(page); 598 goto fail; 599 } 600 kaddr = kmap_atomic(page); 601 memset(kaddr, 0, chunk_size); 602 de = (struct nilfs_dir_entry *)kaddr; 603 de->name_len = 1; 604 de->rec_len = nilfs_rec_len_to_disk(NILFS_DIR_REC_LEN(1)); 605 memcpy(de->name, ".\0\0", 4); 606 de->inode = cpu_to_le64(inode->i_ino); 607 nilfs_set_de_type(de, inode); 608 609 de = (struct nilfs_dir_entry *)(kaddr + NILFS_DIR_REC_LEN(1)); 610 de->name_len = 2; 611 de->rec_len = nilfs_rec_len_to_disk(chunk_size - NILFS_DIR_REC_LEN(1)); 612 de->inode = cpu_to_le64(parent->i_ino); 613 memcpy(de->name, "..\0", 4); 614 nilfs_set_de_type(de, inode); 615 kunmap_atomic(kaddr); 616 nilfs_commit_chunk(page, mapping, 0, chunk_size); 617 fail: 618 put_page(page); 619 return err; 620 } 621 622 /* 623 * routine to check that the specified directory is empty (for rmdir) 624 */ 625 int nilfs_empty_dir(struct inode *inode) 626 { 627 struct page *page = NULL; 628 unsigned long i, npages = dir_pages(inode); 629 630 for (i = 0; i < npages; i++) { 631 char *kaddr; 632 struct nilfs_dir_entry *de; 633 634 kaddr = nilfs_get_page(inode, i, &page); 635 if (IS_ERR(kaddr)) 636 return 0; 637 638 de = (struct nilfs_dir_entry *)kaddr; 639 kaddr += nilfs_last_byte(inode, i) - NILFS_DIR_REC_LEN(1); 640 641 while ((char *)de <= kaddr) { 642 if (de->rec_len == 0) { 643 nilfs_error(inode->i_sb, 644 "zero-length directory entry (kaddr=%p, de=%p)", 645 kaddr, de); 646 goto not_empty; 647 } 648 if (de->inode != 0) { 649 /* check for . and .. */ 650 if (de->name[0] != '.') 651 goto not_empty; 652 if (de->name_len > 2) 653 goto not_empty; 654 if (de->name_len < 2) { 655 if (de->inode != 656 cpu_to_le64(inode->i_ino)) 657 goto not_empty; 658 } else if (de->name[1] != '.') 659 goto not_empty; 660 } 661 de = nilfs_next_entry(de); 662 } 663 nilfs_put_page(page); 664 } 665 return 1; 666 667 not_empty: 668 nilfs_put_page(page); 669 return 0; 670 } 671 672 const struct file_operations nilfs_dir_operations = { 673 .llseek = generic_file_llseek, 674 .read = generic_read_dir, 675 .iterate_shared = nilfs_readdir, 676 .unlocked_ioctl = nilfs_ioctl, 677 #ifdef CONFIG_COMPAT 678 .compat_ioctl = nilfs_compat_ioctl, 679 #endif /* CONFIG_COMPAT */ 680 .fsync = nilfs_sync_file, 681 682 }; 683