commit a12786b41804e7e65db12f421ee4cc4547b70419
author David Rogers <davidrogers@google.com> Fri Jan 31 16:02:33 2020 -0800
committer CQ Bot Account <commit-bot@chromium.org> Sat Feb 01 02:21:31 2020 +0000
tree a56f6d09c07e781bb4296452441a2a20de655c11
parent 1c9ce1b395fea5c6787c03ccd462c200a8bc138d

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

pw_kvs/key_value_store.cc

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 = &sector;
+      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 = &sector;
+        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