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

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