Messages in this thread Patch in this message | | | Date | Thu, 19 Jan 2006 03:48:12 +0200 | From | Paul Mundt <> | Subject | [PATCH] bitmap: Support for pages > BITS_PER_LONG. |
| |
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);[unhandled content-type:application/pgp-signature] | |