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