resize/inodemap.c

   1 /*
   2  * inodemap.c --- ext2resizer indoe mapper
   3  *
   4  * Copyright (C) 1997 Theodore Ts'o
   5  *
   6  * %Begin-Header%
   7  * All rights reserved.
   8  * %End-Header%
   9  */
  10
  11 #include "resize2fs.h"
  12
  13 struct inode_map_entry {
  14         ino_t   old, new;
  15 };
  16
  17 struct inode_map_struct {
  18         struct inode_map_entry *list;
  19         int     size;
  20         int     num;
  21         int     sorted;
  22 };
  23
  24 typedef struct inode_map_struct *inode_map;
  25
  26 /*
  27  * Create inode map table
  28  */
  29 static errcode_t create_inode_map(inode_map *imap, int size)
  30 {
  31         inode_map       new;
  32
  33         new = malloc(sizeof(struct inode_map_struct));
  34         if (!new)
  35                 return ENOMEM;
  36         memset(new, 0, sizeof(struct inode_map_struct));
  37
  38         new->size = size ? size : 50;
  39         new->num = 0;
  40         new->sorted = 1;
  41
  42         new->list = malloc(sizeof(struct inode_map_struct) * new->size);
  43         if (!new->list) {
  44                 free(new);
  45                 return ENOMEM;
  46         }
  47         *imap = new;
  48         return 0;
  49 }
  50
  51 /*
  52  * Add an entry to the inode table map
  53  */
  54 static errcode_t add_inode_map_entry(inode_map imap, ino_t old, ino_t new)
  55 {
  56         struct inode_map_entry *p;
  57         int     newsize;
  58
  59         if (imap->num >= imap->size) {
  60                 newsize = imap->size + 100;
  61                 p = realloc(imap->list,
  62                             sizeof(struct inode_map_struct) * newsize);
  63                 if (!p)
  64                         return ENOMEM;
  65                 imap->list = p;
  66                 imap->size = newsize;
  67         }
  68         if (imap->num) {
  69                 if (imap->list[imap->num-1].old > old)
  70                         imap->sorted = 0;
  71         }
  72         imap->list[imap->num].old = old;
  73         imap->list[imap->num].new = new;
  74         imap->num++;
  75         return 0;
  76 }
  77
  78 /*
  79  * Helper function for qsort
  80  */
  81 static int inode_map_cmp(const void *a, const void *b)
  82 {
  83         const struct inode_map_entry *db_a =
  84                 (const struct inode_map_entry *) a;
  85         const struct inode_map_entry *db_b =
  86                 (const struct inode_map_entry *) b;
  87
  88         return (db_a->old - db_b->old);
  89 }
  90
  91 /*
  92  * Given an inode map and inode number, look up the old inode number
  93  * and return the new inode number
  94  */
  95 static ino_t inode_map_translate(inode_map imap, ino_t old)
  96 {
  97         int     low, high, mid;
  98         ino_t   lowval, highval;
  99         float   range;
 100
 101         if (!imap->sorted) {
 102                 qsort(imap->list, imap->num,
 103                       sizeof(struct inode_map_entry), inode_map_cmp);
 104                 imap->sorted = 1;
 105         }
 106         low = 0;
 107         high = imap->num-1;
 108         while (low <= high) {
 109 #if 0
 110                 mid = (low+high)/2;
 111 #else
 112                 if (low == high)
 113                         mid = low;
 114                 else {
 115                         /* Interpolate for efficiency */
 116                         lowval = imap->list[low].old;
 117                         highval = imap->list[high].old;
 118
 119                         if (old < lowval)
 120                                 range = 0;
 121                         else if (old > highval)
 122                                 range = 1;
 123                         else
 124                                 range = ((float) (old - lowval)) /
 125                                         (highval - lowval);
 126                         mid = low + ((int) (range * (high-low)));
 127                 }
 128 #endif
 129                 if (old == imap->list[mid].old)
 130                         return imap->list[mid].new;
 131                 if (old < imap->list[mid].old)
 132                         high = mid-1;
 133                 else
 134                         low = mid+1;
 135         }
 136         return 0;
 137 }
 138
 139 struct istruct {
 140         inode_map       imap;
 141         int             flags;
 142 };
 143
 144 int check_and_change_inodes(ino_t dir, int entry,
 145                             struct ext2_dir_entry *dirent, int offset,
 146                             int blocksize, char *buf, void *private)
 147 {
 148         struct istruct *is = private;
 149         ino_t   new;
 150
 151         if (!dirent->inode)
 152                 return 0;
 153
 154         new = inode_map_translate(is->imap, dirent->inode);
 155
 156         if (!new)
 157                 return 0;
 158         if (is->flags & RESIZE_DEBUG_INODEMAP)
 159                 printf("Inode translate (dir=%ld, name=%.*s, %ld->%ld)\n",
 160                        dir, dirent->name_len, dirent->name,
 161                        dirent->inode, new);
 162
 163         dirent->inode = new;
 164
 165         return DIRENT_CHANGED;
 166 }
 167
 168 errcode_t ext2fs_inode_move(ext2_resize_t rfs)
 169 {
 170         ino_t                   ino, start, end, new;
 171         struct ext2_inode       inode;
 172         ext2_inode_scan         scan;
 173         inode_map               imap;
 174         errcode_t               retval;
 175         int                     group;
 176         struct istruct          is;
 177
 178         if (rfs->old_fs->group_desc_count <=
 179             rfs->new_fs->group_desc_count)
 180                 return 0;
 181
 182         retval = create_inode_map(&imap, 0);
 183         if (retval)
 184                 return retval;
 185
 186         retval = ext2fs_open_inode_scan(rfs->old_fs, 0, &scan);
 187         if (retval)
 188                 return retval;
 189
 190         retval = ext2fs_inode_scan_goto_blockgroup(scan,
 191                                    rfs->new_fs->group_desc_count);
 192         if (retval) {
 193                 ext2fs_close_inode_scan(scan);
 194                 return retval;
 195         }
 196
 197         new = EXT2_FIRST_INODE(rfs->new_fs->super);
 198
 199         /*
 200          * First, copy all of the inodes that need to be moved
 201          * elsewhere in the inode table
 202          */
 203         while (1) {
 204                 retval = ext2fs_get_next_inode(scan, &ino, &inode);
 205                 if (retval)
 206                         return retval;
 207                 if (!ino)
 208                         break;
 209
 210                 if (!ext2fs_test_inode_bitmap(rfs->old_fs->inode_map, ino))
 211                         continue;
 212
 213                 /*
 214                  * Find a new inode
 215                  */
 216                 while (1) {
 217                         if (!ext2fs_test_inode_bitmap(rfs->new_fs->inode_map,
 218                                                       new))
 219                                 break;
 220                         new++;
 221                         if (new > rfs->new_fs->super->s_inodes_count)
 222                                 return ENOSPC;
 223                 }
 224                 ext2fs_mark_inode_bitmap(rfs->new_fs->inode_map, new);
 225                 retval = ext2fs_write_inode(rfs->old_fs, new, &inode);
 226                 if (retval)
 227                         return retval;
 228                 group = (new-1) / EXT2_INODES_PER_GROUP(rfs->new_fs->super);
 229                 if (LINUX_S_ISDIR(inode.i_mode))
 230                         rfs->new_fs->group_desc[group].bg_used_dirs_count++;
 231
 232                 if (rfs->flags & RESIZE_DEBUG_INODEMAP)
 233                         printf("Inode moved %ld->%ld\n", ino, new);
 234
 235                 add_inode_map_entry(imap, ino, new);
 236         }
 237         /*
 238          * Now, we iterate over all of the directories to update the
 239          * inode references
 240          */
 241         is.imap = imap;
 242         is.flags = rfs->flags;
 243         retval = ext2fs_dblist_dir_iterate(rfs->old_fs->dblist, 0, 0,
 244                                            check_and_change_inodes, &is);
 245         if (retval)
 246                 return retval;
 247
 248         return 0;
 249 }
 250