radix-tree.c 21.5 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3
/*
 * Copyright (C) 2001 Momchil Velikov
 * Portions Copyright (C) 2001 Christoph Hellwig
4
 * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com>
Linus Torvalds's avatar
Linus Torvalds committed
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
 *
 * This program is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2, or (at
 * your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
 * General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
 */

#include <linux/errno.h>
#include <linux/init.h>
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/radix-tree.h>
#include <linux/percpu.h>
#include <linux/slab.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/gfp.h>
#include <linux/string.h>
#include <linux/bitops.h>


#ifdef __KERNEL__
Nick Piggin's avatar
Nick Piggin committed
36
#define RADIX_TREE_MAP_SHIFT	(CONFIG_BASE_SMALL ? 4 : 6)
Linus Torvalds's avatar
Linus Torvalds committed
37 38 39 40 41 42 43 44 45 46 47 48 49
#else
#define RADIX_TREE_MAP_SHIFT	3	/* For more stressful testing */
#endif

#define RADIX_TREE_MAP_SIZE	(1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK	(RADIX_TREE_MAP_SIZE-1)

#define RADIX_TREE_TAG_LONGS	\
	((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)

struct radix_tree_node {
	unsigned int	count;
	void		*slots[RADIX_TREE_MAP_SIZE];
50
	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
Linus Torvalds's avatar
Linus Torvalds committed
51 52 53
};

struct radix_tree_path {
54
	struct radix_tree_node *node;
Linus Torvalds's avatar
Linus Torvalds committed
55 56 57 58 59 60
	int offset;
};

#define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))
#define RADIX_TREE_MAX_PATH (RADIX_TREE_INDEX_BITS/RADIX_TREE_MAP_SHIFT + 2)

61
static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly;
Linus Torvalds's avatar
Linus Torvalds committed
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76

/*
 * Radix tree node cache.
 */
static kmem_cache_t *radix_tree_node_cachep;

/*
 * Per-cpu pool of preloaded nodes
 */
struct radix_tree_preload {
	int nr;
	struct radix_tree_node *nodes[RADIX_TREE_MAX_PATH];
};
DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };

77 78 79 80 81
static inline gfp_t root_gfp_mask(struct radix_tree_root *root)
{
	return root->gfp_mask & __GFP_BITS_MASK;
}

Linus Torvalds's avatar
Linus Torvalds committed
82 83 84 85 86 87 88 89
/*
 * This assumes that the caller has performed appropriate preallocation, and
 * that the caller has pinned this thread of control to the current CPU.
 */
static struct radix_tree_node *
radix_tree_node_alloc(struct radix_tree_root *root)
{
	struct radix_tree_node *ret;
90
	gfp_t gfp_mask = root_gfp_mask(root);
Linus Torvalds's avatar
Linus Torvalds committed
91

92 93
	ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
	if (ret == NULL && !(gfp_mask & __GFP_WAIT)) {
Linus Torvalds's avatar
Linus Torvalds committed
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117
		struct radix_tree_preload *rtp;

		rtp = &__get_cpu_var(radix_tree_preloads);
		if (rtp->nr) {
			ret = rtp->nodes[rtp->nr - 1];
			rtp->nodes[rtp->nr - 1] = NULL;
			rtp->nr--;
		}
	}
	return ret;
}

static inline void
radix_tree_node_free(struct radix_tree_node *node)
{
	kmem_cache_free(radix_tree_node_cachep, node);
}

/*
 * Load up this CPU's radix_tree_node buffer with sufficient objects to
 * ensure that the addition of a single element in the tree cannot fail.  On
 * success, return zero, with preemption disabled.  On error, return -ENOMEM
 * with preemption not disabled.
 */
118
int radix_tree_preload(gfp_t gfp_mask)
Linus Torvalds's avatar
Linus Torvalds committed
119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142
{
	struct radix_tree_preload *rtp;
	struct radix_tree_node *node;
	int ret = -ENOMEM;

	preempt_disable();
	rtp = &__get_cpu_var(radix_tree_preloads);
	while (rtp->nr < ARRAY_SIZE(rtp->nodes)) {
		preempt_enable();
		node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
		if (node == NULL)
			goto out;
		preempt_disable();
		rtp = &__get_cpu_var(radix_tree_preloads);
		if (rtp->nr < ARRAY_SIZE(rtp->nodes))
			rtp->nodes[rtp->nr++] = node;
		else
			kmem_cache_free(radix_tree_node_cachep, node);
	}
	ret = 0;
out:
	return ret;
}

143 144
static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
		int offset)
Linus Torvalds's avatar
Linus Torvalds committed
145
{
146
	__set_bit(offset, node->tags[tag]);
Linus Torvalds's avatar
Linus Torvalds committed
147 148
}

149 150
static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
		int offset)
Linus Torvalds's avatar
Linus Torvalds committed
151
{
152
	__clear_bit(offset, node->tags[tag]);
Linus Torvalds's avatar
Linus Torvalds committed
153 154
}

155 156
static inline int tag_get(struct radix_tree_node *node, unsigned int tag,
		int offset)
Linus Torvalds's avatar
Linus Torvalds committed
157
{
158
	return test_bit(offset, node->tags[tag]);
Linus Torvalds's avatar
Linus Torvalds committed
159 160
}

161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181
static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag)
{
	root->gfp_mask |= (1 << (tag + __GFP_BITS_SHIFT));
}


static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag)
{
	root->gfp_mask &= ~(1 << (tag + __GFP_BITS_SHIFT));
}

static inline void root_tag_clear_all(struct radix_tree_root *root)
{
	root->gfp_mask &= __GFP_BITS_MASK;
}

static inline int root_tag_get(struct radix_tree_root *root, unsigned int tag)
{
	return root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));
}

182 183 184 185
/*
 * Returns 1 if any slot in the node has this tag set.
 * Otherwise returns 0.
 */
186
static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag)
187 188 189 190 191 192 193 194 195
{
	int idx;
	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
		if (node->tags[tag][idx])
			return 1;
	}
	return 0;
}

Linus Torvalds's avatar
Linus Torvalds committed
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
/*
 *	Return the maximum key which can be store into a
 *	radix tree with height HEIGHT.
 */
static inline unsigned long radix_tree_maxindex(unsigned int height)
{
	return height_to_maxindex[height];
}

/*
 *	Extend a radix tree so it can store key @index.
 */
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
	struct radix_tree_node *node;
	unsigned int height;
	int tag;

	/* Figure out what the height should be.  */
	height = root->height + 1;
	while (index > radix_tree_maxindex(height))
		height++;

	if (root->rnode == NULL) {
		root->height = height;
		goto out;
	}

	do {
		if (!(node = radix_tree_node_alloc(root)))
			return -ENOMEM;

		/* Increase the height.  */
		node->slots[0] = root->rnode;

		/* Propagate the aggregated tag info into the new root */
232
		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
233
			if (root_tag_get(root, tag))
Linus Torvalds's avatar
Linus Torvalds committed
234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255
				tag_set(node, tag, 0);
		}

		node->count = 1;
		root->rnode = node;
		root->height++;
	} while (height > root->height);
out:
	return 0;
}

/**
 *	radix_tree_insert    -    insert into a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *	@item:		item to insert
 *
 *	Insert an item into the radix tree at position @index.
 */
int radix_tree_insert(struct radix_tree_root *root,
			unsigned long index, void *item)
{
256
	struct radix_tree_node *node = NULL, *slot;
Linus Torvalds's avatar
Linus Torvalds committed
257 258 259 260 261
	unsigned int height, shift;
	int offset;
	int error;

	/* Make sure the tree is high enough.  */
262
	if (index > radix_tree_maxindex(root->height)) {
Linus Torvalds's avatar
Linus Torvalds committed
263 264 265 266 267
		error = radix_tree_extend(root, index);
		if (error)
			return error;
	}

268
	slot = root->rnode;
Linus Torvalds's avatar
Linus Torvalds committed
269 270 271 272
	height = root->height;
	shift = (height-1) * RADIX_TREE_MAP_SHIFT;

	offset = 0;			/* uninitialised var warning */
273
	while (height > 0) {
274
		if (slot == NULL) {
Linus Torvalds's avatar
Linus Torvalds committed
275
			/* Have to add a child node.  */
276
			if (!(slot = radix_tree_node_alloc(root)))
Linus Torvalds's avatar
Linus Torvalds committed
277
				return -ENOMEM;
278 279
			if (node) {
				node->slots[offset] = slot;
Linus Torvalds's avatar
Linus Torvalds committed
280
				node->count++;
281 282
			} else
				root->rnode = slot;
Linus Torvalds's avatar
Linus Torvalds committed
283 284 285 286
		}

		/* Go a level down */
		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
287 288
		node = slot;
		slot = node->slots[offset];
Linus Torvalds's avatar
Linus Torvalds committed
289 290
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
291
	}
Linus Torvalds's avatar
Linus Torvalds committed
292

293
	if (slot != NULL)
Linus Torvalds's avatar
Linus Torvalds committed
294
		return -EEXIST;
295

296 297 298 299 300 301 302 303 304 305
	if (node) {
		node->count++;
		node->slots[offset] = item;
		BUG_ON(tag_get(node, 0, offset));
		BUG_ON(tag_get(node, 1, offset));
	} else {
		root->rnode = item;
		BUG_ON(root_tag_get(root, 0));
		BUG_ON(root_tag_get(root, 1));
	}
Linus Torvalds's avatar
Linus Torvalds committed
306 307 308 309 310

	return 0;
}
EXPORT_SYMBOL(radix_tree_insert);

311 312
static inline void **__lookup_slot(struct radix_tree_root *root,
				   unsigned long index)
Linus Torvalds's avatar
Linus Torvalds committed
313 314
{
	unsigned int height, shift;
315
	struct radix_tree_node **slot;
Linus Torvalds's avatar
Linus Torvalds committed
316 317

	height = root->height;
318

Linus Torvalds's avatar
Linus Torvalds committed
319 320 321
	if (index > radix_tree_maxindex(height))
		return NULL;

322 323 324
	if (height == 0 && root->rnode)
		return (void **)&root->rnode;

Linus Torvalds's avatar
Linus Torvalds committed
325
	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
326
	slot = &root->rnode;
Linus Torvalds's avatar
Linus Torvalds committed
327 328

	while (height > 0) {
329
		if (*slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
330 331
			return NULL;

332 333 334
		slot = (struct radix_tree_node **)
			((*slot)->slots +
				((index >> shift) & RADIX_TREE_MAP_MASK));
Linus Torvalds's avatar
Linus Torvalds committed
335 336 337 338
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
	}

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
	return (void **)slot;
}

/**
 *	radix_tree_lookup_slot    -    lookup a slot in a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *
 *	Lookup the slot corresponding to the position @index in the radix tree
 *	@root. This is useful for update-if-exists operations.
 */
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index)
{
	return __lookup_slot(root, index);
}
EXPORT_SYMBOL(radix_tree_lookup_slot);

/**
 *	radix_tree_lookup    -    perform lookup operation on a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *
 *	Lookup the item at the position @index in the radix tree @root.
 */
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
	void **slot;

	slot = __lookup_slot(root, index);
	return slot != NULL ? *slot : NULL;
Linus Torvalds's avatar
Linus Torvalds committed
369 370 371 372 373 374 375 376 377
}
EXPORT_SYMBOL(radix_tree_lookup);

/**
 *	radix_tree_tag_set - set a tag on a radix tree node
 *	@root:		radix tree root
 *	@index:		index key
 *	@tag: 		tag index
 *
378 379
 *	Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *	corresponding to @index in the radix tree.  From
Linus Torvalds's avatar
Linus Torvalds committed
380 381 382 383 384 385
 *	the root all the way down to the leaf node.
 *
 *	Returns the address of the tagged item.   Setting a tag on a not-present
 *	item is a bug.
 */
void *radix_tree_tag_set(struct radix_tree_root *root,
386
			unsigned long index, unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
387 388
{
	unsigned int height, shift;
389
	struct radix_tree_node *slot;
Linus Torvalds's avatar
Linus Torvalds committed
390 391

	height = root->height;
392
	BUG_ON(index > radix_tree_maxindex(height));
Linus Torvalds's avatar
Linus Torvalds committed
393

394
	slot = root->rnode;
395
	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
Linus Torvalds's avatar
Linus Torvalds committed
396 397 398 399 400

	while (height > 0) {
		int offset;

		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
401 402
		if (!tag_get(slot, tag, offset))
			tag_set(slot, tag, offset);
403 404
		slot = slot->slots[offset];
		BUG_ON(slot == NULL);
Linus Torvalds's avatar
Linus Torvalds committed
405 406 407 408
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
	}

409 410 411 412
	/* set the root's tag bit */
	if (slot && !root_tag_get(root, tag))
		root_tag_set(root, tag);

413
	return slot;
Linus Torvalds's avatar
Linus Torvalds committed
414 415 416 417 418 419 420 421 422
}
EXPORT_SYMBOL(radix_tree_tag_set);

/**
 *	radix_tree_tag_clear - clear a tag on a radix tree node
 *	@root:		radix tree root
 *	@index:		index key
 *	@tag: 		tag index
 *
423 424
 *	Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
 *	corresponding to @index in the radix tree.  If
Linus Torvalds's avatar
Linus Torvalds committed
425 426 427 428 429 430 431
 *	this causes the leaf node to have no tags set then clear the tag in the
 *	next-to-leaf node, etc.
 *
 *	Returns the address of the tagged item on success, else NULL.  ie:
 *	has the same return value and semantics as radix_tree_lookup().
 */
void *radix_tree_tag_clear(struct radix_tree_root *root,
432
			unsigned long index, unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
433 434
{
	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
435
	struct radix_tree_node *slot = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
436 437 438 439 440 441 442 443
	unsigned int height, shift;

	height = root->height;
	if (index > radix_tree_maxindex(height))
		goto out;

	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
	pathp->node = NULL;
444
	slot = root->rnode;
Linus Torvalds's avatar
Linus Torvalds committed
445 446 447 448

	while (height > 0) {
		int offset;

449
		if (slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
450 451 452 453
			goto out;

		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
		pathp[1].offset = offset;
454 455
		pathp[1].node = slot;
		slot = slot->slots[offset];
Linus Torvalds's avatar
Linus Torvalds committed
456 457 458 459 460
		pathp++;
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
	}

461
	if (slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
462 463
		goto out;

464
	while (pathp->node) {
465 466
		if (!tag_get(pathp->node, tag, pathp->offset))
			goto out;
467
		tag_clear(pathp->node, tag, pathp->offset);
468 469
		if (any_tag_set(pathp->node, tag))
			goto out;
Linus Torvalds's avatar
Linus Torvalds committed
470
		pathp--;
471 472 473 474 475 476
	}

	/* clear the root's tag bit */
	if (root_tag_get(root, tag))
		root_tag_clear(root, tag);

Linus Torvalds's avatar
Linus Torvalds committed
477
out:
478
	return slot;
Linus Torvalds's avatar
Linus Torvalds committed
479 480 481 482 483
}
EXPORT_SYMBOL(radix_tree_tag_clear);

#ifndef __KERNEL__	/* Only the test harness uses this at present */
/**
484 485 486
 * radix_tree_tag_get - get a tag on a radix tree node
 * @root:		radix tree root
 * @index:		index key
487
 * @tag: 		tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds's avatar
Linus Torvalds committed
488
 *
489
 * Return values:
Linus Torvalds's avatar
Linus Torvalds committed
490
 *
491 492
 *  0: tag not present or not set
 *  1: tag set
Linus Torvalds's avatar
Linus Torvalds committed
493 494
 */
int radix_tree_tag_get(struct radix_tree_root *root,
495
			unsigned long index, unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
496 497
{
	unsigned int height, shift;
498
	struct radix_tree_node *slot;
Linus Torvalds's avatar
Linus Torvalds committed
499 500 501 502 503 504
	int saw_unset_tag = 0;

	height = root->height;
	if (index > radix_tree_maxindex(height))
		return 0;

505 506 507 508 509 510 511
	/* check the root's tag bit */
	if (!root_tag_get(root, tag))
		return 0;

	if (height == 0)
		return 1;

Linus Torvalds's avatar
Linus Torvalds committed
512
	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
513
	slot = root->rnode;
Linus Torvalds's avatar
Linus Torvalds committed
514 515 516 517

	for ( ; ; ) {
		int offset;

518
		if (slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
519 520 521 522 523 524 525 526
			return 0;

		offset = (index >> shift) & RADIX_TREE_MAP_MASK;

		/*
		 * This is just a debug check.  Later, we can bale as soon as
		 * we see an unset tag.
		 */
527
		if (!tag_get(slot, tag, offset))
Linus Torvalds's avatar
Linus Torvalds committed
528 529
			saw_unset_tag = 1;
		if (height == 1) {
530
			int ret = tag_get(slot, tag, offset);
Linus Torvalds's avatar
Linus Torvalds committed
531 532

			BUG_ON(ret && saw_unset_tag);
533
			return !!ret;
Linus Torvalds's avatar
Linus Torvalds committed
534
		}
535
		slot = slot->slots[offset];
Linus Torvalds's avatar
Linus Torvalds committed
536 537 538 539 540 541 542 543 544 545 546 547
		shift -= RADIX_TREE_MAP_SHIFT;
		height--;
	}
}
EXPORT_SYMBOL(radix_tree_tag_get);
#endif

static unsigned int
__lookup(struct radix_tree_root *root, void **results, unsigned long index,
	unsigned int max_items, unsigned long *next_index)
{
	unsigned int nr_found = 0;
548
	unsigned int shift, height;
Linus Torvalds's avatar
Linus Torvalds committed
549
	struct radix_tree_node *slot;
550 551 552
	unsigned long i;

	height = root->height;
553 554 555
	if (height == 0) {
		if (root->rnode && index == 0)
			results[nr_found++] = root->rnode;
556
		goto out;
557
	}
Linus Torvalds's avatar
Linus Torvalds committed
558 559 560 561

	shift = (height-1) * RADIX_TREE_MAP_SHIFT;
	slot = root->rnode;

562
	for ( ; height > 1; height--) {
Linus Torvalds's avatar
Linus Torvalds committed
563

564 565
		for (i = (index >> shift) & RADIX_TREE_MAP_MASK ;
				i < RADIX_TREE_MAP_SIZE; i++) {
Linus Torvalds's avatar
Linus Torvalds committed
566 567 568 569 570 571 572 573 574 575 576 577 578
			if (slot->slots[i] != NULL)
				break;
			index &= ~((1UL << shift) - 1);
			index += 1UL << shift;
			if (index == 0)
				goto out;	/* 32-bit wraparound */
		}
		if (i == RADIX_TREE_MAP_SIZE)
			goto out;

		shift -= RADIX_TREE_MAP_SHIFT;
		slot = slot->slots[i];
	}
579 580 581 582 583 584 585 586 587 588

	/* Bottom level: grab some items */
	for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
		index++;
		if (slot->slots[i]) {
			results[nr_found++] = slot->slots[i];
			if (nr_found == max_items)
				goto out;
		}
	}
Linus Torvalds's avatar
Linus Torvalds committed
589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627 628 629 630 631 632 633 634 635 636 637
out:
	*next_index = index;
	return nr_found;
}

/**
 *	radix_tree_gang_lookup - perform multiple lookup on a radix tree
 *	@root:		radix tree root
 *	@results:	where the results of the lookup are placed
 *	@first_index:	start the lookup from this key
 *	@max_items:	place up to this many items at *results
 *
 *	Performs an index-ascending scan of the tree for present items.  Places
 *	them at *@results and returns the number of items which were placed at
 *	*@results.
 *
 *	The implementation is naive.
 */
unsigned int
radix_tree_gang_lookup(struct radix_tree_root *root, void **results,
			unsigned long first_index, unsigned int max_items)
{
	const unsigned long max_index = radix_tree_maxindex(root->height);
	unsigned long cur_index = first_index;
	unsigned int ret = 0;

	while (ret < max_items) {
		unsigned int nr_found;
		unsigned long next_index;	/* Index of next search */

		if (cur_index > max_index)
			break;
		nr_found = __lookup(root, results + ret, cur_index,
					max_items - ret, &next_index);
		ret += nr_found;
		if (next_index == 0)
			break;
		cur_index = next_index;
	}
	return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup);

/*
 * FIXME: the two tag_get()s here should use find_next_bit() instead of
 * open-coding the search.
 */
static unsigned int
__lookup_tag(struct radix_tree_root *root, void **results, unsigned long index,
638
	unsigned int max_items, unsigned long *next_index, unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
639 640 641 642 643 644
{
	unsigned int nr_found = 0;
	unsigned int shift;
	unsigned int height = root->height;
	struct radix_tree_node *slot;

645 646 647 648 649 650
	if (height == 0) {
		if (root->rnode && index == 0)
			results[nr_found++] = root->rnode;
		goto out;
	}

Linus Torvalds's avatar
Linus Torvalds committed
651 652 653
	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
	slot = root->rnode;

654
	do {
Linus Torvalds's avatar
Linus Torvalds committed
655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684
		unsigned long i = (index >> shift) & RADIX_TREE_MAP_MASK;

		for ( ; i < RADIX_TREE_MAP_SIZE; i++) {
			if (tag_get(slot, tag, i)) {
				BUG_ON(slot->slots[i] == NULL);
				break;
			}
			index &= ~((1UL << shift) - 1);
			index += 1UL << shift;
			if (index == 0)
				goto out;	/* 32-bit wraparound */
		}
		if (i == RADIX_TREE_MAP_SIZE)
			goto out;
		height--;
		if (height == 0) {	/* Bottom level: grab some items */
			unsigned long j = index & RADIX_TREE_MAP_MASK;

			for ( ; j < RADIX_TREE_MAP_SIZE; j++) {
				index++;
				if (tag_get(slot, tag, j)) {
					BUG_ON(slot->slots[j] == NULL);
					results[nr_found++] = slot->slots[j];
					if (nr_found == max_items)
						goto out;
				}
			}
		}
		shift -= RADIX_TREE_MAP_SHIFT;
		slot = slot->slots[i];
685
	} while (height > 0);
Linus Torvalds's avatar
Linus Torvalds committed
686 687 688 689 690 691 692 693 694 695 696 697
out:
	*next_index = index;
	return nr_found;
}

/**
 *	radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
 *	                             based on a tag
 *	@root:		radix tree root
 *	@results:	where the results of the lookup are placed
 *	@first_index:	start the lookup from this key
 *	@max_items:	place up to this many items at *results
698
 *	@tag:		the tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds's avatar
Linus Torvalds committed
699 700 701 702 703 704 705
 *
 *	Performs an index-ascending scan of the tree for present items which
 *	have the tag indexed by @tag set.  Places the items at *@results and
 *	returns the number of items which were placed at *@results.
 */
unsigned int
radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
706 707
		unsigned long first_index, unsigned int max_items,
		unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
708 709 710 711 712
{
	const unsigned long max_index = radix_tree_maxindex(root->height);
	unsigned long cur_index = first_index;
	unsigned int ret = 0;

713 714 715 716
	/* check the root's tag bit */
	if (!root_tag_get(root, tag))
		return 0;

Linus Torvalds's avatar
Linus Torvalds committed
717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733
	while (ret < max_items) {
		unsigned int nr_found;
		unsigned long next_index;	/* Index of next search */

		if (cur_index > max_index)
			break;
		nr_found = __lookup_tag(root, results + ret, cur_index,
					max_items - ret, &next_index, tag);
		ret += nr_found;
		if (next_index == 0)
			break;
		cur_index = next_index;
	}
	return ret;
}
EXPORT_SYMBOL(radix_tree_gang_lookup_tag);

734 735 736 737 738 739 740
/**
 *	radix_tree_shrink    -    shrink height of a radix tree to minimal
 *	@root		radix tree root
 */
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
	/* try to shrink tree height */
741
	while (root->height > 0 &&
742 743 744 745 746 747 748 749 750 751 752 753 754 755 756
			root->rnode->count == 1 &&
			root->rnode->slots[0]) {
		struct radix_tree_node *to_free = root->rnode;

		root->rnode = to_free->slots[0];
		root->height--;
		/* must only free zeroed nodes into the slab */
		tag_clear(to_free, 0, 0);
		tag_clear(to_free, 1, 0);
		to_free->slots[0] = NULL;
		to_free->count = 0;
		radix_tree_node_free(to_free);
	}
}

Linus Torvalds's avatar
Linus Torvalds committed
757 758 759 760 761 762 763 764 765 766 767 768
/**
 *	radix_tree_delete    -    delete an item from a radix tree
 *	@root:		radix tree root
 *	@index:		index key
 *
 *	Remove the item at @index from the radix tree rooted at @root.
 *
 *	Returns the address of the deleted item, or NULL if it was not present.
 */
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;
769
	struct radix_tree_node *slot = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
770
	unsigned int height, shift;
771 772
	int tag;
	int offset;
Linus Torvalds's avatar
Linus Torvalds committed
773 774 775 776 777

	height = root->height;
	if (index > radix_tree_maxindex(height))
		goto out;

778 779 780 781 782 783 784
	slot = root->rnode;
	if (height == 0 && root->rnode) {
		root_tag_clear_all(root);
		root->rnode = NULL;
		goto out;
	}

Linus Torvalds's avatar
Linus Torvalds committed
785 786 787
	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
	pathp->node = NULL;

788
	do {
789
		if (slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
790 791
			goto out;

792
		pathp++;
Linus Torvalds's avatar
Linus Torvalds committed
793
		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
794 795
		pathp->offset = offset;
		pathp->node = slot;
796
		slot = slot->slots[offset];
Linus Torvalds's avatar
Linus Torvalds committed
797
		shift -= RADIX_TREE_MAP_SHIFT;
798 799
		height--;
	} while (height > 0);
Linus Torvalds's avatar
Linus Torvalds committed
800

801
	if (slot == NULL)
Linus Torvalds's avatar
Linus Torvalds committed
802 803 804 805 806
		goto out;

	/*
	 * Clear all tags associated with the just-deleted item
	 */
807
	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
808 809
		if (tag_get(pathp->node, tag, pathp->offset))
			radix_tree_tag_clear(root, index, tag);
810
	}
Linus Torvalds's avatar
Linus Torvalds committed
811

812
	/* Now free the nodes we do not need anymore */
813
	while (pathp->node) {
814
		pathp->node->slots[pathp->offset] = NULL;
815 816 817 818 819
		pathp->node->count--;

		if (pathp->node->count) {
			if (pathp->node == root->rnode)
				radix_tree_shrink(root);
820
			goto out;
821
		}
822 823 824

		/* Node with zero slots in use so free it */
		radix_tree_node_free(pathp->node);
825 826

		pathp--;
Linus Torvalds's avatar
Linus Torvalds committed
827
	}
828
	root_tag_clear_all(root);
829
	root->height = 0;
830 831
	root->rnode = NULL;

Linus Torvalds's avatar
Linus Torvalds committed
832
out:
833
	return slot;
Linus Torvalds's avatar
Linus Torvalds committed
834 835 836 837 838 839 840 841
}
EXPORT_SYMBOL(radix_tree_delete);

/**
 *	radix_tree_tagged - test whether any items in the tree are tagged
 *	@root:		radix tree root
 *	@tag:		tag to test
 */
842
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag)
Linus Torvalds's avatar
Linus Torvalds committed
843
{
844
	return root_tag_get(root, tag);
Linus Torvalds's avatar
Linus Torvalds committed
845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901
}
EXPORT_SYMBOL(radix_tree_tagged);

static void
radix_tree_node_ctor(void *node, kmem_cache_t *cachep, unsigned long flags)
{
	memset(node, 0, sizeof(struct radix_tree_node));
}

static __init unsigned long __maxindex(unsigned int height)
{
	unsigned int tmp = height * RADIX_TREE_MAP_SHIFT;
	unsigned long index = (~0UL >> (RADIX_TREE_INDEX_BITS - tmp - 1)) >> 1;

	if (tmp >= RADIX_TREE_INDEX_BITS)
		index = ~0UL;
	return index;
}

static __init void radix_tree_init_maxindex(void)
{
	unsigned int i;

	for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
		height_to_maxindex[i] = __maxindex(i);
}

#ifdef CONFIG_HOTPLUG_CPU
static int radix_tree_callback(struct notifier_block *nfb,
                            unsigned long action,
                            void *hcpu)
{
       int cpu = (long)hcpu;
       struct radix_tree_preload *rtp;

       /* Free per-cpu pool of perloaded nodes */
       if (action == CPU_DEAD) {
               rtp = &per_cpu(radix_tree_preloads, cpu);
               while (rtp->nr) {
                       kmem_cache_free(radix_tree_node_cachep,
                                       rtp->nodes[rtp->nr-1]);
                       rtp->nodes[rtp->nr-1] = NULL;
                       rtp->nr--;
               }
       }
       return NOTIFY_OK;
}
#endif /* CONFIG_HOTPLUG_CPU */

void __init radix_tree_init(void)
{
	radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
			sizeof(struct radix_tree_node), 0,
			SLAB_PANIC, radix_tree_node_ctor, NULL);
	radix_tree_init_maxindex();
	hotcpu_notifier(radix_tree_callback, 0);
}