idr.c 22 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406407408409410411412413414415416417418419420421422423424425426427428429430431432433434435436437438439440441442443444445446447448449450451452453454455456457458459460461462463464465466467468469470471472473474475476477478479480481482483484485486487488489490491492493494495496497498499500501502503504505506507508509510511512513514515516517518519520521522523524525526527528529530531532533534535536537538539540541542543544545546547548549550551552553554555556557558559560561562563564565566567568569570571572573574575576577578579580581582583584585586587588589590591592593594595596597598599600601602603604605606607608609610611612613614615616617618619620621622623624625626627628629630631632633634635636637638639640641642643644645646647648649650651652653654655656657658659660661662663664665666667668669670671672673674675676677678679680681682683684685686687688689690691692693694695696697698699700701702703704705706707708709710711712713714715716717718719720721722723724725726727728729730731732733734735736737738739740741742743744745746747748749750751752753754755756757758759760761762763764765766767768769770771772773774775776777778779780781782783784785786787788789790791792793794795796797798799800801802803804805806807808809810811812813814815816817818819820821822823824825826827828829830831832833834835836837838839840841842843844845846847848849850851852853854855856857858859860861862863864865866867868869870871872873874875876877878879880881882883884885886887888889890891892893894895896897898899900901902903904905906907908909910911912913914915916917918919920921922923924925926927928929930931932933934935936937938
  1. /*
  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. *
  9. * Modified by Nadia Derbey to make it RCU safe.
  10. *
  11. * Small id to pointer translation service.
  12. *
  13. * It uses a radix tree like structure as a sparse array indexed
  14. * by the id to obtain the pointer. The bitmap makes allocating
  15. * a new id quick.
  16. *
  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. * You can release ids at any time. When all ids are released, most of
  22. * the memory is returned (we keep IDR_FREE_MAX) in a local pool so we
  23. * don't need to go to the memory "store" during an id allocate, just
  24. * so you don't need to be too concerned about locking and conflicts
  25. * with the slab allocator.
  26. */
  27. #ifndef TEST // to test in user space...
  28. #include <linux/slab.h>
  29. #include <linux/init.h>
  30. #include <linux/module.h>
  31. #endif
  32. #include <linux/err.h>
  33. #include <linux/string.h>
  34. #include <linux/idr.h>
  35. static struct kmem_cache *idr_layer_cache;
  36. static struct idr_layer *get_from_free_list(struct idr *idp)
  37. {
  38. struct idr_layer *p;
  39. unsigned long flags;
  40. spin_lock_irqsave(&idp->lock, flags);
  41. if ((p = idp->id_free)) {
  42. idp->id_free = p->ary[0];
  43. idp->id_free_cnt--;
  44. p->ary[0] = NULL;
  45. }
  46. spin_unlock_irqrestore(&idp->lock, flags);
  47. return(p);
  48. }
  49. static void idr_layer_rcu_free(struct rcu_head *head)
  50. {
  51. struct idr_layer *layer;
  52. layer = container_of(head, struct idr_layer, rcu_head);
  53. kmem_cache_free(idr_layer_cache, layer);
  54. }
  55. static inline void free_layer(struct idr_layer *p)
  56. {
  57. call_rcu(&p->rcu_head, idr_layer_rcu_free);
  58. }
  59. /* only called when idp->lock is held */
  60. static void __move_to_free_list(struct idr *idp, struct idr_layer *p)
  61. {
  62. p->ary[0] = idp->id_free;
  63. idp->id_free = p;
  64. idp->id_free_cnt++;
  65. }
  66. static void move_to_free_list(struct idr *idp, struct idr_layer *p)
  67. {
  68. unsigned long flags;
  69. /*
  70. * Depends on the return element being zeroed.
  71. */
  72. spin_lock_irqsave(&idp->lock, flags);
  73. __move_to_free_list(idp, p);
  74. spin_unlock_irqrestore(&idp->lock, flags);
  75. }
  76. static void idr_mark_full(struct idr_layer **pa, int id)
  77. {
  78. struct idr_layer *p = pa[0];
  79. int l = 0;
  80. __set_bit(id & IDR_MASK, &p->bitmap);
  81. /*
  82. * If this layer is full mark the bit in the layer above to
  83. * show that this part of the radix tree is full. This may
  84. * complete the layer above and require walking up the radix
  85. * tree.
  86. */
  87. while (p->bitmap == IDR_FULL) {
  88. if (!(p = pa[++l]))
  89. break;
  90. id = id >> IDR_BITS;
  91. __set_bit((id & IDR_MASK), &p->bitmap);
  92. }
  93. }
  94. /**
  95. * idr_pre_get - reserver resources for idr allocation
  96. * @idp: idr handle
  97. * @gfp_mask: memory allocation flags
  98. *
  99. * This function should be called prior to locking and calling the
  100. * idr_get_new* functions. It preallocates enough memory to satisfy
  101. * the worst possible allocation.
  102. *
  103. * If the system is REALLY out of memory this function returns 0,
  104. * otherwise 1.
  105. */
  106. int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
  107. {
  108. while (idp->id_free_cnt < IDR_FREE_MAX) {
  109. struct idr_layer *new;
  110. new = kmem_cache_zalloc(idr_layer_cache, gfp_mask);
  111. if (new == NULL)
  112. return (0);
  113. move_to_free_list(idp, new);
  114. }
  115. return 1;
  116. }
  117. EXPORT_SYMBOL(idr_pre_get);
  118. static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
  119. {
  120. int n, m, sh;
  121. struct idr_layer *p, *new;
  122. int l, id, oid;
  123. unsigned long bm;
  124. id = *starting_id;
  125. restart:
  126. p = idp->top;
  127. l = idp->layers;
  128. pa[l--] = NULL;
  129. while (1) {
  130. /*
  131. * We run around this while until we reach the leaf node...
  132. */
  133. n = (id >> (IDR_BITS*l)) & IDR_MASK;
  134. bm = ~p->bitmap;
  135. m = find_next_bit(&bm, IDR_SIZE, n);
  136. if (m == IDR_SIZE) {
  137. /* no space available go back to previous layer. */
  138. l++;
  139. oid = id;
  140. id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
  141. /* if already at the top layer, we need to grow */
  142. if (id >= 1 << (idp->layers * IDR_BITS)) {
  143. *starting_id = id;
  144. return IDR_NEED_TO_GROW;
  145. }
  146. p = pa[l];
  147. BUG_ON(!p);
  148. /* If we need to go up one layer, continue the
  149. * loop; otherwise, restart from the top.
  150. */
  151. sh = IDR_BITS * (l + 1);
  152. if (oid >> sh == id >> sh)
  153. continue;
  154. else
  155. goto restart;
  156. }
  157. if (m != n) {
  158. sh = IDR_BITS*l;
  159. id = ((id >> sh) ^ n ^ m) << sh;
  160. }
  161. if ((id >= MAX_ID_BIT) || (id < 0))
  162. return IDR_NOMORE_SPACE;
  163. if (l == 0)
  164. break;
  165. /*
  166. * Create the layer below if it is missing.
  167. */
  168. if (!p->ary[m]) {
  169. new = get_from_free_list(idp);
  170. if (!new)
  171. return -1;
  172. new->layer = l-1;
  173. rcu_assign_pointer(p->ary[m], new);
  174. p->count++;
  175. }
  176. pa[l--] = p;
  177. p = p->ary[m];
  178. }
  179. pa[l] = p;
  180. return id;
  181. }
  182. static int idr_get_empty_slot(struct idr *idp, int starting_id,
  183. struct idr_layer **pa)
  184. {
  185. struct idr_layer *p, *new;
  186. int layers, v, id;
  187. unsigned long flags;
  188. id = starting_id;
  189. build_up:
  190. p = idp->top;
  191. layers = idp->layers;
  192. if (unlikely(!p)) {
  193. if (!(p = get_from_free_list(idp)))
  194. return -1;
  195. p->layer = 0;
  196. layers = 1;
  197. }
  198. /*
  199. * Add a new layer to the top of the tree if the requested
  200. * id is larger than the currently allocated space.
  201. */
  202. while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
  203. layers++;
  204. if (!p->count) {
  205. /* special case: if the tree is currently empty,
  206. * then we grow the tree by moving the top node
  207. * upwards.
  208. */
  209. p->layer++;
  210. continue;
  211. }
  212. if (!(new = get_from_free_list(idp))) {
  213. /*
  214. * The allocation failed. If we built part of
  215. * the structure tear it down.
  216. */
  217. spin_lock_irqsave(&idp->lock, flags);
  218. for (new = p; p && p != idp->top; new = p) {
  219. p = p->ary[0];
  220. new->ary[0] = NULL;
  221. new->bitmap = new->count = 0;
  222. __move_to_free_list(idp, new);
  223. }
  224. spin_unlock_irqrestore(&idp->lock, flags);
  225. return -1;
  226. }
  227. new->ary[0] = p;
  228. new->count = 1;
  229. new->layer = layers-1;
  230. if (p->bitmap == IDR_FULL)
  231. __set_bit(0, &new->bitmap);
  232. p = new;
  233. }
  234. rcu_assign_pointer(idp->top, p);
  235. idp->layers = layers;
  236. v = sub_alloc(idp, &id, pa);
  237. if (v == IDR_NEED_TO_GROW)
  238. goto build_up;
  239. return(v);
  240. }
  241. static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
  242. {
  243. struct idr_layer *pa[MAX_LEVEL];
  244. int id;
  245. id = idr_get_empty_slot(idp, starting_id, pa);
  246. if (id >= 0) {
  247. /*
  248. * Successfully found an empty slot. Install the user
  249. * pointer and mark the slot full.
  250. */
  251. rcu_assign_pointer(pa[0]->ary[id & IDR_MASK],
  252. (struct idr_layer *)ptr);
  253. pa[0]->count++;
  254. idr_mark_full(pa, id);
  255. }
  256. return id;
  257. }
  258. /**
  259. * idr_get_new_above - allocate new idr entry above or equal to a start id
  260. * @idp: idr handle
  261. * @ptr: pointer you want associated with the id
  262. * @starting_id: id to start search at
  263. * @id: pointer to the allocated handle
  264. *
  265. * This is the allocate id function. It should be called with any
  266. * required locks.
  267. *
  268. * If memory is required, it will return -EAGAIN, you should unlock
  269. * and go back to the idr_pre_get() call. If the idr is full, it will
  270. * return -ENOSPC.
  271. *
  272. * @id returns a value in the range @starting_id ... 0x7fffffff
  273. */
  274. int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
  275. {
  276. int rv;
  277. rv = idr_get_new_above_int(idp, ptr, starting_id);
  278. /*
  279. * This is a cheap hack until the IDR code can be fixed to
  280. * return proper error values.
  281. */
  282. if (rv < 0)
  283. return _idr_rc_to_errno(rv);
  284. *id = rv;
  285. return 0;
  286. }
  287. EXPORT_SYMBOL(idr_get_new_above);
  288. /**
  289. * idr_get_new - allocate new idr entry
  290. * @idp: idr handle
  291. * @ptr: pointer you want associated with the id
  292. * @id: pointer to the allocated handle
  293. *
  294. * This is the allocate id function. It should be called with any
  295. * required locks.
  296. *
  297. * If memory is required, it will return -EAGAIN, you should unlock
  298. * and go back to the idr_pre_get() call. If the idr is full, it will
  299. * return -ENOSPC.
  300. *
  301. * @id returns a value in the range 0 ... 0x7fffffff
  302. */
  303. int idr_get_new(struct idr *idp, void *ptr, int *id)
  304. {
  305. int rv;
  306. rv = idr_get_new_above_int(idp, ptr, 0);
  307. /*
  308. * This is a cheap hack until the IDR code can be fixed to
  309. * return proper error values.
  310. */
  311. if (rv < 0)
  312. return _idr_rc_to_errno(rv);
  313. *id = rv;
  314. return 0;
  315. }
  316. EXPORT_SYMBOL(idr_get_new);
  317. static void idr_remove_warning(int id)
  318. {
  319. printk(KERN_WARNING
  320. "idr_remove called for id=%d which is not allocated.\n", id);
  321. dump_stack();
  322. }
  323. static void sub_remove(struct idr *idp, int shift, int id)
  324. {
  325. struct idr_layer *p = idp->top;
  326. struct idr_layer **pa[MAX_LEVEL];
  327. struct idr_layer ***paa = &pa[0];
  328. struct idr_layer *to_free;
  329. int n;
  330. *paa = NULL;
  331. *++paa = &idp->top;
  332. while ((shift > 0) && p) {
  333. n = (id >> shift) & IDR_MASK;
  334. __clear_bit(n, &p->bitmap);
  335. *++paa = &p->ary[n];
  336. p = p->ary[n];
  337. shift -= IDR_BITS;
  338. }
  339. n = id & IDR_MASK;
  340. if (likely(p != NULL && test_bit(n, &p->bitmap))){
  341. __clear_bit(n, &p->bitmap);
  342. rcu_assign_pointer(p->ary[n], NULL);
  343. to_free = NULL;
  344. while(*paa && ! --((**paa)->count)){
  345. if (to_free)
  346. free_layer(to_free);
  347. to_free = **paa;
  348. **paa-- = NULL;
  349. }
  350. if (!*paa)
  351. idp->layers = 0;
  352. if (to_free)
  353. free_layer(to_free);
  354. } else
  355. idr_remove_warning(id);
  356. }
  357. /**
  358. * idr_remove - remove the given id and free it's slot
  359. * @idp: idr handle
  360. * @id: unique key
  361. */
  362. void idr_remove(struct idr *idp, int id)
  363. {
  364. struct idr_layer *p;
  365. struct idr_layer *to_free;
  366. /* Mask off upper bits we don't use for the search. */
  367. id &= MAX_ID_MASK;
  368. sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
  369. if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
  370. idp->top->ary[0]) {
  371. /*
  372. * Single child at leftmost slot: we can shrink the tree.
  373. * This level is not needed anymore since when layers are
  374. * inserted, they are inserted at the top of the existing
  375. * tree.
  376. */
  377. to_free = idp->top;
  378. p = idp->top->ary[0];
  379. rcu_assign_pointer(idp->top, p);
  380. --idp->layers;
  381. to_free->bitmap = to_free->count = 0;
  382. free_layer(to_free);
  383. }
  384. while (idp->id_free_cnt >= IDR_FREE_MAX) {
  385. p = get_from_free_list(idp);
  386. /*
  387. * Note: we don't call the rcu callback here, since the only
  388. * layers that fall into the freelist are those that have been
  389. * preallocated.
  390. */
  391. kmem_cache_free(idr_layer_cache, p);
  392. }
  393. return;
  394. }
  395. EXPORT_SYMBOL(idr_remove);
  396. /**
  397. * idr_remove_all - remove all ids from the given idr tree
  398. * @idp: idr handle
  399. *
  400. * idr_destroy() only frees up unused, cached idp_layers, but this
  401. * function will remove all id mappings and leave all idp_layers
  402. * unused.
  403. *
  404. * A typical clean-up sequence for objects stored in an idr tree, will
  405. * use idr_for_each() to free all objects, if necessay, then
  406. * idr_remove_all() to remove all ids, and idr_destroy() to free
  407. * up the cached idr_layers.
  408. */
  409. void idr_remove_all(struct idr *idp)
  410. {
  411. int n, id, max;
  412. int bt_mask;
  413. struct idr_layer *p;
  414. struct idr_layer *pa[MAX_LEVEL];
  415. struct idr_layer **paa = &pa[0];
  416. n = idp->layers * IDR_BITS;
  417. p = idp->top;
  418. rcu_assign_pointer(idp->top, NULL);
  419. max = 1 << n;
  420. id = 0;
  421. while (id < max) {
  422. while (n > IDR_BITS && p) {
  423. n -= IDR_BITS;
  424. *paa++ = p;
  425. p = p->ary[(id >> n) & IDR_MASK];
  426. }
  427. bt_mask = id;
  428. id += 1 << n;
  429. /* Get the highest bit that the above add changed from 0->1. */
  430. while (n < fls(id ^ bt_mask)) {
  431. if (p)
  432. free_layer(p);
  433. n += IDR_BITS;
  434. p = *--paa;
  435. }
  436. }
  437. idp->layers = 0;
  438. }
  439. EXPORT_SYMBOL(idr_remove_all);
  440. /**
  441. * idr_destroy - release all cached layers within an idr tree
  442. * @idp: idr handle
  443. */
  444. void idr_destroy(struct idr *idp)
  445. {
  446. while (idp->id_free_cnt) {
  447. struct idr_layer *p = get_from_free_list(idp);
  448. kmem_cache_free(idr_layer_cache, p);
  449. }
  450. }
  451. EXPORT_SYMBOL(idr_destroy);
  452. /**
  453. * idr_find - return pointer for given id
  454. * @idp: idr handle
  455. * @id: lookup key
  456. *
  457. * Return the pointer given the id it has been registered with. A %NULL
  458. * return indicates that @id is not valid or you passed %NULL in
  459. * idr_get_new().
  460. *
  461. * This function can be called under rcu_read_lock(), given that the leaf
  462. * pointers lifetimes are correctly managed.
  463. */
  464. void *idr_find(struct idr *idp, int id)
  465. {
  466. int n;
  467. struct idr_layer *p;
  468. p = rcu_dereference_raw(idp->top);
  469. if (!p)
  470. return NULL;
  471. n = (p->layer+1) * IDR_BITS;
  472. /* Mask off upper bits we don't use for the search. */
  473. id &= MAX_ID_MASK;
  474. if (id >= (1 << n))
  475. return NULL;
  476. BUG_ON(n == 0);
  477. while (n > 0 && p) {
  478. n -= IDR_BITS;
  479. BUG_ON(n != p->layer*IDR_BITS);
  480. p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
  481. }
  482. return((void *)p);
  483. }
  484. EXPORT_SYMBOL(idr_find);
  485. /**
  486. * idr_for_each - iterate through all stored pointers
  487. * @idp: idr handle
  488. * @fn: function to be called for each pointer
  489. * @data: data passed back to callback function
  490. *
  491. * Iterate over the pointers registered with the given idr. The
  492. * callback function will be called for each pointer currently
  493. * registered, passing the id, the pointer and the data pointer passed
  494. * to this function. It is not safe to modify the idr tree while in
  495. * the callback, so functions such as idr_get_new and idr_remove are
  496. * not allowed.
  497. *
  498. * We check the return of @fn each time. If it returns anything other
  499. * than 0, we break out and return that value.
  500. *
  501. * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
  502. */
  503. int idr_for_each(struct idr *idp,
  504. int (*fn)(int id, void *p, void *data), void *data)
  505. {
  506. int n, id, max, error = 0;
  507. struct idr_layer *p;
  508. struct idr_layer *pa[MAX_LEVEL];
  509. struct idr_layer **paa = &pa[0];
  510. n = idp->layers * IDR_BITS;
  511. p = rcu_dereference_raw(idp->top);
  512. max = 1 << n;
  513. id = 0;
  514. while (id < max) {
  515. while (n > 0 && p) {
  516. n -= IDR_BITS;
  517. *paa++ = p;
  518. p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
  519. }
  520. if (p) {
  521. error = fn(id, (void *)p, data);
  522. if (error)
  523. break;
  524. }
  525. id += 1 << n;
  526. while (n < fls(id)) {
  527. n += IDR_BITS;
  528. p = *--paa;
  529. }
  530. }
  531. return error;
  532. }
  533. EXPORT_SYMBOL(idr_for_each);
  534. /**
  535. * idr_get_next - lookup next object of id to given id.
  536. * @idp: idr handle
  537. * @nextidp: pointer to lookup key
  538. *
  539. * Returns pointer to registered object with id, which is next number to
  540. * given id. After being looked up, *@nextidp will be updated for the next
  541. * iteration.
  542. */
  543. void *idr_get_next(struct idr *idp, int *nextidp)
  544. {
  545. struct idr_layer *p, *pa[MAX_LEVEL];
  546. struct idr_layer **paa = &pa[0];
  547. int id = *nextidp;
  548. int n, max;
  549. /* find first ent */
  550. n = idp->layers * IDR_BITS;
  551. max = 1 << n;
  552. p = rcu_dereference_raw(idp->top);
  553. if (!p)
  554. return NULL;
  555. while (id < max) {
  556. while (n > 0 && p) {
  557. n -= IDR_BITS;
  558. *paa++ = p;
  559. p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
  560. }
  561. if (p) {
  562. *nextidp = id;
  563. return p;
  564. }
  565. id += 1 << n;
  566. while (n < fls(id)) {
  567. n += IDR_BITS;
  568. p = *--paa;
  569. }
  570. }
  571. return NULL;
  572. }
  573. EXPORT_SYMBOL(idr_get_next);
  574. /**
  575. * idr_replace - replace pointer for given id
  576. * @idp: idr handle
  577. * @ptr: pointer you want associated with the id
  578. * @id: lookup key
  579. *
  580. * Replace the pointer registered with an id and return the old value.
  581. * A -ENOENT return indicates that @id was not found.
  582. * A -EINVAL return indicates that @id was not within valid constraints.
  583. *
  584. * The caller must serialize with writers.
  585. */
  586. void *idr_replace(struct idr *idp, void *ptr, int id)
  587. {
  588. int n;
  589. struct idr_layer *p, *old_p;
  590. p = idp->top;
  591. if (!p)
  592. return ERR_PTR(-EINVAL);
  593. n = (p->layer+1) * IDR_BITS;
  594. id &= MAX_ID_MASK;
  595. if (id >= (1 << n))
  596. return ERR_PTR(-EINVAL);
  597. n -= IDR_BITS;
  598. while ((n > 0) && p) {
  599. p = p->ary[(id >> n) & IDR_MASK];
  600. n -= IDR_BITS;
  601. }
  602. n = id & IDR_MASK;
  603. if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
  604. return ERR_PTR(-ENOENT);
  605. old_p = p->ary[n];
  606. rcu_assign_pointer(p->ary[n], ptr);
  607. return old_p;
  608. }
  609. EXPORT_SYMBOL(idr_replace);
  610. void __init idr_init_cache(void)
  611. {
  612. idr_layer_cache = kmem_cache_create("idr_layer_cache",
  613. sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
  614. }
  615. /**
  616. * idr_init - initialize idr handle
  617. * @idp: idr handle
  618. *
  619. * This function is use to set up the handle (@idp) that you will pass
  620. * to the rest of the functions.
  621. */
  622. void idr_init(struct idr *idp)
  623. {
  624. memset(idp, 0, sizeof(struct idr));
  625. spin_lock_init(&idp->lock);
  626. }
  627. EXPORT_SYMBOL(idr_init);
  628. /*
  629. * IDA - IDR based ID allocator
  630. *
  631. * this is id allocator without id -> pointer translation. Memory
  632. * usage is much lower than full blown idr because each id only
  633. * occupies a bit. ida uses a custom leaf node which contains
  634. * IDA_BITMAP_BITS slots.
  635. *
  636. * 2007-04-25 written by Tejun Heo <htejun@gmail.com>
  637. */
  638. static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
  639. {
  640. unsigned long flags;
  641. if (!ida->free_bitmap) {
  642. spin_lock_irqsave(&ida->idr.lock, flags);
  643. if (!ida->free_bitmap) {
  644. ida->free_bitmap = bitmap;
  645. bitmap = NULL;
  646. }
  647. spin_unlock_irqrestore(&ida->idr.lock, flags);
  648. }
  649. kfree(bitmap);
  650. }
  651. /**
  652. * ida_pre_get - reserve resources for ida allocation
  653. * @ida: ida handle
  654. * @gfp_mask: memory allocation flag
  655. *
  656. * This function should be called prior to locking and calling the
  657. * following function. It preallocates enough memory to satisfy the
  658. * worst possible allocation.
  659. *
  660. * If the system is REALLY out of memory this function returns 0,
  661. * otherwise 1.
  662. */
  663. int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
  664. {
  665. /* allocate idr_layers */
  666. if (!idr_pre_get(&ida->idr, gfp_mask))
  667. return 0;
  668. /* allocate free_bitmap */
  669. if (!ida->free_bitmap) {
  670. struct ida_bitmap *bitmap;
  671. bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
  672. if (!bitmap)
  673. return 0;
  674. free_bitmap(ida, bitmap);
  675. }
  676. return 1;
  677. }
  678. EXPORT_SYMBOL(ida_pre_get);
  679. /**
  680. * ida_get_new_above - allocate new ID above or equal to a start id
  681. * @ida: ida handle
  682. * @starting_id: id to start search at
  683. * @p_id: pointer to the allocated handle
  684. *
  685. * Allocate new ID above or equal to @ida. It should be called with
  686. * any required locks.
  687. *
  688. * If memory is required, it will return -EAGAIN, you should unlock
  689. * and go back to the ida_pre_get() call. If the ida is full, it will
  690. * return -ENOSPC.
  691. *
  692. * @p_id returns a value in the range @starting_id ... 0x7fffffff.
  693. */
  694. int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
  695. {
  696. struct idr_layer *pa[MAX_LEVEL];
  697. struct ida_bitmap *bitmap;
  698. unsigned long flags;
  699. int idr_id = starting_id / IDA_BITMAP_BITS;
  700. int offset = starting_id % IDA_BITMAP_BITS;
  701. int t, id;
  702. restart:
  703. /* get vacant slot */
  704. t = idr_get_empty_slot(&ida->idr, idr_id, pa);
  705. if (t < 0)
  706. return _idr_rc_to_errno(t);
  707. if (t * IDA_BITMAP_BITS >= MAX_ID_BIT)
  708. return -ENOSPC;
  709. if (t != idr_id)
  710. offset = 0;
  711. idr_id = t;
  712. /* if bitmap isn't there, create a new one */
  713. bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
  714. if (!bitmap) {
  715. spin_lock_irqsave(&ida->idr.lock, flags);
  716. bitmap = ida->free_bitmap;
  717. ida->free_bitmap = NULL;
  718. spin_unlock_irqrestore(&ida->idr.lock, flags);
  719. if (!bitmap)
  720. return -EAGAIN;
  721. memset(bitmap, 0, sizeof(struct ida_bitmap));
  722. rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
  723. (void *)bitmap);
  724. pa[0]->count++;
  725. }
  726. /* lookup for empty slot */
  727. t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
  728. if (t == IDA_BITMAP_BITS) {
  729. /* no empty slot after offset, continue to the next chunk */
  730. idr_id++;
  731. offset = 0;
  732. goto restart;
  733. }
  734. id = idr_id * IDA_BITMAP_BITS + t;
  735. if (id >= MAX_ID_BIT)
  736. return -ENOSPC;
  737. __set_bit(t, bitmap->bitmap);
  738. if (++bitmap->nr_busy == IDA_BITMAP_BITS)
  739. idr_mark_full(pa, idr_id);
  740. *p_id = id;
  741. /* Each leaf node can handle nearly a thousand slots and the
  742. * whole idea of ida is to have small memory foot print.
  743. * Throw away extra resources one by one after each successful
  744. * allocation.
  745. */
  746. if (ida->idr.id_free_cnt || ida->free_bitmap) {
  747. struct idr_layer *p = get_from_free_list(&ida->idr);
  748. if (p)
  749. kmem_cache_free(idr_layer_cache, p);
  750. }
  751. return 0;
  752. }
  753. EXPORT_SYMBOL(ida_get_new_above);
  754. /**
  755. * ida_get_new - allocate new ID
  756. * @ida: idr handle
  757. * @p_id: pointer to the allocated handle
  758. *
  759. * Allocate new ID. It should be called with any required locks.
  760. *
  761. * If memory is required, it will return -EAGAIN, you should unlock
  762. * and go back to the idr_pre_get() call. If the idr is full, it will
  763. * return -ENOSPC.
  764. *
  765. * @id returns a value in the range 0 ... 0x7fffffff.
  766. */
  767. int ida_get_new(struct ida *ida, int *p_id)
  768. {
  769. return ida_get_new_above(ida, 0, p_id);
  770. }
  771. EXPORT_SYMBOL(ida_get_new);
  772. /**
  773. * ida_remove - remove the given ID
  774. * @ida: ida handle
  775. * @id: ID to free
  776. */
  777. void ida_remove(struct ida *ida, int id)
  778. {
  779. struct idr_layer *p = ida->idr.top;
  780. int shift = (ida->idr.layers - 1) * IDR_BITS;
  781. int idr_id = id / IDA_BITMAP_BITS;
  782. int offset = id % IDA_BITMAP_BITS;
  783. int n;
  784. struct ida_bitmap *bitmap;
  785. /* clear full bits while looking up the leaf idr_layer */
  786. while ((shift > 0) && p) {
  787. n = (idr_id >> shift) & IDR_MASK;
  788. __clear_bit(n, &p->bitmap);
  789. p = p->ary[n];
  790. shift -= IDR_BITS;
  791. }
  792. if (p == NULL)
  793. goto err;
  794. n = idr_id & IDR_MASK;
  795. __clear_bit(n, &p->bitmap);
  796. bitmap = (void *)p->ary[n];
  797. if (!test_bit(offset, bitmap->bitmap))
  798. goto err;
  799. /* update bitmap and remove it if empty */
  800. __clear_bit(offset, bitmap->bitmap);
  801. if (--bitmap->nr_busy == 0) {
  802. __set_bit(n, &p->bitmap); /* to please idr_remove() */
  803. idr_remove(&ida->idr, idr_id);
  804. free_bitmap(ida, bitmap);
  805. }
  806. return;
  807. err:
  808. printk(KERN_WARNING
  809. "ida_remove called for id=%d which is not allocated.\n", id);
  810. }
  811. EXPORT_SYMBOL(ida_remove);
  812. /**
  813. * ida_destroy - release all cached layers within an ida tree
  814. * @ida: ida handle
  815. */
  816. void ida_destroy(struct ida *ida)
  817. {
  818. idr_destroy(&ida->idr);
  819. kfree(ida->free_bitmap);
  820. }
  821. EXPORT_SYMBOL(ida_destroy);
  822. /**
  823. * ida_init - initialize ida handle
  824. * @ida: ida handle
  825. *
  826. * This function is use to set up the handle (@ida) that you will pass
  827. * to the rest of the functions.
  828. */
  829. void ida_init(struct ida *ida)
  830. {
  831. memset(ida, 0, sizeof(struct ida));
  832. idr_init(&ida->idr);
  833. }
  834. EXPORT_SYMBOL(ida_init);