third_party/pigweed/repo/pw_kvs/public/pw_kvs/internal/entry.h

   1 // Copyright 2020 The Pigweed Authors
   2 //
   3 // Licensed under the Apache License, Version 2.0 (the "License"); you may not
   4 // use this file except in compliance with the License. You may obtain a copy of
   5 // the License at
   6 //
   7 //     https://www.apache.org/licenses/LICENSE-2.0
   8 //
   9 // Unless required by applicable law or agreed to in writing, software
  10 // distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
  11 // WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
  12 // License for the specific language governing permissions and limitations under
  13 // the License.
  14
  15 // This file defines classes for managing the in-flash format for KVS entires.
  16 #pragma once
  17
  18 #include <algorithm>
  19 #include <array>
  20 #include <cstddef>
  21 #include <cstdint>
  22 #include <span>
  23
  24 #include "pw_kvs/alignment.h"
  25 #include "pw_kvs/checksum.h"
  26 #include "pw_kvs/flash_memory.h"
  27 #include "pw_kvs/format.h"
  28 #include "pw_kvs/internal/hash.h"
  29 #include "pw_kvs/internal/key_descriptor.h"
  30 #include "pw_kvs/key.h"
  31
  32 namespace pw {
  33 namespace kvs {
  34 namespace internal {
  35
  36 // Entry represents a key-value entry in a flash partition.
  37 class Entry {
  38  public:
  39   static constexpr size_t kMinAlignmentBytes = sizeof(EntryHeader);
  40   static constexpr size_t kMaxKeyLength = 0b111111;
  41
  42   using Address = FlashPartition::Address;
  43
  44   // Buffer capable of holding any valid key (without a null terminator);
  45   using KeyBuffer = std::array<char, kMaxKeyLength>;
  46
  47   // Returns flash partition Read error codes, or one of the following:
  48   //
  49   //          OK: successfully read the header and initialized the Entry
  50   //   NOT_FOUND: read the header, but the data appears to be erased
  51   //   DATA_LOSS: read the header, but it contained invalid data
  52   //
  53   static Status Read(FlashPartition& partition,
  54                      Address address,
  55                      const internal::EntryFormats& formats,
  56                      Entry* entry);
  57
  58   // Reads a key into a buffer, which must be at least key_length bytes.
  59   static Status ReadKey(FlashPartition& partition,
  60                         Address address,
  61                         size_t key_length,
  62                         char* key);
  63
  64   // Creates a new Entry for a valid (non-deleted) entry.
  65   static Entry Valid(FlashPartition& partition,
  66                      Address address,
  67                      const EntryFormat& format,
  68                      Key key,
  69                      std::span<const std::byte> value,
  70                      uint32_t transaction_id) {
  71     return Entry(
  72         partition, address, format, key, value, value.size(), transaction_id);
  73   }
  74
  75   // Creates a new Entry for a tombstone entry, which marks a deleted key.
  76   static Entry Tombstone(FlashPartition& partition,
  77                          Address address,
  78                          const EntryFormat& format,
  79                          Key key,
  80                          uint32_t transaction_id) {
  81     return Entry(partition,
  82                  address,
  83                  format,
  84                  key,
  85                  {},
  86                  kDeletedValueLength,
  87                  transaction_id);
  88   }
  89
  90   Entry() = default;
  91
  92   KeyDescriptor descriptor(Key key) const { return descriptor(Hash(key)); }
  93
  94   KeyDescriptor descriptor(uint32_t key_hash) const {
  95     return KeyDescriptor{key_hash,
  96                          transaction_id(),
  97                          deleted() ? EntryState::kDeleted : EntryState::kValid};
  98   }
  99
 100   StatusWithSize Write(Key key, std::span<const std::byte> value) const;
 101
 102   // Changes the format and transcation ID for this entry. In order to calculate
 103   // the new checksum, the entire entry is read into a small stack-allocated
 104   // buffer. The updated entry may be written to flash using the Copy function.
 105   Status Update(const EntryFormat& new_format, uint32_t new_transaction_id);
 106
 107   // Writes this entry at a new address. The key and value are read from the
 108   // entry's current address. The Entry object's header, which may be newer than
 109   // what is in flash, is used.
 110   StatusWithSize Copy(Address new_address) const;
 111
 112   // Reads a key into a buffer, which must be large enough for a max-length key.
 113   // If successful, the size is returned in the StatusWithSize. The key is not
 114   // null terminated.
 115   template <size_t kSize>
 116   StatusWithSize ReadKey(std::array<char, kSize>& key) const {
 117     static_assert(kSize >= kMaxKeyLength);
 118     return StatusWithSize(
 119         ReadKey(partition(), address_, key_length(), key.data()), key_length());
 120   }
 121
 122   StatusWithSize ReadValue(std::span<std::byte> buffer,
 123                            size_t offset_bytes = 0) const;
 124
 125   Status ValueMatches(std::span<const std::byte> value) const;
 126
 127   Status VerifyChecksum(Key key, std::span<const std::byte> value) const;
 128
 129   Status VerifyChecksumInFlash() const;
 130
 131   // Calculates the total size of an entry, including padding.
 132   static size_t size(const FlashPartition& partition,
 133                      Key key,
 134                      std::span<const std::byte> value) {
 135     return AlignUp(sizeof(EntryHeader) + key.size() + value.size(),
 136                    std::max(partition.alignment_bytes(), kMinAlignmentBytes));
 137   }
 138
 139   // Byte size of overhead (not-key, not-value) in an entry. Does not include
 140   // any paddding used to get proper size alignment.
 141   static constexpr size_t entry_overhead() { return sizeof(EntryHeader); }
 142
 143   Address address() const { return address_; }
 144
 145   void set_address(Address address) { address_ = address; }
 146
 147   // The address at which the next possible entry could be located.
 148   Address next_address() const { return address() + size(); }
 149
 150   // Total size of this entry, including padding.
 151   size_t size() const { return AlignUp(content_size(), alignment_bytes()); }
 152
 153   // The length of the key in bytes. Keys are not null terminated.
 154   size_t key_length() const { return header_.key_length_bytes; }
 155
 156   // The size of the value, without padding. The size is 0 if this is a
 157   // tombstone entry.
 158   size_t value_size() const {
 159     return deleted() ? 0u : header_.value_size_bytes;
 160   }
 161
 162   uint32_t magic() const { return header_.magic; }
 163
 164   uint32_t transaction_id() const { return header_.transaction_id; }
 165
 166   // True if this is a tombstone entry.
 167   bool deleted() const {
 168     return header_.value_size_bytes == kDeletedValueLength;
 169   }
 170
 171   void DebugLog() const;
 172
 173  private:
 174   static constexpr uint16_t kDeletedValueLength = 0xFFFF;
 175
 176   Entry(FlashPartition& partition,
 177         Address address,
 178         const EntryFormat& format,
 179         Key key,
 180         std::span<const std::byte> value,
 181         uint16_t value_size_bytes,
 182         uint32_t transaction_id);
 183
 184   constexpr Entry(FlashPartition* partition,
 185                   Address address,
 186                   const EntryFormat& format,
 187                   EntryHeader header)
 188       : partition_(partition),
 189         address_(address),
 190         checksum_algo_(format.checksum),
 191         header_(header) {}
 192
 193   FlashPartition& partition() const { return *partition_; }
 194
 195   size_t alignment_bytes() const { return (header_.alignment_units + 1) * 16; }
 196
 197   // The total size of the entry, excluding padding.
 198   size_t content_size() const {
 199     return sizeof(EntryHeader) + key_length() + value_size();
 200   }
 201
 202   std::span<const std::byte> checksum_bytes() const {
 203     return std::as_bytes(std::span<const uint32_t>(&header_.checksum, 1));
 204   }
 205
 206   std::span<const std::byte> CalculateChecksum(
 207       Key key, std::span<const std::byte> value) const;
 208
 209   Status CalculateChecksumFromFlash();
 210
 211   // Update the checksum with 0s to pad the entry to its alignment boundary.
 212   void AddPaddingBytesToChecksum() const;
 213
 214   static constexpr uint8_t alignment_bytes_to_units(size_t alignment_bytes) {
 215     return (alignment_bytes + 15) / 16 - 1;  // An alignment of 0 is invalid.
 216   }
 217
 218   FlashPartition* partition_;
 219   Address address_;
 220   ChecksumAlgorithm* checksum_algo_;
 221   EntryHeader header_;
 222 };
 223
 224 }  // namespace internal
 225 }  // namespace kvs
 226 }  // namespace pw