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