search for: xb_zero

On Mon, Aug 28, 2017 at 06:08:30PM +0800, Wei Wang wrote: > +/** > + * xb_zero - zero a range of bits in the xbitmap > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + */ > +void xb_zero(struct xb *xb, unsigned long start, unsigned long end) > +{ > + unsigned lo...

On Mon, Aug 28, 2017 at 06:08:30PM +0800, Wei Wang wrote: > +/** > + * xb_zero - zero a range of bits in the xbitmap > + * @xb: the xbitmap that the bits reside in > + * @start: the start of the range, inclusive > + * @end: the end of the range, inclusive > + */ > +void xb_zero(struct xb *xb, unsigned long start, unsigned long end) > +{ > + unsigned lo...

...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 > i...

...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 > i...

...e = 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_set(const struct xb *xb, unsigned long max, unsigned long *bit); +bool xb_find_zero(const struct xb *xb, unsigned long max, unsigned long *bit); + +static inline b...

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

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

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

On Fri, Dec 22, 2017 at 04:49:11PM +0800, Wei Wang wrote: > 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. Thanks; I applied the change. Can you supply a test-case for testing xb_zero please? > > @@ -25,8 +26,11 @@ idr-test: idr-test.o $(CORE_OFILES) > >...

...es in the 1st round. It is not concerned that the memory pages are used after they are given to the hypervisor as a hint of the free pages, because they will be tracked by the hypervisor and transferred in the next round if they are used and written. ChangeLog: v20 (RESEND)->v21: 1) patch 1: - xb_zero: fix the bug related to bitmap_clear; - testing/radix-tree/Makefile: removed the "$CC.." line; - added a test case for xbitmap_check_zero_bits; 2) patch 2: virtio-balloon - changed the usage of the xb_ related APIs v19->v20: 1) patch 1: xbitmap - add __rcu to "void **slot&quo...

This patch made some changes to the original xbitmap implementation 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 fai...

...lementation; 2) Simpler function to get the free page block. v7->v8: 1) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Matthew Wilcox (1): Introduce xbitmap Wei Wang (4): xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks virtio-balloon: VIRTIO_BALLOON_F_FREE_PAGE_VQ drivers/virtio/virtio_balloon.c | 302 +++++++++++++++++++++++++++++++----- include/linux/mm.h | 7 + include/linux/mmzone.h | 5 +...

...lementation; 2) Simpler function to get the free page block. v7->v8: 1) Use only one chunk format, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Matthew Wilcox (1): Introduce xbitmap Wei Wang (4): xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks virtio-balloon: VIRTIO_BALLOON_F_FREE_PAGE_VQ drivers/virtio/virtio_balloon.c | 302 +++++++++++++++++++++++++++++++----- include/linux/mm.h | 7 + include/linux/mmzone.h | 5 +...

...end_balloon_page_sg(vb, vq, sg_addr, sg_max_len, 1); > > Last argument should be true, not 1. > > > > > + sg_addr += sg_max_len; > > > + sg_len -= sg_max_len; > > > + } > > > + send_balloon_page_sg(vb, vq, sg_addr, sg_len, 1); > > > + xb_zero(&vb->page_xb, sg_pfn_start, sg_pfn_end); > > > + sg_pfn_start = sg_pfn_end + 1; > > > + } > > > + > > > + /* > > > + * The last few sgs may not reach the batch size, but need a kick to > > > + * notify the device to handle them. > &...

...end_balloon_page_sg(vb, vq, sg_addr, sg_max_len, 1); > > Last argument should be true, not 1. > > > > > + sg_addr += sg_max_len; > > > + sg_len -= sg_max_len; > > > + } > > > + send_balloon_page_sg(vb, vq, sg_addr, sg_len, 1); > > > + xb_zero(&vb->page_xb, sg_pfn_start, sg_pfn_end); > > > + sg_pfn_start = sg_pfn_end + 1; > > > + } > > > + > > > + /* > > > + * The last few sgs may not reach the batch size, but need a kick to > > > + * notify the device to handle them. > &...

...low test, not sure if this is the "bug" you referred to, but I'm glad to hear your different thought. I agree that some tests may be repeated in some degree, since we test the implementation from different aspects, for example, xbitmap_check_bit_range() may have already performed xb_zero() while we specifically have another xbitmap_check_zero_bits() which may test something that has already been tested when checking bit range. But I think testing twice is better than omission. Also, I left the "Regualr test1: node=NULL" case though the new implementation doesn't e...

...t; Last argument should be true, not 1. > > > > > > > > > + sg_addr += sg_max_len; > > > > > + sg_len -= sg_max_len; > > > > > + } > > > > > + send_balloon_page_sg(vb, vq, sg_addr, sg_len, 1); > > > > > + xb_zero(&vb->page_xb, sg_pfn_start, sg_pfn_end); > > > > > + sg_pfn_start = sg_pfn_end + 1; > > > > > + } > > > > > + > > > > > + /* > > > > > + * The last few sgs may not reach the batch size, but need a kick to > >...

...t; Last argument should be true, not 1. > > > > > > > > > + sg_addr += sg_max_len; > > > > > + sg_len -= sg_max_len; > > > > > + } > > > > > + send_balloon_page_sg(vb, vq, sg_addr, sg_len, 1); > > > > > + xb_zero(&vb->page_xb, sg_pfn_start, sg_pfn_end); > > > > > + sg_pfn_start = sg_pfn_end + 1; > > > > > + } > > > > > + > > > > > + /* > > > > > + * The last few sgs may not reach the batch size, but need a kick to > >...

...e_sg(vb, vq, sg_addr, sg_max_len, 1); >>> Last argument should be true, not 1. >>> >>>> + sg_addr += sg_max_len; >>>> + sg_len -= sg_max_len; >>>> + } >>>> + send_balloon_page_sg(vb, vq, sg_addr, sg_len, 1); >>>> + xb_zero(&vb->page_xb, sg_pfn_start, sg_pfn_end); >>>> + sg_pfn_start = sg_pfn_end + 1; >>>> + } >>>> + >>>> + /* >>>> + * The last few sgs may not reach the batch size, but need a kick to >>>> + * notify the device to handle...

...rmat, instead of two. 2) re-write the virtio-balloon implementation patch. 3) commit changes 4) patch re-org Liang Li (1): virtio-balloon: deflate via a page list Matthew Wilcox (1): Introduce xbitmap Wei Wang (6): virtio-balloon: coding format cleanup xbitmap: add xb_find_next_bit() and xb_zero() virtio-balloon: VIRTIO_BALLOON_F_SG mm: support reporting free page blocks mm: export symbol of next_zone and first_online_pgdat virtio-balloon: VIRTIO_BALLOON_F_CMD_VQ drivers/virtio/virtio_balloon.c | 414 ++++++++++++++++++++++++++++++++---- drivers/virtio/virtio_ring.c |...