From 439c7a5909d89685b7afbe3d8eda83b7140014e3 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Sat, 13 Oct 2018 07:47:30 -0400 Subject: [PATCH] radix tree tests: Convert regression2 to XArray The regression2 test was the last user of radix_tree_gang_lookup_tag_slot() and was testing functionality that was only used by the page cache, so it makes sense to convert it to the XArray. The actual bug that it attempts to catch was really in radix_tree_range_tag_if_tagged() which was deleted months ago. Signed-off-by: Matthew Wilcox --- include/linux/radix-tree.h | 4 -- lib/radix-tree.c | 38 +----------- tools/testing/radix-tree/regression2.c | 84 ++++++++++++-------------- 3 files changed, 38 insertions(+), 88 deletions(-) diff --git a/include/linux/radix-tree.h b/include/linux/radix-tree.h index b5116013f27e..a9581ade2314 100644 --- a/include/linux/radix-tree.h +++ b/include/linux/radix-tree.h @@ -122,7 +122,6 @@ struct radix_tree_iter { * radix_tree_tag_get * radix_tree_gang_lookup * radix_tree_gang_lookup_tag - * radix_tree_gang_lookup_tag_slot * radix_tree_tagged * * The first 7 functions are able to be called locklessly, using RCU. The @@ -238,9 +237,6 @@ void radix_tree_iter_tag_clear(struct radix_tree_root *, unsigned int radix_tree_gang_lookup_tag(const struct radix_tree_root *, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag); -unsigned int radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *, - void __rcu ***results, unsigned long first_index, - unsigned int max_items, unsigned int tag); int radix_tree_tagged(const struct radix_tree_root *, unsigned int tag); static inline void radix_tree_preload_end(void) diff --git a/lib/radix-tree.c b/lib/radix-tree.c index 18c1dfbb1765..d46e6b60e2ef 100644 --- a/lib/radix-tree.c +++ b/lib/radix-tree.c @@ -910,8 +910,7 @@ void __radix_tree_replace(struct radix_tree_root *root, * @slot: pointer to slot * @item: new item to store in the slot. * - * For use with radix_tree_lookup_slot() and - * radix_tree_gang_lookup_tag_slot(). Caller must hold tree write locked + * For use with radix_tree_lookup_slot(). Caller must hold tree write locked * across slot lookup and replacement. * * NOTE: This cannot be used to switch between non-entries (empty slots), @@ -1335,41 +1334,6 @@ radix_tree_gang_lookup_tag(const struct radix_tree_root *root, void **results, } EXPORT_SYMBOL(radix_tree_gang_lookup_tag); -/** - * radix_tree_gang_lookup_tag_slot - perform multiple slot lookup on a - * radix tree based on a tag - * @root: radix tree root - * @results: where the results of the lookup are placed - * @first_index: start the lookup from this key - * @max_items: place up to this many items at *results - * @tag: the tag index (< RADIX_TREE_MAX_TAGS) - * - * Performs an index-ascending scan of the tree for present items which - * have the tag indexed by @tag set. Places the slots at *@results and - * returns the number of slots which were placed at *@results. - */ -unsigned int -radix_tree_gang_lookup_tag_slot(const struct radix_tree_root *root, - void __rcu ***results, unsigned long first_index, - unsigned int max_items, unsigned int tag) -{ - struct radix_tree_iter iter; - void __rcu **slot; - unsigned int ret = 0; - - if (unlikely(!max_items)) - return 0; - - radix_tree_for_each_tagged(slot, root, &iter, first_index, tag) { - results[ret] = slot; - if (++ret == max_items) - break; - } - - return ret; -} -EXPORT_SYMBOL(radix_tree_gang_lookup_tag_slot); - static bool __radix_tree_delete(struct radix_tree_root *root, struct radix_tree_node *node, void __rcu **slot) { diff --git a/tools/testing/radix-tree/regression2.c b/tools/testing/radix-tree/regression2.c index f2c7e640a919..cb01340f4b9e 100644 --- a/tools/testing/radix-tree/regression2.c +++ b/tools/testing/radix-tree/regression2.c @@ -2,51 +2,42 @@ /* * Regression2 * Description: - * Toshiyuki Okajima describes the following radix-tree bug: + * Toshiyuki Okajima describes the following bug, originally found in the + * radix tree and now translated into XArray terminology: * - * In the following case, we can get a hangup on - * radix_radix_tree_gang_lookup_tag_slot. + * In the following case, we can get a hang in xa_extract. * - * 0. The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of - * a certain item has PAGECACHE_TAG_DIRTY. - * 1. radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY, - * PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag - * for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with - * PAGECACHE_TAG_DIRTY within the range from start to end. As the result, - * There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has - * PAGECACHE_TAG_TOWRITE. - * 2. An item is added into the radix tree and then the level of it is - * extended into 2 from 1. At that time, the new radix tree node succeeds - * the tag status of the root tag. Therefore the tag of the new radix tree - * node has PAGECACHE_TAG_TOWRITE but there is not slot with - * PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node. - * 3. The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY. - * 4. All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are - * released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the - * radix tree.) As the result, the slot of the radix tree node is NULL but - * the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE. - * 5. radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls - * __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't - * change the index that is the input and output parameter. Because the 1st - * slot of the radix tree node is NULL, but the tag which corresponds to - * the slot has PAGECACHE_TAG_TOWRITE. - * Therefore radix_tree_gang_lookup_tag_slot tries to get some items by - * calling __lookup_tag, but it cannot get any items forever. + * 0. The xarray contains XA_CHUNK_SIZE items. And a certain entry is marked + * with PAGECACHE_TAG_DIRTY. + * 1. tag_tagged_items(, start, end, , PAGECACHE_TAG_DIRTY, + * PAGECACHE_TAG_TOWRITE) is called to set PAGECACHE_TAG_TOWRITE on + * entries which have PAGECACHE_TAG_DIRTY. However, there is no entry with + * PAGECACHE_TAG_DIRTY within the range from start to end. As a result, + * there is no entry with PAGECACHE_TAG_TOWRITE but the root is marked + * PAGECACHE_TAG_TOWRITE. + * 2. An item is added into the xarray and then the level of it is + * extended into 2 from 1. At that time, the new xa_node inherits + * the mark from the root. Therefore the new xa_node has + * PAGECACHE_TAG_TOWRITE but none of its children have that mark. + * 3. The PAGECACHE_TAG_DIRTY mark is cleared from the entry in step 0. + * 4. All entries within the index range from 0 to XA_CHUNK_SIZE - 1 are + * released (only the entry at index XA_CHUNK_SIZE exists in the + * xarray). As the result, the slot of the xa_node is NULL but + * the slot still has PAGECACHE_TAG_TOWRITE set. + * 5. xa_extract(, PAGECACHE_TAG_TOWRITE) finds slot 0 has the tag set + * and tries to get some items, but it spins forever. * - * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag - * if it doesn't set any tags within the specified range. + * The fix is to change tag_tagged_items() to not mark the root + * if it doesn't set any marks within the specified range. * * Running: * This test should run to completion immediately. The above bug would cause it * to hang indefinitely. - * - * Upstream commit: - * Not yet */ #include #include #include -#include +#include #include #include @@ -57,8 +48,8 @@ #define PAGECACHE_TAG_WRITEBACK XA_MARK_1 #define PAGECACHE_TAG_TOWRITE XA_MARK_2 -static RADIX_TREE(mt_tree, GFP_KERNEL); -unsigned long page_count = 0; +static DEFINE_XARRAY(mt_tree); +static unsigned long page_count = 0; struct page { unsigned long index; @@ -77,7 +68,7 @@ void regression2_test(void) { int i; struct page *p; - int max_slots = RADIX_TREE_MAP_SIZE; + int max_slots = XA_CHUNK_SIZE; unsigned long int start, end; struct page *pages[1]; @@ -85,9 +76,9 @@ void regression2_test(void) /* 0. */ for (i = 0; i <= max_slots - 1; i++) { p = page_alloc(); - radix_tree_insert(&mt_tree, i, p); + xa_store(&mt_tree, i, p, GFP_KERNEL); } - radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); + xa_set_mark(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); /* 1. */ start = 0; @@ -97,27 +88,26 @@ void regression2_test(void) /* 2. */ p = page_alloc(); - radix_tree_insert(&mt_tree, max_slots, p); + xa_store(&mt_tree, max_slots, p, GFP_KERNEL); /* 3. */ - radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); + xa_clear_mark(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY); /* 4. */ for (i = max_slots - 1; i >= 0; i--) - free(radix_tree_delete(&mt_tree, i)); + free(xa_erase(&mt_tree, i)); /* 5. */ - // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot - // can return. + // NOTE: start should not be 0 because xa_extract can return. start = 1; end = max_slots - 2; - radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end, + xa_extract(&mt_tree, (void **)pages, start, 1, end, PAGECACHE_TAG_TOWRITE); /* We remove all the remained nodes */ - free(radix_tree_delete(&mt_tree, max_slots)); + free(xa_erase(&mt_tree, max_slots)); - BUG_ON(!radix_tree_empty(&mt_tree)); + BUG_ON(!xa_empty(&mt_tree)); printv(1, "regression test 2, done\n"); } -- 2.50.1