Hi Nico!
I'm not sure how to use a per erase-block counter? When would it update? we could only do that on every erase. A per variable counter might be useful, but I still hope it will work without.
I was thinking of putting a number in the first word of a block. Every time a new block is allocated, this value is written once. The value is the highest number already used plus 1. Also beware of wraparounds there.
Maybe a better option would be to have a maybe 64bit field in the header of every erase-block that gets gets erased with the whole block and every time blocks are erased an additional bit will get written in the other erase blocks that contain valid data. Your proposal to first mark an entry for update, then write the new entry and after that invalidate the old entry would solve this problem better though.
Updated scheme: With n erase blocks, the first n-1 blocks would be num- bered 0..n-2. The last block would be the "spare block". The spare block has a header (or footer, with size <= size of an entry's header) that contains the number of another block (or 0xffff).
I wouldn't use a dedicated spare block, since that will be the block that wears out first, since every time the same block is used. Just use one of the blocks in the ring buffer for that; that also eliminates a special case. Just make sure that always at least one erase-block isn't used for data.
Updated write: Before each write, check if the spare block is marked with another blocks number. If it is, find the first block with free space and continue the defragmentation process at this point.
Defragmentation:
Find duplicate entries and invalidate the ones added later
Hm, with using the older of the two entries, we make sure that we won't use an entry that isn't written completely. Good idea.
Find the first block m with invalid entries Write m into the spare block's footer Copy all valid entries from m into the spare block (it will fit, because there was at least one invalidated entry in m) For i in m .. n-3 Erase i For j in m+1 .. n-3 Copy all valid entries from j that fit into i, invalidating each! End For End For Add back all entries from spare block, invalidating each Erase the spare block
My proposal would be doing the normal mark, update, invalidate routine until only one erase block is left unused after the current write. If less than at least a full erase-block would be left after a write, a garbage collection/defragmentation run has to be done. In this run the non-invalidated entries from the first/oldest block get written to the last empty block. Then the valid data of the next block gets written to the space that might be left in the block where the contents of the block that was processed before the current source block were written to; if there isn't enough space for an entry, the next erased block will be used. With this the whole ring buffer will be defragmented. Sure, with another strategy the number of block erases could be further decreased, but the code should kept short and understandable; finding and fixing bugs that don't occur often isn't that fun.
To keep things simple, I'd also introduce the limitation that an entry mustn't be longer than the size of an erase-block.
Regards Felix