RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

[Matthew Wilcox]

Thanks, Ross.

Konstantin, I think there are problems with the concept behind this series.  You have multiple entries in the tree with the same value.  That works out fine when the entry is a pointer (eg to a struct page), but not so well when it's an exceptional entry (eg a swap cache entry or a DAX radix tree entry).  If you look at the recent DAX work, you'll see there's a lock bit, and having multiple lock bits is a recipe for disaster.

But I did notice that we have a missing test in the test-suite; one that checks whether replace_slot actually replaces all of the parts of a multiorder entry.  See attachment.

-----Original Message-----
From: Ross Zwisler [mailto:ross.zwisler@xxxxxxxxxxxxxxx] 
Sent: Saturday, August 27, 2016 2:09 PM
To: Matthew Wilcox <mawilcox@xxxxxxxxxxxxx>
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

Hey Matthew,

Just wanted to make sure that you saw this series.

- Ross

On Sat, Aug 27, 2016 at 05:14:34PM +0300, Konstantin Khlebnikov wrote:
> This patch adds function for filling and truncating ranges of slots:
> 
> radix_tree_node *radix_tree_fill_range(root, start, end, item, flags)
> 
> It fills slots in range "begin".."end" with "item" and returns pointer 
> to the last filled node. Filling with NULL truncates range.
> 
> This is intended for managing transparent huge pages in page cache 
> where all entries are aligned but this function can handle arbitrary 
> unaligned ranges. Might be useful for PAT or VMA-like extent trees.
> 
> By default filling range constructs shallow tree: entries are assigned 
> directly inner slots if possible. In worst case any range requires 
> only
> 2 * RADIX_TREE_MAX_PATH nodes. If length is power of two and start 
> index is aligned then all slots are always in single node and requires 
> at most RADIX_TREE_MAX_PATH nodes.
> 
> Function accepts several flags:
> 
> RADIX_TREE_FILL_LEAVES  - build deep tree, insert entry into leaves.
> 
> RADIX_TREE_FILL_OVERWRITE - overwrite instead of failing with -EEXIST.
> 
> RADIX_TREE_FILL_ATOMIC - play well with concurrent RCU-protected lookup:
> fill new nodes with RADIX_TREE_RETRY before inserting them into the tree.
> At following iterations these slots are filled with @item or sub-nodes.
> 
> RADIX_TREE_FILL_CLEAR_TAGS - also clears all tags.
> 
> radix_tree_fill_range() returns pointer to the node which holds the 
> last slot in range, NULL if this is root slot, or ERR_PTR in case of error.
> 
> Thus, radix_tree_fill_range() can handle all operations required for THP:
> 
> * Insert
> Fill range with pointer to head page.
> 
> radix_tree_fill_range(root, index, index + nr_pages - 1, head_page,
> 		      RADIX_TREE_FILL_ATOMIC)
> 
> * Remove
> Fill range with NULL or shadow entry, returned value will be used for 
> linking completely shadow nodes into slab shrinker.
> 
> radix_tree_fill_range(root, index, index + nr_pages - 1, NULL,
> 		      RADIX_TREE_FILL_OVERWRITE)
> 
> * Merge
> Fill range with overwrite to replace 0-order pages with THP.
> 
> radix_tree_fill_range(root, index, index + nr_pages - 1, head_page,
> 		      RADIX_TREE_FILL_OVERWRITE | RADIX_TREE_FILL_ATOMIC)
> 
> * Split
> Two passes: first fill leaves with head_page entry and then replace 
> each slot with pointer to individual tail page. This could be done in 
> single pass but makes radix_tree_fill_range much more complicated.
> 
> radix_tree_fill_range(root, index, index + nr_pages - 1, head_page,
> 		      RADIX_TREE_FILL_LEAVES | RADIX_TREE_FILL_OVERWRITE |
> 		      RADIX_TREE_FILL_ATOMIC);
> radix_tree_for_each_slot(...)
> 	radix_tree_replace_slot(slot, head + iter.index - head->index);
> 
> 
> Page lookup and iterator will return pointer to head page for any index.
> 
> 
> Code inside iterator loop could detect huge entry, handle all 
> sub-pages and jump to next index using new helper function radix_tree_iter_jump():
> 
> slot = radix_tree_iter_jump(&iter, page->index + 
> hpage_nr_pages(page));
> 
> This helper has builtin protection against overflows: jump to index = 
> 0 stops iterator. This uses existing logic in radix_tree_next_chunk():
> if iter.next_index is zero then iter.index must be zero too.
> 
> 
> Tags should be set only for last index of THP range: this way iterator 
> will find them regardless of starting index.
> 
> radix_tree_preload_range() pre-allocates nodes for filling range.
> 
> Signed-off-by: Konstantin Khlebnikov <koct9i@xxxxxxxxx>
> ---
>  include/linux/radix-tree.h |   46 ++++++++
>  lib/radix-tree.c           |  245 ++++++++++++++++++++++++++++++++++++++++++++
>  2 files changed, 291 insertions(+)
> 
> diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h 
> index 4613bf35c311..af33e8d93ec3 100644
> --- a/include/linux/radix-tree.h
> +++ b/include/linux/radix-tree.h
> @@ -319,6 +319,35 @@ static inline void radix_tree_preload_end(void)
>  	preempt_enable();
>  }
>  
> +#define RADIX_TREE_FILL_LEAVES		1 /* build full depth tree */
> +#define RADIX_TREE_FILL_OVERWRITE	2 /* overwrite non-empty slots */
> +#define RADIX_TREE_FILL_CLEAR_TAGS	4 /* clear all tags */
> +#define RADIX_TREE_FILL_ATOMIC		8 /* play well with rcu lookup */
> +
> +struct radix_tree_node *
> +radix_tree_fill_range(struct radix_tree_root *root, unsigned long start,
> +		      unsigned long end, void *item, unsigned int flags);
> +
> +int radix_tree_preload_range(gfp_t gfp_mask, unsigned long start,
> +			     unsigned long end, unsigned int flags);
> +
> +/**
> + * radix_tree_truncate_range  - remove everything in range
> + * @root:	radix tree root
> + * @start:	first index
> + * @end:	last index
> + *
> + * This function removes all items and tags within given range.
> + */
> +static inline void
> +radix_tree_truncate_range(struct radix_tree_root *root,
> +			  unsigned long start, unsigned long end) {
> +	radix_tree_fill_range(root, start, end, NULL,
> +			      RADIX_TREE_FILL_OVERWRITE |
> +			      RADIX_TREE_FILL_CLEAR_TAGS); }
> +
>  /**
>   * struct radix_tree_iter - radix tree iterator state
>   *
> @@ -435,6 +464,23 @@ void **radix_tree_iter_next(struct 
> radix_tree_iter *iter)  }
>  
>  /**
> + * radix_tree_iter_jump - restart iterating from given index if it non-zero
> + * @iter:	iterator state
> + * @index:	next index
> + *
> + * If index is zero when iterator will stop. This protects from 
> +endless loop
> + * when index overflows after visiting last entry.
> + */
> +static inline __must_check
> +void **radix_tree_iter_jump(struct radix_tree_iter *iter, unsigned 
> +long index) {
> +	iter->index = index - 1;
> +	iter->next_index = index;
> +	iter->tags = 0;
> +	return NULL;
> +}
> +
> +/**
>   * radix_tree_chunk_size - get current chunk size
>   *
>   * @iter:	pointer to radix tree iterator
> diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 
> 1b7bf7314141..c46a60065a77 100644
> --- a/lib/radix-tree.c
> +++ b/lib/radix-tree.c
> @@ -36,6 +36,7 @@
>  #include <linux/bitops.h>
>  #include <linux/rcupdate.h>
>  #include <linux/preempt.h>		/* in_interrupt() */
> +#include <linux/err.h>
>  
>  
>  /* Number of nodes in fully populated tree of given height */ @@ 
> -1014,6 +1015,250 @@ void **radix_tree_next_chunk(struct 
> radix_tree_root *root,  EXPORT_SYMBOL(radix_tree_next_chunk);
>  
>  /**
> + * radix_tree_preload_range  - preload nodes for filling range.
> + * @gfp_mask:
> + * @start:	first index
> + * @end:	last index
> + * @flags:	RADIX_TREE_FILL_*
> + */
> +int radix_tree_preload_range(gfp_t gfp_mask, unsigned long start,
> +			     unsigned long end, unsigned int flags) {
> +	unsigned long length = end - start + 1;
> +	int nr_nodes, shift;
> +
> +	/* Preloading doesn't help anything with this gfp mask, skip it */
> +	if (!gfpflags_allow_blocking(gfp_mask)) {
> +		preempt_disable();
> +		return 0;
> +	}
> +
> +	/*
> +	 * For filling leaves tree must cover all indexes in range at all
> +	 * levels plus RADIX_TREE_MAX_PATH required for growing tree depth
> +	 * and only root node is shared for sure.
> +	 *
> +	 * If for aligned range we need RADIX_TREE_MAX_PATH for growing depth
> +	 * and RADIX_TREE_MAX_PATH for path where all slots will be.
> +	 *
> +	 * For arbitrary range we need again RADIX_TREE_MAX_PATH for growing
> +	 * depth and two RADIX_TREE_MAX_PATH chains for constructing arc of
> +	 * slots from leaf to root and back. Only root node is shared.
> +	 */
> +	if (flags & RADIX_TREE_FILL_LEAVES) {
> +		if (start > end)
> +			return -EINVAL;
> +		shift = 0;
> +		nr_nodes = RADIX_TREE_MAX_PATH - 1;
> +		do {
> +			shift += RADIX_TREE_MAP_SHIFT;
> +			nr_nodes += (end >> shift) - (start >> shift) + 1;
> +		} while (shift < RADIX_TREE_INDEX_BITS);
> +	} else if (is_power_of_2(length) && IS_ALIGNED(start, length))
> +		nr_nodes = RADIX_TREE_MAX_PATH * 2 - 1;
> +	else
> +		nr_nodes = RADIX_TREE_MAX_PATH * 3 - 2;
> +	return __radix_tree_preload(gfp_mask, nr_nodes); } 
> +EXPORT_SYMBOL(radix_tree_preload_range);
> +
> +/**
> + * radix_tree_fill_range - fill range of slots
> + * @root:	radix tree root
> + * @start:	first index
> + * @end:	last index
> + * @item:	value for filling, NULL for removing
> + * @flags:	RADIX_TREE_FILL_* flags
> + * Returns:	pointer last node or NULL, ERR_PTR for errors
> + *
> + * By default builds shallow tree: assign entry to inner slots if possible.
> + * In wost case range requires up to 2 * RADIX_TREE_MAX_PATH nodes 
> +plus
> + * RADIX_TREE_MAX_PATH for extending tree depth.
> + *
> + * If length is 2^n and start aligned to it then all slots are in one node.
> + *
> + * This function cannot fill or cut part of bugger range if this 
> +require
> + * spltting inner slots and insering new nodes: fails with -ERANGE.
> + *
> + * With flag RADIX_TREE_FILL_LEAVES builds deep tree and insert @item 
> +into
> + * leaf slots. This requires much more nodes.
> + *
> + * With flag RADIX_TREE_FILL_OVERWRITE removes everything in range 
> +and cut
> + * sub-tree if @item is NULL. Without that flag function undo all 
> +chandges
> + * and fails with code -EEXIST if finds any populated slot.
> + *
> + * With flag RADIX_TREE_FILL_ATOMIC function plays well with 
> +rcu-protected
> + * lookups: it fills new nodes with RADIX_TREE_RETRY before inserting 
> +them
> + * into the tree: lookup will see either old entry, @item or retry entry.
> + * At following iterations these slots are filled with @item or sub-nodes.
> + *
> + * With flag RADIX_TREE_FILL_CLEAR_TAGS also clears all tags.
> + *
> + * Function returns pointer to node which holds the last slot in 
> +range,
> + * NULL if that was root slot, or ERR_PTR: -ENOMEM, -EEXIST, -ERANGE.
> + */
> +struct radix_tree_node *
> +radix_tree_fill_range(struct radix_tree_root *root, unsigned long start,
> +		      unsigned long end, void *item, unsigned int flags) {
> +	unsigned long index = start, maxindex;
> +	struct radix_tree_node *node, *child;
> +	int error, root_shift, shift, tag, offset;
> +	void *entry;
> +
> +	/* Sanity check */
> +	if (start > end)
> +		return ERR_PTR(-EINVAL);
> +
> +	/* Make sure the tree is high enough.  */
> +	root_shift = radix_tree_load_root(root, &node, &maxindex);
> +	if (end > maxindex) {
> +		error = radix_tree_extend(root, end, root_shift);
> +		if (error < 0)
> +			return ERR_PTR(error);
> +		root_shift = error;
> +	}
> +
> +	/* Special case: single slot tree */
> +	if (!root_shift) {
> +		if (node && (!(flags & RADIX_TREE_FILL_OVERWRITE)))
> +			return ERR_PTR(-EEXIST);
> +		if (flags & RADIX_TREE_FILL_CLEAR_TAGS)
> +			root_tag_clear_all(root);
> +		rcu_assign_pointer(root->rnode, item);
> +		return NULL;
> +	}
> +
> +next_node:
> +	node = NULL;
> +	offset = 0;
> +	entry = rcu_dereference_raw(root->rnode);
> +	shift = root_shift;
> +
> +	/* Descend to the index. Do at least one step. */
> +	do {
> +		child = entry_to_node(entry);
> +		shift -= RADIX_TREE_MAP_SHIFT;
> +		if (!child || !radix_tree_is_internal_node(entry)) {
> +			/* Entry wider than range */
> +			if (child) {
> +				error = -ERANGE;
> +				goto undo;
> +			}
> +			/* Hole wider tnan truncated range */
> +			if (!item)
> +				goto skip_node;
> +			child = radix_tree_node_alloc(root);
> +			if (!child) {
> +				error = -ENOMEM;
> +				goto undo;
> +			}
> +			child->shift = shift;
> +			child->offset = offset;
> +			child->parent = node;
> +			/* Populate range with retry entries. */
> +			if (flags & RADIX_TREE_FILL_ATOMIC) {
> +				int idx = (index >> shift) &
> +					   RADIX_TREE_MAP_MASK;
> +				int last = RADIX_TREE_MAP_SIZE;
> +
> +				if (end < (index | shift_maxindex(shift)))
> +					last = (end >> shift) &
> +						RADIX_TREE_MAP_MASK;
> +				for (; idx <= last; idx++)
> +					child->slots[idx] = RADIX_TREE_RETRY;
> +			}
> +			entry = node_to_entry(child);
> +			if (node) {
> +				rcu_assign_pointer(node->slots[offset], entry);
> +				node->count++;
> +			} else
> +				rcu_assign_pointer(root->rnode, entry);
> +		}
> +		node = child;
> +		offset = (index >> shift) & RADIX_TREE_MAP_MASK;
> +		entry = rcu_dereference_raw(node->slots[offset]);
> +
> +		/* Stop if find leaf or slot inside range */
> +	} while ((flags & RADIX_TREE_FILL_LEAVES) ? shift :
> +			((index & ((1ul << shift) - 1)) ||
> +			 (index | ((1ul << shift) - 1)) > end));
> +
> +next_slot:
> +	/* NULL or retry entry */
> +	if (entry <= RADIX_TREE_RETRY)
> +		goto fill;
> +
> +	if (!(flags & RADIX_TREE_FILL_OVERWRITE)) {
> +		error = -EEXIST;
> +		goto undo;
> +	}
> +
> +	/* Cut sub-tree */
> +	if (unlikely(radix_tree_is_internal_node(entry))) {
> +		rcu_assign_pointer(node->slots[offset], item);
> +		child = entry_to_node(entry);
> +		offset = 0;
> +		do {
> +			entry = rcu_dereference_raw(child->slots[offset]);
> +			if (entry)
> +				child->count--;
> +			if (radix_tree_is_internal_node(entry)) {
> +				child = entry_to_node(entry);
> +				offset = 0;
> +			} else if (++offset == RADIX_TREE_MAP_SIZE) {
> +				offset = child->offset;
> +				entry = child->parent;
> +				WARN_ON_ONCE(child->count);
> +				radix_tree_node_free(child);
> +				child = entry;
> +			}
> +		} while (child != node);
> +	}
> +
> +	if (flags & RADIX_TREE_FILL_CLEAR_TAGS) {
> +		for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
> +			node_tag_clear(root, node, tag, offset);
> +	}
> +
> +	/* Skip the rest if we're cleared class slot in node */
> +	if (!--node->count && !item && __radix_tree_delete_node(root, node))
> +		goto skip_node;
> +
> +
> +fill:
> +	rcu_assign_pointer(node->slots[offset], item);
> +	if (item)
> +		node->count++;
> +
> +	index += 1ul << shift;
> +	if (index - 1 == end)
> +		return node;
> +
> +	/* Next slot in this node and still in range */
> +	if (index + (1ul << shift) - 1 <= end &&
> +			++offset < RADIX_TREE_MAP_SIZE) {
> +		entry = rcu_dereference_raw(node->slots[offset]);
> +		goto next_slot;
> +	}
> +
> +	goto next_node;
> +
> +skip_node:
> +	index |= shift_maxindex(shift);
> +	if (index++ >= end)
> +		return node;
> +	goto next_node;
> +
> +undo:
> +	if (index > start)
> +		radix_tree_fill_range(root, start, index - 1, NULL,
> +				      RADIX_TREE_FILL_OVERWRITE);
> +	return ERR_PTR(error);
> +}
> +EXPORT_SYMBOL(radix_tree_fill_range);
> +
> +/**
>   * radix_tree_range_tag_if_tagged - for each item in given range set given
>   *				   tag if item has another tag set
>   * @root:		radix tree root
>

Attachment: rtts.replace-slot.diff
Description: rtts.replace-slot.diff