pw_kvs: Introduce alignment to the entry header
- Add an 8-bit alignment field to the entry header. This makes the
entry header a complete description of the entry's representation in
flash (assuming the checksum algorithm is implied by the magic).
- Write basic tests for the EntryHeader class.
Change-Id: I7e48d5c16451ceb81f7c191d2f261e0a9bef14b7
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD
index cb9464b..9f267b0 100644
--- a/pw_kvs/BUILD
+++ b/pw_kvs/BUILD
@@ -81,6 +81,16 @@
)
pw_cc_test(
+ name = "entry_test",
+ srcs = [
+ "entry_test.cc",
+ ],
+ deps = [
+ ":pw_kvs",
+ ],
+)
+
+pw_cc_test(
name = "key_value_store_test",
srcs = ["key_value_store_test.cc"],
deps = [
diff --git a/pw_kvs/BUILD.gn b/pw_kvs/BUILD.gn
index c82141e..dab9de4 100644
--- a/pw_kvs/BUILD.gn
+++ b/pw_kvs/BUILD.gn
@@ -43,7 +43,10 @@
dir_pw_checksum,
dir_pw_log,
]
- friend = [ ":key_value_store_test" ]
+ friend = [
+ ":entry_test",
+ ":key_value_store_test",
+ ]
}
source_set("crc16") {
@@ -82,6 +85,7 @@
pw_test_group("tests") {
tests = [
":checksum_test",
+ ":entry_test",
":key_value_store_test",
]
}
@@ -97,6 +101,15 @@
]
}
+pw_test("entry_test") {
+ deps = [
+ ":pw_kvs",
+ ]
+ sources = [
+ "entry_test.cc",
+ ]
+}
+
pw_test("key_value_store_test") {
deps = [
":crc16",
diff --git a/pw_kvs/entry_test.cc b/pw_kvs/entry_test.cc
new file mode 100644
index 0000000..a726b5f
--- /dev/null
+++ b/pw_kvs/entry_test.cc
@@ -0,0 +1,57 @@
+// 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 "gtest/gtest.h"
+#include "pw_kvs/flash_memory.h"
+#include "pw_kvs_private/format.h"
+
+namespace pw::kvs {
+namespace {
+
+TEST(EntryHeader, Alignment) {
+ for (size_t alignment_bytes = 1; alignment_bytes <= 4096; ++alignment_bytes) {
+ ASSERT_EQ(AlignUp(alignment_bytes, EntryHeader::kMinAlignmentBytes),
+ EntryHeader::Valid(9, nullptr, "k", {}, alignment_bytes, 0)
+ .alignment_bytes());
+ ASSERT_EQ(AlignUp(alignment_bytes, EntryHeader::kMinAlignmentBytes),
+ EntryHeader::Tombstone(9, nullptr, "k", alignment_bytes, 0)
+ .alignment_bytes());
+ }
+}
+
+TEST(EntryHeader, ValidEntry) {
+ EntryHeader entry =
+ EntryHeader::Valid(9, nullptr, "k", as_bytes(span("123")), 1, 9876);
+
+ EXPECT_FALSE(entry.deleted());
+ EXPECT_EQ(entry.magic(), 9u);
+ EXPECT_EQ(entry.checksum(), 0u); // kNoChecksum
+ EXPECT_EQ(entry.key_length(), 1u);
+ EXPECT_EQ(entry.value_length(), sizeof("123"));
+ EXPECT_EQ(entry.key_version(), 9876u);
+}
+
+TEST(EntryHeader, Tombstone) {
+ EntryHeader entry = EntryHeader::Tombstone(99, nullptr, "key", 1, 123);
+
+ EXPECT_TRUE(entry.deleted());
+ EXPECT_EQ(entry.magic(), 99u);
+ EXPECT_EQ(entry.checksum(), 0u); // kNoChecksum
+ EXPECT_EQ(entry.key_length(), 3u);
+ EXPECT_EQ(entry.value_length(), 0u);
+ EXPECT_EQ(entry.key_version(), 123u);
+}
+
+} // namespace
+} // namespace pw::kvs
diff --git a/pw_kvs/format.cc b/pw_kvs/format.cc
index 6abb3b7..d39fe44 100644
--- a/pw_kvs/format.cc
+++ b/pw_kvs/format.cc
@@ -26,12 +26,14 @@
ChecksumAlgorithm* algorithm,
string_view key,
span<const byte> value,
- uint32_t value_length,
+ uint16_t value_length_bytes,
+ size_t alignment_bytes,
uint32_t key_version)
: magic_(magic),
checksum_(kNoChecksum),
- key_value_length_(value_length << kValueLengthShift |
- (key.size() & kKeyLengthMask)),
+ alignment_units_(alignment_bytes_to_units(alignment_bytes)),
+ key_length_bytes_(key.size()),
+ value_length_bytes_(value_length_bytes),
key_version_(key_version) {
if (algorithm != nullptr) {
CalculateChecksum(algorithm, key, value);
@@ -39,6 +41,9 @@
algorithm->state().data(),
std::min(algorithm->size_bytes(), sizeof(checksum_)));
}
+
+ // TODO: 0 is an invalid alignment value. There should be an assert for this.
+ // DCHECK_NE(alignment_bytes, 0);
}
Status EntryHeader::VerifyChecksum(ChecksumAlgorithm* algorithm,
@@ -87,7 +92,7 @@
// Read and calculate the checksum of the remaining header, key, and value.
address += checked_data_offset();
- size_t bytes_to_read = size() - checked_data_offset();
+ size_t bytes_to_read = content_size() - checked_data_offset();
while (bytes_to_read > 0u) {
const size_t read_size = std::min(sizeof(buffer), bytes_to_read);
diff --git a/pw_kvs/key_value_store.cc b/pw_kvs/key_value_store.cc
index b19c163..5f5bddc 100644
--- a/pw_kvs/key_value_store.cc
+++ b/pw_kvs/key_value_store.cc
@@ -189,8 +189,7 @@
TRY(AppendNewOrOverwriteStaleExistingDescriptor(key_descriptor));
// TODO: Extract this to something like "NextValidEntryAddress".
- *next_entry_address =
- AlignUp(key_descriptor.address + header.size(), alignment_bytes);
+ *next_entry_address = key_descriptor.address + header.size();
return Status::OK;
}
@@ -476,7 +475,8 @@
SectorDescriptor& old_sector = SectorFromAddress(key_descriptor->address);
SectorDescriptor* sector;
- TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, value)));
+ TRY(FindOrRecoverSectorWithSpace(
+ §or, EntryHeader::size(partition_.alignment_bytes(), key, value)));
DBG("Writing existing entry; found sector: %zu", SectorIndex(sector));
TRY(AppendEntry(sector, key_descriptor, key, value, new_state));
@@ -503,7 +503,8 @@
key_descriptor.state = KeyDescriptor::kValid;
SectorDescriptor* sector;
- TRY(FindOrRecoverSectorWithSpace(§or, EntryHeader::size(key, value)));
+ TRY(FindOrRecoverSectorWithSpace(
+ §or, EntryHeader::size(partition_.alignment_bytes(), key, value)));
DBG("Writing new entry; found sector: %zu", SectorIndex(sector));
TRY(AppendEntry(sector, &key_descriptor, key, value));
@@ -719,16 +720,20 @@
header = EntryHeader::Tombstone(entry_header_format_.magic,
entry_header_format_.checksum,
key,
+ partition_.alignment_bytes(),
key_descriptor->key_version + 1);
} else {
header = EntryHeader::Valid(entry_header_format_.magic,
entry_header_format_.checksum,
key,
value,
+ partition_.alignment_bytes(),
key_descriptor->key_version + 1);
}
- DBG("Appending entry with key version: %zx", size_t(header.key_version()));
+ DBG("Appending %zu B entry with key version: %x",
+ header.size(),
+ unsigned(header.key_version()));
Address address = NextWritableAddress(sector);
DBG("Appending to address: %zx", size_t(address));
diff --git a/pw_kvs/pw_kvs_private/format.h b/pw_kvs/pw_kvs_private/format.h
index da72026..2e9094e 100644
--- a/pw_kvs/pw_kvs_private/format.h
+++ b/pw_kvs/pw_kvs_private/format.h
@@ -29,6 +29,8 @@
// EntryHeader represents a key-value entry as stored in flash.
class EntryHeader {
public:
+ static constexpr size_t kMinAlignmentBytes = 16;
+
EntryHeader() = default;
// Creates a new EntryHeader for a valid (non-deleted) entry.
@@ -36,17 +38,30 @@
ChecksumAlgorithm* algorithm,
std::string_view key,
span<const std::byte> value,
+ size_t alignment_bytes,
uint32_t key_version) {
- return EntryHeader(magic, algorithm, key, value, value.size(), key_version);
+ return EntryHeader(magic,
+ algorithm,
+ key,
+ value,
+ value.size(),
+ alignment_bytes,
+ key_version);
}
// Creates a new EntryHeader for a tombstone entry, which marks a deleted key.
static EntryHeader Tombstone(uint32_t magic,
ChecksumAlgorithm* algorithm,
std::string_view key,
+ size_t alignment_bytes,
uint32_t key_version) {
- return EntryHeader(
- magic, algorithm, key, {}, kDeletedValueLength, key_version);
+ return EntryHeader(magic,
+ algorithm,
+ key,
+ {},
+ kDeletedValueLength,
+ alignment_bytes,
+ key_version);
}
Status VerifyChecksum(ChecksumAlgorithm* algorithm,
@@ -57,54 +72,64 @@
FlashPartition::Address header_address,
ChecksumAlgorithm* algorithm) const;
- // Calculates the total size of the entry: header, key, and value.
- static constexpr size_t size(std::string_view key,
+ // Calculates the total size of an entry, including padding.
+ static constexpr size_t size(size_t alignment_bytes,
+ std::string_view key,
span<const std::byte> value) {
- return sizeof(EntryHeader) + key.size() + value.size();
+ return AlignUp(sizeof(EntryHeader) + key.size() + value.size(),
+ alignment_bytes);
}
- size_t size() const {
- return sizeof(EntryHeader) + key_length() + value_length();
- }
+ // Total size of this entry, including padding.
+ size_t size() const { return AlignUp(content_size(), alignment_bytes()); }
uint32_t magic() const { return magic_; }
uint32_t checksum() const { return checksum_; }
- bool deleted() const {
- return (key_value_length_ >> kValueLengthShift) == kDeletedValueLength;
+ // The length of the key in bytes. Keys are not null terminated.
+ size_t key_length() const { return key_length_bytes_; }
+
+ static constexpr size_t max_key_length() { return kKeyLengthMask; }
+
+ void set_key_length(uint32_t key_length) { key_length_bytes_ = key_length; }
+
+ // The length of the value, which is 0 if this is a tombstone entry.
+ size_t value_length() const { return deleted() ? 0u : value_length_bytes_; }
+
+ static constexpr size_t max_value_length() { return 0xFFFE; }
+
+ void set_value_length(uint16_t value_length) {
+ value_length_bytes_ = value_length;
}
- size_t key_length() const { return key_value_length_ & kKeyLengthMask; }
- void set_key_length(uint32_t key_length) {
- key_value_length_ = key_length | (~kKeyLengthMask & key_value_length_);
- }
-
- size_t value_length() const {
- return deleted() ? 0u : (key_value_length_ >> kValueLengthShift);
- }
- void set_value_length(uint32_t value_length) {
- key_value_length_ = (value_length << kValueLengthShift) |
- (kKeyLengthMask & key_value_length_);
- }
+ size_t alignment_bytes() const { return (alignment_units_ + 1) * 16; }
uint32_t key_version() const { return key_version_; }
+ // True if this is a tombstone entry.
+ bool deleted() const { return value_length_bytes_ == kDeletedValueLength; }
+
private:
+ // The total size of the entry, excluding padding.
+ size_t content_size() const {
+ return sizeof(EntryHeader) + key_length() + value_length();
+ }
+
static constexpr uint32_t kNoChecksum = 0;
static constexpr uint32_t kKeyLengthMask = 0b111111;
- static constexpr uint32_t kValueLengthShift = 8;
- static constexpr uint32_t kDeletedValueLength = 0xFFFFFF;
+ static constexpr uint16_t kDeletedValueLength = 0xFFFF;
EntryHeader(uint32_t magic,
ChecksumAlgorithm* algorithm,
std::string_view key,
span<const std::byte> value,
- uint32_t value_length_field,
+ uint16_t value_length_bytes,
+ size_t alignment_bytes,
uint32_t key_version);
static constexpr size_t checked_data_offset() {
- return offsetof(EntryHeader, key_value_length_);
+ return offsetof(EntryHeader, alignment_units_);
}
span<const std::byte> checksum_bytes() const {
@@ -115,15 +140,31 @@
std::string_view key,
span<const std::byte> value) const;
+ static constexpr uint8_t alignment_bytes_to_units(size_t alignment_bytes) {
+ return (alignment_bytes + 15) / 16 - 1; // An alignment of 0 is invalid.
+ }
+
uint32_t magic_;
uint32_t checksum_;
- // 6 bits, 0: 5 - key - maximum 64 characters
- // 2 bits, 6: 7 - reserved
- // 24 bits, 8:31 - value - maximum 16MB
- uint32_t key_value_length_;
+
+ // Stores the alignment in 16-byte units, starting from 16. To calculate the
+ // number of bytes, add one to this number and multiply by 16.
+ uint8_t alignment_units_;
+
+ // The length of the key in bytes.
+ // 6 bits, 0:5 - key - maximum 64 characters
+ // 2 bits, 6:7 - reserved
+ uint8_t key_length_bytes_;
+
+ // Byte length of the value; maximum of 65534. The max uint16_t value (65535
+ // or 0xFFFF) is reserved to indicate this is a tombstone (deleted) entry.
+ uint16_t value_length_bytes_;
+
+ // The version of the key. Monotonically increasing.
uint32_t key_version_;
};
static_assert(sizeof(EntryHeader) == 16, "EntryHeader should have no padding");
+static_assert(sizeof(EntryHeader) == EntryHeader::kMinAlignmentBytes);
} // namespace pw::kvs
