[PATCH rdma-core 1/5] util: Add new bitmap API

[Yishai Hadas <yishaih@nvidia.com>]

From: Maher Sanalla <msanalla@nvidia.com>

Adds new bitmap implementation to util directory, which replaces the
ccan equivalent, due to the license used (LGPLv2+) which is not fitting
in rdma-core.

Signed-off-by: Maher Sanalla <msanalla@nvidia.com>
Reviewed-by: Avihai Horon <avihaih@nvidia.com>
Signed-off-by: Yishai Hadas <yishaih@nvidia.com>
---
 providers/mlx5/bitmap.h |   2 -
 util/CMakeLists.txt     |   2 +
 util/bitmap.c           | 180 ++++++++++++++++++++++++++++++++++++++++++++++++
 util/bitmap.h           | 120 ++++++++++++++++++++++++++++++++
 util/util.h             |   1 +
 5 files changed, 303 insertions(+), 2 deletions(-)
 create mode 100644 util/bitmap.c
 create mode 100644 util/bitmap.h

diff --git a/providers/mlx5/bitmap.h b/providers/mlx5/bitmap.h
index 034fb98..b2c8a36 100644
--- a/providers/mlx5/bitmap.h
+++ b/providers/mlx5/bitmap.h
@@ -54,8 +54,6 @@
 #define MLX5_SHMAT_FLAGS 0
 #endif
 
-#define BITS_TO_LONGS(nr)	DIV_ROUND_UP(nr, BITS_PER_LONG)
-
 #ifndef HPAGE_SIZE
 #define HPAGE_SIZE		(2UL * 1024 * 1024)
 #endif
diff --git a/util/CMakeLists.txt b/util/CMakeLists.txt
index d8a66be..58c77d5 100644
--- a/util/CMakeLists.txt
+++ b/util/CMakeLists.txt
@@ -1,4 +1,5 @@
 publish_internal_headers(util
+  bitmap.h
   cl_qmap.h
   compiler.h
   interval_set.h
@@ -9,6 +10,7 @@ publish_internal_headers(util
   )
 
 set(C_FILES
+  bitmap.c
   cl_map.c
   interval_set.c
   node_name_map.c
diff --git a/util/bitmap.c b/util/bitmap.c
new file mode 100644
index 0000000..e5ed30e
--- /dev/null
+++ b/util/bitmap.c
@@ -0,0 +1,180 @@
+/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */
+
+#include "bitmap.h"
+
+#define BMP_WORD_INDEX(n) (BITS_TO_LONGS((n) + 1) - 1)
+#define BMP_FIRST_WORD_MASK(start) (~0UL << ((start) & (BITS_PER_LONG - 1)))
+#define BMP_LAST_WORD_MASK(end) (~BMP_FIRST_WORD_MASK(end))
+
+static unsigned long __word_ffs(const unsigned long *word)
+{
+	unsigned long i;
+
+	for (i = 0; i < BITS_PER_LONG; i++) {
+		if (bitmap_test_bit(word, i))
+			return i;
+	}
+
+	return i;
+}
+
+static unsigned long word_ffs(const unsigned long *word,
+			      unsigned long bmp_index, unsigned long end)
+{
+	unsigned long set_bit;
+
+	set_bit = __word_ffs(word);
+	set_bit += bmp_index * BITS_PER_LONG;
+	if (set_bit >= end)
+		return end;
+
+	return set_bit;
+}
+
+/*
+ * Finds the first set bit in the bitmap starting from
+ * 'start' bit until ('end'-1) bit.
+ *
+ * Returns the set bit index if found, otherwise returns 'end'.
+ */
+unsigned long bitmap_find_first_bit(const unsigned long *bmp,
+				    unsigned long start, unsigned long end)
+{
+	unsigned long mask;
+	unsigned long first_word;
+	unsigned long curr_idx = BMP_WORD_INDEX(start);
+	unsigned long end_idx = BMP_WORD_INDEX(end);
+
+	assert(start <= end);
+
+	mask = BMP_FIRST_WORD_MASK(start);
+
+	first_word = bmp[curr_idx] & mask;
+	if (first_word)
+		return word_ffs(&first_word, curr_idx, end);
+
+	for (curr_idx++; curr_idx <= end_idx; curr_idx++) {
+		if (!bmp[curr_idx])
+			continue;
+
+		return word_ffs(&bmp[curr_idx], curr_idx, end);
+	}
+
+	return end;
+}
+
+/*
+ * Zeroes bitmap bits in the following range: [start,end-1]
+ */
+void bitmap_zero_region(unsigned long *bmp, unsigned long start,
+			unsigned long end)
+{
+	unsigned long start_mask;
+	unsigned long last_mask;
+	unsigned long curr_idx = BMP_WORD_INDEX(start);
+	unsigned long end_idx = BMP_WORD_INDEX(end);
+
+	assert(start <= end);
+
+	start_mask = BMP_FIRST_WORD_MASK(start);
+	last_mask = BMP_LAST_WORD_MASK(end);
+
+	if (curr_idx == end_idx) {
+		bmp[curr_idx] &= ~(start_mask & last_mask);
+		return;
+	}
+
+	bmp[curr_idx] &= ~start_mask;
+
+	for (curr_idx++; curr_idx < end_idx; curr_idx++)
+		bmp[curr_idx] = 0;
+
+	bmp[curr_idx] &= ~last_mask;
+}
+
+/*
+ * Sets bitmap bits in the following range: [start,end-1]
+ */
+void bitmap_fill_region(unsigned long *bmp, unsigned long start,
+			unsigned long end)
+{
+	unsigned long start_mask;
+	unsigned long last_mask;
+	unsigned long curr_idx = BMP_WORD_INDEX(start);
+	unsigned long end_idx = BMP_WORD_INDEX(end);
+
+	assert(start <= end);
+
+	start_mask = BMP_FIRST_WORD_MASK(start);
+	last_mask = BMP_LAST_WORD_MASK(end);
+
+	if (curr_idx == end_idx) {
+		bmp[curr_idx] |= (start_mask & last_mask);
+		return;
+	}
+
+	bmp[curr_idx] |= start_mask;
+
+	for (curr_idx++; curr_idx < end_idx; curr_idx++)
+		bmp[curr_idx] = ULONG_MAX;
+
+	bmp[curr_idx] |= last_mask;
+}
+
+/*
+ * Checks whether the contiguous region of region_size bits starting from
+ * start is free.
+ *
+ * Returns true if the said region is free, otherwise returns false.
+ */
+static bool bitmap_is_free_region(unsigned long *bmp, unsigned long start,
+				  unsigned long region_size)
+{
+	unsigned long curr_idx;
+	unsigned long last_idx;
+	unsigned long last_mask;
+	unsigned long start_mask;
+
+	curr_idx = BMP_WORD_INDEX(start);
+	start_mask = BMP_FIRST_WORD_MASK(start);
+	last_idx = BMP_WORD_INDEX(start + region_size);
+	last_mask = BMP_LAST_WORD_MASK(start + region_size);
+
+	if (curr_idx == last_idx)
+		return !(bmp[curr_idx] & start_mask & last_mask);
+
+	if (bmp[curr_idx] & start_mask)
+		return false;
+
+	for (curr_idx++; curr_idx < last_idx; curr_idx++) {
+		if (bmp[curr_idx])
+			return false;
+	}
+
+	return !(bmp[curr_idx] & last_mask);
+}
+
+/*
+ * Finds a contiguous region with the size of region_size
+ * in the bitmap that is not set.
+ *
+ * Returns first index of such region if found,
+ * otherwise returns nbits.
+ */
+unsigned long bitmap_find_free_region(unsigned long *bmp,
+				      unsigned long nbits,
+				      unsigned long region_size)
+{
+	unsigned long start;
+
+	for (start = 0; start + region_size <= nbits; start++) {
+		if (bitmap_test_bit(bmp, start))
+			continue;
+
+		if (bitmap_is_free_region(bmp, start, region_size))
+			return start;
+	}
+
+	return nbits;
+}
+
diff --git a/util/bitmap.h b/util/bitmap.h
new file mode 100644
index 0000000..c48706a
--- /dev/null
+++ b/util/bitmap.h
@@ -0,0 +1,120 @@
+/* GPLv2 or OpenIB.org BSD (MIT) See COPYING file */
+
+#ifndef UTIL_BITMAP_H
+#define UTIL_BITMAP_H
+
+#include <stdlib.h>
+#include <stdbool.h>
+#include <limits.h>
+#include <string.h>
+#include <assert.h>
+
+#include "util.h"
+
+#define BMP_DECLARE(name, nbits) \
+	unsigned long (name)[BITS_TO_LONGS((nbits))]
+
+unsigned long bitmap_find_first_bit(const unsigned long *bmp,
+				    unsigned long start, unsigned long end);
+
+void bitmap_zero_region(unsigned long *bmp, unsigned long start,
+			unsigned long end);
+
+void bitmap_fill_region(unsigned long *bmp, unsigned long start,
+			unsigned long end);
+
+unsigned long bitmap_find_free_region(unsigned long *bmp,
+				      unsigned long nbits,
+				      unsigned long region_size);
+
+static inline void bitmap_fill(unsigned long *bmp, unsigned long nbits)
+{
+	unsigned long size = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+
+	memset(bmp, 0xff, size);
+}
+
+static inline void bitmap_zero(unsigned long *bmp, unsigned long nbits)
+{
+	unsigned long size = BITS_TO_LONGS(nbits) * sizeof(unsigned long);
+
+	memset(bmp, 0, size);
+}
+
+static inline bool bitmap_empty(const unsigned long *bmp, unsigned long nbits)
+{
+	unsigned long i;
+	unsigned long mask = ULONG_MAX;
+
+	assert(nbits);
+
+	for (i = 0; i < BITS_TO_LONGS(nbits) - 1; i++) {
+		if (bmp[i] != 0)
+			return false;
+	}
+
+	if (nbits % BITS_PER_LONG)
+		mask = (1UL << (nbits % BITS_PER_LONG)) - 1;
+
+	return (bmp[i] & mask) ? false : true;
+}
+
+static inline bool bitmap_full(const unsigned long *bmp, unsigned long nbits)
+{
+	unsigned long i;
+	unsigned long mask = ULONG_MAX;
+
+	assert(nbits);
+
+	for (i = 0; i < BITS_TO_LONGS(nbits) - 1; i++) {
+		if (bmp[i] != -1UL)
+			return false;
+	}
+
+	if (nbits % BITS_PER_LONG)
+		mask = (1UL << (nbits % BITS_PER_LONG)) - 1;
+
+	return ((bmp[i] & mask) ^ (mask)) ? false : true;
+}
+
+static inline void bitmap_set_bit(unsigned long *bmp, unsigned long idx)
+{
+	bmp[(idx / BITS_PER_LONG)] |= (1UL << (idx % BITS_PER_LONG));
+}
+
+static inline void bitmap_clear_bit(unsigned long *bmp, unsigned long idx)
+{
+	bmp[(idx / BITS_PER_LONG)] &= ~(1UL << (idx % BITS_PER_LONG));
+}
+
+static inline bool bitmap_test_bit(const unsigned long *bmp, unsigned long idx)
+{
+	return !!(bmp[(idx / BITS_PER_LONG)] &
+		 (1UL << (idx % BITS_PER_LONG)));
+}
+
+static inline unsigned long *bitmap_alloc0(unsigned long size)
+{
+	unsigned long *bmp;
+
+	bmp = calloc(BITS_TO_LONGS(size), sizeof(long));
+	if (!bmp)
+		return NULL;
+
+	return bmp;
+}
+
+static inline unsigned long *bitmap_alloc1(unsigned long size)
+{
+	unsigned long *bmp;
+
+	bmp = bitmap_alloc0(size);
+	if (!bmp)
+		return NULL;
+
+	bitmap_fill(bmp, size);
+
+	return bmp;
+}
+
+#endif
diff --git a/util/util.h b/util/util.h
index f721b83..af03c42 100644
--- a/util/util.h
+++ b/util/util.h
@@ -28,6 +28,7 @@ static inline bool __good_snprintf(size_t len, int rc)
 
 #define BITS_PER_LONG	   (8 * sizeof(long))
 #define BITS_PER_LONG_LONG (8 * sizeof(long long))
+#define BITS_TO_LONGS(nr)  (((nr) + BITS_PER_LONG - 1) / BITS_PER_LONG)
 
 #define GENMASK(h, l) \
 	(((~0UL) - (1UL << (l)) + 1) & (~0UL >> (BITS_PER_LONG - 1 - (h))))
-- 
1.8.3.1