{"thread":{"id":"31422","subject":"[PATCH] test-generation: compute generation numbers and clock skews","startedAt":"2012-09-04T09:50:26Z","lastAt":"2012-09-14T21:55:57Z","messageCount":2,"participants":["Junio C Hamano","Michael Schubert"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"198289","messageId":"7vtxvece1p.fsf@alter.siamese.dyndns.org","threadId":"31422","inReplyTo":null,"subject":"[PATCH] test-generation: compute generation numbers and clock skews","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-09-04T09:50:26Z","receivedAt":"2012-09-04T09:50:26Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"It finds three commits that has older commit timestamp than the\nnewest commit timestamp among its ancestor in our history; all of\nthese are a direct child of a commit that is older (i.e. the clock\nskew lasts for only one hop).\n\n  commit  gen  timestamp                 skew gen ancestor\n  ed19f36 2870 2006-03-04 07:29:56 +0000 (8) 2869 91a6bf4\n  7763987 6404 2007-09-02 06:53:47 +0000 (373) 6403 86bab96\n  619a644 9982 2009-10-18 19:34:56 +0000 (268948) 9981 46148dd\n\nOn the other hand, the kernel history is littered with skewed\nchains.  I counted 2239 commits that have an ancestor newer than\nthemselves in total (they tend to cluster, but I haven't counted\nclusters), among 322345 commits (0.7%).\n\nFor example, a 33-commit chain leading to b4e1b7e builds on top of\n422e6c4 that was commited by Linus at Tue Mar 15 15:48:13 2011, but\nthe tip commit claims to have been committed at Sun Feb 20 19:19:43\n2011, which is clearly impossible.\n\nSigned-off-by: Junio C Hamano <gitster@pobox.com>\n---\n\n * Take the usefulness and correctness of this patch with a large\n   grain of salt, as it was done primarily because I couldn't sleep\n   X-<.\n\n   The motivation behind this toy is to help analyzing the real\n   world history and come up with a way to improve the robustness of\n   history traversal, which depends on the SLOP heuristics, without\n   having to give each and every commit object an extra generation\n   number (worse yet, after the fact).  We could instead mark only\n   these 2200+ commits, and teach still_interesting() function not\n   to rely on SLOP, but answer yes while one of these commits marked\n   as \"unreliable/skewed\" are still on the list.  When we no longer\n   have these skewed commits (whose definition is \"its timestamp is\n   older than one of its ancestor's timestamp), we know that the\n   time-based priority queue has popped all the ancestors that\n   possibly can matter, and stop the traversal with confidence.\n\n Makefile          |   1 +\n test-generation.c | 105 ++++++++++++++++++++++++++++++++++++++++++++++++++++++\n 2 files changed, 106 insertions(+)\n create mode 100644 test-generation.c\n\ndiff --git a/Makefile b/Makefile\nindex 66e8216..52f62b7 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -489,6 +489,7 @@ TEST_PROGRAMS_NEED_X += test-date\n TEST_PROGRAMS_NEED_X += test-delta\n TEST_PROGRAMS_NEED_X += test-dump-cache-tree\n TEST_PROGRAMS_NEED_X += test-genrandom\n+TEST_PROGRAMS_NEED_X += test-generation\n TEST_PROGRAMS_NEED_X += test-index-version\n TEST_PROGRAMS_NEED_X += test-line-buffer\n TEST_PROGRAMS_NEED_X += test-match-trees\ndiff --git a/test-generation.c b/test-generation.c\nnew file mode 100644\nindex 0000000..4df5a0d\n--- /dev/null\n+++ b/test-generation.c\n@@ -0,0 +1,105 @@\n+#include \"cache.h\"\n+#include \"commit.h\"\n+#include \"diff.h\"\n+#include \"revision.h\"\n+\n+\n+struct gdata {\n+\tint generation;\n+\tstruct commit *youngest_ancestor;\n+};\n+\n+static struct gdata *util_gd(struct commit *commit)\n+{\n+\treturn commit->util;\n+}\n+\n+static void show_commit(struct commit *commit, struct gdata *gd)\n+{\n+\tprintf(\"%s %d\",\n+\t       find_unique_abbrev(commit->object.sha1, DEFAULT_ABBREV),\n+\t       gd->generation);\n+\tif (gd->youngest_ancestor != commit) {\n+\t\tstruct commit *ancestor = gd->youngest_ancestor;\n+\t\tconst char *abbrev;\n+\n+\t\tabbrev = find_unique_abbrev(ancestor->object.sha1,\n+\t\t\t\t\t    DEFAULT_ABBREV);\n+\t\tprintf(\" %s \", show_date(commit->date, 0, DATE_ISO8601));\n+\t\tprintf(\"(%lu) \", ancestor->date - commit->date);\n+\t\tprintf(\"%d\", util_gd(ancestor)->generation);\n+\t\tprintf(\" %s\", abbrev);\n+\t}\n+\tputchar('\\n');\n+}\n+\n+int main(int ac, const char **av)\n+{\n+\tstruct rev_info revs;\n+\tstruct setup_revision_opt opt;\n+\tstruct commit_list *list;\n+\tstruct commit_list *stuck = NULL;\n+\n+\tmemset(&opt, 0, sizeof(opt));\n+\topt.def = \"HEAD\";\n+\tinit_revisions(&revs, NULL);\n+\tsetup_revisions(ac, av, &revs, &opt);\n+\tprepare_revision_walk(&revs);\n+\n+\tlist = revs.commits;\n+\twhile (list || stuck) {\n+\t\tstruct commit_list *parent, *next;\n+\t\tstruct commit *commit;\n+\t\tstruct gdata *gd;\n+\t\tint ready = 1;\n+\t\tint parent_generation;\n+\t\tstruct commit *youngest_ancestor;\n+\n+\t\tif (!list) {\n+\t\t\tlist = stuck;\n+\t\t\tstuck = NULL;\n+\t\t}\n+\t\tcommit = list->item;\n+\t\tyoungest_ancestor = commit;\n+\t\tparent_generation = 0;\n+\t\tparse_commit(commit);\n+\t\tif (!commit->util)\n+\t\t\tcommit->util = xcalloc(1, sizeof(*gd));\n+\t\tgd = commit->util;\n+\t\tif (gd->generation) {\n+\t\t\t/* we have handled this already */\n+\t\t\tnext = list->next;\n+\t\t\tfree(list);\n+\t\t\tlist = next;\n+\t\t\tcontinue;\n+\t\t}\n+\n+\t\tfor (parent = commit->parents; parent; parent = parent->next) {\n+\t\t\tstruct commit *p = parent->item;\n+\t\t\tstruct gdata *pgd = p->util;\n+\n+\t\t\t/* queue to the front */\n+\t\t\tcommit_list_insert(p, &list);\n+\t\t\tif (!pgd || !pgd->generation) {\n+\t\t\t\tready = 0;\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (parent_generation < pgd->generation)\n+\t\t\t\tparent_generation = pgd->generation;\n+\t\t\tif (youngest_ancestor->date < pgd->youngest_ancestor->date)\n+\t\t\t\tyoungest_ancestor = pgd->youngest_ancestor;\n+\t\t}\n+\t\tif (!ready) {\n+\t\t\tcommit_list_insert(commit, &stuck);\n+\t\t\tcontinue;\n+\t\t}\n+\t\tgd->generation = parent_generation + 1;\n+\t\tgd->youngest_ancestor = youngest_ancestor;\n+\n+\t\tnext = list->next;\n+\t\tfree(list);\n+\t\tlist = next;\n+\n+\t\tshow_commit(commit, gd);\n+\t}\n+}\n-- \n1.7.12.321.g60f00e5\n"},{"id":"199079","messageId":"5053A7ED.9080403@elegosoft.com","threadId":"31422","inReplyTo":"7vtxvece1p.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH] test-generation: compute generation numbers and clock skews","fromName":"Michael Schubert","fromEmail":"mschub@elegosoft.com","sentAt":"2012-09-14T21:55:57Z","receivedAt":"2012-09-14T21:55:57Z","isPatch":true,"sender":{"key":"mschub@elegosoft.com","avatar":null},"body":"main() is missing a return here:\ntest-generation.c:105:1: warning: control reaches end of non-void function [-Wreturn-type]\n"}]}