]>
Commit | Line | Data |
---|---|---|
c762c8e6 TT |
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 | * | |
0cee8a5c TT |
8 | * Copyright (C) 1997, 1998 by Theodore Ts'o and |
9 | * PowerQuest, Inc. | |
10 | * | |
055866d8 | 11 | * Copyright (C) 1999, 2000 by Theodore Ts'o |
efc6f628 | 12 | * |
c762c8e6 | 13 | * %Begin-Header% |
0cee8a5c TT |
14 | * This file may be redistributed under the terms of the GNU Public |
15 | * License. | |
c762c8e6 TT |
16 | * %End-Header% |
17 | */ | |
18 | ||
d1154eb4 | 19 | #include "config.h" |
c762c8e6 TT |
20 | #include "resize2fs.h" |
21 | ||
22 | struct ext2_extent_entry { | |
8728d506 VAH |
23 | __u64 old_loc, new_loc; |
24 | __u64 size; | |
c762c8e6 TT |
25 | }; |
26 | ||
27 | struct _ext2_extent { | |
28 | struct ext2_extent_entry *list; | |
8728d506 VAH |
29 | __u64 cursor; |
30 | __u64 size; | |
31 | __u64 num; | |
32 | __u64 sorted; | |
c762c8e6 TT |
33 | }; |
34 | ||
35 | /* | |
36 | * Create an extent table | |
37 | */ | |
8728d506 | 38 | errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, __u64 size) |
c762c8e6 | 39 | { |
ca8abba7 TT |
40 | ext2_extent extent; |
41 | errcode_t retval; | |
efc6f628 | 42 | |
c4e3d3f3 | 43 | retval = ext2fs_get_mem(sizeof(struct _ext2_extent), &extent); |
ca8abba7 TT |
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 | ||
ec30a439 | 53 | retval = ext2fs_get_arrayzero(sizeof(struct ext2_extent_entry), |
c4e3d3f3 | 54 | extent->size, &extent->list); |
ca8abba7 | 55 | if (retval) { |
c4e3d3f3 | 56 | ext2fs_free_mem(&extent); |
ca8abba7 | 57 | return retval; |
c762c8e6 | 58 | } |
ca8abba7 | 59 | *ret_extent = extent; |
c762c8e6 TT |
60 | return 0; |
61 | } | |
62 | ||
63 | /* | |
64 | * Free an extent table | |
65 | */ | |
66 | void ext2fs_free_extent_table(ext2_extent extent) | |
67 | { | |
68 | if (extent->list) | |
c4e3d3f3 | 69 | ext2fs_free_mem(&extent->list); |
c762c8e6 TT |
70 | extent->list = 0; |
71 | extent->size = 0; | |
72 | extent->num = 0; | |
c4e3d3f3 | 73 | ext2fs_free_mem(&extent); |
c762c8e6 TT |
74 | } |
75 | ||
76 | /* | |
77 | * Add an entry to the extent table | |
78 | */ | |
8728d506 | 79 | errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u64 old_loc, __u64 new_loc) |
c762c8e6 | 80 | { |
ca8abba7 TT |
81 | struct ext2_extent_entry *ent; |
82 | errcode_t retval; | |
8728d506 VAH |
83 | __u64 newsize; |
84 | __u64 curr; | |
c762c8e6 TT |
85 | |
86 | if (extent->num >= extent->size) { | |
87 | newsize = extent->size + 100; | |
efc6f628 TT |
88 | retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) * |
89 | extent->size, | |
90 | sizeof(struct ext2_extent_entry) * | |
c4e3d3f3 | 91 | newsize, &extent->list); |
ca8abba7 TT |
92 | if (retval) |
93 | return retval; | |
c762c8e6 TT |
94 | extent->size = newsize; |
95 | } | |
96 | curr = extent->num; | |
97 | ent = extent->list + curr; | |
98 | if (curr) { | |
99 | /* | |
100 | * Check to see if this can be coalesced with the last | |
101 | * extent | |
102 | */ | |
103 | ent--; | |
ca8abba7 TT |
104 | if ((ent->old_loc + ent->size == old_loc) && |
105 | (ent->new_loc + ent->size == new_loc)) { | |
c762c8e6 TT |
106 | ent->size++; |
107 | return 0; | |
108 | } | |
109 | /* | |
110 | * Now see if we're going to ruin the sorting | |
111 | */ | |
ca8abba7 | 112 | if (ent->old_loc + ent->size > old_loc) |
c762c8e6 TT |
113 | extent->sorted = 0; |
114 | ent++; | |
115 | } | |
ca8abba7 TT |
116 | ent->old_loc = old_loc; |
117 | ent->new_loc = new_loc; | |
c762c8e6 TT |
118 | ent->size = 1; |
119 | extent->num++; | |
120 | return 0; | |
121 | } | |
122 | ||
123 | /* | |
124 | * Helper function for qsort | |
125 | */ | |
4c77fe50 | 126 | static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b) |
c762c8e6 | 127 | { |
ca8abba7 TT |
128 | const struct ext2_extent_entry *db_a; |
129 | const struct ext2_extent_entry *db_b; | |
efc6f628 | 130 | |
2a3013b8 TT |
131 | db_a = (const struct ext2_extent_entry *) a; |
132 | db_b = (const struct ext2_extent_entry *) b; | |
efc6f628 | 133 | |
ca8abba7 | 134 | return (db_a->old_loc - db_b->old_loc); |
efc6f628 | 135 | } |
c762c8e6 TT |
136 | |
137 | /* | |
138 | * Given an inode map and inode number, look up the old inode number | |
ca8abba7 | 139 | * and return the new inode number. |
c762c8e6 | 140 | */ |
8728d506 | 141 | __u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc) |
c762c8e6 | 142 | { |
8728d506 VAH |
143 | __s64 low, high, mid; |
144 | __u64 lowval, highval; | |
c762c8e6 TT |
145 | float range; |
146 | ||
147 | if (!extent->sorted) { | |
148 | qsort(extent->list, extent->num, | |
149 | sizeof(struct ext2_extent_entry), extent_cmp); | |
150 | extent->sorted = 1; | |
151 | } | |
152 | low = 0; | |
153 | high = extent->num-1; | |
154 | while (low <= high) { | |
155 | #if 0 | |
156 | mid = (low+high)/2; | |
157 | #else | |
158 | if (low == high) | |
159 | mid = low; | |
160 | else { | |
161 | /* Interpolate for efficiency */ | |
ca8abba7 TT |
162 | lowval = extent->list[low].old_loc; |
163 | highval = extent->list[high].old_loc; | |
c762c8e6 | 164 | |
ca8abba7 | 165 | if (old_loc < lowval) |
c762c8e6 | 166 | range = 0; |
ca8abba7 | 167 | else if (old_loc > highval) |
c762c8e6 | 168 | range = 1; |
ac92f3cc | 169 | else { |
ca8abba7 | 170 | range = ((float) (old_loc - lowval)) / |
c762c8e6 | 171 | (highval - lowval); |
ac92f3cc TT |
172 | if (range > 0.9) |
173 | range = 0.9; | |
174 | if (range < 0.1) | |
175 | range = 0.1; | |
176 | } | |
8728d506 | 177 | mid = low + ((__u64) (range * (high-low))); |
c762c8e6 TT |
178 | } |
179 | #endif | |
ca8abba7 TT |
180 | if ((old_loc >= extent->list[mid].old_loc) && |
181 | (old_loc < extent->list[mid].old_loc + extent->list[mid].size)) | |
182 | return (extent->list[mid].new_loc + | |
183 | (old_loc - extent->list[mid].old_loc)); | |
184 | if (old_loc < extent->list[mid].old_loc) | |
c762c8e6 TT |
185 | high = mid-1; |
186 | else | |
187 | low = mid+1; | |
188 | } | |
189 | return 0; | |
190 | } | |
191 | ||
192 | /* | |
193 | * For debugging only | |
194 | */ | |
195 | void ext2fs_extent_dump(ext2_extent extent, FILE *out) | |
196 | { | |
8728d506 | 197 | __u64 i; |
c762c8e6 | 198 | struct ext2_extent_entry *ent; |
efc6f628 | 199 | |
a13575f4 | 200 | fputs(_("# Extent dump:\n"), out); |
8728d506 | 201 | fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"), |
33b9a60c TT |
202 | (unsigned long long) extent->num, |
203 | (unsigned long long) extent->size, | |
204 | (unsigned long long) extent->cursor, | |
205 | (unsigned long long) extent->sorted); | |
c762c8e6 | 206 | for (i=0, ent=extent->list; i < extent->num; i++, ent++) { |
33b9a60c TT |
207 | fprintf(out, "#\t\t %llu -> %llu (%llu)\n", |
208 | (unsigned long long) ent->old_loc, | |
209 | (unsigned long long) ent->new_loc, | |
210 | (unsigned long long) ent->size); | |
c762c8e6 TT |
211 | } |
212 | } | |
213 | ||
214 | /* | |
215 | * Iterate over the contents of the extent table | |
216 | */ | |
8728d506 VAH |
217 | errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc, |
218 | __u64 *new_loc, __u64 *size) | |
c762c8e6 TT |
219 | { |
220 | struct ext2_extent_entry *ent; | |
efc6f628 | 221 | |
ca8abba7 | 222 | if (!old_loc) { |
c762c8e6 TT |
223 | extent->cursor = 0; |
224 | return 0; | |
225 | } | |
226 | ||
227 | if (extent->cursor >= extent->num) { | |
ca8abba7 TT |
228 | *old_loc = 0; |
229 | *new_loc = 0; | |
c762c8e6 TT |
230 | *size = 0; |
231 | return 0; | |
232 | } | |
233 | ||
234 | ent = extent->list + extent->cursor++; | |
235 | ||
ca8abba7 TT |
236 | *old_loc = ent->old_loc; |
237 | *new_loc = ent->new_loc; | |
c762c8e6 TT |
238 | *size = ent->size; |
239 | return 0; | |
240 | } | |
efc6f628 TT |
241 | |
242 | ||
243 | ||
244 |