Home | History | Annotate | Download | only in resize
      1 /*
      2  * extent.c --- ext2 extent abstraction
      3  *
      4  * This abstraction is used to provide a compact way of representing a
      5  * translation table, for moving multiple contiguous ranges (extents)
      6  * of blocks or inodes.
      7  *
      8  * Copyright (C) 1997, 1998 by Theodore Ts'o and
      9  * 	PowerQuest, Inc.
     10  *
     11  * Copyright (C) 1999, 2000 by Theosore Ts'o
     12  *
     13  * %Begin-Header%
     14  * This file may be redistributed under the terms of the GNU Public
     15  * License.
     16  * %End-Header%
     17  */
     18 
     19 #include "resize2fs.h"
     20 
     21 struct ext2_extent_entry {
     22 	__u64	old_loc, new_loc;
     23 	__u64	size;
     24 };
     25 
     26 struct _ext2_extent {
     27 	struct ext2_extent_entry *list;
     28 	__u64	cursor;
     29 	__u64	size;
     30 	__u64	num;
     31 	__u64	sorted;
     32 };
     33 
     34 /*
     35  * Create an extent table
     36  */
     37 errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, __u64 size)
     38 {
     39 	ext2_extent	extent;
     40 	errcode_t	retval;
     41 
     42 	retval = ext2fs_get_mem(sizeof(struct _ext2_extent), &extent);
     43 	if (retval)
     44 		return retval;
     45 	memset(extent, 0, sizeof(struct _ext2_extent));
     46 
     47 	extent->size = size ? size : 50;
     48 	extent->cursor = 0;
     49 	extent->num = 0;
     50 	extent->sorted = 1;
     51 
     52 	retval = ext2fs_get_array(sizeof(struct ext2_extent_entry),
     53 				extent->size, &extent->list);
     54 	if (retval) {
     55 		ext2fs_free_mem(&extent);
     56 		return retval;
     57 	}
     58 	memset(extent->list, 0,
     59 	       sizeof(struct ext2_extent_entry) * extent->size);
     60 	*ret_extent = extent;
     61 	return 0;
     62 }
     63 
     64 /*
     65  * Free an extent table
     66  */
     67 void ext2fs_free_extent_table(ext2_extent extent)
     68 {
     69 	if (extent->list)
     70 		ext2fs_free_mem(&extent->list);
     71 	extent->list = 0;
     72 	extent->size = 0;
     73 	extent->num = 0;
     74 	ext2fs_free_mem(&extent);
     75 }
     76 
     77 /*
     78  * Add an entry to the extent table
     79  */
     80 errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u64 old_loc, __u64 new_loc)
     81 {
     82 	struct	ext2_extent_entry	*ent;
     83 	errcode_t			retval;
     84 	__u64				newsize;
     85 	__u64				curr;
     86 
     87 	if (extent->num >= extent->size) {
     88 		newsize = extent->size + 100;
     89 		retval = ext2fs_resize_mem(sizeof(struct ext2_extent_entry) *
     90 					   extent->size,
     91 					   sizeof(struct ext2_extent_entry) *
     92 					   newsize, &extent->list);
     93 		if (retval)
     94 			return retval;
     95 		extent->size = newsize;
     96 	}
     97 	curr = extent->num;
     98 	ent = extent->list + curr;
     99 	if (curr) {
    100 		/*
    101 		 * Check to see if this can be coalesced with the last
    102 		 * extent
    103 		 */
    104 		ent--;
    105 		if ((ent->old_loc + ent->size == old_loc) &&
    106 		    (ent->new_loc + ent->size == new_loc)) {
    107 			ent->size++;
    108 			return 0;
    109 		}
    110 		/*
    111 		 * Now see if we're going to ruin the sorting
    112 		 */
    113 		if (ent->old_loc + ent->size > old_loc)
    114 			extent->sorted = 0;
    115 		ent++;
    116 	}
    117 	ent->old_loc = old_loc;
    118 	ent->new_loc = new_loc;
    119 	ent->size = 1;
    120 	extent->num++;
    121 	return 0;
    122 }
    123 
    124 /*
    125  * Helper function for qsort
    126  */
    127 static EXT2_QSORT_TYPE extent_cmp(const void *a, const void *b)
    128 {
    129 	const struct ext2_extent_entry *db_a;
    130 	const struct ext2_extent_entry *db_b;
    131 
    132 	db_a = (const struct ext2_extent_entry *) a;
    133 	db_b = (const struct ext2_extent_entry *) b;
    134 
    135 	return (db_a->old_loc - db_b->old_loc);
    136 }
    137 
    138 /*
    139  * Given an inode map and inode number, look up the old inode number
    140  * and return the new inode number.
    141  */
    142 __u64 ext2fs_extent_translate(ext2_extent extent, __u64 old_loc)
    143 {
    144 	__s64	low, high, mid;
    145 	__u64	lowval, highval;
    146 	float	range;
    147 
    148 	if (!extent->sorted) {
    149 		qsort(extent->list, extent->num,
    150 		      sizeof(struct ext2_extent_entry), extent_cmp);
    151 		extent->sorted = 1;
    152 	}
    153 	low = 0;
    154 	high = extent->num-1;
    155 	while (low <= high) {
    156 #if 0
    157 		mid = (low+high)/2;
    158 #else
    159 		if (low == high)
    160 			mid = low;
    161 		else {
    162 			/* Interpolate for efficiency */
    163 			lowval = extent->list[low].old_loc;
    164 			highval = extent->list[high].old_loc;
    165 
    166 			if (old_loc < lowval)
    167 				range = 0;
    168 			else if (old_loc > highval)
    169 				range = 1;
    170 			else {
    171 				range = ((float) (old_loc - lowval)) /
    172 					(highval - lowval);
    173 				if (range > 0.9)
    174 					range = 0.9;
    175 				if (range < 0.1)
    176 					range = 0.1;
    177 			}
    178 			mid = low + ((__u64) (range * (high-low)));
    179 		}
    180 #endif
    181 		if ((old_loc >= extent->list[mid].old_loc) &&
    182 		    (old_loc < extent->list[mid].old_loc + extent->list[mid].size))
    183 			return (extent->list[mid].new_loc +
    184 				(old_loc - extent->list[mid].old_loc));
    185 		if (old_loc < extent->list[mid].old_loc)
    186 			high = mid-1;
    187 		else
    188 			low = mid+1;
    189 	}
    190 	return 0;
    191 }
    192 
    193 /*
    194  * For debugging only
    195  */
    196 void ext2fs_extent_dump(ext2_extent extent, FILE *out)
    197 {
    198 	__u64	i;
    199 	struct ext2_extent_entry *ent;
    200 
    201 	fputs(_("# Extent dump:\n"), out);
    202 	fprintf(out, _("#\tNum=%llu, Size=%llu, Cursor=%llu, Sorted=%llu\n"),
    203 	       extent->num, extent->size, extent->cursor, extent->sorted);
    204 	for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
    205 		fprintf(out, "#\t\t %llu -> %llu (%llu)\n", ent->old_loc,
    206 			ent->new_loc, ent->size);
    207 	}
    208 }
    209 
    210 /*
    211  * Iterate over the contents of the extent table
    212  */
    213 errcode_t ext2fs_iterate_extent(ext2_extent extent, __u64 *old_loc,
    214 				__u64 *new_loc, __u64 *size)
    215 {
    216 	struct ext2_extent_entry *ent;
    217 
    218 	if (!old_loc) {
    219 		extent->cursor = 0;
    220 		return 0;
    221 	}
    222 
    223 	if (extent->cursor >= extent->num) {
    224 		*old_loc = 0;
    225 		*new_loc = 0;
    226 		*size = 0;
    227 		return 0;
    228 	}
    229 
    230 	ent = extent->list + extent->cursor++;
    231 
    232 	*old_loc = ent->old_loc;
    233 	*new_loc = ent->new_loc;
    234 	*size = ent->size;
    235 	return 0;
    236 }
    237 
    238 
    239 
    240 
    241