pw_kvs: EntryCache class
- Allocate space for addresses in the derived KeyValueStore class. This
allows having multiple KeyValueStores with different redundancies,
without any wasted memory.
- Addresses are moved to a contiguous array instead of a Vector,
removing the kMaxEntries * uint32_t bytes of Vector overhead.
- Create the EntryCache and EntryMetadata abstractions. These bring
together KeyDescriptors and their addresses.
- Move functions for finding and updating KeyDescriptors to the
EntryCache and EntryMetadata classes.
- Start EntryCache unit tests. The tests will be expanded in future CLs.
Change-Id: I726ec198c0c4188086357ac6df944a7670c30000
diff --git a/pw_kvs/entry_cache.cc b/pw_kvs/entry_cache.cc
new file mode 100644
index 0000000..eec4044
--- /dev/null
+++ b/pw_kvs/entry_cache.cc
@@ -0,0 +1,202 @@
+// 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 <cinttypes>
+
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/entry.h"
+#include "pw_kvs/internal/hash.h"
+#include "pw_kvs_private/macros.h"
+#include "pw_log/log.h"
+
+namespace pw::kvs::internal {
+namespace {
+
+using std::string_view;
+
+constexpr FlashPartition::Address kNoAddress = FlashPartition::Address(-1);
+
+} // namespace
+
+void EntryMetadata::Reset(const KeyDescriptor& descriptor, Address address) {
+ *descriptor_ = descriptor;
+
+ addresses_[0] = address;
+ for (size_t i = 1; i < addresses_.size(); ++i) {
+ addresses_[i] = kNoAddress;
+ }
+ addresses_ = addresses_.first(1);
+}
+
+Status EntryCache::Find(FlashPartition& partition,
+ string_view key,
+ EntryMetadata* metadata) const {
+ const uint32_t hash = internal::Hash(key);
+ Entry::KeyBuffer key_buffer;
+
+ for (size_t i = 0; i < descriptors_.size(); ++i) {
+ if (descriptors_[i].key_hash == hash) {
+ TRY(Entry::ReadKey(
+ partition, *first_address(i), key.size(), key_buffer.data()));
+
+ if (key == string_view(key_buffer.data(), key.size())) {
+ PW_LOG_DEBUG("Found match for key hash 0x%08" PRIx32, hash);
+ *metadata = EntryMetadata(descriptors_[i], addresses(i));
+ return Status::OK;
+ } else {
+ PW_LOG_WARN("Found key hash collision for 0x%08" PRIx32, hash);
+ return Status::ALREADY_EXISTS;
+ }
+ }
+ }
+ return Status::NOT_FOUND;
+}
+
+Status EntryCache::FindExisting(FlashPartition& partition,
+ string_view key,
+ EntryMetadata* metadata) const {
+ Status status = Find(partition, key, metadata);
+
+ // 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())) {
+ return Status::NOT_FOUND;
+ }
+ return status;
+}
+
+EntryMetadata EntryCache::AddNew(const KeyDescriptor& descriptor,
+ Address entry_address) {
+ // TODO(hepler): DCHECK(!full());
+ Address* first_address = ResetAddresses(descriptors_.size(), entry_address);
+ descriptors_.push_back(descriptor);
+ return EntryMetadata(descriptors_.back(), span(first_address, 1));
+}
+
+// TODO: This method is the trigger of the O(valid_entries * all_entries) time
+// complexity for reading. At some cost to memory, this could be optimized by
+// using a hash table instead of scanning, but in practice this should be fine
+// for a small number of keys
+Status EntryCache::AddNewOrUpdateExisting(const KeyDescriptor& descriptor,
+ Address address,
+ size_t sector_size_bytes) {
+ // With the new key descriptor, either add it to the descriptor table or
+ // overwrite an existing entry with an older version of the key.
+ const int index = FindIndex(descriptor.key_hash);
+
+ // Write a new entry if there is room.
+ if (index == -1) {
+ if (full()) {
+ return Status::RESOURCE_EXHAUSTED;
+ }
+ AddNew(descriptor, address);
+ return Status::OK;
+ }
+
+ // Existing entry is old; replace the existing entry with the new one.
+ if (descriptor.transaction_id > descriptors_[index].transaction_id) {
+ descriptors_[index] = descriptor;
+ ResetAddresses(index, address);
+ return Status::OK;
+ }
+
+ // If the entries have a duplicate transaction ID, add the new (redundant)
+ // entry to the existing descriptor.
+ if (descriptors_[index].transaction_id == descriptor.transaction_id) {
+ if (descriptors_[index].key_hash != descriptor.key_hash) {
+ PW_LOG_ERROR("Duplicate entry for key 0x%08" PRIx32
+ " with transaction ID %" PRIu32 " has non-matching hash",
+ descriptor.key_hash,
+ descriptor.transaction_id);
+ return Status::DATA_LOSS;
+ }
+
+ // Verify that this entry is not in the same sector as an existing copy of
+ // this same key.
+ for (Address existing_address : addresses(index)) {
+ if (existing_address / sector_size_bytes == address / sector_size_bytes) {
+ PW_LOG_DEBUG("Multiple Redundant entries in same sector %zu",
+ address / sector_size_bytes);
+ return Status::DATA_LOSS;
+ }
+ }
+
+ AddAddressIfRoom(index, address);
+ } else {
+ PW_LOG_DEBUG("Found stale entry when appending; ignoring");
+ }
+ return Status::OK;
+}
+
+size_t EntryCache::present_entries() const {
+ size_t present_entries = 0;
+
+ for (const KeyDescriptor& descriptor : descriptors_) {
+ if (descriptor.state != EntryState::kDeleted) {
+ present_entries += 1;
+ }
+ }
+
+ return present_entries;
+}
+
+int EntryCache::FindIndex(uint32_t key_hash) const {
+ for (size_t i = 0; i < descriptors_.size(); ++i) {
+ if (descriptors_[i].key_hash == key_hash) {
+ return i;
+ }
+ }
+ return -1;
+}
+
+void EntryCache::AddAddressIfRoom(size_t descriptor_index, Address address) {
+ Address* const existing = first_address(descriptor_index);
+
+ for (size_t i = 0; i < redundancy(); ++i) {
+ if (existing[i] == kNoAddress) {
+ existing[i] = address;
+ addresses(descriptor_index);
+ return;
+ }
+ }
+}
+
+span<EntryCache::Address> EntryCache::addresses(size_t descriptor_index) const {
+ Address* const addresses = first_address(descriptor_index);
+
+ size_t size = 0;
+ while (size < redundancy() && addresses[size] != kNoAddress) {
+ size += 1;
+ }
+
+ return span(addresses, size);
+}
+
+EntryCache::Address* EntryCache::ResetAddresses(size_t descriptor_index,
+ Address address) {
+ Address* first = first_address(descriptor_index);
+ *first = address;
+
+ // Clear the additional addresses, if any.
+ for (size_t i = 1; i < redundancy_; ++i) {
+ first[i] = kNoAddress;
+ }
+
+ return first;
+}
+
+} // namespace pw::kvs::internal