broken bitmap_parse for ncpus > 32

PATCH In review Joe Korty 3 participants 9 messages Mar 22, 2004 – Mar 23, 2004

Subsystems (2)

Library code Bitmap API

lore

Share & tools

lore

Joe Korty

author

2004-03-22 20:22 UTC #0 lore raw

PATCH 1/1 broken bitmap_parse for ncpus > 32

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

lib/bitmap.c +11 -1

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

Paul Jackson

2004-03-22 21:45 UTC #1 lore raw

Quoted 1 line

I also prepended comments to the bitmap_shift_* functions defining what

Nice work.

Signature · 3 lines

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

William Lee Irwin III

2004-03-22 23:13 UTC #2 lore raw

In reply to Joe Korty

Quoted 4 lines · 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

Quoted 8 lines

(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

Joe Korty

author

2004-03-23 00:16 UTC #3 lore raw

Quoted 3 lines

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

William Lee Irwin III

2004-03-23 02:09 UTC #4 lore raw

Quoted 3 lines · At some point in the past, I wrote:

Quoted 3 lines
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.

Quoted 4 lines · Joe Korty

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

Joe Korty

author

2004-03-23 04:11 UTC #5 lore raw

Quoted 6 lines · William Lee Irwin III

Quoted 3 lines · At some point in the past, I wrote:
Quoted 3 lines
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:

Quoted 8 lines

Quoted 4 lines
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:

lib/bitmap.c +23 -1

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

William Lee Irwin III

2004-03-23 04:18 UTC #6 lore raw

Quoted 3 lines · William Lee Irwin III

Quoted 3 lines
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.

Quoted 1 line · Joe Korty

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

Paul Jackson

2004-03-23 00:20 UTC #7 lore raw

In reply to William Lee Irwin III

Quoted 3 lines

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.

Signature · 3 lines

                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373

William Lee Irwin III

2004-03-23 02:08 UTC #8 lore raw

Quoted 5 lines · Paul Jackson

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