third_party/pigweed/repo/pw_kvs/entry_cache_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 "pw_kvs/internal/entry_cache.h"
  16
  17 #include "gtest/gtest.h"
  18 #include "pw_bytes/array.h"
  19 #include "pw_kvs/fake_flash_memory.h"
  20 #include "pw_kvs/flash_memory.h"
  21 #include "pw_kvs/internal/hash.h"
  22 #include "pw_kvs/internal/key_descriptor.h"
  23
  24 namespace pw::kvs::internal {
  25 namespace {
  26
  27 using std::byte;
  28
  29 class EmptyEntryCache : public ::testing::Test {
  30  protected:
  31   static constexpr size_t kMaxEntries = 32;
  32   static constexpr size_t kRedundancy = 3;
  33
  34   EmptyEntryCache() : entries_(descriptors_, addresses_, kRedundancy) {}
  35
  36   Vector<KeyDescriptor, kMaxEntries> descriptors_;
  37   EntryCache::AddressList<kMaxEntries, kRedundancy> addresses_;
  38
  39   EntryCache entries_;
  40 };
  41
  42 constexpr char kTheKey[] = "The Key";
  43
  44 constexpr KeyDescriptor kDescriptor = {.key_hash = Hash(kTheKey),
  45                                        .transaction_id = 123,
  46                                        .state = EntryState::kValid};
  47
  48 TEST_F(EmptyEntryCache, AddNew) {
  49   EntryMetadata metadata = entries_.AddNew(kDescriptor, 5);
  50   EXPECT_EQ(kDescriptor.key_hash, metadata.hash());
  51   EXPECT_EQ(kDescriptor.transaction_id, metadata.transaction_id());
  52   EXPECT_EQ(kDescriptor.state, metadata.state());
  53
  54   EXPECT_EQ(5u, metadata.first_address());
  55   EXPECT_EQ(1u, metadata.addresses().size());
  56 }
  57
  58 TEST_F(EmptyEntryCache, EntryMetadata_AddNewAddress) {
  59   EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
  60
  61   metadata.AddNewAddress(999);
  62
  63   EXPECT_EQ(2u, metadata.addresses().size());
  64   EXPECT_EQ(100u, metadata.first_address());
  65   EXPECT_EQ(100u, metadata.addresses()[0]);
  66   EXPECT_EQ(999u, metadata.addresses()[1]);
  67 }
  68
  69 TEST_F(EmptyEntryCache, EntryMetadata_Reset) {
  70   EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
  71   metadata.AddNewAddress(999);
  72
  73   metadata.Reset(
  74       {.key_hash = 987, .transaction_id = 5, .state = EntryState::kDeleted},
  75       8888);
  76
  77   EXPECT_EQ(987u, metadata.hash());
  78   EXPECT_EQ(5u, metadata.transaction_id());
  79   EXPECT_EQ(EntryState::kDeleted, metadata.state());
  80   EXPECT_EQ(1u, metadata.addresses().size());
  81   EXPECT_EQ(8888u, metadata.first_address());
  82   EXPECT_EQ(8888u, metadata.addresses()[0]);
  83 }
  84
  85 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry) {
  86   ASSERT_EQ(OkStatus(),
  87             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
  88
  89   EXPECT_EQ(1u, entries_.present_entries());
  90
  91   for (const EntryMetadata& entry : entries_) {
  92     EXPECT_EQ(1000u, entry.first_address());
  93     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
  94     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
  95   }
  96 }
  97
  98 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry_Full) {
  99   for (uint32_t i = 0; i < kMaxEntries; ++i) {
 100     ASSERT_EQ(  // Fill up the cache
 101         OkStatus(),
 102         entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
 103   }
 104   ASSERT_EQ(kMaxEntries, entries_.total_entries());
 105   ASSERT_TRUE(entries_.full());
 106
 107   EXPECT_EQ(Status::ResourceExhausted(),
 108             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1));
 109   EXPECT_EQ(kMaxEntries, entries_.total_entries());
 110 }
 111
 112 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_UpdatedEntry) {
 113   KeyDescriptor kd = kDescriptor;
 114   kd.transaction_id += 3;
 115
 116   ASSERT_EQ(OkStatus(), entries_.AddNewOrUpdateExisting(kd, 3210, 2000));
 117
 118   EXPECT_EQ(1u, entries_.present_entries());
 119
 120   for (const EntryMetadata& entry : entries_) {
 121     EXPECT_EQ(3210u, entry.first_address());
 122     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
 123     EXPECT_EQ(kDescriptor.transaction_id + 3, entry.transaction_id());
 124   }
 125 }
 126
 127 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntry) {
 128   ASSERT_EQ(OkStatus(),
 129             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
 130   ASSERT_EQ(OkStatus(),
 131             entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
 132   ASSERT_EQ(OkStatus(),
 133             entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));
 134
 135   // Duplicates beyond the redundancy are ignored.
 136   ASSERT_EQ(OkStatus(),
 137             entries_.AddNewOrUpdateExisting(kDescriptor, 9000, 2000));
 138
 139   EXPECT_EQ(1u, entries_.present_entries());
 140
 141   for (const EntryMetadata& entry : entries_) {
 142     EXPECT_EQ(3u, entry.addresses().size());
 143     EXPECT_EQ(1000u, entry.addresses()[0]);
 144     EXPECT_EQ(3000u, entry.addresses()[1]);
 145     EXPECT_EQ(7000u, entry.addresses()[2]);
 146
 147     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
 148     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
 149   }
 150 }
 151
 152 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntryInSameSector) {
 153   ASSERT_EQ(OkStatus(),
 154             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
 155   EXPECT_EQ(Status::DataLoss(),
 156             entries_.AddNewOrUpdateExisting(kDescriptor, 1950, 1000));
 157
 158   EXPECT_EQ(1u, entries_.present_entries());
 159
 160   for (const EntryMetadata& entry : entries_) {
 161     EXPECT_EQ(1u, entry.addresses().size());
 162     EXPECT_EQ(1000u, entry.addresses()[0]);
 163
 164     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
 165     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
 166   }
 167 }
 168
 169 TEST_F(EmptyEntryCache, Iterator_MutableFromConst_CanModify) {
 170   entries_.AddNew(kDescriptor, 1);
 171   EntryCache::iterator it = static_cast<const EntryCache&>(entries_).begin();
 172
 173   static_assert(kRedundancy > 1);
 174   it->AddNewAddress(1234);
 175
 176   EXPECT_EQ(1u, it->first_address());
 177   EXPECT_EQ(1u, (*it).addresses()[0]);
 178   EXPECT_EQ(1234u, it->addresses()[1]);
 179 }
 180
 181 TEST_F(EmptyEntryCache, Iterator_Const) {
 182   entries_.AddNew(kDescriptor, 99);
 183   EntryCache::const_iterator it = entries_.cbegin();
 184
 185   EXPECT_EQ(99u, (*it).first_address());
 186   EXPECT_EQ(99u, it->first_address());
 187 }
 188
 189 TEST_F(EmptyEntryCache, Iterator_Const_CanBeAssignedFromMutable) {
 190   entries_.AddNew(kDescriptor, 99);
 191   EntryCache::const_iterator it = entries_.begin();
 192
 193   EXPECT_EQ(99u, (*it).first_address());
 194   EXPECT_EQ(99u, it->first_address());
 195 }
 196
 197 constexpr size_t kSectorSize = 64;
 198 constexpr uint32_t kMagic = 0xa14ae726;
 199 // For KVS entry magic value always use a random 32 bit integer rather than a
 200 // human readable 4 bytes. See pw_kvs/format.h for more information.
 201 constexpr auto kTheEntry =
 202     bytes::Concat(uint32_t(kMagic),              // magic
 203                   uint32_t(0),                   // checksum
 204                   uint8_t(0),                    // alignment (16 B)
 205                   uint8_t(sizeof(kTheKey) - 1),  // key length
 206                   uint16_t(0),                   // value size
 207                   uint32_t(123),                 // transaction ID
 208                   bytes::String(kTheKey));
 209 constexpr std::array<byte, kSectorSize - kTheEntry.size() % kSectorSize>
 210     kPadding1{};
 211 constexpr size_t kSize1 = kTheEntry.size() + kPadding1.size();
 212
 213 constexpr char kCollision1[] = "9FDC";
 214 constexpr char kCollision2[] = "axzzK";
 215
 216 // For KVS entry magic value always use a random 32 bit integer rather than a
 217 // human readable 4 bytes. See pw_kvs/format.h for more information.
 218 constexpr auto kCollisionEntry =
 219     bytes::Concat(uint32_t(kMagic),                  // magic
 220                   uint32_t(0),                       // checksum
 221                   uint8_t(0),                        // alignment (16 B)
 222                   uint8_t(sizeof(kCollision1) - 1),  // key length
 223                   uint16_t(0),                       // value size
 224                   uint32_t(123),                     // transaction ID
 225                   bytes::String(kCollision1));
 226 constexpr std::array<byte, kSectorSize - kCollisionEntry.size() % kSectorSize>
 227     kPadding2{};
 228 constexpr size_t kSize2 = kCollisionEntry.size() + kPadding2.size();
 229
 230 // For KVS entry magic value always use a random 32 bit integer rather than a
 231 // human readable 4 bytes. See pw_kvs/format.h for more information.
 232 constexpr auto kDeletedEntry =
 233     bytes::Concat(uint32_t(kMagic),                 // magic
 234                   uint32_t(0),                      // checksum
 235                   uint8_t(0),                       // alignment (16 B)
 236                   uint8_t(sizeof("delorted") - 1),  // key length
 237                   uint16_t(0xffff),                 // value size (deleted)
 238                   uint32_t(123),                    // transaction ID
 239                   bytes::String("delorted"));
 240 constexpr std::array<byte, kSectorSize - kDeletedEntry.size() % kSectorSize>
 241     kPadding3{};
 242
 243 // For KVS entry magic value always use a random 32 bit integer rather than a
 244 // human readable 4 bytes. See pw_kvs/format.h for more information.
 245 constexpr EntryFormat kFormat{.magic = uint32_t(kMagic), .checksum = nullptr};
 246
 247 class InitializedEntryCache : public EmptyEntryCache {
 248  protected:
 249   static_assert(Hash(kCollision1) == Hash(kCollision2));
 250
 251   InitializedEntryCache()
 252       : flash_(bytes::Concat(kTheEntry,
 253                              kPadding1,
 254                              kTheEntry,
 255                              kPadding1,
 256                              kCollisionEntry,
 257                              kPadding2,
 258                              kDeletedEntry,
 259                              kPadding3)),
 260         partition_(&flash_),
 261         sectors_(sector_descriptors_, partition_, nullptr),
 262         format_(kFormat) {
 263     sectors_.Reset();
 264     size_t address = 0;
 265     auto entry = entries_.AddNew(kDescriptor, address);
 266
 267     address += kSize1;
 268     entry.AddNewAddress(kSize1);
 269
 270     address += kSize1;
 271     entries_.AddNew({.key_hash = Hash(kCollision1),
 272                      .transaction_id = 125,
 273                      .state = EntryState::kDeleted},
 274                     address);
 275
 276     address += kSize2;
 277     entries_.AddNew({.key_hash = Hash("delorted"),
 278                      .transaction_id = 256,
 279                      .state = EntryState::kDeleted},
 280                     address);
 281   }
 282
 283   void CheckForCorruptSectors(SectorDescriptor* sector1 = nullptr,
 284                               SectorDescriptor* sector2 = nullptr) {
 285     for (const auto& sector : sectors_) {
 286       bool expect_corrupt =
 287           ((sector1 && &sector == sector1) || (sector2 && &sector == sector2));
 288       EXPECT_EQ(expect_corrupt, sector.corrupt());
 289     }
 290   }
 291
 292   static constexpr size_t kTotalSectors = 128;
 293   FakeFlashMemoryBuffer<kSectorSize, kTotalSectors> flash_;
 294   FlashPartition partition_;
 295
 296   Vector<SectorDescriptor, kTotalSectors> sector_descriptors_;
 297   Sectors sectors_;
 298
 299   EntryFormats format_;
 300 };
 301
 302 TEST_F(InitializedEntryCache, EntryCounts) {
 303   EXPECT_EQ(3u, entries_.total_entries());
 304   EXPECT_EQ(1u, entries_.present_entries());
 305   EXPECT_EQ(kMaxEntries, entries_.max_entries());
 306 }
 307
 308 TEST_F(InitializedEntryCache, Reset_ClearsEntryCounts) {
 309   entries_.Reset();
 310
 311   EXPECT_EQ(0u, entries_.total_entries());
 312   EXPECT_EQ(0u, entries_.present_entries());
 313   EXPECT_EQ(kMaxEntries, entries_.max_entries());
 314 }
 315
 316 TEST_F(InitializedEntryCache, Find_PresentEntry) {
 317   EntryMetadata metadata;
 318
 319   StatusWithSize result =
 320       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
 321
 322   ASSERT_EQ(OkStatus(), result.status());
 323   EXPECT_EQ(0u, result.size());
 324   EXPECT_EQ(Hash(kTheKey), metadata.hash());
 325   EXPECT_EQ(EntryState::kValid, metadata.state());
 326   CheckForCorruptSectors();
 327 }
 328
 329 TEST_F(InitializedEntryCache, Find_PresentEntryWithSingleReadError) {
 330   // Inject 2 read errors so that the initial key read and the follow-up full
 331   // read of the first entry fail.
 332   flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 2));
 333
 334   EntryMetadata metadata;
 335
 336   StatusWithSize result =
 337       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
 338
 339   ASSERT_EQ(OkStatus(), result.status());
 340   EXPECT_EQ(1u, result.size());
 341   EXPECT_EQ(Hash(kTheKey), metadata.hash());
 342   EXPECT_EQ(EntryState::kValid, metadata.state());
 343   CheckForCorruptSectors(&sectors_.FromAddress(0));
 344 }
 345
 346 TEST_F(InitializedEntryCache, Find_PresentEntryWithMultiReadError) {
 347   flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 4));
 348
 349   EntryMetadata metadata;
 350
 351   StatusWithSize result =
 352       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);
 353
 354   ASSERT_EQ(Status::DataLoss(), result.status());
 355   EXPECT_EQ(1u, result.size());
 356   CheckForCorruptSectors(&sectors_.FromAddress(0),
 357                          &sectors_.FromAddress(kSize1));
 358 }
 359
 360 TEST_F(InitializedEntryCache, Find_DeletedEntry) {
 361   EntryMetadata metadata;
 362
 363   StatusWithSize result =
 364       entries_.Find(partition_, sectors_, format_, "delorted", &metadata);
 365
 366   ASSERT_EQ(OkStatus(), result.status());
 367   EXPECT_EQ(0u, result.size());
 368   EXPECT_EQ(Hash("delorted"), metadata.hash());
 369   EXPECT_EQ(EntryState::kDeleted, metadata.state());
 370   CheckForCorruptSectors();
 371 }
 372
 373 TEST_F(InitializedEntryCache, Find_MissingEntry) {
 374   EntryMetadata metadata;
 375
 376   StatusWithSize result =
 377       entries_.Find(partition_, sectors_, format_, "3.141", &metadata);
 378
 379   ASSERT_EQ(Status::NotFound(), result.status());
 380   EXPECT_EQ(0u, result.size());
 381   CheckForCorruptSectors();
 382 }
 383
 384 TEST_F(InitializedEntryCache, Find_Collision) {
 385   EntryMetadata metadata;
 386
 387   StatusWithSize result =
 388       entries_.Find(partition_, sectors_, format_, kCollision2, &metadata);
 389   EXPECT_EQ(Status::AlreadyExists(), result.status());
 390   EXPECT_EQ(0u, result.size());
 391   CheckForCorruptSectors();
 392 }
 393
 394 }  // namespace
 395 }  // namespace pw::kvs::internal