[PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Mundt <lethal@linux-sh.org>]

[-- Attachment #1: Type: text/plain, Size: 3685 bytes --]

It seems like I was fortunate enough to trigger the BUG_ON() in the
bitmap API regarding pages > BITS_PER_LONG, so as per the comment, here's
a stupid implementation which seems to get the job done.

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.

The implementation could probably use some work, but it works for me..

Signed-off-by: Paul Mundt <lethal@linux-sh.org>

---

 lib/bitmap.c |   59 ++++++++++++++++++++++++++++++++++++++++++-----------------
 1 file changed, 42 insertions(+), 17 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 48e7083..80131e0 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -695,10 +695,11 @@ int bitmap_find_free_region(unsigned lon
 {
 	unsigned long mask;
 	int pages = 1 << order;
+	int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
 	int i;
 
 	if(pages > BITS_PER_LONG)
-		return -EINVAL;
+		pages = BITS_PER_LONG;
 
 	/* make a mask of the order */
 	mask = (1ul << (pages - 1));
@@ -708,11 +709,24 @@ int bitmap_find_free_region(unsigned lon
 	for (i = 0; i < bits; i += pages) {
 		int index = i/BITS_PER_LONG;
 		int offset = i - (index * BITS_PER_LONG);
-		if((bitmap[index] & (mask << offset)) == 0) {
-			/* set region in bimap */
-			bitmap[index] |= (mask << offset);
-			return i;
-		}
+		int j, space = 1;
+
+		/* find space in the bitmap */
+		for (j = 0; j < span; j++)
+			if ((bitmap[index + j] & (mask << offset))) {
+				space = 0;
+				break;
+			}
+
+		/* keep looking */
+		if (unlikely(!space))
+			continue;
+
+		for (j = 0; j < span; j++)
+			/* set region in bitmap */
+			bitmap[index + j] |= (mask << offset);
+
+		return i;
 	}
 	return -ENOMEM;
 }
@@ -730,30 +744,41 @@ 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 span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
+	unsigned long mask;
 	int index = pos/BITS_PER_LONG;
 	int offset = pos - (index * BITS_PER_LONG);
+	int i;
+
+	if (pages > BITS_PER_LONG)
+		pages = BITS_PER_LONG;
+
+	mask = (1ul << (pages - 1));
 	mask += mask - 1;
-	bitmap[index] &= ~(mask << offset);
+	for (i = 0; i < span; i++)
+		bitmap[index + i] &= ~(mask << offset);
 }
 EXPORT_SYMBOL(bitmap_release_region);
 
 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 {
 	int pages = 1 << order;
-	unsigned long mask = (1ul << (pages - 1));
+	int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
+	unsigned long mask;
 	int index = pos/BITS_PER_LONG;
 	int offset = pos - (index * BITS_PER_LONG);
+	int i;
 
-	/* 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);
+	if (pages > BITS_PER_LONG)
+		pages = BITS_PER_LONG;
+
+	mask = (1ul << (pages - 1));
 	mask += mask - 1;
-	if (bitmap[index] & (mask << offset))
-		return -EBUSY;
-	bitmap[index] |= (mask << offset);
+	for (i = 0; i < span; i++)
+		if (bitmap[index + i] & (mask << offset))
+			return -EBUSY;
+	for (i = 0; i < span; i++)
+		bitmap[index + i] |= (mask << offset);
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_allocate_region);

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]