diff options
Diffstat (limited to 'negotiator')
| -rw-r--r-- | negotiator/default.c | 176 | ||||
| -rw-r--r-- | negotiator/default.h | 8 | ||||
| -rw-r--r-- | negotiator/skipping.c | 250 | ||||
| -rw-r--r-- | negotiator/skipping.h | 8 |
4 files changed, 442 insertions, 0 deletions
diff --git a/negotiator/default.c b/negotiator/default.c new file mode 100644 index 0000000000..4b78f6bf36 --- /dev/null +++ b/negotiator/default.c @@ -0,0 +1,176 @@ +#include "cache.h" +#include "default.h" +#include "../commit.h" +#include "../fetch-negotiator.h" +#include "../prio-queue.h" +#include "../refs.h" +#include "../tag.h" + +/* Remember to update object flag allocation in object.h */ +#define COMMON (1U << 2) +#define COMMON_REF (1U << 3) +#define SEEN (1U << 4) +#define POPPED (1U << 5) + +static int marked; + +struct negotiation_state { + struct prio_queue rev_list; + int non_common_revs; +}; + +static void rev_list_push(struct negotiation_state *ns, + struct commit *commit, int mark) +{ + if (!(commit->object.flags & mark)) { + commit->object.flags |= mark; + + if (parse_commit(commit)) + return; + + prio_queue_put(&ns->rev_list, commit); + + if (!(commit->object.flags & COMMON)) + ns->non_common_revs++; + } +} + +static int clear_marks(const char *refname, const struct object_id *oid, + int flag, void *cb_data) +{ + struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0); + + if (o && o->type == OBJ_COMMIT) + clear_commit_marks((struct commit *)o, + COMMON | COMMON_REF | SEEN | POPPED); + return 0; +} + +/* + * This function marks a rev and its ancestors as common. + * In some cases, it is desirable to mark only the ancestors (for example + * when only the server does not yet know that they are common). + */ +static void mark_common(struct negotiation_state *ns, struct commit *commit, + int ancestors_only, int dont_parse) +{ + if (commit != NULL && !(commit->object.flags & COMMON)) { + struct object *o = (struct object *)commit; + + if (!ancestors_only) + o->flags |= COMMON; + + if (!(o->flags & SEEN)) + rev_list_push(ns, commit, SEEN); + else { + struct commit_list *parents; + + if (!ancestors_only && !(o->flags & POPPED)) + ns->non_common_revs--; + if (!o->parsed && !dont_parse) + if (parse_commit(commit)) + return; + + for (parents = commit->parents; + parents; + parents = parents->next) + mark_common(ns, parents->item, 0, + dont_parse); + } + } +} + +/* + * Get the next rev to send, ignoring the common. + */ +static const struct object_id *get_rev(struct negotiation_state *ns) +{ + struct commit *commit = NULL; + + while (commit == NULL) { + unsigned int mark; + struct commit_list *parents; + + if (ns->rev_list.nr == 0 || ns->non_common_revs == 0) + return NULL; + + commit = prio_queue_get(&ns->rev_list); + parse_commit(commit); + parents = commit->parents; + + commit->object.flags |= POPPED; + if (!(commit->object.flags & COMMON)) + ns->non_common_revs--; + + if (commit->object.flags & COMMON) { + /* do not send "have", and ignore ancestors */ + commit = NULL; + mark = COMMON | SEEN; + } else if (commit->object.flags & COMMON_REF) + /* send "have", and ignore ancestors */ + mark = COMMON | SEEN; + else + /* send "have", also for its ancestors */ + mark = SEEN; + + while (parents) { + if (!(parents->item->object.flags & SEEN)) + rev_list_push(ns, parents->item, mark); + if (mark & COMMON) + mark_common(ns, parents->item, 1, 0); + parents = parents->next; + } + } + + return &commit->object.oid; +} + +static void known_common(struct fetch_negotiator *n, struct commit *c) +{ + if (!(c->object.flags & SEEN)) { + rev_list_push(n->data, c, COMMON_REF | SEEN); + mark_common(n->data, c, 1, 1); + } +} + +static void add_tip(struct fetch_negotiator *n, struct commit *c) +{ + n->known_common = NULL; + rev_list_push(n->data, c, SEEN); +} + +static const struct object_id *next(struct fetch_negotiator *n) +{ + n->known_common = NULL; + n->add_tip = NULL; + return get_rev(n->data); +} + +static int ack(struct fetch_negotiator *n, struct commit *c) +{ + int known_to_be_common = !!(c->object.flags & COMMON); + mark_common(n->data, c, 0, 1); + return known_to_be_common; +} + +static void release(struct fetch_negotiator *n) +{ + clear_prio_queue(&((struct negotiation_state *)n->data)->rev_list); + FREE_AND_NULL(n->data); +} + +void default_negotiator_init(struct fetch_negotiator *negotiator) +{ + struct negotiation_state *ns; + negotiator->known_common = known_common; + negotiator->add_tip = add_tip; + negotiator->next = next; + negotiator->ack = ack; + negotiator->release = release; + negotiator->data = ns = xcalloc(1, sizeof(*ns)); + ns->rev_list.compare = compare_commits_by_commit_date; + + if (marked) + for_each_ref(clear_marks, NULL); + marked = 1; +} diff --git a/negotiator/default.h b/negotiator/default.h new file mode 100644 index 0000000000..d23a8f2fb8 --- /dev/null +++ b/negotiator/default.h @@ -0,0 +1,8 @@ +#ifndef NEGOTIATOR_DEFAULT_H +#define NEGOTIATOR_DEFAULT_H + +struct fetch_negotiator; + +void default_negotiator_init(struct fetch_negotiator *negotiator); + +#endif diff --git a/negotiator/skipping.c b/negotiator/skipping.c new file mode 100644 index 0000000000..dffbc76c49 --- /dev/null +++ b/negotiator/skipping.c @@ -0,0 +1,250 @@ +#include "cache.h" +#include "skipping.h" +#include "../commit.h" +#include "../fetch-negotiator.h" +#include "../prio-queue.h" +#include "../refs.h" +#include "../tag.h" + +/* Remember to update object flag allocation in object.h */ +/* + * Both us and the server know that both parties have this object. + */ +#define COMMON (1U << 2) +/* + * The server has told us that it has this object. We still need to tell the + * server that we have this object (or one of its descendants), but since we are + * going to do that, we do not need to tell the server about its ancestors. + */ +#define ADVERTISED (1U << 3) +/* + * This commit has entered the priority queue. + */ +#define SEEN (1U << 4) +/* + * This commit has left the priority queue. + */ +#define POPPED (1U << 5) + +static int marked; + +/* + * An entry in the priority queue. + */ +struct entry { + struct commit *commit; + + /* + * Used only if commit is not COMMON. + */ + uint16_t original_ttl; + uint16_t ttl; +}; + +struct data { + struct prio_queue rev_list; + + /* + * The number of non-COMMON commits in rev_list. + */ + int non_common_revs; +}; + +static int compare(const void *a_, const void *b_, void *unused) +{ + const struct entry *a = a_; + const struct entry *b = b_; + return compare_commits_by_commit_date(a->commit, b->commit, NULL); +} + +static struct entry *rev_list_push(struct data *data, struct commit *commit, int mark) +{ + struct entry *entry; + commit->object.flags |= mark | SEEN; + + entry = xcalloc(1, sizeof(*entry)); + entry->commit = commit; + prio_queue_put(&data->rev_list, entry); + + if (!(mark & COMMON)) + data->non_common_revs++; + return entry; +} + +static int clear_marks(const char *refname, const struct object_id *oid, + int flag, void *cb_data) +{ + struct object *o = deref_tag(the_repository, parse_object(the_repository, oid), refname, 0); + + if (o && o->type == OBJ_COMMIT) + clear_commit_marks((struct commit *)o, + COMMON | ADVERTISED | SEEN | POPPED); + return 0; +} + +/* + * Mark this SEEN commit and all its SEEN ancestors as COMMON. + */ +static void mark_common(struct data *data, struct commit *c) +{ + struct commit_list *p; + + if (c->object.flags & COMMON) + return; + c->object.flags |= COMMON; + if (!(c->object.flags & POPPED)) + data->non_common_revs--; + + if (!c->object.parsed) + return; + for (p = c->parents; p; p = p->next) { + if (p->item->object.flags & SEEN) + mark_common(data, p->item); + } +} + +/* + * Ensure that the priority queue has an entry for to_push, and ensure that the + * entry has the correct flags and ttl. + * + * This function returns 1 if an entry was found or created, and 0 otherwise + * (because the entry for this commit had already been popped). + */ +static int push_parent(struct data *data, struct entry *entry, + struct commit *to_push) +{ + struct entry *parent_entry; + + if (to_push->object.flags & SEEN) { + int i; + if (to_push->object.flags & POPPED) + /* + * The entry for this commit has already been popped, + * due to clock skew. Pretend that this parent does not + * exist. + */ + return 0; + /* + * Find the existing entry and use it. + */ + for (i = 0; i < data->rev_list.nr; i++) { + parent_entry = data->rev_list.array[i].data; + if (parent_entry->commit == to_push) + goto parent_found; + } + BUG("missing parent in priority queue"); +parent_found: + ; + } else { + parent_entry = rev_list_push(data, to_push, 0); + } + + if (entry->commit->object.flags & (COMMON | ADVERTISED)) { + mark_common(data, to_push); + } else { + uint16_t new_original_ttl = entry->ttl + ? entry->original_ttl : entry->original_ttl * 3 / 2 + 1; + uint16_t new_ttl = entry->ttl + ? entry->ttl - 1 : new_original_ttl; + if (parent_entry->original_ttl < new_original_ttl) { + parent_entry->original_ttl = new_original_ttl; + parent_entry->ttl = new_ttl; + } + } + + return 1; +} + +static const struct object_id *get_rev(struct data *data) +{ + struct commit *to_send = NULL; + + while (to_send == NULL) { + struct entry *entry; + struct commit *commit; + struct commit_list *p; + int parent_pushed = 0; + + if (data->rev_list.nr == 0 || data->non_common_revs == 0) + return NULL; + + entry = prio_queue_get(&data->rev_list); + commit = entry->commit; + commit->object.flags |= POPPED; + if (!(commit->object.flags & COMMON)) + data->non_common_revs--; + + if (!(commit->object.flags & COMMON) && !entry->ttl) + to_send = commit; + + parse_commit(commit); + for (p = commit->parents; p; p = p->next) + parent_pushed |= push_parent(data, entry, p->item); + + if (!(commit->object.flags & COMMON) && !parent_pushed) + /* + * This commit has no parents, or all of its parents + * have already been popped (due to clock skew), so send + * it anyway. + */ + to_send = commit; + + free(entry); + } + + return &to_send->object.oid; +} + +static void known_common(struct fetch_negotiator *n, struct commit *c) +{ + if (c->object.flags & SEEN) + return; + rev_list_push(n->data, c, ADVERTISED); +} + +static void add_tip(struct fetch_negotiator *n, struct commit *c) +{ + n->known_common = NULL; + if (c->object.flags & SEEN) + return; + rev_list_push(n->data, c, 0); +} + +static const struct object_id *next(struct fetch_negotiator *n) +{ + n->known_common = NULL; + n->add_tip = NULL; + return get_rev(n->data); +} + +static int ack(struct fetch_negotiator *n, struct commit *c) +{ + int known_to_be_common = !!(c->object.flags & COMMON); + if (!(c->object.flags & SEEN)) + die("received ack for commit %s not sent as 'have'\n", + oid_to_hex(&c->object.oid)); + mark_common(n->data, c); + return known_to_be_common; +} + +static void release(struct fetch_negotiator *n) +{ + clear_prio_queue(&((struct data *)n->data)->rev_list); + FREE_AND_NULL(n->data); +} + +void skipping_negotiator_init(struct fetch_negotiator *negotiator) +{ + struct data *data; + negotiator->known_common = known_common; + negotiator->add_tip = add_tip; + negotiator->next = next; + negotiator->ack = ack; + negotiator->release = release; + negotiator->data = data = xcalloc(1, sizeof(*data)); + data->rev_list.compare = compare; + + if (marked) + for_each_ref(clear_marks, NULL); + marked = 1; +} diff --git a/negotiator/skipping.h b/negotiator/skipping.h new file mode 100644 index 0000000000..d7dfa6c6e4 --- /dev/null +++ b/negotiator/skipping.h @@ -0,0 +1,8 @@ +#ifndef NEGOTIATOR_SKIPPING_H +#define NEGOTIATOR_SKIPPING_H + +struct fetch_negotiator; + +void skipping_negotiator_init(struct fetch_negotiator *negotiator); + +#endif |