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 31typedef 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 */ 38static 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 49static 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 */ 64static inline unsigned ext2_chunk_size(struct inode *inode) 65{ 66 return inode->i_sb->s_blocksize; 67} 68 69static 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 */ 79static unsigned 80ext2_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 90static 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 115static 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; 151out: 152 SetPageChecked(page); 153 return true; 154 155 /* Too bad, we had an error */ 156 157Ebadsize: 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; 163Eshort: 164 error = "rec_len is smaller than minimal"; 165 goto bad_entry; 166Ealign: 167 error = "unaligned directory entry"; 168 goto bad_entry; 169Enamelen: 170 error = "rec_len is too small for name_len"; 171 goto bad_entry; 172Espan: 173 error = "directory entry across blocks"; 174 goto bad_entry; 175Einumber: 176 error = "inode out of bounds"; 177bad_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; 185Eend: 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 } 194fail: 195 SetPageError(page); 196 return false; 197} 198 199static 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 213fail: 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 */ 223static 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 */ 236static 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 242static inline unsigned 243ext2_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 255static 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 263static int 264ext2_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 */ 340struct 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 352 if (npages == 0) 353 goto out; 354 355 /* OFFSET_CACHE */ 356 *res_page = NULL; 357 358 start = ei->i_dir_start_lookup; 359 if (start >= npages) 360 start = 0; 361 n = start; 362 do { 363 char *kaddr; 364 page = ext2_get_page(dir, n, 0); 365 if (IS_ERR(page)) 366 return ERR_CAST(page); 367 368 kaddr = page_address(page); 369 de = (ext2_dirent *) kaddr; 370 kaddr += ext2_last_byte(dir, n) - reclen; 371 while ((char *) de <= kaddr) { 372 if (de->rec_len == 0) { 373 ext2_error(dir->i_sb, __func__, 374 "zero-length directory entry"); 375 ext2_put_page(page); 376 goto out; 377 } 378 if (ext2_match(namelen, name, de)) 379 goto found; 380 de = ext2_next_entry(de); 381 } 382 ext2_put_page(page); 383 384 if (++n >= npages) 385 n = 0; 386 /* next page is past the blocks we've got */ 387 if (unlikely(n > (dir->i_blocks >> (PAGE_SHIFT - 9)))) { 388 ext2_error(dir->i_sb, __func__, 389 "dir %lu size %lld exceeds block count %llu", 390 dir->i_ino, dir->i_size, 391 (unsigned long long)dir->i_blocks); 392 goto out; 393 } 394 } while (n != start); 395out: 396 return ERR_PTR(-ENOENT); 397 398found: 399 *res_page = page; 400 ei->i_dir_start_lookup = n; 401 return de; 402} 403 404struct ext2_dir_entry_2 * ext2_dotdot (struct inode *dir, struct page **p) 405{ 406 struct page *page = ext2_get_page(dir, 0, 0); 407 ext2_dirent *de = NULL; 408 409 if (!IS_ERR(page)) { 410 de = ext2_next_entry((ext2_dirent *) page_address(page)); 411 *p = page; 412 } 413 return de; 414} 415 416int ext2_inode_by_name(struct inode *dir, const struct qstr *child, ino_t *ino) 417{ 418 struct ext2_dir_entry_2 *de; 419 struct page *page; 420 421 de = ext2_find_entry(dir, child, &page); 422 if (IS_ERR(de)) 423 return PTR_ERR(de); 424 425 *ino = le32_to_cpu(de->inode); 426 ext2_put_page(page); 427 return 0; 428} 429 430static int ext2_prepare_chunk(struct page *page, loff_t pos, unsigned len) 431{ 432 return __block_write_begin(page, pos, len, ext2_get_block); 433} 434 435/* Releases the page */ 436void ext2_set_link(struct inode *dir, struct ext2_dir_entry_2 *de, 437 struct page *page, struct inode *inode, int update_times) 438{ 439 loff_t pos = page_offset(page) + 440 (char *) de - (char *) page_address(page); 441 unsigned len = ext2_rec_len_from_disk(de->rec_len); 442 int err; 443 444 lock_page(page); 445 err = ext2_prepare_chunk(page, pos, len); 446 BUG_ON(err); 447 de->inode = cpu_to_le32(inode->i_ino); 448 ext2_set_de_type(de, inode); 449 err = ext2_commit_chunk(page, pos, len); 450 ext2_put_page(page); 451 if (update_times) 452 dir->i_mtime = dir->i_ctime = current_time(dir); 453 EXT2_I(dir)->i_flags &= ~EXT2_BTREE_FL; 454 mark_inode_dirty(dir); 455} 456 457/* 458 * Parent is locked. 459 */ 460int ext2_add_link (struct dentry *dentry, struct inode *inode) 461{ 462 struct inode *dir = d_inode(dentry->d_parent); 463 const char *name = dentry->d_name.name; 464 int namelen = dentry->d_name.len; 465 unsigned chunk_size = ext2_chunk_size(dir); 466 unsigned reclen = EXT2_DIR_REC_LEN(namelen); 467 unsigned short rec_len, name_len; 468 struct page *page = NULL; 469 ext2_dirent * de; 470 unsigned long npages = dir_pages(dir); 471 unsigned long n; 472 char *kaddr; 473 loff_t pos; 474 int err; 475 476 /* 477 * We take care of directory expansion in the same loop. 478 * This code plays outside i_size, so it locks the page 479 * to protect that region. 480 */ 481 for (n = 0; n <= npages; n++) { 482 char *dir_end; 483 484 page = ext2_get_page(dir, n, 0); 485 err = PTR_ERR(page); 486 if (IS_ERR(page)) 487 goto out; 488 lock_page(page); 489 kaddr = page_address(page); 490 dir_end = kaddr + ext2_last_byte(dir, n); 491 de = (ext2_dirent *)kaddr; 492 kaddr += PAGE_SIZE - reclen; 493 while ((char *)de <= kaddr) { 494 if ((char *)de == dir_end) { 495 /* We hit i_size */ 496 name_len = 0; 497 rec_len = chunk_size; 498 de->rec_len = ext2_rec_len_to_disk(chunk_size); 499 de->inode = 0; 500 goto got_it; 501 } 502 if (de->rec_len == 0) { 503 ext2_error(dir->i_sb, __func__, 504 "zero-length directory entry"); 505 err = -EIO; 506 goto out_unlock; 507 } 508 err = -EEXIST; 509 if (ext2_match (namelen, name, de)) 510 goto out_unlock; 511 name_len = EXT2_DIR_REC_LEN(de->name_len); 512 rec_len = ext2_rec_len_from_disk(de->rec_len); 513 if (!de->inode && rec_len >= reclen) 514 goto got_it; 515 if (rec_len >= name_len + reclen) 516 goto got_it; 517 de = (ext2_dirent *) ((char *) de + rec_len); 518 } 519 unlock_page(page); 520 ext2_put_page(page); 521 } 522 BUG(); 523 return -EINVAL; 524 525got_it: 526 pos = page_offset(page) + 527 (char*)de - (char*)page_address(page); 528 err = ext2_prepare_chunk(page, pos, rec_len); 529 if (err) 530 goto out_unlock; 531 if (de->inode) { 532 ext2_dirent *de1 = (ext2_dirent *) ((char *) de + name_len); 533 de1->rec_len = ext2_rec_len_to_disk(rec_len - name_len); 534 de->rec_len = ext2_rec_len_to_disk(name_len); 535 de = de1; 536 } 537 de->name_len = namelen; 538 memcpy(de->name, name, namelen); 539 de->inode = cpu_to_le32(inode->i_ino); 540 ext2_set_de_type (de, inode); 541 err = ext2_commit_chunk(page, pos, rec_len); 542 dir->i_mtime = dir->i_ctime = current_time(dir); 543 EXT2_I(dir)->i_flags &= ~EXT2_BTREE_FL; 544 mark_inode_dirty(dir); 545 /* OFFSET_CACHE */ 546out_put: 547 ext2_put_page(page); 548out: 549 return err; 550out_unlock: 551 unlock_page(page); 552 goto out_put; 553} 554 555/* 556 * ext2_delete_entry deletes a directory entry by merging it with the 557 * previous entry. Page is up-to-date. Releases the page. 558 */ 559int ext2_delete_entry (struct ext2_dir_entry_2 * dir, struct page * page ) 560{ 561 struct inode *inode = page->mapping->host; 562 char *kaddr = page_address(page); 563 unsigned from = ((char*)dir - kaddr) & ~(ext2_chunk_size(inode)-1); 564 unsigned to = ((char *)dir - kaddr) + 565 ext2_rec_len_from_disk(dir->rec_len); 566 loff_t pos; 567 ext2_dirent * pde = NULL; 568 ext2_dirent * de = (ext2_dirent *) (kaddr + from); 569 int err; 570 571 while ((char*)de < (char*)dir) { 572 if (de->rec_len == 0) { 573 ext2_error(inode->i_sb, __func__, 574 "zero-length directory entry"); 575 err = -EIO; 576 goto out; 577 } 578 pde = de; 579 de = ext2_next_entry(de); 580 } 581 if (pde) 582 from = (char*)pde - (char*)page_address(page); 583 pos = page_offset(page) + from; 584 lock_page(page); 585 err = ext2_prepare_chunk(page, pos, to - from); 586 BUG_ON(err); 587 if (pde) 588 pde->rec_len = ext2_rec_len_to_disk(to - from); 589 dir->inode = 0; 590 err = ext2_commit_chunk(page, pos, to - from); 591 inode->i_ctime = inode->i_mtime = current_time(inode); 592 EXT2_I(inode)->i_flags &= ~EXT2_BTREE_FL; 593 mark_inode_dirty(inode); 594out: 595 ext2_put_page(page); 596 return err; 597} 598 599/* 600 * Set the first fragment of directory. 601 */ 602int ext2_make_empty(struct inode *inode, struct inode *parent) 603{ 604 struct page *page = grab_cache_page(inode->i_mapping, 0); 605 unsigned chunk_size = ext2_chunk_size(inode); 606 struct ext2_dir_entry_2 * de; 607 int err; 608 void *kaddr; 609 610 if (!page) 611 return -ENOMEM; 612 613 err = ext2_prepare_chunk(page, 0, chunk_size); 614 if (err) { 615 unlock_page(page); 616 goto fail; 617 } 618 kaddr = kmap_atomic(page); 619 memset(kaddr, 0, chunk_size); 620 de = (struct ext2_dir_entry_2 *)kaddr; 621 de->name_len = 1; 622 de->rec_len = ext2_rec_len_to_disk(EXT2_DIR_REC_LEN(1)); 623 memcpy (de->name, ".\0\0", 4); 624 de->inode = cpu_to_le32(inode->i_ino); 625 ext2_set_de_type (de, inode); 626 627 de = (struct ext2_dir_entry_2 *)(kaddr + EXT2_DIR_REC_LEN(1)); 628 de->name_len = 2; 629 de->rec_len = ext2_rec_len_to_disk(chunk_size - EXT2_DIR_REC_LEN(1)); 630 de->inode = cpu_to_le32(parent->i_ino); 631 memcpy (de->name, "..\0", 4); 632 ext2_set_de_type (de, inode); 633 kunmap_atomic(kaddr); 634 err = ext2_commit_chunk(page, 0, chunk_size); 635fail: 636 put_page(page); 637 return err; 638} 639 640/* 641 * routine to check that the specified directory is empty (for rmdir) 642 */ 643int ext2_empty_dir (struct inode * inode) 644{ 645 struct page *page = NULL; 646 unsigned long i, npages = dir_pages(inode); 647 int dir_has_error = 0; 648 649 for (i = 0; i < npages; i++) { 650 char *kaddr; 651 ext2_dirent * de; 652 page = ext2_get_page(inode, i, dir_has_error); 653 654 if (IS_ERR(page)) { 655 dir_has_error = 1; 656 continue; 657 } 658 659 kaddr = page_address(page); 660 de = (ext2_dirent *)kaddr; 661 kaddr += ext2_last_byte(inode, i) - EXT2_DIR_REC_LEN(1); 662 663 while ((char *)de <= kaddr) { 664 if (de->rec_len == 0) { 665 ext2_error(inode->i_sb, __func__, 666 "zero-length directory entry"); 667 printk("kaddr=%p, de=%p\n", kaddr, de); 668 goto not_empty; 669 } 670 if (de->inode != 0) { 671 /* check for . and .. */ 672 if (de->name[0] != '.') 673 goto not_empty; 674 if (de->name_len > 2) 675 goto not_empty; 676 if (de->name_len < 2) { 677 if (de->inode != 678 cpu_to_le32(inode->i_ino)) 679 goto not_empty; 680 } else if (de->name[1] != '.') 681 goto not_empty; 682 } 683 de = ext2_next_entry(de); 684 } 685 ext2_put_page(page); 686 } 687 return 1; 688 689not_empty: 690 ext2_put_page(page); 691 return 0; 692} 693 694const struct file_operations ext2_dir_operations = { 695 .llseek = generic_file_llseek, 696 .read = generic_read_dir, 697 .iterate_shared = ext2_readdir, 698 .unlocked_ioctl = ext2_ioctl, 699#ifdef CONFIG_COMPAT 700 .compat_ioctl = ext2_compat_ioctl, 701#endif 702 .fsync = ext2_fsync, 703}; 704