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         entry = xcalloc(1, sizeof(*entry));
  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, void *cb_data)
  76 {
  77         struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0);
  78
  79         if (o && o->type == OBJ_COMMIT)
  80                 clear_commit_marks((struct commit *)o,
  81                                    COMMON | ADVERTISED | SEEN | POPPED);
  82         return 0;
  83 }
  84
  85 /*
  86  * Mark this SEEN commit and all its SEEN ancestors as COMMON.
  87  */
  88 static void mark_common(struct data *data, struct commit *c)
  89 {
  90         struct commit_list *p;
  91
  92         if (c->object.flags & COMMON)
  93                 return;
  94         c->object.flags |= COMMON;
  95         if (!(c->object.flags & POPPED))
  96                 data->non_common_revs--;
  97
  98         if (!c->object.parsed)
  99                 return;
 100         for (p = c->parents; p; p = p->next) {
 101                 if (p->item->object.flags & SEEN)
 102                         mark_common(data, p->item);
 103         }
 104 }
 105
 106 /*
 107  * Ensure that the priority queue has an entry for to_push, and ensure that the
 108  * entry has the correct flags and ttl.
 109  *
 110  * This function returns 1 if an entry was found or created, and 0 otherwise
 111  * (because the entry for this commit had already been popped).
 112  */
 113 static int push_parent(struct data *data, struct entry *entry,
 114                        struct commit *to_push)
 115 {
 116         struct entry *parent_entry;
 117
 118         if (to_push->object.flags & SEEN) {
 119                 int i;
 120                 if (to_push->object.flags & POPPED)
 121                         /*
 122                          * The entry for this commit has already been popped,
 123                          * due to clock skew. Pretend that this parent does not
 124                          * exist.
 125                          */
 126                         return 0;
 127                 /*
 128                  * Find the existing entry and use it.
 129                  */
 130                 for (i = 0; i < data->rev_list.nr; i++) {
 131                         parent_entry = data->rev_list.array[i].data;
 132                         if (parent_entry->commit == to_push)
 133                                 goto parent_found;
 134                 }
 135                 BUG("missing parent in priority queue");
 136 parent_found:
 137                 ;
 138         } else {
 139                 parent_entry = rev_list_push(data, to_push, 0);
 140         }
 141
 142         if (entry->commit->object.flags & (COMMON | ADVERTISED)) {
 143                 mark_common(data, to_push);
 144         } else {
 145                 uint16_t new_original_ttl = entry->ttl
 146                         ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1;
 147                 uint16_t new_ttl = entry->ttl
 148                         ? entry->ttl - 1 : new_original_ttl;
 149                 if (parent_entry->original_ttl < new_original_ttl) {
 150                         parent_entry->original_ttl = new_original_ttl;
 151                         parent_entry->ttl = new_ttl;
 152                 }
 153         }
 154
 155         return 1;
 156 }
 157
 158 static const struct object_id *get_rev(struct data *data)
 159 {
 160         struct commit *to_send = NULL;
 161
 162         while (to_send == NULL) {
 163                 struct entry *entry;
 164                 struct commit *commit;
 165                 struct commit_list *p;
 166                 int parent_pushed = 0;
 167
 168                 if (data->rev_list.nr == 0 || data->non_common_revs == 0)
 169                         return NULL;
 170
 171                 entry = prio_queue_get(&data->rev_list);
 172                 commit = entry->commit;
 173                 commit->object.flags |= POPPED;
 174                 if (!(commit->object.flags & COMMON))
 175                         data->non_common_revs--;
 176
 177                 if (!(commit->object.flags & COMMON) && !entry->ttl)
 178                         to_send = commit;
 179
 180                 parse_commit(commit);
 181                 for (p = commit->parents; p; p = p->next)
 182                         parent_pushed |= push_parent(data, entry, p->item);
 183
 184                 if (!(commit->object.flags & COMMON) && !parent_pushed)
 185                         /*
 186                          * This commit has no parents, or all of its parents
 187                          * have already been popped (due to clock skew), so send
 188                          * it anyway.
 189                          */
 190                         to_send = commit;
 191
 192                 free(entry);
 193         }
 194
 195         return &to_send->object.oid;
 196 }
 197
 198 static void known_common(struct fetch_negotiator *n, struct commit *c)
 199 {
 200         if (c->object.flags & SEEN)
 201                 return;
 202         rev_list_push(n->data, c, ADVERTISED);
 203 }
 204
 205 static void add_tip(struct fetch_negotiator *n, struct commit *c)
 206 {
 207         n->known_common = NULL;
 208         if (c->object.flags & SEEN)
 209                 return;
 210         rev_list_push(n->data, c, 0);
 211 }
 212
 213 static const struct object_id *next(struct fetch_negotiator *n)
 214 {
 215         n->known_common = NULL;
 216         n->add_tip = NULL;
 217         return get_rev(n->data);
 218 }
 219
 220 static int ack(struct fetch_negotiator *n, struct commit *c)
 221 {
 222         int known_to_be_common = !!(c->object.flags & COMMON);
 223         if (!(c->object.flags & SEEN))
 224                 die("received ack for commit %s not sent as 'have'\n",
 225                     oid_to_hex(&c->object.oid));
 226         mark_common(n->data, c);
 227         return known_to_be_common;
 228 }
 229
 230 static void release(struct fetch_negotiator *n)
 231 {
 232         clear_prio_queue(&((struct data *)n->data)->rev_list);
 233         FREE_AND_NULL(n->data);
 234 }
 235
 236 void skipping_negotiator_init(struct fetch_negotiator *negotiator)
 237 {
 238         struct data *data;
 239         negotiator->known_common = known_common;
 240         negotiator->add_tip = add_tip;
 241         negotiator->next = next;
 242         negotiator->ack = ack;
 243         negotiator->release = release;
 244         negotiator->data = data = xcalloc(1, sizeof(*data));
 245         data->rev_list.compare = compare;
 246
 247         if (marked)
 248                 for_each_ref(clear_marks, NULL);
 249         marked = 1;
 250 }