similar to: [PATCH v15 1/5] lib/xbitmap: Introduce xbitmap

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 long i; > +

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 long i; > +

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

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: Matthew Wilcox <mawilcox at microsoft.com> Signed-off-by: Wei Wang

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

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

On Thu, 3 Aug 2017 14:38:15 +0800 Wei Wang <wei.w.wang at intel.com> wrote: > 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(),

On Thu, 3 Aug 2017 14:38:15 +0800 Wei Wang <wei.w.wang at intel.com> wrote: > 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(),

From: Matthew Wilcox <mawilcox at microsoft.com> Add the following tests for xbitmap: 1) single bit test: single bit set/clear/find; 2) bit range test: set/clear a range of bits and find a 0 or 1 bit in the range. Signed-off-by: Wei Wang <wei.w.wang at intel.com> Cc: Matthew Wilcox <mawilcox at microsoft.com> Cc: Andrew Morton <akpm at linux-foundation.org> Cc: Michael S.

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;

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

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

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

On 12/12/2017 09:20 PM, Tetsuo Handa wrote: > Wei Wang wrote: >> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) >> +{ >> + struct radix_tree_root *root = &xb->xbrt; >> + struct radix_tree_node *node; >> + void **slot; >> + struct ida_bitmap *bitmap; >> + unsigned int nbits; >> + >> + for (; start <

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 12/13/2017 10:16 PM, Tetsuo Handa wrote: > Wei Wang wrote: >> On 12/12/2017 09:20 PM, Tetsuo Handa wrote: >>> Wei Wang wrote: >>>> +void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long end) >>>> +{ >>>> + struct radix_tree_root *root = &xb->xbrt; >>>> + struct radix_tree_node *node; >>>> +

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

Hi Matthew, I love your patch! Perhaps something to improve: [auto build test WARNING on linus/master] [also build test WARNING on v4.15-rc3] [if your patch is applied to the wrong git tree, please drop us a note to help improve the system] url: https://github.com/0day-ci/linux/commits/Wei-Wang/Virtio-balloon-Enhancement/20171215-100525 reproduce: # apt-get install sparse