aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorPaul Jackson <pj@sgi.com>2006-03-24 06:15:44 -0500
committerLinus Torvalds <torvalds@g5.osdl.org>2006-03-24 10:33:20 -0500
commit87e24802586333fa861861f6493c76039872755b (patch)
tree631a252da4716798027cd96b4529351e601c50c6
parentf993b3bf80b23d329951fe0fc5ba3647d5d912e9 (diff)
[PATCH] bitmap: region cleanup
Paul Mundt <lethal@linux-sh.org> says: This patch set implements a number of patches to clean up and restructure the bitmap region code, in addition to extending the interface to support multiword spanning allocations. The current implementation (before this patch set) is limited by only being able to allocate pages <= BITS_PER_LONG, as noted by the strategically positioned BUG_ON() at lib/bitmap.c:752: /* 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); As I seem to have been the first person to trigger this, the result ends up being the following patch set with the help of Paul Jackson. The final patch in the series eliminates quite a bit of code duplication, so the bitmap code size ends up being smaller than the current implementation as an added bonus. After these are applied, it should already be possible to do multiword allocations with dma_alloc_coherent() out of ranges established by dma_declare_coherent_memory() on x86 without having to change any of the code, and the SH store queue API will follow up on this as the other user that needs support for this. This patch: Some code cleanup on the lib/bitmap.c bitmap_*_region() routines: * spacing * variable names * comments Has no change to code function. 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>
-rw-r--r--include/linux/bitmap.h3
-rw-r--r--lib/bitmap.c64
2 files changed, 41 insertions, 26 deletions
diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 7d8ff97b3e92..d9ed27969855 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -46,6 +46,9 @@
46 * bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf 46 * bitmap_parse(ubuf, ulen, dst, nbits) Parse bitmap dst from user buf
47 * bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf 47 * bitmap_scnlistprintf(buf, len, src, nbits) Print bitmap src as list to buf
48 * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from list 48 * bitmap_parselist(buf, dst, nbits) Parse bitmap dst from list
49 * bitmap_find_free_region(bitmap, bits, order) Find and allocate bit region
50 * bitmap_release_region(bitmap, pos, order) Free specified bit region
51 * bitmap_allocate_region(bitmap, pos, order) Allocate specified bit region
49 */ 52 */
50 53
51/* 54/*
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 48e708381d44..3fab1ce9ac65 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -677,39 +677,38 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
677EXPORT_SYMBOL(bitmap_bitremap); 677EXPORT_SYMBOL(bitmap_bitremap);
678 678
679/** 679/**
680 * bitmap_find_free_region - find a contiguous aligned mem region 680 * bitmap_find_free_region - find a contiguous aligned mem region
681 * @bitmap: an array of unsigned longs corresponding to the bitmap 681 * @bitmap: an array of unsigned longs corresponding to the bitmap
682 * @bits: number of bits in the bitmap 682 * @bits: number of bits in the bitmap
683 * @order: region size to find (size is actually 1<<order) 683 * @order: region size to find (size is actually 1<<order)
684 * 684 *
685 * This is used to allocate a memory region from a bitmap. The idea is 685 * Find a sequence of free (zero) bits in a bitmap and allocate
686 * that the region has to be 1<<order sized and 1<<order aligned (this 686 * them (set them to one). Only consider sequences of length a
687 * makes the search algorithm much faster). 687 * power ('order') of two, aligned to that power of two, which
688 * makes the search algorithm much faster.
688 * 689 *
689 * The region is marked as set bits in the bitmap if a free one is 690 * Return the bit offset in bitmap of the allocated sequence,
690 * found. 691 * or -errno on failure.
691 *
692 * Returns either beginning of region or negative error
693 */ 692 */
694int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 693int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
695{ 694{
696 unsigned long mask; 695 unsigned long mask;
697 int pages = 1 << order; 696 int nbits = 1 << order;
698 int i; 697 int i;
699 698
700 if(pages > BITS_PER_LONG) 699 if (nbits > BITS_PER_LONG)
701 return -EINVAL; 700 return -EINVAL;
702 701
703 /* make a mask of the order */ 702 /* make a mask of the order */
704 mask = (1ul << (pages - 1)); 703 mask = (1UL << (nbits - 1));
705 mask += mask - 1; 704 mask += mask - 1;
706 705
707 /* run up the bitmap pages bits at a time */ 706 /* run up the bitmap nbits at a time */
708 for (i = 0; i < bits; i += pages) { 707 for (i = 0; i < bits; i += nbits) {
709 int index = i/BITS_PER_LONG; 708 int index = i / BITS_PER_LONG;
710 int offset = i - (index * BITS_PER_LONG); 709 int offset = i - (index * BITS_PER_LONG);
711 if((bitmap[index] & (mask << offset)) == 0) { 710 if ((bitmap[index] & (mask << offset)) == 0) {
712 /* set region in bimap */ 711 /* set region in bitmap */
713 bitmap[index] |= (mask << offset); 712 bitmap[index] |= (mask << offset);
714 return i; 713 return i;
715 } 714 }
@@ -719,7 +718,7 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
719EXPORT_SYMBOL(bitmap_find_free_region); 718EXPORT_SYMBOL(bitmap_find_free_region);
720 719
721/** 720/**
722 * bitmap_release_region - release allocated bitmap region 721 * bitmap_release_region - release allocated bitmap region
723 * @bitmap: a pointer to the bitmap 722 * @bitmap: a pointer to the bitmap
724 * @pos: the beginning of the region 723 * @pos: the beginning of the region
725 * @order: the order of the bits to release (number is 1<<order) 724 * @order: the order of the bits to release (number is 1<<order)
@@ -729,27 +728,40 @@ EXPORT_SYMBOL(bitmap_find_free_region);
729 */ 728 */
730void bitmap_release_region(unsigned long *bitmap, int pos, int order) 729void bitmap_release_region(unsigned long *bitmap, int pos, int order)
731{ 730{
732 int pages = 1 << order; 731 int nbits = 1 << order;
733 unsigned long mask = (1ul << (pages - 1)); 732 unsigned long mask = (1UL << (nbits - 1));
734 int index = pos/BITS_PER_LONG; 733 int index = pos / BITS_PER_LONG;
735 int offset = pos - (index * BITS_PER_LONG); 734 int offset = pos - (index * BITS_PER_LONG);
735
736 mask += mask - 1; 736 mask += mask - 1;
737 bitmap[index] &= ~(mask << offset); 737 bitmap[index] &= ~(mask << offset);
738} 738}
739EXPORT_SYMBOL(bitmap_release_region); 739EXPORT_SYMBOL(bitmap_release_region);
740 740
741/**
742 * bitmap_allocate_region - allocate bitmap region
743 * @bitmap: a pointer to the bitmap
744 * @pos: the beginning of the region
745 * @order: the order of the bits to allocate (number is 1<<order)
746 *
747 * Allocate (set bits in) a specified region of a bitmap.
748 * Return 0 on success, or -EBUSY if specified region wasn't
749 * free (not all bits were zero).
750 */
741int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 751int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
742{ 752{
743 int pages = 1 << order; 753 int nbits = 1 << order;
744 unsigned long mask = (1ul << (pages - 1)); 754 unsigned long mask = (1UL << (nbits - 1));
745 int index = pos/BITS_PER_LONG; 755 int index = pos / BITS_PER_LONG;
746 int offset = pos - (index * BITS_PER_LONG); 756 int offset = pos - (index * BITS_PER_LONG);
747 757
748 /* We don't do regions of pages > BITS_PER_LONG. The 758 /*
759 * We don't do regions of nbits > BITS_PER_LONG. The
749 * algorithm would be a simple look for multiple zeros in the 760 * algorithm would be a simple look for multiple zeros in the
750 * array, but there's no driver today that needs this. If you 761 * array, but there's no driver today that needs this. If you
751 * trip this BUG(), you get to code it... */ 762 * trip this BUG(), you get to code it...
752 BUG_ON(pages > BITS_PER_LONG); 763 */
764 BUG_ON(nbits > BITS_PER_LONG);
753 mask += mask - 1; 765 mask += mask - 1;
754 if (bitmap[index] & (mask << offset)) 766 if (bitmap[index] & (mask << offset))
755 return -EBUSY; 767 return -EBUSY;