Bluetooth: Verify that l2cap_get_conf_opt provides large enough buffer

[pandora-kernel.git] / lib / idr.c

diff --git a/lib/idr.c b/lib/idr.c
index ed055b2..2d3879b 100644 (file)
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -39,6 +39,14 @@
 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;
@@ -159,7 +167,7 @@ static int sub_alloc(struct idr *idp, int *starting_id, struct idr_layer **pa)
                        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;
                        }
@@ -223,7 +231,7 @@ build_up:
         * 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,
@@ -265,7 +273,7 @@ build_up:
 
 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);
@@ -357,7 +365,7 @@ static void idr_remove_warning(int id)
 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;
@@ -451,16 +459,16 @@ void idr_remove_all(struct idr *idp)
        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;
@@ -519,7 +527,7 @@ void *idr_find(struct idr *idp, int id)
        /* 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);
 
@@ -555,15 +563,15 @@ int idr_for_each(struct idr *idp,
 {
        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;
@@ -595,23 +603,25 @@ EXPORT_SYMBOL(idr_for_each);
  * 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;
@@ -623,7 +633,14 @@ void *idr_get_next(struct idr *idp, int *nextidp)
                        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;
@@ -655,14 +672,12 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
        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;
@@ -778,7 +793,7 @@ EXPORT_SYMBOL(ida_pre_get);
  */
 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;