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