Peristent values #7
Description
Currently value changes are not persisted. Many chips only offer data flash instead of eeprom, so a suitable strategy would be useful. Here's an idea.
RA4M1 data flash (UNO R4) is erasable in 1K blocks but writable in individual bytes. It's not very practical to persist a single cell value in the same place in data flash. Ideally any updates should be simply written into the empty space in the data flash. This means that the actual value would have to be found by searching the data flash. This would be annoying and slow to do on every value read, but we could instead back the value with a RAM slot and only search the dataflash at startup to initialize the RAM slot.
This way value reads would be very fast. Value writes would write both the RAM slot and write the update record into the data flash. After reset all the value RAM slots would have to be initialized by searching the data flash.
To make the data flash searchable, each value needs to be identifiable. The simplest is probably giving it a cell sized ID. We could store the ID with the value word definition and have it be something recognizable by a human. That would make inspecting the data flash contents easier. The downside is that we then need to search the dictionary to figure out how IDs map to RAM addresses.
The simplest is probably to use the value RAM address as the ID. The data flash records would be two cells, the first one being the ID and second one with the actual value. This would yield a very simple value initialization procedure. Simply run from the start of the data flash to the (written) end, and for each record write the value to the address pointed to by the identifier. Once you reach a record with ID -1 (unwritten flash), set the data flash VP to its address and you are done. Note that the data flash VP won't be a persistent value, it would be RAM only and initialized by finding the end of the written data flash.
Finally we need a way to compact the value flash when it fills up. A critical requirement is that the written state of the flash is always such that we can recover correctly even if the board resets in the middle of the compaction, we don't want to lose values because compation wasn't able to complete successfully. Here's how we could go about this (again going for the simplest, rather than fastest or otherwise optimal approach).
The value flash will be allocated in two arenas of the same size. One arena will always be the active one, the other will be dormant and used as a compaction target when the time comes. After successful compaction the roles will be reversed.
The arena size must be a multiple of flash erase page size. It should be probably be at least twice the size of the total space required to house the flash records of the maximum number of persistent values. This is so that when the flash is compacted it is at most half full to allow for value update records. So if we want to support up to N values, the arena size should be at least N * (2 * cellsize) * VF, where VF is the "vacancy factor" of at least 2 and probably should be higher, depending on the expected rate of value updates and desired compaction frequency.
The first value record of an arena will be used to identify the state of the arena. The ID field should always contain a value that is distinct from possible value IDs. ID -1 (unwritten) indicates dormant arena that was successfully erased. Let's say value addresses always have their MSB clear, so arena IDs must have this bit set. Flipping the roles of arenas will be the critical step, at that point the newly compacted arena will have to be marked active and the previously active arena will needs to be erased. This cannot be done atomically so there will be a moment when both arenas are marked active and we need to be able to say which one should stay and which one should go. We will do that by using the ID as a counter. When we go to mark the compacted arena as active we will write its ID to be one more than the old arena ID. If we crash and restart after that point, and both arenas have a valid ID (not -1) we will pick the one with the higher ID (overflow should be handled but with 31-bits that is a lot of arena flips before that becomes an issue). Then we finish erasing the other one.
So with arena lifecycle settled, we just need the compaction algorithm. The simplest is to walk the dictionary for all value definitions and writing their RAM values into new value records in the dormant arena. We can use value side of the arena record to indicate whether the flash is clean or has been written into. If the value is -1 it is clean (fresh erased). We start the compaction by writing 0 into the value of arena record and then continue writing the value records. If at the start of the compatction the value of arena record is not (-1) we will erase the arena first.
And that should be it. What's left is to decide when compaction runs. It could be invoked automatically when the active arena fills up. Any subsequent value update would have to perform successful compaction/arena flip first. Alternatively we could have value updates just throw until compaction is invoked manually and succeeds, to have a bit more control over the potentially somewhat slow operation.