e2fsck/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 #undef DIRINFO_DEBUG
   9
  10 #include "e2fsck.h"
  11 struct dir_info_db {
  12         int             count;
  13         int             size;
  14         struct dir_info *array;
  15         struct dir_info *last_lookup;
  16 };
  17
  18 struct dir_info_iter {
  19         int     i;
  20 };
  21
  22 static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir);
  23
  24 void setup_db(e2fsck_t ctx)
  25 {
  26         struct dir_info_db      *db;
  27         ext2_ino_t              num_dirs;
  28         errcode_t               retval;
  29
  30         db = (struct dir_info_db *)
  31                 e2fsck_allocate_memory(ctx, sizeof(struct dir_info_db),
  32                                        "directory map db");
  33         db->count = db->size = 0;
  34         db->array = 0;
  35
  36         retval = ext2fs_get_num_dirs(ctx->fs, &num_dirs);
  37         if (retval)
  38                 num_dirs = 1024;        /* Guess */
  39         db->size = num_dirs + 10;
  40         db->array  = (struct dir_info *)
  41                 e2fsck_allocate_memory(ctx, db->size
  42                                        * sizeof (struct dir_info),
  43                                        "directory map");
  44
  45         ctx->dir_info = db;
  46 }
  47
  48 /*
  49  * This subroutine is called during pass1 to create a directory info
  50  * entry.  During pass1, the passed-in parent is 0; it will get filled
  51  * in during pass2.
  52  */
  53 void e2fsck_add_dir_info(e2fsck_t ctx, ext2_ino_t ino, ext2_ino_t parent)
  54 {
  55         struct dir_info_db      *db;
  56         struct dir_info         *dir, ent;
  57         int                     i, j;
  58         errcode_t               retval;
  59         unsigned long           old_size;
  60
  61 #ifdef DIRINFO_DEBUG
  62         printf("add_dir_info for inode (%lu, %lu)...\n", ino, parent);
  63 #endif
  64         if (!ctx->dir_info)
  65                 setup_db(ctx);
  66         db = ctx->dir_info;
  67
  68         if (ctx->dir_info->count >= ctx->dir_info->size) {
  69                 old_size = ctx->dir_info->size * sizeof(struct dir_info);
  70                 ctx->dir_info->size += 10;
  71                 retval = ext2fs_resize_mem(old_size, ctx->dir_info->size *
  72                                            sizeof(struct dir_info),
  73                                            &ctx->dir_info);
  74                 if (retval) {
  75                         ctx->dir_info->size -= 10;
  76                         return;
  77                 }
  78         }
  79
  80         ent.ino = ino;
  81         ent.parent = parent;
  82         ent.dotdot = parent;
  83
  84         e2fsck_put_dir_info(ctx, &ent);
  85
  86         /*
  87          * Normally, add_dir_info is called with each inode in
  88          * sequential order; but once in a while (like when pass 3
  89          * needs to recreate the root directory or lost+found
  90          * directory) it is called out of order.  In those cases, we
  91          * need to move the dir_info entries down to make room, since
  92          * the dir_info array needs to be sorted by inode number for
  93          * get_dir_info()'s sake.
  94          */
  95         if (ctx->dir_info->count &&
  96             ctx->dir_info->array[ctx->dir_info->count-1].ino >= ino) {
  97                 for (i = ctx->dir_info->count-1; i > 0; i--)
  98                         if (ctx->dir_info->array[i-1].ino < ino)
  99                                 break;
 100                 dir = &ctx->dir_info->array[i];
 101                 if (dir->ino != ino)
 102                         for (j = ctx->dir_info->count++; j > i; j--)
 103                                 ctx->dir_info->array[j] = ctx->dir_info->array[j-1];
 104         } else
 105                 dir = &ctx->dir_info->array[ctx->dir_info->count++];
 106
 107         dir->ino = ino;
 108         dir->dotdot = parent;
 109         dir->parent = parent;
 110 }
 111
 112 /*
 113  * get_dir_info() --- given an inode number, try to find the directory
 114  * information entry for it.
 115  */
 116 static struct dir_info *e2fsck_get_dir_info(e2fsck_t ctx, ext2_ino_t ino)
 117 {
 118         struct dir_info_db      *db = ctx->dir_info;
 119         int                     low, high, mid, ret;
 120
 121         if (!db)
 122                 return 0;
 123
 124 #ifdef DIRINFO_DEBUG
 125         printf("e2fsck_get_dir_info %d...", ino);
 126 #endif
 127
 128         if (db->last_lookup && db->last_lookup->ino == ino)
 129                 return db->last_lookup;
 130
 131         low = 0;
 132         high = ctx->dir_info->count-1;
 133         if (ino == ctx->dir_info->array[low].ino) {
 134 #ifdef DIRINFO_DEBUG
 135                 printf("(%d,%d,%d)\n", ino,
 136                        ctx->dir_info->array[low].dotdot,
 137                        ctx->dir_info->array[low].parent);
 138 #endif
 139                 return &ctx->dir_info->array[low];
 140         }
 141         if (ino == ctx->dir_info->array[high].ino) {
 142 #ifdef DIRINFO_DEBUG
 143                 printf("(%d,%d,%d)\n", ino,
 144                        ctx->dir_info->array[high].dotdot,
 145                        ctx->dir_info->array[high].parent);
 146 #endif
 147                 return &ctx->dir_info->array[high];
 148         }
 149
 150         while (low < high) {
 151                 mid = (low+high)/2;
 152                 if (mid == low || mid == high)
 153                         break;
 154                 if (ino == ctx->dir_info->array[mid].ino) {
 155 #ifdef DIRINFO_DEBUG
 156                         printf("(%d,%d,%d)\n", ino,
 157                                ctx->dir_info->array[mid].dotdot,
 158                                ctx->dir_info->array[mid].parent);
 159 #endif
 160                         return &ctx->dir_info->array[mid];
 161                 }
 162                 if (ino < ctx->dir_info->array[mid].ino)
 163                         high = mid;
 164                 else
 165                         low = mid;
 166         }
 167         return 0;
 168 }
 169
 170 static void e2fsck_put_dir_info(e2fsck_t ctx, struct dir_info *dir)
 171 {
 172 #ifdef DIRINFO_DEBUG
 173         printf("e2fsck_put_dir_info (%d, %d, %d)...", dir->ino, dir->dotdot,
 174                dir->parent);
 175 #endif
 176         return;
 177 }
 178
 179 /*
 180  * Free the dir_info structure when it isn't needed any more.
 181  */
 182 void e2fsck_free_dir_info(e2fsck_t ctx)
 183 {
 184         if (ctx->dir_info) {
 185                 ctx->dir_info->size = 0;
 186                 ctx->dir_info->count = 0;
 187                 ext2fs_free_mem(&ctx->dir_info);
 188                 ctx->dir_info = 0;
 189         }
 190 }
 191
 192 /*
 193  * Return the count of number of directories in the dir_info structure
 194  */
 195 int e2fsck_get_num_dirinfo(e2fsck_t ctx)
 196 {
 197         return ctx->dir_info ? ctx->dir_info->count : 0;
 198 }
 199
 200 extern struct dir_info_iter *e2fsck_dir_info_iter_begin(e2fsck_t ctx)
 201 {
 202         struct dir_info_iter *iter;
 203         struct dir_info_db *db = ctx->dir_info;
 204         int ret;
 205
 206         iter = e2fsck_allocate_memory(ctx, sizeof(struct dir_info_iter),
 207                                       "dir_info iterator");
 208         memset(iter, 0, sizeof(iter));
 209         return iter;
 210 }
 211
 212 extern void e2fsck_dir_info_iter_end(e2fsck_t ctx,
 213                                      struct dir_info_iter *iter)
 214 {
 215         ext2fs_free_mem(&iter);
 216 }
 217
 218 /*
 219  * A simple interator function
 220  */
 221 struct dir_info *e2fsck_dir_info_iter(e2fsck_t ctx, struct dir_info_iter *iter)
 222 {
 223         if (!ctx->dir_info || !iter ||
 224             (iter->i >= ctx->dir_info->count))
 225                 return 0;
 226
 227 #ifdef DIRINFO_DEBUG
 228         printf("iter(%d, %d, %d)...", ctx->dir_info->array[iter->i].ino,
 229                ctx->dir_info->array[iter->i].dotdot,
 230                ctx->dir_info->array[iter->i].parent);
 231 #endif
 232         return(ctx->dir_info->array + iter->i++);
 233 }
 234
 235 /*
 236  * This function only sets the parent pointer, and requires that
 237  * dirinfo structure has already been created.
 238  */
 239 int e2fsck_dir_info_set_parent(e2fsck_t ctx, ext2_ino_t ino,
 240                                ext2_ino_t parent)
 241 {
 242         struct dir_info *p;
 243
 244         p = e2fsck_get_dir_info(ctx, ino);
 245         if (!p)
 246                 return 1;
 247         p->parent = parent;
 248         e2fsck_put_dir_info(ctx, p);
 249         return 0;
 250 }
 251
 252 /*
 253  * This function only sets the dot dot pointer, and requires that
 254  * dirinfo structure has already been created.
 255  */
 256 int e2fsck_dir_info_set_dotdot(e2fsck_t ctx, ext2_ino_t ino,
 257                                ext2_ino_t dotdot)
 258 {
 259         struct dir_info *p;
 260
 261         p = e2fsck_get_dir_info(ctx, ino);
 262         if (!p)
 263                 return 1;
 264         p->dotdot = dotdot;
 265         e2fsck_put_dir_info(ctx, p);
 266         return 0;
 267 }
 268
 269 /*
 270  * This function only sets the parent pointer, and requires that
 271  * dirinfo structure has already been created.
 272  */
 273 int e2fsck_dir_info_get_parent(e2fsck_t ctx, ext2_ino_t ino,
 274                                ext2_ino_t *parent)
 275 {
 276         struct dir_info *p;
 277
 278         p = e2fsck_get_dir_info(ctx, ino);
 279         if (!p)
 280                 return 1;
 281         *parent = p->parent;
 282         return 0;
 283 }
 284
 285 /*
 286  * This function only sets the dot dot pointer, and requires that
 287  * dirinfo structure has already been created.
 288  */
 289 int e2fsck_dir_info_get_dotdot(e2fsck_t ctx, ext2_ino_t ino,
 290                                ext2_ino_t *dotdot)
 291 {
 292         struct dir_info *p;
 293
 294         p = e2fsck_get_dir_info(ctx, ino);
 295         if (!p)
 296                 return 1;
 297         *dotdot = p->dotdot;
 298         return 0;
 299 }
 300