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 u64 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, 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, from, to); 99 copied = block_write_end(NULL, mapping, pos, len, len, folio, 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 int nilfs_readdir(struct file *file, struct dir_context *ctx) 235 { 236 loff_t pos = ctx->pos; 237 struct inode *inode = file_inode(file); 238 struct super_block *sb = inode->i_sb; 239 unsigned int offset = pos & ~PAGE_MASK; 240 unsigned long n = pos >> PAGE_SHIFT; 241 unsigned long npages = dir_pages(inode); 242 243 if (pos > inode->i_size - NILFS_DIR_REC_LEN(1)) 244 return 0; 245 246 for ( ; n < npages; n++, offset = 0) { 247 char *kaddr, *limit; 248 struct nilfs_dir_entry *de; 249 struct folio *folio; 250 251 kaddr = nilfs_get_folio(inode, n, &folio); 252 if (IS_ERR(kaddr)) { 253 nilfs_error(sb, "bad page in #%lu", inode->i_ino); 254 ctx->pos += PAGE_SIZE - offset; 255 return -EIO; 256 } 257 de = (struct nilfs_dir_entry *)(kaddr + offset); 258 limit = kaddr + nilfs_last_byte(inode, n) - 259 NILFS_DIR_REC_LEN(1); 260 for ( ; (char *)de <= limit; de = nilfs_next_entry(de)) { 261 if (de->rec_len == 0) { 262 nilfs_error(sb, "zero-length directory entry"); 263 folio_release_kmap(folio, kaddr); 264 return -EIO; 265 } 266 if (de->inode) { 267 unsigned char t; 268 269 t = fs_ftype_to_dtype(de->file_type); 270 271 if (!dir_emit(ctx, de->name, de->name_len, 272 le64_to_cpu(de->inode), t)) { 273 folio_release_kmap(folio, kaddr); 274 return 0; 275 } 276 } 277 ctx->pos += nilfs_rec_len_from_disk(de->rec_len); 278 } 279 folio_release_kmap(folio, kaddr); 280 } 281 return 0; 282 } 283 284 /* 285 * nilfs_find_entry() 286 * 287 * Finds an entry in the specified directory with the wanted name. It 288 * returns the folio in which the entry was found, and the entry itself. 289 * The folio is mapped and unlocked. When the caller is finished with 290 * the entry, it should call folio_release_kmap(). 291 * 292 * On failure, returns an error pointer and the caller should ignore foliop. 293 */ 294 struct nilfs_dir_entry *nilfs_find_entry(struct inode *dir, 295 const struct qstr *qstr, struct folio **foliop) 296 { 297 const unsigned char *name = qstr->name; 298 int namelen = qstr->len; 299 unsigned int reclen = NILFS_DIR_REC_LEN(namelen); 300 unsigned long start, n; 301 unsigned long npages = dir_pages(dir); 302 struct nilfs_inode_info *ei = NILFS_I(dir); 303 struct nilfs_dir_entry *de; 304 305 if (npages == 0) 306 goto out; 307 308 start = ei->i_dir_start_lookup; 309 if (start >= npages) 310 start = 0; 311 n = start; 312 do { 313 char *kaddr = nilfs_get_folio(dir, n, foliop); 314 315 if (IS_ERR(kaddr)) 316 return ERR_CAST(kaddr); 317 318 de = (struct nilfs_dir_entry *)kaddr; 319 kaddr += nilfs_last_byte(dir, n) - reclen; 320 while ((char *)de <= kaddr) { 321 if (de->rec_len == 0) { 322 nilfs_error(dir->i_sb, 323 "zero-length directory entry"); 324 folio_release_kmap(*foliop, kaddr); 325 goto out; 326 } 327 if (nilfs_match(namelen, name, de)) 328 goto found; 329 de = nilfs_next_entry(de); 330 } 331 folio_release_kmap(*foliop, kaddr); 332 333 if (++n >= npages) 334 n = 0; 335 /* next folio is past the blocks we've got */ 336 if (unlikely(n > (dir->i_blocks >> (PAGE_SHIFT - 9)))) { 337 nilfs_error(dir->i_sb, 338 "dir %lu size %lld exceeds block count %llu", 339 dir->i_ino, dir->i_size, 340 (unsigned long long)dir->i_blocks); 341 goto out; 342 } 343 } while (n != start); 344 out: 345 return ERR_PTR(-ENOENT); 346 347 found: 348 ei->i_dir_start_lookup = n; 349 return de; 350 } 351 352 struct nilfs_dir_entry *nilfs_dotdot(struct inode *dir, struct folio **foliop) 353 { 354 struct folio *folio; 355 struct nilfs_dir_entry *de, *next_de; 356 size_t limit; 357 char *msg; 358 359 de = nilfs_get_folio(dir, 0, &folio); 360 if (IS_ERR(de)) 361 return NULL; 362 363 limit = nilfs_last_byte(dir, 0); /* is a multiple of chunk size */ 364 if (unlikely(!limit || le64_to_cpu(de->inode) != dir->i_ino || 365 !nilfs_match(1, ".", de))) { 366 msg = "missing '.'"; 367 goto fail; 368 } 369 370 next_de = nilfs_next_entry(de); 371 /* 372 * If "next_de" has not reached the end of the chunk, there is 373 * at least one more record. Check whether it matches "..". 374 */ 375 if (unlikely((char *)next_de == (char *)de + nilfs_chunk_size(dir) || 376 !nilfs_match(2, "..", next_de))) { 377 msg = "missing '..'"; 378 goto fail; 379 } 380 *foliop = folio; 381 return next_de; 382 383 fail: 384 nilfs_error(dir->i_sb, "directory #%lu %s", dir->i_ino, msg); 385 folio_release_kmap(folio, de); 386 return NULL; 387 } 388 389 int nilfs_inode_by_name(struct inode *dir, const struct qstr *qstr, ino_t *ino) 390 { 391 struct nilfs_dir_entry *de; 392 struct folio *folio; 393 394 de = nilfs_find_entry(dir, qstr, &folio); 395 if (IS_ERR(de)) 396 return PTR_ERR(de); 397 398 *ino = le64_to_cpu(de->inode); 399 folio_release_kmap(folio, de); 400 return 0; 401 } 402 403 int nilfs_set_link(struct inode *dir, struct nilfs_dir_entry *de, 404 struct folio *folio, struct inode *inode) 405 { 406 size_t from = offset_in_folio(folio, de); 407 size_t to = from + nilfs_rec_len_from_disk(de->rec_len); 408 struct address_space *mapping = folio->mapping; 409 int err; 410 411 folio_lock(folio); 412 err = nilfs_prepare_chunk(folio, from, to); 413 if (unlikely(err)) { 414 folio_unlock(folio); 415 return err; 416 } 417 de->inode = cpu_to_le64(inode->i_ino); 418 de->file_type = fs_umode_to_ftype(inode->i_mode); 419 nilfs_commit_chunk(folio, mapping, from, to); 420 inode_set_mtime_to_ts(dir, inode_set_ctime_current(dir)); 421 return 0; 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 de->file_type = fs_umode_to_ftype(inode->i_mode); 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 if (unlikely(err)) { 551 folio_unlock(folio); 552 goto out; 553 } 554 if (pde) 555 pde->rec_len = nilfs_rec_len_to_disk(to - from); 556 dir->inode = 0; 557 nilfs_commit_chunk(folio, mapping, from, to); 558 inode_set_mtime_to_ts(inode, inode_set_ctime_current(inode)); 559 out: 560 return err; 561 } 562 563 /* 564 * Set the first fragment of directory. 565 */ 566 int nilfs_make_empty(struct inode *inode, struct inode *parent) 567 { 568 struct address_space *mapping = inode->i_mapping; 569 struct folio *folio = filemap_grab_folio(mapping, 0); 570 unsigned int chunk_size = nilfs_chunk_size(inode); 571 struct nilfs_dir_entry *de; 572 int err; 573 void *kaddr; 574 575 if (IS_ERR(folio)) 576 return PTR_ERR(folio); 577 578 err = nilfs_prepare_chunk(folio, 0, chunk_size); 579 if (unlikely(err)) { 580 folio_unlock(folio); 581 goto fail; 582 } 583 kaddr = kmap_local_folio(folio, 0); 584 memset(kaddr, 0, chunk_size); 585 de = (struct nilfs_dir_entry *)kaddr; 586 de->name_len = 1; 587 de->rec_len = nilfs_rec_len_to_disk(NILFS_DIR_REC_LEN(1)); 588 memcpy(de->name, ".\0\0", 4); 589 de->inode = cpu_to_le64(inode->i_ino); 590 de->file_type = fs_umode_to_ftype(inode->i_mode); 591 592 de = (struct nilfs_dir_entry *)(kaddr + NILFS_DIR_REC_LEN(1)); 593 de->name_len = 2; 594 de->rec_len = nilfs_rec_len_to_disk(chunk_size - NILFS_DIR_REC_LEN(1)); 595 de->inode = cpu_to_le64(parent->i_ino); 596 memcpy(de->name, "..\0", 4); 597 de->file_type = fs_umode_to_ftype(inode->i_mode); 598 kunmap_local(kaddr); 599 nilfs_commit_chunk(folio, mapping, 0, chunk_size); 600 fail: 601 folio_put(folio); 602 return err; 603 } 604 605 /* 606 * routine to check that the specified directory is empty (for rmdir) 607 */ 608 int nilfs_empty_dir(struct inode *inode) 609 { 610 struct folio *folio = NULL; 611 char *kaddr; 612 unsigned long i, npages = dir_pages(inode); 613 614 for (i = 0; i < npages; i++) { 615 struct nilfs_dir_entry *de; 616 617 kaddr = nilfs_get_folio(inode, i, &folio); 618 if (IS_ERR(kaddr)) 619 return 0; 620 621 de = (struct nilfs_dir_entry *)kaddr; 622 kaddr += nilfs_last_byte(inode, i) - NILFS_DIR_REC_LEN(1); 623 624 while ((char *)de <= kaddr) { 625 if (de->rec_len == 0) { 626 nilfs_error(inode->i_sb, 627 "zero-length directory entry (kaddr=%p, de=%p)", 628 kaddr, de); 629 goto not_empty; 630 } 631 if (de->inode != 0) { 632 /* check for . and .. */ 633 if (de->name[0] != '.') 634 goto not_empty; 635 if (de->name_len > 2) 636 goto not_empty; 637 if (de->name_len < 2) { 638 if (de->inode != 639 cpu_to_le64(inode->i_ino)) 640 goto not_empty; 641 } else if (de->name[1] != '.') 642 goto not_empty; 643 } 644 de = nilfs_next_entry(de); 645 } 646 folio_release_kmap(folio, kaddr); 647 } 648 return 1; 649 650 not_empty: 651 folio_release_kmap(folio, kaddr); 652 return 0; 653 } 654 655 const struct file_operations nilfs_dir_operations = { 656 .llseek = generic_file_llseek, 657 .read = generic_read_dir, 658 .iterate_shared = nilfs_readdir, 659 .unlocked_ioctl = nilfs_ioctl, 660 #ifdef CONFIG_COMPAT 661 .compat_ioctl = nilfs_compat_ioctl, 662 #endif /* CONFIG_COMPAT */ 663 .fsync = nilfs_sync_file, 664 665 }; 666