resize/extent.c

   1 /*
   2  * extent.c --- ext2 extent abstraction
   3  *
   4  * This abstraction is used to provide a compact way of representing a
   5  * translation table, for moving multiple contiguous ranges (extents)
   6  * of blocks or inodes.
   7  *
   8  * Copyright (C) 1997 Theodore Ts'o
   9  *
  10  * %Begin-Header%
  11  * All rights reserved.
  12  * %End-Header%
  13  */
  14
  15 #include "resize2fs.h"
  16
  17 struct ext2_extent_entry {
  18         __u32   old, new;
  19         int     size;
  20 };
  21
  22 struct _ext2_extent {
  23         struct ext2_extent_entry *list;
  24         int     cursor;
  25         int     size;
  26         int     num;
  27         int     sorted;
  28 };
  29
  30 /*
  31  * Create an extent table
  32  */
  33 errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, int size)
  34 {
  35         ext2_extent     new;
  36
  37         new = malloc(sizeof(struct _ext2_extent));
  38         if (!new)
  39                 return ENOMEM;
  40         memset(new, 0, sizeof(struct _ext2_extent));
  41
  42         new->size = size ? size : 50;
  43         new->cursor = 0;
  44         new->num = 0;
  45         new->sorted = 1;
  46
  47         new->list = malloc(sizeof(struct ext2_extent_entry) * new->size);
  48         if (!new->list) {
  49                 free(new);
  50                 return ENOMEM;
  51         }
  52         memset(new->list, 0, sizeof(struct ext2_extent_entry) * new->size);
  53         *ret_extent = new;
  54         return 0;
  55 }
  56
  57 /*
  58  * Free an extent table
  59  */
  60 void ext2fs_free_extent_table(ext2_extent extent)
  61 {
  62         if (extent->list)
  63                 free(extent->list);
  64         extent->list = 0;
  65         extent->size = 0;
  66         extent->num = 0;
  67         free(extent);
  68 }
  69
  70 /*
  71  * Add an entry to the extent table
  72  */
  73 errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u32 old, __u32 new)
  74 {
  75         struct ext2_extent_entry *p;
  76         int     newsize;
  77         int     curr;
  78         struct  ext2_extent_entry *ent;
  79
  80         if (extent->num >= extent->size) {
  81                 newsize = extent->size + 100;
  82                 p = realloc(extent->list,
  83                             sizeof(struct ext2_extent_entry) * newsize);
  84                 if (!p)
  85                         return ENOMEM;
  86                 extent->list = p;
  87                 extent->size = newsize;
  88         }
  89         curr = extent->num;
  90         ent = extent->list + curr;
  91         if (curr) {
  92                 /*
  93                  * Check to see if this can be coalesced with the last
  94                  * extent
  95                  */
  96                 ent--;
  97                 if ((ent->old + ent->size == old) &&
  98                     (ent->new + ent->size == new)) {
  99                         ent->size++;
 100                         return 0;
 101                 }
 102                 /*
 103                  * Now see if we're going to ruin the sorting
 104                  */
 105                 if (ent->old + ent->size > old)
 106                         extent->sorted = 0;
 107                 ent++;
 108         }
 109         ent->old = old;
 110         ent->new = new;
 111         ent->size = 1;
 112         extent->num++;
 113         return 0;
 114 }
 115
 116 /*
 117  * Helper function for qsort
 118  */
 119 static int extent_cmp(const void *a, const void *b)
 120 {
 121         const struct ext2_extent_entry *db_a = a;
 122         const struct ext2_extent_entry *db_b = b;
 123
 124         return (db_a->old - db_b->old);
 125 }
 126
 127 /*
 128  * Given an inode map and inode number, look up the old inode number
 129  * and return the new inode number
 130  */
 131 __u32 ext2fs_extent_translate(ext2_extent extent, __u32 old)
 132 {
 133         int     low, high, mid;
 134         ino_t   lowval, highval;
 135         float   range;
 136
 137         if (!extent->sorted) {
 138                 qsort(extent->list, extent->num,
 139                       sizeof(struct ext2_extent_entry), extent_cmp);
 140                 extent->sorted = 1;
 141         }
 142         low = 0;
 143         high = extent->num-1;
 144         while (low <= high) {
 145 #if 0
 146                 mid = (low+high)/2;
 147 #else
 148                 if (low == high)
 149                         mid = low;
 150                 else {
 151                         /* Interpolate for efficiency */
 152                         lowval = extent->list[low].old;
 153                         highval = extent->list[high].old;
 154
 155                         if (old < lowval)
 156                                 range = 0;
 157                         else if (old > highval)
 158                                 range = 1;
 159                         else
 160                                 range = ((float) (old - lowval)) /
 161                                         (highval - lowval);
 162                         mid = low + ((int) (range * (high-low)));
 163                 }
 164 #endif
 165                 if ((old >= extent->list[mid].old) &&
 166                     (old < extent->list[mid].old + extent->list[mid].size))
 167                         return (extent->list[mid].new +
 168                                 (old - extent->list[mid].old));
 169                 if (old < extent->list[mid].old)
 170                         high = mid-1;
 171                 else
 172                         low = mid+1;
 173         }
 174         return 0;
 175 }
 176
 177 /*
 178  * For debugging only
 179  */
 180 void ext2fs_extent_dump(ext2_extent extent, FILE *out)
 181 {
 182         int     i;
 183         struct ext2_extent_entry *ent;
 184
 185         fputs("# Extent dump:\n", out);
 186         fprintf(out, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n",
 187                extent->num, extent->size, extent->cursor, extent->sorted);
 188         for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
 189                 fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old,
 190                         ent->new, ent->size);
 191         }
 192 }
 193
 194 /*
 195  * Iterate over the contents of the extent table
 196  */
 197 errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old,
 198                                 __u32 *new, int *size)
 199 {
 200         struct ext2_extent_entry *ent;
 201
 202         if (!old) {
 203                 extent->cursor = 0;
 204                 return 0;
 205         }
 206
 207         if (extent->cursor >= extent->num) {
 208                 *old = 0;
 209                 *new = 0;
 210                 *size = 0;
 211                 return 0;
 212         }
 213
 214         ent = extent->list + extent->cursor++;
 215
 216         *old = ent->old;
 217         *new = ent->new;
 218         *size = ent->size;
 219         return 0;
 220 }
 221
 222
 223
 224