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 preempt_enable();
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)
189
190
191
192
193
194
195
196
197
198
199
200#define idr_for_each_entry_ul(idr, entry, id) \
201 for (id = 0; ((entry) = idr_get_next_ul(idr, &(id))) != NULL; ++id)
202
203
204
205
206
207
208
209
210
211#define idr_for_each_entry_continue(idr, entry, id) \
212 for ((entry) = idr_get_next((idr), &(id)); \
213 entry; \
214 ++id, (entry) = idr_get_next((idr), &(id)))
215
216
217
218
219#define IDA_CHUNK_SIZE 128
220#define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long))
221#define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8)
222
223struct ida_bitmap {
224 unsigned long bitmap[IDA_BITMAP_LONGS];
225};
226
227struct ida {
228 struct xarray xa;
229};
230
231#define IDA_INIT_FLAGS (XA_FLAGS_LOCK_IRQ | XA_FLAGS_ALLOC)
232
233#define IDA_INIT(name) { \
234 .xa = XARRAY_INIT(name, IDA_INIT_FLAGS) \
235}
236#define DEFINE_IDA(name) struct ida name = IDA_INIT(name)
237
238int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t);
239void ida_free(struct ida *, unsigned int id);
240void ida_destroy(struct ida *ida);
241
242
243
244
245
246
247
248
249
250
251
252
253static inline int ida_alloc(struct ida *ida, gfp_t gfp)
254{
255 return ida_alloc_range(ida, 0, ~0, gfp);
256}
257
258
259
260
261
262
263
264
265
266
267
268
269
270static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp)
271{
272 return ida_alloc_range(ida, min, ~0, gfp);
273}
274
275
276
277
278
279
280
281
282
283
284
285
286
287static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp)
288{
289 return ida_alloc_range(ida, 0, max, gfp);
290}
291
292static inline void ida_init(struct ida *ida)
293{
294 xa_init_flags(&ida->xa, IDA_INIT_FLAGS);
295}
296
297#define ida_simple_get(ida, start, end, gfp) \
298 ida_alloc_range(ida, start, (end) - 1, gfp)
299#define ida_simple_remove(ida, id) ida_free(ida, id)
300
301static inline bool ida_is_empty(const struct ida *ida)
302{
303 return xa_empty(&ida->xa);
304}
305#endif
306