%%%%%%%%%%INCLUDE alephdefault.mgp %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% This default.mgp is "Xft2" oriented. %deffont "standard" xfont "serif" %deffont "thick" xfont "sans-serif" %deffont "typewriter" xfont "monospace" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% Default settings per each line numbers. %% %default 1 area 90 90, leftfill, size 2, fore "white", back "black", font "thick" %default 2 size 7, vgap 10, prefix " " %default 3 size 2, bar "gray70", vgap 10 %default 4 size 5, fore "white", vgap 30, prefix " ", font "standard" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %% %% Default settings that are applied to TAB-indented lines. %% %tab 1 size 5, vgap 40, prefix " ", icon box "green" 40 %tab 2 size 4, vgap 40, prefix " ", icon box "green" 30 %tab 3 size 3, vgap 40, prefix " ", icon delta3 "white" 20 %%%%%%%%%%INCLUDE-END alephdefault.mgp %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page %nodefault %size 7, font "standard", fore "white", center YAFFS A NAND-flash filesystem %size 4 Wookey Aleph One Ltd, Embedded Debian %font "typewriter" wookey@aleph1.co.uk %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Intro Who's who Project Genesis and history Flash primer - NOR vs NAND How it works (log structure, GC, ECC) Porting and Use Performance, and JFFS2 comparison Licencing YAFFS2 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Project Genesis TCL needed a reliable FS for NAND Considered Smartmedia compatibility Considered JFFS2 Better than FTL High RAM use Slow boot times %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page History Decided to create YAFFS - Dec 2001 Working on RAM emulation - March 2002 Working on real NAND (Linux) - May 2002 WinCE version - Aug 2002 ucLinux use - Sept 2002 Linux rootfs - Nov 2002 pSOS version - Feb 2003 Shipping commercially - Early 2003 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Flash primer - NOR vs NAND %image "EMBEDDIR/nornand.png" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Design approach %size 4 OS neutral and developed in user space %size 4 Developed on NAND emulator %size 4 Portable - OS interface, guts, hardware interface (diag) %size 4 Single threaded (don't need separate GC thread like NOR) %size 4 Journalling - Tags break down dependence on physical location %size 4 Avoid in-place re-writing - expensive due to erase size %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Architecture %image "EMBEDDIR/overview.eps" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Terminology Flash-defined Page - 512 byte flash page Block - Erasable set of pages (usually 32) YAFFS-defined Chunk - YAFFS tracking unit. ==page (for YAFFS1) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Filesystem Design %size 4 Each file has an id - equivalent to inode. id 0 indicates 'deleted' %size 4 File data stored in chunks, same size as flash pages (512 bytes) %size 4 Chunks numbered 1,2,3,4 etc - 0 is header. %size 4 Each flash page is marked with file id and chunk number %size 4 These tags are stored in the OOB - 64bits: including file id, chunk number, write serial number, tag ECC and bytes-in-page-used %size 4 On overwriting the relevant chunks are replaced by writing new pages with new data but same tags - the old page is marked 'discarded' %size 4 File headers (mode, uid, length etc) get a page of their own (chunk 0) %size 4 Pages also have a 2-bit serial number - incremented on write %size 3 Allows crash-recovery when two pages have same tags (because old page has not yet been marked 'discarded'). %size 4 Discarded blocks are garbage-collected. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Filesystem Limits YAFFS 2^18 files (>260,000) 2^20 max file size (512MB) 1GB max filesystem size YAFFS2 8GB max filesystem size %size 4 Devices, hardlinks, softlinks, pipes supported %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page OOB data 16 bytes. YAFFS/Smartmedia or JFFS2 ECC %image "EMBEDDIR/OOBtable.png" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Filesystem RAM Data Structures (1) Not fundamental - needed for speed 16-bit page address for each file 1-1 mapping on 32Mb NAND - block of 4 pages on 128Mb NAND - scan %font "thick" yaffs_Object %cont %font "standard" - file, dir, hardlink, softlink %font "thick" yaffs_ObjectHeader %cont %font "standard" - in OOB, corresponds to yaffs_object. Each Object has parent, siblings (linked list), children if directory %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Filesystem RAM Data Structures (2) %image "EMBEDDIR/tnode.eps" %font "thick" yaffs_Tnode %cont %font "standard" tree of 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. %size 4 data structures are allocated in groups to reduce allocation/freeing overhead %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Partitioning Internal - give start and end block MTD partitioning (partition appears as device) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Garbage Collection and threads When a block (1-4 pages) contains only discarded pages - collect it If only one valid page than can copy it to release block for collection Single threaded Gross locking, matches NAND Soft Background deletion - Delete/Resize large files can take up to 0.5s Incorporated with GC Spread over several writes %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page ECC NAND is unreliable - bad blocks, data errors Needs Error Correction Codes for reliable use ECC on Tags and data 22bits per 256 bytes, 1-bit correction CPU/RAM intensive Lots of options: Hardware or software YAFFS (slightly faster) or MTD JFFS2 or YAFFS/Smartmedia positioning (if using MTD) Make sure bootloader, OS and FS generation all match! Can be disabled - not recommended! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page OS portability Linux WinCE pSOS ThreadX DSP-BIOS Reliable FS on NAND flash (un-corruptible, ECC, wear leveling, bad blocks) Good for battery devices - (power fail) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Yaffs in Use Formatting a device/partition for Yaffs simpy consists of blanking it Creating a filesystem image needs to generate OOB data mkyaffsimage tool - generates images mkyaffs - makes partition, and can fill with fs image In Linux - kernel module YAFFS Direct - supply 7 functions %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Embedded system use - YAFFS Direct Interface (1) YDI replaces Linux VFS/WinCE FSD layer open, close, stat, read, write, rename, mount etc Caching of unaligned accesses Port needs 7 functions: Lock and Unlock (mutex) current time (for time stamping) NAND access (read, write, init, erase). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Embedded system use - YAFFS Direct Interface (1b) %image "EMBEDDIR/overview.eps-0" %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Embedded system use - YAFFS Direct Interface (1) YDI replaces Linux VFS/WinCE FSD layer open, close, stat, read, write, rename, mount etc Caching of unaligned accesses Port needs 7 functions: Lock and Unlock (mutex) current time (for time stamping) NAND access (read, write, init, erase). %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Embedded system use - YAFFS Direct Interface (2) No CSD - all filenames in full Case sensitive No UID/GIDS Flat 32-bit time Thread safe - one mutex Multiple devices - eg /ram /boot /flash %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Performance - Examples 200Mhz StrongARM, 100Mhz SDRAM, 2*64MB NAND (winCE) 1.5-200x comercial FAT-based FS Flat-out write speed (1MB writes). 1.2MB/s. YAFFS-to-YAFFS copy using the WinCE file explorer. 64kB chunks. 500kB/s. Copy 11MB file from host over USB ActiveSync. Approx 26 seconds - most of which is USB transfer time. Delete an 11MB file: 5 seconds. 24Mhz ARM720 prototype, 16bit 12MHz RAM bus, SW ECC. Read: 185Kb/s Write: 85Kb/s Write (no verify): 175Kb/s %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Performance - Caching Linux VFS has cache, WinCE and RTOS don't YAFFS internal cache 15x speed-up for short writes on WinCE Choose generic read/write (VFS) or direct read/write (MTD) Generic is cached (_usually_ reads much faster ~10x, writes 5% slower) Direct is more robust on power fail %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page JFFS2 and YAFFS comparison JFFS2 - 16 bytes per node (48 in JFFS) (4MB for 128MB) YAFFS - 2 bytes per page (512K for 128MB) 128MB NAND scan on boot - 25s Boot scan only reads OOB - 3s compressed uncompressed complex (especially GC) simple Linux, ecos Lots of OSes, easy to port boot: JFFS2 4s for 4MB(8MB), YAFFS:7s for 30MB (twice as fast) %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page Licensing GPL - patents, Good Thing (TM) Bootloader LGPL to allow incorporation YAFFS in proprietary OSes - WinCE4, pSOS Wider use Aleph One Licence - MySQL-style: 'If you don't want to play then you can pay' %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page YAFFS2 Specced Dec 2002 For new NAND chips. 2k pages no re-writing simultaneous page programming 16-bit bus on some parts Main difference is 'discarded' status tracking zero re-writes means can't use 'discarded' flag Instead track block allocation order (with sequence number) Delete by making chunks available for GC and move file to special 'unlinked' directory until all chunks in it are 'stale' GC gets more complex to keep 'sense of history' %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page YAFFS2 comparison with YAFFS1 write: 1-3x faster (1.5-4.5MB/s vs 1.5MB/s read: 1-2x faster (7.6-16.7MB/s vs. 7.6MB/s) delete: 4-34x faster (7.8-62.5MB/s vs. 1.8MB/s) Garbage collection: 2-7x faster (2.1-7.7 vs. 1.1MB/s) RAM footprint 25%-50% less Slowest figures are for 512b pages (like YAFFS1) Faster ones for 2K pages and 2K pages+16bit bus Development sponsorship would help a lot %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %page %nodefault %size 7, font "standard", fore "white", center YAFFS A NAND-flash filesystem Questions? %size 4 Wookey Aleph One Ltd, Embedded Debian, Balloon Project %font "typewriter" wookey@aleph1.co.uk %embed "tnode.eps.gz" M'XL(")KJ-$```W1N;V1E+F5P
]?T7GP6^3E5_/#;[G7-F#`
MR36R%TB`(#"THUFM?&=GA)E9VQ<+__?4J5-DCQ1)#X86AK>KV&05BRP63U6/
MOOJ7G]Y>_=O-X=WV*G[MYN]^>ON]$M-77_WE\&E_<[>__ >I$)5#2"L SR-,A@OQU^4Z=/C8F-<1_G#@#Z!OK=>W77TM2:/G7Z^`GC:]:N>7#_P;S\
M/'L'>P"P;6H;%1V5G9/MT,X!`+2TM<9-'#=SUDR/A1YW;MX9/FPX_*9^N?\F
MAF7*R\L!0%=?%P!\M_@>.W&,=+94200`@(@=G3L>.WYL^\[M49%1$>$1]>O5
MAXJ3U;)UR^/'C@?Z!5ZZ?.GH\:/&QL90T6G#L`S#,`*!X$#8@9-'3[9JWHIE
M_I\_E\,%@/Z#^L<>C0T.#(Z-C95()=>3K@=L"VC9O"4`='3H>#WINGU[>T2L
M6Z=NV)XPW^V^<4?BGCQYXKG$4TU-32:3S9D^IYU#.P!P[N!\Y]:=AC8->_7L
ME?$F`Q%W!>U25U/G)XUMLL1/3S]U-75P>`T6-'QQV+"PP(/'GRI$@L2KZ7
M7,N@%M#!C'\!Q1J*BST61QV*$I6($/'NO;O:6MK5SJN:FAHB3IOQ_W&"JN3D
MY#9LVK!\Y?)/?ONSD5VUL+!`Q,>/'_OO\@\_&)Z:FGK[SNV&C1M"E8&-\$/A
M*2DI9"U+"\M;UV_UZ-6#?+2RM2HH*-BV8QL`Z.OI^V[VG35C%@!H:VD?/WK\
M\9/'`*"NKAYW+.[FS9L`X.3DM';U6OCP`B`7:K<>W9+O)I,EMLULY\V?!P`]
MNO=`Q'8=VI'E'3IT>/?NG5,')P`8.G)H]KML/3T]`.C=NS.'$E]FCIE\I1+
MERZ12$#]5+^ZIT4BD?AN\Q4(!%K:6E]9K0B%0JJ24P^&H
M*JENW[:=P^'$Q<29F9K]Y2H%!0739DSSV^'GZ."HHJSRN4%.EF7%8O'V'=LY
MR%FW89V6KI:BHN*PH<,,#0P?/'D`53J1OE-)>4E98=G-ZS<7>BZ<-G5:.\=V
MJ]:LJCHJ2ZY5965EN^9VQ27%4%'=2\22<^?/*2HI.C@X-+)I5%!<`!5!XOZ#
M^Z&AH0`@0UE!88&5E=7^T/UO,]_"A\&U\E>D/$Y9LG2)IH;FX*V[1J4UI6
M*F6D3UM;N^H,=!Z/MVC.HED+9CU[
M^@P`I#)IVLLT4N`JDZDJJ0)`9E;FR)$CI5(IN??,SLZUOQ(I%HZ_:M"@H*
MFIJ:,IFLLLPI*2E-GS1]RJPI66^RJA5$%165R>,G3YDUY5WFNY\Q;YW\D*O7
MKP:%!9$EQ47%`"`O+\\3\B02"7QJF^_3*,AS^!R)^--IH++=K:IJV]2VJ*B(
M+&&`$96+$LXGJ*JI6C6R*BTK)0VE]\@D;,YG,Y3)9'4LZSBT<9@Z:ZI4)&59
M]AL>%V`81BJ36C6RLFEL,W/>3)1@U7S(J4E_EAX>$4Y:_>7EY6*)F(P-D!]U
M_^%]4;FH09T&\&'=P0`CEHI%$A'Y>.O.K;+R,@LS"_(Q,CI255FUOVM_`%!4
M5,S-S?WX<)D8F]34K[EYV^;Y"^;/GC?;M;
7OW1MV-PS?%CYF])@F85-T3'3@^L#JZFH6BR612'1U=2-W
M1+HZNPJ%0AZ/MVOWKOGSYO.X/*&HM8^
]N`A"QD`3@1.:E#]4)UZ,%6I5,0)\>&W#U/?I^AQ%X%J&BST8@``:KAL
MR%DW?H[].+V6I@Y#U(/2/.7D/X3]6-_1#<.0)J7@:%":E!)/$_0JPS"RZUF&
M8>AHN3PC,WT,:GUJSU,X!Y.D:9KV3J/"1,?AE;F:+V?V5;94+F%_S0=+GI63
MSY.V47N?VK--(=U%,/$T$;X>CMZ)FKN;VAYW*D:69R
M343"2/Y-_NM[7]=^WW-(T._[U5#]4)UZ,*7,*;=NW(I^$Z4SY4TI_E+,O,Q,
MW9MZ_.?'#,-4J]7&.7@*]N/J[P>R\/#;APS#B+=%HVJ8R6@D_3*-$.(XSLLI
M.NG>M*@10IF7F=7O5D/70N5?R\@!Z;[TV3]^]E7XJ\4GB^L_K:O?J9_RG]9=
ML_7?6YM_W0Q="WG"`(ZJK;8HKJ[]7MW[:W?]LN_EPL_UI.9]++_[4\(HPT
M+^C?;7Z:4NM2DDVSV5XKJGZH+O[G8O1V=.K!%-?/%?]6K$^A60N^_<`KE