[LinuxBIOS] [PATCH] v3: add a check for a termination member

[Carl-Daniel Hailfinger]

On 06.01.2008 20:29, ron minnich wrote:
> On Jan 6, 2008 3:29 AM, Stefan Reinauer <stepan at coresystems.de> wrote:
>
>   
>> And we can't cache the ROM because of CAR?
>>     
>
> yes.
>   

Well, we can't use CPU cache, but we can abuse CAR memory as cache
(ironic, isn't it? I'll call it CARAC.) for the first few (or all)
members in the LAR. The cost estimate would be 8-32 bytes per LAR
member, depending on your personal opinion on memory usage vs. speed
tradeoff.

>> I am not convinced that failing to find files has to be a performance
>> critical path - While I generally agree it must not take several
>> seconds, something's wrong with our logic if we fail to find files
>> before we have RAM and Cache enabled.
>>     
>
> I think we should eliminate all unnnecessary overhead. Scanning (e.g.)
> 2 Mbytes of memory for each failed lookup -- all the other BIOSes are
> going to point at us and make rude comments :-)
>   

I have another orthogonal design pending which incurs the lookup cost
only on the first lookup. See above for the basic idea. The first failed
lookup will incur the (almost) full cost of walking the LAR, all
subsequent lookups (whether successful or failed) will cost
O(larmembers) RAM/CARAC accesses.

> I really would like us to have a reasonable termination instead of
> searching all of memory. It can be anything -- make a file name called
> EOF. Carl-Daniel's design was nice because it was very flash-friendly,
> but I'm not picky.
>   

I guess I need to explain the rationale in more detail. Our routines
work just fine and with almost maximum efficiency achievable for a
linear search as long as there are no empty (erased) areas before the
LAR member we try to find. If there are empty areas in flash, we walk
those empty areas in 16 byte steps. That is horribly inefficient and
makes failed lookups slow, especially if your flash is almost empty.

The bootblock will always be the last member of the lar. We also try to
fill the lar from the bottom up. That means unless the lar is completely
full, we will walk an empty are in 16 byte increments. Since we know the
location of the boot block (top of flash) and we also know we never have
to lookup or load the bootblock during LB execution, there should be an
easy way to specify "from here to the beginning of the bootblock there
will be no file" which is equivalent to "stop searching here".
The "no file till bootblock" functionality can be implemented in three ways:
1. Explicit "stop searching here" marker or lar member.
2. Explicit lar member covering the free space.
3. List free space somehere in flash.

Two of these ways fail in practice:
3. Listing free space in flash means erasing and/or rewriting that list
everytime the lar changes. The only reasonable place for such a list
would be the bootblock and we don't want to touch it during partial reflash.
2. Explicit free space covering lar member is fine, but to add any new
file to the archive, you have to erase the part covered by the exlusive
space.

That leaves way #1:
1. Explicit "stop searching here" marker. Either we arrange for the
marker bit pattern to be overwritable without erasing or not. Using the
"normal" LAR header infrastructure, that would be an entry starting with
"LARCHIVE" followed by a series of 0xFF bytes . That way, we can create
a new LAR member without having to erase anything because the "LARCHIVE"
magic stays the same and all other bits are still 1 and can be written to.


Regards,
Carl-Daniel