1
2
3
4
5
6
7
8
9
10
11
12#ifndef __IDR_H__
13#define __IDR_H__
14
15#include <linux/radix-tree.h>
16#include <linux/gfp.h>
17#include <linux/percpu.h>
18
19struct idr {
20 struct radix_tree_root idr_rt;
21 unsigned int idr_base;
22 unsigned int idr_next;
23};
24
25
26
27
28
29#define IDR_FREE 0
30
31
32#define IDR_RT_MARKER (ROOT_IS_IDR | (__force gfp_t) \
33 (1 << (ROOT_TAG_SHIFT + IDR_FREE)))
34
35#define IDR_INIT_BASE(name, base) { \
36 .idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER), \
37 .idr_base = (base), \
38 .idr_next = 0, \
39}
40
41
42
43
44
45
46
47#define IDR_INIT(name) IDR_INIT_BASE(name, 0)
48
49
50
51
52
53
54
55
56#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
57
58
59
60
61
62
63
64
65
66static inline unsigned int idr_get_cursor(const struct idr *idr)
67{
68 return READ_ONCE(idr->idr_next);
69}
70
71
72
73
74
75
76
77
78
79static inline void idr_set_cursor(struct idr *idr, unsigned int val)
80{
81 WRITE_ONCE(idr->idr_next, val);
82}
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101#define idr_lock(idr) xa_lock(&(idr)->idr_rt)
102#define idr_unlock(idr) xa_unlock(&(idr)->idr_rt)
103#define idr_lock_bh(idr) xa_lock_bh(&(idr)->idr_rt)
104#define idr_unlock_bh(idr) xa_unlock_bh(&(idr)->idr_rt)
105#define idr_lock_irq(idr) xa_lock_irq(&(idr)->idr_rt)
106#define idr_unlock_irq(idr) xa_unlock_irq(&(idr)->idr_rt)
107#define idr_lock_irqsave(idr, flags) \
108 xa_lock_irqsave(&(idr)->idr_rt, flags)
109#define idr_unlock_irqrestore(idr, flags) \
110 xa_unlock_irqrestore(&(idr)->idr_rt, flags)
111
112void idr_preload(gfp_t gfp_mask);
113
114int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t);
115int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id,
116 unsigned long max, gfp_t);
117int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t);
118void *idr_remove(struct idr *, unsigned long id);
119void *idr_find(const struct idr *, unsigned long id);
120int idr_for_each(const struct idr *,
121 int (*fn)(int id, void *p, void *data), void *data);
122void *idr_get_next(struct idr *, int *nextid);
123void *idr_get_next_ul(struct idr *, unsigned long *nextid);
124void *idr_replace(struct idr *, void *, unsigned long id);
125void idr_destroy(struct idr *);
126
127
128
129
130
131
132
133
134
135static inline void idr_init_base(struct idr *idr, int base)
136{
137 INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER);
138 idr->idr_base = base;
139 idr->idr_next = 0;
140}
141
142
143
144
145
146
147
148
149static inline void idr_init(struct idr *idr)
150{
151 idr_init_base(idr, 0);
152}
153
154
155
156
157
158
159
160static inline bool idr_is_empty(const struct idr *idr)
161{
162 return radix_tree_empty(&idr->idr_rt) &&
163 radix_tree_tagged(&idr->idr_rt, IDR_FREE);
164}
165
166
167
168
169
170
171
172static inline void idr_preload_end(void)
173{
174 local_unlock(&radix_tree_preloads.lock);
175}
176
177
178
179
180
181
182
183
184
185
186
187#define idr_for_each_entry(idr, entry, id) \
188 for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; id += 1U)
189
190
191
192
193
194
195
196
197
198
199
200
201#define idr_for_each_entry_ul(idr, entry, tmp, id) \
202 for (tmp = 0, id = 0; \
203 tmp <= id && ((entry) = idr_get_next_ul(idr, &(id))) != NULL; \
204 tmp = id, ++id)
205
206
207
208
209
210
211
212
213
214#define idr_for_each_entry_continue(idr, entry, id) \
215 for ((entry) = idr_get_next((idr), &(id)); \
216 entry; \
217 ++id, (entry) = idr_get_next((idr), &(id)))
218
219
220
221
222
223
224
225
226
227
228#define idr_for_each_entry_continue_ul(idr, entry, tmp, id) \
229 for (tmp = id; \
230 tmp <= id && ((entry) = idr_get_next_ul(idr, &(id))) != NULL; \
231 tmp = id, ++id)
232
233
234
235
236#define IDA_CHUNK_SIZE 128
237#define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long))
238#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
239
240struct ida_bitmap {
241 unsigned long bitmap[IDA_BITMAP_LONGS];
242};
243
244struct ida {
245 struct xarray xa;
246};
247
248#define IDA_INIT_FLAGS (XA_FLAGS_LOCK_IRQ | XA_FLAGS_ALLOC)
249
250#define IDA_INIT(name) { \
251 .xa = XARRAY_INIT(name, IDA_INIT_FLAGS) \
252}
253#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
254
255int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
256void ida_free(struct ida *, unsigned int id);
257void ida_destroy(struct ida *ida);
258
259
260
261
262
263
264
265
266
267
268
269
270
271static inline int ida_alloc(struct ida *ida, gfp_t gfp)
272{
273 return ida_alloc_range(ida, 0, ~0, gfp);
274}
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)
290{
291 return ida_alloc_range(ida, min, ~0, gfp);
292}
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)
308{
309 return ida_alloc_range(ida, 0, max, gfp);
310}
311
312static inline void ida_init(struct ida *ida)
313{
314 xa_init_flags(&ida->xa, IDA_INIT_FLAGS);
315}
316
317
318
319
320
321#define ida_simple_get(ida, start, end, gfp) \
322 ida_alloc_range(ida, start, (end) - 1, gfp)
323#define ida_simple_remove(ida, id) ida_free(ida, id)
324
325static inline bool ida_is_empty(const struct ida *ida)
326{
327 return xa_empty(&ida->xa);
328}
329#endif
330