ID Allocation

Author:

Matthew Wilcox

Overview

A common problem to solve is allocating identifiers (IDs); generallysmall numbers which identify a thing. Examples include file descriptors,process IDs, packet identifiers in networking protocols, SCSI tagsand device instance numbers. The IDR and the IDA provide a reasonablesolution to the problem to avoid everybody inventing their own. The IDRprovides the ability to map an ID to a pointer, while the IDA providesonly ID allocation, and as a result is much more memory-efficient.

The IDR interface is deprecated; please use theXArrayinstead.

IDR usage

Start by initialising an IDR, either withDEFINE_IDR()for statically allocated IDRs oridr_init() for dynamicallyallocated IDRs.

You can callidr_alloc() to allocate an unused ID. Look upthe pointer you associated with the ID by callingidr_find()and free the ID by callingidr_remove().

If you need to change the pointer associated with an ID, you can callidr_replace(). One common reason to do this is to reserve anID by passing aNULL pointer to the allocation function; initialise theobject with the reserved ID and finally insert the initialised objectinto the IDR.

Some users need to allocate IDs larger thanINT_MAX. So far all ofthese users have been content with aUINT_MAX limit, and they useidr_alloc_u32(). If you need IDs that will not fit in a u32,we will work with you to address your needs.

If you need to allocate IDs sequentially, you can useidr_alloc_cyclic(). The IDR becomes less efficient when dealingwith larger IDs, so using this function comes at a slight cost.

To perform an action on all pointers used by the IDR, you caneither use the callback-basedidr_for_each() or theiterator-styleidr_for_each_entry(). You may need to useidr_for_each_entry_continue() to continue an iteration. You canalso useidr_get_next() if the iterator doesn’t fit your needs.

When you have finished using an IDR, you can callidr_destroy()to release the memory used by the IDR. This will not free the objectspointed to from the IDR; if you want to do that, use one of the iteratorsto do it.

You can useidr_is_empty() to find out whether there are anyIDs currently allocated.

If you need to take a lock while allocating a new ID from the IDR,you may need to pass a restrictive set of GFP flags, which can leadto the IDR being unable to allocate memory. To work around this,you can callidr_preload() before taking the lock, and thenidr_preload_end() after the allocation.

idr synchronization (stolen from radix-tree.h)

idr_find() is able to be called locklessly, using RCU. The caller mustensure calls to this function are made withinrcu_read_lock() regions.Other readers (lock-free or otherwise) and modifications may be runningconcurrently.

It is still required that the caller manage the synchronization andlifetimes of the items. So if RCU lock-free lookups are used, typicallythis would mean that the items have their own locks, or are amenable tolock-free access; and that the items are freed by RCU (or only freed afterhaving been deleted from the idr treeand asynchronize_rcu() graceperiod).

IDA usage

The IDA is an ID allocator which does not provide the ability toassociate an ID with a pointer. As such, it only needs to store onebit per ID, and so is more space efficient than an IDR. To use an IDA,define it usingDEFINE_IDA() (or embed astructida in a data structure,then initialise it usingida_init()). To allocate a new ID, callida_alloc(),ida_alloc_min(),ida_alloc_max() orida_alloc_range().To free an ID, callida_free().

ida_destroy() can be used to dispose of an IDA without needing tofree the individual IDs in it. You can useida_is_empty() to findout whether the IDA has any IDs currently allocated.

The IDA handles its own locking. It is safe to call any of the IDAfunctions without synchronisation in your code.

IDs are currently limited to the range [0-INT_MAX]. If this is an awkwardlimitation, it should be quite straightforward to raise the maximum.

Functions and structures

IDR_INIT

IDR_INIT(name)

Initialise an IDR.

Parameters

name

Name of IDR.

Description

A freshly-initialised IDR contains no IDs.

DEFINE_IDR

DEFINE_IDR(name)

Define a statically-allocated IDR.

Parameters

name

Name of IDR.

Description

An IDR defined using this macro is ready for use with no additionalinitialisation required. It contains no IDs.

unsignedintidr_get_cursor(conststructidr*idr)

Return the current position of the cyclic allocator

Parameters

conststructidr*idr

idr handle

Description

The value returned is the value that will be next returned fromidr_alloc_cyclic() if it is free (otherwise the search will start fromthis position).

voididr_set_cursor(structidr*idr,unsignedintval)

Set the current position of the cyclic allocator

Parameters

structidr*idr

idr handle

unsignedintval

new position

Description

The next call toidr_alloc_cyclic() will returnval if it is free(otherwise the search will start from this position).

voididr_init_base(structidr*idr,intbase)

Initialise an IDR.

Parameters

structidr*idr

IDR handle.

intbase

The base value for the IDR.

Description

This variation ofidr_init() creates an IDR which will allocate IDsstarting atbase.

voididr_init(structidr*idr)

Initialise an IDR.

Parameters

structidr*idr

IDR handle.

Description

Initialise a dynamically allocated IDR. To initialise astatically allocated IDR, useDEFINE_IDR().

boolidr_is_empty(conststructidr*idr)

Are there any IDs allocated?

Parameters

conststructidr*idr

IDR handle.

Return

true if any IDs have been allocated from this IDR.

voididr_preload_end(void)

end preload section started withidr_preload()

Parameters

void

no arguments

Description

Eachidr_preload() should be matched with an invocation of thisfunction. Seeidr_preload() for details.

idr_for_each_entry

idr_for_each_entry(idr,entry,id)

Iterate over an IDR’s elements of a given type.

Parameters

idr

IDR handle.

entry

The type * to use as cursor

id

Entry ID.

Description

entry andid do not need to be initialized before the loop, andafter normal terminationentry is left with the value NULL. Thisis convenient for a “not found” value.

idr_for_each_entry_ul

idr_for_each_entry_ul(idr,entry,tmp,id)

Iterate over an IDR’s elements of a given type.

Parameters

idr

IDR handle.

entry

The type * to use as cursor.

tmp

A temporary placeholder for ID.

id

Entry ID.

Description

entry andid do not need to be initialized before the loop, andafter normal terminationentry is left with the value NULL. Thisis convenient for a “not found” value.

idr_for_each_entry_continue

idr_for_each_entry_continue(idr,entry,id)

Continue iteration over an IDR’s elements of a given type

Parameters

idr

IDR handle.

entry

The type * to use as a cursor.

id

Entry ID.

Description

Continue to iterate over entries, continuing after the current position.

idr_for_each_entry_continue_ul

idr_for_each_entry_continue_ul(idr,entry,tmp,id)

Continue iteration over an IDR’s elements of a given type

Parameters

idr

IDR handle.

entry

The type * to use as a cursor.

tmp

A temporary placeholder for ID.

id

Entry ID.

Description

Continue to iterate over entries, continuing after the current position.After normal terminationentry is left with the value NULL. Thisis convenient for a “not found” value.

intida_alloc(structida*ida,gfp_tgfp)

Allocate an unused ID.

Parameters

structida*ida

IDA handle.

gfp_tgfp

Memory allocation flags.

Description

Allocate an ID between 0 andINT_MAX, inclusive.

Context

Any context. It is safe to call this function withoutlocking in your code.

Return

The allocated ID, or-ENOMEM if memory could not be allocated,or-ENOSPC if there are no free IDs.

intida_alloc_min(structida*ida,unsignedintmin,gfp_tgfp)

Allocate an unused ID.

Parameters

structida*ida

IDA handle.

unsignedintmin

Lowest ID to allocate.

gfp_tgfp

Memory allocation flags.

Description

Allocate an ID betweenmin andINT_MAX, inclusive.

Context

Any context. It is safe to call this function withoutlocking in your code.

Return

The allocated ID, or-ENOMEM if memory could not be allocated,or-ENOSPC if there are no free IDs.

intida_alloc_max(structida*ida,unsignedintmax,gfp_tgfp)

Allocate an unused ID.

Parameters

structida*ida

IDA handle.

unsignedintmax

Highest ID to allocate.

gfp_tgfp

Memory allocation flags.

Description

Allocate an ID between 0 andmax, inclusive.

Context

Any context. It is safe to call this function withoutlocking in your code.

Return

The allocated ID, or-ENOMEM if memory could not be allocated,or-ENOSPC if there are no free IDs.

intidr_alloc_u32(structidr*idr,void*ptr,u32*nextid,unsignedlongmax,gfp_tgfp)

Allocate an ID.

Parameters

structidr*idr

IDR handle.

void*ptr

Pointer to be associated with the new ID.

u32*nextid

Pointer to an ID.

unsignedlongmax

The maximum ID to allocate (inclusive).

gfp_tgfp

Memory allocation flags.

Description

Allocates an unused ID in the range specified bynextid andmax.Note thatmax is inclusive whereas theend parameter toidr_alloc()is exclusive. The new ID is assigned tonextid before the pointeris inserted into the IDR, so ifnextid points into the object pointedto byptr, a concurrent lookup will not find an uninitialised ID.

The caller should provide their own locking to ensure that twoconcurrent modifications to the IDR are not possible. Read-onlyaccesses to the IDR may be done under the RCU read lock or mayexclude simultaneous writers.

Return

0 if an ID was allocated, -ENOMEM if memory allocation failed,or -ENOSPC if no free IDs could be found. If an error occurred,nextid is unchanged.

intidr_alloc(structidr*idr,void*ptr,intstart,intend,gfp_tgfp)

Allocate an ID.

Parameters

structidr*idr

IDR handle.

void*ptr

Pointer to be associated with the new ID.

intstart

The minimum ID (inclusive).

intend

The maximum ID (exclusive).

gfp_tgfp

Memory allocation flags.

Description

Allocates an unused ID in the range specified bystart andend. Ifend is <= 0, it is treated as one larger thanINT_MAX. This allowscallers to usestart + N asend as long as N is within integer range.

The caller should provide their own locking to ensure that twoconcurrent modifications to the IDR are not possible. Read-onlyaccesses to the IDR may be done under the RCU read lock or mayexclude simultaneous writers.

Return

The newly allocated ID, -ENOMEM if memory allocation failed,or -ENOSPC if no free IDs could be found.

intidr_alloc_cyclic(structidr*idr,void*ptr,intstart,intend,gfp_tgfp)

Allocate an ID cyclically.

Parameters

structidr*idr

IDR handle.

void*ptr

Pointer to be associated with the new ID.

intstart

The minimum ID (inclusive).

intend

The maximum ID (exclusive).

gfp_tgfp

Memory allocation flags.

Description

Allocates an unused ID in the range specified bystart andend. Ifend is <= 0, it is treated as one larger thanINT_MAX. This allowscallers to usestart + N asend as long as N is within integer range.The search for an unused ID will start at the last ID allocated and willwrap around tostart if no free IDs are found before reachingend.

The caller should provide their own locking to ensure that twoconcurrent modifications to the IDR are not possible. Read-onlyaccesses to the IDR may be done under the RCU read lock or mayexclude simultaneous writers.

Return

The newly allocated ID, -ENOMEM if memory allocation failed,or -ENOSPC if no free IDs could be found.

void*idr_remove(structidr*idr,unsignedlongid)

Remove an ID from the IDR.

Parameters

structidr*idr

IDR handle.

unsignedlongid

Pointer ID.

Description

Removes this ID from the IDR. If the ID was not previously in the IDR,this function returnsNULL.

Since this function modifies the IDR, the caller should provide theirown locking to ensure that concurrent modification of the same IDR isnot possible.

Return

The pointer formerly associated with this ID.

void*idr_find(conststructidr*idr,unsignedlongid)

Return pointer for given ID.

Parameters

conststructidr*idr

IDR handle.

unsignedlongid

Pointer ID.

Description

Looks up the pointer associated with this ID. ANULL pointer mayindicate thatid is not allocated or that theNULL pointer wasassociated with this ID.

This function can be called underrcu_read_lock(), given that the leafpointers lifetimes are correctly managed.

Return

The pointer associated with this ID.

intidr_for_each(conststructidr*idr,int(*fn)(intid,void*p,void*data),void*data)

Iterate through all stored pointers.

Parameters

conststructidr*idr

IDR handle.

int(*fn)(intid,void*p,void*data)

Function to be called for each pointer.

void*data

Data passed to callback function.

Description

The callback function will be called for each entry inidr, passingthe ID, the entry anddata.

Iffn returns anything other than0, the iteration stops and thatvalue is returned from this function.

idr_for_each() can be called concurrently withidr_alloc() andidr_remove() if protected by RCU. Newly added entries may not beseen and deleted entries may be seen, but adding and removing entrieswill not cause other entries to be skipped, nor spurious ones to be seen.

void*idr_get_next_ul(structidr*idr,unsignedlong*nextid)

Find next populated entry.

Parameters

structidr*idr

IDR handle.

unsignedlong*nextid

Pointer to an ID.

Description

Returns the next populated entry in the tree with an ID greater thanor equal to the value pointed to bynextid. On exit,nextid is updatedto the ID of the found value. To use in a loop, the value pointed to bynextid must be incremented by the user.

void*idr_get_next(structidr*idr,int*nextid)

Find next populated entry.

Parameters

structidr*idr

IDR handle.

int*nextid

Pointer to an ID.

Description

Returns the next populated entry in the tree with an ID greater thanor equal to the value pointed to bynextid. On exit,nextid is updatedto the ID of the found value. To use in a loop, the value pointed to bynextid must be incremented by the user.

void*idr_replace(structidr*idr,void*ptr,unsignedlongid)

replace pointer for given ID.

Parameters

structidr*idr

IDR handle.

void*ptr

New pointer to associate with the ID.

unsignedlongid

ID to change.

Description

Replace the pointer registered with an ID and return the old value.This function can be called under the RCU read lock concurrently withidr_alloc() andidr_remove() (as long as the ID being removed is notthe one being replaced!).

Return

the old value on success.-ENOENT indicates thatid was notfound.-EINVAL indicates thatptr was not valid.

intida_alloc_range(structida*ida,unsignedintmin,unsignedintmax,gfp_tgfp)

Allocate an unused ID.

Parameters

structida*ida

IDA handle.

unsignedintmin

Lowest ID to allocate.

unsignedintmax

Highest ID to allocate.

gfp_tgfp

Memory allocation flags.

Description

Allocate an ID betweenmin andmax, inclusive. The allocated ID willnot exceedINT_MAX, even ifmax is larger.

Context

Any context. It is safe to call this function withoutlocking in your code.

Return

The allocated ID, or-ENOMEM if memory could not be allocated,or-ENOSPC if there are no free IDs.

intida_find_first_range(structida*ida,unsignedintmin,unsignedintmax)

Get the lowest used ID.

Parameters

structida*ida

IDA handle.

unsignedintmin

Lowest ID to get.

unsignedintmax

Highest ID to get.

Description

Get the lowest used ID betweenmin andmax, inclusive. The returnedID will not exceedINT_MAX, even ifmax is larger.

Context

Any context. Takes and releases the xa_lock.

Return

The lowest used ID, or errno if no used ID is found.

voidida_free(structida*ida,unsignedintid)

Release an allocated ID.

Parameters

structida*ida

IDA handle.

unsignedintid

Previously allocated ID.

Context

Any context. It is safe to call this function withoutlocking in your code.

voidida_destroy(structida*ida)

Free all IDs.

Parameters

structida*ida

IDA handle.

Description

Calling this function frees all IDs and releases all resources usedby an IDA. When this call returns, the IDA is empty and can be reusedor freed. If the IDA is already empty, there is no need to call thisfunction.

Context

Any context. It is safe to call this function withoutlocking in your code.