On Thu,  3 Aug 2017 14:38:15 +0800 Wei Wang <wei.w.w...@intel.com> wrote:

> From: Matthew Wilcox <mawil...@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-tree.c
> +++ b/lib/radix-tree.c
> @@ -37,6 +37,7 @@
>  #include <linux/rcupdate.h>
>  #include <linux/slab.h>
>  #include <linux/string.h>
> +#include <linux/xbitmap.h>
>  
>  
>  /* 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.

This comment is hard to understand.

> + */
> +#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)
> +
>
> ...
>  
> +void xb_preload(gfp_t gfp)
> +{
> +     __radix_tree_preload(gfp, XB_PRELOAD_SIZE);
> +     if (!this_cpu_read(ida_bitmap)) {
> +             struct ida_bitmap *bitmap = kmalloc(sizeof(*bitmap), gfp);
> +
> +             if (!bitmap)
> +                     return;
> +             bitmap = this_cpu_cmpxchg(ida_bitmap, NULL, bitmap);
> +             kfree(bitmap);
> +     }
> +}
> +EXPORT_SYMBOL(xb_preload);

Please document the exported API.  It's conventional to do this in
kerneldoc but for some reason kerneldoc makes people write
uninteresting and unuseful documentation.  Be sure to cover the
*useful* stuff: what it does, why it does it, under which circumstances
it should be used, what the caller-provided locking should look like,
what the return values mean, etc.  Stuff which programmers actually
will benefit from knowing.

> +int xb_set_bit(struct xb *xb, unsigned long bit)
>
> ...
>
> +int xb_clear_bit(struct xb *xb, unsigned long bit)

There's quite a lot of common code here.  Did you investigate factoring
that out in some fashion?

> +bool xb_test_bit(const 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)
> +             return false;
> +     if (radix_tree_exception(bitmap)) {
> +             bit += RADIX_TREE_EXCEPTIONAL_SHIFT;
> +             if (bit > BITS_PER_LONG)
> +                     return false;
> +             return (unsigned long)bitmap & (1UL << bit);
> +     }
> +     return test_bit(bit, bitmap->bitmap);
> +}
> +

Missing EXPORT_SYMBOL?


Perhaps all this code should go into a new lib/xbitmap.c.
_______________________________________________
Virtualization mailing list
Virtualization@lists.linux-foundation.org
https://lists.linuxfoundation.org/mailman/listinfo/virtualization

Reply via email to