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
23namespace {
24
25template <std::size_t VarCount = 2, unsigned Bits = 2>
26int 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
140TEST_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
178TEST_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