Message ID | 20171221141805.GA27695@bombadil.infradead.org (mailing list archive) |
---|---|
State | New, archived |
Headers | show |
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.
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
diff --git a/lib/xbitmap.c b/lib/xbitmap.c index f03a0f9f9e29..b29af08a7597 100644 --- a/lib/xbitmap.c +++ b/lib/xbitmap.c @@ -249,11 +249,12 @@ void xbitmap_check_bit(unsigned long bit) assert(!xb_test_bit(&xb1, bit)); assert(xb_set_bit(&xb1, bit) == 0); assert(xb_test_bit(&xb1, bit)); - assert(xb_clear_bit(&xb1, bit) == 0); + xb_clear_bit(&xb1, bit); assert(xb_empty(&xb1)); - assert(xb_clear_bit(&xb1, bit) == 0); + xb_clear_bit(&xb1, bit); assert(xb_empty(&xb1)); xb_preload_end(); + assert(xb_find_set(&xb1, ULONG_MAX, 0) == bit); } static void xbitmap_check_bit_range(void) diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index 34ece7883629..adf36e34dd77 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -1,9 +1,9 @@ # 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 \