third_party/pigweed/repo/pw_kvs/entry_cache.cc

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 #define PW_LOG_MODULE_NAME "KVS"
  16 #define PW_LOG_LEVEL PW_KVS_LOG_LEVEL
  17
  18 #include "pw_kvs/internal/entry_cache.h"
  19
  20 #include <cinttypes>
  21
  22 #include "pw_kvs/flash_memory.h"
  23 #include "pw_kvs/internal/entry.h"
  24 #include "pw_kvs/internal/hash.h"
  25 #include "pw_kvs_private/config.h"
  26 #include "pw_log/log.h"
  27
  28 namespace pw::kvs::internal {
  29 namespace {
  30
  31 constexpr FlashPartition::Address kNoAddress = FlashPartition::Address(-1);
  32
  33 }  // namespace
  34
  35 void EntryMetadata::RemoveAddress(Address address_to_remove) {
  36   // Find the index of the address to remove.
  37   for (Address& address : addresses_) {
  38     if (address == address_to_remove) {
  39       // Move the address at the back of the list to the slot of the address
  40       // being removed. Do this unconditionally, even if the address to remove
  41       // is the last slot since the logic still works.
  42       address = addresses_.back();
  43
  44       // Remove the back entry of the address list.
  45       addresses_.back() = kNoAddress;
  46       addresses_ = std::span(addresses_.begin(), addresses_.size() - 1);
  47       break;
  48     }
  49   }
  50 }
  51
  52 void EntryMetadata::Reset(const KeyDescriptor& descriptor, Address address) {
  53   *descriptor_ = descriptor;
  54
  55   addresses_[0] = address;
  56   for (size_t i = 1; i < addresses_.size(); ++i) {
  57     addresses_[i] = kNoAddress;
  58   }
  59   addresses_ = addresses_.first(1);
  60 }
  61
  62 StatusWithSize EntryCache::Find(FlashPartition& partition,
  63                                 const Sectors& sectors,
  64                                 const EntryFormats& formats,
  65                                 Key key,
  66                                 EntryMetadata* metadata) const {
  67   const uint32_t hash = internal::Hash(key);
  68   Entry::KeyBuffer key_buffer;
  69   bool error_detected = false;
  70
  71   for (size_t i = 0; i < descriptors_.size(); ++i) {
  72     if (descriptors_[i].key_hash == hash) {
  73       bool key_found = false;
  74       Key read_key;
  75
  76       for (Address address : addresses(i)) {
  77         Status read_result =
  78             Entry::ReadKey(partition, address, key.size(), key_buffer.data());
  79
  80         read_key = Key(key_buffer.data(), key.size());
  81
  82         if (read_result.ok() && hash == internal::Hash(read_key)) {
  83           key_found = true;
  84           break;
  85         } else {
  86           // A hash mismatch can be caused by reading invalid data or a key hash
  87           // collision of keys with differing size. To verify the data read from
  88           // flash is good, validate the entry.
  89           Entry entry;
  90           read_result = Entry::Read(partition, address, formats, &entry);
  91           if (read_result.ok() && entry.VerifyChecksumInFlash().ok()) {
  92             key_found = true;
  93             break;
  94           }
  95
  96           PW_LOG_WARN(
  97               "   Found corrupt entry, invalidating this copy of the key");
  98           error_detected = true;
  99           sectors.FromAddress(address).mark_corrupt();
 100         }
 101       }
 102       size_t error_val = error_detected ? 1 : 0;
 103
 104       if (!key_found) {
 105         PW_LOG_ERROR("No valid entries for key. Data has been lost!");
 106         return StatusWithSize::DataLoss(error_val);
 107       } else if (key == read_key) {
 108         PW_LOG_DEBUG("Found match for key hash 0x%08" PRIx32, hash);
 109         *metadata = EntryMetadata(descriptors_[i], addresses(i));
 110         return StatusWithSize(error_val);
 111       } else {
 112         PW_LOG_WARN("Found key hash collision for 0x%08" PRIx32, hash);
 113         return StatusWithSize::AlreadyExists(error_val);
 114       }
 115     }
 116   }
 117   return StatusWithSize::NotFound();
 118 }
 119
 120 EntryMetadata EntryCache::AddNew(const KeyDescriptor& descriptor,
 121                                  Address entry_address) const {
 122   // TODO(hepler): DCHECK(!full());
 123   Address* first_address = ResetAddresses(descriptors_.size(), entry_address);
 124   descriptors_.push_back(descriptor);
 125   return EntryMetadata(descriptors_.back(), std::span(first_address, 1));
 126 }
 127
 128 // TODO: This method is the trigger of the O(valid_entries * all_entries) time
 129 // complexity for reading. At some cost to memory, this could be optimized by
 130 // using a hash table instead of scanning, but in practice this should be fine
 131 // for a small number of keys
 132 Status EntryCache::AddNewOrUpdateExisting(const KeyDescriptor& descriptor,
 133                                           Address address,
 134                                           size_t sector_size_bytes) const {
 135   // With the new key descriptor, either add it to the descriptor table or
 136   // overwrite an existing entry with an older version of the key.
 137   const int index = FindIndex(descriptor.key_hash);
 138
 139   // Write a new entry if there is room.
 140   if (index == -1) {
 141     if (full()) {
 142       return Status::ResourceExhausted();
 143     }
 144     AddNew(descriptor, address);
 145     return OkStatus();
 146   }
 147
 148   // Existing entry is old; replace the existing entry with the new one.
 149   if (descriptor.transaction_id > descriptors_[index].transaction_id) {
 150     descriptors_[index] = descriptor;
 151     ResetAddresses(index, address);
 152     return OkStatus();
 153   }
 154
 155   // If the entries have a duplicate transaction ID, add the new (redundant)
 156   // entry to the existing descriptor.
 157   if (descriptors_[index].transaction_id == descriptor.transaction_id) {
 158     if (descriptors_[index].key_hash != descriptor.key_hash) {
 159       PW_LOG_ERROR("Duplicate entry for key 0x%08" PRIx32
 160                    " with transaction ID %" PRIu32 " has non-matching hash",
 161                    descriptor.key_hash,
 162                    descriptor.transaction_id);
 163       return Status::DataLoss();
 164     }
 165
 166     // Verify that this entry is not in the same sector as an existing copy of
 167     // this same key.
 168     for (Address existing_address : addresses(index)) {
 169       if (existing_address / sector_size_bytes == address / sector_size_bytes) {
 170         PW_LOG_DEBUG("Multiple Redundant entries in same sector %u",
 171                      unsigned(address / sector_size_bytes));
 172         return Status::DataLoss();
 173       }
 174     }
 175
 176     AddAddressIfRoom(index, address);
 177   } else {
 178     PW_LOG_DEBUG("Found stale entry when appending; ignoring");
 179   }
 180   return OkStatus();
 181 }
 182
 183 size_t EntryCache::present_entries() const {
 184   size_t present_entries = 0;
 185
 186   for (const KeyDescriptor& descriptor : descriptors_) {
 187     if (descriptor.state != EntryState::kDeleted) {
 188       present_entries += 1;
 189     }
 190   }
 191
 192   return present_entries;
 193 }
 194
 195 int EntryCache::FindIndex(uint32_t key_hash) const {
 196   for (size_t i = 0; i < descriptors_.size(); ++i) {
 197     if (descriptors_[i].key_hash == key_hash) {
 198       return i;
 199     }
 200   }
 201   return -1;
 202 }
 203
 204 void EntryCache::AddAddressIfRoom(size_t descriptor_index,
 205                                   Address address) const {
 206   Address* const existing = first_address(descriptor_index);
 207
 208   for (size_t i = 0; i < redundancy(); ++i) {
 209     if (existing[i] == kNoAddress) {
 210       existing[i] = address;
 211       return;
 212     }
 213   }
 214 }
 215
 216 std::span<EntryCache::Address> EntryCache::addresses(
 217     size_t descriptor_index) const {
 218   Address* const addresses = first_address(descriptor_index);
 219
 220   size_t size = 0;
 221   while (size < redundancy() && addresses[size] != kNoAddress) {
 222     size += 1;
 223   }
 224
 225   return std::span(addresses, size);
 226 }
 227
 228 EntryCache::Address* EntryCache::ResetAddresses(size_t descriptor_index,
 229                                                 Address address) const {
 230   Address* first = first_address(descriptor_index);
 231   *first = address;
 232
 233   // Clear the additional addresses, if any.
 234   for (size_t i = 1; i < redundancy_; ++i) {
 235     first[i] = kNoAddress;
 236   }
 237
 238   return first;
 239 }
 240
 241 }  // namespace pw::kvs::internal