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