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