Uploaded image for project: 'Subversion'
  1. Subversion
  2. SVN-4269

subtree mergeinfo can degrade automatic merge performance

    XMLWordPrintableJSON

    Details

      Description

      hwright reported a run-of-the-mill automatic merge which took several minutes
      before anything appeared to happen, see
      http://svn.haxx.se/dev/archive-2012-12/0086.shtml
      
      I analyzed this merge and there is a potential performance problem when
      automatic (a.k.a. sync merges) are made to long-lived branches where a previous
      automatic merge *added* a subtree with explicit mergeinfo.  If this earlier
      merge took place long after the creation of the branch and after other sync
      merges have already occurred, then a problem can arise.
      
      The problem is that the merge code (specifically
      libsvn_client/merge.c:remove_noop_subtree_ranges) uses svn_ra_get_log2 to detect
      revisions that don't need to be merged because they are inoperative.  In the
      aforementioned scenario, there is the possibility that a very large number of
      logs will need to be retrieved.
      
      A look at the example hwright encountered will help explain.
      
      The merge is into a working copy of ^/subversion/branches/ev2-export.  This
      branch was made from ^/subversion/trunk@1231318.  Frequent auto merges were made
      to this branch from ^/subversion/trunk to keep it in sync.  The problem starts
      in the auto merge made in r1308894.  That merge added the subtree
      'tools/dist/make-deps-tarball.sh' which had explicit mergeinfo on it:
      
      C:\SVN\src-branch-ev2-export>svn pg svn:mergeinfo -r1308894
      tools\dist\make-deps-tarball.sh
      /subversion/branches/1.5.x-r30215/tools/dist/construct-rolling-environment.sh:870312
      /subversion/branches/bdb-reverse-deltas/tools/dist/construct-rolling-environment.sh:872050-872529
      /subversion/branches/diff-callbacks3/tools/dist/construct-rolling-environment.sh:870059-870761
      <SNIP>
      /subversion/branches/tree-conflicts/tools/dist/construct-rolling-environment.sh:868291-873154
      /subversion/branches/tree-conflicts-notify/tools/dist/construct-rolling-environment.sh:873926-874008
      /subversion/trunk/tools/dist/make-deps-tarball.sh:1304315-1308886
                  ^^^^^
      Notice that mergeinfo describing the merge that added this subtree is recorded.
      
      Regular auto merges continue to be made up until today, leaving us with this
      before hwright's problematic merge:
      
      ---trunk@1231318-----------1297218---1308886----------->
           |             | | |      |         |      | | |
          copy           auto      auto      auto    auto
           |             merges    merge     merge   merges
           |             | | |      |         |      | | |
           v             v v v      v         v      v v v
         ex2-export--------------1297221---1308894----------->
                                           Adds subtree
                                           'tools/dist/make-deps-tarball.sh'
                                           with explicit mergeinfo on it
      
      Which brings us to the merge.  We have a WC of the ev2-export branch at revision
      1417130, with this mergeinfo:
      
      C:\SVN\src-branch-ev2-export>svn pg svn:mergeinfo -vR
      Properties on '.':
        svn:mergeinfo
          /subversion/branches/1.5.x-r30215:870312
          /subversion/branches/1.7.x-fs-verify:1146708,1161180
         
      /subversion/branches/10Gb:1388102,1388163-1388190,1388195,1388202,1388205,1388211,1388276,1388362,1388375,1388394,1388636,1388639-1388640,1388643-1388644,1388654,1388720,1388789,1388795,1388801,1388805,1388807,1388810,1388816,1389044,1389276,1389289,1389662,1389867,1390017,1390209,1390216,1390407,1390409,1390414,1390419,1390955
      <SNIP>
          /subversion/branches/uris-as-urls:1060426-1064427
          /subversion/trunk:1231319-1295003,1295006-1416744
      Properties on 'tools\dist\make-deps-tarball.sh':
        svn:mergeinfo
         
      /subversion/branches/1.5.x-r30215/tools/dist/construct-rolling-environment.sh:870312
         
      /subversion/branches/10Gb/tools/dist/make-deps-tarball.sh:1388394,1388636,1388639,1388644,1388654,1388720,1388789,1388795,1388801,1388805,1388810,1388816,1389044,1389276,1389289,1389662,1389867,1390017,1390216,1390407
         
      /subversion/branches/auto-props-sdc/tools/dist/make-deps-tarball.sh:1384106-1401643
      <SNIP>
         
      /subversion/branches/tree-conflicts/tools/dist/construct-rolling-environment.sh:868291-873154
         
      /subversion/branches/tree-conflicts-notify/tools/dist/construct-rolling-environment.sh:873926-874008
          /subversion/trunk/tools/dist/make-deps-tarball.sh:1304315-1404840
      
      What we want to pay close attention to is the mergeinfo from ^/subversion/trunk
      (since that is where we will merge from):
      
      Properties on '.':
        svn:mergeinfo
          /subversion/trunk:1231319-1295003,1295006-1416744
      Properties on 'tools\dist\make-deps-tarball.sh':
        svn:mergeinfo
          /subversion/trunk/tools/dist/make-deps-tarball.sh:1304315-1404840
      
      When we try an auto merge like so,
      
      ---trunk@1231318-----------1297218---1308886---------------
           |             | | |      |         |      | | |      |
          copy           auto      auto      auto    auto      auto
           |             merges    merge     merge   merges    merge
           |             | | |      |         |      | | |      |
           v             v v v      v         v      v v v      v 
         ex2-export--------------1297221---1308894-----------WC@1417130
                                           Adds subtree
                                           'tools/dist/make-deps-tarball.sh'
                                           with explicit mergeinfo on it
      
      the merge code starts by assuming that -r1231318(YCA):1417138(HEAD) needs to be
      merged.  It then tries to figure out what part of this range is already merged
      per the merge target's mergeinfo, both that on the target and on any of its
      subtrees.  The code does several calculations in this space, but the one that is
      causing the problem is in libsvn_client/merge.c:remove_noop_subtree_ranges(),
      where we determine what revisions are needed by subtrees but aren't required by
      the target itself.  Coming into this function we've already pared down our
      initial default merge assumption:
      
      FOR THE TARGET '.':
        
        Default Merge:  /subversion/trunk:1231319:1417138
        Less Mergeinfo: /subversion/trunk:1231319-1295003,1295006-1416744
        To be merged:   /subversion/trunk:1416745-1417138*
      
      * The gap 1295004-1295005 represents a replacement of trunk with itself, this
      has already been removed.
      
      FOR THE SUBTREE 'tools\dist\make-deps-tarball.sh':
      
        Default Merge:  /subversion/trunk/tools/dist/make-deps-tarball.sh:1231319:1417138
        Less Mergeinfo: /subversion/trunk/tools/dist/make-deps-tarball.sh:1304315-1404840
        To be merged:  
      /subversion/trunk/tools/dist/make-deps-tarball.sh:1231319-1304314,1404841-1417138
      
      That's what we know when we enter remove_noop_subtree_ranges():
      
      /* Helper for do_directory_merge().
      
         SOURCE is cascaded from the argument of the same name in
         do_directory_merge().  TARGET is the merge target.  RA_SESSION is the
         session for SOURCE->loc2.
      
         Find all the ranges required by subtrees in
         CHILDREN_WITH_MERGEINFO that are *not* required by
         TARGET->abspath (i.e. CHILDREN_WITH_MERGEINFO[0]).  If such
         ranges exist, then find any subset of ranges which, if merged, would be
         inoperative.  Finally, if any inoperative ranges are found then remove
         these ranges from all of the subtree's REMAINING_RANGES.
      
         This function should only be called when honoring mergeinfo during
         forward merges (i.e. SOURCE->rev1 < SOURCE->rev2).
      */
      static svn_error_t *
      remove_noop_subtree_ranges(const merge_source_t *source,
                                 const merge_target_t *target,
                                 svn_ra_session_t *ra_session,
                                 apr_array_header_t *children_with_mergeinfo,
                                 apr_pool_t *result_pool,
                                 apr_pool_t *scratch_pool)
      
      First the function determines what ranges need to be merged to the subtree but
      not the target, based on a naive reading of the mergeinfo:
      
        To be merged to target:  /subversion/trunk: 1416745-1417138
        To be merged to subtree:
      /subversion/trunk/tools/dist/make-deps-tarball.sh:1231319-1304314,1404841-1417138
      
        To be merged only to subtree: 1231319-1304314,1404841-1416744
      
      Then the function uses svn_ra_get_log2 (via its get_log helper) to figure out
      which of these revisions is actually operative:
      
        SVN_ERR(svn_ra_get_log2(ra_session, log_targets,
                                youngest_rev=1231319,
                                oldest_rev=1416744,
                                0 /* limit */, discover_changed_paths,
                                FALSE /* strict_node_history */,
                                FALSE /* include_merged_revisions */,
                                revprops, receiver, receiver_baton, pool));
      
      Unfortunately in this case we have a *lot* of revisions to check; there are 3412
      operative revisions here.  This takes several minutes for me against
      svn.apache.org, which represents the bulk of the delay I reported in
      http://svn.haxx.se/dev/archive-2012-12/0105.shtml.  Worse, at this point in the
      merge no progress messages have been sent, so the user simply sees this:
      
      C:\SVN\src-branch-ev2-export>svn merge
      https://svn.apache.org/repos/asf/subversion/trunk .
      <several minutes with no feedback>
      

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                Unassigned
                Reporter:
                pburba Paul Burba
              • Votes:
                0 Vote for this issue
                Watchers:
                0 Start watching this issue

                Dates

                • Created:
                  Updated: