1 | /* SPDX-License-Identifier: GPL-2.0-only */ |
2 | /* |
3 | * include/linux/idr.h |
4 | * |
5 | * 2002-10-18 written by Jim Houston jim.houston@ccur.com |
6 | * Copyright (C) 2002 by Concurrent Computer Corporation |
7 | * |
8 | * Small id to pointer translation service avoiding fixed sized |
9 | * tables. |
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 | |
19 | struct idr { |
20 | struct radix_tree_root idr_rt; |
21 | unsigned int idr_base; |
22 | unsigned int idr_next; |
23 | }; |
24 | |
25 | /* |
26 | * The IDR API does not expose the tagging functionality of the radix tree |
27 | * to users. Use tag 0 to track whether a node has free space below it. |
28 | */ |
29 | #define IDR_FREE 0 |
30 | |
31 | /* Set the IDR flag and the IDR_FREE tag */ |
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 | * IDR_INIT() - Initialise an IDR. |
43 | * @name: Name of IDR. |
44 | * |
45 | * A freshly-initialised IDR contains no IDs. |
46 | */ |
47 | #define IDR_INIT(name) IDR_INIT_BASE(name, 0) |
48 | |
49 | /** |
50 | * DEFINE_IDR() - Define a statically-allocated IDR. |
51 | * @name: Name of IDR. |
52 | * |
53 | * An IDR defined using this macro is ready for use with no additional |
54 | * initialisation required. It contains no IDs. |
55 | */ |
56 | #define DEFINE_IDR(name) struct idr name = IDR_INIT(name) |
57 | |
58 | /** |
59 | * idr_get_cursor - Return the current position of the cyclic allocator |
60 | * @idr: idr handle |
61 | * |
62 | * The value returned is the value that will be next returned from |
63 | * idr_alloc_cyclic() if it is free (otherwise the search will start from |
64 | * this position). |
65 | */ |
66 | static inline unsigned int idr_get_cursor(const struct idr *idr) |
67 | { |
68 | return READ_ONCE(idr->idr_next); |
69 | } |
70 | |
71 | /** |
72 | * idr_set_cursor - Set the current position of the cyclic allocator |
73 | * @idr: idr handle |
74 | * @val: new position |
75 | * |
76 | * The next call to idr_alloc_cyclic() will return @val if it is free |
77 | * (otherwise the search will start from this position). |
78 | */ |
79 | static inline void idr_set_cursor(struct idr *idr, unsigned int val) |
80 | { |
81 | WRITE_ONCE(idr->idr_next, val); |
82 | } |
83 | |
84 | /** |
85 | * DOC: idr sync |
86 | * idr synchronization (stolen from radix-tree.h) |
87 | * |
88 | * idr_find() is able to be called locklessly, using RCU. The caller must |
89 | * ensure calls to this function are made within rcu_read_lock() regions. |
90 | * Other readers (lock-free or otherwise) and modifications may be running |
91 | * concurrently. |
92 | * |
93 | * It is still required that the caller manage the synchronization and |
94 | * lifetimes of the items. So if RCU lock-free lookups are used, typically |
95 | * this would mean that the items have their own locks, or are amenable to |
96 | * lock-free access; and that the items are freed by RCU (or only freed after |
97 | * having been deleted from the idr tree *and* a synchronize_rcu() grace |
98 | * period). |
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 | |
112 | void idr_preload(gfp_t gfp_mask); |
113 | |
114 | int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t); |
115 | int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id, |
116 | unsigned long max, gfp_t); |
117 | int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t); |
118 | void *idr_remove(struct idr *, unsigned long id); |
119 | void *idr_find(const struct idr *, unsigned long id); |
120 | int idr_for_each(const struct idr *, |
121 | int (*fn)(int id, void *p, void *data), void *data); |
122 | void *idr_get_next(struct idr *, int *nextid); |
123 | void *idr_get_next_ul(struct idr *, unsigned long *nextid); |
124 | void *idr_replace(struct idr *, void *, unsigned long id); |
125 | void idr_destroy(struct idr *); |
126 | |
127 | /** |
128 | * idr_init_base() - Initialise an IDR. |
129 | * @idr: IDR handle. |
130 | * @base: The base value for the IDR. |
131 | * |
132 | * This variation of idr_init() creates an IDR which will allocate IDs |
133 | * starting at %base. |
134 | */ |
135 | static 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 | * idr_init() - Initialise an IDR. |
144 | * @idr: IDR handle. |
145 | * |
146 | * Initialise a dynamically allocated IDR. To initialise a |
147 | * statically allocated IDR, use DEFINE_IDR(). |
148 | */ |
149 | static inline void idr_init(struct idr *idr) |
150 | { |
151 | idr_init_base(idr, base: 0); |
152 | } |
153 | |
154 | /** |
155 | * idr_is_empty() - Are there any IDs allocated? |
156 | * @idr: IDR handle. |
157 | * |
158 | * Return: %true if any IDs have been allocated from this IDR. |
159 | */ |
160 | static inline bool idr_is_empty(const struct idr *idr) |
161 | { |
162 | return radix_tree_empty(root: &idr->idr_rt) && |
163 | radix_tree_tagged(&idr->idr_rt, IDR_FREE); |
164 | } |
165 | |
166 | /** |
167 | * idr_preload_end - end preload section started with idr_preload() |
168 | * |
169 | * Each idr_preload() should be matched with an invocation of this |
170 | * function. See idr_preload() for details. |
171 | */ |
172 | static inline void idr_preload_end(void) |
173 | { |
174 | local_unlock(&radix_tree_preloads.lock); |
175 | } |
176 | |
177 | /** |
178 | * idr_for_each_entry() - Iterate over an IDR's elements of a given type. |
179 | * @idr: IDR handle. |
180 | * @entry: The type * to use as cursor |
181 | * @id: Entry ID. |
182 | * |
183 | * @entry and @id do not need to be initialized before the loop, and |
184 | * after normal termination @entry is left with the value NULL. This |
185 | * is convenient for a "not found" value. |
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 | * idr_for_each_entry_ul() - Iterate over an IDR's elements of a given type. |
192 | * @idr: IDR handle. |
193 | * @entry: The type * to use as cursor. |
194 | * @tmp: A temporary placeholder for ID. |
195 | * @id: Entry ID. |
196 | * |
197 | * @entry and @id do not need to be initialized before the loop, and |
198 | * after normal termination @entry is left with the value NULL. This |
199 | * is convenient for a "not found" value. |
200 | */ |
201 | #define idr_for_each_entry_ul(idr, entry, tmp, id) \ |
202 | for (tmp = 0, id = 0; \ |
203 | ((entry) = tmp <= id ? idr_get_next_ul(idr, &(id)) : NULL) != NULL; \ |
204 | tmp = id, ++id) |
205 | |
206 | /** |
207 | * idr_for_each_entry_continue() - Continue iteration over an IDR's elements of a given type |
208 | * @idr: IDR handle. |
209 | * @entry: The type * to use as a cursor. |
210 | * @id: Entry ID. |
211 | * |
212 | * Continue to iterate over entries, continuing after the current position. |
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 | * idr_for_each_entry_continue_ul() - Continue iteration over an IDR's elements of a given type |
221 | * @idr: IDR handle. |
222 | * @entry: The type * to use as a cursor. |
223 | * @tmp: A temporary placeholder for ID. |
224 | * @id: Entry ID. |
225 | * |
226 | * Continue to iterate over entries, continuing after the current position. |
227 | * After normal termination @entry is left with the value NULL. This |
228 | * is convenient for a "not found" value. |
229 | */ |
230 | #define idr_for_each_entry_continue_ul(idr, entry, tmp, id) \ |
231 | for (tmp = id; \ |
232 | ((entry) = tmp <= id ? idr_get_next_ul(idr, &(id)) : NULL) != NULL; \ |
233 | tmp = id, ++id) |
234 | |
235 | /* |
236 | * IDA - ID Allocator, use when translation from id to pointer isn't necessary. |
237 | */ |
238 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ |
239 | #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
240 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
241 | |
242 | struct ida_bitmap { |
243 | unsigned long bitmap[IDA_BITMAP_LONGS]; |
244 | }; |
245 | |
246 | struct ida { |
247 | struct xarray xa; |
248 | }; |
249 | |
250 | #define IDA_INIT_FLAGS (XA_FLAGS_LOCK_IRQ | XA_FLAGS_ALLOC) |
251 | |
252 | #define IDA_INIT(name) { \ |
253 | .xa = XARRAY_INIT(name, IDA_INIT_FLAGS) \ |
254 | } |
255 | #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) |
256 | |
257 | int ida_alloc_range(struct ida *, unsigned int min, unsigned int max, gfp_t); |
258 | void ida_free(struct ida *, unsigned int id); |
259 | void ida_destroy(struct ida *ida); |
260 | |
261 | /** |
262 | * ida_alloc() - Allocate an unused ID. |
263 | * @ida: IDA handle. |
264 | * @gfp: Memory allocation flags. |
265 | * |
266 | * Allocate an ID between 0 and %INT_MAX, inclusive. |
267 | * |
268 | * Context: Any context. It is safe to call this function without |
269 | * locking in your code. |
270 | * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, |
271 | * or %-ENOSPC if there are no free IDs. |
272 | */ |
273 | static inline int ida_alloc(struct ida *ida, gfp_t gfp) |
274 | { |
275 | return ida_alloc_range(ida, min: 0, max: ~0, gfp); |
276 | } |
277 | |
278 | /** |
279 | * ida_alloc_min() - Allocate an unused ID. |
280 | * @ida: IDA handle. |
281 | * @min: Lowest ID to allocate. |
282 | * @gfp: Memory allocation flags. |
283 | * |
284 | * Allocate an ID between @min and %INT_MAX, inclusive. |
285 | * |
286 | * Context: Any context. It is safe to call this function without |
287 | * locking in your code. |
288 | * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, |
289 | * or %-ENOSPC if there are no free IDs. |
290 | */ |
291 | static inline int ida_alloc_min(struct ida *ida, unsigned int min, gfp_t gfp) |
292 | { |
293 | return ida_alloc_range(ida, min, max: ~0, gfp); |
294 | } |
295 | |
296 | /** |
297 | * ida_alloc_max() - Allocate an unused ID. |
298 | * @ida: IDA handle. |
299 | * @max: Highest ID to allocate. |
300 | * @gfp: Memory allocation flags. |
301 | * |
302 | * Allocate an ID between 0 and @max, inclusive. |
303 | * |
304 | * Context: Any context. It is safe to call this function without |
305 | * locking in your code. |
306 | * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, |
307 | * or %-ENOSPC if there are no free IDs. |
308 | */ |
309 | static inline int ida_alloc_max(struct ida *ida, unsigned int max, gfp_t gfp) |
310 | { |
311 | return ida_alloc_range(ida, min: 0, max, gfp); |
312 | } |
313 | |
314 | static inline void ida_init(struct ida *ida) |
315 | { |
316 | xa_init_flags(xa: &ida->xa, IDA_INIT_FLAGS); |
317 | } |
318 | |
319 | /* |
320 | * ida_simple_get() and ida_simple_remove() are deprecated. Use |
321 | * ida_alloc() and ida_free() instead respectively. |
322 | */ |
323 | #define ida_simple_get(ida, start, end, gfp) \ |
324 | ida_alloc_range(ida, start, (end) - 1, gfp) |
325 | #define ida_simple_remove(ida, id) ida_free(ida, id) |
326 | |
327 | static inline bool ida_is_empty(const struct ida *ida) |
328 | { |
329 | return xa_empty(xa: &ida->xa); |
330 | } |
331 | #endif /* __IDR_H__ */ |
332 | |