static struct kmem_cache *idr_layer_cache;
static DEFINE_SPINLOCK(simple_ida_lock);
+/* the maximum ID which can be allocated given idr->layers */
+static int idr_max(int layers)
+{
+ int bits = min_t(int, layers * IDR_BITS, MAX_ID_SHIFT);
+
+ return (1 << bits) - 1;
+}
+
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
id = (id | ((1 << (IDR_BITS * l)) - 1)) + 1;
/* if already at the top layer, we need to grow */
- if (id >= 1 << (idp->layers * IDR_BITS)) {
+ if (id > idr_max(idp->layers)) {
*starting_id = id;
return IDR_NEED_TO_GROW;
}
* Add a new layer to the top of the tree if the requested
* id is larger than the currently allocated space.
*/
- while ((layers < (MAX_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
+ while (id > idr_max(layers)) {
layers++;
if (!p->count) {
/* special case: if the tree is currently empty,
static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
{
- struct idr_layer *pa[MAX_LEVEL];
+ struct idr_layer *pa[MAX_LEVEL + 1];
int id;
id = idr_get_empty_slot(idp, starting_id, pa);
static void sub_remove(struct idr *idp, int shift, int id)
{
struct idr_layer *p = idp->top;
- struct idr_layer **pa[MAX_LEVEL];
+ struct idr_layer **pa[MAX_LEVEL + 1];
struct idr_layer ***paa = &pa[0];
struct idr_layer *to_free;
int n;
int n, id, max;
int bt_mask;
struct idr_layer *p;
- struct idr_layer *pa[MAX_LEVEL];
+ struct idr_layer *pa[MAX_LEVEL + 1];
struct idr_layer **paa = &pa[0];
n = idp->layers * IDR_BITS;
p = idp->top;
rcu_assign_pointer(idp->top, NULL);
- max = 1 << n;
+ max = idr_max(idp->layers);
id = 0;
- while (id < max) {
+ while (id >= 0 && id <= max) {
while (n > IDR_BITS && p) {
n -= IDR_BITS;
*paa++ = p;
/* Mask off upper bits we don't use for the search. */
id &= MAX_ID_MASK;
- if (id >= (1 << n))
+ if (id > idr_max(p->layer + 1))
return NULL;
BUG_ON(n == 0);
{
int n, id, max, error = 0;
struct idr_layer *p;
- struct idr_layer *pa[MAX_LEVEL];
+ struct idr_layer *pa[MAX_LEVEL + 1];
struct idr_layer **paa = &pa[0];
n = idp->layers * IDR_BITS;
p = rcu_dereference_raw(idp->top);
- max = 1 << n;
+ max = idr_max(idp->layers);
id = 0;
- while (id < max) {
+ while (id >= 0 && id <= max) {
while (n > 0 && p) {
n -= IDR_BITS;
*paa++ = p;
* Returns pointer to registered object with id, which is next number to
* given id. After being looked up, *@nextidp will be updated for the next
* iteration.
+ *
+ * This function can be called under rcu_read_lock(), given that the leaf
+ * pointers lifetimes are correctly managed.
*/
-
void *idr_get_next(struct idr *idp, int *nextidp)
{
- struct idr_layer *p, *pa[MAX_LEVEL];
+ struct idr_layer *p, *pa[MAX_LEVEL + 1];
struct idr_layer **paa = &pa[0];
int id = *nextidp;
int n, max;
/* find first ent */
- n = idp->layers * IDR_BITS;
- max = 1 << n;
p = rcu_dereference_raw(idp->top);
if (!p)
return NULL;
+ n = (p->layer + 1) * IDR_BITS;
+ max = idr_max(p->layer + 1);
- while (id < max) {
+ while (id >= 0 && id <= max) {
while (n > 0 && p) {
n -= IDR_BITS;
*paa++ = p;
return p;
}
- id += 1 << n;
+ /*
+ * Proceed to the next layer at the current level. Unlike
+ * idr_for_each(), @id isn't guaranteed to be aligned to
+ * layer boundary at this point and adding 1 << n may
+ * incorrectly skip IDs. Make sure we jump to the
+ * beginning of the next layer using round_up().
+ */
+ id = round_up(id + 1, 1 << n);
while (n < fls(id)) {
n += IDR_BITS;
p = *--paa;
if (!p)
return ERR_PTR(-EINVAL);
- n = (p->layer+1) * IDR_BITS;
-
id &= MAX_ID_MASK;
- if (id >= (1 << n))
+ if (id > idr_max(p->layer + 1))
return ERR_PTR(-EINVAL);
- n -= IDR_BITS;
+ n = p->layer * IDR_BITS;
while ((n > 0) && p) {
p = p->ary[(id >> n) & IDR_MASK];
n -= IDR_BITS;
*/
int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
{
- struct idr_layer *pa[MAX_LEVEL];
+ struct idr_layer *pa[MAX_LEVEL + 1];
struct ida_bitmap *bitmap;
unsigned long flags;
int idr_id = starting_id / IDA_BITMAP_BITS;
{
int ret, id;
unsigned int max;
+ unsigned long flags;
BUG_ON((int)start < 0);
BUG_ON((int)end < 0);
if (!ida_pre_get(ida, gfp_mask))
return -ENOMEM;
- spin_lock(&simple_ida_lock);
+ spin_lock_irqsave(&simple_ida_lock, flags);
ret = ida_get_new_above(ida, start, &id);
if (!ret) {
if (id > max) {
ret = id;
}
}
- spin_unlock(&simple_ida_lock);
+ spin_unlock_irqrestore(&simple_ida_lock, flags);
if (unlikely(ret == -EAGAIN))
goto again;
*/
void ida_simple_remove(struct ida *ida, unsigned int id)
{
+ unsigned long flags;
+
BUG_ON((int)id < 0);
- spin_lock(&simple_ida_lock);
+ spin_lock_irqsave(&simple_ida_lock, flags);
ida_remove(ida, id);
- spin_unlock(&simple_ida_lock);
+ spin_unlock_irqrestore(&simple_ida_lock, flags);
}
EXPORT_SYMBOL(ida_simple_remove);