LXR linux/tools/testing/radix-tree/regression3.c

   1/*
   2 * Regression3
   3 * Description:
   4 * Helper radix_tree_iter_retry resets next_index to the current index.
   5 * In following radix_tree_next_slot current chunk size becomes zero.
   6 * This isn't checked and it tries to dereference null pointer in slot.
   7 *
   8 * Helper radix_tree_iter_next reset slot to NULL and next_index to index + 1,
   9 * for tagger iteraction it also must reset cached tags in iterator to abort
  10 * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk.
  11 *
  12 * Running:
  13 * This test should run to completion immediately. The above bug would
  14 * cause it to segfault.
  15 *
  16 * Upstream commit:
  17 * Not yet
  18 */
  19#include <linux/kernel.h>
  20#include <linux/gfp.h>
  21#include <linux/slab.h>
  22#include <linux/radix-tree.h>
  23#include <stdlib.h>
  24#include <stdio.h>
  25
  26#include "regression.h"
  27
  28void regression3_test(void)
  29{
  30        RADIX_TREE(root, GFP_KERNEL);
  31        void *ptr0 = (void *)4ul;
  32        void *ptr = (void *)8ul;
  33        struct radix_tree_iter iter;
  34        void **slot;
  35        bool first;
  36
  37        printf("running regression test 3 (should take milliseconds)\n");
  38
  39        radix_tree_insert(&root, 0, ptr0);
  40        radix_tree_tag_set(&root, 0, 0);
  41
  42        first = true;
  43        radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
  44                printf("tagged %ld %p\n", iter.index, *slot);
  45                if (first) {
  46                        radix_tree_insert(&root, 1, ptr);
  47                        radix_tree_tag_set(&root, 1, 0);
  48                        first = false;
  49                }
  50                if (radix_tree_deref_retry(*slot)) {
  51                        printf("retry at %ld\n", iter.index);
  52                        slot = radix_tree_iter_retry(&iter);
  53                        continue;
  54                }
  55        }
  56        radix_tree_delete(&root, 1);
  57
  58        first = true;
  59        radix_tree_for_each_slot(slot, &root, &iter, 0) {
  60                printf("slot %ld %p\n", iter.index, *slot);
  61                if (first) {
  62                        radix_tree_insert(&root, 1, ptr);
  63                        first = false;
  64                }
  65                if (radix_tree_deref_retry(*slot)) {
  66                        printk("retry at %ld\n", iter.index);
  67                        slot = radix_tree_iter_retry(&iter);
  68                        continue;
  69                }
  70        }
  71        radix_tree_delete(&root, 1);
  72
  73        first = true;
  74        radix_tree_for_each_contig(slot, &root, &iter, 0) {
  75                printk("contig %ld %p\n", iter.index, *slot);
  76                if (first) {
  77                        radix_tree_insert(&root, 1, ptr);
  78                        first = false;
  79                }
  80                if (radix_tree_deref_retry(*slot)) {
  81                        printk("retry at %ld\n", iter.index);
  82                        slot = radix_tree_iter_retry(&iter);
  83                        continue;
  84                }
  85        }
  86
  87        radix_tree_for_each_slot(slot, &root, &iter, 0) {
  88                printf("slot %ld %p\n", iter.index, *slot);
  89                if (!iter.index) {
  90                        printf("next at %ld\n", iter.index);
  91                        slot = radix_tree_iter_next(&iter);
  92                }
  93        }
  94
  95        radix_tree_for_each_contig(slot, &root, &iter, 0) {
  96                printf("contig %ld %p\n", iter.index, *slot);
  97                if (!iter.index) {
  98                        printf("next at %ld\n", iter.index);
  99                        slot = radix_tree_iter_next(&iter);
 100                }
 101        }
 102
 103        radix_tree_tag_set(&root, 0, 0);
 104        radix_tree_tag_set(&root, 1, 0);
 105        radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
 106                printf("tagged %ld %p\n", iter.index, *slot);
 107                if (!iter.index) {
 108                        printf("next at %ld\n", iter.index);
 109                        slot = radix_tree_iter_next(&iter);
 110                }
 111        }
 112
 113        radix_tree_delete(&root, 0);
 114        radix_tree_delete(&root, 1);
 115
 116        printf("regression test 3 passed\n");
 117}
 118