blob: 5ed506d648c4e53ee955e9c19b942fd0d666eee1 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * Copyright (C) 2001 Momchil Velikov
3 * Portions Copyright (C) 2001 Christoph Hellwig
Christoph Lametercde53532008-07-04 09:59:22 -07004 * Copyright (C) 2005 SGI, Christoph Lameter
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08005 * Copyright (C) 2006 Nick Piggin
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07006 * Copyright (C) 2012 Konstantin Khlebnikov
Matthew Wilcox6b053b82016-05-20 17:02:58 -07007 * Copyright (C) 2016 Intel, Matthew Wilcox
8 * Copyright (C) 2016 Intel, Ross Zwisler
Linus Torvalds1da177e2005-04-16 15:20:36 -07009 *
10 * This program is free software; you can redistribute it and/or
11 * modify it under the terms of the GNU General Public License as
12 * published by the Free Software Foundation; either version 2, or (at
13 * your option) any later version.
14 *
15 * This program is distributed in the hope that it will be useful, but
16 * WITHOUT ANY WARRANTY; without even the implied warranty of
17 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
18 * General Public License for more details.
19 *
20 * You should have received a copy of the GNU General Public License
21 * along with this program; if not, write to the Free Software
22 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
23 */
24
Matthew Wilcox0a835c42016-12-20 10:27:56 -050025#include <linux/bitmap.h>
26#include <linux/bitops.h>
Matthew Wilcoxe157b552016-12-14 15:09:01 -080027#include <linux/cpu.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070028#include <linux/errno.h>
Matthew Wilcox0a835c42016-12-20 10:27:56 -050029#include <linux/export.h>
30#include <linux/idr.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070031#include <linux/init.h>
32#include <linux/kernel.h>
Catalin Marinasce80b062014-06-06 14:38:18 -070033#include <linux/kmemleak.h>
Matthew Wilcox0a835c42016-12-20 10:27:56 -050034#include <linux/percpu.h>
Frederic Weisbecker92cf2112015-05-12 16:41:46 +020035#include <linux/preempt.h> /* in_interrupt() */
Matthew Wilcox0a835c42016-12-20 10:27:56 -050036#include <linux/radix-tree.h>
37#include <linux/rcupdate.h>
38#include <linux/slab.h>
39#include <linux/string.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070040
41
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -070042/* Number of nodes in fully populated tree of given height */
43static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly;
44
Jeff Moyer26fb1582007-10-16 01:24:49 -070045/*
Linus Torvalds1da177e2005-04-16 15:20:36 -070046 * Radix tree node cache.
47 */
Christoph Lametere18b8902006-12-06 20:33:20 -080048static struct kmem_cache *radix_tree_node_cachep;
Linus Torvalds1da177e2005-04-16 15:20:36 -070049
50/*
Nick Piggin55368052012-05-29 15:07:34 -070051 * The radix tree is variable-height, so an insert operation not only has
52 * to build the branch to its corresponding item, it also has to build the
53 * branch to existing items if the size has to be increased (by
54 * radix_tree_extend).
55 *
56 * The worst case is a zero height tree with just a single item at index 0,
57 * and then inserting an item at index ULONG_MAX. This requires 2 new branches
58 * of RADIX_TREE_MAX_PATH size to be created, with only the root node shared.
59 * Hence:
60 */
61#define RADIX_TREE_PRELOAD_SIZE (RADIX_TREE_MAX_PATH * 2 - 1)
62
63/*
Matthew Wilcox0a835c42016-12-20 10:27:56 -050064 * The IDR does not have to be as high as the radix tree since it uses
65 * signed integers, not unsigned longs.
66 */
67#define IDR_INDEX_BITS (8 /* CHAR_BIT */ * sizeof(int) - 1)
68#define IDR_MAX_PATH (DIV_ROUND_UP(IDR_INDEX_BITS, \
69 RADIX_TREE_MAP_SHIFT))
70#define IDR_PRELOAD_SIZE (IDR_MAX_PATH * 2 - 1)
71
72/*
Matthew Wilcox7ad3d4d2016-12-16 11:55:56 -050073 * The IDA is even shorter since it uses a bitmap at the last level.
74 */
75#define IDA_INDEX_BITS (8 * sizeof(int) - 1 - ilog2(IDA_BITMAP_BITS))
76#define IDA_MAX_PATH (DIV_ROUND_UP(IDA_INDEX_BITS, \
77 RADIX_TREE_MAP_SHIFT))
78#define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1)
79
80/*
Linus Torvalds1da177e2005-04-16 15:20:36 -070081 * Per-cpu pool of preloaded nodes
82 */
83struct radix_tree_preload {
Matthew Wilcox2fcd9002016-05-20 17:03:04 -070084 unsigned nr;
Matthew Wilcox1293d5c2017-01-16 16:41:29 -050085 /* nodes->parent points to next preallocated node */
Kirill A. Shutemov9d2a8da2015-06-25 15:02:19 -070086 struct radix_tree_node *nodes;
Linus Torvalds1da177e2005-04-16 15:20:36 -070087};
Harvey Harrison8cef7d52009-01-06 14:40:50 -080088static DEFINE_PER_CPU(struct radix_tree_preload, radix_tree_preloads) = { 0, };
Linus Torvalds1da177e2005-04-16 15:20:36 -070089
Matthew Wilcox148deab2016-12-14 15:08:49 -080090static inline struct radix_tree_node *entry_to_node(void *ptr)
91{
92 return (void *)((unsigned long)ptr & ~RADIX_TREE_INTERNAL_NODE);
93}
94
Matthew Wilcoxa4db4dc2016-05-20 17:03:24 -070095static inline void *node_to_entry(void *ptr)
Nick Piggin27d20fd2010-11-11 14:05:19 -080096{
Matthew Wilcox30ff46cc2016-05-20 17:03:22 -070097 return (void *)((unsigned long)ptr | RADIX_TREE_INTERNAL_NODE);
Nick Piggin27d20fd2010-11-11 14:05:19 -080098}
99
Matthew Wilcoxa4db4dc2016-05-20 17:03:24 -0700100#define RADIX_TREE_RETRY node_to_entry(NULL)
Matthew Wilcoxafe0e392016-05-20 17:02:17 -0700101
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700102#ifdef CONFIG_RADIX_TREE_MULTIORDER
103/* Sibling slots point directly to another slot in the same node */
Matthew Wilcox35534c82016-12-19 17:43:19 -0500104static inline
105bool is_sibling_entry(const struct radix_tree_node *parent, void *node)
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700106{
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500107 void __rcu **ptr = node;
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700108 return (parent->slots <= ptr) &&
109 (ptr < parent->slots + RADIX_TREE_MAP_SIZE);
110}
111#else
Matthew Wilcox35534c82016-12-19 17:43:19 -0500112static inline
113bool is_sibling_entry(const struct radix_tree_node *parent, void *node)
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700114{
115 return false;
116}
117#endif
118
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500119static inline unsigned long
120get_slot_offset(const struct radix_tree_node *parent, void __rcu **slot)
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700121{
122 return slot - parent->slots;
123}
124
Matthew Wilcox35534c82016-12-19 17:43:19 -0500125static unsigned int radix_tree_descend(const struct radix_tree_node *parent,
Matthew Wilcox9e85d812016-05-20 17:03:48 -0700126 struct radix_tree_node **nodep, unsigned long index)
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700127{
Matthew Wilcox9e85d812016-05-20 17:03:48 -0700128 unsigned int offset = (index >> parent->shift) & RADIX_TREE_MAP_MASK;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500129 void __rcu **entry = rcu_dereference_raw(parent->slots[offset]);
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700130
131#ifdef CONFIG_RADIX_TREE_MULTIORDER
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700132 if (radix_tree_is_internal_node(entry)) {
Linus Torvalds8d2c0d32016-09-25 13:32:46 -0700133 if (is_sibling_entry(parent, entry)) {
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500134 void __rcu **sibentry;
135 sibentry = (void __rcu **) entry_to_node(entry);
Linus Torvalds8d2c0d32016-09-25 13:32:46 -0700136 offset = get_slot_offset(parent, sibentry);
137 entry = rcu_dereference_raw(*sibentry);
Matthew Wilcoxdb050f22016-05-20 17:01:57 -0700138 }
139 }
140#endif
141
142 *nodep = (void *)entry;
143 return offset;
144}
145
Matthew Wilcox35534c82016-12-19 17:43:19 -0500146static inline gfp_t root_gfp_mask(const struct radix_tree_root *root)
Nick Piggin612d6c12006-06-23 02:03:22 -0700147{
148 return root->gfp_mask & __GFP_BITS_MASK;
149}
150
Nick Piggin643b52b2008-06-12 15:21:52 -0700151static inline void tag_set(struct radix_tree_node *node, unsigned int tag,
152 int offset)
153{
154 __set_bit(offset, node->tags[tag]);
155}
156
157static inline void tag_clear(struct radix_tree_node *node, unsigned int tag,
158 int offset)
159{
160 __clear_bit(offset, node->tags[tag]);
161}
162
Matthew Wilcox35534c82016-12-19 17:43:19 -0500163static inline int tag_get(const struct radix_tree_node *node, unsigned int tag,
Nick Piggin643b52b2008-06-12 15:21:52 -0700164 int offset)
165{
166 return test_bit(offset, node->tags[tag]);
167}
168
Matthew Wilcox35534c82016-12-19 17:43:19 -0500169static inline void root_tag_set(struct radix_tree_root *root, unsigned tag)
Nick Piggin643b52b2008-06-12 15:21:52 -0700170{
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500171 root->gfp_mask |= (__force gfp_t)(1 << (tag + ROOT_TAG_SHIFT));
Nick Piggin643b52b2008-06-12 15:21:52 -0700172}
173
Matthew Wilcox2fcd9002016-05-20 17:03:04 -0700174static inline void root_tag_clear(struct radix_tree_root *root, unsigned tag)
Nick Piggin643b52b2008-06-12 15:21:52 -0700175{
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500176 root->gfp_mask &= (__force gfp_t)~(1 << (tag + ROOT_TAG_SHIFT));
Nick Piggin643b52b2008-06-12 15:21:52 -0700177}
178
179static inline void root_tag_clear_all(struct radix_tree_root *root)
180{
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500181 root->gfp_mask &= (1 << ROOT_TAG_SHIFT) - 1;
Nick Piggin643b52b2008-06-12 15:21:52 -0700182}
183
Matthew Wilcox35534c82016-12-19 17:43:19 -0500184static inline int root_tag_get(const struct radix_tree_root *root, unsigned tag)
Nick Piggin643b52b2008-06-12 15:21:52 -0700185{
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500186 return (__force int)root->gfp_mask & (1 << (tag + ROOT_TAG_SHIFT));
Nick Piggin643b52b2008-06-12 15:21:52 -0700187}
188
Matthew Wilcox35534c82016-12-19 17:43:19 -0500189static inline unsigned root_tags_get(const struct radix_tree_root *root)
Matthew Wilcox7b60e9a2016-05-20 17:02:23 -0700190{
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500191 return (__force unsigned)root->gfp_mask >> ROOT_TAG_SHIFT;
192}
193
194static inline bool is_idr(const struct radix_tree_root *root)
195{
196 return !!(root->gfp_mask & ROOT_IS_IDR);
Matthew Wilcox7b60e9a2016-05-20 17:02:23 -0700197}
198
Nick Piggin643b52b2008-06-12 15:21:52 -0700199/*
200 * Returns 1 if any slot in the node has this tag set.
201 * Otherwise returns 0.
202 */
Matthew Wilcox35534c82016-12-19 17:43:19 -0500203static inline int any_tag_set(const struct radix_tree_node *node,
204 unsigned int tag)
Nick Piggin643b52b2008-06-12 15:21:52 -0700205{
Matthew Wilcox2fcd9002016-05-20 17:03:04 -0700206 unsigned idx;
Nick Piggin643b52b2008-06-12 15:21:52 -0700207 for (idx = 0; idx < RADIX_TREE_TAG_LONGS; idx++) {
208 if (node->tags[tag][idx])
209 return 1;
210 }
211 return 0;
212}
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700213
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500214static inline void all_tag_set(struct radix_tree_node *node, unsigned int tag)
215{
216 bitmap_fill(node->tags[tag], RADIX_TREE_MAP_SIZE);
217}
218
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700219/**
220 * radix_tree_find_next_bit - find the next set bit in a memory region
221 *
222 * @addr: The address to base the search on
223 * @size: The bitmap size in bits
224 * @offset: The bitnumber to start searching at
225 *
226 * Unrollable variant of find_next_bit() for constant size arrays.
227 * Tail bits starting from size to roundup(size, BITS_PER_LONG) must be zero.
228 * Returns next bit offset, or size if nothing found.
229 */
230static __always_inline unsigned long
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -0800231radix_tree_find_next_bit(struct radix_tree_node *node, unsigned int tag,
232 unsigned long offset)
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700233{
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -0800234 const unsigned long *addr = node->tags[tag];
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700235
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -0800236 if (offset < RADIX_TREE_MAP_SIZE) {
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700237 unsigned long tmp;
238
239 addr += offset / BITS_PER_LONG;
240 tmp = *addr >> (offset % BITS_PER_LONG);
241 if (tmp)
242 return __ffs(tmp) + offset;
243 offset = (offset + BITS_PER_LONG) & ~(BITS_PER_LONG - 1);
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -0800244 while (offset < RADIX_TREE_MAP_SIZE) {
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700245 tmp = *++addr;
246 if (tmp)
247 return __ffs(tmp) + offset;
248 offset += BITS_PER_LONG;
249 }
250 }
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -0800251 return RADIX_TREE_MAP_SIZE;
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -0700252}
253
Matthew Wilcox268f42d2016-12-14 15:08:55 -0800254static unsigned int iter_offset(const struct radix_tree_iter *iter)
255{
256 return (iter->index >> iter_shift(iter)) & RADIX_TREE_MAP_MASK;
257}
258
Matthew Wilcox218ed752016-12-14 15:08:43 -0800259/*
260 * The maximum index which can be stored in a radix tree
261 */
262static inline unsigned long shift_maxindex(unsigned int shift)
263{
264 return (RADIX_TREE_MAP_SIZE << shift) - 1;
265}
266
Matthew Wilcox35534c82016-12-19 17:43:19 -0500267static inline unsigned long node_maxindex(const struct radix_tree_node *node)
Matthew Wilcox218ed752016-12-14 15:08:43 -0800268{
269 return shift_maxindex(node->shift);
270}
271
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500272static unsigned long next_index(unsigned long index,
273 const struct radix_tree_node *node,
274 unsigned long offset)
275{
276 return (index & ~node_maxindex(node)) + (offset << node->shift);
277}
278
Ross Zwisler0796c582016-05-20 17:02:55 -0700279#ifndef __KERNEL__
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700280static void dump_node(struct radix_tree_node *node, unsigned long index)
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700281{
Ross Zwisler0796c582016-05-20 17:02:55 -0700282 unsigned long i;
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700283
Matthew Wilcox218ed752016-12-14 15:08:43 -0800284 pr_debug("radix node: %p offset %d indices %lu-%lu parent %p tags %lx %lx %lx shift %d count %d exceptional %d\n",
285 node, node->offset, index, index | node_maxindex(node),
286 node->parent,
Ross Zwisler0796c582016-05-20 17:02:55 -0700287 node->tags[0][0], node->tags[1][0], node->tags[2][0],
Matthew Wilcox218ed752016-12-14 15:08:43 -0800288 node->shift, node->count, node->exceptional);
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700289
Ross Zwisler0796c582016-05-20 17:02:55 -0700290 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++) {
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700291 unsigned long first = index | (i << node->shift);
292 unsigned long last = first | ((1UL << node->shift) - 1);
Ross Zwisler0796c582016-05-20 17:02:55 -0700293 void *entry = node->slots[i];
294 if (!entry)
295 continue;
Matthew Wilcox218ed752016-12-14 15:08:43 -0800296 if (entry == RADIX_TREE_RETRY) {
297 pr_debug("radix retry offset %ld indices %lu-%lu parent %p\n",
298 i, first, last, node);
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700299 } else if (!radix_tree_is_internal_node(entry)) {
Matthew Wilcox218ed752016-12-14 15:08:43 -0800300 pr_debug("radix entry %p offset %ld indices %lu-%lu parent %p\n",
301 entry, i, first, last, node);
302 } else if (is_sibling_entry(node, entry)) {
303 pr_debug("radix sblng %p offset %ld indices %lu-%lu parent %p val %p\n",
304 entry, i, first, last, node,
305 *(void **)entry_to_node(entry));
Ross Zwisler0796c582016-05-20 17:02:55 -0700306 } else {
Matthew Wilcox4dd6c092016-05-20 17:03:27 -0700307 dump_node(entry_to_node(entry), first);
Ross Zwisler0796c582016-05-20 17:02:55 -0700308 }
309 }
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700310}
311
312/* For debug */
313static void radix_tree_dump(struct radix_tree_root *root)
314{
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700315 pr_debug("radix root: %p rnode %p tags %x\n",
316 root, root->rnode,
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500317 root->gfp_mask >> ROOT_TAG_SHIFT);
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700318 if (!radix_tree_is_internal_node(root->rnode))
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700319 return;
Matthew Wilcox4dd6c092016-05-20 17:03:27 -0700320 dump_node(entry_to_node(root->rnode), 0);
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700321}
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500322
323static void dump_ida_node(void *entry, unsigned long index)
324{
325 unsigned long i;
326
327 if (!entry)
328 return;
329
330 if (radix_tree_is_internal_node(entry)) {
331 struct radix_tree_node *node = entry_to_node(entry);
332
333 pr_debug("ida node: %p offset %d indices %lu-%lu parent %p free %lx shift %d count %d\n",
334 node, node->offset, index * IDA_BITMAP_BITS,
335 ((index | node_maxindex(node)) + 1) *
336 IDA_BITMAP_BITS - 1,
337 node->parent, node->tags[0][0], node->shift,
338 node->count);
339 for (i = 0; i < RADIX_TREE_MAP_SIZE; i++)
340 dump_ida_node(node->slots[i],
341 index | (i << node->shift));
Matthew Wilcoxd37cacc2016-12-17 08:18:17 -0500342 } else if (radix_tree_exceptional_entry(entry)) {
343 pr_debug("ida excp: %p offset %d indices %lu-%lu data %lx\n",
344 entry, (int)(index & RADIX_TREE_MAP_MASK),
345 index * IDA_BITMAP_BITS,
346 index * IDA_BITMAP_BITS + BITS_PER_LONG -
347 RADIX_TREE_EXCEPTIONAL_SHIFT,
348 (unsigned long)entry >>
349 RADIX_TREE_EXCEPTIONAL_SHIFT);
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500350 } else {
351 struct ida_bitmap *bitmap = entry;
352
353 pr_debug("ida btmp: %p offset %d indices %lu-%lu data", bitmap,
354 (int)(index & RADIX_TREE_MAP_MASK),
355 index * IDA_BITMAP_BITS,
356 (index + 1) * IDA_BITMAP_BITS - 1);
357 for (i = 0; i < IDA_BITMAP_LONGS; i++)
358 pr_cont(" %lx", bitmap->bitmap[i]);
359 pr_cont("\n");
360 }
361}
362
363static void ida_dump(struct ida *ida)
364{
365 struct radix_tree_root *root = &ida->ida_rt;
Matthew Wilcox7ad3d4d2016-12-16 11:55:56 -0500366 pr_debug("ida: %p node %p free %d\n", ida, root->rnode,
367 root->gfp_mask >> ROOT_TAG_SHIFT);
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500368 dump_ida_node(root->rnode, 0);
369}
Matthew Wilcox7cf19af2016-03-17 14:21:57 -0700370#endif
371
Linus Torvalds1da177e2005-04-16 15:20:36 -0700372/*
373 * This assumes that the caller has performed appropriate preallocation, and
374 * that the caller has pinned this thread of control to the current CPU.
375 */
376static struct radix_tree_node *
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500377radix_tree_node_alloc(gfp_t gfp_mask, struct radix_tree_node *parent,
Matthew Wilcoxd58275b2017-01-16 17:10:21 -0500378 struct radix_tree_root *root,
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800379 unsigned int shift, unsigned int offset,
380 unsigned int count, unsigned int exceptional)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381{
Nick Piggine2848a02008-02-04 22:29:10 -0800382 struct radix_tree_node *ret = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700383
Jan Kara5e4c0d972013-09-11 14:26:05 -0700384 /*
Matthew Wilcox2fcd9002016-05-20 17:03:04 -0700385 * Preload code isn't irq safe and it doesn't make sense to use
386 * preloading during an interrupt anyway as all the allocations have
387 * to be atomic. So just do normal allocation when in interrupt.
Jan Kara5e4c0d972013-09-11 14:26:05 -0700388 */
Mel Gormand0164ad2015-11-06 16:28:21 -0800389 if (!gfpflags_allow_blocking(gfp_mask) && !in_interrupt()) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700390 struct radix_tree_preload *rtp;
391
Nick Piggine2848a02008-02-04 22:29:10 -0800392 /*
Vladimir Davydov58e698a2016-03-17 14:18:36 -0700393 * Even if the caller has preloaded, try to allocate from the
Vladimir Davydov05eb6e72016-08-02 14:03:01 -0700394 * cache first for the new node to get accounted to the memory
395 * cgroup.
Vladimir Davydov58e698a2016-03-17 14:18:36 -0700396 */
397 ret = kmem_cache_alloc(radix_tree_node_cachep,
Vladimir Davydov05eb6e72016-08-02 14:03:01 -0700398 gfp_mask | __GFP_NOWARN);
Vladimir Davydov58e698a2016-03-17 14:18:36 -0700399 if (ret)
400 goto out;
401
402 /*
Nick Piggine2848a02008-02-04 22:29:10 -0800403 * Provided the caller has preloaded here, we will always
404 * succeed in getting a node here (and never reach
405 * kmem_cache_alloc)
406 */
Christoph Lameter7c8e0182014-06-04 16:07:56 -0700407 rtp = this_cpu_ptr(&radix_tree_preloads);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700408 if (rtp->nr) {
Kirill A. Shutemov9d2a8da2015-06-25 15:02:19 -0700409 ret = rtp->nodes;
Matthew Wilcox1293d5c2017-01-16 16:41:29 -0500410 rtp->nodes = ret->parent;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700411 rtp->nr--;
412 }
Catalin Marinasce80b062014-06-06 14:38:18 -0700413 /*
414 * Update the allocation stack trace as this is more useful
415 * for debugging.
416 */
417 kmemleak_update_trace(ret);
Vladimir Davydov58e698a2016-03-17 14:18:36 -0700418 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700419 }
Vladimir Davydov05eb6e72016-08-02 14:03:01 -0700420 ret = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Vladimir Davydov58e698a2016-03-17 14:18:36 -0700421out:
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700422 BUG_ON(radix_tree_is_internal_node(ret));
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800423 if (ret) {
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800424 ret->shift = shift;
425 ret->offset = offset;
426 ret->count = count;
427 ret->exceptional = exceptional;
Matthew Wilcoxd58275b2017-01-16 17:10:21 -0500428 ret->parent = parent;
429 ret->root = root;
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800430 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700431 return ret;
432}
433
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800434static void radix_tree_node_rcu_free(struct rcu_head *head)
435{
436 struct radix_tree_node *node =
437 container_of(head, struct radix_tree_node, rcu_head);
Nick Piggin643b52b2008-06-12 15:21:52 -0700438
439 /*
Matthew Wilcox175542f2016-12-14 15:08:58 -0800440 * Must only free zeroed nodes into the slab. We can be left with
441 * non-NULL entries by radix_tree_free_nodes, so clear the entries
442 * and tags here.
Nick Piggin643b52b2008-06-12 15:21:52 -0700443 */
Matthew Wilcox175542f2016-12-14 15:08:58 -0800444 memset(node->slots, 0, sizeof(node->slots));
445 memset(node->tags, 0, sizeof(node->tags));
Matthew Wilcox91d9c052016-12-14 15:08:34 -0800446 INIT_LIST_HEAD(&node->private_list);
Nick Piggin643b52b2008-06-12 15:21:52 -0700447
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800448 kmem_cache_free(radix_tree_node_cachep, node);
449}
450
Linus Torvalds1da177e2005-04-16 15:20:36 -0700451static inline void
452radix_tree_node_free(struct radix_tree_node *node)
453{
Nick Piggin7cf9c2c2006-12-06 20:33:44 -0800454 call_rcu(&node->rcu_head, radix_tree_node_rcu_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700455}
456
457/*
458 * Load up this CPU's radix_tree_node buffer with sufficient objects to
459 * ensure that the addition of a single element in the tree cannot fail. On
460 * success, return zero, with preemption disabled. On error, return -ENOMEM
461 * with preemption not disabled.
David Howellsb34df792009-11-19 18:11:14 +0000462 *
463 * To make use of this facility, the radix tree must be initialised without
Mel Gormand0164ad2015-11-06 16:28:21 -0800464 * __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
Linus Torvalds1da177e2005-04-16 15:20:36 -0700465 */
Matthew Wilcox27916532016-12-14 15:09:04 -0800466static int __radix_tree_preload(gfp_t gfp_mask, unsigned nr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700467{
468 struct radix_tree_preload *rtp;
469 struct radix_tree_node *node;
470 int ret = -ENOMEM;
471
Vladimir Davydov05eb6e72016-08-02 14:03:01 -0700472 /*
473 * Nodes preloaded by one cgroup can be be used by another cgroup, so
474 * they should never be accounted to any particular memory cgroup.
475 */
476 gfp_mask &= ~__GFP_ACCOUNT;
477
Linus Torvalds1da177e2005-04-16 15:20:36 -0700478 preempt_disable();
Christoph Lameter7c8e0182014-06-04 16:07:56 -0700479 rtp = this_cpu_ptr(&radix_tree_preloads);
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -0700480 while (rtp->nr < nr) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700481 preempt_enable();
Christoph Lameter488514d2008-04-28 02:12:05 -0700482 node = kmem_cache_alloc(radix_tree_node_cachep, gfp_mask);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700483 if (node == NULL)
484 goto out;
485 preempt_disable();
Christoph Lameter7c8e0182014-06-04 16:07:56 -0700486 rtp = this_cpu_ptr(&radix_tree_preloads);
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -0700487 if (rtp->nr < nr) {
Matthew Wilcox1293d5c2017-01-16 16:41:29 -0500488 node->parent = rtp->nodes;
Kirill A. Shutemov9d2a8da2015-06-25 15:02:19 -0700489 rtp->nodes = node;
490 rtp->nr++;
491 } else {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700492 kmem_cache_free(radix_tree_node_cachep, node);
Kirill A. Shutemov9d2a8da2015-06-25 15:02:19 -0700493 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700494 }
495 ret = 0;
496out:
497 return ret;
498}
Jan Kara5e4c0d972013-09-11 14:26:05 -0700499
500/*
501 * Load up this CPU's radix_tree_node buffer with sufficient objects to
502 * ensure that the addition of a single element in the tree cannot fail. On
503 * success, return zero, with preemption disabled. On error, return -ENOMEM
504 * with preemption not disabled.
505 *
506 * To make use of this facility, the radix tree must be initialised without
Mel Gormand0164ad2015-11-06 16:28:21 -0800507 * __GFP_DIRECT_RECLAIM being passed to INIT_RADIX_TREE().
Jan Kara5e4c0d972013-09-11 14:26:05 -0700508 */
509int radix_tree_preload(gfp_t gfp_mask)
510{
511 /* Warn on non-sensical use... */
Mel Gormand0164ad2015-11-06 16:28:21 -0800512 WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -0700513 return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
Jan Kara5e4c0d972013-09-11 14:26:05 -0700514}
David Chinnerd7f09232007-07-14 16:05:04 +1000515EXPORT_SYMBOL(radix_tree_preload);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700516
Nick Piggin6e954b92006-01-08 01:01:40 -0800517/*
Jan Kara5e4c0d972013-09-11 14:26:05 -0700518 * The same as above function, except we don't guarantee preloading happens.
519 * We do it, if we decide it helps. On success, return zero with preemption
520 * disabled. On error, return -ENOMEM with preemption not disabled.
521 */
522int radix_tree_maybe_preload(gfp_t gfp_mask)
523{
Mel Gormand0164ad2015-11-06 16:28:21 -0800524 if (gfpflags_allow_blocking(gfp_mask))
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -0700525 return __radix_tree_preload(gfp_mask, RADIX_TREE_PRELOAD_SIZE);
Jan Kara5e4c0d972013-09-11 14:26:05 -0700526 /* Preloading doesn't help anything with this gfp mask, skip it */
527 preempt_disable();
528 return 0;
529}
530EXPORT_SYMBOL(radix_tree_maybe_preload);
531
Matthew Wilcox27916532016-12-14 15:09:04 -0800532#ifdef CONFIG_RADIX_TREE_MULTIORDER
533/*
534 * Preload with enough objects to ensure that we can split a single entry
535 * of order @old_order into many entries of size @new_order
536 */
537int radix_tree_split_preload(unsigned int old_order, unsigned int new_order,
538 gfp_t gfp_mask)
539{
540 unsigned top = 1 << (old_order % RADIX_TREE_MAP_SHIFT);
541 unsigned layers = (old_order / RADIX_TREE_MAP_SHIFT) -
542 (new_order / RADIX_TREE_MAP_SHIFT);
543 unsigned nr = 0;
544
545 WARN_ON_ONCE(!gfpflags_allow_blocking(gfp_mask));
546 BUG_ON(new_order >= old_order);
547
548 while (layers--)
549 nr = nr * RADIX_TREE_MAP_SIZE + 1;
550 return __radix_tree_preload(gfp_mask, top * nr);
551}
552#endif
553
Jan Kara5e4c0d972013-09-11 14:26:05 -0700554/*
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -0700555 * The same as function above, but preload number of nodes required to insert
556 * (1 << order) continuous naturally-aligned elements.
557 */
558int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order)
559{
560 unsigned long nr_subtrees;
561 int nr_nodes, subtree_height;
562
563 /* Preloading doesn't help anything with this gfp mask, skip it */
564 if (!gfpflags_allow_blocking(gfp_mask)) {
565 preempt_disable();
566 return 0;
567 }
568
569 /*
570 * Calculate number and height of fully populated subtrees it takes to
571 * store (1 << order) elements.
572 */
573 nr_subtrees = 1 << order;
574 for (subtree_height = 0; nr_subtrees > RADIX_TREE_MAP_SIZE;
575 subtree_height++)
576 nr_subtrees >>= RADIX_TREE_MAP_SHIFT;
577
578 /*
579 * The worst case is zero height tree with a single item at index 0 and
580 * then inserting items starting at ULONG_MAX - (1 << order).
581 *
582 * This requires RADIX_TREE_MAX_PATH nodes to build branch from root to
583 * 0-index item.
584 */
585 nr_nodes = RADIX_TREE_MAX_PATH;
586
587 /* Plus branch to fully populated subtrees. */
588 nr_nodes += RADIX_TREE_MAX_PATH - subtree_height;
589
590 /* Root node is shared. */
591 nr_nodes--;
592
593 /* Plus nodes required to build subtrees. */
594 nr_nodes += nr_subtrees * height_to_maxnodes[subtree_height];
595
596 return __radix_tree_preload(gfp_mask, nr_nodes);
597}
598
Matthew Wilcox35534c82016-12-19 17:43:19 -0500599static unsigned radix_tree_load_root(const struct radix_tree_root *root,
Matthew Wilcox1456a432016-05-20 17:02:08 -0700600 struct radix_tree_node **nodep, unsigned long *maxindex)
601{
602 struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
603
604 *nodep = node;
605
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700606 if (likely(radix_tree_is_internal_node(node))) {
Matthew Wilcox4dd6c092016-05-20 17:03:27 -0700607 node = entry_to_node(node);
Matthew Wilcox1456a432016-05-20 17:02:08 -0700608 *maxindex = node_maxindex(node);
Matthew Wilcoxc12e51b2016-05-20 17:03:10 -0700609 return node->shift + RADIX_TREE_MAP_SHIFT;
Matthew Wilcox1456a432016-05-20 17:02:08 -0700610 }
611
612 *maxindex = 0;
613 return 0;
614}
615
Linus Torvalds1da177e2005-04-16 15:20:36 -0700616/*
617 * Extend a radix tree so it can store key @index.
618 */
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500619static int radix_tree_extend(struct radix_tree_root *root, gfp_t gfp,
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700620 unsigned long index, unsigned int shift)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700621{
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500622 void *entry;
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700623 unsigned int maxshift;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700624 int tag;
625
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700626 /* Figure out what the shift should be. */
627 maxshift = shift;
628 while (index > shift_maxindex(maxshift))
629 maxshift += RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700630
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500631 entry = rcu_dereference_raw(root->rnode);
632 if (!entry && (!is_idr(root) || root_tag_get(root, IDR_FREE)))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700633 goto out;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700634
Linus Torvalds1da177e2005-04-16 15:20:36 -0700635 do {
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500636 struct radix_tree_node *node = radix_tree_node_alloc(gfp, NULL,
Matthew Wilcoxd58275b2017-01-16 17:10:21 -0500637 root, shift, 0, 1, 0);
Matthew Wilcox2fcd9002016-05-20 17:03:04 -0700638 if (!node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700639 return -ENOMEM;
640
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500641 if (is_idr(root)) {
642 all_tag_set(node, IDR_FREE);
643 if (!root_tag_get(root, IDR_FREE)) {
644 tag_clear(node, IDR_FREE, 0);
645 root_tag_set(root, IDR_FREE);
646 }
647 } else {
648 /* Propagate the aggregated tag info to the new child */
649 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
650 if (root_tag_get(root, tag))
651 tag_set(node, tag, 0);
652 }
Linus Torvalds1da177e2005-04-16 15:20:36 -0700653 }
654
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700655 BUG_ON(shift > BITS_PER_LONG);
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500656 if (radix_tree_is_internal_node(entry)) {
657 entry_to_node(entry)->parent = node;
658 } else if (radix_tree_exceptional_entry(entry)) {
Johannes Weinerf7942432016-12-12 16:43:41 -0800659 /* Moving an exceptional root->rnode to a node */
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800660 node->exceptional = 1;
Johannes Weinerf7942432016-12-12 16:43:41 -0800661 }
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500662 /*
663 * entry was already in the radix tree, so we do not need
664 * rcu_assign_pointer here
665 */
666 node->slots[0] = (void __rcu *)entry;
667 entry = node_to_entry(node);
668 rcu_assign_pointer(root->rnode, entry);
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700669 shift += RADIX_TREE_MAP_SHIFT;
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700670 } while (shift <= maxshift);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700671out:
Matthew Wilcoxd0891262016-05-20 17:03:19 -0700672 return maxshift + RADIX_TREE_MAP_SHIFT;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700673}
674
675/**
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800676 * radix_tree_shrink - shrink radix tree to minimum height
677 * @root radix tree root
678 */
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500679static inline bool radix_tree_shrink(struct radix_tree_root *root,
Johannes Weiner4d693d02016-12-12 16:43:49 -0800680 radix_tree_update_node_t update_node,
681 void *private)
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800682{
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500683 bool shrunk = false;
684
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800685 for (;;) {
Matthew Wilcox12320d02017-02-13 15:22:48 -0500686 struct radix_tree_node *node = rcu_dereference_raw(root->rnode);
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800687 struct radix_tree_node *child;
688
689 if (!radix_tree_is_internal_node(node))
690 break;
691 node = entry_to_node(node);
692
693 /*
694 * The candidate node has more than one child, or its child
695 * is not at the leftmost slot, or the child is a multiorder
696 * entry, we cannot shrink.
697 */
698 if (node->count != 1)
699 break;
Matthew Wilcox12320d02017-02-13 15:22:48 -0500700 child = rcu_dereference_raw(node->slots[0]);
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800701 if (!child)
702 break;
703 if (!radix_tree_is_internal_node(child) && node->shift)
704 break;
705
706 if (radix_tree_is_internal_node(child))
707 entry_to_node(child)->parent = NULL;
708
709 /*
710 * We don't need rcu_assign_pointer(), since we are simply
711 * moving the node from one part of the tree to another: if it
712 * was safe to dereference the old pointer to it
713 * (node->slots[0]), it will be safe to dereference the new
714 * one (root->rnode) as far as dependent read barriers go.
715 */
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500716 root->rnode = (void __rcu *)child;
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500717 if (is_idr(root) && !tag_get(node, IDR_FREE, 0))
718 root_tag_clear(root, IDR_FREE);
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800719
720 /*
721 * We have a dilemma here. The node's slot[0] must not be
722 * NULLed in case there are concurrent lookups expecting to
723 * find the item. However if this was a bottom-level node,
724 * then it may be subject to the slot pointer being visible
725 * to callers dereferencing it. If item corresponding to
726 * slot[0] is subsequently deleted, these callers would expect
727 * their slot to become empty sooner or later.
728 *
729 * For example, lockless pagecache will look up a slot, deref
730 * the page pointer, and if the page has 0 refcount it means it
731 * was concurrently deleted from pagecache so try the deref
732 * again. Fortunately there is already a requirement for logic
733 * to retry the entire slot lookup -- the indirect pointer
734 * problem (replacing direct root node with an indirect pointer
735 * also results in a stale slot). So tag the slot as indirect
736 * to force callers to retry.
737 */
Johannes Weiner4d693d02016-12-12 16:43:49 -0800738 node->count = 0;
739 if (!radix_tree_is_internal_node(child)) {
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500740 node->slots[0] = (void __rcu *)RADIX_TREE_RETRY;
Johannes Weiner4d693d02016-12-12 16:43:49 -0800741 if (update_node)
742 update_node(node, private);
743 }
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800744
Johannes Weinerea07b862017-01-06 19:21:43 -0500745 WARN_ON_ONCE(!list_empty(&node->private_list));
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800746 radix_tree_node_free(node);
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500747 shrunk = true;
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800748 }
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500749
750 return shrunk;
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800751}
752
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500753static bool delete_node(struct radix_tree_root *root,
Johannes Weiner4d693d02016-12-12 16:43:49 -0800754 struct radix_tree_node *node,
755 radix_tree_update_node_t update_node, void *private)
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800756{
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500757 bool deleted = false;
758
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800759 do {
760 struct radix_tree_node *parent;
761
762 if (node->count) {
Matthew Wilcox12320d02017-02-13 15:22:48 -0500763 if (node_to_entry(node) ==
764 rcu_dereference_raw(root->rnode))
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500765 deleted |= radix_tree_shrink(root, update_node,
766 private);
767 return deleted;
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800768 }
769
770 parent = node->parent;
771 if (parent) {
772 parent->slots[node->offset] = NULL;
773 parent->count--;
774 } else {
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500775 /*
776 * Shouldn't the tags already have all been cleared
777 * by the caller?
778 */
779 if (!is_idr(root))
780 root_tag_clear_all(root);
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800781 root->rnode = NULL;
782 }
783
Johannes Weinerea07b862017-01-06 19:21:43 -0500784 WARN_ON_ONCE(!list_empty(&node->private_list));
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800785 radix_tree_node_free(node);
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500786 deleted = true;
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800787
788 node = parent;
789 } while (node);
Matthew Wilcox0ac398e2017-01-28 09:56:22 -0500790
791 return deleted;
Johannes Weinerf4b109c2016-12-12 16:43:46 -0800792}
793
794/**
Johannes Weiner139e5612014-04-03 14:47:54 -0700795 * __radix_tree_create - create a slot in a radix tree
Linus Torvalds1da177e2005-04-16 15:20:36 -0700796 * @root: radix tree root
797 * @index: index key
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700798 * @order: index occupies 2^order aligned slots
Johannes Weiner139e5612014-04-03 14:47:54 -0700799 * @nodep: returns node
800 * @slotp: returns slot
Linus Torvalds1da177e2005-04-16 15:20:36 -0700801 *
Johannes Weiner139e5612014-04-03 14:47:54 -0700802 * Create, if necessary, and return the node and slot for an item
803 * at position @index in the radix tree @root.
804 *
805 * Until there is more than one item in the tree, no nodes are
806 * allocated and @root->rnode is used as a direct slot instead of
807 * pointing to a node, in which case *@nodep will be NULL.
808 *
809 * Returns -ENOMEM, or 0 for success.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700810 */
Johannes Weiner139e5612014-04-03 14:47:54 -0700811int __radix_tree_create(struct radix_tree_root *root, unsigned long index,
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700812 unsigned order, struct radix_tree_node **nodep,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500813 void __rcu ***slotp)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700814{
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700815 struct radix_tree_node *node = NULL, *child;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500816 void __rcu **slot = (void __rcu **)&root->rnode;
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700817 unsigned long maxindex;
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700818 unsigned int shift, offset = 0;
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700819 unsigned long max = index | ((1UL << order) - 1);
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500820 gfp_t gfp = root_gfp_mask(root);
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700821
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700822 shift = radix_tree_load_root(root, &child, &maxindex);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700823
824 /* Make sure the tree is high enough. */
Matthew Wilcox175542f2016-12-14 15:08:58 -0800825 if (order > 0 && max == ((1UL << order) - 1))
826 max++;
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700827 if (max > maxindex) {
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500828 int error = radix_tree_extend(root, gfp, max, shift);
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700829 if (error < 0)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700830 return error;
Matthew Wilcox49ea6eb2016-05-20 17:02:11 -0700831 shift = error;
Matthew Wilcox12320d02017-02-13 15:22:48 -0500832 child = rcu_dereference_raw(root->rnode);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700833 }
834
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700835 while (shift > order) {
Matthew Wilcoxc12e51b2016-05-20 17:03:10 -0700836 shift -= RADIX_TREE_MAP_SHIFT;
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700837 if (child == NULL) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700838 /* Have to add a child node. */
Matthew Wilcoxd58275b2017-01-16 17:10:21 -0500839 child = radix_tree_node_alloc(gfp, node, root, shift,
Matthew Wilcoxe8de4342016-12-14 15:09:31 -0800840 offset, 0, 0);
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700841 if (!child)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700842 return -ENOMEM;
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700843 rcu_assign_pointer(*slot, node_to_entry(child));
844 if (node)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700845 node->count++;
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700846 } else if (!radix_tree_is_internal_node(child))
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700847 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848
849 /* Go a level down */
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700850 node = entry_to_node(child);
Matthew Wilcox9e85d812016-05-20 17:03:48 -0700851 offset = radix_tree_descend(node, &child, index);
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700852 slot = &node->slots[offset];
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700853 }
854
Johannes Weiner139e5612014-04-03 14:47:54 -0700855 if (nodep)
856 *nodep = node;
857 if (slotp)
Matthew Wilcox89148aa2016-05-20 17:03:42 -0700858 *slotp = slot;
Johannes Weiner139e5612014-04-03 14:47:54 -0700859 return 0;
860}
861
Matthew Wilcox175542f2016-12-14 15:08:58 -0800862/*
863 * Free any nodes below this node. The tree is presumed to not need
864 * shrinking, and any user data in the tree is presumed to not need a
865 * destructor called on it. If we need to add a destructor, we can
866 * add that functionality later. Note that we may not clear tags or
867 * slots from the tree as an RCU walker may still have a pointer into
868 * this subtree. We could replace the entries with RADIX_TREE_RETRY,
869 * but we'll still have to clear those in rcu_free.
870 */
871static void radix_tree_free_nodes(struct radix_tree_node *node)
872{
873 unsigned offset = 0;
874 struct radix_tree_node *child = entry_to_node(node);
875
876 for (;;) {
Matthew Wilcox12320d02017-02-13 15:22:48 -0500877 void *entry = rcu_dereference_raw(child->slots[offset]);
Matthew Wilcox175542f2016-12-14 15:08:58 -0800878 if (radix_tree_is_internal_node(entry) &&
879 !is_sibling_entry(child, entry)) {
880 child = entry_to_node(entry);
881 offset = 0;
882 continue;
883 }
884 offset++;
885 while (offset == RADIX_TREE_MAP_SIZE) {
886 struct radix_tree_node *old = child;
887 offset = child->offset + 1;
888 child = child->parent;
Matthew Wilcoxdd040b62017-01-24 15:18:16 -0800889 WARN_ON_ONCE(!list_empty(&old->private_list));
Matthew Wilcox175542f2016-12-14 15:08:58 -0800890 radix_tree_node_free(old);
891 if (old == entry_to_node(node))
892 return;
893 }
894 }
895}
896
Matthew Wilcox0a835c42016-12-20 10:27:56 -0500897#ifdef CONFIG_RADIX_TREE_MULTIORDER
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500898static inline int insert_entries(struct radix_tree_node *node,
899 void __rcu **slot, void *item, unsigned order, bool replace)
Matthew Wilcox175542f2016-12-14 15:08:58 -0800900{
901 struct radix_tree_node *child;
902 unsigned i, n, tag, offset, tags = 0;
903
904 if (node) {
Matthew Wilcoxe157b552016-12-14 15:09:01 -0800905 if (order > node->shift)
906 n = 1 << (order - node->shift);
907 else
908 n = 1;
Matthew Wilcox175542f2016-12-14 15:08:58 -0800909 offset = get_slot_offset(node, slot);
910 } else {
911 n = 1;
912 offset = 0;
913 }
914
915 if (n > 1) {
916 offset = offset & ~(n - 1);
917 slot = &node->slots[offset];
918 }
919 child = node_to_entry(slot);
920
921 for (i = 0; i < n; i++) {
922 if (slot[i]) {
923 if (replace) {
924 node->count--;
925 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
926 if (tag_get(node, tag, offset + i))
927 tags |= 1 << tag;
928 } else
929 return -EEXIST;
930 }
931 }
932
933 for (i = 0; i < n; i++) {
Matthew Wilcox12320d02017-02-13 15:22:48 -0500934 struct radix_tree_node *old = rcu_dereference_raw(slot[i]);
Matthew Wilcox175542f2016-12-14 15:08:58 -0800935 if (i) {
936 rcu_assign_pointer(slot[i], child);
937 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
938 if (tags & (1 << tag))
939 tag_clear(node, tag, offset + i);
940 } else {
941 rcu_assign_pointer(slot[i], item);
942 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
943 if (tags & (1 << tag))
944 tag_set(node, tag, offset);
945 }
946 if (radix_tree_is_internal_node(old) &&
Matthew Wilcoxe157b552016-12-14 15:09:01 -0800947 !is_sibling_entry(node, old) &&
948 (old != RADIX_TREE_RETRY))
Matthew Wilcox175542f2016-12-14 15:08:58 -0800949 radix_tree_free_nodes(old);
950 if (radix_tree_exceptional_entry(old))
951 node->exceptional--;
952 }
953 if (node) {
954 node->count += n;
955 if (radix_tree_exceptional_entry(item))
956 node->exceptional += n;
957 }
958 return n;
959}
960#else
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500961static inline int insert_entries(struct radix_tree_node *node,
962 void __rcu **slot, void *item, unsigned order, bool replace)
Matthew Wilcox175542f2016-12-14 15:08:58 -0800963{
964 if (*slot)
965 return -EEXIST;
966 rcu_assign_pointer(*slot, item);
967 if (node) {
968 node->count++;
969 if (radix_tree_exceptional_entry(item))
970 node->exceptional++;
971 }
972 return 1;
973}
974#endif
975
Johannes Weiner139e5612014-04-03 14:47:54 -0700976/**
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700977 * __radix_tree_insert - insert into a radix tree
Johannes Weiner139e5612014-04-03 14:47:54 -0700978 * @root: radix tree root
979 * @index: index key
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700980 * @order: key covers the 2^order indices around index
Johannes Weiner139e5612014-04-03 14:47:54 -0700981 * @item: item to insert
982 *
983 * Insert an item into the radix tree at position @index.
984 */
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700985int __radix_tree_insert(struct radix_tree_root *root, unsigned long index,
986 unsigned order, void *item)
Johannes Weiner139e5612014-04-03 14:47:54 -0700987{
988 struct radix_tree_node *node;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -0500989 void __rcu **slot;
Johannes Weiner139e5612014-04-03 14:47:54 -0700990 int error;
991
Matthew Wilcoxb194d162016-05-20 17:03:30 -0700992 BUG_ON(radix_tree_is_internal_node(item));
Johannes Weiner139e5612014-04-03 14:47:54 -0700993
Matthew Wilcoxe6145232016-03-17 14:21:54 -0700994 error = __radix_tree_create(root, index, order, &node, &slot);
Johannes Weiner139e5612014-04-03 14:47:54 -0700995 if (error)
996 return error;
Matthew Wilcox175542f2016-12-14 15:08:58 -0800997
998 error = insert_entries(node, slot, item, order, false);
999 if (error < 0)
1000 return error;
Christoph Lameter201b6262005-09-06 15:16:46 -07001001
Nick Piggin612d6c12006-06-23 02:03:22 -07001002 if (node) {
Matthew Wilcox7b60e9a2016-05-20 17:02:23 -07001003 unsigned offset = get_slot_offset(node, slot);
Matthew Wilcox7b60e9a2016-05-20 17:02:23 -07001004 BUG_ON(tag_get(node, 0, offset));
1005 BUG_ON(tag_get(node, 1, offset));
1006 BUG_ON(tag_get(node, 2, offset));
Nick Piggin612d6c12006-06-23 02:03:22 -07001007 } else {
Matthew Wilcox7b60e9a2016-05-20 17:02:23 -07001008 BUG_ON(root_tags_get(root));
Nick Piggin612d6c12006-06-23 02:03:22 -07001009 }
Linus Torvalds1da177e2005-04-16 15:20:36 -07001010
Linus Torvalds1da177e2005-04-16 15:20:36 -07001011 return 0;
1012}
Matthew Wilcoxe6145232016-03-17 14:21:54 -07001013EXPORT_SYMBOL(__radix_tree_insert);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001014
Johannes Weiner139e5612014-04-03 14:47:54 -07001015/**
1016 * __radix_tree_lookup - lookup an item in a radix tree
1017 * @root: radix tree root
1018 * @index: index key
1019 * @nodep: returns node
1020 * @slotp: returns slot
1021 *
1022 * Lookup and return the item at position @index in the radix
1023 * tree @root.
1024 *
1025 * Until there is more than one item in the tree, no nodes are
1026 * allocated and @root->rnode is used as a direct slot instead of
1027 * pointing to a node, in which case *@nodep will be NULL.
Hans Reisera4331362005-11-07 00:59:29 -08001028 */
Matthew Wilcox35534c82016-12-19 17:43:19 -05001029void *__radix_tree_lookup(const struct radix_tree_root *root,
1030 unsigned long index, struct radix_tree_node **nodep,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001031 void __rcu ***slotp)
Hans Reisera4331362005-11-07 00:59:29 -08001032{
Johannes Weiner139e5612014-04-03 14:47:54 -07001033 struct radix_tree_node *node, *parent;
Matthew Wilcox85829952016-05-20 17:02:20 -07001034 unsigned long maxindex;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001035 void __rcu **slot;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001036
Matthew Wilcox85829952016-05-20 17:02:20 -07001037 restart:
1038 parent = NULL;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001039 slot = (void __rcu **)&root->rnode;
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001040 radix_tree_load_root(root, &node, &maxindex);
Matthew Wilcox85829952016-05-20 17:02:20 -07001041 if (index > maxindex)
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001042 return NULL;
1043
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001044 while (radix_tree_is_internal_node(node)) {
Matthew Wilcox85829952016-05-20 17:02:20 -07001045 unsigned offset;
Johannes Weiner139e5612014-04-03 14:47:54 -07001046
Matthew Wilcox85829952016-05-20 17:02:20 -07001047 if (node == RADIX_TREE_RETRY)
1048 goto restart;
Matthew Wilcox4dd6c092016-05-20 17:03:27 -07001049 parent = entry_to_node(node);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001050 offset = radix_tree_descend(parent, &node, index);
Matthew Wilcox85829952016-05-20 17:02:20 -07001051 slot = parent->slots + offset;
1052 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001053
Johannes Weiner139e5612014-04-03 14:47:54 -07001054 if (nodep)
1055 *nodep = parent;
1056 if (slotp)
1057 *slotp = slot;
1058 return node;
Huang Shijieb72b71c2009-06-16 15:33:42 -07001059}
1060
1061/**
1062 * radix_tree_lookup_slot - lookup a slot in a radix tree
1063 * @root: radix tree root
1064 * @index: index key
1065 *
1066 * Returns: the slot corresponding to the position @index in the
1067 * radix tree @root. This is useful for update-if-exists operations.
1068 *
1069 * This function can be called under rcu_read_lock iff the slot is not
1070 * modified by radix_tree_replace_slot, otherwise it must be called
1071 * exclusive from other writers. Any dereference of the slot must be done
1072 * using radix_tree_deref_slot.
1073 */
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001074void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *root,
Matthew Wilcox35534c82016-12-19 17:43:19 -05001075 unsigned long index)
Huang Shijieb72b71c2009-06-16 15:33:42 -07001076{
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001077 void __rcu **slot;
Johannes Weiner139e5612014-04-03 14:47:54 -07001078
1079 if (!__radix_tree_lookup(root, index, NULL, &slot))
1080 return NULL;
1081 return slot;
Hans Reisera4331362005-11-07 00:59:29 -08001082}
1083EXPORT_SYMBOL(radix_tree_lookup_slot);
1084
Linus Torvalds1da177e2005-04-16 15:20:36 -07001085/**
1086 * radix_tree_lookup - perform lookup operation on a radix tree
1087 * @root: radix tree root
1088 * @index: index key
1089 *
1090 * Lookup the item at the position @index in the radix tree @root.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001091 *
1092 * This function can be called under rcu_read_lock, however the caller
1093 * must manage lifetimes of leaf nodes (eg. RCU may also be used to free
1094 * them safely). No RCU barriers are required to access or modify the
1095 * returned item, however.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001096 */
Matthew Wilcox35534c82016-12-19 17:43:19 -05001097void *radix_tree_lookup(const struct radix_tree_root *root, unsigned long index)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001098{
Johannes Weiner139e5612014-04-03 14:47:54 -07001099 return __radix_tree_lookup(root, index, NULL, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001100}
1101EXPORT_SYMBOL(radix_tree_lookup);
1102
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001103static inline void replace_sibling_entries(struct radix_tree_node *node,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001104 void __rcu **slot, int count, int exceptional)
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001105{
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001106#ifdef CONFIG_RADIX_TREE_MULTIORDER
1107 void *ptr = node_to_entry(slot);
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001108 unsigned offset = get_slot_offset(node, slot) + 1;
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001109
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001110 while (offset < RADIX_TREE_MAP_SIZE) {
Matthew Wilcox12320d02017-02-13 15:22:48 -05001111 if (rcu_dereference_raw(node->slots[offset]) != ptr)
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001112 break;
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001113 if (count < 0) {
1114 node->slots[offset] = NULL;
1115 node->count--;
1116 }
1117 node->exceptional += exceptional;
1118 offset++;
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001119 }
1120#endif
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001121}
1122
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001123static void replace_slot(void __rcu **slot, void *item,
1124 struct radix_tree_node *node, int count, int exceptional)
Johannes Weiner6d75f362016-12-12 16:43:43 -08001125{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001126 if (WARN_ON_ONCE(radix_tree_is_internal_node(item)))
1127 return;
Johannes Weiner6d75f362016-12-12 16:43:43 -08001128
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001129 if (node && (count || exceptional)) {
Johannes Weinerf4b109c2016-12-12 16:43:46 -08001130 node->count += count;
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001131 node->exceptional += exceptional;
1132 replace_sibling_entries(node, slot, count, exceptional);
Johannes Weinerf4b109c2016-12-12 16:43:46 -08001133 }
Johannes Weiner6d75f362016-12-12 16:43:43 -08001134
1135 rcu_assign_pointer(*slot, item);
1136}
1137
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001138static bool node_tag_get(const struct radix_tree_root *root,
1139 const struct radix_tree_node *node,
1140 unsigned int tag, unsigned int offset)
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001141{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001142 if (node)
1143 return tag_get(node, tag, offset);
1144 return root_tag_get(root, tag);
1145}
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001146
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001147/*
1148 * IDR users want to be able to store NULL in the tree, so if the slot isn't
1149 * free, don't adjust the count, even if it's transitioning between NULL and
1150 * non-NULL. For the IDA, we mark slots as being IDR_FREE while they still
1151 * have empty bits, but it only stores NULL in slots when they're being
1152 * deleted.
1153 */
1154static int calculate_count(struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001155 struct radix_tree_node *node, void __rcu **slot,
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001156 void *item, void *old)
1157{
1158 if (is_idr(root)) {
1159 unsigned offset = get_slot_offset(node, slot);
1160 bool free = node_tag_get(root, node, IDR_FREE, offset);
1161 if (!free)
1162 return 0;
1163 if (!old)
1164 return 1;
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001165 }
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001166 return !!item - !!old;
Matthew Wilcoxa90eb3a2016-12-14 15:09:07 -08001167}
1168
Linus Torvalds1da177e2005-04-16 15:20:36 -07001169/**
Johannes Weinerf7942432016-12-12 16:43:41 -08001170 * __radix_tree_replace - replace item in a slot
Johannes Weiner4d693d02016-12-12 16:43:49 -08001171 * @root: radix tree root
1172 * @node: pointer to tree node
1173 * @slot: pointer to slot in @node
1174 * @item: new item to store in the slot.
1175 * @update_node: callback for changing leaf nodes
1176 * @private: private data to pass to @update_node
Johannes Weinerf7942432016-12-12 16:43:41 -08001177 *
1178 * For use with __radix_tree_lookup(). Caller must hold tree write locked
1179 * across slot lookup and replacement.
1180 */
1181void __radix_tree_replace(struct radix_tree_root *root,
1182 struct radix_tree_node *node,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001183 void __rcu **slot, void *item,
Johannes Weiner4d693d02016-12-12 16:43:49 -08001184 radix_tree_update_node_t update_node, void *private)
Johannes Weinerf7942432016-12-12 16:43:41 -08001185{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001186 void *old = rcu_dereference_raw(*slot);
1187 int exceptional = !!radix_tree_exceptional_entry(item) -
1188 !!radix_tree_exceptional_entry(old);
1189 int count = calculate_count(root, node, slot, item, old);
1190
Johannes Weiner6d75f362016-12-12 16:43:43 -08001191 /*
Johannes Weinerf4b109c2016-12-12 16:43:46 -08001192 * This function supports replacing exceptional entries and
1193 * deleting entries, but that needs accounting against the
1194 * node unless the slot is root->rnode.
Johannes Weiner6d75f362016-12-12 16:43:43 -08001195 */
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001196 WARN_ON_ONCE(!node && (slot != (void __rcu **)&root->rnode) &&
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001197 (count || exceptional));
1198 replace_slot(slot, item, node, count, exceptional);
Johannes Weinerf4b109c2016-12-12 16:43:46 -08001199
Johannes Weiner4d693d02016-12-12 16:43:49 -08001200 if (!node)
1201 return;
1202
1203 if (update_node)
1204 update_node(node, private);
1205
1206 delete_node(root, node, update_node, private);
Johannes Weiner6d75f362016-12-12 16:43:43 -08001207}
Johannes Weinerf7942432016-12-12 16:43:41 -08001208
Johannes Weiner6d75f362016-12-12 16:43:43 -08001209/**
1210 * radix_tree_replace_slot - replace item in a slot
1211 * @root: radix tree root
1212 * @slot: pointer to slot
1213 * @item: new item to store in the slot.
1214 *
1215 * For use with radix_tree_lookup_slot(), radix_tree_gang_lookup_slot(),
1216 * radix_tree_gang_lookup_tag_slot(). Caller must hold tree write locked
1217 * across slot lookup and replacement.
1218 *
1219 * NOTE: This cannot be used to switch between non-entries (empty slots),
1220 * regular entries, and exceptional entries, as that requires accounting
Johannes Weinerf4b109c2016-12-12 16:43:46 -08001221 * inside the radix tree node. When switching from one type of entry or
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001222 * deleting, use __radix_tree_lookup() and __radix_tree_replace() or
1223 * radix_tree_iter_replace().
Johannes Weiner6d75f362016-12-12 16:43:43 -08001224 */
1225void radix_tree_replace_slot(struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001226 void __rcu **slot, void *item)
Johannes Weiner6d75f362016-12-12 16:43:43 -08001227{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001228 __radix_tree_replace(root, NULL, slot, item, NULL, NULL);
Johannes Weinerf7942432016-12-12 16:43:41 -08001229}
Song Liu10257d72017-01-11 10:00:51 -08001230EXPORT_SYMBOL(radix_tree_replace_slot);
Johannes Weinerf7942432016-12-12 16:43:41 -08001231
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001232/**
1233 * radix_tree_iter_replace - replace item in a slot
1234 * @root: radix tree root
1235 * @slot: pointer to slot
1236 * @item: new item to store in the slot.
1237 *
1238 * For use with radix_tree_split() and radix_tree_for_each_slot().
1239 * Caller must hold tree write locked across split and replacement.
1240 */
1241void radix_tree_iter_replace(struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001242 const struct radix_tree_iter *iter,
1243 void __rcu **slot, void *item)
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001244{
1245 __radix_tree_replace(root, iter->node, slot, item, NULL, NULL);
1246}
1247
Matthew Wilcox175542f2016-12-14 15:08:58 -08001248#ifdef CONFIG_RADIX_TREE_MULTIORDER
1249/**
1250 * radix_tree_join - replace multiple entries with one multiorder entry
1251 * @root: radix tree root
1252 * @index: an index inside the new entry
1253 * @order: order of the new entry
1254 * @item: new entry
1255 *
1256 * Call this function to replace several entries with one larger entry.
1257 * The existing entries are presumed to not need freeing as a result of
1258 * this call.
1259 *
1260 * The replacement entry will have all the tags set on it that were set
1261 * on any of the entries it is replacing.
1262 */
1263int radix_tree_join(struct radix_tree_root *root, unsigned long index,
1264 unsigned order, void *item)
1265{
1266 struct radix_tree_node *node;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001267 void __rcu **slot;
Matthew Wilcox175542f2016-12-14 15:08:58 -08001268 int error;
1269
1270 BUG_ON(radix_tree_is_internal_node(item));
1271
1272 error = __radix_tree_create(root, index, order, &node, &slot);
1273 if (!error)
1274 error = insert_entries(node, slot, item, order, true);
1275 if (error > 0)
1276 error = 0;
1277
1278 return error;
1279}
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001280
1281/**
1282 * radix_tree_split - Split an entry into smaller entries
1283 * @root: radix tree root
1284 * @index: An index within the large entry
1285 * @order: Order of new entries
1286 *
1287 * Call this function as the first step in replacing a multiorder entry
1288 * with several entries of lower order. After this function returns,
1289 * loop over the relevant portion of the tree using radix_tree_for_each_slot()
1290 * and call radix_tree_iter_replace() to set up each new entry.
1291 *
1292 * The tags from this entry are replicated to all the new entries.
1293 *
1294 * The radix tree should be locked against modification during the entire
1295 * replacement operation. Lock-free lookups will see RADIX_TREE_RETRY which
1296 * should prompt RCU walkers to restart the lookup from the root.
1297 */
1298int radix_tree_split(struct radix_tree_root *root, unsigned long index,
1299 unsigned order)
1300{
1301 struct radix_tree_node *parent, *node, *child;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001302 void __rcu **slot;
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001303 unsigned int offset, end;
1304 unsigned n, tag, tags = 0;
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001305 gfp_t gfp = root_gfp_mask(root);
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001306
1307 if (!__radix_tree_lookup(root, index, &parent, &slot))
1308 return -ENOENT;
1309 if (!parent)
1310 return -ENOENT;
1311
1312 offset = get_slot_offset(parent, slot);
1313
1314 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1315 if (tag_get(parent, tag, offset))
1316 tags |= 1 << tag;
1317
1318 for (end = offset + 1; end < RADIX_TREE_MAP_SIZE; end++) {
Matthew Wilcox12320d02017-02-13 15:22:48 -05001319 if (!is_sibling_entry(parent,
1320 rcu_dereference_raw(parent->slots[end])))
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001321 break;
1322 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1323 if (tags & (1 << tag))
1324 tag_set(parent, tag, end);
1325 /* rcu_assign_pointer ensures tags are set before RETRY */
1326 rcu_assign_pointer(parent->slots[end], RADIX_TREE_RETRY);
1327 }
1328 rcu_assign_pointer(parent->slots[offset], RADIX_TREE_RETRY);
1329 parent->exceptional -= (end - offset);
1330
1331 if (order == parent->shift)
1332 return 0;
1333 if (order > parent->shift) {
1334 while (offset < end)
1335 offset += insert_entries(parent, &parent->slots[offset],
1336 RADIX_TREE_RETRY, order, true);
1337 return 0;
1338 }
1339
1340 node = parent;
1341
1342 for (;;) {
1343 if (node->shift > order) {
Matthew Wilcoxd58275b2017-01-16 17:10:21 -05001344 child = radix_tree_node_alloc(gfp, node, root,
Matthew Wilcoxe8de4342016-12-14 15:09:31 -08001345 node->shift - RADIX_TREE_MAP_SHIFT,
1346 offset, 0, 0);
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001347 if (!child)
1348 goto nomem;
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001349 if (node != parent) {
1350 node->count++;
Matthew Wilcox12320d02017-02-13 15:22:48 -05001351 rcu_assign_pointer(node->slots[offset],
1352 node_to_entry(child));
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001353 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1354 if (tags & (1 << tag))
1355 tag_set(node, tag, offset);
1356 }
1357
1358 node = child;
1359 offset = 0;
1360 continue;
1361 }
1362
1363 n = insert_entries(node, &node->slots[offset],
1364 RADIX_TREE_RETRY, order, false);
1365 BUG_ON(n > RADIX_TREE_MAP_SIZE);
1366
1367 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
1368 if (tags & (1 << tag))
1369 tag_set(node, tag, offset);
1370 offset += n;
1371
1372 while (offset == RADIX_TREE_MAP_SIZE) {
1373 if (node == parent)
1374 break;
1375 offset = node->offset;
1376 child = node;
1377 node = node->parent;
1378 rcu_assign_pointer(node->slots[offset],
1379 node_to_entry(child));
1380 offset++;
1381 }
1382 if ((node == parent) && (offset == end))
1383 return 0;
1384 }
1385
1386 nomem:
1387 /* Shouldn't happen; did user forget to preload? */
1388 /* TODO: free all the allocated nodes */
1389 WARN_ON(1);
1390 return -ENOMEM;
1391}
Matthew Wilcox175542f2016-12-14 15:08:58 -08001392#endif
1393
Matthew Wilcox30b888b2017-01-28 09:55:20 -05001394static void node_tag_set(struct radix_tree_root *root,
1395 struct radix_tree_node *node,
1396 unsigned int tag, unsigned int offset)
1397{
1398 while (node) {
1399 if (tag_get(node, tag, offset))
1400 return;
1401 tag_set(node, tag, offset);
1402 offset = node->offset;
1403 node = node->parent;
1404 }
1405
1406 if (!root_tag_get(root, tag))
1407 root_tag_set(root, tag);
1408}
1409
Linus Torvalds1da177e2005-04-16 15:20:36 -07001410/**
1411 * radix_tree_tag_set - set a tag on a radix tree node
1412 * @root: radix tree root
1413 * @index: index key
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001414 * @tag: tag index
Linus Torvalds1da177e2005-04-16 15:20:36 -07001415 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001416 * Set the search tag (which must be < RADIX_TREE_MAX_TAGS)
1417 * corresponding to @index in the radix tree. From
Linus Torvalds1da177e2005-04-16 15:20:36 -07001418 * the root all the way down to the leaf node.
1419 *
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001420 * Returns the address of the tagged item. Setting a tag on a not-present
Linus Torvalds1da177e2005-04-16 15:20:36 -07001421 * item is a bug.
1422 */
1423void *radix_tree_tag_set(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001424 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001425{
Ross Zwislerfb969902016-05-20 17:02:32 -07001426 struct radix_tree_node *node, *parent;
1427 unsigned long maxindex;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001428
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001429 radix_tree_load_root(root, &node, &maxindex);
Ross Zwislerfb969902016-05-20 17:02:32 -07001430 BUG_ON(index > maxindex);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001431
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001432 while (radix_tree_is_internal_node(node)) {
Ross Zwislerfb969902016-05-20 17:02:32 -07001433 unsigned offset;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001434
Matthew Wilcox4dd6c092016-05-20 17:03:27 -07001435 parent = entry_to_node(node);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001436 offset = radix_tree_descend(parent, &node, index);
Ross Zwislerfb969902016-05-20 17:02:32 -07001437 BUG_ON(!node);
1438
1439 if (!tag_get(parent, tag, offset))
1440 tag_set(parent, tag, offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001441 }
1442
Nick Piggin612d6c12006-06-23 02:03:22 -07001443 /* set the root's tag bit */
Ross Zwislerfb969902016-05-20 17:02:32 -07001444 if (!root_tag_get(root, tag))
Nick Piggin612d6c12006-06-23 02:03:22 -07001445 root_tag_set(root, tag);
1446
Ross Zwislerfb969902016-05-20 17:02:32 -07001447 return node;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001448}
1449EXPORT_SYMBOL(radix_tree_tag_set);
1450
Matthew Wilcox30b888b2017-01-28 09:55:20 -05001451/**
1452 * radix_tree_iter_tag_set - set a tag on the current iterator entry
1453 * @root: radix tree root
1454 * @iter: iterator state
1455 * @tag: tag to set
1456 */
1457void radix_tree_iter_tag_set(struct radix_tree_root *root,
1458 const struct radix_tree_iter *iter, unsigned int tag)
1459{
1460 node_tag_set(root, iter->node, tag, iter_offset(iter));
1461}
1462
Matthew Wilcoxd604c322016-05-20 17:03:45 -07001463static void node_tag_clear(struct radix_tree_root *root,
1464 struct radix_tree_node *node,
1465 unsigned int tag, unsigned int offset)
1466{
1467 while (node) {
1468 if (!tag_get(node, tag, offset))
1469 return;
1470 tag_clear(node, tag, offset);
1471 if (any_tag_set(node, tag))
1472 return;
1473
1474 offset = node->offset;
1475 node = node->parent;
1476 }
1477
1478 /* clear the root's tag bit */
1479 if (root_tag_get(root, tag))
1480 root_tag_clear(root, tag);
1481}
1482
Matthew Wilcox268f42d2016-12-14 15:08:55 -08001483/**
Linus Torvalds1da177e2005-04-16 15:20:36 -07001484 * radix_tree_tag_clear - clear a tag on a radix tree node
1485 * @root: radix tree root
1486 * @index: index key
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001487 * @tag: tag index
Linus Torvalds1da177e2005-04-16 15:20:36 -07001488 *
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001489 * Clear the search tag (which must be < RADIX_TREE_MAX_TAGS)
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001490 * corresponding to @index in the radix tree. If this causes
1491 * the leaf node to have no tags set then clear the tag in the
Linus Torvalds1da177e2005-04-16 15:20:36 -07001492 * next-to-leaf node, etc.
1493 *
1494 * Returns the address of the tagged item on success, else NULL. ie:
1495 * has the same return value and semantics as radix_tree_lookup().
1496 */
1497void *radix_tree_tag_clear(struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001498 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001499{
Ross Zwisler00f47b52016-05-20 17:02:35 -07001500 struct radix_tree_node *node, *parent;
1501 unsigned long maxindex;
Hugh Dickinse2bdb932012-01-12 17:20:41 -08001502 int uninitialized_var(offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001503
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001504 radix_tree_load_root(root, &node, &maxindex);
Ross Zwisler00f47b52016-05-20 17:02:35 -07001505 if (index > maxindex)
1506 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001507
Ross Zwisler00f47b52016-05-20 17:02:35 -07001508 parent = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001509
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001510 while (radix_tree_is_internal_node(node)) {
Matthew Wilcox4dd6c092016-05-20 17:03:27 -07001511 parent = entry_to_node(node);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001512 offset = radix_tree_descend(parent, &node, index);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001513 }
1514
Matthew Wilcoxd604c322016-05-20 17:03:45 -07001515 if (node)
1516 node_tag_clear(root, parent, tag, offset);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001517
Ross Zwisler00f47b52016-05-20 17:02:35 -07001518 return node;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001519}
1520EXPORT_SYMBOL(radix_tree_tag_clear);
1521
Linus Torvalds1da177e2005-04-16 15:20:36 -07001522/**
Matthew Wilcox30b888b2017-01-28 09:55:20 -05001523 * radix_tree_iter_tag_clear - clear a tag on the current iterator entry
1524 * @root: radix tree root
1525 * @iter: iterator state
1526 * @tag: tag to clear
1527 */
1528void radix_tree_iter_tag_clear(struct radix_tree_root *root,
1529 const struct radix_tree_iter *iter, unsigned int tag)
1530{
1531 node_tag_clear(root, iter->node, tag, iter_offset(iter));
1532}
1533
1534/**
Marcelo Tosatti32605a12005-09-06 15:16:48 -07001535 * radix_tree_tag_get - get a tag on a radix tree node
1536 * @root: radix tree root
1537 * @index: index key
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001538 * @tag: tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001539 *
Marcelo Tosatti32605a12005-09-06 15:16:48 -07001540 * Return values:
Linus Torvalds1da177e2005-04-16 15:20:36 -07001541 *
Nick Piggin612d6c12006-06-23 02:03:22 -07001542 * 0: tag not present or not set
1543 * 1: tag set
David Howellsce826532010-04-06 22:36:20 +01001544 *
1545 * Note that the return value of this function may not be relied on, even if
1546 * the RCU lock is held, unless tag modification and node deletion are excluded
1547 * from concurrency.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001548 */
Matthew Wilcox35534c82016-12-19 17:43:19 -05001549int radix_tree_tag_get(const struct radix_tree_root *root,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001550 unsigned long index, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001551{
Ross Zwisler4589ba62016-05-20 17:02:38 -07001552 struct radix_tree_node *node, *parent;
1553 unsigned long maxindex;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001554
Nick Piggin612d6c12006-06-23 02:03:22 -07001555 if (!root_tag_get(root, tag))
1556 return 0;
1557
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001558 radix_tree_load_root(root, &node, &maxindex);
Ross Zwisler4589ba62016-05-20 17:02:38 -07001559 if (index > maxindex)
1560 return 0;
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001561
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001562 while (radix_tree_is_internal_node(node)) {
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001563 unsigned offset;
Ross Zwisler4589ba62016-05-20 17:02:38 -07001564
Matthew Wilcox4dd6c092016-05-20 17:03:27 -07001565 parent = entry_to_node(node);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001566 offset = radix_tree_descend(parent, &node, index);
Ross Zwisler4589ba62016-05-20 17:02:38 -07001567
Ross Zwisler4589ba62016-05-20 17:02:38 -07001568 if (!tag_get(parent, tag, offset))
1569 return 0;
1570 if (node == RADIX_TREE_RETRY)
1571 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001572 }
Ross Zwisler4589ba62016-05-20 17:02:38 -07001573
1574 return 1;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001575}
1576EXPORT_SYMBOL(radix_tree_tag_get);
Linus Torvalds1da177e2005-04-16 15:20:36 -07001577
Ross Zwisler21ef5332016-05-20 17:02:26 -07001578static inline void __set_iter_shift(struct radix_tree_iter *iter,
1579 unsigned int shift)
1580{
1581#ifdef CONFIG_RADIX_TREE_MULTIORDER
1582 iter->shift = shift;
1583#endif
1584}
1585
Matthew Wilcox148deab2016-12-14 15:08:49 -08001586/* Construct iter->tags bit-mask from node->tags[tag] array */
1587static void set_iter_tags(struct radix_tree_iter *iter,
1588 struct radix_tree_node *node, unsigned offset,
1589 unsigned tag)
1590{
1591 unsigned tag_long = offset / BITS_PER_LONG;
1592 unsigned tag_bit = offset % BITS_PER_LONG;
1593
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001594 if (!node) {
1595 iter->tags = 1;
1596 return;
1597 }
1598
Matthew Wilcox148deab2016-12-14 15:08:49 -08001599 iter->tags = node->tags[tag][tag_long] >> tag_bit;
1600
1601 /* This never happens if RADIX_TREE_TAG_LONGS == 1 */
1602 if (tag_long < RADIX_TREE_TAG_LONGS - 1) {
1603 /* Pick tags from next element */
1604 if (tag_bit)
1605 iter->tags |= node->tags[tag][tag_long + 1] <<
1606 (BITS_PER_LONG - tag_bit);
1607 /* Clip chunk size, here only BITS_PER_LONG tags */
1608 iter->next_index = __radix_tree_iter_add(iter, BITS_PER_LONG);
1609 }
1610}
1611
1612#ifdef CONFIG_RADIX_TREE_MULTIORDER
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001613static void __rcu **skip_siblings(struct radix_tree_node **nodep,
1614 void __rcu **slot, struct radix_tree_iter *iter)
Matthew Wilcox148deab2016-12-14 15:08:49 -08001615{
1616 void *sib = node_to_entry(slot - 1);
1617
1618 while (iter->index < iter->next_index) {
1619 *nodep = rcu_dereference_raw(*slot);
1620 if (*nodep && *nodep != sib)
1621 return slot;
1622 slot++;
1623 iter->index = __radix_tree_iter_add(iter, 1);
1624 iter->tags >>= 1;
1625 }
1626
1627 *nodep = NULL;
1628 return NULL;
1629}
1630
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001631void __rcu **__radix_tree_next_slot(void __rcu **slot,
1632 struct radix_tree_iter *iter, unsigned flags)
Matthew Wilcox148deab2016-12-14 15:08:49 -08001633{
1634 unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
1635 struct radix_tree_node *node = rcu_dereference_raw(*slot);
1636
1637 slot = skip_siblings(&node, slot, iter);
1638
1639 while (radix_tree_is_internal_node(node)) {
1640 unsigned offset;
1641 unsigned long next_index;
1642
1643 if (node == RADIX_TREE_RETRY)
1644 return slot;
1645 node = entry_to_node(node);
Matthew Wilcox268f42d2016-12-14 15:08:55 -08001646 iter->node = node;
Matthew Wilcox148deab2016-12-14 15:08:49 -08001647 iter->shift = node->shift;
1648
1649 if (flags & RADIX_TREE_ITER_TAGGED) {
1650 offset = radix_tree_find_next_bit(node, tag, 0);
1651 if (offset == RADIX_TREE_MAP_SIZE)
1652 return NULL;
1653 slot = &node->slots[offset];
1654 iter->index = __radix_tree_iter_add(iter, offset);
1655 set_iter_tags(iter, node, offset, tag);
1656 node = rcu_dereference_raw(*slot);
1657 } else {
1658 offset = 0;
1659 slot = &node->slots[0];
1660 for (;;) {
1661 node = rcu_dereference_raw(*slot);
1662 if (node)
1663 break;
1664 slot++;
1665 offset++;
1666 if (offset == RADIX_TREE_MAP_SIZE)
1667 return NULL;
1668 }
1669 iter->index = __radix_tree_iter_add(iter, offset);
1670 }
1671 if ((flags & RADIX_TREE_ITER_CONTIG) && (offset > 0))
1672 goto none;
1673 next_index = (iter->index | shift_maxindex(iter->shift)) + 1;
1674 if (next_index < iter->next_index)
1675 iter->next_index = next_index;
1676 }
1677
1678 return slot;
1679 none:
1680 iter->next_index = 0;
1681 return NULL;
1682}
1683EXPORT_SYMBOL(__radix_tree_next_slot);
1684#else
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001685static void __rcu **skip_siblings(struct radix_tree_node **nodep,
1686 void __rcu **slot, struct radix_tree_iter *iter)
Matthew Wilcox148deab2016-12-14 15:08:49 -08001687{
1688 return slot;
1689}
1690#endif
1691
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001692void __rcu **radix_tree_iter_resume(void __rcu **slot,
1693 struct radix_tree_iter *iter)
Matthew Wilcox148deab2016-12-14 15:08:49 -08001694{
1695 struct radix_tree_node *node;
1696
1697 slot++;
1698 iter->index = __radix_tree_iter_add(iter, 1);
Matthew Wilcox148deab2016-12-14 15:08:49 -08001699 skip_siblings(&node, slot, iter);
1700 iter->next_index = iter->index;
1701 iter->tags = 0;
1702 return NULL;
1703}
1704EXPORT_SYMBOL(radix_tree_iter_resume);
1705
Fengguang Wu6df8ba42007-10-16 01:24:33 -07001706/**
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001707 * radix_tree_next_chunk - find next chunk of slots for iteration
1708 *
1709 * @root: radix tree root
1710 * @iter: iterator state
1711 * @flags: RADIX_TREE_ITER_* flags and tag index
1712 * Returns: pointer to chunk first slot, or NULL if iteration is over
1713 */
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001714void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root,
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001715 struct radix_tree_iter *iter, unsigned flags)
1716{
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001717 unsigned tag = flags & RADIX_TREE_ITER_TAG_MASK;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001718 struct radix_tree_node *node, *child;
Ross Zwisler21ef5332016-05-20 17:02:26 -07001719 unsigned long index, offset, maxindex;
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001720
1721 if ((flags & RADIX_TREE_ITER_TAGGED) && !root_tag_get(root, tag))
1722 return NULL;
1723
1724 /*
1725 * Catch next_index overflow after ~0UL. iter->index never overflows
1726 * during iterating; it can be zero only at the beginning.
1727 * And we cannot overflow iter->next_index in a single step,
1728 * because RADIX_TREE_MAP_SHIFT < BITS_PER_LONG.
Konstantin Khlebnikovfffaee32012-06-05 21:36:33 +04001729 *
1730 * This condition also used by radix_tree_next_slot() to stop
Matthew Wilcox91b9677c2016-12-14 15:08:31 -08001731 * contiguous iterating, and forbid switching to the next chunk.
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001732 */
1733 index = iter->next_index;
1734 if (!index && iter->index)
1735 return NULL;
1736
Ross Zwisler21ef5332016-05-20 17:02:26 -07001737 restart:
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001738 radix_tree_load_root(root, &child, &maxindex);
Ross Zwisler21ef5332016-05-20 17:02:26 -07001739 if (index > maxindex)
1740 return NULL;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001741 if (!child)
1742 return NULL;
Ross Zwisler21ef5332016-05-20 17:02:26 -07001743
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001744 if (!radix_tree_is_internal_node(child)) {
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001745 /* Single-slot tree */
Ross Zwisler21ef5332016-05-20 17:02:26 -07001746 iter->index = index;
1747 iter->next_index = maxindex + 1;
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001748 iter->tags = 1;
Matthew Wilcox268f42d2016-12-14 15:08:55 -08001749 iter->node = NULL;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001750 __set_iter_shift(iter, 0);
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001751 return (void __rcu **)&root->rnode;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001752 }
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001753
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001754 do {
1755 node = entry_to_node(child);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001756 offset = radix_tree_descend(node, &child, index);
Ross Zwisler21ef5332016-05-20 17:02:26 -07001757
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001758 if ((flags & RADIX_TREE_ITER_TAGGED) ?
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001759 !tag_get(node, tag, offset) : !child) {
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001760 /* Hole detected */
1761 if (flags & RADIX_TREE_ITER_CONTIG)
1762 return NULL;
1763
1764 if (flags & RADIX_TREE_ITER_TAGGED)
Matthew Wilcoxbc412fc2016-12-14 15:08:40 -08001765 offset = radix_tree_find_next_bit(node, tag,
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001766 offset + 1);
1767 else
1768 while (++offset < RADIX_TREE_MAP_SIZE) {
Matthew Wilcox12320d02017-02-13 15:22:48 -05001769 void *slot = rcu_dereference_raw(
1770 node->slots[offset]);
Ross Zwisler21ef5332016-05-20 17:02:26 -07001771 if (is_sibling_entry(node, slot))
1772 continue;
1773 if (slot)
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001774 break;
1775 }
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001776 index &= ~node_maxindex(node);
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001777 index += offset << node->shift;
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001778 /* Overflow after ~0UL */
1779 if (!index)
1780 return NULL;
1781 if (offset == RADIX_TREE_MAP_SIZE)
1782 goto restart;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001783 child = rcu_dereference_raw(node->slots[offset]);
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001784 }
1785
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001786 if (!child)
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001787 goto restart;
Matthew Wilcoxe157b552016-12-14 15:09:01 -08001788 if (child == RADIX_TREE_RETRY)
1789 break;
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001790 } while (radix_tree_is_internal_node(child));
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001791
1792 /* Update the iterator state */
Matthew Wilcox8c1244d2016-05-20 17:03:36 -07001793 iter->index = (index &~ node_maxindex(node)) | (offset << node->shift);
1794 iter->next_index = (index | node_maxindex(node)) + 1;
Matthew Wilcox268f42d2016-12-14 15:08:55 -08001795 iter->node = node;
Matthew Wilcox9e85d812016-05-20 17:03:48 -07001796 __set_iter_shift(iter, node->shift);
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001797
Matthew Wilcox148deab2016-12-14 15:08:49 -08001798 if (flags & RADIX_TREE_ITER_TAGGED)
1799 set_iter_tags(iter, node, offset, tag);
Konstantin Khlebnikov78c1d782012-03-28 14:42:53 -07001800
1801 return node->slots + offset;
1802}
1803EXPORT_SYMBOL(radix_tree_next_chunk);
1804
1805/**
Linus Torvalds1da177e2005-04-16 15:20:36 -07001806 * radix_tree_gang_lookup - perform multiple lookup on a radix tree
1807 * @root: radix tree root
1808 * @results: where the results of the lookup are placed
1809 * @first_index: start the lookup from this key
1810 * @max_items: place up to this many items at *results
1811 *
1812 * Performs an index-ascending scan of the tree for present items. Places
1813 * them at *@results and returns the number of items which were placed at
1814 * *@results.
1815 *
1816 * The implementation is naive.
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001817 *
1818 * Like radix_tree_lookup, radix_tree_gang_lookup may be called under
1819 * rcu_read_lock. In this case, rather than the returned results being
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07001820 * an atomic snapshot of the tree at a single point in time, the
1821 * semantics of an RCU protected gang lookup are as though multiple
1822 * radix_tree_lookups have been issued in individual locks, and results
1823 * stored in 'results'.
Linus Torvalds1da177e2005-04-16 15:20:36 -07001824 */
1825unsigned int
Matthew Wilcox35534c82016-12-19 17:43:19 -05001826radix_tree_gang_lookup(const struct radix_tree_root *root, void **results,
Linus Torvalds1da177e2005-04-16 15:20:36 -07001827 unsigned long first_index, unsigned int max_items)
1828{
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001829 struct radix_tree_iter iter;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001830 void __rcu **slot;
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001831 unsigned int ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001832
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001833 if (unlikely(!max_items))
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001834 return 0;
1835
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001836 radix_tree_for_each_slot(slot, root, &iter, first_index) {
Matthew Wilcox46437f92016-02-02 16:57:52 -08001837 results[ret] = rcu_dereference_raw(*slot);
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001838 if (!results[ret])
1839 continue;
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001840 if (radix_tree_is_internal_node(results[ret])) {
Matthew Wilcox46437f92016-02-02 16:57:52 -08001841 slot = radix_tree_iter_retry(&iter);
1842 continue;
1843 }
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001844 if (++ret == max_items)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001845 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001846 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001847
Linus Torvalds1da177e2005-04-16 15:20:36 -07001848 return ret;
1849}
1850EXPORT_SYMBOL(radix_tree_gang_lookup);
1851
Nick Piggin47feff22008-07-25 19:45:29 -07001852/**
1853 * radix_tree_gang_lookup_slot - perform multiple slot lookup on radix tree
1854 * @root: radix tree root
1855 * @results: where the results of the lookup are placed
Hugh Dickins63286502011-08-03 16:21:18 -07001856 * @indices: where their indices should be placed (but usually NULL)
Nick Piggin47feff22008-07-25 19:45:29 -07001857 * @first_index: start the lookup from this key
1858 * @max_items: place up to this many items at *results
1859 *
1860 * Performs an index-ascending scan of the tree for present items. Places
1861 * their slots at *@results and returns the number of items which were
1862 * placed at *@results.
1863 *
1864 * The implementation is naive.
1865 *
1866 * Like radix_tree_gang_lookup as far as RCU and locking goes. Slots must
1867 * be dereferenced with radix_tree_deref_slot, and if using only RCU
1868 * protection, radix_tree_deref_slot may fail requiring a retry.
1869 */
1870unsigned int
Matthew Wilcox35534c82016-12-19 17:43:19 -05001871radix_tree_gang_lookup_slot(const struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001872 void __rcu ***results, unsigned long *indices,
Nick Piggin47feff22008-07-25 19:45:29 -07001873 unsigned long first_index, unsigned int max_items)
1874{
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001875 struct radix_tree_iter iter;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001876 void __rcu **slot;
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001877 unsigned int ret = 0;
Nick Piggin47feff22008-07-25 19:45:29 -07001878
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001879 if (unlikely(!max_items))
Nick Piggin47feff22008-07-25 19:45:29 -07001880 return 0;
1881
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001882 radix_tree_for_each_slot(slot, root, &iter, first_index) {
1883 results[ret] = slot;
Hugh Dickins63286502011-08-03 16:21:18 -07001884 if (indices)
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001885 indices[ret] = iter.index;
1886 if (++ret == max_items)
Nick Piggin47feff22008-07-25 19:45:29 -07001887 break;
Nick Piggin47feff22008-07-25 19:45:29 -07001888 }
1889
1890 return ret;
1891}
1892EXPORT_SYMBOL(radix_tree_gang_lookup_slot);
1893
Linus Torvalds1da177e2005-04-16 15:20:36 -07001894/**
1895 * radix_tree_gang_lookup_tag - perform multiple lookup on a radix tree
1896 * based on a tag
1897 * @root: radix tree root
1898 * @results: where the results of the lookup are placed
1899 * @first_index: start the lookup from this key
1900 * @max_items: place up to this many items at *results
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001901 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001902 *
1903 * Performs an index-ascending scan of the tree for present items which
1904 * have the tag indexed by @tag set. Places the items at *@results and
1905 * returns the number of items which were placed at *@results.
1906 */
1907unsigned int
Matthew Wilcox35534c82016-12-19 17:43:19 -05001908radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results,
Jonathan Corbetdaff89f2006-03-25 03:08:05 -08001909 unsigned long first_index, unsigned int max_items,
1910 unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001911{
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001912 struct radix_tree_iter iter;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001913 void __rcu **slot;
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001914 unsigned int ret = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001915
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001916 if (unlikely(!max_items))
Nick Piggin612d6c12006-06-23 02:03:22 -07001917 return 0;
1918
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001919 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
Matthew Wilcox46437f92016-02-02 16:57:52 -08001920 results[ret] = rcu_dereference_raw(*slot);
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001921 if (!results[ret])
1922 continue;
Matthew Wilcoxb194d162016-05-20 17:03:30 -07001923 if (radix_tree_is_internal_node(results[ret])) {
Matthew Wilcox46437f92016-02-02 16:57:52 -08001924 slot = radix_tree_iter_retry(&iter);
1925 continue;
1926 }
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001927 if (++ret == max_items)
Linus Torvalds1da177e2005-04-16 15:20:36 -07001928 break;
Linus Torvalds1da177e2005-04-16 15:20:36 -07001929 }
Nick Piggin7cf9c2c2006-12-06 20:33:44 -08001930
Linus Torvalds1da177e2005-04-16 15:20:36 -07001931 return ret;
1932}
1933EXPORT_SYMBOL(radix_tree_gang_lookup_tag);
1934
1935/**
Nick Piggin47feff22008-07-25 19:45:29 -07001936 * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a
1937 * radix tree based on a tag
1938 * @root: radix tree root
1939 * @results: where the results of the lookup are placed
1940 * @first_index: start the lookup from this key
1941 * @max_items: place up to this many items at *results
1942 * @tag: the tag index (< RADIX_TREE_MAX_TAGS)
1943 *
1944 * Performs an index-ascending scan of the tree for present items which
1945 * have the tag indexed by @tag set. Places the slots at *@results and
1946 * returns the number of slots which were placed at *@results.
1947 */
1948unsigned int
Matthew Wilcox35534c82016-12-19 17:43:19 -05001949radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001950 void __rcu ***results, unsigned long first_index,
Matthew Wilcox35534c82016-12-19 17:43:19 -05001951 unsigned int max_items, unsigned int tag)
Nick Piggin47feff22008-07-25 19:45:29 -07001952{
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001953 struct radix_tree_iter iter;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001954 void __rcu **slot;
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001955 unsigned int ret = 0;
Nick Piggin47feff22008-07-25 19:45:29 -07001956
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001957 if (unlikely(!max_items))
Nick Piggin47feff22008-07-25 19:45:29 -07001958 return 0;
1959
Konstantin Khlebnikovcebbd292012-03-28 14:42:53 -07001960 radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) {
1961 results[ret] = slot;
1962 if (++ret == max_items)
Nick Piggin47feff22008-07-25 19:45:29 -07001963 break;
Nick Piggin47feff22008-07-25 19:45:29 -07001964 }
1965
1966 return ret;
1967}
1968EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot);
1969
Nick Piggin47feff22008-07-25 19:45:29 -07001970/**
Johannes Weiner139e5612014-04-03 14:47:54 -07001971 * __radix_tree_delete_node - try to free node after clearing a slot
1972 * @root: radix tree root
Johannes Weiner139e5612014-04-03 14:47:54 -07001973 * @node: node containing @index
Johannes Weinerea07b862017-01-06 19:21:43 -05001974 * @update_node: callback for changing leaf nodes
1975 * @private: private data to pass to @update_node
Johannes Weiner139e5612014-04-03 14:47:54 -07001976 *
1977 * After clearing the slot at @index in @node from radix tree
1978 * rooted at @root, call this function to attempt freeing the
1979 * node and shrinking the tree.
Johannes Weiner139e5612014-04-03 14:47:54 -07001980 */
Johannes Weiner14b46872016-12-12 16:43:52 -08001981void __radix_tree_delete_node(struct radix_tree_root *root,
Johannes Weinerea07b862017-01-06 19:21:43 -05001982 struct radix_tree_node *node,
1983 radix_tree_update_node_t update_node,
1984 void *private)
Johannes Weiner139e5612014-04-03 14:47:54 -07001985{
Johannes Weinerea07b862017-01-06 19:21:43 -05001986 delete_node(root, node, update_node, private);
Johannes Weiner139e5612014-04-03 14:47:54 -07001987}
1988
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05001989static bool __radix_tree_delete(struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05001990 struct radix_tree_node *node, void __rcu **slot)
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05001991{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001992 void *old = rcu_dereference_raw(*slot);
1993 int exceptional = radix_tree_exceptional_entry(old) ? -1 : 0;
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05001994 unsigned offset = get_slot_offset(node, slot);
1995 int tag;
1996
Matthew Wilcox0a835c42016-12-20 10:27:56 -05001997 if (is_idr(root))
1998 node_tag_set(root, node, IDR_FREE, offset);
1999 else
2000 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
2001 node_tag_clear(root, node, tag, offset);
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002002
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002003 replace_slot(slot, NULL, node, -1, exceptional);
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002004 return node && delete_node(root, node, NULL, NULL);
2005}
2006
Johannes Weiner139e5612014-04-03 14:47:54 -07002007/**
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002008 * radix_tree_iter_delete - delete the entry at this iterator position
2009 * @root: radix tree root
2010 * @iter: iterator state
2011 * @slot: pointer to slot
Linus Torvalds1da177e2005-04-16 15:20:36 -07002012 *
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002013 * Delete the entry at the position currently pointed to by the iterator.
2014 * This may result in the current node being freed; if it is, the iterator
2015 * is advanced so that it will not reference the freed memory. This
2016 * function may be called without any locking if there are no other threads
2017 * which can access this tree.
2018 */
2019void radix_tree_iter_delete(struct radix_tree_root *root,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05002020 struct radix_tree_iter *iter, void __rcu **slot)
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002021{
2022 if (__radix_tree_delete(root, iter->node, slot))
2023 iter->index = iter->next_index;
2024}
2025
2026/**
2027 * radix_tree_delete_item - delete an item from a radix tree
2028 * @root: radix tree root
2029 * @index: index key
2030 * @item: expected item
Linus Torvalds1da177e2005-04-16 15:20:36 -07002031 *
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002032 * Remove @item at @index from the radix tree rooted at @root.
2033 *
2034 * Return: the deleted entry, or %NULL if it was not present
2035 * or the entry at the given @index was not @item.
Linus Torvalds1da177e2005-04-16 15:20:36 -07002036 */
Johannes Weiner53c59f22014-04-03 14:47:39 -07002037void *radix_tree_delete_item(struct radix_tree_root *root,
2038 unsigned long index, void *item)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002039{
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002040 struct radix_tree_node *node = NULL;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05002041 void __rcu **slot;
Johannes Weiner139e5612014-04-03 14:47:54 -07002042 void *entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002043
Johannes Weiner139e5612014-04-03 14:47:54 -07002044 entry = __radix_tree_lookup(root, index, &node, &slot);
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002045 if (!entry && (!is_idr(root) || node_tag_get(root, node, IDR_FREE,
2046 get_slot_offset(node, slot))))
Johannes Weiner139e5612014-04-03 14:47:54 -07002047 return NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002048
Johannes Weiner139e5612014-04-03 14:47:54 -07002049 if (item && entry != item)
2050 return NULL;
2051
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002052 __radix_tree_delete(root, node, slot);
Christoph Lameter201b6262005-09-06 15:16:46 -07002053
Johannes Weiner139e5612014-04-03 14:47:54 -07002054 return entry;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002055}
Johannes Weiner53c59f22014-04-03 14:47:39 -07002056EXPORT_SYMBOL(radix_tree_delete_item);
2057
2058/**
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002059 * radix_tree_delete - delete an entry from a radix tree
2060 * @root: radix tree root
2061 * @index: index key
Johannes Weiner53c59f22014-04-03 14:47:39 -07002062 *
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002063 * Remove the entry at @index from the radix tree rooted at @root.
Johannes Weiner53c59f22014-04-03 14:47:39 -07002064 *
Matthew Wilcox0ac398e2017-01-28 09:56:22 -05002065 * Return: The deleted entry, or %NULL if it was not present.
Johannes Weiner53c59f22014-04-03 14:47:39 -07002066 */
2067void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
2068{
2069 return radix_tree_delete_item(root, index, NULL);
2070}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002071EXPORT_SYMBOL(radix_tree_delete);
2072
Johannes Weinerd3798ae2016-10-04 22:02:08 +02002073void radix_tree_clear_tags(struct radix_tree_root *root,
2074 struct radix_tree_node *node,
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05002075 void __rcu **slot)
Matthew Wilcoxd604c322016-05-20 17:03:45 -07002076{
Matthew Wilcoxd604c322016-05-20 17:03:45 -07002077 if (node) {
2078 unsigned int tag, offset = get_slot_offset(node, slot);
2079 for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
2080 node_tag_clear(root, node, tag, offset);
2081 } else {
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002082 root_tag_clear_all(root);
Matthew Wilcoxd604c322016-05-20 17:03:45 -07002083 }
Matthew Wilcoxd604c322016-05-20 17:03:45 -07002084}
2085
Linus Torvalds1da177e2005-04-16 15:20:36 -07002086/**
2087 * radix_tree_tagged - test whether any items in the tree are tagged
2088 * @root: radix tree root
2089 * @tag: tag to test
2090 */
Matthew Wilcox35534c82016-12-19 17:43:19 -05002091int radix_tree_tagged(const struct radix_tree_root *root, unsigned int tag)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002092{
Nick Piggin612d6c12006-06-23 02:03:22 -07002093 return root_tag_get(root, tag);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002094}
2095EXPORT_SYMBOL(radix_tree_tagged);
2096
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002097/**
2098 * idr_preload - preload for idr_alloc()
2099 * @gfp_mask: allocation mask to use for preloading
2100 *
2101 * Preallocate memory to use for the next call to idr_alloc(). This function
2102 * returns with preemption disabled. It will be enabled by idr_preload_end().
2103 */
2104void idr_preload(gfp_t gfp_mask)
2105{
2106 __radix_tree_preload(gfp_mask, IDR_PRELOAD_SIZE);
2107}
2108EXPORT_SYMBOL(idr_preload);
2109
Matthew Wilcox7ad3d4d2016-12-16 11:55:56 -05002110/**
2111 * ida_pre_get - reserve resources for ida allocation
2112 * @ida: ida handle
2113 * @gfp: memory allocation flags
2114 *
2115 * This function should be called before calling ida_get_new_above(). If it
2116 * is unable to allocate memory, it will return %0. On success, it returns %1.
2117 */
2118int ida_pre_get(struct ida *ida, gfp_t gfp)
2119{
2120 __radix_tree_preload(gfp, IDA_PRELOAD_SIZE);
2121 /*
2122 * The IDA API has no preload_end() equivalent. Instead,
2123 * ida_get_new() can return -EAGAIN, prompting the caller
2124 * to return to the ida_pre_get() step.
2125 */
2126 preempt_enable();
2127
2128 if (!this_cpu_read(ida_bitmap)) {
2129 struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp);
2130 if (!bitmap)
2131 return 0;
2132 bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);
2133 kfree(bitmap);
2134 }
2135
2136 return 1;
2137}
2138EXPORT_SYMBOL(ida_pre_get);
2139
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05002140void __rcu **idr_get_free(struct radix_tree_root *root,
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002141 struct radix_tree_iter *iter, gfp_t gfp, int end)
2142{
2143 struct radix_tree_node *node = NULL, *child;
Matthew Wilcoxd7b62722017-02-13 15:58:24 -05002144 void __rcu **slot = (void __rcu **)&root->rnode;
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002145 unsigned long maxindex, start = iter->next_index;
2146 unsigned long max = end > 0 ? end - 1 : INT_MAX;
2147 unsigned int shift, offset = 0;
2148
2149 grow:
2150 shift = radix_tree_load_root(root, &child, &maxindex);
2151 if (!radix_tree_tagged(root, IDR_FREE))
2152 start = max(start, maxindex + 1);
2153 if (start > max)
2154 return ERR_PTR(-ENOSPC);
2155
2156 if (start > maxindex) {
2157 int error = radix_tree_extend(root, gfp, start, shift);
2158 if (error < 0)
2159 return ERR_PTR(error);
2160 shift = error;
2161 child = rcu_dereference_raw(root->rnode);
2162 }
2163
2164 while (shift) {
2165 shift -= RADIX_TREE_MAP_SHIFT;
2166 if (child == NULL) {
2167 /* Have to add a child node. */
Matthew Wilcoxd58275b2017-01-16 17:10:21 -05002168 child = radix_tree_node_alloc(gfp, node, root, shift,
2169 offset, 0, 0);
Matthew Wilcox0a835c42016-12-20 10:27:56 -05002170 if (!child)
2171 return ERR_PTR(-ENOMEM);
2172 all_tag_set(child, IDR_FREE);
2173 rcu_assign_pointer(*slot, node_to_entry(child));
2174 if (node)
2175 node->count++;
2176 } else if (!radix_tree_is_internal_node(child))
2177 break;
2178
2179 node = entry_to_node(child);
2180 offset = radix_tree_descend(node, &child, start);
2181 if (!tag_get(node, IDR_FREE, offset)) {
2182 offset = radix_tree_find_next_bit(node, IDR_FREE,
2183 offset + 1);
2184 start = next_index(start, node, offset);
2185 if (start > max)
2186 return ERR_PTR(-ENOSPC);
2187 while (offset == RADIX_TREE_MAP_SIZE) {
2188 offset = node->offset + 1;
2189 node = node->parent;
2190 if (!node)
2191 goto grow;
2192 shift = node->shift;
2193 }
2194 child = rcu_dereference_raw(node->slots[offset]);
2195 }
2196 slot = &node->slots[offset];
2197 }
2198
2199 iter->index = start;
2200 if (node)
2201 iter->next_index = 1 + min(max, (start | node_maxindex(node)));
2202 else
2203 iter->next_index = 1;
2204 iter->node = node;
2205 __set_iter_shift(iter, shift);
2206 set_iter_tags(iter, node, offset, IDR_FREE);
2207
2208 return slot;
2209}
2210
2211/**
2212 * idr_destroy - release all internal memory from an IDR
2213 * @idr: idr handle
2214 *
2215 * After this function is called, the IDR is empty, and may be reused or
2216 * the data structure containing it may be freed.
2217 *
2218 * A typical clean-up sequence for objects stored in an idr tree will use
2219 * idr_for_each() to free all objects, if necessary, then idr_destroy() to
2220 * free the memory used to keep track of those objects.
2221 */
2222void idr_destroy(struct idr *idr)
2223{
2224 struct radix_tree_node *node = rcu_dereference_raw(idr->idr_rt.rnode);
2225 if (radix_tree_is_internal_node(node))
2226 radix_tree_free_nodes(node);
2227 idr->idr_rt.rnode = NULL;
2228 root_tag_set(&idr->idr_rt, IDR_FREE);
2229}
2230EXPORT_SYMBOL(idr_destroy);
2231
Linus Torvalds1da177e2005-04-16 15:20:36 -07002232static void
Johannes Weiner449dd692014-04-03 14:47:56 -07002233radix_tree_node_ctor(void *arg)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002234{
Johannes Weiner449dd692014-04-03 14:47:56 -07002235 struct radix_tree_node *node = arg;
2236
2237 memset(node, 0, sizeof(*node));
2238 INIT_LIST_HEAD(&node->private_list);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002239}
2240
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -07002241static __init unsigned long __maxindex(unsigned int height)
2242{
2243 unsigned int width = height * RADIX_TREE_MAP_SHIFT;
2244 int shift = RADIX_TREE_INDEX_BITS - width;
2245
2246 if (shift < 0)
2247 return ~0UL;
2248 if (shift >= BITS_PER_LONG)
2249 return 0UL;
2250 return ~0UL >> shift;
2251}
2252
2253static __init void radix_tree_init_maxnodes(void)
2254{
2255 unsigned long height_to_maxindex[RADIX_TREE_MAX_PATH + 1];
2256 unsigned int i, j;
2257
2258 for (i = 0; i < ARRAY_SIZE(height_to_maxindex); i++)
2259 height_to_maxindex[i] = __maxindex(i);
2260 for (i = 0; i < ARRAY_SIZE(height_to_maxnodes); i++) {
2261 for (j = i; j > 0; j--)
2262 height_to_maxnodes[i] += height_to_maxindex[j - 1] + 1;
2263 }
2264}
2265
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002266static int radix_tree_cpu_dead(unsigned int cpu)
Linus Torvalds1da177e2005-04-16 15:20:36 -07002267{
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07002268 struct radix_tree_preload *rtp;
2269 struct radix_tree_node *node;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002270
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07002271 /* Free per-cpu pool of preloaded nodes */
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002272 rtp = &per_cpu(radix_tree_preloads, cpu);
2273 while (rtp->nr) {
2274 node = rtp->nodes;
Matthew Wilcox1293d5c2017-01-16 16:41:29 -05002275 rtp->nodes = node->parent;
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002276 kmem_cache_free(radix_tree_node_cachep, node);
2277 rtp->nr--;
Matthew Wilcox2fcd9002016-05-20 17:03:04 -07002278 }
Matthew Wilcox7ad3d4d2016-12-16 11:55:56 -05002279 kfree(per_cpu(ida_bitmap, cpu));
2280 per_cpu(ida_bitmap, cpu) = NULL;
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002281 return 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002282}
Linus Torvalds1da177e2005-04-16 15:20:36 -07002283
2284void __init radix_tree_init(void)
2285{
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002286 int ret;
Linus Torvalds1da177e2005-04-16 15:20:36 -07002287 radix_tree_node_cachep = kmem_cache_create("radix_tree_node",
2288 sizeof(struct radix_tree_node), 0,
Christoph Lameter488514d2008-04-28 02:12:05 -07002289 SLAB_PANIC | SLAB_RECLAIM_ACCOUNT,
2290 radix_tree_node_ctor);
Kirill A. Shutemovc78c66d2016-07-26 15:26:02 -07002291 radix_tree_init_maxnodes();
Sebastian Andrzej Siewiord544abd2016-11-03 15:50:01 +01002292 ret = cpuhp_setup_state_nocalls(CPUHP_RADIX_DEAD, "lib/radix:dead",
2293 NULL, radix_tree_cpu_dead);
2294 WARN_ON(ret < 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -07002295}