IDR API
The IDR API is charged with the allocation of integer ID numbers used with device names, POSIX timers, and more.
void idr_preload(gfp_t gfp_mask);
int idr_alloc(struct idr *idp, void *ptr, int start
, int end, gfp_t gfp_mask);
void idr_preload_end(void);
idr_preload() function is charged with allocating the memory necessary to satisfy the next allocation request. A call to idr_alloc() allocates an integer ID. It accepts upper and lower bounds for that ID to accommodate code that can only cope with a given range of numbers — code that uses the ID as an array index, for example. If need be, it will attempt to allocate memory using the given gfp_mask. Allocations will be unnecessary if idr_preload() has been called.
Looking up an existing ID is achieved with:
void *idr_find(struct idr *idp, int id);
The return value will be the pointer associated with the given id, or NULL otherwise.
To deallocate an ID, use:
void idr_remove(struct idr *idp, int id);
With these functions, kernel code can generate ID numbers to use as minor device numbers, inode numbers, or in any other place where small integer IDs are useful, for instance file descriptors.
The longer version: An application of the IDR system is to associate an integer with a pointer. For example, in the IIC bus, each device has its own address; to find a particular device on the bus, we must first find the device address.
To access a bus on the IIC device, we must know the ID and use that to describe the structure of the device in the kernel. If one were to use an array to store the structure and the array index were to correspond to the integer ID, once the ID is in higher numbers, a lot a memory will be occupied. If instead we were to use a list, finding the structure would not be time efficient. Hence, IDR comes to the rescue!
The internal implementation of IDR is done using a radix tree, and thus it is very convenient to associate an integer and pointer, along with a high search efficiency.
Two, related structures:
struct idr {
struct idr_layer __rcu *hint; //A recent memory pointer data structures of the idr_layer
struct idr_layer __rcu *top; //IDR idr_layer tree top, the root of the tree
struct idr_layer *id_free; //Pointer to a idr_layer free list
int layers; //The idr_layer layer in the IDR tree number
int id_free_cnt; //The number of idr_layer idr_layer in the remaining free list
int cur; //current pos for cyclic allocation
spinlock_t lock;
};
struct idr_layer {
int prefix; //the ID prefix of this idr_layer
DECLARE_BITMAP(bitmap, IDR_SIZE); //Mark ary bitmap, an array of tag the idr_layer usage
//The array is used to save the pointer data specific to idr_layer or sub structure, the size of 1<<6=64
struct idr_layer __rcu *ary[1<<IDR_BITS];
int count; //Ary array using count
int layer; //The layer number
struct rcu_head rcu_head;
};
Initalisation in IDR API
The function idr_init_cache() is called inside the start_kernel function. idr_init_cache() allocates a slab cache and is used for the allocation of idr_layer structure.
static struct kmem_cache *idr_layer_cache;
void __init idr_init_cache(void)
{
idr_layer_cache = kmem_cache_create(“idr_layer_cache”,sizeof(struct idr_layer), 0, SLAB_PANIC, NULL);
}
There are two ways to create a new IDR structure: Macro definition and initialization of a named name IDR:
#define DEFINE_IDR(name) struct idr name = IDR_INIT(name)
#define IDR_INIT(name) \
{ \
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \
}
Dynamic initialization of IDR:
void idr_init(struct idr *idp)
{
memset(idp, 0, sizeof(struct idr));
spin_lock_init(&idp->lock);
}
Allocation
void idr_preload(gfp_t gfp_mask);
int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask);
void idr_preload_end(void);
idr_preload() is charged with allocating the memory necessary to satisfy the next allocation request. A call to idr_alloc() allocates an integer ID. It accepts upper and lower bounds for that ID to accommodate code that can only cope with a given range of numbers — code that uses the ID as an array index, for example. If need be, it will attempt to allocate memory using the given gfp_mask. Allocations will be unnecessary if idr_preload() has been called. When used inside preloaded section, the allocation mask of preloading can be assumed. Integer and the pointer associated with it IDR allocates integers relatively simply. IDR_BITS=6, so the first level in the IDR tree (or the root) has 64 slots. Let’s assume we have a two level structure, top refers to 64 tree roots and in the next level are 64 leaf nodes corresponding to each slot in the root. In the leaf layer idr_layer ary array element is used to point to the target obj. Then the two levels can control 64*64=4096 objects. Find a pointer corresponding to an ID Let us assume a two level tree. Now if we were to find the pointer corresponding to the ID 65, then 74/64 =1, so starting from the top, we move to top->ary[1]. Next we need to find the leaf node. The leaf node index is ID&IDR_MASK, which is 10. So the ary[10] object in the second level points to the pointer to this ID.
static inline void *idr_find(struct idr *idr, int id)
{
//Retains the last operation before the idr_layer pointer
struct idr_layer *hint = rcu_dereference_raw(idr->hint);
//Assign a proper ID in the IDR idr_layer tree, idr_layer path
//and distribution records in the PA array
rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp);
if (rv <0)
return rv == -ENOMEM ? -EAGAIN : rv;
//Correlation of PTR and ID
idr_fill_slot(idp, ptr, rv, pa);
*id = rv;
return 0;
}
Replace pointer for an ID Sometimes, one might want to update the pointer corresponding to an ID. This essentially is looking up the location corresponding to the ID followed by updating the pointer in that location.
void *idr_replace(struct idr *idp, void *ptr, int id)
{
int n;
struct idr_layer *p, *old_p;
if (id <0)
return ERR_PTR(-EINVAL);
//Find the IDR top pointer
p = idp->top;
if (!p)
return ERR_PTR(-EINVAL);
//According to the IDR layer, set the corresponding bits
n = (p->layer+1) * IDR_BITS;
if (id >= (1 <<n))
return ERR_PTR(-EINVAL);
//From the tree top top, to find out the leaves, array ID in the corresponding data pointer
n -= IDR_BITS;
while ((n > 0) && p) {
p = p->ary[(id >> n) & IDR_MASK];
n -= IDR_BITS;
}
//Find the leaf address
n = id & IDR_MASK;
if (unlikely(p == NULL || !test_bit(n, p->bitmap)))
return ERR_PTR(-ENOENT);
//ID ary arrays, pointer replacement
old_p = p->ary[n];
rcu_assign_pointer(p->ary[n], ptr);
return old_p;
}
Remove assignment of a pointer from an ID To remove the assignment of a pointer from an ID we need three steps:
- Look up the pointer in the tree.
- Remove assignment to that pointer (by traversing the an idr_layer array inside sub_remove() and releasing the idr_layer structure).
- If there is an opportunity to shrink the tree, remove the entire level.
void idr_remove(struct idr *idp, int id)
{
struct idr_layer *p;
struct idr_layer *to_free;
if (id <0)
return;
//Idr_layer path ID releases corresponding space
sub_remove(idp, (idp->layers — 1) * IDR_BITS, id);
if (idp->top && idp->top->count == 1
&& (idp->layers > 1) && idp->top->ary[0])
{
/*
* Single child at leftmost slot: we can shrink the tree.
* This level is not needed anymore since when layers are
* inserted, they are inserted at the top of the existing
* tree.
*/
to_free = idp->top;
p = idp->top->ary[0];
rcu_assign_pointer(idp->top, p);
--idp->layers;
to_free->count = 0;
bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
free_layer(idp, to_free);
}
}