Radix tree range entries
Subsystems (2)
Matthew Wilcox
maintainerHi 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
@@ -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
@@ -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
@@ -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
@@ -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
@@ -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 );
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
b6444c0557bc1ac5add3c8db66d26a7ba7ccd6a6Author: 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.Signed-off-by Matthew Wilcox <[email protected]>
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()?
Matthew Wilcox
maintainerQuoted 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.Signed-off-by Matthew Wilcox <[email protected]>Thanks, I'll take a look. This will let me get rid of the
order_at()hack I have indevm_memremap_pages(). I assume there's no requirement that 'start' be aligned to 'len' when callingradix_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.