]>
git.ipfire.org Git - thirdparty/e2fsprogs.git/blob - e2fsck/ea_refcount.c
4 * Copyright (C) 2001 Theodore Ts'o. This file may be
5 * redistributed under the terms of the GNU Public License.
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.
27 struct ea_refcount_el
{
36 struct ea_refcount_el
*list
;
39 void ea_refcount_free(ext2_refcount_t refcount
)
45 ext2fs_free_mem(&refcount
->list
);
46 ext2fs_free_mem(&refcount
);
49 errcode_t
ea_refcount_create(int size
, ext2_refcount_t
*ret
)
51 ext2_refcount_t refcount
;
55 retval
= ext2fs_get_mem(sizeof(struct ea_refcount
), &refcount
);
58 memset(refcount
, 0, sizeof(struct ea_refcount
));
62 refcount
->size
= size
;
63 bytes
= (size_t) (size
* sizeof(struct ea_refcount_el
));
65 printf("Refcount allocated %d entries, %d bytes.\n",
66 refcount
->size
, bytes
);
68 retval
= ext2fs_get_mem(bytes
, &refcount
->list
);
71 memset(refcount
->list
, 0, bytes
);
80 ea_refcount_free(refcount
);
85 * collapse_refcount() --- go through the refcount array, and get rid
86 * of any count == zero entries
88 static void refcount_collapse(ext2_refcount_t refcount
)
91 struct ea_refcount_el
*list
;
93 list
= refcount
->list
;
94 for (i
= 0, j
= 0; i
< refcount
->count
; i
++) {
95 if (list
[i
].ea_count
) {
101 #if defined(DEBUG) || defined(TEST_PROGRAM)
102 printf("Refcount_collapse: size was %d, now %d\n",
110 * insert_refcount_el() --- Insert a new entry into the sorted list at a
111 * specified position.
113 static struct ea_refcount_el
*insert_refcount_el(ext2_refcount_t refcount
,
116 struct ea_refcount_el
*el
;
121 if (refcount
->count
>= refcount
->size
) {
122 new_size
= refcount
->size
+ 100;
124 printf("Reallocating refcount %d entries...\n", new_size
);
126 retval
= ext2fs_resize_mem((size_t) refcount
->size
*
127 sizeof(struct ea_refcount_el
),
129 sizeof(struct ea_refcount_el
),
133 refcount
->size
= new_size
;
135 num
= (int) refcount
->count
- pos
;
137 return 0; /* should never happen */
139 memmove(&refcount
->list
[pos
+1], &refcount
->list
[pos
],
140 sizeof(struct ea_refcount_el
) * num
);
143 el
= &refcount
->list
[pos
];
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.
155 static struct ea_refcount_el
*get_refcount_el(ext2_refcount_t refcount
,
156 blk_t blk
, int create
)
160 blk_t lowval
, highval
;
162 if (!refcount
|| !refcount
->list
)
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
);
172 return insert_refcount_el(refcount
, blk
,
173 (unsigned) refcount
->count
);
175 if (refcount
->count
== 0)
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
++];
183 printf("Non-cursor get_refcount_el: %u\n", blk
);
185 while (low
<= high
) {
192 /* Interpolate for efficiency */
193 lowval
= refcount
->list
[low
].ea_blk
;
194 highval
= refcount
->list
[high
].ea_blk
;
198 else if (blk
> highval
)
201 range
= ((float) (blk
- lowval
)) /
208 mid
= low
+ ((int) (range
* (high
-low
)));
211 if (blk
== refcount
->list
[mid
].ea_blk
) {
212 refcount
->cursor
= mid
+1;
213 return &refcount
->list
[mid
];
215 if (blk
< refcount
->list
[mid
].ea_blk
)
221 * If we need to create a new entry, it should be right at
222 * low (where high will be left at low-1).
225 if (refcount
->count
>= refcount
->size
) {
226 refcount_collapse(refcount
);
227 if (refcount
->count
< refcount
->size
)
230 return insert_refcount_el(refcount
, blk
, low
);
235 errcode_t
ea_refcount_fetch(ext2_refcount_t refcount
, blk_t blk
,
238 struct ea_refcount_el
*el
;
240 el
= get_refcount_el(refcount
, blk
, 0);
249 errcode_t
ea_refcount_increment(ext2_refcount_t refcount
, blk_t blk
, int *ret
)
251 struct ea_refcount_el
*el
;
253 el
= get_refcount_el(refcount
, blk
, 1);
255 return EXT2_ET_NO_MEMORY
;
263 errcode_t
ea_refcount_decrement(ext2_refcount_t refcount
, blk_t blk
, int *ret
)
265 struct ea_refcount_el
*el
;
267 el
= get_refcount_el(refcount
, blk
, 0);
268 if (!el
|| el
->ea_count
== 0)
269 return EXT2_ET_INVALID_ARGUMENT
;
278 errcode_t
ea_refcount_store(ext2_refcount_t refcount
, blk_t blk
, int count
)
280 struct ea_refcount_el
*el
;
283 * Get the refcount element
285 el
= get_refcount_el(refcount
, blk
, count
? 1 : 0);
287 return count
? EXT2_ET_NO_MEMORY
: 0;
288 el
->ea_count
= count
;
292 blk_t
ext2fs_get_refcount_size(ext2_refcount_t refcount
)
297 return refcount
->size
;
300 void ea_refcount_intr_begin(ext2_refcount_t refcount
)
302 refcount
->cursor
= 0;
306 blk_t
ea_refcount_intr_next(ext2_refcount_t refcount
,
309 struct ea_refcount_el
*list
;
312 if (refcount
->cursor
>= refcount
->count
)
314 list
= refcount
->list
;
315 if (list
[refcount
->cursor
].ea_count
) {
317 *ret
= list
[refcount
->cursor
].ea_count
;
318 return list
[refcount
->cursor
++].ea_blk
;
327 errcode_t
ea_refcount_validate(ext2_refcount_t refcount
, FILE *out
)
331 const char *bad
= "bad refcount";
333 if (refcount
->count
> refcount
->size
) {
334 fprintf(out
, "%s: count > size\n", bad
);
335 return EXT2_ET_INVALID_ARGUMENT
;
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
;
349 #define BCODE_CREATE 1
351 #define BCODE_STORE 3
354 #define BCODE_FETCH 6
355 #define BCODE_VALIDATE 7
357 #define BCODE_COLLAPSE 9
359 int bcode_program
[] = {
394 int main(int argc
, char **argv
)
397 ext2_refcount_t refcount
;
403 switch (bcode_program
[i
++]) {
407 size
= bcode_program
[i
++];
408 retval
= ea_refcount_create(size
, &refcount
);
410 com_err("ea_refcount_create",
414 printf("Creating refcount with size %d\n",
418 ea_refcount_free(refcount
);
420 printf("Freeing refcount\n");
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
);
428 com_err("ea_refcount_store", retval
, "");
431 blk
= (blk_t
) bcode_program
[i
++];
432 retval
= ea_refcount_fetch(refcount
, blk
, &arg
);
434 com_err("ea_refcount_fetch", retval
, "");
436 printf("bcode_fetch(%u) returns %d\n",
440 blk
= (blk_t
) bcode_program
[i
++];
441 retval
= ea_refcount_increment(refcount
, blk
,
444 com_err("ea_refcount_increment", retval
,
447 printf("bcode_increment(%u) returns %d\n",
451 blk
= (blk_t
) bcode_program
[i
++];
452 retval
= ea_refcount_decrement(refcount
, blk
,
455 com_err("ea_refcount_decrement", retval
,
456 "while decrementing blk %u", blk
);
458 printf("bcode_decrement(%u) returns %d\n",
462 retval
= ea_refcount_validate(refcount
, stderr
);
464 com_err("ea_refcount_validate",
467 printf("Refcount validation OK.\n");
470 ea_refcount_intr_begin(refcount
);
472 blk
= ea_refcount_intr_next(refcount
,
476 printf("\tblk=%u, count=%d\n", blk
,
481 refcount_collapse(refcount
);