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