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