Hi Nico!
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).
No, always choosing the first would be determined behavior. In case we keep things in order it's also the better choice when it comes to sear- ching the current, valid entry (we'd have to always search the whole used space for a newer version otherwise). I'd treat it like this: If the old version wasn't invalidated, the update didn't finish. So we can ignore the new version.
I was assuming the ring buffer case here where the first entry in the raw flash address space doesn't have to be the oldest one.
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).
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.
Might be done in a sanitation phase before each write. But if we define the first entry to be the valid one, we probably don't need it. Update: I didn't come around in my scheme below... maybe we should make the update in three steps: tag for update, insert new value, invalidate. This way we would only have to search for duplicates for valid entries tagged for update.
Good idea.
Defragmentation:
Haven't really looked at and thought about your defragmentation phase idea; maybe I'll comment on that next week.
Regards Felix