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
--
coreboot mailing list: [email protected]
https://mail.coreboot.org/mailman/listinfo/coreboot
