1 // Copyright 2020 The Pigweed Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
4 // use this file except in compliance with the License. You may obtain a copy of
5 // the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
12 // License for the specific language governing permissions and limitations under
13 // the License.
14
15 #include <cstdlib>
16 #include <random>
17 #include <set>
18 #include <span>
19 #include <string>
20 #include <string_view>
21 #include <unordered_map>
22 #include <unordered_set>
23
24 #define DUMP_KVS_CONTENTS 0
25
26 #if DUMP_KVS_CONTENTS
27 #include <iostream>
28 #endif // DUMP_KVS_CONTENTS
29
30 #include "gtest/gtest.h"
31 #include "pw_kvs/crc16_checksum.h"
32 #include "pw_kvs/fake_flash_memory.h"
33 #include "pw_kvs/flash_partition_with_stats.h"
34 #include "pw_kvs/internal/entry.h"
35 #include "pw_kvs/key_value_store.h"
36 #include "pw_log/log.h"
37
38 namespace pw::kvs {
39 namespace {
40
41 using std::byte;
42
43 constexpr size_t kMaxEntries = 256;
44 constexpr size_t kMaxUsableSectors = 256;
45
46 constexpr std::string_view kChars =
47 "abcdefghijklmnopqrstuvwxyz"
48 "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
49 "0123456789";
50
51 struct TestParameters {
52 size_t sector_size;
53 size_t sector_count;
54 size_t sector_alignment;
55 size_t redundancy;
56 size_t partition_start_sector;
57 size_t partition_sector_count;
58 size_t partition_alignment;
59 };
60
61 enum Options {
62 kNone,
63 kReinit,
64 kReinitWithFullGC,
65 kReinitWithPartialGC,
66 };
67
68 template <typename T>
difference(const std::set<T> lhs,const std::set<T> rhs)69 std::set<T> difference(const std::set<T> lhs, const std::set<T> rhs) {
70 std::set<T> diff;
71 std::set_difference(lhs.begin(),
72 lhs.end(),
73 rhs.begin(),
74 rhs.end(),
75 std::inserter(diff, diff.begin()));
76
77 return diff;
78 }
79
80 template <const TestParameters& kParams>
81 class KvsTester {
82 public:
KvsTester()83 KvsTester()
84 : partition_(&flash_,
85 kParams.partition_start_sector,
86 kParams.partition_sector_count,
87 kParams.partition_alignment),
88 // For KVS magic value always use a random 32 bit integer rather than a
89 // human readable 4 bytes. See pw_kvs/format.h for more information.
90 kvs_(&partition_, {.magic = 0xc857e51d, .checksum = nullptr}) {
91 EXPECT_EQ(OkStatus(), partition_.Erase());
92 Status result = kvs_.Init();
93 EXPECT_EQ(OkStatus(), result);
94
95 if (!result.ok()) {
96 std::abort();
97 }
98 }
99
~KvsTester()100 ~KvsTester() { CompareContents(); }
101
Test_RandomValidInputs(int iterations,uint_fast32_t seed,Options options)102 void Test_RandomValidInputs(int iterations,
103 uint_fast32_t seed,
104 Options options) {
105 std::mt19937 random(seed);
106 std::uniform_int_distribution<unsigned> distro;
107 auto random_int = [&] { return distro(random); };
108
109 auto random_string = [&](size_t length) {
110 std::string value;
111 for (size_t i = 0; i < length; ++i) {
112 value.push_back(kChars[random_int() % kChars.size()]);
113 }
114 return value;
115 };
116
117 partition_.ResetCounters();
118
119 for (int i = 0; i < iterations; ++i) {
120 if (options != kNone && random_int() % 10 == 0) {
121 Init();
122 }
123
124 // One out of 4 times, delete a key.
125 if (random_int() % 4 == 0) {
126 // Either delete a non-existent key or delete an existing one.
127 if (empty() || random_int() % 8 == 0) {
128 Delete("not_a_key" + std::to_string(random_int()));
129 } else {
130 Delete(RandomPresentKey());
131 }
132 } else {
133 std::string key;
134
135 // Either add a new key or replace an existing one.
136 // TODO: Using %2 (or any less than 16) fails with redundancy due to KVS
137 // filling up and not being able to write the second redundant entry,
138 // returning error. After re-init() the new key is picked up, resulting
139 // in a mis-match between KVS and the test map.
140 if (empty() || random_int() % 16 == 0) {
141 key = random_string(random_int() %
142 (internal::Entry::kMaxKeyLength + 1));
143 } else {
144 key = RandomPresentKey();
145 }
146
147 Put(key, random_string(random_int() % kMaxValueLength));
148 }
149
150 if (options == kReinitWithFullGC && random_int() % 250 == 0) {
151 GCFull();
152 } else if (options == kReinitWithPartialGC && random_int() % 40 == 0) {
153 GCPartial();
154 }
155 }
156
157 // Only save for tests that have enough data to be interesting.
158 if (partition_.sector_count() > 2 && partition_.total_erase_count() > 20) {
159 pw::StringBuffer<64> label;
160 label << "Random";
161 label << partition_.sector_count();
162 label << "Sector";
163 label << iterations;
164 label << ((options != kNone) ? "Reinit" : "");
165 label << ((options == kReinitWithFullGC) ? "FullGC" : "");
166 label << ((options == kReinitWithPartialGC) ? "PartialGC" : "");
167 label << ((kvs_.redundancy() > 1) ? "Redundant" : "");
168
169 partition_.SaveStorageStats(kvs_, label.data());
170 }
171 }
172
Test_Put()173 void Test_Put() {
174 Put("base_key", "base_value");
175 for (int i = 0; i < 100; ++i) {
176 Put("other_key", std::to_string(i));
177 }
178 for (int i = 0; i < 100; ++i) {
179 Put("key_" + std::to_string(i), std::to_string(i));
180 }
181 }
182
Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted()183 void Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted() {
184 for (int i = 0; i < 100; ++i) {
185 std::string str = "key_" + std::to_string(i);
186 Put(str, std::string(kMaxValueLength, '?'));
187 Delete(str);
188 }
189 }
190
191 private:
CompareContents()192 void CompareContents() {
193 #if DUMP_KVS_CONTENTS
194 std::set<std::string> map_keys, kvs_keys;
195
196 std::cout << "/==============================================\\\n";
197 std::cout << "KVS EXPECTED CONTENTS\n";
198 std::cout << "------------------------------------------------\n";
199 std::cout << "Entries: " << map_.size() << '\n';
200 std::cout << "------------------------------------------------\n";
201 for (const auto& [key, value] : map_) {
202 std::cout << key << " = [" << value << "]\n";
203 map_keys.insert(key);
204 }
205 std::cout << "\\===============================================/\n";
206
207 std::cout << "/==============================================\\\n";
208 std::cout << "KVS ACTUAL CONTENTS\n";
209 std::cout << "------------------------------------------------\n";
210 std::cout << "Entries: " << kvs_.size() << '\n';
211 std::cout << "------------------------------------------------\n";
212 for (const auto& item : kvs_) {
213 std::cout << item.key() << " = " << item.ValueSize().size() << " B\n";
214 kvs_keys.insert(std::string(item.key()));
215 }
216 std::cout << "\\===============================================/\n";
217
218 auto missing_from_kvs = difference(map_keys, kvs_keys);
219
220 if (!missing_from_kvs.empty()) {
221 std::cout << "MISSING FROM KVS: " << missing_from_kvs.size() << '\n';
222 for (auto& key : missing_from_kvs) {
223 std::cout << key << '\n';
224 }
225 }
226
227 auto missing_from_map = difference(kvs_keys, map_keys);
228 if (!missing_from_map.empty()) {
229 std::cout << "MISSING FROM MAP: " << missing_from_map.size() << '\n';
230 for (auto& key : missing_from_map) {
231 std::cout << key << '\n';
232 }
233 }
234 #endif // DUMP_KVS_CONTENTS
235
236 EXPECT_EQ(map_.size(), kvs_.size());
237
238 size_t count = 0;
239
240 for (auto& item : kvs_) {
241 count += 1;
242
243 auto map_entry = map_.find(std::string(item.key()));
244 if (map_entry == map_.end()) {
245 PW_LOG_CRITICAL(
246 "Entry %s missing from map%s",
247 item.key(),
248 deleted_.count(item.key()) > 0u ? " [was deleted previously]" : "");
249 } else if (map_entry != map_.end()) {
250 EXPECT_EQ(map_entry->first, item.key());
251
252 char value[kMaxValueLength + 1] = {};
253 EXPECT_EQ(OkStatus(),
254 item.Get(std::as_writable_bytes(std::span(value))).status());
255 EXPECT_EQ(map_entry->second, std::string(value));
256 }
257 }
258
259 EXPECT_EQ(count, map_.size());
260 }
261
262 // Adds a key to the KVS, if there is room for it.
Put(const std::string & key,const std::string & value)263 void Put(const std::string& key, const std::string& value) {
264 StartOperation("Put", key);
265 EXPECT_LE(value.size(), kMaxValueLength);
266
267 Status result = kvs_.Put(key, std::as_bytes(std::span(value)));
268
269 if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
270 EXPECT_EQ(Status::InvalidArgument(), result);
271 } else if (map_.size() == kvs_.max_size()) {
272 EXPECT_EQ(Status::ResourceExhausted(), result);
273 } else if (result.IsResourceExhausted()) {
274 EXPECT_FALSE(map_.empty());
275 } else if (result.ok()) {
276 map_[key] = value;
277 deleted_.erase(key);
278 } else {
279 PW_LOG_CRITICAL("Put: unhandled result %s", result.str());
280 std::abort();
281 }
282
283 FinishOperation("Put", result, key);
284 }
285
286 // Deletes a key from the KVS if it is present.
Delete(const std::string & key)287 void Delete(const std::string& key) {
288 StartOperation("Delete", key);
289
290 Status result = kvs_.Delete(key);
291
292 if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
293 EXPECT_EQ(Status::InvalidArgument(), result);
294 } else if (map_.count(key) == 0) {
295 EXPECT_EQ(Status::NotFound(), result);
296 } else if (result.ok()) {
297 map_.erase(key);
298
299 if (deleted_.count(key) > 0u) {
300 PW_LOG_CRITICAL("Deleted key that was already deleted %s", key.c_str());
301 std::abort();
302 }
303
304 deleted_.insert(key);
305 } else if (result.IsResourceExhausted()) {
306 PW_LOG_WARN("Delete: RESOURCE_EXHAUSTED could not delete key %s",
307 key.c_str());
308 } else {
309 PW_LOG_CRITICAL("Delete: unhandled result \"%s\"", result.str());
310 std::abort();
311 }
312 FinishOperation("Delete", result, key);
313 }
314
Init()315 void Init() {
316 StartOperation("Init");
317 Status status = kvs_.Init();
318 EXPECT_EQ(OkStatus(), status);
319 FinishOperation("Init", status);
320 }
321
GCFull()322 void GCFull() {
323 StartOperation("GCFull");
324 Status status = kvs_.FullMaintenance();
325 EXPECT_EQ(OkStatus(), status);
326
327 KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
328 if (post_stats.in_use_bytes > ((partition_.size_bytes() * 70) / 100)) {
329 EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
330 }
331
332 FinishOperation("GCFull", status);
333 }
334
GCPartial()335 void GCPartial() {
336 StartOperation("GCPartial");
337 KeyValueStore::StorageStats pre_stats = kvs_.GetStorageStats();
338 Status status = kvs_.PartialMaintenance();
339 KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
340 if (pre_stats.reclaimable_bytes != 0) {
341 EXPECT_EQ(OkStatus(), status);
342 EXPECT_LT(post_stats.reclaimable_bytes, pre_stats.reclaimable_bytes);
343 } else {
344 EXPECT_EQ(Status::NotFound(), status);
345 EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
346 }
347 FinishOperation("GCPartial", status);
348 }
349
350 // Logs that an operation started and checks that the KVS matches the map. If
351 // a key is provided, that is included in the logs.
StartOperation(const std::string & operation,const std::string & key="")352 void StartOperation(const std::string& operation,
353 const std::string& key = "") {
354 count_ += 1;
355 if (key.empty()) {
356 PW_LOG_DEBUG("[%3u] START %s", count_, operation.c_str());
357 } else {
358 PW_LOG_DEBUG(
359 "[%3u] START %s for '%s'", count_, operation.c_str(), key.c_str());
360 }
361 AbortIfMismatched("Pre-" + operation);
362 }
363
364 // Logs that an operation finished and checks that the KVS matches the map.
365 // If a key is provided, that is included in the logs.
FinishOperation(const std::string & operation,Status result,const std::string & key="")366 void FinishOperation(const std::string& operation,
367 Status result,
368 const std::string& key = "") {
369 if (key.empty()) {
370 PW_LOG_DEBUG(
371 "[%3u] FINISH %s <%s>", count_, operation.c_str(), result.str());
372 } else {
373 PW_LOG_DEBUG("[%3u] FINISH %s <%s> for '%s'",
374 count_,
375 operation.c_str(),
376 result.str(),
377 key.c_str());
378 }
379 AbortIfMismatched(operation);
380 }
381
empty() const382 bool empty() const { return map_.empty(); }
383
RandomPresentKey() const384 std::string RandomPresentKey() const {
385 return map_.empty() ? "" : map_.begin()->second;
386 }
387
AbortIfMismatched(const std::string & stage)388 void AbortIfMismatched(const std::string& stage) {
389 if (kvs_.size() != map_.size()) {
390 PW_LOG_CRITICAL("%s: size mismatch", stage.c_str());
391 CompareContents();
392 std::abort();
393 }
394 }
395
396 static constexpr size_t kMaxValueLength = 64;
397
398 static FakeFlashMemoryBuffer<kParams.sector_size,
399 (kParams.sector_count * kParams.redundancy)>
400 flash_;
401
402 FlashPartitionWithStatsBuffer<kMaxEntries> partition_;
403
404 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, kParams.redundancy> kvs_;
405 std::unordered_map<std::string, std::string> map_;
406 std::unordered_set<std::string> deleted_;
407 unsigned count_ = 0;
408 };
409
410 template <const TestParameters& kParams>
411 FakeFlashMemoryBuffer<kParams.sector_size,
412 (kParams.sector_count * kParams.redundancy)>
413 KvsTester<kParams>::flash_ =
414 FakeFlashMemoryBuffer<kParams.sector_size,
415 (kParams.sector_count * kParams.redundancy)>(
416 kParams.sector_alignment);
417
418 #define _TEST(fixture, test, ...) \
419 _TEST_VARIANT(fixture, test, test, __VA_ARGS__)
420
421 #define _TEST_VARIANT(fixture, test, variant, ...) \
422 TEST_F(fixture, test##variant) { tester_.Test_##test(__VA_ARGS__); }
423
424 // Defines a test fixture that runs all tests against a flash with the specified
425 // parameters.
426 #define RUN_TESTS_WITH_PARAMETERS(name, ...) \
427 class name : public ::testing::Test { \
428 protected: \
429 static constexpr TestParameters kParams = {__VA_ARGS__}; \
430 \
431 KvsTester<kParams> tester_; \
432 }; \
433 /* Run each test defined in the KvsTester class with these parameters. */ \
434 _TEST(name, Put); \
435 _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted); \
436 _TEST_VARIANT(name, RandomValidInputs, 1, 1000, 6006411, kNone); \
437 _TEST_VARIANT(name, RandomValidInputs, 1WithReinit, 500, 6006411, kReinit); \
438 _TEST_VARIANT(name, RandomValidInputs, 2, 100, 123, kNone); \
439 _TEST_VARIANT(name, RandomValidInputs, 2WithReinit, 100, 123, kReinit); \
440 _TEST_VARIANT(name, \
441 RandomValidInputs, \
442 1ReinitFullGC, \
443 300, \
444 6006411, \
445 kReinitWithFullGC); \
446 _TEST_VARIANT( \
447 name, RandomValidInputs, 2ReinitFullGC, 300, 123, kReinitWithFullGC); \
448 _TEST_VARIANT(name, \
449 RandomValidInputs, \
450 1ReinitPartialGC, \
451 100, \
452 6006411, \
453 kReinitWithPartialGC); \
454 _TEST_VARIANT(name, \
455 RandomValidInputs, \
456 2ReinitPartialGC, \
457 200, \
458 123, \
459 kReinitWithPartialGC); \
460 static_assert(true, "Don't forget a semicolon!")
461
462 RUN_TESTS_WITH_PARAMETERS(Basic,
463 .sector_size = 4 * 1024,
464 .sector_count = 4,
465 .sector_alignment = 16,
466 .redundancy = 1,
467 .partition_start_sector = 0,
468 .partition_sector_count = 4,
469 .partition_alignment = 16);
470
471 RUN_TESTS_WITH_PARAMETERS(BasicRedundant,
472 .sector_size = 4 * 1024,
473 .sector_count = 4,
474 .sector_alignment = 16,
475 .redundancy = 2,
476 .partition_start_sector = 0,
477 .partition_sector_count = 4,
478 .partition_alignment = 16);
479
480 RUN_TESTS_WITH_PARAMETERS(LotsOfSmallSectors,
481 .sector_size = 160,
482 .sector_count = 100,
483 .sector_alignment = 32,
484 .redundancy = 1,
485 .partition_start_sector = 5,
486 .partition_sector_count = 95,
487 .partition_alignment = 32);
488
489 RUN_TESTS_WITH_PARAMETERS(LotsOfSmallSectorsRedundant,
490 .sector_size = 160,
491 .sector_count = 100,
492 .sector_alignment = 32,
493 .redundancy = 2,
494 .partition_start_sector = 5,
495 .partition_sector_count = 95,
496 .partition_alignment = 32);
497
498 RUN_TESTS_WITH_PARAMETERS(OnlyTwoSectors,
499 .sector_size = 4 * 1024,
500 .sector_count = 20,
501 .sector_alignment = 16,
502 .redundancy = 1,
503 .partition_start_sector = 18,
504 .partition_sector_count = 2,
505 .partition_alignment = 64);
506
507 } // namespace
508 } // namespace pw::kvs
509