Blame view
lib/idr.c
28.5 KB
1da177e4c Linux-2.6.12-rc2 |
1 2 3 4 5 6 7 8 |
/* * 2002-10-18 written by Jim Houston jim.houston@ccur.com * Copyright (C) 2002 by Concurrent Computer Corporation * Distributed under the GNU GPL license version 2. * * Modified by George Anzinger to reuse immediately and to use * find bit instructions. Also removed _irq on spinlocks. * |
3219b3b74 idr: make idr_get... |
9 10 |
* Modified by Nadia Derbey to make it RCU safe. * |
e15ae2dd3 [PATCH] Whitespac... |
11 |
* Small id to pointer translation service. |
1da177e4c Linux-2.6.12-rc2 |
12 |
* |
e15ae2dd3 [PATCH] Whitespac... |
13 |
* It uses a radix tree like structure as a sparse array indexed |
1da177e4c Linux-2.6.12-rc2 |
14 |
* by the id to obtain the pointer. The bitmap makes allocating |
e15ae2dd3 [PATCH] Whitespac... |
15 |
* a new id quick. |
1da177e4c Linux-2.6.12-rc2 |
16 17 18 19 20 |
* * You call it to allocate an id (an int) an associate with that id a * pointer or what ever, we treat it as a (void *). You can pass this * id to a user for him to pass back at a later time. You then pass * that id to this code and it returns your pointer. |
1da177e4c Linux-2.6.12-rc2 |
21 22 23 24 25 |
*/ #ifndef TEST // to test in user space... #include <linux/slab.h> #include <linux/init.h> |
8bc3bcc93 lib: reduce the u... |
26 |
#include <linux/export.h> |
1da177e4c Linux-2.6.12-rc2 |
27 |
#endif |
5806f07cd [PATCH] lib: add ... |
28 |
#include <linux/err.h> |
1da177e4c Linux-2.6.12-rc2 |
29 30 |
#include <linux/string.h> #include <linux/idr.h> |
88eca0207 ida: simplified f... |
31 |
#include <linux/spinlock.h> |
d5c7409f7 idr: implement id... |
32 |
#include <linux/percpu.h> |
1da177e4c Linux-2.6.12-rc2 |
33 |
|
e8c8d1bc0 idr: remove MAX_I... |
34 35 36 37 38 39 40 41 |
#define MAX_IDR_SHIFT (sizeof(int) * 8 - 1) #define MAX_IDR_BIT (1U << MAX_IDR_SHIFT) /* Leave the possibility of an incomplete final layer */ #define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS) /* Number of id_layer structs to leave in free list */ #define MAX_IDR_FREE (MAX_IDR_LEVEL * 2) |
e18b890bb [PATCH] slab: rem... |
42 |
static struct kmem_cache *idr_layer_cache; |
d5c7409f7 idr: implement id... |
43 44 |
static DEFINE_PER_CPU(struct idr_layer *, idr_preload_head); static DEFINE_PER_CPU(int, idr_preload_cnt); |
88eca0207 ida: simplified f... |
45 |
static DEFINE_SPINLOCK(simple_ida_lock); |
1da177e4c Linux-2.6.12-rc2 |
46 |
|
326cf0f0f idr: fix top laye... |
47 48 49 50 51 52 53 |
/* the maximum ID which can be allocated given idr->layers */ static int idr_max(int layers) { int bits = min_t(int, layers * IDR_BITS, MAX_IDR_SHIFT); return (1 << bits) - 1; } |
54616283c idr: add idr_laye... |
54 55 56 57 58 59 60 61 62 |
/* * Prefix mask for an idr_layer at @layer. For layer 0, the prefix mask is * all bits except for the lower IDR_BITS. For layer 1, 2 * IDR_BITS, and * so on. */ static int idr_layer_prefix_mask(int layer) { return ~idr_max(layer + 1); } |
4ae537892 idr: rename some ... |
63 |
static struct idr_layer *get_from_free_list(struct idr *idp) |
1da177e4c Linux-2.6.12-rc2 |
64 65 |
{ struct idr_layer *p; |
c259cc281 [PATCH] Convert i... |
66 |
unsigned long flags; |
1da177e4c Linux-2.6.12-rc2 |
67 |
|
c259cc281 [PATCH] Convert i... |
68 |
spin_lock_irqsave(&idp->lock, flags); |
1da177e4c Linux-2.6.12-rc2 |
69 70 71 72 73 |
if ((p = idp->id_free)) { idp->id_free = p->ary[0]; idp->id_free_cnt--; p->ary[0] = NULL; } |
c259cc281 [PATCH] Convert i... |
74 |
spin_unlock_irqrestore(&idp->lock, flags); |
1da177e4c Linux-2.6.12-rc2 |
75 76 |
return(p); } |
d5c7409f7 idr: implement id... |
77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 |
/** * idr_layer_alloc - allocate a new idr_layer * @gfp_mask: allocation mask * @layer_idr: optional idr to allocate from * * If @layer_idr is %NULL, directly allocate one using @gfp_mask or fetch * one from the per-cpu preload buffer. If @layer_idr is not %NULL, fetch * an idr_layer from @idr->id_free. * * @layer_idr is to maintain backward compatibility with the old alloc * interface - idr_pre_get() and idr_get_new*() - and will be removed * together with per-pool preload buffer. */ static struct idr_layer *idr_layer_alloc(gfp_t gfp_mask, struct idr *layer_idr) { struct idr_layer *new; /* this is the old path, bypass to get_from_free_list() */ if (layer_idr) return get_from_free_list(layer_idr); |
59bfbcf01 idr: idr_alloc() ... |
97 98 99 100 101 102 103 104 |
/* * Try to allocate directly from kmem_cache. We want to try this * before preload buffer; otherwise, non-preloading idr_alloc() * users will end up taking advantage of preloading ones. As the * following is allowed to fail for preloaded cases, suppress * warning this time. */ new = kmem_cache_zalloc(idr_layer_cache, gfp_mask | __GFP_NOWARN); |
d5c7409f7 idr: implement id... |
105 106 107 108 109 110 111 |
if (new) return new; /* * Try to fetch one from the per-cpu preload buffer if in process * context. See idr_preload() for details. */ |
59bfbcf01 idr: idr_alloc() ... |
112 113 114 115 116 117 118 119 120 121 122 |
if (!in_interrupt()) { preempt_disable(); new = __this_cpu_read(idr_preload_head); if (new) { __this_cpu_write(idr_preload_head, new->ary[0]); __this_cpu_dec(idr_preload_cnt); new->ary[0] = NULL; } preempt_enable(); if (new) return new; |
d5c7409f7 idr: implement id... |
123 |
} |
59bfbcf01 idr: idr_alloc() ... |
124 125 126 127 128 129 |
/* * Both failed. Try kmem_cache again w/o adding __GFP_NOWARN so * that memory allocation failure warning is printed as intended. */ return kmem_cache_zalloc(idr_layer_cache, gfp_mask); |
d5c7409f7 idr: implement id... |
130 |
} |
cf481c20c idr: make idr_rem... |
131 132 133 134 135 136 137 |
static void idr_layer_rcu_free(struct rcu_head *head) { struct idr_layer *layer; layer = container_of(head, struct idr_layer, rcu_head); kmem_cache_free(idr_layer_cache, layer); } |
0ffc2a9c8 idr: implement lo... |
138 |
static inline void free_layer(struct idr *idr, struct idr_layer *p) |
cf481c20c idr: make idr_rem... |
139 |
{ |
15f3ec3f2 idr: reduce the u... |
140 |
if (idr->hint == p) |
0ffc2a9c8 idr: implement lo... |
141 |
RCU_INIT_POINTER(idr->hint, NULL); |
cf481c20c idr: make idr_rem... |
142 143 |
call_rcu(&p->rcu_head, idr_layer_rcu_free); } |
1eec00565 [PATCH] fix race ... |
144 |
/* only called when idp->lock is held */ |
4ae537892 idr: rename some ... |
145 |
static void __move_to_free_list(struct idr *idp, struct idr_layer *p) |
1eec00565 [PATCH] fix race ... |
146 147 148 149 150 |
{ p->ary[0] = idp->id_free; idp->id_free = p; idp->id_free_cnt++; } |
4ae537892 idr: rename some ... |
151 |
static void move_to_free_list(struct idr *idp, struct idr_layer *p) |
1da177e4c Linux-2.6.12-rc2 |
152 |
{ |
c259cc281 [PATCH] Convert i... |
153 |
unsigned long flags; |
1da177e4c Linux-2.6.12-rc2 |
154 155 156 |
/* * Depends on the return element being zeroed. */ |
c259cc281 [PATCH] Convert i... |
157 |
spin_lock_irqsave(&idp->lock, flags); |
4ae537892 idr: rename some ... |
158 |
__move_to_free_list(idp, p); |
c259cc281 [PATCH] Convert i... |
159 |
spin_unlock_irqrestore(&idp->lock, flags); |
1da177e4c Linux-2.6.12-rc2 |
160 |
} |
e33ac8bdb idr: separate out... |
161 162 163 164 |
static void idr_mark_full(struct idr_layer **pa, int id) { struct idr_layer *p = pa[0]; int l = 0; |
1d9b2e1e6 idr: remove lengt... |
165 |
__set_bit(id & IDR_MASK, p->bitmap); |
e33ac8bdb idr: separate out... |
166 167 168 169 170 171 |
/* * If this layer is full mark the bit in the layer above to * show that this part of the radix tree is full. This may * complete the layer above and require walking up the radix * tree. */ |
1d9b2e1e6 idr: remove lengt... |
172 |
while (bitmap_full(p->bitmap, IDR_SIZE)) { |
e33ac8bdb idr: separate out... |
173 174 175 |
if (!(p = pa[++l])) break; id = id >> IDR_BITS; |
1d9b2e1e6 idr: remove lengt... |
176 |
__set_bit((id & IDR_MASK), p->bitmap); |
e33ac8bdb idr: separate out... |
177 178 |
} } |
90ae3ae53 idr: remove dead ... |
179 |
static int __idr_pre_get(struct idr *idp, gfp_t gfp_mask) |
1da177e4c Linux-2.6.12-rc2 |
180 |
{ |
125c4c706 idr: rename MAX_L... |
181 |
while (idp->id_free_cnt < MAX_IDR_FREE) { |
1da177e4c Linux-2.6.12-rc2 |
182 |
struct idr_layer *new; |
5b019e990 lib/idr.c: use km... |
183 |
new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); |
e15ae2dd3 [PATCH] Whitespac... |
184 |
if (new == NULL) |
1da177e4c Linux-2.6.12-rc2 |
185 |
return (0); |
4ae537892 idr: rename some ... |
186 |
move_to_free_list(idp, new); |
1da177e4c Linux-2.6.12-rc2 |
187 188 189 |
} return 1; } |
1da177e4c Linux-2.6.12-rc2 |
190 |
|
12d1b4393 idr: remove _idr_... |
191 192 193 194 |
/** * sub_alloc - try to allocate an id without growing the tree depth * @idp: idr handle * @starting_id: id to start search at |
12d1b4393 idr: remove _idr_... |
195 |
* @pa: idr_layer[MAX_IDR_LEVEL] used as backtrack buffer |
d5c7409f7 idr: implement id... |
196 197 |
* @gfp_mask: allocation mask for idr_layer_alloc() * @layer_idr: optional idr passed to idr_layer_alloc() |
12d1b4393 idr: remove _idr_... |
198 199 200 201 202 203 204 205 206 |
* * Allocate an id in range [@starting_id, INT_MAX] from @idp without * growing its depth. Returns * * the allocated id >= 0 if successful, * -EAGAIN if the tree needs to grow for allocation to succeed, * -ENOSPC if the id space is exhausted, * -ENOMEM if more idr_layers need to be allocated. */ |
d5c7409f7 idr: implement id... |
207 208 |
static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa, gfp_t gfp_mask, struct idr *layer_idr) |
1da177e4c Linux-2.6.12-rc2 |
209 210 211 |
{ int n, m, sh; struct idr_layer *p, *new; |
7aae6dd80 idr: fix obscure ... |
212 |
int l, id, oid; |
1da177e4c Linux-2.6.12-rc2 |
213 214 |
id = *starting_id; |
7aae6dd80 idr: fix obscure ... |
215 |
restart: |
1da177e4c Linux-2.6.12-rc2 |
216 217 218 219 220 221 222 223 |
p = idp->top; l = idp->layers; pa[l--] = NULL; while (1) { /* * We run around this while until we reach the leaf node... */ n = (id >> (IDR_BITS*l)) & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
224 |
m = find_next_zero_bit(p->bitmap, IDR_SIZE, n); |
1da177e4c Linux-2.6.12-rc2 |
225 226 227 |
if (m == IDR_SIZE) { /* no space available go back to previous layer. */ l++; |
7aae6dd80 idr: fix obscure ... |
228 |
oid = id; |
e15ae2dd3 [PATCH] Whitespac... |
229 |
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1; |
7aae6dd80 idr: fix obscure ... |
230 231 |
/* if already at the top layer, we need to grow */ |
3afb69cb5 idr: fix overflow... |
232 |
if (id > idr_max(idp->layers)) { |
1da177e4c Linux-2.6.12-rc2 |
233 |
*starting_id = id; |
12d1b4393 idr: remove _idr_... |
234 |
return -EAGAIN; |
1da177e4c Linux-2.6.12-rc2 |
235 |
} |
d2e7276b6 idr: fix a critic... |
236 237 |
p = pa[l]; BUG_ON(!p); |
7aae6dd80 idr: fix obscure ... |
238 239 240 241 242 243 244 245 246 |
/* If we need to go up one layer, continue the * loop; otherwise, restart from the top. */ sh = IDR_BITS * (l + 1); if (oid >> sh == id >> sh) continue; else goto restart; |
1da177e4c Linux-2.6.12-rc2 |
247 248 249 250 251 |
} if (m != n) { sh = IDR_BITS*l; id = ((id >> sh) ^ n ^ m) << sh; } |
125c4c706 idr: rename MAX_L... |
252 |
if ((id >= MAX_IDR_BIT) || (id < 0)) |
12d1b4393 idr: remove _idr_... |
253 |
return -ENOSPC; |
1da177e4c Linux-2.6.12-rc2 |
254 255 256 257 258 259 |
if (l == 0) break; /* * Create the layer below if it is missing. */ if (!p->ary[m]) { |
d5c7409f7 idr: implement id... |
260 |
new = idr_layer_alloc(gfp_mask, layer_idr); |
4ae537892 idr: rename some ... |
261 |
if (!new) |
12d1b4393 idr: remove _idr_... |
262 |
return -ENOMEM; |
6ff2d39b9 lib/idr.c: fix rc... |
263 |
new->layer = l-1; |
54616283c idr: add idr_laye... |
264 |
new->prefix = id & idr_layer_prefix_mask(new->layer); |
3219b3b74 idr: make idr_get... |
265 |
rcu_assign_pointer(p->ary[m], new); |
1da177e4c Linux-2.6.12-rc2 |
266 267 268 269 270 |
p->count++; } pa[l--] = p; p = p->ary[m]; } |
e33ac8bdb idr: separate out... |
271 272 273 |
pa[l] = p; return id; |
1da177e4c Linux-2.6.12-rc2 |
274 |
} |
e33ac8bdb idr: separate out... |
275 |
static int idr_get_empty_slot(struct idr *idp, int starting_id, |
d5c7409f7 idr: implement id... |
276 277 |
struct idr_layer **pa, gfp_t gfp_mask, struct idr *layer_idr) |
1da177e4c Linux-2.6.12-rc2 |
278 279 280 |
{ struct idr_layer *p, *new; int layers, v, id; |
c259cc281 [PATCH] Convert i... |
281 |
unsigned long flags; |
e15ae2dd3 [PATCH] Whitespac... |
282 |
|
1da177e4c Linux-2.6.12-rc2 |
283 284 285 286 287 |
id = starting_id; build_up: p = idp->top; layers = idp->layers; if (unlikely(!p)) { |
d5c7409f7 idr: implement id... |
288 |
if (!(p = idr_layer_alloc(gfp_mask, layer_idr))) |
12d1b4393 idr: remove _idr_... |
289 |
return -ENOMEM; |
6ff2d39b9 lib/idr.c: fix rc... |
290 |
p->layer = 0; |
1da177e4c Linux-2.6.12-rc2 |
291 292 293 294 295 296 |
layers = 1; } /* * Add a new layer to the top of the tree if the requested * id is larger than the currently allocated space. */ |
326cf0f0f idr: fix top laye... |
297 |
while (id > idr_max(layers)) { |
1da177e4c Linux-2.6.12-rc2 |
298 |
layers++; |
711a49a07 lib/idr.c: Fix bu... |
299 300 301 302 303 304 |
if (!p->count) { /* special case: if the tree is currently empty, * then we grow the tree by moving the top node * upwards. */ p->layer++; |
54616283c idr: add idr_laye... |
305 |
WARN_ON_ONCE(p->prefix); |
1da177e4c Linux-2.6.12-rc2 |
306 |
continue; |
711a49a07 lib/idr.c: Fix bu... |
307 |
} |
d5c7409f7 idr: implement id... |
308 |
if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) { |
1da177e4c Linux-2.6.12-rc2 |
309 310 311 312 |
/* * The allocation failed. If we built part of * the structure tear it down. */ |
c259cc281 [PATCH] Convert i... |
313 |
spin_lock_irqsave(&idp->lock, flags); |
1da177e4c Linux-2.6.12-rc2 |
314 315 316 |
for (new = p; p && p != idp->top; new = p) { p = p->ary[0]; new->ary[0] = NULL; |
1d9b2e1e6 idr: remove lengt... |
317 318 |
new->count = 0; bitmap_clear(new->bitmap, 0, IDR_SIZE); |
4ae537892 idr: rename some ... |
319 |
__move_to_free_list(idp, new); |
1da177e4c Linux-2.6.12-rc2 |
320 |
} |
c259cc281 [PATCH] Convert i... |
321 |
spin_unlock_irqrestore(&idp->lock, flags); |
12d1b4393 idr: remove _idr_... |
322 |
return -ENOMEM; |
1da177e4c Linux-2.6.12-rc2 |
323 324 325 |
} new->ary[0] = p; new->count = 1; |
6ff2d39b9 lib/idr.c: fix rc... |
326 |
new->layer = layers-1; |
54616283c idr: add idr_laye... |
327 |
new->prefix = id & idr_layer_prefix_mask(new->layer); |
1d9b2e1e6 idr: remove lengt... |
328 329 |
if (bitmap_full(p->bitmap, IDR_SIZE)) __set_bit(0, new->bitmap); |
1da177e4c Linux-2.6.12-rc2 |
330 331 |
p = new; } |
3219b3b74 idr: make idr_get... |
332 |
rcu_assign_pointer(idp->top, p); |
1da177e4c Linux-2.6.12-rc2 |
333 |
idp->layers = layers; |
d5c7409f7 idr: implement id... |
334 |
v = sub_alloc(idp, &id, pa, gfp_mask, layer_idr); |
12d1b4393 idr: remove _idr_... |
335 |
if (v == -EAGAIN) |
1da177e4c Linux-2.6.12-rc2 |
336 337 338 |
goto build_up; return(v); } |
3594eb289 idr: refactor idr... |
339 340 341 342 |
/* * @id and @pa are from a successful allocation from idr_get_empty_slot(). * Install the user pointer @ptr and mark the slot full. */ |
0ffc2a9c8 idr: implement lo... |
343 344 |
static void idr_fill_slot(struct idr *idr, void *ptr, int id, struct idr_layer **pa) |
e33ac8bdb idr: separate out... |
345 |
{ |
0ffc2a9c8 idr: implement lo... |
346 347 |
/* update hint used for lookup, cleared from free_layer() */ rcu_assign_pointer(idr->hint, pa[0]); |
3594eb289 idr: refactor idr... |
348 349 350 |
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr); pa[0]->count++; idr_mark_full(pa, id); |
e33ac8bdb idr: separate out... |
351 |
} |
1da177e4c Linux-2.6.12-rc2 |
352 |
|
d5c7409f7 idr: implement id... |
353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 |
/** * idr_preload - preload for idr_alloc() * @gfp_mask: allocation mask to use for preloading * * Preload per-cpu layer buffer for idr_alloc(). Can only be used from * process context and each idr_preload() invocation should be matched with * idr_preload_end(). Note that preemption is disabled while preloaded. * * The first idr_alloc() in the preloaded section can be treated as if it * were invoked with @gfp_mask used for preloading. This allows using more * permissive allocation masks for idrs protected by spinlocks. * * For example, if idr_alloc() below fails, the failure can be treated as * if idr_alloc() were called with GFP_KERNEL rather than GFP_NOWAIT. * * idr_preload(GFP_KERNEL); * spin_lock(lock); * * id = idr_alloc(idr, ptr, start, end, GFP_NOWAIT); * * spin_unlock(lock); * idr_preload_end(); * if (id < 0) * error; */ void idr_preload(gfp_t gfp_mask) { /* * Consuming preload buffer from non-process context breaks preload * allocation guarantee. Disallow usage from those contexts. */ WARN_ON_ONCE(in_interrupt()); |
d0164adc8 mm, page_alloc: d... |
385 |
might_sleep_if(gfpflags_allow_blocking(gfp_mask)); |
d5c7409f7 idr: implement id... |
386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401 402 403 404 405 406 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 427 428 429 430 431 432 433 434 435 |
preempt_disable(); /* * idr_alloc() is likely to succeed w/o full idr_layer buffer and * return value from idr_alloc() needs to be checked for failure * anyway. Silently give up if allocation fails. The caller can * treat failures from idr_alloc() as if idr_alloc() were called * with @gfp_mask which should be enough. */ while (__this_cpu_read(idr_preload_cnt) < MAX_IDR_FREE) { struct idr_layer *new; preempt_enable(); new = kmem_cache_zalloc(idr_layer_cache, gfp_mask); preempt_disable(); if (!new) break; /* link the new one to per-cpu preload list */ new->ary[0] = __this_cpu_read(idr_preload_head); __this_cpu_write(idr_preload_head, new); __this_cpu_inc(idr_preload_cnt); } } EXPORT_SYMBOL(idr_preload); /** * idr_alloc - allocate new idr entry * @idr: the (initialized) idr * @ptr: pointer to be associated with the new id * @start: the minimum id (inclusive) * @end: the maximum id (exclusive, <= 0 for max) * @gfp_mask: memory allocation flags * * Allocate an id in [start, end) and associate it with @ptr. If no ID is * available in the specified range, returns -ENOSPC. On memory allocation * failure, returns -ENOMEM. * * Note that @end is treated as max when <= 0. This is to always allow * using @start + N as @end as long as N is inside integer range. * * The user is responsible for exclusively synchronizing all operations * which may modify @idr. However, read-only accesses such as idr_find() * or iteration can be performed under RCU read lock provided the user * destroys @ptr in RCU-safe way after removal from idr. */ int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask) { int max = end > 0 ? end - 1 : INT_MAX; /* inclusive upper limit */ |
326cf0f0f idr: fix top laye... |
436 |
struct idr_layer *pa[MAX_IDR_LEVEL + 1]; |
d5c7409f7 idr: implement id... |
437 |
int id; |
d0164adc8 mm, page_alloc: d... |
438 |
might_sleep_if(gfpflags_allow_blocking(gfp_mask)); |
d5c7409f7 idr: implement id... |
439 440 441 442 443 444 445 446 447 448 449 450 451 |
/* sanity checks */ if (WARN_ON_ONCE(start < 0)) return -EINVAL; if (unlikely(max < start)) return -ENOSPC; /* allocate id */ id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL); if (unlikely(id < 0)) return id; if (unlikely(id > max)) return -ENOSPC; |
0ffc2a9c8 idr: implement lo... |
452 |
idr_fill_slot(idr, ptr, id, pa); |
d5c7409f7 idr: implement id... |
453 454 455 |
return id; } EXPORT_SYMBOL_GPL(idr_alloc); |
3e6628c4b idr: introduce id... |
456 457 458 459 460 461 462 463 464 465 466 467 468 469 470 471 472 473 474 475 476 477 478 479 480 481 |
/** * idr_alloc_cyclic - allocate new idr entry in a cyclical fashion * @idr: the (initialized) idr * @ptr: pointer to be associated with the new id * @start: the minimum id (inclusive) * @end: the maximum id (exclusive, <= 0 for max) * @gfp_mask: memory allocation flags * * Essentially the same as idr_alloc, but prefers to allocate progressively * higher ids if it can. If the "cur" counter wraps, then it will start again * at the "start" end of the range and allocate one that has already been used. */ int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask) { int id; id = idr_alloc(idr, ptr, max(start, idr->cur), end, gfp_mask); if (id == -ENOSPC) id = idr_alloc(idr, ptr, start, end, gfp_mask); if (likely(id >= 0)) idr->cur = id + 1; return id; } EXPORT_SYMBOL(idr_alloc_cyclic); |
1da177e4c Linux-2.6.12-rc2 |
482 483 |
static void idr_remove_warning(int id) { |
dd04b452f idr: print a stac... |
484 485 |
WARN(1, "idr_remove called for id=%d which is not allocated. ", id); |
1da177e4c Linux-2.6.12-rc2 |
486 487 488 489 490 |
} static void sub_remove(struct idr *idp, int shift, int id) { struct idr_layer *p = idp->top; |
326cf0f0f idr: fix top laye... |
491 |
struct idr_layer **pa[MAX_IDR_LEVEL + 1]; |
1da177e4c Linux-2.6.12-rc2 |
492 |
struct idr_layer ***paa = &pa[0]; |
cf481c20c idr: make idr_rem... |
493 |
struct idr_layer *to_free; |
1da177e4c Linux-2.6.12-rc2 |
494 495 496 497 498 499 500 |
int n; *paa = NULL; *++paa = &idp->top; while ((shift > 0) && p) { n = (id >> shift) & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
501 |
__clear_bit(n, p->bitmap); |
1da177e4c Linux-2.6.12-rc2 |
502 503 504 505 506 |
*++paa = &p->ary[n]; p = p->ary[n]; shift -= IDR_BITS; } n = id & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
507 508 |
if (likely(p != NULL && test_bit(n, p->bitmap))) { __clear_bit(n, p->bitmap); |
3f59b067c lib/idr.c: use RC... |
509 |
RCU_INIT_POINTER(p->ary[n], NULL); |
cf481c20c idr: make idr_rem... |
510 |
to_free = NULL; |
1da177e4c Linux-2.6.12-rc2 |
511 |
while(*paa && ! --((**paa)->count)){ |
cf481c20c idr: make idr_rem... |
512 |
if (to_free) |
0ffc2a9c8 idr: implement lo... |
513 |
free_layer(idp, to_free); |
cf481c20c idr: make idr_rem... |
514 |
to_free = **paa; |
1da177e4c Linux-2.6.12-rc2 |
515 516 |
**paa-- = NULL; } |
e15ae2dd3 [PATCH] Whitespac... |
517 |
if (!*paa) |
1da177e4c Linux-2.6.12-rc2 |
518 |
idp->layers = 0; |
cf481c20c idr: make idr_rem... |
519 |
if (to_free) |
0ffc2a9c8 idr: implement lo... |
520 |
free_layer(idp, to_free); |
e15ae2dd3 [PATCH] Whitespac... |
521 |
} else |
1da177e4c Linux-2.6.12-rc2 |
522 |
idr_remove_warning(id); |
1da177e4c Linux-2.6.12-rc2 |
523 524 525 |
} /** |
56083ab17 docbook: add idr/... |
526 |
* idr_remove - remove the given id and free its slot |
72fd4a35a [PATCH] Numerous ... |
527 528 |
* @idp: idr handle * @id: unique key |
1da177e4c Linux-2.6.12-rc2 |
529 530 531 532 |
*/ void idr_remove(struct idr *idp, int id) { struct idr_layer *p; |
cf481c20c idr: make idr_rem... |
533 |
struct idr_layer *to_free; |
1da177e4c Linux-2.6.12-rc2 |
534 |
|
2e1c9b286 idr: remove WARN_... |
535 |
if (id < 0) |
e8c8d1bc0 idr: remove MAX_I... |
536 |
return; |
1da177e4c Linux-2.6.12-rc2 |
537 |
|
8f9f665a7 idr: fix unexpect... |
538 539 540 541 |
if (id > idr_max(idp->layers)) { idr_remove_warning(id); return; } |
1da177e4c Linux-2.6.12-rc2 |
542 |
sub_remove(idp, (idp->layers - 1) * IDR_BITS, id); |
e15ae2dd3 [PATCH] Whitespac... |
543 |
if (idp->top && idp->top->count == 1 && (idp->layers > 1) && |
cf481c20c idr: make idr_rem... |
544 545 546 547 548 549 550 551 |
idp->top->ary[0]) { /* * Single child at leftmost slot: we can shrink the tree. * This level is not needed anymore since when layers are * inserted, they are inserted at the top of the existing * tree. */ to_free = idp->top; |
1da177e4c Linux-2.6.12-rc2 |
552 |
p = idp->top->ary[0]; |
cf481c20c idr: make idr_rem... |
553 |
rcu_assign_pointer(idp->top, p); |
1da177e4c Linux-2.6.12-rc2 |
554 |
--idp->layers; |
1d9b2e1e6 idr: remove lengt... |
555 556 |
to_free->count = 0; bitmap_clear(to_free->bitmap, 0, IDR_SIZE); |
0ffc2a9c8 idr: implement lo... |
557 |
free_layer(idp, to_free); |
1da177e4c Linux-2.6.12-rc2 |
558 |
} |
1da177e4c Linux-2.6.12-rc2 |
559 560 |
} EXPORT_SYMBOL(idr_remove); |
90ae3ae53 idr: remove dead ... |
561 |
static void __idr_remove_all(struct idr *idp) |
23936cc0b lib: add idr_remo... |
562 |
{ |
6ace06dc6 idr_remove_all: k... |
563 |
int n, id, max; |
2dcb22b34 idr: fix backtrac... |
564 |
int bt_mask; |
23936cc0b lib: add idr_remo... |
565 |
struct idr_layer *p; |
326cf0f0f idr: fix top laye... |
566 |
struct idr_layer *pa[MAX_IDR_LEVEL + 1]; |
23936cc0b lib: add idr_remo... |
567 568 569 |
struct idr_layer **paa = &pa[0]; n = idp->layers * IDR_BITS; |
93b7aca35 lib/idr.c: fix ou... |
570 |
*paa = idp->top; |
3f59b067c lib/idr.c: use RC... |
571 |
RCU_INIT_POINTER(idp->top, NULL); |
326cf0f0f idr: fix top laye... |
572 |
max = idr_max(idp->layers); |
23936cc0b lib: add idr_remo... |
573 574 |
id = 0; |
326cf0f0f idr: fix top laye... |
575 |
while (id >= 0 && id <= max) { |
93b7aca35 lib/idr.c: fix ou... |
576 |
p = *paa; |
23936cc0b lib: add idr_remo... |
577 578 |
while (n > IDR_BITS && p) { n -= IDR_BITS; |
23936cc0b lib: add idr_remo... |
579 |
p = p->ary[(id >> n) & IDR_MASK]; |
93b7aca35 lib/idr.c: fix ou... |
580 |
*++paa = p; |
23936cc0b lib: add idr_remo... |
581 |
} |
2dcb22b34 idr: fix backtrac... |
582 |
bt_mask = id; |
23936cc0b lib: add idr_remo... |
583 |
id += 1 << n; |
2dcb22b34 idr: fix backtrac... |
584 585 |
/* Get the highest bit that the above add changed from 0->1. */ while (n < fls(id ^ bt_mask)) { |
93b7aca35 lib/idr.c: fix ou... |
586 587 |
if (*paa) free_layer(idp, *paa); |
23936cc0b lib: add idr_remo... |
588 |
n += IDR_BITS; |
93b7aca35 lib/idr.c: fix ou... |
589 |
--paa; |
23936cc0b lib: add idr_remo... |
590 591 |
} } |
23936cc0b lib: add idr_remo... |
592 593 |
idp->layers = 0; } |
23936cc0b lib: add idr_remo... |
594 595 |
/** |
8d3b35914 [PATCH] inotify/i... |
596 |
* idr_destroy - release all cached layers within an idr tree |
ea24ea850 idr: fix kernel-d... |
597 |
* @idp: idr handle |
9bb26bc1f idr: make idr_des... |
598 599 600 601 602 603 604 |
* * Free all id mappings and all idp_layers. After this function, @idp is * completely unused and can be freed / recycled. The caller is * responsible for ensuring that no one else accesses @idp during or after * idr_destroy(). * * A typical clean-up sequence for objects stored in an idr tree will use |
da3dae54e Documentation: Do... |
605 |
* idr_for_each() to free all objects, if necessary, then idr_destroy() to |
9bb26bc1f idr: make idr_des... |
606 |
* free up the id mappings and cached idr_layers. |
8d3b35914 [PATCH] inotify/i... |
607 608 609 |
*/ void idr_destroy(struct idr *idp) { |
fe6e24ec9 idr: deprecate id... |
610 |
__idr_remove_all(idp); |
9bb26bc1f idr: make idr_des... |
611 |
|
8d3b35914 [PATCH] inotify/i... |
612 |
while (idp->id_free_cnt) { |
4ae537892 idr: rename some ... |
613 |
struct idr_layer *p = get_from_free_list(idp); |
8d3b35914 [PATCH] inotify/i... |
614 615 616 617 |
kmem_cache_free(idr_layer_cache, p); } } EXPORT_SYMBOL(idr_destroy); |
0ffc2a9c8 idr: implement lo... |
618 |
void *idr_find_slowpath(struct idr *idp, int id) |
1da177e4c Linux-2.6.12-rc2 |
619 620 621 |
{ int n; struct idr_layer *p; |
2e1c9b286 idr: remove WARN_... |
622 |
if (id < 0) |
e8c8d1bc0 idr: remove MAX_I... |
623 |
return NULL; |
96be753af idr: Apply lockde... |
624 |
p = rcu_dereference_raw(idp->top); |
6ff2d39b9 lib/idr.c: fix rc... |
625 626 627 |
if (!p) return NULL; n = (p->layer+1) * IDR_BITS; |
1da177e4c Linux-2.6.12-rc2 |
628 |
|
326cf0f0f idr: fix top laye... |
629 |
if (id > idr_max(p->layer + 1)) |
1da177e4c Linux-2.6.12-rc2 |
630 |
return NULL; |
6ff2d39b9 lib/idr.c: fix rc... |
631 |
BUG_ON(n == 0); |
1da177e4c Linux-2.6.12-rc2 |
632 633 634 |
while (n > 0 && p) { n -= IDR_BITS; |
6ff2d39b9 lib/idr.c: fix rc... |
635 |
BUG_ON(n != p->layer*IDR_BITS); |
96be753af idr: Apply lockde... |
636 |
p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); |
1da177e4c Linux-2.6.12-rc2 |
637 638 639 |
} return((void *)p); } |
0ffc2a9c8 idr: implement lo... |
640 |
EXPORT_SYMBOL(idr_find_slowpath); |
1da177e4c Linux-2.6.12-rc2 |
641 |
|
5806f07cd [PATCH] lib: add ... |
642 |
/** |
96d7fa421 lib: add idr_for_... |
643 644 645 646 647 648 649 650 651 652 653 654 655 |
* idr_for_each - iterate through all stored pointers * @idp: idr handle * @fn: function to be called for each pointer * @data: data passed back to callback function * * Iterate over the pointers registered with the given idr. The * callback function will be called for each pointer currently * registered, passing the id, the pointer and the data pointer passed * to this function. It is not safe to modify the idr tree while in * the callback, so functions such as idr_get_new and idr_remove are * not allowed. * * We check the return of @fn each time. If it returns anything other |
56083ab17 docbook: add idr/... |
656 |
* than %0, we break out and return that value. |
96d7fa421 lib: add idr_for_... |
657 658 659 660 661 662 663 664 |
* * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove(). */ int idr_for_each(struct idr *idp, int (*fn)(int id, void *p, void *data), void *data) { int n, id, max, error = 0; struct idr_layer *p; |
326cf0f0f idr: fix top laye... |
665 |
struct idr_layer *pa[MAX_IDR_LEVEL + 1]; |
96d7fa421 lib: add idr_for_... |
666 667 668 |
struct idr_layer **paa = &pa[0]; n = idp->layers * IDR_BITS; |
93b7aca35 lib/idr.c: fix ou... |
669 |
*paa = rcu_dereference_raw(idp->top); |
326cf0f0f idr: fix top laye... |
670 |
max = idr_max(idp->layers); |
96d7fa421 lib: add idr_for_... |
671 672 |
id = 0; |
326cf0f0f idr: fix top laye... |
673 |
while (id >= 0 && id <= max) { |
93b7aca35 lib/idr.c: fix ou... |
674 |
p = *paa; |
96d7fa421 lib: add idr_for_... |
675 676 |
while (n > 0 && p) { n -= IDR_BITS; |
96be753af idr: Apply lockde... |
677 |
p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); |
93b7aca35 lib/idr.c: fix ou... |
678 |
*++paa = p; |
96d7fa421 lib: add idr_for_... |
679 680 681 682 683 684 685 686 687 688 689 |
} if (p) { error = fn(id, (void *)p, data); if (error) break; } id += 1 << n; while (n < fls(id)) { n += IDR_BITS; |
93b7aca35 lib/idr.c: fix ou... |
690 |
--paa; |
96d7fa421 lib: add idr_for_... |
691 692 693 694 695 696 697 698 |
} } return error; } EXPORT_SYMBOL(idr_for_each); /** |
38460b48d cgroup: CSS ID su... |
699 700 |
* idr_get_next - lookup next object of id to given id. * @idp: idr handle |
ea24ea850 idr: fix kernel-d... |
701 |
* @nextidp: pointer to lookup key |
38460b48d cgroup: CSS ID su... |
702 703 |
* * Returns pointer to registered object with id, which is next number to |
1458ce166 idr: describe how... |
704 705 |
* given id. After being looked up, *@nextidp will be updated for the next * iteration. |
9f7de8275 idr: make idr_get... |
706 707 708 |
* * This function can be called under rcu_read_lock(), given that the leaf * pointers lifetimes are correctly managed. |
38460b48d cgroup: CSS ID su... |
709 |
*/ |
38460b48d cgroup: CSS ID su... |
710 711 |
void *idr_get_next(struct idr *idp, int *nextidp) { |
326cf0f0f idr: fix top laye... |
712 |
struct idr_layer *p, *pa[MAX_IDR_LEVEL + 1]; |
38460b48d cgroup: CSS ID su... |
713 714 715 716 717 |
struct idr_layer **paa = &pa[0]; int id = *nextidp; int n, max; /* find first ent */ |
93b7aca35 lib/idr.c: fix ou... |
718 |
p = *paa = rcu_dereference_raw(idp->top); |
38460b48d cgroup: CSS ID su... |
719 720 |
if (!p) return NULL; |
9f7de8275 idr: make idr_get... |
721 |
n = (p->layer + 1) * IDR_BITS; |
326cf0f0f idr: fix top laye... |
722 |
max = idr_max(p->layer + 1); |
38460b48d cgroup: CSS ID su... |
723 |
|
326cf0f0f idr: fix top laye... |
724 |
while (id >= 0 && id <= max) { |
93b7aca35 lib/idr.c: fix ou... |
725 |
p = *paa; |
38460b48d cgroup: CSS ID su... |
726 727 |
while (n > 0 && p) { n -= IDR_BITS; |
94bfa3b66 idr: fix RCU lock... |
728 |
p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]); |
93b7aca35 lib/idr.c: fix ou... |
729 |
*++paa = p; |
38460b48d cgroup: CSS ID su... |
730 731 732 733 734 735 |
} if (p) { *nextidp = id; return p; } |
6cdae7416 idr: fix a subtle... |
736 737 738 739 740 741 742 743 |
/* * Proceed to the next layer at the current level. Unlike * idr_for_each(), @id isn't guaranteed to be aligned to * layer boundary at this point and adding 1 << n may * incorrectly skip IDs. Make sure we jump to the * beginning of the next layer using round_up(). */ id = round_up(id + 1, 1 << n); |
38460b48d cgroup: CSS ID su... |
744 745 |
while (n < fls(id)) { n += IDR_BITS; |
93b7aca35 lib/idr.c: fix ou... |
746 |
--paa; |
38460b48d cgroup: CSS ID su... |
747 748 749 750 |
} } return NULL; } |
4d1ee80f3 idr: export idr_g... |
751 |
EXPORT_SYMBOL(idr_get_next); |
38460b48d cgroup: CSS ID su... |
752 753 754 |
/** |
5806f07cd [PATCH] lib: add ... |
755 756 757 758 759 760 |
* idr_replace - replace pointer for given id * @idp: idr handle * @ptr: pointer you want associated with the id * @id: lookup key * * Replace the pointer registered with an id and return the old value. |
56083ab17 docbook: add idr/... |
761 762 |
* A %-ENOENT return indicates that @id was not found. * A %-EINVAL return indicates that @id was not within valid constraints. |
5806f07cd [PATCH] lib: add ... |
763 |
* |
cf481c20c idr: make idr_rem... |
764 |
* The caller must serialize with writers. |
5806f07cd [PATCH] lib: add ... |
765 766 767 768 769 |
*/ void *idr_replace(struct idr *idp, void *ptr, int id) { int n; struct idr_layer *p, *old_p; |
2e1c9b286 idr: remove WARN_... |
770 |
if (id < 0) |
e8c8d1bc0 idr: remove MAX_I... |
771 |
return ERR_PTR(-EINVAL); |
5806f07cd [PATCH] lib: add ... |
772 |
p = idp->top; |
6ff2d39b9 lib/idr.c: fix rc... |
773 |
if (!p) |
b93804b2f idr: fix idr_repl... |
774 |
return ERR_PTR(-ENOENT); |
6ff2d39b9 lib/idr.c: fix rc... |
775 |
|
3afb69cb5 idr: fix overflow... |
776 |
if (id > idr_max(p->layer + 1)) |
b93804b2f idr: fix idr_repl... |
777 |
return ERR_PTR(-ENOENT); |
5806f07cd [PATCH] lib: add ... |
778 |
|
3afb69cb5 idr: fix overflow... |
779 |
n = p->layer * IDR_BITS; |
5806f07cd [PATCH] lib: add ... |
780 781 782 783 784 785 |
while ((n > 0) && p) { p = p->ary[(id >> n) & IDR_MASK]; n -= IDR_BITS; } n = id & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
786 |
if (unlikely(p == NULL || !test_bit(n, p->bitmap))) |
5806f07cd [PATCH] lib: add ... |
787 788 789 |
return ERR_PTR(-ENOENT); old_p = p->ary[n]; |
cf481c20c idr: make idr_rem... |
790 |
rcu_assign_pointer(p->ary[n], ptr); |
5806f07cd [PATCH] lib: add ... |
791 792 793 794 |
return old_p; } EXPORT_SYMBOL(idr_replace); |
199f0ca51 idr: create idr_l... |
795 |
void __init idr_init_cache(void) |
1da177e4c Linux-2.6.12-rc2 |
796 |
{ |
199f0ca51 idr: create idr_l... |
797 |
idr_layer_cache = kmem_cache_create("idr_layer_cache", |
5b019e990 lib/idr.c: use km... |
798 |
sizeof(struct idr_layer), 0, SLAB_PANIC, NULL); |
1da177e4c Linux-2.6.12-rc2 |
799 800 801 802 803 804 805 806 807 808 809 |
} /** * idr_init - initialize idr handle * @idp: idr handle * * This function is use to set up the handle (@idp) that you will pass * to the rest of the functions. */ void idr_init(struct idr *idp) { |
1da177e4c Linux-2.6.12-rc2 |
810 811 812 813 |
memset(idp, 0, sizeof(struct idr)); spin_lock_init(&idp->lock); } EXPORT_SYMBOL(idr_init); |
72dba584b ida: implement id... |
814 |
|
05f7a7d6a idr: Add new func... |
815 816 817 818 819 820 821 822 823 824 |
static int idr_has_entry(int id, void *p, void *data) { return 1; } bool idr_is_empty(struct idr *idp) { return !idr_for_each(idp, idr_has_entry, NULL); } EXPORT_SYMBOL(idr_is_empty); |
72dba584b ida: implement id... |
825 |
|
56083ab17 docbook: add idr/... |
826 827 |
/** * DOC: IDA description |
72dba584b ida: implement id... |
828 829 |
* IDA - IDR based ID allocator * |
56083ab17 docbook: add idr/... |
830 |
* This is id allocator without id -> pointer translation. Memory |
72dba584b ida: implement id... |
831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 |
* usage is much lower than full blown idr because each id only * occupies a bit. ida uses a custom leaf node which contains * IDA_BITMAP_BITS slots. * * 2007-04-25 written by Tejun Heo <htejun@gmail.com> */ static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap) { unsigned long flags; if (!ida->free_bitmap) { spin_lock_irqsave(&ida->idr.lock, flags); if (!ida->free_bitmap) { ida->free_bitmap = bitmap; bitmap = NULL; } spin_unlock_irqrestore(&ida->idr.lock, flags); } kfree(bitmap); } /** * ida_pre_get - reserve resources for ida allocation * @ida: ida handle * @gfp_mask: memory allocation flag * * This function should be called prior to locking and calling the * following function. It preallocates enough memory to satisfy the * worst possible allocation. * |
56083ab17 docbook: add idr/... |
863 864 |
* If the system is REALLY out of memory this function returns %0, * otherwise %1. |
72dba584b ida: implement id... |
865 866 867 868 |
*/ int ida_pre_get(struct ida *ida, gfp_t gfp_mask) { /* allocate idr_layers */ |
c8615d371 idr: deprecate id... |
869 |
if (!__idr_pre_get(&ida->idr, gfp_mask)) |
72dba584b ida: implement id... |
870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 |
return 0; /* allocate free_bitmap */ if (!ida->free_bitmap) { struct ida_bitmap *bitmap; bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask); if (!bitmap) return 0; free_bitmap(ida, bitmap); } return 1; } EXPORT_SYMBOL(ida_pre_get); /** * ida_get_new_above - allocate new ID above or equal to a start id * @ida: ida handle |
ea24ea850 idr: fix kernel-d... |
890 |
* @starting_id: id to start search at |
72dba584b ida: implement id... |
891 892 |
* @p_id: pointer to the allocated handle * |
e3816c540 lib/idr.c: fix co... |
893 894 |
* Allocate new ID above or equal to @starting_id. It should be called * with any required locks. |
72dba584b ida: implement id... |
895 |
* |
56083ab17 docbook: add idr/... |
896 |
* If memory is required, it will return %-EAGAIN, you should unlock |
72dba584b ida: implement id... |
897 |
* and go back to the ida_pre_get() call. If the ida is full, it will |
56083ab17 docbook: add idr/... |
898 |
* return %-ENOSPC. |
72dba584b ida: implement id... |
899 |
* |
a2ef9471c lib/ida: document... |
900 901 902 |
* Note that callers must ensure that concurrent access to @ida is not possible. * See ida_simple_get() for a varaint which takes care of locking. * |
56083ab17 docbook: add idr/... |
903 |
* @p_id returns a value in the range @starting_id ... %0x7fffffff. |
72dba584b ida: implement id... |
904 905 906 |
*/ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id) { |
326cf0f0f idr: fix top laye... |
907 |
struct idr_layer *pa[MAX_IDR_LEVEL + 1]; |
72dba584b ida: implement id... |
908 909 910 911 912 913 914 915 |
struct ida_bitmap *bitmap; unsigned long flags; int idr_id = starting_id / IDA_BITMAP_BITS; int offset = starting_id % IDA_BITMAP_BITS; int t, id; restart: /* get vacant slot */ |
d5c7409f7 idr: implement id... |
916 |
t = idr_get_empty_slot(&ida->idr, idr_id, pa, 0, &ida->idr); |
944ca05c7 idr: error checki... |
917 |
if (t < 0) |
12d1b4393 idr: remove _idr_... |
918 |
return t == -ENOMEM ? -EAGAIN : t; |
72dba584b ida: implement id... |
919 |
|
125c4c706 idr: rename MAX_L... |
920 |
if (t * IDA_BITMAP_BITS >= MAX_IDR_BIT) |
72dba584b ida: implement id... |
921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 |
return -ENOSPC; if (t != idr_id) offset = 0; idr_id = t; /* if bitmap isn't there, create a new one */ bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK]; if (!bitmap) { spin_lock_irqsave(&ida->idr.lock, flags); bitmap = ida->free_bitmap; ida->free_bitmap = NULL; spin_unlock_irqrestore(&ida->idr.lock, flags); if (!bitmap) return -EAGAIN; memset(bitmap, 0, sizeof(struct ida_bitmap)); |
3219b3b74 idr: make idr_get... |
939 940 |
rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK], (void *)bitmap); |
72dba584b ida: implement id... |
941 942 943 944 945 946 947 948 949 950 951 952 953 |
pa[0]->count++; } /* lookup for empty slot */ t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset); if (t == IDA_BITMAP_BITS) { /* no empty slot after offset, continue to the next chunk */ idr_id++; offset = 0; goto restart; } id = idr_id * IDA_BITMAP_BITS + t; |
125c4c706 idr: rename MAX_L... |
954 |
if (id >= MAX_IDR_BIT) |
72dba584b ida: implement id... |
955 956 957 958 959 960 961 962 963 964 965 966 967 968 |
return -ENOSPC; __set_bit(t, bitmap->bitmap); if (++bitmap->nr_busy == IDA_BITMAP_BITS) idr_mark_full(pa, idr_id); *p_id = id; /* Each leaf node can handle nearly a thousand slots and the * whole idea of ida is to have small memory foot print. * Throw away extra resources one by one after each successful * allocation. */ if (ida->idr.id_free_cnt || ida->free_bitmap) { |
4ae537892 idr: rename some ... |
969 |
struct idr_layer *p = get_from_free_list(&ida->idr); |
72dba584b ida: implement id... |
970 971 972 973 974 975 976 977 978 |
if (p) kmem_cache_free(idr_layer_cache, p); } return 0; } EXPORT_SYMBOL(ida_get_new_above); /** |
72dba584b ida: implement id... |
979 980 981 982 983 984 985 986 987 988 989 990 |
* ida_remove - remove the given ID * @ida: ida handle * @id: ID to free */ void ida_remove(struct ida *ida, int id) { struct idr_layer *p = ida->idr.top; int shift = (ida->idr.layers - 1) * IDR_BITS; int idr_id = id / IDA_BITMAP_BITS; int offset = id % IDA_BITMAP_BITS; int n; struct ida_bitmap *bitmap; |
8f9f665a7 idr: fix unexpect... |
991 992 |
if (idr_id > idr_max(ida->idr.layers)) goto err; |
72dba584b ida: implement id... |
993 994 995 |
/* clear full bits while looking up the leaf idr_layer */ while ((shift > 0) && p) { n = (idr_id >> shift) & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
996 |
__clear_bit(n, p->bitmap); |
72dba584b ida: implement id... |
997 998 999 1000 1001 1002 1003 1004 |
p = p->ary[n]; shift -= IDR_BITS; } if (p == NULL) goto err; n = idr_id & IDR_MASK; |
1d9b2e1e6 idr: remove lengt... |
1005 |
__clear_bit(n, p->bitmap); |
72dba584b ida: implement id... |
1006 1007 |
bitmap = (void *)p->ary[n]; |
aef0f62e8 idr: fix NULL poi... |
1008 |
if (!bitmap || !test_bit(offset, bitmap->bitmap)) |
72dba584b ida: implement id... |
1009 1010 1011 1012 1013 |
goto err; /* update bitmap and remove it if empty */ __clear_bit(offset, bitmap->bitmap); if (--bitmap->nr_busy == 0) { |
1d9b2e1e6 idr: remove lengt... |
1014 |
__set_bit(n, p->bitmap); /* to please idr_remove() */ |
72dba584b ida: implement id... |
1015 1016 1017 1018 1019 1020 1021 |
idr_remove(&ida->idr, idr_id); free_bitmap(ida, bitmap); } return; err: |
dd04b452f idr: print a stac... |
1022 1023 |
WARN(1, "ida_remove called for id=%d which is not allocated. ", id); |
72dba584b ida: implement id... |
1024 1025 1026 1027 1028 |
} EXPORT_SYMBOL(ida_remove); /** * ida_destroy - release all cached layers within an ida tree |
ea24ea850 idr: fix kernel-d... |
1029 |
* @ida: ida handle |
72dba584b ida: implement id... |
1030 1031 1032 1033 1034 1035 1036 1037 1038 |
*/ void ida_destroy(struct ida *ida) { idr_destroy(&ida->idr); kfree(ida->free_bitmap); } EXPORT_SYMBOL(ida_destroy); /** |
88eca0207 ida: simplified f... |
1039 1040 1041 1042 1043 1044 1045 1046 1047 |
* 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... |
1048 1049 1050 |
* 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... |
1051 1052 1053 1054 1055 1056 1057 |
* 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... |
1058 |
unsigned long flags; |
88eca0207 ida: simplified f... |
1059 1060 1061 1062 1063 1064 1065 1066 1067 1068 1069 1070 1071 1072 |
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... |
1073 |
spin_lock_irqsave(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
1074 1075 1076 1077 1078 1079 1080 1081 1082 |
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... |
1083 |
spin_unlock_irqrestore(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
1084 1085 1086 1087 1088 1089 1090 1091 1092 1093 1094 1095 |
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... |
1096 1097 1098 1099 1100 |
* * 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... |
1101 1102 1103 |
*/ void ida_simple_remove(struct ida *ida, unsigned int id) { |
46cbc1d39 ida: make ida_sim... |
1104 |
unsigned long flags; |
88eca0207 ida: simplified f... |
1105 |
BUG_ON((int)id < 0); |
46cbc1d39 ida: make ida_sim... |
1106 |
spin_lock_irqsave(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
1107 |
ida_remove(ida, id); |
46cbc1d39 ida: make ida_sim... |
1108 |
spin_unlock_irqrestore(&simple_ida_lock, flags); |
88eca0207 ida: simplified f... |
1109 1110 1111 1112 |
} EXPORT_SYMBOL(ida_simple_remove); /** |
72dba584b ida: implement id... |
1113 1114 1115 1116 1117 1118 1119 1120 1121 1122 1123 1124 1125 |
* ida_init - initialize ida handle * @ida: ida handle * * This function is use to set up the handle (@ida) that you will pass * to the rest of the functions. */ void ida_init(struct ida *ida) { memset(ida, 0, sizeof(struct ida)); idr_init(&ida->idr); } EXPORT_SYMBOL(ida_init); |