Inside Bitcoin

1// Copyright (c) The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <random.h>
6#include <span.h>
7#include <test/fuzz/util.h>
8#include <util/vecdeque.h>
9
10#include <cstdint>
11#include <deque>
12
13namespace {
14
15/** The maximum number of simultaneous buffers kept by the test. */
16static constexpr size_t MAX_BUFFERS{3};
17/** How many elements are kept in a buffer at most. */
18static constexpr size_t MAX_BUFFER_SIZE{48};
19/** How many operations are performed at most on the buffers in one test. */
20static constexpr size_t MAX_OPERATIONS{1024};
21
22/** Perform a simulation fuzz test on VecDeque type T.
23 *
24 * T must be constructible from a uint64_t seed, comparable to other T, copyable, and movable.
25 */
26template<typename T, bool CheckNoneLeft>
27void TestType(std::span<const uint8_t> buffer, uint64_t rng_tweak)
28{
29    FuzzedDataProvider provider(buffer.data(), buffer.size());
30    // Local RNG, only used for the seeds to initialize T objects with.
31    InsecureRandomContext rng(provider.ConsumeIntegral<uint64_t>() ^ rng_tweak);
32
33    // Real circular buffers.
34    std::vector<VecDeque<T>> real;
35    real.reserve(MAX_BUFFERS);
36    // Simulated circular buffers.
37    std::vector<std::deque<T>> sim;
38    sim.reserve(MAX_BUFFERS);
39    // Temporary object of type T.
40    std::optional<T> tmp;
41
42    // Compare a real and a simulated buffer.
43    auto compare_fn = [](const VecDeque<T>& r, const std::deque<T>& s) {
44        assert(r.size() == s.size());
45        assert(r.empty() == s.empty());
46        assert(r.capacity() >= r.size());
47        if (s.size() == 0) return;
48        assert(r.front() == s.front());
49        assert(r.back() == s.back());
50        for (size_t i = 0; i < s.size(); ++i) {
51            assert(r[i] == s[i]);
52        }
53    };
54
55    LIMITED_WHILE (provider.remaining_bytes(), MAX_OPERATIONS) {
56        int command = provider.ConsumeIntegral<uint8_t>() % 64;
57        unsigned idx = real.empty() ? 0 : provider.ConsumeIntegralInRange<unsigned>(0, real.size() - 1);
58        const size_t num_buffers = sim.size();
59        // Pick one operation based on value of command. Not all operations are always applicable.
60        // Loop through the applicable ones until command reaches 0 (which avoids the need to
61        // compute the number of applicable commands ahead of time).
62        const bool non_empty{num_buffers != 0};
63        const bool non_full{num_buffers < MAX_BUFFERS};
64        const bool partially_full{non_empty && non_full};
65        const bool multiple_exist{num_buffers > 1};
66        const bool existing_buffer_non_full{non_empty && sim[idx].size() < MAX_BUFFER_SIZE};
67        const bool existing_buffer_non_empty{non_empty && !sim[idx].empty()};
68        assert(non_full || non_empty);
69        while (true) {
70            if (non_full && command-- == 0) {
71                /* Default construct. */
72                real.emplace_back();
73                sim.emplace_back();
74                break;
75            }
76            if (non_empty && command-- == 0) {
77                /* resize() */
78                compare_fn(real[idx], sim[idx]);
79                size_t new_size = provider.ConsumeIntegralInRange<size_t>(0, MAX_BUFFER_SIZE);
80                real[idx].resize(new_size);
81                sim[idx].resize(new_size);
82                assert(real[idx].size() == new_size);
83                break;
84            }
85            if (non_empty && command-- == 0) {
86                /* clear() */
87                compare_fn(real[idx], sim[idx]);
88                real[idx].clear();
89                sim[idx].clear();
90                assert(real[idx].empty());
91                break;
92            }
93            if (non_empty && command-- == 0) {
94                /* Copy construct default. */
95                compare_fn(real[idx], sim[idx]);
96                real[idx] = VecDeque<T>();
97                sim[idx].clear();
98                assert(real[idx].size() == 0);
99                break;
100            }
101            if (non_empty && command-- == 0) {
102                /* Destruct. */
103                compare_fn(real.back(), sim.back());
104                real.pop_back();
105                sim.pop_back();
106                break;
107            }
108            if (partially_full && command-- == 0) {
109                /* Copy construct. */
110                real.emplace_back(real[idx]);
111                sim.emplace_back(sim[idx]);
112                break;
113            }
114            if (partially_full && command-- == 0) {
115                /* Move construct. */
116                VecDeque<T> copy(real[idx]);
117                real.emplace_back(std::move(copy));
118                sim.emplace_back(sim[idx]);
119                break;
120            }
121            if (multiple_exist && command-- == 0) {
122                /* swap() */
123                swap(real[idx], real[(idx + 1) % num_buffers]);
124                swap(sim[idx], sim[(idx + 1) % num_buffers]);
125                break;
126            }
127            if (multiple_exist && command-- == 0) {
128                /* Copy assign. */
129                compare_fn(real[idx], sim[idx]);
130                real[idx] = real[(idx + 1) % num_buffers];
131                sim[idx] = sim[(idx + 1) % num_buffers];
132                break;
133            }
134            if (multiple_exist && command-- == 0) {
135                /* Move assign. */
136                VecDeque<T> copy(real[(idx + 1) % num_buffers]);
137                compare_fn(real[idx], sim[idx]);
138                real[idx] = std::move(copy);
139                sim[idx] = sim[(idx + 1) % num_buffers];
140                break;
141            }
142            if (non_empty && command-- == 0) {
143                /* Self swap() */
144                swap(real[idx], real[idx]);
145                break;
146            }
147            if (non_empty && command-- == 0) {
148                /* Self-copy assign. */
149                real[idx] = real[idx];
150                break;
151            }
152            if (non_empty && command-- == 0) {
153                /* Self-move assign. */
154                // Do not use std::move(real[idx]) here: -Wself-move correctly warns about that.
155                real[idx] = static_cast<VecDeque<T>&&>(real[idx]);
156                break;
157            }
158            if (non_empty && command-- == 0) {
159                /* reserve() */
160                size_t res_size = provider.ConsumeIntegralInRange<size_t>(0, MAX_BUFFER_SIZE);
161                size_t old_cap = real[idx].capacity();
162                size_t old_size = real[idx].size();
163                real[idx].reserve(res_size);
164                assert(real[idx].size() == old_size);
165                assert(real[idx].capacity() == std::max(old_cap, res_size));
166                break;
167            }
168            if (non_empty && command-- == 0) {
169                /* shrink_to_fit() */
170                size_t old_size = real[idx].size();
171                real[idx].shrink_to_fit();
172                assert(real[idx].size() == old_size);
173                assert(real[idx].capacity() == old_size);
174                break;
175            }
176            if (existing_buffer_non_full && command-- == 0) {
177                /* push_back() (copying) */
178                tmp = T(rng.rand64());
179                size_t old_size = real[idx].size();
180                size_t old_cap = real[idx].capacity();
181                real[idx].push_back(*tmp);
182                sim[idx].push_back(*tmp);
183                assert(real[idx].size() == old_size + 1);
184                if (old_cap > old_size) {
185                    assert(real[idx].capacity() == old_cap);
186                } else {
187                    assert(real[idx].capacity() > old_cap);
188                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
189                }
190                break;
191            }
192            if (existing_buffer_non_full && command-- == 0) {
193                /* push_back() (moving) */
194                tmp = T(rng.rand64());
195                size_t old_size = real[idx].size();
196                size_t old_cap = real[idx].capacity();
197                sim[idx].push_back(*tmp);
198                real[idx].push_back(std::move(*tmp));
199                assert(real[idx].size() == old_size + 1);
200                if (old_cap > old_size) {
201                    assert(real[idx].capacity() == old_cap);
202                } else {
203                    assert(real[idx].capacity() > old_cap);
204                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
205                }
206                break;
207            }
208            if (existing_buffer_non_full && command-- == 0) {
209                /* emplace_back() */
210                uint64_t seed{rng.rand64()};
211                size_t old_size = real[idx].size();
212                size_t old_cap = real[idx].capacity();
213                sim[idx].emplace_back(seed);
214                real[idx].emplace_back(seed);
215                assert(real[idx].size() == old_size + 1);
216                if (old_cap > old_size) {
217                    assert(real[idx].capacity() == old_cap);
218                } else {
219                    assert(real[idx].capacity() > old_cap);
220                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
221                }
222                break;
223            }
224            if (existing_buffer_non_full && command-- == 0) {
225                /* push_front() (copying) */
226                tmp = T(rng.rand64());
227                size_t old_size = real[idx].size();
228                size_t old_cap = real[idx].capacity();
229                real[idx].push_front(*tmp);
230                sim[idx].push_front(*tmp);
231                assert(real[idx].size() == old_size + 1);
232                if (old_cap > old_size) {
233                    assert(real[idx].capacity() == old_cap);
234                } else {
235                    assert(real[idx].capacity() > old_cap);
236                    assert(real[idx].capacity() <= 2 * (old_cap + 1));
237                }
238                break;
239            }
240            if (existing_buffer_non_full && command-- == 0) {
241                /* push_front() (moving) */
242                tmp = T(rng.rand64());
243                size_t old_size = real[idx].size();
244                size_t old_cap = real[idx].capacity();
245                sim[idx].push_front(*tmp);
246                real[idx].push_front(std::move(*tmp));
247                assert(real[idx].size() == old_size + 1);
248                if (old_cap > old_size) {
249                    assert(real[idx].capacity() == old_cap);
250                } else {