e2fsck/dx_dirinfo.c

   1 /*
   2  * dirinfo.c --- maintains the directory information table for e2fsck.
   3  *
   4  * Copyright (C) 1993 Theodore Ts'o.  This file may be redistributed
   5  * under the terms of the GNU Public License.
   6  */
   7
   8 #include "config.h"
   9 #include "e2fsck.h"
  10
  11 /*
  12  * This subroutine is called during pass1 to create a directory info
  13  * entry.  During pass1, the passed-in parent is 0; it will get filled
  14  * in during pass2.
  15  */
  16 void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, struct ext2_inode *inode,
  17                        int num_blocks)
  18 {
  19         struct dx_dir_info *dir;
  20         ext2_ino_t      i, j;
  21         errcode_t       retval;
  22         unsigned long   old_size;
  23
  24 #if 0
  25         printf("add_dx_dir_info for inode %lu...\n", ino);
  26 #endif
  27         if (!ctx->dx_dir_info) {
  28                 ctx->dx_dir_info_count = 0;
  29                 ctx->dx_dir_info_size = 100; /* Guess */
  30                 ctx->dx_dir_info  = (struct dx_dir_info *)
  31                         e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
  32                                                * sizeof (struct dx_dir_info),
  33                                                "directory map");
  34         }
  35
  36         if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
  37                 old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
  38                 ctx->dx_dir_info_size += 10;
  39                 retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
  40                                            sizeof(struct dx_dir_info),
  41                                            &ctx->dx_dir_info);
  42                 if (retval) {
  43                         fprintf(stderr, "Couldn't reallocate dx_dir_info "
  44                                 "structure to %u entries\n",
  45                                 ctx->dx_dir_info_size);
  46                         fatal_error(ctx, 0);
  47                         ctx->dx_dir_info_size -= 10;
  48                         return;
  49                 }
  50         }
  51
  52         /*
  53          * Normally, add_dx_dir_info is called with each inode in
  54          * sequential order; but once in a while (like when pass 3
  55          * needs to recreate the root directory or lost+found
  56          * directory) it is called out of order.  In those cases, we
  57          * need to move the dx_dir_info entries down to make room, since
  58          * the dx_dir_info array needs to be sorted by inode number for
  59          * get_dx_dir_info()'s sake.
  60          */
  61         if (ctx->dx_dir_info_count &&
  62             ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
  63                 for (i = ctx->dx_dir_info_count-1; i > 0; i--)
  64                         if (ctx->dx_dir_info[i-1].ino < ino)
  65                                 break;
  66                 dir = &ctx->dx_dir_info[i];
  67                 if (dir->ino != ino)
  68                         for (j = ctx->dx_dir_info_count++; j > i; j--)
  69                                 ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
  70         } else
  71                 dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
  72
  73         dir->ino = ino;
  74         dir->numblocks = num_blocks;
  75         dir->hashversion = 0;
  76         dir->casefolded_hash = inode->i_flags & EXT4_CASEFOLD_FL;
  77         dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
  78                                        * sizeof (struct dx_dirblock_info),
  79                                        "dx_block info array");
  80
  81 }
  82
  83 /*
  84  * get_dx_dir_info() --- given an inode number, try to find the directory
  85  * information entry for it.
  86  */
  87 struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
  88 {
  89         ext2_ino_t low, high, mid;
  90
  91         low = 0;
  92         high = ctx->dx_dir_info_count-1;
  93         if (!ctx->dx_dir_info)
  94                 return 0;
  95         if (ino == ctx->dx_dir_info[low].ino)
  96                 return &ctx->dx_dir_info[low];
  97         if  (ino == ctx->dx_dir_info[high].ino)
  98                 return &ctx->dx_dir_info[high];
  99
 100         while (low < high) {
 101                 /* sum may overflow, but result will fit into mid again */
 102                 mid = (unsigned long long)(low + high) / 2;
 103                 if (mid == low || mid == high)
 104                         break;
 105                 if (ino == ctx->dx_dir_info[mid].ino)
 106                         return &ctx->dx_dir_info[mid];
 107                 if (ino < ctx->dx_dir_info[mid].ino)
 108                         high = mid;
 109                 else
 110                         low = mid;
 111         }
 112         return 0;
 113 }
 114
 115 /*
 116  * Free the dx_dir_info structure when it isn't needed any more.
 117  */
 118 void e2fsck_free_dx_dir_info(e2fsck_t ctx)
 119 {
 120         struct dx_dir_info *dir;
 121         ext2_ino_t i;
 122
 123         if (ctx->dx_dir_info) {
 124                 dir = ctx->dx_dir_info;
 125                 for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
 126                         if (dir->dx_block) {
 127                                 ext2fs_free_mem(&dir->dx_block);
 128                                 dir->dx_block = 0;
 129                         }
 130                 }
 131                 ext2fs_free_mem(&ctx->dx_dir_info);
 132                 ctx->dx_dir_info = 0;
 133         }
 134         ctx->dx_dir_info_size = 0;
 135         ctx->dx_dir_info_count = 0;
 136 }
 137
 138 /*
 139  * Return the count of number of directories in the dx_dir_info structure
 140  */
 141 ext2_ino_t e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
 142 {
 143         return ctx->dx_dir_info_count;
 144 }
 145
 146 /*
 147  * A simple interator function
 148  */
 149 struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, ext2_ino_t *control)
 150 {
 151         if (*control >= ctx->dx_dir_info_count)
 152                 return 0;
 153
 154         return ctx->dx_dir_info + (*control)++;
 155 }