third_party/pigweed/repo/pw_kvs/key_value_store_binary_format_test.cc

   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
  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:
  46   ChecksumFunction(State (&algorithm)(std::span<const byte>, State))
  47       : ChecksumAlgorithm(std::as_bytes(std::span(&state_, 1))),
  48         algorithm_(algorithm) {}
  49
  50   void Reset() override { state_ = {}; }
  51
  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>
  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>
  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>
 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:
 174   KvsErrorHandling()
 175       : flash_(internal::Entry::kMinAlignmentBytes),
 176         partition_(&flash_),
 177         kvs_(&partition_, default_format, kNoGcOptions) {}
 178
 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
 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
 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
 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
 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
 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
 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
 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.
 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
 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).
 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:
 380   KvsErrorRecovery()
 381       : flash_(internal::Entry::kMinAlignmentBytes),
 382         partition_(&flash_),
 383         kvs_(&partition_,
 384              {.magic = kMagic, .checksum = &default_checksum},
 385              kRecoveryNoGcOptions) {}
 386
 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
 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
 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
 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
 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
 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
 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
 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.
 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
 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).
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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.
 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.
 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
 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
 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
 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
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.
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