similar to: [PATCH v20 0/7] Virtio-balloon Enhancement

On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > Wei Wang wrote: >> ChangeLog: >> v19->v20: >> 1) patch 1: xbitmap >> - add __rcu to "void **slot"; >> - remove the exceptional path. >> 2) patch 3: xbitmap >> - DeveloperNotes: add an item to comment that the current bit range >> related APIs operating on extremely large ranges (e.g.

On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > Wei Wang wrote: >> ChangeLog: >> v19->v20: >> 1) patch 1: xbitmap >> - add __rcu to "void **slot"; >> - remove the exceptional path. >> 2) patch 3: xbitmap >> - DeveloperNotes: add an item to comment that the current bit range >> related APIs operating on extremely large ranges (e.g.

On Tue, Dec 19, 2017 at 11:05:11PM +0900, Tetsuo Handa wrote: > Wei Wang wrote: > > ChangeLog: > > v19->v20: > > 1) patch 1: xbitmap > > - add __rcu to "void **slot"; > > - remove the exceptional path. > > 2) patch 3: xbitmap > > - DeveloperNotes: add an item to comment that the current bit range > > related APIs operating on

On Tue, Dec 19, 2017 at 11:05:11PM +0900, Tetsuo Handa wrote: > Wei Wang wrote: > > ChangeLog: > > v19->v20: > > 1) patch 1: xbitmap > > - add __rcu to "void **slot"; > > - remove the exceptional path. > > 2) patch 3: xbitmap > > - DeveloperNotes: add an item to comment that the current bit range > > related APIs operating on

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

On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > > 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

On Wednesday, December 20, 2017 8:26 PM, Matthew Wilcox wrote: > On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > > 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

On Wed, Dec 20, 2017 at 06:34:36PM +0800, Wei Wang wrote: > On 12/19/2017 10:05 PM, Tetsuo Handa wrote: > > 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

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 Sat, Dec 23, 2017 at 11:33:45PM +0900, Tetsuo Handa wrote: > Matthew Wilcox wrote: > > On Sat, Dec 23, 2017 at 11:59:54AM +0900, Tetsuo Handa wrote: > > > Matthew Wilcox wrote: > > > > + bit %= IDA_BITMAP_BITS; > > > > + radix_tree_iter_init(&iter, index); > > > > + slot = idr_get_free_cmn(root, &iter, GFP_NOWAIT | __GFP_NOWARN,

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

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. Signed-off-by: Matthew Wilcox <mawilcox at microsoft.com> Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Andrew Morton <akpm at linux-foundation.org>

On Sat, Dec 23, 2017 at 11:59:54AM +0900, Tetsuo Handa wrote: > Matthew Wilcox wrote: > > + bit %= IDA_BITMAP_BITS; > > + radix_tree_iter_init(&iter, index); > > + slot = idr_get_free_cmn(root, &iter, GFP_NOWAIT | __GFP_NOWARN, index); > > + if (IS_ERR(slot)) { > > + if (slot == ERR_PTR(-ENOSPC)) > > + return 0; /* Already set */ > > Why

On 12/23/2017 10:33 PM, Tetsuo Handa wrote: >>>> + bitmap = rcu_dereference_raw(*slot); >>>> + if (!bitmap) { >>>> + bitmap = this_cpu_xchg(ida_bitmap, NULL); >>>> + if (!bitmap) >>>> + return -ENOMEM; >>> I can't understand this. I can understand if it were >>> >>> BUG_ON(!bitmap); >>>

On 12/24/2017 12:45 PM, Tetsuo Handa wrote: > Matthew Wilcox wrote: >>> + unsigned long pfn = page_to_pfn(page); >>> + 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;

Add a new feature, VIRTIO_BALLOON_F_SG, which enables the transfer of balloon (i.e. inflated/deflated) pages using scatter-gather lists to the host. The implementation of the previous virtio-balloon is not very efficient, because the balloon pages are transferred to the host by one array each time. Here is the breakdown of the time in percentage spent on each step of the balloon inflating process

On 12/21/2017 01:10 AM, Matthew Wilcox wrote: > 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 ==

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() and xb_test_bit(). Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox

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