diff options
Diffstat (limited to 'resize/extent.c')
| -rw-r--r-- | resize/extent.c | 244 |
1 files changed, 244 insertions, 0 deletions
diff --git a/resize/extent.c b/resize/extent.c new file mode 100644 index 0000000..82f69ca --- /dev/null +++ b/resize/extent.c @@ -0,0 +1,244 @@ +/* + * extent.c --- ext2 extent abstraction + * + * This abstraction is used to provide a compact way of representing a + * translation table, for moving multiple contiguous ranges (extents) + * of blocks or inodes. + * + * Copyright (C) 1997, 1998 by Theodore Ts'o and + * PowerQuest, Inc. + * + * Copyright (C) 1999, 2000 by Theodore Ts'o + * + * %Begin-Header% + * This file may be redistributed under the terms of the GNU Public + * License. + * %End-Header% + */ + +#include "config.h" +#include "resize2fs.h" + +struct ext2_extent_entry { + __u64 old_loc, new_loc; + __u64 size; +}; + +struct _ext2_extent { + struct ext2_extent_entry *list; + __u64 cursor; + __u64 size; + __u64 num; + __u64 sorted; +}; + +/* + * Create an extent table + */ +errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, __u64 size) +{ + ext2_extent extent; + errcode_t retval; + + retval = ext2fs_get_mem(sizeof(struct _ext2_extent), &extent); + if (retval) + return retval; + memset(extent, 0, sizeof(struct _ext2_extent)); + + extent->size = size ? size : 50; + extent->cursor = 0; + extent->num = 0; + extent->sorted = 1; + + retval = ext2fs_get_arrayzero(sizeof(struct ext2_extent_entry), + extent->size, &extent->list); + if (retval) { + ext2fs_free_mem(&extent); + return retval; + } + *ret_extent = extent; + return 0; +} + +/* + * Free an extent table + */ +void ext2fs_free_extent_table(ext2_extent extent) +{ + if (extent->list) + ext2fs_free_mem(&extent->list); + extent->list = 0; + extent->size = 0; + extent->num = 0; + ext2fs_free_mem(&extent); +} + +/* + * Add an entry to the extent table + */ +errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u64 old_loc, __u64 new_loc) +{ + struct ext2_extent_entry *ent; + errcode_t retval; + __u64 newsize; + __u64 curr; + + if (extent->num >= extent->size) { + newsize = extent->size + 100; + retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) * + extent->size, + sizeof(struct ext2_extent_entry) * + newsize, &extent->list); + if (retval) + return retval; + extent->size = newsize; + } + curr = extent->num; + ent = extent->list + curr; + if (curr) { + /* + * Check to see if this can be coalesced with the last + * extent + */ + ent--; + if ((ent->old_loc + ent->size == old_loc) && + (ent->new_loc + ent->size == new_loc)) { + ent->size++; + return 0; + } + /* + * Now see if we're going to ruin the sorting + */ + if (ent->old_loc + ent->size > old_loc) + extent->sorted = 0; + ent++; + } + ent->old_loc = old_loc; + ent->new_loc = new_loc; + ent->size = 1; + extent->num++; + return 0; +} + +/* + * Helper function for qsort + */ +static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b) +{ + const struct ext2_extent_entry *db_a; + const struct ext2_extent_entry *db_b; + + db_a = (const struct ext2_extent_entry *) a; + db_b = (const struct ext2_extent_entry *) b; + + return (db_a->old_loc - db_b->old_loc); +} + +/* + * Given an inode map and inode number, look up the old inode number + * and return the new inode number. + */ +__u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc) +{ + __s64 low, high, mid; + __u64 lowval, highval; + float range; + + if (!extent->sorted) { + qsort(extent->list, extent->num, + sizeof(struct ext2_extent_entry), extent_cmp); + extent->sorted = 1; + } + low = 0; + high = extent->num-1; + while (low <= high) { +#if 0 + mid = (low+high)/2; +#else + if (low == high) + mid = low; + else { + /* Interpolate for efficiency */ + lowval = extent->list[low].old_loc; + highval = extent->list[high].old_loc; + + if (old_loc < lowval) + range = 0; + else if (old_loc > highval) + range = 1; + else { + range = ((float) (old_loc - lowval)) / + (highval - lowval); + if (range > 0.9) + range = 0.9; + if (range < 0.1) + range = 0.1; + } + mid = low + ((__u64) (range * (high-low))); + } +#endif + if ((old_loc >= extent->list[mid].old_loc) && + (old_loc < extent->list[mid].old_loc + extent->list[mid].size)) + return (extent->list[mid].new_loc + + (old_loc - extent->list[mid].old_loc)); + if (old_loc < extent->list[mid].old_loc) + high = mid-1; + else + low = mid+1; + } + return 0; +} + +/* + * For debugging only + */ +void ext2fs_extent_dump(ext2_extent extent, FILE *out) +{ + __u64 i; + struct ext2_extent_entry *ent; + + fputs(_("# Extent dump:\n"), out); + fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"), + (unsigned long long) extent->num, + (unsigned long long) extent->size, + (unsigned long long) extent->cursor, + (unsigned long long) extent->sorted); + for (i=0, ent=extent->list; i < extent->num; i++, ent++) { + fprintf(out, "#\t\t %llu -> %llu (%llu)\n", + (unsigned long long) ent->old_loc, + (unsigned long long) ent->new_loc, + (unsigned long long) ent->size); + } +} + +/* + * Iterate over the contents of the extent table + */ +errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc, + __u64 *new_loc, __u64 *size) +{ + struct ext2_extent_entry *ent; + + if (!old_loc) { + extent->cursor = 0; + return 0; + } + + if (extent->cursor >= extent->num) { + *old_loc = 0; + *new_loc = 0; + *size = 0; + return 0; + } + + ent = extent->list + extent->cursor++; + + *old_loc = ent->old_loc; + *new_loc = ent->new_loc; + *size = ent->size; + return 0; +} + + + + |