📄 yaffs-notes2.html
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN"><HTML><HEAD> <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1"> <TITLE></TITLE> <META NAME="GENERATOR" CONTENT="StarOffice/5.2 (Linux)"> <META NAME="AUTHOR" CONTENT=" "> <META NAME="CREATED" CONTENT="20020429;14311100"> <META NAME="CHANGEDBY" CONTENT=" "> <META NAME="CHANGED" CONTENT="20020513;21133100"></HEAD><BODY><H1 ALIGN=CENTER>YAFFS Development Notes</H1><P><BR><BR></P><P><BR><BR></P><H3>Build options</H3><P>Yaffs can be built as either a kernel module (ie. a Linux filesystem) or as an application.</P><P>Of course the goal is to build yaffs as a file system running ontop of real NAND flash, but yaffs can be built to run on a RAMemulation layer for in-kernel testing without NAND flash in thesystem.</P><P>Building as an application allows the yaffs_guts algorithms to betested/debugged in a more friendly debugging environment. The testharness is in yaffsdev.c</P><H3>Trying it out</H3><P>YAFFS can be built to run with either mtd or RAM emulation, orboth. The file system that interfaces to mtd is called <B>yaffs</B>,the file system that uses internal ram is called <B>yaffsram</B>.YAFFS simultaneously supports both if they are enabled.</P><OL> <LI><P>Hack the Makefile and change the KERNELDIR define to your kernel directory.</P> <LI><P>If you don't have mtd support in your kernel, then you might need to turn off USE_MTD otherwise the yaffs module might not load.</P> <LI><P>Type <B><FONT FACE="Courier, monospace">make clean; make</FONT></B> to build yaffs</P> <LI><P>Load yaffs as a module by typing <B><FONT FACE="Courier, monospace">/sbin/insmod yaffs.o</FONT></B> (ya gotta be root!).</P> <LI><P>Create a mount point eg. <B><FONT FACE="Courier, monospace">mkdir /mnt/y</FONT></B></P> <LI><P>To mount the RAM emulation version of yaffs, <B><FONT FACE="Courier, monospace">mount -t yaffsram none /mnt/y</FONT></B></P> <LI><P><FONT FACE="Courier, monospace"><SPAN STYLE="font-weight: medium"><FONT FACE="Times, serif">Alternatively, to mount the mtd version of yaffs,</FONT></SPAN><B> mount -t yaffs /dev/mtd0 /mnt/y</B></FONT></P></OL><P><BR><BR></P><H3>YAFFS Data structures</H3><P>All data types are defined in yaffs_guts.h</P><P>Yaffs uses the following major objects:</P><UL> <LI><P>yaffs_Object: A yaffs_Object can be a file, directory, symlink or hardlink. The yaffs_Objects "know" about their corresponding yaffs_ObjectHeader in NAND and the data for that object. yaffs_Objects also bind together the directory structure as follows:</P> <LI><P>parent: pointer to the yaffs_Object that is a parent of this yaffs_Object in the directory structure.</P> <LI><P>siblings: this field is used to link together a list of all the yaffs_Objects in the same directory.</P> <LI><P>children: if the object is a directory, then children holds the head of the list of objects in the directory.</P> <LI><P>yaffs_Tnode: yaffs_Tnodes form a tree structure that speeds up the search for data chunks in a file. As the file grows in size, the levels increase. The Tnodes are a constant size (32 bytes). Level 0 (ie the lowest level) comprise 16 2-byte entries giving an index used to search for the chunkId. Tnodes at other levels comprise 8 4-byte pointer entries to other tnodes lower in the tree.</P> <LI><P>yaffs_Device: this holds the device context and is in some ways analogous to the VFS superblock. It stores the data used to access the mtd as well as function pointers to access the NAND data.</P></UL><P>The Tnodes and Objects are allocated in groups to reduce memoryallocation/freeing overheads. Freed up tnodes and objects are kept ina free list and re-used.</P><H3>yaffs_Object</H3><P><BR><BR></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>struct yaffs_ObjectStruct</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8fake:1; // A fake object has no presence on NAND.</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8renameAllowed:1; // Are we allowed to rename it?</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8unlinkAllowed:1; // Are we allowed to unlink it?</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8dirty:1; // the object needs to be written to flash</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8valid:1; // When the file system is being loaded up, this </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> // object might be created before the data</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> // is available (ie. file data records appear before the header).</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u8serial; // serial number of chunk in NAND. Store here so wedon't have to</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> // read back the old one to update.</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u16sum; // sum of the name to speed searching</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> structyaffs_DeviceStruct *myDev; // The device I'm on</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> structlist_head hashLink; // list of objects in this hash bucket</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> structlist_head hardLinks; // all the equivalent hard linked objects</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> //live on this list</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> //directory structure stuff</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> structyaffs_ObjectStruct *parent; //my parent directory</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> structlist_head siblings; // siblings in a directory</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> // also used for linking up the free list</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> //Where's my data in NAND?</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> intchunkId; // where it lives</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32objectId; // the object id value</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_mode; // protection</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_uid; // user ID of owner</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_gid; // group ID of owner </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_atime; // time of last access</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_mtime; // time of last modification</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> __u32st_ctime; // time of last change</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> yaffs_ObjectTypevariantType;</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> yaffs_ObjectVariantvariant;</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>};</FONT></FONT></P><P><BR><BR></P><P>Obvious stuff skipped....</P><P>fake, renameAllowed, unlinkAllowed are special flags for handling"fake" objects which live in the file system but do notlive on NAND. Currently there are only two such objects: the rootobject and the lost+found directory. None of these may be renamed orunlinked.</P><P>serial, sum: see yaffs_ObjectHeader.</P><P>dirty indicates that the object's contents has changed and a newyaffs_ObjectHeader must be written to flash.</P><P>valid indicates that the object has been loaded up. This is onlyused during scanning (yaffs_Scan()) since we can know of an object'sexistance - and thus need to create the object header - before weencounter the associated yaffs_ObjectHeader.</P><P>hashlink is a list of Objects in the same hash bucket. </P><P>The four variants hold extra info:</P><P>Files hold the file size and the top level and pointer to thetnode tree for the file.</P><P>Directories hold a list of children objects.</P><P>Symlinks hold a pointer to the alias string. This is probablyinefficient, but that probably does not matter since we don't expectto see many of these. </P><P>Hardlinks hold information to identify the equivalent object.</P><P><BR><BR></P><P><BR><BR></P><H3>File structure (tnodes)</H3><P>File structures are done with a tiered indexing structure</P><P><BR><BR></P><P><IMG SRC="sv9349341.gif" NAME="Graphic2" ALIGN=LEFT WIDTH=491 HEIGHT=294 BORDER=0><BR CLEAR=LEFT><BR><BR></P><P>The file structure is maintained by a tree structure. Dependingwhere it is in the tree, each tree node (<B><I>tnode</I></B>) (theblue/things) holds either:</P><UL> <LI><P>.... if it is at the lowest level, then 16 __u16s which identify the page.</P> <LI><P>.... if it is at a higher level (ie an internal tnode), then 8 pointers to lowest-level tnodes.</P></UL><P>When the file starts out, it is assigned only one low-level tnode.When the file expands past what a single tnode can hold, then it isassigned a second tnode and an internal node is added to point to thetwo tnodes. As the file grows, more low-level tnodes and high leveltnodes are added.</P><P>Traversing the tnode tree to find a particular page in a file isquite simple: each internal tnode is selected from by using 3 bits ofthe page offset in the file. The level 0 page resolves 4 bits.</P><P>For example, finding page 0x235 (ie. the one starting at fileposition 0x46800 would proceed as follows:</P><P>0x235 is 0000001000110101, partitioned as follows.000.000.100.011.0101</P><TABLE WIDTH=496 BORDER=1 CELLPADDING=4 CELLSPACING=3> <COL WIDTH=140> <COL WIDTH=160> <COL WIDTH=158> <THEAD> <TR VALIGN=TOP> <TH WIDTH=140> <P>Level</P> </TH> <TH WIDTH=160> <P>Bits</P> </TH> <TH WIDTH=158> <P>Selected value</P> </TH> </TR> </THEAD> <TBODY> <TR VALIGN=TOP> <TD WIDTH=140> <P>3 or more if they exist</P> </TD> <TD WIDTH=160> <P>>= 10</P> </TD> <TD WIDTH=158> <P>Zero</P> </TD> </TR> <TR> <TD WIDTH=140 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;"> <P ALIGN=RIGHT>2</P> </TD> <TD WIDTH=160 VALIGN=TOP> <P ALIGN=LEFT>9 to 7</P> </TD> <TD WIDTH=158 VALIGN=TOP> <P>100 binary = 4</P> </TD> </TR> <TR> <TD WIDTH=140 VALIGN=BOTTOM SDVAL="1" SDNUM="5129;"> <P ALIGN=RIGHT>1</P> </TD> <TD WIDTH=160 VALIGN=TOP> <P ALIGN=LEFT>6 to 4</P> </TD> <TD WIDTH=158 VALIGN=TOP> <P>011 binary = 3</P> </TD> </TR> <TR> <TD WIDTH=140 VALIGN=BOTTOM SDVAL="0" SDNUM="5129;"> <P ALIGN=RIGHT>0</P> </TD> <TD WIDTH=160 VALIGN=TOP> <P ALIGN=LEFT>3 to 0</P> </TD> <TD WIDTH=158 VALIGN=TOP> <P>0101 binary = 5</P> </TD> </TR> </TBODY></TABLE><P><BR><BR></P><P>Free tnodes are stored in a list. When the list is exhausted, moreare allocated.</P><P>Each tnode takes 32 bytes. Each file needs at least one level 0tnode. How many do we need? A full 16MB file system needs at least16MB/512/16 = 2000 level zero tnodes. More for internal tnodes. Morefor files smaller than optimal.</P><P>The tree grows as required. When the file is resized to a smallersize then it is pruned.</P><P><BR><BR></P><H3>NAND data</H3><P>Data is stored on NAND in "chunks". Currently each chunkis the same size as a NAND flash page (ie. 512 bytes + 16 bytespare). In the future we might decide to allow for different chunksizes. Chunks can hold either:</P><UL> <LI><P>A yaffs_ObjectHeader. This is the way a yaffs_Object gets stored on NAND.</P> <LI><P>A chunk of file data.</P></UL><P>The 16 byte spare area contains:</P><UL> <LI><P>8 bytes of tags,</P> <LI><P>6 bytes of ECC data</P> <LI><P>1 byte block status (used to identify damaged blocks)</P> <LI><P>1 byte data status (currently unused).</P></UL><P>The tags are made up as follows:</P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>typedefstruct</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned chunkId:20; //chunk number in file</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned serialNumber:2; //serial number for chunk</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned byteCount:10; //number of bytes of data used in thischunk</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned objectId:18; //the object id that this chunk belongsto. </FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned ecc:12; //ECC on tags</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> unsigned unusedStuff:2; //unused</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>}yaffs_Tags;</FONT></FONT></P><P STYLE="margin-bottom: 0cm"><BR></P><P>A chunkId of zero indicates that this chunk holds ayaffs_ObjectHeader. A non zero value indicates that this is a datachunk and the position of the chunk in the file (ie. the first chunk- at offset 0 - has chunkId 1). See yaffs_guts.c:yaffs_Scan () to seehow this is done.</P><P>When a chunk is repalced (eg. file details changed or a part of afile was overwritten), the new chunk is written before the old chunkis deleted. This means that we don't lose data if there is a powerloss after the new chunk is created but before the old one isdiscarded, but it does mean that we can encounter the situation wherewe find both the old and the new chunks in flash. The serialNumber isincremented each time the chunk is written. 2 bits is sufficient toresolve any ambiguity.</P><P>bytecount applies only to data chunks and tells how many of thedata bytes are valid.</P><P>objectId says which object this chunk belongs to.</P><P>ecc is used to perform error correction on the tags. Another eccfield is used to error correct the data.</P><P><BR><BR></P><H3>yaffs_ObjectHeader</H3><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>typedefstruct</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P><P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2> yaffs_ObjectType⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -