pw_kvs: Add public garbage collection methods and prep for redundancy
- Add public methods to do full garbage collect and partial garbage
collect.
- Do clean up related to finding sector to write entry to that is in
preparation for adding redundancy support.
Change-Id: I42686e60ff53a7372303cf61895a4a937dc2bfb9
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 0282380..415544f 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -607,9 +607,19 @@
SectorDescriptor* old_sector = SectorFromKey(key_descriptor);
- // Find a new sector for the entry and write it to the new location.
+ // Find a new sector for the entry and write it to the new location. For
+ // relocation the find should not not be a sector already containing the key
+ // but can be the always empty sector, since this is part of the GC process
+ // that will result in a new empty sector. Also find a sector that does not
+ // have reclaimable space (mostly for the full GC, where that would result in
+ // an immediate extra relocation).
SectorDescriptor* new_sector;
- TRY(FindSectorWithSpace(&new_sector, entry.size(), old_sector, true));
+
+ // TODO: For redundancy work, replace old_sector_const with a span of sectors
+ // to avoid.
+ const SectorDescriptor* old_sector_const = old_sector;
+ TRY(FindSectorWithSpace(
+ &new_sector, entry.size(), span(&old_sector_const, 1), true, false));
TRY(AppendEntry(
new_sector, &key_descriptor, key, value, key_descriptor.state()));
@@ -621,20 +631,22 @@
// 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.
+// least 1 empty sector unless set to bypass the rule. Optionally skip sectors
+// that have reclaimable bytes.
Status KeyValueStore::FindSectorWithSpace(
SectorDescriptor** found_sector,
size_t size,
- const SectorDescriptor* sector_to_skip,
- bool bypass_empty_sector_rule) {
+ span<const SectorDescriptor*> sectors_to_skip,
+ bool bypass_empty_sector_rule,
+ bool allow_reclaimable) {
SectorDescriptor* first_empty_sector = nullptr;
bool at_least_two_empty_sectors = bypass_empty_sector_rule;
DBG("Find sector with %zu bytes available, starting with sector %u",
size,
SectorIndex(last_new_sector_));
- if (sector_to_skip != nullptr) {
- DBG(" Skip sector %u", SectorIndex(sector_to_skip));
+ for (auto& skip_sector : sectors_to_skip) {
+ DBG(" Skip sector %u", SectorIndex(skip_sector));
}
if (bypass_empty_sector_rule) {
DBG(" Bypassing empty sector rule");
@@ -649,21 +661,32 @@
// sectors.
SectorDescriptor* sector = last_new_sector_;
- // Look for a partial sector to use with enough space. Immediately use the
- // first one of those that is found. While scanning for a partial sector, keep
- // track of the first empty sector and if a second sector was seen.
+ // Look for a sector to use with enough space. The search uses a 2 priority
+ // tier process.
+ //
+ // Tier 1 is sector that already has valid data. Optionally also only select
+ // sector that has no reclaimable bytes. Immediately use the first one of
+ // those that is found.
+ //
+ // Tier 2 is sectors that are empty. While scanning for a partial sector, keep
+ // track of the first empty sector and if a second empty sector was seen. If
+ // bypass_empty_sector_rule is true then count the second empty sector as
+ // always seen.
for (size_t j = 0; j < sectors_.size(); j++) {
sector += 1;
if (sector == sectors_.end()) {
sector = sectors_.begin();
}
- if (sector_to_skip == sector) {
+ if (std::find(sectors_to_skip.begin(), sectors_to_skip.end(), sector) !=
+ sectors_to_skip.end()) {
continue;
}
const size_t sector_size_bytes = partition_.sector_size_bytes();
- if (!sector->Empty(sector_size_bytes) && sector->HasSpace(size)) {
+ if (!sector->Empty(sector_size_bytes) && sector->HasSpace(size) &&
+ (allow_reclaimable ||
+ (sector->RecoverableBytes(sector_size_bytes) == 0))) {
*found_sector = sector;
return Status::OK;
}
@@ -700,7 +723,7 @@
Status result = FindSectorWithSpace(sector, size);
if (result == Status::RESOURCE_EXHAUSTED && options_.partial_gc_on_write) {
// Garbage collect and then try again to find the best sector.
- TRY(GarbageCollectOneSector());
+ TRY(GarbageCollectPartial());
return FindSectorWithSpace(sector, size);
}
return result;
@@ -743,7 +766,30 @@
return sector_candidate;
}
-Status KeyValueStore::GarbageCollectOneSector() {
+Status KeyValueStore::GarbageCollectFull() {
+ DBG("Garbage Collect all sectors");
+ LogSectors();
+ SectorDescriptor* sector = last_new_sector_;
+
+ // TODO: look in to making an iterator method for cycling through sectors
+ // starting from last_new_sector_.
+ for (size_t j = 0; j < sectors_.size(); j++) {
+ sector += 1;
+ if (sector == sectors_.end()) {
+ sector = sectors_.begin();
+ }
+
+ if (sector->RecoverableBytes(partition_.sector_size_bytes()) > 0) {
+ TRY(GarbageCollectSector(sector));
+ }
+ }
+
+ DBG("Garbage Collect all complete");
+ LogSectors();
+ return Status::OK;
+}
+
+Status KeyValueStore::GarbageCollectPartial() {
DBG("Garbage Collect a single sector");
// Step 1: Find the sector to garbage collect
@@ -751,10 +797,17 @@
LogSectors();
if (sector_to_gc == nullptr) {
- return Status::RESOURCE_EXHAUSTED;
+ // Nothing to GC, all done.
+ return Status::OK;
}
- // Step 2: Move any valid entries in the GC sector to other sectors
+ TRY(GarbageCollectSector(sector_to_gc));
+ LogSectors();
+ return Status::OK;
+}
+
+Status KeyValueStore::GarbageCollectSector(SectorDescriptor* sector_to_gc) {
+ // Step 1: Move any valid entries in the GC sector to other sectors
if (sector_to_gc->valid_bytes() != 0) {
for (auto& descriptor : key_descriptors_) {
if (AddressInSector(*sector_to_gc, descriptor.address())) {
@@ -771,13 +824,12 @@
return Status::INTERNAL;
}
- // Step 3: Reinitialize the sector
+ // Step 2: Reinitialize the sector
sector_to_gc->set_writable_bytes(0);
TRY(partition_.Erase(SectorBaseAddress(sector_to_gc), 1));
sector_to_gc->set_writable_bytes(partition_.sector_size_bytes());
- DBG(" Garbage Collect complete");
- LogSectors();
+ DBG(" Garbage Collect sector %u complete", SectorIndex(sector_to_gc));
return Status::OK;
}
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index a65ed2c..f599cbb 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -93,7 +93,9 @@
void Test_RandomValidInputs(int iterations,
uint_fast32_t seed,
- bool reinit = false) {
+ bool reinit = false,
+ bool full_gc = false,
+ bool partial_gc = false) {
std::mt19937 random(seed);
std::uniform_int_distribution<unsigned> distro;
auto random_int = [&] { return distro(random); };
@@ -132,6 +134,12 @@
Put(key, random_string(random_int() % kMaxValueLength));
}
+
+ if (full_gc && random_int() % 25 == 0) {
+ GCFull();
+ } else if (partial_gc && random_int() % 25 == 0) {
+ GCPartial();
+ }
}
}
@@ -288,6 +296,29 @@
FinishOperation("Init", status, "");
}
+ void GCFull() {
+ StartOperation("GCFull", "");
+ Status status = kvs_.GarbageCollectFull();
+ EXPECT_EQ(Status::OK, status);
+ KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
+ EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
+ FinishOperation("GCFull", status, "");
+ }
+
+ void GCPartial() {
+ StartOperation("GCPartial", "");
+ KeyValueStore::StorageStats pre_stats = kvs_.GetStorageStats();
+ Status status = kvs_.GarbageCollectPartial();
+ EXPECT_EQ(Status::OK, status);
+ KeyValueStore::StorageStats post_stats = kvs_.GetStorageStats();
+ if (pre_stats.reclaimable_bytes != 0) {
+ EXPECT_LT(post_stats.reclaimable_bytes, pre_stats.reclaimable_bytes);
+ } else {
+ EXPECT_EQ(post_stats.reclaimable_bytes, 0U);
+ }
+ FinishOperation("GCPartial", status, "");
+ }
+
void StartOperation(const std::string& operation, const std::string& key) {
count_ += 1;
PW_LOG_DEBUG(
@@ -335,21 +366,47 @@
// Defines a test fixture that runs all tests against a flash with the specified
// parameters.
-#define RUN_TESTS_WITH_PARAMETERS(name, ...) \
- class name : public ::testing::Test { \
- protected: \
- static constexpr TestParameters kParams = {__VA_ARGS__}; \
- \
- KvsTester<kParams> tester_; \
- }; \
- \
- /* Run each test defined in the KvsTester class with these parameters. */ \
- _TEST(name, Put); \
- _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted); \
- _TEST_VARIANT(name, RandomValidInputs, 1, 1000, 6006411, false); \
- _TEST_VARIANT(name, RandomValidInputs, 1WithReinit, 1000, 6006411, true); \
- _TEST_VARIANT(name, RandomValidInputs, 2, 1000, 123, false); \
- _TEST_VARIANT(name, RandomValidInputs, 2WithReinit, 1000, 123, true); \
+#define RUN_TESTS_WITH_PARAMETERS(name, ...) \
+ class name : public ::testing::Test { \
+ protected: \
+ static constexpr TestParameters kParams = {__VA_ARGS__}; \
+ \
+ KvsTester<kParams> tester_; \
+ }; \
+ \
+ /* Run each test defined in the KvsTester class with these parameters. */ \
+ _TEST(name, Put); \
+ _TEST(name, PutAndDelete_RelocateDeletedEntriesShouldStayDeleted); \
+ _TEST_VARIANT(name, RandomValidInputs, 1, 100, 6006411, false); \
+ _TEST_VARIANT(name, RandomValidInputs, 1WithReinit, 100, 6006411, true); \
+ _TEST_VARIANT(name, RandomValidInputs, 2, 100, 123, false); \
+ _TEST_VARIANT(name, RandomValidInputs, 2WithReinit, 100, 123, true); \
+ _TEST_VARIANT(name, RandomValidInputs, 1FullGC, 100, 6006411, false, true); \
+ _TEST_VARIANT( \
+ name, RandomValidInputs, 1WithReinitFullGC, 100, 6006411, true, true); \
+ _TEST_VARIANT(name, RandomValidInputs, 2FullGC, 100, 123, false); \
+ _TEST_VARIANT( \
+ name, RandomValidInputs, 2WithReinitFullGC, 100, 123, true, true); \
+ _TEST_VARIANT( \
+ name, RandomValidInputs, 1PartialGC, 100, 6006411, false, false, true); \
+ _TEST_VARIANT(name, \
+ RandomValidInputs, \
+ 1WithReinitPartialGC, \
+ 1000, \
+ 6006411, \
+ true, \
+ false, \
+ true); \
+ _TEST_VARIANT( \
+ name, RandomValidInputs, 2PartialGC, 100, 123, false, false, true); \
+ _TEST_VARIANT(name, \
+ RandomValidInputs, \
+ 2WithReinitFullPartialGC, \
+ 1000, \
+ 123, \
+ true, \
+ true, \
+ true); \
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 b2b114f..5c7d384 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -151,6 +151,13 @@
//
StatusWithSize ValueSize(std::string_view key) const;
+ // Perform garbage collection of all reclaimable space in the KVS.
+ Status GarbageCollectFull();
+
+ // Perform garbage collection of part of the KVS, typically a single sector or
+ // similar unit that makes sense for the KVS implementation.
+ Status GarbageCollectPartial();
+
void LogDebugInfo();
// Classes and functions to support STL-style iteration.
@@ -308,12 +315,14 @@
Status FindSectorWithSpace(SectorDescriptor** found_sector,
size_t size,
- const SectorDescriptor* sector_to_skip = nullptr,
- bool bypass_empty_sector_rule = false);
+ span<const SectorDescriptor*> sector_to_skip =
+ span<const SectorDescriptor*>(),
+ bool bypass_empty_sector_rule = false,
+ bool allow_reclaimable = true);
Status FindOrRecoverSectorWithSpace(SectorDescriptor** sector, size_t size);
- Status GarbageCollectOneSector();
+ Status GarbageCollectSector(SectorDescriptor* sector_to_gc);
SectorDescriptor* FindSectorToGarbageCollect();