-
Notifications
You must be signed in to change notification settings - Fork 2
/
test_art_fuzz_deepstate.cpp
211 lines (191 loc) · 7.96 KB
/
test_art_fuzz_deepstate.cpp
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
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
// Copyright 2019-2021 Laurynas Biveinis
#include "global.hpp" // IWYU pragma: keep
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <limits>
#include <new>
#include <sstream>
#include <unordered_map>
#include <utility>
#include <vector>
#include <deepstate/DeepState.hpp>
#include <gsl/gsl_util>
#include "art.hpp"
#include "art_common.hpp"
#include "deepstate_utils.hpp"
namespace {
constexpr auto maximum_value_len = 1024 * 1024; // 1MB
// Close to the longest test run that fits into 8192 random bytes provided by
// DeepState API.
constexpr auto test_length = 480;
using dynamic_value = std::vector<std::byte>;
using values_type = std::vector<dynamic_value>;
auto make_random_value(dynamic_value::size_type length) {
dynamic_value result{length};
for (dynamic_value::size_type i = 0; i < length; i++) {
// Ideally we would take random bytes from DeepState, but we'd end up
// exhausting their default source len too soon. Do something deterministic
// that has embedded zero bytes to shake out any C string API use
result[i] = gsl::narrow_cast<std::byte>(i % 256);
}
return result;
}
auto get_value(dynamic_value::size_type max_length, values_type &values) {
const auto make_new_value = values.empty() || DeepState_Bool();
ASSERT(max_length <= std::numeric_limits<std::uint32_t>::max());
if (make_new_value) {
const dynamic_value::size_type new_value_len =
DeepState_SizeTInRange(0, max_length);
auto new_value = make_random_value(new_value_len);
LOG(TRACE) << "Making a new value of length " << new_value_len;
const auto &inserted_value = values.emplace_back(std::move(new_value));
return unodb::value_view{inserted_value};
}
LOG(TRACE) << "Reusing an existing value";
ASSERT(values.size() <= std::numeric_limits<std::uint32_t>::max());
const auto existing_value_i = DeepState_ContainerIndex(values);
const auto &existing_value = values[existing_value_i];
return unodb::value_view{existing_value};
}
unodb::key get_key(unodb::key max_key_value,
const std::vector<unodb::key> &keys) {
const auto use_existing_key = !keys.empty() && DeepState_Bool();
if (use_existing_key) {
ASSERT(!keys.empty());
ASSERT(keys.size() <= std::numeric_limits<std::uint32_t>::max());
const auto existing_key_i = DeepState_ContainerIndex(keys);
return keys[existing_key_i];
}
return DeepState_UInt64InRange(0, max_key_value);
}
void dump_tree(const unodb::db &tree) {
// Dump the tree to a string. Do not attempt to check the dump format, only
// that dumping does not crash
std::stringstream dump_sink;
tree.dump(dump_sink);
}
} // namespace
UNODB_START_DEEPSTATE_TESTS()
TEST(ART, DeepStateFuzz) {
const auto limit_max_key = DeepState_Bool();
const auto max_key_value =
limit_max_key
? DeepState_UInt64InRange(0, std::numeric_limits<unodb::key>::max())
: std::numeric_limits<unodb::key>::max();
if (limit_max_key)
LOG(TRACE) << "Limiting maximum key value to " << max_key_value;
else
LOG(TRACE) << "Not limiting maximum key value (" << max_key_value << ")";
static_assert(maximum_value_len <= std::numeric_limits<std::uint32_t>::max());
const auto limit_value_length = DeepState_Bool();
const auto max_value_length =
limit_value_length ? DeepState_UIntInRange(0, maximum_value_len)
: maximum_value_len;
if (limit_value_length)
LOG(TRACE) << "Limiting maximum value length to " << max_value_length;
else
LOG(TRACE) << "Not limiting value length (" << max_value_length << ")";
unodb::db test_db;
ASSERT(test_db.empty());
std::vector<unodb::key> keys;
values_type values;
std::unordered_map<unodb::key, unodb::value_view> oracle;
for (auto i = 0; i < test_length; i++) {
LOG(TRACE) << "Iteration " << i;
deepstate::OneOf(
// Insert
[&] {
const auto key = DeepState_UInt64InRange(0, max_key_value);
const auto value = get_value(max_value_length, values);
const auto mem_use_before = test_db.get_current_memory_use();
try {
const auto insert_result = test_db.insert(key, value);
const auto mem_use_after = test_db.get_current_memory_use();
if (insert_result) {
LOG(TRACE) << "Inserted key " << key;
ASSERT(!test_db.empty());
ASSERT(mem_use_after > mem_use_before);
const auto oracle_insert_result = oracle.emplace(key, value);
ASSERT(oracle_insert_result.second)
<< "If insert suceeded, oracle insert must succeed";
keys.emplace_back(key);
} else {
LOG(TRACE) << "Tried to insert duplicate key " << key;
ASSERT(mem_use_after == mem_use_before);
ASSERT(oracle.find(key) != oracle.cend())
<< "If insert returned failure, oracle must contain that key";
}
} catch (const std::bad_alloc &) {
const auto mem_use_after = test_db.get_current_memory_use();
ASSERT(mem_use_after == mem_use_before);
}
dump_tree(test_db);
LOG(TRACE) << "Current mem use: " << test_db.get_current_memory_use();
},
// Query
[&] {
const auto key = get_key(max_key_value, keys);
LOG(TRACE) << "Searching for key " << key;
const auto search_result = test_db.get(key);
const auto oracle_search_result = oracle.find(key);
if (search_result) {
ASSERT(!test_db.empty());
ASSERT(oracle_search_result != oracle.cend())
<< "If search found a key, oracle must contain that key";
ASSERT(std::equal(search_result->cbegin(), search_result->cend(),
oracle_search_result->second.cbegin(),
oracle_search_result->second.cend()))
<< "Values stored in ART and in oracle must match";
} else {
ASSERT(oracle_search_result == oracle.cend())
<< "If search did not find a key, oracle must not find it too ";
}
},
// Delete
[&] {
// Delete everything with 0.1% probability
const auto clear = (DeepState_UIntInRange(0, 999) == 0);
if (clear) {
LOG(TRACE) << "Clearing the tree";
test_db.clear();
oracle.clear();
ASSERT(test_db.get_current_memory_use() == 0);
ASSERT(test_db.empty());
return;
}
const auto key = get_key(max_key_value, keys);
LOG(TRACE) << "Deleting key " << key;
const auto mem_use_before = test_db.get_current_memory_use();
const auto delete_result = test_db.remove(key);
const auto mem_use_after = test_db.get_current_memory_use();
const auto oracle_delete_result = oracle.erase(key);
if (delete_result) {
ASSERT(mem_use_after < mem_use_before);
ASSERT(oracle_delete_result == 1)
<< "If delete succeeded, oracle delete must succeed too";
} else {
ASSERT(mem_use_after == mem_use_before);
ASSERT(oracle_delete_result == 0)
<< "If delete failed, oracle delete must fail too";
}
dump_tree(test_db);
LOG(TRACE) << "Current mem use: " << test_db.get_current_memory_use();
});
}
auto prev_mem_use = test_db.get_current_memory_use();
while (!oracle.empty()) {
const auto [key, value] = *oracle.cbegin();
LOG(TRACE) << "Shutdown: deleting key " << key;
const auto oracle_remove_result = oracle.erase(key);
ASSERT(oracle_remove_result == 1);
const auto db_remove_result = test_db.remove(key);
ASSERT(db_remove_result);
const auto current_mem_use = test_db.get_current_memory_use();
LOG(TRACE) << "Current mem use: " << current_mem_use;
ASSERT(current_mem_use < prev_mem_use);
prev_mem_use = current_mem_use;
}
ASSERT(prev_mem_use == 0);
ASSERT(test_db.empty());
}