Re: [PATCH v9 09/61] xarray: Replace exceptional entries

[Josef Bacik <josef@toxicpanda.com>]

On Tue, Mar 13, 2018 at 06:25:47AM -0700, Matthew Wilcox wrote:
> From: Matthew Wilcox <mawilcox@microsoft.com>
> 
> Introduce xarray value entries to replace the radix tree exceptional
> entry code.  This is a slight change in encoding to allow the use of an
> extra bit (we can now store BITS_PER_LONG - 1 bits in a value entry).
> It is also a change in emphasis; exceptional entries are intimidating
> and different.  As the comment explains, you can choose to store values
> or pointers in the xarray and they are both first-class citizens.
> 
> Signed-off-by: Matthew Wilcox <mawilcox@microsoft.com>
> ---
>  arch/powerpc/include/asm/book3s/64/pgtable.h    |   4 +-
>  arch/powerpc/include/asm/nohash/64/pgtable.h    |   4 +-
>  drivers/gpu/drm/i915/i915_gem.c                 |  17 ++--
>  drivers/staging/lustre/lustre/mdc/mdc_request.c |   2 +-
>  fs/btrfs/compression.c                          |   2 +-
>  fs/dax.c                                        | 107 ++++++++++++------------
>  fs/proc/task_mmu.c                              |   2 +-
>  include/linux/radix-tree.h                      |  36 ++------
>  include/linux/swapops.h                         |  19 ++---
>  include/linux/xarray.h                          |  54 ++++++++++++
>  lib/idr.c                                       |  61 ++++++--------
>  lib/radix-tree.c                                |  21 ++---
>  mm/filemap.c                                    |  10 +--
>  mm/khugepaged.c                                 |   2 +-
>  mm/madvise.c                                    |   2 +-
>  mm/memcontrol.c                                 |   2 +-
>  mm/mincore.c                                    |   2 +-
>  mm/readahead.c                                  |   2 +-
>  mm/shmem.c                                      |  10 +--
>  mm/swap.c                                       |   2 +-
>  mm/truncate.c                                   |  12 +--
>  mm/workingset.c                                 |  12 ++-
>  tools/testing/radix-tree/idr-test.c             |   6 +-
>  tools/testing/radix-tree/linux/radix-tree.h     |   1 +
>  tools/testing/radix-tree/multiorder.c           |  47 +++++------
>  tools/testing/radix-tree/test.c                 |   2 +-
>  26 files changed, 223 insertions(+), 218 deletions(-)
> 

<snip>

>  
> @@ -453,18 +449,14 @@ int ida_get_new_above(struct ida *ida, int start, int *id)
>  			new += bit;
>  			if (new < 0)
>  				return -ENOSPC;
> -			if (ebit < BITS_PER_LONG) {
> -				bitmap = (void *)((1UL << ebit) |
> -						RADIX_TREE_EXCEPTIONAL_ENTRY);
> -				radix_tree_iter_replace(root, &iter, slot,
> -						bitmap);
> -				*id = new;
> -				return 0;
> +			if (bit < BITS_PER_XA_VALUE) {
> +				bitmap = xa_mk_value(1UL << bit);
> +			} else {
> +				bitmap = this_cpu_xchg(ida_bitmap, NULL);
> +				if (!bitmap)
> +					return -EAGAIN;
> +				__set_bit(bit, bitmap->bitmap);
>  			}
> -			bitmap = this_cpu_xchg(ida_bitmap, NULL);
> -			if (!bitmap)
> -				return -EAGAIN;
> -			__set_bit(bit, bitmap->bitmap);
>  			radix_tree_iter_replace(root, &iter, slot, bitmap);
>  		}
>  

This threw me off a bit, but we do *id = new below.

> @@ -495,9 +487,9 @@ void ida_remove(struct ida *ida, int id)
>  		goto err;
>  
>  	bitmap = rcu_dereference_raw(*slot);
> -	if (radix_tree_exception(bitmap)) {
> +	if (xa_is_value(bitmap)) {
>  		btmp = (unsigned long *)slot;
> -		offset += RADIX_TREE_EXCEPTIONAL_SHIFT;
> +		offset += 1; /* Intimate knowledge of the xa_data encoding */
>  		if (offset >= BITS_PER_LONG)
>  			goto err;
>  	} else {

Ick.

<snip>

> @@ -393,11 +393,11 @@ void ida_check_conv(void)
>  	for (i = 0; i < 1000000; i++) {
>  		int err = ida_get_new(&ida, &id);
>  		if (err == -EAGAIN) {
> -			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 2));
> +			assert((i % IDA_BITMAP_BITS) == (BITS_PER_LONG - 1));
>  			assert(ida_pre_get(&ida, GFP_KERNEL));
>  			err = ida_get_new(&ida, &id);
>  		} else {
> -			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 2));
> +			assert((i % IDA_BITMAP_BITS) != (BITS_PER_LONG - 1));

Can we just use BITS_PER_XA_VALUE here?

Overall looks fine to me, I'm not married to changing any of the nits.

Reviewed-by: Josef Bacik <jbacik@fb.com>

Thanks,

Josef