1b2441318SGreg Kroah-Hartman // SPDX-License-Identifier: GPL-2.0
21366c37eSMatthew Wilcox /*
31366c37eSMatthew Wilcox * Regression2
41366c37eSMatthew Wilcox * Description:
51366c37eSMatthew Wilcox * Toshiyuki Okajima describes the following radix-tree bug:
61366c37eSMatthew Wilcox *
71366c37eSMatthew Wilcox * In the following case, we can get a hangup on
81366c37eSMatthew Wilcox * radix_radix_tree_gang_lookup_tag_slot.
91366c37eSMatthew Wilcox *
101366c37eSMatthew Wilcox * 0. The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
111366c37eSMatthew Wilcox * a certain item has PAGECACHE_TAG_DIRTY.
121366c37eSMatthew Wilcox * 1. radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
131366c37eSMatthew Wilcox * PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
141366c37eSMatthew Wilcox * for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
151366c37eSMatthew Wilcox * PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
161366c37eSMatthew Wilcox * There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
171366c37eSMatthew Wilcox * PAGECACHE_TAG_TOWRITE.
181366c37eSMatthew Wilcox * 2. An item is added into the radix tree and then the level of it is
191366c37eSMatthew Wilcox * extended into 2 from 1. At that time, the new radix tree node succeeds
201366c37eSMatthew Wilcox * the tag status of the root tag. Therefore the tag of the new radix tree
211366c37eSMatthew Wilcox * node has PAGECACHE_TAG_TOWRITE but there is not slot with
221366c37eSMatthew Wilcox * PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
231366c37eSMatthew Wilcox * 3. The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
241366c37eSMatthew Wilcox * 4. All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
251366c37eSMatthew Wilcox * released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
261366c37eSMatthew Wilcox * radix tree.) As the result, the slot of the radix tree node is NULL but
271366c37eSMatthew Wilcox * the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
281366c37eSMatthew Wilcox * 5. radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
291366c37eSMatthew Wilcox * __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
301366c37eSMatthew Wilcox * change the index that is the input and output parameter. Because the 1st
311366c37eSMatthew Wilcox * slot of the radix tree node is NULL, but the tag which corresponds to
321366c37eSMatthew Wilcox * the slot has PAGECACHE_TAG_TOWRITE.
331366c37eSMatthew Wilcox * Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
341366c37eSMatthew Wilcox * calling __lookup_tag, but it cannot get any items forever.
351366c37eSMatthew Wilcox *
361366c37eSMatthew Wilcox * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
371366c37eSMatthew Wilcox * if it doesn't set any tags within the specified range.
381366c37eSMatthew Wilcox *
391366c37eSMatthew Wilcox * Running:
401366c37eSMatthew Wilcox * This test should run to completion immediately. The above bug would cause it
411366c37eSMatthew Wilcox * to hang indefinitely.
421366c37eSMatthew Wilcox *
431366c37eSMatthew Wilcox * Upstream commit:
441366c37eSMatthew Wilcox * Not yet
451366c37eSMatthew Wilcox */
461366c37eSMatthew Wilcox #include <linux/kernel.h>
471366c37eSMatthew Wilcox #include <linux/gfp.h>
481366c37eSMatthew Wilcox #include <linux/slab.h>
491366c37eSMatthew Wilcox #include <linux/radix-tree.h>
501366c37eSMatthew Wilcox #include <stdlib.h>
511366c37eSMatthew Wilcox #include <stdio.h>
521366c37eSMatthew Wilcox
531366c37eSMatthew Wilcox #include "regression.h"
54268f42deSMatthew Wilcox #include "test.h"
551366c37eSMatthew Wilcox
56372266baSMatthew Wilcox #define PAGECACHE_TAG_DIRTY XA_MARK_0
57372266baSMatthew Wilcox #define PAGECACHE_TAG_WRITEBACK XA_MARK_1
58372266baSMatthew Wilcox #define PAGECACHE_TAG_TOWRITE XA_MARK_2
591366c37eSMatthew Wilcox
601366c37eSMatthew Wilcox static RADIX_TREE(mt_tree, GFP_KERNEL);
611366c37eSMatthew Wilcox unsigned long page_count = 0;
621366c37eSMatthew Wilcox
631366c37eSMatthew Wilcox struct page {
641366c37eSMatthew Wilcox unsigned long index;
651366c37eSMatthew Wilcox };
661366c37eSMatthew Wilcox
page_alloc(void)671366c37eSMatthew Wilcox static struct page *page_alloc(void)
681366c37eSMatthew Wilcox {
691366c37eSMatthew Wilcox struct page *p;
701366c37eSMatthew Wilcox p = malloc(sizeof(struct page));
711366c37eSMatthew Wilcox p->index = page_count++;
721366c37eSMatthew Wilcox
731366c37eSMatthew Wilcox return p;
741366c37eSMatthew Wilcox }
751366c37eSMatthew Wilcox
regression2_test(void)761366c37eSMatthew Wilcox void regression2_test(void)
771366c37eSMatthew Wilcox {
781366c37eSMatthew Wilcox int i;
791366c37eSMatthew Wilcox struct page *p;
801366c37eSMatthew Wilcox int max_slots = RADIX_TREE_MAP_SIZE;
811366c37eSMatthew Wilcox unsigned long int start, end;
821366c37eSMatthew Wilcox struct page *pages[1];
831366c37eSMatthew Wilcox
8473bc029bSRehas Sachdeva printv(1, "running regression test 2 (should take milliseconds)\n");
851366c37eSMatthew Wilcox /* 0. */
861366c37eSMatthew Wilcox for (i = 0; i <= max_slots - 1; i++) {
871366c37eSMatthew Wilcox p = page_alloc();
881366c37eSMatthew Wilcox radix_tree_insert(&mt_tree, i, p);
891366c37eSMatthew Wilcox }
901366c37eSMatthew Wilcox radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
911366c37eSMatthew Wilcox
921366c37eSMatthew Wilcox /* 1. */
931366c37eSMatthew Wilcox start = 0;
941366c37eSMatthew Wilcox end = max_slots - 2;
95372266baSMatthew Wilcox tag_tagged_items(&mt_tree, start, end, 1,
961366c37eSMatthew Wilcox PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
971366c37eSMatthew Wilcox
981366c37eSMatthew Wilcox /* 2. */
991366c37eSMatthew Wilcox p = page_alloc();
1001366c37eSMatthew Wilcox radix_tree_insert(&mt_tree, max_slots, p);
1011366c37eSMatthew Wilcox
1021366c37eSMatthew Wilcox /* 3. */
1031366c37eSMatthew Wilcox radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
1041366c37eSMatthew Wilcox
1051366c37eSMatthew Wilcox /* 4. */
1061366c37eSMatthew Wilcox for (i = max_slots - 1; i >= 0; i--)
1076da0396cSMatthew Wilcox free(radix_tree_delete(&mt_tree, i));
1081366c37eSMatthew Wilcox
1091366c37eSMatthew Wilcox /* 5. */
1101366c37eSMatthew Wilcox // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
1111366c37eSMatthew Wilcox // can return.
1121366c37eSMatthew Wilcox start = 1;
1131366c37eSMatthew Wilcox end = max_slots - 2;
1141366c37eSMatthew Wilcox radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
1151366c37eSMatthew Wilcox PAGECACHE_TAG_TOWRITE);
1161366c37eSMatthew Wilcox
1171366c37eSMatthew Wilcox /* We remove all the remained nodes */
1186da0396cSMatthew Wilcox free(radix_tree_delete(&mt_tree, max_slots));
1196da0396cSMatthew Wilcox
1206da0396cSMatthew Wilcox BUG_ON(!radix_tree_empty(&mt_tree));
1211366c37eSMatthew Wilcox
12273bc029bSRehas Sachdeva printv(1, "regression test 2, done\n");
1231366c37eSMatthew Wilcox }
124