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_simple_get()
. To free an ID, call ida_simple_remove()
.
If you have more complex locking requirements, use a loop around
ida_pre_get()
and ida_get_new()
to allocate a new ID. Then use
ida_remove()
to free an ID. You must make sure that ida_get_new()
and
ida_remove()
cannot be called at the same time as each other for the
same IDA.
You can also use ida_get_new_above()
if you need an ID to be allocated
above a particular number. 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.
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).
idr sync
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).
-
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, 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_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.
-
int
ida_get_new
(struct ida * ida, int * p_id)¶ allocate new ID
Parameters
struct ida * ida
- idr handle
int * p_id
- pointer to the allocated handle
Description
Simple wrapper around ida_get_new_above()
w/ starting_id of zero.
-
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.
IDA description
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_simple_get()
. To free an ID, call ida_simple_remove()
.
If you have more complex locking requirements, use a loop around
ida_pre_get()
and ida_get_new()
to allocate a new ID. Then use
ida_remove()
to free an ID. You must make sure that ida_get_new()
and
ida_remove()
cannot be called at the same time as each other for the
same IDA.
You can also use ida_get_new_above()
if you need an ID to be allocated
above a particular number. 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.
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.
-
int
ida_get_new_above
(struct ida * ida, int start, int * id)¶ allocate new ID above or equal to a start id
Parameters
struct ida * ida
- ida handle
int start
- id to start search at
int * id
- pointer to the allocated handle
Description
Allocate new ID above or equal to start. It should be called
with any required locks to ensure that concurrent calls to
ida_get_new_above()
/ ida_get_new()
/ ida_remove()
are not allowed.
Consider using ida_simple_get()
if you do not have complex locking
requirements.
If memory is required, it will return -EAGAIN
, you should unlock
and go back to the ida_pre_get()
call. If the ida is full, it will
return -ENOSPC
. On success, it will return 0.
id returns a value in the range start ... 0x7fffffff
.
-
void
ida_remove
(struct ida * ida, int id)¶ Free the given ID
Parameters
struct ida * ida
- ida handle
int id
- ID to free
Description
This function should not be called at the same time as ida_get_new_above()
.
-
void
ida_destroy
(struct ida * ida)¶ Free the contents of an ida
Parameters
struct ida * ida
- ida handle
Description
Calling this function releases all resources associated with an IDA. When
this call returns, the IDA is empty and can be reused or freed. The caller
should not allow ida_remove()
or ida_get_new_above()
to be called at the
same time.
-
int
ida_simple_get
(struct ida * ida, unsigned int start, unsigned int end, gfp_t gfp_mask)¶ get a new id.
Parameters
struct ida * ida
- the (initialized) ida.
unsigned int start
- the minimum id (inclusive, < 0x8000000)
unsigned int end
- the maximum id (exclusive, < 0x8000000 or 0)
gfp_t gfp_mask
- memory allocation flags
Description
Allocates an id in the range start <= id < end, or returns -ENOSPC. On memory allocation failure, returns -ENOMEM.
Compared to ida_get_new_above()
this function does its own locking, and
should be used unless there are special requirements.
Use ida_simple_remove()
to get rid of an id.
-
void
ida_simple_remove
(struct ida * ida, unsigned int id)¶ remove an allocated id.
Parameters
struct ida * ida
- the (initialized) ida.
unsigned int id
- the id returned by ida_simple_get.
Description
Use to release an id allocated with ida_simple_get()
.
Compared to ida_remove()
this function does its own locking, and should be
used unless there are special requirements.