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