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 "config.h"
20#include "resize2fs.h"
21
22struct ext2_extent_entry {
23	__u64	old_loc, new_loc;
24	__u64	size;
25};
26
27struct _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 */
38errcode_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 */
68void 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 */
81errcode_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 */
128static 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 */
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 */
197void 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 */
214errcode_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