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