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/
> -#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
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
> 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;
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
> > +/*
> > + * 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;
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
What's wrong with BITS_TO_LONG(MAX_PRIO + 1) ?
Or, using DECLARE_BITMAP() in struct prio_array would be easier...
Takashi
Yes that sounds even better.
--
SUSE Labs, Novell Inc.
Send instant messages to your online friends http://au.messenger.yahoo.com
>
> 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];
};
> -#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