#include <linux/percpu.h>
#include <linux/hardirq.h>
+#define MAX_IDR_SHIFT (sizeof(int) * 8 - 1)
+#define MAX_IDR_BIT (1U << MAX_IDR_SHIFT)
+
+/* Leave the possibility of an incomplete final layer */
+#define MAX_IDR_LEVEL ((MAX_IDR_SHIFT + IDR_BITS - 1) / IDR_BITS)
+
+/* Number of id_layer structs to leave in free list */
+#define MAX_IDR_FREE (MAX_IDR_LEVEL * 2)
+
static struct kmem_cache *idr_layer_cache;
static DEFINE_PER_CPU(struct idr_layer *, idr_preload_head);
static DEFINE_PER_CPU(int, idr_preload_cnt);
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_IDR_SHIFT);
+
+ 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++;
}
* Add a new layer to the top of the tree if the requested
* id is larger than the currently allocated space.
*/
- while ((layers < (MAX_IDR_LEVEL - 1)) && (id >= (1 << (layers*IDR_BITS)))) {
+ while (id > idr_max(layers)) {
layers++;
if (!p->count) {
/* special case: if the tree is currently empty,
* 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);
*/
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
{
- struct idr_layer *pa[MAX_IDR_LEVEL];
+ struct idr_layer *pa[MAX_IDR_LEVEL + 1];
int rv;
rv = idr_get_empty_slot(idp, starting_id, pa, 0, idp);
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;
}
int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
{
int max = end > 0 ? end - 1 : INT_MAX; /* inclusive upper limit */
- struct idr_layer *pa[MAX_IDR_LEVEL];
+ struct idr_layer *pa[MAX_IDR_LEVEL + 1];
int id;
might_sleep_if(gfp_mask & __GFP_WAIT);
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);
static void sub_remove(struct idr *idp, int shift, int id)
{
struct idr_layer *p = idp->top;
- struct idr_layer **pa[MAX_IDR_LEVEL];
+ struct idr_layer **pa[MAX_IDR_LEVEL + 1];
struct idr_layer ***paa = &pa[0];
struct idr_layer *to_free;
int n;
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;
- /* Mask off upper bits we don't use for the search. */
- id &= MAX_IDR_MASK;
+ /* see comment in idr_find_slowpath() */
+ if (WARN_ON_ONCE(id < 0))
+ return;
sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
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);
int n, id, max;
int bt_mask;
struct idr_layer *p;
- struct idr_layer *pa[MAX_IDR_LEVEL];
+ struct idr_layer *pa[MAX_IDR_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;
/* 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;
+
p = rcu_dereference_raw(idp->top);
if (!p)
return NULL;
n = (p->layer+1) * IDR_BITS;
- /* Mask off upper bits we don't use for the search. */
- id &= MAX_IDR_MASK;
-
- if (id >= (1 << n))
+ if (id > idr_max(p->layer + 1))
return NULL;
BUG_ON(n == 0);
}
return((void *)p);
}
-EXPORT_SYMBOL(idr_find);
+EXPORT_SYMBOL(idr_find_slowpath);
/**
* idr_for_each - iterate through all stored pointers
{
int n, id, max, error = 0;
struct idr_layer *p;
- struct idr_layer *pa[MAX_IDR_LEVEL];
+ struct idr_layer *pa[MAX_IDR_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;
*/
void *idr_get_next(struct idr *idp, int *nextidp)
{
- struct idr_layer *p, *pa[MAX_IDR_LEVEL];
+ struct idr_layer *p, *pa[MAX_IDR_LEVEL + 1];
struct idr_layer **paa = &pa[0];
int id = *nextidp;
int n, max;
if (!p)
return NULL;
n = (p->layer + 1) * IDR_BITS;
- max = 1 << n;
+ max = idr_max(p->layer + 1);
- while (id < max) {
+ while (id >= 0 && id <= max) {
while (n > 0 && p) {
n -= IDR_BITS;
*paa++ = p;
int n;
struct idr_layer *p, *old_p;
+ /* see comment in idr_find_slowpath() */
+ if (WARN_ON_ONCE(id < 0))
+ return ERR_PTR(-EINVAL);
+
p = idp->top;
if (!p)
return ERR_PTR(-EINVAL);
n = (p->layer+1) * IDR_BITS;
- id &= MAX_IDR_MASK;
-
if (id >= (1 << n))
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];
*/
int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
{
- struct idr_layer *pa[MAX_IDR_LEVEL];
+ struct idr_layer *pa[MAX_IDR_LEVEL + 1];
struct ida_bitmap *bitmap;
unsigned long flags;
int idr_id = starting_id / IDA_BITMAP_BITS;
/* 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