pw_kvs: Get checksums working; enable test
- Allow checksums to verify data larger than their internal state. This
facilitates using a CRC16 in a uint32_t.
- Move checksum functions to the EntryHeader class, since it ultimately
stores the checksums and is included with it.
- Enable one checksum test. Further tests are needed.
- Make some tweaks to the Get overload for objects.
Change-Id: I989b72905e140794f75c8f8619aaab1623f6f195
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index 69a13ec..0f054f8 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -27,6 +27,7 @@
srcs = [
"checksum.cc",
"flash_memory.cc",
+ "format.cc",
"key_value_store.cc",
"pw_kvs_private/format.h",
"pw_kvs_private/macros.h",
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index 0c17d87..5179386 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -30,6 +30,7 @@
sources = [
"checksum.cc",
"flash_memory.cc",
+ "format.cc",
"key_value_store.cc",
"pw_kvs_private/format.h",
"pw_kvs_private/macros.h",
diff --git a/pw_kvs/checksum.cc b/pw_kvs/checksum.cc
index 9f14c90..f5db069 100644
--- a/pw_kvs/checksum.cc
+++ b/pw_kvs/checksum.cc
@@ -21,14 +21,12 @@
using std::byte;
Status ChecksumAlgorithm::Verify(span<const byte> checksum) const {
- if (checksum.size() != size_bytes()) {
+ if (checksum.size() < size_bytes()) {
return Status::INVALID_ARGUMENT;
}
-
- if (std::memcmp(state_.data(), checksum.data(), state_.size()) != 0) {
+ if (std::memcmp(state_.data(), checksum.data(), size_bytes()) != 0) {
return Status::DATA_LOSS;
}
-
return Status::OK;
}
diff --git a/pw_kvs/checksum_test.cc b/pw_kvs/checksum_test.cc
index e5333ad..fbf228e 100644
--- a/pw_kvs/checksum_test.cc
+++ b/pw_kvs/checksum_test.cc
@@ -43,13 +43,25 @@
TEST(Checksum, Verify_InvalidSize) {
ChecksumCrc16 algo;
EXPECT_EQ(Status::INVALID_ARGUMENT, algo.Verify({}));
- EXPECT_EQ(Status::INVALID_ARGUMENT, algo.Verify(as_bytes(span(kString))));
+ EXPECT_EQ(Status::INVALID_ARGUMENT,
+ algo.Verify(as_bytes(span(kString.substr(0, 1)))));
+}
+
+TEST(Checksum, Verify_LargerState_ComparesToTruncatedData) {
+ byte crc[3] = {byte{0x84}, byte{0xC1}, byte{0x33}};
+ ChecksumCrc16 algo;
+ ASSERT_GT(sizeof(crc), algo.size_bytes());
+
+ algo.Update(as_bytes(span(kString)));
+
+ EXPECT_EQ(Status::OK, algo.Verify(crc));
}
TEST(Checksum, Reset) {
ChecksumCrc16 crc_algo;
crc_algo.Update(as_bytes(span(kString)));
crc_algo.Reset();
+
EXPECT_EQ(crc_algo.state()[0], byte{0xFF});
EXPECT_EQ(crc_algo.state()[1], byte{0xFF});
}
diff --git a/pw_kvs/format.cc b/pw_kvs/format.cc
new file mode 100644
index 0000000..739783d
--- /dev/null
+++ b/pw_kvs/format.cc
@@ -0,0 +1,93 @@
+// 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_private/format.h"
+
+#include "pw_kvs_private/macros.h"
+
+namespace pw::kvs {
+
+using std::byte;
+using std::string_view;
+
+EntryHeader::EntryHeader(uint32_t magic,
+ ChecksumAlgorithm* algorithm,
+ string_view key,
+ span<const byte> value,
+ uint32_t key_version)
+ : magic_(magic),
+ checksum_(kNoChecksum),
+ key_value_length_(value.size() << kValueLengthShift |
+ (key.size() & kKeyLengthMask)),
+ key_version_(key_version) {
+ if (algorithm != nullptr) {
+ CalculateChecksum(algorithm, key, value);
+ std::memcpy(&checksum_,
+ algorithm->state().data(),
+ std::min(algorithm->size_bytes(), sizeof(checksum_)));
+ }
+}
+
+Status EntryHeader::VerifyChecksum(ChecksumAlgorithm* algorithm,
+ string_view key,
+ span<const byte> value) const {
+ if (algorithm == nullptr) {
+ return checksum() == kNoChecksum ? Status::OK : Status::DATA_LOSS;
+ }
+ CalculateChecksum(algorithm, key, value);
+ return algorithm->Verify(checksum_bytes());
+}
+
+Status EntryHeader::VerifyChecksumInFlash(
+ FlashPartition* partition,
+ FlashPartition::Address header_address,
+ ChecksumAlgorithm* algorithm,
+ string_view key) const {
+ if (algorithm == nullptr) {
+ return checksum() == kNoChecksum ? Status::OK : Status::DATA_LOSS;
+ }
+
+ CalculateChecksum(algorithm, key);
+
+ // Read the value piece-by-piece into a small buffer.
+ // TODO: This read may be unaligned. The partition can handle this, but
+ // consider creating a API that skips the intermediate buffering.
+ byte buffer[32];
+
+ size_t bytes_to_read = value_length();
+ FlashPartition::Address address =
+ header_address + sizeof(*this) + key_length();
+
+ while (bytes_to_read > 0u) {
+ const size_t read_size = std::min(sizeof(buffer), bytes_to_read);
+ TRY(partition->Read(address, read_size, buffer));
+ address += read_size;
+ algorithm->Update(buffer, read_size);
+ }
+
+ return algorithm->Verify(checksum_bytes());
+}
+
+void EntryHeader::CalculateChecksum(ChecksumAlgorithm* algorithm,
+ const string_view key,
+ span<const byte> value) const {
+ algorithm->Reset();
+ algorithm->Update(reinterpret_cast<const byte*>(this) +
+ offsetof(EntryHeader, key_value_length_),
+ sizeof(*this) - offsetof(EntryHeader, key_value_length_));
+ algorithm->Update(as_bytes(span(key)));
+ algorithm->Update(value);
+}
+
+} // namespace pw::kvs
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index fdf5e14..0b6a6a3 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -32,11 +32,6 @@
using Address = FlashPartition::Address;
-constexpr union {
- byte bytes[4];
- uint32_t value;
-} kNoChecksum{};
-
// constexpr uint32_t SixFiveFiveNineNine(std::string_view string) {
constexpr uint32_t HashKey(std::string_view string) {
uint32_t hash = 0;
@@ -144,7 +139,7 @@
DBG("Header: ");
DBG(" Address = 0x%zx", size_t(entry_address));
DBG(" Magic = 0x%zx", size_t(header.magic()));
- DBG(" Checksum = 0x%zx", size_t(header.checksum_as_uint32()));
+ DBG(" Checksum = 0x%zx", size_t(header.checksum()));
DBG(" Key length = 0x%zx", size_t(header.key_length()));
DBG(" Value length = 0x%zx", size_t(header.value_length()));
DBG(" Entry size = 0x%zx", size_t(header.entry_size()));
@@ -171,7 +166,8 @@
TRY(ReadEntryKey(key_descriptor, header.key_length(), key_buffer.data()));
const string_view key(key_buffer.data(), header.key_length());
- TRY(ValidateEntryChecksumInFlash(header, key, key_descriptor));
+ TRY(header.VerifyChecksumInFlash(
+ &partition_, key_descriptor.address, entry_header_format_.checksum, key));
key_descriptor.key_hash = HashKey(key);
DBG("Key hash: %zx (%zu)",
@@ -257,7 +253,9 @@
StatusWithSize result = ReadEntryValue(*key_descriptor, header, value_buffer);
if (result.ok() && options_.verify_on_read) {
- return ValidateEntryChecksum(header, key, value_buffer);
+ return header.VerifyChecksum(entry_header_format_.checksum,
+ key,
+ value_buffer.subspan(0, result.size()));
}
return result;
}
@@ -290,7 +288,7 @@
const KeyValueStore::Entry& KeyValueStore::Iterator::operator*() {
const KeyDescriptor& descriptor = entry_.kvs_.key_descriptor_list_[index_];
- std::memset(entry_.key_buffer_.data(), 0, sizeof(entry_.key_buffer_));
+ std::memset(entry_.key_buffer_.data(), 0, entry_.key_buffer_.size());
EntryHeader header;
if (entry_.kvs_.ReadEntryHeader(descriptor, &header).ok()) {
@@ -313,35 +311,19 @@
return StatusWithSize(header.value_length());
}
-Status KeyValueStore::ValidateEntryChecksumInFlash(
- const EntryHeader& header,
- const string_view key,
- const KeyDescriptor& entry) const {
- if (entry_header_format_.checksum == nullptr) {
- return header.checksum_as_uint32() == 0 ? Status::OK : Status::DATA_LOSS;
+Status KeyValueStore::FixedSizeGet(std::string_view key,
+ byte* value,
+ size_t size_bytes) const {
+ // Ensure that the size of the stored value matches the size of the type.
+ // Otherwise, report error. This check avoids potential memory corruption.
+ StatusWithSize result = ValueSize(key);
+ if (!result.ok()) {
+ return result.status();
}
-
- auto& checksum = *entry_header_format_.checksum;
- checksum.Reset();
- checksum.Update(header.DataForChecksum());
- checksum.Update(as_bytes(span(key)));
-
- // Read the value piece-by-piece into a small buffer.
- // TODO: This read may be unaligned. The partition can handle this, but
- // consider creating a API that skips the intermediate buffering.
- byte buffer[32];
-
- size_t bytes_to_read = header.value_length();
- Address address = entry.address + sizeof(header) + header.key_length();
-
- while (bytes_to_read > 0u) {
- const size_t read_size = std::min(sizeof(buffer), bytes_to_read);
- TRY(partition_.Read(address, read_size, buffer));
- address += read_size;
- checksum.Update(buffer, read_size);
+ if (result.size() != size_bytes) {
+ return Status::INVALID_ARGUMENT;
}
-
- return Status::OK;
+ return Get(key, span(value, size_bytes)).status();
}
Status KeyValueStore::InvalidOperation(string_view key) const {
@@ -412,18 +394,6 @@
return StatusWithSize(read_size);
}
-Status KeyValueStore::ValidateEntryChecksum(const EntryHeader& header,
- string_view key,
- span<const byte> value) const {
- if (entry_header_format_.checksum == nullptr) {
- return header.checksum_as_uint32() == kNoChecksum.value ? Status::OK
- : Status::DATA_LOSS;
- }
-
- CalculateEntryChecksum(header, key, value);
- return entry_header_format_.checksum->Verify(header.checksum());
-}
-
Status KeyValueStore::WriteEntryForExistingKey(KeyDescriptor* key_descriptor,
string_view key,
span<const byte> value) {
@@ -593,9 +563,9 @@
span<const byte> value) {
// write header, key, and value
const EntryHeader header(entry_header_format_.magic,
- CalculateEntryChecksum(header, key, value),
- key.size(),
- value.size(),
+ entry_header_format_.checksum,
+ key,
+ value,
key_descriptor->key_version + 1);
DBG("Appending entry with key version: %zx", size_t(header.key_version()));
@@ -635,22 +605,6 @@
return Status::UNIMPLEMENTED;
}
-span<const byte> KeyValueStore::CalculateEntryChecksum(
- const EntryHeader& header,
- const string_view key,
- span<const byte> value) const {
- if (entry_header_format_.checksum == nullptr) {
- return kNoChecksum.bytes;
- }
-
- auto& checksum = *entry_header_format_.checksum;
- checksum.Reset();
- checksum.Update(header.DataForChecksum());
- checksum.Update(as_bytes(span(key)));
- checksum.Update(value.data(), value.size_bytes());
- return checksum.state();
-}
-
void KeyValueStore::LogDebugInfo() {
const size_t sector_count = partition_.sector_count();
const size_t sector_size_bytes = partition_.sector_size_bytes();
diff --git a/pw_kvs/key_value_store_test.cc b/pw_kvs/key_value_store_test.cc
index 8d979fa..ed2ccc8 100644
--- a/pw_kvs/key_value_store_test.cc
+++ b/pw_kvs/key_value_store_test.cc
@@ -390,8 +390,6 @@
#define ASSERT_OK(expr) ASSERT_EQ(Status::OK, expr)
#define EXPECT_OK(expr) EXPECT_EQ(Status::OK, expr)
-#define AS_SIZE(x) static_cast<size_t>(x)
-
TEST(InMemoryKvs, DISABLED_WriteOneKeyMultipleTimes) {
// Create and erase the fake flash. It will persist across reloads.
Flash flash;
@@ -417,7 +415,7 @@
uint32_t written_value;
EXPECT_EQ(kvs.size(), (reload == 0) ? 0 : 1u);
for (uint32_t i = 0; i < num_writes; ++i) {
- INF("PUT #%zu for key %s with value %zu", AS_SIZE(i), key, AS_SIZE(i));
+ INF("PUT #%zu for key %s with value %zu", size_t(i), key, size_t(i));
written_value = i + 0xfc; // Prevent accidental pass with zero.
EXPECT_OK(kvs.Put(key, written_value));
@@ -1196,7 +1194,7 @@
}
#endif
-TEST_F(KeyValueStoreTest, DISABLED_DifferentValueSameCrc16) {
+TEST_F(KeyValueStoreTest, DifferentValueSameCrc16) {
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
@@ -1214,7 +1212,7 @@
ASSERT_EQ(Status::OK, kvs_.Put(kKey, kValue2));
// Read it back and check it is correct
- char value[3];
+ char value[3] = {};
ASSERT_EQ(Status::OK, kvs_.Get(kKey, &value));
ASSERT_EQ(std::memcmp(value, kValue2, sizeof(value)), 0);
}
diff --git a/pw_kvs/public/pw_kvs/checksum.h b/pw_kvs/public/pw_kvs/checksum.h
index 9f974b3..b1f1658 100644
--- a/pw_kvs/public/pw_kvs/checksum.h
+++ b/pw_kvs/public/pw_kvs/checksum.h
@@ -39,7 +39,9 @@
// Returns the size of the checksum state.
constexpr size_t size_bytes() const { return state_.size(); }
- // Compares a calculated checksum to this checksum's current state.
+ // Compares a calculated checksum to this checksum's current state. The
+ // checksum must be at least as large as size_bytes(). If it is larger, bytes
+ // beyond size_bytes() are ignored.
Status Verify(span<const std::byte> checksum) const;
protected:
diff --git a/pw_kvs/public/pw_kvs/key_value_store.h b/pw_kvs/public/pw_kvs/key_value_store.h
index 2b17a97..89ae31c 100644
--- a/pw_kvs/public/pw_kvs/key_value_store.h
+++ b/pw_kvs/public/pw_kvs/key_value_store.h
@@ -49,7 +49,7 @@
std::bool_constant<internal::ConvertsToSpan<std::remove_reference_t<T>>(0)>;
// Internal-only persistent storage header format.
-struct EntryHeader;
+class EntryHeader;
struct EntryHeaderFormat {
uint32_t magic; // unique identifier
@@ -91,21 +91,19 @@
StatusWithSize Get(std::string_view key, span<std::byte> value) const;
- template <typename T>
- Status Get(const std::string_view& 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");
+ // This overload of Get accepts a pointer to a trivially copyable object.
+ // const T& is used instead of T* to prevent arrays from satisfying this
+ // overload. To call Get with an array, pass as_writable_bytes(span(array)),
+ // or pass a pointer to the array instead of the array itself.
+ template <typename Pointer,
+ typename = std::enable_if_t<std::is_pointer_v<Pointer>>>
+ Status Get(const std::string_view& key, const Pointer& pointer) const {
+ using T = std::remove_reference_t<std::remove_pointer_t<Pointer>>;
- // Ensure that the size of the stored value matches the size of the type.
- // Otherwise, report error. This check avoids potential memory corruption.
- StatusWithSize result = ValueSize(key);
- if (!result.ok()) {
- return result.status();
- }
- if (result.size() != sizeof(T)) {
- return Status::INVALID_ARGUMENT;
- }
- return Get(key, as_writable_bytes(span(value, 1))).status();
+ static_assert(std::is_trivially_copyable<T>(), "Values must be copyable");
+ static_assert(!std::is_pointer<T>(), "Values cannot be pointers");
+
+ return FixedSizeGet(key, reinterpret_cast<std::byte*>(pointer), sizeof(T));
}
Status Put(std::string_view key, span<const std::byte> value);
@@ -136,9 +134,10 @@
return kvs_.Get(key(), value_buffer).status();
}
- template <typename T>
- Status Get(T* value) const {
- return kvs_.Get(key(), value);
+ template <typename Pointer,
+ typename = std::enable_if_t<std::is_pointer_v<Pointer>>>
+ Status Get(const Pointer& pointer) const {
+ return kvs_.Get(key(), pointer);
}
StatusWithSize ValueSize() const { return kvs_.ValueSize(key()); }
@@ -219,6 +218,10 @@
}
};
+ Status FixedSizeGet(std::string_view key,
+ std::byte* value,
+ size_t size_bytes) const;
+
Status InvalidOperation(std::string_view key) const;
static constexpr bool InvalidKey(std::string_view key) {
@@ -244,10 +247,6 @@
const EntryHeader& header,
span<std::byte> value) const;
- Status ValidateEntryChecksum(const EntryHeader& header,
- std::string_view key,
- span<const std::byte> value) const;
-
Status LoadEntry(Address entry_address, Address* next_entry_address);
Status AppendNewOrOverwriteStaleExistingDescriptor(
const KeyDescriptor& key_descriptor);
@@ -287,11 +286,6 @@
Status VerifyEntry(SectorDescriptor* sector, KeyDescriptor* key_descriptor);
- span<const std::byte> CalculateEntryChecksum(
- const EntryHeader& header,
- std::string_view key,
- span<const std::byte> value) const;
-
bool AddressInSector(const SectorDescriptor& sector, Address address) const {
const Address sector_base = SectorBaseAddress(§or);
const Address sector_end = sector_base + partition_.sector_size_bytes();
diff --git a/pw_kvs/pw_kvs_private/format.h b/pw_kvs/pw_kvs_private/format.h
index 9cd470c..a1867e4 100644
--- a/pw_kvs/pw_kvs_private/format.h
+++ b/pw_kvs/pw_kvs_private/format.h
@@ -11,40 +11,40 @@
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.
+
+// This file defines classes for managing the in-flash format for KVS entires.
#pragma once
#include <cstddef>
#include <cstdint>
#include <cstring>
+#include <string_view>
+#include "pw_kvs/checksum.h"
+#include "pw_kvs/flash_memory.h"
#include "pw_span/span.h"
namespace pw::kvs {
-// In-flash header format.
-struct EntryHeader {
- EntryHeader() : key_value_length_(0) {}
+// EntryHeader represents a key-value entry as stored in flash.
+class EntryHeader {
+ public:
+ EntryHeader() = default;
EntryHeader(uint32_t magic,
- span<const std::byte> checksum,
- size_t key_length,
- size_t value_length,
- uint32_t key_version)
- : magic_(magic),
- checksum_(0),
- key_value_length_(value_length << kValueLengthShift |
- (key_length & kKeyLengthMask)),
- key_version_(key_version) {
- std::memcpy(&checksum_,
- checksum.data(),
- std::min(checksum.size(), sizeof(checksum_)));
- }
+ ChecksumAlgorithm* algorithm,
+ std::string_view key,
+ span<const std::byte> value,
+ uint32_t key_version);
- span<const std::byte> DataForChecksum() const {
- return span(reinterpret_cast<const std::byte*>(this) +
- offsetof(EntryHeader, key_value_length_),
- sizeof(*this) - offsetof(EntryHeader, key_value_length_));
- }
+ Status VerifyChecksum(ChecksumAlgorithm* algorithm,
+ std::string_view key,
+ span<const std::byte> value) const;
+
+ Status VerifyChecksumInFlash(FlashPartition* partition,
+ FlashPartition::Address header_address,
+ ChecksumAlgorithm* algorithm,
+ std::string_view key) const;
size_t entry_size() const {
return sizeof(*this) + key_length() + value_length();
@@ -52,11 +52,7 @@
uint32_t magic() const { return magic_; }
- span<const std::byte> checksum() const {
- return as_bytes(span(&checksum_, 1));
- }
-
- uint32_t checksum_as_uint32() const { return checksum_; }
+ uint32_t checksum() const { return checksum_; }
size_t key_length() const { return key_value_length_ & kKeyLengthMask; }
void set_key_length(uint32_t key_length) {
@@ -72,9 +68,18 @@
uint32_t key_version() const { return key_version_; }
private:
+ static constexpr uint32_t kNoChecksum = 0;
static constexpr uint32_t kKeyLengthMask = 0b111111;
static constexpr uint32_t kValueLengthShift = 8;
+ span<const std::byte> checksum_bytes() const {
+ return as_bytes(span(&checksum_, 1));
+ }
+
+ void CalculateChecksum(ChecksumAlgorithm* algorithm,
+ std::string_view key,
+ span<const std::byte> value = {}) const;
+
uint32_t magic_;
uint32_t checksum_;
// 6 bits, 0: 5 - key - maximum 64 characters
