pw_kvs: Improvements to FindSectorWithSpace()
Convert FindSectorWithSpace() to return a status
Add support for last new sector tracking
Add SectorIndex() helper
Change-Id: I0b0d21a96815962bc9eebbc96426fd445a53bde0
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index 09747d6..94d4b32 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -51,6 +51,10 @@
// Reset the number of occupied key descriptors; we will fill them later.
key_descriptor_list_size_ = 0;
+ // TODO: init last_new_sector_ to a random sector. Since the on-flash stored
+ // information does not allow recovering the previous last_new_sector_ after
+ // clean start, random is a good second choice.
+
const size_t sector_size_bytes = partition_.sector_size_bytes();
const size_t sector_count = partition_.sector_count();
@@ -405,8 +409,7 @@
span<const byte> value) {
SectorDescriptor* sector;
TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, value)));
- DBG("Writing existing entry; found sector: %d",
- static_cast<int>(sector - sector_map_.data()));
+ DBG("Writing existing entry; found sector: %zu", SectorIndex(sector));
return AppendEntry(sector, key_descriptor, key, value);
}
@@ -428,8 +431,7 @@
SectorDescriptor* sector;
TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, value)));
- DBG("Writing new entry; found sector: %d",
- static_cast<int>(sector - sector_map_.data()));
+ DBG("Writing new entry; found sector: %zu", SectorIndex(sector));
TRY(AppendEntry(sector, &key_descriptor, key, value));
// Only increment bump our size when we are certain the write succeeded.
@@ -468,31 +470,40 @@
}
// Find a new sector for the entry and write it to the new location.
- SectorDescriptor* new_sector =
- FindSectorWithSpace(header.size(), old_sector, true);
- if (new_sector == nullptr) {
- return Status::RESOURCE_EXHAUSTED;
- }
+ SectorDescriptor* new_sector;
+ TRY(FindSectorWithSpace(&new_sector, header.size(), old_sector, true));
return AppendEntry(new_sector, &key_descriptor, key, as_bytes(value));
}
// 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.
-KeyValueStore::SectorDescriptor* KeyValueStore::FindSectorWithSpace(
- size_t size,
- SectorDescriptor* sector_to_skip,
- bool bypass_empty_sector_rule) {
+Status KeyValueStore::FindSectorWithSpace(SectorDescriptor** found_sector,
+ size_t size,
+ SectorDescriptor* sector_to_skip,
+ bool bypass_empty_sector_rule) {
const size_t sector_count = partition_.sector_count();
- // TODO: Ignore last written sector for now and scan from the beginning.
- last_written_sector_ = sector_count - 1;
-
- size_t start = (last_written_sector_ + 1) % sector_count;
+ // 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
+ // the next "find a new empty sector to write to" operation. By using the last
+ // new sector as the start point we will cycle which empty sector is selected
+ // next, spreading the wear across all the empty sectors and get a wear
+ // leveling benefit, rather than putting more wear on the lower number
+ // sectors.
+ //
+ // Locally use the sector index for ease of iterating through the sectors. For
+ // the persistent storage use SectorDescriptor* rather than sector index
+ // because SectorDescriptor* is the standard way to identify a sector.
+ size_t last_new_sector_index_ = SectorIndex(last_new_sector_);
+ size_t start = (last_new_sector_index_ + 1) % sector_count;
SectorDescriptor* first_empty_sector = nullptr;
bool at_least_two_empty_sectors = bypass_empty_sector_rule;
- for (size_t i = start; i != last_written_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.
+ for (size_t i = start; i != last_new_sector_index_;
i = (i + 1) % sector_count) {
DBG("Examining sector %zu", i);
SectorDescriptor& sector = sector_map_[i];
@@ -504,7 +515,8 @@
if (!SectorEmpty(sector) && sector.HasSpace(size)) {
DBG("Partially occupied sector with enough space; done!");
- return §or;
+ *found_sector = §or;
+ return Status::OK;
}
if (SectorEmpty(sector)) {
@@ -516,24 +528,33 @@
}
}
+ // 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).
if (at_least_two_empty_sectors) {
- DBG("Found a usable empty sector; returning the first found (%d)",
- static_cast<int>(first_empty_sector - sector_map_.data()));
- return first_empty_sector;
+ DBG("Found a usable empty sector; returning the first found (%zu)",
+ SectorIndex(first_empty_sector));
+ last_new_sector_ = first_empty_sector;
+ *found_sector = first_empty_sector;
+ return Status::OK;
}
- return nullptr;
+
+ // No sector was found.
+ *found_sector = nullptr;
+ return Status::RESOURCE_EXHAUSTED;
}
Status KeyValueStore::FindOrRecoverSectorWithSpace(SectorDescriptor** sector,
size_t size) {
- *sector = FindSectorWithSpace(size);
- if (*sector != nullptr) {
- return Status::OK;
+ Status result = FindSectorWithSpace(sector, size);
+ if (result.ok()) {
+ return result;
}
if (options_.partial_gc_on_write) {
return GarbageCollectOneSector(sector);
}
- return Status::RESOURCE_EXHAUSTED;
+ return result;
}
KeyValueStore::SectorDescriptor* KeyValueStore::FindSectorToGarbageCollect() {
@@ -621,8 +642,6 @@
&partition_, address, entry_header_format_.checksum));
}
- // TODO: UPDATE last_written_sector_ appropriately
-
key_descriptor->address = address;
key_descriptor->key_version = header.key_version();
sector->valid_bytes += written;
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 104ea41..f38592d 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -85,7 +85,7 @@
key_descriptor_list_{},
key_descriptor_list_size_(0),
sector_map_{},
- last_written_sector_(0),
+ last_new_sector_(sector_map_.data()),
working_buffer_{} {}
Status Init();
@@ -267,10 +267,10 @@
Status RelocateEntry(KeyDescriptor& key_descriptor);
- SectorDescriptor* FindSectorWithSpace(
- size_t size,
- SectorDescriptor* sector_to_skip = nullptr,
- bool bypass_empty_sector_rule = false);
+ Status FindSectorWithSpace(SectorDescriptor** found_sector,
+ size_t size,
+ SectorDescriptor* sector_to_skip = nullptr,
+ bool bypass_empty_sector_rule = false);
Status FindOrRecoverSectorWithSpace(SectorDescriptor** sector, size_t size);
@@ -303,8 +303,13 @@
sector.tail_free_bytes;
}
+ size_t SectorIndex(const SectorDescriptor* sector) const {
+ // TODO: perhaps add assert that the index is valid.
+ return (sector - sector_map_.data());
+ }
+
Address SectorBaseAddress(const SectorDescriptor* sector) const {
- return (sector - sector_map_.data()) * partition_.sector_size_bytes();
+ return SectorIndex(sector) * partition_.sector_size_bytes();
}
SectorDescriptor* SectorFromAddress(Address address) {
@@ -338,7 +343,17 @@
// This is dense, so sector_id == indexof(SectorDescriptor) in sector_map
std::array<SectorDescriptor, kUsableSectors> sector_map_;
- size_t last_written_sector_;
+
+ // The last sector that was selected as the "new empty sector" to write to.
+ // This last new sector is used as the starting point for the next "find a new
+ // empty sector to write to" operation. By using the last new sector as the
+ // start point we will cycle which empty sector is selected next, spreading
+ // the wear across all the empty sectors, rather than putting more wear on the
+ // lower number sectors.
+ //
+ // Use SectorDescriptor* for the persistent storage rather than sector index
+ // because SectorDescriptor* is the standard way to identify a sector.
+ SectorDescriptor* last_new_sector_;
bool initialized_ = false;
