]>
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 | * | |
11 | * Copyright (C) 1999, 2000 by Theosore 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 | ||
e5aace90 | 53 | retval = ext2fs_get_array(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 TT |
59 | memset(extent->list, 0, |
60 | sizeof(struct ext2_extent_entry) * extent->size); | |
61 | *ret_extent = extent; | |
c762c8e6 TT |
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) | |
c4e3d3f3 | 71 | ext2fs_free_mem(&extent->list); |
c762c8e6 TT |
72 | extent->list = 0; |
73 | extent->size = 0; | |
74 | extent->num = 0; | |
c4e3d3f3 | 75 | ext2fs_free_mem(&extent); |
c762c8e6 TT |
76 | } |
77 | ||
78 | /* | |
79 | * Add an entry to the extent table | |
80 | */ | |
8728d506 | 81 | errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u64 old_loc, __u64 new_loc) |
c762c8e6 | 82 | { |
ca8abba7 TT |
83 | struct ext2_extent_entry *ent; |
84 | errcode_t retval; | |
8728d506 VAH |
85 | __u64 newsize; |
86 | __u64 curr; | |
c762c8e6 TT |
87 | |
88 | if (extent->num >= extent->size) { | |
89 | newsize = extent->size + 100; | |
efc6f628 TT |
90 | retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) * |
91 | extent->size, | |
92 | sizeof(struct ext2_extent_entry) * | |
c4e3d3f3 | 93 | newsize, &extent->list); |
ca8abba7 TT |
94 | if (retval) |
95 | return retval; | |
c762c8e6 TT |
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--; | |
ca8abba7 TT |
106 | if ((ent->old_loc + ent->size == old_loc) && |
107 | (ent->new_loc + ent->size == new_loc)) { | |
c762c8e6 TT |
108 | ent->size++; |
109 | return 0; | |
110 | } | |
111 | /* | |
112 | * Now see if we're going to ruin the sorting | |
113 | */ | |
ca8abba7 | 114 | if (ent->old_loc + ent->size > old_loc) |
c762c8e6 TT |
115 | extent->sorted = 0; |
116 | ent++; | |
117 | } | |
ca8abba7 TT |
118 | ent->old_loc = old_loc; |
119 | ent->new_loc = new_loc; | |
c762c8e6 TT |
120 | ent->size = 1; |
121 | extent->num++; | |
122 | return 0; | |
123 | } | |
124 | ||
125 | /* | |
126 | * Helper function for qsort | |
127 | */ | |
4c77fe50 | 128 | static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b) |
c762c8e6 | 129 | { |
ca8abba7 TT |
130 | const struct ext2_extent_entry *db_a; |
131 | const struct ext2_extent_entry *db_b; | |
efc6f628 | 132 | |
2a3013b8 TT |
133 | db_a = (const struct ext2_extent_entry *) a; |
134 | db_b = (const struct ext2_extent_entry *) b; | |
efc6f628 | 135 | |
ca8abba7 | 136 | return (db_a->old_loc - db_b->old_loc); |
efc6f628 | 137 | } |
c762c8e6 TT |
138 | |
139 | /* | |
140 | * Given an inode map and inode number, look up the old inode number | |
ca8abba7 | 141 | * and return the new inode number. |
c762c8e6 | 142 | */ |
8728d506 | 143 | __u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc) |
c762c8e6 | 144 | { |
8728d506 VAH |
145 | __s64 low, high, mid; |
146 | __u64 lowval, highval; | |
c762c8e6 TT |
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 */ | |
ca8abba7 TT |
164 | lowval = extent->list[low].old_loc; |
165 | highval = extent->list[high].old_loc; | |
c762c8e6 | 166 | |
ca8abba7 | 167 | if (old_loc < lowval) |
c762c8e6 | 168 | range = 0; |
ca8abba7 | 169 | else if (old_loc > highval) |
c762c8e6 | 170 | range = 1; |
ac92f3cc | 171 | else { |
ca8abba7 | 172 | range = ((float) (old_loc - lowval)) / |
c762c8e6 | 173 | (highval - lowval); |
ac92f3cc TT |
174 | if (range > 0.9) |
175 | range = 0.9; | |
176 | if (range < 0.1) | |
177 | range = 0.1; | |
178 | } | |
8728d506 | 179 | mid = low + ((__u64) (range * (high-low))); |
c762c8e6 TT |
180 | } |
181 | #endif | |
ca8abba7 TT |
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) | |
c762c8e6 TT |
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 | { | |
8728d506 | 199 | __u64 i; |
c762c8e6 | 200 | struct ext2_extent_entry *ent; |
efc6f628 | 201 | |
a13575f4 | 202 | fputs(_("# Extent dump:\n"), out); |
8728d506 | 203 | fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"), |
c762c8e6 TT |
204 | extent->num, extent->size, extent->cursor, extent->sorted); |
205 | for (i=0, ent=extent->list; i < extent->num; i++, ent++) { | |
84888e55 | 206 | fprintf(out, "#\t\t %llu -> %llu (%llu)\n", ent->old_loc, |
ca8abba7 | 207 | ent->new_loc, ent->size); |
c762c8e6 TT |
208 | } |
209 | } | |
210 | ||
211 | /* | |
212 | * Iterate over the contents of the extent table | |
213 | */ | |
8728d506 VAH |
214 | errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc, |
215 | __u64 *new_loc, __u64 *size) | |
c762c8e6 TT |
216 | { |
217 | struct ext2_extent_entry *ent; | |
efc6f628 | 218 | |
ca8abba7 | 219 | if (!old_loc) { |
c762c8e6 TT |
220 | extent->cursor = 0; |
221 | return 0; | |
222 | } | |
223 | ||
224 | if (extent->cursor >= extent->num) { | |
ca8abba7 TT |
225 | *old_loc = 0; |
226 | *new_loc = 0; | |
c762c8e6 TT |
227 | *size = 0; |
228 | return 0; | |
229 | } | |
230 | ||
231 | ent = extent->list + extent->cursor++; | |
232 | ||
ca8abba7 TT |
233 | *old_loc = ent->old_loc; |
234 | *new_loc = ent->new_loc; | |
c762c8e6 TT |
235 | *size = ent->size; |
236 | return 0; | |
237 | } | |
efc6f628 TT |
238 | |
239 | ||
240 | ||
241 |