1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
4 <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1">
6 <META NAME="GENERATOR" CONTENT="StarOffice/5.2 (Linux)">
7 <META NAME="AUTHOR" CONTENT=" ">
8 <META NAME="CREATED" CONTENT="20021004;15061000">
9 <META NAME="CHANGEDBY" CONTENT=" ">
10 <META NAME="CHANGED" CONTENT="20021126;13574600">
15 <P>The original motivation for YAFFS 2 was to add support for the new
16 NAND with 2kB pages instead of 512-byte pages and strictly sequential
19 <P>To achieve this, a new design is used which also realises the
20 following benefits:</P>
22 <LI><P>zero page rewrites, which means faster operation. (YAFFS1
23 uses a single rewrite in the spare area to delete a page).</P>
24 <LI><P>ability to exploit simultaneous page programming on some
26 <LI><P>improves performance relative to YAFFS1 speed(write:1.5x to
27 5x, delete: 4x, garbage collection: 2x)</P>
28 <LI><P>lower RAM footprint (approx. 25% to 50% of YAFFS1, depending
29 on chunk size used).</P>
30 <LI><P>Can support Toshiba/Sandisk MLC parts.</P>
31 <LI><P>Runtime selection between various chunk sizes.</P>
33 <P>Most of YAFFS and YAFFS2 code is common, therefore the code will
34 likely be kept common with YAFFS vs YAFFS2 being run-time selected.</P>
36 <P>The main philosophical difference between YAFFS and YAFFS2 is how
37 discarded status is tracked. Since we can't do any re-writing, we
38 can't use the "discarded" flags in YAFFS2.</P>
39 <P>Instead YAFFS2 uses two mechanisms to resolve data state.</P>
41 <LI><P>YAFFS2 chunks have more tag information, including a block
42 sequence Id. From that we can determine the chunk sequence Id since
43 the chunks are allocated sequentially in a block. Thus we always
44 know the patch order for all chunks in the system.</P>
45 <LI><P>The above helps us track stale -vs- fresh data, but does not
46 help determine when a file/object is deleted. Deletion is achieved
47 by moving the object to the "unlinked" directory. We also
48 keep track of the number of chunks (both stale and current) in the
49 system for each object. While this number indicates that there are
50 still chunks associated with this object we keep the deletion
51 record. When the last trace of the object has been really erased
52 from NAND, we can forget about the deletion record too.
54 <LI><P>Since there is no deletion, a resize (shrinking) of a file
55 will still have valid data chunks past the end of file on the NAND.
56 However, we write a new ObjectHeader at the time of the resize,
57 therefore this shows the shrunken file size.</P>
59 <P>This changes erasure slightly:</P>
61 <LI><P>During garbage collection we can't just look at chunk state
62 flags, instead we must read the tags of each chunk to determine
63 which object's chunk count we must decrement. This step must also be
64 performed when a block is erased (as part of deletion).</P>
66 <P>This makes erasure & garbage collection more expensive (by
67 adding reads), but remember that ion YAFFS2 we don't need to do page
68 deletions which are much more expensive operations. Thus, all-up
70 <H4>Tag structure</H4>
71 <P>Each chunk in YAFFS2 has the following information:</P>
72 <TABLE WIDTH=100% BORDER=1 CELLPADDING=4 CELLSPACING=3>
86 <P>Size for 1kb chunks</P>
89 <P>Size for 2kB chunks</P>
99 <P>Block state. non-0xFF for bad block</P>
113 <P>32-bit chunk Id</P>
127 <P>32-bit object Id</P>
141 <P>Number of data bytes in this chunk</P>
155 <P>sequence number for this block</P>
169 <P>ECC on tags area</P>
183 <P>ECC, 3 bytes/256 bytes of data</P>
201 <P ALIGN=LEFT><B>30 bytes</B></P>
204 <P><B>42 bytes</B></P>
211 <P>To get enough spare bytes for this tagging structure requires a
212 chunk-size of at least 1kB. YAFFS1 is still used for 512-byte chunk
214 <P>The blockSequence increments each time a block is allocated. (ie.
215 the first block allocated is block 1, and so on).</P>
217 <P>The only reason we need to keep track of data status on NAND is to
218 be able to recreate the file system state during scanning. Since we
219 no longer have chunk deletion status flags we use a slightly
220 different process for scanning a YAFFS2 system.</P>
221 <P>In effect, YAFFS2 recreates its state by "replaying the
222 tape". ie. it scans the chunks in their allocation order (block
223 sequence Id order) rather than in their order on the media. This
224 implies that at start up, the blocks must be read and their block
225 sequence determined.</P>
227 <P>These numbers are indicative of relative performance. These only
228 apply to the NAND data transfer and do not include other overheads.</P>
229 <P>As an example, read/write cycle times of 100nS are used (though
230 NAND can typically do 50nS), "seek time" of 10uS and
231 program time of 200uS. Mileage will vary.</P>
232 <P>NB x16 means using a 16-bit bus. Clearly this cuts down on data
233 transfer time relative to an 8-bit bus.</P>
234 <P>Times for 2kB read(units of 1uS).</P>
235 <TABLE WIDTH=937 BORDER=1 CELLPADDING=4 CELLSPACING=3>
250 <P>YAFFS2 (512b pages)</P>
253 <P>YAFFS2 (2kB pages)</P>
256 <P>YAFFS2(2kB pages, x16)</P>
262 <TD WIDTH=175 VALIGN=TOP>
266 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
267 <P ALIGN=RIGHT>40</P>
269 <TD WIDTH=177 VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
270 <P ALIGN=RIGHT>40</P>
272 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
273 <P ALIGN=RIGHT>10</P>
275 <TD WIDTH=173 VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
276 <P ALIGN=RIGHT>10</P>
280 <TD WIDTH=175 VALIGN=TOP>
283 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
284 <P ALIGN=RIGHT>220</P>
286 <TD WIDTH=177 VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
287 <P ALIGN=RIGHT>220</P>
289 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
290 <P ALIGN=RIGHT>220</P>
292 <TD WIDTH=173 VALIGN=BOTTOM SDVAL="110" SDNUM="5129;">
293 <P ALIGN=RIGHT>110</P>
297 <TD WIDTH=175 VALIGN=TOP>
300 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="260" SDNUM="5129;">
301 <P ALIGN=RIGHT>260</P>
303 <TD WIDTH=177 VALIGN=BOTTOM SDVAL="260" SDNUM="5129;">
304 <P ALIGN=RIGHT>260</P>
306 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="230" SDNUM="5129;">
307 <P ALIGN=RIGHT>230</P>
309 <TD WIDTH=173 VALIGN=BOTTOM SDVAL="120" SDNUM="5129;">
310 <P ALIGN=RIGHT>120</P>
314 <TD WIDTH=175 VALIGN=TOP>
317 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="7.6" SDNUM="5129;">
318 <P ALIGN=RIGHT>7.6</P>
320 <TD WIDTH=177 VALIGN=BOTTOM SDVAL="7.6" SDNUM="5129;">
321 <P ALIGN=RIGHT>7.6</P>
323 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="8.7" SDNUM="5129;">
324 <P ALIGN=RIGHT>8.7</P>
326 <TD WIDTH=173 VALIGN=BOTTOM SDVAL="16.7" SDNUM="5129;">
327 <P ALIGN=RIGHT>16.7</P>
331 <TD WIDTH=175 VALIGN=TOP>
332 <P>Relative speed</P>
334 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
337 <TD WIDTH=177 VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
340 <TD WIDTH=176 VALIGN=BOTTOM SDVAL="1.1" SDNUM="5129;">
341 <P ALIGN=RIGHT>1.1</P>
343 <TD WIDTH=173 VALIGN=BOTTOM SDVAL="2.2" SDNUM="5129;">
344 <P ALIGN=RIGHT>2.2</P>
351 <P>Times for 2kB writes(units of 1uS).</P>
352 <TABLE WIDTH=100% BORDER=1 CELLPADDING=4 CELLSPACING=3>
367 <P>YAFFS2 (512b pages)</P>
370 <P>YAFFS2 (2kB pages)</P>
373 <P>YAFFS2(2kB pages, x16)</P>
379 <TD WIDTH=20% VALIGN=TOP>
382 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
383 <P ALIGN=RIGHT>40</P>
385 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
386 <P ALIGN=RIGHT>40</P>
388 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
389 <P ALIGN=RIGHT>10</P>
391 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
392 <P ALIGN=RIGHT>10</P>
396 <TD WIDTH=20% VALIGN=TOP>
399 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="800" SDNUM="5129;">
400 <P ALIGN=RIGHT>800</P>
402 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="800" SDNUM="5129;">
403 <P ALIGN=RIGHT>800</P>
405 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="200" SDNUM="5129;">
406 <P ALIGN=RIGHT>200</P>
408 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="200" SDNUM="5129;">
409 <P ALIGN=RIGHT>200</P>
413 <TD WIDTH=20% VALIGN=TOP>
416 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
417 <P ALIGN=RIGHT>40</P>
419 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="40" SDNUM="5129;">
420 <P ALIGN=RIGHT>40</P>
422 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
423 <P ALIGN=RIGHT>10</P>
425 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="10" SDNUM="5129;">
426 <P ALIGN=RIGHT>10</P>
430 <TD WIDTH=20% VALIGN=TOP>
433 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
434 <P ALIGN=RIGHT>220</P>
436 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
437 <P ALIGN=RIGHT>220</P>
439 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="220" SDNUM="5129;">
440 <P ALIGN=RIGHT>220</P>
442 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="110" SDNUM="5129;">
443 <P ALIGN=RIGHT>110</P>
447 <TD WIDTH=20% VALIGN=TOP>
450 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1320" SDNUM="5129;">
451 <P ALIGN=RIGHT>1320</P>
453 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1320" SDNUM="5129;">
454 <P ALIGN=RIGHT>1320</P>
456 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="660" SDNUM="5129;">
457 <P ALIGN=RIGHT>660</P>
459 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="440" SDNUM="5129;">
460 <P ALIGN=RIGHT>440</P>
464 <TD WIDTH=20% VALIGN=TOP>
467 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1.5" SDNUM="5129;">
468 <P ALIGN=RIGHT>1.5</P>
470 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1.5" SDNUM="5129;">
471 <P ALIGN=RIGHT>1.5</P>
473 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="3" SDNUM="5129;">
476 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="4.5" SDNUM="5129;">
477 <P ALIGN=RIGHT>4.5</P>
481 <TD WIDTH=20% VALIGN=TOP>
482 <P>Relative speed</P>
484 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
487 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
490 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
493 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="3" SDNUM="5129;">
501 <P>Times for 1MB delete (units of 1uS).</P>
502 <TABLE WIDTH=100% BORDER=1 CELLPADDING=4 CELLSPACING=3>
517 <P>YAFFS2 (512b pages)</P>
520 <P>YAFFS2 (2kB pages)</P>
523 <P>YAFFS2(2kB pages, x16)</P>
529 <TD WIDTH=20% VALIGN=TOP>
532 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="20480" SDNUM="5129;">
533 <P ALIGN=RIGHT>20480</P>
535 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
538 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
541 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
546 <TD WIDTH=20% VALIGN=TOP>
549 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="409600" SDNUM="5129;">
550 <P ALIGN=RIGHT>409600</P>
552 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
555 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
558 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
563 <TD WIDTH=20% VALIGN=TOP>
566 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="128000" SDNUM="5129;">
567 <P ALIGN=RIGHT>128000</P>
569 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="128000" SDNUM="5129;">
570 <P ALIGN=RIGHT>128000</P>
572 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
573 <P ALIGN=RIGHT>16000</P>
575 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
576 <P ALIGN=RIGHT>16000</P>
580 <TD WIDTH=20% VALIGN=TOP>
583 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="558080" SDNUM="5129;">
584 <P ALIGN=RIGHT>558080</P>
586 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="128000" SDNUM="5129;">
587 <P ALIGN=RIGHT>128000</P>
589 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
590 <P ALIGN=RIGHT>16000</P>
592 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
593 <P ALIGN=RIGHT>16000</P>
597 <TD WIDTH=20% VALIGN=TOP>
600 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1.8" SDNUM="5129;">
601 <P ALIGN=RIGHT>1.8</P>
603 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="7.8" SDNUM="5129;">
604 <P ALIGN=RIGHT>7.8</P>
606 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="62.5" SDNUM="5129;">
607 <P ALIGN=RIGHT>62.5</P>
609 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="62.5" SDNUM="5129;">
610 <P ALIGN=RIGHT>62.5</P>
614 <TD WIDTH=20% VALIGN=TOP>
615 <P>Relative speed</P>
617 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
620 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="4" SDNUM="5129;">
623 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="34" SDNUM="5129;">
624 <P ALIGN=RIGHT>34</P>
626 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="34" SDNUM="5129;">
627 <P ALIGN=RIGHT>34</P>
634 <P>Times for 1MB of garbage collection at 50% dirty (units of 1uS).</P>
635 <TABLE WIDTH=100% BORDER=1 CELLPADDING=4 CELLSPACING=3>
650 <P>YAFFS2 (512b pages)</P>
653 <P>YAFFS2 (2kB pages)</P>
656 <P>YAFFS2(2kB pages, x16)</P>
662 <TD WIDTH=20% VALIGN=TOP>
665 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="558080" SDNUM="5129;">
666 <P ALIGN=RIGHT>558080</P>
668 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="128000" SDNUM="5129;">
669 <P ALIGN=RIGHT>128000</P>
671 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
672 <P ALIGN=RIGHT>16000</P>
674 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="16000" SDNUM="5129;">
675 <P ALIGN=RIGHT>16000</P>
679 <TD WIDTH=20% VALIGN=TOP>
682 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="337920" SDNUM="5129;">
683 <P ALIGN=RIGHT>337920</P>
685 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="337920" SDNUM="5129;">
686 <P ALIGN=RIGHT>337920</P>
688 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="168960" SDNUM="5129;">
689 <P ALIGN=RIGHT>168960</P>
691 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="112640" SDNUM="5129;">
692 <P ALIGN=RIGHT>112640</P>
696 <TD WIDTH=20% VALIGN=TOP>
699 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="896000" SDNUM="5129;">
700 <P ALIGN=RIGHT>896000</P>
702 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="465920" SDNUM="5129;">
703 <P ALIGN=RIGHT>465920</P>
705 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="184960" SDNUM="5129;">
706 <P ALIGN=RIGHT>184960</P>
708 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="128640" SDNUM="5129;">
709 <P ALIGN=RIGHT>128640</P>
713 <TD WIDTH=20% VALIGN=TOP>
716 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1.1" SDNUM="5129;">
717 <P ALIGN=RIGHT>1.1</P>
719 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="2.1" SDNUM="5129;">
720 <P ALIGN=RIGHT>2.1</P>
722 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="5.4" SDNUM="5129;">
723 <P ALIGN=RIGHT>5.4</P>
725 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="7.7" SDNUM="5129;">
726 <P ALIGN=RIGHT>7.7</P>
730 <TD WIDTH=20% VALIGN=TOP>
731 <P>Relative speed</P>
733 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
736 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="1.9" SDNUM="5129;">
737 <P ALIGN=RIGHT>1.9</P>
739 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="4.9" SDNUM="5129;">
740 <P ALIGN=RIGHT>4.9</P>
742 <TD WIDTH=20% VALIGN=BOTTOM SDVAL="7" SDNUM="5129;">
750 <P>$Id: yaffs2.html,v 1.1 2002-11-26 01:15:37 charles Exp $</P>