remove bitmap_shift_*() bitmap length limits

remove bitmap_shift_*() bitmap length limits

[William Lee Irwin III]

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

Included as MIME attachments are the userspace test harness I used for
the changes and a patch changing bitmap_shift_left()/bitmap_shift_right()
to have O(1) stackspace requirements. This test harness passed ca. 60
minutes of testing with random inputs before I posted with zero
mismatching output vs. the current implementations.

Given zeroed tail preconditions these implementations satisfy zeroed
tail postconditions, which makes them compatible with whatever changes
from Paul Jackson one may want to merge in the future. No particular
effort was required to ensure this.

A small (but hopefully forgiveable) cleanup is a spelling correction:
s/bitmap_shift_write/bitmap_shift_right/ in one of the kerneldoc comments.

The primary effect of the patch is to remove the MAX_BITMAP_BITS
limitation, so restoring the NR_CPUS to be limited only by stackspace
and slab allocator maximums. They also look vaguely more efficient than
the current code, though as this was not done for performance reasons,
no performance testing was done.

vs. 2.6.5-rc2-mm5

-- wli

[-- Attachment #2: bitmap_test.c --]
[-- Type: text/x-csrc, Size: 8164 bytes --]

#include <limits.h>
#include <stdio.h>
#include <assert.h>
#include <sys/time.h>
#include <time.h>

struct ref {
	void *p;
};

#define EXPORT_SYMBOL(x)	static struct ref __ref__##x = { .p = (x) }
#define BITS_TO_LONGS(bits) \
        (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG)
#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]
#define CLEAR_BITMAP(name,bits) \
        memset(name, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long))
#define TYPEBITS(t)	(CHAR_BIT*sizeof(t))
#define BITS_PER_LONG	TYPEBITS(unsigned long)

#define MAX_BITMAP_BITS	512

#define BUG_ON(p)	assert(!(p))

static inline void bitmap_clear(unsigned long *bitmap, int bits)
{
        CLEAR_BITMAP((unsigned long *)bitmap, bits);
}

static inline void bitmap_fill(unsigned long *bitmap, int bits)
{
        memset(bitmap, 0xff, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline void bitmap_copy(unsigned long *dst,
                        const unsigned long *src, int bits)
{
        memcpy(dst, src, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline int set_bit(int nr, unsigned long *addr)
{
	int	mask, retval;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	retval = (mask & *addr) != 0;
	*addr |= mask;
	return retval;
}

static inline int clear_bit(int nr, unsigned long *addr)
{
	int	mask, retval;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	retval = (mask & *addr) != 0;
	*addr &= ~mask;
	return retval;
}

static inline int test_bit(int nr, const unsigned long *addr)
{
	int	mask;

	addr += nr >> 5;
	mask = 1 << (nr & 0x1f);
	return ((mask & *addr) != 0);
}

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;
	int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; ++k)
		bitmap[k] = ~bitmap[k];
}
EXPORT_SYMBOL(bitmap_complement);

/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	unsigned long mask = (1UL << rem) - 1;
	for (k = 0; off + k < lim; ++k) {
		unsigned long upper;

		/*
		 * If shift is not word aligned, take lower rem bits of
		 * word above and make them the top rem bits of result.
		 */
		if (rem && off + k + 1 < lim)
			upper = src[off + k + 1] & mask;
		else
			upper = 0;
		dst[k] = upper << (BITS_PER_LONG - rem) | src[off + k] >> rem;
	}
	if (off)
		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
}
EXPORT_SYMBOL(bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	for (k = lim - off - 1; k >= 0; --k) {
		unsigned long lower;

		/*
		 * If shift is not word aligned, take upper rem bits of
		 * word below and make them the bottom rem bits of result.
		 */
		if (rem && k > 0)
			lower = src[k - 1] >> (BITS_PER_LONG - rem);
		else
			lower = 0;
		dst[k + off] = lower | src[k] << rem;
	}
	if (off)
		memset(dst, 0, off*sizeof(unsigned long));
}
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);


/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void old_bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_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(old_bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void old_bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_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(old_bitmap_shift_left);

int main(void)
{
	int n;
	struct timeval tv;
	unsigned short seed[3];
	unsigned long bitmap1[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap2[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap3[BITS_TO_LONGS(MAX_BITMAP_BITS)];

	gettimeofday(&tv, NULL);
	seed[0] = (unsigned short)tv.tv_usec;
	seed[1] = (unsigned short)getpid();
	seed[2] = (unsigned short)0;

	while (1) {
		int k, shift;
		++n;
		for (k = 0; k < BITS_TO_LONGS(MAX_BITMAP_BITS); ++k)
			bitmap1[k] = (unsigned long)nrand48(seed);
		shift = (unsigned long)nrand48(seed) & (MAX_BITMAP_BITS - 1);
		/* shift = (shift + 31) & ~0x31UL; */
		memcpy(bitmap2, bitmap1, sizeof(bitmap1));
		memcpy(bitmap3, bitmap1, sizeof(bitmap1));
		if (n & 1) {
			old_bitmap_shift_left(bitmap1, bitmap1, shift, MAX_BITMAP_BITS);
			bitmap_shift_left(bitmap2, bitmap2, shift, MAX_BITMAP_BITS);
		} else {
			old_bitmap_shift_right(bitmap1, bitmap1, shift, MAX_BITMAP_BITS);
			bitmap_shift_right(bitmap2, bitmap2, shift, MAX_BITMAP_BITS);
		}
		if (memcmp(bitmap1, bitmap2, sizeof(bitmap1))) {
			printf("problem %s/%d!!!\n", (n&1) ? "left" : "right", shift);
			for (k = 0; k < BITS_TO_LONGS(MAX_BITMAP_BITS); ++k) {
				printf("orig/old/new = 0x%0*lx/0x%0*lx/0x%0*lx\n",
					2*sizeof(bitmap3[k]), bitmap3[k],
					2*sizeof(bitmap1[k]), bitmap1[k],
					2*sizeof(bitmap2[k]), bitmap2[k]);
			}
			exit(1);
		}
	}
	return 0;
}

[-- Attachment #3: bitmap_shift_stack.patch --]
[-- Type: text/plain, Size: 2656 bytes --]

Index: mm5-2.6.5-rc2/lib/bitmap.c
===================================================================
--- mm5-2.6.5-rc2.orig/lib/bitmap.c	2004-03-29 17:44:14.000000000 -0800
+++ mm5-2.6.5-rc2/lib/bitmap.c	2004-03-29 22:19:42.000000000 -0800
@@ -12,8 +12,6 @@
 #include <asm/bitops.h>
 #include <asm/uaccess.h>
 
-#define MAX_BITMAP_BITS	512U	/* for ia64 NR_CPUS maximum */
-
 int bitmap_empty(const unsigned long *bitmap, int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
@@ -72,7 +70,7 @@
 EXPORT_SYMBOL(bitmap_complement);
 
 /*
- * bitmap_shift_write - logical right shift of the bits in a bitmap
+ * bitmap_shift_right - logical right shift of the bits in a bitmap
  *   @dst - destination bitmap
  *   @src - source bitmap
  *   @nbits - shift by this many bits
@@ -85,15 +83,24 @@
 void bitmap_shift_right(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
-	int k;
-	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);
-
-	BUG_ON(bits > MAX_BITMAP_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);
+	int k, lim = BITS_TO_LONGS(bits);
+	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	unsigned long mask = (1UL << rem) - 1;
+	for (k = 0; off + k < lim; ++k) {
+		unsigned long upper;
+
+		/*
+		 * If shift is not word aligned, take lower rem bits of
+		 * word above and make them the top rem bits of result.
+		 */
+		if (rem && off + k + 1 < lim)
+			upper = src[off + k + 1] & mask;
+		else
+			upper = 0;
+		dst[k] = upper << (BITS_PER_LONG - rem) | src[off + k] >> rem;
+	}
+	if (off)
+		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
 }
 EXPORT_SYMBOL(bitmap_shift_right);
 
@@ -111,15 +118,23 @@
 void bitmap_shift_left(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
-	int k;
-	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);
-
-	BUG_ON(bits > MAX_BITMAP_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);
+	int k, lim = BITS_TO_LONGS(bits);
+	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	for (k = lim - off - 1; k >= 0; --k) {
+		unsigned long lower;
+
+		/*
+		 * If shift is not word aligned, take upper rem bits of
+		 * word below and make them the bottom rem bits of result.
+		 */
+		if (rem && k > 0)
+			lower = src[k - 1] >> (BITS_PER_LONG - rem);
+		else
+			lower = 0;
+		dst[k + off] = lower | src[k] << rem;
+	}
+	if (off)
+		memset(dst, 0, off*sizeof(unsigned long));
 }
 EXPORT_SYMBOL(bitmap_shift_left);
 

Re: remove bitmap_shift_*() bitmap length limits

[William Lee Irwin III]

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

On Mon, Mar 29, 2004 at 10:51:52PM -0800, William Lee Irwin III wrote:
> Given zeroed tail preconditions these implementations satisfy zeroed
> tail postconditions, which makes them compatible with whatever changes
> from Paul Jackson one may want to merge in the future. No particular
> effort was required to ensure this.
> A small (but hopefully forgiveable) cleanup is a spelling correction:
> s/bitmap_shift_write/bitmap_shift_right/ in one of the kerneldoc comments.
> The primary effect of the patch is to remove the MAX_BITMAP_BITS
> limitation, so restoring the NR_CPUS to be limited only by stackspace
> and slab allocator maximums. They also look vaguely more efficient than
> the current code, though as this was not done for performance reasons,
> no performance testing was done.

An updated userspace test harness properly more demonstrating the
zeroed tail preconditions/postconditions properties is included as a
MIME attachment. The bitmap code requires no changes. This is merely a
more adequate testcase.


-- wli

[-- Attachment #2: bitmap_test.c --]
[-- Type: text/x-csrc, Size: 9171 bytes --]

#include <limits.h>
#include <stdio.h>
#include <assert.h>
#include <sys/time.h>
#include <time.h>

struct ref {
	void *p;
};

#define EXPORT_SYMBOL(x)	static struct ref __ref__##x = { .p = (x) }
#define BITS_TO_LONGS(bits) \
        (((bits)+BITS_PER_LONG-1)/BITS_PER_LONG)
#define DECLARE_BITMAP(name,bits) \
        unsigned long name[BITS_TO_LONGS(bits)]
#define CLEAR_BITMAP(name,bits) \
        memset(name, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long))
#define TYPEBITS(t)	(CHAR_BIT*sizeof(t))
#define BITS_PER_LONG	TYPEBITS(unsigned long)

#define MAX_BITMAP_BITS	512

#define BUG_ON(p)	assert(!(p))

static inline void bitmap_clear(unsigned long *bitmap, int bits)
{
        CLEAR_BITMAP((unsigned long *)bitmap, bits);
}

static inline void bitmap_fill(unsigned long *bitmap, int bits)
{
        memset(bitmap, 0xff, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline void bitmap_copy(unsigned long *dst,
                        const unsigned long *src, int bits)
{
        memcpy(dst, src, BITS_TO_LONGS(bits)*sizeof(unsigned long));
}

static inline int set_bit(int nr, unsigned long *addr)
{
	unsigned long mask = 1UL << (nr % BITS_PER_LONG);
	int retval = !!(addr[nr/BITS_PER_LONG] & mask);
	addr[nr/BITS_PER_LONG] |= mask;
	return retval;
}

static inline int clear_bit(int nr, unsigned long *addr)
{
	unsigned long mask = 1UL << (nr % BITS_PER_LONG);
	int retval = !!(addr[nr/BITS_PER_LONG] & mask);
	addr[nr/BITS_PER_LONG] &= ~mask;
	return retval;
}

static inline int test_bit(int nr, const unsigned long *addr)
{
	return !!(addr[nr/BITS_PER_LONG] & (1UL << (nr % BITS_PER_LONG)));
}

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;
	int nr = BITS_TO_LONGS(bits);

	for (k = 0; k < nr; ++k)
		bitmap[k] = ~bitmap[k];
}
EXPORT_SYMBOL(bitmap_complement);

/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	unsigned long mask = (1UL << rem) - 1;
	for (k = 0; off + k < lim; ++k) {
		unsigned long upper;

		/*
		 * If shift is not word aligned, take lower rem bits of
		 * word above and make them the top rem bits of result.
		 */
		if (rem && off + k + 1 < lim)
			upper = src[off + k + 1] & mask;
		else
			upper = 0;
		dst[k] = upper << (BITS_PER_LONG - rem) | src[off + k] >> rem;
	}
	if (off)
		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
}
EXPORT_SYMBOL(bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k, lim = BITS_TO_LONGS(bits);
	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
	for (k = lim - off - 1; k >= 0; --k) {
		unsigned long lower;

		/*
		 * If shift is not word aligned, take upper rem bits of
		 * word below and make them the bottom rem bits of result.
		 */
		if (rem && k > 0)
			lower = src[k - 1] >> (BITS_PER_LONG - rem);
		else
			lower = 0;
		dst[k + off] = lower | src[k] << rem;
	}
	if (off)
		memset(dst, 0, off*sizeof(unsigned long));
}
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);


/*
 * bitmap_shift_right - logical right shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting right (dividing) means moving bits in the MS -> LS bit
 * direction.  Zeros are fed into the vacated MS positions and the
 * LS bits shifted off the bottom are lost.
 */
void old_bitmap_shift_right(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_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(old_bitmap_shift_right);

/*
 * bitmap_shift_left - logical left shift of the bits in a bitmap
 *   @dst - destination bitmap
 *   @src - source bitmap
 *   @nbits - shift by this many bits
 *   @bits - bitmap size, in bits
 *
 * Shifting left (multiplying) means moving bits in the LS -> MS
 * direction.  Zeros are fed into the vacated LS bit positions
 * and those MS bits shifted off the top are lost.
 */
void old_bitmap_shift_left(unsigned long *dst,
			const unsigned long *src, int shift, int bits)
{
	int k;
	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);

	BUG_ON(bits > MAX_BITMAP_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(old_bitmap_shift_left);

#define ALIGN(x,y)	(((x) + (y) - 1) & ~((y) - 1))
#define BITALIGN(x)	ALIGN(x, 1)

int main(void)
{
	int n;
	struct timeval tv;
	unsigned short seed[3];
	unsigned long bitmap1[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap2[BITS_TO_LONGS(MAX_BITMAP_BITS)],
			bitmap3[BITS_TO_LONGS(MAX_BITMAP_BITS)];

	gettimeofday(&tv, NULL);
	seed[0] = (unsigned short)tv.tv_usec;
	seed[1] = (unsigned short)getpid();
	seed[2] = (unsigned short)0;

	while (1) {
		int k, shift, bits = 1;
		++n;
		memset(bitmap1, 0, sizeof(bitmap1));
		memset(bitmap2, 0, sizeof(bitmap2));
		memset(bitmap3, 0, sizeof(bitmap3));
		while (bits <= 1)
			bits = (unsigned long)nrand48(seed) % (MAX_BITMAP_BITS+1);
		bits = BITALIGN(bits);
		for (k = 0; k < BITS_TO_LONGS(bits); ++k) {
			bitmap1[k] = (unsigned long)nrand48(seed);
			if (k == BITS_TO_LONGS(bits) - 1 && bits % BITS_PER_LONG)
				bitmap1[k] &= (1UL << (bits % BITS_PER_LONG)) - 1;
		}
		shift = (unsigned long)nrand48(seed) % bits;
		shift = BITALIGN(shift);
		memcpy(bitmap2, bitmap1, sizeof(bitmap1));
		memcpy(bitmap3, bitmap1, sizeof(bitmap1));
		if (n & 1) {
			old_bitmap_shift_left(bitmap1, bitmap1, shift, bits);
			bitmap_shift_left(bitmap2, bitmap2, shift, bits);
		} else {
			old_bitmap_shift_right(bitmap1, bitmap1, shift, bits);
			bitmap_shift_right(bitmap2, bitmap2, shift, bits);
		}
		if (memcmp(bitmap1, bitmap2, sizeof(bitmap1))) {
			int mismatches = 0;
			for (k = 0; k < BITS_TO_LONGS(bits); ++k) {
				int match;
				unsigned long mask;
				mask = (1UL << (bits % BITS_PER_LONG)) - 1;
				if (k < bits/BITS_PER_LONG)
					match = !!(bitmap1[k] == bitmap2[k]);
				else {
					match = !((bitmap1[k] ^ bitmap2[k]) & mask);
				}
				if (!match)
					mismatches++;
			}
			if (!mismatches)
				continue;

			printf("problem %s/%d/%d!!!\n", (n&1) ? "left" : "right", shift, bits);
			for (k = 0; k < BITS_TO_LONGS(bits); ++k) {
				int match;
				unsigned long mask;
				mask = (1UL << (bits % BITS_PER_LONG)) - 1;
				if (k < bits/BITS_PER_LONG)
					match = !!(bitmap1[k] == bitmap2[k]);
				else {
					match = !((bitmap1[k] ^ bitmap2[k]) & mask);
				}
				printf("orig/old/new %c = 0x%0*lx/0x%0*lx/0x%0*lx\n",
					match ? ' ' : '*',
					2*sizeof(bitmap3[k]), bitmap3[k],
					2*sizeof(bitmap1[k]), bitmap1[k],
					2*sizeof(bitmap2[k]), bitmap2[k]);
			}
			exit(1);
		}
	}
	return 0;
}

Re: remove bitmap_shift_*() bitmap length limits

[William Lee Irwin III]

On Mon, Mar 29, 2004 at 11:36:04PM -0800, William Lee Irwin III wrote:
> An updated userspace test harness properly more demonstrating the
> zeroed tail preconditions/postconditions properties is included as a
> MIME attachment. The bitmap code requires no changes. This is merely a
> more adequate testcase.

The new testcase found issues with unaligned bitmap lengths. Fixed patch
below;


Index: mm5-2.6.5-rc2/lib/bitmap.c
===================================================================
--- mm5-2.6.5-rc2.orig/lib/bitmap.c	2004-03-29 17:44:14.000000000 -0800
+++ mm5-2.6.5-rc2/lib/bitmap.c	2004-03-30 00:09:21.000000000 -0800
@@ -12,8 +12,6 @@
 #include <asm/bitops.h>
 #include <asm/uaccess.h>
 
-#define MAX_BITMAP_BITS	512U	/* for ia64 NR_CPUS maximum */
-
 int bitmap_empty(const unsigned long *bitmap, int bits)
 {
 	int k, lim = bits/BITS_PER_LONG;
@@ -72,7 +70,7 @@
 EXPORT_SYMBOL(bitmap_complement);
 
 /*
- * bitmap_shift_write - logical right shift of the bits in a bitmap
+ * bitmap_shift_right - logical right shift of the bits in a bitmap
  *   @dst - destination bitmap
  *   @src - source bitmap
  *   @nbits - shift by this many bits
@@ -85,15 +83,32 @@
 void bitmap_shift_right(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
-	int k;
-	DECLARE_BITMAP(__shr_tmp, MAX_BITMAP_BITS);
-
-	BUG_ON(bits > MAX_BITMAP_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);
+	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	unsigned long mask = (1UL << left) - 1;
+	for (k = 0; off + k < lim; ++k) {
+		unsigned long upper, lower;
+
+		/*
+		 * If shift is not word aligned, take lower rem bits of
+		 * word above and make them the top rem bits of result.
+		 */
+		if (!rem || off + k + 1 >= lim)
+			upper = 0;
+		else {
+			upper = src[off + k + 1];
+			if (off + k + 1 == lim - 1 && left)
+				upper &= mask;
+		}
+		lower = src[off + k];
+		if (left && off + k == lim - 1)
+			lower &= mask;
+		dst[k] = upper << (BITS_PER_LONG - rem) | lower >> rem;
+		if (left && k == lim - 1)
+			dst[k] &= mask;
+	}
+	if (off)
+		memset(&dst[lim - off], 0, off*sizeof(unsigned long));
 }
 EXPORT_SYMBOL(bitmap_shift_right);
 
@@ -111,15 +126,28 @@
 void bitmap_shift_left(unsigned long *dst,
 			const unsigned long *src, int shift, int bits)
 {
-	int k;
-	DECLARE_BITMAP(__shl_tmp, MAX_BITMAP_BITS);
-
-	BUG_ON(bits > MAX_BITMAP_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);
+	int k, lim = BITS_TO_LONGS(bits), left = bits % BITS_PER_LONG;
+	int off = shift/BITS_PER_LONG, rem = shift % BITS_PER_LONG;
+	for (k = lim - off - 1; k >= 0; --k) {
+		unsigned long upper, lower;
+
+		/*
+		 * If shift is not word aligned, take upper rem bits of
+		 * word below and make them the bottom rem bits of result.
+		 */
+		if (rem && k > 0)
+			lower = src[k - 1];
+		else
+			lower = 0;
+		upper = src[k];
+		if (left && k == lim - 1)
+			upper &= (1UL << left) - 1;
+		dst[k + off] = lower  >> (BITS_PER_LONG - rem) | upper << rem;
+		if (left && k + off == lim - 1)
+			dst[k + off] &= (1UL << left) - 1;
+	}
+	if (off)
+		memset(dst, 0, off*sizeof(unsigned long));
 }
 EXPORT_SYMBOL(bitmap_shift_left);
 

Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson]

> The primary effect of the patch is to remove the MAX_BITMAP_BITS

I'm all in favor of that, and this appears one of the two
reasonable alternatives to accomplish that.

The other, perhaps, would be a single bit loop, but one
that went directly into the destination buffer.

That would be slower, smaller and easier to see by
inspection that it was probably right.

This bitmap shift routines receive limited use at present.
Offhand, I see only one use -- a bitmap_shift_right() in
bitmap_scnprintf(), and a few physids_shift macros, that
are in turn themselves unused.

This might argue for the slow, stupid, small solution ...

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

Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson]

Bill,

Here's roughly what I mean by slow and stupid (code untested, just a way
of presenting an alternative idea).  Perhaps my head is in a weird
place, but I find the following easier to understand.

lib/bitmap.c:
=============

    static void _setbitval(unsigned long *dst,
			    unsigned int n, int val, unsigned int nbits)
    {
	    if (n >= nbits)
		    return;
	    if (val)
		    set_bit(n, dst);
	    else
		    clear_bit(n, dst);
    }

    static int _getbitval(unsigned long *src, unsigned int n, unsigned int nbits)
    {
	    if (n >= nbits)
		    return 0;
	    return test_bit(n, src) ? 1 : 0;
    }

    void bitmap_shift_right(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = 0; k < bits; k++)
		    _setbitval(dst, k, _getbitval(src, k+shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_right);

    void bitmap_shift_left(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = 0; k < bits; k++)
		    _setbitval(dst, k, _getbitval(src, k-shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_left);

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

Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson]

There was one bug in my untested code for simple bitmap shifts,
the left shift needs to scan downwards, not upwards, so as to
avoid clobbering the input if shifting inplace.

The total text size of my user level test program is actually
made smaller with this per-bit simple implementation, as compared
to the implementation currently in the kernel, by 80 bytes.

Bill Irwin's more sophisticated version grows the text size,
over the current implementation, by 304 bytes.  This is on
Pentium pc, gcc version 3.3.2, compiled -O2.

Given the very rare usage this bitmap shift routines receive,
I cast my vote for small and simple.

The more sophisticated logic of Bill's implementation is
impressive, but unjustified in this situation, in my view.

My fixed shift functions are:

lib/bitmap.c:
=============

    static void _setbitval(unsigned long *dst,
			    unsigned int n, int val, unsigned int nbits)
    {
	    if (n >= nbits)
		    return;
	    if (val)
		    set_bit(n, dst);
	    else
		    clear_bit(n, dst);
    }

    static int _getbitval(const unsigned long *src,
			    unsigned int n, unsigned int nbits)
    {
	    if (n >= nbits)
		    return 0;
	    return test_bit(n, src) ? 1 : 0;
    }

    void bitmap_shift_right(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = 0; k < bits; k++)
		    _setbitval(dst, k, _getbitval(src, k+shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_right);

    void bitmap_shift_left(unsigned long *dst,
			    const unsigned long *src, int shift, int bits)
    {
	    int k;
	    for (k = bits-1; k >= 0; k--)
		    _setbitval(dst, k, _getbitval(src, k-shift, bits), bits);
    }
    EXPORT_SYMBOL(bitmap_shift_left);


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

Re: remove bitmap_shift_*() bitmap length limits

[William Lee Irwin III]

On Sat, Apr 03, 2004 at 10:57:12PM -0800, Paul Jackson wrote:
> There was one bug in my untested code for simple bitmap shifts,
> the left shift needs to scan downwards, not upwards, so as to
> avoid clobbering the input if shifting inplace.
> The total text size of my user level test program is actually
> made smaller with this per-bit simple implementation, as compared
> to the implementation currently in the kernel, by 80 bytes.
> Bill Irwin's more sophisticated version grows the text size,
> over the current implementation, by 304 bytes.  This is on
> Pentium pc, gcc version 3.3.2, compiled -O2.
> Given the very rare usage this bitmap shift routines receive,
> I cast my vote for small and simple.
> The more sophisticated logic of Bill's implementation is
> impressive, but unjustified in this situation, in my view.
> My fixed shift functions are:

I don't see this as a hard problem or why you call the implementation I
brewed up impressive. I don't personally have a preference as to what
implementation is used so long as it's not got fixed-size arrays in it,
though I am somewhat puzzled as to why you bothered.


-- wli

Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson]

Hah - save another 16 bytes of kernel text size, by marking _setbitval
and _getbitval "inline".  Apparently their function call overhead was
slightly bigger than their guts, so it's cheaper to have two copies of
each.  Faster too, I presume.  Not that that's the primary concern.

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

Re: remove bitmap_shift_*() bitmap length limits

[Paul Jackson]

> though I am somewhat puzzled as to why you bothered.

Mostly because I enjoy writing such bits of code.
Have a good night, Bill.

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