pw_kvs/entry.cc - pigweed/pigweed - Git at Google

 // 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.

 #define PW_LOG_MODULE_NAME "KVS"
 #define PW_LOG_LEVEL PW_KVS_LOG_LEVEL

 #include "pw_kvs/internal/entry.h"

 #include <cinttypes>
 #include <cstring>

 #include "pw_kvs_private/config.h"
 #include "pw_log/log.h"
 #include "pw_status/try.h"

 namespace pw::kvs::internal {

 static_assert(
     kMaxFlashAlignment >= Entry::kMinAlignmentBytes,
     "Flash alignment is required to be at least Entry::kMinAlignmentBytes");

 constexpr size_t kWriteBufferSize =
     std::max(kMaxFlashAlignment, 4 * Entry::kMinAlignmentBytes);

 using std::byte;

 Status Entry::Read(FlashPartition& partition,
                    Address address,
                    const internal::EntryFormats& formats,
                    Entry* entry) {
   EntryHeader header;
   PW_TRY(partition.Read(address, sizeof(header), &header));

   if (partition.AppearsErased(std::as_bytes(std::span(&header.magic, 1)))) {
     return Status::NotFound();
   }
   if (header.key_length_bytes > kMaxKeyLength) {
     return Status::DataLoss();
   }

   const EntryFormat* format = formats.Find(header.magic);
   if (format == nullptr) {
     PW_LOG_ERROR("Found corrupt magic: %" PRIx32 " at address %u",
                  header.magic,
                  unsigned(address));
     return Status::DataLoss();
   }

   *entry = Entry(&partition, address, *format, header);
   return OkStatus();
 }

 Status Entry::ReadKey(FlashPartition& partition,
                       Address address,
                       size_t key_length,
                       char* key) {
   if (key_length == 0u || key_length > kMaxKeyLength) {
     return Status::DataLoss();
   }

   return partition.Read(address + sizeof(EntryHeader), key_length, key)
       .status();
 }

 Entry::Entry(FlashPartition& partition,
              Address address,
              const EntryFormat& format,
              Key key,
              std::span<const byte> value,
              uint16_t value_size_bytes,
              uint32_t transaction_id)
     : Entry(&partition,
             address,
             format,
             {.magic = format.magic,
              .checksum = 0,
              .alignment_units =
                  alignment_bytes_to_units(partition.alignment_bytes()),
              .key_length_bytes = static_cast<uint8_t>(key.size()),
              .value_size_bytes = value_size_bytes,
              .transaction_id = transaction_id}) {
   if (checksum_algo_ != nullptr) {
     std::span<const byte> checksum = CalculateChecksum(key, value);
     std::memcpy(&header_.checksum,
                 checksum.data(),
                 std::min(checksum.size(), sizeof(header_.checksum)));
   }
 }

 StatusWithSize Entry::Write(Key key, std::span<const byte> value) const {
   FlashPartition::Output flash(partition(), address_);
   return AlignedWrite<kWriteBufferSize>(flash,
                                         alignment_bytes(),
                                         {std::as_bytes(std::span(&header_, 1)),
                                          std::as_bytes(std::span(key)),
                                          value});
 }

 Status Entry::Update(const EntryFormat& new_format,
                      uint32_t new_transaction_id) {
   checksum_algo_ = new_format.checksum;
   header_.magic = new_format.magic;
   header_.alignment_units =
       alignment_bytes_to_units(partition_->alignment_bytes());
   header_.transaction_id = new_transaction_id;

   // If we could write the header last, we could avoid reading the entry twice
   // when moving an entry. However, to support alignments greater than the
   // header size, we first read the entire value to calculate the new checksum,
   // then write the full entry in WriteFrom.
   return CalculateChecksumFromFlash();
 }

 StatusWithSize Entry::Copy(Address new_address) const {
   PW_LOG_DEBUG("Copying entry from %u to %u as ID %" PRIu32,
                unsigned(address()),
                unsigned(new_address),
                transaction_id());

   FlashPartition::Output output(partition(), new_address);
   AlignedWriterBuffer<kWriteBufferSize> writer(alignment_bytes(), output);

   // Use this object's header rather than the header in flash of flash, since
   // this Entry may have been updated.
   PW_TRY_WITH_SIZE(writer.Write(&header_, sizeof(header_)));

   // Write only the key and value from the original entry.
   FlashPartition::Input input(partition(), address() + sizeof(EntryHeader));
   PW_TRY_WITH_SIZE(writer.Write(input, key_length() + value_size()));
   return writer.Flush();
 }

 StatusWithSize Entry::ReadValue(std::span<byte> buffer,
                                 size_t offset_bytes) const {
   if (offset_bytes > value_size()) {
     return StatusWithSize::OutOfRange();
   }

   const size_t remaining_bytes = value_size() - offset_bytes;
   const size_t read_size = std::min(buffer.size(), remaining_bytes);

   StatusWithSize result = partition().Read(
       address_ + sizeof(EntryHeader) + key_length() + offset_bytes,
       buffer.subspan(0, read_size));
   PW_TRY_WITH_SIZE(result);

   if (read_size != remaining_bytes) {
     return StatusWithSize::ResourceExhausted(read_size);
   }
   return StatusWithSize(read_size);
 }

 Status Entry::ValueMatches(std::span<const std::byte> value) const {
   if (value_size() != value.size_bytes()) {
     return Status::NotFound();
   }

   Address address = address_ + sizeof(EntryHeader) + key_length();
   Address end = address + value_size();
   const std::byte* value_ptr = value.data();

   std::array<std::byte, 2 * kMinAlignmentBytes> buffer;
   while (address < end) {
     const size_t read_size = std::min(size_t(end - address), buffer.size());
     PW_TRY(partition_->Read(address, std::span(buffer).first(read_size)));

     if (std::memcmp(buffer.data(), value_ptr, read_size) != 0) {
       return Status::NotFound();
     }

     address += read_size;
     value_ptr += read_size;
   }

   return OkStatus();
 }

 Status Entry::VerifyChecksum(Key key, std::span<const byte> value) const {
   if (checksum_algo_ == nullptr) {
     return header_.checksum == 0 ? OkStatus() : Status::DataLoss();
   }
   CalculateChecksum(key, value);
   return checksum_algo_->Verify(checksum_bytes());
 }

 Status Entry::VerifyChecksumInFlash() const {
   // Read the entire entry piece-by-piece into a small buffer. If the entry is
   // 32 B or less, only one read is required.
   union {
     EntryHeader header_to_verify;
     byte buffer[sizeof(EntryHeader) * 2];
   };

   size_t bytes_to_read = size();
   size_t read_size = std::min(sizeof(buffer), bytes_to_read);

   Address read_address = address_;

   // Read the first chunk, which includes the header, and compare the checksum.
   PW_TRY(partition().Read(read_address, read_size, buffer));

   if (header_to_verify.checksum != header_.checksum) {
     PW_LOG_ERROR("Expected checksum 0x%08" PRIx32 ", found 0x%08" PRIx32,
                  header_.checksum,
                  header_to_verify.checksum);
     return Status::DataLoss();
   }

   if (checksum_algo_ == nullptr) {
     return header_.checksum == 0 ? OkStatus() : Status::DataLoss();
   }

   // The checksum is calculated as if the header's checksum field were 0.
   header_to_verify.checksum = 0;

   checksum_algo_->Reset();

   while (true) {
     // Add the chunk in the buffer to the checksum.
     checksum_algo_->Update(buffer, read_size);

     bytes_to_read -= read_size;
     if (bytes_to_read == 0u) {
       break;
     }

     // Read the next chunk into the buffer.
     read_address += read_size;
     read_size = std::min(sizeof(buffer), bytes_to_read);
     PW_TRY(partition().Read(read_address, read_size, buffer));
   }

   checksum_algo_->Finish();
   return checksum_algo_->Verify(checksum_bytes());
 }

 void Entry::DebugLog() const {
   PW_LOG_DEBUG("Entry [%s]: ", deleted() ? "tombstone" : "present");
   PW_LOG_DEBUG("   Address      = 0x%x", unsigned(address_));
   PW_LOG_DEBUG("   Transaction  = %u", unsigned(transaction_id()));
   PW_LOG_DEBUG("   Magic        = 0x%x", unsigned(magic()));
   PW_LOG_DEBUG("   Checksum     = 0x%x", unsigned(header_.checksum));
   PW_LOG_DEBUG("   Key length   = 0x%x", unsigned(key_length()));
   PW_LOG_DEBUG("   Value length = 0x%x", unsigned(value_size()));
   PW_LOG_DEBUG("   Entry size   = 0x%x", unsigned(size()));
   PW_LOG_DEBUG("   Alignment    = 0x%x", unsigned(alignment_bytes()));
 }

 std::span<const byte> Entry::CalculateChecksum(
     const Key key, std::span<const byte> value) const {
   checksum_algo_->Reset();

   {
     EntryHeader header_for_checksum = header_;
     header_for_checksum.checksum = 0;

     checksum_algo_->Update(&header_for_checksum, sizeof(header_for_checksum));
     checksum_algo_->Update(std::as_bytes(std::span(key)));
     checksum_algo_->Update(value);
   }

   AddPaddingBytesToChecksum();

   return checksum_algo_->Finish();
 }

 Status Entry::CalculateChecksumFromFlash() {
   header_.checksum = 0;

   if (checksum_algo_ == nullptr) {
     return OkStatus();
   }

   checksum_algo_->Reset();
   checksum_algo_->Update(&header_, sizeof(header_));

   Address address = address_ + sizeof(EntryHeader);
   // To handle alignment changes, do not read the padding. The padding is added
   // after checksumming the key and value from flash.
   const Address end = address_ + content_size();

   std::array<std::byte, 2 * kMinAlignmentBytes> buffer;
   while (address < end) {
     const size_t read_size = std::min(size_t(end - address), buffer.size());
     PW_TRY(partition_->Read(address, std::span(buffer).first(read_size)));

     checksum_algo_->Update(buffer.data(), read_size);
     address += read_size;
   }

   AddPaddingBytesToChecksum();

   std::span checksum = checksum_algo_->Finish();
   std::memcpy(&header_.checksum,
               checksum.data(),
               std::min(checksum.size(), sizeof(header_.checksum)));
   return OkStatus();
 }

 void Entry::AddPaddingBytesToChecksum() const {
   constexpr byte padding[kMinAlignmentBytes - 1] = {};
   size_t padding_to_add = Padding(content_size(), alignment_bytes());

   while (padding_to_add != 0u) {
     const size_t chunk_size = std::min(padding_to_add, sizeof(padding));
     checksum_algo_->Update(padding, chunk_size);
     padding_to_add -= chunk_size;
   }
 }

 }  // namespace pw::kvs::internal
	// 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.

	#define PW_LOG_MODULE_NAME "KVS"
	#define PW_LOG_LEVEL PW_KVS_LOG_LEVEL

	#include "pw_kvs/internal/entry.h"

	#include <cinttypes>
	#include <cstring>

	#include "pw_kvs_private/config.h"
	#include "pw_log/log.h"
	#include "pw_status/try.h"

	namespace pw::kvs::internal {

	static_assert(
	kMaxFlashAlignment >= Entry::kMinAlignmentBytes,
	"Flash alignment is required to be at least Entry::kMinAlignmentBytes");

	constexpr size_t kWriteBufferSize =
	std::max(kMaxFlashAlignment, 4 * Entry::kMinAlignmentBytes);

	using std::byte;

	Status Entry::Read(FlashPartition& partition,
	Address address,
	const internal::EntryFormats& formats,
	Entry* entry) {
	EntryHeader header;
	PW_TRY(partition.Read(address, sizeof(header), &header));

	if (partition.AppearsErased(std::as_bytes(std::span(&header.magic, 1)))) {
	return Status::NotFound();
	}
	if (header.key_length_bytes > kMaxKeyLength) {
	return Status::DataLoss();
	}

	const EntryFormat* format = formats.Find(header.magic);
	if (format == nullptr) {
	PW_LOG_ERROR("Found corrupt magic: %" PRIx32 " at address %u",
	header.magic,
	unsigned(address));
	return Status::DataLoss();
	}

	entry = Entry(&partition, address, format, header);
	return OkStatus();
	}

	Status Entry::ReadKey(FlashPartition& partition,
	Address address,
	size_t key_length,
	char* key) {
	if (key_length == 0u \|\| key_length > kMaxKeyLength) {
	return Status::DataLoss();
	}

	return partition.Read(address + sizeof(EntryHeader), key_length, key)
	.status();
	}

	Entry::Entry(FlashPartition& partition,
	Address address,
	const EntryFormat& format,
	Key key,
	std::span<const byte> value,
	uint16_t value_size_bytes,
	uint32_t transaction_id)
	: Entry(&partition,
	address,
	format,
	{.magic = format.magic,
	.checksum = 0,
	.alignment_units =
	alignment_bytes_to_units(partition.alignment_bytes()),
	.key_length_bytes = static_cast<uint8_t>(key.size()),
	.value_size_bytes = value_size_bytes,
	.transaction_id = transaction_id}) {
	if (checksum_algo_ != nullptr) {
	std::span<const byte> checksum = CalculateChecksum(key, value);
	std::memcpy(&header_.checksum,
	checksum.data(),
	std::min(checksum.size(), sizeof(header_.checksum)));
	}
	}

	StatusWithSize Entry::Write(Key key, std::span<const byte> value) const {
	FlashPartition::Output flash(partition(), address_);
	return AlignedWrite<kWriteBufferSize>(flash,
	alignment_bytes(),
	{std::as_bytes(std::span(&header_, 1)),
	std::as_bytes(std::span(key)),
	value});
	}

	Status Entry::Update(const EntryFormat& new_format,
	uint32_t new_transaction_id) {
	checksum_algo_ = new_format.checksum;
	header_.magic = new_format.magic;
	header_.alignment_units =
	alignment_bytes_to_units(partition_->alignment_bytes());
	header_.transaction_id = new_transaction_id;

	// If we could write the header last, we could avoid reading the entry twice
	// when moving an entry. However, to support alignments greater than the
	// header size, we first read the entire value to calculate the new checksum,
	// then write the full entry in WriteFrom.
	return CalculateChecksumFromFlash();
	}

	StatusWithSize Entry::Copy(Address new_address) const {
	PW_LOG_DEBUG("Copying entry from %u to %u as ID %" PRIu32,
	unsigned(address()),
	unsigned(new_address),
	transaction_id());

	FlashPartition::Output output(partition(), new_address);
	AlignedWriterBuffer<kWriteBufferSize> writer(alignment_bytes(), output);

	// Use this object's header rather than the header in flash of flash, since
	// this Entry may have been updated.
	PW_TRY_WITH_SIZE(writer.Write(&header_, sizeof(header_)));

	// Write only the key and value from the original entry.
	FlashPartition::Input input(partition(), address() + sizeof(EntryHeader));
	PW_TRY_WITH_SIZE(writer.Write(input, key_length() + value_size()));
	return writer.Flush();
	}

	StatusWithSize Entry::ReadValue(std::span<byte> buffer,
	size_t offset_bytes) const {
	if (offset_bytes > value_size()) {
	return StatusWithSize::OutOfRange();
	}

	const size_t remaining_bytes = value_size() - offset_bytes;
	const size_t read_size = std::min(buffer.size(), remaining_bytes);

	StatusWithSize result = partition().Read(
	address_ + sizeof(EntryHeader) + key_length() + offset_bytes,
	buffer.subspan(0, read_size));
	PW_TRY_WITH_SIZE(result);

	if (read_size != remaining_bytes) {
	return StatusWithSize::ResourceExhausted(read_size);
	}
	return StatusWithSize(read_size);
	}

	Status Entry::ValueMatches(std::span<const std::byte> value) const {
	if (value_size() != value.size_bytes()) {
	return Status::NotFound();
	}

	Address address = address_ + sizeof(EntryHeader) + key_length();
	Address end = address + value_size();
	const std::byte* value_ptr = value.data();

	std::array<std::byte, 2 * kMinAlignmentBytes> buffer;
	while (address < end) {
	const size_t read_size = std::min(size_t(end - address), buffer.size());
	PW_TRY(partition_->Read(address, std::span(buffer).first(read_size)));

	if (std::memcmp(buffer.data(), value_ptr, read_size) != 0) {
	return Status::NotFound();
	}

	address += read_size;
	value_ptr += read_size;
	}

	return OkStatus();
	}

	Status Entry::VerifyChecksum(Key key, std::span<const byte> value) const {
	if (checksum_algo_ == nullptr) {
	return header_.checksum == 0 ? OkStatus() : Status::DataLoss();
	}
	CalculateChecksum(key, value);
	return checksum_algo_->Verify(checksum_bytes());
	}

	Status Entry::VerifyChecksumInFlash() const {
	// Read the entire entry piece-by-piece into a small buffer. If the entry is
	// 32 B or less, only one read is required.
	union {
	EntryHeader header_to_verify;
	byte buffer[sizeof(EntryHeader) * 2];
	};

	size_t bytes_to_read = size();
	size_t read_size = std::min(sizeof(buffer), bytes_to_read);

	Address read_address = address_;

	// Read the first chunk, which includes the header, and compare the checksum.
	PW_TRY(partition().Read(read_address, read_size, buffer));

	if (header_to_verify.checksum != header_.checksum) {
	PW_LOG_ERROR("Expected checksum 0x%08" PRIx32 ", found 0x%08" PRIx32,
	header_.checksum,
	header_to_verify.checksum);
	return Status::DataLoss();
	}

	if (checksum_algo_ == nullptr) {
	return header_.checksum == 0 ? OkStatus() : Status::DataLoss();
	}

	// The checksum is calculated as if the header's checksum field were 0.
	header_to_verify.checksum = 0;

	checksum_algo_->Reset();

	while (true) {
	// Add the chunk in the buffer to the checksum.
	checksum_algo_->Update(buffer, read_size);

	bytes_to_read -= read_size;
	if (bytes_to_read == 0u) {
	break;
	}

	// Read the next chunk into the buffer.
	read_address += read_size;
	read_size = std::min(sizeof(buffer), bytes_to_read);
	PW_TRY(partition().Read(read_address, read_size, buffer));
	}

	checksum_algo_->Finish();
	return checksum_algo_->Verify(checksum_bytes());
	}

	void Entry::DebugLog() const {
	PW_LOG_DEBUG("Entry [%s]: ", deleted() ? "tombstone" : "present");
	PW_LOG_DEBUG(" Address = 0x%x", unsigned(address_));
	PW_LOG_DEBUG(" Transaction = %u", unsigned(transaction_id()));
	PW_LOG_DEBUG(" Magic = 0x%x", unsigned(magic()));
	PW_LOG_DEBUG(" Checksum = 0x%x", unsigned(header_.checksum));
	PW_LOG_DEBUG(" Key length = 0x%x", unsigned(key_length()));
	PW_LOG_DEBUG(" Value length = 0x%x", unsigned(value_size()));
	PW_LOG_DEBUG(" Entry size = 0x%x", unsigned(size()));
	PW_LOG_DEBUG(" Alignment = 0x%x", unsigned(alignment_bytes()));
	}

	std::span<const byte> Entry::CalculateChecksum(
	const Key key, std::span<const byte> value) const {
	checksum_algo_->Reset();

	{
	EntryHeader header_for_checksum = header_;
	header_for_checksum.checksum = 0;

	checksum_algo_->Update(&header_for_checksum, sizeof(header_for_checksum));
	checksum_algo_->Update(std::as_bytes(std::span(key)));
	checksum_algo_->Update(value);
	}

	AddPaddingBytesToChecksum();

	return checksum_algo_->Finish();
	}

	Status Entry::CalculateChecksumFromFlash() {
	header_.checksum = 0;

	if (checksum_algo_ == nullptr) {
	return OkStatus();
	}

	checksum_algo_->Reset();
	checksum_algo_->Update(&header_, sizeof(header_));

	Address address = address_ + sizeof(EntryHeader);
	// To handle alignment changes, do not read the padding. The padding is added
	// after checksumming the key and value from flash.
	const Address end = address_ + content_size();

	std::array<std::byte, 2 * kMinAlignmentBytes> buffer;
	while (address < end) {
	const size_t read_size = std::min(size_t(end - address), buffer.size());
	PW_TRY(partition_->Read(address, std::span(buffer).first(read_size)));

	checksum_algo_->Update(buffer.data(), read_size);
	address += read_size;
	}

	AddPaddingBytesToChecksum();

	std::span checksum = checksum_algo_->Finish();
	std::memcpy(&header_.checksum,
	checksum.data(),
	std::min(checksum.size(), sizeof(header_.checksum)));
	return OkStatus();
	}

	void Entry::AddPaddingBytesToChecksum() const {
	constexpr byte padding[kMinAlignmentBytes - 1] = {};
	size_t padding_to_add = Padding(content_size(), alignment_bytes());

	while (padding_to_add != 0u) {
	const size_t chunk_size = std::min(padding_to_add, sizeof(padding));
	checksum_algo_->Update(padding, chunk_size);
	padding_to_add -= chunk_size;
	}
	}

	} // namespace pw::kvs::internal