lkml.org 
[lkml]   [2017]   [Dec]   [22]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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.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

\
 
 \ /
  Last update: 2017-12-22 09:47    [W:0.094 / U:16.068 seconds]
©2003-2018 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site