diff options
Diffstat (limited to 'lib')
-rw-r--r-- | lib/bitmap.c | 199 |
1 files changed, 102 insertions, 97 deletions
diff --git a/lib/bitmap.c b/lib/bitmap.c index f49eabe09271..8acab0e176ef 100644 --- a/lib/bitmap.c +++ b/lib/bitmap.c | |||
@@ -676,138 +676,143 @@ int bitmap_bitremap(int oldbit, const unsigned long *old, | |||
676 | } | 676 | } |
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 | * Common code for bitmap_*_region() routines. |
681 | * @bitmap: an array of unsigned longs corresponding to the bitmap | 681 | * bitmap: array of unsigned longs corresponding to the bitmap |
682 | * @bits: number of bits in the bitmap | 682 | * pos: the beginning of the region |
683 | * @order: region size to find (size is actually 1<<order) | 683 | * order: region size (log base 2 of number of bits) |
684 | * reg_op: operation(s) to perform on that region of bitmap | ||
684 | * | 685 | * |
685 | * Find a sequence of free (zero) bits in a bitmap and allocate | 686 | * Can set, verify and/or release a region of bits in a bitmap, |
686 | * them (set them to one). Only consider sequences of length a | 687 | * depending on which combination of REG_OP_* flag bits is set. |
687 | * power ('order') of two, aligned to that power of two, which | ||
688 | * makes the search algorithm much faster. | ||
689 | * | 688 | * |
690 | * Return the bit offset in bitmap of the allocated sequence, | 689 | * A region of a bitmap is a sequence of bits in the bitmap, of |
691 | * or -errno on failure. | 690 | * some size '1 << order' (a power of two), aligned to that same |
691 | * '1 << order' power of two. | ||
692 | * | ||
693 | * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits). | ||
694 | * Returns 0 in all other cases and reg_ops. | ||
692 | */ | 695 | */ |
693 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | 696 | |
697 | enum { | ||
698 | REG_OP_ISFREE, /* true if region is all zero bits */ | ||
699 | REG_OP_ALLOC, /* set all bits in region */ | ||
700 | REG_OP_RELEASE, /* clear all bits in region */ | ||
701 | }; | ||
702 | |||
703 | static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op) | ||
694 | { | 704 | { |
695 | int nbits; /* number of bits in region */ | 705 | int nbits_reg; /* number of bits in region */ |
696 | int nlongs; /* num longs spanned by region in bitmap */ | 706 | int index; /* index first long of region in bitmap */ |
707 | int offset; /* bit offset region in bitmap[index] */ | ||
708 | int nlongs_reg; /* num longs spanned by region in bitmap */ | ||
697 | int nbitsinlong; /* num bits of region in each spanned long */ | 709 | int nbitsinlong; /* num bits of region in each spanned long */ |
698 | unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ | 710 | unsigned long mask; /* bitmask for one long of region */ |
699 | int i; /* scans bitmap by longs */ | 711 | int i; /* scans bitmap by longs */ |
712 | int ret = 0; /* return value */ | ||
700 | 713 | ||
701 | nbits = 1 << order; | 714 | /* |
702 | nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; | 715 | * Either nlongs_reg == 1 (for small orders that fit in one long) |
703 | nbitsinlong = nbits; | 716 | * or (offset == 0 && mask == ~0UL) (for larger multiword orders.) |
704 | if (nbitsinlong > BITS_PER_LONG) | 717 | */ |
705 | nbitsinlong = BITS_PER_LONG; | 718 | nbits_reg = 1 << order; |
719 | index = pos / BITS_PER_LONG; | ||
720 | offset = pos - (index * BITS_PER_LONG); | ||
721 | nlongs_reg = BITS_TO_LONGS(nbits_reg); | ||
722 | nbitsinlong = min(nbits_reg, BITS_PER_LONG); | ||
706 | 723 | ||
707 | /* make a mask of the order */ | 724 | /* |
725 | * Can't do "mask = (1UL << nbitsinlong) - 1", as that | ||
726 | * overflows if nbitsinlong == BITS_PER_LONG. | ||
727 | */ | ||
708 | mask = (1UL << (nbitsinlong - 1)); | 728 | mask = (1UL << (nbitsinlong - 1)); |
709 | mask += mask - 1; | 729 | mask += mask - 1; |
730 | mask <<= offset; | ||
710 | 731 | ||
711 | /* run up the bitmap nbitsinlong at a time */ | 732 | switch (reg_op) { |
712 | for (i = 0; i < bits; i += nbitsinlong) { | 733 | case REG_OP_ISFREE: |
713 | int index = i / BITS_PER_LONG; | 734 | for (i = 0; i < nlongs_reg; i++) { |
714 | int offset = i - (index * BITS_PER_LONG); | 735 | if (bitmap[index + i] & mask) |
715 | int j, space = 1; | 736 | goto done; |
716 | 737 | } | |
717 | /* find space in the bitmap */ | 738 | ret = 1; /* all bits in region free (zero) */ |
718 | for (j = 0; j < nlongs; j++) | 739 | break; |
719 | if ((bitmap[index + j] & (mask << offset))) { | 740 | |
720 | space = 0; | 741 | case REG_OP_ALLOC: |
721 | break; | 742 | for (i = 0; i < nlongs_reg; i++) |
722 | } | 743 | bitmap[index + i] |= mask; |
723 | 744 | break; | |
724 | /* keep looking */ | 745 | |
725 | if (unlikely(!space)) | 746 | case REG_OP_RELEASE: |
726 | continue; | 747 | for (i = 0; i < nlongs_reg; i++) |
727 | 748 | bitmap[index + i] &= ~mask; | |
728 | for (j = 0; j < nlongs; j++) | 749 | break; |
729 | /* set region in bitmap */ | ||
730 | bitmap[index + j] |= (mask << offset); | ||
731 | |||
732 | return i; | ||
733 | } | 750 | } |
734 | return -ENOMEM; | 751 | done: |
752 | return ret; | ||
753 | } | ||
754 | |||
755 | /** | ||
756 | * bitmap_find_free_region - find a contiguous aligned mem region | ||
757 | * @bitmap: array of unsigned longs corresponding to the bitmap | ||
758 | * @bits: number of bits in the bitmap | ||
759 | * @order: region size (log base 2 of number of bits) to find | ||
760 | * | ||
761 | * Find a region of free (zero) bits in a @bitmap of @bits bits and | ||
762 | * allocate them (set them to one). Only consider regions of length | ||
763 | * a power (@order) of two, aligned to that power of two, which | ||
764 | * makes the search algorithm much faster. | ||
765 | * | ||
766 | * Return the bit offset in bitmap of the allocated region, | ||
767 | * or -errno on failure. | ||
768 | */ | ||
769 | int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) | ||
770 | { | ||
771 | int pos; /* scans bitmap by regions of size order */ | ||
772 | |||
773 | for (pos = 0; pos < bits; pos += (1 << order)) | ||
774 | if (__reg_op(bitmap, pos, order, REG_OP_ISFREE)) | ||
775 | break; | ||
776 | if (pos == bits) | ||
777 | return -ENOMEM; | ||
778 | __reg_op(bitmap, pos, order, REG_OP_ALLOC); | ||
779 | return pos; | ||
735 | } | 780 | } |
736 | EXPORT_SYMBOL(bitmap_find_free_region); | 781 | EXPORT_SYMBOL(bitmap_find_free_region); |
737 | 782 | ||
738 | /** | 783 | /** |
739 | * bitmap_release_region - release allocated bitmap region | 784 | * bitmap_release_region - release allocated bitmap region |
740 | * @bitmap: a pointer to the bitmap | 785 | * @bitmap: array of unsigned longs corresponding to the bitmap |
741 | * @pos: the beginning of the region | 786 | * @pos: beginning of bit region to release |
742 | * @order: the order of the bits to release (number is 1<<order) | 787 | * @order: region size (log base 2 of number of bits) to release |
743 | * | 788 | * |
744 | * This is the complement to __bitmap_find_free_region and releases | 789 | * This is the complement to __bitmap_find_free_region and releases |
745 | * the found region (by clearing it in the bitmap). | 790 | * the found region (by clearing it in the bitmap). |
791 | * | ||
792 | * No return value. | ||
746 | */ | 793 | */ |
747 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) | 794 | void bitmap_release_region(unsigned long *bitmap, int pos, int order) |
748 | { | 795 | { |
749 | int nbits; /* number of bits in region */ | 796 | __reg_op(bitmap, pos, order, REG_OP_RELEASE); |
750 | int nlongs; /* num longs spanned by region in bitmap */ | ||
751 | int index; /* index first long of region in bitmap */ | ||
752 | int offset; /* bit offset region in bitmap[index] */ | ||
753 | int nbitsinlong; /* num bits of region in each spanned long */ | ||
754 | unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ | ||
755 | int i; /* scans bitmap by longs */ | ||
756 | |||
757 | nbits = 1 << order; | ||
758 | nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; | ||
759 | index = pos / BITS_PER_LONG; | ||
760 | offset = pos - (index * BITS_PER_LONG); | ||
761 | |||
762 | nbitsinlong = nbits; | ||
763 | if (nbitsinlong > BITS_PER_LONG) | ||
764 | nbitsinlong = BITS_PER_LONG; | ||
765 | |||
766 | mask = (1UL << (nbitsinlong - 1)); | ||
767 | mask += mask - 1; | ||
768 | |||
769 | for (i = 0; i < nlongs; i++) | ||
770 | bitmap[index + i] &= ~(mask << offset); | ||
771 | } | 797 | } |
772 | EXPORT_SYMBOL(bitmap_release_region); | 798 | EXPORT_SYMBOL(bitmap_release_region); |
773 | 799 | ||
774 | /** | 800 | /** |
775 | * bitmap_allocate_region - allocate bitmap region | 801 | * bitmap_allocate_region - allocate bitmap region |
776 | * @bitmap: a pointer to the bitmap | 802 | * @bitmap: array of unsigned longs corresponding to the bitmap |
777 | * @pos: the beginning of the region | 803 | * @pos: beginning of bit region to allocate |
778 | * @order: the order of the bits to allocate (number is 1<<order) | 804 | * @order: region size (log base 2 of number of bits) to allocate |
779 | * | 805 | * |
780 | * Allocate (set bits in) a specified region of a bitmap. | 806 | * Allocate (set bits in) a specified region of a bitmap. |
807 | * | ||
781 | * Return 0 on success, or -EBUSY if specified region wasn't | 808 | * Return 0 on success, or -EBUSY if specified region wasn't |
782 | * free (not all bits were zero). | 809 | * free (not all bits were zero). |
783 | */ | 810 | */ |
784 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) | 811 | int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) |
785 | { | 812 | { |
786 | int nbits; /* number of bits in region */ | 813 | if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE)) |
787 | int nlongs; /* num longs spanned by region in bitmap */ | 814 | return -EBUSY; |
788 | int index; /* index first long of region in bitmap */ | 815 | __reg_op(bitmap, pos, order, REG_OP_ALLOC); |
789 | int offset; /* bit offset region in bitmap[index] */ | ||
790 | int nbitsinlong; /* num bits of region in each spanned long */ | ||
791 | unsigned long mask; /* bitmask of bits [0 .. nbitsinlong-1] */ | ||
792 | int i; /* scans bitmap by longs */ | ||
793 | |||
794 | nbits = 1 << order; | ||
795 | nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG; | ||
796 | index = pos / BITS_PER_LONG; | ||
797 | offset = pos - (index * BITS_PER_LONG); | ||
798 | |||
799 | nbitsinlong = nbits; | ||
800 | if (nbitsinlong > BITS_PER_LONG) | ||
801 | nbitsinlong = BITS_PER_LONG; | ||
802 | |||
803 | mask = (1UL << (nbitsinlong - 1)); | ||
804 | mask += mask - 1; | ||
805 | |||
806 | for (i = 0; i < nlongs; i++) | ||
807 | if (bitmap[index + i] & (mask << offset)) | ||
808 | return -EBUSY; | ||
809 | for (i = 0; i < nlongs; i++) | ||
810 | bitmap[index + i] |= (mask << offset); | ||
811 | return 0; | 816 | return 0; |
812 | } | 817 | } |
813 | EXPORT_SYMBOL(bitmap_allocate_region); | 818 | EXPORT_SYMBOL(bitmap_allocate_region); |