LXR linux/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#define PAGECACHE_TAG_DIRTY     0
  55#define PAGECACHE_TAG_WRITEBACK 1
  56#define PAGECACHE_TAG_TOWRITE   2
  57
  58static RADIX_TREE(mt_tree, GFP_KERNEL);
  59unsigned long page_count = 0;
  60
  61struct page {
  62        unsigned long index;
  63};
  64
  65static struct page *page_alloc(void)
  66{
  67        struct page *p;
  68        p = malloc(sizeof(struct page));
  69        p->index = page_count++;
  70
  71        return p;
  72}
  73
  74void regression2_test(void)
  75{
  76        int i;
  77        struct page *p;
  78        int max_slots = RADIX_TREE_MAP_SIZE;
  79        unsigned long int start, end;
  80        struct page *pages[1];
  81
  82        printf("running regression test 2 (should take milliseconds)\n");
  83        /* 0. */
  84        for (i = 0; i <= max_slots - 1; i++) {
  85                p = page_alloc();
  86                radix_tree_insert(&mt_tree, i, p);
  87        }
  88        radix_tree_tag_set(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
  89
  90        /* 1. */
  91        start = 0;
  92        end = max_slots - 2;
  93        radix_tree_range_tag_if_tagged(&mt_tree, &start, end, 1,
  94                                PAGECACHE_TAG_DIRTY, PAGECACHE_TAG_TOWRITE);
  95
  96        /* 2. */
  97        p = page_alloc();
  98        radix_tree_insert(&mt_tree, max_slots, p);
  99
 100        /* 3. */
 101        radix_tree_tag_clear(&mt_tree, max_slots - 1, PAGECACHE_TAG_DIRTY);
 102
 103        /* 4. */
 104        for (i = max_slots - 1; i >= 0; i--)
 105                radix_tree_delete(&mt_tree, i);
 106
 107        /* 5. */
 108        // NOTE: start should not be 0 because radix_tree_gang_lookup_tag_slot
 109        //       can return.
 110        start = 1;
 111        end = max_slots - 2;
 112        radix_tree_gang_lookup_tag_slot(&mt_tree, (void ***)pages, start, end,
 113                PAGECACHE_TAG_TOWRITE);
 114
 115        /* We remove all the remained nodes */
 116        radix_tree_delete(&mt_tree, max_slots);
 117
 118        printf("regression test 2, done\n");
 119}
 120