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

[Paul Mundt]

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@xxxxxxxxxxxx>

---

 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: pgp00000.pgp
Description: PGP signature