| 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 struct reference *ref, void *cb_data UNUSED) |
| 79 | { |
| 80 | struct object *o = deref_tag(the_repository, parse_object(the_repository, ref->oid), |
| 81 | ref->name, 0); |
| 82 | |
| 83 | if (o && o->type == OBJ_COMMIT) |
| 84 | clear_commit_marks((struct commit *)o, |
| 85 | COMMON | ADVERTISED | SEEN | POPPED); |
| 86 | return 0; |
| 87 | } |
| 88 | |
| 89 | /* |
| 90 | * Mark this SEEN commit and all its parsed SEEN ancestors as COMMON. |
| 91 | */ |
| 92 | static void mark_common(struct data *data, struct commit *seen_commit) |
| 93 | { |
| 94 | struct commit_stack stack = COMMIT_STACK_INIT; |
| 95 | struct commit *c; |
| 96 | |
| 97 | if (seen_commit->object.flags & COMMON) |
| 98 | return; |
| 99 | |
| 100 | commit_stack_push(&stack, seen_commit); |
| 101 | seen_commit->object.flags |= COMMON; |
| 102 | while ((c = commit_stack_pop(&stack))) { |
| 103 | struct commit_list *p; |
| 104 | |
| 105 | if (!(c->object.flags & POPPED)) |
| 106 | data->non_common_revs--; |
| 107 | |
| 108 | if (!c->object.parsed) |
| 109 | continue; |
| 110 | for (p = c->parents; p; p = p->next) { |
| 111 | if (!(p->item->object.flags & SEEN) || |
| 112 | (p->item->object.flags & COMMON)) |
| 113 | continue; |
| 114 | |
| 115 | p->item->object.flags |= COMMON; |
| 116 | commit_stack_push(&stack, p->item); |
| 117 | } |
| 118 | } |
| 119 | |
| 120 | commit_stack_clear(&stack); |
| 121 | } |
| 122 | |
| 123 | /* |
| 124 | * Ensure that the priority queue has an entry for to_push, and ensure that the |
| 125 | * entry has the correct flags and ttl. |
| 126 | * |
| 127 | * This function returns 1 if an entry was found or created, and 0 otherwise |
| 128 | * (because the entry for this commit had already been popped). |
| 129 | */ |
| 130 | static int push_parent(struct data *data, struct entry *entry, |
| 131 | struct commit *to_push) |
| 132 | { |
| 133 | struct entry *parent_entry; |
| 134 | |
| 135 | if (to_push->object.flags & SEEN) { |
| 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 (size_t 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'", |
| 241 | oid_to_hex(&c->object.oid)); |
| 242 | mark_common(n->data, c); |
| 243 | return known_to_be_common; |
| 244 | } |
| 245 | |
| 246 | static void have_sent(struct fetch_negotiator *n, struct commit *c) |
| 247 | { |
| 248 | if (repo_parse_commit(the_repository, c)) |
| 249 | return; |
| 250 | mark_common(n->data, c); |
| 251 | } |
| 252 | |
| 253 | static void release(struct fetch_negotiator *n) |
| 254 | { |
| 255 | struct data *data = n->data; |
| 256 | for (size_t i = 0; i < data->rev_list.nr; i++) |
| 257 | free(data->rev_list.array[i].data); |
| 258 | clear_prio_queue(&data->rev_list); |
| 259 | FREE_AND_NULL(data); |
| 260 | } |
| 261 | |
| 262 | void skipping_negotiator_init(struct fetch_negotiator *negotiator) |
| 263 | { |
| 264 | struct data *data; |
| 265 | negotiator->known_common = known_common; |
| 266 | negotiator->add_tip = add_tip; |
| 267 | negotiator->next = next; |
| 268 | negotiator->ack = ack; |
| 269 | negotiator->have_sent = have_sent; |
| 270 | negotiator->release = release; |
| 271 | negotiator->data = CALLOC_ARRAY(data, 1); |
| 272 | data->rev_list.compare = compare; |
| 273 | |
| 274 | if (marked) |
| 275 | refs_for_each_ref(get_main_ref_store(the_repository), |
| 276 | clear_marks, NULL); |
| 277 | marked = 1; |
| 278 | } |