184 lines · 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-exception6//7//===----------------------------------------------------------------------===//8///9/// Fuzzing test for llvm-libc hashtable implementations.10///11//===----------------------------------------------------------------------===//12#include "hdr/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 18namespace LIBC_NAMESPACE_DECL {19 20// A fuzzing payload starts with21// - uint16_t: initial capacity for table A22// - uint64_t: seed for table A23// - uint16_t: initial capacity for table B24// - uint64_t: seed for table B25// 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 string28// - Insert: a single byte valued (0,1,2 mod 5) followed by a null-terminated29// string30static constexpr size_t INITIAL_HEADER_SIZE =31 2 * (sizeof(uint16_t) + sizeof(uint64_t));32extern "C" size_t LLVMFuzzerMutate(uint8_t *data, size_t size, size_t max_size);33extern "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 seeds37 if (size < INITIAL_HEADER_SIZE)38 return 0;39 40 // skip the initial capacities and seeds41 size_t i = INITIAL_HEADER_SIZE;42 while (i < size) {43 // cross check44 if (static_cast<uint8_t>(data[i]) % 5 == 4) {45 // skip the cross check byte46 ++i;47 continue;48 }49 50 // find or insert51 // check if there is enough space for the action byte and the52 // null-terminator53 if (i + 2 >= max_size)54 return i;55 // skip the action byte56 ++i;57 // skip the null-terminated string58 while (i < max_size && data[i] != 0)59 ++i;60 // in the case the string is not null-terminated, null-terminate it61 if (i == max_size && data[i - 1] != 0) {62 data[i - 1] = 0;63 return max_size;64 }65 66 // move to the next action67 ++i;68 }69 // return the new size70 return i;71}72 73// a tagged union74struct Action {75 enum class Tag { Find, Insert, CrossCheck } tag;76 cpp::string_view key;77};78 79static 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 115class HashTable {116 internal::HashTable *table;117 118public: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 134HashTable 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 140extern "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_DECL184