Hi!
Write strategy: Invalidate any entry with matching key, append after last entry if there is enough space in the current erase block. If not, finalize current erase block with an invalid entry spanning the free space of the block, write variable into next erase block. If we run out of erase blocks, defragment the whole thing (needs one com- plete erase block size to cache things, afaics)?
What happens when the power gets cut right between invalidating the old entry and writing the new entry? One of the design goals should be to always have a consistent state in the flash chip. So for the case that there is enough free space in the SPI NOR flash, I'd write the new entry and invalidate the old entry after that. For the defragmentation at least one erase block needs to be reserved so that the new entries can be written before the old ones are invalidated. The easiest method of wear leveling would be to use the blocks as a ring buffer; sure this doesn't minimize the number of erase cycles, but since NOR flash is quite robust and new entries probably won't get written that often, I'd probably prefer this less complex approach to increase the code readability and maintainability.
Read strategy: Either cache and index the whole thing, or read until the first valid entry with matching key.
The question I have here is what to do if there is more than one valid entry. Just using the first one introduces a bit of undetermined behavior (block order in the flash might be different after defragmentation). So either use some counter (beware of overflows!) on either the flash erase block (small overhead and rather efficient) or the entry (full region has to be either cached or read every time and needs more bytes than the counter per erase block) or accept the possibility of undetermined behavior (IMHO not a good idea). Also a good idea would be to invalidate everything except the newest entry when reading in the case that there is more than one valid entry.
For boolean options you can also reserve a word of 32 or 64 bits and flip one bit for every toggle and test if the number of flipped bits is even or odd, so you don't have to write a new entry every time the option gets toggled. Also works for n-bit values, but I'm not sure if it's worth the more complex code.
Having some sort of key-value store that can be written to during runtime would also be great for replacing the CMOS user option table thing.
Regards Felix