Skip to contentSkip to conversation

ida: fix up bitmap size calculation

PATCH In review Namhyung Kim 2 participants 7 messages Sep 2, 2010 – Sep 3, 2010 Xarray

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 ida: fix up bitmap size calculation

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.

---
 include/linux/idr.h |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)
include/linux/idr.h +2 -2
index e968db7..13c7296 100644
@@ -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;
Signature · 1 line
1.7.2.2
#1 lore raw

Hello,

Quoted 14 lines · 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.

---
 include/linux/idr.h |    4 ++--
 1 files changed, 2 insertions(+), 2 deletions(-)
include/linux/idr.h +0 -0
index e968db7..13c7296 100644

include/linux/idr.h void idr_init(struct idr *idp); · line 123

Quoted 7 lines
include/linux/idr.h +2 -2
@@ -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.

Signature · 1 line
tejun
#2 lore raw

Hi,

Quoted 8 lines · Tejun Heo

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

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

Quoted 7 lines

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.

Signature · 2 lines
Regards,
Namhyung Kim
#3 lore raw
Quoted 2 lines · Namhyung Kim

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

How about this?

Quoted 1 line

From 38866b19cdbf03d133c54a1f3b7d48279bdd4177 Mon Sep 17 00:00:00 2001

From: Namhyung Kim <[email protected]>
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.

---
 include/linux/idr.h |    9 ++++++++-
 1 files changed, 8 insertions(+), 1 deletions(-)
include/linux/idr.h +8 -1
index e968db7..7807e4b 100644
@@ -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];
Signature · 1 line
1.7.2.2
#4 lore raw
Quoted 5 lines · Namhyung Kim
Quoted 2 lines · Namhyung Kim

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 [email protected]?

Thanks.

include/linux/idr.h +4 -1
index e968db7..1208528 100644
@@ -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 {
Signature · 1 line
tejun
#5 lore raw
Quoted 3 lines · Tejun Heo

I'd prefer something with a bit more brevity.  If this looks good, can you please send it to [email protected]?

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

Signature · 2 lines
Regards,
Namhyung Kim
#6 lore raw
Quoted 7 lines · Namhyung Kim
Quoted 3 lines · Tejun Heo

I'd prefer something with a bit more brevity. If this looks good, can you please send it to [email protected]?

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

Yeap, sure thing.

Thanks.

Signature · 1 line
tejun