testing/radix-tree/regression3.c

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * Regression3
0004  * Description:
0005  * Helper radix_tree_iter_retry resets next_index to the current index.
0006  * In following radix_tree_next_slot current chunk size becomes zero.
0007  * This isn't checked and it tries to dereference null pointer in slot.
0008  *
0009  * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1,
0010  * for tagger iteraction it also must reset cached tags in iterator to abort
0011  * next radix_tree_next_slot and go to slow-path into radix_tree_next_chunk.
0012  *
0013  * Running:
0014  * This test should run to completion immediately. The above bug would
0015  * cause it to segfault.
0016  *
0017  * Upstream commit:
0018  * Not yet
0019  */
0020 #include <linux/kernel.h>
0021 #include <linux/gfp.h>
0022 #include <linux/slab.h>
0023 #include <linux/radix-tree.h>
0024 #include <stdlib.h>
0025 #include <stdio.h>
0026
0027 #include "regression.h"
0028
0029 void regression3_test(void)
0030 {
0031     RADIX_TREE(root, GFP_KERNEL);
0032     void *ptr0 = (void *)4ul;
0033     void *ptr = (void *)8ul;
0034     struct radix_tree_iter iter;
0035     void **slot;
0036     bool first;
0037
0038     printv(1, "running regression test 3 (should take milliseconds)\n");
0039
0040     radix_tree_insert(&root, 0, ptr0);
0041     radix_tree_tag_set(&root, 0, 0);
0042
0043     first = true;
0044     radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
0045         printv(2, "tagged %ld %p\n", iter.index, *slot);
0046         if (first) {
0047             radix_tree_insert(&root, 1, ptr);
0048             radix_tree_tag_set(&root, 1, 0);
0049             first = false;
0050         }
0051         if (radix_tree_deref_retry(*slot)) {
0052             printv(2, "retry at %ld\n", iter.index);
0053             slot = radix_tree_iter_retry(&iter);
0054             continue;
0055         }
0056     }
0057     radix_tree_delete(&root, 1);
0058
0059     first = true;
0060     radix_tree_for_each_slot(slot, &root, &iter, 0) {
0061         printv(2, "slot %ld %p\n", iter.index, *slot);
0062         if (first) {
0063             radix_tree_insert(&root, 1, ptr);
0064             first = false;
0065         }
0066         if (radix_tree_deref_retry(*slot)) {
0067             printv(2, "retry at %ld\n", iter.index);
0068             slot = radix_tree_iter_retry(&iter);
0069             continue;
0070         }
0071     }
0072
0073     radix_tree_for_each_slot(slot, &root, &iter, 0) {
0074         printv(2, "slot %ld %p\n", iter.index, *slot);
0075         if (!iter.index) {
0076             printv(2, "next at %ld\n", iter.index);
0077             slot = radix_tree_iter_resume(slot, &iter);
0078         }
0079     }
0080
0081     radix_tree_tag_set(&root, 0, 0);
0082     radix_tree_tag_set(&root, 1, 0);
0083     radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
0084         printv(2, "tagged %ld %p\n", iter.index, *slot);
0085         if (!iter.index) {
0086             printv(2, "next at %ld\n", iter.index);
0087             slot = radix_tree_iter_resume(slot, &iter);
0088         }
0089     }
0090
0091     radix_tree_delete(&root, 0);
0092     radix_tree_delete(&root, 1);
0093
0094     printv(1, "regression test 3 passed\n");
0095 }