pw_kvs: Don't write key values that don't change
Do not write incoming key vales that match the already-stored entry. The
check it done by comparing entry state, value length, checksum, and
actual value.
Change-Id: Ibf2f1145cf59144b832af8ae8b2e5580e91091a1
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index dbbddd3..15899ad 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -52,6 +52,7 @@
],
includes = ["public"],
deps = [
+ "//pw_assert",
"//pw_checksum",
"//pw_containers",
"//pw_log",
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index 0f38b2b..43ef1ec 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -52,6 +52,7 @@
dir_pw_status,
]
deps = [
+ dir_pw_assert,
dir_pw_checksum,
dir_pw_log,
]
diff --git a/pw_kvs/CMakeLists.txt b/pw_kvs/CMakeLists.txt
index 65b31ee..d2f3380 100644
--- a/pw_kvs/CMakeLists.txt
+++ b/pw_kvs/CMakeLists.txt
@@ -17,6 +17,7 @@
pw_containers
pw_status
PRIVATE_DEPS
+ pw_assert
pw_checksum
pw_log
pw_string
diff --git a/pw_kvs/entry.cc b/pw_kvs/entry.cc
index c393253..0429455 100644
--- a/pw_kvs/entry.cc
+++ b/pw_kvs/entry.cc
@@ -151,6 +151,31 @@
return StatusWithSize(read_size);
}
+Status Entry::ValueMatches(span<const std::byte> value) const {
+ if (value_size() != value.size_bytes()) {
+ return Status::NOT_FOUND;
+ }
+
+ Address address = address_ + sizeof(EntryHeader) + key_length();
+ Address end = address + value_size();
+ const std::byte* value_ptr = value.data();
+
+ std::array<std::byte, 2 * kMinAlignmentBytes> buffer;
+ while (address < end) {
+ const size_t read_size = std::min(size_t(end - address), buffer.size());
+ TRY(partition_->Read(address, span(buffer).first(read_size)));
+
+ if (std::memcmp(buffer.data(), value_ptr, read_size) != 0) {
+ return Status::NOT_FOUND;
+ }
+
+ address += read_size;
+ value_ptr += read_size;
+ }
+
+ return Status::OK;
+}
+
Status Entry::VerifyChecksum(string_view key, span<const byte> value) const {
if (checksum_algo_ == nullptr) {
return header_.checksum == 0 ? Status::OK : Status::DATA_LOSS;
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 80bb8cc..fa85c42 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -22,6 +22,7 @@
#include <type_traits>
#define PW_LOG_USE_ULTRA_SHORT_NAMES 1
+#include "pw_assert/assert.h"
#include "pw_kvs_private/macros.h"
#include "pw_log/log.h"
@@ -619,7 +620,7 @@
Entry entry;
TRY(ReadEntry(metadata, entry));
- return WriteEntry(key, value, new_state, &metadata, entry.size());
+ return WriteEntry(key, value, new_state, &metadata, &entry);
}
Status KeyValueStore::WriteEntryForNewKey(string_view key,
@@ -637,22 +638,46 @@
span<const byte> value,
EntryState new_state,
EntryMetadata* prior_metadata,
- size_t prior_size) {
- const size_t entry_size = Entry::size(partition_, key, value);
+ const Entry* prior_entry) {
+ Entry entry = CreateEntry(key, value, new_state);
+
+ // If new entry and prior entry have matching value size, state, and checksum,
+ // check if the values match. Directly compare the prior and new values
+ // because the checksum can not be depended on to establish equality, it can
+ // only be depended on to establish inequality.
+ if (prior_entry != nullptr &&
+ prior_entry->value_size() == entry.value_size() &&
+ prior_metadata->state() == new_state &&
+ prior_entry->checksum() == entry.checksum() &&
+ prior_entry->ValueMatches(value).ok()) {
+ // The new value matches the prior value, don't need to write anything.
+ // Just keep the existing entry.
+ DBG("Write for key 0x%08x with matching value skipped",
+ unsigned(prior_metadata->hash()));
+ return Status::OK;
+ }
// List of addresses for sectors with space for this entry.
Address* reserved_addresses = entry_cache_.TempReservedAddressesForWrite();
// Find addresses to write the entry to. This may involve garbage collecting
// one or more sectors.
+ const size_t entry_size = Entry::size(partition_, key, value);
TRY(GetAddressesForWrite(reserved_addresses, entry_size));
+ // Commiting to do the write, time to update last_transaction_id_. Update
+ // here, rather in CreateEntry, so last_transaction_id_ only increments for
+ // writes that are actually attempted.
+ last_transaction_id_ += 1;
+ PW_CHECK(last_transaction_id_ == entry.transaction_id());
+
// Write the entry at the first address that was found.
- Entry entry = CreateEntry(reserved_addresses[0], key, value, new_state);
+ entry.set_address(reserved_addresses[0]);
TRY(AppendEntry(entry, key, value));
// After writing the first entry successfully, update the key descriptors.
// Once a single new the entry is written, the old entries are invalidated.
+ size_t prior_size = prior_entry != nullptr ? prior_entry->size() : 0;
EntryMetadata new_metadata =
CreateOrUpdateKeyDescriptor(entry, key, prior_metadata, prior_size);
@@ -1181,8 +1206,7 @@
return FixErrors();
}
-KeyValueStore::Entry KeyValueStore::CreateEntry(Address address,
- string_view key,
+KeyValueStore::Entry KeyValueStore::CreateEntry(string_view key,
span<const byte> value,
EntryState state) {
// Always bump the transaction ID when creating a new entry.
@@ -1196,19 +1220,20 @@
// 2. The transaction ID is NOT incremented, because of the failure
// 3. (later) A new entry is written, re-using the transaction ID (oops)
//
- // By always burning transaction IDs, the above problem can't happen.
- last_transaction_id_ += 1;
+ // By always burning transaction IDs, the above problem can't happen. The
+ // actual updating of last_transaction_id_ is done once the write method is
+ // ready to commit to attempting an actual write.
+ uint32_t new_transaction_id = last_transaction_id_ + 1;
+
+ // Set address to zero, the address of the entry is set later.
+ const Address address = 0;
if (state == EntryState::kDeleted) {
return Entry::Tombstone(
- partition_, address, formats_.primary(), key, last_transaction_id_);
+ partition_, address, formats_.primary(), key, new_transaction_id);
}
- return Entry::Valid(partition_,
- address,
- formats_.primary(),
- key,
- value,
- last_transaction_id_);
+ return Entry::Valid(
+ partition_, address, formats_.primary(), key, value, new_transaction_id);
}
void KeyValueStore::LogDebugInfo() const {
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index 5bd8535..4b15880 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -197,7 +197,7 @@
std::cout << "Entries: " << map_.size() << '\n';
std::cout << "------------------------------------------------\n";
for (const auto& [key, value] : map_) {
- std::cout << key << " = " << value << '\n';
+ std::cout << key << " = [" << value << "]\n";
map_keys.insert(key);
}
std::cout << "\\===============================================/\n";
diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
index c6c3b0a..d2f33fc 100644
--- a/pw_kvs/key_value_store_test.cc
+++ b/pw_kvs/key_value_store_test.cc
@@ -717,7 +717,7 @@
format);
ASSERT_OK(kvs.Init());
- // Add two entries with different keys and values.
+ // Add one entry.
const char* key = "Key1";
DBG("PUT value for key: %s", key);
uint8_t written_value = 0xDA;
@@ -732,6 +732,38 @@
EXPECT_EQ(kvs.size(), 1u);
}
+TEST(InMemoryKvs, WriteOneKeyValueMultipleTimes) {
+ // Create and erase the fake flash.
+ Flash flash;
+ ASSERT_OK(flash.partition.Erase());
+
+ // Create and initialize the KVS.
+ constexpr EntryFormat format{.magic = 0xBAD'C0D3, .checksum = nullptr};
+ KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
+ format);
+ ASSERT_OK(kvs.Init());
+
+ // Add one entry, with the same key and value, multiple times.
+ const char* key = "Key1";
+ uint8_t written_value = 0xDA;
+ for (int i = 0; i < 50; i++) {
+ DBG("PUT [%d] value for key: %s", i, key);
+ ASSERT_OK(kvs.Put(key, written_value));
+ EXPECT_EQ(kvs.size(), 1u);
+ }
+
+ DBG("GET value for key: %s", key);
+ uint8_t actual_value;
+ ASSERT_OK(kvs.Get(key, &actual_value));
+ EXPECT_EQ(actual_value, written_value);
+
+ // Verify that only one entry was written to the KVS.
+ EXPECT_EQ(kvs.size(), 1u);
+ EXPECT_EQ(kvs.transaction_count(), 1u);
+ KeyValueStore::StorageStats stats = kvs.GetStorageStats();
+ EXPECT_EQ(stats.reclaimable_bytes, 0u);
+}
+
TEST(InMemoryKvs, Basic) {
const char* key1 = "Key1";
const char* key2 = "Key2";
diff --git a/pw_kvs/public/pw_kvs/internal/entry.h b/pw_kvs/public/pw_kvs/internal/entry.h
index aa81e16..a8f297f 100644
--- a/pw_kvs/public/pw_kvs/internal/entry.h
+++ b/pw_kvs/public/pw_kvs/internal/entry.h
@@ -122,6 +122,8 @@
StatusWithSize ReadValue(span<std::byte> buffer,
size_t offset_bytes = 0) const;
+ Status ValueMatches(span<const std::byte> value) const;
+
Status VerifyChecksum(std::string_view key,
span<const std::byte> value) const;
@@ -156,6 +158,8 @@
uint32_t magic() const { return header_.magic; }
+ uint32_t checksum() const { return header_.checksum; }
+
uint32_t transaction_id() const { return header_.transaction_id; }
// True if this is a tombstone entry.
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 061b512..e1a3b18 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -398,7 +398,7 @@
span<const std::byte> value,
EntryState new_state,
EntryMetadata* prior_metadata = nullptr,
- size_t prior_size = 0);
+ const internal::Entry* prior_entry = nullptr);
EntryMetadata CreateOrUpdateKeyDescriptor(const Entry& new_entry,
std::string_view key,
@@ -459,8 +459,7 @@
Status Repair();
- internal::Entry CreateEntry(Address address,
- std::string_view key,
+ internal::Entry CreateEntry(std::string_view key,
span<const std::byte> value,
EntryState state);
