[coreboot] how to implement variable read/write variable in coreboot

[Felix Held]

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