pw_kvs/entry_cache_test.cc - platform/external/pigweed - Gitiles

 // 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_bytes/array.h"
 #include "pw_kvs/fake_flash_memory.h"
 #include "pw_kvs/flash_memory.h"
 #include "pw_kvs/internal/hash.h"
 #include "pw_kvs/internal/key_descriptor.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(OkStatus(),
             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
         OkStatus(),
         entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
   }
   ASSERT_EQ(kMaxEntries, entries_.total_entries());
   ASSERT_TRUE(entries_.full());

   EXPECT_EQ(Status::ResourceExhausted(),
             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(OkStatus(), 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(OkStatus(),
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
   ASSERT_EQ(OkStatus(),
             entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
   ASSERT_EQ(OkStatus(),
             entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));

   // Duplicates beyond the redundancy are ignored.
   ASSERT_EQ(OkStatus(),
             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(OkStatus(),
             entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
   EXPECT_EQ(Status::DataLoss(),
             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());
   }
 }

 TEST_F(EmptyEntryCache, Iterator_MutableFromConst_CanModify) {
   entries_.AddNew(kDescriptor, 1);
   EntryCache::iterator it = static_cast<const EntryCache&>(entries_).begin();

   static_assert(kRedundancy > 1);
   it->AddNewAddress(1234);

   EXPECT_EQ(1u, it->first_address());
   EXPECT_EQ(1u, (*it).addresses()[0]);
   EXPECT_EQ(1234u, it->addresses()[1]);
 }

 TEST_F(EmptyEntryCache, Iterator_Const) {
   entries_.AddNew(kDescriptor, 99);
   EntryCache::const_iterator it = entries_.cbegin();

   EXPECT_EQ(99u, (*it).first_address());
   EXPECT_EQ(99u, it->first_address());
 }

 TEST_F(EmptyEntryCache, Iterator_Const_CanBeAssignedFromMutable) {
   entries_.AddNew(kDescriptor, 99);
   EntryCache::const_iterator it = entries_.begin();

   EXPECT_EQ(99u, (*it).first_address());
   EXPECT_EQ(99u, it->first_address());
 }

 constexpr size_t kSectorSize = 64;
 constexpr uint32_t kMagic = 0xa14ae726;
 // For KVS entry magic value always use a random 32 bit integer rather than a
 // human readable 4 bytes. See pw_kvs/format.h for more information.
 constexpr auto kTheEntry =
     bytes::Concat(uint32_t(kMagic),              // 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
                   bytes::String(kTheKey));
 constexpr std::array<byte, kSectorSize - kTheEntry.size() % kSectorSize>
     kPadding1{};
 constexpr size_t kSize1 = kTheEntry.size() + kPadding1.size();

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

 // For KVS entry magic value always use a random 32 bit integer rather than a
 // human readable 4 bytes. See pw_kvs/format.h for more information.
 constexpr auto kCollisionEntry =
     bytes::Concat(uint32_t(kMagic),                  // 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
                   bytes::String(kCollision1));
 constexpr std::array<byte, kSectorSize - kCollisionEntry.size() % kSectorSize>
     kPadding2{};
 constexpr size_t kSize2 = kCollisionEntry.size() + kPadding2.size();

 // For KVS entry magic value always use a random 32 bit integer rather than a
 // human readable 4 bytes. See pw_kvs/format.h for more information.
 constexpr auto kDeletedEntry =
     bytes::Concat(uint32_t(kMagic),                 // 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
                   bytes::String("delorted"));
 constexpr std::array<byte, kSectorSize - kDeletedEntry.size() % kSectorSize>
     kPadding3{};

 // For KVS entry magic value always use a random 32 bit integer rather than a
 // human readable 4 bytes. See pw_kvs/format.h for more information.
 constexpr EntryFormat kFormat{.magic = uint32_t(kMagic), .checksum = nullptr};

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

   InitializedEntryCache()
       : flash_(bytes::Concat(kTheEntry,
                              kPadding1,
                              kTheEntry,
                              kPadding1,
                              kCollisionEntry,
                              kPadding2,
                              kDeletedEntry,
                              kPadding3)),
         partition_(&flash_),
         sectors_(sector_descriptors_, partition_, nullptr),
         format_(kFormat) {
     sectors_.Reset();
     size_t address = 0;
     auto entry = entries_.AddNew(kDescriptor, address);

     address += kSize1;
     entry.AddNewAddress(kSize1);

     address += kSize1;
     entries_.AddNew({.key_hash = Hash(kCollision1),
                      .transaction_id = 125,
                      .state = EntryState::kDeleted},
                     address);

     address += kSize2;
     entries_.AddNew({.key_hash = Hash("delorted"),
                      .transaction_id = 256,
                      .state = EntryState::kDeleted},
                     address);
   }

   void CheckForCorruptSectors(SectorDescriptor* sector1 = nullptr,
                               SectorDescriptor* sector2 = nullptr) {
     for (const auto& sector : sectors_) {
       bool expect_corrupt =
           ((sector1 && &sector == sector1) || (sector2 && &sector == sector2));
       EXPECT_EQ(expect_corrupt, sector.corrupt());
     }
   }

   static constexpr size_t kTotalSectors = 128;
   FakeFlashMemoryBuffer<kSectorSize, kTotalSectors> flash_;
   FlashPartition partition_;

   Vector<SectorDescriptor, kTotalSectors> sector_descriptors_;
   Sectors sectors_;

   EntryFormats format_;
 };

 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;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

   ASSERT_EQ(OkStatus(), result.status());
   EXPECT_EQ(0u, result.size());
   EXPECT_EQ(Hash(kTheKey), metadata.hash());
   EXPECT_EQ(EntryState::kValid, metadata.state());
   CheckForCorruptSectors();
 }

 TEST_F(InitializedEntryCache, Find_PresentEntryWithSingleReadError) {
   // Inject 2 read errors so that the initial key read and the follow-up full
   // read of the first entry fail.
   flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 2));

   EntryMetadata metadata;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

   ASSERT_EQ(OkStatus(), result.status());
   EXPECT_EQ(1u, result.size());
   EXPECT_EQ(Hash(kTheKey), metadata.hash());
   EXPECT_EQ(EntryState::kValid, metadata.state());
   CheckForCorruptSectors(&sectors_.FromAddress(0));
 }

 TEST_F(InitializedEntryCache, Find_PresentEntryWithMultiReadError) {
   flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 4));

   EntryMetadata metadata;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

   ASSERT_EQ(Status::DataLoss(), result.status());
   EXPECT_EQ(1u, result.size());
   CheckForCorruptSectors(&sectors_.FromAddress(0),
                          &sectors_.FromAddress(kSize1));
 }

 TEST_F(InitializedEntryCache, Find_DeletedEntry) {
   EntryMetadata metadata;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, "delorted", &metadata);

   ASSERT_EQ(OkStatus(), result.status());
   EXPECT_EQ(0u, result.size());
   EXPECT_EQ(Hash("delorted"), metadata.hash());
   EXPECT_EQ(EntryState::kDeleted, metadata.state());
   CheckForCorruptSectors();
 }

 TEST_F(InitializedEntryCache, Find_MissingEntry) {
   EntryMetadata metadata;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, "3.141", &metadata);

   ASSERT_EQ(Status::NotFound(), result.status());
   EXPECT_EQ(0u, result.size());
   CheckForCorruptSectors();
 }

 TEST_F(InitializedEntryCache, Find_Collision) {
   EntryMetadata metadata;

   StatusWithSize result =
       entries_.Find(partition_, sectors_, format_, kCollision2, &metadata);
   EXPECT_EQ(Status::AlreadyExists(), result.status());
   EXPECT_EQ(0u, result.size());
   CheckForCorruptSectors();
 }

 }  // 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_bytes/array.h"
	#include "pw_kvs/fake_flash_memory.h"
	#include "pw_kvs/flash_memory.h"
	#include "pw_kvs/internal/hash.h"
	#include "pw_kvs/internal/key_descriptor.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(OkStatus(),
	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
	OkStatus(),
	entries_.AddNewOrUpdateExisting({i, i, EntryState::kValid}, i, 1));
	}
	ASSERT_EQ(kMaxEntries, entries_.total_entries());
	ASSERT_TRUE(entries_.full());

	EXPECT_EQ(Status::ResourceExhausted(),
	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(OkStatus(), 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(OkStatus(),
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 2000));
	ASSERT_EQ(OkStatus(),
	entries_.AddNewOrUpdateExisting(kDescriptor, 3000, 2000));
	ASSERT_EQ(OkStatus(),
	entries_.AddNewOrUpdateExisting(kDescriptor, 7000, 2000));

	// Duplicates beyond the redundancy are ignored.
	ASSERT_EQ(OkStatus(),
	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(OkStatus(),
	entries_.AddNewOrUpdateExisting(kDescriptor, 1000, 1000));
	EXPECT_EQ(Status::DataLoss(),
	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());
	}
	}

	TEST_F(EmptyEntryCache, Iterator_MutableFromConst_CanModify) {
	entries_.AddNew(kDescriptor, 1);
	EntryCache::iterator it = static_cast<const EntryCache&>(entries_).begin();

	static_assert(kRedundancy > 1);
	it->AddNewAddress(1234);

	EXPECT_EQ(1u, it->first_address());
	EXPECT_EQ(1u, (*it).addresses()[0]);
	EXPECT_EQ(1234u, it->addresses()[1]);
	}

	TEST_F(EmptyEntryCache, Iterator_Const) {
	entries_.AddNew(kDescriptor, 99);
	EntryCache::const_iterator it = entries_.cbegin();

	EXPECT_EQ(99u, (*it).first_address());
	EXPECT_EQ(99u, it->first_address());
	}

	TEST_F(EmptyEntryCache, Iterator_Const_CanBeAssignedFromMutable) {
	entries_.AddNew(kDescriptor, 99);
	EntryCache::const_iterator it = entries_.begin();

	EXPECT_EQ(99u, (*it).first_address());
	EXPECT_EQ(99u, it->first_address());
	}

	constexpr size_t kSectorSize = 64;
	constexpr uint32_t kMagic = 0xa14ae726;
	// For KVS entry magic value always use a random 32 bit integer rather than a
	// human readable 4 bytes. See pw_kvs/format.h for more information.
	constexpr auto kTheEntry =
	bytes::Concat(uint32_t(kMagic), // 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
	bytes::String(kTheKey));
	constexpr std::array<byte, kSectorSize - kTheEntry.size() % kSectorSize>
	kPadding1{};
	constexpr size_t kSize1 = kTheEntry.size() + kPadding1.size();

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

	// For KVS entry magic value always use a random 32 bit integer rather than a
	// human readable 4 bytes. See pw_kvs/format.h for more information.
	constexpr auto kCollisionEntry =
	bytes::Concat(uint32_t(kMagic), // 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
	bytes::String(kCollision1));
	constexpr std::array<byte, kSectorSize - kCollisionEntry.size() % kSectorSize>
	kPadding2{};
	constexpr size_t kSize2 = kCollisionEntry.size() + kPadding2.size();

	// For KVS entry magic value always use a random 32 bit integer rather than a
	// human readable 4 bytes. See pw_kvs/format.h for more information.
	constexpr auto kDeletedEntry =
	bytes::Concat(uint32_t(kMagic), // 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
	bytes::String("delorted"));
	constexpr std::array<byte, kSectorSize - kDeletedEntry.size() % kSectorSize>
	kPadding3{};

	// For KVS entry magic value always use a random 32 bit integer rather than a
	// human readable 4 bytes. See pw_kvs/format.h for more information.
	constexpr EntryFormat kFormat{.magic = uint32_t(kMagic), .checksum = nullptr};

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

	InitializedEntryCache()
	: flash_(bytes::Concat(kTheEntry,
	kPadding1,
	kTheEntry,
	kPadding1,
	kCollisionEntry,
	kPadding2,
	kDeletedEntry,
	kPadding3)),
	partition_(&flash_),
	sectors_(sector_descriptors_, partition_, nullptr),
	format_(kFormat) {
	sectors_.Reset();
	size_t address = 0;
	auto entry = entries_.AddNew(kDescriptor, address);

	address += kSize1;
	entry.AddNewAddress(kSize1);

	address += kSize1;
	entries_.AddNew({.key_hash = Hash(kCollision1),
	.transaction_id = 125,
	.state = EntryState::kDeleted},
	address);

	address += kSize2;
	entries_.AddNew({.key_hash = Hash("delorted"),
	.transaction_id = 256,
	.state = EntryState::kDeleted},
	address);
	}

	void CheckForCorruptSectors(SectorDescriptor* sector1 = nullptr,
	SectorDescriptor* sector2 = nullptr) {
	for (const auto& sector : sectors_) {
	bool expect_corrupt =
	((sector1 && &sector == sector1) \|\| (sector2 && &sector == sector2));
	EXPECT_EQ(expect_corrupt, sector.corrupt());
	}
	}

	static constexpr size_t kTotalSectors = 128;
	FakeFlashMemoryBuffer<kSectorSize, kTotalSectors> flash_;
	FlashPartition partition_;

	Vector<SectorDescriptor, kTotalSectors> sector_descriptors_;
	Sectors sectors_;

	EntryFormats format_;
	};

	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;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

	ASSERT_EQ(OkStatus(), result.status());
	EXPECT_EQ(0u, result.size());
	EXPECT_EQ(Hash(kTheKey), metadata.hash());
	EXPECT_EQ(EntryState::kValid, metadata.state());
	CheckForCorruptSectors();
	}

	TEST_F(InitializedEntryCache, Find_PresentEntryWithSingleReadError) {
	// Inject 2 read errors so that the initial key read and the follow-up full
	// read of the first entry fail.
	flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 2));

	EntryMetadata metadata;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

	ASSERT_EQ(OkStatus(), result.status());
	EXPECT_EQ(1u, result.size());
	EXPECT_EQ(Hash(kTheKey), metadata.hash());
	EXPECT_EQ(EntryState::kValid, metadata.state());
	CheckForCorruptSectors(&sectors_.FromAddress(0));
	}

	TEST_F(InitializedEntryCache, Find_PresentEntryWithMultiReadError) {
	flash_.InjectReadError(FlashError::Unconditional(Status::Internal(), 4));

	EntryMetadata metadata;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, kTheKey, &metadata);

	ASSERT_EQ(Status::DataLoss(), result.status());
	EXPECT_EQ(1u, result.size());
	CheckForCorruptSectors(&sectors_.FromAddress(0),
	&sectors_.FromAddress(kSize1));
	}

	TEST_F(InitializedEntryCache, Find_DeletedEntry) {
	EntryMetadata metadata;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, "delorted", &metadata);

	ASSERT_EQ(OkStatus(), result.status());
	EXPECT_EQ(0u, result.size());
	EXPECT_EQ(Hash("delorted"), metadata.hash());
	EXPECT_EQ(EntryState::kDeleted, metadata.state());
	CheckForCorruptSectors();
	}

	TEST_F(InitializedEntryCache, Find_MissingEntry) {
	EntryMetadata metadata;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, "3.141", &metadata);

	ASSERT_EQ(Status::NotFound(), result.status());
	EXPECT_EQ(0u, result.size());
	CheckForCorruptSectors();
	}

	TEST_F(InitializedEntryCache, Find_Collision) {
	EntryMetadata metadata;

	StatusWithSize result =
	entries_.Find(partition_, sectors_, format_, kCollision2, &metadata);
	EXPECT_EQ(Status::AlreadyExists(), result.status());
	EXPECT_EQ(0u, result.size());
	CheckForCorruptSectors();
	}

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