pw_kvs: Move reading and writing to Entry class
- Add the FlashPartition and address to the Entry class.
- Move functions for reading or writing the entry header, key, and value
to the Entry class.
Change-Id: I0af3c140a519c8b050fcef81eca4f3b45560f75c
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index bb38bcb..052216e 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -100,6 +100,7 @@
"entry_test.cc",
],
deps = [
+ ":in_memory_fake_flash",
":pw_kvs",
],
)
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index 33c5ad8..1edd0d2 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -119,6 +119,7 @@
pw_test("entry_test") {
deps = [
+ ":in_memory_fake_flash",
":pw_kvs",
]
sources = [
diff --git a/pw_kvs/entry.cc b/pw_kvs/entry.cc
index 41cdaf4..c0cc9e6 100644
--- a/pw_kvs/entry.cc
+++ b/pw_kvs/entry.cc
@@ -15,6 +15,7 @@
#include "pw_kvs_private/entry.h"
#include <cinttypes>
+#include <cstring>
#include "pw_kvs_private/macros.h"
#include "pw_log/log.h"
@@ -24,19 +25,45 @@
using std::byte;
using std::string_view;
-Entry::Entry(uint32_t magic,
+Status Entry::Read(FlashPartition& partition, Address address, Entry* entry) {
+ EntryHeader header;
+ TRY(partition.Read(address, sizeof(header), &header));
+ *entry = Entry(&partition, address, header);
+
+ if (partition.AppearsErased(as_bytes(span(&header.magic, 1)))) {
+ return Status::NOT_FOUND;
+ }
+ return Status::OK;
+}
+
+StatusWithSize Entry::ReadKey(FlashPartition& partition,
+ Address address,
+ size_t key_length,
+ KeyBuffer& key) {
+ if (key_length == 0u || key_length > kMaxKeyLength) {
+ return StatusWithSize(Status::DATA_LOSS);
+ }
+
+ return partition.Read(address + sizeof(EntryHeader), key_length, key.data());
+}
+
+Entry::Entry(FlashPartition& partition,
+ Address address,
+ uint32_t magic,
ChecksumAlgorithm* algorithm,
string_view key,
span<const byte> value,
- uint16_t value_length_bytes,
+ uint16_t value_size_bytes,
size_t alignment_bytes,
uint32_t key_version)
- : header_{.magic = magic,
- .checksum = 0,
- .alignment_units = alignment_bytes_to_units(alignment_bytes),
- .key_length_bytes = static_cast<uint8_t>(key.size()),
- .value_length_bytes = value_length_bytes,
- .key_version = key_version} {
+ : Entry(&partition,
+ address,
+ {.magic = magic,
+ .checksum = 0,
+ .alignment_units = alignment_bytes_to_units(alignment_bytes),
+ .key_length_bytes = static_cast<uint8_t>(key.size()),
+ .value_size_bytes = value_size_bytes,
+ .key_version = key_version}) {
if (algorithm != nullptr) {
span<const byte> checksum = CalculateChecksum(algorithm, key, value);
std::memcpy(&header_.checksum,
@@ -48,6 +75,28 @@
// DCHECK_NE(alignment_bytes, 0);
}
+StatusWithSize Entry::Write(const string_view key,
+ span<const byte> value) const {
+ FlashPartition::Output flash(partition(), address_);
+ return AlignedWrite<64>(
+ flash,
+ alignment_bytes(),
+ {as_bytes(span(&header_, 1)), as_bytes(span(key)), value});
+}
+
+StatusWithSize Entry::ReadValue(span<byte> value) const {
+ const size_t read_size = std::min(value_size(), value.size());
+ StatusWithSize result =
+ partition().Read(address_ + sizeof(EntryHeader) + key_length(),
+ value.subspan(0, read_size));
+ TRY_WITH_SIZE(result);
+
+ if (read_size != value_size()) {
+ return StatusWithSize(Status::RESOURCE_EXHAUSTED, read_size);
+ }
+ return StatusWithSize(read_size);
+}
+
Status Entry::VerifyChecksum(ChecksumAlgorithm* algorithm,
string_view key,
span<const byte> value) const {
@@ -58,9 +107,7 @@
return algorithm->Verify(checksum_bytes());
}
-Status Entry::VerifyChecksumInFlash(FlashPartition* partition,
- FlashPartition::Address address,
- ChecksumAlgorithm* algorithm) const {
+Status Entry::VerifyChecksumInFlash(ChecksumAlgorithm* algorithm) const {
// Read the entire entry piece-by-piece into a small buffer. If the entry is
// 32 B or less, only one read is required.
union {
@@ -71,8 +118,10 @@
size_t bytes_to_read = size();
size_t read_size = std::min(sizeof(buffer), bytes_to_read);
+ Address read_address = address_;
+
// Read the first chunk, which includes the header, and compare the checksum.
- TRY(partition->Read(address, read_size, buffer));
+ TRY(partition().Read(read_address, read_size, buffer));
if (header_to_verify.checksum != checksum()) {
PW_LOG_ERROR("Expected checksum %08" PRIx32 ", found %08" PRIx32,
@@ -100,15 +149,26 @@
}
// Read the next chunk into the buffer.
- address += read_size;
+ read_address += read_size;
read_size = std::min(sizeof(buffer), bytes_to_read);
- TRY(partition->Read(address, read_size, buffer));
+ TRY(partition().Read(read_address, read_size, buffer));
}
algorithm->Finish();
return algorithm->Verify(checksum_bytes());
}
+void Entry::DebugLog() {
+ PW_LOG_DEBUG("Header: ");
+ PW_LOG_DEBUG(" Address = 0x%zx", size_t(address_));
+ PW_LOG_DEBUG(" Magic = 0x%zx", size_t(magic()));
+ PW_LOG_DEBUG(" Checksum = 0x%zx", size_t(checksum()));
+ PW_LOG_DEBUG(" Key length = 0x%zx", size_t(key_length()));
+ PW_LOG_DEBUG(" Value length = 0x%zx", size_t(value_size()));
+ PW_LOG_DEBUG(" Entry size = 0x%zx", size_t(size()));
+ PW_LOG_DEBUG(" Alignment = 0x%zx", size_t(alignment_bytes()));
+}
+
span<const byte> Entry::CalculateChecksum(ChecksumAlgorithm* algorithm,
const string_view key,
span<const byte> value) const {
diff --git a/pw_kvs/entry_test.cc b/pw_kvs/entry_test.cc
index 194978e..d181926 100644
--- a/pw_kvs/entry_test.cc
+++ b/pw_kvs/entry_test.cc
@@ -15,43 +15,57 @@
#include "pw_kvs_private/entry.h"
#include "gtest/gtest.h"
+#include "pw_kvs/alignment.h"
#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/in_memory_fake_flash.h"
namespace pw::kvs {
namespace {
-TEST(Entry, Alignment) {
+// TODO(hepler): expand these tests
+
+InMemoryFakeFlash<128, 4> test_flash(16);
+FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
+
+TEST(Entry, Size_RoundsUpToAlignment) {
for (size_t alignment_bytes = 1; alignment_bytes <= 4096; ++alignment_bytes) {
- ASSERT_EQ(AlignUp(alignment_bytes, Entry::kMinAlignmentBytes),
- Entry::Valid(9, nullptr, "k", {}, alignment_bytes, 0)
- .alignment_bytes());
- ASSERT_EQ(AlignUp(alignment_bytes, Entry::kMinAlignmentBytes),
- Entry::Tombstone(9, nullptr, "k", alignment_bytes, 0)
- .alignment_bytes());
+ const size_t align = AlignUp(alignment_bytes, Entry::kMinAlignmentBytes);
+
+ for (size_t value : {size_t(0), align - 1, align, align + 1, 2 * align}) {
+ Entry entry = Entry::Valid(test_partition,
+ 0,
+ 9,
+ nullptr,
+ "k",
+ {nullptr, value},
+ alignment_bytes,
+ 0);
+ ASSERT_EQ(AlignUp(sizeof(EntryHeader) + 1 /* key */ + value, align),
+ entry.size());
+ }
+
+ Entry entry = Entry::Tombstone(
+ test_partition, 0, 9, nullptr, "k", alignment_bytes, 0);
+ ASSERT_EQ(AlignUp(sizeof(EntryHeader) + 1 /* key */, align), entry.size());
}
}
-TEST(Entry, ValidEntry) {
- Entry entry = Entry::Valid(9, nullptr, "k", as_bytes(span("123")), 1, 9876);
+TEST(Entry, Construct_ValidEntry) {
+ auto entry = Entry::Valid(
+ test_partition, 1, 9, nullptr, "k", as_bytes(span("123")), 1, 9876);
EXPECT_FALSE(entry.deleted());
EXPECT_EQ(entry.magic(), 9u);
- EXPECT_EQ(entry.checksum(), 0u); // kNoChecksum
- EXPECT_EQ(entry.key_length(), 1u);
- EXPECT_EQ(entry.value_length(), sizeof("123"));
- EXPECT_EQ(entry.alignment_bytes(), 16u);
+ EXPECT_EQ(entry.value_size(), sizeof("123"));
EXPECT_EQ(entry.key_version(), 9876u);
}
-TEST(Entry, Tombstone) {
- Entry entry = Entry::Tombstone(99, nullptr, "key", 1, 123);
+TEST(Entry, Construct_Tombstone) {
+ auto entry = Entry::Tombstone(test_partition, 1, 99, nullptr, "key", 1, 123);
EXPECT_TRUE(entry.deleted());
EXPECT_EQ(entry.magic(), 99u);
- EXPECT_EQ(entry.checksum(), 0u); // kNoChecksum
- EXPECT_EQ(entry.key_length(), 3u);
- EXPECT_EQ(entry.value_length(), 0u);
- EXPECT_EQ(entry.alignment_bytes(), 16u);
+ EXPECT_EQ(entry.value_size(), 0u);
EXPECT_EQ(entry.key_version(), 123u);
}
diff --git a/pw_kvs/flash_memory.cc b/pw_kvs/flash_memory.cc
index cd951f2..f3d8dfb 100644
--- a/pw_kvs/flash_memory.cc
+++ b/pw_kvs/flash_memory.cc
@@ -94,6 +94,15 @@
return Status::OK;
}
+bool FlashPartition::AppearsErased(span<const byte> data) const {
+ for (byte b : data) {
+ if (b != flash_.erased_memory_content()) {
+ return false;
+ }
+ }
+ return true;
+}
+
Status FlashPartition::CheckBounds(Address address, size_t length) const {
if (address + length > size_bytes()) {
PW_LOG_ERROR("Attempted out-of-bound flash memory access (address: %" PRIu32
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 85565b9..29fa778 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -61,8 +61,7 @@
const size_t sector_size_bytes = partition_.sector_size_bytes();
if (working_buffer_.size() < sector_size_bytes) {
- CRT("ERROR: working_buffer_ (%zu bytes) is smaller than sector "
- "size (%zu bytes)",
+ CRT("working_buffer_ (%zu bytes) is smaller than sector size (%zu bytes)",
working_buffer_.size(),
sector_size_bytes);
return Status::INVALID_ARGUMENT;
@@ -125,9 +124,9 @@
// For every valid key, increment the valid bytes for that sector.
for (KeyDescriptor& key_descriptor : key_descriptors_) {
uint32_t sector_id = key_descriptor.address / sector_size_bytes;
- Entry header;
- TRY(ReadEntryHeader(key_descriptor.address, &header));
- sectors_[sector_id].valid_bytes += header.size();
+ Entry entry;
+ TRY(Entry::Read(partition_, key_descriptor.address, &entry));
+ sectors_[sector_id].valid_bytes += entry.size();
}
initialized_ = true;
return Status::OK;
@@ -135,27 +134,14 @@
Status KeyValueStore::LoadEntry(Address entry_address,
Address* next_entry_address) {
- Entry header;
- TRY(ReadEntryHeader(entry_address, &header));
- // TODO: Should likely add a "LogHeader" method or similar.
- DBG("Header: ");
- DBG(" Address = 0x%zx", size_t(entry_address));
- DBG(" Magic = 0x%zx", size_t(header.magic()));
- DBG(" Checksum = 0x%zx", size_t(header.checksum()));
- DBG(" Key length = 0x%zx", size_t(header.key_length()));
- DBG(" Value length = 0x%zx", size_t(header.value_length()));
- DBG(" Entry size = 0x%zx", size_t(header.size()));
- DBG(" Alignment = 0x%zx", size_t(header.alignment_bytes()));
-
- if (HeaderLooksLikeUnwrittenData(header)) {
- return Status::NOT_FOUND;
- }
+ Entry entry;
+ TRY(Entry::Read(partition_, entry_address, &entry));
// TODO: Handle multiple magics for formats that have changed.
- if (header.magic() != entry_header_format_.magic) {
+ if (entry.magic() != entry_header_format_.magic) {
// TODO: It may be cleaner to have some logging helpers for these cases.
- CRT("Found corrupt magic: %zx; expecting %zx; at address %zx",
- size_t(header.magic()),
+ ERR("Found corrupt magic: %zx; expecting %zx; at address %zx",
+ size_t(entry.magic()),
size_t(entry_header_format_.magic),
size_t(entry_address));
return Status::DATA_LOSS;
@@ -163,17 +149,16 @@
// Read the key from flash & validate the entry (which reads the value).
KeyBuffer key_buffer;
- TRY(ReadEntryKey(entry_address, header.key_length(), key_buffer.data()));
- const string_view key(key_buffer.data(), header.key_length());
+ TRY_ASSIGN(size_t key_length, entry.ReadKey(key_buffer));
+ const string_view key(key_buffer.data(), key_length);
- TRY(header.VerifyChecksumInFlash(
- &partition_, entry_address, entry_header_format_.checksum));
+ TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
KeyDescriptor key_descriptor(
key,
- header.key_version(),
+ entry.key_version(),
entry_address,
- header.deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
+ entry.deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
DBG("Key hash: %zx (%zu)",
size_t(key_descriptor.key_hash),
@@ -181,9 +166,7 @@
TRY(AppendNewOrOverwriteStaleExistingDescriptor(key_descriptor));
- // TODO: Extract this to something like "NextValidEntryAddress".
- *next_entry_address = key_descriptor.address + header.size();
-
+ *next_entry_address = entry.next_address();
return Status::OK;
}
@@ -222,7 +205,6 @@
// TODO: Need a better name.
Status KeyValueStore::AppendEmptyDescriptor(KeyDescriptor** new_descriptor) {
if (key_descriptors_.full()) {
- // TODO: Is this the right return code?
return Status::RESOURCE_EXHAUSTED;
}
key_descriptors_.emplace_back();
@@ -230,12 +212,6 @@
return Status::OK;
}
-// TODO: Finish.
-bool KeyValueStore::HeaderLooksLikeUnwrittenData(const Entry& header) const {
- // TODO: This is not correct; it should call through to flash memory.
- return header.magic() == 0xffffffff;
-}
-
KeyValueStore::KeyDescriptor* KeyValueStore::FindDescriptor(uint32_t hash) {
for (KeyDescriptor& key_descriptor : key_descriptors_) {
if (key_descriptor.key_hash == hash) {
@@ -252,15 +228,15 @@
const KeyDescriptor* key_descriptor;
TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
- Entry header;
- TRY_WITH_SIZE(ReadEntryHeader(key_descriptor->address, &header));
+ Entry entry;
+ TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address, &entry));
- StatusWithSize result = ReadEntryValue(*key_descriptor, header, value_buffer);
+ StatusWithSize result = entry.ReadValue(value_buffer);
if (result.ok() && options_.verify_on_read) {
Status verify_result =
- header.VerifyChecksum(entry_header_format_.checksum,
- key,
- value_buffer.subspan(0, result.size()));
+ entry.VerifyChecksum(entry_header_format_.checksum,
+ key,
+ value_buffer.subspan(0, result.size()));
if (!verify_result.ok()) {
std::memset(
value_buffer.subspan(0, result.size()).data(), 0, result.size());
@@ -325,10 +301,9 @@
const KeyValueStore::Item& KeyValueStore::iterator::operator*() {
std::memset(item_.key_buffer_.data(), 0, item_.key_buffer_.size());
- Entry header;
- if (item_.kvs_.ReadEntryHeader(descriptor().address, &header).ok()) {
- item_.kvs_.ReadEntryKey(
- descriptor().address, header.key_length(), item_.key_buffer_.data());
+ Entry entry;
+ if (Entry::Read(item_.kvs_.partition_, descriptor().address, &entry).ok()) {
+ entry.ReadKey(item_.key_buffer_);
}
return item_;
@@ -363,10 +338,10 @@
const KeyDescriptor* key_descriptor;
TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
- Entry header;
- TRY_WITH_SIZE(ReadEntryHeader(key_descriptor->address, &header));
+ Entry entry;
+ TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address, &entry));
- return StatusWithSize(header.value_length());
+ return StatusWithSize(entry.value_size());
}
uint32_t KeyValueStore::HashKey(string_view string) {
@@ -418,14 +393,15 @@
//
Status KeyValueStore::FindKeyDescriptor(string_view key,
const KeyDescriptor** result) const {
- char key_buffer[kMaxKeyLength];
+ Entry::KeyBuffer key_buffer;
const uint32_t hash = HashKey(key);
for (auto& descriptor : key_descriptors_) {
if (descriptor.key_hash == hash) {
- TRY(ReadEntryKey(descriptor.address, key.size(), key_buffer));
+ TRY(Entry::ReadKey(
+ partition_, descriptor.address, key.size(), key_buffer));
- if (key == string_view(key_buffer, key.size())) {
+ if (key == string_view(key_buffer.data(), key.size())) {
DBG("Found match for key hash 0x%08" PRIx32, hash);
*result = &descriptor;
return Status::OK;
@@ -457,49 +433,13 @@
return status;
}
-Status KeyValueStore::ReadEntryHeader(Address address, Entry* header) const {
- return partition_.Read(address, sizeof(*header), header).status();
-}
-
-Status KeyValueStore::ReadEntryKey(Address address,
- size_t key_length,
- char* key) const {
- // TODO: This check probably shouldn't be here; this is like
- // checking that the Cortex M's RAM isn't corrupt. This should be
- // done at boot time.
- // ^^ This argument sometimes comes from Entry::key_value_len,
- // which is read directly from flash. If it's corrupted, we shouldn't try
- // to read a bunch of extra data.
- if (key_length == 0u || key_length > kMaxKeyLength) {
- return Status::DATA_LOSS;
- }
- // The key is immediately after the entry header.
- return partition_.Read(address + sizeof(EntryHeader), key_length, key)
- .status();
-}
-
-StatusWithSize KeyValueStore::ReadEntryValue(
- const KeyDescriptor& key_descriptor,
- const Entry& header,
- span<byte> value) const {
- const size_t read_size = std::min(header.value_length(), value.size());
- StatusWithSize result = partition_.Read(
- key_descriptor.address + sizeof(header) + header.key_length(),
- value.subspan(0, read_size));
- TRY_WITH_SIZE(result);
- if (read_size != header.value_length()) {
- return StatusWithSize(Status::RESOURCE_EXHAUSTED, read_size);
- }
- return StatusWithSize(read_size);
-}
-
Status KeyValueStore::WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
KeyDescriptor::State new_state,
string_view key,
span<const byte> value) {
// Find the original entry and sector to update the sector's valid_bytes.
Entry original_entry;
- TRY(ReadEntryHeader(key_descriptor->address, &original_entry));
+ TRY(Entry::Read(partition_, key_descriptor->address, &original_entry));
SectorDescriptor* old_sector = SectorFromAddress(key_descriptor->address);
SectorDescriptor* sector;
@@ -547,43 +487,40 @@
Status KeyValueStore::RelocateEntry(KeyDescriptor& key_descriptor) {
struct TempEntry {
- std::array<char, kMaxKeyLength + 1> key;
+ Entry::KeyBuffer key;
std::array<char, sizeof(working_buffer_) - sizeof(key)> value;
};
- TempEntry* entry = reinterpret_cast<TempEntry*>(working_buffer_.data());
+ TempEntry* temp_entry = reinterpret_cast<TempEntry*>(working_buffer_.data());
DBG("Relocating entry"); // TODO: add entry info to the log statement.
- // Read the entry to be relocated. Store the header in a local variable and
+ // Read the entry to be relocated. Store the entry in a local variable and
// store the key and value in the TempEntry stored in the static allocated
// working_buffer_.
- Entry header;
- TRY(ReadEntryHeader(key_descriptor.address, &header));
- TRY(ReadEntryKey(
- key_descriptor.address, header.key_length(), entry->key.data()));
- string_view key = string_view(entry->key.data(), header.key_length());
- StatusWithSize result = ReadEntryValue(
- key_descriptor, header, as_writable_bytes(span(entry->value)));
+ Entry entry;
+ TRY(Entry::Read(partition_, key_descriptor.address, &entry));
+ TRY_ASSIGN(size_t key_length, entry.ReadKey(temp_entry->key));
+ string_view key = string_view(temp_entry->key.data(), key_length);
+ auto result = entry.ReadValue(as_writable_bytes(span(temp_entry->value)));
if (!result.status().ok()) {
return Status::INTERNAL;
}
- auto value = span(entry->value.data(), result.size());
-
- TRY(header.VerifyChecksum(
+ auto value = span(temp_entry->value.data(), result.size());
+ TRY(entry.VerifyChecksum(
entry_header_format_.checksum, key, as_bytes(value)));
SectorDescriptor* old_sector = SectorFromAddress(key_descriptor.address);
// Find a new sector for the entry and write it to the new location.
SectorDescriptor* new_sector;
- TRY(FindSectorWithSpace(&new_sector, header.size(), old_sector, true));
+ TRY(FindSectorWithSpace(&new_sector, entry.size(), old_sector, true));
TRY(AppendEntry(
new_sector, &key_descriptor, key, as_bytes(value), key_descriptor.state));
// Do the valid bytes accounting for the sector the entry was relocated out
// of.
- old_sector->RemoveValidBytes(header.size());
+ old_sector->RemoveValidBytes(entry.size());
return Status::OK;
}
@@ -758,46 +695,42 @@
const string_view key,
span<const byte> value,
KeyDescriptor::State new_state) {
- // write header, key, and value
- Entry header;
+ const Address address = NextWritableAddress(sector);
+ DBG("Appending to address: %#zx", size_t(address));
+
+ Entry entry;
if (new_state == KeyDescriptor::kDeleted) {
- header = Entry::Tombstone(entry_header_format_.magic,
- entry_header_format_.checksum,
- key,
- partition_.alignment_bytes(),
- key_descriptor->key_version + 1);
+ entry = Entry::Tombstone(partition_,
+ address,
+ entry_header_format_.magic,
+ entry_header_format_.checksum,
+ key,
+ partition_.alignment_bytes(),
+ key_descriptor->key_version + 1);
} else {
- header = Entry::Valid(entry_header_format_.magic,
- entry_header_format_.checksum,
- key,
- value,
- partition_.alignment_bytes(),
- key_descriptor->key_version + 1);
+ entry = Entry::Valid(partition_,
+ address,
+ entry_header_format_.magic,
+ entry_header_format_.checksum,
+ key,
+ value,
+ partition_.alignment_bytes(),
+ key_descriptor->key_version + 1);
}
DBG("Appending %zu B entry with key version: %x",
- header.size(),
- unsigned(header.key_version()));
+ entry.size(),
+ unsigned(entry.key_version()));
- Address address = NextWritableAddress(sector);
- DBG("Appending to address: %#zx", size_t(address));
-
- // Write multiple concatenated buffers and pad the results.
- FlashPartition::Output flash(partition_, address);
- TRY_ASSIGN(const size_t written,
- AlignedWrite<32>(
- flash,
- header.alignment_bytes(),
- {as_bytes(span(&header, 1)), as_bytes(span(key)), value}));
+ TRY_ASSIGN(const size_t written, entry.Write(key, value));
if (options_.verify_on_write) {
- TRY(header.VerifyChecksumInFlash(
- &partition_, address, entry_header_format_.checksum));
+ TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
}
key_descriptor->address = address;
- key_descriptor->key_version = header.key_version();
+ key_descriptor->key_version = entry.key_version();
key_descriptor->state = new_state;
sector->valid_bytes += written;
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index c976db2..6643256 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -107,16 +107,17 @@
if (empty() || random_int() % 8 == 0) {
Delete("not_a_key" + std::to_string(random_int()));
} else {
- Delete(RandomKey());
+ Delete(RandomPresentKey());
}
} else {
std::string key;
// Either add a new key or replace an existing one.
if (empty() || random_int() % 2 == 0) {
- key = random_string(random_int() % KeyValueStore::kMaxKeyLength);
+ key =
+ random_string(random_int() % (KeyValueStore::kMaxKeyLength + 1));
} else {
- key = RandomKey();
+ key = RandomPresentKey();
}
Put(key, random_string(random_int() % kMaxValueLength));
@@ -247,7 +248,7 @@
Status result = kvs_.Delete(key);
- if (key.empty() || key.size() >= KeyValueStore::kMaxKeyLength) {
+ if (key.empty() || key.size() > KeyValueStore::kMaxKeyLength) {
EXPECT_EQ(Status::INVALID_ARGUMENT, result);
} else if (map_.count(key) == 0) {
EXPECT_EQ(Status::NOT_FOUND, result);
@@ -285,7 +286,7 @@
bool empty() const { return map_.empty(); }
- std::string RandomKey() const {
+ std::string RandomPresentKey() const {
return map_.empty() ? "" : map_.begin()->second;
}
diff --git a/pw_kvs/public/pw_kvs/checksum.h b/pw_kvs/public/pw_kvs/checksum.h
index 3acb5a4..e9cb85f 100644
--- a/pw_kvs/public/pw_kvs/checksum.h
+++ b/pw_kvs/public/pw_kvs/checksum.h
@@ -88,6 +88,8 @@
~AlignedChecksum() = default;
private:
+ static_assert(kBufferSize >= kAlignmentBytes);
+
void Finalize() final {
writer_.Flush();
FinalizeAligned();
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
index a10af48..5d8f558 100644
--- a/pw_kvs/public/pw_kvs/flash_memory.h
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -150,6 +150,9 @@
: alignment_bytes),
permission_(permission) {}
+ FlashPartition(const FlashPartition&) = delete;
+ FlashPartition& operator=(const FlashPartition&) = delete;
+
virtual ~FlashPartition() = default;
// Performs any required partition or flash-level initialization.
@@ -196,6 +199,11 @@
size_t len,
bool* is_erased);
+ // Checks to see if the data appears to be erased. No reads or writes occur;
+ // the FlashPartition simply compares the data to
+ // flash_.erased_memory_content().
+ bool AppearsErased(span<const std::byte> data) const;
+
// Overridden by derived classes. The reported sector size is space available
// to users of FlashPartition. It accounts for space reserved in the sector
// for FlashPartition to store metadata.
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 2f1c91a..b29058d 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -86,12 +86,13 @@
public:
// TODO: Make these configurable
- static constexpr size_t kMaxKeyLength = 64;
static constexpr size_t kMaxEntries = 256;
static constexpr size_t kMaxUsableSectors = 256;
static constexpr size_t kWorkingBufferSizeBytes = (4 * 1024);
- // +1 for null-terminator.
+ // TODO: Remove the duplicate kMaxKeyLength and KeyBuffer definitions. These
+ // should be provided by the Entry class.
+ static constexpr size_t kMaxKeyLength = 0b111111;
using KeyBuffer = std::array<char, kMaxKeyLength + 1>;
// In the future, will be able to provide additional EntryHeaderFormats for
@@ -301,22 +302,11 @@
key, const_cast<const KeyDescriptor**>(result));
}
- Status ReadEntryHeader(Address address, Entry* header) const;
- Status ReadEntryKey(Address address, size_t key_length, char* key) const;
-
- StatusWithSize ReadEntryValue(const KeyDescriptor& key_descriptor,
- const Entry& header,
- span<std::byte> value) const;
-
Status LoadEntry(Address entry_address, Address* next_entry_address);
Status AppendNewOrOverwriteStaleExistingDescriptor(
const KeyDescriptor& key_descriptor);
Status AppendEmptyDescriptor(KeyDescriptor** new_descriptor);
- Status ValidateEntryChecksumInFlash(const Entry& header,
- std::string_view key,
- const KeyDescriptor& entry) const;
-
Status WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
KeyDescriptor::State new_state,
std::string_view key,
@@ -337,8 +327,6 @@
SectorDescriptor* FindSectorToGarbageCollect();
- bool HeaderLooksLikeUnwrittenData(const Entry& header) const;
-
KeyDescriptor* FindDescriptor(uint32_t hash);
Status AppendEntry(SectorDescriptor* sector,
diff --git a/pw_kvs/pw_kvs_private/entry.h b/pw_kvs/pw_kvs_private/entry.h
index 0685703..c272886 100644
--- a/pw_kvs/pw_kvs_private/entry.h
+++ b/pw_kvs/pw_kvs_private/entry.h
@@ -15,9 +15,9 @@
// This file defines classes for managing the in-flash format for KVS entires.
#pragma once
+#include <array>
#include <cstddef>
#include <cstdint>
-#include <cstring>
#include <string_view>
#include "pw_kvs/alignment.h"
@@ -47,7 +47,7 @@
// Byte length of the value; maximum of 65534. The max uint16_t value (65535
// or 0xFFFF) is reserved to indicate this is a tombstone (deleted) entry.
- uint16_t value_length_bytes;
+ uint16_t value_size_bytes;
// The version of the key. Monotonically increasing.
uint32_t key_version;
@@ -55,21 +55,43 @@
static_assert(sizeof(EntryHeader) == 16, "EntryHeader must not have padding");
-// Entry represents a key-value entry.
+// Entry represents a key-value entry in a flash partition.
class Entry {
public:
static constexpr size_t kMinAlignmentBytes = sizeof(EntryHeader);
+ static constexpr size_t kMaxKeyLength = 0b111111;
+ static constexpr size_t kMaxValueSize = 0xFFFF;
- Entry() = default;
+ using Address = FlashPartition::Address;
+
+ // Buffer capable of holding a null-terminated version of any valid key.
+ using KeyBuffer = std::array<char, kMaxKeyLength + 1>;
+
+ // Returns flash partition Read error codes, or one of the following:
+ //
+ // OK: successfully read the header and initialized the Entry
+ // NOT_FOUND: read the header, but the data appears to be erased
+ //
+ static Status Read(FlashPartition& partition, Address address, Entry* entry);
+
+ static StatusWithSize ReadKey(FlashPartition& partition,
+ Address address,
+ size_t key_length,
+ KeyBuffer& key);
// Creates a new Entry for a valid (non-deleted) entry.
- static Entry Valid(uint32_t magic,
+ static Entry Valid(FlashPartition& partition,
+ Address address,
+ // TODO: Use EntryHeaderFormat here?
+ uint32_t magic,
ChecksumAlgorithm* algorithm,
std::string_view key,
span<const std::byte> value,
size_t alignment_bytes,
uint32_t key_version) {
- return Entry(magic,
+ return Entry(partition,
+ address,
+ magic,
algorithm,
key,
value,
@@ -79,12 +101,16 @@
}
// Creates a new Entry for a tombstone entry, which marks a deleted key.
- static Entry Tombstone(uint32_t magic,
+ static Entry Tombstone(FlashPartition& partition,
+ Address address,
+ uint32_t magic,
ChecksumAlgorithm* algorithm,
std::string_view key,
size_t alignment_bytes,
uint32_t key_version) {
- return Entry(magic,
+ return Entry(partition,
+ address,
+ magic,
algorithm,
key,
{},
@@ -93,13 +119,21 @@
key_version);
}
+ Entry() = default;
+
+ StatusWithSize Write(std::string_view key, span<const std::byte> value) const;
+
+ StatusWithSize ReadKey(KeyBuffer& key) const {
+ return ReadKey(partition(), address_, key_length(), key);
+ }
+
+ StatusWithSize ReadValue(span<std::byte> value) const;
+
Status VerifyChecksum(ChecksumAlgorithm* algorithm,
std::string_view key,
span<const std::byte> value) const;
- Status VerifyChecksumInFlash(FlashPartition* partition,
- FlashPartition::Address header_address,
- ChecksumAlgorithm* algorithm) const;
+ Status VerifyChecksumInFlash(ChecksumAlgorithm* algorithm) const;
// Calculates the total size of an entry, including padding.
static constexpr size_t size(size_t alignment_bytes,
@@ -109,51 +143,61 @@
alignment_bytes);
}
+ // The address at which the next possible entry could be located.
+ Address next_address() const { return address_ + size(); }
+
// Total size of this entry, including padding.
size_t size() const { return AlignUp(content_size(), alignment_bytes()); }
+ // The size of the value, without padding. The size is 0 if this is a
+ // tombstone entry.
+ size_t value_size() const {
+ return deleted() ? 0u : header_.value_size_bytes;
+ }
+
uint32_t magic() const { return header_.magic; }
+ uint32_t key_version() const { return header_.key_version; }
+
+ // True if this is a tombstone entry.
+ bool deleted() const {
+ return header_.value_size_bytes == kDeletedValueLength;
+ }
+
+ void DebugLog();
+
+ private:
+ static constexpr uint16_t kDeletedValueLength = 0xFFFF;
+
+ FlashPartition& partition() const { return *partition_; }
+
uint32_t checksum() const { return header_.checksum; }
// The length of the key in bytes. Keys are not null terminated.
size_t key_length() const { return header_.key_length_bytes; }
- static constexpr size_t max_key_length() { return kKeyLengthMask; }
-
- // The length of the value, which is 0 if this is a tombstone entry.
- size_t value_length() const {
- return deleted() ? 0u : header_.value_length_bytes;
- }
-
- static constexpr size_t max_value_length() { return 0xFFFE; }
-
size_t alignment_bytes() const { return (header_.alignment_units + 1) * 16; }
- uint32_t key_version() const { return header_.key_version; }
-
- // True if this is a tombstone entry.
- bool deleted() const {
- return header_.value_length_bytes == kDeletedValueLength;
- }
-
- private:
// The total size of the entry, excluding padding.
size_t content_size() const {
- return sizeof(EntryHeader) + key_length() + value_length();
+ return sizeof(EntryHeader) + key_length() + value_size();
}
- static constexpr uint32_t kKeyLengthMask = 0b111111;
- static constexpr uint16_t kDeletedValueLength = 0xFFFF;
-
- Entry(uint32_t magic,
+ Entry(FlashPartition& partition,
+ Address address,
+ uint32_t magic,
ChecksumAlgorithm* algorithm,
std::string_view key,
span<const std::byte> value,
- uint16_t value_length_bytes,
+ uint16_t value_size_bytes,
size_t alignment_bytes,
uint32_t key_version);
+ constexpr Entry(FlashPartition* partition,
+ Address address,
+ EntryHeader header)
+ : partition_(partition), address_(address), header_(header) {}
+
span<const std::byte> checksum_bytes() const {
return as_bytes(span(&header_.checksum, 1));
}
@@ -166,6 +210,8 @@
return (alignment_bytes + 15) / 16 - 1; // An alignment of 0 is invalid.
}
+ FlashPartition* partition_;
+ Address address_;
EntryHeader header_;
};