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