{"thread":{"id":"33874","subject":"[PATCH 00/17] Remove assumptions about refname lifetimes","startedAt":"2013-05-19T20:26:55Z","lastAt":"2013-05-23T18:02:50Z","messageCount":42,"participants":["Michael Haggerty","Johan Herland","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":1,"patchTotal":17},"messages":[{"id":"217928","messageId":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":null,"subject":"[PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:26:55Z","receivedAt":"2013-05-19T20:26:55Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Prior to this patch series, the refs API said nothing about the\nlifetime of the refname parameter passed to each_ref_fn callbacks by\nthe for_each_ref()-style iteration functions.  De facto, the refnames\nusually had long lives because they were pointers into the ref_cache\ndata structures, and those are only invalidated under rare\ncircumstances.  And some callers were assuming a long lifetime, for\nexample storing references to the refname string instead of copying\nit.\n\nBut it has long been the case that ref caches could be invalidated,\nfor example when a packed ref is deleted.  AFAIK there was never much\nclarity about what that might mean for callers.\n\nRecently a number of race conditions related to references have been\ndiscovered.  There is likely to be a two-pronged solution to the\nraces:\n\n* For traditional, filesystem-based references, there will have to be\n  more checks that the ref caches are still up-to-date at the time of\n  their use (see, for example, [1]).  If not, the ref cache will have\n  to be invalidated and reloaded.  Assuming that the invalidation of\n  the old cache includes freeing its memory, such an invalidation will\n  cause lots of refname strings to be freed even though callers might\n  still hold references to them.\n\n* For server-class installations, filesystem-based references might\n  not be robust enough for 100% reliable operation, because the\n  reading of the complete set of references is not an atomic\n  operation.  If another reference storage mechanism is developed,\n  there is no reason to expect the refnames strings to have long\n  lifetimes.\n\nA prerequisite for either of these approaches is to harmonize what\ncallers assume and what the API guarantees.\n\nThe purpose of this patch series is to track down callers who assume\nthat the refnames that they receive via a each_ref_fn callback have\nlifetimes beyond the duration of the callback invocation and to\nrewrite them to work without that assumption.  The final patch\ndocuments explicitly that callers should not retain references to the\nrefnames.\n\nA word about how I audited the code:\n\nTo find callers making unwarranted assumptions, I (temporarily)\nchanged do_one_ref() to do a xstrdup() of the refname, pass the copy\nto the callback function, then free() the copy.  This caused\nill-behaved callers to access freed memory, which could be detected by\nrunning the testsuite under valgrind.  There were indeed a number of\nsuch errors.  All of them are fixed by this patch series, and the test\njust described now runs without errors.\n\nI plan to do a second audit by hand to see if the test suite and/or\nvalgrind missed anything.\n\nThe last two patches are RFCs.  I would like some input on the second\nto last because I am not very familiar with how the object array entry\nnames are used, how many might be created, etc.  The last patch is an\nillustration of how I would like to change the API docs, but it will\nonly be ready when all of the code has been audited and adapted.\nPlease see especially my comments on these two patches for more\ninformation.\n\n[1] http://thread.gmane.org/gmane.comp.version-control.git/223299\n\nMichael Haggerty (17):\n  describe: make own copy of refname\n  fetch: make own copies of refnames\n  add_rev_cmdline(): make a copy of the name argument\n  builtin_diff_tree(): make it obvious that function wants two entries\n  cmd_diff(): use an object_array for holding trees\n  cmd_diff(): rename local variable \"list\" -> \"entry\"\n  cmd_diff(): make it obvious which cases are exclusive of each other\n  revision: split some overly-long lines\n  gc_boundary(): move the check \"alloc <= nr\" to caller\n  get_revision_internal(): make check less mysterious\n  object_array: add function object_array_filter()\n  object_array_remove_duplicates(): rewrite to reduce copying\n  fsck: don't put a void*-shaped peg in a char*-shaped hole\n  find_first_merges(): initialize merges variable using initializer\n  find_first_merges(): remove unnecessary code\n  object_array_entry: copy name before storing in name field\n  refs: document the lifetime of the refname passed to each_ref_fn\n\n builtin/describe.c |  6 +++--\n builtin/diff.c     | 68 ++++++++++++++++++++++++++----------------------------\n builtin/fetch.c    |  4 ++--\n builtin/fsck.c     |  2 +-\n object.c           | 50 +++++++++++++++++++++++++++++++--------\n object.h           | 23 ++++++++++++++++--\n refs.h             | 22 +++++++++++++-----\n revision.c         | 61 +++++++++++++++++++++++++-----------------------\n revision.h         | 32 ++++++++++++++++---------\n submodule.c        |  6 ++---\n 10 files changed, 172 insertions(+), 102 deletions(-)\n\n-- \n1.8.2.3\n"},{"id":"217929","messageId":"1368995232-11042-2-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 01/17] describe: make own copy of refname","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:26:56Z","receivedAt":"2013-05-19T20:26:56Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Do not retain a reference to the refname passed to the each_ref_fn\ncallback get_name(), because there is no guarantee of the lifetimes of\nthese names.  Instead, make a local copy when needed.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/describe.c | 6 ++++--\n 1 file changed, 4 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/describe.c b/builtin/describe.c\nindex 6636a68..3dc09eb 100644\n--- a/builtin/describe.c\n+++ b/builtin/describe.c\n@@ -42,7 +42,7 @@ struct commit_name {\n \tunsigned prio:2; /* annotated tag = 2, tag = 1, head = 0 */\n \tunsigned name_checked:1;\n \tunsigned char sha1[20];\n-\tconst char *path;\n+\tchar *path;\n };\n static const char *prio_names[] = {\n \t\"head\", \"lightweight\", \"annotated\",\n@@ -126,12 +126,14 @@ static void add_to_known_names(const char *path,\n \t\t\t} else {\n \t\t\t\te->next = NULL;\n \t\t\t}\n+\t\t\te->path = NULL;\n \t\t}\n \t\te->tag = tag;\n \t\te->prio = prio;\n \t\te->name_checked = 0;\n \t\thashcpy(e->sha1, sha1);\n-\t\te->path = path;\n+\t\tfree(e->path);\n+\t\te->path = xstrdup(path);\n \t}\n }\n \n-- \n1.8.2.3\n"},{"id":"217930","messageId":"1368995232-11042-3-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 02/17] fetch: make own copies of refnames","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:26:57Z","receivedAt":"2013-05-19T20:26:57Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Do not retain references to refnames passed to the each_ref_fn\ncallback add_existing(), because their lifetime is not guaranteed.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/fetch.c | 4 ++--\n 1 file changed, 2 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/fetch.c b/builtin/fetch.c\nindex 4b6b1df..f949115 100644\n--- a/builtin/fetch.c\n+++ b/builtin/fetch.c\n@@ -590,7 +590,7 @@ static void find_non_local_tags(struct transport *transport,\n \t\t\tstruct ref **head,\n \t\t\tstruct ref ***tail)\n {\n-\tstruct string_list existing_refs = STRING_LIST_INIT_NODUP;\n+\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n \tstruct string_list remote_refs = STRING_LIST_INIT_NODUP;\n \tconst struct ref *ref;\n \tstruct string_list_item *item = NULL;\n@@ -693,7 +693,7 @@ static int truncate_fetch_head(void)\n static int do_fetch(struct transport *transport,\n \t\t    struct refspec *refs, int ref_count)\n {\n-\tstruct string_list existing_refs = STRING_LIST_INIT_NODUP;\n+\tstruct string_list existing_refs = STRING_LIST_INIT_DUP;\n \tstruct string_list_item *peer_item = NULL;\n \tstruct ref *ref_map;\n \tstruct ref *rm;\n-- \n1.8.2.3\n"},{"id":"217931","messageId":"1368995232-11042-4-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 03/17] add_rev_cmdline(): make a copy of the name argument","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:26:58Z","receivedAt":"2013-05-19T20:26:58Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Instead of assuming that the memory pointed to by the name argument\nwill live forever, make a local copy of it before storing it in the\nref_cmdline_info.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n revision.c | 6 +++++-\n 1 file changed, 5 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex a67b615..25e424c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -898,6 +898,10 @@ static int limit_list(struct rev_info *revs)\n \treturn 0;\n }\n \n+/*\n+ * Add an entry to refs->cmdline with the specified information.\n+ * *name is copied.\n+ */\n static void add_rev_cmdline(struct rev_info *revs,\n \t\t\t    struct object *item,\n \t\t\t    const char *name,\n@@ -909,7 +913,7 @@ static void add_rev_cmdline(struct rev_info *revs,\n \n \tALLOC_GROW(info->rev, nr + 1, info->alloc);\n \tinfo->rev[nr].item = item;\n-\tinfo->rev[nr].name = name;\n+\tinfo->rev[nr].name = xstrdup(name);\n \tinfo->rev[nr].whence = whence;\n \tinfo->rev[nr].flags = flags;\n \tinfo->nr++;\n-- \n1.8.2.3\n"},{"id":"217944","messageId":"1368995232-11042-5-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 04/17] builtin_diff_tree(): make it obvious that function wants two entries","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:26:59Z","receivedAt":"2013-05-19T20:26:59Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Instead of accepting an array and using exactly two elements from the\narray, take two single (struct object_array_entry *) arguments.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/diff.c | 18 +++++++++---------\n 1 file changed, 9 insertions(+), 9 deletions(-)\n\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 8c2af6c..ba68c6c 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -153,7 +153,8 @@ static int builtin_diff_index(struct rev_info *revs,\n \n static int builtin_diff_tree(struct rev_info *revs,\n \t\t\t     int argc, const char **argv,\n-\t\t\t     struct object_array_entry *ent)\n+\t\t\t     struct object_array_entry *ent0,\n+\t\t\t     struct object_array_entry *ent1)\n {\n \tconst unsigned char *(sha1[2]);\n \tint swap = 0;\n@@ -161,13 +162,13 @@ static int builtin_diff_tree(struct rev_info *revs,\n \tif (argc > 1)\n \t\tusage(builtin_diff_usage);\n \n-\t/* We saw two trees, ent[0] and ent[1].\n-\t * if ent[1] is uninteresting, they are swapped\n+\t/* We saw two trees, ent0 and ent1.\n+\t * if ent1 is uninteresting, they are swapped\n \t */\n-\tif (ent[1].item->flags & UNINTERESTING)\n+\tif (ent1->item->flags & UNINTERESTING)\n \t\tswap = 1;\n-\tsha1[swap] = ent[0].item->sha1;\n-\tsha1[1-swap] = ent[1].item->sha1;\n+\tsha1[swap] = ent0->item->sha1;\n+\tsha1[1-swap] = ent1->item->sha1;\n \tdiff_tree_sha1(sha1[0], sha1[1], \"\", &revs->diffopt);\n \tlog_tree_diff_flush(revs);\n \treturn 0;\n@@ -403,7 +404,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \telse if (ents == 1)\n \t\tresult = builtin_diff_index(&rev, argc, argv);\n \telse if (ents == 2)\n-\t\tresult = builtin_diff_tree(&rev, argc, argv, ent);\n+\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[1]);\n \telse if (ent[0].item->flags & UNINTERESTING) {\n \t\t/*\n \t\t * diff A...B where there is at least one merge base\n@@ -412,8 +413,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\t * between the base and B.  Note that we pick one\n \t\t * merge base at random if there are more than one.\n \t\t */\n-\t\tent[1] = ent[ents-1];\n-\t\tresult = builtin_diff_tree(&rev, argc, argv, ent);\n+\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[ents-1]);\n \t} else\n \t\tresult = builtin_diff_combined(&rev, argc, argv,\n \t\t\t\t\t       ent, ents);\n-- \n1.8.2.3\n"},{"id":"217933","messageId":"1368995232-11042-6-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 05/17] cmd_diff(): use an object_array for holding trees","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:00Z","receivedAt":"2013-05-19T20:27:00Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Change cmd_diff() to use a (struct object_array) for holding the trees\nthat it accumulates, rather than rolling its own equivalent.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/diff.c | 37 ++++++++++++++++++-------------------\n 1 file changed, 18 insertions(+), 19 deletions(-)\n\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex ba68c6c..72d99c0 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -252,8 +252,8 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n {\n \tint i;\n \tstruct rev_info rev;\n-\tstruct object_array_entry ent[100];\n-\tint ents = 0, blobs = 0, paths = 0;\n+\tstruct object_array ent = OBJECT_ARRAY_INIT;\n+\tint blobs = 0, paths = 0;\n \tconst char *path = NULL;\n \tstruct blobinfo blob[2];\n \tint nongit;\n@@ -350,13 +350,8 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\tif (obj->type == OBJ_COMMIT)\n \t\t\tobj = &((struct commit *)obj)->tree->object;\n \t\tif (obj->type == OBJ_TREE) {\n-\t\t\tif (ARRAY_SIZE(ent) <= ents)\n-\t\t\t\tdie(_(\"more than %d trees given: '%s'\"),\n-\t\t\t\t    (int) ARRAY_SIZE(ent), name);\n \t\t\tobj->flags |= flags;\n-\t\t\tent[ents].item = obj;\n-\t\t\tent[ents].name = name;\n-\t\t\tents++;\n+\t\t\tadd_object_array(obj, name, &ent);\n \t\t\tcontinue;\n \t\t}\n \t\tif (obj->type == OBJ_BLOB) {\n@@ -380,7 +375,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t/*\n \t * Now, do the arguments look reasonable?\n \t */\n-\tif (!ents) {\n+\tif (!ent.nr) {\n \t\tswitch (blobs) {\n \t\tcase 0:\n \t\t\tresult = builtin_diff_files(&rev, argc, argv);\n@@ -401,22 +396,26 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t}\n \telse if (blobs)\n \t\tusage(builtin_diff_usage);\n-\telse if (ents == 1)\n+\telse if (ent.nr == 1)\n \t\tresult = builtin_diff_index(&rev, argc, argv);\n-\telse if (ents == 2)\n-\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[1]);\n-\telse if (ent[0].item->flags & UNINTERESTING) {\n+\telse if (ent.nr == 2)\n+\t\tresult = builtin_diff_tree(&rev, argc, argv,\n+\t\t\t\t\t   &ent.objects[0], &ent.objects[1]);\n+\telse if (ent.objects[0].item->flags & UNINTERESTING) {\n \t\t/*\n \t\t * diff A...B where there is at least one merge base\n-\t\t * between A and B.  We have ent[0] == merge-base,\n-\t\t * ent[ents-2] == A, and ent[ents-1] == B.  Show diff\n-\t\t * between the base and B.  Note that we pick one\n-\t\t * merge base at random if there are more than one.\n+\t\t * between A and B.  We have ent.objects[0] ==\n+\t\t * merge-base, ent.objects[ents-2] == A, and\n+\t\t * ent.objects[ents-1] == B.  Show diff between the\n+\t\t * base and B.  Note that we pick one merge base at\n+\t\t * random if there are more than one.\n \t\t */\n-\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[ents-1]);\n+\t\tresult = builtin_diff_tree(&rev, argc, argv,\n+\t\t\t\t\t   &ent.objects[0],\n+\t\t\t\t\t   &ent.objects[ent.nr-1]);\n \t} else\n \t\tresult = builtin_diff_combined(&rev, argc, argv,\n-\t\t\t\t\t       ent, ents);\n+\t\t\t\t\t       ent.objects, ent.nr);\n \tresult = diff_result_code(&rev.diffopt, result);\n \tif (1 < rev.diffopt.skip_stat_unmatch)\n \t\trefresh_index_quietly();\n-- \n1.8.2.3\n"},{"id":"217941","messageId":"1368995232-11042-7-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 06/17] cmd_diff(): rename local variable \"list\" -> \"entry\"","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:01Z","receivedAt":"2013-05-19T20:27:01Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"It's not a list, it's an array entry.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/diff.c | 8 ++++----\n 1 file changed, 4 insertions(+), 4 deletions(-)\n\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 72d99c0..7cac6de 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -338,9 +338,9 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t}\n \n \tfor (i = 0; i < rev.pending.nr; i++) {\n-\t\tstruct object_array_entry *list = rev.pending.objects+i;\n-\t\tstruct object *obj = list->item;\n-\t\tconst char *name = list->name;\n+\t\tstruct object_array_entry *entry = &rev.pending.objects[i];\n+\t\tstruct object *obj = entry->item;\n+\t\tconst char *name = entry->name;\n \t\tint flags = (obj->flags & UNINTERESTING);\n \t\tif (!obj->parsed)\n \t\t\tobj = parse_object(obj->sha1);\n@@ -359,7 +359,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\t\t\tdie(_(\"more than two blobs given: '%s'\"), name);\n \t\t\thashcpy(blob[blobs].sha1, obj->sha1);\n \t\t\tblob[blobs].name = name;\n-\t\t\tblob[blobs].mode = list->mode;\n+\t\t\tblob[blobs].mode = entry->mode;\n \t\t\tblobs++;\n \t\t\tcontinue;\n \n-- \n1.8.2.3\n"},{"id":"217945","messageId":"1368995232-11042-8-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 07/17] cmd_diff(): make it obvious which cases are exclusive of each other","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:02Z","receivedAt":"2013-05-19T20:27:02Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"At first glance the OBJ_COMMIT, OBJ_TREE, and OBJ_BLOB cases look like\nthey might be mutually exclusive.  But the OBJ_COMMIT case doesn't end\nthe loop iteration with \"continue\" like the other two cases, but\nrather falls through.  So use if...else if...else construct to make it\nmore obvious that only the last two cases are mutually exclusive.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n builtin/diff.c | 9 ++++-----\n 1 file changed, 4 insertions(+), 5 deletions(-)\n\ndiff --git a/builtin/diff.c b/builtin/diff.c\nindex 7cac6de..3b90ee6 100644\n--- a/builtin/diff.c\n+++ b/builtin/diff.c\n@@ -349,22 +349,21 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n \t\t\tdie(_(\"invalid object '%s' given.\"), name);\n \t\tif (obj->type == OBJ_COMMIT)\n \t\t\tobj = &((struct commit *)obj)->tree->object;\n+\n \t\tif (obj->type == OBJ_TREE) {\n \t\t\tobj->flags |= flags;\n \t\t\tadd_object_array(obj, name, &ent);\n-\t\t\tcontinue;\n-\t\t}\n-\t\tif (obj->type == OBJ_BLOB) {\n+\t\t} else if (obj->type == OBJ_BLOB) {\n \t\t\tif (2 <= blobs)\n \t\t\t\tdie(_(\"more than two blobs given: '%s'\"), name);\n \t\t\thashcpy(blob[blobs].sha1, obj->sha1);\n \t\t\tblob[blobs].name = name;\n \t\t\tblob[blobs].mode = entry->mode;\n \t\t\tblobs++;\n-\t\t\tcontinue;\n \n+\t\t} else {\n+\t\t\tdie(_(\"unhandled object '%s' given.\"), name);\n \t\t}\n-\t\tdie(_(\"unhandled object '%s' given.\"), name);\n \t}\n \tif (rev.prune_data.nr) {\n \t\tif (!path)\n-- \n1.8.2.3\n"},{"id":"217932","messageId":"1368995232-11042-9-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 08/17] revision: split some overly-long lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:03Z","receivedAt":"2013-05-19T20:27:03Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n revision.c | 20 ++++++++++++++------\n revision.h | 32 +++++++++++++++++++++-----------\n 2 files changed, 35 insertions(+), 17 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 25e424c..8ac88d6 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -70,7 +70,8 @@ static int show_path_truncated(FILE *out, const struct name_path *path)\n \treturn ours || emitted;\n }\n \n-void show_object_with_name(FILE *out, struct object *obj, const struct name_path *path, const char *component)\n+void show_object_with_name(FILE *out, struct object *obj,\n+\t\t\t   const struct name_path *path, const char *component)\n {\n \tstruct name_path leaf;\n \tleaf.up = (struct name_path *)path;\n@@ -186,7 +187,9 @@ void mark_parents_uninteresting(struct commit *commit)\n \t}\n }\n \n-static void add_pending_object_with_mode(struct rev_info *revs, struct object *obj, const char *name, unsigned mode)\n+static void add_pending_object_with_mode(struct rev_info *revs,\n+\t\t\t\t\t struct object *obj,\n+\t\t\t\t\t const char *name, unsigned mode)\n {\n \tif (!obj)\n \t\treturn;\n@@ -209,7 +212,8 @@ static void add_pending_object_with_mode(struct rev_info *revs, struct object *o\n \tadd_object_array_with_mode(obj, name, &revs->pending, mode);\n }\n \n-void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)\n+void add_pending_object(struct rev_info *revs,\n+\t\t\tstruct object *obj, const char *name)\n {\n \tadd_pending_object_with_mode(revs, obj, name, S_IFINVALID);\n }\n@@ -226,7 +230,9 @@ void add_head_to_pending(struct rev_info *revs)\n \tadd_pending_object(revs, obj, \"HEAD\");\n }\n \n-static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)\n+static struct object *get_reference(struct rev_info *revs, const char *name,\n+\t\t\t\t    const unsigned char *sha1,\n+\t\t\t\t    unsigned int flags)\n {\n \tstruct object *object;\n \n@@ -247,7 +253,8 @@ void add_pending_sha1(struct rev_info *revs, const char *name,\n \tadd_pending_object(revs, object, name);\n }\n \n-static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)\n+static struct commit *handle_commit(struct rev_info *revs,\n+\t\t\t\t    struct object *object, const char *name)\n {\n \tunsigned long flags = object->flags;\n \n@@ -368,7 +375,8 @@ static void file_change(struct diff_options *options,\n \tDIFF_OPT_SET(options, HAS_CHANGES);\n }\n \n-static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct commit *commit)\n+static int rev_compare_tree(struct rev_info *revs,\n+\t\t\t    struct commit *parent, struct commit *commit)\n {\n \tstruct tree *t1 = parent->tree;\n \tstruct tree *t2 = commit->tree;\ndiff --git a/revision.h b/revision.h\nindex 01bd2b7..9628465 100644\n--- a/revision.h\n+++ b/revision.h\n@@ -195,19 +195,23 @@ struct setup_revision_opt {\n };\n \n extern void init_revisions(struct rev_info *revs, const char *prefix);\n-extern int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *);\n+extern int setup_revisions(int argc, const char **argv, struct rev_info *revs,\n+\t\t\t   struct setup_revision_opt *);\n extern void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,\n-\t\t\t\t const struct option *options,\n-\t\t\t\t const char * const usagestr[]);\n+\t\t\t       const struct option *options,\n+\t\t\t       const char * const usagestr[]);\n #define REVARG_CANNOT_BE_FILENAME 01\n #define REVARG_COMMITTISH 02\n-extern int handle_revision_arg(const char *arg, struct rev_info *revs, int flags, unsigned revarg_opt);\n+extern int handle_revision_arg(const char *arg, struct rev_info *revs,\n+\t\t\t       int flags, unsigned revarg_opt);\n \n extern void reset_revision_walk(void);\n extern int prepare_revision_walk(struct rev_info *revs);\n extern struct commit *get_revision(struct rev_info *revs);\n-extern char *get_revision_mark(const struct rev_info *revs, const struct commit *commit);\n-extern void put_revision_mark(const struct rev_info *revs, const struct commit *commit);\n+extern char *get_revision_mark(const struct rev_info *revs,\n+\t\t\t       const struct commit *commit);\n+extern void put_revision_mark(const struct rev_info *revs,\n+\t\t\t      const struct commit *commit);\n \n extern void mark_parents_uninteresting(struct commit *commit);\n extern void mark_tree_uninteresting(struct tree *tree);\n@@ -220,15 +224,19 @@ struct name_path {\n \n char *path_name(const struct name_path *path, const char *name);\n \n-extern void show_object_with_name(FILE *, struct object *, const struct name_path *, const char *);\n+extern void show_object_with_name(FILE *, struct object *,\n+\t\t\t\t  const struct name_path *, const char *);\n \n extern void add_object(struct object *obj,\n \t\t       struct object_array *p,\n \t\t       struct name_path *path,\n \t\t       const char *name);\n \n-extern void add_pending_object(struct rev_info *revs, struct object *obj, const char *name);\n-extern void add_pending_sha1(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags);\n+extern void add_pending_object(struct rev_info *revs,\n+\t\t\t       struct object *obj, const char *name);\n+extern void add_pending_sha1(struct rev_info *revs,\n+\t\t\t     const char *name, const unsigned char *sha1,\n+\t\t\t     unsigned int flags);\n \n extern void add_head_to_pending(struct rev_info *);\n \n@@ -238,7 +246,9 @@ enum commit_action {\n \tcommit_error\n };\n \n-extern enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit);\n-extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n+extern enum commit_action get_commit_action(struct rev_info *revs,\n+\t\t\t\t\t    struct commit *commit);\n+extern enum commit_action simplify_commit(struct rev_info *revs,\n+\t\t\t\t\t  struct commit *commit);\n \n #endif\n-- \n1.8.2.3\n"},{"id":"217939","messageId":"1368995232-11042-10-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 09/17] gc_boundary(): move the check \"alloc <= nr\" to caller","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:04Z","receivedAt":"2013-05-19T20:27:04Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"There is no logical reason for this test to be here.  At the caller we\nmight be able to figure out its meaning.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n revision.c | 27 ++++++++++++---------------\n 1 file changed, 12 insertions(+), 15 deletions(-)\n\ndiff --git a/revision.c b/revision.c\nindex 8ac88d6..2e0992b 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2437,23 +2437,19 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \n static void gc_boundary(struct object_array *array)\n {\n-\tunsigned nr = array->nr;\n-\tunsigned alloc = array->alloc;\n+\tunsigned nr = array->nr, i, j;\n \tstruct object_array_entry *objects = array->objects;\n \n-\tif (alloc <= nr) {\n-\t\tunsigned i, j;\n-\t\tfor (i = j = 0; i < nr; i++) {\n-\t\t\tif (objects[i].item->flags & SHOWN)\n-\t\t\t\tcontinue;\n-\t\t\tif (i != j)\n-\t\t\t\tobjects[j] = objects[i];\n-\t\t\tj++;\n-\t\t}\n-\t\tfor (i = j; i < nr; i++)\n-\t\t\tobjects[i].item = NULL;\n-\t\tarray->nr = j;\n+\tfor (i = j = 0; i < nr; i++) {\n+\t\tif (objects[i].item->flags & SHOWN)\n+\t\t\tcontinue;\n+\t\tif (i != j)\n+\t\t\tobjects[j] = objects[i];\n+\t\tj++;\n \t}\n+\tfor (i = j; i < nr; i++)\n+\t\tobjects[i].item = NULL;\n+\tarray->nr = j;\n }\n \n static void create_boundary_commit_list(struct rev_info *revs)\n@@ -2577,7 +2573,8 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n \t\t\tcontinue;\n \t\tp->flags |= CHILD_SHOWN;\n-\t\tgc_boundary(&revs->boundary_commits);\n+\t\tif (revs->boundary_commits.alloc <= revs->boundary_commits.nr)\n+\t\t\tgc_boundary(&revs->boundary_commits);\n \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n \t}\n \n-- \n1.8.2.3\n"},{"id":"217943","messageId":"1368995232-11042-11-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 10/17] get_revision_internal(): make check less mysterious","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:05Z","receivedAt":"2013-05-19T20:27:05Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The condition under which gc_boundary() is called was previously\n\n    if (alloc <= nr)\n\n.  But by construction, nr can never exceed alloc, so the check looks\nunnecessarily mysterious.  In fact, the purpose of the check is to try\nto avoid a realloc() call by shrinking the array if possible if it is\nat its allocation limit when a new element is about to be added.  So\nchange the check to\n\n    if (nr == alloc)\n\nand add a comment to explain what's going on.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\nPlease check that I have properly described the purpose of this check.\n\nThe way the code is written, it looks like a bad pattern of growth and\nshrinkage of the array (namely, just under the resize limit) could\ncause gc_boundary() to be called over and over again with (most of)\nthe same data.  I hope that the author had some reason to believe that\nsuch a pattern is unlikely.\n\n revision.c | 4 +++-\n 1 file changed, 3 insertions(+), 1 deletion(-)\n\ndiff --git a/revision.c b/revision.c\nindex 2e0992b..19c59f4 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2573,8 +2573,10 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n \t\t\tcontinue;\n \t\tp->flags |= CHILD_SHOWN;\n-\t\tif (revs->boundary_commits.alloc <= revs->boundary_commits.nr)\n+\t\tif (revs->boundary_commits.nr == revs->boundary_commits.alloc) {\n+\t\t\t/* Try to make space and thereby avoid a realloc(): */\n \t\t\tgc_boundary(&revs->boundary_commits);\n+\t\t}\n \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n \t}\n \n-- \n1.8.2.3\n"},{"id":"217934","messageId":"1368995232-11042-12-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 11/17] object_array: add function object_array_filter()","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:06Z","receivedAt":"2013-05-19T20:27:06Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Add a function that allows unwanted entries in an object_array to be\nremoved.  This encapsulation is a step towards giving object_array\nownership of its entries' name memory.\n\nUse the new function to replace revision.c:gc_boundary().\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n object.c   | 16 ++++++++++++++++\n object.h   | 11 +++++++++++\n revision.c | 28 ++++++++++------------------\n 3 files changed, 37 insertions(+), 18 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 20703f5..fcd4a82 100644\n--- a/object.c\n+++ b/object.c\n@@ -278,6 +278,22 @@ void add_object_array_with_mode(struct object *obj, const char *name, struct obj\n \tarray->nr = ++nr;\n }\n \n+void object_array_filter(struct object_array *array,\n+\t\t\t object_array_each_func_t want, void *cb_data)\n+{\n+\tunsigned nr = array->nr, src, dst;\n+\tstruct object_array_entry *objects = array->objects;\n+\n+\tfor (src = dst = 0; src < nr; src++) {\n+\t\tif (want(&objects[src], cb_data)) {\n+\t\t\tif (src != dst)\n+\t\t\t\tobjects[dst] = objects[src];\n+\t\t\tdst++;\n+\t\t}\n+\t}\n+\tarray->nr = dst;\n+}\n+\n void object_array_remove_duplicates(struct object_array *array)\n {\n \tunsigned int ref, src, dst;\ndiff --git a/object.h b/object.h\nindex 97d384b..0d39ff4 100644\n--- a/object.h\n+++ b/object.h\n@@ -85,6 +85,17 @@ int object_list_contains(struct object_list *list, struct object *obj);\n /* Object array handling .. */\n void add_object_array(struct object *obj, const char *name, struct object_array *array);\n void add_object_array_with_mode(struct object *obj, const char *name, struct object_array *array, unsigned mode);\n+\n+typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n+\n+/*\n+ * Apply want to each entry in array, retaining only the entries for\n+ * which the function returns true.  Preserve the order of the entries\n+ * that are retained.\n+ */\n+void object_array_filter(struct object_array *array,\n+\t\t\t object_array_each_func_t want, void *cb_data);\n+\n void object_array_remove_duplicates(struct object_array *);\n \n void clear_object_flags(unsigned flags);\ndiff --git a/revision.c b/revision.c\nindex 19c59f4..ddc6d7c 100644\n--- a/revision.c\n+++ b/revision.c\n@@ -2435,23 +2435,6 @@ static struct commit *get_revision_1(struct rev_info *revs)\n \treturn NULL;\n }\n \n-static void gc_boundary(struct object_array *array)\n-{\n-\tunsigned nr = array->nr, i, j;\n-\tstruct object_array_entry *objects = array->objects;\n-\n-\tfor (i = j = 0; i < nr; i++) {\n-\t\tif (objects[i].item->flags & SHOWN)\n-\t\t\tcontinue;\n-\t\tif (i != j)\n-\t\t\tobjects[j] = objects[i];\n-\t\tj++;\n-\t}\n-\tfor (i = j; i < nr; i++)\n-\t\tobjects[i].item = NULL;\n-\tarray->nr = j;\n-}\n-\n static void create_boundary_commit_list(struct rev_info *revs)\n {\n \tunsigned i;\n@@ -2493,6 +2476,15 @@ static void create_boundary_commit_list(struct rev_info *revs)\n \tsort_in_topological_order(&revs->commits, revs->lifo);\n }\n \n+/*\n+ * Return true for entries that have not yet been shown.  (This is an\n+ * object_array_each_func_t.)\n+ */\n+static int entry_unshown(struct object_array_entry *entry, void *cb_data_unused)\n+{\n+\treturn !(entry->item->flags & SHOWN);\n+}\n+\n static struct commit *get_revision_internal(struct rev_info *revs)\n {\n \tstruct commit *c = NULL;\n@@ -2575,7 +2567,7 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n \t\tp->flags |= CHILD_SHOWN;\n \t\tif (revs->boundary_commits.nr == revs->boundary_commits.alloc) {\n \t\t\t/* Try to make space and thereby avoid a realloc(): */\n-\t\t\tgc_boundary(&revs->boundary_commits);\n+\t\t\tobject_array_filter(&revs->boundary_commits, entry_unshown, NULL);\n \t\t}\n \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n \t}\n-- \n1.8.2.3\n"},{"id":"217942","messageId":"1368995232-11042-13-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 12/17] object_array_remove_duplicates(): rewrite to reduce copying","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:07Z","receivedAt":"2013-05-19T20:27:07Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The old version copied one entry to its destination position, then\ndeleted any matching entries from the tail of the array.  This\nrequired the tail of the array to be copied multiple times.  It didn't\naffect the complexity of the algorithm because the whole tail has to\nbe searched through anyway.  But all the copying was unnecessary.\n\nInstead, check for the existence of an entry with the same name in the\n*head* of the list before copying an entry to its final position.\nThis way each entry has to be copied at most one time.\n\nExtract a helper function contains_name() to do a bit of the work.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n object.c | 32 +++++++++++++++++++++-----------\n object.h |  6 +++++-\n 2 files changed, 26 insertions(+), 12 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex fcd4a82..10b5349 100644\n--- a/object.c\n+++ b/object.c\n@@ -294,22 +294,32 @@ void object_array_filter(struct object_array *array,\n \tarray->nr = dst;\n }\n \n+/*\n+ * Return true iff array already contains an entry with name.\n+ */\n+static int contains_name(struct object_array *array, const char *name)\n+{\n+\tunsigned nr = array->nr, i;\n+\tstruct object_array_entry *object = array->objects;\n+\n+\tfor (i = 0; i < nr; i++, object++)\n+\t\tif (!strcmp(object->name, name))\n+\t\t\treturn 1;\n+\treturn 0;\n+}\n+\n void object_array_remove_duplicates(struct object_array *array)\n {\n-\tunsigned int ref, src, dst;\n+\tunsigned nr = array->nr, src;\n \tstruct object_array_entry *objects = array->objects;\n \n-\tfor (ref = 0; ref + 1 < array->nr; ref++) {\n-\t\tfor (src = ref + 1, dst = src;\n-\t\t     src < array->nr;\n-\t\t     src++) {\n-\t\t\tif (!strcmp(objects[ref].name, objects[src].name))\n-\t\t\t\tcontinue;\n-\t\t\tif (src != dst)\n-\t\t\t\tobjects[dst] = objects[src];\n-\t\t\tdst++;\n+\tarray->nr = 0;\n+\tfor (src = 0; src < nr; src++) {\n+\t\tif (!contains_name(array, objects[src].name)) {\n+\t\t\tif (src != array->nr)\n+\t\t\t\tobjects[array->nr] = objects[src];\n+\t\t\tarray->nr++;\n \t\t}\n-\t\tarray->nr = dst;\n \t}\n }\n \ndiff --git a/object.h b/object.h\nindex 0d39ff4..6c1c27f 100644\n--- a/object.h\n+++ b/object.h\n@@ -96,7 +96,11 @@ typedef int (*object_array_each_func_t)(struct object_array_entry *, void *);\n void object_array_filter(struct object_array *array,\n \t\t\t object_array_each_func_t want, void *cb_data);\n \n-void object_array_remove_duplicates(struct object_array *);\n+/*\n+ * Remove from array all but the first entry with a given name.\n+ * Warning: this function uses an O(N^2) algorithm.\n+ */\n+void object_array_remove_duplicates(struct object_array *array);\n \n void clear_object_flags(unsigned flags);\n \n-- \n1.8.2.3\n"},{"id":"217935","messageId":"1368995232-11042-14-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 13/17] fsck: don't put a void*-shaped peg in a char*-shaped hole","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:08Z","receivedAt":"2013-05-19T20:27:08Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The source of this nonsense was\n\n    04d3975937 fsck: reduce stack footprint\n\n, which wedged a pointer to parent into the object_array_entry's name\nfield.  The parent pointer was passed to traverse_one_object(), even\nthough that function *didn't use it*.\n\nThe useless code has been deleted over time.  Commit\n\n    a1cdc25172 fsck: drop unused parameter from traverse_one_object()\n\nremoved the parent pointer from traverse_one_object()'s\nsignature. Commit\n\n    c0aa335c95 Remove unused variables\n\nremoved the code that read the parent pointer back out of the name\nfield.\n\nThis commit takes the last step: don't write the parent pointer into\nthe name field in the first place.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\nI thought that this misuse of the name field was going to be a\nshowstopper for changing how the name's memory is managed, but then I\nnoticed that the value stored here is never used.\n\n builtin/fsck.c | 2 +-\n 1 file changed, 1 insertion(+), 1 deletion(-)\n\ndiff --git a/builtin/fsck.c b/builtin/fsck.c\nindex bb9a2cd..9909b6d 100644\n--- a/builtin/fsck.c\n+++ b/builtin/fsck.c\n@@ -112,7 +112,7 @@ static int mark_object(struct object *obj, int type, void *data)\n \t\treturn 1;\n \t}\n \n-\tadd_object_array(obj, (void *) parent, &pending);\n+\tadd_object_array(obj, NULL, &pending);\n \treturn 0;\n }\n \n-- \n1.8.2.3\n"},{"id":"217940","messageId":"1368995232-11042-15-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 14/17] find_first_merges(): initialize merges variable using initializer","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:09Z","receivedAt":"2013-05-19T20:27:09Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n submodule.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/submodule.c b/submodule.c\nindex e728025..b837c04 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -846,7 +846,7 @@ static int find_first_merges(struct object_array *result, const char *path,\n \t\tstruct commit *a, struct commit *b)\n {\n \tint i, j;\n-\tstruct object_array merges;\n+\tstruct object_array merges = OBJECT_ARRAY_INIT;\n \tstruct commit *commit;\n \tint contains_another;\n \n@@ -856,7 +856,6 @@ static int find_first_merges(struct object_array *result, const char *path,\n \tstruct rev_info revs;\n \tstruct setup_revision_opt rev_opts;\n \n-\tmemset(&merges, 0, sizeof(merges));\n \tmemset(result, 0, sizeof(struct object_array));\n \tmemset(&rev_opts, 0, sizeof(rev_opts));\n \n-- \n1.8.2.3\n"},{"id":"217937","messageId":"1368995232-11042-16-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 15/17] find_first_merges(): remove unnecessary code","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:10Z","receivedAt":"2013-05-19T20:27:10Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"No names are ever set for the object_array_entries in merges, so there\nis no need to pretend to copy them to the result array.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n submodule.c | 3 +--\n 1 file changed, 1 insertion(+), 2 deletions(-)\n\ndiff --git a/submodule.c b/submodule.c\nindex b837c04..ad476ce 100644\n--- a/submodule.c\n+++ b/submodule.c\n@@ -893,8 +893,7 @@ static int find_first_merges(struct object_array *result, const char *path,\n \t\t}\n \n \t\tif (!contains_another)\n-\t\t\tadd_object_array(merges.objects[i].item,\n-\t\t\t\t\t merges.objects[i].name, result);\n+\t\t\tadd_object_array(merges.objects[i].item, NULL, result);\n \t}\n \n \tfree(merges.objects);\n-- \n1.8.2.3\n"},{"id":"217938","messageId":"1368995232-11042-17-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[RFC 16/17] object_array_entry: copy name before storing in name field","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:11Z","receivedAt":"2013-05-19T20:27:11Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Change object_array and object_array_entry to copy the name before\nstoring it in the name field, and free it when an entry is deleted\nfrom the array.  This is useful because some of the name strings\npassed to add_object_array() or add_object_array_with_mode() are\nrefnames whose lifetime is not defined by the refs API (and which we\nwant to shorten).\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\nThis is the culmination of the last few commits.  Since some callers\nwant to store refnames in the name field of object_array elements, but\nwe don't want those callers to assume that the refnames that they got\nfrom for_each_ref() have infinite lifetime, the easiest thing to do is\nhave object_array make a copy of the names before writing them in the\nentries, and to free the names for entries that are no longer in use.\nThis change fixes the problem, but has some disadvantages:\n\n* It requires extra copies to be made of strings that are already\n  copies, for example when the results of path_name(path, name) are\n  used as a name in revision.c:add_object().  This might be rare\n  enough that it can be ignored (though the original result of\n  path_name() would have to be freed, which this patch doesn't do so\n  there is a memory leak).\n\n* Many callers store the empty string (\"\") as the name; for example,\n  most of the entries created during a run of rev-list have \"\" as\n  their name.  This means that lots of needless copies of \"\" are being\n  made.  I think that the best solution to this problem would be to\n  store NULL rather than \"\" for such entries, but I haven't figured\n  out all of the places where the name is used.\n\nThe alternative would be to have callers make the copies if necessary\n*before* passing the names into add_object_array(), and themselves\nensure that those copies get freed sometime.  This would be more work:\neffectively each object_array would have to have its own memory\nownership policy and we would have to figure out exactly where in the\ncode entries are added and removed from particular lists.\n\nSince I'm not too clear on what these names are used for, how many\nobject_array entries are created in different scenarios, etc., I\ndecided to submit this patch as an RFC to get some feedback before I\nwork on a final solution.\n\n object.c | 6 +++++-\n object.h | 6 +++++-\n 2 files changed, 10 insertions(+), 2 deletions(-)\n\ndiff --git a/object.c b/object.c\nindex 10b5349..a678c1b 100644\n--- a/object.c\n+++ b/object.c\n@@ -273,7 +273,7 @@ void add_object_array_with_mode(struct object *obj, const char *name, struct obj\n \t\tarray->objects = objects;\n \t}\n \tobjects[nr].item = obj;\n-\tobjects[nr].name = name;\n+\tobjects[nr].name = name ? xstrdup(name) : NULL;\n \tobjects[nr].mode = mode;\n \tarray->nr = ++nr;\n }\n@@ -289,6 +289,8 @@ void object_array_filter(struct object_array *array,\n \t\t\tif (src != dst)\n \t\t\t\tobjects[dst] = objects[src];\n \t\t\tdst++;\n+\t\t} else {\n+\t\t\tfree(objects[src].name);\n \t\t}\n \t}\n \tarray->nr = dst;\n@@ -319,6 +321,8 @@ void object_array_remove_duplicates(struct object_array *array)\n \t\t\tif (src != array->nr)\n \t\t\t\tobjects[array->nr] = objects[src];\n \t\t\tarray->nr++;\n+\t\t} else {\n+\t\t\tfree(objects[src].name);\n \t\t}\n \t}\n }\ndiff --git a/object.h b/object.h\nindex 6c1c27f..f2c503a 100644\n--- a/object.h\n+++ b/object.h\n@@ -11,7 +11,11 @@ struct object_array {\n \tunsigned int alloc;\n \tstruct object_array_entry {\n \t\tstruct object *item;\n-\t\tconst char *name;\n+\t\t/*\n+\t\t * name or NULL.  If non-NULL, the memory pointed to\n+\t\t * is owned by this object.\n+\t\t */\n+\t\tchar *name;\n \t\tunsigned mode;\n \t} *objects;\n };\n-- \n1.8.2.3\n"},{"id":"217936","messageId":"1368995232-11042-18-git-send-email-mhagger@alum.mit.edu","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"[RFC 17/17] refs: document the lifetime of the refname passed to each_ref_fn","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-19T20:27:12Z","receivedAt":"2013-05-19T20:27:12Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"The lifetime of the refname was never documented, but some callers\nused to assume that its lifetime was essentially permanent.  The\ncommits leading up to this have disabused such callers of that notion.\n\nThe new status quo is that the API explicitly does *not* guarantee\nthat the refname string lives beyond a single callback invocation.\nDocument that fact.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\nThis patch is the ultimate goal of the series, and I include it for\nillustration, but it obviously shouldn't be committed before the\nobject_array questions have been answered and the rest of the code has\nbeen audited more carefully.\n\n refs.h | 22 ++++++++++++++++------\n 1 file changed, 16 insertions(+), 6 deletions(-)\n\ndiff --git a/refs.h b/refs.h\nindex a35eafc..e67fb07 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -15,13 +15,23 @@ struct ref_lock {\n #define REF_ISBROKEN 0x04\n \n /*\n- * Calls the specified function for each ref file until it returns\n- * nonzero, and returns the value.  Please note that it is not safe to\n- * modify references while an iteration is in progress, unless the\n- * same callback function invocation that modifies the reference also\n- * returns a nonzero value to immediately stop the iteration.\n+ * The callback functions for the for_each_*() functions below must\n+ * have this signature.  The memory pointed to by the refname argument\n+ * is only guaranteed to be valid for the duration of a single\n+ * callback invocation.\n+ */\n+typedef int each_ref_fn(const char *refname,\n+\t\t\tconst unsigned char *sha1, int flags, void *cb_data);\n+\n+/*\n+ * The following functions invoke the specified callback function for\n+ * each reference indicated.  If the function ever returns a nonzero\n+ * value, stop the iteration and return that value.  Please note that\n+ * it is not safe to modify references while an iteration is in\n+ * progress, unless the same callback function invocation that\n+ * modifies the reference also returns a nonzero value to immediately\n+ * stop the iteration.\n  */\n-typedef int each_ref_fn(const char *refname, const unsigned char *sha1, int flags, void *cb_data);\n extern int head_ref(each_ref_fn, void *);\n extern int for_each_ref(each_ref_fn, void *);\n extern int for_each_ref_in(const char *, each_ref_fn, void *);\n-- \n1.8.2.3\n"},{"id":"217973","messageId":"CALKQrgfpAqWESDrjE5po+XPvK+xft=PVwDXr3E7BU28jdDRcZA@mail.gmail.com","threadId":"33874","inReplyTo":"1368995232-11042-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T10:28:29Z","receivedAt":"2013-05-20T10:28:29Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Sun, May 19, 2013 at 10:26 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> Recently a number of race conditions related to references have been\n> discovered.  There is likely to be a two-pronged solution to the\n> races:\n>\n> * For traditional, filesystem-based references, there will have to be\n>   more checks that the ref caches are still up-to-date at the time of\n>   their use (see, for example, [1]).  If not, the ref cache will have\n>   to be invalidated and reloaded.  Assuming that the invalidation of\n>   the old cache includes freeing its memory, such an invalidation will\n>   cause lots of refname strings to be freed even though callers might\n>   still hold references to them.\n>\n> * For server-class installations, filesystem-based references might\n>   not be robust enough for 100% reliable operation, because the\n>   reading of the complete set of references is not an atomic\n>   operation.  If another reference storage mechanism is developed,\n>   there is no reason to expect the refnames strings to have long\n>   lifetimes.\n\n(Sorry for going slightly off-topic and returning to the general\ndiscussion on how to resolve the race conditions...)\n\nFor server-class installations we need ref storage that can be read\n(and updated?) atomically, and the current system of loose + packed\nfiles won't work since reading (and updating) more than a single file\nis not an atomic operation. Trivially, one could resolve this by\ndropping loose refs, and always using a single packed-refs file, but\nthat would make it prohibitively expensive to update refs (the entire\npacked-refs file must be rewritten for every update).\n\nNow, observe that we don't have these race conditions in the object\ndatabase, because it is an add-only immutable data store.\n\nWhat if we stored the refs as a tree object in the object database,\nreferenced by a single (loose) ref? There would be a _single_ (albeit\nhighly contentious) file outside the object database that represent\nthe current state of the refs, but hopefully we can guarantee\natomicity when reading (and updating?) that one file. Transactions can\nbe done by:\n 1. Recording the tree id holding the refs before starting manipulation.\n 2. Creating a new tree object holding the manipulated state.\n 3. Re-checking the tree id before replacing the loose ref. If\nunchanged: commit, else: rollback/error out.\n\nAll readers would trivially have access to a consistent refs view,\nsince the state of the entire refs hierarchy is held in the tree id\nread from that single loose ref.\n\nIt seems to me this should be somewhat less prohibitively expensive\nthan maintaining all refs in a single packed-refs file. That said, we\ndo end up producing a few new objects for every single ref update,\nmost of which would be thrown away by a future \"gc\". This might bog\nthings down, but I'm not sure how much.\n\nI'm sure someone must have had this idea before (although I don't\nremember this alternative being raised at the Git Merge conference),\nso please enlighten me as to why this won't work... ;)\n\n...Johan\n\n\nPS: Keeping reflogs is just a matter of wrapping the ref tree in a\ncommit object using the previous state of the ref tree as its parent.\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"217975","messageId":"CALKQrgeZ3yOogZhumQ6sQ=7B4XoEUDxPNt6Lj7ZAs13oJTOeUA@mail.gmail.com","threadId":"33874","inReplyTo":"1368995232-11042-17-git-send-email-mhagger@alum.mit.edu","subject":"Re: [RFC 16/17] object_array_entry: copy name before storing in name field","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T10:33:06Z","receivedAt":"2013-05-20T10:33:06Z","isPatch":false,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Sun, May 19, 2013 at 10:27 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n> This is the culmination of the last few commits.  Since some callers\n> want to store refnames in the name field of object_array elements, but\n> we don't want those callers to assume that the refnames that they got\n> from for_each_ref() have infinite lifetime, the easiest thing to do is\n> have object_array make a copy of the names before writing them in the\n> entries, and to free the names for entries that are no longer in use.\n> This change fixes the problem, but has some disadvantages:\n>\n> * It requires extra copies to be made of strings that are already\n>   copies, for example when the results of path_name(path, name) are\n>   used as a name in revision.c:add_object().  This might be rare\n>   enough that it can be ignored (though the original result of\n>   path_name() would have to be freed, which this patch doesn't do so\n>   there is a memory leak).\n>\n> * Many callers store the empty string (\"\") as the name; for example,\n>   most of the entries created during a run of rev-list have \"\" as\n>   their name.  This means that lots of needless copies of \"\" are being\n>   made.  I think that the best solution to this problem would be to\n>   store NULL rather than \"\" for such entries, but I haven't figured\n>   out all of the places where the name is used.\n\nUse strbufs?\n\nNo allocation (except for the strbuf object itself) is needed for\nempty strings, and string ownership and be transferred to and from it\nto prevent extra copies.\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"217977","messageId":"519A13F1.9070900@alum.mit.edu","threadId":"33874","inReplyTo":"CALKQrgfpAqWESDrjE5po+XPvK+xft=PVwDXr3E7BU28jdDRcZA@mail.gmail.com","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-20T12:15:45Z","receivedAt":"2013-05-20T12:15:45Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This is a very interesting idea.  \"It's turtles all the way down.\"\n\nOn 05/20/2013 12:28 PM, Johan Herland wrote:\n> (Sorry for going slightly off-topic and returning to the general\n> discussion on how to resolve the race conditions...)\n> \n> For server-class installations we need ref storage that can be read\n> (and updated?) atomically, and the current system of loose + packed\n> files won't work since reading (and updating) more than a single file\n> is not an atomic operation. Trivially, one could resolve this by\n> dropping loose refs, and always using a single packed-refs file, but\n> that would make it prohibitively expensive to update refs (the entire\n> packed-refs file must be rewritten for every update).\n\nCorrect, or the \"packed-refs\" file would have to be updated in place\nusing some database-style approach for locking/transactions/whatever.\n\n> Now, observe that we don't have these race conditions in the object\n> database, because it is an add-only immutable data store.\n\nExcept for prune, of course, which can cause race conditions WRT to writers.\n\n> What if we stored the refs as a tree object in the object database,\n> referenced by a single (loose) ref? There would be a _single_ (albeit\n> highly contentious) file outside the object database that represent\n> the current state of the refs, but hopefully we can guarantee\n> atomicity when reading (and updating?) that one file. Transactions can\n> be done by:\n>  1. Recording the tree id holding the refs before starting manipulation.\n>  2. Creating a new tree object holding the manipulated state.\n>  3. Re-checking the tree id before replacing the loose ref. If\n> unchanged: commit, else: rollback/error out.\n\nThere are two closely related possibilities and I'm not sure which one\nyou mean:\n\n* Effectively treat all of the refs as loose refs, but stored not in the\nfilesystem but rather in a hierarchical tree structure in the object\ndatabase.  E.g., all of the refs directly under \"refs/heads\" would be in\none tree object, those in refs/remotes/foo in a second, those for\nrefs/remotes/bar in another etc. and all of them linked up together in a\ntree object representing \"refs\".\n\n* Effectively treat all of the refs as packed refs, but store the single\n\"packed-refs\" file as a single object in the object database.\n\n(The first alternative sounds more practical to me.  I also guess that's\nwhat you mean, since down below you say that each change would require\nproducing \"a few objects\".)\n\nOf course in either case we couldn't use a tree object directly, because\nthese new \"reference tree\" objects would refer not only to blobs and\nother trees but also to commits and tags.\n\n> All readers would trivially have access to a consistent refs view,\n> since the state of the entire refs hierarchy is held in the tree id\n> read from that single loose ref.\n> \n> It seems to me this should be somewhat less prohibitively expensive\n> than maintaining all refs in a single packed-refs file. That said, we\n> do end up producing a few new objects for every single ref update,\n> most of which would be thrown away by a future \"gc\". This might bog\n> things down, but I'm not sure how much.\n> \n> I'm sure someone must have had this idea before (although I don't\n> remember this alternative being raised at the Git Merge conference),\n> so please enlighten me as to why this won't work... ;)\n\n[I know this is not what you are suggesting, but I am reminded of\nSubversion, which stores trunk, branches, and tags in the same \"tree\"\nspace as the contents of the working trees.  A Subversion commit\nreferences a gigantic tree encompassing all branches of development and\nall files on all of those branches (with cheap copies to reduce the\nredundancy):\n\n    /\n    /trunk/\n    /trunk/Makefile\n    /trunk/src/\n    /trunk/src/foo.c\n    /branches/\n    /branches/next/\n    /branches/next/Makefile\n    /branches/next/src/\n    /branches/next/src/foo.c\n    /branches/pu/\n    /branches/pu/Makefile\n    /branches/pu/src/\n    /branches/pu/src/foo.c\n    /tags/\n    /tags/v1.8.2/\n    /tags/v1.8.2/Makefile\n    /tags/v1.8.2/src/\n    /tags/v1.8.2/src/foo.c\n    etc...\n\nA Subversion commit thus describes the state of *every* branch and tag\nat that moment in time.  The model is conceptually very simple (in fact,\ntoo simple, and I believe the Subversion developers regret not having\ndistinguished between the branch namespace and the file namespace).]\n\nThe main difficulty with this idea will be the extreme contention on\nthat \"last loose reference file\" pointing at the root of the reference\ntree.  Essentially *every* change to the repository will have to create\na new reference tree and point this file at the new version.  I doubt\nthat would be a problem for short-lived operations, but I fear that a\nlong-lived operation would *never* get done.  By the time it had\nfinished constructing its new reference tree, some other short-lived\noperation will have changed it, and the long-lived process will have to\nchoose between\n\n* Restart from the beginning.\n\n* Die with a kind of \"concurrent modification error\".\n\n* Resolve the difference between the reference tree at the start of its\noperation and the reference tree as it exists when it is done with the\nchanges that they want to make.  In some cases this might be able to be\ndone automatically as a kind of \"reference tree merge\" but the logic\nmight have to vary from case to case.\n\n> PS: Keeping reflogs is just a matter of wrapping the ref tree in a\n> commit object using the previous state of the ref tree as its parent.\n\nYes, there are a lot of nice aspects to this idea in that it reuses\nconcepts with which we are already familiar.  For example, fetching from\na remote would approximately hook the remote's entire reference tree\ninto a subtree of the local \"refs/remotes\" reference subtree.  But with\nthings like reflogs we would have to be careful not to keep obsolete\nobjects around *forever*--there would have to be some mechanism to prune\nthe old reference history.\n\nAltogether a very interesting idea.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"217979","messageId":"519A365E.6020807@alum.mit.edu","threadId":"33874","inReplyTo":"CALKQrgeZ3yOogZhumQ6sQ=7B4XoEUDxPNt6Lj7ZAs13oJTOeUA@mail.gmail.com","subject":"Re: [RFC 16/17] object_array_entry: copy name before storing in name field","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-20T14:42:38Z","receivedAt":"2013-05-20T14:42:38Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/20/2013 12:33 PM, Johan Herland wrote:\n> On Sun, May 19, 2013 at 10:27 PM, Michael Haggerty <mhagger@alum.mit.edu> wrote:\n>> This is the culmination of the last few commits.  Since some callers\n>> want to store refnames in the name field of object_array elements, but\n>> we don't want those callers to assume that the refnames that they got\n>> from for_each_ref() have infinite lifetime, the easiest thing to do is\n>> have object_array make a copy of the names before writing them in the\n>> entries, and to free the names for entries that are no longer in use.\n>> This change fixes the problem, but has some disadvantages:\n>>\n>> * It requires extra copies to be made of strings that are already\n>>   copies, for example when the results of path_name(path, name) are\n>>   used as a name in revision.c:add_object().  This might be rare\n>>   enough that it can be ignored (though the original result of\n>>   path_name() would have to be freed, which this patch doesn't do so\n>>   there is a memory leak).\n>>\n>> * Many callers store the empty string (\"\") as the name; for example,\n>>   most of the entries created during a run of rev-list have \"\" as\n>>   their name.  This means that lots of needless copies of \"\" are being\n>>   made.  I think that the best solution to this problem would be to\n>>   store NULL rather than \"\" for such entries, but I haven't figured\n>>   out all of the places where the name is used.\n> \n> Use strbufs?\n> \n> No allocation (except for the strbuf object itself) is needed for\n> empty strings, and string ownership and be transferred to and from it\n> to prevent extra copies.\n\nThat would cost two extra size_t per object_array_entry.  I have the\nfeeling that this structure is used often enough that the extra overhead\nwould be a disadvantage, but I'm not sure.\n\nThe obvious alternative would be to teach users to deal with NULL and\neither add another constructor alternative that transfers string\nownership or *always* transfer string ownership and change the callers\nto call xstrdup() if they don't already own the name string.  I think I\nwill try that approach first.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"217981","messageId":"7vfvxhwqt1.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"CALKQrgfpAqWESDrjE5po+XPvK+xft=PVwDXr3E7BU28jdDRcZA@mail.gmail.com","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-20T16:37:30Z","receivedAt":"2013-05-20T16:37:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> For server-class installations we need ref storage that can be read\n> (and updated?) atomically, and the current system of loose + packed\n> files won't work since reading (and updating) more than a single file\n> is not an atomic operation. Trivially, one could resolve this by\n> dropping loose refs, and always using a single packed-refs file, but\n> that would make it prohibitively expensive to update refs (the entire\n> packed-refs file must be rewritten for every update).\n>\n> Now, observe that we don't have these race conditions in the object\n> database, because it is an add-only immutable data store.\n>\n> What if we stored the refs as a tree object in the object database,\n> referenced by a single (loose) ref?\n\nWhat is the cost of updating a single branch with that scheme?\n\nDoesn't it end up recording roughly the same amount of information\nas updating a single packed-refs file that is flat, but with the\nneed to open a few tree objects (top-level, refs/, and refs/heads/),\nwriting out a blob that stores the object name at the tip, computing\nthe updated trees (refs/heads/, refs/ and top-level), and then\nfinally doing the compare-and-swap of that single loose ref?\n\nYou may guarantee atomicity but it is the same granularity of\natomicity as a single packed-refs file.  When you are updating a\nbranch while somebody else is updating a tag, of course you do not\nhave to look at refs/tags/ in your operation and you can write out\nyour final packed-refs equivalent tree to the object database\nwithout racing with the other process, but the top-level you come up\nwith and the top-level the other process comes up with (which has\nan up-to-date refs/tags/ part, but has a stale refs/heads/ part from\nyour point of view) have to race to update that single loose ref,\nand one of you have to back out.\n\nThat \"backing out\" can be made more intelligently than just dying\nwith \"compare and swap failed--please retry\" message, e.g. you at\nthat point notice what you started with, what the other party did\nwhile you were working on (i.e. updating refs/tags/), and three-way\nmerge the refs tree, and in cases where \"all refs recorded as loose\nrefs\" scheme wouldn't have resulted in problematic conflict, such a\nthree-way merge would resolve trivially (you updated refs/heads/ and\nthe update by the other process to refs/tags/ would not conflict\nwith what you did).  But the same three-way merge scheme can be\nemployed with the current flat single packed-refs scheme, can't it?\n\nEven worse, what is the cost of looking up the value of a single\nbranch?  You would need to open a few tree objects and the leaf blob\nthat records the object name the ref points at, wouldn't you?\n\nRight now, such a look-up is either opening a single small file and\nreading the first 41 bytes off of it, and falling back (when the ref\nin question is packed) to read a single packed-refs file and finding\nthe ref you want from it.\n\nSo...\n"},{"id":"217982","messageId":"20130520164458.GA27788@sigill.intra.peff.net","threadId":"33874","inReplyTo":"519A365E.6020807@alum.mit.edu","subject":"Re: [RFC 16/17] object_array_entry: copy name before storing in name field","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-20T16:44:58Z","receivedAt":"2013-05-20T16:44:58Z","isPatch":false,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 20, 2013 at 04:42:38PM +0200, Michael Haggerty wrote:\n\n> >> * Many callers store the empty string (\"\") as the name; for example,\n> >>   most of the entries created during a run of rev-list have \"\" as\n> >>   their name.  This means that lots of needless copies of \"\" are being\n> >>   made.  I think that the best solution to this problem would be to\n> >>   store NULL rather than \"\" for such entries, but I haven't figured\n> >>   out all of the places where the name is used.\n> > \n> > Use strbufs?\n> > \n> > No allocation (except for the strbuf object itself) is needed for\n> > empty strings, and string ownership and be transferred to and from it\n> > to prevent extra copies.\n> \n> That would cost two extra size_t per object_array_entry.  I have the\n> feeling that this structure is used often enough that the extra overhead\n> would be a disadvantage, but I'm not sure.\n> \n> The obvious alternative would be to teach users to deal with NULL and\n> either add another constructor alternative that transfers string\n> ownership or *always* transfer string ownership and change the callers\n> to call xstrdup() if they don't already own the name string.  I think I\n> will try that approach first.\n\nYou could use the same trick that strbuf does: instead of NULL, point to\na well-known empty string literal. Readers do not have to care about\nthis optimization at all; only writers need to recognize the well-known\npointer value. And since we do not update in place but only eventually\nfree, it really is just that anyone calling free() would do \"if (name !=\nwell_known_empty_string)\".\n\n-Peff\n"},{"id":"217983","messageId":"20130520165942.GB27788@sigill.intra.peff.net","threadId":"33874","inReplyTo":"7vfvxhwqt1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2013-05-20T16:59:42Z","receivedAt":"2013-05-20T16:59:42Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Mon, May 20, 2013 at 09:37:30AM -0700, Junio C Hamano wrote:\n\n> Johan Herland <johan@herland.net> writes:\n> \n> > For server-class installations we need ref storage that can be read\n> > (and updated?) atomically, and the current system of loose + packed\n> > files won't work since reading (and updating) more than a single file\n> > is not an atomic operation. Trivially, one could resolve this by\n> > dropping loose refs, and always using a single packed-refs file, but\n> > that would make it prohibitively expensive to update refs (the entire\n> > packed-refs file must be rewritten for every update).\n> >\n> > Now, observe that we don't have these race conditions in the object\n> > database, because it is an add-only immutable data store.\n> >\n> > What if we stored the refs as a tree object in the object database,\n> > referenced by a single (loose) ref?\n> \n> What is the cost of updating a single branch with that scheme?\n\nYeah, I had the same thoughts as you here; I don't think this is really\nmuch better than updating a single packed-refs file. You may only\nhave to touch log(N) of the entries to update the trees along the path\nto your ref (assuming you have a bushy refs/ tree; in practice, of\ncourse, you have a lot of entries in refs/heads/, so you do not quite\nget log behavior). So algorithmically it may be slightly better, but you\npay a much higher constant, in that you are creating many tree objects\nalong the path (and reading them on lookup).\n\nBut more importantly, it introduces contention between two unrelated\nrefs that are being updated. Even if we reconcile the differences\nautomatically (e.g., with a \"merge-and-retry\" strategy), that is going\nto be a serious performance regression for a busy repository, as we\nrepeatedly try to reconcile the serialized updates to the refs/ root\ntree.\n\nAny transactional solution needs to have the equivalent of ref-level\nlocking (i.e., row-level locking in a relational setting). It is OK for\ntwo simultaneous updates to different rows to happen in random order; we\ndon't care about that level of atomicity. The important thing is that\nthe _readers_ see transactions in consistent order; if we know that\nupdate B started after update A finished, then we must never see update\nA without update B reflected. And I think that is more or less a solved\nproblem in the database world.\n\nThat is what prevents:\n\n  git update-ref A B\n  git update-ref -d B\n\nfrom creating a view where the reader sees neither A nor B (which is\nwhat can happen with the current filesystem view).\n\n-Peff\n"},{"id":"217984","messageId":"CALKQrgd3=5Rb5wbDGTV7PQfcingimYf08yEHcbfSCkjGDUU_Ng@mail.gmail.com","threadId":"33874","inReplyTo":"7vfvxhwqt1.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T17:03:52Z","receivedAt":"2013-05-20T17:03:52Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Mon, May 20, 2013 at 6:37 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> Johan Herland <johan@herland.net> writes:\n>> For server-class installations we need ref storage that can be read\n>> (and updated?) atomically, and the current system of loose + packed\n>> files won't work since reading (and updating) more than a single file\n>> is not an atomic operation. Trivially, one could resolve this by\n>> dropping loose refs, and always using a single packed-refs file, but\n>> that would make it prohibitively expensive to update refs (the entire\n>> packed-refs file must be rewritten for every update).\n>>\n>> Now, observe that we don't have these race conditions in the object\n>> database, because it is an add-only immutable data store.\n>>\n>> What if we stored the refs as a tree object in the object database,\n>> referenced by a single (loose) ref?\n>\n> What is the cost of updating a single branch with that scheme?\n>\n> Doesn't it end up recording roughly the same amount of information\n> as updating a single packed-refs file that is flat, but with the\n> need to open a few tree objects (top-level, refs/, and refs/heads/),\n> writing out a blob that stores the object name at the tip, computing\n> the updated trees (refs/heads/, refs/ and top-level), and then\n> finally doing the compare-and-swap of that single loose ref?\n\nYes, except that when you update packed-refs, you have to write out\nthe _entire_ file, whereas with this scheme you only have to write out\nthe part of the refs hierarchy you actually touched (e.g. rewriting\nrefs/heads/foo would not have to write out anything inside\nrefs/tags/*). If you have small number of branches, and a huge number\nof tags, this scheme might end up being cheaper than writing the\nentire packed-refs. But in general, it's probably much more expensive\nto go via the odb.\n\n> You may guarantee atomicity but it is the same granularity of\n> atomicity as a single packed-refs file.\n\nYes, as I argued elsewhere in this thread: It seems that _any_\nfilesystem-based solution must resort to having all updates depend on\na single file in order to guarantee atomicity.\n\n> When you are updating a\n> branch while somebody else is updating a tag, of course you do not\n> have to look at refs/tags/ in your operation and you can write out\n> your final packed-refs equivalent tree to the object database\n> without racing with the other process, but the top-level you come up\n> with and the top-level the other process comes up with (which has\n> an up-to-date refs/tags/ part, but has a stale refs/heads/ part from\n> your point of view) have to race to update that single loose ref,\n> and one of you have to back out.\n\nTrue.\n\n> That \"backing out\" can be made more intelligently than just dying\n> with \"compare and swap failed--please retry\" message, e.g. you at\n> that point notice what you started with, what the other party did\n> while you were working on (i.e. updating refs/tags/), and three-way\n> merge the refs tree, and in cases where \"all refs recorded as loose\n> refs\" scheme wouldn't have resulted in problematic conflict, such a\n> three-way merge would resolve trivially (you updated refs/heads/ and\n> the update by the other process to refs/tags/ would not conflict\n> with what you did).  But the same three-way merge scheme can be\n> employed with the current flat single packed-refs scheme, can't it?\n\nYes. (albeit without reusing the machinery we already have for doing\nthree-way merges)\n\n> Even worse, what is the cost of looking up the value of a single\n> branch?  You would need to open a few tree objects and the leaf blob\n> that records the object name the ref points at, wouldn't you?\n\nYes. Probably a showstopper, although single branch/ref lookup might\nnot be so common on server side, as it is on the user side.\n\n> Right now, such a look-up is either opening a single small file and\n> reading the first 41 bytes off of it, and falling back (when the ref\n> in question is packed) to read a single packed-refs file and finding\n> the ref you want from it.\n>\n> So...\n\nYep...\n\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"217985","messageId":"CALKQrgfJht_rCJ98vBZ3Xo-Q4WLfXxo_rRc10sgWEXK7HNQXBg@mail.gmail.com","threadId":"33874","inReplyTo":"20130520165942.GB27788@sigill.intra.peff.net","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Johan Herland","fromEmail":"johan@herland.net","sentAt":"2013-05-20T17:08:27Z","receivedAt":"2013-05-20T17:08:27Z","isPatch":true,"sender":{"key":"johan@herland.net","avatar":"https://avatars.githubusercontent.com/u/547031?v=4"},"body":"On Mon, May 20, 2013 at 6:59 PM, Jeff King <peff@peff.net> wrote:\n> On Mon, May 20, 2013 at 09:37:30AM -0700, Junio C Hamano wrote:\n>> Johan Herland <johan@herland.net> writes:\n>>\n>> > For server-class installations we need ref storage that can be read\n>> > (and updated?) atomically, and the current system of loose + packed\n>> > files won't work since reading (and updating) more than a single file\n>> > is not an atomic operation. Trivially, one could resolve this by\n>> > dropping loose refs, and always using a single packed-refs file, but\n>> > that would make it prohibitively expensive to update refs (the entire\n>> > packed-refs file must be rewritten for every update).\n>> >\n>> > Now, observe that we don't have these race conditions in the object\n>> > database, because it is an add-only immutable data store.\n>> >\n>> > What if we stored the refs as a tree object in the object database,\n>> > referenced by a single (loose) ref?\n>>\n>> What is the cost of updating a single branch with that scheme?\n>\n> Yeah, I had the same thoughts as you here; I don't think this is really\n> much better than updating a single packed-refs file. You may only\n> have to touch log(N) of the entries to update the trees along the path\n> to your ref (assuming you have a bushy refs/ tree; in practice, of\n> course, you have a lot of entries in refs/heads/, so you do not quite\n> get log behavior). So algorithmically it may be slightly better, but you\n> pay a much higher constant, in that you are creating many tree objects\n> along the path (and reading them on lookup).\n\nTrue.\n\n> But more importantly, it introduces contention between two unrelated\n> refs that are being updated. Even if we reconcile the differences\n> automatically (e.g., with a \"merge-and-retry\" strategy), that is going\n> to be a serious performance regression for a busy repository, as we\n> repeatedly try to reconcile the serialized updates to the refs/ root\n> tree.\n>\n> Any transactional solution needs to have the equivalent of ref-level\n> locking (i.e., row-level locking in a relational setting). It is OK for\n> two simultaneous updates to different rows to happen in random order; we\n> don't care about that level of atomicity. The important thing is that\n> the _readers_ see transactions in consistent order; if we know that\n> update B started after update A finished, then we must never see update\n> A without update B reflected. And I think that is more or less a solved\n> problem in the database world.\n>\n> That is what prevents:\n>\n>   git update-ref A B\n>   git update-ref -d B\n>\n> from creating a view where the reader sees neither A nor B (which is\n> what can happen with the current filesystem view).\n\nAll true. Just a last spasm from the dying notion that we could solve\nthis in the filesystem, without using \"proper\" database...\n\n...Johan\n\n-- \nJohan Herland, <johan@herland.net>\nwww.herland.net\n"},{"id":"217990","messageId":"7vy5b9v896.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"20130520165942.GB27788@sigill.intra.peff.net","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-20T18:03:33Z","receivedAt":"2013-05-20T18:03:33Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Jeff King <peff@peff.net> writes:\n\n> But more importantly, it introduces contention between two unrelated\n> refs that are being updated. Even if we reconcile the differences\n> automatically (e.g., with a \"merge-and-retry\" strategy), that is going\n> to be a serious performance regression for a busy repository, as we\n> repeatedly try to reconcile the serialized updates to the refs/ root\n> tree.\n\nI think we are on the same page.\n\n> Any transactional solution needs to have the equivalent of ref-level\n> locking (i.e., row-level locking in a relational setting).\n\nNot necessarily if we can exploit assumptions such as deletion is\nfar rare compared to update and creation which in turn are far rare\ncompared to lookup.  I've been wondering if we can find a cheap\nreader-writer lock mechanism, use a single instance of it to govern\nthe whole repository, and have everybody but ref deleters and \"git\npack-ref\" take the read side of the lock.\n\nThen only while ref deletion or ref packing is going on, everybody\nneed to stall, but otherwise the most common \"read or update\nrecently touched refs (aka loose refs)\" will be taking the reader\nside of that cheap read-write lock and reading a single loose ref\nfile.\n\nPerhaps such a \"cheap on reader side\" reader-write lock is hard to\ncome by?\n"},{"id":"218004","messageId":"519A96D5.2070608@alum.mit.edu","threadId":"33874","inReplyTo":"20130520164458.GA27788@sigill.intra.peff.net","subject":"Re: [RFC 16/17] object_array_entry: copy name before storing in name field","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-20T21:34:13Z","receivedAt":"2013-05-20T21:34:13Z","isPatch":false,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/20/2013 06:44 PM, Jeff King wrote:\n> On Mon, May 20, 2013 at 04:42:38PM +0200, Michael Haggerty wrote:\n> \n>>>> * Many callers store the empty string (\"\") as the name; for example,\n>>>>   most of the entries created during a run of rev-list have \"\" as\n>>>>   their name.  This means that lots of needless copies of \"\" are being\n>>>>   made.  I think that the best solution to this problem would be to\n>>>>   store NULL rather than \"\" for such entries, but I haven't figured\n>>>>   out all of the places where the name is used.\n>>>\n>>> Use strbufs?\n>>>\n>>> No allocation (except for the strbuf object itself) is needed for\n>>> empty strings, and string ownership and be transferred to and from it\n>>> to prevent extra copies.\n>>\n>> That would cost two extra size_t per object_array_entry.  I have the\n>> feeling that this structure is used often enough that the extra overhead\n>> would be a disadvantage, but I'm not sure.\n>>\n>> The obvious alternative would be to teach users to deal with NULL and\n>> either add another constructor alternative that transfers string\n>> ownership or *always* transfer string ownership and change the callers\n>> to call xstrdup() if they don't already own the name string.  I think I\n>> will try that approach first.\n> \n> You could use the same trick that strbuf does: instead of NULL, point to\n> a well-known empty string literal. Readers do not have to care about\n> this optimization at all; only writers need to recognize the well-known\n> pointer value. And since we do not update in place but only eventually\n> free, it really is just that anyone calling free() would do \"if (name !=\n> well_known_empty_string)\".\n\nYes, that sounds like the best solution.  Ultimately there is only one\nwriter, add_object_array_with_mode(), and it can do\n\n    if (!name)\n        entry->name = NULL;\n    else if (!*name)\n        entry->name = well_known_empty_string;\n    else\n        entry->name = xstrdup(name);\n\nThis should be a lot less intrusive than what I was trying: to change\ncallers who wrote name=\"\" to write name=NULL instead.  But it is a\nnightmare to find all of the code that reads name and decide whether\nthey need to do\n\n    entry->name ? entry->name : \"\"\n\nbecause that in turn depends on whether the code that wrote into the\nsame object_array always/never/sometimes wrote strings vs. NULL to the\nname field.  Blech, encapsulation is tough in C.\n\nWhile I was chasing down callers, I came across other gems like\n\nbuiltin/checkout.c:\n\tadd_pending_object(&revs, object, sha1_to_hex(object->sha1));\n\nrevision.c:\n\tadd_pending_object(revs, object, sha1_to_hex(object->sha1));\n\nsubmodule.c:\n\tadd_pending_object(rev, &list->item->object,\n\t\tsha1_to_hex(list->item->object.sha1));\n\nso apparently I wasn't the only one befuddled by the lifetime and\nownership of the name field of object_array_entry.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218063","messageId":"7v8v38p7jx.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"1368995232-11042-5-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 04/17] builtin_diff_tree(): make it obvious that function wants two entries","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T17:27:30Z","receivedAt":"2013-05-21T17:27:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> Instead of accepting an array and using exactly two elements from the\n> array, take two single (struct object_array_entry *) arguments.\n>\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n> ---\n>  builtin/diff.c | 18 +++++++++---------\n>  1 file changed, 9 insertions(+), 9 deletions(-)\n>\n> diff --git a/builtin/diff.c b/builtin/diff.c\n> index 8c2af6c..ba68c6c 100644\n> --- a/builtin/diff.c\n> +++ b/builtin/diff.c\n> @@ -153,7 +153,8 @@ static int builtin_diff_index(struct rev_info *revs,\n>  \n>  static int builtin_diff_tree(struct rev_info *revs,\n>  \t\t\t     int argc, const char **argv,\n> -\t\t\t     struct object_array_entry *ent)\n> +\t\t\t     struct object_array_entry *ent0,\n> +\t\t\t     struct object_array_entry *ent1)\n>  {\n>  \tconst unsigned char *(sha1[2]);\n>  \tint swap = 0;\n> @@ -161,13 +162,13 @@ static int builtin_diff_tree(struct rev_info *revs,\n>  \tif (argc > 1)\n>  \t\tusage(builtin_diff_usage);\n>  \n> -\t/* We saw two trees, ent[0] and ent[1].\n> -\t * if ent[1] is uninteresting, they are swapped\n> +\t/* We saw two trees, ent0 and ent1.\n> +\t * if ent1 is uninteresting, they are swapped\n>  \t */\n\n\"While you are touching this comment\" is a perfect time to fix the\nexisting style violation.\n\nOther than that, looks good to me.\n\n> -\tif (ent[1].item->flags & UNINTERESTING)\n> +\tif (ent1->item->flags & UNINTERESTING)\n>  \t\tswap = 1;\n> -\tsha1[swap] = ent[0].item->sha1;\n> -\tsha1[1-swap] = ent[1].item->sha1;\n> +\tsha1[swap] = ent0->item->sha1;\n> +\tsha1[1-swap] = ent1->item->sha1;\n>  \tdiff_tree_sha1(sha1[0], sha1[1], \"\", &revs->diffopt);\n>  \tlog_tree_diff_flush(revs);\n>  \treturn 0;\n> @@ -403,7 +404,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  \telse if (ents == 1)\n>  \t\tresult = builtin_diff_index(&rev, argc, argv);\n>  \telse if (ents == 2)\n> -\t\tresult = builtin_diff_tree(&rev, argc, argv, ent);\n> +\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[1]);\n>  \telse if (ent[0].item->flags & UNINTERESTING) {\n>  \t\t/*\n>  \t\t * diff A...B where there is at least one merge base\n> @@ -412,8 +413,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  \t\t * between the base and B.  Note that we pick one\n>  \t\t * merge base at random if there are more than one.\n>  \t\t */\n> -\t\tent[1] = ent[ents-1];\n> -\t\tresult = builtin_diff_tree(&rev, argc, argv, ent);\n> +\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[ents-1]);\n>  \t} else\n>  \t\tresult = builtin_diff_combined(&rev, argc, argv,\n>  \t\t\t\t\t       ent, ents);\n"},{"id":"218064","messageId":"7v4ndwp7ed.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"1368995232-11042-6-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 05/17] cmd_diff(): use an object_array for holding trees","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T17:30:50Z","receivedAt":"2013-05-21T17:30:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> Change cmd_diff() to use a (struct object_array) for holding the trees\n> that it accumulates, rather than rolling its own equivalent.\n>\n\nA significant detail missing here is that this lifts the hardcoded\n100 tree limit in combined diff but that does not matter in\npractice, I would suppose ;-).\n\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n> ---\n>  builtin/diff.c | 37 ++++++++++++++++++-------------------\n>  1 file changed, 18 insertions(+), 19 deletions(-)\n>\n> diff --git a/builtin/diff.c b/builtin/diff.c\n> index ba68c6c..72d99c0 100644\n> --- a/builtin/diff.c\n> +++ b/builtin/diff.c\n> @@ -252,8 +252,8 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  {\n>  \tint i;\n>  \tstruct rev_info rev;\n> -\tstruct object_array_entry ent[100];\n> -\tint ents = 0, blobs = 0, paths = 0;\n> +\tstruct object_array ent = OBJECT_ARRAY_INIT;\n> +\tint blobs = 0, paths = 0;\n>  \tconst char *path = NULL;\n>  \tstruct blobinfo blob[2];\n>  \tint nongit;\n> @@ -350,13 +350,8 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  \t\tif (obj->type == OBJ_COMMIT)\n>  \t\t\tobj = &((struct commit *)obj)->tree->object;\n>  \t\tif (obj->type == OBJ_TREE) {\n> -\t\t\tif (ARRAY_SIZE(ent) <= ents)\n> -\t\t\t\tdie(_(\"more than %d trees given: '%s'\"),\n> -\t\t\t\t    (int) ARRAY_SIZE(ent), name);\n>  \t\t\tobj->flags |= flags;\n> -\t\t\tent[ents].item = obj;\n> -\t\t\tent[ents].name = name;\n> -\t\t\tents++;\n> +\t\t\tadd_object_array(obj, name, &ent);\n>  \t\t\tcontinue;\n>  \t\t}\n>  \t\tif (obj->type == OBJ_BLOB) {\n> @@ -380,7 +375,7 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  \t/*\n>  \t * Now, do the arguments look reasonable?\n>  \t */\n> -\tif (!ents) {\n> +\tif (!ent.nr) {\n>  \t\tswitch (blobs) {\n>  \t\tcase 0:\n>  \t\t\tresult = builtin_diff_files(&rev, argc, argv);\n> @@ -401,22 +396,26 @@ int cmd_diff(int argc, const char **argv, const char *prefix)\n>  \t}\n>  \telse if (blobs)\n>  \t\tusage(builtin_diff_usage);\n> -\telse if (ents == 1)\n> +\telse if (ent.nr == 1)\n>  \t\tresult = builtin_diff_index(&rev, argc, argv);\n> -\telse if (ents == 2)\n> -\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[1]);\n> -\telse if (ent[0].item->flags & UNINTERESTING) {\n> +\telse if (ent.nr == 2)\n> +\t\tresult = builtin_diff_tree(&rev, argc, argv,\n> +\t\t\t\t\t   &ent.objects[0], &ent.objects[1]);\n> +\telse if (ent.objects[0].item->flags & UNINTERESTING) {\n>  \t\t/*\n>  \t\t * diff A...B where there is at least one merge base\n> -\t\t * between A and B.  We have ent[0] == merge-base,\n> -\t\t * ent[ents-2] == A, and ent[ents-1] == B.  Show diff\n> -\t\t * between the base and B.  Note that we pick one\n> -\t\t * merge base at random if there are more than one.\n> +\t\t * between A and B.  We have ent.objects[0] ==\n> +\t\t * merge-base, ent.objects[ents-2] == A, and\n> +\t\t * ent.objects[ents-1] == B.  Show diff between the\n> +\t\t * base and B.  Note that we pick one merge base at\n> +\t\t * random if there are more than one.\n>  \t\t */\n> -\t\tresult = builtin_diff_tree(&rev, argc, argv, &ent[0], &ent[ents-1]);\n> +\t\tresult = builtin_diff_tree(&rev, argc, argv,\n> +\t\t\t\t\t   &ent.objects[0],\n> +\t\t\t\t\t   &ent.objects[ent.nr-1]);\n>  \t} else\n>  \t\tresult = builtin_diff_combined(&rev, argc, argv,\n> -\t\t\t\t\t       ent, ents);\n> +\t\t\t\t\t       ent.objects, ent.nr);\n>  \tresult = diff_result_code(&rev.diffopt, result);\n>  \tif (1 < rev.diffopt.skip_stat_unmatch)\n>  \t\trefresh_index_quietly();\n"},{"id":"218065","messageId":"7vzjvonsna.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"1368995232-11042-9-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 08/17] revision: split some overly-long lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T17:34:49Z","receivedAt":"2013-05-21T17:34:49Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n> ---\n>  revision.c | 20 ++++++++++++++------\n>  revision.h | 32 +++++++++++++++++++++-----------\n>  2 files changed, 35 insertions(+), 17 deletions(-)\n\nLooks obviously good for *.c file, but I am on the fence for *.h\none, as the reason we kept these long single lines in *.h files was\nto help those who want to grep in *.h files to let them view the\nfull function signature.  It probably is OK to tell them to use\n\"git grep -A$n\" instead, though.\n\n> diff --git a/revision.c b/revision.c\n> index 25e424c..8ac88d6 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -70,7 +70,8 @@ static int show_path_truncated(FILE *out, const struct name_path *path)\n>  \treturn ours || emitted;\n>  }\n>  \n> -void show_object_with_name(FILE *out, struct object *obj, const struct name_path *path, const char *component)\n> +void show_object_with_name(FILE *out, struct object *obj,\n> +\t\t\t   const struct name_path *path, const char *component)\n>  {\n>  \tstruct name_path leaf;\n>  \tleaf.up = (struct name_path *)path;\n> @@ -186,7 +187,9 @@ void mark_parents_uninteresting(struct commit *commit)\n>  \t}\n>  }\n>  \n> -static void add_pending_object_with_mode(struct rev_info *revs, struct object *obj, const char *name, unsigned mode)\n> +static void add_pending_object_with_mode(struct rev_info *revs,\n> +\t\t\t\t\t struct object *obj,\n> +\t\t\t\t\t const char *name, unsigned mode)\n>  {\n>  \tif (!obj)\n>  \t\treturn;\n> @@ -209,7 +212,8 @@ static void add_pending_object_with_mode(struct rev_info *revs, struct object *o\n>  \tadd_object_array_with_mode(obj, name, &revs->pending, mode);\n>  }\n>  \n> -void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)\n> +void add_pending_object(struct rev_info *revs,\n> +\t\t\tstruct object *obj, const char *name)\n>  {\n>  \tadd_pending_object_with_mode(revs, obj, name, S_IFINVALID);\n>  }\n> @@ -226,7 +230,9 @@ void add_head_to_pending(struct rev_info *revs)\n>  \tadd_pending_object(revs, obj, \"HEAD\");\n>  }\n>  \n> -static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)\n> +static struct object *get_reference(struct rev_info *revs, const char *name,\n> +\t\t\t\t    const unsigned char *sha1,\n> +\t\t\t\t    unsigned int flags)\n>  {\n>  \tstruct object *object;\n>  \n> @@ -247,7 +253,8 @@ void add_pending_sha1(struct rev_info *revs, const char *name,\n>  \tadd_pending_object(revs, object, name);\n>  }\n>  \n> -static struct commit *handle_commit(struct rev_info *revs, struct object *object, const char *name)\n> +static struct commit *handle_commit(struct rev_info *revs,\n> +\t\t\t\t    struct object *object, const char *name)\n>  {\n>  \tunsigned long flags = object->flags;\n>  \n> @@ -368,7 +375,8 @@ static void file_change(struct diff_options *options,\n>  \tDIFF_OPT_SET(options, HAS_CHANGES);\n>  }\n>  \n> -static int rev_compare_tree(struct rev_info *revs, struct commit *parent, struct commit *commit)\n> +static int rev_compare_tree(struct rev_info *revs,\n> +\t\t\t    struct commit *parent, struct commit *commit)\n>  {\n>  \tstruct tree *t1 = parent->tree;\n>  \tstruct tree *t2 = commit->tree;\n> diff --git a/revision.h b/revision.h\n> index 01bd2b7..9628465 100644\n> --- a/revision.h\n> +++ b/revision.h\n> @@ -195,19 +195,23 @@ struct setup_revision_opt {\n>  };\n>  \n>  extern void init_revisions(struct rev_info *revs, const char *prefix);\n> -extern int setup_revisions(int argc, const char **argv, struct rev_info *revs, struct setup_revision_opt *);\n> +extern int setup_revisions(int argc, const char **argv, struct rev_info *revs,\n> +\t\t\t   struct setup_revision_opt *);\n>  extern void parse_revision_opt(struct rev_info *revs, struct parse_opt_ctx_t *ctx,\n> -\t\t\t\t const struct option *options,\n> -\t\t\t\t const char * const usagestr[]);\n> +\t\t\t       const struct option *options,\n> +\t\t\t       const char * const usagestr[]);\n>  #define REVARG_CANNOT_BE_FILENAME 01\n>  #define REVARG_COMMITTISH 02\n> -extern int handle_revision_arg(const char *arg, struct rev_info *revs, int flags, unsigned revarg_opt);\n> +extern int handle_revision_arg(const char *arg, struct rev_info *revs,\n> +\t\t\t       int flags, unsigned revarg_opt);\n>  \n>  extern void reset_revision_walk(void);\n>  extern int prepare_revision_walk(struct rev_info *revs);\n>  extern struct commit *get_revision(struct rev_info *revs);\n> -extern char *get_revision_mark(const struct rev_info *revs, const struct commit *commit);\n> -extern void put_revision_mark(const struct rev_info *revs, const struct commit *commit);\n> +extern char *get_revision_mark(const struct rev_info *revs,\n> +\t\t\t       const struct commit *commit);\n> +extern void put_revision_mark(const struct rev_info *revs,\n> +\t\t\t      const struct commit *commit);\n>  \n>  extern void mark_parents_uninteresting(struct commit *commit);\n>  extern void mark_tree_uninteresting(struct tree *tree);\n> @@ -220,15 +224,19 @@ struct name_path {\n>  \n>  char *path_name(const struct name_path *path, const char *name);\n>  \n> -extern void show_object_with_name(FILE *, struct object *, const struct name_path *, const char *);\n> +extern void show_object_with_name(FILE *, struct object *,\n> +\t\t\t\t  const struct name_path *, const char *);\n>  \n>  extern void add_object(struct object *obj,\n>  \t\t       struct object_array *p,\n>  \t\t       struct name_path *path,\n>  \t\t       const char *name);\n>  \n> -extern void add_pending_object(struct rev_info *revs, struct object *obj, const char *name);\n> -extern void add_pending_sha1(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags);\n> +extern void add_pending_object(struct rev_info *revs,\n> +\t\t\t       struct object *obj, const char *name);\n> +extern void add_pending_sha1(struct rev_info *revs,\n> +\t\t\t     const char *name, const unsigned char *sha1,\n> +\t\t\t     unsigned int flags);\n>  \n>  extern void add_head_to_pending(struct rev_info *);\n>  \n> @@ -238,7 +246,9 @@ enum commit_action {\n>  \tcommit_error\n>  };\n>  \n> -extern enum commit_action get_commit_action(struct rev_info *revs, struct commit *commit);\n> -extern enum commit_action simplify_commit(struct rev_info *revs, struct commit *commit);\n> +extern enum commit_action get_commit_action(struct rev_info *revs,\n> +\t\t\t\t\t    struct commit *commit);\n> +extern enum commit_action simplify_commit(struct rev_info *revs,\n> +\t\t\t\t\t  struct commit *commit);\n>  \n>  #endif\n"},{"id":"218066","messageId":"7vsj1gnsgn.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"1368995232-11042-11-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 10/17] get_revision_internal(): make check less mysterious","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T17:38:48Z","receivedAt":"2013-05-21T17:38:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> The condition under which gc_boundary() is called was previously\n>\n>     if (alloc <= nr)\n>\n> .  But by construction, nr can never exceed alloc, so the check looks\n> unnecessarily mysterious.  In fact, the purpose of the check is to try\n> to avoid a realloc() call by shrinking the array if possible if it is\n> at its allocation limit when a new element is about to be added.  So\n> change the check to\n>\n>     if (nr == alloc)\n>\n> and add a comment to explain what's going on.\n>\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n> ---\n> Please check that I have properly described the purpose of this check.\n>\n> The way the code is written, it looks like a bad pattern of growth and\n> shrinkage of the array (namely, just under the resize limit) could\n> cause gc_boundary() to be called over and over again with (most of)\n> the same data.  I hope that the author had some reason to believe that\n> such a pattern is unlikely.\n\nThat is about comparing with \"alloc\", not having high and low\nwatermarks, right?\n\nI do not see \"alloc <= nr\" is mysterious at all; it is merely being\ndefensive.\n\n>\n>  revision.c | 4 +++-\n>  1 file changed, 3 insertions(+), 1 deletion(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 2e0992b..19c59f4 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2573,8 +2573,10 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n>  \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n>  \t\t\tcontinue;\n>  \t\tp->flags |= CHILD_SHOWN;\n> -\t\tif (revs->boundary_commits.alloc <= revs->boundary_commits.nr)\n> +\t\tif (revs->boundary_commits.nr == revs->boundary_commits.alloc) {\n> +\t\t\t/* Try to make space and thereby avoid a realloc(): */\n>  \t\t\tgc_boundary(&revs->boundary_commits);\n> +\t\t}\n>  \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n>  \t}\n"},{"id":"218067","messageId":"7vobc4nrz8.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"1368995232-11042-10-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 09/17] gc_boundary(): move the check \"alloc <= nr\" to caller","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T17:49:15Z","receivedAt":"2013-05-21T17:49:15Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> There is no logical reason for this test to be here.  At the caller we\n> might be able to figure out its meaning.\n>\n> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n> ---\n\nI do not think this change is justified, *unless* the caller later\nin the series gains a better heuristics than what can be done with\ninformation in the object_array (namely, alloc and nr) to decide\nwhen to trigger gc.\n\nAnd I was hoping to see such a cleverness added to the caller, but I\ndo not think I saw any.\n\nI would have to say gc_boundary() knows better when it needs to gc\nwith the code at this point in the series, and that is true also in\nthe final code after all the patches in this series.\n\nIf we keep the \"when to gc\" logic inside \"gc\", in 11/17 this caller\ncan no longer call directly to object_array_filter().  It should\ncall gc_boundary(), but I see it as a merit, not a downside.  The\n\"gc function can later be taught the high/low watermark logic you\nalluded to in 10/17, and the growth/shrinkage characteristic you\nwould take advantage of while doing \"gc\" is specific to this\ncodepath.  And the logic still does not have to have access to\nanything only the caller has access to; \"gc\" can work on what can be\nread from the object_array->{alloc,nr} that is given to it.\n\n  revision.c | 27 ++++++++++++---------------\n\n>  1 file changed, 12 insertions(+), 15 deletions(-)\n>\n> diff --git a/revision.c b/revision.c\n> index 8ac88d6..2e0992b 100644\n> --- a/revision.c\n> +++ b/revision.c\n> @@ -2437,23 +2437,19 @@ static struct commit *get_revision_1(struct rev_info *revs)\n>  \n>  static void gc_boundary(struct object_array *array)\n>  {\n> -\tunsigned nr = array->nr;\n> -\tunsigned alloc = array->alloc;\n> +\tunsigned nr = array->nr, i, j;\n>  \tstruct object_array_entry *objects = array->objects;\n>  \n> -\tif (alloc <= nr) {\n> -\t\tunsigned i, j;\n> -\t\tfor (i = j = 0; i < nr; i++) {\n> -\t\t\tif (objects[i].item->flags & SHOWN)\n> -\t\t\t\tcontinue;\n> -\t\t\tif (i != j)\n> -\t\t\t\tobjects[j] = objects[i];\n> -\t\t\tj++;\n> -\t\t}\n> -\t\tfor (i = j; i < nr; i++)\n> -\t\t\tobjects[i].item = NULL;\n> -\t\tarray->nr = j;\n> +\tfor (i = j = 0; i < nr; i++) {\n> +\t\tif (objects[i].item->flags & SHOWN)\n> +\t\t\tcontinue;\n> +\t\tif (i != j)\n> +\t\t\tobjects[j] = objects[i];\n> +\t\tj++;\n>  \t}\n> +\tfor (i = j; i < nr; i++)\n> +\t\tobjects[i].item = NULL;\n> +\tarray->nr = j;\n>  }\n>  \n>  static void create_boundary_commit_list(struct rev_info *revs)\n> @@ -2577,7 +2573,8 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n>  \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n>  \t\t\tcontinue;\n>  \t\tp->flags |= CHILD_SHOWN;\n> -\t\tgc_boundary(&revs->boundary_commits);\n> +\t\tif (revs->boundary_commits.alloc <= revs->boundary_commits.nr)\n> +\t\t\tgc_boundary(&revs->boundary_commits);\n>  \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n>  \t}\n"},{"id":"218081","messageId":"7v7gisnpnx.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"CALKQrgd3=5Rb5wbDGTV7PQfcingimYf08yEHcbfSCkjGDUU_Ng@mail.gmail.com","subject":"Re: [PATCH 00/17] Remove assumptions about refname lifetimes","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-21T18:39:14Z","receivedAt":"2013-05-21T18:39:14Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Johan Herland <johan@herland.net> writes:\n\n> On Mon, May 20, 2013 at 6:37 PM, Junio C Hamano <gitster@pobox.com> wrote:\n> ...\n>> That \"backing out\" can be made more intelligently than just dying\n>> with \"compare and swap failed--please retry\" message, e.g. you at\n>> that point notice what you started with, what the other party did\n>> while you were working on (i.e. updating refs/tags/), and three-way\n>> merge the refs tree, and in cases where \"all refs recorded as loose\n>> refs\" scheme wouldn't have resulted in problematic conflict, such a\n>> three-way merge would resolve trivially (you updated refs/heads/ and\n>> the update by the other process to refs/tags/ would not conflict\n>> with what you did).  But the same three-way merge scheme can be\n>> employed with the current flat single packed-refs scheme, can't it?\n>\n> Yes. (albeit without reusing the machinery we already have for doing\n> three-way merges)\n\nI do not think that is relevant, as you do *not* want to reuse the\nusual three-way xdiff merge machinery that leaves \"<=>\" markers for\nthis usage anyway.\n\nBut that is not the primary reason why I am beating this dead horse;\nit is the following.\n\nYour version of packed-refs file, and his version of packed-refs\nfile, and the original you started with, are all sorted in a known\norder.  You just look at lines from all and merge them line by line.\n\nI think that logic should become a new blob-level merge driver that\ncan be reused for normal in-working-tree objects that are sorted.\nFor that kind of \"sorted wordlist\" file, conflicts that may\nartificially arise only because two sides updated adjacent lines in\nthe list and you used the normal xdiff merge machinery is unwanted,\nand users would benefit by having such a specialized merge driver\noutside the context of merging two proposed list of refs.\n"},{"id":"218233","messageId":"519DB6E2.9010900@alum.mit.edu","threadId":"33874","inReplyTo":"7vzjvonsna.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 08/17] revision: split some overly-long lines","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T06:27:46Z","receivedAt":"2013-05-23T06:27:46Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2013 07:34 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n>> ---\n>>  revision.c | 20 ++++++++++++++------\n>>  revision.h | 32 +++++++++++++++++++++-----------\n>>  2 files changed, 35 insertions(+), 17 deletions(-)\n> \n> Looks obviously good for *.c file, but I am on the fence for *.h\n> one, as the reason we kept these long single lines in *.h files was\n> to help those who want to grep in *.h files to let them view the\n> full function signature.  It probably is OK to tell them to use\n> \"git grep -A$n\" instead, though.\n\nMy goal with this patch was not to set a new policy but rather just to\nmake the code conform a little better to the existing policy as\ndescribed in CodingGuidelines.  *If* it is preferred that header files\nlist all parameters on a single line, then by all means adjust the\nCodingGuidelines and I will just as happily make header files conform to\n*that* policy when I touch them :-)\n\n(That being said, my personal preference is to apply the 80-character\nlimit for header files too.)\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218234","messageId":"519DB985.5040103@alum.mit.edu","threadId":"33874","inReplyTo":"7vsj1gnsgn.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 10/17] get_revision_internal(): make check less mysterious","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T06:39:01Z","receivedAt":"2013-05-23T06:39:01Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2013 07:38 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> The condition under which gc_boundary() is called was previously\n>>\n>>     if (alloc <= nr)\n>>\n>> .  But by construction, nr can never exceed alloc, so the check looks\n>> unnecessarily mysterious.  In fact, the purpose of the check is to try\n>> to avoid a realloc() call by shrinking the array if possible if it is\n>> at its allocation limit when a new element is about to be added.  So\n>> change the check to\n>>\n>>     if (nr == alloc)\n>>\n>> and add a comment to explain what's going on.\n>>\n>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n>> ---\n>> Please check that I have properly described the purpose of this check.\n>>\n>> The way the code is written, it looks like a bad pattern of growth and\n>> shrinkage of the array (namely, just under the resize limit) could\n>> cause gc_boundary() to be called over and over again with (most of)\n>> the same data.  I hope that the author had some reason to believe that\n>> such a pattern is unlikely.\n> \n> That is about comparing with \"alloc\", not having high and low\n> watermarks, right?\n> \n> I do not see \"alloc <= nr\" is mysterious at all; it is merely being\n> defensive.\n\nIf nr would ever exceed alloc, then the code would be broken and would\nprobably have already performed an illegal memory access.  Pretending to\nsupport nr > alloc here is not defensive but misleading, because by that\ntime the ship is going down anyway.\n\nOn a more practical level, when I saw this code I thought to myself\n\"that's strange, I'd better look into it because it suggests that I\ndon't understand the meaning of nr and alloc\".  I think that the\nsuggested change will help prevent the next reader from repeating the\nsame pointless investigation.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218235","messageId":"519DC0B7.7080401@alum.mit.edu","threadId":"33874","inReplyTo":"7vobc4nrz8.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 09/17] gc_boundary(): move the check \"alloc <= nr\" to caller","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T07:09:43Z","receivedAt":"2013-05-23T07:09:43Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2013 07:49 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> There is no logical reason for this test to be here.  At the caller we\n>> might be able to figure out its meaning.\n>>\n>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n>> ---\n> \n> I do not think this change is justified, *unless* the caller later\n> in the series gains a better heuristics than what can be done with\n> information in the object_array (namely, alloc and nr) to decide\n> when to trigger gc.\n> \n> And I was hoping to see such a cleverness added to the caller, but I\n> do not think I saw any.\n\nCorrect.\n\n> I would have to say gc_boundary() knows better when it needs to gc\n> with the code at this point in the series, and that is true also in\n> the final code after all the patches in this series.\n> \n> If we keep the \"when to gc\" logic inside \"gc\", in 11/17 this caller\n> can no longer call directly to object_array_filter().  It should\n> call gc_boundary(), but I see it as a merit, not a downside.  The\n> \"gc function can later be taught the high/low watermark logic you\n> alluded to in 10/17, and the growth/shrinkage characteristic you\n> would take advantage of while doing \"gc\" is specific to this\n> codepath.  And the logic still does not have to have access to\n> anything only the caller has access to; \"gc\" can work on what can be\n> read from the object_array->{alloc,nr} that is given to it.\n\nI don't feel strongly about this patch and if you prefer to have it\ndropped I will do so.  But let me explain my reasoning:\n\n1. The function name gc_boundary() suggests that it will do a garbage\ncollection unconditionally.  In fact, it might or might not depending on\nthis test.  At the caller, this made it look like a gc was happening\neach time through the loop, which made me nervous about the performance.\n The new version makes it clear at the caller that the gc is only\nhappening occasionally.\n\n2. Even assuming that gc_boundary() were renamed to maybe_gc_boundary(),\nthe function has hopelessly little information on which to base its\ndecision whether or not to gc, and the choice of policy can only be\njustified based on some implicit knowledge about how the array is grown\nand shrunk.  But the growing/shrinking is done at the layer of the\ncaller, and therefore the choice of gc policy also belongs at the layer\nof the caller.\n\n3. As you point out, if the gc policy is ever to be made more\nintelligent, then gc_boundary() is unlikely to have enough information\nto implement the new policy (e.g., it would have no place to record\nlow/high water marks).  Separating concerns at the correct level would\nmake a change like that easier.\n\nAt the moment I am not interested in improving the gc policy of this\ncode.  The only reason that I am mucking about here is to change it to\nuse object_array_filter(), which is needed to centralize where\nobject_array_entries are created and destroyed so that the \"name\" memory\ncan be copied and freed consistently.  That can be done with or without\npatches 09 and 10.  Please let me know what you prefer.\n\nMichael\n\n>   revision.c | 27 ++++++++++++---------------\n> \n>>  1 file changed, 12 insertions(+), 15 deletions(-)\n>>\n>> diff --git a/revision.c b/revision.c\n>> index 8ac88d6..2e0992b 100644\n>> --- a/revision.c\n>> +++ b/revision.c\n>> @@ -2437,23 +2437,19 @@ static struct commit *get_revision_1(struct rev_info *revs)\n>>  \n>>  static void gc_boundary(struct object_array *array)\n>>  {\n>> -\tunsigned nr = array->nr;\n>> -\tunsigned alloc = array->alloc;\n>> +\tunsigned nr = array->nr, i, j;\n>>  \tstruct object_array_entry *objects = array->objects;\n>>  \n>> -\tif (alloc <= nr) {\n>> -\t\tunsigned i, j;\n>> -\t\tfor (i = j = 0; i < nr; i++) {\n>> -\t\t\tif (objects[i].item->flags & SHOWN)\n>> -\t\t\t\tcontinue;\n>> -\t\t\tif (i != j)\n>> -\t\t\t\tobjects[j] = objects[i];\n>> -\t\t\tj++;\n>> -\t\t}\n>> -\t\tfor (i = j; i < nr; i++)\n>> -\t\t\tobjects[i].item = NULL;\n>> -\t\tarray->nr = j;\n>> +\tfor (i = j = 0; i < nr; i++) {\n>> +\t\tif (objects[i].item->flags & SHOWN)\n>> +\t\t\tcontinue;\n>> +\t\tif (i != j)\n>> +\t\t\tobjects[j] = objects[i];\n>> +\t\tj++;\n>>  \t}\n>> +\tfor (i = j; i < nr; i++)\n>> +\t\tobjects[i].item = NULL;\n>> +\tarray->nr = j;\n>>  }\n>>  \n>>  static void create_boundary_commit_list(struct rev_info *revs)\n>> @@ -2577,7 +2573,8 @@ static struct commit *get_revision_internal(struct rev_info *revs)\n>>  \t\tif (p->flags & (CHILD_SHOWN | SHOWN))\n>>  \t\t\tcontinue;\n>>  \t\tp->flags |= CHILD_SHOWN;\n>> -\t\tgc_boundary(&revs->boundary_commits);\n>> +\t\tif (revs->boundary_commits.alloc <= revs->boundary_commits.nr)\n>> +\t\t\tgc_boundary(&revs->boundary_commits);\n>>  \t\tadd_object_array(p, NULL, &revs->boundary_commits);\n>>  \t}\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218236","messageId":"519DC2E4.7070102@alum.mit.edu","threadId":"33874","inReplyTo":"7v8v38p7jx.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 04/17] builtin_diff_tree(): make it obvious that function wants two entries","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T07:19:00Z","receivedAt":"2013-05-23T07:19:00Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2013 07:27 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> Instead of accepting an array and using exactly two elements from the\n>> array, take two single (struct object_array_entry *) arguments.\n>>\n>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n>> ---\n>>  builtin/diff.c | 18 +++++++++---------\n>>  1 file changed, 9 insertions(+), 9 deletions(-)\n>>\n>> diff --git a/builtin/diff.c b/builtin/diff.c\n>> index 8c2af6c..ba68c6c 100644\n>> --- a/builtin/diff.c\n>> +++ b/builtin/diff.c\n>> @@ -153,7 +153,8 @@ static int builtin_diff_index(struct rev_info *revs,\n>>  \n>>  static int builtin_diff_tree(struct rev_info *revs,\n>>  \t\t\t     int argc, const char **argv,\n>> -\t\t\t     struct object_array_entry *ent)\n>> +\t\t\t     struct object_array_entry *ent0,\n>> +\t\t\t     struct object_array_entry *ent1)\n>>  {\n>>  \tconst unsigned char *(sha1[2]);\n>>  \tint swap = 0;\n>> @@ -161,13 +162,13 @@ static int builtin_diff_tree(struct rev_info *revs,\n>>  \tif (argc > 1)\n>>  \t\tusage(builtin_diff_usage);\n>>  \n>> -\t/* We saw two trees, ent[0] and ent[1].\n>> -\t * if ent[1] is uninteresting, they are swapped\n>> +\t/* We saw two trees, ent0 and ent1.\n>> +\t * if ent1 is uninteresting, they are swapped\n>>  \t */\n> \n> \"While you are touching this comment\" is a perfect time to fix the\n> existing style violation.\n\nYes.  Will fix in next version.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218237","messageId":"519DC371.7090109@alum.mit.edu","threadId":"33874","inReplyTo":"7v4ndwp7ed.fsf@alter.siamese.dyndns.org","subject":"Re: [PATCH 05/17] cmd_diff(): use an object_array for holding trees","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2013-05-23T07:21:21Z","receivedAt":"2013-05-23T07:21:21Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"On 05/21/2013 07:30 PM, Junio C Hamano wrote:\n> Michael Haggerty <mhagger@alum.mit.edu> writes:\n> \n>> Change cmd_diff() to use a (struct object_array) for holding the trees\n>> that it accumulates, rather than rolling its own equivalent.\n>>\n> \n> A significant detail missing here is that this lifts the hardcoded\n> 100 tree limit in combined diff but that does not matter in\n> practice, I would suppose ;-).\n\nI'll note it anyway in v2 of the patch series.\n\nThanks for all of your comments.  I will send a re-roll after I hear\nback from you regarding patches 08, 09, and 10.\n\nMichael\n\n-- \nMichael Haggerty\nmhagger@alum.mit.edu\nhttp://softwareswirl.blogspot.com/\n"},{"id":"218285","messageId":"7vy5b5fwu7.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"519DB6E2.9010900@alum.mit.edu","subject":"Re: [PATCH 08/17] revision: split some overly-long lines","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-23T17:08:16Z","receivedAt":"2013-05-23T17:08:16Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> On 05/21/2013 07:34 PM, Junio C Hamano wrote:\n>> Michael Haggerty <mhagger@alum.mit.edu> writes:\n>> \n>>> Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n>>> ---\n>>>  revision.c | 20 ++++++++++++++------\n>>>  revision.h | 32 +++++++++++++++++++++-----------\n>>>  2 files changed, 35 insertions(+), 17 deletions(-)\n>> \n>> Looks obviously good for *.c file, but I am on the fence for *.h\n>> one, as the reason we kept these long single lines in *.h files was\n>> to help those who want to grep in *.h files to let them view the\n>> full function signature.  It probably is OK to tell them to use\n>> \"git grep -A$n\" instead, though.\n>\n> My goal with this patch was not to set a new policy but rather just to\n> make the code conform a little better to the existing policy as\n> described in CodingGuidelines.  *If* it is preferred that header files\n> list all parameters on a single line, then by all means adjust the\n> CodingGuidelines and I will just as happily make header files conform to\n> *that* policy when I touch them :-)\n>\n> (That being said, my personal preference is to apply the 80-character\n> limit for header files too.)\n\nYeah, that is why I said \"I am on the fence but it probably is OK to\nbreak\" the unwritten but guessable rule.\n"},{"id":"218291","messageId":"7vd2shfub9.fsf@alter.siamese.dyndns.org","threadId":"33874","inReplyTo":"519DC0B7.7080401@alum.mit.edu","subject":"Re: [PATCH 09/17] gc_boundary(): move the check \"alloc <= nr\" to caller","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2013-05-23T18:02:50Z","receivedAt":"2013-05-23T18:02:50Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> 1. The function name gc_boundary() suggests that it will do a garbage\n> collection unconditionally.  In fact, it might or might not depending on\n> this test.  At the caller, this made it look like a gc was happening\n> each time through the loop, which made me nervous about the performance.\n>  The new version makes it clear at the caller that the gc is only\n> happening occasionally.\n\nPerhaps.\n\n> 2. Even assuming that gc_boundary() were renamed to maybe_gc_boundary(),\n> the function has hopelessly little information on which to base its\n> decision whether or not to gc, and the choice of policy can only be\n> justified based on some implicit knowledge about how the array is grown\n> and shrunk.  But the growing/shrinking is done at the layer of the\n> caller, and therefore the choice of gc policy also belongs at the layer\n> of the caller.\n>\n> 3. As you point out, if the gc policy is ever to be made more\n> intelligent, then gc_boundary() is unlikely to have enough information\n> to implement the new policy (e.g., it would have no place to record\n> low/high water marks).  Separating concerns at the correct level would\n> make a change like that easier.\n\nThese two depend on how you look at the API hierarchy.  You seem to\nthink that the ideal end result is\n\n\tget_revision_internal()\n          have an open coded \"when to gc\" logic in this function\n          call object_array_filter()\n\nMy suggestion was based on a different view, which is:\n\n\tget_revision_internal()\n          call gc_boundary()\n\n        gc_boundary()\n          make decision on when and how to gc\n          if decided to do so\n            call object_array_fitler()\n\nYou can obviously rename gc_boundary() to auto_gc_boundary() if that\nmakes it easier to understand, but these two belong to the same\ncodepath that deals with the object array used specifically for\nkeeping track of boundary commits. I view \"who has what information\"\nas secondary---if the decision to gc is not the primary thing\nget_revision_internal() should be worrying about (and I do not think\nit is), it would be a better code structure to have a helper specific\nfor doing so, i.e. gc_boundary(), and delegate that part of job to it.\n\nObviously, the caller needs to supply sufficient information to that\nhelper if the helper needs more than what it currently gets by\nadding parameters to it, but that goes without saying.\n\n> At the moment I am not interested in improving the gc policy of this\n> code.\n\nI am not either; the only effect we get from removing gc_boudnary()\nand calling directly to object_array_filter() is to lose the above\nabstraction and make it easy to let get_revision_internal() become\nmore cluttered when somebody else later decides to improve the gc\npolicy, it seems.\n"}]}