[PATCH 0/7 V3] idr: fix & cleanup

[PATCH 0/7 V3] idr: fix & cleanup

[Lai Jiangshan]

Patch1 fix a bug caused by overflow.
Patch2,3 add checks for unallocated_id.
Patch4 changes to returned error code
Patch5-7 cleanup.

All patches are acked by Tejun.

Thanks
Lai

Lai Jiangshan (7):
  idr: fix overflow bug during maximum ID calculation at maximum height
  idr: fix unexpected ID-removal when idr_remove(unallocated_id)
  idr: fix NULL pointer dereference when ida_remove(unallocated_id)
  idr: fix idr_replace()'s returned error code
  idr: don't need to shink the free list when idr_remove()
  idr: reduce the unneeded check in free_layer()
  idr: remove useless #ifndef TEST

 lib/idr.c |   42 +++++++++++++++---------------------------
 1 files changed, 15 insertions(+), 27 deletions(-)

-- 
1.7.4.4

[PATCH 1/7 V3] idr: fix overflow bug during maximum ID calculation at maximum height

[Lai Jiangshan]

idr_replace() open-codes the logic to calculate the maximum valid ID
given the height of the idr tree; unfortunately, the open-coded logic
doesn't account for the fact that the top layer may have unused slots
and over-shifts the limit to zero when the tree is at its maximum
height.

The following test code shows it fails to replace the value for id=((1<<27)+42):

static void test5(void)
{
	int id;
	DEFINE_IDR(test_idr);
#define TEST5_START ((1<<27)+42) /* use the highest layer */

	printk(KERN_INFO "Start test5\n");
	id = idr_alloc(&test_idr, (void *)1, TEST5_START, 0, GFP_KERNEL);
	BUG_ON(id != TEST5_START);
	TEST_BUG_ON(idr_replace(&test_idr, (void *)2, TEST5_START) != (void *)1);
	idr_destroy(&test_idr);
	printk(KERN_INFO "End of test5\n");
}

Fix the bug by using idr_max() which correctly takes into account the
maximum allowed shift.

sub_alloc() shares the same problem and may incorrectly fail with
-EAGAIN; however, this bug doesn't affect correct operation because
idr_get_empty_slot(), which already uses idr_max(), retries with the
increased @id in such cases.

tj: Updated patch description.

CC: stable@vger.kernel.org
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    8 +++-----
 1 files changed, 3 insertions(+), 5 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 2642fa8..4df6792 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -249,7 +249,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 -EAGAIN;
 			}
@@ -811,12 +811,10 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
 	if (!p)
 		return ERR_PTR(-EINVAL);
 
-	n = (p->layer+1) * IDR_BITS;
-
-	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;
-- 
1.7.4.4

[PATCH 2/7 V3] idr: fix unexpected ID-removal when idr_remove(unallocated_id)

[Lai Jiangshan]

If unallocated_id = (ANY * idr_max(idp->layers) + existing_id) is passed
to idr_remove(). The existing_id will be removed unexpectedly.

The following test shows this unexpected id-removal:

static void test4(void)
{
	int id;
	DEFINE_IDR(test_idr);

	printk(KERN_INFO "Start test4\n");
	id = idr_alloc(&test_idr, (void *)1, 42, 43, GFP_KERNEL);
	BUG_ON(id != 42);
	idr_remove(&test_idr, 42 + IDR_SIZE);
	TEST_BUG_ON(idr_find(&test_idr, 42) != (void *)1);
	idr_destroy(&test_idr);
	printk(KERN_INFO "End of test4\n");
}

ida_remove() shares the similar problem.

It happens only when the caller tries to free an unallocated ID which
is the caller's fault. It is not a bug. But it is better to add
the proper check and complain rather than removing an existing_id silently.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    8 ++++++++
 1 files changed, 8 insertions(+), 0 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 4df6792..c4afd94 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -562,6 +562,11 @@ void idr_remove(struct idr *idp, int id)
 	if (id < 0)
 		return;
 
+	if (id > idr_max(idp->layers)) {
+		idr_remove_warning(id);
+		return;
+	}
+
 	sub_remove(idp, (idp->layers - 1) * IDR_BITS, id);
 	if (idp->top && idp->top->count == 1 && (idp->layers > 1) &&
 	    idp->top->ary[0]) {
@@ -1025,6 +1030,9 @@ void ida_remove(struct ida *ida, int id)
 	int n;
 	struct ida_bitmap *bitmap;
 
+	if (idr_id > idr_max(ida->idr.layers))
+		goto err;
+
 	/* clear full bits while looking up the leaf idr_layer */
 	while ((shift > 0) && p) {
 		n = (idr_id >> shift) & IDR_MASK;
-- 
1.7.4.4

[PATCH 3/7 V3] idr: fix NULL pointer dereference when ida_remove(unallocated_id)

[Lai Jiangshan]

If the ida has at least one existing id, and when an unallocated ID which
meets a certain condition is passed to the ida_remove(), the system will crash
because it hits NULL pointer dereference.

The condition is that the unallocated ID shares the same lowest idr layer with
the existing ID, but the idr slot would be different if the unallocated ID
were to be allocated.

In this case the matching idr slot for the unallocated_id is NULL,
causing @bitmap to be NULL which the function dereferences without
checking crashing the kernel.

See the test code:

static void test3(void)
{
	int id;
	DEFINE_IDA(test_ida);

	printk(KERN_INFO "Start test3\n");
	if (ida_pre_get(&test_ida, GFP_KERNEL) < 0) return;
	if (ida_get_new(&test_ida,  &id) < 0) return;
	ida_remove(&test_ida, 4000); /* bug: null deference here */
	printk(KERN_INFO "End of test3\n");
}

It happens only when the caller tries to free an unallocated ID which
is the caller's fault. It is not a bug. But it is better to add
the proper check and complain rather than crashing the kernel.

tj: Updated patch description.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index c4afd94..36ff732 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1048,7 +1048,7 @@ void ida_remove(struct ida *ida, int id)
 	__clear_bit(n, p->bitmap);
 
 	bitmap = (void *)p->ary[n];
-	if (!test_bit(offset, bitmap->bitmap))
+	if (!bitmap || !test_bit(offset, bitmap->bitmap))
 		goto err;
 
 	/* update bitmap and remove it if empty */
-- 
1.7.4.4

[PATCH 4/7 V3] idr: fix idr_replace()'s returned error code

[Lai Jiangshan]

When the smaller id is not found, idr_replace() returns -ENOENT.
But when the id is bigger enough, idr_replace() returns -EINVAL,
actually there is no difference between these two kinds of ids.

These are all unallocated id, the return values of the idr_replace()
for these ids should be the same: -ENOENT.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 36ff732..e79e051 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -814,10 +814,10 @@ void *idr_replace(struct idr *idp, void *ptr, int id)
 
 	p = idp->top;
 	if (!p)
-		return ERR_PTR(-EINVAL);
+		return ERR_PTR(-ENOENT);
 
 	if (id > idr_max(p->layer + 1))
-		return ERR_PTR(-EINVAL);
+		return ERR_PTR(-ENOENT);
 
 	n = p->layer * IDR_BITS;
 	while ((n > 0) && p) {
-- 
1.7.4.4

[PATCH 5/7 V3] idr: don't need to shink the free list when idr_remove()

[Lai Jiangshan]

After idr subsystem is changed to RCU-awared, the free layer will not go to
the free list. The free list will not be filled up when idr_remove().
So we don't need to shink it too.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |   16 ----------------
 1 files changed, 0 insertions(+), 16 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index e79e051..9ed37a7 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -18,12 +18,6 @@
  * pointer or what ever, we treat it as a (void *).  You can pass this
  * id to a user for him to pass back at a later time.  You then pass
  * that id to this code and it returns your pointer.
-
- * You can release ids at any time. When all ids are released, most of
- * the memory is returned (we keep MAX_IDR_FREE) in a local pool so we
- * don't need to go to the memory "store" during an id allocate, just
- * so you don't need to be too concerned about locking and conflicts
- * with the slab allocator.
  */
 
 #ifndef TEST                        // to test in user space...
@@ -584,16 +578,6 @@ void idr_remove(struct idr *idp, int id)
 		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);
-		/*
-		 * Note: we don't call the rcu callback here, since the only
-		 * layers that fall into the freelist are those that have been
-		 * preallocated.
-		 */
-		kmem_cache_free(idr_layer_cache, p);
-	}
-	return;
 }
 EXPORT_SYMBOL(idr_remove);
 
-- 
1.7.4.4

[PATCH 6/7 V3] idr: reduce the unneeded check in free_layer()

[Lai Jiangshan]

If "idr->hint == p" is true, it also implies "idr->hint" is true(not NULL).

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 9ed37a7..39158ab 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -145,7 +145,7 @@ static void idr_layer_rcu_free(struct rcu_head *head)
 
 static inline void free_layer(struct idr *idr, struct idr_layer *p)
 {
-	if (idr->hint && idr->hint == p)
+	if (idr->hint == p)
 		RCU_INIT_POINTER(idr->hint, NULL);
 	call_rcu(&p->rcu_head, idr_layer_rcu_free);
 }
-- 
1.7.4.4

[PATCH 7/7 V3] idr: remove useless #ifndef TEST

[Lai Jiangshan]

"#ifndef TEST" can't work for user space test now, just remove it.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
Acked-by: Tejun Heo <tj@kernel.org>
---
 lib/idr.c |    2 --
 1 files changed, 0 insertions(+), 2 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 39158ab..96bb252 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -20,11 +20,9 @@
  * that id to this code and it returns your pointer.
  */
 
-#ifndef TEST                        // to test in user space...
 #include <linux/slab.h>
 #include <linux/init.h>
 #include <linux/export.h>
-#endif
 #include <linux/err.h>
 #include <linux/string.h>
 #include <linux/idr.h>
-- 
1.7.4.4