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 __u64 old_loc, new_loc; 23 __u64 size; 24 }; 25 26 struct _ext2_extent { 27 struct ext2_extent_entry *list; 28 __u64 cursor; 29 __u64 size; 30 __u64 num; 31 __u64 sorted; 32 }; 33 34 /* 35 * Create an extent table 36 */ 37 errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, __u64 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, __u64 old_loc, __u64 new_loc) 81 { 82 struct ext2_extent_entry *ent; 83 errcode_t retval; 84 __u64 newsize; 85 __u64 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 __u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc) 143 { 144 __s64 low, high, mid; 145 __u64 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 + ((__u64) (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 __u64 i; 199 struct ext2_extent_entry *ent; 200 201 fputs(_("# Extent dump:\n"), out); 202 fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\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 %llu -> %llu (%llu)\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, __u64 *old_loc, 214 __u64 *new_loc, __u64 *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 241
