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