From 01ecf332ff9f0c8f61e493cdca116f58d80bb5fb Mon Sep 17 00:00:00 2001 From: Nick Brassel Date: Mon, 27 Jun 2022 07:18:21 +1000 Subject: Generic wear-leveling algorithm (#16996) * Initial import of wear-leveling algorithm. * Alignment. * Docs tweaks. * Lock/unlock. * Update quantum/wear_leveling/wear_leveling_internal.h Co-authored-by: Stefan Kerkmann * More tests, fix issue with consolidation when unlocked. * More tests. * Review comments. * Add plumbing for FNV1a. * Another test checking that checksum mismatch clears the cache. * Check that the write log still gets played back. Co-authored-by: Stefan Kerkmann --- quantum/wear_leveling/tests/backing_mocks.cpp | 154 ++++ quantum/wear_leveling/tests/backing_mocks.hpp | 210 ++++++ quantum/wear_leveling/tests/rules.mk | 66 ++ quantum/wear_leveling/tests/testlist.mk | 6 + .../wear_leveling/tests/wear_leveling_2byte.cpp | 228 ++++++ .../tests/wear_leveling_2byte_optimized_writes.cpp | 295 ++++++++ .../wear_leveling/tests/wear_leveling_4byte.cpp | 193 +++++ .../wear_leveling/tests/wear_leveling_8byte.cpp | 178 +++++ .../wear_leveling/tests/wear_leveling_general.cpp | 204 ++++++ quantum/wear_leveling/wear_leveling.c | 779 +++++++++++++++++++++ quantum/wear_leveling/wear_leveling.h | 54 ++ quantum/wear_leveling/wear_leveling_internal.h | 145 ++++ 12 files changed, 2512 insertions(+) create mode 100644 quantum/wear_leveling/tests/backing_mocks.cpp create mode 100644 quantum/wear_leveling/tests/backing_mocks.hpp create mode 100644 quantum/wear_leveling/tests/rules.mk create mode 100644 quantum/wear_leveling/tests/testlist.mk create mode 100644 quantum/wear_leveling/tests/wear_leveling_2byte.cpp create mode 100644 quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp create mode 100644 quantum/wear_leveling/tests/wear_leveling_4byte.cpp create mode 100644 quantum/wear_leveling/tests/wear_leveling_8byte.cpp create mode 100644 quantum/wear_leveling/tests/wear_leveling_general.cpp create mode 100644 quantum/wear_leveling/wear_leveling.c create mode 100644 quantum/wear_leveling/wear_leveling.h create mode 100644 quantum/wear_leveling/wear_leveling_internal.h (limited to 'quantum') diff --git a/quantum/wear_leveling/tests/backing_mocks.cpp b/quantum/wear_leveling/tests/backing_mocks.cpp new file mode 100644 index 0000000000..1dbb26f8e7 --- /dev/null +++ b/quantum/wear_leveling/tests/backing_mocks.cpp @@ -0,0 +1,154 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Backing Store Mock implementation +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +void MockBackingStore::reset_instance() { + for (auto&& e : backing_storage) + e.reset(); + + locked = true; + + backing_erasure_count = 0; + backing_max_write_count = 0; + backing_total_write_count = 0; + + backing_init_invoke_count = 0; + backing_unlock_invoke_count = 0; + backing_erase_invoke_count = 0; + backing_write_invoke_count = 0; + backing_lock_invoke_count = 0; + + init_success_callback = [](std::uint64_t) { return true; }; + erase_success_callback = [](std::uint64_t) { return true; }; + unlock_success_callback = [](std::uint64_t) { return true; }; + write_success_callback = [](std::uint64_t, std::uint32_t) { return true; }; + lock_success_callback = [](std::uint64_t) { return true; }; + + write_log.clear(); +} + +bool MockBackingStore::init(void) { + ++backing_init_invoke_count; + + if (init_success_callback) { + return init_success_callback(backing_init_invoke_count); + } + return true; +} + +bool MockBackingStore::unlock(void) { + ++backing_unlock_invoke_count; + + EXPECT_TRUE(is_locked()) << "Attempted to unlock but was not locked"; + locked = false; + + if (unlock_success_callback) { + return unlock_success_callback(backing_unlock_invoke_count); + } + return true; +} + +bool MockBackingStore::erase(void) { + ++backing_erase_invoke_count; + + // Erase each slot + for (std::size_t i = 0; i < backing_storage.size(); ++i) { + // Drop out of erase early with failure if we need to + if (erase_success_callback && !erase_success_callback(backing_erase_invoke_count)) { + append_log(true); + return false; + } + + backing_storage[i].erase(); + } + + // Keep track of the erase in the write log so that we can verify during tests + append_log(true); + + ++backing_erasure_count; + return true; +} + +bool MockBackingStore::write(uint32_t address, backing_store_int_t value) { + ++backing_write_invoke_count; + + // precondition: value's buffer size already matches BACKING_STORE_WRITE_SIZE + EXPECT_TRUE(address % BACKING_STORE_WRITE_SIZE == 0) << "Supplied address was not aligned with the backing store integral size"; + EXPECT_TRUE(address + BACKING_STORE_WRITE_SIZE <= WEAR_LEVELING_BACKING_SIZE) << "Address would result of out-of-bounds access"; + EXPECT_FALSE(is_locked()) << "Write was attempted without being unlocked first"; + + // Drop out of write early with failure if we need to + if (write_success_callback && !write_success_callback(backing_write_invoke_count, address)) { + return false; + } + + // Write the complement as we're simulating flash memory -- 0xFF means 0x00 + std::size_t index = address / BACKING_STORE_WRITE_SIZE; + backing_storage[index].set(~value); + + // Keep track of the write log so that we can verify during tests + append_log(address, value); + + // Keep track of the total number of writes into the backing store + ++backing_total_write_count; + + return true; +} + +bool MockBackingStore::lock(void) { + ++backing_lock_invoke_count; + + EXPECT_FALSE(is_locked()) << "Attempted to lock but was not unlocked"; + locked = true; + + if (lock_success_callback) { + return lock_success_callback(backing_lock_invoke_count); + } + return true; +} + +bool MockBackingStore::read(uint32_t address, backing_store_int_t& value) const { + // precondition: value's buffer size already matches BACKING_STORE_WRITE_SIZE + EXPECT_TRUE(address % BACKING_STORE_WRITE_SIZE == 0) << "Supplied address was not aligned with the backing store integral size"; + EXPECT_TRUE(address + BACKING_STORE_WRITE_SIZE <= WEAR_LEVELING_BACKING_SIZE) << "Address would result of out-of-bounds access"; + + // Read and take the complement as we're simulating flash memory -- 0xFF means 0x00 + std::size_t index = address / BACKING_STORE_WRITE_SIZE; + value = ~backing_storage[index].get(); + + return true; +} + +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// +// Backing Implementation +//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////// + +extern "C" bool backing_store_init(void) { + return MockBackingStore::Instance().init(); +} + +extern "C" bool backing_store_unlock(void) { + return MockBackingStore::Instance().unlock(); +} + +extern "C" bool backing_store_erase(void) { + return MockBackingStore::Instance().erase(); +} + +extern "C" bool backing_store_write(uint32_t address, backing_store_int_t value) { + return MockBackingStore::Instance().write(address, value); +} + +extern "C" bool backing_store_lock(void) { + return MockBackingStore::Instance().lock(); +} + +extern "C" bool backing_store_read(uint32_t address, backing_store_int_t* value) { + return MockBackingStore::Instance().read(address, *value); +} diff --git a/quantum/wear_leveling/tests/backing_mocks.hpp b/quantum/wear_leveling/tests/backing_mocks.hpp new file mode 100644 index 0000000000..e7af7895f3 --- /dev/null +++ b/quantum/wear_leveling/tests/backing_mocks.hpp @@ -0,0 +1,210 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#pragma once +#include +#include +#include +#include +#include +#include +#include + +extern "C" { +#include "fnv.h" +#include "wear_leveling.h" +#include "wear_leveling_internal.h" +}; + +// Maximum number of mock write log entries to keep +using MOCK_WRITE_LOG_MAX_ENTRIES = std::integral_constant; +// Complement to the backing store integral, for emulating flash erases of all bytes=0xFF +using BACKING_STORE_INTEGRAL_COMPLEMENT = std::integral_constant; +// Total number of elements stored in the backing arrays +using BACKING_STORE_ELEMENT_COUNT = std::integral_constant; + +class MockBackingStoreElement { + private: + backing_store_int_t value; + std::size_t writes; + std::size_t erases; + + public: + MockBackingStoreElement() : value(BACKING_STORE_INTEGRAL_COMPLEMENT::value), writes(0), erases(0) {} + void reset() { + erase(); + writes = 0; + erases = 0; + } + void erase() { + if (!is_erased()) { + ++erases; + } + value = BACKING_STORE_INTEGRAL_COMPLEMENT::value; + } + backing_store_int_t get() const { + return value; + } + void set(const backing_store_int_t& v) { + EXPECT_TRUE(is_erased()) << "Attempted write at index which isn't empty."; + value = v; + ++writes; + } + std::size_t num_writes() const { + return writes; + } + std::size_t num_erases() const { + return erases; + } + bool is_erased() const { + return value == BACKING_STORE_INTEGRAL_COMPLEMENT::value; + } +}; + +struct MockBackingStoreLogEntry { + MockBackingStoreLogEntry(uint32_t address, backing_store_int_t value) : address(address), value(value), erased(false) {} + MockBackingStoreLogEntry(bool erased) : address(0), value(0), erased(erased) {} + uint32_t address = 0; // The address of the operation + backing_store_int_t value = 0; // The value of the operation + bool erased = false; // Whether the entire backing store was erased +}; + +class MockBackingStore { + private: + MockBackingStore() { + reset_instance(); + } + + // Type containing each of the entries and the write counts + using storage_t = std::array; + + // Whether the backing store is locked + bool locked; + // The actual data stored in the emulated flash + storage_t backing_storage; + // The number of erase cycles that have occurred + std::uint64_t backing_erasure_count; + // The max number of writes to an element of the backing store + std::uint64_t backing_max_write_count; + // The total number of writes to all elements of the backing store + std::uint64_t backing_total_write_count; + // The write log for the backing store + std::vector write_log; + + // The number of times each API was invoked + std::uint64_t backing_init_invoke_count; + std::uint64_t backing_unlock_invoke_count; + std::uint64_t backing_erase_invoke_count; + std::uint64_t backing_write_invoke_count; + std::uint64_t backing_lock_invoke_count; + + // Whether init should succeed + std::function init_success_callback; + // Whether erase should succeed + std::function erase_success_callback; + // Whether unlocks should succeed + std::function unlock_success_callback; + // Whether writes should succeed + std::function write_success_callback; + // Whether locks should succeed + std::function lock_success_callback; + + template + void append_log(Args&&... args) { + if (write_log.size() < MOCK_WRITE_LOG_MAX_ENTRIES::value) { + write_log.emplace_back(std::forward(args)...); + } + } + + public: + static MockBackingStore& Instance() { + static MockBackingStore instance; + return instance; + } + + std::uint64_t erasure_count() const { + return backing_erasure_count; + } + std::uint64_t max_write_count() const { + return backing_max_write_count; + } + std::uint64_t total_write_count() const { + return backing_total_write_count; + } + + // The number of times each API was invoked + std::uint64_t init_invoke_count() const { + return backing_init_invoke_count; + } + std::uint64_t unlock_invoke_count() const { + return backing_unlock_invoke_count; + } + std::uint64_t erase_invoke_count() const { + return backing_erase_invoke_count; + } + std::uint64_t write_invoke_count() const { + return backing_write_invoke_count; + } + std::uint64_t lock_invoke_count() const { + return backing_lock_invoke_count; + } + + // Clear out the internal data for the next run + void reset_instance(); + + bool is_locked() const { + return locked; + } + + // APIs for the backing store + bool init(); + bool unlock(); + bool erase(); + bool write(std::uint32_t address, backing_store_int_t value); + bool lock(); + bool read(std::uint32_t address, backing_store_int_t& value) const; + + // Control over when init/writes/erases should succeed + void set_init_callback(std::function callback) { + init_success_callback = callback; + } + void set_erase_callback(std::function callback) { + erase_success_callback = callback; + } + void set_unlock_callback(std::function callback) { + unlock_success_callback = callback; + } + void set_write_callback(std::function callback) { + write_success_callback = callback; + } + void set_lock_callback(std::function callback) { + lock_success_callback = callback; + } + + auto storage_begin() const -> decltype(backing_storage.begin()) { + return backing_storage.begin(); + } + auto storage_end() const -> decltype(backing_storage.end()) { + return backing_storage.end(); + } + + auto storage_begin() -> decltype(backing_storage.begin()) { + return backing_storage.begin(); + } + auto storage_end() -> decltype(backing_storage.end()) { + return backing_storage.end(); + } + + auto log_begin() -> decltype(write_log.begin()) { + return write_log.begin(); + } + auto log_end() -> decltype(write_log.end()) { + return write_log.end(); + } + + auto log_begin() const -> decltype(write_log.begin()) { + return write_log.begin(); + } + auto log_end() const -> decltype(write_log.end()) { + return write_log.end(); + } +}; diff --git a/quantum/wear_leveling/tests/rules.mk b/quantum/wear_leveling/tests/rules.mk new file mode 100644 index 0000000000..4d7a964049 --- /dev/null +++ b/quantum/wear_leveling/tests/rules.mk @@ -0,0 +1,66 @@ +wear_leveling_common_DEFS := \ + -DWEAR_LEVELING_TESTS +wear_leveling_common_SRC := \ + $(LIB_PATH)/fnv/qmk_fnv_type_validation.c \ + $(LIB_PATH)/fnv/hash_32a.c \ + $(LIB_PATH)/fnv/hash_64a.c \ + $(QUANTUM_PATH)/wear_leveling/wear_leveling.c \ + $(QUANTUM_PATH)/wear_leveling/tests/backing_mocks.cpp +wear_leveling_common_INC := \ + $(LIB_PATH)/fnv \ + $(QUANTUM_PATH)/wear_leveling + +wear_leveling_general_DEFS := \ + $(wear_leveling_common_DEFS) \ + -DBACKING_STORE_WRITE_SIZE=2 \ + -DWEAR_LEVELING_BACKING_SIZE=48 \ + -DWEAR_LEVELING_LOGICAL_SIZE=16 +wear_leveling_general_SRC := \ + $(wear_leveling_common_SRC) \ + $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_general.cpp +wear_leveling_general_INC := \ + $(wear_leveling_common_INC) + +wear_leveling_2byte_optimized_writes_DEFS := \ + $(wear_leveling_common_DEFS) \ + -DBACKING_STORE_WRITE_SIZE=2 \ + -DWEAR_LEVELING_BACKING_SIZE=65536 \ + -DWEAR_LEVELING_LOGICAL_SIZE=32768 +wear_leveling_2byte_optimized_writes_SRC := \ + $(wear_leveling_common_SRC) \ + $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp +wear_leveling_2byte_optimized_writes_INC := \ + $(wear_leveling_common_INC) + +wear_leveling_2byte_DEFS := \ + $(wear_leveling_common_DEFS) \ + -DBACKING_STORE_WRITE_SIZE=2 \ + -DWEAR_LEVELING_BACKING_SIZE=48 \ + -DWEAR_LEVELING_LOGICAL_SIZE=16 +wear_leveling_2byte_SRC := \ + $(wear_leveling_common_SRC) \ + $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_2byte.cpp +wear_leveling_2byte_INC := \ + $(wear_leveling_common_INC) + +wear_leveling_4byte_DEFS := \ + $(wear_leveling_common_DEFS) \ + -DBACKING_STORE_WRITE_SIZE=4 \ + -DWEAR_LEVELING_BACKING_SIZE=48 \ + -DWEAR_LEVELING_LOGICAL_SIZE=16 +wear_leveling_4byte_SRC := \ + $(wear_leveling_common_SRC) \ + $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_4byte.cpp +wear_leveling_4byte_INC := \ + $(wear_leveling_common_INC) + +wear_leveling_8byte_DEFS := \ + $(wear_leveling_common_DEFS) \ + -DBACKING_STORE_WRITE_SIZE=8 \ + -DWEAR_LEVELING_BACKING_SIZE=48 \ + -DWEAR_LEVELING_LOGICAL_SIZE=16 +wear_leveling_8byte_SRC := \ + $(wear_leveling_common_SRC) \ + $(QUANTUM_PATH)/wear_leveling/tests/wear_leveling_8byte.cpp +wear_leveling_8byte_INC := \ + $(wear_leveling_common_INC) \ No newline at end of file diff --git a/quantum/wear_leveling/tests/testlist.mk b/quantum/wear_leveling/tests/testlist.mk new file mode 100644 index 0000000000..32cfc178b4 --- /dev/null +++ b/quantum/wear_leveling/tests/testlist.mk @@ -0,0 +1,6 @@ +TEST_LIST += \ + wear_leveling_general \ + wear_leveling_2byte_optimized_writes \ + wear_leveling_2byte \ + wear_leveling_4byte \ + wear_leveling_8byte diff --git a/quantum/wear_leveling/tests/wear_leveling_2byte.cpp b/quantum/wear_leveling/tests/wear_leveling_2byte.cpp new file mode 100644 index 0000000000..b749c32b04 --- /dev/null +++ b/quantum/wear_leveling/tests/wear_leveling_2byte.cpp @@ -0,0 +1,228 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +class WearLeveling2Byte : public ::testing::Test { + protected: + void SetUp() override { + MockBackingStore::Instance().reset_instance(); + wear_leveling_init(); + } +}; + +static std::array verify_data; + +static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) { + memcpy(&verify_data[address], value, length); + return wear_leveling_write(address, value, length); +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location. + */ +TEST_F(WearLeveling2Byte, FirstWriteOccursAfterHash) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred. + */ +TEST_F(WearLeveling2Byte, FirstWriteOccursAfterHash_AfterErase) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + wear_leveling_erase(); + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the + * base logical area. + */ +TEST_F(WearLeveling2Byte, ConsolidationOverflow) { + auto& inst = MockBackingStore::Instance(); + + // Generate a test block of data which forces OPTIMIZED_64 writes + std::array testvalue; + + // Write the data + std::iota(testvalue.begin(), testvalue.end(), 0x20); + EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status"; + uint8_t dummy = 0x40; + EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status"; + + // All writes are at address<64, so each logical byte written will generate 1 write log entry, thus 1 backing store write. + // Expected log: + // [0..11]: optimised64, backing address 0x18, logical address 0x00 + // [12]: erase + // [13..20]: consolidated data, backing address 0x00, logical address 0x00 + // [21..24]: FNV1a_64 result, backing address 0x10 + // [25]: optimised64, backing address 0x18, logical address 0x04 + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 26); + + // Verify the backing store writes for the write log + std::size_t index; + write_log_entry_t e; + for (index = 0; index < 12; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, WEAR_LEVELING_LOGICAL_SIZE + 8 + (index * BACKING_STORE_WRITE_SIZE)) << "Invalid write log address"; + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_OPTIMIZED_64) << "Invalid write log entry type"; + } + + // Verify the backing store erase + { + index = 12; + auto write_iter = inst.log_begin() + index; + e.raw16[0] = write_iter->value; + EXPECT_TRUE(write_iter->erased) << "Backing store erase did not occur as required"; + } + + // Verify the backing store writes for consolidation + for (index = 13; index < 21; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, (index - 13) * BACKING_STORE_WRITE_SIZE) << "Invalid write log entry address"; + } + + // Verify the FNV1a_64 write + { + EXPECT_EQ((inst.log_begin() + 21)->address, WEAR_LEVELING_LOGICAL_SIZE) << "Invalid write log address"; + e.raw16[0] = (inst.log_begin() + 21)->value; + e.raw16[1] = (inst.log_begin() + 22)->value; + e.raw16[2] = (inst.log_begin() + 23)->value; + e.raw16[3] = (inst.log_begin() + 24)->value; + EXPECT_EQ(e.raw64, fnv_64a_buf(testvalue.data(), testvalue.size(), FNV1A_64_INIT)) << "Invalid checksum"; // Note that checksum is based on testvalue, as we overwrote one byte and need to consult the consolidated data, not the current + } + + // Verify the final write + EXPECT_EQ((inst.log_begin() + 25)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid write log address"; + + // Verify the data is what we expected + std::array readback; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; + + // Re-init and re-read, verifying the reload capability + EXPECT_NE(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Re-initialisation failed"; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; +} + +/** + * This test verifies multibyte readback gets canceled with an out-of-bounds address. + */ +TEST_F(WearLeveling2Byte, PlaybackReadbackMultibyte_OOB) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + (logstart + 2)->set(0); + (logstart + 3)->set(0); + + // Set up a 2-byte logical write of [0x11,0x12] at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry0.raw8[3] = 0x11; + entry0.raw8[4] = 0x12; + (logstart + 4)->set(~entry0.raw16[0]); + (logstart + 5)->set(~entry0.raw16[1]); + (logstart + 6)->set(~entry0.raw16[2]); + + // Set up a 2-byte logical write of [0x13,0x14] at logical offset 0x1000 (out of bounds) + auto entry1 = LOG_ENTRY_MAKE_MULTIBYTE(0x1000, 2); + entry1.raw8[3] = 0x13; + entry1.raw8[4] = 0x14; + (logstart + 7)->set(~entry1.raw16[0]); + (logstart + 8)->set(~entry1.raw16[1]); + (logstart + 9)->set(~entry1.raw16[2]); + + // Set up a 2-byte logical write of [0x15,0x16] at logical offset 0x01 + auto entry2 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry2.raw8[3] = 0x15; + entry2.raw8[4] = 0x16; + (logstart + 10)->set(~entry2.raw16[0]); + (logstart + 11)->set(~entry2.raw16[1]); + (logstart + 12)->set(~entry2.raw16[2]); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_CONSOLIDATED) << "Readback should have failed and triggered consolidation"; + EXPECT_EQ(inst.erasure_count(), 1) << "Invalid final erase count"; + + uint8_t buf[2]; + wear_leveling_read(0x01, buf, sizeof(buf)); + EXPECT_EQ(buf[0], 0x11) << "Readback should have maintained the previous pre-failure value from the write log"; + EXPECT_EQ(buf[1], 0x12) << "Readback should have maintained the previous pre-failure value from the write log"; +} + +/** + * This test verifies optimized 64 readback gets canceled with an out-of-bounds address. + */ +TEST_F(WearLeveling2Byte, PlaybackReadbackOptimized64_OOB) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + (logstart + 2)->set(0); + (logstart + 3)->set(0); + + // Set up a 1-byte logical write of 0x11 at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x01, 0x11); + (logstart + 4)->set(~entry0.raw16[0]); + + // Set up a 1-byte logical write of 0x11 at logical offset 0x30 (out of bounds) + auto entry1 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x30, 0x11); + (logstart + 5)->set(~entry1.raw16[0]); + + // Set up a 1-byte logical write of 0x12 at logical offset 0x01 + auto entry2 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x01, 0x12); + (logstart + 6)->set(~entry2.raw16[0]); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_CONSOLIDATED) << "Readback should have failed and triggered consolidation"; + EXPECT_EQ(inst.erasure_count(), 1) << "Invalid final erase count"; + uint8_t tmp; + wear_leveling_read(0x01, &tmp, sizeof(tmp)); + EXPECT_EQ(tmp, 0x11) << "Readback should have maintained the previous pre-failure value from the write log"; +} + +/** + * This test verifies word 0/1 readback gets canceled with an out-of-bounds address. + */ +TEST_F(WearLeveling2Byte, PlaybackReadbackWord01_OOB) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + (logstart + 2)->set(0); + (logstart + 3)->set(0); + + // Set up a 1-byte logical write of 1 at logical offset 0x02 + auto entry0 = LOG_ENTRY_MAKE_WORD_01(0x02, 1); + (logstart + 4)->set(~entry0.raw16[0]); + + // Set up a 1-byte logical write of 1 at logical offset 0x1000 (out of bounds) + auto entry1 = LOG_ENTRY_MAKE_WORD_01(0x1000, 1); + (logstart + 5)->set(~entry1.raw16[0]); + + // Set up a 1-byte logical write of 0 at logical offset 0x02 + auto entry2 = LOG_ENTRY_MAKE_WORD_01(0x02, 0); + (logstart + 6)->set(~entry2.raw16[0]); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_CONSOLIDATED) << "Readback should have failed and triggered consolidation"; + EXPECT_EQ(inst.erasure_count(), 1) << "Invalid final erase count"; + uint8_t tmp; + wear_leveling_read(0x02, &tmp, sizeof(tmp)); + EXPECT_EQ(tmp, 1) << "Readback should have maintained the previous pre-failure value from the write log"; +} diff --git a/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp b/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp new file mode 100644 index 0000000000..0b03113c89 --- /dev/null +++ b/quantum/wear_leveling/tests/wear_leveling_2byte_optimized_writes.cpp @@ -0,0 +1,295 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +class WearLeveling2ByteOptimizedWrites : public ::testing::Test { + protected: + void SetUp() override { + MockBackingStore::Instance().reset_instance(); + wear_leveling_init(); + } +}; + +static std::array verify_data; + +static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) { + memcpy(&verify_data[address], value, length); + return wear_leveling_write(address, value, length); +} + +/** + * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size. + */ +TEST_F(WearLeveling2ByteOptimizedWrites, MultibyteBackingStoreWriteCounts) { + auto& inst = MockBackingStore::Instance(); + + for (std::size_t length = 1; length <= 5; ++length) { + // Clear things out + std::fill(verify_data.begin(), verify_data.end(), 0); + inst.reset_instance(); + wear_leveling_init(); + + // Generate a test block of data + std::vector testvalue(length); + std::iota(testvalue.begin(), testvalue.end(), 0x20); + + // Write the data + EXPECT_EQ(test_write(2000, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + + std::size_t expected; + if (length > 3) { + expected = 4; + } else if (length > 1) { + expected = 3; + } else { + expected = 2; + } + + // Check that we got the expected number of write log entries + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected); + } +} + +/** + * This test runs through writing U16 values of `0` or `1` over the entire logical address range, to even addresses only. + * - Addresses <16384 will result in a single optimised backing write + * - Higher addresses will result in a multibyte write of 3 backing writes + */ +TEST_F(WearLeveling2ByteOptimizedWrites, WriteOneThenZeroToEvenAddresses) { + auto& inst = MockBackingStore::Instance(); + + // Only attempt writes for each address up to a limit that would NOT force a consolidated data write. + std::size_t writes_per_loop = (MOCK_WRITE_LOG_MAX_ENTRIES::value / 6) - 1; // Worst case is 6 writes for each pair of writes of 0/1 + std::size_t final_address; + for (uint32_t address = 0; address < WEAR_LEVELING_LOGICAL_SIZE; address += (writes_per_loop * 2)) { + // Clear things out + std::fill(verify_data.begin(), verify_data.end(), 0); + inst.reset_instance(); + wear_leveling_init(); + + // Loop through all the addresses in this range + std::size_t expected = 0; + for (uint32_t offset = 0; offset < (writes_per_loop * 2); offset += 2) { + // If we're about to exceed the limit of the logical store, skip the writes + if (address + offset + 2 > WEAR_LEVELING_LOGICAL_SIZE) { + break; + } + + // The default erased value of the wear-leveling cache is zero, so we write a one first, then a zero, to ensure a backing store write occurs. + uint16_t val = 1; + EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + val = 0; + EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + + std::size_t backing_store_writes_expected = 0; + if (address + offset < 16384) { + // A U16 value of 0/1 at an even address <16384 will result in 1 backing write each, so we need 2 backing writes for 2 logical writes + backing_store_writes_expected = 2; + } else { + // All other addresses result in a multibyte write (3 backing store writes) to write two local bytes of data + backing_store_writes_expected = 6; + } + + // Keep track of the total number of expected writes to the backing store + expected += backing_store_writes_expected; + + // Verify we're at the correct number of writes + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected) << "Write log doesn't match required number of backing store writes for address " << (address + offset); + + // Verify that the write log entries we expect are actually present + std::size_t write_index = expected - backing_store_writes_expected; + auto write_iter = inst.log_begin() + write_index; + write_log_entry_t e; + if (address + offset < 16384) { + // A U16 value of 0/1 at an even address <16384 will result in 1 backing write each, so we need 2 backing writes for 2 logical writes + for (std::size_t i = 0; i < 2; ++i) { + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_WORD_01) << "Invalid write log entry type at " << (address + offset); + ++write_iter; + } + } else { + // Multibyte write + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_MULTIBYTE) << "Invalid write log entry type at " << (address + offset); + EXPECT_EQ(LOG_ENTRY_MULTIBYTE_GET_LENGTH(e), 2) << "Invalid write log entry length at " << (address + offset); + ++write_iter; + } + + // Keep track of the final address written, so we can verify the entire logical range was handled + final_address = address + offset; + } + + // Verify the number of writes that occurred to the backing store + size_t backing_write_count = std::distance(inst.log_begin(), inst.log_end()); + EXPECT_EQ(backing_write_count, expected) << "Invalid write count at address " << address; + + // Verify the data is what we expected + std::array readback; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback for address " << address << " did not match"; + + // Re-init and re-read, testing the reload capability + EXPECT_NE(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Re-initialisation failed"; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback for address " << address << " did not match"; + } + + // Verify the full range of the logical area got written + EXPECT_EQ(final_address, WEAR_LEVELING_LOGICAL_SIZE - 2) << "Invalid final write address"; +} + +/** + * This test runs through writing U16 values of `0` or `1` over the entire logical address range, to odd addresses only. + * - Addresses <63 will result in 2 optimised backing writes + * - Address 63 results in a single optimised backing write for the first logical byte, and a multibyte write of 2 backing writes for the second logical byte + * - Higher addresses will result in a multibyte write of 3 backing writes + */ +TEST_F(WearLeveling2ByteOptimizedWrites, WriteOneThenZeroToOddAddresses) { + auto& inst = MockBackingStore::Instance(); + + // Only attempt writes for each address up to a limit that would NOT force a consolidated data write. + std::size_t writes_per_loop = (MOCK_WRITE_LOG_MAX_ENTRIES::value / 6) - 1; // Worst case is 6 writes for each pair of writes of 0/1 + std::size_t final_address; + for (uint32_t address = 1; address < WEAR_LEVELING_LOGICAL_SIZE; address += (writes_per_loop * 2)) { + // Clear things out + std::fill(verify_data.begin(), verify_data.end(), 0); + inst.reset_instance(); + wear_leveling_init(); + + // Loop through all the addresses in this range + std::size_t expected = 0; + for (uint32_t offset = 0; offset < (writes_per_loop * 2); offset += 2) { + // If we're about to exceed the limit of the logical store, skip the writes + if (address + offset + 2 > WEAR_LEVELING_LOGICAL_SIZE) { + break; + } + + // The default erased value of the wear-leveling cache is zero, so we write a one first, then a zero, to ensure a backing store write occurs. + uint16_t val = 1; + EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + val = 0; + EXPECT_EQ(test_write(address + offset, &val, sizeof(val)), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + + std::size_t backing_store_writes_expected = 0; + if (address + offset < 63) { + // A U16 value of 0/1 at an odd address <64 will result in 2 backing writes each, so we need 4 backing writes for 2 logical writes + backing_store_writes_expected = 4; + } else if (address + offset == 63) { + // If we're straddling the boundary for optimised bytes (addr==64), then the first logical byte is written using the optimised write (1 backing + // store write), and the second logical byte uses a multibyte write (2 backing store writes) + backing_store_writes_expected = 2 // First logical bytes written using optimised log entries + + 4; // Second logical bytes written using multibyte log entries + } else { + // All other addresses result in a multibyte write (3 backing store writes) to write two local bytes of data + backing_store_writes_expected = 6; + } + + // Keep track of the total number of expected writes to the backing store + expected += backing_store_writes_expected; + + // Verify we're at the correct number of writes + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected) << "Write log doesn't match required number of backing store writes for address " << (address + offset); + + // Verify that the write log entries we expect are actually present + std::size_t write_index = expected - backing_store_writes_expected; + auto write_iter = inst.log_begin() + write_index; + write_log_entry_t e; + if (address + offset < 63) { + // A U16 value of 0/1 at an odd address <64 will result in 2 backing writes each, so we need 4 backing writes for 2 logical writes + for (std::size_t i = 0; i < 4; ++i) { + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_OPTIMIZED_64) << "Invalid write log entry type"; + ++write_iter; + } + } else if (address + offset == 63) { + // First log entry is the 64-addr optimised one + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_OPTIMIZED_64) << "Invalid write log entry type"; + ++write_iter; + + // Second log entry is the multibyte entry for the second logical byte + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_MULTIBYTE) << "Invalid write log entry type"; + EXPECT_EQ(LOG_ENTRY_MULTIBYTE_GET_LENGTH(e), 1) << "Invalid write log entry length"; + ++write_iter; + } else { + // Multibyte write + e.raw16[0] = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_MULTIBYTE) << "Invalid write log entry type"; + EXPECT_EQ(LOG_ENTRY_MULTIBYTE_GET_LENGTH(e), 2) << "Invalid write log entry length"; + ++write_iter; + } + + // Keep track of the final address written, so we can verify the entire logical range was handled + final_address = address + offset; + } + + // Verify the number of writes that occurred to the backing store + size_t backing_write_count = std::distance(inst.log_begin(), inst.log_end()); + EXPECT_EQ(backing_write_count, expected) << "Invalid write count at address " << address; + + // Verify the data is what we expected + std::array readback; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback for address " << address << " did not match"; + + // Re-init and re-read, testing the reload capability + EXPECT_NE(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Re-initialisation failed"; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback for address " << address << " did not match"; + } + + // Verify the full range of the logical area got written + EXPECT_EQ(final_address, WEAR_LEVELING_LOGICAL_SIZE - 3) << "Invalid final write address"; +} + +/** + * This test verifies readback after playback of the write log, simulating power loss and reboot. + */ +TEST_F(WearLeveling2ByteOptimizedWrites, PlaybackReadbackOptimized64_Success) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + (logstart + 2)->set(0); + (logstart + 3)->set(0); + + // Set up a 1-byte logical write of 0x11 at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x01, 0x11); + (logstart + 4)->set(~entry0.raw16[0]); // start at offset 4 to skip FNV1a_64 result + + wear_leveling_init(); + uint8_t tmp; + + wear_leveling_read(0x01, &tmp, sizeof(tmp)); + EXPECT_EQ(tmp, 0x11) << "Failed to read back the seeded data"; +} + +/** + * This test verifies readback after playback of the write log, simulating power loss and reboot. + */ +TEST_F(WearLeveling2ByteOptimizedWrites, PlaybackReadbackWord01_Success) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + (logstart + 2)->set(0); + (logstart + 3)->set(0); + + // Set up a 1-byte logical write of 1 at logical offset 0x02 + auto entry0 = LOG_ENTRY_MAKE_WORD_01(0x02, 1); + (logstart + 4)->set(~entry0.raw16[0]); // start at offset 4 to skip FNV1a_64 result + + wear_leveling_init(); + uint8_t tmp; + + wear_leveling_read(0x02, &tmp, sizeof(tmp)); + EXPECT_EQ(tmp, 1) << "Failed to read back the seeded data"; +} diff --git a/quantum/wear_leveling/tests/wear_leveling_4byte.cpp b/quantum/wear_leveling/tests/wear_leveling_4byte.cpp new file mode 100644 index 0000000000..54482c5fe7 --- /dev/null +++ b/quantum/wear_leveling/tests/wear_leveling_4byte.cpp @@ -0,0 +1,193 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +class WearLeveling4Byte : public ::testing::Test { + protected: + void SetUp() override { + MockBackingStore::Instance().reset_instance(); + wear_leveling_init(); + } +}; + +static std::array verify_data; + +static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) { + memcpy(&verify_data[address], value, length); + return wear_leveling_write(address, value, length); +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location. + */ +TEST_F(WearLeveling4Byte, FirstWriteOccursAfterHash) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred. + */ +TEST_F(WearLeveling4Byte, FirstWriteOccursAfterHash_AfterErase) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + wear_leveling_erase(); + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size. + */ +TEST_F(WearLeveling4Byte, MultibyteBackingStoreWriteCounts) { + auto& inst = MockBackingStore::Instance(); + + for (std::size_t length = 1; length <= 5; ++length) { + // Clear things out + std::fill(verify_data.begin(), verify_data.end(), 0); + inst.reset_instance(); + wear_leveling_init(); + + // Generate a test block of data + std::vector testvalue(length); + std::iota(testvalue.begin(), testvalue.end(), 0x20); + + // Write the data + EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + + std::size_t expected; + if (length > 1) { + expected = 2; + } else { + expected = 1; + } + + // Check that we got the expected number of write log entries + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), expected); + } +} + +/** + * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the + * base logical area. + */ +TEST_F(WearLeveling4Byte, ConsolidationOverflow) { + auto& inst = MockBackingStore::Instance(); + + // Generate a test block of data + std::array testvalue; + + // Write the data + std::iota(testvalue.begin(), testvalue.end(), 0x20); + EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status"; + uint8_t dummy = 0x40; + EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status"; + + // Expected log: + // [0,1]: multibyte, 5 bytes, backing address 0x18, logical address 0x00 + // [2,3]: multibyte, 5 bytes, backing address 0x20, logical address 0x05 + // [4,5]: multibyte, 5 bytes, backing address 0x28, logical address 0x0A, triggers consolidation + // [6]: erase + // [7,8]: consolidated data, backing address 0x00, logical address 0x00 + // [9,10]: consolidated data, backing address 0x08, logical address 0x08 + // [11,12]: FNV1a_64 result, backing address 0x10 + // [13]: multibyte, 1 byte, backing address 0x18, logical address 0x04 + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 14); + + // Verify the backing store writes for the write log + std::size_t index; + write_log_entry_t e; + for (index = 0; index < 6; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, WEAR_LEVELING_LOGICAL_SIZE + 8 + (index * BACKING_STORE_WRITE_SIZE)) << "Invalid write log address"; + + // If this is the backing store write that contains the metadata, verify it + if (index % 2 == 0) { + write_log_entry_t e; + e.raw64 = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_MULTIBYTE) << "Invalid write log entry type"; + } + } + + // Verify the backing store erase + { + index = 6; + auto write_iter = inst.log_begin() + index; + e.raw64 = write_iter->value; + EXPECT_TRUE(write_iter->erased) << "Backing store erase did not occur as required"; + } + + // Verify the backing store writes for consolidation + for (index = 7; index < 11; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, (index - 7) * BACKING_STORE_WRITE_SIZE) << "Invalid write log entry address"; + } + + // Verify the FNV1a_64 write + { + EXPECT_EQ((inst.log_begin() + 11)->address, WEAR_LEVELING_LOGICAL_SIZE) << "Invalid write log address"; + e.raw32[0] = (inst.log_begin() + 11)->value; + e.raw32[1] = (inst.log_begin() + 12)->value; + EXPECT_EQ(e.raw64, fnv_64a_buf(testvalue.data(), testvalue.size(), FNV1A_64_INIT)) << "Invalid checksum"; // Note that checksum is based on testvalue, as we overwrote one byte and need to consult the consolidated data, not the current + } + + // Verify the final write + EXPECT_EQ((inst.log_begin() + 13)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid write log address"; + + // Verify the data is what we expected + std::array readback; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; + + // Re-init and re-read, verifying the reload capability + EXPECT_NE(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Re-initialisation failed"; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; +} + +/** + * This test verifies multibyte readback gets canceled with an out-of-bounds address. + */ +TEST_F(WearLeveling4Byte, PlaybackReadbackMultibyte_OOB) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + (logstart + 1)->set(0); + + // Set up a 2-byte logical write of [0x11,0x12] at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry0.raw8[3] = 0x11; + entry0.raw8[4] = 0x12; + (logstart + 2)->set(~entry0.raw32[0]); + (logstart + 3)->set(~entry0.raw32[1]); + + // Set up a 2-byte logical write of [0x13,0x14] at logical offset 0x1000 (out of bounds) + auto entry1 = LOG_ENTRY_MAKE_MULTIBYTE(0x1000, 2); + entry1.raw8[3] = 0x13; + entry1.raw8[4] = 0x14; + (logstart + 4)->set(~entry1.raw32[0]); + (logstart + 5)->set(~entry1.raw32[1]); + + // Set up a 2-byte logical write of [0x15,0x16] at logical offset 0x10 + auto entry2 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry2.raw8[3] = 0x15; + entry2.raw8[4] = 0x16; + (logstart + 6)->set(~entry2.raw32[0]); + (logstart + 7)->set(~entry2.raw32[1]); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_CONSOLIDATED) << "Readback should have failed and triggered consolidation"; + EXPECT_EQ(inst.erasure_count(), 1) << "Invalid final erase count"; + + uint8_t buf[2]; + wear_leveling_read(0x01, buf, sizeof(buf)); + EXPECT_EQ(buf[0], 0x11) << "Readback should have maintained the previous pre-failure value from the write log"; + EXPECT_EQ(buf[1], 0x12) << "Readback should have maintained the previous pre-failure value from the write log"; +} diff --git a/quantum/wear_leveling/tests/wear_leveling_8byte.cpp b/quantum/wear_leveling/tests/wear_leveling_8byte.cpp new file mode 100644 index 0000000000..c27c21d034 --- /dev/null +++ b/quantum/wear_leveling/tests/wear_leveling_8byte.cpp @@ -0,0 +1,178 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +class WearLeveling8Byte : public ::testing::Test { + protected: + void SetUp() override { + MockBackingStore::Instance().reset_instance(); + wear_leveling_init(); + } +}; + +static std::array verify_data; + +static wear_leveling_status_t test_write(const uint32_t address, const void* value, size_t length) { + memcpy(&verify_data[address], value, length); + return wear_leveling_write(address, value, length); +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location. + */ +TEST_F(WearLeveling8Byte, FirstWriteOccursAfterHash) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ(inst.log_begin()->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test verifies that the first write after initialisation occurs after the FNV1a_64 hash location, after an erase has occurred. + */ +TEST_F(WearLeveling8Byte, FirstWriteOccursAfterHash_AfterErase) { + auto& inst = MockBackingStore::Instance(); + uint8_t test_value = 0x15; + wear_leveling_erase(); + test_write(0x02, &test_value, sizeof(test_value)); + EXPECT_EQ((inst.log_begin() + 1)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid first write address."; +} + +/** + * This test ensures the correct number of backing store writes occurs with a multibyte write, given the input buffer size. + */ +TEST_F(WearLeveling8Byte, MultibyteBackingStoreWriteCounts) { + auto& inst = MockBackingStore::Instance(); + + for (std::size_t length = 1; length <= 5; ++length) { + // Clear things out + std::fill(verify_data.begin(), verify_data.end(), 0); + inst.reset_instance(); + wear_leveling_init(); + + // Generate a test block of data + std::vector testvalue(length); + std::iota(testvalue.begin(), testvalue.end(), 0x20); + + // Write the data + EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Write failed with incorrect status"; + + // Check that we got the expected number of write log entries + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 1); + } +} + +/** + * This test forces consolidation by writing enough to the write log that it overflows, consolidating the data into the + * base logical area. + */ +TEST_F(WearLeveling8Byte, ConsolidationOverflow) { + auto& inst = MockBackingStore::Instance(); + + // Generate a test block of data + std::array testvalue; + + // Write the data + std::iota(testvalue.begin(), testvalue.end(), 0x20); + EXPECT_EQ(test_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status"; + uint8_t dummy = 0x40; + EXPECT_EQ(test_write(0x04, &dummy, sizeof(dummy)), WEAR_LEVELING_SUCCESS) << "Write returned incorrect status"; + + // Expected log: + // [0]: multibyte, 5 bytes, backing address 0x18, logical address 0x00 + // [1]: multibyte, 5 bytes, backing address 0x20, logical address 0x05 + // [2]: multibyte, 5 bytes, backing address 0x28, logical address 0x0A, triggers consolidation + // [3]: erase + // [4]: consolidated data, backing address 0x00, logical address 0x00 + // [5]: consolidated data, backing address 0x08, logical address 0x08 + // [6]: FNV1a_64 result, backing address 0x10 + // [7]: multibyte, 1 byte, backing address 0x18, logical address 0x04 + EXPECT_EQ(std::distance(inst.log_begin(), inst.log_end()), 8); + + // Verify the backing store writes for the write log + std::size_t index; + write_log_entry_t e; + for (index = 0; index < 3; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, WEAR_LEVELING_LOGICAL_SIZE + 8 + (index * BACKING_STORE_WRITE_SIZE)) << "Invalid write log address"; + + write_log_entry_t e; + e.raw64 = write_iter->value; + EXPECT_EQ(LOG_ENTRY_GET_TYPE(e), LOG_ENTRY_TYPE_MULTIBYTE) << "Invalid write log entry type"; + } + + // Verify the backing store erase + { + index = 3; + auto write_iter = inst.log_begin() + index; + e.raw64 = write_iter->value; + EXPECT_TRUE(write_iter->erased) << "Backing store erase did not occur as required"; + } + + // Verify the backing store writes for consolidation + for (index = 4; index < 6; ++index) { + auto write_iter = inst.log_begin() + index; + EXPECT_EQ(write_iter->address, (index - 4) * BACKING_STORE_WRITE_SIZE) << "Invalid write log entry address"; + } + + // Verify the FNV1a_64 write + { + EXPECT_EQ((inst.log_begin() + 6)->address, WEAR_LEVELING_LOGICAL_SIZE) << "Invalid write log address"; + e.raw64 = (inst.log_begin() + 6)->value; + EXPECT_EQ(e.raw64, fnv_64a_buf(testvalue.data(), testvalue.size(), FNV1A_64_INIT)) << "Invalid checksum"; // Note that checksum is based on testvalue, as we overwrote one byte and need to consult the consolidated data, not the current + } + + // Verify the final write + EXPECT_EQ((inst.log_begin() + 7)->address, WEAR_LEVELING_LOGICAL_SIZE + 8) << "Invalid write log address"; + + // Verify the data is what we expected + std::array readback; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; + + // Re-init and re-read, verifying the reload capability + EXPECT_NE(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Re-initialisation failed"; + EXPECT_EQ(wear_leveling_read(0, readback.data(), WEAR_LEVELING_LOGICAL_SIZE), WEAR_LEVELING_SUCCESS) << "Failed to read back the saved data"; + EXPECT_TRUE(memcmp(readback.data(), verify_data.data(), WEAR_LEVELING_LOGICAL_SIZE) == 0) << "Readback did not match"; +} + +/** + * This test verifies multibyte readback gets canceled with an out-of-bounds address. + */ +TEST_F(WearLeveling8Byte, PlaybackReadbackMultibyte_OOB) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Invalid FNV1a_64 hash + (logstart + 0)->set(0); + + // Set up a 2-byte logical write of [0x11,0x12] at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry0.raw8[3] = 0x11; + entry0.raw8[4] = 0x12; + (logstart + 1)->set(~entry0.raw64); + + // Set up a 2-byte logical write of [0x13,0x14] at logical offset 0x1000 (out of bounds) + auto entry1 = LOG_ENTRY_MAKE_MULTIBYTE(0x1000, 2); + entry1.raw8[3] = 0x13; + entry1.raw8[4] = 0x14; + (logstart + 2)->set(~entry1.raw64); + + // Set up a 2-byte logical write of [0x15,0x16] at logical offset 0x10 + auto entry2 = LOG_ENTRY_MAKE_MULTIBYTE(0x01, 2); + entry2.raw8[3] = 0x15; + entry2.raw8[4] = 0x16; + (logstart + 3)->set(~entry2.raw64); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_CONSOLIDATED) << "Readback should have failed and triggered consolidation"; + EXPECT_EQ(inst.erasure_count(), 1) << "Invalid final erase count"; + + uint8_t buf[2]; + wear_leveling_read(0x01, buf, sizeof(buf)); + EXPECT_EQ(buf[0], 0x11) << "Readback should have maintained the previous pre-failure value from the write log"; + EXPECT_EQ(buf[1], 0x12) << "Readback should have maintained the previous pre-failure value from the write log"; +} diff --git a/quantum/wear_leveling/tests/wear_leveling_general.cpp b/quantum/wear_leveling/tests/wear_leveling_general.cpp new file mode 100644 index 0000000000..76a4bf7bf3 --- /dev/null +++ b/quantum/wear_leveling/tests/wear_leveling_general.cpp @@ -0,0 +1,204 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "gtest/gtest.h" +#include "gmock/gmock.h" +#include "backing_mocks.hpp" + +class WearLevelingGeneral : public ::testing::Test { + protected: + void SetUp() override { + MockBackingStore::Instance().reset_instance(); + wear_leveling_init(); + } +}; + +/** + * This test verifies that even if there is consolidated data present, if the checksum doesn't match then the cache is zero'd after reading the consolidated area, but before write log is played back. + */ +TEST_F(WearLevelingGeneral, InvalidChecksum_ConsolidatedDataIgnored) { + auto& inst = MockBackingStore::Instance(); + auto logstart = inst.storage_begin() + (WEAR_LEVELING_LOGICAL_SIZE / sizeof(backing_store_int_t)); + + // Generate a test block of data + std::array testvalue; + std::iota(testvalue.begin(), testvalue.end(), 0x20); + + // Write the data + EXPECT_EQ(wear_leveling_write(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_CONSOLIDATED) << "Write returned incorrect status"; + + // Invalidate the checksum + (logstart + 0)->erase(); + (logstart + 1)->erase(); + (logstart + 2)->erase(); + (logstart + 3)->erase(); + + // Set up a 1-byte logical write of [0x11] at logical offset 0x01 + auto entry0 = LOG_ENTRY_MAKE_OPTIMIZED_64(0x01, 0x11); + (logstart + 4)->set(~entry0.raw16[0]); + + // Re-init + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_SUCCESS) << "Init returned incorrect status"; + EXPECT_EQ(wear_leveling_read(0, testvalue.data(), testvalue.size()), WEAR_LEVELING_SUCCESS) << "Failed to read"; + for (int i = 0; i < WEAR_LEVELING_LOGICAL_SIZE; ++i) { + EXPECT_EQ(testvalue[i], i == 0x01 ? 0x11 : 0x00) << "Invalid readback"; + } +} + +/** + * This test verifies that writing the same data multiple times does not result in subsequent writes to the backing store. + */ +TEST_F(WearLevelingGeneral, SameValue_SingleBackingWrite) { + auto& inst = MockBackingStore::Instance(); + + uint8_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(0x02, &test_val, sizeof(test_val)), WEAR_LEVELING_SUCCESS) << "First overall write operation should have succeeded"; + + uint64_t invoke_count = inst.unlock_invoke_count(); + uint64_t erase_count = inst.erase_invoke_count(); + uint64_t write_count = inst.write_invoke_count(); + uint64_t lock_count = inst.lock_invoke_count(); + + for (int i = 0; i < 10; ++i) { + EXPECT_EQ(wear_leveling_write(0x02, &test_val, sizeof(test_val)), WEAR_LEVELING_SUCCESS) << "Subsequent overall write operation should have succeeded"; + + EXPECT_EQ(inst.unlock_invoke_count(), invoke_count) << "Unlock count should match"; + EXPECT_EQ(inst.erase_invoke_count(), erase_count) << "Erase count should match"; + EXPECT_EQ(inst.write_invoke_count(), write_count) << "Write count should match"; + EXPECT_EQ(inst.lock_invoke_count(), lock_count) << "Lock count should match"; + } +} + +/** + * This test verifies that no other invocations occur if `backing_store_init()` fails. + */ +TEST_F(WearLevelingGeneral, InitFailure) { + auto& inst = MockBackingStore::Instance(); + inst.reset_instance(); // make sure the counters are all zero + inst.set_init_callback([](std::uint64_t count) { return false; }); + + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid initial erase count"; + EXPECT_EQ(wear_leveling_init(), WEAR_LEVELING_FAILED) << "Init should have failed"; + EXPECT_EQ(inst.erasure_count(), 0) << "Invalid final erase count"; + + EXPECT_EQ(inst.init_invoke_count(), 1) << "Init should have been invoked once"; + EXPECT_EQ(inst.unlock_invoke_count(), 0) << "Unlock should not have been invoked"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; +} + +/** + * This test verifies that no invocations occur if the supplied address is out of range while writing. + */ +TEST_F(WearLevelingGeneral, WriteFailure_OOB) { + auto& inst = MockBackingStore::Instance(); + + uint8_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(0x21349830, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall write operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 0) << "Unlock should not have been invoked"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; +} + +/** + * This test verifies that a single write occurs if the supplied address and data length hits the edge of the logical area. + */ +TEST_F(WearLevelingGeneral, WriteSuccess_BoundaryOK) { + auto& inst = MockBackingStore::Instance(); + + uint16_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(WEAR_LEVELING_LOGICAL_SIZE - sizeof(test_val), &test_val, sizeof(test_val)), WEAR_LEVELING_SUCCESS) << "Overall write operation should have succeeded"; + + EXPECT_EQ(inst.unlock_invoke_count(), 1) << "Unlock should have been invoked once"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 2) << "Write should have been invoked twice"; + EXPECT_EQ(inst.lock_invoke_count(), 1) << "Lock should have been invoked once"; +} + +/** + * This test verifies that no invocations occur if the supplied address and length would generate writes outside the logical range. + */ +TEST_F(WearLevelingGeneral, WriteFailure_BoundaryOverflow) { + auto& inst = MockBackingStore::Instance(); + + uint16_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(WEAR_LEVELING_LOGICAL_SIZE - sizeof(test_val) + 1, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall write operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 0) << "Unlock should not have been invoked"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; +} + +/** + * This test verifies that no invocations occur if the supplied address is out of range while reading. + */ +TEST_F(WearLevelingGeneral, ReadFailure_OOB) { + auto& inst = MockBackingStore::Instance(); + + uint8_t test_val = 0; + EXPECT_EQ(wear_leveling_read(0x21349830, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall read operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 0) << "Unlock should not have been invoked"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; +} + +/** + * This test verifies that no write invocations occur if `backing_store_unlock()` fails. + */ +TEST_F(WearLevelingGeneral, UnlockFailure_NoWrite) { + auto& inst = MockBackingStore::Instance(); + inst.set_unlock_callback([](std::uint64_t count) { return false; }); + + uint8_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(0x04, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall write operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 1) << "Unlock should have been invoked once"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; + + test_val = 0; + wear_leveling_read(0x04, &test_val, sizeof(test_val)); + EXPECT_EQ(test_val, 0x14) << "Readback should come from cache regardless of unlock failure"; +} + +/** + * This test verifies that no erase invocations occur if `backing_store_unlock()` fails. + */ +TEST_F(WearLevelingGeneral, UnlockFailure_NoErase) { + auto& inst = MockBackingStore::Instance(); + inst.set_unlock_callback([](std::uint64_t count) { return false; }); + + EXPECT_EQ(wear_leveling_erase(), WEAR_LEVELING_FAILED) << "Overall erase operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 1) << "Unlock should have been invoked once"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 0) << "Write should not have been invoked"; + EXPECT_EQ(inst.lock_invoke_count(), 0) << "Lock should not have been invoked"; +} + +/** + * This test verifies that only one write invocation occurs if `backing_store_write()` fails. + */ +TEST_F(WearLevelingGeneral, WriteFailure_NoSubsequentWrites) { + auto& inst = MockBackingStore::Instance(); + inst.set_write_callback([](std::uint64_t count, std::uint32_t address) { return false; }); + + uint8_t test_val = 0x14; + EXPECT_EQ(wear_leveling_write(0x04, &test_val, sizeof(test_val)), WEAR_LEVELING_FAILED) << "Overall write operation should have failed"; + + EXPECT_EQ(inst.unlock_invoke_count(), 1) << "Unlock should have been invoked once"; + EXPECT_EQ(inst.erase_invoke_count(), 0) << "Erase should not have been invoked"; + EXPECT_EQ(inst.write_invoke_count(), 1) << "Write should have been invoked once"; + EXPECT_EQ(inst.lock_invoke_count(), 1) << "Lock should have been invoked once"; + + test_val = 0; + wear_leveling_read(0x04, &test_val, sizeof(test_val)); + EXPECT_EQ(test_val, 0x14) << "Readback should come from cache regardless of unlock failure"; +} diff --git a/quantum/wear_leveling/wear_leveling.c b/quantum/wear_leveling/wear_leveling.c new file mode 100644 index 0000000000..8418ae77bf --- /dev/null +++ b/quantum/wear_leveling/wear_leveling.c @@ -0,0 +1,779 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#include +#include "fnv.h" +#include "wear_leveling.h" +#include "wear_leveling_internal.h" + +/* + This wear leveling algorithm is adapted from algorithms from previous + implementations in QMK, namely: + - Artur F. (http://engsta.com/stm32-flash-memory-eeprom-emulator/) + - Yiancar -- QMK's base implementation for STM32F303 + - Ilya Zhuravlev -- initial wear leveling algorithm + - Don Kjer -- increased flash density algorithm + - Nick Brassel (@tzarc) -- decoupled for use on other peripherals + + At this layer, it is assumed that any reads/writes from the backing store + have a "reset state" after erasure of zero. + It is up to the backing store to perform translation of values, such as + taking the complement in order to deal with flash memory's reset value. + + Terminology: + + - Backing store: this is the storage area used by the wear leveling + algorithm. + + - Backing size: this is the amount of storage provided by the backing + store for use by the wear leveling algorithm. + + - Backing write size: this is the minimum number of bytes the backing + store can write in a single operation. + + - Logical data: this is the externally-visible "emulated EEPROM" that + external subsystems "see" when performing reads/writes. + + - Logical size: this is the amount of storage available for use + externally. Effectively, the "size of the EEPROM". + + - Write log: this is a section of the backing store used to keep track + of modifications without overwriting existing data. This log is + "played back" on startup such that any subsequent reads are capable + of returning the latest data. + + - Consolidated data: this is a section of the backing store reserved for + use for the latest copy of logical data. This is only ever written + when the write log is full -- the latest values for the logical data + are written here and the write log is cleared. + + Configurables: + + - BACKING_STORE_WRITE_SIZE: The number of bytes requires for a write + operation. This is defined by the capabilities of the backing store. + + - WEAR_LEVELING_BACKING_SIZE: The number of bytes provided by the + backing store for use by the wear leveling algorithm. This is + defined by the capabilities of the backing store. This value must + also be at least twice the size of the logical size, as well as a + multiple of the logical size. + + - WEAR_LEVELING_LOGICAL_SIZE: The number of bytes externally visible + to other subsystems performing reads/writes. This must be a multiple + of the write size. + + General algorithm: + + During initialization: + * The contents of the consolidated data section are read into cache. + * The contents of the write log are "played back" and update the + cache accordingly. + + During reads: + * Logical data is served from the cache. + + During writes: + * The cache is updated with the new data. + * A new write log entry is appended to the log. + * If the log's full, data is consolidated and the write log cleared. + + Write log structure: + + The first 8 bytes of the write log are a FNV1a_64 hash of the contents + of the consolidated data area, in an attempt to detect and guard against + any data corruption. + + The write log follows the hash: + + Given that the algorithm needs to cater for 2-, 4-, and 8-byte writes, + a variable-length write log entry is used such that the minimal amount + of storage is used based off the backing store write size. + + Firstly, an empty log entry is expected to be all zeros. If the backing + store uses 0xFF for cleared bytes, it should return the complement, such + that this wear-leveling algorithm "receives" zeros. + + For multi-byte writes, up to 8 bytes will be used for each log entry, + depending on the size of backing store writes: + + ╔ Multi-byte Log Entry (2, 4-byte) ═╗ + ║00XXXYYY║YYYYYYYY║YYYYYYYY║AAAAAAAA║ + ║ └┬┘└┬┘║└──┬───┘║└──┬───┘║└──┬───┘║ + ║ LenAdd║ Address║ Address║Value[0]║ + ╚════════╩════════╩════════╩════════╝ + ╔ Multi-byte Log Entry (2-byte) ══════════════════════╗ + ║00XXXYYY║YYYYYYYY║YYYYYYYY║AAAAAAAA║BBBBBBBB║CCCCCCCC║ + ║ └┬┘└┬┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║ + ║ LenAdd║ Address║ Address║Value[0]║Value[1]║Value[2]║ + ╚════════╩════════╩════════╩════════╩════════╩════════╝ + ╔ Multi-byte Log Entry (2, 4, 8-byte) ══════════════════════════════════╗ + ║00XXXYYY║YYYYYYYY║YYYYYYYY║AAAAAAAA║BBBBBBBB║CCCCCCCC║DDDDDDDD║EEEEEEEE║ + ║ └┬┘└┬┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║└──┬───┘║ + ║ LenAdd║ Address║ Address║Value[0]║Value[1]║Value[2]║Value[3]║Value[4]║ + ╚════════╩════════╩════════╩════════╩════════╩════════╩════════╩════════╝ + + 19 bits are used for the address, which allows for a max logical size of + 512kB. Up to 5 bytes can be included in a single log entry. + + For 2-byte backing store writes, the last two bytes are optional + depending on the length of data to be written. Accordingly, either 3 + or 4 backing store write operations will occur. + For 4-byte backing store writes, either one or two write operations + occur, depending on the length. + For 8-byte backing store writes, one write operation occur. + + 2-byte backing store optimizations: + + For single byte writes, addresses between 0...63 are encoded in a single + backing store write operation. 4- and 8-byte backing stores do not have + this optimization as it does not minimize the number of bytes written. + + ╔ Byte-Entry ════╗ + ║01XXXXXXYYYYYYYY║ + ║ └─┬──┘└──┬───┘║ + ║ Address Value ║ + ╚════════════════╝ + 0 <= Address < 0x40 (64) + + A second optimization takes into account uint16_t writes of 0 or 1, + specifically catering for KC_NO and KC_TRANSPARENT in the dynamic keymap + subsystem. This is valid only for the first 16kB of logical data -- + addresses outside this range will use the multi-byte encoding above. + + ╔ U16-Encoded 0 ═╗ + ║100XXXXXXXXXXXXX║ + ║ │└─────┬─────┘║ + ║ │Address >> 1 ║ + ║ └── Value: 0 ║ + ╚════════════════╝ + 0 <= Address <= 0x3FFE (16382) + + ╔ U16-Encoded 1 ═╗ + ║101XXXXXXXXXXXXX║ + ║ │└─────┬─────┘║ + ║ │Address >> 1 ║ + ║ └── Value: 1 ║ + ╚════════════════╝ + 0 <= Address <= 0x3FFE (16382) */ + +/** + * Storage area for the wear-leveling cache. + */ +static struct __attribute__((__aligned__(BACKING_STORE_WRITE_SIZE))) { + __attribute__((__aligned__(BACKING_STORE_WRITE_SIZE))) uint8_t cache[(WEAR_LEVELING_LOGICAL_SIZE)]; + uint32_t write_address; + bool unlocked; +} wear_leveling; + +/** + * Locking helper: status + */ +typedef enum backing_store_lock_status_t { STATUS_FAILURE = 0, STATUS_SUCCESS, STATUS_UNCHANGED } backing_store_lock_status_t; + +/** + * Locking helper: unlock + */ +static inline backing_store_lock_status_t wear_leveling_unlock(void) { + if (wear_leveling.unlocked) { + return STATUS_UNCHANGED; + } + if (!backing_store_unlock()) { + return STATUS_FAILURE; + } + wear_leveling.unlocked = true; + return STATUS_SUCCESS; +} + +/** + * Locking helper: lock + */ +static inline backing_store_lock_status_t wear_leveling_lock(void) { + if (!wear_leveling.unlocked) { + return STATUS_UNCHANGED; + } + if (!backing_store_lock()) { + return STATUS_FAILURE; + } + wear_leveling.unlocked = false; + return STATUS_SUCCESS; +} + +/** + * Resets the cache, ensuring the write address is correctly initialised. + */ +static void wear_leveling_clear_cache(void) { + memset(wear_leveling.cache, 0, (WEAR_LEVELING_LOGICAL_SIZE)); + wear_leveling.write_address = (WEAR_LEVELING_LOGICAL_SIZE) + 8; // +8 is due to the FNV1a_64 of the consolidated buffer +} + +/** + * Reads the consolidated data from the backing store into the cache. + * Does not consider the write log. + */ +static wear_leveling_status_t wear_leveling_read_consolidated(void) { + wl_dprintf("Reading consolidated data\n"); + + wear_leveling_status_t status = WEAR_LEVELING_SUCCESS; + for (int address = 0; address < (WEAR_LEVELING_LOGICAL_SIZE); address += (BACKING_STORE_WRITE_SIZE)) { + backing_store_int_t *const loc = (backing_store_int_t *)&wear_leveling.cache[address]; + backing_store_int_t temp; + bool ok = backing_store_read(address, &temp); + if (!ok) { + wl_dprintf("Failed to read from backing store\n"); + status = WEAR_LEVELING_FAILED; + break; + } + *loc = temp; + } + + // Verify the FNV1a_64 result + if (status != WEAR_LEVELING_FAILED) { + uint64_t expected = fnv_64a_buf(wear_leveling.cache, (WEAR_LEVELING_LOGICAL_SIZE), FNV1A_64_INIT); + write_log_entry_t entry; +#if BACKING_STORE_WRITE_SIZE == 2 + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 0, &entry.raw16[0]); + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 2, &entry.raw16[1]); + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 4, &entry.raw16[2]); + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 6, &entry.raw16[3]); +#elif BACKING_STORE_WRITE_SIZE == 4 + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 0, &entry.raw32[0]); + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 4, &entry.raw32[1]); +#elif BACKING_STORE_WRITE_SIZE == 8 + backing_store_read((WEAR_LEVELING_LOGICAL_SIZE) + 0, &entry.raw64); +#endif + // If we have a mismatch, clear the cache but do not flag a failure, + // which will cater for the completely clean MCU case. + if (entry.raw64 != expected) { + wear_leveling_clear_cache(); + } + } + + // If we failed for any reason, then clear the cache + if (status == WEAR_LEVELING_FAILED) { + wear_leveling_clear_cache(); + } + + return status; +} + +/** + * Writes the current cache to consolidated data at the beginning of the backing store. + * Does not clear the write log. + */ +static wear_leveling_status_t wear_leveling_write_consolidated(void) { + wl_dprintf("Writing consolidated data\n"); + + wear_leveling_status_t status = WEAR_LEVELING_CONSOLIDATED; + backing_store_lock_status_t lock_status = wear_leveling_unlock(); + for (int address = 0; address < (WEAR_LEVELING_LOGICAL_SIZE); address += (BACKING_STORE_WRITE_SIZE)) { + const backing_store_int_t value = *(backing_store_int_t *)&wear_leveling.cache[address]; + backing_store_int_t temp; + bool ok = backing_store_read(address, &temp); + if (!ok) { + wl_dprintf("Failed to read from backing store\n"); + status = WEAR_LEVELING_FAILED; + break; + } + if (temp != value) { + ok = backing_store_write(address, value); + if (!ok) { + wl_dprintf("Failed to write to backing store\n"); + status = WEAR_LEVELING_FAILED; + break; + } + } + } + + if (status != WEAR_LEVELING_FAILED) { + // Write out the FNV1a_64 result of the consolidated data + write_log_entry_t entry; + entry.raw64 = fnv_64a_buf(wear_leveling.cache, (WEAR_LEVELING_LOGICAL_SIZE), FNV1A_64_INIT); + do { +#if BACKING_STORE_WRITE_SIZE == 2 + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 0, entry.raw16[0])) { + status = WEAR_LEVELING_FAILED; + break; + } + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 2, entry.raw16[1])) { + status = WEAR_LEVELING_FAILED; + break; + } + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 4, entry.raw16[2])) { + status = WEAR_LEVELING_FAILED; + break; + } + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 6, entry.raw16[3])) { + status = WEAR_LEVELING_FAILED; + break; + } +#elif BACKING_STORE_WRITE_SIZE == 4 + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 0, entry.raw32[0])) { + status = WEAR_LEVELING_FAILED; + break; + } + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 4, entry.raw32[1])) { + status = WEAR_LEVELING_FAILED; + break; + } +#elif BACKING_STORE_WRITE_SIZE == 8 + if (!backing_store_write((WEAR_LEVELING_LOGICAL_SIZE) + 0, entry.raw64)) { + status = WEAR_LEVELING_FAILED; + break; + } +#endif + } while (0); + } + + if (lock_status == STATUS_SUCCESS) { + wear_leveling_lock(); + } + return status; +} + +/** + * Forces a write of the current cache. + * Erases the backing store, including the write log. + * During this operation, there is the potential for data loss if a power loss occurs. + */ +static wear_leveling_status_t wear_leveling_consolidate_force(void) { + wl_dprintf("Erasing backing store\n"); + + // Erase the backing store. Expectation is that any un-written values that are read back after this call come back as zero. + bool ok = backing_store_erase(); + if (!ok) { + wl_dprintf("Failed to erase backing store\n"); + return WEAR_LEVELING_FAILED; + } + + // Write the cache to the first section of the backing store. + wear_leveling_status_t status = wear_leveling_write_consolidated(); + if (status == WEAR_LEVELING_FAILED) { + wl_dprintf("Failed to write consolidated data\n"); + } + + // Next write of the log occurs after the consolidated values at the start of the backing store. + wear_leveling.write_address = (WEAR_LEVELING_LOGICAL_SIZE) + 8; // +8 due to the FNV1a_64 of the consolidated area + + return status; +} + +/** + * Potential write of the current cache to the backing store. + * Skipped if the current write log position is not at the end of the backing store. + * During this operation, there is the potential for data loss if a power loss occurs. + * + * @return true if consolidation occurred + */ +static wear_leveling_status_t wear_leveling_consolidate_if_needed(void) { + if (wear_leveling.write_address >= (WEAR_LEVELING_BACKING_SIZE)) { + return wear_leveling_consolidate_force(); + } + + return WEAR_LEVELING_SUCCESS; +} + +/** + * Appends the supplied fixed-width entry to the write log, optionally consolidating if the log is full. + * + * @return true if consolidation occurred + */ +static wear_leveling_status_t wear_leveling_append_raw(backing_store_int_t value) { + bool ok = backing_store_write(wear_leveling.write_address, value); + if (!ok) { + wl_dprintf("Failed to write to backing store\n"); + return WEAR_LEVELING_FAILED; + } + wear_leveling.write_address += (BACKING_STORE_WRITE_SIZE); + return wear_leveling_consolidate_if_needed(); +} + +/** + * Handles writing multi_byte-encoded data to the backing store. + * + * @return true if consolidation occurred + */ +static wear_leveling_status_t wear_leveling_write_raw_multibyte(uint32_t address, const void *value, size_t length) { + const uint8_t * p = value; + write_log_entry_t log = LOG_ENTRY_MAKE_MULTIBYTE(address, length); + for (size_t i = 0; i < length; ++i) { + log.raw8[3 + i] = p[i]; + } + + // Write to the backing store. See the multi-byte log format in the documentation header at the top of the file. + wear_leveling_status_t status; +#if BACKING_STORE_WRITE_SIZE == 2 + status = wear_leveling_append_raw(log.raw16[0]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + + status = wear_leveling_append_raw(log.raw16[1]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + + if (length > 1) { + status = wear_leveling_append_raw(log.raw16[2]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + } + + if (length > 3) { + status = wear_leveling_append_raw(log.raw16[3]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + } +#elif BACKING_STORE_WRITE_SIZE == 4 + status = wear_leveling_append_raw(log.raw32[0]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + + if (length > 1) { + status = wear_leveling_append_raw(log.raw32[1]); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } + } +#elif BACKING_STORE_WRITE_SIZE == 8 + status = wear_leveling_append_raw(log.raw64); + if (status != WEAR_LEVELING_SUCCESS) { + return status; + } +#endif + return status; +} + +/** + * Handles the actual writing of logical data into the write log section of the backing store. + */ +static wear_leveling_status_t wear_leveling_write_raw(uint32_t address, const void *value, size_t length) { + const uint8_t * p = value; + size_t remaining = length; + wear_leveling_status_t status = WEAR_LEVELING_SUCCESS; + while (remaining > 0) { +#if BACKING_STORE_WRITE_SIZE == 2 + // Small-write optimizations - uint16_t, 0 or 1, address is even, address <16384: + if (remaining >= 2 && address % 2 == 0 && address < 16384) { + const uint16_t v = *(const uint16_t *)p; + if (v == 0 || v == 1) { + const write_log_entry_t log = LOG_ENTRY_MAKE_WORD_01(address, v); + status = wear_leveling_append_raw(log.raw16[0]); + if (status != WEAR_LEVELING_SUCCESS) { + // If consolidation occurred, then the cache has already been written to the consolidated area. No need to continue. + // If a failure occurred, pass it on. + return status; + } + + remaining -= 2; + address += 2; + p += 2; + continue; + } + } + + // Small-write optimizations - address<64: + if (address < 64) { + const write_log_entry_t log = LOG_ENTRY_MAKE_OPTIMIZED_64(address, *p); + status = wear_leveling_append_raw(log.raw16[0]); + if (status != WEAR_LEVELING_SUCCESS) { + // If consolidation occurred, then the cache has already been written to the consolidated area. No need to continue. + // If a failure occurred, pass it on. + return status; + } + + remaining--; + address++; + p++; + continue; + } +#endif // BACKING_STORE_WRITE_SIZE == 2 + const size_t this_length = remaining >= LOG_ENTRY_MULTIBYTE_MAX_BYTES ? LOG_ENTRY_MULTIBYTE_MAX_BYTES : remaining; + status = wear_leveling_write_raw_multibyte(address, p, this_length); + if (status != WEAR_LEVELING_SUCCESS) { + // If consolidation occurred, then the cache has already been written to the consolidated area. No need to continue. + // If a failure occurred, pass it on. + return status; + } + remaining -= this_length; + address += (uint32_t)this_length; + p += this_length; + } + + return status; +} + +/** + * "Replays" the write log from the backing store, updating the local cache with updated values. + */ +static wear_leveling_status_t wear_leveling_playback_log(void) { + wl_dprintf("Playback write log\n"); + + wear_leveling_status_t status = WEAR_LEVELING_SUCCESS; + bool cancel_playback = false; + uint32_t address = (WEAR_LEVELING_LOGICAL_SIZE) + 8; // +8 due to the FNV1a_64 of the consolidated area + while (!cancel_playback && address < (WEAR_LEVELING_BACKING_SIZE)) { + backing_store_int_t value; + bool ok = backing_store_read(address, &value); + if (!ok) { + wl_dprintf("Failed to load from backing store, skipping playback of write log\n"); + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + if (value == 0) { + wl_dprintf("Found empty slot, no more log entries\n"); + cancel_playback = true; + break; + } + + // If we got a nonzero value, then we need to increment the address to ensure next write occurs at next location + address += (BACKING_STORE_WRITE_SIZE); + + // Read from the write log + write_log_entry_t log; +#if BACKING_STORE_WRITE_SIZE == 2 + log.raw16[0] = value; +#elif BACKING_STORE_WRITE_SIZE == 4 + log.raw32[0] = value; +#elif BACKING_STORE_WRITE_SIZE == 8 + log.raw64 = value; +#endif + + switch (LOG_ENTRY_GET_TYPE(log)) { + case LOG_ENTRY_TYPE_MULTIBYTE: { +#if BACKING_STORE_WRITE_SIZE == 2 + ok = backing_store_read(address, &log.raw16[1]); + if (!ok) { + wl_dprintf("Failed to load from backing store, skipping playback of write log\n"); + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + address += (BACKING_STORE_WRITE_SIZE); +#endif // BACKING_STORE_WRITE_SIZE == 2 + const uint32_t a = LOG_ENTRY_MULTIBYTE_GET_ADDRESS(log); + const uint8_t l = LOG_ENTRY_MULTIBYTE_GET_LENGTH(log); + + if (a + l > (WEAR_LEVELING_LOGICAL_SIZE)) { + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + +#if BACKING_STORE_WRITE_SIZE == 2 + if (l > 1) { + ok = backing_store_read(address, &log.raw16[2]); + if (!ok) { + wl_dprintf("Failed to load from backing store, skipping playback of write log\n"); + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + address += (BACKING_STORE_WRITE_SIZE); + } + if (l > 3) { + ok = backing_store_read(address, &log.raw16[3]); + if (!ok) { + wl_dprintf("Failed to load from backing store, skipping playback of write log\n"); + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + address += (BACKING_STORE_WRITE_SIZE); + } +#elif BACKING_STORE_WRITE_SIZE == 4 + if (l > 1) { + ok = backing_store_read(address, &log.raw32[1]); + if (!ok) { + wl_dprintf("Failed to load from backing store, skipping playback of write log\n"); + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + address += (BACKING_STORE_WRITE_SIZE); + } +#endif + + memcpy(&wear_leveling.cache[a], &log.raw8[3], l); + } break; +#if BACKING_STORE_WRITE_SIZE == 2 + case LOG_ENTRY_TYPE_OPTIMIZED_64: { + const uint32_t a = LOG_ENTRY_OPTIMIZED_64_GET_ADDRESS(log); + const uint8_t v = LOG_ENTRY_OPTIMIZED_64_GET_VALUE(log); + + if (a >= (WEAR_LEVELING_LOGICAL_SIZE)) { + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + + wear_leveling.cache[a] = v; + } break; + case LOG_ENTRY_TYPE_WORD_01: { + const uint32_t a = LOG_ENTRY_WORD_01_GET_ADDRESS(log); + const uint8_t v = LOG_ENTRY_WORD_01_GET_VALUE(log); + + if (a + 1 >= (WEAR_LEVELING_LOGICAL_SIZE)) { + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + break; + } + + wear_leveling.cache[a + 0] = v; + wear_leveling.cache[a + 1] = 0; + } break; +#endif // BACKING_STORE_WRITE_SIZE == 2 + default: { + cancel_playback = true; + status = WEAR_LEVELING_FAILED; + } break; + } + } + + // We've reached the end of the log, so we're at the new write location + wear_leveling.write_address = address; + + if (status == WEAR_LEVELING_FAILED) { + // If we had a failure during readback, assume we're corrupted -- force a consolidation with the data we already have + status = wear_leveling_consolidate_force(); + } else { + // Consolidate the cache + write log if required + status = wear_leveling_consolidate_if_needed(); + } + + return status; +} + +/** + * Wear-leveling initialization + */ +wear_leveling_status_t wear_leveling_init(void) { + wl_dprintf("Init\n"); + + // Reset the cache + wear_leveling_clear_cache(); + + // Initialise the backing store + if (!backing_store_init()) { + // If it failed, clear the cache and return with failure + wear_leveling_clear_cache(); + return WEAR_LEVELING_FAILED; + } + + // Read the previous consolidated values, then replay the existing write log so that the cache has the "live" values + wear_leveling_status_t status = wear_leveling_read_consolidated(); + if (status == WEAR_LEVELING_FAILED) { + // If it failed, clear the cache and return with failure + wear_leveling_clear_cache(); + return status; + } + + status = wear_leveling_playback_log(); + if (status == WEAR_LEVELING_FAILED) { + // If it failed, clear the cache and return with failure + wear_leveling_clear_cache(); + return status; + } + + return status; +} + +/** + * Wear-leveling erase. + * Post-condition: any reads from the backing store directly after an erase operation must come back as zero. + */ +wear_leveling_status_t wear_leveling_erase(void) { + wl_dprintf("Erase\n"); + + // Unlock the backing store + backing_store_lock_status_t lock_status = wear_leveling_unlock(); + if (lock_status == STATUS_FAILURE) { + wear_leveling_lock(); + return WEAR_LEVELING_FAILED; + } + + // Perform the erase + bool ret = backing_store_erase(); + wear_leveling_clear_cache(); + + // Lock the backing store if we acquired the lock successfully + if (lock_status == STATUS_SUCCESS) { + ret &= (wear_leveling_lock() != STATUS_FAILURE); + } + + return ret ? WEAR_LEVELING_SUCCESS : WEAR_LEVELING_FAILED; +} + +/** + * Writes logical data into the backing store. Skips writes if there are no changes to values. + */ +wear_leveling_status_t wear_leveling_write(const uint32_t address, const void *value, size_t length) { + wl_assert(address + length <= (WEAR_LEVELING_LOGICAL_SIZE)); + if (address + length > (WEAR_LEVELING_LOGICAL_SIZE)) { + return WEAR_LEVELING_FAILED; + } + + wl_dprintf("Write "); + wl_dump(address, value, length); + + // Skip write if there's no change compared to the current cached value + if (memcmp(value, &wear_leveling.cache[address], length) == 0) { + return true; + } + + // Update the cache before writing to the backing store -- if we hit the end of the backing store during writes to the log then we'll force a consolidation in-line + memcpy(&wear_leveling.cache[address], value, length); + + // Unlock the backing store + backing_store_lock_status_t lock_status = wear_leveling_unlock(); + if (lock_status == STATUS_FAILURE) { + wear_leveling_lock(); + return WEAR_LEVELING_FAILED; + } + + // Perform the actual write + wear_leveling_status_t status = wear_leveling_write_raw(address, value, length); + switch (status) { + case WEAR_LEVELING_CONSOLIDATED: + case WEAR_LEVELING_FAILED: + // If the write triggered consolidation, or the write failed, then nothing else needs to occur. + break; + + case WEAR_LEVELING_SUCCESS: + // Consolidate the cache + write log if required + status = wear_leveling_consolidate_if_needed(); + break; + + default: + // Unsure how we'd get here... + status = WEAR_LEVELING_FAILED; + break; + } + + if (lock_status == STATUS_SUCCESS) { + if (wear_leveling_lock() == STATUS_FAILURE) { + status = WEAR_LEVELING_FAILED; + } + } + + return status; +} + +/** + * Reads logical data from the cache. + */ +wear_leveling_status_t wear_leveling_read(const uint32_t address, void *value, size_t length) { + wl_assert(address + length <= (WEAR_LEVELING_LOGICAL_SIZE)); + if (address + length > (WEAR_LEVELING_LOGICAL_SIZE)) { + return WEAR_LEVELING_FAILED; + } + + // Only need to copy from the cache + memcpy(value, &wear_leveling.cache[address], length); + + wl_dprintf("Read "); + wl_dump(address, value, length); + return WEAR_LEVELING_SUCCESS; +} diff --git a/quantum/wear_leveling/wear_leveling.h b/quantum/wear_leveling/wear_leveling.h new file mode 100644 index 0000000000..6641bc49b3 --- /dev/null +++ b/quantum/wear_leveling/wear_leveling.h @@ -0,0 +1,54 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#pragma once +#include +#include + +/** + * @typedef Status returned from any wear-leveling API. + */ +typedef enum wear_leveling_status_t { + WEAR_LEVELING_FAILED, //< Invocation failed + WEAR_LEVELING_SUCCESS, //< Invocation succeeded + WEAR_LEVELING_CONSOLIDATED //< Invocation succeeded, consolidation occurred +} wear_leveling_status_t; + +/** + * Wear-leveling initialization + * + * @return Status of the request + */ +wear_leveling_status_t wear_leveling_init(void); + +/** + * Wear-leveling erasure. + * + * Clears the wear-leveling area, with the definition that the "reset state" of all data is zero. + * + * @return Status of the request + */ +wear_leveling_status_t wear_leveling_erase(void); + +/** + * Writes logical data into the backing store. + * + * Skips writes if there are no changes to written values. The entire written block is considered when attempting to + * determine if an overwrite should occur -- if there is any data mismatch the entire block will be written to the log, + * not just the changed bytes. + * + * @param address[in] the logical address to write data + * @param value[in] pointer to the source buffer + * @param length[in] length of the data + * @return Status of the request + */ +wear_leveling_status_t wear_leveling_write(uint32_t address, const void* value, size_t length); + +/** + * Reads logical data from the cache. + * + * @param address[in] the logical address to read data + * @param value[out] pointer to the destination buffer + * @param length[in] length of the data + * @return Status of the request + */ +wear_leveling_status_t wear_leveling_read(uint32_t address, void* value, size_t length); diff --git a/quantum/wear_leveling/wear_leveling_internal.h b/quantum/wear_leveling/wear_leveling_internal.h new file mode 100644 index 0000000000..74b43932df --- /dev/null +++ b/quantum/wear_leveling/wear_leveling_internal.h @@ -0,0 +1,145 @@ +// Copyright 2022 Nick Brassel (@tzarc) +// SPDX-License-Identifier: GPL-2.0-or-later +#pragma once + +#ifdef __cplusplus +# define _Static_assert static_assert +#endif + +#include +#include + +#if BACKING_STORE_WRITE_SIZE == 2 +typedef uint16_t backing_store_int_t; +#elif BACKING_STORE_WRITE_SIZE == 4 +typedef uint32_t backing_store_int_t; +#elif BACKING_STORE_WRITE_SIZE == 8 +typedef uint64_t backing_store_int_t; +#else +# error Invalid BACKING_STORE_WRITE_SIZE, needs to be 2/4/8. +#endif + +#ifndef WEAR_LEVELING_BACKING_SIZE +# error WEAR_LEVELING_BACKING_SIZE was not set. +#endif + +#ifndef WEAR_LEVELING_LOGICAL_SIZE +# error WEAR_LEVELING_LOGICAL_SIZE was not set. +#endif + +#ifdef WEAR_LEVELING_DEBUG_OUTPUT +# include +# define wl_dprintf(...) printf("Wear leveling: " __VA_ARGS__) +# define wl_dump(address, value, length) \ + do { \ + printf("[0x%04X]: ", (int)(address)); \ + const uint8_t* p = (const uint8_t*)(value); \ + for (int i = 0; i < (length); ++i) { \ + printf(" %02X", (int)p[i]); \ + } \ + printf("\n"); \ + } while (0) +#else +# define wl_dprintf(...) \ + do { \ + } while (0) +# define wl_dump(...) \ + do { \ + } while (0) +#endif // WEAR_LEVELING_DEBUG_OUTPUT + +#ifdef WEAR_LEVELING_ASSERTS +# include +# define wl_assert(...) assert(__VA_ARGS__) +#else +# define wl_assert(...) \ + do { \ + } while (0) +#endif // WEAR_LEVELING_ASSERTS + +// Compile-time validation of configurable options +_Static_assert(WEAR_LEVELING_BACKING_SIZE >= (WEAR_LEVELING_LOGICAL_SIZE * 2), "Total backing size must be at least twice the size of the logical size"); +_Static_assert(WEAR_LEVELING_LOGICAL_SIZE % BACKING_STORE_WRITE_SIZE == 0, "Logical size must be a multiple of write size"); +_Static_assert(WEAR_LEVELING_BACKING_SIZE % WEAR_LEVELING_LOGICAL_SIZE == 0, "Backing size must be a multiple of logical size"); + +// Backing Store API, to be implemented elsewhere by flash driver etc. +bool backing_store_init(void); +bool backing_store_unlock(void); +bool backing_store_erase(void); +bool backing_store_write(uint32_t address, backing_store_int_t value); +bool backing_store_lock(void); +bool backing_store_read(uint32_t address, backing_store_int_t* value); + +/** + * Helper type used to contain a write log entry. + */ +typedef union write_log_entry_t { + uint64_t raw64; + uint32_t raw32[2]; + uint16_t raw16[4]; + uint8_t raw8[8]; +} write_log_entry_t; + +_Static_assert(sizeof(write_log_entry_t) == 8, "Wear leveling write log entry size was not 8"); + +/** + * Log entry type discriminator. + */ +enum { + // 0x00 -- Multi-byte storage type + LOG_ENTRY_TYPE_MULTIBYTE, + + // 0x01 -- 2-byte backing store write optimization: address < 64 + LOG_ENTRY_TYPE_OPTIMIZED_64, + + // 0x02 -- 2-byte backing store write optimization: word-encoded 0/1 values + LOG_ENTRY_TYPE_WORD_01, + + LOG_ENTRY_TYPES +}; + +_Static_assert(LOG_ENTRY_TYPES <= (1 << 2), "Too many log entry types to fit into 2 bits of storage"); + +#define BITMASK_FOR_BITCOUNT(n) ((1 << (n)) - 1) + +#define LOG_ENTRY_GET_TYPE(entry) (((entry).raw8[0] >> 6) & BITMASK_FOR_BITCOUNT(2)) + +#define LOG_ENTRY_MULTIBYTE_MAX_BYTES 5 +#define LOG_ENTRY_MULTIBYTE_GET_ADDRESS(entry) (((((uint32_t)((entry).raw8[0])) & BITMASK_FOR_BITCOUNT(3)) << 16) | (((uint32_t)((entry).raw8[1])) << 8) | (entry).raw8[2]) +#define LOG_ENTRY_MULTIBYTE_GET_LENGTH(entry) ((uint8_t)(((entry).raw8[0] >> 3) & BITMASK_FOR_BITCOUNT(3))) +#define LOG_ENTRY_MAKE_MULTIBYTE(address, length) \ + (write_log_entry_t) { \ + .raw8 = { \ + [0] = (((((uint8_t)LOG_ENTRY_TYPE_MULTIBYTE) & BITMASK_FOR_BITCOUNT(2)) << 6) /* type */ \ + | ((((uint8_t)(length)) & BITMASK_FOR_BITCOUNT(3)) << 3) /* length */ \ + | ((((uint8_t)((address) >> 16))) & BITMASK_FOR_BITCOUNT(3)) /* address */ \ + ), \ + [1] = (((uint8_t)((address) >> 8)) & BITMASK_FOR_BITCOUNT(8)), /* address */ \ + [2] = (((uint8_t)(address)) & BITMASK_FOR_BITCOUNT(8)), /* address */ \ + } \ + } + +#define LOG_ENTRY_OPTIMIZED_64_GET_ADDRESS(entry) ((uint32_t)((entry).raw8[0] & BITMASK_FOR_BITCOUNT(6))) +#define LOG_ENTRY_OPTIMIZED_64_GET_VALUE(entry) ((entry).raw8[1]) +#define LOG_ENTRY_MAKE_OPTIMIZED_64(address, value) \ + (write_log_entry_t) { \ + .raw8 = { \ + [0] = (((((uint8_t)LOG_ENTRY_TYPE_OPTIMIZED_64) & BITMASK_FOR_BITCOUNT(2)) << 6) /* type */ \ + | ((((uint8_t)(address))) & BITMASK_FOR_BITCOUNT(6)) /* address */ \ + ), \ + [1] = ((uint8_t)(value)), /* value */ \ + } \ + } + +#define LOG_ENTRY_WORD_01_GET_ADDRESS(entry) ((((uint32_t)(((entry).raw8[0]) & BITMASK_FOR_BITCOUNT(5))) << 9) | (((uint32_t)((entry).raw8[1])) << 1)) +#define LOG_ENTRY_WORD_01_GET_VALUE(entry) ((uint8_t)((entry).raw8[0] >> 5) & BITMASK_FOR_BITCOUNT(1)) +#define LOG_ENTRY_MAKE_WORD_01(address, value) \ + (write_log_entry_t) { \ + .raw8 = { \ + [0] = (((((uint8_t)LOG_ENTRY_TYPE_WORD_01) & BITMASK_FOR_BITCOUNT(2)) << 6) /* type */ \ + | (((((uint8_t)((value) ? 1 : 0))) & BITMASK_FOR_BITCOUNT(1)) << 5) /* value */ \ + | ((((uint8_t)((address) >> 9))) & BITMASK_FOR_BITCOUNT(5)) /* address */ \ + ), \ + [1] = (uint8_t)((address) >> 1), /* address */ \ + } \ + } -- cgit v1.2.1