[Yaffs] Tnode tallness (trading memory for nand reads)

[Charles Manning]

I spoke with Brad on the phone about this (handy living in the same part =
of=20
the world eh?) and herewith a description.

The YAFFS Tnode tree structure has "leaf nodes" which are 16 bits wide. T=
hese=20
leaf nodes are used to indentify the chunk (page) in NAND for that part o=
f=20
the file. If there are less than 2^16 (ie 64k) chunks in the flash partit=
ion=20
then the look-up is very fast. But let's look at what happens when you ha=
ve a=20
512MB partition. This has 2^20 pages. This means we're short 4 bits. YAFF=
S=20
resolves this by using "chunk groups". The 16 bits in the tnode are used =
to=20
resolve to a "chunk group" and the chunk within the chunk group is found =
by=20
brute force searching. On our 512MB device you might need to look at up t=
o 16=20
(but average 8.5) chunks to locate the correct one.=20

A potential solution is to widen the tnode structure so that it can suppo=
rt=20
larger numbers. This could be dynamic (ie. determined at run time) to all=
ow=20
trade offs to be made. eg. 512MB with lots of free RAM, just make the tno=
de=20
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 i=
t
> correctly, when yaffs needs to find a chunk in nand,
> yaffs_FindChunkInFile is called which walks the tnode structure until i=
t
> 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 th=
e
> 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