blob: d2f4565055d82d28e5713c921c3e6489857cb61b [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.
#pragma once
#include <climits>
#include <cstddef>
#include <cstdint>
#include <span>
#include "pw_containers/vector.h"
#include "pw_kvs/flash_memory.h"
namespace pw::kvs::internal {
// Tracks the available and used space in each sector used by the KVS.
class SectorDescriptor {
// The number of bytes available to be written in this sector. It the sector
// is marked as corrupt, no bytes are available.
size_t writable_bytes() const {
return (tail_free_bytes_ == kCorruptSector) ? 0 : tail_free_bytes_;
void set_writable_bytes(uint16_t writable_bytes) {
tail_free_bytes_ = writable_bytes;
void mark_corrupt() { tail_free_bytes_ = kCorruptSector; }
bool corrupt() const { return tail_free_bytes_ == kCorruptSector; }
// The number of bytes of valid data in this sector.
size_t valid_bytes() const { return valid_bytes_; }
// Adds valid bytes without updating the writable bytes.
void AddValidBytes(uint16_t bytes) { valid_bytes_ += bytes; }
// Removes valid bytes without updating the writable bytes.
void RemoveValidBytes(uint16_t bytes) {
if (bytes > valid_bytes()) {
// TODO: use a DCHECK instead -- this is a programming error
valid_bytes_ = 0;
} else {
valid_bytes_ -= bytes;
// Removes writable bytes without updating the valid bytes.
void RemoveWritableBytes(uint16_t bytes) {
if (bytes > writable_bytes()) {
// TODO: use a DCHECK instead -- this is a programming error
tail_free_bytes_ = 0;
} else {
tail_free_bytes_ -= bytes;
bool HasSpace(size_t required_space) const {
return writable_bytes() >= required_space;
bool Empty(size_t sector_size_bytes) const {
return writable_bytes() == sector_size_bytes;
// Returns the number of bytes that would be recovered if this sector is
// garbage collected.
size_t RecoverableBytes(size_t sector_size_bytes) const {
return sector_size_bytes - valid_bytes_ - writable_bytes();
static constexpr size_t max_sector_size() { return kMaxSectorSize; }
friend class Sectors;
static constexpr uint16_t kCorruptSector = UINT16_MAX;
static constexpr size_t kMaxSectorSize = UINT16_MAX - 1;
explicit constexpr SectorDescriptor(uint16_t sector_size_bytes)
: tail_free_bytes_(sector_size_bytes), valid_bytes_(0) {}
uint16_t tail_free_bytes_; // writable bytes at the end of the sector
uint16_t valid_bytes_; // sum of sizes of valid entries
// Represents a list of sectors usable by the KVS.
class Sectors {
using Address = FlashPartition::Address;
constexpr Sectors(Vector<SectorDescriptor>& sectors,
FlashPartition& partition,
const SectorDescriptor** temp_sectors_to_skip)
: descriptors_(sectors),
temp_sectors_to_skip_(temp_sectors_to_skip) {}
// Resets the Sectors list. Must be called before using the object.
void Reset() {
last_new_ = descriptors_.begin();
// 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() const { return last_new_; }
// Sets the last new sector from the provided address.
void set_last_new_sector(Address address) {
last_new_ = &FromAddress(address);
// Checks if an address is in the particular sector.
bool AddressInSector(const SectorDescriptor& sector, Address address) const {
const Address sector_base = BaseAddress(sector);
const Address sector_end = sector_base + partition_.sector_size_bytes();
return ((address >= sector_base) && (address < sector_end));
// Returns the first address in the provided sector.
Address BaseAddress(const SectorDescriptor& sector) const {
return Index(sector) * partition_.sector_size_bytes();
SectorDescriptor& FromAddress(Address address) const {
// TODO: Add boundary checking once asserts are supported.
// DCHECK_LT(index, sector_map_size_);`
return descriptors_[address / partition_.sector_size_bytes()];
Address NextWritableAddress(const SectorDescriptor& sector) const {
return BaseAddress(sector) + partition_.sector_size_bytes() -
// Finds 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. Addresses in reserved_addresses are avoided.
Status FindSpace(SectorDescriptor** found_sector,
size_t size,
std::span<const Address> reserved_addresses) {
return Find(kAppendEntry, found_sector, size, {}, reserved_addresses);
// Same as FindSpace, except that the 1 empty sector invariant is ignored.
// Both addresses_to_skip and reserved_addresses are avoided.
Status FindSpaceDuringGarbageCollection(
SectorDescriptor** found_sector,
size_t size,
std::span<const Address> addresses_to_skip,
std::span<const Address> reserved_addresses) {
return Find(kGarbageCollect,
// Finds a sector that is ready to be garbage collected. Returns nullptr if no
// sectors can / need to be garbage collected.
SectorDescriptor* FindSectorToGarbageCollect(
std::span<const Address> addresses_to_avoid) const;
// The number of sectors in use.
size_t size() const { return descriptors_.size(); }
// The maximum number of sectors supported.
size_t max_size() const { return descriptors_.max_size(); }
// Returns the index of the provided sector. Used for logging.
unsigned Index(const SectorDescriptor& sector) const {
return &sector - descriptors_.begin();
unsigned Index(const SectorDescriptor* s) const { return Index(*s); }
unsigned Index(Address address) const { return Index(FromAddress(address)); }
// Iterators for iterating over all sectors.
using iterator = Vector<SectorDescriptor>::iterator;
using const_iterator = Vector<SectorDescriptor>::const_iterator;
iterator begin() { return descriptors_.begin(); }
const_iterator begin() const { return descriptors_.begin(); }
iterator end() { return descriptors_.end(); }
const_iterator end() const { return descriptors_.end(); }
enum FindMode { kAppendEntry, kGarbageCollect };
Status Find(FindMode find_mode,
SectorDescriptor** found_sector,
size_t size,
std::span<const Address> addresses_to_skip,
std::span<const Address> reserved_addresses);
SectorDescriptor& WearLeveledSectorFromIndex(size_t idx) const;
Vector<SectorDescriptor>& descriptors_;
FlashPartition& partition_;
SectorDescriptor* last_new_;
// Temp buffer with space for redundancy * 2 - 1 sector pointers. This list is
// used to track sectors that should be excluded from Find functions.
const SectorDescriptor** const temp_sectors_to_skip_;
} // namespace pw::kvs::internal