seperator error in __mask_snprintf_len

seperator error in __mask_snprintf_len

[Joe Korty]

Against 2.6.1-rc1.

--- base/lib/mask.c	2004-01-07 11:40:07.000000000 -0500
+++ new/lib/mask.c	2004-01-07 11:51:26.000000000 -0500
@@ -96,7 +96,7 @@
 	while (i >= 1 && wordp[i] == 0)
 		i--;
 	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
+		len += snprintf(buf+len, buflen-len, "%x%s", wordp[i], sep);
 		sep = ",";
 		i--;
 	}

Re: seperator error in __mask_snprintf_len

[Andrew Morton]

Joe Korty <joe.korty@ccur.com> wrote:
>
> Against 2.6.1-rc1.
> 
> --- base/lib/mask.c	2004-01-07 11:40:07.000000000 -0500
> +++ new/lib/mask.c	2004-01-07 11:51:26.000000000 -0500
> @@ -96,7 +96,7 @@
>  	while (i >= 1 && wordp[i] == 0)
>  		i--;
>  	while (i >= 0) {
> -		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
> +		len += snprintf(buf+len, buflen-len, "%x%s", wordp[i], sep);
>  		sep = ",";
>  		i--;
>  	}

What does the patch do?

Just looking at this function, it seems to walking an array of longs using
a u32*.  Could someone please convince me that this is correct on both
little-endian and big-endian 64-bit hardware?  

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Joe proposed this change to the loop displaying masks:
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
+		len += snprintf(buf+len, buflen-len, "%x%s", wordp[i], sep);


I doubt that your patch is correct, Joe.

Consider for example the case that exactly three words are displayed.

Before your patch, the code would output one hex word, then (after
looping around once) the "," separator and the second word, then on the
final loop another separator and word, resulting in something such as:

    deadbeef,12345678,87654321

After your patch, it would output the first word, then the second word,
then a trailing separator, and then the third word and separator,
resulting in something such as:

    deadbeef12345678,87654321,

Oops.

In the abstract, the separator is _not_ a trailing punctutator to each
word, but is rather used to separate each word from the _preceding_ word
(if any).

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

On Wed, Jan 07, 2004 at 05:06:50PM -0800, Paul Jackson wrote:
> Joe proposed this change to the loop displaying masks:
> -		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
> +		len += snprintf(buf+len, buflen-len, "%x%s", wordp[i], sep);
> 
> 
> I doubt that your patch is correct, Joe.
> 
> Consider for example the case that exactly three words are displayed.
> 
> Before your patch, the code would output one hex word, then (after
> looping around once) the "," separator and the second word, then on the
> final loop another separator and word, resulting in something such as:
> 
>     deadbeef,12345678,87654321
> 
> After your patch, it would output the first word, then the second word,
> then a trailing separator, and then the third word and separator,
> resulting in something such as:
> 
>     deadbeef12345678,87654321,

Sorry about the bit of conceptual dylexia on my part.

Paul, there might be a problem with __mask_snprintf_len.  Won't a
value that should be displayed as:

     d,00abcdef      be displayed as
     d,abcdef

Joe

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Joe noted:
> Paul, there might be a problem with __mask_snprintf_len.  Won't a
> value that should be displayed as:
> 
>      d,00abcdef      be displayed as
>      d,abcdef

You are correct that it will be displayed without zero padding.

But I don't think that's a problem; rather working as designed.

An example that suggests the motivation for this design choice is given
in the examples in the mask.c comment:

 *   A mask with just bit 127 set displays as "80000000,0,0,0".

With zero padding, this example gets longer.  For masks of 500 or a 1000
bits encoding a single high set bit, it's worse, resulting in several
text lines of ",00000000" words.

If you have reason to claim that it would be better to zero fill
these words, go ahead and make your case.

There are hundreds of possible ways of formatting the ascii
representation of bit masks; I picked one that I liked.  If good reasons
or a concensus develop for some other format, that's fine.
Better to change now than later.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Andrew asked:
> Just looking at this function, it seems to walking an array of longs using
> a u32*.  Could someone please convince me that this is correct on both
> little-endian and big-endian 64-bit hardware?  

Good question, Andrew.  Thanks.  I suspect I did indeed break something
here.

The key thing to recall first is that these masks, and the bitops of
longer standing on which they rely, are very little endian.  On all
architectures, masks are essentially as if an array of bytes, even
though they have a size that is a multiple of sizeof(long).

To quote from include/asm-ppc64/bitops.h:

 * Bitops are odd when viewed on big-endian systems.  They were designed
 * on little endian so the size of the bitset doesn't matter (low order bytes
 * come first) as long as the bit in question is valid.

>From one u32 word to the next, both my input and output routines in
lib/mask.c (mask_snprintf and mask_parse) respect this order, so that
part is correct, I believe.  For a mask beginning at address A, bytes
A[0..3] form the first u32 word, A[4..7] the second, and so forth. 
Good.

Whether the mask size is a multiple of u32 or u64 doesn't matter.

 ==> However, _within_ each word, I suspect that I have the bytes arse
backwards on a big endian machine.  The underlying snprintf("%x") and
strtoul() routines that I call will presume that the byte order of the
referenced u32 binary word is native (big on big endian).  Not good.

Anyone with a big-endian SMP machine should be able to see this, by
displaying /proc/irq/prof_cpu_mask or /proc/irq/<pid>/smp_affinity, and
determining if they see the expected low order bit(s) set, or instead
the output is byte reversed.

Given the good chance that I'm still confused, I will now broadcast
under a more enticing Subject a request for someone with a big endian
SMP to verify whether I've broken this as I suspect.

If this request proceeds as expected, I will follow up with a patch to
lib/mask.c that will likely make use of the cpu_to_le32() and
le32_to_cpu() macros in byteorder.h to swap bytes in the u32 words being
displayed and parsed.

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

Re: seperator error in __mask_snprintf_len

[Paul Mackerras]

Paul Jackson writes:

> The key thing to recall first is that these masks, and the bitops of
> longer standing on which they rely, are very little endian.  On all
> architectures, masks are essentially as if an array of bytes, even
> though they have a size that is a multiple of sizeof(long).
> 
> To quote from include/asm-ppc64/bitops.h:
> 
>  * Bitops are odd when viewed on big-endian systems.  They were designed
>  * on little endian so the size of the bitset doesn't matter (low order bytes
>  * come first) as long as the bit in question is valid.

Hmmm, well, that comment is a bit misleading.  Bitmasks on ppc64 (and
other bigendian 64-bit architectures such as sparc64) are stored as an
array of unsigned longs, i.e. 64-bit values.  The layout is such that
bit N is set iff (p[N/64] && (1UL << (N%64))) != 0, where p is an
unsigned long *.  In other words, a bitmask with only bit 0 set looks
like this, as an array of bytes:

00 00 00 00 00 00 00 01 00...

>  ==> However, _within_ each word, I suspect that I have the bytes arse
> backwards on a big endian machine.  The underlying snprintf("%x") and
> strtoul() routines that I call will presume that the byte order of the
> referenced u32 binary word is native (big on big endian).  Not good.

Why do you have to reference them as u32?  Why can't you use unsigned
long instead?  That should Just Work.

> If this request proceeds as expected, I will follow up with a patch to
> lib/mask.c that will likely make use of the cpu_to_le32() and
> le32_to_cpu() macros in byteorder.h to swap bytes in the u32 words being
> displayed and parsed.

That would be the wrong approach IMHO.

Regards,
Paul.

Re: seperator error in __mask_snprintf_len

[Joe Korty]

> >  ==> However, _within_ each word, I suspect that I have the bytes arse
> > backwards on a big endian machine.  The underlying snprintf("%x") and
> > strtoul() routines that I call will presume that the byte order of the
> > referenced u32 binary word is native (big on big endian).  Not good.
> 
> Why do you have to reference them as u32?  Why can't you use unsigned
> long instead?  That should Just Work.

I believe he wants the commas to group the digits by at most eight
irrespective of architecture.  Which seems reasonable.

Joe

Re: seperator error in __mask_snprintf_len

[Paul Mackerras]

Joe Korty writes:

> I believe he wants the commas to group the digits by at most eight
> irrespective of architecture.  Which seems reasonable.

Ah, ok, that makes sense.  I guess we need a BITMAP_WORD macro which
looks like this on big-endian 64-bit systems:

#define BITMAP_WORD(p, n)	(((u32 *)(p))[(n) ^ 1])

and this on other systems:

#define BITMAP_WORD(p, n)	(((u32 *)(p))[(n)])

or something like that...

Paul.

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

One side note I should warn of - my breakage (if such it be) was not
consistent.

To quote my original patch to Andrew:

> Date: Fri, 28 Nov 2003 12:54:28 -0800
> Subject: [PATCH] new /proc/irq cpumask format; consolidate cpumask display and input code
> 
> ...
> 
> There are two exceptions to the consolidation - the alpha and
> sparc64 arch's manipulate bare unsigned longs, not cpumask_t's,
> on input (write syscall), and do stuff that was more funky than
> I could make sense of.  So the input side of these two arch's
> was left as-is.  I'd welcome someone with access to either of
> these systems to provide additional patches.

This suggests that while I may well have broken the output side (what
the kernel displays when you read cpumasks in /proc/irq/prof_cpu_mask or
/proc/irq/<pid>/smp_affinity), it is less likely that I broke the input
side (the affect of writing a mask to these files).

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Joe, responding to Paul M:
> > Why do you have to reference them as u32?  Why can't you use unsigned
> > long instead?  That should Just Work.
> 
> I believe he wants the commas to group the digits by at most eight
> irrespective of architecture.  Which seems reasonable.


Yes - that's why I use u32 - each comma separated word in the
ascii representation of a mask represents 32 bits, regardless
of the native word size of the current architecture.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Paul M wrote:
> Hmmm, well, that comment is a bit misleading.  Bitmasks on ppc64 (and
> other bigendian 64-bit architectures such as sparc64) are stored as an
> array of unsigned longs, i.e. 64-bit values.

Ok - thank you for educating me on this.

So the byte order for 64 bit big endian cpumasks is:

  7 6 5 4 3 2 1 0 15 14 13 12 11 10 9 8 23 22 ...

rather than the little endian byte order of:

  0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 ...

I suspect that you are right, that I need a macro to pick the 'other'
half of a long, as you suggested:

  #define BITMAP_WORD(p, n)	(((u32 *)(p))[(n) ^ 1])

This would be defined in the include/asm-sparc64/cpumask.h and
include/asm-ppc64/cpumask.h files, with a no-op default in the
include/asm-generic/cpumask.h file for other architectures that
don't need it.  It would be used in lib/mask.c when printing
and scanning cpumasks.

I'm technically on vacation this week - If it doesn't cause anyone
heartburn, I likely won't get this patch out until mid next week.
If that hurts, squawk, and I'll work harder ;).

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Paul M, replying to Paul J:
> > If this request proceeds as expected, I will follow up with a patch to
> > lib/mask.c that will likely make use of the cpu_to_le32() and
> > le32_to_cpu() macros in byteorder.h to swap bytes in the u32 words being
> > displayed and parsed.
> 
> That would be the wrong approach IMHO.

Ok - I agree that this would be wrong for 64 bit sparc and ppc, for
these architectures use native big endian byte order within cpumasks,
not little endian.

Indeed, I take it that this applies not just to cpumasks, but to any
mask-like operand that bitops such as ffs() are applied to.

I also need to examine the 32 bit big endian architectures, to see
whether their cpumasks, and other bitop operands, are big or little
endian.  If they are big endian (native order) then my mask printing and
scanning code should always presume native byte order, and only has to
special case the order of two u32 words within a u64 long on 64 bit big
endian architectures.  If they are little endian, then I'll also need to
make use of the cpu_to_le32() and le32_to_cpu() macros in byteorder.h to
swap bytes in the u32 words being displayed and parsed (but _not_ for
sparc64 or ppc).

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

Re: seperator error in __mask_snprintf_len

[Andreas Schwab]

Paul Jackson <pj@sgi.com> writes:

> This would be defined in the include/asm-sparc64/cpumask.h and
> include/asm-ppc64/cpumask.h files, with a no-op default in the
> include/asm-generic/cpumask.h file for other architectures that
> don't need it. 

S390x is big-endian, too.  IMHO it should rather be in
include/linux/byteorder, or derived from the macros in there.

Andreas.

-- 
Andreas Schwab, SuSE Labs, schwab@suse.de
SuSE Linux AG, Maxfeldstraße 5, 90409 Nürnberg, Germany
Key fingerprint = 58CA 54C7 6D53 942B 1756  01D3 44D5 214B 8276 4ED5
"And now for something completely different."

Re: seperator error in __mask_snprintf_len

[Christoph Hellwig]

On Fri, Jan 09, 2004 at 04:14:55PM +0100, Andreas Schwab wrote:
> Paul Jackson <pj@sgi.com> writes:
> 
> > This would be defined in the include/asm-sparc64/cpumask.h and
> > include/asm-ppc64/cpumask.h files, with a no-op default in the
> > include/asm-generic/cpumask.h file for other architectures that
> > don't need it. 
> 
> S390x is big-endian, too.  IMHO it should rather be in
> include/linux/byteorder, or derived from the macros in there.

Yes, we'll need it for mips, too.

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Andreas wrote:
> S390x is big-endian, too.  IMHO it should rather be in
> include/linux/byteorder, or derived from the macros in there.

ok.

I suspect I will end up agreeing with your byteorder.h suggestion - good.

Chistoph wrote:
> Yes, we'll need it for mips, too.

ok.

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

Paul & Andrew,
 This version of __mask_snprintf_len should work with all mixes of big
vs little endian and 32 vs 64 bit longs.  I tested it in user-land on
a 32 bit big and 32 bit little endian machine.  I tested the 64 bit
long issues by setting MASK_CHUNKSZ == 16 on both of my 32 bit processors.
This should be equivalent to MASK_CHUNKSZ == 32 test on a 64 bit
processor.

This patch preserves Paul's ideas of how a cpumask_t should be printed
out even though I do not agree with those ideas.  At a minimum I prefer
a constant-width display so that columns of cpumasks will be readable.

I expect __mask_parse_len will need similar fixes; I have not looked
as this patch is enough for a Sunday evening's worth of work.

Regards,
Joe

Against 2.6.1


diff -Nua 2.6/lib/mask.c.0 2.6/lib/mask.c
--- 2.6/lib/mask.c.0	2004-01-11 18:53:18.000000000 -0500
+++ 2.6/lib/mask.c	2004-01-11 18:52:43.000000000 -0500
@@ -85,21 +85,30 @@
  *   __mask_snprintf_len(buf, buflen, cpus_addr(mask), sizeof(mask))
  */
 
+#define MASK_CHUNKSZ	(32)		/* in bits.  legal values: 4, 8, 16, 32 */
+
 int __mask_snprintf_len(char *buf, unsigned int buflen,
 	const unsigned long *maskp, unsigned int maskbytes)
 {
-	u32 *wordp = (u32 *)maskp;
-	int i = maskbytes/sizeof(u32) - 1;
-	int len = 0;
+	int i, word, bit, len = 0; 
+	unsigned long val;
 	char *sep = "";
 
-	while (i >= 1 && wordp[i] == 0)
-		i--;
-	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
-		sep = ",";
-		i--;
+	if (buflen <= 0)
+		return 0;
+	buflen--;
+
+	i = (maskbytes * 8 - 1) & ~(MASK_CHUNKSZ - 1);
+	for (; i >= 0; i -= MASK_CHUNKSZ) {
+		word = i / (sizeof(unsigned long) * 8);
+		bit = i % (sizeof(unsigned long) * 8);
+		val = (maskp[word] >> bit) & ((1ULL << MASK_CHUNKSZ) - 1);
+		if (!i || val || *sep == ',') {
+			len += snprintf(buf+len, buflen-len, "%s%lx", sep, val);
+			sep = ",";
+		}
 	}
+	buf[len++] = 0;
 	return len;
 }
 

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

A couple of questions on your proposed patch for __mask_snprintf_len()
in lib/mask.c:

 1) Why make the MASK_CHUNKSZ a possible (compile time) variable?
    I can think of a couple good reasons why not to:
    a] So long as we have the current format, in which each word
       is _not_ zero filled, then the chunk size needs to be a
       well known constant, or else the output is ambiguous.
       For example, an output of "1,0" is ambiguous unless we know
       a priori that the "0" stands for exactly 32, say, bits.
    b] Even if we change to a zero filled format, better to just
       always use the same chunk size, as that is one less detail
       to confuse user level code.
    I don't see any reason offhand for needing code that works with
    more than one chunk size.
 2) Why the trailing "buf[len++] = 0"?  Won't the last snprintf do
    as much?
 3) This code has quite a bit more detail of bit shifts, masks and
    arithmetic than before.  Perhaps some is necessary to fix the
    word order bug I had, perhaps some is only needed to allow for
    the chunk size to vary.  I'll take a shot at seeing if I can
    find a less detail-rich expression of this that still gets the
    word order correct.

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

On Mon, Jan 12, 2004 at 01:41:12PM -0800, Paul Jackson wrote:
> A couple of questions on your proposed patch for __mask_snprintf_len()
> in lib/mask.c:
> 
>  1) Why make the MASK_CHUNKSZ a possible (compile time) variable?
>     I can think of a couple good reasons why not to:
>     a] So long as we have the current format, in which each word
>        is _not_ zero filled, then the chunk size needs to be a
>        well known constant, or else the output is ambiguous.
>        For example, an output of "1,0" is ambiguous unless we know
>        a priori that the "0" stands for exactly 32, say, bits.
>     b] Even if we change to a zero filled format, better to just
>        always use the same chunk size, as that is one less detail
>        to confuse user level code.
>     I don't see any reason offhand for needing code that works with
>     more than one chunk size.

MASK_CHUNKSZ is a named constant not a variable.  Once we pick a value
it can never change.  The specified legal values are for 1) varying to
test for algorithmic correctness, and 2) giving the list of values from
which we must pick the permanent value before too much more time goes by.


>  2) Why the trailing "buf[len++] = 0"?  Won't the last snprintf do
>     as much?

No.  snprintf will fill to the end of the buffer and not place the
trailing \0 if it has to.  (I read the vsnprintf code this morning
just to make sure of that).

>  3) This code has quite a bit more detail of bit shifts, masks and
>     arithmetic than before.  Perhaps some is necessary to fix the
>     word order bug I had, perhaps some is only needed to allow for
>     the chunk size to vary.  I'll take a shot at seeing if I can
>     find a less detail-rich expression of this that still gets the
>     word order correct.

I am pretty sure the code is within a hairsbreadth of being minimal.
It will be interesting to find out.

Regards
-- 
"Money can buy bandwidth, but latency is forever" -- John Mashey
Joe

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

> MASK_CHUNKSZ is a named constant not a variable.  Once we pick a value
> it can never change.  The specified legal values are for 1) varying to
> test for algorithmic correctness, and 2) giving the list of values from
> which we must pick the permanent value before too much more time goes by.

I can see where the testing for algorithmic correctness would be useful.

The final code should reflect the final choices.

> No.  snprintf will fill to the end of the buffer and not place the

Correct - snprintf will not nul terminate if it runs out of buffer.

But then again, I wouldn't expect a "mask_snprintf" (such as might wrap
this __mask_snprintf_len() code) to guarantee nul termination in the
full buffer case either.  Rather the caller has to watch for a returned
length that is too close to the length of the buffer, and handle it as
an error.  If you look at the cpumask_snprintf() calls, they do just
this.

snprintf-like calls should behave like snprintf calls, no fancier.

> I am pretty sure the code is within a hairsbreadth of being minimal.

We'll see.  I'm still poking at it.

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

> snprintf-like calls should behave like snprintf calls, no fancier.

You are correct.
-- 
"Money can buy bandwidth, but latency is forever" -- John Mashey
Joe

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Paul M suggested (in the 32-bit display loop of lib/mask.c):
> #define BITMAP_WORD(p, n)	(((u32 *)(p))[(n) ^ 1])

Then, later, Joe sugguested a patch rewriting the lib/mask.c display
loop using various C bit operations (& ! / % << >>).

Joe - question - is there any good reason not to use Paul M's
suggestion, eor'ing the index with 1 on 64 bit big endian hardware?
I have a patch about ready (as soon as I can get time on my big system
to test it) that uses the eor 1 idea.

The eor 1 code looks good to me, and takes a few bytes fewer machine
instructions.  Perhaps you know something I am missing.  The actual
patch should be up in about 5 hours, in case you'd rather not comment on
code unseen ;).

Joe suggested:
> This patch preserves Paul's ideas of how a cpumask_t should be printed
> out even though I do not agree with those ideas.  At a minimum I prefer
> a constant-width display so that columns of cpumasks will be readable.

On further review, I think you're right on this, Joe.  After I get the
above big endian fix out, I will attempt a patch that changes this
format, zero-filling each word to 8 hex chars, from:

=========== OLD ===========
 * Examples:
 *   A mask with just bit 0 set displays as "1".
 *   A mask with just bit 127 set displays as "80000000,0,0,0".
 *   A mask with just bit 64 set displays as "1,0,0".
 *   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
 *     as "1,1,10117".  The first "1" is for bit 64, the second
 *     for bit 32, the third for bit 16, and so forth, to the
 *     "7", which is for bits 2, 1 and 0.
 *   A mask with bits 32 through 39 set displays as "ff,0".
=========== OLD ===========

to:

=========== NEW ===========
 * Examples:
 *   A mask with just bit 0 set displays as "00000001".
 *   A mask with just bit 127 set displays as "80000000,00000000,00000000,00000000".
 *   A mask with just bit 64 set displays as "00000001,00000000,00000000".
 *   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
 *     as "00000001,00000001,00010117".  The first "1" is for bit 64, the second
 *     for bit 32, the third for bit 16, and so forth, to the
 *     "7", which is for bits 2, 1 and 0.
 *   A mask with bits 32 through 39 set displays as "000000ff,00000000".
=========== NEW ===========

How does that look to you?  Anyone else want to chime in?

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

On Wed, Jan 14, 2004 at 03:03:31PM -0800, Paul Jackson wrote:
> Joe - question - is there any good reason not to use Paul M's
> suggestion, eor'ing the index with 1 on 64 bit big endian hardware?
> I have a patch about ready (as soon as I can get time on my big system
> to test it) that uses the eor 1 idea.

In principle it should work fine.  The details will be in the code
of course.

I've been working on-and-off on fixing the equivalent endian problem
in __mask_parse_len.  How is that part going for you?  I haven't yet
decided if I want to post it.

-- 
"Money can buy bandwidth, but latency is forever" -- John Mashey
Joe

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

> I've been working on-and-off on fixing the equivalent endian problem
> in __mask_parse_len.  How is that part going for you?  I haven't yet
> decided if I want to post it.

I have coded both - it was a simple matter of replacing each:

  wordp[i]

with:

  wordp[M32X(i)]

where M32X (for "Mask 32-bit indeX") is defined:

#include <asm/byteorder.h>
#if BITS_PER_LONG == 64 && defined(__BIG_ENDIAN)
#define M32X(i) ((i)^1)
#elif BITS_PER_LONG == 32 || defined(__LITTLE_ENDIAN)
#define M32X(i) (i)
#endif

I spent more time writing the comments explaining it than I did writing
the code.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Ok - here is a patch that should fix lib/mask.c displaying and parsing
cpumasks for 64 bit big endian architectures.  It has only been tested
on 64 bit little endian architectures ;).  Technically, it is against
2.6.1-mm3, though it should work against any kernel with a lib/mask.c
file, since this is the first change to that file.

The comments in the patch explain the details.

Thanks to Paul Mackerras for the "eor-1" coding suggestion, and to Joe
Korty for keeping me honest.

Tomorrow I will attempt a patch to change the ascii format for masks to
zero-fill each word (8 ascii hex chars, representing 32 bits).


# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.1507  -> 1.1508 
#	          lib/mask.c	1.1     -> 1.2    
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/01/14	pj@sgi.com	1.1508
# Swizzle u32 wordp[] indexing to handle 64 bit big-endian arch.
# --------------------------------------------
#
diff -Nru a/lib/mask.c b/lib/mask.c
--- a/lib/mask.c	Wed Jan 14 20:29:14 2004
+++ b/lib/mask.c	Wed Jan 14 20:29:14 2004
@@ -33,15 +33,16 @@
  * about any such struct details, relying on inline macros in
  * files such as cpumask.h to pass in an unsigned long pointer
  * and a length (in bytes), describing the mask contents.
- * The 32bit words in the array are in little-endian order,
- * low order word first.  Beware that this is the reverse order
- * of the ascii representation.
+ *
+ * This layout of masks is determined by the macros in bitops.h,
+ * which pre-date masks.  The bitop operations were formalized
+ * before the mask data type to which they apply.
  *
  * Even though the size of the input mask is provided in bytes,
- * the following code may assume that the mask is a multiple of
- * 32 or 64 bit words long, and ignore any fractional portion
- * of a word at the end.  The main reason the size is passed in
- * bytes is because it is so easy to write 'sizeof(somemask_t)'
+ * the following code may assume that the mask size is a multiple
+ * of sizeof(long), and ignore any fractional portion of a word
+ * at the end.  The main reason the size is passed in bytes is
+ * because it is so easy to write 'sizeof(somemask_t)'.
  * in the macros.
  *
  * Masks are not a single,simple type, like classic 'C'
@@ -72,6 +73,36 @@
 #define BASE 16			/* masks are input in hex (base 16) */
 #define NUL ((char)'\0')	/* nul-terminator */
 
+/*
+ * The following M32X() macro and associated comment really
+ * belong in include/linux/mask.h, which declares the 'mask'
+ * data type to which bitops apply.  However mask.h doesn't
+ * exist yet in the main Linux development line ...
+ */
+
+/*
+ * Masks are arrays of unsigned long.  This is almost the same
+ * as an array of unsigned ints, except on 64 bit big endian
+ * architectures, in which the two 32-bit int halves of each long
+ * are reversed (big 32-bit halfword first, naturally).
+ *
+ * Use this M32X (for "Mask 32-bit indeX") macro to index the
+ * i-th word of a mask declared as an array of 32 bit words.
+ *
+ * Usage example accessing 32-bit words in mask[] in order,
+ * smallest first:
+ *    u32 mask[MASKLENGTH];
+ *    int i;
+ *    for (i = 0; i < MASKLENGTH; i++)
+ *        ... mask[M32X(i)] ...
+ */
+#include <asm/byteorder.h>
+#if BITS_PER_LONG == 64 && defined(__BIG_ENDIAN)
+#define M32X(i) ((i)^1)
+#elif BITS_PER_LONG == 32 || defined(__LITTLE_ENDIAN)
+#define M32X(i) (i)
+#endif
+
 /**
  * __mask_snprintf_len - represent multi-word bit mask as string.
  * @buf: The buffer to place the result into
@@ -93,10 +124,11 @@
 	int len = 0;
 	char *sep = "";
 
-	while (i >= 1 && wordp[i] == 0)
+	while (i >= 1 && wordp[M32X(i)] == 0)
 		i--;
 	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
+		len += snprintf(buf+len, buflen-len,
+			"%s%x", sep, wordp[M32X(i)]);
 		sep = ",";
 		i--;
 	}
@@ -165,13 +197,13 @@
 		t = simple_strtoull(p, 0, BASE);
 		if (t != (u32)t)
 			return -EOVERFLOW;
-		wordp[j++] = t;
+		wordp[M32X(j++)] = t;
 	}
 	--j;
 	while (i < j) {
-		u32 t = wordp[i];
-		wordp[i] = wordp[j];
-		wordp[j] = t;
+		u32 t = wordp[M32X(i)];
+		wordp[M32X(i)] = wordp[M32X(j)];
+		wordp[M32X(j)] = t;
 		i++, --j;
 	}
 	return 0;


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

Re: seperator error in __mask_snprintf_len

[Andrew Morton]

Paul Jackson <pj@sgi.com> wrote:
>
> Ok - here is a patch that should fix lib/mask.c displaying and parsing
>  cpumasks for 64 bit big endian architectures.

Gad.

> + * This layout of masks is determined by the macros in bitops.h,
> + * which pre-date masks.  The bitop operations were formalized
> + * before the mask data type to which they apply.

So why not simply iterate across it with test_bit()?

	val = 0;
	for (bit = maskbytes * 8; bit >= 0; bit--) {
		val <<= 1;
		if (__test_bit(maskp, bit))
			val |= 1;
		if ((bit & 15) == 15) {
			sprintf(buf, "%x", val);
			buf++;
			val = 0;
		}
	}

(plus bounds checking, null-termination, etc)?  It is hardly
performance-critical.

Re: seperator error in __mask_snprintf_len

[Joe Korty]

Paul and Andrew,
This patch captures what I am looking for in bitmap display and input.

The biggest feature is the folding of all functionality into the bitmap.h
family, with corresponding name and function call argument changes.

bitmap size is now expressed in #bits rather than #bytes.  The cpumask
parse and display functions now call the bitmap functions with NR_CPUS.
Thus on display exactly NR_CPUS bits are displayed, no more and no less,
and on input no value is accepted which is larger than what can be stored
in exactly NR_CPUS bits.


ChangeLog:
 o move into the bitmap.h family, rename and refactor interface to match
 o bitmap size resolution changed from byte to bit
 o no limits on string length when parsing
 o chunking (digits between commas) changed from 8 to 4 digits
 o display no longer affected by sizeof(unsigned long).
 o no alloca usage
 o works correctly independent of the size of an unsigned long.
 o works on big and little endian machine.

Downsides:
 o code is subtle and fragile.  Corner cases may be present.

Most of the subtlety is for handling bitmask size resolution down to
the bit and for detecting illegal syntax such as "3,,2" "," and "".

These routines have been tested in user-land on both a big and little
endian machine.  Testing focused mainly on standard and corner bitmap
sizes (1,2,3,4,5,7,8,15,16,17,31,32,33,36,37,48,64 and 96), for a wide
variety of legal syntax and illegal syntax (eg legal: "0", "00", "0,0",
"0,0,0,00000000000017,0", "dead,beaf", "a,beaf", "beaf,a").

Regards,
Joe



Regards,
Joe

diff -Nua 2.6/lib/Makefile.0 2.6/lib/Makefile
--- 2.6/lib/Makefile.0	2004-01-15 12:10:41.000000000 -0500
+++ 2.6/lib/Makefile	2004-01-15 11:37:01.000000000 -0500
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o
+	 kobject.o idr.o div64.o parser.o int_sqrt.o bitmap.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o
diff -Nua 2.6/lib/bitmap.c.0 2.6/lib/bitmap.c
--- 2.6/lib/bitmap.c.0	2004-01-15 12:10:41.000000000 -0500
+++ 2.6/lib/bitmap.c	2004-01-15 12:08:10.000000000 -0500
@@ -0,0 +1,130 @@
+/*
+ * lib/bitmask.c - bitmask manipulation routines too big to go into bitmask.h
+ *
+ * Copyright 2002, Concurrent Computer Corporation, and distributed under
+ * the GNU GPL license version 2.  For other license arrangements, contact
+ * Concurrent Computer Corporation.
+ */
+
+#include <linux/kernel.h>
+#include <linux/string.h>
+#include <linux/ctype.h>
+#include <linux/errno.h>
+#include <linux/bitmap.h>
+#include <asm/uaccess.h>
+
+#define CHUNKSZ		16
+
+#define ROUNDUP_POWER2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
+
+
+/**
+ * bitmap_snprintf - convert bitmap to an ASCII hex string.
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Exactly nmaskbits bits are displayed.  Hex digits are grouped into
+ * fours seperated by commas.
+ */
+
+int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, unsigned int nmaskbits)
+{
+	int i, word, bit, len = 0; 
+	unsigned long val;
+	const char *sep = "";
+	int chunksz;
+	u32 chunkmask;
+
+	chunksz = nmaskbits & (CHUNKSZ - 1);
+	if (chunksz == 0)
+		chunksz = CHUNKSZ;
+
+	i = ROUNDUP_POWER2(nmaskbits, CHUNKSZ) - CHUNKSZ;
+	for (; i >= 0; i -= CHUNKSZ) {
+		chunkmask = ((1ULL << chunksz) - 1);
+		word = i / BITS_PER_LONG;
+		bit = i % BITS_PER_LONG;
+		val = (maskp[word] >> bit) & chunkmask;
+		len += snprintf(buf+len, buflen-len, "%s%0*lx", sep,
+			(chunksz+3)/4, val);
+		chunksz = CHUNKSZ;
+		sep = ",";
+	}
+	return len;
+}
+/**
+* bitmap_parse - convert an ASCII hex string into a bitmap.
+* @buf: pointer to buffer in user space containing string.
+* @buflen: buffer size in bytes.  If string is smaller than this
+*    then it must be terminated by a \0.
+* @maskp: pointer to bitmap that will contain result.
+* @nmaskbits: size of bitmap, in bits.
+*
+* Commas group hex digits into chunks. Each chunk defines exactly 16
+* bits of the resultant bitmask.  No chunk may specify a value larger
+* than 16 bits (-EOVERFLOW), and if a chunk specifies a smaller value
+* leading 0-bits are appended.
+*/
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, unsigned int nmaskbits)
+{
+	int i, j, c, d, n, nt;
+	int nchunks = ROUNDUP_POWER2(nmaskbits, CHUNKSZ) / CHUNKSZ;
+	u32 chunk, firstchunk = 0;
+	int chunkoff = nmaskbits & (CHUNKSZ - 1);
+	u32 chunkmask = ~((1U << chunkoff) - 1);
+
+	bitmap_clear(maskp, nmaskbits);
+
+	i = nt = 0;
+	while (ubuflen) {
+		chunk = c = n = 0;
+		while (ubuflen) {
+			if (get_user(c, ubuf++)) 
+				return -EFAULT;
+			ubuflen--;
+			if (!c || c == ',')
+				break;
+			if (isspace(c))
+				continue;
+			if (!isxdigit(c))
+				return -EINVAL;
+			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+				return -EOVERFLOW;
+			d = isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10);
+			chunk = (chunk << 4) | d;
+			n++; nt++;
+		}
+		if (n==0) {
+			if (c == ',')
+				return -EINVAL;
+			if (!c)
+				break;
+		}
+		if (i >= nchunks)
+			return -EOVERFLOW;
+		if (i > 0 || chunk) {
+			bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+			for (j = 0; j < 32; j++) {
+				if (chunk & (1 << j)) {
+					set_bit(j, maskp);
+				}
+			}
+			i++;
+			if (i == 1)
+				firstchunk = chunk;
+			if ( i == nchunks) {
+				if (chunkoff && (firstchunk & chunkmask)) {
+					/* input value > 2^nmaskbits -1 */
+					return -EOVERFLOW;
+				}
+			}
+		}
+	}
+	if (nt == 0)
+		return -EINVAL;
+	return 0;
+}
diff -Nua 2.6/include/linux/bitmap.h.0 2.6/include/linux/bitmap.h
--- 2.6/include/linux/bitmap.h.0	2004-01-15 12:10:41.000000000 -0500
+++ 2.6/include/linux/bitmap.h	2004-01-15 11:44:21.000000000 -0500
@@ -154,6 +154,12 @@
 }
 #endif
 
+extern int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, unsigned int nmaskbits);
+
+extern int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, unsigned int nmaskbits);
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
diff -Nua 2.6/include/linux/cpumask.h.0 2.6/include/linux/cpumask.h
--- 2.6/include/linux/cpumask.h.0	2004-01-15 12:10:41.000000000 -0500
+++ 2.6/include/linux/cpumask.h	2004-01-15 11:41:26.000000000 -0500
@@ -2,6 +2,7 @@
 #define __LINUX_CPUMASK_H
 
 #include <linux/threads.h>
+#include <linux/bitmap.h>
 #include <asm/cpumask.h>
 #include <asm/bug.h>
 
@@ -35,16 +36,10 @@
 		cpu < NR_CPUS;						\
 		cpu = next_online_cpu(cpu,map))
 
-extern int __mask_snprintf_len(char *buf, unsigned int buflen,
-		const unsigned long *maskp, unsigned int maskbytes);
-
 #define cpumask_snprintf(buf, buflen, map)				\
-	__mask_snprintf_len(buf, buflen, cpus_addr(map), sizeof(map))
-
-extern int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes);
+	bitmap_snprintf(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #define cpumask_parse(buf, buflen, map)					\
-	__mask_parse_len(buf, buflen, cpus_addr(map), sizeof(map))
+	bitmap_parse(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #endif /* __LINUX_CPUMASK_H */
diff -Nua 2.6/lib/mask.c.0 2.6/lib/mask.c
--- 2.6/lib/mask.c.0	2004-01-15 12:10:41.000000000 -0500
+++ 2.6/lib/mask.c	1969-12-31 19:00:00.000000000 -0500
@@ -1,178 +0,0 @@
-/*
- * lib/mask.c
- *
- * This file is subject to the terms and conditions of the GNU General Public
- * License.  See the file "COPYING" in the main directory of this archive
- * for more details.
- *
- * Copyright (C) 2003 Silicon Graphics, Inc.  All Rights Reserved.
- */
-
-/*
- * Routines to manipulate multi-word bit masks, such as cpumasks.
- *
- * The ascii representation of multi-word bit masks displays each
- * 32bit word in hex (not zero filled), and for masks longer than
- * one word, uses a comma separator between words.  Words are
- * displayed in big-endian order most significant first.  And hex
- * digits within a word are also in big-endian order, of course.
- *
- * Examples:
- *   A mask with just bit 0 set displays as "1".
- *   A mask with just bit 127 set displays as "80000000,0,0,0".
- *   A mask with just bit 64 set displays as "1,0,0".
- *   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
- *     as "1,1,10117".  The first "1" is for bit 64, the second
- *     for bit 32, the third for bit 16, and so forth, to the
- *     "7", which is for bits 2, 1 and 0.
- *   A mask with bits 32 through 39 set displays as "ff,0".
- *
- * The internal binary representation of masks is as one or
- * an array of unsigned longs, perhaps wrapped in a struct for
- * convenient use as an lvalue.  The following code doesn't know
- * about any such struct details, relying on inline macros in
- * files such as cpumask.h to pass in an unsigned long pointer
- * and a length (in bytes), describing the mask contents.
- * The 32bit words in the array are in little-endian order,
- * low order word first.  Beware that this is the reverse order
- * of the ascii representation.
- *
- * Even though the size of the input mask is provided in bytes,
- * the following code may assume that the mask is a multiple of
- * 32 or 64 bit words long, and ignore any fractional portion
- * of a word at the end.  The main reason the size is passed in
- * bytes is because it is so easy to write 'sizeof(somemask_t)'
- * in the macros.
- *
- * Masks are not a single,simple type, like classic 'C'
- * nul-term strings.  Rather they are a family of types, one
- * for each different length.  Inline macros are used to pick
- * up the actual length, where it is known to the compiler, and
- * pass it down to these routines, which work on any specified
- * length array of unsigned longs.  Poor man's templates.
- *
- * Many of the inline macros don't call into the following
- * routines.  Some of them call into other kernel routines,
- * such as memset(), set_bit() or ffs().  Some of them can
- * accomplish their task right inline, such as returning the
- * size or address of the unsigned long array, or optimized
- * versions of the macros for the most common case of an array
- * of a single unsigned long.
- */
-
-#include <linux/kernel.h>
-#include <linux/string.h>
-#include <linux/ctype.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-#include <linux/gfp.h>
-#include <asm/uaccess.h>
-
-#define MAX_HEX_PER_BYTE 4	/* dont need > 4 hex chars to encode byte */
-#define BASE 16			/* masks are input in hex (base 16) */
-#define NUL ((char)'\0')	/* nul-terminator */
-
-/**
- * __mask_snprintf_len - represent multi-word bit mask as string.
- * @buf: The buffer to place the result into
- * @buflen: The size of the buffer, including the trailing null space
- * @maskp: Points to beginning of multi-word bit mask.
- * @maskbytes: Number of bytes in bit mask at maskp.
- *
- * This routine is expected to be called from a macro such as:
- *
- * #define cpumask_snprintf(buf, buflen, mask) \
- *   __mask_snprintf_len(buf, buflen, cpus_addr(mask), sizeof(mask))
- */
-
-int __mask_snprintf_len(char *buf, unsigned int buflen,
-	const unsigned long *maskp, unsigned int maskbytes)
-{
-	u32 *wordp = (u32 *)maskp;
-	int i = maskbytes/sizeof(u32) - 1;
-	int len = 0;
-	char *sep = "";
-
-	while (i >= 1 && wordp[i] == 0)
-		i--;
-	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
-		sep = ",";
-		i--;
-	}
-	return len;
-}
-
-/**
- * __mask_parse_len - parse user string into maskbytes mask at maskp
- * @ubuf: The user buffer from which to take the string
- * @ubuflen: The size of this buffer, including the terminating char
- * @maskp: Place resulting mask (array of unsigned longs) here
- * @masklen: Construct mask at @maskp to have exactly @masklen bytes
- *
- * @masklen is a multiple of sizeof(unsigned long).  A mask of
- * @masklen bytes is constructed starting at location @maskp.
- * The value of this mask is specified by the user provided
- * string starting at address @ubuf.  Only bytes in the range
- * [@ubuf, @ubuf+@ubuflen) can be read from user space, and
- * reading will stop after the first byte that is not a comma
- * or valid hex digit in the characters [,0-9a-fA-F], or at
- * the point @ubuf+@ubuflen, whichever comes first.
- *
- * Since the user only needs about 2.25 chars per byte to encode
- * a mask (one char per nibble plus one comma separator or nul
- * terminator per byte), we blow them off with -EINVAL if they
- * claim a @ubuflen more than 4 (MAX_HEX_PER_BYTE) times maskbytes.
- * An empty word (delimited by two consecutive commas, for example)
- * is taken as zero.  If @buflen is zero, the entire @maskp is set
- * to zero.
- *
- * If the user provides fewer comma-separated ascii words
- * than there are 32 bit words in maskbytes, we zero fill the
- * remaining high order words.  If they provide more, they fail
- * with -EINVAL.  Each comma-separate ascii word is taken as
- * a hex representation; leading zeros are ignored, and do not
- * imply octal.  '00e1', 'e1', '00E1', 'E1' are all the same.
- * If user passes a word that is larger than fits in a u32,
- * they fail with -EOVERFLOW.
- */
-
-int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes)
-{
-	char buf[maskbytes * MAX_HEX_PER_BYTE + sizeof(NUL)];
-	char *bp = buf;
-	u32 *wordp = (u32 *)maskp;
-	char *p;
-	int i, j;
-
-	if (ubuflen > maskbytes * MAX_HEX_PER_BYTE)
-		return -EINVAL;
-	if (copy_from_user(buf, ubuf, ubuflen))
-		return -EFAULT;
-	buf[ubuflen] = NUL;
-
-	/*
-	 * Put the words into wordp[] in big-endian order,
-	 * then go back and reverse them.
-	 */
-	memset(wordp, 0, maskbytes);
-	i = j = 0;
-	while ((p = strsep(&bp, ",")) != NULL) {
-		unsigned long long t;
-		if (j == maskbytes/sizeof(u32))
-			return -EINVAL;
-		t = simple_strtoull(p, 0, BASE);
-		if (t != (u32)t)
-			return -EOVERFLOW;
-		wordp[j++] = t;
-	}
-	--j;
-	while (i < j) {
-		u32 t = wordp[i];
-		wordp[i] = wordp[j];
-		wordp[j] = t;
-		i++, --j;
-	}
-	return 0;
-}

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Andrew wrote:
> Gad.

Could you elaborate a bit on this critique, Andrew?

You sketch an alternative, that loops by bit, with an sprintf each
nibble, instead of looping by u32 word.  By the time that alternative is
fancied up to handle (optionally) suppression of leading zero words and
(vital, for very long masks) a 32-bit word separator, and various other
details, I doubt that it will be any simpler than the corresponding bit
of code in my patch:

        int i = maskbytes/sizeof(u32) - 1;
        int len = 0;
        char *sep = "";

        while (i >= 1 && wordp[M32X(i)] == 0)
                i--;
        while (i >= 0) {
                len += snprintf(buf+len, buflen-len,
                        "%s%x", sep, wordp[M32X(i)]);
                sep = ",";
                i--;
        }

I am at a loss to understand why the above u32 loop version of this code
is so much worse that it only merits a "Gad".

Did I provide too many comments?


> It is hardly performance-critical.

I quite agree on that.  One thing I _do_ try to optimize in most code is
the number of "fussy details".  The few operations, conditions, special
cases, and such, the better, given the finite limits of human brain power.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

> This patch captures what I am looking for in bitmap display and input.

Interesting.  I appear to have provoked Joe into a burst of coding.
Now, if I had any smarts, I would stand aside and let Joe own this,
just as Bill Irwin did when I posted my initial lib/mask.c patch a
couple months ago.


Andrew:

    If you find Joe's coding more to your liking than my "Gad" style,
    I will bless this, and after tossing in a few parting shots, will
    stand aside.  It meets my essential needs, which were:
     - chunked output (a comma every 16 or 32 bits),
     - symmetric input and output formats, and
     - display and parsing code generic to diverse bitmap sizes.

    My actual recommendation, if however you are still undecided, is:
     - my patch of last night (with the M32X() 64 bit big endian fix),
     - Joe's recommended format, zero-filling to chunksize each word,
     - Joe's renaming/refactoring from lib/mask.c to lib/bitmap.h, and
     - a chunksize of 16 rather than 32 (Joe likes 16, I don't care).

The essential differences between Joe's and my proposals that I see are:
    - Joe's has more code, especially in the parsing routine,
    - Joe's bitmap size resolution is bits, not words, and
    - I use an implied alloca of 4 x sizeof(mask) bytes.


Comments on Joe's patch:

> ChangeLog:

  Good job of summarizing for the Changelog the changes.

> o move into the bitmap.h family, rename and refactor interface to match

  I think I like this - good.

>  o bitmap size resolution changed from byte to bit

  Why?  This adds a fair bit of complexity to the code, I suspect.
  I am not aware of a need for this, but if there is one, ok.

> o chunking (digits between commas) changed from 8 to 4 digits

  Ok - either 8 or 4 works for me.  This detail should be decided
  by those working on 16 to 32 cpu systems, who will notice this
  choice the most.  Those of us on larger or smaller systems are
  going to see, or not see, separators in either case.

>  o display no longer affected by sizeof(unsigned long).

  A bit of a misstatement.  The display was only affected by the
  chunksize, one of 32 (sizeof(u32)*8) or 16 (CHUNKSZ).

>  o no alloca usage

  True.  Though on the other hand, you need to roll your own parsing
  code of comma-separated chunks, instead of getting by with using
  strsep().  So you trade alloca usage for code complexity.  Either
  way works - coders choice.  I agree that we disagree on this tradeoff.

>  o works correctly independent of the size of an unsigned long.

  And my version doesn't?

>  o works on big and little endian machine.

  With my M32X() eor-1 fix, so did mine.

> + * lib/bitmask.c - bitmask manipulation routines too big to go into bitmask.h

  Typo?  Did you mean bitmap.c and bitmap.h, not bitmask?

> +int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
> +        unsigned long *maskp, unsigned int nmaskbits)

  This routine has quite a bit more code detail than my corresponding
  parsing routine.  I hope that:
    (1) providing bit-level resolution, and
    (2) removing the implied alloca
  justifies this increase in code detail.

> +			if (isspace(c))
> +				continue;

  So a space embedded in a hex number is skipped?  That is, your code
  parses "dead,beef" and "de a d, bee  f" the same?  This seems strange.
  Perhaps you would prefer to suppress only leading spaces in each chunk:

			if (!n && isspace(c))
				continue;

> +			for (j = 0; j < 32; j++) {

  What's this "32", an unrepentant CHUNKSZ?

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

Re: seperator error in __mask_snprintf_len

[Joe Korty]

On Thu, Jan 15, 2004 at 04:17:32PM -0800, Paul Jackson wrote:
> > This patch captures what I am looking for in bitmap display and input.
> 
> Interesting.  I appear to have provoked Joe into a burst of coding.
> Now, if I had any smarts, I would stand aside and let Joe own this,
> just as Bill Irwin did when I posted my initial lib/mask.c patch a
> couple months ago.

I would prefer that we provoke each other until Andrew finds something
that he likes:)



>     If you find Joe's coding more to your liking than my "Gad" style,
>     I will bless this, and after tossing in a few parting shots, will
>     stand aside.  It meets my essential needs, which were:

I like the output parser but am not too happy with the input parser.
I would prefer that the commas on input be optional, and when present
silently skipped over.  That would greatly simplify the code and has
the added benefit that masks generated by programs (which by default
have no commas) be feedable to the parser, while still supporting
the human readable form for input.



>>  o bitmap size resolution changed from byte to bit
> 
>   Why?  This adds a fair bit of complexity to the code, I suspect.
>   I am not aware of a need for this, but if there is one, ok.

I think it important that we display exactly what the bitmask represents,
no more and no less.  This is a philosophical point, to be sure.

In any case I think we should not have the display change from one
machine to the next, simply because the size of the underlying
'unsigned long' changed underneath us.  The fact that bitmasks are
encoded in unsigned longs is entirely an internal bitmask.h affair.


>   So a space embedded in a hex number is skipped?  That is, your code
>   parses "dead,beef" and "de a d, bee  f" the same?  This seems strange.
>   Perhaps you would prefer to suppress only leading spaces in each chunk:
> 
> 			if (!n && isspace(c))
> 				continue;

Yes, this would be better.

>> +			for (j = 0; j < 32; j++) {
>   What's this "32", an unrepentant CHUNKSZ?

Oops.  Thanks, good catch.

-- 
"Money can buy bandwidth, but latency is forever" -- John Mashey
Joe

Re: seperator error in __mask_snprintf_len

[Andrew Morton]

Paul Jackson <pj@sgi.com> wrote:
>
> Andrew wrote:
> > Gad.
> 
> Could you elaborate a bit on this critique, Andrew?

The code seems very complex for such a conceptually simple problem.

And doubts remain whether it is correct on particular wordsize/endianness
machines.

It seems that there is a layering violation in which this code is poking
around inside representations which should known only to the particular
architecture.  Hence, if we can find a way to provide this function using
existing architecture API's (test_bit) then everything is solved.

If this code needs some arch-provided support function then so be it. 
That's better than adding a tangle of ifdefs in generic code.

> Did I provide too many comments?

You can never provide too many comments!

Anyway, please wake me up again when you and Joe have finished.  (I agree
that making that function take a number of bits is better than taking a
number of bytes btw).

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Joe wrote:
> I would prefer that we provoke each other until Andrew finds something
> that he likes:)

Drat ;).  Perhaps Andrew will elaborate on his "gad", and I will have
some clue of whether it is worth responding with another variant.
Clearly something in my last patch looked ugly to him.


> I would prefer that the commas on input be optional, and when present
> silently skipped over.

This wasn't an option before, in my variations that didn't zero-fill each
chunk.  But with your zero-fill, which I agree is better, this is possible.

Not a bad idea.  Another instance of Postel's Prescription:

   Be liberal in what you accept, and conservative in what you send.
     http://www.postel.org/postel.html
   Referenced in: Basics of the Unix Philosophy
     http://www.faqs.org/docs/artu/ch01s06.html

Though possibly a violation of the Rule of Composition:

   Design programs to be connected to other programs.

If commas are optional on input, then a user level program that
generates such masks could not always feed them to another user level
program that reads them.  The reader might require exact comma placement
that the producer didn't provide.

Since the primary "documentation" for this format will be what is
displayed when someone does "cat /proc/irq/prof_cpu_mask", I rather
think that the design format should be exactly what displays here,
including exact comma separation, both displaying and parsing.


> I think it important that we display exactly what the bitmask represents,
> no more and no less.  This is a philosophical point, to be sure.

Purely philosophical, as best as I can tell.  All the other bitmask
stuff works on objects that are some number of words in size.  I see no
use whatsoever for this additional complexity.

Unless you can show me a need for this, I think it is overdesign.


> In any case I think we should not have the display change from one
> machine to the next, simply because the size of the underlying
> 'unsigned long' changed underneath us.

Huh?  I am unware that my code displays differently depending on whether
the underling "unsigned long" is 4 or 8 bytes.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Thanks for the feedback, Andrew.

Two points you made that I now agree with:

 * Better that this code uses existing arch-dependent bitops,
   than that it have code pretending to be generic hiding
   additional arch specific dependencies.

 * Having just realized that the other existing include/bitmap.h
   calls take a count of bits, not bytes, I now agree with you
   and Joe that it should be bit counts.


> You can never provide too many comments!

Good - I'm on solid ground there ;)


> Anyway, please wake me up again when you and Joe have finished.

ok

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

I give, Joe.  Given the several details that are better with your
solution, I endorse your solution, with the couple of minor edits you
have in the pipeline.

It pains me to see the minor code growth (parsing went from 391 bytes
of machine code to 625), with non-trivial code duplication of the
simple_stroull() routine, and admitted increase in code complexity.

But, yes, better bits than bytes, better not to alloca(), and
better using existing bitops than misplaced arch dependencies.

And better you than me ... tag - you're it <grin>.

Bonus question:

  Should any of the other inline routines in include/bitmap.h
  be moved to your new file lib/bitmap.c?

  Others have commented that too much stuff is marked inline,
  and this might be such a case.

  For example, I count about a dozen copies of bitmask_empty(),
  mostly as cpus_empty(), in various generic and i386 files,
  each one worth perhaps 80 bytes of kernel text space.

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

Re: seperator error in __mask_snprintf_len

[Andrew Morton]

Paul Jackson <pj@sgi.com> wrote:
>
>   Should any of the other inline routines in include/bitmap.h
>    be moved to your new file lib/bitmap.c?

Yup.   The below patch will be in 2.6.1-mm4:



uninline bitmap functions

- A couple of them are using alloca (via DECLARE_BITMAP) and this generates
  a cannot-inline warning with -Winline.

- These functions are too big to inline anwyay.



---

 include/linux/bitmap.h |  140 ++++---------------------------------------------
 lib/Makefile           |    3 -
 lib/bitmap.c           |  140 +++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 156 insertions(+), 127 deletions(-)

diff -puN /dev/null lib/bitmap.c
--- /dev/null	2002-08-30 16:31:37.000000000 -0700
+++ 25-akpm/lib/bitmap.c	2004-01-14 02:52:02.000000000 -0800
@@ -0,0 +1,140 @@
+#include <linux/bitmap.h>
+#include <linux/module.h>
+
+int bitmap_empty(const unsigned long *bitmap, int bits)
+{
+	int k, lim = bits/BITS_PER_LONG;
+	for (k = 0; k < lim; ++k)
+		if (bitmap[k])
+			return 0;
+
+	if (bits % BITS_PER_LONG)
+		if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
+			return 0;
+
+	return 1;
+}
+EXPORT_SYMBOL(bitmap_empty);
+
+int bitmap_full(const unsigned long *bitmap, int bits)
+{
+	int k, lim = bits/BITS_PER_LONG;
+	for (k = 0; k < lim; ++k)
+		if (~bitmap[k])
+			return 0;
+
+	if (bits % BITS_PER_LONG)
+		if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
+			return 0;
+
+	return 1;
+}
+EXPORT_SYMBOL(bitmap_full);
+
+int bitmap_equal(const unsigned long *bitmap1,
+		unsigned long *bitmap2, int bits)
+{
+	int k, lim = bits/BITS_PER_LONG;;
+	for (k = 0; k < lim; ++k)
+		if (bitmap1[k] != bitmap2[k])
+			return 0;
+
+	if (bits % BITS_PER_LONG)
+		if ((bitmap1[k] ^ bitmap2[k]) &
+				((1UL << (bits % BITS_PER_LONG)) - 1))
+			return 0;
+
+	return 1;
+}
+EXPORT_SYMBOL(bitmap_equal);
+
+void bitmap_complement(unsigned long *bitmap, int bits)
+{
+	int k;
+
+	for (k = 0; k < BITS_TO_LONGS(bits); ++k)
+		bitmap[k] = ~bitmap[k];
+}
+EXPORT_SYMBOL(bitmap_complement);
+
+void bitmap_shift_right(unsigned long *dst,
+			const unsigned long *src, int shift, int bits)
+{
+	int k;
+	DECLARE_BITMAP(__shr_tmp, bits);
+
+	bitmap_clear(__shr_tmp, bits);
+	for (k = 0; k < bits - shift; ++k)
+		if (test_bit(k + shift, src))
+			set_bit(k, __shr_tmp);
+	bitmap_copy(dst, __shr_tmp, bits);
+}
+EXPORT_SYMBOL(bitmap_shift_right);
+
+void bitmap_shift_left(unsigned long *dst,
+			const unsigned long *src, int shift, int bits)
+{
+	int k;
+	DECLARE_BITMAP(__shl_tmp, bits);
+
+	bitmap_clear(__shl_tmp, bits);
+	for (k = bits; k >= shift; --k)
+		if (test_bit(k - shift, src))
+			set_bit(k, __shl_tmp);
+	bitmap_copy(dst, __shl_tmp, bits);
+}
+EXPORT_SYMBOL(bitmap_shift_left);
+
+void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+				const unsigned long *bitmap2, int bits)
+{
+	int k;
+	int nr = BITS_TO_LONGS(bits);
+
+	for (k = 0; k < nr; k++)
+		dst[k] = bitmap1[k] & bitmap2[k];
+}
+EXPORT_SYMBOL(bitmap_and);
+
+void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+				const unsigned long *bitmap2, int bits)
+{
+	int k;
+	int nr = BITS_TO_LONGS(bits);
+
+	for (k = 0; k < nr; k++)
+		dst[k] = bitmap1[k] | bitmap2[k];
+}
+EXPORT_SYMBOL(bitmap_or);
+
+#if BITS_PER_LONG == 32
+int bitmap_weight(const unsigned long *bitmap, int bits)
+{
+	int k, w = 0, lim = bits/BITS_PER_LONG;
+
+	for (k = 0; k < lim; k++)
+		w += hweight32(bitmap[k]);
+
+	if (bits % BITS_PER_LONG)
+		w += hweight32(bitmap[k] &
+				((1UL << (bits % BITS_PER_LONG)) - 1));
+
+	return w;
+}
+#else
+int bitmap_weight(const unsigned long *bitmap, int bits)
+{
+	int k, w = 0, lim = bits/BITS_PER_LONG;
+
+	for (k = 0; k < lim; k++)
+		w += hweight64(bitmap[k]);
+
+	if (bits % BITS_PER_LONG)
+		w += hweight64(bitmap[k] &
+				((1UL << (bits % BITS_PER_LONG)) - 1));
+
+	return w;
+}
+#endif
+EXPORT_SYMBOL(bitmap_weight);
+
diff -puN include/linux/bitmap.h~uninline-bitmap-functions include/linux/bitmap.h
--- 25/include/linux/bitmap.h~uninline-bitmap-functions	2004-01-14 02:36:26.000000000 -0800
+++ 25-akpm/include/linux/bitmap.h	2004-01-14 02:36:26.000000000 -0800
@@ -10,57 +10,11 @@
 #include <linux/bitops.h>
 #include <linux/string.h>
 
-static inline int bitmap_empty(const unsigned long *bitmap, int bits)
-{
-	int k, lim = bits/BITS_PER_LONG;
-	for (k = 0; k < lim; ++k)
-		if (bitmap[k])
-			return 0;
-
-	if (bits % BITS_PER_LONG)
-		if (bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
-			return 0;
-
-	return 1;
-}
-
-static inline int bitmap_full(const unsigned long *bitmap, int bits)
-{
-	int k, lim = bits/BITS_PER_LONG;
-	for (k = 0; k < lim; ++k)
-		if (~bitmap[k])
-			return 0;
-
-	if (bits % BITS_PER_LONG)
-		if (~bitmap[k] & ((1UL << (bits % BITS_PER_LONG)) - 1))
-			return 0;
-
-	return 1;
-}
-
-static inline int bitmap_equal(const unsigned long *bitmap1,
-				unsigned long *bitmap2, int bits)
-{
-	int k, lim = bits/BITS_PER_LONG;;
-	for (k = 0; k < lim; ++k)
-		if (bitmap1[k] != bitmap2[k])
-			return 0;
-
-	if (bits % BITS_PER_LONG)
-		if ((bitmap1[k] ^ bitmap2[k]) &
-				((1UL << (bits % BITS_PER_LONG)) - 1))
-			return 0;
-
-	return 1;
-}
-
-static inline void bitmap_complement(unsigned long *bitmap, int bits)
-{
-	int k;
-
-	for (k = 0; k < BITS_TO_LONGS(bits); ++k)
-		bitmap[k] = ~bitmap[k];
-}
+int bitmap_empty(const unsigned long *bitmap, int bits);
+int bitmap_full(const unsigned long *bitmap, int bits);
+int bitmap_equal(const unsigned long *bitmap1,
+			unsigned long *bitmap2, int bits);
+void bitmap_complement(unsigned long *bitmap, int bits);
 
 static inline void bitmap_clear(unsigned long *bitmap, int bits)
 {
@@ -78,81 +32,15 @@ static inline void bitmap_copy(unsigned 
 	memcpy(dst, src, BITS_TO_LONGS(bits)*sizeof(unsigned long));
 }
 
-static inline void bitmap_shift_right(unsigned long *dst,
-				const unsigned long *src, int shift, int bits)
-{
-	int k;
-	DECLARE_BITMAP(__shr_tmp, bits);
-
-	bitmap_clear(__shr_tmp, bits);
-	for (k = 0; k < bits - shift; ++k)
-		if (test_bit(k + shift, src))
-			set_bit(k, __shr_tmp);
-	bitmap_copy(dst, __shr_tmp, bits);
-}
-
-static inline void bitmap_shift_left(unsigned long *dst,
-				const unsigned long *src, int shift, int bits)
-{
-	int k;
-	DECLARE_BITMAP(__shl_tmp, bits);
-
-	bitmap_clear(__shl_tmp, bits);
-	for (k = bits; k >= shift; --k)
-		if (test_bit(k - shift, src))
-			set_bit(k, __shl_tmp);
-	bitmap_copy(dst, __shl_tmp, bits);
-}
-
-static inline void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
-{
-	int k;
-	int nr = BITS_TO_LONGS(bits);
-
-	for (k = 0; k < nr; k++)
-		dst[k] = bitmap1[k] & bitmap2[k];
-}
-
-static inline void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
-				const unsigned long *bitmap2, int bits)
-{
-	int k;
-	int nr = BITS_TO_LONGS(bits);
-
-	for (k = 0; k < nr; k++)
-		dst[k] = bitmap1[k] | bitmap2[k];
-}
-
-#if BITS_PER_LONG == 32
-static inline int bitmap_weight(const unsigned long *bitmap, int bits)
-{
-	int k, w = 0, lim = bits/BITS_PER_LONG;
-
-	for (k = 0; k < lim; k++)
-		w += hweight32(bitmap[k]);
-
-	if (bits % BITS_PER_LONG)
-		w += hweight32(bitmap[k] &
-				((1UL << (bits % BITS_PER_LONG)) - 1));
-
-	return w;
-}
-#else
-static inline int bitmap_weight(const unsigned long *bitmap, int bits)
-{
-	int k, w = 0, lim = bits/BITS_PER_LONG;
-
-	for (k = 0; k < lim; k++)
-		w += hweight64(bitmap[k]);
-
-	if (bits % BITS_PER_LONG)
-		w += hweight64(bitmap[k] &
-				((1UL << (bits % BITS_PER_LONG)) - 1));
-
-	return w;
-}
-#endif
+void bitmap_shift_right(unsigned long *dst,
+			const unsigned long *src, int shift, int bits);
+void bitmap_shift_left(unsigned long *dst,
+			const unsigned long *src, int shift, int bits);
+void bitmap_and(unsigned long *dst, const unsigned long *bitmap1,
+			const unsigned long *bitmap2, int bits);
+void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
+			const unsigned long *bitmap2, int bits);
+int bitmap_weight(const unsigned long *bitmap, int bits);
 
 #endif /* __ASSEMBLY__ */
 
diff -puN lib/Makefile~uninline-bitmap-functions lib/Makefile
--- 25/lib/Makefile~uninline-bitmap-functions	2004-01-14 02:36:26.000000000 -0800
+++ 25-akpm/lib/Makefile	2004-01-14 02:36:26.000000000 -0800
@@ -5,7 +5,8 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o
+	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o \
+	 bitmap.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
 lib-$(CONFIG_RWSEM_XCHGADD_ALGORITHM) += rwsem.o

_

Re: seperator error in __mask_snprintf_len

[William Lee Irwin III]

Paul Jackson <pj@sgi.com> wrote:
>>   Should any of the other inline routines in include/bitmap.h
>>    be moved to your new file lib/bitmap.c?

On Thu, Jan 15, 2004 at 09:26:13PM -0800, Andrew Morton wrote:
> Yup.   The below patch will be in 2.6.1-mm4:
> uninline bitmap functions
> - A couple of them are using alloca (via DECLARE_BITMAP) and this generates
>   a cannot-inline warning with -Winline.
> - These functions are too big to inline anwyay.

Uninlining is good (I originally wanted to avoid controversy by not
having them compiled in unless they were called), but it's also possible
to remove the stack allocations entirely with more sophisticated
implementations. These are actually quite dumb as implementations of the
bitmap operations, and meant to look simple as opposed to performing well
or being well-behaved with respect to stackspace.


-- wli

Re: seperator error in __mask_snprintf_len

[Joe Korty]

On Thu, Jan 15, 2004 at 09:14:02PM -0800, Paul Jackson wrote:
> I give, Joe.  Given the several details that are better with your
> solution, I endorse your solution, with the couple of minor edits you
> have in the pipeline.
> 
> It pains me to see the minor code growth (parsing went from 391 bytes
> of machine code to 625), with non-trivial code duplication of the
> simple_stroull() routine, and admitted increase in code complexity.
> 
> But, yes, better bits than bytes, better not to alloca(), and
> better using existing bitops than misplaced arch dependencies.

First of all, I don't like my parser anymore so I hope you don't back
out, Paul.  Perhaps all that is needed to make your parser acceptable
to Andrew is 1) tweak it to use bitmap_shift_right / set_bit, and 2)
use nbits in the interface but immediately convert it to the nbytes that
the algorithm actually wants.

Over the weekend, I may poke at my version and look over yours again
and perhaps yet a third version will come out of this.  Which is a good
thing since lots of choices to pick and merge from is what is best for
Andrew and for Linux.

Joe

Re: seperator error in __mask_snprintf_len

[Matthew Dobson]

FWIW, I think a 32-bit chunk-size is preferable.  I personally don't 
think "dead,beef" is easier to read than "deadbeef", nor "0073,0f0f" 
compared to "00730f0f".  On the small CPU count, ie: <=32, either 
version is pretty readable, but on larger CPU count boxen you're going 
to overflow your brain counting groups of 4 versus groups of 8.  I can't 
believe I just called a 32 CPU box "small".  My world perspective is a 
bit skewed... ;)

Also, on the input side, a lot of apps will output a 32-bit CPU mask. 
With commas separating every 32 bits, we can feed an "uncommafied" mask 
to the kernel and it won't barf.  If we go with 16-bit chunks, we'll 
have to "commafy" these 32-bit bitmasks to feed them to the kernel.

As a NUMA guy who deals with largish CPU count machines daily, that's my 
2 cents...

-Matt


Paul Jackson wrote:
>>This patch captures what I am looking for in bitmap display and input.
> 
> 
> Interesting.  I appear to have provoked Joe into a burst of coding.
> Now, if I had any smarts, I would stand aside and let Joe own this,
> just as Bill Irwin did when I posted my initial lib/mask.c patch a
> couple months ago.
> 
> 
> Andrew:
> 
>     If you find Joe's coding more to your liking than my "Gad" style,
>     I will bless this, and after tossing in a few parting shots, will
>     stand aside.  It meets my essential needs, which were:
>      - chunked output (a comma every 16 or 32 bits),
>      - symmetric input and output formats, and
>      - display and parsing code generic to diverse bitmap sizes.
> 
>     My actual recommendation, if however you are still undecided, is:
>      - my patch of last night (with the M32X() 64 bit big endian fix),
>      - Joe's recommended format, zero-filling to chunksize each word,
>      - Joe's renaming/refactoring from lib/mask.c to lib/bitmap.h, and
>      - a chunksize of 16 rather than 32 (Joe likes 16, I don't care).
> 
> The essential differences between Joe's and my proposals that I see are:
>     - Joe's has more code, especially in the parsing routine,
>     - Joe's bitmap size resolution is bits, not words, and
>     - I use an implied alloca of 4 x sizeof(mask) bytes.
> 
> 
> Comments on Joe's patch:
> 
> 
>>ChangeLog:
> 
> 
>   Good job of summarizing for the Changelog the changes.
> 
> 
>>o move into the bitmap.h family, rename and refactor interface to match
> 
> 
>   I think I like this - good.
> 
> 
>> o bitmap size resolution changed from byte to bit
> 
> 
>   Why?  This adds a fair bit of complexity to the code, I suspect.
>   I am not aware of a need for this, but if there is one, ok.
> 
> 
>>o chunking (digits between commas) changed from 8 to 4 digits
> 
> 
>   Ok - either 8 or 4 works for me.  This detail should be decided
>   by those working on 16 to 32 cpu systems, who will notice this
>   choice the most.  Those of us on larger or smaller systems are
>   going to see, or not see, separators in either case.
> 
> 
>> o display no longer affected by sizeof(unsigned long).
> 
> 
>   A bit of a misstatement.  The display was only affected by the
>   chunksize, one of 32 (sizeof(u32)*8) or 16 (CHUNKSZ).
> 
> 
>> o no alloca usage
> 
> 
>   True.  Though on the other hand, you need to roll your own parsing
>   code of comma-separated chunks, instead of getting by with using
>   strsep().  So you trade alloca usage for code complexity.  Either
>   way works - coders choice.  I agree that we disagree on this tradeoff.
> 
> 
>> o works correctly independent of the size of an unsigned long.
> 
> 
>   And my version doesn't?
> 
> 
>> o works on big and little endian machine.
> 
> 
>   With my M32X() eor-1 fix, so did mine.
> 
> 
>>+ * lib/bitmask.c - bitmask manipulation routines too big to go into bitmask.h
> 
> 
>   Typo?  Did you mean bitmap.c and bitmap.h, not bitmask?
> 
> 
>>+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
>>+        unsigned long *maskp, unsigned int nmaskbits)
> 
> 
>   This routine has quite a bit more code detail than my corresponding
>   parsing routine.  I hope that:
>     (1) providing bit-level resolution, and
>     (2) removing the implied alloca
>   justifies this increase in code detail.
> 
> 
>>+			if (isspace(c))
>>+				continue;
> 
> 
>   So a space embedded in a hex number is skipped?  That is, your code
>   parses "dead,beef" and "de a d, bee  f" the same?  This seems strange.
>   Perhaps you would prefer to suppress only leading spaces in each chunk:
> 
> 			if (!n && isspace(c))
> 				continue;
> 
> 
>>+			for (j = 0; j < 32; j++) {
> 
> 
>   What's this "32", an unrepentant CHUNKSZ?
> 

[PATCH] bitmap parsing routines, version 3

[Joe Korty]

Andrew, Paul, Matthew,
 This bitmask parsing/printing patch addresses all concerns except code
size, that I am aware of.

The most significant change is the replacement of the rather complex
firstchunk, chunkmask system of detecting if the value fits into
nmaskbits, with one that directly measures the #bits in the value as
accumulated so far and compares that with nmaskbits.  This resulted
in a significant slimming-down of bitmap_parse, though not to the point
of approaching Paul's original version in simplicity.

Applies against 2.6.1-mm4.

Regards,
Joe

Changelog:
 o forbid embedded whitespace, allow leading whitespace (Paul Jackson)
 o trailing whitespace stops parsing, like \0 does.
 o chunk size now 32 bits (Matthew Dobson)
 o cleaner, smaller fit-into-nbits error checking code.
 o bugfix, j < 32 should be j < CHUNKSZ (Paul Jackson)
 o fix sometimes consumption of bytes between \0 and eobuf



diff -Nura base/include/linux/bitmap.h new/include/linux/bitmap.h
--- base/include/linux/bitmap.h	2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/bitmap.h	2004-01-17 00:13:50.000000000 -0500
@@ -42,6 +42,12 @@
 			const unsigned long *bitmap2, int bits);
 int bitmap_weight(const unsigned long *bitmap, int bits);
 
+extern int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, int bits);
+
+extern int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, int bits);
+
 #endif /* __ASSEMBLY__ */
 
 #endif /* __LINUX_BITMAP_H */
diff -Nura base/include/linux/cpumask.h new/include/linux/cpumask.h
--- base/include/linux/cpumask.h	2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/cpumask.h	2004-01-17 00:13:50.000000000 -0500
@@ -2,6 +2,7 @@
 #define __LINUX_CPUMASK_H
 
 #include <linux/threads.h>
+#include <linux/bitmap.h>
 #include <asm/cpumask.h>
 #include <asm/bug.h>
 
@@ -31,16 +32,10 @@
 #define for_each_online_cpu(cpu) for (cpu = 0; cpu < 1; cpu++)
 #endif
 
-extern int __mask_snprintf_len(char *buf, unsigned int buflen,
-		const unsigned long *maskp, unsigned int maskbytes);
-
 #define cpumask_snprintf(buf, buflen, map)				\
-	__mask_snprintf_len(buf, buflen, cpus_addr(map), sizeof(map))
-
-extern int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes);
+	bitmap_snprintf(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #define cpumask_parse(buf, buflen, map)					\
-	__mask_parse_len(buf, buflen, cpus_addr(map), sizeof(map))
+	bitmap_parse(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #endif /* __LINUX_CPUMASK_H */
diff -Nura base/lib/Makefile new/lib/Makefile
--- base/lib/Makefile	2004-01-17 00:10:11.000000000 -0500
+++ new/lib/Makefile	2004-01-17 00:13:50.000000000 -0500
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o \
+	 kobject.o idr.o div64.o parser.o int_sqrt.o \
 	 bitmap.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
diff -Nura base/lib/bitmap.c new/lib/bitmap.c
--- base/lib/bitmap.c	2004-01-17 00:10:11.000000000 -0500
+++ new/lib/bitmap.c	2004-01-17 00:34:02.000000000 -0500
@@ -1,5 +1,16 @@
-#include <linux/bitmap.h>
+/*
+ * lib/bitmap.c
+ * Helper functions for bitmap.h.
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
 #include <linux/module.h>
+#include <linux/ctype.h>
+#include <linux/errno.h>
+#include <linux/bitmap.h>
+#include <asm/bitops.h>
+#include <asm/uaccess.h>
 
 int bitmap_empty(const unsigned long *bitmap, int bits)
 {
@@ -138,3 +149,115 @@
 #endif
 EXPORT_SYMBOL(bitmap_weight);
 
+/*
+ * Bitmap printing & parsing functions: first version by Bill Irwin,
+ * second version by Paul Jackson, third by Joe Korty.
+ */
+
+#define CHUNKSZ				32
+#define bits_to_hold_value(val)		fls(val)
+#define roundup_power2(val,modulus)	(((val) + (modulus) - 1) & ~((modulus) - 1))
+#define unhex(c)			(isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
+
+/**
+ * bitmap_snprintf - convert bitmap to a hex string.
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
+ * comma-separated sets of eight digits per set.
+ */
+int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, int nmaskbits)
+{
+	int i, word, bit, len = 0; 
+	unsigned long val;
+	const char *sep = "";
+	int chunksz;
+	u32 chunkmask;
+
+	chunksz = nmaskbits & (CHUNKSZ - 1);
+	if (chunksz == 0)
+		chunksz = CHUNKSZ;
+
+	i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
+	for (; i >= 0; i -= CHUNKSZ) {
+		chunkmask = ((1ULL << chunksz) - 1);
+		word = i / BITS_PER_LONG;
+		bit = i % BITS_PER_LONG;
+		val = (maskp[word] >> bit) & chunkmask;
+		len += snprintf(buf+len, buflen-len, "%s%0*lx", sep,
+			(chunksz+3)/4, val);
+		chunksz = CHUNKSZ;
+		sep = ",";
+	}
+	return len;
+}
+EXPORT_SYMBOL(bitmap_snprintf);
+
+/**
+ * bitmap_parse - convert a hex string into a bitmap.
+ * @buf: pointer to buffer in user space containing string.
+ * @buflen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0 or whitespace.
+ * @maskp: pointer to bitmap that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Commas group hex digits into chunks. Each chunk defines exactly 32
+ * bits of the resultant bitmask.  No chunk may specify a value larger
+ * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
+ * then leading 0-bits are appended.  Leading spaces accepted.  -EINVAL
+ * is returned for illegal characters and grouping errors such as "1,,5",
+ " ,44", "," and "".
+ */
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, int nmaskbits)
+{
+	int i, j, c, n, nt, nb;
+	u32 chunk;
+
+	bitmap_clear(maskp, nmaskbits);
+
+	i = nt = nb = 0;
+	do {
+		chunk = c = n = 0;
+		while (ubuflen) {
+			if (get_user(c, ubuf++)) 
+				return -EFAULT;
+			ubuflen--;
+			if (!c || c == ',')
+				break;
+			if (isspace(c)) {
+				if (nt == 0)
+					continue;
+				c = '\0';
+				break;
+			}
+			if (!isxdigit(c))
+				return -EINVAL;
+			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+				return -EOVERFLOW;
+			chunk = (chunk << 4) | unhex(c);
+			n++; nt++;
+		}
+		if (n == 0)
+			break;
+		if (i > 0 || chunk) {
+			bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+			for (j = 0; j < CHUNKSZ; j++)
+				if (chunk & (1 << j))
+					set_bit(j, maskp);
+			i++;
+			nb += (i == 1) ? bits_to_hold_value(chunk) : CHUNKSZ;
+			if (nb > nmaskbits)
+				return -EOVERFLOW;
+		}
+	} while (ubuflen && c == ',');
+
+	if (nt == 0 || c == ',')
+		return -EINVAL;
+	return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);
diff -Nura base/lib/mask.c new/lib/mask.c
--- base/lib/mask.c	2004-01-09 01:59:34.000000000 -0500
+++ new/lib/mask.c	1969-12-31 19:00:00.000000000 -0500
@@ -1,178 +0,0 @@
-/*
- * lib/mask.c
- *
- * This file is subject to the terms and conditions of the GNU General Public
- * License.  See the file "COPYING" in the main directory of this archive
- * for more details.
- *
- * Copyright (C) 2003 Silicon Graphics, Inc.  All Rights Reserved.
- */
-
-/*
- * Routines to manipulate multi-word bit masks, such as cpumasks.
- *
- * The ascii representation of multi-word bit masks displays each
- * 32bit word in hex (not zero filled), and for masks longer than
- * one word, uses a comma separator between words.  Words are
- * displayed in big-endian order most significant first.  And hex
- * digits within a word are also in big-endian order, of course.
- *
- * Examples:
- *   A mask with just bit 0 set displays as "1".
- *   A mask with just bit 127 set displays as "80000000,0,0,0".
- *   A mask with just bit 64 set displays as "1,0,0".
- *   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
- *     as "1,1,10117".  The first "1" is for bit 64, the second
- *     for bit 32, the third for bit 16, and so forth, to the
- *     "7", which is for bits 2, 1 and 0.
- *   A mask with bits 32 through 39 set displays as "ff,0".
- *
- * The internal binary representation of masks is as one or
- * an array of unsigned longs, perhaps wrapped in a struct for
- * convenient use as an lvalue.  The following code doesn't know
- * about any such struct details, relying on inline macros in
- * files such as cpumask.h to pass in an unsigned long pointer
- * and a length (in bytes), describing the mask contents.
- * The 32bit words in the array are in little-endian order,
- * low order word first.  Beware that this is the reverse order
- * of the ascii representation.
- *
- * Even though the size of the input mask is provided in bytes,
- * the following code may assume that the mask is a multiple of
- * 32 or 64 bit words long, and ignore any fractional portion
- * of a word at the end.  The main reason the size is passed in
- * bytes is because it is so easy to write 'sizeof(somemask_t)'
- * in the macros.
- *
- * Masks are not a single,simple type, like classic 'C'
- * nul-term strings.  Rather they are a family of types, one
- * for each different length.  Inline macros are used to pick
- * up the actual length, where it is known to the compiler, and
- * pass it down to these routines, which work on any specified
- * length array of unsigned longs.  Poor man's templates.
- *
- * Many of the inline macros don't call into the following
- * routines.  Some of them call into other kernel routines,
- * such as memset(), set_bit() or ffs().  Some of them can
- * accomplish their task right inline, such as returning the
- * size or address of the unsigned long array, or optimized
- * versions of the macros for the most common case of an array
- * of a single unsigned long.
- */
-
-#include <linux/kernel.h>
-#include <linux/string.h>
-#include <linux/ctype.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-#include <linux/gfp.h>
-#include <asm/uaccess.h>
-
-#define MAX_HEX_PER_BYTE 4	/* dont need > 4 hex chars to encode byte */
-#define BASE 16			/* masks are input in hex (base 16) */
-#define NUL ((char)'\0')	/* nul-terminator */
-
-/**
- * __mask_snprintf_len - represent multi-word bit mask as string.
- * @buf: The buffer to place the result into
- * @buflen: The size of the buffer, including the trailing null space
- * @maskp: Points to beginning of multi-word bit mask.
- * @maskbytes: Number of bytes in bit mask at maskp.
- *
- * This routine is expected to be called from a macro such as:
- *
- * #define cpumask_snprintf(buf, buflen, mask) \
- *   __mask_snprintf_len(buf, buflen, cpus_addr(mask), sizeof(mask))
- */
-
-int __mask_snprintf_len(char *buf, unsigned int buflen,
-	const unsigned long *maskp, unsigned int maskbytes)
-{
-	u32 *wordp = (u32 *)maskp;
-	int i = maskbytes/sizeof(u32) - 1;
-	int len = 0;
-	char *sep = "";
-
-	while (i >= 1 && wordp[i] == 0)
-		i--;
-	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
-		sep = ",";
-		i--;
-	}
-	return len;
-}
-
-/**
- * __mask_parse_len - parse user string into maskbytes mask at maskp
- * @ubuf: The user buffer from which to take the string
- * @ubuflen: The size of this buffer, including the terminating char
- * @maskp: Place resulting mask (array of unsigned longs) here
- * @masklen: Construct mask at @maskp to have exactly @masklen bytes
- *
- * @masklen is a multiple of sizeof(unsigned long).  A mask of
- * @masklen bytes is constructed starting at location @maskp.
- * The value of this mask is specified by the user provided
- * string starting at address @ubuf.  Only bytes in the range
- * [@ubuf, @ubuf+@ubuflen) can be read from user space, and
- * reading will stop after the first byte that is not a comma
- * or valid hex digit in the characters [,0-9a-fA-F], or at
- * the point @ubuf+@ubuflen, whichever comes first.
- *
- * Since the user only needs about 2.25 chars per byte to encode
- * a mask (one char per nibble plus one comma separator or nul
- * terminator per byte), we blow them off with -EINVAL if they
- * claim a @ubuflen more than 4 (MAX_HEX_PER_BYTE) times maskbytes.
- * An empty word (delimited by two consecutive commas, for example)
- * is taken as zero.  If @buflen is zero, the entire @maskp is set
- * to zero.
- *
- * If the user provides fewer comma-separated ascii words
- * than there are 32 bit words in maskbytes, we zero fill the
- * remaining high order words.  If they provide more, they fail
- * with -EINVAL.  Each comma-separate ascii word is taken as
- * a hex representation; leading zeros are ignored, and do not
- * imply octal.  '00e1', 'e1', '00E1', 'E1' are all the same.
- * If user passes a word that is larger than fits in a u32,
- * they fail with -EOVERFLOW.
- */
-
-int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes)
-{
-	char buf[maskbytes * MAX_HEX_PER_BYTE + sizeof(NUL)];
-	char *bp = buf;
-	u32 *wordp = (u32 *)maskp;
-	char *p;
-	int i, j;
-
-	if (ubuflen > maskbytes * MAX_HEX_PER_BYTE)
-		return -EINVAL;
-	if (copy_from_user(buf, ubuf, ubuflen))
-		return -EFAULT;
-	buf[ubuflen] = NUL;
-
-	/*
-	 * Put the words into wordp[] in big-endian order,
-	 * then go back and reverse them.
-	 */
-	memset(wordp, 0, maskbytes);
-	i = j = 0;
-	while ((p = strsep(&bp, ",")) != NULL) {
-		unsigned long long t;
-		if (j == maskbytes/sizeof(u32))
-			return -EINVAL;
-		t = simple_strtoull(p, 0, BASE);
-		if (t != (u32)t)
-			return -EOVERFLOW;
-		wordp[j++] = t;
-	}
-	--j;
-	while (i < j) {
-		u32 t = wordp[i];
-		wordp[i] = wordp[j];
-		wordp[j] = t;
-		i++, --j;
-	}
-	return 0;
-}

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

> I think a 32-bit chunk-size is preferable.

I see that Joe has been persuaded by your points,
in his latest patch.

Good - 32 it is.  Thanks.

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

Re: seperator error in __mask_snprintf_len

[Paul Jackson]

Joe wrote:
> First of all, I don't like my parser anymore so I hope you don't back
> out, Paul.

Well, I see Joe has already refined his version, as version 3
in my inbox.

Here is a half-baked refinement of mine, based on Joe's version 2
of a couple days ago:

 o It is called with a bit count, not a byte count.
 o It uses kmalloc()/kfree(), instead of implied alloca().
 o The M32X() eor-1 index swizzling was moved to linux/bitops.h
 o The CHUNKSZ is 32.  Thanks, Matthew.

However:
 - The parsing code is in my u32 word style, but the printing
     code in Joe's bit fiddling style.
 - It has never been tested.
 - It is now only moderately "simpler" than Joe's version 3,
     in my view.  Source line count may well favor Joe's by
     now.
 - While I moved the ifdef'd defines of the magic eor-1 index
     macro to linux/bitops.h, it's still an ifdef'd define,
     because I still think that is the most robust and maintainable
     way of stating this detail.
 - It has not been upgraded with any relavent refinements from
     Joe's version 3.

My take is that we should go with Joe's.  Personally, I don't like, and
avoid at great effort, bit coding.  However, this stuff _is_ all about
bits, and for the purposes of maintainability, I conjecture that it is
better to have code in a style that future hackers of this code are most
likely to be comfortable with.  My careful use of C types to avoid bit
details is a minor negative, even if it does reduce the code size a
little.

If there is a concensus to the contrary, and a hue and cry for my u32
word style of coding, then the printing routine should be redone in the
same style, and the other negatives above addressed, before this is
accepted.

# This is a BitKeeper generated patch for the following project:
# Project Name: Linux kernel tree
# This patch format is intended for GNU patch command version 2.5 or higher.
# This patch includes the following deltas:
#	           ChangeSet	1.1506  -> 1.1507 
#	        lib/bitmap.c	1.1     -> 1.2    
#	include/linux/bitops.h	1.6     -> 1.7    
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/01/17	pj@sgi.com	1.1507
# rework bitmap_parse - takes bits, u32 word style algorithm
# --------------------------------------------
#
diff -Nru a/include/linux/bitops.h b/include/linux/bitops.h
--- a/include/linux/bitops.h	Sat Jan 17 01:47:35 2004
+++ b/include/linux/bitops.h	Sat Jan 17 01:47:35 2004
@@ -130,4 +130,29 @@
 	return sizeof(w) == 4 ? generic_hweight32(w) : generic_hweight64(w);
 }
 
+/*
+ * Bitops apply to arrays of unsigned long.  This is almost
+ * the same as an array of unsigned ints, except on 64 bit big
+ * endian architectures, in which the two 32-bit int halves of
+ * each long are reversed (big 32-bit halfword first, naturally).
+ *
+ * Use this BIT32X (for "BITop 32-bit indeX") macro to index the
+ * i-th word of a bit mask declared as an array of 32 bit words.
+ *
+ * Usage example accessing 32-bit words in mask[] in order,
+ * smallest first:
+ *    u32 mask[MASKLENGTH];
+ *    int i;
+ *    for (i = 0; i < MASKLENGTH; i++)
+ *        ... mask[BIT32X(i)] ...
+ */
+#ifndef BIT32X
+#include <asm/byteorder.h>
+#if BITS_PER_LONG == 64 && defined(__BIG_ENDIAN)
+#define BIT32X(i) ((i)^1)
+#elif BITS_PER_LONG == 32 || defined(__LITTLE_ENDIAN)
+#define BIT32X(i) (i)
+#endif
+#endif
+
 #endif
diff -Nru a/lib/bitmap.c b/lib/bitmap.c
--- a/lib/bitmap.c	Sat Jan 17 01:47:35 2004
+++ b/lib/bitmap.c	Sat Jan 17 01:47:35 2004
@@ -11,11 +11,12 @@
 #include <linux/ctype.h>
 #include <linux/errno.h>
 #include <linux/bitmap.h>
+#include <linux/slab.h>
 #include <asm/uaccess.h>
 
-#define CHUNKSZ		16
+#define CHUNKSZ		32
 
-#define ROUNDUP_POWER2(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
+#define ROUND_UP(val,modulus) (((val) + (modulus) - 1) & ~((modulus) - 1))
 
 
 /**
@@ -25,8 +26,8 @@
  * @maskp: pointer to bitmap to convert
  * @nmaskbits: size of bitmap, in bits
  *
- * Exactly nmaskbits bits are displayed.  Hex digits are grouped into
- * fours seperated by commas.
+ * Exactly nmaskbits bits are displayed.  Hex digits are put
+ * in groups of eight, seperated by commas.
  */
 
 int bitmap_snprintf(char *buf, unsigned int buflen,
@@ -42,7 +43,7 @@
 	if (chunksz == 0)
 		chunksz = CHUNKSZ;
 
-	i = ROUNDUP_POWER2(nmaskbits, CHUNKSZ) - CHUNKSZ;
+	i = ROUND_UP(nmaskbits, CHUNKSZ) - CHUNKSZ;
 	for (; i >= 0; i -= CHUNKSZ) {
 		chunkmask = ((1ULL << chunksz) - 1);
 		word = i / BITS_PER_LONG;
@@ -55,6 +56,11 @@
 	}
 	return len;
 }
+
+#define MAX_HEX_PER_BYTE 4	/* dont need > 4 hex chars to encode byte */
+#define BASE 16			/* masks are input in hex (base 16) */
+#define NUL ((char)'\0')	/* nul-terminator */
+
 /**
 * bitmap_parse - convert an ASCII hex string into a bitmap.
 * @buf: pointer to buffer in user space containing string.
@@ -63,68 +69,89 @@
 * @maskp: pointer to bitmap that will contain result.
 * @nmaskbits: size of bitmap, in bits.
 *
-* Commas group hex digits into chunks. Each chunk defines exactly 16
+* Commas group hex digits into chunks. Each chunk defines exactly 32
 * bits of the resultant bitmask.  No chunk may specify a value larger
-* than 16 bits (-EOVERFLOW), and if a chunk specifies a smaller value
+* than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
 * leading 0-bits are appended.
+*
+* Since the user only needs about 2.25 chars per byte to encode
+* a mask (one char per nibble plus one comma separator or nul
+* terminator per byte), we blow them off with -EINVAL if they
+* claim a @ubuflen more than 4 (MAX_HEX_PER_BYTE) times maskbytes.
+* An empty word (delimited by two consecutive commas, for example)
+* is taken as zero.  If @buflen is zero, the entire @maskp is set
+* to zero.
+*
+* If the user provides fewer comma-separated ascii words
+* than there are 32 bit words in maskbytes, we zero fill the
+* remaining high order words.  If they provide more, they fail
+* with -EINVAL.  Each comma-separate ascii word is taken as
+* a hex representation; leading zeros are ignored, and do not
+* imply octal.  '00e1', 'e1', '00E1', 'E1' are all the same.
+* If user passes a word that is larger than fits in a u32,
+* they fail with -EOVERFLOW.
 */
+
 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
         unsigned long *maskp, unsigned int nmaskbits)
 {
-	int i, j, c, d, n, nt;
-	int nchunks = ROUNDUP_POWER2(nmaskbits, CHUNKSZ) / CHUNKSZ;
-	u32 chunk, firstchunk = 0;
-	int chunkoff = nmaskbits & (CHUNKSZ - 1);
-	u32 chunkmask = ~((1U << chunkoff) - 1);
-
-	bitmap_clear(maskp, nmaskbits);
-
-	i = nt = 0;
-	while (ubuflen) {
-		chunk = c = n = 0;
-		while (ubuflen) {
-			if (get_user(c, ubuf++)) 
-				return -EFAULT;
-			ubuflen--;
-			if (!c || c == ',')
-				break;
-			if (isspace(c))
-				continue;
-			if (!isxdigit(c))
-				return -EINVAL;
-			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
-				return -EOVERFLOW;
-			d = isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10);
-			chunk = (chunk << 4) | d;
-			n++; nt++;
-		}
-		if (n==0) {
-			if (c == ',')
-				return -EINVAL;
-			if (!c)
-				break;
+	char *buf;		/* copy user's ubuf[] to here */
+	char *bp;		/* strsep() cursor over buf[] */
+	unsigned maskbytes;	/* bytes in nmaskbits, round to sizeof(u32) */
+	u32 *wordp;		/* access output maskp as array of u32 */
+	char *p;		/* scan comma separated input hex words */
+	int i, j;		/* index output wordp[] */
+	int lwbits;		/* num bits ok set in last word (0 == all) */
+	int ret;		/* return value */
+
+	maskbytes = ROUND_UP(nmaskbits, CHUNKSZ)/CHUNKSZ;
+	if (ubuflen > maskbytes * MAX_HEX_PER_BYTE)
+		return -EINVAL;
+	buf = kmalloc(maskbytes * MAX_HEX_PER_BYTE + sizeof(NUL), GFP_KERNEL);
+	if (!buf)
+		return -ENOMEM;
+	if (copy_from_user(buf, ubuf, ubuflen)) {
+		ret = -EFAULT;
+		goto out;
+	}
+	buf[ubuflen] = NUL;
+
+	/*
+	 * Put the words into wordp[] in big-endian order,
+	 * make sure no bits above nmaskbits set in last word,
+	 * and then go back and reverse the words.
+	 */
+	wordp = (u32 *)maskp;
+	memset(maskp, 0, ROUND_UP(maskbytes, sizeof(*maskp)));
+	i = j = 0;
+	bp = buf;
+	while ((p = strsep(&bp, ",")) != NULL) {
+		unsigned long long t;
+		if (j == maskbytes/sizeof(u32)) {
+			ret = -EINVAL;
+			goto out;
 		}
-		if (i >= nchunks)
-			return -EOVERFLOW;
-		if (i > 0 || chunk) {
-			bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
-			for (j = 0; j < 32; j++) {
-				if (chunk & (1 << j)) {
-					set_bit(j, maskp);
-				}
-			}
-			i++;
-			if (i == 1)
-				firstchunk = chunk;
-			if ( i == nchunks) {
-				if (chunkoff && (firstchunk & chunkmask)) {
-					/* input value > 2^nmaskbits -1 */
-					return -EOVERFLOW;
-				}
-			}
+		t = simple_strtoull(p, 0, BASE);
+		if (t != (u32)t) {
+			ret = -EOVERFLOW;
+			goto out;
 		}
+		wordp[BIT32X(j++)] = t;
 	}
-	if (nt == 0)
-		return -EINVAL;
-	return 0;
+	lwbits = nmaskbits % CHUNKSZ;
+	if (lwbits && (wordp[0] & ~((1<<lwbits) - 1))) {
+		ret = -EOVERFLOW;
+		goto out;
+	}
+	--j;
+	while (i < j) {
+		u32 t = wordp[BIT32X(i)];
+		wordp[BIT32X(i)] = wordp[BIT32X(j)];
+		wordp[BIT32X(j)] = t;
+		i++, --j;
+	}
+	ret = 0;
+ out:
+	kfree(buf);
+	return ret;
 }


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

Re: [PATCH] bitmap parsing routines, version 3

[Paul Jackson]

> +	bitmap_clear(maskp, nmaskbits);

Might be better to clear all the bits in the mask,
not just the low order nmaskbits worth.

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

Re: [PATCH] bitmap parsing routines, version 3

[Joe Korty]

On Sat, Jan 17, 2004 at 09:55:45AM -0500, Joe Korty wrote:
> > > +	bitmap_clear(maskp, nmaskbits);
> > 
> > Might be better to clear all the bits in the mask,
> > not just the low order nmaskbits worth.
> 
> Thanks.  Will do.
> Joe

Hi Paul,
On reflection, I reverse my position -- this should really be done in
bitmap_clear et all as an attribute of bitmaps in general, rather than
as something local to bitmap_parse.

Right now, the bitmap functions treat the unused bits as a kind of
garbage dump.  For example, bitmap_complement() flips every bit in
the set of unsigned longs.  Therefore it is somewhat meaningless for
bitmap_parse, alone among the bitmap functions, to treat the unused bits
as something special.

-- 
Joe
"Money can buy bandwidth, but latency is forever" -- John Mashey

[PATCH] bitmap parsing/printing routines, version 4

[Joe Korty]

This release of the bitmap parser/printer continues the cycle of making
ever-smaller changes to the base code.

The most significant change this time around is to be sure every
character in the string is scanned for correctness.  In the previous
version, the scan would stop on the first whitespace character following
a non-whitespace character.  There was no determination made if that was
the start of either embedded or trailing whitspace -- it was assumed to
be trailing.

I gradually came to feel that examining the whole string was important, as
the parser does not return a pointer to where it stopped as the string(3)
family does, so it is not possible for the caller to easily determine
if the condition stopping the scan was reasonable or not.

ChangeLog:
 o remove trailing whitespace early termination.
 o add leading / embedded / trailing whitespace tests.
 o 'extern' not needed on prototypes (Bill Irwin)
 o made terse variable names readable.
 o continued the reduction of the algorithm to simpler forms.

This release concludes my contributions to this patch, other than changes
driven by user requests and experience.

Against 2.6.1-mm4.

Joe


diff -Nura base/include/linux/bitmap.h new/include/linux/bitmap.h
--- base/include/linux/bitmap.h	2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/bitmap.h	2004-01-17 02:23:57.000000000 -0500
@@ -41,6 +41,10 @@
 void bitmap_or(unsigned long *dst, const unsigned long *bitmap1,
 			const unsigned long *bitmap2, int bits);
 int bitmap_weight(const unsigned long *bitmap, int bits);
+int bitmap_snprintf(char *buf, unsigned int buflen,
+			const unsigned long *maskp, int bits);
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+			unsigned long *maskp, int bits);
 
 #endif /* __ASSEMBLY__ */
 
diff -Nura base/include/linux/cpumask.h new/include/linux/cpumask.h
--- base/include/linux/cpumask.h	2004-01-17 00:10:11.000000000 -0500
+++ new/include/linux/cpumask.h	2004-01-17 00:13:50.000000000 -0500
@@ -2,6 +2,7 @@
 #define __LINUX_CPUMASK_H
 
 #include <linux/threads.h>
+#include <linux/bitmap.h>
 #include <asm/cpumask.h>
 #include <asm/bug.h>
 
@@ -31,16 +32,10 @@
 #define for_each_online_cpu(cpu) for (cpu = 0; cpu < 1; cpu++)
 #endif
 
-extern int __mask_snprintf_len(char *buf, unsigned int buflen,
-		const unsigned long *maskp, unsigned int maskbytes);
-
 #define cpumask_snprintf(buf, buflen, map)				\
-	__mask_snprintf_len(buf, buflen, cpus_addr(map), sizeof(map))
-
-extern int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes);
+	bitmap_snprintf(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #define cpumask_parse(buf, buflen, map)					\
-	__mask_parse_len(buf, buflen, cpus_addr(map), sizeof(map))
+	bitmap_parse(buf, buflen, cpus_addr(map), NR_CPUS)
 
 #endif /* __LINUX_CPUMASK_H */
diff -Nura base/lib/Makefile new/lib/Makefile
--- base/lib/Makefile	2004-01-17 00:10:11.000000000 -0500
+++ new/lib/Makefile	2004-01-17 00:13:50.000000000 -0500
@@ -5,7 +5,7 @@
 
 lib-y := errno.o ctype.o string.o vsprintf.o cmdline.o \
 	 bust_spinlocks.o rbtree.o radix-tree.o dump_stack.o \
-	 kobject.o idr.o div64.o parser.o int_sqrt.o mask.o \
+	 kobject.o idr.o div64.o parser.o int_sqrt.o \
 	 bitmap.o
 
 lib-$(CONFIG_RWSEM_GENERIC_SPINLOCK) += rwsem-spinlock.o
diff -Nura base/lib/bitmap.c new/lib/bitmap.c
--- base/lib/bitmap.c	2004-01-17 00:10:11.000000000 -0500
+++ new/lib/bitmap.c	2004-01-17 12:31:13.000000000 -0500
@@ -1,5 +1,16 @@
-#include <linux/bitmap.h>
+/*
+ * lib/bitmap.c
+ * Helper functions for bitmap.h.
+ *
+ * This source code is licensed under the GNU General Public License,
+ * Version 2.  See the file COPYING for more details.
+ */
 #include <linux/module.h>
+#include <linux/ctype.h>
+#include <linux/errno.h>
+#include <linux/bitmap.h>
+#include <asm/bitops.h>
+#include <asm/uaccess.h>
 
 int bitmap_empty(const unsigned long *bitmap, int bits)
 {
@@ -138,3 +149,114 @@
 #endif
 EXPORT_SYMBOL(bitmap_weight);
 
+/*
+ * Bitmap printing & parsing functions: first version by Bill Irwin,
+ * second version by Paul Jackson, third by Joe Korty.
+ */
+
+#define CHUNKSZ				32
+#define nbits_to_hold_value(val)	fls(val)
+#define roundup_power2(val,modulus)	(((val) + (modulus) - 1) & ~((modulus) - 1))
+#define unhex(c)			(isdigit(c) ? (c - '0') : (toupper(c) - 'A' + 10))
+
+/**
+ * bitmap_snprintf - convert bitmap to an ASCII hex string.
+ * @buf: byte buffer into which string is placed
+ * @buflen: reserved size of @buf, in bytes
+ * @maskp: pointer to bitmap to convert
+ * @nmaskbits: size of bitmap, in bits
+ *
+ * Exactly @nmaskbits bits are displayed.  Hex digits are grouped into
+ * comma-separated sets of eight digits per set.
+ */
+int bitmap_snprintf(char *buf, unsigned int buflen,
+	const unsigned long *maskp, int nmaskbits)
+{
+	int i, word, bit, len = 0; 
+	unsigned long val;
+	const char *sep = "";
+	int chunksz;
+	u32 chunkmask;
+
+	chunksz = nmaskbits & (CHUNKSZ - 1);
+	if (chunksz == 0)
+		chunksz = CHUNKSZ;
+
+	i = roundup_power2(nmaskbits, CHUNKSZ) - CHUNKSZ;
+	for (; i >= 0; i -= CHUNKSZ) {
+		chunkmask = ((1ULL << chunksz) - 1);
+		word = i / BITS_PER_LONG;
+		bit = i % BITS_PER_LONG;
+		val = (maskp[word] >> bit) & chunkmask;
+		len += snprintf(buf+len, buflen-len, "%s%0*lx", sep,
+			(chunksz+3)/4, val);
+		chunksz = CHUNKSZ;
+		sep = ",";
+	}
+	return len;
+}
+EXPORT_SYMBOL(bitmap_snprintf);
+
+/**
+ * bitmap_parse - convert an ASCII hex string into a bitmap.
+ * @buf: pointer to buffer in user space containing string.
+ * @buflen: buffer size in bytes.  If string is smaller than this
+ *    then it must be terminated with a \0.
+ * @maskp: pointer to bitmap array that will contain result.
+ * @nmaskbits: size of bitmap, in bits.
+ *
+ * Commas group hex digits into chunks.  Each chunk defines exactly 32
+ * bits of the resultant bitmask.  No chunk may specify a value larger
+ * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
+ * then leading 0-bits are prepended.  -EINVAL is returned for illegal
+ * characters and for grouping errors such as "1,,5", ,44", "," and "".
+ * Leading and trailing whitespace accepted, but not embedded whitespace.
+ */
+int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
+        unsigned long *maskp, int nmaskbits)
+{
+	int i, c, oc, ndigits, totaldigits, nchunks, nbits;
+	u32 chunk;
+
+	bitmap_clear(maskp, nmaskbits);
+
+	nchunks = nbits = totaldigits = c = 0;
+	do {
+		chunk = ndigits = 0;
+		while (ubuflen) {
+			oc = c;
+			if (get_user(c, ubuf++)) 
+				return -EFAULT;
+			ubuflen--;
+			if (isspace(c))
+				continue;
+			if (totaldigits && c && isspace(oc))
+				return -EINVAL;
+			if (!c || c == ',')
+				break;
+			if (!isxdigit(c))
+				return -EINVAL;
+			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
+				return -EOVERFLOW;
+			chunk = (chunk << 4) | unhex(c);
+			ndigits++; totaldigits++;
+		}
+		if (ndigits == 0)
+			return -EINVAL;
+		if (nchunks == 0 && chunk == 0)
+			continue;
+		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+		for (i = 0; i < CHUNKSZ; i++)
+			if (chunk & (1 << i))
+				set_bit(i, maskp);
+		nchunks++;
+		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
+		if (nbits > nmaskbits)
+			return -EOVERFLOW;
+	} while (ubuflen && c == ',');
+
+	if (totaldigits == 0)
+		return -EINVAL;
+	return 0;
+}
+EXPORT_SYMBOL(bitmap_parse);
diff -Nura base/lib/mask.c new/lib/mask.c
--- base/lib/mask.c	2004-01-09 01:59:34.000000000 -0500
+++ new/lib/mask.c	1969-12-31 19:00:00.000000000 -0500
@@ -1,178 +0,0 @@
-/*
- * lib/mask.c
- *
- * This file is subject to the terms and conditions of the GNU General Public
- * License.  See the file "COPYING" in the main directory of this archive
- * for more details.
- *
- * Copyright (C) 2003 Silicon Graphics, Inc.  All Rights Reserved.
- */
-
-/*
- * Routines to manipulate multi-word bit masks, such as cpumasks.
- *
- * The ascii representation of multi-word bit masks displays each
- * 32bit word in hex (not zero filled), and for masks longer than
- * one word, uses a comma separator between words.  Words are
- * displayed in big-endian order most significant first.  And hex
- * digits within a word are also in big-endian order, of course.
- *
- * Examples:
- *   A mask with just bit 0 set displays as "1".
- *   A mask with just bit 127 set displays as "80000000,0,0,0".
- *   A mask with just bit 64 set displays as "1,0,0".
- *   A mask with bits 0, 1, 2, 4, 8, 16, 32 and 64 set displays
- *     as "1,1,10117".  The first "1" is for bit 64, the second
- *     for bit 32, the third for bit 16, and so forth, to the
- *     "7", which is for bits 2, 1 and 0.
- *   A mask with bits 32 through 39 set displays as "ff,0".
- *
- * The internal binary representation of masks is as one or
- * an array of unsigned longs, perhaps wrapped in a struct for
- * convenient use as an lvalue.  The following code doesn't know
- * about any such struct details, relying on inline macros in
- * files such as cpumask.h to pass in an unsigned long pointer
- * and a length (in bytes), describing the mask contents.
- * The 32bit words in the array are in little-endian order,
- * low order word first.  Beware that this is the reverse order
- * of the ascii representation.
- *
- * Even though the size of the input mask is provided in bytes,
- * the following code may assume that the mask is a multiple of
- * 32 or 64 bit words long, and ignore any fractional portion
- * of a word at the end.  The main reason the size is passed in
- * bytes is because it is so easy to write 'sizeof(somemask_t)'
- * in the macros.
- *
- * Masks are not a single,simple type, like classic 'C'
- * nul-term strings.  Rather they are a family of types, one
- * for each different length.  Inline macros are used to pick
- * up the actual length, where it is known to the compiler, and
- * pass it down to these routines, which work on any specified
- * length array of unsigned longs.  Poor man's templates.
- *
- * Many of the inline macros don't call into the following
- * routines.  Some of them call into other kernel routines,
- * such as memset(), set_bit() or ffs().  Some of them can
- * accomplish their task right inline, such as returning the
- * size or address of the unsigned long array, or optimized
- * versions of the macros for the most common case of an array
- * of a single unsigned long.
- */
-
-#include <linux/kernel.h>
-#include <linux/string.h>
-#include <linux/ctype.h>
-#include <linux/slab.h>
-#include <linux/errno.h>
-#include <linux/gfp.h>
-#include <asm/uaccess.h>
-
-#define MAX_HEX_PER_BYTE 4	/* dont need > 4 hex chars to encode byte */
-#define BASE 16			/* masks are input in hex (base 16) */
-#define NUL ((char)'\0')	/* nul-terminator */
-
-/**
- * __mask_snprintf_len - represent multi-word bit mask as string.
- * @buf: The buffer to place the result into
- * @buflen: The size of the buffer, including the trailing null space
- * @maskp: Points to beginning of multi-word bit mask.
- * @maskbytes: Number of bytes in bit mask at maskp.
- *
- * This routine is expected to be called from a macro such as:
- *
- * #define cpumask_snprintf(buf, buflen, mask) \
- *   __mask_snprintf_len(buf, buflen, cpus_addr(mask), sizeof(mask))
- */
-
-int __mask_snprintf_len(char *buf, unsigned int buflen,
-	const unsigned long *maskp, unsigned int maskbytes)
-{
-	u32 *wordp = (u32 *)maskp;
-	int i = maskbytes/sizeof(u32) - 1;
-	int len = 0;
-	char *sep = "";
-
-	while (i >= 1 && wordp[i] == 0)
-		i--;
-	while (i >= 0) {
-		len += snprintf(buf+len, buflen-len, "%s%x", sep, wordp[i]);
-		sep = ",";
-		i--;
-	}
-	return len;
-}
-
-/**
- * __mask_parse_len - parse user string into maskbytes mask at maskp
- * @ubuf: The user buffer from which to take the string
- * @ubuflen: The size of this buffer, including the terminating char
- * @maskp: Place resulting mask (array of unsigned longs) here
- * @masklen: Construct mask at @maskp to have exactly @masklen bytes
- *
- * @masklen is a multiple of sizeof(unsigned long).  A mask of
- * @masklen bytes is constructed starting at location @maskp.
- * The value of this mask is specified by the user provided
- * string starting at address @ubuf.  Only bytes in the range
- * [@ubuf, @ubuf+@ubuflen) can be read from user space, and
- * reading will stop after the first byte that is not a comma
- * or valid hex digit in the characters [,0-9a-fA-F], or at
- * the point @ubuf+@ubuflen, whichever comes first.
- *
- * Since the user only needs about 2.25 chars per byte to encode
- * a mask (one char per nibble plus one comma separator or nul
- * terminator per byte), we blow them off with -EINVAL if they
- * claim a @ubuflen more than 4 (MAX_HEX_PER_BYTE) times maskbytes.
- * An empty word (delimited by two consecutive commas, for example)
- * is taken as zero.  If @buflen is zero, the entire @maskp is set
- * to zero.
- *
- * If the user provides fewer comma-separated ascii words
- * than there are 32 bit words in maskbytes, we zero fill the
- * remaining high order words.  If they provide more, they fail
- * with -EINVAL.  Each comma-separate ascii word is taken as
- * a hex representation; leading zeros are ignored, and do not
- * imply octal.  '00e1', 'e1', '00E1', 'E1' are all the same.
- * If user passes a word that is larger than fits in a u32,
- * they fail with -EOVERFLOW.
- */
-
-int __mask_parse_len(const char __user *ubuf, unsigned int ubuflen,
-	unsigned long *maskp, unsigned int maskbytes)
-{
-	char buf[maskbytes * MAX_HEX_PER_BYTE + sizeof(NUL)];
-	char *bp = buf;
-	u32 *wordp = (u32 *)maskp;
-	char *p;
-	int i, j;
-
-	if (ubuflen > maskbytes * MAX_HEX_PER_BYTE)
-		return -EINVAL;
-	if (copy_from_user(buf, ubuf, ubuflen))
-		return -EFAULT;
-	buf[ubuflen] = NUL;
-
-	/*
-	 * Put the words into wordp[] in big-endian order,
-	 * then go back and reverse them.
-	 */
-	memset(wordp, 0, maskbytes);
-	i = j = 0;
-	while ((p = strsep(&bp, ",")) != NULL) {
-		unsigned long long t;
-		if (j == maskbytes/sizeof(u32))
-			return -EINVAL;
-		t = simple_strtoull(p, 0, BASE);
-		if (t != (u32)t)
-			return -EOVERFLOW;
-		wordp[j++] = t;
-	}
-	--j;
-	while (i < j) {
-		u32 t = wordp[i];
-		wordp[i] = wordp[j];
-		wordp[j] = t;
-		i++, --j;
-	}
-	return 0;
-}

Re: [PATCH] bitmap parsing routines, version 3

[Paul Jackson]

> On reflection, I reverse my position -- this should really be done in
> bitmap_clear et all as an attribute of bitmaps in general,

You're right.  Good point.

Having the various bitop routines cease treating the unused high bits as
a garbage dump is a separate task.  I don't like the way it is, as it
seems to open the door for some random bugs, in case some hapless code
is depending on these high bits in ways it shouldn't.

This whole mechanism seems to have a design confusion - whether to
specify and honor a specific bit count, or not.

My preference would have been to have these masks be officially some
multiple of "unsigned long" words; but instead we have ended up with a
data type that is ill-defined.  Sometimes it honors bit counts, and
sometimes it doesn't.  Some calls take a bit count (and may or may not
behave predictably in handling the high bits in the last word above the
count); some don't even admit of a bit count argument.  In some ways, it
is supposed to be just a hidden internal implementation detail that
these masks are an array of unsigned longs.  But some ops leave garbage
in the "unused" high bits, and some ops react to these high bits.

As one example, the CPU_MASK_ALL initializer (the cpumask_t type sits on
these masks) sets exactly NR_CPUS bits on small systems, but some
multiple of 8*sizeof(unsigned long) bits on large systems (masks more
than one word).

We're cruising for a bruising; but I lack the clarity of vision and
energy to remedy the situation.

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

Re: [PATCH] bitmap parsing/printing routines, version 4

[Paul Jackson]

Andrew - I encourage you to accept Joe's version 4.

It appears to be a local optimum in the design space.

Good work, Joe.  Thanks.

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

Re: [PATCH] bitmap parsing routines, version 3

[William Lee Irwin III]

On Sat, Jan 17, 2004 at 03:33:44PM -0800, Paul Jackson wrote:
> Having the various bitop routines cease treating the unused high bits as
> a garbage dump is a separate task.  I don't like the way it is, as it
> seems to open the door for some random bugs, in case some hapless code
> is depending on these high bits in ways it shouldn't.
> This whole mechanism seems to have a design confusion - whether to
> specify and honor a specific bit count, or not.

There has never been any confusion. The slop bits are treated
consistently as "don't cares". The functions used to inspect the values,
bitmap_empty(), bitmap_full(), bitmap_equal(), and bitmap_weight(), all
properly check the boundary cases. The remaining functions clobber the
slop bits without hesitation in order to simplify the implementation,
as those bits are never examined by the inspection functions.

If those bits are ever examined and interpreted when they should not be,
I'd be far more interested in hearing about that than about don't cares
being clobbered when they are supposed to be.


-- wli

Re: [PATCH] bitmap parsing routines, version 3

[Paul Jackson]

> There has never been any confusion. The slop bits are treated
> consistently as "don't cares".

Hmmm ... you seem to be quite right about the bitmap stuff.
The cpumask stuff that sits on top of this still worries me.

I need to look more closely.  Sorry, Bill.

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

Re: [PATCH] bitmap parsing/printing routines, version 4

[Matthew Dobson]

[-- Attachment #1: Type: text/plain, Size: 2189 bytes --]

Joe Korty wrote:
> This release of the bitmap parser/printer continues the cycle of making
> ever-smaller changes to the base code.
> 
> The most significant change this time around is to be sure every
> character in the string is scanned for correctness.  In the previous
> version, the scan would stop on the first whitespace character following
> a non-whitespace character.  There was no determination made if that was
> the start of either embedded or trailing whitspace -- it was assumed to
> be trailing.
> 
> I gradually came to feel that examining the whole string was important, as
> the parser does not return a pointer to where it stopped as the string(3)
> family does, so it is not possible for the caller to easily determine
> if the condition stopping the scan was reasonable or not.
> 
> ChangeLog:
>  o remove trailing whitespace early termination.
>  o add leading / embedded / trailing whitespace tests.
>  o 'extern' not needed on prototypes (Bill Irwin)
>  o made terse variable names readable.
>  o continued the reduction of the algorithm to simpler forms.
> 
> This release concludes my contributions to this patch, other than changes
> driven by user requests and experience.
> 
> Against 2.6.1-mm4.
> 
> Joe

Joe,
	I've attatched a small patch with some *small* changes, and the 
addition of a whole lotta comments.  I'd like to see what you think.

Changes:
1) Added a missing '"' in the comment for the bitmap_parse function
2) Renamed 'oc' to 'old_c' for readability
3) Remove "totaldigits == 0" check at the end of bitmap_parse.  I 
believe this check is redundant.  The only way that totaldigits could be 
0 at the end of the function is if ndigits is also 0 (because they're 
both incremented at the same time), and this condition is already 
checked for at the end of each chunk parsed.  Is this correct?

Additions:
4) A whole bunch of comments.  Are these all correct?

None of the things in my patch (with the possible exception of #3) 
change the functionality of the code, which looks great.

Andrew, I agree with Paul's "thumbs-up" of Joe's patch.  My patch is 
solely meant to increase the readability of the bitmap_parse function.

Cheers!

-Matt

[-- Attachment #2: joe_korty-bitmap-fix.patch --]
[-- Type: text/plain, Size: 3040 bytes --]

--- linux-2.6.1-joe_korty-bitmap/lib/bitmap.c.orig	Mon Jan 19 11:45:32 2004
+++ linux-2.6.1-joe_korty-bitmap/lib/bitmap.c	Mon Jan 19 13:11:24 2004
@@ -209,13 +209,13 @@ EXPORT_SYMBOL(bitmap_snprintf);
  * bits of the resultant bitmask.  No chunk may specify a value larger
  * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
  * then leading 0-bits are prepended.  -EINVAL is returned for illegal
- * characters and for grouping errors such as "1,,5", ,44", "," and "".
+ * characters and for grouping errors such as "1,,5", ",44", "," and "".
  * Leading and trailing whitespace accepted, but not embedded whitespace.
  */
 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
         unsigned long *maskp, int nmaskbits)
 {
-	int i, c, oc, ndigits, totaldigits, nchunks, nbits;
+	int i, c, old_c, totaldigits, ndigits, nchunks, nbits;
 	u32 chunk;
 
 	bitmap_clear(maskp, nmaskbits);
@@ -223,40 +223,73 @@ int bitmap_parse(const char __user *ubuf
 	nchunks = nbits = totaldigits = c = 0;
 	do {
 		chunk = ndigits = 0;
+
+		/* Get the next chunk of the bitmap */
 		while (ubuflen) {
-			oc = c;
+			/* Remember the last char & get the next char */
+			old_c = c;
 			if (get_user(c, ubuf++)) 
 				return -EFAULT;
 			ubuflen--;
+
+			/* Ignore spaces */
 			if (isspace(c))
 				continue;
-			if (totaldigits && c && isspace(oc))
+
+			/*
+			 * If the last character was a space and the current 
+			 * character isn't '\0' we've got embedded whitespace. 
+			 * This is a no-no, so throw an error.
+			 */
+			if (totaldigits && c && isspace(old_c))
 				return -EINVAL;
+
+			/* A '\0' or a ',' signal the end of the chunk */
 			if (!c || c == ',')
 				break;
+
+			/* A non-hexdigit is also a no-no, so throw an error */
 			if (!isxdigit(c))
 				return -EINVAL;
+
+			/*
+			 * Make sure there are at least 4 free bits in 'chunk'.
+			 * If not, this hexdigit will overflow 'chunk', so 
+			 * throw an error.
+			 */
 			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
 				return -EOVERFLOW;
+
+			/*
+			 * Add this expanded hexdigit to 'chunk' and increment 
+			 * both the current chunk & total digit counts.
+			 */
 			chunk = (chunk << 4) | unhex(c);
 			ndigits++; totaldigits++;
 		}
+		/* Empty chunks are another no-no.  Throw an error. */
 		if (ndigits == 0)
 			return -EINVAL;
+
+		/* If the first chunk is all 0's, just move to the next one */
 		if (nchunks == 0 && chunk == 0)
 			continue;
+
+		/* Shift the bitmap right to make room for this chunk */
 		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
+
+		/* Copy the chunk into the bitmap, and increment chunk count */
 		for (i = 0; i < CHUNKSZ; i++)
 			if (chunk & (1 << i))
 				set_bit(i, maskp);
 		nchunks++;
+
+		/* Increment the bit count & make sure we didn't overflow */
 		nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ;
 		if (nbits > nmaskbits)
 			return -EOVERFLOW;
 	} while (ubuflen && c == ',');
 
-	if (totaldigits == 0)
-		return -EINVAL;
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_parse);

Re: [PATCH] bitmap parsing/printing routines, version 4

[Paul Jackson]

Matthew rrote:
> 3) Remove "totaldigits == 0" check at the end of bitmap_parse. 

I agree - that check looks redundant to me too.

> addition of a whole lotta comments.

cool.

> Andrew, I agree with Paul's "thumbs-up" of Joe's patch.

Thanks.

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

Re: [PATCH] bitmap parsing/printing routines, version 4

[Joe Korty]

On Mon, Jan 19, 2004 at 01:17:26PM -0800, Matthew Dobson wrote:
> Joe,
> 	I've attatched a small patch with some *small* changes, and the 
> addition of a whole lotta comments.  I'd like to see what you think.
> 
> Changes:
> 1) Added a missing '"' in the comment for the bitmap_parse function
> 2) Renamed 'oc' to 'old_c' for readability
> 3) Remove "totaldigits == 0" check at the end of bitmap_parse.  I 
> believe this check is redundant.  The only way that totaldigits could be 
> 0 at the end of the function is if ndigits is also 0 (because they're 
> both incremented at the same time), and this condition is already 
> checked for at the end of each chunk parsed.  Is this correct?
> 
> Additions:
> 4) A whole bunch of comments.  Are these all correct?
> 
> None of the things in my patch (with the possible exception of #3) 
> change the functionality of the code, which looks great.
> 
> Andrew, I agree with Paul's "thumbs-up" of Joe's patch.  My patch is 
> solely meant to increase the readability of the bitmap_parse function.
> 
> Cheers!
> 
> -Matt

Indeed you are correct, the final (totaldigits == 1) test can be removed.
Good catch.

However, IMHO you added too many comments.  Unlike Andrew, I do believe
one can have too many comments.  Comments become 'too many' when they
dilute to the point that the code can no longer be clearly read.

If you reduce the comments to just those that say something not easily
deduced from the code, then they would be acceptable to me, and would
make a useful addition IMO.  That would be all but three, or perhaps four,
of them.

Andrew, if you do like the fully commented version, then please remove
my name from the comment in the patch.  The dilute style of coding is
not one I wish to have my name associated with.

Thanks,
Joe

Re: [PATCH] bitmap parsing/printing routines, version 4

[Paul Jackson]

> Unlike Andrew, I do believe one can have too many comments. 

How about keeping the comments somewhat separate from the code?

Let the code tell its own story, for those who want to read code.  Let
the comments explain the overall goals and strategy, and perhaps a key
detail or two that might be confusing.

But don't intermingle the two line by line.  They are as two different
languages, that speak to different people, and different parts of the
brain of the bi-lingual.

Make it visually easy for each reader to filter out the 'other stuff.'

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

Re: [PATCH] bitmap parsing/printing routines, version 4

[Randy Dunlap]

> On Mon, Jan 19, 2004 at 01:17:26PM -0800, Matthew Dobson wrote:
>> Joe,
>>
>> Additions:
>> 4) A whole bunch of comments.  Are these all correct?
>>
>> None of the things in my patch (with the possible exception of #3)
>> change the functionality of the code, which looks great.
>>
>> Andrew, I agree with Paul's "thumbs-up" of Joe's patch.  My patch is
>> solely meant to increase the readability of the bitmap_parse function.
>>
>> Cheers!
>>
>> -Matt
>
> Indeed you are correct, the final (totaldigits == 1) test can be
> removed. Good catch.
>
> However, IMHO you added too many comments.  Unlike Andrew, I do believe
> one can have too many comments.  Comments become 'too many' when they
> dilute to the point that the code can no longer be clearly read.

Sure, some code can have too many comments, but most of Linux isn't
approaching that level.

> If you reduce the comments to just those that say something not easily
> deduced from the code, then they would be acceptable to me, and would
> make a useful addition IMO.  That would be all but three, or perhaps
> four, of them.
>
> Andrew, if you do like the fully commented version, then please remove
> my name from the comment in the patch.  The dilute style of coding is
> not one I wish to have my name associated with.

~Randy

Re: [PATCH] bitmap parsing/printing routines, version 4

[Matthew Dobson]

[-- Attachment #1: Type: text/plain, Size: 2451 bytes --]

Joe Korty wrote:
> On Mon, Jan 19, 2004 at 01:17:26PM -0800, Matthew Dobson wrote:
> 
>>Joe,
>>	I've attatched a small patch with some *small* changes, and the 
>>addition of a whole lotta comments.  I'd like to see what you think.
>>
>>Changes:
>>1) Added a missing '"' in the comment for the bitmap_parse function
>>2) Renamed 'oc' to 'old_c' for readability
>>3) Remove "totaldigits == 0" check at the end of bitmap_parse.  I 
>>believe this check is redundant.  The only way that totaldigits could be 
>>0 at the end of the function is if ndigits is also 0 (because they're 
>>both incremented at the same time), and this condition is already 
>>checked for at the end of each chunk parsed.  Is this correct?
>>
>>Additions:
>>4) A whole bunch of comments.  Are these all correct?
>>
>>None of the things in my patch (with the possible exception of #3) 
>>change the functionality of the code, which looks great.
>>
>>Andrew, I agree with Paul's "thumbs-up" of Joe's patch.  My patch is 
>>solely meant to increase the readability of the bitmap_parse function.
>>
>>Cheers!
>>
>>-Matt
> 
> 
> Indeed you are correct, the final (totaldigits == 1) test can be removed.
> Good catch.

Thanks!

> However, IMHO you added too many comments.  Unlike Andrew, I do believe
> one can have too many comments.  Comments become 'too many' when they
> dilute to the point that the code can no longer be clearly read.
> 
> If you reduce the comments to just those that say something not easily
> deduced from the code, then they would be acceptable to me, and would
> make a useful addition IMO.  That would be all but three, or perhaps four,
> of them.
> 
> Andrew, if you do like the fully commented version, then please remove
> my name from the comment in the patch.  The dilute style of coding is
> not one I wish to have my name associated with.
> 
> Thanks,
> Joe

I'm sorry you feel that way, Joe.  I had no intention of "diluting" your 
code, and I certainly don't want you to remove your name from good code 
you spent significant time & effort on.  I'm just about to go to sleep, 
so I made this patch pretty quickly.  I think the 4 comments I kept are 
the most useful and non-obvious.  Let me know if this looks acceptable 
to you.  As I said, I have no desire to have you pull your name from the 
code, especially since I feel it is good code!

Andrew, once Joe and I work out an acceptable patch, we'll make sure you 
get a copy.

Cheers!

-Matt

[-- Attachment #2: joe_korty-bitmap-fix.patch --]
[-- Type: text/plain, Size: 2454 bytes --]

--- linux-2.6.1-joe_korty-bitmap/lib/bitmap.c.orig	Mon Jan 19 11:45:32 2004
+++ linux-2.6.1-joe_korty-bitmap/lib/bitmap.c	Mon Jan 19 22:57:19 2004
@@ -209,13 +209,13 @@ EXPORT_SYMBOL(bitmap_snprintf);
  * bits of the resultant bitmask.  No chunk may specify a value larger
  * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
  * then leading 0-bits are prepended.  -EINVAL is returned for illegal
- * characters and for grouping errors such as "1,,5", ,44", "," and "".
+ * characters and for grouping errors such as "1,,5", ",44", "," and "".
  * Leading and trailing whitespace accepted, but not embedded whitespace.
  */
 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
         unsigned long *maskp, int nmaskbits)
 {
-	int i, c, oc, ndigits, totaldigits, nchunks, nbits;
+	int i, c, old_c, totaldigits, ndigits, nchunks, nbits;
 	u32 chunk;
 
 	bitmap_clear(maskp, nmaskbits);
@@ -223,21 +223,39 @@ int bitmap_parse(const char __user *ubuf
 	nchunks = nbits = totaldigits = c = 0;
 	do {
 		chunk = ndigits = 0;
+
+		/* Get the next chunk of the bitmap */
 		while (ubuflen) {
-			oc = c;
+			old_c = c;
 			if (get_user(c, ubuf++)) 
 				return -EFAULT;
 			ubuflen--;
 			if (isspace(c))
 				continue;
-			if (totaldigits && c && isspace(oc))
+
+			/*
+			 * If the last character was a space and the current 
+			 * character isn't '\0', we've got embedded whitespace.
+			 * This is a no-no, so throw an error.
+			 */
+			if (totaldigits && c && isspace(old_c))
 				return -EINVAL;
-			if (!c || c == ',')
+
+			/* A '\0' or a ',' signal the end of the chunk */
+			if (c == '\0' || c == ',')
 				break;
+
 			if (!isxdigit(c))
 				return -EINVAL;
+
+			/*
+			 * Make sure there are at least 4 free bits in 'chunk'.
+			 * If not, this hexdigit will overflow 'chunk', so 
+			 * throw an error.
+			 */
 			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
 				return -EOVERFLOW;
+
 			chunk = (chunk << 4) | unhex(c);
 			ndigits++; totaldigits++;
 		}
@@ -245,6 +263,7 @@ int bitmap_parse(const char __user *ubuf
 			return -EINVAL;
 		if (nchunks == 0 && chunk == 0)
 			continue;
+
 		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
 		for (i = 0; i < CHUNKSZ; i++)
 			if (chunk & (1 << i))
@@ -255,8 +274,6 @@ int bitmap_parse(const char __user *ubuf
 			return -EOVERFLOW;
 	} while (ubuflen && c == ',');
 
-	if (totaldigits == 0)
-		return -EINVAL;
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_parse);

Re: [PATCH] bitmap parsing/printing routines, version 4

[Joe Korty]

>>However, IMHO you added too many comments.  Unlike Andrew, I do believe
>>one can have too many comments.  Comments become 'too many' when they
>>dilute to the point that the code can no longer be clearly read.
>>
>>If you reduce the comments to just those that say something not easily
>>deduced from the code, then they would be acceptable to me, and would
>>make a useful addition IMO.  That would be all but three, or perhaps four,
>>of them.
>>
>>Andrew, if you do like the fully commented version, then please remove
>>my name from the comment in the patch.  The dilute style of coding is
>>not one I wish to have my name associated with.
>>
>>Thanks,
>>Joe
> 
> I'm sorry you feel that way, Joe.  I had no intention of "diluting" your 
> code, and I certainly don't want you to remove your name from good code 
> you spent significant time & effort on.  I'm just about to go to sleep, 
> so I made this patch pretty quickly.  I think the 4 comments I kept are 
> the most useful and non-obvious.  Let me know if this looks acceptable 
> to you.  As I said, I have no desire to have you pull your name from the 
> code, especially since I feel it is good code!
> 
> Andrew, once Joe and I work out an acceptable patch, we'll make sure you 
> get a copy.

Much better, Matthew.  I can live with this latest patch:)
Thanks,
Joe

Re: [PATCH] bitmap parsing/printing routines, version 4

[Matthew Dobson]

[-- Attachment #1: Type: text/plain, Size: 1537 bytes --]

Joe Korty wrote:
>>>However, IMHO you added too many comments.  Unlike Andrew, I do believe
>>>one can have too many comments.  Comments become 'too many' when they
>>>dilute to the point that the code can no longer be clearly read.
>>>
>>>If you reduce the comments to just those that say something not easily
>>>deduced from the code, then they would be acceptable to me, and would
>>>make a useful addition IMO.  That would be all but three, or perhaps four,
>>>of them.
>>>
>>>Andrew, if you do like the fully commented version, then please remove
>>>my name from the comment in the patch.  The dilute style of coding is
>>>not one I wish to have my name associated with.
>>>
>>>Thanks,
>>>Joe
>>
>>I'm sorry you feel that way, Joe.  I had no intention of "diluting" your 
>>code, and I certainly don't want you to remove your name from good code 
>>you spent significant time & effort on.  I'm just about to go to sleep, 
>>so I made this patch pretty quickly.  I think the 4 comments I kept are 
>>the most useful and non-obvious.  Let me know if this looks acceptable 
>>to you.  As I said, I have no desire to have you pull your name from the 
>>code, especially since I feel it is good code!
>>
>>Andrew, once Joe and I work out an acceptable patch, we'll make sure you 
>>get a copy.
> 
> 
> Much better, Matthew.  I can live with this latest patch:)
> Thanks,
> Joe

Great!  Ok Andrew, I've rediffed this patch against -mm5, and the 
attatched patch should apply cleanly.

Joe & Paul, kudos on the code.  Looks great!

-Matt


[-- Attachment #2: bitmap_readability.patch --]
[-- Type: text/plain, Size: 2556 bytes --]

diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.1-mm5/lib/bitmap.c linux-2.6.1-bitmap_readability/lib/bitmap.c
--- linux-2.6.1-mm5/lib/bitmap.c	Tue Jan 20 08:56:40 2004
+++ linux-2.6.1-bitmap_readability/lib/bitmap.c	Tue Jan 20 09:00:28 2004
@@ -210,13 +210,13 @@ EXPORT_SYMBOL(bitmap_snprintf);
  * bits of the resultant bitmask.  No chunk may specify a value larger
  * than 32 bits (-EOVERFLOW), and if a chunk specifies a smaller value
  * then leading 0-bits are prepended.  -EINVAL is returned for illegal
- * characters and for grouping errors such as "1,,5", ,44", "," and "".
+ * characters and for grouping errors such as "1,,5", ",44", "," and "".
  * Leading and trailing whitespace accepted, but not embedded whitespace.
  */
 int bitmap_parse(const char __user *ubuf, unsigned int ubuflen,
         unsigned long *maskp, int nmaskbits)
 {
-	int i, c, oc, ndigits, totaldigits, nchunks, nbits;
+	int i, c, old_c, totaldigits, ndigits, nchunks, nbits;
 	u32 chunk;
 
 	bitmap_clear(maskp, nmaskbits);
@@ -224,21 +224,39 @@ int bitmap_parse(const char __user *ubuf
 	nchunks = nbits = totaldigits = c = 0;
 	do {
 		chunk = ndigits = 0;
+
+		/* Get the next chunk of the bitmap */
 		while (ubuflen) {
-			oc = c;
+			old_c = c;
 			if (get_user(c, ubuf++))
 				return -EFAULT;
 			ubuflen--;
 			if (isspace(c))
 				continue;
-			if (totaldigits && c && isspace(oc))
+
+			/*
+			 * If the last character was a space and the current 
+			 * character isn't '\0', we've got embedded whitespace.
+			 * This is a no-no, so throw an error.
+			 */
+			if (totaldigits && c && isspace(old_c))
 				return -EINVAL;
-			if (!c || c == ',')
+
+			/* A '\0' or a ',' signal the end of the chunk */
+			if (c == '\0' || c == ',')
 				break;
+
 			if (!isxdigit(c))
 				return -EINVAL;
+
+			/*
+			 * Make sure there are at least 4 free bits in 'chunk'.
+			 * If not, this hexdigit will overflow 'chunk', so 
+			 * throw an error.
+			 */
 			if (chunk & ~((1UL << (CHUNKSZ - 4)) - 1))
 				return -EOVERFLOW;
+
 			chunk = (chunk << 4) | unhex(c);
 			ndigits++; totaldigits++;
 		}
@@ -246,6 +264,7 @@ int bitmap_parse(const char __user *ubuf
 			return -EINVAL;
 		if (nchunks == 0 && chunk == 0)
 			continue;
+
 		bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits);
 		for (i = 0; i < CHUNKSZ; i++)
 			if (chunk & (1 << i))
@@ -256,8 +275,6 @@ int bitmap_parse(const char __user *ubuf
 			return -EOVERFLOW;
 	} while (ubuflen && c == ',');
 
-	if (totaldigits == 0)
-		return -EINVAL;
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_parse);

Re: seperator error in __mask_snprintf_len

[Andi Kleen]

> >  static inline void bitmap_complement(unsigned long *bitmap, int bits)
> >  {
> >         int k;
> > +       int max = BITS_TO_LONGS(bits);
> >  
> > -       for (k = 0; k < BITS_TO_LONGS(bits); ++k)
> > +       for (k = 0; k < max; ++k)
> >                 bitmap[k] = ~bitmap[k];
> 
> OK.  bitmap_and() and bitmap_or() were converted to this form a while back
> because they too were hitting the bug.  On ia32.  It might no longer
> happen now they're uninlined but whatever - you don't have to look
> at the code and think "gee, I hope the compiler moves that arith out
> of the loop".

BTW I think the original point of the inlining was that when you have bits ==
BITS_PER_LONG the function could collapse to a single ~ operation using
the compiler's optimizer. That would be the case with nodemasks on x86-64. 
As for the NUMA API i don't care particularly because there is no bitmap 
manipulation in any fast path. Avoiding miscompilations is definitely 
higher priority. 

-Andi

Re: seperator error in __mask_snprintf_len

[Andrew Morton]

Andi Kleen <ak@muc.de> wrote:
>
> Andrew Morton <akpm@osdl.org> writes:
> 
> > +void bitmap_complement(unsigned long *bitmap, int bits)
> > +{
> > +	int k;
> > +
> > +	for (k = 0; k < BITS_TO_LONGS(bits); ++k)
> > +		bitmap[k] = ~bitmap[k];
> > +}
> > +EXPORT_SYMBOL(bitmap_complement);
> 
> I actually had to change that one in my NUMA API patchkit (which uses
> bitmap functions for its node maps), because gcc 3.2 miscompiled the
> loop.
>
> Please add something like that (looks silly, but makes a big 
> difference):
> 
>  static inline void bitmap_complement(unsigned long *bitmap, int bits)
>  {
>         int k;
> +       int max = BITS_TO_LONGS(bits);
>  
> -       for (k = 0; k < BITS_TO_LONGS(bits); ++k)
> +       for (k = 0; k < max; ++k)
>                 bitmap[k] = ~bitmap[k];

OK.  bitmap_and() and bitmap_or() were converted to this form a while back
because they too were hitting the bug.  On ia32.  It might no longer
happen now they're uninlined but whatever - you don't have to look
at the code and think "gee, I hope the compiler moves that arith out
of the loop".

Re: seperator error in __mask_snprintf_len

[Andi Kleen]

Andrew Morton <akpm@osdl.org> writes:

> +void bitmap_complement(unsigned long *bitmap, int bits)
> +{
> +	int k;
> +
> +	for (k = 0; k < BITS_TO_LONGS(bits); ++k)
> +		bitmap[k] = ~bitmap[k];
> +}
> +EXPORT_SYMBOL(bitmap_complement);

I actually had to change that one in my NUMA API patchkit (which uses
bitmap functions for its node maps), because gcc 3.2 miscompiled the
loop.

Please add something like that (looks silly, but makes a big 
difference):

 static inline void bitmap_complement(unsigned long *bitmap, int bits)
 {
        int k;
+       int max = BITS_TO_LONGS(bits);
 
-       for (k = 0; k < BITS_TO_LONGS(bits); ++k)
+       for (k = 0; k < max; ++k)
                bitmap[k] = ~bitmap[k];

-Andi