From: Maher Sanalla <msanalla@xxxxxxxxxx>
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@xxxxxxxxxx>
Reviewed-by: Avihai Horon <avihaih@xxxxxxxxxx>
Signed-off-by: Yishai Hadas <yishaih@xxxxxxxxxx>
---
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
