blob: ace2543c3edab3061042e24af19408d6b9ecbcd6 [file] [log] [blame]
Greg Kroah-Hartmanb2441312017-11-01 15:07:57 +01001// SPDX-License-Identifier: GPL-2.0
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -07002/*
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 Wilcox148deab2016-12-14 15:08:49 -08009 * Helper radix_tree_iter_resume reset slot to NULL and next_index to index + 1,
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070010 * 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 Khlebnikov2d6f45b2016-03-17 14:22:08 -070013 * 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);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070032 void *ptr0 = (void *)4ul;
33 void *ptr = (void *)8ul;
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070034 struct radix_tree_iter iter;
35 void **slot;
36 bool first;
37
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050038 printv(1, "running regression test 3 (should take milliseconds)\n");
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070039
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070040 radix_tree_insert(&root, 0, ptr0);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070041 radix_tree_tag_set(&root, 0, 0);
42
43 first = true;
44 radix_tree_for_each_tagged(slot, &root, &iter, 0, 0) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050045 printv(2, "tagged %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070046 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 Sachdeva73bc0292017-01-04 11:55:00 -050052 printv(2, "retry at %ld\n", iter.index);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070053 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 Sachdeva73bc0292017-01-04 11:55:00 -050061 printv(2, "slot %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070062 if (first) {
63 radix_tree_insert(&root, 1, ptr);
64 first = false;
65 }
66 if (radix_tree_deref_retry(*slot)) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050067 printv(2, "retry at %ld\n", iter.index);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070068 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 Sachdeva73bc0292017-01-04 11:55:00 -050076 printv(2, "contig %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070077 if (first) {
78 radix_tree_insert(&root, 1, ptr);
79 first = false;
80 }
81 if (radix_tree_deref_retry(*slot)) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050082 printv(2, "retry at %ld\n", iter.index);
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -070083 slot = radix_tree_iter_retry(&iter);
84 continue;
85 }
86 }
87
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070088 radix_tree_for_each_slot(slot, &root, &iter, 0) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050089 printv(2, "slot %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070090 if (!iter.index) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050091 printv(2, "next at %ld\n", iter.index);
Matthew Wilcox148deab2016-12-14 15:08:49 -080092 slot = radix_tree_iter_resume(slot, &iter);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070093 }
94 }
95
96 radix_tree_for_each_contig(slot, &root, &iter, 0) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050097 printv(2, "contig %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -070098 if (!iter.index) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -050099 printv(2, "next at %ld\n", iter.index);
Matthew Wilcox148deab2016-12-14 15:08:49 -0800100 slot = radix_tree_iter_resume(slot, &iter);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -0700101 }
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 Sachdeva73bc0292017-01-04 11:55:00 -0500107 printv(2, "tagged %ld %p\n", iter.index, *slot);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -0700108 if (!iter.index) {
Rehas Sachdeva73bc0292017-01-04 11:55:00 -0500109 printv(2, "next at %ld\n", iter.index);
Matthew Wilcox148deab2016-12-14 15:08:49 -0800110 slot = radix_tree_iter_resume(slot, &iter);
Konstantin Khlebnikov74758512016-03-17 14:22:11 -0700111 }
112 }
113
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -0700114 radix_tree_delete(&root, 0);
115 radix_tree_delete(&root, 1);
116
Rehas Sachdeva73bc0292017-01-04 11:55:00 -0500117 printv(1, "regression test 3 passed\n");
Konstantin Khlebnikov2d6f45b2016-03-17 14:22:08 -0700118}