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