1 // Copyright 2020 The Pigweed Authors
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
7 // https://www.apache.org/licenses/LICENSE-2.0
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
20 #include <type_traits>
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_kvs/key.h"
32 #include "pw_status/status.h"
33 #include "pw_status/status_with_size.h"
38 enum class GargbageCollectOnWrite {
39 // Disable all automatic garbage collection on write.
42 // Allow up to a single sector, if needed, to be garbage collected on write.
45 // Allow as many sectors as needed be garbage collected on write.
49 enum class ErrorRecovery {
50 // Immediately do full recovery of any errors that are detected.
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.
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
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 = GargbageCollectOnWrite::kOneSector;
71 // When the KVS handles errors that are discovered, such as corrupt entries,
72 // not enough redundant copys of an entry, etc.
73 ErrorRecovery recovery = ErrorRecovery::kLazy;
75 // Verify an entry's checksum after reading it from flash.
76 bool verify_on_read = true;
78 // Verify an in-flash entry's checksum after writing it.
79 bool verify_on_write = true;
84 // KeyValueStores are declared as instances of
85 // KeyValueStoreBuffer<MAX_ENTRIES, MAX_SECTORS>, which allocates buffers for
86 // tracking entries and flash sectors.
88 // Initializes the key-value store. Must be called before calling other
93 // OK: KVS successfully initialized.
94 // DATA_LOSS: KVS initialized and is usable, but contains corrupt data.
95 // UNKNOWN: Unknown error. KVS is not initialized.
99 bool initialized() const {
100 return initialized_ == InitializationState::kReady;
103 // Reads the value of an entry in the KVS. The value is read into the provided
104 // buffer and the number of bytes read is returned. If desired, the read can
105 // be started at an offset.
107 // If the output buffer is too small for the value, Get returns
108 // RESOURCE_EXHAUSTED with the number of bytes read. The remainder of the
109 // value can be read by calling get with an offset.
111 // OK: the entry was successfully read
112 // NOT_FOUND: the key is not present in the KVS
113 // DATA_LOSS: found the entry, but the data was corrupted
114 // RESOURCE_EXHAUSTED: the buffer could not fit the entire value, but as
115 // many bytes as possible were written to it
116 // FAILED_PRECONDITION: the KVS is not initialized
117 // INVALID_ARGUMENT: key is empty or too long or value is too large
119 StatusWithSize Get(Key key,
120 std::span<std::byte> value,
121 size_t offset_bytes = 0) const;
123 // This overload of Get accepts a pointer to a trivially copyable object.
124 // If the value is an array, call Get with
125 // std::as_writable_bytes(std::span(array)), or pass a pointer to the array
126 // instead of the array itself.
127 template <typename Pointer,
128 typename = std::enable_if_t<std::is_pointer<Pointer>::value>>
129 Status Get(const Key& key, const Pointer& pointer) const {
130 using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
131 CheckThatObjectCanBePutOrGet<T>();
132 return FixedSizeGet(key, pointer, sizeof(T));
135 // Adds a key-value entry to the KVS. If the key was already present, its
136 // value is overwritten.
138 // The value may be a std::span of bytes or a trivially copyable object.
140 // In the current implementation, all keys in the KVS must have a unique hash.
141 // If Put is called with a key whose hash matches an existing key, nothing
142 // is added and ALREADY_EXISTS is returned.
144 // OK: the entry was successfully added or updated
145 // DATA_LOSS: checksum validation failed after writing the data
146 // RESOURCE_EXHAUSTED: there is not enough space to add the entry
147 // ALREADY_EXISTS: the entry could not be added because a different key
148 // with the same hash is already in the KVS
149 // FAILED_PRECONDITION: the KVS is not initialized
150 // INVALID_ARGUMENT: key is empty or too long or value is too large
152 template <typename T,
153 typename std::enable_if_t<ConvertsToSpan<T>::value>* = nullptr>
154 Status Put(const Key& key, const T& value) {
155 return PutBytes(key, std::as_bytes(internal::make_span(value)));
158 template <typename T,
159 typename std::enable_if_t<!ConvertsToSpan<T>::value>* = nullptr>
160 Status Put(const Key& key, const T& value) {
161 CheckThatObjectCanBePutOrGet<T>();
162 return PutBytes(key, std::as_bytes(std::span<const T>(&value, 1)));
165 // Removes a key-value entry from the KVS.
167 // OK: the entry was successfully added or updated
168 // NOT_FOUND: the key is not present in the KVS
169 // DATA_LOSS: checksum validation failed after recording the erase
170 // RESOURCE_EXHAUSTED: insufficient space to mark the entry as deleted
171 // FAILED_PRECONDITION: the KVS is not initialized
172 // INVALID_ARGUMENT: key is empty or too long
174 Status Delete(Key key);
176 // Returns the size of the value corresponding to the key.
178 // OK: the size was returned successfully
179 // NOT_FOUND: the key is not present in the KVS
180 // DATA_LOSS: checksum validation failed after reading the entry
181 // FAILED_PRECONDITION: the KVS is not initialized
182 // INVALID_ARGUMENT: key is empty or too long
184 StatusWithSize ValueSize(Key key) const;
186 // Perform all maintenance possible, including all neeeded repairing of
187 // corruption and garbage collection of reclaimable space in the KVS. When
188 // configured for manual recovery, this (along with FullMaintenance) is the
189 // only way KVS repair is triggered.
191 // - Heavy garbage collection of all reclaimable space, regardless of valid
192 // data in the sector.
193 Status HeavyMaintenance() {
194 return FullMaintenanceHelper(MaintenanceType::kHeavy);
197 // Perform all maintenance possible, including all neeeded repairing of
198 // corruption and garbage collection of reclaimable space in the KVS. When
199 // configured for manual recovery, this (along with HeavyMaintenance) is the
200 // only way KVS repair is triggered.
202 // - Regular will not garbage collect sectors with valid data unless the KVS
204 Status FullMaintenance() {
205 return FullMaintenanceHelper(MaintenanceType::kRegular);
208 // Perform a portion of KVS maintenance. If configured for at least lazy
209 // recovery, will do any needed repairing of corruption. Does garbage
210 // collection of part of the KVS, typically a single sector or similar unit
211 // that makes sense for the KVS implementation.
212 Status PartialMaintenance();
214 void LogDebugInfo() const;
216 // Classes and functions to support STL-style iteration.
221 // The key as a null-terminated string.
222 const char* key() const { return key_buffer_.data(); }
224 // Gets the value referred to by this iterator. Equivalent to
225 // KeyValueStore::Get.
226 StatusWithSize Get(std::span<std::byte> value_buffer,
227 size_t offset_bytes = 0) const {
228 return kvs_.Get(key(), *iterator_, value_buffer, offset_bytes);
231 template <typename Pointer,
232 typename = std::enable_if_t<std::is_pointer<Pointer>::value>>
233 Status Get(const Pointer& pointer) const {
234 using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
235 CheckThatObjectCanBePutOrGet<T>();
236 return kvs_.FixedSizeGet(key(), *iterator_, pointer, sizeof(T));
239 // Reads the size of the value referred to by this iterator. Equivalent to
240 // KeyValueStore::ValueSize.
241 StatusWithSize ValueSize() const { return kvs_.ValueSize(*iterator_); }
244 friend class iterator;
246 constexpr Item(const KeyValueStore& kvs,
247 const internal::EntryCache::const_iterator& item_iterator)
248 : kvs_(kvs), iterator_(item_iterator), key_buffer_{} {}
252 const KeyValueStore& kvs_;
253 internal::EntryCache::const_iterator iterator_;
255 // Buffer large enough for a null-terminated version of any valid key.
256 std::array<char, internal::Entry::kMaxKeyLength + 1> key_buffer_;
261 iterator& operator++();
263 iterator& operator++(int) { return operator++(); }
265 // Reads the entry's key from flash.
266 const Item& operator*() {
271 const Item* operator->() {
272 return &operator*(); // Read the key into the Item object.
275 constexpr bool operator==(const iterator& rhs) const {
276 return item_.iterator_ == rhs.item_.iterator_;
279 constexpr bool operator!=(const iterator& rhs) const {
280 return item_.iterator_ != rhs.item_.iterator_;
284 friend class KeyValueStore;
287 const KeyValueStore& kvs,
288 const internal::EntryCache::const_iterator& item_iterator)
289 : item_(kvs, item_iterator) {}
294 using const_iterator = iterator; // Standard alias for iterable types.
296 iterator begin() const;
297 iterator end() const { return iterator(*this, entry_cache_.end()); }
299 // Returns the number of valid entries in the KeyValueStore.
300 size_t size() const { return entry_cache_.present_entries(); }
302 size_t max_size() const { return entry_cache_.max_entries(); }
304 size_t empty() const { return size() == 0u; }
306 // Returns the number of transactions that have occurred since the KVS was
307 // first used. This value is retained across initializations, but is reset if
308 // the underlying flash is erased.
309 uint32_t transaction_count() const { return last_transaction_id_; }
311 struct StorageStats {
312 size_t writable_bytes;
314 size_t reclaimable_bytes;
315 size_t sector_erase_count;
316 size_t corrupt_sectors_recovered;
317 size_t missing_redundant_entries_recovered;
320 StorageStats GetStorageStats() const;
322 // Level of redundancy to use for writing entries.
323 size_t redundancy() const { return entry_cache_.redundancy(); }
325 bool error_detected() const { return error_detected_; }
327 // Maximum number of bytes allowed for a key-value combination.
328 size_t max_key_value_size_bytes() const {
329 return max_key_value_size_bytes(partition_.sector_size_bytes());
332 // Maximum number of bytes allowed for a given sector size for a key-value
334 static constexpr size_t max_key_value_size_bytes(
335 size_t partition_sector_size_bytes) {
336 return partition_sector_size_bytes - Entry::entry_overhead();
339 // Check KVS for any error conditions. Primarily intended for test and
341 bool CheckForErrors();
344 using Address = FlashPartition::Address;
345 using Entry = internal::Entry;
346 using KeyDescriptor = internal::KeyDescriptor;
347 using SectorDescriptor = internal::SectorDescriptor;
349 // In the future, will be able to provide additional EntryFormats for
350 // backwards compatibility.
351 KeyValueStore(FlashPartition* partition,
352 std::span<const EntryFormat> formats,
353 const Options& options,
355 Vector<SectorDescriptor>& sector_descriptor_list,
356 const SectorDescriptor** temp_sectors_to_skip,
357 Vector<KeyDescriptor>& key_descriptor_list,
361 using EntryMetadata = internal::EntryMetadata;
362 using EntryState = internal::EntryState;
364 template <typename T>
365 static constexpr void CheckThatObjectCanBePutOrGet() {
367 std::is_trivially_copyable<T>::value && !std::is_pointer<T>::value,
368 "Only trivially copyable, non-pointer objects may be Put and Get by "
369 "value. Any value may be stored by converting it to a byte std::span "
370 "with std::as_bytes(std::span(&value, 1)) or "
371 "std::as_writable_bytes(std::span(&value, 1)).");
374 Status InitializeMetadata();
375 Status LoadEntry(Address entry_address, Address* next_entry_address);
376 Status ScanForEntry(const SectorDescriptor& sector,
377 Address start_address,
378 Address* next_entry_address);
380 Status PutBytes(Key key, std::span<const std::byte> value);
382 StatusWithSize ValueSize(const EntryMetadata& metadata) const;
384 Status ReadEntry(const EntryMetadata& metadata, Entry& entry) const;
386 // Finds the metadata for an entry matching a particular key. Searches for a
387 // KeyDescriptor that matches this key and sets *metadata to point to it if
390 // OK: there is a matching descriptor and *metadata is set
391 // NOT_FOUND: there is no descriptor that matches this key, but this key
392 // has a unique hash (and could potentially be added to the
394 // ALREADY_EXISTS: there is no descriptor that matches this key, but the
395 // key's hash collides with the hash for an existing
398 Status FindEntry(Key key, EntryMetadata* metadata) const;
400 // Searches for a KeyDescriptor that matches this key and sets *metadata to
401 // point to it if one is found.
403 // OK: there is a matching descriptor and *metadata is set
404 // NOT_FOUND: there is no descriptor that matches this key
406 Status FindExisting(Key key, EntryMetadata* metadata) const;
408 StatusWithSize Get(Key key,
409 const EntryMetadata& metadata,
410 std::span<std::byte> value_buffer,
411 size_t offset_bytes) const;
413 Status FixedSizeGet(Key key, void* value, size_t size_bytes) const;
415 Status FixedSizeGet(Key key,
416 const EntryMetadata& descriptor,
418 size_t size_bytes) const;
420 Status CheckWriteOperation(Key key) const;
421 Status CheckReadOperation(Key key) const;
423 Status WriteEntryForExistingKey(EntryMetadata& metadata,
424 EntryState new_state,
426 std::span<const std::byte> value);
428 Status WriteEntryForNewKey(Key key, std::span<const std::byte> value);
430 Status WriteEntry(Key key,
431 std::span<const std::byte> value,
432 EntryState new_state,
433 EntryMetadata* prior_metadata = nullptr,
434 const internal::Entry* prior_entry = nullptr);
436 EntryMetadata CreateOrUpdateKeyDescriptor(const Entry& new_entry,
438 EntryMetadata* prior_metadata,
441 EntryMetadata UpdateKeyDescriptor(const Entry& entry,
443 EntryMetadata* prior_metadata,
446 Status GetAddressesForWrite(Address* write_addresses, size_t write_size);
448 Status GetSectorForWrite(SectorDescriptor** sector,
450 std::span<const Address> addresses_to_skip);
452 Status MarkSectorCorruptIfNotOk(Status status, SectorDescriptor* sector);
454 Status AppendEntry(const Entry& entry,
456 std::span<const std::byte> value);
458 StatusWithSize CopyEntryToSector(Entry& entry,
459 SectorDescriptor* new_sector,
460 Address new_address);
462 Status RelocateEntry(const EntryMetadata& metadata,
463 KeyValueStore::Address& address,
464 std::span<const Address> addresses_to_skip);
466 // Perform all maintenance possible, including all neeeded repairing of
467 // corruption and garbage collection of reclaimable space in the KVS. When
468 // configured for manual recovery, this is the only way KVS repair is
471 // - Regular will not garbage collect sectors with valid data unless the KVS
473 // - Heavy will garbage collect all reclaimable space regardless of valid data
475 enum class MaintenanceType {
479 Status FullMaintenanceHelper(MaintenanceType maintenance_type);
481 // Find and garbage collect a singe sector that does not include an address to
483 Status GarbageCollect(std::span<const Address> addresses_to_skip);
485 Status RelocateKeyAddressesInSector(
486 SectorDescriptor& sector_to_gc,
487 const EntryMetadata& descriptor,
488 std::span<const Address> addresses_to_skip);
490 Status GarbageCollectSector(SectorDescriptor& sector_to_gc,
491 std::span<const Address> addresses_to_skip);
493 // Ensure that all entries are on the primary (first) format. Entries that are
494 // not on the primary format are rewritten.
496 // Return: status + number of entries updated.
497 StatusWithSize UpdateEntriesToPrimaryFormat();
499 Status AddRedundantEntries(EntryMetadata& metadata);
501 Status RepairCorruptSectors();
503 Status EnsureFreeSectorExists();
505 Status EnsureEntryRedundancy();
511 internal::Entry CreateEntry(Address address,
513 std::span<const std::byte> value,
516 void LogSectors() const;
517 void LogKeyDescriptor() const;
519 FlashPartition& partition_;
520 const internal::EntryFormats formats_;
522 // List of sectors used by this KVS.
523 internal::Sectors sectors_;
525 // Unordered list of KeyDescriptors. Finding a key requires scanning and
526 // verifying a match by reading the actual entry.
527 internal::EntryCache entry_cache_;
531 // Threshold value for when to garbage collect all stale data. Above the
532 // threshold, GC all reclaimable bytes regardless of if valid data is in
533 // sector. Below the threshold, only GC sectors with reclaimable bytes and no
534 // valid bytes. The threshold is based on the portion of KVS capacity used by
536 static constexpr size_t kGcUsageThresholdPercentage = 70;
538 enum class InitializationState {
539 // KVS Init() has not been called and KVS is not usable.
542 // KVS Init() run but not all the needed invariants are met for an operating
543 // KVS. KVS is not writable, but read operaions are possible.
546 // KVS is fully ready for use.
549 InitializationState initialized_;
551 // error_detected_ needs to be set from const KVS methods (such as Get), so
553 mutable bool error_detected_;
555 struct InternalStats {
556 size_t sector_erase_count;
557 size_t corrupt_sectors_recovered;
558 size_t missing_redundant_entries_recovered;
560 InternalStats internal_stats_;
562 uint32_t last_transaction_id_;
565 template <size_t kMaxEntries,
566 size_t kMaxUsableSectors,
567 size_t kRedundancy = 1,
568 size_t kEntryFormats = 1>
569 class KeyValueStoreBuffer : public KeyValueStore {
571 // Constructs a KeyValueStore on the partition, with support for one
572 // EntryFormat (kEntryFormats must be 1).
573 KeyValueStoreBuffer(FlashPartition* partition,
574 const EntryFormat& format,
575 const Options& options = {})
576 : KeyValueStoreBuffer(
578 std::span<const EntryFormat, kEntryFormats>(
579 reinterpret_cast<const EntryFormat (&)[1]>(format)),
581 static_assert(kEntryFormats == 1,
582 "kEntryFormats EntryFormats must be specified");
585 // Constructs a KeyValueStore on the partition. Supports multiple entry
586 // formats. The first EntryFormat is used for new entries.
587 KeyValueStoreBuffer(FlashPartition* partition,
588 std::span<const EntryFormat, kEntryFormats> formats,
589 const Options& options = {})
590 : KeyValueStore(partition,
595 temp_sectors_to_skip_,
598 std::copy(formats.begin(), formats.end(), formats_.begin());
602 static_assert(kMaxEntries > 0u);
603 static_assert(kMaxUsableSectors > 0u);
604 static_assert(kRedundancy > 0u);
605 static_assert(kEntryFormats > 0u);
607 Vector<SectorDescriptor, kMaxUsableSectors> sectors_;
609 // Allocate space for an list of SectorDescriptors to avoid while searching
610 // for space to write entries. This is used to avoid changing sectors that are
611 // reserved for a new entry or marked as having other redundant copies of an
612 // entry. Up to kRedundancy sectors are reserved for a new entry, and up to
613 // kRedundancy - 1 sectors can have redundant copies of an entry, giving a
614 // maximum of 2 * kRedundancy - 1 sectors to avoid.
615 const SectorDescriptor* temp_sectors_to_skip_[2 * kRedundancy - 1];
617 // KeyDescriptors for use by the KVS's EntryCache.
618 Vector<KeyDescriptor, kMaxEntries> key_descriptors_;
620 // An array of addresses associated with the KeyDescriptors for use with the
621 // EntryCache. To support having KeyValueStores with different redundancies,
622 // the addresses are stored in a parallel array instead of inside
624 internal::EntryCache::AddressList<kRedundancy, kMaxEntries> addresses_;
626 // EntryFormats that can be read by this KeyValueStore.
627 std::array<EntryFormat, kEntryFormats> formats_;