seperator error in __mask_snprintf_len

Against 2.6.1-rc1.

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

Andrew asked:

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.

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 <[email protected]> 1.650.933.1373

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...

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

That would be the wrong approach IMHO.

Regards,
Paul.

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

Joe

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.

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

To quote my original patch to Andrew:

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 <[email protected]> 1.650.933.1373

Paul M suggested (in the 32-bit display loop of lib/mask.c):

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:

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 <[email protected]> 1.650.933.1373

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

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 <[email protected]> 1.650.933.1373

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 [email protected] 1.1508
# Swizzle u32 wordp[] indexing to handle 64 bit big-endian arch. # --------------------------------------------
#

diff -Nru a/lib/mask.c b/lib/mask.c
@@ -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 <[email protected]> 1.650.933.1373

Gad.

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.

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
@@ -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/include/linux/bitmap.h.0 2.6/include/linux/bitmap.h
@@ -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 +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 */

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:

Good job of summarizing for the Changelog the changes.

I think I like this - good.

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.

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.

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

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.

And my version doesn't?

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

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

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

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

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

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.

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.

Yes, this would be better.

Oops. Thanks, good catch.

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

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.

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.

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.

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 <[email protected]> 1.650.933.1373

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

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

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

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 <[email protected]> 1.650.933.1373

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

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 <[email protected]> 1.650.933.1373

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

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 <[email protected]> 1.650.933.1373

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

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

Matthew rrote:

I agree - that check looks redundant to me too.

cool.

Thanks.

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

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

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 <[email protected]> 1.650.933.1373

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

~Randy

Thanks!

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

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

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

diff -Nurp --exclude-from=/home/mcd/.dontdiff linux-2.6.1-mm5/lib/bitmap.c linux-2.6.1-bitmap_readability/lib/bitmap.c
@@ -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);

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 <[email protected]> 1.650.933.1373

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 <[email protected]> 1.650.933.1373

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
@@ -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 lib/Makefile~uninline-bitmap-functions lib/Makefile
@@ -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

_

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

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

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 [email protected] 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
@@ -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 <[email protected]> 1.650.933.1373

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?

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 <[email protected]> 1.650.933.1373

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.

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).

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.

Good - I'm on solid ground there ;)

ok

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

Joe, responding to Paul M:

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 <[email protected]> 1.650.933.1373

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 <[email protected]> 1.650.933.1373

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, [email protected]
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."

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

ok.

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

ok.

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

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

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 <[email protected]> 1.650.933.1373

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.

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).

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

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

The final code should reflect the final choices.

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.

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

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

You are correct.

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

Paul M, replying to Paul J:

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 <[email protected]> 1.650.933.1373

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 <[email protected]> 1.650.933.1373

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

Joe noted:

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 <[email protected]> 1.650.933.1373