0001 .. SPDX-License-Identifier: GPL-2.0+
0002
0003 =============
0004 ID Allocation
0005 =============
0006
0007 :Author: Matthew Wilcox
0008
0009 Overview
0010 ========
0011
0012 A common problem to solve is allocating identifiers (IDs); generally
0013 small numbers which identify a thing. Examples include file descriptors,
0014 process IDs, packet identifiers in networking protocols, SCSI tags
0015 and device instance numbers. The IDR and the IDA provide a reasonable
0016 solution to the problem to avoid everybody inventing their own. The IDR
0017 provides the ability to map an ID to a pointer, while the IDA provides
0018 only ID allocation, and as a result is much more memory-efficient.
0019
0020 The IDR interface is deprecated; please use the :doc:`XArray <xarray>`
0021 instead.
0022
0023 IDR usage
0024 =========
0025
0026 Start by initialising an IDR, either with DEFINE_IDR()
0027 for statically allocated IDRs or idr_init() for dynamically
0028 allocated IDRs.
0029
0030 You can call idr_alloc() to allocate an unused ID. Look up
0031 the pointer you associated with the ID by calling idr_find()
0032 and free the ID by calling idr_remove().
0033
0034 If you need to change the pointer associated with an ID, you can call
0035 idr_replace(). One common reason to do this is to reserve an
0036 ID by passing a ``NULL`` pointer to the allocation function; initialise the
0037 object with the reserved ID and finally insert the initialised object
0038 into the IDR.
0039
0040 Some users need to allocate IDs larger than ``INT_MAX``. So far all of
0041 these users have been content with a ``UINT_MAX`` limit, and they use
0042 idr_alloc_u32(). If you need IDs that will not fit in a u32,
0043 we will work with you to address your needs.
0044
0045 If you need to allocate IDs sequentially, you can use
0046 idr_alloc_cyclic(). The IDR becomes less efficient when dealing
0047 with larger IDs, so using this function comes at a slight cost.
0048
0049 To perform an action on all pointers used by the IDR, you can
0050 either use the callback-based idr_for_each() or the
0051 iterator-style idr_for_each_entry(). You may need to use
0052 idr_for_each_entry_continue() to continue an iteration. You can
0053 also use idr_get_next() if the iterator doesn't fit your needs.
0054
0055 When you have finished using an IDR, you can call idr_destroy()
0056 to release the memory used by the IDR. This will not free the objects
0057 pointed to from the IDR; if you want to do that, use one of the iterators
0058 to do it.
0059
0060 You can use idr_is_empty() to find out whether there are any
0061 IDs currently allocated.
0062
0063 If you need to take a lock while allocating a new ID from the IDR,
0064 you may need to pass a restrictive set of GFP flags, which can lead
0065 to the IDR being unable to allocate memory. To work around this,
0066 you can call idr_preload() before taking the lock, and then
0067 idr_preload_end() after the allocation.
0068
0069 .. kernel-doc:: include/linux/idr.h
0070 :doc: idr sync
0071
0072 IDA usage
0073 =========
0074
0075 .. kernel-doc:: lib/idr.c
0076 :doc: IDA description
0077
0078 Functions and structures
0079 ========================
0080
0081 .. kernel-doc:: include/linux/idr.h
0082 :functions:
0083 .. kernel-doc:: lib/idr.c
0084 :functions:
