e2fsck/rehash.c

   1 /*
   2  * rehash.c --- rebuild hash tree directories
   3  *
   4  * Copyright (C) 2002 Theodore Ts'o
   5  *
   6  * %Begin-Header%
   7  * This file may be redistributed under the terms of the GNU Public
   8  * License.
   9  * %End-Header%
  10  *
  11  * This algorithm is designed for simplicity of implementation and to
  12  * pack the directory as much as possible.  It however requires twice
  13  * as much memory as the size of the directory.  The maximum size
  14  * directory supported using a 4k blocksize is roughly a gigabyte, and
  15  * so there may very well be problems with machines that don't have
  16  * virtual memory, and obscenely large directories.
  17  *
  18  * An alternate algorithm which is much more disk intensive could be
  19  * written, and probably will need to be written in the future.  The
  20  * design goals of such an algorithm are: (a) use (roughly) constant
  21  * amounts of memory, no matter how large the directory, (b) the
  22  * directory must be safe at all times, even if e2fsck is interrupted
  23  * in the middle, (c) we must use minimal amounts of extra disk
  24  * blocks.  This pretty much requires an incremental approach, where
  25  * we are reading from one part of the directory, and inserting into
  26  * the front half.  So the algorithm will have to keep track of a
  27  * moving block boundary between the new tree and the old tree, and
  28  * files will need to be moved from the old directory and inserted
  29  * into the new tree.  If the new directory requires space which isn't
  30  * yet available, blocks from the beginning part of the old directory
  31  * may need to be moved to the end of the directory to make room for
  32  * the new tree:
  33  *
  34  *    --------------------------------------------------------
  35  *    |  new tree   |        | old tree                      |
  36  *    --------------------------------------------------------
  37  *                  ^ ptr    ^ptr
  38  *                tail new   head old
  39  *
  40  * This is going to be a pain in the tuckus to implement, and will
  41  * require a lot more disk accesses.  So I'm going to skip it for now;
  42  * it's only really going to be an issue for really, really big
  43  * filesystems (when we reach the level of tens of millions of files
  44  * in a single directory).  It will probably be easier to simply
  45  * require that e2fsck use VM first.
  46  */
  47
  48 #include "config.h"
  49 #include <string.h>
  50 #include <ctype.h>
  51 #include <errno.h>
  52 #include "e2fsck.h"
  53 #include "problem.h"
  54
  55 struct fill_dir_struct {
  56         char *buf;
  57         struct ext2_inode *inode;
  58         errcode_t err;
  59         e2fsck_t ctx;
  60         struct hash_entry *harray;
  61         int max_array, num_array;
  62         unsigned int dir_size;
  63         int compress;
  64         ino_t parent;
  65         struct ext2_dir_entry *dot_de;
  66         struct ext2_dir_entry *dotdot_de;
  67 };
  68
  69 struct hash_entry {
  70         ext2_dirhash_t  hash;
  71         ext2_dirhash_t  minor_hash;
  72         ino_t           ino;
  73         struct ext2_dir_entry   *dir;
  74 };
  75
  76 struct out_dir {
  77         int             num;
  78         int             max;
  79         char            *buf;
  80         ext2_dirhash_t  *hashes;
  81 };
  82
  83 static int fill_dir_block(ext2_filsys fs,
  84                           blk64_t *block_nr,
  85                           e2_blkcnt_t blockcnt,
  86                           blk64_t ref_block EXT2FS_ATTR((unused)),
  87                           int ref_offset EXT2FS_ATTR((unused)),
  88                           void *priv_data)
  89 {
  90         struct fill_dir_struct  *fd = (struct fill_dir_struct *) priv_data;
  91         struct hash_entry       *new_array, *ent;
  92         struct ext2_dir_entry   *dirent;
  93         char                    *dir;
  94         unsigned int            offset, dir_offset, rec_len;
  95         int                     hash_alg;
  96
  97         if (blockcnt < 0)
  98                 return 0;
  99
 100         offset = blockcnt * fs->blocksize;
 101         if (offset + fs->blocksize > fd->inode->i_size) {
 102                 fd->err = EXT2_ET_DIR_CORRUPTED;
 103                 return BLOCK_ABORT;
 104         }
 105         dir = (fd->buf+offset);
 106         if (HOLE_BLKADDR(*block_nr)) {
 107                 memset(dir, 0, fs->blocksize);
 108                 dirent = (struct ext2_dir_entry *) dir;
 109                 (void) ext2fs_set_rec_len(fs, fs->blocksize, dirent);
 110         } else {
 111                 fd->err = ext2fs_read_dir_block3(fs, *block_nr, dir, 0);
 112                 if (fd->err)
 113                         return BLOCK_ABORT;
 114         }
 115         hash_alg = fs->super->s_def_hash_version;
 116         if ((hash_alg <= EXT2_HASH_TEA) &&
 117             (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
 118                 hash_alg += 3;
 119         /* While the directory block is "hot", index it. */
 120         dir_offset = 0;
 121         while (dir_offset < fs->blocksize) {
 122                 dirent = (struct ext2_dir_entry *) (dir + dir_offset);
 123                 (void) ext2fs_get_rec_len(fs, dirent, &rec_len);
 124                 if (((dir_offset + rec_len) > fs->blocksize) ||
 125                     (rec_len < 8) ||
 126                     ((rec_len % 4) != 0) ||
 127                     (((dirent->name_len & 0xFF)+8U) > rec_len)) {
 128                         fd->err = EXT2_ET_DIR_CORRUPTED;
 129                         return BLOCK_ABORT;
 130                 }
 131                 dir_offset += rec_len;
 132                 if (dirent->inode == 0)
 133                         continue;
 134                 if (!fd->compress && ((dirent->name_len & 0xFF) == 1) &&
 135                     (dirent->name[0] == '.')) {
 136                         fd->dot_de = dirent;
 137                         continue;
 138                 }
 139                 if (!fd->compress && ((dirent->name_len & 0xFF) == 2) &&
 140                     (dirent->name[0] == '.') && (dirent->name[1] == '.')) {
 141                         fd->parent = dirent->inode;
 142                         fd->dotdot_de = dirent;
 143                         continue;
 144                 }
 145                 if (fd->num_array >= fd->max_array) {
 146                         new_array = realloc(fd->harray,
 147                             sizeof(struct hash_entry) * (fd->max_array+500));
 148                         if (!new_array) {
 149                                 fd->err = ENOMEM;
 150                                 return BLOCK_ABORT;
 151                         }
 152                         fd->harray = new_array;
 153                         fd->max_array += 500;
 154                 }
 155                 ent = fd->harray + fd->num_array++;
 156                 ent->dir = dirent;
 157                 fd->dir_size += EXT2_DIR_REC_LEN(dirent);
 158                 ent->ino = dirent->inode;
 159                 if (fd->compress)
 160                         ent->hash = ent->minor_hash = 0;
 161                 else {
 162                         fd->err = ext2fs_dirhash(hash_alg, dirent->name,
 163                                                  dirent->name_len & 0xFF,
 164                                                  fs->super->s_hash_seed,
 165                                                  &ent->hash, &ent->minor_hash);
 166                         if (fd->err)
 167                                 return BLOCK_ABORT;
 168                 }
 169         }
 170
 171         return 0;
 172 }
 173
 174 /* Used for sorting the hash entry */
 175 static EXT2_QSORT_TYPE ino_cmp(const void *a, const void *b)
 176 {
 177         const struct hash_entry *he_a = (const struct hash_entry *) a;
 178         const struct hash_entry *he_b = (const struct hash_entry *) b;
 179
 180         return (he_a->ino - he_b->ino);
 181 }
 182
 183 /* Used for sorting the hash entry */
 184 static EXT2_QSORT_TYPE name_cmp(const void *a, const void *b)
 185 {
 186         const struct hash_entry *he_a = (const struct hash_entry *) a;
 187         const struct hash_entry *he_b = (const struct hash_entry *) b;
 188         int     ret;
 189         int     min_len;
 190
 191         min_len = he_a->dir->name_len;
 192         if (min_len > he_b->dir->name_len)
 193                 min_len = he_b->dir->name_len;
 194
 195         ret = strncmp(he_a->dir->name, he_b->dir->name, min_len);
 196         if (ret == 0) {
 197                 if (he_a->dir->name_len > he_b->dir->name_len)
 198                         ret = 1;
 199                 else if (he_a->dir->name_len < he_b->dir->name_len)
 200                         ret = -1;
 201                 else
 202                         ret = he_b->dir->inode - he_a->dir->inode;
 203         }
 204         return ret;
 205 }
 206
 207 /* Used for sorting the hash entry */
 208 static EXT2_QSORT_TYPE hash_cmp(const void *a, const void *b)
 209 {
 210         const struct hash_entry *he_a = (const struct hash_entry *) a;
 211         const struct hash_entry *he_b = (const struct hash_entry *) b;
 212         int     ret;
 213
 214         if (he_a->hash > he_b->hash)
 215                 ret = 1;
 216         else if (he_a->hash < he_b->hash)
 217                 ret = -1;
 218         else {
 219                 if (he_a->minor_hash > he_b->minor_hash)
 220                         ret = 1;
 221                 else if (he_a->minor_hash < he_b->minor_hash)
 222                         ret = -1;
 223                 else
 224                         ret = name_cmp(a, b);
 225         }
 226         return ret;
 227 }
 228
 229 static errcode_t alloc_size_dir(ext2_filsys fs, struct out_dir *outdir,
 230                                 int blocks)
 231 {
 232         void                    *new_mem;
 233
 234         if (outdir->max) {
 235                 new_mem = realloc(outdir->buf, blocks * fs->blocksize);
 236                 if (!new_mem)
 237                         return ENOMEM;
 238                 outdir->buf = new_mem;
 239                 new_mem = realloc(outdir->hashes,
 240                                   blocks * sizeof(ext2_dirhash_t));
 241                 if (!new_mem)
 242                         return ENOMEM;
 243                 outdir->hashes = new_mem;
 244         } else {
 245                 outdir->buf = malloc(blocks * fs->blocksize);
 246                 outdir->hashes = malloc(blocks * sizeof(ext2_dirhash_t));
 247                 outdir->num = 0;
 248         }
 249         outdir->max = blocks;
 250         return 0;
 251 }
 252
 253 static void free_out_dir(struct out_dir *outdir)
 254 {
 255         free(outdir->buf);
 256         free(outdir->hashes);
 257         outdir->max = 0;
 258         outdir->num =0;
 259 }
 260
 261 static errcode_t get_next_block(ext2_filsys fs, struct out_dir *outdir,
 262                          char ** ret)
 263 {
 264         errcode_t       retval;
 265
 266         if (outdir->num >= outdir->max) {
 267                 retval = alloc_size_dir(fs, outdir, outdir->max + 50);
 268                 if (retval)
 269                         return retval;
 270         }
 271         *ret = outdir->buf + (outdir->num++ * fs->blocksize);
 272         memset(*ret, 0, fs->blocksize);
 273         return 0;
 274 }
 275
 276 /*
 277  * This function is used to make a unique filename.  We do this by
 278  * appending ~0, and then incrementing the number.  However, we cannot
 279  * expand the length of the filename beyond the padding available in
 280  * the directory entry.
 281  */
 282 static void mutate_name(char *str, __u16 *len)
 283 {
 284         int     i;
 285         __u16   l = *len & 0xFF, h = *len & 0xff00;
 286
 287         /*
 288          * First check to see if it looks the name has been mutated
 289          * already
 290          */
 291         for (i = l-1; i > 0; i--) {
 292                 if (!isdigit(str[i]))
 293                         break;
 294         }
 295         if ((i == l-1) || (str[i] != '~')) {
 296                 if (((l-1) & 3) < 2)
 297                         l += 2;
 298                 else
 299                         l = (l+3) & ~3;
 300                 str[l-2] = '~';
 301                 str[l-1] = '0';
 302                 *len = l | h;
 303                 return;
 304         }
 305         for (i = l-1; i >= 0; i--) {
 306                 if (isdigit(str[i])) {
 307                         if (str[i] == '9')
 308                                 str[i] = '0';
 309                         else {
 310                                 str[i]++;
 311                                 return;
 312                         }
 313                         continue;
 314                 }
 315                 if (i == 1) {
 316                         if (str[0] == 'z')
 317                                 str[0] = 'A';
 318                         else if (str[0] == 'Z') {
 319                                 str[0] = '~';
 320                                 str[1] = '0';
 321                         } else
 322                                 str[0]++;
 323                 } else if (i > 0) {
 324                         str[i] = '1';
 325                         str[i-1] = '~';
 326                 } else {
 327                         if (str[0] == '~')
 328                                 str[0] = 'a';
 329                         else
 330                                 str[0]++;
 331                 }
 332                 break;
 333         }
 334 }
 335
 336 static int duplicate_search_and_fix(e2fsck_t ctx, ext2_filsys fs,
 337                                     ext2_ino_t ino,
 338                                     struct fill_dir_struct *fd)
 339 {
 340         struct problem_context  pctx;
 341         struct hash_entry       *ent, *prev;
 342         int                     i, j;
 343         int                     fixed = 0;
 344         char                    new_name[256];
 345         __u16                   new_len;
 346         int                     hash_alg;
 347
 348         clear_problem_context(&pctx);
 349         pctx.ino = ino;
 350
 351         hash_alg = fs->super->s_def_hash_version;
 352         if ((hash_alg <= EXT2_HASH_TEA) &&
 353             (fs->super->s_flags & EXT2_FLAGS_UNSIGNED_HASH))
 354                 hash_alg += 3;
 355
 356         for (i=1; i < fd->num_array; i++) {
 357                 ent = fd->harray + i;
 358                 prev = ent - 1;
 359                 if (!ent->dir->inode ||
 360                     ((ent->dir->name_len & 0xFF) !=
 361                      (prev->dir->name_len & 0xFF)) ||
 362                     (strncmp(ent->dir->name, prev->dir->name,
 363                              ent->dir->name_len & 0xFF)))
 364                         continue;
 365                 pctx.dirent = ent->dir;
 366                 if ((ent->dir->inode == prev->dir->inode) &&
 367                     fix_problem(ctx, PR_2_DUPLICATE_DIRENT, &pctx)) {
 368                         e2fsck_adjust_inode_count(ctx, ent->dir->inode, -1);
 369                         ent->dir->inode = 0;
 370                         fixed++;
 371                         continue;
 372                 }
 373                 memcpy(new_name, ent->dir->name, ent->dir->name_len & 0xFF);
 374                 new_len = ent->dir->name_len;
 375                 mutate_name(new_name, &new_len);
 376                 for (j=0; j < fd->num_array; j++) {
 377                         if ((i==j) ||
 378                             ((new_len & 0xFF) !=
 379                              (fd->harray[j].dir->name_len & 0xFF)) ||
 380                             (strncmp(new_name, fd->harray[j].dir->name,
 381                                      new_len & 0xFF)))
 382                                 continue;
 383                         mutate_name(new_name, &new_len);
 384
 385                         j = -1;
 386                 }
 387                 new_name[new_len & 0xFF] = 0;
 388                 pctx.str = new_name;
 389                 if (fix_problem(ctx, PR_2_NON_UNIQUE_FILE, &pctx)) {
 390                         memcpy(ent->dir->name, new_name, new_len & 0xFF);
 391                         ent->dir->name_len = new_len;
 392                         ext2fs_dirhash(hash_alg, ent->dir->name,
 393                                        ent->dir->name_len & 0xFF,
 394                                        fs->super->s_hash_seed,
 395                                        &ent->hash, &ent->minor_hash);
 396                         fixed++;
 397                 }
 398         }
 399         return fixed;
 400 }
 401
 402
 403 static errcode_t copy_dir_entries(e2fsck_t ctx,
 404                                   struct fill_dir_struct *fd,
 405                                   struct out_dir *outdir)
 406 {
 407         ext2_filsys             fs = ctx->fs;
 408         errcode_t               retval;
 409         char                    *block_start;
 410         struct hash_entry       *ent;
 411         struct ext2_dir_entry   *dirent;
 412         unsigned int            rec_len, prev_rec_len, left, slack, offset;
 413         int                     i;
 414         ext2_dirhash_t          prev_hash;
 415
 416         if (ctx->htree_slack_percentage == 255) {
 417                 profile_get_uint(ctx->profile, "options",
 418                                  "indexed_dir_slack_percentage",
 419                                  0, 20,
 420                                  &ctx->htree_slack_percentage);
 421                 if (ctx->htree_slack_percentage > 100)
 422                         ctx->htree_slack_percentage = 20;
 423         }
 424
 425         outdir->max = 0;
 426         retval = alloc_size_dir(fs, outdir,
 427                                 (fd->dir_size / fs->blocksize) + 2);
 428         if (retval)
 429                 return retval;
 430         outdir->num = fd->compress ? 0 : 1;
 431         offset = 0;
 432         outdir->hashes[0] = 0;
 433         prev_hash = 1;
 434         if ((retval = get_next_block(fs, outdir, &block_start)))
 435                 return retval;
 436         dirent = (struct ext2_dir_entry *) block_start;
 437         prev_rec_len = 0;
 438         rec_len = 0;
 439         left = fs->blocksize;
 440         slack = fd->compress ? 12 :
 441                 (fs->blocksize * ctx->htree_slack_percentage)/100;
 442         if (slack < 12)
 443                 slack = 12;
 444         for (i = 0; i < fd->num_array; i++) {
 445                 ent = fd->harray + i;
 446                 if (ent->dir->inode == 0)
 447                         continue;
 448                 rec_len = EXT2_DIR_REC_LEN(ent->dir);
 449                 if (rec_len > left) {
 450                         if (left) {
 451                                 left += prev_rec_len;
 452                                 retval = ext2fs_set_rec_len(fs, left, dirent);
 453                                 if (retval)
 454                                         return retval;
 455                         }
 456                         if ((retval = get_next_block(fs, outdir,
 457                                                       &block_start)))
 458                                 return retval;
 459                         offset = 0;
 460                 }
 461                 left = fs->blocksize - offset;
 462                 dirent = (struct ext2_dir_entry *) (block_start + offset);
 463                 if (offset == 0) {
 464                         if (ent->hash == prev_hash)
 465                                 outdir->hashes[outdir->num-1] = ent->hash | 1;
 466                         else
 467                                 outdir->hashes[outdir->num-1] = ent->hash;
 468                 }
 469                 dirent->inode = ent->dir->inode;
 470                 dirent->name_len = ent->dir->name_len;
 471                 retval = ext2fs_set_rec_len(fs, rec_len, dirent);
 472                 if (retval)
 473                         return retval;
 474                 prev_rec_len = rec_len;
 475                 memcpy(dirent->name, ent->dir->name, rec_len);
 476                 offset += rec_len;
 477                 left -= rec_len;
 478                 if (left < slack) {
 479                         prev_rec_len += left;
 480                         retval = ext2fs_set_rec_len(fs, prev_rec_len, dirent);
 481                         if (retval)
 482                                 return retval;
 483                         offset += left;
 484                         left = 0;
 485                 }
 486                 prev_hash = ent->hash;
 487         }
 488         if (left)
 489                 retval = ext2fs_set_rec_len(fs, rec_len + left, dirent);
 490
 491         return retval;
 492 }
 493
 494
 495 static struct ext2_dx_root_info *set_root_node(ext2_filsys fs, char *buf,
 496                                         ext2_ino_t ino, ext2_ino_t parent,
 497                                         struct ext2_dir_entry *dot_de,
 498                                         struct ext2_dir_entry *dotdot_de)
 499 {
 500         struct ext2_dir_entry           *dir;
 501         struct ext2_dx_root_info        *root;
 502         struct ext2_dx_countlimit       *limits;
 503         int                             offset;
 504         int                             rec_len;
 505
 506         memset(buf, 0, fs->blocksize);
 507         dir = (struct ext2_dir_entry *) buf;
 508         dir->inode = ino;
 509         dir->name_len = dot_de->name_len;
 510         dir->rec_len = dot_de->rec_len;
 511         rec_len = EXT2_DIR_REC_LEN(dot_de);
 512         memcpy(dir->name, dot_de->name, rec_len);
 513         offset = rec_len;
 514
 515         dir = (struct ext2_dir_entry *) (buf + offset);
 516         /* set to jump over the index block */
 517         dir->inode = parent;
 518         dir->name_len = dotdot_de->name_len;
 519         dir->rec_len = fs->blocksize - rec_len;
 520         rec_len = EXT2_DIR_REC_LEN(dotdot_de);
 521         memcpy(dir->name, dotdot_de->name, rec_len);
 522         offset += rec_len;
 523
 524         root = (struct ext2_dx_root_info *) (buf + offset);
 525         root->reserved_zero = 0;
 526         root->hash_version = fs->super->s_def_hash_version;
 527         root->info_length = sizeof(struct ext2_dx_root_info);
 528         root->indirect_levels = 0;
 529         root->unused_flags = 0;
 530         offset += sizeof(struct ext2_dx_root_info);
 531
 532         limits = (struct ext2_dx_countlimit *) (buf + offset);
 533         limits->limit = (fs->blocksize - offset) / sizeof(struct ext2_dx_entry);
 534         limits->count = 0;
 535
 536         return root;
 537 }
 538
 539
 540 static struct ext2_dx_entry *set_int_node(ext2_filsys fs, char *buf)
 541 {
 542         struct ext2_dir_entry           *dir;
 543         struct ext2_dx_countlimit       *limits;
 544
 545         memset(buf, 0, fs->blocksize);
 546         dir = (struct ext2_dir_entry *) buf;
 547         dir->inode = 0;
 548         (void) ext2fs_set_rec_len(fs, fs->blocksize, dir);
 549
 550         limits = (struct ext2_dx_countlimit *) (buf+8);
 551         limits->limit = (fs->blocksize - 8) / sizeof(struct ext2_dx_entry);
 552         limits->count = 0;
 553
 554         return (struct ext2_dx_entry *) limits;
 555 }
 556
 557 /*
 558  * This function takes the leaf nodes which have been written in
 559  * outdir, and populates the root node and any necessary interior nodes.
 560  */
 561 static errcode_t calculate_tree(ext2_filsys fs,
 562                                 struct out_dir *outdir,
 563                                 ext2_ino_t ino,
 564                                 ext2_ino_t parent,
 565                                 struct ext2_dir_entry *dot_de,
 566                                 struct ext2_dir_entry *dotdot_de)
 567 {
 568         struct ext2_dx_root_info        *root_info;
 569         struct ext2_dx_entry            *root, *dx_ent = 0;
 570         struct ext2_dx_countlimit       *root_limit, *limit;
 571         errcode_t                       retval;
 572         char                            * block_start;
 573         int                             i, c1, c2, nblks;
 574         int                             limit_offset, root_offset;
 575
 576         root_info = set_root_node(fs, outdir->buf, ino, parent, dot_de,
 577                                   dotdot_de);
 578         root_offset = limit_offset = ((char *) root_info - outdir->buf) +
 579                 root_info->info_length;
 580         root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset);
 581         c1 = root_limit->limit;
 582         nblks = outdir->num;
 583
 584         /* Write out the pointer blocks */
 585         if (nblks-1 <= c1) {
 586                 /* Just write out the root block, and we're done */
 587                 root = (struct ext2_dx_entry *) (outdir->buf + root_offset);
 588                 for (i=1; i < nblks; i++) {
 589                         root->block = ext2fs_cpu_to_le32(i);
 590                         if (i != 1)
 591                                 root->hash =
 592                                         ext2fs_cpu_to_le32(outdir->hashes[i]);
 593                         root++;
 594                         c1--;
 595                 }
 596         } else {
 597                 c2 = 0;
 598                 limit = 0;
 599                 root_info->indirect_levels = 1;
 600                 for (i=1; i < nblks; i++) {
 601                         if (c1 == 0)
 602                                 return ENOSPC;
 603                         if (c2 == 0) {
 604                                 if (limit)
 605                                         limit->limit = limit->count =
 606                 ext2fs_cpu_to_le16(limit->limit);
 607                                 root = (struct ext2_dx_entry *)
 608                                         (outdir->buf + root_offset);
 609                                 root->block = ext2fs_cpu_to_le32(outdir->num);
 610                                 if (i != 1)
 611                                         root->hash =
 612                         ext2fs_cpu_to_le32(outdir->hashes[i]);
 613                                 if ((retval =  get_next_block(fs, outdir,
 614                                                               &block_start)))
 615                                         return retval;
 616                                 dx_ent = set_int_node(fs, block_start);
 617                                 limit = (struct ext2_dx_countlimit *) dx_ent;
 618                                 c2 = limit->limit;
 619                                 root_offset += sizeof(struct ext2_dx_entry);
 620                                 c1--;
 621                         }
 622                         dx_ent->block = ext2fs_cpu_to_le32(i);
 623                         if (c2 != limit->limit)
 624                                 dx_ent->hash =
 625                                         ext2fs_cpu_to_le32(outdir->hashes[i]);
 626                         dx_ent++;
 627                         c2--;
 628                 }
 629                 limit->count = ext2fs_cpu_to_le16(limit->limit - c2);
 630                 limit->limit = ext2fs_cpu_to_le16(limit->limit);
 631         }
 632         root_limit = (struct ext2_dx_countlimit *) (outdir->buf + limit_offset);
 633         root_limit->count = ext2fs_cpu_to_le16(root_limit->limit - c1);
 634         root_limit->limit = ext2fs_cpu_to_le16(root_limit->limit);
 635
 636         return 0;
 637 }
 638
 639 struct write_dir_struct {
 640         struct out_dir *outdir;
 641         errcode_t       err;
 642         e2fsck_t        ctx;
 643         blk64_t         cleared;
 644 };
 645
 646 /*
 647  * Helper function which writes out a directory block.
 648  */
 649 static int write_dir_block(ext2_filsys fs,
 650                            blk64_t *block_nr,
 651                            e2_blkcnt_t blockcnt,
 652                            blk64_t ref_block EXT2FS_ATTR((unused)),
 653                            int ref_offset EXT2FS_ATTR((unused)),
 654                            void *priv_data)
 655 {
 656         struct write_dir_struct *wd = (struct write_dir_struct *) priv_data;
 657         blk64_t blk;
 658         char    *dir;
 659
 660         if (*block_nr == 0)
 661                 return 0;
 662         if (blockcnt >= wd->outdir->num) {
 663                 e2fsck_read_bitmaps(wd->ctx);
 664                 blk = *block_nr;
 665                 /*
 666                  * In theory, we only release blocks from the end of the
 667                  * directory file, so it's fine to clobber a whole cluster at
 668                  * once.
 669                  */
 670                 if (blk % EXT2FS_CLUSTER_RATIO(fs) == 0) {
 671                         ext2fs_block_alloc_stats2(fs, blk, -1);
 672                         wd->cleared++;
 673                 }
 674                 *block_nr = 0;
 675                 return BLOCK_CHANGED;
 676         }
 677         if (blockcnt < 0)
 678                 return 0;
 679
 680         dir = wd->outdir->buf + (blockcnt * fs->blocksize);
 681         wd->err = ext2fs_write_dir_block3(fs, *block_nr, dir, 0);
 682         if (wd->err)
 683                 return BLOCK_ABORT;
 684         return 0;
 685 }
 686
 687 static errcode_t write_directory(e2fsck_t ctx, ext2_filsys fs,
 688                                  struct out_dir *outdir,
 689                                  ext2_ino_t ino, int compress)
 690 {
 691         struct write_dir_struct wd;
 692         errcode_t       retval;
 693         struct ext2_inode       inode;
 694
 695         retval = e2fsck_expand_directory(ctx, ino, -1, outdir->num);
 696         if (retval)
 697                 return retval;
 698
 699         wd.outdir = outdir;
 700         wd.err = 0;
 701         wd.ctx = ctx;
 702         wd.cleared = 0;
 703
 704         retval = ext2fs_block_iterate3(fs, ino, 0, 0,
 705                                        write_dir_block, &wd);
 706         if (retval)
 707                 return retval;
 708         if (wd.err)
 709                 return wd.err;
 710
 711         e2fsck_read_inode(ctx, ino, &inode, "rehash_dir");
 712         if (compress)
 713                 inode.i_flags &= ~EXT2_INDEX_FL;
 714         else
 715                 inode.i_flags |= EXT2_INDEX_FL;
 716         retval = ext2fs_inode_size_set(fs, &inode,
 717                                        outdir->num * fs->blocksize);
 718         if (retval)
 719                 return retval;
 720         ext2fs_iblk_sub_blocks(fs, &inode, wd.cleared);
 721         e2fsck_write_inode(ctx, ino, &inode, "rehash_dir");
 722
 723         return 0;
 724 }
 725
 726 errcode_t e2fsck_rehash_dir(e2fsck_t ctx, ext2_ino_t ino)
 727 {
 728         ext2_filsys             fs = ctx->fs;
 729         errcode_t               retval;
 730         struct ext2_inode       inode;
 731         char                    *dir_buf = 0;
 732         struct fill_dir_struct  fd;
 733         struct out_dir          outdir;
 734
 735         outdir.max = outdir.num = 0;
 736         outdir.buf = 0;
 737         outdir.hashes = 0;
 738         e2fsck_read_inode(ctx, ino, &inode, "rehash_dir");
 739
 740         retval = ENOMEM;
 741         fd.harray = 0;
 742         dir_buf = malloc(inode.i_size);
 743         if (!dir_buf)
 744                 goto errout;
 745
 746         fd.max_array = inode.i_size / 32;
 747         fd.num_array = 0;
 748         fd.harray = malloc(fd.max_array * sizeof(struct hash_entry));
 749         if (!fd.harray)
 750                 goto errout;
 751
 752         fd.ctx = ctx;
 753         fd.buf = dir_buf;
 754         fd.inode = &inode;
 755         fd.err = 0;
 756         fd.dir_size = 0;
 757         fd.compress = 0;
 758         if (!(fs->super->s_feature_compat & EXT2_FEATURE_COMPAT_DIR_INDEX) ||
 759             (inode.i_size / fs->blocksize) < 2)
 760                 fd.compress = 1;
 761         fd.parent = 0;
 762
 763 retry_nohash:
 764         /* Read in the entire directory into memory */
 765         retval = ext2fs_block_iterate3(fs, ino, 0, 0,
 766                                        fill_dir_block, &fd);
 767         if (fd.err) {
 768                 retval = fd.err;
 769                 goto errout;
 770         }
 771
 772         /*
 773          * If the entries read are less than a block, then don't index
 774          * the directory
 775          */
 776         if (!fd.compress && (fd.dir_size < (fs->blocksize - 24))) {
 777                 fd.compress = 1;
 778                 fd.dir_size = 0;
 779                 fd.num_array = 0;
 780                 goto retry_nohash;
 781         }
 782
 783 #if 0
 784         printf("%d entries (%d bytes) found in inode %d\n",
 785                fd.num_array, fd.dir_size, ino);
 786 #endif
 787
 788         /* Sort the list */
 789 resort:
 790         if (fd.compress && fd.num_array > 1)
 791                 qsort(fd.harray+2, fd.num_array-2, sizeof(struct hash_entry),
 792                       hash_cmp);
 793         else
 794                 qsort(fd.harray, fd.num_array, sizeof(struct hash_entry),
 795                       hash_cmp);
 796
 797         /*
 798          * Look for duplicates
 799          */
 800         if (duplicate_search_and_fix(ctx, fs, ino, &fd))
 801                 goto resort;
 802
 803         if (ctx->options & E2F_OPT_NO) {
 804                 retval = 0;
 805                 goto errout;
 806         }
 807
 808         /* Sort non-hashed directories by inode number */
 809         if (fd.compress && fd.num_array > 1)
 810                 qsort(fd.harray+2, fd.num_array-2,
 811                       sizeof(struct hash_entry), ino_cmp);
 812
 813         /*
 814          * Copy the directory entries.  In a htree directory these
 815          * will become the leaf nodes.
 816          */
 817         retval = copy_dir_entries(ctx, &fd, &outdir);
 818         if (retval)
 819                 goto errout;
 820
 821         if (!fd.compress) {
 822                 /* Calculate the interior nodes */
 823                 retval = calculate_tree(fs, &outdir, ino, fd.parent,
 824                                         fd.dot_de, fd.dotdot_de);
 825                 if (retval)
 826                         goto errout;
 827         }
 828
 829         retval = write_directory(ctx, fs, &outdir, ino, fd.compress);
 830         if (retval)
 831                 goto errout;
 832
 833 errout:
 834         free(dir_buf);
 835         free(fd.harray);
 836
 837         free_out_dir(&outdir);
 838         return retval;
 839 }
 840
 841 void e2fsck_rehash_directories(e2fsck_t ctx)
 842 {
 843         struct problem_context  pctx;
 844 #ifdef RESOURCE_TRACK
 845         struct resource_track   rtrack;
 846 #endif
 847         struct dir_info         *dir;
 848         ext2_u32_iterate        iter;
 849         struct dir_info_iter *  dirinfo_iter = 0;
 850         ext2_ino_t              ino;
 851         errcode_t               retval;
 852         int                     cur, max, all_dirs, first = 1;
 853
 854         init_resource_track(&rtrack, ctx->fs->io);
 855         all_dirs = ctx->options & E2F_OPT_COMPRESS_DIRS;
 856
 857         if (!ctx->dirs_to_hash && !all_dirs)
 858                 return;
 859
 860         e2fsck_get_lost_and_found(ctx, 0);
 861
 862         clear_problem_context(&pctx);
 863
 864         cur = 0;
 865         if (all_dirs) {
 866                 dirinfo_iter = e2fsck_dir_info_iter_begin(ctx);
 867                 max = e2fsck_get_num_dirinfo(ctx);
 868         } else {
 869                 retval = ext2fs_u32_list_iterate_begin(ctx->dirs_to_hash,
 870                                                        &iter);
 871                 if (retval) {
 872                         pctx.errcode = retval;
 873                         fix_problem(ctx, PR_3A_OPTIMIZE_ITER, &pctx);
 874                         return;
 875                 }
 876                 max = ext2fs_u32_list_count(ctx->dirs_to_hash);
 877         }
 878         while (1) {
 879                 if (all_dirs) {
 880                         if ((dir = e2fsck_dir_info_iter(ctx,
 881                                                         dirinfo_iter)) == 0)
 882                                 break;
 883                         ino = dir->ino;
 884                 } else {
 885                         if (!ext2fs_u32_list_iterate(iter, &ino))
 886                                 break;
 887                 }
 888                 if (ino == ctx->lost_and_found)
 889                         continue;
 890                 pctx.dir = ino;
 891                 if (first) {
 892                         fix_problem(ctx, PR_3A_PASS_HEADER, &pctx);
 893                         first = 0;
 894                 }
 895 #if 0
 896                 fix_problem(ctx, PR_3A_OPTIMIZE_DIR, &pctx);
 897 #endif
 898                 pctx.errcode = e2fsck_rehash_dir(ctx, ino);
 899                 if (pctx.errcode) {
 900                         end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR);
 901                         fix_problem(ctx, PR_3A_OPTIMIZE_DIR_ERR, &pctx);
 902                 }
 903                 if (ctx->progress && !ctx->progress_fd)
 904                         e2fsck_simple_progress(ctx, "Rebuilding directory",
 905                                100.0 * (float) (++cur) / (float) max, ino);
 906         }
 907         end_problem_latch(ctx, PR_LATCH_OPTIMIZE_DIR);
 908         if (all_dirs)
 909                 e2fsck_dir_info_iter_end(ctx, dirinfo_iter);
 910         else
 911                 ext2fs_u32_list_iterate_end(iter);
 912
 913         if (ctx->dirs_to_hash)
 914                 ext2fs_u32_list_free(ctx->dirs_to_hash);
 915         ctx->dirs_to_hash = 0;
 916
 917         print_resource_track(ctx, "Pass 3A", &rtrack, ctx->fs->io);
 918 }