blob: eec4044be380e5c75ab8835808ee65166e34487f [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 <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