Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.
Dismiss

[PATCH] Silly bitmap size accounting fix

0 views
Skip to first unread message

Steven Rostedt

unread,
May 12, 2006, 4:40:08 AM5/12/06
to

Ingo,

While explaining to a colleague why you defined BITMAP_SIZE in sched.c to:

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

and not

#define BITMAP_SIZE ((((MAX_PRIO)/8)+sizeof(long))/sizeof(long))

It dawned on me that the MAX_PRIO+1 should really be just MAX_PRIO.

Priorities go from 0 to MAX_PRIO-1 so you only need to store MAX_PRIO
bits. As you probably know since you define the array in the run queue to
only queue[MAX_PRIO] and not [MAX_PRIO+1].

So on a normal system where long is 4 bytes we get:

MAX_PRIO = 140
sizeof(long) = 4
((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long)) = 5

And with the new fix:

((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long)) = 5

So the result is the same, and hence the "Silly" part in the subject.

But although this change really has no affect on the kernel, it is still
a correctness issue, and readability issue. The +1+7 confuses people,
especially when the +1 is not needed.

Not to mention, for those that change the kernel to use their own priority
settings, it might waste one extra word (althought this is actually not
that big of a deal).

So for correctness and readability, I'm submitting this patch.

-- Steve

Signed-off-by: Steven Rostedt <ros...@goodmis.org>

Index: linux-2.6.17-rc3-mm1/kernel/sched.c
===================================================================
--- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400
+++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-12 04:02:39.000000000 -0400
@@ -192,7 +192,7 @@ static inline unsigned int task_timeslic
* These are the runqueue data structures:
*/

-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
+#define BITMAP_SIZE ((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long))

typedef struct runqueue runqueue_t;

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

Ingo Molnar

unread,
May 12, 2006, 5:20:11 AM5/12/06
to

* Steven Rostedt <ros...@goodmis.org> wrote:

> -#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
> +#define BITMAP_SIZE ((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long))

Acked-by: Ingo Molnar <mi...@elte.hu>

Ingo

Nick Piggin

unread,
May 12, 2006, 9:40:10 PM5/12/06
to
Ingo Molnar wrote:
> * Steven Rostedt <ros...@goodmis.org> wrote:
>
>
>>-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>>+#define BITMAP_SIZE ((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long))
>
>
> Acked-by: Ingo Molnar <mi...@elte.hu>

Really?! What about the delimiter bit set at MAX_PRIO?

--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com

Steven Rostedt

unread,
May 13, 2006, 10:20:09 AM5/13/06
to

On Sat, 13 May 2006, Nick Piggin wrote:

> Ingo Molnar wrote:
> > * Steven Rostedt <ros...@goodmis.org> wrote:
> >
> >
> >>-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
> >>+#define BITMAP_SIZE ((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long))
> >
> >
> > Acked-by: Ingo Molnar <mi...@elte.hu>
>
> Really?! What about the delimiter bit set at MAX_PRIO?


// delimiter for bitsearch
__set_bit(MAX_PRIO, array->bitmap);


Ah! I see what you mean. New patch (add a comment).

-- Steve

Signed-off-by: Steven Rostedt <ros...@goodmis.org>

Index: linux-2.6.17-rc3-mm1/kernel/sched.c
===================================================================
--- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400

+++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:09:15.000000000 -0400
@@ -192,6 +192,10 @@ static inline unsigned int task_timeslic


* These are the runqueue data structures:
*/

+/*
+ * Calculate BITMAP_SIZE.
+ * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
+ */
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

typedef struct runqueue runqueue_t;

Nick Piggin

unread,
May 13, 2006, 10:40:08 AM5/13/06
to
Steven Rostedt wrote:
> On Sat, 13 May 2006, Nick Piggin wrote:
>
>
>>Ingo Molnar wrote:
>>
>>>* Steven Rostedt <ros...@goodmis.org> wrote:
>>>
>>>
>>>
>>>>-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>>>>+#define BITMAP_SIZE ((((MAX_PRIO+7)/8)+sizeof(long)-1)/sizeof(long))
>>>
>>>
>>>Acked-by: Ingo Molnar <mi...@elte.hu>
>>
>>Really?! What about the delimiter bit set at MAX_PRIO?
>
>
>
> // delimiter for bitsearch
> __set_bit(MAX_PRIO, array->bitmap);
>
>
> Ah! I see what you mean. New patch (add a comment).

That would have caused someone a world of pain 3 years ahead ;)

>
> -- Steve
>
> Signed-off-by: Steven Rostedt <ros...@goodmis.org>

OK I guess. Does it help to also spell out exactly what's going on there?

>
> Index: linux-2.6.17-rc3-mm1/kernel/sched.c
> ===================================================================
> --- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400
> +++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:09:15.000000000 -0400
> @@ -192,6 +192,10 @@ static inline unsigned int task_timeslic
> * These are the runqueue data structures:
> */
>
> +/*
> + * Calculate BITMAP_SIZE.
> + * The bitmask holds MAX_PRIO bits + 1 for the delimiter.

+ * Calculation is to find the minimum number of longs that holds MAX_PRIO+1 bits:
+ * size-in-chars = ceiling((MAX_PRIO+1) / CHAR_BITS)
+ * size-in-longs = ceiling(size-in-chars / sizeof(long))

> + */
> #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>

--

SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com

Steven Rostedt

unread,
May 13, 2006, 11:00:07 AM5/13/06
to

> > +/*
> > + * Calculate BITMAP_SIZE.
> > + * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
>
> + * Calculation is to find the minimum number of longs that holds MAX_PRIO+1 bits:
> + * size-in-chars = ceiling((MAX_PRIO+1) / CHAR_BITS)
> + * size-in-longs = ceiling(size-in-chars / sizeof(long))
>
> > + */
> > #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
> >
>

What do you think of the following comment, better?

-- Steve

Signed-off-by: Steven Rostedt <ros...@goodmis.org>

Index: linux-2.6.17-rc3-mm1/kernel/sched.c


===================================================================
--- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400

+++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:50:44.000000000 -0400
@@ -192,6 +192,13 @@ static inline unsigned int task_timeslic


* These are the runqueue data structures:
*/

+/*
+ * Calculate BITMAP_SIZE.
+ * The bitmask holds MAX_PRIO bits + 1 for the delimiter.

+ * BITMAP_SIZE is the minimum number of longs that holds MAX_PRIO+1 bits:
+ * size-in-bytes = ceiling((MAX_PRIO+1) / BITS_PER_BYTE)
+ * size-in-longs = ceiling(size-in-bytes / sizeof(long))


+ */
#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

typedef struct runqueue runqueue_t;

Nick Piggin

unread,
May 13, 2006, 11:00:08 AM5/13/06
to
Steven Rostedt wrote:
>
>>>+/*
>>>+ * Calculate BITMAP_SIZE.
>>>+ * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
>>
>>+ * Calculation is to find the minimum number of longs that holds MAX_PRIO+1 bits:
>>+ * size-in-chars = ceiling((MAX_PRIO+1) / CHAR_BITS)
>>+ * size-in-longs = ceiling(size-in-chars / sizeof(long))
>>
>>
>>>+ */
>>> #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>>>
>>
>
> What do you think of the following comment, better?

Cool, thanks.

>
> -- Steve
>
> Signed-off-by: Steven Rostedt <ros...@goodmis.org>
>
> Index: linux-2.6.17-rc3-mm1/kernel/sched.c
> ===================================================================
> --- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400
> +++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:50:44.000000000 -0400
> @@ -192,6 +192,13 @@ static inline unsigned int task_timeslic
> * These are the runqueue data structures:
> */
>
> +/*
> + * Calculate BITMAP_SIZE.
> + * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
> + * BITMAP_SIZE is the minimum number of longs that holds MAX_PRIO+1 bits:
> + * size-in-bytes = ceiling((MAX_PRIO+1) / BITS_PER_BYTE)
> + * size-in-longs = ceiling(size-in-bytes / sizeof(long))
> + */
> #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>
> typedef struct runqueue runqueue_t;
>

--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com

Takashi Iwai

unread,
May 13, 2006, 11:40:14 AM5/13/06
to
At Sat, 13 May 2006 10:12:11 -0400 (EDT),

Steven Rostedt wrote:
>
>
> Index: linux-2.6.17-rc3-mm1/kernel/sched.c
> ===================================================================
> --- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400
> +++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:09:15.000000000 -0400
> @@ -192,6 +192,10 @@ static inline unsigned int task_timeslic
> * These are the runqueue data structures:
> */
>
> +/*
> + * Calculate BITMAP_SIZE.
> + * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
> + */
> #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

What's wrong with BITS_TO_LONG(MAX_PRIO + 1) ?

Or, using DECLARE_BITMAP() in struct prio_array would be easier...


Takashi

Nick Piggin

unread,
May 13, 2006, 11:50:08 AM5/13/06
to
Takashi Iwai wrote:
> At Sat, 13 May 2006 10:12:11 -0400 (EDT),
> Steven Rostedt wrote:
>
>>
>>Index: linux-2.6.17-rc3-mm1/kernel/sched.c
>>===================================================================
>>--- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400
>>+++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 10:09:15.000000000 -0400
>>@@ -192,6 +192,10 @@ static inline unsigned int task_timeslic
>> * These are the runqueue data structures:
>> */
>>
>>+/*
>>+ * Calculate BITMAP_SIZE.
>>+ * The bitmask holds MAX_PRIO bits + 1 for the delimiter.
>>+ */
>> #define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
>
>
> What's wrong with BITS_TO_LONG(MAX_PRIO + 1) ?
>
> Or, using DECLARE_BITMAP() in struct prio_array would be easier...

Yes that sounds even better.

--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com

Steven Rostedt

unread,
May 13, 2006, 12:00:12 PM5/13/06
to

On Sun, 14 May 2006, Nick Piggin wrote:

>
> Yes that sounds even better.
>

I absolutely agree (a bit of a blush as well!)

Andrew,

I guess this is much better than before. Never seen so much action on a
patch that was just a comment!

-- Steve

Signed-off-by: Steven Rostedt <ros...@goodmis.org>

Index: linux-2.6.17-rc3-mm1/kernel/sched.c


===================================================================
--- linux-2.6.17-rc3-mm1.orig/kernel/sched.c 2006-05-12 04:02:32.000000000 -0400

+++ linux-2.6.17-rc3-mm1/kernel/sched.c 2006-05-13 11:56:08.000000000 -0400
@@ -192,13 +192,11 @@ static inline unsigned int task_timeslic


* These are the runqueue data structures:
*/

-#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
-
typedef struct runqueue runqueue_t;

struct prio_array {
unsigned int nr_active;
- unsigned long bitmap[BITMAP_SIZE];
+ DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
struct list_head queue[MAX_PRIO];
};

Ingo Molnar

unread,
May 14, 2006, 4:20:10 AM5/14/06
to

* Steven Rostedt <ros...@goodmis.org> wrote:

> -#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))
> -
> typedef struct runqueue runqueue_t;
>
> struct prio_array {
> unsigned int nr_active;
> - unsigned long bitmap[BITMAP_SIZE];
> + DECLARE_BITMAP(bitmap, MAX_PRIO+1); /* include 1 bit for delimiter */
> struct list_head queue[MAX_PRIO];
> };

Acked-by: Ingo Molnar <mi...@elte.hu>

Ingo

0 new messages