idr.rst 2.8 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081
  1. .. SPDX-License-Identifier: GPL-2.0+
  2. =============
  3. ID Allocation
  4. =============
  5. :Author: Matthew Wilcox
  6. Overview
  7. ========
  8. A common problem to solve is allocating identifiers (IDs); generally
  9. small numbers which identify a thing. Examples include file descriptors,
  10. process IDs, packet identifiers in networking protocols, SCSI tags
  11. and device instance numbers. The IDR and the IDA provide a reasonable
  12. solution to the problem to avoid everybody inventing their own. The IDR
  13. provides the ability to map an ID to a pointer, while the IDA provides
  14. only ID allocation, and as a result is much more memory-efficient.
  15. IDR usage
  16. =========
  17. Start by initialising an IDR, either with DEFINE_IDR()
  18. for statically allocated IDRs or idr_init() for dynamically
  19. allocated IDRs.
  20. You can call idr_alloc() to allocate an unused ID. Look up
  21. the pointer you associated with the ID by calling idr_find()
  22. and free the ID by calling idr_remove().
  23. If you need to change the pointer associated with an ID, you can call
  24. idr_replace(). One common reason to do this is to reserve an
  25. ID by passing a ``NULL`` pointer to the allocation function; initialise the
  26. object with the reserved ID and finally insert the initialised object
  27. into the IDR.
  28. Some users need to allocate IDs larger than ``INT_MAX``. So far all of
  29. these users have been content with a ``UINT_MAX`` limit, and they use
  30. idr_alloc_u32(). If you need IDs that will not fit in a u32,
  31. we will work with you to address your needs.
  32. If you need to allocate IDs sequentially, you can use
  33. idr_alloc_cyclic(). The IDR becomes less efficient when dealing
  34. with larger IDs, so using this function comes at a slight cost.
  35. To perform an action on all pointers used by the IDR, you can
  36. either use the callback-based idr_for_each() or the
  37. iterator-style idr_for_each_entry(). You may need to use
  38. idr_for_each_entry_continue() to continue an iteration. You can
  39. also use idr_get_next() if the iterator doesn't fit your needs.
  40. When you have finished using an IDR, you can call idr_destroy()
  41. to release the memory used by the IDR. This will not free the objects
  42. pointed to from the IDR; if you want to do that, use one of the iterators
  43. to do it.
  44. You can use idr_is_empty() to find out whether there are any
  45. IDs currently allocated.
  46. If you need to take a lock while allocating a new ID from the IDR,
  47. you may need to pass a restrictive set of GFP flags, which can lead
  48. to the IDR being unable to allocate memory. To work around this,
  49. you can call idr_preload() before taking the lock, and then
  50. idr_preload_end() after the allocation.
  51. .. kernel-doc:: include/linux/idr.h
  52. :doc: idr sync
  53. IDA usage
  54. =========
  55. .. kernel-doc:: lib/idr.c
  56. :doc: IDA description
  57. Functions and structures
  58. ========================
  59. .. kernel-doc:: include/linux/idr.h
  60. :functions:
  61. .. kernel-doc:: lib/idr.c
  62. :functions: