Documentation/core-api/idr.rst

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