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
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?> > @@ -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.Not sure what build error you're talking about, but yes that CC line should go. Thanks, deleted.
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