From f951179269c98ac7b58dcfa3de2e68d4a0a3d680 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 23:00:10 -0700 Subject: [PATCH] Broken bitmap_parse for ncpus > 32 From: Joe Korty This patch replaces the call to bitmap_shift_right() in bitmap_parse() with bitmap_shift_left(). I also prepended comments to the bitmap_shift_* functions defining what 'left' and 'right' means. This is under the theory that if I and all the reviewers were bamboozled, others in the future occasionally might be too. --- lib/bitmap.c | 24 +++++++++++++++++++++++- 1 file changed, 23 insertions(+), 1 deletion(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 6793ac002915..68abf679808b 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -71,6 +71,17 @@ void bitmap_complement(unsigned long *bitmap, int bits) } EXPORT_SYMBOL(bitmap_complement); +/* + * bitmap_shift_write - 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) { @@ -86,6 +97,17 @@ void bitmap_shift_right(unsigned long *dst, } 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) { @@ -269,7 +291,7 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, if (nchunks == 0 && chunk == 0) continue; - bitmap_shift_right(maskp, maskp, CHUNKSZ, nmaskbits); + bitmap_shift_left(maskp, maskp, CHUNKSZ, nmaskbits); *maskp |= chunk; nchunks++; nbits += (nchunks == 1) ? nbits_to_hold_value(chunk) : CHUNKSZ; -- cgit v1.2.3 From 77c8efaeba52f0ebe0aaab689bdbb53bf6f5a723 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Sun, 11 Apr 2004 23:05:41 -0700 Subject: [PATCH] Remove bitmap_shift_*() bitmap length limits From: William Lee Irwin III Chang bitmap_shift_left()/bitmap_shift_right() to have O(1) stackspace requirements. 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. --- lib/bitmap.c | 70 ++++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 49 insertions(+), 21 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 68abf679808b..602b919ef551 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -12,8 +12,6 @@ #include #include -#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 @@ void bitmap_complement(unsigned long *bitmap, int bits) 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 @@ EXPORT_SYMBOL(bitmap_complement); void bitmap_shift_right(unsigned long *dst, const unsigned long *src, int shift, int bits) { - int k; - DECLARE_BITMAP(__shr_tmp, 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 @@ EXPORT_SYMBOL(bitmap_shift_right); void bitmap_shift_left(unsigned long *dst, const unsigned long *src, int shift, int bits) { - int k; - DECLARE_BITMAP(__shl_tmp, 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); -- cgit v1.2.3 From 8447ac2688647d261af7a7397a53548a2a1afc13 Mon Sep 17 00:00:00 2001 From: Andrew Morton Date: Mon, 12 Apr 2004 01:03:29 -0700 Subject: [PATCH] Rename bitmap_clear to bitmap_zero, remove CLEAR_BITMAP From: Rusty Russell clear_bit(n, addr) clears the nth bit. test_and_clear_bit(n, addr) clears the nth bit. cpu_clear(n, cpumask) clears the nth bit (vs. cpus_clear()). bitmap_clear(bitmap, n) clears out all the bits up to n. Moreover, there's a CLEAR_BITMAP() in linux/types.h which bitmap_clear() is a wrapper for. Rename bitmap_clear to bitmap_zero, which is harder to confuse (yes, it bit me), and make everyone use it. --- arch/ia64/sn/kernel/sn2/sn2_smp.c | 2 +- drivers/atm/lanai.c | 6 +++--- drivers/ieee1394/ieee1394_types.h | 2 +- drivers/scsi/atari_NCR5380.c | 4 ++-- include/asm-generic/cpumask_array.h | 2 +- include/asm-i386/mpspec.h | 2 +- include/asm-x86_64/mpspec.h | 2 +- include/linux/bitmap.h | 4 ++-- include/linux/types.h | 2 -- lib/bitmap.c | 2 +- mm/page_alloc.c | 2 +- 11 files changed, 14 insertions(+), 16 deletions(-) (limited to 'lib/bitmap.c') diff --git a/arch/ia64/sn/kernel/sn2/sn2_smp.c b/arch/ia64/sn/kernel/sn2/sn2_smp.c index 3cfb3cd74d51..e8bc389edebb 100644 --- a/arch/ia64/sn/kernel/sn2/sn2_smp.c +++ b/arch/ia64/sn/kernel/sn2/sn2_smp.c @@ -91,7 +91,7 @@ sn2_global_tlb_purge (unsigned long start, unsigned long end, unsigned long nbit short nasids[NR_NODES], nix; DECLARE_BITMAP(nodes_flushed, NR_NODES); - CLEAR_BITMAP(nodes_flushed, NR_NODES); + bitmap_zero(nodes_flushed, NR_NODES); i = 0; diff --git a/drivers/atm/lanai.c b/drivers/atm/lanai.c index 402e78a5ac97..5a7037af6add 100644 --- a/drivers/atm/lanai.c +++ b/drivers/atm/lanai.c @@ -1743,7 +1743,7 @@ static void run_service(struct lanai_dev *lanai) read_lock(&vcc_sklist_lock); vci_bitfield_iterate(lanai, lanai->transmit_ready, iter_transmit); - CLEAR_BITMAP(&lanai->transmit_ready, NUM_VCI); + bitmap_zero(lanai->transmit_ready, NUM_VCI); read_unlock(&vcc_sklist_lock); } } @@ -2158,8 +2158,8 @@ static int __init lanai_dev_open(struct atm_dev *atmdev) /* Basic device fields */ lanai->number = atmdev->number; lanai->num_vci = NUM_VCI; - CLEAR_BITMAP(&lanai->backlog_vccs, NUM_VCI); - CLEAR_BITMAP(&lanai->transmit_ready, NUM_VCI); + bitmap_zero(lanai->backlog_vccs, NUM_VCI); + bitmap_zero(lanai->transmit_ready, NUM_VCI); lanai->naal0 = 0; #ifdef USE_POWERDOWN lanai->nbound = 0; diff --git a/drivers/ieee1394/ieee1394_types.h b/drivers/ieee1394/ieee1394_types.h index 552667142ce1..3165609ec1ec 100644 --- a/drivers/ieee1394/ieee1394_types.h +++ b/drivers/ieee1394/ieee1394_types.h @@ -24,7 +24,7 @@ struct hpsb_tlabel_pool { #define HPSB_TPOOL_INIT(_tp) \ do { \ - CLEAR_BITMAP((_tp)->pool, 64); \ + bitmap_zero((_tp)->pool, 64); \ spin_lock_init(&(_tp)->lock); \ (_tp)->next = 0; \ (_tp)->allocations = 0; \ diff --git a/drivers/scsi/atari_NCR5380.c b/drivers/scsi/atari_NCR5380.c index cd8ddb7084a2..5d1e78ebed83 100644 --- a/drivers/scsi/atari_NCR5380.c +++ b/drivers/scsi/atari_NCR5380.c @@ -329,7 +329,7 @@ static void __init init_tags( void ) for( target = 0; target < 8; ++target ) { for( lun = 0; lun < 8; ++lun ) { ta = &TagAlloc[target][lun]; - CLEAR_BITMAP( ta->allocated, MAX_TAGS ); + bitmap_zero(ta->allocated, MAX_TAGS); ta->nr_allocated = 0; /* At the beginning, assume the maximum queue size we could * support (MAX_TAGS). This value will be decreased if the target @@ -438,7 +438,7 @@ static void free_all_tags( void ) for( target = 0; target < 8; ++target ) { for( lun = 0; lun < 8; ++lun ) { ta = &TagAlloc[target][lun]; - CLEAR_BITMAP( ta->allocated, MAX_TAGS ); + bitmap_zero(ta->allocated, MAX_TAGS); ta->nr_allocated = 0; } } diff --git a/include/asm-generic/cpumask_array.h b/include/asm-generic/cpumask_array.h index bd5c49133c6c..c7e2db29dc53 100644 --- a/include/asm-generic/cpumask_array.h +++ b/include/asm-generic/cpumask_array.h @@ -16,7 +16,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_clear(map) bitmap_zero((map).mask, NR_CPUS) #define cpus_complement(map) bitmap_complement((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) diff --git a/include/asm-i386/mpspec.h b/include/asm-i386/mpspec.h index 78bd12b7ae42..b376b093749c 100644 --- a/include/asm-i386/mpspec.h +++ b/include/asm-i386/mpspec.h @@ -52,7 +52,7 @@ typedef struct physid_mask physid_mask_t; #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_clear(map) bitmap_zero((map).mask, MAX_APICS) #define physids_complement(map) bitmap_complement((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) diff --git a/include/asm-x86_64/mpspec.h b/include/asm-x86_64/mpspec.h index 896b99f11cec..cbe6058e9270 100644 --- a/include/asm-x86_64/mpspec.h +++ b/include/asm-x86_64/mpspec.h @@ -211,7 +211,7 @@ typedef struct physid_mask physid_mask_t; #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_clear(map) bitmap_zero((map).mask, MAX_APICS) #define physids_complement(map) bitmap_complement((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) diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h index 2ad5fb97fa26..81e73cdc1a62 100644 --- a/include/linux/bitmap.h +++ b/include/linux/bitmap.h @@ -16,9 +16,9 @@ int bitmap_equal(const unsigned long *bitmap1, unsigned long *bitmap2, int bits); void bitmap_complement(unsigned long *bitmap, int bits); -static inline void bitmap_clear(unsigned long *bitmap, int bits) +static inline void bitmap_zero(unsigned long *bitmap, int bits) { - CLEAR_BITMAP((unsigned long *)bitmap, bits); + memset(bitmap, 0, BITS_TO_LONGS(bits)*sizeof(unsigned long)); } static inline void bitmap_fill(unsigned long *bitmap, int bits) diff --git a/include/linux/types.h b/include/linux/types.h index 93f5f3653561..23c414f11cbe 100644 --- a/include/linux/types.h +++ b/include/linux/types.h @@ -8,8 +8,6 @@ (((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)) #endif #include diff --git a/lib/bitmap.c b/lib/bitmap.c index 602b919ef551..779d30365e46 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -273,7 +273,7 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, int c, old_c, totaldigits, ndigits, nchunks, nbits; u32 chunk; - bitmap_clear(maskp, nmaskbits); + bitmap_zero(maskp, nmaskbits); nchunks = nbits = totaldigits = c = 0; do { diff --git a/mm/page_alloc.c b/mm/page_alloc.c index 6b4d5dc0c930..8d3f6f46105e 100644 --- a/mm/page_alloc.c +++ b/mm/page_alloc.c @@ -1222,7 +1222,7 @@ static void __init build_zonelists(pg_data_t *pgdat) local_node = pgdat->node_id; load = numnodes; prev_node = local_node; - CLEAR_BITMAP(used_mask, MAX_NUMNODES); + bitmap_zero(used_mask, MAX_NUMNODES); while ((node = find_next_best_node(local_node, used_mask)) >= 0) { /* * We don't want to pressure a particular node. -- cgit v1.2.3