search for: xb_set_bit

This patch adds support to find next 1 or 0 bit in a xbmitmap range and clear a range of bits. More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add tags to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm at lin...

This patch adds support to find next 1 or 0 bit in a xbmitmap range and clear a range of bits. More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add tags to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm at lin...

...tation. 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!...

...tation. 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!...

...+ struct radix_tree_root xbrt; +}; + +#define XB_INIT { \ + .xbrt = RADIX_TREE_INIT(IDR_RT_MARKER | GFP_NOWAIT), \ +} +#define DEFINE_XB(name) struct xb name = XB_INIT + +static inline void xb_init(struct xb *xb) +{ + INIT_RADIX_TREE(&xb->xbrt, IDR_RT_MARKER | GFP_NOWAIT); +} + +int xb_set_bit(struct xb *xb, unsigned long bit); +bool xb_test_bit(const struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_zero(struct xb *xb, unsigned long min, unsigned long max); +void xb_fill(struct xb *xb, unsigned long min, unsigned long max); +bool xb_find_s...

...lear() 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 o...

...in [0, 2048) --> 2000 > * Next 1 in [2000, 2002) --> 2000 > * Next 1 in [2002, 2041) --> 2040 > * Next 1 in [2002, 2040) --> 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)); [...] > xb_preload_end(); > > you are not calling xb_preload() prior to each xb_set_bit() call. > This means that, if each xb_set_bit() is not surrounded with > xb_preload()/xb_p...

...on to > > come as separate patches with corresponding test cases in the future. > > You can't remove the !node path. You'll see !node when the highest set bit > is less than 1024. So do something like this: > > unsigned long bit; > xb_preload(GFP_KERNEL); > xb_set_bit(xb, 700); > xb_preload_end(); > bit = xb_find_set(xb, ULONG_MAX, 0); > assert(bit == 700); This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. A better test would be ... xb_set_bit(xb, 700); ass...

...on to > > come as separate patches with corresponding test cases in the future. > > You can't remove the !node path. You'll see !node when the highest set bit > is less than 1024. So do something like this: > > unsigned long bit; > xb_preload(GFP_KERNEL); > xb_set_bit(xb, 700); > xb_preload_end(); > bit = xb_find_set(xb, ULONG_MAX, 0); > assert(bit == 700); This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. A better test would be ... xb_set_bit(xb, 700); ass...

...ion from the linux-dax tree: - remove xb_fill() and xb_zero() from xbitmap.h since they are not implemented; - xb_test_bit: changed "ebit > BITS_PER_LONG" to "ebit >= BITS_PER_LONG", because bit 64 beyonds the "unsigned long" exceptional entry (0 to 63); - xb_set_bit: delete the new inserted radix_tree_node when failing to get the per cpu ida bitmap, this avoids the kind of memory leak of the unused radix tree node left in the tree. - xb_clear_bit: change it to be a void function, since the original implementation reurns nothing than a 0. - remove the c...

...tag is clear, > > we know the bitmap is full. > > > > OK. But does using IDR_FREE tag have more benefit than cost? > You are doing > > if (bitmap_full(bitmap->bitmap, IDA_BITMAP_BITS)) > radix_tree_iter_tag_clear(root, &iter, IDR_FREE); > > for each xb_set_bit() call. How likely do we hit ERR_PTR(-ENOSPC) path? > Isn't removing both bitmap_full() and ERR_PTR(-ENOSPC) better? You're assuming that the purpose of using IDR_FREE is to save xb_set_bit from walking the tree unnecessarily. It isn't; that's just a happy side-effect. Its mai...

...w file mode 100644 index 0000000..bee8a38 --- /dev/null +++ b/tools/testing/radix-tree/xbitmap.c @@ -0,0 +1,278 @@ +#include <linux/bitmap.h> +#include <linux/slab.h> +#include <linux/kernel.h> +#include "../../../include/linux/xbitmap.h" + +static DEFINE_XB(xb1); + +int xb_set_bit(struct xb *xb, unsigned long bit) +{ + int err; + unsigned long index = bit / IDA_BITMAP_BITS; + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %= IDA_BITMAP_BITS; + ebit = bit + 2; + + err =...

...) --> 2000 >>> * Next 1 in [2002, 2041) --> 2040 >>> * Next 1 in [2002, 2040) --> 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)); >> [...] >>> xb_preload_end(); >>> >>> you are not calling xb_preload() prior to each xb_set_bit() call. >>> This means that, if each xb...

On Wed, Dec 20, 2017 at 04:13:16PM +0000, Wang, Wei W wrote: > On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > > unsigned long bit; > > xb_preload(GFP_KERNEL); > > xb_set_bit(xb, 700); > > xb_preload_end(); > > bit = xb_find_set(xb, ULONG_MAX, 0); > > assert(bit == 700); > > This above test will result in "!node with bitmap !=NULL", and it goes to the regular "if (bitmap)" path, which finds 700. > > A better test wo...

From: Matthew Wilcox <mawilcox at microsoft.com> The eXtensible Bitmap is a sparse bitmap representation which is efficient for set bits which tend to cluster. It supports up to 'unsigned long' worth of bits, and this commit adds the bare bones -- xb_set_bit(), xb_clear_bit(), xb_clear_bit_range(), xb_test_bit(), xb_find_next_set_bit(), xb_find_next_zero_bit(). More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) a...

This patch adds support to find next 1 or 0 bit in a xbmitmap range and clear a range of bits. More possible optimizations to add in the future: 1) xb_set_bit_range: set a range of bits. 2) when searching a bit, if the bit is not found in the slot, move on to the next slot directly. 3) add tags to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm at lin...

...ut virtio-balloon changes? > > . > > I still think we don't need xb_preload()/xb_preload_end(). Why would you think preload is not needed? The bitmap is allocated via preload "bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);", this allocated bitmap would be used in xb_set_bit(). > I think xb_find_set() has a bug in !node path. I think we can probably remove the "!node" path for now. It would be good to get the fundamental part in first, and leave optimization to come as separate patches with corresponding test cases in the future. Best, Wei

...ut virtio-balloon changes? > > . > > I still think we don't need xb_preload()/xb_preload_end(). Why would you think preload is not needed? The bitmap is allocated via preload "bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);", this allocated bitmap would be used in xb_set_bit(). > I think xb_find_set() has a bug in !node path. I think we can probably remove the "!node" path for now. It would be good to get the fundamental part in first, and leave optimization to come as separate patches with corresponding test cases in the future. Best, Wei

...t;>> + int ret; >>> + >>> + *pfn_min = min(pfn, *pfn_min); >>> + *pfn_max = max(pfn, *pfn_max); >>> + >>> + do { >>> + if (xb_preload(GFP_NOWAIT | __GFP_NOWARN) < 0) >>> + return -ENOMEM; >>> + >>> + ret = xb_set_bit(&vb->page_xb, pfn); >>> + xb_preload_end(); >>> + } while (unlikely(ret == -EAGAIN)); >> OK, so you don't need a spinlock because you're under a mutex? But you >> can't allocate memory because you're in the balloon driver, and so a >> GFP...

This patch series enhances the existing virtio-balloon with the following new features: 1) fast ballooning: transfer ballooned pages between the guest and host in chunks using sgs, instead of one array each time; and 2) free page block reporting: a new virtqueue to report guest free pages to the host. The second feature can be used to accelerate live migration of VMs. Here are some details: Live