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

Groups > linux.kernel > #1471188 > unrolled thread

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

Back to article view | Back to linux.kernel

Contents

  [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-27 16:20 +0200
    RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 17:40 +0200
      Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-29 18:20 +0200
        Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-08-29 20:20 +0200
          RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 21:10 +0200
            Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 00:00 +0200
              Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:10 +0200
                Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 00:30 +0200
                  Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 01:00 +0200
                    Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-01 08:20 +0200
                      RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-09-02 20:20 +0200
                        Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-03 07:00 +0200
                  RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-31 17:00 +0200
                    Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Dan Williams <dan.j.williams@intel.com> - 2016-08-31 18:50 +0200
                      Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Konstantin Khlebnikov <koct9i@gmail.com> - 2016-09-01 08:20 +0200
            Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:10 +0200
        RE: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Matthew Wilcox <mawilcox@microsoft.com> - 2016-08-29 20:30 +0200
    Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range Ross Zwisler <ross.zwisler@linux.intel.com> - 2016-08-31 00:40 +0200

#1471188 — [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

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@gmail.com>
---
 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

[toc] | [next] | [standalone]

#1471935

[Multipart message — attachments visible in raw view] — view raw

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@linux.intel.com] 
Sent: Saturday, August 27, 2016 2:09 PM
To: Matthew Wilcox <mawilcox@microsoft.com>
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@gmail.com>
> ---
>  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
> 

[toc] | [prev] | [next] | [standalone]

#1471965

On Mon, Aug 29, 2016 at 6:21 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> 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.
>

I see no problem here. They could use lock bit at first or last entry.
Anyway all changes should be protecred by lock at mapping.


> 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@linux.intel.com]
> Sent: Saturday, August 27, 2016 2:09 PM
> To: Matthew Wilcox <mawilcox@microsoft.com>
> 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@gmail.com>
>> ---
>>  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
>>

[toc] | [prev] | [next] | [standalone]

#1472041

On Mon, Aug 29, 2016 at 9:08 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> The DAX lock bit is analogous to the PageLock.  You can't serialise on the mapping lock; the contention will be too high.

I mean DAX lock bit is protected by mapping lock thus we can set/clear
it for all entries if needed.

>
> And the point of having the radix tree support the same entry for many indices is that we don't have to go and probe the radix tree multiple times looking for the first or last entry.  We just look up the index, then use the entry we got back.

Right, but lookup function can also return pointer for node --
fininding first or last entries is trivial here.
We could simply scan back/forward or if huge DAX order is known then
just align slot pointer to first or last entry.

>
> -----Original Message-----
> From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
> Sent: Monday, August 29, 2016 12:14 PM
> To: Matthew Wilcox <mawilcox@microsoft.com>
> Cc: Ross Zwisler <ross.zwisler@linux.intel.com>; linux-kernel@vger.kernel.org
> Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range
>
> On Mon, Aug 29, 2016 at 6:21 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> 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.
>>
>
> I see no problem here. They could use lock bit at first or last entry.
> Anyway all changes should be protecred by lock at mapping.
>
>

[toc] | [prev] | [next] | [standalone]

#1472064

It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.

Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.

-----Original Message-----
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com] 
Sent: Monday, August 29, 2016 2:16 PM
To: Matthew Wilcox <mawilcox@microsoft.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>; linux-kernel@vger.kernel.org
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Mon, Aug 29, 2016 at 9:08 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> The DAX lock bit is analogous to the PageLock.  You can't serialise on the mapping lock; the contention will be too high.

I mean DAX lock bit is protected by mapping lock thus we can set/clear it for all entries if needed.

>
> And the point of having the radix tree support the same entry for many indices is that we don't have to go and probe the radix tree multiple times looking for the first or last entry.  We just look up the index, then use the entry we got back.

Right, but lookup function can also return pointer for node -- fininding first or last entries is trivial here.
We could simply scan back/forward or if huge DAX order is known then just align slot pointer to first or last entry.

>
> -----Original Message-----
> From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
> Sent: Monday, August 29, 2016 12:14 PM
> To: Matthew Wilcox <mawilcox@microsoft.com>
> Cc: Ross Zwisler <ross.zwisler@linux.intel.com>; 
> linux-kernel@vger.kernel.org
> Subject: Re: [PATCH RFC 1/4] lib/radix: add universal 
> radix_tree_fill_range
>
> On Mon, Aug 29, 2016 at 6:21 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> 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.
>>
>
> I see no problem here. They could use lock bit at first or last entry.
> Anyway all changes should be protecred by lock at mapping.
>
>

[toc] | [prev] | [next] | [standalone]

#1472898

On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>
> Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.

I'd use a fill range api for the radix backing get_dev_pagemap() and
potentially another use in device-dax.  It centralizes the common
routine of breaking down a range into its constituent power-of-2
ranges.

[toc] | [prev] | [next] | [standalone]

#1472903

On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
> >
> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
> 
> I'd use a fill range api for the radix backing get_dev_pagemap() and
> potentially another use in device-dax.  It centralizes the common
> routine of breaking down a range into its constituent power-of-2
> ranges.

Does your usage not work with the current sibling & canonical entry model?

[toc] | [prev] | [next] | [standalone]

#1472911

On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler
<ross.zwisler@linux.intel.com> wrote:
> On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>> >
>> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>>
>> I'd use a fill range api for the radix backing get_dev_pagemap() and
>> potentially another use in device-dax.  It centralizes the common
>> routine of breaking down a range into its constituent power-of-2
>> ranges.
>
> Does your usage not work with the current sibling & canonical entry model?

It does, but I find myself writing code to walk a range and determine
the order of each entry as I insert them.  I can see other users
needing the same sort of insert helper and the aspect I like of
Konstantin's proposed change is that the functionality is part of the
core implementation rather than left to be duplicated in each user.

[toc] | [prev] | [next] | [standalone]

#1472930

On Tue, Aug 30, 2016 at 03:21:24PM -0700, Dan Williams wrote:
> On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler
> <ross.zwisler@linux.intel.com> wrote:
> > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
> >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
> >> >
> >> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
> >>
> >> I'd use a fill range api for the radix backing get_dev_pagemap() and
> >> potentially another use in device-dax.  It centralizes the common
> >> routine of breaking down a range into its constituent power-of-2
> >> ranges.
> >
> > Does your usage not work with the current sibling & canonical entry model?
> 
> It does, but I find myself writing code to walk a range and determine
> the order of each entry as I insert them.  I can see other users
> needing the same sort of insert helper and the aspect I like of
> Konstantin's proposed change is that the functionality is part of the
> core implementation rather than left to be duplicated in each user.

Perhaps the answer is to have them both?  Matthew's multi-order radix
functionality with siblings for those of us that really *want* a single
canonical entry that we can look up, use tags on, etc.   And Konstantin's
method where we insert a bunch of duplicate entries that don't have sibling
pointers?  Is there a reason why they can't coexist?

[toc] | [prev] | [next] | [standalone]

#1474073

On Wed, Aug 31, 2016 at 1:53 AM, Ross Zwisler
<ross.zwisler@linux.intel.com> wrote:
> On Tue, Aug 30, 2016 at 03:21:24PM -0700, Dan Williams wrote:
>> On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler
>> <ross.zwisler@linux.intel.com> wrote:
>> > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>> >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>> >> >
>> >> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>> >>
>> >> I'd use a fill range api for the radix backing get_dev_pagemap() and
>> >> potentially another use in device-dax.  It centralizes the common
>> >> routine of breaking down a range into its constituent power-of-2
>> >> ranges.
>> >
>> > Does your usage not work with the current sibling & canonical entry model?
>>
>> It does, but I find myself writing code to walk a range and determine
>> the order of each entry as I insert them.  I can see other users
>> needing the same sort of insert helper and the aspect I like of
>> Konstantin's proposed change is that the functionality is part of the
>> core implementation rather than left to be duplicated in each user.
>
> Perhaps the answer is to have them both?  Matthew's multi-order radix
> functionality with siblings for those of us that really *want* a single
> canonical entry that we can look up, use tags on, etc.   And Konstantin's
> method where we insert a bunch of duplicate entries that don't have sibling
> pointers?  Is there a reason why they can't coexist?

I'm not all against "sibling" entries, I just don't want to mess them
into iterator and
common lookup routines. This is redundant.

Actually it's very easy to integrate similar "sibling" entries into my
filling function.

That will be yet another flag which tells to assign given entry only
to the first slot and
fill following tail with reference to that first slot. Just a pointer
with both lower bits set to
distinguish it from exceptional and internal pointers.

I think it's better to call them "indirect" entries because this will
work for arbitrary
ranges too where they are not siblings at all and may be located in
several nodes.

[toc] | [prev] | [next] | [standalone]

#1475388

I have a rewrite of the iterators; would you like to take a look?

http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-09-02

There's five distinct sets of changes in that tree:

1. Test suite enhancements (first 8 patches)
2. Split/Join (patches 9-11)
3. Misc cleanups (patches 12-16)
4. Iterator rewrite (patches 17-19)
5. IDR rewrite (patches 20-25)

I could rebase the cleanups & iterator rewrite on top of Linus' tree if we don't want to get the split/join functionality into 4.9.

-----Original Message-----
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com] 
Sent: Thursday, September 1, 2016 2:12 AM
To: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Dan Williams <dan.j.williams@intel.com>; Matthew Wilcox <mawilcox@microsoft.com>; linux-kernel@vger.kernel.org
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Wed, Aug 31, 2016 at 1:53 AM, Ross Zwisler <ross.zwisler@linux.intel.com> wrote:
> On Tue, Aug 30, 2016 at 03:21:24PM -0700, Dan Williams wrote:
>> On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler 
>> <ross.zwisler@linux.intel.com> wrote:
>> > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>> >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>> >> >
>> >> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>> >>
>> >> I'd use a fill range api for the radix backing get_dev_pagemap() 
>> >> and potentially another use in device-dax.  It centralizes the 
>> >> common routine of breaking down a range into its constituent 
>> >> power-of-2 ranges.
>> >
>> > Does your usage not work with the current sibling & canonical entry model?
>>
>> It does, but I find myself writing code to walk a range and determine 
>> the order of each entry as I insert them.  I can see other users 
>> needing the same sort of insert helper and the aspect I like of 
>> Konstantin's proposed change is that the functionality is part of the 
>> core implementation rather than left to be duplicated in each user.
>
> Perhaps the answer is to have them both?  Matthew's multi-order radix 
> functionality with siblings for those of us that really *want* a single
> canonical entry that we can look up, use tags on, etc.   And Konstantin's
> method where we insert a bunch of duplicate entries that don't have 
> sibling pointers?  Is there a reason why they can't coexist?

I'm not all against "sibling" entries, I just don't want to mess them into iterator and common lookup routines. This is redundant.

Actually it's very easy to integrate similar "sibling" entries into my filling function.

That will be yet another flag which tells to assign given entry only to the first slot and fill following tail with reference to that first slot. Just a pointer with both lower bits set to distinguish it from exceptional and internal pointers.

I think it's better to call them "indirect" entries because this will work for arbitrary ranges too where they are not siblings at all and may be located in several nodes.

[toc] | [prev] | [next] | [standalone]

#1475540

On Fri, Sep 2, 2016 at 8:59 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> I have a rewrite of the iterators; would you like to take a look?
>
> http://git.infradead.org/users/willy/linux-dax.git/shortlog/refs/heads/idr-2016-09-02
>
> There's five distinct sets of changes in that tree:
>
> 1. Test suite enhancements (first 8 patches)
> 2. Split/Join (patches 9-11)
> 3. Misc cleanups (patches 12-16)
> 4. Iterator rewrite (patches 17-19)

Have you compared performance?
There is simple benchmark in my patchset.

> 5. IDR rewrite (patches 20-25)

Why? I don't see reason for that.

>
> I could rebase the cleanups & iterator rewrite on top of Linus' tree if we don't want to get the split/join functionality into 4.9.
>
> -----Original Message-----
> From: Konstantin Khlebnikov [mailto:koct9i@gmail.com]
> Sent: Thursday, September 1, 2016 2:12 AM
> To: Ross Zwisler <ross.zwisler@linux.intel.com>
> Cc: Dan Williams <dan.j.williams@intel.com>; Matthew Wilcox <mawilcox@microsoft.com>; linux-kernel@vger.kernel.org
> Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range
>
> On Wed, Aug 31, 2016 at 1:53 AM, Ross Zwisler <ross.zwisler@linux.intel.com> wrote:
>> On Tue, Aug 30, 2016 at 03:21:24PM -0700, Dan Williams wrote:
>>> On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler
>>> <ross.zwisler@linux.intel.com> wrote:
>>> > On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>>> >> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>>> >> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>>> >> >
>>> >> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>>> >>
>>> >> I'd use a fill range api for the radix backing get_dev_pagemap()
>>> >> and potentially another use in device-dax.  It centralizes the
>>> >> common routine of breaking down a range into its constituent
>>> >> power-of-2 ranges.
>>> >
>>> > Does your usage not work with the current sibling & canonical entry model?
>>>
>>> It does, but I find myself writing code to walk a range and determine
>>> the order of each entry as I insert them.  I can see other users
>>> needing the same sort of insert helper and the aspect I like of
>>> Konstantin's proposed change is that the functionality is part of the
>>> core implementation rather than left to be duplicated in each user.
>>
>> Perhaps the answer is to have them both?  Matthew's multi-order radix
>> functionality with siblings for those of us that really *want* a single
>> canonical entry that we can look up, use tags on, etc.   And Konstantin's
>> method where we insert a bunch of duplicate entries that don't have
>> sibling pointers?  Is there a reason why they can't coexist?
>
> I'm not all against "sibling" entries, I just don't want to mess them into iterator and common lookup routines. This is redundant.
>
> Actually it's very easy to integrate similar "sibling" entries into my filling function.
>
> That will be yet another flag which tells to assign given entry only to the first slot and fill following tail with reference to that first slot. Just a pointer with both lower bits set to distinguish it from exceptional and internal pointers.
>
> I think it's better to call them "indirect" entries because this will work for arbitrary ranges too where they are not siblings at all and may be located in several nodes.

[toc] | [prev] | [next] | [standalone]

#1473582

I'm not at all against the idea of having a tree which supports ranges, except that we already have one; the interval tree.  Did you investigate using the interval tree for your use case?

-----Original Message-----
From: Dan Williams [mailto:dan.j.williams@intel.com] 
Sent: Tuesday, August 30, 2016 6:21 PM
To: Ross Zwisler <ross.zwisler@linux.intel.com>
Cc: Matthew Wilcox <mawilcox@microsoft.com>; Konstantin Khlebnikov <koct9i@gmail.com>; linux-kernel@vger.kernel.org
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Tue, Aug 30, 2016 at 3:03 PM, Ross Zwisler <ross.zwisler@linux.intel.com> wrote:
> On Tue, Aug 30, 2016 at 02:56:17PM -0700, Dan Williams wrote:
>> On Mon, Aug 29, 2016 at 11:52 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> > It may be protected by the mapping lock in the current code, but I would it expect it to become an RCU lookup + lock eventually.  No mapping lock, just like the page cache.
>> >
>> > Even if we can work around it, why do we want to?  What's the compelling reason to change from the current radix tree representation of order-N entries to an arbitrary range?  There are no in-kernel users right now; is there a performance reason to change?  We don't usually change an API in anticipation of future users appearing, particularly when the API makes it harder for the existing users to use it.
>>
>> I'd use a fill range api for the radix backing get_dev_pagemap() and 
>> potentially another use in device-dax.  It centralizes the common 
>> routine of breaking down a range into its constituent power-of-2 
>> ranges.
>
> Does your usage not work with the current sibling & canonical entry model?

It does, but I find myself writing code to walk a range and determine the order of each entry as I insert them.  I can see other users needing the same sort of insert helper and the aspect I like of Konstantin's proposed change is that the functionality is part of the core implementation rather than left to be duplicated in each user.

[toc] | [prev] | [next] | [standalone]

#1473687

On Wed, Aug 31, 2016 at 7:57 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> I'm not at all against the idea of having a tree which supports ranges, except that we already have one; the interval tree.  Did you investigate using the interval tree for your use case?

I am continuing to investigate, but that is orthogonal to whether
Konstantin's changes are an improvement for the radix implementation.
Hmm, would we have ended up with two data-structures if a range-based
radix was available?

The benefits I see is that it simplifies insertion as it no longer
needs to explicitly manage the order of the entries, and, iiuc, let's
the user skip the sibling-to-head conversion when it is not needed
which simplifies lookups.

[toc] | [prev] | [next] | [standalone]

#1474071

On Wed, Aug 31, 2016 at 7:36 PM, Dan Williams <dan.j.williams@intel.com> wrote:
> On Wed, Aug 31, 2016 at 7:57 AM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
>> I'm not at all against the idea of having a tree which supports ranges, except that we already have one; the interval tree.  Did you investigate using the interval tree for your use case?
>
> I am continuing to investigate, but that is orthogonal to whether
> Konstantin's changes are an improvement for the radix implementation.
> Hmm, would we have ended up with two data-structures if a range-based
> radix was available?

Interval tree is a augmented rb-tree. AFAIK it doesn't support RCU lookup
without special dances with sequential counters - some branches disappears
from RCU readers during rebalance.

>
> The benefits I see is that it simplifies insertion as it no longer
> needs to explicitly manage the order of the entries, and, iiuc, let's
> the user skip the sibling-to-head conversion when it is not needed
> which simplifies lookups.

[toc] | [prev] | [next] | [standalone]

#1472904

On Mon, Aug 29, 2016 at 06:52:54PM +0000, Matthew Wilcox wrote:
> It may be protected by the mapping lock in the current code, but I would it
> expect it to become an RCU lookup + lock eventually.  No mapping lock, just
> like the page cache.
> 
> Even if we can work around it, why do we want to?  What's the compelling
> reason to change from the current radix tree representation of order-N
> entries to an arbitrary range?  There are no in-kernel users right now; is
> there a performance reason to change?  We don't usually change an API in
> anticipation of future users appearing, particularly when the API makes it
> harder for the existing users to use it.

I do have a patch set out for review which uses the multi-order nature of the
radix tree:

https://lkml.org/lkml/2016/8/23/725

This code takes advantage of the fact that using the radix tree for an order-0
entry is the same as for a multi-order entry.  Both have a single lock bit,
and a single entry that i need to use for lookups, sets, locking and
unlocking.

My usage fits well with the current implementation of the radix tree, and I'd
like to keep it simple if I can.

[toc] | [prev] | [next] | [standalone]

#1472046

The DAX lock bit is analogous to the PageLock.  You can't serialise on the mapping lock; the contention will be too high.

And the point of having the radix tree support the same entry for many indices is that we don't have to go and probe the radix tree multiple times looking for the first or last entry.  We just look up the index, then use the entry we got back.

-----Original Message-----
From: Konstantin Khlebnikov [mailto:koct9i@gmail.com] 
Sent: Monday, August 29, 2016 12:14 PM
To: Matthew Wilcox <mawilcox@microsoft.com>
Cc: Ross Zwisler <ross.zwisler@linux.intel.com>; linux-kernel@vger.kernel.org
Subject: Re: [PATCH RFC 1/4] lib/radix: add universal radix_tree_fill_range

On Mon, Aug 29, 2016 at 6:21 PM, Matthew Wilcox <mawilcox@microsoft.com> wrote:
> 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.
>

I see no problem here. They could use lock bit at first or last entry.
Anyway all changes should be protecred by lock at mapping.

[toc] | [prev] | [next] | [standalone]

#1472915

On Sat, Aug 27, 2016 at 05:14:34PM +0300, Konstantin Khlebnikov wrote:
> Tags should be set only for last index of THP range: this way iterator
> will find them regardless of starting index.

I don't think this works well for DAX.  We really want to to have the tags be
consistent for all indices within a multi-order range.  Meaning, if I fault in
an order-9 fault, and then I get a PTE write fault to anywhere within that
range, I want to be able to do a lookup, find the one canonical entry that has
my dirty tags, flush, and eventually I want to be able to clear that one tag.

I agree that it's *possible* to do all of this with your code, but it puts a
lot of onus on the user.  I now have to have two paths, one for order-0
entries, and one for multi-order entries where I know to use a specific entry
as my canonical entry where I can count on the log bit, on tags, etc.

This was actually the way that it was done with the old PMD code.   We used
the first aligned index for the PMD to be the one source of truth.  On every
fault I would first check to see if there was a PMD aligned entry, and then if
not I would treat it like a normal 4k fault.  The multi-order radix tree with
sibling entries was a huge step forward.

I guess my question is the same as Matthew's: what is the problem you need to
solve with this code, and why can't the current code be made to solve it?

[toc] | [prev] | [standalone]

Back to top | Article view | linux.kernel

csiph-web