tools/testing/radix-tree/regression3.c

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