[PATCH rdma-core 0/5] Add new bitmap API

[PATCH rdma-core 0/5] Add new bitmap API

[Yishai Hadas]

This series adds new bitmap implementation to util directory which replaces the
ccan equivalent.

The ccan/bitmap stuff was published under the LGPLv2+ license which is not
fitting in rdma-core.

As of the above, the applicable bitmap code in rdma-core was adapted to use the
util new API.

PR was sent:
https://github.com/linux-rdma/rdma-core/pull/1144

Maher Sanalla (5):
  util: Add new bitmap API
  mlx5: Adapt bitmap usage to use util API
  libhns: Adapt bitmap usage to use util API
  verbs: Adapt bitmap usage to use util API
  ccan: Remove bitmap code

 ccan/CMakeLists.txt           |   2 -
 ccan/bitmap.c                 | 125 ----------------------
 ccan/bitmap.h                 | 239 ------------------------------------------
 libibverbs/ibverbs.h          |   4 +-
 providers/hns/hns_roce_u.h    |   4 +-
 providers/hns/hns_roce_u_db.c |   4 +-
 providers/mlx5/bitmap.h       | 111 --------------------
 providers/mlx5/buf.c          | 187 +++++++--------------------------
 providers/mlx5/dr_buddy.c     |  12 +--
 providers/mlx5/mlx5.h         |  17 +--
 providers/mlx5/mlx5_vfio.c    |   3 +-
 providers/mlx5/mlx5_vfio.h    |   2 +-
 providers/mlx5/mlx5dv_dr.h    |   6 +-
 util/CMakeLists.txt           |   2 +
 util/bitmap.c                 | 180 +++++++++++++++++++++++++++++++
 util/bitmap.h                 | 120 +++++++++++++++++++++
 util/util.h                   |   1 +
 17 files changed, 362 insertions(+), 657 deletions(-)
 delete mode 100644 ccan/bitmap.c
 delete mode 100644 ccan/bitmap.h
 delete mode 100644 providers/mlx5/bitmap.h
 create mode 100644 util/bitmap.c
 create mode 100644 util/bitmap.h

-- 
1.8.3.1

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

[Yishai Hadas]

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

[PATCH rdma-core 2/5] mlx5: Adapt bitmap usage to use util API

[Yishai Hadas]

From: Maher Sanalla <msanalla@nvidia.com>

Replace the usage of ccan bitmap with the newly added bitmap
implementation in util.

As part of it, remove mlx5 bitmap API.

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    | 109 --------------------------
 providers/mlx5/buf.c       | 187 +++++++++------------------------------------
 providers/mlx5/dr_buddy.c  |  12 +--
 providers/mlx5/mlx5.h      |  17 +----
 providers/mlx5/mlx5_vfio.c |   3 +-
 providers/mlx5/mlx5_vfio.h |   2 +-
 providers/mlx5/mlx5dv_dr.h |   6 +-
 7 files changed, 53 insertions(+), 283 deletions(-)
 delete mode 100644 providers/mlx5/bitmap.h

diff --git a/providers/mlx5/bitmap.h b/providers/mlx5/bitmap.h
deleted file mode 100644
index b2c8a36..0000000
--- a/providers/mlx5/bitmap.h
+++ /dev/null
@@ -1,109 +0,0 @@
-/*
- * Copyright (c) 2000, 2011 Mellanox Technology Inc.  All rights reserved.
- *
- * This software is available to you under a choice of one of two
- * licenses.  You may choose to be licensed under the terms of the GNU
- * General Public License (GPL) Version 2, available from the file
- * COPYING in the main directory of this source tree, or the
- * OpenIB.org BSD license below:
- *
- *     Redistribution and use in source and binary forms, with or
- *     without modification, are permitted provided that the following
- *     conditions are met:
- *
- *      - Redistributions of source code must retain the above
- *        copyright notice, this list of conditions and the following
- *        disclaimer.
- *
- *      - Redistributions in binary form must reproduce the above
- *        copyright notice, this list of conditions and the following
- *        disclaimer in the documentation and/or other materials
- *        provided with the distribution.
- *
- * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
- * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
- * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
- * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
- * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
- * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
- * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
- * SOFTWARE.
- */
-
-#ifndef BITMAP_H
-#define BITMAP_H
-
-#include <stdlib.h>
-#include <stdio.h>
-#include <pthread.h>
-#include <string.h>
-#include <sys/types.h>
-#include <sys/ipc.h>
-#include <sys/shm.h>
-#include <sys/mman.h>
-#include <linux/errno.h>
-#include <util/util.h>
-#include "mlx5.h"
-
-/* Only ia64 requires this */
-#ifdef __ia64__
-#define MLX5_SHM_ADDR ((void *)0x8000000000000000UL)
-#define MLX5_SHMAT_FLAGS (SHM_RND)
-#else
-#define MLX5_SHM_ADDR NULL
-#define MLX5_SHMAT_FLAGS 0
-#endif
-
-#ifndef HPAGE_SIZE
-#define HPAGE_SIZE		(2UL * 1024 * 1024)
-#endif
-
-#define MLX5_SHM_LENGTH		HPAGE_SIZE
-#define MLX5_Q_CHUNK_SIZE	32768
-#define MLX5_SHM_NUM_REGION	64
-
-static inline unsigned long mlx5_ffz(uint32_t word)
-{
-	return __builtin_ffs(~word) - 1;
-}
-
-static inline uint32_t mlx5_find_first_zero_bit(const unsigned long *addr,
-					 uint32_t size)
-{
-	const unsigned long *p = addr;
-	uint32_t result = 0;
-	unsigned long tmp;
-
-	while (size & ~(BITS_PER_LONG - 1)) {
-		tmp = *(p++);
-		if (~tmp)
-			goto found;
-		result += BITS_PER_LONG;
-		size -= BITS_PER_LONG;
-	}
-	if (!size)
-		return result;
-
-	tmp = (*p) | (~0UL << size);
-	if (tmp == (uint32_t)~0UL)	/* Are any bits zero? */
-		return result + size;	/* Nope. */
-found:
-	return result + mlx5_ffz(tmp);
-}
-
-static inline void mlx5_set_bit(unsigned int nr, unsigned long *addr)
-{
-	addr[(nr / BITS_PER_LONG)] |= (1 << (nr % BITS_PER_LONG));
-}
-
-static inline void mlx5_clear_bit(unsigned int nr,  unsigned long *addr)
-{
-	addr[(nr / BITS_PER_LONG)] &= ~(1 << (nr % BITS_PER_LONG));
-}
-
-static inline int mlx5_test_bit(unsigned int nr, const unsigned long *addr)
-{
-	return !!(addr[(nr / BITS_PER_LONG)] & (1 <<  (nr % BITS_PER_LONG)));
-}
-
-#endif
diff --git a/providers/mlx5/buf.c b/providers/mlx5/buf.c
index 83c32b0..3a3a792 100644
--- a/providers/mlx5/buf.c
+++ b/providers/mlx5/buf.c
@@ -38,155 +38,38 @@
 #include <stdio.h>
 #include <stdlib.h>
 #include <errno.h>
+#include <sys/mman.h>
+#include <util/bitmap.h>
 
 #include "mlx5.h"
-#include "bitmap.h"
 
-static int mlx5_bitmap_init(struct mlx5_bitmap *bmp, uint32_t num,
-			    uint32_t mask)
-{
-	bmp->last = 0;
-	bmp->top  = 0;
-	bmp->max  = num;
-	bmp->avail = num;
-	bmp->mask = mask;
-	bmp->avail = bmp->max;
-	bmp->table = calloc(BITS_TO_LONGS(bmp->max), sizeof(*bmp->table));
-	if (!bmp->table)
-		return -ENOMEM;
-
-	return 0;
-}
-
-static void bitmap_free_range(struct mlx5_bitmap *bmp, uint32_t obj,
-			      int cnt)
-{
-	int i;
+/* Only ia64 requires this */
+#ifdef __ia64__
+#define MLX5_SHM_ADDR ((void *)0x8000000000000000UL)
+#define MLX5_SHMAT_FLAGS (SHM_RND)
+#else
+#define MLX5_SHM_ADDR NULL
+#define MLX5_SHMAT_FLAGS 0
+#endif
 
-	obj &= bmp->max - 1;
-
-	for (i = 0; i < cnt; i++)
-		mlx5_clear_bit(obj + i, bmp->table);
-	bmp->last = min(bmp->last, obj);
-	bmp->top = (bmp->top + bmp->max) & bmp->mask;
-	bmp->avail += cnt;
-}
-
-static int mlx5_bitmap_empty(struct mlx5_bitmap *bmp)
-{
-	return (bmp->avail == bmp->max) ? 1 : 0;
-}
-
-static int bitmap_avail(struct mlx5_bitmap *bmp)
-{
-	return bmp->avail;
-}
+#ifndef HPAGE_SIZE
+#define HPAGE_SIZE              (2UL * 1024 * 1024)
+#endif
 
-static void mlx5_bitmap_cleanup(struct mlx5_bitmap *bmp)
-{
-	if (bmp->table)
-		free(bmp->table);
-}
+#define MLX5_SHM_LENGTH         HPAGE_SIZE
+#define MLX5_Q_CHUNK_SIZE       32768
 
 static void free_huge_mem(struct mlx5_hugetlb_mem *hmem)
 {
-	mlx5_bitmap_cleanup(&hmem->bitmap);
+	if (hmem->bitmap)
+		free(hmem->bitmap);
+
 	if (shmdt(hmem->shmaddr) == -1)
 		mlx5_dbg(stderr, MLX5_DBG_CONTIG, "%s\n", strerror(errno));
 	shmctl(hmem->shmid, IPC_RMID, NULL);
 	free(hmem);
 }
 
-static int mlx5_bitmap_alloc(struct mlx5_bitmap *bmp)
-{
-	uint32_t obj;
-	int ret;
-
-	obj = mlx5_find_first_zero_bit(bmp->table, bmp->max);
-	if (obj < bmp->max) {
-		mlx5_set_bit(obj, bmp->table);
-		bmp->last = (obj + 1);
-		if (bmp->last == bmp->max)
-			bmp->last = 0;
-		obj |= bmp->top;
-		ret = obj;
-	} else
-		ret = -1;
-
-	if (ret != -1)
-		--bmp->avail;
-
-	return ret;
-}
-
-static uint32_t find_aligned_range(unsigned long *bmp,
-				   uint32_t start, uint32_t nbits,
-				   int len, int alignment)
-{
-	uint32_t end, i;
-
-again:
-	start = align(start, alignment);
-
-	while ((start < nbits) && mlx5_test_bit(start, bmp))
-		start += alignment;
-
-	if (start >= nbits)
-		return -1;
-
-	end = start + len;
-	if (end > nbits)
-		return -1;
-
-	for (i = start + 1; i < end; i++) {
-		if (mlx5_test_bit(i, bmp)) {
-			start = i + 1;
-			goto again;
-		}
-	}
-
-	return start;
-}
-
-static int bitmap_alloc_range(struct mlx5_bitmap *bmp, int cnt,
-			      int align)
-{
-	uint32_t obj;
-	int ret, i;
-
-	if (cnt == 1 && align == 1)
-		return mlx5_bitmap_alloc(bmp);
-
-	if (cnt > bmp->max)
-		return -1;
-
-	obj = find_aligned_range(bmp->table, bmp->last,
-				 bmp->max, cnt, align);
-	if (obj >= bmp->max) {
-		bmp->top = (bmp->top + bmp->max) & bmp->mask;
-		obj = find_aligned_range(bmp->table, 0, bmp->max,
-					 cnt, align);
-	}
-
-	if (obj < bmp->max) {
-		for (i = 0; i < cnt; i++)
-			mlx5_set_bit(obj + i, bmp->table);
-		if (obj == bmp->last) {
-			bmp->last = (obj + cnt);
-			if (bmp->last >= bmp->max)
-				bmp->last = 0;
-		}
-		obj |= bmp->top;
-		ret = obj;
-	} else
-		ret = -1;
-
-	if (ret != -1)
-		bmp->avail -= cnt;
-
-	return obj;
-}
-
 static struct mlx5_hugetlb_mem *alloc_huge_mem(size_t size)
 {
 	struct mlx5_hugetlb_mem *hmem;
@@ -209,12 +92,14 @@ static struct mlx5_hugetlb_mem *alloc_huge_mem(size_t size)
 		goto out_rmid;
 	}
 
-	if (mlx5_bitmap_init(&hmem->bitmap, shm_len / MLX5_Q_CHUNK_SIZE,
-			     shm_len / MLX5_Q_CHUNK_SIZE - 1)) {
+	hmem->bitmap = bitmap_alloc0(shm_len / MLX5_Q_CHUNK_SIZE);
+	if (!hmem->bitmap) {
 		mlx5_dbg(stderr, MLX5_DBG_CONTIG, "%s\n", strerror(errno));
 		goto out_shmdt;
 	}
 
+	hmem->bmp_size = shm_len / MLX5_Q_CHUNK_SIZE;
+
 	/*
 	 * Marked to be destroyed when process detaches from shmget segment
 	 */
@@ -250,9 +135,13 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf,
 
 	mlx5_spin_lock(&mctx->hugetlb_lock);
 	list_for_each(&mctx->hugetlb_list, hmem, entry) {
-		if (bitmap_avail(&hmem->bitmap)) {
-			buf->base = bitmap_alloc_range(&hmem->bitmap, nchunk, 1);
-			if (buf->base != -1) {
+		if (!bitmap_full(hmem->bitmap, hmem->bmp_size)) {
+			buf->base = bitmap_find_free_region(hmem->bitmap,
+							    hmem->bmp_size,
+							    nchunk);
+			if (buf->base != hmem->bmp_size) {
+				bitmap_fill_region(hmem->bitmap, buf->base,
+						   buf->base + nchunk);
 				buf->hmem = hmem;
 				found = 1;
 				break;
@@ -266,16 +155,14 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf,
 		if (!hmem)
 			return -1;
 
-		buf->base = bitmap_alloc_range(&hmem->bitmap, nchunk, 1);
-		if (buf->base == -1) {
-			free_huge_mem(hmem);
-			return -1;
-		}
+		buf->base = 0;
+		assert(nchunk <= hmem->bmp_size);
+		bitmap_fill_region(hmem->bitmap, 0, nchunk);
 
 		buf->hmem = hmem;
 
 		mlx5_spin_lock(&mctx->hugetlb_lock);
-		if (bitmap_avail(&hmem->bitmap))
+		if (nchunk != hmem->bmp_size)
 			list_add(&mctx->hugetlb_list, &hmem->entry);
 		else
 			list_add_tail(&mctx->hugetlb_list, &hmem->entry);
@@ -295,8 +182,8 @@ static int alloc_huge_buf(struct mlx5_context *mctx, struct mlx5_buf *buf,
 
 out_fork:
 	mlx5_spin_lock(&mctx->hugetlb_lock);
-	bitmap_free_range(&hmem->bitmap, buf->base, nchunk);
-	if (mlx5_bitmap_empty(&hmem->bitmap)) {
+	bitmap_zero_region(hmem->bitmap, buf->base, buf->base + nchunk);
+	if (bitmap_empty(hmem->bitmap, hmem->bmp_size)) {
 		list_del(&hmem->entry);
 		mlx5_spin_unlock(&mctx->hugetlb_lock);
 		free_huge_mem(hmem);
@@ -315,8 +202,8 @@ static void free_huge_buf(struct mlx5_context *ctx, struct mlx5_buf *buf)
 		return;
 
 	mlx5_spin_lock(&ctx->hugetlb_lock);
-	bitmap_free_range(&buf->hmem->bitmap, buf->base, nchunk);
-	if (mlx5_bitmap_empty(&buf->hmem->bitmap)) {
+	bitmap_zero_region(buf->hmem->bitmap, buf->base, buf->base + nchunk);
+	if (bitmap_empty(buf->hmem->bitmap, buf->hmem->bmp_size)) {
 		list_del(&buf->hmem->entry);
 		mlx5_spin_unlock(&ctx->hugetlb_lock);
 		free_huge_mem(buf->hmem);
diff --git a/providers/mlx5/dr_buddy.c b/providers/mlx5/dr_buddy.c
index e153677..8713fe4 100644
--- a/providers/mlx5/dr_buddy.c
+++ b/providers/mlx5/dr_buddy.c
@@ -34,23 +34,23 @@
  */
 
 #include <stdlib.h>
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 #include "mlx5dv_dr.h"
 
 struct dr_icm_pool;
 struct dr_icm_buddy_mem;
 
-static int dr_find_first_bit(const bitmap *set_addr,
-			     const bitmap *addr,
+static int dr_find_first_bit(const unsigned long *set_addr,
+			     const unsigned long *addr,
 			     unsigned int size)
 {
 	unsigned int set_size = (size - 1) / BITS_PER_LONG + 1;
 	unsigned long set_idx;
 
 	/* find the first free in the first level */
-	set_idx =  bitmap_ffs(set_addr, 0, set_size);
+	set_idx =  bitmap_find_first_bit(set_addr, 0, set_size);
 	/* find the next level */
-	return bitmap_ffs(addr, set_idx * BITS_PER_LONG, size);
+	return bitmap_find_first_bit(addr, set_idx * BITS_PER_LONG, size);
 }
 
 int dr_buddy_init(struct dr_icm_buddy_mem *buddy, uint32_t max_order)
@@ -161,7 +161,7 @@ static void dr_buddy_update_upper_bitmap(struct dr_icm_buddy_mem *buddy,
 
 	/* clear upper layer of search if needed */
 	dr_buddy_get_seg_borders(seg, &l, &h);
-	m = bitmap_ffs(buddy->bits[order], l, h);
+	m = bitmap_find_first_bit(buddy->bits[order], l, h);
 	if (m == h) /* nothing in the long that includes seg */
 		bitmap_clear_bit(buddy->set_bit[order], seg / BITS_PER_LONG);
 }
diff --git a/providers/mlx5/mlx5.h b/providers/mlx5/mlx5.h
index 1eca478..4656153 100644
--- a/providers/mlx5/mlx5.h
+++ b/providers/mlx5/mlx5.h
@@ -44,9 +44,8 @@
 #include <util/udma_barrier.h>
 #include <util/util.h>
 #include "mlx5-abi.h"
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 #include <ccan/list.h>
-#include "bitmap.h"
 #include <ccan/minmax.h>
 #include "mlx5dv.h"
 
@@ -289,7 +288,7 @@ struct mlx5_hca_cap_2_caps {
 };
 
 struct reserved_qpn_blk {
-	bitmap *bmp;
+	unsigned long *bmp;
 	uint32_t first_qpn;
 	struct list_node entry;
 	unsigned int next_avail_slot;
@@ -419,19 +418,11 @@ struct mlx5_context {
 	pthread_mutex_t			crypto_login_mutex;
 };
 
-struct mlx5_bitmap {
-	uint32_t		last;
-	uint32_t		top;
-	uint32_t		max;
-	uint32_t		avail;
-	uint32_t		mask;
-	unsigned long	       *table;
-};
-
 struct mlx5_hugetlb_mem {
 	int			shmid;
 	void		       *shmaddr;
-	struct mlx5_bitmap	bitmap;
+	unsigned long		*bitmap;
+	unsigned long		bmp_size;
 	struct list_node	entry;
 };
 
diff --git a/providers/mlx5/mlx5_vfio.c b/providers/mlx5/mlx5_vfio.c
index 3f1811d..b9cdfeb 100644
--- a/providers/mlx5/mlx5_vfio.c
+++ b/providers/mlx5/mlx5_vfio.c
@@ -142,7 +142,8 @@ static int mlx5_vfio_alloc_page(struct mlx5_vfio_context *ctx, uint64_t *iova)
 	pthread_mutex_lock(&ctx->mem_alloc.block_list_mutex);
 	while (true) {
 		list_for_each(&ctx->mem_alloc.block_list, page_block, next_block) {
-			pg = bitmap_ffs(page_block->free_pages, 0, MLX5_VFIO_BLOCK_NUM_PAGES);
+			pg = bitmap_find_first_bit(page_block->free_pages, 0,
+						   MLX5_VFIO_BLOCK_NUM_PAGES);
 			if (pg != MLX5_VFIO_BLOCK_NUM_PAGES) {
 				bitmap_clear_bit(page_block->free_pages, pg);
 				*iova = page_block->iova + pg * MLX5_ADAPTER_PAGE_SIZE;
diff --git a/providers/mlx5/mlx5_vfio.h b/providers/mlx5/mlx5_vfio.h
index 2165a22..88cc332 100644
--- a/providers/mlx5/mlx5_vfio.h
+++ b/providers/mlx5/mlx5_vfio.h
@@ -163,7 +163,7 @@ struct page_block {
 	void *page_ptr;
 	uint64_t iova;
 	struct list_node next_block;
-	BITMAP_DECLARE(free_pages, MLX5_VFIO_BLOCK_NUM_PAGES);
+	BMP_DECLARE(free_pages, MLX5_VFIO_BLOCK_NUM_PAGES);
 };
 
 struct vfio_mem_allocator {
diff --git a/providers/mlx5/mlx5dv_dr.h b/providers/mlx5/mlx5dv_dr.h
index 16e5340..3cc3035 100644
--- a/providers/mlx5/mlx5dv_dr.h
+++ b/providers/mlx5/mlx5dv_dr.h
@@ -35,7 +35,7 @@
 
 #include <ccan/list.h>
 #include <ccan/minmax.h>
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 #include <stdatomic.h>
 #include "mlx5dv.h"
 #include "mlx5_ifc.h"
@@ -1619,9 +1619,9 @@ int dr_send_postsend_action(struct mlx5dv_dr_domain *dmn,
 struct dr_icm_mr;
 
 struct dr_icm_buddy_mem {
-	bitmap			**bits;
+	unsigned long		**bits;
 	unsigned int		*num_free;
-	bitmap			**set_bit;
+	unsigned long		**set_bit;
 	uint32_t		max_order;
 	struct list_node	list_node;
 	struct dr_icm_mr	*icm_mr;
-- 
1.8.3.1

[PATCH rdma-core 3/5] libhns: Adapt bitmap usage to use util API

[Yishai Hadas]

From: Maher Sanalla <msanalla@nvidia.com>

Replace the usage of ccan bitmap with the newly added bitmap
implementation in util.

Signed-off-by: Maher Sanalla <msanalla@nvidia.com>
Reviewed-by: Avihai Horon <avihaih@nvidia.com>
Signed-off-by: Yishai Hadas <yishaih@nvidia.com>
---
 providers/hns/hns_roce_u.h    | 4 ++--
 providers/hns/hns_roce_u_db.c | 4 ++--
 2 files changed, 4 insertions(+), 4 deletions(-)

diff --git a/providers/hns/hns_roce_u.h b/providers/hns/hns_roce_u.h
index 2b4ba18..d786efb 100644
--- a/providers/hns/hns_roce_u.h
+++ b/providers/hns/hns_roce_u.h
@@ -42,7 +42,7 @@
 #include <util/util.h>
 #include <infiniband/verbs.h>
 #include <ccan/array_size.h>
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 #include <ccan/container_of.h>
 #include <linux/if_ether.h>
 #include "hns_roce_u_abi.h"
@@ -193,7 +193,7 @@ struct hns_roce_db_page {
 	struct hns_roce_buf	buf;
 	unsigned int		num_db;
 	unsigned int		use_cnt;
-	bitmap			*bitmap;
+	unsigned long		*bitmap;
 };
 
 struct hns_roce_context {
diff --git a/providers/hns/hns_roce_u_db.c b/providers/hns/hns_roce_u_db.c
index f7aaa6e..f5acac2 100644
--- a/providers/hns/hns_roce_u_db.c
+++ b/providers/hns/hns_roce_u_db.c
@@ -33,7 +33,7 @@
 #include <stdlib.h>
 #include <string.h>
 #include <stdio.h>
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 #include "hns_roce_u.h"
 #include "hns_roce_u_db.h"
 
@@ -109,7 +109,7 @@ void *hns_roce_alloc_db(struct hns_roce_context *ctx,
 found:
 	++page->use_cnt;
 
-	npos = bitmap_ffs(page->bitmap, 0, page->num_db);
+	npos = bitmap_find_first_bit(page->bitmap, 0, page->num_db);
 	bitmap_clear_bit(page->bitmap, npos);
 	db = page->buf.buf + npos * db_size[type];
 
-- 
1.8.3.1

[PATCH rdma-core 4/5] verbs: Adapt bitmap usage to use util API

[Yishai Hadas]

From: Maher Sanalla <msanalla@nvidia.com>

Replace the usage of ccan bitmap with the newly added bitmap
implementation in util.

Signed-off-by: Maher Sanalla <msanalla@nvidia.com>
Reviewed-by: Avihai Horon <avihaih@nvidia.com>
Signed-off-by: Yishai Hadas <yishaih@nvidia.com>
---
 libibverbs/ibverbs.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/libibverbs/ibverbs.h b/libibverbs/ibverbs.h
index 5e60ace..33f83a7 100644
--- a/libibverbs/ibverbs.h
+++ b/libibverbs/ibverbs.h
@@ -37,7 +37,7 @@
 #include <pthread.h>
 
 #include <infiniband/driver.h>
-#include <ccan/bitmap.h>
+#include <util/bitmap.h>
 
 #define INIT		__attribute__((constructor))
 
@@ -70,7 +70,7 @@ void load_drivers(void);
 #endif
 
 struct verbs_ex_private {
-	BITMAP_DECLARE(unsupported_ioctls, VERBS_OPS_NUM);
+	BMP_DECLARE(unsupported_ioctls, VERBS_OPS_NUM);
 	uint32_t driver_id;
 	bool use_ioctl_write;
 	struct verbs_context_ops ops;
-- 
1.8.3.1

[PATCH rdma-core 5/5] ccan: Remove bitmap code

[Yishai Hadas]

From: Maher Sanalla <msanalla@nvidia.com>

Removes ccan bitmap implementation, along with adjustments to the
ccan Makefile.

Signed-off-by: Maher Sanalla <msanalla@nvidia.com>
Reviewed-by: Avihai Horon <avihaih@nvidia.com>
Signed-off-by: Yishai Hadas <yishaih@nvidia.com>
---
 ccan/CMakeLists.txt |   2 -
 ccan/bitmap.c       | 125 ---------------------------
 ccan/bitmap.h       | 239 ----------------------------------------------------
 3 files changed, 366 deletions(-)
 delete mode 100644 ccan/bitmap.c
 delete mode 100644 ccan/bitmap.h

diff --git a/ccan/CMakeLists.txt b/ccan/CMakeLists.txt
index 5c5c6a2..d370a8e 100644
--- a/ccan/CMakeLists.txt
+++ b/ccan/CMakeLists.txt
@@ -1,6 +1,5 @@
 publish_internal_headers(ccan
   array_size.h
-  bitmap.h
   build_assert.h
   check_type.h
   compiler.h
@@ -13,7 +12,6 @@ publish_internal_headers(ccan
   )
 
 set(C_FILES
-  bitmap.c
   ilog.c
   list.c
   str.c
diff --git a/ccan/bitmap.c b/ccan/bitmap.c
deleted file mode 100644
index ea5531c..0000000
--- a/ccan/bitmap.c
+++ /dev/null
@@ -1,125 +0,0 @@
-/* Licensed under LGPLv2.1+ - see LICENSE file for details */
-
-#include "config.h"
-
-#include <ccan/bitmap.h>
-
-#include <assert.h>
-
-#define BIT_ALIGN_DOWN(n)	((n) & ~(BITMAP_WORD_BITS - 1))
-#define BIT_ALIGN_UP(n)		BIT_ALIGN_DOWN((n) + BITMAP_WORD_BITS - 1)
-
-void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m)
-{
-	unsigned long an = BIT_ALIGN_UP(n);
-	unsigned long am = BIT_ALIGN_DOWN(m);
-	bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
-	bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
-
-	assert(m >= n);
-
-	if (am < an) {
-		BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask & tailmask);
-		return;
-	}
-
-	if (an > n)
-		BITMAP_WORD(bmap, n) &= ~bitmap_bswap(headmask);
-
-	if (am > an)
-		memset(&BITMAP_WORD(bmap, an), 0,
-		       (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
-
-	if (m > am)
-		BITMAP_WORD(bmap, m) &= ~bitmap_bswap(tailmask);
-}
-
-void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m)
-{
-	unsigned long an = BIT_ALIGN_UP(n);
-	unsigned long am = BIT_ALIGN_DOWN(m);
-	bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
-	bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
-
-	assert(m >= n);
-
-	if (am < an) {
-		BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask & tailmask);
-		return;
-	}
-
-	if (an > n)
-		BITMAP_WORD(bmap, n) |= bitmap_bswap(headmask);
-
-	if (am > an)
-		memset(&BITMAP_WORD(bmap, an), 0xff,
-		       (am - an) / BITMAP_WORD_BITS * sizeof(bitmap_word));
-
-	if (m > am)
-		BITMAP_WORD(bmap, m) |= bitmap_bswap(tailmask);
-}
-
-static int bitmap_clz(bitmap_word w)
-{
-#if HAVE_BUILTIN_CLZL
-	return __builtin_clzl(w);
-#else
-	int lz = 0;
-	bitmap_word mask = 1UL << (BITMAP_WORD_BITS - 1);
-
-	while (!(w & mask)) {
-		lz++;
-		mask >>= 1;
-	}
-
-	return lz;
-#endif
-}
-
-unsigned long bitmap_ffs(const bitmap *bmap,
-			 unsigned long n, unsigned long m)
-{
-	unsigned long an = BIT_ALIGN_UP(n);
-	unsigned long am = BIT_ALIGN_DOWN(m);
-	bitmap_word headmask = -1ULL >> (n % BITMAP_WORD_BITS);
-	bitmap_word tailmask = ~(-1ULL >> (m % BITMAP_WORD_BITS));
-
-	assert(m >= n);
-
-	if (am < an) {
-		bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n));
-
-		w &= (headmask & tailmask);
-
-		return w ? am + bitmap_clz(w) : m;
-	}
-
-	if (an > n) {
-		bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, n));
-
-		w &= headmask;
-
-		if (w)
-			return BIT_ALIGN_DOWN(n) + bitmap_clz(w);
-	}
-
-	while (an < am) {
-		bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, an));
-
-		if (w)
-			return an + bitmap_clz(w);
-
-		an += BITMAP_WORD_BITS;
-	}
-
-	if (m > am) {
-		bitmap_word w = bitmap_bswap(BITMAP_WORD(bmap, m));
-
-		w &= tailmask;
-
-		if (w)
-			return am + bitmap_clz(w);
-	}
-
-	return m;
-}
diff --git a/ccan/bitmap.h b/ccan/bitmap.h
deleted file mode 100644
index ff0b8c8..0000000
--- a/ccan/bitmap.h
+++ /dev/null
@@ -1,239 +0,0 @@
-/* Licensed under LGPLv2+ - see LICENSE file for details */
-#ifndef CCAN_BITMAP_H_
-#define CCAN_BITMAP_H_
-
-#include <stdbool.h>
-#include <stdlib.h>
-#include <string.h>
-#include <limits.h>
-
-typedef unsigned long bitmap_word;
-
-#define BITMAP_WORD_BITS	(sizeof(bitmap_word) * CHAR_BIT)
-#define BITMAP_NWORDS(_n)	\
-	(((_n) + BITMAP_WORD_BITS - 1) / BITMAP_WORD_BITS)
-
-/*
- * We wrap each word in a structure for type checking.
- */
-typedef struct {
-	bitmap_word w;
-} bitmap;
-
-#define BITMAP_DECLARE(_name, _nbits) \
-	bitmap (_name)[BITMAP_NWORDS(_nbits)]
-
-static inline size_t bitmap_sizeof(unsigned long nbits)
-{
-	return BITMAP_NWORDS(nbits) * sizeof(bitmap_word);
-}
-
-static inline bitmap_word bitmap_bswap(bitmap_word w)
-{
-	/* We do not need to have the bitmap in any specific endianness */
-	return w;
-}
-
-#define BITMAP_WORD(_bm, _n)	((_bm)[(_n) / BITMAP_WORD_BITS].w)
-#define BITMAP_WORDBIT(_n) 	\
-	(bitmap_bswap(1UL << (BITMAP_WORD_BITS - ((_n) % BITMAP_WORD_BITS) - 1)))
-
-#define BITMAP_HEADWORDS(_nbits) \
-	((_nbits) / BITMAP_WORD_BITS)
-#define BITMAP_HEADBYTES(_nbits) \
-	(BITMAP_HEADWORDS(_nbits) * sizeof(bitmap_word))
-
-#define BITMAP_TAILWORD(_bm, _nbits) \
-	((_bm)[BITMAP_HEADWORDS(_nbits)].w)
-#define BITMAP_HASTAIL(_nbits)	(((_nbits) % BITMAP_WORD_BITS) != 0)
-#define BITMAP_TAILBITS(_nbits)	\
-	(bitmap_bswap(~(-1UL >> ((_nbits) % BITMAP_WORD_BITS))))
-#define BITMAP_TAIL(_bm, _nbits) \
-	(BITMAP_TAILWORD(_bm, _nbits) & BITMAP_TAILBITS(_nbits))
-
-static inline void bitmap_set_bit(bitmap *bmap, unsigned long n)
-{
-	BITMAP_WORD(bmap, n) |= BITMAP_WORDBIT(n);
-}
-
-static inline void bitmap_clear_bit(bitmap *bmap, unsigned long n)
-{
-	BITMAP_WORD(bmap, n) &= ~BITMAP_WORDBIT(n);
-}
-
-static inline void bitmap_change_bit(bitmap *bmap, unsigned long n)
-{
-	BITMAP_WORD(bmap, n) ^= BITMAP_WORDBIT(n);
-}
-
-static inline bool bitmap_test_bit(const bitmap *bmap, unsigned long n)
-{
-	return !!(BITMAP_WORD(bmap, n) & BITMAP_WORDBIT(n));
-}
-
-void bitmap_zero_range(bitmap *bmap, unsigned long n, unsigned long m);
-void bitmap_fill_range(bitmap *bmap, unsigned long n, unsigned long m);
-
-static inline void bitmap_zero(bitmap *bmap, unsigned long nbits)
-{
-	memset(bmap, 0, bitmap_sizeof(nbits));
-}
-
-static inline void bitmap_fill(bitmap *bmap, unsigned long nbits)
-{
-	memset(bmap, 0xff, bitmap_sizeof(nbits));
-}
-
-static inline void bitmap_copy(bitmap *dst, const bitmap *src,
-			       unsigned long nbits)
-{
-	memcpy(dst, src, bitmap_sizeof(nbits));
-}
-
-#define BITMAP_DEF_BINOP(_name, _op) \
-	static inline void bitmap_##_name(bitmap *dst, bitmap *src1, bitmap *src2, \
-					  unsigned long nbits)		\
-	{ \
-		unsigned long i = 0; \
-		for (i = 0; i < BITMAP_NWORDS(nbits); i++) { \
-			dst[i].w = src1[i].w _op src2[i].w; \
-		} \
-	}
-
-BITMAP_DEF_BINOP(and, &)
-BITMAP_DEF_BINOP(or, |)
-BITMAP_DEF_BINOP(xor, ^)
-BITMAP_DEF_BINOP(andnot, & ~)
-
-#undef BITMAP_DEF_BINOP
-
-static inline void bitmap_complement(bitmap *dst, const bitmap *src,
-				     unsigned long nbits)
-{
-	unsigned long i;
-
-	for (i = 0; i < BITMAP_NWORDS(nbits); i++)
-		dst[i].w = ~src[i].w;
-}
-
-static inline bool bitmap_equal(const bitmap *src1, const bitmap *src2,
-				unsigned long nbits)
-{
-	return (memcmp(src1, src2, BITMAP_HEADBYTES(nbits)) == 0)
-		&& (!BITMAP_HASTAIL(nbits)
-		    || (BITMAP_TAIL(src1, nbits) == BITMAP_TAIL(src2, nbits)));
-}
-
-static inline bool bitmap_intersects(const bitmap *src1, const bitmap *src2,
-				     unsigned long nbits)
-{
-	unsigned long i;
-
-	for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
-		if (src1[i].w & src2[i].w)
-			return true;
-	}
-	if (BITMAP_HASTAIL(nbits) &&
-	    (BITMAP_TAIL(src1, nbits) & BITMAP_TAIL(src2, nbits)))
-		return true;
-	return false;
-}
-
-static inline bool bitmap_subset(const bitmap *src1, const bitmap *src2,
-				 unsigned long nbits)
-{
-	unsigned long i;
-
-	for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
-		if (src1[i].w  & ~src2[i].w)
-			return false;
-	}
-	if (BITMAP_HASTAIL(nbits) &&
-	    (BITMAP_TAIL(src1, nbits) & ~BITMAP_TAIL(src2, nbits)))
-		return false;
-	return true;
-}
-
-static inline bool bitmap_full(const bitmap *bmap, unsigned long nbits)
-{
-	unsigned long i;
-
-	for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
-		if (bmap[i].w != -1UL)
-			return false;
-	}
-	if (BITMAP_HASTAIL(nbits) &&
-	    (BITMAP_TAIL(bmap, nbits) != BITMAP_TAILBITS(nbits)))
-		return false;
-
-	return true;
-}
-
-static inline bool bitmap_empty(const bitmap *bmap, unsigned long nbits)
-{
-	unsigned long i;
-
-	for (i = 0; i < BITMAP_HEADWORDS(nbits); i++) {
-		if (bmap[i].w != 0)
-			return false;
-	}
-	if (BITMAP_HASTAIL(nbits) && (BITMAP_TAIL(bmap, nbits) != 0))
-		return false;
-
-	return true;
-}
-
-unsigned long bitmap_ffs(const bitmap *bmap,
-			 unsigned long n, unsigned long m);
-
-/*
- * Allocation functions
- */
-static inline bitmap *bitmap_alloc(unsigned long nbits)
-{
-	return malloc(bitmap_sizeof(nbits));
-}
-
-static inline bitmap *bitmap_alloc0(unsigned long nbits)
-{
-	bitmap *bmap;
-
-	bmap = bitmap_alloc(nbits);
-	if (bmap)
-		bitmap_zero(bmap, nbits);
-	return bmap;
-}
-
-static inline bitmap *bitmap_alloc1(unsigned long nbits)
-{
-	bitmap *bmap;
-
-	bmap = bitmap_alloc(nbits);
-	if (bmap)
-		bitmap_fill(bmap, nbits);
-	return bmap;
-}
-
-static inline bitmap *bitmap_realloc0(bitmap *bmap, unsigned long obits,
-				      unsigned long nbits)
-{
-	bmap = realloc(bmap, bitmap_sizeof(nbits));
-
-	if ((nbits > obits) && bmap)
-		bitmap_zero_range(bmap, obits, nbits);
-
-	return bmap;
-}
-
-static inline bitmap *bitmap_realloc1(bitmap *bmap, unsigned long obits,
-				      unsigned long nbits)
-{
-	bmap = realloc(bmap, bitmap_sizeof(nbits));
-
-	if ((nbits > obits) && bmap)
-		bitmap_fill_range(bmap, obits, nbits);
-
-	return bmap;
-}
-
-#endif /* CCAN_BITMAP_H_ */
-- 
1.8.3.1

Re: [PATCH rdma-core 0/5] Add new bitmap API

[Yishai Hadas]

On 2/28/2022 10:48 AM, Yishai Hadas wrote:
> This series adds new bitmap implementation to util directory which replaces the
> ccan equivalent.
>
> The ccan/bitmap stuff was published under the LGPLv2+ license which is not
> fitting in rdma-core.
>
> As of the above, the applicable bitmap code in rdma-core was adapted to use the
> util new API.
>
> PR was sent:
> https://github.com/linux-rdma/rdma-core/pull/1144
>
> Maher Sanalla (5):
>    util: Add new bitmap API
>    mlx5: Adapt bitmap usage to use util API
>    libhns: Adapt bitmap usage to use util API
>    verbs: Adapt bitmap usage to use util API
>    ccan: Remove bitmap code
>
>   ccan/CMakeLists.txt           |   2 -
>   ccan/bitmap.c                 | 125 ----------------------
>   ccan/bitmap.h                 | 239 ------------------------------------------
>   libibverbs/ibverbs.h          |   4 +-
>   providers/hns/hns_roce_u.h    |   4 +-
>   providers/hns/hns_roce_u_db.c |   4 +-
>   providers/mlx5/bitmap.h       | 111 --------------------
>   providers/mlx5/buf.c          | 187 +++++++--------------------------
>   providers/mlx5/dr_buddy.c     |  12 +--
>   providers/mlx5/mlx5.h         |  17 +--
>   providers/mlx5/mlx5_vfio.c    |   3 +-
>   providers/mlx5/mlx5_vfio.h    |   2 +-
>   providers/mlx5/mlx5dv_dr.h    |   6 +-
>   util/CMakeLists.txt           |   2 +
>   util/bitmap.c                 | 180 +++++++++++++++++++++++++++++++
>   util/bitmap.h                 | 120 +++++++++++++++++++++
>   util/util.h                   |   1 +
>   17 files changed, 362 insertions(+), 657 deletions(-)
>   delete mode 100644 ccan/bitmap.c
>   delete mode 100644 ccan/bitmap.h
>   delete mode 100644 providers/mlx5/bitmap.h
>   create mode 100644 util/bitmap.c
>   create mode 100644 util/bitmap.h
>
The PR was merged.

Yishai