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

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(&sector, EntryHeader::size(key, value)));
+  TRY(FindOrRecoverSectorWithSpace(
+      &sector, 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(&sector, EntryHeader::size(key, value)));
+  TRY(FindOrRecoverSectorWithSpace(
+      &sector, 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