Merge branch 'jt/fetch-negotiator-skipping'
authorJunio C Hamano <gitster@pobox.com>
Thu, 2 Aug 2018 22:30:46 +0000 (15:30 -0700)
committerJunio C Hamano <gitster@pobox.com>
Thu, 2 Aug 2018 22:30:46 +0000 (15:30 -0700)
Add a server-side knob to skip commits in exponential/fibbonacci
stride in an attempt to cover wider swath of history with a smaller
number of iterations, potentially accepting a larger packfile
transfer, instead of going back one commit a time during common
ancestor discovery during the "git fetch" transaction.

* jt/fetch-negotiator-skipping:
  negotiator/skipping: skip commits during fetch

1  2 
Documentation/config.txt
Makefile
fetch-pack.c
negotiator/skipping.c

diff --combined Documentation/config.txt
@@@ -344,16 -344,6 +344,16 @@@ advice.*:
                Advice shown when you used linkgit:git-checkout[1] to
                move to the detach HEAD state, to instruct how to create
                a local branch after the fact.
 +      checkoutAmbiguousRemoteBranchName::
 +              Advice shown when the argument to
 +              linkgit:git-checkout[1] ambiguously resolves to a
 +              remote tracking branch on more than one remote in
 +              situations where an unambiguous argument would have
 +              otherwise caused a remote-tracking branch to be
 +              checked out. See the `checkout.defaultRemote`
 +              configuration variable for how to set a given remote
 +              to used by default in some situations where this
 +              advice would be printed.
        amWorkDir::
                Advice that shows the location of the patch file when
                linkgit:git-am[1] fails to apply it.
                Advice on what to do when you've accidentally added one
                git repo inside of another.
        ignoredHook::
 -              Advice shown if an hook is ignored because the hook is not
 +              Advice shown if a hook is ignored because the hook is not
                set as executable.
        waitingForEditor::
                Print a message to the terminal whenever Git is waiting for
@@@ -400,19 -390,16 +400,19 @@@ core.hideDotFiles:
        default mode is 'dotGitOnly'.
  
  core.ignoreCase::
 -      If true, this option enables various workarounds to enable
 +      Internal variable which enables various workarounds to enable
        Git to work better on filesystems that are not case sensitive,
 -      like FAT. For example, if a directory listing finds
 -      "makefile" when Git expects "Makefile", Git will assume
 +      like APFS, HFS+, FAT, NTFS, etc. For example, if a directory listing
 +      finds "makefile" when Git expects "Makefile", Git will assume
        it is really the same file, and continue to remember it as
        "Makefile".
  +
  The default is false, except linkgit:git-clone[1] or linkgit:git-init[1]
  will probe and set core.ignoreCase true if appropriate when the repository
  is created.
 ++
 +Git relies on the proper configuration of this variable for your operating
 +and file system. Modifying this value may result in unexpected behavior.
  
  core.precomposeUnicode::
        This option is only used by Mac OS implementation of Git.
@@@ -917,12 -904,9 +917,12 @@@ core.notesRef:
  This setting defaults to "refs/notes/commits", and it can be overridden by
  the `GIT_NOTES_REF` environment variable.  See linkgit:git-notes[1].
  
 -core.commitGraph::
 -      Enable git commit graph feature. Allows reading from the
 -      commit-graph file.
 +gc.commitGraph::
 +      If true, then gc will rewrite the commit-graph file when
 +      linkgit:git-gc[1] is run. When using linkgit:git-gc[1]
 +      '--auto' the commit-graph will be updated if housekeeping is
 +      required. Default is false. See linkgit:git-commit-graph[1]
 +      for details.
  
  core.sparseCheckout::
        Enable "sparse checkout" feature. See section "Sparse checkout" in
@@@ -1114,22 -1098,6 +1114,22 @@@ browser.<tool>.path:
        browse HTML help (see `-w` option in linkgit:git-help[1]) or a
        working repository in gitweb (see linkgit:git-instaweb[1]).
  
 +checkout.defaultRemote::
 +      When you run 'git checkout <something>' and only have one
 +      remote, it may implicitly fall back on checking out and
 +      tracking e.g. 'origin/<something>'. This stops working as soon
 +      as you have more than one remote with a '<something>'
 +      reference. This setting allows for setting the name of a
 +      preferred remote that should always win when it comes to
 +      disambiguation. The typical use-case is to set this to
 +      `origin`.
 ++
 +Currently this is used by linkgit:git-checkout[1] when 'git checkout
 +<something>' will checkout the '<something>' branch on another remote,
 +and by linkgit:git-worktree[1] when 'git worktree add' refers to a
 +remote branch. This setting might be used for other checkout-like
 +commands or functionality in the future.
 +
  clean.requireForce::
        A boolean to make git-clean do nothing unless given -f,
        -i or -n.   Defaults to true.
@@@ -1178,11 -1146,6 +1178,11 @@@ diff.colorMoved:
        true the default color mode will be used. When set to false,
        moved lines are not colored.
  
 +diff.colorMovedWS::
 +      When moved lines are colored using e.g. the `diff.colorMoved` setting,
 +      this option controls the `<mode>` how spaces are treated
 +      for details of valid modes see '--color-moved-ws' in linkgit:git-diff[1].
 +
  color.diff.<slot>::
        Use customized color for diff colorization.  `<slot>` specifies
        which part of the patch to use the specified color, and is one
  color.decorate.<slot>::
        Use customized color for 'git log --decorate' output.  `<slot>` is one
        of `branch`, `remoteBranch`, `tag`, `stash` or `HEAD` for local
 -      branches, remote-tracking branches, tags, stash and HEAD, respectively.
 +      branches, remote-tracking branches, tags, stash and HEAD, respectively
 +      and `grafted` for grafted commits.
  
  color.grep::
        When set to `always`, always highlight matches.  When `false` (or
@@@ -1219,10 -1181,8 +1219,10 @@@ color.grep.<slot>:
        filename prefix (when not using `-h`)
  `function`;;
        function name lines (when using `-p`)
 -`linenumber`;;
 +`lineNumber`;;
        line number prefix (when using `-n`)
 +`column`;;
 +      column number prefix (when using `--column`)
  `match`;;
        matching text (same as setting `matchContext` and `matchSelected`)
  `matchContext`;;
@@@ -1531,6 -1491,15 +1531,15 @@@ fetch.output:
        `full` and `compact`. Default value is `full`. See section
        OUTPUT in linkgit:git-fetch[1] for detail.
  
+ fetch.negotiationAlgorithm::
+       Control how information about the commits in the local repository is
+       sent when negotiating the contents of the packfile to be sent by the
+       server. Set to "skipping" to use an algorithm that skips commits in an
+       effort to converge faster, but may result in a larger-than-necessary
+       packfile; any other value instructs Git to use the default algorithm
+       that never skips commits (unless the server has acknowledged it or one
+       of its descendants).
  format.attach::
        Enable multipart/mixed attachments as the default for
        'format-patch'.  The value can also be a double quoted string
@@@ -1837,9 -1806,6 +1846,9 @@@ gitweb.snapshot:
  grep.lineNumber::
        If set to true, enable `-n` option by default.
  
 +grep.column::
 +      If set to true, enable the `--column` option by default.
 +
  grep.patternType::
        Set the default matching behavior. Using a value of 'basic', 'extended',
        'fixed', or 'perl' will enable the `--basic-regexp`, `--extended-regexp`,
@@@ -3370,13 -3336,12 +3379,13 @@@ submodule.<name>.ignore:
  submodule.<name>.active::
        Boolean value indicating if the submodule is of interest to git
        commands.  This config option takes precedence over the
 -      submodule.active config option.
 +      submodule.active config option. See linkgit:gitsubmodules[7] for
 +      details.
  
  submodule.active::
        A repeated field which contains a pathspec used to match against a
        submodule's path to determine if the submodule is of interest to git
 -      commands.
 +      commands. See linkgit:gitsubmodules[7] for details.
  
  submodule.recurse::
        Specifies if commands recurse into submodules by default. This
@@@ -3523,13 -3488,6 +3532,13 @@@ Note that this configuration variable i
  repository-level config (this is a safety measure against fetching from
  untrusted repositories).
  
 +uploadpack.allowRefInWant::
 +      If this option is set, `upload-pack` will support the `ref-in-want`
 +      feature of the protocol version 2 `fetch` command.  This feature
 +      is intended for the benefit of load-balanced servers which may
 +      not have the same view of what OIDs their refs point to due to
 +      replication delay.
 +
  url.<base>.insteadOf::
        Any URL that starts with this value will be rewritten to
        start, instead, with <base>. In cases where some site serves a
diff --combined Makefile
+++ b/Makefile
@@@ -620,7 -620,6 +620,7 @@@ SCRIPT_LIB += git-mergetool--li
  SCRIPT_LIB += git-parse-remote
  SCRIPT_LIB += git-rebase--am
  SCRIPT_LIB += git-rebase--interactive
 +SCRIPT_LIB += git-rebase--preserve-merges
  SCRIPT_LIB += git-rebase--merge
  SCRIPT_LIB += git-sh-setup
  SCRIPT_LIB += git-sh-i18n
@@@ -690,6 -689,7 +690,6 @@@ PROGRAM_OBJS += http-backend.
  PROGRAM_OBJS += imap-send.o
  PROGRAM_OBJS += sh-i18n--envsubst.o
  PROGRAM_OBJS += shell.o
 -PROGRAM_OBJS += show-index.o
  PROGRAM_OBJS += remote-testsvn.o
  
  # Binary suffix, set to .exe for Windows builds
@@@ -893,6 -893,7 +893,7 @@@ LIB_OBJS += merge-recursive.
  LIB_OBJS += mergesort.o
  LIB_OBJS += name-hash.o
  LIB_OBJS += negotiator/default.o
+ LIB_OBJS += negotiator/skipping.o
  LIB_OBJS += notes.o
  LIB_OBJS += notes-cache.o
  LIB_OBJS += notes-merge.o
@@@ -1079,7 -1080,6 +1080,7 @@@ BUILTIN_OBJS += builtin/send-pack.
  BUILTIN_OBJS += builtin/serve.o
  BUILTIN_OBJS += builtin/shortlog.o
  BUILTIN_OBJS += builtin/show-branch.o
 +BUILTIN_OBJS += builtin/show-index.o
  BUILTIN_OBJS += builtin/show-ref.o
  BUILTIN_OBJS += builtin/stripspace.o
  BUILTIN_OBJS += builtin/submodule--helper.o
@@@ -1354,19 -1354,17 +1355,19 @@@ ifdef APPLE_COMMON_CRYPT
        LIB_4_CRYPTO += -framework Security -framework CoreFoundation
  endif
  endif
 -ifdef NEEDS_LIBICONV
 -      ifdef ICONVDIR
 -              BASIC_CFLAGS += -I$(ICONVDIR)/include
 -              ICONV_LINK = -L$(ICONVDIR)/$(lib) $(CC_LD_DYNPATH)$(ICONVDIR)/$(lib)
 -      else
 -              ICONV_LINK =
 -      endif
 -      ifdef NEEDS_LIBINTL_BEFORE_LIBICONV
 -              ICONV_LINK += -lintl
 +ifndef NO_ICONV
 +      ifdef NEEDS_LIBICONV
 +              ifdef ICONVDIR
 +                      BASIC_CFLAGS += -I$(ICONVDIR)/include
 +                      ICONV_LINK = -L$(ICONVDIR)/$(lib) $(CC_LD_DYNPATH)$(ICONVDIR)/$(lib)
 +              else
 +                      ICONV_LINK =
 +              endif
 +              ifdef NEEDS_LIBINTL_BEFORE_LIBICONV
 +                      ICONV_LINK += -lintl
 +              endif
 +              EXTLIBS += $(ICONV_LINK) -liconv
        endif
 -      EXTLIBS += $(ICONV_LINK) -liconv
  endif
  ifdef NEEDS_LIBGEN
        EXTLIBS += -lgen
@@@ -2023,9 -2021,8 +2024,9 @@@ version.sp version.s version.o: GIT-VER
  version.sp version.s version.o: EXTRA_CPPFLAGS = \
        '-DGIT_VERSION="$(GIT_VERSION)"' \
        '-DGIT_USER_AGENT=$(GIT_USER_AGENT_CQ_SQ)' \
 -      '-DGIT_BUILT_FROM_COMMIT="$(shell GIT_CEILING_DIRECTORIES=\"$(CURDIR)/..\" \
 -              git rev-parse -q --verify HEAD || :)"'
 +      '-DGIT_BUILT_FROM_COMMIT="$(shell \
 +              GIT_CEILING_DIRECTORIES="$(CURDIR)/.." \
 +              git rev-parse -q --verify HEAD 2>/dev/null)"'
  
  $(BUILT_INS): git$X
        $(QUIET_BUILT_IN)$(RM) $@ && \
@@@ -2113,7 -2110,7 +2114,7 @@@ $(SCRIPT_PERL_GEN): % : %.perl GIT-PERL
        $(QUIET_GEN)$(RM) $@ $@+ && \
        sed -e '1{' \
            -e '        s|#!.*perl|#!$(PERL_PATH_SQ)|' \
 -          -e '        rGIT-PERL-HEADER' \
 +          -e '        r GIT-PERL-HEADER' \
            -e '        G' \
            -e '}' \
            -e 's/@@GIT_VERSION@@/$(GIT_VERSION)/g' \
@@@ -2401,7 -2398,6 +2402,7 @@@ LOCALIZED_C = $(C_OBJ:o=c) $(LIB_H) $(G
  LOCALIZED_SH = $(SCRIPT_SH)
  LOCALIZED_SH += git-parse-remote.sh
  LOCALIZED_SH += git-rebase--interactive.sh
 +LOCALIZED_SH += git-rebase--preserve-merges.sh
  LOCALIZED_SH += git-sh-setup.sh
  LOCALIZED_PERL = $(SCRIPT_PERL)
  
diff --combined fetch-pack.c
@@@ -18,8 -18,6 +18,8 @@@
  #include "sha1-array.h"
  #include "oidset.h"
  #include "packfile.h"
 +#include "object-store.h"
 +#include "connected.h"
  #include "fetch-negotiator.h"
  
  static int transfer_unpack_limit = -1;
@@@ -35,6 -33,7 +35,7 @@@ static int agent_supported
  static int server_supports_filtering;
  static struct lock_file shallow_lock;
  static const char *alternate_shallow_file;
+ static char *negotiation_algorithm;
  
  /* Remember to update object flag allocation in object.h */
  #define COMPLETE      (1U << 0)
@@@ -78,7 -77,7 +79,7 @@@ static void cache_one_alternate(const c
                                void *vcache)
  {
        struct alternate_object_cache *cache = vcache;
 -      struct object *obj = parse_object(oid);
 +      struct object *obj = parse_object(the_repository, oid);
  
        if (!obj || (obj->flags & ALTERNATE))
                return;
@@@ -109,9 -108,7 +110,9 @@@ static int rev_list_insert_ref(struct f
                               const char *refname,
                               const struct object_id *oid)
  {
 -      struct object *o = deref_tag(parse_object(oid), refname, 0);
 +      struct object *o = deref_tag(the_repository,
 +                                   parse_object(the_repository, oid),
 +                                   refname, 0);
  
        if (o && o->type == OBJ_COMMIT)
                negotiator->add_tip(negotiator, (struct commit *)o);
@@@ -217,22 -214,6 +218,22 @@@ static int next_flush(int stateless_rpc
        return count;
  }
  
 +static void mark_tips(struct fetch_negotiator *negotiator,
 +                    const struct oid_array *negotiation_tips)
 +{
 +      int i;
 +
 +      if (!negotiation_tips) {
 +              for_each_ref(rev_list_insert_ref_oid, negotiator);
 +              return;
 +      }
 +
 +      for (i = 0; i < negotiation_tips->nr; i++)
 +              rev_list_insert_ref(negotiator, NULL,
 +                                  &negotiation_tips->oid[i]);
 +      return;
 +}
 +
  static int find_common(struct fetch_negotiator *negotiator,
                       struct fetch_pack_args *args,
                       int fd[2], struct object_id *result_oid,
        if (args->stateless_rpc && multi_ack == 1)
                die(_("--stateless-rpc requires multi_ack_detailed"));
  
 -      for_each_ref(rev_list_insert_ref_oid, negotiator);
 +      mark_tips(negotiator, args->negotiation_tips);
        for_each_cached_alternate(negotiator, insert_one_alternate_object);
  
        fetching = 0;
                 * interested in the case we *know* the object is
                 * reachable and we have already scanned it.
                 */
 -              if (((o = lookup_object(remote->hash)) != NULL) &&
 +              if (((o = lookup_object(the_repository, remote->hash)) != NULL) &&
                                (o->flags & COMPLETE)) {
                        continue;
                }
                return 1;
        }
  
 -      if (is_repository_shallow())
 +      if (is_repository_shallow(the_repository))
                write_shallow_commits(&req_buf, 1, NULL);
        if (args->depth > 0)
                packet_buf_write(&req_buf, "deepen %d", args->depth);
                        if (skip_prefix(line, "shallow ", &arg)) {
                                if (get_oid_hex(arg, &oid))
                                        die(_("invalid shallow line: %s"), line);
 -                              register_shallow(&oid);
 +                              register_shallow(the_repository, &oid);
                                continue;
                        }
                        if (skip_prefix(line, "unshallow ", &arg)) {
                                if (get_oid_hex(arg, &oid))
                                        die(_("invalid unshallow line: %s"), line);
 -                              if (!lookup_object(oid.hash))
 +                              if (!lookup_object(the_repository, oid.hash))
                                        die(_("object not found: %s"), line);
                                /* make sure that it is parsed as shallow */
 -                              if (!parse_object(&oid))
 +                              if (!parse_object(the_repository, &oid))
                                        die(_("error in object: %s"), line);
                                if (unregister_shallow(&oid))
                                        die(_("no shallow found: %s"), line);
                                case ACK_ready:
                                case ACK_continue: {
                                        struct commit *commit =
 -                                              lookup_commit(result_oid);
 +                                              lookup_commit(the_repository,
 +                                                            result_oid);
                                        int was_common;
 +
                                        if (!commit)
                                                die(_("invalid commit %s"), oid_to_hex(result_oid));
                                        was_common = negotiator->ack(negotiator, commit);
@@@ -482,14 -461,14 +483,14 @@@ static struct commit_list *complete
  
  static int mark_complete(const struct object_id *oid)
  {
 -      struct object *o = parse_object(oid);
 +      struct object *o = parse_object(the_repository, oid);
  
        while (o && o->type == OBJ_TAG) {
                struct tag *t = (struct tag *) o;
                if (!t->tagged)
                        break; /* broken repository */
                o->flags |= COMPLETE;
 -              o = parse_object(&t->tagged->oid);
 +              o = parse_object(the_repository, &t->tagged->oid);
        }
        if (o && o->type == OBJ_COMMIT) {
                struct commit *commit = (struct commit *)o;
@@@ -570,11 -549,11 +571,11 @@@ static void filter_refs(struct fetch_pa
                                }
                                i++;
                        }
 -              }
  
 -              if (!keep && args->fetch_all &&
 -                  (!args->deepen || !starts_with(ref->name, "refs/tags/")))
 -                      keep = 1;
 +                      if (!keep && args->fetch_all &&
 +                          (!args->deepen || !starts_with(ref->name, "refs/tags/")))
 +                              keep = 1;
 +              }
  
                if (keep) {
                        *newtail = ref;
@@@ -690,7 -669,7 +691,7 @@@ static void mark_complete_and_common_re
  
                if (!has_object_file_with_flags(&ref->old_oid, flags))
                        continue;
 -              o = parse_object(&ref->old_oid);
 +              o = parse_object(the_repository, &ref->old_oid);
                if (!o)
                        continue;
  
                 * Don't mark them common yet; the server has to be told so first.
                 */
                for (ref = *refs; ref; ref = ref->next) {
 -                      struct object *o = deref_tag(lookup_object(ref->old_oid.hash),
 +                      struct object *o = deref_tag(the_repository,
 +                                                   lookup_object(the_repository,
 +                                                   ref->old_oid.hash),
                                                     NULL, 0);
  
                        if (!o || o->type != OBJ_COMMIT || !(o->flags & COMPLETE))
@@@ -751,7 -728,7 +752,7 @@@ static int everything_local(struct fetc
                const struct object_id *remote = &ref->old_oid;
                struct object *o;
  
 -              o = lookup_object(remote->hash);
 +              o = lookup_object(the_repository, remote->hash);
                if (!o || !(o->flags & COMPLETE)) {
                        retval = 0;
                        print_verbose(args, "want %s (%s)", oid_to_hex(remote),
@@@ -913,12 -890,12 +914,12 @@@ static struct ref *do_fetch_pack(struc
        const char *agent_feature;
        int agent_len;
        struct fetch_negotiator negotiator;
-       fetch_negotiator_init(&negotiator);
+       fetch_negotiator_init(&negotiator, negotiation_algorithm);
  
        sort_ref_list(&ref, ref_compare_name);
        QSORT(sought, nr_sought, cmp_ref_by_name);
  
 -      if ((args->depth > 0 || is_repository_shallow()) && !server_supports("shallow"))
 +      if ((args->depth > 0 || is_repository_shallow(the_repository)) && !server_supports("shallow"))
                die(_("Server does not support shallow clients"));
        if (args->depth > 0 || args->deepen_since || args->deepen_not)
                args->deepen = 1;
  static void add_shallow_requests(struct strbuf *req_buf,
                                 const struct fetch_pack_args *args)
  {
 -      if (is_repository_shallow())
 +      if (is_repository_shallow(the_repository))
                write_shallow_commits(req_buf, 1, NULL);
        if (args->depth > 0)
                packet_buf_write(req_buf, "deepen %d", args->depth);
  
  static void add_wants(const struct ref *wants, struct strbuf *req_buf)
  {
 +      int use_ref_in_want = server_supports_feature("fetch", "ref-in-want", 0);
 +
        for ( ; wants ; wants = wants->next) {
                const struct object_id *remote = &wants->old_oid;
 -              const char *remote_hex;
                struct object *o;
  
                /*
                 * interested in the case we *know* the object is
                 * reachable and we have already scanned it.
                 */
 -              if (((o = lookup_object(remote->hash)) != NULL) &&
 +              if (((o = lookup_object(the_repository, remote->hash)) != NULL) &&
                    (o->flags & COMPLETE)) {
                        continue;
                }
  
 -              remote_hex = oid_to_hex(remote);
 -              packet_buf_write(req_buf, "want %s\n", remote_hex);
 +              if (!use_ref_in_want || wants->exact_oid)
 +                      packet_buf_write(req_buf, "want %s\n", oid_to_hex(remote));
 +              else
 +                      packet_buf_write(req_buf, "want-ref %s\n", wants->name);
        }
  }
  
@@@ -1137,7 -1111,7 +1138,7 @@@ static int send_fetch_request(struct fe
        /* Add shallow-info and deepen request */
        if (server_supports_feature("fetch", "shallow", 0))
                add_shallow_requests(&req_buf, args);
 -      else if (is_repository_shallow() || args->deepen)
 +      else if (is_repository_shallow(the_repository) || args->deepen)
                die(_("Server does not support shallow requests"));
  
        /* Add filter */
@@@ -1218,7 -1192,7 +1219,7 @@@ static int process_acks(struct fetch_ne
                        if (!get_oid_hex(arg, &oid)) {
                                struct commit *commit;
                                oidset_insert(common, &oid);
 -                              commit = lookup_commit(&oid);
 +                              commit = lookup_commit(the_repository, &oid);
                                negotiator->ack(negotiator, commit);
                        }
                        continue;
@@@ -1251,16 -1225,16 +1252,16 @@@ static void receive_shallow_info(struc
                if (skip_prefix(reader->line, "shallow ", &arg)) {
                        if (get_oid_hex(arg, &oid))
                                die(_("invalid shallow line: %s"), reader->line);
 -                      register_shallow(&oid);
 +                      register_shallow(the_repository, &oid);
                        continue;
                }
                if (skip_prefix(reader->line, "unshallow ", &arg)) {
                        if (get_oid_hex(arg, &oid))
                                die(_("invalid unshallow line: %s"), reader->line);
 -                      if (!lookup_object(oid.hash))
 +                      if (!lookup_object(the_repository, oid.hash))
                                die(_("object not found: %s"), reader->line);
                        /* make sure that it is parsed as shallow */
 -                      if (!parse_object(&oid))
 +                      if (!parse_object(the_repository, &oid))
                                die(_("error in object: %s"), reader->line);
                        if (unregister_shallow(&oid))
                                die(_("no shallow found: %s"), reader->line);
        args->deepen = 1;
  }
  
 +static void receive_wanted_refs(struct packet_reader *reader, struct ref *refs)
 +{
 +      process_section_header(reader, "wanted-refs", 0);
 +      while (packet_reader_read(reader) == PACKET_READ_NORMAL) {
 +              struct object_id oid;
 +              const char *end;
 +              struct ref *r = NULL;
 +
 +              if (parse_oid_hex(reader->line, &oid, &end) || *end++ != ' ')
 +                      die("expected wanted-ref, got '%s'", reader->line);
 +
 +              for (r = refs; r; r = r->next) {
 +                      if (!strcmp(end, r->name)) {
 +                              oidcpy(&r->old_oid, &oid);
 +                              break;
 +                      }
 +              }
 +
 +              if (!r)
 +                      die("unexpected wanted-ref: '%s'", reader->line);
 +      }
 +
 +      if (reader->status != PACKET_READ_DELIM)
 +              die("error processing wanted refs: %d", reader->status);
 +}
 +
  enum fetch_state {
        FETCH_CHECK_LOCAL = 0,
        FETCH_SEND_REQUEST,
@@@ -1324,7 -1272,7 +1325,7 @@@ static struct ref *do_fetch_pack_v2(str
        int in_vain = 0;
        int haves_to_send = INITIAL_FLUSH;
        struct fetch_negotiator negotiator;
-       fetch_negotiator_init(&negotiator);
+       fetch_negotiator_init(&negotiator, negotiation_algorithm);
        packet_reader_init(&reader, fd[0], NULL, 0,
                           PACKET_READ_CHOMP_NEWLINE);
  
                        else
                                state = FETCH_SEND_REQUEST;
  
 -                      for_each_ref(rev_list_insert_ref_oid, &negotiator);
 +                      mark_tips(&negotiator, args->negotiation_tips);
                        for_each_cached_alternate(&negotiator,
                                                  insert_one_alternate_object);
                        break;
                        if (process_section_header(&reader, "shallow-info", 1))
                                receive_shallow_info(args, &reader);
  
 +                      if (process_section_header(&reader, "wanted-refs", 1))
 +                              receive_wanted_refs(&reader, ref);
 +
                        /* get the pack */
                        process_section_header(&reader, "packfile", 0);
                        if (get_pack(args, fd, pack_lockfile))
@@@ -1406,6 -1351,8 +1407,8 @@@ static void fetch_pack_config(void
        git_config_get_bool("repack.usedeltabaseoffset", &prefer_ofs_delta);
        git_config_get_bool("fetch.fsckobjects", &fetch_fsck_objects);
        git_config_get_bool("transfer.fsckobjects", &transfer_fsck_objects);
+       git_config_get_string("fetch.negotiationalgorithm",
+                             &negotiation_algorithm);
  
        git_config(git_default_config, NULL);
  }
@@@ -1445,17 -1392,16 +1448,17 @@@ static int remove_duplicates_in_refs(st
  }
  
  static void update_shallow(struct fetch_pack_args *args,
 -                         struct ref **sought, int nr_sought,
 +                         struct ref *refs,
                           struct shallow_info *si)
  {
        struct oid_array ref = OID_ARRAY_INIT;
        int *status;
        int i;
 +      struct ref *r;
  
        if (args->deepen && alternate_shallow_file) {
                if (*alternate_shallow_file == '\0') { /* --unshallow */
 -                      unlink_or_warn(git_path_shallow());
 +                      unlink_or_warn(git_path_shallow(the_repository));
                        rollback_lock_file(&shallow_lock);
                } else
                        commit_lock_file(&shallow_lock);
        remove_nonexistent_theirs_shallow(si);
        if (!si->nr_ours && !si->nr_theirs)
                return;
 -      for (i = 0; i < nr_sought; i++)
 -              oid_array_append(&ref, &sought[i]->old_oid);
 +      for (r = refs; r; r = r->next)
 +              oid_array_append(&ref, &r->old_oid);
        si->ref = &ref;
  
        if (args->update_shallow) {
         * remote is also shallow, check what ref is safe to update
         * without updating .git/shallow
         */
 -      status = xcalloc(nr_sought, sizeof(*status));
 +      status = xcalloc(ref.nr, sizeof(*status));
        assign_shallow_commits_to_refs(si, NULL, status);
        if (si->nr_ours || si->nr_theirs) {
 -              for (i = 0; i < nr_sought; i++)
 +              for (r = refs, i = 0; r; r = r->next, i++)
                        if (status[i])
 -                              sought[i]->status = REF_STATUS_REJECT_SHALLOW;
 +                              r->status = REF_STATUS_REJECT_SHALLOW;
        }
        free(status);
        oid_array_clear(&ref);
  }
  
 +static int iterate_ref_map(void *cb_data, struct object_id *oid)
 +{
 +      struct ref **rm = cb_data;
 +      struct ref *ref = *rm;
 +
 +      if (!ref)
 +              return -1; /* end of the list */
 +      *rm = ref->next;
 +      oidcpy(oid, &ref->old_oid);
 +      return 0;
 +}
 +
  struct ref *fetch_pack(struct fetch_pack_args *args,
                       int fd[], struct child_process *conn,
                       const struct ref *ref,
                ref_cpy = do_fetch_pack(args, fd, ref, sought, nr_sought,
                                        &si, pack_lockfile);
        reprepare_packed_git(the_repository);
 -      update_shallow(args, sought, nr_sought, &si);
 +
 +      if (!args->cloning && args->deepen) {
 +              struct check_connected_options opt = CHECK_CONNECTED_INIT;
 +              struct ref *iterator = ref_cpy;
 +              opt.shallow_file = alternate_shallow_file;
 +              if (args->deepen)
 +                      opt.is_deepening_fetch = 1;
 +              if (check_connected(iterate_ref_map, &iterator, &opt)) {
 +                      error(_("remote did not send all necessary objects"));
 +                      free_refs(ref_cpy);
 +                      ref_cpy = NULL;
 +                      rollback_lock_file(&shallow_lock);
 +                      goto cleanup;
 +              }
 +              args->connectivity_checked = 1;
 +      }
 +
 +      update_shallow(args, ref_cpy, &si);
 +cleanup:
        clear_shallow_info(&si);
        return ref_cpy;
  }
diff --combined negotiator/skipping.c
index 0000000,74d25e8..dffbc76
mode 000000,100644..100644
--- /dev/null
@@@ -1,0 -1,250 +1,250 @@@
 -      struct object *o = deref_tag(parse_object(oid), refname, 0);
+ #include "cache.h"
+ #include "skipping.h"
+ #include "../commit.h"
+ #include "../fetch-negotiator.h"
+ #include "../prio-queue.h"
+ #include "../refs.h"
+ #include "../tag.h"
+ /* Remember to update object flag allocation in object.h */
+ /*
+  * Both us and the server know that both parties have this object.
+  */
+ #define COMMON                (1U << 2)
+ /*
+  * The server has told us that it has this object. We still need to tell the
+  * server that we have this object (or one of its descendants), but since we are
+  * going to do that, we do not need to tell the server about its ancestors.
+  */
+ #define ADVERTISED    (1U << 3)
+ /*
+  * This commit has entered the priority queue.
+  */
+ #define SEEN          (1U << 4)
+ /*
+  * This commit has left the priority queue.
+  */
+ #define POPPED                (1U << 5)
+ static int marked;
+ /*
+  * An entry in the priority queue.
+  */
+ struct entry {
+       struct commit *commit;
+       /*
+        * Used only if commit is not COMMON.
+        */
+       uint16_t original_ttl;
+       uint16_t ttl;
+ };
+ struct data {
+       struct prio_queue rev_list;
+       /*
+        * The number of non-COMMON commits in rev_list.
+        */
+       int non_common_revs;
+ };
+ static int compare(const void *a_, const void *b_, void *unused)
+ {
+       const struct entry *a = a_;
+       const struct entry *b = b_;
+       return compare_commits_by_commit_date(a->commit, b->commit, NULL);
+ }
+ static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
+ {
+       struct entry *entry;
+       commit->object.flags |= mark | SEEN;
+       entry = xcalloc(1, sizeof(*entry));
+       entry->commit = commit;
+       prio_queue_put(&data->rev_list, entry);
+       if (!(mark & COMMON))
+               data->non_common_revs++;
+       return entry;
+ }
+ static int clear_marks(const char *refname, const struct object_id *oid,
+                      int flag, void *cb_data)
+ {
++      struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
+       if (o && o->type == OBJ_COMMIT)
+               clear_commit_marks((struct commit *)o,
+                                  COMMON | ADVERTISED | SEEN | POPPED);
+       return 0;
+ }
+ /*
+  * Mark this SEEN commit and all its SEEN ancestors as COMMON.
+  */
+ static void mark_common(struct data *data, struct commit *c)
+ {
+       struct commit_list *p;
+       if (c->object.flags & COMMON)
+               return;
+       c->object.flags |= COMMON;
+       if (!(c->object.flags & POPPED))
+               data->non_common_revs--;
+       if (!c->object.parsed)
+               return;
+       for (p = c->parents; p; p = p->next) {
+               if (p->item->object.flags & SEEN)
+                       mark_common(data, p->item);
+       }
+ }
+ /*
+  * Ensure that the priority queue has an entry for to_push, and ensure that the
+  * entry has the correct flags and ttl.
+  *
+  * This function returns 1 if an entry was found or created, and 0 otherwise
+  * (because the entry for this commit had already been popped).
+  */
+ static int push_parent(struct data *data, struct entry *entry,
+                      struct commit *to_push)
+ {
+       struct entry *parent_entry;
+       if (to_push->object.flags & SEEN) {
+               int i;
+               if (to_push->object.flags & POPPED)
+                       /*
+                        * The entry for this commit has already been popped,
+                        * due to clock skew. Pretend that this parent does not
+                        * exist.
+                        */
+                       return 0;
+               /*
+                * Find the existing entry and use it.
+                */
+               for (i = 0; i < data->rev_list.nr; i++) {
+                       parent_entry = data->rev_list.array[i].data;
+                       if (parent_entry->commit == to_push)
+                               goto parent_found;
+               }
+               BUG("missing parent in priority queue");
+ parent_found:
+               ;
+       } else {
+               parent_entry = rev_list_push(data, to_push, 0);
+       }
+       if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
+               mark_common(data, to_push);
+       } else {
+               uint16_t new_original_ttl = entry->ttl
+                       ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
+               uint16_t new_ttl = entry->ttl
+                       ? entry->ttl - 1 : new_original_ttl;
+               if (parent_entry->original_ttl < new_original_ttl) {
+                       parent_entry->original_ttl = new_original_ttl;
+                       parent_entry->ttl = new_ttl;
+               }
+       }
+       return 1;
+ }
+ static const struct object_id *get_rev(struct data *data)
+ {
+       struct commit *to_send = NULL;
+       while (to_send == NULL) {
+               struct entry *entry;
+               struct commit *commit;
+               struct commit_list *p;
+               int parent_pushed = 0;
+               if (data->rev_list.nr == 0 || data->non_common_revs == 0)
+                       return NULL;
+               entry = prio_queue_get(&data->rev_list);
+               commit = entry->commit;
+               commit->object.flags |= POPPED;
+               if (!(commit->object.flags & COMMON))
+                       data->non_common_revs--;
+               if (!(commit->object.flags & COMMON) && !entry->ttl)
+                       to_send = commit;
+               parse_commit(commit);
+               for (p = commit->parents; p; p = p->next)
+                       parent_pushed |= push_parent(data, entry, p->item);
+               if (!(commit->object.flags & COMMON) && !parent_pushed)
+                       /*
+                        * This commit has no parents, or all of its parents
+                        * have already been popped (due to clock skew), so send
+                        * it anyway.
+                        */
+                       to_send = commit;
+               free(entry);
+       }
+       return &to_send->object.oid;
+ }
+ static void known_common(struct fetch_negotiator *n, struct commit *c)
+ {
+       if (c->object.flags & SEEN)
+               return;
+       rev_list_push(n->data, c, ADVERTISED);
+ }
+ static void add_tip(struct fetch_negotiator *n, struct commit *c)
+ {
+       n->known_common = NULL;
+       if (c->object.flags & SEEN)
+               return;
+       rev_list_push(n->data, c, 0);
+ }
+ static const struct object_id *next(struct fetch_negotiator *n)
+ {
+       n->known_common = NULL;
+       n->add_tip = NULL;
+       return get_rev(n->data);
+ }
+ static int ack(struct fetch_negotiator *n, struct commit *c)
+ {
+       int known_to_be_common = !!(c->object.flags & COMMON);
+       if (!(c->object.flags & SEEN))
+               die("received ack for commit %s not sent as 'have'\n",
+                   oid_to_hex(&c->object.oid));
+       mark_common(n->data, c);
+       return known_to_be_common;
+ }
+ static void release(struct fetch_negotiator *n)
+ {
+       clear_prio_queue(&((struct data *)n->data)->rev_list);
+       FREE_AND_NULL(n->data);
+ }
+ void skipping_negotiator_init(struct fetch_negotiator *negotiator)
+ {
+       struct data *data;
+       negotiator->known_common = known_common;
+       negotiator->add_tip = add_tip;
+       negotiator->next = next;
+       negotiator->ack = ack;
+       negotiator->release = release;
+       negotiator->data = data = xcalloc(1, sizeof(*data));
+       data->rev_list.compare = compare;
+       if (marked)
+               for_each_ref(clear_marks, NULL);
+       marked = 1;
+ }