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: 82