[TEST PATCH 1/3] lib bitmap region cleanup

[TEST PATCH 1/3] lib bitmap region cleanup

[Paul Jackson]

>From Paul Jackson <pj@sgi.com>

Some code cleanup on the lib/bitmap.c bitmap_*_region() routines:
 * spacing
 * variable names
 * comments

Has no change to code function.

Signed-off-by: Paul Jackson <pj@sgi.com>

---

This compiles, but has not been tested past that.
I am hoping that Paul Mundt will be able to test.

 include/linux/bitmap.h |    3 ++
 lib/bitmap.c           |   57 ++++++++++++++++++++++++++++++-------------------
 2 files changed, 38 insertions(+), 22 deletions(-)

--- 2.6.15-mm2.orig/include/linux/bitmap.h	2006-01-18 23:31:05.859645986 -0800
+++ 2.6.15-mm2/include/linux/bitmap.h	2006-01-18 23:39:53.505381843 -0800
@@ -46,6 +46,9 @@
  * bitmap_parse(ubuf, ulen, dst, nbits)		Parse bitmap dst from user buf
  * bitmap_scnlistprintf(buf, len, src, nbits)	Print bitmap src as list to buf
  * bitmap_parselist(buf, dst, nbits)		Parse bitmap dst from list
+ * bitmap_find_free_region(bitmap, bits, order)	Find and allocate bit region
+ * bitmap_release_region(bitmap, pos, order)	Free specified bit region
+ * bitmap_allocate_region(bitmap, pos, order)	Allocate specified bit region
  */
 
 /*
--- 2.6.15-mm2.orig/lib/bitmap.c	2006-01-18 23:39:46.282642389 -0800
+++ 2.6.15-mm2/lib/bitmap.c	2006-01-18 23:40:23.342639589 -0800
@@ -682,34 +682,34 @@ EXPORT_SYMBOL(bitmap_bitremap);
  *	@bits: number of bits in the bitmap
  *	@order: region size to find (size is actually 1<<order)
  *
- * This is used to allocate a memory region from a bitmap.  The idea is
- * that the region has to be 1<<order sized and 1<<order aligned (this
- * makes the search algorithm much faster).
+ * 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, alligned to that power of two, which
+ * makes the search algorithm much faster.
  *
- * The region is marked as set bits in the bitmap if a free one is
- * found.
+ * Return the bit offset in bitmap of the allocated sequence,
+ * or -errno on failure.
  *
- * Returns either beginning of region or negative error
  */
 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	unsigned long mask;
-	int pages = 1 << order;
+	int nbits = 1 << order;
 	int i;
 
-	if(pages > BITS_PER_LONG)
+	if(nbits > BITS_PER_LONG)
 		return -EINVAL;
 
 	/* make a mask of the order */
-	mask = (1ul << (pages - 1));
+	mask = (1UL << (nbits - 1));
 	mask += mask - 1;
 
-	/* run up the bitmap pages bits at a time */
-	for (i = 0; i < bits; i += pages) {
-		int index = i/BITS_PER_LONG;
+	/* run up the bitmap nbits at a time */
+	for (i = 0; i < bits; i += nbits) {
+		int index = i / BITS_PER_LONG;
 		int offset = i - (index * BITS_PER_LONG);
 		if((bitmap[index] & (mask << offset)) == 0) {
-			/* set region in bimap */
+			/* set region in bitmap */
 			bitmap[index] |= (mask << offset);
 			return i;
 		}
@@ -729,27 +729,40 @@ EXPORT_SYMBOL(bitmap_find_free_region);
  */
 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
 {
-	int pages = 1 << order;
-	unsigned long mask = (1ul << (pages - 1));
-	int index = pos/BITS_PER_LONG;
+	int nbits = 1 << order;
+	unsigned long mask = (1UL << (nbits - 1));
+	int index = pos / BITS_PER_LONG;
 	int offset = pos - (index * BITS_PER_LONG);
+
 	mask += mask - 1;
 	bitmap[index] &= ~(mask << offset);
 }
 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)
+ *
+ * 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 pages = 1 << order;
-	unsigned long mask = (1ul << (pages - 1));
-	int index = pos/BITS_PER_LONG;
+	int nbits = 1 << order;
+	unsigned long mask = (1UL << (nbits - 1));
+	int index = pos / BITS_PER_LONG;
 	int offset = pos - (index * BITS_PER_LONG);
 
-	/* We don't do regions of pages > BITS_PER_LONG.  The
+	/*
+	 * We don't do regions of nbits > BITS_PER_LONG.  The
 	 * algorithm would be a simple look for multiple zeros in the
 	 * array, but there's no driver today that needs this.  If you
-	 * trip this BUG(), you get to code it... */
-	BUG_ON(pages > BITS_PER_LONG);
+	 * trip this BUG(), you get to code it...
+	 */
+	BUG_ON(nbits > BITS_PER_LONG);
 	mask += mask - 1;
 	if (bitmap[index] & (mask << offset))
 		return -EBUSY;

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

[TEST PATCH 2/3] lib bitmap region multiword

[Paul Jackson]

>From Paul Mundt <lethal@linux-sh.org>

Add support to the lib/bitmap.c bitmap_*_region() routines
for bitmap regions larger than one word (nbits > BITS_PER_LONG).
This removes a BUG_ON() in lib bitmap.

I have an updated store queue API for SH that is currently using this
with relative success, and at first glance, it seems like this could be
useful for x86 (arch/i386/kernel/pci-dma.c) as well. Particularly for
anything using dma_declare_coherent_memory() on large areas and that
attempts to allocate large buffers from that space.

Signed-off-by: Paul Mundt <lethal@linux-sh.org>
Signed-off-by: Paul Jackson <pj@sgi.com>

---

This is Mundt's patch, rediffed against a bitmap region cleanup
by myself (pj), with a little tweaking of a variable name.

This compiles, but has never been tested past that.
I am hoping that Paul Mundt will be able to test.

 lib/bitmap.c |  109 ++++++++++++++++++++++++++++++++++++++++-------------------
 1 files changed, 75 insertions(+), 34 deletions(-)

--- 2.6.15-mm2.orig/lib/bitmap.c	2006-01-19 11:46:38.962860359 -0800
+++ 2.6.15-mm2/lib/bitmap.c	2006-01-19 11:47:34.411717879 -0800
@@ -689,30 +689,47 @@ EXPORT_SYMBOL(bitmap_bitremap);
  *
  * Return the bit offset in bitmap of the allocated sequence,
  * or -errno on failure.
- *
  */
 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
-	unsigned long mask;
-	int nbits = 1 << order;
-	int i;
-
-	if(nbits > BITS_PER_LONG)
-		return -EINVAL;
+	int nbits;		/* number of bits in region */
+	int nlongs;		/* 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] */
+	int i;			/* scans bitmap by longs */
+
+	nbits = 1 << order;
+	nlongs = (nbits + (BITS_PER_LONG - 1)) / BITS_PER_LONG;
+	nbitsinlong = nbits;
+	if(nbitsinlong > BITS_PER_LONG)
+		nbitsinlong = BITS_PER_LONG;
 
 	/* make a mask of the order */
-	mask = (1UL << (nbits - 1));
+	mask = (1UL << (nbitsinlong - 1));
 	mask += mask - 1;
 
-	/* run up the bitmap nbits at a time */
-	for (i = 0; i < bits; i += nbits) {
+	/* 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);
-		if((bitmap[index] & (mask << offset)) == 0) {
+		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] |= (mask << offset);
-			return i;
-		}
+			bitmap[index + j] |= (mask << offset);
+
+		return i;
 	}
 	return -ENOMEM;
 }
@@ -729,13 +746,28 @@ EXPORT_SYMBOL(bitmap_find_free_region);
  */
 void bitmap_release_region(unsigned long *bitmap, int pos, int order)
 {
-	int nbits = 1 << order;
-	unsigned long mask = (1UL << (nbits - 1));
-	int index = pos / BITS_PER_LONG;
-	int offset = pos - (index * BITS_PER_LONG);
+	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;
-	bitmap[index] &= ~(mask << offset);
+
+	for (i = 0; i < nlongs; i++)
+		bitmap[index + i] &= ~(mask << offset);
 }
 EXPORT_SYMBOL(bitmap_release_region);
 
@@ -751,22 +783,31 @@ EXPORT_SYMBOL(bitmap_release_region);
  */
 int bitmap_allocate_region(unsigned long *bitmap, int pos, int order)
 {
-	int nbits = 1 << order;
-	unsigned long mask = (1UL << (nbits - 1));
-	int index = pos / BITS_PER_LONG;
-	int offset = pos - (index * BITS_PER_LONG);
-
-	/*
-	 * We don't do regions of nbits > BITS_PER_LONG.  The
-	 * algorithm would be a simple look for multiple zeros in the
-	 * array, but there's no driver today that needs this.  If you
-	 * trip this BUG(), you get to code it...
-	 */
-	BUG_ON(nbits > BITS_PER_LONG);
+	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;
-	if (bitmap[index] & (mask << offset))
-		return -EBUSY;
-	bitmap[index] |= (mask << offset);
+
+	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);
 	return 0;
 }
 EXPORT_SYMBOL(bitmap_allocate_region);

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

[TEST PATCH 3/3] lib bitmap region restructure

[Paul Jackson]

>From Paul Jackson <pj@sgi.com>

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.

Signed-off-by: Paul Jackson <pj@sgi.com>

---

This compiles, but has not been tested past that.
Be more careful of this patch -- unlike the previous
two in this set, this patch reworks quite a bit of
the logic, so is at higher risk of being broken.

 lib/bitmap.c |  199 ++++++++++++++++++++++++++++++-----------------------------
 1 files changed, 102 insertions(+), 97 deletions(-)

--- 2.6.15-mm2.orig/lib/bitmap.c	2006-01-19 16:45:52.421764533 -0800
+++ 2.6.15-mm2/lib/bitmap.c	2006-01-19 17:50:21.692255714 -0800
@@ -676,138 +676,143 @@ int bitmap_bitremap(int oldbit, const un
 }
 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, alligned 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), alligned 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, alligned 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);

-- 
                          I won't rest till it's the best ...
                          Programmer, Linux Scalability
                          Paul Jackson <pj@sgi.com> 1.650.933.1373

Re: [TEST PATCH 3/3] lib bitmap region restructure

[Paul Mundt]

[-- Attachment #1: Type: text/plain, Size: 2441 bytes --]

On Thu, Jan 19, 2006 at 06:08:08PM -0800, Paul Jackson wrote:
> This compiles, but has not been tested past that.
> Be more careful of this patch -- unlike the previous
> two in this set, this patch reworks quite a bit of
> the logic, so is at higher risk of being broken.
> 
The first two work fine for me. This one is another case. With this, the
bitmap_find_free_region() switches to walking the bitmap in 1 << order
steps, as opposed to nbitsperlong, which causes it to skip over more
space than it needs to and we end up fragmenting the bitmap pretty
quickly.

By changing bitmap_find_free_region() back to the previous behaviour, it
seems to work again (at least in the bitmap_find_free_region() case). I
hate to invalidate your comments this quickly, though :-)

Signed-off-by: Paul Mundt <lethal@linux-sh.org>

---

 lib/bitmap.c |   11 ++++++++---
 1 file changed, 8 insertions(+), 3 deletions(-)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 72bd06a..adf336e 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -687,7 +687,7 @@ EXPORT_SYMBOL(bitmap_bitremap);
  * depending on which combination of REG_OP_* flag bits is set.
  *
  * A region of a bitmap is a sequence of bits in the bitmap, of
- * some size '1 << order' (a power of two), alligned to that same
+ * 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).
@@ -760,7 +760,7 @@ done:
  *
  * 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, alligned to that power of two, which
+ * 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,
@@ -768,9 +768,14 @@ done:
  */
 int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
+	int nbits_reg;		/* number of bits in region */
+	int nbitsinlong;	/* num bits of region in each spanned long */
 	int pos;		/* scans bitmap by regions of size order */
 
-	for (pos = 0; pos < bits; pos += (1 << order))
+	nbits_reg = 1 << order;
+	nbitsinlong = min(nbits_reg, BITS_PER_LONG);
+
+	for (pos = 0; pos < bits; pos += nbitsinlong)
 		if (__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			break;
 	if (pos == bits)

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

Re: [TEST PATCH 3/3] lib bitmap region restructure

[Paul Jackson]

Paul - I told Andrew in a side discussion that he can ignore us until we
finished hashing this out.

Once you have something you like, then could you send lkml and Andrew
and the rest of us on the cc list one full set of these patches, in
nicely cleaned up ready to publish form, asking Andrew to take them?

I'll almost certainly agree with any of the variations you are
considering now, and chime in with my "signed-off-by" to your
post.  If you want to get fancy, you can put, on exactly line
one at the top of the patch "From Paul Jackson <pj@sgi.com>"
for those patches that you'd rather I get blamed for than you.

If you decide to change the alignment to at most word boundaries,
instead of the (1 << order) I had for all sizes, then probably best to
redo my patch 3/3 to your choice.  No sense sending in 4 patches,
where patch 4 just reverses a rejected design decision of patch 3.

Paul Mundt wrote:
> bitmap_find_free_region() switches to walking the bitmap in 1 << order
> steps, as opposed to nbitsperlong, which causes it to skip over more
> space than it needs to and we end up fragmenting the bitmap pretty
> quickly

Ah - I guess my problem is that I believed James code comment:

 * This is used to allocate a memory region from a bitmap.  The idea is
 * that the region has to be 1<<order sized and 1<<order aligned (this
 * makes the search algorithm much faster).

I thought this meant that it was a design requirement (the "idea")
to have the alignment always be (1 << order).  Apparently it was
just a useful performance tweak, for the sub-word sizes.

Apparently for the multiword case you are adding, you recommend going
for tighter packing of the allocated regions, rather than extending
the alignment constraint past a single word.

> ... causes it to skip over more
> space than it needs to and we end up fragmenting the bitmap pretty
> quickly.

Just guessing here, since I've no clue what your typical access
pattern is.  But it might actually be that you got less fragmentation
over the long haul with a uniform alignment to (1 << order), than with
an alignment to at most a word boundary.  Certainly as you observed the
early allocations will take more space, but the (1 << order) alignment
seems to nicely mimic a buddy heap, which over an extended period of
insertions and deletions (allocs and frees or whatever) resists
fragmentation rather well.

I actually don't care either way, however.

If you are going with the alignment to at most a word boundary,
rather than uniformly to (1 << order) bits, then could you fix one
more comment, my rephrasing of James initial comment:

 * A region of a bitmap is a sequence of bits in the bitmap, of
 * some size '1 << order' (a power of two), alligned to that same
 * '1 << order' power of two.

After the spelling error you caught, and this restatement of
alignment, this comment should become something like:

 * A region of a bitmap is a sequence of bits in the bitmap, of
 * some size '1 << order' (a power of two).  For regions smaller
 * than one word (namely, if ((1 << order) < BITS_PER_LONG), then
 * the region is aligned to that same '1 << order' power of two.
 * For regions one word or longer in size, the region is aligned
 * to a word boundary ("word" being unsigned long).

Hmmm ... one more comment needs the same treatment.

My comment:

 * 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, alligned to that power of two, which
 * makes the search algorithm much faster.

would become something like:

 * 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 either that power of two, or to
 * word boundaries, whichever is smaller.

If you're going to change this alignment to be at most to a word
boundary, then read over my code carefully, in patch 3/3, looking
for any other places where I assumed the (1 << order) alignment.

There is one possible performance hit with this changed alignment.

The performance of bitmap_find_free_region() becomes essentially
O(N**2) rather than O(Log2 N).  The search loop would scan forward
with REG_OP_ISFREE from each word in succession, until it found
the requested sequence of free words, rather than scanning just
from the words on (1 << order) bits alignment.  Since it looks in
more places, the worst case times are longer.

-- 
                  I won't rest till it's the best ...
                  Programmer, Linux Scalability
                  Paul Jackson <pj@sgi.com> 1.925.600.0401

Re: [TEST PATCH 3/3] lib bitmap region restructure

[Paul Mundt]

[-- Attachment #1: Type: text/plain, Size: 2708 bytes --]

On Fri, Jan 20, 2006 at 01:56:43AM -0800, Paul Jackson wrote:
> Ah - I guess my problem is that I believed James code comment:
> 
>  * This is used to allocate a memory region from a bitmap.  The idea is
>  * that the region has to be 1<<order sized and 1<<order aligned (this
>  * makes the search algorithm much faster).
> 
> I thought this meant that it was a design requirement (the "idea")
> to have the alignment always be (1 << order).  Apparently it was
> just a useful performance tweak, for the sub-word sizes.
> 
> Apparently for the multiword case you are adding, you recommend going
> for tighter packing of the allocated regions, rather than extending
> the alignment constraint past a single word.
> 
From a performance point of view going the (1 << order) route for
alignment and searching is much faster. I'm not too tightly bound to the
notion of tightly packing the allocated regions, that was just the
behaviour my implementation was following originally.

Speeding up the searches should take priority for this, though I expect
there's going to be very few corner cases where the search time is of
real relevance (primarily given the fact that it can only handle the <=
BITS_PER_LONG case now).

To give you an example of my use case, I have a 64MB chunk of address
space at a fixed virtual range in the SH-4 processors, which can be
accessed by both the kernel and userspace (unfortunately the address
range is in the mapped peripheral space, which exceeds TASK_SIZE, so
relying even on a custom ->get_unmapped_area() to prep the VMA location
and ->mmap() to setup the mappings simply isn't going to work).

Based off of this, I've got a bitmap for covering this space that both
the kernel and userspace interfaces hook in to to carve up the address
space amongst themselves, and it's not uncommon to map large memory
apertures (32M or so) through this space all at once, particularly in the
case where VRAM is remapped to parallelize with DMA for faster
throughput.

> The performance of bitmap_find_free_region() becomes essentially
> O(N**2) rather than O(Log2 N).  The search loop would scan forward
> with REG_OP_ISFREE from each word in succession, until it found
> the requested sequence of free words, rather than scanning just
> from the words on (1 << order) bits alignment.  Since it looks in
> more places, the worst case times are longer.
> 
Yes, I think given this your patch 3/3 should be mostly fine as is. I've
gotten around to testing it in practice now and everything seems to hold
up. I'll clean up the comments a bit and submit the patch set to Andrew,
who I'm sure is rather tired of hearing about this by now :-)

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]