namei.c revision 81a052273998f94b098945c4c313e05246956eb2
1/* 2 * linux/fs/ext3/namei.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/namei.c 12 * 13 * Copyright (C) 1991, 1992 Linus Torvalds 14 * 15 * Big-endian to little-endian byte-swapping/bitmaps by 16 * David S. Miller (davem@caip.rutgers.edu), 1995 17 * Directory entry file type support and forward compatibility hooks 18 * for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998 19 * Hash Tree Directory indexing (c) 20 * Daniel Phillips, 2001 21 * Hash Tree Directory indexing porting 22 * Christopher Li, 2002 23 * Hash Tree Directory indexing cleanup 24 * Theodore Ts'o, 2002 25 */ 26 27#include <linux/fs.h> 28#include <linux/pagemap.h> 29#include <linux/jbd.h> 30#include <linux/time.h> 31#include <linux/ext3_fs.h> 32#include <linux/ext3_jbd.h> 33#include <linux/fcntl.h> 34#include <linux/stat.h> 35#include <linux/string.h> 36#include <linux/quotaops.h> 37#include <linux/buffer_head.h> 38#include <linux/bio.h> 39 40#include "namei.h" 41#include "xattr.h" 42#include "acl.h" 43 44/* 45 * define how far ahead to read directories while searching them. 46 */ 47#define NAMEI_RA_CHUNKS 2 48#define NAMEI_RA_BLOCKS 4 49#define NAMEI_RA_SIZE (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS) 50#define NAMEI_RA_INDEX(c,b) (((c) * NAMEI_RA_BLOCKS) + (b)) 51 52static struct buffer_head *ext3_append(handle_t *handle, 53 struct inode *inode, 54 u32 *block, int *err) 55{ 56 struct buffer_head *bh; 57 58 *block = inode->i_size >> inode->i_sb->s_blocksize_bits; 59 60 bh = ext3_bread(handle, inode, *block, 1, err); 61 if (bh) { 62 inode->i_size += inode->i_sb->s_blocksize; 63 EXT3_I(inode)->i_disksize = inode->i_size; 64 *err = ext3_journal_get_write_access(handle, bh); 65 if (*err) { 66 brelse(bh); 67 bh = NULL; 68 } 69 } 70 return bh; 71} 72 73#ifndef assert 74#define assert(test) J_ASSERT(test) 75#endif 76 77#ifdef DX_DEBUG 78#define dxtrace(command) command 79#else 80#define dxtrace(command) 81#endif 82 83struct fake_dirent 84{ 85 __le32 inode; 86 __le16 rec_len; 87 u8 name_len; 88 u8 file_type; 89}; 90 91struct dx_countlimit 92{ 93 __le16 limit; 94 __le16 count; 95}; 96 97struct dx_entry 98{ 99 __le32 hash; 100 __le32 block; 101}; 102 103/* 104 * dx_root_info is laid out so that if it should somehow get overlaid by a 105 * dirent the two low bits of the hash version will be zero. Therefore, the 106 * hash version mod 4 should never be 0. Sincerely, the paranoia department. 107 */ 108 109struct dx_root 110{ 111 struct fake_dirent dot; 112 char dot_name[4]; 113 struct fake_dirent dotdot; 114 char dotdot_name[4]; 115 struct dx_root_info 116 { 117 __le32 reserved_zero; 118 u8 hash_version; 119 u8 info_length; /* 8 */ 120 u8 indirect_levels; 121 u8 unused_flags; 122 } 123 info; 124 struct dx_entry entries[0]; 125}; 126 127struct dx_node 128{ 129 struct fake_dirent fake; 130 struct dx_entry entries[0]; 131}; 132 133 134struct dx_frame 135{ 136 struct buffer_head *bh; 137 struct dx_entry *entries; 138 struct dx_entry *at; 139}; 140 141struct dx_map_entry 142{ 143 u32 hash; 144 u16 offs; 145 u16 size; 146}; 147 148static inline unsigned dx_get_block (struct dx_entry *entry); 149static void dx_set_block (struct dx_entry *entry, unsigned value); 150static inline unsigned dx_get_hash (struct dx_entry *entry); 151static void dx_set_hash (struct dx_entry *entry, unsigned value); 152static unsigned dx_get_count (struct dx_entry *entries); 153static unsigned dx_get_limit (struct dx_entry *entries); 154static void dx_set_count (struct dx_entry *entries, unsigned value); 155static void dx_set_limit (struct dx_entry *entries, unsigned value); 156static unsigned dx_root_limit (struct inode *dir, unsigned infosize); 157static unsigned dx_node_limit (struct inode *dir); 158static struct dx_frame *dx_probe(struct qstr *entry, 159 struct inode *dir, 160 struct dx_hash_info *hinfo, 161 struct dx_frame *frame, 162 int *err); 163static void dx_release (struct dx_frame *frames); 164static int dx_make_map (struct ext3_dir_entry_2 *de, int size, 165 struct dx_hash_info *hinfo, struct dx_map_entry map[]); 166static void dx_sort_map(struct dx_map_entry *map, unsigned count); 167static struct ext3_dir_entry_2 *dx_move_dirents (char *from, char *to, 168 struct dx_map_entry *offsets, int count); 169static struct ext3_dir_entry_2* dx_pack_dirents (char *base, int size); 170static void dx_insert_block (struct dx_frame *frame, u32 hash, u32 block); 171static int ext3_htree_next_block(struct inode *dir, __u32 hash, 172 struct dx_frame *frame, 173 struct dx_frame *frames, 174 __u32 *start_hash); 175static struct buffer_head * ext3_dx_find_entry(struct inode *dir, 176 struct qstr *entry, struct ext3_dir_entry_2 **res_dir, 177 int *err); 178static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry, 179 struct inode *inode); 180 181/* 182 * p is at least 6 bytes before the end of page 183 */ 184static inline struct ext3_dir_entry_2 * 185ext3_next_entry(struct ext3_dir_entry_2 *p) 186{ 187 return (struct ext3_dir_entry_2 *)((char *)p + 188 ext3_rec_len_from_disk(p->rec_len)); 189} 190 191/* 192 * Future: use high four bits of block for coalesce-on-delete flags 193 * Mask them off for now. 194 */ 195 196static inline unsigned dx_get_block (struct dx_entry *entry) 197{ 198 return le32_to_cpu(entry->block) & 0x00ffffff; 199} 200 201static inline void dx_set_block (struct dx_entry *entry, unsigned value) 202{ 203 entry->block = cpu_to_le32(value); 204} 205 206static inline unsigned dx_get_hash (struct dx_entry *entry) 207{ 208 return le32_to_cpu(entry->hash); 209} 210 211static inline void dx_set_hash (struct dx_entry *entry, unsigned value) 212{ 213 entry->hash = cpu_to_le32(value); 214} 215 216static inline unsigned dx_get_count (struct dx_entry *entries) 217{ 218 return le16_to_cpu(((struct dx_countlimit *) entries)->count); 219} 220 221static inline unsigned dx_get_limit (struct dx_entry *entries) 222{ 223 return le16_to_cpu(((struct dx_countlimit *) entries)->limit); 224} 225 226static inline void dx_set_count (struct dx_entry *entries, unsigned value) 227{ 228 ((struct dx_countlimit *) entries)->count = cpu_to_le16(value); 229} 230 231static inline void dx_set_limit (struct dx_entry *entries, unsigned value) 232{ 233 ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value); 234} 235 236static inline unsigned dx_root_limit (struct inode *dir, unsigned infosize) 237{ 238 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(1) - 239 EXT3_DIR_REC_LEN(2) - infosize; 240 return entry_space / sizeof(struct dx_entry); 241} 242 243static inline unsigned dx_node_limit (struct inode *dir) 244{ 245 unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(0); 246 return entry_space / sizeof(struct dx_entry); 247} 248 249/* 250 * Debug 251 */ 252#ifdef DX_DEBUG 253static void dx_show_index (char * label, struct dx_entry *entries) 254{ 255 int i, n = dx_get_count (entries); 256 printk("%s index ", label); 257 for (i = 0; i < n; i++) 258 { 259 printk("%x->%u ", i? dx_get_hash(entries + i): 0, dx_get_block(entries + i)); 260 } 261 printk("\n"); 262} 263 264struct stats 265{ 266 unsigned names; 267 unsigned space; 268 unsigned bcount; 269}; 270 271static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext3_dir_entry_2 *de, 272 int size, int show_names) 273{ 274 unsigned names = 0, space = 0; 275 char *base = (char *) de; 276 struct dx_hash_info h = *hinfo; 277 278 printk("names: "); 279 while ((char *) de < base + size) 280 { 281 if (de->inode) 282 { 283 if (show_names) 284 { 285 int len = de->name_len; 286 char *name = de->name; 287 while (len--) printk("%c", *name++); 288 ext3fs_dirhash(de->name, de->name_len, &h); 289 printk(":%x.%u ", h.hash, 290 ((char *) de - base)); 291 } 292 space += EXT3_DIR_REC_LEN(de->name_len); 293 names++; 294 } 295 de = ext3_next_entry(de); 296 } 297 printk("(%i)\n", names); 298 return (struct stats) { names, space, 1 }; 299} 300 301struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir, 302 struct dx_entry *entries, int levels) 303{ 304 unsigned blocksize = dir->i_sb->s_blocksize; 305 unsigned count = dx_get_count (entries), names = 0, space = 0, i; 306 unsigned bcount = 0; 307 struct buffer_head *bh; 308 int err; 309 printk("%i indexed blocks...\n", count); 310 for (i = 0; i < count; i++, entries++) 311 { 312 u32 block = dx_get_block(entries), hash = i? dx_get_hash(entries): 0; 313 u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash; 314 struct stats stats; 315 printk("%s%3u:%03u hash %8x/%8x ",levels?"":" ", i, block, hash, range); 316 if (!(bh = ext3_bread (NULL,dir, block, 0,&err))) continue; 317 stats = levels? 318 dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1): 319 dx_show_leaf(hinfo, (struct ext3_dir_entry_2 *) bh->b_data, blocksize, 0); 320 names += stats.names; 321 space += stats.space; 322 bcount += stats.bcount; 323 brelse (bh); 324 } 325 if (bcount) 326 printk("%snames %u, fullness %u (%u%%)\n", levels?"":" ", 327 names, space/bcount,(space/bcount)*100/blocksize); 328 return (struct stats) { names, space, bcount}; 329} 330#endif /* DX_DEBUG */ 331 332/* 333 * Probe for a directory leaf block to search. 334 * 335 * dx_probe can return ERR_BAD_DX_DIR, which means there was a format 336 * error in the directory index, and the caller should fall back to 337 * searching the directory normally. The callers of dx_probe **MUST** 338 * check for this error code, and make sure it never gets reflected 339 * back to userspace. 340 */ 341static struct dx_frame * 342dx_probe(struct qstr *entry, struct inode *dir, 343 struct dx_hash_info *hinfo, struct dx_frame *frame_in, int *err) 344{ 345 unsigned count, indirect; 346 struct dx_entry *at, *entries, *p, *q, *m; 347 struct dx_root *root; 348 struct buffer_head *bh; 349 struct dx_frame *frame = frame_in; 350 u32 hash; 351 352 frame->bh = NULL; 353 if (!(bh = ext3_bread (NULL,dir, 0, 0, err))) 354 goto fail; 355 root = (struct dx_root *) bh->b_data; 356 if (root->info.hash_version != DX_HASH_TEA && 357 root->info.hash_version != DX_HASH_HALF_MD4 && 358 root->info.hash_version != DX_HASH_LEGACY) { 359 ext3_warning(dir->i_sb, __func__, 360 "Unrecognised inode hash code %d", 361 root->info.hash_version); 362 brelse(bh); 363 *err = ERR_BAD_DX_DIR; 364 goto fail; 365 } 366 hinfo->hash_version = root->info.hash_version; 367 if (hinfo->hash_version <= DX_HASH_TEA) 368 hinfo->hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned; 369 hinfo->seed = EXT3_SB(dir->i_sb)->s_hash_seed; 370 if (entry) 371 ext3fs_dirhash(entry->name, entry->len, hinfo); 372 hash = hinfo->hash; 373 374 if (root->info.unused_flags & 1) { 375 ext3_warning(dir->i_sb, __func__, 376 "Unimplemented inode hash flags: %#06x", 377 root->info.unused_flags); 378 brelse(bh); 379 *err = ERR_BAD_DX_DIR; 380 goto fail; 381 } 382 383 if ((indirect = root->info.indirect_levels) > 1) { 384 ext3_warning(dir->i_sb, __func__, 385 "Unimplemented inode hash depth: %#06x", 386 root->info.indirect_levels); 387 brelse(bh); 388 *err = ERR_BAD_DX_DIR; 389 goto fail; 390 } 391 392 entries = (struct dx_entry *) (((char *)&root->info) + 393 root->info.info_length); 394 395 if (dx_get_limit(entries) != dx_root_limit(dir, 396 root->info.info_length)) { 397 ext3_warning(dir->i_sb, __func__, 398 "dx entry: limit != root limit"); 399 brelse(bh); 400 *err = ERR_BAD_DX_DIR; 401 goto fail; 402 } 403 404 dxtrace (printk("Look up %x", hash)); 405 while (1) 406 { 407 count = dx_get_count(entries); 408 if (!count || count > dx_get_limit(entries)) { 409 ext3_warning(dir->i_sb, __func__, 410 "dx entry: no count or count > limit"); 411 brelse(bh); 412 *err = ERR_BAD_DX_DIR; 413 goto fail2; 414 } 415 416 p = entries + 1; 417 q = entries + count - 1; 418 while (p <= q) 419 { 420 m = p + (q - p)/2; 421 dxtrace(printk(".")); 422 if (dx_get_hash(m) > hash) 423 q = m - 1; 424 else 425 p = m + 1; 426 } 427 428 if (0) // linear search cross check 429 { 430 unsigned n = count - 1; 431 at = entries; 432 while (n--) 433 { 434 dxtrace(printk(",")); 435 if (dx_get_hash(++at) > hash) 436 { 437 at--; 438 break; 439 } 440 } 441 assert (at == p - 1); 442 } 443 444 at = p - 1; 445 dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at))); 446 frame->bh = bh; 447 frame->entries = entries; 448 frame->at = at; 449 if (!indirect--) return frame; 450 if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0, err))) 451 goto fail2; 452 at = entries = ((struct dx_node *) bh->b_data)->entries; 453 if (dx_get_limit(entries) != dx_node_limit (dir)) { 454 ext3_warning(dir->i_sb, __func__, 455 "dx entry: limit != node limit"); 456 brelse(bh); 457 *err = ERR_BAD_DX_DIR; 458 goto fail2; 459 } 460 frame++; 461 frame->bh = NULL; 462 } 463fail2: 464 while (frame >= frame_in) { 465 brelse(frame->bh); 466 frame--; 467 } 468fail: 469 if (*err == ERR_BAD_DX_DIR) 470 ext3_warning(dir->i_sb, __func__, 471 "Corrupt dir inode %ld, running e2fsck is " 472 "recommended.", dir->i_ino); 473 return NULL; 474} 475 476static void dx_release (struct dx_frame *frames) 477{ 478 if (frames[0].bh == NULL) 479 return; 480 481 if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels) 482 brelse(frames[1].bh); 483 brelse(frames[0].bh); 484} 485 486/* 487 * This function increments the frame pointer to search the next leaf 488 * block, and reads in the necessary intervening nodes if the search 489 * should be necessary. Whether or not the search is necessary is 490 * controlled by the hash parameter. If the hash value is even, then 491 * the search is only continued if the next block starts with that 492 * hash value. This is used if we are searching for a specific file. 493 * 494 * If the hash value is HASH_NB_ALWAYS, then always go to the next block. 495 * 496 * This function returns 1 if the caller should continue to search, 497 * or 0 if it should not. If there is an error reading one of the 498 * index blocks, it will a negative error code. 499 * 500 * If start_hash is non-null, it will be filled in with the starting 501 * hash of the next page. 502 */ 503static int ext3_htree_next_block(struct inode *dir, __u32 hash, 504 struct dx_frame *frame, 505 struct dx_frame *frames, 506 __u32 *start_hash) 507{ 508 struct dx_frame *p; 509 struct buffer_head *bh; 510 int err, num_frames = 0; 511 __u32 bhash; 512 513 p = frame; 514 /* 515 * Find the next leaf page by incrementing the frame pointer. 516 * If we run out of entries in the interior node, loop around and 517 * increment pointer in the parent node. When we break out of 518 * this loop, num_frames indicates the number of interior 519 * nodes need to be read. 520 */ 521 while (1) { 522 if (++(p->at) < p->entries + dx_get_count(p->entries)) 523 break; 524 if (p == frames) 525 return 0; 526 num_frames++; 527 p--; 528 } 529 530 /* 531 * If the hash is 1, then continue only if the next page has a 532 * continuation hash of any value. This is used for readdir 533 * handling. Otherwise, check to see if the hash matches the 534 * desired contiuation hash. If it doesn't, return since 535 * there's no point to read in the successive index pages. 536 */ 537 bhash = dx_get_hash(p->at); 538 if (start_hash) 539 *start_hash = bhash; 540 if ((hash & 1) == 0) { 541 if ((bhash & ~1) != hash) 542 return 0; 543 } 544 /* 545 * If the hash is HASH_NB_ALWAYS, we always go to the next 546 * block so no check is necessary 547 */ 548 while (num_frames--) { 549 if (!(bh = ext3_bread(NULL, dir, dx_get_block(p->at), 550 0, &err))) 551 return err; /* Failure */ 552 p++; 553 brelse (p->bh); 554 p->bh = bh; 555 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries; 556 } 557 return 1; 558} 559 560 561/* 562 * This function fills a red-black tree with information from a 563 * directory block. It returns the number directory entries loaded 564 * into the tree. If there is an error it is returned in err. 565 */ 566static int htree_dirblock_to_tree(struct file *dir_file, 567 struct inode *dir, int block, 568 struct dx_hash_info *hinfo, 569 __u32 start_hash, __u32 start_minor_hash) 570{ 571 struct buffer_head *bh; 572 struct ext3_dir_entry_2 *de, *top; 573 int err, count = 0; 574 575 dxtrace(printk("In htree dirblock_to_tree: block %d\n", block)); 576 if (!(bh = ext3_bread (NULL, dir, block, 0, &err))) 577 return err; 578 579 de = (struct ext3_dir_entry_2 *) bh->b_data; 580 top = (struct ext3_dir_entry_2 *) ((char *) de + 581 dir->i_sb->s_blocksize - 582 EXT3_DIR_REC_LEN(0)); 583 for (; de < top; de = ext3_next_entry(de)) { 584 if (!ext3_check_dir_entry("htree_dirblock_to_tree", dir, de, bh, 585 (block<<EXT3_BLOCK_SIZE_BITS(dir->i_sb)) 586 +((char *)de - bh->b_data))) { 587 /* On error, skip the f_pos to the next block. */ 588 dir_file->f_pos = (dir_file->f_pos | 589 (dir->i_sb->s_blocksize - 1)) + 1; 590 brelse (bh); 591 return count; 592 } 593 ext3fs_dirhash(de->name, de->name_len, hinfo); 594 if ((hinfo->hash < start_hash) || 595 ((hinfo->hash == start_hash) && 596 (hinfo->minor_hash < start_minor_hash))) 597 continue; 598 if (de->inode == 0) 599 continue; 600 if ((err = ext3_htree_store_dirent(dir_file, 601 hinfo->hash, hinfo->minor_hash, de)) != 0) { 602 brelse(bh); 603 return err; 604 } 605 count++; 606 } 607 brelse(bh); 608 return count; 609} 610 611 612/* 613 * This function fills a red-black tree with information from a 614 * directory. We start scanning the directory in hash order, starting 615 * at start_hash and start_minor_hash. 616 * 617 * This function returns the number of entries inserted into the tree, 618 * or a negative error code. 619 */ 620int ext3_htree_fill_tree(struct file *dir_file, __u32 start_hash, 621 __u32 start_minor_hash, __u32 *next_hash) 622{ 623 struct dx_hash_info hinfo; 624 struct ext3_dir_entry_2 *de; 625 struct dx_frame frames[2], *frame; 626 struct inode *dir; 627 int block, err; 628 int count = 0; 629 int ret; 630 __u32 hashval; 631 632 dxtrace(printk("In htree_fill_tree, start hash: %x:%x\n", start_hash, 633 start_minor_hash)); 634 dir = dir_file->f_path.dentry->d_inode; 635 if (!(EXT3_I(dir)->i_flags & EXT3_INDEX_FL)) { 636 hinfo.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version; 637 if (hinfo.hash_version <= DX_HASH_TEA) 638 hinfo.hash_version += 639 EXT3_SB(dir->i_sb)->s_hash_unsigned; 640 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed; 641 count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo, 642 start_hash, start_minor_hash); 643 *next_hash = ~0; 644 return count; 645 } 646 hinfo.hash = start_hash; 647 hinfo.minor_hash = 0; 648 frame = dx_probe(NULL, dir_file->f_path.dentry->d_inode, &hinfo, frames, &err); 649 if (!frame) 650 return err; 651 652 /* Add '.' and '..' from the htree header */ 653 if (!start_hash && !start_minor_hash) { 654 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data; 655 if ((err = ext3_htree_store_dirent(dir_file, 0, 0, de)) != 0) 656 goto errout; 657 count++; 658 } 659 if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) { 660 de = (struct ext3_dir_entry_2 *) frames[0].bh->b_data; 661 de = ext3_next_entry(de); 662 if ((err = ext3_htree_store_dirent(dir_file, 2, 0, de)) != 0) 663 goto errout; 664 count++; 665 } 666 667 while (1) { 668 block = dx_get_block(frame->at); 669 ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo, 670 start_hash, start_minor_hash); 671 if (ret < 0) { 672 err = ret; 673 goto errout; 674 } 675 count += ret; 676 hashval = ~0; 677 ret = ext3_htree_next_block(dir, HASH_NB_ALWAYS, 678 frame, frames, &hashval); 679 *next_hash = hashval; 680 if (ret < 0) { 681 err = ret; 682 goto errout; 683 } 684 /* 685 * Stop if: (a) there are no more entries, or 686 * (b) we have inserted at least one entry and the 687 * next hash value is not a continuation 688 */ 689 if ((ret == 0) || 690 (count && ((hashval & 1) == 0))) 691 break; 692 } 693 dx_release(frames); 694 dxtrace(printk("Fill tree: returned %d entries, next hash: %x\n", 695 count, *next_hash)); 696 return count; 697errout: 698 dx_release(frames); 699 return (err); 700} 701 702 703/* 704 * Directory block splitting, compacting 705 */ 706 707/* 708 * Create map of hash values, offsets, and sizes, stored at end of block. 709 * Returns number of entries mapped. 710 */ 711static int dx_make_map (struct ext3_dir_entry_2 *de, int size, 712 struct dx_hash_info *hinfo, struct dx_map_entry *map_tail) 713{ 714 int count = 0; 715 char *base = (char *) de; 716 struct dx_hash_info h = *hinfo; 717 718 while ((char *) de < base + size) 719 { 720 if (de->name_len && de->inode) { 721 ext3fs_dirhash(de->name, de->name_len, &h); 722 map_tail--; 723 map_tail->hash = h.hash; 724 map_tail->offs = (u16) ((char *) de - base); 725 map_tail->size = le16_to_cpu(de->rec_len); 726 count++; 727 cond_resched(); 728 } 729 /* XXX: do we need to check rec_len == 0 case? -Chris */ 730 de = ext3_next_entry(de); 731 } 732 return count; 733} 734 735/* Sort map by hash value */ 736static void dx_sort_map (struct dx_map_entry *map, unsigned count) 737{ 738 struct dx_map_entry *p, *q, *top = map + count - 1; 739 int more; 740 /* Combsort until bubble sort doesn't suck */ 741 while (count > 2) 742 { 743 count = count*10/13; 744 if (count - 9 < 2) /* 9, 10 -> 11 */ 745 count = 11; 746 for (p = top, q = p - count; q >= map; p--, q--) 747 if (p->hash < q->hash) 748 swap(*p, *q); 749 } 750 /* Garden variety bubble sort */ 751 do { 752 more = 0; 753 q = top; 754 while (q-- > map) 755 { 756 if (q[1].hash >= q[0].hash) 757 continue; 758 swap(*(q+1), *q); 759 more = 1; 760 } 761 } while(more); 762} 763 764static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block) 765{ 766 struct dx_entry *entries = frame->entries; 767 struct dx_entry *old = frame->at, *new = old + 1; 768 int count = dx_get_count(entries); 769 770 assert(count < dx_get_limit(entries)); 771 assert(old < entries + count); 772 memmove(new + 1, new, (char *)(entries + count) - (char *)(new)); 773 dx_set_hash(new, hash); 774 dx_set_block(new, block); 775 dx_set_count(entries, count + 1); 776} 777 778static void ext3_update_dx_flag(struct inode *inode) 779{ 780 if (!EXT3_HAS_COMPAT_FEATURE(inode->i_sb, 781 EXT3_FEATURE_COMPAT_DIR_INDEX)) 782 EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL; 783} 784 785/* 786 * NOTE! unlike strncmp, ext3_match returns 1 for success, 0 for failure. 787 * 788 * `len <= EXT3_NAME_LEN' is guaranteed by caller. 789 * `de != NULL' is guaranteed by caller. 790 */ 791static inline int ext3_match (int len, const char * const name, 792 struct ext3_dir_entry_2 * de) 793{ 794 if (len != de->name_len) 795 return 0; 796 if (!de->inode) 797 return 0; 798 return !memcmp(name, de->name, len); 799} 800 801/* 802 * Returns 0 if not found, -1 on failure, and 1 on success 803 */ 804static inline int search_dirblock(struct buffer_head * bh, 805 struct inode *dir, 806 struct qstr *child, 807 unsigned long offset, 808 struct ext3_dir_entry_2 ** res_dir) 809{ 810 struct ext3_dir_entry_2 * de; 811 char * dlimit; 812 int de_len; 813 const char *name = child->name; 814 int namelen = child->len; 815 816 de = (struct ext3_dir_entry_2 *) bh->b_data; 817 dlimit = bh->b_data + dir->i_sb->s_blocksize; 818 while ((char *) de < dlimit) { 819 /* this code is executed quadratically often */ 820 /* do minimal checking `by hand' */ 821 822 if ((char *) de + namelen <= dlimit && 823 ext3_match (namelen, name, de)) { 824 /* found a match - just to be sure, do a full check */ 825 if (!ext3_check_dir_entry("ext3_find_entry", 826 dir, de, bh, offset)) 827 return -1; 828 *res_dir = de; 829 return 1; 830 } 831 /* prevent looping on a bad block */ 832 de_len = ext3_rec_len_from_disk(de->rec_len); 833 if (de_len <= 0) 834 return -1; 835 offset += de_len; 836 de = (struct ext3_dir_entry_2 *) ((char *) de + de_len); 837 } 838 return 0; 839} 840 841 842/* 843 * ext3_find_entry() 844 * 845 * finds an entry in the specified directory with the wanted name. It 846 * returns the cache buffer in which the entry was found, and the entry 847 * itself (as a parameter - res_dir). It does NOT read the inode of the 848 * entry - you'll have to do that yourself if you want to. 849 * 850 * The returned buffer_head has ->b_count elevated. The caller is expected 851 * to brelse() it when appropriate. 852 */ 853static struct buffer_head *ext3_find_entry(struct inode *dir, 854 struct qstr *entry, 855 struct ext3_dir_entry_2 **res_dir) 856{ 857 struct super_block * sb; 858 struct buffer_head * bh_use[NAMEI_RA_SIZE]; 859 struct buffer_head * bh, *ret = NULL; 860 unsigned long start, block, b; 861 int ra_max = 0; /* Number of bh's in the readahead 862 buffer, bh_use[] */ 863 int ra_ptr = 0; /* Current index into readahead 864 buffer */ 865 int num = 0; 866 int nblocks, i, err; 867 int namelen; 868 869 *res_dir = NULL; 870 sb = dir->i_sb; 871 namelen = entry->len; 872 if (namelen > EXT3_NAME_LEN) 873 return NULL; 874 if (is_dx(dir)) { 875 bh = ext3_dx_find_entry(dir, entry, res_dir, &err); 876 /* 877 * On success, or if the error was file not found, 878 * return. Otherwise, fall back to doing a search the 879 * old fashioned way. 880 */ 881 if (bh || (err != ERR_BAD_DX_DIR)) 882 return bh; 883 dxtrace(printk("ext3_find_entry: dx failed, falling back\n")); 884 } 885 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb); 886 start = EXT3_I(dir)->i_dir_start_lookup; 887 if (start >= nblocks) 888 start = 0; 889 block = start; 890restart: 891 do { 892 /* 893 * We deal with the read-ahead logic here. 894 */ 895 if (ra_ptr >= ra_max) { 896 /* Refill the readahead buffer */ 897 ra_ptr = 0; 898 b = block; 899 for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) { 900 /* 901 * Terminate if we reach the end of the 902 * directory and must wrap, or if our 903 * search has finished at this block. 904 */ 905 if (b >= nblocks || (num && block == start)) { 906 bh_use[ra_max] = NULL; 907 break; 908 } 909 num++; 910 bh = ext3_getblk(NULL, dir, b++, 0, &err); 911 bh_use[ra_max] = bh; 912 if (bh) 913 ll_rw_block(READ_META, 1, &bh); 914 } 915 } 916 if ((bh = bh_use[ra_ptr++]) == NULL) 917 goto next; 918 wait_on_buffer(bh); 919 if (!buffer_uptodate(bh)) { 920 /* read error, skip block & hope for the best */ 921 ext3_error(sb, __func__, "reading directory #%lu " 922 "offset %lu", dir->i_ino, block); 923 brelse(bh); 924 goto next; 925 } 926 i = search_dirblock(bh, dir, entry, 927 block << EXT3_BLOCK_SIZE_BITS(sb), res_dir); 928 if (i == 1) { 929 EXT3_I(dir)->i_dir_start_lookup = block; 930 ret = bh; 931 goto cleanup_and_exit; 932 } else { 933 brelse(bh); 934 if (i < 0) 935 goto cleanup_and_exit; 936 } 937 next: 938 if (++block >= nblocks) 939 block = 0; 940 } while (block != start); 941 942 /* 943 * If the directory has grown while we were searching, then 944 * search the last part of the directory before giving up. 945 */ 946 block = nblocks; 947 nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb); 948 if (block < nblocks) { 949 start = 0; 950 goto restart; 951 } 952 953cleanup_and_exit: 954 /* Clean up the read-ahead blocks */ 955 for (; ra_ptr < ra_max; ra_ptr++) 956 brelse (bh_use[ra_ptr]); 957 return ret; 958} 959 960static struct buffer_head * ext3_dx_find_entry(struct inode *dir, 961 struct qstr *entry, struct ext3_dir_entry_2 **res_dir, 962 int *err) 963{ 964 struct super_block * sb; 965 struct dx_hash_info hinfo; 966 u32 hash; 967 struct dx_frame frames[2], *frame; 968 struct ext3_dir_entry_2 *de, *top; 969 struct buffer_head *bh; 970 unsigned long block; 971 int retval; 972 int namelen = entry->len; 973 const u8 *name = entry->name; 974 975 sb = dir->i_sb; 976 /* NFS may look up ".." - look at dx_root directory block */ 977 if (namelen > 2 || name[0] != '.'|| (namelen == 2 && name[1] != '.')) { 978 if (!(frame = dx_probe(entry, dir, &hinfo, frames, err))) 979 return NULL; 980 } else { 981 frame = frames; 982 frame->bh = NULL; /* for dx_release() */ 983 frame->at = (struct dx_entry *)frames; /* hack for zero entry*/ 984 dx_set_block(frame->at, 0); /* dx_root block is 0 */ 985 } 986 hash = hinfo.hash; 987 do { 988 block = dx_get_block(frame->at); 989 if (!(bh = ext3_bread (NULL,dir, block, 0, err))) 990 goto errout; 991 de = (struct ext3_dir_entry_2 *) bh->b_data; 992 top = (struct ext3_dir_entry_2 *) ((char *) de + sb->s_blocksize - 993 EXT3_DIR_REC_LEN(0)); 994 for (; de < top; de = ext3_next_entry(de)) { 995 int off = (block << EXT3_BLOCK_SIZE_BITS(sb)) 996 + ((char *) de - bh->b_data); 997 998 if (!ext3_check_dir_entry(__func__, dir, de, bh, off)) { 999 brelse(bh); 1000 *err = ERR_BAD_DX_DIR; 1001 goto errout; 1002 } 1003 1004 if (ext3_match(namelen, name, de)) { 1005 *res_dir = de; 1006 dx_release(frames); 1007 return bh; 1008 } 1009 } 1010 brelse (bh); 1011 /* Check to see if we should continue to search */ 1012 retval = ext3_htree_next_block(dir, hash, frame, 1013 frames, NULL); 1014 if (retval < 0) { 1015 ext3_warning(sb, __func__, 1016 "error reading index page in directory #%lu", 1017 dir->i_ino); 1018 *err = retval; 1019 goto errout; 1020 } 1021 } while (retval == 1); 1022 1023 *err = -ENOENT; 1024errout: 1025 dxtrace(printk("%s not found\n", name)); 1026 dx_release (frames); 1027 return NULL; 1028} 1029 1030static struct dentry *ext3_lookup(struct inode * dir, struct dentry *dentry, struct nameidata *nd) 1031{ 1032 struct inode * inode; 1033 struct ext3_dir_entry_2 * de; 1034 struct buffer_head * bh; 1035 1036 if (dentry->d_name.len > EXT3_NAME_LEN) 1037 return ERR_PTR(-ENAMETOOLONG); 1038 1039 bh = ext3_find_entry(dir, &dentry->d_name, &de); 1040 inode = NULL; 1041 if (bh) { 1042 unsigned long ino = le32_to_cpu(de->inode); 1043 brelse (bh); 1044 if (!ext3_valid_inum(dir->i_sb, ino)) { 1045 ext3_error(dir->i_sb, "ext3_lookup", 1046 "bad inode number: %lu", ino); 1047 return ERR_PTR(-EIO); 1048 } 1049 inode = ext3_iget(dir->i_sb, ino); 1050 if (IS_ERR(inode)) 1051 return ERR_CAST(inode); 1052 } 1053 return d_splice_alias(inode, dentry); 1054} 1055 1056 1057struct dentry *ext3_get_parent(struct dentry *child) 1058{ 1059 unsigned long ino; 1060 struct qstr dotdot = {.name = "..", .len = 2}; 1061 struct ext3_dir_entry_2 * de; 1062 struct buffer_head *bh; 1063 1064 bh = ext3_find_entry(child->d_inode, &dotdot, &de); 1065 if (!bh) 1066 return ERR_PTR(-ENOENT); 1067 ino = le32_to_cpu(de->inode); 1068 brelse(bh); 1069 1070 if (!ext3_valid_inum(child->d_inode->i_sb, ino)) { 1071 ext3_error(child->d_inode->i_sb, "ext3_get_parent", 1072 "bad inode number: %lu", ino); 1073 return ERR_PTR(-EIO); 1074 } 1075 1076 return d_obtain_alias(ext3_iget(child->d_inode->i_sb, ino)); 1077} 1078 1079#define S_SHIFT 12 1080static unsigned char ext3_type_by_mode[S_IFMT >> S_SHIFT] = { 1081 [S_IFREG >> S_SHIFT] = EXT3_FT_REG_FILE, 1082 [S_IFDIR >> S_SHIFT] = EXT3_FT_DIR, 1083 [S_IFCHR >> S_SHIFT] = EXT3_FT_CHRDEV, 1084 [S_IFBLK >> S_SHIFT] = EXT3_FT_BLKDEV, 1085 [S_IFIFO >> S_SHIFT] = EXT3_FT_FIFO, 1086 [S_IFSOCK >> S_SHIFT] = EXT3_FT_SOCK, 1087 [S_IFLNK >> S_SHIFT] = EXT3_FT_SYMLINK, 1088}; 1089 1090static inline void ext3_set_de_type(struct super_block *sb, 1091 struct ext3_dir_entry_2 *de, 1092 umode_t mode) { 1093 if (EXT3_HAS_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_FILETYPE)) 1094 de->file_type = ext3_type_by_mode[(mode & S_IFMT)>>S_SHIFT]; 1095} 1096 1097/* 1098 * Move count entries from end of map between two memory locations. 1099 * Returns pointer to last entry moved. 1100 */ 1101static struct ext3_dir_entry_2 * 1102dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count) 1103{ 1104 unsigned rec_len = 0; 1105 1106 while (count--) { 1107 struct ext3_dir_entry_2 *de = (struct ext3_dir_entry_2 *) (from + map->offs); 1108 rec_len = EXT3_DIR_REC_LEN(de->name_len); 1109 memcpy (to, de, rec_len); 1110 ((struct ext3_dir_entry_2 *) to)->rec_len = 1111 ext3_rec_len_to_disk(rec_len); 1112 de->inode = 0; 1113 map++; 1114 to += rec_len; 1115 } 1116 return (struct ext3_dir_entry_2 *) (to - rec_len); 1117} 1118 1119/* 1120 * Compact each dir entry in the range to the minimal rec_len. 1121 * Returns pointer to last entry in range. 1122 */ 1123static struct ext3_dir_entry_2* dx_pack_dirents(char *base, int size) 1124{ 1125 struct ext3_dir_entry_2 *next, *to, *prev, *de = (struct ext3_dir_entry_2 *) base; 1126 unsigned rec_len = 0; 1127 1128 prev = to = de; 1129 while ((char*)de < base + size) { 1130 next = ext3_next_entry(de); 1131 if (de->inode && de->name_len) { 1132 rec_len = EXT3_DIR_REC_LEN(de->name_len); 1133 if (de > to) 1134 memmove(to, de, rec_len); 1135 to->rec_len = ext3_rec_len_to_disk(rec_len); 1136 prev = to; 1137 to = (struct ext3_dir_entry_2 *) (((char *) to) + rec_len); 1138 } 1139 de = next; 1140 } 1141 return prev; 1142} 1143 1144/* 1145 * Split a full leaf block to make room for a new dir entry. 1146 * Allocate a new block, and move entries so that they are approx. equally full. 1147 * Returns pointer to de in block into which the new entry will be inserted. 1148 */ 1149static struct ext3_dir_entry_2 *do_split(handle_t *handle, struct inode *dir, 1150 struct buffer_head **bh,struct dx_frame *frame, 1151 struct dx_hash_info *hinfo, int *error) 1152{ 1153 unsigned blocksize = dir->i_sb->s_blocksize; 1154 unsigned count, continued; 1155 struct buffer_head *bh2; 1156 u32 newblock; 1157 u32 hash2; 1158 struct dx_map_entry *map; 1159 char *data1 = (*bh)->b_data, *data2; 1160 unsigned split, move, size; 1161 struct ext3_dir_entry_2 *de = NULL, *de2; 1162 int err = 0, i; 1163 1164 bh2 = ext3_append (handle, dir, &newblock, &err); 1165 if (!(bh2)) { 1166 brelse(*bh); 1167 *bh = NULL; 1168 goto errout; 1169 } 1170 1171 BUFFER_TRACE(*bh, "get_write_access"); 1172 err = ext3_journal_get_write_access(handle, *bh); 1173 if (err) 1174 goto journal_error; 1175 1176 BUFFER_TRACE(frame->bh, "get_write_access"); 1177 err = ext3_journal_get_write_access(handle, frame->bh); 1178 if (err) 1179 goto journal_error; 1180 1181 data2 = bh2->b_data; 1182 1183 /* create map in the end of data2 block */ 1184 map = (struct dx_map_entry *) (data2 + blocksize); 1185 count = dx_make_map ((struct ext3_dir_entry_2 *) data1, 1186 blocksize, hinfo, map); 1187 map -= count; 1188 dx_sort_map (map, count); 1189 /* Split the existing block in the middle, size-wise */ 1190 size = 0; 1191 move = 0; 1192 for (i = count-1; i >= 0; i--) { 1193 /* is more than half of this entry in 2nd half of the block? */ 1194 if (size + map[i].size/2 > blocksize/2) 1195 break; 1196 size += map[i].size; 1197 move++; 1198 } 1199 /* map index at which we will split */ 1200 split = count - move; 1201 hash2 = map[split].hash; 1202 continued = hash2 == map[split - 1].hash; 1203 dxtrace(printk("Split block %i at %x, %i/%i\n", 1204 dx_get_block(frame->at), hash2, split, count-split)); 1205 1206 /* Fancy dance to stay within two buffers */ 1207 de2 = dx_move_dirents(data1, data2, map + split, count - split); 1208 de = dx_pack_dirents(data1,blocksize); 1209 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de); 1210 de2->rec_len = ext3_rec_len_to_disk(data2 + blocksize - (char *) de2); 1211 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data1, blocksize, 1)); 1212 dxtrace(dx_show_leaf (hinfo, (struct ext3_dir_entry_2 *) data2, blocksize, 1)); 1213 1214 /* Which block gets the new entry? */ 1215 if (hinfo->hash >= hash2) 1216 { 1217 swap(*bh, bh2); 1218 de = de2; 1219 } 1220 dx_insert_block (frame, hash2 + continued, newblock); 1221 err = ext3_journal_dirty_metadata (handle, bh2); 1222 if (err) 1223 goto journal_error; 1224 err = ext3_journal_dirty_metadata (handle, frame->bh); 1225 if (err) 1226 goto journal_error; 1227 brelse (bh2); 1228 dxtrace(dx_show_index ("frame", frame->entries)); 1229 return de; 1230 1231journal_error: 1232 brelse(*bh); 1233 brelse(bh2); 1234 *bh = NULL; 1235 ext3_std_error(dir->i_sb, err); 1236errout: 1237 *error = err; 1238 return NULL; 1239} 1240 1241 1242/* 1243 * Add a new entry into a directory (leaf) block. If de is non-NULL, 1244 * it points to a directory entry which is guaranteed to be large 1245 * enough for new directory entry. If de is NULL, then 1246 * add_dirent_to_buf will attempt search the directory block for 1247 * space. It will return -ENOSPC if no space is available, and -EIO 1248 * and -EEXIST if directory entry already exists. 1249 * 1250 * NOTE! bh is NOT released in the case where ENOSPC is returned. In 1251 * all other cases bh is released. 1252 */ 1253static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry, 1254 struct inode *inode, struct ext3_dir_entry_2 *de, 1255 struct buffer_head * bh) 1256{ 1257 struct inode *dir = dentry->d_parent->d_inode; 1258 const char *name = dentry->d_name.name; 1259 int namelen = dentry->d_name.len; 1260 unsigned long offset = 0; 1261 unsigned short reclen; 1262 int nlen, rlen, err; 1263 char *top; 1264 1265 reclen = EXT3_DIR_REC_LEN(namelen); 1266 if (!de) { 1267 de = (struct ext3_dir_entry_2 *)bh->b_data; 1268 top = bh->b_data + dir->i_sb->s_blocksize - reclen; 1269 while ((char *) de <= top) { 1270 if (!ext3_check_dir_entry("ext3_add_entry", dir, de, 1271 bh, offset)) { 1272 brelse (bh); 1273 return -EIO; 1274 } 1275 if (ext3_match (namelen, name, de)) { 1276 brelse (bh); 1277 return -EEXIST; 1278 } 1279 nlen = EXT3_DIR_REC_LEN(de->name_len); 1280 rlen = ext3_rec_len_from_disk(de->rec_len); 1281 if ((de->inode? rlen - nlen: rlen) >= reclen) 1282 break; 1283 de = (struct ext3_dir_entry_2 *)((char *)de + rlen); 1284 offset += rlen; 1285 } 1286 if ((char *) de > top) 1287 return -ENOSPC; 1288 } 1289 BUFFER_TRACE(bh, "get_write_access"); 1290 err = ext3_journal_get_write_access(handle, bh); 1291 if (err) { 1292 ext3_std_error(dir->i_sb, err); 1293 brelse(bh); 1294 return err; 1295 } 1296 1297 /* By now the buffer is marked for journaling */ 1298 nlen = EXT3_DIR_REC_LEN(de->name_len); 1299 rlen = ext3_rec_len_from_disk(de->rec_len); 1300 if (de->inode) { 1301 struct ext3_dir_entry_2 *de1 = (struct ext3_dir_entry_2 *)((char *)de + nlen); 1302 de1->rec_len = ext3_rec_len_to_disk(rlen - nlen); 1303 de->rec_len = ext3_rec_len_to_disk(nlen); 1304 de = de1; 1305 } 1306 de->file_type = EXT3_FT_UNKNOWN; 1307 if (inode) { 1308 de->inode = cpu_to_le32(inode->i_ino); 1309 ext3_set_de_type(dir->i_sb, de, inode->i_mode); 1310 } else 1311 de->inode = 0; 1312 de->name_len = namelen; 1313 memcpy (de->name, name, namelen); 1314 /* 1315 * XXX shouldn't update any times until successful 1316 * completion of syscall, but too many callers depend 1317 * on this. 1318 * 1319 * XXX similarly, too many callers depend on 1320 * ext3_new_inode() setting the times, but error 1321 * recovery deletes the inode, so the worst that can 1322 * happen is that the times are slightly out of date 1323 * and/or different from the directory change time. 1324 */ 1325 dir->i_mtime = dir->i_ctime = CURRENT_TIME_SEC; 1326 ext3_update_dx_flag(dir); 1327 dir->i_version++; 1328 ext3_mark_inode_dirty(handle, dir); 1329 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata"); 1330 err = ext3_journal_dirty_metadata(handle, bh); 1331 if (err) 1332 ext3_std_error(dir->i_sb, err); 1333 brelse(bh); 1334 return 0; 1335} 1336 1337/* 1338 * This converts a one block unindexed directory to a 3 block indexed 1339 * directory, and adds the dentry to the indexed directory. 1340 */ 1341static int make_indexed_dir(handle_t *handle, struct dentry *dentry, 1342 struct inode *inode, struct buffer_head *bh) 1343{ 1344 struct inode *dir = dentry->d_parent->d_inode; 1345 const char *name = dentry->d_name.name; 1346 int namelen = dentry->d_name.len; 1347 struct buffer_head *bh2; 1348 struct dx_root *root; 1349 struct dx_frame frames[2], *frame; 1350 struct dx_entry *entries; 1351 struct ext3_dir_entry_2 *de, *de2; 1352 char *data1, *top; 1353 unsigned len; 1354 int retval; 1355 unsigned blocksize; 1356 struct dx_hash_info hinfo; 1357 u32 block; 1358 struct fake_dirent *fde; 1359 1360 blocksize = dir->i_sb->s_blocksize; 1361 dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino)); 1362 retval = ext3_journal_get_write_access(handle, bh); 1363 if (retval) { 1364 ext3_std_error(dir->i_sb, retval); 1365 brelse(bh); 1366 return retval; 1367 } 1368 root = (struct dx_root *) bh->b_data; 1369 1370 /* The 0th block becomes the root, move the dirents out */ 1371 fde = &root->dotdot; 1372 de = (struct ext3_dir_entry_2 *)((char *)fde + 1373 ext3_rec_len_from_disk(fde->rec_len)); 1374 if ((char *) de >= (((char *) root) + blocksize)) { 1375 ext3_error(dir->i_sb, __func__, 1376 "invalid rec_len for '..' in inode %lu", 1377 dir->i_ino); 1378 brelse(bh); 1379 return -EIO; 1380 } 1381 len = ((char *) root) + blocksize - (char *) de; 1382 1383 bh2 = ext3_append (handle, dir, &block, &retval); 1384 if (!(bh2)) { 1385 brelse(bh); 1386 return retval; 1387 } 1388 EXT3_I(dir)->i_flags |= EXT3_INDEX_FL; 1389 data1 = bh2->b_data; 1390 1391 memcpy (data1, de, len); 1392 de = (struct ext3_dir_entry_2 *) data1; 1393 top = data1 + len; 1394 while ((char *)(de2 = ext3_next_entry(de)) < top) 1395 de = de2; 1396 de->rec_len = ext3_rec_len_to_disk(data1 + blocksize - (char *) de); 1397 /* Initialize the root; the dot dirents already exist */ 1398 de = (struct ext3_dir_entry_2 *) (&root->dotdot); 1399 de->rec_len = ext3_rec_len_to_disk(blocksize - EXT3_DIR_REC_LEN(2)); 1400 memset (&root->info, 0, sizeof(root->info)); 1401 root->info.info_length = sizeof(root->info); 1402 root->info.hash_version = EXT3_SB(dir->i_sb)->s_def_hash_version; 1403 entries = root->entries; 1404 dx_set_block (entries, 1); 1405 dx_set_count (entries, 1); 1406 dx_set_limit (entries, dx_root_limit(dir, sizeof(root->info))); 1407 1408 /* Initialize as for dx_probe */ 1409 hinfo.hash_version = root->info.hash_version; 1410 if (hinfo.hash_version <= DX_HASH_TEA) 1411 hinfo.hash_version += EXT3_SB(dir->i_sb)->s_hash_unsigned; 1412 hinfo.seed = EXT3_SB(dir->i_sb)->s_hash_seed; 1413 ext3fs_dirhash(name, namelen, &hinfo); 1414 frame = frames; 1415 frame->entries = entries; 1416 frame->at = entries; 1417 frame->bh = bh; 1418 bh = bh2; 1419 de = do_split(handle,dir, &bh, frame, &hinfo, &retval); 1420 dx_release (frames); 1421 if (!(de)) 1422 return retval; 1423 1424 return add_dirent_to_buf(handle, dentry, inode, de, bh); 1425} 1426 1427/* 1428 * ext3_add_entry() 1429 * 1430 * adds a file entry to the specified directory, using the same 1431 * semantics as ext3_find_entry(). It returns NULL if it failed. 1432 * 1433 * NOTE!! The inode part of 'de' is left at 0 - which means you 1434 * may not sleep between calling this and putting something into 1435 * the entry, as someone else might have used it while you slept. 1436 */ 1437static int ext3_add_entry (handle_t *handle, struct dentry *dentry, 1438 struct inode *inode) 1439{ 1440 struct inode *dir = dentry->d_parent->d_inode; 1441 unsigned long offset; 1442 struct buffer_head * bh; 1443 struct ext3_dir_entry_2 *de; 1444 struct super_block * sb; 1445 int retval; 1446 int dx_fallback=0; 1447 unsigned blocksize; 1448 u32 block, blocks; 1449 1450 sb = dir->i_sb; 1451 blocksize = sb->s_blocksize; 1452 if (!dentry->d_name.len) 1453 return -EINVAL; 1454 if (is_dx(dir)) { 1455 retval = ext3_dx_add_entry(handle, dentry, inode); 1456 if (!retval || (retval != ERR_BAD_DX_DIR)) 1457 return retval; 1458 EXT3_I(dir)->i_flags &= ~EXT3_INDEX_FL; 1459 dx_fallback++; 1460 ext3_mark_inode_dirty(handle, dir); 1461 } 1462 blocks = dir->i_size >> sb->s_blocksize_bits; 1463 for (block = 0, offset = 0; block < blocks; block++) { 1464 bh = ext3_bread(handle, dir, block, 0, &retval); 1465 if(!bh) 1466 return retval; 1467 retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh); 1468 if (retval != -ENOSPC) 1469 return retval; 1470 1471 if (blocks == 1 && !dx_fallback && 1472 EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX)) 1473 return make_indexed_dir(handle, dentry, inode, bh); 1474 brelse(bh); 1475 } 1476 bh = ext3_append(handle, dir, &block, &retval); 1477 if (!bh) 1478 return retval; 1479 de = (struct ext3_dir_entry_2 *) bh->b_data; 1480 de->inode = 0; 1481 de->rec_len = ext3_rec_len_to_disk(blocksize); 1482 return add_dirent_to_buf(handle, dentry, inode, de, bh); 1483} 1484 1485/* 1486 * Returns 0 for success, or a negative error value 1487 */ 1488static int ext3_dx_add_entry(handle_t *handle, struct dentry *dentry, 1489 struct inode *inode) 1490{ 1491 struct dx_frame frames[2], *frame; 1492 struct dx_entry *entries, *at; 1493 struct dx_hash_info hinfo; 1494 struct buffer_head * bh; 1495 struct inode *dir = dentry->d_parent->d_inode; 1496 struct super_block * sb = dir->i_sb; 1497 struct ext3_dir_entry_2 *de; 1498 int err; 1499 1500 frame = dx_probe(&dentry->d_name, dir, &hinfo, frames, &err); 1501 if (!frame) 1502 return err; 1503 entries = frame->entries; 1504 at = frame->at; 1505 1506 if (!(bh = ext3_bread(handle,dir, dx_get_block(frame->at), 0, &err))) 1507 goto cleanup; 1508 1509 BUFFER_TRACE(bh, "get_write_access"); 1510 err = ext3_journal_get_write_access(handle, bh); 1511 if (err) 1512 goto journal_error; 1513 1514 err = add_dirent_to_buf(handle, dentry, inode, NULL, bh); 1515 if (err != -ENOSPC) { 1516 bh = NULL; 1517 goto cleanup; 1518 } 1519 1520 /* Block full, should compress but for now just split */ 1521 dxtrace(printk("using %u of %u node entries\n", 1522 dx_get_count(entries), dx_get_limit(entries))); 1523 /* Need to split index? */ 1524 if (dx_get_count(entries) == dx_get_limit(entries)) { 1525 u32 newblock; 1526 unsigned icount = dx_get_count(entries); 1527 int levels = frame - frames; 1528 struct dx_entry *entries2; 1529 struct dx_node *node2; 1530 struct buffer_head *bh2; 1531 1532 if (levels && (dx_get_count(frames->entries) == 1533 dx_get_limit(frames->entries))) { 1534 ext3_warning(sb, __func__, 1535 "Directory index full!"); 1536 err = -ENOSPC; 1537 goto cleanup; 1538 } 1539 bh2 = ext3_append (handle, dir, &newblock, &err); 1540 if (!(bh2)) 1541 goto cleanup; 1542 node2 = (struct dx_node *)(bh2->b_data); 1543 entries2 = node2->entries; 1544 node2->fake.rec_len = ext3_rec_len_to_disk(sb->s_blocksize); 1545 node2->fake.inode = 0; 1546 BUFFER_TRACE(frame->bh, "get_write_access"); 1547 err = ext3_journal_get_write_access(handle, frame->bh); 1548 if (err) 1549 goto journal_error; 1550 if (levels) { 1551 unsigned icount1 = icount/2, icount2 = icount - icount1; 1552 unsigned hash2 = dx_get_hash(entries + icount1); 1553 dxtrace(printk("Split index %i/%i\n", icount1, icount2)); 1554 1555 BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */ 1556 err = ext3_journal_get_write_access(handle, 1557 frames[0].bh); 1558 if (err) 1559 goto journal_error; 1560 1561 memcpy ((char *) entries2, (char *) (entries + icount1), 1562 icount2 * sizeof(struct dx_entry)); 1563 dx_set_count (entries, icount1); 1564 dx_set_count (entries2, icount2); 1565 dx_set_limit (entries2, dx_node_limit(dir)); 1566 1567 /* Which index block gets the new entry? */ 1568 if (at - entries >= icount1) { 1569 frame->at = at = at - entries - icount1 + entries2; 1570 frame->entries = entries = entries2; 1571 swap(frame->bh, bh2); 1572 } 1573 dx_insert_block (frames + 0, hash2, newblock); 1574 dxtrace(dx_show_index ("node", frames[1].entries)); 1575 dxtrace(dx_show_index ("node", 1576 ((struct dx_node *) bh2->b_data)->entries)); 1577 err = ext3_journal_dirty_metadata(handle, bh2); 1578 if (err) 1579 goto journal_error; 1580 brelse (bh2); 1581 } else { 1582 dxtrace(printk("Creating second level index...\n")); 1583 memcpy((char *) entries2, (char *) entries, 1584 icount * sizeof(struct dx_entry)); 1585 dx_set_limit(entries2, dx_node_limit(dir)); 1586 1587 /* Set up root */ 1588 dx_set_count(entries, 1); 1589 dx_set_block(entries + 0, newblock); 1590 ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1; 1591 1592 /* Add new access path frame */ 1593 frame = frames + 1; 1594 frame->at = at = at - entries + entries2; 1595 frame->entries = entries = entries2; 1596 frame->bh = bh2; 1597 err = ext3_journal_get_write_access(handle, 1598 frame->bh); 1599 if (err) 1600 goto journal_error; 1601 } 1602 ext3_journal_dirty_metadata(handle, frames[0].bh); 1603 } 1604 de = do_split(handle, dir, &bh, frame, &hinfo, &err); 1605 if (!de) 1606 goto cleanup; 1607 err = add_dirent_to_buf(handle, dentry, inode, de, bh); 1608 bh = NULL; 1609 goto cleanup; 1610 1611journal_error: 1612 ext3_std_error(dir->i_sb, err); 1613cleanup: 1614 if (bh) 1615 brelse(bh); 1616 dx_release(frames); 1617 return err; 1618} 1619 1620/* 1621 * ext3_delete_entry deletes a directory entry by merging it with the 1622 * previous entry 1623 */ 1624static int ext3_delete_entry (handle_t *handle, 1625 struct inode * dir, 1626 struct ext3_dir_entry_2 * de_del, 1627 struct buffer_head * bh) 1628{ 1629 struct ext3_dir_entry_2 * de, * pde; 1630 int i; 1631 1632 i = 0; 1633 pde = NULL; 1634 de = (struct ext3_dir_entry_2 *) bh->b_data; 1635 while (i < bh->b_size) { 1636 if (!ext3_check_dir_entry("ext3_delete_entry", dir, de, bh, i)) 1637 return -EIO; 1638 if (de == de_del) { 1639 BUFFER_TRACE(bh, "get_write_access"); 1640 ext3_journal_get_write_access(handle, bh); 1641 if (pde) 1642 pde->rec_len = ext3_rec_len_to_disk( 1643 ext3_rec_len_from_disk(pde->rec_len) + 1644 ext3_rec_len_from_disk(de->rec_len)); 1645 else 1646 de->inode = 0; 1647 dir->i_version++; 1648 BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata"); 1649 ext3_journal_dirty_metadata(handle, bh); 1650 return 0; 1651 } 1652 i += ext3_rec_len_from_disk(de->rec_len); 1653 pde = de; 1654 de = ext3_next_entry(de); 1655 } 1656 return -ENOENT; 1657} 1658 1659static int ext3_add_nondir(handle_t *handle, 1660 struct dentry *dentry, struct inode *inode) 1661{ 1662 int err = ext3_add_entry(handle, dentry, inode); 1663 if (!err) { 1664 ext3_mark_inode_dirty(handle, inode); 1665 d_instantiate(dentry, inode); 1666 unlock_new_inode(inode); 1667 return 0; 1668 } 1669 drop_nlink(inode); 1670 unlock_new_inode(inode); 1671 iput(inode); 1672 return err; 1673} 1674 1675/* 1676 * By the time this is called, we already have created 1677 * the directory cache entry for the new file, but it 1678 * is so far negative - it has no inode. 1679 * 1680 * If the create succeeds, we fill in the inode information 1681 * with d_instantiate(). 1682 */ 1683static int ext3_create (struct inode * dir, struct dentry * dentry, int mode, 1684 struct nameidata *nd) 1685{ 1686 handle_t *handle; 1687 struct inode * inode; 1688 int err, retries = 0; 1689 1690retry: 1691 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) + 1692 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 + 1693 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb)); 1694 if (IS_ERR(handle)) 1695 return PTR_ERR(handle); 1696 1697 if (IS_DIRSYNC(dir)) 1698 handle->h_sync = 1; 1699 1700 inode = ext3_new_inode (handle, dir, mode); 1701 err = PTR_ERR(inode); 1702 if (!IS_ERR(inode)) { 1703 inode->i_op = &ext3_file_inode_operations; 1704 inode->i_fop = &ext3_file_operations; 1705 ext3_set_aops(inode); 1706 err = ext3_add_nondir(handle, dentry, inode); 1707 } 1708 ext3_journal_stop(handle); 1709 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries)) 1710 goto retry; 1711 return err; 1712} 1713 1714static int ext3_mknod (struct inode * dir, struct dentry *dentry, 1715 int mode, dev_t rdev) 1716{ 1717 handle_t *handle; 1718 struct inode *inode; 1719 int err, retries = 0; 1720 1721 if (!new_valid_dev(rdev)) 1722 return -EINVAL; 1723 1724retry: 1725 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) + 1726 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 + 1727 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb)); 1728 if (IS_ERR(handle)) 1729 return PTR_ERR(handle); 1730 1731 if (IS_DIRSYNC(dir)) 1732 handle->h_sync = 1; 1733 1734 inode = ext3_new_inode (handle, dir, mode); 1735 err = PTR_ERR(inode); 1736 if (!IS_ERR(inode)) { 1737 init_special_inode(inode, inode->i_mode, rdev); 1738#ifdef CONFIG_EXT3_FS_XATTR 1739 inode->i_op = &ext3_special_inode_operations; 1740#endif 1741 err = ext3_add_nondir(handle, dentry, inode); 1742 } 1743 ext3_journal_stop(handle); 1744 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries)) 1745 goto retry; 1746 return err; 1747} 1748 1749static int ext3_mkdir(struct inode * dir, struct dentry * dentry, int mode) 1750{ 1751 handle_t *handle; 1752 struct inode * inode; 1753 struct buffer_head * dir_block; 1754 struct ext3_dir_entry_2 * de; 1755 int err, retries = 0; 1756 1757 if (dir->i_nlink >= EXT3_LINK_MAX) 1758 return -EMLINK; 1759 1760retry: 1761 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) + 1762 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3 + 1763 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb)); 1764 if (IS_ERR(handle)) 1765 return PTR_ERR(handle); 1766 1767 if (IS_DIRSYNC(dir)) 1768 handle->h_sync = 1; 1769 1770 inode = ext3_new_inode (handle, dir, S_IFDIR | mode); 1771 err = PTR_ERR(inode); 1772 if (IS_ERR(inode)) 1773 goto out_stop; 1774 1775 inode->i_op = &ext3_dir_inode_operations; 1776 inode->i_fop = &ext3_dir_operations; 1777 inode->i_size = EXT3_I(inode)->i_disksize = inode->i_sb->s_blocksize; 1778 dir_block = ext3_bread (handle, inode, 0, 1, &err); 1779 if (!dir_block) { 1780 drop_nlink(inode); /* is this nlink == 0? */ 1781 unlock_new_inode(inode); 1782 ext3_mark_inode_dirty(handle, inode); 1783 iput (inode); 1784 goto out_stop; 1785 } 1786 BUFFER_TRACE(dir_block, "get_write_access"); 1787 ext3_journal_get_write_access(handle, dir_block); 1788 de = (struct ext3_dir_entry_2 *) dir_block->b_data; 1789 de->inode = cpu_to_le32(inode->i_ino); 1790 de->name_len = 1; 1791 de->rec_len = ext3_rec_len_to_disk(EXT3_DIR_REC_LEN(de->name_len)); 1792 strcpy (de->name, "."); 1793 ext3_set_de_type(dir->i_sb, de, S_IFDIR); 1794 de = ext3_next_entry(de); 1795 de->inode = cpu_to_le32(dir->i_ino); 1796 de->rec_len = ext3_rec_len_to_disk(inode->i_sb->s_blocksize - 1797 EXT3_DIR_REC_LEN(1)); 1798 de->name_len = 2; 1799 strcpy (de->name, ".."); 1800 ext3_set_de_type(dir->i_sb, de, S_IFDIR); 1801 inode->i_nlink = 2; 1802 BUFFER_TRACE(dir_block, "call ext3_journal_dirty_metadata"); 1803 ext3_journal_dirty_metadata(handle, dir_block); 1804 brelse (dir_block); 1805 ext3_mark_inode_dirty(handle, inode); 1806 err = ext3_add_entry (handle, dentry, inode); 1807 if (err) { 1808 inode->i_nlink = 0; 1809 unlock_new_inode(inode); 1810 ext3_mark_inode_dirty(handle, inode); 1811 iput (inode); 1812 goto out_stop; 1813 } 1814 inc_nlink(dir); 1815 ext3_update_dx_flag(dir); 1816 ext3_mark_inode_dirty(handle, dir); 1817 d_instantiate(dentry, inode); 1818 unlock_new_inode(inode); 1819out_stop: 1820 ext3_journal_stop(handle); 1821 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries)) 1822 goto retry; 1823 return err; 1824} 1825 1826/* 1827 * routine to check that the specified directory is empty (for rmdir) 1828 */ 1829static int empty_dir (struct inode * inode) 1830{ 1831 unsigned long offset; 1832 struct buffer_head * bh; 1833 struct ext3_dir_entry_2 * de, * de1; 1834 struct super_block * sb; 1835 int err = 0; 1836 1837 sb = inode->i_sb; 1838 if (inode->i_size < EXT3_DIR_REC_LEN(1) + EXT3_DIR_REC_LEN(2) || 1839 !(bh = ext3_bread (NULL, inode, 0, 0, &err))) { 1840 if (err) 1841 ext3_error(inode->i_sb, __func__, 1842 "error %d reading directory #%lu offset 0", 1843 err, inode->i_ino); 1844 else 1845 ext3_warning(inode->i_sb, __func__, 1846 "bad directory (dir #%lu) - no data block", 1847 inode->i_ino); 1848 return 1; 1849 } 1850 de = (struct ext3_dir_entry_2 *) bh->b_data; 1851 de1 = ext3_next_entry(de); 1852 if (le32_to_cpu(de->inode) != inode->i_ino || 1853 !le32_to_cpu(de1->inode) || 1854 strcmp (".", de->name) || 1855 strcmp ("..", de1->name)) { 1856 ext3_warning (inode->i_sb, "empty_dir", 1857 "bad directory (dir #%lu) - no `.' or `..'", 1858 inode->i_ino); 1859 brelse (bh); 1860 return 1; 1861 } 1862 offset = ext3_rec_len_from_disk(de->rec_len) + 1863 ext3_rec_len_from_disk(de1->rec_len); 1864 de = ext3_next_entry(de1); 1865 while (offset < inode->i_size ) { 1866 if (!bh || 1867 (void *) de >= (void *) (bh->b_data+sb->s_blocksize)) { 1868 err = 0; 1869 brelse (bh); 1870 bh = ext3_bread (NULL, inode, 1871 offset >> EXT3_BLOCK_SIZE_BITS(sb), 0, &err); 1872 if (!bh) { 1873 if (err) 1874 ext3_error(sb, __func__, 1875 "error %d reading directory" 1876 " #%lu offset %lu", 1877 err, inode->i_ino, offset); 1878 offset += sb->s_blocksize; 1879 continue; 1880 } 1881 de = (struct ext3_dir_entry_2 *) bh->b_data; 1882 } 1883 if (!ext3_check_dir_entry("empty_dir", inode, de, bh, offset)) { 1884 de = (struct ext3_dir_entry_2 *)(bh->b_data + 1885 sb->s_blocksize); 1886 offset = (offset | (sb->s_blocksize - 1)) + 1; 1887 continue; 1888 } 1889 if (le32_to_cpu(de->inode)) { 1890 brelse (bh); 1891 return 0; 1892 } 1893 offset += ext3_rec_len_from_disk(de->rec_len); 1894 de = ext3_next_entry(de); 1895 } 1896 brelse (bh); 1897 return 1; 1898} 1899 1900/* ext3_orphan_add() links an unlinked or truncated inode into a list of 1901 * such inodes, starting at the superblock, in case we crash before the 1902 * file is closed/deleted, or in case the inode truncate spans multiple 1903 * transactions and the last transaction is not recovered after a crash. 1904 * 1905 * At filesystem recovery time, we walk this list deleting unlinked 1906 * inodes and truncating linked inodes in ext3_orphan_cleanup(). 1907 */ 1908int ext3_orphan_add(handle_t *handle, struct inode *inode) 1909{ 1910 struct super_block *sb = inode->i_sb; 1911 struct ext3_iloc iloc; 1912 int err = 0, rc; 1913 1914 lock_super(sb); 1915 if (!list_empty(&EXT3_I(inode)->i_orphan)) 1916 goto out_unlock; 1917 1918 /* Orphan handling is only valid for files with data blocks 1919 * being truncated, or files being unlinked. */ 1920 1921 /* @@@ FIXME: Observation from aviro: 1922 * I think I can trigger J_ASSERT in ext3_orphan_add(). We block 1923 * here (on lock_super()), so race with ext3_link() which might bump 1924 * ->i_nlink. For, say it, character device. Not a regular file, 1925 * not a directory, not a symlink and ->i_nlink > 0. 1926 */ 1927 J_ASSERT ((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) || 1928 S_ISLNK(inode->i_mode)) || inode->i_nlink == 0); 1929 1930 BUFFER_TRACE(EXT3_SB(sb)->s_sbh, "get_write_access"); 1931 err = ext3_journal_get_write_access(handle, EXT3_SB(sb)->s_sbh); 1932 if (err) 1933 goto out_unlock; 1934 1935 err = ext3_reserve_inode_write(handle, inode, &iloc); 1936 if (err) 1937 goto out_unlock; 1938 1939 /* Insert this inode at the head of the on-disk orphan list... */ 1940 NEXT_ORPHAN(inode) = le32_to_cpu(EXT3_SB(sb)->s_es->s_last_orphan); 1941 EXT3_SB(sb)->s_es->s_last_orphan = cpu_to_le32(inode->i_ino); 1942 err = ext3_journal_dirty_metadata(handle, EXT3_SB(sb)->s_sbh); 1943 rc = ext3_mark_iloc_dirty(handle, inode, &iloc); 1944 if (!err) 1945 err = rc; 1946 1947 /* Only add to the head of the in-memory list if all the 1948 * previous operations succeeded. If the orphan_add is going to 1949 * fail (possibly taking the journal offline), we can't risk 1950 * leaving the inode on the orphan list: stray orphan-list 1951 * entries can cause panics at unmount time. 1952 * 1953 * This is safe: on error we're going to ignore the orphan list 1954 * anyway on the next recovery. */ 1955 if (!err) 1956 list_add(&EXT3_I(inode)->i_orphan, &EXT3_SB(sb)->s_orphan); 1957 1958 jbd_debug(4, "superblock will point to %lu\n", inode->i_ino); 1959 jbd_debug(4, "orphan inode %lu will point to %d\n", 1960 inode->i_ino, NEXT_ORPHAN(inode)); 1961out_unlock: 1962 unlock_super(sb); 1963 ext3_std_error(inode->i_sb, err); 1964 return err; 1965} 1966 1967/* 1968 * ext3_orphan_del() removes an unlinked or truncated inode from the list 1969 * of such inodes stored on disk, because it is finally being cleaned up. 1970 */ 1971int ext3_orphan_del(handle_t *handle, struct inode *inode) 1972{ 1973 struct list_head *prev; 1974 struct ext3_inode_info *ei = EXT3_I(inode); 1975 struct ext3_sb_info *sbi; 1976 unsigned long ino_next; 1977 struct ext3_iloc iloc; 1978 int err = 0; 1979 1980 lock_super(inode->i_sb); 1981 if (list_empty(&ei->i_orphan)) { 1982 unlock_super(inode->i_sb); 1983 return 0; 1984 } 1985 1986 ino_next = NEXT_ORPHAN(inode); 1987 prev = ei->i_orphan.prev; 1988 sbi = EXT3_SB(inode->i_sb); 1989 1990 jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino); 1991 1992 list_del_init(&ei->i_orphan); 1993 1994 /* If we're on an error path, we may not have a valid 1995 * transaction handle with which to update the orphan list on 1996 * disk, but we still need to remove the inode from the linked 1997 * list in memory. */ 1998 if (!handle) 1999 goto out; 2000 2001 err = ext3_reserve_inode_write(handle, inode, &iloc); 2002 if (err) 2003 goto out_err; 2004 2005 if (prev == &sbi->s_orphan) { 2006 jbd_debug(4, "superblock will point to %lu\n", ino_next); 2007 BUFFER_TRACE(sbi->s_sbh, "get_write_access"); 2008 err = ext3_journal_get_write_access(handle, sbi->s_sbh); 2009 if (err) 2010 goto out_brelse; 2011 sbi->s_es->s_last_orphan = cpu_to_le32(ino_next); 2012 err = ext3_journal_dirty_metadata(handle, sbi->s_sbh); 2013 } else { 2014 struct ext3_iloc iloc2; 2015 struct inode *i_prev = 2016 &list_entry(prev, struct ext3_inode_info, i_orphan)->vfs_inode; 2017 2018 jbd_debug(4, "orphan inode %lu will point to %lu\n", 2019 i_prev->i_ino, ino_next); 2020 err = ext3_reserve_inode_write(handle, i_prev, &iloc2); 2021 if (err) 2022 goto out_brelse; 2023 NEXT_ORPHAN(i_prev) = ino_next; 2024 err = ext3_mark_iloc_dirty(handle, i_prev, &iloc2); 2025 } 2026 if (err) 2027 goto out_brelse; 2028 NEXT_ORPHAN(inode) = 0; 2029 err = ext3_mark_iloc_dirty(handle, inode, &iloc); 2030 2031out_err: 2032 ext3_std_error(inode->i_sb, err); 2033out: 2034 unlock_super(inode->i_sb); 2035 return err; 2036 2037out_brelse: 2038 brelse(iloc.bh); 2039 goto out_err; 2040} 2041 2042static int ext3_rmdir (struct inode * dir, struct dentry *dentry) 2043{ 2044 int retval; 2045 struct inode * inode; 2046 struct buffer_head * bh; 2047 struct ext3_dir_entry_2 * de; 2048 handle_t *handle; 2049 2050 /* Initialize quotas before so that eventual writes go in 2051 * separate transaction */ 2052 vfs_dq_init(dentry->d_inode); 2053 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb)); 2054 if (IS_ERR(handle)) 2055 return PTR_ERR(handle); 2056 2057 retval = -ENOENT; 2058 bh = ext3_find_entry(dir, &dentry->d_name, &de); 2059 if (!bh) 2060 goto end_rmdir; 2061 2062 if (IS_DIRSYNC(dir)) 2063 handle->h_sync = 1; 2064 2065 inode = dentry->d_inode; 2066 2067 retval = -EIO; 2068 if (le32_to_cpu(de->inode) != inode->i_ino) 2069 goto end_rmdir; 2070 2071 retval = -ENOTEMPTY; 2072 if (!empty_dir (inode)) 2073 goto end_rmdir; 2074 2075 retval = ext3_delete_entry(handle, dir, de, bh); 2076 if (retval) 2077 goto end_rmdir; 2078 if (inode->i_nlink != 2) 2079 ext3_warning (inode->i_sb, "ext3_rmdir", 2080 "empty directory has nlink!=2 (%d)", 2081 inode->i_nlink); 2082 inode->i_version++; 2083 clear_nlink(inode); 2084 /* There's no need to set i_disksize: the fact that i_nlink is 2085 * zero will ensure that the right thing happens during any 2086 * recovery. */ 2087 inode->i_size = 0; 2088 ext3_orphan_add(handle, inode); 2089 inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC; 2090 ext3_mark_inode_dirty(handle, inode); 2091 drop_nlink(dir); 2092 ext3_update_dx_flag(dir); 2093 ext3_mark_inode_dirty(handle, dir); 2094 2095end_rmdir: 2096 ext3_journal_stop(handle); 2097 brelse (bh); 2098 return retval; 2099} 2100 2101static int ext3_unlink(struct inode * dir, struct dentry *dentry) 2102{ 2103 int retval; 2104 struct inode * inode; 2105 struct buffer_head * bh; 2106 struct ext3_dir_entry_2 * de; 2107 handle_t *handle; 2108 2109 /* Initialize quotas before so that eventual writes go 2110 * in separate transaction */ 2111 vfs_dq_init(dentry->d_inode); 2112 handle = ext3_journal_start(dir, EXT3_DELETE_TRANS_BLOCKS(dir->i_sb)); 2113 if (IS_ERR(handle)) 2114 return PTR_ERR(handle); 2115 2116 if (IS_DIRSYNC(dir)) 2117 handle->h_sync = 1; 2118 2119 retval = -ENOENT; 2120 bh = ext3_find_entry(dir, &dentry->d_name, &de); 2121 if (!bh) 2122 goto end_unlink; 2123 2124 inode = dentry->d_inode; 2125 2126 retval = -EIO; 2127 if (le32_to_cpu(de->inode) != inode->i_ino) 2128 goto end_unlink; 2129 2130 if (!inode->i_nlink) { 2131 ext3_warning (inode->i_sb, "ext3_unlink", 2132 "Deleting nonexistent file (%lu), %d", 2133 inode->i_ino, inode->i_nlink); 2134 inode->i_nlink = 1; 2135 } 2136 retval = ext3_delete_entry(handle, dir, de, bh); 2137 if (retval) 2138 goto end_unlink; 2139 dir->i_ctime = dir->i_mtime = CURRENT_TIME_SEC; 2140 ext3_update_dx_flag(dir); 2141 ext3_mark_inode_dirty(handle, dir); 2142 drop_nlink(inode); 2143 if (!inode->i_nlink) 2144 ext3_orphan_add(handle, inode); 2145 inode->i_ctime = dir->i_ctime; 2146 ext3_mark_inode_dirty(handle, inode); 2147 retval = 0; 2148 2149end_unlink: 2150 ext3_journal_stop(handle); 2151 brelse (bh); 2152 return retval; 2153} 2154 2155static int ext3_symlink (struct inode * dir, 2156 struct dentry *dentry, const char * symname) 2157{ 2158 handle_t *handle; 2159 struct inode * inode; 2160 int l, err, retries = 0; 2161 2162 l = strlen(symname)+1; 2163 if (l > dir->i_sb->s_blocksize) 2164 return -ENAMETOOLONG; 2165 2166retry: 2167 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) + 2168 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 5 + 2169 2*EXT3_QUOTA_INIT_BLOCKS(dir->i_sb)); 2170 if (IS_ERR(handle)) 2171 return PTR_ERR(handle); 2172 2173 if (IS_DIRSYNC(dir)) 2174 handle->h_sync = 1; 2175 2176 inode = ext3_new_inode (handle, dir, S_IFLNK|S_IRWXUGO); 2177 err = PTR_ERR(inode); 2178 if (IS_ERR(inode)) 2179 goto out_stop; 2180 2181 if (l > sizeof (EXT3_I(inode)->i_data)) { 2182 inode->i_op = &ext3_symlink_inode_operations; 2183 ext3_set_aops(inode); 2184 /* 2185 * page_symlink() calls into ext3_prepare/commit_write. 2186 * We have a transaction open. All is sweetness. It also sets 2187 * i_size in generic_commit_write(). 2188 */ 2189 err = __page_symlink(inode, symname, l, 1); 2190 if (err) { 2191 drop_nlink(inode); 2192 unlock_new_inode(inode); 2193 ext3_mark_inode_dirty(handle, inode); 2194 iput (inode); 2195 goto out_stop; 2196 } 2197 } else { 2198 inode->i_op = &ext3_fast_symlink_inode_operations; 2199 memcpy((char*)&EXT3_I(inode)->i_data,symname,l); 2200 inode->i_size = l-1; 2201 } 2202 EXT3_I(inode)->i_disksize = inode->i_size; 2203 err = ext3_add_nondir(handle, dentry, inode); 2204out_stop: 2205 ext3_journal_stop(handle); 2206 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries)) 2207 goto retry; 2208 return err; 2209} 2210 2211static int ext3_link (struct dentry * old_dentry, 2212 struct inode * dir, struct dentry *dentry) 2213{ 2214 handle_t *handle; 2215 struct inode *inode = old_dentry->d_inode; 2216 int err, retries = 0; 2217 2218 if (inode->i_nlink >= EXT3_LINK_MAX) 2219 return -EMLINK; 2220 /* 2221 * Return -ENOENT if we've raced with unlink and i_nlink is 0. Doing 2222 * otherwise has the potential to corrupt the orphan inode list. 2223 */ 2224 if (inode->i_nlink == 0) 2225 return -ENOENT; 2226 2227retry: 2228 handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS(dir->i_sb) + 2229 EXT3_INDEX_EXTRA_TRANS_BLOCKS); 2230 if (IS_ERR(handle)) 2231 return PTR_ERR(handle); 2232 2233 if (IS_DIRSYNC(dir)) 2234 handle->h_sync = 1; 2235 2236 inode->i_ctime = CURRENT_TIME_SEC; 2237 inc_nlink(inode); 2238 atomic_inc(&inode->i_count); 2239 2240 err = ext3_add_entry(handle, dentry, inode); 2241 if (!err) { 2242 ext3_mark_inode_dirty(handle, inode); 2243 d_instantiate(dentry, inode); 2244 } else { 2245 drop_nlink(inode); 2246 iput(inode); 2247 } 2248 ext3_journal_stop(handle); 2249 if (err == -ENOSPC && ext3_should_retry_alloc(dir->i_sb, &retries)) 2250 goto retry; 2251 return err; 2252} 2253 2254#define PARENT_INO(buffer) \ 2255 (ext3_next_entry((struct ext3_dir_entry_2 *)(buffer))->inode) 2256 2257/* 2258 * Anybody can rename anything with this: the permission checks are left to the 2259 * higher-level routines. 2260 */ 2261static int ext3_rename (struct inode * old_dir, struct dentry *old_dentry, 2262 struct inode * new_dir,struct dentry *new_dentry) 2263{ 2264 handle_t *handle; 2265 struct inode * old_inode, * new_inode; 2266 struct buffer_head * old_bh, * new_bh, * dir_bh; 2267 struct ext3_dir_entry_2 * old_de, * new_de; 2268 int retval; 2269 2270 old_bh = new_bh = dir_bh = NULL; 2271 2272 /* Initialize quotas before so that eventual writes go 2273 * in separate transaction */ 2274 if (new_dentry->d_inode) 2275 vfs_dq_init(new_dentry->d_inode); 2276 handle = ext3_journal_start(old_dir, 2 * 2277 EXT3_DATA_TRANS_BLOCKS(old_dir->i_sb) + 2278 EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2); 2279 if (IS_ERR(handle)) 2280 return PTR_ERR(handle); 2281 2282 if (IS_DIRSYNC(old_dir) || IS_DIRSYNC(new_dir)) 2283 handle->h_sync = 1; 2284 2285 old_bh = ext3_find_entry(old_dir, &old_dentry->d_name, &old_de); 2286 /* 2287 * Check for inode number is _not_ due to possible IO errors. 2288 * We might rmdir the source, keep it as pwd of some process 2289 * and merrily kill the link to whatever was created under the 2290 * same name. Goodbye sticky bit ;-< 2291 */ 2292 old_inode = old_dentry->d_inode; 2293 retval = -ENOENT; 2294 if (!old_bh || le32_to_cpu(old_de->inode) != old_inode->i_ino) 2295 goto end_rename; 2296 2297 new_inode = new_dentry->d_inode; 2298 new_bh = ext3_find_entry(new_dir, &new_dentry->d_name, &new_de); 2299 if (new_bh) { 2300 if (!new_inode) { 2301 brelse (new_bh); 2302 new_bh = NULL; 2303 } 2304 } 2305 if (S_ISDIR(old_inode->i_mode)) { 2306 if (new_inode) { 2307 retval = -ENOTEMPTY; 2308 if (!empty_dir (new_inode)) 2309 goto end_rename; 2310 } 2311 retval = -EIO; 2312 dir_bh = ext3_bread (handle, old_inode, 0, 0, &retval); 2313 if (!dir_bh) 2314 goto end_rename; 2315 if (le32_to_cpu(PARENT_INO(dir_bh->b_data)) != old_dir->i_ino) 2316 goto end_rename; 2317 retval = -EMLINK; 2318 if (!new_inode && new_dir!=old_dir && 2319 new_dir->i_nlink >= EXT3_LINK_MAX) 2320 goto end_rename; 2321 } 2322 if (!new_bh) { 2323 retval = ext3_add_entry (handle, new_dentry, old_inode); 2324 if (retval) 2325 goto end_rename; 2326 } else { 2327 BUFFER_TRACE(new_bh, "get write access"); 2328 ext3_journal_get_write_access(handle, new_bh); 2329 new_de->inode = cpu_to_le32(old_inode->i_ino); 2330 if (EXT3_HAS_INCOMPAT_FEATURE(new_dir->i_sb, 2331 EXT3_FEATURE_INCOMPAT_FILETYPE)) 2332 new_de->file_type = old_de->file_type; 2333 new_dir->i_version++; 2334 new_dir->i_ctime = new_dir->i_mtime = CURRENT_TIME_SEC; 2335 ext3_mark_inode_dirty(handle, new_dir); 2336 BUFFER_TRACE(new_bh, "call ext3_journal_dirty_metadata"); 2337 ext3_journal_dirty_metadata(handle, new_bh); 2338 brelse(new_bh); 2339 new_bh = NULL; 2340 } 2341 2342 /* 2343 * Like most other Unix systems, set the ctime for inodes on a 2344 * rename. 2345 */ 2346 old_inode->i_ctime = CURRENT_TIME_SEC; 2347 ext3_mark_inode_dirty(handle, old_inode); 2348 2349 /* 2350 * ok, that's it 2351 */ 2352 if (le32_to_cpu(old_de->inode) != old_inode->i_ino || 2353 old_de->name_len != old_dentry->d_name.len || 2354 strncmp(old_de->name, old_dentry->d_name.name, old_de->name_len) || 2355 (retval = ext3_delete_entry(handle, old_dir, 2356 old_de, old_bh)) == -ENOENT) { 2357 /* old_de could have moved from under us during htree split, so 2358 * make sure that we are deleting the right entry. We might 2359 * also be pointing to a stale entry in the unused part of 2360 * old_bh so just checking inum and the name isn't enough. */ 2361 struct buffer_head *old_bh2; 2362 struct ext3_dir_entry_2 *old_de2; 2363 2364 old_bh2 = ext3_find_entry(old_dir, &old_dentry->d_name, 2365 &old_de2); 2366 if (old_bh2) { 2367 retval = ext3_delete_entry(handle, old_dir, 2368 old_de2, old_bh2); 2369 brelse(old_bh2); 2370 } 2371 } 2372 if (retval) { 2373 ext3_warning(old_dir->i_sb, "ext3_rename", 2374 "Deleting old file (%lu), %d, error=%d", 2375 old_dir->i_ino, old_dir->i_nlink, retval); 2376 } 2377 2378 if (new_inode) { 2379 drop_nlink(new_inode); 2380 new_inode->i_ctime = CURRENT_TIME_SEC; 2381 } 2382 old_dir->i_ctime = old_dir->i_mtime = CURRENT_TIME_SEC; 2383 ext3_update_dx_flag(old_dir); 2384 if (dir_bh) { 2385 BUFFER_TRACE(dir_bh, "get_write_access"); 2386 ext3_journal_get_write_access(handle, dir_bh); 2387 PARENT_INO(dir_bh->b_data) = cpu_to_le32(new_dir->i_ino); 2388 BUFFER_TRACE(dir_bh, "call ext3_journal_dirty_metadata"); 2389 ext3_journal_dirty_metadata(handle, dir_bh); 2390 drop_nlink(old_dir); 2391 if (new_inode) { 2392 drop_nlink(new_inode); 2393 } else { 2394 inc_nlink(new_dir); 2395 ext3_update_dx_flag(new_dir); 2396 ext3_mark_inode_dirty(handle, new_dir); 2397 } 2398 } 2399 ext3_mark_inode_dirty(handle, old_dir); 2400 if (new_inode) { 2401 ext3_mark_inode_dirty(handle, new_inode); 2402 if (!new_inode->i_nlink) 2403 ext3_orphan_add(handle, new_inode); 2404 } 2405 retval = 0; 2406 2407end_rename: 2408 brelse (dir_bh); 2409 brelse (old_bh); 2410 brelse (new_bh); 2411 ext3_journal_stop(handle); 2412 return retval; 2413} 2414 2415/* 2416 * directories can handle most operations... 2417 */ 2418const struct inode_operations ext3_dir_inode_operations = { 2419 .create = ext3_create, 2420 .lookup = ext3_lookup, 2421 .link = ext3_link, 2422 .unlink = ext3_unlink, 2423 .symlink = ext3_symlink, 2424 .mkdir = ext3_mkdir, 2425 .rmdir = ext3_rmdir, 2426 .mknod = ext3_mknod, 2427 .rename = ext3_rename, 2428 .setattr = ext3_setattr, 2429#ifdef CONFIG_EXT3_FS_XATTR 2430 .setxattr = generic_setxattr, 2431 .getxattr = generic_getxattr, 2432 .listxattr = ext3_listxattr, 2433 .removexattr = generic_removexattr, 2434#endif 2435 .permission = ext3_permission, 2436}; 2437 2438const struct inode_operations ext3_special_inode_operations = { 2439 .setattr = ext3_setattr, 2440#ifdef CONFIG_EXT3_FS_XATTR 2441 .setxattr = generic_setxattr, 2442 .getxattr = generic_getxattr, 2443 .listxattr = ext3_listxattr, 2444 .removexattr = generic_removexattr, 2445#endif 2446 .permission = ext3_permission, 2447}; 2448