blob: 599ae801032acb12c950cd0b7896aff42518c149 [file] [log] [blame]
Wyatt Hepler7ded6da2020-03-11 18:24:43 -07001// 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
Armando Montanez28ecccb2020-05-04 15:35:54 -070015#define PW_LOG_MODULE_NAME "KVS"
16
Wyatt Hepler7ded6da2020-03-11 18:24:43 -070017#include "pw_kvs/internal/entry_cache.h"
18
19#include <cinttypes>
20
21#include "pw_kvs/flash_memory.h"
22#include "pw_kvs/internal/entry.h"
23#include "pw_kvs/internal/hash.h"
24#include "pw_kvs_private/macros.h"
25#include "pw_log/log.h"
26
27namespace pw::kvs::internal {
28namespace {
29
30using std::string_view;
31
32constexpr FlashPartition::Address kNoAddress = FlashPartition::Address(-1);
33
34} // namespace
35
David Rogers9abe3c72020-03-24 19:03:13 -070036void EntryMetadata::RemoveAddress(Address address_to_remove) {
37 // Find the index of the address to remove.
38 for (Address& address : addresses_) {
39 if (address == address_to_remove) {
40 // Move the address at the back of the list to the slot of the address
41 // being removed. Do this unconditionally, even if the address to remove
42 // is the last slot since the logic still works.
43 address = addresses_.back();
44
45 // Remove the back entry of the address list.
46 addresses_.back() = kNoAddress;
47 addresses_ = span(addresses_.begin(), addresses_.size() - 1);
48 break;
49 }
50 }
51}
52
Wyatt Hepler7ded6da2020-03-11 18:24:43 -070053void EntryMetadata::Reset(const KeyDescriptor& descriptor, Address address) {
54 *descriptor_ = descriptor;
55
56 addresses_[0] = address;
57 for (size_t i = 1; i < addresses_.size(); ++i) {
58 addresses_[i] = kNoAddress;
59 }
60 addresses_ = addresses_.first(1);
61}
62
David Rogers98fea472020-04-01 15:43:48 -070063StatusWithSize EntryCache::Find(FlashPartition& partition,
64 const Sectors& sectors,
65 const EntryFormats& formats,
66 string_view key,
67 EntryMetadata* metadata) const {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -070068 const uint32_t hash = internal::Hash(key);
69 Entry::KeyBuffer key_buffer;
David Rogers98fea472020-04-01 15:43:48 -070070 bool error_detected = false;
Wyatt Hepler7ded6da2020-03-11 18:24:43 -070071
72 for (size_t i = 0; i < descriptors_.size(); ++i) {
73 if (descriptors_[i].key_hash == hash) {
David Rogers98fea472020-04-01 15:43:48 -070074 bool key_found = false;
75 string_view read_key;
Wyatt Hepler7ded6da2020-03-11 18:24:43 -070076
David Rogers98fea472020-04-01 15:43:48 -070077 for (Address address : addresses(i)) {
78 Status read_result =
79 Entry::ReadKey(partition, address, key.size(), key_buffer.data());
80
81 read_key = string_view(key_buffer.data(), key.size());
82
83 if (read_result.ok() && hash == internal::Hash(read_key)) {
84 key_found = true;
85 break;
86 } else {
87 // A hash mismatch can be caused by reading invalid data or a key hash
88 // collision of keys with differing size. To verify the data read from
89 // flash is good, validate the entry.
90 Entry entry;
91 read_result = Entry::Read(partition, address, formats, &entry);
92 if (read_result.ok() && entry.VerifyChecksumInFlash().ok()) {
93 key_found = true;
94 break;
95 }
96
97 PW_LOG_WARN(
98 " Found corrupt entry, invalidating this copy of the key");
99 error_detected = true;
100 sectors.FromAddress(address).mark_corrupt();
101 }
102 }
103 size_t error_val = error_detected ? 1 : 0;
104
105 if (!key_found) {
106 PW_LOG_ERROR("No valid entries for key. Data has been lost!");
107 return StatusWithSize(Status::DATA_LOSS, error_val);
108 } else if (key == read_key) {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700109 PW_LOG_DEBUG("Found match for key hash 0x%08" PRIx32, hash);
110 *metadata = EntryMetadata(descriptors_[i], addresses(i));
David Rogers98fea472020-04-01 15:43:48 -0700111 return StatusWithSize(Status::OK, error_val);
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700112 } else {
113 PW_LOG_WARN("Found key hash collision for 0x%08" PRIx32, hash);
David Rogers98fea472020-04-01 15:43:48 -0700114 return StatusWithSize(Status::ALREADY_EXISTS, error_val);
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700115 }
116 }
117 }
David Rogers98fea472020-04-01 15:43:48 -0700118 return StatusWithSize::NOT_FOUND;
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700119}
120
121EntryMetadata EntryCache::AddNew(const KeyDescriptor& descriptor,
Wyatt Hepler883e7402020-04-06 09:31:18 -0700122 Address entry_address) const {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700123 // TODO(hepler): DCHECK(!full());
124 Address* first_address = ResetAddresses(descriptors_.size(), entry_address);
125 descriptors_.push_back(descriptor);
126 return EntryMetadata(descriptors_.back(), span(first_address, 1));
127}
128
129// TODO: This method is the trigger of the O(valid_entries * all_entries) time
130// complexity for reading. At some cost to memory, this could be optimized by
131// using a hash table instead of scanning, but in practice this should be fine
132// for a small number of keys
133Status EntryCache::AddNewOrUpdateExisting(const KeyDescriptor& descriptor,
134 Address address,
Wyatt Hepler883e7402020-04-06 09:31:18 -0700135 size_t sector_size_bytes) const {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700136 // With the new key descriptor, either add it to the descriptor table or
137 // overwrite an existing entry with an older version of the key.
138 const int index = FindIndex(descriptor.key_hash);
139
140 // Write a new entry if there is room.
141 if (index == -1) {
142 if (full()) {
143 return Status::RESOURCE_EXHAUSTED;
144 }
145 AddNew(descriptor, address);
146 return Status::OK;
147 }
148
149 // Existing entry is old; replace the existing entry with the new one.
150 if (descriptor.transaction_id > descriptors_[index].transaction_id) {
151 descriptors_[index] = descriptor;
152 ResetAddresses(index, address);
153 return Status::OK;
154 }
155
156 // If the entries have a duplicate transaction ID, add the new (redundant)
157 // entry to the existing descriptor.
158 if (descriptors_[index].transaction_id == descriptor.transaction_id) {
159 if (descriptors_[index].key_hash != descriptor.key_hash) {
160 PW_LOG_ERROR("Duplicate entry for key 0x%08" PRIx32
161 " with transaction ID %" PRIu32 " has non-matching hash",
162 descriptor.key_hash,
163 descriptor.transaction_id);
164 return Status::DATA_LOSS;
165 }
166
167 // Verify that this entry is not in the same sector as an existing copy of
168 // this same key.
169 for (Address existing_address : addresses(index)) {
170 if (existing_address / sector_size_bytes == address / sector_size_bytes) {
Wyatt Hepler09b3a2a2020-03-25 13:18:37 -0700171 PW_LOG_DEBUG("Multiple Redundant entries in same sector %u",
172 unsigned(address / sector_size_bytes));
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700173 return Status::DATA_LOSS;
174 }
175 }
176
177 AddAddressIfRoom(index, address);
178 } else {
179 PW_LOG_DEBUG("Found stale entry when appending; ignoring");
180 }
181 return Status::OK;
182}
183
184size_t EntryCache::present_entries() const {
185 size_t present_entries = 0;
186
187 for (const KeyDescriptor& descriptor : descriptors_) {
188 if (descriptor.state != EntryState::kDeleted) {
189 present_entries += 1;
190 }
191 }
192
193 return present_entries;
194}
195
196int EntryCache::FindIndex(uint32_t key_hash) const {
197 for (size_t i = 0; i < descriptors_.size(); ++i) {
198 if (descriptors_[i].key_hash == key_hash) {
199 return i;
200 }
201 }
202 return -1;
203}
204
Wyatt Hepler883e7402020-04-06 09:31:18 -0700205void EntryCache::AddAddressIfRoom(size_t descriptor_index,
206 Address address) const {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700207 Address* const existing = first_address(descriptor_index);
208
209 for (size_t i = 0; i < redundancy(); ++i) {
210 if (existing[i] == kNoAddress) {
211 existing[i] = address;
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700212 return;
213 }
214 }
215}
216
217span<EntryCache::Address> EntryCache::addresses(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 span(addresses, size);
226}
227
228EntryCache::Address* EntryCache::ResetAddresses(size_t descriptor_index,
Wyatt Hepler883e7402020-04-06 09:31:18 -0700229 Address address) const {
Wyatt Hepler7ded6da2020-03-11 18:24:43 -0700230 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