pw_kvs: Initial commit of key value store module
This commit does not build or pass presubmit checks.
Change-Id: I3d4dd393ede1c778888c3cd8be9f12dfbf92fb88
diff --git a/pw_kvs/public/pw_kvs/flash.h b/pw_kvs/public/pw_kvs/flash.h
new file mode 100644
index 0000000..5cb80cd
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/flash.h
@@ -0,0 +1,33 @@
+// 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 "pw_kvs/devices/flash_memory.h"
+
+namespace pw {
+
+// Writes a buffer which is not guaranteed to be aligned, pads remaining
+// bytes with 0.
+Status PaddedWrite(FlashPartition* partition,
+ FlashPartition::Address address,
+ const uint8_t* buffer,
+ uint16_t size);
+
+// Read into a buffer when size is not guaranteed to be aligned.
+Status UnalignedRead(FlashPartition* partition,
+ uint8_t* buffer,
+ FlashPartition::Address address,
+ uint16_t size);
+
+} // namespace pw
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
new file mode 100644
index 0000000..707f128
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -0,0 +1,377 @@
+// 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 <algorithm>
+
+#include "pw_kvs/assert.h"
+#include "pw_kvs/logging.h"
+#include "pw_kvs/peripherals/partition_table_entry.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/status_macros.h"
+
+namespace pw {
+class FlashMemory {
+ public:
+ // The flash address is in the range of: 0 to FlashSize.
+ typedef uint32_t Address;
+ constexpr FlashMemory(uint32_t sector_size,
+ uint32_t sector_count,
+ uint8_t alignment,
+ uint32_t start_address = 0,
+ uint32_t sector_start = 0,
+ uint8_t erased_memory_content = 0xFF)
+ : sector_size_(sector_size),
+ flash_sector_count_(sector_count),
+ alignment_(alignment),
+ start_address_(start_address),
+ sector_start_(sector_start),
+ erased_memory_content_(erased_memory_content) {}
+
+ virtual Status Enable() = 0;
+ virtual Status Disable() = 0;
+ virtual bool IsEnabled() const = 0;
+ virtual Status SelfTest() { return Status::UNIMPLEMENTED; }
+
+ // Erase num_sectors starting at a given address. Blocking call.
+ // Address should be on a sector boundary.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or sector count is invalid.
+ // UNKNOWN, on HAL error
+ virtual Status Erase(Address flash_address, uint32_t num_sectors) = 0;
+
+ // Reads bytes from flash into buffer. Blocking call.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ virtual Status Read(uint8_t* destination_ram_address,
+ Address source_flash_address,
+ uint32_t len) = 0;
+
+ // Writes bytes to flash. Blocking call.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ virtual Status Write(Address destination_flash_address,
+ const uint8_t* source_ram_address,
+ uint32_t len) = 0;
+
+ // Convert an Address to an MCU pointer, this can be used for memory
+ // mapped reads. Return NULL if the memory is not memory mapped.
+ virtual uint8_t* FlashAddressToMcuAddress(Address address) const {
+ return nullptr;
+ }
+
+ // GetStartSector() is useful for FlashMemory instances where the
+ // sector start is not 0. (ex.: cases where there are portions of flash
+ // that should be handled independently).
+ constexpr uint32_t GetStartSector() const { return sector_start_; }
+ constexpr uint32_t GetSectorSizeBytes() const { return sector_size_; }
+ constexpr uint32_t GetSectorCount() const { return flash_sector_count_; }
+ constexpr uint8_t GetAlignmentBytes() const { return alignment_; }
+ constexpr uint32_t GetSizeBytes() const {
+ return sector_size_ * flash_sector_count_;
+ }
+ // Address of the start of flash (the address of sector 0)
+ constexpr uint32_t GetStartAddress() const { return start_address_; }
+ constexpr uint8_t GetErasedMemoryContent() const {
+ return erased_memory_content_;
+ }
+
+ private:
+ const uint32_t sector_size_;
+ const uint32_t flash_sector_count_;
+ const uint8_t alignment_;
+ const uint32_t start_address_;
+ const uint32_t sector_start_;
+ const uint8_t erased_memory_content_;
+};
+
+// Exposes a sub-sector sized region of flash memory that cannot be erased.
+// It can be thought of as one pseudo-sector that is sized exactly as provided.
+//
+// TODO(b/117553777): This makes a little more sense as a SubSectorPartition,
+// but PartitionTableEntry currently assumes all partitions fill entire sectors.
+// Revisit when PartitionTable is refactored.
+class FlashMemorySubSector : public FlashMemory {
+ public:
+ constexpr FlashMemorySubSector(FlashMemory* flash,
+ uint32_t start_address,
+ uint32_t size)
+ : FlashMemory(size,
+ 1, // Round up to "1" sector.
+ flash->GetAlignmentBytes(),
+ start_address,
+ // Calculate the sector for this start address.
+ flash->GetStartSector() +
+ ((start_address - flash->GetStartAddress()) /
+ flash->GetSectorSizeBytes())),
+ flash_(*CHECK_NOTNULL(flash)),
+ base_offset_(start_address - flash->GetStartAddress()) {
+ // Make sure we're not specifying a region of flash larger than
+ // that which the underlying FlashMemory supports.
+ CHECK(start_address >= flash->GetStartAddress());
+ CHECK(size <= flash->GetSectorSizeBytes());
+ CHECK(start_address + size <=
+ flash->GetStartAddress() + flash->GetSizeBytes());
+ CHECK_EQ(0, start_address % flash->GetAlignmentBytes());
+ CHECK_EQ(0, size % flash->GetAlignmentBytes());
+ }
+
+ Status Enable() override { return flash_.Enable(); }
+ Status Disable() override { return flash_.Disable(); }
+ bool IsEnabled() const override { return flash_.IsEnabled(); }
+ Status SelfTest() override { return flash_.SelfTest(); }
+
+ Status Erase(Address flash_address, uint32_t num_sectors) override {
+ return Status::UNIMPLEMENTED;
+ }
+
+ Status Read(uint8_t* destination_ram_address,
+ Address source_flash_address,
+ uint32_t len) override {
+ return flash_.Read(destination_ram_address, source_flash_address, len);
+ }
+
+ Status Write(Address destination_flash_address,
+ const uint8_t* source_ram_address,
+ uint32_t len) override {
+ return flash_.Write(destination_flash_address, source_ram_address, len);
+ }
+
+ uint8_t* FlashAddressToMcuAddress(Address address) const override {
+ return flash_.FlashAddressToMcuAddress(base_offset_ + address);
+ }
+
+ private:
+ FlashMemory& flash_;
+ // Value to add to addresses to get to the underlying flash_ address.
+ const Address base_offset_;
+};
+
+class FlashPartition {
+ public:
+ // The flash address is in the range of: 0 to PartitionSize.
+ typedef uint32_t Address;
+
+ constexpr FlashPartition(
+ FlashMemory* flash,
+ uint32_t start_sector_index,
+ uint32_t sector_count,
+ PartitionPermission permission = PartitionPermission::kReadAndWrite)
+ : flash_(*flash),
+ start_sector_index_(start_sector_index),
+ sector_count_(sector_count),
+ permission_(permission) {}
+
+ constexpr FlashPartition(FlashMemory* flash, PartitionTableEntry entry)
+ : flash_(*flash),
+ start_sector_index_(entry.partition_start_sector_index),
+ sector_count_(entry.partition_end_sector_index -
+ entry.partition_start_sector_index + 1),
+ permission_(entry.partition_permission) {}
+
+ // Erase num_sectors starting at a given address. Blocking call.
+ // Address should be on a sector boundary.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or sector count is invalid.
+ // PERMISSION_DENIED, if partition is read only.
+ // UNKNOWN, on HAL error
+ virtual Status Erase(Address address, uint32_t num_sectors) {
+ RETURN_STATUS_IF(permission_ == PartitionPermission::kReadOnly,
+ Status::PERMISSION_DENIED);
+ RETURN_IF_ERROR(CheckBounds(address, num_sectors * GetSectorSizeBytes()));
+ return flash_.Erase(PartitionToFlashAddress(address), num_sectors);
+ }
+
+ // Reads bytes from flash into buffer. Blocking call.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ virtual Status Read(uint8_t* destination_ram_address,
+ Address source_flash_address,
+ uint32_t len) {
+ RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+ return flash_.Read(destination_ram_address,
+ PartitionToFlashAddress(source_flash_address),
+ len);
+ }
+
+ // Writes bytes to flash. Blocking call.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // PERMISSION_DENIED, if partition is read only.
+ // UNKNOWN, on HAL error
+ virtual Status Write(Address destination_flash_address,
+ const uint8_t* source_ram_address,
+ uint32_t len) {
+ RETURN_STATUS_IF(permission_ == PartitionPermission::kReadOnly,
+ Status::PERMISSION_DENIED);
+ RETURN_IF_ERROR(CheckBounds(destination_flash_address, len));
+ return flash_.Write(PartitionToFlashAddress(destination_flash_address),
+ source_ram_address,
+ len);
+ }
+
+ // Check to see if chunk of flash memory is erased. Address and len need to
+ // be aligned with FlashMemory.
+ // Returns: OK, on success.
+ // TIMEOUT, on timeout.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ virtual Status IsChunkErased(Address source_flash_address,
+ uint32_t len,
+ bool* is_erased) {
+ // Max alignment is artifical to keep the stack usage low for this
+ // function. Using 16 because it's the alignment of encrypted flash.
+ const uint8_t kMaxAlignment = 16;
+ // Relying on Read() to check address and len arguments.
+ RETURN_STATUS_IF(!is_erased, Status::INVALID_ARGUMENT);
+ uint8_t alignment = GetAlignmentBytes();
+ RETURN_STATUS_IF(alignment > kMaxAlignment, Status::INVALID_ARGUMENT);
+ RETURN_STATUS_IF(kMaxAlignment % alignment, Status::INVALID_ARGUMENT);
+ RETURN_STATUS_IF(len % alignment, Status::INVALID_ARGUMENT);
+
+ uint8_t buffer[kMaxAlignment];
+ uint8_t erased_pattern_buffer[kMaxAlignment];
+ size_t offset = 0;
+ memset(erased_pattern_buffer,
+ flash_.GetErasedMemoryContent(),
+ sizeof(erased_pattern_buffer));
+ *is_erased = false;
+ while (len > 0) {
+ // Check earlier that len is aligned, no need to round up
+ uint16_t read_size = std::min(static_cast<uint32_t>(sizeof(buffer)), len);
+ RETURN_IF_ERROR(Read(buffer, source_flash_address + offset, read_size));
+ if (memcmp(buffer, erased_pattern_buffer, read_size)) {
+ // Detected memory chunk is not entirely erased
+ return Status::OK;
+ }
+ offset += read_size;
+ len -= read_size;
+ }
+ *is_erased = true;
+ return Status::OK;
+ }
+
+ constexpr uint32_t GetSectorSizeBytes() const {
+ return flash_.GetSectorSizeBytes();
+ }
+
+ uint32_t GetSizeBytes() const {
+ return GetSectorCount() * GetSectorSizeBytes();
+ }
+
+ virtual uint8_t GetAlignmentBytes() const {
+ return flash_.GetAlignmentBytes();
+ }
+
+ virtual uint32_t GetSectorCount() const { return sector_count_; }
+
+ // Convert a FlashMemory::Address to an MCU pointer, this can be used for
+ // memory mapped reads. Return NULL if the memory is not memory mapped.
+ uint8_t* PartitionAddressToMcuAddress(Address address) const {
+ return flash_.FlashAddressToMcuAddress(PartitionToFlashAddress(address));
+ }
+
+ FlashMemory::Address PartitionToFlashAddress(Address address) const {
+ return flash_.GetStartAddress() +
+ (start_sector_index_ - flash_.GetStartSector()) *
+ GetSectorSizeBytes() +
+ address;
+ }
+
+ protected:
+ Status CheckBounds(Address address, uint32_t len) const {
+ if (address + len > GetSizeBytes()) {
+ LOG(ERROR) << "Attempted out-of-bound flash memory access (address:"
+ << address << " length:" << len << ")";
+ return Status::INVALID_ARGUMENT;
+ }
+ return Status::OK;
+ }
+
+ private:
+ FlashMemory& flash_;
+ const uint32_t start_sector_index_;
+ const uint32_t sector_count_;
+ const PartitionPermission permission_;
+};
+
+// FlashSubPartition defines a new partition which maps itself as a smaller
+// piece of another partition. This can used when a partition has special
+// behaviours (for example encrypted flash).
+// For example, this will be the first sector of test_partition:
+// FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+class FlashSubPartition : public FlashPartition {
+ public:
+ constexpr FlashSubPartition(FlashPartition* parent_partition,
+ uint32_t start_sector_index,
+ uint32_t sector_count)
+ : FlashPartition(*parent_partition),
+ partition_(parent_partition),
+ start_sector_index_(start_sector_index),
+ sector_count_(sector_count) {}
+
+ Status Erase(Address address, uint32_t num_sectors) override {
+ RETURN_IF_ERROR(CheckBounds(address, num_sectors * GetSectorSizeBytes()));
+ return partition_->Erase(ParentAddress(address), num_sectors);
+ }
+
+ Status Read(uint8_t* destination_ram_address,
+ Address source_flash_address,
+ uint32_t len) override {
+ RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+ return partition_->Read(
+ destination_ram_address, ParentAddress(source_flash_address), len);
+ }
+
+ Status Write(Address destination_flash_address,
+ const uint8_t* source_ram_address,
+ uint32_t len) override {
+ RETURN_IF_ERROR(CheckBounds(destination_flash_address, len));
+ return partition_->Write(
+ ParentAddress(destination_flash_address), source_ram_address, len);
+ }
+
+ Status IsChunkErased(Address source_flash_address,
+ uint32_t len,
+ bool* is_erased) override {
+ RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+ return partition_->IsChunkErased(
+ ParentAddress(source_flash_address), len, is_erased);
+ }
+
+ uint8_t GetAlignmentBytes() const override {
+ return partition_->GetAlignmentBytes();
+ }
+
+ uint32_t GetSectorCount() const override { return sector_count_; }
+
+ private:
+ Address ParentAddress(Address address) const {
+ return address + start_sector_index_ * partition_->GetSectorSizeBytes();
+ }
+ FlashPartition* partition_;
+ const uint32_t start_sector_index_;
+ const uint32_t sector_count_;
+};
+
+} // namespace pw
diff --git a/pw_kvs/public/pw_kvs/in_memory_fake_flash.h b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
new file mode 100644
index 0000000..a67c770
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
@@ -0,0 +1,92 @@
+// 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 "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/status_macros.h"
+
+namespace pw {
+
+// This creates a buffer which mimics the behaviour of flash (requires erase,
+// before write, checks alignments, and is addressed in sectors).
+template <uint32_t kSectorSize, uint16_t kSectorCount>
+class InMemoryFakeFlash : public FlashMemory {
+ public:
+ InMemoryFakeFlash(uint8_t alignment = 1) // default 8 bit alignment
+ : FlashMemory(kSectorSize, kSectorCount, alignment) {}
+
+ // Always enabled
+ Status Enable() override { return Status::OK; }
+ Status Disable() override { return Status::OK; }
+ bool IsEnabled() const override { return true; }
+
+ // Erase num_sectors starting at a given address. Blocking call.
+ // Address should be on a sector boundary.
+ // Returns: OK, on success.
+ // INVALID_ARGUMENT, if address or sector count is invalid.
+ // UNKNOWN, on HAL error
+ Status Erase(Address addr, uint32_t num_sectors) override {
+ RETURN_STATUS_IF(addr % GetSectorSizeBytes() != 0,
+ Status::INVALID_ARGUMENT);
+ RETURN_STATUS_IF(
+ addr / GetSectorSizeBytes() + num_sectors > GetSectorCount(),
+ Status::UNKNOWN);
+ RETURN_STATUS_IF(addr % GetAlignmentBytes() != 0, Status::INVALID_ARGUMENT);
+ memset(&buffer_[addr], 0xFF, GetSectorSizeBytes() * num_sectors);
+ return Status::OK;
+ }
+
+ // Reads bytes from flash into buffer. Blocking call.
+ // Returns: OK, on success.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ Status Read(uint8_t* dest_ram_addr,
+ Address source_flash_addr,
+ uint32_t len) override {
+ RETURN_STATUS_IF(
+ (source_flash_addr + len) >= GetSectorCount() * GetSizeBytes(),
+ Status::INVALID_ARGUMENT);
+ memcpy(dest_ram_addr, &buffer_[source_flash_addr], len);
+ return Status::OK;
+ }
+
+ // Writes bytes to flash. Blocking call.
+ // Returns: OK, on success.
+ // INVALID_ARGUMENT, if address or length is invalid.
+ // UNKNOWN, on HAL error
+ Status Write(Address dest_flash_addr,
+ const uint8_t* source_ram_addr,
+ uint32_t len) override {
+ RETURN_STATUS_IF(
+ (dest_flash_addr + len) >= GetSectorCount() * GetSizeBytes(),
+ Status::INVALID_ARGUMENT);
+ RETURN_STATUS_IF(dest_flash_addr % GetAlignmentBytes() != 0,
+ Status::INVALID_ARGUMENT);
+ RETURN_STATUS_IF(len % GetAlignmentBytes() != 0, Status::INVALID_ARGUMENT);
+ // Check in erased state
+ for (unsigned i = 0; i < len; i++) {
+ RETURN_STATUS_IF(buffer_[dest_flash_addr + i] != 0xFF, Status::UNKNOWN);
+ }
+ memcpy(&buffer_[dest_flash_addr], source_ram_addr, len);
+ return Status::OK;
+ }
+
+ private:
+ std::array<uint8_t, kSectorCount * kSectorSize> buffer_;
+};
+
+} // namespace pw
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
new file mode 100644
index 0000000..dca6507
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -0,0 +1,366 @@
+// 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 <algorithm>
+#include <type_traits>
+
+#include "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/logging.h"
+#include "pw_kvs/os/mutex.h"
+#include "pw_kvs/status.h"
+
+namespace pw {
+
+// This object is very large and should not be placed on the stack.
+class KeyValueStore {
+ public:
+ KeyValueStore(FlashPartition* partition) : partition_(*partition) {}
+
+ // Enable the KVS, scans the sectors of the partition for any current KVS
+ // data. Erases and initializes any sectors which are not initialized.
+ // Checks the CRC of all data in the KVS; on failure the corrupted data is
+ // lost and Enable will return Status::DATA_LOSS, but the KVS will still load
+ // other data and will be enabled.
+ Status Enable();
+ bool IsEnabled() const { return enabled_; }
+ void Disable() {
+ if (enabled_ == false) {
+ return;
+ }
+ os::MutexLock lock(&lock_);
+ enabled_ = false;
+ }
+
+ // Erase a key value element.
+ // key is a null terminated c string.
+ // Returns OK if erased
+ // NOT_FOUND if key was not found.
+ Status Erase(const char* key);
+
+ // Copy the first size bytes of key's value into value buffer.
+ // key is a null terminated c string. Size is the amount of bytes to read,
+ // Optional offset argument supports reading size bytes starting at the
+ // specified offset.
+ // Returns OK if successful
+ // NOT_FOUND if key was not found
+ // DATA_LOSS if the value failed crc check
+ Status Get(const char* key, void* value, uint16_t size, uint16_t offset = 0);
+
+ // Interpret the key's value as the given type and return it.
+ // Returns OK if successful
+ // NOT_FOUND if key was not found
+ // DATA_LOSS if the value failed crc check
+ // INVALID_ARGUMENT if size of value != sizeof(T)
+ template <typename T>
+ Status Get(const char* 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");
+ uint16_t value_size = 0;
+ RETURN_IF_ERROR(GetValueSize(key, &value_size));
+ RETURN_STATUS_IF(value_size != sizeof(T), Status::INVALID_ARGUMENT);
+ return Get(key, value, sizeof(T));
+ }
+
+ // Writes the key value store to the partition. If the key already exists it
+ // will be deleted before writing the new value.
+ // key is a null terminated c string.
+ // Returns OK if successful
+ // RESOURCE_EXHAUSTED if there is not enough available space
+ Status Put(const char* key, const void* value, uint16_t size);
+
+ // Writes the value to the partition. If the key already exists it will be
+ // deleted before writing the new value.
+ // key is a null terminated c string.
+ // Returns OK if successful
+ // RESOURCE_EXHAUSTED if there is not enough available space
+ template <typename T>
+ Status Put(const char* key, const T& value) {
+ static_assert(std::is_trivially_copyable<T>(), "KVS values must copyable");
+ static_assert(!std::is_pointer<T>(), "KVS values cannot be pointers");
+ return Put(key, &value, sizeof(T));
+ }
+
+ // Gets the size of the value stored for provided key.
+ // Returns OK if successful
+ // INVALID_ARGUMENT if args are invalid.
+ // FAILED_PRECONDITION if KVS is not enabled.
+ // NOT_FOUND if key was not found.
+ Status GetValueSize(const char* key, uint16_t* value_size);
+
+ // Tests if the proposed key value entry can be stored in the KVS.
+ bool CanFitEntry(uint16_t key_len, uint16_t value_len) {
+ return kSectorInvalid != FindSpace(ChunkSize(key_len, value_len));
+ }
+
+ // CleanAll cleans each sector which is currently marked for cleaning.
+ // Note: if any data is invalid/corrupt it could be lost.
+ Status CleanAll() {
+ os::MutexLock lock(&lock_);
+ return CleanAllInternal();
+ }
+ size_t PendingCleanCount() {
+ os::MutexLock lock(&lock_);
+ size_t ret = 0;
+ for (size_t i = 0; i < SectorCount(); i++) {
+ ret += sector_space_remaining_[i] == 0 ? 1 : 0;
+ }
+ return ret;
+ }
+
+ // Clean a single sector and return, if all sectors are clean it will set
+ // all_sectors_have_been_cleaned to true and return.
+ Status CleanOneSector(bool* all_sectors_have_been_cleaned);
+
+ // For debugging, logging, and testing. (Don't use in regular code)
+ // Note: a key_index is not valid after an element is erased or updated.
+ uint8_t KeyCount() const;
+ const char* GetKey(uint8_t idx) const;
+ uint16_t GetValueSize(uint8_t idx) const;
+ size_t GetMaxKeys() const { return kListCapacityMax; }
+ bool HasEmptySector() const { return HaveEmptySectorImpl(); }
+
+ static constexpr size_t kHeaderSize = 8; // Sector and KVS Header size
+ static constexpr uint16_t MaxValueLength() { return kChunkValueLengthMax; }
+ KeyValueStore(const KeyValueStore&) = delete;
+ KeyValueStore& operator=(const KeyValueStore&) = delete;
+
+ private:
+ using KeyIndex = uint8_t;
+ using SectorIndex = uint32_t;
+
+ static constexpr uint16_t kVersion = 4;
+ static constexpr KeyIndex kListCapacityMax = cfg::kKvsMaxKeyCount;
+ static constexpr SectorIndex kSectorCountMax = cfg::kKvsMaxSectorCount;
+
+ // Number of bits for fields in KVSHeader:
+ static constexpr int kChunkHeaderKeyFieldNumBits = 4;
+ static constexpr int kChunkHeaderChunkFieldNumBits = 12;
+
+ static constexpr uint16_t kSectorReadyValue = 0xABCD;
+ static constexpr uint16_t kChunkSyncValue = 0x55AA;
+
+ static constexpr uint16_t kChunkLengthMax =
+ ((1 << kChunkHeaderChunkFieldNumBits) - 1);
+ static constexpr uint16_t kChunkKeyLengthMax =
+ ((1 << kChunkHeaderKeyFieldNumBits) - 1);
+ static constexpr uint16_t kChunkValueLengthMax =
+ (kChunkLengthMax - kChunkKeyLengthMax);
+
+ static constexpr SectorIndex kSectorInvalid = 0xFFFFFFFFul;
+ static constexpr FlashPartition::Address kAddressInvalid = 0xFFFFFFFFul;
+ static constexpr uint64_t kSectorCleanNotPending = 0xFFFFFFFFFFFFFFFFull;
+
+ // TODO: Use BitPacker if/when have more flags.
+ static constexpr uint16_t kFlagsIsErasedMask = 0x0001;
+ static constexpr uint16_t kMaxAlignmentBytes = 128;
+
+ // This packs into 16 bytes.
+ struct KvsSectorHeaderMeta {
+ uint16_t synchronize_token;
+ uint16_t version;
+ uint16_t alignment_bytes; // alignment used for each chunk in this sector.
+ uint16_t padding; // padding to support uint64_t alignment.
+ } __attribute__((__packed__));
+ static_assert(sizeof(KvsSectorHeaderMeta) == kHeaderSize,
+ "Invalid KvsSectorHeaderMeta size");
+
+ // sector_clean_pending is broken off from KvsSectorHeaderMeta to support
+ // larger than sizeof(KvsSectorHeaderMeta) flash write alignments.
+ struct KvsSectorHeaderCleaning {
+ // When this sector is not marked for cleaning this will be in the erased
+ // state. When marked for clean this value indicates the order the sectors
+ // were marked for cleaning, and therfore which data is the newest.
+ // To remain backwards compatible with v2 and v3 KVS this is 8 bytes, if the
+ // alignment is greater than 8 we will check the entire alignment is in the
+ // default erased state.
+ uint64_t sector_clean_order;
+ };
+ static_assert(sizeof(KvsSectorHeaderCleaning) == kHeaderSize,
+ "Invalid KvsSectorHeaderCleaning size");
+
+ // This packs into 8 bytes, to support uint64_t alignment.
+ struct KvsHeader {
+ uint16_t synchronize_token;
+ uint16_t crc; // Crc of the key + data (Ignoring any padding bytes)
+ // flags is a Bitmask: bits 15-1 reserved = 0,
+ // bit 0: is_erased [0 when not erased, 1 when erased]
+ uint16_t flags;
+ // On little endian the length fields map to memory as follows:
+ // byte array: [ 0x(c0to3 k0to3) 0x(c8to11 c4to7) ]
+ // Key length does not include trailing zero. That is not stored.
+ uint16_t key_len : kChunkHeaderKeyFieldNumBits;
+ // Chunk length is the total length of the chunk before alignment.
+ // That way we can work out the length of the value as:
+ // (chunk length - key length - size of chunk header).
+ uint16_t chunk_len : kChunkHeaderChunkFieldNumBits;
+ } __attribute__((__packed__));
+ static_assert(sizeof(KvsHeader) == kHeaderSize, "Invalid KvsHeader size");
+
+ struct KeyMap {
+ char key[kChunkKeyLengthMax + 1]; // + 1 for null terminator
+ FlashPartition::Address address;
+ uint16_t chunk_len;
+ bool is_erased;
+ };
+
+ // NOTE: All public APIs handle the locking, the internal methods assume the
+ // lock has already been acquired.
+
+ SectorIndex AddressToSectorIndex(FlashPartition::Address address) const {
+ return address / partition_.GetSectorSizeBytes();
+ }
+
+ FlashPartition::Address SectorIndexToAddress(SectorIndex index) const {
+ return index * partition_.GetSectorSizeBytes();
+ }
+
+ // Returns kAddressInvalid if no space is found, otherwise the address.
+ FlashPartition::Address FindSpace(uint16_t requested_size) const;
+
+ // Attempts to rewrite a key's value by appending the new value to the same
+ // sector. If the sector is full the value is written to another sector, and
+ // the sector is marked for cleaning.
+ // Returns RESOURCE_EXHAUSTED if no space is available, OK otherwise.
+ Status RewriteValue(KeyIndex key_index,
+ const uint8_t* value,
+ uint16_t size,
+ bool is_erased = false);
+
+ bool ValueMatches(KeyIndex key_index,
+ const uint8_t* value,
+ uint16_t size,
+ bool is_erased);
+
+ // ResetSector erases the sector and writes the sector header.
+ Status ResetSector(SectorIndex sector_index);
+ Status WriteKeyValue(FlashPartition::Address address,
+ const char* key,
+ const uint8_t* value,
+ uint16_t size,
+ bool is_erased = false);
+ uint32_t SectorSpaceRemaining(SectorIndex sector_index) const;
+
+ // Returns idx if key is found, otherwise kListCapacityMax.
+ KeyIndex FindKeyInMap(const char* key) const;
+ bool IsKeyInMap(const char* key) const {
+ return FindKeyInMap(key) != kListCapacityMax;
+ }
+
+ void RemoveFromMap(KeyIndex key_index);
+ Status AppendToMap(const char* key,
+ FlashPartition::Address address,
+ uint16_t chunk_len,
+ bool is_erased = false);
+ void UpdateMap(KeyIndex key_index,
+ FlashPartition::Address address,
+ uint16_t chunk_len,
+ bool is_erased = false);
+ uint16_t CalculateCrc(const char* key,
+ uint16_t key_size,
+ const uint8_t* value,
+ uint16_t value_size) const;
+
+ // Calculates the CRC by reading the value from flash in chunks.
+ Status CalculateCrcFromValueAddress(const char* key,
+ uint16_t key_size,
+ FlashPartition::Address value_address,
+ uint16_t value_size,
+ uint16_t* crc_ret);
+
+ uint16_t RoundUpForAlignment(uint16_t size) const {
+ if (size % alignment_bytes_ != 0) {
+ return size + alignment_bytes_ - size % alignment_bytes_;
+ }
+ return size;
+ }
+
+ // The buffer is chosen to be no larger then the config value, and
+ // be a multiple of the flash alignment.
+ size_t TempBufferAlignedSize() const {
+ CHECK_GE(sizeof(temp_buffer_), partition_.GetAlignmentBytes());
+ return sizeof(temp_buffer_) -
+ (sizeof(temp_buffer_) % partition_.GetAlignmentBytes());
+ }
+
+ // Moves a key/value chunk from one address to another, all fields expected to
+ // be aligned.
+ Status MoveChunk(FlashPartition::Address dest_address,
+ FlashPartition::Address src_address,
+ uint16_t size);
+
+ // Size of a chunk including header, key, value, and alignment padding.
+ uint16_t ChunkSize(uint16_t key_len, uint16_t chunk_len) const {
+ return RoundUpForAlignment(sizeof(KvsHeader)) +
+ RoundUpForAlignment(key_len) + RoundUpForAlignment(chunk_len);
+ }
+
+ // Sectors should be cleaned when full, every valid (Most recent, not erased)
+ // chunk of data is moved to another sector and the sector is erased.
+ // TODO: Clean sectors with lots of invalid data, without a rewrite
+ // or erase triggering it.
+ Status MarkSectorForClean(SectorIndex sector);
+ Status CleanSector(SectorIndex sector);
+ Status CleanAllInternal();
+ Status GarbageCollectImpl(bool clean_pending_sectors,
+ bool exit_when_have_free_sector);
+ Status FullGarbageCollect();
+ Status EnforceFreeSector();
+
+ SectorIndex SectorCount() const {
+ return std::min(partition_.GetSectorCount(), kSectorCountMax);
+ }
+
+ size_t SectorSpaceAvailableWhenEmpty() const {
+ return partition_.GetSectorSizeBytes() -
+ RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)) -
+ RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning));
+ }
+
+ bool HaveEmptySectorImpl(SectorIndex skip_sector = kSectorInvalid) const {
+ for (SectorIndex i = 0; i < SectorCount(); i++) {
+ if (i != skip_sector &&
+ sector_space_remaining_[i] == SectorSpaceAvailableWhenEmpty()) {
+ return true;
+ }
+ }
+ return false;
+ }
+
+ bool IsInLastFreeSector(FlashPartition::Address address) {
+ return sector_space_remaining_[AddressToSectorIndex(address)] ==
+ SectorSpaceAvailableWhenEmpty() &&
+ !HaveEmptySectorImpl(AddressToSectorIndex(address));
+ }
+
+ FlashPartition& partition_;
+ os::Mutex lock_;
+ bool enabled_ = false;
+ uint8_t alignment_bytes_ = 0;
+ uint64_t next_sector_clean_order_ = 0;
+
+ // Free space available in each sector, set to 0 when clean is pending/active
+ uint32_t sector_space_remaining_[kSectorCountMax] = {0};
+ uint64_t sector_clean_order_[kSectorCountMax] = {kSectorCleanNotPending};
+ KeyMap key_map_[kListCapacityMax] = {{{0}}};
+ KeyIndex map_size_ = 0;
+
+ // +1 for nul-terminator since keys are stored as Length + Value and no nul
+ // termination but we are using them as nul-terminated strings through
+ // loading-up and comparing the keys.
+ char temp_key_buffer_[kChunkKeyLengthMax + 1u] = {0};
+ uint8_t temp_buffer_[cfg::kKvsBufferSize] = {0};
+};
+
+} // namespace pw
diff --git a/pw_kvs/public/pw_kvs/partition_table_entry.h b/pw_kvs/public/pw_kvs/partition_table_entry.h
new file mode 100644
index 0000000..9aa111d
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/partition_table_entry.h
@@ -0,0 +1,51 @@
+// 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 <cstdint>
+
+namespace pw {
+
+namespace partition_table {
+
+enum DataType { kRawData, kKvs };
+
+} // namespace partition_table
+
+enum class PartitionPermission : bool {
+ kReadOnly = true,
+ kReadAndWrite = false,
+};
+
+struct PartitionTableEntry {
+ constexpr PartitionTableEntry(
+ const uint32_t start_sector_index,
+ const uint32_t end_sector_index,
+ const uint8_t partition_identifier,
+ partition_table::DataType datatype,
+ PartitionPermission permission = PartitionPermission::kReadAndWrite)
+ : partition_start_sector_index(start_sector_index),
+ partition_end_sector_index(end_sector_index),
+ partition_id(partition_identifier),
+ data_type(datatype),
+ partition_permission(permission) {}
+
+ const uint32_t partition_start_sector_index;
+ const uint32_t partition_end_sector_index;
+ const uint8_t partition_id;
+ const partition_table::DataType data_type;
+ const PartitionPermission partition_permission;
+};
+
+} // namespace pw
