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