pw_kvs: Transcation ID and key descriptor refactor
- Switch from per-key versions to a monotonically increasing KVS-global
transcation ID.
- Move KeyDescriptor and the hash function to their own files.
Change-Id: I05287137579d4fe2d72c6e176969d46006c2aae6
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index 50601da..6adb71a 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -30,6 +30,8 @@
"entry.cc",
"flash_memory.cc",
"key_value_store.cc",
+ "public/pw_kvs/internal/hash.h",
+ "public/pw_kvs/internal/key_descriptor.h",
"public/pw_kvs/internal/sector_descriptor.h",
"pw_kvs_private/entry.h",
"pw_kvs_private/macros.h",
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index a083724..e626bbb 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -34,6 +34,8 @@
"entry.cc",
"flash_memory.cc",
"key_value_store.cc",
+ "public/pw_kvs/internal/hash.h",
+ "public/pw_kvs/internal/key_descriptor.h",
"public/pw_kvs/internal/sector_descriptor.h",
"pw_kvs_private/entry.h",
"pw_kvs_private/macros.h",
diff --git a/pw_kvs/entry.cc b/pw_kvs/entry.cc
index 33e86a8..ad81b12 100644
--- a/pw_kvs/entry.cc
+++ b/pw_kvs/entry.cc
@@ -20,7 +20,7 @@
#include "pw_kvs_private/macros.h"
#include "pw_log/log.h"
-namespace pw::kvs {
+namespace pw::kvs::internal {
using std::byte;
using std::string_view;
@@ -60,7 +60,7 @@
span<const byte> value,
uint16_t value_size_bytes,
size_t alignment_bytes,
- uint32_t key_version)
+ uint32_t transaction_id)
: Entry(&partition,
address,
{.magic = magic,
@@ -68,7 +68,7 @@
.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}) {
+ .transaction_id = transaction_id}) {
if (algorithm != nullptr) {
span<const byte> checksum = CalculateChecksum(algorithm, key, value);
std::memcpy(&header_.checksum,
@@ -207,4 +207,4 @@
return algorithm->Finish();
}
-} // namespace pw::kvs
+} // namespace pw::kvs::internal
diff --git a/pw_kvs/entry_test.cc b/pw_kvs/entry_test.cc
index 5022034..2c5f7c4 100644
--- a/pw_kvs/entry_test.cc
+++ b/pw_kvs/entry_test.cc
@@ -24,7 +24,7 @@
#include "pw_kvs_private/byte_utils.h"
#include "pw_span/span.h"
-namespace pw::kvs {
+namespace pw::kvs::internal {
namespace {
using std::byte;
@@ -60,7 +60,7 @@
EXPECT_FALSE(entry.deleted());
EXPECT_EQ(entry.magic(), 9u);
EXPECT_EQ(entry.value_size(), sizeof("123"));
- EXPECT_EQ(entry.key_version(), 9876u);
+ EXPECT_EQ(entry.transaction_id(), 9876u);
}
TEST(Entry, Construct_Tombstone) {
@@ -72,7 +72,7 @@
EXPECT_TRUE(entry.deleted());
EXPECT_EQ(entry.magic(), 99u);
EXPECT_EQ(entry.value_size(), 0u);
- EXPECT_EQ(entry.key_version(), 123u);
+ EXPECT_EQ(entry.transaction_id(), 123u);
}
constexpr auto kHeader1 = ByteStr(
@@ -111,7 +111,7 @@
EXPECT_EQ(entry_.magic(), 0x600DF00Du);
EXPECT_EQ(entry_.key_length(), 5u);
EXPECT_EQ(entry_.value_size(), 6u);
- EXPECT_EQ(entry_.key_version(), 0x96979899u);
+ EXPECT_EQ(entry_.transaction_id(), 0x96979899u);
EXPECT_FALSE(entry_.deleted());
}
@@ -229,7 +229,7 @@
EXPECT_EQ(entry_.magic(), 0x600DF00Du);
EXPECT_EQ(entry_.key_length(), 1u);
EXPECT_EQ(entry_.value_size(), 0u);
- EXPECT_EQ(entry_.key_version(), 0x03020100u);
+ EXPECT_EQ(entry_.transaction_id(), 0x03020100u);
EXPECT_TRUE(entry_.deleted());
}
@@ -300,4 +300,4 @@
EXPECT_EQ(Status::OK, entry.VerifyChecksumInFlash(&checksum));
}
} // namespace
-} // namespace pw::kvs
+} // namespace pw::kvs::internal
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 2fe9504..934b296 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -27,6 +27,7 @@
namespace pw::kvs {
namespace {
+using internal::Entry;
using std::byte;
using std::string_view;
@@ -45,8 +46,7 @@
entry_header_format_(format),
options_(options),
key_descriptors_(key_descriptor_list),
- sectors_(sector_descriptor_list),
- last_new_sector_(sectors_.data()) {}
+ sectors_(sector_descriptor_list) {}
Status KeyValueStore::Init() {
INF("Initializing key value store");
@@ -62,10 +62,6 @@
sectors_.resize(partition_.sector_count());
key_descriptors_.clear();
- // TODO: init last_new_sector_ to a random sector. Since the on-flash stored
- // information does not allow recovering the previous last_new_sector_ after
- // clean start, random is a good second choice.
-
const size_t sector_size_bytes = partition_.sector_size_bytes();
if (working_buffer_.size() < sector_size_bytes) {
@@ -132,12 +128,27 @@
}
DBG("Second pass: Count valid bytes in each sector");
+ const KeyDescriptor* newest_key = nullptr;
+ last_transaction_id_ = 0;
+
// For every valid key, increment the valid bytes for that sector.
for (KeyDescriptor& key_descriptor : key_descriptors_) {
Entry entry;
- TRY(Entry::Read(partition_, key_descriptor.address, &entry));
- SectorFromAddress(key_descriptor.address)->AddValidBytes(entry.size());
+ TRY(Entry::Read(partition_, key_descriptor.address(), &entry));
+ SectorFromKey(key_descriptor)->AddValidBytes(entry.size());
+
+ if (key_descriptor.IsNewerThan(last_transaction_id_)) {
+ last_transaction_id_ = key_descriptor.transaction_id();
+ newest_key = &key_descriptor;
+ }
}
+
+ if (newest_key == nullptr) {
+ last_new_sector_ = sectors_.begin();
+ } else {
+ last_new_sector_ = SectorFromKey(newest_key);
+ }
+
initialized_ = true;
INF("KeyValueStore init complete: active keys %zu, deleted keys %zu, sectors "
@@ -171,18 +182,7 @@
const string_view key(key_buffer.data(), key_length);
TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
-
- KeyDescriptor key_descriptor(
- key,
- entry.key_version(),
- entry_address,
- entry.deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
-
- DBG("Key hash: %zx (%zu)",
- size_t(key_descriptor.key_hash),
- size_t(key_descriptor.key_hash));
-
- TRY(AppendNewOrOverwriteStaleExistingDescriptor(key_descriptor));
+ TRY(AppendNewOrOverwriteStaleExistingDescriptor(entry.descriptor(key)));
*next_entry_address = entry.next_address();
return Status::OK;
@@ -196,7 +196,7 @@
const KeyDescriptor& key_descriptor) {
// With the new key descriptor, either add it to the descriptor table or
// overwrite an existing entry with an older version of the key.
- KeyDescriptor* existing_descriptor = FindDescriptor(key_descriptor.key_hash);
+ KeyDescriptor* existing_descriptor = FindDescriptor(key_descriptor.hash());
// Write a new entry.
if (existing_descriptor == nullptr) {
@@ -204,15 +204,18 @@
return Status::RESOURCE_EXHAUSTED;
}
key_descriptors_.push_back(key_descriptor);
- } else if (existing_descriptor->key_version < key_descriptor.key_version) {
+ } else if (key_descriptor.IsNewerThan(
+ existing_descriptor->transaction_id())) {
// Existing entry is old; replace the existing entry with the new one.
*existing_descriptor = key_descriptor;
} else {
- // Otherwise, check for data integrity and leave the existing entry.
- if (existing_descriptor->key_version == key_descriptor.key_version) {
- ERR("Data loss: Duplicated old(=%zu) and new(=%zu) version",
- size_t(existing_descriptor->key_version),
- size_t(key_descriptor.key_version));
+ // Otherwise, check if the entries have a duplicate transaction ID, which is
+ // not valid.
+ if (existing_descriptor->transaction_id() ==
+ key_descriptor.transaction_id()) {
+ ERR("Data loss: Duplicated old(=%zu) and new(=%zu) transaction ID",
+ size_t(existing_descriptor->transaction_id()),
+ size_t(key_descriptor.transaction_id()));
return Status::DATA_LOSS;
}
DBG("Found stale entry when appending; ignoring");
@@ -222,7 +225,7 @@
KeyValueStore::KeyDescriptor* KeyValueStore::FindDescriptor(uint32_t hash) {
for (KeyDescriptor& key_descriptor : key_descriptors_) {
- if (key_descriptor.key_hash == hash) {
+ if (key_descriptor.hash() == hash) {
return &key_descriptor;
}
}
@@ -238,7 +241,7 @@
TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
Entry entry;
- TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address, &entry));
+ TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address(), &entry));
StatusWithSize result = entry.ReadValue(value_buffer, offset_bytes);
if (result.ok() && options_.verify_on_read && offset_bytes == 0u) {
@@ -276,8 +279,8 @@
if (status.ok()) {
DBG("Overwriting entry for key %#08" PRIx32 " in sector %u",
- key_descriptor->key_hash,
- SectorIndex(SectorFromAddress(key_descriptor->address)));
+ key_descriptor->hash(),
+ SectorIndex(SectorFromKey(key_descriptor)));
return WriteEntryForExistingKey(
key_descriptor, KeyDescriptor::kValid, key, value);
}
@@ -296,8 +299,8 @@
TRY(FindExistingKeyDescriptor(key, &key_descriptor));
DBG("Writing tombstone for key %#08" PRIx32 " in sector %u",
- key_descriptor->key_hash,
- SectorIndex(SectorFromAddress(key_descriptor->address)));
+ key_descriptor->hash(),
+ SectorIndex(SectorFromKey(key_descriptor)));
return WriteEntryForExistingKey(
key_descriptor, KeyDescriptor::kDeleted, key, {});
}
@@ -314,7 +317,7 @@
std::memset(item_.key_buffer_.data(), 0, item_.key_buffer_.size());
Entry entry;
- if (Entry::Read(item_.kvs_.partition_, descriptor().address, &entry).ok()) {
+ if (Entry::Read(item_.kvs_.partition_, descriptor().address(), &entry).ok()) {
entry.ReadKey(item_.key_buffer_);
}
@@ -351,23 +354,11 @@
TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
Entry entry;
- TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address, &entry));
+ TRY_WITH_SIZE(Entry::Read(partition_, key_descriptor->address(), &entry));
return StatusWithSize(entry.value_size());
}
-uint32_t KeyValueStore::HashKey(string_view string) {
- uint32_t hash = 0;
- uint32_t coefficient = 65599u;
-
- for (char ch : string) {
- hash += coefficient * unsigned(ch);
- coefficient *= 65599u;
- }
-
- return hash;
-}
-
Status KeyValueStore::FixedSizeGet(std::string_view key,
byte* value,
size_t size_bytes) const {
@@ -405,13 +396,13 @@
//
Status KeyValueStore::FindKeyDescriptor(string_view key,
const KeyDescriptor** result) const {
- const uint32_t hash = HashKey(key);
+ const uint32_t hash = internal::Hash(key);
Entry::KeyBuffer key_buffer;
for (auto& descriptor : key_descriptors_) {
- if (descriptor.key_hash == hash) {
+ if (descriptor.hash() == hash) {
TRY(Entry::ReadKey(
- partition_, descriptor.address, key.size(), key_buffer.data()));
+ partition_, descriptor.address(), key.size(), key_buffer.data()));
if (key == string_view(key_buffer.data(), key.size())) {
DBG("Found match for key hash 0x%08" PRIx32, hash);
@@ -451,8 +442,8 @@
span<const byte> value) {
// Find the original entry and sector to update the sector's valid_bytes.
Entry original_entry;
- TRY(Entry::Read(partition_, key_descriptor->address, &original_entry));
- SectorDescriptor* old_sector = SectorFromAddress(key_descriptor->address);
+ TRY(Entry::Read(partition_, key_descriptor->address(), &original_entry));
+ SectorDescriptor* old_sector = SectorFromKey(key_descriptor);
SectorDescriptor* sector;
TRY(FindOrRecoverSectorWithSpace(§or,
@@ -461,13 +452,13 @@
SectorIndex(sector),
SectorBaseAddress(sector));
- if (old_sector != SectorFromAddress(key_descriptor->address)) {
+ if (old_sector != SectorFromKey(key_descriptor)) {
DBG("Sector for old entry (size %zu) was garbage collected. Old entry "
"relocated to sector %u",
original_entry.size(),
- SectorIndex(SectorFromAddress(key_descriptor->address)));
+ SectorIndex(SectorFromKey(key_descriptor)));
- old_sector = SectorFromAddress(key_descriptor->address);
+ old_sector = SectorFromKey(key_descriptor);
}
TRY(AppendEntry(sector, key_descriptor, key, value, new_state));
@@ -484,14 +475,14 @@
return Status::RESOURCE_EXHAUSTED;
}
- // Create the KeyDescriptor that will be added to the list. The version and
- // address will be set by AppendEntry.
- KeyDescriptor key_descriptor(key, 0, 0);
-
SectorDescriptor* sector;
TRY(FindOrRecoverSectorWithSpace(§or,
Entry::size(partition_, key, value)));
DBG("Writing new entry; found sector: %u", SectorIndex(sector));
+
+ // Create the KeyDescriptor that will be added to the list. The transaction ID
+ // and address will be set by AppendEntry.
+ KeyDescriptor key_descriptor(key);
TRY(AppendEntry(sector, &key_descriptor, key, value, KeyDescriptor::kValid));
// Only add the entry when we are certain the write succeeded.
@@ -512,7 +503,7 @@
// store the key and value in the TempEntry stored in the static allocated
// working_buffer_.
Entry entry;
- TRY(Entry::Read(partition_, key_descriptor.address, &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)));
@@ -524,13 +515,16 @@
TRY(entry.VerifyChecksum(
entry_header_format_.checksum, key, as_bytes(value)));
- SectorDescriptor* old_sector = SectorFromAddress(key_descriptor.address);
+ SectorDescriptor* old_sector = SectorFromKey(key_descriptor);
// Find a new sector for the entry and write it to the new location.
SectorDescriptor* new_sector;
TRY(FindSectorWithSpace(&new_sector, entry.size(), old_sector, true));
- TRY(AppendEntry(
- new_sector, &key_descriptor, key, as_bytes(value), key_descriptor.state));
+ 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.
@@ -677,7 +671,7 @@
// Step 2: Move any valid entries in the GC sector to other sectors
if (sector_to_gc->valid_bytes() != 0) {
for (auto& descriptor : key_descriptors_) {
- if (AddressInSector(*sector_to_gc, descriptor.address)) {
+ if (AddressInSector(*sector_to_gc, descriptor.address())) {
DBG(" Relocate entry");
TRY(RelocateEntry(descriptor));
}
@@ -703,36 +697,16 @@
Status KeyValueStore::AppendEntry(SectorDescriptor* sector,
KeyDescriptor* key_descriptor,
- const string_view key,
+ string_view key,
span<const byte> value,
KeyDescriptor::State new_state) {
const Address address = NextWritableAddress(sector);
- DBG("Appending to address: %#zx", size_t(address));
+ Entry entry = CreateEntry(address, key, value, new_state);
- Entry entry;
-
- if (new_state == KeyDescriptor::kDeleted) {
- entry = Entry::Tombstone(partition_,
- address,
- entry_header_format_.magic,
- entry_header_format_.checksum,
- key,
- partition_.alignment_bytes(),
- key_descriptor->key_version + 1);
- } else {
- 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",
+ DBG("Appending %zu B entry with transaction ID %" PRIu32 " to address %#zx",
entry.size(),
- unsigned(entry.key_version()));
+ entry.transaction_id(),
+ size_t(address));
TRY_ASSIGN(const size_t written, entry.Write(key, value));
@@ -740,14 +714,36 @@
TRY(entry.VerifyChecksumInFlash(entry_header_format_.checksum));
}
- key_descriptor->address = address;
- key_descriptor->key_version = entry.key_version();
- key_descriptor->state = new_state;
-
+ entry.UpdateDescriptor(key_descriptor);
sector->MarkValidBytesWritten(written);
return Status::OK;
}
+Entry KeyValueStore::CreateEntry(Address address,
+ std::string_view key,
+ span<const byte> value,
+ KeyDescriptor::State state) {
+ const uint32_t transaction_id = ++last_transaction_id_;
+
+ if (state == KeyDescriptor::kDeleted) {
+ return Entry::Tombstone(partition_,
+ address,
+ entry_header_format_.magic,
+ entry_header_format_.checksum,
+ key,
+ partition_.alignment_bytes(),
+ transaction_id);
+ }
+ return Entry::Valid(partition_,
+ address,
+ entry_header_format_.magic,
+ entry_header_format_.checksum,
+ key,
+ value,
+ partition_.alignment_bytes(),
+ transaction_id);
+}
+
void KeyValueStore::LogDebugInfo() {
const size_t sector_size_bytes = partition_.sector_size_bytes();
DBG("====================== KEY VALUE STORE DUMP =========================");
@@ -769,10 +765,10 @@
const KeyDescriptor& kd = key_descriptors_[i];
DBG(" |%3zu: | %8zx |%8zu | %8zu | %8zx",
i,
- size_t(kd.key_hash),
- size_t(kd.key_version),
- size_t(kd.address),
- size_t(kd.address));
+ size_t(kd.hash()),
+ size_t(kd.transaction_id()),
+ size_t(kd.address()),
+ size_t(kd.address()));
}
DBG(" ");
@@ -838,11 +834,11 @@
void KeyValueStore::LogKeyDescriptor() const {
DBG("Key descriptors: count %zu", key_descriptors_.size());
for (auto& key : key_descriptors_) {
- DBG(" - Key: %s, hash %#zx, version %zu, address %#zx",
+ DBG(" - Key: %s, hash %#zx, transaction ID %zu, address %#zx",
key.deleted() ? "Deleted" : "Valid",
- static_cast<size_t>(key.key_hash),
- static_cast<size_t>(key.key_version),
- static_cast<size_t>(key.address));
+ static_cast<size_t>(key.hash()),
+ static_cast<size_t>(key.transaction_id()),
+ static_cast<size_t>(key.address()));
}
}
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index 6f3a5a4..2e04fc0 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -118,7 +118,8 @@
// Either add a new key or replace an existing one.
if (empty() || random_int() % 2 == 0) {
- key = random_string(random_int() % (Entry::kMaxKeyLength + 1));
+ key = random_string(random_int() %
+ (internal::Entry::kMaxKeyLength + 1));
} else {
key = RandomPresentKey();
}
@@ -221,7 +222,7 @@
Status result = kvs_.Put(key, as_bytes(span(value)));
- if (key.empty() || key.size() > Entry::kMaxKeyLength) {
+ if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
EXPECT_EQ(Status::INVALID_ARGUMENT, result);
} else if (map_.size() == kvs_.max_size()) {
EXPECT_EQ(Status::RESOURCE_EXHAUSTED, result);
@@ -251,7 +252,7 @@
Status result = kvs_.Delete(key);
- if (key.empty() || key.size() > Entry::kMaxKeyLength) {
+ if (key.empty() || key.size() > internal::Entry::kMaxKeyLength) {
EXPECT_EQ(Status::INVALID_ARGUMENT, result);
} else if (map_.count(key) == 0) {
EXPECT_EQ(Status::NOT_FOUND, result);
diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
index 0c29979..d47eed4 100644
--- a/pw_kvs/key_value_store_test.cc
+++ b/pw_kvs/key_value_store_test.cc
@@ -45,6 +45,7 @@
namespace pw::kvs {
namespace {
+using internal::EntryHeader;
using std::byte;
constexpr size_t kMaxEntries = 256;
diff --git a/pw_kvs/public/pw_kvs/internal/hash.h b/pw_kvs/public/pw_kvs/internal/hash.h
new file mode 100644
index 0000000..5e97e69
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/internal/hash.h
@@ -0,0 +1,34 @@
+// 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 <cstddef>
+#include <string_view>
+
+namespace pw::kvs::internal {
+
+// The hash function used to hash keys.
+constexpr uint32_t Hash(std::string_view string) {
+ uint32_t hash = 0;
+ uint32_t coefficient = 65599u;
+
+ for (char ch : string) {
+ hash += coefficient * uint32_t(ch);
+ coefficient *= 65599u;
+ }
+
+ return hash;
+}
+
+} // namespace pw::kvs::internal
diff --git a/pw_kvs/public/pw_kvs/internal/key_descriptor.h b/pw_kvs/public/pw_kvs/internal/key_descriptor.h
new file mode 100644
index 0000000..bc4d2f8
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/internal/key_descriptor.h
@@ -0,0 +1,67 @@
+// 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 <cstddef>
+#include <cstdint>
+#include <string_view>
+
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/hash.h"
+
+namespace pw::kvs::internal {
+
+// Caches information about a key-value entry. Facilitates quickly finding
+// entries without having to read flash.
+class KeyDescriptor {
+ public:
+ enum State { kValid, kDeleted };
+
+ constexpr KeyDescriptor(std::string_view key)
+ : KeyDescriptor(key, 0, 0, kValid) {}
+
+ uint32_t hash() const { return key_hash_; }
+ uint32_t transaction_id() const { return transaction_id_; }
+ uint32_t address() const { return address_; }
+ State state() const { return state_; }
+
+ // True if the KeyDesctiptor's transaction ID is newer than the specified ID.
+ bool IsNewerThan(uint32_t other_transaction_id) const {
+ // TODO: Consider handling rollover.
+ return transaction_id() > other_transaction_id;
+ }
+
+ bool deleted() const { return state_ == kDeleted; }
+
+ private:
+ friend class Entry;
+
+ constexpr KeyDescriptor(std::string_view key,
+ uint32_t version,
+ FlashPartition::Address address,
+ State initial_state)
+ : key_hash_(Hash(key)),
+ transaction_id_(version),
+ address_(address),
+ state_(initial_state) {}
+
+ uint32_t key_hash_;
+ uint32_t transaction_id_;
+ FlashPartition::Address address_;
+
+ // TODO: This information could be packed into the above fields to save RAM.
+ State state_;
+};
+
+} // namespace pw::kvs::internal
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index da40270..d6a6768 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -22,6 +22,7 @@
#include "pw_containers/vector.h"
#include "pw_kvs/checksum.h"
#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/key_descriptor.h"
#include "pw_kvs/internal/sector_descriptor.h"
#include "pw_span/span.h"
#include "pw_status/status.h"
@@ -30,6 +31,8 @@
namespace pw::kvs {
namespace internal {
+class Entry;
+
template <typename T, typename = decltype(span(std::declval<T>()))>
constexpr bool ConvertsToSpan(int) {
return true;
@@ -49,9 +52,6 @@
using ConvertsToSpan =
std::bool_constant<internal::ConvertsToSpan<std::remove_reference_t<T>>(0)>;
-// Internal-only persistent storage header format.
-class Entry;
-
struct EntryHeaderFormat {
// Magic is a unique constant identifier for entries.
//
@@ -82,9 +82,6 @@
};
class KeyValueStore {
- protected:
- struct KeyDescriptor;
-
public:
// TODO: Make this configurable.
static constexpr size_t kWorkingBufferSizeBytes = (4 * 1024);
@@ -210,7 +207,7 @@
constexpr iterator(const KeyValueStore& kvs, size_t index)
: item_(kvs), index_(index) {}
- const KeyDescriptor& descriptor() const {
+ const internal::KeyDescriptor& descriptor() const {
return item_.kvs_.key_descriptors_[index_];
}
@@ -232,30 +229,9 @@
protected:
using Address = FlashPartition::Address;
+ using KeyDescriptor = internal::KeyDescriptor;
using SectorDescriptor = internal::SectorDescriptor;
- struct KeyDescriptor {
- enum State { kValid, kDeleted };
-
- KeyDescriptor(std::string_view key,
- uint32_t version,
- Address addr,
- State initial_state = kValid)
- : key_hash(HashKey(key)),
- key_version(version),
- address(addr),
- state(initial_state) {}
-
- bool deleted() const { return state == kDeleted; }
-
- uint32_t key_hash;
- uint32_t key_version;
- Address address; // In partition address.
-
- // TODO: This information should be packed into the above fields to save RAM
- State state;
- };
-
// In the future, will be able to provide additional EntryHeaderFormats for
// backwards compatibility.
KeyValueStore(FlashPartition* partition,
@@ -265,8 +241,6 @@
const Options& options);
private:
- static uint32_t HashKey(std::string_view string);
-
Status FixedSizeGet(std::string_view key,
std::byte* value,
size_t size_bytes) const;
@@ -339,18 +313,27 @@
return SectorIndex(sector) * partition_.sector_size_bytes();
}
- SectorDescriptor* SectorFromAddress(Address address) {
- const size_t index = address / partition_.sector_size_bytes();
+ SectorDescriptor* SectorFromKey(const KeyDescriptor& descriptor) {
+ const size_t index = descriptor.address() / partition_.sector_size_bytes();
// TODO: Add boundary checking once asserts are supported.
// DCHECK_LT(index, sector_map_size_);
return §ors_[index];
}
+ SectorDescriptor* SectorFromKey(const KeyDescriptor* descriptor) {
+ return SectorFromKey(*descriptor);
+ }
+
Address NextWritableAddress(const SectorDescriptor* sector) const {
return SectorBaseAddress(sector) + partition_.sector_size_bytes() -
sector->writable_bytes();
}
+ internal::Entry CreateEntry(Address address,
+ std::string_view key,
+ span<const std::byte> value,
+ KeyDescriptor::State state);
+
void LogSectors() const;
void LogKeyDescriptor() const;
@@ -379,6 +362,7 @@
// Use SectorDescriptor* for the persistent storage rather than sector index
// because SectorDescriptor* is the standard way to identify a sector.
SectorDescriptor* last_new_sector_;
+ uint32_t last_transaction_id_;
bool initialized_ = false;
diff --git a/pw_kvs/pw_kvs_private/entry.h b/pw_kvs/pw_kvs_private/entry.h
index f42df7c..d898f56 100644
--- a/pw_kvs/pw_kvs_private/entry.h
+++ b/pw_kvs/pw_kvs_private/entry.h
@@ -24,9 +24,10 @@
#include "pw_kvs/alignment.h"
#include "pw_kvs/checksum.h"
#include "pw_kvs/flash_memory.h"
+#include "pw_kvs/internal/key_descriptor.h"
#include "pw_span/span.h"
-namespace pw::kvs {
+namespace pw::kvs::internal {
// Disk format of the header used for each key-value entry.
struct EntryHeader {
@@ -50,8 +51,8 @@
// or 0xFFFF) is reserved to indicate this is a tombstone (deleted) entry.
uint16_t value_size_bytes;
- // The version of the key. Monotonically increasing.
- uint32_t key_version;
+ // The transaction ID for this key. Monotonically increasing.
+ uint32_t transaction_id;
};
static_assert(sizeof(EntryHeader) == 16, "EntryHeader must not have padding");
@@ -90,7 +91,7 @@
std::string_view key,
span<const std::byte> value,
size_t alignment_bytes,
- uint32_t key_version) {
+ uint32_t transaction_id) {
return Entry(partition,
address,
magic,
@@ -99,7 +100,7 @@
value,
value.size(),
alignment_bytes,
- key_version);
+ transaction_id);
}
// Creates a new Entry for a tombstone entry, which marks a deleted key.
@@ -109,7 +110,7 @@
ChecksumAlgorithm* algorithm,
std::string_view key,
size_t alignment_bytes,
- uint32_t key_version) {
+ uint32_t transaction_id) {
return Entry(partition,
address,
magic,
@@ -118,11 +119,25 @@
{},
kDeletedValueLength,
alignment_bytes,
- key_version);
+ transaction_id);
}
Entry() = default;
+ KeyDescriptor descriptor(std::string_view key) const {
+ return KeyDescriptor(
+ key,
+ transaction_id(),
+ address_,
+ deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid);
+ }
+
+ void UpdateDescriptor(KeyDescriptor* kd) {
+ kd->transaction_id_ = transaction_id();
+ kd->address_ = address_;
+ kd->state_ = deleted() ? KeyDescriptor::kDeleted : KeyDescriptor::kValid;
+ }
+
StatusWithSize Write(std::string_view key, span<const std::byte> value) const;
// Reads a key into a buffer, which must be large enough for a max-length key.
@@ -169,7 +184,7 @@
uint32_t magic() const { return header_.magic; }
- uint32_t key_version() const { return header_.key_version; }
+ uint32_t transaction_id() const { return header_.transaction_id; }
// True if this is a tombstone entry.
bool deleted() const {
@@ -200,7 +215,7 @@
span<const std::byte> value,
uint16_t value_size_bytes,
size_t alignment_bytes,
- uint32_t key_version);
+ uint32_t transaction_id);
constexpr Entry(FlashPartition* partition,
Address address,
@@ -224,4 +239,4 @@
EntryHeader header_;
};
-} // namespace pw::kvs
+} // namespace pw::kvs::internal
