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
  73         radix_tree_for_each_slot(slot, &root, &iter, 0) {
  74                 printv(2, "slot %ld %p\n", iter.index, *slot);
  75                 if (!iter.index) {
  76                         printv(2, "next at %ld\n", iter.index);
  77                         slot = radix_tree_iter_resume(slot, &iter);
  78                 }
  79         }
  80
  81         radix_tree_tag_set(&root, 0, 0);
  82         radix_tree_tag_set(&root, 1, 0);
  83         radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
  84                 printv(2, "tagged %ld %p\n", iter.index, *slot);
  85                 if (!iter.index) {
  86                         printv(2, "next at %ld\n", iter.index);
  87                         slot = radix_tree_iter_resume(slot, &iter);
  88                 }
  89         }
  90
  91         radix_tree_delete(&root, 0);
  92         radix_tree_delete(&root, 1);
  93
  94         printv(1, "regression test 3 passed\n");
  95 }