tools/testing/radix-tree/regression2.c

   1 /*
   2  * Regression2
   3  * Description:
   4  * Toshiyuki Okajima describes the following radix-tree bug:
   5  *
   6  * In the following case, we can get a hangup on
   7  *   radix_radix_tree_gang_lookup_tag_slot.
   8  *
   9  * 0.  The radix tree contains RADIX_TREE_MAP_SIZE items. And the tag of
  10  *     a certain item has PAGECACHE_TAG_DIRTY.
  11  * 1.  radix_tree_range_tag_if_tagged(, start, end, , PAGECACHE_TAG_DIRTY,
  12  *     PAGECACHE_TAG_TOWRITE) is called to add PAGECACHE_TAG_TOWRITE tag
  13  *     for the tag which has PAGECACHE_TAG_DIRTY. However, there is no tag with
  14  *     PAGECACHE_TAG_DIRTY within the range from start to end. As the result,
  15  *     There is no tag with PAGECACHE_TAG_TOWRITE but the root tag has
  16  *     PAGECACHE_TAG_TOWRITE.
  17  * 2.  An item is added into the radix tree and then the level of it is
  18  *     extended into 2 from 1. At that time, the new radix tree node succeeds
  19  *     the tag status of the root tag. Therefore the tag of the new radix tree
  20  *     node has PAGECACHE_TAG_TOWRITE but there is not slot with
  21  *     PAGECACHE_TAG_TOWRITE tag in the child node of the new radix tree node.
  22  * 3.  The tag of a certain item is cleared with PAGECACHE_TAG_DIRTY.
  23  * 4.  All items within the index range from 0 to RADIX_TREE_MAP_SIZE - 1 are
  24  *     released. (Only the item which index is RADIX_TREE_MAP_SIZE exist in the
  25  *     radix tree.) As the result, the slot of the radix tree node is NULL but
  26  *     the tag which corresponds to the slot has PAGECACHE_TAG_TOWRITE.
  27  * 5.  radix_tree_gang_lookup_tag_slot(PAGECACHE_TAG_TOWRITE) calls
  28  *     __lookup_tag. __lookup_tag returns with 0. And __lookup_tag doesn't
  29  *     change the index that is the input and output parameter. Because the 1st
  30  *     slot of the radix tree node is NULL, but the tag which corresponds to
  31  *     the slot has PAGECACHE_TAG_TOWRITE.
  32  *     Therefore radix_tree_gang_lookup_tag_slot tries to get some items by
  33  *     calling __lookup_tag, but it cannot get any items forever.
  34  *
  35  * The fix is to change that radix_tree_tag_if_tagged doesn't tag the root tag
  36  * if it doesn't set any tags within the specified range.
  37  *
  38  * Running:
  39  * This test should run to completion immediately. The above bug would cause it
  40  * to hang indefinitely.
  41  *
  42  * Upstream commit:
  43  * Not yet
  44  */
  45 #include <linux/kernel.h>
  46 #include <linux/gfp.h>
  47 #include <linux/slab.h>
  48 #include <linux/radix-tree.h>
  49 #include <stdlib.h>
  50 #include <stdio.h>
  51
  52 #include "regression.h"
  53
  54 #ifdef __KERNEL__
  55 #define RADIX_TREE_MAP_SHIFT    (CONFIG_BASE_SMALL ? 4 : 6)
  56 #else
  57 #define RADIX_TREE_MAP_SHIFT    3       /* For more stressful testing */
  58 #endif
  59
  60 #define RADIX_TREE_MAP_SIZE     (1UL << RADIX_TREE_MAP_SHIFT)
  61 #define PAGECACHE_TAG_DIRTY     0
  62 #define PAGECACHE_TAG_WRITEBACK 1
  63 #define PAGECACHE_TAG_TOWRITE   2
  64
  65 static RADIX_TREE(mt_tree, GFP_KERNEL);
  66 unsigned long page_count = 0;
  67
  68 struct page {
  69         unsigned long index;
  70 };
  71
  72 static struct page *page_alloc(void)
  73 {
  74         struct page *p;
  75         p = malloc(sizeof(struct page));
  76         p->index = page_count++;
  77
  78         return p;
  79 }
  80
  81 void regression2_test(void)
  82 {
  83         int i;
  84         struct page *p;
  85         int max_slots = RADIX_TREE_MAP_SIZE;
  86         unsigned long int start, end;
  87         struct page *pages[1];
  88
  89         printf("running regression test 2 (should take milliseconds)\n");
  90         /* 0. */
  91         for (i = 0; i <= max_slots - 1; i++) {
  92                 p = page_alloc();
  93                 radix_tree_insert(&mt_tree, i, p);
  94         }
  95         radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
  96
  97         /* 1. */
  98         start = 0;
  99         end = max_slots - 2;
 100         radix_tree_range_tag_if_tagged(&mt_tree, &start, end, 1,
 101                                 PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
 102
 103         /* 2. */
 104         p = page_alloc();
 105         radix_tree_insert(&mt_tree, max_slots, p);
 106
 107         /* 3. */
 108         radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
 109
 110         /* 4. */
 111         for (i = max_slots - 1; i >= 0; i--)
 112                 radix_tree_delete(&mt_tree, i);
 113
 114         /* 5. */
 115         // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
 116         //       can return.
 117         start = 1;
 118         end = max_slots - 2;
 119         radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
 120                 PAGECACHE_TAG_TOWRITE);
 121
 122         /* We remove all the remained nodes */
 123         radix_tree_delete(&mt_tree, max_slots);
 124
 125         printf("regression test 2, done\n");
 126 }