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 {