]>
Commit | Line | Data |
---|---|---|
1 | #include <linux/bitmap.h> | |
2 | #include <linux/export.h> | |
3 | #include <linux/idr.h> | |
4 | #include <linux/slab.h> | |
5 | #include <linux/spinlock.h> | |
6 | ||
7 | DEFINE_PER_CPU(struct ida_bitmap *, ida_bitmap); | |
8 | static DEFINE_SPINLOCK(simple_ida_lock); | |
9 | ||
10 | int idr_alloc_cmn(struct idr *idr, void *ptr, unsigned long *index, | |
11 | unsigned long start, unsigned long end, gfp_t gfp, | |
12 | bool ext) | |
13 | { | |
14 | struct radix_tree_iter iter; | |
15 | void __rcu **slot; | |
16 | ||
17 | if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) | |
18 | return -EINVAL; | |
19 | ||
20 | radix_tree_iter_init(&iter, start); | |
21 | if (ext) | |
22 | slot = idr_get_free_ext(&idr->idr_rt, &iter, gfp, end); | |
23 | else | |
24 | slot = idr_get_free(&idr->idr_rt, &iter, gfp, end); | |
25 | if (IS_ERR(slot)) | |
26 | return PTR_ERR(slot); | |
27 | ||
28 | radix_tree_iter_replace(&idr->idr_rt, &iter, slot, ptr); | |
29 | radix_tree_iter_tag_clear(&idr->idr_rt, &iter, IDR_FREE); | |
30 | ||
31 | if (index) | |
32 | *index = iter.index; | |
33 | return 0; | |
34 | } | |
35 | EXPORT_SYMBOL_GPL(idr_alloc_cmn); | |
36 | ||
37 | /** | |
38 | * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion | |
39 | * @idr: idr handle | |
40 | * @ptr: pointer to be associated with the new id | |
41 | * @start: the minimum id (inclusive) | |
42 | * @end: the maximum id (exclusive) | |
43 | * @gfp: memory allocation flags | |
44 | * | |
45 | * Allocates an ID larger than the last ID allocated if one is available. | |
46 | * If not, it will attempt to allocate the smallest ID that is larger or | |
47 | * equal to @start. | |
48 | */ | |
49 | int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp) | |
50 | { | |
51 | int id, curr = idr->idr_next; | |
52 | ||
53 | if (curr < start) | |
54 | curr = start; | |
55 | ||
56 | id = idr_alloc(idr, ptr, curr, end, gfp); | |
57 | if ((id == -ENOSPC) && (curr > start)) | |
58 | id = idr_alloc(idr, ptr, start, curr, gfp); | |
59 | ||
60 | if (id >= 0) | |
61 | idr->idr_next = id + 1U; | |
62 | ||
63 | return id; | |
64 | } | |
65 | EXPORT_SYMBOL(idr_alloc_cyclic); | |
66 | ||
67 | /** | |
68 | * idr_for_each - iterate through all stored pointers | |
69 | * @idr: idr handle | |
70 | * @fn: function to be called for each pointer | |
71 | * @data: data passed to callback function | |
72 | * | |
73 | * The callback function will be called for each entry in @idr, passing | |
74 | * the id, the pointer and the data pointer passed to this function. | |
75 | * | |
76 | * If @fn returns anything other than %0, the iteration stops and that | |
77 | * value is returned from this function. | |
78 | * | |
79 | * idr_for_each() can be called concurrently with idr_alloc() and | |
80 | * idr_remove() if protected by RCU. Newly added entries may not be | |
81 | * seen and deleted entries may be seen, but adding and removing entries | |
82 | * will not cause other entries to be skipped, nor spurious ones to be seen. | |
83 | */ | |
84 | int idr_for_each(const struct idr *idr, | |
85 | int (*fn)(int id, void *p, void *data), void *data) | |
86 | { | |
87 | struct radix_tree_iter iter; | |
88 | void __rcu **slot; | |
89 | ||
90 | radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, 0) { | |
91 | int ret = fn(iter.index, rcu_dereference_raw(*slot), data); | |
92 | if (ret) | |
93 | return ret; | |
94 | } | |
95 | ||
96 | return 0; | |
97 | } | |
98 | EXPORT_SYMBOL(idr_for_each); | |
99 | ||
100 | /** | |
101 | * idr_get_next - Find next populated entry | |
102 | * @idr: idr handle | |
103 | * @nextid: Pointer to lowest possible ID to return | |
104 | * | |
105 | * Returns the next populated entry in the tree with an ID greater than | |
106 | * or equal to the value pointed to by @nextid. On exit, @nextid is updated | |
107 | * to the ID of the found value. To use in a loop, the value pointed to by | |
108 | * nextid must be incremented by the user. | |
109 | */ | |
110 | void *idr_get_next(struct idr *idr, int *nextid) | |
111 | { | |
112 | struct radix_tree_iter iter; | |
113 | void __rcu **slot; | |
114 | void *entry = NULL; | |
115 | ||
116 | radix_tree_for_each_slot(slot, &idr->idr_rt, &iter, *nextid) { | |
117 | entry = rcu_dereference_raw(*slot); | |
118 | if (!entry) | |
119 | continue; | |
120 | if (!radix_tree_deref_retry(entry)) | |
121 | break; | |
122 | if (slot != (void *)&idr->idr_rt.rnode && | |
123 | entry != (void *)RADIX_TREE_INTERNAL_NODE) | |
124 | break; | |
125 | slot = radix_tree_iter_retry(&iter); | |
126 | } | |
127 | if (!slot) | |
128 | return NULL; | |
129 | ||
130 | if (WARN_ON_ONCE(iter.index > INT_MAX)) | |
131 | return NULL; | |
132 | ||
133 | *nextid = iter.index; | |
134 | return entry; | |
135 | } | |
136 | EXPORT_SYMBOL(idr_get_next); | |
137 | ||
138 | void *idr_get_next_ext(struct idr *idr, unsigned long *nextid) | |
139 | { | |
140 | struct radix_tree_iter iter; | |
141 | void __rcu **slot; | |
142 | ||
143 | slot = radix_tree_iter_find(&idr->idr_rt, &iter, *nextid); | |
144 | if (!slot) | |
145 | return NULL; | |
146 | ||
147 | *nextid = iter.index; | |
148 | return rcu_dereference_raw(*slot); | |
149 | } | |
150 | EXPORT_SYMBOL(idr_get_next_ext); | |
151 | ||
152 | /** | |
153 | * idr_replace - replace pointer for given id | |
154 | * @idr: idr handle | |
155 | * @ptr: New pointer to associate with the ID | |
156 | * @id: Lookup key | |
157 | * | |
158 | * Replace the pointer registered with an ID and return the old value. | |
159 | * This function can be called under the RCU read lock concurrently with | |
160 | * idr_alloc() and idr_remove() (as long as the ID being removed is not | |
161 | * the one being replaced!). | |
162 | * | |
163 | * Returns: the old value on success. %-ENOENT indicates that @id was not | |
164 | * found. %-EINVAL indicates that @id or @ptr were not valid. | |
165 | */ | |
166 | void *idr_replace(struct idr *idr, void *ptr, int id) | |
167 | { | |
168 | if (id < 0) | |
169 | return ERR_PTR(-EINVAL); | |
170 | ||
171 | return idr_replace_ext(idr, ptr, id); | |
172 | } | |
173 | EXPORT_SYMBOL(idr_replace); | |
174 | ||
175 | void *idr_replace_ext(struct idr *idr, void *ptr, unsigned long id) | |
176 | { | |
177 | struct radix_tree_node *node; | |
178 | void __rcu **slot = NULL; | |
179 | void *entry; | |
180 | ||
181 | if (WARN_ON_ONCE(radix_tree_is_internal_node(ptr))) | |
182 | return ERR_PTR(-EINVAL); | |
183 | ||
184 | entry = __radix_tree_lookup(&idr->idr_rt, id, &node, &slot); | |
185 | if (!slot || radix_tree_tag_get(&idr->idr_rt, id, IDR_FREE)) | |
186 | return ERR_PTR(-ENOENT); | |
187 | ||
188 | __radix_tree_replace(&idr->idr_rt, node, slot, ptr, NULL); | |
189 | ||
190 | return entry; | |
191 | } | |
192 | EXPORT_SYMBOL(idr_replace_ext); | |
193 | ||
194 | /** | |
195 | * DOC: IDA description | |
196 | * | |
197 | * The IDA is an ID allocator which does not provide the ability to | |
198 | * associate an ID with a pointer. As such, it only needs to store one | |
199 | * bit per ID, and so is more space efficient than an IDR. To use an IDA, | |
200 | * define it using DEFINE_IDA() (or embed a &struct ida in a data structure, | |
201 | * then initialise it using ida_init()). To allocate a new ID, call | |
202 | * ida_simple_get(). To free an ID, call ida_simple_remove(). | |
203 | * | |
204 | * If you have more complex locking requirements, use a loop around | |
205 | * ida_pre_get() and ida_get_new() to allocate a new ID. Then use | |
206 | * ida_remove() to free an ID. You must make sure that ida_get_new() and | |
207 | * ida_remove() cannot be called at the same time as each other for the | |
208 | * same IDA. | |
209 | * | |
210 | * You can also use ida_get_new_above() if you need an ID to be allocated | |
211 | * above a particular number. ida_destroy() can be used to dispose of an | |
212 | * IDA without needing to free the individual IDs in it. You can use | |
213 | * ida_is_empty() to find out whether the IDA has any IDs currently allocated. | |
214 | * | |
215 | * IDs are currently limited to the range [0-INT_MAX]. If this is an awkward | |
216 | * limitation, it should be quite straightforward to raise the maximum. | |
217 | */ | |
218 | ||
219 | /* | |
220 | * Developer's notes: | |
221 | * | |
222 | * The IDA uses the functionality provided by the IDR & radix tree to store | |
223 | * bitmaps in each entry. The IDR_FREE tag means there is at least one bit | |
224 | * free, unlike the IDR where it means at least one entry is free. | |
225 | * | |
226 | * I considered telling the radix tree that each slot is an order-10 node | |
227 | * and storing the bit numbers in the radix tree, but the radix tree can't | |
228 | * allow a single multiorder entry at index 0, which would significantly | |
229 | * increase memory consumption for the IDA. So instead we divide the index | |
230 | * by the number of bits in the leaf bitmap before doing a radix tree lookup. | |
231 | * | |
232 | * As an optimisation, if there are only a few low bits set in any given | |
233 | * leaf, instead of allocating a 128-byte bitmap, we use the 'exceptional | |
234 | * entry' functionality of the radix tree to store BITS_PER_LONG - 2 bits | |
235 | * directly in the entry. By being really tricksy, we could store | |
236 | * BITS_PER_LONG - 1 bits, but there're diminishing returns after optimising | |
237 | * for 0-3 allocated IDs. | |
238 | * | |
239 | * We allow the radix tree 'exceptional' count to get out of date. Nothing | |
240 | * in the IDA nor the radix tree code checks it. If it becomes important | |
241 | * to maintain an accurate exceptional count, switch the rcu_assign_pointer() | |
242 | * calls to radix_tree_iter_replace() which will correct the exceptional | |
243 | * count. | |
244 | * | |
245 | * The IDA always requires a lock to alloc/free. If we add a 'test_bit' | |
246 | * equivalent, it will still need locking. Going to RCU lookup would require | |
247 | * using RCU to free bitmaps, and that's not trivial without embedding an | |
248 | * RCU head in the bitmap, which adds a 2-pointer overhead to each 128-byte | |
249 | * bitmap, which is excessive. | |
250 | */ | |
251 | ||
252 | #define IDA_MAX (0x80000000U / IDA_BITMAP_BITS) | |
253 | ||
254 | /** | |
255 | * ida_get_new_above - allocate new ID above or equal to a start id | |
256 | * @ida: ida handle | |
257 | * @start: id to start search at | |
258 | * @id: pointer to the allocated handle | |
259 | * | |
260 | * Allocate new ID above or equal to @start. It should be called | |
261 | * with any required locks to ensure that concurrent calls to | |
262 | * ida_get_new_above() / ida_get_new() / ida_remove() are not allowed. | |
263 | * Consider using ida_simple_get() if you do not have complex locking | |
264 | * requirements. | |
265 | * | |
266 | * If memory is required, it will return %-EAGAIN, you should unlock | |
267 | * and go back to the ida_pre_get() call. If the ida is full, it will | |
268 | * return %-ENOSPC. On success, it will return 0. | |
269 | * | |
270 | * @id returns a value in the range @start ... %0x7fffffff. | |
271 | */ | |
272 | int ida_get_new_above(struct ida *ida, int start, int *id) | |
273 | { | |
274 | struct radix_tree_root *root = &ida->ida_rt; | |
275 | void __rcu **slot; | |
276 | struct radix_tree_iter iter; | |
277 | struct ida_bitmap *bitmap; | |
278 | unsigned long index; | |
279 | unsigned bit, ebit; | |
280 | int new; | |
281 | ||
282 | index = start / IDA_BITMAP_BITS; | |
283 | bit = start % IDA_BITMAP_BITS; | |
284 | ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT; | |
285 | ||
286 | slot = radix_tree_iter_init(&iter, index); | |
287 | for (;;) { | |
288 | if (slot) | |
289 | slot = radix_tree_next_slot(slot, &iter, | |
290 | RADIX_TREE_ITER_TAGGED); | |
291 | if (!slot) { | |
292 | slot = idr_get_free(root, &iter, GFP_NOWAIT, IDA_MAX); | |
293 | if (IS_ERR(slot)) { | |
294 | if (slot == ERR_PTR(-ENOMEM)) | |
295 | return -EAGAIN; | |
296 | return PTR_ERR(slot); | |
297 | } | |
298 | } | |
299 | if (iter.index > index) { | |
300 | bit = 0; | |
301 | ebit = RADIX_TREE_EXCEPTIONAL_SHIFT; | |
302 | } | |
303 | new = iter.index * IDA_BITMAP_BITS; | |
304 | bitmap = rcu_dereference_raw(*slot); | |
305 | if (radix_tree_exception(bitmap)) { | |
306 | unsigned long tmp = (unsigned long)bitmap; | |
307 | ebit = find_next_zero_bit(&tmp, BITS_PER_LONG, ebit); | |
308 | if (ebit < BITS_PER_LONG) { | |
309 | tmp |= 1UL << ebit; | |
310 | rcu_assign_pointer(*slot, (void *)tmp); | |
311 | *id = new + ebit - RADIX_TREE_EXCEPTIONAL_SHIFT; | |
312 | return 0; | |
313 | } | |
314 | bitmap = this_cpu_xchg(ida_bitmap, NULL); | |
315 | if (!bitmap) | |
316 | return -EAGAIN; | |
317 | memset(bitmap, 0, sizeof(*bitmap)); | |
318 | bitmap->bitmap[0] = tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT; | |
319 | rcu_assign_pointer(*slot, bitmap); | |
320 | } | |
321 | ||
322 | if (bitmap) { | |
323 | bit = find_next_zero_bit(bitmap->bitmap, | |
324 | IDA_BITMAP_BITS, bit); | |
325 | new += bit; | |
326 | if (new < 0) | |
327 | return -ENOSPC; | |
328 | if (bit == IDA_BITMAP_BITS) | |
329 | continue; | |
330 | ||
331 | __set_bit(bit, bitmap->bitmap); | |
332 | if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) | |
333 | radix_tree_iter_tag_clear(root, &iter, | |
334 | IDR_FREE); | |
335 | } else { | |
336 | new += bit; | |
337 | if (new < 0) | |
338 | return -ENOSPC; | |
339 | if (ebit < BITS_PER_LONG) { | |
340 | bitmap = (void *)((1UL << ebit) | | |
341 | RADIX_TREE_EXCEPTIONAL_ENTRY); | |
342 | radix_tree_iter_replace(root, &iter, slot, | |
343 | bitmap); | |
344 | *id = new; | |
345 | return 0; | |
346 | } | |
347 | bitmap = this_cpu_xchg(ida_bitmap, NULL); | |
348 | if (!bitmap) | |
349 | return -EAGAIN; | |
350 | memset(bitmap, 0, sizeof(*bitmap)); | |
351 | __set_bit(bit, bitmap->bitmap); | |
352 | radix_tree_iter_replace(root, &iter, slot, bitmap); | |
353 | } | |
354 | ||
355 | *id = new; | |
356 | return 0; | |
357 | } | |
358 | } | |
359 | EXPORT_SYMBOL(ida_get_new_above); | |
360 | ||
361 | /** | |
362 | * ida_remove - Free the given ID | |
363 | * @ida: ida handle | |
364 | * @id: ID to free | |
365 | * | |
366 | * This function should not be called at the same time as ida_get_new_above(). | |
367 | */ | |
368 | void ida_remove(struct ida *ida, int id) | |
369 | { | |
370 | unsigned long index = id / IDA_BITMAP_BITS; | |
371 | unsigned offset = id % IDA_BITMAP_BITS; | |
372 | struct ida_bitmap *bitmap; | |
373 | unsigned long *btmp; | |
374 | struct radix_tree_iter iter; | |
375 | void __rcu **slot; | |
376 | ||
377 | slot = radix_tree_iter_lookup(&ida->ida_rt, &iter, index); | |
378 | if (!slot) | |
379 | goto err; | |
380 | ||
381 | bitmap = rcu_dereference_raw(*slot); | |
382 | if (radix_tree_exception(bitmap)) { | |
383 | btmp = (unsigned long *)slot; | |
384 | offset += RADIX_TREE_EXCEPTIONAL_SHIFT; | |
385 | if (offset >= BITS_PER_LONG) | |
386 | goto err; | |
387 | } else { | |
388 | btmp = bitmap->bitmap; | |
389 | } | |
390 | if (!test_bit(offset, btmp)) | |
391 | goto err; | |
392 | ||
393 | __clear_bit(offset, btmp); | |
394 | radix_tree_iter_tag_set(&ida->ida_rt, &iter, IDR_FREE); | |
395 | if (radix_tree_exception(bitmap)) { | |
396 | if (rcu_dereference_raw(*slot) == | |
397 | (void *)RADIX_TREE_EXCEPTIONAL_ENTRY) | |
398 | radix_tree_iter_delete(&ida->ida_rt, &iter, slot); | |
399 | } else if (bitmap_empty(btmp, IDA_BITMAP_BITS)) { | |
400 | kfree(bitmap); | |
401 | radix_tree_iter_delete(&ida->ida_rt, &iter, slot); | |
402 | } | |
403 | return; | |
404 | err: | |
405 | WARN(1, "ida_remove called for id=%d which is not allocated.\n", id); | |
406 | } | |
407 | EXPORT_SYMBOL(ida_remove); | |
408 | ||
409 | /** | |
410 | * ida_destroy - Free the contents of an ida | |
411 | * @ida: ida handle | |
412 | * | |
413 | * Calling this function releases all resources associated with an IDA. When | |
414 | * this call returns, the IDA is empty and can be reused or freed. The caller | |
415 | * should not allow ida_remove() or ida_get_new_above() to be called at the | |
416 | * same time. | |
417 | */ | |
418 | void ida_destroy(struct ida *ida) | |
419 | { | |
420 | struct radix_tree_iter iter; | |
421 | void __rcu **slot; | |
422 | ||
423 | radix_tree_for_each_slot(slot, &ida->ida_rt, &iter, 0) { | |
424 | struct ida_bitmap *bitmap = rcu_dereference_raw(*slot); | |
425 | if (!radix_tree_exception(bitmap)) | |
426 | kfree(bitmap); | |
427 | radix_tree_iter_delete(&ida->ida_rt, &iter, slot); | |
428 | } | |
429 | } | |
430 | EXPORT_SYMBOL(ida_destroy); | |
431 | ||
432 | /** | |
433 | * ida_simple_get - get a new id. | |
434 | * @ida: the (initialized) ida. | |
435 | * @start: the minimum id (inclusive, < 0x8000000) | |
436 | * @end: the maximum id (exclusive, < 0x8000000 or 0) | |
437 | * @gfp_mask: memory allocation flags | |
438 | * | |
439 | * Allocates an id in the range start <= id < end, or returns -ENOSPC. | |
440 | * On memory allocation failure, returns -ENOMEM. | |
441 | * | |
442 | * Compared to ida_get_new_above() this function does its own locking, and | |
443 | * should be used unless there are special requirements. | |
444 | * | |
445 | * Use ida_simple_remove() to get rid of an id. | |
446 | */ | |
447 | int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end, | |
448 | gfp_t gfp_mask) | |
449 | { | |
450 | int ret, id; | |
451 | unsigned int max; | |
452 | unsigned long flags; | |
453 | ||
454 | BUG_ON((int)start < 0); | |
455 | BUG_ON((int)end < 0); | |
456 | ||
457 | if (end == 0) | |
458 | max = 0x80000000; | |
459 | else { | |
460 | BUG_ON(end < start); | |
461 | max = end - 1; | |
462 | } | |
463 | ||
464 | again: | |
465 | if (!ida_pre_get(ida, gfp_mask)) | |
466 | return -ENOMEM; | |
467 | ||
468 | spin_lock_irqsave(&simple_ida_lock, flags); | |
469 | ret = ida_get_new_above(ida, start, &id); | |
470 | if (!ret) { | |
471 | if (id > max) { | |
472 | ida_remove(ida, id); | |
473 | ret = -ENOSPC; | |
474 | } else { | |
475 | ret = id; | |
476 | } | |
477 | } | |
478 | spin_unlock_irqrestore(&simple_ida_lock, flags); | |
479 | ||
480 | if (unlikely(ret == -EAGAIN)) | |
481 | goto again; | |
482 | ||
483 | return ret; | |
484 | } | |
485 | EXPORT_SYMBOL(ida_simple_get); | |
486 | ||
487 | /** | |
488 | * ida_simple_remove - remove an allocated id. | |
489 | * @ida: the (initialized) ida. | |
490 | * @id: the id returned by ida_simple_get. | |
491 | * | |
492 | * Use to release an id allocated with ida_simple_get(). | |
493 | * | |
494 | * Compared to ida_remove() this function does its own locking, and should be | |
495 | * used unless there are special requirements. | |
496 | */ | |
497 | void ida_simple_remove(struct ida *ida, unsigned int id) | |
498 | { | |
499 | unsigned long flags; | |
500 | ||
501 | BUG_ON((int)id < 0); | |
502 | spin_lock_irqsave(&simple_ida_lock, flags); | |
503 | ida_remove(ida, id); | |
504 | spin_unlock_irqrestore(&simple_ida_lock, flags); | |
505 | } | |
506 | EXPORT_SYMBOL(ida_simple_remove); |