aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorPaul Jackson <pj@sgi.com>2006-03-24 03:15:44 -0800
committerLinus Torvalds <torvalds@g5.osdl.org>2006-03-24 07:33:20 -0800
commit87e24802586333fa861861f6493c76039872755b (patch)
tree631a252da4716798027cd96b4529351e601c50c6
parentf993b3bf80b23d329951fe0fc5ba3647d5d912e9 (diff)
[PATCH] bitmap: region cleanup
Paul Mundt <lethal@linux-sh.org> 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 <lethal@linux-sh.org> Signed-off-by: Paul Jackson <pj@sgi.com> Signed-off-by: Andrew Morton <akpm@osdl.org> Signed-off-by: Linus Torvalds <torvalds@osdl.org>
-rw-r--r--include/linux/bitmap.h3
-rw-r--r--lib/bitmap.c64
2 files changed, 41 insertions, 26 deletions
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 7d8ff97b3e9..d9ed2796985 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -46,6 +46,9 @@
* bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
* bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf
* bitmap_parselist(buf, dst, nbits) Parse bitmap dst from list
+ * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region
+ * bitmap_release_region(bitmap, pos, order) Free specified bit region
+ * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region
*/
/*
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<<order)
*
- * This is used to allocate a memory region from a bitmap. The idea is
- * that the region has to be 1<<order sized and 1<<order aligned (this
- * makes the search algorithm much faster).
+ * Find a sequence of free (zero) bits in a bitmap and allocate
+ * them (set them to one). Only consider sequences of length a
+ * power ('order') of two, aligned to that power of two, which
+ * makes the search algorithm much faster.
*
- * The region is marked as set bits in the bitmap if a free one is
- * found.
- *
- * Returns either beginning of region or negative error
+ * Return the bit offset in bitmap of the allocated sequence,
+ * or -errno on failure.
*/
int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
unsigned long mask;
- int pages = 1 << order;
+ int nbits = 1 << order;
int i;
- if(pages > 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<<order)
@@ -729,27 +728,40 @@ EXPORT_SYMBOL(bitmap_find_free_region);
*/
void bitmap_release_region(unsigned long *bitmap, int pos, int order)
{
- int pages = 1 << order;
- unsigned long mask = (1ul << (pages - 1));
- int index = pos/BITS_PER_LONG;
+ int nbits = 1 << order;
+ unsigned long mask = (1UL << (nbits - 1));
+ int index = pos / BITS_PER_LONG;
int offset = pos - (index * BITS_PER_LONG);
+
mask += mask - 1;
bitmap[index] &= ~(mask << offset);
}
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<<order)
+ *
+ * Allocate (set bits in) a specified region of a bitmap.
+ * Return 0 on success, or -EBUSY if specified region wasn't
+ * free (not all bits were zero).
+ */
int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
{
- int pages = 1 << order;
- unsigned long mask = (1ul << (pages - 1));
- int index = pos/BITS_PER_LONG;
+ 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 pages > 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;