Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > linux.kernel > #1730333 > unrolled thread

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

Back to article view | Back to linux.kernel

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: [PATCH v15 1/5] lib/xbitmap: Introduce xbitmap Matthew Wilcox <willy@infradead.org> - 2017-09-11 15:00 +0200
    Re: [PATCH v15 1/5] lib/xbitmap: Introduce xbitmap Wei Wang <wei.w.wang@intel.com> - 2017-09-12 15:30 +0200

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

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.

[toc] | [next] | [standalone]

#1730858

On 09/11/2017 08:54 PM, Matthew Wilcox wrote:
> 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.

This was changed in the previous version and included in that
v13->v14 ChangeLog: https://lkml.org/lkml/2017/8/16/923


> 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.

Probably it shouldn't be modified when the discussion is incomplete:
https://lkml.org/lkml/2017/8/10/36
Sorry about that. Hope we could get more feedback from you on the
changes later.

If you want, we can continue this part from the the v13 patch, which might
be closer to the implementation that you like: 
https://lkml.org/lkml/2017/8/3/60

>> 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.

Based on the previous comments (put all the code to lib/xbitmap.c) and your
comment here, I will move xb_preload() and the above Macro to radix-tree.c,
while leaving the rest in xbitmap.c.

Would this be something you expected? Or would you like to move all back
to radix-tree.c like that in v13?


Best,
Wei

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web