yaffs工作原理

1、how yaffs workscharles manning2007-2010table of contents 1 purpose.2 2 what is yaffs?.2 3 design and coding strategies.2 4 terminology: yaffs vs yaffs1 vs yaffs2.3 5 objects.3 6 the yaffs nand model.4 7 how yaffs1 stores files.4 8 garbage collection.7 9 yaffs1 serial numbers.8 10 yaffs2 nand model.9

2、10.1.yaffs2 extended tags.11 11 bad block handling nand error handling.11 12 ram structures.1212.1.yaffs_object.1312.2.objectid look-up.1312.3.directory structure.1412.4.hard links.1512.5.symbolic link and special object.1612.6.file object.16 12.6.1 tnode tree.16 13 how various mechanisms work.1713.

3、1.block and chunk management.17 13.1.1 block states.17 13.1.2 block and chunk allocation.19 13.1.3 a word about wear leveling.20 13.1.4 yaffs_tnode and yaffs_object management.2013.2.internal cache.2113.3.scanning.22 13.3.1 yaffs1 scanning.22 13.3.2 yaffs2 scanning.2213.4.checkpoint.2313.5.extended

4、tags and packed tags.2413.6.inband tags.2413.7.soft deletion.25page 1/25 1 purposethe purpose of this document is to give a reasonable explanation of most of the core mechanisms that make yaffs work. as of the time of writing this, the yaffs2 code base includes approximately 19,000 lines of code mak

5、ing a very detailed discussion impractical.this document should serve as a first port of call for understanding yaffs. further detailed questions and discussions are welcomed on the yaffs discussion list.this document is updated periodically. yaffs mechanism design changes from time to time and this

6、 document will not always reflect the most up to date code. 2 what is yaffs?yaffs stands for yet another flash file system , a term coined by charles manning in 2001 when suggesting that the already cluttered flash file system space could do with yet another offering this time a flash file system de

7、signed from the ground up to work with nand flash.the first release of yaffs was developed during the end of 2001 and the beginning of 2002. by mid-2002, yaffs was being trialled in various products. in may 2002, yaffs was announced and a few more projects started playing with it. in june, porting t

8、o other oss started. in september 2002, yaffs was announced on which started a far wider uptake of yaffs.yaffs1, the original version of yaffs, supported 512-byte page nand devices with a smartmedia-like memory layout.yaffs2 is a follow-up to yaffs1 extending yaffs1 to support larger and different d

9、evices with different constraints.yaffsis highly portable and has been used in many different products and applications as varied as sewing machines, point of sale, phones and aerospace. yaffs has been used with multiple different operating systems. native support is available for linux, windowsce a

10、nd ecos while yaffs direct interface provides a layer that can be used in other applications such as rtoss. yaffs has been used with multiple different cpus and compilers.yaffs has also been used as a nor file system and even as a ram file system. 3 design and coding strategiesyaffs is designed to w

11、ork in multiple environments which drives the need for portability. portability also improves the debugging and testing since it is easier to develop and debug code in an application environment than within an os kernel. this generally allows yaffs to progress faster with less programming resources.

12、 primary strategies that improve portability include:no os-specific features used in main code body.no compiler-specific features used in the main code body.abstract types and functions used to allow unicode or ascii operation.page 2/25simplicity is another key goal. complexity is limited to those s

13、ituations that provide significant improvements to performance or utility. simplicity improves robustness and the ease of integration and development. primary strategies that improve simplicity are:single threaded model. yaffs is locked on a per-partition basis at a high level. this is simpler than

14、tracking lower-level locking. yaffs direct interface uses a single lock for all partitions.log structure makes for a simpler garbage collector and allocation methodology.abstractions that build layered code which is easier to understand and debug. 4 terminology: yaffs vs yaffs1 vs yaffs2before we em

15、bark on our quest to understand what yaffs is, a terminology explanation is in order.there are two versions of yaffs code: the original yaffs code-base and the current yaffs2 code-base. the yaffs2 code-base supports functionality provided by the yaffs code-base as well as being extended with new fun

16、ctionality to provide extra modes of operation, most importantly those required to work with larger and more modern nand parts. the yaffs2 code-base supports the yaffs1 mode of operation through a backward compatibility mode.unless explicitly mentioned, this text refers to the yaffs2 code-base.this

17、text uses three terms yaffs, yaffs1 and yaffs2 depending on various modes of operation.?yaffs1 is a simpler mode of operation that uses deletion markers to track state. ?yaffs2 is a more complex mode of operating that was developed to support larger flash types that cannot used deletion markers.?yaf

18、fs means operations common to both.yaffs1 originally only worked with 512-byte page devices but has been extended to support larger flash pages such as intel m18 flash with 1k pages.yaffs2 was originally designed for 1k or larger page sizes but can be used with smaller pages by using in-band tags.si

19、nce the yaffs1 mode of operation is simpler to understand than the yaffs2 mode of operation, yaffs1 will be described first and readers interested in yaffs2 operation should first fully acquaint themselves with the yaffs1 mode of operation. it is suggested that this document be read sequentially rat

20、her than browsing it. 5 objectsin yaffs-speak, an object is anything that is stored in the file system. these are:regular data filesdirectorieshard-linkssymbolic linkspage 3/25special objects (pipes, devices etc).all objects are identified by a unique integer objectid.in the standard posix model, as

21、 used by linux, there are inodes and directory entries (dentries). an inode may be a regular file, directory, or special file.directory entries provide the naming mechanism that is used to locate inodes.under posix, each inode may have zero, one or many dentries:one dentry per inode is commonly unde

22、rstood.multiple dentries per inode allow the same inode to be accessed via multiple names. this is achieved through hard links.zero dentries per inode is less often understood. this happens when an inode is unlinked while there is still a handle open to the inode. the unlinking deletes the dentry bu

23、t the inode still exists. as soon as the handle is closed the inode is deleted too. 6 the yaffs nand modelthe memory in nand flash is arranged in pages. a page is the unit of allocation and programming. in yaffs, the unit of allocation is thechunk. typically a chunk will be the same as a nand page,

24、but there is flexibility to use chunks which map to multiple pages (eg. a system may have two nand chips in parallel requiring 2x512 = 1024 byte chunks) . this distinction gives a lot of flexibility in how the system can be configured. in this text the term page and chunk are synonymous unless state

25、d otherwise.many, typically 32 to 128 but as many as a few hundred, chunks form a block. a block is the unit of erasure. nand flash may be shipped with bad blocks and further blocks may go bad during the operation of the device. thus, yaffs is aware of bad blocks and needs to be able to detect and m

26、ark bad blocks.nand flash also typically requires the use of some sort of error detection and correction code (ecc). yaffs can either use existing ecc logic or provide its own. 7 how yaffs1 stores filesyaffs1 has a modified log structure, while yaffs2 (see below) has a true log structure. a true log

27、 structured file system only ever writes sequentially. yaffs1 uses deletion markers, which breaks the sequential write rule. yaffs2 does not use deletion markers and is thus a true log structured file system.instead of writing data in locations specific to the files, the file system data is written

28、in the form of a sequential log, the entries in the log are all one chunk in size and can hold one of two types of chunk:data chunk: a chunk holding regular data file contents.object header: a descriptor for an object (directory,regular data file, hard link, soft link, special descriptor,.). this ho

29、lds details such as the identifier for the parent directory, object name, etc.page 4/25each chunk has tags associated with it. the tags comprise the following important fields (others being ignored for now):objectid: identifies which object the chunk belongs to.chunkid : identifies where in the file

30、 this chunk belongs. a chunkid of zero signifies that this chunk contains an objectheader. chunkid=1 signifies the first chunk in the file (ie. at file offset 0), chunkid=2 is the next chunk and so on.deletion marker: (yaffs1 only) shows that this chunk is no longer in use.byte count: number of byte

31、s of data if this is a data chunk.serial number: (yaffs1 only) serial number used to differentiate chunks with the same objectid and chunkid.now lets bring that all together in an explanation. this is a simplified explanation and skips over issues such as soft deletion (mentioned later in the docume

32、nt). for explanation purposes, we shall consider usage of fictitious nand type that has 4 chunks per block, starting with an empty (erased) flash.first well create a file.blockchunkobjectidchunkiddeletioncomment105000liveobject header for this file (length 0)next we write a few chunks of data to the

33、 file.blockchunk objectidchunkiddeletioncomment105000liveobject header for this file (length 0)115001livefirst chunk of data125002livesecond chunk of data135003livethird chunk of datanext we close the file. this writers a new object header for the file. notice how the previous object header is delet

34、ed.blockchunk objectidchunkiddeletioncomment105000deletedobsoleted object header (length 0)115001livefirst chunk of data125002livesecond chunk of data135003livethird chunk of datapage 5/25205000livenew object header (length n)lets now open the file for read/write, overwrite part of the first chunk i

35、n the file and close the file. the replaced data and object header chunks become deleted.blockchunk objectidchunkiddeletioncomment105000deletedobsolete object header.115001deletedobsolete first chunk of data125002livesecond chunk of data135003livethird chunk of data205000deletedobsolete object heade

36、r215001livenew first chunk of file225000livenew object headernow lets resize the file to zero by opening the file with o_trunc and closing the file. this writes a new object header with length 0 and the contents are pruned making the data chunks deleted.blockchunk objectidchunkiddeletioncomment10500

37、0deletedobsolete object header.115001deletedobsolete first chunk of data125002deletedsecond chunk of data135003deletedthird chunk of data205000deletedobsolete object header215001deleteddeleted first chunk of file225000deltedobsoleted object header235000livenew object header (length 0).note how all t

38、he pages in block 1 are now marked as deleted. this means that block 1 no longer contains useful information so we can now erase block 1 and reuse the space.we will now rename the file. to do this we write a new object header for the filepage 6/25blockchunk objectidchunkiddeletedcomment10erased11era

39、sed12erased13erased205000deletedobsolete object header215001deleteddeleted first chunk of file225002deletedobsoleted object header235000deletedobsolete object header305000livenew object header showing new nameblock 2 now contains only deleted chunks and can be erased and reused.note how the tags tel

40、l us:?which chunks belong to which object,?the position of the chunks within a file,?which chunks are currentwith that information we can recreate the state of the files regardless of the placement of the chunks in nand. this means that should the system fail (crash, power fail,.) at any point durin

41、g the sequences above, we are still able to recover the file system state up to that point.note that there are no file allocation tables or similar structures stored in the flash. this reduces the amount of writing and erasing (improving write performance) while also improving robustness. corruption

42、 of file allocation tables and similar structures is a common failure mechanism for embedded file systems. the lack of such structures makes yaffs more robust. or, to put it another way, you cant corrupt what you dont store. 8 garbage collectionas we have shown so far, when a block is made up only o

43、f deleted chunks, that block can be erased and reused. however, consider what will happen if we have many blocks which each have a few current chunks in them. clearly we cannot erase any of the current blocks or we will destroy data. what we need to do is copy the useful data chunks off a block, del

44、eting the originals and allowing the block to be erased and reused. this process is referred to as garbage collection.the yaffs garbage collection process works as follows:1.find a block worth collecting (according the the heuristics below). if none found, then exit.2.iterate through the chunks in t

45、he block. if the chunk is in use then create a new copy and delete the original. fix up the ram data structures to reflect the change.page 7/25once all chunks in this block have been deleted, the block can be erased ready for reuse.note that although step 2 deletes the original chunk when it gets co

46、pied there is not much point in actually programming the deletion marker in flash since were about to erase the block anyway. thus yaffs does not program the deletion marker in these cases. if power is lost part way through the operation we can still tell the difference between the original and the

47、copy by looking at the serial number (not that it really matters anyway since the two have the same contents so either can be used).the heuristics to determine whether a block is worth collecting are as follows:1.if there are many erased blocks available, then yaffs does not need to work hard, but w

48、ill instead only attempt to perform garbage collection of blocks with very few chunks in use. this is termed passive garbage collection.2.if, however, there are very few erased blocks, yaffs will work much harder to recover more space and will garbage collect blocks with more chunks in use. this is

49、termed aggressive garbage collection.ok, the passive/aggressive names are a bit silly, but they were contrived around midnight. give me a break!if garbage collection is aggressive, the whole block is collected in a single garbage collection cycle. if the collection is passive then the number of copi

50、es is reduced thus spreading the effort over many garbage collection cycles. this is done to reduce garbage collection load and improve responsiveness.the rationale behind the above heuristics is to delay garbage collection when possible to reduce the amount of collection that needs to be performed,

51、 thus increasing average system performance. yet there is a conflicting goal of trying to spread the garbage collection so that it does not all happen at the same causing fluctuations in file system throughput. these conflicting goals make garbage tuning quite challenging.all flash file systems need

52、 some sort of garbage collector to reclaim space. the garbage collector is often a determining factor in the performance of the flash file system. many file systems have to do a significant amount of effort in a single collection sweep. yaffs only deals with one block at a time which constrains the

53、amount of effort in a garbage collection cycle, thus reducing the “ stall time”.the yaffs garbage collection algorithm is under review with the goal of reducing “ stall time” and increasing throughput. 9 yaffs1 serial numbersin yaffs1, each chunk is marked with a 2-bit serial number that is incremen

54、ted every time a chunk with the same tags value is replaced (eg. when a chunk is overwritten or when copied by garbage collection).now lets suppose first that we did not have a serial number. page 8/25lets consider a rename where an object header chunk must be replaced with a new one with the new na

55、me. yaffs could do the following:?delete the old chunk.?write the new chunk. if the system fails after the delete, the system could end up with no chunks matching the relevant tags values. this could cause files to be lost (end up in lost+found). thus, we have to write the new chunk before deleting

56、the old chunk.but now consider what might happen if we did this:?write new chunk.?delete old chunk.if the system failed after the write we now have two chunks that match the tags. how can we tell which one is current?the current chunk is determined by inspecting the serial number. since the serial n

57、umber is only incremented by one before the old chunk is deleted, a 2-bit serial number is sufficient. valid pairs are:oldnew0001011010111100thus, by inspecting the serial number attached to the old and new tags the current chunk can be determined and the old chunk can be deleted. 10 yaffs2 nand mod

58、elyaffs2 is an extension of yaffs designed to fulfill a new set of objectives to work with newer nand types including:zero overwrites. yaffs1 only ever overwrites a single byte in the spare area of the chunks to set the deletion marker. more modern nand devices are less tolerant of overwrites and ya

59、ffs2 performs no overwrites at all.sequential chunk writing within a block. more modern nand reliability specifications tend to assume sequential writing. since yaffs2 does not write deletion markers, the writing of chunks within a block is strictly sequential.since yaffs2 performs less writes, ther

60、e is potential for yaffs2 to have improved write performance.yaffs2 cannot use a deletion marker because that would violate the zero overwrites mandate and alternate mechanisms page 9/25are provided to determine which chunks are current and which are deleted. these mechanisms are:sequence number : a