threads / patch / 29380

patch, 4 partsRemove a user of extra_refs in clone

Subject: [PATCH 0/4] Remove a user of extra_refs in clone

## tl;dr

7 messages between Jan 17, 2012 and Jan 17, 2012. Diffs are folded; open one to read it.

replies: 6people: 3as markdown or json

mhagger@alum.mit.edu· Jan 17, 2012, 05:50 UTC · lore
From: Michael Haggerty <mhagger@alum.mit.edu>

When cloning, write_remote_refs() creates local packed refs from the refs read from the remote repository. It does this by creating extra refs for the references then calling pack_refs() to bake the extra refs into the packed-refs file, then calling clear_extra_refs().

This is silly and relies on the kludgy extra_refs mechanism, which I want to get rid of. Instead, add a function call add_packed_ref() to the refs API, and use it to create packed refs (in the memory cache) directly. Then call pack_refs() as before to write the packed-refs file.

Because the new add_packed_ref() function allows references (perhaps many of them) to be added to an existing ref_array, it would be inefficient to re-sort the list after every addition. So instead, append new entries to the end of the ref_array and note that the array is unsorted. Then, before the ref_array is used, check if it is unsorted and sort it if necessary.

A side effect of this change is that the new packed references are left in the in-memory packed reference cache after the return from write_remote_refs() (whereas previously, the refs were stored as temporary extra refs that were purged before return from the function). I can't see any place in the following code where this would make a difference, but there is quite a bit of code there so it is hard to audit. Confirmation that this is OK would be welcome.

Michael Haggerty (4):
  pack_refs(): remove redundant check
  ref_array: keep track of whether references are sorted
  add_packed_ref(): new function in the refs API.
  write_remote_refs(): create packed (rather than extra) refs
 builtin/clone.c |    3 +--
 pack-refs.c     |    3 +--
 refs.c          |   39 ++++++++++++++++++++++++++++++++-------
 refs.h          |    6 ++++++
 4 files changed, 40 insertions(+), 11 deletions(-)
-- 
1.7.8.3
mhagger@alum.mit.edu· Jan 17, 2012, 05:50 UTC · re: mhagger@alum.mit.edu · lore

[PATCH 1/4] pack_refs(): remove redundant check

From: Michael Haggerty <mhagger@alum.mit.edu>

handle_one_ref() only adds refs to the cbdata.ref_to_prune list if (cbdata.flags & PACK_REFS_PRUNE) is set. So any references in this list at the end of pack_refs() can be pruned unconditionally.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
Trivial simplification, not essential to the rest of this patch
series.
 pack-refs.c |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)
Show changes to pack-refs.c +1 −2
diff --git a/pack-refs.c b/pack-refs.c
index 23bbd00..f09a054 100644
--- a/pack-refs.c
+++ b/pack-refs.c
@@ -143,7 +143,6 @@ int pack_refs(unsigned int flags)
 	packed.fd = -1;
 	if (commit_lock_file(&packed) < 0)
 		die_errno("unable to overwrite old ref-pack file");
-	if (cbdata.flags & PACK_REFS_PRUNE)
-		prune_refs(cbdata.ref_to_prune);
+	prune_refs(cbdata.ref_to_prune);
 	return 0;
 }

-- 
1.7.8.3
mhagger@alum.mit.edu· Jan 17, 2012, 05:50 UTC · re: mhagger@alum.mit.edu · lore

[PATCH 2/4] ref_array: keep track of whether references are sorted

From: Michael Haggerty <mhagger@alum.mit.edu>

Keep track of how many entries in a ref_array are already sorted. In sort_ref_array(), only call qsort() if the dir contains unsorted entries (i.e., if references have been appended to the end of the list since the last call to sort_ref_array()).

Sort ref_arrays only when needed, namely in search_ref_array() and in do_for_each_ref(). However, never sort the extra_refs, because extra_refs can contain multiple entries with the same name.

This change is currently not useful, because entries are not added to ref_arrays after they are created. But in a moment they will be...

Implementation note: we could store a binary "sorted" value instead of an integer, but storing the number of sorted entries leaves the way open for a couple of possible future optimizations:

* In sort_ref_array(), sort *only* the unsorted entries, then merge
  them with the sorted entries.  This should be faster if most of the
  entries are already sorted.
* Teach search_ref_array() to do a binary search of any sorted
  entries, and if unsuccessful do a linear search of any unsorted
  entries.  This would avoid the need to sort the list every time that
  search_ref_array() is called, and (given some intelligence about how
  often to sort) could significantly improve the speed in certain
  hypothetical usage patterns.
Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs.c |   33 ++++++++++++++++++++++++++-------
 1 files changed, 26 insertions(+), 7 deletions(-)
Show changes to refs.c +26 −7
diff --git a/refs.c b/refs.c
index 6f436f1..268816f 100644
--- a/refs.c
+++ b/refs.c
@@ -17,6 +17,15 @@ struct ref_entry {
 
 struct ref_array {
 	int nr, alloc;
+
+	/*
+	 * Entries with index 0 <= i < sorted are sorted by name.  New
+	 * entries are appended to the list unsorted, and are sorted
+	 * only when required; thus we avoid the need to sort the list
+	 * after the addition of every reference.
+	 */
+	int sorted;
+
 	struct ref_entry **refs;
 };
 
@@ -105,12 +114,18 @@ static int is_dup_ref(const struct ref_entry *ref1, const struct ref_entry *ref2
 	}
 }
 
+/*
+ * Sort the entries in array (if they are not already sorted).
+ */
 static void sort_ref_array(struct ref_array *array)
 {
 	int i, j;
 
-	/* Nothing to sort unless there are at least two entries */
-	if (array->nr < 2)
+	/*
+	 * This check also prevents passing a zero-length array to qsort(),
+	 * which is a problem on some platforms.
+	 */
+	if (array->sorted == array->nr)
 		return;
 
 	qsort(array->refs, array->nr, sizeof(*array->refs), ref_entry_cmp);
@@ -124,7 +139,7 @@ static void sort_ref_array(struct ref_array *array)
 		}
 		array->refs[++i] = array->refs[j];
 	}
-	array->nr = i + 1;
+	array->sorted = array->nr = i + 1;
 }
 
 static struct ref_entry *search_ref_array(struct ref_array *array, const char *refname)
@@ -137,7 +152,7 @@ static struct ref_entry *search_ref_array(struct ref_array *array, const char *r
 
 	if (!array->nr)
 		return NULL;
-
+	sort_ref_array(array);
 	len = strlen(refname) + 1;
 	e = xmalloc(sizeof(struct ref_entry) + len);
 	memcpy(e->name, refname, len);
@@ -168,6 +183,10 @@ static struct ref_cache {
 
 static struct ref_entry *current_ref;
 
+/*
+ * The extra_refs is never sorted, because it is allowed to contain entries
+ * with duplicate names.
+ */
 static struct ref_array extra_refs;
 
 static void clear_ref_array(struct ref_array *array)
@@ -176,7 +195,7 @@ static void clear_ref_array(struct ref_array *array)
 	for (i = 0; i < array->nr; i++)
 		free(array->refs[i]);
 	free(array->refs);
-	array->nr = array->alloc = 0;
+	array->sorted = array->nr = array->alloc = 0;
 	array->refs = NULL;
 }
 
@@ -268,7 +287,6 @@ static void read_packed_refs(FILE *f, struct ref_array *array)
 		    !get_sha1_hex(refline + 1, sha1))
 			hashcpy(last->peeled, sha1);
 	}
-	sort_ref_array(array);
 }
 
 void add_extra_ref(const char *refname, const unsigned char *sha1, int flag)
@@ -404,7 +422,6 @@ static struct ref_array *get_loose_refs(struct ref_cache *refs)
 {
 	if (!refs->did_loose) {
 		get_ref_dir(refs, "refs", &refs->loose);
-		sort_ref_array(&refs->loose);
 		refs->did_loose = 1;
 	}
 	return &refs->loose;
@@ -720,6 +737,8 @@ static int do_for_each_ref(const char *submodule, const char *base, each_ref_fn
 	for (i = 0; i < extra->nr; i++)
 		retval = do_one_ref(base, fn, trim, flags, cb_data, extra->refs[i]);
 
+	sort_ref_array(packed);
+	sort_ref_array(loose);
 	while (p < packed->nr && l < loose->nr) {
 		struct ref_entry *entry;
 		int cmp = strcmp(packed->refs[p]->name, loose->refs[l]->name);

-- 
1.7.8.3
mhagger@alum.mit.edu· Jan 17, 2012, 05:50 UTC · re: mhagger@alum.mit.edu · lore

[PATCH 3/4] add_packed_ref(): new function in the refs API.

From: Michael Haggerty <mhagger@alum.mit.edu>

Add a new function add_packed_ref() that adds a reference directly to the in-memory packed reference cache. This will be useful for creating local references while cloning.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
This new function call only stores the new reference to the in-memory
cache.  The user has to remember to call pack_refs() to actually write
the new reference(s) to the packed-refs file.  (I don't think it is
practical to make the write happen automatically.)
 refs.c |    6 ++++++
 refs.h |    6 ++++++
 2 files changed, 12 insertions(+), 0 deletions(-)
Show changes to 2 files +12 −0

refs.c, refs.h

diff --git a/refs.c b/refs.c
index 268816f..14f764d 100644
--- a/refs.c
+++ b/refs.c
@@ -319,6 +319,12 @@ static struct ref_array *get_packed_refs(struct ref_cache *refs)
 	return &refs->packed;
 }
 
+void add_packed_ref(const char *refname, const unsigned char *sha1)
+{
+	add_ref(get_packed_refs(get_ref_cache(NULL)),
+			create_ref_entry(refname, sha1, REF_ISPACKED, 1));
+}
+
 static void get_ref_dir(struct ref_cache *refs, const char *base,
 			struct ref_array *array)
 {
diff --git a/refs.h b/refs.h
index d498291..00ba1e2 100644
--- a/refs.h
+++ b/refs.h
@@ -51,6 +51,12 @@ extern int for_each_rawref(each_ref_fn, void *);
 extern void warn_dangling_symref(FILE *fp, const char *msg_fmt, const char *refname);
 
 /*
+ * Add a reference to the in-memory packed reference cache.  To actually
+ * write the reference to the packed-refs file, call pack_refs().
+ */
+extern void add_packed_ref(const char *refname, const unsigned char *sha1);
+
+/*
  * Extra refs will be listed by for_each_ref() before any actual refs
  * for the duration of this process or until clear_extra_refs() is
  * called. Only extra refs added before for_each_ref() is called will

-- 
1.7.8.3
mhagger@alum.mit.edu· Jan 17, 2012, 05:50 UTC · re: mhagger@alum.mit.edu · lore

[PATCH 4/4] write_remote_refs(): create packed (rather than extra) refs

From: Michael Haggerty <mhagger@alum.mit.edu>

write_remote_refs() creates new packed refs from references obtained from the remote repository, which is "out of thin air" as far as the local repository is concerned. Previously it did this by creating "extra" refs, then calling pack_refs() to bake them into the packed-refs file. Instead, create packed refs (in the packed reference cache) directly, then call pack_refs().

Aside from being more logical, this is another step towards removing extra refs entirely.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 builtin/clone.c |    3 +--
 1 files changed, 1 insertions(+), 2 deletions(-)
Show changes to builtin/clone.c +1 −2
diff --git a/builtin/clone.c b/builtin/clone.c
index 86db954..9413537 100644
--- a/builtin/clone.c
+++ b/builtin/clone.c
@@ -441,11 +441,10 @@ static void write_remote_refs(const struct ref *local_refs)
 	for (r = local_refs; r; r = r->next) {
 		if (!r->peer_ref)
 			continue;
-		add_extra_ref(r->peer_ref->name, r->old_sha1, 0);
+		add_packed_ref(r->peer_ref->name, r->old_sha1);
 	}
 
 	pack_refs(PACK_REFS_ALL);
-	clear_extra_refs();
 }
 
 static int write_one_config(const char *key, const char *value, void *data)

-- 
1.7.8.3
Jeff King· Jan 17, 2012, 06:35 UTC · re: mhagger@alum.mit.edu · lore

Re: [PATCH 0/4] Remove a user of extra_refs in clone

On Tue, Jan 17, 2012 at 06:50:30AM +0100, mhagger@alum.mit.edu wrote:
Show 10 quoted lines
> When cloning, write_remote_refs() creates local packed refs from the
> refs read from the remote repository.  It does this by creating extra
> refs for the references then calling pack_refs() to bake the extra
> refs into the packed-refs file, then calling clear_extra_refs().
> 
> This is silly and relies on the kludgy extra_refs mechanism, which I
> want to get rid of.  Instead, add a function call add_packed_ref() to
> the refs API, and use it to create packed refs (in the memory cache)
> directly.  Then call pack_refs() as before to write the packed-refs
> file.
I certainly approve of the goal.
Show 6 quoted lines
> Because the new add_packed_ref() function allows references (perhaps
> many of them) to be added to an existing ref_array, it would be
> inefficient to re-sort the list after every addition.  So instead,
> append new entries to the end of the ref_array and note that the array
> is unsorted.  Then, before the ref_array is used, check if it is
> unsorted and sort it if necessary.
Makes sense.
Show 7 quoted lines
> A side effect of this change is that the new packed references are
> left in the in-memory packed reference cache after the return from
> write_remote_refs() (whereas previously, the refs were stored as
> temporary extra refs that were purged before return from the
> function).  I can't see any place in the following code where this
> would make a difference, but there is quite a bit of code there so it
> is hard to audit.  Confirmation that this is OK would be welcome.
Actually, I think you may be fixing an extremely minor bug with this.

If later code in clone tries to resolve one of the refs in refs/remotes/<origin>/, the current code will see that it doesn't exist as a ref file (because we wrote it packed) and call get_packed_ref. That checks the cached refs list, which will claim that did_packed is true, but the "packed" array will be empty. Which is wrong; we _do_ have that ref, and our cache is stale. After writing the packed list, the current code probably ought to be calling invalidate_ref_cache(). It was only the fact that most of the remaining code didn't care that this wasn't a bug in the first place.

Your code makes more sense, in that it will keep the packed_refs list up to date, and later calls to resolve_ref will properly find those refs.

The only place where I can detect a change in behavior is in the reflog creation. When we write the refs/remotes/<origin>/HEAD ref, we call create_symref, which in turn will decide whether to write a reflog entry or not based on whether the pointed-to ref exists (because if we are making a symref to something that doesn't exist, we have no sha1 to write in the reflog entry). So before, we got no reflog for refs/remotes/<origin>/HEAD (because we erroneously thought that refs/remotes/origin/master (or whatever) did not exist). With your patches, the reflog entry is created.

I doubt anyone ever noticed, but now that code is at least working as intended.

Show 5 quoted lines
> Michael Haggerty (4):
>   pack_refs(): remove redundant check
>   ref_array: keep track of whether references are sorted
>   add_packed_ref(): new function in the refs API.
>   write_remote_refs(): create packed (rather than extra) refs

I won't respond to each patch individually. All of them looked good to me. Thanks for a very pleasant read.

-Peff

← back to recent threads