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 <[email protected]> --- 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:
pgpkO7jno7y98.pgp
Description: PGP signature
- Follow-Ups:
- Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.
- From: Paul Jackson <[email protected]>
- Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.
- From: Paul Jackson <[email protected]>
- Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.
- Prev by Date: Re: Linux 2.6.16-rc1
- Next by Date: Re: 2.6.15-rc5: latency regression vs 2.6.14 in exit_mmap->free_pgtables
- Previous by thread: [2.6 patch] drivers/base/: proper prototypes
- Next by thread: Re: [PATCH] bitmap: Support for pages > BITS_PER_LONG.
- Index(es):
 |