/* * Copyright (C) 2001 Momchil Velikov * Portions Copyright (C) 2001 Christoph Hellwig * Copyright (C) 2005 SGI, Christoph Lameter * Copyright (C) 2006 Nick Piggin * Copyright (C) 2012 Konstantin Khlebnikov * * 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/export.h>#include <linux/radix-tree.h>#include <linux/percpu.h>#include <linux/slab.h>#include <linux/notifier.h>#include <linux/cpu.h>#include <linux/string.h>#include <linux/bitops.h>#include <linux/rcupdate.h>#include <linux/hardirq.h>		/* in_interrupt() */  #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;	union {		struct radix_tree_node *parent;	/* Used when ascending tree */		struct rcu_head	rcu_head;	/* Used when freeing node */	};	void __rcu	*slots[RADIX_TREE_MAP_SIZE];	unsigned long	tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];}; #define RADIX_TREE_INDEX_BITS  (8 /* CHAR_BIT */ * sizeof(unsigned long))#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \					  RADIX_TREE_MAP_SHIFT)) /* * The height_to_maxindex array needs to be one deeper than the maximum * path as height 0 holds only 1 entry. */static unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1] __read_mostly; /* * Radix tree node cache. */static struct kmem_cache *radix_tree_node_cachep; /* * The radix tree is variable-height, so an insert operation not only has * to build the branch to its corresponding item, it also has to build the * branch to existing items if the size has to be increased (by * radix_tree_extend). * * The worst case is a zero height tree with just a single item at index 0, * and then inserting an item at index ULONG_MAX. This requires 2 new branches * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared. * Hence: */#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1) /* * Per-cpu pool of preloaded nodes */struct radix_tree_preload {	int nr;	struct radix_tree_node *nodes[RADIX_TREE_PRELOAD_SIZE];};static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; static inline void *ptr_to_indirect(void *ptr){	return (void *)((unsigned long)ptr | RADIX_TREE_INDIRECT_PTR);} static inline void *indirect_to_ptr(void *ptr){	return (void *)((unsigned long)ptr & ~RADIX_TREE_INDIRECT_PTR);} static inline gfp_t root_gfp_mask(struct radix_tree_root *root){	return root->gfp_mask & __GFP_BITS_MASK;} 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;} /** * radix_tree_find_next_bit - find the next set bit in a memory region * * @addr: The address to base the search on * @size: The bitmap size in bits * @offset: The bitnumber to start searching at * * Unrollable variant of find_next_bit() for constant size arrays. * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero. * Returns next bit offset, or size if nothing found. */static __always_inline unsigned longradix_tree_find_next_bit(const unsigned long *addr,			 unsigned long size, unsigned long offset){	if (!__builtin_constant_p(size))		return find_next_bit(addr, size, offset); 	if (offset < size) {		unsigned long tmp; 		addr += offset / BITS_PER_LONG;		tmp = *addr >> (offset % BITS_PER_LONG);		if (tmp)			return __ffs(tmp) + offset;		offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);		while (offset < size) {			tmp = *++addr;			if (tmp)				return __ffs(tmp) + offset;			offset += BITS_PER_LONG;		}	}	return size;} /* * 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 = NULL;	gfp_t gfp_mask = root_gfp_mask(root); 	/*	 * Preload code isn't irq safe and it doesn't make sence to use	 * preloading in the interrupt anyway as all the allocations have to	 * be atomic. So just do normal allocation when in interrupt.	 */	if (!(gfp_mask & __GFP_WAIT) && !in_interrupt()) {		struct radix_tree_preload *rtp; 		/*		 * Provided the caller has preloaded here, we will always		 * succeed in getting a node here (and never reach		 * kmem_cache_alloc)		 */		rtp = &__get_cpu_var(radix_tree_preloads);		if (rtp->nr) {			ret = rtp->nodes[rtp->nr - 1];			rtp->nodes[rtp->nr - 1] = NULL;			rtp->nr--;		}	}	if (ret == NULL)		ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); 	BUG_ON(radix_tree_is_indirect_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);	int i; 	/*	 * must only free zeroed nodes into the slab. radix_tree_shrink	 * can leave us with a non-NULL entry in the first slot, so clear	 * that here to make sure.	 */	for (i = 0; i < RADIX_TREE_MAX_TAGS; i++)		tag_clear(node, i, 0); 	node->slots[0] = NULL;	node->count = 0; 	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. * * To make use of this facility, the radix tree must be initialised without * __GFP_WAIT being passed to INIT_RADIX_TREE(). */static 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;} /* * 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. * * To make use of this facility, the radix tree must be initialised without * __GFP_WAIT being passed to INIT_RADIX_TREE(). */int radix_tree_preload(gfp_t gfp_mask){	/* Warn on non-sensical use... */	WARN_ON_ONCE(!(gfp_mask & __GFP_WAIT));	return __radix_tree_preload(gfp_mask);}EXPORT_SYMBOL(radix_tree_preload); /* * The same as above function, except we don't guarantee preloading happens. * We do it, if we decide it helps. On success, return zero with preemption * disabled. On error, return -ENOMEM with preemption not disabled. */int radix_tree_maybe_preload(gfp_t gfp_mask){	if (gfp_mask & __GFP_WAIT)		return __radix_tree_preload(gfp_mask);	/* Preloading doesn't help anything with this gfp mask, skip it */	preempt_disable();	return 0;}EXPORT_SYMBOL(radix_tree_maybe_preload); /* *	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;	struct radix_tree_node *slot;	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; 		/* 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);		} 		/* Increase the height.  */		newheight = root->height+1;		node->height = newheight;		node->count = 1;		node->parent = NULL;		slot = root->rnode;		if (newheight > 1) {			slot = indirect_to_ptr(slot);			slot->parent = node;		}		node->slots[0] = slot;		node = ptr_to_indirect(node);		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_indirect_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 = indirect_to_ptr(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;			slot->parent = node;			if (node) {				rcu_assign_pointer(node->slots[offset], slot);				node->count++;			} else				rcu_assign_pointer(root->rnode, ptr_to_indirect(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, item);		BUG_ON(root_tag_get(root, 0));		BUG_ON(root_tag_get(root, 1));	} 	return 0;}EXPORT_SYMBOL(radix_tree_insert); /* * is_slot == 1 : search for the slot. * is_slot == 0 : search for the node. */static void *radix_tree_lookup_element(struct radix_tree_root *root,				unsigned long index, int is_slot){	unsigned int height, shift;	struct radix_tree_node *node, **slot; 	node = rcu_dereference_raw(root->rnode);	if (node == NULL)		return NULL; 	if (!radix_tree_is_indirect_ptr(node)) {		if (index > 0)			return NULL;		return is_slot ? (void *)&root->rnode : node;	}	node = indirect_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_raw(*slot);		if (node == NULL)			return NULL; 		shift -= RADIX_TREE_MAP_SHIFT;		height--;	} while (height > 0); 	return is_slot ? (void *)slot : indirect_to_ptr(node);} 

Lines 1–500 of 1492. Load more