| // Copyright 2020 The Pigweed Authors |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); you may not |
| // use this file except in compliance with the License. You may obtain a copy of |
| // the License at |
| // |
| // https://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT |
| // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the |
| // License for the specific language governing permissions and limitations under |
| // the License. |
| #pragma once |
| |
| #include <array> |
| #include <cstddef> |
| #include <cstdint> |
| #include <string_view> |
| |
| #include "pw_kvs/checksum.h" |
| #include "pw_kvs/flash_memory.h" |
| #include "pw_span/span.h" |
| #include "pw_status/status.h" |
| #include "pw_status/status_with_size.h" |
| |
| // TODO: Resolve uses of partition_.sector_count() vs kMaxUsableSectors. |
| |
| namespace pw::kvs { |
| namespace internal { |
| |
| template <typename T, typename = decltype(span(std::declval<T>()))> |
| constexpr bool ConvertsToSpan(int) { |
| return true; |
| } |
| |
| // If the expression span(T) fails, then the type can't be converted to a span. |
| template <typename T> |
| constexpr bool ConvertsToSpan(...) { |
| return false; |
| } |
| |
| } // namespace internal |
| |
| // Traits class to detect if the type is a span. std::is_same is insufficient |
| // because span is a class template. This is used to ensure that the correct |
| // overload of the Put function is selected. |
| template <typename T> |
| using ConvertsToSpan = |
| std::bool_constant<internal::ConvertsToSpan<std::remove_reference_t<T>>(0)>; |
| |
| // Internal-only persistent storage header format. |
| struct EntryHeader; |
| |
| struct EntryHeaderFormat { |
| uint32_t magic; // unique identifier |
| ChecksumAlgorithm* checksum; |
| }; |
| |
| // TODO: Select the appropriate defaults, add descriptions. |
| struct Options { |
| bool partial_gc_on_write = true; |
| bool verify_on_read = true; |
| bool verify_on_write = true; |
| }; |
| |
| class KeyValueStore { |
| public: |
| // TODO: Make these configurable |
| static constexpr size_t kMaxKeyLength = 64; |
| static constexpr size_t kMaxEntries = 64; |
| static constexpr size_t kUsableSectors = 64; |
| |
| // +1 for null-terminator. |
| typedef std::array<char, kMaxKeyLength + 1> KeyBuffer; |
| |
| // In the future, will be able to provide additional EntryHeaderFormats for |
| // backwards compatibility. |
| constexpr KeyValueStore(FlashPartition* partition, |
| const EntryHeaderFormat& format, |
| const Options& options = {}) |
| : partition_(*partition), |
| entry_header_format_(format), |
| options_(options), |
| key_descriptor_list_{}, |
| key_descriptor_list_size_(0), |
| sector_map_{}, |
| last_written_sector_(0) {} |
| |
| Status Init(); |
| bool initialized() const { return false; } // TODO: Implement this |
| |
| StatusWithSize Get(std::string_view key, span<std::byte> value) const; |
| |
| template <typename T> |
| Status Get(const std::string_view& key, T* value) { |
| static_assert(std::is_trivially_copyable<T>(), "KVS values must copyable"); |
| static_assert(!std::is_pointer<T>(), "KVS values cannot be pointers"); |
| |
| // TODO: Re-enable this check once we are further along. |
| #if 0 |
| // Ensure that the size of the stored value matches the size of the type. |
| // Otherwise, report error. This check avoids potential memory corruption. |
| StatusWithSize result = ValueSize(key); |
| if (!result.ok()) { |
| return result.status(); |
| } |
| if (result.size() != sizeof(T)) { |
| return Status::INVALID_ARGUMENT; |
| } |
| #endif |
| return Get(key, as_writable_bytes(span(value, 1))).status(); |
| } |
| |
| Status Put(std::string_view key, span<const std::byte> value); |
| |
| template <typename T, |
| typename = std::enable_if_t<std::is_trivially_copyable_v<T> && |
| !std::is_pointer_v<T> && |
| !ConvertsToSpan<T>::value>> |
| Status Put(const std::string_view& key, const T& value) { |
| return Put(key, as_bytes(span(&value, 1))); |
| } |
| |
| Status Delete(std::string_view key); |
| |
| StatusWithSize ValueSize(std::string_view key) const { |
| // TODO: Implement this! For now, just accept whatever size. |
| // return Status::OK; |
| (void)key; |
| return Status::UNIMPLEMENTED; |
| } |
| |
| void LogDebugInfo(); |
| |
| // Classes and functions to support STL-style iteration. |
| class Iterator; |
| |
| class Entry { |
| public: |
| // Guaranteed to be null-terminated |
| std::string_view key() const { return key_buffer_.data(); } |
| |
| Status Get(span<std::byte> value_buffer) const { |
| return kvs_.Get(key(), value_buffer).status(); |
| } |
| |
| template <typename T> |
| Status Get(T* value) const { |
| return kvs_.Get(key(), value); |
| } |
| |
| StatusWithSize ValueSize() const { return kvs_.ValueSize(key()); } |
| |
| private: |
| friend class Iterator; |
| |
| constexpr Entry(const KeyValueStore& kvs) : kvs_(kvs), key_buffer_{} {} |
| |
| const KeyValueStore& kvs_; |
| std::array<char, kMaxKeyLength + 1> key_buffer_; // +1 for null-terminator |
| }; |
| |
| class Iterator { |
| public: |
| Iterator& operator++() { |
| index_ += 1; |
| return *this; |
| } |
| |
| Iterator& operator++(int) { return operator++(); } |
| |
| // Reads the entry's key from flash. |
| const Entry& operator*(); |
| |
| const Entry* operator->() { |
| operator*(); // Read the key into the Entry object. |
| return &entry_; |
| } |
| |
| constexpr bool operator==(const Iterator& rhs) const { |
| return index_ == rhs.index_; |
| } |
| |
| constexpr bool operator!=(const Iterator& rhs) const { |
| return index_ != rhs.index_; |
| } |
| |
| private: |
| friend class KeyValueStore; |
| |
| constexpr Iterator(const KeyValueStore& kvs, size_t index) |
| : entry_(kvs), index_(index) {} |
| |
| Entry entry_; |
| size_t index_; |
| }; |
| |
| // Standard aliases for iterator types. |
| using iterator = Iterator; |
| using const_iterator = Iterator; |
| |
| Iterator begin() const { return Iterator(*this, 0); } |
| Iterator end() const { return Iterator(*this, empty() ? 0 : size() - 1); } |
| |
| // Returns the number of valid entries in the KeyValueStore. |
| size_t size() const { return key_descriptor_list_size_; } |
| |
| static constexpr size_t max_size() { return kMaxKeyLength; } |
| |
| size_t empty() const { return size() == 0u; } |
| |
| private: |
| using Address = FlashPartition::Address; |
| |
| struct KeyDescriptor { |
| uint32_t key_hash; |
| uint32_t key_version; |
| Address address; // In partition address. |
| }; |
| |
| struct SectorDescriptor { |
| uint16_t tail_free_bytes; |
| uint16_t valid_bytes; // sum of sizes of valid entries |
| |
| bool HasSpace(size_t required_space) const { |
| return (tail_free_bytes >= required_space); |
| } |
| }; |
| |
| Status InvalidOperation(std::string_view key) const; |
| |
| static constexpr bool InvalidKey(std::string_view key) { |
| return key.empty() || (key.size() > kMaxKeyLength); |
| } |
| |
| Status FindKeyDescriptor(std::string_view key, |
| const KeyDescriptor** result) const; |
| |
| // Non-const version of FindKeyDescriptor. |
| Status FindKeyDescriptor(std::string_view key, KeyDescriptor** result) { |
| return static_cast<const KeyValueStore&>(*this).FindKeyDescriptor( |
| key, const_cast<const KeyDescriptor**>(result)); |
| } |
| |
| Status ReadEntryHeader(const KeyDescriptor& descriptor, |
| EntryHeader* header) const; |
| Status ReadEntryKey(const KeyDescriptor& descriptor, |
| size_t key_length, |
| char* key) const; |
| |
| StatusWithSize ReadEntryValue(const KeyDescriptor& key_descriptor, |
| const EntryHeader& header, |
| span<std::byte> value) const; |
| |
| Status ValidateEntryChecksum(const EntryHeader& header, |
| std::string_view key, |
| span<const std::byte> value) const; |
| |
| Status LoadEntry(Address entry_address, Address* next_entry_address); |
| Status AppendNewOrOverwriteStaleExistingDescriptor( |
| const KeyDescriptor& key_descriptor); |
| Status AppendEmptyDescriptor(KeyDescriptor** new_descriptor); |
| |
| // This version reads from flash. |
| Status ValidateEntryChecksum(const EntryHeader& header, |
| std::string_view key, |
| const KeyDescriptor& entry) const; |
| |
| Status WriteEntryForExistingKey(KeyDescriptor* key_descriptor, |
| std::string_view key, |
| span<const std::byte> value); |
| |
| Status WriteEntryForNewKey(std::string_view key, span<const std::byte> value); |
| |
| Status RelocateEntry(KeyDescriptor& key_descriptor); |
| |
| SectorDescriptor* FindSectorWithSpace(size_t size); |
| |
| Status FindOrRecoverSectorWithSpace(SectorDescriptor** sector, size_t size); |
| |
| Status GarbageCollectOneSector(SectorDescriptor** sector); |
| |
| SectorDescriptor* FindSectorToGarbageCollect(); |
| |
| bool HeaderLooksLikeUnwrittenData(const EntryHeader& header) const; |
| |
| KeyDescriptor* FindDescriptor(uint32_t hash); |
| |
| Status AppendEntry(SectorDescriptor* sector, |
| KeyDescriptor* key_descriptor, |
| std::string_view key, |
| span<const std::byte> value); |
| |
| Status VerifyEntry(SectorDescriptor* sector, KeyDescriptor* key_descriptor); |
| |
| span<const std::byte> CalculateEntryChecksum( |
| const EntryHeader& header, |
| std::string_view key, |
| span<const std::byte> value) const; |
| |
| bool AddressInSector(const SectorDescriptor& sector, Address address) const { |
| const Address sector_base = SectorBaseAddress(§or); |
| const Address sector_end = sector_base + partition_.sector_size_bytes(); |
| |
| return ((address >= sector_base) && (address < sector_end)); |
| } |
| |
| bool SectorEmpty(const SectorDescriptor& sector) const { |
| return (sector.tail_free_bytes == partition_.sector_size_bytes()); |
| } |
| |
| size_t RecoverableBytes(const SectorDescriptor& sector) { |
| return partition_.sector_size_bytes() - sector.valid_bytes - |
| sector.tail_free_bytes; |
| } |
| |
| Address SectorBaseAddress(const SectorDescriptor* sector) const { |
| return (sector - sector_map_.data()) * partition_.sector_size_bytes(); |
| } |
| |
| Address NextWritableAddress(SectorDescriptor* sector) const { |
| return SectorBaseAddress(sector) + partition_.sector_size_bytes() - |
| sector->tail_free_bytes; |
| } |
| |
| bool KeyListFull() const { return key_descriptor_list_size_ == kMaxEntries; } |
| |
| span<KeyDescriptor> key_descriptors() { |
| return span(key_descriptor_list_.data(), key_descriptor_list_size_); |
| } |
| |
| span<const KeyDescriptor> key_descriptors() const { |
| return span(key_descriptor_list_.data(), key_descriptor_list_size_); |
| } |
| |
| FlashPartition& partition_; |
| EntryHeaderFormat entry_header_format_; |
| Options options_; |
| |
| // Map is unordered; finding a key requires scanning and |
| // verifying a match by reading the actual entry. |
| std::array<KeyDescriptor, kMaxEntries> key_descriptor_list_; |
| size_t key_descriptor_list_size_; // Number of valid entries in |
| // key_descriptor_list_ |
| |
| // This is dense, so sector_id == indexof(SectorDescriptor) in sector_map |
| std::array<SectorDescriptor, kUsableSectors> sector_map_; |
| size_t last_written_sector_; |
| |
| bool enabled_ = false; |
| }; |
| |
| } // namespace pw::kvs |