idr/ida Functions

idr_alloc — allocate an id
idr_alloc_cyclic — allocate new idr entry in a cyclical fashion
idr_for_each — iterate through all stored pointers
idr_get_next — Find next populated entry
idr_replace — replace pointer for given id
ida_get_new_above — allocate new ID above or equal to a start id
ida_remove — Free the given ID
ida_destroy — Free the contents of an ida
ida_simple_get — get a new id.
ida_simple_remove — remove an allocated id.

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

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.