aboutsummaryrefslogtreecommitdiff
path: root/e2fsprogs/ext2fs/icount.c
blob: 7d0d63c916d5bf93fe295dacbfcbc018c80a18e9 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
/*
 * icount.c --- an efficient inode count abstraction
 *
 * Copyright (C) 1997 Theodore Ts'o.
 *
 * %Begin-Header%
 * This file may be redistributed under the terms of the GNU Public
 * License.
 * %End-Header%
 */

#if HAVE_UNISTD_H
#include <unistd.h>
#endif
#include <string.h>
#include <stdio.h>

#include "ext2_fs.h"
#include "ext2fs.h"

/*
 * The data storage strategy used by icount relies on the observation
 * that most inode counts are either zero (for non-allocated inodes),
 * one (for most files), and only a few that are two or more
 * (directories and files that are linked to more than one directory).
 *
 * Also, e2fsck tends to load the icount data sequentially.
 *
 * So, we use an inode bitmap to indicate which inodes have a count of
 * one, and then use a sorted list to store the counts for inodes
 * which are greater than one.
 *
 * We also use an optional bitmap to indicate which inodes are already
 * in the sorted list, to speed up the use of this abstraction by
 * e2fsck's pass 2.  Pass 2 increments inode counts as it finds them,
 * so this extra bitmap avoids searching the sorted list to see if a
 * particular inode is on the sorted list already.
 */

struct ext2_icount_el {
	ext2_ino_t	ino;
	__u16	count;
};

struct ext2_icount {
	errcode_t		magic;
	ext2fs_inode_bitmap	single;
	ext2fs_inode_bitmap	multiple;
	ext2_ino_t		count;
	ext2_ino_t		size;
	ext2_ino_t		num_inodes;
	ext2_ino_t		cursor;
	struct ext2_icount_el	*list;
};

void ext2fs_free_icount(ext2_icount_t icount)
{
	if (!icount)
		return;

	icount->magic = 0;
	ext2fs_free_mem(&icount->list);
	ext2fs_free_inode_bitmap(icount->single);
	ext2fs_free_inode_bitmap(icount->multiple);
	ext2fs_free_mem(&icount);
}

errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
				ext2_icount_t hint, ext2_icount_t *ret)
{
	ext2_icount_t	icount;
	errcode_t	retval;
	size_t		bytes;
	ext2_ino_t	i;

	if (hint) {
		EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
		if (hint->size > size)
			size = (size_t) hint->size;
	}

	retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
	if (retval)
		return retval;
	memset(icount, 0, sizeof(struct ext2_icount));

	retval = ext2fs_allocate_inode_bitmap(fs, 0,
					      &icount->single);
	if (retval)
		goto errout;

	if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
		retval = ext2fs_allocate_inode_bitmap(fs, 0,
						      &icount->multiple);
		if (retval)
			goto errout;
	} else
		icount->multiple = 0;

	if (size) {
		icount->size = size;
	} else {
		/*
		 * Figure out how many special case inode counts we will
		 * have.  We know we will need one for each directory;
		 * we also need to reserve some extra room for file links
		 */
		retval = ext2fs_get_num_dirs(fs, &icount->size);
		if (retval)
			goto errout;
		icount->size += fs->super->s_inodes_count / 50;
	}

	bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
	retval = ext2fs_get_mem(bytes, &icount->list);
	if (retval)
		goto errout;
	memset(icount->list, 0, bytes);

	icount->magic = EXT2_ET_MAGIC_ICOUNT;
	icount->count = 0;
	icount->cursor = 0;
	icount->num_inodes = fs->super->s_inodes_count;

	/*
	 * Populate the sorted list with those entries which were
	 * found in the hint icount (since those are ones which will
	 * likely need to be in the sorted list this time around).
	 */
	if (hint) {
		for (i=0; i < hint->count; i++)
			icount->list[i].ino = hint->list[i].ino;
		icount->count = hint->count;
	}

	*ret = icount;
	return 0;

errout:
	ext2fs_free_icount(icount);
	return(retval);
}

errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
			       unsigned int size,
			       ext2_icount_t *ret)
{
	return ext2fs_create_icount2(fs, flags, size, 0, ret);
}

/*
 * insert_icount_el() --- Insert a new entry into the sorted list at a
 *	specified position.
 */
static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
					    ext2_ino_t ino, int pos)
{
	struct ext2_icount_el	*el;
	errcode_t		retval;
	ext2_ino_t			new_size = 0;
	int			num;

	if (icount->count >= icount->size) {
		if (icount->count) {
			new_size = icount->list[(unsigned)icount->count-1].ino;
			new_size = (ext2_ino_t) (icount->count *
				((float) icount->num_inodes / new_size));
		}
		if (new_size < (icount->size + 100))
			new_size = icount->size + 100;
		retval = ext2fs_resize_mem((size_t) icount->size *
					   sizeof(struct ext2_icount_el),
					   (size_t) new_size *
					   sizeof(struct ext2_icount_el),
					   &icount->list);
		if (retval)
			return 0;
		icount->size = new_size;
	}
	num = (int) icount->count - pos;
	if (num < 0)
		return 0;	/* should never happen */
	if (num) {
		memmove(&icount->list[pos+1], &icount->list[pos],
			sizeof(struct ext2_icount_el) * num);
	}
	icount->count++;
	el = &icount->list[pos];
	el->count = 0;
	el->ino = ino;
	return el;
}

/*
 * get_icount_el() --- given an inode number, try to find icount
 *	information in the sorted list.  If the create flag is set,
 *	and we can't find an entry, create one in the sorted list.
 */
static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
					    ext2_ino_t ino, int create)
{
	float	range;
	int	low, high, mid;
	ext2_ino_t	lowval, highval;

	if (!icount || !icount->list)
		return 0;

	if (create && ((icount->count == 0) ||
		       (ino > icount->list[(unsigned)icount->count-1].ino))) {
		return insert_icount_el(icount, ino, (unsigned) icount->count);
	}
	if (icount->count == 0)
		return 0;

	if (icount->cursor >= icount->count)
		icount->cursor = 0;
	if (ino == icount->list[icount->cursor].ino)
		return &icount->list[icount->cursor++];
	low = 0;
	high = (int) icount->count-1;
	while (low <= high) {
		if (low == high)
			mid = low;
		else {
			/* Interpolate for efficiency */
			lowval = icount->list[low].ino;
			highval = icount->list[high].ino;

			if (ino < lowval)
				range = 0;
			else if (ino > highval)
				range = 1;
			else
				range = ((float) (ino - lowval)) /
					(highval - lowval);
			mid = low + ((int) (range * (high-low)));
		}
		if (ino == icount->list[mid].ino) {
			icount->cursor = mid+1;
			return &icount->list[mid];
		}
		if (ino < icount->list[mid].ino)
			high = mid-1;
		else
			low = mid+1;
	}
	/*
	 * If we need to create a new entry, it should be right at
	 * low (where high will be left at low-1).
	 */
	if (create)
		return insert_icount_el(icount, ino, low);
	return 0;
}

errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
{
	errcode_t	ret = 0;
	unsigned int	i;
	const char *bad = "bad icount";

	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);

	if (icount->count > icount->size) {
		fprintf(out, "%s: count > size\n", bad);
		return EXT2_ET_INVALID_ARGUMENT;
	}
	for (i=1; i < icount->count; i++) {
		if (icount->list[i-1].ino >= icount->list[i].ino) {
			fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
				bad, i-1, icount->list[i-1].ino,
				i, icount->list[i].ino);
			ret = EXT2_ET_INVALID_ARGUMENT;
		}
	}
	return ret;
}

errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
{
	struct ext2_icount_el	*el;

	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);

	if (!ino || (ino > icount->num_inodes))
		return EXT2_ET_INVALID_ARGUMENT;

	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
		*ret = 1;
		return 0;
	}
	if (icount->multiple &&
	    !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
		*ret = 0;
		return 0;
	}
	el = get_icount_el(icount, ino, 0);
	if (!el) {
		*ret = 0;
		return 0;
	}
	*ret = el->count;
	return 0;
}

errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
				  __u16 *ret)
{
	struct ext2_icount_el	*el;

	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);

	if (!ino || (ino > icount->num_inodes))
		return EXT2_ET_INVALID_ARGUMENT;

	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
		/*
		 * If the existing count is 1, then we know there is
		 * no entry in the list.
		 */
		el = get_icount_el(icount, ino, 1);
		if (!el)
			return EXT2_ET_NO_MEMORY;
		ext2fs_unmark_inode_bitmap(icount->single, ino);
		el->count = 2;
	} else if (icount->multiple) {
		/*
		 * The count is either zero or greater than 1; if the
		 * inode is set in icount->multiple, then there should
		 * be an entry in the list, so find it using
		 * get_icount_el().
		 */
		if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
			el = get_icount_el(icount, ino, 1);
			if (!el)
				return EXT2_ET_NO_MEMORY;
			el->count++;
		} else {
			/*
			 * The count was zero; mark the single bitmap
			 * and return.
			 */
		zero_count:
			ext2fs_mark_inode_bitmap(icount->single, ino);
			if (ret)
				*ret = 1;
			return 0;
		}
	} else {
		/*
		 * The count is either zero or greater than 1; try to
		 * find an entry in the list to determine which.
		 */
		el = get_icount_el(icount, ino, 0);
		if (!el) {
			/* No entry means the count was zero */
			goto zero_count;
		}
		el = get_icount_el(icount, ino, 1);
		if (!el)
			return EXT2_ET_NO_MEMORY;
		el->count++;
	}
	if (icount->multiple)
		ext2fs_mark_inode_bitmap(icount->multiple, ino);
	if (ret)
		*ret = el->count;
	return 0;
}

errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
				  __u16 *ret)
{
	struct ext2_icount_el	*el;

	if (!ino || (ino > icount->num_inodes))
		return EXT2_ET_INVALID_ARGUMENT;

	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);

	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
		ext2fs_unmark_inode_bitmap(icount->single, ino);
		if (icount->multiple)
			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
		else {
			el = get_icount_el(icount, ino, 0);
			if (el)
				el->count = 0;
		}
		if (ret)
			*ret = 0;
		return 0;
	}

	if (icount->multiple &&
	    !ext2fs_test_inode_bitmap(icount->multiple, ino))
		return EXT2_ET_INVALID_ARGUMENT;

	el = get_icount_el(icount, ino, 0);
	if (!el || el->count == 0)
		return EXT2_ET_INVALID_ARGUMENT;

	el->count--;
	if (el->count == 1)
		ext2fs_mark_inode_bitmap(icount->single, ino);
	if ((el->count == 0) && icount->multiple)
		ext2fs_unmark_inode_bitmap(icount->multiple, ino);

	if (ret)
		*ret = el->count;
	return 0;
}

errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
			      __u16 count)
{
	struct ext2_icount_el	*el;

	if (!ino || (ino > icount->num_inodes))
		return EXT2_ET_INVALID_ARGUMENT;

	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);

	if (count == 1) {
		ext2fs_mark_inode_bitmap(icount->single, ino);
		if (icount->multiple)
			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
		return 0;
	}
	if (count == 0) {
		ext2fs_unmark_inode_bitmap(icount->single, ino);
		if (icount->multiple) {
			/*
			 * If the icount->multiple bitmap is enabled,
			 * we can just clear both bitmaps and we're done
			 */
			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
		} else {
			el = get_icount_el(icount, ino, 0);
			if (el)
				el->count = 0;
		}
		return 0;
	}

	/*
	 * Get the icount element
	 */
	el = get_icount_el(icount, ino, 1);
	if (!el)
		return EXT2_ET_NO_MEMORY;
	el->count = count;
	ext2fs_unmark_inode_bitmap(icount->single, ino);
	if (icount->multiple)
		ext2fs_mark_inode_bitmap(icount->multiple, ino);
	return 0;
}

ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
{
	if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
		return 0;

	return icount->size;
}