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