[PATCH] broken bitmap_parse for ncpus > 32

[PATCH] broken bitmap_parse for ncpus > 32

[Joe Korty]

Andrew,
 This patch replaces the call to bitmap_shift_right() in bitmap_parse()
with bitmap_shift_left().

This mental confusion between right and left did not show up in my
(userland) testing, as I foolishly wrote my own bitmap_shift routines
rather than drag over the kernel versions.  And it did not show up in my
kernel testing because no shift routine is called when NR_CPUS <= 32.

I tested this in userland with the kernel's versions of bitmap_shift_*
and compiled a kernel and spot checked it on a 2-cpu system.

I also prepended comments to the bitmap_shift_* functions defining what
'left' and 'right' means. This is under the theory that if I and all the
reviewers were bamboozled, others in the future occasionally might be too.

Regards,
Joe

--- base/lib/bitmap.c	2004-03-10 21:55:43.000000000 -0500
+++ new/lib/bitmap.c	2004-03-22 14:41:03.000000000 -0500
@@ -71,6 +71,11 @@
 }
 EXPORT_SYMBOL(bitmap_complement);
 
+/*
+ * Shifting right (dividing) means moving bits in the MS -> LS bit
+ * direction.  Zeros are fed into the vacated MS positions and the
+ * LS bits shifted off the bottom are lost.
+ */
 void bitmap_shift_right(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
@@ -86,6 +91,11 @@
 }
 EXPORT_SYMBOL(bitmap_shift_right);
 
+/*
+ * Shifting left (multiplying) means moving bits in the LS -> MS
+ * direction.  Zeros are fed into the vacated LS bit positions
+ * and those MS bits shifted off the top are lost.
+ */
 void bitmap_shift_left(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
@@ -269,7 +279,7 @@
 		if (nchunks == 0 && chunk == 0)
 			continue;
 
-		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+		bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
 		*maskp |= chunk;
 		nchunks++;
 		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;

Re: [PATCH] broken bitmap_parse for ncpus > 32

[Paul Jackson]

> I also prepended comments to the bitmap_shift_* functions defining what

Nice work.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [PATCH] broken bitmap_parse for ncpus > 32

[William Lee Irwin III]

On Mon, Mar 22, 2004 at 03:21:18PM -0500, Joe Korty wrote:
> Andrew,
>  This patch replaces the call to bitmap_shift_right() in bitmap_parse()
> with bitmap_shift_left().
> This mental confusion between right and left did not show up in my
> (userland) testing, as I foolishly wrote my own bitmap_shift routines
> rather than drag over the kernel versions.  And it did not show up in my
> kernel testing because no shift routine is called when NR_CPUS <= 32.
> I tested this in userland with the kernel's versions of bitmap_shift_*
> and compiled a kernel and spot checked it on a 2-cpu system.
> I also prepended comments to the bitmap_shift_* functions defining what
> 'left' and 'right' means. This is under the theory that if I and all the
> reviewers were bamboozled, others in the future occasionally might be too.

Bugfixes are always good. Maybe the kerneldoc stuff would be a good idea
for these functions, and the rest of the non-static functions ppl might
be expected to call.


-- wli

Re: [PATCH] broken bitmap_parse for ncpus > 32

[Joe Korty]

> Bugfixes are always good. Maybe the kerneldoc stuff would be a good idea
> for these functions, and the rest of the non-static functions ppl might
> be expected to call.

IMO, one+ liners describing how a function is used is best put near
the function, where it is most likely to be seen.  Stuff going into
Documentation/*.txt should be bulky stuff not suitable for inlining,
such as largish tutorials, annotated examples, theory papers, etc. 

Joe

Re: [PATCH] broken bitmap_parse for ncpus > 32

[Paul Jackson]

> Maybe the kerneldoc stuff would be a good idea
> for these functions, and the rest of the non-static functions ppl might
> be expected to call.

Not quite sure what Bill is converying here with the qualifier 'non-static'.

My inclinations lay more toward looking for improvements, explored in
other messages on a concurrent thread "[PATCH] Introduce nodemask_t
ADT", to the cpumask API, to be followed by a kerneldoc, rather than
trying very hard to document the current API much more.

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [PATCH] broken bitmap_parse for ncpus > 32

[William Lee Irwin III]

On Mon, Mar 22, 2004 at 04:19:31PM -0800, Paul Jackson wrote:
> Not quite sure what Bill is converying here with the qualifier 'non-static'.
> My inclinations lay more toward looking for improvements, explored in
> other messages on a concurrent thread "[PATCH] Introduce nodemask_t
> ADT", to the cpumask API, to be followed by a kerneldoc, rather than
> trying very hard to document the current API much more.

non-static == exported for people to use, declared in a header, and
without the "static" qualifier to the function. Basically, things added
to the kernel API. As this is the low-level bitmap stuff, I believe it
should be relatively unchanged across whatever API changes you may have
in store for higher-level API's e.g. cpumasks. This is the bitmap
library code we're talking about, isn't it? At least it's what I'm
talking about.


-- wli

Re: [PATCH] broken bitmap_parse for ncpus > 32

[William Lee Irwin III]

At some point in the past, I wrote:
>> Bugfixes are always good. Maybe the kerneldoc stuff would be a good idea
>> for these functions, and the rest of the non-static functions ppl might
>> be expected to call.

On Mon, Mar 22, 2004 at 07:14:33PM -0500, Joe Korty wrote:
> IMO, one+ liners describing how a function is used is best put near
> the function, where it is most likely to be seen.  Stuff going into
> Documentation/*.txt should be bulky stuff not suitable for inlining,
> such as largish tutorials, annotated examples, theory papers, etc. 

Sorry about not being clear; I meant the : and @ stuff I've seen around
various comments that somehow gets yanked directly out of C comments in
the source and generated into a pdf.


-- wli

Re: [PATCH] broken bitmap_parse for ncpus > 32

[Joe Korty]

On Mon, Mar 22, 2004 at 06:09:07PM -0800, William Lee Irwin III wrote:
> At some point in the past, I wrote:
>>> Bugfixes are always good. Maybe the kerneldoc stuff would be a good idea
>>> for these functions, and the rest of the non-static functions ppl might
>>> be expected to call.
> 
> On Mon, Mar 22, 2004 at 07:14:33PM -0500, Joe Korty wrote:
>> IMO, one+ liners describing how a function is used is best put near
>> the function, where it is most likely to be seen.  Stuff going into
>> Documentation/*.txt should be bulky stuff not suitable for inlining,
>> such as largish tutorials, annotated examples, theory papers, etc. 
> 
> Sorry about not being clear; I meant the : and @ stuff I've seen around
> various comments that somehow gets yanked directly out of C comments in
> the source and generated into a pdf.


Ah, I see.  Here is the New-n-Improved patch:

--- base/lib/bitmap.c	2004-03-10 21:55:43.000000000 -0500
+++ new/lib/bitmap.c	2004-03-22 23:04:51.000000000 -0500
@@ -71,6 +71,17 @@
 }
 EXPORT_SYMBOL(bitmap_complement);
 
+/*
+ * bitmap_shift_write - logical right shift of the bits in a bitmap
+ *   @dst - destination bitmap
+ *   @src - source bitmap
+ *   @nbits - shift by this many bits
+ *   @bits - bitmap size, in bits
+ *
+ * Shifting right (dividing) means moving bits in the MS -> LS bit
+ * direction.  Zeros are fed into the vacated MS positions and the
+ * LS bits shifted off the bottom are lost.
+ */
 void bitmap_shift_right(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
@@ -86,6 +97,17 @@
 }
 EXPORT_SYMBOL(bitmap_shift_right);
 
+/*
+ * bitmap_shift_left - logical left shift of the bits in a bitmap
+ *   @dst - destination bitmap
+ *   @src - source bitmap
+ *   @nbits - shift by this many bits
+ *   @bits - bitmap size, in bits
+ *
+ * Shifting left (multiplying) means moving bits in the LS -> MS
+ * direction.  Zeros are fed into the vacated LS bit positions
+ * and those MS bits shifted off the top are lost.
+ */
 void bitmap_shift_left(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
@@ -269,7 +291,7 @@
 		if (nchunks == 0 && chunk == 0)
 			continue;
 
-		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+		bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits);
 		*maskp |= chunk;
 		nchunks++;
 		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;

Re: [PATCH] broken bitmap_parse for ncpus > 32

[William Lee Irwin III]

On Mon, Mar 22, 2004 at 06:09:07PM -0800, William Lee Irwin III wrote:
>> Sorry about not being clear; I meant the : and @ stuff I've seen around
>> various comments that somehow gets yanked directly out of C comments in
>> the source and generated into a pdf.

On Mon, Mar 22, 2004 at 11:10:13PM -0500, Joe Korty wrote:
> Ah, I see.  Here is the New-n-Improved patch:

Cool! I wouldn't have said it was a requirement, but I certainly like
the updated patch.


-- wli