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