[PATCH 0/8] idr: fix & cleanup

[PATCH 0/8] 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-8 cleanup.

Lai Jiangshan (8):
  idr: fix overflow bug for the max-high layer
  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: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.
  idr: avoid ping-pong
  idr: don't need to shink the free list when idr_remove()
  idr: reduce the unneeded check in free_layer()

 lib/idr.c |   58 +++++++++++++++++-----------------------------------------
 1 files changed, 17 insertions(+), 41 deletions(-)

-- 
1.7.4.4

[PATCH 1/8] idr: fix overflow bug for the max-high layer

[Lai Jiangshan]

In idr_replace(), when the top layer is the max-high layer(p->layer == 3),
The "(1 << n)" will overflow and the result is 0, it causes idr_replace()
return -EINVAL even the id is actually valid.

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");
}

Fixed the bug by using idr_max() instead of the incorrect open code.

There is the same problem in sub_alloc(). The overflow causes sub_alloc()
returns -EAGAIN unexpectedly. But the idr_get_empty_slot() will call it
again with increased @id. So the bug is hided.

CC: stable@vger.kernel.org
Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 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

Re: [PATCH 1/8] idr: fix overflow bug for the max-high layer

[Tejun Heo]

Hello,

Subject: idr: fix overflow bug during maximum ID calculation at maximum height

On Fri, Apr 18, 2014 at 08:49:48PM +0800, Lai Jiangshan wrote:
> In idr_replace(), when the top layer is the max-high layer(p->layer == 3),
> The "(1 << n)" will overflow and the result is 0, it causes idr_replace()
> return -EINVAL even the id is actually valid.

  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");
> }
> 
> Fixed the bug by using idr_max() instead of the incorrect open code.

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

> There is the same problem in sub_alloc(). The overflow causes sub_alloc()
> returns -EAGAIN unexpectedly. But the idr_get_empty_slot() will call it
> again with increased @id. So the bug is hided.

  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.

> CC: stable@vger.kernel.org
> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>

 Acked-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun

Re: [PATCH 1/8] idr: fix overflow bug for the max-high layer

[Lai Jiangshan]

On Sat, Apr 19, 2014 at 12:29 AM, Tejun Heo <tj@kernel.org> wrote:
> Hello,

Hi,

Should I resend the patch with your updated changelog?
Or something else I need to do?

>
> Subject: idr: fix overflow bug during maximum ID calculation at maximum height
>
> On Fri, Apr 18, 2014 at 08:49:48PM +0800, Lai Jiangshan wrote:
>> In idr_replace(), when the top layer is the max-high layer(p->layer == 3),
>> The "(1 << n)" will overflow and the result is 0, it causes idr_replace()
>> return -EINVAL even the id is actually valid.
>
>   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");
>> }

Does the above testing code need to be kept in the changelog.

Thanks,
Lai

>>
>> Fixed the bug by using idr_max() instead of the incorrect open code.
>
>   Fix the bug by using idr_max() which correctly takes into account the
>   maximum allowed shift.
>
>> There is the same problem in sub_alloc(). The overflow causes sub_alloc()
>> returns -EAGAIN unexpectedly. But the idr_get_empty_slot() will call it
>> again with increased @id. So the bug is hided.
>
>   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.
>
>> CC: stable@vger.kernel.org
>> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
>
>  Acked-by: Tejun Heo <tj@kernel.org>
>
> Thanks.
>
> --
> tejun
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 1/8] idr: fix overflow bug for the max-high layer

[Tejun Heo]

On Sat, Apr 19, 2014 at 01:08:46AM +0800, Lai Jiangshan wrote:
> On Sat, Apr 19, 2014 at 12:29 AM, Tejun Heo <tj@kernel.org> wrote:
> > Hello,
> 
> Hi,
> 
> Should I resend the patch with your updated changelog?
> Or something else I need to do?

Yeah, please resend with the description updated.

> >> 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");
> >> }
> 
> Does the above testing code need to be kept in the changelog.

Yeah, why not?  It makes what's failing very clear.

Thanks.

-- 
tejun

[PATCH 2/8] idr: fix unexpected id-removal when idr_remove(unallocated_id)

[Lai Jiangshan]

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

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");
}

It only happens when unallocated_id, it is caller's fault. It is not
a bug. But it is better to add the proper check and complains instead
of removing an existed_id silently.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |    5 +++++
 1 files changed, 5 insertions(+), 0 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 4df6792..a28036d 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]) {
-- 
1.7.4.4

Re: [PATCH 2/8] idr: fix unexpected id-removal when idr_remove(unallocated_id)

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:49PM +0800, Lai Jiangshan wrote:
> If unallocated_id = (ANY * idr_max(idp->layers) + existed_id) is passed

						    existing_id

> to idr_remove(). The existed_id will be removed unexpected.

                       ditto.

> 
> 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");
> }
> 
> It only happens when unallocated_id, it is caller's fault. It is not
> a bug. But it is better to add the proper check and complains instead

							complain

> of removing an existed_id silently.

                existing_id

> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>

Acked-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun

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

[Lai Jiangshan]

If the ida has at least one existed_id, and when an special unallocated_id
is passed to the ida_remove(), the system will crash because it hits NULL
pointer dereference.

This special unallocated_id is that it shares the same lowest idr layer with
an exsited_id, but the idr slot is different(if the unallocated_id is allocated).
In this case the supposed idr slot of the unallocated_id is NULL,
It means @bitmap == NULL, and when the code dereference it, it crash 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 only happens when unallocated_id, it is caller's fault. It is not
a bug. But it is better to add the proper check and complains instead
of crashing the kernel.

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

diff --git a/lib/idr.c b/lib/idr.c
index a28036d..d200d67 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1045,7 +1045,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

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

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:50PM +0800, Lai Jiangshan wrote:
> If the ida has at least one existed_id, and when an special unallocated_id

		existing id or allocated id

					  when an unallocated id which
					  meets a certain condition is passed to...

> is passed to the ida_remove(), the system will crash because it hits NULL
> pointer dereference.
> 
> This special unallocated_id is that it shares the same lowest idr layer with

The condition is that the ID shares the...

> an exsited_id, but the idr slot is different(if the unallocated_id is allocated).

the existing ID,                  would be different if the unallocated ID were to be allocated.

> In this case the supposed idr slot of the unallocated_id is NULL,

                   matching          for

> It means @bitmap == NULL, and when the code dereference it, it crash the kernel.

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 only happens when unallocated_id, it is caller's fault. It is not

It happens only when the caller tries to free an unallocated ID which
is the caller's fault.

> a bug. But it is better to add the proper check and complains instead

                                                  and complain rather than crashing the kernel

> of crashing the kernel.
> 
> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>

Acked-by: Tejun Heo <tj@kernel.org>

Thanks.

-- 
tejun

[PATCH 4/8] 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>
---
 lib/idr.c |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index d200d67..104f87f 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

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

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:51PM +0800, Lai Jiangshan wrote:
> 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>

Thanks.

-- 
tejun

[PATCH 5/8] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Lai Jiangshan]

When the arguments passed by the caller are invalid, WARN_ON_ONCE()
is proper than BUG_ON() which may crash the kernel.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |    9 +++++----
 1 files changed, 5 insertions(+), 4 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 104f87f..e4f9965 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1093,13 +1093,14 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 	unsigned int max;
 	unsigned long flags;
 
-	BUG_ON((int)start < 0);
-	BUG_ON((int)end < 0);
+	if (WARN_ON_ONCE(((int)start < 0) || ((int)end < 0)))
+		return -EINVAL;
 
 	if (end == 0)
 		max = 0x80000000;
 	else {
-		BUG_ON(end < start);
+		if (WARN_ON_ONCE(end < start))
+			return -EINVAL;
 		max = end - 1;
 	}
 
@@ -1135,7 +1136,7 @@ void ida_simple_remove(struct ida *ida, unsigned int id)
 {
 	unsigned long flags;
 
-	BUG_ON((int)id < 0);
+	WARN_ON_ONCE((int)id < 0);
 	spin_lock_irqsave(&simple_ida_lock, flags);
 	ida_remove(ida, id);
 	spin_unlock_irqrestore(&simple_ida_lock, flags);
-- 
1.7.4.4

Re: [PATCH 5/8] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:52PM +0800, Lai Jiangshan wrote:
> @@ -1135,7 +1136,7 @@ void ida_simple_remove(struct ida *ida, unsigned int id)
>  {
>  	unsigned long flags;
>  
> -	BUG_ON((int)id < 0);
> +	WARN_ON_ONCE((int)id < 0);

Shouldn't this be moved to ida_remove()?  Also, it probably should
return afterwards?

Thanks.

-- 
tejun

[PATCH 6/8] idr: avoid ping-pong

[Lai Jiangshan]

The ida callers always calls ida_pre_get() before ida_get_new*().
ida_pre_get() will do layer allocation, and ida_get_new*() will do layer removal.

It causes an unneeded ping-pong. The speculative layer removal in
ida_get_new*() can't result expected optimization.

So we remove the unneeded layer removal in ida_get_new*().

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |   11 -----------
 1 files changed, 0 insertions(+), 11 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index e4f9965..be0b6ff 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1001,17 +1001,6 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 
 	*p_id = id;
 
-	/* Each leaf node can handle nearly a thousand slots and the
-	 * whole idea of ida is to have small memory foot print.
-	 * Throw away extra resources one by one after each successful
-	 * allocation.
-	 */
-	if (ida->idr.id_free_cnt || ida->free_bitmap) {
-		struct idr_layer *p = get_from_free_list(&ida->idr);
-		if (p)
-			kmem_cache_free(idr_layer_cache, p);
-	}
-
 	return 0;
 }
 EXPORT_SYMBOL(ida_get_new_above);
-- 
1.7.4.4

Re: [PATCH 6/8] idr: avoid ping-pong

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:53PM +0800, Lai Jiangshan wrote:
> The ida callers always calls ida_pre_get() before ida_get_new*().
> ida_pre_get() will do layer allocation, and ida_get_new*() will do layer removal.
> 
> It causes an unneeded ping-pong. The speculative layer removal in
> ida_get_new*() can't result expected optimization.
> 
> So we remove the unneeded layer removal in ida_get_new*().

But the as comment says, ida doesn't want to keep extra layers around
as it wants to keep its memory footprint minimal.  I think the right
thing to do is implementing ida_preload() which is simliar to
idr_preload() and do away with per-ida layer cache.

Thanks.

-- 
tejun

Re: [PATCH 6/8] idr: avoid ping-pong

[Lai Jiangshan]

On 04/19/2014 01:17 AM, Tejun Heo wrote:
> On Fri, Apr 18, 2014 at 08:49:53PM +0800, Lai Jiangshan wrote:
>> The ida callers always calls ida_pre_get() before ida_get_new*().
>> ida_pre_get() will do layer allocation, and ida_get_new*() will do layer removal.
>>
>> It causes an unneeded ping-pong. The speculative layer removal in
>> ida_get_new*() can't result expected optimization.
>>
>> So we remove the unneeded layer removal in ida_get_new*().
> 
> But the as comment says, ida doesn't want to keep extra layers around
> as it wants to keep its memory footprint minimal.  

It only frees one layer. And the ida_pre_get() for the next ida_get_new*()
will allocation it back again. The aim "Throw away extra resources one by one"
can't be achieved. It can't keep its memory footprint minimal.


> I think the right
> thing to do is implementing ida_preload() which is simliar to
> idr_preload() and do away with per-ida layer cache.

Yes and no.

We need a static private ida_preload() for ida_simple_get() only.

Because the IDA doesn't have any query-function, so IDA's own synchronization
is enough for all use cases, IDA should off-loads the caller's
synchronization burden.

In my todo-list, IDA only needs the following functions. other functions
will be deprecated and scheduled to be removed:
	void ida_destroy(struct ida *ida);
	void ida_init(struct ida *ida);
	int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
			   gfp_t gfp_mask);
	void ida_simple_remove(struct ida *ida, unsigned int id);

(I don't think we need any query-function, But...)
If in the future we need some query-functions such as:
	ida_is_this_id_allocated()
	ida_find_next_[un]allocated_id(),
In this case, we can expose the ida_preload() and ida_alloc() at the same time that
we introduce the query-functions.

Any thought?

But we need to remove this unneeded ping-pong despite of any plan.

Thanks,
Lai

Re: [PATCH 6/8] idr: avoid ping-pong

[Tejun Heo]

Hello,

On Sat, Apr 19, 2014 at 06:43:41PM +0800, Lai Jiangshan wrote:
> On 04/19/2014 01:17 AM, Tejun Heo wrote:
> It only frees one layer. And the ida_pre_get() for the next ida_get_new*()
> will allocation it back again. The aim "Throw away extra resources one by one"
> can't be achieved. It can't keep its memory footprint minimal.

Isn't the point not keeping the memory around per-ida between
allocations which can be arbitrarily long?  Why isn't it achieved?

> > I think the right
> > thing to do is implementing ida_preload() which is simliar to
> > idr_preload() and do away with per-ida layer cache.
> 
> Yes and no.
> 
> We need a static private ida_preload() for ida_simple_get() only.
> 
> Because the IDA doesn't have any query-function, so IDA's own synchronization
> is enough for all use cases, IDA should off-loads the caller's
> synchronization burden.

Hmmm?  And why can't that use preload on its own?

> In my todo-list, IDA only needs the following functions. other functions
> will be deprecated and scheduled to be removed:
> 	void ida_destroy(struct ida *ida);
> 	void ida_init(struct ida *ida);
> 	int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
> 			   gfp_t gfp_mask);
> 	void ida_simple_remove(struct ida *ida, unsigned int id);
> 
> (I don't think we need any query-function, But...)
> If in the future we need some query-functions such as:
> 	ida_is_this_id_allocated()
> 	ida_find_next_[un]allocated_id(),
> In this case, we can expose the ida_preload() and ida_alloc() at the same time that
> we introduce the query-functions.

Regardless of interface, we can still switch to per-cpu layer caching
which would make this per-ida allocation issue go away.  I'd much
prefer to see that than debating the (dis)merits of this patch.

Thanks.

-- 
tejun

Re: [PATCH 6/8] idr: avoid ping-pong

[Lai Jiangshan]

On Sat, Apr 19, 2014 at 9:01 PM, Tejun Heo <tj@kernel.org> wrote:
> Hello,
>
> On Sat, Apr 19, 2014 at 06:43:41PM +0800, Lai Jiangshan wrote:
>> On 04/19/2014 01:17 AM, Tejun Heo wrote:
>> It only frees one layer. And the ida_pre_get() for the next ida_get_new*()
>> will allocation it back again. The aim "Throw away extra resources one by one"
>> can't be achieved. It can't keep its memory footprint minimal.
>
> Isn't the point not keeping the memory around per-ida between
> allocations which can be arbitrarily long?  Why isn't it achieved?

"Throw away one layer" is achieved.
"one by one" can't be achieved.

>
>> > I think the right
>> > thing to do is implementing ida_preload() which is simliar to
>> > idr_preload() and do away with per-ida layer cache.
>>
>> Yes and no.

Yes: I agree to add ida_preload().
No: Because I think we don't need to expose ida_preload().

>>
>> We need a static private ida_preload() for ida_simple_get() only.
>>
>> Because the IDA doesn't have any query-function, so IDA's own synchronization
>> is enough for all use cases, IDA should off-loads the caller's
>> synchronization burden.
>
> Hmmm?  And why can't that use preload on its own?

We need to use  preload  for ida_simple_get().
But we don't need to expose the ida_preload() if we kill the
ida_get_new*() APIs.
(The reason why we can kill the ida_get_new*() is explained below.)

>
>> In my todo-list, IDA only needs the following functions. other functions
>> will be deprecated and scheduled to be removed:
>>       void ida_destroy(struct ida *ida);
>>       void ida_init(struct ida *ida);
>>       int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
>>                          gfp_t gfp_mask);
>>       void ida_simple_remove(struct ida *ida, unsigned int id);
>>
>> (I don't think we need any query-function, But...)
>> If in the future we need some query-functions such as:
>>       ida_is_this_id_allocated()
>>       ida_find_next_[un]allocated_id(),
>> In this case, we can expose the ida_preload() and ida_alloc() at the same time that
>> we introduce the query-functions.
>
> Regardless of interface, we can still switch to per-cpu layer caching
> which would make this per-ida allocation issue go away.

agree.

>  I'd much
> prefer to see that than debating the (dis)merits of this patch.

agree.

Please drop this patch.
It will be better if we will cleanup it(and all free list related code)
after ida_preload() is added.

Thanks
Lai

>
> Thanks.
>
> --
> tejun
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

[PATCH 7/8] 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.

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

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |   17 -----------------
 1 files changed, 0 insertions(+), 17 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index be0b6ff..314ea5f 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -18,19 +18,11 @@
  * 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...
 #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>
@@ -584,15 +576,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

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

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:54PM +0800, Lai Jiangshan wrote:
> 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.
> 
> "#ifndef TEST" can't work for user space test now, just remove it.

Maybe put this in a separate patch?

> Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>

Acked-by: Tejun Heo <tj@kernel.org>

-- 
tejun

[PATCH 8/8] 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>
---
 lib/idr.c |    2 +-
 1 files changed, 1 insertions(+), 1 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 314ea5f..08d010c 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -143,7 +143,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

Re: [PATCH 8/8] idr: reduce the unneeded check in free_layer()

[Tejun Heo]

On Fri, Apr 18, 2014 at 08:49:55PM +0800, Lai Jiangshan wrote:
> 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>

Thanks.

-- 
tejun

[PATCH 0/9 V2] 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-9 cleanup.


Lai Jiangshan (9):
  idr: fix overflow bug during maximum ID calculation at maximum height
  idr: fix unexpected ID-removal when idr_remove(unallocated_id)
**^^also consider ida_remove()
  idr: fix NULL pointer dereference when ida_remove(unallocated_id)
  idr: fix idr_replace()'s returned error code
  idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.
**^^move the test into ida_remove() as tj suggested.
  idr: avoid ping-pong
  idr: don't need to shink the free list when idr_remove()
**^^split
  idr: reduce the unneeded check in free_layer()
  idr: remove useless C-PreProcessor branch
**^^new

 lib/idr.c |   66 +++++++++++++++++++++---------------------------------------
 1 files changed, 23 insertions(+), 43 deletions(-)

-- 
1.7.4.4

[PATCH 1/9 V2] 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/9 V2] 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/9 V2] 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/9 V2] 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/9 V2] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Lai Jiangshan]

When the arguments passed by the caller are invalid, WARN_ON_ONCE()
is proper than BUG_ON() which may crash the kernel.

The invalid-checking for ida_simple_remove() is moved into ida_remove().
idr_remove() also adds this WARN_ON_ONCE().

And when "end < start" in ida_simple_get(), it returns -ENOSPC as
ida_alloc() does.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |   13 ++++++++-----
 1 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index e79e051..317fd35 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -559,7 +559,7 @@ void idr_remove(struct idr *idp, int id)
 	struct idr_layer *p;
 	struct idr_layer *to_free;
 
-	if (id < 0)
+	if (WARN_ON_ONCE(id < 0))
 		return;
 
 	if (id > idr_max(idp->layers)) {
@@ -1030,6 +1030,9 @@ void ida_remove(struct ida *ida, int id)
 	int n;
 	struct ida_bitmap *bitmap;
 
+	if (WARN_ON_ONCE(id < 0))
+		return;
+
 	if (idr_id > idr_max(ida->idr.layers))
 		goto err;
 
@@ -1096,13 +1099,14 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
 	unsigned int max;
 	unsigned long flags;
 
-	BUG_ON((int)start < 0);
-	BUG_ON((int)end < 0);
+	if (WARN_ON_ONCE(((int)start < 0) || ((int)end < 0)))
+		return -EINVAL;
 
 	if (end == 0)
 		max = 0x80000000;
 	else {
-		BUG_ON(end < start);
+		if (WARN_ON_ONCE(end < start))
+			return -ENOSPC;
 		max = end - 1;
 	}
 
@@ -1138,7 +1142,6 @@ void ida_simple_remove(struct ida *ida, unsigned int id)
 {
 	unsigned long flags;
 
-	BUG_ON((int)id < 0);
 	spin_lock_irqsave(&simple_ida_lock, flags);
 	ida_remove(ida, id);
 	spin_unlock_irqrestore(&simple_ida_lock, flags);
-- 
1.7.4.4

Re: [PATCH 5/9 V2] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Tejun Heo]

On Sat, Apr 19, 2014 at 07:38:12PM +0800, Lai Jiangshan wrote:
> @@ -559,7 +559,7 @@ void idr_remove(struct idr *idp, int id)
>  	struct idr_layer *p;
>  	struct idr_layer *to_free;
>  
> -	if (id < 0)
> +	if (WARN_ON_ONCE(id < 0))
>  		return;

ISTR callers which call in with error value, but yeah weeding them out
could be a good idea.  Shouldn't it be idr_remove_warning() though?

> @@ -1030,6 +1030,9 @@ void ida_remove(struct ida *ida, int id)
>  	int n;
>  	struct ida_bitmap *bitmap;
>  
> +	if (WARN_ON_ONCE(id < 0))
> +		return;

Why not jump to err?

> +
>  	if (idr_id > idr_max(ida->idr.layers))
>  		goto err;
>  
> @@ -1096,13 +1099,14 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
>  	unsigned int max;
>  	unsigned long flags;
>  
> -	BUG_ON((int)start < 0);
> -	BUG_ON((int)end < 0);
> +	if (WARN_ON_ONCE(((int)start < 0) || ((int)end < 0)))
> +		return -EINVAL;
>  
>  	if (end == 0)
>  		max = 0x80000000;
>  	else {
> -		BUG_ON(end < start);
> +		if (WARN_ON_ONCE(end < start))
> +			return -ENOSPC;

-EINVAL

Thanks.

-- 
tejun

Re: [PATCH 5/9 V2] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Lai Jiangshan]

On Sat, Apr 19, 2014 at 9:07 PM, Tejun Heo <tj@kernel.org> wrote:
> On Sat, Apr 19, 2014 at 07:38:12PM +0800, Lai Jiangshan wrote:
>> @@ -559,7 +559,7 @@ void idr_remove(struct idr *idp, int id)
>>       struct idr_layer *p;
>>       struct idr_layer *to_free;
>>
>> -     if (id < 0)
>> +     if (WARN_ON_ONCE(id < 0))
>>               return;
>
> ISTR callers which call in with error value, but yeah weeding them out
> could be a good idea.  Shouldn't it be idr_remove_warning() though?

WARN_ON_ONCE() for invalid id (negative id).
idr_remove_warning() for unallocated id.

>
>> @@ -1030,6 +1030,9 @@ void ida_remove(struct ida *ida, int id)
>>       int n;
>>       struct ida_bitmap *bitmap;
>>
>> +     if (WARN_ON_ONCE(id < 0))
>> +             return;
>
> Why not jump to err?

WARN_ON_ONCE() for invalid id (negative id).
"goto err" for unallocated id.

>
>> +
>>       if (idr_id > idr_max(ida->idr.layers))
>>               goto err;
>>
>> @@ -1096,13 +1099,14 @@ int ida_simple_get(struct ida *ida, unsigned int start, unsigned int end,
>>       unsigned int max;
>>       unsigned long flags;
>>
>> -     BUG_ON((int)start < 0);
>> -     BUG_ON((int)end < 0);
>> +     if (WARN_ON_ONCE(((int)start < 0) || ((int)end < 0)))
>> +             return -EINVAL;
>>
>>       if (end == 0)
>>               max = 0x80000000;
>>       else {
>> -             BUG_ON(end < start);
>> +             if (WARN_ON_ONCE(end < start))
>> +                     return -ENOSPC;
>
> -EINVAL

In my V1 patch, it returns -EINVAL.

The V2 changelog explain this change: make the returned value as the
same as idr_alloc().
###
It is important for cyclic allocation (idr_alloc()).

int idr_alloc_cyclic(struct idr *idr, void *ptr, int start, int end,
gfp_t gfp_mask)
{
int id;

id = idr_alloc(idr, ptr, max(start, idr->cur), end, gfp_mask);
if (id == -ENOSPC)
id = idr_alloc(idr, ptr, start, end, gfp_mask);

if (likely(id >= 0))
idr->cur = id + 1;
return id;
}

idr->cur can equals to @end. idr_alloc() should return  -ENOSPC for
next idr_alloc().

>
> Thanks.
>
> --
> tejun
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 5/9 V2] idr: covert BUG_ON() to WARN_ON_ONCE() if the argument is invalid.

[Tejun Heo]

Hello,

On Sat, Apr 19, 2014 at 10:04:06PM +0800, Lai Jiangshan wrote:
> On Sat, Apr 19, 2014 at 9:07 PM, Tejun Heo <tj@kernel.org> wrote:
> WARN_ON_ONCE() for invalid id (negative id).
> idr_remove_warning() for unallocated id.

I don't know.  Seem like an unnecessary distinction.

> >> @@ -1030,6 +1030,9 @@ void ida_remove(struct ida *ida, int id)
> >>       int n;
> >>       struct ida_bitmap *bitmap;
> >>
> >> +     if (WARN_ON_ONCE(id < 0))
> >> +             return;
> >
> > Why not jump to err?
> 
> WARN_ON_ONCE() for invalid id (negative id).
> "goto err" for unallocated id.

Ditto.

Thanks.

-- 
tejun

[PATCH 6/9 V2] idr: avoid ping-pong

[Lai Jiangshan]

The ida callers always calls ida_pre_get() before ida_get_new*().
ida_pre_get() will always do layer allocation, which means the layer removal
in ida_get_new*() is helpless. ida_get_new*() frees and the ida_pre_get() for
the next ida_get_new*() allocates.

It causes an unneeded ping-pong. The aim "Throw away extra resources one by one"
can't be achieved. This speculative layer removal in ida_get_new*() can't
result expected optimization.

So we remove the unneeded layer removal in ida_get_new*().

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 lib/idr.c |   11 -----------
 1 files changed, 0 insertions(+), 11 deletions(-)

diff --git a/lib/idr.c b/lib/idr.c
index 317fd35..25fe476 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -1001,17 +1001,6 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 
 	*p_id = id;
 
-	/* Each leaf node can handle nearly a thousand slots and the
-	 * whole idea of ida is to have small memory foot print.
-	 * Throw away extra resources one by one after each successful
-	 * allocation.
-	 */
-	if (ida->idr.id_free_cnt || ida->free_bitmap) {
-		struct idr_layer *p = get_from_free_list(&ida->idr);
-		if (p)
-			kmem_cache_free(idr_layer_cache, p);
-	}
-
 	return 0;
 }
 EXPORT_SYMBOL(ida_get_new_above);
-- 
1.7.4.4

[PATCH 7/9 V2] 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 25fe476..4a11c5d 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 8/9 V2] 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 4a11c5d..e3c1da0 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 9/9 V2] idr: remove useless C-PreProcessor branch

[Lai Jiangshan]

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

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

diff --git a/lib/idr.c b/lib/idr.c
index e3c1da0..d77cdca 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

Re: [PATCH 9/9 V2] idr: remove useless C-PreProcessor branch

[Tejun Heo]

$SUBJ: idr: remove useless #ifndef TEST

On Sat, Apr 19, 2014 at 07:38:16PM +0800, Lai Jiangshan wrote:
> "#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>

Thanks.

-- 
tejun

Re: [PATCH 9/9 V2] idr: remove useless C-PreProcessor branch

[Lai Jiangshan]

On Sun, Apr 20, 2014 at 7:51 AM, Tejun Heo <tj@kernel.org> wrote:
> $SUBJ: idr: remove useless #ifndef TEST
>
> On Sat, Apr 19, 2014 at 07:38:16PM +0800, Lai Jiangshan wrote:
>> "#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>

Hi, Tejun

Will you accept the acked patches into your tj/misc.git tree?
(Or somebody else accepts the idr patches?).

5/9 will be sent later (in other patchset)
6/8 will be dropped.

Thanks,
Lai

>
> Thanks.
>
> --
> tejun
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at  http://www.tux.org/lkml/

Re: [PATCH 9/9 V2] idr: remove useless C-PreProcessor branch

[Tejun Heo]

Hello,

On Sun, Apr 20, 2014 at 11:56:02AM +0800, Lai Jiangshan wrote:
> On Sun, Apr 20, 2014 at 7:51 AM, Tejun Heo <tj@kernel.org> wrote:
> > $SUBJ: idr: remove useless #ifndef TEST
> >
> > On Sat, Apr 19, 2014 at 07:38:16PM +0800, Lai Jiangshan wrote:
> >> "#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>
> 
> Hi, Tejun
> 
> Will you accept the acked patches into your tj/misc.git tree?
> (Or somebody else accepts the idr patches?).

I can route them through misc or Andrew can take them through -mm,
which probably would be better.

> 5/9 will be sent later (in other patchset)
> 6/8 will be dropped.

Andrew, can you please take the acked patches?

Thanks.

-- 
tejun