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 } 119