xref: /aosp_15_r20/external/pigweed/pw_kvs/public/pw_kvs/key_value_store.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 <array>
17 #include <cstddef>
18 #include <cstdint>
19 #include <string_view>
20 #include <type_traits>
21 
22 #include "pw_containers/vector.h"
23 #include "pw_kvs/checksum.h"
24 #include "pw_kvs/flash_memory.h"
25 #include "pw_kvs/format.h"
26 #include "pw_kvs/internal/entry.h"
27 #include "pw_kvs/internal/entry_cache.h"
28 #include "pw_kvs/internal/key_descriptor.h"
29 #include "pw_kvs/internal/sectors.h"
30 #include "pw_kvs/internal/span_traits.h"
31 #include "pw_span/span.h"
32 #include "pw_status/status.h"
33 #include "pw_status/status_with_size.h"
34 
35 namespace pw {
36 namespace kvs {
37 
38 enum class GargbageCollectOnWrite {
39   // Disable all automatic garbage collection on write.
40   kDisabled,
41 
42   // Allow up to a single sector, if needed, to be garbage collected on write.
43   kOneSector,
44 
45   // Allow as many sectors as needed be garbage collected on write.
46   kAsManySectorsNeeded,
47 };
48 
49 enum class ErrorRecovery {
50   // Immediately do full recovery of any errors that are detected.
51   kImmediate,
52 
53   // Recover from errors, but delay time consuming recovery steps until later
54   // as part of other time consuming operations. Such as waiting to garbage
55   // collect sectors with corrupt entries until the next garbage collection.
56   kLazy,
57 
58   // Only recover from errors when manually triggered as part of maintenance
59   // operations. This is not recommended for normal use, only for test or
60   // read-only use.
61   kManual,
62 };
63 
64 struct Options {
65   // Perform garbage collection if necessary when writing. If not kDisabled,
66   // garbage collection is attempted if space for an entry cannot be found. This
67   // is a relatively lengthy operation. If kDisabled, Put calls that would
68   // require garbage collection fail with RESOURCE_EXHAUSTED.
69   GargbageCollectOnWrite gc_on_write =
70       GargbageCollectOnWrite::kAsManySectorsNeeded;
71 
72   // When the KVS handles errors that are discovered, such as corrupt entries,
73   // not enough redundant copys of an entry, etc.
74   ErrorRecovery recovery = ErrorRecovery::kLazy;
75 
76   // Verify an entry's checksum after reading it from flash.
77   bool verify_on_read = true;
78 
79   // Verify an in-flash entry's checksum after writing it.
80   bool verify_on_write = true;
81 };
82 
83 /// Flash-backed persistent key-value store (KVS) with integrated
84 /// wear-leveling.
85 ///
86 /// Instances are declared as instances of
87 /// `pw::kvs::KeyValueStoreBuffer<MAX_ENTRIES, MAX_SECTORS>`, which allocates
88 /// buffers for tracking entries and flash sectors.
89 ///
90 /// @code{.cpp}
91 ///   #include "pw_kvs/key_value_store.h"
92 ///   #include "pw_kvs/flash_test_partition.h"
93 ///
94 ///   constexpr size_t kMaxSectors = 6;
95 ///   constexpr size_t kMaxEntries = 64;
96 ///   static constexpr pw::kvs::EntryFormat kvs_format = {
97 ///     .magic = 0xd253a8a9,  // Prod apps should use a random number here
98 ///     .checksum = nullptr
99 ///   };
100 ///   pw::kvs::KeyValueStoreBuffer<kMaxEntries, kMaxSectors> kvs(
101 ///     &pw::kvs::FlashTestPartition(),
102 ///     kvs_format
103 ///   );
104 ///
105 ///   kvs.Init();
106 /// @endcode
107 class KeyValueStore {
108  public:
109   /// Initializes the KVS. Must be called before calling other functions.
110   ///
111   /// @returns @rst
112   ///
113   /// .. pw-status-codes::
114   ///
115   ///    OK: The KVS successfully initialized.
116   ///
117   ///    DATA_LOSS: The KVS initialized and is usable, but contains corrupt
118   ///    data.
119   ///
120   ///    UNKNOWN: Unknown error. The KVS is not initialized.
121   ///
122   /// @endrst
123   Status Init();
124 
initialized()125   bool initialized() const {
126     return initialized_ == InitializationState::kReady;
127   }
128 
129   /// Reads the value of an entry in the KVS. The value is read into the
130   /// provided buffer and the number of bytes read is returned. Reads can be
131   /// started at an offset.
132   ///
133   /// @param[in] key The name of the key.
134   ///
135   /// @param[out] value The buffer to read the key's value into.
136   ///
137   /// @param[in] offset_bytes The byte offset to start the read at. Optional.
138   ///
139   /// @returns @rst
140   ///
141   /// .. pw-status-codes::
142   ///
143   ///    OK: The entry was successfully read.
144   ///
145   ///    NOT_FOUND: The key is not present in the KVS.
146   ///
147   ///    DATA_LOSS: Found the entry, but the data was corrupted.
148   ///
149   ///    RESOURCE_EXHAUSTED: The buffer could not fit the entire
150   ///    value, but as many bytes as possible were written to it. The number of
151   ///    of bytes read is returned. The remainder of the value can be read by
152   ///    calling ``Get()`` again with an offset.
153   ///
154   ///    FAILED_PRECONDITION: The KVS is not initialized. Call ``Init()``
155   ///    before calling this method.
156   ///
157   ///    INVALID_ARGUMENT: ``key`` is empty or too long, or ``value``
158   ///    is too large.
159   ///
160   /// @endrst
161   StatusWithSize Get(std::string_view key,
162                      span<std::byte> value,
163                      size_t offset_bytes = 0) const;
164 
165   /// Overload of `Get()` that accepts a pointer to a trivially copyable
166   /// object.
167   ///
168   /// If `value` is an array, call `Get()` with
169   /// `as_writable_bytes(span(array))`, or pass a pointer to the array
170   /// instead of the array itself.
171   template <typename Pointer,
172             typename = std::enable_if_t<std::is_pointer<Pointer>::value>>
Get(const std::string_view & key,const Pointer & pointer)173   Status Get(const std::string_view& key, const Pointer& pointer) const {
174     using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
175     CheckThatObjectCanBePutOrGet<T>();
176     return FixedSizeGet(key, pointer, sizeof(T));
177   }
178 
179   /// Adds a key-value entry to the KVS. If the key was already present, its
180   /// value is overwritten.
181   ///
182   /// @param[in] key The name of the key. All keys in the KVS must have a
183   /// unique hash. If the hash of your key matches an existing key, nothing is
184   /// added and @pw_status{ALREADY_EXISTS} is returned.
185   ///
186   /// @param[in] value The value for the key. This can be a span of bytes or a
187   /// trivially copyable object.
188   ///
189   /// @returns @rst
190   ///
191   /// .. pw-status-codes::
192   ///
193   ///    OK: The entry was successfully added or updated.
194   ///
195   ///    DATA_LOSS: Checksum validation failed after writing data.
196   ///
197   ///    RESOURCE_EXHAUSTED: Not enough space to add the entry.
198   ///
199   ///    ALREADY_EXISTS: The entry could not be added because a different
200   ///    key with the same hash is already in the KVS.
201   ///
202   ///    FAILED_PRECONDITION: The KVS is not initialized. Call ``Init()``
203   ///    before calling this method.
204   ///
205   ///    INVALID_ARGUMENT: ``key`` is empty or too long, or ``value``
206   ///    is too large.
207   ///
208   /// @endrst
209   template <typename T,
210             typename std::enable_if_t<ConvertsToSpan<T>::value>* = nullptr>
Put(const std::string_view & key,const T & value)211   Status Put(const std::string_view& key, const T& value) {
212     return PutBytes(key, as_bytes(internal::make_span(value)));
213   }
214 
215   template <typename T,
216             typename std::enable_if_t<!ConvertsToSpan<T>::value>* = nullptr>
Put(const std::string_view & key,const T & value)217   Status Put(const std::string_view& key, const T& value) {
218     CheckThatObjectCanBePutOrGet<T>();
219     return PutBytes(key, as_bytes(span<const T>(&value, 1)));
220   }
221 
222   /// Removes a key-value entry from the KVS.
223   ///
224   /// @param[in] key - The name of the key-value entry to delete.
225   ///
226   /// @returns @rst
227   ///
228   /// .. pw-status-codes::
229   ///
230   ///    OK: The entry was successfully deleted.
231   ///
232   ///    NOT_FOUND: ``key`` is not present in the KVS.
233   ///
234   ///    DATA_LOSS: Checksum validation failed after recording the
235   ///    erase.
236   ///
237   ///    RESOURCE_EXHAUSTED: Insufficient space to mark the entry as deleted.
238   ///
239   ///    FAILED_PRECONDITION: The KVS is not initialized. Call ``Init()``
240   ///    before calling this method.
241   ///
242   ///    INVALID_ARGUMENT: ``key`` is empty or too long.
243   ///
244   /// @endrst
245   Status Delete(std::string_view key);
246 
247   /// Returns the size of the value corresponding to the key.
248   ///
249   /// @param[in] key - The name of the key.
250   ///
251   /// @returns @rst
252   ///
253   /// .. pw-status-codes::
254   ///
255   ///    OK: The size was returned successfully.
256   ///
257   ///    NOT_FOUND: ``key`` is not present in the KVS.
258   ///
259   ///    DATA_LOSS: Checksum validation failed after reading the entry.
260   ///
261   ///    FAILED_PRECONDITION: The KVS is not initialized. Call ``Init()``
262   ///    before calling this method.
263   ///
264   ///    INVALID_ARGUMENT: ``key`` is empty or too long.
265   ///
266   /// @endrst
267   StatusWithSize ValueSize(std::string_view key) const;
268 
269   /// Performs all maintenance possible, including all needed repairing of
270   /// corruption and garbage collection of reclaimable space in the KVS. When
271   /// configured for manual recovery, this (along with `FullMaintenance()`) is
272   /// the only way KVS repair is triggered.
273   ///
274   /// @warning Performs heavy garbage collection of all reclaimable space,
275   /// regardless of whether there's other valid data in the sector. This
276   /// method may cause a significant amount of moving of valid entries.
HeavyMaintenance()277   Status HeavyMaintenance() {
278     return FullMaintenanceHelper(MaintenanceType::kHeavy);
279   }
280 
281   /// Perform all maintenance possible, including all needed repairing of
282   /// corruption and garbage collection of reclaimable space in the KVS. When
283   /// configured for manual recovery, this (along with `HeavyMaintenance()`) is
284   /// the only way KVS repair is triggered.
285   ///
286   /// Does not garbage collect sectors with valid data unless the KVS is mostly
287   /// full.
FullMaintenance()288   Status FullMaintenance() {
289     return FullMaintenanceHelper(MaintenanceType::kRegular);
290   }
291 
292   /// Performs a portion of KVS maintenance. If configured for at least lazy
293   /// recovery, will do any needed repairing of corruption. Does garbage
294   /// collection of part of the KVS, typically a single sector or similar unit
295   /// that makes sense for the KVS implementation.
296   Status PartialMaintenance();
297 
298   void LogDebugInfo() const;
299 
300   // Classes and functions to support STL-style iteration.
301   class iterator;
302 
303   /// Representation of a key-value entry during iteration.
304   class Item {
305    public:
306     /// @returns The key as a null-terminated string.
key()307     const char* key() const { return key_buffer_.data(); }
308 
309     /// @returns The value referred to by this iterator. Equivalent to
310     /// `pw::kvs::KeyValueStore::Get()`.
311     StatusWithSize Get(span<std::byte> value_buffer,
312                        size_t offset_bytes = 0) const {
313       return kvs_.Get(key(), *iterator_, value_buffer, offset_bytes);
314     }
315 
316     template <typename Pointer,
317               typename = std::enable_if_t<std::is_pointer<Pointer>::value>>
Get(const Pointer & pointer)318     Status Get(const Pointer& pointer) const {
319       using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
320       CheckThatObjectCanBePutOrGet<T>();
321       return kvs_.FixedSizeGet(key(), *iterator_, pointer, sizeof(T));
322     }
323 
324     // Reads the size of the value referred to by this iterator. Equivalent to
325     // KeyValueStore::ValueSize.
ValueSize()326     StatusWithSize ValueSize() const { return kvs_.ValueSize(*iterator_); }
327 
328    private:
329     friend class iterator;
330 
Item(const KeyValueStore & kvs,const internal::EntryCache::const_iterator & item_iterator)331     constexpr Item(const KeyValueStore& kvs,
332                    const internal::EntryCache::const_iterator& item_iterator)
333         : kvs_(kvs), iterator_(item_iterator), key_buffer_{} {}
334 
335     void ReadKey();
336 
337     const KeyValueStore& kvs_;
338     internal::EntryCache::const_iterator iterator_;
339 
340     // Buffer large enough for a null-terminated version of any valid key.
341     std::array<char, internal::Entry::kMaxKeyLength + 1> key_buffer_;
342   };
343 
344   /// Supported iteration methods.
345   class iterator {
346    public:
347     /// Increments to the next key-value entry in the container.
348     iterator& operator++();
349 
350     /// Increments to the next key-value entry in the container.
351     iterator operator++(int) {
352       const iterator original(item_.kvs_, item_.iterator_);
353       operator++();
354       return original;
355     }
356 
357     /// Reads the entry's key from flash.
358     const Item& operator*() {
359       item_.ReadKey();
360       return item_;
361     }
362 
363     /// Reads the entry into the `Item` object.
364     const Item* operator->() { return &operator*(); }
365 
366     /// Equality comparison of two entries.
367     constexpr bool operator==(const iterator& rhs) const {
368       return item_.iterator_ == rhs.item_.iterator_;
369     }
370 
371     /// Inequality comparison of two entries.
372     constexpr bool operator!=(const iterator& rhs) const {
373       return item_.iterator_ != rhs.item_.iterator_;
374     }
375 
376    private:
377     friend class KeyValueStore;
378 
iterator(const KeyValueStore & kvs,const internal::EntryCache::const_iterator & item_iterator)379     constexpr iterator(
380         const KeyValueStore& kvs,
381         const internal::EntryCache::const_iterator& item_iterator)
382         : item_(kvs, item_iterator) {}
383 
384     Item item_;
385   };
386 
387   using const_iterator = iterator;  // Standard alias for iterable types.
388 
389   /// @returns The first key-value entry in the container. Used for iteration.
390   iterator begin() const;
391   /// @returns The last key-value entry in the container. Used for iteration.
end()392   iterator end() const { return iterator(*this, entry_cache_.end()); }
393 
394   /// @returns The number of valid entries in the KVS.
size()395   size_t size() const { return entry_cache_.present_entries(); }
396 
397   /// @returns The number of valid entries and deleted entries yet to be
398   /// collected.
total_entries_with_deleted()399   size_t total_entries_with_deleted() const {
400     return entry_cache_.total_entries();
401   }
402 
403   /// @returns The maximum number of KV entries that's possible in the KVS.
max_size()404   size_t max_size() const { return entry_cache_.max_entries(); }
405 
406   /// @returns `true` if the KVS is empty.
empty()407   size_t empty() const { return size() == 0u; }
408 
409   /// @returns The number of transactions that have occurred since the KVS was
410   /// first used. This value is retained across initializations, but is reset
411   /// if the underlying flash is erased.
transaction_count()412   uint32_t transaction_count() const { return last_transaction_id_; }
413 
414   /// Statistics about the KVS.
415   ///
416   /// Statistics are since the KVS init. They're not retained across reboots.
417   struct StorageStats {
418     /// The number of writeable bytes remaining in the KVS. This number doesn't
419     /// include the one empty sector required for KVS garbage collection.
420     size_t writable_bytes;
421     /// The number of bytes in the KVS that are already in use.
422     size_t in_use_bytes;
423     /// The maximum number of bytes possible to reclaim by garbage collection.
424     /// The number of bytes actually reclaimed by maintenance depends on the
425     /// type of maintenance that's performed.
426     size_t reclaimable_bytes;
427     /// The total count of individual sector erases that have been performed.
428     size_t sector_erase_count;
429     /// The number of corrupt sectors that have been recovered.
430     size_t corrupt_sectors_recovered;
431     /// The number of missing redundant copies of entries that have been
432     /// recovered.
433     size_t missing_redundant_entries_recovered;
434   };
435 
436   /// @returns A `StorageStats` struct with details about the current and past
437   /// state of the KVS.
438   StorageStats GetStorageStats() const;
439 
440   /// @returns The number of identical copies written for each entry. A
441   /// redundancy of 1 means that only a single copy is written for each entry.
redundancy()442   size_t redundancy() const { return entry_cache_.redundancy(); }
443 
444   /// @returns `true` if the KVS has any unrepaired errors.
error_detected()445   bool error_detected() const { return error_detected_; }
446 
447   /// @returns The maximum number of bytes allowed for a key-value combination.
max_key_value_size_bytes()448   size_t max_key_value_size_bytes() const {
449     return max_key_value_size_bytes(partition_.sector_size_bytes());
450   }
451 
452   /// @returns The maximum number of bytes allowed for a given sector size for
453   /// a key-value combination.
max_key_value_size_bytes(size_t partition_sector_size_bytes)454   static constexpr size_t max_key_value_size_bytes(
455       size_t partition_sector_size_bytes) {
456     return partition_sector_size_bytes - Entry::entry_overhead();
457   }
458 
459   /// Checks the KVS for any error conditions and returns `true` if any errors
460   /// are present. Primarily intended for test and internal use.
461   bool CheckForErrors();
462 
463  protected:
464   using Address = FlashPartition::Address;
465   using Entry = internal::Entry;
466   using KeyDescriptor = internal::KeyDescriptor;
467   using SectorDescriptor = internal::SectorDescriptor;
468 
469   // In the future, will be able to provide additional EntryFormats for
470   // backwards compatibility.
471   KeyValueStore(FlashPartition* partition,
472                 span<const EntryFormat> formats,
473                 const Options& options,
474                 size_t redundancy,
475                 Vector<SectorDescriptor>& sector_descriptor_list,
476                 const SectorDescriptor** temp_sectors_to_skip,
477                 Vector<KeyDescriptor>& key_descriptor_list,
478                 Address* addresses);
479 
480  private:
481   using EntryMetadata = internal::EntryMetadata;
482   using EntryState = internal::EntryState;
483 
484   template <typename T>
CheckThatObjectCanBePutOrGet()485   static constexpr void CheckThatObjectCanBePutOrGet() {
486     static_assert(
487         std::is_trivially_copyable<T>::value && !std::is_pointer<T>::value,
488         "Only trivially copyable, non-pointer objects may be Put and Get by "
489         "value. Any value may be stored by converting it to a byte span "
490         "with as_bytes(span(&value, 1)) or "
491         "as_writable_bytes(span(&value, 1)).");
492   }
493 
494   Status InitializeMetadata();
495   Status LoadEntry(Address entry_address, Address* next_entry_address);
496   Status ScanForEntry(const SectorDescriptor& sector,
497                       Address start_address,
498                       Address* next_entry_address);
499 
500   // Remove deleted keys from the entry cache, including freeing sector bytes
501   // used by those keys. This must only be done directly after a full garbage
502   // collection, otherwise the current deleted entry could be garbage
503   // collected before the older stale entry producing a window for an
504   // invalid/corrupted KVS state if there was a power-fault, crash or other
505   // interruption.
506   Status RemoveDeletedKeyEntries();
507 
508   Status PutBytes(std::string_view key, span<const std::byte> value);
509 
510   StatusWithSize ValueSize(const EntryMetadata& metadata) const;
511 
512   Status ReadEntry(const EntryMetadata& metadata, Entry& entry) const;
513 
514   // Finds the metadata for an entry matching a particular key. Searches for a
515   // KeyDescriptor that matches this key and sets *metadata_out to point to it
516   // if one is found.
517   //
518   //             OK: there is a matching descriptor and *metadata is set
519   //      NOT_FOUND: there is no descriptor that matches this key, but this key
520   //                 has a unique hash (and could potentially be added to the
521   //                 KVS)
522   // ALREADY_EXISTS: there is no descriptor that matches this key, but the
523   //                 key's hash collides with the hash for an existing
524   //                 descriptor
525   //
526   Status FindEntry(std::string_view key, EntryMetadata* metadata_out) const;
527 
528   // Searches for a KeyDescriptor that matches this key and sets *metadata_out
529   // to point to it if one is found.
530   //
531   //          OK: there is a matching descriptor and *metadata_out is set
532   //   NOT_FOUND: there is no descriptor that matches this key
533   //
534   Status FindExisting(std::string_view key, EntryMetadata* metadata_out) const;
535 
536   StatusWithSize Get(std::string_view key,
537                      const EntryMetadata& metadata,
538                      span<std::byte> value_buffer,
539                      size_t offset_bytes) const;
540 
541   Status FixedSizeGet(std::string_view key,
542                       void* value,
543                       size_t size_bytes) const;
544 
545   Status FixedSizeGet(std::string_view key,
546                       const EntryMetadata& metadata,
547                       void* value,
548                       size_t size_bytes) const;
549 
550   Status CheckWriteOperation(std::string_view key) const;
551   Status CheckReadOperation(std::string_view key) const;
552 
553   Status WriteEntryForExistingKey(EntryMetadata& metadata,
554                                   EntryState new_state,
555                                   std::string_view key,
556                                   span<const std::byte> value);
557 
558   Status WriteEntryForNewKey(std::string_view key, span<const std::byte> value);
559 
560   Status WriteEntry(std::string_view key,
561                     span<const std::byte> value,
562                     EntryState new_state,
563                     EntryMetadata* prior_metadata = nullptr,
564                     const internal::Entry* prior_entry = nullptr);
565 
566   EntryMetadata CreateOrUpdateKeyDescriptor(const Entry& new_entry,
567                                             std::string_view key,
568                                             EntryMetadata* prior_metadata,
569                                             size_t prior_size);
570 
571   EntryMetadata UpdateKeyDescriptor(const Entry& entry,
572                                     Address new_address,
573                                     EntryMetadata* prior_metadata,
574                                     size_t prior_size);
575 
576   Status GetAddressesForWrite(Address* write_addresses, size_t write_size);
577 
578   Status GetSectorForWrite(SectorDescriptor** sector,
579                            size_t entry_size,
580                            span<const Address> reserved_addresses);
581 
582   Status MarkSectorCorruptIfNotOk(Status status, SectorDescriptor* sector);
583 
584   Status AppendEntry(const Entry& entry,
585                      std::string_view key,
586                      span<const std::byte> value);
587 
588   StatusWithSize CopyEntryToSector(Entry& entry,
589                                    SectorDescriptor* new_sector,
590                                    Address new_address);
591 
592   Status RelocateEntry(const EntryMetadata& metadata,
593                        KeyValueStore::Address& address,
594                        span<const Address> reserved_addresses);
595 
596   // Perform all maintenance possible, including all neeeded repairing of
597   // corruption and garbage collection of reclaimable space in the KVS. When
598   // configured for manual recovery, this is the only way KVS repair is
599   // triggered.
600   //
601   // - Regular will not garbage collect sectors with valid data unless the KVS
602   //   is mostly full.
603   // - Heavy will garbage collect all reclaimable space regardless of valid data
604   //   in the sector.
605   enum class MaintenanceType {
606     kRegular,
607     kHeavy,
608   };
609   Status FullMaintenanceHelper(MaintenanceType maintenance_type);
610 
611   // Find and garbage collect a singe sector that does not include a reserved
612   // address.
613   Status GarbageCollect(span<const Address> reserved_addresses);
614 
615   Status RelocateKeyAddressesInSector(SectorDescriptor& sector_to_gc,
616                                       const EntryMetadata& metadata,
617                                       span<const Address> reserved_addresses);
618 
619   Status GarbageCollectSector(SectorDescriptor& sector_to_gc,
620                               span<const Address> reserved_addresses);
621 
622   // Ensure that all entries are on the primary (first) format. Entries that are
623   // not on the primary format are rewritten.
624   //
625   // Return: status + number of entries updated.
626   StatusWithSize UpdateEntriesToPrimaryFormat();
627 
628   Status AddRedundantEntries(EntryMetadata& metadata);
629 
630   Status RepairCorruptSectors();
631 
632   Status EnsureFreeSectorExists();
633 
634   Status EnsureEntryRedundancy();
635 
636   Status FixErrors();
637 
638   Status Repair();
639 
640   internal::Entry CreateEntry(Address address,
641                               std::string_view key,
642                               span<const std::byte> value,
643                               EntryState state);
644 
645   void LogSectors() const;
646   void LogKeyDescriptor() const;
647 
648   FlashPartition& partition_;
649   const internal::EntryFormats formats_;
650 
651   // List of sectors used by this KVS.
652   internal::Sectors sectors_;
653 
654   // Unordered list of KeyDescriptors. Finding a key requires scanning and
655   // verifying a match by reading the actual entry.
656   internal::EntryCache entry_cache_;
657 
658   Options options_;
659 
660   // Threshold value for when to garbage collect all stale data. Above the
661   // threshold, GC all reclaimable bytes regardless of if valid data is in
662   // sector. Below the threshold, only GC sectors with reclaimable bytes and no
663   // valid bytes. The threshold is based on the portion of KVS capacity used by
664   // valid bytes.
665   static constexpr size_t kGcUsageThresholdPercentage = 70;
666 
667   enum class InitializationState {
668     // KVS Init() has not been called and KVS is not usable.
669     kNotInitialized,
670 
671     // KVS Init() run but not all the needed invariants are met for an operating
672     // KVS. KVS is not writable, but read operaions are possible.
673     kNeedsMaintenance,
674 
675     // KVS is fully ready for use.
676     kReady,
677   };
678   InitializationState initialized_;
679 
680   // error_detected_ needs to be set from const KVS methods (such as Get), so
681   // make it mutable.
682   mutable bool error_detected_;
683 
684   struct InternalStats {
685     size_t sector_erase_count;
686     size_t corrupt_sectors_recovered;
687     size_t missing_redundant_entries_recovered;
688   };
689   InternalStats internal_stats_;
690 
691   uint32_t last_transaction_id_;
692 };
693 
694 template <size_t kMaxEntries,
695           size_t kMaxUsableSectors,
696           size_t kRedundancy = 1,
697           size_t kEntryFormats = 1>
698 class KeyValueStoreBuffer : public KeyValueStore {
699  public:
700   // Constructs a KeyValueStore on the partition, with support for one
701   // EntryFormat (kEntryFormats must be 1).
702   KeyValueStoreBuffer(FlashPartition* partition,
703                       const EntryFormat& format,
704                       const Options& options = {})
KeyValueStoreBuffer(partition,span<const EntryFormat,kEntryFormats> (reinterpret_cast<const EntryFormat (&)[1]> (format)),options)705       : KeyValueStoreBuffer(
706             partition,
707             span<const EntryFormat, kEntryFormats>(
708                 reinterpret_cast<const EntryFormat (&)[1]>(format)),
709             options) {
710     static_assert(kEntryFormats == 1,
711                   "kEntryFormats EntryFormats must be specified");
712   }
713 
714   // Constructs a KeyValueStore on the partition. Supports multiple entry
715   // formats. The first EntryFormat is used for new entries.
716   KeyValueStoreBuffer(FlashPartition* partition,
717                       span<const EntryFormat, kEntryFormats> formats,
718                       const Options& options = {})
KeyValueStore(partition,formats_,options,kRedundancy,sectors_,temp_sectors_to_skip_,key_descriptors_,addresses_)719       : KeyValueStore(partition,
720                       formats_,
721                       options,
722                       kRedundancy,
723                       sectors_,
724                       temp_sectors_to_skip_,
725                       key_descriptors_,
726                       addresses_),
727         sectors_(),
728         key_descriptors_(),
729         formats_() {
730     std::copy(formats.begin(), formats.end(), formats_.begin());
731   }
732 
733  private:
734   static_assert(kMaxEntries > 0u);
735   static_assert(kMaxUsableSectors > 0u);
736   static_assert(kRedundancy > 0u);
737   static_assert(kEntryFormats > 0u);
738 
739   Vector<SectorDescriptor, kMaxUsableSectors> sectors_;
740 
741   // Allocate space for an list of SectorDescriptors to avoid while searching
742   // for space to write entries. This is used to avoid changing sectors that are
743   // reserved for a new entry or marked as having other redundant copies of an
744   // entry. Up to kRedundancy sectors are reserved for a new entry, and up to
745   // kRedundancy - 1 sectors can have redundant copies of an entry, giving a
746   // maximum of 2 * kRedundancy - 1 sectors to avoid.
747   const SectorDescriptor* temp_sectors_to_skip_[2 * kRedundancy - 1];
748 
749   // KeyDescriptors for use by the KVS's EntryCache.
750   Vector<KeyDescriptor, kMaxEntries> key_descriptors_;
751 
752   // An array of addresses associated with the KeyDescriptors for use with the
753   // EntryCache. To support having KeyValueStores with different redundancies,
754   // the addresses are stored in a parallel array instead of inside
755   // KeyDescriptors.
756   internal::EntryCache::AddressList<kRedundancy, kMaxEntries> addresses_;
757 
758   // EntryFormats that can be read by this KeyValueStore.
759   std::array<EntryFormat, kEntryFormats> formats_;
760 };
761 
762 }  // namespace kvs
763 }  // namespace pw
764