85 lines · plain
1.. SPDX-License-Identifier: GPL-2.0+2 3=============4ID Allocation5=============6 7:Author: Matthew Wilcox8 9Overview10========11 12A common problem to solve is allocating identifiers (IDs); generally13small numbers which identify a thing. Examples include file descriptors,14process IDs, packet identifiers in networking protocols, SCSI tags15and device instance numbers. The IDR and the IDA provide a reasonable16solution to the problem to avoid everybody inventing their own. The IDR17provides the ability to map an ID to a pointer, while the IDA provides18only 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 usage24=========25 26Start by initialising an IDR, either with DEFINE_IDR()27for statically allocated IDRs or idr_init() for dynamically28allocated IDRs.29 30You can call idr_alloc() to allocate an unused ID. Look up31the 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 call35idr_replace(). One common reason to do this is to reserve an36ID by passing a ``NULL`` pointer to the allocation function; initialise the37object with the reserved ID and finally insert the initialised object38into the IDR.39 40Some users need to allocate IDs larger than ``INT_MAX``. So far all of41these users have been content with a ``UINT_MAX`` limit, and they use42idr_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 use46idr_alloc_cyclic(). The IDR becomes less efficient when dealing47with larger IDs, so using this function comes at a slight cost.48 49To perform an action on all pointers used by the IDR, you can50either use the callback-based idr_for_each() or the51iterator-style idr_for_each_entry(). You may need to use52idr_for_each_entry_continue() to continue an iteration. You can53also 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 objects57pointed to from the IDR; if you want to do that, use one of the iterators58to do it.59 60You can use idr_is_empty() to find out whether there are any61IDs 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 lead65to the IDR being unable to allocate memory. To work around this,66you can call idr_preload() before taking the lock, and then67idr_preload_end() after the allocation.68 69.. kernel-doc:: include/linux/idr.h70 :doc: idr sync71 72IDA usage73=========74 75.. kernel-doc:: lib/idr.c76 :doc: IDA description77 78Functions and structures79========================80 81.. kernel-doc:: include/linux/idr.h82 :functions:83.. kernel-doc:: lib/idr.c84 :functions:85