LXR linux/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
  29void 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}
  96