[PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

Patch_1_of_22 - Underlying bitmap/bitop details, added ops
	Add a couple of 'const' qualifiers
	Add intersects, subset, xor and andnot operators.
	Fix some unused bits in bitmap_complement
	Change bitmap_complement to take two operands.

diffstat Patch_1_of_22:
 include/asm-generic/bitops.h        |    2 -
 include/asm-generic/cpumask_array.h |    2 -
 include/asm-i386/mpspec.h           |    2 -
 include/asm-x86_64/mpspec.h         |    2 -
 include/linux/bitmap.h              |   12 +++++-
 lib/bitmap.c                        |   67 ++++++++++++++++++++++++++++++++----
 6 files changed, 75 insertions(+), 12 deletions(-)

# 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.1706  -> 1.1707 
#	include/asm-i386/mpspec.h	1.17    -> 1.18   
#	include/asm-x86_64/mpspec.h	1.8     -> 1.9    
#	include/asm-generic/cpumask_array.h	1.3     -> 1.4    
#	include/asm-generic/bitops.h	1.2     -> 1.3    
#	        lib/bitmap.c	1.6     -> 1.7    
#	include/linux/bitmap.h	1.4     -> 1.5    
#
# The following is the BitKeeper ChangeSet Log
# --------------------------------------------
# 04/03/28	pj@sgi.com	1.1707
# Change bitmap_complement() from inplace to separate dest and source args.
# Add bitmap xor, andnot, intersects and subset operators.
# Mark 2nd bitmap_equal() argument as 'const'
# Refine bitmap_complement to ignore unused bits in last word.
# Mark 2nd test_bit() argument as 'const'.
# --------------------------------------------
#
diff -Nru a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
--- a/include/asm-generic/bitops.h	Mon Mar 29 01:03:26 2004
+++ b/include/asm-generic/bitops.h	Mon Mar 29 01:03:26 2004
@@ -42,7 +42,7 @@
 	return retval;
 }
 
-extern __inline__ int test_bit(int nr, long * addr)
+extern __inline__ int test_bit(int nr, const unsigned long * addr)
 {
 	int	mask;
 
diff -Nru a/include/asm-generic/cpumask_array.h b/include/asm-generic/cpumask_array.h
--- a/include/asm-generic/cpumask_array.h	Mon Mar 29 01:03:26 2004
+++ b/include/asm-generic/cpumask_array.h	Mon Mar 29 01:03:26 2004
@@ -17,7 +17,7 @@
 #define cpus_and(dst,src1,src2)	bitmap_and((dst).mask,(src1).mask, (src2).mask, NR_CPUS)
 #define cpus_or(dst,src1,src2)	bitmap_or((dst).mask, (src1).mask, (src2).mask, NR_CPUS)
 #define cpus_clear(map)		bitmap_clear((map).mask, NR_CPUS)
-#define cpus_complement(map)	bitmap_complement((map).mask, NR_CPUS)
+#define cpus_complement(map)	bitmap_complement((map).mask, (map).mask, NR_CPUS)
 #define cpus_equal(map1, map2)	bitmap_equal((map1).mask, (map2).mask, NR_CPUS)
 #define cpus_empty(map)		bitmap_empty(map.mask, NR_CPUS)
 #define cpus_addr(map)		((map).mask)
diff -Nru a/include/asm-i386/mpspec.h b/include/asm-i386/mpspec.h
--- a/include/asm-i386/mpspec.h	Mon Mar 29 01:03:26 2004
+++ b/include/asm-i386/mpspec.h	Mon Mar 29 01:03:26 2004
@@ -60,7 +60,7 @@
 #define physids_and(dst, src1, src2)		bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
 #define physids_or(dst, src1, src2)		bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
 #define physids_clear(map)			bitmap_clear((map).mask, MAX_APICS)
-#define physids_complement(map)			bitmap_complement((map).mask, MAX_APICS)
+#define physids_complement(map)			bitmap_complement((map).mask, (map).mask, MAX_APICS)
 #define physids_empty(map)			bitmap_empty((map).mask, MAX_APICS)
 #define physids_equal(map1, map2)		bitmap_equal((map1).mask, (map2).mask, MAX_APICS)
 #define physids_weight(map)			bitmap_weight((map).mask, MAX_APICS)
diff -Nru a/include/asm-x86_64/mpspec.h b/include/asm-x86_64/mpspec.h
--- a/include/asm-x86_64/mpspec.h	Mon Mar 29 01:03:26 2004
+++ b/include/asm-x86_64/mpspec.h	Mon Mar 29 01:03:26 2004
@@ -214,7 +214,7 @@
 #define physids_and(dst, src1, src2)		bitmap_and((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
 #define physids_or(dst, src1, src2)		bitmap_or((dst).mask, (src1).mask, (src2).mask, MAX_APICS)
 #define physids_clear(map)			bitmap_clear((map).mask, MAX_APICS)
-#define physids_complement(map)			bitmap_complement((map).mask, MAX_APICS)
+#define physids_complement(map)			bitmap_complement((map).mask, (map).mask, MAX_APICS)
 #define physids_empty(map)			bitmap_empty((map).mask, MAX_APICS)
 #define physids_equal(map1, map2)		bitmap_equal((map1).mask, (map2).mask, MAX_APICS)
 #define physids_weight(map)			bitmap_weight((map).mask, MAX_APICS)
diff -Nru a/include/linux/bitmap.h b/include/linux/bitmap.h
--- a/include/linux/bitmap.h	Mon Mar 29 01:03:26 2004
+++ b/include/linux/bitmap.h	Mon Mar 29 01:03:26 2004
@@ -13,8 +13,8 @@
 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);
+			const unsigned long *bitmap2, int bits);
+void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits);
 
 static inline void bitmap_clear(unsigned long *bitmap, int bits)
 {
@@ -39,6 +39,14 @@
 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);
+void bitmap_xor(unsigned long *dst, const unsigned long *bitmap1,
+			const unsigned long *bitmap2, int bits);
+void bitmap_andnot(unsigned long *dst, const unsigned long *bitmap1,
+			const unsigned long *bitmap2, int bits);
+int bitmap_intersects(const unsigned long *bitmap1,
+			const unsigned long *bitmap2, int bits);
+int bitmap_subset(const unsigned long *bitmap1,
 			const unsigned long *bitmap2, int bits);
 int bitmap_weight(const unsigned long *bitmap, int bits);
 int bitmap_scnprintf(char *buf, unsigned int buflen,
diff -Nru a/lib/bitmap.c b/lib/bitmap.c
--- a/lib/bitmap.c	Mon Mar 29 01:03:26 2004
+++ b/lib/bitmap.c	Mon Mar 29 01:03:26 2004
@@ -45,7 +45,7 @@
 EXPORT_SYMBOL(bitmap_full);
 
 int bitmap_equal(const unsigned long *bitmap1,
-		unsigned long *bitmap2, int bits)
+		const unsigned long *bitmap2, int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;;
 	for (k = 0; k < lim; ++k)
@@ -61,13 +61,14 @@
 }
 EXPORT_SYMBOL(bitmap_equal);
 
-void bitmap_complement(unsigned long *bitmap, int bits)
+void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
 {
-	int k;
-	int nr = BITS_TO_LONGS(bits);
+	int k, lim = bits/BITS_PER_LONG;;
+	for (k = 0; k < lim; ++k)
+		dst[k] = ~src[k];
 
-	for (k = 0; k < nr; ++k)
-		bitmap[k] = ~bitmap[k];
+	if (bits % BITS_PER_LONG)
+		dst[k] = ~src[k] & ((1UL << (bits % BITS_PER_LONG)) - 1);
 }
 EXPORT_SYMBOL(bitmap_complement);
 
@@ -122,6 +123,60 @@
 		dst[k] = bitmap1[k] | bitmap2[k];
 }
 EXPORT_SYMBOL(bitmap_or);
+
+void bitmap_xor(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_xor);
+
+void bitmap_andnot(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_andnot);
+
+int bitmap_intersects(const unsigned long *bitmap1,
+				const unsigned long *bitmap2, int bits)
+{
+	int k, lim = bits/BITS_PER_LONG;;
+	for (k = 0; k < lim; ++k)
+		if (bitmap1[k] & bitmap2[k])
+			return 1;
+
+	if (bits % BITS_PER_LONG)
+		if ((bitmap1[k] & bitmap2[k]) &
+				((1UL << (bits % BITS_PER_LONG)) - 1))
+			return 1;
+	return 0;
+}
+EXPORT_SYMBOL(bitmap_intersects);
+
+int bitmap_subset(const unsigned long *bitmap1,
+				const 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_subset);
 
 #if BITS_PER_LONG == 32
 int bitmap_weight(const unsigned long *bitmap, int bits)


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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Matthew Dobson]

On Mon, 2004-03-29 at 04:12, Paul Jackson wrote:
> Patch_1_of_22 - Underlying bitmap/bitop details, added ops
> 	Add a couple of 'const' qualifiers
> 	Add intersects, subset, xor and andnot operators.
> 	Fix some unused bits in bitmap_complement
> 	Change bitmap_complement to take two operands.

<snip>

> diff -Nru a/lib/bitmap.c b/lib/bitmap.c
> --- a/lib/bitmap.c	Mon Mar 29 01:03:26 2004
> +++ b/lib/bitmap.c	Mon Mar 29 01:03:26 2004
> @@ -45,7 +45,7 @@
>  EXPORT_SYMBOL(bitmap_full);
>  
>  int bitmap_equal(const unsigned long *bitmap1,
> -		unsigned long *bitmap2, int bits)
> +		const unsigned long *bitmap2, int bits)
>  {
>  	int k, lim = bits/BITS_PER_LONG;;
>  	for (k = 0; k < lim; ++k)

Double `;`?  You didn't put it there, but it seems that...

> @@ -61,13 +61,14 @@
>  }
>  EXPORT_SYMBOL(bitmap_equal);
>  
> -void bitmap_complement(unsigned long *bitmap, int bits)
> +void bitmap_complement(unsigned long *dst, const unsigned long *src, int bits)
>  {
> -	int k;
> -	int nr = BITS_TO_LONGS(bits);
> +	int k, lim = bits/BITS_PER_LONG;;
> +	for (k = 0; k < lim; ++k)
> +		dst[k] = ~src[k];

...you propagated the error...

 
> +int bitmap_intersects(const unsigned long *bitmap1,
> +				const unsigned long *bitmap2, int bits)
> +{
> +	int k, lim = bits/BITS_PER_LONG;;

...a couple times...

> +	for (k = 0; k < lim; ++k)
> +		if (bitmap1[k] & bitmap2[k])
> +			return 1;
> +
> +	if (bits % BITS_PER_LONG)
> +		if ((bitmap1[k] & bitmap2[k]) &
> +				((1UL << (bits % BITS_PER_LONG)) - 1))
> +			return 1;
> +	return 0;
> +}
> +EXPORT_SYMBOL(bitmap_intersects);

Do we need to check the last word specially?  If we're assuming that the
unused bits are 0's, then they can't affect the check, right?  If we're
not assuming the unused bits are 0's, then we need to do this last word
special casing in bitmap_xor & bitmap_andnot, because they could set the
unused bits.  Or am I confused?

> +int bitmap_subset(const unsigned long *bitmap1,
> +				const 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_subset);

Same comments here, both the double ';' and the last word special
casing...

Looking ahead, patch 2/22 specifically states that we assume all our
input masks have the high/unused bits cleared and we promise not to set
them.  So we shouldn't need the last word special casing in
bitmap_intersect & bitmap_subset...  I think. ;)

-Matt

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[William Lee Irwin III]

On Mon, Mar 29, 2004 at 03:06:16PM -0800, Matthew Dobson wrote:
> Do we need to check the last word specially?  If we're assuming that the
> unused bits are 0's, then they can't affect the check, right?  If we're
> not assuming the unused bits are 0's, then we need to do this last word
> special casing in bitmap_xor & bitmap_andnot, because they could set the
> unused bits.  Or am I confused?

No, not those two. xor of 0's is 0 again. and of 0 and anything is 0 again.
xornot and ornot would need those checks if implemented.


On Mon, Mar 29, 2004 at 03:06:16PM -0800, Matthew Dobson wrote:
> Same comments here, both the double ';' and the last word special
> casing...
> Looking ahead, patch 2/22 specifically states that we assume all our
> input masks have the high/unused bits cleared and we promise not to set
> them.  So we shouldn't need the last word special casing in
> bitmap_intersect & bitmap_subset...  I think. ;)

It looks like Paul wants those invariants. Which is fine; I can do things
on behalf of users, or stand back and let them do things themselves.

You're right that intersection (and) and subset (andnot) shouldn't require
any special cases for the final word.


-- wli

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

My thinking on when to worry about the unused bits, and when not to, is
thus.

For the lib/bitmap.c code, it seems that the existing standard, followed
by everything except bitmap_complement(), is to not set any unused bits
(at least when called with correct arguments in range), but to always
filter them out when testing for some Boolean condition or scalar result
(weight).

So I fixed bitmap_complement() to also not set them, and I put checks in
my new Booleans bitmap_subset() and bitmap_intersects(), to filter them
out.

But I didn't worry about them in bitmap_xor() or bitmap_andnot(), just
like the similar bitmap_or() and bitmap_and() don't worry about them
(proper calls of or/and/xor/andnot will not set the unused bits anyway.)

The standard I set for the include/linux/mask.h code is different than
for lib/bitmap.c.  In the mask.h code, I won't set them if all your
calls are proper and in range (same as bitmap), but I also make no
effort to filter them out on Boolean or scalar ops (though if some
bitmap op I happen to call does filter such, I don't worry about it).

So with the bitmap API, you can get unused bits set, and not notice it
in most cases, due to the filtering.  But with the mask API, you'd best
not screw up and set them, or else you might get different Boolean and
scalar results, depending on implementation details.

My biggest defense against coding bugs in kernel code using these masks
is to get the cpumask and nodemask API easier to understand and use.
This should reduce bugs do to coder confusion.  So long as they call
this stuff with proper arguments, all is well.

The bitmap stuff probably does more checking than I would like, but I
felt it was more important to be consistent there, as bitmaps are an
exposed API in their own right.  Either add unused bit zeroing and
filtering in the remaining places (complement and the new subset and
intersects), or rip it all out.

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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Matthew Dobson]

On Mon, 2004-03-29 at 15:43, Paul Jackson wrote:
> My thinking on when to worry about the unused bits, and when not to, is
> thus.
> 
> For the lib/bitmap.c code, it seems that the existing standard, followed
> by everything except bitmap_complement(), is to not set any unused bits
> (at least when called with correct arguments in range), but to always
> filter them out when testing for some Boolean condition or scalar result
> (weight).

Ok...  I see why you are masking off those bits now.  Thanks for the
explanation.


> The bitmap stuff probably does more checking than I would like, but I
> felt it was more important to be consistent there, as bitmaps are an
> exposed API in their own right.  Either add unused bit zeroing and
> filtering in the remaining places (complement and the new subset and
> intersects), or rip it all out.

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[William Lee Irwin III]

On Mon, Mar 29, 2004 at 03:43:30PM -0800, Paul Jackson wrote:
> My thinking on when to worry about the unused bits, and when not to, is
> thus.
> For the lib/bitmap.c code, it seems that the existing standard, followed
> by everything except bitmap_complement(), is to not set any unused bits
> (at least when called with correct arguments in range), but to always
> filter them out when testing for some Boolean condition or scalar result
> (weight).

No, the existing standard is to treat the unused bits as "don't cares".
The difference codewise between the two choices is rather small anyway,
but if you want to _change_ the invariant to be something else, e.g.
insist that they always be zeroes, announce this up-front and make the
change independently of API. The "bugs" you're speaking of are nowhere
near the vicinity of bitmap_complement(). They exist only in the
arithmetic implementation and are fixed in a minimal impact way in the
following patch, which maintains current invariants.

The impact of changing this invariant is likely more relevant to
sensitivity to garbage leaking in through initializations of dynamically
allocated cpumasks than the implementations of the runtime operations.

In any event, best to fix the bug in the current code now and let the
cleanups go in after. akpm, this is needed for mainline.


-- wli


Index: mm5-2.6.5-rc2/include/asm-generic/cpumask_arith.h
===================================================================
--- mm5-2.6.5-rc2.orig/include/asm-generic/cpumask_arith.h	2004-03-19 16:11:33.000000000 -0800
+++ mm5-2.6.5-rc2/include/asm-generic/cpumask_arith.h	2004-03-29 17:58:25.000000000 -0800
@@ -6,6 +6,12 @@
  * to contain the whole cpu bitmap.
  */
 
+#if NR_CPUS % BITS_PER_LONG
+#define __CPU_VALID_MASK__		(~((1UL<< (NR_CPUS%BITS_PER_LONG) - 1))
+#else
+#define __CPU_VALID_MASK__		(~0UL)
+#endif
+
 #define cpu_set(cpu, map)		set_bit(cpu, &(map))
 #define cpu_clear(cpu, map)		clear_bit(cpu, &(map))
 #define cpu_isset(cpu, map)		test_bit(cpu, &(map))
@@ -15,14 +21,14 @@
 #define cpus_or(dst,src1,src2)		do { dst = (src1) | (src2); } while (0)
 #define cpus_clear(map)			do { map = 0; } while (0)
 #define cpus_complement(map)		do { map = ~(map); } while (0)
-#define cpus_equal(map1, map2)		((map1) == (map2))
-#define cpus_empty(map)			((map) == 0)
+#define cpus_equal(x, y)		(!(((x) ^ (y)) & __CPU_VALID_MASK__))
+#define cpus_empty(map)			(!((map) & __CPU_VALID_MASK__))
 #define cpus_addr(map)			(&(map))
 
 #if BITS_PER_LONG == 32
-#define cpus_weight(map)		hweight32(map)
+#define cpus_weight(map)		hweight32((map) & __CPU_VALID_MASK__)
 #elif BITS_PER_LONG == 64
-#define cpus_weight(map)		hweight64(map)
+#define cpus_weight(map)		hweight64((map) & __CPU_VALID_MASK__)
 #endif
 
 #define cpus_shift_right(dst, src, n)	do { dst = (src) >> (n); } while (0)
@@ -39,7 +45,7 @@
 #define CPU_MASK_NONE	((cpumask_t)0)
 
 /* only ever use this for things that are _never_ used on large boxen */
-#define cpus_coerce(map)		((unsigned long)(map))
+#define cpus_coerce(map)		((map) & __CPU_VALID_MASK__)
 #define cpus_promote(map)		({ map; })
 #define cpumask_of_cpu(cpu)		({ ((cpumask_t)1) << (cpu); })
 

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

> akpm, this is needed for mainline.

How urgent to you consider this fix (masking unused bits in the
arithmetic (single unsigned long word) cpumask implementation?

So far as I know, the only way to get high bits set with correct
invocations is by using cpus_complement(), which I don't see anyone
doing.

So I believe that this patch fixes latent bugs, not current bugs.

And it would be my preference (not surprisingly) to fix this in a way
that is consistent with my mask ADT proposal (avoid setting unused bits
on proper calls; don't filter on Boolean/scalar predicate evaluations):

+#if NR_CPUS % BITS_PER_LONG
+#define __CPU_VALID_MASK__		(~((1UL<< (NR_CPUS%BITS_PER_LONG) - 1))
+#else
+#define __CPU_VALID_MASK__		(~0UL)
+#endif

-#define cpus_complement(map)		do { map = ~(map); } while (0)
+#define cpus_complement(map)		\
+	do { map = ~(map) & __CPU_VALID_MASK__; } while (0)

_instead_ of changing the several other macros to follow the
bitmap convention (let the unused bits remain dont-care, until
resolving a Boolean or scalar predicate).

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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[William Lee Irwin III]

At some point in the past, I wrote:
>> akpm, this is needed for mainline.

On Mon, Mar 29, 2004 at 05:46:37PM -0800, Paul Jackson wrote:
> How urgent to you consider this fix (masking unused bits in the
> arithmetic (single unsigned long word) cpumask implementation?
> So far as I know, the only way to get high bits set with correct
> invocations is by using cpus_complement(), which I don't see anyone
> doing.
> So I believe that this patch fixes latent bugs, not current bugs.

False. The semantics are currently "don't care" and the ADT fails to
ignore the upper bits in cpumask_arith.h. It's a bug in the ADT code.
Whether callers experience ill effects is irrelevant.


On Mon, Mar 29, 2004 at 05:46:37PM -0800, Paul Jackson wrote:
> And it would be my preference (not surprisingly) to fix this in a way
> that is consistent with my mask ADT proposal (avoid setting unused bits
> on proper calls; don't filter on Boolean/scalar predicate evaluations):
> +#if NR_CPUS % BITS_PER_LONG
> +#define __CPU_VALID_MASK__		(~((1UL<< (NR_CPUS%BITS_PER_LONG) - 1))
> +#else
> +#define __CPU_VALID_MASK__		(~0UL)
> +#endif
> -#define cpus_complement(map)		do { map = ~(map); } while (0)
> +#define cpus_complement(map)		\
> +	do { map = ~(map) & __CPU_VALID_MASK__; } while (0)
> _instead_ of changing the several other macros to follow the
> bitmap convention (let the unused bits remain dont-care, until
> resolving a Boolean or scalar predicate).

You're missing the changes needed for cpus_shift_left() and
cpus_promote() to satisfy zeroed tail postconditions. IIRC the needed
changes to cpus_shift_left() are also missing from your other patches
in the bitmap code. You are also changing the invariants, which should
be the substance of a patch different from any bugfix.


-- wli

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

> Whether callers experience ill effects is irrelevant.

Not irrelevant to the callers ;)

And Andrew might reasonably choose to prioritize fixes,
depending in part on the impact of what they fix.

Ah - there is one more use of *_complement, in i386/mach-es7000.
But it masks the result in the next line with cpu_online_map, so
also avoids propogating the damage.


> IIRC the needed changes to cpus_shift_left() are also missing from
> your other patches in the bitmap code.

Hmmm ... could you elaborate on this?  I don't see this bug.

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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[William Lee Irwin III]

At some point in the past, I wrote:
>> Whether callers experience ill effects is irrelevant.

On Mon, Mar 29, 2004 at 09:09:17PM -0800, Paul Jackson wrote:
> Not irrelevant to the callers ;)
> And Andrew might reasonably choose to prioritize fixes,
> depending in part on the impact of what they fix.
> Ah - there is one more use of *_complement, in i386/mach-es7000.
> But it masks the result in the next line with cpu_online_map, so
> also avoids propogating the damage.

This is also irrelevant. By this token, races in rarely/never-called
codepaths would not be bugs.

The cleanups are fine as cleanups. Just get arch maintainer approvals
because you _are_ relying on operational semantics specific to gcc
versions, which may not support various architectures. Do not attempt
to confuse the issue with bugfixing. Lobbying me is pointless; go to
arch maintainers.


At some point in the past, I wrote:
>> IIRC the needed changes to cpus_shift_left() are also missing from
>> your other patches in the bitmap code.

On Mon, Mar 29, 2004 at 09:09:17PM -0800, Paul Jackson wrote:
> Hmmm ... could you elaborate on this?  I don't see this bug.

I recalled a more intelligent implementation scrapped for the sake of
simplicity/merging. The version in mainline doesn't have the issue,
though it does have limitations on bitmap sizes, which I'll remove
shortly while also preserving their current satisfaction of zeroed tail
postconditions given zeroed tail preconditions. This should have no
effect and/or conflict with your changes, but rather merely restore the
arbitrary bitmap size capabilities and look vaguely more efficient.


-- wli

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

> No, the existing standard is to treat the unused bits as "don't cares".
> The difference codewise between the two choices is rather small anyway,

As you have documented in your requested patch to Andrew, the actual
code in 2.6.4 deviated from your intended bitmap model by the details
of cpus_equal(), cpus_empty() and cpus_weight() routines in
cpumask_arith.h.

And 2.6.4 deviates from my bitmap model by a couple of *_complement
implementations and the multi-word CPU_MASK_ALL initializor.

By my model, the CPU_MASK_ALL code for large (multi word mask) systems
is missing the zero'ing of unused bits, in the (rare) case that the
number of valid bits in the mask was not an exact word multiple. And the
*_complement implementations routinely returned masks with the unused
bits set, given input with them not set.

Looking ahead to your next post - I suspect that my model is not the
zeroed tail invariant you describe.  My bitmap model makes no promise to
zero out all input tails.

Rather my bitmap model adds the further implementation condition:

  If input tails are zero, then output tails will be zero.

By your model, the CPU_MASK_ALL code for small (one word mask) systems
has some redundant code, to zero the unused bits.  This CPU_MASK_ALL
could simply be "~0UL", not the more elaborate "(~((cpumask_t)0) >>
(8*sizeof(cpumask_t) - NR_CPUS))".

On further examination, I believe that your model better describes
what has been the design intent for bitmaps.

However my model conforms to yours.  Any correct bitmap implementation
of my model is a correct implementation of yours.  My model simply
adds the above condition on the implementation.

My change to zero out unused bits in the *_complement operators does not
violate your model.   Nor does my change to zero out the unused bits in
the multi-word CPU_MASK_ALL initializor violate your model.  You have
repeatedly emphasized that you don't care about the setting of these
bits.  Surely you don't care if they are zero, just as you don't care
that the one word CPU_MASK_ALL initialization zeros the unused bits.

==> Note of course that the above model(s) are efforts to describe
    the bitmap/bitop code.  The model I provide for my new mask ADT is
    different - it makes use of the implementation condition above on
    bitmaps "Zero tails in yield zero tails out", along with an added
    precondition "Don't pass in masks with nonzero tails" to avoid
    needing much filtering code.

So - would you consent to my bundling the following changes as a single
patch - that adds to bitmaps the property that "output tails will be
zero if input tails are zero"?

  1) Zero unused bits in the *_complement operators.
  2) Zero unused bits in CPU_MASK_ALL (multiword).

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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[William Lee Irwin III]

At some point in the past, I wrote:
>> No, the existing standard is to treat the unused bits as "don't cares".

At some point in the past, Paul Jackson wrote:
> ==> Note of course that the above model(s) are efforts to describe
>     the bitmap/bitop code.  The model I provide for my new mask ADT is
>     different - it makes use of the implementation condition above on
>     bitmaps "Zero tails in yield zero tails out", along with an added
>     precondition "Don't pass in masks with nonzero tails" to avoid
>     needing much filtering code.

I think the difference is maybe one or two lines, but it doesn't matter
much. If zeroed tails are what you want, by all means, have them. But
please keep it to one change at a time(e.g. do the standardized
array-in-struct datatype in a different patch). Also, please document
the change of invariants. I didn't realize it would become a point of
confusion and we should avoid repeating this kind of affair.

I think I failed to convey the entire zeroed tail invariant I described.
What I wanted to convey did include the precondition of zeroed tails
for validity and/or satisfying zeroed tail postconditions. I think I
even meant to go as far as saying not having zeroed tails meant undefined
behavior, where I suspect you want general validity and zeroed tails
preserved when present (and actually it would take some effort to barf
on nonzeroed tails for most of the operations).


At some point in the past, Paul Jackson wrote:
> So - would you consent to my bundling the following changes as a single
> patch - that adds to bitmaps the property that "output tails will be
> zero if input tails are zero"?
>   1) Zero unused bits in the *_complement operators.
>   2) Zero unused bits in CPU_MASK_ALL (multiword).

I think the change is small enough and transparent enough in general you
could do the entire invariant conversion for arith and bitmaps as one
patch. But please document it (possibly with kerneldoc) somewhere
nearby to where the API's are implemented. I think a couple of lines of
comments at the top of lib/bitmap.c should be enough if the bitmap
functions don't rely on zeroed tails for correctness. If some do rely
on zeroed tails for correctness, that should be in kerneldoc comments
(e.g. if bitmap_shift_right() needs zeroed tails not to shift in garbage
from upper bits, that's a gotcha that needs to be documented).

Part of what led to this confusion in the first place was the assumption
(likely on my part) that the "don't care" invariant was the most natural
and not documenting it. Zeroed tails are a stronger condition in general
and likely make some small optimizations possible if the bitmap functions
are allowed to produce undefined results for nonzeroed tails (which is an
okay thing to do, just needs to be a separate change for bisection/testing
etc. purposes if by some catastrophe something does break).


-- wli

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

> No, not those two. xor of 0's is 0 again. and of 0 and anything is 0 again.

I agree with Bill on this.


> It looks like Paul wants those invariants.

No - bitmap wants these invariants, and I wanted bitmap to be
consistent.  It's an exposed API in its own right.  Since it mostly
already had filtering of unused bits on Boolean/scalar ops, and
avoidance of setting unused bits on proper calls, I completed that
model.

For masks, I promise not to set them if you don't screw up, but I don't
add any code to protect against such, and I don't hestitate to presume
the unused bits are always zero whenever it is convenient to do so.

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

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Chris Friesen]

William Lee Irwin III wrote:
> On Mon, Mar 29, 2004 at 03:06:16PM -0800, Matthew Dobson wrote:
>>If we're
>>not assuming the unused bits are 0's, then we need to do this last word
>>special casing in bitmap_xor & bitmap_andnot, because they could set the
>>unused bits.  Or am I confused?
> 
> 
> No, not those two. xor of 0's is 0 again. and of 0 and anything is 0 again.

Huh?  Xor of 0 and 1 is 1.

Chris

Re: [PATCH] mask ADT: bitmap and bitop tweaks [1/22]

[Paul Jackson]

> Huh?  Xor of 0 and 1 is 1.

Heh - no fair introducing facts into this discussion ;).

Actually, you're right.  Though this is a 'latent' bug in
this particular discussion - it doesn't impact any subsequent
points that Bill or I was making.

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