On 06.01.2008 20:29, ron minnich wrote:
On Jan 6, 2008 3:29 AM, Stefan Reinauer stepan@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