1 files changed, 55 insertions, 46 deletions

diff --git a/lib/idr.c b/lib/idr.c
index 1cac726c44bc..e15502e8b21e 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -106,16 +106,17 @@ static void idr_mark_full(struct idr_layer **pa, int id)
 }
 
 /**
- * idr_pre_get - reserver resources for idr allocation
+ * idr_pre_get - reserve resources for idr allocation
  * @idp:        idr handle
  * @gfp_mask:   memory allocation flags
  *
- * This function should be called prior to locking and calling the
- * idr_get_new* functions. It preallocates enough memory to satisfy
- * the worst possible allocation.
+ * This function should be called prior to calling the idr_get_new* functions.
+ * It preallocates enough memory to satisfy the worst possible allocation. The
+ * caller should pass in GFP_KERNEL if possible.  This of course requires that
+ * no spinning locks be held.
  *
- * If the system is REALLY out of memory this function returns 0,
- * otherwise 1.
+ * If the system is REALLY out of memory this function returns %0,
+ * otherwise %1.
  */
 int idr_pre_get(struct idr *idp, gfp_t gfp_mask)
 {
@@ -156,10 +157,12 @@ 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 (!(p = pa[l])) {
+                        if (id >= 1 << (idp->layers * IDR_BITS)) {
                                 *starting_id = id;
                                 return IDR_NEED_TO_GROW;
                         }
+                        p = pa[l];
+                        BUG_ON(!p);
 
                         /* If we need to go up one layer, continue the
                          * loop; otherwise, restart from the top.
@@ -282,17 +285,19 @@ static int idr_get_new_above_int(struct idr *idp, void *ptr, int starting_id)
  * idr_get_new_above - allocate new idr entry above or equal to a start id
  * @idp: idr handle
  * @ptr: pointer you want associated with the id
- * @start_id: id to start search at
+ * @starting_id: id to start search at
  * @id: pointer to the allocated handle
  *
  * This is the allocate id function.  It should be called with any
  * required locks.
  *
- * If memory is required, it will return -EAGAIN, you should unlock
- * and go back to the idr_pre_get() call.  If the idr is full, it will
- * return -ENOSPC.
+ * If allocation from IDR's private freelist fails, idr_get_new_above() will
+ * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
+ * IDR's preallocation and then retry the idr_get_new_above() call.
+ *
+ * If the idr is full idr_get_new_above() will return %-ENOSPC.
  *
- * @id returns a value in the range @starting_id ... 0x7fffffff
+ * @id returns a value in the range @starting_id ... %0x7fffffff
  */
 int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id)
 {
@@ -316,14 +321,13 @@ EXPORT_SYMBOL(idr_get_new_above);
  * @ptr: pointer you want associated with the id
  * @id: pointer to the allocated handle
  *
- * This is the allocate id function.  It should be called with any
- * required locks.
+ * If allocation from IDR's private freelist fails, idr_get_new_above() will
+ * return %-EAGAIN.  The caller should retry the idr_pre_get() call to refill
+ * IDR's preallocation and then retry the idr_get_new_above() call.
  *
- * If memory is required, it will return -EAGAIN, you should unlock
- * and go back to the idr_pre_get() call.  If the idr is full, it will
- * return -ENOSPC.
+ * If the idr is full idr_get_new_above() will return %-ENOSPC.
  *
- * @id returns a value in the range 0 ... 0x7fffffff
+ * @id returns a value in the range %0 ... %0x7fffffff
  */
 int idr_get_new(struct idr *idp, void *ptr, int *id)
 {
@@ -386,7 +390,7 @@ static void sub_remove(struct idr *idp, int shift, int id)
 }
 
 /**
- * idr_remove - remove the given id and free it's slot
+ * idr_remove - remove the given id and free its slot
  * @idp: idr handle
  * @id: unique key
  */
@@ -435,7 +439,7 @@ EXPORT_SYMBOL(idr_remove);
  * function will remove all id mappings and leave all idp_layers
  * unused.
  *
- * A typical clean-up sequence for objects stored in an idr tree, will
+ * A typical clean-up sequence for objects stored in an idr tree will
  * use idr_for_each() to free all objects, if necessay, then
  * idr_remove_all() to remove all ids, and idr_destroy() to free
  * up the cached idr_layers.
@@ -443,6 +447,7 @@ EXPORT_SYMBOL(idr_remove);
 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 **paa = &pa[0];
@@ -460,8 +465,10 @@ void idr_remove_all(struct idr *idp)
                         p = p->ary[(id >> n) & IDR_MASK];
                 }
 
+                bt_mask = id;
                 id += 1 << n;
-                while (n < fls(id)) {
+                /* Get the highest bit that the above add changed from 0->1. */
+                while (n < fls(id ^ bt_mask)) {
                         if (p)
                                 free_layer(p);
                         n += IDR_BITS;
@@ -474,7 +481,7 @@ EXPORT_SYMBOL(idr_remove_all);
 
 /**
  * idr_destroy - release all cached layers within an idr tree
- * idp: idr handle
+ * @idp: idr handle
  */
 void idr_destroy(struct idr *idp)
 {
@@ -502,7 +509,7 @@ void *idr_find(struct idr *idp, int id)
         int n;
         struct idr_layer *p;
 
-        p = rcu_dereference(idp->top);
+        p = rcu_dereference_raw(idp->top);
         if (!p)
                 return NULL;
         n = (p->layer+1) * IDR_BITS;
@@ -517,7 +524,7 @@ void *idr_find(struct idr *idp, int id)
         while (n > 0 && p) {
                 n -= IDR_BITS;
                 BUG_ON(n != p->layer*IDR_BITS);
-                p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
+                p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
         }
         return((void *)p);
 }
@@ -537,7 +544,7 @@ EXPORT_SYMBOL(idr_find);
  * not allowed.
  *
  * We check the return of @fn each time. If it returns anything other
- * than 0, we break out and return that value.
+ * than %0, we break out and return that value.
  *
  * The caller must serialize idr_for_each() vs idr_get_new() and idr_remove().
  */
@@ -550,7 +557,7 @@ int idr_for_each(struct idr *idp,
         struct idr_layer **paa = &pa[0];
 
         n = idp->layers * IDR_BITS;
-        p = rcu_dereference(idp->top);
+        p = rcu_dereference_raw(idp->top);
         max = 1 << n;
 
         id = 0;
@@ -558,7 +565,7 @@ int idr_for_each(struct idr *idp,
                 while (n > 0 && p) {
                         n -= IDR_BITS;
                         *paa++ = p;
-                        p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
+                        p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
                 }
 
                 if (p) {
@@ -581,10 +588,11 @@ EXPORT_SYMBOL(idr_for_each);
 /**
  * idr_get_next - lookup next object of id to given id.
  * @idp: idr handle
- * @id:  pointer to lookup key
+ * @nextidp:  pointer to lookup key
  *
  * Returns pointer to registered object with id, which is next number to
- * given id.
+ * given id. After being looked up, *@nextidp will be updated for the next
+ * iteration.
  */
 
 void *idr_get_next(struct idr *idp, int *nextidp)
@@ -597,7 +605,7 @@ void *idr_get_next(struct idr *idp, int *nextidp)
         /* find first ent */
         n = idp->layers * IDR_BITS;
         max = 1 << n;
-        p = rcu_dereference(idp->top);
+        p = rcu_dereference_raw(idp->top);
         if (!p)
                 return NULL;
 
@@ -605,7 +613,7 @@ void *idr_get_next(struct idr *idp, int *nextidp)
                 while (n > 0 && p) {
                         n -= IDR_BITS;
                         *paa++ = p;
-                        p = rcu_dereference(p->ary[(id >> n) & IDR_MASK]);
+                        p = rcu_dereference_raw(p->ary[(id >> n) & IDR_MASK]);
                 }
 
                 if (p) {
@@ -621,7 +629,7 @@ void *idr_get_next(struct idr *idp, int *nextidp)
         }
         return NULL;
 }
-
+EXPORT_SYMBOL(idr_get_next);
 
 
 /**
@@ -631,8 +639,8 @@ void *idr_get_next(struct idr *idp, int *nextidp)
  * @id: lookup key
  *
  * Replace the pointer registered with an id and return the old value.
- * A -ENOENT return indicates that @id was not found.
- * A -EINVAL return indicates that @id was not within valid constraints.
+ * A %-ENOENT return indicates that @id was not found.
+ * A %-EINVAL return indicates that @id was not within valid constraints.
  *
  * The caller must serialize with writers.
  */
@@ -690,10 +698,11 @@ void idr_init(struct idr *idp)
 EXPORT_SYMBOL(idr_init);
 
 
-/*
+/**
+ * DOC: IDA description
  * IDA - IDR based ID allocator
  *
- * this is id allocator without id -> pointer translation.  Memory
+ * This is id allocator without id -> pointer translation.  Memory
  * usage is much lower than full blown idr because each id only
  * occupies a bit.  ida uses a custom leaf node which contains
  * IDA_BITMAP_BITS slots.
@@ -726,8 +735,8 @@ static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
  * following function.  It preallocates enough memory to satisfy the
  * worst possible allocation.
  *
- * If the system is REALLY out of memory this function returns 0,
- * otherwise 1.
+ * If the system is REALLY out of memory this function returns %0,
+ * otherwise %1.
  */
 int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
 {
@@ -753,17 +762,17 @@ EXPORT_SYMBOL(ida_pre_get);
 /**
  * ida_get_new_above - allocate new ID above or equal to a start id
  * @ida:        ida handle
- * @staring_id: id to start search at
+ * @starting_id: id to start search at
  * @p_id:       pointer to the allocated handle
  *
  * Allocate new ID above or equal to @ida.  It should be called with
  * any required locks.
  *
- * If memory is required, it will return -EAGAIN, you should unlock
+ * If memory is required, it will return %-EAGAIN, you should unlock
  * and go back to the ida_pre_get() call.  If the ida is full, it will
- * return -ENOSPC.
+ * return %-ENOSPC.
  *
- * @p_id returns a value in the range @starting_id ... 0x7fffffff.
+ * @p_id returns a value in the range @starting_id ... %0x7fffffff.
  */
 int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 {
@@ -845,11 +854,11 @@ EXPORT_SYMBOL(ida_get_new_above);
  *
  * Allocate new ID.  It should be called with any required locks.
  *
- * If memory is required, it will return -EAGAIN, you should unlock
+ * If memory is required, it will return %-EAGAIN, you should unlock
  * and go back to the idr_pre_get() call.  If the idr is full, it will
- * return -ENOSPC.
+ * return %-ENOSPC.
  *
- * @id returns a value in the range 0 ... 0x7fffffff.
+ * @id returns a value in the range %0 ... %0x7fffffff.
  */
 int ida_get_new(struct ida *ida, int *p_id)
 {
@@ -907,7 +916,7 @@ EXPORT_SYMBOL(ida_remove);
 
 /**
  * ida_destroy - release all cached layers within an ida tree
- * ida:         ida handle
+ * @ida:                ida handle
  */
 void ida_destroy(struct ida *ida)
 {