blob: 11e410249be13c6a37827f5b5e0b69ae9fe28fe3 [file] [log] [blame]
// 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 DUMP_KVS_STATE_TO_FILE 0
#define USE_MEMORY_BUFFER 1
#include "pw_kvs/key_value_store.h"
#include <array>
#include <cstdio>
#include <cstring>
#include "pw_span/span.h"
#if DUMP_KVS_STATE_TO_FILE
#include <vector>
#endif // DUMP_KVS_STATE_TO_FILE
#include "gtest/gtest.h"
#include "pw_assert/check.h"
#include "pw_bytes/array.h"
#include "pw_checksum/crc16_ccitt.h"
#include "pw_kvs/crc16_checksum.h"
#include "pw_kvs/fake_flash_memory.h"
#include "pw_kvs/flash_memory.h"
#include "pw_kvs/internal/entry.h"
#include "pw_kvs_private/config.h"
#include "pw_log/log.h"
#include "pw_log/shorter.h"
#include "pw_status/status.h"
#include "pw_string/string_builder.h"
namespace pw::kvs {
namespace {
using internal::EntryHeader;
constexpr size_t kMaxEntries = 256;
constexpr size_t kMaxUsableSectors = 256;
// This is a self contained flash unit with both memory and a single partition.
template <uint32_t kSectorSizeBytes, uint16_t kSectorCount>
struct FlashWithPartitionFake {
// Default to 16 byte alignment, which is common in practice.
FlashWithPartitionFake() : FlashWithPartitionFake(16) {}
FlashWithPartitionFake(size_t alignment_bytes)
: memory(alignment_bytes), partition(&memory, 0, memory.sector_count()) {}
FakeFlashMemoryBuffer<kSectorSizeBytes, kSectorCount> memory;
FlashPartition partition;
public:
#if DUMP_KVS_STATE_TO_FILE
Status Dump(const char* filename) {
std::FILE* out_file = std::fopen(filename, "w+");
if (out_file == nullptr) {
PW_LOG_ERROR("Failed to dump to %s", filename);
return Status::DataLoss();
}
std::vector<std::byte> out_vec(memory.size_bytes());
Status status =
memory.Read(0, span<std::byte>(out_vec.data(), out_vec.size()));
if (status != OkStatus()) {
fclose(out_file);
return status;
}
size_t written =
std::fwrite(out_vec.data(), 1, memory.size_bytes(), out_file);
if (written != memory.size_bytes()) {
PW_LOG_ERROR("Failed to dump to %s, written=%u",
filename,
static_cast<unsigned>(written));
status = Status::DataLoss();
} else {
PW_LOG_INFO("Dumped to %s", filename);
status = OkStatus();
}
fclose(out_file);
return status;
}
#else
Status Dump(const char*) { return OkStatus(); }
#endif // DUMP_KVS_STATE_TO_FILE
};
typedef FlashWithPartitionFake<4 * 128 /*sector size*/, 6 /*sectors*/> Flash;
FakeFlashMemoryBuffer<1024, 60> large_test_flash(8);
FlashPartition large_test_partition(&large_test_flash,
0,
large_test_flash.sector_count());
constexpr std::array<const char*, 3> keys{"TestKey1", "Key2", "TestKey3"};
ChecksumCrc16 checksum;
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat default_format{.magic = 0xa6cb3c16,
.checksum = &checksum};
} // namespace
TEST(InitCheck, TooFewSectors) {
// Use test flash with 1 x 4k sectors, 16 byte alignment
FakeFlashMemoryBuffer<4 * 1024, 1> test_flash(16);
FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat format{.magic = 0x89bb14d2, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&test_partition,
format);
EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
}
TEST(InitCheck, ZeroSectors) {
// Use test flash with 1 x 4k sectors, 16 byte alignment
FakeFlashMemoryBuffer<4 * 1024, 1> test_flash(16);
// Set FlashPartition to have 0 sectors.
FlashPartition test_partition(&test_flash, 0, 0);
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat format{.magic = 0xd1da57c1, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&test_partition,
format);
EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
}
TEST(InitCheck, TooManySectors) {
// Use test flash with 1 x 4k sectors, 16 byte alignment
FakeFlashMemoryBuffer<4 * 1024, 5> test_flash(16);
// Set FlashPartition to have 0 sectors.
FlashPartition test_partition(&test_flash, 0, test_flash.sector_count());
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat format{.magic = 0x610f6d17, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, 2> kvs(&test_partition, format);
EXPECT_EQ(kvs.Init(), Status::FailedPrecondition());
}
#define ASSERT_OK(expr) ASSERT_EQ(OkStatus(), expr)
#define EXPECT_OK(expr) EXPECT_EQ(OkStatus(), expr)
TEST(InMemoryKvs, WriteOneKeyMultipleTimes) {
// Create and erase the fake flash. It will persist across reloads.
Flash flash;
ASSERT_OK(flash.partition.Erase());
int num_reloads = 2;
for (int reload = 0; reload < num_reloads; ++reload) {
DBG("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
DBG("xxx xxxx");
DBG("xxx Reload %2d xxxx", reload);
DBG("xxx xxxx");
DBG("xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx");
// Create and initialize the KVS. For KVS magic value always use a random 32
// bit integer rather than a human readable 4 bytes. See pw_kvs/format.h for
// more information.
constexpr EntryFormat format{.magic = 0x83a9257, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
format);
ASSERT_OK(kvs.Init());
// Write the same entry many times.
const char* key = "abcd";
const size_t num_writes = 99;
uint32_t written_value;
EXPECT_EQ(kvs.size(), (reload == 0) ? 0 : 1u);
for (uint32_t i = 0; i < num_writes; ++i) {
DBG("PUT #%zu for key %s with value %zu", size_t(i), key, size_t(i));
written_value = i + 0xfc; // Prevent accidental pass with zero.
EXPECT_OK(kvs.Put(key, written_value));
EXPECT_EQ(kvs.size(), 1u);
}
// Verify that we can read the value back.
DBG("GET final value for key: %s", key);
uint32_t actual_value;
EXPECT_OK(kvs.Get(key, &actual_value));
EXPECT_EQ(actual_value, written_value);
char fname_buf[64] = {'\0'};
snprintf(&fname_buf[0],
sizeof(fname_buf),
"WriteOneKeyMultipleTimes_%d.bin",
reload);
ASSERT_EQ(OkStatus(), flash.Dump(fname_buf));
}
}
TEST(InMemoryKvs, WritingMultipleKeysIncreasesSize) {
// Create and erase the fake flash.
Flash flash;
ASSERT_OK(flash.partition.Erase());
// Create and initialize the KVS. For KVS magic value always use a random 32
// bit integer rather than a human readable 4 bytes. See pw_kvs/format.h for
// more information.
constexpr EntryFormat format{.magic = 0x2ed3a058, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
format);
ASSERT_OK(kvs.Init());
// Write the same entry many times.
const size_t num_writes = 10;
EXPECT_EQ(kvs.size(), 0u);
for (size_t i = 0; i < num_writes; ++i) {
StringBuffer<150> key;
key << "key_" << i;
DBG("PUT #%zu for key %s with value %zu", i, key.c_str(), i);
size_t value = i + 77; // Prevent accidental pass with zero.
EXPECT_OK(kvs.Put(key.view(), value));
EXPECT_EQ(kvs.size(), i + 1);
}
ASSERT_EQ(OkStatus(), flash.Dump("WritingMultipleKeysIncreasesSize.bin"));
}
TEST(InMemoryKvs, WriteAndReadOneKey) {
// Create and erase the fake flash.
Flash flash;
ASSERT_OK(flash.partition.Erase());
// Create and initialize the KVS.
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat format{.magic = 0x5d70896, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
format);
ASSERT_OK(kvs.Init());
// Add one entry.
const char* key = "Key1";
DBG("PUT value for key: %s", key);
uint8_t written_value = 0xDA;
ASSERT_OK(kvs.Put(key, written_value));
EXPECT_EQ(kvs.size(), 1u);
DBG("GET value for key: %s", key);
uint8_t actual_value;
ASSERT_OK(kvs.Get(key, &actual_value));
EXPECT_EQ(actual_value, written_value);
EXPECT_EQ(kvs.size(), 1u);
}
TEST(InMemoryKvs, WriteOneKeyValueMultipleTimes) {
// Create and erase the fake flash.
Flash flash;
ASSERT_OK(flash.partition.Erase());
// Create and initialize the KVS.
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
default_format);
ASSERT_OK(kvs.Init());
// Add one entry, with the same key and value, multiple times.
const char* key = "Key1";
uint8_t written_value = 0xDA;
for (int i = 0; i < 50; i++) {
DBG("PUT [%d] value for key: %s", i, key);
ASSERT_OK(kvs.Put(key, written_value));
EXPECT_EQ(kvs.size(), 1u);
}
DBG("GET value for key: %s", key);
uint8_t actual_value;
ASSERT_OK(kvs.Get(key, &actual_value));
EXPECT_EQ(actual_value, written_value);
// Verify that only one entry was written to the KVS.
EXPECT_EQ(kvs.size(), 1u);
EXPECT_EQ(kvs.transaction_count(), 1u);
KeyValueStore::StorageStats stats = kvs.GetStorageStats();
EXPECT_EQ(stats.reclaimable_bytes, 0u);
}
TEST(InMemoryKvs, Basic) {
const char* key1 = "Key1";
const char* key2 = "Key2";
// Create and erase the fake flash.
Flash flash;
ASSERT_EQ(OkStatus(), flash.partition.Erase());
// Create and initialize the KVS.
// For KVS magic value always use a random 32 bit integer rather than a
// human readable 4 bytes. See pw_kvs/format.h for more information.
constexpr EntryFormat format{.magic = 0x7bf19895, .checksum = nullptr};
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
format);
ASSERT_OK(kvs.Init());
// Add two entries with different keys and values.
uint8_t value1 = 0xDA;
ASSERT_OK(kvs.Put(key1, as_bytes(span(&value1, sizeof(value1)))));
EXPECT_EQ(kvs.size(), 1u);
uint32_t value2 = 0xBAD0301f;
ASSERT_OK(kvs.Put(key2, value2));
EXPECT_EQ(kvs.size(), 2u);
// Verify data
uint32_t test2;
EXPECT_OK(kvs.Get(key2, &test2));
uint8_t test1;
ASSERT_OK(kvs.Get(key1, &test1));
EXPECT_EQ(test1, value1);
EXPECT_EQ(test2, value2);
EXPECT_EQ(kvs.size(), 2u);
}
TEST(InMemoryKvs, CallingEraseTwice_NothingWrittenToFlash) {
// Create and erase the fake flash.
Flash flash;
ASSERT_EQ(OkStatus(), flash.partition.Erase());
// Create and initialize the KVS.
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
default_format);
ASSERT_OK(kvs.Init());
const uint8_t kValue = 0xDA;
ASSERT_EQ(OkStatus(), kvs.Put(keys[0], kValue));
ASSERT_EQ(OkStatus(), kvs.Delete(keys[0]));
// Compare before / after checksums to verify that nothing was written.
const uint16_t crc = checksum::Crc16Ccitt::Calculate(flash.memory.buffer());
EXPECT_EQ(kvs.Delete(keys[0]), Status::NotFound());
EXPECT_EQ(crc, checksum::Crc16Ccitt::Calculate(flash.memory.buffer()));
}
class LargeEmptyInitializedKvs : public ::testing::Test {
protected:
LargeEmptyInitializedKvs() : kvs_(&large_test_partition, default_format) {
PW_CHECK_OK(large_test_partition.Erase());
PW_CHECK_OK(kvs_.Init());
}
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs_;
};
TEST_F(LargeEmptyInitializedKvs, Basic) {
const uint8_t kValue1 = 0xDA;
const uint8_t kValue2 = 0x12;
uint8_t value;
ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
EXPECT_EQ(kvs_.size(), 1u);
ASSERT_EQ(OkStatus(), kvs_.Delete(keys[0]));
EXPECT_EQ(kvs_.Get(keys[0], &value), Status::NotFound());
ASSERT_EQ(OkStatus(), kvs_.Put(keys[1], kValue1));
ASSERT_EQ(OkStatus(), kvs_.Put(keys[2], kValue2));
ASSERT_EQ(OkStatus(), kvs_.Delete(keys[1]));
EXPECT_EQ(OkStatus(), kvs_.Get(keys[2], &value));
EXPECT_EQ(kValue2, value);
ASSERT_EQ(kvs_.Get(keys[1], &value), Status::NotFound());
EXPECT_EQ(kvs_.size(), 1u);
}
TEST_F(LargeEmptyInitializedKvs, FullMaintenance) {
const uint8_t kValue1 = 0xDA;
const uint8_t kValue2 = 0x12;
// Write a key and write again with a different value, resulting in a stale
// entry from the first write.
ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue2));
EXPECT_EQ(kvs_.size(), 1u);
KeyValueStore::StorageStats stats = kvs_.GetStorageStats();
EXPECT_EQ(stats.sector_erase_count, 0u);
EXPECT_GT(stats.reclaimable_bytes, 0u);
// Do regular FullMaintenance, which should not touch the sector with valid
// data.
EXPECT_EQ(OkStatus(), kvs_.FullMaintenance());
stats = kvs_.GetStorageStats();
EXPECT_EQ(stats.sector_erase_count, 0u);
EXPECT_GT(stats.reclaimable_bytes, 0u);
// Do aggressive FullMaintenance, which should GC the sector with valid data,
// resulting in no reclaimable bytes and an erased sector.
EXPECT_EQ(OkStatus(), kvs_.HeavyMaintenance());
stats = kvs_.GetStorageStats();
EXPECT_EQ(stats.sector_erase_count, 1u);
EXPECT_EQ(stats.reclaimable_bytes, 0u);
}
TEST_F(LargeEmptyInitializedKvs, KeyDeletionMaintenance) {
const uint8_t kValue1 = 0xDA;
const uint8_t kValue2 = 0x12;
uint8_t val = 0;
// Write and delete a key. The key should be gone, but the size should be 1.
ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
ASSERT_EQ(kvs_.size(), 1u);
ASSERT_EQ(OkStatus(), kvs_.Delete(keys[0]));
// Ensure the key is indeed gone and the size is 1 before continuing.
ASSERT_EQ(kvs_.Get(keys[0], &val), Status::NotFound());
ASSERT_EQ(kvs_.size(), 0u);
ASSERT_EQ(kvs_.total_entries_with_deleted(), 1u);
KeyValueStore::StorageStats stats = kvs_.GetStorageStats();
EXPECT_EQ(stats.sector_erase_count, 0u);
EXPECT_GT(stats.reclaimable_bytes, 0u);
// Do aggressive FullMaintenance, which should GC the sector with valid data,
// resulting in no reclaimable bytes and an erased sector.
EXPECT_EQ(OkStatus(), kvs_.HeavyMaintenance());
stats = kvs_.GetStorageStats();
EXPECT_EQ(stats.reclaimable_bytes, 0u);
ASSERT_EQ(kvs_.size(), 0u);
if (PW_KVS_REMOVE_DELETED_KEYS_IN_HEAVY_MAINTENANCE) {
EXPECT_GT(stats.sector_erase_count, 1u);
ASSERT_EQ(kvs_.total_entries_with_deleted(), 0u);
} else { // The deleted entries are only removed if that feature is enabled.
EXPECT_EQ(stats.sector_erase_count, 1u);
ASSERT_EQ(kvs_.total_entries_with_deleted(), 1u);
}
// Do it again but with 2 keys and keep one.
ASSERT_EQ(OkStatus(), kvs_.Put(keys[0], kValue1));
ASSERT_EQ(OkStatus(), kvs_.Put(keys[1], kValue2));
ASSERT_EQ(kvs_.size(), 2u);
ASSERT_EQ(OkStatus(), kvs_.Delete(keys[0]));
// Ensure the key is indeed gone and the size is 1 before continuing.
ASSERT_EQ(kvs_.Get(keys[0], &val), Status::NotFound());
ASSERT_EQ(kvs_.size(), 1u);
ASSERT_EQ(kvs_.total_entries_with_deleted(), 2u);
// Do aggressive FullMaintenance, which should GC the sector with valid data,
// resulting in no reclaimable bytes and an erased sector.
EXPECT_EQ(OkStatus(), kvs_.HeavyMaintenance());
stats = kvs_.GetStorageStats();
ASSERT_EQ(kvs_.size(), 1u);
if (PW_KVS_REMOVE_DELETED_KEYS_IN_HEAVY_MAINTENANCE) {
ASSERT_EQ(kvs_.total_entries_with_deleted(), 1u);
} else { // The deleted entries are only removed if that feature is enabled.
ASSERT_EQ(kvs_.total_entries_with_deleted(), 2u);
}
// Read back the second key to make sure it is still valid.
ASSERT_EQ(kvs_.Get(keys[1], &val), OkStatus());
ASSERT_EQ(val, kValue2);
}
TEST(InMemoryKvs, Put_MaxValueSize) {
// Create and erase the fake flash.
Flash flash;
ASSERT_EQ(OkStatus(), flash.partition.Erase());
// Create and initialize the KVS.
KeyValueStoreBuffer<kMaxEntries, kMaxUsableSectors> kvs(&flash.partition,
default_format);
ASSERT_OK(kvs.Init());
size_t max_key_value_size = kvs.max_key_value_size_bytes();
EXPECT_EQ(max_key_value_size,
KeyValueStore::max_key_value_size_bytes(
flash.partition.sector_size_bytes()));
size_t max_value_size =
flash.partition.sector_size_bytes() - sizeof(EntryHeader) - 1;
EXPECT_EQ(max_key_value_size, (max_value_size + 1));
// Use the large_test_flash as a big chunk of data for the Put statement.
ASSERT_GT(sizeof(large_test_flash), max_value_size + 2 * sizeof(EntryHeader));
auto big_data = as_bytes(span(&large_test_flash, 1));
EXPECT_EQ(OkStatus(), kvs.Put("K", big_data.subspan(0, max_value_size)));
// Larger than maximum is rejected.
EXPECT_EQ(Status::InvalidArgument(),
kvs.Put("K", big_data.subspan(0, max_value_size + 1)));
EXPECT_EQ(Status::InvalidArgument(), kvs.Put("K", big_data));
}
} // namespace pw::kvs