mtd/Documentation/jffs3 JFFS3design.tex,1.14,1.15

[Artem Bityuckiy]

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

Modified Files:
	JFFS3design.tex 
Log Message:
Add a chapter about the journal, few fixes.


Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/JFFS3design.tex,v
retrieving revision 1.14
retrieving revision 1.15
diff -u -r1.14 -r1.15
--- JFFS3design.tex	11 Aug 2005 11:37:50 -0000	1.14
+++ JFFS3design.tex	15 Aug 2005 07:36:09 -0000	1.15
@@ -227,27 +227,27 @@
 There are basically 4 main entities which constitute the JFFS3 file system:
 
 \begin{itemize}
-\item \emph{the tree} - contains  files, directories, attributes, etc; this
+\item \emph{the tree} -- contains  files, directories, attributes, etc; this
 is the main, the largest and the most complex entity in JFFS3
 (see~\ref{ref_SectionTree});
 
-\item \emph{the map} - contains the information about each flash
+\item \emph{the map} -- contains the information about each flash
 eraseblock (wear-levelling data, bad flag, etc) and about each
 sector (\emph{used} or \emph{dirty}); the map is mainly used by the
 \emph{garbage collector} and the \emph{space allocator}; \TODO{insert
 reference}
 
-\item \emph{the superblock} - contains the reference to the \emph{root node} of
+\item \emph{the superblock} -- contains the reference to the \emph{root node} of
 the tree, to the map, etc. as well as the static data about the whole file system
 (the version number, etc); here belongs supplementary eraseblocks which provide
 the possibility to quickly find the superblock (see
 section~\ref{ref_SectionSB});
 
-\item \emph{the journal} - the area where any file system change is
+\item \emph{the journal} -- the area where any file system change is
 written at the first time; since
 the transactions support is not planned in JFFS3 (but it may be added later),
 the journal may be regarded as an optimization which helps to reduce the amount
-of flash I/O. \TODO{insert reference}
+of flash I/O (see section \ref{ref_SectionJournal}).
 \end{itemize}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -360,7 +360,7 @@
 
 \item \emph{name 1} (56 bits) -- the first 7 bytes of the name;
 
-\item \emph{name 2} (64 bits) -- the 7th - 15th bytes of the name;
+\item \emph{name 2} (64 bits) -- the 7th-15th bytes of the name;
 
 \item \emph{name 3/hash} (64 bits) -- the last part of the name for short name
 and the hash of the remaining bytes of the name for long names.
@@ -424,6 +424,7 @@
 
 The xattr entry key has the same structure as the direntry, but obviously, has
 different "type" field.
+
 %
 % The figure with the xattr entry key
 %
@@ -431,7 +432,7 @@
 \includegraphics[width=120mm,height=12mm]{xattrentry_key}
 \end{center}
 
-And the xattr body key has the same structure as the file body key, but the
+The xattr body key has the same structure as the file body key, but the
 "object ID" filed is the unique ID of the extended attribute, not the inode
 number. The other difference is that the first 60 bits store the object ID of
 the file (directory, etc) to which this xattr belongs, not the "parent ID".
@@ -445,6 +446,50 @@
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %
+% THE JOURNAL
+%
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+\section{The Journal} \label{ref_SectionJournal}
+This section describes the JFFS3 journal.
+
+When user creates or changes something in JFFS3 (i.e., write to a file, create
+a file, change attributes, etc), this implies the tree is changed -- more objects
+are added or old objects are updated. When an object is added or updated, the
+corresponding leaf node of the tree is added/updated. To add new leaf node assumes
+to add the key/link to its parent node while to update old leaf node assumes to
+update the link in its parent node (because the updated leaf node will be
+written at another flash position).
+
+Thus, any tree change assumes that the entire
+path from the root to the leaf node must be (re)written. I.e., if
+the height of the tree is 4, at least 4 flash sectors must be written. If
+the change requires re-balancing of the tree, then the number of written
+sectors is even greater.
+
+Obviously, when several changes affect the same nodes, it is possible to
+apply the changes at once with less flash I/O overhead then if they would be applied
+independently. This is why the journal exists -- it allows JFFS3 to accumulate
+many of changes and later commit them all at once, thus, lessening the amount
+of flash I/O.
+
+Since the journal's contents are not in the tree, JFFS3 ought to look-up the
+journal before any tree lookup. To achieve this JFFS3 maintains the \emph{journal
+RB-tree} in RAM. The keys of the journal RB-tree are the keys in the main
+tree. So, before any lookup operation in the main tree, JFFS3 look-ups the node
+in the journal RB-tree.
+
+There is certain limit on the maximal size of the journal -- when the journal
+becomes too long it is committed. The journal may also be committed if the
+system memory is low.
+
+On mount, JFFS3 must find the \emph{journal eraseblocks} and read the journal,
+building the journal RB-tree, etc. This make the mount slower, so the length of
+the journal should not be too long. The journal eraseblocks, as well as the
+root node of the tree, are referred from the superblock (see section
+\ref{ref_SectionSB}), so may be located very quickly without any flash scan.
+
+%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
+%
 % SUPERBLOCK MANAGEMENT
 %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -472,10 +517,11 @@
 
 The JFFS3 superblock consists of two parts:
 \begin{itemize}
-\item \emph{static superblock} - contains only stative data which is never
+\item \emph{static superblock} -- contains only stative data which is never
 changed by JFFS3; static superblock takes the first not bad eraseblock of the
 JFFS3 partition and may be change only by external user-level tools;
-\item just \emph{superblock} (\emph{SB}) - contains dynamic data, is often changed and
+
+\item just \emph{superblock} (\emph{SB}) -- contains dynamic data, is often changed and
 requires special methods to deal with it; the rest of this chapter is
 devoted to this dynamic part of the JFFS3 superblock; note, unlike the static
 superblock, the superblock takes one sector, not one eraseblock.
@@ -787,6 +833,12 @@
 only purpose of the journal is optimization (it will have more
 functions if we ever decide to add transactions support to JFFS3). 
 
+\item \textbf{Journal RB-tree} -- a in-memory Red-Black tree referring
+Journal nodes which were not committed so far and are not in the tree. Before
+any tree lookup JFFS3 lookups the node in the journal RB-tree.
+
+\item \textbf{Journal eraseblock} -- an eraseblock containing the journal data.
+
 \item \textbf{Leaf node} -- any node from the leaf level of the tree (level 0).
 Leaf nodes contain only data and do not further refer other nodes.
 
@@ -848,17 +900,18 @@
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Abbreviations}
 \begin{enumerate}
-\item \textbf{ACL} - Access Control List
-\item \textbf{ECC} - Error Correction Code
-\item \textbf{CRC} - Cyclic Redundancy Check
-\item \textbf{GC} - Garbage Collector
-\item \textbf{JFFS2} - Journalling Flash File System version 2
-\item \textbf{JFFS3} - Journalling Flash File System version 3
-\item \textbf{MTD} - Memory Technology Devices
-\item \textbf{RAM} - Random Access Memory
-\item \textbf{SB} - Super Block
-\item \textbf{VFS} - Virtual File System
-\item \textbf{UID} - User Identifier
+\item \textbf{ACL} -- Access Control List
+\item \textbf{ECC} -- Error Correction Code
+\item \textbf{CRC} -- Cyclic Redundancy Check
+\item \textbf{FS} -- File System
+\item \textbf{GC} -- Garbage Collector
+\item \textbf{JFFS2} -- Journalling Flash File System version 2
+\item \textbf{JFFS3} -- Journalling Flash File System version 3
+\item \textbf{MTD} -- Memory Technology Devices
+\item \textbf{RAM} -- Random Access Memory
+\item \textbf{SB} -- Super Block
+\item \textbf{VFS} -- Virtual File System
+\item \textbf{UID} -- User Identifier
 \end{enumerate}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%