pw_kvs: Handle key hash collisions
- Log and return ALREADY_EXISTS if a Put operation introduces a key
whose hash collides with another key already known to the KVS.
- Add tests to cover key hash collisions with Put, Get, ValueSize, and
Delete.
Change-Id: I957e7c4998f700517b70d3b999f0e3f4f4621f6d
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index fd54654..85565b9 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -250,11 +250,7 @@
TRY_WITH_SIZE(CheckOperation(key));
const KeyDescriptor* key_descriptor;
- TRY_WITH_SIZE(FindKeyDescriptor(key, &key_descriptor));
-
- if (key_descriptor->deleted()) {
- return StatusWithSize(Status::NOT_FOUND);
- }
+ TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
Entry header;
TRY_WITH_SIZE(ReadEntryHeader(key_descriptor->address, &header));
@@ -288,7 +284,9 @@
}
KeyDescriptor* key_descriptor;
- if (FindKeyDescriptor(key, &key_descriptor).ok()) {
+ Status status = FindKeyDescriptor(key, &key_descriptor);
+
+ if (status.ok()) {
DBG("Writing over existing entry for key 0x%08" PRIx32 " in sector %zu",
key_descriptor->key_hash,
SectorIndex(SectorFromAddress(key_descriptor->address)));
@@ -296,18 +294,18 @@
key_descriptor, KeyDescriptor::kValid, key, value);
}
- return WriteEntryForNewKey(key, value);
+ if (status == Status::NOT_FOUND) {
+ return WriteEntryForNewKey(key, value);
+ }
+
+ return status;
}
Status KeyValueStore::Delete(string_view key) {
TRY(CheckOperation(key));
KeyDescriptor* key_descriptor;
- TRY(FindKeyDescriptor(key, &key_descriptor));
-
- if (key_descriptor->deleted()) {
- return Status::NOT_FOUND;
- }
+ TRY(FindExistingKeyDescriptor(key, &key_descriptor));
DBG("Writing tombstone for existing key 0x%08" PRIx32 " in sector %zu",
key_descriptor->key_hash,
@@ -363,11 +361,7 @@
TRY_WITH_SIZE(CheckOperation(key));
const KeyDescriptor* key_descriptor;
- TRY_WITH_SIZE(FindKeyDescriptor(key, &key_descriptor));
-
- if (key_descriptor->deleted()) {
- return StatusWithSize(Status::NOT_FOUND);
- }
+ TRY_WITH_SIZE(FindExistingKeyDescriptor(key, &key_descriptor));
Entry header;
TRY_WITH_SIZE(ReadEntryHeader(key_descriptor->address, &header));
@@ -413,6 +407,15 @@
return Status::OK;
}
+// Searches for a KeyDescriptor that matches this key and sets *result to point
+// to it if one is found.
+//
+// OK: there is a matching descriptor and *result is set
+// NOT_FOUND: there is no descriptor that matches this key, but this key
+// has a unique hash (and could potentially be added to the KVS)
+// ALREADY_EXISTS: there is no descriptor that matches this key, but the
+// key's hash collides with the hash for an existing descriptor
+//
Status KeyValueStore::FindKeyDescriptor(string_view key,
const KeyDescriptor** result) const {
char key_buffer[kMaxKeyLength];
@@ -426,12 +429,34 @@
DBG("Found match for key hash 0x%08" PRIx32, hash);
*result = &descriptor;
return Status::OK;
+ } else {
+ WRN("Found key hash collision for 0x%08" PRIx32, hash);
+ return Status::ALREADY_EXISTS;
}
}
}
return Status::NOT_FOUND;
}
+// Searches for a KeyDescriptor that matches this key and sets *result to point
+// to it if one is found.
+//
+// OK: there is a matching descriptor and *result is set
+// NOT_FOUND: there is no descriptor that matches this key
+//
+Status KeyValueStore::FindExistingKeyDescriptor(
+ string_view key, const KeyDescriptor** result) const {
+ Status status = FindKeyDescriptor(key, result);
+
+ // If the key's hash collides with an existing key or if the key is deleted,
+ // treat it as if it is not in the KVS.
+ if (status == Status::ALREADY_EXISTS ||
+ (status.ok() && (*result)->deleted())) {
+ return Status::NOT_FOUND;
+ }
+ return status;
+}
+
Status KeyValueStore::ReadEntryHeader(Address address, Entry* header) const {
return partition_.Read(address, sizeof(*header), header).status();
}
@@ -646,10 +671,7 @@
Status KeyValueStore::FindOrRecoverSectorWithSpace(SectorDescriptor** sector,
size_t size) {
Status result = FindSectorWithSpace(sector, size);
- if (result.ok()) {
- return result;
- }
- if (options_.partial_gc_on_write) {
+ if (result == Status::RESOURCE_EXHAUSTED && options_.partial_gc_on_write) {
// Garbage collect and then try again to find the best sector.
TRY(GarbageCollectOneSector());
return FindSectorWithSpace(sector, size);
diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
index 70e5db1..b608b8f 100644
--- a/pw_kvs/key_value_store_test.cc
+++ b/pw_kvs/key_value_store_test.cc
@@ -297,6 +297,43 @@
EXPECT_TRUE(kvs_.empty());
}
+TEST_F(EmptyInitializedKvs, Collision_WithPresentKey) {
+ // Both hash to 0x19df36f0.
+ constexpr std::string_view key1 = "D4";
+ constexpr std::string_view key2 = "dFU6S";
+
+ ASSERT_EQ(Status::OK, kvs_.Put(key1, 1000));
+
+ EXPECT_EQ(Status::ALREADY_EXISTS, kvs_.Put(key2, 999));
+
+ int value = 0;
+ EXPECT_EQ(Status::OK, kvs_.Get(key1, &value));
+ EXPECT_EQ(1000, value);
+
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.Get(key2, &value));
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.ValueSize(key2).status());
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.Delete(key2));
+}
+
+TEST_F(EmptyInitializedKvs, Collision_WithDeletedKey) {
+ // Both hash to 0x4060f732.
+ constexpr std::string_view key1 = "1U2";
+ constexpr std::string_view key2 = "ahj9d";
+
+ ASSERT_EQ(Status::OK, kvs_.Put(key1, 1000));
+ ASSERT_EQ(Status::OK, kvs_.Delete(key1));
+
+ // key2 collides with key1's tombstone.
+ EXPECT_EQ(Status::ALREADY_EXISTS, kvs_.Put(key2, 999));
+
+ int value = 0;
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.Get(key1, &value));
+
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.Get(key2, &value));
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.ValueSize(key2).status());
+ EXPECT_EQ(Status::NOT_FOUND, kvs_.Delete(key2));
+}
+
TEST_F(EmptyInitializedKvs, Iteration_Empty_ByReference) {
for (const KeyValueStore::Item& entry : kvs_) {
FAIL(); // The KVS is empty; this shouldn't execute.
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index e2777dc..2f1c91a 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -121,6 +121,20 @@
return FixedSizeGet(key, reinterpret_cast<std::byte*>(pointer), sizeof(T));
}
+ // Adds a key-value entry to the KVS. If the key was already present, its
+ // value is overwritten.
+ //
+ // In the current implementation, all keys in the KVS must have a unique hash.
+ // If Put is called with a key whose hash matches an existing key, nothing
+ // is added and ALREADY_EXISTS is returned.
+ //
+ // OK: the entry was successfully added or updated
+ // FAILED_PRECONDITION: the KVS is not initialized
+ // RESOURCE_EXHAUSTED: there is not enough space to add the entry
+ // INVALID_ARGUMENT: key is empty or too long or value is too large
+ // ALREADY_EXISTS: the entry could not be added because a different key
+ // with the same hash is already in the KVS
+ //
Status Put(std::string_view key, span<const std::byte> value);
template <typename T,
@@ -278,6 +292,15 @@
key, const_cast<const KeyDescriptor**>(result));
}
+ Status FindExistingKeyDescriptor(std::string_view key,
+ const KeyDescriptor** result) const;
+
+ Status FindExistingKeyDescriptor(std::string_view key,
+ KeyDescriptor** result) {
+ return static_cast<const KeyValueStore&>(*this).FindExistingKeyDescriptor(
+ key, const_cast<const KeyDescriptor**>(result));
+ }
+
Status ReadEntryHeader(Address address, Entry* header) const;
Status ReadEntryKey(Address address, size_t key_length, char* key) const;
