pw_kvs: Use key's current state in RelocateEntry
When moving tombstone entries for deleted keys, RelocateEntry would
cause them to become present again.
Expand key_value_store_map_test.cc and add a test that covers this case
specifically.
Change-Id: I846cb155bffb25198377e04752cace971555d32b
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index b9beed2..5d7ffd8 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -512,7 +512,7 @@
TRY(FindOrRecoverSectorWithSpace(
§or, Entry::size(partition_.alignment_bytes(), key, value)));
DBG("Writing new entry; found sector: %zu", SectorIndex(sector));
- TRY(AppendEntry(sector, &key_descriptor, key, value));
+ TRY(AppendEntry(sector, &key_descriptor, key, value, KeyDescriptor::kValid));
// Only add the entry when we are certain the write succeeded.
key_descriptors_.push_back(key_descriptor);
@@ -552,7 +552,8 @@
// 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(AppendEntry(new_sector, &key_descriptor, key, as_bytes(value)));
+ 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.
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index 7c3dda5..c976db2 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -12,10 +12,13 @@
// License for the specific language governing permissions and limitations under
// the License.
+#include <cstdlib>
#include <random>
+#include <set>
#include <string>
#include <string_view>
#include <unordered_map>
+#include <unordered_set>
#define DUMP_KVS_CONTENTS 0
@@ -27,6 +30,7 @@
#include "pw_kvs/crc16_checksum.h"
#include "pw_kvs/in_memory_fake_flash.h"
#include "pw_kvs/key_value_store.h"
+#include "pw_log/log.h"
#include "pw_span/span.h"
namespace pw::kvs {
@@ -48,6 +52,18 @@
size_t partition_alignment;
};
+template <typename T>
+std::set<T> difference(const std::set<T> lhs, const std::set<T> rhs) {
+ std::set<T> diff;
+ std::set_difference(lhs.begin(),
+ lhs.end(),
+ rhs.begin(),
+ rhs.end(),
+ std::inserter(diff, diff.begin()));
+
+ return diff;
+}
+
template <const TestParameters& kParams>
class KvsTester {
public:
@@ -69,43 +85,9 @@
}
}
- ~KvsTester() {
-#if DUMP_KVS_CONTENTS
- std::cout << "/==============================================\\\n";
- std::cout << "KVS EXPECTED CONTENTS\n";
- std::cout << "------------------------------------------------\n";
- std::cout << "Entries: " << map_.size() << '\n';
- std::cout << "------------------------------------------------\n";
- for (const auto& [key, value] : map_) {
- std::cout << key << " = " << value << '\n';
- }
- std::cout << "\\===============================================/\n";
-#endif // DUMP_KVS_CONTENTS
+ ~KvsTester() { CompareContents(); }
- EXPECT_EQ(map_.size(), kvs_.size());
-
- size_t count = 0;
-
- for (auto& item : kvs_) {
- count += 1;
-
- auto map_entry = map_.find(std::string(item.key()));
- EXPECT_NE(map_entry, map_.end());
-
- if (map_entry != map_.end()) {
- EXPECT_EQ(map_entry->first, item.key());
-
- char value[kMaxValueLength + 1] = {};
- EXPECT_EQ(Status::OK,
- item.Get(as_writable_bytes(span(value))).status());
- EXPECT_EQ(map_entry->second, std::string(value));
- }
- }
-
- EXPECT_EQ(count, map_.size());
- }
-
- void TestRandomValidInputs(int iterations) {
+ void Test_RandomValidInputs(int iterations) {
std::mt19937 random(6006411);
std::uniform_int_distribution<unsigned> distro;
auto random_int = [&] { return distro(random); };
@@ -142,7 +124,7 @@
}
}
- void TestPut() {
+ void Test_Put() {
Put("base_key", "base_value");
for (int i = 0; i < 100; ++i) {
Put("other_key", std::to_string(i));
@@ -152,10 +134,86 @@
}
}
+ void Test_PutAndDelete_RelocateDeletedEntriesShouldStayDeleted() {
+ for (int i = 0; i < 100; ++i) {
+ std::string str = "key_" + std::to_string(i);
+ Put(str, std::string(kMaxValueLength, '?'));
+ Delete(str);
+ }
+ }
+
private:
+ void CompareContents() {
+#if DUMP_KVS_CONTENTS
+ std::set<std::string> map_keys, kvs_keys;
+
+ std::cout << "/==============================================\\\n";
+ std::cout << "KVS EXPECTED CONTENTS\n";
+ std::cout << "------------------------------------------------\n";
+ std::cout << "Entries: " << map_.size() << '\n';
+ std::cout << "------------------------------------------------\n";
+ for (const auto& [key, value] : map_) {
+ std::cout << key << " = " << value << '\n';
+ map_keys.insert(key);
+ }
+ std::cout << "\\===============================================/\n";
+
+ std::cout << "/==============================================\\\n";
+ std::cout << "KVS ACTUAL CONTENTS\n";
+ std::cout << "------------------------------------------------\n";
+ std::cout << "Entries: " << kvs_.size() << '\n';
+ std::cout << "------------------------------------------------\n";
+ for (const auto& item : kvs_) {
+ std::cout << item.key() << " = " << item.ValueSize().size() << " B\n";
+ kvs_keys.insert(std::string(item.key()));
+ }
+ std::cout << "\\===============================================/\n";
+
+ auto missing_from_kvs = difference(map_keys, kvs_keys);
+
+ if (!missing_from_kvs.empty()) {
+ std::cout << "MISSING FROM KVS: " << missing_from_kvs.size() << '\n';
+ for (auto& key : missing_from_kvs) {
+ std::cout << key << '\n';
+ }
+ }
+
+ auto missing_from_map = difference(kvs_keys, map_keys);
+ if (!missing_from_map.empty()) {
+ std::cout << "MISSING FROM MAP: " << missing_from_map.size() << '\n';
+ for (auto& key : missing_from_map) {
+ std::cout << key << '\n';
+ }
+ }
+#endif // DUMP_KVS_CONTENTS
+
+ EXPECT_EQ(map_.size(), kvs_.size());
+
+ size_t count = 0;
+
+ for (auto& item : kvs_) {
+ count += 1;
+
+ auto map_entry = map_.find(std::string(item.key()));
+ if (map_entry == map_.end()) {
+ PW_LOG_CRITICAL("Entry %s missing from map", item.key().data());
+ } else if (map_entry != map_.end()) {
+ EXPECT_EQ(map_entry->first, item.key());
+
+ char value[kMaxValueLength + 1] = {};
+ EXPECT_EQ(Status::OK,
+ item.Get(as_writable_bytes(span(value))).status());
+ EXPECT_EQ(map_entry->second, std::string(value));
+ }
+ }
+
+ EXPECT_EQ(count, map_.size());
+ }
+
// Adds a key to the KVS, if there is room for it.
void Put(const std::string& key, const std::string& value) {
- ASSERT_LE(value.size(), kMaxValueLength);
+ StartOperation("Put", key);
+ EXPECT_LE(value.size(), kMaxValueLength);
Status result = kvs_.Put(key, as_bytes(span(value)));
@@ -163,24 +221,66 @@
EXPECT_EQ(Status::INVALID_ARGUMENT, result);
} else if (map_.size() == KeyValueStore::kMaxEntries) {
EXPECT_EQ(Status::RESOURCE_EXHAUSTED, result);
- } else {
- ASSERT_EQ(Status::OK, result);
+ } else if (result == Status::RESOURCE_EXHAUSTED) {
+ EXPECT_FALSE(map_.empty());
+ } else if (result.ok()) {
map_[key] = value;
+ deleted_.erase(key);
+ } else {
+ PW_LOG_CRITICAL("Put: unhandled result %s", result.str());
+ std::abort();
+ }
+
+ FinishOperation("Put", result, key);
+
+ if (kvs_.size() != map_.size()) {
+ PW_LOG_CRITICAL("Put: size mismatch; expected %zu, actual %zu",
+ map_.size(),
+ kvs_.size());
+ std::abort();
}
}
// Deletes a key from the KVS if it is present.
void Delete(const std::string& key) {
+ StartOperation("Delete", key);
+
Status result = kvs_.Delete(key);
if (key.empty() || key.size() >= KeyValueStore::kMaxKeyLength) {
EXPECT_EQ(Status::INVALID_ARGUMENT, result);
} else if (map_.count(key) == 0) {
EXPECT_EQ(Status::NOT_FOUND, result);
- } else {
- ASSERT_EQ(Status::OK, result);
+ } else if (result.ok()) {
map_.erase(key);
+
+ if (deleted_.count(key) > 0u) {
+ PW_LOG_CRITICAL("Deleted key that was already deleted %s", key.c_str());
+ std::abort();
+ }
+
+ deleted_.insert(key);
+ } else {
+ PW_LOG_CRITICAL("Delete: unhandled result %s", result.str());
+ std::abort();
}
+ FinishOperation("Delete", result, key);
+ }
+
+ void StartOperation(const std::string& operation, const std::string& key) {
+ count_ += 1;
+ PW_LOG_CRITICAL(
+ "[%3u] START %s for '%s'", count_, operation.c_str(), key.c_str());
+ }
+
+ void FinishOperation(const std::string& operation,
+ Status result,
+ const std::string& key) {
+ PW_LOG_CRITICAL("[%3u] FINISH %s <%s> for '%s'",
+ count_,
+ operation.c_str(),
+ result.str(),
+ key.c_str());
}
bool empty() const { return map_.empty(); }
@@ -196,6 +296,8 @@
KeyValueStore kvs_;
std::unordered_map<std::string, std::string> map_;
+ std::unordered_set<std::string> deleted_;
+ unsigned count_ = 0;
};
template <const TestParameters& kParams>
@@ -204,6 +306,9 @@
InMemoryFakeFlash<kParams.sector_size, kParams.sector_count>(
kParams.sector_alignment);
+#define _TEST(fixture, test, ...) \
+ TEST_F(fixture, test) { tester_.Test_##test(__VA_ARGS__); }
+
// Defines a test fixture that runs all tests against a flash with the specified
// parameters.
#define RUN_TESTS_WITH_PARAMETERS(name, ...) \
@@ -215,11 +320,9 @@
}; \
\
/* Run each test defined in the KvsTester class with these parameters. */ \
- \
- TEST_F(name, Put) { tester_.TestPut(); } \
- TEST_F(name, DISABLED_RandomValidInputs) { /* TODO: Get this passing! */ \
- tester_.TestRandomValidInputs(1000); \
- } \
+ _TEST(name, Put); \
+ _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted); \
+ _TEST(name, RandomValidInputs, 1000) \
static_assert(true, "Don't forget a semicolon!")
RUN_TESTS_WITH_PARAMETERS(Basic,
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index bb3d029..749af8d 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -321,7 +321,7 @@
KeyDescriptor* key_descriptor,
std::string_view key,
span<const std::byte> value,
- KeyDescriptor::State new_state = KeyDescriptor::kValid);
+ KeyDescriptor::State new_state);
bool AddressInSector(const SectorDescriptor& sector, Address address) const {
const Address sector_base = SectorBaseAddress(§or);
