pw_kvs: Update valid_bytes for existing keys
When writing to keys with an existing entry,
SectorDescriptor::valid_bytes must be updated for sector with the
now-stale entry.
Change-Id: I6dc097fdca7ccec079c7c638b8cc071bd2018b78
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 249425c..9d10d19 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -15,6 +15,7 @@
#include "pw_kvs/key_value_store.h"
#include <algorithm>
+#include <cinttypes>
#include <cstring>
#include <type_traits>
@@ -288,11 +289,12 @@
KeyDescriptor* key_descriptor;
if (FindKeyDescriptor(key, &key_descriptor).ok()) {
- DBG("Writing over existing entry");
- return WriteEntryForExistingKey(key_descriptor, key, value);
+ DBG("Writing over existing entry for key 0x%08" PRIx32,
+ key_descriptor->key_hash);
+ return WriteEntryForExistingKey(
+ key_descriptor, KeyDescriptor::kValid, key, value);
}
- DBG("Writing new entry");
return WriteEntryForNewKey(key, value);
}
@@ -306,13 +308,9 @@
return Status::NOT_FOUND;
}
- key_descriptor->state = KeyDescriptor::kDeleted;
-
- SectorDescriptor* sector;
- TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, {})));
-
- DBG("Writing tombstone; found sector: %zu", SectorIndex(sector));
- return AppendEntry(sector, key_descriptor, key, {});
+ DBG("Writing tombstone for key 0x%08" PRIx32, key_descriptor->key_hash);
+ return WriteEntryForExistingKey(
+ key_descriptor, KeyDescriptor::kDeleted, key, {});
}
KeyValueStore::iterator& KeyValueStore::iterator::operator++() {
@@ -419,11 +417,10 @@
for (auto& descriptor : key_descriptors()) {
if (descriptor.key_hash == hash) {
- DBG("Found match! For hash: %zx", size_t(hash));
TRY(ReadEntryKey(descriptor.address, key.size(), key_buffer));
if (key == string_view(key_buffer, key.size())) {
- DBG("Keys matched too");
+ DBG("Found match for key hash 0x%08" PRIx32, hash);
*result = &descriptor;
return Status::OK;
}
@@ -470,14 +467,22 @@
}
Status KeyValueStore::WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
+ KeyDescriptor::State new_state,
string_view key,
span<const byte> value) {
- key_descriptor->state = KeyDescriptor::kValid;
+ // Find the original entry and sector to update the sector's valid_bytes.
+ EntryHeader original_entry;
+ TRY(ReadEntryHeader(key_descriptor->address, &original_entry));
+ SectorDescriptor& old_sector = SectorFromAddress(key_descriptor->address);
SectorDescriptor* sector;
TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, value)));
+
DBG("Writing existing entry; found sector: %zu", SectorIndex(sector));
- return AppendEntry(sector, key_descriptor, key, value);
+ TRY(AppendEntry(sector, key_descriptor, key, value, new_state));
+
+ old_sector.valid_bytes -= original_entry.size();
+ return Status::OK;
}
Status KeyValueStore::WriteEntryForNewKey(string_view key,
@@ -533,24 +538,22 @@
TRY(header.VerifyChecksum(
entry_header_format_.checksum, key, as_bytes(value)));
- SectorDescriptor* old_sector = SectorFromAddress(key_descriptor.address);
- if (old_sector == nullptr) {
- return Status::INTERNAL;
- }
+ 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, header.size(), &old_sector, true));
return AppendEntry(new_sector, &key_descriptor, key, as_bytes(value));
}
// Find either an existing sector with enough space that is not the sector to
// skip, or an empty sector. Maintains the invariant that there is always at
// least 1 empty sector unless set to bypass the rule.
-Status KeyValueStore::FindSectorWithSpace(SectorDescriptor** found_sector,
- size_t size,
- SectorDescriptor* sector_to_skip,
- bool bypass_empty_sector_rule) {
+Status KeyValueStore::FindSectorWithSpace(
+ SectorDescriptor** found_sector,
+ size_t size,
+ const SectorDescriptor* sector_to_skip,
+ bool bypass_empty_sector_rule) {
// The last_new_sector_ is the sector that was last selected as the "new empty
// sector" to write to. This last new sector is used as the starting point for
// the next "find a new empty sector to write to" operation. By using the last
@@ -671,6 +674,7 @@
}
if (sector_to_gc->valid_bytes != 0) {
+ ERR("Failed to relocate valid entries from sector being garbage collected");
return Status::INTERNAL;
}
@@ -686,11 +690,12 @@
Status KeyValueStore::AppendEntry(SectorDescriptor* sector,
KeyDescriptor* key_descriptor,
const string_view key,
- span<const byte> value) {
+ span<const byte> value,
+ KeyDescriptor::State new_state) {
// write header, key, and value
EntryHeader header;
- if (key_descriptor->deleted()) {
+ if (new_state == KeyDescriptor::kDeleted) {
header = EntryHeader::Tombstone(entry_header_format_.magic,
entry_header_format_.checksum,
key,
@@ -705,10 +710,11 @@
DBG("Appending entry with key version: %zx", size_t(header.key_version()));
- // Handles writing multiple concatenated buffers, while breaking up the writes
- // into alignment-sized blocks.
Address address = NextWritableAddress(sector);
DBG("Appending to address: %zx", size_t(address));
+
+ // Handles writing multiple concatenated buffers, while breaking up the writes
+ // into alignment-sized blocks.
TRY_ASSIGN(
size_t written,
partition_.Write(
@@ -721,6 +727,8 @@
key_descriptor->address = address;
key_descriptor->key_version = header.key_version();
+ key_descriptor->state = new_state;
+
sector->valid_bytes += written;
sector->tail_free_bytes -= written;
return Status::OK;
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index d7ee5fb..8d31b77 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -269,6 +269,7 @@
const KeyDescriptor& entry) const;
Status WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
+ KeyDescriptor::State new_state,
std::string_view key,
span<const std::byte> value);
@@ -278,7 +279,7 @@
Status FindSectorWithSpace(SectorDescriptor** found_sector,
size_t size,
- SectorDescriptor* sector_to_skip = nullptr,
+ const SectorDescriptor* sector_to_skip = nullptr,
bool bypass_empty_sector_rule = false);
Status FindOrRecoverSectorWithSpace(SectorDescriptor** sector, size_t size);
@@ -294,7 +295,8 @@
Status AppendEntry(SectorDescriptor* sector,
KeyDescriptor* key_descriptor,
std::string_view key,
- span<const std::byte> value);
+ span<const std::byte> value,
+ KeyDescriptor::State new_state = KeyDescriptor::kValid);
bool AddressInSector(const SectorDescriptor& sector, Address address) const {
const Address sector_base = SectorBaseAddress(§or);
@@ -321,8 +323,11 @@
return SectorIndex(sector) * partition_.sector_size_bytes();
}
- SectorDescriptor* SectorFromAddress(Address address) {
- return §or_map_[address / partition_.sector_size_bytes()];
+ SectorDescriptor& SectorFromAddress(Address address) {
+ const size_t index = address / partition_.sector_size_bytes();
+ // TODO: Add boundary checking once asserts are supported.
+ // DCHECK_LT(index, sector_map_size_);
+ return sector_map_[index];
}
Address NextWritableAddress(SectorDescriptor* sector) const {