/*
* ea_refcount.c
- *
+ *
* Copyright (C) 2001 Theodore Ts'o. This file may be
* redistributed under the terms of the GNU Public License.
*/
+#include "config.h"
#if HAVE_UNISTD_H
#include <unistd.h>
#endif
#include <string.h>
#include <stdio.h>
+#ifdef TEST_PROGRAM
+#undef ENABLE_NLS
+#endif
#include "e2fsck.h"
/*
* follows. We keep a sorted array of first EA blocks and its
* reference counts. Once the refcount has dropped to zero, it is
* removed from the array to save memory space. Once the EA block is
- * checked, its bit is set in the block_ea_map bitmap.
+ * checked, its bit is set in the block_ea_map bitmap.
*/
struct ea_refcount_el {
- blk_t ea_blk;
- int ea_count;
+ /* ea_key could either be an inode number or block number. */
+ ea_key_t ea_key;
+ ea_value_t ea_value;
};
struct ea_refcount {
- blk_t count;
- blk_t size;
- blk_t cursor;
+ size_t count;
+ size_t size;
+ size_t cursor;
struct ea_refcount_el *list;
};
ext2fs_free_mem(&refcount);
}
-errcode_t ea_refcount_create(int size, ext2_refcount_t *ret)
+errcode_t ea_refcount_create(size_t size, ext2_refcount_t *ret)
{
ext2_refcount_t refcount;
errcode_t retval;
size_t bytes;
- retval = ext2fs_get_mem(sizeof(struct ea_refcount), &refcount);
+ retval = ext2fs_get_memzero(sizeof(struct ea_refcount), &refcount);
if (retval)
return retval;
- memset(refcount, 0, sizeof(struct ea_refcount));
if (!size)
size = 500;
refcount->size = size;
- bytes = (size_t) (size * sizeof(struct ea_refcount_el));
+ bytes = size * sizeof(struct ea_refcount_el);
#ifdef DEBUG
- printf("Refcount allocated %d entries, %d bytes.\n",
+ printf("Refcount allocated %zu entries, %zu bytes.\n",
refcount->size, bytes);
#endif
- retval = ext2fs_get_mem(bytes, &refcount->list);
+ retval = ext2fs_get_memzero(bytes, &refcount->list);
if (retval)
goto errout;
- memset(refcount->list, 0, bytes);
refcount->count = 0;
refcount->cursor = 0;
list = refcount->list;
for (i = 0, j = 0; i < refcount->count; i++) {
- if (list[i].ea_count) {
+ if (list[i].ea_value) {
if (i != j)
list[j] = list[i];
j++;
}
}
#if defined(DEBUG) || defined(TEST_PROGRAM)
- printf("Refcount_collapse: size was %d, now %d\n",
+ printf("Refcount_collapse: size was %zu, now %d\n",
refcount->count, j);
#endif
refcount->count = j;
* specified position.
*/
static struct ea_refcount_el *insert_refcount_el(ext2_refcount_t refcount,
- blk_t blk, int pos)
+ ea_key_t ea_key, int pos)
{
struct ea_refcount_el *el;
errcode_t retval;
- blk_t new_size = 0;
+ size_t new_size = 0;
int num;
if (refcount->count >= refcount->size) {
new_size = refcount->size + 100;
#ifdef DEBUG
printf("Reallocating refcount %d entries...\n", new_size);
-#endif
+#endif
retval = ext2fs_resize_mem((size_t) refcount->size *
sizeof(struct ea_refcount_el),
(size_t) new_size *
}
refcount->count++;
el = &refcount->list[pos];
- el->ea_count = 0;
- el->ea_blk = blk;
+ el->ea_key = ea_key;
+ el->ea_value = 0;
return el;
}
* and we can't find an entry, create one in the sorted list.
*/
static struct ea_refcount_el *get_refcount_el(ext2_refcount_t refcount,
- blk_t blk, int create)
+ ea_key_t ea_key, int create)
{
- float range;
int low, high, mid;
- blk_t lowval, highval;
if (!refcount || !refcount->list)
return 0;
low = 0;
high = (int) refcount->count-1;
if (create && ((refcount->count == 0) ||
- (blk > refcount->list[high].ea_blk))) {
+ (ea_key > refcount->list[high].ea_key))) {
if (refcount->count >= refcount->size)
refcount_collapse(refcount);
- return insert_refcount_el(refcount, blk,
+ return insert_refcount_el(refcount, ea_key,
(unsigned) refcount->count);
}
if (refcount->count == 0)
return 0;
-
+
if (refcount->cursor >= refcount->count)
refcount->cursor = 0;
- if (blk == refcount->list[refcount->cursor].ea_blk)
+ if (ea_key == refcount->list[refcount->cursor].ea_key)
return &refcount->list[refcount->cursor++];
#ifdef DEBUG
- printf("Non-cursor get_refcount_el: %u\n", blk);
+ printf("Non-cursor get_refcount_el: %u\n", ea_key);
#endif
while (low <= high) {
-#if 0
mid = (low+high)/2;
-#else
- if (low == high)
- mid = low;
- else {
- /* Interpolate for efficiency */
- lowval = refcount->list[low].ea_blk;
- highval = refcount->list[high].ea_blk;
-
- if (blk < lowval)
- range = 0;
- else if (blk > highval)
- range = 1;
- else
- range = ((float) (blk - lowval)) /
- (highval - lowval);
- mid = low + ((int) (range * (high-low)));
- }
-#endif
- if (blk == refcount->list[mid].ea_blk) {
+ if (ea_key == refcount->list[mid].ea_key) {
refcount->cursor = mid+1;
return &refcount->list[mid];
}
- if (blk < refcount->list[mid].ea_blk)
+ if (ea_key < refcount->list[mid].ea_key)
high = mid-1;
else
low = mid+1;
if (refcount->count < refcount->size)
goto retry;
}
- return insert_refcount_el(refcount, blk, low);
+ return insert_refcount_el(refcount, ea_key, low);
}
return 0;
}
-errcode_t ea_refcount_fetch(ext2_refcount_t refcount, blk_t blk,
- int *ret)
+errcode_t ea_refcount_fetch(ext2_refcount_t refcount, ea_key_t ea_key,
+ ea_value_t *ret)
{
struct ea_refcount_el *el;
-
- el = get_refcount_el(refcount, blk, 0);
+
+ el = get_refcount_el(refcount, ea_key, 0);
if (!el) {
*ret = 0;
return 0;
}
- *ret = el->ea_count;
+ *ret = el->ea_value;
return 0;
}
-errcode_t ea_refcount_increment(ext2_refcount_t refcount, blk_t blk, int *ret)
+errcode_t ea_refcount_increment(ext2_refcount_t refcount, ea_key_t ea_key,
+ ea_value_t *ret)
{
struct ea_refcount_el *el;
- el = get_refcount_el(refcount, blk, 1);
+ el = get_refcount_el(refcount, ea_key, 1);
if (!el)
return EXT2_ET_NO_MEMORY;
- el->ea_count++;
+ el->ea_value++;
if (ret)
- *ret = el->ea_count;
+ *ret = el->ea_value;
return 0;
}
-errcode_t ea_refcount_decrement(ext2_refcount_t refcount, blk_t blk, int *ret)
+errcode_t ea_refcount_decrement(ext2_refcount_t refcount, ea_key_t ea_key,
+ ea_value_t *ret)
{
struct ea_refcount_el *el;
- el = get_refcount_el(refcount, blk, 0);
- if (!el || el->ea_count == 0)
+ el = get_refcount_el(refcount, ea_key, 0);
+ if (!el || el->ea_value == 0)
return EXT2_ET_INVALID_ARGUMENT;
- el->ea_count--;
+ el->ea_value--;
if (ret)
- *ret = el->ea_count;
+ *ret = el->ea_value;
return 0;
}
-errcode_t ea_refcount_store(ext2_refcount_t refcount, blk_t blk, int count)
+errcode_t ea_refcount_store(ext2_refcount_t refcount, ea_key_t ea_key,
+ ea_value_t ea_value)
{
struct ea_refcount_el *el;
/*
* Get the refcount element
*/
- el = get_refcount_el(refcount, blk, count ? 1 : 0);
+ el = get_refcount_el(refcount, ea_key, ea_value ? 1 : 0);
if (!el)
- return count ? EXT2_ET_NO_MEMORY : 0;
- el->ea_count = count;
+ return ea_value ? EXT2_ET_NO_MEMORY : 0;
+ el->ea_value = ea_value;
return 0;
}
-blk_t ext2fs_get_refcount_size(ext2_refcount_t refcount)
+size_t ext2fs_get_refcount_size(ext2_refcount_t refcount)
{
if (!refcount)
return 0;
refcount->cursor = 0;
}
-
-blk_t ea_refcount_intr_next(ext2_refcount_t refcount,
- int *ret)
+ea_key_t ea_refcount_intr_next(ext2_refcount_t refcount,
+ ea_value_t *ret)
{
struct ea_refcount_el *list;
-
+
while (1) {
if (refcount->cursor >= refcount->count)
return 0;
list = refcount->list;
- if (list[refcount->cursor].ea_count) {
+ if (list[refcount->cursor].ea_value) {
if (ret)
- *ret = list[refcount->cursor].ea_count;
- return list[refcount->cursor++].ea_blk;
+ *ret = list[refcount->cursor].ea_value;
+ return list[refcount->cursor++].ea_key;
}
refcount->cursor++;
}
errcode_t ret = 0;
int i;
const char *bad = "bad refcount";
-
+
if (refcount->count > refcount->size) {
fprintf(out, "%s: count > size\n", bad);
return EXT2_ET_INVALID_ARGUMENT;
}
for (i=1; i < refcount->count; i++) {
- if (refcount->list[i-1].ea_blk >= refcount->list[i].ea_blk) {
- fprintf(out, "%s: list[%d].blk=%u, list[%d].blk=%u\n",
- bad, i-1, refcount->list[i-1].ea_blk,
- i, refcount->list[i].ea_blk);
+ if (refcount->list[i-1].ea_key >= refcount->list[i].ea_key) {
+ fprintf(out,
+ "%s: list[%d].ea_key=%llu, list[%d].ea_key=%llu\n",
+ bad, i-1,
+ (unsigned long long) refcount->list[i-1].ea_key,
+ i,
+ (unsigned long long) refcount->list[i].ea_key);
ret = EXT2_ET_INVALID_ARGUMENT;
}
}
{
int i = 0;
ext2_refcount_t refcount;
- int size, arg;
- blk_t blk;
+ size_t size;
+ ea_key_t ea_key;
+ ea_value_t arg;
errcode_t retval;
while (1) {
size = bcode_program[i++];
retval = ea_refcount_create(size, &refcount);
if (retval) {
- com_err("ea_refcount_create",
- retval, "");
+ com_err("ea_refcount_create", retval,
+ "while creating size %zu", size);
exit(1);
} else
- printf("Creating refcount with size %d\n",
+ printf("Creating refcount with size %zu\n",
size);
break;
case BCODE_FREE:
printf("Freeing refcount\n");
break;
case BCODE_STORE:
- blk = (blk_t) bcode_program[i++];
+ ea_key = (size_t) bcode_program[i++];
arg = bcode_program[i++];
- retval = ea_refcount_store(refcount, blk, arg);
- printf("Storing blk %u with value %d\n", blk, arg);
+ printf("Storing ea_key %llu with value %llu\n",
+ (unsigned long long) ea_key,
+ (unsigned long long) arg);
+ retval = ea_refcount_store(refcount, ea_key, arg);
if (retval)
- com_err("ea_refcount_store", retval, "");
+ com_err("ea_refcount_store", retval,
+ "while storing ea_key %llu",
+ (unsigned long long) ea_key);
break;
case BCODE_FETCH:
- blk = (blk_t) bcode_program[i++];
- retval = ea_refcount_fetch(refcount, blk, &arg);
+ ea_key = (size_t) bcode_program[i++];
+ retval = ea_refcount_fetch(refcount, ea_key, &arg);
if (retval)
- com_err("ea_refcount_fetch", retval, "");
+ com_err("ea_refcount_fetch", retval,
+ "while fetching ea_key %llu",
+ (unsigned long long) ea_key);
else
- printf("bcode_fetch(%u) returns %d\n",
- blk, arg);
+ printf("bcode_fetch(%llu) returns %llu\n",
+ (unsigned long long) ea_key,
+ (unsigned long long) arg);
break;
case BCODE_INCR:
- blk = (blk_t) bcode_program[i++];
- retval = ea_refcount_increment(refcount, blk,
- &arg);
+ ea_key = (size_t) bcode_program[i++];
+ retval = ea_refcount_increment(refcount, ea_key, &arg);
if (retval)
com_err("ea_refcount_increment", retval,
- "");
+ "while incrementing ea_key %llu",
+ (unsigned long long) ea_key);
else
- printf("bcode_increment(%u) returns %d\n",
- blk, arg);
+ printf("bcode_increment(%llu) returns %llu\n",
+ (unsigned long long) ea_key,
+ (unsigned long long) arg);
break;
case BCODE_DECR:
- blk = (blk_t) bcode_program[i++];
- retval = ea_refcount_decrement(refcount, blk,
- &arg);
+ ea_key = (size_t) bcode_program[i++];
+ retval = ea_refcount_decrement(refcount, ea_key, &arg);
if (retval)
com_err("ea_refcount_decrement", retval,
- "while decrementing blk %u", blk);
+ "while decrementing ea_key %llu",
+ (unsigned long long) ea_key);
else
- printf("bcode_decrement(%u) returns %d\n",
- blk, arg);
+ printf("bcode_decrement(%llu) returns %llu\n",
+ (unsigned long long) ea_key,
+ (unsigned long long) arg);
break;
case BCODE_VALIDATE:
retval = ea_refcount_validate(refcount, stderr);
if (retval)
- com_err("ea_refcount_validate",
- retval, "");
+ com_err("ea_refcount_validate", retval,
+ "while validating");
else
printf("Refcount validation OK.\n");
break;
case BCODE_LIST:
ea_refcount_intr_begin(refcount);
while (1) {
- blk = ea_refcount_intr_next(refcount,
- &arg);
- if (!blk)
+ ea_key = ea_refcount_intr_next(refcount, &arg);
+ if (!ea_key)
break;
- printf("\tblk=%u, count=%d\n", blk,
- arg);
+ printf("\tea_key=%llu, count=%llu\n",
+ (unsigned long long) ea_key,
+ (unsigned long long) arg);
}
break;
case BCODE_COLLAPSE:
refcount_collapse(refcount);
break;
}
-
+
}
}