{"thread":{"id":"29380","subject":"[PATCH 0/4] Remove a user of extra_refs in clone","startedAt":"2012-01-17T05:50:30Z","lastAt":"2012-01-17T06:51:31Z","messageCount":7,"participants":["mhagger@alum.mit.edu","Jeff King","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"182664","messageId":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","threadId":"29380","inReplyTo":null,"subject":"[PATCH 0/4] Remove a user of extra_refs in clone","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-01-17T05:50:30Z","receivedAt":"2012-01-17T05:50:30Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nWhen cloning, write_remote_refs() creates local packed refs from the\nrefs read from the remote repository. It does this by creating extra\nrefs for the references then calling pack_refs() to bake the extra\nrefs into the packed-refs file, then calling clear_extra_refs().\n\nThis is silly and relies on the kludgy extra_refs mechanism, which I\nwant to get rid of. Instead, add a function call add_packed_ref() to\nthe refs API, and use it to create packed refs (in the memory cache)\ndirectly. Then call pack_refs() as before to write the packed-refs\nfile.\n\nBecause the new add_packed_ref() function allows references (perhaps\nmany of them) to be added to an existing ref_array, it would be\ninefficient to re-sort the list after every addition. So instead,\nappend new entries to the end of the ref_array and note that the array\nis unsorted. Then, before the ref_array is used, check if it is\nunsorted and sort it if necessary.\n\nA side effect of this change is that the new packed references are\nleft in the in-memory packed reference cache after the return from\nwrite_remote_refs() (whereas previously, the refs were stored as\ntemporary extra refs that were purged before return from the\nfunction). I can't see any place in the following code where this\nwould make a difference, but there is quite a bit of code there so it\nis hard to audit. Confirmation that this is OK would be welcome.\n\nMichael Haggerty (4):\n pack_refs(): remove redundant check\n ref_array: keep track of whether references are sorted\n add_packed_ref(): new function in the refs API.\n write_remote_refs(): create packed (rather than extra) refs\n\n builtin/clone.c | 3 +--\n pack-refs.c | 3 +--\n refs.c | 39 ++++++++++++++++++++++++++++++++-------\n refs.h | 6 ++++++\n 4 files changed, 40 insertions(+), 11 deletions(-)\n\n-- \n1.7.8.3\n"},{"id":"182668","messageId":"1326779434-20106-2-git-send-email-mhagger@alum.mit.edu","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 1/4] pack_refs(): remove redundant check","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-01-17T05:50:31Z","receivedAt":"2012-01-17T05:50:31Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nhandle_one_ref() only adds refs to the cbdata.ref_to_prune list if\n(cbdata.flags & PACK_REFS_PRUNE) is set. So any references in this\nlist at the end of pack_refs() can be pruned unconditionally.\n\nSigned-off-by: Michael Haggerty \n---\nTrivial simplification, not essential to the rest of this patch\nseries.\n\n pack-refs.c | 3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/pack-refs.c b/pack-refs.c\nindex 23bbd00..f09a054 100644\n--- a/pack-refs.c\n+++ b/pack-refs.c\n@@ -143,7 +143,6 @@ int pack_refs(unsigned int flags)\n \tpacked.fd = -1;\n \tif (commit_lock_file(&packed) < 0)\n \t\tdie_errno(\"unable to overwrite old ref-pack file\");\n-\tif (cbdata.flags & PACK_REFS_PRUNE)\n-\t\tprune_refs(cbdata.ref_to_prune);\n+\tprune_refs(cbdata.ref_to_prune);\n \treturn 0;\n }\n-- \n1.7.8.3\n"},{"id":"182665","messageId":"1326779434-20106-3-git-send-email-mhagger@alum.mit.edu","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 2/4] ref_array: keep track of whether references are sorted","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-01-17T05:50:32Z","receivedAt":"2012-01-17T05:50:32Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nKeep track of how many entries in a ref_array are already sorted. In\nsort_ref_array(), only call qsort() if the dir contains unsorted\nentries (i.e., if references have been appended to the end of the list\nsince the last call to sort_ref_array()).\n\nSort ref_arrays only when needed, namely in search_ref_array() and in\ndo_for_each_ref(). However, never sort the extra_refs, because\nextra_refs can contain multiple entries with the same name.\n\nThis change is currently not useful, because entries are not added to\nref_arrays after they are created. But in a moment they will be...\n\nImplementation note: we could store a binary \"sorted\" value instead of\nan integer, but storing the number of sorted entries leaves the way\nopen for a couple of possible future optimizations:\n\n* In sort_ref_array(), sort *only* the unsorted entries, then merge\n them with the sorted entries. This should be faster if most of the\n entries are already sorted.\n\n* Teach search_ref_array() to do a binary search of any sorted\n entries, and if unsuccessful do a linear search of any unsorted\n entries. This would avoid the need to sort the list every time that\n search_ref_array() is called, and (given some intelligence about how\n often to sort) could significantly improve the speed in certain\n hypothetical usage patterns.\n\nSigned-off-by: Michael Haggerty \n---\n refs.c | 33 ++++++++++++++++++++++++++-------\n 1 files changed, 26 insertions(+), 7 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 6f436f1..268816f 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -17,6 +17,15 @@ struct ref_entry {\n \n struct ref_array {\n \tint nr, alloc;\n+\n+\t/*\n+\t * Entries with index 0 <= i < sorted are sorted by name. New\n+\t * entries are appended to the list unsorted, and are sorted\n+\t * only when required; thus we avoid the need to sort the list\n+\t * after the addition of every reference.\n+\t */\n+\tint sorted;\n+\n \tstruct ref_entry **refs;\n };\n \n@@ -105,12 +114,18 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2\n \t}\n }\n \n+/*\n+ * Sort the entries in array (if they are not already sorted).\n+ */\n static void sort_ref_array(struct ref_array *array)\n {\n \tint i, j;\n \n-\t/* Nothing to sort unless there are at least two entries */\n-\tif (array->nr < 2)\n+\t/*\n+\t * This check also prevents passing a zero-length array to qsort(),\n+\t * which is a problem on some platforms.\n+\t */\n+\tif (array->sorted == array->nr)\n \t\treturn;\n \n \tqsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);\n@@ -124,7 +139,7 @@ static void sort_ref_array(struct ref_array *array)\n \t\t}\n \t\tarray->refs[++i] = array->refs[j];\n \t}\n-\tarray->nr = i + 1;\n+\tarray->sorted = array->nr = i + 1;\n }\n \n static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)\n@@ -137,7 +152,7 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r\n \n \tif (!array->nr)\n \t\treturn NULL;\n-\n+\tsort_ref_array(array);\n \tlen = strlen(refname) + 1;\n \te = xmalloc(sizeof(struct ref_entry) + len);\n \tmemcpy(e->name, refname, len);\n@@ -168,6 +183,10 @@ static struct ref_cache {\n \n static struct ref_entry *current_ref;\n \n+/*\n+ * The extra_refs is never sorted, because it is allowed to contain entries\n+ * with duplicate names.\n+ */\n static struct ref_array extra_refs;\n \n static void clear_ref_array(struct ref_array *array)\n@@ -176,7 +195,7 @@ static void clear_ref_array(struct ref_array *array)\n \tfor (i = 0; i < array->nr; i++)\n \t\tfree(array->refs[i]);\n \tfree(array->refs);\n-\tarray->nr = array->alloc = 0;\n+\tarray->sorted = array->nr = array->alloc = 0;\n \tarray->refs = NULL;\n }\n \n@@ -268,7 +287,6 @@ static void read_packed_refs(FILE *f, struct ref_array *array)\n \t\t !get_sha1_hex(refline + 1, sha1))\n \t\t\thashcpy(last->peeled, sha1);\n \t}\n-\tsort_ref_array(array);\n }\n \n void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)\n@@ -404,7 +422,6 @@ static struct ref_array *get_loose_refs(struct ref_cache *refs)\n {\n \tif (!refs->did_loose) {\n \t\tget_ref_dir(refs, \"refs\", &refs->loose);\n-\t\tsort_ref_array(&refs->loose);\n \t\trefs->did_loose = 1;\n \t}\n \treturn &refs->loose;\n@@ -720,6 +737,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn\n \tfor (i = 0; i < extra->nr; i++)\n \t\tretval = do_one_ref(base, fn, trim, flags, cb_data, extra->refs[i]);\n \n+\tsort_ref_array(packed);\n+\tsort_ref_array(loose);\n \twhile (p < packed->nr && l < loose->nr) {\n \t\tstruct ref_entry *entry;\n \t\tint cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name);\n-- \n1.7.8.3\n"},{"id":"182666","messageId":"1326779434-20106-4-git-send-email-mhagger@alum.mit.edu","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 3/4] add_packed_ref(): new function in the refs API.","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-01-17T05:50:33Z","receivedAt":"2012-01-17T05:50:33Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nAdd a new function add_packed_ref() that adds a reference directly to\nthe in-memory packed reference cache. This will be useful for\ncreating local references while cloning.\n\nSigned-off-by: Michael Haggerty \n---\nThis new function call only stores the new reference to the in-memory\ncache. The user has to remember to call pack_refs() to actually write\nthe new reference(s) to the packed-refs file. (I don't think it is\npractical to make the write happen automatically.)\n\n refs.c | 6 ++++++\n refs.h | 6 ++++++\n 2 files changed, 12 insertions(+), 0 deletions(-)\n\ndiff --git a/refs.c b/refs.c\nindex 268816f..14f764d 100644\n--- a/refs.c\n+++ b/refs.c\n@@ -319,6 +319,12 @@ static struct ref_array *get_packed_refs(struct ref_cache *refs)\n \treturn &refs->packed;\n }\n \n+void add_packed_ref(const char *refname, const unsigned char *sha1)\n+{\n+\tadd_ref(get_packed_refs(get_ref_cache(NULL)),\n+\t\t\tcreate_ref_entry(refname, sha1, REF_ISPACKED, 1));\n+}\n+\n static void get_ref_dir(struct ref_cache *refs, const char *base,\n \t\t\tstruct ref_array *array)\n {\ndiff --git a/refs.h b/refs.h\nindex d498291..00ba1e2 100644\n--- a/refs.h\n+++ b/refs.h\n@@ -51,6 +51,12 @@ extern int for_each_rawref(each_ref_fn, void *);\n extern void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname);\n \n /*\n+ * Add a reference to the in-memory packed reference cache. To actually\n+ * write the reference to the packed-refs file, call pack_refs().\n+ */\n+extern void add_packed_ref(const char *refname, const unsigned char *sha1);\n+\n+/*\n * Extra refs will be listed by for_each_ref() before any actual refs\n * for the duration of this process or until clear_extra_refs() is\n * called. Only extra refs added before for_each_ref() is called will\n-- \n1.7.8.3\n"},{"id":"182667","messageId":"1326779434-20106-5-git-send-email-mhagger@alum.mit.edu","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"[PATCH 4/4] write_remote_refs(): create packed (rather than extra) refs","fromName":"","fromEmail":"mhagger@alum.mit.edu","sentAt":"2012-01-17T05:50:34Z","receivedAt":"2012-01-17T05:50:34Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"From: Michael Haggerty \n\nwrite_remote_refs() creates new packed refs from references obtained\nfrom the remote repository, which is \"out of thin air\" as far as the\nlocal repository is concerned. Previously it did this by creating\n\"extra\" refs, then calling pack_refs() to bake them into the\npacked-refs file. Instead, create packed refs (in the packed\nreference cache) directly, then call pack_refs().\n\nAside from being more logical, this is another step towards removing\nextra refs entirely.\n\nSigned-off-by: Michael Haggerty \n---\n builtin/clone.c | 3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/builtin/clone.c b/builtin/clone.c\nindex 86db954..9413537 100644\n--- a/builtin/clone.c\n+++ b/builtin/clone.c\n@@ -441,11 +441,10 @@ static void write_remote_refs(const struct ref *local_refs)\n \tfor (r = local_refs; r; r = r->next) {\n \t\tif (!r->peer_ref)\n \t\t\tcontinue;\n-\t\tadd_extra_ref(r->peer_ref->name, r->old_sha1, 0);\n+\t\tadd_packed_ref(r->peer_ref->name, r->old_sha1);\n \t}\n \n \tpack_refs(PACK_REFS_ALL);\n-\tclear_extra_refs();\n }\n \n static int write_one_config(const char *key, const char *value, void *data)\n-- \n1.7.8.3\n"},{"id":"182671","messageId":"20120117063511.GA27770@sigill.intra.peff.net","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 0/4] Remove a user of extra_refs in clone","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2012-01-17T06:35:11Z","receivedAt":"2012-01-17T06:35:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Tue, Jan 17, 2012 at 06:50:30AM +0100, mhagger@alum.mit.edu wrote:\n\n> When cloning, write_remote_refs() creates local packed refs from the\n> refs read from the remote repository. It does this by creating extra\n> refs for the references then calling pack_refs() to bake the extra\n> refs into the packed-refs file, then calling clear_extra_refs().\n> \n> This is silly and relies on the kludgy extra_refs mechanism, which I\n> want to get rid of. Instead, add a function call add_packed_ref() to\n> the refs API, and use it to create packed refs (in the memory cache)\n> directly. Then call pack_refs() as before to write the packed-refs\n> file.\n\nI certainly approve of the goal.\n\n> Because the new add_packed_ref() function allows references (perhaps\n> many of them) to be added to an existing ref_array, it would be\n> inefficient to re-sort the list after every addition. So instead,\n> append new entries to the end of the ref_array and note that the array\n> is unsorted. Then, before the ref_array is used, check if it is\n> unsorted and sort it if necessary.\n\nMakes sense.\n\n> A side effect of this change is that the new packed references are\n> left in the in-memory packed reference cache after the return from\n> write_remote_refs() (whereas previously, the refs were stored as\n> temporary extra refs that were purged before return from the\n> function). I can't see any place in the following code where this\n> would make a difference, but there is quite a bit of code there so it\n> is hard to audit. Confirmation that this is OK would be welcome.\n\nActually, I think you may be fixing an extremely minor bug with this.\n\nIf later code in clone tries to resolve one of the refs in\nrefs/remotes//, the current code will see that it doesn't exist\nas a ref file (because we wrote it packed) and call get_packed_ref. That\nchecks the cached refs list, which will claim that did_packed is true,\nbut the \"packed\" array will be empty. Which is wrong; we _do_ have that\nref, and our cache is stale. After writing the packed list, the current\ncode probably ought to be calling invalidate_ref_cache(). It was only\nthe fact that most of the remaining code didn't care that this wasn't a\nbug in the first place.\n\nYour code makes more sense, in that it will keep the packed_refs list up\nto date, and later calls to resolve_ref will properly find those refs.\n\nThe only place where I can detect a change in behavior is in the reflog\ncreation. When we write the refs/remotes//HEAD ref, we call\ncreate_symref, which in turn will decide whether to write a reflog entry\nor not based on whether the pointed-to ref exists (because if we are\nmaking a symref to something that doesn't exist, we have no sha1 to\nwrite in the reflog entry). So before, we got no reflog for\nrefs/remotes//HEAD (because we erroneously thought that\nrefs/remotes/origin/master (or whatever) did not exist). With your\npatches, the reflog entry is created.\n\nI doubt anyone ever noticed, but now that code is at least working as\nintended.\n\n> Michael Haggerty (4):\n> pack_refs(): remove redundant check\n> ref_array: keep track of whether references are sorted\n> add_packed_ref(): new function in the refs API.\n> write_remote_refs(): create packed (rather than extra) refs\n\nI won't respond to each patch individually. All of them looked good to\nme. Thanks for a very pleasant read.\n\n-Peff\n"},{"id":"182673","messageId":"7v39beu8i4.fsf@alter.siamese.dyndns.org","threadId":"29380","inReplyTo":"1326779434-20106-1-git-send-email-mhagger@alum.mit.edu","subject":"Re: [PATCH 0/4] Remove a user of extra_refs in clone","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2012-01-17T06:51:31Z","receivedAt":"2012-01-17T06:51:31Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Yay ;-)\n\nThanks.\n"}]}