1 | // |
---|---|
2 | // immer: immutable data structures for C++ |
3 | // Copyright (C) 2016, 2017, 2018 Juan Pedro Bolivar Puente |
4 | // |
5 | // This software is distributed under the Boost Software License, Version 1.0. |
6 | // See accompanying file LICENSE or copy at http://boost.org/LICENSE_1_0.txt |
7 | // |
8 | |
9 | #include "extra/fuzzer/fuzzer_input.hpp" |
10 | #include <immer/flex_vector.hpp> |
11 | #include <array> |
12 | #include <iostream> |
13 | #include <catch.hpp> |
14 | |
15 | #define IMMER_FUZZED_TRACE_ENABLE 0 |
16 | |
17 | #if IMMER_FUZZED_TRACE_ENABLE |
18 | #define IMMER_FUZZED_TRACE(...) std::cout << __VA_ARGS__ << std::endl; |
19 | #else |
20 | #define IMMER_FUZZED_TRACE(...) |
21 | #endif |
22 | |
23 | namespace { |
24 | |
25 | template <std::size_t VarCount = 2, unsigned Bits = 2> |
26 | int run_input(const std::uint8_t* data, std::size_t size) |
27 | { |
28 | using vector_t = immer::flex_vector<int, immer::default_memory_policy, Bits, Bits>; |
29 | using size_t = std::uint8_t; |
30 | |
31 | auto vars = std::array<vector_t, VarCount>{}; |
32 | |
33 | #if IMMER_FUZZED_TRACE_ENABLE |
34 | std::cout << "/// new test run"<< std::endl; |
35 | for (auto i = 0u; i < VarCount; ++i) |
36 | std::cout << "auto var"<< i << " = vector_t{};"<< std::endl; |
37 | #endif |
38 | |
39 | auto is_valid_var = [&] (auto idx) { |
40 | return idx >= 0 && idx < VarCount; |
41 | }; |
42 | auto is_valid_index = [] (auto& v) { |
43 | return [&] (auto idx) { return idx >= 0 && idx < v.size(); }; |
44 | }; |
45 | auto is_valid_size = [] (auto& v) { |
46 | return [&] (auto idx) { return idx >= 0 && idx <= v.size(); }; |
47 | }; |
48 | auto can_concat = [] (auto&& v1, auto&& v2) { |
49 | using size_type = decltype(v1.size()); |
50 | return v2.size() < (std::numeric_limits<size_type>::max() - v1.size()); |
51 | }; |
52 | auto can_insert = [] (auto&& v1) { |
53 | using size_type = decltype(v1.size()); |
54 | return v1.size() < std::numeric_limits<size_type>::max(); |
55 | }; |
56 | |
57 | return fuzzer_input{data, size}.run([&] (auto& in) |
58 | { |
59 | enum ops { |
60 | op_push_back, |
61 | op_update, |
62 | op_take, |
63 | op_drop, |
64 | op_concat, |
65 | op_push_back_move, |
66 | op_update_move, |
67 | }; |
68 | auto src = read<std::uint8_t>(in, is_valid_var); |
69 | auto dst = read<std::uint8_t>(in, is_valid_var); |
70 | switch (read<char>(in)) |
71 | { |
72 | case op_push_back: |
73 | if (can_insert(vars[src])) { |
74 | IMMER_FUZZED_TRACE( |
75 | "var"<< +dst << " = var"<< +src << |
76 | ".push_back(42);"); |
77 | vars[dst] = vars[src].push_back(42); |
78 | } |
79 | break; |
80 | case op_update: { |
81 | auto idx = read<size_t>(in, is_valid_index(vars[src])); |
82 | IMMER_FUZZED_TRACE( |
83 | "var"<< +dst << " = var"<< +src << |
84 | ".update("<< +idx << ", [] (auto x) { return x + 1; });"); |
85 | vars[dst] = vars[src].update(idx, [] (auto x) { return x + 1; }); |
86 | break; |
87 | } |
88 | case op_take: { |
89 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
90 | IMMER_FUZZED_TRACE( |
91 | "var"<< +dst << " = var"<< +src << |
92 | ".take("<< +idx << ");"); |
93 | vars[dst] = vars[src].take(idx); |
94 | break; |
95 | } |
96 | case op_drop: { |
97 | auto idx = read<size_t>(in, is_valid_size(vars[src])); |
98 | IMMER_FUZZED_TRACE( |
99 | "var"<< +dst << " = var"<< +src << |
100 | ".take("<< +idx << ");"); |
101 | vars[dst] = vars[src].drop(idx); |
102 | break; |
103 | } |
104 | case op_concat: { |
105 | auto src2 = read<std::uint8_t>(in, is_valid_var); |
106 | if (can_concat(vars[src], vars[src2])) { |
107 | IMMER_FUZZED_TRACE( |
108 | "var"<< +dst << " = var"<< +src << " + var"<< +src2 << ";"); |
109 | vars[dst] = vars[src] + vars[src2]; |
110 | } |
111 | break; |
112 | } |
113 | case op_push_back_move: { |
114 | if (can_insert(vars[src])) { |
115 | IMMER_FUZZED_TRACE( |
116 | "var"<< +dst << " = std::move(var"<< +src << |
117 | ").push_back(21);"); |
118 | vars[dst] = std::move(vars[src]).push_back(21); |
119 | } |
120 | break; |
121 | } |
122 | case op_update_move: { |
123 | auto idx = read<size_t>(in, is_valid_index(vars[src])); |
124 | IMMER_FUZZED_TRACE( |
125 | "var"<< +dst << " = std::move(var"<< +src << |
126 | ").update("<< +idx << ", [] (auto x) { return x + 1; });"); |
127 | vars[dst] = std::move(vars[src]) |
128 | .update(idx, [] (auto x) { return x + 1; }); |
129 | break; |
130 | } |
131 | default: |
132 | break; |
133 | }; |
134 | return true; |
135 | }); |
136 | } |
137 | |
138 | } // anonymous namespace |
139 | |
140 | TEST_CASE("bug: memory leak because of move update") |
141 | { |
142 | // There was a problem caused with shared "sizes buffer" in |
143 | // relaxed nodes. In particular, the ensure_mutable_relaxed(...) |
144 | // function was not decremeting the old sizes buffer. That is why |
145 | // the last transient push_back (which uses mutable operations) |
146 | // causes some of the relaxed buffers that are created during the |
147 | // previous concatenations, and that start to be shared from the |
148 | // update() onwards, to later be leaked. |
149 | SECTION("simplified") |
150 | { |
151 | using vector_t = immer::flex_vector<int, immer::default_memory_policy, 2, 2>; |
152 | auto var0 = vector_t{}; |
153 | auto var1 = vector_t{}; |
154 | var0 = var0.push_back(42); |
155 | var0 = var0.push_back(42); |
156 | var0 = var0.push_back(42); |
157 | var0 = var0 + var0; |
158 | var1 = var0.push_back(42); |
159 | var0 = var0 + var1; |
160 | var1 = var0.push_back(42); |
161 | var0 = var0 + var0; |
162 | var0 = var1 + var0; |
163 | var0 = var1.update(5, [] (auto x) { return x + 1; }); |
164 | var0 = std::move(var0).push_back(21); |
165 | } |
166 | |
167 | #if __GNUC__ != 9 |
168 | SECTION("") |
169 | { |
170 | constexpr std::uint8_t input[] = { |
171 | 0xff,0x0,0xff,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x0,0x40,0x0,0x0,0x4,0x0,0x6d,0x6d,0x0,0x1,0x0,0x4,0x6d,0x6d,0x6d,0x0,0x0,0x4,0x1,0x6d,0x6d,0x0,0x1,0x0,0x0,0x0,0x4,0x28,0x0,0xfc,0x1,0x0,0x4,0x0,0x0,0x0,0xfc,0x1,0x0,0x1,0x5,0x0,0x0,0x1,0x5,0x0,0x0,0x5,0x0,0x0,0xff,0xff,0xff,0x27, |
172 | }; |
173 | CHECK(run_input(input, sizeof(input)) == 0); |
174 | } |
175 | #endif |
176 | } |
177 | |
178 | TEST_CASE("non-bug: crash") |
179 | { |
180 | // This is an interesting finding that is left here for |
181 | // documentation. This test actually should not run... the |
182 | // problem is that when we build too large vectors via |
183 | // concatenation, we can sometimes "overflow the shift". This is |
184 | // a degenerate case that we won't fix, but this helped adding |
185 | // appropriate assertions to the code. |
186 | // |
187 | // To prevent this in further fuzzing, the can_concat check has |
188 | // been made stricter. |
189 | return; |
190 | |
191 | SECTION("simplified") |
192 | { |
193 | using vector_t = immer::flex_vector<int, immer::default_memory_policy, 2, 2>; |
194 | auto var4 = vector_t{}; |
195 | var4 = var4.push_back(42); |
196 | var4 = var4.push_back(42); |
197 | var4 = var4.push_back(42); |
198 | var4 = var4.push_back(42); |
199 | var4 = var4.push_back(42); |
200 | auto var0 = var4; |
201 | var4 = var4 + var4; |
202 | var4 = var4 + var4; |
203 | var4 = var4 + var4; |
204 | var4 = var4 + var4; |
205 | var4 = var4 + var4; |
206 | var4 = var4 + var4; |
207 | var4 = var4 + var4; |
208 | var4 = var4 + var4; |
209 | var4 = var4 + var4; |
210 | var4 = var4 + var4; |
211 | var4 = var4 + var4; |
212 | var4 = var4 + var4; |
213 | var4 = var4 + var4; |
214 | var4 = var4 + var4; |
215 | var4 = var4 + var4; |
216 | var4 = var4 + var4; |
217 | var4 = var4 + var4; |
218 | var4 = var4 + var4; |
219 | var4 = var4 + var4; |
220 | var4 = var4 + var4; |
221 | var4 = var4 + var4; |
222 | var4 = var4 + var4; |
223 | var4 = var4 + var4; |
224 | var4 = var4 + var4; |
225 | var4 = var4 + var4; |
226 | var4 = var4 + var4; |
227 | var4 = var4 + var4; |
228 | var4 = var4 + var4; |
229 | var4 = var4 + var4; |
230 | var4 = var4 + var4; |
231 | var4 = var4 + var4; |
232 | var4 = var4 + var4; |
233 | var4 = var4 + var4; |
234 | var4 = var4 + var4; |
235 | var4 = var4 + var4; |
236 | var4 = var0 + var4; |
237 | var4 = var4 + var4; |
238 | var4 = var4 + var4; |
239 | var4 = var4 + var4; |
240 | var4 = var4 + var4; |
241 | var4 = var4 + var4; |
242 | var4 = var4 + var4; |
243 | var4 = var4 + var4; |
244 | var4 = var4 + var4; |
245 | var4 = var4 + var4; |
246 | var4 = var4 + var4; |
247 | var4 = var4 + var4; |
248 | var4 = var4 + var4; |
249 | var4 = var4 + var4; |
250 | var4 = var4 + var4; |
251 | var4 = var4 + var4; |
252 | var4 = var4 + var4; |
253 | var4 = var4 + var4; |
254 | var4 = var4 + var4; |
255 | var4 = var4 + var4; |
256 | var4 = var4 + var4; |
257 | var4 = var4 + var4; |
258 | var4 = var4 + var4; |
259 | var4 = var4 + var4; |
260 | var4 = var4 + var4; |
261 | var4 = var4 + var4; |
262 | var4 = var4 + var4; |
263 | var4 = var4.update(4, [] (auto x) { return x + 1; }); |
264 | } |
265 | #if __GNUC__ != 9 |
266 | SECTION("") |
267 | { |
268 | constexpr std::uint8_t input[] = { |
269 | 0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x2a,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0xfc,0xf9,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0xd5,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x01,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x01,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x3a,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x21,0x04,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x00,0x04,0x04,0x00,0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x00,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x13,0x13,0x13,0x13,0x13,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x29,0x00,0x00,0x00,0x00,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x03,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x21,0x00,0x10,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x3a,0x00,0x02,0x00,0x00,0x00,0x04,0x00,0x00,0x04,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x01,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x01,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x05,0x04,0x04,0x04,0x04,0x04,0x04,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x3a,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x21,0x04,0x00,0x00,0x00,0x00,0x00,0x00,0x04,0x01,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x23,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0xff,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x04,0x00, |
270 | }; |
271 | CHECK(run_input<8>(input, sizeof(input)) == 0); |
272 | } |
273 | #endif |
274 | } |
275 |