Documentation/yaffs_report20020211.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="20020211;20201700">
   9         <META NAME="CHANGEDBY" CONTENT=" ">
  10         <META NAME="CHANGED" CONTENT="20020211;21005100">
  11 </HEAD>
  12 <BODY>
  13 <H3>YAFFS Progress 11 Feb 2002</H3>
  14 <H3>Approach</H3>
  15 <P><I>C. A. R. Hoare, in his 1980 ACM Turing Award lecture, told of
  16 two ways of constructing a software design: &quot;One way is to make
  17 it so simple that there are obviously no deficiencies and the other
  18 way is to make it so complicated that there are no obvious
  19 deficiencies.&quot;</I></P>
  20 <P>The approach I'm taking with Yaffs is to design and make notes up
  21 front as much as possible. I find this helps make the coding/debug
  22 phase go way faster and more predictably.</P>
  23 <P>Although obviously the code ends up in the kernel, I'm abstracting
  24 out kernel services so that I develop/debug in user space using
  25 vanilla dev tools. I like to use Source Navigator because it has a
  26 nice xref capability though a few quirks too). Thus, yaffs code will
  27 be tested in application space wrapped in a test harness which calls
  28 the yaffs functions. and sits on top of a NAND emulation layer (just
  29 two big disk files).  I can then do things like force ecc failures
  30 etc at will to test recovery logic and check booting etc. This
  31 general approach has served me well in the past and I expect it will
  32 this time too.</P>
  33 <H3>Design</H3>
  34 <P>At this stage all the major design work is done. Basically there
  35 are 3 in RAM management &quot;objects&quot;:</P>
  36 <UL>
  37         <LI><P> inodes: An inode maps to the normal file system concept of
  38         an inode. It is thus either a file or a directory. <BR>A file type
  39         inode points to a tnode tree which is a layered tree that is used to
  40         quickly find the pages of data in NAND.<BR>A directory type inode
  41         has a list of children links (ie. the links in that directory).<BR>An
  42         inode knows which hard links are associated with it.<BR>inode
  43         look-up uses a hashing table.</P>
  44         <LI><P>links: Links are hard or soft links. All links have a parent
  45         inode (ie. the directory they're in). <BR>Hard links point to an
  46         inode.<BR>Soft links are just alias strings.<BR>Instead of storing
  47         the link name in RAM (big and wasteful and variable size), the
  48         location in NAND is stored instead and a u16 &quot;checksum&quot;
  49         value is stored in RAM to help in quickly scanning links [ie. say
  50         the checksum for &quot;freddies_file&quot; is 123 then when I go
  51         search for it I don't need to go look at every link in NAND (slow),
  52         just those that match checksum 123].
  53         </P>
  54         <LI><P>tnodes: Tnodes are a tiered tree system to rapidly get from
  55         inodes to their data pages in RAM.</P>
  56 </UL>
  57 <P>There is a need for speed in certain areas, such as rapidly
  58 locating inodes, links data pages during certain scenarios (eg.
  59 garbage collection). These have been identified and suitable  look-up
  60 structures are in place.</P>
  61 <P>All dynamic data structures are allocated from pools rather than
  62 one at a time. This is more efficient time-wise and simplifies
  63 clean-up.</P>
  64 <H3>Code</H3>
  65 <P>Much of the code for the management layers is already in place, as
  66 is some of the tag management code. Some of the code has already been
  67 tested.</P>
  68 <P>I have started with coding the management layer since this is the
  69 most critical part to get right. Every now and then I have coded up
  70 some other section to verify that what I have will work.</P>
  71 <H3>Time</H3>
  72 <P>So far I've logged 65 hours on yaffs (though it chews up
  73 significant null cycles too :-)). I believe this is comfortably
  74 within budget. I was not able to make much progress through Christmas
  75 and the week of January, but am able to give a lot more effort now.</P>
  76 <P><BR><BR>
  77 </P>
  78 <P><BR><BR>
  79 </P>
  80 </BODY>
  81 </HTML>