Blame view
lib/idr.c
16.9 KB
0a835c4f0 Reimplement IDR a... |
1 |
#include <linux/bitmap.h> |
460488c58 idr: Remove idr_a... |
2 |
#include <linux/bug.h> |
8bc3bcc93 lib: reduce the u... |
3 |
#include <linux/export.h> |
1da177e4c Linux-2.6.12-rc2 |
4 |
#include <linux/idr.h> |
0a835c4f0 Reimplement IDR a... |
5 |
#include <linux/slab.h> |
88eca0207 ida: simplified f... |
6 |
#include <linux/spinlock.h> |
b94078e69 lib/idr.c: remove... |
7 |
#include <linux/xarray.h> |
1da177e4c Linux-2.6.12-rc2 |
8 |
|
7ad3d4d85 ida: Move ida_bit... |
9 |
DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
1da177e4c Linux-2.6.12-rc2 |
10 |
|
e096f6a76 idr: Add idr_allo... |
11 12 13 14 15 16 17 18 19 20 |
/** * idr_alloc_u32() - Allocate an ID. * @idr: IDR handle. * @ptr: Pointer to be associated with the new ID. * @nextid: Pointer to an ID. * @max: The maximum ID to allocate (inclusive). * @gfp: Memory allocation flags. * * Allocates an unused ID in the range specified by @nextid and @max. * Note that @max is inclusive whereas the @end parameter to idr_alloc() |
460488c58 idr: Remove idr_a... |
21 22 23 |
* is exclusive. The new ID is assigned to @nextid before the pointer * is inserted into the IDR, so if @nextid points into the object pointed * to by @ptr, a concurrent lookup will not find an uninitialised ID. |
e096f6a76 idr: Add idr_allo... |
24 25 26 27 28 29 30 31 32 33 34 35 36 |
* * The caller should provide their own locking to ensure that two * concurrent modifications to the IDR are not possible. Read-only * accesses to the IDR may be done under the RCU read lock or may * exclude simultaneous writers. * * Return: 0 if an ID was allocated, -ENOMEM if memory allocation failed, * or -ENOSPC if no free IDs could be found. If an error occurred, * @nextid is unchanged. */ int idr_alloc_u32(struct idr *idr, void *ptr, u32 *nextid, unsigned long max, gfp_t gfp) { |
0a835c4f0 Reimplement IDR a... |
37 |
struct radix_tree_iter iter; |
388f79fda idr: Add new APIs... |
38 |
void __rcu **slot; |
4b0ad0765 idr: Fix handling... |
39 40 |
unsigned int base = idr->idr_base; unsigned int id = *nextid; |
d5c7409f7 idr: implement id... |
41 |
|
0a835c4f0 Reimplement IDR a... |
42 43 |
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) return -EINVAL; |
460488c58 idr: Remove idr_a... |
44 45 |
if (WARN_ON_ONCE(!(idr->idr_rt.gfp_mask & ROOT_IS_IDR))) idr->idr_rt.gfp_mask |= IDR_RT_MARKER; |
d5c7409f7 idr: implement id... |
46 |
|
6ce711f27 idr: Make 1-based... |
47 48 49 |
id = (id < base) ? 0 : id - base; radix_tree_iter_init(&iter, id); slot = idr_get_free(&idr->idr_rt, &iter, gfp, max - base); |
0a835c4f0 Reimplement IDR a... |
50 51 |
if (IS_ERR(slot)) return PTR_ERR(slot); |
d5c7409f7 idr: implement id... |
52 |
|
6ce711f27 idr: Make 1-based... |
53 |
*nextid = iter.index + base; |
460488c58 idr: Remove idr_a... |
54 |
/* there is a memory barrier inside radix_tree_iter_replace() */ |
0a835c4f0 Reimplement IDR a... |
55 56 |
radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr); radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE); |
388f79fda idr: Add new APIs... |
57 |
|
388f79fda idr: Add new APIs... |
58 |
return 0; |
d5c7409f7 idr: implement id... |
59 |
} |
460488c58 idr: Remove idr_a... |
60 |
EXPORT_SYMBOL_GPL(idr_alloc_u32); |
d5c7409f7 idr: implement id... |
61 |
|
3e6628c4b idr: introduce id... |
62 |
/** |
460488c58 idr: Remove idr_a... |
63 64 65 66 67 68 |
* idr_alloc() - Allocate an ID. * @idr: IDR handle. * @ptr: Pointer to be associated with the new ID. * @start: The minimum ID (inclusive). * @end: The maximum ID (exclusive). * @gfp: Memory allocation flags. |
9bb26bc1f idr: make idr_des... |
69 |
* |
460488c58 idr: Remove idr_a... |
70 71 72 73 74 75 76 77 78 79 80 |
* Allocates an unused ID in the range specified by @start and @end. If * @end is <= 0, it is treated as one larger than %INT_MAX. This allows * callers to use @start + N as @end as long as N is within integer range. * * The caller should provide their own locking to ensure that two * concurrent modifications to the IDR are not possible. Read-only * accesses to the IDR may be done under the RCU read lock or may * exclude simultaneous writers. * * Return: The newly allocated ID, -ENOMEM if memory allocation failed, * or -ENOSPC if no free IDs could be found. |
8d3b35914 [PATCH] inotify/i... |
81 |
*/ |
460488c58 idr: Remove idr_a... |
82 |
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) |
1da177e4c Linux-2.6.12-rc2 |
83 |
{ |
460488c58 idr: Remove idr_a... |
84 85 86 87 88 89 90 91 92 |
u32 id = start; int ret; if (WARN_ON_ONCE(start < 0)) return -EINVAL; ret = idr_alloc_u32(idr, ptr, &id, end > 0 ? end - 1 : INT_MAX, gfp); if (ret) return ret; |
1da177e4c Linux-2.6.12-rc2 |
93 |
|
460488c58 idr: Remove idr_a... |
94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 |
return id; } EXPORT_SYMBOL_GPL(idr_alloc); /** * idr_alloc_cyclic() - Allocate an ID cyclically. * @idr: IDR handle. * @ptr: Pointer to be associated with the new ID. * @start: The minimum ID (inclusive). * @end: The maximum ID (exclusive). * @gfp: Memory allocation flags. * * Allocates an unused ID in the range specified by @nextid and @end. If * @end is <= 0, it is treated as one larger than %INT_MAX. This allows * callers to use @start + N as @end as long as N is within integer range. * The search for an unused ID will start at the last ID allocated and will * wrap around to @start if no free IDs are found before reaching @end. * * The caller should provide their own locking to ensure that two * concurrent modifications to the IDR are not possible. Read-only * accesses to the IDR may be done under the RCU read lock or may * exclude simultaneous writers. * * Return: The newly allocated ID, -ENOMEM if memory allocation failed, * or -ENOSPC if no free IDs could be found. */ int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) { u32 id = idr->idr_next; int err, max = end > 0 ? end - 1 : INT_MAX; |
e8c8d1bc0 idr: remove MAX_I... |
124 |
|
460488c58 idr: Remove idr_a... |
125 126 |
if ((int)id < start) id = start; |
1da177e4c Linux-2.6.12-rc2 |
127 |
|
460488c58 idr: Remove idr_a... |
128 129 130 131 132 133 134 |
err = idr_alloc_u32(idr, ptr, &id, max, gfp); if ((err == -ENOSPC) && (id > start)) { id = start; err = idr_alloc_u32(idr, ptr, &id, max, gfp); } if (err) return err; |
1da177e4c Linux-2.6.12-rc2 |
135 |
|
460488c58 idr: Remove idr_a... |
136 |
idr->idr_next = id + 1; |
0a835c4f0 Reimplement IDR a... |
137 |
return id; |
1da177e4c Linux-2.6.12-rc2 |
138 |
} |
0a835c4f0 Reimplement IDR a... |
139 |
EXPORT_SYMBOL(idr_alloc_cyclic); |
1da177e4c Linux-2.6.12-rc2 |
140 |
|
5806f07cd [PATCH] lib: add ... |
141 |
/** |
6ce711f27 idr: Make 1-based... |
142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 |
* idr_remove() - Remove an ID from the IDR. * @idr: IDR handle. * @id: Pointer ID. * * Removes this ID from the IDR. If the ID was not previously in the IDR, * this function returns %NULL. * * Since this function modifies the IDR, the caller should provide their * own locking to ensure that concurrent modification of the same IDR is * not possible. * * Return: The pointer formerly associated with this ID. */ void *idr_remove(struct idr *idr, unsigned long id) { return radix_tree_delete_item(&idr->idr_rt, id - idr->idr_base, NULL); } EXPORT_SYMBOL_GPL(idr_remove); /** * idr_find() - Return pointer for given ID. * @idr: IDR handle. * @id: Pointer ID. * * Looks up the pointer associated with this ID. A %NULL pointer may * indicate that @id is not allocated or that the %NULL pointer was * associated with this ID. * * This function can be called under rcu_read_lock(), given that the leaf * pointers lifetimes are correctly managed. * * Return: The pointer associated with this ID. */ void *idr_find(const struct idr *idr, unsigned long id) { return radix_tree_lookup(&idr->idr_rt, id - idr->idr_base); } EXPORT_SYMBOL_GPL(idr_find); /** |
7a4575778 idr: Rename idr_f... |
182 183 184 185 |
* idr_for_each() - Iterate through all stored pointers. * @idr: IDR handle. * @fn: Function to be called for each pointer. * @data: Data passed to callback function. |
96d7fa421 lib: add idr_for_... |
186 |
* |
0a835c4f0 Reimplement IDR a... |
187 |
* The callback function will be called for each entry in @idr, passing |
7a4575778 idr: Rename idr_f... |
188 |
* the ID, the entry and @data. |
96d7fa421 lib: add idr_for_... |
189 |
* |
0a835c4f0 Reimplement IDR a... |
190 191 |
* If @fn returns anything other than %0, the iteration stops and that * value is returned from this function. |
96d7fa421 lib: add idr_for_... |
192 |
* |
0a835c4f0 Reimplement IDR a... |
193 194 195 196 |
* idr_for_each() can be called concurrently with idr_alloc() and * idr_remove() if protected by RCU. Newly added entries may not be * seen and deleted entries may be seen, but adding and removing entries * will not cause other entries to be skipped, nor spurious ones to be seen. |
96d7fa421 lib: add idr_for_... |
197 |
*/ |
0a835c4f0 Reimplement IDR a... |
198 199 |
int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data) |
96d7fa421 lib: add idr_for_... |
200 |
{ |
0a835c4f0 Reimplement IDR a... |
201 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
202 |
void __rcu **slot; |
6ce711f27 idr: Make 1-based... |
203 |
int base = idr->idr_base; |
96d7fa421 lib: add idr_for_... |
204 |
|
0a835c4f0 Reimplement IDR a... |
205 |
radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { |
72fd6c7be idr: Warn if old ... |
206 |
int ret; |
4b0ad0765 idr: Fix handling... |
207 |
unsigned long id = iter.index + base; |
72fd6c7be idr: Warn if old ... |
208 |
|
4b0ad0765 idr: Fix handling... |
209 |
if (WARN_ON_ONCE(id > INT_MAX)) |
72fd6c7be idr: Warn if old ... |
210 |
break; |
4b0ad0765 idr: Fix handling... |
211 |
ret = fn(id, rcu_dereference_raw(*slot), data); |
0a835c4f0 Reimplement IDR a... |
212 213 |
if (ret) return ret; |
96d7fa421 lib: add idr_for_... |
214 |
} |
0a835c4f0 Reimplement IDR a... |
215 |
return 0; |
96d7fa421 lib: add idr_for_... |
216 217 218 219 |
} EXPORT_SYMBOL(idr_for_each); /** |
7a4575778 idr: Rename idr_f... |
220 221 222 |
* idr_get_next() - Find next populated entry. * @idr: IDR handle. * @nextid: Pointer to an ID. |
0a835c4f0 Reimplement IDR a... |
223 224 225 226 227 |
* * Returns the next populated entry in the tree with an ID greater than * or equal to the value pointed to by @nextid. On exit, @nextid is updated * to the ID of the found value. To use in a loop, the value pointed to by * nextid must be incremented by the user. |
38460b48d cgroup: CSS ID su... |
228 |
*/ |
0a835c4f0 Reimplement IDR a... |
229 |
void *idr_get_next(struct idr *idr, int *nextid) |
38460b48d cgroup: CSS ID su... |
230 |
{ |
0a835c4f0 Reimplement IDR a... |
231 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
232 |
void __rcu **slot; |
4b0ad0765 idr: Fix handling... |
233 234 |
unsigned long base = idr->idr_base; unsigned long id = *nextid; |
38460b48d cgroup: CSS ID su... |
235 |
|
6ce711f27 idr: Make 1-based... |
236 237 |
id = (id < base) ? 0 : id - base; slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); |
0a835c4f0 Reimplement IDR a... |
238 |
if (!slot) |
38460b48d cgroup: CSS ID su... |
239 |
return NULL; |
6ce711f27 idr: Make 1-based... |
240 |
id = iter.index + base; |
38460b48d cgroup: CSS ID su... |
241 |
|
6ce711f27 idr: Make 1-based... |
242 |
if (WARN_ON_ONCE(id > INT_MAX)) |
72fd6c7be idr: Warn if old ... |
243 |
return NULL; |
6ce711f27 idr: Make 1-based... |
244 |
*nextid = id; |
0a835c4f0 Reimplement IDR a... |
245 |
return rcu_dereference_raw(*slot); |
38460b48d cgroup: CSS ID su... |
246 |
} |
4d1ee80f3 idr: export idr_g... |
247 |
EXPORT_SYMBOL(idr_get_next); |
38460b48d cgroup: CSS ID su... |
248 |
|
7a4575778 idr: Rename idr_f... |
249 250 251 252 253 254 255 256 257 258 259 |
/** * idr_get_next_ul() - Find next populated entry. * @idr: IDR handle. * @nextid: Pointer to an ID. * * Returns the next populated entry in the tree with an ID greater than * or equal to the value pointed to by @nextid. On exit, @nextid is updated * to the ID of the found value. To use in a loop, the value pointed to by * nextid must be incremented by the user. */ void *idr_get_next_ul(struct idr *idr, unsigned long *nextid) |
388f79fda idr: Add new APIs... |
260 261 262 |
{ struct radix_tree_iter iter; void __rcu **slot; |
6ce711f27 idr: Make 1-based... |
263 264 |
unsigned long base = idr->idr_base; unsigned long id = *nextid; |
388f79fda idr: Add new APIs... |
265 |
|
6ce711f27 idr: Make 1-based... |
266 267 |
id = (id < base) ? 0 : id - base; slot = radix_tree_iter_find(&idr->idr_rt, &iter, id); |
388f79fda idr: Add new APIs... |
268 269 |
if (!slot) return NULL; |
6ce711f27 idr: Make 1-based... |
270 |
*nextid = iter.index + base; |
388f79fda idr: Add new APIs... |
271 272 |
return rcu_dereference_raw(*slot); } |
7a4575778 idr: Rename idr_f... |
273 |
EXPORT_SYMBOL(idr_get_next_ul); |
388f79fda idr: Add new APIs... |
274 |
|
38460b48d cgroup: CSS ID su... |
275 |
/** |
460488c58 idr: Remove idr_a... |
276 277 278 279 |
* idr_replace() - replace pointer for given ID. * @idr: IDR handle. * @ptr: New pointer to associate with the ID. * @id: ID to change. |
5806f07cd [PATCH] lib: add ... |
280 |
* |
0a835c4f0 Reimplement IDR a... |
281 282 283 284 |
* Replace the pointer registered with an ID and return the old value. * This function can be called under the RCU read lock concurrently with * idr_alloc() and idr_remove() (as long as the ID being removed is not * the one being replaced!). |
5806f07cd [PATCH] lib: add ... |
285 |
* |
a70e43a59 lib/idr.c: fix co... |
286 |
* Returns: the old value on success. %-ENOENT indicates that @id was not |
234a4624e idr: Delete idr_r... |
287 |
* found. %-EINVAL indicates that @ptr was not valid. |
5806f07cd [PATCH] lib: add ... |
288 |
*/ |
234a4624e idr: Delete idr_r... |
289 |
void *idr_replace(struct idr *idr, void *ptr, unsigned long id) |
388f79fda idr: Add new APIs... |
290 |
{ |
0a835c4f0 Reimplement IDR a... |
291 |
struct radix_tree_node *node; |
7e73eb0b2 idr: Add missing ... |
292 |
void __rcu **slot = NULL; |
0a835c4f0 Reimplement IDR a... |
293 |
void *entry; |
5806f07cd [PATCH] lib: add ... |
294 |
|
0a835c4f0 Reimplement IDR a... |
295 |
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) |
e8c8d1bc0 idr: remove MAX_I... |
296 |
return ERR_PTR(-EINVAL); |
6ce711f27 idr: Make 1-based... |
297 |
id -= idr->idr_base; |
e8c8d1bc0 idr: remove MAX_I... |
298 |
|
0a835c4f0 Reimplement IDR a... |
299 300 |
entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) |
5806f07cd [PATCH] lib: add ... |
301 |
return ERR_PTR(-ENOENT); |
c7df8ad29 mm, truncate: do ... |
302 |
__radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL); |
5806f07cd [PATCH] lib: add ... |
303 |
|
0a835c4f0 Reimplement IDR a... |
304 |
return entry; |
5806f07cd [PATCH] lib: add ... |
305 |
} |
234a4624e idr: Delete idr_r... |
306 |
EXPORT_SYMBOL(idr_replace); |
5806f07cd [PATCH] lib: add ... |
307 |
|
56083ab17 docbook: add idr/... |
308 309 |
/** * DOC: IDA description |
72dba584b ida: implement id... |
310 |
* |
0a835c4f0 Reimplement IDR a... |
311 312 313 314 315 |
* The IDA is an ID allocator which does not provide the ability to * associate an ID with a pointer. As such, it only needs to store one * bit per ID, and so is more space efficient than an IDR. To use an IDA, * define it using DEFINE_IDA() (or embed a &struct ida in a data structure, * then initialise it using ida_init()). To allocate a new ID, call |
5ade60dda ida: Add new API |
316 317 |
* ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). * To free an ID, call ida_free(). |
0a835c4f0 Reimplement IDR a... |
318 |
* |
b03f8e43c ida: Remove old API |
319 320 321 |
* ida_destroy() can be used to dispose of an IDA without needing to * free the individual IDs in it. You can use ida_is_empty() to find * out whether the IDA has any IDs currently allocated. |
0a835c4f0 Reimplement IDR a... |
322 323 324 |
* * IDs are currently limited to the range [0-INT_MAX]. If this is an awkward * limitation, it should be quite straightforward to raise the maximum. |
72dba584b ida: implement id... |
325 |
*/ |
d37cacc5a ida: Use exceptio... |
326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 |
/* * Developer's notes: * * The IDA uses the functionality provided by the IDR & radix tree to store * bitmaps in each entry. The IDR_FREE tag means there is at least one bit * free, unlike the IDR where it means at least one entry is free. * * I considered telling the radix tree that each slot is an order-10 node * and storing the bit numbers in the radix tree, but the radix tree can't * allow a single multiorder entry at index 0, which would significantly * increase memory consumption for the IDA. So instead we divide the index * by the number of bits in the leaf bitmap before doing a radix tree lookup. * * As an optimisation, if there are only a few low bits set in any given * leaf, instead of allocating a 128-byte bitmap, we use the 'exceptional * entry' functionality of the radix tree to store BITS_PER_LONG - 2 bits * directly in the entry. By being really tricksy, we could store * BITS_PER_LONG - 1 bits, but there're diminishing returns after optimising * for 0-3 allocated IDs. * * We allow the radix tree 'exceptional' count to get out of date. Nothing * in the IDA nor the radix tree code checks it. If it becomes important * to maintain an accurate exceptional count, switch the rcu_assign_pointer() * calls to radix_tree_iter_replace() which will correct the exceptional * count. * * The IDA always requires a lock to alloc/free. If we add a 'test_bit' * equivalent, it will still need locking. Going to RCU lookup would require * using RCU to free bitmaps, and that's not trivial without embedding an * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte * bitmap, which is excessive. */ |
460488c58 idr: Remove idr_a... |
358 |
#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS - 1) |
0a835c4f0 Reimplement IDR a... |
359 |
|
1df895190 ida: Change ida_g... |
360 |
static int ida_get_new_above(struct ida *ida, int start) |
72dba584b ida: implement id... |
361 |
{ |
0a835c4f0 Reimplement IDR a... |
362 |
struct radix_tree_root *root = &ida->ida_rt; |
7e73eb0b2 idr: Add missing ... |
363 |
void __rcu **slot; |
0a835c4f0 Reimplement IDR a... |
364 |
struct radix_tree_iter iter; |
72dba584b ida: implement id... |
365 |
struct ida_bitmap *bitmap; |
0a835c4f0 Reimplement IDR a... |
366 |
unsigned long index; |
d37cacc5a ida: Use exceptio... |
367 |
unsigned bit, ebit; |
0a835c4f0 Reimplement IDR a... |
368 369 370 371 |
int new; index = start / IDA_BITMAP_BITS; bit = start % IDA_BITMAP_BITS; |
d37cacc5a ida: Use exceptio... |
372 |
ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; |
0a835c4f0 Reimplement IDR a... |
373 374 375 376 377 378 379 380 381 382 383 384 385 386 |
slot = radix_tree_iter_init(&iter, index); for (;;) { if (slot) slot = radix_tree_next_slot(slot, &iter, RADIX_TREE_ITER_TAGGED); if (!slot) { slot = idr_get_free(root, &iter, GFP_NOWAIT, IDA_MAX); if (IS_ERR(slot)) { if (slot == ERR_PTR(-ENOMEM)) return -EAGAIN; return PTR_ERR(slot); } } |
d37cacc5a ida: Use exceptio... |
387 |
if (iter.index > index) { |
0a835c4f0 Reimplement IDR a... |
388 |
bit = 0; |
d37cacc5a ida: Use exceptio... |
389 390 |
ebit = RADIX_TREE_EXCEPTIONAL_SHIFT; } |
0a835c4f0 Reimplement IDR a... |
391 392 |
new = iter.index * IDA_BITMAP_BITS; bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
393 394 395 396 397 398 |
if (radix_tree_exception(bitmap)) { unsigned long tmp = (unsigned long)bitmap; ebit = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit); if (ebit < BITS_PER_LONG) { tmp |= 1UL << ebit; rcu_assign_pointer(*slot, (void *)tmp); |
1df895190 ida: Change ida_g... |
399 400 |
return new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; |
d37cacc5a ida: Use exceptio... |
401 402 403 404 |
} bitmap = this_cpu_xchg(ida_bitmap, NULL); if (!bitmap) return -EAGAIN; |
d37cacc5a ida: Use exceptio... |
405 406 407 |
bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; rcu_assign_pointer(*slot, bitmap); } |
0a835c4f0 Reimplement IDR a... |
408 409 410 411 412 413 414 415 |
if (bitmap) { bit = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, bit); new += bit; if (new < 0) return -ENOSPC; if (bit == IDA_BITMAP_BITS) continue; |
72dba584b ida: implement id... |
416 |
|
0a835c4f0 Reimplement IDR a... |
417 418 419 420 421 422 423 424 |
__set_bit(bit, bitmap->bitmap); if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) radix_tree_iter_tag_clear(root, &iter, IDR_FREE); } else { new += bit; if (new < 0) return -ENOSPC; |
d37cacc5a ida: Use exceptio... |
425 426 427 428 429 |
if (ebit < BITS_PER_LONG) { bitmap = (void *)((1UL << ebit) | RADIX_TREE_EXCEPTIONAL_ENTRY); radix_tree_iter_replace(root, &iter, slot, bitmap); |
1df895190 ida: Change ida_g... |
430 |
return new; |
d37cacc5a ida: Use exceptio... |
431 |
} |
7ad3d4d85 ida: Move ida_bit... |
432 |
bitmap = this_cpu_xchg(ida_bitmap, NULL); |
0a835c4f0 Reimplement IDR a... |
433 434 |
if (!bitmap) return -EAGAIN; |
0a835c4f0 Reimplement IDR a... |
435 436 437 |
__set_bit(bit, bitmap->bitmap); radix_tree_iter_replace(root, &iter, slot, bitmap); } |
72dba584b ida: implement id... |
438 |
|
1df895190 ida: Change ida_g... |
439 |
return new; |
72dba584b ida: implement id... |
440 |
} |
72dba584b ida: implement id... |
441 |
} |
72dba584b ida: implement id... |
442 |
|
b03f8e43c ida: Remove old API |
443 |
static void ida_remove(struct ida *ida, int id) |
72dba584b ida: implement id... |
444 |
{ |
0a835c4f0 Reimplement IDR a... |
445 446 |
unsigned long index = id / IDA_BITMAP_BITS; unsigned offset = id % IDA_BITMAP_BITS; |
72dba584b ida: implement id... |
447 |
struct ida_bitmap *bitmap; |
d37cacc5a ida: Use exceptio... |
448 |
unsigned long *btmp; |
0a835c4f0 Reimplement IDR a... |
449 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
450 |
void __rcu **slot; |
72dba584b ida: implement id... |
451 |
|
0a835c4f0 Reimplement IDR a... |
452 453 |
slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index); if (!slot) |
8f9f665a7 idr: fix unexpect... |
454 |
goto err; |
0a835c4f0 Reimplement IDR a... |
455 |
bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
456 457 458 459 460 461 462 463 464 |
if (radix_tree_exception(bitmap)) { btmp = (unsigned long *)slot; offset += RADIX_TREE_EXCEPTIONAL_SHIFT; if (offset >= BITS_PER_LONG) goto err; } else { btmp = bitmap->bitmap; } if (!test_bit(offset, btmp)) |
72dba584b ida: implement id... |
465 |
goto err; |
d37cacc5a ida: Use exceptio... |
466 |
__clear_bit(offset, btmp); |
0a835c4f0 Reimplement IDR a... |
467 |
radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); |
d37cacc5a ida: Use exceptio... |
468 469 470 471 472 |
if (radix_tree_exception(bitmap)) { if (rcu_dereference_raw(*slot) == (void *)RADIX_TREE_EXCEPTIONAL_ENTRY) radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) { |
0a835c4f0 Reimplement IDR a... |
473 474 |
kfree(bitmap); radix_tree_iter_delete(&ida->ida_rt, &iter, slot); |
72dba584b ida: implement id... |
475 |
} |
72dba584b ida: implement id... |
476 |
return; |
72dba584b ida: implement id... |
477 |
err: |
b03f8e43c ida: Remove old API |
478 479 |
WARN(1, "ida_free called for id=%d which is not allocated. ", id); |
72dba584b ida: implement id... |
480 |
} |
72dba584b ida: implement id... |
481 482 |
/** |
50d97d507 ida: Lock the IDA... |
483 484 485 486 487 488 489 |
* ida_destroy() - Free all IDs. * @ida: IDA handle. * * Calling this function frees all IDs and releases all resources used * by an IDA. When this call returns, the IDA is empty and can be reused * or freed. If the IDA is already empty, there is no need to call this * function. |
0a835c4f0 Reimplement IDR a... |
490 |
* |
50d97d507 ida: Lock the IDA... |
491 |
* Context: Any context. |
72dba584b ida: implement id... |
492 493 494 |
*/ void ida_destroy(struct ida *ida) { |
50d97d507 ida: Lock the IDA... |
495 |
unsigned long flags; |
0a835c4f0 Reimplement IDR a... |
496 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
497 |
void __rcu **slot; |
0a835c4f0 Reimplement IDR a... |
498 |
|
50d97d507 ida: Lock the IDA... |
499 |
xa_lock_irqsave(&ida->ida_rt, flags); |
0a835c4f0 Reimplement IDR a... |
500 501 |
radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
502 503 |
if (!radix_tree_exception(bitmap)) kfree(bitmap); |
0a835c4f0 Reimplement IDR a... |
504 505 |
radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } |
50d97d507 ida: Lock the IDA... |
506 |
xa_unlock_irqrestore(&ida->ida_rt, flags); |
72dba584b ida: implement id... |
507 508 509 510 |
} EXPORT_SYMBOL(ida_destroy); /** |
5ade60dda ida: Add new API |
511 512 513 514 515 |
* ida_alloc_range() - Allocate an unused ID. * @ida: IDA handle. * @min: Lowest ID to allocate. * @max: Highest ID to allocate. * @gfp: Memory allocation flags. |
88eca0207 ida: simplified f... |
516 |
* |
5ade60dda ida: Add new API |
517 518 |
* Allocate an ID between @min and @max, inclusive. The allocated ID will * not exceed %INT_MAX, even if @max is larger. |
a2ef9471c lib/ida: document... |
519 |
* |
5ade60dda ida: Add new API |
520 521 522 |
* Context: Any context. * Return: The allocated ID, or %-ENOMEM if memory could not be allocated, * or %-ENOSPC if there are no free IDs. |
88eca0207 ida: simplified f... |
523 |
*/ |
5ade60dda ida: Add new API |
524 525 |
int ida_alloc_range(struct ida *ida, unsigned int min, unsigned int max, gfp_t gfp) |
88eca0207 ida: simplified f... |
526 |
{ |
1df895190 ida: Change ida_g... |
527 |
int id = 0; |
46cbc1d39 ida: make ida_sim... |
528 |
unsigned long flags; |
88eca0207 ida: simplified f... |
529 |
|
5ade60dda ida: Add new API |
530 531 |
if ((int)min < 0) return -ENOSPC; |
88eca0207 ida: simplified f... |
532 |
|
5ade60dda ida: Add new API |
533 534 |
if ((int)max < 0) max = INT_MAX; |
88eca0207 ida: simplified f... |
535 536 |
again: |
b94078e69 lib/idr.c: remove... |
537 |
xa_lock_irqsave(&ida->ida_rt, flags); |
1df895190 ida: Change ida_g... |
538 539 540 541 |
id = ida_get_new_above(ida, min); if (id > (int)max) { ida_remove(ida, id); id = -ENOSPC; |
88eca0207 ida: simplified f... |
542 |
} |
b94078e69 lib/idr.c: remove... |
543 |
xa_unlock_irqrestore(&ida->ida_rt, flags); |
88eca0207 ida: simplified f... |
544 |
|
1df895190 ida: Change ida_g... |
545 |
if (unlikely(id == -EAGAIN)) { |
5ade60dda ida: Add new API |
546 547 |
if (!ida_pre_get(ida, gfp)) return -ENOMEM; |
88eca0207 ida: simplified f... |
548 |
goto again; |
5ade60dda ida: Add new API |
549 |
} |
88eca0207 ida: simplified f... |
550 |
|
1df895190 ida: Change ida_g... |
551 |
return id; |
88eca0207 ida: simplified f... |
552 |
} |
5ade60dda ida: Add new API |
553 |
EXPORT_SYMBOL(ida_alloc_range); |
88eca0207 ida: simplified f... |
554 555 |
/** |
5ade60dda ida: Add new API |
556 557 558 |
* ida_free() - Release an allocated ID. * @ida: IDA handle. * @id: Previously allocated ID. |
a2ef9471c lib/ida: document... |
559 |
* |
5ade60dda ida: Add new API |
560 |
* Context: Any context. |
88eca0207 ida: simplified f... |
561 |
*/ |
5ade60dda ida: Add new API |
562 |
void ida_free(struct ida *ida, unsigned int id) |
88eca0207 ida: simplified f... |
563 |
{ |
46cbc1d39 ida: make ida_sim... |
564 |
unsigned long flags; |
88eca0207 ida: simplified f... |
565 |
BUG_ON((int)id < 0); |
b94078e69 lib/idr.c: remove... |
566 |
xa_lock_irqsave(&ida->ida_rt, flags); |
88eca0207 ida: simplified f... |
567 |
ida_remove(ida, id); |
b94078e69 lib/idr.c: remove... |
568 |
xa_unlock_irqrestore(&ida->ida_rt, flags); |
88eca0207 ida: simplified f... |
569 |
} |
5ade60dda ida: Add new API |
570 |
EXPORT_SYMBOL(ida_free); |