third_party/pigweed/repo/pw_kvs/key_value_store_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 #define DUMP_KVS_STATE_TO_FILE 0
  16 #define USE_MEMORY_BUFFER 1
  17 #define PW_LOG_USE_ULTRA_SHORT_NAMES 1
  18
  19 #include "pw_kvs/key_value_store.h"
  20
  21 #include <array>
  22 #include <cstdio>
  23 #include <cstring>
  24 #include <span>
  25
  26 #if DUMP_KVS_STATE_TO_FILE
  27 #include <vector>
  28 #endif  // DUMP_KVS_STATE_TO_FILE
  29
  30 #include "gtest/gtest.h"
  31 #include "pw_bytes/array.h"
  32 #include "pw_checksum/crc16_ccitt.h"
  33 #include "pw_kvs/crc16_checksum.h"
  34 #include "pw_kvs/fake_flash_memory.h"
  35 #include "pw_kvs/flash_memory.h"
  36 #include "pw_kvs/internal/entry.h"
  37 #include "pw_log/log.h"
  38 #include "pw_status/status.h"
  39 #include "pw_string/string_builder.h"
  40
  41 namespace pw::kvs {
  42 namespace {
  43
  44 using internal::EntryHeader;
  45 using std::byte;
  46
  47 constexpr size_t kMaxEntries = 256;
  48 constexpr size_t kMaxUsableSectors = 256;
  49
  50 // This is a self contained flash unit with both memory and a single partition.
  51 template <uint32_t sector_size_bytes, uint16_t sector_count>
  52 struct FlashWithPartitionFake {
  53   // Default to 16 byte alignment, which is common in practice.
  54   FlashWithPartitionFake() : FlashWithPartitionFake(16) {}
  55   FlashWithPartitionFake(size_t alignment_bytes)
  56       : memory(alignment_bytes), partition(&memory, 0, memory.sector_count()) {}
  57
  58   FakeFlashMemoryBuffer<sector_size_bytes, sector_count> memory;
  59   FlashPartition partition;
  60
  61  public:
  62 #if DUMP_KVS_STATE_TO_FILE
  63   Status Dump(const char* filename) {
  64     std::FILE* out_file = std::fopen(filename, "w+");
  65     if (out_file == nullptr) {
  66       PW_LOG_ERROR("Failed to dump to %s", filename);
  67       return Status::DataLoss();
  68     }
  69     std::vector<std::byte> out_vec(memory.size_bytes());
  70     Status status =
  71         memory.Read(0, std::span<std::byte>(out_vec.data(), out_vec.size()));
  72     if (status != OkStatus()) {
  73       fclose(out_file);
  74       return status;
  75     }
  76
  77     size_t written =
  78         std::fwrite(out_vec.data(), 1, memory.size_bytes(), out_file);
  79     if (written != memory.size_bytes()) {
  80       PW_LOG_ERROR("Failed to dump to %s, written=%u",
  81                    filename,
  82                    static_cast<unsigned>(written));
  83       status = Status::DataLoss();
  84     } else {
  85       PW_LOG_INFO("Dumped to %s", filename);
  86       status = OkStatus();
  87     }
  88
  89     fclose(out_file);
  90     return status;
  91   }
  92 #else
  93   Status Dump(const char*) { return OkStatus(); }
  94 #endif  // DUMP_KVS_STATE_TO_FILE
  95 };
  96
  97 typedef FlashWithPartitionFake<4 * 128 /*sector size*/, 6 /*sectors*/> Flash;
  98
  99 FakeFlashMemoryBuffer<1024, 60> large_test_flash(8);
 100 FlashPartition large_test_partition(&large_test_flash,
 101                                     0,
 102                                     large_test_flash.sector_count());
 103
 104 constexpr std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
 105
 106 ChecksumCrc16 checksum;
 107 // For KVS magic value always use a random 32 bit integer rather than a
 108 // human readable 4 bytes. See pw_kvs/format.h for more information.
 109 constexpr EntryFormat default_format{.magic = 0xa6cb3c16,
 110                                      .checksum = &checksum};
 111
 112 }  // namespace
 113
 114 TEST(InitCheck, TooFewSectors) {
 115   // Use test flash with 1 x 4k sectors, 16 byte alignment
 116   FakeFlashMemoryBuffer<4 * 1024, 1> test_flash(16);
 117   FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
 118
 119   // For KVS magic value always use a random 32 bit integer rather than a
 120   // human readable 4 bytes. See pw_kvs/format.h for more information.
 121   constexpr EntryFormat format{.magic = 0x89bb14d2, .checksum = nullptr};
 122   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&test_partition,
 123                                                           format);
 124
 125   EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
 126 }
 127
 128 TEST(InitCheck, ZeroSectors) {
 129   // Use test flash with 1 x 4k sectors, 16 byte alignment
 130   FakeFlashMemoryBuffer<4 * 1024, 1> test_flash(16);
 131
 132   // Set FlashPartition to have 0 sectors.
 133   FlashPartition test_partition(&test_flash, 0, 0);
 134
 135   // For KVS magic value always use a random 32 bit integer rather than a
 136   // human readable 4 bytes. See pw_kvs/format.h for more information.
 137   constexpr EntryFormat format{.magic = 0xd1da57c1, .checksum = nullptr};
 138   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&test_partition,
 139                                                           format);
 140
 141   EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
 142 }
 143
 144 TEST(InitCheck, TooManySectors) {
 145   // Use test flash with 1 x 4k sectors, 16 byte alignment
 146   FakeFlashMemoryBuffer<4 * 1024, 5> test_flash(16);
 147
 148   // Set FlashPartition to have 0 sectors.
 149   FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
 150
 151   // For KVS magic value always use a random 32 bit integer rather than a
 152   // human readable 4 bytes. See pw_kvs/format.h for more information.
 153   constexpr EntryFormat format{.magic = 0x610f6d17, .checksum = nullptr};
 154   KeyValueStoreBuffer<kMaxEntries, 2> kvs(&test_partition, format);
 155
 156   EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
 157 }
 158
 159 #define ASSERT_OK(expr) ASSERT_EQ(OkStatus(), expr)
 160 #define EXPECT_OK(expr) EXPECT_EQ(OkStatus(), expr)
 161
 162 TEST(InMemoryKvs, WriteOneKeyMultipleTimes) {
 163   // Create and erase the fake flash. It will persist across reloads.
 164   Flash flash;
 165   ASSERT_OK(flash.partition.Erase());
 166
 167   int num_reloads = 2;
 168   for (int reload = 0; reload < num_reloads; ++reload) {
 169     DBG("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
 170     DBG("xxx                                      xxxx");
 171     DBG("xxx               Reload %2d              xxxx", reload);
 172     DBG("xxx                                      xxxx");
 173     DBG("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
 174
 175     // Create and initialize the KVS. For KVS magic value always use a random 32
 176     // bit integer rather than a human readable 4 bytes. See pw_kvs/format.h for
 177     // more information.
 178     constexpr EntryFormat format{.magic = 0x83a9257, .checksum = nullptr};
 179     KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 180                                                             format);
 181     ASSERT_OK(kvs.Init());
 182
 183     // Write the same entry many times.
 184     const char* key = "abcd";
 185     const size_t num_writes = 99;
 186     uint32_t written_value;
 187     EXPECT_EQ(kvs.size(), (reload == 0) ? 0 : 1u);
 188     for (uint32_t i = 0; i < num_writes; ++i) {
 189       DBG("PUT #%zu for key %s with value %zu", size_t(i), key, size_t(i));
 190
 191       written_value = i + 0xfc;  // Prevent accidental pass with zero.
 192       EXPECT_OK(kvs.Put(key, written_value));
 193       EXPECT_EQ(kvs.size(), 1u);
 194     }
 195
 196     // Verify that we can read the value back.
 197     DBG("GET final value for key: %s", key);
 198     uint32_t actual_value;
 199     EXPECT_OK(kvs.Get(key, &actual_value));
 200     EXPECT_EQ(actual_value, written_value);
 201
 202     char fname_buf[64] = {'\0'};
 203     snprintf(&fname_buf[0],
 204              sizeof(fname_buf),
 205              "WriteOneKeyMultipleTimes_%d.bin",
 206              reload);
 207     flash.Dump(fname_buf);
 208   }
 209 }
 210
 211 TEST(InMemoryKvs, WritingMultipleKeysIncreasesSize) {
 212   // Create and erase the fake flash.
 213   Flash flash;
 214   ASSERT_OK(flash.partition.Erase());
 215
 216   // Create and initialize the KVS. For KVS magic value always use a random 32
 217   // bit integer rather than a human readable 4 bytes. See pw_kvs/format.h for
 218   // more information.
 219   constexpr EntryFormat format{.magic = 0x2ed3a058, .checksum = nullptr};
 220   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 221                                                           format);
 222   ASSERT_OK(kvs.Init());
 223
 224   // Write the same entry many times.
 225   const size_t num_writes = 10;
 226   EXPECT_EQ(kvs.size(), 0u);
 227   for (size_t i = 0; i < num_writes; ++i) {
 228     StringBuffer<150> key;
 229     key << "key_" << i;
 230     DBG("PUT #%zu for key %s with value %zu", i, key.c_str(), i);
 231
 232     size_t value = i + 77;  // Prevent accidental pass with zero.
 233     EXPECT_OK(kvs.Put(key.view(), value));
 234     EXPECT_EQ(kvs.size(), i + 1);
 235   }
 236   flash.Dump("WritingMultipleKeysIncreasesSize.bin");
 237 }
 238
 239 TEST(InMemoryKvs, WriteAndReadOneKey) {
 240   // Create and erase the fake flash.
 241   Flash flash;
 242   ASSERT_OK(flash.partition.Erase());
 243
 244   // Create and initialize the KVS.
 245   // For KVS magic value always use a random 32 bit integer rather than a
 246   // human readable 4 bytes. See pw_kvs/format.h for more information.
 247   constexpr EntryFormat format{.magic = 0x5d70896, .checksum = nullptr};
 248   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 249                                                           format);
 250   ASSERT_OK(kvs.Init());
 251
 252   // Add one entry.
 253   const char* key = "Key1";
 254   DBG("PUT value for key: %s", key);
 255   uint8_t written_value = 0xDA;
 256   ASSERT_OK(kvs.Put(key, written_value));
 257   EXPECT_EQ(kvs.size(), 1u);
 258
 259   DBG("GET value for key: %s", key);
 260   uint8_t actual_value;
 261   ASSERT_OK(kvs.Get(key, &actual_value));
 262   EXPECT_EQ(actual_value, written_value);
 263
 264   EXPECT_EQ(kvs.size(), 1u);
 265 }
 266
 267 TEST(InMemoryKvs, WriteOneKeyValueMultipleTimes) {
 268   // Create and erase the fake flash.
 269   Flash flash;
 270   ASSERT_OK(flash.partition.Erase());
 271
 272   // Create and initialize the KVS.
 273   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 274                                                           default_format);
 275   ASSERT_OK(kvs.Init());
 276
 277   // Add one entry, with the same key and value, multiple times.
 278   const char* key = "Key1";
 279   uint8_t written_value = 0xDA;
 280   for (int i = 0; i < 50; i++) {
 281     DBG("PUT [%d] value for key: %s", i, key);
 282     ASSERT_OK(kvs.Put(key, written_value));
 283     EXPECT_EQ(kvs.size(), 1u);
 284   }
 285
 286   DBG("GET value for key: %s", key);
 287   uint8_t actual_value;
 288   ASSERT_OK(kvs.Get(key, &actual_value));
 289   EXPECT_EQ(actual_value, written_value);
 290
 291   // Verify that only one entry was written to the KVS.
 292   EXPECT_EQ(kvs.size(), 1u);
 293   EXPECT_EQ(kvs.transaction_count(), 1u);
 294   KeyValueStore::StorageStats stats = kvs.GetStorageStats();
 295   EXPECT_EQ(stats.reclaimable_bytes, 0u);
 296 }
 297
 298 TEST(InMemoryKvs, Basic) {
 299   const char* key1 = "Key1";
 300   const char* key2 = "Key2";
 301
 302   // Create and erase the fake flash.
 303   Flash flash;
 304   ASSERT_EQ(OkStatus(), flash.partition.Erase());
 305
 306   // Create and initialize the KVS.
 307   // For KVS magic value always use a random 32 bit integer rather than a
 308   // human readable 4 bytes. See pw_kvs/format.h for more information.
 309   constexpr EntryFormat format{.magic = 0x7bf19895, .checksum = nullptr};
 310   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 311                                                           format);
 312   ASSERT_OK(kvs.Init());
 313
 314   // Add two entries with different keys and values.
 315   uint8_t value1 = 0xDA;
 316   ASSERT_OK(kvs.Put(key1, std::as_bytes(std::span(&value1, sizeof(value1)))));
 317   EXPECT_EQ(kvs.size(), 1u);
 318
 319   uint32_t value2 = 0xBAD0301f;
 320   ASSERT_OK(kvs.Put(key2, value2));
 321   EXPECT_EQ(kvs.size(), 2u);
 322
 323   // Verify data
 324   uint32_t test2;
 325   EXPECT_OK(kvs.Get(key2, &test2));
 326
 327   uint8_t test1;
 328   ASSERT_OK(kvs.Get(key1, &test1));
 329
 330   EXPECT_EQ(test1, value1);
 331   EXPECT_EQ(test2, value2);
 332
 333   EXPECT_EQ(kvs.size(), 2u);
 334 }
 335
 336 TEST(InMemoryKvs, CallingEraseTwice_NothingWrittenToFlash) {
 337   // Create and erase the fake flash.
 338   Flash flash;
 339   ASSERT_EQ(OkStatus(), flash.partition.Erase());
 340
 341   // Create and initialize the KVS.
 342   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 343                                                           default_format);
 344   ASSERT_OK(kvs.Init());
 345
 346   const uint8_t kValue = 0xDA;
 347   ASSERT_EQ(OkStatus(), kvs.Put(keys[0], kValue));
 348   ASSERT_EQ(OkStatus(), kvs.Delete(keys[0]));
 349
 350   // Compare before / after checksums to verify that nothing was written.
 351   const uint16_t crc = checksum::Crc16Ccitt::Calculate(flash.memory.buffer());
 352
 353   EXPECT_EQ(kvs.Delete(keys[0]), Status::NotFound());
 354
 355   EXPECT_EQ(crc, checksum::Crc16Ccitt::Calculate(flash.memory.buffer()));
 356 }
 357
 358 class LargeEmptyInitializedKvs : public ::testing::Test {
 359  protected:
 360   LargeEmptyInitializedKvs() : kvs_(&large_test_partition, default_format) {
 361     ASSERT_EQ(OkStatus(), large_test_partition.Erase());
 362     ASSERT_EQ(OkStatus(), kvs_.Init());
 363   }
 364
 365   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
 366 };
 367
 368 TEST_F(LargeEmptyInitializedKvs, Basic) {
 369   const uint8_t kValue1 = 0xDA;
 370   const uint8_t kValue2 = 0x12;
 371   uint8_t value;
 372   ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
 373   EXPECT_EQ(kvs_.size(), 1u);
 374   ASSERT_EQ(OkStatus(), kvs_.Delete(keys[0]));
 375   EXPECT_EQ(kvs_.Get(keys[0], &value), Status::NotFound());
 376   ASSERT_EQ(OkStatus(), kvs_.Put(keys[1], kValue1));
 377   ASSERT_EQ(OkStatus(), kvs_.Put(keys[2], kValue2));
 378   ASSERT_EQ(OkStatus(), kvs_.Delete(keys[1]));
 379   EXPECT_EQ(OkStatus(), kvs_.Get(keys[2], &value));
 380   EXPECT_EQ(kValue2, value);
 381   ASSERT_EQ(kvs_.Get(keys[1], &value), Status::NotFound());
 382   EXPECT_EQ(kvs_.size(), 1u);
 383 }
 384
 385 TEST_F(LargeEmptyInitializedKvs, FullMaintenance) {
 386   const uint8_t kValue1 = 0xDA;
 387   const uint8_t kValue2 = 0x12;
 388
 389   // Write a key and write again with a different value, resulting in a stale
 390   // entry from the first write.
 391   ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
 392   ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue2));
 393   EXPECT_EQ(kvs_.size(), 1u);
 394
 395   KeyValueStore::StorageStats stats = kvs_.GetStorageStats();
 396   EXPECT_EQ(stats.sector_erase_count, 0u);
 397   EXPECT_GT(stats.reclaimable_bytes, 0u);
 398
 399   // Do regular FullMaintenance, which should not touch the sector with valid
 400   // data.
 401   EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
 402   stats = kvs_.GetStorageStats();
 403   EXPECT_EQ(stats.sector_erase_count, 0u);
 404   EXPECT_GT(stats.reclaimable_bytes, 0u);
 405
 406   // Do aggressive FullMaintenance, which should GC the sector with valid data,
 407   // resulting in no reclaimable bytes and an erased sector.
 408   EXPECT_EQ(OkStatus(), kvs_.HeavyMaintenance());
 409   stats = kvs_.GetStorageStats();
 410   EXPECT_EQ(stats.sector_erase_count, 1u);
 411   EXPECT_EQ(stats.reclaimable_bytes, 0u);
 412 }
 413
 414 TEST(InMemoryKvs, Put_MaxValueSize) {
 415   // Create and erase the fake flash.
 416   Flash flash;
 417   ASSERT_EQ(OkStatus(), flash.partition.Erase());
 418
 419   // Create and initialize the KVS.
 420   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
 421                                                           default_format);
 422   ASSERT_OK(kvs.Init());
 423
 424   size_t max_key_value_size = kvs.max_key_value_size_bytes();
 425   EXPECT_EQ(max_key_value_size,
 426             KeyValueStore::max_key_value_size_bytes(
 427                 flash.partition.sector_size_bytes()));
 428
 429   size_t max_value_size =
 430       flash.partition.sector_size_bytes() - sizeof(EntryHeader) - 1;
 431   EXPECT_EQ(max_key_value_size, (max_value_size + 1));
 432
 433   // Use the large_test_flash as a big chunk of data for the Put statement.
 434   ASSERT_GT(sizeof(large_test_flash), max_value_size + 2 * sizeof(EntryHeader));
 435   auto big_data = std::as_bytes(std::span(&large_test_flash, 1));
 436
 437   EXPECT_EQ(OkStatus(), kvs.Put("K", big_data.subspan(0, max_value_size)));
 438
 439   // Larger than maximum is rejected.
 440   EXPECT_EQ(Status::InvalidArgument(),
 441             kvs.Put("K", big_data.subspan(0, max_value_size + 1)));
 442   EXPECT_EQ(Status::InvalidArgument(), kvs.Put("K", big_data));
 443 }
 444
 445 }  // namespace pw::kvs