This file describes the design, layouts, and file formats of a libsvn_fs_fs repository. Design ------ In FSFS, each committed revision is represented as an immutable file containing the new node-revisions, contents, and changed-path information for the revision, plus a second, changeable file containing the revision properties. In contrast to the BDB back end, the contents of recent revision of files are stored as deltas against earlier revisions, instead of the other way around. This is less efficient for common-case checkouts, but brings greater simplicity and robustness, as well as the flexibility to make commits work without write access to existing revisions. Skip-deltas and delta combination mitigate the checkout cost. In-progress transactions are represented with a prototype rev file containing only the new text representations of files (appended to as changed file contents come in), along with a separate file for each node-revision, directory representation, or property representation which has been changed or added in the transaction. During the finale stage of the commit, these separate files are marshalled onto the end of the prototype rev file to form the immutable revision file. Layout of the FS directory -------------------------- The layout of the FS directory (the "db" subdirectory of the repository) is: revs Subdirectory containing revs File containing rev revprops Subdirectory containing rev-props File containing rev-props for transactions Subdirectory containing transactions .txn Directory containing transaction locks Subdirectory containing locks partial-digest Subdirectory named for first 3 letters of an MD5 digest File containing locks/children for path with current File specifying current revision write-lock Lockfile for commits Files in the revprops directory are in the hash dump format used by svn_hash_write. The format of the "current" file is a single line of the form " \n" giving the youngest revision, the next unique node-ID, and the next unique copy-ID for the repository. The "write-lock" file is an empty file which is locked before the final stage of a commit and unlocked after the new "current" file has been moved into place to indicate that a new revision is present. Node-revision IDs ----------------- In order to support efficient lookup of node-revisions by their IDs and to simplify the allocation of fresh node-IDs during a transaction, we treat the fields of a node-ID in new and interesting ways. Within a revision file, node-revs have a txn-id field of the form "r/", to support easy lookup. The node-id and copy-id fields are unique base36 values as in the BDB implementation. New node-revision IDs assigned within a transaction have the txn-id field of "t". The node-id or copy-id field may be base36 values if the node-revision is derived from a pre-existing node and/or copy; if the node-revision must have a freshly-assigned node-id or copy-id, it uses "_" followed by a base36 unique to the transaction. During the final phase of a commit, node-revision IDs are rewritten to have unique node-ID and copy-ID fields and to have "r/" txn-id fields. The temporary assignment of node-ID and copy-ID fields has implications for svn_fs_compare_ids and svn_fs_check_related. The IDs _1.0.t1 is not related to the ID _1.0.t2 even though they have the same node-ID, because temporary node-IDs are restricted in scope to the transactions they belong to. Copy-IDs and copy roots ----------------------- Copy-IDs are assigned in the same manner as they are in the BDB implementation: * A node-rev resulting from a creation operation (with no copy history) receives the copy-ID of its parent directory. * A node-rev resulting from a copy operation receives a fresh copy-ID, as one would expect. * A node-rev resulting from a modification operation receives a copy-ID depending on whether its predecessor derives from a copy operation or whether it derives from a creation operation with no intervening copies: - If the predecessor does not derive from a copy, the new node-rev receives the copy-ID of its parent directory. If the node-rev is being modified through its created-path, this will be the same copy-ID as the predecessor node-rev has; however, if the node-rev is being modified through a copied ancestor directory (i.e. we are performing a "lazy copy"), this will be a different copy-ID. - If the predecessor derives from a copy and the node-rev is being modified through its created-path, the new node-rev receives the copy-ID of the predecessor. - If the predecessor derives from a copy and the node-rev is not being modified through its created path, the new node-rev receives a fresh copy-ID. This is called a "soft copy" operation, as distinct from a "true copy" operation which was actually requested through the svn_fs interface. Soft copies exist to ensure that the same pair is not used twice within a transaction. Unlike the BDB implementation, we do not have a "copies" table. Instead, each node-revision record contains a "copyroot" field identifying the node-rev resulting from the true copy operation most proximal to the node-rev. If the node-rev does not itself derive from a copy operation, then the copyroot field identifies the copy of an ancestor directory; if no ancestor directories derive from a copy operation, then the copyroot field identifies the root directory of rev 0. Revision file format -------------------- A revision file contains a concatenation of various kinds of data: * Text and property representations * Node-revisions * At the end, the changed-path data * Two offsets at the very end A representation begins with a line containing either "PLAIN\n" or "DELTA\n" or "DELTA \n", where , , and give the location of the delta base of the representation and the amount of data it contains (not counting the header or trailer). If no base location is given for a delta, the base is the empty stream. After the initial line comes raw svndiff data, followed by a cosmetic trailer "ENDREP\n". If the a representation is for the text contents of a directory node, the expanded contents are in hash dump format mapping entry names to " " pairs, where is "file" or "dir" and gives the ID of the child node-rev. If a representation is for a property list, the expanded contents are in the form of a dumped hash map mapping property names to property values. The marshalling syntax for node-revs is a series of fields terminated by a blank line. Fields have the syntax ": \n", where is a symbolic field name (each symbolic name is used only once in a given node-rev) and is the value data. Unrecognized fields are ignored, for extensibility. The following fields are defined: id The ID of the node-rev type "file" or "dir" pred The ID of the predecessor node-rev count Count of node-revs since the base of the node text " " for text rep props " " for props rep and give location of rep gives length of rep, sans header and trailer gives size of expanded rep gives hex MD5 digest of expanded rep cpath FS pathname node was created at copyfrom " " of copyfrom data copyroot " " of the root of this copy The predecessor of a node-rev crosses both soft and true copies; together with the count field, it allows efficient determination of the base for skip-deltas. The first node-rev of a node contains no "pred" field. A node-revision with no properties may omit the "props" field. A node-revision with no contents (a zero-length file or an empty directory) may omit the "text" field. In a node-revision resulting from a true copy operation, the "copyfrom" field gives the copyfrom data. The "copyroot" field identifies the root node-revision of the copy; it may be omitted if the node-rev is its own copy root (as is the case for node-revs with copy history, and for the root node of revision 0). Copy roots are identified by revision and created-path, not by node-rev ID, because a copy root may be a node-rev which exists later on within the same revision file, meaning its offset is not yet known. The changed-path data is represented as a series of changed-path items, each consisting of two lines. The first line has the format " \n", where is the node-rev ID of the new node-rev, is "add", "delete", "replace", or "modify", and are "true" or "false" indicating whether the text and/or properties changed, and is the changed pathname. For deletes, is the node-rev ID of the deleted node-rev, and and are always "false". The second line has the format " \n" containing the node-rev's copyfrom information if it has any; if it does not, the second line is blank. At the very end of a rev file is a pair of lines containing "\n \n", where is the offset of the root directory node revision and is the offset of the changed-path data. All numbers in the rev file format are unsigned and are represented as ASCII decimal. Transaction layout ------------------ A transaction directory has the following layout: rev Prototype rev file with new text reps props Transaction props next-ids Next temporary node-ID and copy-ID changes Changed-path information so far node.. New node-rev data for node node...props Props for new node-rev, if changed node...children Directory contents for node-rev The two kinds of props files are both in hash dump format. The "next-ids" file contains a single line " \n" giving the next temporary node-ID and copy-ID assignments (without the leading underscores). The "children" file for a node-revision begins with a copy of the hash dump representation of the directory entries from the old node-rev (or a dump of the empty hash for new directories), and then an incremental hash dump entry for each change made to the directory. The "changes" file contains changed-path entries in the same form as the changed-path entries in a rev file, except that and may both be "reset" (in which case and are both always "false") to indicate that all changes to a path should be considered undone. Reset entries are only used during the final merge phase of a transaction. The node-rev files have the same format as node-revs in a revision file, except that the "text" and "props" fields are augmented as follows: * The "props" field may have the value "-1" if properties have been changed and are contained in a "props" file within the node-rev subdirectory. * For directory node-revs, the "text" field may have the value "-1" if entries have been changed and are contained in a "contents" file in the node-rev subdirectory. * For file node-revs, the "text" field may have the value "-1 " if the text representation is within the prototype rev file. * The "copyroot" field may have the value "-1 " if the copy root of the node-rev is part of the transaction in process. Locks layout ------------------ Locks in FSFS are stored in serialized hash format in files whose names are MD5 digests of the FS path which the lock is associated with. For the purposes of keeping directory inode usage down, these digest files live in subdirectories of the main lock directory whose names are the first 3 characters of the digest filename. Also stored in the digest file for a given FS path are pointers to other digest files which contain information associated with other FS paths that are our path's immediate children. To answer the question, "Does path FOO have a lock associate with it?", one need only generate the MD5 digest of FOO's absolute-in-the-FS path (say, 3b1b011fed614a263986b5c4869604e8), lock for a file located like so: /path/to/repos/locks/3b1/3b1b011fed614a263986b5c4869604e8 And then see if that file contains lock information. To inquire about locks on children of the path FOO, you would reference the same path as above, but look for a list of children in that file (instead of lock information). Children as listed as MD5 digests, too, so you would simply iterate over those digests and consult the files they reference, and so on, recursively.