blob: 00739aaf95a2717536957f9cb08413621417a2f8 [file] [log] [blame]
Linus Torvalds1da177e2005-04-16 15:20:36 -07001/*
2 * 2002-10-18 written by Jim Houston jim.houston@ccur.com
3 * Copyright (C) 2002 by Concurrent Computer Corporation
4 * Distributed under the GNU GPL license version 2.
5 *
6 * Modified by George Anzinger to reuse immediately and to use
7 * find bit instructions. Also removed _irq on spinlocks.
8 *
Nadia Derbey3219b3b2008-07-25 01:48:00 -07009 * Modified by Nadia Derbey to make it RCU safe.
10 *
Jesper Juhle15ae2d2005-10-30 15:02:14 -080011 * Small id to pointer translation service.
Linus Torvalds1da177e2005-04-16 15:20:36 -070012 *
Jesper Juhle15ae2d2005-10-30 15:02:14 -080013 * It uses a radix tree like structure as a sparse array indexed
Linus Torvalds1da177e2005-04-16 15:20:36 -070014 * by the id to obtain the pointer. The bitmap makes allocating
Jesper Juhle15ae2d2005-10-30 15:02:14 -080015 * a new id quick.
Linus Torvalds1da177e2005-04-16 15:20:36 -070016 *
17 * You call it to allocate an id (an int) an associate with that id a
18 * pointer or what ever, we treat it as a (void *). You can pass this
19 * id to a user for him to pass back at a later time. You then pass
20 * that id to this code and it returns your pointer.
21
Jesper Juhle15ae2d2005-10-30 15:02:14 -080022 * You can release ids at any time. When all ids are released, most of
Fengguang Wu125c4c72012-10-04 17:13:15 -070023 * the memory is returned (we keep MAX_IDR_FREE) in a local pool so we
Jesper Juhle15ae2d2005-10-30 15:02:14 -080024 * don't need to go to the memory "store" during an id allocate, just
Linus Torvalds1da177e2005-04-16 15:20:36 -070025 * so you don't need to be too concerned about locking and conflicts
26 * with the slab allocator.
27 */
28
29#ifndef TEST // to test in user space...
30#include <linux/slab.h>
31#include <linux/init.h>
Paul Gortmaker8bc3bcc2011-11-16 21:29:17 -050032#include <linux/export.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070033#endif
Jeff Mahoney5806f072006-06-26 00:27:19 -070034#include <linux/err.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070035#include <linux/string.h>
36#include <linux/idr.h>
Rusty Russell88eca022011-08-03 16:21:06 -070037#include <linux/spinlock.h>
Tejun Heod5c74092013-02-27 17:03:55 -080038#include <linux/percpu.h>
39#include <linux/hardirq.h>
Linus Torvalds1da177e2005-04-16 15:20:36 -070040
Tejun Heoe8c8d1b2013-02-27 17:05:04 -080041#define MAX_IDR_SHIFT (sizeof(int) * 8 - 1)
42#define MAX_IDR_BIT (1U << MAX_IDR_SHIFT)
43
44/* Leave the possibility of an incomplete final layer */
45#define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS)
46
47/* Number of id_layer structs to leave in free list */
48#define MAX_IDR_FREE (MAX_IDR_LEVEL * 2)
49
Christoph Lametere18b8902006-12-06 20:33:20 -080050static struct kmem_cache *idr_layer_cache;
Tejun Heod5c74092013-02-27 17:03:55 -080051static DEFINE_PER_CPU(struct idr_layer *, idr_preload_head);
52static DEFINE_PER_CPU(int, idr_preload_cnt);
Rusty Russell88eca022011-08-03 16:21:06 -070053static DEFINE_SPINLOCK(simple_ida_lock);
Linus Torvalds1da177e2005-04-16 15:20:36 -070054
Tejun Heo326cf0f2013-02-27 17:05:02 -080055/* the maximum ID which can be allocated given idr->layers */
56static int idr_max(int layers)
57{
58 int bits = min_t(int, layers * IDR_BITS, MAX_IDR_SHIFT);
59
60 return (1 << bits) - 1;
61}
62
Tejun Heo54616282013-02-27 17:05:07 -080063/*
64 * Prefix mask for an idr_layer at @layer. For layer 0, the prefix mask is
65 * all bits except for the lower IDR_BITS. For layer 1, 2 * IDR_BITS, and
66 * so on.
67 */
68static int idr_layer_prefix_mask(int layer)
69{
70 return ~idr_max(layer + 1);
71}
72
Nadia Derbey4ae53782008-07-25 01:47:58 -070073static struct idr_layer *get_from_free_list(struct idr *idp)
Linus Torvalds1da177e2005-04-16 15:20:36 -070074{
75 struct idr_layer *p;
Roland Dreierc259cc22006-07-14 00:24:23 -070076 unsigned long flags;
Linus Torvalds1da177e2005-04-16 15:20:36 -070077
Roland Dreierc259cc22006-07-14 00:24:23 -070078 spin_lock_irqsave(&idp->lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -070079 if ((p = idp->id_free)) {
80 idp->id_free = p->ary[0];
81 idp->id_free_cnt--;
82 p->ary[0] = NULL;
83 }
Roland Dreierc259cc22006-07-14 00:24:23 -070084 spin_unlock_irqrestore(&idp->lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -070085 return(p);
86}
87
Tejun Heod5c74092013-02-27 17:03:55 -080088/**
89 * idr_layer_alloc - allocate a new idr_layer
90 * @gfp_mask: allocation mask
91 * @layer_idr: optional idr to allocate from
92 *
93 * If @layer_idr is %NULL, directly allocate one using @gfp_mask or fetch
94 * one from the per-cpu preload buffer. If @layer_idr is not %NULL, fetch
95 * an idr_layer from @idr->id_free.
96 *
97 * @layer_idr is to maintain backward compatibility with the old alloc
98 * interface - idr_pre_get() and idr_get_new*() - and will be removed
99 * together with per-pool preload buffer.
100 */
101static struct idr_layer *idr_layer_alloc(gfp_t gfp_mask, struct idr *layer_idr)
102{
103 struct idr_layer *new;
104
105 /* this is the old path, bypass to get_from_free_list() */
106 if (layer_idr)
107 return get_from_free_list(layer_idr);
108
109 /* try to allocate directly from kmem_cache */
110 new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
111 if (new)
112 return new;
113
114 /*
115 * Try to fetch one from the per-cpu preload buffer if in process
116 * context. See idr_preload() for details.
117 */
118 if (in_interrupt())
119 return NULL;
120
121 preempt_disable();
122 new = __this_cpu_read(idr_preload_head);
123 if (new) {
124 __this_cpu_write(idr_preload_head, new->ary[0]);
125 __this_cpu_dec(idr_preload_cnt);
126 new->ary[0] = NULL;
127 }
128 preempt_enable();
129 return new;
130}
131
Nadia Derbeycf481c22008-07-25 01:48:02 -0700132static void idr_layer_rcu_free(struct rcu_head *head)
133{
134 struct idr_layer *layer;
135
136 layer = container_of(head, struct idr_layer, rcu_head);
137 kmem_cache_free(idr_layer_cache, layer);
138}
139
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800140static inline void free_layer(struct idr *idr, struct idr_layer *p)
Nadia Derbeycf481c22008-07-25 01:48:02 -0700141{
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800142 if (idr->hint && idr->hint == p)
143 RCU_INIT_POINTER(idr->hint, NULL);
Nadia Derbeycf481c22008-07-25 01:48:02 -0700144 call_rcu(&p->rcu_head, idr_layer_rcu_free);
145}
146
Sonny Rao1eec0052006-06-25 05:49:34 -0700147/* only called when idp->lock is held */
Nadia Derbey4ae53782008-07-25 01:47:58 -0700148static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
Sonny Rao1eec0052006-06-25 05:49:34 -0700149{
150 p->ary[0] = idp->id_free;
151 idp->id_free = p;
152 idp->id_free_cnt++;
153}
154
Nadia Derbey4ae53782008-07-25 01:47:58 -0700155static void move_to_free_list(struct idr *idp, struct idr_layer *p)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700156{
Roland Dreierc259cc22006-07-14 00:24:23 -0700157 unsigned long flags;
158
Linus Torvalds1da177e2005-04-16 15:20:36 -0700159 /*
160 * Depends on the return element being zeroed.
161 */
Roland Dreierc259cc22006-07-14 00:24:23 -0700162 spin_lock_irqsave(&idp->lock, flags);
Nadia Derbey4ae53782008-07-25 01:47:58 -0700163 __move_to_free_list(idp, p);
Roland Dreierc259cc22006-07-14 00:24:23 -0700164 spin_unlock_irqrestore(&idp->lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700165}
166
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900167static void idr_mark_full(struct idr_layer **pa, int id)
168{
169 struct idr_layer *p = pa[0];
170 int l = 0;
171
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800172 __set_bit(id & IDR_MASK, p->bitmap);
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900173 /*
174 * If this layer is full mark the bit in the layer above to
175 * show that this part of the radix tree is full. This may
176 * complete the layer above and require walking up the radix
177 * tree.
178 */
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800179 while (bitmap_full(p->bitmap, IDR_SIZE)) {
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900180 if (!(p = pa[++l]))
181 break;
182 id = id >> IDR_BITS;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800183 __set_bit((id & IDR_MASK), p->bitmap);
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900184 }
185}
186
Linus Torvalds1da177e2005-04-16 15:20:36 -0700187/**
Randy Dunlap56083ab2010-10-26 14:19:08 -0700188 * idr_pre_get - reserve resources for idr allocation
Linus Torvalds1da177e2005-04-16 15:20:36 -0700189 * @idp: idr handle
190 * @gfp_mask: memory allocation flags
191 *
Naohiro Aota066a9be2010-10-26 14:23:03 -0700192 * This function should be called prior to calling the idr_get_new* functions.
193 * It preallocates enough memory to satisfy the worst possible allocation. The
194 * caller should pass in GFP_KERNEL if possible. This of course requires that
195 * no spinning locks be held.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700196 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700197 * If the system is REALLY out of memory this function returns %0,
198 * otherwise %1.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700199 */
Al Virofd4f2df2005-10-21 03:18:50 -0400200int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700201{
Fengguang Wu125c4c72012-10-04 17:13:15 -0700202 while (idp->id_free_cnt < MAX_IDR_FREE) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700203 struct idr_layer *new;
Andrew Morton5b019e92009-01-15 13:51:21 -0800204 new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800205 if (new == NULL)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700206 return (0);
Nadia Derbey4ae53782008-07-25 01:47:58 -0700207 move_to_free_list(idp, new);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700208 }
209 return 1;
210}
211EXPORT_SYMBOL(idr_pre_get);
212
Tejun Heo12d1b432013-02-27 17:03:53 -0800213/**
214 * sub_alloc - try to allocate an id without growing the tree depth
215 * @idp: idr handle
216 * @starting_id: id to start search at
217 * @id: pointer to the allocated handle
218 * @pa: idr_layer[MAX_IDR_LEVEL] used as backtrack buffer
Tejun Heod5c74092013-02-27 17:03:55 -0800219 * @gfp_mask: allocation mask for idr_layer_alloc()
220 * @layer_idr: optional idr passed to idr_layer_alloc()
Tejun Heo12d1b432013-02-27 17:03:53 -0800221 *
222 * Allocate an id in range [@starting_id, INT_MAX] from @idp without
223 * growing its depth. Returns
224 *
225 * the allocated id >= 0 if successful,
226 * -EAGAIN if the tree needs to grow for allocation to succeed,
227 * -ENOSPC if the id space is exhausted,
228 * -ENOMEM if more idr_layers need to be allocated.
229 */
Tejun Heod5c74092013-02-27 17:03:55 -0800230static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa,
231 gfp_t gfp_mask, struct idr *layer_idr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700232{
233 int n, m, sh;
234 struct idr_layer *p, *new;
Tejun Heo7aae6dd2007-06-14 03:45:12 +0900235 int l, id, oid;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700236
237 id = *starting_id;
Tejun Heo7aae6dd2007-06-14 03:45:12 +0900238 restart:
Linus Torvalds1da177e2005-04-16 15:20:36 -0700239 p = idp->top;
240 l = idp->layers;
241 pa[l--] = NULL;
242 while (1) {
243 /*
244 * We run around this while until we reach the leaf node...
245 */
246 n = (id >> (IDR_BITS*l)) & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800247 m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700248 if (m == IDR_SIZE) {
249 /* no space available go back to previous layer. */
250 l++;
Tejun Heo7aae6dd2007-06-14 03:45:12 +0900251 oid = id;
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800252 id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
Tejun Heo7aae6dd2007-06-14 03:45:12 +0900253
254 /* if already at the top layer, we need to grow */
Tejun Heod2e72762010-02-22 12:44:19 -0800255 if (id >= 1 << (idp->layers * IDR_BITS)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700256 *starting_id = id;
Tejun Heo12d1b432013-02-27 17:03:53 -0800257 return -EAGAIN;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700258 }
Tejun Heod2e72762010-02-22 12:44:19 -0800259 p = pa[l];
260 BUG_ON(!p);
Tejun Heo7aae6dd2007-06-14 03:45:12 +0900261
262 /* If we need to go up one layer, continue the
263 * loop; otherwise, restart from the top.
264 */
265 sh = IDR_BITS * (l + 1);
266 if (oid >> sh == id >> sh)
267 continue;
268 else
269 goto restart;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700270 }
271 if (m != n) {
272 sh = IDR_BITS*l;
273 id = ((id >> sh) ^ n ^ m) << sh;
274 }
Fengguang Wu125c4c72012-10-04 17:13:15 -0700275 if ((id >= MAX_IDR_BIT) || (id < 0))
Tejun Heo12d1b432013-02-27 17:03:53 -0800276 return -ENOSPC;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700277 if (l == 0)
278 break;
279 /*
280 * Create the layer below if it is missing.
281 */
282 if (!p->ary[m]) {
Tejun Heod5c74092013-02-27 17:03:55 -0800283 new = idr_layer_alloc(gfp_mask, layer_idr);
Nadia Derbey4ae53782008-07-25 01:47:58 -0700284 if (!new)
Tejun Heo12d1b432013-02-27 17:03:53 -0800285 return -ENOMEM;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800286 new->layer = l-1;
Tejun Heo54616282013-02-27 17:05:07 -0800287 new->prefix = id & idr_layer_prefix_mask(new->layer);
Nadia Derbey3219b3b2008-07-25 01:48:00 -0700288 rcu_assign_pointer(p->ary[m], new);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700289 p->count++;
290 }
291 pa[l--] = p;
292 p = p->ary[m];
293 }
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900294
295 pa[l] = p;
296 return id;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700297}
298
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900299static int idr_get_empty_slot(struct idr *idp, int starting_id,
Tejun Heod5c74092013-02-27 17:03:55 -0800300 struct idr_layer **pa, gfp_t gfp_mask,
301 struct idr *layer_idr)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700302{
303 struct idr_layer *p, *new;
304 int layers, v, id;
Roland Dreierc259cc22006-07-14 00:24:23 -0700305 unsigned long flags;
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800306
Linus Torvalds1da177e2005-04-16 15:20:36 -0700307 id = starting_id;
308build_up:
309 p = idp->top;
310 layers = idp->layers;
311 if (unlikely(!p)) {
Tejun Heod5c74092013-02-27 17:03:55 -0800312 if (!(p = idr_layer_alloc(gfp_mask, layer_idr)))
Tejun Heo12d1b432013-02-27 17:03:53 -0800313 return -ENOMEM;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800314 p->layer = 0;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700315 layers = 1;
316 }
317 /*
318 * Add a new layer to the top of the tree if the requested
319 * id is larger than the currently allocated space.
320 */
Tejun Heo326cf0f2013-02-27 17:05:02 -0800321 while (id > idr_max(layers)) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700322 layers++;
Manfred Spraul711a49a2008-12-10 18:17:06 +0100323 if (!p->count) {
324 /* special case: if the tree is currently empty,
325 * then we grow the tree by moving the top node
326 * upwards.
327 */
328 p->layer++;
Tejun Heo54616282013-02-27 17:05:07 -0800329 WARN_ON_ONCE(p->prefix);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700330 continue;
Manfred Spraul711a49a2008-12-10 18:17:06 +0100331 }
Tejun Heod5c74092013-02-27 17:03:55 -0800332 if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {
Linus Torvalds1da177e2005-04-16 15:20:36 -0700333 /*
334 * The allocation failed. If we built part of
335 * the structure tear it down.
336 */
Roland Dreierc259cc22006-07-14 00:24:23 -0700337 spin_lock_irqsave(&idp->lock, flags);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700338 for (new = p; p && p != idp->top; new = p) {
339 p = p->ary[0];
340 new->ary[0] = NULL;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800341 new->count = 0;
342 bitmap_clear(new->bitmap, 0, IDR_SIZE);
Nadia Derbey4ae53782008-07-25 01:47:58 -0700343 __move_to_free_list(idp, new);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700344 }
Roland Dreierc259cc22006-07-14 00:24:23 -0700345 spin_unlock_irqrestore(&idp->lock, flags);
Tejun Heo12d1b432013-02-27 17:03:53 -0800346 return -ENOMEM;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700347 }
348 new->ary[0] = p;
349 new->count = 1;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800350 new->layer = layers-1;
Tejun Heo54616282013-02-27 17:05:07 -0800351 new->prefix = id & idr_layer_prefix_mask(new->layer);
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800352 if (bitmap_full(p->bitmap, IDR_SIZE))
353 __set_bit(0, new->bitmap);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700354 p = new;
355 }
Nadia Derbey3219b3b2008-07-25 01:48:00 -0700356 rcu_assign_pointer(idp->top, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700357 idp->layers = layers;
Tejun Heod5c74092013-02-27 17:03:55 -0800358 v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr);
Tejun Heo12d1b432013-02-27 17:03:53 -0800359 if (v == -EAGAIN)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700360 goto build_up;
361 return(v);
362}
363
Tejun Heo3594eb22013-02-27 17:03:54 -0800364/*
365 * @id and @pa are from a successful allocation from idr_get_empty_slot().
366 * Install the user pointer @ptr and mark the slot full.
367 */
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800368static void idr_fill_slot(struct idr *idr, void *ptr, int id,
369 struct idr_layer **pa)
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900370{
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800371 /* update hint used for lookup, cleared from free_layer() */
372 rcu_assign_pointer(idr->hint, pa[0]);
373
Tejun Heo3594eb22013-02-27 17:03:54 -0800374 rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
375 pa[0]->count++;
376 idr_mark_full(pa, id);
Tejun Heoe33ac8b2007-06-14 03:45:12 +0900377}
378
Linus Torvalds1da177e2005-04-16 15:20:36 -0700379/**
John McCutchan7c657f22005-08-26 14:02:04 -0400380 * idr_get_new_above - allocate new idr entry above or equal to a start id
Linus Torvalds1da177e2005-04-16 15:20:36 -0700381 * @idp: idr handle
Thadeu Lima de Souza Cascardo94e2bd62009-10-16 15:20:49 +0200382 * @ptr: pointer you want associated with the id
Naohiro Aotaea24ea82010-08-31 00:37:03 +0900383 * @starting_id: id to start search at
Linus Torvalds1da177e2005-04-16 15:20:36 -0700384 * @id: pointer to the allocated handle
385 *
386 * This is the allocate id function. It should be called with any
387 * required locks.
388 *
Naohiro Aota066a9be2010-10-26 14:23:03 -0700389 * If allocation from IDR's private freelist fails, idr_get_new_above() will
Randy Dunlap56083ab2010-10-26 14:19:08 -0700390 * return %-EAGAIN. The caller should retry the idr_pre_get() call to refill
Naohiro Aota066a9be2010-10-26 14:23:03 -0700391 * IDR's preallocation and then retry the idr_get_new_above() call.
392 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700393 * If the idr is full idr_get_new_above() will return %-ENOSPC.
Linus Torvalds1da177e2005-04-16 15:20:36 -0700394 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700395 * @id returns a value in the range @starting_id ... %0x7fffffff
Linus Torvalds1da177e2005-04-16 15:20:36 -0700396 */
397int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
398{
Tejun Heo326cf0f2013-02-27 17:05:02 -0800399 struct idr_layer *pa[MAX_IDR_LEVEL + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700400 int rv;
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800401
Tejun Heod5c74092013-02-27 17:03:55 -0800402 rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp);
Nadia Derbey944ca052008-07-25 01:47:59 -0700403 if (rv < 0)
Tejun Heo12d1b432013-02-27 17:03:53 -0800404 return rv == -ENOMEM ? -EAGAIN : rv;
Tejun Heo3594eb22013-02-27 17:03:54 -0800405
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800406 idr_fill_slot(idp, ptr, rv, pa);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700407 *id = rv;
408 return 0;
409}
410EXPORT_SYMBOL(idr_get_new_above);
411
Tejun Heod5c74092013-02-27 17:03:55 -0800412/**
413 * idr_preload - preload for idr_alloc()
414 * @gfp_mask: allocation mask to use for preloading
415 *
416 * Preload per-cpu layer buffer for idr_alloc(). Can only be used from
417 * process context and each idr_preload() invocation should be matched with
418 * idr_preload_end(). Note that preemption is disabled while preloaded.
419 *
420 * The first idr_alloc() in the preloaded section can be treated as if it
421 * were invoked with @gfp_mask used for preloading. This allows using more
422 * permissive allocation masks for idrs protected by spinlocks.
423 *
424 * For example, if idr_alloc() below fails, the failure can be treated as
425 * if idr_alloc() were called with GFP_KERNEL rather than GFP_NOWAIT.
426 *
427 * idr_preload(GFP_KERNEL);
428 * spin_lock(lock);
429 *
430 * id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT);
431 *
432 * spin_unlock(lock);
433 * idr_preload_end();
434 * if (id < 0)
435 * error;
436 */
437void idr_preload(gfp_t gfp_mask)
438{
439 /*
440 * Consuming preload buffer from non-process context breaks preload
441 * allocation guarantee. Disallow usage from those contexts.
442 */
443 WARN_ON_ONCE(in_interrupt());
444 might_sleep_if(gfp_mask & __GFP_WAIT);
445
446 preempt_disable();
447
448 /*
449 * idr_alloc() is likely to succeed w/o full idr_layer buffer and
450 * return value from idr_alloc() needs to be checked for failure
451 * anyway. Silently give up if allocation fails. The caller can
452 * treat failures from idr_alloc() as if idr_alloc() were called
453 * with @gfp_mask which should be enough.
454 */
455 while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) {
456 struct idr_layer *new;
457
458 preempt_enable();
459 new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
460 preempt_disable();
461 if (!new)
462 break;
463
464 /* link the new one to per-cpu preload list */
465 new->ary[0] = __this_cpu_read(idr_preload_head);
466 __this_cpu_write(idr_preload_head, new);
467 __this_cpu_inc(idr_preload_cnt);
468 }
469}
470EXPORT_SYMBOL(idr_preload);
471
472/**
473 * idr_alloc - allocate new idr entry
474 * @idr: the (initialized) idr
475 * @ptr: pointer to be associated with the new id
476 * @start: the minimum id (inclusive)
477 * @end: the maximum id (exclusive, <= 0 for max)
478 * @gfp_mask: memory allocation flags
479 *
480 * Allocate an id in [start, end) and associate it with @ptr. If no ID is
481 * available in the specified range, returns -ENOSPC. On memory allocation
482 * failure, returns -ENOMEM.
483 *
484 * Note that @end is treated as max when <= 0. This is to always allow
485 * using @start + N as @end as long as N is inside integer range.
486 *
487 * The user is responsible for exclusively synchronizing all operations
488 * which may modify @idr. However, read-only accesses such as idr_find()
489 * or iteration can be performed under RCU read lock provided the user
490 * destroys @ptr in RCU-safe way after removal from idr.
491 */
492int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
493{
494 int max = end > 0 ? end - 1 : INT_MAX; /* inclusive upper limit */
Tejun Heo326cf0f2013-02-27 17:05:02 -0800495 struct idr_layer *pa[MAX_IDR_LEVEL + 1];
Tejun Heod5c74092013-02-27 17:03:55 -0800496 int id;
497
498 might_sleep_if(gfp_mask & __GFP_WAIT);
499
500 /* sanity checks */
501 if (WARN_ON_ONCE(start < 0))
502 return -EINVAL;
503 if (unlikely(max < start))
504 return -ENOSPC;
505
506 /* allocate id */
507 id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL);
508 if (unlikely(id < 0))
509 return id;
510 if (unlikely(id > max))
511 return -ENOSPC;
512
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800513 idr_fill_slot(idr, ptr, id, pa);
Tejun Heod5c74092013-02-27 17:03:55 -0800514 return id;
515}
516EXPORT_SYMBOL_GPL(idr_alloc);
517
Linus Torvalds1da177e2005-04-16 15:20:36 -0700518static void idr_remove_warning(int id)
519{
Nadia Derbeyf098ad62008-07-25 01:47:59 -0700520 printk(KERN_WARNING
521 "idr_remove called for id=%d which is not allocated.\n", id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700522 dump_stack();
523}
524
525static void sub_remove(struct idr *idp, int shift, int id)
526{
527 struct idr_layer *p = idp->top;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800528 struct idr_layer **pa[MAX_IDR_LEVEL + 1];
Linus Torvalds1da177e2005-04-16 15:20:36 -0700529 struct idr_layer ***paa = &pa[0];
Nadia Derbeycf481c22008-07-25 01:48:02 -0700530 struct idr_layer *to_free;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700531 int n;
532
533 *paa = NULL;
534 *++paa = &idp->top;
535
536 while ((shift > 0) && p) {
537 n = (id >> shift) & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800538 __clear_bit(n, p->bitmap);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700539 *++paa = &p->ary[n];
540 p = p->ary[n];
541 shift -= IDR_BITS;
542 }
543 n = id & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800544 if (likely(p != NULL && test_bit(n, p->bitmap))) {
545 __clear_bit(n, p->bitmap);
Nadia Derbeycf481c22008-07-25 01:48:02 -0700546 rcu_assign_pointer(p->ary[n], NULL);
547 to_free = NULL;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700548 while(*paa && ! --((**paa)->count)){
Nadia Derbeycf481c22008-07-25 01:48:02 -0700549 if (to_free)
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800550 free_layer(idp, to_free);
Nadia Derbeycf481c22008-07-25 01:48:02 -0700551 to_free = **paa;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700552 **paa-- = NULL;
553 }
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800554 if (!*paa)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700555 idp->layers = 0;
Nadia Derbeycf481c22008-07-25 01:48:02 -0700556 if (to_free)
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800557 free_layer(idp, to_free);
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800558 } else
Linus Torvalds1da177e2005-04-16 15:20:36 -0700559 idr_remove_warning(id);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700560}
561
562/**
Randy Dunlap56083ab2010-10-26 14:19:08 -0700563 * idr_remove - remove the given id and free its slot
Robert P. J. Day72fd4a32007-02-10 01:45:59 -0800564 * @idp: idr handle
565 * @id: unique key
Linus Torvalds1da177e2005-04-16 15:20:36 -0700566 */
567void idr_remove(struct idr *idp, int id)
568{
569 struct idr_layer *p;
Nadia Derbeycf481c22008-07-25 01:48:02 -0700570 struct idr_layer *to_free;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700571
Tejun Heo2e1c9b22013-03-08 12:43:30 -0800572 if (id < 0)
Tejun Heoe8c8d1b2013-02-27 17:05:04 -0800573 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700574
575 sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
Jesper Juhle15ae2d2005-10-30 15:02:14 -0800576 if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
Nadia Derbeycf481c22008-07-25 01:48:02 -0700577 idp->top->ary[0]) {
578 /*
579 * Single child at leftmost slot: we can shrink the tree.
580 * This level is not needed anymore since when layers are
581 * inserted, they are inserted at the top of the existing
582 * tree.
583 */
584 to_free = idp->top;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700585 p = idp->top->ary[0];
Nadia Derbeycf481c22008-07-25 01:48:02 -0700586 rcu_assign_pointer(idp->top, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700587 --idp->layers;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800588 to_free->count = 0;
589 bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800590 free_layer(idp, to_free);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700591 }
Fengguang Wu125c4c72012-10-04 17:13:15 -0700592 while (idp->id_free_cnt >= MAX_IDR_FREE) {
Nadia Derbey4ae53782008-07-25 01:47:58 -0700593 p = get_from_free_list(idp);
Nadia Derbeycf481c22008-07-25 01:48:02 -0700594 /*
595 * Note: we don't call the rcu callback here, since the only
596 * layers that fall into the freelist are those that have been
597 * preallocated.
598 */
Linus Torvalds1da177e2005-04-16 15:20:36 -0700599 kmem_cache_free(idr_layer_cache, p);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700600 }
Nadia Derbeyaf8e2a42008-05-01 04:34:57 -0700601 return;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700602}
603EXPORT_SYMBOL(idr_remove);
604
Tejun Heofe6e24e2013-02-27 17:03:50 -0800605void __idr_remove_all(struct idr *idp)
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700606{
Oleg Nesterov6ace06dc2007-07-31 00:39:19 -0700607 int n, id, max;
Imre Deak2dcb22b2010-05-26 14:43:38 -0700608 int bt_mask;
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700609 struct idr_layer *p;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800610 struct idr_layer *pa[MAX_IDR_LEVEL + 1];
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700611 struct idr_layer **paa = &pa[0];
612
613 n = idp->layers * IDR_BITS;
614 p = idp->top;
Paul E. McKenney1b233362009-03-10 12:55:52 -0700615 rcu_assign_pointer(idp->top, NULL);
Tejun Heo326cf0f2013-02-27 17:05:02 -0800616 max = idr_max(idp->layers);
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700617
618 id = 0;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800619 while (id >= 0 && id <= max) {
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700620 while (n > IDR_BITS && p) {
621 n -= IDR_BITS;
622 *paa++ = p;
623 p = p->ary[(id >> n) & IDR_MASK];
624 }
625
Imre Deak2dcb22b2010-05-26 14:43:38 -0700626 bt_mask = id;
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700627 id += 1 << n;
Imre Deak2dcb22b2010-05-26 14:43:38 -0700628 /* Get the highest bit that the above add changed from 0->1. */
629 while (n < fls(id ^ bt_mask)) {
Nadia Derbeycf481c22008-07-25 01:48:02 -0700630 if (p)
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800631 free_layer(idp, p);
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700632 n += IDR_BITS;
633 p = *--paa;
634 }
635 }
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700636 idp->layers = 0;
637}
Tejun Heofe6e24e2013-02-27 17:03:50 -0800638EXPORT_SYMBOL(__idr_remove_all);
Kristian Hoegsberg23936cc2007-07-15 23:37:24 -0700639
640/**
Andrew Morton8d3b3592005-10-23 12:57:18 -0700641 * idr_destroy - release all cached layers within an idr tree
Naohiro Aotaea24ea82010-08-31 00:37:03 +0900642 * @idp: idr handle
Tejun Heo9bb26bc2013-02-27 17:03:35 -0800643 *
644 * Free all id mappings and all idp_layers. After this function, @idp is
645 * completely unused and can be freed / recycled. The caller is
646 * responsible for ensuring that no one else accesses @idp during or after
647 * idr_destroy().
648 *
649 * A typical clean-up sequence for objects stored in an idr tree will use
650 * idr_for_each() to free all objects, if necessay, then idr_destroy() to
651 * free up the id mappings and cached idr_layers.
Andrew Morton8d3b3592005-10-23 12:57:18 -0700652 */
653void idr_destroy(struct idr *idp)
654{
Tejun Heofe6e24e2013-02-27 17:03:50 -0800655 __idr_remove_all(idp);
Tejun Heo9bb26bc2013-02-27 17:03:35 -0800656
Andrew Morton8d3b3592005-10-23 12:57:18 -0700657 while (idp->id_free_cnt) {
Nadia Derbey4ae53782008-07-25 01:47:58 -0700658 struct idr_layer *p = get_from_free_list(idp);
Andrew Morton8d3b3592005-10-23 12:57:18 -0700659 kmem_cache_free(idr_layer_cache, p);
660 }
661}
662EXPORT_SYMBOL(idr_destroy);
663
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800664void *idr_find_slowpath(struct idr *idp, int id)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700665{
666 int n;
667 struct idr_layer *p;
668
Tejun Heo2e1c9b22013-03-08 12:43:30 -0800669 if (id < 0)
Tejun Heoe8c8d1b2013-02-27 17:05:04 -0800670 return NULL;
671
Paul E. McKenney96be7532010-02-22 17:04:55 -0800672 p = rcu_dereference_raw(idp->top);
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800673 if (!p)
674 return NULL;
675 n = (p->layer+1) * IDR_BITS;
Linus Torvalds1da177e2005-04-16 15:20:36 -0700676
Tejun Heo326cf0f2013-02-27 17:05:02 -0800677 if (id > idr_max(p->layer + 1))
Linus Torvalds1da177e2005-04-16 15:20:36 -0700678 return NULL;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800679 BUG_ON(n == 0);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700680
681 while (n > 0 && p) {
682 n -= IDR_BITS;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800683 BUG_ON(n != p->layer*IDR_BITS);
Paul E. McKenney96be7532010-02-22 17:04:55 -0800684 p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700685 }
686 return((void *)p);
687}
Tejun Heo0ffc2a92013-02-27 17:05:08 -0800688EXPORT_SYMBOL(idr_find_slowpath);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700689
Jeff Mahoney5806f072006-06-26 00:27:19 -0700690/**
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700691 * idr_for_each - iterate through all stored pointers
692 * @idp: idr handle
693 * @fn: function to be called for each pointer
694 * @data: data passed back to callback function
695 *
696 * Iterate over the pointers registered with the given idr. The
697 * callback function will be called for each pointer currently
698 * registered, passing the id, the pointer and the data pointer passed
699 * to this function. It is not safe to modify the idr tree while in
700 * the callback, so functions such as idr_get_new and idr_remove are
701 * not allowed.
702 *
703 * We check the return of @fn each time. If it returns anything other
Randy Dunlap56083ab2010-10-26 14:19:08 -0700704 * than %0, we break out and return that value.
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700705 *
706 * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
707 */
708int idr_for_each(struct idr *idp,
709 int (*fn)(int id, void *p, void *data), void *data)
710{
711 int n, id, max, error = 0;
712 struct idr_layer *p;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800713 struct idr_layer *pa[MAX_IDR_LEVEL + 1];
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700714 struct idr_layer **paa = &pa[0];
715
716 n = idp->layers * IDR_BITS;
Paul E. McKenney96be7532010-02-22 17:04:55 -0800717 p = rcu_dereference_raw(idp->top);
Tejun Heo326cf0f2013-02-27 17:05:02 -0800718 max = idr_max(idp->layers);
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700719
720 id = 0;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800721 while (id >= 0 && id <= max) {
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700722 while (n > 0 && p) {
723 n -= IDR_BITS;
724 *paa++ = p;
Paul E. McKenney96be7532010-02-22 17:04:55 -0800725 p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
Kristian Hoegsberg96d7fa42007-07-15 23:37:24 -0700726 }
727
728 if (p) {
729 error = fn(id, (void *)p, data);
730 if (error)
731 break;
732 }
733
734 id += 1 << n;
735 while (n < fls(id)) {
736 n += IDR_BITS;
737 p = *--paa;
738 }
739 }
740
741 return error;
742}
743EXPORT_SYMBOL(idr_for_each);
744
745/**
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700746 * idr_get_next - lookup next object of id to given id.
747 * @idp: idr handle
Naohiro Aotaea24ea82010-08-31 00:37:03 +0900748 * @nextidp: pointer to lookup key
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700749 *
750 * Returns pointer to registered object with id, which is next number to
Naohiro Aota1458ce12010-08-27 17:43:46 +0900751 * given id. After being looked up, *@nextidp will be updated for the next
752 * iteration.
Hugh Dickins9f7de822012-03-21 16:34:20 -0700753 *
754 * This function can be called under rcu_read_lock(), given that the leaf
755 * pointers lifetimes are correctly managed.
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700756 */
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700757void *idr_get_next(struct idr *idp, int *nextidp)
758{
Tejun Heo326cf0f2013-02-27 17:05:02 -0800759 struct idr_layer *p, *pa[MAX_IDR_LEVEL + 1];
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700760 struct idr_layer **paa = &pa[0];
761 int id = *nextidp;
762 int n, max;
763
764 /* find first ent */
Paul E. McKenney94bfa3b2010-06-07 17:09:45 -0700765 p = rcu_dereference_raw(idp->top);
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700766 if (!p)
767 return NULL;
Hugh Dickins9f7de822012-03-21 16:34:20 -0700768 n = (p->layer + 1) * IDR_BITS;
Tejun Heo326cf0f2013-02-27 17:05:02 -0800769 max = idr_max(p->layer + 1);
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700770
Tejun Heo326cf0f2013-02-27 17:05:02 -0800771 while (id >= 0 && id <= max) {
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700772 while (n > 0 && p) {
773 n -= IDR_BITS;
774 *paa++ = p;
Paul E. McKenney94bfa3b2010-06-07 17:09:45 -0700775 p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700776 }
777
778 if (p) {
779 *nextidp = id;
780 return p;
781 }
782
Tejun Heo6cdae742013-02-27 17:03:34 -0800783 /*
784 * Proceed to the next layer at the current level. Unlike
785 * idr_for_each(), @id isn't guaranteed to be aligned to
786 * layer boundary at this point and adding 1 << n may
787 * incorrectly skip IDs. Make sure we jump to the
788 * beginning of the next layer using round_up().
789 */
790 id = round_up(id + 1, 1 << n);
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700791 while (n < fls(id)) {
792 n += IDR_BITS;
793 p = *--paa;
794 }
795 }
796 return NULL;
797}
Ben Hutchings4d1ee802010-01-29 20:59:17 +0000798EXPORT_SYMBOL(idr_get_next);
KAMEZAWA Hiroyuki38460b42009-04-02 16:57:25 -0700799
800
801/**
Jeff Mahoney5806f072006-06-26 00:27:19 -0700802 * idr_replace - replace pointer for given id
803 * @idp: idr handle
804 * @ptr: pointer you want associated with the id
805 * @id: lookup key
806 *
807 * Replace the pointer registered with an id and return the old value.
Randy Dunlap56083ab2010-10-26 14:19:08 -0700808 * A %-ENOENT return indicates that @id was not found.
809 * A %-EINVAL return indicates that @id was not within valid constraints.
Jeff Mahoney5806f072006-06-26 00:27:19 -0700810 *
Nadia Derbeycf481c22008-07-25 01:48:02 -0700811 * The caller must serialize with writers.
Jeff Mahoney5806f072006-06-26 00:27:19 -0700812 */
813void *idr_replace(struct idr *idp, void *ptr, int id)
814{
815 int n;
816 struct idr_layer *p, *old_p;
817
Tejun Heo2e1c9b22013-03-08 12:43:30 -0800818 if (id < 0)
Tejun Heoe8c8d1b2013-02-27 17:05:04 -0800819 return ERR_PTR(-EINVAL);
820
Jeff Mahoney5806f072006-06-26 00:27:19 -0700821 p = idp->top;
Manfred Spraul6ff2d392008-12-01 13:14:02 -0800822 if (!p)
823 return ERR_PTR(-EINVAL);
824
825 n = (p->layer+1) * IDR_BITS;
Jeff Mahoney5806f072006-06-26 00:27:19 -0700826
Jeff Mahoney5806f072006-06-26 00:27:19 -0700827 if (id >= (1 << n))
828 return ERR_PTR(-EINVAL);
829
830 n -= IDR_BITS;
831 while ((n > 0) && p) {
832 p = p->ary[(id >> n) & IDR_MASK];
833 n -= IDR_BITS;
834 }
835
836 n = id & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -0800837 if (unlikely(p == NULL || !test_bit(n, p->bitmap)))
Jeff Mahoney5806f072006-06-26 00:27:19 -0700838 return ERR_PTR(-ENOENT);
839
840 old_p = p->ary[n];
Nadia Derbeycf481c22008-07-25 01:48:02 -0700841 rcu_assign_pointer(p->ary[n], ptr);
Jeff Mahoney5806f072006-06-26 00:27:19 -0700842
843 return old_p;
844}
845EXPORT_SYMBOL(idr_replace);
846
Akinobu Mita199f0ca2008-04-29 01:03:13 -0700847void __init idr_init_cache(void)
Linus Torvalds1da177e2005-04-16 15:20:36 -0700848{
Akinobu Mita199f0ca2008-04-29 01:03:13 -0700849 idr_layer_cache = kmem_cache_create("idr_layer_cache",
Andrew Morton5b019e92009-01-15 13:51:21 -0800850 sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
Linus Torvalds1da177e2005-04-16 15:20:36 -0700851}
852
853/**
854 * idr_init - initialize idr handle
855 * @idp: idr handle
856 *
857 * This function is use to set up the handle (@idp) that you will pass
858 * to the rest of the functions.
859 */
860void idr_init(struct idr *idp)
861{
Linus Torvalds1da177e2005-04-16 15:20:36 -0700862 memset(idp, 0, sizeof(struct idr));
863 spin_lock_init(&idp->lock);
864}
865EXPORT_SYMBOL(idr_init);
Tejun Heo72dba582007-06-14 03:45:13 +0900866
867
Randy Dunlap56083ab2010-10-26 14:19:08 -0700868/**
869 * DOC: IDA description
Tejun Heo72dba582007-06-14 03:45:13 +0900870 * IDA - IDR based ID allocator
871 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700872 * This is id allocator without id -> pointer translation. Memory
Tejun Heo72dba582007-06-14 03:45:13 +0900873 * usage is much lower than full blown idr because each id only
874 * occupies a bit. ida uses a custom leaf node which contains
875 * IDA_BITMAP_BITS slots.
876 *
877 * 2007-04-25 written by Tejun Heo <htejun@gmail.com>
878 */
879
880static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
881{
882 unsigned long flags;
883
884 if (!ida->free_bitmap) {
885 spin_lock_irqsave(&ida->idr.lock, flags);
886 if (!ida->free_bitmap) {
887 ida->free_bitmap = bitmap;
888 bitmap = NULL;
889 }
890 spin_unlock_irqrestore(&ida->idr.lock, flags);
891 }
892
893 kfree(bitmap);
894}
895
896/**
897 * ida_pre_get - reserve resources for ida allocation
898 * @ida: ida handle
899 * @gfp_mask: memory allocation flag
900 *
901 * This function should be called prior to locking and calling the
902 * following function. It preallocates enough memory to satisfy the
903 * worst possible allocation.
904 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700905 * If the system is REALLY out of memory this function returns %0,
906 * otherwise %1.
Tejun Heo72dba582007-06-14 03:45:13 +0900907 */
908int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
909{
910 /* allocate idr_layers */
911 if (!idr_pre_get(&ida->idr, gfp_mask))
912 return 0;
913
914 /* allocate free_bitmap */
915 if (!ida->free_bitmap) {
916 struct ida_bitmap *bitmap;
917
918 bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
919 if (!bitmap)
920 return 0;
921
922 free_bitmap(ida, bitmap);
923 }
924
925 return 1;
926}
927EXPORT_SYMBOL(ida_pre_get);
928
929/**
930 * ida_get_new_above - allocate new ID above or equal to a start id
931 * @ida: ida handle
Naohiro Aotaea24ea82010-08-31 00:37:03 +0900932 * @starting_id: id to start search at
Tejun Heo72dba582007-06-14 03:45:13 +0900933 * @p_id: pointer to the allocated handle
934 *
Wang Sheng-Huie3816c52011-10-31 17:12:36 -0700935 * Allocate new ID above or equal to @starting_id. It should be called
936 * with any required locks.
Tejun Heo72dba582007-06-14 03:45:13 +0900937 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700938 * If memory is required, it will return %-EAGAIN, you should unlock
Tejun Heo72dba582007-06-14 03:45:13 +0900939 * and go back to the ida_pre_get() call. If the ida is full, it will
Randy Dunlap56083ab2010-10-26 14:19:08 -0700940 * return %-ENOSPC.
Tejun Heo72dba582007-06-14 03:45:13 +0900941 *
Randy Dunlap56083ab2010-10-26 14:19:08 -0700942 * @p_id returns a value in the range @starting_id ... %0x7fffffff.
Tejun Heo72dba582007-06-14 03:45:13 +0900943 */
944int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
945{
Tejun Heo326cf0f2013-02-27 17:05:02 -0800946 struct idr_layer *pa[MAX_IDR_LEVEL + 1];
Tejun Heo72dba582007-06-14 03:45:13 +0900947 struct ida_bitmap *bitmap;
948 unsigned long flags;
949 int idr_id = starting_id / IDA_BITMAP_BITS;
950 int offset = starting_id % IDA_BITMAP_BITS;
951 int t, id;
952
953 restart:
954 /* get vacant slot */
Tejun Heod5c74092013-02-27 17:03:55 -0800955 t = idr_get_empty_slot(&ida->idr, idr_id, pa, 0, &ida->idr);
Nadia Derbey944ca052008-07-25 01:47:59 -0700956 if (t < 0)
Tejun Heo12d1b432013-02-27 17:03:53 -0800957 return t == -ENOMEM ? -EAGAIN : t;
Tejun Heo72dba582007-06-14 03:45:13 +0900958
Fengguang Wu125c4c72012-10-04 17:13:15 -0700959 if (t * IDA_BITMAP_BITS >= MAX_IDR_BIT)
Tejun Heo72dba582007-06-14 03:45:13 +0900960 return -ENOSPC;
961
962 if (t != idr_id)
963 offset = 0;
964 idr_id = t;
965
966 /* if bitmap isn't there, create a new one */
967 bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
968 if (!bitmap) {
969 spin_lock_irqsave(&ida->idr.lock, flags);
970 bitmap = ida->free_bitmap;
971 ida->free_bitmap = NULL;
972 spin_unlock_irqrestore(&ida->idr.lock, flags);
973
974 if (!bitmap)
975 return -EAGAIN;
976
977 memset(bitmap, 0, sizeof(struct ida_bitmap));
Nadia Derbey3219b3b2008-07-25 01:48:00 -0700978 rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
979 (void *)bitmap);
Tejun Heo72dba582007-06-14 03:45:13 +0900980 pa[0]->count++;
981 }
982
983 /* lookup for empty slot */
984 t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
985 if (t == IDA_BITMAP_BITS) {
986 /* no empty slot after offset, continue to the next chunk */
987 idr_id++;
988 offset = 0;
989 goto restart;
990 }
991
992 id = idr_id * IDA_BITMAP_BITS + t;
Fengguang Wu125c4c72012-10-04 17:13:15 -0700993 if (id >= MAX_IDR_BIT)
Tejun Heo72dba582007-06-14 03:45:13 +0900994 return -ENOSPC;
995
996 __set_bit(t, bitmap->bitmap);
997 if (++bitmap->nr_busy == IDA_BITMAP_BITS)
998 idr_mark_full(pa, idr_id);
999
1000 *p_id = id;
1001
1002 /* Each leaf node can handle nearly a thousand slots and the
1003 * whole idea of ida is to have small memory foot print.
1004 * Throw away extra resources one by one after each successful
1005 * allocation.
1006 */
1007 if (ida->idr.id_free_cnt || ida->free_bitmap) {
Nadia Derbey4ae53782008-07-25 01:47:58 -07001008 struct idr_layer *p = get_from_free_list(&ida->idr);
Tejun Heo72dba582007-06-14 03:45:13 +09001009 if (p)
1010 kmem_cache_free(idr_layer_cache, p);
1011 }
1012
1013 return 0;
1014}
1015EXPORT_SYMBOL(ida_get_new_above);
1016
1017/**
Tejun Heo72dba582007-06-14 03:45:13 +09001018 * ida_remove - remove the given ID
1019 * @ida: ida handle
1020 * @id: ID to free
1021 */
1022void ida_remove(struct ida *ida, int id)
1023{
1024 struct idr_layer *p = ida->idr.top;
1025 int shift = (ida->idr.layers - 1) * IDR_BITS;
1026 int idr_id = id / IDA_BITMAP_BITS;
1027 int offset = id % IDA_BITMAP_BITS;
1028 int n;
1029 struct ida_bitmap *bitmap;
1030
1031 /* clear full bits while looking up the leaf idr_layer */
1032 while ((shift > 0) && p) {
1033 n = (idr_id >> shift) & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -08001034 __clear_bit(n, p->bitmap);
Tejun Heo72dba582007-06-14 03:45:13 +09001035 p = p->ary[n];
1036 shift -= IDR_BITS;
1037 }
1038
1039 if (p == NULL)
1040 goto err;
1041
1042 n = idr_id & IDR_MASK;
Tejun Heo1d9b2e12013-02-27 17:05:05 -08001043 __clear_bit(n, p->bitmap);
Tejun Heo72dba582007-06-14 03:45:13 +09001044
1045 bitmap = (void *)p->ary[n];
1046 if (!test_bit(offset, bitmap->bitmap))
1047 goto err;
1048
1049 /* update bitmap and remove it if empty */
1050 __clear_bit(offset, bitmap->bitmap);
1051 if (--bitmap->nr_busy == 0) {
Tejun Heo1d9b2e12013-02-27 17:05:05 -08001052 __set_bit(n, p->bitmap); /* to please idr_remove() */
Tejun Heo72dba582007-06-14 03:45:13 +09001053 idr_remove(&ida->idr, idr_id);
1054 free_bitmap(ida, bitmap);
1055 }
1056
1057 return;
1058
1059 err:
1060 printk(KERN_WARNING
1061 "ida_remove called for id=%d which is not allocated.\n", id);
1062}
1063EXPORT_SYMBOL(ida_remove);
1064
1065/**
1066 * ida_destroy - release all cached layers within an ida tree
Naohiro Aotaea24ea82010-08-31 00:37:03 +09001067 * @ida: ida handle
Tejun Heo72dba582007-06-14 03:45:13 +09001068 */
1069void ida_destroy(struct ida *ida)
1070{
1071 idr_destroy(&ida->idr);
1072 kfree(ida->free_bitmap);
1073}
1074EXPORT_SYMBOL(ida_destroy);
1075
1076/**
Rusty Russell88eca022011-08-03 16:21:06 -07001077 * ida_simple_get - get a new id.
1078 * @ida: the (initialized) ida.
1079 * @start: the minimum id (inclusive, < 0x8000000)
1080 * @end: the maximum id (exclusive, < 0x8000000 or 0)
1081 * @gfp_mask: memory allocation flags
1082 *
1083 * Allocates an id in the range start <= id < end, or returns -ENOSPC.
1084 * On memory allocation failure, returns -ENOMEM.
1085 *
1086 * Use ida_simple_remove() to get rid of an id.
1087 */
1088int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
1089 gfp_t gfp_mask)
1090{
1091 int ret, id;
1092 unsigned int max;
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001093 unsigned long flags;
Rusty Russell88eca022011-08-03 16:21:06 -07001094
1095 BUG_ON((int)start < 0);
1096 BUG_ON((int)end < 0);
1097
1098 if (end == 0)
1099 max = 0x80000000;
1100 else {
1101 BUG_ON(end < start);
1102 max = end - 1;
1103 }
1104
1105again:
1106 if (!ida_pre_get(ida, gfp_mask))
1107 return -ENOMEM;
1108
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001109 spin_lock_irqsave(&simple_ida_lock, flags);
Rusty Russell88eca022011-08-03 16:21:06 -07001110 ret = ida_get_new_above(ida, start, &id);
1111 if (!ret) {
1112 if (id > max) {
1113 ida_remove(ida, id);
1114 ret = -ENOSPC;
1115 } else {
1116 ret = id;
1117 }
1118 }
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001119 spin_unlock_irqrestore(&simple_ida_lock, flags);
Rusty Russell88eca022011-08-03 16:21:06 -07001120
1121 if (unlikely(ret == -EAGAIN))
1122 goto again;
1123
1124 return ret;
1125}
1126EXPORT_SYMBOL(ida_simple_get);
1127
1128/**
1129 * ida_simple_remove - remove an allocated id.
1130 * @ida: the (initialized) ida.
1131 * @id: the id returned by ida_simple_get.
1132 */
1133void ida_simple_remove(struct ida *ida, unsigned int id)
1134{
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001135 unsigned long flags;
1136
Rusty Russell88eca022011-08-03 16:21:06 -07001137 BUG_ON((int)id < 0);
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001138 spin_lock_irqsave(&simple_ida_lock, flags);
Rusty Russell88eca022011-08-03 16:21:06 -07001139 ida_remove(ida, id);
Tejun Heo46cbc1d2011-11-02 13:38:46 -07001140 spin_unlock_irqrestore(&simple_ida_lock, flags);
Rusty Russell88eca022011-08-03 16:21:06 -07001141}
1142EXPORT_SYMBOL(ida_simple_remove);
1143
1144/**
Tejun Heo72dba582007-06-14 03:45:13 +09001145 * ida_init - initialize ida handle
1146 * @ida: ida handle
1147 *
1148 * This function is use to set up the handle (@ida) that you will pass
1149 * to the rest of the functions.
1150 */
1151void ida_init(struct ida *ida)
1152{
1153 memset(ida, 0, sizeof(struct ida));
1154 idr_init(&ida->idr);
1155
1156}
1157EXPORT_SYMBOL(ida_init);