[Yaffs-archive] YAFFS - YAFFS2 starts

Top Page
Attachments:
Message as email
+ (text/plain)
+ yaffs2.html (text/html)
Delete this message
Reply to this message
Author: Charles Manning
Date:  
To: yaffs
Subject: [Yaffs-archive] YAFFS - YAFFS2 starts
I have started working on YAFFS2.

The main purpose behind YAFFS2 is to support the larger NAND parts with 2kB
pages and zero rewrite. But wait, there's more... lower RAM footprint,
faster,...

YAFFS2 needs at least a 1kB chunk size. On 512byte pages you can do this by
just using two pages per chunk. This means a bit more wasted space at the end
of files. Thus, probably the best approach will be to use YAFFS1 on NAND
arrays less than, say, 128MB.

Since almost all the algorithms are the same for YAFFS1 and YAFFS2, I expect
to keep the code together with YAFFS1 or YAFFS2 being run-time selectable (ie
as a flag in the device structure).

Any ideas/input/wishes more than welcome.

Herewith a brief outline.

-- CHarles






    
    
    
    
    
    
    


YAFFS2
Summary
The original motivation for YAFFS 2 was to add support for the new
NAND with 2kB pages instead of 512-byte pages and strictly sequential
page writing order.

To achieve this, a new design is used which also realises the
following benefits:

    zero page rewrites means faster operation. (YAFFS1 uses a
    single rewrite in the spare area to delete a page).

    ability to exploit simultaneous page programming on some
    chips.

    improves performance relative to YAFFS1 speed(write:1.5x to
    5x, delete: 4x, garbage collection: 2x)

    lower RAM footprint (approx. 25% to 50% of YAFFS1).
    Can support Toshiba/Sandisk MLC parts.

Most of YAFFS and YAFFS2 code is common, therefore the code will
likely be kept common with YAFFS vs YAFFS2 being run-time selected.
Method
The main philosophical difference between YAFFS and YAFFS2 is how
discarded status is tracked. Since we can't do any re-writing, we
can't use the "discarded" flags in YAFFS2.


Instead YAFFS2 uses two mechanisms to resolve data state.

    YAFFS2 chunks have more tag information, including a block
    sequence Id. From that we can determine the chunk sequence Id since
    the chunks are allocated sequentially in a block. Thus we always
    know the patch order for all chunks in the system.

    The above helps us track stale -vs- fresh data, but does not
    help determine when a file/object is deleted. Deletion is achieved
    by moving the object to the "unlinked" directory. We also
    keep track of the number of chunks (both stale and current) in the
    system for each object. While this number indicates that there are
    still chunks associated with this object we keep the deletion
    record. When the last trace of the object has been really erased
    from NAND, we can forget about the deletion record too. 

    
    Since there is no deletion, a resize (shrinking) of a file
    will still have valid data chunks past the end of file on the NAND.
    However, we write a new ObjectHeader at the time of the resize,
    therefore this shows the shrunken file size.


This changes erasure slightly:

    During garbage collection we can't just look at chunk state
    flags, instead we must read the tags of each chunk to determine
    which object's chunk count we must decrement. This step must also be
    performed when a block is erased (as part of deletion).


This makes erasure & garbage collection more expensive (by
adding reads), but remember that ion YAFFS2 we don't need to do page
deletions which are much more expensive operations. Thus, all-up
YAFFS2 wins.
Tag structure
Each chunk in YAFFS2 has the following information:

    
    
    
    
    
        
            
                Field
            
            
                Comment
            
            
                Size for 1kb chunks
            
            
                Size for 2kB chunks
            
        
    
    
        
            
                blockState
            
            
                Block state. non-0xFF for bad block
            
            
                1 byte
            
            
                1 byte
            
        
        
            
                chunkId
            
            
                32-bit chunk Id
            
            
                4 bytes
            
            
                4 bytes
            
        
        
            
                objectId
            
            
                32-bit object Id
            
            
                4 bytes
            
            
                4 bytes
            
        
        
            
                nBytes
            
            
                Number of data bytes in this chunk
            
            
                2 bytes
            
            
                2 bytes
            
        
        
            
                blockSequence
            
            
                sequence number for this block
            
            
                4 bytes
            
            
                4 bytes
            
        
        
            
                tagsEcc
            
            
                ECC on tags area
            
            
                3 bytes
            
            
                3 bytes
            
        
        
            
                ecc
            
            
                ECC, 3 bytes/256 bytes of data
            
            
                12 bytes
            
            
                24 bytes
            
        
        
            
                Total
            
            
                
                
            
            
                30 bytes
            
            
                42 bytes
            
        
    



To get enough spare bytes for this tagging structure requires a
chunk-size of at least 1kB.
The blockSequence increments each time a block is allocated. (ie.
the first block allocated is block 1, and so on).
Scanning
The only reason we need to keep track of data status on NAND is to
be able to recreate the file system state during scanning. Since we
no longer have chunk deletion status flags we use a slightly
different process for scanning a YAFFS2 system.
In effect, YAFFS2 recreates its state by "replaying the
tape". ie. it scans the chunks in their allocation order (block
sequence Id order) rather than in their order on the media. This
implies that at start up, the blocks must be read and their block
sequence determined.
Performance
Times for 2kB read(units of 1uS).

    
    
    
    
    
    
        
            
                Operation
            
            
                YAFFS1
            
            
                YAFFS2 (512b pages)
            
            
                YAFFS2 (2kB pages)
            
            
                YAFFS2(2kB pages, x16)
            
        
    
    
        
            
                Seek
                
            
            
                40
            
            
                40
            
            
                10
            
            
                10
            
        
        
            
                Read
            
            
                220
            
            
                220
            
            
                220
            
            
                110
            
        
        
            
                Total
            
            
                260
            
            
                260
            
            
                230
            
            
                120
            
        
        
            
                MB/s
            
            
                7.6
            
            
                7.6
            
            
                8.7
            
            
                16.7
            
        
        
            
                Relative speed
            
            
                1
            
            
                1
            
            
                1.1
            
            
                2.2
            
        
    



Times for 2kB writes(units of 1uS).

    
    
    
    
    
    
        
            
                Operation
            
            
                YAFFS1
            
            
                YAFFS2 (512b pages)
            
            
                YAFFS2 (2kB pages)
            
            
                YAFFS2(2kB pages, x16)
            
        
    
    
        
            
                Seek
            
            
                40
            
            
                40
            
            
                10
            
            
                10
            
        
        
            
                Program
            
            
                800
            
            
                800
            
            
                200
            
            
                200
            
        
        
            
                Seek
            
            
                40
            
            
                40
            
            
                10
            
            
                10
            
        
        
            
                Read
            
            
                220
            
            
                220
            
            
                220
            
            
                110
            
        
        
            
                Total
            
            
                1320
            
            
                1320
            
            
                660
            
            
                440
            
        
        
            
                MB/s
            
            
                1.5
            
            
                1.5
            
            
                3
            
            
                4.5
            
        
        
            
                Relative speed
            
            
                1
            
            
                1
            
            
                2
            
            
                3
            
        
    



Times for 1MB delete (units of 1uS).

    
    
    
    
    
    
        
            
                Operation
            
            
                YAFFS1
            
            
                YAFFS2 (512b pages)
            
            
                YAFFS2 (2kB pages)
            
            
                YAFFS2(2kB pages, x16)
            
        
    
    
        
            
                Seek
            
            
                20480
            
            
                0
            
            
                0
            
            
                0
            
        
        
            
                Program
            
            
                409600
            
            
                0
            
            
                0
            
            
                0
            
        
        
            
                Erase
            
            
                128000
            
            
                128000
            
            
                16000
            
            
                16000
            
        
        
            
                Total
            
            
                558080
            
            
                128000
            
            
                16000
            
            
                16000
            
        
        
            
                MB/s
            
            
                1.8
            
            
                7.8
            
            
                62.5
            
            
                62.5
            
        
        
            
                Relative speed
            
            
                1
            
            
                4
            
            
                34
            
            
                34
            
        
    



Times for 1MB of garbage collection at 50% dirty (units of 1uS).

    
    
    
    
    
    
        
            
                Operation
            
            
                YAFFS1
            
            
                YAFFS2 (512b pages)
            
            
                YAFFS2 (2kB pages)
            
            
                YAFFS2(2kB pages, x16)
            
        
    
    
        
            
                Delete 1MB
            
            
                558080
            
            
                128000
            
            
                16000
            
            
                16000
            
        
        
            
                Write 0.5MB
            
            
                337920
            
            
                337920
            
            
                168960
            
            
                112640
            
        
        
            
                Total
            
            
                896000
            
            
                465920
            
            
                184960
            
            
                128640
            
        
        
            
                MB/s
            
            
                1.1
            
            
                2.1
            
            
                5.4
            
            
                7.7
            
        
        
            
                Relative speed
            
            
                1
            
            
                1.9
            
            
                4.9
            
            
                7
            
        
    



$Id$