[dm-devel] [PATCH v2 08/35] libmultipath: create bitfield abstraction
mwilck at suse.com
mwilck at suse.com
Wed Aug 12 11:32:31 UTC 2020
From: Martin Wilck <mwilck at suse.com>
In e32d521d ("libmultipath: coalesce_paths: fix size mismatch handling"),
we introduced simple bitmap handling functions. We can do better. This
patch introduces a bitfield type with overflow detection and a
find_first_set() method.
Use this in coalesce_paths(), and adapt the unit tests. Also, add
unit tests for "odd" bitfield sizes; so far we tested only multiples
of 64.
Signed-off-by: Martin Wilck <mwilck at suse.com>
---
libmultipath/configure.c | 9 +-
libmultipath/util.c | 22 ++++
libmultipath/util.h | 56 +++++++++-
tests/util.c | 231 ++++++++++++++++++++++++++++++++++-----
4 files changed, 281 insertions(+), 37 deletions(-)
diff --git a/libmultipath/configure.c b/libmultipath/configure.c
index 96c7961..fe590f4 100644
--- a/libmultipath/configure.c
+++ b/libmultipath/configure.c
@@ -1092,7 +1092,7 @@ int coalesce_paths (struct vectors * vecs, vector newmp, char * refwwid,
vector pathvec = vecs->pathvec;
struct config *conf;
int allow_queueing;
- uint64_t *size_mismatch_seen;
+ struct bitfield *size_mismatch_seen;
/* ignore refwwid if it's empty */
if (refwwid && !strlen(refwwid))
@@ -1106,8 +1106,7 @@ int coalesce_paths (struct vectors * vecs, vector newmp, char * refwwid,
if (VECTOR_SIZE(pathvec) == 0)
return CP_OK;
- size_mismatch_seen = calloc((VECTOR_SIZE(pathvec) - 1) / 64 + 1,
- sizeof(uint64_t));
+ size_mismatch_seen = alloc_bitfield(VECTOR_SIZE(pathvec));
if (size_mismatch_seen == NULL)
return CP_FAIL;
@@ -1131,7 +1130,7 @@ int coalesce_paths (struct vectors * vecs, vector newmp, char * refwwid,
}
/* 2. if path already coalesced, or seen and discarded */
- if (pp1->mpp || is_bit_set_in_array(k, size_mismatch_seen))
+ if (pp1->mpp || is_bit_set_in_bitfield(k, size_mismatch_seen))
continue;
/* 3. if path has disappeared */
@@ -1183,7 +1182,7 @@ int coalesce_paths (struct vectors * vecs, vector newmp, char * refwwid,
"Discard", pp2->dev, pp2->size,
mpp->size);
mpp->action = ACT_REJECT;
- set_bit_in_array(i, size_mismatch_seen);
+ set_bit_in_bitfield(i, size_mismatch_seen);
}
}
verify_paths(mpp, vecs);
diff --git a/libmultipath/util.c b/libmultipath/util.c
index 3c43f28..3e2708a 100644
--- a/libmultipath/util.c
+++ b/libmultipath/util.c
@@ -404,3 +404,25 @@ void close_fd(void *arg)
{
close((long)arg);
}
+
+struct bitfield *alloc_bitfield(unsigned int maxbit)
+{
+ unsigned int n;
+ struct bitfield *bf;
+
+ if (maxbit == 0) {
+ errno = EINVAL;
+ return NULL;
+ }
+
+ n = (maxbit - 1) / bits_per_slot + 1;
+ bf = calloc(1, sizeof(struct bitfield) + n * sizeof(bitfield_t));
+ if (bf)
+ bf->len = maxbit;
+ return bf;
+}
+
+void _log_bitfield_overflow(const char *f, unsigned int bit, unsigned int len)
+{
+ condlog(0, "%s: bitfield overflow: %u >= %u", f, bit, len);
+}
diff --git a/libmultipath/util.h b/libmultipath/util.h
index df75c4f..7ed30c7 100644
--- a/libmultipath/util.h
+++ b/libmultipath/util.h
@@ -1,6 +1,9 @@
#ifndef _UTIL_H
#define _UTIL_H
+#include <stdlib.h>
+#include <string.h>
+#include <limits.h>
#include <sys/types.h>
/* for rlim_t */
#include <sys/resource.h>
@@ -51,19 +54,60 @@ struct scandir_result {
};
void free_scandir_result(struct scandir_result *);
-static inline bool is_bit_set_in_array(unsigned int bit, const uint64_t *arr)
+/*
+ * ffsll() is also available on glibc < 2.27 if _GNU_SOURCE is defined.
+ * But relying on that would require that every program using this header file
+ * set _GNU_SOURCE during compilation, because otherwise the library and the
+ * program would use different types for bitfield_t, causing errors.
+ * That's too error prone, so if in doubt, use ffs().
+ */
+#if __GLIBC_PREREQ(2, 27)
+typedef unsigned long long int bitfield_t;
+#define _ffs(x) ffsll(x)
+#else
+typedef unsigned int bitfield_t;
+#define _ffs(x) ffs(x)
+#endif
+#define bits_per_slot (sizeof(bitfield_t) * CHAR_BIT)
+
+struct bitfield {
+ unsigned int len;
+ bitfield_t bits[];
+};
+
+struct bitfield *alloc_bitfield(unsigned int maxbit);
+
+void _log_bitfield_overflow(const char *f, unsigned int bit, unsigned int len);
+#define log_bitfield_overflow(bit, len) \
+ _log_bitfield_overflow(__func__, bit, len)
+
+static inline bool is_bit_set_in_bitfield(unsigned int bit,
+ const struct bitfield *bf)
{
- return arr[bit / 64] & (1ULL << (bit % 64)) ? 1 : 0;
+ if (bit >= bf->len) {
+ log_bitfield_overflow(bit, bf->len);
+ return false;
+ }
+ return !!(bf->bits[bit / bits_per_slot] &
+ (1ULL << (bit % bits_per_slot)));
}
-static inline void set_bit_in_array(unsigned int bit, uint64_t *arr)
+static inline void set_bit_in_bitfield(unsigned int bit, struct bitfield *bf)
{
- arr[bit / 64] |= (1ULL << (bit % 64));
+ if (bit >= bf->len) {
+ log_bitfield_overflow(bit, bf->len);
+ return;
+ }
+ bf->bits[bit / bits_per_slot] |= (1ULL << (bit % bits_per_slot));
}
-static inline void clear_bit_in_array(unsigned int bit, uint64_t *arr)
+static inline void clear_bit_in_bitfield(unsigned int bit, struct bitfield *bf)
{
- arr[bit / 64] &= ~(1ULL << (bit % 64));
+ if (bit >= bf->len) {
+ log_bitfield_overflow(bit, bf->len);
+ return;
+ }
+ bf->bits[bit / bits_per_slot] &= ~(1ULL << (bit % bits_per_slot));
}
#endif /* _UTIL_H */
diff --git a/tests/util.c b/tests/util.c
index 6d12fda..fa869cd 100644
--- a/tests/util.c
+++ b/tests/util.c
@@ -164,19 +164,25 @@ static int test_basenamecpy(void)
static void test_bitmask_1(void **state)
{
- uint64_t arr[BITARR_SZ];
+ struct bitfield *bf;
+ uint64_t *arr;
int i, j, k, m, b;
- memset(arr, 0, sizeof(arr));
+ bf = alloc_bitfield(BITARR_SZ * 64);
+ assert_non_null(bf);
+ assert_int_equal(bf->len, BITARR_SZ * 64);
+ arr = (uint64_t *)bf->bits;
for (j = 0; j < BITARR_SZ; j++) {
for (i = 0; i < 64; i++) {
b = 64 * j + i;
- assert(!is_bit_set_in_array(b, arr));
- set_bit_in_array(b, arr);
+ assert(!is_bit_set_in_bitfield(b, bf));
+ set_bit_in_bitfield(b, bf);
for (k = 0; k < BITARR_SZ; k++) {
+#if 0
printf("b = %d j = %d k = %d a = %"PRIx64"\n",
b, j, k, arr[k]);
+#endif
if (k == j)
assert_int_equal(arr[j], 1ULL << i);
else
@@ -184,39 +190,44 @@ static void test_bitmask_1(void **state)
}
for (m = 0; m < 64; m++)
if (i == m)
- assert(is_bit_set_in_array(64 * j + m,
- arr));
+ assert(is_bit_set_in_bitfield(64 * j + m,
+ bf));
else
- assert(!is_bit_set_in_array(64 * j + m,
- arr));
- clear_bit_in_array(b, arr);
- assert(!is_bit_set_in_array(b, arr));
+ assert(!is_bit_set_in_bitfield(64 * j + m,
+ bf));
+ clear_bit_in_bitfield(b, bf);
+ assert(!is_bit_set_in_bitfield(b, bf));
for (k = 0; k < BITARR_SZ; k++)
assert_int_equal(arr[k], 0ULL);
}
}
+ free(bf);
}
static void test_bitmask_2(void **state)
{
- uint64_t arr[BITARR_SZ];
+ struct bitfield *bf;
+ uint64_t *arr;
int i, j, k, m, b;
- memset(arr, 0, sizeof(arr));
+ bf = alloc_bitfield(BITARR_SZ * 64);
+ assert_non_null(bf);
+ assert_int_equal(bf->len, BITARR_SZ * 64);
+ arr = (uint64_t *)bf->bits;
for (j = 0; j < BITARR_SZ; j++) {
for (i = 0; i < 64; i++) {
b = 64 * j + i;
- assert(!is_bit_set_in_array(b, arr));
- set_bit_in_array(b, arr);
+ assert(!is_bit_set_in_bitfield(b, bf));
+ set_bit_in_bitfield(b, bf);
for (m = 0; m < 64; m++)
if (m <= i)
- assert(is_bit_set_in_array(64 * j + m,
- arr));
+ assert(is_bit_set_in_bitfield(64 * j + m,
+ bf));
else
- assert(!is_bit_set_in_array(64 * j + m,
- arr));
- assert(is_bit_set_in_array(b, arr));
+ assert(!is_bit_set_in_bitfield(64 * j + m,
+ bf));
+ assert(is_bit_set_in_bitfield(b, bf));
for (k = 0; k < BITARR_SZ; k++) {
if (k < j || (k == j && i == 63))
assert_int_equal(arr[k], ~0ULL);
@@ -232,16 +243,16 @@ static void test_bitmask_2(void **state)
for (j = 0; j < BITARR_SZ; j++) {
for (i = 0; i < 64; i++) {
b = 64 * j + i;
- assert(is_bit_set_in_array(b, arr));
- clear_bit_in_array(b, arr);
+ assert(is_bit_set_in_bitfield(b, bf));
+ clear_bit_in_bitfield(b, bf);
for (m = 0; m < 64; m++)
if (m <= i)
- assert(!is_bit_set_in_array(64 * j + m,
- arr));
+ assert(!is_bit_set_in_bitfield(64 * j + m,
+ bf));
else
- assert(is_bit_set_in_array(64 * j + m,
- arr));
- assert(!is_bit_set_in_array(b, arr));
+ assert(is_bit_set_in_bitfield(64 * j + m,
+ bf));
+ assert(!is_bit_set_in_bitfield(b, bf));
for (k = 0; k < BITARR_SZ; k++) {
if (k < j || (k == j && i == 63))
assert_int_equal(arr[k], 0ULL);
@@ -254,13 +265,181 @@ static void test_bitmask_2(void **state)
}
}
}
+ free(bf);
}
+/*
+ * Test operations on a 0-length bitfield
+ */
+static void test_bitmask_len_0(void **state)
+{
+ struct bitfield *bf;
+
+ bf = alloc_bitfield(0);
+ assert_null(bf);
+}
+
+static void _test_bitmask_small(unsigned int n)
+{
+ struct bitfield *bf;
+ uint64_t *arr;
+
+ assert(n <= 64);
+ assert(n >= 1);
+
+ bf = alloc_bitfield(n);
+ assert_non_null(bf);
+ assert_int_equal(bf->len, n);
+ arr = (uint64_t *)bf->bits;
+
+ assert_int_equal(*arr, 0);
+
+ set_bit_in_bitfield(n + 1, bf);
+ assert_int_equal(*arr, 0);
+
+ set_bit_in_bitfield(n, bf);
+ assert_int_equal(*arr, 0);
+
+ set_bit_in_bitfield(n - 1, bf);
+ assert_int_equal(*arr, 1ULL << (n - 1));
+
+ clear_bit_in_bitfield(n - 1, bf);
+ assert_int_equal(*arr, 0);
+
+ set_bit_in_bitfield(0, bf);
+ assert_int_equal(*arr, 1);
+
+ free(bf);
+}
+
+static void _test_bitmask_small_2(unsigned int n)
+{
+ struct bitfield *bf;
+ uint64_t *arr;
+
+ assert(n <= 128);
+ assert(n >= 65);
+
+ bf = alloc_bitfield(n);
+ assert_non_null(bf);
+ assert_int_equal(bf->len, n);
+ arr = (uint64_t *)bf->bits;
+
+ assert_int_equal(arr[0], 0);
+ assert_int_equal(arr[1], 0);
+
+ set_bit_in_bitfield(n + 1, bf);
+ assert_int_equal(arr[0], 0);
+ assert_int_equal(arr[1], 0);
+
+ set_bit_in_bitfield(n, bf);
+ assert_int_equal(arr[0], 0);
+ assert_int_equal(arr[1], 0);
+
+ set_bit_in_bitfield(n - 1, bf);
+ assert_int_equal(arr[0], 0);
+ assert_int_equal(arr[1], 1ULL << (n - 65));
+
+ set_bit_in_bitfield(0, bf);
+ assert_int_equal(arr[0], 1);
+ assert_int_equal(arr[1], 1ULL << (n - 65));
+
+ set_bit_in_bitfield(64, bf);
+ assert_int_equal(arr[0], 1);
+ assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
+
+ clear_bit_in_bitfield(0, bf);
+ assert_int_equal(arr[0], 0);
+ assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
+
+ free(bf);
+}
+
+static void test_bitmask_len_1(void **state)
+{
+ _test_bitmask_small(1);
+}
+
+static void test_bitmask_len_2(void **state)
+{
+ _test_bitmask_small(2);
+}
+
+static void test_bitmask_len_3(void **state)
+{
+ _test_bitmask_small(3);
+}
+
+static void test_bitmask_len_23(void **state)
+{
+ _test_bitmask_small(23);
+}
+
+static void test_bitmask_len_63(void **state)
+{
+ _test_bitmask_small(63);
+}
+
+static void test_bitmask_len_64(void **state)
+{
+ _test_bitmask_small(63);
+}
+
+static void test_bitmask_len_65(void **state)
+{
+ _test_bitmask_small_2(65);
+}
+
+static void test_bitmask_len_66(void **state)
+{
+ _test_bitmask_small_2(66);
+}
+
+static void test_bitmask_len_67(void **state)
+{
+ _test_bitmask_small_2(67);
+}
+
+static void test_bitmask_len_103(void **state)
+{
+ _test_bitmask_small_2(103);
+}
+
+static void test_bitmask_len_126(void **state)
+{
+ _test_bitmask_small_2(126);
+}
+
+static void test_bitmask_len_127(void **state)
+{
+ _test_bitmask_small_2(127);
+}
+
+static void test_bitmask_len_128(void **state)
+{
+ _test_bitmask_small_2(128);
+}
+
+
static int test_bitmasks(void)
{
const struct CMUnitTest tests[] = {
cmocka_unit_test(test_bitmask_1),
cmocka_unit_test(test_bitmask_2),
+ cmocka_unit_test(test_bitmask_len_0),
+ cmocka_unit_test(test_bitmask_len_1),
+ cmocka_unit_test(test_bitmask_len_2),
+ cmocka_unit_test(test_bitmask_len_3),
+ cmocka_unit_test(test_bitmask_len_23),
+ cmocka_unit_test(test_bitmask_len_63),
+ cmocka_unit_test(test_bitmask_len_64),
+ cmocka_unit_test(test_bitmask_len_65),
+ cmocka_unit_test(test_bitmask_len_66),
+ cmocka_unit_test(test_bitmask_len_67),
+ cmocka_unit_test(test_bitmask_len_103),
+ cmocka_unit_test(test_bitmask_len_126),
+ cmocka_unit_test(test_bitmask_len_127),
+ cmocka_unit_test(test_bitmask_len_128),
};
return cmocka_run_group_tests(tests, NULL, NULL);
}
--
2.28.0
More information about the dm-devel
mailing list