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 | * |
Theodore Ts'o | 0cee8a5 | 2000-04-06 21:38:34 +0000 | [diff] [blame] | 8 | * Copyright (C) 1997, 1998 by Theodore Ts'o and |
| 9 | * PowerQuest, Inc. |
| 10 | * |
| 11 | * Copyright (C) 1999, 2000 by Theosore Ts'o |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 12 | * |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 13 | * %Begin-Header% |
Theodore Ts'o | 0cee8a5 | 2000-04-06 21:38:34 +0000 | [diff] [blame] | 14 | * This file may be redistributed under the terms of the GNU Public |
| 15 | * License. |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 16 | * %End-Header% |
| 17 | */ |
| 18 | |
Theodore Ts'o | d1154eb | 2011-09-18 17:34:37 -0400 | [diff] [blame] | 19 | #include "config.h" |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 20 | #include "resize2fs.h" |
| 21 | |
| 22 | struct ext2_extent_entry { |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 23 | __u64 old_loc, new_loc; |
| 24 | __u64 size; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 25 | }; |
| 26 | |
| 27 | struct _ext2_extent { |
| 28 | struct ext2_extent_entry *list; |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 29 | __u64 cursor; |
| 30 | __u64 size; |
| 31 | __u64 num; |
| 32 | __u64 sorted; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 33 | }; |
| 34 | |
| 35 | /* |
| 36 | * Create an extent table |
| 37 | */ |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 38 | errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, __u64 size) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 39 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 40 | ext2_extent extent; |
| 41 | errcode_t retval; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 42 | |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 43 | retval = ext2fs_get_mem(sizeof(struct _ext2_extent), &extent); |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 44 | if (retval) |
| 45 | return retval; |
| 46 | memset(extent, 0, sizeof(struct _ext2_extent)); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 47 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 48 | extent->size = size ? size : 50; |
| 49 | extent->cursor = 0; |
| 50 | extent->num = 0; |
| 51 | extent->sorted = 1; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 52 | |
Theodore Ts'o | e5aace9 | 2007-12-27 10:08:13 -0500 | [diff] [blame] | 53 | retval = ext2fs_get_array(sizeof(struct ext2_extent_entry), |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 54 | extent->size, &extent->list); |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 55 | if (retval) { |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 56 | ext2fs_free_mem(&extent); |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 57 | return retval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 58 | } |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 59 | memset(extent->list, 0, |
| 60 | sizeof(struct ext2_extent_entry) * extent->size); |
| 61 | *ret_extent = extent; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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) |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 71 | ext2fs_free_mem(&extent->list); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 72 | extent->list = 0; |
| 73 | extent->size = 0; |
| 74 | extent->num = 0; |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 75 | ext2fs_free_mem(&extent); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 76 | } |
| 77 | |
| 78 | /* |
| 79 | * Add an entry to the extent table |
| 80 | */ |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 81 | errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u64 old_loc, __u64 new_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 82 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 83 | struct ext2_extent_entry *ent; |
| 84 | errcode_t retval; |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 85 | __u64 newsize; |
| 86 | __u64 curr; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 87 | |
| 88 | if (extent->num >= extent->size) { |
| 89 | newsize = extent->size + 100; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 90 | retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) * |
| 91 | extent->size, |
| 92 | sizeof(struct ext2_extent_entry) * |
Theodore Ts'o | c4e3d3f | 2003-08-01 09:41:07 -0400 | [diff] [blame] | 93 | newsize, &extent->list); |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 94 | if (retval) |
| 95 | return retval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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--; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 106 | if ((ent->old_loc + ent->size == old_loc) && |
| 107 | (ent->new_loc + ent->size == new_loc)) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 108 | ent->size++; |
| 109 | return 0; |
| 110 | } |
| 111 | /* |
| 112 | * Now see if we're going to ruin the sorting |
| 113 | */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 114 | if (ent->old_loc + ent->size > old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 115 | extent->sorted = 0; |
| 116 | ent++; |
| 117 | } |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 118 | ent->old_loc = old_loc; |
| 119 | ent->new_loc = new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 120 | ent->size = 1; |
| 121 | extent->num++; |
| 122 | return 0; |
| 123 | } |
| 124 | |
| 125 | /* |
| 126 | * Helper function for qsort |
| 127 | */ |
Theodore Ts'o | 4c77fe5 | 1998-04-30 17:35:59 +0000 | [diff] [blame] | 128 | 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] | 129 | { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 130 | const struct ext2_extent_entry *db_a; |
| 131 | const struct ext2_extent_entry *db_b; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 132 | |
Theodore Ts'o | 2a3013b | 1998-03-30 01:08:41 +0000 | [diff] [blame] | 133 | db_a = (const struct ext2_extent_entry *) a; |
| 134 | db_b = (const struct ext2_extent_entry *) b; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 135 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 136 | return (db_a->old_loc - db_b->old_loc); |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 137 | } |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 138 | |
| 139 | /* |
| 140 | * 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] | 141 | * and return the new inode number. |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 142 | */ |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 143 | __u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 144 | { |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 145 | __s64 low, high, mid; |
| 146 | __u64 lowval, highval; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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 */ |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 164 | lowval = extent->list[low].old_loc; |
| 165 | highval = extent->list[high].old_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 166 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 167 | if (old_loc < lowval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 168 | range = 0; |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 169 | else if (old_loc > highval) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 170 | range = 1; |
Theodore Ts'o | ac92f3c | 2010-07-05 20:40:41 -0400 | [diff] [blame] | 171 | else { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 172 | range = ((float) (old_loc - lowval)) / |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 173 | (highval - lowval); |
Theodore Ts'o | ac92f3c | 2010-07-05 20:40:41 -0400 | [diff] [blame] | 174 | if (range > 0.9) |
| 175 | range = 0.9; |
| 176 | if (range < 0.1) |
| 177 | range = 0.1; |
| 178 | } |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 179 | mid = low + ((__u64) (range * (high-low))); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 180 | } |
| 181 | #endif |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 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) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 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 | { |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 199 | __u64 i; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 200 | struct ext2_extent_entry *ent; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 201 | |
Theodore Ts'o | a13575f | 2000-06-12 22:06:16 +0000 | [diff] [blame] | 202 | fputs(_("# Extent dump:\n"), out); |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 203 | fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"), |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 204 | extent->num, extent->size, extent->cursor, extent->sorted); |
| 205 | for (i=0, ent=extent->list; i < extent->num; i++, ent++) { |
Theodore Ts'o | 84888e5 | 2011-10-08 13:32:00 -0400 | [diff] [blame] | 206 | fprintf(out, "#\t\t %llu -> %llu (%llu)\n", ent->old_loc, |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 207 | ent->new_loc, ent->size); |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 208 | } |
| 209 | } |
| 210 | |
| 211 | /* |
| 212 | * Iterate over the contents of the extent table |
| 213 | */ |
Valerie Aurora Henson | 8728d50 | 2010-06-13 18:00:00 -0400 | [diff] [blame] | 214 | errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc, |
| 215 | __u64 *new_loc, __u64 *size) |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 216 | { |
| 217 | struct ext2_extent_entry *ent; |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 218 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 219 | if (!old_loc) { |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 220 | extent->cursor = 0; |
| 221 | return 0; |
| 222 | } |
| 223 | |
| 224 | if (extent->cursor >= extent->num) { |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 225 | *old_loc = 0; |
| 226 | *new_loc = 0; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 227 | *size = 0; |
| 228 | return 0; |
| 229 | } |
| 230 | |
| 231 | ent = extent->list + extent->cursor++; |
| 232 | |
Theodore Ts'o | ca8abba | 1998-01-19 14:55:24 +0000 | [diff] [blame] | 233 | *old_loc = ent->old_loc; |
| 234 | *new_loc = ent->new_loc; |
Theodore Ts'o | c762c8e | 1997-06-17 03:52:12 +0000 | [diff] [blame] | 235 | *size = ent->size; |
| 236 | return 0; |
| 237 | } |
Theodore Ts'o | efc6f62 | 2008-08-27 23:07:54 -0400 | [diff] [blame] | 238 | |
| 239 | |
| 240 | |
| 241 | |