Greg Kroah-Hartman | b244131 | 2017-11-01 15:07:57 +0100 | [diff] [blame] | 1 | // SPDX-License-Identifier: GPL-2.0 |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 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 | * |
Matthew Wilcox | 148deab | 2016-12-14 15:08:49 -0800 | [diff] [blame] | 9 | * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1, |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 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 | * |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 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); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 32 | void *ptr0 = (void *)4ul; |
| 33 | void *ptr = (void *)8ul; |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 34 | struct radix_tree_iter iter; |
| 35 | void **slot; |
| 36 | bool first; |
| 37 | |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 38 | printv(1, "running regression test 3 (should take milliseconds)\n"); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 39 | |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 40 | radix_tree_insert(&root, 0, ptr0); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 41 | radix_tree_tag_set(&root, 0, 0); |
| 42 | |
| 43 | first = true; |
| 44 | radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 45 | printv(2, "tagged %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 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)) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 52 | printv(2, "retry at %ld\n", iter.index); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 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) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 61 | printv(2, "slot %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 62 | if (first) { |
| 63 | radix_tree_insert(&root, 1, ptr); |
| 64 | first = false; |
| 65 | } |
| 66 | if (radix_tree_deref_retry(*slot)) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 67 | printv(2, "retry at %ld\n", iter.index); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 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) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 76 | printv(2, "contig %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 77 | if (first) { |
| 78 | radix_tree_insert(&root, 1, ptr); |
| 79 | first = false; |
| 80 | } |
| 81 | if (radix_tree_deref_retry(*slot)) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 82 | printv(2, "retry at %ld\n", iter.index); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 83 | slot = radix_tree_iter_retry(&iter); |
| 84 | continue; |
| 85 | } |
| 86 | } |
| 87 | |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 88 | radix_tree_for_each_slot(slot, &root, &iter, 0) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 89 | printv(2, "slot %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 90 | if (!iter.index) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 91 | printv(2, "next at %ld\n", iter.index); |
Matthew Wilcox | 148deab | 2016-12-14 15:08:49 -0800 | [diff] [blame] | 92 | slot = radix_tree_iter_resume(slot, &iter); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 93 | } |
| 94 | } |
| 95 | |
| 96 | radix_tree_for_each_contig(slot, &root, &iter, 0) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 97 | printv(2, "contig %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 98 | if (!iter.index) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 99 | printv(2, "next at %ld\n", iter.index); |
Matthew Wilcox | 148deab | 2016-12-14 15:08:49 -0800 | [diff] [blame] | 100 | slot = radix_tree_iter_resume(slot, &iter); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 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) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 107 | printv(2, "tagged %ld %p\n", iter.index, *slot); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 108 | if (!iter.index) { |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 109 | printv(2, "next at %ld\n", iter.index); |
Matthew Wilcox | 148deab | 2016-12-14 15:08:49 -0800 | [diff] [blame] | 110 | slot = radix_tree_iter_resume(slot, &iter); |
Konstantin Khlebnikov | 7475851 | 2016-03-17 14:22:11 -0700 | [diff] [blame] | 111 | } |
| 112 | } |
| 113 | |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 114 | radix_tree_delete(&root, 0); |
| 115 | radix_tree_delete(&root, 1); |
| 116 | |
Rehas Sachdeva | 73bc029 | 2017-01-04 11:55:00 -0500 | [diff] [blame] | 117 | printv(1, "regression test 3 passed\n"); |
Konstantin Khlebnikov | 2d6f45b | 2016-03-17 14:22:08 -0700 | [diff] [blame] | 118 | } |