# mtd/fs/jffs3 JFFS3design.tex,1.44,1.45

Sat Apr 23 11:07:13 EDT 2005

Update of /home/cvs/mtd/fs/jffs3

Modified Files:
JFFS3design.tex
Log Message:
Remove outdated info.

Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/fs/jffs3/JFFS3design.tex,v
retrieving revision 1.44
retrieving revision 1.45
diff -u -r1.44 -r1.45
--- JFFS3design.tex	23 Apr 2005 14:48:51 -0000	1.44
+++ JFFS3design.tex	23 Apr 2005 15:07:09 -0000	1.45
@@ -517,147 +517,6 @@

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
-% CHECKSUM
-%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Checksum}
-Any data (including actual file content and internal JFFS3 data) stored within
-JFFS3 file-system is protected by checksum. Nothing is stored on the flash media
-without checksum.
-
-Checksums are destined to detect errors caused by wearing, BB appearance
-or external factors (radiation, abnormal temperatures and the
-like). Errors fall into the following categories.
-
-\begin{itemize}
-\item \emph{Permanent} error is an error which stays after the corresponding block has
-been erased.
-
-\item \emph{Occasional} error is an error which becomes fixed after the corresponding
-block has been erased.
-\end{itemize}
-
-Different flash technologies imply different reliability. The following
-is a brief overview of Flash technologies in this perspective.
-
-\begin{itemize}
-\item \emph{NOR}
-flash is the most trustworthy type of flashes which doesn't admit of permanent
-errors. Any permanent error is critical and means that the chip is not workable anymore.
-Nevertheless, some kinds of NOR flash are not avoid of very rare bit flipping
-events and the use of checksum still might make sense here.
-
-\item \emph{DataFlash} is based on NOR technology and inherits its properties.
-[\ref{ref_AtmelDataFlash}].
-
-\item \emph{ECC NOR} may be regarded as not very robust NOR flash plus extra ECC
-protection.
-
-\item \emph{NAND} flash is not so reliable as NOR and it admits of permanent errors, let
-alone occasional ones which are also possible. The NAND technology itself
-implies bad blocks may dynamically appear during its utilization, albeit this is
-rather rare event [\ref{ref_NANDMTD}, \ref{ref_ToshibaNAND}].
-
-\item \emph{OneNAND} is based on NAND technology and has similar properties
-[\ref{ref_SamsungOneNAND}].
-
-\item \emph{AND} (\emph{AG-AND} and \emph{SuperAND}),
-like NAND technology, implies bad blocks either factory marked
-or dynamically found [\ref{ref_RenesasAND}].
-\end{itemize}
-
-%
-% Checksum modes
-%
-\subsection{Checksum modes}
-Because of a significant disparity in the reliability between different types of
-flashes JFFS3 might operate in either of the following modes.
-
-\begin{enumerate}
-\item \emph{Strict mode} -- checksums are always verified i.e. anything JFFS2
-reads from the flash is validated by checksum. This is safest operation mode and
-should probably always be enabled by default at least with NAND/AND flashes.
-
-\item \emph{Relaxed mode} -- data checksums are not ever being checked, i.e
-JFFS3 still checks node headers and other internal data but doesn't check actual
-file's content. This is dangerous working mode and may probably only be enabled
-by default when JFFS3 works on top of NOR flash.
-\end{enumerate}
-
-Both of the above mentioned operation modes imply that JFFS3 calculates and
-saves checksums when it is performing write operations.
-
-If the underlying flash makes use of ECC (e.g., NAND), and JFFS3 has been
-reported ECC error, JFFS3 checks the corresponding data that had been read.
-
-The checksum mode might be set on the per file basis with
-help of the corresponding extended attribute. In this case the extended
-attribute overrides the default mode. This is very handy mechanism
-whereby users might, for example, disable the checking of multimedia
-file's content.
-
-%
-% Checksum and unclean reboots
-%
-\subsection{Checksum and unclean reboots}
-Unlike JFFS2, JFFS3 does not utilize checksum to detect unclean reboots, albeit
-might do this. The primary aim of checksum is to prevent problems
-related to physical media corruptions. Unclean reboots are substantially
-detected by means of summary nodes. This property makes it possible to distinct
-between checksum errors caused by media problems and by unclean reboots.
-
-%
-% Checksum errors
-%
-\subsection{Checksum errors}
-If a checksum error has been found and if it has not been caused by
-an unclean reboot, JFFS3 behaves as follows.
-
-\begin{enumerate}
-\item Reports the fact of the checksum error.
-
-\item Takes an attempt to recover the erroneous node.
-Ignores the erroneous node (possibly, marking it obsolete) irrespective
-of the recovery procedure result (success or failure).
-
-\item Locks the inode to whom the erroneous node belongs. Namely,
-rejects any further access to the inode. This might be implementing by
-means of setting the relating extended attribute. JFFS3
-must not reject xattr operation whereby user might clean the
-attribute that locks the inode.
-
-\item Returns an error if the operation was being done on behalf of an
-user process (not Garbage Collector). Otherwise, let the GC to carry on.
-\end{enumerate}
-
-%
-% Checksum error recovery
-%
-\subsubsection{Checksum error recovery}
-The recovery procedure
-has not been designed so far and probably we may postpone this work as
-unimportant although it should be kept in mind during JFFS3
-implementation.
-
-Conceivably, JFFS3 might try to find an older obsolete node
-containing the corrupted information as well as to reconstruct the
-corrupted data using the corresponding in-memory data if it is present.
-The recovery is especially important in case of corrupted direntry node
-as if we just ignore it we might loose the whole file or directory with
-children.
-
-%
-% Miscellaneous
-%
-\subsection{Miscellaneous}
-Like JFFS2, JFFS3 makes use of CRC32 checksum algorithm with the start seed
-0xFFFFFFFF.
-
-If zlib library is used to compress node's data it is worth asking zlib not to
-generate redundant adler32 checksum for better performance.
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%
% VIRTUAL BLOCK HANDLING
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -835,6 +694,148 @@

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
+% CHECKSUM
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{Checksum}
+Any data (including actual file content and internal JFFS3 data) stored within
+JFFS3 file-system is protected by checksum. Nothing is stored on the flash media
+without checksum.
+
+Checksums are destined to detect errors caused by wearing, BB appearance
+or external factors (radiation, abnormal temperatures and the
+like). Errors fall into the following categories.
+
+\begin{itemize}
+\item \emph{Permanent} error is an error which stays after the corresponding block has
+been erased.
+
+\item \emph{Occasional} error is an error which becomes fixed after the corresponding
+block has been erased.
+\end{itemize}
+
+Different flash technologies imply different reliability. The following
+is a brief overview of Flash technologies in this perspective.
+
+\begin{itemize}
+\item \emph{NOR}
+flash is the most trustworthy type of flashes which doesn't admit of permanent
+errors. Any permanent error is critical and means that the chip is not workable anymore.
+Nevertheless, some kinds of NOR flash are not avoid of very rare bit flipping
+events and the use of checksum still might make sense here.
+
+\item \emph{DataFlash} is based on NOR technology and inherits its properties.
+[\ref{ref_AtmelDataFlash}].
+
+\item \emph{ECC NOR} may be regarded as not very robust NOR flash plus extra ECC
+protection.
+
+\item \emph{NAND} flash is not so reliable as NOR and it admits of permanent errors, let
+alone occasional ones which are also possible. The NAND technology itself
+implies bad blocks may dynamically appear during its utilization, albeit this is
+rather rare event [\ref{ref_NANDMTD}, \ref{ref_ToshibaNAND}].
+
+\item \emph{OneNAND} is based on NAND technology and has similar properties
+[\ref{ref_SamsungOneNAND}].
+
+\item \emph{AND} (\emph{AG-AND} and \emph{SuperAND}),
+like NAND technology, implies bad blocks either factory marked
+or dynamically found [\ref{ref_RenesasAND}].
+\end{itemize}
+
+%
+% Checksum modes
+%
+\subsection{Checksum modes}
+Because of a significant disparity in the reliability between different types of
+flashes JFFS3 might operate in either of the following modes.
+
+\begin{enumerate}
+\item \emph{Strict mode} -- checksums are always verified i.e. anything JFFS2
+reads from the flash is validated by checksum. This is safest operation mode and
+should probably always be enabled by default at least with NAND/AND flashes.
+
+\item \emph{Relaxed mode} -- data checksums are not ever being checked, i.e
+JFFS3 still checks node headers and other internal data but doesn't check actual
+file's content. This is dangerous working mode and may probably only be enabled
+by default when JFFS3 works on top of NOR flash.
+\end{enumerate}
+
+Both of the above mentioned operation modes imply that JFFS3 calculates and
+saves checksums when it is performing write operations.
+
+If the underlying flash makes use of ECC (e.g., NAND), and JFFS3 has been
+reported ECC error, JFFS3 checks the corresponding data that had been read.
+
+The checksum mode might be set on the per file basis with
+help of the corresponding extended attribute. In this case the extended
+attribute overrides the default mode. This is very handy mechanism
+whereby users might, for example, disable the checking of multimedia
+file's content.
+
+%
+% Checksum and unclean reboots
+%
+\subsection{Checksum and unclean reboots}
+Unlike JFFS2, JFFS3 does not utilize checksum to detect unclean reboots, albeit
+might do this. The primary aim of checksum is to prevent problems
+related to physical media corruptions. Unclean reboots are substantially
+detected by means of summary nodes. This property makes it possible to distinct
+between checksum errors caused by media problems and by unclean reboots.
+
+%
+% Checksum errors
+%
+\subsection{Checksum errors}
+If a checksum error has been found and if it has not been caused by
+an unclean reboot, JFFS3 behaves as follows.
+
+\begin{enumerate}
+\item Reports the fact of the checksum error.
+
+\item Takes an attempt to recover the erroneous node.
+Ignores the erroneous node (possibly, marking it obsolete) irrespective
+of the recovery procedure result (success or failure).
+
+\item Locks the inode to whom the erroneous node belongs. Namely,
+rejects any further access to the inode. This might be implementing by
+means of setting the relating extended attribute. JFFS3
+must not reject xattr operation whereby user might clean the
+attribute that locks the inode.
+
+\item Returns an error if the operation was being done on behalf of an
+user process (not Garbage Collector). Otherwise, let the GC to carry on.
+\end{enumerate}
+
+%
+% Checksum error recovery
+%
+\subsubsection{Checksum error recovery}
+The recovery procedure
+has not been designed so far and probably we may postpone this work as
+unimportant although it should be kept in mind during JFFS3
+implementation.
+
+Conceivably, JFFS3 might try to find an older obsolete node
+containing the corrupted information as well as to reconstruct the
+corrupted data using the corresponding in-memory data if it is present.
+The recovery is especially important in case of corrupted direntry node
+as if we just ignore it we might loose the whole file or directory with
+children.
+
+%
+% Miscellaneous
+%
+\subsection{Miscellaneous}
+Like JFFS2, JFFS3 makes use of CRC32 checksum algorithm with the start seed
+0xFFFFFFFF.
+
+If zlib library is used to compress node's data it is worth asking zlib not to
+generate redundant adler32 checksum for better performance.
+
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
% MAXIMAL SIZE OF THE INODE NODE DATA
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -921,161 +922,6 @@
\end{itemize}

-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%
-% INODE CHECKPOINTS
-%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Inode Checkpoints}
-
-\subsection{JFFS2 and memory consumption problem} \label{ref_JFFS2_and_mem}
-TODO.
-
-Take a glimpse at\\
-for the description of the problem for now.
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%
-% DATA STRUCTURES
-%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Data Structures}
-
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-%
-% ALGORITHMS
-%
-%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\section{Algorithms}
-This section describes the main JFFS3 algorithms in pseudo-code. The
-description doesn't contain all the details but refers most fundamental
-steps.
-
-\subsection{Inode build}
-The algorithm is initiated by the \texttt{iget()} VFS call. From the user's
-perspective it happens e.g. on \texttt{stat()} and \texttt{open()} calls.
-
-\begin{verbatim}
-For each node_ref
-{
-  read the corresponding node from the flash;
-  If the inode is the directory inode
-  {
-    insert the dirent node to dentree.
-  }
-  Else if the inode is the regular file inode
-  {
-    insert the data node to fragtree.
-  }
-  Else if the inode is the symlink inode
-  {
-  }
-  Else read the metadata for another types of the inode as well;
-}
-
-If the inode is the directory inode or the regular file inode
-{
-  For each icp_ref
-  {
-    read the corresponding ICP from the flash;
-    For each node in this ICP
-    {
-      If the inode is the directory inode
-      {
-        insert the dirent node to dentree.
-      }
-      Else if the inode is the regular file inode
-      {
-        insert the data node to fragtree.
-      }
-    }
-  }
-}
-\end{verbatim}
-
-Notes:
-\begin{itemize}
-\item Since the nodes which aren't referred by any ICP are younger (have
-the higher version) then those which refereed, we start building fragtree
-from them. In this case, we will have fewer RB-tree balancing
-operations.
-
-\item ICP entries are sorted by versions in ICPs and they must be
-processed in the descended version order.
-\end{itemize}
-
-\subsection{Garbage Collection}
-\begin{verbatim}
-Choose the vblock to GC (gcblock);
-
-For each node in the gcblock
-{
-  If node is valid
-  {
-    move the node;
-    If the node is described by an ICP
-    {
-      Obsolete the corresponding ICP entry in the ICP;
-    }
-  }
-}
-\end{verbatim}
-
-Notes:
-\begin{itemize}
-\item See [\ref{ref_Node_Valid}] for the algorithm of checking whether a
-node is valid;
-
-\item See [\ref{ref_Move_Node}] for the algorithm of a node moving;
-
-\item See [\ref{ref_Obsolete_Entry}] for the algorithm of how to
-obsolete an ICP entry in the ICP.
-\end{itemize}
-
-\subsubsection{Check if node is valid} \label{ref_Node_Valid}
-Each vblock has an associated list of its obsolete nodes. To check if
-a vblock's node is valid the list should be scanned.
-
-\subsubsection{Move a node} \label{ref_Move_Node}
-TODO
-
-\subsection{Obsolete an ICP entry} \label{ref_Obsolete_Entry}
-An ICP is associated with the icp\_ref. One inode may have more then on
-ICP.
-
-An ICP covers some version range and includes ICP entries referring
-\emph{all} the \emph{valid} nodes within that range.
-
-An icp\_ref contains a counter of valid nodes that it refers. When one
-of its nodes becomes obsolete, the counter is decremented. When the
-number of valid nodes referred by the ICP becomes too small, the ICP is
-treated as obsolete and is removed from the inode's icp\_ref list.
-
-\begin{verbatim}
-Decrement the icp_ref's valid nodes count;
-
-If the count becomes too small
-{
-  For each valid node in the icp
-  {
-    Allocate the node_ref for it;
-    Insert this node_ref to the node_refs list;
-  }
-
-  Remove the icp_ref from the icp_ref list;
-  Add the icp_ref's node_ref to the list of obsolete nodes;
-}
-\end{verbatim}
-
-\subsection{Flash scan}
-
-\subsection{FS build}
-
-\subsection{Memory shrink}
-TODO

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
@@ -1086,13 +932,16 @@
\begin{enumerate}
\item \emph{CRC} - Cyclic Redundancy Check
-\item \emph{ICP} - Inode Check-Point
+\item \emph{CP} -  Check-Point
+\item \emph{DCP} -  Data Check-Point
+\item \emph{DCP2} - Data Check-Point level 2
\item \emph{JFFS2} - Journalling Flash File System version 2
\item \emph{JFFS3} - Journalling Flash File System version 3
\item \emph{MTD} - Memory Technology Devices
\item \emph{VFS} - Virtual File System
\end{enumerate}

+
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
% DEFINITIONS