Re: [Qemu-devel] [PATCH v15 1/5] lib/xbitmap: Introduce xbitmap

[Matthew Wilcox]

On Mon, Aug 28, 2017 at 06:08:29PM +0800, Wei Wang wrote:
> From: Matthew Wilcox <address@hidden>
> 
> 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 <address@hidden>
> Signed-off-by: Wei Wang <address@hidden>
> Cc: Andrew Morton <address@hidden>
> Cc: Michal Hocko <address@hidden>
> Cc: Michael S. Tsirkin <address@hidden>

This is quite naughty of you.  You've modified the xbitmap implementation
without any indication in the changelog that you did so.  I don't
think the modifications you made are an improvement, but without any
argumentation from you I don't know why you think they're an improvement.

> diff --git a/lib/radix-tree.c b/lib/radix-tree.c
> index 898e879..ee72e2c 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -496,6 +496,7 @@ static int __radix_tree_preload(gfp_t gfp_mask, unsigned 
> nr)
>  out:
>       return ret;
>  }
> +EXPORT_SYMBOL(__radix_tree_preload);
>  
>  /*
>   * Load up this CPU's radix_tree_node buffer with sufficient objects to

You exported this to modules for some reason.  Why?

> @@ -2003,6 +2018,7 @@ static bool __radix_tree_delete(struct radix_tree_root 
> *root,
>       replace_slot(slot, NULL, node, -1, exceptional);
>       return node && delete_node(root, node, NULL, NULL);
>  }
> +EXPORT_SYMBOL(__radix_tree_delete);
>  
>  /**
>   * radix_tree_iter_delete - delete the entry at this iterator position

Ditto?

> diff --git a/lib/xbitmap.c b/lib/xbitmap.c
> new file mode 100644
> index 0000000..8c55296
> --- /dev/null
> +++ b/lib/xbitmap.c
> @@ -0,0 +1,176 @@
> +#include <linux/slab.h>
> +#include <linux/xbitmap.h>
> +
> +/*
> + * The xbitmap 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)

I don't understand why you moved the xb_preload code here from the
radix tree.  I want all the code which touches the preload implementation
together in one place, which is the radix tree.

> +enum xb_ops {
> +     XB_SET,
> +     XB_CLEAR,
> +     XB_TEST
> +};
> +
> +static int xb_bit_ops(struct xb *xb, unsigned long bit, enum xb_ops ops)
> +{
> +     int ret = 0;
> +     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, tmp;
> +
> +     bit %= IDA_BITMAP_BITS;
> +     ebit = bit + RADIX_TREE_EXCEPTIONAL_SHIFT;
> +
> +     switch (ops) {
> +     case XB_SET:
> +             ret = __radix_tree_create(root, index, 0, &node, &slot);
> +             if (ret)
> +                     return ret;
> +             bitmap = rcu_dereference_raw(*slot);
> +             if (radix_tree_exception(bitmap)) {
> +                     tmp = (unsigned long)bitmap;
> +                     if (ebit < BITS_PER_LONG) {
> +                             tmp |= 1UL << ebit;
> +                             rcu_assign_pointer(*slot, (void *)tmp);
> +                             return 0;
> +                     }
> +                     bitmap = this_cpu_xchg(ida_bitmap, NULL);
> +                     if (!bitmap)
> +                             return -EAGAIN;
> +                     memset(bitmap, 0, sizeof(*bitmap));
> +                     bitmap->bitmap[0] =
> +                                     tmp >> RADIX_TREE_EXCEPTIONAL_SHIFT;
> +                     rcu_assign_pointer(*slot, bitmap);
> +             }
> +             if (!bitmap) {
> +                     if (ebit < BITS_PER_LONG) {
> +                             bitmap = (void *)((1UL << ebit) |
> +                                     RADIX_TREE_EXCEPTIONAL_ENTRY);
> +                             __radix_tree_replace(root, node, slot, bitmap,
> +                                                  NULL, NULL);
> +                             return 0;
> +                     }
> +                     bitmap = this_cpu_xchg(ida_bitmap, NULL);
> +                     if (!bitmap)
> +                             return -EAGAIN;
> +                     memset(bitmap, 0, sizeof(*bitmap));
> +                     __radix_tree_replace(root, node, slot, bitmap, NULL,
> +                                          NULL);
> +             }
> +             __set_bit(bit, bitmap->bitmap);
> +             break;
> +     case XB_CLEAR:
> +             bitmap = __radix_tree_lookup(root, index, &node, &slot);
> +             if (radix_tree_exception(bitmap)) {
> +                     tmp = (unsigned long)bitmap;
> +                     if (ebit >= BITS_PER_LONG)
> +                             return 0;
> +                     tmp &= ~(1UL << ebit);
> +                     if (tmp == RADIX_TREE_EXCEPTIONAL_ENTRY)
> +                             __radix_tree_delete(root, node, slot);
> +                     else
> +                             rcu_assign_pointer(*slot, (void *)tmp);
> +                     return 0;
> +             }
> +             if (!bitmap)
> +                     return 0;
> +             __clear_bit(bit, bitmap->bitmap);
> +             if (bitmap_empty(bitmap->bitmap, IDA_BITMAP_BITS)) {
> +                     kfree(bitmap);
> +                     __radix_tree_delete(root, node, slot);
> +             }
> +             break;
> +     case XB_TEST:
> +             bitmap = radix_tree_lookup(root, index);
> +             if (!bitmap)
> +                     return 0;
> +             if (radix_tree_exception(bitmap)) {
> +                     if (ebit > BITS_PER_LONG)
> +                             return 0;
> +                     return (unsigned long)bitmap & (1UL << bit);
> +             }
> +             ret = test_bit(bit, bitmap->bitmap);
> +             break;
> +     default:
> +             return -EINVAL;
> +     }
> +     return ret;
> +}

This is what I have the biggest problem with.  You've spliced
three functions together into a single 86-line function.  All that
they share is the first 11 lines of setup!  Go back and read
Documentation/process/coding-style.rst section 6 again.


And you've just deleted the test suite.  Test suites are incredibly
important!  They keep us from regressing.