See thread starter for discussion.
Signed-off-by: Thomas Rast <trast@xxxxxxxxxxxxxxx>
---
builtin-fetch-pack.c | 333 +++++++++++++++++++++++++++++++++++++++++++------
upload-pack.c | 4 +-
2 files changed, 294 insertions(+), 43 deletions(-)
diff --git a/builtin-fetch-pack.c b/builtin-fetch-pack.c
index 4dfef29..9f010fe 100644
--- a/builtin-fetch-pack.c
+++ b/builtin-fetch-pack.c
@@ -25,6 +25,11 @@ static const char fetch_pack_usage[] =
#define COMMON_REF (1U << 2)
#define SEEN (1U << 3)
#define POPPED (1U << 4)
+#define BISECTED_FW (1U << 5)
+#define BISECTED_BW (1U << 6)
+#define NOTCOMMON (1U << 7)
+#define HAS_INFO (1U << 8)
+#define CLEAN_MARKS (COMMON | COMMON_REF | SEEN | POPPED | BISECTED_FW | BISECTED_BW | NOTCOMMON)
static int marked;
@@ -34,19 +39,78 @@ static int marked;
*/
#define MAX_IN_VAIN 256
-static struct commit_list *rev_list;
+struct work_list
+{
+ struct work_list *next;
+ struct commit *commit;
+ unsigned int stride; /* current stride length between commits */
+ unsigned int steps; /* steps left to go before emitting again */
+ unsigned int bisect;
+ unsigned int is_ref :1; /* prioritise refs */
+};
+
+static struct work_list *work_list = NULL;
+
+static struct commit_list *outstanding = NULL; /* list of commits not ACKed yet */
+static struct commit_list *outstanding_end = NULL;
+
+struct commit_info
+{
+ struct commit_list *children;
+};
+
+
static int non_common_revs, multi_ack, use_sideband;
-static void rev_list_push(struct commit *commit, int mark)
+static struct commit_info *get_commit_info(struct commit *commit)
+{
+ if (commit->object.flags & HAS_INFO)
+ return commit->util;
+
+ struct commit_info *info = xmalloc(sizeof(struct commit_info));
+ info->children = NULL;
+ commit->util = info;
+ commit->object.flags |= HAS_INFO;
+ return info;
+}
+
+static void work_list_insert(struct work_list *work_item)
{
+ struct work_list **pp = &work_list;
+ struct work_list *p;
+
+ while ((p = *pp)) {
+ if ((work_item->is_ref && (!p->is_ref || p->commit->date < work_item->commit->date))
+ || (!work_item->bisect && (p->bisect || p->commit->date < work_item->commit->date))
+ || p->bisect > work_item->bisect)
+ break;
+ pp = &p->next;
+ }
+
+ work_item->next = p;
+ *pp = work_item;
+}
+
+
+static void rev_list_push(struct commit *commit, int mark, unsigned int stride, unsigned int steps, unsigned int is_ref)
+{
+ struct work_list *work_item;
+
if (!(commit->object.flags & mark)) {
commit->object.flags |= mark;
- if (!(commit->object.parsed))
+ if (!(commit->object.parsed)) {
if (parse_commit(commit))
return;
+ }
- insert_by_date(commit, &rev_list);
+ work_item = xmalloc(sizeof(struct work_list));
+ work_item->commit = commit;
+ work_item->stride = stride;
+ work_item->steps = steps;
+ work_item->bisect = 0;
+ work_item->is_ref = is_ref;
+ work_list_insert(work_item);
if (!(commit->object.flags & COMMON))
non_common_revs++;
@@ -58,7 +122,7 @@ static int rev_list_insert_ref(const char *path, const unsigned char *sha1, int
struct object *o = deref_tag(parse_object(sha1), path, 0);
if (o && o->type == OBJ_COMMIT)
- rev_list_push((struct commit *)o, SEEN);
+ rev_list_push((struct commit *)o, SEEN, 1, 1, 1);
return 0;
}
@@ -68,8 +132,7 @@ static int clear_marks(const char *path, const unsigned char *sha1, int flag, vo
struct object *o = deref_tag(parse_object(sha1), path, 0);
if (o && o->type == OBJ_COMMIT)
- clear_commit_marks((struct commit *)o,
- COMMON | COMMON_REF | SEEN | POPPED);
+ clear_commit_marks((struct commit *)o, CLEAN_MARKS);
return 0;
}
@@ -89,7 +152,7 @@ static void mark_common(struct commit *commit,
o->flags |= COMMON;
if (!(o->flags & SEEN))
- rev_list_push(commit, SEEN);
+ rev_list_push(commit, SEEN, 1, 1, 0);
else {
struct commit_list *parents;
@@ -111,49 +174,216 @@ static void mark_common(struct commit *commit,
Get the next rev to send, ignoring the common.
*/
-static const unsigned char* get_rev(void)
+
+static void get_rev_queue_parents(struct commit *commit, int mark, unsigned int stride, unsigned int steps)
+{
+ struct commit_list *parents = commit->parents;
+
+ while (parents) {
+ struct commit_info *info = get_commit_info(parents->item);
+ struct commit_list *entry;
+ for (entry = info->children; entry; entry = entry->next)
+ if (entry->item == commit)
+ break;
+ if (!entry)
+ commit_list_insert(commit, &(info->children));
+ if (!(parents->item->object.flags & SEEN))
+ rev_list_push(parents->item, mark, stride, steps, 0);
+ if (mark & COMMON)
+ mark_common(parents->item, 1, 0);
+ parents = parents->next;
+ }
+}
+
+
+static struct commit* get_rev_stride_skip(struct work_list *work_item)
+{
+ get_rev_queue_parents(work_item->commit, SEEN, work_item->stride,
+ work_item->steps + 1);
+
+ free(work_item);
+ return NULL;
+}
+
+static void setup_bisect(struct commit *commit, int depth)
+{
+ struct work_list *work_item = xmalloc(sizeof(struct work_list));
+
+ work_item->commit = commit;
+ work_item->bisect = 1+depth;
+ work_item->is_ref = 0;
+ work_list_insert(work_item);
+}
+
+static void setup_bisect_all (struct commit_list* list, int depth)
+{
+ while (list) {
+ setup_bisect(list->item, depth);
+ list = list->next;
+ }
+}
+
+static struct commit* get_rev_stride_emit(struct work_list *work_item)
+{
+ struct commit *commit = work_item->commit;
+ unsigned int mark;
+
+ commit->object.flags |= POPPED;
+
+ /* This one got hit by our walk! */
+ if (!(commit->object.flags & COMMON))
+ 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;
+ setup_bisect(commit, 0);
+ }
+
+ if (commit)
+ get_rev_queue_parents(commit, mark, work_item->stride*2, 0);
+
+ free(work_item);
+
+ return commit;
+}
+
+static struct commit* get_rev_bisect(struct work_list *work_item)
+{
+ struct commit *full;
+ struct commit *half;
+ int half_step;
+ struct commit_info *info;
+ unsigned int flags = work_item->commit->object.flags;
+
+ if (flags & NOTCOMMON) {
+ /* we inferred that this side of the bisection is not
+ * interesting any longer */
+ free(work_item);
+ return NULL;
+ }
+
+
+ if (!(flags & (COMMON|BISECTED_BW))) {
+ /* Server does not have this. Search backward in history */
+
+ full = work_item->commit;
+ full->object.flags |= BISECTED_BW;
+ half = work_item->commit;
+ half_step = 0;
+
+ while (full && full->parents) {
+ setup_bisect_all(full->parents->next, work_item->bisect);
+ full = full->parents->item;
+ half_step ^= 1;
+ if (half_step)
+ half = half->parents->item;
+ if (full->object.flags & (POPPED|COMMON))
+ break;
+ }
+
+ /* also insert the same bisection again so we can try forward too */
+ work_list_insert(work_item);
+
+ if (full->object.flags & POPPED
+ && !(full->object.flags & NOTCOMMON)
+ && !(half->object.flags & (COMMON|POPPED))) {
+ setup_bisect(half, work_item->bisect);
+ half->object.flags |= POPPED;
+ info = get_commit_info(half);
+ return half;
+ } else {
+ return NULL;
+ }
+ }
+
+ if (!(flags & (NOTCOMMON|BISECTED_FW))) {
+ /* We have not seen this yet when bisecting, search forward */
+
+ full = work_item->commit;
+ full->object.flags |= BISECTED_FW;
+ half = work_item->commit;
+ half_step = 0;
+
+ while (full && (info=get_commit_info(full))->children) {
+ setup_bisect_all(info->children->next, work_item->bisect);
+ full = info->children->item;
+ half_step ^= 1;
+ if (half_step) {
+ info = get_commit_info(half);
+ half = info->children->item;
+ }
+ if (full->object.flags & (POPPED|NOTCOMMON))
+ break;
+ }
+
+ if (full->object.flags & POPPED
+ && !(full->object.flags & COMMON)
+ && !(half->object.flags & POPPED)) {
+ setup_bisect(half, work_item->bisect);
+ half->object.flags |= POPPED;
+ info = get_commit_info(half);
+ free(work_item);
+ return half;
+ }
+ }
+
+ free(work_item);
+ return NULL;
+}
+
+
+static void mark_not_common(struct commit *commit)
+{
+ struct commit_info *info = get_commit_info(commit);
+ struct commit_list *child;
+
+ if (commit->object.flags & COMMON)
+ /* this has already been acked earlier */
+ return;
+
+ commit->object.flags |= NOTCOMMON;
+
+ for (child = info->children; child; child = child->next)
+ mark_not_common(child->item);
+}
+
+static struct commit *get_rev(void)
{
struct commit *commit = NULL;
while (commit == NULL) {
- unsigned int mark;
- struct commit_list *parents;
+ struct work_list *work_item = NULL;
- if (rev_list == NULL || non_common_revs == 0)
+ if (work_list == NULL || non_common_revs == 0)
return NULL;
- commit = rev_list->item;
- if (!commit->object.parsed)
+ work_item = work_list;
+ work_list = work_item->next;
+
+ commit = work_item->commit;
+
+ if (commit && !commit->object.parsed)
parse_commit(commit);
- parents = commit->parents;
- commit->object.flags |= POPPED;
- if (!(commit->object.flags & COMMON))
- 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(parents->item, mark);
- if (mark & COMMON)
- mark_common(parents->item, 1, 0);
- parents = parents->next;
+ if (work_item->bisect) {
+ commit = get_rev_bisect(work_item);
+ } else if (work_item->steps >= work_item->stride-1
+ || (commit && !commit->parents)) {
+ commit = get_rev_stride_emit(work_item);
+ } else {
+ commit = get_rev_stride_skip(work_item);
}
-
- rev_list = rev_list->next;
}
- return commit->object.sha1;
+ return commit;
}
static int find_common(int fd[2], unsigned char *result_sha1,
@@ -161,6 +391,7 @@ static int find_common(int fd[2], unsigned char *result_sha1,
{
int fetching;
int count = 0, flushes = 0, retval;
+ struct commit *commit;
const unsigned char *sha1;
unsigned in_vain = 0;
int got_continue = 0;
@@ -243,11 +474,21 @@ static int find_common(int fd[2], unsigned char *result_sha1,
flushes = 0;
retval = -1;
- while ((sha1 = get_rev())) {
+ while ((commit = get_rev())) {
+ sha1 = commit->object.sha1;
packet_write(fd[1], "have %s\n", sha1_to_hex(sha1));
if (args.verbose)
fprintf(stderr, "have %s\n", sha1_to_hex(sha1));
in_vain++;
+
+ if (outstanding) {
+ commit_list_insert(commit, &(outstanding_end->next));
+ outstanding_end = outstanding_end->next;
+ } else {
+ commit_list_insert(commit, &outstanding);
+ outstanding_end = outstanding;
+ }
+
if (!(31 & ++count)) {
int ack;
@@ -274,6 +515,16 @@ static int find_common(int fd[2], unsigned char *result_sha1,
} else if (ack == 2) {
struct commit *commit =
lookup_commit(result_sha1);
+ struct commit_list *item;
+ while (commit != outstanding->item) {
+ mark_not_common(commit);
+ item = outstanding;
+ outstanding = item->next;
+ free(item);
+ }
+ item = outstanding;
+ outstanding = item->next;
+ free(item);
mark_common(commit, 0, 1);
retval = 0;
in_vain = 0;
@@ -445,7 +696,7 @@ static int everything_local(struct ref **refs, int nr_match, char **match)
continue;
if (!(o->flags & SEEN)) {
- rev_list_push((struct commit *)o, COMMON_REF | SEEN);
+ rev_list_push((struct commit *)o, COMMON_REF | SEEN, 1, 1, 1);
mark_common((struct commit *)o, 1, 1);
}
diff --git a/upload-pack.c b/upload-pack.c
index e5adbc0..c6dfb32 100644
--- a/upload-pack.c
+++ b/upload-pack.c
@@ -414,9 +414,9 @@ static int get_common_commits(void)
if (!prefixcmp(line, "have ")) {
switch (got_sha1(line+5, sha1)) {
case -1: /* they have what we do not */
- if (multi_ack && ok_to_give_up())
+/* if (multi_ack && ok_to_give_up())
packet_write(1, "ACK %s continue\n",
- sha1_to_hex(sha1));
+ sha1_to_hex(sha1));*/
break;
default:
memcpy(hex, sha1_to_hex(sha1), 41);
--
tg: (1293c95..) t/fetch-pack-speedup (depends on: origin/master)
--
To unsubscribe from this list: send the line "unsubscribe git" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
