diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/bitmap.c | 64 |
1 files changed, 38 insertions, 26 deletions
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, | |||
677 | EXPORT_SYMBOL(bitmap_bitremap); | 677 | EXPORT_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 | */ |
694 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | 693 | int 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) | |||
719 | EXPORT_SYMBOL(bitmap_find_free_region); | 718 | EXPORT_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 | */ |
730 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) | 729 | void 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 | } |
739 | EXPORT_SYMBOL(bitmap_release_region); | 739 | EXPORT_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 | */ | ||
741 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) | 751 | int 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; |