negotiator/skipping.c

   1 #include "cache.h"
   2 #include "skipping.h"
   3 #include "../commit.h"
   4 #include "../fetch-negotiator.h"
   5 #include "../prio-queue.h"
   6 #include "../refs.h"
   7 #include "../tag.h"
   8
   9 /* Remember to update object flag allocation in object.h */
  10 /*
  11  * Both us and the server know that both parties have this object.
  12  */
  13 #define COMMON          (1U << 2)
  14 /*
  15  * The server has told us that it has this object. We still need to tell the
  16  * server that we have this object (or one of its descendants), but since we are
  17  * going to do that, we do not need to tell the server about its ancestors.
  18  */
  19 #define ADVERTISED      (1U << 3)
  20 /*
  21  * This commit has entered the priority queue.
  22  */
  23 #define SEEN            (1U << 4)
  24 /*
  25  * This commit has left the priority queue.
  26  */
  27 #define POPPED          (1U << 5)
  28
  29 static int marked;
  30
  31 /*
  32  * An entry in the priority queue.
  33  */
  34 struct entry {
  35         struct commit *commit;
  36
  37         /*
  38          * Used only if commit is not COMMON.
  39          */
  40         uint16_t original_ttl;
  41         uint16_t ttl;
  42 };
  43
  44 struct data {
  45         struct prio_queue rev_list;
  46
  47         /*
  48          * The number of non-COMMON commits in rev_list.
  49          */
  50         int non_common_revs;
  51 };
  52
  53 static int compare(const void *a_, const void *b_, void *unused)
  54 {
  55         const struct entry *a = a_;
  56         const struct entry *b = b_;
  57         return compare_commits_by_commit_date(a->commit, b->commit, NULL);
  58 }
  59
  60 static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark)
  61 {
  62         struct entry *entry;
  63         commit->object.flags |= mark | SEEN;
  64
  65         CALLOC_ARRAY(entry, 1);
  66         entry->commit = commit;
  67         prio_queue_put(&data->rev_list, entry);
  68
  69         if (!(mark & COMMON))
  70                 data->non_common_revs++;
  71         return entry;
  72 }
  73
  74 static int clear_marks(const char *refname, const struct object_id *oid,
  75                        int flag UNUSED,
  76                        void *cb_data UNUSED)
  77 {
  78         struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
  79
  80         if (o && o->type == OBJ_COMMIT)
  81                 clear_commit_marks((struct commit *)o,
  82                                    COMMON | ADVERTISED | SEEN | POPPED);
  83         return 0;
  84 }
  85
  86 /*
  87  * Mark this SEEN commit and all its SEEN ancestors as COMMON.
  88  */
  89 static void mark_common(struct data *data, struct commit *c)
  90 {
  91         struct commit_list *p;
  92
  93         if (c->object.flags & COMMON)
  94                 return;
  95         c->object.flags |= COMMON;
  96         if (!(c->object.flags & POPPED))
  97                 data->non_common_revs--;
  98
  99         if (!c->object.parsed)
 100                 return;
 101         for (p = c->parents; p; p = p->next) {
 102                 if (p->item->object.flags & SEEN)
 103                         mark_common(data, p->item);
 104         }
 105 }
 106
 107 /*
 108  * Ensure that the priority queue has an entry for to_push, and ensure that the
 109  * entry has the correct flags and ttl.
 110  *
 111  * This function returns 1 if an entry was found or created, and 0 otherwise
 112  * (because the entry for this commit had already been popped).
 113  */
 114 static int push_parent(struct data *data, struct entry *entry,
 115                        struct commit *to_push)
 116 {
 117         struct entry *parent_entry;
 118
 119         if (to_push->object.flags & SEEN) {
 120                 int i;
 121                 if (to_push->object.flags & POPPED)
 122                         /*
 123                          * The entry for this commit has already been popped,
 124                          * due to clock skew. Pretend that this parent does not
 125                          * exist.
 126                          */
 127                         return 0;
 128                 /*
 129                  * Find the existing entry and use it.
 130                  */
 131                 for (i = 0; i < data->rev_list.nr; i++) {
 132                         parent_entry = data->rev_list.array[i].data;
 133                         if (parent_entry->commit == to_push)
 134                                 goto parent_found;
 135                 }
 136                 BUG("missing parent in priority queue");
 137 parent_found:
 138                 ;
 139         } else {
 140                 parent_entry = rev_list_push(data, to_push, 0);
 141         }
 142
 143         if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
 144                 mark_common(data, to_push);
 145         } else {
 146                 uint16_t new_original_ttl = entry->ttl
 147                         ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
 148                 uint16_t new_ttl = entry->ttl
 149                         ? entry->ttl - 1 : new_original_ttl;
 150                 if (parent_entry->original_ttl < new_original_ttl) {
 151                         parent_entry->original_ttl = new_original_ttl;
 152                         parent_entry->ttl = new_ttl;
 153                 }
 154         }
 155
 156         return 1;
 157 }
 158
 159 static const struct object_id *get_rev(struct data *data)
 160 {
 161         struct commit *to_send = NULL;
 162
 163         while (to_send == NULL) {
 164                 struct entry *entry;
 165                 struct commit *commit;
 166                 struct commit_list *p;
 167                 int parent_pushed = 0;
 168
 169                 if (data->rev_list.nr == 0 || data->non_common_revs == 0)
 170                         return NULL;
 171
 172                 entry = prio_queue_get(&data->rev_list);
 173                 commit = entry->commit;
 174                 commit->object.flags |= POPPED;
 175                 if (!(commit->object.flags & COMMON))
 176                         data->non_common_revs--;
 177
 178                 if (!(commit->object.flags & COMMON) && !entry->ttl)
 179                         to_send = commit;
 180
 181                 parse_commit(commit);
 182                 for (p = commit->parents; p; p = p->next)
 183                         parent_pushed |= push_parent(data, entry, p->item);
 184
 185                 if (!(commit->object.flags & COMMON) && !parent_pushed)
 186                         /*
 187                          * This commit has no parents, or all of its parents
 188                          * have already been popped (due to clock skew), so send
 189                          * it anyway.
 190                          */
 191                         to_send = commit;
 192
 193                 free(entry);
 194         }
 195
 196         return &to_send->object.oid;
 197 }
 198
 199 static void known_common(struct fetch_negotiator *n, struct commit *c)
 200 {
 201         if (c->object.flags & SEEN)
 202                 return;
 203         rev_list_push(n->data, c, ADVERTISED);
 204 }
 205
 206 static void add_tip(struct fetch_negotiator *n, struct commit *c)
 207 {
 208         n->known_common = NULL;
 209         if (c->object.flags & SEEN)
 210                 return;
 211         rev_list_push(n->data, c, 0);
 212 }
 213
 214 static const struct object_id *next(struct fetch_negotiator *n)
 215 {
 216         n->known_common = NULL;
 217         n->add_tip = NULL;
 218         return get_rev(n->data);
 219 }
 220
 221 static int ack(struct fetch_negotiator *n, struct commit *c)
 222 {
 223         int known_to_be_common = !!(c->object.flags & COMMON);
 224         if (!(c->object.flags & SEEN))
 225                 die("received ack for commit %s not sent as 'have'\n",
 226                     oid_to_hex(&c->object.oid));
 227         mark_common(n->data, c);
 228         return known_to_be_common;
 229 }
 230
 231 static void release(struct fetch_negotiator *n)
 232 {
 233         clear_prio_queue(&((struct data *)n->data)->rev_list);
 234         FREE_AND_NULL(n->data);
 235 }
 236
 237 void skipping_negotiator_init(struct fetch_negotiator *negotiator)
 238 {
 239         struct data *data;
 240         negotiator->known_common = known_common;
 241         negotiator->add_tip = add_tip;
 242         negotiator->next = next;
 243         negotiator->ack = ack;
 244         negotiator->release = release;
 245         negotiator->data = CALLOC_ARRAY(data, 1);
 246         data->rev_list.compare = compare;
 247
 248         if (marked)
 249                 for_each_ref(clear_marks, NULL);
 250         marked = 1;
 251 }