Documentation/yaffs-notes2.html

   1 <!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 3.2//EN">
   2 <HTML>
   3 <HEAD>
   4         <META HTTP-EQUIV="CONTENT-TYPE" CONTENT="text/html; charset=iso-8859-1">
   5         <TITLE></TITLE>
   6         <META NAME="GENERATOR" CONTENT="StarOffice/5.2 (Linux)">
   7         <META NAME="AUTHOR" CONTENT=" ">
   8         <META NAME="CREATED" CONTENT="20020429;14311100">
   9         <META NAME="CHANGEDBY" CONTENT=" ">
  10         <META NAME="CHANGED" CONTENT="20020513;21133100">
  11 </HEAD>
  12 <BODY>
  13 <H1 ALIGN=CENTER>YAFFS Development Notes</H1>
  14 <P><BR><BR>
  15 </P>
  16 <P><BR><BR>
  17 </P>
  18 <H3>Build options</H3>
  19 <P>Yaffs can be built as either a kernel module (ie. a Linux file
  20 system) or as an application.</P>
  21 <P>Of course the goal is to build yaffs as a file system running on
  22 top of real NAND flash, but yaffs can be built to run on a RAM
  23 emulation layer for in-kernel testing without NAND flash in the
  24 system.</P>
  25 <P>Building as an application allows the yaffs_guts algorithms to be
  26 tested/debugged in a more friendly debugging environment. The test
  27 harness is in yaffsdev.c</P>
  28 <H3>Trying it out</H3>
  29 <P>YAFFS can be built to run with either mtd or RAM emulation, or
  30 both. The file system that interfaces to mtd is called <B>yaffs</B>,
  31 the file system that uses internal ram is called <B>yaffsram</B>.
  32 YAFFS simultaneously supports both if they are enabled.</P>
  33 <OL>
  34         <LI><P>Hack the Makefile and change the KERNELDIR define to your
  35         kernel directory.</P>
  36         <LI><P>If you don't have mtd support in your kernel, then you might
  37         need to turn off USE_MTD otherwise the yaffs module might not load.</P>
  38         <LI><P>Type <B><FONT FACE="Courier, monospace">make clean; make</FONT></B>
  39         to build yaffs</P>
  40         <LI><P>Load yaffs as a module by typing <B><FONT FACE="Courier, monospace">/sbin/insmod
  41         yaffs.o</FONT></B> (ya gotta be root!).</P>
  42         <LI><P>Create a mount point eg. <B><FONT FACE="Courier, monospace">mkdir
  43         /mnt/y</FONT></B></P>
  44         <LI><P>To mount the RAM emulation version of yaffs,  <B><FONT FACE="Courier, monospace">mount
  45         -t yaffsram none /mnt/y</FONT></B></P>
  46         <LI><P><FONT FACE="Courier, monospace"><SPAN STYLE="font-weight: medium"><FONT FACE="Times, serif">Alternatively,
  47         to mount the mtd version of yaffs,</FONT></SPAN><B> mount -t yaffs
  48         /dev/mtd0 /mnt/y</B></FONT></P>
  49 </OL>
  50 <P><BR><BR>
  51 </P>
  52 <H3>YAFFS Data structures</H3>
  53 <P>All data types are defined in yaffs_guts.h</P>
  54 <P>Yaffs uses the following major objects:</P>
  55 <UL>
  56         <LI><P>yaffs_Object: A yaffs_Object can be a file, directory,
  57         symlink or hardlink. The yaffs_Objects &quot;know&quot; about their
  58         corresponding yaffs_ObjectHeader in NAND and the data for that
  59         object. yaffs_Objects also bind together the directory structure as
  60         follows:</P>
  61         <LI><P>parent: pointer to the yaffs_Object that is a parent of this
  62         yaffs_Object in the directory structure.</P>
  63         <LI><P>siblings: this field is used to link together a list of all
  64         the yaffs_Objects in the same directory.</P>
  65         <LI><P>children: if the object is a directory, then children holds
  66         the head of the list of objects in the directory.</P>
  67         <LI><P>yaffs_Tnode: yaffs_Tnodes form a tree structure that speeds
  68         up the search for data chunks in a file. As the file grows in size,
  69         the levels increase. The Tnodes are a constant size (32 bytes).
  70         Level 0 (ie the lowest level) comprise 16 2-byte entries giving an
  71         index used to search for the chunkId. Tnodes at other levels
  72         comprise 8 4-byte pointer entries to other tnodes lower in the tree.</P>
  73         <LI><P>yaffs_Device: this holds the device context and is in some
  74         ways analogous to the VFS superblock. It stores the data used to
  75         access the mtd as well as function pointers to access the NAND data.</P>
  76 </UL>
  77 <P>The Tnodes and Objects are allocated in groups to reduce memory
  78 allocation/freeing overheads. Freed up tnodes and objects are kept in
  79 a free list and re-used.</P>
  80 <H3>yaffs_Object</H3>
  81 <P><BR><BR>
  82 </P>
  83 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>struct
  84  yaffs_ObjectStruct</FONT></FONT></P>
  85 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P>
  86 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
  87 fake:1;             // A fake object has no presence on NAND.</FONT></FONT></P>
  88 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
  89 renameAllowed:1;           // Are we allowed to rename it?</FONT></FONT></P>
  90 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
  91 unlinkAllowed:1;           // Are we allowed to unlink it?</FONT></FONT></P>
  92 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
  93 dirty:1;                    // the object needs to be written to flash</FONT></FONT></P>
  94 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
  95 valid:1;                    // When the file system is being loaded up, this </FONT></FONT>
  96 </P>
  97 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
  98    // object might be created before the data</FONT></FONT></P>
  99 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 100    // is available (ie. file data records appear before the header).</FONT></FONT></P>
 101 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u8
 102 serial;             // serial number of chunk in NAND. Store here so we
 103 don't have to</FONT></FONT></P>
 104 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 105    // read back the old one to update.</FONT></FONT></P>
 106 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u16
 107 sum;                // sum of the name to speed searching</FONT></FONT></P>
 108 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 109 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   struct
 110 yaffs_DeviceStruct *myDev; // The device I'm on</FONT></FONT></P>
 111 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 112 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>                                                           </FONT></FONT></P>
 113 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   struct
 114 list_head hashLink;     // list of objects in this hash bucket</FONT></FONT></P>
 115 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>                                                   </FONT></FONT></P>
 116 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
 117 </P>
 118 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   struct
 119 list_head hardLinks; // all the equivalent hard linked objects</FONT></FONT></P>
 120 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>                           //
 121 live on this list</FONT></FONT></P>
 122 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 123 directory structure stuff</FONT></FONT></P>
 124 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   struct
 125 yaffs_ObjectStruct  *parent;    //my parent directory</FONT></FONT></P>
 126 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   struct
 127 list_head siblings;               // siblings in a directory</FONT></FONT></P>
 128 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 129 // also used for linking up the free list</FONT></FONT></P>
 130 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>           </FONT></FONT></P>
 131 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 132 Where's my data in NAND?</FONT></FONT></P>
 133 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   int
 134 chunkId;                // where it lives</FONT></FONT></P>
 135 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 136 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 137 objectId;               // the object id value</FONT></FONT></P>
 138 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 139 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 140 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 141 st_mode;        // protection</FONT></FONT></P>
 142 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 143 st_uid;         // user ID of owner</FONT></FONT></P>
 144 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 145 st_gid;         // group ID of owner </FONT></FONT>
 146 </P>
 147 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 148 st_atime;       // time of last access</FONT></FONT></P>
 149 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 150 st_mtime;       // time of last modification</FONT></FONT></P>
 151 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 152 st_ctime;       // time of last change</FONT></FONT></P>
 153 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
 154 </P>
 155 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 156 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   yaffs_ObjectType
 157 variantType;</FONT></FONT></P>
 158 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 159 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   yaffs_ObjectVariant
 160 variant;</FONT></FONT></P>
 161 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 162 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>};</FONT></FONT></P>
 163 <P><BR><BR>
 164 </P>
 165 <P>Obvious stuff skipped....</P>
 166 <P>fake, renameAllowed, unlinkAllowed are special flags for handling
 167 &quot;fake&quot; objects which live in the file system but do not
 168 live on NAND. Currently there are only two such objects: the root
 169 object and the lost+found directory. None of these may be renamed or
 170 unlinked.</P>
 171 <P>serial, sum: see yaffs_ObjectHeader.</P>
 172 <P>dirty indicates that the object's contents has changed and a new
 173 yaffs_ObjectHeader must be written to flash.</P>
 174 <P>valid indicates that the object has been loaded up. This is only
 175 used during scanning (yaffs_Scan()) since we can know of an object's
 176 existance - and thus need to create the object header - before we
 177 encounter the associated yaffs_ObjectHeader.</P>
 178 <P>hashlink is a list of Objects in the same hash bucket.
 179 </P>
 180 <P>The four variants hold extra info:</P>
 181 <P>Files hold the file size and the top level and pointer to the
 182 tnode tree for the file.</P>
 183 <P>Directories hold a list of children objects.</P>
 184 <P>Symlinks hold a pointer to the alias string. This is probably
 185 inefficient, but that probably does not matter since we don't expect
 186 to see many of these.
 187 </P>
 188 <P>Hardlinks hold information to identify the equivalent object.</P>
 189 <P><BR><BR>
 190 </P>
 191 <P><BR><BR>
 192 </P>
 193 <H3>File structure (tnodes)</H3>
 194 <P>File structures are done with a tiered indexing structure</P>
 195 <P><BR><BR>
 196 </P>
 197 <P><IMG SRC="sv9349341.gif" NAME="Graphic2" ALIGN=LEFT WIDTH=491 HEIGHT=294 BORDER=0><BR CLEAR=LEFT><BR><BR>
 198 </P>
 199 <P>The file structure is maintained by a tree structure. Depending
 200 where it is in the tree, each tree node (<B><I>tnode</I></B>) (the
 201 blue/things) holds either:</P>
 202 <UL>
 203         <LI><P>.... if it is at the lowest level, then 16 __u16s which
 204         identify the page.</P>
 205         <LI><P>.... if it is at a higher level (ie an internal tnode), then
 206         8 pointers to lowest-level tnodes.</P>
 207 </UL>
 208 <P>When the file starts out, it is assigned only one low-level tnode.
 209 When the file expands past what a single tnode can hold, then it is
 210 assigned a second tnode and an internal node is added to point to the
 211 two tnodes. As the file grows, more low-level tnodes and high level
 212 tnodes are added.</P>
 213 <P>Traversing the tnode tree to find a particular page in a file is
 214 quite simple: each internal tnode is selected from by using 3 bits of
 215 the page offset in the file. The level 0 page resolves 4 bits.</P>
 216 <P>For example, finding page 0x235 (ie. the one starting at file
 217 position 0x46800 would proceed as follows:</P>
 218 <P>0x235 is 0000001000110101, partitioned as follows.
 219 000.000.100.011.0101</P>
 220 <TABLE WIDTH=496 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 221         <COL WIDTH=140>
 222         <COL WIDTH=160>
 223         <COL WIDTH=158>
 224         <THEAD>
 225                 <TR VALIGN=TOP>
 226                         <TH WIDTH=140>
 227                                 <P>Level</P>
 228                         </TH>
 229                         <TH WIDTH=160>
 230                                 <P>Bits</P>
 231                         </TH>
 232                         <TH WIDTH=158>
 233                                 <P>Selected value</P>
 234                         </TH>
 235                 </TR>
 236         </THEAD>
 237         <TBODY>
 238                 <TR VALIGN=TOP>
 239                         <TD WIDTH=140>
 240                                 <P>3 or more if they exist</P>
 241                         </TD>
 242                         <TD WIDTH=160>
 243                                 <P>&gt;= 10</P>
 244                         </TD>
 245                         <TD WIDTH=158>
 246                                 <P>Zero</P>
 247                         </TD>
 248                 </TR>
 249                 <TR>
 250                         <TD WIDTH=140 VALIGN=BOTTOM SDVAL="2" SDNUM="5129;">
 251                                 <P ALIGN=RIGHT>2</P>
 252                         </TD>
 253                         <TD WIDTH=160 VALIGN=TOP>
 254                                 <P ALIGN=LEFT>9 to 7</P>
 255                         </TD>
 256                         <TD WIDTH=158 VALIGN=TOP>
 257                                 <P>100 binary = 4</P>
 258                         </TD>
 259                 </TR>
 260                 <TR>
 261                         <TD WIDTH=140 VALIGN=BOTTOM SDVAL="1" SDNUM="5129;">
 262                                 <P ALIGN=RIGHT>1</P>
 263                         </TD>
 264                         <TD WIDTH=160 VALIGN=TOP>
 265                                 <P ALIGN=LEFT>6 to 4</P>
 266                         </TD>
 267                         <TD WIDTH=158 VALIGN=TOP>
 268                                 <P>011 binary = 3</P>
 269                         </TD>
 270                 </TR>
 271                 <TR>
 272                         <TD WIDTH=140 VALIGN=BOTTOM SDVAL="0" SDNUM="5129;">
 273                                 <P ALIGN=RIGHT>0</P>
 274                         </TD>
 275                         <TD WIDTH=160 VALIGN=TOP>
 276                                 <P ALIGN=LEFT>3 to 0</P>
 277                         </TD>
 278                         <TD WIDTH=158 VALIGN=TOP>
 279                                 <P>0101 binary = 5</P>
 280                         </TD>
 281                 </TR>
 282         </TBODY>
 283 </TABLE>
 284 <P><BR><BR>
 285 </P>
 286 <P>Free tnodes are stored in a list. When the list is exhausted, more
 287 are allocated.</P>
 288 <P>Each tnode takes 32 bytes. Each file needs at least one level 0
 289 tnode. How many do we need? A full 16MB file system needs at least
 290 16MB/512/16 = 2000 level zero tnodes. More for internal tnodes. More
 291 for files smaller than optimal.</P>
 292 <P>The tree grows as required. When the file is resized to a smaller
 293 size then it is pruned.</P>
 294 <P><BR><BR>
 295 </P>
 296 <H3>NAND data</H3>
 297 <P>Data is stored on NAND in &quot;chunks&quot;. Currently each chunk
 298 is the same size as a NAND flash page (ie. 512 bytes + 16 byte
 299 spare). In the future we might decide to allow for different chunk
 300 sizes. Chunks can hold either:</P>
 301 <UL>
 302         <LI><P>A yaffs_ObjectHeader. This is the way a yaffs_Object gets
 303         stored on NAND.</P>
 304         <LI><P>A chunk of file data.</P>
 305 </UL>
 306 <P>The 16 byte spare area contains:</P>
 307 <UL>
 308         <LI><P>8 bytes of tags,</P>
 309         <LI><P>6 bytes of ECC data</P>
 310         <LI><P>1 byte block status (used to identify damaged blocks)</P>
 311         <LI><P>1 byte data status (currently unused).</P>
 312 </UL>
 313 <P>The tags are made up as follows:</P>
 314 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>typedef
 315 struct</FONT></FONT></P>
 316 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P>
 317 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 318    unsigned chunkId:20;     //chunk number in file</FONT></FONT></P>
 319 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 320    unsigned serialNumber:2; //serial number for chunk</FONT></FONT></P>
 321 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 322    unsigned byteCount:10;   //number of bytes of data used in this
 323 chunk</FONT></FONT></P>
 324 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 325    unsigned objectId:18;    //the object id that this chunk belongs
 326 to. </FONT></FONT>
 327 </P>
 328 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 329    unsigned ecc:12;         //ECC on tags</FONT></FONT></P>
 330 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 331    unsigned unusedStuff:2;  //unused</FONT></FONT></P>
 332 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>}
 333 yaffs_Tags;</FONT></FONT></P>
 334 <P STYLE="margin-bottom: 0cm"><BR>
 335 </P>
 336 <P>A chunkId of zero indicates that this chunk holds a
 337 yaffs_ObjectHeader. A non zero value indicates that this is a data
 338 chunk and  the position of the chunk in the file (ie. the first chunk
 339 - at offset 0 - has chunkId 1). See yaffs_guts.c:yaffs_Scan () to see
 340 how this is done.</P>
 341 <P>When a chunk is repalced (eg. file details changed or a part of a
 342 file was overwritten), the new chunk is written before the old chunk
 343 is deleted. This means that we don't lose data if there is a power
 344 loss after the new chunk is created but before the old one is
 345 discarded, but it does mean that we can encounter the situation where
 346 we find both the old and the new chunks in flash. The serialNumber is
 347 incremented each time the chunk is written. 2 bits is sufficient to
 348 resolve any ambiguity.</P>
 349 <P>bytecount applies only to data chunks and tells how many of the
 350 data bytes are valid.</P>
 351 <P>objectId says which object this chunk belongs to.</P>
 352 <P>ecc is used to perform error correction on the tags. Another ecc
 353 field is used to error correct the data.</P>
 354 <P><BR><BR>
 355 </P>
 356 <H3>yaffs_ObjectHeader</H3>
 357 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>typedef
 358 struct</FONT></FONT></P>
 359 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>{</FONT></FONT></P>
 360 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   yaffs_ObjectType
 361 type;</FONT></FONT></P>
 362 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
 363 </P>
 364 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 365 Apply to everything     </FONT></FONT></P>
 366 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   int
 367   parentObjectId;</FONT></FONT></P>
 368 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u16
 369 sum;    // checksum of name</FONT></FONT></P>
 370 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   char
 371  name[YAFFS_MAX_NAME_LENGTH + 1];</FONT></FONT></P>
 372 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
 373 </P>
 374 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 375 Thes following apply to directories, files, symlinks - not hard links</FONT></FONT></P>
 376 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 377 st_mode;  // protection</FONT></FONT></P>
 378 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 379 st_uid;   // user ID of owner</FONT></FONT></P>
 380 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 381 st_gid;    // group ID of owner </FONT></FONT>
 382 </P>
 383 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 384 st_atime; // time of last access</FONT></FONT></P>
 385 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 386 st_mtime; // time of last modification</FONT></FONT></P>
 387 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   __u32
 388 st_ctime; // time of last change</FONT></FONT></P>
 389 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 390 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 391 File size  applies to files only</FONT></FONT></P>
 392 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   int
 393 fileSize; </FONT></FONT>
 394 </P>
 395 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>           </FONT></FONT></P>
 396 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   //
 397 Equivalent object id applies to hard links only.</FONT></FONT></P>
 398 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   int
 399  equivalentObjectId;</FONT></FONT></P>
 400 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>
 401         // alias only applies to symlinks</FONT></FONT></P>
 402 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   char
 403 alias[YAFFS_MAX_ALIAS_LENGTH + 1];</FONT></FONT></P>
 404 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 405 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>   </FONT></FONT></P>
 406 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><FONT FACE="Courier, monospace"><FONT SIZE=2>}
 407 yaffs_ObjectHeader;</FONT></FONT></P>
 408 <P STYLE="margin-left: 2cm; margin-bottom: 0cm"><BR>
 409 </P>
 410 <P>A yaffs_ObjectHeader is stored in NAND for every yaffs_Object.</P>
 411 <P>type holds the type of yaffs_Object (file,directory,hardlink or
 412 symlink).</P>
 413 <P>parentObject is the objectId of this object's parent. name holds
 414 the object's name. Together these form the directory structure of the
 415 file system. Also worth mention is sum. This is a &quot;checksum&quot;
 416 on the name which speeds directory searching (ie. when searching the
 417 directory we only compare the name for those entries where sum
 418 matches).</P>
 419 <P>Obvious stuff skipped....</P>
 420 <P>equivalentObjectId is used by hardlinks. A hardlink to an object
 421 uses this field to specify the object that this links to. This way of
 422 doing things is a bit different than the normal Linux way of doing
 423 things (ie. keeping the links distinct from the inode) but is simpler
 424 and uses less space except for a few corner cases with hardlinks.</P>
 425 <P>alias is used by symlinks to hold the symlink alias string. This
 426 limits the size of the symlink alias. In future we should expand
 427 YAFFS to use data chunks to store aliases too long to fit into the
 428 yaffs_ObjectHeader.</P>
 429 <P><BR><BR>
 430 </P>
 431 <H3>NAND Interface</H3>
 432 <P>All NAND access is performed via four functions pointed to by
 433 yaffs_Device. At the moment a chunk is a page.</P>
 434 <UL>
 435         <LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
 436         WriteChunkToNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND,
 437         const __u8 *data, yaffs_Spare *spare)</FONT></FONT></P>
 438         <LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
 439         ReadChunkFromNAND(struct yaffs_DeviceStruct *dev,int chunkInNAND,
 440         __u8 *data, yaffs_Spare *spare);</FONT></FONT></P>
 441         <LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
 442         EraseBlockInNAND(struct yaffs_DeviceStruct *dev,int blockInNAND);</FONT></FONT></P>
 443         <LI><P><FONT FACE="Courier, monospace"><FONT SIZE=2>int
 444         InitialiseNAND(struct yaffs_DeviceStruct *dev);</FONT></FONT></P>
 445 </UL>
 446 <P>In the Readxxx and Writexxx functions, the data and/or spare
 447 pointers may be NULL in which case these data transfers are ignored.</P>
 448 <P>A quick note about NAND:</P>
 449 <UL>
 450         <LI><P>NAND is not random access, but page oriented. Thus, we do all
 451         reads &amp; writes in pages.</P>
 452         <LI><P>Each NAND page holds 512 bytes of data and 16 &quot;spare&quot;
 453         bytes. Yaffs structures the spare area with tags used to identify
 454         what is stored in the data area. There are 32 such pages to a block.</P>
 455         <LI><P>NAND writes will only change 1 bits to 0. eg. if a byte holds
 456         10110011 and you write 11011010 to it you will get the logical and
 457         of the two values: 10010010. The only way to get 1s again is to
 458         erase the entire block.
 459         </P>
 460         <LI><P>You may only write to a page a few times before erasing the
 461         entire block. Yaffs lives within these limitations. Each page only
 462         gets written to twice (once when written and once when discarded).</P>
 463         <LI><P>ECC is normally used with NAND to correct for single bit
 464         errors. YAFFS applies the ECC itself, so the MTD should not do this.</P>
 465         <LI><P>The current mtd interfaces are not particularly well suited
 466         to YAFFS and we will address the issue with the mtd group. (The mtd
 467         interface does not support page-oriented read/write which YAFFS
 468         would prefer).</P>
 469 </UL>
 470 <P><BR><BR>
 471 </P>
 472 <H3>mkyaffs</H3>
 473 <P>mkyaffs is the tool to format a NAND mtd to be used for YAFFS.
 474 This is quite simple, just erase all the undamaged blocks. YAFFS
 475 treats erased blocks as free (empty) space.</P>
 476 <P><BR><BR>
 477 </P>
 478 <H2>Expected performance</H2>
 479 <P>The following numbers should give an indication of the performance
 480 we should expect from YAFFS.</P>
 481 <P>As an example, I'll use the following numbers. Since the hardware
 482 is capable of 50ns read/write, these numbers allow for some other
 483 ovberheads. Clearly though, the performance can be degraded in
 484 various ways.</P>
 485 <TABLE WIDTH=233 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 486         <COL WIDTH=103>
 487         <COL WIDTH=103>
 488         <THEAD>
 489                 <TR VALIGN=TOP>
 490                         <TH WIDTH=103>
 491                                 <P ALIGN=LEFT STYLE="font-style: normal">Seek</P>
 492                         </TH>
 493                         <TH WIDTH=103>
 494                                 <P ALIGN=LEFT STYLE="font-style: normal">10uS/page</P>
 495                         </TH>
 496                 </TR>
 497         </THEAD>
 498         <TBODY>
 499                 <TR VALIGN=TOP>
 500                         <TD WIDTH=103>
 501                                 <P ALIGN=LEFT STYLE="font-style: normal">Read</P>
 502                         </TD>
 503                         <TD WIDTH=103>
 504                                 <P ALIGN=LEFT STYLE="font-style: normal">100nS/byte</P>
 505                         </TD>
 506                 </TR>
 507                 <TR VALIGN=TOP>
 508                         <TD WIDTH=103>
 509                                 <P ALIGN=LEFT STYLE="font-style: normal">Write</P>
 510                         </TD>
 511                         <TD WIDTH=103>
 512                                 <P ALIGN=LEFT STYLE="font-style: normal">100nS/byte</P>
 513                         </TD>
 514                 </TR>
 515                 <TR VALIGN=TOP>
 516                         <TD WIDTH=103>
 517                                 <P ALIGN=LEFT STYLE="font-style: normal">Program</P>
 518                         </TD>
 519                         <TD WIDTH=103>
 520                                 <P ALIGN=LEFT STYLE="font-style: normal">200uS/page</P>
 521                         </TD>
 522                 </TR>
 523                 <TR VALIGN=TOP>
 524                         <TD WIDTH=103>
 525                                 <P ALIGN=LEFT STYLE="font-style: normal">Erase</P>
 526                         </TD>
 527                         <TD WIDTH=103>
 528                                 <P ALIGN=LEFT STYLE="font-style: normal">2mS/block</P>
 529                         </TD>
 530                 </TR>
 531         </TBODY>
 532 </TABLE>
 533 <P><BR><BR>
 534 </P>
 535 <P>From this we can derive some higher-level numbers:</P>
 536 <TABLE WIDTH=706 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 537         <COL WIDTH=204>
 538         <COL WIDTH=160>
 539         <COL WIDTH=304>
 540         <THEAD>
 541                 <TR VALIGN=TOP>
 542                         <TH WIDTH=204>
 543                                 <P>Operation</P>
 544                         </TH>
 545                         <TH WIDTH=160>
 546                                 <P>Time</P>
 547                         </TH>
 548                         <TH WIDTH=304>
 549                                 <P>Calculation</P>
 550                         </TH>
 551                 </TR>
 552         </THEAD>
 553         <TBODY>
 554                 <TR VALIGN=TOP>
 555                         <TD WIDTH=204>
 556                                 <P>Read spare</P>
 557                         </TD>
 558                         <TD WIDTH=160>
 559                                 <P>12uS</P>
 560                         </TD>
 561                         <TD WIDTH=304>
 562                                 <P>seek + 16 * read</P>
 563                         </TD>
 564                 </TR>
 565                 <TR VALIGN=TOP>
 566                         <TD WIDTH=204>
 567                                 <P>Read page</P>
 568                         </TD>
 569                         <TD WIDTH=160>
 570                                 <P>63 uS</P>
 571                         </TD>
 572                         <TD WIDTH=304>
 573                                 <P>seek + 528 * read</P>
 574                         </TD>
 575                 </TR>
 576                 <TR VALIGN=TOP>
 577                         <TD WIDTH=204>
 578                                 <P>Write page</P>
 579                         </TD>
 580                         <TD WIDTH=160>
 581                                 <P>326 uS</P>
 582                         </TD>
 583                         <TD WIDTH=304>
 584                                 <P>seek + 528 * write + program + read page (for verification)</P>
 585                         </TD>
 586                 </TR>
 587                 <TR VALIGN=TOP>
 588                         <TD WIDTH=204>
 589                                 <P>Discard page</P>
 590                         </TD>
 591                         <TD WIDTH=160>
 592                                 <P>212 uS</P>
 593                         </TD>
 594                         <TD WIDTH=304>
 595                                 <P>seek + 16 * write + program</P>
 596                         </TD>
 597                 </TR>
 598                 <TR VALIGN=TOP>
 599                         <TD WIDTH=204>
 600                                 <P>Overwrite page</P>
 601                         </TD>
 602                         <TD WIDTH=160>
 603                                 <P>538 uS</P>
 604                         </TD>
 605                         <TD WIDTH=304>
 606                                 <P>write page + discard page</P>
 607                         </TD>
 608                 </TR>
 609                 <TR VALIGN=TOP>
 610                         <TD WIDTH=204>
 611                                 <P>Erase overhead per page</P>
 612                         </TD>
 613                         <TD WIDTH=160>
 614                                 <P>63uS</P>
 615                         </TD>
 616                         <TD WIDTH=304>
 617                                 <P>erase/32</P>
 618                         </TD>
 619                 </TR>
 620         </TBODY>
 621 </TABLE>
 622 <P><BR><BR>
 623 </P>
 624 <P>From this we can infer the following flash access times:</P>
 625 <TABLE WIDTH=704 BORDER=1 CELLPADDING=4 CELLSPACING=3>
 626         <COL WIDTH=196>
 627         <COL WIDTH=167>
 628         <COL WIDTH=303>
 629         <THEAD>
 630                 <TR VALIGN=TOP>
 631                         <TH WIDTH=196>
 632                                 <P>Operation</P>
 633                         </TH>
 634                         <TH WIDTH=167>
 635                                 <P>Time</P>
 636                         </TH>
 637                         <TH WIDTH=303>
 638                                 <P>Calculation</P>
 639                         </TH>
 640                 </TR>
 641         </THEAD>
 642         <TBODY>
 643                 <TR VALIGN=TOP>
 644                         <TD WIDTH=196>
 645                                 <P>Read 1MB file</P>
 646                         </TD>
 647                         <TD WIDTH=167>
 648                                 <P>0.13s (about 7.5 MB/s)</P>
 649                         </TD>
 650                         <TD WIDTH=303>
 651                                 <P>2000 * read page</P>
 652                         </TD>
 653                 </TR>
 654                 <TR VALIGN=TOP>
 655                         <TD WIDTH=196>
 656                                 <P>Write 1MB (clean system)</P>
 657                         </TD>
 658                         <TD WIDTH=167>
 659                                 <P>0.53s (about 1.8 MB/s)</P>
 660                         </TD>
 661                         <TD WIDTH=303>
 662                                 <P>2000 * write page</P>
 663                         </TD>
 664                 </TR>
 665                 <TR VALIGN=TOP>
 666                         <TD WIDTH=196>
 667                                 <P>Overwrite 1MB file (no gc)</P>
 668                         </TD>
 669                         <TD WIDTH=167>
 670                                 <P>1.08s (about 0.9MB/s)</P>
 671                         </TD>
 672                         <TD WIDTH=303>
 673                                 <P>2000 * overwrite page</P>
 674                         </TD>
 675                 </TR>
 676                 <TR VALIGN=TOP>
 677                         <TD WIDTH=196>
 678                                 <P>Overwrite 1MB with 50% gc</P>
 679                         </TD>
 680                         <TD WIDTH=167>
 681                                 <P>2.4s (about 0.4 MB/s)</P>
 682                         </TD>
 683                         <TD WIDTH=303>
 684                                 <P>2000 * overwrite page + 2000 * page copy (== overwrite page) +
 685                                 4000 * erase overhead</P>
 686                         </TD>
 687                 </TR>
 688                 <TR VALIGN=TOP>
 689                         <TD WIDTH=196>
 690                                 <P>Delete 1MB file</P>
 691                         </TD>
 692                         <TD WIDTH=167>
 693                                 <P>0.43s (about 2.2 MB/s)</P>
 694                         </TD>
 695                         <TD WIDTH=303>
 696                                 <P>2000 * discard page</P>
 697                         </TD>
 698                 </TR>
 699                 <TR VALIGN=TOP>
 700                         <TD WIDTH=196>
 701                                 <P>Delete 1MB file with 50% gc</P>
 702                         </TD>
 703                         <TD WIDTH=167>
 704                                 <P>0.49s (about 2.0MB/s)</P>
 705                         </TD>
 706                         <TD WIDTH=303>
 707                                 <P>2000 * discard page + 1000 * erase overhead</P>
 708                         </TD>
 709                 </TR>
 710         </TBODY>
 711 </TABLE>
 712 <P><BR><BR>
 713 </P>
 714 <P><BR><BR>
 715 </P>
 716 <P><BR><BR>
 717 </P>
 718 </BODY>
 719 </HTML>