testing/radix-tree/regression2.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Regression2
0004  * Description:
0005  * Toshiyuki Okajima describes the following radix-tree bug:
0006  *
0007  * In the following case, we can get a hangup on
0008  *   radix_radix_tree_gang_lookup_tag_slot.
0009  *
0010  * 0.  The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
0011  *     a certain item has PAGECACHE_TAG_DIRTY.
0012  * 1.  radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
0013  *     PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
0014  *     for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
0015  *     PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
0016  *     There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
0017  *     PAGECACHE_TAG_TOWRITE.
0018  * 2.  An item is added into the radix tree and then the level of it is
0019  *     extended into 2 from 1. At that time, the new radix tree node succeeds
0020  *     the tag status of the root tag. Therefore the tag of the new radix tree
0021  *     node has PAGECACHE_TAG_TOWRITE but there is not slot with
0022  *     PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
0023  * 3.  The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
0024  * 4.  All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
0025  *     released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
0026  *     radix tree.) As the result, the slot of the radix tree node is NULL but
0027  *     the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
0028  * 5.  radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
0029  *     __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
0030  *     change the index that is the input and output parameter. Because the 1st
0031  *     slot of the radix tree node is NULL, but the tag which corresponds to
0032  *     the slot has PAGECACHE_TAG_TOWRITE.
0033  *     Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
0034  *     calling __lookup_tag, but it cannot get any items forever.
0035  *
0036  * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
0037  * if it doesn't set any tags within the specified range.
0038  *
0039  * Running:
0040  * This test should run to completion immediately. The above bug would cause it
0041  * to hang indefinitely.
0042  *
0043  * Upstream commit:
0044  * Not yet
0045  */
0046 #include <linux/kernel.h>
0047 #include <linux/gfp.h>
0048 #include <linux/slab.h>
0049 #include <linux/radix-tree.h>
0050 #include <stdlib.h>
0051 #include <stdio.h>
0052
0053 #include "regression.h"
0054 #include "test.h"
0055
0056 #define PAGECACHE_TAG_DIRTY     XA_MARK_0
0057 #define PAGECACHE_TAG_WRITEBACK XA_MARK_1
0058 #define PAGECACHE_TAG_TOWRITE   XA_MARK_2
0059
0060 static RADIX_TREE(mt_tree, GFP_KERNEL);
0061 unsigned long page_count = 0;
0062
0063 struct page {
0064     unsigned long index;
0065 };
0066
0067 static struct page *page_alloc(void)
0068 {
0069     struct page *p;
0070     p = malloc(sizeof(struct page));
0071     p->index = page_count++;
0072
0073     return p;
0074 }
0075
0076 void regression2_test(void)
0077 {
0078     int i;
0079     struct page *p;
0080     int max_slots = RADIX_TREE_MAP_SIZE;
0081     unsigned long int start, end;
0082     struct page *pages[1];
0083
0084     printv(1, "running regression test 2 (should take milliseconds)\n");
0085     /* 0. */
0086     for (i = 0; i <= max_slots - 1; i++) {
0087         p = page_alloc();
0088         radix_tree_insert(&mt_tree, i, p);
0089     }
0090     radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
0091
0092     /* 1. */
0093     start = 0;
0094     end = max_slots - 2;
0095     tag_tagged_items(&mt_tree, start, end, 1,
0096                 PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
0097
0098     /* 2. */
0099     p = page_alloc();
0100     radix_tree_insert(&mt_tree, max_slots, p);
0101
0102     /* 3. */
0103     radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
0104
0105     /* 4. */
0106     for (i = max_slots - 1; i >= 0; i--)
0107         free(radix_tree_delete(&mt_tree, i));
0108
0109     /* 5. */
0110     // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
0111     //       can return.
0112     start = 1;
0113     end = max_slots - 2;
0114     radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
0115         PAGECACHE_TAG_TOWRITE);
0116
0117     /* We remove all the remained nodes */
0118     free(radix_tree_delete(&mt_tree, max_slots));
0119
0120     BUG_ON(!radix_tree_empty(&mt_tree));
0121
0122     printv(1, "regression test 2, done\n");
0123 }