aboutsummaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorPaul Jackson <pj@sgi.com>2006-03-24 06:15:46 -0500
committerLinus Torvalds <torvalds@g5.osdl.org>2006-03-24 10:33:20 -0500
commit3cf64b933c90ba701cfdc7188431104c646d7c9e (patch)
treea51cd036519cfddc1235b7023320c0dc53939432
parent74373c6acc52450ced28780d5fece60f1d7d20aa (diff)
[PATCH] bitmap: region restructuring
Restructure the bitmap_*_region() operations, to avoid code duplication. Also reduces binary text size by about 100 bytes (ia64 arch). The original Bottomley bitmap_*_region patch added about 1000 bytes of compiled kernel text (ia64). The Mundt multiword extension added another 600 bytes, and this restructuring patch gets back about 100 bytes. But the real motivation was the reduced amount of duplicated code. Tested by Paul Mundt using <= BITS_PER_LONG as well as power of 2 aligned multiword spanning allocations. 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--lib/bitmap.c199
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}
677EXPORT_SYMBOL(bitmap_bitremap); 677EXPORT_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 */
693int bitmap_find_free_region(unsigned long *bitmap, int bits, int order) 696
697enum {
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
703static 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; 751done:
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 */
769int 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}
736EXPORT_SYMBOL(bitmap_find_free_region); 781EXPORT_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 */
747void bitmap_release_region(unsigned long *bitmap, int pos, int order) 794void 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}
772EXPORT_SYMBOL(bitmap_release_region); 798EXPORT_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 */
784int bitmap_allocate_region(unsigned long *bitmap, int pos, int order) 811int 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}
813EXPORT_SYMBOL(bitmap_allocate_region); 818EXPORT_SYMBOL(bitmap_allocate_region);