mtd/fs/jffs3 JFFS3design.tex,1.41,1.42
Artem Bityuckiy
dedekind at infradead.org
Fri Apr 22 13:18:42 EDT 2005
Update of /home/cvs/mtd/fs/jffs3
In directory phoenix.infradead.org:/tmp/cvs-serv26465
Modified Files:
JFFS3design.tex
Log Message:
Update DCP chapter.
Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/fs/jffs3/JFFS3design.tex,v
retrieving revision 1.41
retrieving revision 1.42
diff -u -r1.41 -r1.42
--- JFFS3design.tex 21 Apr 2005 16:50:20 -0000 1.41
+++ JFFS3design.tex 22 Apr 2005 17:18:39 -0000 1.42
@@ -9,6 +9,7 @@
\documentclass[12pt,a4paper,oneside,titlepage]{article}
\usepackage{hyperref}
\usepackage{html}
+\usepackage{longtable}
\textwidth=18cm
\oddsidemargin=0cm
\topmargin=0cm
@@ -335,8 +336,8 @@
Data checkpoints (DCP):
\begin{itemize}
\item are associated with regular files;
-\item refer all the valid nodes of a regular file inode;
-\item play the role of JFFS2 fragtrees, i.e., allow to quickly locate
+\item refer all the valid nodes of the regular file inode;
+\item play the role of JFFS2 fragment trees, i.e., allow to quickly locate
positions of data nodes for any given file data range.
\end{itemize}
@@ -345,15 +346,15 @@
Small files have only one correspondent DCP, large files may have many
associated data checkpoints.
-Each DCP corresponds to a fixed data range of file $R$, or
-\emph{DCP range}.
+Each DCP corresponds to a fixed data range of the file, and
+this range is called \emph{DCP range} or $R_{DCP}$.
The idea behind such a splitting is to facilitate:
\begin{itemize}
-\item GC and file change speed optimization - we update only few DCP nodes if
+\item GC and file change speed optimization -- we update only few DCP nodes if
a large file is being changed or one of its nodes is being GCed;
-\item memory consumption optimization - we don't need to keep in-core
+\item memory consumption optimization -- we don't need to keep in-core
the DCP ranges;
-\item DCP composing optimization - DCP entries are sorted in DCP and
+\item DCP composing optimization -- DCP entries are sorted and
it is much faster to sort short arrays rather then long.
\end{itemize}
@@ -383,65 +384,117 @@
}
\end{verbatim}
-The value of the DCP range $R$ depends on various aspects:
+The value of the DCP range $R_{DCP}$ depends on various aspects:
\begin{description}
-\item[Memory consumption.] The larger is $R$, the fewer DCP references
-we should keep in-core. For example, for 128~MiB file
-we would need to keep 8192 DCP references in RAM if $R$~=~16~KiB and
-only 128 DCP references if $R$~=~1~MiB.
-
-\item[The maximal DCP node size on flash.] DCP node physical sizes shouldn't be
-neither too large nor too small. Very large DCP nodes result in slow
-DCP updates whereas very small DCP nodes imply larger space overhead and
-almost do not decrease DCP update time. It it sane to limit the DCP
-node size by one of few NAND pages. Fore a data checkpoint
-of size = 1 NAND page the possible maximal number of DCP entries $E$
-(which are 6~bytes in size) is:
-
+\item[Memory consumption.] JFFS3 ought to keep in-core DCP references
+and it is clear then the larger is $R_{DCP}$ the less is the memory
+consumption. To facilitate good scalability $R_{DCP}$ must grow with growing
+flash size. Nonetheless, this will make troubles when moving an JFFS3
+image from small flash to large.
+
+\item[RAM page size.] Obviously $R_{DCP}$ must be multiple of
+\texttt{PAGE\_SIZE}, and to facilitate JFFS3 portability we should
+make it multiple of the largest 64~KiB \texttt{PAGE\_SIZE}
+used in Linux our days. 4 KiB should be treated as the smallest possible
+RAM page size.
+
+\item[DCP node size.] The DCP node physical size shouldn't be
+neither too large nor too small. To facilitate faster DCP update on NAND
+flashes the maximum DCP node physical size $S_{DCP}$ should be one NAND
+page.
+One DCP entry takes 6 bytes and the DCP header takes 32 bytes and it is
+easy to calculate the maximum number DCP entries $E_{DCP}$ if DCP node
+size would be limited to one NAND page:
\begin{center}
\begin{tabular}{ll}
-NAND page size & Max. entries per DCP($E$) \\
+\textbf{NAND page size} & $\bf E_{DCP}$ \\
+\hline
512 bytes & 80\\
2048 bytes & 336\\
4096 bytes & 667\\
\end{tabular}
\end{center}
-\item[The maximal data node range.] The larger is the maximal data node
-range, the fewer DCP entries we need to store for in a DCP for a fixed $R$.
-The following are examples of possible configurations, assuming the
-physical DCP node size is limited to the size of the NAND page.
+\item[Largest data node size.] To gain write performance JFFS3 should be
+able to write non-pristine nodes, i.e., nodes of size <
+\texttt{PAGE\_SIZE}. In order to allow filling the DCP range by
+non-pristine nodes the following should be true:
+$$R_{DCP} > R_{data}{\cdot}E_{DCP},$$
+where $R_{data}$ is the maximal data node range and $E_{DCP}$ is the
+maximal number of DCP entries in DCP. The table below illustrates
+the average data node range size depending on $R$ and NAND page size.
+512 bytes NAND page:
\begin{center}
\begin{tabular}{ll}
-Max. data node range ($r$) & Max. DCP range ($R$)\\
-512 bytes per NAND page &\\
+$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
\hline
-4 KiB & 320 KiB\\
-8 KiB & 640 KiB\\
-16 KiB & 1280 KiB\\
-2048 bytes per NAND page &\\
-\hline
-4 KiB & 1344 KiB\\
-8 KiB & 2688 KiB\\
-16 KiB & 5376 KiB\\
-4096 bytes per NAND page &\\
+64 KiB & 820 bytes\\
+128 KiB & 1.64 KiB\\
+256 KiB & 3.28 KiB\\[4pt]
+\end{tabular}
+\end{center}
+
+2048 bytes NAND page:
+\begin{center}
+\begin{tabular}{ll}
+$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
\hline
-4 KiB & 2668 KiB\\
-8 KiB & 5336 KiB\\
-16 KiB & 10672 KiB\\
+256 KiB & 780 bytes\\
+512 KiB & 1.56 KiB\\
+1 MiB & 3.12 KiB\\[4pt]
\end{tabular}
\end{center}
-In order to make it possible to write in smaller chunks then $r$, we
-ought to have \hbox{$R > r{\cdot}E$}. Since the number of data nodes
-corresponding to an inode range is still limited, JFFS3 must start
-merging small data nodes when the number of DCP entries reaches the
-value $E$ while not the whole range $R$ is filled by data. The possible
-way to calculate $R$ is to use formula
-\hbox{$R = (r{\cdot}E)/k$}, where $k=2, 3, ...$
+4096 bytes NAND page:
+\begin{center}
+\begin{tabular}{ll}
+$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
+\hline
+512 KiB & 790 bytes\\
+1 MiB & 1.57 KiB\\
+2 MiB & 3.14 KiB\\
+\end{tabular}
+\end{center}
\end{description}
+Keeping in-core references to all the DCP nodes of a
+file may eat much RAM. Assuming that we keep in-core only 4~byte DCP
+flash addresses (which is in fact unreachable) we have:
+
+\begin{center}
+\begin{tabular}{llll}
+\textbf{File size} & \textbf{NAND Page size} &
+$\bf R_{DCP}$ & \textbf{RAM required}\\
+\hline
+64 MiB & 512 bytes & 256 KiB & 1 MiB\\
+1 GiB & 2048 bytes & 1 MiB & 4 MiB\\
+8 GiB & 4096 bytes & 2 MiB & 8 MiB\\
+\end{tabular}
+\end{center}
+
+To relax this JFFS3 uses \emph{second level data checkpoints} (DCP2) referring
+the level one data checkpoints of the file. Similarly to DCP, DCP2
+constraints are:
+\begin{itemize}
+\item DCP2 range $R_{DCP2}$ is multiple of DCP range $R_{DCP}$;
+\item the largest DCP2 node physical size $S_{DCP2}$ is limited by the
+NAND page size;
+\end{itemize}
+
+With DCP2 the above table looks as:
+\begin{center}
+\begin{tabular}{llll}
+\textbf{File size} & \textbf{NAND Page size} &
+$\bf R_{DCP}$ & \textbf{RAM required}\\
+\hline
+64 MiB & 512 bytes & 256 KiB & 12 bytes\\
+1 GiB & 2048 bytes & 1 MiB & 12 bytes\\
+8 GiB & 4096 bytes & 2 MiB & 24 bytes\\
+\end{tabular}
+\end{center}
+
+TODO: but the real picture is not so nice... more complications needed...
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
@@ -680,7 +733,7 @@
{
list_head *list;
node_ref *node;
- /* Status bits and accounting dependend on state */
+ /* Status bits and accounting dependent on state */
u32 status;
}
\end{verbatim}
@@ -716,7 +769,7 @@
selectable by the user to scale the system according to the
requirements. See the paragraph about virtual erase blocks.
-Using JFFS2 concatentation of 16 blocks would reduce the RAM
+Using JFFS2 concatenation of 16 blocks would reduce the RAM
requirement to 32KiB for the largest devices.
\subsection{JFFS2 blocks reference} \label{ref_JFFS2_blk_ref}
@@ -775,7 +828,7 @@
this depends on several aspects:
\begin{itemize}
-\item The physcial block size. Nodes must not exceed the physical block size
+\item The physical block size. Nodes must not exceed the physical block size
to allow the configurable selection of block concatenation in virtual blocks.
\item Nodes can not be written over physical block boundaries.
More information about the linux-mtd-cvs
mailing list