cregit-Linux how code gets into the kernel

Release 4.7 lib/radix-tree.c

Directory: lib
/*
 * 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
 * Copyright (C) 2016 Intel, Matthew Wilcox
 * Copyright (C) 2016 Intel, Ross Zwisler
 *
 * 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/kmemleak.h>
#include <linux/notifier.h>
#include <linux/cpu.h>
#include <linux/string.h>
#include <linux/bitops.h>
#include <linux/rcupdate.h>
#include <linux/preempt.h>		/* in_interrupt() */


/*
 * 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 {
	
unsigned nr;
	/* nodes->private_data points to next preallocated node */
	
struct radix_tree_node *nodes;
};
static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };


static inline void *node_to_entry(void *ptr) { return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin2592.59%133.33%
matthew wilcoxmatthew wilcox27.41%266.67%
Total27100.00%3100.00%

#define RADIX_TREE_RETRY node_to_entry(NULL) #ifdef CONFIG_RADIX_TREE_MULTIORDER /* Sibling slots point directly to another slot in the same node */
static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) { void **ptr = node; return (parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE); }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox42100.00%1100.00%
Total42100.00%1100.00%

#else
static inline bool is_sibling_entry(struct radix_tree_node *parent, void *node) { return false; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox19100.00%1100.00%
Total19100.00%1100.00%

#endif
static inline unsigned long get_slot_offset(struct radix_tree_node *parent, void **slot) { return slot - parent->slots; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox25100.00%1100.00%
Total25100.00%1100.00%


static unsigned int radix_tree_descend(struct radix_tree_node *parent, struct radix_tree_node **nodep, unsigned long index) { unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; void **entry = rcu_dereference_raw(parent->slots[offset]); #ifdef CONFIG_RADIX_TREE_MULTIORDER if (radix_tree_is_internal_node(entry)) { unsigned long siboff = get_slot_offset(parent, entry); if (siboff < RADIX_TREE_MAP_SIZE) { offset = siboff; entry = rcu_dereference_raw(parent->slots[offset]); } } #endif *nodep = (void *)entry; return offset; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox112100.00%3100.00%
Total112100.00%3100.00%


static inline gfp_t root_gfp_mask(struct radix_tree_root *root) { return root->gfp_mask & __GFP_BITS_MASK; }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin19100.00%1100.00%
Total19100.00%1100.00%


static inline void tag_set(struct radix_tree_node *node, unsigned int tag, int offset) { __set_bit(offset, node->tags[tag]); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin2064.52%125.00%
andrew mortonandrew morton1135.48%375.00%
Total31100.00%4100.00%


static inline void tag_clear(struct radix_tree_node *node, unsigned int tag, int offset) { __clear_bit(offset, node->tags[tag]); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin2683.87%150.00%
andrew mortonandrew morton516.13%150.00%
Total31100.00%2100.00%


static inline int tag_get(struct radix_tree_node *node, unsigned int tag, int offset) { return test_bit(offset, node->tags[tag]); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin3093.75%375.00%
andrew mortonandrew morton26.25%125.00%
Total32100.00%4100.00%


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)); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin34100.00%2100.00%
Total34100.00%2100.00%


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

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin2470.59%240.00%
andrew mortonandrew morton1029.41%360.00%
Total34100.00%5100.00%


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

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin1583.33%150.00%
andrew mortonandrew morton316.67%150.00%
Total18100.00%2100.00%


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

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin3291.43%133.33%
andrew mortonandrew morton25.71%133.33%
matthew wilcoxmatthew wilcox12.86%133.33%
Total35100.00%3100.00%


static inline unsigned root_tags_get(struct radix_tree_root *root) { return (__force unsigned)root->gfp_mask >> __GFP_BITS_SHIFT; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox23100.00%1100.00%
Total23100.00%1100.00%

/* * 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) { unsigned idx; for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) { if (node->tags[tag][idx]) return 1; } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin4178.85%133.33%
andrew mortonandrew morton1019.23%133.33%
matthew wilcoxmatthew wilcox11.92%133.33%
Total52100.00%3100.00%

/** * 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 long radix_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; }

Contributors

PersonTokensPropCommitsCommitProp
konstantin khlebnikovkonstantin khlebnikov129100.00%1100.00%
Total129100.00%1100.00%

#ifndef __KERNEL__
static void dump_node(struct radix_tree_node *node, unsigned long index) { unsigned long i; pr_debug("radix node: %p offset %d tags %lx %lx %lx shift %d count %d parent %p\n", node, node->offset, node->tags[0][0], node->tags[1][0], node->tags[2][0], node->shift, node->count, node->parent); for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) { unsigned long first = index | (i << node->shift); unsigned long last = first | ((1UL << node->shift) - 1); void *entry = node->slots[i]; if (!entry) continue; if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld val %p indices %ld-%ld\n", entry, i, *(void **)entry_to_node(entry), first, last); } else if (!radix_tree_is_internal_node(entry)) { pr_debug("radix entry %p offset %ld indices %ld-%ld\n", entry, i, first, last); } else { dump_node(entry_to_node(entry), first); } } }

Contributors

PersonTokensPropCommitsCommitProp
ross zwislerross zwisler19694.23%114.29%
matthew wilcoxmatthew wilcox125.77%685.71%
Total208100.00%7100.00%

/* For debug */
static void radix_tree_dump(struct radix_tree_root *root) { pr_debug("radix root: %p rnode %p tags %x\n", root, root->rnode, root->gfp_mask >> __GFP_BITS_SHIFT); if (!radix_tree_is_internal_node(root->rnode)) return; dump_node(entry_to_node(root->rnode), 0); }

Contributors

PersonTokensPropCommitsCommitProp
ross zwislerross zwisler4894.12%125.00%
matthew wilcoxmatthew wilcox35.88%375.00%
Total51100.00%4100.00%

#endif /* * 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 sense to use * preloading during an interrupt anyway as all the allocations have * to be atomic. So just do normal allocation when in interrupt. */ if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) { struct radix_tree_preload *rtp; /* * Even if the caller has preloaded, try to allocate from the * cache first for the new node to get accounted. */ ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask | __GFP_ACCOUNT | __GFP_NOWARN); if (ret) goto out; /* * Provided the caller has preloaded here, we will always * succeed in getting a node here (and never reach * kmem_cache_alloc) */ rtp = this_cpu_ptr(&radix_tree_preloads); if (rtp->nr) { ret = rtp->nodes; rtp->nodes = ret->private_data; ret->private_data = NULL; rtp->nr--; } /* * Update the allocation stack trace as this is more useful * for debugging. */ kmemleak_update_trace(ret); goto out; } ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask | __GFP_ACCOUNT); out: BUG_ON(radix_tree_is_internal_node(ret)); return ret; }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin5538.19%19.09%
andrew mortonandrew morton3725.69%218.18%
vladimir davydovvladimir davydov2819.44%19.09%
kirill a. shutemovkirill a. shutemov74.86%19.09%
catalin marinascatalin marinas64.17%19.09%
jan karajan kara42.78%19.09%
mel gormanmel gorman32.08%19.09%
matthew wilcoxmatthew wilcox21.39%218.18%
christoph lameterchristoph lameter21.39%19.09%
Total144100.00%11100.00%


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); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin4155.41%240.00%
dave chinnerdave chinner1621.62%120.00%
andrew mortonandrew morton1520.27%120.00%
al viroal viro22.70%120.00%
Total74100.00%5100.00%


static inline void radix_tree_node_free(struct radix_tree_node *node) { call_rcu(&node->rcu_head, radix_tree_node_rcu_free); }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin22100.00%2100.00%
Total22100.00%2100.00%

/* * 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_DIRECT_RECLAIM 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 = this_cpu_ptr(&radix_tree_preloads); while (rtp->nr < RADIX_TREE_PRELOAD_SIZE) { preempt_enable(); node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask); if (node == NULL) goto out; preempt_disable(); rtp = this_cpu_ptr(&radix_tree_preloads); if (rtp->nr < RADIX_TREE_PRELOAD_SIZE) { node->private_data = rtp->nodes; rtp->nodes = node; rtp->nr++; } else { kmem_cache_free(radix_tree_node_cachep, node); } } ret = 0; out: return ret; }

Contributors

PersonTokensPropCommitsCommitProp
nick pigginnick piggin10583.33%240.00%
kirill a. shutemovkirill a. shutemov1511.90%120.00%
christoph lameterchristoph lameter43.17%120.00%
jan karajan kara21.59%120.00%
Total126100.00%5100.00%

/* * 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_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). */
int radix_tree_preload(gfp_t gfp_mask) { /* Warn on non-sensical use... */ WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask)); return __radix_tree_preload(gfp_mask); }

Contributors

PersonTokensPropCommitsCommitProp
jan karajan kara2187.50%150.00%
mel gormanmel gorman312.50%150.00%
Total24100.00%2100.00%

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 (gfpflags_allow_blocking(gfp_mask)) return __radix_tree_preload(gfp_mask); /* Preloading doesn't help anything with this gfp mask, skip it */ preempt_disable(); return 0; }

Contributors

PersonTokensPropCommitsCommitProp
jan karajan kara2589.29%150.00%
mel gormanmel gorman310.71%150.00%
Total28100.00%2100.00%

EXPORT_SYMBOL(radix_tree_maybe_preload); /* * The maximum index which can be stored in a radix tree */
static inline unsigned long shift_maxindex(unsigned int shift) { return (RADIX_TREE_MAP_SIZE << shift) - 1; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox21100.00%1100.00%
Total21100.00%1100.00%


static inline unsigned long node_maxindex(struct radix_tree_node *node) { return shift_maxindex(node->shift); }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox21100.00%2100.00%
Total21100.00%2100.00%


static unsigned radix_tree_load_root(struct radix_tree_root *root, struct radix_tree_node **nodep, unsigned long *maxindex) { struct radix_tree_node *node = rcu_dereference_raw(root->rnode); *nodep = node; if (likely(radix_tree_is_internal_node(node))) { node = entry_to_node(node); *maxindex = node_maxindex(node); return node->shift + RADIX_TREE_MAP_SHIFT; } *maxindex = 0; return 0; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox81100.00%4100.00%
Total81100.00%4100.00%

/* * Extend a radix tree so it can store key @index. */
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index, unsigned int shift) { struct radix_tree_node *slot; unsigned int maxshift; int tag; /* Figure out what the shift should be. */ maxshift = shift; while (index > shift_maxindex(maxshift)) maxshift += RADIX_TREE_MAP_SHIFT; slot = root->rnode; if (!slot) goto out; do { struct radix_tree_node *node = radix_tree_node_alloc(root); if (!node) 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); } BUG_ON(shift > BITS_PER_LONG); node->shift = shift; node->offset = 0; node->count = 1; node->parent = NULL; if (radix_tree_is_internal_node(slot)) entry_to_node(slot)->parent = node; node->slots[0] = slot; slot = node_to_entry(node); rcu_assign_pointer(root->rnode, slot); shift += RADIX_TREE_MAP_SHIFT; } while (shift <= maxshift); out: return maxshift + RADIX_TREE_MAP_SHIFT; }

Contributors

PersonTokensPropCommitsCommitProp
andrew mortonandrew morton10047.85%211.76%
matthew wilcoxmatthew wilcox5827.75%952.94%
hugh dickinshugh dickins2712.92%15.88%
nick pigginnick piggin199.09%317.65%
johannes weinerjohannes weiner41.91%15.88%
jonathan corbetjonathan corbet10.48%15.88%
Total209100.00%17100.00%

/** * __radix_tree_create - create a slot in a radix tree * @root: radix tree root * @index: index key * @order: index occupies 2^order aligned slots * @nodep: returns node * @slotp: returns slot * * Create, if necessary, and return the node and slot for an item * at position @index in the radix tree @root. * * Until there is more than one item in the tree, no nodes are * allocated and @root->rnode is used as a direct slot instead of * pointing to a node, in which case *@nodep will be NULL. * * Returns -ENOMEM, or 0 for success. */
int __radix_tree_create(struct radix_tree_root *root, unsigned long index, unsigned order, struct radix_tree_node **nodep, void ***slotp) { struct radix_tree_node *node = NULL, *child; void **slot = (void **)&root->rnode; unsigned long maxindex; unsigned int shift, offset = 0; unsigned long max = index | ((1UL << order) - 1); shift = radix_tree_load_root(root, &child, &maxindex); /* Make sure the tree is high enough. */ if (max > maxindex) { int error = radix_tree_extend(root, max, shift); if (error < 0) return error; shift = error; child = root->rnode; if (order == shift) shift += RADIX_TREE_MAP_SHIFT; } while (shift > order) { shift -= RADIX_TREE_MAP_SHIFT; if (child == NULL) { /* Have to add a child node. */ child = radix_tree_node_alloc(root); if (!child) return -ENOMEM; child->shift = shift; child->offset = offset; child->parent = node; rcu_assign_pointer(*slot, node_to_entry(child)); if (node) node->count++; } else if (!radix_tree_is_internal_node(child)) break; /* Go a level down */ node = entry_to_node(child); offset = radix_tree_descend(node, &child, index); slot = &node->slots[offset]; } #ifdef CONFIG_RADIX_TREE_MULTIORDER /* Insert pointers to the canonical entry */ if (order > shift) { unsigned i, n = 1 << (order - shift); offset = offset & ~(n - 1); slot = &node->slots[offset]; child = node_to_entry(slot); for (i = 0; i < n; i++) { if (slot[i]) return -EEXIST; } for (i = 1; i < n; i++) { rcu_assign_pointer(slot[i], child); node->count++; } } #endif if (nodep) *nodep = node; if (slotp) *slotp = slot; return 0; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox25765.56%1669.57%
andrew mortonandrew morton8822.45%28.70%
johannes weinerjohannes weiner307.65%14.35%
nick pigginnick piggin112.81%28.70%
hugh dickinshugh dickins51.28%14.35%
christoph lameterchristoph lameter10.26%14.35%
Total392100.00%23100.00%

/** * __radix_tree_insert - insert into a radix tree * @root: radix tree root * @index: index key * @order: key covers the 2^order indices around index * @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, unsigned order, void *item) { struct radix_tree_node *node; void **slot; int error; BUG_ON(radix_tree_is_internal_node(item)); error = __radix_tree_create(root, index, order, &node, &slot); if (error) return error; if (*slot != NULL) return -EEXIST; rcu_assign_pointer(*slot, item); if (node) { unsigned offset = get_slot_offset(node, slot); node->count++; BUG_ON(tag_get(node, 0, offset)); BUG_ON(tag_get(node, 1, offset)); BUG_ON(tag_get(node, 2, offset)); } else { BUG_ON(root_tags_get(root)); } return 0; }

Contributors

PersonTokensPropCommitsCommitProp
johannes weinerjohannes weiner6944.23%112.50%
andrew mortonandrew morton4025.64%337.50%
matthew wilcoxmatthew wilcox2817.95%337.50%
nick pigginnick piggin1912.18%112.50%
Total156100.00%8100.00%

EXPORT_SYMBOL(__radix_tree_insert); /** * __radix_tree_lookup - lookup an item in a radix tree * @root: radix tree root * @index: index key * @nodep: returns node * @slotp: returns slot * * Lookup and return the item at position @index in the radix * tree @root. * * Until there is more than one item in the tree, no nodes are * allocated and @root->rnode is used as a direct slot instead of * pointing to a node, in which case *@nodep will be NULL. */
void *__radix_tree_lookup(struct radix_tree_root *root, unsigned long index, struct radix_tree_node **nodep, void ***slotp) { struct radix_tree_node *node, *parent; unsigned long maxindex; void **slot; restart: parent = NULL; slot = (void **)&root->rnode; radix_tree_load_root(root, &node, &maxindex); if (index > maxindex) return NULL; while (radix_tree_is_internal_node(node)) { unsigned offset; if (node == RADIX_TREE_RETRY) goto restart; parent = entry_to_node(node); offset = radix_tree_descend(parent, &node, index); slot = parent->slots + offset; } if (nodep) *nodep = parent; if (slotp) *slotp = slot; return node; }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox5637.09%535.71%
johannes weinerjohannes weiner4731.13%214.29%
nick pigginnick piggin2214.57%321.43%
andrew mortonandrew morton1912.58%214.29%
huang shijiehuang shijie42.65%17.14%
hans reiserhans reiser31.99%17.14%
Total151100.00%14100.00%

/** * 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 can be called under rcu_read_lock iff the slot is not * modified by radix_tree_replace_slot, otherwise it must be called * exclusive from other writers. Any dereference of the slot must be done * using radix_tree_deref_slot. */
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index) { void **slot; if (!__radix_tree_lookup(root, index, NULL, &slot)) return NULL; return slot; }

Contributors

PersonTokensPropCommitsCommitProp
huang shijiehuang shijie2252.38%133.33%
johannes weinerjohannes weiner1842.86%133.33%
hans reiserhans reiser24.76%133.33%
Total42100.00%3100.00%

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) { return __radix_tree_lookup(root, index, NULL, NULL); }

Contributors

PersonTokensPropCommitsCommitProp
hans reiserhans reiser1555.56%116.67%
nick pigginnick piggin414.81%233.33%
johannes weinerjohannes weiner414.81%116.67%
huang shijiehuang shijie311.11%116.67%
andrew mortonandrew morton13.70%116.67%
Total27100.00%6100.00%

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) { struct radix_tree_node *node, *parent; unsigned long maxindex; radix_tree_load_root(root, &node, &maxindex); BUG_ON(index > maxindex); while (radix_tree_is_internal_node(node)) { unsigned offset; parent = entry_to_node(node); offset = radix_tree_descend(parent, &node, index); BUG_ON(!node); if (!tag_get(parent, tag, offset)) tag_set(parent, tag, offset); } /* set the root's tag bit */ if (!root_tag_get(root, tag)) root_tag_set(root, tag); return node; }

Contributors

PersonTokensPropCommitsCommitProp
ross zwislerross zwisler4736.72%18.33%
andrew mortonandrew morton4434.38%18.33%
nick pigginnick piggin2217.19%325.00%
matthew wilcoxmatthew wilcox129.38%541.67%
peter zijlstrapeter zijlstra21.56%18.33%
jonathan corbetjonathan corbet10.78%18.33%
Total128100.00%12100.00%

EXPORT_SYMBOL(radix_tree_tag_set);
static void node_tag_clear(struct radix_tree_root *root, struct radix_tree_node *node, unsigned int tag, unsigned int offset) { while (node) { if (!tag_get(node, tag, offset)) return; tag_clear(node, tag, offset); if (any_tag_set(node, tag)) return; offset = node->offset; node = node->parent; } /* clear the root's tag bit */ if (root_tag_get(root, tag)) root_tag_clear(root, tag); }

Contributors

PersonTokensPropCommitsCommitProp
matthew wilcoxmatthew wilcox91100.00%1100.00%
Total91100.00%1100.00%

/** * 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) {