linux-kernel - [PATCH v2] bitmap: speedup in bitmap_find_free

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <1365475486-14371-1-git-send-email-chanho.min@lge.com>
Date:	Tue,  9 Apr 2013 11:44:46 +0900
From:	Chanho Min <chanho.min@....com>
To:	Andrew Morton <akpm@...ux-foundation.org>,
	Nadia Yvette Chambers <nyc@...omorphy.com>,
	Jiri Kosina <jkosina@...e.cz>,
	Guennadi Liakhovetski <lg@...x.de>
Cc:	linux-kernel@...r.kernel.org, Chanho Min <chanho.min@....com>
Subject: [PATCH v2] 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 speed up significantly.

Changes compared to v1:
 - Modified unnecessarily complicated code.
 - Fixed the buggy code if `bits' is not an multiple of BITS_PER_LONG.

Signed-off-by: Chanho Min <chanho.min@....com>
---
 lib/bitmap.c |   36 ++++++++++++++++++++++++++++++++++++
 1 file changed, 36 insertions(+)

diff --git a/lib/bitmap.c b/lib/bitmap.c
index 06f7e4f..663fc28 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -1099,6 +1099,39 @@ 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, end = BITS_PER_LONG, i;
+	int nlongs_reg = BITS_TO_LONGS(bits);
+	int last_bits = bits % BITS_PER_LONG;
+
+	for (i = 0 ; i < nlongs_reg ; i++) {
+		if (bitmap[i] != ~0UL) {
+			if (i == (nlongs_reg - 1) && last_bits)
+				end = last_bits;
+			for (pos = 0 ; pos < end ; 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 +1149,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;
-- 
1.7.9.5

--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/