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