pw_kvs/entry_cache_test.cc - pigweed/pigweed - Git at Google

 // Copyright 2020 The Pigweed Authors
 //
 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
 // use this file except in compliance with the License. You may obtain a copy of
 // the License at
 //
 //     https://www.apache.org/licenses/LICENSE-2.0
 //
 // Unless required by applicable law or agreed to in writing, software
 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 // License for the specific language governing permissions and limitations under
 // the License.

 #include "pw_kvs/internal/entry_cache.h"

 #include "gtest/gtest.h"
 #include "pw_kvs/flash_memory.h"
 #include "pw_kvs/in_memory_fake_flash.h"
 #include "pw_kvs/internal/hash.h"
 #include "pw_kvs/internal/key_descriptor.h"
 #include "pw_kvs_private/byte_utils.h"

 namespace pw::kvs::internal {
 namespace {

 using std::byte;

 class EmptyEntryCache : public ::testing::Test {
  protected:
   static constexpr size_t kMaxEntries = 32;
   static constexpr size_t kRedundancy = 3;

   EmptyEntryCache() : entries_(descriptors_, addresses_, kRedundancy) {}

   Vector<KeyDescriptor, kMaxEntries> descriptors_;
   EntryCache::AddressList<kMaxEntries, kRedundancy> addresses_;

   EntryCache entries_;
 };

 constexpr char kTheKey[] = "The Key";

 constexpr KeyDescriptor kDescriptor = {.key_hash = Hash(kTheKey),
                                        .transaction_id = 123,
                                        .state = EntryState::kValid};

 TEST_F(EmptyEntryCache, AddNew) {
   EntryMetadata metadata = entries_.AddNew(kDescriptor, 5);
   EXPECT_EQ(kDescriptor.key_hash, metadata.hash());
   EXPECT_EQ(kDescriptor.transaction_id, metadata.transaction_id());
   EXPECT_EQ(kDescriptor.state, metadata.state());

   EXPECT_EQ(5u, metadata.first_address());
   EXPECT_EQ(1u, metadata.addresses().size());
 }

 TEST_F(EmptyEntryCache, EntryMetadata_AddNewAddress) {
   EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);

   metadata.AddNewAddress(999);

   EXPECT_EQ(2u, metadata.addresses().size());
   EXPECT_EQ(100u, metadata.first_address());
   EXPECT_EQ(100u, metadata.addresses()[0]);
   EXPECT_EQ(999u, metadata.addresses()[1]);
 }

 TEST_F(EmptyEntryCache, EntryMetadata_Reset) {
   EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
   metadata.AddNewAddress(999);

   metadata.Reset(
       {.key_hash = 987, .transaction_id = 5, .state = EntryState::kDeleted},
       8888);

   EXPECT_EQ(987u, metadata.hash());
   EXPECT_EQ(5u, metadata.transaction_id());
   EXPECT_EQ(EntryState::kDeleted, metadata.state());
   EXPECT_EQ(1u, metadata.addresses().size());
   EXPECT_EQ(8888u, metadata.first_address());
   EXPECT_EQ(8888u, metadata.addresses()[0]);
 }

 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry) {
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));

   EXPECT_EQ(1u, entries_.present_entries());

   for (const EntryMetadata& entry : entries_) {
     EXPECT_EQ(1000u, entry.first_address());
     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
   }
 }

 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry_Full) {
   for (uint32_t i = 0; i < kMaxEntries; ++i) {
     ASSERT_EQ(  // Fill up the cache
         Status::OK,
         entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
   }
   ASSERT_EQ(kMaxEntries, entries_.total_entries());
   ASSERT_TRUE(entries_.full());

   EXPECT_EQ(Status::RESOURCE_EXHAUSTED,
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1));
   EXPECT_EQ(kMaxEntries, entries_.total_entries());
 }

 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_UpdatedEntry) {
   KeyDescriptor kd = kDescriptor;
   kd.transaction_id += 3;

   ASSERT_EQ(Status::OK, entries_.AddNewOrUpdateExisting(kd, 3210, 2000));

   EXPECT_EQ(1u, entries_.present_entries());

   for (const EntryMetadata& entry : entries_) {
     EXPECT_EQ(3210u, entry.first_address());
     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
     EXPECT_EQ(kDescriptor.transaction_id + 3, entry.transaction_id());
   }
 }

 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntry) {
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));

   // Duplicates beyond the redundancy are ignored.
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 9000, 2000));

   EXPECT_EQ(1u, entries_.present_entries());

   for (const EntryMetadata& entry : entries_) {
     EXPECT_EQ(3u, entry.addresses().size());
     EXPECT_EQ(1000u, entry.addresses()[0]);
     EXPECT_EQ(3000u, entry.addresses()[1]);
     EXPECT_EQ(7000u, entry.addresses()[2]);

     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
   }
 }

 TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntryInSameSector) {
   ASSERT_EQ(Status::OK,
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
   EXPECT_EQ(Status::DATA_LOSS,
             entries_.AddNewOrUpdateExisting(kDescriptor, 1950, 1000));

   EXPECT_EQ(1u, entries_.present_entries());

   for (const EntryMetadata& entry : entries_) {
     EXPECT_EQ(1u, entry.addresses().size());
     EXPECT_EQ(1000u, entry.addresses()[0]);

     EXPECT_EQ(kDescriptor.key_hash, entry.hash());
     EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
   }
 }

 constexpr auto kTheEntry = AsBytes(uint32_t(12345),  // magic
                                    uint32_t(0),      // checksum
                                    uint8_t(0),       // alignment (16 B)
                                    uint8_t(sizeof(kTheKey) - 1),  // key length
                                    uint16_t(0),                   // value size
                                    uint32_t(123),  // transaction ID
                                    ByteStr(kTheKey));
 constexpr std::array<byte, 16 - kTheEntry.size() % 16> kPadding1{};

 constexpr char kCollision1[] = "9FDC";
 constexpr char kCollision2[] = "axzzK";

 constexpr auto kCollisionEntry =
     AsBytes(uint32_t(12345),                   // magic
             uint32_t(0),                       // checksum
             uint8_t(0),                        // alignment (16 B)
             uint8_t(sizeof(kCollision1) - 1),  // key length
             uint16_t(0),                       // value size
             uint32_t(123),                     // transaction ID
             ByteStr(kCollision1));
 constexpr std::array<byte, 16 - kCollisionEntry.size() % 16> kPadding2{};

 constexpr auto kDeletedEntry =
     AsBytes(uint32_t(12345),                  // magic
             uint32_t(0),                      // checksum
             uint8_t(0),                       // alignment (16 B)
             uint8_t(sizeof("delorted") - 1),  // key length
             uint16_t(0xffff),                 // value size (deleted)
             uint32_t(123),                    // transaction ID
             ByteStr("delorted"));

 class InitializedEntryCache : public EmptyEntryCache {
  protected:
   static_assert(Hash(kCollision1) == Hash(kCollision2));

   InitializedEntryCache()
       : flash_(AsBytes(
             kTheEntry, kPadding1, kCollisionEntry, kPadding2, kDeletedEntry)),
         partition_(&flash_) {
     entries_.AddNew(kDescriptor, 0);
     entries_.AddNew({.key_hash = Hash(kCollision1),
                      .transaction_id = 125,
                      .state = EntryState::kDeleted},
                     kTheEntry.size() + kPadding1.size());
     entries_.AddNew({.key_hash = Hash("delorted"),
                      .transaction_id = 256,
                      .state = EntryState::kDeleted},
                     kTheEntry.size() + kPadding1.size() +
                         kCollisionEntry.size() + kPadding2.size());
   }

   FakeFlashBuffer<64, 128> flash_;
   FlashPartition partition_;
 };

 TEST_F(InitializedEntryCache, EntryCounts) {
   EXPECT_EQ(3u, entries_.total_entries());
   EXPECT_EQ(1u, entries_.present_entries());
   EXPECT_EQ(kMaxEntries, entries_.max_entries());
 }

 TEST_F(InitializedEntryCache, Reset_ClearsEntryCounts) {
   entries_.Reset();

   EXPECT_EQ(0u, entries_.total_entries());
   EXPECT_EQ(0u, entries_.present_entries());
   EXPECT_EQ(kMaxEntries, entries_.max_entries());
 }

 TEST_F(InitializedEntryCache, Find_PresentEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::OK, entries_.Find(partition_, kTheKey, &metadata));
   EXPECT_EQ(Hash(kTheKey), metadata.hash());
   EXPECT_EQ(EntryState::kValid, metadata.state());
 }

 TEST_F(InitializedEntryCache, Find_DeletedEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::OK, entries_.Find(partition_, "delorted", &metadata));
   EXPECT_EQ(Hash("delorted"), metadata.hash());
   EXPECT_EQ(EntryState::kDeleted, metadata.state());
 }

 TEST_F(InitializedEntryCache, Find_MissingEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::NOT_FOUND, entries_.Find(partition_, "3.141", &metadata));
 }

 TEST_F(InitializedEntryCache, Find_Collision) {
   EntryMetadata metadata;
   EXPECT_EQ(Status::ALREADY_EXISTS,
             entries_.Find(partition_, kCollision2, &metadata));
 }

 TEST_F(InitializedEntryCache, FindExisting_PresentEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::OK, entries_.FindExisting(partition_, kTheKey, &metadata));
   EXPECT_EQ(Hash(kTheKey), metadata.hash());
 }

 TEST_F(InitializedEntryCache, FindExisting_DeletedEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::NOT_FOUND,
             entries_.FindExisting(partition_, "delorted", &metadata));
 }

 TEST_F(InitializedEntryCache, FindExisting_MissingEntry) {
   EntryMetadata metadata;
   ASSERT_EQ(Status::NOT_FOUND,
             entries_.FindExisting(partition_, "3.141", &metadata));
 }

 TEST_F(InitializedEntryCache, FindExisting_Collision) {
   EntryMetadata metadata;
   EXPECT_EQ(Status::NOT_FOUND,
             entries_.FindExisting(partition_, kCollision2, &metadata));
 }

 }  // namespace
 }  // namespace pw::kvs::internal
	// Copyright 2020 The Pigweed Authors
	//
	// Licensed under the Apache License, Version 2.0 (the "License"); you may not
	// use this file except in compliance with the License. You may obtain a copy of
	// the License at
	//
	// https://www.apache.org/licenses/LICENSE-2.0
	//
	// Unless required by applicable law or agreed to in writing, software
	// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
	// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
	// License for the specific language governing permissions and limitations under
	// the License.

	#include "pw_kvs/internal/entry_cache.h"

	#include "gtest/gtest.h"
	#include "pw_kvs/flash_memory.h"
	#include "pw_kvs/in_memory_fake_flash.h"
	#include "pw_kvs/internal/hash.h"
	#include "pw_kvs/internal/key_descriptor.h"
	#include "pw_kvs_private/byte_utils.h"

	namespace pw::kvs::internal {
	namespace {

	using std::byte;

	class EmptyEntryCache : public ::testing::Test {
	protected:
	static constexpr size_t kMaxEntries = 32;
	static constexpr size_t kRedundancy = 3;

	EmptyEntryCache() : entries_(descriptors_, addresses_, kRedundancy) {}

	Vector<KeyDescriptor, kMaxEntries> descriptors_;
	EntryCache::AddressList<kMaxEntries, kRedundancy> addresses_;

	EntryCache entries_;
	};

	constexpr char kTheKey[] = "The Key";

	constexpr KeyDescriptor kDescriptor = {.key_hash = Hash(kTheKey),
	.transaction_id = 123,
	.state = EntryState::kValid};

	TEST_F(EmptyEntryCache, AddNew) {
	EntryMetadata metadata = entries_.AddNew(kDescriptor, 5);
	EXPECT_EQ(kDescriptor.key_hash, metadata.hash());
	EXPECT_EQ(kDescriptor.transaction_id, metadata.transaction_id());
	EXPECT_EQ(kDescriptor.state, metadata.state());

	EXPECT_EQ(5u, metadata.first_address());
	EXPECT_EQ(1u, metadata.addresses().size());
	}

	TEST_F(EmptyEntryCache, EntryMetadata_AddNewAddress) {
	EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);

	metadata.AddNewAddress(999);

	EXPECT_EQ(2u, metadata.addresses().size());
	EXPECT_EQ(100u, metadata.first_address());
	EXPECT_EQ(100u, metadata.addresses()[0]);
	EXPECT_EQ(999u, metadata.addresses()[1]);
	}

	TEST_F(EmptyEntryCache, EntryMetadata_Reset) {
	EntryMetadata metadata = entries_.AddNew(kDescriptor, 100);
	metadata.AddNewAddress(999);

	metadata.Reset(
	{.key_hash = 987, .transaction_id = 5, .state = EntryState::kDeleted},
	8888);

	EXPECT_EQ(987u, metadata.hash());
	EXPECT_EQ(5u, metadata.transaction_id());
	EXPECT_EQ(EntryState::kDeleted, metadata.state());
	EXPECT_EQ(1u, metadata.addresses().size());
	EXPECT_EQ(8888u, metadata.first_address());
	EXPECT_EQ(8888u, metadata.addresses()[0]);
	}

	TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry) {
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));

	EXPECT_EQ(1u, entries_.present_entries());

	for (const EntryMetadata& entry : entries_) {
	EXPECT_EQ(1000u, entry.first_address());
	EXPECT_EQ(kDescriptor.key_hash, entry.hash());
	EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
	}
	}

	TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_NewEntry_Full) {
	for (uint32_t i = 0; i < kMaxEntries; ++i) {
	ASSERT_EQ( // Fill up the cache
	Status::OK,
	entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
	}
	ASSERT_EQ(kMaxEntries, entries_.total_entries());
	ASSERT_TRUE(entries_.full());

	EXPECT_EQ(Status::RESOURCE_EXHAUSTED,
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1));
	EXPECT_EQ(kMaxEntries, entries_.total_entries());
	}

	TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_UpdatedEntry) {
	KeyDescriptor kd = kDescriptor;
	kd.transaction_id += 3;

	ASSERT_EQ(Status::OK, entries_.AddNewOrUpdateExisting(kd, 3210, 2000));

	EXPECT_EQ(1u, entries_.present_entries());

	for (const EntryMetadata& entry : entries_) {
	EXPECT_EQ(3210u, entry.first_address());
	EXPECT_EQ(kDescriptor.key_hash, entry.hash());
	EXPECT_EQ(kDescriptor.transaction_id + 3, entry.transaction_id());
	}
	}

	TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntry) {
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));

	// Duplicates beyond the redundancy are ignored.
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 9000, 2000));

	EXPECT_EQ(1u, entries_.present_entries());

	for (const EntryMetadata& entry : entries_) {
	EXPECT_EQ(3u, entry.addresses().size());
	EXPECT_EQ(1000u, entry.addresses()[0]);
	EXPECT_EQ(3000u, entry.addresses()[1]);
	EXPECT_EQ(7000u, entry.addresses()[2]);

	EXPECT_EQ(kDescriptor.key_hash, entry.hash());
	EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
	}
	}

	TEST_F(EmptyEntryCache, AddNewOrUpdateExisting_AddDuplicateEntryInSameSector) {
	ASSERT_EQ(Status::OK,
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
	EXPECT_EQ(Status::DATA_LOSS,
	entries_.AddNewOrUpdateExisting(kDescriptor, 1950, 1000));

	EXPECT_EQ(1u, entries_.present_entries());

	for (const EntryMetadata& entry : entries_) {
	EXPECT_EQ(1u, entry.addresses().size());
	EXPECT_EQ(1000u, entry.addresses()[0]);

	EXPECT_EQ(kDescriptor.key_hash, entry.hash());
	EXPECT_EQ(kDescriptor.transaction_id, entry.transaction_id());
	}
	}

	constexpr auto kTheEntry = AsBytes(uint32_t(12345), // magic
	uint32_t(0), // checksum
	uint8_t(0), // alignment (16 B)
	uint8_t(sizeof(kTheKey) - 1), // key length
	uint16_t(0), // value size
	uint32_t(123), // transaction ID
	ByteStr(kTheKey));
	constexpr std::array<byte, 16 - kTheEntry.size() % 16> kPadding1{};

	constexpr char kCollision1[] = "9FDC";
	constexpr char kCollision2[] = "axzzK";

	constexpr auto kCollisionEntry =
	AsBytes(uint32_t(12345), // magic
	uint32_t(0), // checksum
	uint8_t(0), // alignment (16 B)
	uint8_t(sizeof(kCollision1) - 1), // key length
	uint16_t(0), // value size
	uint32_t(123), // transaction ID
	ByteStr(kCollision1));
	constexpr std::array<byte, 16 - kCollisionEntry.size() % 16> kPadding2{};

	constexpr auto kDeletedEntry =
	AsBytes(uint32_t(12345), // magic
	uint32_t(0), // checksum
	uint8_t(0), // alignment (16 B)
	uint8_t(sizeof("delorted") - 1), // key length
	uint16_t(0xffff), // value size (deleted)
	uint32_t(123), // transaction ID
	ByteStr("delorted"));

	class InitializedEntryCache : public EmptyEntryCache {
	protected:
	static_assert(Hash(kCollision1) == Hash(kCollision2));

	InitializedEntryCache()
	: flash_(AsBytes(
	kTheEntry, kPadding1, kCollisionEntry, kPadding2, kDeletedEntry)),
	partition_(&flash_) {
	entries_.AddNew(kDescriptor, 0);
	entries_.AddNew({.key_hash = Hash(kCollision1),
	.transaction_id = 125,
	.state = EntryState::kDeleted},
	kTheEntry.size() + kPadding1.size());
	entries_.AddNew({.key_hash = Hash("delorted"),
	.transaction_id = 256,
	.state = EntryState::kDeleted},
	kTheEntry.size() + kPadding1.size() +
	kCollisionEntry.size() + kPadding2.size());
	}

	FakeFlashBuffer<64, 128> flash_;
	FlashPartition partition_;
	};

	TEST_F(InitializedEntryCache, EntryCounts) {
	EXPECT_EQ(3u, entries_.total_entries());
	EXPECT_EQ(1u, entries_.present_entries());
	EXPECT_EQ(kMaxEntries, entries_.max_entries());
	}

	TEST_F(InitializedEntryCache, Reset_ClearsEntryCounts) {
	entries_.Reset();

	EXPECT_EQ(0u, entries_.total_entries());
	EXPECT_EQ(0u, entries_.present_entries());
	EXPECT_EQ(kMaxEntries, entries_.max_entries());
	}

	TEST_F(InitializedEntryCache, Find_PresentEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::OK, entries_.Find(partition_, kTheKey, &metadata));
	EXPECT_EQ(Hash(kTheKey), metadata.hash());
	EXPECT_EQ(EntryState::kValid, metadata.state());
	}

	TEST_F(InitializedEntryCache, Find_DeletedEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::OK, entries_.Find(partition_, "delorted", &metadata));
	EXPECT_EQ(Hash("delorted"), metadata.hash());
	EXPECT_EQ(EntryState::kDeleted, metadata.state());
	}

	TEST_F(InitializedEntryCache, Find_MissingEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::NOT_FOUND, entries_.Find(partition_, "3.141", &metadata));
	}

	TEST_F(InitializedEntryCache, Find_Collision) {
	EntryMetadata metadata;
	EXPECT_EQ(Status::ALREADY_EXISTS,
	entries_.Find(partition_, kCollision2, &metadata));
	}

	TEST_F(InitializedEntryCache, FindExisting_PresentEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::OK, entries_.FindExisting(partition_, kTheKey, &metadata));
	EXPECT_EQ(Hash(kTheKey), metadata.hash());
	}

	TEST_F(InitializedEntryCache, FindExisting_DeletedEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::NOT_FOUND,
	entries_.FindExisting(partition_, "delorted", &metadata));
	}

	TEST_F(InitializedEntryCache, FindExisting_MissingEntry) {
	EntryMetadata metadata;
	ASSERT_EQ(Status::NOT_FOUND,
	entries_.FindExisting(partition_, "3.141", &metadata));
	}

	TEST_F(InitializedEntryCache, FindExisting_Collision) {
	EntryMetadata metadata;
	EXPECT_EQ(Status::NOT_FOUND,
	entries_.FindExisting(partition_, kCollision2, &metadata));
	}

	} // namespace
	} // namespace pw::kvs::internal