diff mbox series

[08/35] libmultipath: create bitfield abstraction

Message ID 20200709101620.6786-9-mwilck@suse.com (mailing list archive)
State Not Applicable, archived
Delegated to: christophe varoqui
Headers show
Series multipath-tools series part I: minor changes | expand

Commit Message

Martin Wilck July 9, 2020, 10:15 a.m. UTC 
From: Martin Wilck <mwilck@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@suse.com>
---
 libmultipath/configure.c |   9 +-
 libmultipath/util.c      |  35 ++++++
 libmultipath/util.h      |  57 ++++++++-
 tests/util.c             | 263 +++++++++++++++++++++++++++++++++++----
 4 files changed, 327 insertions(+), 37 deletions(-)

Comments

Benjamin Marzinski July 16, 2020, 9:17 p.m. UTC | #1 
On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com wrote:
> From: Martin Wilck <mwilck@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@suse.com>
> ---
>  libmultipath/configure.c |   9 +-
>  libmultipath/util.c      |  35 ++++++
>  libmultipath/util.h      |  57 ++++++++-
>  tests/util.c             | 263 +++++++++++++++++++++++++++++++++++----
>  4 files changed, 327 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..46cacd4 100644
> --- a/libmultipath/util.c
> +++ b/libmultipath/util.c
> @@ -404,3 +404,38 @@ void close_fd(void *arg)
>  {
>  	close((long)arg);
>  }
> +
> +struct bitfield *alloc_bitfield(unsigned int maxbit)
> +{
> +	unsigned int n;
> +	struct bitfield *bf;
> +
> +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;

What's the point in accepting 0? That's an empty bitmap.

> +	bf = calloc(1, sizeof(struct bitfield) + n * sizeof(bitfield_t));

Need to check that bf got set before dereferencing it.

> +	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);
> +}
> +
> +unsigned int find_first_set(const struct bitfield *bf)
> +{
> +	unsigned int b = 0, i, n;
> +
> +	for (i = 0; i < bf->len; i+= bits_per_slot) {
> +		b = _ffs(bf->bits[i / bits_per_slot]);
> +		if (b != 0)
> +			break;
> +	};
> +	if (b == 0)
> +		return 0;
> +
> +	n = i + b;
> +	if (n <= bf->len)
> +		return n;
> +
> +	return 0;
> +}

This is neat and all, but what's it for?  I didn't see it used in the
rest of the patches.  Did I miss it, or do you have a future use for it?

> diff --git a/libmultipath/util.h b/libmultipath/util.h
> index df75c4f..ec6de6d 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,61 @@ 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));
>  }
>  
> +unsigned int find_first_set(const struct bitfield *bf);
>  #endif /* _UTIL_H */
> diff --git a/tests/util.c b/tests/util.c
> index 6d12fda..db7c05f 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,46 @@ 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));
> +			assert_int_equal(find_first_set(bf), b + 1);
> +			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));
> +			assert_int_equal(find_first_set(bf), 1);
>  			for (k = 0; k < BITARR_SZ; k++) {
>  				if (k < j || (k == j && i == 63))
>  					assert_int_equal(arr[k], ~0ULL);
> @@ -232,16 +245,20 @@ 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));
> +			if (b == 64 * BITARR_SZ - 1)
> +				assert_int_equal(find_first_set(bf), 0);
> +			else
> +				assert_int_equal(find_first_set(bf), b + 2);
>  			for (k = 0; k < BITARR_SZ; k++) {
>  				if (k < j || (k == j && i == 63))
>  					assert_int_equal(arr[k], 0ULL);
> @@ -254,13 +271,207 @@ 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_non_null(bf);
> +	assert_int_equal(bf->len, 0);
> +	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
> +	assert_int_equal(is_bit_set_in_bitfield(1, bf), 0);
> +	assert_int_equal(find_first_set(bf), 0);
> +	set_bit_in_bitfield(0, bf);
> +	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
> +	assert_int_equal(find_first_set(bf), 0);
> +	clear_bit_in_bitfield(0, bf);
> +	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
> +	set_bit_in_bitfield(11, bf);
> +	assert_int_equal(find_first_set(bf), 0);
> +	assert_int_equal(is_bit_set_in_bitfield(11, bf), 0);
> +	clear_bit_in_bitfield(11, bf);
> +	assert_int_equal(is_bit_set_in_bitfield(11, bf), 0);
> +	free(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);
> +	assert_int_equal(find_first_set(bf), 0);
> +
> +	set_bit_in_bitfield(n, bf);
> +	assert_int_equal(*arr, 0);
> +	assert_int_equal(find_first_set(bf), 0);
> +
> +	set_bit_in_bitfield(n - 1, bf);
> +	assert_int_equal(*arr, 1ULL << (n - 1));
> +	assert_int_equal(find_first_set(bf), n);
> +
> +	clear_bit_in_bitfield(n - 1, bf);
> +	assert_int_equal(*arr, 0);
> +	assert_int_equal(find_first_set(bf), 0);
> +
> +	set_bit_in_bitfield(0, bf);
> +	assert_int_equal(*arr, 1);
> +	assert_int_equal(find_first_set(bf), 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);
> +	assert_int_equal(find_first_set(bf), 0);
> +
> +	set_bit_in_bitfield(n, bf);
> +	assert_int_equal(arr[0], 0);
> +	assert_int_equal(arr[1], 0);
> +	assert_int_equal(find_first_set(bf), 0);
> +
> +	set_bit_in_bitfield(n - 1, bf);
> +	assert_int_equal(arr[0], 0);
> +	assert_int_equal(arr[1], 1ULL << (n - 65));
> +	assert_int_equal(find_first_set(bf), n);
> +
> +	set_bit_in_bitfield(0, bf);
> +	assert_int_equal(arr[0], 1);
> +	assert_int_equal(arr[1], 1ULL << (n - 65));
> +	assert_int_equal(find_first_set(bf), 1);
> +
> +	set_bit_in_bitfield(64, bf);
> +	assert_int_equal(arr[0], 1);
> +	assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
> +	assert_int_equal(find_first_set(bf), 1);
> +
> +	clear_bit_in_bitfield(0, bf);
> +	assert_int_equal(arr[0], 0);
> +	assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
> +	assert_int_equal(find_first_set(bf), 65);
> +
> +	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.26.2

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Aug. 4, 2020, 3:04 p.m. UTC | #2 
On Thu, 2020-07-16 at 16:17 -0500, Benjamin Marzinski wrote:
> On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com wrote:
> > From: Martin Wilck <mwilck@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@suse.com>
> > ---
> >  libmultipath/configure.c |   9 +-
> >  libmultipath/util.c      |  35 ++++++
> >  libmultipath/util.h      |  57 ++++++++-
> >  tests/util.c             | 263
> > +++++++++++++++++++++++++++++++++++----
> >  4 files changed, 327 insertions(+), 37 deletions(-)
> > 
> > ...
> > diff --git a/libmultipath/util.c b/libmultipath/util.c
> > index 3c43f28..46cacd4 100644
> > --- a/libmultipath/util.c
> > +++ b/libmultipath/util.c
> > @@ -404,3 +404,38 @@ void close_fd(void *arg)
> >  {
> >  	close((long)arg);
> >  }
> > +
> > +struct bitfield *alloc_bitfield(unsigned int maxbit)
> > +{
> > +	unsigned int n;
> > +	struct bitfield *bf;
> > +
> > +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
> 
> What's the point in accepting 0? That's an empty bitmap.
> 
> > +	bf = calloc(1, sizeof(struct bitfield) + n *
> > sizeof(bitfield_t));
> 
> Need to check that bf got set before dereferencing it.

Thanks for spotting these, I will fix them.

> 
> > +	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);
> > +}
> > +
> > +unsigned int find_first_set(const struct bitfield *bf)
> > +{
> > +	unsigned int b = 0, i, n;
> > +
> > +	for (i = 0; i < bf->len; i+= bits_per_slot) {
> > +		b = _ffs(bf->bits[i / bits_per_slot]);
> > +		if (b != 0)
> > +			break;
> > +	};
> > +	if (b == 0)
> > +		return 0;
> > +
> > +	n = i + b;
> > +	if (n <= bf->len)
> > +		return n;
> > +
> > +	return 0;
> > +}
> 
> This is neat and all, but what's it for?  I didn't see it used in the
> rest of the patches.  Did I miss it, or do you have a future use for
> it?

Got me :-) I first thought we had a use for it. I can rip it out if you
prefer, saving a local copy in case we need it in the future. 

Martin


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Aug. 4, 2020, 3:18 p.m. UTC | #3 
On Tue, 2020-08-04 at 17:04 +0200, Martin Wilck wrote:
> On Thu, 2020-07-16 at 16:17 -0500, Benjamin Marzinski wrote:
> > On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com wrote:
> > > From: Martin Wilck <mwilck@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@suse.com>
> > > ---
> > >  libmultipath/configure.c |   9 +-
> > >  libmultipath/util.c      |  35 ++++++
> > >  libmultipath/util.h      |  57 ++++++++-
> > >  tests/util.c             | 263
> > > +++++++++++++++++++++++++++++++++++----
> > >  4 files changed, 327 insertions(+), 37 deletions(-)
> > > 
> > > ...
> > > diff --git a/libmultipath/util.c b/libmultipath/util.c
> > > index 3c43f28..46cacd4 100644
> > > --- a/libmultipath/util.c
> > > +++ b/libmultipath/util.c
> > > @@ -404,3 +404,38 @@ void close_fd(void *arg)
> > >  {
> > >  	close((long)arg);
> > >  }
> > > +
> > > +struct bitfield *alloc_bitfield(unsigned int maxbit)
> > > +{
> > > +	unsigned int n;
> > > +	struct bitfield *bf;
> > > +
> > > +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
> > 
> > What's the point in accepting 0? That's an empty bitmap.
> > 
> Thanks for spotting these, I will fix them.

Thinking about it once more, I believe that accepting 0 as the bitfield
length is actually the right thing. A bitfield of length 0 makes not
much less sense than one of length 1. The code makes sure that the bit
operations on the 0-length bitfield behave correctly (see
test_bitmask_len_0()). Thus callers can use bitfields without bothering
for extra NULL checks. That was the intention. Like we support 0-length 
vectors.

Regards,
Martin


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Benjamin Marzinski Aug. 4, 2020, 4:26 p.m. UTC | #4 
On Tue, Aug 04, 2020 at 05:18:18PM +0200, Martin Wilck wrote:
> On Tue, 2020-08-04 at 17:04 +0200, Martin Wilck wrote:
> > On Thu, 2020-07-16 at 16:17 -0500, Benjamin Marzinski wrote:
> > > On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com wrote:
> > > > From: Martin Wilck <mwilck@suse.com>
> > > > +struct bitfield *alloc_bitfield(unsigned int maxbit)
> > > > +{
> > > > +	unsigned int n;
> > > > +	struct bitfield *bf;
> > > > +
> > > > +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
> > > 
> > > What's the point in accepting 0? That's an empty bitmap.
> > > 
> > Thanks for spotting these, I will fix them.
> 
> Thinking about it once more, I believe that accepting 0 as the bitfield
> length is actually the right thing. A bitfield of length 0 makes not
> much less sense than one of length 1. The code makes sure that the bit
> operations on the 0-length bitfield behave correctly (see
> test_bitmask_len_0()). Thus callers can use bitfields without bothering
> for extra NULL checks. That was the intention. Like we support 0-length 
> vectors.

But the calloc call itself can return NULL, so deferencing bf (as in
bf->len = maxbit), can crash.

I'm also still fuzzy on why we want to support zero length bitfields.
Since they can't be grown like vectors can, it seem like requesting a
zero length bitfield will always be a sign of a coding error. We
would get a more useful error by having the failure happen closer to
the error in the code.  Or is there actually a use for a zero length
bitfield that can't be grown?

-Ben

> Regards,
> Martin
> 

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Aug. 4, 2020, 7:35 p.m. UTC | #5 
On Tue, 2020-08-04 at 11:26 -0500, Benjamin Marzinski wrote:
> On Tue, Aug 04, 2020 at 05:18:18PM +0200, Martin Wilck wrote:
> > On Tue, 2020-08-04 at 17:04 +0200, Martin Wilck wrote:
> > > On Thu, 2020-07-16 at 16:17 -0500, Benjamin Marzinski wrote:
> > > > On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com
> > > > wrote:
> > > > > From: Martin Wilck <mwilck@suse.com>
> > > > > +struct bitfield *alloc_bitfield(unsigned int maxbit)
> > > > > +{
> > > > > +	unsigned int n;
> > > > > +	struct bitfield *bf;
> > > > > +
> > > > > +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
> > > > 
> > > > What's the point in accepting 0? That's an empty bitmap.
> > > > 
> > > Thanks for spotting these, I will fix them.
> > 
> > Thinking about it once more, I believe that accepting 0 as the
> > bitfield
> > length is actually the right thing. A bitfield of length 0 makes
> > not
> > much less sense than one of length 1. The code makes sure that the
> > bit
> > operations on the 0-length bitfield behave correctly (see
> > test_bitmask_len_0()). Thus callers can use bitfields without
> > bothering
> > for extra NULL checks. That was the intention. Like we support 0-
> > length 
> > vectors.
> 
> But the calloc call itself can return NULL, so deferencing bf (as in
> bf->len = maxbit), can crash.

Of course, I wasn't arguing about that. I'm going to resend with this
fixed.

> I'm also still fuzzy on why we want to support zero length bitfields.
> Since they can't be grown like vectors can, it seem like requesting a
> zero length bitfield will always be a sign of a coding error. We
> would get a more useful error by having the failure happen closer to
> the error in the code.  Or is there actually a use for a zero length
> bitfield that can't be grown?

The only "use" would be to be able to work with bitmaps in situations
where zero elements are possible, without the need to catch another
exception. 0-element bitfields are technically possible although
logically they make no sense. That's robust design for a library
function, IMO. I don't see why it'd be "better" to return NULL instead.
If we are after errors in callers, we might want to print an error
message and still not return NULL.

Martin


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Benjamin Marzinski Aug. 10, 2020, 6:05 p.m. UTC | #6 
On Tue, Aug 04, 2020 at 09:35:08PM +0200, Martin Wilck wrote:
> On Tue, 2020-08-04 at 11:26 -0500, Benjamin Marzinski wrote:
> > On Tue, Aug 04, 2020 at 05:18:18PM +0200, Martin Wilck wrote:
> > > On Tue, 2020-08-04 at 17:04 +0200, Martin Wilck wrote:
> > > > On Thu, 2020-07-16 at 16:17 -0500, Benjamin Marzinski wrote:
> > > > > On Thu, Jul 09, 2020 at 12:15:53PM +0200, mwilck@suse.com
> > > > > wrote:
> > > > > > From: Martin Wilck <mwilck@suse.com>
> > > > > > +struct bitfield *alloc_bitfield(unsigned int maxbit)
> > > > > > +{
> > > > > > +	unsigned int n;
> > > > > > +	struct bitfield *bf;
> > > > > > +
> > > > > > +	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
> > > > > 
> > > > > What's the point in accepting 0? That's an empty bitmap.
> > > > > 
> > > > Thanks for spotting these, I will fix them.
> > > 
> > > Thinking about it once more, I believe that accepting 0 as the
> > > bitfield
> > > length is actually the right thing. A bitfield of length 0 makes
> > > not
> > > much less sense than one of length 1. The code makes sure that the
> > > bit
> > > operations on the 0-length bitfield behave correctly (see
> > > test_bitmask_len_0()). Thus callers can use bitfields without
> > > bothering
> > > for extra NULL checks. That was the intention. Like we support 0-
> > > length 
> > > vectors.
> > 
> > But the calloc call itself can return NULL, so deferencing bf (as in
> > bf->len = maxbit), can crash.
> 
> Of course, I wasn't arguing about that. I'm going to resend with this
> fixed.
> 
> > I'm also still fuzzy on why we want to support zero length bitfields.
> > Since they can't be grown like vectors can, it seem like requesting a
> > zero length bitfield will always be a sign of a coding error. We
> > would get a more useful error by having the failure happen closer to
> > the error in the code.  Or is there actually a use for a zero length
> > bitfield that can't be grown?
> 
> The only "use" would be to be able to work with bitmaps in situations
> where zero elements are possible, without the need to catch another
> exception. 0-element bitfields are technically possible although
> logically they make no sense. That's robust design for a library
> function, IMO. I don't see why it'd be "better" to return NULL instead.
> If we are after errors in callers, we might want to print an error
> message and still not return NULL.

Fine. It's a pretty trivial thing either way.

-Ben

> 
> Martin
> 

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
Martin Wilck Aug. 10, 2020, 6:59 p.m. UTC | #7 
Hi Ben,

On Mon, 2020-08-10 at 13:05 -0500, Benjamin Marzinski wrote:
> On Tue, Aug 04, 2020 at 09:35:08PM +0200, Martin Wilck wrote:
> > On Tue, 2020-08-04 at 11:26 -0500, Benjamin Marzinski wrote:
> > > 
> > > I'm also still fuzzy on why we want to support zero length
> > > bitfields.
> > > Since they can't be grown like vectors can, it seem like
> > > requesting a
> > > zero length bitfield will always be a sign of a coding error. We
> > > would get a more useful error by having the failure happen closer
> > > to
> > > the error in the code.  Or is there actually a use for a zero
> > > length
> > > bitfield that can't be grown?
> > 
> > The only "use" would be to be able to work with bitmaps in
> > situations
> > where zero elements are possible, without the need to catch another
> > exception. 0-element bitfields are technically possible although
> > logically they make no sense. That's robust design for a library
> > function, IMO. I don't see why it'd be "better" to return NULL
> > instead.
> > If we are after errors in callers, we might want to print an error
> > message and still not return NULL.
> 
> Fine. It's a pretty trivial thing either way.

It took me a while, but ...

The current typical usage e.g. in group_by_match() looks like this:

	bitmap = alloc_bitfield(VECTOR_SIZE(paths));

	if (!bitmap)
		goto out;

	for (i = 0; i < VECTOR_SIZE(paths); i++) {
	        ....

Here, VECTOR_SIZE(paths) == 0 is a valid value that just causes nothing
to happen in the function. The other callers aren't much different. I
think we rather don't want to print an error message in these cases.

Every caller needs to check the return value of alloc_bitfield()
anyway, to guard against OOM. The code above would actually be slightly
optimized by returning NULL from alloc_bitfield() for maxbit == 0, by
returning immediately. Besides, we eliminate an (albeit minimal) risk
of hitting OOM by avoiding one needless memory allocation. 

The fact that all our callers work like this convinces me. I'll change
the return value to NULL like you suggested.

Cheers,
Martin


--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
diff mbox series

Patch

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..46cacd4 100644
--- a/libmultipath/util.c
+++ b/libmultipath/util.c
@@ -404,3 +404,38 @@  void close_fd(void *arg)
 {
 	close((long)arg);
 }
+
+struct bitfield *alloc_bitfield(unsigned int maxbit)
+{
+	unsigned int n;
+	struct bitfield *bf;
+
+	n = maxbit > 0 ? (maxbit - 1) / bits_per_slot + 1 : 0;
+	bf = calloc(1, sizeof(struct bitfield) + n * sizeof(bitfield_t));
+	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);
+}
+
+unsigned int find_first_set(const struct bitfield *bf)
+{
+	unsigned int b = 0, i, n;
+
+	for (i = 0; i < bf->len; i+= bits_per_slot) {
+		b = _ffs(bf->bits[i / bits_per_slot]);
+		if (b != 0)
+			break;
+	};
+	if (b == 0)
+		return 0;
+
+	n = i + b;
+	if (n <= bf->len)
+		return n;
+
+	return 0;
+}
diff --git a/libmultipath/util.h b/libmultipath/util.h
index df75c4f..ec6de6d 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,61 @@  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));
 }
 
+unsigned int find_first_set(const struct bitfield *bf);
 #endif /* _UTIL_H */
diff --git a/tests/util.c b/tests/util.c
index 6d12fda..db7c05f 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,46 @@  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));
+			assert_int_equal(find_first_set(bf), b + 1);
+			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));
+			assert_int_equal(find_first_set(bf), 1);
 			for (k = 0; k < BITARR_SZ; k++) {
 				if (k < j || (k == j && i == 63))
 					assert_int_equal(arr[k], ~0ULL);
@@ -232,16 +245,20 @@  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));
+			if (b == 64 * BITARR_SZ - 1)
+				assert_int_equal(find_first_set(bf), 0);
+			else
+				assert_int_equal(find_first_set(bf), b + 2);
 			for (k = 0; k < BITARR_SZ; k++) {
 				if (k < j || (k == j && i == 63))
 					assert_int_equal(arr[k], 0ULL);
@@ -254,13 +271,207 @@  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_non_null(bf);
+	assert_int_equal(bf->len, 0);
+	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
+	assert_int_equal(is_bit_set_in_bitfield(1, bf), 0);
+	assert_int_equal(find_first_set(bf), 0);
+	set_bit_in_bitfield(0, bf);
+	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
+	assert_int_equal(find_first_set(bf), 0);
+	clear_bit_in_bitfield(0, bf);
+	assert_int_equal(is_bit_set_in_bitfield(0, bf), 0);
+	set_bit_in_bitfield(11, bf);
+	assert_int_equal(find_first_set(bf), 0);
+	assert_int_equal(is_bit_set_in_bitfield(11, bf), 0);
+	clear_bit_in_bitfield(11, bf);
+	assert_int_equal(is_bit_set_in_bitfield(11, bf), 0);
+	free(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);
+	assert_int_equal(find_first_set(bf), 0);
+
+	set_bit_in_bitfield(n, bf);
+	assert_int_equal(*arr, 0);
+	assert_int_equal(find_first_set(bf), 0);
+
+	set_bit_in_bitfield(n - 1, bf);
+	assert_int_equal(*arr, 1ULL << (n - 1));
+	assert_int_equal(find_first_set(bf), n);
+
+	clear_bit_in_bitfield(n - 1, bf);
+	assert_int_equal(*arr, 0);
+	assert_int_equal(find_first_set(bf), 0);
+
+	set_bit_in_bitfield(0, bf);
+	assert_int_equal(*arr, 1);
+	assert_int_equal(find_first_set(bf), 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);
+	assert_int_equal(find_first_set(bf), 0);
+
+	set_bit_in_bitfield(n, bf);
+	assert_int_equal(arr[0], 0);
+	assert_int_equal(arr[1], 0);
+	assert_int_equal(find_first_set(bf), 0);
+
+	set_bit_in_bitfield(n - 1, bf);
+	assert_int_equal(arr[0], 0);
+	assert_int_equal(arr[1], 1ULL << (n - 65));
+	assert_int_equal(find_first_set(bf), n);
+
+	set_bit_in_bitfield(0, bf);
+	assert_int_equal(arr[0], 1);
+	assert_int_equal(arr[1], 1ULL << (n - 65));
+	assert_int_equal(find_first_set(bf), 1);
+
+	set_bit_in_bitfield(64, bf);
+	assert_int_equal(arr[0], 1);
+	assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
+	assert_int_equal(find_first_set(bf), 1);
+
+	clear_bit_in_bitfield(0, bf);
+	assert_int_equal(arr[0], 0);
+	assert_int_equal(arr[1], (1ULL << (n - 65)) | 1);
+	assert_int_equal(find_first_set(bf), 65);
+
+	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);
 }