From 87e24802586333fa861861f6493c76039872755b Mon Sep 17 00:00:00 2001 From: Paul Jackson Date: Fri, 24 Mar 2006 03:15:44 -0800 Subject: [PATCH] bitmap: region cleanup Paul Mundt says: This patch set implements a number of patches to clean up and restructure the bitmap region code, in addition to extending the interface to support multiword spanning allocations. The current implementation (before this patch set) is limited by only being able to allocate pages <= BITS_PER_LONG, as noted by the strategically positioned BUG_ON() at lib/bitmap.c:752: /* We don't do regions of pages > BITS_PER_LONG. The * algorithm would be a simple look for multiple zeros in the * array, but there's no driver today that needs this. If you * trip this BUG(), you get to code it... */ BUG_ON(pages > BITS_PER_LONG); As I seem to have been the first person to trigger this, the result ends up being the following patch set with the help of Paul Jackson. The final patch in the series eliminates quite a bit of code duplication, so the bitmap code size ends up being smaller than the current implementation as an added bonus. After these are applied, it should already be possible to do multiword allocations with dma_alloc_coherent() out of ranges established by dma_declare_coherent_memory() on x86 without having to change any of the code, and the SH store queue API will follow up on this as the other user that needs support for this. This patch: Some code cleanup on the lib/bitmap.c bitmap_*_region() routines: * spacing * variable names * comments Has no change to code function. Signed-off-by: Paul Mundt Signed-off-by: Paul Jackson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/bitmap.c | 64 ++++++++++++++++++++++++++++++++++++------------------------ 1 file changed, 38 insertions(+), 26 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 48e708381d4..3fab1ce9ac6 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -677,39 +677,38 @@ int bitmap_bitremap(int oldbit, const unsigned long *old, EXPORT_SYMBOL(bitmap_bitremap); /** - * bitmap_find_free_region - find a contiguous aligned mem region + * bitmap_find_free_region - find a contiguous aligned mem region * @bitmap: an array of unsigned longs corresponding to the bitmap * @bits: number of bits in the bitmap * @order: region size to find (size is actually 1< BITS_PER_LONG) + if (nbits > BITS_PER_LONG) return -EINVAL; /* make a mask of the order */ - mask = (1ul << (pages - 1)); + mask = (1UL << (nbits - 1)); mask += mask - 1; - /* run up the bitmap pages bits at a time */ - for (i = 0; i < bits; i += pages) { - int index = i/BITS_PER_LONG; + /* run up the bitmap nbits at a time */ + for (i = 0; i < bits; i += nbits) { + int index = i / BITS_PER_LONG; int offset = i - (index * BITS_PER_LONG); - if((bitmap[index] & (mask << offset)) == 0) { - /* set region in bimap */ + if ((bitmap[index] & (mask << offset)) == 0) { + /* set region in bitmap */ bitmap[index] |= (mask << offset); return i; } @@ -719,7 +718,7 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) EXPORT_SYMBOL(bitmap_find_free_region); /** - * bitmap_release_region - release allocated bitmap region + * bitmap_release_region - release allocated bitmap region * @bitmap: a pointer to the bitmap * @pos: the beginning of the region * @order: the order of the bits to release (number is 1< BITS_PER_LONG. The + /* + * We don't do regions of nbits > BITS_PER_LONG. The * algorithm would be a simple look for multiple zeros in the * array, but there's no driver today that needs this. If you - * trip this BUG(), you get to code it... */ - BUG_ON(pages > BITS_PER_LONG); + * trip this BUG(), you get to code it... + */ + BUG_ON(nbits > BITS_PER_LONG); mask += mask - 1; if (bitmap[index] & (mask << offset)) return -EBUSY; -- cgit v1.2.3-70-g09d2 From 74373c6acc52450ced28780d5fece60f1d7d20aa Mon Sep 17 00:00:00 2001 From: Paul Mundt Date: Fri, 24 Mar 2006 03:15:45 -0800 Subject: [PATCH] bitmap: region multiword spanning support Add support to the lib/bitmap.c bitmap_*_region() routines For bitmap regions larger than one word (nbits > BITS_PER_LONG). This removes a BUG_ON() in lib bitmap. I have an updated store queue API for SH that is currently using this with relative success, and at first glance, it seems like this could be useful for x86 (arch/i386/kernel/pci-dma.c) as well. Particularly for anything using dma_declare_coherent_memory() on large areas and that attempts to allocate large buffers from that space. Paul Jackson also did some cleanup to this patch. Signed-off-by: Paul Mundt Signed-off-by: Paul Jackson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/bitmap.c | 110 +++++++++++++++++++++++++++++++++++++++++------------------ 1 file changed, 76 insertions(+), 34 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index 3fab1ce9ac6..f49eabe0927 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -692,26 +692,44 @@ EXPORT_SYMBOL(bitmap_bitremap); */ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) { - unsigned long mask; - int nbits = 1 << order; - int i; - - if (nbits > BITS_PER_LONG) - return -EINVAL; + int nbits; /* number of bits in region */ + int nlongs; /* num longs spanned by region in bitmap */ + int nbitsinlong; /* num bits of region in each spanned long */ + unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ + int i; /* scans bitmap by longs */ + + nbits = 1 << order; + nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; + nbitsinlong = nbits; + if (nbitsinlong > BITS_PER_LONG) + nbitsinlong = BITS_PER_LONG; /* make a mask of the order */ - mask = (1UL << (nbits - 1)); + mask = (1UL << (nbitsinlong - 1)); mask += mask - 1; - /* run up the bitmap nbits at a time */ - for (i = 0; i < bits; i += nbits) { + /* run up the bitmap nbitsinlong at a time */ + for (i = 0; i < bits; i += nbitsinlong) { int index = i / BITS_PER_LONG; int offset = i - (index * BITS_PER_LONG); - if ((bitmap[index] & (mask << offset)) == 0) { + int j, space = 1; + + /* find space in the bitmap */ + for (j = 0; j < nlongs; j++) + if ((bitmap[index + j] & (mask << offset))) { + space = 0; + break; + } + + /* keep looking */ + if (unlikely(!space)) + continue; + + for (j = 0; j < nlongs; j++) /* set region in bitmap */ - bitmap[index] |= (mask << offset); - return i; - } + bitmap[index + j] |= (mask << offset); + + return i; } return -ENOMEM; } @@ -728,13 +746,28 @@ EXPORT_SYMBOL(bitmap_find_free_region); */ void bitmap_release_region(unsigned long *bitmap, int pos, int order) { - int nbits = 1 << order; - unsigned long mask = (1UL << (nbits - 1)); - int index = pos / BITS_PER_LONG; - int offset = pos - (index * BITS_PER_LONG); - + int nbits; /* number of bits in region */ + int nlongs; /* num longs spanned by region in bitmap */ + int index; /* index first long of region in bitmap */ + int offset; /* bit offset region in bitmap[index] */ + int nbitsinlong; /* num bits of region in each spanned long */ + unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ + int i; /* scans bitmap by longs */ + + nbits = 1 << order; + nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; + index = pos / BITS_PER_LONG; + offset = pos - (index * BITS_PER_LONG); + + nbitsinlong = nbits; + if (nbitsinlong > BITS_PER_LONG) + nbitsinlong = BITS_PER_LONG; + + mask = (1UL << (nbitsinlong - 1)); mask += mask - 1; - bitmap[index] &= ~(mask << offset); + + for (i = 0; i < nlongs; i++) + bitmap[index + i] &= ~(mask << offset); } EXPORT_SYMBOL(bitmap_release_region); @@ -750,22 +783,31 @@ EXPORT_SYMBOL(bitmap_release_region); */ int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) { - int nbits = 1 << order; - unsigned long mask = (1UL << (nbits - 1)); - int index = pos / BITS_PER_LONG; - int offset = pos - (index * BITS_PER_LONG); - - /* - * We don't do regions of nbits > BITS_PER_LONG. The - * algorithm would be a simple look for multiple zeros in the - * array, but there's no driver today that needs this. If you - * trip this BUG(), you get to code it... - */ - BUG_ON(nbits > BITS_PER_LONG); + int nbits; /* number of bits in region */ + int nlongs; /* num longs spanned by region in bitmap */ + int index; /* index first long of region in bitmap */ + int offset; /* bit offset region in bitmap[index] */ + int nbitsinlong; /* num bits of region in each spanned long */ + unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ + int i; /* scans bitmap by longs */ + + nbits = 1 << order; + nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; + index = pos / BITS_PER_LONG; + offset = pos - (index * BITS_PER_LONG); + + nbitsinlong = nbits; + if (nbitsinlong > BITS_PER_LONG) + nbitsinlong = BITS_PER_LONG; + + mask = (1UL << (nbitsinlong - 1)); mask += mask - 1; - if (bitmap[index] & (mask << offset)) - return -EBUSY; - bitmap[index] |= (mask << offset); + + for (i = 0; i < nlongs; i++) + if (bitmap[index + i] & (mask << offset)) + return -EBUSY; + for (i = 0; i < nlongs; i++) + bitmap[index + i] |= (mask << offset); return 0; } EXPORT_SYMBOL(bitmap_allocate_region); -- cgit v1.2.3-70-g09d2 From 3cf64b933c90ba701cfdc7188431104c646d7c9e Mon Sep 17 00:00:00 2001 From: Paul Jackson Date: Fri, 24 Mar 2006 03:15:46 -0800 Subject: [PATCH] bitmap: region restructuring Restructure the bitmap_*_region() operations, to avoid code duplication. Also reduces binary text size by about 100 bytes (ia64 arch). The original Bottomley bitmap_*_region patch added about 1000 bytes of compiled kernel text (ia64). The Mundt multiword extension added another 600 bytes, and this restructuring patch gets back about 100 bytes. But the real motivation was the reduced amount of duplicated code. Tested by Paul Mundt using <= BITS_PER_LONG as well as power of 2 aligned multiword spanning allocations. Signed-off-by: Paul Mundt Signed-off-by: Paul Jackson Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- lib/bitmap.c | 199 ++++++++++++++++++++++++++++++----------------------------- 1 file changed, 102 insertions(+), 97 deletions(-) (limited to 'lib/bitmap.c') diff --git a/lib/bitmap.c b/lib/bitmap.c index f49eabe0927..8acab0e176e 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -676,138 +676,143 @@ int bitmap_bitremap(int oldbit, const unsigned long *old, } EXPORT_SYMBOL(bitmap_bitremap); -/** - * bitmap_find_free_region - find a contiguous aligned mem region - * @bitmap: an array of unsigned longs corresponding to the bitmap - * @bits: number of bits in the bitmap - * @order: region size to find (size is actually 1< BITS_PER_LONG) - nbitsinlong = BITS_PER_LONG; + /* + * Either nlongs_reg == 1 (for small orders that fit in one long) + * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) + */ + nbits_reg = 1 << order; + index = pos / BITS_PER_LONG; + offset = pos - (index * BITS_PER_LONG); + nlongs_reg = BITS_TO_LONGS(nbits_reg); + nbitsinlong = min(nbits_reg, BITS_PER_LONG); - /* make a mask of the order */ + /* + * Can't do "mask = (1UL << nbitsinlong) - 1", as that + * overflows if nbitsinlong == BITS_PER_LONG. + */ mask = (1UL << (nbitsinlong - 1)); mask += mask - 1; + mask <<= offset; - /* run up the bitmap nbitsinlong at a time */ - for (i = 0; i < bits; i += nbitsinlong) { - int index = i / BITS_PER_LONG; - int offset = i - (index * BITS_PER_LONG); - int j, space = 1; - - /* find space in the bitmap */ - for (j = 0; j < nlongs; j++) - if ((bitmap[index + j] & (mask << offset))) { - space = 0; - break; - } - - /* keep looking */ - if (unlikely(!space)) - continue; - - for (j = 0; j < nlongs; j++) - /* set region in bitmap */ - bitmap[index + j] |= (mask << offset); - - return i; + switch (reg_op) { + case REG_OP_ISFREE: + for (i = 0; i < nlongs_reg; i++) { + if (bitmap[index + i] & mask) + goto done; + } + ret = 1; /* all bits in region free (zero) */ + break; + + case REG_OP_ALLOC: + for (i = 0; i < nlongs_reg; i++) + bitmap[index + i] |= mask; + break; + + case REG_OP_RELEASE: + for (i = 0; i < nlongs_reg; i++) + bitmap[index + i] &= ~mask; + break; } - return -ENOMEM; +done: + return ret; +} + +/** + * bitmap_find_free_region - find a contiguous aligned mem region + * @bitmap: array of unsigned longs corresponding to the bitmap + * @bits: number of bits in the bitmap + * @order: region size (log base 2 of number of bits) to find + * + * Find a region of free (zero) bits in a @bitmap of @bits bits and + * allocate them (set them to one). Only consider regions of length + * a power (@order) of two, aligned to that power of two, which + * makes the search algorithm much faster. + * + * Return the bit offset in bitmap of the allocated region, + * or -errno on failure. + */ +int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) +{ + int pos; /* scans bitmap by regions of size order */ + + for (pos = 0; pos < bits; pos += (1 << order)) + if (__reg_op(bitmap, pos, order, REG_OP_ISFREE)) + break; + if (pos == bits) + return -ENOMEM; + __reg_op(bitmap, pos, order, REG_OP_ALLOC); + return pos; } EXPORT_SYMBOL(bitmap_find_free_region); /** * bitmap_release_region - release allocated bitmap region - * @bitmap: a pointer to the bitmap - * @pos: the beginning of the region - * @order: the order of the bits to release (number is 1< BITS_PER_LONG) - nbitsinlong = BITS_PER_LONG; - - mask = (1UL << (nbitsinlong - 1)); - mask += mask - 1; - - for (i = 0; i < nlongs; i++) - bitmap[index + i] &= ~(mask << offset); + __reg_op(bitmap, pos, order, REG_OP_RELEASE); } EXPORT_SYMBOL(bitmap_release_region); /** * bitmap_allocate_region - allocate bitmap region - * @bitmap: a pointer to the bitmap - * @pos: the beginning of the region - * @order: the order of the bits to allocate (number is 1< BITS_PER_LONG) - nbitsinlong = BITS_PER_LONG; - - mask = (1UL << (nbitsinlong - 1)); - mask += mask - 1; - - for (i = 0; i < nlongs; i++) - if (bitmap[index + i] & (mask << offset)) - return -EBUSY; - for (i = 0; i < nlongs; i++) - bitmap[index + i] |= (mask << offset); + if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) + return -EBUSY; + __reg_op(bitmap, pos, order, REG_OP_ALLOC); return 0; } EXPORT_SYMBOL(bitmap_allocate_region); -- cgit v1.2.3-70-g09d2 From 37d54111c133bea05fbae9dfe6d3d61a1b19c09b Mon Sep 17 00:00:00 2001 From: Akinobu Mita Date: Sun, 26 Mar 2006 01:39:56 -0800 Subject: [PATCH] bitops: hweight() related cleanup By defining generic hweight*() routines - hweight64() will be defined on all architectures - hweight_long() will use architecture optimized hweight32() or hweight64() I found two possible cleanups by these reasons. Signed-off-by: Akinobu Mita Signed-off-by: Andrew Morton Signed-off-by: Linus Torvalds --- drivers/ieee1394/highlevel.c | 3 +-- lib/bitmap.c | 19 ++----------------- 2 files changed, 3 insertions(+), 19 deletions(-) (limited to 'lib/bitmap.c') diff --git a/drivers/ieee1394/highlevel.c b/drivers/ieee1394/highlevel.c index 734b121a055..491e6032bde 100644 --- a/drivers/ieee1394/highlevel.c +++ b/drivers/ieee1394/highlevel.c @@ -306,8 +306,7 @@ u64 hpsb_allocate_and_register_addrspace(struct hpsb_highlevel *hl, u64 align_mask = ~(alignment - 1); if ((alignment & 3) || (alignment > 0x800000000000ULL) || - ((hweight32(alignment >> 32) + - hweight32(alignment & 0xffffffff) != 1))) { + (hweight64(alignment) != 1)) { HPSB_ERR("%s called with invalid alignment: 0x%048llx", __FUNCTION__, (unsigned long long)alignment); return retval; diff --git a/lib/bitmap.c b/lib/bitmap.c index 8acab0e176e..ed2ae3b0cd0 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -253,33 +253,18 @@ int __bitmap_subset(const unsigned long *bitmap1, } EXPORT_SYMBOL(__bitmap_subset); -#if BITS_PER_LONG == 32 int __bitmap_weight(const unsigned long *bitmap, int bits) { int k, w = 0, lim = bits/BITS_PER_LONG; for (k = 0; k < lim; k++) - w += hweight32(bitmap[k]); + w += hweight_long(bitmap[k]); if (bits % BITS_PER_LONG) - w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); + w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); return w; } -#else -int __bitmap_weight(const unsigned long *bitmap, int bits) -{ - int k, w = 0, lim = bits/BITS_PER_LONG; - - for (k = 0; k < lim; k++) - w += hweight64(bitmap[k]); - - if (bits % BITS_PER_LONG) - w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits)); - - return w; -} -#endif EXPORT_SYMBOL(__bitmap_weight); /* -- cgit v1.2.3-70-g09d2