blob: 01fa3a1fab4dc332a6be1b929217bcaea1d5f59e [file] [log] [blame]
// 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/fake_flash_memory.h"
#include "pw_kvs/flash_memory.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());
}
}
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 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, kSectorSize - kTheEntry.size() % kSectorSize>
kPadding1{};
constexpr size_t kSize1 = kTheEntry.size() + kPadding1.size();
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, kSectorSize - kCollisionEntry.size() % kSectorSize>
kPadding2{};
constexpr size_t kSize2 = kCollisionEntry.size() + kPadding2.size();
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"));
constexpr std::array<byte, kSectorSize - kDeletedEntry.size() % kSectorSize>
kPadding3{};
constexpr EntryFormat kFormat{.magic = uint32_t(12345), .checksum = nullptr};
class InitializedEntryCache : public EmptyEntryCache {
protected:
static_assert(Hash(kCollision1) == Hash(kCollision2));
InitializedEntryCache()
: flash_(AsBytes(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 (auto& sector : sectors_) {
bool expect_corrupt =
(&sector == sector1 || &sector == sector2) ? true : false;
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(Status::OK, 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(Status::OK, 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::DATA_LOSS, 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(Status::OK, 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::NOT_FOUND, 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::ALREADY_EXISTS, result.status());
EXPECT_EQ(0u, result.size());
CheckForCorruptSectors();
}
} // namespace
} // namespace pw::kvs::internal