diff options
Diffstat (limited to 'pw_kvs')
-rw-r--r-- | pw_kvs/BUILD | 10 | ||||
-rw-r--r-- | pw_kvs/BUILD.gn | 15 | ||||
-rw-r--r-- | pw_kvs/entry_test.cc | 57 | ||||
-rw-r--r-- | pw_kvs/format.cc | 13 | ||||
-rw-r--r-- | pw_kvs/key_value_store.cc | 15 | ||||
-rw-r--r-- | pw_kvs/pw_kvs_private/format.h | 101 |
6 files changed, 171 insertions, 40 deletions
diff --git a/pw_kvs/BUILD b/pw_kvs/BUILD index cb9464b02..9f267b0df 100644 --- a/pw_kvs/BUILD +++ b/pw_kvs/BUILD @@ -81,6 +81,16 @@ pw_cc_test( ) 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 c82141e3b..dab9de4d8 100644 --- a/pw_kvs/BUILD.gn +++ b/pw_kvs/BUILD.gn @@ -43,7 +43,10 @@ source_set("pw_kvs") { 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 @@ executable("debug_cli") { pw_test_group("tests") { tests = [ ":checksum_test", + ":entry_test", ":key_value_store_test", ] } @@ -97,6 +101,15 @@ pw_test("checksum_test") { ] } +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 000000000..a726b5f01 --- /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 6abb3b759..d39fe4482 100644 --- a/pw_kvs/format.cc +++ b/pw_kvs/format.cc @@ -26,12 +26,14 @@ EntryHeader::EntryHeader(uint32_t magic, 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 @@ EntryHeader::EntryHeader(uint32_t magic, 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 @@ Status EntryHeader::VerifyChecksumInFlash(FlashPartition* partition, // 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 b19c1637a..5f5bddc85 100644 --- a/pw_kvs/key_value_store.cc +++ b/pw_kvs/key_value_store.cc @@ -189,8 +189,7 @@ Status KeyValueStore::LoadEntry(Address entry_address, 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 @@ Status KeyValueStore::WriteEntryForExistingKey(KeyDescriptor* key_descriptor, 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 @@ Status KeyValueStore::WriteEntryForNewKey(string_view key, 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 @@ Status KeyValueStore::AppendEntry(SectorDescriptor* sector, 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 da720269a..2e9094e1e 100644 --- a/pw_kvs/pw_kvs_private/format.h +++ b/pw_kvs/pw_kvs_private/format.h @@ -29,6 +29,8 @@ namespace pw::kvs { // 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 @@ class EntryHeader { 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 @@ class EntryHeader { 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_; } - 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_); - } + static constexpr size_t max_key_length() { return kKeyLengthMask; } - 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_); + 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 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 @@ class EntryHeader { 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 |