/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com> * * 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__#define RADIX_TREE_MAP_SHIFT	6#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];	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];}; struct radix_tree_path {	struct radix_tree_node *node;	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) static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH] __read_mostly; /* * 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, }; /* * 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; 	ret = kmem_cache_alloc(radix_tree_node_cachep, root->gfp_mask);	if (ret == NULL && !(root->gfp_mask & __GFP_WAIT)) {		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 voidradix_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. */int radix_tree_preload(gfp_t gfp_mask){	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;} static inline void tag_set(struct radix_tree_node *node, unsigned int tag,		int offset){	__set_bit(offset, node->tags[tag]);} static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,		int offset){	__clear_bit(offset, node->tags[tag]);} static inline int tag_get(struct radix_tree_node *node, unsigned int tag,		int offset){	return test_bit(offset, node->tags[tag]);} /* * Returns 1 if any slot in the node has this tag set. * Otherwise returns 0. */static inline int any_tag_set(struct radix_tree_node *node, unsigned int tag){	int idx;	for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {		if (node->tags[tag][idx])			return 1;	}	return 0;} /* *	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;	char tags[RADIX_TREE_MAX_TAGS];	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;	} 	/*	 * Prepare the tag status of the top-level node for propagation	 * into the newly-pushed top-level node(s)	 */	for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {		tags[tag] = 0;		if (any_tag_set(root->rnode, tag))			tags[tag] = 1;	} 	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 */		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {			if (tags[tag])				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){	struct radix_tree_node *node = NULL, *slot;	unsigned int height, shift;	int offset;	int error; 	/* Make sure the tree is high enough.  */	if ((!index && !root->rnode) ||			index > radix_tree_maxindex(root->height)) {		error = radix_tree_extend(root, index);		if (error)			return error;	} 	slot = root->rnode;	height = root->height;	shift = (height-1) * RADIX_TREE_MAP_SHIFT; 	offset = 0;			/* uninitialised var warning */	do {		if (slot == NULL) {			/* Have to add a child node.  */			if (!(slot = radix_tree_node_alloc(root)))				return -ENOMEM;			if (node) {				node->slots[offset] = slot;				node->count++;			} else				root->rnode = slot;		} 		/* Go a level down */		offset = (index >> shift) & RADIX_TREE_MAP_MASK;		node = slot;		slot = node->slots[offset];		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} while (height > 0); 	if (slot != NULL)		return -EEXIST; 	BUG_ON(!node);	node->count++;	node->slots[offset] = item;	BUG_ON(tag_get(node, 0, offset));	BUG_ON(tag_get(node, 1, offset)); 	return 0;}EXPORT_SYMBOL(radix_tree_insert); static inline void **__lookup_slot(struct radix_tree_root *root,				   unsigned long index){	unsigned int height, shift;	struct radix_tree_node **slot; 	height = root->height;	if (index > radix_tree_maxindex(height))		return NULL; 	shift = (height-1) * RADIX_TREE_MAP_SHIFT;	slot = &root->rnode; 	while (height > 0) {		if (*slot == NULL)			return NULL; 		slot = (struct radix_tree_node **)			((*slot)->slots +				((index >> shift) & RADIX_TREE_MAP_MASK));		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} 	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;}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 * *	Set the search tag (which must be < RADIX_TREE_MAX_TAGS) *	corresponding to @index in the radix tree.  From *	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,			unsigned long index, unsigned int tag){	unsigned int height, shift;	struct radix_tree_node *slot; 	height = root->height;	if (index > radix_tree_maxindex(height))		return NULL; 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;	slot = root->rnode; 	while (height > 0) {		int offset; 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;		if (!tag_get(slot, tag, offset))			tag_set(slot, tag, offset);		slot = slot->slots[offset];		BUG_ON(slot == NULL);		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} 	return slot;}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 * *	Clear the search tag (which must be < RADIX_TREE_MAX_TAGS) *	corresponding to @index in the radix tree.  If *	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,			unsigned long index, unsigned int tag){	struct radix_tree_path path[RADIX_TREE_MAX_PATH], *pathp = path;	struct radix_tree_node *slot;	unsigned int height, shift;	void *ret = NULL; 	height = root->height;	if (index > radix_tree_maxindex(height))		goto out; 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;	pathp->node = NULL;	slot = root->rnode; 	while (height > 0) {		int offset; 		if (slot == NULL)			goto out; 		offset = (index >> shift) & RADIX_TREE_MAP_MASK;		pathp[1].offset = offset;		pathp[1].node = slot;		slot = slot->slots[offset];		pathp++;		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} 	ret = slot;	if (ret == NULL)		goto out; 	do {		if (!tag_get(pathp->node, tag, pathp->offset))			goto out;		tag_clear(pathp->node, tag, pathp->offset);		if (any_tag_set(pathp->node, tag))			goto out;		pathp--;	} while (pathp->node);out:	return ret;}EXPORT_SYMBOL(radix_tree_tag_clear); #ifndef __KERNEL__	/* Only the test harness uses this at present *//** * radix_tree_tag_get - get a tag on a radix tree node * @root:		radix tree root * @index:		index key * @tag: 		tag index (< RADIX_TREE_MAX_TAGS) * * Return values: * *  0: tag not present *  1: tag present, set * -1: tag present, unset */int radix_tree_tag_get(struct radix_tree_root *root,			unsigned long index, unsigned int tag){	unsigned int height, shift;	struct radix_tree_node *slot;	int saw_unset_tag = 0; 	height = root->height;	if (index > radix_tree_maxindex(height))		return 0; 	shift = (height - 1) * RADIX_TREE_MAP_SHIFT;	slot = root->rnode; 	for ( ; ; ) {		int offset; 		if (slot == NULL)			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.		 */		if (!tag_get(slot, tag, offset))			saw_unset_tag = 1;		if (height == 1) {			int ret = tag_get(slot, tag, offset); 			BUG_ON(ret && saw_unset_tag);			return ret ? 1 : -1;		}		slot = slot->slots[offset];		shift -= RADIX_TREE_MAP_SHIFT;

Lines 1–500 of 872. Load more