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

[Matthew Wilcox <willy@infradead.org>]

On Mon, Aug 28, 2017 at 06:08:29PM +0800, Wei Wang wrote:
> From: Matthew Wilcox <mawilcox@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@microsoft.com>
> Signed-off-by: Wei Wang <wei.w.wang@intel.com>
> Cc: Andrew Morton <akpm@linux-foundation.org>
> Cc: Michal Hocko <mhocko@kernel.org>
> Cc: Michael S. Tsirkin <mst@redhat.com>

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.

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org.  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>