I spoke with Brad on the phone about this (handy living in the same part of
the world eh?) and herewith a description.
The YAFFS Tnode tree structure has "leaf nodes" which are 16 bits wide. These
leaf nodes are used to indentify the chunk (page) in NAND for that part of
the file. If there are less than 2^16 (ie 64k) chunks in the flash partition
then the look-up is very fast. But let's look at what happens when you have a
512MB partition. This has 2^20 pages. This means we're short 4 bits. YAFFS
resolves this by using "chunk groups". The 16 bits in the tnode are used to
resolve to a "chunk group" and the chunk within the chunk group is found by
brute force searching. On our 512MB device you might need to look at up to 16
(but average 8.5) chunks to locate the correct one.
A potential solution is to widen the tnode structure so that it can support
larger numbers. This could be dynamic (ie. determined at run time) to allow
trade offs to be made. eg. 512MB with lots of free RAM, just make the tnode
entries 20 bits each. 512MB but a bit less memory, keep them 16 bits each.
-- Charles
On Wednesday 02 February 2005 09:44, Brad Beveridge wrote:
> Hi all, I've been taking a bit of a look through the yaffs source code,
> in particular looking at the Tnode structures. If I am understanding it
> correctly, when yaffs needs to find a chunk in nand,
> yaffs_FindChunkInFile is called which walks the tnode structure until it
> hits the leaf nodes, and then scans up to dev->chunkGroupSize spare
> areas to find the correct chunk. I'm not sure, but I think that
> chunkGroupSize could be up to a whole block. From our quick analysis,
> reading these spare areas to find the correct chunk is taking quite a
> hit on our read performance (ie, we expect ~7Mb/s, but are getting
> closer to 2Mb/s)
> I have a couple of questions
> 1) How easy is it to trade memory space for nand reads in this case?
> Ie, can we reduce the number of nand reads that are required to find the
> right chunk. In our particular system where memory is plentiful, we
> would like to find the correct chunk first time every time without
> having to (slowly) read the nand.
> 2) Is it worth trying to optimise for the usual read case? I expect
> that the usual read case would be to read more than 1 chunk sized area,
> so perhaps Yaffs should remember where the last chunk resided, and on
> the next chunk read - if the Tnode leaf is the same - check the next
> sequential chunk to see if it is the correct one.
>
> Thanks for any comments.
>
> Cheers
> Brad
>
> _______________________________________________
> yaffs mailing list
> yaffs@stoneboat.aleph1.co.uk
> http://stoneboat.aleph1.co.uk/cgi-bin/mailman/listinfo/yaffs
(text/plain)