[PATCH] bitmap: Support for pages > BITS_PER_LONG.

[PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Mundt]

[-- 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 --]

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Jackson]

James,

The patch in this lkml thread from Paul Mundt looks to extend
the lib/bitmap.c bitmap_find_free_region() and related
routines that you added in June 2004.  This current patch
extends this code to handle more than a page worth of bits.

I added the others to the CC list because they were on your CC
list on your patch:

    Subject: [PATCH] provide x86 implementation of on-chip coherent memory API
	    for DMA
    From: James Bottomley <James.Bottomley@steeleye.com>
    Date:   30 Jun 2004 21:52:24 -0500

Could you look Mundt's patch, and see if it looks ok?

Thanks.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.925.600.0401

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Jackson]

It looks to me like I never properly reviewed James patch
when it was originally submitted.  It has some minor confusions
that have gotten slightly worse with this patch.

Just reading the patch, I see the following possible opportunities
for improvement:

 * Could the calculation of mask:
        mask = (1ul << (pages - 1));
        mask += mask - 1;
   be simplified to:
	mask = (1UL << pages) - 1;
   (and note that 1UL is easier to read than 1ul)

 * The variable named 'pages' is misnamed.  It happens that the
   current user of this code is using one bit to represent one
   page, but that is not something that this code has any business
   knowing.  For this code, it might better be 'nbits' or some such.

 * With your 'pages > BITS_PER_LONG' patch, this 'pages' variable
   becomes more confused.  Apparently, it is the number of bits
   to consider in each word scanned, and 'scan' is the number of
   words to scan.  Hmmm ... that's not quite right either.  It
   seems that 'pages' is first set (in bitmask_find_free_region)
   to the number of bits total to find, which value is used to
   compute 'scan', the number of words needed to hold that many
   bits; then 'pages' is recomputed to be the number of bits in
   a single word to examine, which value is used to compute the
   'mask'.  This sort of dual use of a poorly named variable is
   confusing.  I'd suggest two variables - 'nbitstotal' and
   'nbitsinword', or some such.  Or short variable names, and
   a comment:
	int bt;		/* total number of bits to find free */
	int bw;		/* how many bits to consider in one word */

 * The block comment states:
	allocate a memory region from a bitmap
   This is another confusion between the user of this code, and
   this current code.  I think we are allocating a sequence of
   consecutive bits of size and allignment some power of two
   ('order' is that power), not allocating a 'memory region.'

 * There is no function block comment for bitmap_allocate_region().

 * The include/linux/bitmap.h header comment is missing the
   three lines specifying these three routines.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.925.600.0401

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Jackson]

Someone unnamed has suggested I submit a patch with these cleanups.

But I am  lazy git who hates to test code, and it looks like Paul
Mundt is in a position to actually test that whatever we end up
with still works.

So I intend to send in two totally untested patches shortly:
 1) some minor cleanups of these bitmap routines, and
 2) Mundt's > BITS_PER_LONG patch, more or less, on top of that.

Then perhaps Mundt could retest and fix what I broke, then send in a
final pair of patches for Andrew's consideration.

If this isn't such a hot idea, Mundt, holler, and we can work
something else out.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.925.600.0401

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[James Bottomley]

On Wed, 2006-01-18 at 19:11 -0800, Paul Jackson wrote:
> Could you look Mundt's patch, and see if it looks ok?

Not being on lkml, this was harder than it sounds, but I eventually
found the actual patch on marc.  However, no, it doesn't look right.

This:

> +		/* find space in the bitmap */
> +		for (j = 0; j < span; j++)
> +			if ((bitmap[index + j] & (mask << offset))) {


Is wrong.  You're looking for an unset span of order bits at a given
offset.  So you get the byte offset for the first, then all the
following bitmap[n] need to be zero until you need to do an offset in
reverse for the last bit.  i.e. (assuming BITS_PER_LONG=32) for a span
of 126 at offset 1, you check

bitmap[0] & 0xfffffffe == 0
bitmap[1] & 0xffffffff == 0
bitmap[2] & 0xffffffff == 0
bitmap[3] & 0x7fffffff == 0

and so on.

> +				space = 0;
> +				break;
> +			}
> +
> +		/* keep looking */
> +		if (unlikely(!space))
> +			continue;
> +
> +		for (j = 0; j < span; j++)
> +			/* set region in bitmap */
> +			bitmap[index + j] |= (mask << offset);

Likewise, you'd have to or in what you checked above.

James

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Mundt]

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

On Thu, Jan 19, 2006 at 09:28:30PM -0600, James Bottomley wrote:
> On Wed, 2006-01-18 at 19:11 -0800, Paul Jackson wrote:
> > Could you look Mundt's patch, and see if it looks ok?
> 
> Not being on lkml, this was harder than it sounds, but I eventually
> found the actual patch on marc.  However, no, it doesn't look right.
> 
> This:
> 
> > +		/* find space in the bitmap */
> > +		for (j = 0; j < span; j++)
> > +			if ((bitmap[index + j] & (mask << offset))) {
> 
> 
> Is wrong.  You're looking for an unset span of order bits at a given
> offset.  So you get the byte offset for the first, then all the
> following bitmap[n] need to be zero until you need to do an offset in
> reverse for the last bit.  i.e. (assuming BITS_PER_LONG=32) for a span
> of 126 at offset 1, you check
> 
> bitmap[0] & 0xfffffffe == 0
> bitmap[1] & 0xffffffff == 0
> bitmap[2] & 0xffffffff == 0
> bitmap[3] & 0x7fffffff == 0
> 
> and so on.
> 
This code operates on the assumption that offset is always 0 for the
pages == BITS_PER_LONG case. It's calculated in this order:

        unsigned int pages = 1 << order;
        int i;
        int span = (pages + (BITS_PER_LONG - 1)) / BITS_PER_LONG;

        if (pages > BITS_PER_LONG)
                pages = BITS_PER_LONG;

...
        for (i = 0; i < bits; i += pages) {
                int index = i/BITS_PER_LONG;
                int offset = i - (index * BITS_PER_LONG);
...

So in the case of pages >= BITS_PER_LONG the mask will be 0xffffffff, and
offset will be 0, and the span will define how many adjacent words we
need to set. Unless I'm missing something, I don't see how your case
would happen. I did test this quite a bit mixing both tiny and large
orders.

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

Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.

[Paul Jackson]

James wrote:
> Is wrong.  You're looking for an unset span of order bits at a given
> offset. 

But your comment, James, said:

 * 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).



So, like the other Paul said:
> Unless I'm missing something, I don't see how your case
> would happen.

James further wrote:
>   i.e. (assuming BITS_PER_LONG=32) for a span
> of 126 at offset 1, you check

I thought that the span had to be a power of two.  Perhaps
you mean 128, not 126 (order 7: 2**7 == 128).

And I thought, from your comment above, that if the span was
128, then the alignment had to be 128 as well.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.925.600.0401