Re: [Yaffs] architecture problem with yaffs2 scanBackwards

On Thursday 11 December 2008 22:30:53 pagcal@runbox.com wrote:
> ----- Start Original Message -----
> Sent: Thu, 11 Dec 2008 09:33:01 +1300
> From: Charles Manning <manningc2@actrix.gen.nz>
> To: yaffs@lists.aleph1.co.uk
> Subject: Re: [Yaffs] architecture problem with yaffs2 scanBackwards
>
> > On Thursday 11 December 2008 01:53:58 Cal Page wrote:
> > > yaffs2 runs fine forever as long as I mount/dismount, but if I crash,
> > > it scrambles the file system.
> > >
> > > Specifically, garbage collection that moves chunks out of blocks
> > > re-tags the chunk with its new sequenceNumber.
> >
> > It is supposed to do that.
> >
> > Try reading http://users.actrix.co.nz/manningc/yaffs/HowYaffsWorks.pdf
> >
> > > Then, if the system crashes,
> > > scanBackwards will receive this moved chunk out of order.
> >
> > The order that matters is time order, not physical order.
> >
> > The sequence numbers are used to identify the order in which the logs
> > were written and allow us to "replay history" to rebuild the file system
> > state.
Cal, as Wookey has said, you really need to improve your understanding of how
this works with a good read of the doc.

> >
> > When a garbage collection happens, live data on the block is copied out
> > and is reassigned with the new sequence number. Since it now has a more
> > recent sequenceNumber, the ScanBackwards() will encounter it sooner.
>
> This is precisely the problem. The moved chunk should not be encountered
> sooner, but rather, be encountered WHEN IT WAS CREATED. If you change its
> sequenceNumber, you destroy the time order.

It does not matter when it is encountered during the scan, so long as we can
tell that it is still valid.

The time order must be preserved to handle deletions, shrinks, renames etc as
well as being able to distinguish between current and obsolete data.

For example if we find three chunks that both match the same objectId:chunkId,
we can use the sequence number to resolve this:
* The most recent one (with the greatest sequence number) is the valid one and
others are obsolete.
* Since we scan backwards by sequence number, the most recently created one is
the one that is encountered first.

Since garbage collection only copies the valid data, that will be the one that
gets the highest sequence number and is encountered first.

Invalid data will get ignored by gc.


>
> I would think the easiest fix would be to update the sequenceNumber each
> time a new chunk is written. But, if the chunk were moved, the
> sequenceNumber would stay the same. scanBackwards would change because it
> would have to collect sequenceNumbers by chunk instead of block, sort them,
> and then walk through the chunks in sorted order. To keep from overflowing,
> sequenceNumber would have go go to 64 bits.

That would require sorting on a per-chunk basis, not a per-block basis. That
would drive up the sorting and scanning costs.

We essentially still have that information: the combination of
objectId,chunkId and sequence number will always tell you which is the most
up to date version of a chunk.

>
> There are other problems with scanBackwards. One was that it attempts to
> re-find the allocation point. But, if the block is full, then it fails. I
> now check for this condition and tell the block allocator it must re-search
> for a new allocation point.

Please elaborate a bit more.

-- Charles

>
> Cal Page
>
> > > Typically, I get a lot of files in lost+found.
> >
> > Can you do an "ls-ial" on lost+found and include that.
> >
> > This sounds very much like the tags are getting mashed by the mtd layer
> > or mtd interfacing.
> >
> > I suggest you do some simple verifications to ensure that the tags are
> > getting saved and restored properly.
> >
> > -- CHarles
>
> ----- End Original Message -----
>
> _______________________________________________
> yaffs mailing list
> yaffs@lists.aleph1.co.uk
> http://lists.aleph1.co.uk/cgi-bin/mailman/listinfo/yaffs