[PATCH] Silly bitmap size accounting fix

[PATCH] Silly bitmap size accounting fix

[Steven Rostedt]

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 <rostedt@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;

Re: [PATCH] Silly bitmap size accounting fix

[Ingo Molnar]

* Steven Rostedt <rostedt@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 <mingo@elte.hu>

	Ingo

Re: [PATCH] Silly bitmap size accounting fix

[Nick Piggin]

Ingo Molnar wrote:
> * Steven Rostedt <rostedt@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 <mingo@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 

Re: [PATCH] Silly bitmap size accounting fix

[Steven Rostedt]

On Sat, 13 May 2006, Nick Piggin wrote:

> Ingo Molnar wrote:
> > * Steven Rostedt <rostedt@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 <mingo@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 <rostedt@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;

Re: [PATCH] Silly bitmap size accounting fix

[Nick Piggin]

Steven Rostedt wrote:
> On Sat, 13 May 2006, Nick Piggin wrote:
> 
> 
>>Ingo Molnar wrote:
>>
>>>* Steven Rostedt <rostedt@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 <mingo@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 <rostedt@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 

Re: [PATCH] Silly bitmap size accounting fix

[Steven Rostedt]

> > +/*
> > + * 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 <rostedt@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;

Re: [PATCH] Silly bitmap size accounting fix

[Nick Piggin]

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 <rostedt@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 

Re: [PATCH] Silly bitmap size accounting fix

[Takashi Iwai]

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

Re: [PATCH] Silly bitmap size accounting fix

[Nick Piggin]

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 

Re: [PATCH] Silly bitmap size accounting fix

[Steven Rostedt]

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 <rostedt@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];
 };

Re: [PATCH] Silly bitmap size accounting fix

[Ingo Molnar]

* Steven Rostedt <rostedt@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 <mingo@elte.hu>

	Ingo