lustre/kernel_patches/patches/htree-ext3-2.4.18.patch

   1 --- ./fs/ext3/super.c   2002/03/05 06:18:59     2.1
   2 +++ ./fs/ext3/super.c   2002/03/05 06:26:56
   3 @@ -529,6 +529,12 @@
   4                                        "EXT3 Check option not supported\n");
   5  #endif
   6                 }
   7 +               else if (!strcmp (this_char, "index"))
   8 +#ifdef CONFIG_EXT3_INDEX
   9 +                       set_opt (*mount_options, INDEX);
  10 +#else
  11 +                       printk("EXT3 index option not supported\n");
  12 +#endif
  13                 else if (!strcmp (this_char, "debug"))
  14                         set_opt (*mount_options, DEBUG);
  15                 else if (!strcmp (this_char, "errors")) {
  16 @@ -702,6 +708,12 @@
  17         es->s_mtime = cpu_to_le32(CURRENT_TIME);
  18         ext3_update_dynamic_rev(sb);
  19         EXT3_SET_INCOMPAT_FEATURE(sb, EXT3_FEATURE_INCOMPAT_RECOVER);
  20 +
  21 +       if (test_opt(sb, INDEX))
  22 +               EXT3_SET_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX);
  23 +       else if (EXT3_HAS_COMPAT_FEATURE(sb, EXT3_FEATURE_COMPAT_DIR_INDEX))
  24 +               set_opt (EXT3_SB(sb)->s_mount_opt, INDEX);
  25 +
  26         ext3_commit_super (sb, es, 1);
  27         if (test_opt (sb, DEBUG))
  28                 printk (KERN_INFO
  29 --- ./fs/ext3/namei.c   2002/03/05 06:18:59     2.1
  30 +++ ./fs/ext3/namei.c   2002/03/06 00:13:18
  31 @@ -16,6 +16,10 @@
  32   *        David S. Miller (davem@caip.rutgers.edu), 1995
  33   *  Directory entry file type support and forward compatibility hooks
  34   *     for B-tree directories by Theodore Ts'o (tytso@mit.edu), 1998
  35 + *  Hash Tree Directory indexing (c)
  36 + *     Daniel Phillips, 2001
  37 + *  Hash Tree Directory indexing porting
  38 + *     Christopher Li, 2002
  39   */
  40
  41  #include <linux/fs.h>
  42 @@ -33,7 +33,7 @@
  43  #include <linux/string.h>
  44  #include <linux/locks.h>
  45  #include <linux/quotaops.h>
  46 -
  47 +#include <linux/slab.h>
  48
  49  /*
  50   * define how far ahead to read directories while searching them.
  51 @@ -38,6 +42,437 @@
  52  #define NAMEI_RA_SIZE        (NAMEI_RA_CHUNKS * NAMEI_RA_BLOCKS)
  53  #define NAMEI_RA_INDEX(c,b)  (((c) * NAMEI_RA_BLOCKS) + (b))
  54
  55 +static struct buffer_head *ext3_append(handle_t *handle,
  56 +                                       struct inode *inode,
  57 +                                       u32 *block, int *err)
  58 +{
  59 +       struct buffer_head *bh;
  60 +
  61 +       *block = inode->i_size >> inode->i_sb->s_blocksize_bits;
  62 +
  63 +       if ((bh = ext3_bread(handle, inode, *block, 1, err))) {
  64 +               inode->i_size += inode->i_sb->s_blocksize;
  65 +               EXT3_I(inode)->i_disksize = inode->i_size;
  66 +               ext3_journal_get_write_access(handle,bh);
  67 +       }
  68 +       return bh;
  69 +}
  70 +
  71 +#ifndef assert
  72 +#define assert(test) J_ASSERT(test)
  73 +#endif
  74 +
  75 +#ifndef swap
  76 +#define swap(x, y) do { typeof(x) z = x; x = y; y = z; } while (0)
  77 +#endif
  78 +
  79 +typedef struct { u32 v; } le_u32;
  80 +typedef struct { u16 v; } le_u16;
  81 +
  82 +#define dxtrace_on(command) command
  83 +#define dxtrace_off(command)
  84 +
  85 +struct fake_dirent
  86 +{
  87 +       /*le*/u32 inode;
  88 +       /*le*/u16 rec_len;
  89 +       u8 name_len;
  90 +       u8 file_type;
  91 +};
  92 +
  93 +struct dx_countlimit
  94 +{
  95 +       le_u16 limit;
  96 +       le_u16 count;
  97 +};
  98 +
  99 +struct dx_entry
 100 +{
 101 +       le_u32 hash;
 102 +       le_u32 block;
 103 +};
 104 +
 105 +/*
 106 + * dx_root_info is laid out so that if it should somehow get overlaid by a
 107 + * dirent the two low bits of the hash version will be zero.  Therefore, the
 108 + * hash version mod 4 should never be 0.  Sincerely, the paranoia department.
 109 + */
 110 +
 111 +struct dx_root
 112 +{
 113 +       struct fake_dirent dot;
 114 +       char dot_name[4];
 115 +       struct fake_dirent dotdot;
 116 +       char dotdot_name[4];
 117 +       struct dx_root_info
 118 +       {
 119 +               le_u32 reserved_zero;
 120 +               u8 hash_version; /* 0 now, 1 at release */
 121 +               u8 info_length; /* 8 */
 122 +               u8 indirect_levels;
 123 +               u8 unused_flags;
 124 +       }
 125 +       info;
 126 +       struct dx_entry entries[0];
 127 +};
 128 +
 129 +struct dx_node
 130 +{
 131 +       struct fake_dirent fake;
 132 +       struct dx_entry entries[0];
 133 +};
 134 +
 135 +
 136 +struct dx_frame
 137 +{
 138 +       struct buffer_head *bh;
 139 +       struct dx_entry *entries;
 140 +       struct dx_entry *at;
 141 +};
 142 +
 143 +struct dx_map_entry
 144 +{
 145 +       u32 hash;
 146 +       u32 offs;
 147 +};
 148 +
 149 +typedef struct ext3_dir_entry_2 ext3_dirent;
 150 +static inline unsigned dx_get_block (struct dx_entry *entry);
 151 +static void dx_set_block (struct dx_entry *entry, unsigned value);
 152 +static inline unsigned dx_get_hash (struct dx_entry *entry);
 153 +static void dx_set_hash (struct dx_entry *entry, unsigned value);
 154 +static unsigned dx_get_count (struct dx_entry *entries);
 155 +static unsigned dx_get_limit (struct dx_entry *entries);
 156 +static void dx_set_count (struct dx_entry *entries, unsigned value);
 157 +static void dx_set_limit (struct dx_entry *entries, unsigned value);
 158 +static unsigned dx_root_limit (struct inode *dir, unsigned infosize);
 159 +static unsigned dx_node_limit (struct inode *dir);
 160 +static unsigned dx_hack_hash (const u8 *name, int len);
 161 +static struct dx_frame *dx_probe (struct inode *dir, u32 hash, struct dx_frame *frame);
 162 +static void dx_release (struct dx_frame *frames);
 163 +static int dx_make_map (ext3_dirent *de, int size, struct dx_map_entry map[]);
 164 +static void dx_sort_map(struct dx_map_entry *map, unsigned count);
 165 +static ext3_dirent *dx_copy_dirents (char *from, char *to,
 166 +     struct dx_map_entry *map, int count);
 167 +static void dx_insert_block (struct dx_frame *frame, u32 hash, u32 block);
 168 +
 169 +
 170 +#ifdef CONFIG_EXT3_INDEX
 171 +/*
 172 + * Future: use high four bits of block for coalesce-on-delete flags
 173 + * Mask them off for now.
 174 + */
 175 +
 176 +static inline unsigned dx_get_block (struct dx_entry *entry)
 177 +{
 178 +       return le32_to_cpu(entry->block.v) & 0x00ffffff;
 179 +}
 180 +
 181 +static inline void dx_set_block (struct dx_entry *entry, unsigned value)
 182 +{
 183 +       entry->block.v = cpu_to_le32(value);
 184 +}
 185 +
 186 +static inline unsigned dx_get_hash (struct dx_entry *entry)
 187 +{
 188 +       return le32_to_cpu(entry->hash.v);
 189 +}
 190 +
 191 +static inline void dx_set_hash (struct dx_entry *entry, unsigned value)
 192 +{
 193 +       entry->hash.v = cpu_to_le32(value);
 194 +}
 195 +
 196 +static inline unsigned dx_get_count (struct dx_entry *entries)
 197 +{
 198 +       return le16_to_cpu(((struct dx_countlimit *) entries)->count.v);
 199 +}
 200 +
 201 +static inline unsigned dx_get_limit (struct dx_entry *entries)
 202 +{
 203 +       return le16_to_cpu(((struct dx_countlimit *) entries)->limit.v);
 204 +}
 205 +
 206 +static inline void dx_set_count (struct dx_entry *entries, unsigned value)
 207 +{
 208 +       ((struct dx_countlimit *) entries)->count.v = cpu_to_le16(value);
 209 +}
 210 +
 211 +static inline void dx_set_limit (struct dx_entry *entries, unsigned value)
 212 +{
 213 +       ((struct dx_countlimit *) entries)->limit.v = cpu_to_le16(value);
 214 +}
 215 +
 216 +static inline unsigned dx_root_limit (struct inode *dir, unsigned infosize)
 217 +{
 218 +       unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(1) -
 219 +               EXT3_DIR_REC_LEN(2) - infosize;
 220 +       return 0? 20: entry_space / sizeof(struct dx_entry);
 221 +}
 222 +
 223 +static inline unsigned dx_node_limit (struct inode *dir)
 224 +{
 225 +       unsigned entry_space = dir->i_sb->s_blocksize - EXT3_DIR_REC_LEN(0);
 226 +       return 0? 22: entry_space / sizeof(struct dx_entry);
 227 +}
 228 +
 229 +/* Hash function - not bad, but still looking for an ideal default */
 230 +
 231 +static unsigned dx_hack_hash (const u8 *name, int len)
 232 +{
 233 +       u32 hash0 = 0x12a3fe2d, hash1 = 0x37abe8f9;
 234 +       while (len--)
 235 +       {
 236 +               u32 hash = hash1 + (hash0 ^ (*name++ * 7152373));
 237 +               if (hash & 0x80000000) hash -= 0x7fffffff;
 238 +               hash1 = hash0;
 239 +               hash0 = hash;
 240 +       }
 241 +       return hash0;
 242 +}
 243 +
 244 +#define dx_hash(s,n) (dx_hack_hash(s,n) << 1)
 245 +
 246 +/*
 247 + * Debug
 248 + */
 249 +#ifdef DX_DEBUG
 250 +#define dxtrace dxtrace_on
 251 +static void dx_show_index (char * label, struct dx_entry *entries)
 252 +{
 253 +       int i, n = dx_get_count (entries);
 254 +       printk("%s index ", label);
 255 +       for (i = 0; i < n; i++)
 256 +       {
 257 +               printk("%x->%u ", i? dx_get_hash(entries + i): 0, dx_get_block(entries + i));
 258 +       }
 259 +       printk("\n");
 260 +}
 261 +
 262 +struct stats
 263 +{
 264 +       unsigned names;
 265 +       unsigned space;
 266 +       unsigned bcount;
 267 +};
 268 +
 269 +static struct stats dx_show_leaf (ext3_dirent *de, int size, int show_names)
 270 +{
 271 +       unsigned names = 0, space = 0;
 272 +       char *base = (char *) de;
 273 +       printk("names: ");
 274 +       while ((char *) de < base + size)
 275 +       {
 276 +               if (de->inode)
 277 +               {
 278 +                       if (show_names)
 279 +                       {
 280 +                               int len = de->name_len;
 281 +                               char *name = de->name;
 282 +                               while (len--) printk("%c", *name++);
 283 +                               printk(":%x.%u ", dx_hash (de->name, de->name_len), ((char *) de - base));
 284 +                       }
 285 +                       space += EXT3_DIR_REC_LEN(de->name_len);
 286 +                       names++;
 287 +               }
 288 +               de = (ext3_dirent *) ((char *) de + le16_to_cpu(de->rec_len));
 289 +       }
 290 +       printk("(%i)\n", names);
 291 +       return (struct stats) { names, space, 1 };
 292 +}
 293 +
 294 +struct stats dx_show_entries (struct inode *dir, struct dx_entry *entries, int levels)
 295 +{
 296 +       unsigned blocksize = dir->i_sb->s_blocksize;
 297 +       unsigned count = dx_get_count (entries), names = 0, space = 0, i;
 298 +       unsigned bcount = 0;
 299 +       struct buffer_head *bh;
 300 +       int err;
 301 +       printk("%i indexed blocks...\n", count);
 302 +       for (i = 0; i < count; i++, entries++)
 303 +       {
 304 +               u32 block = dx_get_block(entries), hash = i? dx_get_hash(entries): 0;
 305 +               u32 range = i < count - 1? (dx_get_hash(entries + 1) - hash): ~hash;
 306 +               struct stats stats;
 307 +               printk("%s%3u:%03u hash %8x/%8x ",levels?"":"   ", i, block, hash, range);
 308 +               if (!(bh = ext3_bread (NULL,dir, block, 0,&err))) continue;
 309 +               stats = levels?
 310 +                  dx_show_entries (dir, ((struct dx_node *) bh->b_data)->entries, levels - 1):
 311 +                  dx_show_leaf ((ext3_dirent *) bh->b_data, blocksize, 0);
 312 +               names += stats.names;
 313 +               space += stats.space;
 314 +               bcount += stats.bcount;
 315 +               brelse (bh);
 316 +       }
 317 +       if (bcount)
 318 +               printk("%snames %u, fullness %u (%u%%)\n", levels?"":"   ",
 319 +                       names, space/bcount,(space/bcount)*100/blocksize);
 320 +       return (struct stats) { names, space, bcount};
 321 +}
 322 +#else
 323 +#define dxtrace dxtrace_off
 324 +#endif
 325 +
 326 +/*
 327 + * Probe for a directory leaf block to search
 328 + */
 329 +
 330 +static struct dx_frame *
 331 +dx_probe(struct inode *dir, u32 hash, struct dx_frame *frame_in)
 332 +{
 333 +       unsigned count, indirect;
 334 +       struct dx_entry *at, *entries, *p, *q, *m;
 335 +       struct dx_root *root;
 336 +       struct buffer_head *bh;
 337 +       struct dx_frame *frame = frame_in;
 338 +       int err;
 339 +
 340 +       frame->bh = NULL;
 341 +       if (!(bh = ext3_bread(NULL, dir, 0, 0, &err)))
 342 +               goto fail;
 343 +       root = (struct dx_root *) bh->b_data;
 344 +       if (root->info.hash_version > 0 || root->info.unused_flags & 1) {
 345 +               brelse(bh);
 346 +               goto fail;
 347 +       }
 348 +       if ((indirect = root->info.indirect_levels) > 1) {
 349 +               brelse(bh);
 350 +               goto fail;
 351 +       }
 352 +       entries = (struct dx_entry *) (((char *) &root->info) + root->info.info_length);
 353 +       assert (dx_get_limit(entries) == dx_root_limit(dir, root->info.info_length));
 354 +       dxtrace (printk("Look up %x", hash));
 355 +       while (1)
 356 +       {
 357 +               count = dx_get_count(entries);
 358 +               assert (count && count <= dx_get_limit(entries));
 359 +               p = entries + 1;
 360 +               q = entries + count - 1;
 361 +               while (p <= q)
 362 +               {
 363 +                       m = p + (q - p)/2;
 364 +                       dxtrace(printk("."));
 365 +                       if (dx_get_hash(m) > hash)
 366 +                               q = m - 1;
 367 +                       else
 368 +                               p = m + 1;
 369 +               }
 370 +
 371 +               if (0) // linear search cross check
 372 +               {
 373 +                       unsigned n = count - 1;
 374 +                       at = entries;
 375 +                       while (n--)
 376 +                       {
 377 +                               dxtrace(printk(","));
 378 +                               if (dx_get_hash(++at) > hash)
 379 +                               {
 380 +                                       at--;
 381 +                                       break;
 382 +                               }
 383 +                       }
 384 +                       assert (at == p - 1);
 385 +               }
 386 +
 387 +               at = p - 1;
 388 +               dxtrace(printk(" %x->%u\n", at == entries? 0: dx_get_hash(at), dx_get_block(at)));
 389 +               frame->bh = bh;
 390 +               frame->entries = entries;
 391 +               frame->at = at;
 392 +               if (!indirect--) return frame;
 393 +               if (!(bh = ext3_bread (NULL,dir, dx_get_block(at), 0,&err)))
 394 +                       goto fail2;
 395 +               at = entries = ((struct dx_node *) bh->b_data)->entries;
 396 +               assert (dx_get_limit(entries) == dx_node_limit (dir));
 397 +               frame++;
 398 +       }
 399 +fail2:
 400 +       while (frame >= frame_in) {
 401 +               brelse(frame->bh);
 402 +               frame--;
 403 +       }
 404 +fail:
 405 +       return NULL;
 406 +}
 407 +
 408 +static void dx_release (struct dx_frame *frames)
 409 +{
 410 +       if (frames[0].bh == NULL)
 411 +               return;
 412 +
 413 +       if (((struct dx_root *)frames[0].bh->b_data)->info.indirect_levels)
 414 +               brelse (frames[1].bh);
 415 +       brelse (frames[0].bh);
 416 +}
 417 +
 418 +/*
 419 + * Directory block splitting, compacting
 420 + */
 421 +
 422 +static int dx_make_map (ext3_dirent *de, int size, struct dx_map_entry map[])
 423 +{
 424 +       int count = 0;
 425 +       char *base = (char *) de;
 426 +       while ((char *) de < base + size) {
 427 +               if (de->name_len && de->inode) {
 428 +                       map[count].hash = dx_hash (de->name, de->name_len);
 429 +                       map[count].offs = (u32) ((char *) de - base);
 430 +                       count++;
 431 +               }
 432 +               de = (ext3_dirent *) ((char *) de + le16_to_cpu(de->rec_len));
 433 +       }
 434 +       return count;
 435 +}
 436 +
 437 +static void dx_sort_map (struct dx_map_entry *map, unsigned count)
 438 +{
 439 +        struct dx_map_entry *p, *q, *top = map + count - 1;
 440 +        int more;
 441 +        /* Combsort until bubble sort doesn't suck */
 442 +        while (count > 2)
 443 +       {
 444 +                count = count*10/13;
 445 +                if (count - 9 < 2) /* 9, 10 -> 11 */
 446 +                        count = 11;
 447 +                for (p = top, q = p - count; q >= map; p--, q--)
 448 +                        if (p->hash < q->hash)
 449 +                                swap(*p, *q);
 450 +        }
 451 +        /* Garden variety bubble sort */
 452 +        do {
 453 +                more = 0;
 454 +                q = top;
 455 +                while (q-- > map)
 456 +               {
 457 +                        if (q[1].hash >= q[0].hash)
 458 +                               continue;
 459 +                        swap(*(q+1), *q);
 460 +                        more = 1;
 461 +               }
 462 +       } while(more);
 463 +}
 464 +
 465 +static void dx_insert_block(struct dx_frame *frame, u32 hash, u32 block)
 466 +{
 467 +       struct dx_entry *entries = frame->entries;
 468 +       struct dx_entry *old = frame->at, *new = old + 1;
 469 +       int count = dx_get_count(entries);
 470 +
 471 +       assert(count < dx_get_limit(entries));
 472 +       assert(old < entries + count);
 473 +       memmove(new + 1, new, (char *)(entries + count) - (char *)(new));
 474 +       dx_set_hash(new, hash);
 475 +       dx_set_block(new, block);
 476 +       dx_set_count(entries, count + 1);
 477 +}
 478 +#endif
 479 +
 480 +static void ext3_update_dx_flag(struct inode *inode)
 481 +{
 482 +       if (!test_opt(inode->i_sb, INDEX))
 483 +               EXT3_I(inode)->i_flags &= ~EXT3_INDEX_FL;
 484 +}
 485 +
 486  /*
 487   * NOTE! unlike strncmp, ext3_match returns 1 for success, 0 for failure.
 488   *
 489 @@ -95,6 +529,15 @@
 490  }
 491
 492  /*
 493 + * p is at least 6 bytes before the end of page
 494 + */
 495 +static inline ext3_dirent *ext3_next_entry(ext3_dirent *p)
 496 +{
 497 +       return (ext3_dirent *)((char*)p + le16_to_cpu(p->rec_len));
 498 +}
 499 +
 500 +
 501 +/*
 502   *     ext3_find_entry()
 503   *
 504   * finds an entry in the specified directory with the wanted name. It
 505 @@ -105,6 +548,8 @@
 506   * The returned buffer_head has ->b_count elevated.  The caller is expected
 507   * to brelse() it when appropriate.
 508   */
 509 +
 510 +
 511  static struct buffer_head * ext3_find_entry (struct dentry *dentry,
 512                                         struct ext3_dir_entry_2 ** res_dir)
 513  {
 514 @@ -119,10 +564,70 @@
 515         int num = 0;
 516         int nblocks, i, err;
 517         struct inode *dir = dentry->d_parent->d_inode;
 518 +       ext3_dirent *de, *top;
 519
 520         *res_dir = NULL;
 521         sb = dir->i_sb;
 522 +       if (dentry->d_name.len > EXT3_NAME_LEN)
 523 +               return NULL;
 524 +       if (ext3_dx && is_dx(dir)) {
 525 +               u32 hash = dx_hash(dentry->d_name.name, dentry->d_name.len);
 526 +               struct dx_frame frames[2], *frame;
 527 +               if (!(frame = dx_probe (dir, hash, frames)))
 528 +                       return NULL;
 529 +dxnext:
 530 +               block = dx_get_block(frame->at);
 531 +               if (!(bh = ext3_bread (NULL,dir, block, 0, &err)))
 532 +                       goto dxfail;
 533 +               de = (ext3_dirent *) bh->b_data;
 534 +               top = (ext3_dirent *) ((char *) de + sb->s_blocksize -
 535 +                               EXT3_DIR_REC_LEN(0));
 536 +               for (; de < top; de = ext3_next_entry(de))
 537 +                       if (ext3_match(dentry->d_name.len, dentry->d_name.name, de)) {
 538 +                               if (!ext3_check_dir_entry("ext3_find_entry",
 539 +                                         dir, de, bh,
 540 +                                         (block<<EXT3_BLOCK_SIZE_BITS(sb))
 541 +                                          +((char *)de - bh->b_data))) {
 542 +                                       brelse (bh);
 543 +                                       goto dxfail;
 544 +                               }
 545 +                               *res_dir = de;
 546 +                               goto dxfound;
 547 +                       }
 548 +               brelse (bh);
 549 +               /* Same hash continues in next block?  Search on. */
 550 +               if (++(frame->at) == frame->entries + dx_get_count(frame->entries))
 551 +               {
 552 +                       struct buffer_head *bh2;
 553 +                       if (frame == frames)
 554 +                               goto dxfail;
 555 +                       if (++(frames->at) == frames->entries + dx_get_count(frames->entries))
 556 +                               goto dxfail;
 557 +                       /* should omit read if not continued */
 558 +                       if (!(bh2 = ext3_bread (NULL, dir,
 559 +                                               dx_get_block(frames->at),
 560 +                                               0, &err)))
 561 +                               goto dxfail;
 562 +                       brelse (frame->bh);
 563 +                       frame->bh = bh2;
 564 +                       frame->at = frame->entries = ((struct dx_node *) bh2->b_data)->entries;
 565 +                       /* Subtle: the 0th entry has the count, find the hash in frame above */
 566 +                       if ((dx_get_hash(frames->at) & -2) == hash)
 567 +                               goto dxnext;
 568 +                       goto dxfail;
 569 +               }
 570 +               if ((dx_get_hash(frame->at) & -2) == hash)
 571 +                       goto dxnext;
 572 +dxfail:
 573 +               dxtrace(printk("%s not found\n", name));
 574 +               dx_release (frames);
 575 +               return NULL;
 576 +dxfound:
 577 +               dx_release (frames);
 578 +               return bh;
 579
 580 +       }
 581 +
 582         nblocks = dir->i_size >> EXT3_BLOCK_SIZE_BITS(sb);
 583         start = dir->u.ext3_i.i_dir_start_lookup;
 584         if (start >= nblocks)
 585 @@ -237,6 +748,90 @@
 586                 de->file_type = ext3_type_by_mode[(mode & S_IFMT)>>S_SHIFT];
 587  }
 588
 589 +static ext3_dirent *
 590 +dx_copy_dirents (char *from, char *to, struct dx_map_entry *map, int count)
 591 +{
 592 +       unsigned rec_len = 0;
 593 +
 594 +       while (count--) {
 595 +               ext3_dirent *de = (ext3_dirent *) (from + map->offs);
 596 +               rec_len = EXT3_DIR_REC_LEN(de->name_len);
 597 +               memcpy (to, de, rec_len);
 598 +               ((ext3_dirent *) to)->rec_len = rec_len;
 599 +               to += rec_len;
 600 +               map++;
 601 +       }
 602 +       return (ext3_dirent *) (to - rec_len);
 603 +}
 604 +
 605 +#ifdef CONFIG_EXT3_INDEX
 606 +static ext3_dirent *do_split(handle_t *handle, struct inode *dir,
 607 +                       struct buffer_head **bh,struct dx_frame *frame,
 608 +                       u32 hash, int *error)
 609 +{
 610 +       unsigned count;
 611 +       struct buffer_head *bh2;
 612 +       u32 newblock;
 613 +       u32 hash2;
 614 +       struct dx_map_entry *map;
 615 +       char *data1 = (*bh)->b_data, *data2, *data3;
 616 +       unsigned split;
 617 +       ext3_dirent *de, *de2;
 618 +
 619 +       bh2 = ext3_append (handle, dir, &newblock, error);
 620 +       if (!(bh2))
 621 +       {
 622 +               brelse(*bh);
 623 +               *bh = NULL;
 624 +               return (ext3_dirent *)bh2;
 625 +       }
 626 +
 627 +       BUFFER_TRACE(*bh, "get_write_access");
 628 +       ext3_journal_get_write_access(handle, *bh);
 629 +       BUFFER_TRACE(frame->bh, "get_write_access");
 630 +       ext3_journal_get_write_access(handle, frame->bh);
 631 +
 632 +       data2 = bh2->b_data;
 633 +
 634 +       map = kmalloc(sizeof(*map) * PAGE_CACHE_SIZE/EXT3_DIR_REC_LEN(1) + 1,
 635 +                     GFP_KERNEL);
 636 +       if (!map)
 637 +               panic("no memory for do_split\n");
 638 +       count = dx_make_map((ext3_dirent *)data1, dir->i_sb->s_blocksize, map);
 639 +       split = count/2; // need to adjust to actual middle
 640 +       dx_sort_map (map, count);
 641 +       hash2 = map[split].hash;
 642 +       dxtrace(printk("Split block %i at %x, %i/%i\n",
 643 +               dx_get_block(frame->at), hash2, split, count-split));
 644 +
 645 +       /* Fancy dance to stay within two buffers */
 646 +       de2 = dx_copy_dirents (data1, data2, map + split, count - split);
 647 +       data3 = (char *) de2 + de2->rec_len;
 648 +       de = dx_copy_dirents (data1, data3, map, split);
 649 +       memcpy(data1, data3, (char *) de + de->rec_len - data3);
 650 +       de = (ext3_dirent *) ((char *) de - data3 + data1); // relocate de
 651 +       de->rec_len = cpu_to_le16(data1 + dir->i_sb->s_blocksize - (char *)de);
 652 +       de2->rec_len = cpu_to_le16(data2 + dir->i_sb->s_blocksize-(char *)de2);
 653 +       dxtrace(dx_show_leaf((ext3_dirent *)data1, dir->i_sb->s_blocksize, 1));
 654 +       dxtrace(dx_show_leaf((ext3_dirent *)data2, dir->i_sb->s_blocksize, 1));
 655 +
 656 +       /* Which block gets the new entry? */
 657 +       if (hash >= hash2)
 658 +       {
 659 +               swap(*bh, bh2);
 660 +               de = de2;
 661 +       }
 662 +       dx_insert_block(frame, hash2 + (hash2 == map[split-1].hash), newblock);
 663 +       ext3_journal_dirty_metadata (handle, bh2);
 664 +       brelse (bh2);
 665 +       ext3_journal_dirty_metadata (handle, frame->bh);
 666 +       dxtrace(dx_show_index ("frame", frame->entries));
 667 +       kfree(map);
 668 +       return de;
 669 +}
 670 +#endif
 671 +
 672 +
 673  /*
 674   *     ext3_add_entry()
 675   *
 676 @@ -255,118 +849,279 @@
 677         struct inode *inode)
 678  {
 679         struct inode *dir = dentry->d_parent->d_inode;
 680 -       const char *name = dentry->d_name.name;
 681 -       int namelen = dentry->d_name.len;
 682         unsigned long offset;
 683 -       unsigned short rec_len;
 684         struct buffer_head * bh;
 685 -       struct ext3_dir_entry_2 * de, * de1;
 686 -       struct super_block * sb;
 687 +       ext3_dirent *de;
 688 +       struct super_block * sb = dir->i_sb;
 689         int     retval;
 690 +       unsigned short reclen = EXT3_DIR_REC_LEN(dentry->d_name.len);
 691
 692 -       sb = dir->i_sb;
 693 +       unsigned nlen, rlen;
 694 +       u32 block, blocks;
 695 +       char *top;
 696
 697 -       if (!namelen)
 698 +       if (!dentry->d_name.len)
 699                 return -EINVAL;
 700 -       bh = ext3_bread (handle, dir, 0, 0, &retval);
 701 -       if (!bh)
 702 -               return retval;
 703 -       rec_len = EXT3_DIR_REC_LEN(namelen);
 704 -       offset = 0;
 705 -       de = (struct ext3_dir_entry_2 *) bh->b_data;
 706 -       while (1) {
 707 -               if ((char *)de >= sb->s_blocksize + bh->b_data) {
 708 -                       brelse (bh);
 709 -                       bh = NULL;
 710 -                       bh = ext3_bread (handle, dir,
 711 -                               offset >> EXT3_BLOCK_SIZE_BITS(sb), 1, &retval);
 712 -                       if (!bh)
 713 -                               return retval;
 714 -                       if (dir->i_size <= offset) {
 715 -                               if (dir->i_size == 0) {
 716 -                                       brelse(bh);
 717 -                                       return -ENOENT;
 718 +       if (ext3_dx && is_dx(dir)) {
 719 +               struct dx_frame frames[2], *frame;
 720 +               struct dx_entry *entries, *at;
 721 +               u32 hash;
 722 +               char *data1;
 723 +
 724 +               hash = dx_hash(dentry->d_name.name, dentry->d_name.len);
 725 +               /* FIXME: do something if dx_probe() fails here */
 726 +               frame = dx_probe(dir, hash, frames);
 727 +               entries = frame->entries;
 728 +               at = frame->at;
 729 +
 730 +               if (!(bh = ext3_bread(handle,dir, dx_get_block(at), 0,&retval)))
 731 +                       goto dxfail1;
 732 +
 733 +               BUFFER_TRACE(bh, "get_write_access");
 734 +               ext3_journal_get_write_access(handle, bh);
 735 +
 736 +               data1 = bh->b_data;
 737 +               de = (ext3_dirent *) data1;
 738 +               top = data1 + (0? 200: sb->s_blocksize);
 739 +               while ((char *) de < top)
 740 +               {
 741 +                       /* FIXME: check EEXIST and dir */
 742 +                       nlen = EXT3_DIR_REC_LEN(de->name_len);
 743 +                       rlen = le16_to_cpu(de->rec_len);
 744 +                       if ((de->inode? rlen - nlen: rlen) >= reclen)
 745 +                               goto dx_add;
 746 +                       de = (ext3_dirent *) ((char *) de + rlen);
 747 +               }
 748 +               /* Block full, should compress but for now just split */
 749 +               dxtrace(printk("using %u of %u node entries\n",
 750 +                       dx_get_count(entries), dx_get_limit(entries)));
 751 +               /* Need to split index? */
 752 +               if (dx_get_count(entries) == dx_get_limit(entries))
 753 +               {
 754 +                       u32 newblock;
 755 +                       unsigned icount = dx_get_count(entries);
 756 +                       int levels = frame - frames;
 757 +                       struct dx_entry *entries2;
 758 +                       struct dx_node *node2;
 759 +                       struct buffer_head *bh2;
 760 +                       if (levels && dx_get_count(frames->entries) == dx_get_limit(frames->entries))
 761 +                               goto dxfull;
 762 +                       bh2 = ext3_append (handle, dir, &newblock, &retval);
 763 +                       if (!(bh2))
 764 +                               goto dxfail2;
 765 +                       node2 = (struct dx_node *)(bh2->b_data);
 766 +                       entries2 = node2->entries;
 767 +                       node2->fake.rec_len = cpu_to_le16(sb->s_blocksize);
 768 +                       node2->fake.inode = 0;
 769 +                       BUFFER_TRACE(frame->bh, "get_write_access");
 770 +                       ext3_journal_get_write_access(handle, frame->bh);
 771 +                       if (levels)
 772 +                       {
 773 +                               unsigned icount1 = icount/2, icount2 = icount - icount1;
 774 +                               unsigned hash2 = dx_get_hash(entries + icount1);
 775 +                               dxtrace(printk("Split index %i/%i\n", icount1, icount2));
 776 +
 777 +                               BUFFER_TRACE(frame->bh, "get_write_access"); /* index root */
 778 +                               ext3_journal_get_write_access(handle, frames[0].bh);
 779 +
 780 +                               memcpy ((char *) entries2, (char *) (entries + icount1),
 781 +                                       icount2 * sizeof(struct dx_entry));
 782 +                               dx_set_count (entries, icount1);
 783 +                               dx_set_count (entries2, icount2);
 784 +                               dx_set_limit (entries2, dx_node_limit(dir));
 785 +
 786 +                               /* Which index block gets the new entry? */
 787 +                               if (at - entries >= icount1) {
 788 +                                       frame->at = at = at - entries - icount1 + entries2;
 789 +                                       frame->entries = entries = entries2;
 790 +                                       swap(frame->bh, bh2);
 791                                 }
 792 -
 793 -                               ext3_debug ("creating next block\n");
 794 -
 795 -                               BUFFER_TRACE(bh, "get_write_access");
 796 -                               ext3_journal_get_write_access(handle, bh);
 797 -                               de = (struct ext3_dir_entry_2 *) bh->b_data;
 798 -                               de->inode = 0;
 799 -                               de->rec_len = le16_to_cpu(sb->s_blocksize);
 800 -                               dir->u.ext3_i.i_disksize =
 801 -                                       dir->i_size = offset + sb->s_blocksize;
 802 -                               dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
 803 -                               ext3_mark_inode_dirty(handle, dir);
 804 +                               dx_insert_block (frames + 0, hash2, newblock);
 805 +                               dxtrace(dx_show_index ("node", frames[1].entries));
 806 +                               dxtrace(dx_show_index ("node",
 807 +                                       ((struct dx_node *) bh2->b_data)->entries));
 808 +                               ext3_journal_dirty_metadata(handle, bh2);
 809 +                               brelse (bh2);
 810                         } else {
 811 -
 812 -                               ext3_debug ("skipping to next block\n");
 813 -
 814 -                               de = (struct ext3_dir_entry_2 *) bh->b_data;
 815 +                               dxtrace(printk("Creating second level index...\n"));
 816 +                               memcpy((char *) entries2, (char *) entries,
 817 +                                       icount * sizeof(struct dx_entry));
 818 +                               dx_set_limit(entries2, dx_node_limit(dir));
 819 +
 820 +                               /* Set up root */
 821 +                               dx_set_count(entries, 1);
 822 +                               dx_set_block(entries + 0, newblock);
 823 +                               ((struct dx_root *) frames[0].bh->b_data)->info.indirect_levels = 1;
 824 +
 825 +                               /* Add new access path frame */
 826 +                               frame = frames + 1;
 827 +                               frame->at = at = at - entries + entries2;
 828 +                               frame->entries = entries = entries2;
 829 +                               frame->bh = bh2;
 830 +                               ext3_journal_get_write_access(handle, frame->bh);
 831                         }
 832 +                       ext3_journal_dirty_metadata(handle, frames[0].bh);
 833                 }
 834 -               if (!ext3_check_dir_entry ("ext3_add_entry", dir, de, bh,
 835 -                                          offset)) {
 836 -                       brelse (bh);
 837 -                       return -ENOENT;
 838 -               }
 839 -               if (ext3_match (namelen, name, de)) {
 840 +               de = do_split(handle, dir, &bh, frame, hash, &retval);
 841 +               dx_release (frames);
 842 +               if (!(de))
 843 +                       goto fail;
 844 +               nlen = EXT3_DIR_REC_LEN(de->name_len);
 845 +               rlen = le16_to_cpu(de->rec_len);
 846 +               goto add;
 847 +
 848 +dx_add:
 849 +               dx_release (frames);
 850 +               goto add;
 851 +
 852 +dxfull:
 853 +               ext3_warning(sb, __FUNCTION__, "Directory index full!\n");
 854 +               retval = -ENOSPC;
 855 +dxfail2:
 856 +               brelse(bh);
 857 +dxfail1:
 858 +               dx_release (frames);
 859 +               goto fail1;
 860 +       }
 861 +
 862 +       blocks = dir->i_size >> sb->s_blocksize_bits;
 863 +       for (block = 0, offset = 0; block < blocks; block++) {
 864 +               bh = ext3_bread(handle, dir, block, 0, &retval);
 865 +               if(!bh)
 866 +                       return retval;
 867 +               de = (ext3_dirent *)bh->b_data;
 868 +               top = bh->b_data + sb->s_blocksize - reclen;
 869 +               while ((char *) de <= top) {
 870 +                       if (!ext3_check_dir_entry("ext3_add_entry", dir, de,
 871 +                                                 bh, offset)) {
 872 +                               brelse (bh);
 873 +                               return -EIO;
 874 +                       }
 875 +                       if (ext3_match(dentry->d_name.len,dentry->d_name.name,de)) {
 876                                 brelse (bh);
 877                                 return -EEXIST;
 878 -               }
 879 -               if ((le32_to_cpu(de->inode) == 0 &&
 880 -                               le16_to_cpu(de->rec_len) >= rec_len) ||
 881 -                   (le16_to_cpu(de->rec_len) >=
 882 -                               EXT3_DIR_REC_LEN(de->name_len) + rec_len)) {
 883 -                       BUFFER_TRACE(bh, "get_write_access");
 884 -                       ext3_journal_get_write_access(handle, bh);
 885 -                       /* By now the buffer is marked for journaling */
 886 -                       offset += le16_to_cpu(de->rec_len);
 887 -                       if (le32_to_cpu(de->inode)) {
 888 -                               de1 = (struct ext3_dir_entry_2 *) ((char *) de +
 889 -                                       EXT3_DIR_REC_LEN(de->name_len));
 890 -                               de1->rec_len =
 891 -                                       cpu_to_le16(le16_to_cpu(de->rec_len) -
 892 -                                       EXT3_DIR_REC_LEN(de->name_len));
 893 -                               de->rec_len = cpu_to_le16(
 894 -                                               EXT3_DIR_REC_LEN(de->name_len));
 895 -                               de = de1;
 896                         }
 897 -                       de->file_type = EXT3_FT_UNKNOWN;
 898 -                       if (inode) {
 899 -                               de->inode = cpu_to_le32(inode->i_ino);
 900 -                               ext3_set_de_type(dir->i_sb, de, inode->i_mode);
 901 -                       } else
 902 -                               de->inode = 0;
 903 -                       de->name_len = namelen;
 904 -                       memcpy (de->name, name, namelen);
 905 -                       /*
 906 -                        * XXX shouldn't update any times until successful
 907 -                        * completion of syscall, but too many callers depend
 908 -                        * on this.
 909 -                        *
 910 -                        * XXX similarly, too many callers depend on
 911 -                        * ext3_new_inode() setting the times, but error
 912 -                        * recovery deletes the inode, so the worst that can
 913 -                        * happen is that the times are slightly out of date
 914 -                        * and/or different from the directory change time.
 915 -                        */
 916 -                       dir->i_mtime = dir->i_ctime = CURRENT_TIME;
 917 -                       dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
 918 -                       dir->i_version = ++event;
 919 -                       ext3_mark_inode_dirty(handle, dir);
 920 -                       BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
 921 -                       ext3_journal_dirty_metadata(handle, bh);
 922 +                       nlen = EXT3_DIR_REC_LEN(de->name_len);
 923 +                       rlen = le16_to_cpu(de->rec_len);
 924 +                       if ((de->inode ? rlen - nlen: rlen) >= reclen)
 925 +                               goto add;
 926 +                       de = (ext3_dirent *)((char *)de + rlen);
 927 +                       offset += rlen;
 928 +               }
 929 +               if (ext3_dx && blocks == 1 && test_opt(sb, INDEX))
 930 +                       goto dx_make_index;
 931 +               brelse(bh);
 932 +       }
 933 +       bh = ext3_append(handle, dir, &block, &retval);
 934 +       if (!bh)
 935 +               return retval;
 936 +       de = (ext3_dirent *) bh->b_data;
 937 +       de->inode = 0;
 938 +       de->rec_len = cpu_to_le16(rlen = sb->s_blocksize);
 939 +       nlen = 0;
 940 +       goto add;
 941 +
 942 +add:
 943 +       BUFFER_TRACE(bh, "get_write_access");
 944 +       ext3_journal_get_write_access(handle, bh);
 945 +       /* By now the buffer is marked for journaling */
 946 +       if (de->inode) {
 947 +               ext3_dirent *de1 = (ext3_dirent *)((char *)de + nlen);
 948 +               de1->rec_len = cpu_to_le16(rlen - nlen);
 949 +               de->rec_len = cpu_to_le16(nlen);
 950 +               de = de1;
 951 +       }
 952 +       de->file_type = EXT3_FT_UNKNOWN;
 953 +       if (inode) {
 954 +               de->inode = cpu_to_le32(inode->i_ino);
 955 +               ext3_set_de_type(dir->i_sb, de, inode->i_mode);
 956 +       } else
 957 +               de->inode = 0;
 958 +       de->name_len = dentry->d_name.len;
 959 +       memcpy (de->name, dentry->d_name.name, dentry->d_name.len);
 960 +       /*
 961 +        * XXX shouldn't update any times until successful
 962 +        * completion of syscall, but too many callers depend
 963 +        * on this.
 964 +        *
 965 +        * XXX similarly, too many callers depend on
 966 +        * ext3_new_inode() setting the times, but error
 967 +        * recovery deletes the inode, so the worst that can
 968 +        * happen is that the times are slightly out of date
 969 +        * and/or different from the directory change time.
 970 +        */
 971 +       dir->i_mtime = dir->i_ctime = CURRENT_TIME;
 972 +       ext3_update_dx_flag(dir);
 973 +       dir->i_version = ++event;
 974 +       ext3_mark_inode_dirty(handle, dir);
 975 +       BUFFER_TRACE(bh, "call ext3_journal_dirty_metadata");
 976 +       ext3_journal_dirty_metadata(handle, bh);
 977 +       brelse(bh);
 978 +       return 0;
 979 +
 980 +dx_make_index:
 981 +       {
 982 +               struct buffer_head *bh2;
 983 +               struct dx_root *root;
 984 +               struct dx_frame frames[2], *frame;
 985 +               struct dx_entry *entries;
 986 +               ext3_dirent *de2;
 987 +               char *data1;
 988 +               unsigned len;
 989 +               u32 hash;
 990 +
 991 +               dxtrace(printk("Creating index\n"));
 992 +               ext3_journal_get_write_access(handle, bh);
 993 +               root = (struct dx_root *) bh->b_data;
 994 +
 995 +               EXT3_I(dir)->i_flags |= EXT3_INDEX_FL;
 996 +               bh2 = ext3_append (handle, dir, &block, &retval);
 997 +               if (!(bh2))
 998 +               {
 999                         brelse(bh);
1000 -                       return 0;
1001 +                       return retval;
1002                 }
1003 -               offset += le16_to_cpu(de->rec_len);
1004 -               de = (struct ext3_dir_entry_2 *)
1005 -                       ((char *) de + le16_to_cpu(de->rec_len));
1006 +               data1 = bh2->b_data;
1007 +
1008 +               /* The 0th block becomes the root, move the dirents out */
1009 +               de = (struct ext3_dir_entry_2 *) &root->dotdot;
1010 +               de = (struct ext3_dir_entry_2 *) ((char *)de + de->rec_len);
1011 +               len = ((char *) root) + sb->s_blocksize - (char *) de;
1012 +               memcpy (data1, de, len);
1013 +               de = (ext3_dirent *) data1;
1014 +               top = data1 + len;
1015 +               while (((char *) de2=(char*)de+le16_to_cpu(de->rec_len)) < top)
1016 +                       de = de2;
1017 +               de->rec_len = cpu_to_le16(data1 + sb->s_blocksize - (char *)de);
1018 +               /* Initialize the root; the dot dirents already exist */
1019 +               de = (ext3_dirent *) (&root->dotdot);
1020 +               de->rec_len = cpu_to_le16(sb->s_blocksize-EXT3_DIR_REC_LEN(2));
1021 +               memset (&root->info, 0, sizeof(root->info));
1022 +               root->info.info_length = sizeof(root->info);
1023 +               entries = root->entries;
1024 +               dx_set_block (entries, 1);
1025 +               dx_set_count (entries, 1);
1026 +               dx_set_limit (entries, dx_root_limit(dir, sizeof(root->info)));
1027 +
1028 +               /* Initialize as for dx_probe */
1029 +               hash = dx_hash (dentry->d_name.name, dentry->d_name.len);
1030 +               frame = frames;
1031 +               frame->entries = entries;
1032 +               frame->at = entries;
1033 +               frame->bh = bh;
1034 +               bh = bh2;
1035 +               de = do_split(handle,dir, &bh, frame, hash, &retval);
1036 +               dx_release (frames);
1037 +               if (!(de))
1038 +                       return retval;
1039 +               nlen = EXT3_DIR_REC_LEN(de->name_len);
1040 +               rlen = le16_to_cpu(de->rec_len);
1041 +               goto add;
1042         }
1043 -       brelse (bh);
1044 -       return -ENOSPC;
1045 +fail1:
1046 +       return retval;
1047 +fail:
1048 +       return -ENOENT;
1049  }
1050
1051  /*
1052 @@ -451,7 +1212,8 @@
1053         struct inode * inode;
1054         int err;
1055
1056 -       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS + 3);
1057 +       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS +
1058 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3);
1059         if (IS_ERR(handle))
1060                 return PTR_ERR(handle);
1061
1062 @@ -478,7 +1240,8 @@
1063         struct inode *inode;
1064         int err;
1065
1066 -       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS + 3);
1067 +       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS +
1068 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3);
1069         if (IS_ERR(handle))
1070                 return PTR_ERR(handle);
1071
1072 @@ -507,7 +1270,8 @@
1073         if (dir->i_nlink >= EXT3_LINK_MAX)
1074                 return -EMLINK;
1075
1076 -       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS + 3);
1077 +       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS +
1078 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 3);
1079         if (IS_ERR(handle))
1080                 return PTR_ERR(handle);
1081
1082 @@ -550,7 +1320,7 @@
1083         if (err)
1084                 goto out_no_entry;
1085         dir->i_nlink++;
1086 -       dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
1087 +       ext3_update_dx_flag(dir);
1088         ext3_mark_inode_dirty(handle, dir);
1089         d_instantiate(dentry, inode);
1090  out_stop:
1091 @@ -832,7 +1596,7 @@
1092         ext3_mark_inode_dirty(handle, inode);
1093         dir->i_nlink--;
1094         inode->i_ctime = dir->i_ctime = dir->i_mtime = CURRENT_TIME;
1095 -       dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
1096 +       ext3_update_dx_flag(dir);
1097         ext3_mark_inode_dirty(handle, dir);
1098
1099  end_rmdir:
1100 @@ -878,7 +1642,7 @@
1101         if (retval)
1102                 goto end_unlink;
1103         dir->i_ctime = dir->i_mtime = CURRENT_TIME;
1104 -       dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
1105 +       ext3_update_dx_flag(dir);
1106         ext3_mark_inode_dirty(handle, dir);
1107         inode->i_nlink--;
1108         if (!inode->i_nlink)
1109 @@ -904,7 +1668,8 @@
1110         if (l > dir->i_sb->s_blocksize)
1111                 return -ENAMETOOLONG;
1112
1113 -       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS + 5);
1114 +       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS +
1115 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 5);
1116         if (IS_ERR(handle))
1117                 return PTR_ERR(handle);
1118
1119 @@ -959,7 +1724,8 @@
1120         if (inode->i_nlink >= EXT3_LINK_MAX)
1121                 return -EMLINK;
1122
1123 -       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS);
1124 +       handle = ext3_journal_start(dir, EXT3_DATA_TRANS_BLOCKS +
1125 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS);
1126         if (IS_ERR(handle))
1127                 return PTR_ERR(handle);
1128
1129 @@ -995,7 +1761,8 @@
1130
1131         old_bh = new_bh = dir_bh = NULL;
1132
1133 -       handle = ext3_journal_start(old_dir, 2 * EXT3_DATA_TRANS_BLOCKS + 2);
1134 +       handle = ext3_journal_start(old_dir, 2 * EXT3_DATA_TRANS_BLOCKS +
1135 +                                       EXT3_INDEX_EXTRA_TRANS_BLOCKS + 2);
1136         if (IS_ERR(handle))
1137                 return PTR_ERR(handle);
1138
1139 @@ -1077,7 +1844,7 @@
1140                 new_inode->i_ctime = CURRENT_TIME;
1141         }
1142         old_dir->i_ctime = old_dir->i_mtime = CURRENT_TIME;
1143 -       old_dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
1144 +       ext3_update_dx_flag(old_dir);
1145         if (dir_bh) {
1146                 BUFFER_TRACE(dir_bh, "get_write_access");
1147                 ext3_journal_get_write_access(handle, dir_bh);
1148 @@ -1089,7 +1856,7 @@
1149                         new_inode->i_nlink--;
1150                 } else {
1151                         new_dir->i_nlink++;
1152 -                       new_dir->u.ext3_i.i_flags &= ~EXT3_INDEX_FL;
1153 +                       ext3_update_dx_flag(new_dir);
1154                         ext3_mark_inode_dirty(handle, new_dir);
1155                 }
1156         }
1157 --- ./include/linux/ext3_fs.h   2002/03/05 06:18:59     2.1
1158 +++ ./include/linux/ext3_fs.h   2002/03/05 06:26:56
1159 @@ -339,6 +339,7 @@
1160    #define EXT3_MOUNT_WRITEBACK_DATA    0x0C00  /* No data ordering */
1161  #define EXT3_MOUNT_UPDATE_JOURNAL      0x1000  /* Update the journal format */
1162  #define EXT3_MOUNT_NO_UID32            0x2000  /* Disable 32-bit UIDs */
1163 +#define EXT3_MOUNT_INDEX               0x4000  /* Enable directory index */
1164
1165  /* Compatibility, for having both ext2_fs.h and ext3_fs.h included at once */
1166  #ifndef _LINUX_EXT2_FS_H
1167 @@ -575,6 +576,24 @@
1168  #define EXT3_DIR_ROUND                 (EXT3_DIR_PAD - 1)
1169  #define EXT3_DIR_REC_LEN(name_len)     (((name_len) + 8 + EXT3_DIR_ROUND) & \
1170                                          ~EXT3_DIR_ROUND)
1171 +/*
1172 + * Hash Tree Directory indexing
1173 + * (c) Daniel Phillips, 2001
1174 + */
1175 +
1176 +#define CONFIG_EXT3_INDEX
1177 +
1178 +#ifdef CONFIG_EXT3_INDEX
1179 +  enum {ext3_dx = 1};
1180 +  #define is_dx(dir) (EXT3_I(dir)->i_flags & EXT3_INDEX_FL)
1181 +#define EXT3_DIR_LINK_MAX(dir) (!is_dx(dir) && (dir)->i_nlink >= EXT3_LINK_MAX)
1182 +#define EXT3_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2 || (dir)->i_nlink == 1)
1183 +#else
1184 +  enum {ext3_dx = 0};
1185 +  #define is_dx(dir) 0
1186 +#define EXT3_DIR_LINK_MAX(dir) ((dir)->i_nlink >= EXT3_LINK_MAX)
1187 +#define EXT3_DIR_LINK_EMPTY(dir) ((dir)->i_nlink == 2)
1188 +#endif
1189
1190  #ifdef __KERNEL__
1191  /*
1192 --- ./include/linux/ext3_jbd.h  2002/03/05 06:18:59     2.1
1193 +++ ./include/linux/ext3_jbd.h  2002/03/05 06:33:54
1194 @@ -63,6 +63,8 @@
1195
1196  #define EXT3_RESERVE_TRANS_BLOCKS      12
1197
1198 +#define EXT3_INDEX_EXTRA_TRANS_BLOCKS  8
1199 +
1200  int
1201  ext3_mark_iloc_dirty(handle_t *handle,
1202                      struct inode *inode,