yaffs-0.3.html

YAFFS A NAND-flash filesystem

			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=96>
				<P ALIGN=LEFT>518..519</P>
			</TD>
			<TD WIDTH=249>
				<P>Block address</P>
			</TD>
			<TD WIDTH=291>
				<P>Tags</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=96>
				<P ALIGN=LEFT>520..522</P>
			</TD>
			<TD WIDTH=249>
				<P>ECC on second 256 bytes part of data</P>
			</TD>
			<TD WIDTH=291>
				<P>ECC on second 256 bytes of data</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=96>
				<P ALIGN=LEFT>523..524</P>
			</TD>
			<TD WIDTH=249>
				<P>Block address</P>
			</TD>
			<TD WIDTH=291>
				<P>Tags</P>
			</TD>
		</TR>
		<TR VALIGN=TOP>
			<TD WIDTH=96>
				<P ALIGN=LEFT>525..527</P>
			</TD>
			<TD WIDTH=249>
				<P>ECC on first 256 bytes part of data</P>
			</TD>
			<TD WIDTH=291>
				<P>ECC on first 256 bytes part of data</P>
			</TD>
		</TR>
	</TBODY>
</TABLE>
<P><BR><BR>
</P>
<P>The block status is a reserved value that shows whether the block
is damaged.</P>
<P>The data status tracks whether the page is valid. If less than 4
bits are zero, then the page is valid otherwise it is discarded.</P>
<P>There are 8 bytes (64 bits) for use by YAFFS tags. This is
partitioned as follows:</P>
<TABLE WIDTH=596 BORDER=1 CELLPADDING=4 CELLSPACING=3>
	<COL WIDTH=146>
	<COL WIDTH=423>
	<THEAD>
		<TR VALIGN=TOP>
			<TH WIDTH=146>
				<P>Number of bits</P>
			</TH>
			<TH WIDTH=423>
				<P>Usage</P>
			</TH>
		</TR>
	</THEAD>
	<TBODY>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="18" SDNUM="5129;">
				<P ALIGN=RIGHT>18</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P>18-bit file id. ie. Limit of 2<SUP>18</SUP> (over 260000)
				files. File id 0 is not valid and indicates a deleted page. File
				Id 0x3FFFF i is also not valid.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
				<P ALIGN=RIGHT>2</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P ALIGN=LEFT>2-bit serial number.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="20" SDNUM="5129;">
				<P ALIGN=RIGHT>20</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P>20-bit page id within file. Limit of 2<SUP>20</SUP> pages per
				file. ie. over 500MB file max size. Page id 0 means the file
				header for this file.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
				<P ALIGN=RIGHT>10</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P>10-bit counter of the number of bytes used in the page.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="12" SDNUM="5129;">
				<P ALIGN=RIGHT>12</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P>12-bit ECC on tags.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
				<P ALIGN=RIGHT>2</P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P>Unused. Keep as 1.</P>
			</TD>
		</TR>
		<TR>
			<TD WIDTH=146 VALIGN=BOTTOM SDVAL="64" SDNUM="5129;">
				<P ALIGN=RIGHT><B>64</B></P>
			</TD>
			<TD WIDTH=423 VALIGN=TOP>
				<P><B>Total</B></P>
			</TD>
		</TR>
	</TBODY>
</TABLE>
<P><BR><BR>
</P>
<P>A bit of explanation on the usage of some of these fields:</P>
<P>file Id is synonymous with inode.</P>
<P>The serial number is incremented each time a page with the same
file_id:page_id is rewritten (because of data changes or copy during
garbage collection). When a page is replaced, there is a brief period
during which there are two pages with the same id. The serial number
resolves this. Since there should never be a difference of less than
more than one, a two-bit counter is sufficient to determine which is
the current page.</P>
<P>When the page is rewritten, the file id, these data status byte
and the 12-bit ECC are all written to zero.</P>
<P>The byte counter indicates how many bytes are valid in this page.
Since the page would not exist if it contains zero bytes, this field
should thus hold 512 for all pages except the last page in the file.
The use of counters means that the file length integrity is preserved
while the file is open without having to constantly update the file
length in the file header. The file header only needs to be refreshed
when the file is closed (rather than whenever it is appended to).
This field is wide enough to allow expansion to 1024-byte &quot;chunks&quot;.</P>
<P>File &quot;headers&quot; come in two flavours:</P>
<UL>
	<LI><P>file info ( the mode, ower id, group id, length,...)</P>
	<LI><P>the hard link(s) that refers to the file.</P>
</UL>
<P>A directory also appears as a file (ie. has an inode and hard
link(s)) but has no data.</P>
<P>The 12-bit ECC applies to only the tag data uses a similar
algorithm to the 22-bit ECCs used for file system data. They are kept
independent.</P>
<H3>RAM data details</H3>
<P>Block management details are reasonably obvious and, I feel, don't
need to be addressed here apart from stating that there will be a
structure to track block status (eg. number of pages in use, failed
blocks, and which are candidates for garbage collection etc).</P>
<P>The files need an indexing structure of sorts to locate and track
the pages in the file. Some sort of tree structure should work rather
well. The look-up needs to be quite efficient in both CPU time and
space.</P>
<H3>Page allocation and garbage collection</H3>
<P>Pages are allocated sequentially from the currently selected
block. When all the pages in the block are filled, another clean
block is selected for allocation. At least two or three clean blocks
are reserved for garbage collection purposes. If there are
insufficient clean blocks available, then a dirty block ( ie one
containing only discarded pages) is erased to free it up as a clean
block. If no dirty blocks are available, then the dirtiest block is
selected for garbage collection.</P>
<P>Garbage collection is performed by copying the valid data pages
into new data pages thus rendering all the pages in this block dirty
and freeing it up for erasure. I also like the idea of selecting a
block at random some small percentage of the time - thus reducing the
chance of wear differences.</P>
<P>Relative to NOR, NAND writes and erases very fast. Therefore
garbage collection might be performed on-demand (eg. during a write)
without significant degradation in performance. Alternatively garbage
collection might be delegated to a kernel tasklet.</P>
<P>Relative to JFFSx, the garbage collection presented here is
incredibly simple - thanks mainly to the use of fixed-size pages
instead of journaling nodes.</P>
<H3>Flash writing</H3>
<P>As presented here, YAFFS only writes to the page's data area once
and to the spare area twice (once when new page is written and once when it
gets stomped on) before an erasure. This is within the limits of the most
restrictive NAND flashes.</P>

<H3>Wear leveling</H3>
<P>No wear leveling is explicitly used here. Instead we rely on two
&quot;strategies&quot;:</P>
<UL>
	<LI><P>Reserving some blocks to cater for failure. You need to do
	this anyway with NAND. The main purpose behind wear leveling is to
	prevent some blocks getting more wear and failing. Since we expect,
	and handle, failure this is no longer as important.</P>
	<LI><P>The infrequent random block selection should prevent low-wear
	blocks getting &quot;stuck&quot;.</P>
</UL>
<h3>Partitioning</h3>
<p> Partitioning is not included in this spec, but could be added if
required.</p>
<h3>Bootloading</h3>
<p>Bootloaders cannot just read files direct from NAND due to the high
probability of bad blocks. Because YAFFS is quite simple it will be
relatively straightforward for bootloaders to read from it (eg reading a
kernel).</p>

<H3>Conclusion</H3>
<P>YAFFS is very simple. It is also NAND-friendly, is relatively
frugal with resources (especially RAM) and boots quickly. Like JFFSx
it has journaling which makes it far more robust than FAT.</P>
<P>While it might seem high-risk to develop YAFFS, it is probably
about the same amount of effort as implementing changes to JFFS to
get it to work effectively within the constraints of NAND. A
resulting JFFSx system would still require significant amounts of RAM
and have long boot times.</P>
<P>While YAFFS is indeed a new file system internally, much of the
file system glue code (including inode management, link management
etc) can likely be stolen from JFFSx. 
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
<P><BR><BR>
</P>
</BODY>
</HTML>