search for: ida_bitmap_bit

...ck 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; > + unsigned long index = bit / IDA_BITMAP_BITS; > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + 2; > + > + err = __radix_tree_create(root, index, 0, &n...

...ck 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; > + unsigned long index = bit / IDA_BITMAP_BITS; > + struct radix_tree_root *root = &xb->xbrt; > + struct radix_tree_node *node; > + void **slot; > + struct ida_bitmap *bitmap; > + unsigned long ebit; > + > + bit %= IDA_BITMAP_BITS; > + ebit = bit + 2; > + > + err = __radix_tree_create(root, index, 0, &n...

...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 < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { >> + unsigned long index = start / IDA_BITMAP_BITS; >> + unsigned long bit = start % IDA_BITMAP_BITS; >> + >> + bitmap = __radix_tree_lookup(root, index, &node, &slot); >> + if (radix_tree_exception(bitmap)) { >> + unsigned long ebit =...

...bitmap are 0, the bitmap will be freed. + */ +void xb_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void __rcu **slot; + struct ida_bitmap *bitmap; + unsigned long index = start / IDA_BITMAP_BITS; + unsigned long bit = start % IDA_BITMAP_BITS; + + if (nbits > ULONG_MAX - start) + nbits = ULONG_MAX - start; + + while (nbits) { + unsigned int __nbits = min(nbits, + (unsigned long)IDA_BITMAP_BITS - bit); + + bitmap = __radix_tree_lookup(root, index, &node, &slot); + if (bit...

...bitmap are 0, the bitmap will be freed. + */ +void xb_clear_bit_range(struct xb *xb, unsigned long start, + unsigned long nbits) +{ + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void __rcu **slot; + struct ida_bitmap *bitmap; + unsigned long index = start / IDA_BITMAP_BITS; + unsigned long bit = start % IDA_BITMAP_BITS; + + if (nbits > ULONG_MAX - start) + nbits = ULONG_MAX - start; + + while (nbits) { + unsigned int __nbits = min(nbits, + (unsigned long)IDA_BITMAP_BITS - bit); + + bitmap = __radix_tree_lookup(root, index, &node, &slot); + if (bit...

...itmap.c @@ -0,0 +1,278 @@ +#include <linux/bitmap.h> +#include <linux/slab.h> +#include <linux/kernel.h> +#include "../../../include/linux/xbitmap.h" + +static DEFINE_XB(xb1); + +int xb_set_bit(struct xb *xb, unsigned long bit) +{ + int err; + unsigned long index = bit / IDA_BITMAP_BITS; + struct radix_tree_root *root = &xb->xbrt; + struct radix_tree_node *node; + void **slot; + struct ida_bitmap *bitmap; + unsigned long ebit; + + bit %= IDA_BITMAP_BITS; + ebit = bit + 2; + + err = __radix_tree_create(root, index, 0, &node, &slot); + if (err) + return err; + bitma...

...gt; + struct radix_tree_root *root = &xb->xbrt; >>>> + struct radix_tree_node *node; >>>> + void **slot; >>>> + struct ida_bitmap *bitmap; >>>> + unsigned int nbits; >>>> + >>>> + for (; start < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { >>>> + unsigned long index = start / IDA_BITMAP_BITS; >>>> + unsigned long bit = start % IDA_BITMAP_BITS; >>>> + >>>> + bitmap = __radix_tree_lookup(root, index, &node, &slot); >>>> + if (radix_tree_exception(bitm...

...the lines of this: void xb_clear(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; for (; end < start; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { unsigned long index = start / IDA_BITMAP_BITS; unsigned long bit = start % IDA_BITMAP_BITS; bitmap = __radix_tree_lookup(root, index, &node, &slot); if (radix_tree_exception(bitmap)) {...

...the lines of this: void xb_clear(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; for (; end < start; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { unsigned long index = start / IDA_BITMAP_BITS; unsigned long bit = start % IDA_BITMAP_BITS; bitmap = __radix_tree_lookup(root, index, &node, &slot); if (radix_tree_exception(bitmap)) {...

...tmap implementation supports up to ULONG_MAX bits, and it is + * implemented based on ida bitmaps. So, given an unsigned long index, + * the high order XB_INDEX_BITS bits of the index is used to find the + * corresponding item (i.e. ida bitmap) from the radix tree, and the low + * order (i.e. ilog2(IDA_BITMAP_BITS)) bits of the index are indexed into + * the ida bitmap to find the bit. + */ +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS)) +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \ + RADIX_TREE_MAP_SHIFT)) +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1) + +/* * Per-cpu p...

...ap will be freed. + */ +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 < end; start = (start | (IDA_BITMAP_BITS - 1)) + 1) { + unsigned long index = start / IDA_BITMAP_BITS; + unsigned long bit = start % IDA_BITMAP_BITS; + + bitmap = __radix_tree_lookup(root, index, &node, &slot); + if (radix_tree_exception(bitmap)) { + unsigned long ebit = bit + 2; + unsigned long tmp = (unsigned long)bitma...

...ee of given height */ static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly; @@ -77,6 +77,11 @@ static struct kmem_cache *radix_tree_node_cachep; RADIX_TREE_MAP_SHIFT)) #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS)) +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \ + RADIX_TREE_MAP_SHIFT)) +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1) + /* * Per-cpu pool of preloaded nodes */ @@ -1781,7 +1786,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, child = rcu_dereferen...

...ee of given height */ static unsigned long height_to_maxnodes[RADIX_TREE_MAX_PATH + 1] __read_mostly; @@ -77,6 +77,11 @@ static struct kmem_cache *radix_tree_node_cachep; RADIX_TREE_MAP_SHIFT)) #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS)) +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \ + RADIX_TREE_MAP_SHIFT)) +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1) + /* * Per-cpu pool of preloaded nodes */ @@ -1781,7 +1786,7 @@ void __rcu **radix_tree_next_chunk(const struct radix_tree_root *root, child = rcu_dereferen...

...- unsigned long offset) +bool xb_find_set(struct xb *xb, unsigned long max, unsigned long *bit) { - struct radix_tree_root *root = &xb->xbrt; - struct radix_tree_node *node; + struct radix_tree_iter iter; void __rcu **slot; struct ida_bitmap *bitmap; - unsigned long index = offset / IDA_BITMAP_BITS; - unsigned long index_end = size / IDA_BITMAP_BITS; - unsigned long bit = offset % IDA_BITMAP_BITS; - - if (unlikely(offset >= size)) - return size; - - while (index <= index_end) { - unsigned long ret; - unsigned int nbits = size - index * IDA_BITMAP_BITS; - - bitmap = __radix_tree_loo...

...long size, >>> + unsigned long offset) >>> +{ >>> + struct radix_tree_root *root = &xb->xbrt; >>> + struct radix_tree_node *node; >>> + void __rcu **slot; >>> + struct ida_bitmap *bitmap; >>> + unsigned long index = offset / IDA_BITMAP_BITS; >>> + unsigned long index_end = size / IDA_BITMAP_BITS; >>> + unsigned long bit = offset % IDA_BITMAP_BITS; >>> + >>> + if (unlikely(offset >= size)) >>> + return size; >>> + >>> + while (index <= index_end) { >>> + u...

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

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

...* Number of nodes in fully populated tree of given height */ @@ -78,6 +79,14 @@ static struct kmem_cache *radix_tree_node_cachep; #define IDA_PRELOAD_SIZE (IDA_MAX_PATH * 2 - 1) /* + * The XB can go up to unsigned long, but also uses a bitmap. + */ +#define XB_INDEX_BITS (BITS_PER_LONG - ilog2(IDA_BITMAP_BITS)) +#define XB_MAX_PATH (DIV_ROUND_UP(XB_INDEX_BITS, \ + RADIX_TREE_MAP_SHIFT)) +#define XB_PRELOAD_SIZE (XB_MAX_PATH * 2 - 1) + +/* * Per-cpu pool of preloaded nodes */ struct radix_tree_preload { @@ -840,6 +849,8 @@ int __radix_tree_create(struct radix_tree_root *root, unsigned l...