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