mtd/fs/jffs3 JFFS3design.tex,1.46,1.47

[Artem Bityuckiy]

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

Modified Files:
	JFFS3design.tex 
Log Message:
Start Directory checkpoint chapter

Index: JFFS3design.tex
===================================================================
RCS file: /home/cvs/mtd/fs/jffs3/JFFS3design.tex,v
retrieving revision 1.46
retrieving revision 1.47
diff -u -r1.46 -r1.47
--- JFFS3design.tex	23 Apr 2005 17:00:04 -0000	1.46
+++ JFFS3design.tex	23 Apr 2005 17:46:24 -0000	1.47
@@ -360,17 +360,17 @@
 
 The data structure corresponding to FCP is:
 \begin{verbatim}
-struct jffs3_raw_file_checkpoint
+struct jffs3_raw_fcp
 {
   uint16_t magic;   /* Magic bitmask of FCP node. */
+  uint64_t version; /* Helps to differentiate between valid
   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. */
+                       and obsolete file checkpoints. */
   uint32_t hdr_crc; /* FCP Header CRC32 checksum. */
-  uint32_t crc;     /* FCP CRC32 checksum. */
+  uint32_t crc;     /* FCP payload CRC32 checksum. */
 
-  /* An array of references  to nodes corresponding to the
+  /* An array of references to data nodes corresponding to
    * FCP. The array is sorted by the node range offset in
    * ascending order. */
   struct jffs3_fcp_entry entries[];
@@ -513,6 +513,45 @@
 denoting the minimal size of file which can have an
 associated FCP2 node.
 
+\subsection{Directory checkpoints}
+Directory checkpoints (DCP):
+\begin{itemize}
+\item are associated with directory inodes;
+\item refer all the valid directory entries of the directory;
+\item allow to quickly find the directory entry nodes by their names.
+\end{itemize}
+
+The DCP data structure looks as follows.
+
+\begin{verbatim}
+struct jffs3_raw_dcp
+{
+  uint16_t magic;   /* Magic bitmask of DCP node. */
+  uint64_t version; /* Helps to differentiate between valid
+                       and obsolete directory checkpoints. */
+  uint32_t hstart;  /* Starting value of the DCP hash range. */
+  uint32_t hend;    /* Ending value of the DCP hash range. */
+  uint32_t hdr_crc; /* DCP Header CRC32 checksum. */
+  uint32_t crc;     /* DCP payload CRC32 checksum. */
+  
+  /* An array of references to direntry nodes corresponding to
+   * DCP. The array is sorted by the direntry name hash value
+   * in ascending order. */
+  struct jffs3_dcp_entry entries[];
+} __attribute__((packed));
+
+struct jffs3_dcp_entry
+{
+  uint32_t hash;
+  uint32_t offs;
+} __attribute__((packed));
+\end{verbatim}
+
+To split large DCP on several nodes JFFS3 makes use of hash function
+$H$ mapping directory entry names to 32-bit integers. In case of good
+$H$ the probability of name collisions will be $1/2^{32}$.
+
+
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
 %
 % VIRTUAL BLOCK HANDLING