linux-kernel - [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero

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-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <1255076961-21325-2-git-send-email-akinobu.mita@gmail.com>
Date:	Fri,  9 Oct 2009 17:29:15 +0900
From:	Akinobu Mita <akinobu.mita@...il.com>
To:	linux-kernel@...r.kernel.org, akpm@...ux-foundation.org
Cc:	Akinobu Mita <akinobu.mita@...il.com>,
	FUJITA Tomonori <fujita.tomonori@....ntt.co.jp>,
	"David S. Miller" <davem@...emloft.net>,
	sparclinux@...r.kernel.org,
	Benjamin Herrenschmidt <benh@...nel.crashing.org>,
	Paul Mackerras <paulus@...ba.org>, linuxppc-dev@...abs.org,
	Thomas Gleixner <tglx@...utronix.de>,
	Ingo Molnar <mingo@...hat.com>,
	"H. Peter Anvin" <hpa@...or.com>, x86@...nel.org,
	Greg Kroah-Hartman <gregkh@...e.de>,
	Lothar Wassmann <LW@...O-electronics.de>,
	linux-usb@...r.kernel.org, Roland Dreier <rolandd@...co.com>,
	Yevgeny Petrilin <yevgenyp@...lanox.co.il>,
	netdev@...r.kernel.org, Tony Luck <tony.luck@...el.com>,
	Fenghua Yu <fenghua.yu@...el.com>, linux-ia64@...r.kernel.org,
	linux-altix@....com
Subject: [PATCH 2/8] bitmap: Introduce bitmap_set, bitmap_clear, bitmap_find_next_zero_area

This introduces new bitmap functions:

bitmap_set: Set specified bit area
bitmap_clear: Clear specified bit area
bitmap_find_next_zero_area: Find free bit area

These are stolen from iommu helper.

I changed the return value of bitmap_find_next_zero_area if there is
no zero area.

find_next_zero_area in iommu helper: returns -1
bitmap_find_next_zero_area: return >= bitmap size

Cc: FUJITA Tomonori <fujita.tomonori@....ntt.co.jp>
Cc: "David S. Miller" <davem@...emloft.net>
Cc: sparclinux@...r.kernel.org
Cc: Benjamin Herrenschmidt <benh@...nel.crashing.org>
Cc: Paul Mackerras <paulus@...ba.org>
Cc: linuxppc-dev@...abs.org
Cc: Thomas Gleixner <tglx@...utronix.de>
Cc: Ingo Molnar <mingo@...hat.com>
Cc: "H. Peter Anvin" <hpa@...or.com>
Cc: x86@...nel.org
Cc: Greg Kroah-Hartman <gregkh@...e.de>
Cc: Lothar Wassmann <LW@...O-electronics.de>
Cc: linux-usb@...r.kernel.org
Cc: Roland Dreier <rolandd@...co.com>
Cc: Yevgeny Petrilin <yevgenyp@...lanox.co.il>
Cc: netdev@...r.kernel.org
Cc: Tony Luck <tony.luck@...el.com>
Cc: Fenghua Yu <fenghua.yu@...el.com>
Cc: linux-ia64@...r.kernel.org
Cc: linux-altix@....com
Signed-off-by: Akinobu Mita <akinobu.mita@...il.com>
---
 include/linux/bitmap.h |   11 +++++++++++
 lib/bitmap.c           |   47 +++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 58 insertions(+), 0 deletions(-)

diff --git a/include/linux/bitmap.h b/include/linux/bitmap.h
index 756d78b..daf8c48 100644
--- a/include/linux/bitmap.h
+++ b/include/linux/bitmap.h
@@ -42,6 +42,9 @@
  * bitmap_empty(src, nbits)			Are all bits zero in *src?
  * bitmap_full(src, nbits)			Are all bits set in *src?
  * bitmap_weight(src, nbits)			Hamming Weight: number set bits
+ * bitmap_set(dst, pos, nbits)			Set specified bit area
+ * bitmap_clear(dst, pos, nbits)		Clear specified bit area
+ * bitmap_find_next_zero_area(buf, len, pos, n, mask)	Find bit free area
  * bitmap_shift_right(dst, src, n, nbits)	*dst = *src >> n
  * bitmap_shift_left(dst, src, n, nbits)	*dst = *src << n
  * bitmap_remap(dst, src, old, new, nbits)	*dst = map(old, new)(src)
@@ -108,6 +111,14 @@ extern int __bitmap_subset(const unsigned long *bitmap1,
 			const unsigned long *bitmap2, int bits);
 extern int __bitmap_weight(const unsigned long *bitmap, int bits);
 
+extern void bitmap_set(unsigned long *map, int i, int len);
+extern void bitmap_clear(unsigned long *map, int start, int nr);
+extern unsigned long bitmap_find_next_zero_area(unsigned long *map,
+					 unsigned long size,
+					 unsigned long start,
+					 unsigned int nr,
+					 unsigned long align_mask);
+
 extern int bitmap_scnprintf(char *buf, unsigned int len,
 			const unsigned long *src, int nbits);
 extern int __bitmap_parse(const char *buf, unsigned int buflen, int is_user,
diff --git a/lib/bitmap.c b/lib/bitmap.c
index 7025658..95070fa 100644
--- a/lib/bitmap.c
+++ b/lib/bitmap.c
@@ -271,6 +271,53 @@ int __bitmap_weight(const unsigned long *bitmap, int bits)
 }
 EXPORT_SYMBOL(__bitmap_weight);
 
+void bitmap_set(unsigned long *map, int i, int len)
+{
+	int end = i + len;
+
+	while (i < end) {
+		__set_bit(i, map);
+		i++;
+	}
+}
+EXPORT_SYMBOL(bitmap_set);
+
+void bitmap_clear(unsigned long *map, int start, int nr)
+{
+	int end = start + nr;
+
+	while (start < end) {
+		__clear_bit(start, map);
+		start++;
+	}
+}
+EXPORT_SYMBOL(bitmap_clear);
+
+unsigned long bitmap_find_next_zero_area(unsigned long *map,
+					 unsigned long size,
+					 unsigned long start,
+					 unsigned int nr,
+					 unsigned long align_mask)
+{
+	unsigned long index, end, i;
+again:
+	index = find_next_zero_bit(map, size, start);
+
+	/* Align allocation */
+	index = (index + align_mask) & ~align_mask;
+
+	end = index + nr;
+	if (end >= size)
+		return end;
+	i = find_next_bit(map, end, index);
+	if (i < end) {
+		start = i + 1;
+		goto again;
+	}
+	return index;
+}
+EXPORT_SYMBOL(bitmap_find_next_zero_area);
+
 /*
  * Bitmap printing & parsing functions: first version by Bill Irwin,
  * second version by Paul Jackson, third by Joe Korty.
-- 
1.5.4.3

--
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/