X-Git-Url: http://git.rot13.org/?a=blobdiff_plain;f=lib%2Fbitmap.c;h=ed2ae3b0cd066244b1ddef1dc3345bbe582247d1;hb=8c33fd11e3a21a15af35b5831f1516faf53094f1;hp=f49eabe09271304ccc9b5adedf1ba13b6a8a058e;hpb=74373c6acc52450ced28780d5fece60f1d7d20aa;p=powerpc.git

diff --git a/lib/bitmap.c b/lib/bitmap.c
index f49eabe092..ed2ae3b0cd 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -253,33 +253,18 @@ int __bitmap_subset(const unsigned long *bitmap1,
 }
 EXPORT_SYMBOL(__bitmap_subset);
 
-#if BITS_PER_LONG == 32
 int __bitmap_weight(const unsigned long *bitmap, int bits)
 {
 	int k, w = 0, lim = bits/BITS_PER_LONG;
 
 	for (k = 0; k < lim; k++)
-		w += hweight32(bitmap[k]);
+		w += hweight_long(bitmap[k]);
 
 	if (bits % BITS_PER_LONG)
-		w += hweight32(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
+		w += hweight_long(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
 
 	return w;
 }
-#else
-int __bitmap_weight(const unsigned long *bitmap, int bits)
-{
-	int k, w = 0, lim = bits/BITS_PER_LONG;
-
-	for (k = 0; k < lim; k++)
-		w += hweight64(bitmap[k]);
-
-	if (bits % BITS_PER_LONG)
-		w += hweight64(bitmap[k] & BITMAP_LAST_WORD_MASK(bits));
-
-	return w;
-}
-#endif
 EXPORT_SYMBOL(__bitmap_weight);
 
 /*
@@ -676,138 +661,143 @@ int bitmap_bitremap(int oldbit, const unsigned long *old,
 }
 EXPORT_SYMBOL(bitmap_bitremap);
 
-/**
- * bitmap_find_free_region - find a contiguous aligned mem region
- *	@bitmap: an array of unsigned longs corresponding to the bitmap
- *	@bits: number of bits in the bitmap
- *	@order: region size to find (size is actually 1<<order)
+/*
+ * Common code for bitmap_*_region() routines.
+ *	bitmap: array of unsigned longs corresponding to the bitmap
+ *	pos: the beginning of the region
+ *	order: region size (log base 2 of number of bits)
+ *	reg_op: operation(s) to perform on that region of bitmap
  *
- * Find a sequence of free (zero) bits in a bitmap and allocate
- * them (set them to one).  Only consider sequences of length a
- * power ('order') of two, aligned to that power of two, which
- * makes the search algorithm much faster.
+ * Can set, verify and/or release a region of bits in a bitmap,
+ * depending on which combination of REG_OP_* flag bits is set.
  *
- * Return the bit offset in bitmap of the allocated sequence,
- * or -errno on failure.
+ * A region of a bitmap is a sequence of bits in the bitmap, of
+ * some size '1 << order' (a power of two), aligned to that same
+ * '1 << order' power of two.
+ *
+ * Returns 1 if REG_OP_ISFREE succeeds (region is all zero bits).
+ * Returns 0 in all other cases and reg_ops.
  */
-int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
+
+enum {
+	REG_OP_ISFREE,		/* true if region is all zero bits */
+	REG_OP_ALLOC,		/* set all bits in region */
+	REG_OP_RELEASE,		/* clear all bits in region */
+};
+
+static int __reg_op(unsigned long *bitmap, int pos, int order, int reg_op)
 {
-	int nbits;		/* number of bits in region */
-	int nlongs;		/* num longs spanned by region in bitmap */
+	int nbits_reg;		/* number of bits in region */
+	int index;		/* index first long of region in bitmap */
+	int offset;		/* bit offset region in bitmap[index] */
+	int nlongs_reg;		/* num longs spanned by region in bitmap */
 	int nbitsinlong;	/* num bits of region in each spanned long */
-	unsigned long mask;	/* bitmask of bits [0 .. nbitsinlong-1] */
+	unsigned long mask;	/* bitmask for one long of region */
 	int i;			/* scans bitmap by longs */
+	int ret = 0;		/* return value */
 
-	nbits = 1 << order;
-	nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
-	nbitsinlong = nbits;
-	if (nbitsinlong > BITS_PER_LONG)
-		nbitsinlong = BITS_PER_LONG;
+	/*
+	 * Either nlongs_reg == 1 (for small orders that fit in one long)
+	 * or (offset == 0 && mask == ~0UL) (for larger multiword orders.)
+	 */
+	nbits_reg = 1 << order;
+	index = pos / BITS_PER_LONG;
+	offset = pos - (index * BITS_PER_LONG);
+	nlongs_reg = BITS_TO_LONGS(nbits_reg);
+	nbitsinlong = min(nbits_reg,  BITS_PER_LONG);
 
-	/* make a mask of the order */
+	/*
+	 * Can't do "mask = (1UL << nbitsinlong) - 1", as that
+	 * overflows if nbitsinlong == BITS_PER_LONG.
+	 */
 	mask = (1UL << (nbitsinlong - 1));
 	mask += mask - 1;
+	mask <<= offset;
 
-	/* run up the bitmap nbitsinlong at a time */
-	for (i = 0; i < bits; i += nbitsinlong) {
-		int index = i / BITS_PER_LONG;
-		int offset = i - (index * BITS_PER_LONG);
-		int j, space = 1;
-
-		/* find space in the bitmap */
-		for (j = 0; j < nlongs; j++)
-			if ((bitmap[index + j] & (mask << offset))) {
-				space = 0;
-				break;
-			}
-
-		/* keep looking */
-		if (unlikely(!space))
-			continue;
-
-		for (j = 0; j < nlongs; j++)
-			/* set region in bitmap */
-			bitmap[index + j] |= (mask << offset);
-
-		return i;
+	switch (reg_op) {
+	case REG_OP_ISFREE:
+		for (i = 0; i < nlongs_reg; i++) {
+			if (bitmap[index + i] & mask)
+				goto done;
+		}
+		ret = 1;	/* all bits in region free (zero) */
+		break;
+
+	case REG_OP_ALLOC:
+		for (i = 0; i < nlongs_reg; i++)
+			bitmap[index + i] |= mask;
+		break;
+
+	case REG_OP_RELEASE:
+		for (i = 0; i < nlongs_reg; i++)
+			bitmap[index + i] &= ~mask;
+		break;
 	}
-	return -ENOMEM;
+done:
+	return ret;
+}
+
+/**
+ * bitmap_find_free_region - find a contiguous aligned mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *	@order: region size (log base 2 of number of bits) to find
+ *
+ * Find a region of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).  Only consider regions of length
+ * a power (@order) of two, aligned to that power of two, which
+ * makes the search algorithm much faster.
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
+{
+	int pos;		/* scans bitmap by regions of size order */
+
+	for (pos = 0; pos < bits; pos += (1 << order))
+		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+			break;
+	if (pos == bits)
+		return -ENOMEM;
+	__reg_op(bitmap, pos, order, REG_OP_ALLOC);
+	return pos;
 }
 EXPORT_SYMBOL(bitmap_find_free_region);
 
 /**
  * bitmap_release_region - release allocated bitmap region
- *	@bitmap: a pointer to the bitmap
- *	@pos: the beginning of the region
- *	@order: the order of the bits to release (number is 1<<order)
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@pos: beginning of bit region to release
+ *	@order: region size (log base 2 of number of bits) to release
  *
  * This is the complement to __bitmap_find_free_region and releases
  * the found region (by clearing it in the bitmap).
+ *
+ * No return value.
  */
 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
 {
-	int nbits;		/* number of bits in region */
-	int nlongs;		/* num longs spanned by region in bitmap */
-	int index;		/* index first long of region in bitmap */
-	int offset;		/* bit offset region in bitmap[index] */
-	int nbitsinlong;	/* num bits of region in each spanned long */
-	unsigned long mask;	/* bitmask of bits [0 .. nbitsinlong-1] */
-	int i;			/* scans bitmap by longs */
-
-	nbits = 1 << order;
-	nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
-	index = pos / BITS_PER_LONG;
-	offset = pos - (index * BITS_PER_LONG);
-
-	nbitsinlong = nbits;
-	if (nbitsinlong > BITS_PER_LONG)
-		nbitsinlong = BITS_PER_LONG;
-
-	mask = (1UL << (nbitsinlong - 1));
-	mask += mask - 1;
-
-	for (i = 0; i < nlongs; i++)
-		bitmap[index + i] &= ~(mask << offset);
+	__reg_op(bitmap, pos, order, REG_OP_RELEASE);
 }
 EXPORT_SYMBOL(bitmap_release_region);
 
 /**
  * bitmap_allocate_region - allocate bitmap region
- *	@bitmap: a pointer to the bitmap
- *	@pos: the beginning of the region
- *	@order: the order of the bits to allocate (number is 1<<order)
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@pos: beginning of bit region to allocate
+ *	@order: region size (log base 2 of number of bits) to allocate
  *
  * Allocate (set bits in) a specified region of a bitmap.
+ *
  * Return 0 on success, or -EBUSY if specified region wasn't
  * free (not all bits were zero).
  */
 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 {
-	int nbits;		/* number of bits in region */
-	int nlongs;		/* num longs spanned by region in bitmap */
-	int index;		/* index first long of region in bitmap */
-	int offset;		/* bit offset region in bitmap[index] */
-	int nbitsinlong;	/* num bits of region in each spanned long */
-	unsigned long mask;	/* bitmask of bits [0 .. nbitsinlong-1] */
-	int i;			/* scans bitmap by longs */
-
-	nbits = 1 << order;
-	nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
-	index = pos / BITS_PER_LONG;
-	offset = pos - (index * BITS_PER_LONG);
-
-	nbitsinlong = nbits;
-	if (nbitsinlong > BITS_PER_LONG)
-		nbitsinlong = BITS_PER_LONG;
-
-	mask = (1UL << (nbitsinlong - 1));
-	mask += mask - 1;
-
-	for (i = 0; i < nlongs; i++)
-		if (bitmap[index + i] & (mask << offset))
-			return -EBUSY;
-	for (i = 0; i < nlongs; i++)
-		bitmap[index + i] |= (mask << offset);
+	if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
+		return -EBUSY;
+	__reg_op(bitmap, pos, order, REG_OP_ALLOC);
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_allocate_region);