[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]
Subject: Re: [PATCH v20 3/7 RESEND] xbitmap: add more operations
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.0CFLAGS += -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.oifndef SHIFTSHIFT=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
[Date Prev] | [Thread Prev] | [Thread Next] | [Date Next] -- [Date Index] | [Thread Index] | [List Home]