ID Allocation¶

Author:	Matthew Wilcox

Overview¶

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

IDR usage¶

Start by initialising an IDR, either with DEFINE_IDR() for statically allocated IDRs or idr_init() for dynamically allocated IDRs.

You can call idr_alloc() to allocate an unused ID. Look up the pointer you associated with the ID by calling idr_find() and free the ID by calling idr_remove().

If you need to change the pointer associated with an ID, you can call idr_replace(). One common reason to do this is to reserve an ID by passing a NULL pointer to the allocation function; initialise the object with the reserved ID and finally insert the initialised object into the IDR.

Some users need to allocate IDs larger than INT_MAX. So far all of these users have been content with a UINT_MAX limit, and they use idr_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 use idr_alloc_cyclic(). The IDR becomes less efficient when dealing with larger IDs, so using this function comes at a slight cost.

To perform an action on all pointers used by the IDR, you can either use the callback-based idr_for_each() or the iterator-style idr_for_each_entry(). You may need to use idr_for_each_entry_continue() to continue an iteration. You can also use idr_get_next() if the iterator doesn’t fit your needs.

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

You can use idr_is_empty() to find out whether there are any IDs 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 lead to the IDR being unable to allocate memory. To work around this, you can call idr_preload() before taking the lock, and then idr_preload_end() after the allocation.

idr synchronization (stolen from radix-tree.h)

idr_find() is able to be called locklessly, using RCU. The caller must ensure calls to this function are made within rcu_read_lock() regions. Other readers (lock-free or otherwise) and modifications may be running concurrently.

It is still required that the caller manage the synchronization and lifetimes of the items. So if RCU lock-free lookups are used, typically this would mean that the items have their own locks, or are amenable to lock-free access; and that the items are freed by RCU (or only freed after having been deleted from the idr tree and a synchronize_rcu() grace period).

IDA usage¶

The IDA is an ID allocator which does not provide the ability to associate an ID with a pointer. As such, it only needs to store one bit per ID, and so is more space efficient than an IDR. To use an IDA, define it using DEFINE_IDA() (or embed a struct ida in a data structure, then initialise it using ida_init()). To allocate a new ID, call ida_alloc(), ida_alloc_min(), ida_alloc_max() or ida_alloc_range(). To free an ID, call ida_free().

ida_destroy() can be used to dispose of an IDA without needing to free the individual IDs in it. You can use ida_is_empty() to find out whether the IDA has any IDs currently allocated.

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

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

Functions and structures¶

IDR_INIT(name)¶: Initialise an IDR.

Parameters

name: Name of IDR.

Description

A freshly-initialised IDR contains no IDs.

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 additional initialisation required. It contains no IDs.

unsigned int idr_get_cursor(const struct idr * idr)¶: Return the current position of the cyclic allocator

Parameters

const struct idr * idr: idr handle

Description

The value returned is the value that will be next returned from idr_alloc_cyclic() if it is free (otherwise the search will start from this position).

void idr_set_cursor(struct idr * idr, unsigned int val)¶: Set the current position of the cyclic allocator

Parameters

struct idr * idr: idr handle
unsigned int val: new position

Description

The next call to idr_alloc_cyclic() will return val if it is free (otherwise the search will start from this position).

void idr_init_base(struct idr * idr, int base)¶: Initialise an IDR.

Parameters

struct idr * idr: IDR handle.
int base: The base value for the IDR.

Description

This variation of idr_init() creates an IDR which will allocate IDs starting at base.

void idr_init(struct idr * idr)¶: Initialise an IDR.

Parameters

struct idr * idr: IDR handle.

Description

Initialise a dynamically allocated IDR. To initialise a statically allocated IDR, use DEFINE_IDR().

bool idr_is_empty(const struct idr * idr)¶: Are there any IDs allocated?

Parameters

const struct idr * idr: IDR handle.

Return

true if any IDs have been allocated from this IDR.

void idr_preload_end(void)¶: end preload section started with idr_preload()

Parameters

void: no arguments

Description

Each idr_preload() should be matched with an invocation of this function. See idr_preload() for details.

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 and id do not need to be initialized before the loop, and after normal termination entry is left with the value NULL. This is convenient for a “not found” value.

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 and id do not need to be initialized before the loop, and after normal termination entry is left with the value NULL. This is convenient for a “not found” value.

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, 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.

int ida_alloc(struct ida * ida, gfp_t gfp)¶: Allocate an unused ID.

Parameters

struct ida * ida: IDA handle.
gfp_t gfp: Memory allocation flags.

Description

Allocate an ID between 0 and INT_MAX, inclusive.

Context

Any context.

Return

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

int ida_alloc_min(struct ida * ida, unsigned int min, gfp_t gfp)¶: Allocate an unused ID.

Parameters

struct ida * ida: IDA handle.
unsigned int min: Lowest ID to allocate.
gfp_t gfp: Memory allocation flags.

Description

Allocate an ID between min and INT_MAX, inclusive.

Context

Any context.

Return

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

int ida_alloc_max(struct ida * ida, unsigned int max, gfp_t gfp)¶: Allocate an unused ID.

Parameters

struct ida * ida: IDA handle.
unsigned int max: Highest ID to allocate.
gfp_t gfp: Memory allocation flags.

Description

Allocate an ID between 0 and max, inclusive.

Context

Any context.

Return

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

int idr_alloc_u32(struct idr * idr, void * ptr, u32 * nextid, unsigned long max, gfp_t gfp)¶: Allocate an ID.

Parameters

struct idr * idr: IDR handle.
void * ptr: Pointer to be associated with the new ID.
u32 * nextid: Pointer to an ID.
unsigned long max: The maximum ID to allocate (inclusive).
gfp_t gfp: Memory allocation flags.

Description

Allocates an unused ID in the range specified by nextid and max. Note that max is inclusive whereas the end parameter to idr_alloc() is exclusive. The new ID is assigned to nextid before the pointer is inserted into the IDR, so if nextid points into the object pointed to by ptr, a concurrent lookup will not find an uninitialised ID.

The caller should provide their own locking to ensure that two concurrent modifications to the IDR are not possible. Read-only accesses to the IDR may be done under the RCU read lock or may exclude 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.

int idr_alloc(struct idr * idr, void * ptr, int start, int end, gfp_t gfp)¶: Allocate an ID.

Parameters

struct idr * idr: IDR handle.
void * ptr: Pointer to be associated with the new ID.
int start: The minimum ID (inclusive).
int end: The maximum ID (exclusive).
gfp_t gfp: Memory allocation flags.

Description

Allocates an unused ID in the range specified by start and end. If end is <= 0, it is treated as one larger than INT_MAX. This allows callers to use start + N as end as long as N is within integer range.

The caller should provide their own locking to ensure that two concurrent modifications to the IDR are not possible. Read-only accesses to the IDR may be done under the RCU read lock or may exclude simultaneous writers.

Return

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

int idr_alloc_cyclic(struct idr * idr, void * ptr, int start, int end, gfp_t gfp)¶: Allocate an ID cyclically.

Parameters

struct idr * idr: IDR handle.
void * ptr: Pointer to be associated with the new ID.
int start: The minimum ID (inclusive).
int end: The maximum ID (exclusive).
gfp_t gfp: Memory allocation flags.

Description

Allocates an unused ID in the range specified by nextid and end. If end is <= 0, it is treated as one larger than INT_MAX. This allows callers to use start + N as end as long as N is within integer range. The search for an unused ID will start at the last ID allocated and will wrap around to start if no free IDs are found before reaching end.

The caller should provide their own locking to ensure that two concurrent modifications to the IDR are not possible. Read-only accesses to the IDR may be done under the RCU read lock or may exclude simultaneous writers.

Return

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

void * idr_remove(struct idr * idr, unsigned long id)¶: Remove an ID from the IDR.

Parameters

struct idr * idr: IDR handle.
unsigned long id: Pointer ID.

Description

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

Since this function modifies the IDR, the caller should provide their own locking to ensure that concurrent modification of the same IDR is not possible.

Return

The pointer formerly associated with this ID.

void * idr_find(const struct idr * idr, unsigned long id)¶: Return pointer for given ID.

Parameters

const struct idr * idr: IDR handle.
unsigned long id: Pointer ID.

Description

Looks up the pointer associated with this ID. A NULL pointer may indicate that id is not allocated or that the NULL pointer was associated with this ID.

This function can be called under rcu_read_lock(), given that the leaf pointers lifetimes are correctly managed.

Return

The pointer associated with this ID.

int idr_for_each(const struct idr * idr, int (*fn) (int id, void *p, void *data, void * data)¶: Iterate through all stored pointers.

Parameters

const struct idr * idr: IDR handle.
int (*)(int id, void *p, void *data) fn: Function to be called for each pointer.
void * data: Data passed to callback function.

Description

The callback function will be called for each entry in idr, passing the ID, the entry and data.

If fn returns anything other than 0, the iteration stops and that value is returned from this function.

idr_for_each() can be called concurrently with idr_alloc() and idr_remove() if protected by RCU. Newly added entries may not be seen and deleted entries may be seen, but adding and removing entries will not cause other entries to be skipped, nor spurious ones to be seen.

void * idr_get_next(struct idr * idr, int * nextid)¶: Find next populated entry.

Parameters

struct idr * idr: IDR handle.
int * nextid: Pointer to an ID.

Description

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

void * idr_get_next_ul(struct idr * idr, unsigned long * nextid)¶: Find next populated entry.

Parameters

struct idr * idr: IDR handle.
unsigned long * nextid: Pointer to an ID.

Description

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

void * idr_replace(struct idr * idr, void * ptr, unsigned long id)¶: replace pointer for given ID.

Parameters

struct idr * idr: IDR handle.
void * ptr: New pointer to associate with the ID.
unsigned long id: 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 with idr_alloc() and idr_remove() (as long as the ID being removed is not the one being replaced!).

Return

the old value on success. -ENOENT indicates that id was not found. -EINVAL indicates that ptr was not valid.

int ida_alloc_range(struct ida * ida, unsigned int min, unsigned int max, gfp_t gfp)¶: Allocate an unused ID.

Parameters

struct ida * ida: IDA handle.
unsigned int min: Lowest ID to allocate.
unsigned int max: Highest ID to allocate.
gfp_t gfp: Memory allocation flags.

Description

Allocate an ID between min and max, inclusive. The allocated ID will not exceed INT_MAX, even if max is larger.

Context

Any context.

Return

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

void ida_free(struct ida * ida, unsigned int id)¶: Release an allocated ID.

Parameters

struct ida * ida: IDA handle.
unsigned int id: Previously allocated ID.

Context

Any context.

void ida_destroy(struct ida * ida)¶: Free all IDs.

Parameters

struct ida * ida: IDA handle.

Description

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

Context

Any context.