Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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 { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 18 | __u32 old_loc, new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 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)); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 43 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 44 | extent->size = size ? size : 50; |
| 45 | extent->cursor = 0; |
| 46 | extent->num = 0; |
| 47 | extent->sorted = 1; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 48 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 49 | retval = ext2fs_get_mem(sizeof(struct ext2_extent_entry) * |
| 50 | extent->size, (void **) &extent->list); |
| 51 | if (retval) { |
Theodore Ts'o | 4c77fe5 | 1998-04-30 17:35:59 +0000 | [diff] [blame] | 52 | ext2fs_free_mem((void **) &extent); |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 53 | return retval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 54 | } |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 55 | memset(extent->list, 0, |
| 56 | sizeof(struct ext2_extent_entry) * extent->size); |
| 57 | *ret_extent = extent; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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) |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 67 | ext2fs_free_mem((void **) &extent->list); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 68 | extent->list = 0; |
| 69 | extent->size = 0; |
| 70 | extent->num = 0; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 71 | ext2fs_free_mem((void **) &extent); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 72 | } |
| 73 | |
| 74 | /* |
| 75 | * Add an entry to the extent table |
| 76 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 77 | errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u32 old_loc, __u32 new_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 78 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 79 | struct ext2_extent_entry *ent; |
| 80 | errcode_t retval; |
| 81 | int newsize; |
| 82 | int curr; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 83 | |
| 84 | if (extent->num >= extent->size) { |
| 85 | newsize = extent->size + 100; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 86 | retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) * |
Theodore Ts'o | 76f875d | 1998-04-27 01:41:13 +0000 | [diff] [blame] | 87 | extent->size, |
| 88 | sizeof(struct ext2_extent_entry) * |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 89 | newsize, (void **) &extent->list); |
| 90 | if (retval) |
| 91 | return retval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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--; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 102 | if ((ent->old_loc + ent->size == old_loc) && |
| 103 | (ent->new_loc + ent->size == new_loc)) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 104 | ent->size++; |
| 105 | return 0; |
| 106 | } |
| 107 | /* |
| 108 | * Now see if we're going to ruin the sorting |
| 109 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 110 | if (ent->old_loc + ent->size > old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 111 | extent->sorted = 0; |
| 112 | ent++; |
| 113 | } |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 114 | ent->old_loc = old_loc; |
| 115 | ent->new_loc = new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 116 | ent->size = 1; |
| 117 | extent->num++; |
| 118 | return 0; |
| 119 | } |
| 120 | |
| 121 | /* |
| 122 | * Helper function for qsort |
| 123 | */ |
Theodore Ts'o | 4c77fe5 | 1998-04-30 17:35:59 +0000 | [diff] [blame] | 124 | static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 125 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 126 | const struct ext2_extent_entry *db_a; |
| 127 | const struct ext2_extent_entry *db_b; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 128 | |
Theodore Ts'o | 2a3013b | 1998-03-30 01:08:41 +0000 | [diff] [blame] | 129 | db_a = (const struct ext2_extent_entry *) a; |
| 130 | db_b = (const struct ext2_extent_entry *) b; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 131 | |
| 132 | return (db_a->old_loc - db_b->old_loc); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 133 | } |
| 134 | |
| 135 | /* |
| 136 | * Given an inode map and inode number, look up the old inode number |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 137 | * and return the new inode number. |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 138 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 139 | __u32 ext2fs_extent_translate(ext2_extent extent, __u32 old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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 */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 160 | lowval = extent->list[low].old_loc; |
| 161 | highval = extent->list[high].old_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 162 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 163 | if (old_loc < lowval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 164 | range = 0; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 165 | else if (old_loc > highval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 166 | range = 1; |
| 167 | else |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 168 | range = ((float) (old_loc - lowval)) / |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 169 | (highval - lowval); |
| 170 | mid = low + ((int) (range * (high-low))); |
| 171 | } |
| 172 | #endif |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 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) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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++) { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 197 | fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old_loc, |
| 198 | ent->new_loc, ent->size); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 199 | } |
| 200 | } |
| 201 | |
| 202 | /* |
| 203 | * Iterate over the contents of the extent table |
| 204 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 205 | errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old_loc, |
| 206 | __u32 *new_loc, int *size) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 207 | { |
| 208 | struct ext2_extent_entry *ent; |
| 209 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 210 | if (!old_loc) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 211 | extent->cursor = 0; |
| 212 | return 0; |
| 213 | } |
| 214 | |
| 215 | if (extent->cursor >= extent->num) { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 216 | *old_loc = 0; |
| 217 | *new_loc = 0; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 218 | *size = 0; |
| 219 | return 0; |
| 220 | } |
| 221 | |
| 222 | ent = extent->list + extent->cursor++; |
| 223 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 224 | *old_loc = ent->old_loc; |
| 225 | *new_loc = ent->new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 226 | *size = ent->size; |
| 227 | return 0; |
| 228 | } |
| 229 | |
| 230 | |
| 231 | |
| 232 | |