1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
|
//===-- weak_avl_fuzz.cpp -------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
///
/// Fuzzing test for llvm-libc weak AVL implementations.
///
//===----------------------------------------------------------------------===//
#include "hdr/types/ENTRY.h"
#include "src/__support/CPP/bit.h"
#include "src/__support/CPP/optional.h"
#include "src/__support/macros/config.h"
#include "src/__support/weak_avl.h"
namespace LIBC_NAMESPACE_DECL {
// A sequence of actions:
// - Erase: a single byte valued (5, 6 mod 7) followed by an int
// - Find: a single byte valued (4 mod 7) followed by an int
// - FindOrInsert: a single byte valued (0,1,2,3 mod 7) followed by an int
extern "C" size_t LLVMFuzzerMutate(uint8_t *data, size_t size, size_t max_size);
extern "C" size_t LLVMFuzzerCustomMutator(uint8_t *data, size_t size,
size_t max_size, unsigned int seed) {
size = LLVMFuzzerMutate(data, size, max_size);
return size / (1 + sizeof(int)) * (1 + sizeof(int));
}
class AVLTree {
using Node = WeakAVLNode<int>;
Node *root = nullptr;
bool reversed = false;
static int compare(int a, int b) { return (a > b) - (a < b); }
static int reverse_compare(int a, int b) { return (b > a) - (b < a); }
public:
AVLTree(bool reversed = false) : reversed(reversed) {}
bool find(int key) {
return Node::find(root, key, reversed ? reverse_compare : compare)
.has_value();
}
bool find_or_insert(int key) {
return Node::find_or_insert(root, key, reversed ? reverse_compare : compare)
.has_value();
}
bool erase(int key) {
if (cpp::optional<Node *> node =
Node::find(root, key, reversed ? reverse_compare : compare)) {
Node::erase(root, node.value());
return true;
}
return false;
}
~AVLTree() { Node::destroy(root); }
};
extern "C" int LLVMFuzzerTestOneInput(const uint8_t *data, size_t size) {
AVLTree tree1;
AVLTree tree2(true);
for (size_t i = 0; i + (1 + sizeof(int)) <= size; i += 1 + sizeof(int)) {
uint8_t action = data[i];
int key;
__builtin_memcpy(&key, data + i + 1, sizeof(int));
if (action % 7 == 4) {
// Find
bool res1 = tree1.find(key);
bool res2 = tree2.find(key);
if (res1 != res2)
__builtin_trap();
} else if (action % 7 == 5 || action % 7 == 6) {
// Erase
bool res1 = tree1.erase(key);
bool res2 = tree2.erase(key);
if (res1 != res2)
__builtin_trap();
if (tree1.find(key))
__builtin_trap();
if (tree2.find(key))
__builtin_trap();
} else {
// FindOrInsert
bool res1 = tree1.find_or_insert(key);
bool res2 = tree2.find_or_insert(key);
if (res1 != res2)
__builtin_trap();
if (!tree1.find(key))
__builtin_trap();
if (!tree2.find(key))
__builtin_trap();
}
}
return 0;
}
} // namespace LIBC_NAMESPACE_DECL
|
