[PATCH 0/4] idr: idr cleanups

[PATCH 0/4] idr: idr cleanups

[Lai Jiangshan]

patch1 is the new version of previous pathset.(it is dropped by previous
	patchset, this one is new)

patch2/3 save a lot memory

Lai Jiangshan (4):
  idr: proper invalid argument handling
  idr: reduce the number of MAX_IDR_FREE
  ida: in-place ida allocation
  idr: reorder the fields

 include/linux/idr.h |   28 ++++--------
 lib/idr.c           |  119 ++++++++++++++++++---------------------------------
 2 files changed, 51 insertions(+), 96 deletions(-)

-- 
1.7.4.4

[PATCH 1/4] idr: proper invalid argument handling

[Lai Jiangshan]

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

ida_remove()/idr_remove() add checks for "id < 0".
BUG_ON() in ida_simple_remove() is simply removed, due to
ida_remove() already checks for "id < 0".

In idr_alloc(), it still returns -ENOSPC when "start == end",
but it returns -EINVAL when "max < start" while old code returns
-ENOSPC. -EINVAL is proper here, the caller must passed wrong
arguments.

ida_simple_get()'s argument-checks are changed as the same as
idr_alloc().

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

diff --git a/lib/idr.c b/lib/idr.c
index 96bb252..87c98fc 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -457,8 +457,10 @@ int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
 	/* sanity checks */
 	if (WARN_ON_ONCE(start < 0))
 		return -EINVAL;
-	if (unlikely(max < start))
+	if (unlikely(end > 0 && start == end))
 		return -ENOSPC;
+	if (WARN_ON_ONCE(max < start))
+		return -EINVAL;
 
 	/* allocate id */
 	id = idr_get_empty_slot(idr, start, pa, gfp_mask, NULL);
@@ -551,10 +553,7 @@ void idr_remove(struct idr *idp, int id)
 	struct idr_layer *p;
 	struct idr_layer *to_free;
 
-	if (id < 0)
-		return;
-
-	if (id > idr_max(idp->layers)) {
+	if (id < 0 || id > idr_max(idp->layers)) {
 		idr_remove_warning(id);
 		return;
 	}
@@ -1012,7 +1011,7 @@ void ida_remove(struct ida *ida, int id)
 	int n;
 	struct ida_bitmap *bitmap;
 
-	if (idr_id > idr_max(ida->idr.layers))
+	if (id < 0 || idr_id > idr_max(ida->idr.layers))
 		goto err;
 
 	/* clear full bits while looking up the leaf idr_layer */
@@ -1078,14 +1077,17 @@ 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))
+		return -EINVAL;
 
-	if (end == 0)
-		max = 0x80000000;
+	if ((int)end <= 0)
+		max = INT_MAX;
 	else {
-		BUG_ON(end < start);
 		max = end - 1;
+		if (unlikely(start == end))
+			return -ENOSPC;
+		if (WARN_ON_ONCE(max < start))
+			return -EINVAL;
 	}
 
 again:
@@ -1120,7 +1122,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

[PATCH 2/4] idr: reduce the number of MAX_IDR_FREE

[Lai Jiangshan]

Whe need to prepare MAX_IDR_FREE idr_layers for allocation.

But when idr is not empty, we need atmost (MAX_IDR_LEVEL - 1) idr_layers
to build up and atmost (MAX_IDR_LEVEL - 1) idr_layers to allocate down.
When idr is empty need atmost MAX_IDR_LEVEL layers.

So max((MAX_IDR_LEVEL * 2 - 2), MAX_IDR_LEVEL) idr_layers is enough.

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

diff --git a/lib/idr.c b/lib/idr.c
index 87c98fc..871991b 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -36,8 +36,13 @@
 /* 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)
+/*
+ * Number of idr_layer structs to leave in free list.
+ * When idr is not empty, we need atmost (MAX_IDR_LEVEL - 1) idr_layers
+ * to build up and atmost (MAX_IDR_LEVEL - 1) idr_layers to allocate down.
+ * When idr is empty need atmost MAX_IDR_LEVEL layers.
+ */
+#define MAX_IDR_FREE max((MAX_IDR_LEVEL * 2 - 2), MAX_IDR_LEVEL)
 
 static struct kmem_cache *idr_layer_cache;
 static DEFINE_PER_CPU(struct idr_layer *, idr_preload_head);
-- 
1.7.4.4

[PATCH 3/4] ida: in-place ida allocation

[Lai Jiangshan]

There are two stages of ida allocation/free, idr_layers and ida_bitmap.
They add unneeded foot print and memory waste.

When a single ID is first allocated from an ida, this ida requires
two big chunks of memory. One idr_layer and one ida_bitmap.

To reduce the foot print and memory, we reduce the ida_bitmap
to a single "unsigned long" and place it in its own idr-slot
and avoid to allocate the ida_bitmap.

It also means ida bitmap is located on its coresponding idr-slot
which size is the same as "unsigned long".
Each ida bitmap(idr-slot) contains BITS_PER_LONG ida-slots.

The struct ida_bitmap is not needed any more, we use "unsigned long"
directly and remove all the code of alloc/free struct ida_bitmap.

Signed-off-by: Lai Jiangshan <laijs@cn.fujitsu.com>
---
 include/linux/idr.h |   15 +--------
 lib/idr.c           |   85 +++++++++++++-------------------------------------
 2 files changed, 23 insertions(+), 77 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 6af3400..3a77b33 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -135,25 +135,12 @@ static inline void *idr_find(struct idr *idr, int id)
 /*
  * IDA - IDR based id allocator, use when translation from id to
  * pointer isn't necessary.
- *
- * IDA_BITMAP_LONGS is calculated to be one less to accommodate
- * ida_bitmap->nr_busy so that the whole struct fits in 128 bytes.
  */
-#define IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
-#define IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long) - 1)
-#define IDA_BITMAP_BITS 	(IDA_BITMAP_LONGS * sizeof(long) * 8)
-
-struct ida_bitmap {
-	long			nr_busy;
-	unsigned long		bitmap[IDA_BITMAP_LONGS];
-};
-
 struct ida {
 	struct idr		idr;
-	struct ida_bitmap	*free_bitmap;
 };
 
-#define IDA_INIT(name)		{ .idr = IDR_INIT((name).idr), .free_bitmap = NULL, }
+#define IDA_INIT(name)		{ .idr = IDR_INIT((name).idr), }
 #define DEFINE_IDA(name)	struct ida name = IDA_INIT(name)
 
 int ida_pre_get(struct ida *ida, gfp_t gfp_mask);
diff --git a/lib/idr.c b/lib/idr.c
index 871991b..69f8d78 100644
--- a/lib/idr.c
+++ b/lib/idr.c
@@ -859,27 +859,15 @@ EXPORT_SYMBOL(idr_is_empty);
  *
  * 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.
+ * occupies a bit.  ida uses the leaf idr-slot which contains
+ * IDA_BITMAP_BITS(BITS_PER_LONG) ida-slots.
  *
  * 2007-04-25  written by Tejun Heo <htejun@gmail.com>
  */
 
-static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
-{
-	unsigned long flags;
-
-	if (!ida->free_bitmap) {
-		spin_lock_irqsave(&ida->idr.lock, flags);
-		if (!ida->free_bitmap) {
-			ida->free_bitmap = bitmap;
-			bitmap = NULL;
-		}
-		spin_unlock_irqrestore(&ida->idr.lock, flags);
-	}
-
-	kfree(bitmap);
-}
+#define IDA_BITMAP_BITS 	BITS_PER_LONG
+#define IDA_BITMAP_EMPTY	0UL
+#define IDA_BITMAP_FULL		(~0UL)
 
 /**
  * ida_pre_get - reserve resources for ida allocation
@@ -896,21 +884,7 @@ static void free_bitmap(struct ida *ida, struct ida_bitmap *bitmap)
 int ida_pre_get(struct ida *ida, gfp_t gfp_mask)
 {
 	/* allocate idr_layers */
-	if (!__idr_pre_get(&ida->idr, gfp_mask))
-		return 0;
-
-	/* allocate free_bitmap */
-	if (!ida->free_bitmap) {
-		struct ida_bitmap *bitmap;
-
-		bitmap = kmalloc(sizeof(struct ida_bitmap), gfp_mask);
-		if (!bitmap)
-			return 0;
-
-		free_bitmap(ida, bitmap);
-	}
-
-	return 1;
+	return __idr_pre_get(&ida->idr, gfp_mask);
 }
 EXPORT_SYMBOL(ida_pre_get);
 
@@ -932,8 +906,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_IDR_LEVEL + 1];
-	struct ida_bitmap *bitmap;
-	unsigned long flags;
+	unsigned long *bitmap;
 	int idr_id = starting_id / IDA_BITMAP_BITS;
 	int offset = starting_id % IDA_BITMAP_BITS;
 	int t, id;
@@ -951,25 +924,11 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 		offset = 0;
 	idr_id = t;
 
-	/* if bitmap isn't there, create a new one */
-	bitmap = (void *)pa[0]->ary[idr_id & IDR_MASK];
-	if (!bitmap) {
-		spin_lock_irqsave(&ida->idr.lock, flags);
-		bitmap = ida->free_bitmap;
-		ida->free_bitmap = NULL;
-		spin_unlock_irqrestore(&ida->idr.lock, flags);
-
-		if (!bitmap)
-			return -EAGAIN;
-
-		memset(bitmap, 0, sizeof(struct ida_bitmap));
-		rcu_assign_pointer(pa[0]->ary[idr_id & IDR_MASK],
-				(void *)bitmap);
-		pa[0]->count++;
-	}
+	/* the lelf idr-slot is the bitmap for ida slots */
+	bitmap = (void *)&pa[0]->ary[idr_id & IDR_MASK];
 
 	/* lookup for empty slot */
-	t = find_next_zero_bit(bitmap->bitmap, IDA_BITMAP_BITS, offset);
+	t = find_next_zero_bit(bitmap, IDA_BITMAP_BITS, offset);
 	if (t == IDA_BITMAP_BITS) {
 		/* no empty slot after offset, continue to the next chunk */
 		idr_id++;
@@ -981,18 +940,21 @@ int ida_get_new_above(struct ida *ida, int starting_id, int *p_id)
 	if (id >= MAX_IDR_BIT)
 		return -ENOSPC;
 
-	__set_bit(t, bitmap->bitmap);
-	if (++bitmap->nr_busy == IDA_BITMAP_BITS)
+	if (*bitmap == IDA_BITMAP_EMPTY)
+		pa[0]->count++;
+
+	__set_bit(t, bitmap);
+	if (*bitmap == IDA_BITMAP_FULL)
 		idr_mark_full(pa, idr_id);
 
 	*p_id = id;
 
-	/* Each leaf node can handle nearly a thousand slots and the
+	/* Each leaf idr_layer 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) {
+	if (ida->idr.id_free_cnt) {
 		struct idr_layer *p = get_from_free_list(&ida->idr);
 		if (p)
 			kmem_cache_free(idr_layer_cache, p);
@@ -1014,7 +976,7 @@ void ida_remove(struct ida *ida, int id)
 	int idr_id = id / IDA_BITMAP_BITS;
 	int offset = id % IDA_BITMAP_BITS;
 	int n;
-	struct ida_bitmap *bitmap;
+	unsigned long *bitmap;
 
 	if (id < 0 || idr_id > idr_max(ida->idr.layers))
 		goto err;
@@ -1033,16 +995,15 @@ void ida_remove(struct ida *ida, int id)
 	n = idr_id & IDR_MASK;
 	__clear_bit(n, p->bitmap);
 
-	bitmap = (void *)p->ary[n];
-	if (!bitmap || !test_bit(offset, bitmap->bitmap))
+	bitmap = (void *)&p->ary[n];
+	if (!test_bit(offset, bitmap))
 		goto err;
 
 	/* update bitmap and remove it if empty */
-	__clear_bit(offset, bitmap->bitmap);
-	if (--bitmap->nr_busy == 0) {
+	__clear_bit(offset, bitmap);
+	if (*bitmap == IDA_BITMAP_EMPTY) {
 		__set_bit(n, p->bitmap);	/* to please idr_remove() */
 		idr_remove(&ida->idr, idr_id);
-		free_bitmap(ida, bitmap);
 	}
 
 	return;
@@ -1059,7 +1020,6 @@ EXPORT_SYMBOL(ida_remove);
 void ida_destroy(struct ida *ida)
 {
 	idr_destroy(&ida->idr);
-	kfree(ida->free_bitmap);
 }
 EXPORT_SYMBOL(ida_destroy);
 
@@ -1142,7 +1102,6 @@ EXPORT_SYMBOL(ida_simple_remove);
  */
 void ida_init(struct ida *ida)
 {
-	memset(ida, 0, sizeof(struct ida));
 	idr_init(&ida->idr);
 
 }
-- 
1.7.4.4

[PATCH 4/4] idr: reorder the fields

[Lai Jiangshan]

idr_layer->layer is always accessed in read path,
move it in the front.

idr_layer->bitmap is moved on the bottom. And
rcu_head shares with bitmap due to they do not
be accessed at the same time.

idr->id_free/id_free_cnt/lock are free list fields,
and moved to the bottom. They will be removed
in near future.

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

diff --git a/include/linux/idr.h b/include/linux/idr.h
index 3a77b33..c537c55 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -29,21 +29,24 @@
 
 struct idr_layer {
 	int			prefix;	/* the ID prefix of this idr_layer */
-	DECLARE_BITMAP(bitmap, IDR_SIZE); /* A zero bit means "space here" */
+	int			layer;	/* distance from leaf */
 	struct idr_layer __rcu	*ary[1<<IDR_BITS];
 	int			count;	/* When zero, we can release it */
-	int			layer;	/* distance from leaf */
-	struct rcu_head		rcu_head;
+	union {
+		/* A zero bit means "space here" */
+		DECLARE_BITMAP(bitmap, IDR_SIZE);
+		struct rcu_head		rcu_head;
+	};
 };
 
 struct idr {
 	struct idr_layer __rcu	*hint;	/* the last layer allocated from */
 	struct idr_layer __rcu	*top;
-	struct idr_layer	*id_free;
 	int			layers;	/* only valid w/o concurrent changes */
-	int			id_free_cnt;
 	int			cur;	/* current pos for cyclic allocation */
 	spinlock_t		lock;
+	int			id_free_cnt;
+	struct idr_layer	*id_free;
 };
 
 #define IDR_INIT(name)							\
-- 
1.7.4.4

Re: [PATCH 1/4] idr: proper invalid argument handling

[Andrew Morton]

On Tue, 22 Apr 2014 18:16:18 +0800 Lai Jiangshan <laijs@cn.fujitsu.com> wrote:

> When the arguments passed by the caller are invalid, WARN_ON_ONCE()
> is proper than BUG_ON() which may crash the kernel.
> 
> ida_remove()/idr_remove() add checks for "id < 0".
> BUG_ON() in ida_simple_remove() is simply removed, due to
> ida_remove() already checks for "id < 0".
> 
> In idr_alloc(), it still returns -ENOSPC when "start == end",
> but it returns -EINVAL when "max < start" while old code returns
> -ENOSPC. -EINVAL is proper here, the caller must passed wrong
> arguments.
> 
> ida_simple_get()'s argument-checks are changed as the same as
> idr_alloc().

This patch doesn't apply.

> @@ -551,10 +553,7 @@ void idr_remove(struct idr *idp, int id)
>  	struct idr_layer *p;
>  	struct idr_layer *to_free;
>  
> -	if (id < 0)
> -		return;
> -
> -	if (id > idr_max(idp->layers)) {
> +	if (id < 0 || id > idr_max(idp->layers)) {
>  		idr_remove_warning(id);
>  		return;
>  	}

3.15-rc2's idr_remove() has a call to sub_remove() in there, but
whatever-kernel-you're-using does not.

Re: [PATCH 1/4] idr: proper invalid argument handling

[Andrew Morton]

On Tue, 22 Apr 2014 12:16:56 -0700 Andrew Morton <akpm@linux-foundation.org> wrote:

> On Tue, 22 Apr 2014 18:16:18 +0800 Lai Jiangshan <laijs@cn.fujitsu.com> wrote:
> 
> > When the arguments passed by the caller are invalid, WARN_ON_ONCE()
> > is proper than BUG_ON() which may crash the kernel.
> > 
> > ida_remove()/idr_remove() add checks for "id < 0".
> > BUG_ON() in ida_simple_remove() is simply removed, due to
> > ida_remove() already checks for "id < 0".
> > 
> > In idr_alloc(), it still returns -ENOSPC when "start == end",
> > but it returns -EINVAL when "max < start" while old code returns
> > -ENOSPC. -EINVAL is proper here, the caller must passed wrong
> > arguments.
> > 
> > ida_simple_get()'s argument-checks are changed as the same as
> > idr_alloc().
> 
> This patch doesn't apply.
> 
> > @@ -551,10 +553,7 @@ void idr_remove(struct idr *idp, int id)
> >  	struct idr_layer *p;
> >  	struct idr_layer *to_free;
> >  
> > -	if (id < 0)
> > -		return;
> > -
> > -	if (id > idr_max(idp->layers)) {
> > +	if (id < 0 || id > idr_max(idp->layers)) {
> >  		idr_remove_warning(id);
> >  		return;
> >  	}
> 
> 3.15-rc2's idr_remove() has a call to sub_remove() in there, but
> whatever-kernel-you're-using does not.

Ah, it's based on your other idr patchset.  That's what I get for
working in reverse time order.

Re: [PATCH 1/4] idr: proper invalid argument handling

[Tejun Heo]

Hello,

On Tue, Apr 22, 2014 at 06:16:18PM +0800, Lai Jiangshan wrote:
> @@ -457,8 +457,10 @@ int idr_alloc(struct idr *idr, void *ptr, int start, int end, gfp_t gfp_mask)
>  	/* sanity checks */
>  	if (WARN_ON_ONCE(start < 0))
>  		return -EINVAL;
> -	if (unlikely(max < start))
> +	if (unlikely(end > 0 && start == end))
>  		return -ENOSPC;
> +	if (WARN_ON_ONCE(max < start))
> +		return -EINVAL;

Why is this change necessary?  Now the code is inconsistent with the
comment?  This change looks very gratuituous.

> @@ -1078,14 +1077,17 @@ 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))
> +		return -EINVAL;
>  
> -	if (end == 0)
> -		max = 0x80000000;
> +	if ((int)end <= 0)
> +		max = INT_MAX;

Again, why are you changing this?  What problem are you trying to fix?

>  	else {
> -		BUG_ON(end < start);
>  		max = end - 1;
> +		if (unlikely(start == end))
> +			return -ENOSPC;
> +		if (WARN_ON_ONCE(max < start))
> +			return -EINVAL;

Please juts convert BUG_ON()s to WARNs.  If you want to change how the
paramters behave.  Do those in a separate patch with proper
rationales.

Thanks.

-- 
tejun

Re: [PATCH 2/4] idr: reduce the number of MAX_IDR_FREE

[Tejun Heo]

On Tue, Apr 22, 2014 at 06:16:19PM +0800, Lai Jiangshan wrote:
> +/*
> + * Number of idr_layer structs to leave in free list.
> + * When idr is not empty, we need atmost (MAX_IDR_LEVEL - 1) idr_layers
> + * to build up and atmost (MAX_IDR_LEVEL - 1) idr_layers to allocate down.
> + * When idr is empty need atmost MAX_IDR_LEVEL layers.
> + */
> +#define MAX_IDR_FREE max((MAX_IDR_LEVEL * 2 - 2), MAX_IDR_LEVEL)

I don't know.  Do we really wanna be this sophiscated about it when
the cost of mistake would be an unexpected id allocation failure which
would *EXTREMELY* difficult to track down or reproduce?  Let's please
keep it dumb and safe.  With preloading we aren't even caching it
per-idr.  I don't think this is something we want to do.

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

Thanks.

-- 
tejun

Re: [PATCH 3/4] ida: in-place ida allocation

[Tejun Heo]

On Tue, Apr 22, 2014 at 06:16:20PM +0800, Lai Jiangshan wrote:
> There are two stages of ida allocation/free, idr_layers and ida_bitmap.
> They add unneeded foot print and memory waste.
> 
> When a single ID is first allocated from an ida, this ida requires
> two big chunks of memory. One idr_layer and one ida_bitmap.
> 
> To reduce the foot print and memory, we reduce the ida_bitmap
> to a single "unsigned long" and place it in its own idr-slot
> and avoid to allocate the ida_bitmap.
> 
> It also means ida bitmap is located on its coresponding idr-slot
> which size is the same as "unsigned long".
> Each ida bitmap(idr-slot) contains BITS_PER_LONG ida-slots.
> 
> The struct ida_bitmap is not needed any more, we use "unsigned long"
> directly and remove all the code of alloc/free struct ida_bitmap.

Are you calling 128 byte a "big chunk of memory" while trading off
tree depth for it?  No, this level of space optimizaiton is completely
uncalled for.

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

Thanks.

-- 
tejun

Re: [PATCH 3/4] ida: in-place ida allocation

[Lai Jiangshan]

On 04/23/2014 04:02 AM, Tejun Heo wrote:
> On Tue, Apr 22, 2014 at 06:16:20PM +0800, Lai Jiangshan wrote:
>> There are two stages of ida allocation/free, idr_layers and ida_bitmap.
>> They add unneeded foot print and memory waste.
>>
>> When a single ID is first allocated from an ida, this ida requires
>> two big chunks of memory. One idr_layer and one ida_bitmap.
>>
>> To reduce the foot print and memory, we reduce the ida_bitmap
>> to a single "unsigned long" and place it in its own idr-slot
>> and avoid to allocate the ida_bitmap.
>>
>> It also means ida bitmap is located on its coresponding idr-slot
>> which size is the same as "unsigned long".
>> Each ida bitmap(idr-slot) contains BITS_PER_LONG ida-slots.
>>
>> The struct ida_bitmap is not needed any more, we use "unsigned long"
>> directly and remove all the code of alloc/free struct ida_bitmap.
> 
> Are you calling 128 byte a "big chunk of memory" while trading off
> tree depth for it?  No, this level of space optimizaiton is completely
> uncalled for.

I reduce the depth, you forgot that struct ida_bitmap is an additional
depth which is removed in the patch.

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

Re: [PATCH 2/4] idr: reduce the number of MAX_IDR_FREE

[Lai Jiangshan]

On 04/23/2014 03:58 AM, Tejun Heo wrote:
> On Tue, Apr 22, 2014 at 06:16:19PM +0800, Lai Jiangshan wrote:
>> +/*
>> + * Number of idr_layer structs to leave in free list.
>> + * When idr is not empty, we need atmost (MAX_IDR_LEVEL - 1) idr_layers
>> + * to build up and atmost (MAX_IDR_LEVEL - 1) idr_layers to allocate down.
>> + * When idr is empty need atmost MAX_IDR_LEVEL layers.
>> + */
>> +#define MAX_IDR_FREE max((MAX_IDR_LEVEL * 2 - 2), MAX_IDR_LEVEL)
> 
> I don't know.  Do we really wanna be this sophiscated about it when
> the cost of mistake would be an unexpected id allocation failure which
> would *EXTREMELY* difficult to track down or reproduce?  Let's please
> keep it dumb and safe.

Do you mean "I need additional free layers to
hide any possible bugs"? let me nervous.

> With preloading we aren't even caching it
> per-idr.  I don't think this is something we want to do.

Understood.

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