search for: xb_test_bit

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 failing to get the per cpu ida bitmap, this avoids the kind of memo...

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 at microsoft.com> Cc: Andrew Morton <akpm at linux-foundation.org> Cc: Michal Hocko <mhocko at kernel.org> Cc: Michael S. Tsirkin <mst at redhat.com> Cc: Tetsuo Handa <penguin-kernel...

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 at microsoft.com> Cc: Andrew Morton <akpm at linux-foundation.org> Cc: Michal Hocko <mhocko at kernel.org> Cc: Michael S. Tsirkin <mst at redhat.com> Cc: Tetsuo Handa <penguin-kernel...

...lt;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(). Would like to see some additional details here justifying the change. The sole user is virtio-balloon, yes? What alternatives were examined and what are the benefits of this approach? Have you identified any other subsystems which could utilize this? > > ... > > --- a/lib/radix-...

...lt;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(). Would like to see some additional details here justifying the change. The sole user is virtio-balloon, yes? What alternatives were examined and what are the benefits of this approach? Have you identified any other subsystems which could utilize this? > > ... > > --- a/lib/radix-...

...x/xbitmap.h index b4d8375..eddf0d5e 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -33,8 +33,14 @@ static inline void xb_init(struct xb *xb) } int xb_set_bit(struct xb *xb, unsigned long bit); +int xb_preload_and_set_bit(struct xb *xb, unsigned long 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,...

..._builtin_constant_p(start) diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index 108f929..ede1029 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -35,6 +35,12 @@ static inline void xb_init(struct xb *xb) 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_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits); +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset); +unsigned long xb_find_zer...

..._builtin_constant_p(start) diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index 108f929..ede1029 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -35,6 +35,12 @@ static inline void xb_init(struct xb *xb) 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_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits); +unsigned long xb_find_set(struct xb *xb, unsigned long size, + unsigned long offset); +unsigned long xb_find_zer...

...ged the API to not have the ambiguous return value, I also changed the test suite, and maybe I introduced a bug. diff --git a/include/linux/xbitmap.h b/include/linux/xbitmap.h index ede1029b8a27..96e7e3560a0e 100644 --- a/include/linux/xbitmap.h +++ b/include/linux/xbitmap.h @@ -37,8 +37,7 @@ bool xb_test_bit(const struct xb *xb, unsigned long bit); void xb_clear_bit(struct xb *xb, unsigned long bit); void xb_clear_bit_range(struct xb *xb, unsigned long start, unsigned long nbits); -unsigned long xb_find_set(struct xb *xb, unsigned long size, - unsigned long offset); +bool xb_find_set(struct x...

...IT { \ + .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_set(const struct xb *xb, unsigned long max, unsigned l...

...+ bitmap_clear(bitmap->bitmap, bit, nbits); > + > + if (nbits == IDA_BITMAP_BITS || > + bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { Same here. > + kfree(bitmap); > + __radix_tree_delete(root, node, slot); > + } > + } > + } > +} > +bool xb_test_bit(struct xb *xb, unsigned long bit) > +{ > + unsigned long index = bit / IDA_BITMAP_BITS; > + const struct radix_tree_root *root = &xb->xbrt; > + struct ida_bitmap *bitmap = radix_tree_lookup(root, index); > + > + bit %= IDA_BITMAP_BITS; > + > + if (!bitmap) > + ret...

...+ bitmap_clear(bitmap->bitmap, bit, nbits); > + > + if (nbits == IDA_BITMAP_BITS || > + bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) { Same here. > + kfree(bitmap); > + __radix_tree_delete(root, node, slot); > + } > + } > + } > +} > +bool xb_test_bit(struct xb *xb, unsigned long bit) > +{ > + unsigned long index = bit / IDA_BITMAP_BITS; > + const struct radix_tree_root *root = &xb->xbrt; > + struct ida_bitmap *bitmap = radix_tree_lookup(root, index); > + > + bit %= IDA_BITMAP_BITS; > + > + if (!bitmap) > + ret...

...lcox <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) add Tags to help searching. Signed-off-by: Wei Wang &...

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

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 <wei.w.wang at intel.com> --- include/linux/radix-tree.h | 2 + include/linux/xbitmap.h | 49 ++++++++++++++++ lib/radix-tree.c | 139 ++++++++++++++++++++++++++++++++++++++++++++- 3 f...

...IT { \ + .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_set(const struct xb *xb, unsigned long max, unsigned l...

...load also preloads radix tree nodes. > Also, please clarify why it is OK to just return here. > I don't know what > > radix_tree_iter_replace(root, &iter, slot, bitmap); > > is doing. If you created a slot but did not assign "bitmap", > what the caller of xb_test_bit() etc. will find? If there is an > assumption about this slot, won't this cause a problem? xb_test_bit will find NULL if bitmap wasn't assigned. That doesn't harm anything.

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