negotiator/skipping.c

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