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