Blame view
lib/idr.c
14.2 KB
0a835c4f0 Reimplement IDR a... |
1 |
#include <linux/bitmap.h> |
8bc3bcc93 lib: reduce the u... |
2 |
#include <linux/export.h> |
1da177e4c Linux-2.6.12-rc2 |
3 |
#include <linux/idr.h> |
0a835c4f0 Reimplement IDR a... |
4 |
#include <linux/slab.h> |
88eca0207 ida: simplified f... |
5 |
#include <linux/spinlock.h> |
1da177e4c Linux-2.6.12-rc2 |
6 |
|
7ad3d4d85 ida: Move ida_bit... |
7 |
DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap); |
88eca0207 ida: simplified f... |
8 |
static DEFINE_SPINLOCK(simple_ida_lock); |
1da177e4c Linux-2.6.12-rc2 |
9 |
|
388f79fda idr: Add new APIs... |
10 11 12 |
int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, unsigned long start, unsigned long end, gfp_t gfp, bool ext) |
d5c7409f7 idr: implement id... |
13 |
{ |
0a835c4f0 Reimplement IDR a... |
14 |
struct radix_tree_iter iter; |
388f79fda idr: Add new APIs... |
15 |
void __rcu **slot; |
d5c7409f7 idr: implement id... |
16 |
|
0a835c4f0 Reimplement IDR a... |
17 18 |
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) return -EINVAL; |
d5c7409f7 idr: implement id... |
19 |
|
0a835c4f0 Reimplement IDR a... |
20 |
radix_tree_iter_init(&iter, start); |
388f79fda idr: Add new APIs... |
21 22 23 24 |
if (ext) slot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end); else slot = idr_get_free(&idr->idr_rt, &iter, gfp, end); |
0a835c4f0 Reimplement IDR a... |
25 26 |
if (IS_ERR(slot)) return PTR_ERR(slot); |
d5c7409f7 idr: implement id... |
27 |
|
0a835c4f0 Reimplement IDR a... |
28 29 |
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... |
30 31 32 33 |
if (index) *index = iter.index; return 0; |
d5c7409f7 idr: implement id... |
34 |
} |
388f79fda idr: Add new APIs... |
35 |
EXPORT_SYMBOL_GPL(idr_alloc_cmn); |
d5c7409f7 idr: implement id... |
36 |
|
3e6628c4b idr: introduce id... |
37 38 |
/** * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion |
0a835c4f0 Reimplement IDR a... |
39 |
* @idr: idr handle |
3e6628c4b idr: introduce id... |
40 41 |
* @ptr: pointer to be associated with the new id * @start: the minimum id (inclusive) |
0a835c4f0 Reimplement IDR a... |
42 43 |
* @end: the maximum id (exclusive) * @gfp: memory allocation flags |
9bb26bc1f idr: make idr_des... |
44 |
* |
0a835c4f0 Reimplement IDR a... |
45 46 47 |
* Allocates an ID larger than the last ID allocated if one is available. * If not, it will attempt to allocate the smallest ID that is larger or * equal to @start. |
8d3b35914 [PATCH] inotify/i... |
48 |
*/ |
0a835c4f0 Reimplement IDR a... |
49 |
int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) |
1da177e4c Linux-2.6.12-rc2 |
50 |
{ |
0a835c4f0 Reimplement IDR a... |
51 |
int id, curr = idr->idr_next; |
1da177e4c Linux-2.6.12-rc2 |
52 |
|
0a835c4f0 Reimplement IDR a... |
53 54 |
if (curr < start) curr = start; |
e8c8d1bc0 idr: remove MAX_I... |
55 |
|
0a835c4f0 Reimplement IDR a... |
56 57 58 |
id = idr_alloc(idr, ptr, curr, end, gfp); if ((id == -ENOSPC) && (curr > start)) id = idr_alloc(idr, ptr, start, curr, gfp); |
1da177e4c Linux-2.6.12-rc2 |
59 |
|
0a835c4f0 Reimplement IDR a... |
60 61 |
if (id >= 0) idr->idr_next = id + 1U; |
1da177e4c Linux-2.6.12-rc2 |
62 |
|
0a835c4f0 Reimplement IDR a... |
63 |
return id; |
1da177e4c Linux-2.6.12-rc2 |
64 |
} |
0a835c4f0 Reimplement IDR a... |
65 |
EXPORT_SYMBOL(idr_alloc_cyclic); |
1da177e4c Linux-2.6.12-rc2 |
66 |
|
5806f07cd [PATCH] lib: add ... |
67 |
/** |
96d7fa421 lib: add idr_for_... |
68 |
* idr_for_each - iterate through all stored pointers |
0a835c4f0 Reimplement IDR a... |
69 |
* @idr: idr handle |
96d7fa421 lib: add idr_for_... |
70 |
* @fn: function to be called for each pointer |
0a835c4f0 Reimplement IDR a... |
71 |
* @data: data passed to callback function |
96d7fa421 lib: add idr_for_... |
72 |
* |
0a835c4f0 Reimplement IDR a... |
73 74 |
* The callback function will be called for each entry in @idr, passing * the id, the pointer and the data pointer passed to this function. |
96d7fa421 lib: add idr_for_... |
75 |
* |
0a835c4f0 Reimplement IDR a... |
76 77 |
* If @fn returns anything other than %0, the iteration stops and that * value is returned from this function. |
96d7fa421 lib: add idr_for_... |
78 |
* |
0a835c4f0 Reimplement IDR a... |
79 80 81 82 |
* 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_... |
83 |
*/ |
0a835c4f0 Reimplement IDR a... |
84 85 |
int idr_for_each(const struct idr *idr, int (*fn)(int id, void *p, void *data), void *data) |
96d7fa421 lib: add idr_for_... |
86 |
{ |
0a835c4f0 Reimplement IDR a... |
87 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
88 |
void __rcu **slot; |
96d7fa421 lib: add idr_for_... |
89 |
|
0a835c4f0 Reimplement IDR a... |
90 91 92 93 |
radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { int ret = fn(iter.index, rcu_dereference_raw(*slot), data); if (ret) return ret; |
96d7fa421 lib: add idr_for_... |
94 |
} |
0a835c4f0 Reimplement IDR a... |
95 |
return 0; |
96d7fa421 lib: add idr_for_... |
96 97 98 99 |
} EXPORT_SYMBOL(idr_for_each); /** |
0a835c4f0 Reimplement IDR a... |
100 101 102 103 104 105 106 107 |
* idr_get_next - Find next populated entry * @idr: idr handle * @nextid: Pointer to lowest possible ID to return * * 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... |
108 |
*/ |
0a835c4f0 Reimplement IDR a... |
109 |
void *idr_get_next(struct idr *idr, int *nextid) |
38460b48d cgroup: CSS ID su... |
110 |
{ |
0a835c4f0 Reimplement IDR a... |
111 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
112 |
void __rcu **slot; |
38460b48d cgroup: CSS ID su... |
113 |
|
0a835c4f0 Reimplement IDR a... |
114 115 |
slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); if (!slot) |
38460b48d cgroup: CSS ID su... |
116 |
return NULL; |
38460b48d cgroup: CSS ID su... |
117 |
|
0a835c4f0 Reimplement IDR a... |
118 119 |
*nextid = iter.index; return rcu_dereference_raw(*slot); |
38460b48d cgroup: CSS ID su... |
120 |
} |
4d1ee80f3 idr: export idr_g... |
121 |
EXPORT_SYMBOL(idr_get_next); |
38460b48d cgroup: CSS ID su... |
122 |
|
388f79fda idr: Add new APIs... |
123 124 125 126 127 128 129 130 131 132 133 134 135 |
void *idr_get_next_ext(struct idr *idr, unsigned long *nextid) { struct radix_tree_iter iter; void __rcu **slot; slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); if (!slot) return NULL; *nextid = iter.index; return rcu_dereference_raw(*slot); } EXPORT_SYMBOL(idr_get_next_ext); |
38460b48d cgroup: CSS ID su... |
136 |
/** |
5806f07cd [PATCH] lib: add ... |
137 |
* idr_replace - replace pointer for given id |
0a835c4f0 Reimplement IDR a... |
138 139 140 |
* @idr: idr handle * @ptr: New pointer to associate with the ID * @id: Lookup key |
5806f07cd [PATCH] lib: add ... |
141 |
* |
0a835c4f0 Reimplement IDR a... |
142 143 144 145 |
* 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 ... |
146 |
* |
a70e43a59 lib/idr.c: fix co... |
147 148 |
* Returns: the old value on success. %-ENOENT indicates that @id was not * found. %-EINVAL indicates that @id or @ptr were not valid. |
5806f07cd [PATCH] lib: add ... |
149 |
*/ |
0a835c4f0 Reimplement IDR a... |
150 |
void *idr_replace(struct idr *idr, void *ptr, int id) |
5806f07cd [PATCH] lib: add ... |
151 |
{ |
a47f68d6a idr: remove WARN_... |
152 |
if (id < 0) |
388f79fda idr: Add new APIs... |
153 154 155 156 157 158 159 160 |
return ERR_PTR(-EINVAL); return idr_replace_ext(idr, ptr, id); } EXPORT_SYMBOL(idr_replace); void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id) { |
0a835c4f0 Reimplement IDR a... |
161 |
struct radix_tree_node *node; |
7e73eb0b2 idr: Add missing ... |
162 |
void __rcu **slot = NULL; |
0a835c4f0 Reimplement IDR a... |
163 |
void *entry; |
5806f07cd [PATCH] lib: add ... |
164 |
|
0a835c4f0 Reimplement IDR a... |
165 |
if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) |
e8c8d1bc0 idr: remove MAX_I... |
166 |
return ERR_PTR(-EINVAL); |
0a835c4f0 Reimplement IDR a... |
167 168 |
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 ... |
169 |
return ERR_PTR(-ENOENT); |
0a835c4f0 Reimplement IDR a... |
170 |
__radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL, NULL); |
5806f07cd [PATCH] lib: add ... |
171 |
|
0a835c4f0 Reimplement IDR a... |
172 |
return entry; |
5806f07cd [PATCH] lib: add ... |
173 |
} |
388f79fda idr: Add new APIs... |
174 |
EXPORT_SYMBOL(idr_replace_ext); |
5806f07cd [PATCH] lib: add ... |
175 |
|
56083ab17 docbook: add idr/... |
176 177 |
/** * DOC: IDA description |
72dba584b ida: implement id... |
178 |
* |
0a835c4f0 Reimplement IDR a... |
179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 |
* 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 * ida_simple_get(). To free an ID, call ida_simple_remove(). * * If you have more complex locking requirements, use a loop around * ida_pre_get() and ida_get_new() to allocate a new ID. Then use * ida_remove() to free an ID. You must make sure that ida_get_new() and * ida_remove() cannot be called at the same time as each other for the * same IDA. * * You can also use ida_get_new_above() if you need an ID to be allocated * above a particular number. 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. * * 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... |
199 |
*/ |
d37cacc5a ida: Use exceptio... |
200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 |
/* * 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. */ |
0a835c4f0 Reimplement IDR a... |
232 |
#define IDA_MAX (0x80000000U / IDA_BITMAP_BITS) |
72dba584b ida: implement id... |
233 234 |
/** * ida_get_new_above - allocate new ID above or equal to a start id |
0a835c4f0 Reimplement IDR a... |
235 236 237 |
* @ida: ida handle * @start: id to start search at * @id: pointer to the allocated handle |
72dba584b ida: implement id... |
238 |
* |
0a835c4f0 Reimplement IDR a... |
239 240 241 242 243 |
* Allocate new ID above or equal to @start. It should be called * with any required locks to ensure that concurrent calls to * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed. * Consider using ida_simple_get() if you do not have complex locking * requirements. |
72dba584b ida: implement id... |
244 |
* |
56083ab17 docbook: add idr/... |
245 |
* If memory is required, it will return %-EAGAIN, you should unlock |
72dba584b ida: implement id... |
246 |
* and go back to the ida_pre_get() call. If the ida is full, it will |
0a835c4f0 Reimplement IDR a... |
247 |
* return %-ENOSPC. On success, it will return 0. |
a2ef9471c lib/ida: document... |
248 |
* |
0a835c4f0 Reimplement IDR a... |
249 |
* @id returns a value in the range @start ... %0x7fffffff. |
72dba584b ida: implement id... |
250 |
*/ |
0a835c4f0 Reimplement IDR a... |
251 |
int ida_get_new_above(struct ida *ida, int start, int *id) |
72dba584b ida: implement id... |
252 |
{ |
0a835c4f0 Reimplement IDR a... |
253 |
struct radix_tree_root *root = &ida->ida_rt; |
7e73eb0b2 idr: Add missing ... |
254 |
void __rcu **slot; |
0a835c4f0 Reimplement IDR a... |
255 |
struct radix_tree_iter iter; |
72dba584b ida: implement id... |
256 |
struct ida_bitmap *bitmap; |
0a835c4f0 Reimplement IDR a... |
257 |
unsigned long index; |
d37cacc5a ida: Use exceptio... |
258 |
unsigned bit, ebit; |
0a835c4f0 Reimplement IDR a... |
259 260 261 262 |
int new; index = start / IDA_BITMAP_BITS; bit = start % IDA_BITMAP_BITS; |
d37cacc5a ida: Use exceptio... |
263 |
ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; |
0a835c4f0 Reimplement IDR a... |
264 265 266 267 268 269 270 271 272 273 274 275 276 277 |
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... |
278 |
if (iter.index > index) { |
0a835c4f0 Reimplement IDR a... |
279 |
bit = 0; |
d37cacc5a ida: Use exceptio... |
280 281 |
ebit = RADIX_TREE_EXCEPTIONAL_SHIFT; } |
0a835c4f0 Reimplement IDR a... |
282 283 |
new = iter.index * IDA_BITMAP_BITS; bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 |
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); *id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; return 0; } bitmap = this_cpu_xchg(ida_bitmap, NULL); if (!bitmap) return -EAGAIN; memset(bitmap, 0, sizeof(*bitmap)); bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; rcu_assign_pointer(*slot, bitmap); } |
0a835c4f0 Reimplement IDR a... |
300 301 302 303 304 305 306 307 |
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... |
308 |
|
0a835c4f0 Reimplement IDR a... |
309 310 311 312 313 314 315 316 |
__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... |
317 318 319 320 321 322 323 324 |
if (ebit < BITS_PER_LONG) { bitmap = (void *)((1UL << ebit) | RADIX_TREE_EXCEPTIONAL_ENTRY); radix_tree_iter_replace(root, &iter, slot, bitmap); *id = new; return 0; } |
7ad3d4d85 ida: Move ida_bit... |
325 |
bitmap = this_cpu_xchg(ida_bitmap, NULL); |
0a835c4f0 Reimplement IDR a... |
326 327 |
if (!bitmap) return -EAGAIN; |
0a835c4f0 Reimplement IDR a... |
328 329 330 331 |
memset(bitmap, 0, sizeof(*bitmap)); __set_bit(bit, bitmap->bitmap); radix_tree_iter_replace(root, &iter, slot, bitmap); } |
72dba584b ida: implement id... |
332 |
|
0a835c4f0 Reimplement IDR a... |
333 334 |
*id = new; return 0; |
72dba584b ida: implement id... |
335 |
} |
72dba584b ida: implement id... |
336 337 338 339 |
} EXPORT_SYMBOL(ida_get_new_above); /** |
0a835c4f0 Reimplement IDR a... |
340 341 342 343 344 |
* ida_remove - Free the given ID * @ida: ida handle * @id: ID to free * * This function should not be called at the same time as ida_get_new_above(). |
72dba584b ida: implement id... |
345 346 347 |
*/ void ida_remove(struct ida *ida, int id) { |
0a835c4f0 Reimplement IDR a... |
348 349 |
unsigned long index = id / IDA_BITMAP_BITS; unsigned offset = id % IDA_BITMAP_BITS; |
72dba584b ida: implement id... |
350 |
struct ida_bitmap *bitmap; |
d37cacc5a ida: Use exceptio... |
351 |
unsigned long *btmp; |
0a835c4f0 Reimplement IDR a... |
352 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
353 |
void __rcu **slot; |
72dba584b ida: implement id... |
354 |
|
0a835c4f0 Reimplement IDR a... |
355 356 |
slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index); if (!slot) |
8f9f665a7 idr: fix unexpect... |
357 |
goto err; |
0a835c4f0 Reimplement IDR a... |
358 |
bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
359 360 361 362 363 364 365 366 367 |
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... |
368 |
goto err; |
d37cacc5a ida: Use exceptio... |
369 |
__clear_bit(offset, btmp); |
0a835c4f0 Reimplement IDR a... |
370 |
radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); |
d37cacc5a ida: Use exceptio... |
371 372 373 374 375 |
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... |
376 377 |
kfree(bitmap); radix_tree_iter_delete(&ida->ida_rt, &iter, slot); |
72dba584b ida: implement id... |
378 |
} |
72dba584b ida: implement id... |
379 |
return; |
72dba584b ida: implement id... |
380 |
err: |
dd04b452f idr: print a stac... |
381 382 |
WARN(1, "ida_remove called for id=%d which is not allocated. ", id); |
72dba584b ida: implement id... |
383 384 385 386 |
} EXPORT_SYMBOL(ida_remove); /** |
0a835c4f0 Reimplement IDR a... |
387 388 389 390 391 392 393 |
* ida_destroy - Free the contents of an ida * @ida: ida handle * * Calling this function releases all resources associated with an IDA. When * this call returns, the IDA is empty and can be reused or freed. The caller * should not allow ida_remove() or ida_get_new_above() to be called at the * same time. |
72dba584b ida: implement id... |
394 395 396 |
*/ void ida_destroy(struct ida *ida) { |
0a835c4f0 Reimplement IDR a... |
397 |
struct radix_tree_iter iter; |
7e73eb0b2 idr: Add missing ... |
398 |
void __rcu **slot; |
0a835c4f0 Reimplement IDR a... |
399 400 401 |
radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); |
d37cacc5a ida: Use exceptio... |
402 403 |
if (!radix_tree_exception(bitmap)) kfree(bitmap); |
0a835c4f0 Reimplement IDR a... |
404 405 |
radix_tree_iter_delete(&ida->ida_rt, &iter, slot); } |
72dba584b ida: implement id... |
406 407 408 409 |
} EXPORT_SYMBOL(ida_destroy); /** |
88eca0207 ida: simplified f... |
410 411 412 413 414 415 416 417 418 |
* ida_simple_get - get a new id. * @ida: the (initialized) ida. * @start: the minimum id (inclusive, < 0x8000000) * @end: the maximum id (exclusive, < 0x8000000 or 0) * @gfp_mask: memory allocation flags * * Allocates an id in the range start <= id < end, or returns -ENOSPC. * On memory allocation failure, returns -ENOMEM. * |
a2ef9471c lib/ida: document... |
419 420 421 |
* Compared to ida_get_new_above() this function does its own locking, and * should be used unless there are special requirements. * |
88eca0207 ida: simplified f... |
422 423 424 425 426 427 428 |
* Use ida_simple_remove() to get rid of an id. */ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, gfp_t gfp_mask) { int ret, id; unsigned int max; |
46cbc1d39 ida: make ida_sim... |
429 |
unsigned long flags; |
88eca0207 ida: simplified f... |
430 431 432 433 434 435 436 437 438 439 440 441 442 443 |
BUG_ON((int)start < 0); BUG_ON((int)end < 0); if (end == 0) max = 0x80000000; else { BUG_ON(end < start); max = end - 1; } again: if (!ida_pre_get(ida, gfp_mask)) return -ENOMEM; |
46cbc1d39 ida: make ida_sim... |
444 |
spin_lock_irqsave(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
445 446 447 448 449 450 451 452 453 |
ret = ida_get_new_above(ida, start, &id); if (!ret) { if (id > max) { ida_remove(ida, id); ret = -ENOSPC; } else { ret = id; } } |
46cbc1d39 ida: make ida_sim... |
454 |
spin_unlock_irqrestore(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
455 456 457 458 459 460 461 462 463 464 465 466 |
if (unlikely(ret == -EAGAIN)) goto again; return ret; } EXPORT_SYMBOL(ida_simple_get); /** * ida_simple_remove - remove an allocated id. * @ida: the (initialized) ida. * @id: the id returned by ida_simple_get. |
a2ef9471c lib/ida: document... |
467 468 469 470 471 |
* * Use to release an id allocated with ida_simple_get(). * * Compared to ida_remove() this function does its own locking, and should be * used unless there are special requirements. |
88eca0207 ida: simplified f... |
472 473 474 |
*/ void ida_simple_remove(struct ida *ida, unsigned int id) { |
46cbc1d39 ida: make ida_sim... |
475 |
unsigned long flags; |
88eca0207 ida: simplified f... |
476 |
BUG_ON((int)id < 0); |
46cbc1d39 ida: make ida_sim... |
477 |
spin_lock_irqsave(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
478 |
ida_remove(ida, id); |
46cbc1d39 ida: make ida_sim... |
479 |
spin_unlock_irqrestore(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
480 481 |
} EXPORT_SYMBOL(ida_simple_remove); |