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 // Tests that directly work with the KVS's binary format and flash layer.
16
17 #include <string_view>
18
19 #include "gtest/gtest.h"
20 #include "pw_bytes/array.h"
21 #include "pw_kvs/crc16_checksum.h"
22 #include "pw_kvs/fake_flash_memory.h"
23 #include "pw_kvs/format.h"
24 #include "pw_kvs/internal/hash.h"
25 #include "pw_kvs/key_value_store.h"
26
27 namespace pw::kvs {
28 namespace {
29
30 using std::byte;
31 using std::string_view;
32
33 constexpr size_t kMaxEntries = 256;
34 constexpr size_t kMaxUsableSectors = 256;
35
SimpleChecksum(std::span<const byte> data,uint32_t state)36 constexpr uint32_t SimpleChecksum(std::span<const byte> data, uint32_t state) {
37 for (byte b : data) {
38 state += uint32_t(b);
39 }
40 return state;
41 }
42
43 template <typename State>
44 class ChecksumFunction final : public ChecksumAlgorithm {
45 public:
ChecksumFunction(State (& algorithm)(std::span<const byte>,State))46 ChecksumFunction(State (&algorithm)(std::span<const byte>, State))
47 : ChecksumAlgorithm(std::as_bytes(std::span(&state_, 1))),
48 algorithm_(algorithm) {}
49
Reset()50 void Reset() override { state_ = {}; }
51
Update(std::span<const byte> data)52 void Update(std::span<const byte> data) override {
53 state_ = algorithm_(data, state_);
54 }
55
56 private:
57 State state_;
58 State (&algorithm_)(std::span<const byte>, State);
59 };
60
61 ChecksumFunction<uint32_t> default_checksum(SimpleChecksum);
62
63 // Returns a buffer containing the necessary padding for an entry.
64 template <size_t kAlignmentBytes, size_t kKeyLength, size_t kValueSize = 0>
EntryPadding()65 constexpr auto EntryPadding() {
66 constexpr size_t content =
67 sizeof(internal::EntryHeader) + kKeyLength + kValueSize;
68 return std::array<byte, Padding(content, kAlignmentBytes)>{};
69 }
70
71 // Creates a buffer containing a valid entry at compile time.
72 template <uint32_t (*kChecksum)(std::span<const byte>,
73 uint32_t) = &SimpleChecksum,
74 size_t kAlignmentBytes = sizeof(internal::EntryHeader),
75 size_t kKeyLengthWithNull,
76 size_t kValueSize>
MakeValidEntry(uint32_t magic,uint32_t id,const char (& key)[kKeyLengthWithNull],const std::array<byte,kValueSize> & value)77 constexpr auto MakeValidEntry(uint32_t magic,
78 uint32_t id,
79 const char (&key)[kKeyLengthWithNull],
80 const std::array<byte, kValueSize>& value) {
81 constexpr size_t kKeyLength = kKeyLengthWithNull - 1;
82
83 auto data =
84 bytes::Concat(magic,
85 uint32_t(0),
86 uint8_t(kAlignmentBytes / 16 - 1),
87 uint8_t(kKeyLength),
88 uint16_t(kValueSize),
89 id,
90 bytes::String(key),
91 std::span(value),
92 EntryPadding<kAlignmentBytes, kKeyLength, kValueSize>());
93
94 // Calculate the checksum
95 uint32_t checksum = kChecksum(data, 0);
96 for (size_t i = 0; i < sizeof(checksum); ++i) {
97 data[4 + i] = byte(checksum & 0xff);
98 checksum >>= 8;
99 }
100
101 return data;
102 }
103
104 // Creates a buffer containing a deleted entry at compile time.
105 template <uint32_t (*kChecksum)(std::span<const byte>,
106 uint32_t) = &SimpleChecksum,
107 size_t kAlignmentBytes = sizeof(internal::EntryHeader),
108 size_t kKeyLengthWithNull>
MakeDeletedEntry(uint32_t magic,uint32_t id,const char (& key)[kKeyLengthWithNull])109 constexpr auto MakeDeletedEntry(uint32_t magic,
110 uint32_t id,
111 const char (&key)[kKeyLengthWithNull]) {
112 constexpr size_t kKeyLength = kKeyLengthWithNull - 1;
113
114 auto data = bytes::Concat(magic,
115 uint32_t(0),
116 uint8_t(kAlignmentBytes / 16 - 1),
117 uint8_t(kKeyLength),
118 uint16_t(0xFFFF),
119 id,
120 bytes::String(key),
121 EntryPadding<kAlignmentBytes, kKeyLength>());
122
123 // Calculate the checksum
124 uint32_t checksum = kChecksum(data, 0);
125 for (size_t i = 0; i < sizeof(checksum); ++i) {
126 data[4 + i] = byte(checksum & 0xff);
127 checksum >>= 8;
128 }
129
130 return data;
131 }
132
133 // For KVS magic value always use a random 32 bit integer rather than a
134 // human readable 4 bytes. See pw_kvs/format.h for more information.
135 constexpr uint32_t kMagic = 0x5ab2f0b5;
136
137 constexpr Options kNoGcOptions{
138 .gc_on_write = GargbageCollectOnWrite::kDisabled,
139 .recovery = ErrorRecovery::kManual,
140 .verify_on_read = true,
141 .verify_on_write = true,
142 };
143
144 constexpr Options kRecoveryNoGcOptions{
145 .gc_on_write = GargbageCollectOnWrite::kDisabled,
146 .recovery = ErrorRecovery::kLazy,
147 .verify_on_read = true,
148 .verify_on_write = true,
149 };
150
151 constexpr Options kRecoveryLazyGcOptions{
152 .gc_on_write = GargbageCollectOnWrite::kOneSector,
153 .recovery = ErrorRecovery::kLazy,
154 .verify_on_read = true,
155 .verify_on_write = true,
156 };
157
158 constexpr auto kEntry1 =
159 MakeValidEntry(kMagic, 1, "key1", bytes::String("value1"));
160 constexpr auto kEntry2 =
161 MakeValidEntry(kMagic, 3, "k2", bytes::String("value2"));
162 constexpr auto kEntry3 =
163 MakeValidEntry(kMagic, 4, "k3y", bytes::String("value3"));
164 constexpr auto kEntry4 =
165 MakeValidEntry(kMagic, 5, "4k", bytes::String("value4"));
166
167 constexpr auto kEmpty32Bytes = bytes::Initialized<32>(0xff);
168 static_assert(sizeof(kEmpty32Bytes) == 32);
169
170 EntryFormat default_format = {.magic = kMagic, .checksum = &default_checksum};
171
172 class KvsErrorHandling : public ::testing::Test {
173 protected:
KvsErrorHandling()174 KvsErrorHandling()
175 : flash_(internal::Entry::kMinAlignmentBytes),
176 partition_(&flash_),
177 kvs_(&partition_, default_format, kNoGcOptions) {}
178
InitFlashTo(std::span<const byte> contents)179 void InitFlashTo(std::span<const byte> contents) {
180 partition_.Erase();
181 std::memcpy(flash_.buffer().data(), contents.data(), contents.size());
182 }
183
184 FakeFlashMemoryBuffer<512, 4> flash_;
185 FlashPartition partition_;
186 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
187 };
188
TEST_F(KvsErrorHandling,Init_Ok)189 TEST_F(KvsErrorHandling, Init_Ok) {
190 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
191
192 EXPECT_EQ(OkStatus(), kvs_.Init());
193 byte buffer[64];
194 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
195 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
196 }
197
TEST_F(KvsErrorHandling,Init_DuplicateEntries_ReturnsDataLossButReadsEntry)198 TEST_F(KvsErrorHandling, Init_DuplicateEntries_ReturnsDataLossButReadsEntry) {
199 InitFlashTo(bytes::Concat(kEntry1, kEntry1));
200
201 EXPECT_EQ(Status::DataLoss(), kvs_.Init());
202 byte buffer[64];
203 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
204 EXPECT_EQ(Status::NotFound(), kvs_.Get("k2", buffer).status());
205 }
206
TEST_F(KvsErrorHandling,Init_CorruptEntry_FindsSubsequentValidEntry)207 TEST_F(KvsErrorHandling, Init_CorruptEntry_FindsSubsequentValidEntry) {
208 // Corrupt each byte in the first entry once.
209 for (size_t i = 0; i < kEntry1.size(); ++i) {
210 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
211 flash_.buffer()[i] = byte(int(flash_.buffer()[i]) + 1);
212
213 ASSERT_EQ(Status::DataLoss(), kvs_.Init());
214 byte buffer[64];
215 ASSERT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
216 ASSERT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
217
218 auto stats = kvs_.GetStorageStats();
219 // One valid entry.
220 ASSERT_EQ(32u, stats.in_use_bytes);
221 // Rest of space is reclaimable as the sector is corrupt.
222 ASSERT_EQ(480u, stats.reclaimable_bytes);
223 }
224 }
225
TEST_F(KvsErrorHandling,Init_CorruptEntry_CorrectlyAccountsForSectorSize)226 TEST_F(KvsErrorHandling, Init_CorruptEntry_CorrectlyAccountsForSectorSize) {
227 InitFlashTo(bytes::Concat(kEntry1, kEntry2, kEntry3, kEntry4));
228
229 // Corrupt the first and third entries.
230 flash_.buffer()[9] = byte(0xef);
231 flash_.buffer()[67] = byte(0xef);
232
233 ASSERT_EQ(Status::DataLoss(), kvs_.Init());
234
235 EXPECT_EQ(2u, kvs_.size());
236
237 byte buffer[64];
238 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
239 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
240 EXPECT_EQ(Status::NotFound(), kvs_.Get("k3y", buffer).status());
241 EXPECT_EQ(OkStatus(), kvs_.Get("4k", buffer).status());
242
243 auto stats = kvs_.GetStorageStats();
244 ASSERT_EQ(64u, stats.in_use_bytes);
245 ASSERT_EQ(448u, stats.reclaimable_bytes);
246 ASSERT_EQ(1024u, stats.writable_bytes);
247 }
248
TEST_F(KvsErrorHandling,Init_ReadError_InitializedWithSingleEntryError)249 TEST_F(KvsErrorHandling, Init_ReadError_InitializedWithSingleEntryError) {
250 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
251
252 flash_.InjectReadError(
253 FlashError::InRange(Status::Unauthenticated(), kEntry1.size()));
254
255 EXPECT_EQ(Status::DataLoss(), kvs_.Init());
256 EXPECT_FALSE(kvs_.initialized());
257 }
258
TEST_F(KvsErrorHandling,Init_CorruptSectors_ShouldBeUnwritable)259 TEST_F(KvsErrorHandling, Init_CorruptSectors_ShouldBeUnwritable) {
260 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
261
262 // Corrupt 3 of the 4 512-byte flash sectors. Corrupt sectors should be
263 // unwritable, and the KVS must maintain one empty sector at all times.
264 // As GC on write is disabled through KVS options, writes should no longer be
265 // possible due to lack of space.
266 flash_.buffer()[1] = byte(0xef);
267 flash_.buffer()[513] = byte(0xef);
268 flash_.buffer()[1025] = byte(0xef);
269
270 ASSERT_EQ(Status::DataLoss(), kvs_.Init());
271 EXPECT_EQ(Status::FailedPrecondition(),
272 kvs_.Put("hello", bytes::String("world")));
273 EXPECT_EQ(Status::FailedPrecondition(), kvs_.Put("a", bytes::String("b")));
274
275 // Existing valid entries should still be readable.
276 EXPECT_EQ(1u, kvs_.size());
277 byte buffer[64];
278 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
279 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
280
281 auto stats = kvs_.GetStorageStats();
282 EXPECT_EQ(32u, stats.in_use_bytes);
283 EXPECT_EQ(480u + 2 * 512u, stats.reclaimable_bytes);
284 EXPECT_EQ(0u, stats.writable_bytes);
285 }
286
TEST_F(KvsErrorHandling,Init_CorruptSectors_ShouldRecoverOne)287 TEST_F(KvsErrorHandling, Init_CorruptSectors_ShouldRecoverOne) {
288 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
289
290 // Corrupt all of the 4 512-byte flash sectors. Leave the pre-init entries
291 // intact. The KVS should be unavailable because recovery is set to full
292 // manual, and it does not have the required one empty sector at all times.
293 flash_.buffer()[64] = byte(0xef);
294 flash_.buffer()[513] = byte(0xef);
295 flash_.buffer()[1025] = byte(0xef);
296 flash_.buffer()[1537] = byte(0xef);
297
298 ASSERT_EQ(Status::DataLoss(), kvs_.Init());
299
300 auto stats = kvs_.GetStorageStats();
301 EXPECT_EQ(64u, stats.in_use_bytes);
302 EXPECT_EQ(4 * 512u - 64u, stats.reclaimable_bytes);
303 EXPECT_EQ(0u, stats.writable_bytes);
304 }
305
306 // Currently disabled due to KVS failing the test. KVS fails due to Init bailing
307 // out when it sees a small patch of "erased" looking flash space, which could
308 // result in missing keys that are actually written after a write error in
309 // flash.
TEST_F(KvsErrorHandling,DISABLED_Init_OkWithWriteErrorOnFlash)310 TEST_F(KvsErrorHandling, DISABLED_Init_OkWithWriteErrorOnFlash) {
311 InitFlashTo(bytes::Concat(kEntry1, kEmpty32Bytes, kEntry2));
312
313 EXPECT_EQ(Status::DataLoss(), kvs_.Init());
314 byte buffer[64];
315 EXPECT_EQ(2u, kvs_.size());
316 EXPECT_EQ(true, kvs_.error_detected());
317 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
318 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
319
320 auto stats = kvs_.GetStorageStats();
321 EXPECT_EQ(64u, stats.in_use_bytes);
322 EXPECT_EQ(512u - 64u, stats.reclaimable_bytes);
323 EXPECT_EQ(2 * 512u, stats.writable_bytes);
324 }
325
TEST_F(KvsErrorHandling,Init_CorruptKey_RevertsToPreviousVersion)326 TEST_F(KvsErrorHandling, Init_CorruptKey_RevertsToPreviousVersion) {
327 constexpr auto kVersion7 =
328 MakeValidEntry(kMagic, 7, "my_key", bytes::String("version 7"));
329 constexpr auto kVersion8 =
330 MakeValidEntry(kMagic, 8, "my_key", bytes::String("version 8"));
331
332 InitFlashTo(bytes::Concat(kVersion7, kVersion8));
333
334 // Corrupt a byte of entry version 8 (addresses 32-63).
335 flash_.buffer()[34] = byte(0xef);
336
337 ASSERT_EQ(Status::DataLoss(), kvs_.Init());
338
339 char buffer[64] = {};
340
341 EXPECT_EQ(1u, kvs_.size());
342
343 auto result = kvs_.Get("my_key", std::as_writable_bytes(std::span(buffer)));
344 EXPECT_EQ(OkStatus(), result.status());
345 EXPECT_EQ(sizeof("version 7") - 1, result.size());
346 EXPECT_STREQ("version 7", buffer);
347
348 EXPECT_EQ(32u, kvs_.GetStorageStats().in_use_bytes);
349 }
350
351 // The Put_WriteFailure_EntryNotAddedButBytesMarkedWritten test is run with both
352 // the KvsErrorRecovery and KvsErrorHandling test fixtures (different KVS
353 // configurations).
TEST_F(KvsErrorHandling,Put_WriteFailure_EntryNotAddedButBytesMarkedWritten)354 TEST_F(KvsErrorHandling, Put_WriteFailure_EntryNotAddedButBytesMarkedWritten) {
355 ASSERT_EQ(OkStatus(), kvs_.Init());
356 flash_.InjectWriteError(FlashError::Unconditional(Status::Unavailable(), 1));
357
358 EXPECT_EQ(Status::Unavailable(), kvs_.Put("key1", bytes::String("value1")));
359
360 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", std::span<byte>()).status());
361 ASSERT_TRUE(kvs_.empty());
362
363 auto stats = kvs_.GetStorageStats();
364 EXPECT_EQ(stats.in_use_bytes, 0u);
365 EXPECT_EQ(stats.reclaimable_bytes, 512u);
366 EXPECT_EQ(stats.writable_bytes, 512u * 2);
367
368 // The bytes were marked used, so a new key should not overlap with the bytes
369 // from the failed Put.
370 EXPECT_EQ(OkStatus(), kvs_.Put("key1", bytes::String("value1")));
371
372 stats = kvs_.GetStorageStats();
373 EXPECT_EQ(stats.in_use_bytes, (32u * kvs_.redundancy()));
374 EXPECT_EQ(stats.reclaimable_bytes, 512u);
375 EXPECT_EQ(stats.writable_bytes, 512u * 2 - (32 * kvs_.redundancy()));
376 }
377
378 class KvsErrorRecovery : public ::testing::Test {
379 protected:
KvsErrorRecovery()380 KvsErrorRecovery()
381 : flash_(internal::Entry::kMinAlignmentBytes),
382 partition_(&flash_),
383 kvs_(&partition_,
384 {.magic = kMagic, .checksum = &default_checksum},
385 kRecoveryNoGcOptions) {}
386
InitFlashTo(std::span<const byte> contents)387 void InitFlashTo(std::span<const byte> contents) {
388 partition_.Erase();
389 std::memcpy(flash_.buffer().data(), contents.data(), contents.size());
390 }
391
392 FakeFlashMemoryBuffer<512, 4> flash_;
393 FlashPartition partition_;
394 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
395 };
396
TEST_F(KvsErrorRecovery,Init_Ok)397 TEST_F(KvsErrorRecovery, Init_Ok) {
398 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
399
400 EXPECT_EQ(OkStatus(), kvs_.Init());
401 byte buffer[64];
402 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
403 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
404 }
405
TEST_F(KvsErrorRecovery,Init_DuplicateEntries_RecoversDuringInit)406 TEST_F(KvsErrorRecovery, Init_DuplicateEntries_RecoversDuringInit) {
407 InitFlashTo(bytes::Concat(kEntry1, kEntry1));
408
409 EXPECT_EQ(OkStatus(), kvs_.Init());
410 auto stats = kvs_.GetStorageStats();
411 EXPECT_EQ(stats.corrupt_sectors_recovered, 1u);
412
413 byte buffer[64];
414 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
415 EXPECT_EQ(Status::NotFound(), kvs_.Get("k2", buffer).status());
416 }
417
TEST_F(KvsErrorRecovery,Init_CorruptEntry_FindsSubsequentValidEntry)418 TEST_F(KvsErrorRecovery, Init_CorruptEntry_FindsSubsequentValidEntry) {
419 // Corrupt each byte in the first entry once.
420 for (size_t i = 0; i < kEntry1.size(); ++i) {
421 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
422 flash_.buffer()[i] = byte(int(flash_.buffer()[i]) + 1);
423
424 ASSERT_EQ(OkStatus(), kvs_.Init());
425 byte buffer[64];
426 ASSERT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
427 ASSERT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
428
429 auto stats = kvs_.GetStorageStats();
430 // One valid entry.
431 ASSERT_EQ(32u, stats.in_use_bytes);
432 // The sector with corruption should have been recovered.
433 ASSERT_EQ(0u, stats.reclaimable_bytes);
434 ASSERT_EQ(i + 1u, stats.corrupt_sectors_recovered);
435 }
436 }
437
TEST_F(KvsErrorRecovery,Init_CorruptEntry_CorrectlyAccountsForSectorSize)438 TEST_F(KvsErrorRecovery, Init_CorruptEntry_CorrectlyAccountsForSectorSize) {
439 InitFlashTo(bytes::Concat(kEntry1, kEntry2, kEntry3, kEntry4));
440
441 // Corrupt the first and third entries.
442 flash_.buffer()[9] = byte(0xef);
443 flash_.buffer()[67] = byte(0xef);
444
445 ASSERT_EQ(OkStatus(), kvs_.Init());
446
447 EXPECT_EQ(2u, kvs_.size());
448
449 byte buffer[64];
450 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
451 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
452 EXPECT_EQ(Status::NotFound(), kvs_.Get("k3y", buffer).status());
453 EXPECT_EQ(OkStatus(), kvs_.Get("4k", buffer).status());
454
455 auto stats = kvs_.GetStorageStats();
456 ASSERT_EQ(64u, stats.in_use_bytes);
457 ASSERT_EQ(0u, stats.reclaimable_bytes);
458 ASSERT_EQ(1472u, stats.writable_bytes);
459 ASSERT_EQ(1u, stats.corrupt_sectors_recovered);
460 }
461
TEST_F(KvsErrorRecovery,Init_ReadError_InitializedWithSingleEntryError)462 TEST_F(KvsErrorRecovery, Init_ReadError_InitializedWithSingleEntryError) {
463 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
464
465 flash_.InjectReadError(
466 FlashError::InRange(Status::Unauthenticated(), kEntry1.size()));
467
468 EXPECT_EQ(OkStatus(), kvs_.Init());
469 EXPECT_TRUE(kvs_.initialized());
470 auto stats = kvs_.GetStorageStats();
471 ASSERT_EQ(32u, stats.in_use_bytes);
472 ASSERT_EQ(0u, stats.reclaimable_bytes);
473 ASSERT_EQ(3 * 512u - 32u, stats.writable_bytes);
474 ASSERT_EQ(1u, stats.corrupt_sectors_recovered);
475 ASSERT_EQ(0u, stats.missing_redundant_entries_recovered);
476 }
477
TEST_F(KvsErrorRecovery,Init_CorruptSectors_ShouldBeUnwritable)478 TEST_F(KvsErrorRecovery, Init_CorruptSectors_ShouldBeUnwritable) {
479 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
480
481 // Corrupt 3 of the 4 512-byte flash sectors. Corrupt sectors should be
482 // recovered via garbage collection.
483 flash_.buffer()[1] = byte(0xef);
484 flash_.buffer()[513] = byte(0xef);
485 flash_.buffer()[1025] = byte(0xef);
486
487 ASSERT_EQ(OkStatus(), kvs_.Init());
488 EXPECT_EQ(OkStatus(), kvs_.Put("hello", bytes::String("world")));
489 EXPECT_EQ(OkStatus(), kvs_.Put("a", bytes::String("b")));
490
491 // Existing valid entries should still be readable.
492 EXPECT_EQ(3u, kvs_.size());
493 byte buffer[64];
494 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", buffer).status());
495 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
496
497 auto stats = kvs_.GetStorageStats();
498 EXPECT_EQ(96u, stats.in_use_bytes);
499 EXPECT_EQ(0u, stats.reclaimable_bytes);
500 EXPECT_EQ(1440u, stats.writable_bytes);
501 EXPECT_EQ(3u, stats.corrupt_sectors_recovered);
502 }
503
TEST_F(KvsErrorRecovery,Init_CorruptSectors_ShouldRecoverOne)504 TEST_F(KvsErrorRecovery, Init_CorruptSectors_ShouldRecoverOne) {
505 InitFlashTo(bytes::Concat(kEntry1, kEntry2));
506
507 // Corrupt all of the 4 512-byte flash sectors. Leave the pre-init entries
508 // intact. As part of recovery all corrupt sectors should get garbage
509 // collected.
510 flash_.buffer()[64] = byte(0xef);
511 flash_.buffer()[513] = byte(0xef);
512 flash_.buffer()[1025] = byte(0xef);
513 flash_.buffer()[1537] = byte(0xef);
514
515 ASSERT_EQ(OkStatus(), kvs_.Init());
516
517 auto stats = kvs_.GetStorageStats();
518 EXPECT_EQ(64u, stats.in_use_bytes);
519 EXPECT_EQ(0u, stats.reclaimable_bytes);
520 EXPECT_EQ(3 * 512u - 64u, stats.writable_bytes);
521 EXPECT_EQ(4u, stats.corrupt_sectors_recovered);
522 }
523
524 // Currently disabled due to KVS failing the test. KVS fails due to Init bailing
525 // out when it sees a small patch of "erased" looking flash space, which could
526 // result in missing keys that are actually written after a write error in
527 // flash.
TEST_F(KvsErrorRecovery,DISABLED_Init_OkWithWriteErrorOnFlash)528 TEST_F(KvsErrorRecovery, DISABLED_Init_OkWithWriteErrorOnFlash) {
529 InitFlashTo(bytes::Concat(kEntry1, kEmpty32Bytes, kEntry2));
530
531 EXPECT_EQ(OkStatus(), kvs_.Init());
532 byte buffer[64];
533 EXPECT_EQ(2u, kvs_.size());
534 EXPECT_EQ(false, kvs_.error_detected());
535 EXPECT_EQ(OkStatus(), kvs_.Get("key1", buffer).status());
536 EXPECT_EQ(OkStatus(), kvs_.Get("k2", buffer).status());
537
538 auto stats = kvs_.GetStorageStats();
539 EXPECT_EQ(64u, stats.in_use_bytes);
540 EXPECT_EQ(0u, stats.reclaimable_bytes);
541 EXPECT_EQ(3 * 512u - 64u, stats.writable_bytes);
542 EXPECT_EQ(1u, stats.corrupt_sectors_recovered);
543 EXPECT_EQ(0u, stats.missing_redundant_entries_recovered);
544 }
545
TEST_F(KvsErrorRecovery,Init_CorruptKey_RevertsToPreviousVersion)546 TEST_F(KvsErrorRecovery, Init_CorruptKey_RevertsToPreviousVersion) {
547 constexpr auto kVersion7 =
548 MakeValidEntry(kMagic, 7, "my_key", bytes::String("version 7"));
549 constexpr auto kVersion8 =
550 MakeValidEntry(kMagic, 8, "my_key", bytes::String("version 8"));
551
552 InitFlashTo(bytes::Concat(kVersion7, kVersion8));
553
554 // Corrupt a byte of entry version 8 (addresses 32-63).
555 flash_.buffer()[34] = byte(0xef);
556
557 ASSERT_EQ(OkStatus(), kvs_.Init());
558
559 char buffer[64] = {};
560
561 EXPECT_EQ(1u, kvs_.size());
562
563 auto result = kvs_.Get("my_key", std::as_writable_bytes(std::span(buffer)));
564 EXPECT_EQ(OkStatus(), result.status());
565 EXPECT_EQ(sizeof("version 7") - 1, result.size());
566 EXPECT_STREQ("version 7", buffer);
567
568 EXPECT_EQ(32u, kvs_.GetStorageStats().in_use_bytes);
569 }
570
571 // The Put_WriteFailure_EntryNotAddedButBytesMarkedWritten test is run with both
572 // the KvsErrorRecovery and KvsErrorHandling test fixtures (different KVS
573 // configurations).
TEST_F(KvsErrorRecovery,Put_WriteFailure_EntryNotAddedButBytesMarkedWritten)574 TEST_F(KvsErrorRecovery, Put_WriteFailure_EntryNotAddedButBytesMarkedWritten) {
575 ASSERT_EQ(OkStatus(), kvs_.Init());
576 flash_.InjectWriteError(FlashError::Unconditional(Status::Unavailable(), 1));
577
578 EXPECT_EQ(Status::Unavailable(), kvs_.Put("key1", bytes::String("value1")));
579 EXPECT_EQ(true, kvs_.error_detected());
580
581 EXPECT_EQ(Status::NotFound(), kvs_.Get("key1", std::span<byte>()).status());
582 ASSERT_TRUE(kvs_.empty());
583
584 auto stats = kvs_.GetStorageStats();
585 EXPECT_EQ(stats.in_use_bytes, 0u);
586 EXPECT_EQ(stats.reclaimable_bytes, 512u);
587 EXPECT_EQ(stats.writable_bytes, 512u * 2);
588 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
589 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
590
591 // The bytes were marked used, so a new key should not overlap with the bytes
592 // from the failed Put.
593 EXPECT_EQ(OkStatus(), kvs_.Put("key1", bytes::String("value1")));
594
595 stats = kvs_.GetStorageStats();
596 EXPECT_EQ(stats.in_use_bytes, (32u * kvs_.redundancy()));
597 EXPECT_EQ(stats.reclaimable_bytes, 512u);
598 EXPECT_EQ(stats.writable_bytes, 512u * 2 - (32 * kvs_.redundancy()));
599 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
600 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
601 }
602
603 // For KVS magic value always use a random 32 bit integer rather than a
604 // human readable 4 bytes. See pw_kvs/format.h for more information.
605 constexpr uint32_t kAltMagic = 0x41a2db83;
606
AltChecksum(std::span<const byte> data,uint32_t state)607 constexpr uint32_t AltChecksum(std::span<const byte> data, uint32_t state) {
608 for (byte b : data) {
609 state = (state << 8) | uint32_t(byte(state >> 24) ^ b);
610 }
611 return state;
612 }
613
614 ChecksumFunction<uint32_t> alt_checksum(AltChecksum);
615
616 constexpr auto kAltEntry =
617 MakeValidEntry<AltChecksum>(kAltMagic, 32, "A Key", bytes::String("XD"));
618
NoChecksum(std::span<const byte>,uint32_t)619 constexpr uint32_t NoChecksum(std::span<const byte>, uint32_t) { return 0; }
620 // For KVS magic value always use a random 32 bit integer rather than a
621 // human readable 4 bytes. See pw_kvs/format.h for more information.
622 constexpr uint32_t kNoChecksumMagic = 0xd49ba138;
623
624 constexpr auto kNoChecksumEntry = MakeValidEntry<NoChecksum>(
625 kNoChecksumMagic, 64, "kee", bytes::String("O_o"));
626
627 constexpr auto kDeletedEntry =
628 MakeDeletedEntry<AltChecksum>(kAltMagic, 128, "gone");
629
630 class InitializedRedundantMultiMagicKvs : public ::testing::Test {
631 protected:
632 static constexpr auto kInitialContents = bytes::Concat(
633 kNoChecksumEntry, kEntry1, kAltEntry, kEntry2, kEntry3, kDeletedEntry);
634
InitializedRedundantMultiMagicKvs()635 InitializedRedundantMultiMagicKvs()
636 : flash_(internal::Entry::kMinAlignmentBytes),
637 partition_(&flash_),
638 kvs_(&partition_,
639 {{
640 {.magic = kMagic, .checksum = &default_checksum},
641 {.magic = kAltMagic, .checksum = &alt_checksum},
642 {.magic = kNoChecksumMagic, .checksum = nullptr},
643 }},
644 kRecoveryNoGcOptions) {
645 partition_.Erase();
646 std::memcpy(flash_.buffer().data(),
647 kInitialContents.data(),
648 kInitialContents.size());
649
650 EXPECT_EQ(OkStatus(), kvs_.Init());
651 }
652
653 FakeFlashMemoryBuffer<512, 4, 3> flash_;
654 FlashPartition partition_;
655 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 2, 3> kvs_;
656 };
657
658 #define ASSERT_CONTAINS_ENTRY(key, str_value) \
659 do { \
660 char val[sizeof(str_value)] = {}; \
661 StatusWithSize stat = \
662 kvs_.Get(key, std::as_writable_bytes(std::span(val))); \
663 ASSERT_EQ(OkStatus(), stat.status()); \
664 ASSERT_EQ(sizeof(str_value) - 1, stat.size()); \
665 ASSERT_STREQ(str_value, val); \
666 } while (0)
667
TEST_F(InitializedRedundantMultiMagicKvs,AllEntriesArePresent)668 TEST_F(InitializedRedundantMultiMagicKvs, AllEntriesArePresent) {
669 ASSERT_CONTAINS_ENTRY("key1", "value1");
670 ASSERT_CONTAINS_ENTRY("k2", "value2");
671 ASSERT_CONTAINS_ENTRY("k3y", "value3");
672 ASSERT_CONTAINS_ENTRY("A Key", "XD");
673 ASSERT_CONTAINS_ENTRY("kee", "O_o");
674 }
675
TEST_F(InitializedRedundantMultiMagicKvs,RecoversLossOfFirstSector)676 TEST_F(InitializedRedundantMultiMagicKvs, RecoversLossOfFirstSector) {
677 auto stats = kvs_.GetStorageStats();
678 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
679 EXPECT_EQ(stats.reclaimable_bytes, 0u);
680 EXPECT_EQ(stats.writable_bytes, 512u * 3 - (192 * kvs_.redundancy()));
681 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
682 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
683
684 EXPECT_EQ(OkStatus(), partition_.Erase(0, 1));
685
686 ASSERT_CONTAINS_ENTRY("key1", "value1");
687 ASSERT_CONTAINS_ENTRY("k2", "value2");
688 ASSERT_CONTAINS_ENTRY("k3y", "value3");
689 ASSERT_CONTAINS_ENTRY("A Key", "XD");
690 ASSERT_CONTAINS_ENTRY("kee", "O_o");
691
692 EXPECT_EQ(true, kvs_.error_detected());
693
694 stats = kvs_.GetStorageStats();
695 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
696 EXPECT_EQ(stats.reclaimable_bytes, 320u);
697 EXPECT_EQ(stats.writable_bytes, 512u * 2 - (192 * (kvs_.redundancy() - 1)));
698 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
699 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
700
701 EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
702 stats = kvs_.GetStorageStats();
703 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
704 EXPECT_EQ(stats.reclaimable_bytes, 0u);
705 EXPECT_EQ(stats.writable_bytes, 512u * 3 - (192 * kvs_.redundancy()));
706 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
707 EXPECT_EQ(stats.missing_redundant_entries_recovered, 6u);
708 }
709
TEST_F(InitializedRedundantMultiMagicKvs,RecoversLossOfSecondSector)710 TEST_F(InitializedRedundantMultiMagicKvs, RecoversLossOfSecondSector) {
711 auto stats = kvs_.GetStorageStats();
712 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
713 EXPECT_EQ(stats.reclaimable_bytes, 0u);
714 EXPECT_EQ(stats.writable_bytes, 512u * 3 - (192 * kvs_.redundancy()));
715 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
716 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
717
718 EXPECT_EQ(OkStatus(), partition_.Erase(partition_.sector_size_bytes(), 1));
719
720 ASSERT_CONTAINS_ENTRY("key1", "value1");
721 ASSERT_CONTAINS_ENTRY("k2", "value2");
722 ASSERT_CONTAINS_ENTRY("k3y", "value3");
723 ASSERT_CONTAINS_ENTRY("A Key", "XD");
724 ASSERT_CONTAINS_ENTRY("kee", "O_o");
725
726 EXPECT_EQ(false, kvs_.error_detected());
727
728 EXPECT_EQ(OkStatus(), kvs_.Init());
729 stats = kvs_.GetStorageStats();
730 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
731 EXPECT_EQ(stats.reclaimable_bytes, 0u);
732 EXPECT_EQ(stats.writable_bytes, 512u * 3 - (192 * kvs_.redundancy()));
733 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
734 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
735 }
736
TEST_F(InitializedRedundantMultiMagicKvs,SingleReadErrors)737 TEST_F(InitializedRedundantMultiMagicKvs, SingleReadErrors) {
738 // Inject 2 read errors, so the first read attempt fully fails.
739 flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 2));
740
741 flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 1, 7));
742
743 ASSERT_CONTAINS_ENTRY("key1", "value1");
744 ASSERT_CONTAINS_ENTRY("k2", "value2");
745 ASSERT_CONTAINS_ENTRY("k3y", "value3");
746 ASSERT_CONTAINS_ENTRY("A Key", "XD");
747 ASSERT_CONTAINS_ENTRY("kee", "O_o");
748
749 EXPECT_EQ(true, kvs_.error_detected());
750
751 auto stats = kvs_.GetStorageStats();
752 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
753 EXPECT_EQ(stats.reclaimable_bytes, 320u);
754 EXPECT_EQ(stats.writable_bytes, 512u * 2 - (192 * (kvs_.redundancy() - 1)));
755 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
756 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
757 }
758
TEST_F(InitializedRedundantMultiMagicKvs,SingleWriteError)759 TEST_F(InitializedRedundantMultiMagicKvs, SingleWriteError) {
760 flash_.InjectWriteError(FlashError::Unconditional(Status::Internal(), 1, 1));
761
762 EXPECT_EQ(Status::Internal(), kvs_.Put("new key", bytes::String("abcd?")));
763
764 EXPECT_EQ(true, kvs_.error_detected());
765
766 auto stats = kvs_.GetStorageStats();
767 EXPECT_EQ(stats.in_use_bytes, 32 + (192u * kvs_.redundancy()));
768 EXPECT_EQ(stats.reclaimable_bytes, 320u);
769 EXPECT_EQ(stats.writable_bytes,
770 512u * 2 - 32 - (192 * (kvs_.redundancy() - 1)));
771 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
772 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
773
774 char val[20] = {};
775 EXPECT_EQ(
776 OkStatus(),
777 kvs_.Get("new key", std::as_writable_bytes(std::span(val))).status());
778
779 EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
780 stats = kvs_.GetStorageStats();
781 EXPECT_EQ(stats.in_use_bytes, (224u * kvs_.redundancy()));
782 EXPECT_EQ(stats.reclaimable_bytes, 0u);
783 EXPECT_EQ(stats.writable_bytes, 512u * 3 - (224 * kvs_.redundancy()));
784 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
785 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
786
787 EXPECT_EQ(
788 OkStatus(),
789 kvs_.Get("new key", std::as_writable_bytes(std::span(val))).status());
790 }
791
TEST_F(InitializedRedundantMultiMagicKvs,DataLossAfterLosingBothCopies)792 TEST_F(InitializedRedundantMultiMagicKvs, DataLossAfterLosingBothCopies) {
793 EXPECT_EQ(OkStatus(), partition_.Erase(0, 2));
794
795 char val[20] = {};
796 EXPECT_EQ(Status::DataLoss(),
797 kvs_.Get("key1", std::as_writable_bytes(std::span(val))).status());
798 EXPECT_EQ(Status::DataLoss(),
799 kvs_.Get("k2", std::as_writable_bytes(std::span(val))).status());
800 EXPECT_EQ(Status::DataLoss(),
801 kvs_.Get("k3y", std::as_writable_bytes(std::span(val))).status());
802 EXPECT_EQ(Status::DataLoss(),
803 kvs_.Get("A Key", std::as_writable_bytes(std::span(val))).status());
804 EXPECT_EQ(Status::DataLoss(),
805 kvs_.Get("kee", std::as_writable_bytes(std::span(val))).status());
806
807 EXPECT_EQ(true, kvs_.error_detected());
808
809 auto stats = kvs_.GetStorageStats();
810 EXPECT_EQ(stats.in_use_bytes, (192u * kvs_.redundancy()));
811 EXPECT_EQ(stats.reclaimable_bytes, 2 * 320u);
812 EXPECT_EQ(stats.writable_bytes, 512u);
813 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
814 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
815 }
816
TEST_F(InitializedRedundantMultiMagicKvs,PutNewEntry_UsesFirstFormat)817 TEST_F(InitializedRedundantMultiMagicKvs, PutNewEntry_UsesFirstFormat) {
818 EXPECT_EQ(OkStatus(), kvs_.Put("new key", bytes::String("abcd?")));
819
820 constexpr auto kNewEntry =
821 MakeValidEntry(kMagic, 129, "new key", bytes::String("abcd?"));
822 EXPECT_EQ(0,
823 std::memcmp(kNewEntry.data(),
824 flash_.buffer().data() + kInitialContents.size(),
825 kNewEntry.size()));
826 ASSERT_CONTAINS_ENTRY("new key", "abcd?");
827 }
828
TEST_F(InitializedRedundantMultiMagicKvs,PutExistingEntry_UsesFirstFormat)829 TEST_F(InitializedRedundantMultiMagicKvs, PutExistingEntry_UsesFirstFormat) {
830 EXPECT_EQ(OkStatus(), kvs_.Put("A Key", bytes::String("New value!")));
831
832 constexpr auto kNewEntry =
833 MakeValidEntry(kMagic, 129, "A Key", bytes::String("New value!"));
834 EXPECT_EQ(0,
835 std::memcmp(kNewEntry.data(),
836 flash_.buffer().data() + kInitialContents.size(),
837 kNewEntry.size()));
838 ASSERT_CONTAINS_ENTRY("A Key", "New value!");
839 }
840
841 #define ASSERT_KVS_CONTAINS_ENTRY(kvs, key, str_value) \
842 do { \
843 char val[sizeof(str_value)] = {}; \
844 StatusWithSize stat = \
845 kvs.Get(key, std::as_writable_bytes(std::span(val))); \
846 ASSERT_EQ(OkStatus(), stat.status()); \
847 ASSERT_EQ(sizeof(str_value) - 1, stat.size()); \
848 ASSERT_STREQ(str_value, val); \
849 } while (0)
850
TEST_F(InitializedRedundantMultiMagicKvs,UpdateEntryFormat)851 TEST_F(InitializedRedundantMultiMagicKvs, UpdateEntryFormat) {
852 ASSERT_EQ(OkStatus(), kvs_.FullMaintenance());
853
854 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 2, 1> local_kvs(
855 &partition_,
856 {.magic = kMagic, .checksum = &default_checksum},
857 kNoGcOptions);
858
859 ASSERT_EQ(OkStatus(), local_kvs.Init());
860 EXPECT_EQ(false, local_kvs.error_detected());
861 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "key1", "value1");
862 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k2", "value2");
863 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k3y", "value3");
864 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "A Key", "XD");
865 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "kee", "O_o");
866 }
867
868 class InitializedMultiMagicKvs : public ::testing::Test {
869 protected:
870 static constexpr auto kInitialContents =
871 bytes::Concat(kNoChecksumEntry, kEntry1, kAltEntry, kEntry2, kEntry3);
872
InitializedMultiMagicKvs()873 InitializedMultiMagicKvs()
874 : flash_(internal::Entry::kMinAlignmentBytes),
875 partition_(&flash_),
876 kvs_(&partition_,
877 {{
878 {.magic = kMagic, .checksum = &default_checksum},
879 {.magic = kAltMagic, .checksum = &alt_checksum},
880 {.magic = kNoChecksumMagic, .checksum = nullptr},
881 }},
882 kRecoveryNoGcOptions) {
883 partition_.Erase();
884 std::memcpy(flash_.buffer().data(),
885 kInitialContents.data(),
886 kInitialContents.size());
887
888 EXPECT_EQ(OkStatus(), kvs_.Init());
889 }
890
891 FakeFlashMemoryBuffer<512, 4, 3> flash_;
892 FlashPartition partition_;
893 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 1, 3> kvs_;
894 };
895
896 // Similar to test for InitializedRedundantMultiMagicKvs. Doing similar test
897 // with different KVS configuration.
TEST_F(InitializedMultiMagicKvs,AllEntriesArePresent)898 TEST_F(InitializedMultiMagicKvs, AllEntriesArePresent) {
899 ASSERT_CONTAINS_ENTRY("key1", "value1");
900 ASSERT_CONTAINS_ENTRY("k2", "value2");
901 ASSERT_CONTAINS_ENTRY("k3y", "value3");
902 ASSERT_CONTAINS_ENTRY("A Key", "XD");
903 ASSERT_CONTAINS_ENTRY("kee", "O_o");
904 }
905
906 // Similar to test for InitializedRedundantMultiMagicKvs. Doing similar test
907 // with different KVS configuration.
TEST_F(InitializedMultiMagicKvs,UpdateEntryFormat)908 TEST_F(InitializedMultiMagicKvs, UpdateEntryFormat) {
909 ASSERT_EQ(OkStatus(), kvs_.FullMaintenance());
910
911 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 1, 1> local_kvs(
912 &partition_,
913 {.magic = kMagic, .checksum = &default_checksum},
914 kNoGcOptions);
915
916 ASSERT_EQ(OkStatus(), local_kvs.Init());
917 EXPECT_EQ(false, local_kvs.error_detected());
918 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "key1", "value1");
919 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k2", "value2");
920 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k3y", "value3");
921 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "A Key", "XD");
922 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "kee", "O_o");
923 }
924
925 class InitializedRedundantLazyRecoveryKvs : public ::testing::Test {
926 protected:
927 static constexpr auto kInitialContents =
928 bytes::Concat(kEntry1, kEntry2, kEntry3, kEntry4);
929
InitializedRedundantLazyRecoveryKvs()930 InitializedRedundantLazyRecoveryKvs()
931 : flash_(internal::Entry::kMinAlignmentBytes),
932 partition_(&flash_),
933 kvs_(&partition_,
934 {.magic = kMagic, .checksum = &default_checksum},
935 kRecoveryLazyGcOptions) {
936 partition_.Erase();
937 std::memcpy(flash_.buffer().data(),
938 kInitialContents.data(),
939 kInitialContents.size());
940
941 EXPECT_EQ(OkStatus(), kvs_.Init());
942 }
943
944 FakeFlashMemoryBuffer<512, 4, 3> flash_;
945 FlashPartition partition_;
946 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 2> kvs_;
947 };
948
TEST_F(InitializedRedundantLazyRecoveryKvs,WriteAfterDataLoss)949 TEST_F(InitializedRedundantLazyRecoveryKvs, WriteAfterDataLoss) {
950 EXPECT_EQ(OkStatus(), partition_.Erase(0, 4));
951
952 char val[20] = {};
953 EXPECT_EQ(Status::DataLoss(),
954 kvs_.Get("key1", std::as_writable_bytes(std::span(val))).status());
955 EXPECT_EQ(Status::DataLoss(),
956 kvs_.Get("k2", std::as_writable_bytes(std::span(val))).status());
957 EXPECT_EQ(Status::DataLoss(),
958 kvs_.Get("k3y", std::as_writable_bytes(std::span(val))).status());
959 EXPECT_EQ(Status::DataLoss(),
960 kvs_.Get("4k", std::as_writable_bytes(std::span(val))).status());
961
962 EXPECT_EQ(true, kvs_.error_detected());
963
964 auto stats = kvs_.GetStorageStats();
965 EXPECT_EQ(stats.in_use_bytes, (128u * kvs_.redundancy()));
966 EXPECT_EQ(stats.reclaimable_bytes, 2 * 384u);
967 EXPECT_EQ(stats.writable_bytes, 512u);
968 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
969 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
970
971 ASSERT_EQ(Status::DataLoss(), kvs_.Put("key1", 1000));
972
973 EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
974 stats = kvs_.GetStorageStats();
975 EXPECT_EQ(stats.in_use_bytes, 0u);
976 EXPECT_EQ(stats.reclaimable_bytes, 0u);
977 EXPECT_EQ(stats.writable_bytes, 3 * 512u);
978 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
979 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
980 }
981
TEST_F(InitializedRedundantLazyRecoveryKvs,TwoSectorsCorruptWithGoodEntries)982 TEST_F(InitializedRedundantLazyRecoveryKvs, TwoSectorsCorruptWithGoodEntries) {
983 ASSERT_CONTAINS_ENTRY("key1", "value1");
984 ASSERT_CONTAINS_ENTRY("k2", "value2");
985 ASSERT_CONTAINS_ENTRY("k3y", "value3");
986 ASSERT_CONTAINS_ENTRY("4k", "value4");
987
988 EXPECT_EQ(false, kvs_.error_detected());
989
990 auto stats = kvs_.GetStorageStats();
991 EXPECT_EQ(stats.in_use_bytes, (128u * kvs_.redundancy()));
992 EXPECT_EQ(stats.reclaimable_bytes, 0u);
993 EXPECT_EQ(stats.writable_bytes, 3 * 512u - (128u * kvs_.redundancy()));
994 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
995 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
996
997 // Corrupt all the keys, alternating which copy gets corrupted.
998 flash_.buffer()[0x10] = byte(0xef);
999 flash_.buffer()[0x230] = byte(0xef);
1000 flash_.buffer()[0x50] = byte(0xef);
1001 flash_.buffer()[0x270] = byte(0xef);
1002
1003 ASSERT_CONTAINS_ENTRY("key1", "value1");
1004 ASSERT_CONTAINS_ENTRY("k2", "value2");
1005 ASSERT_CONTAINS_ENTRY("k3y", "value3");
1006 ASSERT_CONTAINS_ENTRY("4k", "value4");
1007
1008 EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
1009 stats = kvs_.GetStorageStats();
1010 EXPECT_EQ(stats.in_use_bytes, (128u * kvs_.redundancy()));
1011 EXPECT_EQ(stats.reclaimable_bytes, 0u);
1012 EXPECT_EQ(stats.writable_bytes, 3 * 512u - (128u * kvs_.redundancy()));
1013 EXPECT_EQ(stats.corrupt_sectors_recovered, 2u);
1014 EXPECT_EQ(stats.missing_redundant_entries_recovered, 4u);
1015 }
1016
1017 class InitializedLazyRecoveryKvs : public ::testing::Test {
1018 protected:
1019 static constexpr auto kInitialContents =
1020 bytes::Concat(kEntry1, kEntry2, kEntry3, kEntry4);
1021
InitializedLazyRecoveryKvs()1022 InitializedLazyRecoveryKvs()
1023 : flash_(internal::Entry::kMinAlignmentBytes),
1024 partition_(&flash_),
1025 kvs_(&partition_,
1026 {.magic = kMagic, .checksum = &default_checksum},
1027 kRecoveryLazyGcOptions) {
1028 partition_.Erase();
1029 std::memcpy(flash_.buffer().data(),
1030 kInitialContents.data(),
1031 kInitialContents.size());
1032
1033 EXPECT_EQ(OkStatus(), kvs_.Init());
1034 }
1035
1036 FakeFlashMemoryBuffer<512, 8> flash_;
1037 FlashPartition partition_;
1038 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
1039 };
1040
1041 // Test a KVS with a number of entries, several sectors that are nearly full
1042 // of stale (reclaimable) space, and not enough writable (free) space to add a
1043 // redundant copy for any of the entries. Tests that the add redundancy step of
1044 // repair is able to use garbage collection to free up space needed for the new
1045 // copies.
TEST_F(InitializedLazyRecoveryKvs,AddRedundancyToKvsFullOfStaleData)1046 TEST_F(InitializedLazyRecoveryKvs, AddRedundancyToKvsFullOfStaleData) {
1047 // Verify the pre-initialized key are present in the KVS.
1048 ASSERT_CONTAINS_ENTRY("key1", "value1");
1049 ASSERT_CONTAINS_ENTRY("k2", "value2");
1050 ASSERT_CONTAINS_ENTRY("k3y", "value3");
1051 ASSERT_CONTAINS_ENTRY("4k", "value4");
1052
1053 EXPECT_EQ(false, kvs_.error_detected());
1054
1055 auto stats = kvs_.GetStorageStats();
1056 EXPECT_EQ(stats.in_use_bytes, (128u * kvs_.redundancy()));
1057 EXPECT_EQ(stats.reclaimable_bytes, 0u);
1058 EXPECT_EQ(stats.writable_bytes, 7 * 512u - (128u * kvs_.redundancy()));
1059 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
1060 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
1061
1062 // Block of data to use for entry value. Sized to 470 so the total entry
1063 // results in the 512 byte sector having 16 bytes remaining.
1064 uint8_t test_data[470] = {1, 2, 3, 4, 5, 6};
1065
1066 // Add a near-sector size key entry to fill the KVS with a valid large entry
1067 // and stale data. Modify the value in between Puts so it actually writes
1068 // (identical value writes are skipped).
1069 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1070 test_data[0]++;
1071 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1072 test_data[0]++;
1073 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1074 test_data[0]++;
1075 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1076 test_data[0]++;
1077 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1078 test_data[0]++;
1079 EXPECT_EQ(OkStatus(), kvs_.Put("big_key", test_data));
1080
1081 // Instantiate a new KVS with redundancy of 2. This KVS should add an extra
1082 // copy of each valid key as part of the init process. Because there is not
1083 // enough writable space, the adding redundancy will need to garbage collect
1084 // two sectors.
1085 KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors, 2> local_kvs(
1086 &partition_,
1087 {.magic = kMagic, .checksum = &default_checksum},
1088 kRecoveryLazyGcOptions);
1089 ASSERT_EQ(OkStatus(), local_kvs.Init());
1090
1091 // Verify no errors found in the new KVS and all the entries are present.
1092 EXPECT_EQ(false, local_kvs.error_detected());
1093 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "key1", "value1");
1094 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k2", "value2");
1095 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "k3y", "value3");
1096 ASSERT_KVS_CONTAINS_ENTRY(local_kvs, "4k", "value4");
1097 StatusWithSize big_key_size = local_kvs.ValueSize("big_key");
1098 EXPECT_EQ(OkStatus(), big_key_size.status());
1099 EXPECT_EQ(sizeof(test_data), big_key_size.size());
1100
1101 // Verify that storage stats of the new redundant KVS match expected values.
1102 stats = local_kvs.GetStorageStats();
1103
1104 // Expected in-use bytes is size of (pre-init keys + big key) * redundancy.
1105 EXPECT_EQ(stats.in_use_bytes, ((128u + 496u) * local_kvs.redundancy()));
1106
1107 // Expected reclaimable space is number of stale entries remaining for big_key
1108 // (3 after GC to add redundancy) * total sizeof big_key entry (496 bytes).
1109
1110 EXPECT_EQ(stats.reclaimable_bytes, 496u * 3u);
1111 // Expected writable bytes is total writable size (512 * 7) - valid bytes (in
1112 // use) - reclaimable bytes.
1113 EXPECT_EQ(stats.writable_bytes, 848u);
1114 EXPECT_EQ(stats.corrupt_sectors_recovered, 0u);
1115 EXPECT_EQ(stats.missing_redundant_entries_recovered, 0u);
1116 }
1117
1118 } // namespace
1119 } // namespace pw::kvs
1120