[virtio-dev] [PATCH v20 3/7 RESEND] xbitmap: add more operations

[virtio-dev] [PATCH v20 3/7 RESEND] xbitmap: add more operations

[Wei Wang]

This patch adds support to find next 1 or 0 bit in a xbmitmap range and
clear a range of bits.

More possible optimizations to add in the future:
1) xb_set_bit_range: set a range of bits.
2) when searching a bit, if the bit is not found in the slot, move on to
the next slot directly.
3) add tags to help searching.

Signed-off-by: Wei Wang <wei.w.wang@intel.com>
Cc: Matthew Wilcox <mawilcox@microsoft.com>
Cc: Andrew Morton <akpm@linux-foundation.org>
Cc: Michal Hocko <mhocko@kernel.org>
Cc: Michael S. Tsirkin <mst@redhat.com>
Cc: Tetsuo Handa <penguin-kernel@I-love.SAKURA.ne.jp>
Suggested-by: Matthew Wilcox <mawilcox@microsoft.com>
---
 include/linux/xbitmap.h      |   6 ++
 lib/xbitmap.c                | 205 +++++++++++++++++++++++++++++++++++++++++++
 tools/include/linux/bitmap.h |  34 +++++++
 tools/include/linux/kernel.h |   2 +
 4 files changed, 247 insertions(+)

v20 RESEND Changes:
	- fixed the !node path
	- added the test cases for the !node path
	- change __builtin_constant_p(start & 7) to __builtin_constant_p(start) 

diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h
index 108f929..ede1029 100644
--- a/include/linux/xbitmap.h
+++ b/include/linux/xbitmap.h
@@ -35,6 +35,12 @@ static inline void xb_init(struct xb *xb)
 int xb_set_bit(struct xb *xb, unsigned long bit);
 bool xb_test_bit(const struct xb *xb, unsigned long bit);
 void xb_clear_bit(struct xb *xb, unsigned long bit);
+void xb_clear_bit_range(struct xb *xb, unsigned long start,
+			unsigned long nbits);
+unsigned long xb_find_set(struct xb *xb, unsigned long size,
+			  unsigned long offset);
+unsigned long xb_find_zero(struct xb *xb, unsigned long size,
+			   unsigned long offset);
 
 static inline bool xb_empty(const struct xb *xb)
 {
diff --git a/lib/xbitmap.c b/lib/xbitmap.c
index a1c0abd..1c99586 100644
--- a/lib/xbitmap.c
+++ b/lib/xbitmap.c
@@ -3,6 +3,16 @@
 #include <linux/bitmap.h>
 #include <linux/slab.h>
 
+/*
+ * Developer notes:
+ * - locks are required to gurantee there is no concurrent
+ *   calls of xb_set_bit, xb_clear_bit, xb_clear_bit_range, xb_test_bit,
+ *   xb_find_set, or xb_find_clear to operate on the same ida bitmap.
+ * - The current implementation of xb_clear_bit_range, xb_find_set and
+ *   xb_find_clear may cause long latency when the bit range to operate
+ *   on is super large (e.g. [0, ULONG_MAX]).
+ */
+
 /**
  *  xb_set_bit - set a bit in the xbitmap
  *  @xb: the xbitmap tree used to record the bit
@@ -72,6 +82,49 @@ void xb_clear_bit(struct xb *xb, unsigned long bit)
 EXPORT_SYMBOL(xb_clear_bit);
 
 /**
+ * xb_clear_bit_range - clear a range of bits in the xbitmap
+ * @start: the start of the bit range, inclusive
+ * @nbits: number of bits to clear
+ *
+ * This function is used to clear a range of bits in the xbitmap. If all the
+ * bits in the bitmap are 0, the bitmap will be freed.
+ */
+void xb_clear_bit_range(struct xb *xb, unsigned long start,
+			unsigned long nbits)
+{
+	struct radix_tree_root *root = &xb->xbrt;
+	struct radix_tree_node *node;
+	void __rcu **slot;
+	struct ida_bitmap *bitmap;
+	unsigned long index = start / IDA_BITMAP_BITS;
+	unsigned long bit = start % IDA_BITMAP_BITS;
+
+	if (nbits > ULONG_MAX - start)
+		nbits = ULONG_MAX - start;
+
+	while (nbits) {
+		unsigned int __nbits = min(nbits,
+					(unsigned long)IDA_BITMAP_BITS - bit);
+
+		bitmap = __radix_tree_lookup(root, index, &node, &slot);
+		if (bitmap) {
+			if (__nbits != IDA_BITMAP_BITS)
+				bitmap_clear(bitmap->bitmap, bit, __nbits);
+
+			if (__nbits == IDA_BITMAP_BITS ||
+			    bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
+				kfree(bitmap);
+				__radix_tree_delete(root, node, slot);
+			}
+		}
+		bit = 0;
+		index++;
+		nbits -= __nbits;
+	}
+}
+EXPORT_SYMBOL(xb_clear_bit_range);
+
+/**
  * xb_test_bit - test a bit in the xbitmap
  * @xb: the xbitmap tree used to record the bit
  * @bit: index of the bit to test
@@ -94,6 +147,98 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit)
 }
 EXPORT_SYMBOL(xb_test_bit);
 
+/**
+ * xb_find_set - find the next set bit in a range of bits
+ * @xb: the xbitmap to search from
+ * @offset: the offset in the range to start searching
+ * @size: the size of the range
+ *
+ * Returns: the found bit or, @size if no set bit is found.
+ */
+unsigned long xb_find_set(struct xb *xb, unsigned long size,
+			  unsigned long offset)
+{
+	struct radix_tree_root *root = &xb->xbrt;
+	struct radix_tree_node *node;
+	void __rcu **slot;
+	struct ida_bitmap *bitmap;
+	unsigned long index = offset / IDA_BITMAP_BITS;
+	unsigned long index_end = size / IDA_BITMAP_BITS;
+	unsigned long bit = offset % IDA_BITMAP_BITS;
+
+	if (unlikely(offset >= size))
+		return size;
+
+	while (index <= index_end) {
+		unsigned long ret;
+		unsigned int nbits = size - index * IDA_BITMAP_BITS;
+
+		bitmap = __radix_tree_lookup(root, index, &node, &slot);
+
+		if (!node && !bitmap)
+			return size;
+
+		if (bitmap) {
+			if (nbits > IDA_BITMAP_BITS)
+				nbits = IDA_BITMAP_BITS;
+
+			ret = find_next_bit(bitmap->bitmap, nbits, bit);
+			if (ret != nbits)
+				return ret + index * IDA_BITMAP_BITS;
+		}
+		bit = 0;
+		index++;
+	}
+
+	return size;
+}
+EXPORT_SYMBOL(xb_find_set);
+
+/**
+ * xb_find_zero - find the next zero bit in a range of bits
+ * @xb: the xbitmap to search from
+ * @offset: the offset in the range to start searching
+ * @size: the size of the range
+ *
+ * Returns: the found bit or, @size if no zero bit is found.
+ */
+unsigned long xb_find_zero(struct xb *xb, unsigned long size,
+			   unsigned long offset)
+{
+	struct radix_tree_root *root = &xb->xbrt;
+	struct radix_tree_node *node;
+	void __rcu **slot;
+	struct ida_bitmap *bitmap;
+	unsigned long index = offset / IDA_BITMAP_BITS;
+	unsigned long index_end = size / IDA_BITMAP_BITS;
+	unsigned long bit = offset % IDA_BITMAP_BITS;
+
+	if (unlikely(offset >= size))
+		return size;
+
+	while (index <= index_end) {
+		unsigned long ret;
+		unsigned int nbits = size - index * IDA_BITMAP_BITS;
+
+		bitmap = __radix_tree_lookup(root, index, &node, &slot);
+		if (bitmap) {
+			if (nbits > IDA_BITMAP_BITS)
+				nbits = IDA_BITMAP_BITS;
+
+			ret = find_next_zero_bit(bitmap->bitmap, nbits, bit);
+			if (ret != nbits)
+				return ret + index * IDA_BITMAP_BITS;
+		} else {
+			return bit + index * IDA_BITMAP_BITS;
+		}
+		bit = 0;
+		index++;
+	}
+
+	return size;
+}
+EXPORT_SYMBOL(xb_find_zero);
+
 #ifndef __KERNEL__
 
 static DEFINE_XB(xb1);
@@ -111,6 +256,64 @@ void xbitmap_check_bit(unsigned long bit)
 	xb_preload_end();
 }
 
+static void xbitmap_check_bit_range(void)
+{
+	/* Regular test1: node = NULL */
+	xb_preload(GFP_KERNEL);
+	xb_set_bit(&xb1, 700);
+	xb_preload_end();
+	assert(xb_find_set(&xb1, ULONG_MAX, 0) == 700);
+	assert(xb_find_set(&xb1, ULONG_MAX, 800) == ULONG_MAX);
+	xb_clear_bit_range(&xb1, 0, 1024);
+
+	/*
+	 * Regular test 2
+	 * set bit 2000, 2001, 2040
+	 * Next 1 in [0, 2048)		--> 2000
+	 * Next 1 in [2000, 2002)	--> 2000
+	 * Next 1 in [2002, 2041)	--> 2040
+	 * Next 1 in [2002, 2040)	--> none
+	 * Next 0 in [2000, 2048)	--> 2002
+	 * Next 0 in [2048, 2060)	--> 2048
+	 */
+	xb_preload(GFP_KERNEL);
+	assert(!xb_set_bit(&xb1, 2000));
+	assert(!xb_set_bit(&xb1, 2001));
+	assert(!xb_set_bit(&xb1, 2040));
+	assert(xb_find_set(&xb1, 2048, 0) == 2000);
+	assert(xb_find_set(&xb1, 2002, 2000) == 2000);
+	assert(xb_find_set(&xb1, 2041, 2002) == 2040);
+	assert(xb_find_set(&xb1, 2040, 2002) == 2040);
+	assert(xb_find_zero(&xb1, 2048, 2000) == 2002);
+	assert(xb_find_zero(&xb1, 2060, 2048) == 2048);
+	xb_clear_bit_range(&xb1, 0, 2048);
+	assert(xb_find_set(&xb1, 2048, 0) == 2048);
+	xb_preload_end();
+
+	/*
+	 * Overflow tests:
+	 * Set bit 1 and ULONG_MAX - 4
+	 * Next 1 in [ULONG_MAX - 4, ULONG_MAX)		--> ULONG_MAX - 4
+	 * Next 1 [ULONG_MAX - 3, ULONG_MAX + 4)	--> none
+	 * Next 0 [ULONG_MAX - 4, ULONG_MAX + 4)	--> none
+	 */
+	xb_preload(GFP_KERNEL);
+	assert(!xb_set_bit(&xb1, 1));
+	xb_preload_end();
+	xb_preload(GFP_KERNEL);
+	assert(!xb_set_bit(&xb1, ULONG_MAX - 4));
+	assert(xb_find_set(&xb1, ULONG_MAX, ULONG_MAX - 4) == ULONG_MAX - 4);
+	assert(xb_find_set(&xb1, ULONG_MAX + 4, ULONG_MAX - 3) ==
+	       ULONG_MAX + 4);
+	assert(xb_find_zero(&xb1, ULONG_MAX + 4, ULONG_MAX - 4) ==
+	       ULONG_MAX + 4);
+	xb_clear_bit_range(&xb1, ULONG_MAX - 4, 4);
+	assert(xb_find_set(&xb1, ULONG_MAX, ULONG_MAX - 10) == ULONG_MAX);
+	xb_clear_bit_range(&xb1, 0, 2);
+	assert(xb_find_set(&xb1, 2, 0) == 2);
+	xb_preload_end();
+}
+
 void xbitmap_checks(void)
 {
 	xb_init(&xb1);
@@ -122,6 +325,8 @@ void xbitmap_checks(void)
 	xbitmap_check_bit(1025);
 	xbitmap_check_bit((1UL << 63) | (1UL << 24));
 	xbitmap_check_bit((1UL << 63) | (1UL << 24) | 70);
+
+	xbitmap_check_bit_range();
 }
 
 int __weak main(void)
diff --git a/tools/include/linux/bitmap.h b/tools/include/linux/bitmap.h
index ca16027..6b559ee 100644
--- a/tools/include/linux/bitmap.h
+++ b/tools/include/linux/bitmap.h
@@ -37,6 +37,40 @@ static inline void bitmap_zero(unsigned long *dst, int nbits)
 	}
 }
 
+static inline void __bitmap_clear(unsigned long *map, unsigned int start,
+				  int len)
+{
+	unsigned long *p = map + BIT_WORD(start);
+	const unsigned int size = start + len;
+	int bits_to_clear = BITS_PER_LONG - (start % BITS_PER_LONG);
+	unsigned long mask_to_clear = BITMAP_FIRST_WORD_MASK(start);
+
+	while (len - bits_to_clear >= 0) {
+		*p &= ~mask_to_clear;
+		len -= bits_to_clear;
+		bits_to_clear = BITS_PER_LONG;
+		mask_to_clear = ~0UL;
+		p++;
+	}
+	if (len) {
+		mask_to_clear &= BITMAP_LAST_WORD_MASK(size);
+		*p &= ~mask_to_clear;
+	}
+}
+
+static inline __always_inline void bitmap_clear(unsigned long *map,
+						unsigned int start,
+						unsigned int nbits)
+{
+	if (__builtin_constant_p(nbits) && nbits == 1)
+		__clear_bit(start, map);
+	else if (__builtin_constant_p(start) && IS_ALIGNED(start, 8) &&
+		 __builtin_constant_p(nbits) && IS_ALIGNED(nbits, 8))
+		memset((char *)map + start / 8, 0, nbits / 8);
+	else
+		__bitmap_clear(map, start, nbits);
+}
+
 static inline void bitmap_fill(unsigned long *dst, unsigned int nbits)
 {
 	unsigned int nlongs = BITS_TO_LONGS(nbits);
diff --git a/tools/include/linux/kernel.h b/tools/include/linux/kernel.h
index 0ad8844..3c992ae 100644
--- a/tools/include/linux/kernel.h
+++ b/tools/include/linux/kernel.h
@@ -13,6 +13,8 @@
 #define UINT_MAX	(~0U)
 #endif
 
+#define IS_ALIGNED(x, a)	(((x) & ((typeof(x))(a) - 1)) == 0)
+
 #define DIV_ROUND_UP(n,d) (((n) + (d) - 1) / (d))
 
 #define PERF_ALIGN(x, a)	__PERF_ALIGN_MASK(x, (typeof(x))(a)-1)
-- 
2.7.4


---------------------------------------------------------------------
To unsubscribe, e-mail: virtio-dev-unsubscribe@lists.oasis-open.org
For additional commands, e-mail: virtio-dev-help@lists.oasis-open.org

[virtio-dev] Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

[Wei Wang]

On 12/21/2017 10:37 PM, Tetsuo Handa wrote:
> Matthew Wilcox wrote:
>>> +/**
>>> + * xb_find_set - find the next set bit in a range of bits
>>> + * @xb: the xbitmap to search from
>>> + * @offset: the offset in the range to start searching
>>> + * @size: the size of the range
>>> + *
>>> + * Returns: the found bit or, @size if no set bit is found.
>>> + */
>>> +unsigned long xb_find_set(struct xb *xb, unsigned long size,
>>> +			  unsigned long offset)
>>> +{
>>> +	struct radix_tree_root *root = &xb->xbrt;
>>> +	struct radix_tree_node *node;
>>> +	void __rcu **slot;
>>> +	struct ida_bitmap *bitmap;
>>> +	unsigned long index = offset / IDA_BITMAP_BITS;
>>> +	unsigned long index_end = size / IDA_BITMAP_BITS;
>>> +	unsigned long bit = offset % IDA_BITMAP_BITS;
>>> +
>>> +	if (unlikely(offset >= size))
>>> +		return size;
>>> +
>>> +	while (index <= index_end) {
>>> +		unsigned long ret;
>>> +		unsigned int nbits = size - index * IDA_BITMAP_BITS;
>>> +
>>> +		bitmap = __radix_tree_lookup(root, index, &node, &slot);
>>> +
>>> +		if (!node && !bitmap)
>>> +			return size;
>>> +
>>> +		if (bitmap) {
>>> +			if (nbits > IDA_BITMAP_BITS)
>>> +				nbits = IDA_BITMAP_BITS;
>>> +
>>> +			ret = find_next_bit(bitmap->bitmap, nbits, bit);
>>> +			if (ret != nbits)
>>> +				return ret + index * IDA_BITMAP_BITS;
>>> +		}
>>> +		bit = 0;
>>> +		index++;
>>> +	}
>>> +
>>> +	return size;
>>> +}
>>> +EXPORT_SYMBOL(xb_find_set);
>> This is going to be slower than the implementation I sent yesterday.  If I
>> call:
>> 	xb_init(xb);
>> 	xb_set_bit(xb, ULONG_MAX);
>> 	xb_find_set(xb, ULONG_MAX, 0);
>>
>> it's going to call __radix_tree_lookup() 16 quadrillion times.
>> My implementation will walk the tree precisely once.
>>
> Yes. Wei's patch still can not work.
> We should start reviewing Matthew's implementation.

It runs without any issue on my machine. I didn't generate an "xbitmap" 
executable (I just found adding xbitmap executable causes a build error 
due to a Makefile error), instead, I tested it within "main" and it 
passed all the tests.

Matthew has implemented a new version, let's start from there.

Best,
Wei


---------------------------------------------------------------------
To unsubscribe, e-mail: virtio-dev-unsubscribe@lists.oasis-open.org
For additional commands, e-mail: virtio-dev-help@lists.oasis-open.org

[virtio-dev] Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

[Wei Wang]

On 12/22/2017 05:03 AM, Matthew Wilcox wrote:
> OK, here's a rewrite of xbitmap.
>
> Compared to the version you sent:
>   - xb_find_set() is the rewrite I sent out yesterday.
>   - xb_find_clear() is a new implementation.  I use the IDR_FREE tag to find
>     clear bits.  This led to me finding a bug in radix_tree_for_each_tagged().
>   - xb_zero() is also a new implementation (replacing xb_clear_bit_range).
>     It should also be more efficient in deep trees.
>   - Did not accept your change to xb_set_bit(); I think it's important to
>     leave the radix tree node in place, so we're guaranteed to make progress
>     in low-memory situations.  We're expecting the caller to retry, so the
>     memory should not leak.
>   - Redid a lot of the kernel-doc.  Thanks for adding it!  I removed mentions
>     of implementation details, leaving only information useful to those who
>     are using it.
>
> Compared to the version I put out back in February:
>   - Accepted your change to xb_preload(); I think it's an improvement.
>   - Rewrote xb_set_bit() to use the radix_tree_iter_ family of functions.
>     Should improve performance for deep trees.
>   - Rewrote xb_clear_bit() for the same reason.
>   - Left out the use of radix tree exceptional entries.  Thanks for taking
>     them out!  Keeps it clearer for now; if they prove useful, we can put
>     them back in.
>   - Removed the use of __radix_tree_delete and __radix_tree_create, so drop
>     the changes to those functions.
>
> Other miscellaneous notes
>   - I left xb_fill() in the header file, even though there's no implementation
>     yet.  Wouldn't be hard to add once we have a user.
>   - Used SPDX tags instead of a license notice.
>
> I think we need more test cases ... in reviewing this to send out,
> I found a bug in xb_zero(), which I've only fixed because I don't have
> time to write a test case for it.

Thanks for the improvement. I also found a small bug in xb_zero. With 
the following changes, it has passed the current test cases and tested 
with the virtio-balloon usage without any issue.


> +
> +/**
> + * xb_zero() - Clear a range of bits in the XBitmap.
> + * @xb: The XBitmap.
> + * @min: The first bit to clear.
> + * @max: The last bit to clear.
> + *
> + * This function is used to clear a range of bits in the xbitmap.
> + */
> +void xb_zero(struct xb *xb, unsigned long min, unsigned long max)
> +{
> +	struct radix_tree_root *root = &xb->xbrt;
> +	struct radix_tree_iter iter;
> +	void __rcu **slot;
> +	struct ida_bitmap *bitmap;
> +	unsigned long index = min / IDA_BITMAP_BITS;
> +	unsigned long first = min % IDA_BITMAP_BITS;
> +	unsigned long maxindex = max / IDA_BITMAP_BITS;
> +
> +	radix_tree_for_each_slot(slot, root, &iter, index) {
> +		unsigned long nbits = IDA_BITMAP_BITS;
> +		if (index > maxindex)
> +			break;
> +		bitmap = radix_tree_deref_slot(slot);
> +		if (!bitmap)
> +			continue;
> +		radix_tree_iter_tag_set(root, &iter, IDR_FREE);
> +
> +		if (!first && iter.index < maxindex)
> +			goto delete;
> +		if (iter.index == maxindex)
> +			nbits = max % IDA_BITMAP_BITS + 1;
> +		bitmap_clear(bitmap->bitmap, first, nbits);

It should be: bitmap_clear(.., first, nbits - first);


> diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile
> index fa7ee369b3c9..adf36e34dd77 100644
> --- a/tools/testing/radix-tree/Makefile
> +++ b/tools/testing/radix-tree/Makefile
> @@ -1,12 +1,13 @@
>   # SPDX-License-Identifier: GPL-2.0
>   
>   CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address
> -LDFLAGS += -fsanitize=address
> -LDLIBS+= -lpthread -lurcu
> -TARGETS = main idr-test multiorder
> +LDFLAGS += -fsanitize=address $(LDLIBS)
> +LDLIBS := -lpthread -lurcu
> +TARGETS = main idr-test multiorder xbitmap
>   CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o
>   OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \
> -	 tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o
> +	 tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o \
> +	 xbitmap.o
>   
>   ifndef SHIFT
>   	SHIFT=3
> @@ -25,8 +26,11 @@ idr-test: idr-test.o $(CORE_OFILES)
>   
>   multiorder: multiorder.o $(CORE_OFILES)
>   
> +xbitmap: xbitmap.o $(CORE_OFILES)
> +	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o xbitmap
> +

I think the "$(CC).." line should be removed, which will fix the build 
error when adding "xbitmap" to TARGET.


Best,
Wei

---------------------------------------------------------------------
To unsubscribe, e-mail: virtio-dev-unsubscribe@lists.oasis-open.org
For additional commands, e-mail: virtio-dev-help@lists.oasis-open.org

[virtio-dev] Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

[Wei Wang]

On 01/02/2018 10:09 PM, Matthew Wilcox wrote:
> On Fri, Dec 22, 2017 at 04:49:11PM +0800, Wei Wang wrote:
>> Thanks for the improvement. I also found a small bug in xb_zero. With the
>> following changes, it has passed the current test cases and tested with the
>> virtio-balloon usage without any issue.
> Thanks; I applied the change.  Can you supply a test-case for testing
> xb_zero please?
>

Sure. Please check below the test cases. Do you plan to send out the new 
version of xbitmap yourself? If so, I will wait for that to send out the 
virtio-balloon patches.


static void xbitmap_check_zero_bits(void)
{
         assert(xb_empty(&xb1));

         /* Zero an empty xbitmap should work though no real work to do */
         xb_zero(&xb1, 0, ULONG_MAX);
         assert(xb_empty(&xb1));

         xb_preload(GFP_KERNEL);
         assert(xb_set_bit(&xb1, 0) == 0);
         xb_preload_end();

         /* Overflow test */
         xb_zero(&xb1, ULONG_MAX - 10, ULONG_MAX);
         assert(xb_test_bit(&xb1, 0));

         xb_preload(GFP_KERNEL);
         assert(xb_set_bit(&xb1, ULONG_MAX) == 0);
         xb_preload_end();

         xb_zero(&xb1, 0, ULONG_MAX);
         assert(xb_empty(&xb1));
}


/*
  * In the following tests, preload is called once when all the bits to set
  * locate in the same ida bitmap. Otherwise, it is recommended to call
  * preload for each xb_set_bit.
  */
static void xbitmap_check_bit_range(void)
{
         unsigned long nbit = 0;

         /* Regular test1: node = NULL */
         xb_preload(GFP_KERNEL);
         xb_set_bit(&xb1, 700);
         xb_preload_end();
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true);
         assert(nbit == 700);
         nbit++;
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == false);
         assert(nbit == 701);
         xb_zero(&xb1, 0, 1023);

         /*
          * Regular test2
          * set bit 2000, 2001, 2040
          * Next 1 in [0, 2048]          --> 2000
          * Next 1 in [2000, 2002]       --> 2000
          * Next 1 in [2002, 2040]       --> 2040
          * Next 1 in [2002, 2039]       --> none
          * Next 0 in [2000, 2048]       --> 2002
          * Next 0 in [2048, 2060]       --> 2048
          */
         xb_preload(GFP_KERNEL);
         assert(!xb_set_bit(&xb1, 2000));
         assert(!xb_set_bit(&xb1, 2001));
         assert(!xb_set_bit(&xb1, 2040));
         nbit = 0;
         assert(xb_find_set(&xb1, 2048, &nbit) == true);
         assert(nbit == 2000);
         assert(xb_find_set(&xb1, 2002, &nbit) == true);
         assert(nbit == 2000);
         nbit = 2002;
         assert(xb_find_set(&xb1, 2040, &nbit) == true);
         assert(nbit == 2040);
         nbit = 2002;
         assert(xb_find_set(&xb1, 2039, &nbit) == false);
         assert(nbit == 2002);
         nbit = 2000;
         assert(xb_find_zero(&xb1, 2048, &nbit) == true);
         assert(nbit == 2002);
         nbit = 2048;
         assert(xb_find_zero(&xb1, 2060, &nbit) == true);
         assert(nbit == 2048);
         xb_zero(&xb1, 0, 2048);
         nbit = 0;
         assert(xb_find_set(&xb1, 2048, &nbit) == false);
         assert(nbit == 0);
         xb_preload_end();

         /*
          * Overflow tests:
          * Set bit 1 and ULONG_MAX - 4
          * Next 1 in [0, ULONG_MAX]                     --> 1
          * Next 1 in [1, ULONG_MAX]                     --> 1
          * Next 1 in [2, ULONG_MAX]                     --> ULONG_MAX - 4
          * Next 1 in [ULONG_MAX - 3, 2]                 --> none
          * Next 0 in [ULONG_MAX - 4, ULONG_MAX]         --> ULONG_MAX - 3
          * Zero [ULONG_MAX - 4, ULONG_MAX]
          * Next 1 in [ULONG_MAX - 10, ULONG_MAX]        --> none
          * Next 1 in [ULONG_MAX - 1, 2]                 --> none
          * Zero [0, 1]
          * Next 1 in [0, 2]                             --> none
          */
         xb_preload(GFP_KERNEL);
         assert(!xb_set_bit(&xb1, 1));
         xb_preload_end();
         xb_preload(GFP_KERNEL);
         assert(!xb_set_bit(&xb1, ULONG_MAX - 4));
         nbit = 0;
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true);
         assert(nbit == 1);
         nbit = 1;
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true);
         assert(nbit == 1);
         nbit = 2;
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == true);
         assert(nbit == ULONG_MAX - 4);
         nbit++;
         assert(xb_find_set(&xb1, 2, &nbit) == false);
         assert(nbit == ULONG_MAX - 3);
         nbit--;
         assert(xb_find_zero(&xb1, ULONG_MAX, &nbit) == true);
         assert(nbit == ULONG_MAX - 3);
         xb_zero(&xb1, ULONG_MAX - 4, ULONG_MAX);
         nbit = ULONG_MAX - 10;
         assert(xb_find_set(&xb1, ULONG_MAX, &nbit) == false);
         assert(nbit == ULONG_MAX - 10);
         nbit = ULONG_MAX - 1;
         assert(xb_find_set(&xb1, 2, &nbit) == false);
         xb_zero(&xb1, 0, 1);
         nbit = 0;
         assert(xb_find_set(&xb1, 2, &nbit) == false);
         assert(nbit == 0);
         xb_preload_end();
         assert(xb_empty(&xb1));
}


Best,
Wei


---------------------------------------------------------------------
To unsubscribe, e-mail: virtio-dev-unsubscribe@lists.oasis-open.org
For additional commands, e-mail: virtio-dev-help@lists.oasis-open.org

[virtio-dev] Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations

[Wei Wang]

On 12/23/2017 10:33 PM, Tetsuo Handa wrote:
>>>> +	bitmap = rcu_dereference_raw(*slot);
>>>> +	if (!bitmap) {
>>>> +		bitmap = this_cpu_xchg(ida_bitmap, NULL);
>>>> +		if (!bitmap)
>>>> +			return -ENOMEM;
>>> I can't understand this. I can understand if it were
>>>
>>>    BUG_ON(!bitmap);
>>>
>>> because you called xb_preload().
>>>
>>> But
>>>
>>> 	/*
>>> 	 * Regular test 2
>>> 	 * set bit 2000, 2001, 2040
>>> 	 * Next 1 in [0, 2048)		--> 2000
>>> 	 * Next 1 in [2000, 2002)	--> 2000
>>> 	 * Next 1 in [2002, 2041)	--> 2040
>>> 	 * Next 1 in [2002, 2040)	--> none
>>> 	 * Next 0 in [2000, 2048)	--> 2002
>>> 	 * Next 0 in [2048, 2060)	--> 2048
>>> 	 */
>>> 	xb_preload(GFP_KERNEL);
>>> 	assert(!xb_set_bit(&xb1, 2000));
>>> 	assert(!xb_set_bit(&xb1, 2001));
>>> 	assert(!xb_set_bit(&xb1, 2040));
>> [...]
>>> 	xb_preload_end();
>>>
>>> you are not calling xb_preload() prior to each xb_set_bit() call.
>>> This means that, if each xb_set_bit() is not surrounded with
>>> xb_preload()/xb_preload_end(), there is possibility of hitting
>>> this_cpu_xchg(ida_bitmap, NULL) == NULL.
>> This is just a lazy test.  We "know" that the bits in the range 1024-2047
>> will all land in the same bitmap, so there's no need to preload for each
>> of them.
> Testcases also serves as how to use that API.
> Assuming such thing leads to incorrect usage.

If callers are aware that the bits that they going to record locate in 
the same bitmap, I think they should also perform the xb_ APIs with only 
one preload. So the test cases here have shown them a correct example. 
We can probably add some comments above to explain this.


Best,
Wei

---------------------------------------------------------------------
To unsubscribe, e-mail: virtio-dev-unsubscribe@lists.oasis-open.org
For additional commands, e-mail: virtio-dev-help@lists.oasis-open.org