third_party/pigweed/repo/pw_kvs/key_value_store_initialized_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 #include <array>
  16 #include <cstdio>
  17 #include <cstring>
  18 #include <span>
  19
  20 #include "gtest/gtest.h"
  21 #include "pw_bytes/array.h"
  22 #include "pw_checksum/crc16_ccitt.h"
  23 #include "pw_kvs/crc16_checksum.h"
  24 #include "pw_kvs/flash_memory.h"
  25 #include "pw_kvs/flash_test_partition.h"
  26 #include "pw_kvs/internal/entry.h"
  27 #include "pw_kvs/key_value_store.h"
  28 #include "pw_log/log.h"
  29 #include "pw_status/status.h"
  30 #include "pw_string/string_builder.h"
  31
  32 namespace pw::kvs {
  33 namespace {
  34
  35 using internal::EntryHeader;
  36 using std::byte;
  37
  38 constexpr size_t kMaxEntries = 256;
  39 constexpr size_t kMaxUsableSectors = 256;
  40
  41 FlashPartition& test_partition = FlashTestPartition();
  42
  43 std::array<byte, 512> buffer;
  44
  45 size_t RoundUpForAlignment(size_t size) {
  46   return AlignUp(size, test_partition.alignment_bytes());
  47 }
  48
  49 // This class gives attributes of KVS that we are testing against
  50 class KvsAttributes {
  51  public:
  52   KvsAttributes(size_t key_size, size_t data_size)
  53       : chunk_header_size_(RoundUpForAlignment(sizeof(EntryHeader))),
  54         data_size_(RoundUpForAlignment(data_size)),
  55         key_size_(RoundUpForAlignment(key_size)),
  56         erase_size_(chunk_header_size_ + key_size_),
  57         min_put_size_(
  58             RoundUpForAlignment(chunk_header_size_ + key_size_ + data_size_)) {}
  59
  60   size_t ChunkHeaderSize() { return chunk_header_size_; }
  61   size_t DataSize() { return data_size_; }
  62   size_t KeySize() { return key_size_; }
  63   size_t EraseSize() { return erase_size_; }
  64   size_t MinPutSize() { return min_put_size_; }
  65
  66  private:
  67   const size_t chunk_header_size_;
  68   const size_t data_size_;
  69   const size_t key_size_;
  70   const size_t erase_size_;
  71   const size_t min_put_size_;
  72 };
  73
  74 constexpr std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
  75
  76 ChecksumCrc16 checksum;
  77 // For KVS magic value always use a random 32 bit integer rather than a
  78 // human readable 4 bytes. See pw_kvs/format.h for more information.
  79 constexpr EntryFormat default_format{.magic = 0x5b9a341e,
  80                                      .checksum = &checksum};
  81
  82 class EmptyInitializedKvs : public ::testing::Test {
  83  protected:
  84   EmptyInitializedKvs() : kvs_(&test_partition, default_format) {
  85     test_partition.Erase();
  86     ASSERT_EQ(OkStatus(), kvs_.Init());
  87   }
  88
  89   // Intention of this is to put and erase key-val to fill up sectors. It's a
  90   // helper function in testing how KVS handles cases where flash sector is full
  91   // or near full.
  92   void FillKvs(const char* key, size_t size_to_fill) {
  93     constexpr size_t kTestDataSize = 8;
  94     KvsAttributes kvs_attr(std::strlen(key), kTestDataSize);
  95     const size_t kMaxPutSize =
  96         buffer.size() + kvs_attr.ChunkHeaderSize() + kvs_attr.KeySize();
  97
  98     ASSERT_GE(size_to_fill, kvs_attr.MinPutSize() + kvs_attr.EraseSize());
  99
 100     // Saving enough space to perform erase after loop
 101     size_to_fill -= kvs_attr.EraseSize();
 102     // We start with possible small chunk to prevent too small of a Kvs.Put() at
 103     // the end.
 104     size_t chunk_len =
 105         std::max(kvs_attr.MinPutSize(), size_to_fill % buffer.size());
 106     std::memset(buffer.data(), 0, buffer.size());
 107     while (size_to_fill > 0) {
 108       // Changing buffer value so put actually does something
 109       buffer[0] = static_cast<byte>(static_cast<uint8_t>(buffer[0]) + 1);
 110       ASSERT_EQ(OkStatus(),
 111                 kvs_.Put(key,
 112                          std::span(buffer.data(),
 113                                    chunk_len - kvs_attr.ChunkHeaderSize() -
 114                                        kvs_attr.KeySize())));
 115       size_to_fill -= chunk_len;
 116       chunk_len = std::min(size_to_fill, kMaxPutSize);
 117     }
 118     ASSERT_EQ(OkStatus(), kvs_.Delete(key));
 119   }
 120
 121   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
 122 };
 123
 124 }  // namespace
 125
 126 TEST_F(EmptyInitializedKvs, Put_SameKeySameValueRepeatedly_AlignedEntries) {
 127   std::array<char, 8> value{'v', 'a', 'l', 'u', 'e', '6', '7', '\0'};
 128
 129   for (int i = 0; i < 1000; ++i) {
 130     ASSERT_EQ(OkStatus(),
 131               kvs_.Put("The Key!", std::as_bytes(std::span(value))));
 132   }
 133 }
 134
 135 TEST_F(EmptyInitializedKvs, Put_SameKeySameValueRepeatedly_UnalignedEntries) {
 136   std::array<char, 7> value{'v', 'a', 'l', 'u', 'e', '6', '\0'};
 137
 138   for (int i = 0; i < 1000; ++i) {
 139     ASSERT_EQ(OkStatus(),
 140               kvs_.Put("The Key!", std::as_bytes(std::span(value))));
 141   }
 142 }
 143
 144 TEST_F(EmptyInitializedKvs, Put_SameKeyDifferentValuesRepeatedly) {
 145   std::array<char, 10> value{'v', 'a', 'l', 'u', 'e', '6', '7', '8', '9', '\0'};
 146
 147   for (int i = 0; i < 100; ++i) {
 148     for (unsigned size = 0; size < value.size(); ++size) {
 149       ASSERT_EQ(OkStatus(), kvs_.Put("The Key!", i));
 150     }
 151   }
 152 }
 153
 154 TEST_F(EmptyInitializedKvs, PutAndGetByValue_ConvertibleToSpan) {
 155   constexpr float input[] = {1.0, -3.5};
 156   ASSERT_EQ(OkStatus(), kvs_.Put("key", input));
 157
 158   float output[2] = {};
 159   ASSERT_EQ(OkStatus(), kvs_.Get("key", &output));
 160   EXPECT_EQ(input[0], output[0]);
 161   EXPECT_EQ(input[1], output[1]);
 162 }
 163
 164 TEST_F(EmptyInitializedKvs, PutAndGetByValue_Span) {
 165   float input[] = {1.0, -3.5};
 166   ASSERT_EQ(OkStatus(), kvs_.Put("key", std::span(input)));
 167
 168   float output[2] = {};
 169   ASSERT_EQ(OkStatus(), kvs_.Get("key", &output));
 170   EXPECT_EQ(input[0], output[0]);
 171   EXPECT_EQ(input[1], output[1]);
 172 }
 173
 174 TEST_F(EmptyInitializedKvs, PutAndGetByValue_NotConvertibleToSpan) {
 175   struct TestStruct {
 176     float a;
 177     bool b;
 178   };
 179   const TestStruct input{-1234.5, true};
 180
 181   ASSERT_EQ(OkStatus(), kvs_.Put("key", input));
 182
 183   TestStruct output;
 184   ASSERT_EQ(OkStatus(), kvs_.Get("key", &output));
 185   EXPECT_EQ(input.a, output.a);
 186   EXPECT_EQ(input.b, output.b);
 187 }
 188
 189 TEST_F(EmptyInitializedKvs, Get_Simple) {
 190   ASSERT_EQ(OkStatus(),
 191             kvs_.Put("Charles", std::as_bytes(std::span("Mingus"))));
 192
 193   char value[16];
 194   auto result = kvs_.Get("Charles", std::as_writable_bytes(std::span(value)));
 195   EXPECT_EQ(OkStatus(), result.status());
 196   EXPECT_EQ(sizeof("Mingus"), result.size());
 197   EXPECT_STREQ("Mingus", value);
 198 }
 199
 200 TEST_F(EmptyInitializedKvs, Get_WithOffset) {
 201   ASSERT_EQ(OkStatus(),
 202             kvs_.Put("Charles", std::as_bytes(std::span("Mingus"))));
 203
 204   char value[16];
 205   auto result =
 206       kvs_.Get("Charles", std::as_writable_bytes(std::span(value)), 4);
 207   EXPECT_EQ(OkStatus(), result.status());
 208   EXPECT_EQ(sizeof("Mingus") - 4, result.size());
 209   EXPECT_STREQ("us", value);
 210 }
 211
 212 TEST_F(EmptyInitializedKvs, Get_WithOffset_FillBuffer) {
 213   ASSERT_EQ(OkStatus(),
 214             kvs_.Put("Charles", std::as_bytes(std::span("Mingus"))));
 215
 216   char value[4] = {};
 217   auto result =
 218       kvs_.Get("Charles", std::as_writable_bytes(std::span(value, 3)), 1);
 219   EXPECT_EQ(Status::ResourceExhausted(), result.status());
 220   EXPECT_EQ(3u, result.size());
 221   EXPECT_STREQ("ing", value);
 222 }
 223
 224 TEST_F(EmptyInitializedKvs, Get_WithOffset_PastEnd) {
 225   ASSERT_EQ(OkStatus(),
 226             kvs_.Put("Charles", std::as_bytes(std::span("Mingus"))));
 227
 228   char value[16];
 229   auto result = kvs_.Get("Charles",
 230                          std::as_writable_bytes(std::span(value)),
 231                          sizeof("Mingus") + 1);
 232   EXPECT_EQ(Status::OutOfRange(), result.status());
 233   EXPECT_EQ(0u, result.size());
 234 }
 235
 236 TEST_F(EmptyInitializedKvs, GetValue) {
 237   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 238
 239   uint32_t value = 0;
 240   EXPECT_EQ(OkStatus(), kvs_.Get("key", &value));
 241   EXPECT_EQ(uint32_t(0xfeedbeef), value);
 242 }
 243
 244 TEST_F(EmptyInitializedKvs, GetValue_TooSmall) {
 245   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 246
 247   uint8_t value = 0;
 248   EXPECT_EQ(Status::InvalidArgument(), kvs_.Get("key", &value));
 249   EXPECT_EQ(0u, value);
 250 }
 251
 252 TEST_F(EmptyInitializedKvs, GetValue_TooLarge) {
 253   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 254
 255   uint64_t value = 0;
 256   EXPECT_EQ(Status::InvalidArgument(), kvs_.Get("key", &value));
 257   EXPECT_EQ(0u, value);
 258 }
 259
 260 TEST_F(EmptyInitializedKvs, Delete_GetDeletedKey_ReturnsNotFound) {
 261   ASSERT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("123"))));
 262   ASSERT_EQ(OkStatus(), kvs_.Delete("kEy"));
 263
 264   EXPECT_EQ(Status::NotFound(), kvs_.Get("kEy", {}).status());
 265   EXPECT_EQ(Status::NotFound(), kvs_.ValueSize("kEy").status());
 266 }
 267
 268 TEST_F(EmptyInitializedKvs, Delete_AddBackKey_PersistsAfterInitialization) {
 269   ASSERT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("123"))));
 270   ASSERT_EQ(OkStatus(), kvs_.Delete("kEy"));
 271
 272   EXPECT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("45678"))));
 273   char data[6] = {};
 274   ASSERT_EQ(OkStatus(), kvs_.Get("kEy", &data));
 275   EXPECT_STREQ(data, "45678");
 276
 277   // Ensure that the re-added key is still present after reinitialization.
 278   KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> new_kvs(&test_partition,
 279                                                               default_format);
 280   ASSERT_EQ(OkStatus(), new_kvs.Init());
 281
 282   EXPECT_EQ(OkStatus(), new_kvs.Put("kEy", std::as_bytes(std::span("45678"))));
 283   char new_data[6] = {};
 284   EXPECT_EQ(OkStatus(), new_kvs.Get("kEy", &new_data));
 285   EXPECT_STREQ(data, "45678");
 286 }
 287
 288 TEST_F(EmptyInitializedKvs, Delete_AllItems_KvsIsEmpty) {
 289   ASSERT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("123"))));
 290   ASSERT_EQ(OkStatus(), kvs_.Delete("kEy"));
 291
 292   EXPECT_EQ(0u, kvs_.size());
 293   EXPECT_TRUE(kvs_.empty());
 294 }
 295
 296 TEST_F(EmptyInitializedKvs, Collision_WithPresentKey) {
 297   // Both hash to 0x19df36f0.
 298   constexpr std::string_view key1 = "D4";
 299   constexpr std::string_view key2 = "dFU6S";
 300
 301   ASSERT_EQ(OkStatus(), kvs_.Put(key1, 1000));
 302
 303   EXPECT_EQ(Status::AlreadyExists(), kvs_.Put(key2, 999));
 304
 305   int value = 0;
 306   EXPECT_EQ(OkStatus(), kvs_.Get(key1, &value));
 307   EXPECT_EQ(1000, value);
 308
 309   EXPECT_EQ(Status::NotFound(), kvs_.Get(key2, &value));
 310   EXPECT_EQ(Status::NotFound(), kvs_.ValueSize(key2).status());
 311   EXPECT_EQ(Status::NotFound(), kvs_.Delete(key2));
 312 }
 313
 314 TEST_F(EmptyInitializedKvs, Collision_WithDeletedKey) {
 315   // Both hash to 0x4060f732.
 316   constexpr std::string_view key1 = "1U2";
 317   constexpr std::string_view key2 = "ahj9d";
 318
 319   ASSERT_EQ(OkStatus(), kvs_.Put(key1, 1000));
 320   ASSERT_EQ(OkStatus(), kvs_.Delete(key1));
 321
 322   // key2 collides with key1's tombstone.
 323   EXPECT_EQ(Status::AlreadyExists(), kvs_.Put(key2, 999));
 324
 325   int value = 0;
 326   EXPECT_EQ(Status::NotFound(), kvs_.Get(key1, &value));
 327
 328   EXPECT_EQ(Status::NotFound(), kvs_.Get(key2, &value));
 329   EXPECT_EQ(Status::NotFound(), kvs_.ValueSize(key2).status());
 330   EXPECT_EQ(Status::NotFound(), kvs_.Delete(key2));
 331 }
 332
 333 TEST_F(EmptyInitializedKvs, Iteration_Empty_ByReference) {
 334   for (const KeyValueStore::Item& entry : kvs_) {
 335     FAIL();  // The KVS is empty; this shouldn't execute.
 336     static_cast<void>(entry);
 337   }
 338 }
 339
 340 TEST_F(EmptyInitializedKvs, Iteration_Empty_ByValue) {
 341   for (KeyValueStore::Item entry : kvs_) {
 342     FAIL();  // The KVS is empty; this shouldn't execute.
 343     static_cast<void>(entry);
 344   }
 345 }
 346
 347 TEST_F(EmptyInitializedKvs, Iteration_OneItem) {
 348   ASSERT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("123"))));
 349
 350   for (KeyValueStore::Item entry : kvs_) {
 351     EXPECT_STREQ(entry.key(), "kEy");  // Make sure null-terminated.
 352
 353     char temp[sizeof("123")] = {};
 354     EXPECT_EQ(OkStatus(), entry.Get(&temp));
 355     EXPECT_STREQ("123", temp);
 356   }
 357 }
 358
 359 TEST_F(EmptyInitializedKvs, Iteration_GetWithOffset) {
 360   ASSERT_EQ(OkStatus(), kvs_.Put("key", std::as_bytes(std::span("not bad!"))));
 361
 362   for (KeyValueStore::Item entry : kvs_) {
 363     char temp[5];
 364     auto result = entry.Get(std::as_writable_bytes(std::span(temp)), 4);
 365     EXPECT_EQ(OkStatus(), result.status());
 366     EXPECT_EQ(5u, result.size());
 367     EXPECT_STREQ("bad!", temp);
 368   }
 369 }
 370
 371 TEST_F(EmptyInitializedKvs, Iteration_GetValue) {
 372   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 373
 374   for (KeyValueStore::Item entry : kvs_) {
 375     uint32_t value = 0;
 376     EXPECT_EQ(OkStatus(), entry.Get(&value));
 377     EXPECT_EQ(uint32_t(0xfeedbeef), value);
 378   }
 379 }
 380
 381 TEST_F(EmptyInitializedKvs, Iteration_GetValue_TooSmall) {
 382   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 383
 384   for (KeyValueStore::Item entry : kvs_) {
 385     uint8_t value = 0;
 386     EXPECT_EQ(Status::InvalidArgument(), entry.Get(&value));
 387     EXPECT_EQ(0u, value);
 388   }
 389 }
 390
 391 TEST_F(EmptyInitializedKvs, Iteration_GetValue_TooLarge) {
 392   ASSERT_EQ(OkStatus(), kvs_.Put("key", uint32_t(0xfeedbeef)));
 393
 394   for (KeyValueStore::Item entry : kvs_) {
 395     uint64_t value = 0;
 396     EXPECT_EQ(Status::InvalidArgument(), entry.Get(&value));
 397     EXPECT_EQ(0u, value);
 398   }
 399 }
 400
 401 TEST_F(EmptyInitializedKvs, Iteration_EmptyAfterDeletion) {
 402   ASSERT_EQ(OkStatus(), kvs_.Put("kEy", std::as_bytes(std::span("123"))));
 403   ASSERT_EQ(OkStatus(), kvs_.Delete("kEy"));
 404
 405   for (KeyValueStore::Item entry : kvs_) {
 406     static_cast<void>(entry);
 407     FAIL();
 408   }
 409 }
 410
 411 TEST_F(EmptyInitializedKvs, FuzzTest) {
 412   if (test_partition.sector_size_bytes() < 4 * 1024 ||
 413       test_partition.sector_count() < 4) {
 414     PW_LOG_INFO("Sectors too small, skipping test.");
 415     return;  // TODO: Test could be generalized
 416   }
 417   const char* key1 = "Buf1";
 418   const char* key2 = "Buf2";
 419   const size_t kLargestBufSize = 3 * 1024;
 420   static byte buf1[kLargestBufSize];
 421   static byte buf2[kLargestBufSize];
 422   std::memset(buf1, 1, sizeof(buf1));
 423   std::memset(buf2, 2, sizeof(buf2));
 424
 425   // Start with things in KVS
 426   ASSERT_EQ(OkStatus(), kvs_.Put(key1, buf1));
 427   ASSERT_EQ(OkStatus(), kvs_.Put(key2, buf2));
 428   for (size_t j = 0; j < keys.size(); j++) {
 429     ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
 430   }
 431
 432   for (size_t i = 0; i < 100; i++) {
 433     // Vary two sizes
 434     size_t size1 = (kLargestBufSize) / (i + 1);
 435     size_t size2 = (kLargestBufSize) / (100 - i);
 436     for (size_t j = 0; j < 50; j++) {
 437       // Rewrite a single key many times, can fill up a sector
 438       ASSERT_EQ(OkStatus(), kvs_.Put("some_data", j));
 439     }
 440     // Delete and re-add everything
 441     ASSERT_EQ(OkStatus(), kvs_.Delete(key1));
 442     ASSERT_EQ(OkStatus(), kvs_.Put(key1, std::span(buf1, size1)));
 443     ASSERT_EQ(OkStatus(), kvs_.Delete(key2));
 444     ASSERT_EQ(OkStatus(), kvs_.Put(key2, std::span(buf2, size2)));
 445     for (size_t j = 0; j < keys.size(); j++) {
 446       ASSERT_EQ(OkStatus(), kvs_.Delete(keys[j]));
 447       ASSERT_EQ(OkStatus(), kvs_.Put(keys[j], j));
 448     }
 449
 450     // Re-enable and verify
 451     ASSERT_EQ(OkStatus(), kvs_.Init());
 452     static byte buf[4 * 1024];
 453     ASSERT_EQ(OkStatus(), kvs_.Get(key1, std::span(buf, size1)).status());
 454     ASSERT_EQ(std::memcmp(buf, buf1, size1), 0);
 455     ASSERT_EQ(OkStatus(), kvs_.Get(key2, std::span(buf, size2)).status());
 456     ASSERT_EQ(std::memcmp(buf2, buf2, size2), 0);
 457     for (size_t j = 0; j < keys.size(); j++) {
 458       size_t ret = 1000;
 459       ASSERT_EQ(OkStatus(), kvs_.Get(keys[j], &ret));
 460       ASSERT_EQ(ret, j);
 461     }
 462   }
 463 }
 464
 465 TEST_F(EmptyInitializedKvs, Basic) {
 466   // Add some data
 467   uint8_t value1 = 0xDA;
 468   ASSERT_EQ(
 469       OkStatus(),
 470       kvs_.Put(keys[0], std::as_bytes(std::span(&value1, sizeof(value1)))));
 471
 472   uint32_t value2 = 0xBAD0301f;
 473   ASSERT_EQ(OkStatus(), kvs_.Put(keys[1], value2));
 474
 475   // Verify data
 476   uint32_t test2;
 477   EXPECT_EQ(OkStatus(), kvs_.Get(keys[1], &test2));
 478   uint8_t test1;
 479   ASSERT_EQ(OkStatus(), kvs_.Get(keys[0], &test1));
 480
 481   EXPECT_EQ(test1, value1);
 482   EXPECT_EQ(test2, value2);
 483
 484   // Delete a key
 485   EXPECT_EQ(OkStatus(), kvs_.Delete(keys[0]));
 486
 487   // Verify it was erased
 488   EXPECT_EQ(kvs_.Get(keys[0], &test1), Status::NotFound());
 489   test2 = 0;
 490   ASSERT_EQ(OkStatus(),
 491             kvs_.Get(keys[1],
 492                      std::span(reinterpret_cast<byte*>(&test2), sizeof(test2)))
 493                 .status());
 494   EXPECT_EQ(test2, value2);
 495
 496   // Delete other key
 497   kvs_.Delete(keys[1]);
 498
 499   // Verify it was erased
 500   EXPECT_EQ(kvs_.size(), 0u);
 501 }
 502
 503 }  // namespace pw::kvs