mtd/fs/jffs3 JFFS3design.tex,1.45,1.46
Artem Bityuckiy
dedekind at infradead.org
Sat Apr 23 13:00:08 EDT 2005
Update of /home/cvs/mtd/fs/jffs3
In directory phoenix.infradead.org:/tmp/cvs-serv30293
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.45
retrieving revision 1.46
diff -u -r1.45 -r1.46
--- JFFS3design.tex 23 Apr 2005 15:07:09 -0000 1.45
+++ JFFS3design.tex 23 Apr 2005 17:00:04 -0000 1.46
@@ -50,7 +50,7 @@
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
-% JFFS2 analysis
+% JFFS2 ANALYSIS
%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{JFFS2 analysis}
@@ -325,58 +325,58 @@
types of checkpoints are defined:
\begin{itemize}
-\item data checkpoints which are associated with regular files;
-\item directory checkpoints which are associated with directories.
+\item file checkpoints which are associated with regular file inodes;
+\item directory checkpoints which are associated with directory inodes.
\end{itemize}
%
% Data checkpoints
%
-\subsection{Data checkpoints}
-Data checkpoints (DCP):
+\subsection{File checkpoints}
+File checkpoints (FCP):
\begin{itemize}
-\item are associated with regular files;
-\item refer all the valid nodes of the regular file inode;
+\item are associated with regular file inodes;
+\item refer all the valid data nodes of the file;
\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}
-Each regular file inode is associated with one or more data
-checkpoints. The number of the associated DCP depends on the file size.
-Small files have only one correspondent DCP, large files may have many
-associated data checkpoints.
+Each regular file inode is associated with one or more
+checkpoints. The number of the associated FCP depends on the file size.
+Small files have only one correspondent FCP, large files may have many
+associated checkpoints.
-Each DCP corresponds to a fixed data range of the file, and
-this range is called \emph{DCP range} or $R_{DCP}$.
+Each FCP corresponds to a fixed data range of the file, and
+this range is called \emph{FCP range} or $R_{FCP}$.
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
-a large file is being changed or one of its nodes is being GCed;
+\item fast GC and file change operations -- we update only one or few FCP nodes if
+a large file is changed or one of its nodes are Garbage Collected;
\item memory consumption optimization -- JFFS3 doesn't need to keep in-core
-the DCP ranges;
-\item DCP composing optimization -- DCP entries are sorted and
-it is much faster to sort short arrays rather then long.
+the FCP ranges;
+\item FCP creation optimization -- FCP entries are sorted in FCP and
+it is faster to sort short arrays rather then long.
\end{itemize}
-The data structure corresponding to DCP is:
+The data structure corresponding to FCP is:
\begin{verbatim}
-struct jffs3_raw_data_checkpoint
+struct jffs3_raw_file_checkpoint
{
- uint16_t magic; /* Magic bitmask of DCP node. */
- uint16_t index; /* The DCP index. Gives DCP range offset
- if multiplied by the DCP range. */
+ uint16_t magic; /* Magic bitmask of FCP node. */
+ uint16_t index; /* The FCP index. Gives FCP range offset
+ if multiplied by the FCP range. */
uint64_t version; /* Helps to differentiate between valid
and obsolete data checkpoints. */
- uint32_t hdr_crc; /* DCP Header CRC32 checksum. */
- uint32_t crc; /* DCP CRC32 checksum. */
+ uint32_t hdr_crc; /* FCP Header CRC32 checksum. */
+ uint32_t crc; /* FCP CRC32 checksum. */
/* An array of references to nodes corresponding to the
- * DCP. The array is sorted by the node range offset in
+ * FCP. The array is sorted by the node range offset in
* ascending order. */
- struct jffs3_dcp_entry entries[];
+ struct jffs3_fcp_entry entries[];
} __attribute__((packed));
-struct jffs3_raw_dcp_entry
+struct jffs3_raw_fcp_entry
{
uint32_t phys_offs; /* The position of the node on Flash. */
uint32_t offs; /* Offset of the data range the node refers. */
@@ -384,33 +384,34 @@
} __attribute__((packed));
\end{verbatim}
-The value of the DCP range $R_{DCP}$ depends on various aspects:
+The value of the FCP range $R_{FCP}$ depends on various aspects:
\begin{description}
-\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
+\item[Memory consumption.] JFFS3 ought to keep in-core FCP references
+and it is clear then the larger is $R_{FCP}$ the less is memory
+consumption. To facilitate good scalability $R_{FCP}$ must grow with growing
flash size. Nonetheless, this will make troubles when moving an JFFS3
image from small flash to large.
-From the other hand, very large $R_{DCP}$ implies large physical
-DCP nodes size and slower DCP updates.
+From the other hand, very large $R_{FCP}$ implies large physical
+FCP nodes size and slower FCP updates.
-\item[RAM page size.] Obviously $R_{DCP}$ must be multiple of
+\item[RAM page size.] Obviously $R_{FCP}$ must be multiple of
\texttt{PAGE\_SIZE}, and to facilitate JFFS3 portability in the case of
removable devices, 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
+make it multiple of the largest \texttt{PAGE\_SIZE}
+used in Linux our days (64 KiB). 4 KiB should be regarded 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 10 bytes, the DCP node header takes 20 bytes and it is
-easy to calculate the maximum number DCP entries $E_{DCP}$:
+\item[FCP node size.] FCP node physical size shouldn't be
+neither too large nor too small. To facilitate faster FCP update on NAND
+flashes the maximum FCP node physical size ($S_{FCP}$) should be one NAND
+page (or less).
+
+Since one FCP entry takes 10 bytes, the FCP node header takes 20 bytes
+the maximum number of FCP entries $E_{FCP}$ will be:
\begin{center}
\begin{tabular}{ll}
-\textbf{NAND page size} & $\bf E_{DCP}$ \\
+\textbf{NAND page size} & $\bf E_{FCP}$ \\
\hline
512 bytes & 49\\
2048 bytes & 202\\
@@ -419,18 +420,18 @@
\end{center}
\item[Largest data node size.] To gain the 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
+able to write non-pristine nodes, i.e., nodes of
+\mbox{size < \texttt{PAGE\_SIZE}}. In order to allow filling the FCP range by
non-pristine nodes the following should be true:
-$$R_{DCP} > \mathtt{PAGE\_SIZE}{\cdot}E_{DCP},$$
-where $E_{DCP}$ is the
-maximal number of DCP entries in DCP. The table below illustrates
+$$R_{FCP} > \mathtt{PAGE\_SIZE}{\cdot}E_{FCP},$$
+where $E_{FCP}$ is the
+maximal number of FCP entries in FCP. 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}
-$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
+$\bf R_{FCP}$ & \textbf{Average $\bf R_{data}$}\\
\hline
64 KiB & 1.3 KiB\\
128 KiB & 2.7 KiB\\
@@ -440,7 +441,7 @@
2048 bytes NAND page:
\begin{center}
\begin{tabular}{ll}
-$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
+$\bf R_{FCP}$ & \textbf{Average $\bf R_{data}$}\\
\hline
128 KiB & 650 bytes\\
256 KiB & 1.3 KiB\\
@@ -451,7 +452,7 @@
4096 bytes NAND page:
\begin{center}
\begin{tabular}{ll}
-$\bf R_{DCP}$ & \textbf{Average $\bf R_{data}$}\\
+$\bf R_{FCP}$ & \textbf{Average $\bf R_{data}$}\\
\hline
256 KiB & 642 bytes\\
512 KiB & 1.3 KiB\\
@@ -459,22 +460,20 @@
\end{tabular}
\end{center}
-The above tables assume each DCP entry may at most refer 4~KiB of data.
-Thus we guarantee that DCP node won't be larger then one NAND page.
+The above tables assumei that each FCP entry may at most refer 4~KiB of data.
For NOR and other non-paged flashes JFFS3 just assumes that
the flash page size is virtually 512 bytes or larger, depending on the
flash size.
\end{description}
-If we keep in RAM references of all the DCP nodes of a file, we may
-waste much RAM. Assuming that each reference takes 4~bytes
+If we keep in-core references of all the FCP nodes of a file, we may
+waste a lot ot RAM. Even assuming that each reference takes 4~bytes
(which is in fact unreachably few) we have:
-
\begin{center}
\begin{tabular}{lllll}
\textbf{File size} & \textbf{NAND Page size} &
-$\bf R_{DCP}$ & \textbf{RAM required} &
+$\bf R_{FCP}$ & \textbf{RAM required} &
\textbf{Flash overhead}\\
\hline
64 MiB & 512 bytes & 128 KiB & 2 MiB & 256 KiB (0.4\%)\\
@@ -484,24 +483,24 @@
\end{center}
The above table also shows the amount of Flash space required to store
-DCP nodes (assuming each DCP entry takes the whole Flash page).
+FCP nodes (assuming each FCP entry takes the whole Flash page).
-To relax RAM usage JFFS3 makes use of \emph{second level data
-checkpoints} (DCP2) referring
-the level one data checkpoints of the file similarly to how DCP refers
-data nodes. The following requirements are to be met for DCP2:
+To relax RAM usage JFFS3 makes use of \emph{second level file
+checkpoints} (FCP2) referring
+the level one file checkpoints of the file similarly to how FCP refers
+data nodes. The following requirements are to be met for FCP2:
\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
+\item FCP2 range $R_{FCP2}$ is multiple of FCP range $R_{FCP}$;
+\item the largest FCP2 node physical size $S_{FCP2}$ is limited by the
NAND page size;
\end{itemize}
-With DCP2 the above table looks as:
+With FCP2 the above table looks as:
\begin{center}
\begin{tabular}{lllll}
\textbf{File size} & \textbf{NAND Page size} &
-$\bf R_{DCP}$ & $\bf R_{DCP2}$
+$\bf R_{FCP}$ & $\bf R_{FCP2}$
& \textbf{RAM required}\\
\hline
64 MiB & 512 bytes & 256 KiB & 8 MiB & 32 bytes\\
@@ -510,10 +509,9 @@
\end{tabular}
\end{center}
-Besides $R_{DCP2}$ JFFS3 defines one more constant $R_{DCP2}^{min}$
+Beside $R_{FCP2}$, JFFS3 defines one more constant $R_{FCP2}^{min}$
denoting the minimal size of file which can have an
-associated DCP2 node.
-
+associated FCP2 node.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%
@@ -933,8 +931,8 @@
\item \emph{BB} - Bad Block
\item \emph{CRC} - Cyclic Redundancy Check
\item \emph{CP} - Check-Point
-\item \emph{DCP} - Data Check-Point
-\item \emph{DCP2} - Data Check-Point level 2
+\item \emph{FCP} - File Check-Point
+\item \emph{FCP2} - File 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
More information about the linux-mtd-cvs
mailing list