blob: a36f03cf3fdcb8d73c176af6b49a5773bbfcc92f [file] [log] [blame]
// 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
// 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"
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 =
// 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 {
// TODO: Make these configurable
static constexpr size_t kMaxKeyLength = 64;
static constexpr size_t kMaxEntries = 64;
static constexpr size_t kUsableSectors = 64;
// 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),
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");
StatusWithSize result = ValueSize(key);
if (!result.ok()) {
return result.status();
if (result.size() != sizeof(T)) {
return Status::INVALID_ARGUMENT;
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> &&
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 {
return Status::UNIMPLEMENTED;
// Classes and functions to support STL-style iteration.
class Iterator;
class Entry {
// Guaranteed to be null-terminated
std::string_view key() const { return; }
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()); }
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 {
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_;
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; }
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 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();
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(&sector);
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 -
Address SectorBaseAddress(const SectorDescriptor* sector) const {
return (sector - * partition_.sector_size_bytes();
Address NextWritableAddress(SectorDescriptor* sector) const {
return SectorBaseAddress(sector) + partition_.sector_size_bytes() -
bool KeyListFull() const { return key_descriptor_list_size_ == kMaxEntries; }
span<KeyDescriptor> key_descriptors() {
return span(, key_descriptor_list_size_);
span<const KeyDescriptor> key_descriptors() const {
return span(, 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_; // TODO: this variable is not used!
} // namespace pw::kvs