[PATCH] test-generation: compute generation numbers and clock skews

[PATCH] test-generation: compute generation numbers and clock skews

[Junio C Hamano]

It finds three commits that has older commit timestamp than the
newest commit timestamp among its ancestor in our history; all of
these are a direct child of a commit that is older (i.e. the clock
skew lasts for only one hop).

  commit  gen  timestamp                 skew gen ancestor
  ed19f36 2870 2006-03-04 07:29:56 +0000 (8) 2869 91a6bf4
  7763987 6404 2007-09-02 06:53:47 +0000 (373) 6403 86bab96
  619a644 9982 2009-10-18 19:34:56 +0000 (268948) 9981 46148dd

On the other hand, the kernel history is littered with skewed
chains.  I counted 2239 commits that have an ancestor newer than
themselves in total (they tend to cluster, but I haven't counted
clusters), among 322345 commits (0.7%).

For example, a 33-commit chain leading to b4e1b7e builds on top of
422e6c4 that was commited by Linus at Tue Mar 15 15:48:13 2011, but
the tip commit claims to have been committed at Sun Feb 20 19:19:43
2011, which is clearly impossible.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 * Take the usefulness and correctness of this patch with a large
   grain of salt, as it was done primarily because I couldn't sleep
   X-<.

   The motivation behind this toy is to help analyzing the real
   world history and come up with a way to improve the robustness of
   history traversal, which depends on the SLOP heuristics, without
   having to give each and every commit object an extra generation
   number (worse yet, after the fact).  We could instead mark only
   these 2200+ commits, and teach still_interesting() function not
   to rely on SLOP, but answer yes while one of these commits marked
   as "unreliable/skewed" are still on the list.  When we no longer
   have these skewed commits (whose definition is "its timestamp is
   older than one of its ancestor's timestamp), we know that the
   time-based priority queue has popped all the ancestors that
   possibly can matter, and stop the traversal with confidence.

 Makefile          |   1 +
 test-generation.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 106 insertions(+)
 create mode 100644 test-generation.c

diff --git a/Makefile b/Makefile
index 66e8216..52f62b7 100644
--- a/Makefile
+++ b/Makefile
@@ -489,6 +489,7 @@ TEST_PROGRAMS_NEED_X += test-date
 TEST_PROGRAMS_NEED_X += test-delta
 TEST_PROGRAMS_NEED_X += test-dump-cache-tree
 TEST_PROGRAMS_NEED_X += test-genrandom
+TEST_PROGRAMS_NEED_X += test-generation
 TEST_PROGRAMS_NEED_X += test-index-version
 TEST_PROGRAMS_NEED_X += test-line-buffer
 TEST_PROGRAMS_NEED_X += test-match-trees
diff --git a/test-generation.c b/test-generation.c
new file mode 100644
index 0000000..4df5a0d
--- /dev/null
+++ b/test-generation.c
@@ -0,0 +1,105 @@
+#include "cache.h"
+#include "commit.h"
+#include "diff.h"
+#include "revision.h"
+
+
+struct gdata {
+	int generation;
+	struct commit *youngest_ancestor;
+};
+
+static struct gdata *util_gd(struct commit *commit)
+{
+	return commit->util;
+}
+
+static void show_commit(struct commit *commit, struct gdata *gd)
+{
+	printf("%s %d",
+	       find_unique_abbrev(commit->object.sha1, DEFAULT_ABBREV),
+	       gd->generation);
+	if (gd->youngest_ancestor != commit) {
+		struct commit *ancestor = gd->youngest_ancestor;
+		const char *abbrev;
+
+		abbrev = find_unique_abbrev(ancestor->object.sha1,
+					    DEFAULT_ABBREV);
+		printf(" %s ", show_date(commit->date, 0, DATE_ISO8601));
+		printf("(%lu) ", ancestor->date - commit->date);
+		printf("%d", util_gd(ancestor)->generation);
+		printf(" %s", abbrev);
+	}
+	putchar('\n');
+}
+
+int main(int ac, const char **av)
+{
+	struct rev_info revs;
+	struct setup_revision_opt opt;
+	struct commit_list *list;
+	struct commit_list *stuck = NULL;
+
+	memset(&opt, 0, sizeof(opt));
+	opt.def = "HEAD";
+	init_revisions(&revs, NULL);
+	setup_revisions(ac, av, &revs, &opt);
+	prepare_revision_walk(&revs);
+
+	list = revs.commits;
+	while (list || stuck) {
+		struct commit_list *parent, *next;
+		struct commit *commit;
+		struct gdata *gd;
+		int ready = 1;
+		int parent_generation;
+		struct commit *youngest_ancestor;
+
+		if (!list) {
+			list = stuck;
+			stuck = NULL;
+		}
+		commit = list->item;
+		youngest_ancestor = commit;
+		parent_generation = 0;
+		parse_commit(commit);
+		if (!commit->util)
+			commit->util = xcalloc(1, sizeof(*gd));
+		gd = commit->util;
+		if (gd->generation) {
+			/* we have handled this already */
+			next = list->next;
+			free(list);
+			list = next;
+			continue;
+		}
+
+		for (parent = commit->parents; parent; parent = parent->next) {
+			struct commit *p = parent->item;
+			struct gdata *pgd = p->util;
+
+			/* queue to the front */
+			commit_list_insert(p, &list);
+			if (!pgd || !pgd->generation) {
+				ready = 0;
+				continue;
+			}
+			if (parent_generation < pgd->generation)
+				parent_generation = pgd->generation;
+			if (youngest_ancestor->date < pgd->youngest_ancestor->date)
+				youngest_ancestor = pgd->youngest_ancestor;
+		}
+		if (!ready) {
+			commit_list_insert(commit, &stuck);
+			continue;
+		}
+		gd->generation = parent_generation + 1;
+		gd->youngest_ancestor = youngest_ancestor;
+
+		next = list->next;
+		free(list);
+		list = next;
+
+		show_commit(commit, gd);
+	}
+}
-- 
1.7.12.321.g60f00e5

Re: [PATCH] test-generation: compute generation numbers and clock skews

[Michael Schubert]

main() is missing a return here:
test-generation.c:105:1: warning: control reaches end of non-void function [-Wreturn-type]