yaffs-notes2.html

YAFFS A NAND-flash filesystem

type;</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>	//
Apply to everything	</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	int
  parentObjectId;</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u16
sum;	// checksum of name</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	char
 name[YAFFS_MAX_NAME_LENGTH + 1];</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>	//
Thes following apply to directories, files, symlinks - not hard links</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_mode;  // protection</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_uid;   // user ID of owner</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_gid;    // group ID of owner </FONT></FONT>
</P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_atime; // time of last access</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_mtime; // time of last modification</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	__u32
st_ctime; // time of last change</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>	//
File size  applies to files only</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	int
fileSize; </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>	//
Equivalent object id applies to hard links only.</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	int
 equivalentObjectId;</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
        // alias only applies to symlinks</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>	char
alias[YAFFS_MAX_ALIAS_LENGTH + 1];</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>}
yaffs_ObjectHeader;</FONT></FONT></P>
<P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
</P>
<P>A yaffs_ObjectHeader is stored in NAND for every yaffs_Object.</P>
<P>type holds the type of yaffs_Object (file,directory,hardlink or
symlink).</P>
<P>parentObject is the objectId of this object's parent. name holds
the object's name. Together these form the directory structure of the
file system. Also worth mention is sum. This is a &quot;checksum&quot;
on the name which speeds directory searching (ie. when searching the
directory we only compare the name for those entries where sum
matches).</P>
<P>Obvious stuff skipped....</P>
<P>equivalentObjectId is used by hardlinks. A hardlink to an object
uses this field to specify the object that this links to. This way of
doing things is a bit different than the normal Linux way of doing
things (ie. keeping the links distinct from the inode) but is simpler
and uses less space except for a few corner cases with hardlinks.</P>
<P>alias is used by symlinks to hold the symlink alias string. This
limits the size of the symlink alias. In future we should expand
YAFFS to use data chunks to store aliases too long to fit into the
yaffs_ObjectHeader.</P>
<P><BR><BR>
</P>
<H3>NAND Interface</H3>
<P>All NAND access is performed via four functions pointed to by
yaffs_Device. At the moment a chunk is a page.</P>
<UL>
	<LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
	WriteChunkToNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND,
	const __u8 *data, yaffs_Spare *spare)</FONT></FONT></P>
	<LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
	ReadChunkFromNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND,
	__u8 *data, yaffs_Spare *spare);</FONT></FONT></P>
	<LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
	EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND);</FONT></FONT></P>
	<LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
	InitialiseNAND(struct yaffs_DeviceStruct *dev);</FONT></FONT></P>
</UL>
<P>In the Readxxx and Writexxx functions, the data and/or spare
pointers may be NULL in which case these data transfers are ignored.</P>
<P>A quick note about NAND:</P>
<UL>
	<LI><P>NAND is not random access, but page oriented. Thus, we do all
	reads &amp; writes in pages.</P>
	<LI><P>Each NAND page holds 512 bytes of data and 16 &quot;spare&quot;
	bytes. Yaffs structures the spare area with tags used to identify
	what is stored in the data area. There are 32 such pages to a block.</P>
	<LI><P>NAND writes will only change 1 bits to 0. eg. if a byte holds
	10110011 and you write 11011010 to it you will get the logical and
	of the two values: 10010010. The only way to get 1s again is to
	erase the entire block. 
	</P>
	<LI><P>You may only write to a page a few times before erasing the
	entire block. Yaffs lives within these limitations. Each page only
	gets written to twice (once when written and once when discarded).</P>
	<LI><P>ECC is normally used with NAND to correct for single bit
	errors. YAFFS applies the ECC itself, so the MTD should not do this.</P>
	<LI><P>The current mtd interfaces are not particularly well suited
	to YAFFS and we will address the issue with the mtd group. (The mtd
	interface does not support page-oriented read/write which YAFFS
	would prefer).</P>
</UL>
<P><BR><BR>
</P>
<H3>mkyaffs</H3>
<P>mkyaffs is the tool to format a NAND mtd to be used for YAFFS.
This is quite simple, just erase all the undamaged blocks. YAFFS
treats erased blocks as free (empty) space.</P>
<P><BR><BR>
</P>
<H2>Expected performance</H2>
<P>The following numbers should give an indication of the performance
we should expect from YAFFS.</P>
<P>As an example, I'll use the following numbers. Since the hardware
is capable of 50ns read/write, these numbers allow for some other
ovberheads. Clearly though, the performance can be degraded in
various ways.</P>
<TABLE WIDTH=233 BORDER=1 CELLPADDING=4 CELLSPACING=3>
	<COL WIDTH=103>
	<COL WIDTH=103>
	<THEAD>
		<TR VALIGN=TOP>
			<TH WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">Seek</P>
			</TH>
			<TH WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">10uS/page</P>
			</TH>
		</TR>
	</THEAD>
	<TBODY>
		<TR VALIGN=TOP>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">Read</P>
			</TD>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">100nS/byte</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">Write</P>
			</TD>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">100nS/byte</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">Program</P>
			</TD>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">200uS/page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">Erase</P>
			</TD>
			<TD WIDTH=103>
				<P ALIGN=LEFT STYLE="font-style: normal">2mS/block</P>
			</TD>
		</TR>
	</TBODY>
</TABLE>
<P><BR><BR>
</P>
<P>From this we can derive some higher-level numbers:</P>
<TABLE WIDTH=706 BORDER=1 CELLPADDING=4 CELLSPACING=3>
	<COL WIDTH=204>
	<COL WIDTH=160>
	<COL WIDTH=304>
	<THEAD>
		<TR VALIGN=TOP>
			<TH WIDTH=204>
				<P>Operation</P>
			</TH>
			<TH WIDTH=160>
				<P>Time</P>
			</TH>
			<TH WIDTH=304>
				<P>Calculation</P>
			</TH>
		</TR>
	</THEAD>
	<TBODY>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Read spare</P>
			</TD>
			<TD WIDTH=160>
				<P>12uS</P>
			</TD>
			<TD WIDTH=304>
				<P>seek + 16 * read</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Read page</P>
			</TD>
			<TD WIDTH=160>
				<P>63 uS</P>
			</TD>
			<TD WIDTH=304>
				<P>seek + 528 * read</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Write page</P>
			</TD>
			<TD WIDTH=160>
				<P>326 uS</P>
			</TD>
			<TD WIDTH=304>
				<P>seek + 528 * write + program + read page (for verification)</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Discard page</P>
			</TD>
			<TD WIDTH=160>
				<P>212 uS</P>
			</TD>
			<TD WIDTH=304>
				<P>seek + 16 * write + program</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Overwrite page</P>
			</TD>
			<TD WIDTH=160>
				<P>538 uS</P>
			</TD>
			<TD WIDTH=304>
				<P>write page + discard page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=204>
				<P>Erase overhead per page</P>
			</TD>
			<TD WIDTH=160>
				<P>63uS</P>
			</TD>
			<TD WIDTH=304>
				<P>erase/32</P>
			</TD>
		</TR>
	</TBODY>
</TABLE>
<P><BR><BR>
</P>
<P>From this we can infer the following flash access times:</P>
<TABLE WIDTH=704 BORDER=1 CELLPADDING=4 CELLSPACING=3>
	<COL WIDTH=196>
	<COL WIDTH=167>
	<COL WIDTH=303>
	<THEAD>
		<TR VALIGN=TOP>
			<TH WIDTH=196>
				<P>Operation</P>
			</TH>
			<TH WIDTH=167>
				<P>Time</P>
			</TH>
			<TH WIDTH=303>
				<P>Calculation</P>
			</TH>
		</TR>
	</THEAD>
	<TBODY>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Read 1MB file</P>
			</TD>
			<TD WIDTH=167>
				<P>0.13s (about 7.5 MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * read page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Write 1MB (clean system)</P>
			</TD>
			<TD WIDTH=167>
				<P>0.53s (about 1.8 MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * write page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Overwrite 1MB file (no gc)</P>
			</TD>
			<TD WIDTH=167>
				<P>1.08s (about 0.9MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * overwrite page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Overwrite 1MB with 50% gc</P>
			</TD>
			<TD WIDTH=167>
				<P>2.4s (about 0.4 MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * overwrite page + 2000 * page copy (== overwrite page) +
				4000 * erase overhead</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Delete 1MB file</P>
			</TD>
			<TD WIDTH=167>
				<P>0.43s (about 2.2 MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * discard page</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=196>
				<P>Delete 1MB file with 50% gc</P>
			</TD>
			<TD WIDTH=167>
				<P>0.49s (about 2.0MB/s)</P>
			</TD>
			<TD WIDTH=303>
				<P>2000 * discard page + 1000 * erase overhead</P>
			</TD>
		</TR>
	</TBODY>
</TABLE>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
</BODY>
</HTML>