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