Skip to contentSkip to conversation

Radix tree range entries

PATCH Matthew Wilcox 2 participants 3 messages Jan 31, 2017 – Feb 1, 2017

Subsystems (2)
lore
Share & tools
lore

Matthew Wilcox

author maintainer
#0 lore raw

Hi Dan, Konstantin,

You've been interested in using range entries in the radix tree rather than higher-order entries. I've built a range entry interface on top of our current radix tree substrate, and it seems to be behaving itself in the test suite. Would you care to try out this patch? Ideas for other tests to add to the test suite would be appreciated too.

There may be some minor conflicts with the current Linus tree; the full patch series can be found here:

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

commit b6444c0557bc1ac5add3c8db66d26a7ba7ccd6a6

Author: Matthew Wilcox <[email protected]>
Date:   Tue Jan 31 11:16:47 2017 -0500

radix-tree: Add range entry support

We have a confirmed customer in the shape of devm_memremap_pages(), so add support for range entries. The documentation lists caveats on their use, but none of these caveats apply to the one user.

include/linux/radix-tree.h +5 -0
index 8984f90..34d0910 100644
@@ -386,6 +386,11 @@ int radix_tree_split(struct radix_tree_root *, unsigned long index,
 			unsigned new_order);
 int radix_tree_join(struct radix_tree_root *, unsigned long index,
 			unsigned new_order, void *);
+int radix_tree_insert_range(struct radix_tree_root *, unsigned long start,
+				unsigned long len, void *entry);
+void *radix_tree_delete_range(struct radix_tree_root *, unsigned long start,
+				unsigned long len);
+
 void **idr_get_free(struct radix_tree_root *, struct radix_tree_iter *,
 			gfp_t, int end);
 
lib/radix-tree.c +162 -21

211 lines not on this page · raw message

tools/include/linux/log2.h +16 -0
index 4144666..729b939 100644
@@ -182,4 +182,20 @@ unsigned long __rounddown_pow_of_two(unsigned long n)
 	__rounddown_pow_of_two(n)		\
  )
 
+/**
+ * order_base_2 - calculate the (rounded up) base 2 order of the argument
+ * @n: parameter
+ *
+ * The first few values calculated by this routine:
+ *  ob2(0) = 0
+ *  ob2(1) = 0
+ *  ob2(2) = 1
+ *  ob2(3) = 2
+ *  ob2(4) = 2
+ *  ob2(5) = 3
+ *  ... and so on.
+ */
+
+#define order_base_2(n) ilog2(roundup_pow_of_two(n))
+
 #endif /* _TOOLS_LINUX_LOG2_H */
tools/testing/radix-tree/Makefile +6 -2
index ecea846..72e293a 100644
@@ -1,10 +1,11 @@
 
 CFLAGS += -I. -I../../include -g -O2 -Wall -D_LGPL_SOURCE -fsanitize=address
 LDFLAGS += -lpthread -lurcu
-TARGETS = main idr-test multiorder
+TARGETS = main idr-test multiorder range
 CORE_OFILES := radix-tree.o idr.o linux.o test.o find_bit.o
 OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \
-	 tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o
+	 tag_check.o multiorder.o idr-test.o iteration_check.o benchmark.o \
+	 range.o
 
 ifdef BENCHMARK
 	CFLAGS += -DBENCHMARK=1
@@ -21,6 +22,9 @@ idr-test: idr-test.o $(CORE_OFILES)
 multiorder: multiorder.o $(CORE_OFILES)
 	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o multiorder
 
+range: range.o $(CORE_OFILES)
+	$(CC) $(CFLAGS) $(LDFLAGS) $^ -o range
+
 clean:
 	$(RM) $(TARGETS) *.o radix-tree.c idr.c
 
tools/testing/radix-tree/main.c +4 -0
index b829127..64c960d 100644
@@ -300,6 +300,10 @@ static void single_thread_tests(bool long_run)
 	rcu_barrier();
 	printv(2, "after multiorder_check: %d allocated, preempt %d\n",
 		nr_allocated, preempt_count);
+	range_checks();
+	rcu_barrier();
+	printv(2, "after range_check: %d allocated, preempt %d\n",
+		nr_allocated, preempt_count);
 	locate_check();
 	rcu_barrier();
 	printv(2, "after locate_check: %d allocated, preempt %d\n",
tools/testing/radix-tree/range.c new file +114 -0

114 lines not on this page · raw message

tools/testing/radix-tree/test.h +2 -0
index 4c42c6b..3b6f1b9 100644
@@ -13,6 +13,7 @@ int __item_insert(struct radix_tree_root *root, struct item *item);
 int item_insert(struct radix_tree_root *root, unsigned long index);
 int item_insert_order(struct radix_tree_root *root, unsigned long index,
 			unsigned order);
+void item_sanity(struct item *, unsigned long index);
 int item_delete(struct radix_tree_root *root, unsigned long index);
 struct item *item_lookup(struct radix_tree_root *root, unsigned long index);
 
@@ -32,6 +33,7 @@ unsigned long find_item(struct radix_tree_root *, void *item);
 
 void tag_check(void);
 void multiorder_checks(void);
+void range_checks(void);
 void iteration_test(unsigned order, unsigned duration);
 void benchmark(void);
 void idr_checks(void);
#1 lore raw
Quoted 17 lines · Matthew Wilcox

Hi Dan, Konstantin,

You've been interested in using range entries in the radix tree rather than higher-order entries. I've built a range entry interface on top of our current radix tree substrate, and it seems to be behaving itself in the test suite. Would you care to try out this patch? Ideas for other tests to add to the test suite would be appreciated too.

There may be some minor conflicts with the current Linus tree; the full patch series can be found here:

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

commit b6444c0557bc1ac5add3c8db66d26a7ba7ccd6a6

Author: Matthew Wilcox <[email protected]>
Date:   Tue Jan 31 11:16:47 2017 -0500
Quoted 7 lines

radix-tree: Add range entry support

We have a confirmed customer in the shape of devm_memremap_pages(), so add support for range entries. The documentation lists caveats on their use, but none of these caveats apply to the one user.

Thanks, I'll take a look. This will let me get rid of the order_at() hack I have in devm_memremap_pages(). I assume there's no requirement that 'start' be aligned to 'len' when calling radix_tree_insert_range()?

author maintainer
#2 lore raw
Quoted 11 lines · Dan Williams
Quoted 5 lines · Matthew Wilcox

We have a confirmed customer in the shape of devm_memremap_pages(), so add support for range entries. The documentation lists caveats on their use, but none of these caveats apply to the one user.

Thanks, I'll take a look. This will let me get rid of the order_at() hack I have in devm_memremap_pages(). I assume there's no requirement that 'start' be aligned to 'len' when calling radix_tree_insert_range()?

No alignment restrictions. If you find something that doesn't work, let me know. From the test suite:

+ for (start = 0; start < 100; start++) {
+ for (len = 1; len < 100; len++) {
+ range_check_1(&tree, start, len);
+ }
+ }

The only restrictions I have is that len must be >0 and start+len can't wrap past ~0UL. These seem like reasonable restrictions to me. Maybe we have some users who want to change the index type from unsigned long to unsigned long long, but I think 32-bit machines are dying out fast enough that we don't care.