O:23:"Drupal\node\Entity\Node":25:{s:10:"in_preview";N;s:9:"*values";a:22:{s:3:"vid";a:1:{s:9:"x-default";s:3:"605";}s:8:"langcode";a:1:{s:9:"x-default";s:3:"und";}s:18:"revision_timestamp";a:1:{s:9:"x-default";s:10:"1496873154";}s:12:"revision_uid";a:1:{s:9:"x-default";s:1:"1";}s:12:"revision_log";a:1:{s:9:"x-default";N;}s:3:"nid";a:1:{s:9:"x-default";s:3:"420";}s:4:"type";a:1:{s:9:"x-default";s:5:"paper";}s:4:"uuid";a:1:{s:9:"x-default";s:36:"c3d49866-ddb0-41b9-9505-630fed1d93f4";}s:17:"isDefaultRevision";a:1:{s:9:"x-default";s:1:"1";}s:6:"status";a:1:{s:9:"x-default";s:1:"1";}s:5:"title";a:1:{s:9:"x-default";s:28:"YAFFS Robustness and Testing";}s:3:"uid";a:1:{s:9:"x-default";s:1:"6";}s:7:"created";a:1:{s:9:"x-default";s:10:"1339119318";}s:7:"changed";a:1:{s:9:"x-default";s:10:"1496873154";}s:7:"promote";a:1:{s:9:"x-default";s:1:"1";}s:6:"sticky";a:1:{s:9:"x-default";s:1:"0";}s:29:"revision_translation_affected";a:1:{s:9:"x-default";s:1:"1";}s:16:"default_langcode";a:1:{s:9:"x-default";s:1:"1";}s:4:"body";a:1:{s:9:"x-default";a:1:{i:0;a:3:{s:5:"value";s:61826:"

	<p class="western">Many embedded systems need to store critical
	data, making reliable file systems an important part of modern
	embedded system design. That robustness is not achieved through
	chance. Robustness is only achieved through design and extensive
	testing to verify that the file system functions correctly and is
	resistant to power failure.</p>
	<p class="western">This document describes some of the important
	design criteria and design features used to achieve a robust design.</p>
	
<p class="western" style="page-break-before: always"><h1 class="western">1 Background</h1>
<p class="western">Cheaper CPUs and flash have driven up embedded
system functionality. These increased functions often require file
system storage.</p>
<p class="western">The original flash file storage mechanisms were
the use of a flash translation layer (FTL) – a driver model which
makes flash memory appear as a disk drive – in conjunction with a
disk-oriented file system such as FAT. This storage methodology has
various performance and robustness limitations, leading to the
development of file systems designed specifically for flash memory.
These are known as flash file systems.</p>
<p class="western">Flash memory has various limitations when compared
with a disk. For example, flash memory pages cannot be individually
re-written but instead the whole block must be  erased and rewritten
with the modified page. Typical FTL achieve this with various logical
to physical mapping schemes. Thus emulating disk-like behaviour on
flash memory adds an extra layer of software which slows down write
performance. Worse still, it adds extra state which is prone to
corruption due to power failure.</p>
<p class="western">A typical FTL-based solution will use a file
system such as FAT. FAT always stores tables in the same disk blocks
and must thus change the same blocks often. Since flash memory blocks
can endure a limited number of write/erasure cycles, the FTL must
move the physical location of the block around to prevent  the high
traffic blocks from wearing out. This requires wear levelling – a
further burden.</p>
<p class="western">Some systems try to mitigate against the
performance penalties by caching a lot of data to reduce writes.
While this can go some way towards reducing the apparent write time,
it does make the solution prone to data loss in the event of a power
failure.</p>
<p class="western">As well as limitations, flash memory also has
certain advantages when compared to rotating media. There is no spin
up time, making it more responsive. There is no read head so there is
no read penalty if data is fragmented. Flash file systems can be
designed to exploit these advantages.</p>
<p class="western">True flash file systems<a class="sdfootnoteanc" name="sdfootnote1anc" href="#sdfootnote1sym"><sup>1</sup></a>,
on the other hand, are a single code body designed to take the
features and limitations of flash into consideration. Flash file
systems can thus be far more “flash friendly”. Well designed
flash file systems will avoid using “flash unfriendly” techniques
such as allocation tables and in-place rewriting.</p>
<p class="western">Yaffs is a flash file system, originally designed
specifically for NAND flash though also used with great success on
NOR flash too. Yaffs development started in 2001 when 32Mbytes of
flash was considered large. Since then, Yaffs has been expanded to
work properly with different flash types and far larger memory arrays
(many GBytes).</p>
<p class="western">Yaffs was originally deployed in Linux, but was
written in an OS neutral way, mainly to facilitate modular
development and testing. This turned out to be useful when we had
requests to port Yaffs to other operating systems. Since then, Yaffs
has been used in many different products in a wide variety of
applications from consumer products such as cell phones and sewing
machines to aerospace, industrial and medical applications including
process control, building management, communications infrastructure
and many others.</p>
<p class="western">Yaffs is not tied to any endian ordering and has
been used on a wide variety of architectures including ARM, MIPS,
PowerPC, x86, some DSPs. Yaffs has been deployed using a wide variety
of compilers from many different vendors.</p>
<p class="western">Nor is Yaffs tied to any particular operating
system. Yaffs has been used with Linux, eCOS, Windows Embedded
Compact (previously Windows CE), VxWorks and others.</p>
<h1 class="western">2 Flash File System considerations</h1>
<p class="western">There are many criteria that are important when
selecting a flash file system. These are some that out customers have
found to be most important:</p>
<ul>
	<li/>
<p class="western">Robustness: It really is not worth having a
	file system that loses or corrupts data and prevents the system from
	working properly. Some flash file systems are only robust when
	synced (flushed) after files have been written. That requires extra
	code, slows the system and leaves the file system in a
	non-deterministic state until the sync has been completed. Some file
	systems need to perform disk repair operations (eg. check disk) in
	the event of a power failure. This can add considerable time to the
	start up, preventing the system from being operational.</p>
	<li/>
<p class="western">Performance: In many embedded system
	designs, slow read/write performance can delay tasks and cause
	system degradation or even failure. It is thus important that
	read/write performance be acceptable. Note that many flash file
	systems need to perform extra actions such as garbage collection. In
	some cases these actions can cause the file system to stall for a
	long time. It is thus important that these factors be taken into
	consideration. Performance can sometimes be improved by adding a
	write caching layer. These caching layers make the file system calls
	(write etc) proceed quickly, without actually writing the data to
	flash. This is a two-edged sword as data in the cache will be lost
	on a power failure and syncing the file system will take a long
	time. Thus, most flash file systems offer either speed or robustness
	– not both.</p>
	<li/>
<p class="western">Proven: It is very easy for a file system
	vendor to provide a list of claims saying “100% power safe” or
	similar, but what evidence do they have to back this up? All file
	systems, including flash file systems, are complex bodies of
	software with extremely complex state. They need very significant
	testing to prove that they work correctly.</p>
	<li/>
<p class="western">Portable: Software is a huge investment and
	it is increasingly important to be able to port the software between
	OSs and CPU architectures. Most flash file systems are limited to a
	single operating system which makes it difficult to migrate software
	between different platforms. In Yaffs' case portability extends to
	being able to seamlessly migrate the core Yaffs code into a test
	framework which enhances testing.</p>
</ul>
<h1 class="western">3 How Yaffs achieves robustness and performance</h1>
<p class="western">Yaffs was designed from the ground up specifically
to work well with NAND flash. The author had already developed
another flash file system, so was already familiar with the  design
challenges of flash.</p>
<p class="western">As Yaffs is not just adapting a disk-oriented file
system to work with flash it is not surprising that Yaffs is very
different in design to most other file systems. The key difference is
that Yaffs is a log-structured. file system<a class="sdfootnoteanc" name="sdfootnote2anc" href="#sdfootnote2sym"><sup>2</sup></a>.</p>
<p class="western">In essence, a log structured file system writes
file system changes as a sequential log.  The log structure is
particularly suitable for various reasons including:</p>
<ul>
	<li/>
<p class="western">All writes are at the end of the log. When
	a file is modified, there is no need to erase and rewrite a part of
	the flash. Changes are just appended to the log. Thus there is no
	need to erase and copy old data just to change some existing pages
	in a file. This tends to make writes much faster. There is no need
	to do a lot of caching to achieve performance. Data can be written
	to the log immediately meaning that sync time is very low. Data
	robustness is improved dramatically.</p>
	<li/>
<p class="western">There are no allocation tables or similar.
	This reduces the amount of data being written to the flash, and that
	there are no tables to corrupt.</p>
	<li/>
<p class="western">Since all writes are to the end of the log
	there are no “high traffic” blocks. This means Yaffs only needs
	a simpler wear leveling strategy.</p>
	<li/>
<p class="western">In the event of a power failure, the file
	system state is easily re-created from the log. This means there is
	no need to perform disk repair operations to correct for an unclean
	shutdown.</p>
</ul>
<p class="western">So why don't we see many log structured file
systems for disk file systems? The answer to this is that log file
systems tend to spread the writes around on the media. That is
typically very problematic for mechanical storage which must
physically move the read/write head from one location to another
making the access time very slow. Of course that does not apply for
flash memory. By designing specifically for flash, Yaffs can ignore
this issue and write fast.</p>
<p class="western">Many flash file systems need make a compromise
between robustness against performance. Thanks to the log structure,
Yaffs does not need to. Yaffs can provide high performance without
giving up on robustness.</p>
<p class="western">Those familiar with log structured file system
design will know that some log structured file systems have problems
with garbage collection<a class="sdfootnoteanc" name="sdfootnote3anc" href="#sdfootnote3sym"><sup>3</sup></a>.
Garbage collection is used to clean up the log and make more free
space available. Some log structured file system designs did not pay
enough attention to garbage collection and can stall for a
considerable time while garbage collection happens. Yaffs was
designed differently. The potential impact of garbage collection was
considered throughout the Yaffs design process. As a result, Yaffs
has a very simple garbage collection model that allows a lot of
flexibility in garbage collection scheduling. This prevents the
garbage collection from making the file system unresponsive.</p>
<p class="western">Most file systems are developed within the
context, and framework of, a single operating system. This typically
makes the code difficult to explore, debug and port. Yaffs on the
other hand was developed from the start inside a portable
development/testing framework. Yaffs is then ported to various
operating systems through the addition of glue code.</p>
<p class="western"><br/>
<br/>

</p>
<p class="western"><img src="data:image/png;base64,[encoded data, 38784 characters]" name="Object1" align="left" width="552" height="524"/>
<br/>
<br/>

</p>
<p class="western">There are many benefits to this approach:</p>
<ul>
	<li/>
<p class="western">A development framework runs in user space
	which provides a richer development environment than inside an OS
	kernel. It is much easier to attach debuggers and perform logging
	and create reproducible testing.</p>
	<li/>
<p class="western">The code is structured to be portable. That
	makes it relatively easy to port to a new OS or RTOS with a high
	level of confidence.</p>
	<li/>
<p class="western">There is a choice of porting interfaces
	allowing more flexibility to determine which porting method will be
	simpler. For example, the Linux wrapper accesses the Yaffs core
	directly while the Windows CE wrapper access the Yaffs Direct
	Interface<a class="sdfootnoteanc" name="sdfootnote4anc" href="#sdfootnote4sym"><sup>4</sup></a>.</p>
	<li/>
<p class="western">Each different environment provides
	different test tools. For example, Linux provides a raft of file
	system test tools that do different kinds of testing to the power
	fail test harness. Since the vast majority of the code is in the
	portable Yaffs core, that code gets the advantage of all test
	methods combined. The many millions of Android phone users that use
	Yaffs-based devices are helping test the core code that is also used
	on a wide variety of different operating systems and a wide range of
	different device types.</p>
	<li/>
<p class="western">Its Open Source status means any interested
	person can take a version from git and test it to make sure that it
	meets their needs.</p>
</ul>
<h1 class="western">4 Testing</h1>
<p class="western">It is all very well to design software to be
robust, but it needs thorough testing to build confidence in the
software and in the code authors and supplier.</p>
<p class="western">File systems have incredibly complex state so it
is not at all surprising that operating system designers find file
systems some of the most challenging code to test.</p>
<p class="western">There is no single test methodology that can test
all cases, and exhaustive state testing is impossible. The best we
can do is to have a suite of test methodologies that combine to
provide thorough testing.</p>
<p class="western">Approximately 60% of Yaffs development effort is
directed towards testing and improving the test environment. We are
constantly researching new methodologies.</p>
<p class="western">The following are descriptions of the most
important test strategies used in Yaffs.</p>
<h2 class="western">4.1 Power Fail Stress Testing</h2>
<p class="western">By far the most important consideration in Yaffs
testing is that it is robust to corruptions caused by power failure.
We want Yaffs to provide the basis for reliable products in typical
embedded system environments.</p>
<p class="western">The first power fail testing was done by companies
integrating Yaffs into their products. Some of these built test jigs
which would automatically interrupt power while running a real
hardware device. This approach is better than nothing, but has some
limitations:</p>
<ul>
	<li/>
<p class="western">It is relatively costly to set up. Flash
	has a limited lifetime meaning that test devices wear out with time
	and must be replaced.</p>
	<li/>
<p class="western">It is relatively slow since each cycle
	takes many seconds to boot, run the application for a while and then
	reboot.</p>
	<li/>
<p class="western">Many, and perhaps most, of the power
	interruptions will happen at times when the file system is inactive
	and thus be wasted cycles.</p>
</ul>
<p class="western">In 2008 we developed a simulated power-fail-test
environment. This simulates power failures using simulated flash
memory while running various consistency checks.</p>
<p class="western">The benefits of a software-based test harness are
numerous:</p>
<ul>
	<li/>
<p class="western">The test harness controls the point at
	which the simulated power failures happen. That means every test
	cycle counts.</p>
	<li/>
<p class="western">No special hardware is required.</p>
	<li/>
<p class="western">Test loops run faster. A quad-core computer
	can simulate ten to twenty power failures per second. That means
	about a million power failure simulations per day.</p>
</ul>
<p class="western">The effectiveness of the new software based
testing is dramatic.. A few times we have tested some user-suggested
changes that had passed a week or more of real-world power fail
testing only to have problems caught by the software simulation in a
matter of minutes.</p>
<p class="western">We regularly run the power fail simulation test
over a weekend, testing millions of power fail cycles.</p>
<h2 class="western">4.2 Testing the Yaffs Direct Interface API</h2>
<p class="western">Yaffs Direct Interface (YDI) is a POSIX-like
wrapper around the Yaffs core. This provides a set of function calls,
yaffs_open(), yaffs_write() and the like.</p>
<p class="western">Each function can return numerous error codes and
has to handle numerous different parameters.</p>
<p class="western">Although there were already significant tests for
the YDI, an extensive test harness was developed in 2010 to
comprehensively test each of the error paths and generate all of the
required errors.</p>
<p class="western">This provides a high level of confidence that the
test interfaces do what they should and that POSIX-like functionality
provides relatively clean porting of existing code.</p>
<h2 class="western">4.3 Linux Testing</h2>
<p class="western">The main purpose of the Linux testing is to test
the Linux wrapper code. It does, however, still exercise the Yaffs
core code differently to other testing and thus adds to the test
fabric.</p>
<p class="western">The Linux testing does not do power fail testing
but instead tests other aspects such as clean shutdowns, cache
integrity and write performance. This gives a useful way to assess
the effects of modifications.</p>
<p class="western">Linux testing is done on both real hardware and on
simulated hardware using the Linux mtd nand simulator.</p>
<p class="western">As with the Power Fail Stress Testing described
above, the simulated testing is done using a scrippted environment
which is typically run for a few days at a time.</p>
<h2 class="western">4.4 Fuzz Testing</h2>
<p class="western">Fuzz testing deliberately corrupts the flash image
and ensures that Yaffs still mounts. This is done to ensure that
Yaffs does not crash on corrupted data.</p>
<p class="western">Clearly fuzz testing can corrupt the contents of
individual files (that's its job), but the file system integrity
should not be compromised. 
</p>
<h2 class="western">4.5 Software checking</h2>
<p class="western">Although code checking is  not actual testing per
se, it does help to verify code changes.</p>
<p class="western">The Yaffs code has been checked with Coverity<a class="sdfootnoteanc" name="sdfootnote5anc" href="#sdfootnote5sym"><sup>5</sup></a>
– a market leader in code checking.</p>
<p class="western">We are investigating the use of KLEE and other
tools.</p>
<h2 class="western">4.6 Open Source Usage</h2>
<p class="western">Open Source usage of Yaffs opens it up to testing
by the many different projects. Many of these participate in some way
with the Yaffs mailing list, helping to uncover issues and generally
provide feedback.</p>
<p class="western">Each different project uses Yaffs in a different
way, meaning that a wider range of operation sequences are tested.</p>
<h2 class="western">4.7 Universities</h2>
<p class="western">Over its lifetime, Yaffs has been used as a
teaching framework for various university course in many different
counties around the world.</p>
<p class="western">For example, Oregon State and Utah State
Universities have used Yaffs as a test bench for their post-graduate
software testing courses. They essentially test the test tools by
injecting errors into the Yaffs code and seeing if these are
discovered by the test tools they are testing. Of course this has the
side effect of running these tests over the original Yaffs code too. 
</p>
<p class="western">Those interested in test methods are encouraged to
read some of the university papers in the references of this
document.</p>
<p class="western">We expect to adopt and extend some of the Oregon
State ideas and use these to extend our in-house test suite.</p>
<h1 class="western">5 Conclusions</h1>
<p class="western">Software development is an iterative process of
design and testing. Robust software solutions are only possible with
extensive testing.</p>
<p class="western">Embedded systems increasingly need to store data
in file systems as a critical part of their operation. It is thus
important to have a file system that is predictable and robust to
power failure and similar interruptions.</p>
<p class="western">Yaffs has been designed from scratch to be robust
to power failure and that robustness has been verified with a
multi-pronged test strategy that is continuously being improved.</p>
<h1 class="western" style="page-break-before: always">6References</h1>
<p class="western" align="left">Charles Manning, “How Yaffs
Works”.<br/>
<a href="http://users.actrix.co.nz/manningc/yaffs-docs/HowYaffsWorks.pdf">http://users.actrix.co.nz/manningc/yaffs-docs/HowYaffsWorks.pdf</a></p>
<p class="western" align="left"><br/>
<br/>

</p>
<p class="western" align="left">A. Groce et al, “Swarm Testing”
from Oregon State University, School of EE and Computer Science and
Utah State University, School of Computing,
2011.<br/>
<a href="http://www.ct.utah.edu/~regehr/papers/swarm12.pdf">http://</a><a href="http://www.ct.utah.edu/~regehr/papers/swarm12.pdf">www.ct.utah.edu/~regehr/papers/swarm12.pdf</a></p>
<p class="western" align="left"><br/>
<br/>

</p>
<p class="western" align="left"><em>Wu CH, “Efficient
Initialization and Crash Recovery</em> for. <em>Log</em>-<em>based
File Systems</em> over Flash Memory” from National Taiwan
University, Dept of Computer Science,<span style="font-style: normal">
2006.<br/>
http://</span><cite>www.cis.nctu.edu.tw/~lpchang/papers/SAC_wu_sac06.pdf</cite></p>
<p class="western" align="left" style="font-style: normal"><br/>
<br/>

</p>
<div id="sdfootnote1">
	<p class="sdfootnote-western"><a class="sdfootnotesym" name="sdfootnote1sym" href="#sdfootnote1anc">1</a>Note
	that flash translation layers (FTLs) are erroneously refered to as
	flash file systems. For example, despite the name, M-Systems TrueFFS
	is not a flash file system but a flash translation layer (FTL).</p>
</div>
<div id="sdfootnote2">
	<p class="sdfootnote-western"><a class="sdfootnotesym" name="sdfootnote2sym" href="#sdfootnote2anc">2</a>This
	document only provides a brief overview of the Yaffs architecture
	and design. The “How Yaffs Works” document provides an in-depth
	explanation of the Yaffs design and architecture.</p>
</div>
<div id="sdfootnote3">
	<p class="sdfootnote-western"><a class="sdfootnotesym" name="sdfootnote3sym" href="#sdfootnote3anc">3</a>Refer
	to the “How Yaffs Works” document to understand the need for
	garbage collection and how Yaffs does garbage collection.</p>
</div>
<div id="sdfootnote4">
	<p class="sdfootnote-western"><a class="sdfootnotesym" name="sdfootnote4sym" href="#sdfootnote4anc">4</a>For
	more information on Yaffs Direct Interface, please read the various
	documents on the subject.</p>
</div>
<div id="sdfootnote5">
	<p class="sdfootnote-western"><a class="sdfootnotesym" name="sdfootnote5sym" href="#sdfootnote5anc">5</a>http://www.coverity.com</p>
</div>
";s:7:"summary";s:241:"<p>This document describes some of the important design criteria and design features used to achieve a robust design suitable for modern embedded systems which need to store critical data.&nbsp; The test methodologies are also described.</p>";s:6:"format";s:8:"raw_html";}}}s:19:"field_document_type";a:1:{s:9:"x-default";a:1:{i:0;a:1:{s:9:"target_id";s:3:"345";}}}s:6:"upload";a:1:{s:9:"x-default";a:1:{i:0;a:3:{s:9:"target_id";s:2:"78";s:7:"display";s:1:"1";s:11:"description";s:0:"";}}}s:18:"field_teaser_image";a:1:{s:9:"x-default";a:1:{i:0;a:5:{s:9:"target_id";s:2:"79";s:3:"alt";s:40:"Preview of YaffsRobustnessAndTesting.pdf";s:5:"title";N;s:5:"width";N;s:6:"height";N;}}}}s:9:"*fields";a:0:{}s:19:"*fieldDefinitions";N;s:12:"*languages";N;s:14:"*langcodeKey";s:8:"langcode";s:21:"*defaultLangcodeKey";s:16:"default_langcode";s:17:"*activeLangcode";s:9:"x-default";s:18:"*defaultLangcode";s:3:"und";s:15:"*translations";a:1:{s:9:"x-default";a:1:{s:6:"status";i:1;}}s:24:"*translationInitialize";b:0;s:14:"*newRevision";b:0;s:20:"*isDefaultRevision";s:1:"1";s:13:"*entityKeys";a:4:{s:6:"bundle";s:5:"paper";s:2:"id";s:3:"420";s:8:"revision";s:3:"605";s:4:"uuid";s:36:"c3d49866-ddb0-41b9-9505-630fed1d93f4";}s:25:"*translatableEntityKeys";a:6:{s:5:"label";a:1:{s:9:"x-default";s:28:"YAFFS Robustness and Testing";}s:8:"langcode";a:1:{s:9:"x-default";s:3:"und";}s:6:"status";a:1:{s:9:"x-default";s:1:"1";}s:9:"published";a:1:{s:9:"x-default";s:1:"1";}s:3:"uid";a:1:{s:9:"x-default";s:1:"6";}s:16:"default_langcode";a:1:{s:9:"x-default";s:1:"1";}}s:12:"*validated";b:0;s:21:"*validationRequired";b:0;s:19:"*loadedRevisionId";s:3:"605";s:15:"*entityTypeId";s:4:"node";s:15:"*enforceIsNew";N;s:12:"*typedData";N;s:16:"*cacheContexts";a:0:{}s:12:"*cacheTags";a:0:{}s:14:"*cacheMaxAge";i:-1;s:14:"*_serviceIds";a:0:{}}