extent.c revision e0ed7404719a9ddd2ba427a80db5365c8bad18c0 
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	__u64	old_loc, new_loc;
23	__u64	size;
24};
25
26struct _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 */
37errcode_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 */
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, __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 */
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__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 */
196void 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 */
213errcode_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