]>
Commit | Line | Data |
---|---|---|
1da177e4 LT |
1 | /* |
2 | * include/linux/idr.h | |
3 | * | |
4 | * 2002-10-18 written by Jim Houston jim.houston@ccur.com | |
5 | * Copyright (C) 2002 by Concurrent Computer Corporation | |
6 | * Distributed under the GNU GPL license version 2. | |
7 | * | |
8 | * Small id to pointer translation service avoiding fixed sized | |
9 | * tables. | |
10 | */ | |
f668ab1a LT |
11 | |
12 | #ifndef __IDR_H__ | |
13 | #define __IDR_H__ | |
14 | ||
0a835c4f MW |
15 | #include <linux/radix-tree.h> |
16 | #include <linux/gfp.h> | |
17 | ||
18 | struct idr { | |
19 | struct radix_tree_root idr_rt; | |
20 | unsigned int idr_next; | |
21 | }; | |
1da177e4 | 22 | |
050a6b47 | 23 | /* |
0a835c4f MW |
24 | * The IDR API does not expose the tagging functionality of the radix tree |
25 | * to users. Use tag 0 to track whether a node has free space below it. | |
050a6b47 | 26 | */ |
0a835c4f | 27 | #define IDR_FREE 0 |
1da177e4 | 28 | |
0a835c4f MW |
29 | /* Set the IDR flag and the IDR_FREE tag */ |
30 | #define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT)) | |
1da177e4 | 31 | |
0a835c4f | 32 | #define IDR_INIT \ |
4106ecaf | 33 | { \ |
0a835c4f | 34 | .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \ |
1da177e4 | 35 | } |
0a835c4f | 36 | #define DEFINE_IDR(name) struct idr name = IDR_INIT |
1da177e4 | 37 | |
44430612 MW |
38 | /** |
39 | * idr_get_cursor - Return the current position of the cyclic allocator | |
40 | * @idr: idr handle | |
41 | * | |
42 | * The value returned is the value that will be next returned from | |
43 | * idr_alloc_cyclic() if it is free (otherwise the search will start from | |
44 | * this position). | |
45 | */ | |
0a835c4f | 46 | static inline unsigned int idr_get_cursor(const struct idr *idr) |
44430612 | 47 | { |
0a835c4f | 48 | return READ_ONCE(idr->idr_next); |
44430612 MW |
49 | } |
50 | ||
51 | /** | |
52 | * idr_set_cursor - Set the current position of the cyclic allocator | |
53 | * @idr: idr handle | |
54 | * @val: new position | |
55 | * | |
56 | * The next call to idr_alloc_cyclic() will return @val if it is free | |
57 | * (otherwise the search will start from this position). | |
58 | */ | |
59 | static inline void idr_set_cursor(struct idr *idr, unsigned int val) | |
60 | { | |
0a835c4f | 61 | WRITE_ONCE(idr->idr_next, val); |
44430612 MW |
62 | } |
63 | ||
f9c46d6e | 64 | /** |
56083ab1 | 65 | * DOC: idr sync |
f9c46d6e ND |
66 | * idr synchronization (stolen from radix-tree.h) |
67 | * | |
68 | * idr_find() is able to be called locklessly, using RCU. The caller must | |
69 | * ensure calls to this function are made within rcu_read_lock() regions. | |
70 | * Other readers (lock-free or otherwise) and modifications may be running | |
71 | * concurrently. | |
72 | * | |
73 | * It is still required that the caller manage the synchronization and | |
74 | * lifetimes of the items. So if RCU lock-free lookups are used, typically | |
75 | * this would mean that the items have their own locks, or are amenable to | |
76 | * lock-free access; and that the items are freed by RCU (or only freed after | |
77 | * having been deleted from the idr tree *and* a synchronize_rcu() grace | |
78 | * period). | |
79 | */ | |
80 | ||
d5c7409f | 81 | void idr_preload(gfp_t gfp_mask); |
0a835c4f MW |
82 | int idr_alloc(struct idr *, void *entry, int start, int end, gfp_t); |
83 | int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); | |
84 | int idr_for_each(const struct idr *, | |
96d7fa42 | 85 | int (*fn)(int id, void *p, void *data), void *data); |
0a835c4f MW |
86 | void *idr_get_next(struct idr *, int *nextid); |
87 | void *idr_replace(struct idr *, void *, int id); | |
88 | void idr_destroy(struct idr *); | |
89 | ||
90 | static inline void idr_remove(struct idr *idr, int id) | |
91 | { | |
92 | radix_tree_delete(&idr->idr_rt, id); | |
93 | } | |
94 | ||
95 | static inline void idr_init(struct idr *idr) | |
96 | { | |
97 | INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); | |
98 | idr->idr_next = 0; | |
99 | } | |
100 | ||
101 | static inline bool idr_is_empty(const struct idr *idr) | |
102 | { | |
103 | return radix_tree_empty(&idr->idr_rt) && | |
104 | radix_tree_tagged(&idr->idr_rt, IDR_FREE); | |
105 | } | |
f668ab1a | 106 | |
d5c7409f TH |
107 | /** |
108 | * idr_preload_end - end preload section started with idr_preload() | |
109 | * | |
110 | * Each idr_preload() should be matched with an invocation of this | |
111 | * function. See idr_preload() for details. | |
112 | */ | |
113 | static inline void idr_preload_end(void) | |
114 | { | |
115 | preempt_enable(); | |
116 | } | |
117 | ||
0ffc2a9c TH |
118 | /** |
119 | * idr_find - return pointer for given id | |
5857f70c | 120 | * @idr: idr handle |
0ffc2a9c TH |
121 | * @id: lookup key |
122 | * | |
123 | * Return the pointer given the id it has been registered with. A %NULL | |
124 | * return indicates that @id is not valid or you passed %NULL in | |
125 | * idr_get_new(). | |
126 | * | |
127 | * This function can be called under rcu_read_lock(), given that the leaf | |
128 | * pointers lifetimes are correctly managed. | |
129 | */ | |
0a835c4f | 130 | static inline void *idr_find(const struct idr *idr, int id) |
0ffc2a9c | 131 | { |
0a835c4f | 132 | return radix_tree_lookup(&idr->idr_rt, id); |
0ffc2a9c TH |
133 | } |
134 | ||
49038ef4 TH |
135 | /** |
136 | * idr_for_each_entry - iterate over an idr's elements of a given type | |
0a835c4f | 137 | * @idr: idr handle |
49038ef4 TH |
138 | * @entry: the type * to use as cursor |
139 | * @id: id entry's key | |
b949be58 GS |
140 | * |
141 | * @entry and @id do not need to be initialized before the loop, and | |
142 | * after normal terminatinon @entry is left with the value NULL. This | |
143 | * is convenient for a "not found" value. | |
49038ef4 | 144 | */ |
0a835c4f MW |
145 | #define idr_for_each_entry(idr, entry, id) \ |
146 | for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) | |
49038ef4 | 147 | |
a55bbd37 | 148 | /** |
0a835c4f MW |
149 | * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type |
150 | * @idr: idr handle | |
a55bbd37 AG |
151 | * @entry: the type * to use as cursor |
152 | * @id: id entry's key | |
153 | * | |
154 | * Continue to iterate over list of given type, continuing after | |
155 | * the current position. | |
156 | */ | |
0a835c4f MW |
157 | #define idr_for_each_entry_continue(idr, entry, id) \ |
158 | for ((entry) = idr_get_next((idr), &(id)); \ | |
a55bbd37 | 159 | entry; \ |
0a835c4f | 160 | ++id, (entry) = idr_get_next((idr), &(id))) |
a55bbd37 | 161 | |
72dba584 TH |
162 | /* |
163 | * IDA - IDR based id allocator, use when translation from id to | |
164 | * pointer isn't necessary. | |
165 | */ | |
166 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ | |
0a835c4f | 167 | #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
ed9f524a | 168 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
72dba584 TH |
169 | |
170 | struct ida_bitmap { | |
72dba584 TH |
171 | unsigned long bitmap[IDA_BITMAP_LONGS]; |
172 | }; | |
173 | ||
174 | struct ida { | |
0a835c4f | 175 | struct radix_tree_root ida_rt; |
72dba584 TH |
176 | struct ida_bitmap *free_bitmap; |
177 | }; | |
178 | ||
0a835c4f MW |
179 | #define IDA_INIT { \ |
180 | .ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ | |
181 | } | |
182 | #define DEFINE_IDA(name) struct ida name = IDA_INIT | |
72dba584 TH |
183 | |
184 | int ida_pre_get(struct ida *ida, gfp_t gfp_mask); | |
185 | int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); | |
72dba584 TH |
186 | void ida_remove(struct ida *ida, int id); |
187 | void ida_destroy(struct ida *ida); | |
72dba584 | 188 | |
88eca020 RR |
189 | int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, |
190 | gfp_t gfp_mask); | |
191 | void ida_simple_remove(struct ida *ida, unsigned int id); | |
192 | ||
0a835c4f MW |
193 | static inline void ida_init(struct ida *ida) |
194 | { | |
195 | INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); | |
196 | ida->free_bitmap = NULL; | |
197 | } | |
198 | ||
9749f30f | 199 | /** |
49038ef4 TH |
200 | * ida_get_new - allocate new ID |
201 | * @ida: idr handle | |
202 | * @p_id: pointer to the allocated handle | |
203 | * | |
204 | * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. | |
9749f30f | 205 | */ |
49038ef4 TH |
206 | static inline int ida_get_new(struct ida *ida, int *p_id) |
207 | { | |
208 | return ida_get_new_above(ida, 0, p_id); | |
209 | } | |
210 | ||
0a835c4f | 211 | static inline bool ida_is_empty(const struct ida *ida) |
99c49407 | 212 | { |
0a835c4f | 213 | return radix_tree_empty(&ida->ida_rt); |
99c49407 | 214 | } |
f668ab1a | 215 | #endif /* __IDR_H__ */ |