extent.c revision 19dacda2b02bb08c0ffb649f84526b249c749279 
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
21struct ext2_extent_entry {
22	__u32	old_loc, new_loc;
23	int	size;
24};
25
26struct _ext2_extent {
27	struct ext2_extent_entry *list;
28	int	cursor;
29	int	size;
30	int	num;
31	int	sorted;
32};
33
34/*
35 * Create an extent table
36 */
37errcode_t ext2fs_create_extent_table(ext2_extent *ret_extent, int 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 */
67void 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 */
80errcode_t ext2fs_add_extent_entry(ext2_extent extent, __u32 old_loc, __u32 new_loc)
81{
82	struct	ext2_extent_entry	*ent;
83	errcode_t			retval;
84	int				newsize;
85	int				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 */
127static 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__u32 ext2fs_extent_translate(ext2_extent extent, __u32 old_loc)
143{
144	int	low, high, mid;
145	__u32	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			mid = low + ((int) (range * (high-low)));
174		}
175#endif
176		if ((old_loc >= extent->list[mid].old_loc) &&
177		    (old_loc < extent->list[mid].old_loc + extent->list[mid].size))
178			return (extent->list[mid].new_loc +
179				(old_loc - extent->list[mid].old_loc));
180		if (old_loc < extent->list[mid].old_loc)
181			high = mid-1;
182		else
183			low = mid+1;
184	}
185	return 0;
186}
187
188/*
189 * For debugging only
190 */
191void ext2fs_extent_dump(ext2_extent extent, FILE *out)
192{
193	int	i;
194	struct ext2_extent_entry *ent;
195
196	fputs(_("# Extent dump:\n"), out);
197	fprintf(out, _("#\tNum=%d, Size=%d, Cursor=%d, Sorted=%d\n"),
198	       extent->num, extent->size, extent->cursor, extent->sorted);
199	for (i=0, ent=extent->list; i < extent->num; i++, ent++) {
200		fprintf(out, _("#\t\t %u -> %u (%d)\n"), ent->old_loc,
201			ent->new_loc, ent->size);
202	}
203}
204
205/*
206 * Iterate over the contents of the extent table
207 */
208errcode_t ext2fs_iterate_extent(ext2_extent extent, __u32 *old_loc,
209				__u32 *new_loc, int *size)
210{
211	struct ext2_extent_entry *ent;
212
213	if (!old_loc) {
214		extent->cursor = 0;
215		return 0;
216	}
217
218	if (extent->cursor >= extent->num) {
219		*old_loc = 0;
220		*new_loc = 0;
221		*size = 0;
222		return 0;
223	}
224
225	ent = extent->list + extent->cursor++;
226
227	*old_loc = ent->old_loc;
228	*new_loc = ent->new_loc;
229	*size = ent->size;
230	return 0;
231}
232
233
234
235
236