return (1 << bits) - 1;
}
+/*
+ * Prefix mask for an idr_layer at @layer. For layer 0, the prefix mask is
+ * all bits except for the lower IDR_BITS. For layer 1, 2 * IDR_BITS, and
+ * so on.
+ */
+static int idr_layer_prefix_mask(int layer)
+{
+ return ~idr_max(layer + 1);
+}
+
static struct idr_layer *get_from_free_list(struct idr *idp)
{
struct idr_layer *p;
kmem_cache_free(idr_layer_cache, layer);
}
-static inline void free_layer(struct idr_layer *p)
+static inline void free_layer(struct idr *idr, struct idr_layer *p)
{
+ if (idr->hint && idr->hint == p)
+ RCU_INIT_POINTER(idr->hint, NULL);
call_rcu(&p->rcu_head, idr_layer_rcu_free);
}
struct idr_layer *p = pa[0];
int l = 0;
- __set_bit(id & IDR_MASK, &p->bitmap);
+ __set_bit(id & IDR_MASK, p->bitmap);
/*
* If this layer is full mark the bit in the layer above to
* show that this part of the radix tree is full. This may
* complete the layer above and require walking up the radix
* tree.
*/
- while (p->bitmap == IDR_FULL) {
+ while (bitmap_full(p->bitmap, IDR_SIZE)) {
if (!(p = pa[++l]))
break;
id = id >> IDR_BITS;
- __set_bit((id & IDR_MASK), &p->bitmap);
+ __set_bit((id & IDR_MASK), p->bitmap);
}
}
int n, m, sh;
struct idr_layer *p, *new;
int l, id, oid;
- unsigned long bm;
id = *starting_id;
restart:
* We run around this while until we reach the leaf node...
*/
n = (id >> (IDR_BITS*l)) & IDR_MASK;
- bm = ~p->bitmap;
- m = find_next_bit(&bm, IDR_SIZE, n);
+ m = find_next_zero_bit(p->bitmap, IDR_SIZE, n);
if (m == IDR_SIZE) {
/* no space available go back to previous layer. */
l++;
if (!new)
return -ENOMEM;
new->layer = l-1;
+ new->prefix = id & idr_layer_prefix_mask(new->layer);
rcu_assign_pointer(p->ary[m], new);
p->count++;
}
* upwards.
*/
p->layer++;
+ WARN_ON_ONCE(p->prefix);
continue;
}
if (!(new = idr_layer_alloc(gfp_mask, layer_idr))) {
for (new = p; p && p != idp->top; new = p) {
p = p->ary[0];
new->ary[0] = NULL;
- new->bitmap = new->count = 0;
+ new->count = 0;
+ bitmap_clear(new->bitmap, 0, IDR_SIZE);
__move_to_free_list(idp, new);
}
spin_unlock_irqrestore(&idp->lock, flags);
new->ary[0] = p;
new->count = 1;
new->layer = layers-1;
- if (p->bitmap == IDR_FULL)
- __set_bit(0, &new->bitmap);
+ new->prefix = id & idr_layer_prefix_mask(new->layer);
+ if (bitmap_full(p->bitmap, IDR_SIZE))
+ __set_bit(0, new->bitmap);
p = new;
}
rcu_assign_pointer(idp->top, p);
* @id and @pa are from a successful allocation from idr_get_empty_slot().
* Install the user pointer @ptr and mark the slot full.
*/
-static void idr_fill_slot(void *ptr, int id, struct idr_layer **pa)
+static void idr_fill_slot(struct idr *idr, void *ptr, int id,
+ struct idr_layer **pa)
{
+ /* update hint used for lookup, cleared from free_layer() */
+ rcu_assign_pointer(idr->hint, pa[0]);
+
rcu_assign_pointer(pa[0]->ary[id & IDR_MASK], (struct idr_layer *)ptr);
pa[0]->count++;
idr_mark_full(pa, id);
if (rv < 0)
return rv == -ENOMEM ? -EAGAIN : rv;
- idr_fill_slot(ptr, rv, pa);
+ idr_fill_slot(idp, ptr, rv, pa);
*id = rv;
return 0;
}
if (unlikely(id > max))
return -ENOSPC;
- idr_fill_slot(ptr, id, pa);
+ idr_fill_slot(idr, ptr, id, pa);
return id;
}
EXPORT_SYMBOL_GPL(idr_alloc);
while ((shift > 0) && p) {
n = (id >> shift) & IDR_MASK;
- __clear_bit(n, &p->bitmap);
+ __clear_bit(n, p->bitmap);
*++paa = &p->ary[n];
p = p->ary[n];
shift -= IDR_BITS;
}
n = id & IDR_MASK;
- if (likely(p != NULL && test_bit(n, &p->bitmap))){
- __clear_bit(n, &p->bitmap);
+ if (likely(p != NULL && test_bit(n, p->bitmap))) {
+ __clear_bit(n, p->bitmap);
rcu_assign_pointer(p->ary[n], NULL);
to_free = NULL;
while(*paa && ! --((**paa)->count)){
if (to_free)
- free_layer(to_free);
+ free_layer(idp, to_free);
to_free = **paa;
**paa-- = NULL;
}
if (!*paa)
idp->layers = 0;
if (to_free)
- free_layer(to_free);
+ free_layer(idp, to_free);
} else
idr_remove_warning(id);
}
struct idr_layer *p;
struct idr_layer *to_free;
+ /* see comment in idr_find_slowpath() */
if (WARN_ON_ONCE(id < 0))
return;
p = idp->top->ary[0];
rcu_assign_pointer(idp->top, p);
--idp->layers;
- to_free->bitmap = to_free->count = 0;
- free_layer(to_free);
+ to_free->count = 0;
+ bitmap_clear(to_free->bitmap, 0, IDR_SIZE);
+ free_layer(idp, to_free);
}
while (idp->id_free_cnt >= MAX_IDR_FREE) {
p = get_from_free_list(idp);
/* Get the highest bit that the above add changed from 0->1. */
while (n < fls(id ^ bt_mask)) {
if (p)
- free_layer(p);
+ free_layer(idp, p);
n += IDR_BITS;
p = *--paa;
}
}
EXPORT_SYMBOL(idr_destroy);
-/**
- * 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.
- */
-void *idr_find(struct idr *idp, int id)
+void *idr_find_slowpath(struct idr *idp, int id)
{
int n;
struct idr_layer *p;
+ /*
+ * If @id is negative, idr_find() used to ignore the sign bit and
+ * performed lookup with the rest of bits, which is weird and can
+ * lead to very obscure bugs. We're now returning NULL for all
+ * negative IDs but just in case somebody was depending on the sign
+ * bit being ignored, let's trigger WARN_ON_ONCE() so that they can
+ * be detected and fixed. WARN_ON_ONCE() can later be removed.
+ */
if (WARN_ON_ONCE(id < 0))
return NULL;
}
return((void *)p);
}
-EXPORT_SYMBOL(idr_find);
+EXPORT_SYMBOL(idr_find_slowpath);
/**
* idr_for_each - iterate through all stored pointers
int n;
struct idr_layer *p, *old_p;
+ /* see comment in idr_find_slowpath() */
if (WARN_ON_ONCE(id < 0))
return ERR_PTR(-EINVAL);
}
n = id & IDR_MASK;
- if (unlikely(p == NULL || !test_bit(n, &p->bitmap)))
+ if (unlikely(p == NULL || !test_bit(n, p->bitmap)))
return ERR_PTR(-ENOENT);
old_p = p->ary[n];
/* clear full bits while looking up the leaf idr_layer */
while ((shift > 0) && p) {
n = (idr_id >> shift) & IDR_MASK;
- __clear_bit(n, &p->bitmap);
+ __clear_bit(n, p->bitmap);
p = p->ary[n];
shift -= IDR_BITS;
}
goto err;
n = idr_id & IDR_MASK;
- __clear_bit(n, &p->bitmap);
+ __clear_bit(n, p->bitmap);
bitmap = (void *)p->ary[n];
if (!test_bit(offset, bitmap->bitmap))
/* update bitmap and remove it if empty */
__clear_bit(offset, bitmap->bitmap);
if (--bitmap->nr_busy == 0) {
- __set_bit(n, &p->bitmap); /* to please idr_remove() */
+ __set_bit(n, p->bitmap); /* to please idr_remove() */
idr_remove(&ida->idr, idr_id);
free_bitmap(ida, bitmap);
}
projects / platform / adaptation / renesas_rcar / renesas_kernel.git / blobdiff