[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 <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>
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 3fab1ce..f49eabe 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -692,26 +692,44 @@
*/
int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
{
- unsigned long mask;
- int nbits = 1 << order;
- int i;
+ 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 */
- if (nbits > BITS_PER_LONG)
- return -EINVAL;
+ 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 @@
*/
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 @@
*/
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);
+ 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 */
- /*
- * 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);
+ 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);