Skip to contentSkip to conversation

bitmap: speedup in bitmap_find_free_region when order is 0

PATCH Superseded Chanho Min 3 participants 3 messages Apr 8, 2013

Subsystems (2)

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore

Chanho Min

author
#0 lore raw

PATCH 1/1 bitmap: speedup in bitmap_find_free_region when order is 0

If bitmap_find_free_region() is called with order=0, We can reduce for-loops to find 1 free bit. First, It scans bitmap array by the increment of long type, then find 1 free bit within 1 long type value.

In 32 bits system and 1024 bits size, in the worst case, We need 1024 for-loops to find 1 free bit. But, If This is applied, it takes 64 for-loops. Instead, if free bit is in the first index of the bitmaps, It will be needed additional 1 for-loop. But from second index, It will be speed up significantly.

---
 lib/bitmap.c |   34 ++++++++++++++++++++++++++++++++++
 1 file changed, 34 insertions(+)
lib/bitmap.c +34 -0
index 06f7e4f..0c1f03a 100644
@@ -1099,6 +1099,37 @@ done:
 }
 
 /**
+ * bitmap_find_free_one - find a mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *
+ * Find one of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+static int __bitmap_find_free_one(unsigned long *bitmap, int bits)
+{
+	int pos, i;
+	unsigned long mask = (unsigned long)(~((unsigned long) 0));
+	int nlongs_reg = BITS_TO_LONGS(bits);
+
+	for (i = 0 ; i < nlongs_reg ; i++) {
+		if ((bitmap[i] & mask) != mask) {
+			for (pos = 0 ; pos < BITS_PER_LONG ; pos++) {
+				if (!__reg_op(&bitmap[i], pos, 0,
+					REG_OP_ISFREE))
+					continue;
+				__reg_op(&bitmap[i], pos, 0, REG_OP_ALLOC);
+				return pos;
+			}
+		}
+	}
+	return -ENOMEM;
+}
+
+/**
  * 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
@@ -1116,6 +1147,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	int pos, end;		/* scans bitmap by regions of size order */
 
+	if (order == 0)
+		return __bitmap_find_free_one(bitmap, bits);
+
 	for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;
Signature · 1 line
1.7.9.5
maintainer
#1 lore raw
Quoted 3 lines · On Mon, 8 Apr 2013 11:23:48 +0900 Chanho Min <[email protected]> wrote:

If bitmap_find_free_region() is called with order=0, We can reduce for-loops to find 1 free bit. First, It scans bitmap array by the increment of long type, then find 1 free bit within 1 long type value.

That seems sensible. I assume-without-checking that single-bit is a common case?

Quoted 16 lines

In 32 bits system and 1024 bits size, in the worst case, We need 1024 for-loops to find 1 free bit. But, If This is applied, it takes 64 for-loops. Instead, if free bit is in the first index of the bitmaps, It will be needed additional 1 for-loop. But from second index, It will be speed up significantly.

lib/bitmap.c +4 -0
@@ -1099,6 +1099,37 @@ done:
 }
 
 /**
+ * bitmap_find_free_one - find a mem region
+ *	@bitmap: array of unsigned longs corresponding to the bitmap
+ *	@bits: number of bits in the bitmap
+ *

lib/bitmap.c done: · line 1115

Quoted 10 lines
lib/bitmap.c +10 -0
+ * Find one of free (zero) bits in a @bitmap of @bits bits and
+ * allocate them (set them to one).
+ *
+ * Return the bit offset in bitmap of the allocated region,
+ * or -errno on failure.
+ */
+static int __bitmap_find_free_one(unsigned long *bitmap, int bits)
+{
+	int pos, i;
+	unsigned long mask = (unsigned long)(~((unsigned long) 0));

That seems unnecessarily complicated. "unsigned long mask = -1;" works :)

lib/bitmap.c done: · line 1119

Quoted 4 lines
lib/bitmap.c +4 -0
+	int nlongs_reg = BITS_TO_LONGS(bits);
+
+	for (i = 0 ; i < nlongs_reg ; i++) {
+		if ((bitmap[i] & mask) != mask) {

But here we could just do "if (bitmap[i] != -1)". Or ~0UL.

lib/bitmap.c done: · line 1130

Quoted 11 lines
lib/bitmap.c +11 -0
+			for (pos = 0 ; pos < BITS_PER_LONG ; pos++) {
+				if (!__reg_op(&bitmap[i], pos, 0,
+					REG_OP_ISFREE))
+					continue;
+				__reg_op(&bitmap[i], pos, 0, REG_OP_ALLOC);
+				return pos;
+			}
+		}
+	}
+	return -ENOMEM;
+}

afacit the code is buggy - if `bits' is not an exact multiple of BITS_PER_LONG, this search will wander off the end of the specified region?

Quoted 14 lines
lib/bitmap.c +4 -0
+/**
  * 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
@@ -1116,6 +1147,9 @@ int bitmap_find_free_region(unsigned long *bitmap, int bits, int order)
 {
 	int pos, end;		/* scans bitmap by regions of size order */
 
+	if (order == 0)
+		return __bitmap_find_free_one(bitmap, bits);
+
 	for (pos = 0 ; (end = pos + (1 << order)) <= bits; pos = end) {
 		if (!__reg_op(bitmap, pos, order, REG_OP_ISFREE))
 			continue;
#2 lore raw
Quoted 2 lines · Andrew Morton
Quoted 1 line · On Mon, 8 Apr 2013 11:23:48 +0900 Chanho Min <[email protected]> wrote:

--- a/lib/bitmap.c

[]

Quoted 1 line
Quoted 1 line

+static int __bitmap_find_free_one(unsigned long *bitmap, int bits)

[]

Quoted 3 lines

lib/bitmap.c done: · line 1115

Quoted 1 line
lib/bitmap.c +1 -0
+	unsigned long mask = (unsigned long)(~((unsigned long) 0));

That seems unnecessarily complicated. "unsigned long mask = -1;" works :)

So would ULONG_MAX or just ~0UL