Re: [Yaffs] architecture problem with yaffs2 scanBackwards

Top Page
Attachments:
Message as email
+ (text/plain)
Delete this message
Reply to this message
Author: Wookey
Date:  
To: yaffs
Subject: Re: [Yaffs] architecture problem with yaffs2 scanBackwards
On 2008-12-11 04:30 -0500, wrote:
> Charles Manning <> wrote:
> > 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.
> >
> > 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.


erm, Cal. I don't think you understand properly how this works. Did you read
the bit about sequence numbers in the above pdf?

A new block written due to garbage collection _replaces_ ones that
previously held the data, so it has a newer sequence number. That's
correct. Then scanbackwards will correct ignore the blocks containing
the same data but with older sequence numbers as obsolete. i.e.
chronological data oreding _is_ preserved.

> 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.


It doesn't need fixing: it already works. There must be some
misunderstanding here. Can you give an example of what situation is
going wrong for you? Or explain in detail a circumstance where the
GC/sequencenumber/scanbackwards algorithm is wrong?

> 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.


erm. I don't follow this. Do you have a patch? That might help explain the
issue?

Wookey
--
Principal hats: Balloonz - Toby Churchill - Aleph One - Debian
http://wookware.org/