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; | |
21 | unsigned int idr_next; | |
22 | }; | |
1da177e4 | 23 | |
050a6b47 | 24 | /* |
0a835c4f MW |
25 | * The IDR API does not expose the tagging functionality of the radix tree |
26 | * to users. Use tag 0 to track whether a node has free space below it. | |
050a6b47 | 27 | */ |
0a835c4f | 28 | #define IDR_FREE 0 |
1da177e4 | 29 | |
0a835c4f MW |
30 | /* Set the IDR flag and the IDR_FREE tag */ |
31 | #define IDR_RT_MARKER ((__force gfp_t)(3 << __GFP_BITS_SHIFT)) | |
1da177e4 | 32 | |
0a835c4f | 33 | #define IDR_INIT \ |
4106ecaf | 34 | { \ |
0a835c4f | 35 | .idr_rt = RADIX_TREE_INIT(IDR_RT_MARKER) \ |
1da177e4 | 36 | } |
0a835c4f | 37 | #define DEFINE_IDR(name) struct idr name = IDR_INIT |
1da177e4 | 38 | |
44430612 MW |
39 | /** |
40 | * idr_get_cursor - Return the current position of the cyclic allocator | |
41 | * @idr: idr handle | |
42 | * | |
43 | * The value returned is the value that will be next returned from | |
44 | * idr_alloc_cyclic() if it is free (otherwise the search will start from | |
45 | * this position). | |
46 | */ | |
0a835c4f | 47 | static inline unsigned int idr_get_cursor(const struct idr *idr) |
44430612 | 48 | { |
0a835c4f | 49 | return READ_ONCE(idr->idr_next); |
44430612 MW |
50 | } |
51 | ||
52 | /** | |
53 | * idr_set_cursor - Set the current position of the cyclic allocator | |
54 | * @idr: idr handle | |
55 | * @val: new position | |
56 | * | |
57 | * The next call to idr_alloc_cyclic() will return @val if it is free | |
58 | * (otherwise the search will start from this position). | |
59 | */ | |
60 | static inline void idr_set_cursor(struct idr *idr, unsigned int val) | |
61 | { | |
0a835c4f | 62 | WRITE_ONCE(idr->idr_next, val); |
44430612 MW |
63 | } |
64 | ||
f9c46d6e | 65 | /** |
56083ab1 | 66 | * DOC: idr sync |
f9c46d6e ND |
67 | * idr synchronization (stolen from radix-tree.h) |
68 | * | |
69 | * idr_find() is able to be called locklessly, using RCU. The caller must | |
70 | * ensure calls to this function are made within rcu_read_lock() regions. | |
71 | * Other readers (lock-free or otherwise) and modifications may be running | |
72 | * concurrently. | |
73 | * | |
74 | * It is still required that the caller manage the synchronization and | |
75 | * lifetimes of the items. So if RCU lock-free lookups are used, typically | |
76 | * this would mean that the items have their own locks, or are amenable to | |
77 | * lock-free access; and that the items are freed by RCU (or only freed after | |
78 | * having been deleted from the idr tree *and* a synchronize_rcu() grace | |
79 | * period). | |
80 | */ | |
81 | ||
d5c7409f | 82 | void idr_preload(gfp_t gfp_mask); |
388f79fd CM |
83 | |
84 | int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, | |
85 | unsigned long start, unsigned long end, gfp_t gfp, | |
86 | bool ext); | |
87 | ||
88 | /** | |
89 | * idr_alloc - allocate an id | |
90 | * @idr: idr handle | |
91 | * @ptr: pointer to be associated with the new id | |
92 | * @start: the minimum id (inclusive) | |
93 | * @end: the maximum id (exclusive) | |
94 | * @gfp: memory allocation flags | |
95 | * | |
96 | * Allocates an unused ID in the range [start, end). Returns -ENOSPC | |
97 | * if there are no unused IDs in that range. | |
98 | * | |
99 | * Note that @end is treated as max when <= 0. This is to always allow | |
100 | * using @start + N as @end as long as N is inside integer range. | |
101 | * | |
102 | * Simultaneous modifications to the @idr are not allowed and should be | |
103 | * prevented by the user, usually with a lock. idr_alloc() may be called | |
104 | * concurrently with read-only accesses to the @idr, such as idr_find() and | |
105 | * idr_for_each_entry(). | |
106 | */ | |
107 | static inline int idr_alloc(struct idr *idr, void *ptr, | |
108 | int start, int end, gfp_t gfp) | |
109 | { | |
110 | unsigned long id; | |
111 | int ret; | |
112 | ||
113 | if (WARN_ON_ONCE(start < 0)) | |
114 | return -EINVAL; | |
115 | ||
116 | ret = idr_alloc_cmn(idr, ptr, &id, start, end, gfp, false); | |
117 | ||
118 | if (ret) | |
119 | return ret; | |
120 | ||
121 | return id; | |
122 | } | |
123 | ||
124 | static inline int idr_alloc_ext(struct idr *idr, void *ptr, | |
125 | unsigned long *index, | |
126 | unsigned long start, | |
127 | unsigned long end, | |
128 | gfp_t gfp) | |
129 | { | |
130 | return idr_alloc_cmn(idr, ptr, index, start, end, gfp, true); | |
131 | } | |
132 | ||
0a835c4f MW |
133 | int idr_alloc_cyclic(struct idr *, void *entry, int start, int end, gfp_t); |
134 | int idr_for_each(const struct idr *, | |
96d7fa42 | 135 | int (*fn)(int id, void *p, void *data), void *data); |
0a835c4f | 136 | void *idr_get_next(struct idr *, int *nextid); |
388f79fd | 137 | void *idr_get_next_ext(struct idr *idr, unsigned long *nextid); |
0a835c4f | 138 | void *idr_replace(struct idr *, void *, int id); |
388f79fd | 139 | void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id); |
0a835c4f MW |
140 | void idr_destroy(struct idr *); |
141 | ||
388f79fd | 142 | static inline void *idr_remove_ext(struct idr *idr, unsigned long id) |
0a835c4f | 143 | { |
d3e709e6 | 144 | return radix_tree_delete_item(&idr->idr_rt, id, NULL); |
0a835c4f MW |
145 | } |
146 | ||
388f79fd CM |
147 | static inline void *idr_remove(struct idr *idr, int id) |
148 | { | |
149 | return idr_remove_ext(idr, id); | |
150 | } | |
151 | ||
0a835c4f MW |
152 | static inline void idr_init(struct idr *idr) |
153 | { | |
154 | INIT_RADIX_TREE(&idr->idr_rt, IDR_RT_MARKER); | |
155 | idr->idr_next = 0; | |
156 | } | |
157 | ||
158 | static inline bool idr_is_empty(const struct idr *idr) | |
159 | { | |
160 | return radix_tree_empty(&idr->idr_rt) && | |
161 | radix_tree_tagged(&idr->idr_rt, IDR_FREE); | |
162 | } | |
f668ab1a | 163 | |
d5c7409f TH |
164 | /** |
165 | * idr_preload_end - end preload section started with idr_preload() | |
166 | * | |
167 | * Each idr_preload() should be matched with an invocation of this | |
168 | * function. See idr_preload() for details. | |
169 | */ | |
170 | static inline void idr_preload_end(void) | |
171 | { | |
172 | preempt_enable(); | |
173 | } | |
174 | ||
0ffc2a9c TH |
175 | /** |
176 | * idr_find - return pointer for given id | |
5857f70c | 177 | * @idr: idr handle |
0ffc2a9c TH |
178 | * @id: lookup key |
179 | * | |
180 | * Return the pointer given the id it has been registered with. A %NULL | |
181 | * return indicates that @id is not valid or you passed %NULL in | |
182 | * idr_get_new(). | |
183 | * | |
184 | * This function can be called under rcu_read_lock(), given that the leaf | |
185 | * pointers lifetimes are correctly managed. | |
186 | */ | |
388f79fd | 187 | static inline void *idr_find_ext(const struct idr *idr, unsigned long id) |
0ffc2a9c | 188 | { |
0a835c4f | 189 | return radix_tree_lookup(&idr->idr_rt, id); |
0ffc2a9c TH |
190 | } |
191 | ||
388f79fd CM |
192 | static inline void *idr_find(const struct idr *idr, int id) |
193 | { | |
194 | return idr_find_ext(idr, id); | |
195 | } | |
196 | ||
49038ef4 TH |
197 | /** |
198 | * idr_for_each_entry - iterate over an idr's elements of a given type | |
0a835c4f | 199 | * @idr: idr handle |
49038ef4 TH |
200 | * @entry: the type * to use as cursor |
201 | * @id: id entry's key | |
b949be58 GS |
202 | * |
203 | * @entry and @id do not need to be initialized before the loop, and | |
204 | * after normal terminatinon @entry is left with the value NULL. This | |
205 | * is convenient for a "not found" value. | |
49038ef4 | 206 | */ |
0a835c4f MW |
207 | #define idr_for_each_entry(idr, entry, id) \ |
208 | for (id = 0; ((entry) = idr_get_next(idr, &(id))) != NULL; ++id) | |
388f79fd CM |
209 | #define idr_for_each_entry_ext(idr, entry, id) \ |
210 | for (id = 0; ((entry) = idr_get_next_ext(idr, &(id))) != NULL; ++id) | |
49038ef4 | 211 | |
a55bbd37 | 212 | /** |
0a835c4f MW |
213 | * idr_for_each_entry_continue - continue iteration over an idr's elements of a given type |
214 | * @idr: idr handle | |
a55bbd37 AG |
215 | * @entry: the type * to use as cursor |
216 | * @id: id entry's key | |
217 | * | |
218 | * Continue to iterate over list of given type, continuing after | |
219 | * the current position. | |
220 | */ | |
0a835c4f MW |
221 | #define idr_for_each_entry_continue(idr, entry, id) \ |
222 | for ((entry) = idr_get_next((idr), &(id)); \ | |
a55bbd37 | 223 | entry; \ |
0a835c4f | 224 | ++id, (entry) = idr_get_next((idr), &(id))) |
a55bbd37 | 225 | |
72dba584 TH |
226 | /* |
227 | * IDA - IDR based id allocator, use when translation from id to | |
228 | * pointer isn't necessary. | |
229 | */ | |
230 | #define IDA_CHUNK_SIZE 128 /* 128 bytes per chunk */ | |
0a835c4f | 231 | #define IDA_BITMAP_LONGS (IDA_CHUNK_SIZE / sizeof(long)) |
ed9f524a | 232 | #define IDA_BITMAP_BITS (IDA_BITMAP_LONGS * sizeof(long) * 8) |
72dba584 TH |
233 | |
234 | struct ida_bitmap { | |
72dba584 TH |
235 | unsigned long bitmap[IDA_BITMAP_LONGS]; |
236 | }; | |
237 | ||
7ad3d4d8 MW |
238 | DECLARE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
239 | ||
72dba584 | 240 | struct ida { |
0a835c4f | 241 | struct radix_tree_root ida_rt; |
72dba584 TH |
242 | }; |
243 | ||
0a835c4f MW |
244 | #define IDA_INIT { \ |
245 | .ida_rt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ | |
246 | } | |
247 | #define DEFINE_IDA(name) struct ida name = IDA_INIT | |
72dba584 TH |
248 | |
249 | int ida_pre_get(struct ida *ida, gfp_t gfp_mask); | |
250 | int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); | |
72dba584 TH |
251 | void ida_remove(struct ida *ida, int id); |
252 | void ida_destroy(struct ida *ida); | |
72dba584 | 253 | |
88eca020 RR |
254 | int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, |
255 | gfp_t gfp_mask); | |
256 | void ida_simple_remove(struct ida *ida, unsigned int id); | |
257 | ||
0a835c4f MW |
258 | static inline void ida_init(struct ida *ida) |
259 | { | |
260 | INIT_RADIX_TREE(&ida->ida_rt, IDR_RT_MARKER | GFP_NOWAIT); | |
0a835c4f MW |
261 | } |
262 | ||
9749f30f | 263 | /** |
49038ef4 TH |
264 | * ida_get_new - allocate new ID |
265 | * @ida: idr handle | |
266 | * @p_id: pointer to the allocated handle | |
267 | * | |
268 | * Simple wrapper around ida_get_new_above() w/ @starting_id of zero. | |
9749f30f | 269 | */ |
49038ef4 TH |
270 | static inline int ida_get_new(struct ida *ida, int *p_id) |
271 | { | |
272 | return ida_get_new_above(ida, 0, p_id); | |
273 | } | |
274 | ||
0a835c4f | 275 | static inline bool ida_is_empty(const struct ida *ida) |
99c49407 | 276 | { |
0a835c4f | 277 | return radix_tree_empty(&ida->ida_rt); |
99c49407 | 278 | } |
f668ab1a | 279 | #endif /* __IDR_H__ */ |