/* * 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/bitmap.h>#include <linux/bitops.h>#include <linux/cpu.h>#include <linux/errno.h>#include <linux/export.h>#include <linux/idr.h>#include <linux/init.h>#include <linux/kernel.h>#include <linux/kmemleak.h>#include <linux/percpu.h>#include <linux/preempt.h> /* in_interrupt() */#include <linux/radix-tree.h>#include <linux/rcupdate.h>#include <linux/slab.h>#include <linux/string.h> /* Number of nodes in fully populated tree of given height */static unsigned long height_to_maxnodes[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) /* * The IDR does not have to be as high as the radix tree since it uses * signed integers, not unsigned longs. */#define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)#define IDR_MAX_PATH (DIV_ROUND_UP(IDR_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT))#define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1) /* * The IDA is even shorter since it uses a bitmap at the last level. */#define IDA_INDEX_BITS (8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS))#define IDA_MAX_PATH (DIV_ROUND_UP(IDA_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT))#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) /* * Per-cpu pool of preloaded nodes */struct radix_tree_preload { unsigned nr; /* nodes->parent points to next preallocated node */ struct radix_tree_node *nodes;};static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; static inline struct radix_tree_node *entry_to_node(void *ptr){ return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);} static inline void *node_to_entry(void *ptr){ return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);} #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 inlinebool is_sibling_entry(const struct radix_tree_node *parent, void *node){ void __rcu **ptr = node; return (parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE);}#elsestatic inlinebool is_sibling_entry(const struct radix_tree_node *parent, void *node){ return false;}#endif static inline unsigned longget_slot_offset(const struct radix_tree_node *parent, void __rcu **slot){ return slot - parent->slots;} static unsigned int radix_tree_descend(const struct radix_tree_node *parent, struct radix_tree_node **nodep, unsigned long index){ unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); #ifdef CONFIG_RADIX_TREE_MULTIORDER if (radix_tree_is_internal_node(entry)) { if (is_sibling_entry(parent, entry)) { void __rcu **sibentry; sibentry = (void __rcu **) entry_to_node(entry); offset = get_slot_offset(parent, sibentry); entry = rcu_dereference_raw(*sibentry); } }#endif *nodep = (void *)entry; return offset;} static inline gfp_t root_gfp_mask(const 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(const 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 tag){ root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));} static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag){ root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));} static inline void root_tag_clear_all(struct radix_tree_root *root){ root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1;} static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag){ return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT));} static inline unsigned root_tags_get(const struct radix_tree_root *root){ return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT;} static inline bool is_idr(const struct radix_tree_root *root){ return !!(root->gfp_mask & ROOT_IS_IDR);} /* * Returns 1 if any slot in the node has this tag set. * Otherwise returns 0. */static inline int any_tag_set(const 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;} static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag){ bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);} /** * 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(struct radix_tree_node *node, unsigned int tag, unsigned long offset){ const unsigned long *addr = node->tags[tag]; if (offset < RADIX_TREE_MAP_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 < RADIX_TREE_MAP_SIZE) { tmp = *++addr; if (tmp) return __ffs(tmp) + offset; offset += BITS_PER_LONG; } } return RADIX_TREE_MAP_SIZE;} static unsigned int iter_offset(const struct radix_tree_iter *iter){ return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK;} /* * 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;} static inline unsigned long node_maxindex(const struct radix_tree_node *node){ return shift_maxindex(node->shift);} static unsigned long next_index(unsigned long index, const struct radix_tree_node *node, unsigned long offset){ return (index & ~node_maxindex(node)) + (offset << node->shift);} #ifndef __KERNEL__static void dump_node(struct radix_tree_node *node, unsigned long index){ unsigned long i; pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d\n", node, node->offset, index, index | node_maxindex(node), node->parent, node->tags[0][0], node->tags[1][0], node->tags[2][0], node->shift, node->count, node->exceptional); 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 (entry == RADIX_TREE_RETRY) { pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n", i, first, last, node); } else if (!radix_tree_is_internal_node(entry)) { pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n", entry, i, first, last, node); } else if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n", entry, i, first, last, node, *(void **)entry_to_node(entry)); } else { dump_node(entry_to_node(entry), first); } }} /* 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 >> ROOT_TAG_SHIFT); if (!radix_tree_is_internal_node(root->rnode)) return; dump_node(entry_to_node(root->rnode), 0);} static void dump_ida_node(void *entry, unsigned long index){ unsigned long i; if (!entry) return; if (radix_tree_is_internal_node(entry)) { struct radix_tree_node *node = entry_to_node(entry); pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n", node, node->offset, index * IDA_BITMAP_BITS, ((index | node_maxindex(node)) + 1) * IDA_BITMAP_BITS - 1, node->parent, node->tags[0][0], node->shift, node->count); for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) dump_ida_node(node->slots[i], index | (i << node->shift)); } else if (radix_tree_exceptional_entry(entry)) { pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n", entry, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, index * IDA_BITMAP_BITS + BITS_PER_LONG - RADIX_TREE_EXCEPTIONAL_SHIFT, (unsigned long)entry >> RADIX_TREE_EXCEPTIONAL_SHIFT); } else { struct ida_bitmap *bitmap = entry; pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, (index + 1) * IDA_BITMAP_BITS - 1); for (i = 0; i < IDA_BITMAP_LONGS; i++) pr_cont(" %lx", bitmap->bitmap[i]); pr_cont("\n"); }} static void ida_dump(struct ida *ida){ struct radix_tree_root *root = &ida->ida_rt; pr_debug("ida: %p node %p free %d\n", ida, root->rnode, root->gfp_mask >> ROOT_TAG_SHIFT); dump_ida_node(root->rnode, 0);}#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(gfp_t gfp_mask, struct radix_tree_node *parent, struct radix_tree_root *root, unsigned int shift, unsigned int offset, unsigned int count, unsigned int exceptional){ struct radix_tree_node *ret = NULL; /* * 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 to the memory * cgroup. */ ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask | __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->parent; 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);out: BUG_ON(radix_tree_is_internal_node(ret)); if (ret) { ret->shift = shift; ret->offset = offset; ret->count = count; ret->exceptional = exceptional; ret->parent = parent; ret->root = root; } 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); /* * Must only free zeroed nodes into the slab. We can be left with * non-NULL entries by radix_tree_free_nodes, so clear the entries * and tags here. */ memset(node->slots, 0, sizeof(node->slots)); memset(node->tags, 0, sizeof(node->tags)); INIT_LIST_HEAD(&node->private_list); 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_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). */static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr){ struct radix_tree_preload *rtp; struct radix_tree_node *node; int ret = -ENOMEM; /* * Nodes preloaded by one cgroup can be be used by another cgroup, so * they should never be accounted to any particular memory cgroup. */ gfp_mask &= ~__GFP_ACCOUNT; preempt_disable(); rtp = this_cpu_ptr(&radix_tree_preloads); while (rtp->nr < nr) { 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 < nr) { node->parent = rtp->nodes; rtp->nodes = node; rtp->nr++; } else { kmem_cache_free(radix_tree_node_cachep, node); } } ret = 0;out: return ret;} /*Lines 1–500 of 2297. Load more
/* * 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/bitmap.h> #include <linux/bitops.h> #include <linux/cpu.h> #include <linux/errno.h> #include <linux/export.h> #include <linux/idr.h> #include <linux/init.h> #include <linux/kernel.h> #include <linux/kmemleak.h> #include <linux/percpu.h> #include <linux/preempt.h> /* in_interrupt() */ #include <linux/radix-tree.h> #include <linux/rcupdate.h> #include <linux/slab.h> #include <linux/string.h> /* Number of nodes in fully populated tree of given height */ static unsigned long height_to_maxnodes[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) /* * The IDR does not have to be as high as the radix tree since it uses * signed integers, not unsigned longs. */ #define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1) #define IDR_MAX_PATH (DIV_ROUND_UP(IDR_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) #define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1) /* * The IDA is even shorter since it uses a bitmap at the last level. */ #define IDA_INDEX_BITS (8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS)) #define IDA_MAX_PATH (DIV_ROUND_UP(IDA_INDEX_BITS, \ RADIX_TREE_MAP_SHIFT)) #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) /* * Per-cpu pool of preloaded nodes */ struct radix_tree_preload { unsigned nr; /* nodes->parent points to next preallocated node */ struct radix_tree_node *nodes; }; static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, }; static inline struct radix_tree_node *entry_to_node(void *ptr) { return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE); } static inline void *node_to_entry(void *ptr) { return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE); } #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(const struct radix_tree_node *parent, void *node) { void __rcu **ptr = node; return (parent->slots <= ptr) && (ptr < parent->slots + RADIX_TREE_MAP_SIZE); } #else static inline bool is_sibling_entry(const struct radix_tree_node *parent, void *node) { return false; } #endif static inline unsigned long get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot) { return slot - parent->slots; } static unsigned int radix_tree_descend(const struct radix_tree_node *parent, struct radix_tree_node **nodep, unsigned long index) { unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK; void __rcu **entry = rcu_dereference_raw(parent->slots[offset]); #ifdef CONFIG_RADIX_TREE_MULTIORDER if (radix_tree_is_internal_node(entry)) { if (is_sibling_entry(parent, entry)) { void __rcu **sibentry; sibentry = (void __rcu **) entry_to_node(entry); offset = get_slot_offset(parent, sibentry); entry = rcu_dereference_raw(*sibentry); } } #endif *nodep = (void *)entry; return offset; } static inline gfp_t root_gfp_mask(const 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(const 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 tag) { root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT)); } static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag) { root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT)); } static inline void root_tag_clear_all(struct radix_tree_root *root) { root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1; } static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag) { return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT)); } static inline unsigned root_tags_get(const struct radix_tree_root *root) { return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT; } static inline bool is_idr(const struct radix_tree_root *root) { return !!(root->gfp_mask & ROOT_IS_IDR); } /* * Returns 1 if any slot in the node has this tag set. * Otherwise returns 0. */ static inline int any_tag_set(const 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; } static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag) { bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE); } /** * 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(struct radix_tree_node *node, unsigned int tag, unsigned long offset) { const unsigned long *addr = node->tags[tag]; if (offset < RADIX_TREE_MAP_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 < RADIX_TREE_MAP_SIZE) { tmp = *++addr; if (tmp) return __ffs(tmp) + offset; offset += BITS_PER_LONG; } } return RADIX_TREE_MAP_SIZE; } static unsigned int iter_offset(const struct radix_tree_iter *iter) { return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK; } /* * 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; } static inline unsigned long node_maxindex(const struct radix_tree_node *node) { return shift_maxindex(node->shift); } static unsigned long next_index(unsigned long index, const struct radix_tree_node *node, unsigned long offset) { return (index & ~node_maxindex(node)) + (offset << node->shift); } #ifndef __KERNEL__ static void dump_node(struct radix_tree_node *node, unsigned long index) { unsigned long i; pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d\n", node, node->offset, index, index | node_maxindex(node), node->parent, node->tags[0][0], node->tags[1][0], node->tags[2][0], node->shift, node->count, node->exceptional); 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 (entry == RADIX_TREE_RETRY) { pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n", i, first, last, node); } else if (!radix_tree_is_internal_node(entry)) { pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n", entry, i, first, last, node); } else if (is_sibling_entry(node, entry)) { pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n", entry, i, first, last, node, *(void **)entry_to_node(entry)); } else { dump_node(entry_to_node(entry), first); } } } /* 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 >> ROOT_TAG_SHIFT); if (!radix_tree_is_internal_node(root->rnode)) return; dump_node(entry_to_node(root->rnode), 0); } static void dump_ida_node(void *entry, unsigned long index) { unsigned long i; if (!entry) return; if (radix_tree_is_internal_node(entry)) { struct radix_tree_node *node = entry_to_node(entry); pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n", node, node->offset, index * IDA_BITMAP_BITS, ((index | node_maxindex(node)) + 1) * IDA_BITMAP_BITS - 1, node->parent, node->tags[0][0], node->shift, node->count); for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) dump_ida_node(node->slots[i], index | (i << node->shift)); } else if (radix_tree_exceptional_entry(entry)) { pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n", entry, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, index * IDA_BITMAP_BITS + BITS_PER_LONG - RADIX_TREE_EXCEPTIONAL_SHIFT, (unsigned long)entry >> RADIX_TREE_EXCEPTIONAL_SHIFT); } else { struct ida_bitmap *bitmap = entry; pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap, (int)(index & RADIX_TREE_MAP_MASK), index * IDA_BITMAP_BITS, (index + 1) * IDA_BITMAP_BITS - 1); for (i = 0; i < IDA_BITMAP_LONGS; i++) pr_cont(" %lx", bitmap->bitmap[i]); pr_cont("\n"); } } static void ida_dump(struct ida *ida) { struct radix_tree_root *root = &ida->ida_rt; pr_debug("ida: %p node %p free %d\n", ida, root->rnode, root->gfp_mask >> ROOT_TAG_SHIFT); dump_ida_node(root->rnode, 0); } #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(gfp_t gfp_mask, struct radix_tree_node *parent, struct radix_tree_root *root, unsigned int shift, unsigned int offset, unsigned int count, unsigned int exceptional) { struct radix_tree_node *ret = NULL; /* * 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 to the memory * cgroup. */ ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask | __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->parent; 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); out: BUG_ON(radix_tree_is_internal_node(ret)); if (ret) { ret->shift = shift; ret->offset = offset; ret->count = count; ret->exceptional = exceptional; ret->parent = parent; ret->root = root; } 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); /* * Must only free zeroed nodes into the slab. We can be left with * non-NULL entries by radix_tree_free_nodes, so clear the entries * and tags here. */ memset(node->slots, 0, sizeof(node->slots)); memset(node->tags, 0, sizeof(node->tags)); INIT_LIST_HEAD(&node->private_list); kmem_cache_free(radix_tree_node_cachep, node); } static inline void radix_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_DIRECT_RECLAIM being passed to INIT_RADIX_TREE(). */ static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr) { struct radix_tree_preload *rtp; struct radix_tree_node *node; int ret = -ENOMEM; /* * Nodes preloaded by one cgroup can be be used by another cgroup, so * they should never be accounted to any particular memory cgroup. */ gfp_mask &= ~__GFP_ACCOUNT; preempt_disable(); rtp = this_cpu_ptr(&radix_tree_preloads); while (rtp->nr < nr) { 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 < nr) { node->parent = rtp->nodes; rtp->nodes = node; rtp->nr++; } else { kmem_cache_free(radix_tree_node_cachep, node); } } ret = 0; out: return ret; } /*