[thirdparty/e2fsprogs.git] / lib / ext2fs / icount.c

/*
 * 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%
 */

#include <et/com_err.h>
#include <unistd.h>
#include <stdlib.h>
#include <string.h>
#include <stdio.h>
#ifdef HAVE_ERRNO_H
#include <errno.h>
#endif

#include <linux/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 {
	ino_t	ino;
	__u16	count;
};

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

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

	icount->magic = 0;
	if (icount->list)
		free(icount->list);
	if (icount->single)
		ext2fs_free_inode_bitmap(icount->single);
	if (icount->multiple)
		ext2fs_free_inode_bitmap(icount->multiple);
	free(icount);
}

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

	if (hint) {
		EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
		if (hint->size > size)
			size = hint->size;
	}
	
	icount = malloc(sizeof(struct ext2_icount));
	if (!icount)
		return ENOMEM;
	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 = icount->size * sizeof(struct ext2_icount_el);
#if 0
	printf("Icount allocated %d entries, %d bytes.\n",
	       icount->size, bytes);
#endif
	icount->list = malloc(bytes);
	if (!icount->list)
		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, 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,
					    ino_t ino, int pos)
{
	struct ext2_icount_el *el, *new_list;
	ino_t			new_size = 0;
	int			num;

	if (icount->count >= icount->size) {
		if (icount->count) {
			new_size = icount->list[icount->count-1].ino;
			new_size = icount->count * 
				((float) new_size / icount->num_inodes);
		}
		if (new_size < (icount->size + 100))
			new_size = icount->size + 100;
#if 0
		printf("Reallocating icount %d entries...\n", new_size);
#endif	
		new_list = realloc(icount->list,
			new_size * sizeof(struct ext2_icount_el));
		if (!new_list)
			return 0;
		icount->size = new_size;
		icount->list = new_list;
	}
	num = 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,
					    ino_t ino, int create)
{
	float	range;
	int	low, high, mid;
	ino_t	lowval, highval;

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

	if (create && ((icount->count == 0) ||
		       (ino > icount->list[icount->count-1].ino))) {
		return insert_icount_el(icount, ino, 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++];
#if 0
	printf("Non-cursor get_icount_el: %u\n", ino);
#endif
	low = 0;
	high = icount->count-1;
	while (low <= high) {
#if 0
		mid = (low+high)/2;
#else
		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)));
		}
#endif
		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;
	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 EINVAL;
	}
	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 = EINVAL;
		}
	}
	return ret;
}

errcode_t ext2fs_icount_fetch(ext2_icount_t icount, 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 EINVAL;

	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, 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 EINVAL;

	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 ENOMEM;
		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 ENOMEM;
			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 ENOMEM;
		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, ino_t ino,
				  __u16 *ret)
{
	struct ext2_icount_el	*el;

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

	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 EINVAL;
	
	el = get_icount_el(icount, ino, 0);
	if (!el || el->count == 0)
		return EINVAL;

	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, ino_t ino,
			      __u16 count)
{
	struct ext2_icount_el	*el;

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

	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 ENOMEM;
	el->count = count;
	ext2fs_unmark_inode_bitmap(icount->single, ino);
	if (icount->multiple)
		ext2fs_mark_inode_bitmap(icount->multiple, ino);
	return 0;
}

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

	return icount->size;
}
Commit	Line	Data
19c78dc0 TT	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 Public
	8	* License.
	9	* %End-Header%
	10	*/
	11
	12	#include <et/com_err.h>
	13	#include <unistd.h>
	14	#include <stdlib.h>
	15	#include <string.h>
	16	#include <stdio.h>
	17	#ifdef HAVE_ERRNO_H
	18	#include <errno.h>
	19	#endif
	20
	21	#include <linux/ext2_fs.h>
	22	#include "ext2fs.h"
	23
	24	/*
	25	* The data storage strategy used by icount relies on the observation
	26	* that most inode counts are either zero (for non-allocated inodes),
	27	* one (for most files), and only a few that are two or more
	28	* (directories and files that are linked to more than one directory).
	29	*
	30	* Also, e2fsck tends to load the icount data sequentially.
	31	*
	32	* So, we use an inode bitmap to indicate which inodes have a count of
	33	* one, and then use a sorted list to store the counts for inodes
	34	* which are greater than one.
	35	*
	36	* We also use an optional bitmap to indicate which inodes are already
	37	* in the sorted list, to speed up the use of this abstraction by
	38	* e2fsck's pass 2. Pass 2 increments inode counts as it finds them,
	39	* so this extra bitmap avoids searching the sorted list to see if a
	40	* particular inode is on the sorted list already.
	41	*/
	42
	43	struct ext2_icount_el {
	44	ino_t ino;
	45	__u16 count;
	46	};
	47
	48	struct ext2_icount {
	49	int magic;
	50	ext2fs_inode_bitmap single;
	51	ext2fs_inode_bitmap multiple;
	52	ino_t count;
	53	ino_t size;
	54	ino_t num_inodes;
	55	int cursor;
	56	struct ext2_icount_el *list;
	57	};
	58
	59	void ext2fs_free_icount(ext2_icount_t icount)
	60	{
	61	if (!icount)
	62	return;
	63
	64	icount->magic = 0;
65	if (icount->list)
66	free(icount->list);
67	if (icount->single)
68	ext2fs_free_inode_bitmap(icount->single);
69	if (icount->multiple)
70	ext2fs_free_inode_bitmap(icount->multiple);
71	free(icount);
72	}
73
521e3685 TT	74	errcode_t ext2fs_create_icount2(ext2_filsys fs, int flags, int size,
521e3685 TT	75	ext2_icount_t hint, ext2_icount_t *ret)
19c78dc0 TT	76	{
	77	ext2_icount_t icount;
	78	errcode_t retval;
	79	size_t bytes;
521e3685	80	int i;
19c78dc0	81
521e3685 TT	82	if (hint) {
	83	EXT2_CHECK_MAGIC(hint, EXT2_ET_MAGIC_ICOUNT);
	84	if (hint->size > size)
	85	size = hint->size;
	86	}
	87
19c78dc0 TT	88	icount = malloc(sizeof(struct ext2_icount));
	89	if (!icount)
	90	return ENOMEM;
	91	memset(icount, 0, sizeof(struct ext2_icount));
	92
	93	retval = ext2fs_allocate_inode_bitmap(fs, 0,
	94	&icount->single);
	95	if (retval)
	96	goto errout;
	97
	98	if (flags & EXT2_ICOUNT_OPT_INCREMENT) {
	99	retval = ext2fs_allocate_inode_bitmap(fs, 0,
	100	&icount->multiple);
	101	if (retval)
	102	goto errout;
	103	} else
	104	icount->multiple = 0;
	105
	106	if (size) {
	107	icount->size = size;
	108	} else {
	109	/*
	110	* Figure out how many special case inode counts we will
	111	* have. We know we will need one for each directory;
	112	* we also need to reserve some extra room for file links
	113	*/
	114	retval = ext2fs_get_num_dirs(fs, &icount->size);
	115	if (retval)
	116	goto errout;
	117	icount->size += fs->super->s_inodes_count / 50;
	118	}
	119
	120	bytes = icount->size * sizeof(struct ext2_icount_el);
	121	#if 0
	122	printf("Icount allocated %d entries, %d bytes.\n",
	123	icount->size, bytes);
	124	#endif
	125	icount->list = malloc(bytes);
	126	if (!icount->list)
	127	goto errout;
	128	memset(icount->list, 0, bytes);
	129
	130	icount->magic = EXT2_ET_MAGIC_ICOUNT;
	131	icount->count = 0;
	132	icount->cursor = 0;
	133	icount->num_inodes = fs->super->s_inodes_count;
	134
521e3685 TT	135	/*
	136	* Populate the sorted list with those entries which were
	137	* found in the hint icount (since those are ones which will
	138	* likely need to be in the sorted list this time around).
	139	*/
	140	if (hint) {
	141	for (i=0; i < hint->count; i++)
	142	icount->list[i].ino = hint->list[i].ino;
	143	icount->count = hint->count;
	144	}
19c78dc0	145
521e3685	146	*ret = icount;
19c78dc0 TT	147	return 0;
	148
	149	errout:
	150	ext2fs_free_icount(icount);
	151	return(retval);
	152	}
	153
521e3685 TT	154	errcode_t ext2fs_create_icount(ext2_filsys fs, int flags, int size,
521e3685 TT	155	ext2_icount_t *ret)
19c78dc0	156	{
521e3685	157	return ext2fs_create_icount2(fs, flags, size, 0, ret);
19c78dc0 TT	158	}
	159
	160	/*
521e3685 TT	161	* insert_icount_el() --- Insert a new entry into the sorted list at a
521e3685 TT	162	* specified position.
19c78dc0	163	*/
521e3685 TT	164	static struct ext2_icount_el *insert_icount_el(ext2_icount_t icount,
521e3685 TT	165	ino_t ino, int pos)
19c78dc0 TT	166	{
	167	struct ext2_icount_el el, new_list;
	168	ino_t new_size = 0;
521e3685	169	int num;
19c78dc0 TT	170
	171	if (icount->count >= icount->size) {
	172	if (icount->count) {
	173	new_size = icount->list[icount->count-1].ino;
	174	new_size = icount->count *
	175	((float) new_size / icount->num_inodes);
	176	}
	177	if (new_size < (icount->size + 100))
	178	new_size = icount->size + 100;
	179	#if 0
	180	printf("Reallocating icount %d entries...\n", new_size);
	181	#endif
	182	new_list = realloc(icount->list,
	183	new_size * sizeof(struct ext2_icount_el));
	184	if (!new_list)
	185	return 0;
	186	icount->size = new_size;
	187	icount->list = new_list;
	188	}
521e3685 TT	189	num = icount->count - pos;
	190	if (num < 0)
	191	return 0; /* should never happen */
	192	if (num) {
	193	memmove(&icount->list[pos+1], &icount->list[pos],
	194	sizeof(struct ext2_icount_el) * num);
	195	}
	196	icount->count++;
	197	el = &icount->list[pos];
	198	el->count = 0;
	199	el->ino = ino;
	200	return el;
	201	}
	202
	203	/*
	204	* get_icount_el() --- given an inode number, try to find icount
	205	* information in the sorted list. If the create flag is set,
	206	* and we can't find an entry, create one in the sorted list.
	207	*/
	208	static struct ext2_icount_el *get_icount_el(ext2_icount_t icount,
	209	ino_t ino, int create)
	210	{
	211	float range;
	212	int low, high, mid;
	213	ino_t lowval, highval;
	214
	215	if (!icount \|\| !icount->list)
	216	return 0;
19c78dc0	217
521e3685 TT	218	if (create && ((icount->count == 0) \|\|
	219	(ino > icount->list[icount->count-1].ino))) {
	220	return insert_icount_el(icount, ino, icount->count);
	221	}
	222	if (icount->count == 0)
	223	return 0;
	224
	225	if (icount->cursor >= icount->count)
	226	icount->cursor = 0;
	227	if (ino == icount->list[icount->cursor].ino)
	228	return &icount->list[icount->cursor++];
	229	#if 0
	230	printf("Non-cursor get_icount_el: %u\n", ino);
	231	#endif
	232	low = 0;
	233	high = icount->count-1;
	234	while (low <= high) {
	235	#if 0
	236	mid = (low+high)/2;
	237	#else
	238	if (low == high)
	239	mid = low;
	240	else {
	241	/* Interpolate for efficiency */
	242	lowval = icount->list[low].ino;
	243	highval = icount->list[high].ino;
	244
	245	if (ino < lowval)
	246	range = 0;
	247	else if (ino > highval)
	248	range = 1;
	249	else
	250	range = ((float) (ino - lowval)) /
	251	(highval - lowval);
	252	mid = low + ((int) (range * (high-low)));
	253	}
	254	#endif
	255	if (ino == icount->list[mid].ino) {
	256	icount->cursor = mid+1;
	257	return &icount->list[mid];
	258	}
	259	if (ino < icount->list[mid].ino)
	260	high = mid-1;
	261	else
	262	low = mid+1;
	263	}
19c78dc0	264	/*
521e3685 TT	265	* If we need to create a new entry, it should be right at
521e3685 TT	266	* low (where high will be left at low-1).
19c78dc0	267	*/
521e3685 TT	268	if (create)
	269	return insert_icount_el(icount, ino, low);
	270	return 0;
	271	}
	272
	273	errcode_t ext2fs_icount_validate(ext2_icount_t icount, FILE *out)
	274	{
	275	errcode_t ret = 0;
	276	int i;
	277	const char *bad = "bad icount";
	278
	279	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
	280
	281	if (icount->count > icount->size) {
	282	fprintf(out, "%s: count > size\n", bad);
	283	return EINVAL;
	284	}
	285	for (i=1; i < icount->count; i++) {
	286	if (icount->list[i-1].ino >= icount->list[i].ino) {
	287	fprintf(out, "%s: list[%d].ino=%u, list[%d].ino=%u\n",
	288	bad, i-1, icount->list[i-1].ino,
	289	i, icount->list[i].ino);
	290	ret = EINVAL;
19c78dc0	291	}
19c78dc0	292	}
521e3685	293	return ret;
19c78dc0	294	}
19c78dc0 TT	295
	296	errcode_t ext2fs_icount_fetch(ext2_icount_t icount, ino_t ino, __u16 *ret)
	297	{
	298	struct ext2_icount_el *el;
	299
	300	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
	301
521e3685 TT	302	if (!ino \|\| (ino > icount->num_inodes))
	303	return EINVAL;
	304
19c78dc0 TT	305	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
	306	*ret = 1;
	307	return 0;
	308	}
521e3685 TT	309	if (icount->multiple &&
	310	!ext2fs_test_inode_bitmap(icount->multiple, ino)) {
	311	*ret = 0;
	312	return 0;
	313	}
	314	el = get_icount_el(icount, ino, 0);
19c78dc0 TT	315	if (!el) {
	316	*ret = 0;
	317	return 0;
	318	}
	319	*ret = el->count;
	320	return 0;
	321	}
	322
	323	errcode_t ext2fs_icount_increment(ext2_icount_t icount, ino_t ino,
	324	__u16 *ret)
	325	{
	326	struct ext2_icount_el *el;
	327
	328	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
	329
521e3685 TT	330	if (!ino \|\| (ino > icount->num_inodes))
	331	return EINVAL;
	332
19c78dc0 TT	333	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
	334	/*
	335	* If the existing count is 1, then we know there is
521e3685	336	* no entry in the list.
19c78dc0	337	*/
521e3685	338	el = get_icount_el(icount, ino, 1);
19c78dc0 TT	339	if (!el)
19c78dc0 TT	340	return ENOMEM;
521e3685 TT	341	ext2fs_unmark_inode_bitmap(icount->single, ino);
521e3685 TT	342	el->count = 2;
19c78dc0 TT	343	} else if (icount->multiple) {
	344	/*
	345	* The count is either zero or greater than 1; if the
	346	* inode is set in icount->multiple, then there should
	347	* be an entry in the list, so find it using
	348	* get_icount_el().
	349	*/
	350	if (ext2fs_test_inode_bitmap(icount->multiple, ino)) {
521e3685 TT	351	el = get_icount_el(icount, ino, 1);
	352	if (!el)
	353	return ENOMEM;
	354	el->count++;
19c78dc0 TT	355	} else {
	356	/*
	357	* The count was zero; mark the single bitmap
	358	* and return.
	359	*/
	360	zero_count:
	361	ext2fs_mark_inode_bitmap(icount->single, ino);
	362	if (ret)
	363	*ret = 1;
	364	return 0;
	365	}
	366	} else {
	367	/*
	368	* The count is either zero or greater than 1; try to
	369	* find an entry in the list to determine which.
	370	*/
521e3685	371	el = get_icount_el(icount, ino, 0);
19c78dc0 TT	372	if (!el) {
	373	/* No entry means the count was zero */
	374	goto zero_count;
	375	}
521e3685	376	el = get_icount_el(icount, ino, 1);
19c78dc0 TT	377	if (!el)
19c78dc0 TT	378	return ENOMEM;
19c78dc0	379	el->count++;
521e3685	380	}
19c78dc0 TT	381	if (icount->multiple)
	382	ext2fs_mark_inode_bitmap(icount->multiple, ino);
	383	if (ret)
	384	*ret = el->count;
	385	return 0;
	386	}
	387
	388	errcode_t ext2fs_icount_decrement(ext2_icount_t icount, ino_t ino,
	389	__u16 *ret)
	390	{
	391	struct ext2_icount_el *el;
	392
521e3685 TT	393	if (!ino \|\| (ino > icount->num_inodes))
	394	return EINVAL;
	395
19c78dc0 TT	396	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
	397
	398	if (ext2fs_test_inode_bitmap(icount->single, ino)) {
	399	ext2fs_unmark_inode_bitmap(icount->single, ino);
	400	if (icount->multiple)
	401	ext2fs_unmark_inode_bitmap(icount->multiple, ino);
	402	else {
521e3685	403	el = get_icount_el(icount, ino, 0);
19c78dc0 TT	404	if (el)
	405	el->count = 0;
	406	}
	407	if (ret)
	408	*ret = 0;
	409	return 0;
	410	}
	411
521e3685 TT	412	if (icount->multiple &&
	413	!ext2fs_test_inode_bitmap(icount->multiple, ino))
	414	return EINVAL;
	415
	416	el = get_icount_el(icount, ino, 0);
	417	if (!el \|\| el->count == 0)
19c78dc0 TT	418	return EINVAL;
	419
	420	el->count--;
	421	if (el->count == 1)
	422	ext2fs_mark_inode_bitmap(icount->single, ino);
	423	if ((el->count == 0) && icount->multiple)
	424	ext2fs_unmark_inode_bitmap(icount->multiple, ino);
	425
	426	if (ret)
	427	*ret = el->count;
	428	return 0;
	429	}
	430
	431	errcode_t ext2fs_icount_store(ext2_icount_t icount, ino_t ino,
	432	__u16 count)
	433	{
	434	struct ext2_icount_el *el;
	435
521e3685 TT	436	if (!ino \|\| (ino > icount->num_inodes))
	437	return EINVAL;
	438
19c78dc0 TT	439	EXT2_CHECK_MAGIC(icount, EXT2_ET_MAGIC_ICOUNT);
	440
	441	if (count == 1) {
	442	ext2fs_mark_inode_bitmap(icount->single, ino);
	443	if (icount->multiple)
	444	ext2fs_unmark_inode_bitmap(icount->multiple, ino);
	445	return 0;
	446	}
	447	if (count == 0) {
	448	ext2fs_unmark_inode_bitmap(icount->single, ino);
	449	if (icount->multiple) {
	450	/*
	451	* If the icount->multiple bitmap is enabled,
	452	* we can just clear both bitmaps and we're done
	453	*/
	454	ext2fs_unmark_inode_bitmap(icount->multiple, ino);
	455	} else {
521e3685	456	el = get_icount_el(icount, ino, 0);
19c78dc0 TT	457	if (el)
	458	el->count = 0;
	459	}
	460	return 0;
	461	}
	462
	463	/*
	464	* Get the icount element
	465	*/
521e3685	466	el = get_icount_el(icount, ino, 1);
19c78dc0 TT	467	if (!el)
	468	return ENOMEM;
	469	el->count = count;
	470	ext2fs_unmark_inode_bitmap(icount->single, ino);
	471	if (icount->multiple)
	472	ext2fs_mark_inode_bitmap(icount->multiple, ino);
	473	return 0;
	474	}
	475
	476	ino_t ext2fs_get_icount_size(ext2_icount_t icount)
	477	{
	478	if (!icount \|\| icount->magic != EXT2_ET_MAGIC_ICOUNT)
	479	return 0;
	480
	481	return icount->size;
	482	}