diff options
author | Paul Mundt <lethal@linux-sh.org> | 2006-03-24 03:15:45 -0800 |
---|---|---|
committer | Linus Torvalds <torvalds@g5.osdl.org> | 2006-03-24 07:33:20 -0800 |
commit | 74373c6acc52450ced28780d5fece60f1d7d20aa (patch) | |
tree | 6717fce7fdebbda48ad62b79b4ff721fae1c8dc3 /lib/bitmap.c | |
parent | 87e24802586333fa861861f6493c76039872755b (diff) | |
download | linux-74373c6acc52450ced28780d5fece60f1d7d20aa.tar.gz linux-74373c6acc52450ced28780d5fece60f1d7d20aa.tar.bz2 linux-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.c | 110 |
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); |