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 #include "config.h"
9 #if HAVE_UNISTD_H
10 #include <unistd.h>
11 #endif
12 #include <string.h>
13 #include <stdio.h>
14
15 #ifdef TEST_PROGRAM
16 #undef ENABLE_NLS
17 #endif
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
25 * checked, its bit is set in the block_ea_map bitmap.
26 */
27 struct ea_refcount_el {
28 /* ea_key could either be an inode number or block number. */
29 ea_key_t ea_key;
30 ea_value_t ea_value;
31 };
32
33 struct ea_refcount {
34 size_t count;
35 size_t size;
36 size_t cursor;
37 struct ea_refcount_el *list;
38 };
39
ea_refcount_free(ext2_refcount_t refcount)40 void ea_refcount_free(ext2_refcount_t refcount)
41 {
42 if (!refcount)
43 return;
44
45 if (refcount->list)
46 ext2fs_free_mem(&refcount->list);
47 ext2fs_free_mem(&refcount);
48 }
49
ea_refcount_create(size_t size,ext2_refcount_t * ret)50 errcode_t ea_refcount_create(size_t size, ext2_refcount_t *ret)
51 {
52 ext2_refcount_t refcount;
53 errcode_t retval;
54 size_t bytes;
55
56 retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount);
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;
64 bytes = size * sizeof(struct ea_refcount_el);
65 #ifdef DEBUG
66 printf("Refcount allocated %zu entries, %zu bytes.\n",
67 refcount->size, bytes);
68 #endif
69 retval = ext2fs_get_mem(bytes, &refcount->list);
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 */
refcount_collapse(ext2_refcount_t refcount)89 static void refcount_collapse(ext2_refcount_t refcount)
90 {
91 unsigned int i, j;
92 struct ea_refcount_el *list;
93
94 list = refcount->list;
95 for (i = 0, j = 0; i < refcount->count; i++) {
96 if (list[i].ea_value) {
97 if (i != j)
98 list[j] = list[i];
99 j++;
100 }
101 }
102 #if defined(DEBUG) || defined(TEST_PROGRAM)
103 printf("Refcount_collapse: size was %zu, now %d\n",
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 */
insert_refcount_el(ext2_refcount_t refcount,ea_key_t ea_key,int pos)114 static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount,
115 ea_key_t ea_key, int pos)
116 {
117 struct ea_refcount_el *el;
118 errcode_t retval;
119 size_t new_size = 0;
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);
126 #endif
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),
131 &refcount->list);
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];
145 el->ea_key = ea_key;
146 el->ea_value = 0;
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 */
get_refcount_el(ext2_refcount_t refcount,ea_key_t ea_key,int create)156 static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount,
157 ea_key_t ea_key, int create)
158 {
159 int low, high, mid;
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) ||
167 (ea_key > refcount->list[high].ea_key))) {
168 if (refcount->count >= refcount->size)
169 refcount_collapse(refcount);
170
171 return insert_refcount_el(refcount, ea_key,
172 (unsigned) refcount->count);
173 }
174 if (refcount->count == 0)
175 return 0;
176
177 if (refcount->cursor >= refcount->count)
178 refcount->cursor = 0;
179 if (ea_key == refcount->list[refcount->cursor].ea_key)
180 return &refcount->list[refcount->cursor++];
181 #ifdef DEBUG
182 printf("Non-cursor get_refcount_el: %u\n", ea_key);
183 #endif
184 while (low <= high) {
185 mid = (low+high)/2;
186 if (ea_key == refcount->list[mid].ea_key) {
187 refcount->cursor = mid+1;
188 return &refcount->list[mid];
189 }
190 if (ea_key < refcount->list[mid].ea_key)
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 }
205 return insert_refcount_el(refcount, ea_key, low);
206 }
207 return 0;
208 }
209
ea_refcount_fetch(ext2_refcount_t refcount,ea_key_t ea_key,ea_value_t * ret)210 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, ea_key_t ea_key,
211 ea_value_t *ret)
212 {
213 struct ea_refcount_el *el;
214
215 el = get_refcount_el(refcount, ea_key, 0);
216 if (!el) {
217 *ret = 0;
218 return 0;
219 }
220 *ret = el->ea_value;
221 return 0;
222 }
223
ea_refcount_increment(ext2_refcount_t refcount,ea_key_t ea_key,ea_value_t * ret)224 errcode_t ea_refcount_increment(ext2_refcount_t refcount, ea_key_t ea_key,
225 ea_value_t *ret)
226 {
227 struct ea_refcount_el *el;
228
229 el = get_refcount_el(refcount, ea_key, 1);
230 if (!el)
231 return EXT2_ET_NO_MEMORY;
232 el->ea_value++;
233
234 if (ret)
235 *ret = el->ea_value;
236 return 0;
237 }
238
ea_refcount_decrement(ext2_refcount_t refcount,ea_key_t ea_key,ea_value_t * ret)239 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, ea_key_t ea_key,
240 ea_value_t *ret)
241 {
242 struct ea_refcount_el *el;
243
244 el = get_refcount_el(refcount, ea_key, 0);
245 if (!el || el->ea_value == 0)
246 return EXT2_ET_INVALID_ARGUMENT;
247
248 el->ea_value--;
249
250 if (ret)
251 *ret = el->ea_value;
252 return 0;
253 }
254
ea_refcount_store(ext2_refcount_t refcount,ea_key_t ea_key,ea_value_t ea_value)255 errcode_t ea_refcount_store(ext2_refcount_t refcount, ea_key_t ea_key,
256 ea_value_t ea_value)
257 {
258 struct ea_refcount_el *el;
259
260 /*
261 * Get the refcount element
262 */
263 el = get_refcount_el(refcount, ea_key, ea_value ? 1 : 0);
264 if (!el)
265 return ea_value ? EXT2_ET_NO_MEMORY : 0;
266 el->ea_value = ea_value;
267 return 0;
268 }
269
ext2fs_get_refcount_size(ext2_refcount_t refcount)270 size_t ext2fs_get_refcount_size(ext2_refcount_t refcount)
271 {
272 if (!refcount)
273 return 0;
274
275 return refcount->size;
276 }
277
ea_refcount_intr_begin(ext2_refcount_t refcount)278 void ea_refcount_intr_begin(ext2_refcount_t refcount)
279 {
280 refcount->cursor = 0;
281 }
282
ea_refcount_intr_next(ext2_refcount_t refcount,ea_value_t * ret)283 ea_key_t ea_refcount_intr_next(ext2_refcount_t refcount,
284 ea_value_t *ret)
285 {
286 struct ea_refcount_el *list;
287
288 while (1) {
289 if (refcount->cursor >= refcount->count)
290 return 0;
291 list = refcount->list;
292 if (list[refcount->cursor].ea_value) {
293 if (ret)
294 *ret = list[refcount->cursor].ea_value;
295 return list[refcount->cursor++].ea_key;
296 }
297 refcount->cursor++;
298 }
299 }
300
301
302 #ifdef TEST_PROGRAM
303
ea_refcount_validate(ext2_refcount_t refcount,FILE * out)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";
309
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++) {
315 if (refcount->list[i-1].ea_key >= refcount->list[i].ea_key) {
316 fprintf(out,
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);
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
main(int argc,char ** argv)372 int main(int argc, char **argv)
373 {
374 int i = 0;
375 ext2_refcount_t refcount;
376 size_t size;
377 ea_key_t ea_key;
378 ea_value_t arg;
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) {
389 com_err("ea_refcount_create", retval,
390 "while creating size %zu", size);
391 exit(1);
392 } else
393 printf("Creating refcount with size %zu\n",
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:
402 ea_key = (size_t) bcode_program[i++];
403 arg = bcode_program[i++];
404 printf("Storing ea_key %llu with value %llu\n", ea_key,
405 arg);
406 retval = ea_refcount_store(refcount, ea_key, arg);
407 if (retval)
408 com_err("ea_refcount_store", retval,
409 "while storing ea_key %llu", ea_key);
410 break;
411 case BCODE_FETCH:
412 ea_key = (size_t) bcode_program[i++];
413 retval = ea_refcount_fetch(refcount, ea_key, &arg);
414 if (retval)
415 com_err("ea_refcount_fetch", retval,
416 "while fetching ea_key %llu", ea_key);
417 else
418 printf("bcode_fetch(%llu) returns %llu\n",
419 ea_key, arg);
420 break;
421 case BCODE_INCR:
422 ea_key = (size_t) bcode_program[i++];
423 retval = ea_refcount_increment(refcount, ea_key, &arg);
424 if (retval)
425 com_err("ea_refcount_increment", retval,
426 "while incrementing ea_key %llu",
427 ea_key);
428 else
429 printf("bcode_increment(%llu) returns %llu\n",
430 ea_key, arg);
431 break;
432 case BCODE_DECR:
433 ea_key = (size_t) bcode_program[i++];
434 retval = ea_refcount_decrement(refcount, ea_key, &arg);
435 if (retval)
436 com_err("ea_refcount_decrement", retval,
437 "while decrementing ea_key %llu",
438 ea_key);
439 else
440 printf("bcode_decrement(%llu) returns %llu\n",
441 ea_key, arg);
442 break;
443 case BCODE_VALIDATE:
444 retval = ea_refcount_validate(refcount, stderr);
445 if (retval)
446 com_err("ea_refcount_validate", retval,
447 "while validating");
448 else
449 printf("Refcount validation OK.\n");
450 break;
451 case BCODE_LIST:
452 ea_refcount_intr_begin(refcount);
453 while (1) {
454 ea_key = ea_refcount_intr_next(refcount, &arg);
455 if (!ea_key)
456 break;
457 printf("\tea_key=%llu, count=%llu\n", ea_key,
458 arg);
459 }
460 break;
461 case BCODE_COLLAPSE:
462 refcount_collapse(refcount);
463 break;
464 }
465
466 }
467 }
468
469 #endif
470