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