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 #pragma once 15 16 #include <cstddef> 17 #include <cstdint> 18 #include <string_view> 19 #include <type_traits> 20 21 #include "pw_containers/vector.h" 22 #include "pw_kvs/flash_memory.h" 23 #include "pw_kvs/format.h" 24 #include "pw_kvs/internal/key_descriptor.h" 25 #include "pw_kvs/internal/sectors.h" 26 #include "pw_span/span.h" 27 28 namespace pw { 29 namespace kvs { 30 namespace internal { 31 32 // Caches information about a key-value entry. Facilitates quickly finding 33 // entries without having to read flash. 34 class EntryMetadata { 35 public: 36 using Address = FlashPartition::Address; 37 38 EntryMetadata() = default; 39 hash()40 uint32_t hash() const { return descriptor_->key_hash; } 41 transaction_id()42 uint32_t transaction_id() const { return descriptor_->transaction_id; } 43 state()44 EntryState state() const { return descriptor_->state; } 45 46 // The first known address of this entry. first_address()47 uint32_t first_address() const { return addresses_[0]; } 48 49 // All addresses for this entry, including redundant entries, if any. addresses()50 const span<Address>& addresses() const { return addresses_; } 51 52 // True if the KeyDesctiptor's transaction ID is newer than the specified ID. IsNewerThan(uint32_t other_transaction_id)53 bool IsNewerThan(uint32_t other_transaction_id) const { 54 // TODO(hepler): Consider handling rollover. 55 return transaction_id() > other_transaction_id; 56 } 57 58 // Adds a new address to the entry metadata. MUST NOT be called more times 59 // than allowed by the redundancy. AddNewAddress(Address address)60 void AddNewAddress(Address address) { 61 // Each descriptor is given sufficient space in an EntryCache's address 62 // buffer to meet the redundancy requirements of an EntryCache. This object 63 // isn't aware of required redundancy, so there's no strict checking that 64 // this contract is respected. 65 addresses_ = span<Address>(addresses_.begin(), addresses_.size() + 1); 66 addresses_[addresses_.size() - 1] = address; 67 } 68 69 // Remove an address from the entry metadata. 70 void RemoveAddress(Address address_to_remove); 71 72 // Resets the KeyDescrtiptor and addresses to refer to the provided 73 // KeyDescriptor and address. 74 void Reset(const KeyDescriptor& descriptor, Address address); 75 76 private: 77 friend class EntryCache; 78 EntryMetadata(KeyDescriptor & descriptor,span<Address> addresses)79 constexpr EntryMetadata(KeyDescriptor& descriptor, span<Address> addresses) 80 : descriptor_(&descriptor), addresses_(addresses) {} 81 82 KeyDescriptor* descriptor_; 83 span<Address> addresses_; 84 }; 85 86 // Tracks entry metadata. Combines KeyDescriptors and with their associated 87 // addresses. 88 class EntryCache { 89 private: 90 enum Constness : bool { kMutable = false, kConst = true }; 91 92 // Iterates over the EntryCache as EntryMetadata objects. 93 template <Constness kIsConst> 94 class Iterator { 95 public: 96 using value_type = 97 std::conditional_t<kIsConst, const EntryMetadata, EntryMetadata>; 98 99 Iterator& operator++() { 100 ++metadata_.descriptor_; 101 return *this; 102 } 103 104 Iterator operator++(int) { 105 Iterator original = *this; 106 operator++(); 107 return original; 108 } 109 110 // Updates the internal EntryMetadata object. 111 value_type& operator*() const { 112 metadata_.addresses_ = entry_cache_->addresses( 113 metadata_.descriptor_ - entry_cache_->descriptors_.begin()); 114 return metadata_; 115 } 116 value_type* operator->() const { return &operator*(); } 117 118 constexpr bool operator==(const Iterator& rhs) const { 119 return metadata_.descriptor_ == rhs.metadata_.descriptor_; 120 } 121 constexpr bool operator!=(const Iterator& rhs) const { 122 return metadata_.descriptor_ != rhs.metadata_.descriptor_; 123 } 124 125 // Allow non-const to convert to const. 126 operator Iterator<kConst>() const { 127 return {entry_cache_, metadata_.descriptor_}; 128 } 129 130 private: 131 friend class EntryCache; 132 Iterator(const EntryCache * entry_cache,KeyDescriptor * descriptor)133 constexpr Iterator(const EntryCache* entry_cache, KeyDescriptor* descriptor) 134 : entry_cache_(entry_cache), metadata_(*descriptor, {}) {} 135 136 const EntryCache* entry_cache_; 137 138 // Mark this mutable so it can be updated in the const operator*() method. 139 // This allows lazy updating of the EntryMetadata. 140 mutable EntryMetadata metadata_; 141 }; 142 143 public: 144 using iterator = Iterator<kMutable>; 145 using const_iterator = Iterator<kConst>; 146 147 using Address = FlashPartition::Address; 148 149 // The type to use for an address list with the specified number of entries 150 // and redundancy. kRedundancy extra entries are added to make room for a 151 // temporary list of entry addresses. 152 template <size_t kMaxEntries, size_t kRedundancy> 153 using AddressList = Address[kMaxEntries * kRedundancy + kRedundancy]; 154 EntryCache(Vector<KeyDescriptor> & descriptors,Address * addresses,size_t redundancy)155 constexpr EntryCache(Vector<KeyDescriptor>& descriptors, 156 Address* addresses, 157 size_t redundancy) 158 : descriptors_(descriptors), 159 addresses_(addresses), 160 redundancy_(redundancy) {} 161 162 // Clears all KeyDescriptors. Reset()163 void Reset() const { descriptors_.clear(); } 164 165 // Finds the metadata for an entry matching a particular key. Searches for a 166 // KeyDescriptor that matches this key and sets *metadata to point to it if 167 // one is found. 168 // 169 // OK: there is a matching descriptor and *metadata is set 170 // NOT_FOUND: there is no descriptor that matches this key, but this key 171 // has a unique hash (and could potentially be added to the 172 // KVS) 173 // ALREADY_EXISTS: there is no descriptor that matches this key, but the 174 // key's hash collides with the hash for an existing 175 // descriptor 176 // 177 StatusWithSize Find(FlashPartition& partition, 178 const Sectors& sectors, 179 const EntryFormats& formats, 180 std::string_view key, 181 EntryMetadata* metadata) const; 182 183 // Adds a new descriptor to the descriptor list. The entry MUST be unique and 184 // the EntryCache must NOT be full! 185 EntryMetadata AddNew(const KeyDescriptor& descriptor, Address address) const; 186 187 // Adds a new descriptor, overwrites an existing one, or adds an additional 188 // redundant address to one. The sector size is included for checking that 189 // redundant entries are in different sectors. 190 Status AddNewOrUpdateExisting(const KeyDescriptor& descriptor, 191 Address address, 192 size_t sector_size_bytes) const; 193 194 // Removes an existing entry from the cache. Returns an iterator to the 195 // next entry so that iteration can continue. 196 iterator RemoveEntry(iterator& entry_it); 197 198 // Returns a pointer to an array of redundancy() addresses for temporary use. 199 // This is used by the KeyValueStore to track reserved addresses when finding 200 // space for a new entry. TempReservedAddressesForWrite()201 Address* TempReservedAddressesForWrite() const { 202 return &addresses_[descriptors_.max_size() * redundancy_]; 203 } 204 205 // The number of copies of each entry. redundancy()206 size_t redundancy() const { return redundancy_; } 207 208 // True if no more entries can be added to the cache. full()209 bool full() const { return descriptors_.full(); } 210 211 // The total number of entries, including tombstone entries. total_entries()212 size_t total_entries() const { return descriptors_.size(); } 213 214 // The total number of present (non-tombstone) entries. 215 size_t present_entries() const; 216 217 // The maximum number of entries supported by this EntryCache. max_entries()218 size_t max_entries() const { return descriptors_.max_size(); } 219 begin()220 iterator begin() const { return {this, descriptors_.begin()}; } cbegin()221 const_iterator cbegin() const { return {this, descriptors_.begin()}; } 222 end()223 iterator end() const { return {this, descriptors_.end()}; } cend()224 const_iterator cend() const { return {this, descriptors_.end()}; } 225 226 private: 227 int FindIndex(uint32_t key_hash) const; 228 229 // Adds the address to the descriptor at the specified index if there is an 230 // address slot available. 231 void AddAddressIfRoom(size_t descriptor_index, Address address) const; 232 233 // Returns a span of the valid addresses for the descriptor. 234 span<Address> addresses(size_t descriptor_index) const; 235 first_address(size_t descriptor_index)236 Address* first_address(size_t descriptor_index) const { 237 return &addresses_[descriptor_index * redundancy_]; 238 } 239 240 Address* ResetAddresses(size_t descriptor_index, Address address) const; 241 242 Vector<KeyDescriptor>& descriptors_; 243 FlashPartition::Address* const addresses_; 244 const size_t redundancy_; 245 }; 246 247 } // namespace internal 248 } // namespace kvs 249 } // namespace pw 250