summaryrefslogtreecommitdiff
path: root/lib/bitmap.c
diff options
context:
space:
mode:
authorPaul Mundt <lethal@linux-sh.org>2006-03-24 03:15:45 -0800
committerLinus Torvalds <torvalds@g5.osdl.org>2006-03-24 07:33:20 -0800
commit74373c6acc52450ced28780d5fece60f1d7d20aa (patch)
tree6717fce7fdebbda48ad62b79b4ff721fae1c8dc3 /lib/bitmap.c
parent87e24802586333fa861861f6493c76039872755b (diff)
downloadlwn-74373c6acc52450ced28780d5fece60f1d7d20aa.tar.gz
lwn-74373c6acc52450ced28780d5fece60f1d7d20aa.zip
[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>
Diffstat (limited to 'lib/bitmap.c')
-rw-r--r--lib/bitmap.c110
1 files changed, 76 insertions, 34 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 3fab1ce9ac65..f49eabe09271 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);