pw_kvs/entry_cache.cc

// 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.

#define PW_LOG_MODULE_NAME "KVS"

#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::RemoveAddress(Address address_to_remove) {
  // Find the index of the address to remove.
  for (Address& address : addresses_) {
    if (address == address_to_remove) {
      // Move the address at the back of the list to the slot of the address
      // being removed. Do this unconditionally, even if the address to remove
      // is the last slot since the logic still works.
      address = addresses_.back();

      // Remove the back entry of the address list.
      addresses_.back() = kNoAddress;
      addresses_ = std::span(addresses_.begin(), addresses_.size() - 1);
      break;
    }
  }
}

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);
}

StatusWithSize EntryCache::Find(FlashPartition& partition,
                                const Sectors& sectors,
                                const EntryFormats& formats,
                                string_view key,
                                EntryMetadata* metadata) const {
  const uint32_t hash = internal::Hash(key);
  Entry::KeyBuffer key_buffer;
  bool error_detected = false;

  for (size_t i = 0; i < descriptors_.size(); ++i) {
    if (descriptors_[i].key_hash == hash) {
      bool key_found = false;
      string_view read_key;

      for (Address address : addresses(i)) {
        Status read_result =
            Entry::ReadKey(partition, address, key.size(), key_buffer.data());

        read_key = string_view(key_buffer.data(), key.size());

        if (read_result.ok() && hash == internal::Hash(read_key)) {
          key_found = true;
          break;
        } else {
          // A hash mismatch can be caused by reading invalid data or a key hash
          // collision of keys with differing size. To verify the data read from
          // flash is good, validate the entry.
          Entry entry;
          read_result = Entry::Read(partition, address, formats, &entry);
          if (read_result.ok() && entry.VerifyChecksumInFlash().ok()) {
            key_found = true;
            break;
          }

          PW_LOG_WARN(
              "   Found corrupt entry, invalidating this copy of the key");
          error_detected = true;
          sectors.FromAddress(address).mark_corrupt();
        }
      }
      size_t error_val = error_detected ? 1 : 0;

      if (!key_found) {
        PW_LOG_ERROR("No valid entries for key. Data has been lost!");
        return StatusWithSize(Status::DATA_LOSS, error_val);
      } else if (key == read_key) {
        PW_LOG_DEBUG("Found match for key hash 0x%08" PRIx32, hash);
        *metadata = EntryMetadata(descriptors_[i], addresses(i));
        return StatusWithSize(Status::OK, error_val);
      } else {
        PW_LOG_WARN("Found key hash collision for 0x%08" PRIx32, hash);
        return StatusWithSize(Status::ALREADY_EXISTS, error_val);
      }
    }
  }
  return StatusWithSize::NOT_FOUND;
}

EntryMetadata EntryCache::AddNew(const KeyDescriptor& descriptor,
                                 Address entry_address) const {
  // TODO(hepler): DCHECK(!full());
  Address* first_address = ResetAddresses(descriptors_.size(), entry_address);
  descriptors_.push_back(descriptor);
  return EntryMetadata(descriptors_.back(), std::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) const {
  // 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 %u",
                     unsigned(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) const {
  Address* const existing = first_address(descriptor_index);

  for (size_t i = 0; i < redundancy(); ++i) {
    if (existing[i] == kNoAddress) {
      existing[i] = address;
      return;
    }
  }
}

std::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 std::span(addresses, size);
}

EntryCache::Address* EntryCache::ResetAddresses(size_t descriptor_index,
                                                Address address) const {
  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