xref: /aosp_15_r20/external/pigweed/pw_kvs/public/pw_kvs/internal/entry_cache.h (revision 61c4878ac05f98d0ceed94b57d316916de578985)
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