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
