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 if (range > 0.9)
203 range = 0.9;
204 if (range < 0.1)
205 range = 0.1;
206 }
207 mid = low + ((int) (range * (high-low)));
208 }
209 #endif
210 if (blk == refcount->list[mid].ea_blk) {
211 refcount->cursor = mid+1;
212 return &refcount->list[mid];
213 }
214 if (blk < refcount->list[mid].ea_blk)
215 high = mid-1;
216 else
217 low = mid+1;
218 }
219 /*
220 * If we need to create a new entry, it should be right at
221 * low (where high will be left at low-1).
222 */
223 if (create) {
224 if (refcount->count >= refcount->size) {
225 refcount_collapse(refcount);
226 if (refcount->count < refcount->size)
227 goto retry;
228 }
229 return insert_refcount_el(refcount, blk, low);
230 }
231 return 0;
232 }
233
ea_refcount_fetch(ext2_refcount_t refcount,blk_t blk,int * ret)234 errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk,
235 int *ret)
236 {
237 struct ea_refcount_el *el;
238
239 el = get_refcount_el(refcount, blk, 0);
240 if (!el) {
241 *ret = 0;
242 return 0;
243 }
244 *ret = el->ea_count;
245 return 0;
246 }
247
ea_refcount_increment(ext2_refcount_t refcount,blk_t blk,int * ret)248 errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret)
249 {
250 struct ea_refcount_el *el;
251
252 el = get_refcount_el(refcount, blk, 1);
253 if (!el)
254 return EXT2_ET_NO_MEMORY;
255 el->ea_count++;
256
257 if (ret)
258 *ret = el->ea_count;
259 return 0;
260 }
261
ea_refcount_decrement(ext2_refcount_t refcount,blk_t blk,int * ret)262 errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret)
263 {
264 struct ea_refcount_el *el;
265
266 el = get_refcount_el(refcount, blk, 0);
267 if (!el || el->ea_count == 0)
268 return EXT2_ET_INVALID_ARGUMENT;
269
270 el->ea_count--;
271
272 if (ret)
273 *ret = el->ea_count;
274 return 0;
275 }
276
ea_refcount_store(ext2_refcount_t refcount,blk_t blk,int count)277 errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count)
278 {
279 struct ea_refcount_el *el;
280
281 /*
282 * Get the refcount element
283 */
284 el = get_refcount_el(refcount, blk, count ? 1 : 0);
285 if (!el)
286 return count ? EXT2_ET_NO_MEMORY : 0;
287 el->ea_count = count;
288 return 0;
289 }
290
ext2fs_get_refcount_size(ext2_refcount_t refcount)291 blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount)
292 {
293 if (!refcount)
294 return 0;
295
296 return refcount->size;
297 }
298
ea_refcount_intr_begin(ext2_refcount_t refcount)299 void ea_refcount_intr_begin(ext2_refcount_t refcount)
300 {
301 refcount->cursor = 0;
302 }
303
304
ea_refcount_intr_next(ext2_refcount_t refcount,int * ret)305 blk_t ea_refcount_intr_next(ext2_refcount_t refcount,
306 int *ret)
307 {
308 struct ea_refcount_el *list;
309
310 while (1) {
311 if (refcount->cursor >= refcount->count)
312 return 0;
313 list = refcount->list;
314 if (list[refcount->cursor].ea_count) {
315 if (ret)
316 *ret = list[refcount->cursor].ea_count;
317 return list[refcount->cursor++].ea_blk;
318 }
319 refcount->cursor++;
320 }
321 }
322
323
324 #ifdef TEST_PROGRAM
325
ea_refcount_validate(ext2_refcount_t refcount,FILE * out)326 errcode_t ea_refcount_validate(ext2_refcount_t refcount, FILE *out)
327 {
328 errcode_t ret = 0;
329 int i;
330 const char *bad = "bad refcount";
331
332 if (refcount->count > refcount->size) {
333 fprintf(out, "%s: count > size\n", bad);
334 return EXT2_ET_INVALID_ARGUMENT;
335 }
336 for (i=1; i < refcount->count; i++) {
337 if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) {
338 fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n",
339 bad, i-1, refcount->list[i-1].ea_blk,
340 i, refcount->list[i].ea_blk);
341 ret = EXT2_ET_INVALID_ARGUMENT;
342 }
343 }
344 return ret;
345 }
346
347 #define BCODE_END 0
348 #define BCODE_CREATE 1
349 #define BCODE_FREE 2
350 #define BCODE_STORE 3
351 #define BCODE_INCR 4
352 #define BCODE_DECR 5
353 #define BCODE_FETCH 6
354 #define BCODE_VALIDATE 7
355 #define BCODE_LIST 8
356 #define BCODE_COLLAPSE 9
357
358 int bcode_program[] = {
359 BCODE_CREATE, 5,
360 BCODE_STORE, 3, 3,
361 BCODE_STORE, 4, 4,
362 BCODE_STORE, 1, 1,
363 BCODE_STORE, 8, 8,
364 BCODE_STORE, 2, 2,
365 BCODE_STORE, 4, 0,
366 BCODE_STORE, 2, 0,
367 BCODE_STORE, 6, 6,
368 BCODE_VALIDATE,
369 BCODE_STORE, 4, 4,
370 BCODE_STORE, 2, 2,
371 BCODE_FETCH, 1,
372 BCODE_FETCH, 2,
373 BCODE_INCR, 3,
374 BCODE_INCR, 3,
375 BCODE_DECR, 4,
376 BCODE_STORE, 4, 4,
377 BCODE_VALIDATE,
378 BCODE_STORE, 20, 20,
379 BCODE_STORE, 40, 40,
380 BCODE_STORE, 30, 30,
381 BCODE_STORE, 10, 10,
382 BCODE_DECR, 30,
383 BCODE_FETCH, 30,
384 BCODE_DECR, 2,
385 BCODE_DECR, 2,
386 BCODE_COLLAPSE,
387 BCODE_LIST,
388 BCODE_VALIDATE,
389 BCODE_FREE,
390 BCODE_END
391 };
392
main(int argc,char ** argv)393 int main(int argc, char **argv)
394 {
395 int i = 0;
396 ext2_refcount_t refcount;
397 int size, arg;
398 blk_t blk;
399 errcode_t retval;
400
401 while (1) {
402 switch (bcode_program[i++]) {
403 case BCODE_END:
404 exit(0);
405 case BCODE_CREATE:
406 size = bcode_program[i++];
407 retval = ea_refcount_create(size, &refcount);
408 if (retval) {
409 com_err("ea_refcount_create",
410 retval, "");
411 exit(1);
412 } else
413 printf("Creating refcount with size %d\n",
414 size);
415 break;
416 case BCODE_FREE:
417 ea_refcount_free(refcount);
418 refcount = 0;
419 printf("Freeing refcount\n");
420 break;
421 case BCODE_STORE:
422 blk = (blk_t) bcode_program[i++];
423 arg = bcode_program[i++];
424 retval = ea_refcount_store(refcount, blk, arg);
425 printf("Storing blk %u with value %d\n", blk, arg);
426 if (retval)
427 com_err("ea_refcount_store", retval, "");
428 break;
429 case BCODE_FETCH:
430 blk = (blk_t) bcode_program[i++];
431 retval = ea_refcount_fetch(refcount, blk, &arg);
432 if (retval)
433 com_err("ea_refcount_fetch", retval, "");
434 else
435 printf("bcode_fetch(%u) returns %d\n",
436 blk, arg);
437 break;
438 case BCODE_INCR:
439 blk = (blk_t) bcode_program[i++];
440 retval = ea_refcount_increment(refcount, blk,
441 &arg);
442 if (retval)
443 com_err("ea_refcount_increment", retval,
444 "");
445 else
446 printf("bcode_increment(%u) returns %d\n",
447 blk, arg);
448 break;
449 case BCODE_DECR:
450 blk = (blk_t) bcode_program[i++];
451 retval = ea_refcount_decrement(refcount, blk,
452 &arg);
453 if (retval)
454 com_err("ea_refcount_decrement", retval,
455 "while decrementing blk %u", blk);
456 else
457 printf("bcode_decrement(%u) returns %d\n",
458 blk, arg);
459 break;
460 case BCODE_VALIDATE:
461 retval = ea_refcount_validate(refcount, stderr);
462 if (retval)
463 com_err("ea_refcount_validate",
464 retval, "");
465 else
466 printf("Refcount validation OK.\n");
467 break;
468 case BCODE_LIST:
469 ea_refcount_intr_begin(refcount);
470 while (1) {
471 blk = ea_refcount_intr_next(refcount,
472 &arg);
473 if (!blk)
474 break;
475 printf("\tblk=%u, count=%d\n", blk,
476 arg);
477 }
478 break;
479 case BCODE_COLLAPSE:
480 refcount_collapse(refcount);
481 break;
482 }
483
484 }
485 }
486
487 #endif
488