1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21#ifndef _LINUX_RADIX_TREE_H
22#define _LINUX_RADIX_TREE_H
23
24#include <linux/bitops.h>
25#include <linux/kernel.h>
26#include <linux/list.h>
27#include <linux/preempt.h>
28#include <linux/rcupdate.h>
29#include <linux/spinlock.h>
30#include <linux/types.h>
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48#define RADIX_TREE_ENTRY_MASK 3UL
49#define RADIX_TREE_INTERNAL_NODE 1UL
50
51
52
53
54
55
56
57#define RADIX_TREE_EXCEPTIONAL_ENTRY 2
58#define RADIX_TREE_EXCEPTIONAL_SHIFT 2
59
60static inline bool radix_tree_is_internal_node(void *ptr)
61{
62 return ((unsigned long)ptr & RADIX_TREE_ENTRY_MASK) ==
63 RADIX_TREE_INTERNAL_NODE;
64}
65
66
67
68#define RADIX_TREE_MAX_TAGS 3
69
70#ifndef RADIX_TREE_MAP_SHIFT
71#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
72#endif
73
74#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
75#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
76
77#define RADIX_TREE_TAG_LONGS \
78 ((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
79
80#define RADIX_TREE_INDEX_BITS (8 * sizeof(unsigned long))
81#define RADIX_TREE_MAX_PATH (DIV_ROUND_UP(RADIX_TREE_INDEX_BITS, \
82 RADIX_TREE_MAP_SHIFT))
83
84
85
86
87
88
89
90
91
92struct radix_tree_node {
93 unsigned char shift;
94 unsigned char offset;
95 unsigned char count;
96 unsigned char exceptional;
97 struct radix_tree_node *parent;
98 struct radix_tree_root *root;
99 union {
100 struct list_head private_list;
101 struct rcu_head rcu_head;
102 };
103 void __rcu *slots[RADIX_TREE_MAP_SIZE];
104 unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
105};
106
107
108#define ROOT_IS_IDR ((__force gfp_t)(1 << __GFP_BITS_SHIFT))
109#define ROOT_TAG_SHIFT (__GFP_BITS_SHIFT + 1)
110
111struct radix_tree_root {
112 gfp_t gfp_mask;
113 struct radix_tree_node __rcu *rnode;
114};
115
116#define RADIX_TREE_INIT(mask) { \
117 .gfp_mask = (mask), \
118 .rnode = NULL, \
119}
120
121#define RADIX_TREE(name, mask) \
122 struct radix_tree_root name = RADIX_TREE_INIT(mask)
123
124#define INIT_RADIX_TREE(root, mask) \
125do { \
126 (root)->gfp_mask = (mask); \
127 (root)->rnode = NULL; \
128} while (0)
129
130static inline bool radix_tree_empty(const struct radix_tree_root *root)
131{
132 return root->rnode == NULL;
133}
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151struct radix_tree_iter {
152 unsigned long index;
153 unsigned long next_index;
154 unsigned long tags;
155 struct radix_tree_node *node;
156#ifdef CONFIG_RADIX_TREE_MULTIORDER
157 unsigned int shift;
158#endif
159};
160
161static inline unsigned int iter_shift(const struct radix_tree_iter *iter)
162{
163#ifdef CONFIG_RADIX_TREE_MULTIORDER
164 return iter->shift;
165#else
166 return 0;
167#endif
168}
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235static inline void *radix_tree_deref_slot(void __rcu **slot)
236{
237 return rcu_dereference(*slot);
238}
239
240
241
242
243
244
245
246
247
248
249static inline void *radix_tree_deref_slot_protected(void __rcu **slot,
250 spinlock_t *treelock)
251{
252 return rcu_dereference_protected(*slot, lockdep_is_held(treelock));
253}
254
255
256
257
258
259
260
261
262static inline int radix_tree_deref_retry(void *arg)
263{
264 return unlikely(radix_tree_is_internal_node(arg));
265}
266
267
268
269
270
271
272static inline int radix_tree_exceptional_entry(void *arg)
273{
274
275 return (unsigned long)arg & RADIX_TREE_EXCEPTIONAL_ENTRY;
276}
277
278
279
280
281
282
283static inline int radix_tree_exception(void *arg)
284{
285 return unlikely((unsigned long)arg & RADIX_TREE_ENTRY_MASK);
286}
287
288int __radix_tree_create(struct radix_tree_root *, unsigned long index,
289 unsigned order, struct radix_tree_node **nodep,
290 void __rcu ***slotp);
291int __radix_tree_insert(struct radix_tree_root *, unsigned long index,
292 unsigned order, void *);
293static inline int radix_tree_insert(struct radix_tree_root *root,
294 unsigned long index, void *entry)
295{
296 return __radix_tree_insert(root, index, 0, entry);
297}
298void *__radix_tree_lookup(const struct radix_tree_root *, unsigned long index,
299 struct radix_tree_node **nodep, void __rcu ***slotp);
300void *radix_tree_lookup(const struct radix_tree_root *, unsigned long);
301void __rcu **radix_tree_lookup_slot(const struct radix_tree_root *,
302 unsigned long index);
303typedef void (*radix_tree_update_node_t)(struct radix_tree_node *);
304void __radix_tree_replace(struct radix_tree_root *, struct radix_tree_node *,
305 void __rcu **slot, void *entry,
306 radix_tree_update_node_t update_node);
307void radix_tree_iter_replace(struct radix_tree_root *,
308 const struct radix_tree_iter *, void __rcu **slot, void *entry);
309void radix_tree_replace_slot(struct radix_tree_root *,
310 void __rcu **slot, void *entry);
311void __radix_tree_delete_node(struct radix_tree_root *,
312 struct radix_tree_node *,
313 radix_tree_update_node_t update_node);
314void radix_tree_iter_delete(struct radix_tree_root *,
315 struct radix_tree_iter *iter, void __rcu **slot);
316void *radix_tree_delete_item(struct radix_tree_root *, unsigned long, void *);
317void *radix_tree_delete(struct radix_tree_root *, unsigned long);
318void radix_tree_clear_tags(struct radix_tree_root *, struct radix_tree_node *,
319 void __rcu **slot);
320unsigned int radix_tree_gang_lookup(const struct radix_tree_root *,
321 void **results, unsigned long first_index,
322 unsigned int max_items);
323unsigned int radix_tree_gang_lookup_slot(const struct radix_tree_root *,
324 void __rcu ***results, unsigned long *indices,
325 unsigned long first_index, unsigned int max_items);
326int radix_tree_preload(gfp_t gfp_mask);
327int radix_tree_maybe_preload(gfp_t gfp_mask);
328int radix_tree_maybe_preload_order(gfp_t gfp_mask, int order);
329void radix_tree_init(void);
330void *radix_tree_tag_set(struct radix_tree_root *,
331 unsigned long index, unsigned int tag);
332void *radix_tree_tag_clear(struct radix_tree_root *,
333 unsigned long index, unsigned int tag);
334int radix_tree_tag_get(const struct radix_tree_root *,
335 unsigned long index, unsigned int tag);
336void radix_tree_iter_tag_set(struct radix_tree_root *,
337 const struct radix_tree_iter *iter, unsigned int tag);
338void radix_tree_iter_tag_clear(struct radix_tree_root *,
339 const struct radix_tree_iter *iter, unsigned int tag);
340unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *,
341 void **results, unsigned long first_index,
342 unsigned int max_items, unsigned int tag);
343unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *,
344 void __rcu ***results, unsigned long first_index,
345 unsigned int max_items, unsigned int tag);
346int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag);
347
348static inline void radix_tree_preload_end(void)
349{
350 preempt_enable();
351}
352
353int radix_tree_split_preload(unsigned old_order, unsigned new_order, gfp_t);
354int radix_tree_split(struct radix_tree_root *, unsigned long index,
355 unsigned new_order);
356int radix_tree_join(struct radix_tree_root *, unsigned long index,
357 unsigned new_order, void *);
358
359void __rcu **idr_get_free_cmn(struct radix_tree_root *root,
360 struct radix_tree_iter *iter, gfp_t gfp,
361 unsigned long max);
362static inline void __rcu **idr_get_free(struct radix_tree_root *root,
363 struct radix_tree_iter *iter,
364 gfp_t gfp,
365 int end)
366{
367 return idr_get_free_cmn(root, iter, gfp, end > 0 ? end - 1 : INT_MAX);
368}
369
370static inline void __rcu **idr_get_free_ext(struct radix_tree_root *root,
371 struct radix_tree_iter *iter,
372 gfp_t gfp,
373 unsigned long end)
374{
375 return idr_get_free_cmn(root, iter, gfp, end - 1);
376}
377
378enum {
379 RADIX_TREE_ITER_TAG_MASK = 0x0f,
380 RADIX_TREE_ITER_TAGGED = 0x10,
381 RADIX_TREE_ITER_CONTIG = 0x20,
382};
383
384
385
386
387
388
389
390
391static __always_inline void __rcu **
392radix_tree_iter_init(struct radix_tree_iter *iter, unsigned long start)
393{
394
395
396
397
398
399
400
401
402 iter->index = 0;
403 iter->next_index = start;
404 return NULL;
405}
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420void __rcu **radix_tree_next_chunk(const struct radix_tree_root *,
421 struct radix_tree_iter *iter, unsigned flags);
422
423
424
425
426
427
428
429
430
431
432
433static inline void __rcu **
434radix_tree_iter_lookup(const struct radix_tree_root *root,
435 struct radix_tree_iter *iter, unsigned long index)
436{
437 radix_tree_iter_init(iter, index);
438 return radix_tree_next_chunk(root, iter, RADIX_TREE_ITER_CONTIG);
439}
440
441
442
443
444
445
446
447
448
449
450
451static inline void __rcu **
452radix_tree_iter_find(const struct radix_tree_root *root,
453 struct radix_tree_iter *iter, unsigned long index)
454{
455 radix_tree_iter_init(iter, index);
456 return radix_tree_next_chunk(root, iter, 0);
457}
458
459
460
461
462
463
464
465
466
467
468static inline __must_check
469void __rcu **radix_tree_iter_retry(struct radix_tree_iter *iter)
470{
471 iter->next_index = iter->index;
472 iter->tags = 0;
473 return NULL;
474}
475
476static inline unsigned long
477__radix_tree_iter_add(struct radix_tree_iter *iter, unsigned long slots)
478{
479 return iter->index + (slots << iter_shift(iter));
480}
481
482
483
484
485
486
487
488
489
490
491
492void __rcu **__must_check radix_tree_iter_resume(void __rcu **slot,
493 struct radix_tree_iter *iter);
494
495
496
497
498
499
500
501static __always_inline long
502radix_tree_chunk_size(struct radix_tree_iter *iter)
503{
504 return (iter->next_index - iter->index) >> iter_shift(iter);
505}
506
507#ifdef CONFIG_RADIX_TREE_MULTIORDER
508void __rcu **__radix_tree_next_slot(void __rcu **slot,
509 struct radix_tree_iter *iter, unsigned flags);
510#else
511
512static inline void __rcu **__radix_tree_next_slot(void __rcu **slot,
513 struct radix_tree_iter *iter, unsigned flags)
514{
515 return slot;
516}
517#endif
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538static __always_inline void __rcu **radix_tree_next_slot(void __rcu **slot,
539 struct radix_tree_iter *iter, unsigned flags)
540{
541 if (flags & RADIX_TREE_ITER_TAGGED) {
542 iter->tags >>= 1;
543 if (unlikely(!iter->tags))
544 return NULL;
545 if (likely(iter->tags & 1ul)) {
546 iter->index = __radix_tree_iter_add(iter, 1);
547 slot++;
548 goto found;
549 }
550 if (!(flags & RADIX_TREE_ITER_CONTIG)) {
551 unsigned offset = __ffs(iter->tags);
552
553 iter->tags >>= offset++;
554 iter->index = __radix_tree_iter_add(iter, offset);
555 slot += offset;
556 goto found;
557 }
558 } else {
559 long count = radix_tree_chunk_size(iter);
560
561 while (--count > 0) {
562 slot++;
563 iter->index = __radix_tree_iter_add(iter, 1);
564
565 if (likely(*slot))
566 goto found;
567 if (flags & RADIX_TREE_ITER_CONTIG) {
568
569 iter->next_index = 0;
570 break;
571 }
572 }
573 }
574 return NULL;
575
576 found:
577 if (unlikely(radix_tree_is_internal_node(rcu_dereference_raw(*slot))))
578 return __radix_tree_next_slot(slot, iter, flags);
579 return slot;
580}
581
582
583
584
585
586
587
588
589
590
591
592#define radix_tree_for_each_slot(slot, root, iter, start) \
593 for (slot = radix_tree_iter_init(iter, start) ; \
594 slot || (slot = radix_tree_next_chunk(root, iter, 0)) ; \
595 slot = radix_tree_next_slot(slot, iter, 0))
596
597
598
599
600
601
602
603
604
605
606
607#define radix_tree_for_each_contig(slot, root, iter, start) \
608 for (slot = radix_tree_iter_init(iter, start) ; \
609 slot || (slot = radix_tree_next_chunk(root, iter, \
610 RADIX_TREE_ITER_CONTIG)) ; \
611 slot = radix_tree_next_slot(slot, iter, \
612 RADIX_TREE_ITER_CONTIG))
613
614
615
616
617
618
619
620
621
622
623
624
625#define radix_tree_for_each_tagged(slot, root, iter, start, tag) \
626 for (slot = radix_tree_iter_init(iter, start) ; \
627 slot || (slot = radix_tree_next_chunk(root, iter, \
628 RADIX_TREE_ITER_TAGGED | tag)) ; \
629 slot = radix_tree_next_slot(slot, iter, \
630 RADIX_TREE_ITER_TAGGED | tag))
631
632#endif
633