negotiator/skipping.c

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