aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-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;