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 <assert.h>
   9 #include "config.h"
  10 #include "e2fsck.h"
  11
  12 /*
  13  * This subroutine is called during pass1 to create a directory info
  14  * entry.  During pass1, the passed-in parent is 0; it will get filled
  15  * in during pass2.
  16  */
  17 void e2fsck_add_dx_dir(e2fsck_t ctx, ext2_ino_t ino, struct ext2_inode *inode,
  18                        int num_blocks)
  19 {
  20         struct dx_dir_info *dir;
  21         ext2_ino_t      i, j;
  22         errcode_t       retval;
  23         unsigned long   old_size;
  24
  25 #if 0
  26         printf("add_dx_dir_info for inode %lu...\n", ino);
  27 #endif
  28         if (!ctx->dx_dir_info) {
  29                 ctx->dx_dir_info_count = 0;
  30                 ctx->dx_dir_info_size = 100; /* Guess */
  31                 ctx->dx_dir_info  = (struct dx_dir_info *)
  32                         e2fsck_allocate_memory(ctx, ctx->dx_dir_info_size
  33                                                * sizeof (struct dx_dir_info),
  34                                                "directory map");
  35         }
  36
  37         if (ctx->dx_dir_info_count >= ctx->dx_dir_info_size) {
  38                 old_size = ctx->dx_dir_info_size * sizeof(struct dx_dir_info);
  39                 ctx->dx_dir_info_size += 10;
  40                 retval = ext2fs_resize_mem(old_size, ctx->dx_dir_info_size *
  41                                            sizeof(struct dx_dir_info),
  42                                            &ctx->dx_dir_info);
  43                 if (retval) {
  44                         fprintf(stderr, "Couldn't reallocate dx_dir_info "
  45                                 "structure to %u entries\n",
  46                                 ctx->dx_dir_info_size);
  47                         fatal_error(ctx, 0);
  48                         ctx->dx_dir_info_size -= 10;
  49                         return;
  50                 }
  51         }
  52
  53         /*
  54          * Normally, add_dx_dir_info is called with each inode in
  55          * sequential order; but once in a while (like when pass 3
  56          * needs to recreate the root directory or lost+found
  57          * directory) it is called out of order.  In those cases, we
  58          * need to move the dx_dir_info entries down to make room, since
  59          * the dx_dir_info array needs to be sorted by inode number for
  60          * get_dx_dir_info()'s sake.
  61          */
  62         if (ctx->dx_dir_info_count &&
  63             ctx->dx_dir_info[ctx->dx_dir_info_count-1].ino >= ino) {
  64                 for (i = ctx->dx_dir_info_count-1; i > 0; i--)
  65                         if (ctx->dx_dir_info[i-1].ino < ino)
  66                                 break;
  67                 dir = &ctx->dx_dir_info[i];
  68                 if (dir->ino != ino)
  69                         for (j = ctx->dx_dir_info_count++; j > i; j--)
  70                                 ctx->dx_dir_info[j] = ctx->dx_dir_info[j-1];
  71         } else
  72                 dir = &ctx->dx_dir_info[ctx->dx_dir_info_count++];
  73
  74         dir->ino = ino;
  75         dir->numblocks = num_blocks;
  76         dir->hashversion = 0;
  77         dir->casefolded_hash = !!(inode->i_flags & EXT4_CASEFOLD_FL);
  78         dir->dx_block = e2fsck_allocate_memory(ctx, num_blocks
  79                                        * sizeof (struct dx_dirblock_info),
  80                                        "dx_block info array");
  81 }
  82
  83 /*
  84  * Merge two sorted dir info to @dest
  85  */
  86 void e2fsck_merge_dx_dir(e2fsck_t global_ctx, e2fsck_t thread_ctx)
  87 {
  88         struct dx_dir_info *src_array = thread_ctx->dx_dir_info;
  89         struct dx_dir_info *dest_array = global_ctx->dx_dir_info;
  90         size_t size_dx_info = sizeof(struct dx_dir_info);
  91         ext2_ino_t size = global_ctx->dx_dir_info_size;
  92         ext2_ino_t src_count = thread_ctx->dx_dir_info_count;
  93         ext2_ino_t dest_count = global_ctx->dx_dir_info_count;
  94         ext2_ino_t total_count = src_count + dest_count;
  95         struct dx_dir_info *array;
  96         struct dx_dir_info *array_ptr;
  97         ext2_ino_t src_index = 0, dest_index = 0;
  98
  99         if (thread_ctx->dx_dir_info_count == 0)
 100                 return;
 101
 102         if (size < total_count)
 103                 size = total_count;
 104
 105         array = e2fsck_allocate_memory(global_ctx, size * size_dx_info,
 106                                        "directory map");
 107         array_ptr = array;
 108         /*
 109          * This can be improved by binary search and memcpy, but codes
 110          * would be more complex. And if the groups distributed to each
 111          * thread are strided, this implementation won't be too bad
 112          * comparing to the optimiztion.
 113          */
 114         while (src_index < src_count || dest_index < dest_count) {
 115                 if (src_index >= src_count) {
 116                         memcpy(array_ptr, &dest_array[dest_index],
 117                                (dest_count - dest_index) * size_dx_info);
 118                         break;
 119                 }
 120                 if (dest_index >= dest_count) {
 121                         memcpy(array_ptr, &src_array[src_index],
 122                                (src_count - src_index) * size_dx_info);
 123                         break;
 124                 }
 125                 if (src_array[src_index].ino < dest_array[dest_index].ino) {
 126                         *array_ptr = src_array[src_index];
 127                         src_index++;
 128                 } else {
 129                         assert(src_array[src_index].ino >
 130                                dest_array[dest_index].ino);
 131                         *array_ptr = dest_array[dest_index];
 132                         dest_index++;
 133                 }
 134                 array_ptr++;
 135         }
 136
 137         if (global_ctx->dx_dir_info)
 138                 ext2fs_free_mem(&global_ctx->dx_dir_info);
 139         if (thread_ctx->dx_dir_info)
 140                 ext2fs_free_mem(&thread_ctx->dx_dir_info);
 141         global_ctx->dx_dir_info = array;
 142         global_ctx->dx_dir_info_size = size;
 143         global_ctx->dx_dir_info_count = total_count;
 144 }
 145
 146 /*
 147  * get_dx_dir_info() --- given an inode number, try to find the directory
 148  * information entry for it.
 149  */
 150 struct dx_dir_info *e2fsck_get_dx_dir_info(e2fsck_t ctx, ext2_ino_t ino)
 151 {
 152         ext2_ino_t low, high, mid;
 153
 154         low = 0;
 155         high = ctx->dx_dir_info_count-1;
 156         if (!ctx->dx_dir_info)
 157                 return 0;
 158         if (ino == ctx->dx_dir_info[low].ino)
 159                 return &ctx->dx_dir_info[low];
 160         if  (ino == ctx->dx_dir_info[high].ino)
 161                 return &ctx->dx_dir_info[high];
 162
 163         while (low < high) {
 164                 /* sum may overflow, but result will fit into mid again */
 165                 mid = (unsigned long long)(low + high) / 2;
 166                 if (mid == low || mid == high)
 167                         break;
 168                 if (ino == ctx->dx_dir_info[mid].ino)
 169                         return &ctx->dx_dir_info[mid];
 170                 if (ino < ctx->dx_dir_info[mid].ino)
 171                         high = mid;
 172                 else
 173                         low = mid;
 174         }
 175         return 0;
 176 }
 177
 178 /*
 179  * Free the dx_dir_info structure when it isn't needed any more.
 180  */
 181 void e2fsck_free_dx_dir_info(e2fsck_t ctx)
 182 {
 183         struct dx_dir_info *dir;
 184         ext2_ino_t i;
 185
 186         if (ctx->dx_dir_info) {
 187                 dir = ctx->dx_dir_info;
 188                 for (i=0; i < ctx->dx_dir_info_count; i++,dir++) {
 189                         if (dir->dx_block) {
 190                                 ext2fs_free_mem(&dir->dx_block);
 191                                 dir->dx_block = 0;
 192                         }
 193                 }
 194                 ext2fs_free_mem(&ctx->dx_dir_info);
 195                 ctx->dx_dir_info = 0;
 196         }
 197         ctx->dx_dir_info_size = 0;
 198         ctx->dx_dir_info_count = 0;
 199 }
 200
 201 /*
 202  * Return the count of number of directories in the dx_dir_info structure
 203  */
 204 ext2_ino_t e2fsck_get_num_dx_dirinfo(e2fsck_t ctx)
 205 {
 206         return ctx->dx_dir_info_count;
 207 }
 208
 209 /*
 210  * A simple interator function
 211  */
 212 struct dx_dir_info *e2fsck_dx_dir_info_iter(e2fsck_t ctx, ext2_ino_t *control)
 213 {
 214         if (*control >= ctx->dx_dir_info_count)
 215                 return 0;
 216
 217         return ctx->dx_dir_info + (*control)++;
 218 }