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