[PATCH] ida: fix up bitmap size calculation

[PATCH] ida: fix up bitmap size calculation

[Namhyung Kim]

ida chunk should consist of 128 bytes (= 1024 bits) by definition
but because of wrong calculation of IDA_BITMAP_LONGS it only contained
992 on 32-bit machines, 960 on 64-bit machines. Fix it.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 include/linux/idr.h |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index e968db7..13c7296 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -119,8 +119,8 @@ void idr_init(struct idr *idp);
  * pointer isn't necessary.
  */
 #define IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
-#define IDA_BITMAP_LONGS	(128 / sizeof(long) - 1)
-#define IDA_BITMAP_BITS		(IDA_BITMAP_LONGS * sizeof(long) * 8)
+#define IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long))
+#define IDA_BITMAP_BITS 	(IDA_CHUNK_SIZE * 8)
 
 struct ida_bitmap {
 	long			nr_busy;
-- 
1.7.2.2

Re: [PATCH] ida: fix up bitmap size calculation

[Tejun Heo]

Hello,

On 09/02/2010 07:00 PM, Namhyung Kim wrote:
> ida chunk should consist of 128 bytes (= 1024 bits) by definition
> but because of wrong calculation of IDA_BITMAP_LONGS it only contained
> 992 on 32-bit machines, 960 on 64-bit machines. Fix it.
> 
> Signed-off-by: Namhyung Kim <namhyung@gmail.com>
> ---
>  include/linux/idr.h |    4 ++--
>  1 files changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/include/linux/idr.h b/include/linux/idr.h
> index e968db7..13c7296 100644
> --- a/include/linux/idr.h
> +++ b/include/linux/idr.h
> @@ -119,8 +119,8 @@ void idr_init(struct idr *idp);
>   * pointer isn't necessary.
>   */
>  #define IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
> -#define IDA_BITMAP_LONGS	(128 / sizeof(long) - 1)
> -#define IDA_BITMAP_BITS		(IDA_BITMAP_LONGS * sizeof(long) * 8)
> +#define IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long))
> +#define IDA_BITMAP_BITS 	(IDA_CHUNK_SIZE * 8)

The -1 when calculating IDA_BITMAP_LONGS is intentional.  Please see
below.

struct ida_bitmap {
	long			nr_busy;
	unsigned long		bitmap[IDA_BITMAP_LONGS];
};

With the -1, sizeof(struct ida_bitmap) becomes 128 bytes but if you
remove the -1, it becomes 132 bytes.  Because ida_bitmap doesn't use
dedicated slab (doesn't make sense as it's not a very hot data
structure), with 132 bytes, it's gonna be allocated from 256 byte slot
wasting ~50% of memory.  Adding a comment there to clarify why -1 is
there would be nice tho.

Thanks.

-- 
tejun

Re: [PATCH] ida: fix up bitmap size calculation

[Namhyung Kim]

Hi,

On Fri, Sep 3, 2010 at 02:20, Tejun Heo <tj@kernel.org> wrote:
> The -1 when calculating IDA_BITMAP_LONGS is intentional.  Please see
> below.
>
> struct ida_bitmap {
>        long                    nr_busy;
>        unsigned long           bitmap[IDA_BITMAP_LONGS];
> };
>
> With the -1, sizeof(struct ida_bitmap) becomes 128 bytes but if you
> remove the -1, it becomes 132 bytes.  Because ida_bitmap doesn't use
> dedicated slab (doesn't make sense as it's not a very hot data
> structure), with 132 bytes, it's gonna be allocated from 256 byte slot
> wasting ~50% of memory.  Adding a comment there to clarify why -1 is
> there would be nice tho.
>

Got it. :-) I'll prepare new patch with that comment, then.
Thank you for the explanation.

-- 
Regards,
Namhyung Kim

Re: [PATCH] ida: fix up bitmap size calculation

[Namhyung Kim]

Namhyung Kim <namhyung@gmail.com> writes:
> Got it. :-) I'll prepare new patch with that comment, then.
> Thank you for the explanation.

How about this?

>From 38866b19cdbf03d133c54a1f3b7d48279bdd4177 Mon Sep 17 00:00:00 2001
From: Namhyung Kim <namhyung@gmail.com>
Date: Fri, 3 Sep 2010 02:44:47 +0900
Subject: [PATCH] ida: document IDA_BITMAP_LONGS calculation

IDA_BITMAP_LONGS value is calculated take into account struct ida_bitmap
not to waste memory space. Comment it.

Signed-off-by: Namhyung Kim <namhyung@gmail.com>
---
 include/linux/idr.h |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)

diff --git a/include/linux/idr.h b/include/linux/idr.h
index e968db7..7807e4b 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -119,9 +119,16 @@ void idr_init(struct idr *idp);
  * pointer isn't necessary.
  */
 #define IDA_CHUNK_SIZE		128	/* 128 bytes per chunk */
+/*
+ * -1 is needed here to fit total chunk size into 128 bytes because
+ * struct ida_bitmap consists of nr_busy and bitmap. Since it is
+ * allocated by kmalloc(), chunk size should be matched with kmalloc
+ * size so that it will not waste memory.
+ */
 #define IDA_BITMAP_LONGS	(128 / sizeof(long) - 1)
-#define IDA_BITMAP_BITS		(IDA_BITMAP_LONGS * sizeof(long) * 8)
+#define IDA_BITMAP_BITS 	(IDA_BITMAP_LONGS * sizeof(long) * 8)
 
+/* IDA bitmap chunk */
 struct ida_bitmap {
 	long			nr_busy;
 	unsigned long		bitmap[IDA_BITMAP_LONGS];
-- 
1.7.2.2

Re: [PATCH] ida: fix up bitmap size calculation

[Tejun Heo]

On 09/02/2010 08:07 PM, Namhyung Kim wrote:
> Namhyung Kim <namhyung@gmail.com> writes:
>> Got it. :-) I'll prepare new patch with that comment, then.
>> Thank you for the explanation.
> 
> How about this?

I'd prefer something with a bit more brevity.  If this looks good, can
you please send it to trivial@kernel.org?

Thanks.

diff --git a/include/linux/idr.h b/include/linux/idr.h
index e968db7..1208528 100644
--- a/include/linux/idr.h
+++ b/include/linux/idr.h
@@ -117,9 +117,12 @@ void idr_init(struct idr *idp);
 /*
  * 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 accomodate
+ * 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	(128 / sizeof(long) - 1)
+#define IDA_BITMAP_LONGS	(IDA_CHUNK_SIZE / sizeof(long) - 1)
 #define IDA_BITMAP_BITS		(IDA_BITMAP_LONGS * sizeof(long) * 8)

 struct ida_bitmap {


-- 
tejun

Re: [PATCH] ida: fix up bitmap size calculation

[Namhyung Kim]

On Fri, Sep 3, 2010 at 18:14, Tejun Heo <tj@kernel.org> wrote:
> I'd prefer something with a bit more brevity.  If this looks good, can
> you please send it to trivial@kernel.org?
>

OK. So can I add 'Acked-by' line for you?

-- 
Regards,
Namhyung Kim

Re: [PATCH] ida: fix up bitmap size calculation

[Tejun Heo]

On 09/03/2010 11:26 AM, Namhyung Kim wrote:
> On Fri, Sep 3, 2010 at 18:14, Tejun Heo <tj@kernel.org> wrote:
>> I'd prefer something with a bit more brevity.  If this looks good, can
>> you please send it to trivial@kernel.org?
>>
> 
> OK. So can I add 'Acked-by' line for you?
> 

Yeap, sure thing.

Thanks.

-- 
tejun