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
  28 void 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 }