Home | History | Annotate | Download | only in ext2fs
      1 /*
      2  * icount.c --- an efficient inode count abstraction
      3  *
      4  * Copyright (C) 1997 Theodore Ts'o.
      5  *
      6  * %Begin-Header%
      7  * This file may be redistributed under the terms of the GNU Library
      8  * General Public License, version 2.
      9  * %End-Header%
     10  */
     11 
     12 #if HAVE_UNISTD_H
     13 #include <unistd.h>
     14 #endif
     15 #include <string.h>
     16 #include <stdio.h>
     17 #include <sys/stat.h>
     18 #include <fcntl.h>
     19 #include <errno.h>
     20 
     21 #include "ext2_fs.h"
     22 #include "ext2fs.h"
     23 #include "tdb.h"
     24 
     25 /*
     26  * The data storage strategy used by icount relies on the observation
     27  * that most inode counts are either zero (for non-allocated inodes),
     28  * one (for most files), and only a few that are two or more
     29  * (directories and files that are linked to more than one directory).
     30  *
     31  * Also, e2fsck tends to load the icount data sequentially.
     32  *
     33  * So, we use an inode bitmap to indicate which inodes have a count of
     34  * one, and then use a sorted list to store the counts for inodes
     35  * which are greater than one.
     36  *
     37  * We also use an optional bitmap to indicate which inodes are already
     38  * in the sorted list, to speed up the use of this abstraction by
     39  * e2fsck's pass 2.  Pass 2 increments inode counts as it finds them,
     40  * so this extra bitmap avoids searching the sorted list to see if a
     41  * particular inode is on the sorted list already.
     42  */
     43 
     44 struct ext2_icount_el {
     45 	ext2_ino_t	ino;
     46 	__u32		count;
     47 };
     48 
     49 struct ext2_icount {
     50 	errcode_t		magic;
     51 	ext2fs_inode_bitmap	single;
     52 	ext2fs_inode_bitmap	multiple;
     53 	ext2_ino_t		count;
     54 	ext2_ino_t		size;
     55 	ext2_ino_t		num_inodes;
     56 	ext2_ino_t		cursor;
     57 	struct ext2_icount_el	*list;
     58 	struct ext2_icount_el	*last_lookup;
     59 	char			*tdb_fn;
     60 	TDB_CONTEXT		*tdb;
     61 };
     62 
     63 /*
     64  * We now use a 32-bit counter field because it doesn't cost us
     65  * anything extra for the in-memory data structure, due to alignment
     66  * padding.  But there's no point changing the interface if most of
     67  * the time we only care if the number is bigger than 65,000 or not.
     68  * So use the following translation function to return a 16-bit count.
     69  */
     70 #define icount_16_xlate(x) (((x) > 65500) ? 65500 : (x))
     71 
     72 void ext2fs_free_icount(ext2_icount_t icount)
     73 {
     74 	if (!icount)
     75 		return;
     76 
     77 	icount->magic = 0;
     78 	if (icount->list)
     79 		ext2fs_free_mem(&icount->list);
     80 	if (icount->single)
     81 		ext2fs_free_inode_bitmap(icount->single);
     82 	if (icount->multiple)
     83 		ext2fs_free_inode_bitmap(icount->multiple);
     84 	if (icount->tdb)
     85 		tdb_close(icount->tdb);
     86 	if (icount->tdb_fn) {
     87 		unlink(icount->tdb_fn);
     88 		free(icount->tdb_fn);
     89 	}
     90 
     91 	ext2fs_free_mem(&icount);
     92 }
     93 
     94 static errcode_t alloc_icount(ext2_filsys fs, int flags, ext2_icount_t *ret)
     95 {
     96 	ext2_icount_t	icount;
     97 	errcode_t	retval;
     98 
     99 	*ret = 0;
    100 
    101 	retval = ext2fs_get_mem(sizeof(struct ext2_icount), &icount);
    102 	if (retval)
    103 		return retval;
    104 	memset(icount, 0, sizeof(struct ext2_icount));
    105 
    106 	retval = ext2fs_allocate_inode_bitmap(fs, 0, &icount->single);
    107 	if (retval)
    108 		goto errout;
    109 
    110 	if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
    111 		retval = ext2fs_allocate_inode_bitmap(fs, 0,
    112 						      &icount->multiple);
    113 		if (retval)
    114 			goto errout;
    115 	} else
    116 		icount->multiple = 0;
    117 
    118 	icount->magic = EXT2_ET_MAGIC_ICOUNT;
    119 	icount->num_inodes = fs->super->s_inodes_count;
    120 
    121 	*ret = icount;
    122 	return 0;
    123 
    124 errout:
    125 	ext2fs_free_icount(icount);
    126 	return(retval);
    127 }
    128 
    129 struct uuid {
    130 	__u32	time_low;
    131 	__u16	time_mid;
    132 	__u16	time_hi_and_version;
    133 	__u16	clock_seq;
    134 	__u8	node[6];
    135 };
    136 
    137 static void unpack_uuid(void *in, struct uuid *uu)
    138 {
    139 	__u8	*ptr = in;
    140 	__u32	tmp;
    141 
    142 	tmp = *ptr++;
    143 	tmp = (tmp << 8) | *ptr++;
    144 	tmp = (tmp << 8) | *ptr++;
    145 	tmp = (tmp << 8) | *ptr++;
    146 	uu->time_low = tmp;
    147 
    148 	tmp = *ptr++;
    149 	tmp = (tmp << 8) | *ptr++;
    150 	uu->time_mid = tmp;
    151 
    152 	tmp = *ptr++;
    153 	tmp = (tmp << 8) | *ptr++;
    154 	uu->time_hi_and_version = tmp;
    155 
    156 	tmp = *ptr++;
    157 	tmp = (tmp << 8) | *ptr++;
    158 	uu->clock_seq = tmp;
    159 
    160 	memcpy(uu->node, ptr, 6);
    161 }
    162 
    163 static void uuid_unparse(void *uu, char *out)
    164 {
    165 	struct uuid uuid;
    166 
    167 	unpack_uuid(uu, &uuid);
    168 	sprintf(out,
    169 		"%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x",
    170 		uuid.time_low, uuid.time_mid, uuid.time_hi_and_version,
    171 		uuid.clock_seq >> 8, uuid.clock_seq & 0xFF,
    172 		uuid.node[0], uuid.node[1], uuid.node[2],
    173 		uuid.node[3], uuid.node[4], uuid.node[5]);
    174 }
    175 
    176 errcode_t ext2fs_create_icount_tdb(ext2_filsys fs, char *tdb_dir,
    177 				   int flags, ext2_icount_t *ret)
    178 {
    179 	ext2_icount_t	icount;
    180 	errcode_t	retval;
    181 	char 		*fn, uuid[40];
    182 	int		fd;
    183 
    184 	retval = alloc_icount(fs, flags,  &icount);
    185 	if (retval)
    186 		return retval;
    187 
    188 	retval = ext2fs_get_mem(strlen(tdb_dir) + 64, &fn);
    189 	if (retval)
    190 		goto errout;
    191 	uuid_unparse(fs->super->s_uuid, uuid);
    192 	sprintf(fn, "%s/%s-icount-XXXXXX", tdb_dir, uuid);
    193 	fd = mkstemp(fn);
    194 
    195 	icount->tdb_fn = fn;
    196 	icount->tdb = tdb_open(fn, 0, TDB_CLEAR_IF_FIRST,
    197 			       O_RDWR | O_CREAT | O_TRUNC, 0600);
    198 	if (icount->tdb) {
    199 		close(fd);
    200 		*ret = icount;
    201 		return 0;
    202 	}
    203 
    204 	retval = errno;
    205 	close(fd);
    206 
    207 errout:
    208 	ext2fs_free_icount(icount);
    209 	return(retval);
    210 }
    211 
    212 errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, unsigned int size,
    213 				ext2_icount_t hint, ext2_icount_t *ret)
    214 {
    215 	ext2_icount_t	icount;
    216 	errcode_t	retval;
    217 	size_t		bytes;
    218 	ext2_ino_t	i;
    219 
    220 	if (hint) {
    221 		EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
    222 		if (hint->size > size)
    223 			size = (size_t) hint->size;
    224 	}
    225 
    226 	retval = alloc_icount(fs, flags, &icount);
    227 	if (retval)
    228 		return retval;
    229 
    230 	if (size) {
    231 		icount->size = size;
    232 	} else {
    233 		/*
    234 		 * Figure out how many special case inode counts we will
    235 		 * have.  We know we will need one for each directory;
    236 		 * we also need to reserve some extra room for file links
    237 		 */
    238 		retval = ext2fs_get_num_dirs(fs, &icount->size);
    239 		if (retval)
    240 			goto errout;
    241 		icount->size += fs->super->s_inodes_count / 50;
    242 	}
    243 
    244 	bytes = (size_t) (icount->size * sizeof(struct ext2_icount_el));
    245 #if 0
    246 	printf("Icount allocated %u entries, %d bytes.\n",
    247 	       icount->size, bytes);
    248 #endif
    249 	retval = ext2fs_get_array(icount->size, sizeof(struct ext2_icount_el),
    250 			 &icount->list);
    251 	if (retval)
    252 		goto errout;
    253 	memset(icount->list, 0, bytes);
    254 
    255 	icount->count = 0;
    256 	icount->cursor = 0;
    257 
    258 	/*
    259 	 * Populate the sorted list with those entries which were
    260 	 * found in the hint icount (since those are ones which will
    261 	 * likely need to be in the sorted list this time around).
    262 	 */
    263 	if (hint) {
    264 		for (i=0; i < hint->count; i++)
    265 			icount->list[i].ino = hint->list[i].ino;
    266 		icount->count = hint->count;
    267 	}
    268 
    269 	*ret = icount;
    270 	return 0;
    271 
    272 errout:
    273 	ext2fs_free_icount(icount);
    274 	return(retval);
    275 }
    276 
    277 errcode_t ext2fs_create_icount(ext2_filsys fs, int flags,
    278 			       unsigned int size,
    279 			       ext2_icount_t *ret)
    280 {
    281 	return ext2fs_create_icount2(fs, flags, size, 0, ret);
    282 }
    283 
    284 /*
    285  * insert_icount_el() --- Insert a new entry into the sorted list at a
    286  * 	specified position.
    287  */
    288 static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
    289 					    ext2_ino_t ino, int pos)
    290 {
    291 	struct ext2_icount_el 	*el;
    292 	errcode_t		retval;
    293 	ext2_ino_t		new_size = 0;
    294 	int			num;
    295 
    296 	if (icount->last_lookup && icount->last_lookup->ino == ino)
    297 		return icount->last_lookup;
    298 
    299 	if (icount->count >= icount->size) {
    300 		if (icount->count) {
    301 			new_size = icount->list[(unsigned)icount->count-1].ino;
    302 			new_size = (ext2_ino_t) (icount->count *
    303 				((float) icount->num_inodes / new_size));
    304 		}
    305 		if (new_size < (icount->size + 100))
    306 			new_size = icount->size + 100;
    307 #if 0
    308 		printf("Reallocating icount %u entries...\n", new_size);
    309 #endif
    310 		retval = ext2fs_resize_mem((size_t) icount->size *
    311 					   sizeof(struct ext2_icount_el),
    312 					   (size_t) new_size *
    313 					   sizeof(struct ext2_icount_el),
    314 					   &icount->list);
    315 		if (retval)
    316 			return 0;
    317 		icount->size = new_size;
    318 	}
    319 	num = (int) icount->count - pos;
    320 	if (num < 0)
    321 		return 0;	/* should never happen */
    322 	if (num) {
    323 		memmove(&icount->list[pos+1], &icount->list[pos],
    324 			sizeof(struct ext2_icount_el) * num);
    325 	}
    326 	icount->count++;
    327 	el = &icount->list[pos];
    328 	el->count = 0;
    329 	el->ino = ino;
    330 	icount->last_lookup = el;
    331 	return el;
    332 }
    333 
    334 /*
    335  * get_icount_el() --- given an inode number, try to find icount
    336  * 	information in the sorted list.  If the create flag is set,
    337  * 	and we can't find an entry, create one in the sorted list.
    338  */
    339 static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
    340 					    ext2_ino_t ino, int create)
    341 {
    342 	float	range;
    343 	int	low, high, mid;
    344 	ext2_ino_t	lowval, highval;
    345 
    346 	if (!icount || !icount->list)
    347 		return 0;
    348 
    349 	if (create && ((icount->count == 0) ||
    350 		       (ino > icount->list[(unsigned)icount->count-1].ino))) {
    351 		return insert_icount_el(icount, ino, (unsigned) icount->count);
    352 	}
    353 	if (icount->count == 0)
    354 		return 0;
    355 
    356 	if (icount->cursor >= icount->count)
    357 		icount->cursor = 0;
    358 	if (ino == icount->list[icount->cursor].ino)
    359 		return &icount->list[icount->cursor++];
    360 #if 0
    361 	printf("Non-cursor get_icount_el: %u\n", ino);
    362 #endif
    363 	low = 0;
    364 	high = (int) icount->count-1;
    365 	while (low <= high) {
    366 #if 0
    367 		mid = (low+high)/2;
    368 #else
    369 		if (low == high)
    370 			mid = low;
    371 		else {
    372 			/* Interpolate for efficiency */
    373 			lowval = icount->list[low].ino;
    374 			highval = icount->list[high].ino;
    375 
    376 			if (ino < lowval)
    377 				range = 0;
    378 			else if (ino > highval)
    379 				range = 1;
    380 			else {
    381 				range = ((float) (ino - lowval)) /
    382 					(highval - lowval);
    383 				if (range > 0.9)
    384 					range = 0.9;
    385 				if (range < 0.1)
    386 					range = 0.1;
    387 			}
    388 			mid = low + ((int) (range * (high-low)));
    389 		}
    390 #endif
    391 		if (ino == icount->list[mid].ino) {
    392 			icount->cursor = mid+1;
    393 			return &icount->list[mid];
    394 		}
    395 		if (ino < icount->list[mid].ino)
    396 			high = mid-1;
    397 		else
    398 			low = mid+1;
    399 	}
    400 	/*
    401 	 * If we need to create a new entry, it should be right at
    402 	 * low (where high will be left at low-1).
    403 	 */
    404 	if (create)
    405 		return insert_icount_el(icount, ino, low);
    406 	return 0;
    407 }
    408 
    409 static errcode_t set_inode_count(ext2_icount_t icount, ext2_ino_t ino,
    410 				 __u32 count)
    411 {
    412 	struct ext2_icount_el 	*el;
    413 	TDB_DATA key, data;
    414 
    415 	if (icount->tdb) {
    416 		key.dptr = (unsigned char *) &ino;
    417 		key.dsize = sizeof(ext2_ino_t);
    418 		data.dptr = (unsigned char *) &count;
    419 		data.dsize = sizeof(__u32);
    420 		if (count) {
    421 			if (tdb_store(icount->tdb, key, data, TDB_REPLACE))
    422 				return tdb_error(icount->tdb) +
    423 					EXT2_ET_TDB_SUCCESS;
    424 		} else {
    425 			if (tdb_delete(icount->tdb, key))
    426 				return tdb_error(icount->tdb) +
    427 					EXT2_ET_TDB_SUCCESS;
    428 		}
    429 		return 0;
    430 	}
    431 
    432 	el = get_icount_el(icount, ino, 1);
    433 	if (!el)
    434 		return EXT2_ET_NO_MEMORY;
    435 
    436 	el->count = count;
    437 	return 0;
    438 }
    439 
    440 static errcode_t get_inode_count(ext2_icount_t icount, ext2_ino_t ino,
    441 				 __u32 *count)
    442 {
    443 	struct ext2_icount_el 	*el;
    444 	TDB_DATA key, data;
    445 
    446 	if (icount->tdb) {
    447 		key.dptr = (unsigned char *) &ino;
    448 		key.dsize = sizeof(ext2_ino_t);
    449 
    450 		data = tdb_fetch(icount->tdb, key);
    451 		if (data.dptr == NULL) {
    452 			*count = 0;
    453 			return tdb_error(icount->tdb) + EXT2_ET_TDB_SUCCESS;
    454 		}
    455 
    456 		*count = *((__u32 *) data.dptr);
    457 		free(data.dptr);
    458 		return 0;
    459 	}
    460 	el = get_icount_el(icount, ino, 0);
    461 	if (!el) {
    462 		*count = 0;
    463 		return ENOENT;
    464 	}
    465 
    466 	*count = el->count;
    467 	return 0;
    468 }
    469 
    470 errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
    471 {
    472 	errcode_t	ret = 0;
    473 	unsigned int	i;
    474 	const char *bad = "bad icount";
    475 
    476 	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
    477 
    478 	if (icount->count > icount->size) {
    479 		fprintf(out, "%s: count > size\n", bad);
    480 		return EXT2_ET_INVALID_ARGUMENT;
    481 	}
    482 	for (i=1; i < icount->count; i++) {
    483 		if (icount->list[i-1].ino >= icount->list[i].ino) {
    484 			fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
    485 				bad, i-1, icount->list[i-1].ino,
    486 				i, icount->list[i].ino);
    487 			ret = EXT2_ET_INVALID_ARGUMENT;
    488 		}
    489 	}
    490 	return ret;
    491 }
    492 
    493 errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ext2_ino_t ino, __u16 *ret)
    494 {
    495 	__u32	val;
    496 	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
    497 
    498 	if (!ino || (ino > icount->num_inodes))
    499 		return EXT2_ET_INVALID_ARGUMENT;
    500 
    501 	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
    502 		*ret = 1;
    503 		return 0;
    504 	}
    505 	if (icount->multiple &&
    506 	    !ext2fs_test_inode_bitmap(icount->multiple, ino)) {
    507 		*ret = 0;
    508 		return 0;
    509 	}
    510 	get_inode_count(icount, ino, &val);
    511 	*ret = icount_16_xlate(val);
    512 	return 0;
    513 }
    514 
    515 errcode_t ext2fs_icount_increment(ext2_icount_t icount, ext2_ino_t ino,
    516 				  __u16 *ret)
    517 {
    518 	__u32			curr_value;
    519 
    520 	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
    521 
    522 	if (!ino || (ino > icount->num_inodes))
    523 		return EXT2_ET_INVALID_ARGUMENT;
    524 
    525 	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
    526 		/*
    527 		 * If the existing count is 1, then we know there is
    528 		 * no entry in the list.
    529 		 */
    530 		if (set_inode_count(icount, ino, 2))
    531 			return EXT2_ET_NO_MEMORY;
    532 		curr_value = 2;
    533 		ext2fs_unmark_inode_bitmap(icount->single, ino);
    534 	} else if (icount->multiple) {
    535 		/*
    536 		 * The count is either zero or greater than 1; if the
    537 		 * inode is set in icount->multiple, then there should
    538 		 * be an entry in the list, so we need to fix it.
    539 		 */
    540 		if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
    541 			get_inode_count(icount, ino, &curr_value);
    542 			curr_value++;
    543 			if (set_inode_count(icount, ino, curr_value))
    544 				return EXT2_ET_NO_MEMORY;
    545 		} else {
    546 			/*
    547 			 * The count was zero; mark the single bitmap
    548 			 * and return.
    549 			 */
    550 			ext2fs_mark_inode_bitmap(icount->single, ino);
    551 			if (ret)
    552 				*ret = 1;
    553 			return 0;
    554 		}
    555 	} else {
    556 		/*
    557 		 * The count is either zero or greater than 1; try to
    558 		 * find an entry in the list to determine which.
    559 		 */
    560 		get_inode_count(icount, ino, &curr_value);
    561 		curr_value++;
    562 		if (set_inode_count(icount, ino, curr_value))
    563 			return EXT2_ET_NO_MEMORY;
    564 	}
    565 	if (icount->multiple)
    566 		ext2fs_mark_inode_bitmap(icount->multiple, ino);
    567 	if (ret)
    568 		*ret = icount_16_xlate(curr_value);
    569 	return 0;
    570 }
    571 
    572 errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ext2_ino_t ino,
    573 				  __u16 *ret)
    574 {
    575 	__u32			curr_value;
    576 
    577 	if (!ino || (ino > icount->num_inodes))
    578 		return EXT2_ET_INVALID_ARGUMENT;
    579 
    580 	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
    581 
    582 	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
    583 		ext2fs_unmark_inode_bitmap(icount->single, ino);
    584 		if (icount->multiple)
    585 			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
    586 		else {
    587 			set_inode_count(icount, ino, 0);
    588 		}
    589 		if (ret)
    590 			*ret = 0;
    591 		return 0;
    592 	}
    593 
    594 	if (icount->multiple &&
    595 	    !ext2fs_test_inode_bitmap(icount->multiple, ino))
    596 		return EXT2_ET_INVALID_ARGUMENT;
    597 
    598 	get_inode_count(icount, ino, &curr_value);
    599 	if (!curr_value)
    600 		return EXT2_ET_INVALID_ARGUMENT;
    601 	curr_value--;
    602 	if (set_inode_count(icount, ino, curr_value))
    603 		return EXT2_ET_NO_MEMORY;
    604 
    605 	if (curr_value == 1)
    606 		ext2fs_mark_inode_bitmap(icount->single, ino);
    607 	if ((curr_value == 0) && icount->multiple)
    608 		ext2fs_unmark_inode_bitmap(icount->multiple, ino);
    609 
    610 	if (ret)
    611 		*ret = icount_16_xlate(curr_value);
    612 	return 0;
    613 }
    614 
    615 errcode_t ext2fs_icount_store(ext2_icount_t icount, ext2_ino_t ino,
    616 			      __u16 count)
    617 {
    618 	if (!ino || (ino > icount->num_inodes))
    619 		return EXT2_ET_INVALID_ARGUMENT;
    620 
    621 	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
    622 
    623 	if (count == 1) {
    624 		ext2fs_mark_inode_bitmap(icount->single, ino);
    625 		if (icount->multiple)
    626 			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
    627 		return 0;
    628 	}
    629 	if (count == 0) {
    630 		ext2fs_unmark_inode_bitmap(icount->single, ino);
    631 		if (icount->multiple) {
    632 			/*
    633 			 * If the icount->multiple bitmap is enabled,
    634 			 * we can just clear both bitmaps and we're done
    635 			 */
    636 			ext2fs_unmark_inode_bitmap(icount->multiple, ino);
    637 		} else
    638 			set_inode_count(icount, ino, 0);
    639 		return 0;
    640 	}
    641 
    642 	if (set_inode_count(icount, ino, count))
    643 		return EXT2_ET_NO_MEMORY;
    644 	ext2fs_unmark_inode_bitmap(icount->single, ino);
    645 	if (icount->multiple)
    646 		ext2fs_mark_inode_bitmap(icount->multiple, ino);
    647 	return 0;
    648 }
    649 
    650 ext2_ino_t ext2fs_get_icount_size(ext2_icount_t icount)
    651 {
    652 	if (!icount || icount->magic != EXT2_ET_MAGIC_ICOUNT)
    653 		return 0;
    654 
    655 	return icount->size;
    656 }
    657 
    658 #ifdef DEBUG
    659 
    660 ext2_filsys	test_fs;
    661 ext2_icount_t	icount;
    662 
    663 #define EXIT		0x00
    664 #define FETCH		0x01
    665 #define STORE		0x02
    666 #define INCREMENT	0x03
    667 #define DECREMENT	0x04
    668 
    669 struct test_program {
    670 	int		cmd;
    671 	ext2_ino_t	ino;
    672 	__u16		arg;
    673 	__u16		expected;
    674 };
    675 
    676 struct test_program prog[] = {
    677 	{ STORE, 42, 42, 42 },
    678 	{ STORE, 1,  1, 1 },
    679 	{ STORE, 2,  2, 2 },
    680 	{ STORE, 3,  3, 3 },
    681 	{ STORE, 10, 1, 1 },
    682 	{ STORE, 42, 0, 0 },
    683 	{ INCREMENT, 5, 0, 1 },
    684 	{ INCREMENT, 5, 0, 2 },
    685 	{ INCREMENT, 5, 0, 3 },
    686 	{ INCREMENT, 5, 0, 4 },
    687 	{ DECREMENT, 5, 0, 3 },
    688 	{ DECREMENT, 5, 0, 2 },
    689 	{ DECREMENT, 5, 0, 1 },
    690 	{ DECREMENT, 5, 0, 0 },
    691 	{ FETCH, 10, 0, 1 },
    692 	{ FETCH, 1, 0, 1 },
    693 	{ FETCH, 2, 0, 2 },
    694 	{ FETCH, 3, 0, 3 },
    695 	{ INCREMENT, 1, 0, 2 },
    696 	{ DECREMENT, 2, 0, 1 },
    697 	{ DECREMENT, 2, 0, 0 },
    698 	{ FETCH, 12, 0, 0 },
    699 	{ EXIT, 0, 0, 0 }
    700 };
    701 
    702 struct test_program extended[] = {
    703 	{ STORE, 1,  1, 1 },
    704 	{ STORE, 2,  2, 2 },
    705 	{ STORE, 3,  3, 3 },
    706 	{ STORE, 4,  4, 4 },
    707 	{ STORE, 5,  5, 5 },
    708 	{ STORE, 6,  1, 1 },
    709 	{ STORE, 7,  2, 2 },
    710 	{ STORE, 8,  3, 3 },
    711 	{ STORE, 9,  4, 4 },
    712 	{ STORE, 10, 5, 5 },
    713 	{ STORE, 11, 1, 1 },
    714 	{ STORE, 12, 2, 2 },
    715 	{ STORE, 13, 3, 3 },
    716 	{ STORE, 14, 4, 4 },
    717 	{ STORE, 15, 5, 5 },
    718 	{ STORE, 16, 1, 1 },
    719 	{ STORE, 17, 2, 2 },
    720 	{ STORE, 18, 3, 3 },
    721 	{ STORE, 19, 4, 4 },
    722 	{ STORE, 20, 5, 5 },
    723 	{ STORE, 21, 1, 1 },
    724 	{ STORE, 22, 2, 2 },
    725 	{ STORE, 23, 3, 3 },
    726 	{ STORE, 24, 4, 4 },
    727 	{ STORE, 25, 5, 5 },
    728 	{ STORE, 26, 1, 1 },
    729 	{ STORE, 27, 2, 2 },
    730 	{ STORE, 28, 3, 3 },
    731 	{ STORE, 29, 4, 4 },
    732 	{ STORE, 30, 5, 5 },
    733 	{ EXIT, 0, 0, 0 }
    734 };
    735 
    736 /*
    737  * Setup the variables for doing the inode scan test.
    738  */
    739 static void setup(void)
    740 {
    741 	errcode_t	retval;
    742 	struct ext2_super_block param;
    743 
    744 	initialize_ext2_error_table();
    745 
    746 	memset(&param, 0, sizeof(param));
    747 	param.s_blocks_count = 12000;
    748 
    749 	retval = ext2fs_initialize("test fs", 0, &param,
    750 				   test_io_manager, &test_fs);
    751 	if (retval) {
    752 		com_err("setup", retval,
    753 			"while initializing filesystem");
    754 		exit(1);
    755 	}
    756 	retval = ext2fs_allocate_tables(test_fs);
    757 	if (retval) {
    758 		com_err("setup", retval,
    759 			"while allocating tables for test filesystem");
    760 		exit(1);
    761 	}
    762 }
    763 
    764 int run_test(int flags, int size, char *dir, struct test_program *prog)
    765 {
    766 	errcode_t	retval;
    767 	ext2_icount_t	icount;
    768 	struct test_program *pc;
    769 	__u16		result;
    770 	int		problem = 0;
    771 
    772 	if (dir) {
    773 		retval = ext2fs_create_icount_tdb(test_fs, dir,
    774 						  flags, &icount);
    775 		if (retval) {
    776 			com_err("run_test", retval,
    777 				"while creating icount using tdb");
    778 			exit(1);
    779 		}
    780 	} else {
    781 		retval = ext2fs_create_icount2(test_fs, flags, size, 0,
    782 					       &icount);
    783 		if (retval) {
    784 			com_err("run_test", retval, "while creating icount");
    785 			exit(1);
    786 		}
    787 	}
    788 	for (pc = prog; pc->cmd != EXIT; pc++) {
    789 		switch (pc->cmd) {
    790 		case FETCH:
    791 			printf("icount_fetch(%u) = ", pc->ino);
    792 			break;
    793 		case STORE:
    794 			retval = ext2fs_icount_store(icount, pc->ino, pc->arg);
    795 			if (retval) {
    796 				com_err("run_test", retval,
    797 					"while calling icount_store");
    798 				exit(1);
    799 			}
    800 			printf("icount_store(%u, %u) = ", pc->ino, pc->arg);
    801 			break;
    802 		case INCREMENT:
    803 			retval = ext2fs_icount_increment(icount, pc->ino, 0);
    804 			if (retval) {
    805 				com_err("run_test", retval,
    806 					"while calling icount_increment");
    807 				exit(1);
    808 			}
    809 			printf("icount_increment(%u) = ", pc->ino);
    810 			break;
    811 		case DECREMENT:
    812 			retval = ext2fs_icount_decrement(icount, pc->ino, 0);
    813 			if (retval) {
    814 				com_err("run_test", retval,
    815 					"while calling icount_decrement");
    816 				exit(1);
    817 			}
    818 			printf("icount_decrement(%u) = ", pc->ino);
    819 			break;
    820 		}
    821 		retval = ext2fs_icount_fetch(icount, pc->ino, &result);
    822 		if (retval) {
    823 			com_err("run_test", retval,
    824 				"while calling icount_fetch");
    825 			exit(1);
    826 		}
    827 		printf("%u (%s)\n", result, (result == pc->expected) ?
    828 		       "OK" : "NOT OK");
    829 		if (result != pc->expected)
    830 			problem++;
    831 	}
    832 	printf("icount size is %u\n", ext2fs_get_icount_size(icount));
    833 	retval = ext2fs_icount_validate(icount, stdout);
    834 	if (retval) {
    835 		com_err("run_test", retval, "while calling icount_validate");
    836 		exit(1);
    837 	}
    838 	ext2fs_free_icount(icount);
    839 	return problem;
    840 }
    841 
    842 
    843 int main(int argc, char **argv)
    844 {
    845 	int failed = 0;
    846 
    847 	setup();
    848 	printf("Standard icount run:\n");
    849 	failed += run_test(0, 0, 0, prog);
    850 	printf("\nMultiple bitmap test:\n");
    851 	failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, 0, prog);
    852 	printf("\nResizing icount:\n");
    853 	failed += run_test(0, 3, 0, extended);
    854 	printf("\nStandard icount run with tdb:\n");
    855 	failed += run_test(0, 0, ".", prog);
    856 	printf("\nMultiple bitmap test with tdb:\n");
    857 	failed += run_test(EXT2_ICOUNT_OPT_INCREMENT, 0, ".", prog);
    858 	if (failed)
    859 		printf("FAILED!\n");
    860 	return failed;
    861 }
    862 #endif
    863