remove bitmap_shift_*() bitmap length limits
Subsystems (2)
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
#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;
}lib/bitmap.c +36 -21
@@ -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);
Quoted 11 lines · William Lee Irwin III
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 theMAX_BITMAP_BITSlimitation, so restoring theNR_CPUSto 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
#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;
}Quoted 4 lines · William Lee Irwin III
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;
lib/bitmap.c +49 -21
@@ -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);
Quoted 1 line
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 ...
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Bill,
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);Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373There 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);Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Quoted 6 lines · 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.
Quoted 8 lines
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
Quoted 1 line
though I am somewhat puzzled as to why you bothered.
Mostly because I enjoy writing such bits of code.
Have a good night, Bill.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373Hah - 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.
Signature · 3 lines
I won't rest till it's the best ...
Programmer, Linux Scalability
Paul Jackson <[email protected]> 1.650.933.1373