% % JFFS3 design issues. % % Copyright (C), 2005, Artem B. Bityutskiy, % % $Id: definit.tex,v 1.5 2005/11/27 14:37:49 dedekind Exp $ % \begin{enumerate} \item \textbf{Access Control Lists, ACL}~-- a modern mechanism to control accesses to files which provides much more flexibility that the standard Unix mechanism of owner/group/others permissions, see~[\ref{ref_ACL}] for more details. \item \textbf{Acl}~-- an object in the tree containing inode's ACL. Refer to section~\ref{ref_SectionObjects} for more information. \item \textbf{Acl key}~-- acl object's key. \item \textbf{Acl node}~-- a leaf node containing an acl object. \item \textbf{Anchor eraseblock, anchor area}~-- the second and the third \emph{good} eraseblocks of the JFFS3 partition which are reserved for the superblock management. See section~\ref{ref_SectionSBAlg} for more details. \item \textbf{Attr-data}~-- an object in the tree where inode's attributes are stored (standard Unix attributes like creation time, owner ID, etc and other attributes like the type of compression, etc). Refer to section~\ref{ref_SectionObjects} for more information. \item \textbf{Attr-data key}~-- attr-data object's key. \item \textbf{Attr-data node}~-- a leaf node containing an \mbox{attr-data} object. \item \textbf{$B$-tree}~-- a balanced search tree where each node has many children. See section~\ref{ref_SectionBTrees}. \item \textbf{$B^+$-tree}~-- a \mbox{$B$-tree} where no data is stored in \mbox{non-leaf} nodes but instead, is stored only in leaf nodes. \item \textbf{Branch node}~-- any node that is not leaf, not twig and not root. \item \textbf{Branching factor}~-- the branching factor of the $B$-tree is the number of children of a node. \item \textbf{Chain eraseblock}~-- an eraseblock containing references to other chain eraseblocks or to the super eraseblock. Chain eraseblocks facilitate quick SB searching and are the part of the JFFS3 superblock management scheme (see section~\ref{ref_SectionSBAlg}). The main reason why chain eraseblocks are needed is the need to provide good flash \mbox{wear-levelling}. \item \textbf{Clean eraseblock}~-- an eraseblock which contains no garbage, only valid information. \item \textbf{Data area}~-- the whole JFFS3 partition excluding the static superblock and anchor eraseblocks. \item \textbf{Data key}~-- data object's key. \item \textbf{Data node}~-- a leaf node with file's data. \item \textbf{Directory entry, direntry}~-- basically an association between the name and the inode number. \item \textbf{Direntry key}~-- direntry object's key. \item \textbf{Direntry node}~-- a leaf node containing a direntry object. \item \textbf{Dirt, dirty space}~-- information on flash which is not valid due to \mbox{out-of-place} updates or objects deletion. It is the aim if the Garbage Collector to reclaim the space occupied by dirt. \item \textbf{Dirty eraseblock}~-- an eraseblock which contains some dirt along with valid nodes. \item \textbf{Dirty sector}~-- a sector which contains dirt. \item \textbf{Erasable block, eraseblock}~-- the minimal erasable unit of the flash chip from the JFFS3's viewpoint. \item \textbf{Extended attributes, xattr}~-- an association between names and data for files and directories. See attr(5) Linux manual pages for more information. \item \textbf{Fanout}~-- the same as \textbf{branching factor}. \item \textbf{Free eraseblock}~-- an erased eraseblock (contains only \texttt{0xFF} words). \item \textbf{Garbage}~-- the same as \textbf{dirt}. \item \textbf{Garbage Collector}~-- a part of any Flash File System which is responsible for recycling dirty space and producing free eraseblocks. \item \textbf{Indexing information, index}~-- data structures which do not contain any file system data (files, directories, extended attributes, etc) but instead, keep track of this data. For example, indexing information allows to quickly find all the directory entries for any specified directory. In case of the FAT file system, the File Allocation Table is may be treated as the index, in case of the ext2 file system the inode table, the bitmap and the set of direct, indirect, doubly indirect and triply indirect pointers may be considered as the index. In JFFS3, the index is comprised by the indexing nodes. See section~\ref{ref_SectionIndexing} for more information. \item \textbf{Indexing eraseblock}~-- an eraseblock which contains indexing nodes. \item \textbf{Indexing node}~-- a \mbox{non-leaf} node. Indexing nodes have fixed size (one sector) and contain only keys and links. \item \textbf{In-place updates, in-place writes}~-- a method of updating \mbox{on-media} data when the update is written to the physical position where the data resides (in opposite to \mbox{out-of-place} updates). \item \textbf{Journal}~-- contains recent JFFS3 changes and all the file system updates first go to the journal. The purpose of the Journal is to accumulate a bunch of JFFS3 file system changes and to postpone updating the index. See section~\ref{ref_SectionJournalIntro} for more information. \item \textbf{Journal commit}~-- the process of \mbox{re-building} the indexing information for the data which is in the journal. After the journal has been committed the journal eraseblocks become just leaf eraseblocks. \item \textbf{Journal eraseblock}~-- an eraseblock containing the journal data. \item \textbf{Journal tree}~-- an \mbox{in-memory} tree referring Journal nodes which were not committed so far. When JFFS3 reads, it first looks up the journal tree to find out whether the searched information is there. See section~\ref{ref_SectionJournalIntro} for more details. \item \textbf{Key}~-- an identifier of objects in the tree. \item \textbf{Key type}~-- an unique identifier of the key type. There are 6 key types in JFFS3 (see section~\ref{ref_SectionKeys}). \item \textbf{Leaf eraseblock}~-- an eraseblock containing leaf nodes. \item \textbf{Leaf node}~-- any node from the leaf level of the tree (level 0). Leaf nodes contain only data and do not further refer other nodes. For more information see section~\ref{ref_SectionIndexing}. \item \textbf{NAND page}~-- a basic input output unit of NAND flash chips. ECC is calculated on the \mbox{per-NAND} page basis. See any NAND flash manual for more details, e.g.,~\ref{ref_TOSHIBA_TC58DVM92A1FT}. \item \textbf{Node}~-- a pile of the tree (the tree consists of nodes) as well as the container for file system data. There are different types of nodes in JFFS3. For more information see section~\ref{ref_SectionIndexing}. \item \textbf{Obsolete nodes/data/sectors}~-- the same as \textbf{dirty} nodes, data or sectors. \item \textbf{Out-of-place updates, out-of-place writes}~-- a sort of data updates when the update is not written to the same physical position, but instead, is written to some other place and the previous contents is treated as garbage afterwords. Opposite to \mbox{in-place} updates. \item \textbf{RAM page}~-- an unit of memory management in Virtual Memory Management subsystem of most modern operating systems (including Linux). See~[\ref{ref_VM}] for more information. \item \textbf{Sector}~-- the smallest writable unit of the \emph{flash chip} from JFFS3's viewpoint. May be equivalent to the minimal physical input/output unit (like in case of NAND flashes) or larger (like in case of NOR flashes). \item \textbf{Shared acl}~-- an acl object which is shared by many inodes for optimization purposes. Refer to section~\ref{ref_SectionObjects} for more information. \item \textbf{Static eraseblock}~-- the fist good erasable block of the JFFS3 partition where the file system static data is stored. JFFS3 may only read it and it is created/changed by external formatting tools. \item \textbf{Superblock}~-- a data structure which describes the whole JFFS3 file system. Only dynamic data is stored in the superblock, all the static data is kept in the static superblock. There is a comprehensive superblock management scheme in JFFS3, see section~\ref{ref_SectionSBAlg}. \item \textbf{Super eraseblock}~-- an eraseblock where the superblock is kept. See section~\ref{ref_SectionSBAlg} details. \item \textbf{Target eraseblock}~-- the eraseblock which is currently being processed by the Garbage Collector, i.e., nodes are moved from the \emph{target eraseblock} and it is erased afterwords. \item \textbf{Quota}~-- a mechanism which allows to assign different limits on the file system (e.g., restrict users in the number of files they may create or in the amount of space they may consume, etc). See~[\ref{ref_Quota}] for more details about quota support in Linux. \item \textbf{Tree}~-- the main entity JFFS3 design revolves about. The JFFS3 tree is a wandering \mbox{$B^+$-tree} where all the file system stuff (files, directories, extended attributes, etc) is stored. \item \textbf{Twig nodes}~-- nodes which reside one level upper then leaf nodes (level 1). \item \textbf{Valid nodes}~-- nodes which contain actual information, non-obsolete nodes. \item \textbf{Wandering tree}~-- a method of updating trees when there is no possibility to perform \mbox{in-place} updates. The JFFS3 tree is a wandering \mbox{$B^+$-tree}. See section~\ref{ref_SectionWandTrees} for more information. \item \textbf{Xattr}~-- a widely used contracted form for \textbf{extended attributes}. \item \textbf{Xattr-data}~-- an object in the tree containing the data of an extended attribute. \item \textbf{xattr-data key}~-- xattr-data object's key. \item \textbf{Xattr-data node}~-- a leaf node containing an \mbox{attr-data} object. \item \textbf{Xattr ID}~-- an unique identifier of an extended attribute. Refer to section~\ref{ref_SectionObjects} for more information. \item \textbf{Xentry}~-- an object in the tree which stores the association between the name of an extended attribute and its xattr~ID. Refer to section~\ref{ref_SectionObjects} for more information. \item \textbf{Xentry key}~-- xentry object's key. \item \textbf{Xentry node}~-- a leaf node containing a xentry object. \end{enumerate}