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