mtd/Documentation/jffs3 JFFS3design.tex,1.3,1.4

Wed Jun 15 09:15:51 EDT 2005

Update of /home/cvs/mtd/Documentation/jffs3
In directory phoenix.infradead.org:/tmp/cvs-serv25341

Modified Files:
	JFFS3design.tex 
Log Message:
Slight update, add introductional section

Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/JFFS3design.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4

--- JFFS3design.tex	8 Jun 2005 13:53:51 -0000	1.3
+++ JFFS3design.tex	15 Jun 2005 13:15:47 -0000	1.4
@@ -24,14 +24,14 @@
 % A4 paper has 210mm x 297mm
 % TeX automatically makes 25.4mm left and top indents
 \oddsidemargin=0mm  % 25.4mm by default
-\textwidth=159.2mm  % 25.4mm right iindent
+\textwidth=159.2mm  % 25.4mm right indent
 \topmargin=0mm      % 25.4mm by default
 \textheight=241.6mm % 30mm bottom indent
 \headheight=0mm
 \headsep=0mm
 
 % Define TODO command
-\newcommand{\TODO}[1]{({\textbf{TODO}: #1})\marginpar{\large \textbf{!?!}}}
+\newcommand{\TODO}[1]{[{\textbf{TODO}: #1}]\marginpar{\large \textbf{?!}}}
 
 \begin{document}
 
@@ -131,10 +131,104 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %
+% JFFS3 design overview
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{JFFS3 design overview}
+This section overviews the main JFFS3 design aspects without any thorough
+description and is to be regarded an introduction to the design of JFFS3.
+
+Firstly, the utter difference between JFFS3 and JFFS2 designs must be noted.
+JFFS3 design is greatly impacted by the scalability issues and cannot be just an
+improvement over the design of JFFS2 (which is not scalable) -- some completely
+different principles must be applied to JFFS3.
+
+The following are the most essential things we want JFFS3 to meet:
+
+\begin{itemize}
+\item The JFFS3 memory consumption must not depend on the size of the JFFS3
+partition, the number of inodes in the file system, size of files and
+directories and the like. Of course, JFFS3 must be able to use the advantage
+of the available
+RAM, but only for different kinds of \emph{caches} which may be flushed back to
+flash any time in case of memory pressure.
+
+\item All the JFFS3 characteristics ought to vary not faster then $log(S)$,
+where $S$ is the size of
+JFFS3 partition. JFFS2-like linear dependencies are forbidden.
+
+\item The flash wear-levelling have to always be kept in mind and shouldn't
+suffer.
+
+\item The fact that flash devices may be not very reliable - bits may flip, bad
+blocks may appear, etc should be taken into account.
+
+\item It is oblicatory to make JFFS3 be very tolerant to unclean reboots,
+just like JFFS2.
+\end{itemize}
+
+To meet the above requirements, the following design decisions were made.
+
+\begin{itemize}
+\item JFFS3 is \emph{block-oriented}, much like traditional file systems for hard
+disk drives (on the contrary to JFFS2, which treats flash eraseblocks as contiguous
+space).
+
+\item JFFS3 orients to \emph{large-scale NAND flashes}. Other flash types may be
+supported too, but they should emulate NAND flash - e.g., JFFS3 assumes there is
+an OOB area on each NAND page (sector), etc.
+
+\item There has to exist a \emph{superblock} containing the sufficient amount of
+information to perform quick JFFS3 mount. As flash chips don't admit of
+rewriting of the same place several times without the erasure of the whole
+eraseblock and because of the the wear-levelling
+issues, some complex superblock management schemes are compulsory.
+
+\item Since the compression is very difficult to implement in the block-based
+approach, it was decided not to support it.
+
+\end{itemize}
+
+The way how JFFS2 is storing the filesystem data is similar to the
+approach of \emph{\mbox{ReiserFS}} file system [\ref{ref_Reiser4}].
+All the file system
+objects (inodes, file data blocks, directory entries, extended attributes, etc)
+are kept in one large $B^+$-tree. Effectively, the whole JFFS3 file system may be
+regarded as one large $B^+$-tree, excluding some superblock-related things,
+which don't belong to the tree. Please, refer to [\ref{ref_Reiser4}] if you are
+interested in the merits of such a tree-based approach.
+
+The tree consists of nodes, which may occupy either one sector or one block.
+All the objects stored in the tree are actually kept in the tree's leaf nodes,
+while non-leaf nodes contain only (\emph{key}, \emph{link}) pairs (see the
+definition of $B^+$-tree).
+
+Each file system object has an associated key which provides fast object search.
+Different objects has different keys, but keys may occasionally collide. In
+that case, all the colliding objects are kept together and JFFS3 selects the
+right one by means of the simple linear search.
+
+When files are created, changed or deleted, the corresponding leaf nodes of the
+tree are changed. When a node is changed, JFFS3 writes the node update to
+another place on flash, not to the same place where it was before. 
+To keep the tree consistent, the upper
+node, which points to the leaf, have to also be changed (the link update), and
+so forth up to the root node. I.e., the more levels the tree has,
+the more writes any single node update requires. The same story with Garbage
+Collector - if it moves any tree node, the whole path up to the root must be
+updated.
+
+With the tree-based approach, mount essentially means locating the root node
+of the tree. The root node is referred from the JFFS3 superblock. The superblock
+is found relatively quickly (see section \ref{ref_SectionSB}), so the file
+system mount is also fast.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
 % SUPERBLOCK MANAGEMENT
 %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Superblock management}
+\section{Superblock management} \label{ref_SectionSB}
 The superblock (SB) is the data structure which contains information about the
 whole JFFS3 file system and its layout. When the file system is being mounted,
 the superblock should be found and read.
@@ -412,9 +506,9 @@
 \begin{tabular}{lllllll}
 Flash type & Flash size & $N$ & $n$ & Sector read time & $S$ & SB find time\\
 \hline
-Toshiba TC58DVM92A1FT & 64MB & 32 & 2 & $\sim$50$\mu$s    & 22 & $\sim$1.1ms\\
-ST Micro NAND08G-B    & 1GB  & 64 & 2 & $\sim$130$\mu$s s & 25 & $\sim$3.3ms\\
-Samsung K9K1G08X0B    & 2GB  & 64 & 2 & $\sim$70$\mu$s  s & 25 & $\sim$1.6ms\\
+Toshiba TC58DVM92A1FT & 64MB & 32 & 2 & $\sim$50$\mu$s  & 22 & $\sim$1.1ms\\
+ST Micro NAND08G-B    & 1GB  & 64 & 2 & $\sim$130$\mu$s & 25 & $\sim$3.3ms\\
+Samsung K9K1G08X0B    & 2GB  & 64 & 2 & $\sim$70$\mu$s  & 25 & $\sim$1.6ms\\
 \end{tabular}
 \caption{The superblock search time for different NAND flashes} \label{ref_TableNANDTimes}
 \end{table}
@@ -468,6 +562,11 @@
 3-level scheme, the anchor eraseblock refers the SB eraseblock level 3, which
 refers the SB eraseblock level 2, which refers the SB eraseblock containing the
 superblock.
+
+\item \textbf{Node} -- the tree pile, i.e., the tree consists of nodes. The
+root of the tree is the \textbf{root node}, the leafs of the tree are
+\textbf{leaf nodes}. This terminology is equivalent to the terminology used in
+Reiser4 [\ref{ref_Reiser4}].
 \end{enumerate}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -528,6 +627,10 @@
 \item \raggedright \label{ref_SamsungNANDlist} 
 Samsung Flash memory products,\\
 \url{http://www.samsung.com/Products/Semiconductor/Flash/index.htm}
+
+\item \raggedright \label{ref_Reiser4},
+Reiser4 File System, \url{http://www.namesys.com/}
+
 \end{enumerate}
 
 \end{document}



