diff options
author | James Bottomley <jejb@raven.il.steeleye.com> | 2004-08-14 04:13:34 -0500 |
---|---|---|
committer | James Bottomley <jejb@raven.il.steeleye.com> | 2004-08-14 04:13:34 -0500 |
commit | 8d5c08a4e7c8f9a2010a37c93285d2196314ae17 (patch) | |
tree | 0a75e1fe3fa644b3f5ae71ca3c8d99760ea01130 /lib | |
parent | 4d8021616effa7a49b6df2ad0083dcce6016a3a7 (diff) | |
parent | d80ba2fd04af740267e4576773291982036c30f4 (diff) | |
download | history-8d5c08a4e7c8f9a2010a37c93285d2196314ae17.tar.gz |
Merge
Diffstat (limited to 'lib')
-rw-r--r-- | lib/bitmap.c | 82 |
1 files changed, 82 insertions, 0 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c index 7eb16be309b5ff..8ffd202dcdd6a1 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c @@ -408,3 +408,85 @@ int bitmap_parse(const char __user *ubuf, unsigned int ubuflen, return 0; } EXPORT_SYMBOL(bitmap_parse); + +/** + * bitmap_find_free_region - find a contiguous aligned mem region + * @bitmap: an array of unsigned longs corresponding to the bitmap + * @bits: number of bits in the bitmap + * @order: region size to find (size is actually 1<<order) + * + * 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). + * + * The region is marked as set bits in the bitmap if a free one is + * found. + * + * Returns either beginning of region or negative error + */ +int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) +{ + unsigned long mask; + int pages = 1 << order; + int i; + + if(pages > BITS_PER_LONG) + return -EINVAL; + + /* make a mask of the order */ + mask = (1ul << (pages - 1)); + mask += mask - 1; + + /* run up the bitmap pages bits at a time */ + 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; + } + } + return -ENOMEM; +} +EXPORT_SYMBOL(bitmap_find_free_region); + +/** + * bitmap_release_region - release allocated bitmap region + * @bitmap: a pointer to the bitmap + * @pos: the beginning of the region + * @order: the order of the bits to release (number is 1<<order) + * + * This is the complement to __bitmap_find_free_region and releases + * the found region (by clearing it in the bitmap). + */ +void bitmap_release_region(unsigned long *bitmap, int pos, int order) +{ + int pages = 1 << order; + unsigned long mask = (1ul << (pages - 1)); + int index = pos/BITS_PER_LONG; + int offset = pos - (index * BITS_PER_LONG); + mask += mask - 1; + bitmap[index] &= ~(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 index = pos/BITS_PER_LONG; + int offset = pos - (index * BITS_PER_LONG); + + /* 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); + mask += mask - 1; + if (bitmap[index] & (mask << offset)) + return -EBUSY; + bitmap[index] |= (mask << offset); + return 0; +} +EXPORT_SYMBOL(bitmap_allocate_region); |