fs/ext4/namei.c

   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 #include <trace/events/ext4.h>
  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
  51 static struct buffer_head *ext4_append(handle_t *handle,
  52                                         struct inode *inode,
  53                                         ext4_lblk_t *block)
  54 {
  55         struct buffer_head *bh;
  56         int err;
  57
  58         if (unlikely(EXT4_SB(inode->i_sb)->s_max_dir_size_kb &&
  59                      ((inode->i_size >> 10) >=
  60                       EXT4_SB(inode->i_sb)->s_max_dir_size_kb)))
  61                 return ERR_PTR(-ENOSPC);
  62
  63         *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
  64
  65         bh = ext4_bread(handle, inode, *block, 1);
  66         if (IS_ERR(bh))
  67                 return bh;
  68         inode->i_size += inode->i_sb->s_blocksize;
  69         EXT4_I(inode)->i_disksize = inode->i_size;
  70         BUFFER_TRACE(bh, "get_write_access");
  71         err = ext4_journal_get_write_access(handle, bh);
  72         if (err) {
  73                 brelse(bh);
  74                 ext4_std_error(inode->i_sb, err);
  75                 return ERR_PTR(err);
  76         }
  77         return bh;
  78 }
  79
  80 static int ext4_dx_csum_verify(struct inode *inode,
  81                                struct ext4_dir_entry *dirent);
  82
  83 typedef enum {
  84         EITHER, INDEX, DIRENT
  85 } dirblock_type_t;
  86
  87 #define ext4_read_dirblock(inode, block, type) \
  88         __ext4_read_dirblock((inode), (block), (type), __LINE__)
  89
  90 static struct buffer_head *__ext4_read_dirblock(struct inode *inode,
  91                                               ext4_lblk_t block,
  92                                               dirblock_type_t type,
  93                                               unsigned int line)
  94 {
  95         struct buffer_head *bh;
  96         struct ext4_dir_entry *dirent;
  97         int is_dx_block = 0;
  98
  99         bh = ext4_bread(NULL, inode, block, 0);
 100         if (IS_ERR(bh)) {
 101                 __ext4_warning(inode->i_sb, __func__, line,
 102                                "error %ld reading directory block "
 103                                "(ino %lu, block %lu)", PTR_ERR(bh), inode->i_ino,
 104                                (unsigned long) block);
 105
 106                 return bh;
 107         }
 108         if (!bh) {
 109                 ext4_error_inode(inode, __func__, line, block, "Directory hole found");
 110                 return ERR_PTR(-EIO);
 111         }
 112         dirent = (struct ext4_dir_entry *) bh->b_data;
 113         /* Determine whether or not we have an index block */
 114         if (is_dx(inode)) {
 115                 if (block == 0)
 116                         is_dx_block = 1;
 117                 else if (ext4_rec_len_from_disk(dirent->rec_len,
 118                                                 inode->i_sb->s_blocksize) ==
 119                          inode->i_sb->s_blocksize)
 120                         is_dx_block = 1;
 121         }
 122         if (!is_dx_block && type == INDEX) {
 123                 ext4_error_inode(inode, __func__, line, block,
 124                        "directory leaf block found instead of index block");
 125                 return ERR_PTR(-EIO);
 126         }
 127         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
 128                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM) ||
 129             buffer_verified(bh))
 130                 return bh;
 131
 132         /*
 133          * An empty leaf block can get mistaken for a index block; for
 134          * this reason, we can only check the index checksum when the
 135          * caller is sure it should be an index block.
 136          */
 137         if (is_dx_block && type == INDEX) {
 138                 if (ext4_dx_csum_verify(inode, dirent))
 139                         set_buffer_verified(bh);
 140                 else {
 141                         ext4_error_inode(inode, __func__, line, block,
 142                                 "Directory index failed checksum");
 143                         brelse(bh);
 144                         return ERR_PTR(-EIO);
 145                 }
 146         }
 147         if (!is_dx_block) {
 148                 if (ext4_dirent_csum_verify(inode, dirent))
 149                         set_buffer_verified(bh);
 150                 else {
 151                         ext4_error_inode(inode, __func__, line, block,
 152                                 "Directory block failed checksum");
 153                         brelse(bh);
 154                         return ERR_PTR(-EIO);
 155                 }
 156         }
 157         return bh;
 158 }
 159
 160 #ifndef assert
 161 #define assert(test) J_ASSERT(test)
 162 #endif
 163
 164 #ifdef DX_DEBUG
 165 #define dxtrace(command) command
 166 #else
 167 #define dxtrace(command)
 168 #endif
 169
 170 struct fake_dirent
 171 {
 172         __le32 inode;
 173         __le16 rec_len;
 174         u8 name_len;
 175         u8 file_type;
 176 };
 177
 178 struct dx_countlimit
 179 {
 180         __le16 limit;
 181         __le16 count;
 182 };
 183
 184 struct dx_entry
 185 {
 186         __le32 hash;
 187         __le32 block;
 188 };
 189
 190 /*
 191  * dx_root_info is laid out so that if it should somehow get overlaid by a
 192  * dirent the two low bits of the hash version will be zero.  Therefore, the
 193  * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
 194  */
 195
 196 struct dx_root
 197 {
 198         struct fake_dirent dot;
 199         char dot_name[4];
 200         struct fake_dirent dotdot;
 201         char dotdot_name[4];
 202         struct dx_root_info
 203         {
 204                 __le32 reserved_zero;
 205                 u8 hash_version;
 206                 u8 info_length; /* 8 */
 207                 u8 indirect_levels;
 208                 u8 unused_flags;
 209         }
 210         info;
 211         struct dx_entry entries[0];
 212 };
 213
 214 struct dx_node
 215 {
 216         struct fake_dirent fake;
 217         struct dx_entry entries[0];
 218 };
 219
 220
 221 struct dx_frame
 222 {
 223         struct buffer_head *bh;
 224         struct dx_entry *entries;
 225         struct dx_entry *at;
 226 };
 227
 228 struct dx_map_entry
 229 {
 230         u32 hash;
 231         u16 offs;
 232         u16 size;
 233 };
 234
 235 /*
 236  * This goes at the end of each htree block.
 237  */
 238 struct dx_tail {
 239         u32 dt_reserved;
 240         __le32 dt_checksum;     /* crc32c(uuid+inum+dirblock) */
 241 };
 242
 243 static inline ext4_lblk_t dx_get_block(struct dx_entry *entry);
 244 static void dx_set_block(struct dx_entry *entry, ext4_lblk_t value);
 245 static inline unsigned dx_get_hash(struct dx_entry *entry);
 246 static void dx_set_hash(struct dx_entry *entry, unsigned value);
 247 static unsigned dx_get_count(struct dx_entry *entries);
 248 static unsigned dx_get_limit(struct dx_entry *entries);
 249 static void dx_set_count(struct dx_entry *entries, unsigned value);
 250 static void dx_set_limit(struct dx_entry *entries, unsigned value);
 251 static unsigned dx_root_limit(struct inode *dir, unsigned infosize);
 252 static unsigned dx_node_limit(struct inode *dir);
 253 static struct dx_frame *dx_probe(const struct qstr *d_name,
 254                                  struct inode *dir,
 255                                  struct dx_hash_info *hinfo,
 256                                  struct dx_frame *frame);
 257 static void dx_release(struct dx_frame *frames);
 258 static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
 259                        struct dx_hash_info *hinfo, struct dx_map_entry map[]);
 260 static void dx_sort_map(struct dx_map_entry *map, unsigned count);
 261 static struct ext4_dir_entry_2 *dx_move_dirents(char *from, char *to,
 262                 struct dx_map_entry *offsets, int count, unsigned blocksize);
 263 static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize);
 264 static void dx_insert_block(struct dx_frame *frame,
 265                                         u32 hash, ext4_lblk_t block);
 266 static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 267                                  struct dx_frame *frame,
 268                                  struct dx_frame *frames,
 269                                  __u32 *start_hash);
 270 static struct buffer_head * ext4_dx_find_entry(struct inode *dir,
 271                 const struct qstr *d_name,
 272                 struct ext4_dir_entry_2 **res_dir);
 273 static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
 274                              struct inode *inode);
 275
 276 /* checksumming functions */
 277 void initialize_dirent_tail(struct ext4_dir_entry_tail *t,
 278                             unsigned int blocksize)
 279 {
 280         memset(t, 0, sizeof(struct ext4_dir_entry_tail));
 281         t->det_rec_len = ext4_rec_len_to_disk(
 282                         sizeof(struct ext4_dir_entry_tail), blocksize);
 283         t->det_reserved_ft = EXT4_FT_DIR_CSUM;
 284 }
 285
 286 /* Walk through a dirent block to find a checksum "dirent" at the tail */
 287 static struct ext4_dir_entry_tail *get_dirent_tail(struct inode *inode,
 288                                                    struct ext4_dir_entry *de)
 289 {
 290         struct ext4_dir_entry_tail *t;
 291
 292 #ifdef PARANOID
 293         struct ext4_dir_entry *d, *top;
 294
 295         d = de;
 296         top = (struct ext4_dir_entry *)(((void *)de) +
 297                 (EXT4_BLOCK_SIZE(inode->i_sb) -
 298                 sizeof(struct ext4_dir_entry_tail)));
 299         while (d < top && d->rec_len)
 300                 d = (struct ext4_dir_entry *)(((void *)d) +
 301                     le16_to_cpu(d->rec_len));
 302
 303         if (d != top)
 304                 return NULL;
 305
 306         t = (struct ext4_dir_entry_tail *)d;
 307 #else
 308         t = EXT4_DIRENT_TAIL(de, EXT4_BLOCK_SIZE(inode->i_sb));
 309 #endif
 310
 311         if (t->det_reserved_zero1 ||
 312             le16_to_cpu(t->det_rec_len) != sizeof(struct ext4_dir_entry_tail) ||
 313             t->det_reserved_zero2 ||
 314             t->det_reserved_ft != EXT4_FT_DIR_CSUM)
 315                 return NULL;
 316
 317         return t;
 318 }
 319
 320 static __le32 ext4_dirent_csum(struct inode *inode,
 321                                struct ext4_dir_entry *dirent, int size)
 322 {
 323         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 324         struct ext4_inode_info *ei = EXT4_I(inode);
 325         __u32 csum;
 326
 327         csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
 328         return cpu_to_le32(csum);
 329 }
 330
 331 static void warn_no_space_for_csum(struct inode *inode)
 332 {
 333         ext4_warning(inode->i_sb, "no space in directory inode %lu leaf for "
 334                      "checksum.  Please run e2fsck -D.", inode->i_ino);
 335 }
 336
 337 int ext4_dirent_csum_verify(struct inode *inode, struct ext4_dir_entry *dirent)
 338 {
 339         struct ext4_dir_entry_tail *t;
 340
 341         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
 342                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 343                 return 1;
 344
 345         t = get_dirent_tail(inode, dirent);
 346         if (!t) {
 347                 warn_no_space_for_csum(inode);
 348                 return 0;
 349         }
 350
 351         if (t->det_checksum != ext4_dirent_csum(inode, dirent,
 352                                                 (void *)t - (void *)dirent))
 353                 return 0;
 354
 355         return 1;
 356 }
 357
 358 static void ext4_dirent_csum_set(struct inode *inode,
 359                                  struct ext4_dir_entry *dirent)
 360 {
 361         struct ext4_dir_entry_tail *t;
 362
 363         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
 364                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 365                 return;
 366
 367         t = get_dirent_tail(inode, dirent);
 368         if (!t) {
 369                 warn_no_space_for_csum(inode);
 370                 return;
 371         }
 372
 373         t->det_checksum = ext4_dirent_csum(inode, dirent,
 374                                            (void *)t - (void *)dirent);
 375 }
 376
 377 int ext4_handle_dirty_dirent_node(handle_t *handle,
 378                                   struct inode *inode,
 379                                   struct buffer_head *bh)
 380 {
 381         ext4_dirent_csum_set(inode, (struct ext4_dir_entry *)bh->b_data);
 382         return ext4_handle_dirty_metadata(handle, inode, bh);
 383 }
 384
 385 static struct dx_countlimit *get_dx_countlimit(struct inode *inode,
 386                                                struct ext4_dir_entry *dirent,
 387                                                int *offset)
 388 {
 389         struct ext4_dir_entry *dp;
 390         struct dx_root_info *root;
 391         int count_offset;
 392
 393         if (le16_to_cpu(dirent->rec_len) == EXT4_BLOCK_SIZE(inode->i_sb))
 394                 count_offset = 8;
 395         else if (le16_to_cpu(dirent->rec_len) == 12) {
 396                 dp = (struct ext4_dir_entry *)(((void *)dirent) + 12);
 397                 if (le16_to_cpu(dp->rec_len) !=
 398                     EXT4_BLOCK_SIZE(inode->i_sb) - 12)
 399                         return NULL;
 400                 root = (struct dx_root_info *)(((void *)dp + 12));
 401                 if (root->reserved_zero ||
 402                     root->info_length != sizeof(struct dx_root_info))
 403                         return NULL;
 404                 count_offset = 32;
 405         } else
 406                 return NULL;
 407
 408         if (offset)
 409                 *offset = count_offset;
 410         return (struct dx_countlimit *)(((void *)dirent) + count_offset);
 411 }
 412
 413 static __le32 ext4_dx_csum(struct inode *inode, struct ext4_dir_entry *dirent,
 414                            int count_offset, int count, struct dx_tail *t)
 415 {
 416         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
 417         struct ext4_inode_info *ei = EXT4_I(inode);
 418         __u32 csum;
 419         __le32 save_csum;
 420         int size;
 421
 422         size = count_offset + (count * sizeof(struct dx_entry));
 423         save_csum = t->dt_checksum;
 424         t->dt_checksum = 0;
 425         csum = ext4_chksum(sbi, ei->i_csum_seed, (__u8 *)dirent, size);
 426         csum = ext4_chksum(sbi, csum, (__u8 *)t, sizeof(struct dx_tail));
 427         t->dt_checksum = save_csum;
 428
 429         return cpu_to_le32(csum);
 430 }
 431
 432 static int ext4_dx_csum_verify(struct inode *inode,
 433                                struct ext4_dir_entry *dirent)
 434 {
 435         struct dx_countlimit *c;
 436         struct dx_tail *t;
 437         int count_offset, limit, count;
 438
 439         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
 440                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 441                 return 1;
 442
 443         c = get_dx_countlimit(inode, dirent, &count_offset);
 444         if (!c) {
 445                 EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
 446                 return 1;
 447         }
 448         limit = le16_to_cpu(c->limit);
 449         count = le16_to_cpu(c->count);
 450         if (count_offset + (limit * sizeof(struct dx_entry)) >
 451             EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
 452                 warn_no_space_for_csum(inode);
 453                 return 1;
 454         }
 455         t = (struct dx_tail *)(((struct dx_entry *)c) + limit);
 456
 457         if (t->dt_checksum != ext4_dx_csum(inode, dirent, count_offset,
 458                                             count, t))
 459                 return 0;
 460         return 1;
 461 }
 462
 463 static void ext4_dx_csum_set(struct inode *inode, struct ext4_dir_entry *dirent)
 464 {
 465         struct dx_countlimit *c;
 466         struct dx_tail *t;
 467         int count_offset, limit, count;
 468
 469         if (!EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
 470                                         EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 471                 return;
 472
 473         c = get_dx_countlimit(inode, dirent, &count_offset);
 474         if (!c) {
 475                 EXT4_ERROR_INODE(inode, "dir seems corrupt?  Run e2fsck -D.");
 476                 return;
 477         }
 478         limit = le16_to_cpu(c->limit);
 479         count = le16_to_cpu(c->count);
 480         if (count_offset + (limit * sizeof(struct dx_entry)) >
 481             EXT4_BLOCK_SIZE(inode->i_sb) - sizeof(struct dx_tail)) {
 482                 warn_no_space_for_csum(inode);
 483                 return;
 484         }
 485         t = (struct dx_tail *)(((struct dx_entry *)c) + limit);
 486
 487         t->dt_checksum = ext4_dx_csum(inode, dirent, count_offset, count, t);
 488 }
 489
 490 static inline int ext4_handle_dirty_dx_node(handle_t *handle,
 491                                             struct inode *inode,
 492                                             struct buffer_head *bh)
 493 {
 494         ext4_dx_csum_set(inode, (struct ext4_dir_entry *)bh->b_data);
 495         return ext4_handle_dirty_metadata(handle, inode, bh);
 496 }
 497
 498 /*
 499  * p is at least 6 bytes before the end of page
 500  */
 501 static inline struct ext4_dir_entry_2 *
 502 ext4_next_entry(struct ext4_dir_entry_2 *p, unsigned long blocksize)
 503 {
 504         return (struct ext4_dir_entry_2 *)((char *)p +
 505                 ext4_rec_len_from_disk(p->rec_len, blocksize));
 506 }
 507
 508 /*
 509  * Future: use high four bits of block for coalesce-on-delete flags
 510  * Mask them off for now.
 511  */
 512
 513 static inline ext4_lblk_t dx_get_block(struct dx_entry *entry)
 514 {
 515         return le32_to_cpu(entry->block) & 0x00ffffff;
 516 }
 517
 518 static inline void dx_set_block(struct dx_entry *entry, ext4_lblk_t value)
 519 {
 520         entry->block = cpu_to_le32(value);
 521 }
 522
 523 static inline unsigned dx_get_hash(struct dx_entry *entry)
 524 {
 525         return le32_to_cpu(entry->hash);
 526 }
 527
 528 static inline void dx_set_hash(struct dx_entry *entry, unsigned value)
 529 {
 530         entry->hash = cpu_to_le32(value);
 531 }
 532
 533 static inline unsigned dx_get_count(struct dx_entry *entries)
 534 {
 535         return le16_to_cpu(((struct dx_countlimit *) entries)->count);
 536 }
 537
 538 static inline unsigned dx_get_limit(struct dx_entry *entries)
 539 {
 540         return le16_to_cpu(((struct dx_countlimit *) entries)->limit);
 541 }
 542
 543 static inline void dx_set_count(struct dx_entry *entries, unsigned value)
 544 {
 545         ((struct dx_countlimit *) entries)->count = cpu_to_le16(value);
 546 }
 547
 548 static inline void dx_set_limit(struct dx_entry *entries, unsigned value)
 549 {
 550         ((struct dx_countlimit *) entries)->limit = cpu_to_le16(value);
 551 }
 552
 553 static inline unsigned dx_root_limit(struct inode *dir, unsigned infosize)
 554 {
 555         unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(1) -
 556                 EXT4_DIR_REC_LEN(2) - infosize;
 557
 558         if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
 559                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 560                 entry_space -= sizeof(struct dx_tail);
 561         return entry_space / sizeof(struct dx_entry);
 562 }
 563
 564 static inline unsigned dx_node_limit(struct inode *dir)
 565 {
 566         unsigned entry_space = dir->i_sb->s_blocksize - EXT4_DIR_REC_LEN(0);
 567
 568         if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
 569                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
 570                 entry_space -= sizeof(struct dx_tail);
 571         return entry_space / sizeof(struct dx_entry);
 572 }
 573
 574 /*
 575  * Debug
 576  */
 577 #ifdef DX_DEBUG
 578 static void dx_show_index(char * label, struct dx_entry *entries)
 579 {
 580         int i, n = dx_get_count (entries);
 581         printk(KERN_DEBUG "%s index ", label);
 582         for (i = 0; i < n; i++) {
 583                 printk("%x->%lu ", i ? dx_get_hash(entries + i) :
 584                                 0, (unsigned long)dx_get_block(entries + i));
 585         }
 586         printk("\n");
 587 }
 588
 589 struct stats
 590 {
 591         unsigned names;
 592         unsigned space;
 593         unsigned bcount;
 594 };
 595
 596 static struct stats dx_show_leaf(struct dx_hash_info *hinfo, struct ext4_dir_entry_2 *de,
 597                                  int size, int show_names)
 598 {
 599         unsigned names = 0, space = 0;
 600         char *base = (char *) de;
 601         struct dx_hash_info h = *hinfo;
 602
 603         printk("names: ");
 604         while ((char *) de < base + size)
 605         {
 606                 if (de->inode)
 607                 {
 608                         if (show_names)
 609                         {
 610                                 int len = de->name_len;
 611                                 char *name = de->name;
 612                                 while (len--) printk("%c", *name++);
 613                                 ext4fs_dirhash(de->name, de->name_len, &h);
 614                                 printk(":%x.%u ", h.hash,
 615                                        (unsigned) ((char *) de - base));
 616                         }
 617                         space += EXT4_DIR_REC_LEN(de->name_len);
 618                         names++;
 619                 }
 620                 de = ext4_next_entry(de, size);
 621         }
 622         printk("(%i)\n", names);
 623         return (struct stats) { names, space, 1 };
 624 }
 625
 626 struct stats dx_show_entries(struct dx_hash_info *hinfo, struct inode *dir,
 627                              struct dx_entry *entries, int levels)
 628 {
 629         unsigned blocksize = dir->i_sb->s_blocksize;
 630         unsigned count = dx_get_count(entries), names = 0, space = 0, i;
 631         unsigned bcount = 0;
 632         struct buffer_head *bh;
 633         int err;
 634         printk("%i indexed blocks...\n", count);
 635         for (i = 0; i < count; i++, entries++)
 636         {
 637                 ext4_lblk_t block = dx_get_block(entries);
 638                 ext4_lblk_t hash  = i ? dx_get_hash(entries): 0;
 639                 u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
 640                 struct stats stats;
 641                 printk("%s%3u:%03u hash %8x/%8x ",levels?"":"   ", i, block, hash, range);
 642                 bh = ext4_bread(NULL,dir, block, 0);
 643                 if (!bh || IS_ERR(bh))
 644                         continue;
 645                 stats = levels?
 646                    dx_show_entries(hinfo, dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
 647                    dx_show_leaf(hinfo, (struct ext4_dir_entry_2 *) bh->b_data, blocksize, 0);
 648                 names += stats.names;
 649                 space += stats.space;
 650                 bcount += stats.bcount;
 651                 brelse(bh);
 652         }
 653         if (bcount)
 654                 printk(KERN_DEBUG "%snames %u, fullness %u (%u%%)\n",
 655                        levels ? "" : "   ", names, space/bcount,
 656                        (space/bcount)*100/blocksize);
 657         return (struct stats) { names, space, bcount};
 658 }
 659 #endif /* DX_DEBUG */
 660
 661 /*
 662  * Probe for a directory leaf block to search.
 663  *
 664  * dx_probe can return ERR_BAD_DX_DIR, which means there was a format
 665  * error in the directory index, and the caller should fall back to
 666  * searching the directory normally.  The callers of dx_probe **MUST**
 667  * check for this error code, and make sure it never gets reflected
 668  * back to userspace.
 669  */
 670 static struct dx_frame *
 671 dx_probe(const struct qstr *d_name, struct inode *dir,
 672          struct dx_hash_info *hinfo, struct dx_frame *frame_in)
 673 {
 674         unsigned count, indirect;
 675         struct dx_entry *at, *entries, *p, *q, *m;
 676         struct dx_root *root;
 677         struct dx_frame *frame = frame_in;
 678         struct dx_frame *ret_err = ERR_PTR(ERR_BAD_DX_DIR);
 679         u32 hash;
 680
 681         frame->bh = ext4_read_dirblock(dir, 0, INDEX);
 682         if (IS_ERR(frame->bh))
 683                 return (struct dx_frame *) frame->bh;
 684
 685         root = (struct dx_root *) frame->bh->b_data;
 686         if (root->info.hash_version != DX_HASH_TEA &&
 687             root->info.hash_version != DX_HASH_HALF_MD4 &&
 688             root->info.hash_version != DX_HASH_LEGACY) {
 689                 ext4_warning(dir->i_sb, "Unrecognised inode hash code %d",
 690                              root->info.hash_version);
 691                 goto fail;
 692         }
 693         hinfo->hash_version = root->info.hash_version;
 694         if (hinfo->hash_version <= DX_HASH_TEA)
 695                 hinfo->hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
 696         hinfo->seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 697         if (d_name)
 698                 ext4fs_dirhash(d_name->name, d_name->len, hinfo);
 699         hash = hinfo->hash;
 700
 701         if (root->info.unused_flags & 1) {
 702                 ext4_warning(dir->i_sb, "Unimplemented inode hash flags: %#06x",
 703                              root->info.unused_flags);
 704                 goto fail;
 705         }
 706
 707         if ((indirect = root->info.indirect_levels) > 1) {
 708                 ext4_warning(dir->i_sb, "Unimplemented inode hash depth: %#06x",
 709                              root->info.indirect_levels);
 710                 goto fail;
 711         }
 712
 713         entries = (struct dx_entry *) (((char *)&root->info) +
 714                                        root->info.info_length);
 715
 716         if (dx_get_limit(entries) != dx_root_limit(dir,
 717                                                    root->info.info_length)) {
 718                 ext4_warning(dir->i_sb, "dx entry: limit != root limit");
 719                 goto fail;
 720         }
 721
 722         dxtrace(printk("Look up %x", hash));
 723         while (1) {
 724                 count = dx_get_count(entries);
 725                 if (!count || count > dx_get_limit(entries)) {
 726                         ext4_warning(dir->i_sb,
 727                                      "dx entry: no count or count > limit");
 728                         goto fail;
 729                 }
 730
 731                 p = entries + 1;
 732                 q = entries + count - 1;
 733                 while (p <= q) {
 734                         m = p + (q - p)/2;
 735                         dxtrace(printk("."));
 736                         if (dx_get_hash(m) > hash)
 737                                 q = m - 1;
 738                         else
 739                                 p = m + 1;
 740                 }
 741
 742                 if (0) { // linear search cross check
 743                         unsigned n = count - 1;
 744                         at = entries;
 745                         while (n--)
 746                         {
 747                                 dxtrace(printk(","));
 748                                 if (dx_get_hash(++at) > hash)
 749                                 {
 750                                         at--;
 751                                         break;
 752                                 }
 753                         }
 754                         assert (at == p - 1);
 755                 }
 756
 757                 at = p - 1;
 758                 dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
 759                 frame->entries = entries;
 760                 frame->at = at;
 761                 if (!indirect--)
 762                         return frame;
 763                 frame++;
 764                 frame->bh = ext4_read_dirblock(dir, dx_get_block(at), INDEX);
 765                 if (IS_ERR(frame->bh)) {
 766                         ret_err = (struct dx_frame *) frame->bh;
 767                         frame->bh = NULL;
 768                         goto fail;
 769                 }
 770                 entries = ((struct dx_node *) frame->bh->b_data)->entries;
 771
 772                 if (dx_get_limit(entries) != dx_node_limit (dir)) {
 773                         ext4_warning(dir->i_sb,
 774                                      "dx entry: limit != node limit");
 775                         goto fail;
 776                 }
 777         }
 778 fail:
 779         while (frame >= frame_in) {
 780                 brelse(frame->bh);
 781                 frame--;
 782         }
 783         if (ret_err == ERR_PTR(ERR_BAD_DX_DIR))
 784                 ext4_warning(dir->i_sb,
 785                              "Corrupt dir inode %lu, running e2fsck is "
 786                              "recommended.", dir->i_ino);
 787         return ret_err;
 788 }
 789
 790 static void dx_release (struct dx_frame *frames)
 791 {
 792         if (frames[0].bh == NULL)
 793                 return;
 794
 795         if (((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels)
 796                 brelse(frames[1].bh);
 797         brelse(frames[0].bh);
 798 }
 799
 800 /*
 801  * This function increments the frame pointer to search the next leaf
 802  * block, and reads in the necessary intervening nodes if the search
 803  * should be necessary.  Whether or not the search is necessary is
 804  * controlled by the hash parameter.  If the hash value is even, then
 805  * the search is only continued if the next block starts with that
 806  * hash value.  This is used if we are searching for a specific file.
 807  *
 808  * If the hash value is HASH_NB_ALWAYS, then always go to the next block.
 809  *
 810  * This function returns 1 if the caller should continue to search,
 811  * or 0 if it should not.  If there is an error reading one of the
 812  * index blocks, it will a negative error code.
 813  *
 814  * If start_hash is non-null, it will be filled in with the starting
 815  * hash of the next page.
 816  */
 817 static int ext4_htree_next_block(struct inode *dir, __u32 hash,
 818                                  struct dx_frame *frame,
 819                                  struct dx_frame *frames,
 820                                  __u32 *start_hash)
 821 {
 822         struct dx_frame *p;
 823         struct buffer_head *bh;
 824         int num_frames = 0;
 825         __u32 bhash;
 826
 827         p = frame;
 828         /*
 829          * Find the next leaf page by incrementing the frame pointer.
 830          * If we run out of entries in the interior node, loop around and
 831          * increment pointer in the parent node.  When we break out of
 832          * this loop, num_frames indicates the number of interior
 833          * nodes need to be read.
 834          */
 835         while (1) {
 836                 if (++(p->at) < p->entries + dx_get_count(p->entries))
 837                         break;
 838                 if (p == frames)
 839                         return 0;
 840                 num_frames++;
 841                 p--;
 842         }
 843
 844         /*
 845          * If the hash is 1, then continue only if the next page has a
 846          * continuation hash of any value.  This is used for readdir
 847          * handling.  Otherwise, check to see if the hash matches the
 848          * desired contiuation hash.  If it doesn't, return since
 849          * there's no point to read in the successive index pages.
 850          */
 851         bhash = dx_get_hash(p->at);
 852         if (start_hash)
 853                 *start_hash = bhash;
 854         if ((hash & 1) == 0) {
 855                 if ((bhash & ~1) != hash)
 856                         return 0;
 857         }
 858         /*
 859          * If the hash is HASH_NB_ALWAYS, we always go to the next
 860          * block so no check is necessary
 861          */
 862         while (num_frames--) {
 863                 bh = ext4_read_dirblock(dir, dx_get_block(p->at), INDEX);
 864                 if (IS_ERR(bh))
 865                         return PTR_ERR(bh);
 866                 p++;
 867                 brelse(p->bh);
 868                 p->bh = bh;
 869                 p->at = p->entries = ((struct dx_node *) bh->b_data)->entries;
 870         }
 871         return 1;
 872 }
 873
 874
 875 /*
 876  * This function fills a red-black tree with information from a
 877  * directory block.  It returns the number directory entries loaded
 878  * into the tree.  If there is an error it is returned in err.
 879  */
 880 static int htree_dirblock_to_tree(struct file *dir_file,
 881                                   struct inode *dir, ext4_lblk_t block,
 882                                   struct dx_hash_info *hinfo,
 883                                   __u32 start_hash, __u32 start_minor_hash)
 884 {
 885         struct buffer_head *bh;
 886         struct ext4_dir_entry_2 *de, *top;
 887         int err = 0, count = 0;
 888
 889         dxtrace(printk(KERN_INFO "In htree dirblock_to_tree: block %lu\n",
 890                                                         (unsigned long)block));
 891         bh = ext4_read_dirblock(dir, block, DIRENT);
 892         if (IS_ERR(bh))
 893                 return PTR_ERR(bh);
 894
 895         de = (struct ext4_dir_entry_2 *) bh->b_data;
 896         top = (struct ext4_dir_entry_2 *) ((char *) de +
 897                                            dir->i_sb->s_blocksize -
 898                                            EXT4_DIR_REC_LEN(0));
 899         for (; de < top; de = ext4_next_entry(de, dir->i_sb->s_blocksize)) {
 900                 if (ext4_check_dir_entry(dir, NULL, de, bh,
 901                                 bh->b_data, bh->b_size,
 902                                 (block<<EXT4_BLOCK_SIZE_BITS(dir->i_sb))
 903                                          + ((char *)de - bh->b_data))) {
 904                         /* silently ignore the rest of the block */
 905                         break;
 906                 }
 907                 ext4fs_dirhash(de->name, de->name_len, hinfo);
 908                 if ((hinfo->hash < start_hash) ||
 909                     ((hinfo->hash == start_hash) &&
 910                      (hinfo->minor_hash < start_minor_hash)))
 911                         continue;
 912                 if (de->inode == 0)
 913                         continue;
 914                 if ((err = ext4_htree_store_dirent(dir_file,
 915                                    hinfo->hash, hinfo->minor_hash, de)) != 0) {
 916                         brelse(bh);
 917                         return err;
 918                 }
 919                 count++;
 920         }
 921         brelse(bh);
 922         return count;
 923 }
 924
 925
 926 /*
 927  * This function fills a red-black tree with information from a
 928  * directory.  We start scanning the directory in hash order, starting
 929  * at start_hash and start_minor_hash.
 930  *
 931  * This function returns the number of entries inserted into the tree,
 932  * or a negative error code.
 933  */
 934 int ext4_htree_fill_tree(struct file *dir_file, __u32 start_hash,
 935                          __u32 start_minor_hash, __u32 *next_hash)
 936 {
 937         struct dx_hash_info hinfo;
 938         struct ext4_dir_entry_2 *de;
 939         struct dx_frame frames[2], *frame;
 940         struct inode *dir;
 941         ext4_lblk_t block;
 942         int count = 0;
 943         int ret, err;
 944         __u32 hashval;
 945
 946         dxtrace(printk(KERN_DEBUG "In htree_fill_tree, start hash: %x:%x\n",
 947                        start_hash, start_minor_hash));
 948         dir = file_inode(dir_file);
 949         if (!(ext4_test_inode_flag(dir, EXT4_INODE_INDEX))) {
 950                 hinfo.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
 951                 if (hinfo.hash_version <= DX_HASH_TEA)
 952                         hinfo.hash_version +=
 953                                 EXT4_SB(dir->i_sb)->s_hash_unsigned;
 954                 hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
 955                 if (ext4_has_inline_data(dir)) {
 956                         int has_inline_data = 1;
 957                         count = htree_inlinedir_to_tree(dir_file, dir, 0,
 958                                                         &hinfo, start_hash,
 959                                                         start_minor_hash,
 960                                                         &has_inline_data);
 961                         if (has_inline_data) {
 962                                 *next_hash = ~0;
 963                                 return count;
 964                         }
 965                 }
 966                 count = htree_dirblock_to_tree(dir_file, dir, 0, &hinfo,
 967                                                start_hash, start_minor_hash);
 968                 *next_hash = ~0;
 969                 return count;
 970         }
 971         hinfo.hash = start_hash;
 972         hinfo.minor_hash = 0;
 973         frame = dx_probe(NULL, dir, &hinfo, frames);
 974         if (IS_ERR(frame))
 975                 return PTR_ERR(frame);
 976
 977         /* Add '.' and '..' from the htree header */
 978         if (!start_hash && !start_minor_hash) {
 979                 de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
 980                 if ((err = ext4_htree_store_dirent(dir_file, 0, 0, de)) != 0)
 981                         goto errout;
 982                 count++;
 983         }
 984         if (start_hash < 2 || (start_hash ==2 && start_minor_hash==0)) {
 985                 de = (struct ext4_dir_entry_2 *) frames[0].bh->b_data;
 986                 de = ext4_next_entry(de, dir->i_sb->s_blocksize);
 987                 if ((err = ext4_htree_store_dirent(dir_file, 2, 0, de)) != 0)
 988                         goto errout;
 989                 count++;
 990         }
 991
 992         while (1) {
 993                 block = dx_get_block(frame->at);
 994                 ret = htree_dirblock_to_tree(dir_file, dir, block, &hinfo,
 995                                              start_hash, start_minor_hash);
 996                 if (ret < 0) {
 997                         err = ret;
 998                         goto errout;
 999                 }
1000                 count += ret;
1001                 hashval = ~0;
1002                 ret = ext4_htree_next_block(dir, HASH_NB_ALWAYS,
1003                                             frame, frames, &hashval);
1004                 *next_hash = hashval;
1005                 if (ret < 0) {
1006                         err = ret;
1007                         goto errout;
1008                 }
1009                 /*
1010                  * Stop if:  (a) there are no more entries, or
1011                  * (b) we have inserted at least one entry and the
1012                  * next hash value is not a continuation
1013                  */
1014                 if ((ret == 0) ||
1015                     (count && ((hashval & 1) == 0)))
1016                         break;
1017         }
1018         dx_release(frames);
1019         dxtrace(printk(KERN_DEBUG "Fill tree: returned %d entries, "
1020                        "next hash: %x\n", count, *next_hash));
1021         return count;
1022 errout:
1023         dx_release(frames);
1024         return (err);
1025 }
1026
1027 static inline int search_dirblock(struct buffer_head *bh,
1028                                   struct inode *dir,
1029                                   const struct qstr *d_name,
1030                                   unsigned int offset,
1031                                   struct ext4_dir_entry_2 **res_dir)
1032 {
1033         return search_dir(bh, bh->b_data, dir->i_sb->s_blocksize, dir,
1034                           d_name, offset, res_dir);
1035 }
1036
1037 /*
1038  * Directory block splitting, compacting
1039  */
1040
1041 /*
1042  * Create map of hash values, offsets, and sizes, stored at end of block.
1043  * Returns number of entries mapped.
1044  */
1045 static int dx_make_map(struct ext4_dir_entry_2 *de, unsigned blocksize,
1046                        struct dx_hash_info *hinfo,
1047                        struct dx_map_entry *map_tail)
1048 {
1049         int count = 0;
1050         char *base = (char *) de;
1051         struct dx_hash_info h = *hinfo;
1052
1053         while ((char *) de < base + blocksize) {
1054                 if (de->name_len && de->inode) {
1055                         ext4fs_dirhash(de->name, de->name_len, &h);
1056                         map_tail--;
1057                         map_tail->hash = h.hash;
1058                         map_tail->offs = ((char *) de - base)>>2;
1059                         map_tail->size = le16_to_cpu(de->rec_len);
1060                         count++;
1061                         cond_resched();
1062                 }
1063                 /* XXX: do we need to check rec_len == 0 case? -Chris */
1064                 de = ext4_next_entry(de, blocksize);
1065         }
1066         return count;
1067 }
1068
1069 /* Sort map by hash value */
1070 static void dx_sort_map (struct dx_map_entry *map, unsigned count)
1071 {
1072         struct dx_map_entry *p, *q, *top = map + count - 1;
1073         int more;
1074         /* Combsort until bubble sort doesn't suck */
1075         while (count > 2) {
1076                 count = count*10/13;
1077                 if (count - 9 < 2) /* 9, 10 -> 11 */
1078                         count = 11;
1079                 for (p = top, q = p - count; q >= map; p--, q--)
1080                         if (p->hash < q->hash)
1081                                 swap(*p, *q);
1082         }
1083         /* Garden variety bubble sort */
1084         do {
1085                 more = 0;
1086                 q = top;
1087                 while (q-- > map) {
1088                         if (q[1].hash >= q[0].hash)
1089                                 continue;
1090                         swap(*(q+1), *q);
1091                         more = 1;
1092                 }
1093         } while(more);
1094 }
1095
1096 static void dx_insert_block(struct dx_frame *frame, u32 hash, ext4_lblk_t block)
1097 {
1098         struct dx_entry *entries = frame->entries;
1099         struct dx_entry *old = frame->at, *new = old + 1;
1100         int count = dx_get_count(entries);
1101
1102         assert(count < dx_get_limit(entries));
1103         assert(old < entries + count);
1104         memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
1105         dx_set_hash(new, hash);
1106         dx_set_block(new, block);
1107         dx_set_count(entries, count + 1);
1108 }
1109
1110 /*
1111  * NOTE! unlike strncmp, ext4_match returns 1 for success, 0 for failure.
1112  *
1113  * `len <= EXT4_NAME_LEN' is guaranteed by caller.
1114  * `de != NULL' is guaranteed by caller.
1115  */
1116 static inline int ext4_match (int len, const char * const name,
1117                               struct ext4_dir_entry_2 * de)
1118 {
1119         if (len != de->name_len)
1120                 return 0;
1121         if (!de->inode)
1122                 return 0;
1123         return !memcmp(name, de->name, len);
1124 }
1125
1126 /*
1127  * Returns 0 if not found, -1 on failure, and 1 on success
1128  */
1129 int search_dir(struct buffer_head *bh,
1130                char *search_buf,
1131                int buf_size,
1132                struct inode *dir,
1133                const struct qstr *d_name,
1134                unsigned int offset,
1135                struct ext4_dir_entry_2 **res_dir)
1136 {
1137         struct ext4_dir_entry_2 * de;
1138         char * dlimit;
1139         int de_len;
1140         const char *name = d_name->name;
1141         int namelen = d_name->len;
1142
1143         de = (struct ext4_dir_entry_2 *)search_buf;
1144         dlimit = search_buf + buf_size;
1145         while ((char *) de < dlimit) {
1146                 /* this code is executed quadratically often */
1147                 /* do minimal checking `by hand' */
1148
1149                 if ((char *) de + namelen <= dlimit &&
1150                     ext4_match (namelen, name, de)) {
1151                         /* found a match - just to be sure, do a full check */
1152                         if (ext4_check_dir_entry(dir, NULL, de, bh, bh->b_data,
1153                                                  bh->b_size, offset))
1154                                 return -1;
1155                         *res_dir = de;
1156                         return 1;
1157                 }
1158                 /* prevent looping on a bad block */
1159                 de_len = ext4_rec_len_from_disk(de->rec_len,
1160                                                 dir->i_sb->s_blocksize);
1161                 if (de_len <= 0)
1162                         return -1;
1163                 offset += de_len;
1164                 de = (struct ext4_dir_entry_2 *) ((char *) de + de_len);
1165         }
1166         return 0;
1167 }
1168
1169 static int is_dx_internal_node(struct inode *dir, ext4_lblk_t block,
1170                                struct ext4_dir_entry *de)
1171 {
1172         struct super_block *sb = dir->i_sb;
1173
1174         if (!is_dx(dir))
1175                 return 0;
1176         if (block == 0)
1177                 return 1;
1178         if (de->inode == 0 &&
1179             ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) ==
1180                         sb->s_blocksize)
1181                 return 1;
1182         return 0;
1183 }
1184
1185 /*
1186  *      ext4_find_entry()
1187  *
1188  * finds an entry in the specified directory with the wanted name. It
1189  * returns the cache buffer in which the entry was found, and the entry
1190  * itself (as a parameter - res_dir). It does NOT read the inode of the
1191  * entry - you'll have to do that yourself if you want to.
1192  *
1193  * The returned buffer_head has ->b_count elevated.  The caller is expected
1194  * to brelse() it when appropriate.
1195  */
1196 static struct buffer_head * ext4_find_entry (struct inode *dir,
1197                                         const struct qstr *d_name,
1198                                         struct ext4_dir_entry_2 **res_dir,
1199                                         int *inlined)
1200 {
1201         struct super_block *sb;
1202         struct buffer_head *bh_use[NAMEI_RA_SIZE];
1203         struct buffer_head *bh, *ret = NULL;
1204         ext4_lblk_t start, block, b;
1205         const u8 *name = d_name->name;
1206         int ra_max = 0;         /* Number of bh's in the readahead
1207                                    buffer, bh_use[] */
1208         int ra_ptr = 0;         /* Current index into readahead
1209                                    buffer */
1210         int num = 0;
1211         ext4_lblk_t  nblocks;
1212         int i, namelen;
1213
1214         *res_dir = NULL;
1215         sb = dir->i_sb;
1216         namelen = d_name->len;
1217         if (namelen > EXT4_NAME_LEN)
1218                 return NULL;
1219
1220         if (ext4_has_inline_data(dir)) {
1221                 int has_inline_data = 1;
1222                 ret = ext4_find_inline_entry(dir, d_name, res_dir,
1223                                              &has_inline_data);
1224                 if (has_inline_data) {
1225                         if (inlined)
1226                                 *inlined = 1;
1227                         return ret;
1228                 }
1229         }
1230
1231         if ((namelen <= 2) && (name[0] == '.') &&
1232             (name[1] == '.' || name[1] == '\0')) {
1233                 /*
1234                  * "." or ".." will only be in the first block
1235                  * NFS may look up ".."; "." should be handled by the VFS
1236                  */
1237                 block = start = 0;
1238                 nblocks = 1;
1239                 goto restart;
1240         }
1241         if (is_dx(dir)) {
1242                 bh = ext4_dx_find_entry(dir, d_name, res_dir);
1243                 /*
1244                  * On success, or if the error was file not found,
1245                  * return.  Otherwise, fall back to doing a search the
1246                  * old fashioned way.
1247                  */
1248                 if (!IS_ERR(bh) || PTR_ERR(bh) != ERR_BAD_DX_DIR)
1249                         return bh;
1250                 dxtrace(printk(KERN_DEBUG "ext4_find_entry: dx failed, "
1251                                "falling back\n"));
1252         }
1253         nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
1254         start = EXT4_I(dir)->i_dir_start_lookup;
1255         if (start >= nblocks)
1256                 start = 0;
1257         block = start;
1258 restart:
1259         do {
1260                 /*
1261                  * We deal with the read-ahead logic here.
1262                  */
1263                 if (ra_ptr >= ra_max) {
1264                         /* Refill the readahead buffer */
1265                         ra_ptr = 0;
1266                         b = block;
1267                         for (ra_max = 0; ra_max < NAMEI_RA_SIZE; ra_max++) {
1268                                 /*
1269                                  * Terminate if we reach the end of the
1270                                  * directory and must wrap, or if our
1271                                  * search has finished at this block.
1272                                  */
1273                                 if (b >= nblocks || (num && block == start)) {
1274                                         bh_use[ra_max] = NULL;
1275                                         break;
1276                                 }
1277                                 num++;
1278                                 bh = ext4_getblk(NULL, dir, b++, 0);
1279                                 if (unlikely(IS_ERR(bh))) {
1280                                         if (ra_max == 0)
1281                                                 return bh;
1282                                         break;
1283                                 }
1284                                 bh_use[ra_max] = bh;
1285                                 if (bh)
1286                                         ll_rw_block(READ | REQ_META | REQ_PRIO,
1287                                                     1, &bh);
1288                         }
1289                 }
1290                 if ((bh = bh_use[ra_ptr++]) == NULL)
1291                         goto next;
1292                 wait_on_buffer(bh);
1293                 if (!buffer_uptodate(bh)) {
1294                         /* read error, skip block & hope for the best */
1295                         EXT4_ERROR_INODE(dir, "reading directory lblock %lu",
1296                                          (unsigned long) block);
1297                         brelse(bh);
1298                         goto next;
1299                 }
1300                 if (!buffer_verified(bh) &&
1301                     !is_dx_internal_node(dir, block,
1302                                          (struct ext4_dir_entry *)bh->b_data) &&
1303                     !ext4_dirent_csum_verify(dir,
1304                                 (struct ext4_dir_entry *)bh->b_data)) {
1305                         EXT4_ERROR_INODE(dir, "checksumming directory "
1306                                          "block %lu", (unsigned long)block);
1307                         brelse(bh);
1308                         goto next;
1309                 }
1310                 set_buffer_verified(bh);
1311                 i = search_dirblock(bh, dir, d_name,
1312                             block << EXT4_BLOCK_SIZE_BITS(sb), res_dir);
1313                 if (i == 1) {
1314                         EXT4_I(dir)->i_dir_start_lookup = block;
1315                         ret = bh;
1316                         goto cleanup_and_exit;
1317                 } else {
1318                         brelse(bh);
1319                         if (i < 0)
1320                                 goto cleanup_and_exit;
1321                 }
1322         next:
1323                 if (++block >= nblocks)
1324                         block = 0;
1325         } while (block != start);
1326
1327         /*
1328          * If the directory has grown while we were searching, then
1329          * search the last part of the directory before giving up.
1330          */
1331         block = nblocks;
1332         nblocks = dir->i_size >> EXT4_BLOCK_SIZE_BITS(sb);
1333         if (block < nblocks) {
1334                 start = 0;
1335                 goto restart;
1336         }
1337
1338 cleanup_and_exit:
1339         /* Clean up the read-ahead blocks */
1340         for (; ra_ptr < ra_max; ra_ptr++)
1341                 brelse(bh_use[ra_ptr]);
1342         return ret;
1343 }
1344
1345 static struct buffer_head * ext4_dx_find_entry(struct inode *dir, const struct qstr *d_name,
1346                        struct ext4_dir_entry_2 **res_dir)
1347 {
1348         struct super_block * sb = dir->i_sb;
1349         struct dx_hash_info     hinfo;
1350         struct dx_frame frames[2], *frame;
1351         struct buffer_head *bh;
1352         ext4_lblk_t block;
1353         int retval;
1354
1355         frame = dx_probe(d_name, dir, &hinfo, frames);
1356         if (IS_ERR(frame))
1357                 return (struct buffer_head *) frame;
1358         do {
1359                 block = dx_get_block(frame->at);
1360                 bh = ext4_read_dirblock(dir, block, DIRENT);
1361                 if (IS_ERR(bh))
1362                         goto errout;
1363
1364                 retval = search_dirblock(bh, dir, d_name,
1365                                          block << EXT4_BLOCK_SIZE_BITS(sb),
1366                                          res_dir);
1367                 if (retval == 1)
1368                         goto success;
1369                 brelse(bh);
1370                 if (retval == -1) {
1371                         bh = ERR_PTR(ERR_BAD_DX_DIR);
1372                         goto errout;
1373                 }
1374
1375                 /* Check to see if we should continue to search */
1376                 retval = ext4_htree_next_block(dir, hinfo.hash, frame,
1377                                                frames, NULL);
1378                 if (retval < 0) {
1379                         ext4_warning(sb,
1380                              "error %d reading index page in directory #%lu",
1381                              retval, dir->i_ino);
1382                         bh = ERR_PTR(retval);
1383                         goto errout;
1384                 }
1385         } while (retval == 1);
1386
1387         bh = NULL;
1388 errout:
1389         dxtrace(printk(KERN_DEBUG "%s not found\n", d_name->name));
1390 success:
1391         dx_release(frames);
1392         return bh;
1393 }
1394
1395 static struct dentry *ext4_lookup(struct inode *dir, struct dentry *dentry, unsigned int flags)
1396 {
1397         struct inode *inode;
1398         struct ext4_dir_entry_2 *de;
1399         struct buffer_head *bh;
1400
1401         if (dentry->d_name.len > EXT4_NAME_LEN)
1402                 return ERR_PTR(-ENAMETOOLONG);
1403
1404         bh = ext4_find_entry(dir, &dentry->d_name, &de, NULL);
1405         if (IS_ERR(bh))
1406                 return (struct dentry *) bh;
1407         inode = NULL;
1408         if (bh) {
1409                 __u32 ino = le32_to_cpu(de->inode);
1410                 brelse(bh);
1411                 if (!ext4_valid_inum(dir->i_sb, ino)) {
1412                         EXT4_ERROR_INODE(dir, "bad inode number: %u", ino);
1413                         return ERR_PTR(-EIO);
1414                 }
1415                 if (unlikely(ino == dir->i_ino)) {
1416                         EXT4_ERROR_INODE(dir, "'%pd' linked to parent dir",
1417                                          dentry);
1418                         return ERR_PTR(-EIO);
1419                 }
1420                 inode = ext4_iget(dir->i_sb, ino);
1421                 if (inode == ERR_PTR(-ESTALE)) {
1422                         EXT4_ERROR_INODE(dir,
1423                                          "deleted inode referenced: %u",
1424                                          ino);
1425                         return ERR_PTR(-EIO);
1426                 }
1427         }
1428         return d_splice_alias(inode, dentry);
1429 }
1430
1431
1432 struct dentry *ext4_get_parent(struct dentry *child)
1433 {
1434         __u32 ino;
1435         static const struct qstr dotdot = QSTR_INIT("..", 2);
1436         struct ext4_dir_entry_2 * de;
1437         struct buffer_head *bh;
1438
1439         bh = ext4_find_entry(child->d_inode, &dotdot, &de, NULL);
1440         if (IS_ERR(bh))
1441                 return (struct dentry *) bh;
1442         if (!bh)
1443                 return ERR_PTR(-ENOENT);
1444         ino = le32_to_cpu(de->inode);
1445         brelse(bh);
1446
1447         if (!ext4_valid_inum(child->d_inode->i_sb, ino)) {
1448                 EXT4_ERROR_INODE(child->d_inode,
1449                                  "bad parent inode number: %u", ino);
1450                 return ERR_PTR(-EIO);
1451         }
1452
1453         return d_obtain_alias(ext4_iget(child->d_inode->i_sb, ino));
1454 }
1455
1456 /*
1457  * Move count entries from end of map between two memory locations.
1458  * Returns pointer to last entry moved.
1459  */
1460 static struct ext4_dir_entry_2 *
1461 dx_move_dirents(char *from, char *to, struct dx_map_entry *map, int count,
1462                 unsigned blocksize)
1463 {
1464         unsigned rec_len = 0;
1465
1466         while (count--) {
1467                 struct ext4_dir_entry_2 *de = (struct ext4_dir_entry_2 *)
1468                                                 (from + (map->offs<<2));
1469                 rec_len = EXT4_DIR_REC_LEN(de->name_len);
1470                 memcpy (to, de, rec_len);
1471                 ((struct ext4_dir_entry_2 *) to)->rec_len =
1472                                 ext4_rec_len_to_disk(rec_len, blocksize);
1473                 de->inode = 0;
1474                 map++;
1475                 to += rec_len;
1476         }
1477         return (struct ext4_dir_entry_2 *) (to - rec_len);
1478 }
1479
1480 /*
1481  * Compact each dir entry in the range to the minimal rec_len.
1482  * Returns pointer to last entry in range.
1483  */
1484 static struct ext4_dir_entry_2* dx_pack_dirents(char *base, unsigned blocksize)
1485 {
1486         struct ext4_dir_entry_2 *next, *to, *prev, *de = (struct ext4_dir_entry_2 *) base;
1487         unsigned rec_len = 0;
1488
1489         prev = to = de;
1490         while ((char*)de < base + blocksize) {
1491                 next = ext4_next_entry(de, blocksize);
1492                 if (de->inode && de->name_len) {
1493                         rec_len = EXT4_DIR_REC_LEN(de->name_len);
1494                         if (de > to)
1495                                 memmove(to, de, rec_len);
1496                         to->rec_len = ext4_rec_len_to_disk(rec_len, blocksize);
1497                         prev = to;
1498                         to = (struct ext4_dir_entry_2 *) (((char *) to) + rec_len);
1499                 }
1500                 de = next;
1501         }
1502         return prev;
1503 }
1504
1505 /*
1506  * Split a full leaf block to make room for a new dir entry.
1507  * Allocate a new block, and move entries so that they are approx. equally full.
1508  * Returns pointer to de in block into which the new entry will be inserted.
1509  */
1510 static struct ext4_dir_entry_2 *do_split(handle_t *handle, struct inode *dir,
1511                         struct buffer_head **bh,struct dx_frame *frame,
1512                         struct dx_hash_info *hinfo)
1513 {
1514         unsigned blocksize = dir->i_sb->s_blocksize;
1515         unsigned count, continued;
1516         struct buffer_head *bh2;
1517         ext4_lblk_t newblock;
1518         u32 hash2;
1519         struct dx_map_entry *map;
1520         char *data1 = (*bh)->b_data, *data2;
1521         unsigned split, move, size;
1522         struct ext4_dir_entry_2 *de = NULL, *de2;
1523         struct ext4_dir_entry_tail *t;
1524         int     csum_size = 0;
1525         int     err = 0, i;
1526
1527         if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
1528                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1529                 csum_size = sizeof(struct ext4_dir_entry_tail);
1530
1531         bh2 = ext4_append(handle, dir, &newblock);
1532         if (IS_ERR(bh2)) {
1533                 brelse(*bh);
1534                 *bh = NULL;
1535                 return (struct ext4_dir_entry_2 *) bh2;
1536         }
1537
1538         BUFFER_TRACE(*bh, "get_write_access");
1539         err = ext4_journal_get_write_access(handle, *bh);
1540         if (err)
1541                 goto journal_error;
1542
1543         BUFFER_TRACE(frame->bh, "get_write_access");
1544         err = ext4_journal_get_write_access(handle, frame->bh);
1545         if (err)
1546                 goto journal_error;
1547
1548         data2 = bh2->b_data;
1549
1550         /* create map in the end of data2 block */
1551         map = (struct dx_map_entry *) (data2 + blocksize);
1552         count = dx_make_map((struct ext4_dir_entry_2 *) data1,
1553                              blocksize, hinfo, map);
1554         map -= count;
1555         dx_sort_map(map, count);
1556         /* Split the existing block in the middle, size-wise */
1557         size = 0;
1558         move = 0;
1559         for (i = count-1; i >= 0; i--) {
1560                 /* is more than half of this entry in 2nd half of the block? */
1561                 if (size + map[i].size/2 > blocksize/2)
1562                         break;
1563                 size += map[i].size;
1564                 move++;
1565         }
1566         /* map index at which we will split */
1567         split = count - move;
1568         hash2 = map[split].hash;
1569         continued = hash2 == map[split - 1].hash;
1570         dxtrace(printk(KERN_INFO "Split block %lu at %x, %i/%i\n",
1571                         (unsigned long)dx_get_block(frame->at),
1572                                         hash2, split, count-split));
1573
1574         /* Fancy dance to stay within two buffers */
1575         de2 = dx_move_dirents(data1, data2, map + split, count - split, blocksize);
1576         de = dx_pack_dirents(data1, blocksize);
1577         de->rec_len = ext4_rec_len_to_disk(data1 + (blocksize - csum_size) -
1578                                            (char *) de,
1579                                            blocksize);
1580         de2->rec_len = ext4_rec_len_to_disk(data2 + (blocksize - csum_size) -
1581                                             (char *) de2,
1582                                             blocksize);
1583         if (csum_size) {
1584                 t = EXT4_DIRENT_TAIL(data2, blocksize);
1585                 initialize_dirent_tail(t, blocksize);
1586
1587                 t = EXT4_DIRENT_TAIL(data1, blocksize);
1588                 initialize_dirent_tail(t, blocksize);
1589         }
1590
1591         dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data1, blocksize, 1));
1592         dxtrace(dx_show_leaf (hinfo, (struct ext4_dir_entry_2 *) data2, blocksize, 1));
1593
1594         /* Which block gets the new entry? */
1595         if (hinfo->hash >= hash2) {
1596                 swap(*bh, bh2);
1597                 de = de2;
1598         }
1599         dx_insert_block(frame, hash2 + continued, newblock);
1600         err = ext4_handle_dirty_dirent_node(handle, dir, bh2);
1601         if (err)
1602                 goto journal_error;
1603         err = ext4_handle_dirty_dx_node(handle, dir, frame->bh);
1604         if (err)
1605                 goto journal_error;
1606         brelse(bh2);
1607         dxtrace(dx_show_index("frame", frame->entries));
1608         return de;
1609
1610 journal_error:
1611         brelse(*bh);
1612         brelse(bh2);
1613         *bh = NULL;
1614         ext4_std_error(dir->i_sb, err);
1615         return ERR_PTR(err);
1616 }
1617
1618 int ext4_find_dest_de(struct inode *dir, struct inode *inode,
1619                       struct buffer_head *bh,
1620                       void *buf, int buf_size,
1621                       const char *name, int namelen,
1622                       struct ext4_dir_entry_2 **dest_de)
1623 {
1624         struct ext4_dir_entry_2 *de;
1625         unsigned short reclen = EXT4_DIR_REC_LEN(namelen);
1626         int nlen, rlen;
1627         unsigned int offset = 0;
1628         char *top;
1629
1630         de = (struct ext4_dir_entry_2 *)buf;
1631         top = buf + buf_size - reclen;
1632         while ((char *) de <= top) {
1633                 if (ext4_check_dir_entry(dir, NULL, de, bh,
1634                                          buf, buf_size, offset))
1635                         return -EIO;
1636                 if (ext4_match(namelen, name, de))
1637                         return -EEXIST;
1638                 nlen = EXT4_DIR_REC_LEN(de->name_len);
1639                 rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
1640                 if ((de->inode ? rlen - nlen : rlen) >= reclen)
1641                         break;
1642                 de = (struct ext4_dir_entry_2 *)((char *)de + rlen);
1643                 offset += rlen;
1644         }
1645         if ((char *) de > top)
1646                 return -ENOSPC;
1647
1648         *dest_de = de;
1649         return 0;
1650 }
1651
1652 void ext4_insert_dentry(struct inode *inode,
1653                         struct ext4_dir_entry_2 *de,
1654                         int buf_size,
1655                         const char *name, int namelen)
1656 {
1657
1658         int nlen, rlen;
1659
1660         nlen = EXT4_DIR_REC_LEN(de->name_len);
1661         rlen = ext4_rec_len_from_disk(de->rec_len, buf_size);
1662         if (de->inode) {
1663                 struct ext4_dir_entry_2 *de1 =
1664                                 (struct ext4_dir_entry_2 *)((char *)de + nlen);
1665                 de1->rec_len = ext4_rec_len_to_disk(rlen - nlen, buf_size);
1666                 de->rec_len = ext4_rec_len_to_disk(nlen, buf_size);
1667                 de = de1;
1668         }
1669         de->file_type = EXT4_FT_UNKNOWN;
1670         de->inode = cpu_to_le32(inode->i_ino);
1671         ext4_set_de_type(inode->i_sb, de, inode->i_mode);
1672         de->name_len = namelen;
1673         memcpy(de->name, name, namelen);
1674 }
1675 /*
1676  * Add a new entry into a directory (leaf) block.  If de is non-NULL,
1677  * it points to a directory entry which is guaranteed to be large
1678  * enough for new directory entry.  If de is NULL, then
1679  * add_dirent_to_buf will attempt search the directory block for
1680  * space.  It will return -ENOSPC if no space is available, and -EIO
1681  * and -EEXIST if directory entry already exists.
1682  */
1683 static int add_dirent_to_buf(handle_t *handle, struct dentry *dentry,
1684                              struct inode *inode, struct ext4_dir_entry_2 *de,
1685                              struct buffer_head *bh)
1686 {
1687         struct inode    *dir = dentry->d_parent->d_inode;
1688         const char      *name = dentry->d_name.name;
1689         int             namelen = dentry->d_name.len;
1690         unsigned int    blocksize = dir->i_sb->s_blocksize;
1691         int             csum_size = 0;
1692         int             err;
1693
1694         if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
1695                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1696                 csum_size = sizeof(struct ext4_dir_entry_tail);
1697
1698         if (!de) {
1699                 err = ext4_find_dest_de(dir, inode,
1700                                         bh, bh->b_data, blocksize - csum_size,
1701                                         name, namelen, &de);
1702                 if (err)
1703                         return err;
1704         }
1705         BUFFER_TRACE(bh, "get_write_access");
1706         err = ext4_journal_get_write_access(handle, bh);
1707         if (err) {
1708                 ext4_std_error(dir->i_sb, err);
1709                 return err;
1710         }
1711
1712         /* By now the buffer is marked for journaling */
1713         ext4_insert_dentry(inode, de, blocksize, name, namelen);
1714
1715         /*
1716          * XXX shouldn't update any times until successful
1717          * completion of syscall, but too many callers depend
1718          * on this.
1719          *
1720          * XXX similarly, too many callers depend on
1721          * ext4_new_inode() setting the times, but error
1722          * recovery deletes the inode, so the worst that can
1723          * happen is that the times are slightly out of date
1724          * and/or different from the directory change time.
1725          */
1726         dir->i_mtime = dir->i_ctime = ext4_current_time(dir);
1727         ext4_update_dx_flag(dir);
1728         dir->i_version++;
1729         ext4_mark_inode_dirty(handle, dir);
1730         BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
1731         err = ext4_handle_dirty_dirent_node(handle, dir, bh);
1732         if (err)
1733                 ext4_std_error(dir->i_sb, err);
1734         return 0;
1735 }
1736
1737 /*
1738  * This converts a one block unindexed directory to a 3 block indexed
1739  * directory, and adds the dentry to the indexed directory.
1740  */
1741 static int make_indexed_dir(handle_t *handle, struct dentry *dentry,
1742                             struct inode *inode, struct buffer_head *bh)
1743 {
1744         struct inode    *dir = dentry->d_parent->d_inode;
1745         const char      *name = dentry->d_name.name;
1746         int             namelen = dentry->d_name.len;
1747         struct buffer_head *bh2;
1748         struct dx_root  *root;
1749         struct dx_frame frames[2], *frame;
1750         struct dx_entry *entries;
1751         struct ext4_dir_entry_2 *de, *de2;
1752         struct ext4_dir_entry_tail *t;
1753         char            *data1, *top;
1754         unsigned        len;
1755         int             retval;
1756         unsigned        blocksize;
1757         struct dx_hash_info hinfo;
1758         ext4_lblk_t  block;
1759         struct fake_dirent *fde;
1760         int             csum_size = 0;
1761
1762         if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
1763                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1764                 csum_size = sizeof(struct ext4_dir_entry_tail);
1765
1766         blocksize =  dir->i_sb->s_blocksize;
1767         dxtrace(printk(KERN_DEBUG "Creating index: inode %lu\n", dir->i_ino));
1768         BUFFER_TRACE(bh, "get_write_access");
1769         retval = ext4_journal_get_write_access(handle, bh);
1770         if (retval) {
1771                 ext4_std_error(dir->i_sb, retval);
1772                 brelse(bh);
1773                 return retval;
1774         }
1775         root = (struct dx_root *) bh->b_data;
1776
1777         /* The 0th block becomes the root, move the dirents out */
1778         fde = &root->dotdot;
1779         de = (struct ext4_dir_entry_2 *)((char *)fde +
1780                 ext4_rec_len_from_disk(fde->rec_len, blocksize));
1781         if ((char *) de >= (((char *) root) + blocksize)) {
1782                 EXT4_ERROR_INODE(dir, "invalid rec_len for '..'");
1783                 brelse(bh);
1784                 return -EIO;
1785         }
1786         len = ((char *) root) + (blocksize - csum_size) - (char *) de;
1787
1788         /* Allocate new block for the 0th block's dirents */
1789         bh2 = ext4_append(handle, dir, &block);
1790         if (IS_ERR(bh2)) {
1791                 brelse(bh);
1792                 return PTR_ERR(bh2);
1793         }
1794         ext4_set_inode_flag(dir, EXT4_INODE_INDEX);
1795         data1 = bh2->b_data;
1796
1797         memcpy (data1, de, len);
1798         de = (struct ext4_dir_entry_2 *) data1;
1799         top = data1 + len;
1800         while ((char *)(de2 = ext4_next_entry(de, blocksize)) < top)
1801                 de = de2;
1802         de->rec_len = ext4_rec_len_to_disk(data1 + (blocksize - csum_size) -
1803                                            (char *) de,
1804                                            blocksize);
1805
1806         if (csum_size) {
1807                 t = EXT4_DIRENT_TAIL(data1, blocksize);
1808                 initialize_dirent_tail(t, blocksize);
1809         }
1810
1811         /* Initialize the root; the dot dirents already exist */
1812         de = (struct ext4_dir_entry_2 *) (&root->dotdot);
1813         de->rec_len = ext4_rec_len_to_disk(blocksize - EXT4_DIR_REC_LEN(2),
1814                                            blocksize);
1815         memset (&root->info, 0, sizeof(root->info));
1816         root->info.info_length = sizeof(root->info);
1817         root->info.hash_version = EXT4_SB(dir->i_sb)->s_def_hash_version;
1818         entries = root->entries;
1819         dx_set_block(entries, 1);
1820         dx_set_count(entries, 1);
1821         dx_set_limit(entries, dx_root_limit(dir, sizeof(root->info)));
1822
1823         /* Initialize as for dx_probe */
1824         hinfo.hash_version = root->info.hash_version;
1825         if (hinfo.hash_version <= DX_HASH_TEA)
1826                 hinfo.hash_version += EXT4_SB(dir->i_sb)->s_hash_unsigned;
1827         hinfo.seed = EXT4_SB(dir->i_sb)->s_hash_seed;
1828         ext4fs_dirhash(name, namelen, &hinfo);
1829         frame = frames;
1830         frame->entries = entries;
1831         frame->at = entries;
1832         frame->bh = bh;
1833         bh = bh2;
1834
1835         ext4_handle_dirty_dx_node(handle, dir, frame->bh);
1836         ext4_handle_dirty_dirent_node(handle, dir, bh);
1837
1838         de = do_split(handle,dir, &bh, frame, &hinfo);
1839         if (IS_ERR(de)) {
1840                 /*
1841                  * Even if the block split failed, we have to properly write
1842                  * out all the changes we did so far. Otherwise we can end up
1843                  * with corrupted filesystem.
1844                  */
1845                 ext4_mark_inode_dirty(handle, dir);
1846                 dx_release(frames);
1847                 return PTR_ERR(de);
1848         }
1849         dx_release(frames);
1850
1851         retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
1852         brelse(bh);
1853         return retval;
1854 }
1855
1856 /*
1857  *      ext4_add_entry()
1858  *
1859  * adds a file entry to the specified directory, using the same
1860  * semantics as ext4_find_entry(). It returns NULL if it failed.
1861  *
1862  * NOTE!! The inode part of 'de' is left at 0 - which means you
1863  * may not sleep between calling this and putting something into
1864  * the entry, as someone else might have used it while you slept.
1865  */
1866 static int ext4_add_entry(handle_t *handle, struct dentry *dentry,
1867                           struct inode *inode)
1868 {
1869         struct inode *dir = dentry->d_parent->d_inode;
1870         struct buffer_head *bh;
1871         struct ext4_dir_entry_2 *de;
1872         struct ext4_dir_entry_tail *t;
1873         struct super_block *sb;
1874         int     retval;
1875         int     dx_fallback=0;
1876         unsigned blocksize;
1877         ext4_lblk_t block, blocks;
1878         int     csum_size = 0;
1879
1880         if (EXT4_HAS_RO_COMPAT_FEATURE(inode->i_sb,
1881                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
1882                 csum_size = sizeof(struct ext4_dir_entry_tail);
1883
1884         sb = dir->i_sb;
1885         blocksize = sb->s_blocksize;
1886         if (!dentry->d_name.len)
1887                 return -EINVAL;
1888
1889         if (ext4_has_inline_data(dir)) {
1890                 retval = ext4_try_add_inline_entry(handle, dentry, inode);
1891                 if (retval < 0)
1892                         return retval;
1893                 if (retval == 1) {
1894                         retval = 0;
1895                         return retval;
1896                 }
1897         }
1898
1899         if (is_dx(dir)) {
1900                 retval = ext4_dx_add_entry(handle, dentry, inode);
1901                 if (!retval || (retval != ERR_BAD_DX_DIR))
1902                         return retval;
1903                 ext4_clear_inode_flag(dir, EXT4_INODE_INDEX);
1904                 dx_fallback++;
1905                 ext4_mark_inode_dirty(handle, dir);
1906         }
1907         blocks = dir->i_size >> sb->s_blocksize_bits;
1908         for (block = 0; block < blocks; block++) {
1909                 bh = ext4_read_dirblock(dir, block, DIRENT);
1910                 if (IS_ERR(bh))
1911                         return PTR_ERR(bh);
1912
1913                 retval = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1914                 if (retval != -ENOSPC) {
1915                         brelse(bh);
1916                         return retval;
1917                 }
1918
1919                 if (blocks == 1 && !dx_fallback &&
1920                     EXT4_HAS_COMPAT_FEATURE(sb, EXT4_FEATURE_COMPAT_DIR_INDEX))
1921                         return make_indexed_dir(handle, dentry, inode, bh);
1922                 brelse(bh);
1923         }
1924         bh = ext4_append(handle, dir, &block);
1925         if (IS_ERR(bh))
1926                 return PTR_ERR(bh);
1927         de = (struct ext4_dir_entry_2 *) bh->b_data;
1928         de->inode = 0;
1929         de->rec_len = ext4_rec_len_to_disk(blocksize - csum_size, blocksize);
1930
1931         if (csum_size) {
1932                 t = EXT4_DIRENT_TAIL(bh->b_data, blocksize);
1933                 initialize_dirent_tail(t, blocksize);
1934         }
1935
1936         retval = add_dirent_to_buf(handle, dentry, inode, de, bh);
1937         brelse(bh);
1938         if (retval == 0)
1939                 ext4_set_inode_state(inode, EXT4_STATE_NEWENTRY);
1940         return retval;
1941 }
1942
1943 /*
1944  * Returns 0 for success, or a negative error value
1945  */
1946 static int ext4_dx_add_entry(handle_t *handle, struct dentry *dentry,
1947                              struct inode *inode)
1948 {
1949         struct dx_frame frames[2], *frame;
1950         struct dx_entry *entries, *at;
1951         struct dx_hash_info hinfo;
1952         struct buffer_head *bh;
1953         struct inode *dir = dentry->d_parent->d_inode;
1954         struct super_block *sb = dir->i_sb;
1955         struct ext4_dir_entry_2 *de;
1956         int err;
1957
1958         frame = dx_probe(&dentry->d_name, dir, &hinfo, frames);
1959         if (IS_ERR(frame))
1960                 return PTR_ERR(frame);
1961         entries = frame->entries;
1962         at = frame->at;
1963         bh = ext4_read_dirblock(dir, dx_get_block(frame->at), DIRENT);
1964         if (IS_ERR(bh)) {
1965                 err = PTR_ERR(bh);
1966                 bh = NULL;
1967                 goto cleanup;
1968         }
1969
1970         BUFFER_TRACE(bh, "get_write_access");
1971         err = ext4_journal_get_write_access(handle, bh);
1972         if (err)
1973                 goto journal_error;
1974
1975         err = add_dirent_to_buf(handle, dentry, inode, NULL, bh);
1976         if (err != -ENOSPC)
1977                 goto cleanup;
1978
1979         /* Block full, should compress but for now just split */
1980         dxtrace(printk(KERN_DEBUG "using %u of %u node entries\n",
1981                        dx_get_count(entries), dx_get_limit(entries)));
1982         /* Need to split index? */
1983         if (dx_get_count(entries) == dx_get_limit(entries)) {
1984                 ext4_lblk_t newblock;
1985                 unsigned icount = dx_get_count(entries);
1986                 int levels = frame - frames;
1987                 struct dx_entry *entries2;
1988                 struct dx_node *node2;
1989                 struct buffer_head *bh2;
1990
1991                 if (levels && (dx_get_count(frames->entries) ==
1992                                dx_get_limit(frames->entries))) {
1993                         ext4_warning(sb, "Directory index full!");
1994                         err = -ENOSPC;
1995                         goto cleanup;
1996                 }
1997                 bh2 = ext4_append(handle, dir, &newblock);
1998                 if (IS_ERR(bh2)) {
1999                         err = PTR_ERR(bh2);
2000                         goto cleanup;
2001                 }
2002                 node2 = (struct dx_node *)(bh2->b_data);
2003                 entries2 = node2->entries;
2004                 memset(&node2->fake, 0, sizeof(struct fake_dirent));
2005                 node2->fake.rec_len = ext4_rec_len_to_disk(sb->s_blocksize,
2006                                                            sb->s_blocksize);
2007                 BUFFER_TRACE(frame->bh, "get_write_access");
2008                 err = ext4_journal_get_write_access(handle, frame->bh);
2009                 if (err)
2010                         goto journal_error;
2011                 if (levels) {
2012                         unsigned icount1 = icount/2, icount2 = icount - icount1;
2013                         unsigned hash2 = dx_get_hash(entries + icount1);
2014                         dxtrace(printk(KERN_DEBUG "Split index %i/%i\n",
2015                                        icount1, icount2));
2016
2017                         BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
2018                         err = ext4_journal_get_write_access(handle,
2019                                                              frames[0].bh);
2020                         if (err)
2021                                 goto journal_error;
2022
2023                         memcpy((char *) entries2, (char *) (entries + icount1),
2024                                icount2 * sizeof(struct dx_entry));
2025                         dx_set_count(entries, icount1);
2026                         dx_set_count(entries2, icount2);
2027                         dx_set_limit(entries2, dx_node_limit(dir));
2028
2029                         /* Which index block gets the new entry? */
2030                         if (at - entries >= icount1) {
2031                                 frame->at = at = at - entries - icount1 + entries2;
2032                                 frame->entries = entries = entries2;
2033                                 swap(frame->bh, bh2);
2034                         }
2035                         dx_insert_block(frames + 0, hash2, newblock);
2036                         dxtrace(dx_show_index("node", frames[1].entries));
2037                         dxtrace(dx_show_index("node",
2038                                ((struct dx_node *) bh2->b_data)->entries));
2039                         err = ext4_handle_dirty_dx_node(handle, dir, bh2);
2040                         if (err)
2041                                 goto journal_error;
2042                         brelse (bh2);
2043                 } else {
2044                         dxtrace(printk(KERN_DEBUG
2045                                        "Creating second level index...\n"));
2046                         memcpy((char *) entries2, (char *) entries,
2047                                icount * sizeof(struct dx_entry));
2048                         dx_set_limit(entries2, dx_node_limit(dir));
2049
2050                         /* Set up root */
2051                         dx_set_count(entries, 1);
2052                         dx_set_block(entries + 0, newblock);
2053                         ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
2054
2055                         /* Add new access path frame */
2056                         frame = frames + 1;
2057                         frame->at = at = at - entries + entries2;
2058                         frame->entries = entries = entries2;
2059                         frame->bh = bh2;
2060                         err = ext4_journal_get_write_access(handle,
2061                                                              frame->bh);
2062                         if (err)
2063                                 goto journal_error;
2064                 }
2065                 err = ext4_handle_dirty_dx_node(handle, dir, frames[0].bh);
2066                 if (err) {
2067                         ext4_std_error(inode->i_sb, err);
2068                         goto cleanup;
2069                 }
2070         }
2071         de = do_split(handle, dir, &bh, frame, &hinfo);
2072         if (IS_ERR(de)) {
2073                 err = PTR_ERR(de);
2074                 goto cleanup;
2075         }
2076         err = add_dirent_to_buf(handle, dentry, inode, de, bh);
2077         goto cleanup;
2078
2079 journal_error:
2080         ext4_std_error(dir->i_sb, err);
2081 cleanup:
2082         brelse(bh);
2083         dx_release(frames);
2084         return err;
2085 }
2086
2087 /*
2088  * ext4_generic_delete_entry deletes a directory entry by merging it
2089  * with the previous entry
2090  */
2091 int ext4_generic_delete_entry(handle_t *handle,
2092                               struct inode *dir,
2093                               struct ext4_dir_entry_2 *de_del,
2094                               struct buffer_head *bh,
2095                               void *entry_buf,
2096                               int buf_size,
2097                               int csum_size)
2098 {
2099         struct ext4_dir_entry_2 *de, *pde;
2100         unsigned int blocksize = dir->i_sb->s_blocksize;
2101         int i;
2102
2103         i = 0;
2104         pde = NULL;
2105         de = (struct ext4_dir_entry_2 *)entry_buf;
2106         while (i < buf_size - csum_size) {
2107                 if (ext4_check_dir_entry(dir, NULL, de, bh,
2108                                          bh->b_data, bh->b_size, i))
2109                         return -EIO;
2110                 if (de == de_del)  {
2111                         if (pde)
2112                                 pde->rec_len = ext4_rec_len_to_disk(
2113                                         ext4_rec_len_from_disk(pde->rec_len,
2114                                                                blocksize) +
2115                                         ext4_rec_len_from_disk(de->rec_len,
2116                                                                blocksize),
2117                                         blocksize);
2118                         else
2119                                 de->inode = 0;
2120                         dir->i_version++;
2121                         return 0;
2122                 }
2123                 i += ext4_rec_len_from_disk(de->rec_len, blocksize);
2124                 pde = de;
2125                 de = ext4_next_entry(de, blocksize);
2126         }
2127         return -ENOENT;
2128 }
2129
2130 static int ext4_delete_entry(handle_t *handle,
2131                              struct inode *dir,
2132                              struct ext4_dir_entry_2 *de_del,
2133                              struct buffer_head *bh)
2134 {
2135         int err, csum_size = 0;
2136
2137         if (ext4_has_inline_data(dir)) {
2138                 int has_inline_data = 1;
2139                 err = ext4_delete_inline_entry(handle, dir, de_del, bh,
2140                                                &has_inline_data);
2141                 if (has_inline_data)
2142                         return err;
2143         }
2144
2145         if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
2146                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
2147                 csum_size = sizeof(struct ext4_dir_entry_tail);
2148
2149         BUFFER_TRACE(bh, "get_write_access");
2150         err = ext4_journal_get_write_access(handle, bh);
2151         if (unlikely(err))
2152                 goto out;
2153
2154         err = ext4_generic_delete_entry(handle, dir, de_del,
2155                                         bh, bh->b_data,
2156                                         dir->i_sb->s_blocksize, csum_size);
2157         if (err)
2158                 goto out;
2159
2160         BUFFER_TRACE(bh, "call ext4_handle_dirty_metadata");
2161         err = ext4_handle_dirty_dirent_node(handle, dir, bh);
2162         if (unlikely(err))
2163                 goto out;
2164
2165         return 0;
2166 out:
2167         if (err != -ENOENT)
2168                 ext4_std_error(dir->i_sb, err);
2169         return err;
2170 }
2171
2172 /*
2173  * DIR_NLINK feature is set if 1) nlinks > EXT4_LINK_MAX or 2) nlinks == 2,
2174  * since this indicates that nlinks count was previously 1.
2175  */
2176 static void ext4_inc_count(handle_t *handle, struct inode *inode)
2177 {
2178         inc_nlink(inode);
2179         if (is_dx(inode) && inode->i_nlink > 1) {
2180                 /* limit is 16-bit i_links_count */
2181                 if (inode->i_nlink >= EXT4_LINK_MAX || inode->i_nlink == 2) {
2182                         set_nlink(inode, 1);
2183                         EXT4_SET_RO_COMPAT_FEATURE(inode->i_sb,
2184                                               EXT4_FEATURE_RO_COMPAT_DIR_NLINK);
2185                 }
2186         }
2187 }
2188
2189 /*
2190  * If a directory had nlink == 1, then we should let it be 1. This indicates
2191  * directory has >EXT4_LINK_MAX subdirs.
2192  */
2193 static void ext4_dec_count(handle_t *handle, struct inode *inode)
2194 {
2195         if (!S_ISDIR(inode->i_mode) || inode->i_nlink > 2)
2196                 drop_nlink(inode);
2197 }
2198
2199
2200 static int ext4_add_nondir(handle_t *handle,
2201                 struct dentry *dentry, struct inode *inode)
2202 {
2203         int err = ext4_add_entry(handle, dentry, inode);
2204         if (!err) {
2205                 ext4_mark_inode_dirty(handle, inode);
2206                 unlock_new_inode(inode);
2207                 d_instantiate(dentry, inode);
2208                 return 0;
2209         }
2210         drop_nlink(inode);
2211         unlock_new_inode(inode);
2212         iput(inode);
2213         return err;
2214 }
2215
2216 /*
2217  * By the time this is called, we already have created
2218  * the directory cache entry for the new file, but it
2219  * is so far negative - it has no inode.
2220  *
2221  * If the create succeeds, we fill in the inode information
2222  * with d_instantiate().
2223  */
2224 static int ext4_create(struct inode *dir, struct dentry *dentry, umode_t mode,
2225                        bool excl)
2226 {
2227         handle_t *handle;
2228         struct inode *inode;
2229         int err, credits, retries = 0;
2230
2231         dquot_initialize(dir);
2232
2233         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2234                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2235 retry:
2236         inode = ext4_new_inode_start_handle(dir, mode, &dentry->d_name, 0,
2237                                             NULL, EXT4_HT_DIR, credits);
2238         handle = ext4_journal_current_handle();
2239         err = PTR_ERR(inode);
2240         if (!IS_ERR(inode)) {
2241                 inode->i_op = &ext4_file_inode_operations;
2242                 inode->i_fop = &ext4_file_operations;
2243                 ext4_set_aops(inode);
2244                 err = ext4_add_nondir(handle, dentry, inode);
2245                 if (!err && IS_DIRSYNC(dir))
2246                         ext4_handle_sync(handle);
2247         }
2248         if (handle)
2249                 ext4_journal_stop(handle);
2250         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2251                 goto retry;
2252         return err;
2253 }
2254
2255 static int ext4_mknod(struct inode *dir, struct dentry *dentry,
2256                       umode_t mode, dev_t rdev)
2257 {
2258         handle_t *handle;
2259         struct inode *inode;
2260         int err, credits, retries = 0;
2261
2262         if (!new_valid_dev(rdev))
2263                 return -EINVAL;
2264
2265         dquot_initialize(dir);
2266
2267         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2268                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2269 retry:
2270         inode = ext4_new_inode_start_handle(dir, mode, &dentry->d_name, 0,
2271                                             NULL, EXT4_HT_DIR, credits);
2272         handle = ext4_journal_current_handle();
2273         err = PTR_ERR(inode);
2274         if (!IS_ERR(inode)) {
2275                 init_special_inode(inode, inode->i_mode, rdev);
2276                 inode->i_op = &ext4_special_inode_operations;
2277                 err = ext4_add_nondir(handle, dentry, inode);
2278                 if (!err && IS_DIRSYNC(dir))
2279                         ext4_handle_sync(handle);
2280         }
2281         if (handle)
2282                 ext4_journal_stop(handle);
2283         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2284                 goto retry;
2285         return err;
2286 }
2287
2288 static int ext4_tmpfile(struct inode *dir, struct dentry *dentry, umode_t mode)
2289 {
2290         handle_t *handle;
2291         struct inode *inode;
2292         int err, retries = 0;
2293
2294         dquot_initialize(dir);
2295
2296 retry:
2297         inode = ext4_new_inode_start_handle(dir, mode,
2298                                             NULL, 0, NULL,
2299                                             EXT4_HT_DIR,
2300                         EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
2301                           4 + EXT4_XATTR_TRANS_BLOCKS);
2302         handle = ext4_journal_current_handle();
2303         err = PTR_ERR(inode);
2304         if (!IS_ERR(inode)) {
2305                 inode->i_op = &ext4_file_inode_operations;
2306                 inode->i_fop = &ext4_file_operations;
2307                 ext4_set_aops(inode);
2308                 d_tmpfile(dentry, inode);
2309                 err = ext4_orphan_add(handle, inode);
2310                 if (err)
2311                         goto err_unlock_inode;
2312                 mark_inode_dirty(inode);
2313                 unlock_new_inode(inode);
2314         }
2315         if (handle)
2316                 ext4_journal_stop(handle);
2317         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2318                 goto retry;
2319         return err;
2320 err_unlock_inode:
2321         ext4_journal_stop(handle);
2322         unlock_new_inode(inode);
2323         return err;
2324 }
2325
2326 struct ext4_dir_entry_2 *ext4_init_dot_dotdot(struct inode *inode,
2327                           struct ext4_dir_entry_2 *de,
2328                           int blocksize, int csum_size,
2329                           unsigned int parent_ino, int dotdot_real_len)
2330 {
2331         de->inode = cpu_to_le32(inode->i_ino);
2332         de->name_len = 1;
2333         de->rec_len = ext4_rec_len_to_disk(EXT4_DIR_REC_LEN(de->name_len),
2334                                            blocksize);
2335         strcpy(de->name, ".");
2336         ext4_set_de_type(inode->i_sb, de, S_IFDIR);
2337
2338         de = ext4_next_entry(de, blocksize);
2339         de->inode = cpu_to_le32(parent_ino);
2340         de->name_len = 2;
2341         if (!dotdot_real_len)
2342                 de->rec_len = ext4_rec_len_to_disk(blocksize -
2343                                         (csum_size + EXT4_DIR_REC_LEN(1)),
2344                                         blocksize);
2345         else
2346                 de->rec_len = ext4_rec_len_to_disk(
2347                                 EXT4_DIR_REC_LEN(de->name_len), blocksize);
2348         strcpy(de->name, "..");
2349         ext4_set_de_type(inode->i_sb, de, S_IFDIR);
2350
2351         return ext4_next_entry(de, blocksize);
2352 }
2353
2354 static int ext4_init_new_dir(handle_t *handle, struct inode *dir,
2355                              struct inode *inode)
2356 {
2357         struct buffer_head *dir_block = NULL;
2358         struct ext4_dir_entry_2 *de;
2359         struct ext4_dir_entry_tail *t;
2360         ext4_lblk_t block = 0;
2361         unsigned int blocksize = dir->i_sb->s_blocksize;
2362         int csum_size = 0;
2363         int err;
2364
2365         if (EXT4_HAS_RO_COMPAT_FEATURE(dir->i_sb,
2366                                        EXT4_FEATURE_RO_COMPAT_METADATA_CSUM))
2367                 csum_size = sizeof(struct ext4_dir_entry_tail);
2368
2369         if (ext4_test_inode_state(inode, EXT4_STATE_MAY_INLINE_DATA)) {
2370                 err = ext4_try_create_inline_dir(handle, dir, inode);
2371                 if (err < 0 && err != -ENOSPC)
2372                         goto out;
2373                 if (!err)
2374                         goto out;
2375         }
2376
2377         inode->i_size = 0;
2378         dir_block = ext4_append(handle, inode, &block);
2379         if (IS_ERR(dir_block))
2380                 return PTR_ERR(dir_block);
2381         de = (struct ext4_dir_entry_2 *)dir_block->b_data;
2382         ext4_init_dot_dotdot(inode, de, blocksize, csum_size, dir->i_ino, 0);
2383         set_nlink(inode, 2);
2384         if (csum_size) {
2385                 t = EXT4_DIRENT_TAIL(dir_block->b_data, blocksize);
2386                 initialize_dirent_tail(t, blocksize);
2387         }
2388
2389         BUFFER_TRACE(dir_block, "call ext4_handle_dirty_metadata");
2390         err = ext4_handle_dirty_dirent_node(handle, inode, dir_block);
2391         if (err)
2392                 goto out;
2393         set_buffer_verified(dir_block);
2394 out:
2395         brelse(dir_block);
2396         return err;
2397 }
2398
2399 static int ext4_mkdir(struct inode *dir, struct dentry *dentry, umode_t mode)
2400 {
2401         handle_t *handle;
2402         struct inode *inode;
2403         int err, credits, retries = 0;
2404
2405         if (EXT4_DIR_LINK_MAX(dir))
2406                 return -EMLINK;
2407
2408         dquot_initialize(dir);
2409
2410         credits = (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2411                    EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3);
2412 retry:
2413         inode = ext4_new_inode_start_handle(dir, S_IFDIR | mode,
2414                                             &dentry->d_name,
2415                                             0, NULL, EXT4_HT_DIR, credits);
2416         handle = ext4_journal_current_handle();
2417         err = PTR_ERR(inode);
2418         if (IS_ERR(inode))
2419                 goto out_stop;
2420
2421         inode->i_op = &ext4_dir_inode_operations;
2422         inode->i_fop = &ext4_dir_operations;
2423         err = ext4_init_new_dir(handle, dir, inode);
2424         if (err)
2425                 goto out_clear_inode;
2426         err = ext4_mark_inode_dirty(handle, inode);
2427         if (!err)
2428                 err = ext4_add_entry(handle, dentry, inode);
2429         if (err) {
2430 out_clear_inode:
2431                 clear_nlink(inode);
2432                 unlock_new_inode(inode);
2433                 ext4_mark_inode_dirty(handle, inode);
2434                 iput(inode);
2435                 goto out_stop;
2436         }
2437         ext4_inc_count(handle, dir);
2438         ext4_update_dx_flag(dir);
2439         err = ext4_mark_inode_dirty(handle, dir);
2440         if (err)
2441                 goto out_clear_inode;
2442         unlock_new_inode(inode);
2443         d_instantiate(dentry, inode);
2444         if (IS_DIRSYNC(dir))
2445                 ext4_handle_sync(handle);
2446
2447 out_stop:
2448         if (handle)
2449                 ext4_journal_stop(handle);
2450         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2451                 goto retry;
2452         return err;
2453 }
2454
2455 /*
2456  * routine to check that the specified directory is empty (for rmdir)
2457  */
2458 static int empty_dir(struct inode *inode)
2459 {
2460         unsigned int offset;
2461         struct buffer_head *bh;
2462         struct ext4_dir_entry_2 *de, *de1;
2463         struct super_block *sb;
2464         int err = 0;
2465
2466         if (ext4_has_inline_data(inode)) {
2467                 int has_inline_data = 1;
2468
2469                 err = empty_inline_dir(inode, &has_inline_data);
2470                 if (has_inline_data)
2471                         return err;
2472         }
2473
2474         sb = inode->i_sb;
2475         if (inode->i_size < EXT4_DIR_REC_LEN(1) + EXT4_DIR_REC_LEN(2)) {
2476                 EXT4_ERROR_INODE(inode, "invalid size");
2477                 return 1;
2478         }
2479         bh = ext4_read_dirblock(inode, 0, EITHER);
2480         if (IS_ERR(bh))
2481                 return 1;
2482
2483         de = (struct ext4_dir_entry_2 *) bh->b_data;
2484         de1 = ext4_next_entry(de, sb->s_blocksize);
2485         if (le32_to_cpu(de->inode) != inode->i_ino ||
2486                         !le32_to_cpu(de1->inode) ||
2487                         strcmp(".", de->name) ||
2488                         strcmp("..", de1->name)) {
2489                 ext4_warning(inode->i_sb,
2490                              "bad directory (dir #%lu) - no `.' or `..'",
2491                              inode->i_ino);
2492                 brelse(bh);
2493                 return 1;
2494         }
2495         offset = ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize) +
2496                  ext4_rec_len_from_disk(de1->rec_len, sb->s_blocksize);
2497         de = ext4_next_entry(de1, sb->s_blocksize);
2498         while (offset < inode->i_size) {
2499                 if ((void *) de >= (void *) (bh->b_data+sb->s_blocksize)) {
2500                         unsigned int lblock;
2501                         err = 0;
2502                         brelse(bh);
2503                         lblock = offset >> EXT4_BLOCK_SIZE_BITS(sb);
2504                         bh = ext4_read_dirblock(inode, lblock, EITHER);
2505                         if (IS_ERR(bh))
2506                                 return 1;
2507                         de = (struct ext4_dir_entry_2 *) bh->b_data;
2508                 }
2509                 if (ext4_check_dir_entry(inode, NULL, de, bh,
2510                                          bh->b_data, bh->b_size, offset)) {
2511                         de = (struct ext4_dir_entry_2 *)(bh->b_data +
2512                                                          sb->s_blocksize);
2513                         offset = (offset | (sb->s_blocksize - 1)) + 1;
2514                         continue;
2515                 }
2516                 if (le32_to_cpu(de->inode)) {
2517                         brelse(bh);
2518                         return 0;
2519                 }
2520                 offset += ext4_rec_len_from_disk(de->rec_len, sb->s_blocksize);
2521                 de = ext4_next_entry(de, sb->s_blocksize);
2522         }
2523         brelse(bh);
2524         return 1;
2525 }
2526
2527 /*
2528  * ext4_orphan_add() links an unlinked or truncated inode into a list of
2529  * such inodes, starting at the superblock, in case we crash before the
2530  * file is closed/deleted, or in case the inode truncate spans multiple
2531  * transactions and the last transaction is not recovered after a crash.
2532  *
2533  * At filesystem recovery time, we walk this list deleting unlinked
2534  * inodes and truncating linked inodes in ext4_orphan_cleanup().
2535  *
2536  * Orphan list manipulation functions must be called under i_mutex unless
2537  * we are just creating the inode or deleting it.
2538  */
2539 int ext4_orphan_add(handle_t *handle, struct inode *inode)
2540 {
2541         struct super_block *sb = inode->i_sb;
2542         struct ext4_sb_info *sbi = EXT4_SB(sb);
2543         struct ext4_iloc iloc;
2544         int err = 0, rc;
2545         bool dirty = false;
2546
2547         if (!sbi->s_journal)
2548                 return 0;
2549
2550         WARN_ON_ONCE(!(inode->i_state & (I_NEW | I_FREEING)) &&
2551                      !mutex_is_locked(&inode->i_mutex));
2552         /*
2553          * Exit early if inode already is on orphan list. This is a big speedup
2554          * since we don't have to contend on the global s_orphan_lock.
2555          */
2556         if (!list_empty(&EXT4_I(inode)->i_orphan))
2557                 return 0;
2558
2559         /*
2560          * Orphan handling is only valid for files with data blocks
2561          * being truncated, or files being unlinked. Note that we either
2562          * hold i_mutex, or the inode can not be referenced from outside,
2563          * so i_nlink should not be bumped due to race
2564          */
2565         J_ASSERT((S_ISREG(inode->i_mode) || S_ISDIR(inode->i_mode) ||
2566                   S_ISLNK(inode->i_mode)) || inode->i_nlink == 0);
2567
2568         BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2569         err = ext4_journal_get_write_access(handle, sbi->s_sbh);
2570         if (err)
2571                 goto out;
2572
2573         err = ext4_reserve_inode_write(handle, inode, &iloc);
2574         if (err)
2575                 goto out;
2576
2577         mutex_lock(&sbi->s_orphan_lock);
2578         /*
2579          * Due to previous errors inode may be already a part of on-disk
2580          * orphan list. If so skip on-disk list modification.
2581          */
2582         if (!NEXT_ORPHAN(inode) || NEXT_ORPHAN(inode) >
2583             (le32_to_cpu(sbi->s_es->s_inodes_count))) {
2584                 /* Insert this inode at the head of the on-disk orphan list */
2585                 NEXT_ORPHAN(inode) = le32_to_cpu(sbi->s_es->s_last_orphan);
2586                 sbi->s_es->s_last_orphan = cpu_to_le32(inode->i_ino);
2587                 dirty = true;
2588         }
2589         list_add(&EXT4_I(inode)->i_orphan, &sbi->s_orphan);
2590         mutex_unlock(&sbi->s_orphan_lock);
2591
2592         if (dirty) {
2593                 err = ext4_handle_dirty_super(handle, sb);
2594                 rc = ext4_mark_iloc_dirty(handle, inode, &iloc);
2595                 if (!err)
2596                         err = rc;
2597                 if (err) {
2598                         /*
2599                          * We have to remove inode from in-memory list if
2600                          * addition to on disk orphan list failed. Stray orphan
2601                          * list entries can cause panics at unmount time.
2602                          */
2603                         mutex_lock(&sbi->s_orphan_lock);
2604                         list_del(&EXT4_I(inode)->i_orphan);
2605                         mutex_unlock(&sbi->s_orphan_lock);
2606                 }
2607         }
2608         jbd_debug(4, "superblock will point to %lu\n", inode->i_ino);
2609         jbd_debug(4, "orphan inode %lu will point to %d\n",
2610                         inode->i_ino, NEXT_ORPHAN(inode));
2611 out:
2612         ext4_std_error(sb, err);
2613         return err;
2614 }
2615
2616 /*
2617  * ext4_orphan_del() removes an unlinked or truncated inode from the list
2618  * of such inodes stored on disk, because it is finally being cleaned up.
2619  */
2620 int ext4_orphan_del(handle_t *handle, struct inode *inode)
2621 {
2622         struct list_head *prev;
2623         struct ext4_inode_info *ei = EXT4_I(inode);
2624         struct ext4_sb_info *sbi = EXT4_SB(inode->i_sb);
2625         __u32 ino_next;
2626         struct ext4_iloc iloc;
2627         int err = 0;
2628
2629         if (!sbi->s_journal && !(sbi->s_mount_state & EXT4_ORPHAN_FS))
2630                 return 0;
2631
2632         WARN_ON_ONCE(!(inode->i_state & (I_NEW | I_FREEING)) &&
2633                      !mutex_is_locked(&inode->i_mutex));
2634         /* Do this quick check before taking global s_orphan_lock. */
2635         if (list_empty(&ei->i_orphan))
2636                 return 0;
2637
2638         if (handle) {
2639                 /* Grab inode buffer early before taking global s_orphan_lock */
2640                 err = ext4_reserve_inode_write(handle, inode, &iloc);
2641         }
2642
2643         mutex_lock(&sbi->s_orphan_lock);
2644         jbd_debug(4, "remove inode %lu from orphan list\n", inode->i_ino);
2645
2646         prev = ei->i_orphan.prev;
2647         list_del_init(&ei->i_orphan);
2648
2649         /* If we're on an error path, we may not have a valid
2650          * transaction handle with which to update the orphan list on
2651          * disk, but we still need to remove the inode from the linked
2652          * list in memory. */
2653         if (!handle || err) {
2654                 mutex_unlock(&sbi->s_orphan_lock);
2655                 goto out_err;
2656         }
2657
2658         ino_next = NEXT_ORPHAN(inode);
2659         if (prev == &sbi->s_orphan) {
2660                 jbd_debug(4, "superblock will point to %u\n", ino_next);
2661                 BUFFER_TRACE(sbi->s_sbh, "get_write_access");
2662                 err = ext4_journal_get_write_access(handle, sbi->s_sbh);
2663                 if (err) {
2664                         mutex_unlock(&sbi->s_orphan_lock);
2665                         goto out_brelse;
2666                 }
2667                 sbi->s_es->s_last_orphan = cpu_to_le32(ino_next);
2668                 mutex_unlock(&sbi->s_orphan_lock);
2669                 err = ext4_handle_dirty_super(handle, inode->i_sb);
2670         } else {
2671                 struct ext4_iloc iloc2;
2672                 struct inode *i_prev =
2673                         &list_entry(prev, struct ext4_inode_info, i_orphan)->vfs_inode;
2674
2675                 jbd_debug(4, "orphan inode %lu will point to %u\n",
2676                           i_prev->i_ino, ino_next);
2677                 err = ext4_reserve_inode_write(handle, i_prev, &iloc2);
2678                 if (err) {
2679                         mutex_unlock(&sbi->s_orphan_lock);
2680                         goto out_brelse;
2681                 }
2682                 NEXT_ORPHAN(i_prev) = ino_next;
2683                 err = ext4_mark_iloc_dirty(handle, i_prev, &iloc2);
2684                 mutex_unlock(&sbi->s_orphan_lock);
2685         }
2686         if (err)
2687                 goto out_brelse;
2688         NEXT_ORPHAN(inode) = 0;
2689         err = ext4_mark_iloc_dirty(handle, inode, &iloc);
2690 out_err:
2691         ext4_std_error(inode->i_sb, err);
2692         return err;
2693
2694 out_brelse:
2695         brelse(iloc.bh);
2696         goto out_err;
2697 }
2698
2699 static int ext4_rmdir(struct inode *dir, struct dentry *dentry)
2700 {
2701         int retval;
2702         struct inode *inode;
2703         struct buffer_head *bh;
2704         struct ext4_dir_entry_2 *de;
2705         handle_t *handle = NULL;
2706
2707         /* Initialize quotas before so that eventual writes go in
2708          * separate transaction */
2709         dquot_initialize(dir);
2710         dquot_initialize(dentry->d_inode);
2711
2712         retval = -ENOENT;
2713         bh = ext4_find_entry(dir, &dentry->d_name, &de, NULL);
2714         if (IS_ERR(bh))
2715                 return PTR_ERR(bh);
2716         if (!bh)
2717                 goto end_rmdir;
2718
2719         inode = dentry->d_inode;
2720
2721         retval = -EIO;
2722         if (le32_to_cpu(de->inode) != inode->i_ino)
2723                 goto end_rmdir;
2724
2725         retval = -ENOTEMPTY;
2726         if (!empty_dir(inode))
2727                 goto end_rmdir;
2728
2729         handle = ext4_journal_start(dir, EXT4_HT_DIR,
2730                                     EXT4_DATA_TRANS_BLOCKS(dir->i_sb));
2731         if (IS_ERR(handle)) {
2732                 retval = PTR_ERR(handle);
2733                 handle = NULL;
2734                 goto end_rmdir;
2735         }
2736
2737         if (IS_DIRSYNC(dir))
2738                 ext4_handle_sync(handle);
2739
2740         retval = ext4_delete_entry(handle, dir, de, bh);
2741         if (retval)
2742                 goto end_rmdir;
2743         if (!EXT4_DIR_LINK_EMPTY(inode))
2744                 ext4_warning(inode->i_sb,
2745                              "empty directory has too many links (%d)",
2746                              inode->i_nlink);
2747         inode->i_version++;
2748         clear_nlink(inode);
2749         /* There's no need to set i_disksize: the fact that i_nlink is
2750          * zero will ensure that the right thing happens during any
2751          * recovery. */
2752         inode->i_size = 0;
2753         ext4_orphan_add(handle, inode);
2754         inode->i_ctime = dir->i_ctime = dir->i_mtime = ext4_current_time(inode);
2755         ext4_mark_inode_dirty(handle, inode);
2756         ext4_dec_count(handle, dir);
2757         ext4_update_dx_flag(dir);
2758         ext4_mark_inode_dirty(handle, dir);
2759
2760 end_rmdir:
2761         brelse(bh);
2762         if (handle)
2763                 ext4_journal_stop(handle);
2764         return retval;
2765 }
2766
2767 static int ext4_unlink(struct inode *dir, struct dentry *dentry)
2768 {
2769         int retval;
2770         struct inode *inode;
2771         struct buffer_head *bh;
2772         struct ext4_dir_entry_2 *de;
2773         handle_t *handle = NULL;
2774
2775         trace_ext4_unlink_enter(dir, dentry);
2776         /* Initialize quotas before so that eventual writes go
2777          * in separate transaction */
2778         dquot_initialize(dir);
2779         dquot_initialize(dentry->d_inode);
2780
2781         retval = -ENOENT;
2782         bh = ext4_find_entry(dir, &dentry->d_name, &de, NULL);
2783         if (IS_ERR(bh))
2784                 return PTR_ERR(bh);
2785         if (!bh)
2786                 goto end_unlink;
2787
2788         inode = dentry->d_inode;
2789
2790         retval = -EIO;
2791         if (le32_to_cpu(de->inode) != inode->i_ino)
2792                 goto end_unlink;
2793
2794         handle = ext4_journal_start(dir, EXT4_HT_DIR,
2795                                     EXT4_DATA_TRANS_BLOCKS(dir->i_sb));
2796         if (IS_ERR(handle)) {
2797                 retval = PTR_ERR(handle);
2798                 handle = NULL;
2799                 goto end_unlink;
2800         }
2801
2802         if (IS_DIRSYNC(dir))
2803                 ext4_handle_sync(handle);
2804
2805         if (!inode->i_nlink) {
2806                 ext4_warning(inode->i_sb,
2807                              "Deleting nonexistent file (%lu), %d",
2808                              inode->i_ino, inode->i_nlink);
2809                 set_nlink(inode, 1);
2810         }
2811         retval = ext4_delete_entry(handle, dir, de, bh);
2812         if (retval)
2813                 goto end_unlink;
2814         dir->i_ctime = dir->i_mtime = ext4_current_time(dir);
2815         ext4_update_dx_flag(dir);
2816         ext4_mark_inode_dirty(handle, dir);
2817         drop_nlink(inode);
2818         if (!inode->i_nlink)
2819                 ext4_orphan_add(handle, inode);
2820         inode->i_ctime = ext4_current_time(inode);
2821         ext4_mark_inode_dirty(handle, inode);
2822         retval = 0;
2823
2824 end_unlink:
2825         brelse(bh);
2826         if (handle)
2827                 ext4_journal_stop(handle);
2828         trace_ext4_unlink_exit(dentry, retval);
2829         return retval;
2830 }
2831
2832 static int ext4_symlink(struct inode *dir,
2833                         struct dentry *dentry, const char *symname)
2834 {
2835         handle_t *handle;
2836         struct inode *inode;
2837         int l, err, retries = 0;
2838         int credits;
2839
2840         l = strlen(symname)+1;
2841         if (l > dir->i_sb->s_blocksize)
2842                 return -ENAMETOOLONG;
2843
2844         dquot_initialize(dir);
2845
2846         if (l > EXT4_N_BLOCKS * 4) {
2847                 /*
2848                  * For non-fast symlinks, we just allocate inode and put it on
2849                  * orphan list in the first transaction => we need bitmap,
2850                  * group descriptor, sb, inode block, quota blocks, and
2851                  * possibly selinux xattr blocks.
2852                  */
2853                 credits = 4 + EXT4_MAXQUOTAS_INIT_BLOCKS(dir->i_sb) +
2854                           EXT4_XATTR_TRANS_BLOCKS;
2855         } else {
2856                 /*
2857                  * Fast symlink. We have to add entry to directory
2858                  * (EXT4_DATA_TRANS_BLOCKS + EXT4_INDEX_EXTRA_TRANS_BLOCKS),
2859                  * allocate new inode (bitmap, group descriptor, inode block,
2860                  * quota blocks, sb is already counted in previous macros).
2861                  */
2862                 credits = EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2863                           EXT4_INDEX_EXTRA_TRANS_BLOCKS + 3;
2864         }
2865 retry:
2866         inode = ext4_new_inode_start_handle(dir, S_IFLNK|S_IRWXUGO,
2867                                             &dentry->d_name, 0, NULL,
2868                                             EXT4_HT_DIR, credits);
2869         handle = ext4_journal_current_handle();
2870         err = PTR_ERR(inode);
2871         if (IS_ERR(inode))
2872                 goto out_stop;
2873
2874         if (l > EXT4_N_BLOCKS * 4) {
2875                 inode->i_op = &ext4_symlink_inode_operations;
2876                 ext4_set_aops(inode);
2877                 /*
2878                  * We cannot call page_symlink() with transaction started
2879                  * because it calls into ext4_write_begin() which can wait
2880                  * for transaction commit if we are running out of space
2881                  * and thus we deadlock. So we have to stop transaction now
2882                  * and restart it when symlink contents is written.
2883                  *
2884                  * To keep fs consistent in case of crash, we have to put inode
2885                  * to orphan list in the mean time.
2886                  */
2887                 drop_nlink(inode);
2888                 err = ext4_orphan_add(handle, inode);
2889                 ext4_journal_stop(handle);
2890                 if (err)
2891                         goto err_drop_inode;
2892                 err = __page_symlink(inode, symname, l, 1);
2893                 if (err)
2894                         goto err_drop_inode;
2895                 /*
2896                  * Now inode is being linked into dir (EXT4_DATA_TRANS_BLOCKS
2897                  * + EXT4_INDEX_EXTRA_TRANS_BLOCKS), inode is also modified
2898                  */
2899                 handle = ext4_journal_start(dir, EXT4_HT_DIR,
2900                                 EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2901                                 EXT4_INDEX_EXTRA_TRANS_BLOCKS + 1);
2902                 if (IS_ERR(handle)) {
2903                         err = PTR_ERR(handle);
2904                         goto err_drop_inode;
2905                 }
2906                 set_nlink(inode, 1);
2907                 err = ext4_orphan_del(handle, inode);
2908                 if (err) {
2909                         ext4_journal_stop(handle);
2910                         clear_nlink(inode);
2911                         goto err_drop_inode;
2912                 }
2913         } else {
2914                 /* clear the extent format for fast symlink */
2915                 ext4_clear_inode_flag(inode, EXT4_INODE_EXTENTS);
2916                 inode->i_op = &ext4_fast_symlink_inode_operations;
2917                 memcpy((char *)&EXT4_I(inode)->i_data, symname, l);
2918                 inode->i_size = l-1;
2919         }
2920         EXT4_I(inode)->i_disksize = inode->i_size;
2921         err = ext4_add_nondir(handle, dentry, inode);
2922         if (!err && IS_DIRSYNC(dir))
2923                 ext4_handle_sync(handle);
2924
2925 out_stop:
2926         if (handle)
2927                 ext4_journal_stop(handle);
2928         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2929                 goto retry;
2930         return err;
2931 err_drop_inode:
2932         unlock_new_inode(inode);
2933         iput(inode);
2934         return err;
2935 }
2936
2937 static int ext4_link(struct dentry *old_dentry,
2938                      struct inode *dir, struct dentry *dentry)
2939 {
2940         handle_t *handle;
2941         struct inode *inode = old_dentry->d_inode;
2942         int err, retries = 0;
2943
2944         if (inode->i_nlink >= EXT4_LINK_MAX)
2945                 return -EMLINK;
2946
2947         dquot_initialize(dir);
2948
2949 retry:
2950         handle = ext4_journal_start(dir, EXT4_HT_DIR,
2951                 (EXT4_DATA_TRANS_BLOCKS(dir->i_sb) +
2952                  EXT4_INDEX_EXTRA_TRANS_BLOCKS) + 1);
2953         if (IS_ERR(handle))
2954                 return PTR_ERR(handle);
2955
2956         if (IS_DIRSYNC(dir))
2957                 ext4_handle_sync(handle);
2958
2959         inode->i_ctime = ext4_current_time(inode);
2960         ext4_inc_count(handle, inode);
2961         ihold(inode);
2962
2963         err = ext4_add_entry(handle, dentry, inode);
2964         if (!err) {
2965                 ext4_mark_inode_dirty(handle, inode);
2966                 /* this can happen only for tmpfile being
2967                  * linked the first time
2968                  */
2969                 if (inode->i_nlink == 1)
2970                         ext4_orphan_del(handle, inode);
2971                 d_instantiate(dentry, inode);
2972         } else {
2973                 drop_nlink(inode);
2974                 iput(inode);
2975         }
2976         ext4_journal_stop(handle);
2977         if (err == -ENOSPC && ext4_should_retry_alloc(dir->i_sb, &retries))
2978                 goto retry;
2979         return err;
2980 }
2981
2982
2983 /*
2984  * Try to find buffer head where contains the parent block.
2985  * It should be the inode block if it is inlined or the 1st block
2986  * if it is a normal dir.
2987  */
2988 static struct buffer_head *ext4_get_first_dir_block(handle_t *handle,
2989                                         struct inode *inode,
2990                                         int *retval,
2991                                         struct ext4_dir_entry_2 **parent_de,
2992                                         int *inlined)
2993 {
2994         struct buffer_head *bh;
2995
2996         if (!ext4_has_inline_data(inode)) {
2997                 bh = ext4_read_dirblock(inode, 0, EITHER);
2998                 if (IS_ERR(bh)) {
2999                         *retval = PTR_ERR(bh);
3000                         return NULL;
3001                 }
3002                 *parent_de = ext4_next_entry(
3003                                         (struct ext4_dir_entry_2 *)bh->b_data,
3004                                         inode->i_sb->s_blocksize);
3005                 return bh;
3006         }
3007
3008         *inlined = 1;
3009         return ext4_get_first_inline_block(inode, parent_de, retval);
3010 }
3011
3012 struct ext4_renament {
3013         struct inode *dir;
3014         struct dentry *dentry;
3015         struct inode *inode;
3016         bool is_dir;
3017         int dir_nlink_delta;
3018
3019         /* entry for "dentry" */
3020         struct buffer_head *bh;
3021         struct ext4_dir_entry_2 *de;
3022         int inlined;
3023
3024         /* entry for ".." in inode if it's a directory */
3025         struct buffer_head *dir_bh;
3026         struct ext4_dir_entry_2 *parent_de;
3027         int dir_inlined;
3028 };
3029
3030 static int ext4_rename_dir_prepare(handle_t *handle, struct ext4_renament *ent)
3031 {
3032         int retval;
3033
3034         ent->dir_bh = ext4_get_first_dir_block(handle, ent->inode,
3035                                               &retval, &ent->parent_de,
3036                                               &ent->dir_inlined);
3037         if (!ent->dir_bh)
3038                 return retval;
3039         if (le32_to_cpu(ent->parent_de->inode) != ent->dir->i_ino)
3040                 return -EIO;
3041         BUFFER_TRACE(ent->dir_bh, "get_write_access");
3042         return ext4_journal_get_write_access(handle, ent->dir_bh);
3043 }
3044
3045 static int ext4_rename_dir_finish(handle_t *handle, struct ext4_renament *ent,
3046                                   unsigned dir_ino)
3047 {
3048         int retval;
3049
3050         ent->parent_de->inode = cpu_to_le32(dir_ino);
3051         BUFFER_TRACE(ent->dir_bh, "call ext4_handle_dirty_metadata");
3052         if (!ent->dir_inlined) {
3053                 if (is_dx(ent->inode)) {
3054                         retval = ext4_handle_dirty_dx_node(handle,
3055                                                            ent->inode,
3056                                                            ent->dir_bh);
3057                 } else {
3058                         retval = ext4_handle_dirty_dirent_node(handle,
3059                                                                ent->inode,
3060                                                                ent->dir_bh);
3061                 }
3062         } else {
3063                 retval = ext4_mark_inode_dirty(handle, ent->inode);
3064         }
3065         if (retval) {
3066                 ext4_std_error(ent->dir->i_sb, retval);
3067                 return retval;
3068         }
3069         return 0;
3070 }
3071
3072 static int ext4_setent(handle_t *handle, struct ext4_renament *ent,
3073                        unsigned ino, unsigned file_type)
3074 {
3075         int retval;
3076
3077         BUFFER_TRACE(ent->bh, "get write access");
3078         retval = ext4_journal_get_write_access(handle, ent->bh);
3079         if (retval)
3080                 return retval;
3081         ent->de->inode = cpu_to_le32(ino);
3082         if (EXT4_HAS_INCOMPAT_FEATURE(ent->dir->i_sb,
3083                                       EXT4_FEATURE_INCOMPAT_FILETYPE))
3084                 ent->de->file_type = file_type;
3085         ent->dir->i_version++;
3086         ent->dir->i_ctime = ent->dir->i_mtime =
3087                 ext4_current_time(ent->dir);
3088         ext4_mark_inode_dirty(handle, ent->dir);
3089         BUFFER_TRACE(ent->bh, "call ext4_handle_dirty_metadata");
3090         if (!ent->inlined) {
3091                 retval = ext4_handle_dirty_dirent_node(handle,
3092                                                        ent->dir, ent->bh);
3093                 if (unlikely(retval)) {
3094                         ext4_std_error(ent->dir->i_sb, retval);
3095                         return retval;
3096                 }
3097         }
3098         brelse(ent->bh);
3099         ent->bh = NULL;
3100
3101         return 0;
3102 }
3103
3104 static int ext4_find_delete_entry(handle_t *handle, struct inode *dir,
3105                                   const struct qstr *d_name)
3106 {
3107         int retval = -ENOENT;
3108         struct buffer_head *bh;
3109         struct ext4_dir_entry_2 *de;
3110
3111         bh = ext4_find_entry(dir, d_name, &de, NULL);
3112         if (IS_ERR(bh))
3113                 return PTR_ERR(bh);
3114         if (bh) {
3115                 retval = ext4_delete_entry(handle, dir, de, bh);
3116                 brelse(bh);
3117         }
3118         return retval;
3119 }
3120
3121 static void ext4_rename_delete(handle_t *handle, struct ext4_renament *ent,
3122                                int force_reread)
3123 {
3124         int retval;
3125         /*
3126          * ent->de could have moved from under us during htree split, so make
3127          * sure that we are deleting the right entry.  We might also be pointing
3128          * to a stale entry in the unused part of ent->bh so just checking inum
3129          * and the name isn't enough.
3130          */
3131         if (le32_to_cpu(ent->de->inode) != ent->inode->i_ino ||
3132             ent->de->name_len != ent->dentry->d_name.len ||
3133             strncmp(ent->de->name, ent->dentry->d_name.name,
3134                     ent->de->name_len) ||
3135             force_reread) {
3136                 retval = ext4_find_delete_entry(handle, ent->dir,
3137                                                 &ent->dentry->d_name);
3138         } else {
3139                 retval = ext4_delete_entry(handle, ent->dir, ent->de, ent->bh);
3140                 if (retval == -ENOENT) {
3141                         retval = ext4_find_delete_entry(handle, ent->dir,
3142                                                         &ent->dentry->d_name);
3143                 }
3144         }
3145
3146         if (retval) {
3147                 ext4_warning(ent->dir->i_sb,
3148                                 "Deleting old file (%lu), %d, error=%d",
3149                                 ent->dir->i_ino, ent->dir->i_nlink, retval);
3150         }
3151 }
3152
3153 static void ext4_update_dir_count(handle_t *handle, struct ext4_renament *ent)
3154 {
3155         if (ent->dir_nlink_delta) {
3156                 if (ent->dir_nlink_delta == -1)
3157                         ext4_dec_count(handle, ent->dir);
3158                 else
3159                         ext4_inc_count(handle, ent->dir);
3160                 ext4_mark_inode_dirty(handle, ent->dir);
3161         }
3162 }
3163
3164 /*
3165  * Anybody can rename anything with this: the permission checks are left to the
3166  * higher-level routines.
3167  *
3168  * n.b.  old_{dentry,inode) refers to the source dentry/inode
3169  * while new_{dentry,inode) refers to the destination dentry/inode
3170  * This comes from rename(const char *oldpath, const char *newpath)
3171  */
3172 static int ext4_rename(struct inode *old_dir, struct dentry *old_dentry,
3173                        struct inode *new_dir, struct dentry *new_dentry)
3174 {
3175         handle_t *handle = NULL;
3176         struct ext4_renament old = {
3177                 .dir = old_dir,
3178                 .dentry = old_dentry,
3179                 .inode = old_dentry->d_inode,
3180         };
3181         struct ext4_renament new = {
3182                 .dir = new_dir,
3183                 .dentry = new_dentry,
3184                 .inode = new_dentry->d_inode,
3185         };
3186         int force_reread;
3187         int retval;
3188
3189         dquot_initialize(old.dir);
3190         dquot_initialize(new.dir);
3191
3192         /* Initialize quotas before so that eventual writes go
3193          * in separate transaction */
3194         if (new.inode)
3195                 dquot_initialize(new.inode);
3196
3197         old.bh = ext4_find_entry(old.dir, &old.dentry->d_name, &old.de, NULL);
3198         if (IS_ERR(old.bh))
3199                 return PTR_ERR(old.bh);
3200         /*
3201          *  Check for inode number is _not_ due to possible IO errors.
3202          *  We might rmdir the source, keep it as pwd of some process
3203          *  and merrily kill the link to whatever was created under the
3204          *  same name. Goodbye sticky bit ;-<
3205          */
3206         retval = -ENOENT;
3207         if (!old.bh || le32_to_cpu(old.de->inode) != old.inode->i_ino)
3208                 goto end_rename;
3209
3210         new.bh = ext4_find_entry(new.dir, &new.dentry->d_name,
3211                                  &new.de, &new.inlined);
3212         if (IS_ERR(new.bh)) {
3213                 retval = PTR_ERR(new.bh);
3214                 goto end_rename;
3215         }
3216         if (new.bh) {
3217                 if (!new.inode) {
3218                         brelse(new.bh);
3219                         new.bh = NULL;
3220                 }
3221         }
3222         if (new.inode && !test_opt(new.dir->i_sb, NO_AUTO_DA_ALLOC))
3223                 ext4_alloc_da_blocks(old.inode);
3224
3225         handle = ext4_journal_start(old.dir, EXT4_HT_DIR,
3226                 (2 * EXT4_DATA_TRANS_BLOCKS(old.dir->i_sb) +
3227                  EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2));
3228         if (IS_ERR(handle))
3229                 return PTR_ERR(handle);
3230
3231         if (IS_DIRSYNC(old.dir) || IS_DIRSYNC(new.dir))
3232                 ext4_handle_sync(handle);
3233
3234         if (S_ISDIR(old.inode->i_mode)) {
3235                 if (new.inode) {
3236                         retval = -ENOTEMPTY;
3237                         if (!empty_dir(new.inode))
3238                                 goto end_rename;
3239                 } else {
3240                         retval = -EMLINK;
3241                         if (new.dir != old.dir && EXT4_DIR_LINK_MAX(new.dir))
3242                                 goto end_rename;
3243                 }
3244                 retval = ext4_rename_dir_prepare(handle, &old);
3245                 if (retval)
3246                         goto end_rename;
3247         }
3248         /*
3249          * If we're renaming a file within an inline_data dir and adding or
3250          * setting the new dirent causes a conversion from inline_data to
3251          * extents/blockmap, we need to force the dirent delete code to
3252          * re-read the directory, or else we end up trying to delete a dirent
3253          * from what is now the extent tree root (or a block map).
3254          */
3255         force_reread = (new.dir->i_ino == old.dir->i_ino &&
3256                         ext4_test_inode_flag(new.dir, EXT4_INODE_INLINE_DATA));
3257         if (!new.bh) {
3258                 retval = ext4_add_entry(handle, new.dentry, old.inode);
3259                 if (retval)
3260                         goto end_rename;
3261         } else {
3262                 retval = ext4_setent(handle, &new,
3263                                      old.inode->i_ino, old.de->file_type);
3264                 if (retval)
3265                         goto end_rename;
3266         }
3267         if (force_reread)
3268                 force_reread = !ext4_test_inode_flag(new.dir,
3269                                                      EXT4_INODE_INLINE_DATA);
3270
3271         /*
3272          * Like most other Unix systems, set the ctime for inodes on a
3273          * rename.
3274          */
3275         old.inode->i_ctime = ext4_current_time(old.inode);
3276         ext4_mark_inode_dirty(handle, old.inode);
3277
3278         /*
3279          * ok, that's it
3280          */
3281         ext4_rename_delete(handle, &old, force_reread);
3282
3283         if (new.inode) {
3284                 ext4_dec_count(handle, new.inode);
3285                 new.inode->i_ctime = ext4_current_time(new.inode);
3286         }
3287         old.dir->i_ctime = old.dir->i_mtime = ext4_current_time(old.dir);
3288         ext4_update_dx_flag(old.dir);
3289         if (old.dir_bh) {
3290                 retval = ext4_rename_dir_finish(handle, &old, new.dir->i_ino);
3291                 if (retval)
3292                         goto end_rename;
3293
3294                 ext4_dec_count(handle, old.dir);
3295                 if (new.inode) {
3296                         /* checked empty_dir above, can't have another parent,
3297                          * ext4_dec_count() won't work for many-linked dirs */
3298                         clear_nlink(new.inode);
3299                 } else {
3300                         ext4_inc_count(handle, new.dir);
3301                         ext4_update_dx_flag(new.dir);
3302                         ext4_mark_inode_dirty(handle, new.dir);
3303                 }
3304         }
3305         ext4_mark_inode_dirty(handle, old.dir);
3306         if (new.inode) {
3307                 ext4_mark_inode_dirty(handle, new.inode);
3308                 if (!new.inode->i_nlink)
3309                         ext4_orphan_add(handle, new.inode);
3310         }
3311         retval = 0;
3312
3313 end_rename:
3314         brelse(old.dir_bh);
3315         brelse(old.bh);
3316         brelse(new.bh);
3317         if (handle)
3318                 ext4_journal_stop(handle);
3319         return retval;
3320 }
3321
3322 static int ext4_cross_rename(struct inode *old_dir, struct dentry *old_dentry,
3323                              struct inode *new_dir, struct dentry *new_dentry)
3324 {
3325         handle_t *handle = NULL;
3326         struct ext4_renament old = {
3327                 .dir = old_dir,
3328                 .dentry = old_dentry,
3329                 .inode = old_dentry->d_inode,
3330         };
3331         struct ext4_renament new = {
3332                 .dir = new_dir,
3333                 .dentry = new_dentry,
3334                 .inode = new_dentry->d_inode,
3335         };
3336         u8 new_file_type;
3337         int retval;
3338
3339         dquot_initialize(old.dir);
3340         dquot_initialize(new.dir);
3341
3342         old.bh = ext4_find_entry(old.dir, &old.dentry->d_name,
3343                                  &old.de, &old.inlined);
3344         if (IS_ERR(old.bh))
3345                 return PTR_ERR(old.bh);
3346         /*
3347          *  Check for inode number is _not_ due to possible IO errors.
3348          *  We might rmdir the source, keep it as pwd of some process
3349          *  and merrily kill the link to whatever was created under the
3350          *  same name. Goodbye sticky bit ;-<
3351          */
3352         retval = -ENOENT;
3353         if (!old.bh || le32_to_cpu(old.de->inode) != old.inode->i_ino)
3354                 goto end_rename;
3355
3356         new.bh = ext4_find_entry(new.dir, &new.dentry->d_name,
3357                                  &new.de, &new.inlined);
3358         if (IS_ERR(new.bh)) {
3359                 retval = PTR_ERR(new.bh);
3360                 goto end_rename;
3361         }
3362
3363         /* RENAME_EXCHANGE case: old *and* new must both exist */
3364         if (!new.bh || le32_to_cpu(new.de->inode) != new.inode->i_ino)
3365                 goto end_rename;
3366
3367         handle = ext4_journal_start(old.dir, EXT4_HT_DIR,
3368                 (2 * EXT4_DATA_TRANS_BLOCKS(old.dir->i_sb) +
3369                  2 * EXT4_INDEX_EXTRA_TRANS_BLOCKS + 2));
3370         if (IS_ERR(handle))
3371                 return PTR_ERR(handle);
3372
3373         if (IS_DIRSYNC(old.dir) || IS_DIRSYNC(new.dir))
3374                 ext4_handle_sync(handle);
3375
3376         if (S_ISDIR(old.inode->i_mode)) {
3377                 old.is_dir = true;
3378                 retval = ext4_rename_dir_prepare(handle, &old);
3379                 if (retval)
3380                         goto end_rename;
3381         }
3382         if (S_ISDIR(new.inode->i_mode)) {
3383                 new.is_dir = true;
3384                 retval = ext4_rename_dir_prepare(handle, &new);
3385                 if (retval)
3386                         goto end_rename;
3387         }
3388
3389         /*
3390          * Other than the special case of overwriting a directory, parents'
3391          * nlink only needs to be modified if this is a cross directory rename.
3392          */
3393         if (old.dir != new.dir && old.is_dir != new.is_dir) {
3394                 old.dir_nlink_delta = old.is_dir ? -1 : 1;
3395                 new.dir_nlink_delta = -old.dir_nlink_delta;
3396                 retval = -EMLINK;
3397                 if ((old.dir_nlink_delta > 0 && EXT4_DIR_LINK_MAX(old.dir)) ||
3398                     (new.dir_nlink_delta > 0 && EXT4_DIR_LINK_MAX(new.dir)))
3399                         goto end_rename;
3400         }
3401
3402         new_file_type = new.de->file_type;
3403         retval = ext4_setent(handle, &new, old.inode->i_ino, old.de->file_type);
3404         if (retval)
3405                 goto end_rename;
3406
3407         retval = ext4_setent(handle, &old, new.inode->i_ino, new_file_type);
3408         if (retval)
3409                 goto end_rename;
3410
3411         /*
3412          * Like most other Unix systems, set the ctime for inodes on a
3413          * rename.
3414          */
3415         old.inode->i_ctime = ext4_current_time(old.inode);
3416         new.inode->i_ctime = ext4_current_time(new.inode);
3417         ext4_mark_inode_dirty(handle, old.inode);
3418         ext4_mark_inode_dirty(handle, new.inode);
3419
3420         if (old.dir_bh) {
3421                 retval = ext4_rename_dir_finish(handle, &old, new.dir->i_ino);
3422                 if (retval)
3423                         goto end_rename;
3424         }
3425         if (new.dir_bh) {
3426                 retval = ext4_rename_dir_finish(handle, &new, old.dir->i_ino);
3427                 if (retval)
3428                         goto end_rename;
3429         }
3430         ext4_update_dir_count(handle, &old);
3431         ext4_update_dir_count(handle, &new);
3432         retval = 0;
3433
3434 end_rename:
3435         brelse(old.dir_bh);
3436         brelse(new.dir_bh);
3437         brelse(old.bh);
3438         brelse(new.bh);
3439         if (handle)
3440                 ext4_journal_stop(handle);
3441         return retval;
3442 }
3443
3444 static int ext4_rename2(struct inode *old_dir, struct dentry *old_dentry,
3445                         struct inode *new_dir, struct dentry *new_dentry,
3446                         unsigned int flags)
3447 {
3448         if (flags & ~(RENAME_NOREPLACE | RENAME_EXCHANGE))
3449                 return -EINVAL;
3450
3451         if (flags & RENAME_EXCHANGE) {
3452                 return ext4_cross_rename(old_dir, old_dentry,
3453                                          new_dir, new_dentry);
3454         }
3455         /*
3456          * Existence checking was done by the VFS, otherwise "RENAME_NOREPLACE"
3457          * is equivalent to regular rename.
3458          */
3459         return ext4_rename(old_dir, old_dentry, new_dir, new_dentry);
3460 }
3461
3462 /*
3463  * directories can handle most operations...
3464  */
3465 const struct inode_operations ext4_dir_inode_operations = {
3466         .create         = ext4_create,
3467         .lookup         = ext4_lookup,
3468         .link           = ext4_link,
3469         .unlink         = ext4_unlink,
3470         .symlink        = ext4_symlink,
3471         .mkdir          = ext4_mkdir,
3472         .rmdir          = ext4_rmdir,
3473         .mknod          = ext4_mknod,
3474         .tmpfile        = ext4_tmpfile,
3475         .rename2        = ext4_rename2,
3476         .setattr        = ext4_setattr,
3477         .setxattr       = generic_setxattr,
3478         .getxattr       = generic_getxattr,
3479         .listxattr      = ext4_listxattr,
3480         .removexattr    = generic_removexattr,
3481         .get_acl        = ext4_get_acl,
3482         .set_acl        = ext4_set_acl,
3483         .fiemap         = ext4_fiemap,
3484 };
3485
3486 const struct inode_operations ext4_special_inode_operations = {
3487         .setattr        = ext4_setattr,
3488         .setxattr       = generic_setxattr,
3489         .getxattr       = generic_getxattr,
3490         .listxattr      = ext4_listxattr,
3491         .removexattr    = generic_removexattr,
3492         .get_acl        = ext4_get_acl,
3493         .set_acl        = ext4_set_acl,
3494 };