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_loc, new_loc;
  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     extent;
  36         errcode_t       retval;
  37
  38         retval = ext2fs_get_mem(sizeof(struct _ext2_extent),
  39                                 (void **) &extent);
  40         if (retval)
  41                 return retval;
  42         memset(extent, 0, sizeof(struct _ext2_extent));
  43
  44         extent->size = size ? size : 50;
  45         extent->cursor = 0;
  46         extent->num = 0;
  47         extent->sorted = 1;
  48
  49         retval = ext2fs_get_mem(sizeof(struct ext2_extent_entry) *
  50                                 extent->size, (void **) &extent->list);
  51         if (retval) {
  52                 ext2fs_free_mem((void **) &extent);
  53                 return retval;
  54         }
  55         memset(extent->list, 0,
  56                sizeof(struct ext2_extent_entry) * extent->size);
  57         *ret_extent = extent;
  58         return 0;
  59 }
  60
  61 /*
  62  * Free an extent table
  63  */
  64 void ext2fs_free_extent_table(ext2_extent extent)
  65 {
  66         if (extent->list)
  67                 ext2fs_free_mem((void **) &extent->list);
  68         extent->list = 0;
  69         extent->size = 0;
  70         extent->num = 0;
  71         ext2fs_free_mem((void **) &extent);
  72 }
  73
  74 /*
  75  * Add an entry to the extent table
  76  */
  77 errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u32 old_loc, __u32 new_loc)
  78 {
  79         struct  ext2_extent_entry       *ent;
  80         errcode_t                       retval;
  81         int                             newsize;
  82         int                             curr;
  83
  84         if (extent->num >= extent->size) {
  85                 newsize = extent->size + 100;
  86                 retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) *
  87                                            extent->size,
  88                                            sizeof(struct ext2_extent_entry) *
  89                                            newsize, (void **) &extent->list);
  90                 if (retval)
  91                         return retval;
  92                 extent->size = newsize;
  93         }
  94         curr = extent->num;
  95         ent = extent->list + curr;
  96         if (curr) {
  97                 /*
  98                  * Check to see if this can be coalesced with the last
  99                  * extent
 100                  */
 101                 ent--;
 102                 if ((ent->old_loc + ent->size == old_loc) &&
 103                     (ent->new_loc + ent->size == new_loc)) {
 104                         ent->size++;
 105                         return 0;
 106                 }
 107                 /*
 108                  * Now see if we're going to ruin the sorting
 109                  */
 110                 if (ent->old_loc + ent->size > old_loc)
 111                         extent->sorted = 0;
 112                 ent++;
 113         }
 114         ent->old_loc = old_loc;
 115         ent->new_loc = new_loc;
 116         ent->size = 1;
 117         extent->num++;
 118         return 0;
 119 }
 120
 121 /*
 122  * Helper function for qsort
 123  */
 124 static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b)
 125 {
 126         const struct ext2_extent_entry *db_a;
 127         const struct ext2_extent_entry *db_b;
 128
 129         db_a = (const struct ext2_extent_entry *) a;
 130         db_b = (const struct ext2_extent_entry *) b;
 131
 132         return (db_a->old_loc - db_b->old_loc);
 133 }
 134
 135 /*
 136  * Given an inode map and inode number, look up the old inode number
 137  * and return the new inode number.
 138  */
 139 __u32 ext2fs_extent_translate(ext2_extent extent, __u32 old_loc)
 140 {
 141         int     low, high, mid;
 142         ino_t   lowval, highval;
 143         float   range;
 144
 145         if (!extent->sorted) {
 146                 qsort(extent->list, extent->num,
 147                       sizeof(struct ext2_extent_entry), extent_cmp);
 148                 extent->sorted = 1;
 149         }
 150         low = 0;
 151         high = extent->num-1;
 152         while (low <= high) {
 153 #if 0
 154                 mid = (low+high)/2;
 155 #else
 156                 if (low == high)
 157                         mid = low;
 158                 else {
 159                         /* Interpolate for efficiency */
 160                         lowval = extent->list[low].old_loc;
 161                         highval = extent->list[high].old_loc;
 162
 163                         if (old_loc < lowval)
 164                                 range = 0;
 165                         else if (old_loc > highval)
 166                                 range = 1;
 167                         else
 168                                 range = ((float) (old_loc - lowval)) /
 169                                         (highval - lowval);
 170                         mid = low + ((int) (range * (high-low)));
 171                 }
 172 #endif
 173                 if ((old_loc >= extent->list[mid].old_loc) &&
 174                     (old_loc < extent->list[mid].old_loc + extent->list[mid].size))
 175                         return (extent->list[mid].new_loc +
 176                                 (old_loc - extent->list[mid].old_loc));
 177                 if (old_loc < extent->list[mid].old_loc)
 178                         high = mid-1;
 179                 else
 180                         low = mid+1;
 181         }
 182         return 0;
 183 }
 184
 185 /*
 186  * For debugging only
 187  */
 188 void ext2fs_extent_dump(ext2_extent extent, FILE *out)
 189 {
 190         int     i;
 191         struct ext2_extent_entry *ent;
 192
 193         fputs("# Extent dump:\n", out);
 194         fprintf(out, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n",
 195                extent->num, extent->size, extent->cursor, extent->sorted);
 196         for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
 197                 fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old_loc,
 198                         ent->new_loc, ent->size);
 199         }
 200 }
 201
 202 /*
 203  * Iterate over the contents of the extent table
 204  */
 205 errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old_loc,
 206                                 __u32 *new_loc, int *size)
 207 {
 208         struct ext2_extent_entry *ent;
 209
 210         if (!old_loc) {
 211                 extent->cursor = 0;
 212                 return 0;
 213         }
 214
 215         if (extent->cursor >= extent->num) {
 216                 *old_loc = 0;
 217                 *new_loc = 0;
 218                 *size = 0;
 219                 return 0;
 220         }
 221
 222         ent = extent->list + extent->cursor++;
 223
 224         *old_loc = ent->old_loc;
 225         *new_loc = ent->new_loc;
 226         *size = ent->size;
 227         return 0;
 228 }
 229
 230
 231
 232