FIX bad merge: 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: Ib7e43aa8955a292b025cdff712e4af1745229a69
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 45bf2e4..faf7944 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -629,11 +629,11 @@
// an immediate extra relocation).
SectorDescriptor* new_sector;
- // TODO: For redundancy work, replace old_sector_const with a span of sectors
- // to avoid.
+ // TODO: For redundancy work, replace old_sector_const with a vector of
+ // sectors to avoid.
const SectorDescriptor* old_sector_const = old_sector;
TRY(FindSectorWithSpace(
- &new_sector, entry.size(), span(&old_sector_const, 1), true, false));
+ &new_sector, entry.size(), kGarbageCollect, span(&old_sector_const, 1)));
TRY(AppendEntry(
new_sector, &key_descriptor, key, value, key_descriptor.state()));
@@ -645,16 +645,15 @@
// 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. Optionally skip sectors
-// that have reclaimable bytes.
+// least 1 empty sector except during GC. On GC, skip sectors that have
+// reclaimable bytes.
Status KeyValueStore::FindSectorWithSpace(
SectorDescriptor** found_sector,
size_t size,
- span<const SectorDescriptor*> sectors_to_skip,
- bool bypass_empty_sector_rule,
- bool allow_reclaimable) {
+ FindSectorMode find_mode,
+ span<const SectorDescriptor*> sectors_to_skip) {
SectorDescriptor* first_empty_sector = nullptr;
- bool at_least_two_empty_sectors = bypass_empty_sector_rule;
+ bool at_least_two_empty_sectors = (find_mode == kGarbageCollect);
DBG("Find sector with %zu bytes available, starting with sector %u",
size,
@@ -662,9 +661,6 @@
for (auto& skip_sector : sectors_to_skip) {
DBG(" Skip sector %u", SectorIndex(skip_sector));
}
- if (bypass_empty_sector_rule) {
- DBG(" Bypassing 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
@@ -678,14 +674,13 @@
// 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 1 is sector that already has valid data. During GC only select a
+ // sector that has no reclaimable bytes. Immediately use the first matching
+ // sector 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.
+ // Tier 2 is find sectors that are empty/erased. While scanning for a partial
+ // sector, keep track of the first empty sector and if a second empty sector
+ // was seen. If during GC then count the second empty sector as always seen.
for (size_t j = 0; j < sectors_.size(); j++) {
sector += 1;
if (sector == sectors_.end()) {
@@ -699,7 +694,7 @@
const size_t sector_size_bytes = partition_.sector_size_bytes();
if (!sector->Empty(sector_size_bytes) && sector->HasSpace(size) &&
- (allow_reclaimable ||
+ ((find_mode == kAppendEntry) ||
(sector->RecoverableBytes(sector_size_bytes) == 0))) {
*found_sector = sector;
return Status::OK;
@@ -716,8 +711,7 @@
// If the scan for a partial sector does not find a suitable sector, use the
// first empty sector that was found. Normally it is required to keep 1 empty
- // sector after the sector found here, but that rule can be bypassed in
- // special circumstances (such as during garbage collection).
+ // sector after the sector found here, but that rule does not apply during GC.
if (at_least_two_empty_sectors) {
DBG(" Found a usable empty sector; returning the first found (%u)",
SectorIndex(first_empty_sector));
@@ -734,11 +728,11 @@
Status KeyValueStore::FindOrRecoverSectorWithSpace(SectorDescriptor** sector,
size_t size) {
- Status result = FindSectorWithSpace(sector, size);
+ Status result = FindSectorWithSpace(sector, size, kAppendEntry);
if (result == Status::RESOURCE_EXHAUSTED && options_.partial_gc_on_write) {
// Garbage collect and then try again to find the best sector.
TRY(GarbageCollectPartial());
- return FindSectorWithSpace(sector, size);
+ return FindSectorWithSpace(sector, size, kAppendEntry);
}
return result;
}
@@ -782,7 +776,6 @@
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
@@ -799,7 +792,6 @@
}
DBG("Garbage Collect all complete");
- LogSectors();
return Status::OK;
}
@@ -808,7 +800,6 @@
// Step 1: Find the sector to garbage collect
SectorDescriptor* sector_to_gc = FindSectorToGarbageCollect();
- LogSectors();
if (sector_to_gc == nullptr) {
// Nothing to GC, all done.
@@ -816,7 +807,6 @@
}
TRY(GarbageCollectSector(sector_to_gc));
- LogSectors();
return Status::OK;
}
diff --git a/pw_kvs/key_value_store_map_test.cc b/pw_kvs/key_value_store_map_test.cc
index f599cbb..99b76d2 100644
--- a/pw_kvs/key_value_store_map_test.cc
+++ b/pw_kvs/key_value_store_map_test.cc
@@ -56,6 +56,13 @@
size_t partition_alignment;
};
+enum Options {
+ kNone,
+ kReinit,
+ kReinitWithFullGC,
+ kReinitWithPartialGC,
+};
+
template <typename T>
std::set<T> difference(const std::set<T> lhs, const std::set<T> rhs) {
std::set<T> diff;
@@ -93,9 +100,7 @@
void Test_RandomValidInputs(int iterations,
uint_fast32_t seed,
- bool reinit = false,
- bool full_gc = false,
- bool partial_gc = false) {
+ Options options) {
std::mt19937 random(seed);
std::uniform_int_distribution<unsigned> distro;
auto random_int = [&] { return distro(random); };
@@ -109,7 +114,7 @@
};
for (int i = 0; i < iterations; ++i) {
- if (reinit && random_int() % 10 == 0) {
+ if (options != kNone && random_int() % 10 == 0) {
Init();
}
@@ -135,9 +140,9 @@
Put(key, random_string(random_int() % kMaxValueLength));
}
- if (full_gc && random_int() % 25 == 0) {
+ if (options == kReinitWithFullGC && random_int() % 250 == 0) {
GCFull();
- } else if (partial_gc && random_int() % 25 == 0) {
+ } else if (options == kReinitWithPartialGC && random_int() % 40 == 0) {
GCPartial();
}
}
@@ -366,47 +371,40 @@
// 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, 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); \
+#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, kNone); \
+ _TEST_VARIANT(name, RandomValidInputs, 1WithReinit, 1000, 6006411, kReinit); \
+ _TEST_VARIANT(name, RandomValidInputs, 2, 100, 123, kNone); \
+ _TEST_VARIANT(name, RandomValidInputs, 2WithReinit, 100, 123, kReinit); \
+ _TEST_VARIANT(name, \
+ RandomValidInputs, \
+ 1ReinitFullGC, \
+ 1000, \
+ 6006411, \
+ kReinitWithFullGC); \
+ _TEST_VARIANT( \
+ name, RandomValidInputs, 2ReinitFullGC, 1000, 123, kReinitWithFullGC); \
+ _TEST_VARIANT(name, \
+ RandomValidInputs, \
+ 1ReinitPartialGC, \
+ 100, \
+ 6006411, \
+ kReinitWithPartialGC); \
+ _TEST_VARIANT(name, \
+ RandomValidInputs, \
+ 2ReinitPartialGC, \
+ 200, \
+ 123, \
+ kReinitWithPartialGC); \
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 5c7d384..e605754 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -313,12 +313,13 @@
Status RelocateEntry(KeyDescriptor& key_descriptor);
+ enum FindSectorMode { kAppendEntry, kGarbageCollect };
+
Status FindSectorWithSpace(SectorDescriptor** found_sector,
size_t size,
+ FindSectorMode find_mode,
span<const SectorDescriptor*> sector_to_skip =
- span<const SectorDescriptor*>(),
- bool bypass_empty_sector_rule = false,
- bool allow_reclaimable = true);
+ span<const SectorDescriptor*>());
Status FindOrRecoverSectorWithSpace(SectorDescriptor** sector, size_t size);
