mtd/Documentation/jffs3 JFFS3design.tex,1.22,1.23

Wed Nov 2 12:24:58 EST 2005

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

Modified Files:
	JFFS3design.tex 
Log Message:
Minor fixes and updates


Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/JFFS3design.tex,v
retrieving revision 1.22
retrieving revision 1.23
diff -u -r1.22 -r1.23

--- JFFS3design.tex	2 Nov 2005 15:22:00 -0000	1.22
+++ JFFS3design.tex	2 Nov 2005 17:24:54 -0000	1.23
@@ -69,11 +69,13 @@
 % ABSTRACT
 %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
-\pagestyle{empty} \begin{abstract} JFFS2, the Journalling Flash File System
-version 2, is widely used in the embedded systems world. It was designed for
-relatively small flash chips and has serious problems when it is used on large
-flash devices. Unfortunately, these scalability problems are deep inside the
-design of the file system, and cannot be solved without full redesign.
+\pagestyle{empty}
+
+\begin{abstract} JFFS2, the Journalling Flash File System version 2, is widely
+used in the embedded systems world. It was designed for relatively small flash
+chips and has serious problems when it is used on large flash devices.
+Unfortunately, these scalability problems are deep inside the design of the
+file system, and cannot be solved without full redesign.
 
 This document describes JFFS3~-- a new flash file system which is designed
 to be scalable.
@@ -323,7 +325,7 @@
 \includegraphics{pics/idxprobl.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=100mm,height=50mm]{pics/idxprobl}
+\includegraphics[width=100mm,height=50mm]{pics/idxprobl.pdf}
 %end{latexonly}
 \end{center}
 \caption{JFFS3 indexing problem example.}
@@ -358,7 +360,7 @@
 \includegraphics{pics/wandtree.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=80mm]{pics/wandtree}
+\includegraphics[width=159mm,height=80mm]{pics/wandtree.pdf}
 %end{latexonly}
 \end{center}
 \caption{Wandering tree example.}
@@ -393,7 +395,7 @@
 %
 % B+ TREES
 %
-\subsection{$\bf B^+$-trees}
+\subsection{B-trees}
 
 JFFS3 uses \mbox{$B^+$-trees} and this subsection makes a short introduction to
 \mbox{$B^+$-trees}. There is a plenty of books where one may find more
@@ -416,7 +418,7 @@
 \includegraphics{pics/btree-01.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=65mm]{pics/btree-01}
+\includegraphics[width=159mm,height=65mm]{pics/btree-01.pdf}
 %end{latexonly}
 \end{center}
 \caption{$B^+$-tree example.}
@@ -441,7 +443,7 @@
 \includegraphics{pics/node-01.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=90mm,height=30mm]{pics/node-01}
+\includegraphics[width=90mm,height=30mm]{pics/node-01.pdf}
 %end{latexonly}
 \end{center}
 \caption{The structure of a non-leaf node in $B^+$-tree.}
@@ -542,7 +544,7 @@
 \includegraphics{pics/btree-02.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=70mm]{pics/btree-02}
+\includegraphics[width=159mm,height=70mm]{pics/btree-02.pdf}
 %end{latexonly}
 \end{center}
 \caption{The JFFS3 tree.}
@@ -569,7 +571,7 @@
 \includegraphics{pics/flash-01.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=30mm]{pics/flash-01}
+\includegraphics[width=159mm,height=30mm]{pics/flash-01.pdf}
 %end{latexonly}
 \end{center}
 \caption{Leaf and indexing nodes separation illustration.}
@@ -633,7 +635,7 @@
 \includegraphics{pics/journal-01.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=60mm]{pics/journal-01}
+\includegraphics[width=159mm,height=60mm]{pics/journal-01.pdf}
 %end{latexonly}
 \end{center}
 \caption{The JFFS3 journal.}
@@ -660,7 +662,7 @@
 \includegraphics{pics/journal-02.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=130mm,height=60mm]{pics/journal-02}
+\includegraphics[width=130mm,height=60mm]{pics/journal-02.pdf}
 %end{latexonly}
 \end{center}
 \caption{The read request processing in JFFS3.}
@@ -757,10 +759,11 @@
 
 Anchor eraseblocks contain references to \emph{chain eraseblocks}. Chain
 eraseblocks may either refer other chain eraseblocks or the \emph{super
-eraseblock} (see figure \ref{ref_FigureSB_01}). Note, if there are $k$ chain
-erase blocks, the anchor area will refer the the chain eraseblock 1, which will
-refer the chain eraseblock 2, which will refer the chain eraseblock 3 and so
-forth. The chain eraseblock $k$ will refer the super eraseblock.
+eraseblock} (see figure \ref{ref_FigureSB_01}). The number of chain eraseblocks
+varies depending on the size of the JFFS3 partition. If there are $k$ chain
+erase blocks, the anchor area will refer chain eraseblock 1, which will refer
+chain eraseblock 2, which will refer chain eraseblock 3 and so forth. The chain
+eraseblock $k$ will refer the super eraseblock.
 
 %
 % Figure with superblock management superblocks
@@ -771,10 +774,10 @@
 \includegraphics{pics/sb-01.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=21mm]{pics/sb-01}
+\includegraphics[width=159mm,height=21mm]{pics/sb-01.pdf}
 %end{latexonly}
 \end{center}
-\caption{Eraseblocks involved to the superblock management scheme.}
+\caption{Types of eraseblocks involved to the superblock management scheme.}
 \label{ref_FigureSB_01}
 \end{figure}
 
@@ -782,7 +785,7 @@
 chain eraseblocks contain references to the next chain eraseblock or to the
 super eraseblock.
 
-The JFFS3 superblock management mechanism works as follows. Suppose there are
+The JFFS3 superblock management mechanisms work as follows. Suppose there are
 $k$ chain eraseblocks in the current superblock management scheme. The superblock
 updates are written to consecutive sectors of the super eraseblock. When
 the super eraseblock has no more empty sectors, new super eraseblock is picked,
@@ -793,7 +796,7 @@
 eraseblock~$k$ is picked and the corresponding reference is written to chain
 eraseblock~$k-1$, and so on. When there are no free sectors in the chain
 eraseblock~1, new chain eraseblock~1 is picked and the corresponding
-reference in the anchor area is updated.
+reference is written to the anchor area.
 
 Figure \ref{ref_FigureSB_02} presents the example of the superblock management
 scheme ($k = 2$).
@@ -807,7 +810,7 @@
 \includegraphics{pics/sb-02.png}
 \end{htmlonly}
 %begin{latexonly}
-\includegraphics[width=159mm,height=200mm]{pics/sb-02}
+\includegraphics[width=159mm,height=200mm]{pics/sb-02.pdf}
 %end{latexonly}
 \end{center}
 \caption{The superblock management example.}
@@ -816,14 +819,14 @@
 
 \begin{enumerate}
 
-\item Initially there are 2 chain eraseblocks (numbers 5 and 419) and the super
+\item Initially, there are 2 chain eraseblocks (numbers 5 and 419) and the super
 eraseblock (number~501). There is a reference in the first sector of the anchor
 area which refers the chain eraseblock~1. The first sector of the chain
 eraseblock~1 refers the chain eraseblock~2, and the first sector of the chain
 eraseblock~2 refers the super eraseblock. The first sector of the super
 eraseblock contains the superblock.
 
-\item After the superblock has been updated, the 2nd sector of the super
+\item After the superblock has been updated, the second sector of the super
 eraseblock contains the valid copy of the superblock and the first sector
 contains garbage.
 
@@ -832,12 +835,12 @@
 eraseblock contain garbage.
 
 \item As there were no free sectors at the super eraseblock, new super
-eraseblock was chosen (eraseblock number~7) and the next superblock update was
+eraseblock was chosen (eraseblock number~7) and the superblock update was
 written to the first sector of the new super eraseblock. As the super
 eraseblock changed its position, the corresponding reference at the chain
-eraseblock~2 should have been updated. It was updated \mbox{out-of-place} and
-now the first sector of the chain eraseblock~2 is dirty while the second sector
-contains the valid reference to the new super eraseblock.
+eraseblock~2 was updated. It was updated \mbox{out-of-place} and now the first
+sector of the chain eraseblock~2 is dirty while the second sector contains the
+valid reference to the new super eraseblock.
 
 \item The superblock has been updated many times and the super eraseblock
 changed its position many times and it is currently at the eraseblock number
@@ -851,7 +854,7 @@
 super eraseblock and new super eraseblock was picked (eraseblock number~398)
 and the valid copy of the superblock is currently at the first sector of the
 eraseblock number~398, Also, there were no free sectors at the chain
-eraseblock~2 and new chain eraseblock~2 was found (eraseblock number~77), so
+eraseblock~2 and new chain eraseblock~2 was picked (eraseblock number~77), so
 the first sector of the eraseblock~77 contains the valid reference to the super
 eraseblock. Since the chain eraseblock~2 changed its position, the
 corresponding reference at the chain eraseblock~1 was updated and at the moment
@@ -873,7 +876,7 @@
 anchor eraseblock~2 was used. So, at the moment, the valid reference to the
 chain eraseblock~1 is at the first sector of the anchor eraseblock~2. From now
 on, the first anchor eraseblock may be erased and may be used again when the
-second anchor eraseblock becomes full.
+second anchor eraseblock is full.
 
 \end{enumerate}
 
@@ -885,8 +888,8 @@
 most $N$ times ($N$ is the number of sectors in the eraseblock).
 
 \item In case of NAND flash, the sector is the real minimal physical
-input/output unit, so only $N$ updates are possible in the anchor eraseblock
-and in the chain eraseblocks. But if the real input/output unit is smaller then
+input/output unit, so only $N$ updates are possible in anchor eraseblocks
+and in chain eraseblocks. But if the real input/output unit is smaller then
 the sector (i.e., if JFFS3 works on top of NOR flash) the advantage of this may
 be used and more references may be packed into one anchor or chain eraseblock.
 
@@ -920,7 +923,7 @@
 are needed. This is determined by the need to ensure that the anchor area is
 not worn out earlier then the rest of the JFFS3 partition.
 
-Let's Denote the number of required chain eraseblocks plus one (the super
+Let's denote the number of required chain eraseblocks plus one (the super
 eraseblock) $m$ and calculate $m$ assuming the worst case scenario: any
 file system data update requires the superblock update. This would correspond
 to synchronous JFFS3 operation mode with \mbox{zero-length} journal.
@@ -938,22 +941,27 @@
 excluding the static superblock and the anchor area is referred to as the
 \emph{data area}.
 
-$T_A$ and $T_D$ may be expressed as
+If $R_A$ is the average rate of the anchor area updates (sectors per second),
+$R_D$ s the average rate of the data area updates and $N$ is the number of
+sectors per the eraseblock, then the anchor area will be written to with rate
+$R_A/N$ eraseblocks per second and the data area will be written to with the
+rate $R_D/N$ eraseblocks per second. So, JFFS3 will need to erase $R_A/N$
+eraseblocks per second in the anchor area and $R_D/N$ eraseblocks per second in
+the data area. Therefore, $T_A$ and $T_D$ may be expressed as
 
 $$
-T_A = \frac{2D}{R_A},
+T_A = \frac{2D \cdot N}{R_A},
 $$
 $$
-T_D = \frac{(M-2) \cdot D}{R_D},
+T_D = \frac{(M-3) \cdot D \cdot N}{R_D},
 $$
 
-where $R_A$ is the average rate of the anchor area updates (sectors per
-second), $R_D$ s the average rate of the data area  updates, $D$ is the maximum
-number of flash eraseblock erase cycles, and $M$ is the total number of non-bad
-eraseblocks on the JFFS3 partition. Hence,
+where $D$ is the maximum number of flash eraseblock erase cycles, and $M$ is
+the number of non-bad eraseblock on the JFFS3 partition. We substracted 3 from
+$M$ to get the number of eraseblocks in the data area.
 
 \begin{equation}
-\frac{T_A}{T_D} = 2 \cdot \frac{R_D}{(M-2) \cdot R_A}.
+\frac{T_A}{T_D} = 2 \cdot \frac{R_D}{(M-3) \cdot R_A}.
 \label{ref_Equation_TA_and_TD}
 \end{equation}
 
@@ -962,19 +970,19 @@
 (\ref{ref_Equation_TA_and_TD}) and that in this case $R_A = R_D = R$, we have
 
 $$
-\frac{T_A}{T_D} = 2 \cdot \frac{1}{(M-2)}.
+\frac{T_A}{T_D} = \frac{2}{(M-2)}.
 $$
 
-Suppose $m = 1$. i.e., there are no chain eraseblocks and only the super eraseblock
-is used. In this case each file system data update will require (a) the
-superblock update and (b) the anchor area update. Therefore, providing $N$ is
-the number of sector in the eraseblock, the anchor area will be written $N$
-times less frequently then when $m = 0$ and the data area will be written $2$
-times more frequently then when $m = 0$. This means, that $R_A = R/N$ and
-$R_D = 2R$ and from (\ref{ref_Equation_TA_and_TD}) we have
+Suppose $m = 1$. i.e., there are no chain eraseblocks and only the super
+eraseblock is used. In this case each file system data update will require (a)
+the superblock update in the data area and (b) the anchor area update.
+Therefore, the anchor area will be written $N$ times less frequently then when
+$m = 0$ and the data area will be written $2$ times more frequently then when
+$m = 0$. This means, that $R_A = R/N$ and $R_D = 2R$ and from
+(\ref{ref_Equation_TA_and_TD}) we have
 
 $$
-\frac{T_A}{T_D} = 2 \cdot \frac{2N}{M-2}.
+\frac{T_A}{T_D} = 2 \cdot \frac{2N}{M-3}.
 $$
 
 When $m = 2$, i.e. the chain eraseblock 1 and the super eraseblock are used,
@@ -985,38 +993,38 @@
 R$ and from (\ref{ref_Equation_TA_and_TD}) we have
 
 $$
-\frac{T_A}{T_D} = 2 \cdot \frac{2N^2+N}{M-2}.
+\frac{T_A}{T_D} = 2 \cdot \frac{2N^2+N}{M-3}.
 $$
 
 For $m = 3$, analogously,
 
 $$
-\frac{T_A}{T_D} = 2 \cdot \frac{2N^3 + N^2 + N}{M-2},
+\frac{T_A}{T_D} = 2 \cdot \frac{2N^3 + N^2 + N}{M-3},
 $$
 
 and for $m = 0,1,2,\ldots$
 
 $$
-\frac{T_A}{T_D} = 2 \cdot \frac{2N^m + N^{m-1} + \ldots + N}{M-2}.
+\frac{T_A}{T_D} = 2 \cdot \frac{2N^m + N^{m-1} + \ldots + N}{M-3}.
 \label{ref_Equation_TA_div_TD}
 $$
 
 Consequently, from (\ref{ref_EquationSBIneq}) we have the following inequality:
 
 $$
-2 \cdot \frac{2N^m + N^{m-1} + \ldots + N}{M-2} \geqslant 1,
+2 \cdot \frac{2N^m + N^{m-1} + \ldots + N}{M-3} \geqslant 1,
 $$
 
 or neglecting the minor components,
 
 $$
-\frac{4N^m}{M} \geqslant 1,
+\frac{4N^m}{M-3} \geqslant 1,
 $$
 
 or
 
 \begin{equation}
-m \geqslant log_N{\frac{M}{4}}.
+m \geqslant log_N{\frac{M-3}{4}}.
 \label{ref_EquationSBIneq1}
 \end{equation}
 
@@ -1055,9 +1063,9 @@
 To find the superblock during mount, JFFS3 finds the valid reference in the
 anchor eraseblocks, then finds the valid reference in chain erase blocks
 $1$,~$2$,~$\ldots$,~$m-1$, and finally finds the valid superblock in the super
-eraseblock.  Since JFFS3 assigns versions to sectors of anchor/chain/super
-eraseblock and the versions are increased by one on every update, the binary
-search algorithm may be used to find the valid sector.
+eraseblock.  Since JFFS3 assigns versions to records in anchor/chain/super
+eraseblocks and the versions are increased by one on every update, the binary
+search algorithm may be used to quickly find the valid sector.
 
 The valid reference in the anchor area may be found after $log_2(2N)+2$ steps
 (one step involves one sector read operation), the reference in chain/super
@@ -1065,15 +1073,15 @@
 must read
 
 $$
-S = 2(m+1) + log_2(2N) + m \cdot log_2(N)
+S = 2m + log_2(2N) + (m - 1) \cdot log_2(N)
 $$
 
 sectors.
 
 Table \ref{ref_TableNANDTimes} contains the approximate superblock search time
-for different existing NAND flashes.
+for different existing NAND flashes
 \footnote{the calculated superblock search time doesn't contain the ECC/CRC
-checking overhead as well as any other CPU overhead.}
+checking overhead as well as any other CPU overhead.}.
 
 \begin{table}[h]
 \begin{center}
@@ -1091,22 +1099,20 @@
 \end{table}
 
 For larger flash chips which would utilize the superblock management scheme
-with $n = 3$ (no such flashes exist at the moment), the superblock search time
+with $m = 3$ (no such flashes exist at the moment), the superblock search time
 would be about 4.3ms, providing the flash characteristics are the same as ST
 Micro's (see table \ref{ref_TableNANDTimes}).
 
-Note, the calculated SB search time doesn't contain the ECC/CRC checking
-overhead as well as any other CPU overhead.
-
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %
 % ISSUES/TO BE DONE
 %
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 \section{Issues/ideas/to be done}
-This section is a temporary list of issues which should be solved, ideas which
-should be thought and analyzed more or things which were thought about but are
-not yet described in this document.
+
+This section contains a temporary list of issues which should be solved, ideas
+which should be thought and analyzed deeper or things which were thought about
+but are not yet described in this document.
 
 The following is the list of things which should be thought about more.
 
@@ -1206,6 +1212,7 @@
 
 \item Change the Credits section a bit.
 
+\item Re-calculate digits for SB search time and $m$.
 \end{enumerate}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
@@ -1325,7 +1332,8 @@
 
 \item $N$~-- the number of sectors per eraseblock.
 
-\item $S$~-- the size of the JFFS3 flash partition.
+\item $S$~-- the size of the JFFS3 flash partition (assuming there are no bad
+block).
 \end{itemize}
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



