blob: 69af81ca7704b6ba6f26d8f3798b2d50779834d8 [file] [log] [blame]
// Copyright 2020 The Pigweed Authors
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
#include "pw_kvs/internal/sectors.h"
#include "pw_log/log.h"
namespace pw::kvs::internal {
namespace {
// Returns true if the container conatins the value.
// TODO: At some point move this to pw_containers, along with adding tests.
template <typename Container, typename T>
bool Contains(const Container& container, const T& value) {
return std::find(std::begin(container), std::end(container), value) !=
} // namespace
Status Sectors::Find(FindMode find_mode,
SectorDescriptor** found_sector,
size_t size,
span<const Address> addresses_to_skip,
span<const Address> reserved_addresses) {
SectorDescriptor* first_empty_sector = nullptr;
bool at_least_two_empty_sectors = (find_mode == kGarbageCollect);
// Used for the GC reclaimable bytes check
SectorDescriptor* non_empty_least_reclaimable_sector = nullptr;
const size_t sector_size_bytes = partition_.sector_size_bytes();
// Build a list of sectors to avoid.
// This is overly strict. reserved_addresses is populated when there are
// sectors reserved for a new entry. It is safe to garbage collect into
// these sectors, as long as there remains room for the pending entry. These
// reserved sectors could also be garbage collected if they have recoverable
// space. For simplicitly, avoid both the relocating key's redundant entries
// (addresses_to_skip) and the sectors reserved for pending writes
// (reserved_addresses).
// TODO(hepler): Look into improving garbage collection.
size_t sectors_to_skip = 0;
for (Address address : addresses_to_skip) {
temp_sectors_to_skip_[sectors_to_skip++] = &FromAddress(address);
for (Address address : reserved_addresses) {
temp_sectors_to_skip_[sectors_to_skip++] = &FromAddress(address);
DBG("Find sector with %zu bytes available, starting with sector %u, %s",
(find_mode == kAppendEntry) ? "Append" : "GC");
for (size_t i = 0; i < sectors_to_skip; ++i) {
DBG(" Skip sector %u", Index(temp_sectors_to_skip_[i]));
// last_new_ 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.
SectorDescriptor* sector = last_new_;
// Look for a sector to use with enough space. The search uses a 3 priority
// tier process.
// 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 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.
// Tier 3 is during garbage collection, find sectors with enough space that
// are not empty but have recoverable bytes. Pick the sector with the least
// recoverable bytes to minimize the likelyhood of this sector needing to be
// garbage collected soon.
for (size_t j = 0; j < descriptors_.size(); j++) {
sector += 1;
if (sector == descriptors_.end()) {
sector = descriptors_.begin();
// Skip sectors in the skip list.
if (Contains(span(temp_sectors_to_skip_, sectors_to_skip), sector)) {
if (!sector->Empty(sector_size_bytes) && sector->HasSpace(size)) {
if ((find_mode == kAppendEntry) ||
(sector->RecoverableBytes(sector_size_bytes) == 0)) {
*found_sector = sector;
return Status::OK;
} else {
if ((non_empty_least_reclaimable_sector == nullptr) ||
sector_size_bytes) <
sector->RecoverableBytes(sector_size_bytes))) {
non_empty_least_reclaimable_sector = sector;
if (sector->Empty(sector_size_bytes)) {
if (first_empty_sector == nullptr) {
first_empty_sector = sector;
} else {
at_least_two_empty_sectors = true;
// Tier 2 check: 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 does not
// apply during GC.
if (first_empty_sector != nullptr && at_least_two_empty_sectors) {
DBG(" Found a usable empty sector; returning the first found (%u)",
last_new_ = first_empty_sector;
*found_sector = first_empty_sector;
return Status::OK;
// Tier 3 check: If we got this far, use the sector with least recoverable
// bytes
if (non_empty_least_reclaimable_sector != nullptr) {
*found_sector = non_empty_least_reclaimable_sector;
DBG(" Found a usable sector %u, with %zu B recoverable, in GC",
return Status::OK;
// No sector was found.
DBG(" Unable to find a usable sector");
*found_sector = nullptr;
// TODO: Consider breaking this function into smaller sub-chunks.
SectorDescriptor* Sectors::FindSectorToGarbageCollect(
span<const Address> reserved_addresses) const {
const size_t sector_size_bytes = partition_.sector_size_bytes();
SectorDescriptor* sector_candidate = nullptr;
size_t candidate_bytes = 0;
// Build a vector of sectors to avoid.
for (size_t i = 0; i < reserved_addresses.size(); ++i) {
temp_sectors_to_skip_[i] = &FromAddress(reserved_addresses[i]);
DBG(" Skip sector %u", Index(reserved_addresses[i]));
const span sectors_to_skip(temp_sectors_to_skip_, reserved_addresses.size());
// 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 : descriptors_) {
if ((sector.valid_bytes() == 0) &&
(sector.RecoverableBytes(sector_size_bytes) > candidate_bytes) &&
!Contains(sectors_to_skip, &sector)) {
sector_candidate = &sector;
candidate_bytes = sector.RecoverableBytes(sector_size_bytes);
// Step 2: If step 1 yields no sectors, just find the sector with the most
// reclaimable bytes but no addresses to avoid.
if (sector_candidate == nullptr) {
for (auto& sector : descriptors_) {
if ((sector.RecoverableBytes(sector_size_bytes) > candidate_bytes) &&
!Contains(sectors_to_skip, &sector)) {
sector_candidate = &sector;
candidate_bytes = sector.RecoverableBytes(sector_size_bytes);
// Step 3: If no sectors with reclaimable bytes, select the sector with the
// most free bytes. This at least will allow entries of existing keys to get
// spread to other sectors, including sectors that already have copies of the
// current key being written.
if (sector_candidate == nullptr) {
for (auto& sector : descriptors_) {
if ((sector.valid_bytes() > candidate_bytes) &&
!Contains(sectors_to_skip, &sector)) {
sector_candidate = &sector;
candidate_bytes = sector.valid_bytes();
DBG(" Doing GC on sector with no reclaimable bytes!");
if (sector_candidate != nullptr) {
DBG("Found sector %u to Garbage Collect, %zu recoverable bytes",
} else {
DBG("Unable to find sector to garbage collect!");
return sector_candidate;
} // namespace pw::kvs::internal