pw_kvs: Add part of the garbage collection implementation
Add part of the KVS garbage collection. This gets most of what is
needed, with only the RelocateEntry() method needing work.
Change-Id: Icff1926f43e620d9f48ffb0b94d8c8139836c30a
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 1801dc3..7c83eca 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -202,6 +202,12 @@
return Status::OK;
}
+Status KeyValueStore::RelocateEntry(KeyMapEntry& entry) {
+ // TODO: implement me
+ (void)entry;
+ return Status::UNIMPLEMENTED;
+}
+
// Find either an existing sector with enough space, or an empty sector.
// Maintains the invariant that there is always at least 1 empty sector.
KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorWithSpace(size_t size) {
@@ -243,17 +249,49 @@
return Status::RESOURCE_EXHAUSTED;
}
+KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorToGarbageCollect() {
+ SectorMapEntry* sector_candidate = nullptr;
+ size_t candidate_bytes = 0;
+
+ // Step 1: Try to find a sectors with stale keys and no valid keys (no
+ // relocation needed). If any such sectors are found, use the sector with the
+ // most reclaimable bytes.
+ for (auto& sector : sector_map_) {
+ if ((sector.valid_bytes == 0) &&
+ (RecoverableBytes(sector) > candidate_bytes)) {
+ sector_candidate = §or;
+ candidate_bytes = RecoverableBytes(sector);
+ }
+ }
+
+ // Step 2: If step 1 yields no sectors, just find the sector with the most
+ // reclaimable bytes.
+ if (sector_candidate == nullptr) {
+ for (auto& sector : sector_map_) {
+ if (RecoverableBytes(sector) > candidate_bytes) {
+ sector_candidate = §or;
+ candidate_bytes = RecoverableBytes(sector);
+ }
+ }
+ }
+
+ return sector_candidate;
+}
+
Status KeyValueStore::GarbageCollectOneSector(SectorMapEntry** sector) {
- // TODO: THIS NEEDS WORK
- (void)sector;
+ // Step 1: Find the sector to garbage collect
SectorMapEntry* sector_to_gc = FindSectorToGarbageCollect();
- const Address sector_base = SectorBaseAddress(sector_to_gc);
- const Address sector_end = sector_base + partition_.sector_size_bytes();
+ if (sector_to_gc == nullptr) {
+ return Status::RESOURCE_EXHAUSTED;
+ }
- for (auto entry : entries()) {
- if ((entry.address >= sector_base) && (entry.address < sector_end)) {
- // RelocateEntry(entry);
+ // Step 2: Move any valid entries in the GC sector to other sectors
+ if (sector_to_gc->valid_bytes != 0) {
+ for (auto& entry : entries()) {
+ if (AddressInSector(*sector_to_gc, entry.address)) {
+ TRY(RelocateEntry(entry));
+ }
}
}
@@ -261,12 +299,13 @@
return Status::INTERNAL;
}
- return Status::OK;
-}
+ // Step 3: Reinitialize the sector
+ sector_to_gc->tail_free_bytes = 0;
+ TRY(partition_.Erase(SectorBaseAddress(sector_to_gc), 1));
+ sector_to_gc->tail_free_bytes = partition_.sector_size_bytes();
-KeyValueStore::SectorMapEntry* KeyValueStore::FindSectorToGarbageCollect() {
- // TODO: implement me
- return nullptr;
+ *sector = sector_to_gc;
+ return Status::OK;
}
Status KeyValueStore::AppendEntry(SectorMapEntry* sector,
@@ -321,10 +360,4 @@
return checksum.state();
}
-Status KeyValueStore::RelocateEntry(KeyMapEntry* entry) {
- // TODO: implement me
- (void)entry;
- return Status::UNIMPLEMENTED;
-}
-
} // namespace pw::kvs
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
index 5495141..06a5148 100644
--- a/pw_kvs/public/pw_kvs/flash_memory.h
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -189,15 +189,13 @@
size_t len,
bool* is_erased);
- constexpr uint32_t sector_size_bytes() const {
+ // Overridden by derived classes. The reported sector size is space available
+ // to users of FlashPartition. It accounts for space reserved in the sector
+ // for FlashPartition to store metadata.
+ virtual uint32_t sector_size_bytes() const {
return flash_.sector_size_bytes();
}
- // Overridden by base classes which store metadata at the start of a sector.
- virtual uint32_t sector_available_size_bytes() const {
- return sector_size_bytes();
- }
-
size_t size_bytes() const { return sector_count() * sector_size_bytes(); }
virtual size_t alignment_bytes() const { return flash_.alignment_bytes(); }
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 115bea0..f399629 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -248,6 +248,8 @@
Status WriteEntryForNewKey(std::string_view key, span<const std::byte> value);
+ Status RelocateEntry(KeyMapEntry& entry);
+
SectorMapEntry* FindSectorWithSpace(size_t size);
Status FindOrRecoverSectorWithSpace(SectorMapEntry** sector, size_t size);
@@ -268,10 +270,15 @@
std::string_view key,
span<const std::byte> value) const;
- Status RelocateEntry(KeyMapEntry* entry);
+ bool AddressInSector(const SectorMapEntry& sector, Address address) const {
+ const Address sector_base = SectorBaseAddress(§or);
+ const Address sector_end = sector_base + partition_.sector_size_bytes();
+
+ return ((address >= sector_base) && (address < sector_end));
+ }
bool SectorEmpty(const SectorMapEntry& sector) const {
- return (sector.tail_free_bytes == partition_.sector_available_size_bytes());
+ return (sector.tail_free_bytes == partition_.sector_size_bytes());
}
size_t RecoverableBytes(const SectorMapEntry& sector) {
@@ -279,7 +286,7 @@
sector.tail_free_bytes;
}
- Address SectorBaseAddress(SectorMapEntry* sector) const {
+ Address SectorBaseAddress(const SectorMapEntry* sector) const {
return (sector - sector_map_.data()) * partition_.sector_size_bytes();
}
