]>
Commit | Line | Data |
---|---|---|
a309d5db | 1 | .. SPDX-License-Identifier: GPL-2.0+ |
ac665d94 MW |
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 | ||
ec8213f8 PM |
23 | Start by initialising an IDR, either with DEFINE_IDR() |
24 | for statically allocated IDRs or idr_init() for dynamically | |
ac665d94 MW |
25 | allocated IDRs. |
26 | ||
ec8213f8 PM |
27 | You can call idr_alloc() to allocate an unused ID. Look up |
28 | the pointer you associated with the ID by calling idr_find() | |
29 | and free the ID by calling idr_remove(). | |
ac665d94 MW |
30 | |
31 | If you need to change the pointer associated with an ID, you can call | |
ec8213f8 | 32 | idr_replace(). One common reason to do this is to reserve an |
ac665d94 MW |
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 | |
ec8213f8 | 39 | idr_alloc_u32(). If you need IDs that will not fit in a u32, |
ac665d94 MW |
40 | we will work with you to address your needs. |
41 | ||
42 | If you need to allocate IDs sequentially, you can use | |
ec8213f8 | 43 | idr_alloc_cyclic(). The IDR becomes less efficient when dealing |
ac665d94 MW |
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 | |
ec8213f8 PM |
47 | either use the callback-based idr_for_each() or the |
48 | iterator-style idr_for_each_entry(). You may need to use | |
49 | idr_for_each_entry_continue() to continue an iteration. You can | |
50 | also use idr_get_next() if the iterator doesn't fit your needs. | |
ac665d94 | 51 | |
ec8213f8 | 52 | When you have finished using an IDR, you can call idr_destroy() |
ac665d94 MW |
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 | ||
ec8213f8 | 57 | You can use idr_is_empty() to find out whether there are any |
ac665d94 MW |
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, | |
ec8213f8 PM |
63 | you can call idr_preload() before taking the lock, and then |
64 | idr_preload_end() after the allocation. | |
ac665d94 MW |
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 | |
5105730f | 79 | :functions: |
ac665d94 | 80 | .. kernel-doc:: lib/idr.c |
5105730f | 81 | :functions: |