libc/fuzzing/__support/hashtable_fuzz.cpp

   1 //===-- hashtable_fuzz.cpp ------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8 ///
   9 /// Fuzzing test for llvm-libc hashtable implementations.
  10 ///
  11 //===----------------------------------------------------------------------===//
  12 #include "include/llvm-libc-types/ENTRY.h"
  13 #include "src/__support/CPP/bit.h"
  14 #include "src/__support/CPP/string_view.h"
  15 #include "src/__support/HashTable/table.h"
  16 #include "src/__support/macros/config.h"
  17
  18 namespace LIBC_NAMESPACE_DECL {
  19
  20 // A fuzzing payload starts with
  21 // - uint16_t: initial capacity for table A
  22 // - uint64_t: seed for table A
  23 // - uint16_t: initial capacity for table B
  24 // - uint64_t: seed for table B
  25 // Followed by a sequence of actions:
  26 // - CrossCheck: only a single byte valued (4 mod 5)
  27 // - Find: a single byte valued (3 mod 5) followed by a null-terminated string
  28 // - Insert: a single byte valued (0,1,2 mod 5) followed by a null-terminated
  29 // string
  30 static constexpr size_t INITIAL_HEADER_SIZE =
  31     2 * (sizeof(uint16_t) + sizeof(uint64_t));
  32 extern "C" size_t LLVMFuzzerMutate(uint8_t *data, size_t size, size_t max_size);
  33 extern "C" size_t LLVMFuzzerCustomMutator(uint8_t *data, size_t size,
  34                                           size_t max_size, unsigned int seed) {
  35   size = LLVMFuzzerMutate(data, size, max_size);
  36   // not enough to read the initial capacities and seeds
  37   if (size < INITIAL_HEADER_SIZE)
  38     return 0;
  39
  40   // skip the initial capacities and seeds
  41   size_t i = INITIAL_HEADER_SIZE;
  42   while (i < size) {
  43     // cross check
  44     if (static_cast<uint8_t>(data[i]) % 5 == 4) {
  45       // skip the cross check byte
  46       ++i;
  47       continue;
  48     }
  49
  50     // find or insert
  51     // check if there is enough space for the action byte and the
  52     // null-terminator
  53     if (i + 2 >= max_size)
  54       return i;
  55     // skip the action byte
  56     ++i;
  57     // skip the null-terminated string
  58     while (i < max_size && data[i] != 0)
  59       ++i;
  60     // in the case the string is not null-terminated, null-terminate it
  61     if (i == max_size && data[i - 1] != 0) {
  62       data[i - 1] = 0;
  63       return max_size;
  64     }
  65
  66     // move to the next action
  67     ++i;
  68   }
  69   // return the new size
  70   return i;
  71 }
  72
  73 // a tagged union
  74 struct Action {
  75   enum class Tag { Find, Insert, CrossCheck } tag;
  76   cpp::string_view key;
  77 };
  78
  79 static struct {
  80   size_t remaining;
  81   const char *buffer;
  82
  83   template <typename T> T next() {
  84     static_assert(cpp::is_integral<T>::value, "T must be an integral type");
  85
  86     char data[sizeof(T)];
  87
  88     for (size_t i = 0; i < sizeof(T); i++)
  89       data[i] = buffer[i];
  90     buffer += sizeof(T);
  91     remaining -= sizeof(T);
  92     return cpp::bit_cast<T>(data);
  93   }
  94
  95   cpp::string_view next_string() {
  96     cpp::string_view result(buffer);
  97     buffer = result.end() + 1;
  98     remaining -= result.size() + 1;
  99     return result;
 100   }
 101
 102   Action next_action() {
 103     uint8_t byte = next<uint8_t>();
 104     switch (byte % 5) {
 105     case 4:
 106       return {Action::Tag::CrossCheck, {}};
 107     case 3:
 108       return {Action::Tag::Find, next_string()};
 109     default:
 110       return {Action::Tag::Insert, next_string()};
 111     }
 112   }
 113 } global_status;
 114
 115 class HashTable {
 116   internal::HashTable *table;
 117
 118 public:
 119   HashTable(uint64_t size, uint64_t seed)
 120       : table(internal::HashTable::allocate(size, seed)) {}
 121   HashTable(internal::HashTable *table) : table(table) {}
 122   ~HashTable() { internal::HashTable::deallocate(table); }
 123   HashTable(HashTable &&other) : table(other.table) { other.table = nullptr; }
 124   bool is_valid() const { return table != nullptr; }
 125   ENTRY *find(const char *key) { return table->find(key); }
 126   ENTRY *insert(const ENTRY &entry) {
 127     return internal::HashTable::insert(this->table, entry);
 128   }
 129   using iterator = internal::HashTable::iterator;
 130   iterator begin() const { return table->begin(); }
 131   iterator end() const { return table->end(); }
 132 };
 133
 134 HashTable next_hashtable() {
 135   size_t size = global_status.next<uint16_t>();
 136   uint64_t seed = global_status.next<uint64_t>();
 137   return HashTable(size, seed);
 138 }
 139
 140 extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
 141   global_status.buffer = reinterpret_cast<const char *>(data);
 142   global_status.remaining = size;
 143   if (global_status.remaining < INITIAL_HEADER_SIZE)
 144     return 0;
 145
 146   HashTable table_a = next_hashtable();
 147   HashTable table_b = next_hashtable();
 148   for (;;) {
 149     if (global_status.remaining == 0)
 150       break;
 151     Action action = global_status.next_action();
 152     switch (action.tag) {
 153     case Action::Tag::Find: {
 154       if (static_cast<bool>(table_a.find(action.key.data())) !=
 155           static_cast<bool>(table_b.find(action.key.data())))
 156         __builtin_trap();
 157       break;
 158     }
 159     case Action::Tag::Insert: {
 160       char *ptr = const_cast<char *>(action.key.data());
 161       ENTRY *a = table_a.insert(ENTRY{ptr, ptr});
 162       ENTRY *b = table_b.insert(ENTRY{ptr, ptr});
 163       if (a->data != b->data)
 164         __builtin_trap();
 165       break;
 166     }
 167     case Action::Tag::CrossCheck: {
 168       for (ENTRY a : table_a)
 169         if (const ENTRY *b = table_b.find(a.key); a.data != b->data)
 170           __builtin_trap();
 171
 172       for (ENTRY b : table_b)
 173         if (const ENTRY *a = table_a.find(b.key); a->data != b.data)
 174           __builtin_trap();
 175
 176       break;
 177     }
 178     }
 179   }
 180   return 0;
 181 }
 182
 183 } // namespace LIBC_NAMESPACE_DECL