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 <string>
19 #include <string_view>
20 #include <unordered_map>
21 #include <unordered_set>
22
23 #include "pw_span/span.h"
24
25 #define DUMP_KVS_CONTENTS 0
26
27 #if DUMP_KVS_CONTENTS
28 #include <iostream>
29 #endif // DUMP_KVS_CONTENTS
30
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 #include "pw_string/string_builder.h"
38 #include "pw_unit_test/framework.h"
39
40 namespace pw::kvs {
41 namespace {
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(davidrogers): Using %2 (or any less than 16) fails with
137 // redundancy due to KVS filling up and not being able to write the
138 // second redundant entry, returning error. After re-init() the new key
139 // is picked up, resulting 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 // Ignore error to allow test to pass on platforms where writing out the
170 // stats is not possible.
171 partition_.SaveStorageStats(kvs_, label.data()).IgnoreError();
172 }
173 }
174
Test_Put()175 void Test_Put() {
176 Put("base_key", "base_value");
177 for (int i = 0; i < 100; ++i) {
178 Put("other_key", std::to_string(i));
179 }
180 for (int i = 0; i < 100; ++i) {
181 Put("key_" + std::to_string(i), std::to_string(i));
182 }
183 }
184
Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted()185 void Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted() {
186 for (int i = 0; i < 100; ++i) {
187 std::string str = "key_" + std::to_string(i);
188 Put(str, std::string(kMaxValueLength, '?'));
189 Delete(str);
190 }
191 }
192
193 private:
CompareContents()194 void CompareContents() {
195 #if DUMP_KVS_CONTENTS
196 std::set<std::string> map_keys, kvs_keys;
197
198 std::cout << "/==============================================\\\n";
199 std::cout << "KVS EXPECTED CONTENTS\n";
200 std::cout << "------------------------------------------------\n";
201 std::cout << "Entries: " << map_.size() << '\n';
202 std::cout << "------------------------------------------------\n";
203 for (const auto& [key, value] : map_) {
204 std::cout << key << " = [" << value << "]\n";
205 map_keys.insert(key);
206 }
207 std::cout << "\\===============================================/\n";
208
209 std::cout << "/==============================================\\\n";
210 std::cout << "KVS ACTUAL CONTENTS\n";
211 std::cout << "------------------------------------------------\n";
212 std::cout << "Entries: " << kvs_.size() << '\n';
213 std::cout << "------------------------------------------------\n";
214 for (const auto& item : kvs_) {
215 std::cout << item.key() << " = " << item.ValueSize().size() << " B\n";
216 kvs_keys.insert(std::string(item.key()));
217 }
218 std::cout << "\\===============================================/\n";
219
220 auto missing_from_kvs = difference(map_keys, kvs_keys);
221
222 if (!missing_from_kvs.empty()) {
223 std::cout << "MISSING FROM KVS: " << missing_from_kvs.size() << '\n';
224 for (auto& key : missing_from_kvs) {
225 std::cout << key << '\n';
226 }
227 }
228
229 auto missing_from_map = difference(kvs_keys, map_keys);
230 if (!missing_from_map.empty()) {
231 std::cout << "MISSING FROM MAP: " << missing_from_map.size() << '\n';
232 for (auto& key : missing_from_map) {
233 std::cout << key << '\n';
234 }
235 }
236 #endif // DUMP_KVS_CONTENTS
237
238 EXPECT_EQ(map_.size(), kvs_.size());
239
240 size_t count = 0;
241
242 for (auto& item : kvs_) {
243 count += 1;
244
245 auto map_entry = map_.find(std::string(item.key()));
246 if (map_entry == map_.end()) {
247 PW_LOG_CRITICAL(
248 "Entry %s missing from map%s",
249 item.key(),
250 deleted_.count(item.key()) > 0u ? " [was deleted previously]" : "");
251 } else if (map_entry != map_.end()) {
252 EXPECT_EQ(map_entry->first, item.key());
253
254 char value[kMaxValueLength + 1] = {};
255 EXPECT_EQ(OkStatus(),
256 item.Get(as_writable_bytes(span(value))).status());
257 EXPECT_EQ(map_entry->second, std::string(value));
258 }
259 }
260
261 EXPECT_EQ(count, map_.size());
262 }
263
264 // Adds a key to the KVS, if there is room for it.
Put(const std::string & key,const std::string & value)265 void Put(const std::string& key, const std::string& value) {
266 StartOperation("Put", key);
267 EXPECT_LE(value.size(), kMaxValueLength);
268
269 Status result = kvs_.Put(key, as_bytes(span(value)));
270
271 if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
272 EXPECT_EQ(Status::InvalidArgument(), result);
273 } else if (map_.size() == kvs_.max_size()) {
274 EXPECT_EQ(Status::ResourceExhausted(), result);
275 } else if (result.IsResourceExhausted()) {
276 EXPECT_FALSE(map_.empty());
277 } else if (result.ok()) {
278 map_[key] = value;
279 deleted_.erase(key);
280 } else {
281 PW_LOG_CRITICAL("Put: unhandled result %s", result.str());
282 std::abort();
283 }
284
285 FinishOperation("Put", result, key);
286 }
287
288 // Deletes a key from the KVS if it is present.
Delete(const std::string & key)289 void Delete(const std::string& key) {
290 StartOperation("Delete", key);
291
292 Status result = kvs_.Delete(key);
293
294 if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
295 EXPECT_EQ(Status::InvalidArgument(), result);
296 } else if (map_.count(key) == 0) {
297 EXPECT_EQ(Status::NotFound(), result);
298 } else if (result.ok()) {
299 map_.erase(key);
300
301 if (deleted_.count(key) > 0u) {
302 PW_LOG_CRITICAL("Deleted key that was already deleted %s", key.c_str());
303 std::abort();
304 }
305
306 deleted_.insert(key);
307 } else if (result.IsResourceExhausted()) {
308 PW_LOG_WARN("Delete: RESOURCE_EXHAUSTED could not delete key %s",
309 key.c_str());
310 } else {
311 PW_LOG_CRITICAL("Delete: unhandled result \"%s\"", result.str());
312 std::abort();
313 }
314 FinishOperation("Delete", result, key);
315 }
316
Init()317 void Init() {
318 StartOperation("Init");
319 Status status = kvs_.Init();
320 EXPECT_EQ(OkStatus(), status);
321 FinishOperation("Init", status);
322 }
323
GCFull()324 void GCFull() {
325 StartOperation("GCFull");
326 Status status = kvs_.FullMaintenance();
327 EXPECT_EQ(OkStatus(), status);
328
329 KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
330 if (post_stats.in_use_bytes > ((partition_.size_bytes() * 70) / 100)) {
331 EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
332 }
333
334 FinishOperation("GCFull", status);
335 }
336
GCPartial()337 void GCPartial() {
338 StartOperation("GCPartial");
339 KeyValueStore::StorageStats pre_stats = kvs_.GetStorageStats();
340 Status status = kvs_.PartialMaintenance();
341 KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
342 if (pre_stats.reclaimable_bytes != 0) {
343 EXPECT_EQ(OkStatus(), status);
344 EXPECT_LT(post_stats.reclaimable_bytes, pre_stats.reclaimable_bytes);
345 } else {
346 EXPECT_EQ(Status::NotFound(), status);
347 EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
348 }
349 FinishOperation("GCPartial", status);
350 }
351
352 // Logs that an operation started and checks that the KVS matches the map. If
353 // a key is provided, that is included in the logs.
StartOperation(const std::string & operation,const std::string & key="")354 void StartOperation(const std::string& operation,
355 const std::string& key = "") {
356 count_ += 1;
357 if (key.empty()) {
358 PW_LOG_DEBUG("[%3u] START %s", count_, operation.c_str());
359 } else {
360 PW_LOG_DEBUG(
361 "[%3u] START %s for '%s'", count_, operation.c_str(), key.c_str());
362 }
363 AbortIfMismatched("Pre-" + operation);
364 }
365
366 // Logs that an operation finished and checks that the KVS matches the map.
367 // If a key is provided, that is included in the logs.
FinishOperation(const std::string & operation,Status result,const std::string & key="")368 void FinishOperation(const std::string& operation,
369 Status result,
370 const std::string& key = "") {
371 if (key.empty()) {
372 PW_LOG_DEBUG(
373 "[%3u] FINISH %s <%s>", count_, operation.c_str(), result.str());
374 } else {
375 PW_LOG_DEBUG("[%3u] FINISH %s <%s> for '%s'",
376 count_,
377 operation.c_str(),
378 result.str(),
379 key.c_str());
380 }
381 AbortIfMismatched(operation);
382 }
383
empty() const384 bool empty() const { return map_.empty(); }
385
RandomPresentKey() const386 std::string RandomPresentKey() const {
387 return map_.empty() ? "" : map_.begin()->second;
388 }
389
AbortIfMismatched(const std::string & stage)390 void AbortIfMismatched(const std::string& stage) {
391 if (kvs_.size() != map_.size()) {
392 PW_LOG_CRITICAL("%s: size mismatch", stage.c_str());
393 CompareContents();
394 std::abort();
395 }
396 }
397
398 static constexpr size_t kMaxValueLength = 64;
399
400 static FakeFlashMemoryBuffer<kParams.sector_size,
401 (kParams.sector_count * kParams.redundancy)>
402 flash_;
403
404 FlashPartitionWithStatsBuffer<kMaxEntries> partition_;
405
406 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, kParams.redundancy> kvs_;
407 std::unordered_map<std::string, std::string> map_;
408 std::unordered_set<std::string> deleted_;
409 unsigned count_ = 0;
410 };
411
412 template <const TestParameters& kParams>
413 FakeFlashMemoryBuffer<kParams.sector_size,
414 (kParams.sector_count * kParams.redundancy)>
415 KvsTester<kParams>::flash_ =
416 FakeFlashMemoryBuffer<kParams.sector_size,
417 (kParams.sector_count * kParams.redundancy)>(
418 kParams.sector_alignment);
419
420 #define _TEST(fixture, test, ...) \
421 _TEST_VARIANT(fixture, test, test, __VA_ARGS__); \
422 static_assert(true, "Macros must be terminated with a semicolon")
423
424 #define _TEST_VARIANT(fixture, test, variant, ...) \
425 TEST_F(fixture, test##variant) { tester_.Test_##test(__VA_ARGS__); } \
426 static_assert(true, "Macros must be terminated with a semicolon")
427
428 // Defines a test fixture that runs all tests against a flash with the specified
429 // parameters.
430 #define RUN_TESTS_WITH_PARAMETERS(name, ...) \
431 class name : public ::testing::Test { \
432 protected: \
433 static constexpr TestParameters kParams = {__VA_ARGS__}; \
434 \
435 KvsTester<kParams> tester_; \
436 }; \
437 /* Run each test defined in the KvsTester class with these parameters. */ \
438 _TEST(name, Put); \
439 _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted); \
440 _TEST_VARIANT(name, RandomValidInputs, 1, 1000, 6006411, kNone); \
441 _TEST_VARIANT(name, RandomValidInputs, 1WithReinit, 500, 6006411, kReinit); \
442 _TEST_VARIANT(name, RandomValidInputs, 2, 100, 123, kNone); \
443 _TEST_VARIANT(name, RandomValidInputs, 2WithReinit, 100, 123, kReinit); \
444 _TEST_VARIANT(name, \
445 RandomValidInputs, \
446 1ReinitFullGC, \
447 300, \
448 6006411, \
449 kReinitWithFullGC); \
450 _TEST_VARIANT( \
451 name, RandomValidInputs, 2ReinitFullGC, 300, 123, kReinitWithFullGC); \
452 _TEST_VARIANT(name, \
453 RandomValidInputs, \
454 1ReinitPartialGC, \
455 100, \
456 6006411, \
457 kReinitWithPartialGC); \
458 _TEST_VARIANT(name, \
459 RandomValidInputs, \
460 2ReinitPartialGC, \
461 200, \
462 123, \
463 kReinitWithPartialGC); \
464 static_assert(true, "Don't forget a semicolon!")
465
466 RUN_TESTS_WITH_PARAMETERS(Basic,
467 .sector_size = 4 * 1024,
468 .sector_count = 4,
469 .sector_alignment = 16,
470 .redundancy = 1,
471 .partition_start_sector = 0,
472 .partition_sector_count = 4,
473 .partition_alignment = 16);
474
475 RUN_TESTS_WITH_PARAMETERS(BasicRedundant,
476 .sector_size = 4 * 1024,
477 .sector_count = 4,
478 .sector_alignment = 16,
479 .redundancy = 2,
480 .partition_start_sector = 0,
481 .partition_sector_count = 4,
482 .partition_alignment = 16);
483
484 RUN_TESTS_WITH_PARAMETERS(LotsOfSmallSectors,
485 .sector_size = 160,
486 .sector_count = 100,
487 .sector_alignment = 32,
488 .redundancy = 1,
489 .partition_start_sector = 5,
490 .partition_sector_count = 95,
491 .partition_alignment = 32);
492
493 RUN_TESTS_WITH_PARAMETERS(LotsOfSmallSectorsRedundant,
494 .sector_size = 160,
495 .sector_count = 100,
496 .sector_alignment = 32,
497 .redundancy = 2,
498 .partition_start_sector = 5,
499 .partition_sector_count = 95,
500 .partition_alignment = 32);
501
502 RUN_TESTS_WITH_PARAMETERS(OnlyTwoSectors,
503 .sector_size = 4 * 1024,
504 .sector_count = 20,
505 .sector_alignment = 16,
506 .redundancy = 1,
507 .partition_start_sector = 18,
508 .partition_sector_count = 2,
509 .partition_alignment = 64);
510
511 } // namespace
512 } // namespace pw::kvs
513