diff options
Diffstat (limited to 'e2fsprogs/e2fsck/ea_refcount.c')
-rw-r--r-- | e2fsprogs/e2fsck/ea_refcount.c | 479 |
1 files changed, 479 insertions, 0 deletions
diff --git a/e2fsprogs/e2fsck/ea_refcount.c b/e2fsprogs/e2fsck/ea_refcount.c new file mode 100644 index 000000000..6420c7280 --- /dev/null +++ b/e2fsprogs/e2fsck/ea_refcount.c | |||
@@ -0,0 +1,479 @@ | |||
1 | /* | ||
2 | * ea_refcount.c | ||
3 | * | ||
4 | * Copyright (C) 2001 Theodore Ts'o. This file may be | ||
5 | * redistributed under the terms of the GNU Public License. | ||
6 | */ | ||
7 | |||
8 | #if HAVE_UNISTD_H | ||
9 | #include <unistd.h> | ||
10 | #endif | ||
11 | #include <string.h> | ||
12 | #include <stdio.h> | ||
13 | |||
14 | #include "e2fsck.h" | ||
15 | |||
16 | /* | ||
17 | * The strategy we use for keeping track of EA refcounts is as | ||
18 | * follows. We keep a sorted array of first EA blocks and its | ||
19 | * reference counts. Once the refcount has dropped to zero, it is | ||
20 | * removed from the array to save memory space. Once the EA block is | ||
21 | * checked, its bit is set in the block_ea_map bitmap. | ||
22 | */ | ||
23 | struct ea_refcount_el { | ||
24 | blk_t ea_blk; | ||
25 | int ea_count; | ||
26 | }; | ||
27 | |||
28 | struct ea_refcount { | ||
29 | blk_t count; | ||
30 | blk_t size; | ||
31 | blk_t cursor; | ||
32 | struct ea_refcount_el *list; | ||
33 | }; | ||
34 | |||
35 | void ea_refcount_free(ext2_refcount_t refcount) | ||
36 | { | ||
37 | if (!refcount) | ||
38 | return; | ||
39 | |||
40 | if (refcount->list) | ||
41 | ext2fs_free_mem(&refcount->list); | ||
42 | ext2fs_free_mem(&refcount); | ||
43 | } | ||
44 | |||
45 | errcode_t ea_refcount_create(int size, ext2_refcount_t *ret) | ||
46 | { | ||
47 | ext2_refcount_t refcount; | ||
48 | errcode_t retval; | ||
49 | size_t bytes; | ||
50 | |||
51 | retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount); | ||
52 | if (retval) | ||
53 | return retval; | ||
54 | memset(refcount, 0, sizeof(struct ea_refcount)); | ||
55 | |||
56 | if (!size) | ||
57 | size = 500; | ||
58 | refcount->size = size; | ||
59 | bytes = (size_t) (size * sizeof(struct ea_refcount_el)); | ||
60 | #ifdef DEBUG | ||
61 | printf("Refcount allocated %d entries, %d bytes.\n", | ||
62 | refcount->size, bytes); | ||
63 | #endif | ||
64 | retval = ext2fs_get_mem(bytes, &refcount->list); | ||
65 | if (retval) | ||
66 | goto errout; | ||
67 | memset(refcount->list, 0, bytes); | ||
68 | |||
69 | refcount->count = 0; | ||
70 | refcount->cursor = 0; | ||
71 | |||
72 | *ret = refcount; | ||
73 | return 0; | ||
74 | |||
75 | errout: | ||
76 | ea_refcount_free(refcount); | ||
77 | return(retval); | ||
78 | } | ||
79 | |||
80 | /* | ||
81 | * collapse_refcount() --- go through the refcount array, and get rid | ||
82 | * of any count == zero entries | ||
83 | */ | ||
84 | static void refcount_collapse(ext2_refcount_t refcount) | ||
85 | { | ||
86 | unsigned int i, j; | ||
87 | struct ea_refcount_el *list; | ||
88 | |||
89 | list = refcount->list; | ||
90 | for (i = 0, j = 0; i < refcount->count; i++) { | ||
91 | if (list[i].ea_count) { | ||
92 | if (i != j) | ||
93 | list[j] = list[i]; | ||
94 | j++; | ||
95 | } | ||
96 | } | ||
97 | #if defined(DEBUG) || defined(TEST_PROGRAM) | ||
98 | printf("Refcount_collapse: size was %d, now %d\n", | ||
99 | refcount->count, j); | ||
100 | #endif | ||
101 | refcount->count = j; | ||
102 | } | ||
103 | |||
104 | |||
105 | /* | ||
106 | * insert_refcount_el() --- Insert a new entry into the sorted list at a | ||
107 | * specified position. | ||
108 | */ | ||
109 | static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount, | ||
110 | blk_t blk, int pos) | ||
111 | { | ||
112 | struct ea_refcount_el *el; | ||
113 | errcode_t retval; | ||
114 | blk_t new_size = 0; | ||
115 | int num; | ||
116 | |||
117 | if (refcount->count >= refcount->size) { | ||
118 | new_size = refcount->size + 100; | ||
119 | #ifdef DEBUG | ||
120 | printf("Reallocating refcount %d entries...\n", new_size); | ||
121 | #endif | ||
122 | retval = ext2fs_resize_mem((size_t) refcount->size * | ||
123 | sizeof(struct ea_refcount_el), | ||
124 | (size_t) new_size * | ||
125 | sizeof(struct ea_refcount_el), | ||
126 | &refcount->list); | ||
127 | if (retval) | ||
128 | return 0; | ||
129 | refcount->size = new_size; | ||
130 | } | ||
131 | num = (int) refcount->count - pos; | ||
132 | if (num < 0) | ||
133 | return 0; /* should never happen */ | ||
134 | if (num) { | ||
135 | memmove(&refcount->list[pos+1], &refcount->list[pos], | ||
136 | sizeof(struct ea_refcount_el) * num); | ||
137 | } | ||
138 | refcount->count++; | ||
139 | el = &refcount->list[pos]; | ||
140 | el->ea_count = 0; | ||
141 | el->ea_blk = blk; | ||
142 | return el; | ||
143 | } | ||
144 | |||
145 | |||
146 | /* | ||
147 | * get_refcount_el() --- given an block number, try to find refcount | ||
148 | * information in the sorted list. If the create flag is set, | ||
149 | * and we can't find an entry, create one in the sorted list. | ||
150 | */ | ||
151 | static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount, | ||
152 | blk_t blk, int create) | ||
153 | { | ||
154 | float range; | ||
155 | int low, high, mid; | ||
156 | blk_t lowval, highval; | ||
157 | |||
158 | if (!refcount || !refcount->list) | ||
159 | return 0; | ||
160 | retry: | ||
161 | low = 0; | ||
162 | high = (int) refcount->count-1; | ||
163 | if (create && ((refcount->count == 0) || | ||
164 | (blk > refcount->list[high].ea_blk))) { | ||
165 | if (refcount->count >= refcount->size) | ||
166 | refcount_collapse(refcount); | ||
167 | |||
168 | return insert_refcount_el(refcount, blk, | ||
169 | (unsigned) refcount->count); | ||
170 | } | ||
171 | if (refcount->count == 0) | ||
172 | return 0; | ||
173 | |||
174 | if (refcount->cursor >= refcount->count) | ||
175 | refcount->cursor = 0; | ||
176 | if (blk == refcount->list[refcount->cursor].ea_blk) | ||
177 | return &refcount->list[refcount->cursor++]; | ||
178 | #ifdef DEBUG | ||
179 | printf("Non-cursor get_refcount_el: %u\n", blk); | ||
180 | #endif | ||
181 | while (low <= high) { | ||
182 | #if 0 | ||
183 | mid = (low+high)/2; | ||
184 | #else | ||
185 | if (low == high) | ||
186 | mid = low; | ||
187 | else { | ||
188 | /* Interpolate for efficiency */ | ||
189 | lowval = refcount->list[low].ea_blk; | ||
190 | highval = refcount->list[high].ea_blk; | ||
191 | |||
192 | if (blk < lowval) | ||
193 | range = 0; | ||
194 | else if (blk > highval) | ||
195 | range = 1; | ||
196 | else | ||
197 | range = ((float) (blk - lowval)) / | ||
198 | (highval - lowval); | ||
199 | mid = low + ((int) (range * (high-low))); | ||
200 | } | ||
201 | #endif | ||
202 | if (blk == refcount->list[mid].ea_blk) { | ||
203 | refcount->cursor = mid+1; | ||
204 | return &refcount->list[mid]; | ||
205 | } | ||
206 | if (blk < refcount->list[mid].ea_blk) | ||
207 | high = mid-1; | ||
208 | else | ||
209 | low = mid+1; | ||
210 | } | ||
211 | /* | ||
212 | * If we need to create a new entry, it should be right at | ||
213 | * low (where high will be left at low-1). | ||
214 | */ | ||
215 | if (create) { | ||
216 | if (refcount->count >= refcount->size) { | ||
217 | refcount_collapse(refcount); | ||
218 | if (refcount->count < refcount->size) | ||
219 | goto retry; | ||
220 | } | ||
221 | return insert_refcount_el(refcount, blk, low); | ||
222 | } | ||
223 | return 0; | ||
224 | } | ||
225 | |||
226 | errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk, | ||
227 | int *ret) | ||
228 | { | ||
229 | struct ea_refcount_el *el; | ||
230 | |||
231 | el = get_refcount_el(refcount, blk, 0); | ||
232 | if (!el) { | ||
233 | *ret = 0; | ||
234 | return 0; | ||
235 | } | ||
236 | *ret = el->ea_count; | ||
237 | return 0; | ||
238 | } | ||
239 | |||
240 | errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret) | ||
241 | { | ||
242 | struct ea_refcount_el *el; | ||
243 | |||
244 | el = get_refcount_el(refcount, blk, 1); | ||
245 | if (!el) | ||
246 | return EXT2_ET_NO_MEMORY; | ||
247 | el->ea_count++; | ||
248 | |||
249 | if (ret) | ||
250 | *ret = el->ea_count; | ||
251 | return 0; | ||
252 | } | ||
253 | |||
254 | errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret) | ||
255 | { | ||
256 | struct ea_refcount_el *el; | ||
257 | |||
258 | el = get_refcount_el(refcount, blk, 0); | ||
259 | if (!el || el->ea_count == 0) | ||
260 | return EXT2_ET_INVALID_ARGUMENT; | ||
261 | |||
262 | el->ea_count--; | ||
263 | |||
264 | if (ret) | ||
265 | *ret = el->ea_count; | ||
266 | return 0; | ||
267 | } | ||
268 | |||
269 | errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count) | ||
270 | { | ||
271 | struct ea_refcount_el *el; | ||
272 | |||
273 | /* | ||
274 | * Get the refcount element | ||
275 | */ | ||
276 | el = get_refcount_el(refcount, blk, count ? 1 : 0); | ||
277 | if (!el) | ||
278 | return count ? EXT2_ET_NO_MEMORY : 0; | ||
279 | el->ea_count = count; | ||
280 | return 0; | ||
281 | } | ||
282 | |||
283 | blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount) | ||
284 | { | ||
285 | if (!refcount) | ||
286 | return 0; | ||
287 | |||
288 | return refcount->size; | ||
289 | } | ||
290 | |||
291 | void ea_refcount_intr_begin(ext2_refcount_t refcount) | ||
292 | { | ||
293 | refcount->cursor = 0; | ||
294 | } | ||
295 | |||
296 | |||
297 | blk_t ea_refcount_intr_next(ext2_refcount_t refcount, | ||
298 | int *ret) | ||
299 | { | ||
300 | struct ea_refcount_el *list; | ||
301 | |||
302 | while (1) { | ||
303 | if (refcount->cursor >= refcount->count) | ||
304 | return 0; | ||
305 | list = refcount->list; | ||
306 | if (list[refcount->cursor].ea_count) { | ||
307 | if (ret) | ||
308 | *ret = list[refcount->cursor].ea_count; | ||
309 | return list[refcount->cursor++].ea_blk; | ||
310 | } | ||
311 | refcount->cursor++; | ||
312 | } | ||
313 | } | ||
314 | |||
315 | |||
316 | #ifdef TEST_PROGRAM | ||
317 | |||
318 | errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out) | ||
319 | { | ||
320 | errcode_t ret = 0; | ||
321 | int i; | ||
322 | const char *bad = "bad refcount"; | ||
323 | |||
324 | if (refcount->count > refcount->size) { | ||
325 | fprintf(out, "%s: count > size\n", bad); | ||
326 | return EXT2_ET_INVALID_ARGUMENT; | ||
327 | } | ||
328 | for (i=1; i < refcount->count; i++) { | ||
329 | if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) { | ||
330 | fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n", | ||
331 | bad, i-1, refcount->list[i-1].ea_blk, | ||
332 | i, refcount->list[i].ea_blk); | ||
333 | ret = EXT2_ET_INVALID_ARGUMENT; | ||
334 | } | ||
335 | } | ||
336 | return ret; | ||
337 | } | ||
338 | |||
339 | #define BCODE_END 0 | ||
340 | #define BCODE_CREATE 1 | ||
341 | #define BCODE_FREE 2 | ||
342 | #define BCODE_STORE 3 | ||
343 | #define BCODE_INCR 4 | ||
344 | #define BCODE_DECR 5 | ||
345 | #define BCODE_FETCH 6 | ||
346 | #define BCODE_VALIDATE 7 | ||
347 | #define BCODE_LIST 8 | ||
348 | #define BCODE_COLLAPSE 9 | ||
349 | |||
350 | int bcode_program[] = { | ||
351 | BCODE_CREATE, 5, | ||
352 | BCODE_STORE, 3, 3, | ||
353 | BCODE_STORE, 4, 4, | ||
354 | BCODE_STORE, 1, 1, | ||
355 | BCODE_STORE, 8, 8, | ||
356 | BCODE_STORE, 2, 2, | ||
357 | BCODE_STORE, 4, 0, | ||
358 | BCODE_STORE, 2, 0, | ||
359 | BCODE_STORE, 6, 6, | ||
360 | BCODE_VALIDATE, | ||
361 | BCODE_STORE, 4, 4, | ||
362 | BCODE_STORE, 2, 2, | ||
363 | BCODE_FETCH, 1, | ||
364 | BCODE_FETCH, 2, | ||
365 | BCODE_INCR, 3, | ||
366 | BCODE_INCR, 3, | ||
367 | BCODE_DECR, 4, | ||
368 | BCODE_STORE, 4, 4, | ||
369 | BCODE_VALIDATE, | ||
370 | BCODE_STORE, 20, 20, | ||
371 | BCODE_STORE, 40, 40, | ||
372 | BCODE_STORE, 30, 30, | ||
373 | BCODE_STORE, 10, 10, | ||
374 | BCODE_DECR, 30, | ||
375 | BCODE_FETCH, 30, | ||
376 | BCODE_DECR, 2, | ||
377 | BCODE_DECR, 2, | ||
378 | BCODE_COLLAPSE, | ||
379 | BCODE_LIST, | ||
380 | BCODE_VALIDATE, | ||
381 | BCODE_FREE, | ||
382 | BCODE_END | ||
383 | }; | ||
384 | |||
385 | int main(int argc, char **argv) | ||
386 | { | ||
387 | int i = 0; | ||
388 | ext2_refcount_t refcount; | ||
389 | int size, arg; | ||
390 | blk_t blk; | ||
391 | errcode_t retval; | ||
392 | |||
393 | while (1) { | ||
394 | switch (bcode_program[i++]) { | ||
395 | case BCODE_END: | ||
396 | exit(0); | ||
397 | case BCODE_CREATE: | ||
398 | size = bcode_program[i++]; | ||
399 | retval = ea_refcount_create(size, &refcount); | ||
400 | if (retval) { | ||
401 | com_err("ea_refcount_create", | ||
402 | retval, ""); | ||
403 | exit(1); | ||
404 | } else | ||
405 | printf("Creating refcount with size %d\n", | ||
406 | size); | ||
407 | break; | ||
408 | case BCODE_FREE: | ||
409 | ea_refcount_free(refcount); | ||
410 | refcount = 0; | ||
411 | printf("Freeing refcount\n"); | ||
412 | break; | ||
413 | case BCODE_STORE: | ||
414 | blk = (blk_t) bcode_program[i++]; | ||
415 | arg = bcode_program[i++]; | ||
416 | retval = ea_refcount_store(refcount, blk, arg); | ||
417 | printf("Storing blk %u with value %d\n", blk, arg); | ||
418 | if (retval) | ||
419 | com_err("ea_refcount_store", retval, ""); | ||
420 | break; | ||
421 | case BCODE_FETCH: | ||
422 | blk = (blk_t) bcode_program[i++]; | ||
423 | retval = ea_refcount_fetch(refcount, blk, &arg); | ||
424 | if (retval) | ||
425 | com_err("ea_refcount_fetch", retval, ""); | ||
426 | else | ||
427 | printf("bcode_fetch(%u) returns %d\n", | ||
428 | blk, arg); | ||
429 | break; | ||
430 | case BCODE_INCR: | ||
431 | blk = (blk_t) bcode_program[i++]; | ||
432 | retval = ea_refcount_increment(refcount, blk, | ||
433 | &arg); | ||
434 | if (retval) | ||
435 | com_err("ea_refcount_increment", retval, | ||
436 | ""); | ||
437 | else | ||
438 | printf("bcode_increment(%u) returns %d\n", | ||
439 | blk, arg); | ||
440 | break; | ||
441 | case BCODE_DECR: | ||
442 | blk = (blk_t) bcode_program[i++]; | ||
443 | retval = ea_refcount_decrement(refcount, blk, | ||
444 | &arg); | ||
445 | if (retval) | ||
446 | com_err("ea_refcount_decrement", retval, | ||
447 | "while decrementing blk %u", blk); | ||
448 | else | ||
449 | printf("bcode_decrement(%u) returns %d\n", | ||
450 | blk, arg); | ||
451 | break; | ||
452 | case BCODE_VALIDATE: | ||
453 | retval = ea_refcount_validate(refcount, stderr); | ||
454 | if (retval) | ||
455 | com_err("ea_refcount_validate", | ||
456 | retval, ""); | ||
457 | else | ||
458 | printf("Refcount validation OK.\n"); | ||
459 | break; | ||
460 | case BCODE_LIST: | ||
461 | ea_refcount_intr_begin(refcount); | ||
462 | while (1) { | ||
463 | blk = ea_refcount_intr_next(refcount, | ||
464 | &arg); | ||
465 | if (!blk) | ||
466 | break; | ||
467 | printf("\tblk=%u, count=%d\n", blk, | ||
468 | arg); | ||
469 | } | ||
470 | break; | ||
471 | case BCODE_COLLAPSE: | ||
472 | refcount_collapse(refcount); | ||
473 | break; | ||
474 | } | ||
475 | |||
476 | } | ||
477 | } | ||
478 | |||
479 | #endif | ||