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

Simple merge
diff --cc Makefile
Simple merge
diff --cc fetch-pack.c
Simple merge
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;
+ }