[linux-2.6-block.git] / lib / generic-radix-tree.c


#include <linux/atomic.h>
#include <linux/export.h>
#include <linux/generic-radix-tree.h>
#include <linux/gfp.h>
#include <linux/kmemleak.h>

/*
 * Returns pointer to the specified byte @offset within @radix, or NULL if not
 * allocated
 */
void *__genradix_ptr(struct __genradix *radix, size_t offset)
{
	return __genradix_ptr_inlined(radix, offset);
}
EXPORT_SYMBOL(__genradix_ptr);

/*
 * Returns pointer to the specified byte @offset within @radix, allocating it if
 * necessary - newly allocated slots are always zeroed out:
 */
void *__genradix_ptr_alloc(struct __genradix *radix, size_t offset,
			   struct genradix_node **preallocated,
			   gfp_t gfp_mask)
{
	struct genradix_root *v = READ_ONCE(radix->root);
	struct genradix_node *n, *new_node = NULL;
	unsigned level;

	if (preallocated)
		swap(new_node, *preallocated);

	/* Increase tree depth if necessary: */
	while (1) {
		struct genradix_root *r = v, *new_root;

		n	= genradix_root_to_node(r);
		level	= genradix_root_to_depth(r);

		if (n && ilog2(offset) < genradix_depth_shift(level))
			break;

		if (!new_node) {
			new_node = genradix_alloc_node(gfp_mask);
			if (!new_node)
				return NULL;
		}

		new_node->children[0] = n;
		new_root = ((struct genradix_root *)
			    ((unsigned long) new_node | (n ? level + 1 : 0)));

		if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
			v = new_root;
			new_node = NULL;
		} else {
			new_node->children[0] = NULL;
		}
	}

	while (level--) {
		struct genradix_node **p =
			&n->children[offset >> genradix_depth_shift(level)];
		offset &= genradix_depth_size(level) - 1;

		n = READ_ONCE(*p);
		if (!n) {
			if (!new_node) {
				new_node = genradix_alloc_node(gfp_mask);
				if (!new_node)
					return NULL;
			}

			if (!(n = cmpxchg_release(p, NULL, new_node)))
				swap(n, new_node);
		}
	}

	if (new_node)
		genradix_free_node(new_node);

	return &n->data[offset];
}
EXPORT_SYMBOL(__genradix_ptr_alloc);

void *__genradix_iter_peek(struct genradix_iter *iter,
			   struct __genradix *radix,
			   size_t objs_per_page)
{
	struct genradix_root *r;
	struct genradix_node *n;
	unsigned level, i;

	if (iter->offset == SIZE_MAX)
		return NULL;

restart:
	r = READ_ONCE(radix->root);
	if (!r)
		return NULL;

	n	= genradix_root_to_node(r);
	level	= genradix_root_to_depth(r);

	if (ilog2(iter->offset) >= genradix_depth_shift(level))
		return NULL;

	while (level) {
		level--;

		i = (iter->offset >> genradix_depth_shift(level)) &
			(GENRADIX_ARY - 1);

		while (!n->children[i]) {
			size_t objs_per_ptr = genradix_depth_size(level);

			if (iter->offset + objs_per_ptr < iter->offset) {
				iter->offset	= SIZE_MAX;
				iter->pos	= SIZE_MAX;
				return NULL;
			}

			i++;
			iter->offset = round_down(iter->offset + objs_per_ptr,
						  objs_per_ptr);
			iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) *
				objs_per_page;
			if (i == GENRADIX_ARY)
				goto restart;
		}

		n = n->children[i];
	}

	return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)];
}
EXPORT_SYMBOL(__genradix_iter_peek);

void *__genradix_iter_peek_prev(struct genradix_iter *iter,
				struct __genradix *radix,
				size_t objs_per_page,
				size_t obj_size_plus_page_remainder)
{
	struct genradix_root *r;
	struct genradix_node *n;
	unsigned level, i;

	if (iter->offset == SIZE_MAX)
		return NULL;

restart:
	r = READ_ONCE(radix->root);
	if (!r)
		return NULL;

	n	= genradix_root_to_node(r);
	level	= genradix_root_to_depth(r);

	if (ilog2(iter->offset) >= genradix_depth_shift(level)) {
		iter->offset = genradix_depth_size(level);
		iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page;

		iter->offset -= obj_size_plus_page_remainder;
		iter->pos--;
	}

	while (level) {
		level--;

		i = (iter->offset >> genradix_depth_shift(level)) &
			(GENRADIX_ARY - 1);

		while (!n->children[i]) {
			size_t objs_per_ptr = genradix_depth_size(level);

			iter->offset = round_down(iter->offset, objs_per_ptr);
			iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page;

			if (!iter->offset)
				return NULL;

			iter->offset -= obj_size_plus_page_remainder;
			iter->pos--;

			if (!i)
				goto restart;
			--i;
		}

		n = n->children[i];
	}

	return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)];
}
EXPORT_SYMBOL(__genradix_iter_peek_prev);

static void genradix_free_recurse(struct genradix_node *n, unsigned level)
{
	if (level) {
		unsigned i;

		for (i = 0; i < GENRADIX_ARY; i++)
			if (n->children[i])
				genradix_free_recurse(n->children[i], level - 1);
	}

	genradix_free_node(n);
}

int __genradix_prealloc(struct __genradix *radix, size_t size,
			gfp_t gfp_mask)
{
	size_t offset;

	for (offset = 0; offset < size; offset += GENRADIX_NODE_SIZE)
		if (!__genradix_ptr_alloc(radix, offset, NULL, gfp_mask))
			return -ENOMEM;

	return 0;
}
EXPORT_SYMBOL(__genradix_prealloc);

void __genradix_free(struct __genradix *radix)
{
	struct genradix_root *r = xchg(&radix->root, NULL);

	genradix_free_recurse(genradix_root_to_node(r),
			      genradix_root_to_depth(r));
}
EXPORT_SYMBOL(__genradix_free);
Commit	Line	Data
ba20ba2e	1
73badee4	2	#include <linux/atomic.h>
ba20ba2e KO	3	#include <linux/export.h>
	4	#include <linux/generic-radix-tree.h>
	5	#include <linux/gfp.h>
3c52b0af	6	#include <linux/kmemleak.h>
ba20ba2e	7
ba20ba2e KO	8	/*
	9	* Returns pointer to the specified byte @offset within @radix, or NULL if not
	10	* allocated
	11	*/
	12	void __genradix_ptr(struct __genradix radix, size_t offset)
	13	{
f6594633	14	return __genradix_ptr_inlined(radix, offset);
ba20ba2e KO	15	}
	16	EXPORT_SYMBOL(__genradix_ptr);
	17
	18	/*
	19	* Returns pointer to the specified byte @offset within @radix, allocating it if
	20	* necessary - newly allocated slots are always zeroed out:
	21	*/
	22	void __genradix_ptr_alloc(struct __genradix radix, size_t offset,
b3f9da79	23	struct genradix_node **preallocated,
ba20ba2e KO	24	gfp_t gfp_mask)
	25	{
	26	struct genradix_root *v = READ_ONCE(radix->root);
	27	struct genradix_node n, new_node = NULL;
	28	unsigned level;
	29
b3f9da79 KO	30	if (preallocated)
	31	swap(new_node, *preallocated);
	32
ba20ba2e KO	33	/* Increase tree depth if necessary: */
	34	while (1) {
	35	struct genradix_root r = v, new_root;
	36
	37	n = genradix_root_to_node(r);
	38	level = genradix_root_to_depth(r);
	39
	40	if (n && ilog2(offset) < genradix_depth_shift(level))
	41	break;
	42
	43	if (!new_node) {
3c52b0af	44	new_node = genradix_alloc_node(gfp_mask);
ba20ba2e KO	45	if (!new_node)
	46	return NULL;
	47	}
	48
	49	new_node->children[0] = n;
	50	new_root = ((struct genradix_root *)
	51	((unsigned long) new_node \| (n ? level + 1 : 0)));
	52
	53	if ((v = cmpxchg_release(&radix->root, r, new_root)) == r) {
	54	v = new_root;
	55	new_node = NULL;
b2f11c6f KO	56	} else {
b2f11c6f KO	57	new_node->children[0] = NULL;
ba20ba2e KO	58	}
	59	}
	60
	61	while (level--) {
	62	struct genradix_node **p =
	63	&n->children[offset >> genradix_depth_shift(level)];
	64	offset &= genradix_depth_size(level) - 1;
	65
	66	n = READ_ONCE(*p);
	67	if (!n) {
	68	if (!new_node) {
3c52b0af	69	new_node = genradix_alloc_node(gfp_mask);
ba20ba2e KO	70	if (!new_node)
	71	return NULL;
	72	}
	73
	74	if (!(n = cmpxchg_release(p, NULL, new_node)))
	75	swap(n, new_node);
	76	}
	77	}
	78
	79	if (new_node)
3c52b0af	80	genradix_free_node(new_node);
ba20ba2e KO	81
	82	return &n->data[offset];
	83	}
	84	EXPORT_SYMBOL(__genradix_ptr_alloc);
	85
	86	void __genradix_iter_peek(struct genradix_iter iter,
	87	struct __genradix *radix,
	88	size_t objs_per_page)
	89	{
	90	struct genradix_root *r;
	91	struct genradix_node *n;
	92	unsigned level, i;
9492261f KO	93
	94	if (iter->offset == SIZE_MAX)
	95	return NULL;
	96
ba20ba2e KO	97	restart:
	98	r = READ_ONCE(radix->root);
	99	if (!r)
	100	return NULL;
	101
	102	n = genradix_root_to_node(r);
	103	level = genradix_root_to_depth(r);
	104
	105	if (ilog2(iter->offset) >= genradix_depth_shift(level))
	106	return NULL;
	107
	108	while (level) {
	109	level--;
	110
	111	i = (iter->offset >> genradix_depth_shift(level)) &
	112	(GENRADIX_ARY - 1);
	113
	114	while (!n->children[i]) {
9492261f KO	115	size_t objs_per_ptr = genradix_depth_size(level);
	116
	117	if (iter->offset + objs_per_ptr < iter->offset) {
	118	iter->offset = SIZE_MAX;
	119	iter->pos = SIZE_MAX;
	120	return NULL;
	121	}
	122
ba20ba2e	123	i++;
9492261f KO	124	iter->offset = round_down(iter->offset + objs_per_ptr,
9492261f KO	125	objs_per_ptr);
3a319a24	126	iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) *
ba20ba2e KO	127	objs_per_page;
	128	if (i == GENRADIX_ARY)
	129	goto restart;
	130	}
	131
	132	n = n->children[i];
	133	}
	134
3a319a24	135	return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)];
ba20ba2e KO	136	}
	137	EXPORT_SYMBOL(__genradix_iter_peek);
	138
73badee4 KO	139	void __genradix_iter_peek_prev(struct genradix_iter iter,
	140	struct __genradix *radix,
	141	size_t objs_per_page,
	142	size_t obj_size_plus_page_remainder)
	143	{
	144	struct genradix_root *r;
	145	struct genradix_node *n;
	146	unsigned level, i;
	147
	148	if (iter->offset == SIZE_MAX)
	149	return NULL;
	150
	151	restart:
	152	r = READ_ONCE(radix->root);
	153	if (!r)
	154	return NULL;
	155
	156	n = genradix_root_to_node(r);
	157	level = genradix_root_to_depth(r);
	158
	159	if (ilog2(iter->offset) >= genradix_depth_shift(level)) {
	160	iter->offset = genradix_depth_size(level);
3a319a24	161	iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page;
73badee4 KO	162
	163	iter->offset -= obj_size_plus_page_remainder;
	164	iter->pos--;
	165	}
	166
	167	while (level) {
	168	level--;
	169
	170	i = (iter->offset >> genradix_depth_shift(level)) &
	171	(GENRADIX_ARY - 1);
	172
	173	while (!n->children[i]) {
	174	size_t objs_per_ptr = genradix_depth_size(level);
	175
	176	iter->offset = round_down(iter->offset, objs_per_ptr);
3a319a24	177	iter->pos = (iter->offset >> GENRADIX_NODE_SHIFT) * objs_per_page;
73badee4 KO	178
	179	if (!iter->offset)
	180	return NULL;
	181
	182	iter->offset -= obj_size_plus_page_remainder;
	183	iter->pos--;
	184
	185	if (!i)
	186	goto restart;
	187	--i;
	188	}
	189
	190	n = n->children[i];
	191	}
	192
3a319a24	193	return &n->data[iter->offset & (GENRADIX_NODE_SIZE - 1)];
73badee4 KO	194	}
	195	EXPORT_SYMBOL(__genradix_iter_peek_prev);
	196
ba20ba2e KO	197	static void genradix_free_recurse(struct genradix_node *n, unsigned level)
	198	{
	199	if (level) {
	200	unsigned i;
	201
	202	for (i = 0; i < GENRADIX_ARY; i++)
	203	if (n->children[i])
	204	genradix_free_recurse(n->children[i], level - 1);
	205	}
	206
3c52b0af	207	genradix_free_node(n);
ba20ba2e KO	208	}
	209
	210	int __genradix_prealloc(struct __genradix *radix, size_t size,
	211	gfp_t gfp_mask)
	212	{
	213	size_t offset;
	214
3a319a24	215	for (offset = 0; offset < size; offset += GENRADIX_NODE_SIZE)
b3f9da79	216	if (!__genradix_ptr_alloc(radix, offset, NULL, gfp_mask))
ba20ba2e KO	217	return -ENOMEM;
	218
	219	return 0;
	220	}
	221	EXPORT_SYMBOL(__genradix_prealloc);
	222
	223	void __genradix_free(struct __genradix *radix)
	224	{
	225	struct genradix_root *r = xchg(&radix->root, NULL);
	226
	227	genradix_free_recurse(genradix_root_to_node(r),
	228	genradix_root_to_depth(r));
	229	}
	230	EXPORT_SYMBOL(__genradix_free);