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