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) { |
| 52 | free(extent); |
| 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) * |
| 87 | newsize, (void **) &extent->list); |
| 88 | if (retval) |
| 89 | return retval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 90 | extent->size = newsize; |
| 91 | } |
| 92 | curr = extent->num; |
| 93 | ent = extent->list + curr; |
| 94 | if (curr) { |
| 95 | /* |
| 96 | * Check to see if this can be coalesced with the last |
| 97 | * extent |
| 98 | */ |
| 99 | ent--; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 100 | if ((ent->old_loc + ent->size == old_loc) && |
| 101 | (ent->new_loc + ent->size == new_loc)) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 102 | ent->size++; |
| 103 | return 0; |
| 104 | } |
| 105 | /* |
| 106 | * Now see if we're going to ruin the sorting |
| 107 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 108 | if (ent->old_loc + ent->size > old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 109 | extent->sorted = 0; |
| 110 | ent++; |
| 111 | } |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 112 | ent->old_loc = old_loc; |
| 113 | ent->new_loc = new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 114 | ent->size = 1; |
| 115 | extent->num++; |
| 116 | return 0; |
| 117 | } |
| 118 | |
| 119 | /* |
| 120 | * Helper function for qsort |
| 121 | */ |
| 122 | static int extent_cmp(const void *a, const void *b) |
| 123 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 124 | const struct ext2_extent_entry *db_a; |
| 125 | const struct ext2_extent_entry *db_b; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 126 | |
Theodore Ts'o | 2a3013b | 1998-03-30 01:08:41 +0000 | [diff] [blame^] | 127 | db_a = (const struct ext2_extent_entry *) a; |
| 128 | db_b = (const struct ext2_extent_entry *) b; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 129 | |
| 130 | return (db_a->old_loc - db_b->old_loc); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 131 | } |
| 132 | |
| 133 | /* |
| 134 | * 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] | 135 | * and return the new inode number. |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 136 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 137 | __u32 ext2fs_extent_translate(ext2_extent extent, __u32 old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 138 | { |
| 139 | int low, high, mid; |
| 140 | ino_t lowval, highval; |
| 141 | float range; |
| 142 | |
| 143 | if (!extent->sorted) { |
| 144 | qsort(extent->list, extent->num, |
| 145 | sizeof(struct ext2_extent_entry), extent_cmp); |
| 146 | extent->sorted = 1; |
| 147 | } |
| 148 | low = 0; |
| 149 | high = extent->num-1; |
| 150 | while (low <= high) { |
| 151 | #if 0 |
| 152 | mid = (low+high)/2; |
| 153 | #else |
| 154 | if (low == high) |
| 155 | mid = low; |
| 156 | else { |
| 157 | /* Interpolate for efficiency */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 158 | lowval = extent->list[low].old_loc; |
| 159 | highval = extent->list[high].old_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 160 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 161 | if (old_loc < lowval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 162 | range = 0; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 163 | else if (old_loc > highval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 164 | range = 1; |
| 165 | else |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 166 | range = ((float) (old_loc - lowval)) / |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 167 | (highval - lowval); |
| 168 | mid = low + ((int) (range * (high-low))); |
| 169 | } |
| 170 | #endif |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 171 | if ((old_loc >= extent->list[mid].old_loc) && |
| 172 | (old_loc < extent->list[mid].old_loc + extent->list[mid].size)) |
| 173 | return (extent->list[mid].new_loc + |
| 174 | (old_loc - extent->list[mid].old_loc)); |
| 175 | if (old_loc < extent->list[mid].old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 176 | high = mid-1; |
| 177 | else |
| 178 | low = mid+1; |
| 179 | } |
| 180 | return 0; |
| 181 | } |
| 182 | |
| 183 | /* |
| 184 | * For debugging only |
| 185 | */ |
| 186 | void ext2fs_extent_dump(ext2_extent extent, FILE *out) |
| 187 | { |
| 188 | int i; |
| 189 | struct ext2_extent_entry *ent; |
| 190 | |
| 191 | fputs("# Extent dump:\n", out); |
| 192 | fprintf(out, "#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n", |
| 193 | extent->num, extent->size, extent->cursor, extent->sorted); |
| 194 | for (i=0, ent=extent->list; i < extent->num; i++, ent++) { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 195 | fprintf(out, "#\t\t %u -> %u (%d)\n", ent->old_loc, |
| 196 | ent->new_loc, ent->size); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 197 | } |
| 198 | } |
| 199 | |
| 200 | /* |
| 201 | * Iterate over the contents of the extent table |
| 202 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 203 | errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old_loc, |
| 204 | __u32 *new_loc, int *size) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 205 | { |
| 206 | struct ext2_extent_entry *ent; |
| 207 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 208 | if (!old_loc) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 209 | extent->cursor = 0; |
| 210 | return 0; |
| 211 | } |
| 212 | |
| 213 | if (extent->cursor >= extent->num) { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 214 | *old_loc = 0; |
| 215 | *new_loc = 0; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 216 | *size = 0; |
| 217 | return 0; |
| 218 | } |
| 219 | |
| 220 | ent = extent->list + extent->cursor++; |
| 221 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 222 | *old_loc = ent->old_loc; |
| 223 | *new_loc = ent->new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 224 | *size = ent->size; |
| 225 | return 0; |
| 226 | } |
| 227 | |
| 228 | |
| 229 | |
| 230 | |