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> | |
7ad3d4d8 | 17 | #include <linux/percpu.h> |
0a835c4f MW |
18 | |
19 | struct idr { | |
20 | struct radix_tree_root idr_rt; | |
6ce711f2 | 21 | unsigned int idr_base; |
0a835c4f MW |
22 | unsigned int idr_next; |
23 | }; | |
1da177e4 | 24 | |
050a6b47 | 25 | /* |
0a835c4f MW |
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. | |
050a6b47 | 28 | */ |
0a835c4f | 29 | #define IDR_FREE 0 |
1da177e4 | 30 | |
0a835c4f | 31 | /* Set the IDR flag and the IDR_FREE tag */ |
fa290cda MW |
32 | #define IDR_RT_MARKER (ROOT_IS_IDR | (__force gfp_t) \ |
33 | (1 << (ROOT_TAG_SHIFT + IDR_FREE))) | |
1da177e4 | 34 | |
f6bb2a2c MW |
35 | #define IDR_INIT_BASE(name, base) { \ |
36 | .idr_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER), \ | |
6ce711f2 MW |
37 | .idr_base = (base), \ |
38 | .idr_next = 0, \ | |
1da177e4 | 39 | } |
1da177e4 | 40 | |
6ce711f2 MW |
41 | /** |
42 | * IDR_INIT() - Initialise an IDR. | |
f6bb2a2c | 43 | * @name: Name of IDR. |
6ce711f2 MW |
44 | * |
45 | * A freshly-initialised IDR contains no IDs. | |
46 | */ | |
f6bb2a2c | 47 | #define IDR_INIT(name) IDR_INIT_BASE(name, 0) |
6ce711f2 | 48 | |
ac665d94 | 49 | /** |
f6bb2a2c MW |
50 | * DEFINE_IDR() - Define a statically-allocated IDR. |
51 | * @name: Name of IDR. | |
ac665d94 MW |
52 | * |
53 | * An IDR defined using this macro is ready for use with no additional | |
54 | * initialisation required. It contains no IDs. | |
55 | */ | |
f6bb2a2c | 56 | #define DEFINE_IDR(name) struct idr name = IDR_INIT(name) |
ac665d94 | 57 | |
44430612 MW |
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 | */ | |
0a835c4f | 66 | static inline unsigned int idr_get_cursor(const struct idr *idr) |
44430612 | 67 | { |
0a835c4f | 68 | return READ_ONCE(idr->idr_next); |
44430612 MW |
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 | { | |
0a835c4f | 81 | WRITE_ONCE(idr->idr_next, val); |
44430612 MW |
82 | } |
83 | ||
f9c46d6e | 84 | /** |
56083ab1 | 85 | * DOC: idr sync |
f9c46d6e ND |
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 | ||
d5c7409f | 101 | void idr_preload(gfp_t gfp_mask); |
388f79fd | 102 | |
6ce711f2 MW |
103 | int idr_alloc(struct idr *, void *ptr, int start, int end, gfp_t); |
104 | int __must_check idr_alloc_u32(struct idr *, void *ptr, u32 *id, | |
e096f6a7 | 105 | unsigned long max, gfp_t); |
6ce711f2 MW |
106 | int idr_alloc_cyclic(struct idr *, void *ptr, int start, int end, gfp_t); |
107 | void *idr_remove(struct idr *, unsigned long id); | |
108 | void *idr_find(const struct idr *, unsigned long id); | |
0a835c4f | 109 | int idr_for_each(const struct idr *, |
96d7fa42 | 110 | int (*fn)(int id, void *p, void *data), void *data); |
0a835c4f | 111 | void *idr_get_next(struct idr *, int *nextid); |
7a457577 | 112 | void *idr_get_next_ul(struct idr *, unsigned long *nextid); |
234a4624 | 113 | void *idr_replace(struct idr *, void *, unsigned long id); |
0a835c4f MW |
114 | void idr_destroy(struct idr *); |
115 | ||
6ce711f2 MW |
116 | /** |
117 | * idr_init_base() - Initialise an IDR. | |
118 | * @idr: IDR handle. | |
119 | * @base: The base value for the IDR. | |
120 | * | |
121 | * This variation of idr_init() creates an IDR which will allocate IDs | |
122 | * starting at %base. | |
123 | */ | |
124 | static inline void idr_init_base(struct idr *idr, int base) | |
0a835c4f | 125 | { |
6ce711f2 MW |
126 | INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); |
127 | idr->idr_base = base; | |
128 | idr->idr_next = 0; | |
0a835c4f MW |
129 | } |
130 | ||
6ce711f2 MW |
131 | /** |
132 | * idr_init() - Initialise an IDR. | |
133 | * @idr: IDR handle. | |
134 | * | |
135 | * Initialise a dynamically allocated IDR. To initialise a | |
136 | * statically allocated IDR, use DEFINE_IDR(). | |
137 | */ | |
0a835c4f MW |
138 | static inline void idr_init(struct idr *idr) |
139 | { | |
6ce711f2 | 140 | idr_init_base(idr, 0); |
0a835c4f MW |
141 | } |
142 | ||
ac665d94 MW |
143 | /** |
144 | * idr_is_empty() - Are there any IDs allocated? | |
145 | * @idr: IDR handle. | |
146 | * | |
147 | * Return: %true if any IDs have been allocated from this IDR. | |
148 | */ | |
0a835c4f MW |
149 | static inline bool idr_is_empty(const struct idr *idr) |
150 | { | |
151 | return radix_tree_empty(&idr->idr_rt) && | |
152 | radix_tree_tagged(&idr->idr_rt, IDR_FREE); | |
153 | } | |
f668ab1a | 154 | |
d5c7409f TH |
155 | /** |
156 | * idr_preload_end - end preload section started with idr_preload() | |
157 | * | |
158 | * Each idr_preload() should be matched with an invocation of this | |
159 | * function. See idr_preload() for details. | |
160 | */ | |
161 | static inline void idr_preload_end(void) | |
162 | { | |
163 | preempt_enable(); | |
164 | } | |
165 | ||
49038ef4 | 166 | /** |
7a457577 MW |
167 | * idr_for_each_entry() - Iterate over an IDR's elements of a given type. |
168 | * @idr: IDR handle. | |
169 | * @entry: The type * to use as cursor | |
170 | * @id: Entry ID. | |
b949be58 GS |
171 | * |
172 | * @entry and @id do not need to be initialized before the loop, and | |
7a457577 | 173 | * after normal termination @entry is left with the value NULL. This |
b949be58 | 174 | * is convenient for a "not found" value. |
49038ef4 | 175 | */ |
0a835c4f MW |
176 | #define idr_for_each_entry(idr, entry, id) \ |
177 | for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) | |
49038ef4 | 178 | |
a55bbd37 | 179 | /** |
7a457577 MW |
180 | * idr_for_each_entry_ul() - Iterate over an IDR's elements of a given type. |
181 | * @idr: IDR handle. | |
182 | * @entry: The type * to use as cursor. | |
183 | * @id: Entry ID. | |
184 | * | |
185 | * @entry and @id do not need to be initialized before the loop, and | |
186 | * after normal termination @entry is left with the value NULL. This | |
187 | * is convenient for a "not found" value. | |
188 | */ | |
189 | #define idr_for_each_entry_ul(idr, entry, id) \ | |
190 | for (id = 0; ((entry) = idr_get_next_ul(idr, &(id))) != NULL; ++id) | |
191 | ||
192 | /** | |
193 | * idr_for_each_entry_continue() - Continue iteration over an IDR's elements of a given type | |
194 | * @idr: IDR handle. | |
195 | * @entry: The type * to use as a cursor. | |
196 | * @id: Entry ID. | |
a55bbd37 | 197 | * |
7a457577 | 198 | * Continue to iterate over entries, continuing after the current position. |
a55bbd37 | 199 | */ |
0a835c4f MW |
200 | #define idr_for_each_entry_continue(idr, entry, id) \ |
201 | for ((entry) = idr_get_next((idr), &(id)); \ | |
a55bbd37 | 202 | entry; \ |
0a835c4f | 203 | ++id, (entry) = idr_get_next((idr), &(id))) |
a55bbd37 | 204 | |
72dba584 TH |
205 | /* |
206 | * IDA - IDR based id allocator, use when translation from id to | |
207 | * pointer isn't necessary. | |
208 | */ | |
209 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ | |
0a835c4f | 210 | #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
ed9f524a | 211 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
72dba584 TH |
212 | |
213 | struct ida_bitmap { | |
72dba584 TH |
214 | unsigned long bitmap[IDA_BITMAP_LONGS]; |
215 | }; | |
216 | ||
7ad3d4d8 MW |
217 | DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
218 | ||
72dba584 | 219 | struct ida { |
0a835c4f | 220 | struct radix_tree_root ida_rt; |
72dba584 TH |
221 | }; |
222 | ||
f6bb2a2c MW |
223 | #define IDA_INIT(name) { \ |
224 | .ida_rt = RADIX_TREE_INIT(name, IDR_RT_MARKER | GFP_NOWAIT), \ | |
0a835c4f | 225 | } |
f6bb2a2c | 226 | #define DEFINE_IDA(name) struct ida name = IDA_INIT(name) |
72dba584 TH |
227 | |
228 | int ida_pre_get(struct ida *ida, gfp_t gfp_mask); | |
229 | int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); | |
72dba584 TH |
230 | void ida_remove(struct ida *ida, int id); |
231 | void ida_destroy(struct ida *ida); | |
72dba584 | 232 | |
88eca020 RR |
233 | int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, |
234 | gfp_t gfp_mask); | |
235 | void ida_simple_remove(struct ida *ida, unsigned int id); | |
236 | ||
0a835c4f MW |
237 | static inline void ida_init(struct ida *ida) |
238 | { | |
239 | INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); | |
0a835c4f MW |
240 | } |
241 | ||
9749f30f | 242 | /** |
49038ef4 TH |
243 | * ida_get_new - allocate new ID |
244 | * @ida: idr handle | |
245 | * @p_id: pointer to the allocated handle | |
246 | * | |
247 | * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. | |
9749f30f | 248 | */ |
49038ef4 TH |
249 | static inline int ida_get_new(struct ida *ida, int *p_id) |
250 | { | |
251 | return ida_get_new_above(ida, 0, p_id); | |
252 | } | |
253 | ||
0a835c4f | 254 | static inline bool ida_is_empty(const struct ida *ida) |
99c49407 | 255 | { |
0a835c4f | 256 | return radix_tree_empty(&ida->ida_rt); |
99c49407 | 257 | } |
f668ab1a | 258 | #endif /* __IDR_H__ */ |