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  
 13  namespace {
 14  
 15  /** The maximum number of simultaneous buffers kept by the test. */
 16  static constexpr size_t MAX_BUFFERS{3};
 17  /** How many elements are kept in a buffer at most. */
 18  static constexpr size_t MAX_BUFFER_SIZE{48};
 19  /** How many operations are performed at most on the buffers in one test. */
 20  static 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   */
 26  template<typename T, bool CheckNoneLeft>
 27  void 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 {
251                      assert(real[idx].capacity() > old_cap);
252                      assert(real[idx].capacity() <= 2 * (old_cap + 1));
253                  }
254                  break;
255              }
256              if (existing_buffer_non_full && command-- == 0) {
257                  /* emplace_front() */
258                  uint64_t seed{rng.rand64()};
259                  size_t old_size = real[idx].size();
260                  size_t old_cap = real[idx].capacity();
261                  sim[idx].emplace_front(seed);
262                  real[idx].emplace_front(seed);
263                  assert(real[idx].size() == old_size + 1);
264                  if (old_cap > old_size) {
265                      assert(real[idx].capacity() == old_cap);
266                  } else {
267                      assert(real[idx].capacity() > old_cap);
268                      assert(real[idx].capacity() <= 2 * (old_cap + 1));
269                  }
270                  break;
271              }
272              if (existing_buffer_non_empty && command-- == 0) {
273                  /* front() [modifying] */
274                  tmp = T(rng.rand64());
275                  size_t old_size = real[idx].size();
276                  assert(sim[idx].front() == real[idx].front());
277                  sim[idx].front() = *tmp;
278                  real[idx].front() = std::move(*tmp);
279                  assert(real[idx].size() == old_size);
280                  break;
281              }
282              if (existing_buffer_non_empty && command-- == 0) {
283                  /* back() [modifying] */
284                  tmp = T(rng.rand64());
285                  size_t old_size = real[idx].size();
286                  assert(sim[idx].back() == real[idx].back());
287                  sim[idx].back() = *tmp;
288                  real[idx].back() = *tmp;
289                  assert(real[idx].size() == old_size);
290                  break;
291              }
292              if (existing_buffer_non_empty && command-- == 0) {
293                  /* operator[] [modifying] */
294                  tmp = T(rng.rand64());
295                  size_t pos = provider.ConsumeIntegralInRange<size_t>(0, sim[idx].size() - 1);
296                  size_t old_size = real[idx].size();
297                  assert(sim[idx][pos] == real[idx][pos]);
298                  sim[idx][pos] = *tmp;
299                  real[idx][pos] = std::move(*tmp);
300                  assert(real[idx].size() == old_size);
301                  break;
302              }
303              if (existing_buffer_non_empty && command-- == 0) {
304                  /* pop_front() */
305                  assert(sim[idx].front() == real[idx].front());
306                  size_t old_size = real[idx].size();
307                  sim[idx].pop_front();
308                  real[idx].pop_front();
309                  assert(real[idx].size() == old_size - 1);
310                  break;
311              }
312              if (existing_buffer_non_empty && command-- == 0) {
313                  /* pop_back() */
314                  assert(sim[idx].back() == real[idx].back());
315                  size_t old_size = real[idx].size();
316                  sim[idx].pop_back();
317                  real[idx].pop_back();
318                  assert(real[idx].size() == old_size - 1);
319                  break;
320              }
321          }
322      }
323  
324      /* Fully compare the final state. */
325      for (unsigned i = 0; i < sim.size(); ++i) {
326          // Make sure const getters work.
327          const VecDeque<T>& realbuf = real[i];
328          const std::deque<T>& simbuf = sim[i];
329          compare_fn(realbuf, simbuf);
330          for (unsigned j = 0; j < sim.size(); ++j) {
331              assert((realbuf == real[j]) == (simbuf == sim[j]));
332              assert(((realbuf <=> real[j]) >= 0) == (simbuf >= sim[j]));
333              assert(((realbuf <=> real[j]) <= 0) == (simbuf <= sim[j]));
334          }
335          // Clear out the buffers so we can check below that no objects exist anymore.
336          sim[i].clear();
337          real[i].clear();
338      }
339  
340      if constexpr (CheckNoneLeft) {
341          tmp = std::nullopt;
342          T::CheckNoneExist();
343      }
344  }
345  
346  /** Data structure with built-in tracking of all existing objects. */
347  template<size_t Size>
348  class TrackedObj
349  {
350      static_assert(Size > 0);
351  
352      /* Data type for map that actually stores the object data.
353       *
354       * The key is a pointer to the TrackedObj, the value is the uint64_t it was initialized with.
355       * Default-constructed and moved-from objects hold an std::nullopt.
356       */
357      using track_map_type = std::map<const TrackedObj<Size>*, std::optional<uint64_t>>;
358  
359  private:
360  
361      /** Actual map. */
362      static inline track_map_type g_tracker;
363  
364      /** Iterators into the tracker map for this object.
365       *
366       * This is an array of size Size, all holding the same value, to give the object configurable
367       * size. The value is g_tracker.end() if this object is not fully initialized. */
368      typename track_map_type::iterator m_track_entry[Size];
369  
370      void Check() const
371      {
372          auto it = g_tracker.find(this);
373          for (size_t i = 0; i < Size; ++i) {
374              assert(m_track_entry[i] == it);
375          }
376      }
377  
378      /** Create entry for this object in g_tracker and populate m_track_entry. */
379      void Register()
380      {
381          auto [it, inserted] = g_tracker.emplace(this, std::nullopt);
382          assert(inserted);
383          for (size_t i = 0; i < Size; ++i) {
384              m_track_entry[i] = it;
385          }
386      }
387  
388      void Deregister()
389      {
390          Check();
391          assert(m_track_entry[0] != g_tracker.end());
392          g_tracker.erase(m_track_entry[0]);
393          for (size_t i = 0; i < Size; ++i) {
394              m_track_entry[i] = g_tracker.end();
395          }
396      }
397  
398      /** Get value corresponding to this object in g_tracker. */
399      std::optional<uint64_t>& Deref()
400      {
401          Check();
402          assert(m_track_entry[0] != g_tracker.end());
403          return m_track_entry[0]->second;
404      }
405  
406      /** Get value corresponding to this object in g_tracker. */
407      const std::optional<uint64_t>& Deref() const
408      {
409          Check();
410          assert(m_track_entry[0] != g_tracker.end());
411          return m_track_entry[0]->second;
412      }
413  
414  public:
415      ~TrackedObj() { Deregister(); }
416      TrackedObj() { Register(); }
417  
418      TrackedObj(uint64_t value)
419      {
420          Register();
421          Deref() = value;
422      }
423  
424      TrackedObj(const TrackedObj& other)
425      {
426          Register();
427          Deref() = other.Deref();
428      }
429  
430      TrackedObj(TrackedObj&& other)
431      {
432          Register();
433          Deref() = other.Deref();
434          other.Deref() = std::nullopt;
435      }
436  
437      TrackedObj& operator=(const TrackedObj& other)
438      {
439          if (this == &other) return *this;
440          Deref() = other.Deref();
441          return *this;
442      }
443  
444      TrackedObj& operator=(TrackedObj&& other)
445      {
446          if (this == &other) return *this;
447          Deref() = other.Deref();
448          other.Deref() = std::nullopt;
449          return *this;
450      }
451  
452      friend bool operator==(const TrackedObj& a, const TrackedObj& b)
453      {
454          return a.Deref() == b.Deref();
455      }
456  
457      friend std::strong_ordering operator<=>(const TrackedObj& a, const TrackedObj& b)
458      {
459          // Libc++ 15 & 16 do not support std::optional<T>::operator<=> yet. See
460          // https://reviews.llvm.org/D146392.
461          if (!a.Deref().has_value() || !b.Deref().has_value()) {
462              return a.Deref().has_value() <=> b.Deref().has_value();
463          }
464          return *a.Deref() <=> *b.Deref();
465      }
466  
467      static void CheckNoneExist()
468      {
469          assert(g_tracker.empty());
470      }
471  };
472  
473  } // namespace
474  
475  FUZZ_TARGET(vecdeque)
476  {
477      // Run the test with simple uints (which satisfy all the trivial properties).
478      static_assert(std::is_trivially_copyable_v<uint32_t>);
479      static_assert(std::is_trivially_destructible_v<uint64_t>);
480      TestType<uint8_t, false>(buffer, 1);
481      TestType<uint16_t, false>(buffer, 2);
482      TestType<uint32_t, false>(buffer, 3);
483      TestType<uint64_t, false>(buffer, 4);
484  
485      // Run the test with TrackedObjs (which do not).
486      static_assert(!std::is_trivially_copyable_v<TrackedObj<3>>);
487      static_assert(!std::is_trivially_destructible_v<TrackedObj<17>>);
488      TestType<TrackedObj<1>, true>(buffer, 5);
489      TestType<TrackedObj<3>, true>(buffer, 6);
490      TestType<TrackedObj<17>, true>(buffer, 7);
491  }