mtd/Documentation/jffs3 JFFS3design.tex, 1.29, 1.30 Makefile, 1.4,
1.5 definit.tex, 1.3, 1.4 intro.tex, 1.3, 1.4 jffs2.tex, 1.3,
1.4 jffs3req.tex, 1.3, 1.4 ref.tex, 1.3, 1.4 super.tex, 1.3,
1.4 tree.tex, 1.3, 1.4
Artem Bityutskiy
dedekind at infradead.org
Tue Nov 22 09:49:14 EST 2005
- Previous message: mtd/Documentation/jffs3/pics comprex-02.eps, NONE,
1.1 comprex-02.pdf, NONE, 1.1 comprex-02.png, NONE,
1.1 btree-01.eps, 1.2, 1.3 btree-01.pdf, 1.2, 1.3 btree-01.png,
1.1, 1.2 comprex-01.eps, 1.1, 1.2 comprex-01.pdf, 1.1,
1.2 comprex-01.png, 1.1, 1.2 flash-01.eps, 1.2,
1.3 idxprobl.eps, 1.1, 1.2 idxprobl.pdf, 1.2, 1.3 idxprobl.png,
1.1, 1.2 journal-01.eps, 1.4, 1.5 journal-01.pdf, 1.4,
1.5 journal-01.png, 1.3, 1.4 journal-02.eps, 1.2,
1.3 journal-02.pdf, 1.2, 1.3 journal-02.png, 1.1,
1.2 keyex-01.eps, 1.2, 1.3 keyex-01.pdf, 1.2, 1.3 keyex-01.png,
1.2, 1.3 node-01.eps, 1.5, 1.6 node-01.pdf, 1.5,
1.6 node-01.png, 1.4, 1.5 trivkey-01.eps, 1.3,
1.4 trivkey-01.pdf, 1.3, 1.4 trivkey-01.png, 1.3,
1.4 wandtree.eps, 1.3, 1.4 wandtree.pdf, 1.3, 1.4 wandtree.png,
1.2, 1.3
- Next message: mtd/fs/jffs2 summary.c,1.9,1.10
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
Update of /home/cvs/mtd/Documentation/jffs3
In directory phoenix.infradead.org:/tmp/cvs-serv31381
Modified Files:
JFFS3design.tex Makefile definit.tex intro.tex jffs2.tex
jffs3req.tex ref.tex super.tex tree.tex
Log Message:
Various minor fixes in different chapter.
Tweak the 'keys compression" chapter.
Different changes in pictures - make them more consistent.
Switch to version 0.31.
Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/JFFS3design.tex,v
retrieving revision 1.29
retrieving revision 1.30
diff -u -r1.29 -r1.30
--- JFFS3design.tex 16 Nov 2005 17:13:05 -0000 1.29
+++ JFFS3design.tex 22 Nov 2005 14:48:40 -0000 1.30
@@ -57,9 +57,9 @@
\large{Artem B. Bityutskiy\\
dedekind at infradead.org}\\
\vspace{13cm}
-\large{Version 0.30 (draft)}\\
+\large{Version 0.31 (draft)}\\
\vspace{0.5cm}
-November 16, 2005
+November 22, 2005
\end{center}
\end{titlepage}
%\maketitle
@@ -183,7 +183,7 @@
\item When/how to update stat-data?
-\item How t ochose/add a key scheme?
+\item How to chose/add a key scheme?
\end{enumerate}
@@ -194,6 +194,8 @@
\item Garbage collection.
+\item Tree balancing.
+
\item Caching, write-behind cache.
\item An assumed flash model and the model of interactions between JFFS3 and
@@ -217,7 +219,8 @@
\item The minimal amount of file's data in a node is \texttt{PAGE\_SIZE}. No
way to create smaller nodes as it it possible in JFFS2.
-\item Portability.
+\item Portability (e.g., move FS between machines with different RAM~page size,
+etc).
\end{enumerate}
@@ -328,6 +331,7 @@
The following are the people I am very grateful for help (alphabetical order):
\begin{itemize}
+
\item \textbf{David Woodhouse} \texttt{<dwmw2 at infradead.org>}~-- the author of
JFFS2, answered a great deal of my questions about MTD and JFFS2 and suggested
some interesting ideas for JFFS3.
@@ -345,8 +349,8 @@
software.
\item \textbf{Victor V. Vengerov} \texttt{<vvv at oktetlabs.ru>}~-- my colleague
-from OKTET~Labs who spent a lot of time discussing the JFFS3 design approaches
-with me and suggested some interesting ideas.
+from OKTET~Labs who discussed some JFFS3 design approaches with me and
+suggested several interesting ideas.
\end{itemize}
Index: Makefile
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/Makefile,v
retrieving revision 1.4
retrieving revision 1.5
diff -u -r1.4 -r1.5
--- Makefile 13 Nov 2005 18:01:23 -0000 1.4
+++ Makefile 22 Nov 2005 14:48:40 -0000 1.5
@@ -1,27 +1,26 @@
all: pdf
-pdf_files: pics/btree-01.pdf pics/flash-01.pdf pics/journal-01.pdf \
- pics/node-01.pdf pics/sb-02.pdf pics/btree-02.pdf \
- pics/idxprobl.pdf pics/journal-02.pdf pics/sb-01.pdf \
- pics/wandtree.pdf
+pdf_files: pics/btree-01.pdf pics/btree-02.pdf pics/comprex-01.pdf \
+ pics/comprex-02.pdf pics/dataobj-01.pdf pics/flash-01.pdf \
+ pics/idxprobl.pdf pics/journal-01.pdf pics/journal-02.pdf \
+ pics/keyex-01.pdf pics/node-01.pdf pics/sb-01.pdf \
+ pics/sb-02.pdf pics/trivkey-01.pdf pics/wandtree.pdf
+
+png_files: pics/btree-01.png pics/btree-02.png pics/comprex-01.png \
+ pics/comprex-02.png pics/dataobj-01.png pics/flash-01.png \
+ pics/idxprobl.png pics/journal-01.png pics/journal-02.png \
+ pics/keyex-01.png pics/node-01.png pics/sb-01.png \
+ pics/sb-02.png pics/trivkey-01.png pics/wandtree.png
+
-png_files: pics/btree-01.png pics/flash-01.png pics/journal-01.png \
- pics/node-01.png pics/sb-02.png pics/btree-02.png \
- pics/idxprobl.png pics/journal-02.png pics/sb-01.png \
- pics/wandtree.png
-
-
-tex_files: JFFS3design.tex definit.tex intro.tex jffs2.tex \
- jffs3req.tex pics ref.tex super.tex tree.tex
+tex_files: JFFS3design.tex
-
pdf: pdf_files tex_files
pdflatex JFFS3design.tex
-
+
html: png_files tex_files
latex2html JFFS3design.tex
clean:
- rm -rf JFFS3design.aux JFFS3design.log JFFS3design.out \
- JFFS3design.pdf JFFS3design.toc JFFS3design
+ rm -rf *.aux *.log *.out *.bak *.pdf *.toc JFFS3design
Index: intro.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/intro.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- intro.tex 16 Nov 2005 17:13:05 -0000 1.3
+++ intro.tex 22 Nov 2005 14:48:40 -0000 1.4
@@ -59,7 +59,7 @@
\includegraphics{pics/idxprobl.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=100mm,height=50mm]{pics/idxprobl.pdf}
+\includegraphics[width=90mm,height=45mm]{pics/idxprobl.pdf}
%end{latexonly}
\end{center}
\caption{JFFS3 indexing problem example.}
@@ -283,7 +283,7 @@
\includegraphics{pics/btree-02.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=159mm,height=70mm]{pics/btree-02.pdf}
+\includegraphics[width=159mm,height=65mm]{pics/btree-02.pdf}
%end{latexonly}
\end{center}
\caption{The JFFS3 tree.}
@@ -310,7 +310,7 @@
\includegraphics{pics/flash-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=159mm,height=30mm]{pics/flash-01.pdf}
+\includegraphics[width=159mm,height=25mm]{pics/flash-01.pdf}
%end{latexonly}
\end{center}
\caption{An illustration of leaf and indexing nodes separation.}
@@ -428,7 +428,7 @@
\includegraphics{pics/journal-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=159mm,height=65mm]{pics/journal-01.pdf}
+\includegraphics[width=159mm,height=60mm]{pics/journal-01.pdf}
%end{latexonly}
\end{center}
\caption{The JFFS3 journal.}
@@ -455,7 +455,7 @@
\includegraphics{pics/journal-02.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=130mm,height=60mm]{pics/journal-02.pdf}
+\includegraphics[width=120mm,height=55mm]{pics/journal-02.pdf}
%end{latexonly}
\end{center}
\caption{Read request processing in JFFS3.}
Index: tree.tex
===================================================================
RCS file: /home/cvs/mtd/Documentation/jffs3/tree.tex,v
retrieving revision 1.3
retrieving revision 1.4
diff -u -r1.3 -r1.4
--- tree.tex 16 Nov 2005 17:13:05 -0000 1.3
+++ tree.tex 22 Nov 2005 14:48:40 -0000 1.4
@@ -1,18 +1,22 @@
+This chapter discusses the all the aspects related to the main JFFS3 entity~--
+the tree. Please, refer to section \ref{ref_SectionIndexing} for basic
+information about the JFFS3 tree.
+
%
% OBJECTS
%
\subsection{Objects} \label{ref_SectionObjects}
JFFS3 keeps file system objects in the leaf level of the tree (in leaf nodes)
-and the below is the list of supported objects.
+and the following is the list of supported objects.
\begin{enumerate}
\item \emph{Data} objects contain files' data and are kept in \emph{data
nodes}. Each data node holds one \mbox{RAM page} bytes of data (i.e.,
\texttt{PAGE\_SIZE} which is 4K on most \mbox{32-bit} architectures). But of
-course, for small files (less then one RAM page bytes) and for files' tails
-there may be less data.
+course, in case of small files (less then one RAM page bytes) and files'
+tails~-- less data data may be put to the data node.
%
% Figure with an data objects illustration
@@ -23,7 +27,7 @@
\includegraphics{pics/dataobj-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=130mm,height=90mm]{pics/dataobj-01.pdf}
+\includegraphics[width=130mm,height=85mm]{pics/dataobj-01.pdf}
%end{latexonly}
\end{center}
\caption{An illustration of files' data representation.}
@@ -33,8 +37,8 @@
Figure~\ref{ref_FigureDataObj-01} illustrates the correspondence between files'
contents and data objects. Each \mbox{RAM~page-size} piece of a 13K file
corresponds to a data node in the JFFS3 tree. The 1K tail of the file also
-corresponds to a data node. Because of compression the actual size of
-data nodes is less then the corresponding file fragments.
+corresponds to a data node. But because of compression actual sizes of data
+nodes are less then the corresponding file fragments.
The division on \mbox{RAM~page-sized} fragments relates to the Linux Virtual
Memory Management architecture. Namely, the Linux \emph{Page Cache} works in
@@ -160,7 +164,7 @@
\includegraphics{pics/trivkey-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=110mm,height=75mm]{pics/trivkey-01.pdf}
+\includegraphics[width=110mm,height=70mm]{pics/trivkey-01.pdf}
%end{latexonly}
\end{center}
\caption{The trivial key scheme.}
@@ -247,6 +251,9 @@
in the Reiser4 file system and it is claimed that slow sorting is a bottleneck
in certain \mbox{real-life} workloads. And the like.
+\item Different keys compression methods may be used in different key schemes
+(see section \ref{ref_SectionKeysCompr} below).
+
\end{itemize}
%
@@ -258,7 +265,7 @@
\includegraphics{pics/keyex-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=110mm,height=8mm]{pics/keyex-01.pdf}
+\includegraphics[width=110mm,height=7mm]{pics/keyex-01.pdf}
%end{latexonly}
\end{center}
\caption{Direntry key layout example.}
@@ -267,35 +274,37 @@
So it is obvious why JFFS3 is not attached to a fixed key scheme but instead,
admits of many different key schemes (one at a time of course) with a
-possibility to choose the best suited key scheme.
+possibility to choose the best suited key scheme.
%
% Keys compression
%
-\subsubsection{Keys compression}
+\subsubsection{Keys compression} \label{ref_SectionKeysCompr}
The index is the most frequently \mbox{re-written} part of JFFS3. Indeed, every
single change at the leaf level of the tree requires \mbox{re-writing} $L-1$
-indexing nodes. So, it is really, really important for JFFS3 to keep the tree
-as shallow as it is possible. This means that it makes sense to apply a sort of
-compression to indexing nodes.
-
-There are several ways to compress keys and the following are the examples of
-possible compression techniques.
+indexing nodes. The number of index updates is reduced by the
+\mbox{write-behind} cache and by the \mbox{journal}, but it is still changed
+very often. So, it is extremely important for JFFS3 to keep the tree as
+shallow as it is possible.
+
+This means, that it makes sense to apply a sort of compression to keys in
+indexing nodes. There are several ways to compress keys and the following are
+examples of possible compression techniques.
\begin{description}
-\item[Offset compression.] The compression of offsets in keys may be based on
-the observation that the overwhelming majority of files in many file systems
-are small. This means that it might makes sense to code smaller offsets by
-fewer bits.
+\item[Offsets coding.] Offsets compression may be based on the observation that
+the overwhelming majority of files in many file systems are small files. This
+means, that it might makes sense to code smaller offsets by fewer bits.
Table \ref{ref_TableOffsCodes} contains an example of how offsets may be
-encoded. For offsets in range \texttt{0KB-8KB} only 3~bits are enough, so
-bit sequence "\texttt{000}" will encode offset \texttt{0}, and bit sequence
-"\texttt{001}" will encode offset \texttt{4K} (remember, offsets in keys are
-\mbox{RAM page-aligned} and the RAM~page size is assumed to be 4K). Offsets in
-range \texttt{8KB-64KB} are encoded by 6~bits and so on.
+encoded. For offsets in range \texttt{0KB-8KB} only 3~bits are enough, so the
+bit sequence "\texttt{000}" will encode offset \texttt{0}, and the bit sequence
+"\texttt{001}" will encode offset \texttt{4K} \footnote{Recall, offsets in keys
+are \mbox{RAM page-aligned} and by default, the RAM~page size is assumed to be
+4K in this document}. Offsets in range \texttt{8KB-64KB} are encoded by 6~bits
+and so on.
\begin{table}[h]
\begin{center}
@@ -306,26 +315,26 @@
\texttt{8KB-64KB} & 16 bits & \texttt{01} & 6 bits\\
\texttt{64KB-1MB} & 20 bits & \texttt{10} & 10 bits\\
\texttt{1MB-128MB} & 27 bits & \texttt{110} & 18 bits\\
-\texttt{128MB-1GB} & 32 bits & \texttt{111} & 23 bits\\
+\texttt{128MB-4GB} & 32 bits & \texttt{111} & 23 bits\\
\end{tabular}
-\caption{An example of offset compression.}
+\caption{An example of offset coding.}
\label{ref_TableOffsCodes}
\end{center}
\end{table}
-Note, table \ref{ref_TableOffsCodes} contains just an example and does not
-pretend to work well in all cases.
-
-\item[Inode number compression.] If the approximate number of inodes on the
+\item[Inode number coding.] If the approximate number of inodes on the
file system is known in advance, similar coding scheme may be exploited for
inode numbers providing JFFS3 may reuse deleted files' inode numbers.
-\item[Prefix compression.] In case of the trivial key scheme the first part of
-any key is the inode number and for sequences of keys with the same inode
-number the inode number may be specified only once as a common prefix.
+\item[Common prefix compression.] In case of the trivial key scheme the first
+field of any key is the inode number. Any other key scheme will likely also
+contain the inode number in keys. If the inode number is the first component of
+the key, all keys belonging to the same inode will go sequentially in indexing
+nodes. To put it differently, there will be sequences of keys prefixed by the
+same inode number in the tree.
%
-% Prefix compression example
+% Common prefix compression example
%
\begin{figure}[h]
\begin{center}
@@ -333,43 +342,62 @@
\includegraphics{pics/comprex-01.png}
\end{htmlonly}
%begin{latexonly}
-\includegraphics[width=75mm,height=60mm]{pics/comprex-01.pdf}
+\includegraphics[width=160mm,height=40mm]{pics/comprex-01.pdf}
%end{latexonly}
\end{center}
-\caption{An example of prefix compression.}
+\caption{The common prefix compression idea illustration.}
\label{ref_FigureKeyComprEx_01}
\end{figure}
-Figure \ref{ref_FigureKeyComprEx_01} illustrates how prefix compression works.
-Suppose there are 3 consecutive keys with the same inode number. Compressed
-keys have the following format.
-
-\begin{itemize}
-
-\item The first field is the common inode number.
-
-\item The second field is the \mbox{3-bit} key type identifier. Prefix
-compression makes use of reserved key type identifier 7 (\texttt{type~=~7}).
-
-\item The next field is the compression descriptor (\texttt{CD}) which takes
-few bits and describes the compression. In our example, the compression
-descriptor says that the next two fields are \texttt{count} and the common
-\texttt{type~=~0} (remember, the keys could have had \mbox{non-equivalent}
-types). The \texttt{count} field defines to how many of following keys the
-common \{\texttt{inode~\#~=~17,~type~=~0}\} prefix ought to be applied.
+The evident compression method for these key sequences is to store the inode
+number only once as the common prefix for the entire key sequence, instead of
+duplicating it in every key. Figure \ref{ref_FigureKeyComprEx_01} illustrates
+how does the prefix compression work.
+
+\item[Offsets sequence compression.] In the trivial key scheme the last field
+of data keys is the offset. The offset is multiple of RAM~page size. Obviously,
+indexing nodes will contain sequences of keys each of which describes data
+objects belonging to the same file but with different offsets. Moreover, the
+keys will be ordered in increasing key order.
+
+For sequences like this it is possible to only specify the starting offset, the
+ending offset and the number of keys in the sequence, instead of wasting space
+storing the offset in each key of the sequence.
+%
+% Offsets sequence compression example
+%
+\begin{figure}[h]
+\begin{center}
+\begin{htmlonly}
+\includegraphics{pics/comprex-02.png}
+\end{htmlonly}
+%begin{latexonly}
+\includegraphics[width=160mm,height=42mm]{pics/comprex-02.pdf}
+%end{latexonly}
+\end{center}
+\caption{The Offsets sequence compression idea illustration.}
+\label{ref_FigureKeyComprEx_02}
+\end{figure}
-\end{itemize}
+Figure \ref{ref_FigureKeyComprEx_02} presents an example of the offsets sequence
+compression method. Four consecutive keys which describe four data objects
+belonging to the same inode may be represented as a sequence of four keys
+without the offset field, but prefixed by the starting offset, the ending
+offset and the number of keys in the sequence.
\end{description}
-Thus, because of compression, JFFS3 keys have variable size which means that it
-is impossible to directly apply the binary search algorithm to the contents of
+Note, the above compression methods may be combined to achieve better
+compression.
+
+Because of compression, JFFS3 keys have variable size which means that it is
+impossible to directly apply the binary search algorithm to the contents of
indexing nodes. In JFFS3, indexing nodes are decompressed when read and are
-cached in decompressed form. After the indexing node have beed decompressed,
+cached in decompressed form. And after the indexing node has been decompressed,
the binary search algorithm is applicable.
-We hope that keys compression will considerably reduce the amount of
-\mbox{on-flash} indexing information and increase the overall performance (just
-because the amount of Input/Output will lessen). But only actual
+We believe that keys compression will considerably reduce the amount of
+\mbox{on-flash} indexing information and increase the overall performance just
+because the amount of Input/Output will lessen. But only actual
\mbox{fixed-size} keys~vs.~\mbox{variable-size} keys tests will show if there
-is some real performance gain.
+is some real performance gain present.
- Previous message: mtd/Documentation/jffs3/pics comprex-02.eps, NONE,
1.1 comprex-02.pdf, NONE, 1.1 comprex-02.png, NONE,
1.1 btree-01.eps, 1.2, 1.3 btree-01.pdf, 1.2, 1.3 btree-01.png,
1.1, 1.2 comprex-01.eps, 1.1, 1.2 comprex-01.pdf, 1.1,
1.2 comprex-01.png, 1.1, 1.2 flash-01.eps, 1.2,
1.3 idxprobl.eps, 1.1, 1.2 idxprobl.pdf, 1.2, 1.3 idxprobl.png,
1.1, 1.2 journal-01.eps, 1.4, 1.5 journal-01.pdf, 1.4,
1.5 journal-01.png, 1.3, 1.4 journal-02.eps, 1.2,
1.3 journal-02.pdf, 1.2, 1.3 journal-02.png, 1.1,
1.2 keyex-01.eps, 1.2, 1.3 keyex-01.pdf, 1.2, 1.3 keyex-01.png,
1.2, 1.3 node-01.eps, 1.5, 1.6 node-01.pdf, 1.5,
1.6 node-01.png, 1.4, 1.5 trivkey-01.eps, 1.3,
1.4 trivkey-01.pdf, 1.3, 1.4 trivkey-01.png, 1.3,
1.4 wandtree.eps, 1.3, 1.4 wandtree.pdf, 1.3, 1.4 wandtree.png,
1.2, 1.3
- Next message: mtd/fs/jffs2 summary.c,1.9,1.10
- Messages sorted by:
[ date ]
[ thread ]
[ subject ]
[ author ]
More information about the linux-mtd-cvs
mailing list