pw_kvs: EntryCache tests
- Expand the EntryCache tests.
- Remove unused kWorkingBufferSize variable
- Remove EntryMetadata::deleted() since it isn't widely used and
overlaps with EntryMetadata::state().
Change-Id: Ic18622acf5ce8f3b303fe9ddd15659163dc2ef55
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index 9700013..76bef4f 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -122,7 +122,10 @@
pw_cc_test(
name = "entry_cache_test",
srcs = ["entry_cache_test.cc"],
- deps = [":pw_kvs"],
+ deps = [
+ ":pw_kvs",
+ ":test_utils",
+ ],
)
pw_cc_test(
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index b682455..9c95799 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -133,7 +133,10 @@
}
pw_test("entry_cache_test") {
- deps = [ ":pw_kvs" ]
+ deps = [
+ ":pw_kvs",
+ ":test_utils",
+ ]
sources = [ "entry_cache_test.cc" ]
}
diff --git a/pw_kvs/entry_cache.cc b/pw_kvs/entry_cache.cc
index eec4044..64f3bec 100644
--- a/pw_kvs/entry_cache.cc
+++ b/pw_kvs/entry_cache.cc
@@ -73,7 +73,7 @@
// If the key's hash collides with an existing key or if the key is deleted,
// treat it as if it is not in the KVS.
if (status == Status::ALREADY_EXISTS ||
- (status.ok() && metadata->deleted())) {
+ (status.ok() && metadata->state() == EntryState::kDeleted)) {
return Status::NOT_FOUND;
}
return status;
@@ -169,7 +169,6 @@
for (size_t i = 0; i < redundancy(); ++i) {
if (existing[i] == kNoAddress) {
existing[i] = address;
- addresses(descriptor_index);
return;
}
}
diff --git a/pw_kvs/entry_cache_test.cc b/pw_kvs/entry_cache_test.cc
index df1ae90..3b9d1a1 100644
--- a/pw_kvs/entry_cache_test.cc
+++ b/pw_kvs/entry_cache_test.cc
@@ -15,31 +15,274 @@
#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, 32> descriptors_;
- EntryCache::AddressList<32, kRedundancy> addresses_;
+ 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(
- {.key_hash = 1, .transaction_id = 123, .state = EntryState::kValid}, 5);
- EXPECT_EQ(1u, metadata.hash());
- EXPECT_EQ(123u, metadata.transaction_id());
+ 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());
}
-// TODO(hepler): Expand these tests!
+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
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 2ad68fa..091c244 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -173,8 +173,8 @@
DBG("Second pass: Count valid bytes in each sector");
Address newest_key = 0;
- // For every valid key, increment the valid bytes for that sector.
-
+ // For every valid entry, count the valid bytes in that sector. Track which
+ // entry has the newest transaction ID for initializing last_new_sector_.
for (const EntryMetadata& metadata : entry_cache_) {
for (Address address : metadata.addresses()) {
Entry entry;
@@ -364,7 +364,7 @@
KeyValueStore::iterator& KeyValueStore::iterator::operator++() {
// Skip to the next entry that is valid (not deleted).
while (++item_.iterator_ != item_.kvs_.entry_cache_.end() &&
- item_.iterator_->deleted()) {
+ item_.iterator_->state() != EntryState::kValid) {
}
return *this;
}
@@ -372,7 +372,8 @@
KeyValueStore::iterator KeyValueStore::begin() const {
internal::EntryCache::iterator cache_iterator = entry_cache_.begin();
// Skip over any deleted entries at the start of the descriptor list.
- while (cache_iterator != entry_cache_.end() && cache_iterator->deleted()) {
+ while (cache_iterator != entry_cache_.end() &&
+ cache_iterator->state() != EntryState::kValid) {
++cache_iterator;
}
return iterator(*this, cache_iterator);
@@ -1053,7 +1054,7 @@
DBG("Key descriptors: count %zu", entry_cache_.total_entries());
for (auto& metadata : entry_cache_) {
DBG(" - Key: %s, hash %#zx, transaction ID %zu, first address %#zx",
- metadata.deleted() ? "Deleted" : "Valid",
+ metadata.state() == EntryState::kDeleted ? "Deleted" : "Valid",
static_cast<size_t>(metadata.hash()),
static_cast<size_t>(metadata.transaction_id()),
static_cast<size_t>(metadata.first_address()));
diff --git a/pw_kvs/public/pw_kvs/internal/entry_cache.h b/pw_kvs/public/pw_kvs/internal/entry_cache.h
index 5cbef5c..99c2008 100644
--- a/pw_kvs/public/pw_kvs/internal/entry_cache.h
+++ b/pw_kvs/public/pw_kvs/internal/entry_cache.h
@@ -38,12 +38,10 @@
EntryState state() const { return descriptor_->state; }
- bool deleted() const { return state() == EntryState::kDeleted; }
-
// The first known address of this entry.
uint32_t first_address() const { return addresses_[0]; }
- // All addresses for this entry, including redundant entries.
+ // All addresses for this entry, including redundant entries, if any.
const span<Address>& addresses() const { return addresses_; }
// True if the KeyDesctiptor's transaction ID is newer than the specified ID.
@@ -52,8 +50,8 @@
return transaction_id() > other_transaction_id;
}
- // Adds a new address to the entry metadata. MUST NOT be called more than
- // allowed by the redundancy.
+ // Adds a new address to the entry metadata. MUST NOT be called more times
+ // than allowed by the redundancy.
void AddNewAddress(Address address) {
addresses_[addresses_.size()] = address;
addresses_ = span(addresses_.begin(), addresses_.size() + 1);
@@ -92,7 +90,7 @@
addresses_(addresses),
redundancy_(redundancy) {}
- // Clears all
+ // Clears all KeyDescriptors.
void Reset() { descriptors_.clear(); }
// Finds the metadata for an entry matching a particular key. Searches for a
@@ -121,7 +119,8 @@
std::string_view key,
EntryMetadata* metadata) const;
- // Adds a new descriptor to the descriptor list. Must NOT be full!
+ // Adds a new descriptor to the descriptor list. The entry MUST be unique and
+ // the EntryCache must NOT be full!
EntryMetadata AddNew(const KeyDescriptor& entry, Address address);
// Adds a new descriptor, overwrites an existing one, or adds an additional
