/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig * Copyright (C) 2005 SGI, Christoph Lameter <clameter@sgi.com> * Copyright (C) 2006 Nick Piggin * * 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>#include <linux/rcupdate.h>  #ifdef __KERNEL__#define RADIX_TREE_MAP_SHIFT	(CONFIG_BASE_SMALL ? 4 : 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	height;		/* Height from the bottom */	unsigned int	count;	struct rcu_head	rcu_head;	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 struct kmem_cache *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, }; static inline gfp_t root_gfp_mask(struct radix_tree_root *root){	return root->gfp_mask & __GFP_BITS_MASK;} /* * 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;	gfp_t gfp_mask = root_gfp_mask(root); 	ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);	if (ret == NULL && !(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--;		}	}	BUG_ON(radix_tree_is_direct_ptr(ret));	return ret;} static void radix_tree_node_rcu_free(struct rcu_head *head){	struct radix_tree_node *node =			container_of(head, struct radix_tree_node, rcu_head);	kmem_cache_free(radix_tree_node_cachep, node);} static inline voidradix_tree_node_free(struct radix_tree_node *node){	call_rcu(&node->rcu_head, radix_tree_node_rcu_free);} /* * 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]);} static inline void root_tag_set(struct radix_tree_root *root, unsigned int tag){	root->gfp_mask |= (__force gfp_t)(1 << (tag + __GFP_BITS_SHIFT));}  static inline void root_tag_clear(struct radix_tree_root *root, unsigned int tag){	root->gfp_mask &= (__force gfp_t)~(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 (__force unsigned)root->gfp_mask & (1 << (tag + __GFP_BITS_SHIFT));} /* * 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;	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 {		unsigned int newheight;		if (!(node = radix_tree_node_alloc(root)))			return -ENOMEM; 		/* Increase the height.  */		node->slots[0] = radix_tree_direct_to_ptr(root->rnode); 		/* Propagate the aggregated tag info into the new root */		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {			if (root_tag_get(root, tag))				tag_set(node, tag, 0);		} 		newheight = root->height+1;		node->height = newheight;		node->count = 1;		rcu_assign_pointer(root->rnode, node);		root->height = newheight;	} 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; 	BUG_ON(radix_tree_is_direct_ptr(item)); 	/* Make sure the tree is high enough.  */	if (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 */	while (height > 0) {		if (slot == NULL) {			/* Have to add a child node.  */			if (!(slot = radix_tree_node_alloc(root)))				return -ENOMEM;			slot->height = height;			if (node) {				rcu_assign_pointer(node->slots[offset], slot);				node->count++;			} else				rcu_assign_pointer(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--;	} 	if (slot != NULL)		return -EEXIST; 	if (node) {		node->count++;		rcu_assign_pointer(node->slots[offset], item);		BUG_ON(tag_get(node, 0, offset));		BUG_ON(tag_get(node, 1, offset));	} else {		rcu_assign_pointer(root->rnode, radix_tree_ptr_to_direct(item));		BUG_ON(root_tag_get(root, 0));		BUG_ON(root_tag_get(root, 1));	} 	return 0;}EXPORT_SYMBOL(radix_tree_insert); /** *	radix_tree_lookup_slot    -    lookup a slot in a radix tree *	@root:		radix tree root *	@index:		index key * *	Returns:  the slot corresponding to the position @index in the *	radix tree @root. This is useful for update-if-exists operations. * *	This function cannot be called under rcu_read_lock, it must be *	excluded from writers, as must the returned slot for subsequent *	use by radix_tree_deref_slot() and radix_tree_replace slot. *	Caller must hold tree write locked across slot lookup and *	replace. */void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index){	unsigned int height, shift;	struct radix_tree_node *node, **slot; 	node = root->rnode;	if (node == NULL)		return NULL; 	if (radix_tree_is_direct_ptr(node)) {		if (index > 0)			return NULL;		return (void **)&root->rnode;	} 	height = node->height;	if (index > radix_tree_maxindex(height))		return NULL; 	shift = (height-1) * RADIX_TREE_MAP_SHIFT; 	do {		slot = (struct radix_tree_node **)			(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));		node = *slot;		if (node == NULL)			return NULL; 		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} while (height > 0); 	return (void **)slot;}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. * *	This function can be called under rcu_read_lock, however the caller *	must manage lifetimes of leaf nodes (eg. RCU may also be used to free *	them safely). No RCU barriers are required to access or modify the *	returned item, however. */void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index){	unsigned int height, shift;	struct radix_tree_node *node, **slot; 	node = rcu_dereference(root->rnode);	if (node == NULL)		return NULL; 	if (radix_tree_is_direct_ptr(node)) {		if (index > 0)			return NULL;		return radix_tree_direct_to_ptr(node);	} 	height = node->height;	if (index > radix_tree_maxindex(height))		return NULL; 	shift = (height-1) * RADIX_TREE_MAP_SHIFT; 	do {		slot = (struct radix_tree_node **)			(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK));		node = rcu_dereference(*slot);		if (node == NULL)			return NULL; 		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} while (height > 0); 	return node;}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;	BUG_ON(index > radix_tree_maxindex(height)); 	slot = root->rnode;	shift = (height - 1) * RADIX_TREE_MAP_SHIFT; 	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--;	} 	/* set the root's tag bit */	if (slot && !root_tag_get(root, tag))		root_tag_set(root, tag); 	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 = NULL;	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;	slot = root->rnode; 

Lines 1–500 of 1026. Load more