search for: xb_find_next_zero_bit

...g bit, gfp_t gfp); bool xb_test_bit(const struct xb *xb, unsigned long bit); -int xb_clear_bit(struct xb *xb, unsigned long bit); +void xb_clear_bit(struct xb *xb, unsigned long bit); +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end); +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end); +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end); static inline bool xb_empty(const struct xb *xb) { diff --git a/lib/xbitmap.c b/lib/xbitmap.c index 182aa29..10df879 100644 --- a/lib/xbitmap.c +++ b...

...) + return ret + index * IDA_BITMAP_BITS; + } else if (!bmap && !set) { + return start; + } + } + + return ret; +} + +unsigned long xb_find_next_set_bit(struct xb *xb, unsigned long start, + unsigned long end) +{ + return xb_find_next_bit(xb, start, end, 1); +} + +unsigned long xb_find_next_zero_bit(struct xb *xb, unsigned long start, + unsigned long end) +{ + return xb_find_next_bit(xb, start, end, 0); +} + +static void xbitmap_check_bit(unsigned long bit) +{ + assert(!xb_test_bit(&xb1, bit)); + assert(!xb_preload_and_set_bit(&xb1, bit, GFP_KERNEL)); + assert(xb_test_bit(&x...

...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) add Tags to help searching. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox...

...eptional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the convenience of future updates. > > Removing exceptional path made this patch easier to read. > But wha...

...eptional path; > > - remove xb_preload_and_set(); > > - reimplement xb_clear_bit_range to make its usage close to > > bitmap_clear; > > - rename xb_find_next_set_bit to xb_find_set, and re-implement it > > in a style close to find_next_bit; > > - rename xb_find_next_zero_bit to xb_find_clear, and re-implement > > it in a stytle close to find_next_zero_bit; > > - separate the implementation of xb_find_set and xb_find_clear for > > the convenience of future updates. > > Removing exceptional path made this patch easier to read. > But wha...

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

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

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

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

...he exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the convenience of future updates. > Removing exceptional path made this patch easier to read. > But what I meant...

...he exceptional path; >> - remove xb_preload_and_set(); >> - reimplement xb_clear_bit_range to make its usage close to >> bitmap_clear; >> - rename xb_find_next_set_bit to xb_find_set, and re-implement it >> in a style close to find_next_bit; >> - rename xb_find_next_zero_bit to xb_find_clear, and re-implement >> it in a stytle close to find_next_zero_bit; >> - separate the implementation of xb_find_set and xb_find_clear for >> the convenience of future updates. > Removing exceptional path made this patch easier to read. > But what I meant...

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

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

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

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

...len = round_down(UINT_MAX, PAGE_SIZE); > + > + pfn_start = page_xb_start; > + while (pfn_start < page_xb_end) { > + pfn_start = xb_find_next_set_bit(&vb->page_xb, pfn_start, > + page_xb_end); > + if (pfn_start == page_xb_end + 1) > + break; > + pfn_end = xb_find_next_zero_bit(&vb->page_xb, > + pfn_start + 1, > + page_xb_end); > + addr = pfn_start << PAGE_SHIFT; > + len = (pfn_end - pfn_start) << PAGE_SHIFT; This assugnment can overflow. Next line compares with UINT_MAX but by that time it is too late. I think you should do al...

...len = round_down(UINT_MAX, PAGE_SIZE); > + > + pfn_start = page_xb_start; > + while (pfn_start < page_xb_end) { > + pfn_start = xb_find_next_set_bit(&vb->page_xb, pfn_start, > + page_xb_end); > + if (pfn_start == page_xb_end + 1) > + break; > + pfn_end = xb_find_next_zero_bit(&vb->page_xb, > + pfn_start + 1, > + page_xb_end); > + addr = pfn_start << PAGE_SHIFT; > + len = (pfn_end - pfn_start) << PAGE_SHIFT; This assugnment can overflow. Next line compares with UINT_MAX but by that time it is too late. I think you should do al...

I'm commenting without understanding the logic. Wei Wang wrote: > + > +bool xb_preload(gfp_t gfp); > + Want __must_check annotation, for __radix_tree_preload() is marked with __must_check annotation. By error failing to check result of xb_preload() will lead to preemption kept disabled unexpectedly. > +int xb_set_bit(struct xb *xb, unsigned long bit) > +{ > + int err;

I'm commenting without understanding the logic. Wei Wang wrote: > + > +bool xb_preload(gfp_t gfp); > + Want __must_check annotation, for __radix_tree_preload() is marked with __must_check annotation. By error failing to check result of xb_preload() will lead to preemption kept disabled unexpectedly. > +int xb_set_bit(struct xb *xb, unsigned long bit) > +{ > + int err;

...> + } > + > + return i; > +} > +EXPORT_SYMBOL(xb_find_next_bit); Similar comments ... this is going to be very slow. You can use the tags in the tree to help you find set and clear bits so performance doesn't fall apart in big trees. I'd like to see this be two functions, xb_find_next_zero_bit() and xb_find_next_set_bit().