12,51 → 12,30 |
#ifndef __IDR_H__ |
#define __IDR_H__ |
|
#include <syscall.h> |
#include <linux/types.h> |
#include <errno-base.h> |
#include <linux/bitops.h> |
//#include <linux/init.h> |
//#include <linux/rcupdate.h> |
#include <linux/spinlock.h> |
#include <linux/bitmap.h> |
#include <linux/bug.h> |
|
struct rcu_head { |
struct rcu_head *next; |
void (*func)(struct rcu_head *head); |
}; |
|
|
#if BITS_PER_LONG == 32 |
# define IDR_BITS 5 |
# define IDR_FULL 0xfffffffful |
/* We can only use two of the bits in the top level because there is |
only one possible bit in the top level (5 bits * 7 levels = 35 |
bits, but you only use 31 bits in the id). */ |
# define TOP_LEVEL_FULL (IDR_FULL >> 30) |
#elif BITS_PER_LONG == 64 |
# define IDR_BITS 6 |
# define IDR_FULL 0xfffffffffffffffful |
/* We can only use two of the bits in the top level because there is |
only one possible bit in the top level (6 bits * 6 levels = 36 |
bits, but you only use 31 bits in the id). */ |
# define TOP_LEVEL_FULL (IDR_FULL >> 62) |
#else |
# error "BITS_PER_LONG is not 32 or 64" |
#endif |
|
/* |
* We want shallower trees and thus more bits covered at each layer. 8 |
* bits gives us large enough first layer for most use cases and maximum |
* tree depth of 4. Each idr_layer is slightly larger than 2k on 64bit and |
* 1k on 32bit. |
*/ |
#define IDR_BITS 8 |
#define IDR_SIZE (1 << IDR_BITS) |
#define IDR_MASK ((1 << IDR_BITS)-1) |
|
#define MAX_ID_SHIFT (sizeof(int)*8 - 1) |
#define MAX_ID_BIT (1U << MAX_ID_SHIFT) |
#define MAX_ID_MASK (MAX_ID_BIT - 1) |
|
/* Leave the possibility of an incomplete final layer */ |
#define MAX_LEVEL (MAX_ID_SHIFT + IDR_BITS - 1) / IDR_BITS |
|
/* Number of id_layer structs to leave in free list */ |
#define IDR_FREE_MAX MAX_LEVEL + MAX_LEVEL |
|
struct idr_layer { |
unsigned long bitmap; /* A zero bit means "space here" */ |
int prefix; /* the ID prefix of this idr_layer */ |
DECLARE_BITMAP(bitmap, IDR_SIZE); /* A zero bit means "space here" */ |
struct idr_layer __rcu *ary[1<<IDR_BITS]; |
int count; /* When zero, we can release it */ |
int layer; /* distance from leaf */ |
64,29 → 43,20 |
}; |
|
struct idr { |
struct idr_layer __rcu *hint; /* the last layer allocated from */ |
struct idr_layer __rcu *top; |
struct idr_layer *id_free; |
int layers; /* only valid without concurrent changes */ |
int layers; /* only valid w/o concurrent changes */ |
int id_free_cnt; |
// spinlock_t lock; |
spinlock_t lock; |
}; |
|
#define IDR_INIT(name) \ |
{ \ |
.top = NULL, \ |
.id_free = NULL, \ |
.layers = 0, \ |
.id_free_cnt = 0, \ |
// .lock = __SPIN_LOCK_UNLOCKED(name.lock), \ |
.lock = __SPIN_LOCK_UNLOCKED(name.lock), \ |
} |
#define DEFINE_IDR(name) struct idr name = IDR_INIT(name) |
|
/* Actions to be taken after a call to _idr_sub_alloc */ |
#define IDR_NEED_TO_GROW -2 |
#define IDR_NOMORE_SPACE -3 |
|
#define _idr_rc_to_errno(rc) ((rc) == -1 ? -EAGAIN : -ENOSPC) |
|
/** |
* DOC: idr sync |
* idr synchronization (stolen from radix-tree.h) |
108,20 → 78,91 |
* This is what we export. |
*/ |
|
void *idr_find(struct idr *idp, int id); |
void *idr_find_slowpath(struct idr *idp, int id); |
int idr_pre_get(struct idr *idp, gfp_t gfp_mask); |
int idr_get_new(struct idr *idp, void *ptr, int *id); |
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id); |
void idr_preload(gfp_t gfp_mask); |
int idr_alloc(struct idr *idp, void *ptr, int start, int end, gfp_t gfp_mask); |
int idr_for_each(struct idr *idp, |
int (*fn)(int id, void *p, void *data), void *data); |
void *idr_get_next(struct idr *idp, int *nextid); |
void *idr_replace(struct idr *idp, void *ptr, int id); |
void idr_remove(struct idr *idp, int id); |
void idr_remove_all(struct idr *idp); |
void idr_free(struct idr *idp, int id); |
void idr_destroy(struct idr *idp); |
void idr_init(struct idr *idp); |
|
/** |
* idr_preload_end - end preload section started with idr_preload() |
* |
* Each idr_preload() should be matched with an invocation of this |
* function. See idr_preload() for details. |
*/ |
static inline void idr_preload_end(void) |
{ |
// preempt_enable(); |
} |
|
/** |
* idr_find - return pointer for given id |
* @idp: idr handle |
* @id: lookup key |
* |
* Return the pointer given the id it has been registered with. A %NULL |
* return indicates that @id is not valid or you passed %NULL in |
* idr_get_new(). |
* |
* This function can be called under rcu_read_lock(), given that the leaf |
* pointers lifetimes are correctly managed. |
*/ |
static inline void *idr_find(struct idr *idr, int id) |
{ |
struct idr_layer *hint = rcu_dereference_raw(idr->hint); |
|
if (hint && (id & ~IDR_MASK) == hint->prefix) |
return rcu_dereference_raw(hint->ary[id & IDR_MASK]); |
|
return idr_find_slowpath(idr, id); |
} |
|
/** |
* idr_get_new - allocate new idr entry |
* @idp: idr handle |
* @ptr: pointer you want associated with the id |
* @id: pointer to the allocated handle |
* |
* Simple wrapper around idr_get_new_above() w/ @starting_id of zero. |
*/ |
static inline int idr_get_new(struct idr *idp, void *ptr, int *id) |
{ |
return idr_get_new_above(idp, ptr, 0, id); |
} |
|
/** |
* idr_for_each_entry - iterate over an idr's elements of a given type |
* @idp: idr handle |
* @entry: the type * to use as cursor |
* @id: id entry's key |
*/ |
#define idr_for_each_entry(idp, entry, id) \ |
for (id = 0, entry = (typeof(entry))idr_get_next((idp), &(id)); \ |
entry != NULL; \ |
++id, entry = (typeof(entry))idr_get_next((idp), &(id))) |
|
void __idr_remove_all(struct idr *idp); /* don't use */ |
|
/** |
* idr_remove_all - remove all ids from the given idr tree |
* @idp: idr handle |
* |
* If you're trying to destroy @idp, calling idr_destroy() is enough. |
* This is going away. Don't use. |
*/ |
static inline void __deprecated idr_remove_all(struct idr *idp) |
{ |
__idr_remove_all(idp); |
} |
|
/* |
* IDA - IDR based id allocator, use when translation from id to |
* pointer isn't necessary. |
143,16 → 184,17 |
struct ida_bitmap *free_bitmap; |
}; |
|
#define IDA_INIT(name) { .idr = IDR_INIT(name), .free_bitmap = NULL, } |
#define IDA_INIT(name) { .idr = IDR_INIT((name).idr), .free_bitmap = NULL, } |
#define DEFINE_IDA(name) struct ida name = IDA_INIT(name) |
|
int ida_pre_get(struct ida *ida, gfp_t gfp_mask); |
int ida_get_new_above(struct ida *ida, int starting_id, int *p_id); |
int ida_get_new(struct ida *ida, int *p_id); |
void ida_remove(struct ida *ida, int id); |
void ida_destroy(struct ida *ida); |
void ida_init(struct ida *ida); |
|
void idr_init_cache(void); |
void __init idr_init_cache(void); |
|
|
|
#endif /* __IDR_H__ */ |