subversion-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From stef...@apache.org
Subject svn commit: r1547045 [3/4] - in /subversion/trunk: ./ subversion/libsvn_fs_fs/ subversion/tests/cmdline/ subversion/tests/cmdline/svntest/ subversion/tests/libsvn_fs_fs/ tools/server-side/
Date Mon, 02 Dec 2013 14:55:21 GMT
Modified: subversion/trunk/subversion/libsvn_fs_fs/structure
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/structure?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/structure (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/structure Mon Dec  2 14:55:20 2013
@@ -37,6 +37,8 @@ repository) is:
     <shard>.pack/     Pack directory, if the repo has been packed (see below)
       pack            Pack file, if the repository has been packed (see below)
       manifest        Pack manifest file, if a pack file exists (see below)
+      pack.l2p        Log-to-phys index file (format 7+, see below)
+      pack.p2l        Phys-to-log index file (format 7+, see below)
   revprops/           Subdirectory containing rev-props
     <shard>/          Shard directory, if sharding is in use (see below)
       <revnum>        File containing rev-props for <revnum>
@@ -138,6 +140,7 @@ The formats are:
   Format 4, understood by Subversion 1.6+
   Format 5, understood by Subversion 1.7-dev, never released
   Format 6, understood by Subversion 1.8
+  Format 7, understood by Subversion 1.9
 
 The differences between the formats are:
 
@@ -148,6 +151,7 @@ Delta representation in revision files
 Format options
   Formats 1-2: none permitted
   Format 3+:   "layout" option
+  Format 7+:   "addressing" option
 
 Transaction name reuse
   Formats 1-2: transaction names may be reused
@@ -183,15 +187,21 @@ Shard packing:
   Format 6+:  Applied equally to revision data and revprop data
     (i.e. same min packed revision)
 
+Addressing:
+  Format 1-6: Physical addressing; uses fixed positions within a rev file
+  Format 7+:  Logical addressing; uses item index that will be translated
+    on-the-fly to the actual rev / pack file location
+
 # Incomplete list.  See SVN_FS_FS__MIN_*_FORMAT
 
 
 Filesystem format options
 -------------------------
 
-Currently, the only recognised format option is "layout", which
-specifies the paths that will be used to store the revision files and
-revision property files.
+Currently, the only recognised format options are "layout" and "addressing".
+The first specifies the paths that will be used to store the revision
+files and revision property files.  The second specifies for which
+revisions address translation is required.
 
 The "layout" option is followed by the name of the filesystem layout
 and any required parameters.  The default layout, if no "layout"
@@ -219,19 +229,91 @@ The known layouts, and the parameters th
   revs/0/ directory will contain revisions 0-999, revs/1/ will contain
   1000-1999, and so on.
 
+The "addressing" option is followed by the name of the addressing mode
+and any required parameters.  The default addressing, if no "addressing"
+keyword is specified, is the 'physical' addressing.
+
+The supported modes, and the parameters they require, are as follows:
+
+"physical"
+  All existing and future revision files will use the traditional
+  physical addressing scheme.  All references are given as rev/offset
+  pairs with "offset" being the byte offset relative to the beginning of
+  the revision in the respective rev or pack file.
+
+"logical <first-revision-to-use-it>"
+  'first-revision-to-use-it' specifies the first revision to use logical
+  addressing, must coincide with the beginning of a shard and may be a
+  future revision.  All earlier revisions use physical addressing.  It is
+  illegal to use logical addressing on non-sharded repositories.
+
+
+Addressing modes
+----------------
+
+Two addressing modes are supported in format 7: physical and logical
+addressing.  Both use the same address format but apply a different
+interpretation to it.  Older formats only support physical addressing.
+
+All items are addressed using <rev> <item_index> pairs.  In physical
+addressing mode, item_index is the (ASCII decimal) number of bytes from
+the start of the revision file to the start of the respective item.  For
+non-packed files that is also the absolute file offset.  Revision pack
+files simply concatenate multiple rev files, i.e. the absolute file offset
+is determined as
+
+  absolute offset = rev offset taken from manifest + item_index
+  
+This simple addressing scheme makes it hard to change the location of
+any item since that may break references from later revisions.
+  
+Logical addressing uses an index file to translate the rev / item_index
+pairs into absolute file offsets.  There is one such index for every rev /
+pack file using logical addressing and both are created in sync.  That
+makes it possible to reorder items during pack file creation, particularly
+to mix items from different revisions.
+
+Some item_index values are pre-defined and apply to every revision:
+
+  0 ... not used / invalid
+  1 ... changed path list
+  2 ... root node revision
+
+A reverse index (phys-to-log) is being created as well that allows for
+translating arbitrary file locations into item descriptions (type, rev,
+item_index, on-disk length).  Known item types
+
+  0 ... unused / empty section
+  1 ... file representation
+  2 ... directory representation
+  3 ... file property representation
+  4 ... directory property representation
+  5 ... node revision
+  6 ... changed paths list
+
+The various representation types all share the same morphology.  The
+distinction is only made to allow for more effective reordering heuristics.
+Zero-length items are allowed.
+
+
 Packing revisions
 -----------------
 
 A filesystem can optionally be "packed" to conserve space on disk.  The
 packing process concatenates all the revision files in each full shard to
-create pack files.  A manifest file is also created for each shard which
+create a pack file.  The original shard is removed, and reads are
+redirected to the pack file.
+
+With physical addressing, a manifest file is created for each shard which
 records the indexes of the corresponding revision files in the pack file.
-In addition, the original shard is removed, and reads are redirected to the
-pack file.
+The manifest file consists of a list of offsets, one for each revision in
+the pack file.  The offsets are stored as ASCII decimal, and separated by
+a newline character.
+
+Revision pack files using logical addressing don't use manifest files but
+index files instead.  The revisions inside a pack file will also get
+interleaved to reduce I/O for typical access patterns.
 
-The manifest file consists of a list of offsets, one for each revision in the
-pack file.  The offsets are stored as ASCII decimal, and separated by a newline
-character.
 
 Packing revision properties (format 5: SQLite)
 ---------------------------
@@ -341,13 +423,12 @@ Within a new transaction:
 Within a revision:
 
   Within a revision file, node-revs have a txn-id field of the form
-  "r<rev>/<offset>", to support easy lookup. The <offset> is the (ASCII
-  decimal) number of bytes from the start of the revision file to the
-  start of the node-rev.
+  "r<rev>/<item_index>", to support easy lookup.  See addressing modes
+  for details.
 
   During the final phase of a commit, node-revision IDs are rewritten
   to have repository-wide unique node-ID and copy-ID fields, and to have
-  "r<rev>/<offset>" txn-id fields.
+  "r<rev>/<item_index>" txn-id fields.
 
   In Format 3 and above, this uniqueness is done by changing a temporary
   id of "_<base36>" to "<base36>-<rev>".  Note that this means that the
@@ -429,13 +510,13 @@ A revision file contains a concatenation
   * Text and property representations
   * Node-revisions
   * The changed-path data
-  * Two offsets at the very end
+  * Two offsets at the very end (physical addressing mode only)
 
 A representation begins with a line containing either "PLAIN\n" or
-"DELTA\n" or "DELTA <rev> <offset> <length>\n", where <rev>, <offset>,
-and <length> 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
+"DELTA\n" or "DELTA <rev> <item_index> <length>\n", where <rev>,
+<item_index>, and <length> 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".
 
@@ -459,9 +540,9 @@ defined:
   type      "file" or "dir"
   pred      The ID of the predecessor node-rev
   count     Count of node-revs since the base of the node
-  text      "<rev> <offset> <length> <size> <digest>" for text rep
-  props     "<rev> <offset> <length> <size> <digest>" for props rep
-            <rev> and <offset> give location of rep
+  text      "<rev> <item_index> <length> <size> <digest>" for text rep
+  props     "<rev> <item_index> <length> <size> <digest>" for props rep
+            <rev> and <item_index> give location of rep
             <length> gives length of rep, sans header and trailer
             <size> gives size of expanded rep; may be 0 if equal
              to the length
@@ -489,7 +570,7 @@ of the copy; it may be omitted if the no
 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.
+its location 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
@@ -507,10 +588,10 @@ Starting with FS format 4, <action> may 
 "dir") of the node, after a hyphen; for example, an added directory
 may be represented as "add-dir".
 
-At the very end of a rev file is a pair of lines containing
-"\n<root-offset> <cp-offset>\n", where <root-offset> is the offset of
-the root directory node revision and <cp-offset> is the offset of the
-changed-path data.
+In physical addressing mode, at the very end of a rev file is a pair of
+lines containing "\n<root-offset> <cp-offset>\n", where <root-offset> is
+the offset of the root directory node revision and <cp-offset> is the
+offset of the changed-path data.
 
 All numbers in the rev file format are unsigned and are represented as
 ASCII decimal.
@@ -533,7 +614,15 @@ In FS formats 1 and 2, it also contains:
   rev                        Prototype rev file with new text reps
   rev-lock                   Lockfile for writing to the above
 
-In newer formats, these files are in the txn-protorevs/ directory.
+(In newer formats, these files are in the txn-protorevs/ directory.)
+
+In format 7+ logical addressing mode, it contains two additional index
+files (see structure-indexes for a detailed description) and one more
+counter file:
+
+  itemidx                    Next item_index value as decimal integer
+  index.l2p                  Log-to-phys proto-index
+  index.p2l                  Phys-to-log proto-index
 
 The prototype rev file is used to store the text representations as
 they are received from the client.  To ensure that only one client is
@@ -545,7 +634,7 @@ file will always be present.  The "node.
 only be present if the node-rev properties have been changed.
 
 The <sha1> files have been introduced in FS format 6. Their content
-is that of text rep references: "<rev> <offset> <length> <size> <digest>"
+is that of text rep references: "<rev> <item_offset> <length> <size> <digest>"
 They will be written for text reps in the current transaction and be
 used to eliminate duplicate reps within that transaction.
 
@@ -619,3 +708,14 @@ reference the same path as above, but lo
 that file (instead of lock information).  Children are listed as MD5
 digests, too, so you would simply iterate over those digests and
 consult the files they reference for lock information.
+
+
+Index files
+-----------
+
+Format 7 introduces logical addressing that requires item indexes
+to be translated / mapped to physical rev / pack file offsets.
+
+Details of the binary format used by these index files can be
+found in structure-indexes.
+

Modified: subversion/trunk/subversion/libsvn_fs_fs/transaction.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/transaction.c?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/transaction.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/transaction.c Mon Dec  2 14:55:20 2013
@@ -32,6 +32,7 @@
 #include "svn_dirent_uri.h"
 
 #include "fs_fs.h"
+#include "index.h"
 #include "tree.h"
 #include "util.h"
 #include "id.h"
@@ -403,7 +404,8 @@ get_writable_proto_rev_body(svn_fs_t *fs
   /* Now open the prototype revision file and seek to the end. */
   err = svn_io_file_open(file,
                          svn_fs_fs__path_txn_proto_rev(fs, &b->txn_id, pool),
-                         APR_WRITE | APR_BUFFERED, APR_OS_DEFAULT, pool);
+                         APR_READ | APR_WRITE | APR_BUFFERED, APR_OS_DEFAULT,
+                         pool);
 
   /* You might expect that we could dispense with the following seek
      and achieve the same thing by opening the file using APR_APPEND.
@@ -1583,6 +1585,183 @@ svn_fs_fs__add_change(svn_fs_t *fs,
   return svn_io_file_close(file, pool);
 }
 
+/* If the transaction TXN_ID in FS uses logical addressing, store the
+ * (ITEM_INDEX, OFFSET) pair in the txn's log-to-phys proto index file.
+ * If FINAL_REVISION is not SVN_INVALID_REVNUM, use it to determine whether
+ * to actually write to the proto-index.  Use POOL for allocations.
+ */
+static svn_error_t *
+store_l2p_index_entry(svn_fs_t *fs,
+                      const svn_fs_fs__id_part_t *txn_id,
+                      svn_revnum_t final_revision,
+                      apr_off_t offset,
+                      apr_uint64_t item_index,
+                      apr_pool_t *pool)
+{
+  if (final_revision == SVN_INVALID_REVNUM)
+    final_revision = txn_id->revision + 1;
+
+  if (svn_fs_fs__use_log_addressing(fs, final_revision))
+    {
+      const char *path = svn_fs_fs__path_l2p_proto_index(fs, txn_id, pool);
+      apr_file_t *file;
+      SVN_ERR(svn_fs_fs__l2p_proto_index_open(&file, path, pool));
+      SVN_ERR(svn_fs_fs__l2p_proto_index_add_entry(file, offset,
+                                                   item_index, pool));
+      SVN_ERR(svn_io_file_close(file, pool));
+    }
+
+  return SVN_NO_ERROR;
+}
+
+/* If the transaction TXN_ID in FS uses logical addressing, store ENTRY
+ * in the phys-to-log proto index file of transaction TXN_ID.
+ * If FINAL_REVISION is not SVN_INVALID_REVNUM, use it to determine whether
+ * to actually write to the proto-index.  Use POOL for allocations.
+ */
+static svn_error_t *
+store_p2l_index_entry(svn_fs_t *fs,
+                      const svn_fs_fs__id_part_t *txn_id,
+                      svn_revnum_t final_revision,
+                      svn_fs_fs__p2l_entry_t *entry,
+                      apr_pool_t *pool)
+{
+  if (final_revision == SVN_INVALID_REVNUM)
+    final_revision = txn_id->revision + 1;
+
+  if (svn_fs_fs__use_log_addressing(fs, final_revision))
+    {
+      const char *path = svn_fs_fs__path_p2l_proto_index(fs, txn_id, pool);
+      apr_file_t *file;
+      SVN_ERR(svn_fs_fs__p2l_proto_index_open(&file, path, pool));
+      SVN_ERR(svn_fs_fs__p2l_proto_index_add_entry(file, entry, pool));
+      SVN_ERR(svn_io_file_close(file, pool));
+    }
+
+  return SVN_NO_ERROR;
+}
+
+/* Allocate an item index for the given MY_OFFSET in the transaction TXN_ID
+ * of file system FS and return it in *ITEM_INDEX.  For old formats, it
+ * will simply return the offset as item index; in new formats, it will
+ * increment the txn's item index counter file and store the mapping in
+ * the proto index file.  If FINAL_REVISION is not SVN_INVALID_REVNUM, use
+ * it to determine whether to actually write to the proto-index.
+ * Use POOL for allocations.
+ */
+static svn_error_t *
+allocate_item_index(apr_uint64_t *item_index,
+                    svn_fs_t *fs,
+                    const svn_fs_fs__id_part_t *txn_id,
+                    svn_revnum_t final_revision,
+                    apr_off_t my_offset,
+                    apr_pool_t *pool)
+{
+  if (final_revision == SVN_INVALID_REVNUM)
+    final_revision = txn_id->revision + 1;
+
+  if (svn_fs_fs__use_log_addressing(fs, final_revision))
+    {
+      apr_file_t *file;
+      char buffer[SVN_INT64_BUFFER_SIZE] = { 0 };
+      svn_boolean_t eof = FALSE;
+      apr_size_t to_write;
+      apr_size_t read;
+      apr_off_t offset = 0;
+
+      /* read number, increment it and write it back to disk */
+      SVN_ERR(svn_io_file_open(&file,
+                         svn_fs_fs__path_txn_item_index(fs, txn_id, pool),
+                         APR_READ | APR_WRITE | APR_CREATE | APR_BUFFERED,
+                         APR_OS_DEFAULT, pool));
+      SVN_ERR(svn_io_file_read_full2(file, buffer, sizeof(buffer)-1,
+                                     &read, &eof, pool));
+      if (read)
+        SVN_ERR(svn_cstring_atoui64(item_index, buffer));
+      else
+        *item_index = SVN_FS_FS__ITEM_INDEX_FIRST_USER;
+
+      to_write = svn__ui64toa(buffer, *item_index + 1);
+      SVN_ERR(svn_io_file_seek(file, SEEK_SET, &offset, pool));
+      SVN_ERR(svn_io_file_write_full(file, buffer, to_write, NULL, pool));
+      SVN_ERR(svn_io_file_close(file, pool));
+
+      /* write log-to-phys index */
+      SVN_ERR(store_l2p_index_entry(fs, txn_id, final_revision,
+                                    my_offset, *item_index, pool));
+    }
+  else
+    {
+      *item_index = (apr_uint64_t)my_offset;
+    }
+
+  return SVN_NO_ERROR;
+}
+
+/* Baton used by fnv1a_write_handler to calculate the FNV checksum
+ * before passing the data on to the INNER_STREAM.
+ */
+typedef struct fnv1a_stream_baton_t
+{
+  svn_stream_t *inner_stream;
+  svn_checksum_ctx_t *context;
+} fnv1a_stream_baton_t;
+
+/* Implement svn_write_fn_t.
+ * Update checksum and pass data on to inner stream.
+ */
+static svn_error_t *
+fnv1a_write_handler(void *baton,
+                    const char *data,
+                    apr_size_t *len)
+{
+  fnv1a_stream_baton_t *b = baton;
+
+  SVN_ERR(svn_checksum_update(b->context, data, *len));
+  SVN_ERR(svn_stream_write(b->inner_stream, data, len));
+
+  return SVN_NO_ERROR;
+}
+
+/* Return a stream that calculates a FNV checksum in *CONTEXT
+ * over all data written to the stream and passes that data on
+ * to INNER_STREAM.  Allocate objects in POOL.
+ */
+static svn_stream_t *
+fnv1a_wrap_stream(svn_checksum_ctx_t **context,
+                  svn_stream_t *inner_stream,
+                  apr_pool_t *pool)
+{
+  svn_stream_t *outer_stream;
+
+  fnv1a_stream_baton_t *baton = apr_pcalloc(pool, sizeof(*baton));
+  baton->inner_stream = inner_stream;
+  baton->context = svn_checksum_ctx_create(svn_checksum_fnv1a_32x4, pool);
+  *context = baton->context;
+
+  outer_stream = svn_stream_create(baton, pool);
+  svn_stream_set_write(outer_stream, fnv1a_write_handler);
+
+  return outer_stream;
+}
+
+/* Set *DIGEST to the FNV checksum calculated in CONTEXT.
+ * Use SCRATCH_POOL for temporary allocations.
+ */
+static svn_error_t *
+fnv1a_checksum_finalize(apr_uint32_t *digest,
+                        svn_checksum_ctx_t *context,
+                        apr_pool_t *scratch_pool)
+{
+  svn_checksum_t *checksum;
+
+  SVN_ERR(svn_checksum_final(&checksum, context, scratch_pool));
+  SVN_ERR_ASSERT(checksum->kind == svn_checksum_fnv1a_32x4);
+  *digest =  *(apr_uint32_t *)(checksum->digest);
+
+  return SVN_NO_ERROR;
+}
+
 /* This baton is used by the representation writing streams.  It keeps
    track of the checksum information as well as the total size of the
    representation so far. */
@@ -1619,6 +1798,9 @@ struct rep_write_baton
   svn_checksum_ctx_t *md5_checksum_ctx;
   svn_checksum_ctx_t *sha1_checksum_ctx;
 
+  /* calculate a modified FNV-1a checksum of the on-disk representation */
+  svn_checksum_ctx_t *fnv1a_checksum_ctx;
+
   apr_pool_t *pool;
 
   apr_pool_t *parent_pool;
@@ -1787,7 +1969,6 @@ rep_write_cleanup(void *data)
   return APR_SUCCESS;
 }
 
-
 /* Get a rep_write_baton and store it in *WB_P for the representation
    indicated by NODEREV in filesystem FS.  Perform allocations in
    POOL.  Only appropriate for file contents, not for props or
@@ -1825,7 +2006,10 @@ rep_write_get_baton(struct rep_write_bat
                                  b->pool));
 
   b->file = file;
-  b->rep_stream = svn_stream_from_aprfile2(file, TRUE, b->pool);
+  b->rep_stream = fnv1a_wrap_stream(&b->fnv1a_checksum_ctx,
+                                    svn_stream_from_aprfile2(file, TRUE,
+                                                             b->pool),
+                                    b->pool);
 
   SVN_ERR(svn_fs_fs__get_file_offset(&b->rep_offset, file, b->pool));
 
@@ -1837,7 +2021,7 @@ rep_write_get_baton(struct rep_write_bat
   if (base_rep)
     {
       header.base_revision = base_rep->revision;
-      header.base_offset = base_rep->offset;
+      header.base_item_index = base_rep->item_index;
       header.base_length = base_rep->size;
       header.type = svn_fs_fs__rep_delta;
     }
@@ -2003,7 +2187,6 @@ rep_write_contents_close(void *baton)
   apr_off_t offset;
 
   rep = apr_pcalloc(b->parent_pool, sizeof(*rep));
-  rep->offset = b->rep_offset;
 
   /* Close our delta stream so the last bits of svndiff are written
      out. */
@@ -2040,6 +2223,9 @@ rep_write_contents_close(void *baton)
     {
       /* Write out our cosmetic end marker. */
       SVN_ERR(svn_stream_puts(b->rep_stream, "ENDREP\n"));
+      SVN_ERR(allocate_item_index(&rep->item_index, b->fs, &rep->txn_id,
+                                  SVN_INVALID_REVNUM, b->rep_offset,
+                                  b->pool));
 
       b->noderev->data_rep = rep;
     }
@@ -2051,7 +2237,23 @@ rep_write_contents_close(void *baton)
   SVN_ERR(svn_fs_fs__put_node_revision(b->fs, b->noderev->id, b->noderev,
                                        FALSE, b->pool));
   if (!old_rep)
-    SVN_ERR(store_sha1_rep_mapping(b->fs, b->noderev, b->pool));
+    {
+      svn_fs_fs__p2l_entry_t entry;
+
+      entry.offset = b->rep_offset;
+      SVN_ERR(svn_fs_fs__get_file_offset(&offset, b->file, b->pool));
+      entry.size = offset - b->rep_offset;
+      entry.type = SVN_FS_FS__ITEM_TYPE_FILE_REP;
+      entry.item.revision = SVN_INVALID_REVNUM;
+      entry.item.number = rep->item_index;
+      SVN_ERR(fnv1a_checksum_finalize(&entry.fnv1_checksum,
+                                      b->fnv1a_checksum_ctx,
+                                      b->pool));
+
+      SVN_ERR(store_sha1_rep_mapping(b->fs, b->noderev, b->pool));
+      SVN_ERR(store_p2l_index_entry(b->fs, &rep->txn_id, SVN_INVALID_REVNUM,
+                                    &entry, b->pool));
+    }
 
   SVN_ERR(svn_io_file_close(b->file, b->pool));
   SVN_ERR(unlock_proto_rev(b->fs, &rep->txn_id, b->lockcookie, b->pool));
@@ -2236,21 +2438,27 @@ write_hash_handler(void *baton,
 
 /* Write out the hash HASH as a text representation to file FILE.  In
    the process, record position, the total size of the dump and MD5 as
-   well as SHA1 in REP.   If rep sharing has been enabled and REPS_HASH
+   well as SHA1 in REP.   Add the representation of type ITEM_TYPE to
+   the indexes if necessary.  If rep sharing has been enabled and REPS_HASH
    is not NULL, it will be used in addition to the on-disk cache to find
    earlier reps with the same content.  When such existing reps can be
    found, we will truncate the one just written from the file and return
-   the existing rep.  Perform temporary allocations in POOL. */
+   the existing rep.  If FINAL_REVISION is not SVN_INVALID_REVNUM, use it
+   to determine whether to write to the proto-index files.
+   Perform temporary allocations in POOL. */
 static svn_error_t *
 write_hash_rep(representation_t *rep,
                apr_file_t *file,
                apr_hash_t *hash,
                svn_fs_t *fs,
                apr_hash_t *reps_hash,
+               int item_type,
+               svn_revnum_t final_revision,
                apr_pool_t *pool)
 {
   svn_stream_t *stream;
   struct write_hash_baton *whb;
+  svn_checksum_ctx_t *fnv1a_checksum_ctx;
   representation_t *old_rep;
   apr_off_t offset = 0;
 
@@ -2258,7 +2466,9 @@ write_hash_rep(representation_t *rep,
 
   whb = apr_pcalloc(pool, sizeof(*whb));
 
-  whb->stream = svn_stream_from_aprfile2(file, TRUE, pool);
+  whb->stream = fnv1a_wrap_stream(&fnv1a_checksum_ctx,
+                                  svn_stream_from_aprfile2(file, TRUE, pool),
+                                  pool);
   whb->size = 0;
   whb->md5_ctx = svn_checksum_ctx_create(svn_checksum_md5, pool);
   whb->sha1_ctx = svn_checksum_ctx_create(svn_checksum_sha1, pool);
@@ -2287,10 +2497,26 @@ write_hash_rep(representation_t *rep,
     }
   else
     {
+      svn_fs_fs__p2l_entry_t entry;
+
       /* Write out our cosmetic end marker. */
       SVN_ERR(svn_stream_puts(whb->stream, "ENDREP\n"));
 
-      rep->offset = offset;
+      SVN_ERR(allocate_item_index(&rep->item_index, fs, &rep->txn_id,
+                                  final_revision, offset, pool));
+
+      entry.offset = offset;
+      SVN_ERR(svn_fs_fs__get_file_offset(&offset, file, pool));
+      entry.size = offset - entry.offset;
+      entry.type = item_type;
+      entry.item.revision = SVN_INVALID_REVNUM;
+      entry.item.number = rep->item_index;
+      SVN_ERR(fnv1a_checksum_finalize(&entry.fnv1_checksum,
+                                      fnv1a_checksum_ctx,
+                                      pool));
+
+      SVN_ERR(store_p2l_index_entry(fs, &rep->txn_id, final_revision,
+                                    &entry, pool));
 
       /* update the representation */
       rep->size = whb->size;
@@ -2302,12 +2528,16 @@ write_hash_rep(representation_t *rep,
 
 /* Write out the hash HASH pertaining to the NODEREV in FS as a deltified
    text representation to file FILE.  In the process, record the total size
-   and the md5 digest in REP.  If rep sharing has been enabled and REPS_HASH
+   and the md5 digest in REP and add the representation of type ITEM_TYPE
+   to the indexes if necessary.  If rep sharing has been enabled and REPS_HASH
    is not NULL, it will be used in addition to the on-disk cache to find
    earlier reps with the same content.  When such existing reps can be found,
    we will truncate the one just written from the file and return the existing
-   rep.  If IS_PROPS is set, assume that we want to a props representation as
-   the base for our delta.  Perform temporary allocations in POOL. */
+   rep.  If ITEM_TYPE is IS_PROPS equals SVN_FS_FS__ITEM_TYPE_*_PROPS, assume
+   that we want to a props representation as the base for our delta.
+   If FINAL_REVISION is not SVN_INVALID_REVNUM, use it to determine whether
+   to write to the proto-index files.  Perform temporary allocations in POOL.
+ */
 static svn_error_t *
 write_hash_delta_rep(representation_t *rep,
                      apr_file_t *file,
@@ -2315,7 +2545,8 @@ write_hash_delta_rep(representation_t *r
                      svn_fs_t *fs,
                      node_revision_t *noderev,
                      apr_hash_t *reps_hash,
-                     svn_boolean_t is_props,
+                     int item_type,
+                     svn_revnum_t final_revision,
                      apr_pool_t *pool)
 {
   svn_txdelta_window_handler_t diff_wh;
@@ -2325,6 +2556,7 @@ write_hash_delta_rep(representation_t *r
   svn_stream_t *stream;
   representation_t *base_rep;
   representation_t *old_rep;
+  svn_checksum_ctx_t *fnv1a_checksum_ctx;
   svn_stream_t *source;
   svn_fs_fs__rep_header_t header = { 0 };
 
@@ -2335,6 +2567,8 @@ write_hash_delta_rep(representation_t *r
   struct write_hash_baton *whb;
   fs_fs_data_t *ffd = fs->fsap_data;
   int diff_version = ffd->format >= SVN_FS_FS__MIN_SVNDIFF1_FORMAT ? 1 : 0;
+  svn_boolean_t is_props = (item_type == SVN_FS_FS__ITEM_TYPE_FILE_PROPS)
+                        || (item_type == SVN_FS_FS__ITEM_TYPE_DIR_PROPS);
 
   /* Get the base for this delta. */
   SVN_ERR(choose_delta_base(&base_rep, fs, noderev, is_props, pool));
@@ -2346,7 +2580,7 @@ write_hash_delta_rep(representation_t *r
   if (base_rep)
     {
       header.base_revision = base_rep->revision;
-      header.base_offset = base_rep->offset;
+      header.base_item_index = base_rep->item_index;
       header.base_length = base_rep->size;
       header.type = svn_fs_fs__rep_delta;
     }
@@ -2355,7 +2589,9 @@ write_hash_delta_rep(representation_t *r
       header.type = svn_fs_fs__rep_self_delta;
     }
 
-  file_stream = svn_stream_from_aprfile2(file, TRUE, pool);
+  file_stream = fnv1a_wrap_stream(&fnv1a_checksum_ctx,
+                                  svn_stream_from_aprfile2(file, TRUE, pool),
+                                  pool);
   SVN_ERR(svn_fs_fs__write_rep_header(&header, file_stream, pool));
   SVN_ERR(svn_fs_fs__get_file_offset(&delta_start, file, pool));
 
@@ -2397,11 +2633,27 @@ write_hash_delta_rep(representation_t *r
     }
   else
     {
+      svn_fs_fs__p2l_entry_t entry;
+
       /* Write out our cosmetic end marker. */
       SVN_ERR(svn_fs_fs__get_file_offset(&rep_end, file, pool));
       SVN_ERR(svn_stream_puts(file_stream, "ENDREP\n"));
 
-      rep->offset = offset;
+      SVN_ERR(allocate_item_index(&rep->item_index, fs, &rep->txn_id,
+                                  final_revision, offset, pool));
+
+      entry.offset = offset;
+      SVN_ERR(svn_fs_fs__get_file_offset(&offset, file, pool));
+      entry.size = offset - entry.offset;
+      entry.type = item_type;
+      entry.item.revision = SVN_INVALID_REVNUM;
+      entry.item.number = rep->item_index;
+      SVN_ERR(fnv1a_checksum_finalize(&entry.fnv1_checksum,
+                                      fnv1a_checksum_ctx,
+                                      pool));
+
+      SVN_ERR(store_p2l_index_entry(fs, &rep->txn_id, final_revision,
+                                    &entry, pool));
 
       /* update the representation */
       rep->expanded_size = whb->size;
@@ -2540,8 +2792,12 @@ write_final_rev(const svn_fs_id_t **new_
   node_revision_t *noderev;
   apr_off_t my_offset;
   const svn_fs_id_t *new_id;
-  svn_fs_fs__id_part_t node_id, copy_id, rev_offset;
+  svn_fs_fs__id_part_t node_id, copy_id, rev_item;
   fs_fs_data_t *ffd = fs->fsap_data;
+  const svn_fs_fs__id_part_t *txn_id = svn_fs_fs__id_txn_id(id);
+  svn_stream_t *file_stream;
+  svn_checksum_ctx_t *fnv1a_checksum_ctx;
+
   *new_id_p = NULL;
 
   /* Check to see if this is a transaction node. */
@@ -2587,16 +2843,19 @@ write_final_rev(const svn_fs_id_t **new_
           /* Write out the contents of this directory as a text rep. */
           SVN_ERR(unparse_dir_entries(&str_entries, entries, pool));
 
-          reset_txn_in_rep(noderev->data_rep);
           noderev->data_rep->revision = rev;
 
           if (ffd->deltify_directories)
             SVN_ERR(write_hash_delta_rep(noderev->data_rep, file,
                                          str_entries, fs, noderev, NULL,
-                                         FALSE, pool));
+                                         SVN_FS_FS__ITEM_TYPE_DIR_REP,
+                                         rev, pool));
           else
             SVN_ERR(write_hash_rep(noderev->data_rep, file, str_entries,
-                                   fs, NULL, pool));
+                                   fs, NULL, SVN_FS_FS__ITEM_TYPE_DIR_REP,
+                                   rev, pool));
+
+          reset_txn_in_rep(noderev->data_rep);
         }
     }
   else
@@ -2610,13 +2869,16 @@ write_final_rev(const svn_fs_id_t **new_
           reset_txn_in_rep(noderev->data_rep);
           noderev->data_rep->revision = rev;
 
-          /* See issue 3845.  Some unknown mechanism caused the
-             protorev file to get truncated, so check for that
-             here.  */
-          if (noderev->data_rep->offset + noderev->data_rep->size
-              > initial_offset)
-            return svn_error_create(SVN_ERR_FS_CORRUPT, NULL,
-                                    _("Truncated protorev file detected"));
+          if (!svn_fs_fs__use_log_addressing(fs, rev))
+            {
+              /* See issue 3845.  Some unknown mechanism caused the
+                 protorev file to get truncated, so check for that
+                 here.  */
+              if (noderev->data_rep->item_index + noderev->data_rep->size
+                  > initial_offset)
+                return svn_error_create(SVN_ERR_FS_CORRUPT, NULL,
+                                        _("Truncated protorev file detected"));
+            }
         }
     }
 
@@ -2624,18 +2886,22 @@ write_final_rev(const svn_fs_id_t **new_
   if (noderev->prop_rep && is_txn_rep(noderev->prop_rep))
     {
       apr_hash_t *proplist;
+      int item_type = noderev->kind == svn_node_dir
+                    ? SVN_FS_FS__ITEM_TYPE_DIR_PROPS
+                    : SVN_FS_FS__ITEM_TYPE_FILE_PROPS;
       SVN_ERR(svn_fs_fs__get_proplist(&proplist, fs, noderev, pool));
 
-      reset_txn_in_rep(noderev->prop_rep);
       noderev->prop_rep->revision = rev;
 
       if (ffd->deltify_properties)
         SVN_ERR(write_hash_delta_rep(noderev->prop_rep, file,
                                      proplist, fs, noderev, reps_hash,
-                                     TRUE, pool));
+                                     item_type, rev, pool));
       else
         SVN_ERR(write_hash_rep(noderev->prop_rep, file, proplist,
-                               fs, reps_hash, pool));
+                               fs, reps_hash, item_type, rev, pool));
+
+      reset_txn_in_rep(noderev->prop_rep);
     }
 
   /* Convert our temporary ID into a permanent revision one. */
@@ -2647,11 +2913,21 @@ write_final_rev(const svn_fs_id_t **new_
   if (noderev->copyroot_rev == SVN_INVALID_REVNUM)
     noderev->copyroot_rev = rev;
 
+  /* root nodes have a fixed ID in log addressing mode */
   SVN_ERR(svn_fs_fs__get_file_offset(&my_offset, file, pool));
-  rev_offset.number = my_offset;
+  if (svn_fs_fs__use_log_addressing(fs, rev) && at_root)
+    {
+      /* reference the root noderev from the log-to-phys index */
+      rev_item.number = SVN_FS_FS__ITEM_INDEX_ROOT_NODE;
+      SVN_ERR(store_l2p_index_entry(fs, txn_id, rev, my_offset,
+                                    rev_item.number, pool));
+    }
+  else
+    SVN_ERR(allocate_item_index(&rev_item.number, fs, txn_id, rev,
+                                my_offset, pool));
 
-  rev_offset.revision = rev;
-  new_id = svn_fs_fs__id_rev_create(&node_id, &copy_id, &rev_offset, pool);
+  rev_item.revision = rev;
+  new_id = svn_fs_fs__id_rev_create(&node_id, &copy_id, &rev_item, pool);
 
   noderev->id = new_id;
 
@@ -2697,30 +2973,54 @@ write_final_rev(const svn_fs_id_t **new_
   if (at_root)
     SVN_ERR(validate_root_noderev(fs, noderev, rev, pool));
 
-  SVN_ERR(svn_fs_fs__write_noderev(svn_stream_from_aprfile2(file, TRUE, pool),
-                                   noderev, ffd->format,
+  file_stream = fnv1a_wrap_stream(&fnv1a_checksum_ctx,
+                                  svn_stream_from_aprfile2(file, TRUE, pool),
+                                  pool);
+  SVN_ERR(svn_fs_fs__write_noderev(file_stream, noderev, ffd->format,
                                    svn_fs_fs__fs_supports_mergeinfo(fs),
                                    pool));
 
+  /* reference the root noderev from the log-to-phys index */
+  if (svn_fs_fs__use_log_addressing(fs, rev))
+    {
+      svn_fs_fs__p2l_entry_t entry;
+      rev_item.revision = SVN_INVALID_REVNUM;
+
+      entry.offset = my_offset;
+      SVN_ERR(svn_fs_fs__get_file_offset(&my_offset, file, pool));
+      entry.size = my_offset - entry.offset;
+      entry.type = SVN_FS_FS__ITEM_TYPE_NODEREV;
+      entry.item = rev_item;
+      SVN_ERR(fnv1a_checksum_finalize(&entry.fnv1_checksum,
+                                      fnv1a_checksum_ctx,
+                                      pool));
+
+      SVN_ERR(store_p2l_index_entry(fs, txn_id, rev, &entry, pool));
+    }
+
   /* Return our ID that references the revision file. */
   *new_id_p = noderev->id;
 
   return SVN_NO_ERROR;
 }
 
-/* Write the changed path info CHANGED_PATHS to the permanent rev-file FILE
-   representing NEW_REV in filesystem FS.  *OFFSET_P is set the to offset in
-   the file of the beginning of this information.
+/* Write the changed path info CHANGED_PATHS from transaction TXN_ID to the
+   permanent rev-file FILE representing NEW_REV in filesystem FS.  *OFFSET_P
+   is set the to offset in the file of the beginning of this information.
+   NEW_REV is the revision currently being committed.
    Perform temporary allocations in POOL. */
 static svn_error_t *
 write_final_changed_path_info(apr_off_t *offset_p,
                               apr_file_t *file,
                               svn_fs_t *fs,
+                              const svn_fs_fs__id_part_t *txn_id,
                               apr_hash_t *changed_paths,
                               svn_revnum_t new_rev,
                               apr_pool_t *pool)
 {
   apr_off_t offset;
+  svn_stream_t *stream;
+  svn_checksum_ctx_t *fnv1a_checksum_ctx;
   apr_hash_index_t *hi;
 
   SVN_ERR(svn_fs_fs__get_file_offset(&offset, file, pool));
@@ -2740,11 +3040,34 @@ write_final_changed_path_info(apr_off_t 
         }
     }
 
-  SVN_ERR(svn_fs_fs__write_changes(svn_stream_from_aprfile2(file, TRUE, pool),
-                                   fs, changed_paths, TRUE, pool));
+  /* write to target file & calculate checksum */
+  stream = fnv1a_wrap_stream(&fnv1a_checksum_ctx,
+                             svn_stream_from_aprfile2(file, TRUE, pool),
+                             pool);
+  SVN_ERR(svn_fs_fs__write_changes(stream, fs, changed_paths, TRUE, pool));
 
   *offset_p = offset;
 
+  /* reference changes from the indexes */
+  if (svn_fs_fs__use_log_addressing(fs, new_rev))
+    {
+      svn_fs_fs__p2l_entry_t entry;
+
+      entry.offset = offset;
+      SVN_ERR(svn_fs_fs__get_file_offset(&offset, file, pool));
+      entry.size = offset - entry.offset;
+      entry.type = SVN_FS_FS__ITEM_TYPE_CHANGES;
+      entry.item.revision = SVN_INVALID_REVNUM;
+      entry.item.number = SVN_FS_FS__ITEM_INDEX_CHANGES;
+      SVN_ERR(fnv1a_checksum_finalize(&entry.fnv1_checksum,
+                                      fnv1a_checksum_ctx,
+                                      pool));
+
+      SVN_ERR(store_p2l_index_entry(fs, txn_id, new_rev, &entry, pool));
+      SVN_ERR(store_l2p_index_entry(fs, txn_id, new_rev, entry.offset,
+                                    SVN_FS_FS__ITEM_INDEX_CHANGES, pool));
+    }
+
   return SVN_NO_ERROR;
 }
 
@@ -3061,6 +3384,242 @@ verify_moves(svn_fs_t *fs,
   return SVN_NO_ERROR;
 }
 
+/* Return TRUE, if transaction TXN_ID in FS definitively uses logical
+ * addressing mode.  Use POOL for temporary allocations.
+ */
+static svn_boolean_t
+using_log_addressing(svn_fs_t *fs,
+                     const svn_fs_fs__id_part_t *txn_id,
+                     apr_pool_t *pool)
+{
+  /* As long as we don't write new data representations, we won't allocate
+     IDs and there is no difference between log & phys mode.
+
+     After the first ID got allocated, it is logical mode and the proto-
+     index file does exist.
+   */
+  svn_node_kind_t kind;
+  const char *path = svn_fs_fs__path_l2p_proto_index(fs, txn_id, pool);
+
+  svn_error_t *err = svn_io_check_path(path, &kind, pool);
+  if (err)
+    {
+      /* We couldn't check for the presence of the index file.
+
+         So, we probably won't be able to access it during later stages
+         of the commit.
+       */
+      svn_error_clear(err);
+      return FALSE;
+    }
+
+  return kind == svn_node_file;
+}
+
+/* Return TRUE, if the file with FILENAME contains a node revision.
+ */
+static svn_boolean_t
+is_noderev_file(const char *filename)
+{
+  apr_size_t dot_count = 0;
+
+  /* all interesting files start with "node." */
+  if (strncmp(filename, PATH_PREFIX_NODE, strlen(PATH_PREFIX_NODE)))
+    return FALSE;
+
+  for (; *filename; ++filename)
+    if (*filename == '.')
+      ++dot_count;
+
+  return dot_count == 2;
+}
+
+/* Determine the checksum for the SIZE bytes of data starting at START
+ * in FILE and return the result in *FNV1_CHECKSUM.
+ * Use POOL for tempoary allocations.
+ */
+static svn_error_t *
+fnv1a_checksum_on_file_range(apr_uint32_t *fnv1_checksum,
+                             apr_file_t *file,
+                             apr_off_t start,
+                             apr_off_t size,
+                             apr_pool_t *pool)
+{
+  char buffer[4096];
+
+  svn_checksum_ctx_t *checksum_ctx
+    = svn_checksum_ctx_create(svn_checksum_fnv1a_32x4, pool);
+
+  SVN_ERR(svn_io_file_seek(file, APR_SET, &start, pool));
+  while (size > 0)
+    {
+      apr_size_t to_read = MIN(size, sizeof(buffer));
+
+      SVN_ERR(svn_io_file_read_full2(file, buffer, to_read, &to_read,
+                                     NULL, pool));
+      SVN_ERR(svn_checksum_update(checksum_ctx, buffer, to_read));
+      size -= to_read;
+    }
+  SVN_ERR(fnv1a_checksum_finalize(fnv1_checksum, checksum_ctx, pool));
+
+  return SVN_NO_ERROR;
+}
+
+/* qsort()-compatible comparision function sorting svn_fs_fs__p2l_entry_t
+ * by offset.
+ */
+static int
+compare_sort_p2l_entry(const void *a,
+                       const void *b)
+{
+  apr_off_t lhs = ((const svn_fs_fs__p2l_entry_t *)a)->offset;
+  apr_off_t rhs = ((const svn_fs_fs__p2l_entry_t *)b)->offset;
+
+  return lhs < rhs ? -1 : rhs == lhs ? 0 : 1;
+}
+
+
+/* Upgrade the transaction TXN_ID in FS from physical addressing mode
+ * to logical addressing mode.  FINAL_REVISION is the revision that this
+ * txn is being committed to.  Use POOL for temporary allocations.
+ */
+static svn_error_t *
+upgrade_transaction(svn_fs_t *fs,
+                    const svn_fs_fs__id_part_t *txn_id,
+                    svn_revnum_t final_revision,
+                    apr_file_t *proto_file,
+                    apr_pool_t *pool)
+{
+  fs_fs_data_t *ffd = fs->fsap_data;
+  apr_hash_t *dirents;
+  int i;
+  apr_hash_index_t* hi;
+
+  /* we allocate large temporary data and want to release it asap */
+
+  apr_pool_t *subpool = svn_pool_create(pool);
+  apr_pool_t *iterpool = svn_pool_create(pool);
+
+  apr_hash_t *id_map = apr_hash_make(subpool);
+  const char *txn_dir = svn_fs_fs__path_txn_dir(fs, txn_id, subpool);
+  apr_array_header_t *p2l_entries
+    = apr_array_make(subpool, 16, sizeof(svn_fs_fs__p2l_entry_t));
+
+  /* scan the txn directory for noderev files and patch them up */
+
+  SVN_ERR(svn_io_get_dirents3(&dirents, txn_dir, TRUE, subpool, iterpool));
+  for (hi = apr_hash_first(subpool, dirents); hi; hi = apr_hash_next(hi))
+    {
+      apr_file_t *file;
+      const char *filename;
+      node_revision_t *noderev;
+      svn_stream_t *stream;
+      const char *name;
+      apr_uint64_t *old_index, *item_index, *new_index;
+
+      svn_pool_clear(iterpool);
+
+      /* We are only interested in file data reps of this txns.
+         Older IDs remain valid because they are already committed.
+         Other IDs (noderevs and their usage in directories) will only be
+         assigned later anyways. */
+
+      name = svn__apr_hash_index_key(hi);
+      if (!is_noderev_file(name))
+        continue;
+
+      filename = svn_dirent_join(txn_dir, name, iterpool);
+      SVN_ERR(svn_io_file_open(&file, filename,
+                               APR_READ | APR_WRITE | APR_BUFFERED,
+                               APR_OS_DEFAULT,
+                               iterpool));
+      stream = svn_stream_from_aprfile2(file, TRUE, iterpool);
+      SVN_ERR(svn_fs_fs__read_noderev(&noderev, stream, iterpool));
+      if (   noderev->data_rep == NULL
+          || noderev->data_rep->revision != SVN_INVALID_REVNUM
+          || noderev->kind != svn_node_file)
+        continue;
+
+      /* We need to assign an id.
+         We might already have one because of rep sharing. */
+
+      item_index = &noderev->data_rep->item_index;
+      new_index = apr_hash_get(id_map, item_index, sizeof(*item_index));
+
+      if (new_index)
+        {
+          *item_index = *new_index;
+        }
+      else
+        {
+          svn_fs_fs__rep_header_t *header;
+          svn_fs_fs__p2l_entry_t *entry;
+
+          /* assign a logical ID and write the L2P proto-index */
+
+          old_index = apr_pmemdup(subpool, item_index, sizeof(*item_index));
+          SVN_ERR(allocate_item_index(item_index, fs, txn_id, final_revision,
+                                      *old_index, iterpool));
+
+          new_index = apr_pmemdup(subpool, item_index, sizeof(*item_index));
+          apr_hash_set(id_map, old_index, sizeof(*old_index), new_index);
+
+          /* we need to know the length of the representation header
+             because it is not accounted for by the representation length */
+
+          entry = apr_array_push(p2l_entries);
+          entry->offset = *old_index;
+          SVN_ERR(svn_io_file_seek(proto_file, APR_SET, &entry->offset,
+                                   iterpool));
+          SVN_ERR(svn_fs_fs__read_rep_header(&header,
+                    svn_stream_from_aprfile2(proto_file, TRUE, iterpool),
+                    iterpool));
+
+          /* Create the corresponding entry for the P2L proto-index.
+
+             We need to write that proto-index in strict offset order but
+             we have no control over the order in which we traverse the
+             data reps.   Thus, we collect the entries in an array. */
+
+          entry->size = noderev->data_rep->size + header->header_size + 7;
+                        /* 7 for the "ENDREP\n" */
+          entry->type = SVN_FS_FS__ITEM_TYPE_FILE_REP;
+          entry->item.revision = SVN_INVALID_REVNUM;
+          entry->item.number = *new_index;
+          SVN_ERR(fnv1a_checksum_on_file_range(&entry->fnv1_checksum,
+                                               proto_file,
+                                               entry->offset, entry->size,
+                                               iterpool));
+        }
+
+      /* write the updated noderev to disk */
+
+      SVN_ERR(svn_io_file_trunc(file, 0, iterpool));
+      SVN_ERR(svn_fs_fs__write_noderev(stream, noderev, ffd->format,
+                                       TRUE, iterpool));
+    }
+
+  /* Finally, write all P2L proto-index entries ordered by item offset. */
+
+  qsort(p2l_entries->elts, p2l_entries->nelts, p2l_entries->elt_size,
+        compare_sort_p2l_entry);
+  for (i = 0; i < p2l_entries->nelts; ++i)
+    {
+      svn_fs_fs__p2l_entry_t *entry;
+
+      svn_pool_clear(iterpool);
+
+      entry = &APR_ARRAY_IDX(p2l_entries, i, svn_fs_fs__p2l_entry_t);
+      SVN_ERR(store_p2l_index_entry(fs, txn_id, final_revision,
+                                    entry, iterpool));
+    }
+
+  svn_pool_clear(iterpool);
+  svn_pool_clear(subpool);
+
+  return SVN_NO_ERROR;
+}
+
 /* Baton used for commit_body below. */
 struct commit_baton {
   svn_revnum_t *new_rev_p;
@@ -3093,7 +3652,6 @@ commit_body(void *baton, apr_pool_t *poo
   apr_array_header_t *txnprop_list;
   svn_prop_t prop;
   const svn_fs_fs__id_part_t *txn_id = svn_fs_fs__txn_get_id(cb->txn);
-  svn_stringbuf_t *trailer;
   apr_hash_t *changed_paths;
 
   /* Get the current youngest revision. */
@@ -3134,6 +3692,18 @@ commit_body(void *baton, apr_pool_t *poo
                                  cb->fs, txn_id, pool));
   SVN_ERR(svn_fs_fs__get_file_offset(&initial_offset, proto_file, pool));
 
+  /* Make sure that we don't try to commit an old txn that used physical
+     addressing but will be committed into the revision range that requires
+     logical addressing.
+     */
+  if (svn_fs_fs__use_log_addressing(cb->fs, new_rev)
+      && !svn_fs_fs__use_log_addressing(cb->fs, txn_id->revision)
+      && !using_log_addressing(cb->fs, txn_id, pool))
+    {
+      SVN_ERR(upgrade_transaction(cb->fs, txn_id, new_rev, proto_file, pool));
+      SVN_ERR(svn_io_file_seek(proto_file, APR_SET, &initial_offset, pool));
+    }
+
   /* Write out all the node-revisions and directory contents. */
   root_id = svn_fs_fs__id_txn_create_root(txn_id, pool);
   SVN_ERR(write_final_rev(&new_root_id, proto_file, new_rev, cb->fs, root_id,
@@ -3143,16 +3713,21 @@ commit_body(void *baton, apr_pool_t *poo
 
   /* Write the changed-path information. */
   SVN_ERR(write_final_changed_path_info(&changed_path_offset, proto_file,
-                                        cb->fs, changed_paths, new_rev,
-                                        pool));
+                                        cb->fs, txn_id, changed_paths,
+                                        new_rev, pool));
 
-  /* Write the final line. */
-  trailer = svn_fs_fs__unparse_revision_trailer
-               (svn_fs_fs__id_offset(new_root_id),
-                changed_path_offset,
-                pool);
-  SVN_ERR(svn_io_file_write_full(proto_file, trailer->data, trailer->len,
-                                 NULL, pool));
+  if (!svn_fs_fs__use_log_addressing(cb->fs, new_rev))
+    {
+      /* Write the final line. */
+
+      svn_stringbuf_t *trailer
+        = svn_fs_fs__unparse_revision_trailer
+                  ((apr_off_t)svn_fs_fs__id_item(new_root_id),
+                   changed_path_offset,
+                   pool);
+      SVN_ERR(svn_io_file_write_full(proto_file, trailer->data, trailer->len,
+                                     NULL, pool));
+    }
 
   SVN_ERR(svn_io_file_flush_to_disk(proto_file, pool));
   SVN_ERR(svn_io_file_close(proto_file, pool));
@@ -3222,6 +3797,20 @@ commit_body(void *baton, apr_pool_t *poo
         }
     }
 
+  if (svn_fs_fs__use_log_addressing(cb->fs, new_rev))
+    {
+      /* Convert the index files from the proto format into their form
+         in their final location */
+      SVN_ERR(svn_fs_fs__l2p_index_create(cb->fs,
+                      svn_fs_fs__path_l2p_index(cb->fs, new_rev, FALSE, pool),
+                      svn_fs_fs__path_l2p_proto_index(cb->fs, txn_id, pool),
+                      new_rev, pool));
+      SVN_ERR(svn_fs_fs__p2l_index_create(cb->fs,
+                      svn_fs_fs__path_p2l_index(cb->fs, new_rev, FALSE, pool),
+                      svn_fs_fs__path_p2l_proto_index(cb->fs, txn_id, pool),
+                      new_rev, pool));
+    }
+
   /* Move the finished rev file into place.
 
      ### This "breaks" the transaction by removing the protorev file

Modified: subversion/trunk/subversion/libsvn_fs_fs/tree.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/tree.c?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/tree.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/tree.c Mon Dec  2 14:55:20 2013
@@ -2248,7 +2248,10 @@ fs_dir_optimal_order(apr_array_header_t 
                      apr_hash_t *entries,
                      apr_pool_t *pool)
 {
-  *ordered_p = svn_fs_fs__order_dir_entries(root->fs, entries, pool);
+  *ordered_p
+    = svn_fs_fs__order_dir_entries(root->fs, entries,
+                                   root->rev,
+                                   pool);
 
   return SVN_NO_ERROR;
 }

Modified: subversion/trunk/subversion/libsvn_fs_fs/util.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/util.c?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/util.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/util.c Mon Dec  2 14:55:20 2013
@@ -131,17 +131,51 @@ svn_fs_fs__path_rev(svn_fs_t *fs, svn_re
                               apr_psprintf(pool, "%ld", rev), SVN_VA_NULL);
 }
 
+/* Set *PATH to the path of REV in FS with PACKED selecting whether the
+   (potential) pack file or single revision file name is returned.
+   Allocate *PATH in POOL.
+*/
+static const char *
+path_rev_absolute_internal(svn_fs_t *fs,
+                           svn_revnum_t rev,
+                           svn_boolean_t packed,
+                           apr_pool_t *pool)
+{
+  return packed
+       ? svn_fs_fs__path_rev_packed(fs, rev, PATH_PACKED, pool)
+       : svn_fs_fs__path_rev(fs, rev, pool);
+}
+
+const char *
+svn_fs_fs__path_l2p_index(svn_fs_t *fs,
+                          svn_revnum_t rev,
+                          svn_boolean_t packed,
+                          apr_pool_t *pool)
+{
+  return apr_psprintf(pool, "%s" PATH_EXT_L2P_INDEX,
+                      path_rev_absolute_internal(fs, rev, packed, pool));
+}
+
+const char *
+svn_fs_fs__path_p2l_index(svn_fs_t *fs,
+                          svn_revnum_t rev,
+                          svn_boolean_t packed,
+                          apr_pool_t *pool)
+{
+  return apr_psprintf(pool, "%s" PATH_EXT_P2L_INDEX,
+                      path_rev_absolute_internal(fs, rev, packed, pool));
+}
+
 const char *
 svn_fs_fs__path_rev_absolute(svn_fs_t *fs,
                              svn_revnum_t rev,
                              apr_pool_t *pool)
 {
   fs_fs_data_t *ffd = fs->fsap_data;
+  svn_boolean_t is_packed = ffd->format >= SVN_FS_FS__MIN_PACKED_FORMAT
+                         && svn_fs_fs__is_packed_rev(fs, rev);
 
-  return (   ffd->format < SVN_FS_FS__MIN_PACKED_FORMAT
-          || ! svn_fs_fs__is_packed_rev(fs, rev))
-       ? svn_fs_fs__path_rev(fs, rev, pool)
-       : svn_fs_fs__path_rev_packed(fs, rev, PATH_PACKED, pool);
+  return path_rev_absolute_internal(fs, rev, is_packed, pool);
 }
 
 const char *
@@ -214,6 +248,33 @@ svn_fs_fs__path_txn_dir(svn_fs_t *fs,
                               SVN_VA_NULL);
 }
 
+const char*
+svn_fs_fs__path_l2p_proto_index(svn_fs_t *fs,
+                                const svn_fs_fs__id_part_t *txn_id,
+                                apr_pool_t *pool)
+{
+  return svn_dirent_join(svn_fs_fs__path_txn_dir(fs, txn_id, pool),
+                         PATH_INDEX PATH_EXT_L2P_INDEX, pool);
+}
+
+const char*
+svn_fs_fs__path_p2l_proto_index(svn_fs_t *fs,
+                                const svn_fs_fs__id_part_t *txn_id,
+                                apr_pool_t *pool)
+{
+  return svn_dirent_join(svn_fs_fs__path_txn_dir(fs, txn_id, pool),
+                         PATH_INDEX PATH_EXT_P2L_INDEX, pool);
+}
+
+const char *
+svn_fs_fs__path_txn_item_index(svn_fs_t *fs,
+                               const svn_fs_fs__id_part_t *txn_id,
+                               apr_pool_t *pool)
+{
+  return svn_dirent_join(svn_fs_fs__path_txn_dir(fs, txn_id, pool),
+                         PATH_TXN_ITEM_INDEX, pool);
+}
+
 const char *
 svn_fs_fs__path_txn_proto_rev(svn_fs_t *fs,
                               const svn_fs_fs__id_part_t *txn_id,
@@ -230,6 +291,7 @@ svn_fs_fs__path_txn_proto_rev(svn_fs_t *
                            PATH_REV, pool);
 }
 
+
 const char *
 svn_fs_fs__path_txn_proto_rev_lock(svn_fs_t *fs,
                                    const svn_fs_fs__id_part_t *txn_id,
@@ -567,77 +629,13 @@ svn_fs_fs__move_into_place(const char *o
   return SVN_NO_ERROR;
 }
 
-svn_error_t *
-svn_fs_fs__open_pack_or_rev_file(apr_file_t **file,
-                                 svn_fs_t *fs,
-                                 svn_revnum_t rev,
-                                 apr_pool_t *pool)
+svn_boolean_t
+svn_fs_fs__use_log_addressing(svn_fs_t *fs,
+                              svn_revnum_t rev)
 {
   fs_fs_data_t *ffd = fs->fsap_data;
-  svn_error_t *err;
-  svn_boolean_t retry = FALSE;
-
-  do
-    {
-      const char *path = svn_fs_fs__path_rev_absolute(fs, rev, pool);
-
-      /* open the revision file in buffered r/o mode */
-      err = svn_io_file_open(file, path,
-                            APR_READ | APR_BUFFERED, APR_OS_DEFAULT, pool);
-      if (err && APR_STATUS_IS_ENOENT(err->apr_err))
-        {
-          if (ffd->format >= SVN_FS_FS__MIN_PACKED_FORMAT)
-            {
-              /* Could not open the file. This may happen if the
-               * file once existed but got packed later. */
-              svn_error_clear(err);
-
-              /* if that was our 2nd attempt, leave it at that. */
-              if (retry)
-                return svn_error_createf(SVN_ERR_FS_NO_SUCH_REVISION, NULL,
-                                         _("No such revision %ld"), rev);
-
-              /* We failed for the first time. Refresh cache & retry. */
-              SVN_ERR(svn_fs_fs__update_min_unpacked_rev(fs, pool));
-
-              retry = TRUE;
-            }
-          else
-            {
-              svn_error_clear(err);
-              return svn_error_createf(SVN_ERR_FS_NO_SUCH_REVISION, NULL,
-                                       _("No such revision %ld"), rev);
-            }
-        }
-      else
-        {
-          retry = FALSE;
-        }
-    }
-  while (retry);
-
-  return svn_error_trace(err);
-}
-
-svn_error_t *
-svn_fs_fs__item_offset(apr_off_t *absolute_position,
-                       svn_fs_t *fs,
-                       svn_revnum_t rev,
-                       apr_off_t offset,
-                       apr_pool_t *pool)
-{
-  if (svn_fs_fs__is_packed_rev(fs, rev))
-    {
-      apr_off_t rev_offset;
-      SVN_ERR(svn_fs_fs__get_packed_offset(&rev_offset, fs, rev, pool));
-      *absolute_position = rev_offset + offset;
-    }
-  else
-    {
-      *absolute_position = offset;
-    }
-
-  return SVN_NO_ERROR;
+  return ffd->min_log_addressing_rev != SVN_INVALID_REVNUM
+      && ffd->min_log_addressing_rev <= rev;
 }
 
 svn_boolean_t

Modified: subversion/trunk/subversion/libsvn_fs_fs/util.h
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/util.h?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/util.h (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/util.h Mon Dec  2 14:55:20 2013
@@ -169,6 +169,24 @@ svn_fs_fs__path_revprops(svn_fs_t *fs,
                          svn_revnum_t rev,
                          apr_pool_t *pool);
 
+/* Return the path of the file containing the log-to-phys index for the
+ * file containing revision REV in FS. The result will be allocated in POOL.
+ */
+const char *
+svn_fs_fs__path_l2p_index(svn_fs_t *fs,
+                          svn_revnum_t rev,
+                          svn_boolean_t packed,
+                          apr_pool_t *pool);
+
+/* Return the path of the file containing the phys-to-log index for the
+ * file containing revision REV in FS. The result will be allocated in POOL.
+ */
+const char *
+svn_fs_fs__path_p2l_index(svn_fs_t *fs,
+                          svn_revnum_t rev,
+                          svn_boolean_t packed,
+                          apr_pool_t *pool);
+
 /* Return the path of the file storing the oldest non-packed revision in FS.
  * The result will be allocated in POOL.
  */
@@ -225,6 +243,33 @@ svn_fs_fs__path_txn_node_children(svn_fs
                                   const svn_fs_id_t *id,
                                   apr_pool_t *pool);
 
+/* Return the path of the file containing the log-to-phys index for
+ * the transaction identified by TXN_ID in FS.
+ * The result will be allocated in POOL.
+ */
+const char*
+svn_fs_fs__path_l2p_proto_index(svn_fs_t *fs,
+                                const svn_fs_fs__id_part_t *txn_id,
+                                apr_pool_t *pool);
+
+/* Return the path of the file containing the phys-to-log index for
+ * the transaction identified by TXN_ID in FS.
+ * The result will be allocated in POOL.
+ */
+const char*
+svn_fs_fs__path_p2l_proto_index(svn_fs_t *fs,
+                                const svn_fs_fs__id_part_t *txn_id,
+                                apr_pool_t *pool);
+
+/* Return the path of the file containing item_index counter for
+ * the transaction identified by TXN_ID in FS.
+ * The result will be allocated in POOL.
+ */
+const char *
+svn_fs_fs__path_txn_item_index(svn_fs_t *fs,
+                               const svn_fs_fs__id_part_t *txn_id,
+                               apr_pool_t *pool);
+
 /* Return the path of the file containing the node origins cachs for
  * the given NODE_ID in FS.  The result will be allocated in POOL.
  */
@@ -335,34 +380,13 @@ svn_fs_fs__move_into_place(const char *o
                            const char *perms_reference,
                            apr_pool_t *pool);
 
-/* Open the correct revision file for REV.  If the filesystem FS has
-   been packed, *FILE will be set to the packed file; otherwise, set *FILE
-   to the revision file for REV.  Return SVN_ERR_FS_NO_SUCH_REVISION if the
-   file doesn't exist.
-
-   TODO: Consider returning an indication of whether this is a packed rev
-         file, so the caller need not rely on is_packed_rev() which in turn
-         relies on the cached FFD->min_unpacked_rev value not having changed
-         since the rev file was opened.
-
-   Use POOL for allocations. */
-svn_error_t *
-svn_fs_fs__open_pack_or_rev_file(apr_file_t **file,
-                                 svn_fs_t *fs,
-                                 svn_revnum_t rev,
-                                 apr_pool_t *pool);
-
-/* For OFFSET within REV in FS, return the position in the respective rev
-   or pack file in *ABSOLUTE_POSITION.  Use POOL for allocations. */
-svn_error_t *
-svn_fs_fs__item_offset(apr_off_t *absolute_position,
-                       svn_fs_t *fs,
-                       svn_revnum_t rev,
-                       apr_off_t offset,
-                       apr_pool_t *pool);
+/* Return TRUE, iff revision REV in FS requires logical addressing. */
+svn_boolean_t
+svn_fs_fs__use_log_addressing(svn_fs_t *fs,
+                              svn_revnum_t rev);
 
 /* Return TRUE if FS's format supports moves to be recorded natively. */
 svn_boolean_t
 svn_fs_fs__supports_move(svn_fs_t *fs);
 
-#endif
+#endif
\ No newline at end of file

Modified: subversion/trunk/subversion/libsvn_fs_fs/verify.c
URL: http://svn.apache.org/viewvc/subversion/trunk/subversion/libsvn_fs_fs/verify.c?rev=1547045&r1=1547044&r2=1547045&view=diff
==============================================================================
--- subversion/trunk/subversion/libsvn_fs_fs/verify.c (original)
+++ subversion/trunk/subversion/libsvn_fs_fs/verify.c Mon Dec  2 14:55:20 2013
@@ -20,12 +20,17 @@
  * ====================================================================
  */
 
+#include "svn_sorts.h"
+#include "svn_checksum.h"
+#include "private/svn_subr_private.h"
+
 #include "verify.h"
 #include "fs_fs.h"
 
 #include "cached_data.h"
 #include "rep-cache.h"
 #include "util.h"
+#include "index.h"
 
 #include "../libsvn_fs/fs-loader.h"
 
@@ -154,6 +159,517 @@ verify_rep_cache(svn_fs_t *fs,
   return SVN_NO_ERROR;
 }
 
+/* Verify that for all log-to-phys index entries for revisions START to
+ * START + COUNT-1 in FS there is a consistent entry in the phys-to-log
+ * index.  If given, invoke CANCEL_FUNC with CANCEL_BATON at regular
+ * intervals. Use POOL for allocations.
+ */
+static svn_error_t *
+compare_l2p_to_p2l_index(svn_fs_t *fs,
+                         svn_revnum_t start,
+                         svn_revnum_t count,
+                         svn_cancel_func_t cancel_func,
+                         void *cancel_baton,
+                         apr_pool_t *pool)
+{
+  svn_revnum_t i;
+  apr_pool_t *iterpool = svn_pool_create(pool);
+  apr_array_header_t *max_ids;
+
+  /* common file access structure */
+  svn_fs_fs__revision_file_t rev_file;
+  svn_fs_fs__init_revision_file(&rev_file, fs, start, pool);
+
+  /* determine the range of items to check for each revision */
+  SVN_ERR(svn_fs_fs__l2p_get_max_ids(&max_ids, fs, start, count, pool));
+
+  /* check all items in all revisions if the given range */
+  for (i = 0; i < max_ids->nelts; ++i)
+    {
+      apr_uint64_t k;
+      apr_uint64_t max_id = APR_ARRAY_IDX(max_ids, i, apr_uint64_t);
+      svn_revnum_t revision = start + i;
+
+      for (k = 0; k < max_id; ++k)
+        {
+          apr_off_t offset;
+          svn_fs_fs__p2l_entry_t *p2l_entry;
+          svn_pool_clear(iterpool);
+
+          /* get L2P entry.  Ignore unused entries. */
+          SVN_ERR(svn_fs_fs__item_offset(&offset, fs, &rev_file, revision,
+                                         NULL, k, iterpool));
+          if (offset == -1)
+            continue;
+
+          /* find the corresponding P2L entry */
+          SVN_ERR(svn_fs_fs__p2l_entry_lookup(&p2l_entry, fs, &rev_file,
+                                              revision, offset, iterpool));
+
+          if (p2l_entry == NULL)
+            return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_INCONSISTENT,
+                                     NULL,
+                                     _("p2l index entry not found for "
+                                       "PHYS %s returned by "
+                                       "l2p index for LOG r%ld:i%ld"),
+                                     apr_off_t_toa(pool, offset),
+                                     revision, (long)k);
+
+          if (   p2l_entry->item.number != k
+              || p2l_entry->item.revision != revision)
+            return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_INCONSISTENT,
+                                     NULL,
+                                     _("p2l index info LOG r%ld:i%ld"
+                                       " does not match "
+                                       "l2p index for LOG r%ld:i%ld"),
+                                     p2l_entry->item.revision,
+                                     (long)p2l_entry->item.number,
+                                     revision, (long)k);
+        }
+
+      if (cancel_func)
+        SVN_ERR(cancel_func(cancel_baton));
+    }
+
+  svn_pool_destroy(iterpool);
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that for all phys-to-log index entries for revisions START to
+ * START + COUNT-1 in FS there is a consistent entry in the log-to-phys
+ * index.  If given, invoke CANCEL_FUNC with CANCEL_BATON at regular
+ * intervals. Use POOL for allocations.
+ *
+ * Please note that we can only check on pack / rev file granularity and
+ * must only be called for a single rev / pack file.
+ */
+static svn_error_t *
+compare_p2l_to_l2p_index(svn_fs_t *fs,
+                         svn_revnum_t start,
+                         svn_revnum_t count,
+                         svn_cancel_func_t cancel_func,
+                         void *cancel_baton,
+                         apr_pool_t *pool)
+{
+  apr_pool_t *iterpool = svn_pool_create(pool);
+  apr_off_t max_offset;
+  apr_off_t offset = 0;
+
+  /* common file access structure */
+  svn_fs_fs__revision_file_t rev_file;
+  svn_fs_fs__init_revision_file(&rev_file, fs, start, pool);
+
+  /* get the size of the rev / pack file as covered by the P2L index */
+  SVN_ERR(svn_fs_fs__p2l_get_max_offset(&max_offset, fs, &rev_file, start,
+                                        pool));
+
+  /* for all offsets in the file, get the P2L index entries and check
+     them against the L2P index */
+  for (offset = 0; offset < max_offset; )
+    {
+      apr_array_header_t *entries;
+      svn_fs_fs__p2l_entry_t *last_entry;
+      int i;
+
+      svn_pool_clear(iterpool);
+
+      /* get all entries for the current block */
+      SVN_ERR(svn_fs_fs__p2l_index_lookup(&entries, fs, &rev_file, start,
+                                          offset, iterpool));
+      if (entries->nelts == 0)
+        return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_CORRUPTION,
+                                 NULL,
+                                 _("p2l does not cover offset %s"
+                                   " for revision %ld"),
+                                  apr_off_t_toa(pool, offset), start);
+
+      /* process all entries (and later continue with the next block) */
+      last_entry
+        = &APR_ARRAY_IDX(entries, entries->nelts-1, svn_fs_fs__p2l_entry_t);
+      offset = last_entry->offset + last_entry->size;
+
+      for (i = 0; i < entries->nelts; ++i)
+        {
+          svn_fs_fs__p2l_entry_t *entry
+            = &APR_ARRAY_IDX(entries, i, svn_fs_fs__p2l_entry_t);
+
+          /* check all sub-items for consist entries in the L2P index */
+          if (entry->type != SVN_FS_FS__ITEM_TYPE_UNUSED)
+            {
+              apr_off_t l2p_offset;
+              SVN_ERR(svn_fs_fs__item_offset(&l2p_offset, fs, &rev_file,
+                                             entry->item.revision, NULL,
+                                             entry->item.number, iterpool));
+
+              if (l2p_offset != entry->offset)
+                return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_INCONSISTENT,
+                                         NULL,
+                                         _("l2p index entry PHYS %s"
+                                           "does not match p2l index value "
+                                           "LOG r%ld:i%ld for PHYS %s"),
+                                         apr_off_t_toa(pool, l2p_offset),
+                                         entry->item.revision,
+                                         (long)entry->item.number,
+                                         apr_off_t_toa(pool, entry->offset));
+            }
+        }
+
+      if (cancel_func)
+        SVN_ERR(cancel_func(cancel_baton));
+    }
+
+  svn_pool_destroy(iterpool);
+
+  return SVN_NO_ERROR;
+}
+
+/* Items smaller than this can be read at once into a buffer and directly
+ * be checksummed.  Larger items require stream processing.
+ * Must be a multiple of 8. */
+#define STREAM_THRESHOLD 4096
+
+/* Verify that the next SIZE bytes read from FILE are NUL.
+ * SIZE must not exceed STREAM_THRESHOLD.  Use POOL for allocations.
+ */
+static svn_error_t *
+expect_buffer_nul(apr_file_t *file,
+                  apr_off_t size,
+                  apr_pool_t *pool)
+{
+  union
+  {
+    unsigned char buffer[STREAM_THRESHOLD];
+    apr_uint64_t chunks[STREAM_THRESHOLD / sizeof(apr_uint64_t)];
+  } data;
+
+  apr_size_t i;
+  SVN_ERR_ASSERT(size <= STREAM_THRESHOLD);
+
+  /* read the whole data block; error out on failure */
+  data.chunks[(size - 1)/ sizeof(apr_uint64_t)] = 0;
+  SVN_ERR(svn_io_file_read_full2(file, data.buffer, size, NULL, NULL, pool));
+
+  /* chunky check */
+  for (i = 0; i < size / sizeof(apr_uint64_t); ++i)
+    if (data.chunks[i] != 0)
+      break;
+
+  /* byte-wise check upon mismatch or at the end of the block */
+  for (i *= sizeof(apr_uint64_t); i < size; ++i)
+    if (data.buffer[i] != 0)
+      {
+        const char *file_name;
+        apr_off_t offset;
+        
+        SVN_ERR(svn_io_file_name_get(&file_name, file, pool));
+        SVN_ERR(svn_fs_fs__get_file_offset(&offset, file, pool));
+        offset -= size - i;
+
+        return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
+                                 _("Empty section in file %s contains "
+                                   "non-NUL data at offset %s"),
+                                 file_name, apr_off_t_toa(pool, offset));
+      }
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that the next SIZE bytes read from FILE are NUL.
+ * Use POOL for allocations.
+ */
+static svn_error_t *
+read_all_nul(apr_file_t *file,
+             apr_off_t size,
+             apr_pool_t *pool)
+{
+  for (; size >= STREAM_THRESHOLD; size -= STREAM_THRESHOLD)
+    SVN_ERR(expect_buffer_nul(file, STREAM_THRESHOLD, pool));
+
+  if (size)
+    SVN_ERR(expect_buffer_nul(file, size, pool));
+
+  return SVN_NO_ERROR;
+}
+
+/* Compare the ACTUAL checksum with the one expected by ENTRY.
+ * Return an error in case of mismatch.  Use the name of FILE
+ * in error message.  Allocate data in POOL.
+ */
+static svn_error_t *
+expected_checksum(apr_file_t *file,
+                  svn_fs_fs__p2l_entry_t *entry,
+                  apr_uint32_t actual,
+                  apr_pool_t *pool)
+{
+  if (actual != entry->fnv1_checksum)
+    {
+      const char *file_name;
+
+      SVN_ERR(svn_io_file_name_get(&file_name, file, pool));
+      return svn_error_createf(SVN_ERR_FS_CORRUPT, NULL,
+                               _("Checksum mismatch item at offset %s of "
+                                 "length %s bytes in file %s"),
+                               apr_off_t_toa(pool, entry->offset),
+                               apr_off_t_toa(pool, entry->size), file_name);
+    }
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that the FNV checksum over the next ENTRY->SIZE bytes read
+ * from FILE will match ENTRY's expected checksum.  SIZE must not
+ * exceed STREAM_THRESHOLD.  Use POOL for allocations.
+ */
+static svn_error_t *
+expected_buffered_checksum(apr_file_t *file,
+                           svn_fs_fs__p2l_entry_t *entry,
+                           apr_pool_t *pool)
+{
+  unsigned char buffer[STREAM_THRESHOLD];
+  SVN_ERR_ASSERT(entry->size <= STREAM_THRESHOLD);
+
+  SVN_ERR(svn_io_file_read_full2(file, buffer, (apr_size_t)entry->size,
+                                 NULL, NULL, pool));
+  SVN_ERR(expected_checksum(file, entry,
+                            svn__fnv1a_32x4(buffer, (apr_size_t)entry->size),
+                            pool));
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that the FNV checksum over the next ENTRY->SIZE bytes read from
+ * FILE will match ENTRY's expected checksum.  Use POOL for allocations.
+ */
+static svn_error_t *
+expected_streamed_checksum(apr_file_t *file,
+                           svn_fs_fs__p2l_entry_t *entry,
+                           apr_pool_t *pool)
+{
+  unsigned char buffer[STREAM_THRESHOLD];
+  svn_checksum_t *checksum;
+  svn_checksum_ctx_t *context
+    = svn_checksum_ctx_create(svn_checksum_fnv1a_32x4, pool);
+  apr_off_t size = entry->size;
+
+  while (size > 0)
+    {
+      apr_size_t to_read = size > sizeof(buffer)
+                         ? sizeof(buffer)
+                         : (apr_size_t)size;
+      SVN_ERR(svn_io_file_read_full2(file, buffer, to_read, NULL, NULL,
+                                     pool));
+      SVN_ERR(svn_checksum_update(context, buffer, to_read));
+      size -= to_read;
+    }
+
+  SVN_ERR(svn_checksum_final(&checksum, context, pool));
+  SVN_ERR(expected_checksum(file, entry,
+                            *(apr_uint32_t *)checksum->digest,
+                            pool));
+
+  return SVN_NO_ERROR;
+}
+
+/* Verify that for all phys-to-log index entries for revisions START to
+ * START + COUNT-1 in FS match the actual pack / rev file contents.
+ * If given, invoke CANCEL_FUNC with CANCEL_BATON at regular intervals.
+ * Use POOL for allocations.
+ *
+ * Please note that we can only check on pack / rev file granularity and
+ * must only be called for a single rev / pack file.
+ */
+static svn_error_t *
+compare_p2l_to_rev(svn_fs_t *fs,
+                   svn_revnum_t start,
+                   svn_revnum_t count,
+                   svn_cancel_func_t cancel_func,
+                   void *cancel_baton,
+                   apr_pool_t *pool)
+{
+  fs_fs_data_t *ffd = fs->fsap_data;
+  apr_pool_t *iterpool = svn_pool_create(pool);
+  apr_off_t max_offset;
+  apr_off_t offset = 0;
+  svn_fs_fs__revision_file_t *rev_file;
+
+  /* open the pack / rev file that is covered by the p2l index */
+  SVN_ERR(svn_fs_fs__open_pack_or_rev_file(&rev_file, fs, start, pool));
+
+  /* check file size vs. range covered by index */
+  SVN_ERR(svn_io_file_seek(rev_file->file, APR_END, &offset, pool));
+  SVN_ERR(svn_fs_fs__p2l_get_max_offset(&max_offset, fs, rev_file, start,
+                                        pool));
+
+  if (offset != max_offset)
+    return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_INCONSISTENT, NULL,
+                             _("File size of %s for revision r%ld does "
+                               "not match p2l index size of %s"),
+                             apr_off_t_toa(pool, offset), start,
+                             apr_off_t_toa(pool, max_offset));
+
+  SVN_ERR(svn_io_file_aligned_seek(rev_file->file, ffd->block_size, NULL, 0,
+                                   pool));
+
+  /* for all offsets in the file, get the P2L index entries and check
+     them against the L2P index */
+  for (offset = 0; offset < max_offset; )
+    {
+      apr_array_header_t *entries;
+      int i;
+
+      svn_pool_clear(iterpool);
+
+      /* get all entries for the current block */
+      SVN_ERR(svn_fs_fs__p2l_index_lookup(&entries, fs, rev_file, start,
+                                          offset, iterpool));
+
+      /* process all entries (and later continue with the next block) */
+      for (i = 0; i < entries->nelts; ++i)
+        {
+          svn_fs_fs__p2l_entry_t *entry
+            = &APR_ARRAY_IDX(entries, i, svn_fs_fs__p2l_entry_t);
+
+          /* skip bits we previously checked */
+          if (i == 0 && entry->offset < offset)
+            continue;
+
+          /* skip zero-sized entries */
+          if (entry->size == 0)
+            continue;
+
+          /* p2l index must cover all rev / pack file offsets exactly once */
+          if (entry->offset != offset)
+            return svn_error_createf(SVN_ERR_FS_ITEM_INDEX_INCONSISTENT,
+                                     NULL,
+                                     _("p2l index entry for revision r%ld"
+                                       " is non-contiguous between offsets "
+                                       " %s and %s"),
+                                     start,
+                                     apr_off_t_toa(pool, offset),
+                                     apr_off_t_toa(pool, entry->offset));
+
+          /* empty sections must contain NUL bytes only */
+          if (entry->type == SVN_FS_FS__ITEM_TYPE_UNUSED)
+            {
+              /* skip filler entry at the end of the p2l index */
+              if (entry->offset != max_offset)
+                SVN_ERR(read_all_nul(rev_file->file, entry->size, pool));
+            }
+          else if (entry->fnv1_checksum)
+            {
+              if (entry->size < STREAM_THRESHOLD)
+                SVN_ERR(expected_buffered_checksum(rev_file->file, entry,
+                                                   pool));
+              else
+                SVN_ERR(expected_streamed_checksum(rev_file->file, entry,
+                                                   pool));
+            }
+
+          /* advance offset */
+          offset += entry->size;
+        }
+
+      if (cancel_func)
+        SVN_ERR(cancel_func(cancel_baton));
+    }
+
+  svn_pool_destroy(iterpool);
+
+  return SVN_NO_ERROR;
+}
+
+static svn_revnum_t
+packed_base_rev(svn_fs_t *fs, svn_revnum_t rev)
+{
+  fs_fs_data_t *ffd = fs->fsap_data;
+
+  return rev < ffd->min_unpacked_rev
+       ? rev - (rev % ffd->max_files_per_dir)
+       : rev;
+}
+
+static svn_revnum_t
+pack_size(svn_fs_t *fs, svn_revnum_t rev)
+{
+  fs_fs_data_t *ffd = fs->fsap_data;
+
+  return rev < ffd->min_unpacked_rev ? ffd->max_files_per_dir : 1;
+}
+
+/* Verify that the log-to-phys indexes and phys-to-log indexes are
+ * consistent with each other.  The function signature is similar to
+ * svn_fs_fs__verify.
+ *
+ * The values of START and END have already been auto-selected and
+ * verified.  You may call this for format7 or higher repos.
+ */
+static svn_error_t *
+verify_index_consistency(svn_fs_t *fs,
+                         svn_revnum_t start,
+                         svn_revnum_t end,
+                         svn_fs_progress_notify_func_t notify_func,
+                         void *notify_baton,
+                         svn_cancel_func_t cancel_func,
+                         void *cancel_baton,
+                         apr_pool_t *pool)
+{
+  fs_fs_data_t *ffd = fs->fsap_data;
+  svn_revnum_t revision, next_revision;
+  apr_pool_t *iterpool = svn_pool_create(pool);
+
+  for (revision = start; revision <= end; revision = next_revision)
+    {
+      svn_error_t *err = SVN_NO_ERROR;
+
+      svn_revnum_t count = pack_size(fs, revision);
+      svn_revnum_t pack_start = packed_base_rev(fs, revision);
+      svn_revnum_t pack_end = pack_start + count;
+
+      svn_pool_clear(iterpool);
+
+      if (notify_func && (pack_start % ffd->max_files_per_dir == 0))
+        notify_func(pack_start, notify_baton, iterpool);
+
+      /* two-way index check */
+      err = compare_l2p_to_p2l_index(fs, pack_start, pack_end - pack_start,
+                                     cancel_func, cancel_baton, iterpool);
+      if (!err)
+        err = compare_p2l_to_l2p_index(fs, pack_start, pack_end - pack_start,
+                                       cancel_func, cancel_baton, iterpool);
+
+      /* verify in-index checksums and types vs. actual rev / pack files */
+      if (!err)
+        err = compare_p2l_to_rev(fs, pack_start, pack_end - pack_start,
+                                 cancel_func, cancel_baton, iterpool);
+
+      /* concurrent packing is one of the reasons why verification may fail.
+         Make sure, we operate on up-to-date information. */
+      if (err)
+        SVN_ERR(svn_fs_fs__read_min_unpacked_rev(&ffd->min_unpacked_rev,
+                                                 fs, pool));
+
+      /* retry the whole shard if it got packed in the meantime */
+      if (err && count != pack_size(fs, revision))
+        {
+          svn_error_clear(err);
+
+          /* We could simply assign revision here but the code below is
+             more intuitive to maintainers. */
+          next_revision = packed_base_rev(fs, revision);
+        }
+      else
+        {
+          SVN_ERR(err);
+          next_revision = pack_end;
+        }
+    }
+
+  svn_pool_destroy(iterpool);
+
+  return SVN_NO_ERROR;
+}
+
 svn_error_t *
 svn_fs_fs__verify(svn_fs_t *fs,
                   svn_revnum_t start,
@@ -175,6 +691,14 @@ svn_fs_fs__verify(svn_fs_t *fs,
   SVN_ERR(svn_fs_fs__ensure_revision_exists(start, fs, pool));
   SVN_ERR(svn_fs_fs__ensure_revision_exists(end, fs, pool));
 
+  /* log/phys index consistency.  We need to check them first to make
+     sure we can access the rev / pack files in format7. */
+  if (svn_fs_fs__use_log_addressing(fs, end))
+    SVN_ERR(verify_index_consistency(fs,
+                                     MAX(start, ffd->min_log_addressing_rev),
+                                     end, notify_func, notify_baton,
+                                     cancel_func, cancel_baton, pool));
+
   /* rep cache consistency */
   if (ffd->format >= SVN_FS_FS__MIN_REP_SHARING_FORMAT)
     SVN_ERR(verify_rep_cache(fs, start, end, notify_func, notify_baton,



Mime
View raw message