On Tue, Mar 13, 2018 at 06:25:47AM -0700, Matthew Wilcox wrote:
> From: Matthew Wilcox <[email protected]>
>
> 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 <[email protected]>
> ---
> 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 <[email protected]>
Thanks,
Josef
