diff --git a/pw_kvs/flash.cc b/pw_kvs/flash.cc
new file mode 100644
index 0000000..bcc695f
--- /dev/null
+++ b/pw_kvs/flash.cc
@@ -0,0 +1,63 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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/util/flash.h"
+
+#include "pw_kvs/config.h"
+
+namespace pw {
+
+Status PaddedWrite(FlashPartition* partition,
+                   FlashPartition::Address address,
+                   const uint8_t* buffer,
+                   uint16_t size) {
+  RETURN_STATUS_IF(
+      address % partition->GetAlignmentBytes() ||
+          partition->GetAlignmentBytes() > cfg::kFlashUtilMaxAlignmentBytes,
+      Status::INVALID_ARGUMENT);
+  uint8_t alignment_buffer[cfg::kFlashUtilMaxAlignmentBytes] = {0};
+  uint16_t aligned_bytes = size - size % partition->GetAlignmentBytes();
+  RETURN_IF_ERROR(partition->Write(address, buffer, aligned_bytes));
+  uint16_t remaining_bytes = size - aligned_bytes;
+  if (remaining_bytes > 0) {
+    memcpy(alignment_buffer, &buffer[aligned_bytes], remaining_bytes);
+    RETURN_IF_ERROR(partition->Write(address + aligned_bytes,
+                                     alignment_buffer,
+                                     partition->GetAlignmentBytes()));
+  }
+  return Status::OK;
+}
+
+Status UnalignedRead(FlashPartition* partition,
+                     uint8_t* buffer,
+                     FlashPartition::Address address,
+                     uint16_t size) {
+  RETURN_STATUS_IF(
+      address % partition->GetAlignmentBytes() ||
+          partition->GetAlignmentBytes() > cfg::kFlashUtilMaxAlignmentBytes,
+      Status::INVALID_ARGUMENT);
+  uint16_t aligned_bytes = size - size % partition->GetAlignmentBytes();
+  RETURN_IF_ERROR(partition->Read(buffer, address, aligned_bytes));
+  uint16_t remaining_bytes = size - aligned_bytes;
+  if (remaining_bytes > 0) {
+    uint8_t alignment_buffer[cfg::kFlashUtilMaxAlignmentBytes];
+    RETURN_IF_ERROR(partition->Read(alignment_buffer,
+                                    address + aligned_bytes,
+                                    partition->GetAlignmentBytes()));
+    memcpy(&buffer[aligned_bytes], alignment_buffer, remaining_bytes);
+  }
+  return Status::OK;
+}
+
+}  // namespace pw
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
new file mode 100644
index 0000000..ce21740
--- /dev/null
+++ b/pw_kvs/key_value_store.cc
@@ -0,0 +1,805 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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.
+
+// KVS is a key-value storage format for flash based memory.
+//
+// Currently it stores key-value sets in chunks aligned with the flash memory.
+// Each chunk contains a header (KvsHeader), which is immediately followed by
+// the key, and then the data blob. To support different alignments both the
+// key length and value length are rounded up to be aligned.
+//
+// Example memory layout of sector with two KVS chunks:
+//    [ SECTOR_HEADER - Meta | alignment_padding ]
+//    [ SECTOR_HEADER - Cleaning State | alignment_padding ]
+//    [First Chunk Header | alignment_padding ]
+//    [First Chunk Key | alignment_padding ]
+//    [First Chunk Value | alignment_padding ]
+//    [Second Chunk Header | alignment_padding ]
+//    [Second Chunk Key | alignment_padding ]
+//    [Second Chunk Value | alignment_padding ]
+//
+// For efficiency if a key's value is rewritten the new value is just appended
+// to the same sector, a clean of the sector is only needed if there is no more
+// room. Cleaning the sector involves moving the most recent value of each key
+// to another sector and erasing the sector. Erasing data is treated the same
+// as rewriting data, but an erased chunk has the erased flag set, and no data.
+//
+// KVS maintains a data structure in RAM for quick indexing of each key's most
+// recent value, but no caching of data is ever performed. If a write/erase
+// function returns successfully, it is guaranteed that the data has been
+// pushed to flash. The KVS should also be resistant to sudden unplanned power
+// outages and be capable of recovering even mid clean (this is accomplished
+// using a flag which marks the sector before the clean is started).
+
+#include "pw_kvs/key_value_store.h"
+
+#include <cstring>
+
+#include "pw_kvs/os/mutex.h"
+#include "pw_kvs/util/ccitt_crc16.h"
+#include "pw_kvs/util/constexpr.h"
+#include "pw_kvs/util/flash.h"
+
+namespace pw {
+
+// Declare static constexpr variables so it can be used for pass-by-reference
+// functions.
+constexpr uint16_t KeyValueStore::kSectorReadyValue;
+
+Status KeyValueStore::Enable() {
+  os::MutexLock lock(&lock_);
+  if (enabled_) {
+    return Status::OK;
+  }
+
+  // Reset parameters.
+  memset(sector_space_remaining_, 0, sizeof(sector_space_remaining_));
+  map_size_ = 0;
+
+  // For now alignment is set to use partitions alignment.
+  alignment_bytes_ = partition_.GetAlignmentBytes();
+  DCHECK(alignment_bytes_ <= kMaxAlignmentBytes);
+
+  LOG_WARN_IF(partition_.GetSectorCount() > kSectorCountMax,
+              "Partition is larger then KVS max sector count, not all space "
+              "will be used.");
+  // Load map and setup sectors if needed (first word isn't kSectorReadyValue).
+  next_sector_clean_order_ = 0;
+  for (SectorIndex i = 0; i < SectorCount(); i++) {
+    KvsSectorHeaderMeta sector_header_meta;
+    // Because underlying flash can be encrypted + erased, trying to readback
+    // may give random values. It's important to make sure that data is not
+    // erased before trying to see if there is a token match.
+    bool is_sector_meta_erased;
+    RETURN_IF_ERROR(partition_.IsChunkErased(
+        SectorIndexToAddress(i),
+        RoundUpForAlignment(sizeof(sector_header_meta)),
+        &is_sector_meta_erased));
+    RETURN_IF_ERROR(
+        UnalignedRead(&partition_,
+                      reinterpret_cast<uint8_t*>(&sector_header_meta),
+                      SectorIndexToAddress(i),
+                      sizeof(sector_header_meta)));
+
+    constexpr int kVersion3 = 3;  // Version 3 only cleans 1 sector at a time.
+    constexpr int kVersion2 = 2;  // Version 2 is always 1 byte aligned.
+    if (is_sector_meta_erased ||
+        sector_header_meta.synchronize_token != kSectorReadyValue) {
+      // Sector needs to be setup
+      RETURN_IF_ERROR(ResetSector(i));
+      continue;
+    } else if (sector_header_meta.version != kVersion &&
+               sector_header_meta.version != kVersion3 &&  // Allow version 3
+               sector_header_meta.version != kVersion2) {  // Allow version 2
+      LOG(ERROR) << "Unsupported KVS version in sector: " << i;
+      return Status::FAILED_PRECONDITION;
+    }
+    uint32_t sector_header_cleaning_offset =
+        RoundUpForAlignment(sizeof(KvsSectorHeaderMeta));
+
+    bool clean_not_pending;
+    RETURN_IF_ERROR(partition_.IsChunkErased(
+        SectorIndexToAddress(i) + sector_header_cleaning_offset,
+        RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning)),
+        &clean_not_pending));
+
+    if (!clean_not_pending) {
+      // Sector is marked for cleaning, read the sector_clean_order
+      RETURN_IF_ERROR(
+          UnalignedRead(&partition_,
+                        reinterpret_cast<uint8_t*>(&sector_clean_order_[i]),
+                        SectorIndexToAddress(i) + sector_header_cleaning_offset,
+                        sizeof(KvsSectorHeaderCleaning::sector_clean_order)));
+      next_sector_clean_order_ =
+          std::max(sector_clean_order_[i] + 1, next_sector_clean_order_);
+    } else {
+      sector_clean_order_[i] = kSectorCleanNotPending;
+    }
+
+    // Handle alignment
+    if (sector_header_meta.version == kVersion2) {
+      sector_header_meta.alignment_bytes = 1;
+    }
+    if (sector_header_meta.alignment_bytes != alignment_bytes_) {
+      // NOTE: For now all sectors must have same alignment.
+      LOG(ERROR) << "Sector " << i << " has unexpected alignment "
+                 << alignment_bytes_
+                 << " != " << sector_header_meta.alignment_bytes;
+      return Status::FAILED_PRECONDITION;
+    }
+
+    // Scan through sector and add key/value pairs to map.
+    FlashPartition::Address offset =
+        RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)) +
+        RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning));
+    sector_space_remaining_[i] = partition_.GetSectorSizeBytes() - offset;
+    while (offset < partition_.GetSectorSizeBytes() -
+                        RoundUpForAlignment(sizeof(KvsHeader))) {
+      FlashPartition::Address address = SectorIndexToAddress(i) + offset;
+
+      // Read header
+      KvsHeader header;
+      bool is_kvs_header_erased;
+      // Because underlying flash can be encrypted + erased, trying to readback
+      // may give random values. It's important to make sure that data is not
+      // erased before trying to see if there is a token match.
+      RETURN_IF_ERROR(partition_.IsChunkErased(
+          address, RoundUpForAlignment(sizeof(header)), &is_kvs_header_erased));
+      RETURN_IF_ERROR(UnalignedRead(&partition_,
+                                    reinterpret_cast<uint8_t*>(&header),
+                                    address,
+                                    sizeof(header)));
+      if (is_kvs_header_erased || header.synchronize_token != kChunkSyncValue) {
+        if (!is_kvs_header_erased) {
+          LOG_ERROR("Next sync_token is not clear!");
+          // TODO: handle this?
+        }
+        break;  // End of elements in sector
+      }
+
+      CHECK(header.key_len <= kChunkKeyLengthMax);
+      static_assert(sizeof(temp_key_buffer_) >= (kChunkKeyLengthMax + 1u),
+                    "Key buffer must be at least big enough for a key and a "
+                    "nul-terminator.");
+
+      // Read key and add to map
+      RETURN_IF_ERROR(
+          UnalignedRead(&partition_,
+                        reinterpret_cast<uint8_t*>(&temp_key_buffer_),
+                        address + RoundUpForAlignment(sizeof(header)),
+                        header.key_len));
+      temp_key_buffer_[header.key_len] = '\0';
+      bool is_erased = header.flags & kFlagsIsErasedMask;
+
+      KeyIndex index = FindKeyInMap(temp_key_buffer_);
+      if (index == kListCapacityMax) {
+        RETURN_IF_ERROR(AppendToMap(
+            temp_key_buffer_, address, header.chunk_len, is_erased));
+      } else if (sector_clean_order_[i] >=
+                 sector_clean_order_[AddressToSectorIndex(
+                     key_map_[index].address)]) {
+        // The value being added is also in another sector (which is marked for
+        // cleaning), but the current sector's order is larger and thefore this
+        // is a newer version then what is already in the map.
+        UpdateMap(index, address, header.chunk_len, is_erased);
+      }
+
+      // Increment search
+      offset += ChunkSize(header.key_len, header.chunk_len);
+    }
+    sector_space_remaining_[i] =
+        clean_not_pending ? partition_.GetSectorSizeBytes() - offset : 0;
+  }
+
+  LOG_IF_ERROR(EnforceFreeSector())
+      << "Failed to force clean at boot, no free sectors available!";
+  enabled_ = true;
+  return Status::OK;
+}
+
+Status KeyValueStore::Get(const char* key,
+                          void* raw_value,
+                          uint16_t size,
+                          uint16_t offset) {
+  uint8_t* const value = reinterpret_cast<uint8_t*>(raw_value);
+
+  if (key == nullptr || value == nullptr) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  size_t key_len = util::StringLength(key, kChunkKeyLengthMax + 1u);
+  if (key_len == 0 || key_len > kChunkKeyLengthMax) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  // TODO: Support unaligned offset reads.
+  if (offset % alignment_bytes_ != 0) {
+    LOG_ERROR("Currently unaligned offsets are not supported");
+    return Status::INVALID_ARGUMENT;
+  }
+  os::MutexLock lock(&lock_);
+  if (!enabled_) {
+    return Status::FAILED_PRECONDITION;
+  }
+
+  KeyIndex key_index = FindKeyInMap(key);
+  if (key_index == kListCapacityMax || key_map_[key_index].is_erased) {
+    return Status::NOT_FOUND;
+  }
+  KvsHeader header;
+  // TODO: Could cache the CRC and avoid reading the header.
+  RETURN_IF_ERROR(UnalignedRead(&partition_,
+                                reinterpret_cast<uint8_t*>(&header),
+                                key_map_[key_index].address,
+                                sizeof(header)));
+  if (kChunkSyncValue != header.synchronize_token) {
+    return Status::DATA_LOSS;
+  }
+  if (size + offset > header.chunk_len) {
+    LOG_ERROR("Out of bounds read: offset(%u) + size(%u) > data_size(%u)",
+              offset,
+              size,
+              header.chunk_len);
+    return Status::INVALID_ARGUMENT;
+  }
+  RETURN_IF_ERROR(UnalignedRead(
+      &partition_,
+      value,
+      key_map_[key_index].address + RoundUpForAlignment(sizeof(KvsHeader)) +
+          RoundUpForAlignment(header.key_len) + offset,
+      size));
+
+  // Verify CRC only when full packet was read.
+  if (offset == 0 && size == header.chunk_len) {
+    uint16_t crc = CalculateCrc(key, key_len, value, size);
+    if (crc != header.crc) {
+      LOG_ERROR("KVS CRC does not match for key=%s [expected %u, found %u]",
+                key,
+                header.crc,
+                crc);
+      return Status::DATA_LOSS;
+    }
+  }
+  return Status::OK;
+}
+
+uint16_t KeyValueStore::CalculateCrc(const char* key,
+                                     uint16_t key_size,
+                                     const uint8_t* value,
+                                     uint16_t value_size) const {
+  CcittCrc16 crc;
+  crc.AppendBytes(ConstBuffer(reinterpret_cast<const uint8_t*>(key), key_size));
+  return crc.AppendBytes(ConstBuffer(value, value_size));
+}
+
+Status KeyValueStore::CalculateCrcFromValueAddress(
+    const char* key,
+    uint16_t key_size,
+    FlashPartition::Address value_address,
+    uint16_t value_size,
+    uint16_t* crc_ret) {
+  CcittCrc16 crc;
+  crc.AppendBytes(ConstBuffer(reinterpret_cast<const uint8_t*>(key), key_size));
+  for (size_t i = 0; i < value_size; i += TempBufferAlignedSize()) {
+    auto read_size = std::min(value_size - i, TempBufferAlignedSize());
+    RETURN_IF_ERROR(
+        UnalignedRead(&partition_, temp_buffer_, value_address + i, read_size));
+    crc.AppendBytes(ConstBuffer(temp_buffer_, read_size));
+  }
+  *crc_ret = crc.CurrentValue();
+  return Status::OK;
+}
+
+Status KeyValueStore::Put(const char* key,
+                          const void* raw_value,
+                          uint16_t size) {
+  const uint8_t* const value = reinterpret_cast<const uint8_t*>(raw_value);
+  if (key == nullptr || value == nullptr) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  size_t key_len = util::StringLength(key, (kChunkKeyLengthMax + 1u));
+  if (key_len == 0 || key_len > kChunkKeyLengthMax ||
+      size > kChunkValueLengthMax) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  os::MutexLock lock(&lock_);
+  if (!enabled_) {
+    return Status::FAILED_PRECONDITION;
+  }
+
+  KeyIndex index = FindKeyInMap(key);
+  if (index != kListCapacityMax) {  // Key already in map, rewrite value
+    return RewriteValue(index, value, size);
+  }
+
+  FlashPartition::Address address = FindSpace(ChunkSize(key_len, size));
+  if (address == kSectorInvalid) {
+    return Status::RESOURCE_EXHAUSTED;
+  }
+
+  // Check if this would use the last empty sector on KVS with multiple sectors
+  if (SectorCount() > 1 && IsInLastFreeSector(address)) {
+    // Forcing a full garbage collect to free more sectors.
+    RETURN_IF_ERROR(FullGarbageCollect());
+    address = FindSpace(ChunkSize(key_len, size));
+    if (address == kSectorInvalid || IsInLastFreeSector(address)) {
+      // Couldn't find space, KVS is full.
+      return Status::RESOURCE_EXHAUSTED;
+    }
+  }
+
+  RETURN_IF_ERROR(WriteKeyValue(address, key, value, size));
+  RETURN_IF_ERROR(AppendToMap(key, address, size));
+
+  return Status::OK;
+}
+
+// Garbage collection cleans sectors to try to free up space.
+// If clean_pending_sectors is true, it will only clean sectors which are
+// currently pending a clean.
+// If clean_pending_sectors is false, it will only clean sectors which are not
+// currently pending a clean, instead it will mark them for cleaning and attempt
+// a clean.
+// If exit_when_have_free_sector is true, it will exit once a single free sector
+// exists.
+Status KeyValueStore::GarbageCollectImpl(bool clean_pending_sectors,
+                                         bool exit_when_have_free_sector) {
+  // Try to clean any pending sectors
+  for (SectorIndex sector = 0; sector < SectorCount(); sector++) {
+    if (clean_pending_sectors ==
+        (sector_clean_order_[sector] != kSectorCleanNotPending)) {
+      if (!clean_pending_sectors) {
+        RETURN_IF_ERROR(MarkSectorForClean(sector));
+      }
+      Status status = CleanSector(sector);
+      if (!status.ok() && status != Status::RESOURCE_EXHAUSTED) {
+        return status;
+      }
+      if (exit_when_have_free_sector && HaveEmptySectorImpl()) {
+        return Status::OK;  // Now have a free sector
+      }
+    }
+  }
+  return Status::OK;
+}
+
+Status KeyValueStore::EnforceFreeSector() {
+  if (SectorCount() == 1 || HasEmptySector()) {
+    return Status::OK;
+  }
+  LOG_INFO("KVS garbage collecting to get a free sector");
+  RETURN_IF_ERROR(GarbageCollectImpl(true /*clean_pending_sectors*/,
+                                     true /*exit_when_have_free_sector*/));
+  if (HasEmptySector()) {
+    return Status::OK;
+  }
+  LOG_INFO("KVS: trying to clean non-pending sectors for more space");
+  RETURN_IF_ERROR(GarbageCollectImpl(false /*clean_pending_sectors*/,
+                                     true /*exit_when_have_free_sector*/));
+  return HaveEmptySectorImpl() ? Status::OK : Status::RESOURCE_EXHAUSTED;
+}
+
+Status KeyValueStore::FullGarbageCollect() {
+  LOG_INFO("KVS: Full garbage collecting to try to free space");
+  RETURN_IF_ERROR(GarbageCollectImpl(true /*clean_pending_sectors*/,
+                                     false /*exit_when_have_free_sector*/));
+  return GarbageCollectImpl(false /*clean_pending_sectors*/,
+                            false /*exit_when_have_free_sector*/);
+}
+
+Status KeyValueStore::RewriteValue(KeyIndex key_index,
+                                   const uint8_t* value,
+                                   uint16_t size,
+                                   bool is_erased) {
+  // Compare values, return if values are the same.
+  if (ValueMatches(key_index, value, size, is_erased)) {
+    return Status::OK;
+  }
+
+  size_t key_length =
+      util::StringLength(key_map_[key_index].key, (kChunkKeyLengthMax + 1u));
+  RETURN_STATUS_IF(key_length > kChunkKeyLengthMax, Status::INTERNAL);
+
+  uint32_t space_required = ChunkSize(key_length, size);
+  SectorIndex sector = AddressToSectorIndex(key_map_[key_index].address);
+  uint32_t sector_space_remaining = SectorSpaceRemaining(sector);
+
+  FlashPartition::Address address = kSectorInvalid;
+  if (sector_space_remaining >= space_required) {
+    // Space available within sector, append to end
+    address = SectorIndexToAddress(sector) + partition_.GetSectorSizeBytes() -
+              sector_space_remaining;
+  } else {
+    // No space in current sector, mark sector for clean and use another sector.
+    RETURN_IF_ERROR(MarkSectorForClean(sector));
+    address = FindSpace(ChunkSize(key_length, size));
+  }
+  if (address == kSectorInvalid) {
+    return Status::RESOURCE_EXHAUSTED;
+  }
+  RETURN_IF_ERROR(
+      WriteKeyValue(address, key_map_[key_index].key, value, size, is_erased));
+  UpdateMap(key_index, address, size, is_erased);
+
+  return EnforceFreeSector();
+}
+
+bool KeyValueStore::ValueMatches(KeyIndex index,
+                                 const uint8_t* value,
+                                 uint16_t size,
+                                 bool is_erased) {
+  // Compare sizes of CRC.
+  if (size != key_map_[index].chunk_len) {
+    return false;
+  }
+  KvsHeader header;
+  UnalignedRead(&partition_,
+                reinterpret_cast<uint8_t*>(&header),
+                key_map_[index].address,
+                sizeof(header));
+  uint8_t key_len =
+      util::StringLength(key_map_[index].key, (kChunkKeyLengthMax + 1u));
+  if (key_len > kChunkKeyLengthMax) {
+    return false;
+  }
+
+  if ((header.flags & kFlagsIsErasedMask) != is_erased) {
+    return false;
+  } else if ((header.flags & kFlagsIsErasedMask) && is_erased) {
+    return true;
+  }
+
+  // Compare checksums.
+  if (header.crc != CalculateCrc(key_map_[index].key, key_len, value, size)) {
+    return false;
+  }
+  FlashPartition::Address address = key_map_[index].address +
+                                    RoundUpForAlignment(sizeof(KvsHeader)) +
+                                    RoundUpForAlignment(key_len);
+  // Compare full values.
+  for (size_t i = 0; i < key_map_[index].chunk_len;
+       i += TempBufferAlignedSize()) {
+    auto read_size =
+        std::min(key_map_[index].chunk_len - i, TempBufferAlignedSize());
+    auto status =
+        UnalignedRead(&partition_, temp_buffer_, address + i, read_size);
+    if (!status.ok()) {
+      LOG(ERROR) << "Failed to read chunk: " << status;
+      return false;
+    }
+    if (memcmp(value + i, temp_buffer_, read_size) != 0) {
+      return false;
+    }
+  }
+  return true;
+}
+
+Status KeyValueStore::Erase(const char* key) {
+  if (key == nullptr) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  size_t key_len = util::StringLength(key, (kChunkKeyLengthMax + 1u));
+  if (key_len == 0 || key_len > kChunkKeyLengthMax) {
+    return Status::INVALID_ARGUMENT;
+  }
+  os::MutexLock lock(&lock_);
+  if (!enabled_) {
+    return Status::FAILED_PRECONDITION;
+  }
+
+  KeyIndex key_index = FindKeyInMap(key);
+  if (key_index == kListCapacityMax || key_map_[key_index].is_erased) {
+    return Status::NOT_FOUND;
+  }
+  return RewriteValue(key_index, nullptr, 0, true);
+}
+
+Status KeyValueStore::ResetSector(SectorIndex sector_index) {
+  KvsSectorHeaderMeta sector_header = {.synchronize_token = kSectorReadyValue,
+                                       .version = kVersion,
+                                       .alignment_bytes = alignment_bytes_,
+                                       .padding = 0xFFFF};
+  bool sector_erased = false;
+  partition_.IsChunkErased(SectorIndexToAddress(sector_index),
+                           partition_.GetSectorSizeBytes(),
+                           &sector_erased);
+  auto status = partition_.Erase(SectorIndexToAddress(sector_index), 1);
+
+  // If erasure failed, check first to see if it's merely unimplemented
+  // (as in sub-sector KVSs).
+  if (!status.ok() && !(status == Status::UNIMPLEMENTED && sector_erased)) {
+    return status;
+  }
+
+  RETURN_IF_ERROR(PaddedWrite(&partition_,
+                              SectorIndexToAddress(sector_index),
+                              reinterpret_cast<const uint8_t*>(&sector_header),
+                              sizeof(sector_header)));
+
+  // Update space remaining
+  sector_clean_order_[sector_index] = kSectorCleanNotPending;
+  sector_space_remaining_[sector_index] = SectorSpaceAvailableWhenEmpty();
+  return Status::OK;
+}
+
+Status KeyValueStore::WriteKeyValue(FlashPartition::Address address,
+                                    const char* key,
+                                    const uint8_t* value,
+                                    uint16_t size,
+                                    bool is_erased) {
+  uint16_t key_length = util::StringLength(key, (kChunkKeyLengthMax + 1u));
+  RETURN_STATUS_IF(key_length > kChunkKeyLengthMax, Status::INTERNAL);
+
+  constexpr uint16_t kFlagDefaultValue = 0;
+  KvsHeader header = {
+      .synchronize_token = kChunkSyncValue,
+      .crc = CalculateCrc(key, key_length, value, size),
+      .flags = is_erased ? kFlagsIsErasedMask : kFlagDefaultValue,
+      .key_len = key_length,
+      .chunk_len = size};
+
+  SectorIndex sector = AddressToSectorIndex(address);
+  RETURN_IF_ERROR(PaddedWrite(&partition_,
+                              address,
+                              reinterpret_cast<uint8_t*>(&header),
+                              sizeof(header)));
+  address += RoundUpForAlignment(sizeof(header));
+  RETURN_IF_ERROR(PaddedWrite(
+      &partition_, address, reinterpret_cast<const uint8_t*>(key), key_length));
+  address += RoundUpForAlignment(key_length);
+  if (size > 0) {
+    RETURN_IF_ERROR(PaddedWrite(&partition_, address, value, size));
+  }
+  sector_space_remaining_[sector] -= ChunkSize(key_length, size);
+  return Status::OK;
+}
+
+Status KeyValueStore::MoveChunk(FlashPartition::Address dest_address,
+                                FlashPartition::Address src_address,
+                                uint16_t size) {
+  DCHECK_EQ(src_address % partition_.GetAlignmentBytes(), 0);
+  DCHECK_EQ(dest_address % partition_.GetAlignmentBytes(), 0);
+  DCHECK_EQ(size % partition_.GetAlignmentBytes(), 0);
+
+  // Copy data over in chunks to reduce the size of the temporary buffer
+  for (size_t i = 0; i < size; i += TempBufferAlignedSize()) {
+    size_t move_size = std::min(size - i, TempBufferAlignedSize());
+    DCHECK_EQ(move_size % alignment_bytes_, 0);
+    RETURN_IF_ERROR(partition_.Read(temp_buffer_, src_address + i, move_size));
+    RETURN_IF_ERROR(
+        partition_.Write(dest_address + i, temp_buffer_, move_size));
+  }
+  return Status::OK;
+}
+
+Status KeyValueStore::MarkSectorForClean(SectorIndex sector) {
+  if (sector_clean_order_[sector] != kSectorCleanNotPending) {
+    return Status::OK;  // Sector is already marked for clean
+  }
+
+  // Flag the sector as clean being active. This ensures we can handle losing
+  // power while a clean is active.
+  const KvsSectorHeaderCleaning kValue = {next_sector_clean_order_};
+  RETURN_IF_ERROR(
+      PaddedWrite(&partition_,
+                  SectorIndexToAddress(sector) +
+                      RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)),
+                  reinterpret_cast<const uint8_t*>(&kValue),
+                  sizeof(kValue)));
+  sector_space_remaining_[sector] = 0;
+  sector_clean_order_[sector] = next_sector_clean_order_;
+  next_sector_clean_order_++;
+  return Status::OK;
+}
+
+Status KeyValueStore::CleanSector(SectorIndex sector) {
+  // Iterate through the map, for each valid element which is in this sector:
+  //    - Find space in another sector which can fit this chunk.
+  //    - Add to the other sector and update the map.
+  for (KeyValueStore::KeyIndex i = 0; i < map_size_; i++) {
+    // If this key is an erased chunk don't need to move it.
+    while (i < map_size_ &&
+           sector == AddressToSectorIndex(key_map_[i].address) &&
+           key_map_[i].is_erased) {  // Remove this key from the map.
+      RemoveFromMap(i);
+      // NOTE: i is now a new key, and map_size_ has been decremented.
+    }
+
+    if (i < map_size_ && sector == AddressToSectorIndex(key_map_[i].address)) {
+      uint8_t key_len =
+          util::StringLength(key_map_[i].key, (kChunkKeyLengthMax + 1u));
+      FlashPartition::Address address = key_map_[i].address;
+      auto size = ChunkSize(key_len, key_map_[i].chunk_len);
+      FlashPartition::Address move_address = FindSpace(size);
+      if (move_address == kSectorInvalid) {
+        return Status::RESOURCE_EXHAUSTED;
+      }
+      RETURN_IF_ERROR(MoveChunk(move_address, address, size));
+      sector_space_remaining_[AddressToSectorIndex(move_address)] -= size;
+      key_map_[i].address = move_address;  // Update map
+    }
+  }
+  ResetSector(sector);
+  return Status::OK;
+}
+
+Status KeyValueStore::CleanOneSector(bool* all_sectors_have_been_cleaned) {
+  if (all_sectors_have_been_cleaned == nullptr) {
+    return Status::INVALID_ARGUMENT;
+  }
+  os::MutexLock lock(&lock_);
+  bool have_cleaned_sector = false;
+  for (SectorIndex sector = 0; sector < SectorCount(); sector++) {
+    if (sector_clean_order_[sector] != kSectorCleanNotPending) {
+      if (have_cleaned_sector) {  // only clean 1 sector
+        *all_sectors_have_been_cleaned = false;
+        return Status::OK;
+      }
+      RETURN_IF_ERROR(CleanSector(sector));
+      have_cleaned_sector = true;
+    }
+  }
+  *all_sectors_have_been_cleaned = true;
+  return Status::OK;
+}
+
+Status KeyValueStore::CleanAllInternal() {
+  for (SectorIndex sector = 0; sector < SectorCount(); sector++) {
+    if (sector_clean_order_[sector] != kSectorCleanNotPending) {
+      RETURN_IF_ERROR(CleanSector(sector));
+    }
+  }
+  return Status::OK;
+}
+
+FlashPartition::Address KeyValueStore::FindSpace(
+    uint16_t requested_size) const {
+  if (requested_size > SectorSpaceAvailableWhenEmpty()) {
+    return kSectorInvalid;  // This would never fit
+  }
+  // Iterate through sectors, find first available sector with enough space.
+  SectorIndex first_empty_sector = kSectorInvalid;
+  for (SectorIndex i = 0; i < SectorCount(); i++) {
+    uint32_t space_remaining = SectorSpaceRemaining(i);
+    if (space_remaining == SectorSpaceAvailableWhenEmpty() &&
+        first_empty_sector == kSectorInvalid) {
+      // Skip the first empty sector to encourage keeping one sector free.
+      first_empty_sector = i;
+      continue;
+    }
+    if (space_remaining >= requested_size) {
+      return SectorIndexToAddress(i) + partition_.GetSectorSizeBytes() -
+             space_remaining;
+    }
+  }
+  // Use first empty sector if that is all that is available.
+  if (first_empty_sector != kSectorInvalid) {
+    return SectorIndexToAddress(first_empty_sector) +
+           partition_.GetSectorSizeBytes() - SectorSpaceAvailableWhenEmpty();
+  }
+  return kSectorInvalid;
+}
+
+uint32_t KeyValueStore::SectorSpaceRemaining(SectorIndex sector_index) const {
+  return sector_space_remaining_[sector_index];
+}
+
+Status KeyValueStore::GetValueSize(const char* key, uint16_t* value_size) {
+  if (key == nullptr || value_size == nullptr) {
+    return Status::INVALID_ARGUMENT;
+  }
+
+  size_t key_len = util::StringLength(key, (kChunkKeyLengthMax + 1u));
+  if (key_len == 0 || key_len > kChunkKeyLengthMax) {
+    return Status::INVALID_ARGUMENT;
+  }
+  os::MutexLock lock(&lock_);
+  if (!enabled_) {
+    return Status::FAILED_PRECONDITION;
+  }
+
+  uint8_t idx = FindKeyInMap(key);
+  if (idx == kListCapacityMax || key_map_[idx].is_erased) {
+    return Status::NOT_FOUND;
+  }
+  *value_size = key_map_[idx].chunk_len;
+  return Status::OK;
+}
+
+Status KeyValueStore::AppendToMap(const char* key,
+                                  FlashPartition::Address address,
+                                  uint16_t chunk_len,
+                                  bool is_erased) {
+  if (map_size_ >= kListCapacityMax) {
+    LOG_ERROR("Can't add: reached max supported keys %d", kListCapacityMax);
+    return Status::INTERNAL;
+  }
+
+  // Copy incoming key into map entry, ensuring size checks and nul-termination.
+  StringBuilder key_builder(key_map_[map_size_].key,
+                            sizeof(key_map_[map_size_].key));
+  key_builder.append(key);
+
+  if (!key_builder.status().ok()) {
+    LOG_ERROR("Can't add: got invalid key: %s!", key_builder.status().str());
+    return Status::INTERNAL;
+  }
+
+  key_map_[map_size_].address = address;
+  key_map_[map_size_].chunk_len = chunk_len;
+  key_map_[map_size_].is_erased = is_erased;
+  map_size_++;
+
+  return Status::OK;
+}
+
+KeyValueStore::KeyIndex KeyValueStore::FindKeyInMap(const char* key) const {
+  for (KeyIndex i = 0; i < map_size_; i++) {
+    if (strncmp(key, key_map_[i].key, sizeof(key_map_[i].key)) == 0) {
+      return i;
+    }
+  }
+  return kListCapacityMax;
+}
+
+void KeyValueStore::UpdateMap(KeyIndex index,
+                              FlashPartition::Address address,
+                              uint16_t chunk_len,
+                              bool is_erased) {
+  key_map_[index].address = address;
+  key_map_[index].chunk_len = chunk_len;
+  key_map_[index].is_erased = is_erased;
+}
+
+void KeyValueStore::RemoveFromMap(KeyIndex key_index) {
+  key_map_[key_index] = key_map_[--map_size_];
+}
+
+uint8_t KeyValueStore::KeyCount() const {
+  uint8_t count = 0;
+  for (unsigned i = 0; i < map_size_; i++) {
+    count += key_map_[i].is_erased ? 0 : 1;
+  }
+  return count;
+}
+
+const char* KeyValueStore::GetKey(uint8_t idx) const {
+  uint8_t count = 0;
+  for (unsigned i = 0; i < map_size_; i++) {
+    if (!key_map_[i].is_erased) {
+      if (idx == count) {
+        return key_map_[i].key;
+      }
+      count++;
+    }
+  }
+  return nullptr;
+}
+
+uint16_t KeyValueStore::GetValueSize(uint8_t idx) const {
+  uint8_t count = 0;
+  for (unsigned i = 0; i < map_size_; i++) {
+    if (!key_map_[i].is_erased) {
+      if (idx == count++) {
+        return key_map_[i].chunk_len;
+      }
+    }
+  }
+  return 0;
+}
+
+}  // namespace pw
diff --git a/pw_kvs/key_value_store_sub_sector_test.cc b/pw_kvs/key_value_store_sub_sector_test.cc
new file mode 100644
index 0000000..ff908f5
--- /dev/null
+++ b/pw_kvs/key_value_store_sub_sector_test.cc
@@ -0,0 +1,130 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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/key_value_store.h"
+
+#include "pw_kvs/assert.h"
+#include "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/platform/board.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/test/fixture.h"
+#include "pw_kvs/test/framework.h"
+#include "pw_kvs/test/status_macros.h"
+
+#if USE_MEMORY_BUFFER
+#include "pw_kvs/test/fakes/in_memory_fake_flash.h"
+#endif  // USE_MEMORY_BUFFER
+
+namespace pw {
+namespace {
+
+#if USE_MEMORY_BUFFER
+InMemoryFakeFlash<1024, 4> test_flash(8);  // 4 x 1k sectors, 8 byte alignment
+FlashPartition test_partition(&test_flash, 0, test_flash.GetSectorCount());
+// Test KVS against FlashSubSector
+FlashMemorySubSector test_subsector_flash(&test_flash,
+                                          0,
+                                          128);  // Expose less than a sector.
+#else   // Device test
+FlashPartition& test_partition = Board::Instance().FlashExternalTestPartition();
+FlashMemorySubSector& test_subsector_flash =
+    Board::Instance().FlashMemorySubSectorTestChunk();
+#endif  // USE_MEMORY_BUFFER
+
+FlashPartition test_subsector_partition(&test_subsector_flash, 0, 1);
+KeyValueStore subsector_kvs(&test_subsector_partition);
+
+std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
+
+}  // namespace
+
+TEST(KeyValueStoreTest, WorksWithFlashSubSector) {
+  // The subsector region is assumed to be a part of the test partition.
+  // In order to clear state before the test, we must erase the entire test
+  // partition because erase operations are disallowed on FlashMemorySubSectors.
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // Reset KVS
+  subsector_kvs.Disable();
+  ASSERT_OK(subsector_kvs.Enable());
+
+  // Add some data
+  uint8_t value1 = 0xDA;
+  ASSERT_OK(subsector_kvs.Put(keys[0], &value1, sizeof(value1)));
+
+  uint32_t value2 = 0xBAD0301f;
+  ASSERT_OK(subsector_kvs.Put(
+      keys[1], reinterpret_cast<uint8_t*>(&value2), sizeof(value2)));
+
+  // Verify data
+  uint32_t test2;
+  EXPECT_OK(subsector_kvs.Get(
+      keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+  uint8_t test1;
+  ASSERT_OK(subsector_kvs.Get(
+      keys[0], reinterpret_cast<uint8_t*>(&test1), sizeof(test1)));
+
+  EXPECT_EQ(test1, value1);
+
+  // Erase a key
+  ASSERT_OK(subsector_kvs.Erase(keys[0]));
+
+  // Verify it was erased
+  EXPECT_EQ(subsector_kvs
+                .Get(keys[0], reinterpret_cast<uint8_t*>(&test1), sizeof(test1))
+                .code(),
+            Status::NOT_FOUND);
+  test2 = 0;
+  ASSERT_OK(subsector_kvs.Get(
+      keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+  EXPECT_EQ(test2, value2);
+
+  // Erase other key
+  subsector_kvs.Erase(keys[1]);
+
+  // Verify it was erased
+  EXPECT_EQ(subsector_kvs.KeyCount(), 0);
+}
+
+TEST(KeyValueStoreTest, WorksWithFlashSubSector_MemoryExhausted) {
+  // The subsector region is assumed to be a part of the test partition.
+  // In order to clear state before the test, we must erase the entire test
+  // partition because erase operations are disallowed on FlashMemorySubSectors.
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // Reset KVS
+  subsector_kvs.Disable();
+  ASSERT_OK(subsector_kvs.Enable());
+
+  // Store as much data as possible in the KVS until it fills up.
+  uint64_t test = 0;
+  for (; test < test_subsector_flash.GetSizeBytes(); test++) {
+    Status status = subsector_kvs.Put(keys[0], test);
+    if (status.ok()) {
+      continue;
+    }
+    // Expected code for erasure failure.
+    ASSERT_EQ(Status::RESOURCE_EXHAUSTED, status);
+    break;
+  }
+  EXPECT_GT(test, 0U);  // Should've at least succeeded with one Put.
+
+  // Even though we failed to fill the KVS, it still works, and we
+  // should have the previous test value as the most recent value in the KVS.
+  uint64_t value = 0;
+  ASSERT_OK(subsector_kvs.Get(keys[0], &value));
+  EXPECT_EQ(test - 1, value);
+}
+
+}  // namespace pw
diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
new file mode 100644
index 0000000..fa5eaf9
--- /dev/null
+++ b/pw_kvs/key_value_store_test.cc
@@ -0,0 +1,1396 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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/key_value_store.h"
+
+#include "pw_kvs/assert.h"
+#include "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/os/stack_checks.h"
+#include "pw_kvs/platform/board.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/test/fixture.h"
+#include "pw_kvs/test/framework.h"
+#include "pw_kvs/test/status_macros.h"
+#include "pw_kvs/util/ccitt_crc16.h"
+
+#if USE_MEMORY_BUFFER
+#include "pw_kvs/test/fakes/in_memory_fake_flash.h"
+#endif  // USE_MEMORY_BUFFER
+
+namespace pw {
+namespace {
+
+#if USE_MEMORY_BUFFER
+// Although it might be useful to test other configurations, some tests require
+// at least 3 sectors; therfore it should have this when checked in.
+InMemoryFakeFlash<4 * 1024, 4> test_flash(
+    16);  // 4 x 4k sectors, 16 byte alignment
+FlashPartition test_partition(&test_flash, 0, test_flash.GetSectorCount());
+InMemoryFakeFlash<1024, 60> large_test_flash(8);
+FlashPartition large_test_partition(&large_test_flash,
+                                    0,
+                                    large_test_flash.GetSectorCount());
+#else   // Device test
+FlashPartition& test_partition = Board::Instance().FlashExternalTestPartition();
+#endif  // USE_MEMORY_BUFFER
+
+KeyValueStore kvs(&test_partition);
+
+// Use test fixture for logging support
+class KeyValueStoreTest : public ::testing::Test {
+ protected:
+  KeyValueStoreTest() : kvs_local_(&test_partition) {}
+
+  KeyValueStore kvs_local_;
+};
+
+std::array<uint8_t, 512> buffer;
+std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
+
+Status PaddedWrite(FlashPartition* partition,
+                   FlashPartition::Address address,
+                   const uint8_t* buf,
+                   uint16_t size) {
+  static constexpr uint16_t kMaxAlignmentBytes = 128;
+  uint8_t alignment_buffer[kMaxAlignmentBytes] = {0};
+  uint16_t aligned_bytes = size - (size % partition->GetAlignmentBytes());
+  RETURN_IF_ERROR(partition->Write(address, buf, aligned_bytes));
+  uint16_t remaining_bytes = size - aligned_bytes;
+  if (remaining_bytes > 0) {
+    memcpy(alignment_buffer, &buf[aligned_bytes], remaining_bytes);
+    RETURN_IF_ERROR(partition->Write(address + aligned_bytes,
+                                     alignment_buffer,
+                                     partition->GetAlignmentBytes()));
+  }
+  return Status::OK;
+}
+
+size_t RoundUpForAlignment(size_t size) {
+  uint16_t alignment = test_partition.GetAlignmentBytes();
+  if (size % alignment != 0) {
+    return size + alignment - size % alignment;
+  }
+  return size;
+}
+
+// This class gives attributes of KVS that we are testing against
+class KvsAttributes {
+ public:
+  KvsAttributes(size_t key_size, size_t data_size)
+      : sector_header_meta_size_(
+            RoundUpForAlignment(KeyValueStore::kHeaderSize)),
+        sector_header_clean_size_(
+            RoundUpForAlignment(KeyValueStore::kHeaderSize)),
+        chunk_header_size_(RoundUpForAlignment(KeyValueStore::kHeaderSize)),
+        data_size_(RoundUpForAlignment(data_size)),
+        key_size_(RoundUpForAlignment(key_size)),
+        erase_size_(chunk_header_size_ + key_size_),
+        min_put_size_(chunk_header_size_ + key_size_ + data_size_) {}
+
+  size_t SectorHeaderSize() {
+    return sector_header_meta_size_ + sector_header_clean_size_;
+  }
+  size_t SectorHeaderMetaSize() { return sector_header_meta_size_; }
+  size_t ChunkHeaderSize() { return chunk_header_size_; }
+  size_t DataSize() { return data_size_; }
+  size_t KeySize() { return key_size_; }
+  size_t EraseSize() { return erase_size_; }
+  size_t MinPutSize() { return min_put_size_; }
+
+ private:
+  const size_t sector_header_meta_size_;
+  const size_t sector_header_clean_size_;
+  const size_t chunk_header_size_;
+  const size_t data_size_;
+  const size_t key_size_;
+  const size_t erase_size_;
+  const size_t min_put_size_;
+};
+
+// Intention of this is to put and erase key-val to fill up sectors. It's a
+// helper function in testing how KVS handles cases where flash sector is full
+// or near full.
+void FillKvs(const char* key, size_t size_to_fill) {
+  constexpr size_t kTestDataSize = 8;
+  KvsAttributes kvs_attr(std::strlen(key), kTestDataSize);
+  const size_t kMaxPutSize =
+      buffer.size() + kvs_attr.ChunkHeaderSize() + kvs_attr.KeySize();
+
+  CHECK(size_to_fill >= kvs_attr.MinPutSize() + kvs_attr.EraseSize());
+
+  // Saving enough space to perform erase after loop
+  size_to_fill -= kvs_attr.EraseSize();
+  // We start with possible small chunk to prevent too small of a Kvs.Put() at
+  // the end.
+  size_t chunk_len =
+      std::max(kvs_attr.MinPutSize(), size_to_fill % buffer.size());
+  memset(buffer.data(), 0, buffer.size());
+  while (size_to_fill > 0) {
+    buffer[0]++;  // Changing buffer value so put actually does something
+    ASSERT_OK(
+        kvs.Put(key,
+                buffer.data(),
+                chunk_len - kvs_attr.ChunkHeaderSize() - kvs_attr.KeySize()));
+    size_to_fill -= chunk_len;
+    chunk_len = std::min(size_to_fill, kMaxPutSize);
+  }
+  ASSERT_OK(kvs.Erase(key));
+}
+
+uint16_t CalcKvsCrc(const char* key, const void* data, size_t data_len) {
+  CcittCrc16 crc;
+  static constexpr size_t kChunkKeyLengthMax = 15;
+  crc.AppendBytes(
+      ConstBuffer(reinterpret_cast<const uint8_t*>(key),
+                  pw::util::StringLength(key, kChunkKeyLengthMax)));
+  return crc.AppendBytes(
+      ConstBuffer(reinterpret_cast<const uint8_t*>(data), data_len));
+}
+
+uint16_t CalcTestPartitionCrc() {
+  uint8_t buf[16];  // Read as 16 byte chunks
+  CHECK_EQ(sizeof(buf) % test_partition.GetAlignmentBytes(), 0);
+  CHECK_EQ(test_partition.GetSizeBytes() % sizeof(buf), 0);
+  CcittCrc16 crc;
+  for (size_t i = 0; i < test_partition.GetSizeBytes(); i += sizeof(buf)) {
+    test_partition.Read(buf, i, sizeof(buf));
+    crc.AppendBytes(ConstBuffer(buf, sizeof(buf)));
+  }
+  return crc.CurrentValue();
+}
+}  // namespace
+
+TEST_F(KeyValueStoreTest, FuzzTest) {
+  if (test_partition.GetSectorSizeBytes() < 4 * 1024 ||
+      test_partition.GetSectorCount() < 4) {
+    LOG_INFO("Sectors too small, skipping test.");
+    return;  // TODO: Test could be generalized
+  }
+  // Erase
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  const char* key1 = "Buf1";
+  const char* key2 = "Buf2";
+  const size_t kLargestBufSize = 3 * 1024;
+  static uint8_t buf1[kLargestBufSize];
+  static uint8_t buf2[kLargestBufSize];
+  memset(buf1, 1, sizeof(buf1));
+  memset(buf2, 2, sizeof(buf2));
+
+  // Start with things in KVS
+  ASSERT_OK(kvs.Put(key1, buf1, sizeof(buf1)));
+  ASSERT_OK(kvs.Put(key2, buf2, sizeof(buf2)));
+  for (size_t j = 0; j < keys.size(); j++) {
+    ASSERT_OK(kvs.Put(keys[j], j));
+  }
+
+  for (size_t i = 0; i < 100; i++) {
+    // Vary two sizes
+    size_t size1 = (kLargestBufSize) / (i + 1);
+    size_t size2 = (kLargestBufSize) / (100 - i);
+    for (size_t j = 0; j < 50; j++) {
+      // Rewrite a single key many times, can fill up a sector
+      ASSERT_OK(kvs.Put("some_data", j));
+    }
+    // Delete and re-add everything
+    ASSERT_OK(kvs.Erase(key1));
+    ASSERT_OK(kvs.Put(key1, buf1, size1));
+    ASSERT_OK(kvs.Erase(key2));
+    ASSERT_OK(kvs.Put(key2, buf2, size2));
+    for (size_t j = 0; j < keys.size(); j++) {
+      ASSERT_OK(kvs.Erase(keys[j]));
+      ASSERT_OK(kvs.Put(keys[j], j));
+    }
+
+    // Re-enable and verify
+    kvs.Disable();
+    ASSERT_OK(kvs.Enable());
+    static uint8_t buf[4 * 1024];
+    ASSERT_OK(kvs.Get(key1, buf, size1));
+    ASSERT_EQ(memcmp(buf, buf1, size1), 0);
+    ASSERT_OK(kvs.Get(key2, buf, size2));
+    ASSERT_EQ(memcmp(buf2, buf2, size2), 0);
+    for (size_t j = 0; j < keys.size(); j++) {
+      size_t ret = 1000;
+      ASSERT_OK(kvs.Get(keys[j], &ret));
+      ASSERT_EQ(ret, j);
+    }
+  }
+}
+
+TEST_F(KeyValueStoreTest, Basic) {
+  // Erase
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Add some data
+  uint8_t value1 = 0xDA;
+  ASSERT_OK(kvs.Put(keys[0], &value1, sizeof(value1)));
+
+  uint32_t value2 = 0xBAD0301f;
+  ASSERT_OK(
+      kvs.Put(keys[1], reinterpret_cast<uint8_t*>(&value2), sizeof(value2)));
+
+  // Verify data
+  uint32_t test2;
+  EXPECT_OK(
+      kvs.Get(keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+  uint8_t test1;
+  ASSERT_OK(
+      kvs.Get(keys[0], reinterpret_cast<uint8_t*>(&test1), sizeof(test1)));
+
+  EXPECT_EQ(test1, value1);
+  EXPECT_EQ(test2, value2);
+
+  // Erase a key
+  EXPECT_OK(kvs.Erase(keys[0]));
+
+  // Verify it was erased
+  EXPECT_EQ(kvs.Get(keys[0], reinterpret_cast<uint8_t*>(&test1), sizeof(test1))
+                .code(),
+            Status::NOT_FOUND);
+  test2 = 0;
+  ASSERT_OK(
+      kvs.Get(keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+  EXPECT_EQ(test2, value2);
+
+  // Erase other key
+  kvs.Erase(keys[1]);
+
+  // Verify it was erased
+  EXPECT_EQ(kvs.KeyCount(), 0);
+}
+
+TEST_F(KeyValueStoreTest, MaxKeyLength) {
+  // Erase
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Add some data
+  char key[16] = "123456789abcdef";  // key length 15 (without \0)
+  int value = 1;
+  ASSERT_OK(kvs.Put(key, value));
+
+  // Verify data
+  int test = 0;
+  ASSERT_OK(kvs.Get(key, &test));
+  EXPECT_EQ(test, value);
+
+  // Erase a key
+  kvs.Erase(key);
+
+  // Verify it was erased
+  EXPECT_EQ(kvs.Get(key, &test).code(), Status::NOT_FOUND);
+}
+
+TEST_F(KeyValueStoreTest, LargeBuffers) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Note this assumes that no other keys larger then key0
+  static_assert(sizeof(keys[0]) >= sizeof(keys[1]) &&
+                sizeof(keys[0]) >= sizeof(keys[2]));
+  KvsAttributes kvs_attr(std::strlen(keys[0]), buffer.size());
+
+  // Verify the data will fit in this test partition. This checks that all the
+  // keys chunks will fit and a header for each sector will fit. It requires 1
+  // empty sector also.
+  const size_t kAllChunkSize = kvs_attr.MinPutSize() * keys.size();
+  const size_t kAllSectorHeaderSizes =
+      kvs_attr.SectorHeaderSize() * (test_partition.GetSectorCount() - 1);
+  const size_t kMinSize = kAllChunkSize + kAllSectorHeaderSizes;
+  const size_t kAvailSectorSpace = test_partition.GetSectorSizeBytes() *
+                                   (test_partition.GetSectorCount() - 1);
+  if (kAvailSectorSpace < kMinSize) {
+    LOG_INFO("KVS too small, skipping test.");
+    return;
+  }
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Add and verify
+  for (unsigned add_idx = 0; add_idx < keys.size(); add_idx++) {
+    memset(buffer.data(), add_idx, buffer.size());
+    ASSERT_OK(kvs.Put(keys[add_idx], buffer.data(), buffer.size()));
+    EXPECT_EQ(kvs.KeyCount(), add_idx + 1);
+    for (unsigned verify_idx = 0; verify_idx <= add_idx; verify_idx++) {
+      memset(buffer.data(), 0, buffer.size());
+      ASSERT_OK(kvs.Get(keys[verify_idx], buffer.data(), buffer.size()));
+      for (unsigned i = 0; i < buffer.size(); i++) {
+        EXPECT_EQ(buffer[i], verify_idx);
+      }
+    }
+  }
+
+  // Erase and verify
+  for (unsigned erase_idx = 0; erase_idx < keys.size(); erase_idx++) {
+    ASSERT_OK(kvs.Erase(keys[erase_idx]));
+    EXPECT_EQ(kvs.KeyCount(), keys.size() - erase_idx - 1);
+    for (unsigned verify_idx = 0; verify_idx < keys.size(); verify_idx++) {
+      memset(buffer.data(), 0, buffer.size());
+      if (verify_idx <= erase_idx) {
+        ASSERT_EQ(
+            kvs.Get(keys[verify_idx], buffer.data(), buffer.size()).code(),
+            Status::NOT_FOUND);
+      } else {
+        ASSERT_OK(kvs.Get(keys[verify_idx], buffer.data(), buffer.size()));
+        for (uint32_t i = 0; i < buffer.size(); i++) {
+          EXPECT_EQ(buffer[i], verify_idx);
+        }
+      }
+    }
+  }
+}
+
+TEST_F(KeyValueStoreTest, Enable) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  KvsAttributes kvs_attr(std::strlen(keys[0]), buffer.size());
+
+  // Verify the data will fit in this test partition. This checks that all the
+  // keys chunks will fit and a header for each sector will fit. It requires 1
+  // empty sector also.
+  const size_t kAllChunkSize = kvs_attr.MinPutSize() * keys.size();
+  const size_t kAllSectorHeaderSizes =
+      kvs_attr.SectorHeaderSize() * (test_partition.GetSectorCount() - 1);
+  const size_t kMinSize = kAllChunkSize + kAllSectorHeaderSizes;
+  const size_t kAvailSectorSpace = test_partition.GetSectorSizeBytes() *
+                                   (test_partition.GetSectorCount() - 1);
+  if (kAvailSectorSpace < kMinSize) {
+    LOG_INFO("KVS too small, skipping test.");
+    return;
+  }
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Add some items
+  for (unsigned add_idx = 0; add_idx < keys.size(); add_idx++) {
+    memset(buffer.data(), add_idx, buffer.size());
+    ASSERT_OK(kvs.Put(keys[add_idx], buffer.data(), buffer.size()));
+    EXPECT_EQ(kvs.KeyCount(), add_idx + 1);
+  }
+
+  // Enable different KVS which should be able to properly setup the same map
+  // from what is stored in flash.
+  ASSERT_OK(kvs_local_.Enable());
+  EXPECT_EQ(kvs_local_.KeyCount(), keys.size());
+
+  // Ensure adding to new KVS works
+  uint8_t value = 0xDA;
+  const char* key = "new_key";
+  ASSERT_OK(kvs_local_.Put(key, &value, sizeof(value)));
+  uint8_t test;
+  ASSERT_OK(kvs_local_.Get(key, &test, sizeof(test)));
+  EXPECT_EQ(value, test);
+  EXPECT_EQ(kvs_local_.KeyCount(), keys.size() + 1);
+
+  // Verify previous data
+  for (unsigned verify_idx = 0; verify_idx < keys.size(); verify_idx++) {
+    memset(buffer.data(), 0, buffer.size());
+    ASSERT_OK(kvs_local_.Get(keys[verify_idx], buffer.data(), buffer.size()));
+    for (uint32_t i = 0; i < buffer.size(); i++) {
+      EXPECT_EQ(buffer[i], verify_idx);
+    }
+  }
+}
+
+TEST_F(KeyValueStoreTest, MultiSector) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Calculate number of elements to ensure multiple sectors are required.
+  uint16_t add_count =
+      (test_partition.GetSectorSizeBytes() / buffer.size()) + 1;
+
+  if (kvs.GetMaxKeys() < add_count) {
+    LOG_INFO("Sector size too large, skipping test.");
+    return;  // this chip has very large sectors, test won't work
+  }
+  if (test_partition.GetSectorCount() < 3) {
+    LOG_INFO("Not enough sectors, skipping test.");
+    return;  // need at least 3 sectors for multi-sector test
+  }
+
+  char key[20];
+  for (unsigned add_idx = 0; add_idx < add_count; add_idx++) {
+    memset(buffer.data(), add_idx, buffer.size());
+    snprintf(key, sizeof(key), "key_%u", add_idx);
+    ASSERT_OK(kvs.Put(key, buffer.data(), buffer.size()));
+    EXPECT_EQ(kvs.KeyCount(), add_idx + 1);
+  }
+
+  for (unsigned verify_idx = 0; verify_idx < add_count; verify_idx++) {
+    memset(buffer.data(), 0, buffer.size());
+    snprintf(key, sizeof(key), "key_%u", verify_idx);
+    ASSERT_OK(kvs.Get(key, buffer.data(), buffer.size()));
+    for (uint32_t i = 0; i < buffer.size(); i++) {
+      EXPECT_EQ(buffer[i], verify_idx);
+    }
+  }
+
+  // Check erase
+  for (unsigned erase_idx = 0; erase_idx < add_count; erase_idx++) {
+    snprintf(key, sizeof(key), "key_%u", erase_idx);
+    ASSERT_OK(kvs.Erase(key));
+    EXPECT_EQ(kvs.KeyCount(), add_count - erase_idx - 1);
+  }
+}
+
+TEST_F(KeyValueStoreTest, RewriteValue) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Write first value
+  const uint8_t kValue1 = 0xDA;
+  const uint8_t kValue2 = 0x12;
+  const char* key = "the_key";
+  ASSERT_OK(kvs.Put(key, &kValue1, sizeof(kValue1)));
+
+  // Verify
+  uint8_t value;
+  ASSERT_OK(kvs.Get(key, reinterpret_cast<uint8_t*>(&value), sizeof(value)));
+  EXPECT_EQ(kValue1, value);
+
+  // Write new value for key
+  ASSERT_OK(kvs.Put(key, &kValue2, sizeof(kValue2)));
+
+  // Verify
+  ASSERT_OK(kvs.Get(key, reinterpret_cast<uint8_t*>(&value), sizeof(value)));
+  EXPECT_EQ(kValue2, value);
+
+  // Verify only 1 element exists
+  EXPECT_EQ(kvs.KeyCount(), 1);
+}
+
+TEST_F(KeyValueStoreTest, OffsetRead) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  const char* key = "the_key";
+  constexpr uint8_t kReadSize = 16;  // needs to be a multiple of alignment
+  constexpr uint8_t kTestBufferSize = kReadSize * 10;
+  CHECK_GT(buffer.size(), kTestBufferSize);
+  CHECK_LE(kTestBufferSize, 0xFF);
+
+  // Write the entire buffer
+  for (uint8_t i = 0; i < kTestBufferSize; i++) {
+    buffer[i] = i;
+  }
+  ASSERT_OK(kvs.Put(key, buffer.data(), kTestBufferSize));
+  EXPECT_EQ(kvs.KeyCount(), 1);
+
+  // Read in small chunks and verify
+  for (int i = 0; i < kTestBufferSize / kReadSize; i++) {
+    memset(buffer.data(), 0, buffer.size());
+    ASSERT_OK(kvs.Get(key, buffer.data(), kReadSize, i * kReadSize));
+    for (unsigned j = 0; j < kReadSize; j++) {
+      ASSERT_EQ(buffer[j], j + i * kReadSize);
+    }
+  }
+}
+
+TEST_F(KeyValueStoreTest, MultipleRewrite) {
+  // Write many large buffers to force moving to new sector.
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Calculate number of elements to ensure multiple sectors are required.
+  unsigned add_count =
+      (test_partition.GetSectorSizeBytes() / buffer.size()) + 1;
+
+  const char* key = "the_key";
+  constexpr uint8_t kGoodVal = 0x60;
+  constexpr uint8_t kBadVal = 0xBA;
+  memset(buffer.data(), kBadVal, buffer.size());
+  for (unsigned add_idx = 0; add_idx < add_count; add_idx++) {
+    if (add_idx == add_count - 1) {  // last value
+      memset(buffer.data(), kGoodVal, buffer.size());
+    }
+    ASSERT_OK(kvs.Put(key, buffer.data(), buffer.size()));
+    EXPECT_EQ(kvs.KeyCount(), 1);
+  }
+
+  // Verify
+  memset(buffer.data(), 0, buffer.size());
+  ASSERT_OK(kvs.Get(key, buffer.data(), buffer.size()));
+  for (uint32_t i = 0; i < buffer.size(); i++) {
+    ASSERT_EQ(buffer[i], kGoodVal);
+  }
+}
+
+TEST_F(KeyValueStoreTest, FillSector) {
+  // Write key[0], Write/erase Key[2] multiple times to fill sector check
+  // everything makes sense after.
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  ASSERT_EQ(std::strlen(keys[0]), 8U);  // Easier for alignment
+  ASSERT_EQ(std::strlen(keys[2]), 8U);  // Easier for alignment
+  constexpr size_t kTestDataSize = 8;
+  KvsAttributes kvs_attr(std::strlen(keys[2]), kTestDataSize);
+  int bytes_remaining =
+      test_partition.GetSectorSizeBytes() - kvs_attr.SectorHeaderSize();
+  constexpr uint8_t kKey0Pattern = 0xBA;
+
+  memset(buffer.data(), kKey0Pattern, kvs_attr.DataSize());
+  ASSERT_OK(kvs.Put(keys[0], buffer.data(), kvs_attr.DataSize()));
+  bytes_remaining -= kvs_attr.MinPutSize();
+  memset(buffer.data(), 1, kvs_attr.DataSize());
+  ASSERT_OK(kvs.Put(keys[2], buffer.data(), kvs_attr.DataSize()));
+  bytes_remaining -= kvs_attr.MinPutSize();
+  EXPECT_EQ(kvs.KeyCount(), 2);
+  ASSERT_OK(kvs.Erase(keys[2]));
+  bytes_remaining -= kvs_attr.EraseSize();
+  EXPECT_EQ(kvs.KeyCount(), 1);
+
+  // Intentionally adding erase size to trigger sector cleanup
+  bytes_remaining += kvs_attr.EraseSize();
+  FillKvs(keys[2], bytes_remaining);
+
+  // Verify key[0]
+  memset(buffer.data(), 0, kvs_attr.DataSize());
+  ASSERT_OK(kvs.Get(keys[0], buffer.data(), kvs_attr.DataSize()));
+  for (uint32_t i = 0; i < kvs_attr.DataSize(); i++) {
+    EXPECT_EQ(buffer[i], kKey0Pattern);
+  }
+}
+
+TEST_F(KeyValueStoreTest, Interleaved) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  const uint8_t kValue1 = 0xDA;
+  const uint8_t kValue2 = 0x12;
+  uint8_t value[1];
+  ASSERT_OK(kvs.Put(keys[0], &kValue1, sizeof(kValue1)));
+  EXPECT_EQ(kvs.KeyCount(), 1);
+  ASSERT_OK(kvs.Erase(keys[0]));
+  EXPECT_EQ(kvs.Get(keys[0], value, sizeof(value)), Status::NOT_FOUND);
+  ASSERT_OK(kvs.Put(keys[1], &kValue1, sizeof(kValue1)));
+  ASSERT_OK(kvs.Put(keys[2], &kValue2, sizeof(kValue2)));
+  ASSERT_OK(kvs.Erase(keys[1]));
+  EXPECT_OK(kvs.Get(keys[2], value, sizeof(value)));
+  EXPECT_EQ(kValue2, value[0]);
+
+  EXPECT_EQ(kvs.KeyCount(), 1);
+}
+
+TEST_F(KeyValueStoreTest, BadCrc) {
+  static constexpr uint32_t kTestPattern = 0xBAD0301f;
+  // clang-format off
+  // There is a top and bottom because for each because we don't want to write
+  // the erase 0xFF, especially on encrypted flash.
+  static constexpr uint8_t kKvsTestDataAligned1Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x01, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned1Bottom[] = {
+      0xAA, 0x55, 0xBA, 0xDD, 0x00, 0x00, 0x18, 0x00,  // header (BAD CRC)
+      0x54, 0x65, 0x73, 0x74, 0x4B, 0x65, 0x79, 0x31,  // Key (keys[0])
+      0xDA,                                            // Value
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // Header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32,                          // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA};                         // Value
+  static constexpr uint8_t kKvsTestDataAligned2Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x02, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned2Bottom[] = {
+      0xAA, 0x55, 0xBA, 0xDD, 0x00, 0x00, 0x18, 0x00,  // header (BAD CRC)
+      0x54, 0x65, 0x73, 0x74, 0x4B, 0x65, 0x79, 0x31,  // Key (keys[0])
+      0xDA, 0x00,                                      // Value + padding
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // Header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32,                          // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA};                         // Value
+  static constexpr uint8_t kKvsTestDataAligned8Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x08, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned8Bottom[] = {
+      0xAA, 0x55, 0xBA, 0xDD, 0x00, 0x00, 0x18, 0x00,  // header (BAD CRC)
+      0x54, 0x65, 0x73, 0x74, 0x4B, 0x65, 0x79, 0x31,  // Key (keys[0])
+      0xDA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32, 0x00, 0x00, 0x00, 0x00,  // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+  };
+  static constexpr uint8_t kKvsTestDataAligned16Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x10, 0x00, 0xFF, 0xFF,  // Sector Header
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+  };
+  static constexpr uint8_t kKvsTestDataAligned16Bottom[] = {
+      0xAA, 0x55, 0xBA, 0xDD, 0x00, 0x00, 0x18, 0x00,  // header (BAD CRC)
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0x54, 0x65, 0x73, 0x74, 0x4B, 0x65, 0x79, 0x31,  // Key (keys[0])
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0xDA, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // header (GOOD CRC)
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0x4B, 0x65, 0x79, 0x32, 0x00, 0x00, 0x00, 0x00,  // Key (keys[1])
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0x1F, 0x30, 0xD0, 0xBA, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+  };
+  // clang-format on
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+
+  // We don't actually care about the size values provided, since we are only
+  // using kvs_attr to get Sector Size
+  KvsAttributes kvs_attr(8, 8);
+  if (test_partition.GetAlignmentBytes() == 1) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned1Top, sizeof(kKvsTestDataAligned1Top)));
+    ASSERT_OK(test_partition.Write(kvs_attr.SectorHeaderSize(),
+                                   kKvsTestDataAligned1Bottom,
+                                   sizeof(kKvsTestDataAligned1Bottom)));
+  } else if (test_partition.GetAlignmentBytes() == 2) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned2Top, sizeof(kKvsTestDataAligned2Top)));
+    ASSERT_OK(test_partition.Write(kvs_attr.SectorHeaderSize(),
+                                   kKvsTestDataAligned2Bottom,
+                                   sizeof(kKvsTestDataAligned2Bottom)));
+  } else if (test_partition.GetAlignmentBytes() == 8) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned8Top, sizeof(kKvsTestDataAligned8Top)));
+    ASSERT_OK(test_partition.Write(kvs_attr.SectorHeaderSize(),
+                                   kKvsTestDataAligned8Bottom,
+                                   sizeof(kKvsTestDataAligned8Bottom)));
+  } else if (test_partition.GetAlignmentBytes() == 16) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned16Top, sizeof(kKvsTestDataAligned16Top)));
+    ASSERT_OK(test_partition.Write(kvs_attr.SectorHeaderSize(),
+                                   kKvsTestDataAligned16Bottom,
+                                   sizeof(kKvsTestDataAligned16Bottom)));
+  } else {
+    LOG_ERROR("Test only supports 1, 2, 8 and 16 byte alignments.");
+    ASSERT_OK(false);
+  }
+
+  EXPECT_EQ(kvs_local_.Enable(), Status::OK);
+  EXPECT_TRUE(kvs_local_.IsEnabled());
+
+  EXPECT_EQ(kvs_local_.Get(keys[0], buffer.data(), 1), Status::DATA_LOSS);
+
+  // Value with correct CRC should still be available.
+  uint32_t test2 = 0;
+  ASSERT_OK(kvs_local_.Get(
+      keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+  EXPECT_EQ(kTestPattern, test2);
+
+  // Test rewriting over corrupted data.
+  ASSERT_OK(kvs_local_.Put(keys[0], kTestPattern));
+  test2 = 0;
+  EXPECT_OK(kvs_local_.Get(keys[0], &test2));
+  EXPECT_EQ(kTestPattern, test2);
+
+  // Check correct when re-enabled
+  kvs_local_.Disable();
+  EXPECT_EQ(kvs_local_.Enable(), Status::OK);
+  test2 = 0;
+  EXPECT_OK(kvs_local_.Get(keys[0], &test2));
+  EXPECT_EQ(kTestPattern, test2);
+}
+
+TEST_F(KeyValueStoreTest, TestVersion2) {
+  static constexpr uint32_t kTestPattern = 0xBAD0301f;
+  // Since this test is not run on encypted flash, we can write the clean
+  // pending flag for just this test.
+  static constexpr uint8_t kKvsTestDataAligned1[] = {
+      0xCD, 0xAB, 0x02, 0x00, 0x00, 0x00, 0xFF, 0xFF,  // Sector Header
+      0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF,  // Clean pending flag
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // Header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32,                          // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA};                         // Value
+
+  if (test_partition.GetAlignmentBytes() == 1) {
+    // Test only runs on 1 byte alignment partitions
+    test_partition.Erase(0, test_partition.GetSectorCount());
+    test_partition.Write(0, kKvsTestDataAligned1, sizeof(kKvsTestDataAligned1));
+    EXPECT_OK(kvs_local_.Enable());
+    uint32_t test2 = 0;
+    ASSERT_OK(kvs_local_.Get(
+        keys[1], reinterpret_cast<uint8_t*>(&test2), sizeof(test2)));
+    EXPECT_EQ(kTestPattern, test2);
+  }
+}
+
+TEST_F(KeyValueStoreTest, ReEnable) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  kvs.Disable();
+
+  EXPECT_OK(kvs_local_.Enable());
+  // Write value
+  const uint8_t kValue = 0xDA;
+  ASSERT_OK(kvs_local_.Put(keys[0], &kValue, sizeof(kValue)));
+  uint8_t value;
+  ASSERT_OK(kvs_local_.Get(
+      keys[0], reinterpret_cast<uint8_t*>(&value), sizeof(value)));
+
+  // Verify
+  EXPECT_EQ(kValue, value);
+}
+
+TEST_F(KeyValueStoreTest, Erase) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Write value
+  const uint8_t kValue = 0xDA;
+  ASSERT_OK(kvs.Put(keys[0], &kValue, sizeof(kValue)));
+
+  ASSERT_OK(kvs.Erase(keys[0]));
+  uint8_t value[1];
+  ASSERT_EQ(kvs.Get(keys[0], value, sizeof(value)), Status::NOT_FOUND);
+
+  // Reset KVS, ensure captured at enable
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  ASSERT_EQ(kvs.Get(keys[0], value, sizeof(value)), Status::NOT_FOUND);
+}
+
+TEST_F(KeyValueStoreTest, TemplatedPutAndGet) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  // Store a value with the convenience method.
+  const uint32_t kValue = 0x12345678;
+  ASSERT_OK(kvs.Put(keys[0], kValue));
+
+  // Read it back with the other convenience method.
+  uint32_t value;
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(kValue, value);
+
+  // Make sure we cannot get something where size isn't what we expect
+  const uint8_t kSmallValue = 0xBA;
+  uint8_t small_value = kSmallValue;
+  ASSERT_EQ(kvs.Get(keys[0], &small_value), Status::INVALID_ARGUMENT);
+  ASSERT_EQ(small_value, kSmallValue);
+}
+
+TEST_F(KeyValueStoreTest, SameValueRewrite) {
+  static constexpr uint32_t kTestPattern = 0xBAD0301f;
+  // clang-format off
+  static constexpr uint8_t kKvsTestDataAligned1Top[] = {
+      0xCD, 0xAB, 0x02, 0x00, 0x00, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned1Bottom[] = {
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // Header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32,                          // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA};                         // Value
+  static constexpr uint8_t kKvsTestDataAligned2Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x02, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned2Bottom[] = {
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // Header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32,                          // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA};                         // Value
+  static constexpr uint8_t kKvsTestDataAligned8Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x08, 0x00, 0xFF, 0xFF,  // Sector Header
+  };
+  static constexpr uint8_t kKvsTestDataAligned8Bottom[] = {
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // header (GOOD CRC)
+      0x4B, 0x65, 0x79, 0x32, 0x00, 0x00, 0x00, 0x00,  // Key (keys[1])
+      0x1F, 0x30, 0xD0, 0xBA, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+  };
+  static constexpr uint8_t kKvsTestDataAligned16Top[] = {
+      0xCD, 0xAB, 0x03, 0x00, 0x10, 0x00, 0xFF, 0xFF,  // Sector Header
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+  };
+  static constexpr uint8_t kKvsTestDataAligned16Bottom[] = {
+      0xAA, 0x55, 0xB5, 0x87, 0x00, 0x00, 0x44, 0x00,  // header (GOOD CRC)
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0x4B, 0x65, 0x79, 0x32, 0x00, 0x00, 0x00, 0x00,  // Key (keys[1])
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+      0x1F, 0x30, 0xD0, 0xBA, 0x00, 0x00, 0x00, 0x00,  // Value + padding
+      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  // Alignment to 16
+  };
+  // clang-format on
+
+  ASSERT_OK(test_partition.Erase(0, test_partition.GetSectorCount()));
+  // We don't actually care about the size values provided, since we are only
+  // using kvs_attr to get Sector Size
+  KvsAttributes kvs_attr(8, 8);
+  pw::FlashPartition::Address address = kvs_attr.SectorHeaderSize();
+  if (test_partition.GetAlignmentBytes() == 1) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned1Top, sizeof(kKvsTestDataAligned1Top)));
+    ASSERT_OK(test_partition.Write(address,
+                                   kKvsTestDataAligned1Bottom,
+                                   sizeof(kKvsTestDataAligned1Bottom)));
+    address += sizeof(kKvsTestDataAligned1Bottom);
+  } else if (test_partition.GetAlignmentBytes() == 2) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned2Top, sizeof(kKvsTestDataAligned2Top)));
+    ASSERT_OK(test_partition.Write(address,
+                                   kKvsTestDataAligned2Bottom,
+                                   sizeof(kKvsTestDataAligned2Bottom)));
+    address += sizeof(kKvsTestDataAligned2Bottom);
+  } else if (test_partition.GetAlignmentBytes() == 8) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned8Top, sizeof(kKvsTestDataAligned8Top)));
+    ASSERT_OK(test_partition.Write(address,
+                                   kKvsTestDataAligned8Bottom,
+                                   sizeof(kKvsTestDataAligned8Bottom)));
+    address += sizeof(kKvsTestDataAligned8Bottom);
+  } else if (test_partition.GetAlignmentBytes() == 16) {
+    ASSERT_OK(test_partition.Write(
+        0, kKvsTestDataAligned16Top, sizeof(kKvsTestDataAligned16Top)));
+    ASSERT_OK(test_partition.Write(address,
+                                   kKvsTestDataAligned16Bottom,
+                                   sizeof(kKvsTestDataAligned16Bottom)));
+    address += sizeof(kKvsTestDataAligned16Bottom);
+  } else {
+    LOG_ERROR("Test only supports 1, 2, 8 and 16 byte alignments.");
+    ASSERT_EQ(true, false);
+  }
+
+  ASSERT_OK(kvs_local_.Enable());
+  EXPECT_TRUE(kvs_local_.IsEnabled());
+
+  // Put in same key/value pair
+  ASSERT_OK(kvs_local_.Put(keys[1], kTestPattern));
+
+  bool is_erased = false;
+  ASSERT_OK(test_partition.IsChunkErased(
+      address, test_partition.GetAlignmentBytes(), &is_erased));
+  EXPECT_EQ(is_erased, true);
+}
+
+// This test is derived from bug that was discovered. Testing this corner case
+// relies on creating a new key-value just under the size that is left over in
+// the sector.
+TEST_F(KeyValueStoreTest, FillSector2) {
+  if (test_partition.GetSectorCount() < 3) {
+    LOG_INFO("Not enough sectors, skipping test.");
+    return;  // need at least 3 sectors
+  }
+
+  // Reset KVS
+  kvs.Disable();
+  test_partition.Erase(0, test_partition.GetSectorCount());
+  ASSERT_OK(kvs.Enable());
+
+  // Start of by filling flash sector to near full
+  constexpr int kHalfBufferSize = buffer.size() / 2;
+  const int kSizeToFill = test_partition.GetSectorSizeBytes() - kHalfBufferSize;
+  constexpr size_t kTestDataSize = 8;
+  KvsAttributes kvs_attr(std::strlen(keys[2]), kTestDataSize);
+
+  FillKvs(keys[2], kSizeToFill);
+
+  // Find out how much space is remaining for new key-value and confirm it
+  // makes sense.
+  size_t new_keyvalue_size = 0;
+  size_t alignment = test_partition.GetAlignmentBytes();
+  // Starts on second sector since it will try to keep first sector free
+  pw::FlashPartition::Address read_address =
+      2 * test_partition.GetSectorSizeBytes() - alignment;
+  for (; read_address > 0; read_address -= alignment) {
+    bool is_erased = false;
+    ASSERT_OK(
+        test_partition.IsChunkErased(read_address, alignment, &is_erased));
+    if (is_erased) {
+      new_keyvalue_size += alignment;
+    } else {
+      break;
+    }
+  }
+
+  size_t expected_remaining = test_partition.GetSectorSizeBytes() -
+                              kvs_attr.SectorHeaderSize() - kSizeToFill;
+  ASSERT_EQ(new_keyvalue_size, expected_remaining);
+
+  const char* kNewKey = "NewKey";
+  constexpr size_t kValueLessThanChunkHeaderSize = 2;
+  constexpr uint8_t kTestPattern = 0xBA;
+  new_keyvalue_size -= kValueLessThanChunkHeaderSize;
+  memset(buffer.data(), kTestPattern, new_keyvalue_size);
+  ASSERT_OK(kvs.Put(kNewKey, buffer.data(), new_keyvalue_size));
+
+  // In failed corner case, adding new key is deceptively successful. It isn't
+  // until KVS is disabled and reenabled that issue can be detected.
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  // Might as well check that new key-value is what we expect it to be
+  ASSERT_OK(kvs.Get(kNewKey, buffer.data(), new_keyvalue_size));
+  for (size_t i = 0; i < new_keyvalue_size; i++) {
+    EXPECT_EQ(buffer[i], kTestPattern);
+  }
+}
+
+TEST_F(KeyValueStoreTest, GetValueSizeTests) {
+  constexpr uint16_t kSizeOfValueToFill = 20U;
+  constexpr uint8_t kKey0Pattern = 0xBA;
+  uint16_t value_size = 0;
+  // Start off with disabled KVS
+  kvs.Disable();
+
+  // Try getting value when KVS is disabled, expect failure
+  EXPECT_EQ(kvs.GetValueSize(keys[0], &value_size),
+            Status::FAILED_PRECONDITION);
+
+  // Reset KVS
+  test_partition.Erase(0, test_partition.GetSectorCount());
+  ASSERT_OK(kvs.Enable());
+
+  // Try some case that are expected to fail
+  ASSERT_EQ(kvs.GetValueSize(keys[0], &value_size), Status::NOT_FOUND);
+  ASSERT_EQ(kvs.GetValueSize(nullptr, &value_size), Status::INVALID_ARGUMENT);
+  ASSERT_EQ(kvs.GetValueSize(keys[0], nullptr), Status::INVALID_ARGUMENT);
+
+  // Add key[0] and test we get the right value size for it.
+  memset(buffer.data(), kKey0Pattern, kSizeOfValueToFill);
+  ASSERT_OK(kvs.Put(keys[0], buffer.data(), kSizeOfValueToFill));
+  ASSERT_OK(kvs.GetValueSize(keys[0], &value_size));
+  ASSERT_EQ(value_size, kSizeOfValueToFill);
+
+  // Verify after erase key is not found
+  ASSERT_OK(kvs.Erase(keys[0]));
+  ASSERT_EQ(kvs.GetValueSize(keys[0], &value_size), Status::NOT_FOUND);
+}
+
+TEST_F(KeyValueStoreTest, CanFitEntryTests) {
+  // Reset KVS
+  kvs.Disable();
+  test_partition.Erase(0, test_partition.GetSectorCount());
+  ASSERT_OK(kvs.Enable());
+
+  // Get exactly the number of bytes that can fit in the space remaining for
+  // a large value, accounting for alignment.
+  constexpr uint16_t kTestKeySize = 2;
+  size_t space_remaining =
+      test_partition.GetSectorSizeBytes()                //
+      - RoundUpForAlignment(KeyValueStore::kHeaderSize)  // Sector Header
+      - RoundUpForAlignment(KeyValueStore::kHeaderSize)  // Cleaning Header
+      - RoundUpForAlignment(KeyValueStore::kHeaderSize)  // Chunk Header
+      - RoundUpForAlignment(kTestKeySize);
+  space_remaining -= test_partition.GetAlignmentBytes() / 2;
+  space_remaining = RoundUpForAlignment(space_remaining);
+
+  EXPECT_TRUE(kvs.CanFitEntry(kTestKeySize, space_remaining));
+  EXPECT_FALSE(kvs.CanFitEntry(kTestKeySize, space_remaining + 1));
+}
+
+TEST_F(KeyValueStoreTest, DifferentValueSameCrc16) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+  const char kKey[] = "k";
+  // With the key and our CRC16 algorithm these both have CRC of 0x82AE
+  // Given they are the same size and same key, the KVS will need to check
+  // the actual bits to know they are different.
+  const char kValue1[] = {'d', 'a', 't'};
+  const char kValue2[] = {'u', 'c', 'd'};
+
+  // Verify the CRC matches
+  ASSERT_EQ(CalcKvsCrc(kKey, kValue1, sizeof(kValue1)),
+            CalcKvsCrc(kKey, kValue2, sizeof(kValue2)));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  ASSERT_OK(kvs.Put(kKey, kValue1));
+
+  // Now try to rewrite with the similar value.
+  ASSERT_OK(kvs.Put(kKey, kValue2));
+
+  // Read it back and check it is correct
+  char value[3];
+  ASSERT_OK(kvs.Get(kKey, value, sizeof(value)));
+  ASSERT_EQ(memcmp(value, kValue2, sizeof(value)), 0);
+}
+
+TEST_F(KeyValueStoreTest, CallingEraseTwice) {
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+
+  const uint8_t kValue = 0xDA;
+  ASSERT_OK(kvs.Put(keys[0], &kValue, sizeof(kValue)));
+  ASSERT_OK(kvs.Erase(keys[0]));
+  uint16_t crc = CalcTestPartitionCrc();
+  EXPECT_EQ(kvs.Erase(keys[0]), Status::NOT_FOUND);
+  // Verify the flash has not changed
+  EXPECT_EQ(crc, CalcTestPartitionCrc());
+}
+
+void __attribute__((noinline)) StackHeavyPartialClean() {
+  CHECK_GE(test_partition.GetSectorCount(), 2);
+  FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+  FlashSubPartition test_partition_sector2(&test_partition, 1, 1);
+
+  KeyValueStore kvs1(&test_partition_sector1);
+  KeyValueStore kvs2(&test_partition_sector2);
+
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  ASSERT_OK(kvs1.Enable());
+  ASSERT_OK(kvs2.Enable());
+
+  int values1[3] = {100, 101, 102};
+  ASSERT_OK(kvs1.Put(keys[0], values1[0]));
+  ASSERT_OK(kvs1.Put(keys[1], values1[1]));
+  ASSERT_OK(kvs1.Put(keys[2], values1[2]));
+
+  int values2[3] = {200, 201, 202};
+  ASSERT_OK(kvs2.Put(keys[0], values2[0]));
+  ASSERT_OK(kvs2.Put(keys[1], values2[1]));
+  ASSERT_OK(kvs2.Erase(keys[1]));
+
+  kvs1.Disable();
+  kvs2.Disable();
+
+  // Key 0 is value1 in first sector, value 2 in second
+  // Key 1 is value1 in first sector, erased in second
+  // key 2 is only in first sector
+
+  uint64_t mark_clean_count = 5;
+  ASSERT_OK(PaddedWrite(&test_partition_sector1,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  int value;
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values2[0], value);
+  ASSERT_EQ(kvs.Get(keys[1], &value), Status::NOT_FOUND);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values1[2], value);
+
+  if (test_partition.GetSectorCount() == 2) {
+    EXPECT_EQ(kvs.PendingCleanCount(), 0u);
+    // Has forced a clean, mark again for next test
+    return;  // Not enough sectors to test 2 partial cleans.
+  } else {
+    EXPECT_EQ(kvs.PendingCleanCount(), 1u);
+  }
+
+  mark_clean_count--;
+  ASSERT_OK(PaddedWrite(&test_partition_sector2,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  EXPECT_EQ(kvs.PendingCleanCount(), 2u);
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values1[0], value);
+  ASSERT_OK(kvs.Get(keys[1], &value));
+  ASSERT_EQ(values1[1], value);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values1[2], value);
+}
+
+TEST_F(KeyValueStoreTest, PartialClean) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore) * 2) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  StackHeavyPartialClean();
+}
+
+void __attribute__((noinline)) StackHeavyCleanAll() {
+  CHECK_GE(test_partition.GetSectorCount(), 2);
+  FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+
+  KeyValueStore kvs1(&test_partition_sector1);
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  ASSERT_OK(kvs1.Enable());
+
+  int values1[3] = {100, 101, 102};
+  ASSERT_OK(kvs1.Put(keys[0], values1[0]));
+  ASSERT_OK(kvs1.Put(keys[1], values1[1]));
+  ASSERT_OK(kvs1.Put(keys[2], values1[2] - 100));  //  force a rewrite
+  ASSERT_OK(kvs1.Put(keys[2], values1[2]));
+
+  kvs1.Disable();
+
+  uint64_t mark_clean_count = 5;
+  ASSERT_OK(PaddedWrite(&test_partition_sector1,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+
+  // Reset KVS
+  kvs.Disable();
+  ASSERT_OK(kvs.Enable());
+  int value;
+  EXPECT_EQ(kvs.PendingCleanCount(), 1u);
+  ASSERT_OK(kvs.CleanAll());
+  EXPECT_EQ(kvs.PendingCleanCount(), 0u);
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values1[0], value);
+  ASSERT_OK(kvs.Get(keys[1], &value));
+  ASSERT_EQ(values1[1], value);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values1[2], value);
+}
+
+TEST_F(KeyValueStoreTest, CleanAll) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore) * 1) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  StackHeavyCleanAll();
+}
+
+void __attribute__((noinline)) StackHeavyPartialCleanLargeCounts() {
+  CHECK_GE(test_partition.GetSectorCount(), 2);
+  FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+  FlashSubPartition test_partition_sector2(&test_partition, 1, 1);
+
+  KeyValueStore kvs1(&test_partition_sector1);
+  KeyValueStore kvs2(&test_partition_sector2);
+
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  ASSERT_OK(kvs1.Enable());
+  ASSERT_OK(kvs2.Enable());
+
+  int values1[3] = {100, 101, 102};
+  ASSERT_OK(kvs1.Put(keys[0], values1[0]));
+  ASSERT_OK(kvs1.Put(keys[1], values1[1]));
+  ASSERT_OK(kvs1.Put(keys[2], values1[2]));
+
+  int values2[3] = {200, 201, 202};
+  ASSERT_OK(kvs2.Put(keys[0], values2[0]));
+  ASSERT_OK(kvs2.Put(keys[1], values2[1]));
+  ASSERT_OK(kvs2.Erase(keys[1]));
+
+  kvs1.Disable();
+  kvs2.Disable();
+  kvs.Disable();
+
+  // Key 0 is value1 in first sector, value 2 in second
+  // Key 1 is value1 in first sector, erased in second
+  // key 2 is only in first sector
+
+  uint64_t mark_clean_count = 4569877515;
+  ASSERT_OK(PaddedWrite(&test_partition_sector1,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+
+  // Reset KVS
+  ASSERT_OK(kvs.Enable());
+  int value;
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values2[0], value);
+  ASSERT_EQ(kvs.Get(keys[1], &value), Status::NOT_FOUND);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values1[2], value);
+
+  if (test_partition.GetSectorCount() == 2) {
+    EXPECT_EQ(kvs.PendingCleanCount(), 0u);
+    // Has forced a clean, mark again for next test
+    // Has forced a clean, mark again for next test
+    return;  // Not enough sectors to test 2 partial cleans.
+  } else {
+    EXPECT_EQ(kvs.PendingCleanCount(), 1u);
+  }
+  kvs.Disable();
+
+  mark_clean_count--;
+  ASSERT_OK(PaddedWrite(&test_partition_sector2,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+  // Reset KVS
+  ASSERT_OK(kvs.Enable());
+  EXPECT_EQ(kvs.PendingCleanCount(), 2u);
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values1[0], value);
+  ASSERT_OK(kvs.Get(keys[1], &value));
+  ASSERT_EQ(values1[1], value);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values1[2], value);
+}
+
+TEST_F(KeyValueStoreTest, PartialCleanLargeCounts) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore) * 2) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  StackHeavyPartialCleanLargeCounts();
+}
+
+void __attribute__((noinline)) StackHeavyRecoverNoFreeSectors() {
+  CHECK_GE(test_partition.GetSectorCount(), 2);
+  FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+  FlashSubPartition test_partition_sector2(&test_partition, 1, 1);
+  FlashSubPartition test_partition_both(&test_partition, 0, 2);
+
+  KeyValueStore kvs1(&test_partition_sector1);
+  KeyValueStore kvs2(&test_partition_sector2);
+  KeyValueStore kvs_both(&test_partition_both);
+
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  ASSERT_OK(kvs1.Enable());
+  ASSERT_OK(kvs2.Enable());
+
+  int values[3] = {100, 101};
+  ASSERT_OK(kvs1.Put(keys[0], values[0]));
+  ASSERT_FALSE(kvs1.HasEmptySector());
+  ASSERT_OK(kvs2.Put(keys[1], values[1]));
+  ASSERT_FALSE(kvs2.HasEmptySector());
+
+  kvs1.Disable();
+  kvs2.Disable();
+
+  // Reset KVS
+  ASSERT_OK(kvs_both.Enable());
+  ASSERT_TRUE(kvs_both.HasEmptySector());
+  int value;
+  ASSERT_OK(kvs_both.Get(keys[0], &value));
+  ASSERT_EQ(values[0], value);
+  ASSERT_OK(kvs_both.Get(keys[1], &value));
+  ASSERT_EQ(values[1], value);
+}
+
+TEST_F(KeyValueStoreTest, RecoverNoFreeSectors) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore) * 3) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  StackHeavyRecoverNoFreeSectors();
+}
+
+void __attribute__((noinline)) StackHeavyCleanOneSector() {
+  CHECK_GE(test_partition.GetSectorCount(), 2);
+  FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+  FlashSubPartition test_partition_sector2(&test_partition, 1, 1);
+
+  KeyValueStore kvs1(&test_partition_sector1);
+
+  test_partition.Erase(0, test_partition.GetSectorCount());
+
+  ASSERT_OK(kvs1.Enable());
+
+  int values[3] = {100, 101, 102};
+  ASSERT_OK(kvs1.Put(keys[0], values[0]));
+  ASSERT_OK(kvs1.Put(keys[1], values[1]));
+  ASSERT_OK(kvs1.Put(keys[2], values[2]));
+
+  kvs1.Disable();
+  kvs.Disable();
+
+  uint64_t mark_clean_count = 1;
+  ASSERT_OK(PaddedWrite(&test_partition_sector1,
+                        RoundUpForAlignment(KeyValueStore::kHeaderSize),
+                        reinterpret_cast<uint8_t*>(&mark_clean_count),
+                        sizeof(uint64_t)));
+
+  // Reset KVS
+  ASSERT_OK(kvs.Enable());
+
+  EXPECT_EQ(kvs.PendingCleanCount(), 1u);
+
+  bool all_sectors_have_been_cleaned = false;
+  ASSERT_OK(kvs.CleanOneSector(&all_sectors_have_been_cleaned));
+  EXPECT_EQ(all_sectors_have_been_cleaned, true);
+  EXPECT_EQ(kvs.PendingCleanCount(), 0u);
+  ASSERT_OK(kvs.CleanOneSector(&all_sectors_have_been_cleaned));
+  EXPECT_EQ(all_sectors_have_been_cleaned, true);
+  int value;
+  ASSERT_OK(kvs.Get(keys[0], &value));
+  ASSERT_EQ(values[0], value);
+  ASSERT_OK(kvs.Get(keys[1], &value));
+  ASSERT_EQ(values[1], value);
+  ASSERT_OK(kvs.Get(keys[2], &value));
+  ASSERT_EQ(values[2], value);
+}
+
+TEST_F(KeyValueStoreTest, CleanOneSector) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore)) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  StackHeavyCleanOneSector();
+}
+
+#if USE_MEMORY_BUFFER
+
+TEST_F(KeyValueStoreTest, LargePartition) {
+  if (CurrentTaskStackFree() < sizeof(KeyValueStore)) {
+    LOG_ERROR("Not enough stack for test, skipping");
+    return;
+  }
+  large_test_partition.Erase(0, large_test_partition.GetSectorCount());
+  KeyValueStore large_kvs(&large_test_partition);
+  // Reset KVS
+  large_kvs.Disable();
+  ASSERT_OK(large_kvs.Enable());
+
+  const uint8_t kValue1 = 0xDA;
+  const uint8_t kValue2 = 0x12;
+  uint8_t value[1];
+  ASSERT_OK(large_kvs.Put(keys[0], &kValue1, sizeof(kValue1)));
+  EXPECT_EQ(large_kvs.KeyCount(), 1);
+  ASSERT_OK(large_kvs.Erase(keys[0]));
+  EXPECT_EQ(large_kvs.Get(keys[0], value, sizeof(value)), Status::NOT_FOUND);
+  ASSERT_OK(large_kvs.Put(keys[1], &kValue1, sizeof(kValue1)));
+  ASSERT_OK(large_kvs.Put(keys[2], &kValue2, sizeof(kValue2)));
+  ASSERT_OK(large_kvs.Erase(keys[1]));
+  EXPECT_OK(large_kvs.Get(keys[2], value, sizeof(value)));
+  EXPECT_EQ(kValue2, value[0]);
+  ASSERT_EQ(large_kvs.Get(keys[1], &value), Status::NOT_FOUND);
+  EXPECT_EQ(large_kvs.KeyCount(), 1);
+}
+#endif  // USE_MEMORY_BUFFER
+
+}  // namespace pw
diff --git a/pw_kvs/public/pw_kvs/flash.h b/pw_kvs/public/pw_kvs/flash.h
new file mode 100644
index 0000000..5cb80cd
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/flash.h
@@ -0,0 +1,33 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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 "pw_kvs/devices/flash_memory.h"
+
+namespace pw {
+
+// Writes a buffer which is not guaranteed to be aligned, pads remaining
+// bytes with 0.
+Status PaddedWrite(FlashPartition* partition,
+                   FlashPartition::Address address,
+                   const uint8_t* buffer,
+                   uint16_t size);
+
+// Read into a buffer when size is not guaranteed to be aligned.
+Status UnalignedRead(FlashPartition* partition,
+                     uint8_t* buffer,
+                     FlashPartition::Address address,
+                     uint16_t size);
+
+}  // namespace pw
diff --git a/pw_kvs/public/pw_kvs/flash_memory.h b/pw_kvs/public/pw_kvs/flash_memory.h
new file mode 100644
index 0000000..707f128
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/flash_memory.h
@@ -0,0 +1,377 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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 <algorithm>
+
+#include "pw_kvs/assert.h"
+#include "pw_kvs/logging.h"
+#include "pw_kvs/peripherals/partition_table_entry.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/status_macros.h"
+
+namespace pw {
+class FlashMemory {
+ public:
+  // The flash address is in the range of: 0 to FlashSize.
+  typedef uint32_t Address;
+  constexpr FlashMemory(uint32_t sector_size,
+                        uint32_t sector_count,
+                        uint8_t alignment,
+                        uint32_t start_address = 0,
+                        uint32_t sector_start = 0,
+                        uint8_t erased_memory_content = 0xFF)
+      : sector_size_(sector_size),
+        flash_sector_count_(sector_count),
+        alignment_(alignment),
+        start_address_(start_address),
+        sector_start_(sector_start),
+        erased_memory_content_(erased_memory_content) {}
+
+  virtual Status Enable() = 0;
+  virtual Status Disable() = 0;
+  virtual bool IsEnabled() const = 0;
+  virtual Status SelfTest() { return Status::UNIMPLEMENTED; }
+
+  // Erase num_sectors starting at a given address. Blocking call.
+  // Address should be on a sector boundary.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or sector count is invalid.
+  //          UNKNOWN, on HAL error
+  virtual Status Erase(Address flash_address, uint32_t num_sectors) = 0;
+
+  // Reads bytes from flash into buffer. Blocking call.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  virtual Status Read(uint8_t* destination_ram_address,
+                      Address source_flash_address,
+                      uint32_t len) = 0;
+
+  // Writes bytes to flash. Blocking call.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  virtual Status Write(Address destination_flash_address,
+                       const uint8_t* source_ram_address,
+                       uint32_t len) = 0;
+
+  // Convert an Address to an MCU pointer, this can be used for memory
+  // mapped reads. Return NULL if the memory is not memory mapped.
+  virtual uint8_t* FlashAddressToMcuAddress(Address address) const {
+    return nullptr;
+  }
+
+  // GetStartSector() is useful for FlashMemory instances where the
+  // sector start is not 0. (ex.: cases where there are portions of flash
+  // that should be handled independently).
+  constexpr uint32_t GetStartSector() const { return sector_start_; }
+  constexpr uint32_t GetSectorSizeBytes() const { return sector_size_; }
+  constexpr uint32_t GetSectorCount() const { return flash_sector_count_; }
+  constexpr uint8_t GetAlignmentBytes() const { return alignment_; }
+  constexpr uint32_t GetSizeBytes() const {
+    return sector_size_ * flash_sector_count_;
+  }
+  // Address of the start of flash (the address of sector 0)
+  constexpr uint32_t GetStartAddress() const { return start_address_; }
+  constexpr uint8_t GetErasedMemoryContent() const {
+    return erased_memory_content_;
+  }
+
+ private:
+  const uint32_t sector_size_;
+  const uint32_t flash_sector_count_;
+  const uint8_t alignment_;
+  const uint32_t start_address_;
+  const uint32_t sector_start_;
+  const uint8_t erased_memory_content_;
+};
+
+// Exposes a sub-sector sized region of flash memory that cannot be erased.
+// It can be thought of as one pseudo-sector that is sized exactly as provided.
+//
+// TODO(b/117553777): This makes a little more sense as a SubSectorPartition,
+// but PartitionTableEntry currently assumes all partitions fill entire sectors.
+// Revisit when PartitionTable is refactored.
+class FlashMemorySubSector : public FlashMemory {
+ public:
+  constexpr FlashMemorySubSector(FlashMemory* flash,
+                                 uint32_t start_address,
+                                 uint32_t size)
+      : FlashMemory(size,
+                    1,  // Round up to "1" sector.
+                    flash->GetAlignmentBytes(),
+                    start_address,
+                    // Calculate the sector for this start address.
+                    flash->GetStartSector() +
+                        ((start_address - flash->GetStartAddress()) /
+                         flash->GetSectorSizeBytes())),
+        flash_(*CHECK_NOTNULL(flash)),
+        base_offset_(start_address - flash->GetStartAddress()) {
+    // Make sure we're not specifying a region of flash larger than
+    // that which the underlying FlashMemory supports.
+    CHECK(start_address >= flash->GetStartAddress());
+    CHECK(size <= flash->GetSectorSizeBytes());
+    CHECK(start_address + size <=
+          flash->GetStartAddress() + flash->GetSizeBytes());
+    CHECK_EQ(0, start_address % flash->GetAlignmentBytes());
+    CHECK_EQ(0, size % flash->GetAlignmentBytes());
+  }
+
+  Status Enable() override { return flash_.Enable(); }
+  Status Disable() override { return flash_.Disable(); }
+  bool IsEnabled() const override { return flash_.IsEnabled(); }
+  Status SelfTest() override { return flash_.SelfTest(); }
+
+  Status Erase(Address flash_address, uint32_t num_sectors) override {
+    return Status::UNIMPLEMENTED;
+  }
+
+  Status Read(uint8_t* destination_ram_address,
+              Address source_flash_address,
+              uint32_t len) override {
+    return flash_.Read(destination_ram_address, source_flash_address, len);
+  }
+
+  Status Write(Address destination_flash_address,
+               const uint8_t* source_ram_address,
+               uint32_t len) override {
+    return flash_.Write(destination_flash_address, source_ram_address, len);
+  }
+
+  uint8_t* FlashAddressToMcuAddress(Address address) const override {
+    return flash_.FlashAddressToMcuAddress(base_offset_ + address);
+  }
+
+ private:
+  FlashMemory& flash_;
+  // Value to add to addresses to get to the underlying flash_ address.
+  const Address base_offset_;
+};
+
+class FlashPartition {
+ public:
+  // The flash address is in the range of: 0 to PartitionSize.
+  typedef uint32_t Address;
+
+  constexpr FlashPartition(
+      FlashMemory* flash,
+      uint32_t start_sector_index,
+      uint32_t sector_count,
+      PartitionPermission permission = PartitionPermission::kReadAndWrite)
+      : flash_(*flash),
+        start_sector_index_(start_sector_index),
+        sector_count_(sector_count),
+        permission_(permission) {}
+
+  constexpr FlashPartition(FlashMemory* flash, PartitionTableEntry entry)
+      : flash_(*flash),
+        start_sector_index_(entry.partition_start_sector_index),
+        sector_count_(entry.partition_end_sector_index -
+                      entry.partition_start_sector_index + 1),
+        permission_(entry.partition_permission) {}
+
+  // Erase num_sectors starting at a given address. Blocking call.
+  // Address should be on a sector boundary.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or sector count is invalid.
+  //          PERMISSION_DENIED, if partition is read only.
+  //          UNKNOWN, on HAL error
+  virtual Status Erase(Address address, uint32_t num_sectors) {
+    RETURN_STATUS_IF(permission_ == PartitionPermission::kReadOnly,
+                     Status::PERMISSION_DENIED);
+    RETURN_IF_ERROR(CheckBounds(address, num_sectors * GetSectorSizeBytes()));
+    return flash_.Erase(PartitionToFlashAddress(address), num_sectors);
+  }
+
+  // Reads bytes from flash into buffer. Blocking call.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  virtual Status Read(uint8_t* destination_ram_address,
+                      Address source_flash_address,
+                      uint32_t len) {
+    RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+    return flash_.Read(destination_ram_address,
+                       PartitionToFlashAddress(source_flash_address),
+                       len);
+  }
+
+  // Writes bytes to flash. Blocking call.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          PERMISSION_DENIED, if partition is read only.
+  //          UNKNOWN, on HAL error
+  virtual Status Write(Address destination_flash_address,
+                       const uint8_t* source_ram_address,
+                       uint32_t len) {
+    RETURN_STATUS_IF(permission_ == PartitionPermission::kReadOnly,
+                     Status::PERMISSION_DENIED);
+    RETURN_IF_ERROR(CheckBounds(destination_flash_address, len));
+    return flash_.Write(PartitionToFlashAddress(destination_flash_address),
+                        source_ram_address,
+                        len);
+  }
+
+  // Check to see if chunk of flash memory is erased. Address and len need to
+  // be aligned with FlashMemory.
+  // Returns: OK, on success.
+  //          TIMEOUT, on timeout.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  virtual Status IsChunkErased(Address source_flash_address,
+                               uint32_t len,
+                               bool* is_erased) {
+    // Max alignment is artifical to keep the stack usage low for this
+    // function. Using 16 because it's the alignment of encrypted flash.
+    const uint8_t kMaxAlignment = 16;
+    // Relying on Read() to check address and len arguments.
+    RETURN_STATUS_IF(!is_erased, Status::INVALID_ARGUMENT);
+    uint8_t alignment = GetAlignmentBytes();
+    RETURN_STATUS_IF(alignment > kMaxAlignment, Status::INVALID_ARGUMENT);
+    RETURN_STATUS_IF(kMaxAlignment % alignment, Status::INVALID_ARGUMENT);
+    RETURN_STATUS_IF(len % alignment, Status::INVALID_ARGUMENT);
+
+    uint8_t buffer[kMaxAlignment];
+    uint8_t erased_pattern_buffer[kMaxAlignment];
+    size_t offset = 0;
+    memset(erased_pattern_buffer,
+           flash_.GetErasedMemoryContent(),
+           sizeof(erased_pattern_buffer));
+    *is_erased = false;
+    while (len > 0) {
+      // Check earlier that len is aligned, no need to round up
+      uint16_t read_size = std::min(static_cast<uint32_t>(sizeof(buffer)), len);
+      RETURN_IF_ERROR(Read(buffer, source_flash_address + offset, read_size));
+      if (memcmp(buffer, erased_pattern_buffer, read_size)) {
+        // Detected memory chunk is not entirely erased
+        return Status::OK;
+      }
+      offset += read_size;
+      len -= read_size;
+    }
+    *is_erased = true;
+    return Status::OK;
+  }
+
+  constexpr uint32_t GetSectorSizeBytes() const {
+    return flash_.GetSectorSizeBytes();
+  }
+
+  uint32_t GetSizeBytes() const {
+    return GetSectorCount() * GetSectorSizeBytes();
+  }
+
+  virtual uint8_t GetAlignmentBytes() const {
+    return flash_.GetAlignmentBytes();
+  }
+
+  virtual uint32_t GetSectorCount() const { return sector_count_; }
+
+  // Convert a FlashMemory::Address to an MCU pointer, this can be used for
+  // memory mapped reads. Return NULL if the memory is not memory mapped.
+  uint8_t* PartitionAddressToMcuAddress(Address address) const {
+    return flash_.FlashAddressToMcuAddress(PartitionToFlashAddress(address));
+  }
+
+  FlashMemory::Address PartitionToFlashAddress(Address address) const {
+    return flash_.GetStartAddress() +
+           (start_sector_index_ - flash_.GetStartSector()) *
+               GetSectorSizeBytes() +
+           address;
+  }
+
+ protected:
+  Status CheckBounds(Address address, uint32_t len) const {
+    if (address + len > GetSizeBytes()) {
+      LOG(ERROR) << "Attempted out-of-bound flash memory access (address:"
+                 << address << " length:" << len << ")";
+      return Status::INVALID_ARGUMENT;
+    }
+    return Status::OK;
+  }
+
+ private:
+  FlashMemory& flash_;
+  const uint32_t start_sector_index_;
+  const uint32_t sector_count_;
+  const PartitionPermission permission_;
+};
+
+// FlashSubPartition defines a new partition which maps itself as a smaller
+// piece of another partition. This can used when a partition has special
+// behaviours (for example encrypted flash).
+// For example, this will be the first sector of test_partition:
+//    FlashSubPartition test_partition_sector1(&test_partition, 0, 1);
+class FlashSubPartition : public FlashPartition {
+ public:
+  constexpr FlashSubPartition(FlashPartition* parent_partition,
+                              uint32_t start_sector_index,
+                              uint32_t sector_count)
+      : FlashPartition(*parent_partition),
+        partition_(parent_partition),
+        start_sector_index_(start_sector_index),
+        sector_count_(sector_count) {}
+
+  Status Erase(Address address, uint32_t num_sectors) override {
+    RETURN_IF_ERROR(CheckBounds(address, num_sectors * GetSectorSizeBytes()));
+    return partition_->Erase(ParentAddress(address), num_sectors);
+  }
+
+  Status Read(uint8_t* destination_ram_address,
+              Address source_flash_address,
+              uint32_t len) override {
+    RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+    return partition_->Read(
+        destination_ram_address, ParentAddress(source_flash_address), len);
+  }
+
+  Status Write(Address destination_flash_address,
+               const uint8_t* source_ram_address,
+               uint32_t len) override {
+    RETURN_IF_ERROR(CheckBounds(destination_flash_address, len));
+    return partition_->Write(
+        ParentAddress(destination_flash_address), source_ram_address, len);
+  }
+
+  Status IsChunkErased(Address source_flash_address,
+                       uint32_t len,
+                       bool* is_erased) override {
+    RETURN_IF_ERROR(CheckBounds(source_flash_address, len));
+    return partition_->IsChunkErased(
+        ParentAddress(source_flash_address), len, is_erased);
+  }
+
+  uint8_t GetAlignmentBytes() const override {
+    return partition_->GetAlignmentBytes();
+  }
+
+  uint32_t GetSectorCount() const override { return sector_count_; }
+
+ private:
+  Address ParentAddress(Address address) const {
+    return address + start_sector_index_ * partition_->GetSectorSizeBytes();
+  }
+  FlashPartition* partition_;
+  const uint32_t start_sector_index_;
+  const uint32_t sector_count_;
+};
+
+}  // namespace pw
diff --git a/pw_kvs/public/pw_kvs/in_memory_fake_flash.h b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
new file mode 100644
index 0000000..a67c770
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/in_memory_fake_flash.h
@@ -0,0 +1,92 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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 <array>
+
+#include "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/status.h"
+#include "pw_kvs/status_macros.h"
+
+namespace pw {
+
+// This creates a buffer which mimics the behaviour of flash (requires erase,
+// before write, checks alignments, and is addressed in sectors).
+template <uint32_t kSectorSize, uint16_t kSectorCount>
+class InMemoryFakeFlash : public FlashMemory {
+ public:
+  InMemoryFakeFlash(uint8_t alignment = 1)  // default 8 bit alignment
+      : FlashMemory(kSectorSize, kSectorCount, alignment) {}
+
+  // Always enabled
+  Status Enable() override { return Status::OK; }
+  Status Disable() override { return Status::OK; }
+  bool IsEnabled() const override { return true; }
+
+  // Erase num_sectors starting at a given address. Blocking call.
+  // Address should be on a sector boundary.
+  // Returns: OK, on success.
+  //          INVALID_ARGUMENT, if address or sector count is invalid.
+  //          UNKNOWN, on HAL error
+  Status Erase(Address addr, uint32_t num_sectors) override {
+    RETURN_STATUS_IF(addr % GetSectorSizeBytes() != 0,
+                     Status::INVALID_ARGUMENT);
+    RETURN_STATUS_IF(
+        addr / GetSectorSizeBytes() + num_sectors > GetSectorCount(),
+        Status::UNKNOWN);
+    RETURN_STATUS_IF(addr % GetAlignmentBytes() != 0, Status::INVALID_ARGUMENT);
+    memset(&buffer_[addr], 0xFF, GetSectorSizeBytes() * num_sectors);
+    return Status::OK;
+  }
+
+  // Reads bytes from flash into buffer. Blocking call.
+  // Returns: OK, on success.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  Status Read(uint8_t* dest_ram_addr,
+              Address source_flash_addr,
+              uint32_t len) override {
+    RETURN_STATUS_IF(
+        (source_flash_addr + len) >= GetSectorCount() * GetSizeBytes(),
+        Status::INVALID_ARGUMENT);
+    memcpy(dest_ram_addr, &buffer_[source_flash_addr], len);
+    return Status::OK;
+  }
+
+  // Writes bytes to flash. Blocking call.
+  // Returns: OK, on success.
+  //          INVALID_ARGUMENT, if address or length is invalid.
+  //          UNKNOWN, on HAL error
+  Status Write(Address dest_flash_addr,
+               const uint8_t* source_ram_addr,
+               uint32_t len) override {
+    RETURN_STATUS_IF(
+        (dest_flash_addr + len) >= GetSectorCount() * GetSizeBytes(),
+        Status::INVALID_ARGUMENT);
+    RETURN_STATUS_IF(dest_flash_addr % GetAlignmentBytes() != 0,
+                     Status::INVALID_ARGUMENT);
+    RETURN_STATUS_IF(len % GetAlignmentBytes() != 0, Status::INVALID_ARGUMENT);
+    // Check in erased state
+    for (unsigned i = 0; i < len; i++) {
+      RETURN_STATUS_IF(buffer_[dest_flash_addr + i] != 0xFF, Status::UNKNOWN);
+    }
+    memcpy(&buffer_[dest_flash_addr], source_ram_addr, len);
+    return Status::OK;
+  }
+
+ private:
+  std::array<uint8_t, kSectorCount * kSectorSize> buffer_;
+};
+
+}  // namespace pw
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
new file mode 100644
index 0000000..dca6507
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -0,0 +1,366 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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 <algorithm>
+#include <type_traits>
+
+#include "pw_kvs/devices/flash_memory.h"
+#include "pw_kvs/logging.h"
+#include "pw_kvs/os/mutex.h"
+#include "pw_kvs/status.h"
+
+namespace pw {
+
+// This object is very large and should not be placed on the stack.
+class KeyValueStore {
+ public:
+  KeyValueStore(FlashPartition* partition) : partition_(*partition) {}
+
+  // Enable the KVS, scans the sectors of the partition for any current KVS
+  // data. Erases and initializes any sectors which are not initialized.
+  // Checks the CRC of all data in the KVS; on failure the corrupted data is
+  // lost and Enable will return Status::DATA_LOSS, but the KVS will still load
+  // other data and will be enabled.
+  Status Enable();
+  bool IsEnabled() const { return enabled_; }
+  void Disable() {
+    if (enabled_ == false) {
+      return;
+    }
+    os::MutexLock lock(&lock_);
+    enabled_ = false;
+  }
+
+  // Erase a key value element.
+  // key is a null terminated c string.
+  // Returns OK if erased
+  //         NOT_FOUND if key was not found.
+  Status Erase(const char* key);
+
+  // Copy the first size bytes of key's value into value buffer.
+  // key is a null terminated c string. Size is the amount of bytes to read,
+  // Optional offset argument supports reading size bytes starting at the
+  // specified offset.
+  // Returns OK if successful
+  //         NOT_FOUND if key was not found
+  //         DATA_LOSS if the value failed crc check
+  Status Get(const char* key, void* value, uint16_t size, uint16_t offset = 0);
+
+  // Interpret the key's value as the given type and return it.
+  // Returns OK if successful
+  //         NOT_FOUND if key was not found
+  //         DATA_LOSS if the value failed crc check
+  //         INVALID_ARGUMENT if size of value != sizeof(T)
+  template <typename T>
+  Status Get(const char* key, T* value) {
+    static_assert(std::is_trivially_copyable<T>(), "KVS values must copyable");
+    static_assert(!std::is_pointer<T>(), "KVS values cannot be pointers");
+    uint16_t value_size = 0;
+    RETURN_IF_ERROR(GetValueSize(key, &value_size));
+    RETURN_STATUS_IF(value_size != sizeof(T), Status::INVALID_ARGUMENT);
+    return Get(key, value, sizeof(T));
+  }
+
+  // Writes the key value store to the partition. If the key already exists it
+  // will be deleted before writing the new value.
+  // key is a null terminated c string.
+  // Returns OK if successful
+  //         RESOURCE_EXHAUSTED if there is not enough available space
+  Status Put(const char* key, const void* value, uint16_t size);
+
+  // Writes the value to the partition. If the key already exists it will be
+  // deleted before writing the new value.
+  // key is a null terminated c string.
+  // Returns OK if successful
+  //         RESOURCE_EXHAUSTED if there is not enough available space
+  template <typename T>
+  Status Put(const char* key, const T& value) {
+    static_assert(std::is_trivially_copyable<T>(), "KVS values must copyable");
+    static_assert(!std::is_pointer<T>(), "KVS values cannot be pointers");
+    return Put(key, &value, sizeof(T));
+  }
+
+  // Gets the size of the value stored for provided key.
+  // Returns OK if successful
+  //         INVALID_ARGUMENT if args are invalid.
+  //         FAILED_PRECONDITION if KVS is not enabled.
+  //         NOT_FOUND if key was not found.
+  Status GetValueSize(const char* key, uint16_t* value_size);
+
+  // Tests if the proposed key value entry can be stored in the KVS.
+  bool CanFitEntry(uint16_t key_len, uint16_t value_len) {
+    return kSectorInvalid != FindSpace(ChunkSize(key_len, value_len));
+  }
+
+  // CleanAll cleans each sector which is currently marked for cleaning.
+  // Note: if any data is invalid/corrupt it could be lost.
+  Status CleanAll() {
+    os::MutexLock lock(&lock_);
+    return CleanAllInternal();
+  }
+  size_t PendingCleanCount() {
+    os::MutexLock lock(&lock_);
+    size_t ret = 0;
+    for (size_t i = 0; i < SectorCount(); i++) {
+      ret += sector_space_remaining_[i] == 0 ? 1 : 0;
+    }
+    return ret;
+  }
+
+  // Clean a single sector and return, if all sectors are clean it will set
+  // all_sectors_have_been_cleaned to true and return.
+  Status CleanOneSector(bool* all_sectors_have_been_cleaned);
+
+  // For debugging, logging, and testing. (Don't use in regular code)
+  // Note: a key_index is not valid after an element is erased or updated.
+  uint8_t KeyCount() const;
+  const char* GetKey(uint8_t idx) const;
+  uint16_t GetValueSize(uint8_t idx) const;
+  size_t GetMaxKeys() const { return kListCapacityMax; }
+  bool HasEmptySector() const { return HaveEmptySectorImpl(); }
+
+  static constexpr size_t kHeaderSize = 8;  // Sector and KVS Header size
+  static constexpr uint16_t MaxValueLength() { return kChunkValueLengthMax; }
+  KeyValueStore(const KeyValueStore&) = delete;
+  KeyValueStore& operator=(const KeyValueStore&) = delete;
+
+ private:
+  using KeyIndex = uint8_t;
+  using SectorIndex = uint32_t;
+
+  static constexpr uint16_t kVersion = 4;
+  static constexpr KeyIndex kListCapacityMax = cfg::kKvsMaxKeyCount;
+  static constexpr SectorIndex kSectorCountMax = cfg::kKvsMaxSectorCount;
+
+  // Number of bits for fields in KVSHeader:
+  static constexpr int kChunkHeaderKeyFieldNumBits = 4;
+  static constexpr int kChunkHeaderChunkFieldNumBits = 12;
+
+  static constexpr uint16_t kSectorReadyValue = 0xABCD;
+  static constexpr uint16_t kChunkSyncValue = 0x55AA;
+
+  static constexpr uint16_t kChunkLengthMax =
+      ((1 << kChunkHeaderChunkFieldNumBits) - 1);
+  static constexpr uint16_t kChunkKeyLengthMax =
+      ((1 << kChunkHeaderKeyFieldNumBits) - 1);
+  static constexpr uint16_t kChunkValueLengthMax =
+      (kChunkLengthMax - kChunkKeyLengthMax);
+
+  static constexpr SectorIndex kSectorInvalid = 0xFFFFFFFFul;
+  static constexpr FlashPartition::Address kAddressInvalid = 0xFFFFFFFFul;
+  static constexpr uint64_t kSectorCleanNotPending = 0xFFFFFFFFFFFFFFFFull;
+
+  // TODO: Use BitPacker if/when have more flags.
+  static constexpr uint16_t kFlagsIsErasedMask = 0x0001;
+  static constexpr uint16_t kMaxAlignmentBytes = 128;
+
+  // This packs into 16 bytes.
+  struct KvsSectorHeaderMeta {
+    uint16_t synchronize_token;
+    uint16_t version;
+    uint16_t alignment_bytes;  // alignment used for each chunk in this sector.
+    uint16_t padding;          // padding to support uint64_t alignment.
+  } __attribute__((__packed__));
+  static_assert(sizeof(KvsSectorHeaderMeta) == kHeaderSize,
+                "Invalid KvsSectorHeaderMeta size");
+
+  // sector_clean_pending is broken off from KvsSectorHeaderMeta to support
+  // larger than sizeof(KvsSectorHeaderMeta) flash write alignments.
+  struct KvsSectorHeaderCleaning {
+    // When this sector is not marked for cleaning this will be in the erased
+    // state. When marked for clean this value indicates the order the sectors
+    // were marked for cleaning, and therfore which data is the newest.
+    // To remain backwards compatible with v2 and v3 KVS this is 8 bytes, if the
+    // alignment is greater than 8 we will check the entire alignment is in the
+    // default erased state.
+    uint64_t sector_clean_order;
+  };
+  static_assert(sizeof(KvsSectorHeaderCleaning) == kHeaderSize,
+                "Invalid KvsSectorHeaderCleaning size");
+
+  // This packs into 8 bytes, to support uint64_t alignment.
+  struct KvsHeader {
+    uint16_t synchronize_token;
+    uint16_t crc;  // Crc of the key + data (Ignoring any padding bytes)
+    // flags is a Bitmask: bits 15-1 reserved = 0,
+    // bit 0: is_erased [0 when not erased, 1 when erased]
+    uint16_t flags;
+    // On little endian the length fields map to memory as follows:
+    // byte array: [ 0x(c0to3 k0to3) 0x(c8to11 c4to7) ]
+    // Key length does not include trailing zero. That is not stored.
+    uint16_t key_len : kChunkHeaderKeyFieldNumBits;
+    // Chunk length is the total length of the chunk before alignment.
+    // That way we can work out the length of the value as:
+    // (chunk length - key length - size of chunk header).
+    uint16_t chunk_len : kChunkHeaderChunkFieldNumBits;
+  } __attribute__((__packed__));
+  static_assert(sizeof(KvsHeader) == kHeaderSize, "Invalid KvsHeader size");
+
+  struct KeyMap {
+    char key[kChunkKeyLengthMax + 1];  // + 1 for null terminator
+    FlashPartition::Address address;
+    uint16_t chunk_len;
+    bool is_erased;
+  };
+
+  // NOTE: All public APIs handle the locking, the internal methods assume the
+  // lock has already been acquired.
+
+  SectorIndex AddressToSectorIndex(FlashPartition::Address address) const {
+    return address / partition_.GetSectorSizeBytes();
+  }
+
+  FlashPartition::Address SectorIndexToAddress(SectorIndex index) const {
+    return index * partition_.GetSectorSizeBytes();
+  }
+
+  // Returns kAddressInvalid if no space is found, otherwise the address.
+  FlashPartition::Address FindSpace(uint16_t requested_size) const;
+
+  // Attempts to rewrite a key's value by appending the new value to the same
+  // sector. If the sector is full the value is written to another sector, and
+  // the sector is marked for cleaning.
+  // Returns RESOURCE_EXHAUSTED if no space is available, OK otherwise.
+  Status RewriteValue(KeyIndex key_index,
+                      const uint8_t* value,
+                      uint16_t size,
+                      bool is_erased = false);
+
+  bool ValueMatches(KeyIndex key_index,
+                    const uint8_t* value,
+                    uint16_t size,
+                    bool is_erased);
+
+  // ResetSector erases the sector and writes the sector header.
+  Status ResetSector(SectorIndex sector_index);
+  Status WriteKeyValue(FlashPartition::Address address,
+                       const char* key,
+                       const uint8_t* value,
+                       uint16_t size,
+                       bool is_erased = false);
+  uint32_t SectorSpaceRemaining(SectorIndex sector_index) const;
+
+  // Returns idx if key is found, otherwise kListCapacityMax.
+  KeyIndex FindKeyInMap(const char* key) const;
+  bool IsKeyInMap(const char* key) const {
+    return FindKeyInMap(key) != kListCapacityMax;
+  }
+
+  void RemoveFromMap(KeyIndex key_index);
+  Status AppendToMap(const char* key,
+                     FlashPartition::Address address,
+                     uint16_t chunk_len,
+                     bool is_erased = false);
+  void UpdateMap(KeyIndex key_index,
+                 FlashPartition::Address address,
+                 uint16_t chunk_len,
+                 bool is_erased = false);
+  uint16_t CalculateCrc(const char* key,
+                        uint16_t key_size,
+                        const uint8_t* value,
+                        uint16_t value_size) const;
+
+  // Calculates the CRC by reading the value from flash in chunks.
+  Status CalculateCrcFromValueAddress(const char* key,
+                                      uint16_t key_size,
+                                      FlashPartition::Address value_address,
+                                      uint16_t value_size,
+                                      uint16_t* crc_ret);
+
+  uint16_t RoundUpForAlignment(uint16_t size) const {
+    if (size % alignment_bytes_ != 0) {
+      return size + alignment_bytes_ - size % alignment_bytes_;
+    }
+    return size;
+  }
+
+  // The buffer is chosen to be no larger then the config value, and
+  // be a multiple of the flash alignment.
+  size_t TempBufferAlignedSize() const {
+    CHECK_GE(sizeof(temp_buffer_), partition_.GetAlignmentBytes());
+    return sizeof(temp_buffer_) -
+           (sizeof(temp_buffer_) % partition_.GetAlignmentBytes());
+  }
+
+  // Moves a key/value chunk from one address to another, all fields expected to
+  // be aligned.
+  Status MoveChunk(FlashPartition::Address dest_address,
+                   FlashPartition::Address src_address,
+                   uint16_t size);
+
+  // Size of a chunk including header, key, value, and alignment padding.
+  uint16_t ChunkSize(uint16_t key_len, uint16_t chunk_len) const {
+    return RoundUpForAlignment(sizeof(KvsHeader)) +
+           RoundUpForAlignment(key_len) + RoundUpForAlignment(chunk_len);
+  }
+
+  // Sectors should be cleaned when full, every valid (Most recent, not erased)
+  // chunk of data is moved to another sector and the sector is erased.
+  // TODO: Clean sectors with lots of invalid data, without a rewrite
+  // or erase triggering it.
+  Status MarkSectorForClean(SectorIndex sector);
+  Status CleanSector(SectorIndex sector);
+  Status CleanAllInternal();
+  Status GarbageCollectImpl(bool clean_pending_sectors,
+                            bool exit_when_have_free_sector);
+  Status FullGarbageCollect();
+  Status EnforceFreeSector();
+
+  SectorIndex SectorCount() const {
+    return std::min(partition_.GetSectorCount(), kSectorCountMax);
+  }
+
+  size_t SectorSpaceAvailableWhenEmpty() const {
+    return partition_.GetSectorSizeBytes() -
+           RoundUpForAlignment(sizeof(KvsSectorHeaderMeta)) -
+           RoundUpForAlignment(sizeof(KvsSectorHeaderCleaning));
+  }
+
+  bool HaveEmptySectorImpl(SectorIndex skip_sector = kSectorInvalid) const {
+    for (SectorIndex i = 0; i < SectorCount(); i++) {
+      if (i != skip_sector &&
+          sector_space_remaining_[i] == SectorSpaceAvailableWhenEmpty()) {
+        return true;
+      }
+    }
+    return false;
+  }
+
+  bool IsInLastFreeSector(FlashPartition::Address address) {
+    return sector_space_remaining_[AddressToSectorIndex(address)] ==
+               SectorSpaceAvailableWhenEmpty() &&
+           !HaveEmptySectorImpl(AddressToSectorIndex(address));
+  }
+
+  FlashPartition& partition_;
+  os::Mutex lock_;
+  bool enabled_ = false;
+  uint8_t alignment_bytes_ = 0;
+  uint64_t next_sector_clean_order_ = 0;
+
+  // Free space available in each sector, set to 0 when clean is pending/active
+  uint32_t sector_space_remaining_[kSectorCountMax] = {0};
+  uint64_t sector_clean_order_[kSectorCountMax] = {kSectorCleanNotPending};
+  KeyMap key_map_[kListCapacityMax] = {{{0}}};
+  KeyIndex map_size_ = 0;
+
+  // +1 for nul-terminator since keys are stored as Length + Value and no nul
+  // termination but we are using them as nul-terminated strings through
+  // loading-up and comparing the keys.
+  char temp_key_buffer_[kChunkKeyLengthMax + 1u] = {0};
+  uint8_t temp_buffer_[cfg::kKvsBufferSize] = {0};
+};
+
+}  // namespace pw
diff --git a/pw_kvs/public/pw_kvs/partition_table_entry.h b/pw_kvs/public/pw_kvs/partition_table_entry.h
new file mode 100644
index 0000000..9aa111d
--- /dev/null
+++ b/pw_kvs/public/pw_kvs/partition_table_entry.h
@@ -0,0 +1,51 @@
+// 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
+//
+//     https://www.apache.org/licenses/LICENSE-2.0
+//
+// 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 <cstdint>
+
+namespace pw {
+
+namespace partition_table {
+
+enum DataType { kRawData, kKvs };
+
+}  // namespace partition_table
+
+enum class PartitionPermission : bool {
+  kReadOnly = true,
+  kReadAndWrite = false,
+};
+
+struct PartitionTableEntry {
+  constexpr PartitionTableEntry(
+      const uint32_t start_sector_index,
+      const uint32_t end_sector_index,
+      const uint8_t partition_identifier,
+      partition_table::DataType datatype,
+      PartitionPermission permission = PartitionPermission::kReadAndWrite)
+      : partition_start_sector_index(start_sector_index),
+        partition_end_sector_index(end_sector_index),
+        partition_id(partition_identifier),
+        data_type(datatype),
+        partition_permission(permission) {}
+
+  const uint32_t partition_start_sector_index;
+  const uint32_t partition_end_sector_index;
+  const uint8_t partition_id;
+  const partition_table::DataType data_type;
+  const PartitionPermission partition_permission;
+};
+
+}  // namespace pw