Skip to contentSkip to conversation

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

PATCH In review Paul Jackson 4 participants 15 messages Mar 29, 2004 – Mar 30, 2004

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

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

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 [email protected] 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'.
# --------------------------------------------
#

include/asm-generic/bitops.h +1 -1
diff -Nru a/include/asm-generic/bitops.h b/include/asm-generic/bitops.h
@@ -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;
 
include/asm-generic/cpumask_array.h +1 -1
diff -Nru a/include/asm-generic/cpumask_array.h b/include/asm-generic/cpumask_array.h
@@ -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)
include/asm-i386/mpspec.h +1 -1
diff -Nru a/include/asm-i386/mpspec.h b/include/asm-i386/mpspec.h
@@ -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)
include/asm-x86_64/mpspec.h +1 -1
diff -Nru a/include/asm-x86_64/mpspec.h b/include/asm-x86_64/mpspec.h
@@ -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)
include/linux/bitmap.h +10 -2
diff -Nru a/include/linux/bitmap.h b/include/linux/bitmap.h
@@ -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,
lib/bitmap.c +61 -6

87 lines not on this page · raw message

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#1 lore raw
Quoted 5 lines · 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.

<snip>

lib/bitmap.c line 51

Quoted 12 lines

diff -Nru a/lib/bitmap.c b/lib/bitmap.c

lib/bitmap.c +1 -1
@@ -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...

lib/bitmap.c line 68

Quoted 12 lines
lib/bitmap.c +4 -3
@@ -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...

lib/bitmap.c line 152

Quoted 4 lines
lib/bitmap.c +4 -0
+int bitmap_intersects(const unsigned long *bitmap1,
+				const unsigned long *bitmap2, int bits)
+{
+	int k, lim = bits/BITS_PER_LONG;;

...a couple times...

lib/bitmap.c line 163

Quoted 11 lines
lib/bitmap.c +11 -0
+	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?

Quoted 5 lines
lib/bitmap.c +5 -0
+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)

lib/bitmap.c line 179

Quoted 10 lines
lib/bitmap.c +10 -0
+		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

#2 lore raw
Quoted 5 lines · Matthew Dobson

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.

Quoted 6 lines · Matthew Dobson

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

#3 lore raw

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.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#4 lore raw
Quoted 8 lines · 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).

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

Quoted 5 lines

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.

#5 lore raw
In reply to Paul Jackson
Quoted 7 lines · 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).

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

include/asm-generic/cpumask_arith.h +11 -5
Index: mm5-2.6.5-rc2/include/asm-generic/cpumask_arith.h
===================================================================
@@ -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); })
 
#6 lore raw
Quoted 1 line

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

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#7 lore raw
Quoted 1 line · At some point in the past, I wrote:
Quoted 1 line

akpm, this is needed for mainline.

Quoted 6 lines · Paul Jackson

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.

Quoted 11 lines · Paul Jackson

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

include/asm-generic/cpumask_arith.h +7 -1
+#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)
Quoted 3 lines

_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

#8 lore raw
Quoted 1 line

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.

Quoted 2 lines

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.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#9 lore raw
Quoted 1 line · At some point in the past, I wrote:
Quoted 1 line

Whether callers experience ill effects is irrelevant.

Quoted 6 lines · Paul Jackson

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.

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

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

Quoted 1 line · Paul Jackson

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

#10 lore raw
In reply to William Lee Irwin III
Quoted 2 lines

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

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#11 lore raw
Quoted 1 line · At some point in the past, I wrote:
Quoted 1 line

No, the existing standard is to treat the unused bits as "don't cares".

Quoted 6 lines · Paul Jackson

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

Quoted 5 lines · Paul Jackson

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

#12 lore raw
In reply to William Lee Irwin III
Quoted 1 line

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.

Quoted 1 line

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.

Signature · 3 lines
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <[email protected]> 1.650.933.1373
#13 lore raw
In reply to William Lee Irwin III
Quoted 8 lines · William Lee Irwin III
Quoted 4 lines · Matthew Dobson

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

#14 lore raw
Quoted 1 line

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.

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