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