[PATCH 0/12] reducing resource usage of for_each_alternate_ref

[PATCH 0/12] reducing resource usage of for_each_alternate_ref

[Jeff King]

As I've mentioned before, I have some alternates repositories with
absurd numbers of refs, most of which are duplicates of each other[1].
There are a couple of problems I've seen:

 1. the way that for_each_alternate_ref() works has very high peak memory
    usage for this case

 2. the way that receive-pack de-duplicates the refs has high peak memory
    usage

 3. we access the alternate refs twice in fetch-pack

This fixes all three, along with a few other minor bugfixes, cleanups,
and optimizations. I've tried to order the series to keep bugfixes and
less-contentious changes near the front.

Just to give some numbers, on my worst-case repository (see [1]), this
drops peak RSS for "git clone --reference" from over 25GB to about 40MB.
Sort of, anyway.  You still pay a big CPU and RSS cost on the process in
the alternates repo that accesses packed-refs, but the 25GB came on top
of that. So this is a first pass at the low-hanging fruit.

I'll be the first to admit that this setup is insane. And some of the
optimizations are tradeoffs that help particularly the case where your
refs aren't unique. But for the most part should help _every_ case. And
in the cases where your refs are unique, either you don't have many (so
the tradeoffs are OK) or you have so many that you are pretty much
screwed no matter what (if your fetch is looking at 30 million unique
ref tips, the object storage is your problem, not looking at the refs).

A brief overview of the patches:

  [01/12]: for_each_alternate_ref: handle failure from real_pathdup()
  [02/12]: for_each_alternate_ref: stop trimming trailing slashes
  [03/12]: for_each_alternate_ref: use strbuf for path allocation

    Bugfixes and cleanups (the first one is actually a recent-ish
    regression).

  [04/12]: for_each_alternate_ref: pass name/oid instead of ref struct
  [05/12]: for_each_alternate_ref: replace transport code with for-each-ref
  [06/12]: clone: disable save_commit_buffer

    This gives the 25GB->40MB benefit. There are a bunch of caveats in
    patch 05, but I _think_ it's the right direction for the reasons I
    outlined there.

  [07/12]: fetch-pack: cache results of for_each_alternate_ref

    Just running for-each-ref in the giant alternates repo is about a
    minute of CPU, plus 10GB heap, and fetch-pack wants to do it twice.
    This drops it to once.

  [08/12]: add oidset API
  [09/12]: receive-pack: use oidset to de-duplicate .have lines

    These give another ~12GB RSS improvement when receive-pack looks at
    the alternates in my worst-case repo.

    This is less tested than the earlier ones, as we've disabled
    receive-pack looking at alternates in production (see [1] below).
    I just did them for completeness upstream.

  [10/12]: receive-pack: fix misleading namespace/.have comment
  [11/12]: receive-pack: treat namespace .have lines like alternates
  [12/12]: receive-pack: avoid duplicates between our refs and alternates

    These are optimizations to avoid more duplicate .have lines, and
    should benefit even non-insane cases. As with 8-12, not as well
    tested by me.

 Makefile               |  1 +
 builtin/clone.c        |  1 +
 builtin/receive-pack.c | 41 +++++++++++++++-------------
 fetch-pack.c           | 48 ++++++++++++++++++++++++++++-----
 object.h               |  2 +-
 oidset.c               | 49 ++++++++++++++++++++++++++++++++++
 oidset.h               | 45 +++++++++++++++++++++++++++++++
 t/t5400-send-pack.sh   | 38 ++++++++++++++++++++++++++
 transport.c            | 72 +++++++++++++++++++++++++++++++++++---------------
 transport.h            |  2 +-
 10 files changed, 250 insertions(+), 49 deletions(-)
 create mode 100644 oidset.c
 create mode 100644 oidset.h

-Peff

[1] Background, if you care:

    I've mentioned before that GitHub's repository storage uses a
    fork-network layout. Each user gets their own "fork" repository, and
    it points to "network.git" as shared storage. The network.git
    repository has a ref for each fork that is updated periodically via
    "git fetch".

    So the network.git repo contains O(nr_forks * nr_refs_in_fork) refs.
    Quite a few of these point to the same tip sha1s, as each fork has
    the same tags. One of the most pathological cases is a popular
    public repo that has ~44K tags in it. The network repo has ~80
    million refs, of which ~60K are unique. You can imagine that it
    takes some time to access the refs. Basically anything that loads
    the network.git packed-refs file takes an extra minute of CPU and
    needs ~10G RSS to store the internal cache of `packed-refs`.

    Most operations don't care about this; they work on the fork repo,
    and never look at the network refs. But we _do_ sometimes peek at
    alternate refs from receive-pack and fetch-pack to tell the other
    side about tips we have.

    These optimizations backfire completely in such a setting. Besides
    the CPU and memory spikes on the server, even just the unique refs
    add over 3MB to the ref advertisement. So for the time being, we've
    disabled them. I have patches that add a receive.advertiseAlternates
    config option, if anybody is interested.

    So why do I care?  There is one exception: when we are cloning a
    fork, we turn on the fetch-pack side of the optimizations. This is
    worth it for a large repository, as it saves us having to transfer
    any objects at all (and therefore not process them with index-pack,
    which is expensive).

    This series is also a first step towards other optimizations, like
    asking for just the alternate refs from _one_ of the forks. I hope
    one day to turn alternates optimizations back on everywhere.

[PATCH 01/12] for_each_alternate_ref: handle failure from real_pathdup()

[Jeff King]

In older versions of git, if real_path() failed to resolve
the alternate object store path, we would die() with an
error. However, since 4ac9006f8 (real_path: have callers use
real_pathdup and strbuf_realpath, 2016-12-12) we use the
real_pathdup() function, which may return NULL. Since we
don't check the return value, we can segfault.

This is hard to trigger in practice, since we check that the
path is accessible before creating the alternate_object_database
struct. But it could be removed racily, or we could see a
transient filesystem error.

We could restore the original behavior by switching back to
xstrdup(real_path()).  However, dying is probably not the
best option here. This whole function is best-effort
already; there might not even be a repository around the
shared objects at all. And if the alternate store has gone
away, there are no objects to show.

So let's just quietly return, as we would if we failed to
open "refs/", or if upload-pack failed to start, etc.

Signed-off-by: Jeff King <peff@peff.net>
---
 transport.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/transport.c b/transport.c
index c86ba2eb8..74d0e45bd 100644
--- a/transport.c
+++ b/transport.c
@@ -1215,6 +1215,8 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 	struct alternate_refs_data *cb = data;
 
 	other = real_pathdup(e->path);
+	if (!other)
+		return 0;
 	len = strlen(other);
 
 	while (other[len-1] == '/')
-- 
2.11.0.765.g454d2182f

Re: [PATCH 01/12] for_each_alternate_ref: handle failure from real_pathdup()

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> In older versions of git, if real_path() failed to resolve
> the alternate object store path, we would die() with an
> error. However, since 4ac9006f8 (real_path: have callers use
> real_pathdup and strbuf_realpath, 2016-12-12) we use the
> real_pathdup() function, which may return NULL. Since we
> don't check the return value, we can segfault.
>
> This is hard to trigger in practice, since we check that the
> path is accessible before creating the alternate_object_database
> struct. But it could be removed racily, or we could see a
> transient filesystem error.
>
> We could restore the original behavior by switching back to
> xstrdup(real_path()).  However, dying is probably not the
> best option here. This whole function is best-effort
> already; there might not even be a repository around the
> shared objects at all. And if the alternate store has gone
> away, there are no objects to show.
>
> So let's just quietly return, as we would if we failed to
> open "refs/", or if upload-pack failed to start, etc.

That's sensible, methinks.

>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  transport.c | 2 ++
>  1 file changed, 2 insertions(+)
>
> diff --git a/transport.c b/transport.c
> index c86ba2eb8..74d0e45bd 100644
> --- a/transport.c
> +++ b/transport.c
> @@ -1215,6 +1215,8 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
>  	struct alternate_refs_data *cb = data;
>  
>  	other = real_pathdup(e->path);
> +	if (!other)
> +		return 0;
>  	len = strlen(other);
>  
>  	while (other[len-1] == '/')

[PATCH 02/12] for_each_alternate_ref: stop trimming trailing slashes

[Jeff King]

The real_pathdup() function will have removed extra slashes
for us already (on top of the normalize_path() done when we
created the alternate_object_database struct in the first
place).

Incidentally, this also fixes the case where the path is
just "/", which would read off the start of the array.
That doesn't seem possible to trigger in practice, though,
as link_alt_odb_entry() blindly eats trailing slashes,
including a bare "/".

Signed-off-by: Jeff King <peff@peff.net>
---
I think the "/" thing in link_alt_odb_entry() is buggy, and it's an easy
one-liner fix.  But I notice some of the rest of the code isn't ready to
handle "/" (mostly it just duplicates "/" when appending to the path),
so I left it for now (and I doubt anybody cares anyway).

 transport.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/transport.c b/transport.c
index 74d0e45bd..6b4b3ed31 100644
--- a/transport.c
+++ b/transport.c
@@ -1219,8 +1219,6 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 		return 0;
 	len = strlen(other);
 
-	while (other[len-1] == '/')
-		other[--len] = '\0';
 	if (len < 8 || memcmp(other + len - 8, "/objects", 8))
 		goto out;
 	/* Is this a git repository with refs? */
-- 
2.11.0.765.g454d2182f

[PATCH 03/12] for_each_alternate_ref: use strbuf for path allocation

[Jeff King]

We have a string with ".../objects" pointing to the
alternate object store, and overwrite bits of it to look at
other paths in the (potential) git repository holding it.
This works because the only path we care about is "refs",
which is shorter than "objects".

Using a strbuf to hold the path lets us get rid of some
magic numbers, and makes it more obvious that the memory
operations are safe.

Signed-off-by: Jeff King <peff@peff.net>
---
I had thought I was going to need to generate more paths in the
alternate repo, but I ended up not needing to. So this was originally
done to make that easier, but I think it stands on its own as a cleanup.

 transport.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

diff --git a/transport.c b/transport.c
index 6b4b3ed31..594533d88 100644
--- a/transport.c
+++ b/transport.c
@@ -1207,34 +1207,34 @@ struct alternate_refs_data {
 static int refs_from_alternate_cb(struct alternate_object_database *e,
 				  void *data)
 {
-	char *other;
-	size_t len;
+	struct strbuf path = STRBUF_INIT;
+	size_t base_len;
 	struct remote *remote;
 	struct transport *transport;
 	const struct ref *extra;
 	struct alternate_refs_data *cb = data;
 
-	other = real_pathdup(e->path);
-	if (!other)
-		return 0;
-	len = strlen(other);
-
-	if (len < 8 || memcmp(other + len - 8, "/objects", 8))
+	if (!strbuf_realpath(&path, e->path, 0))
+		goto out;
+	if (!strbuf_strip_suffix(&path, "/objects"))
 		goto out;
+	base_len = path.len;
+
 	/* Is this a git repository with refs? */
-	memcpy(other + len - 8, "/refs", 6);
-	if (!is_directory(other))
+	strbuf_addstr(&path, "/refs");
+	if (!is_directory(path.buf))
 		goto out;
-	other[len - 8] = '\0';
-	remote = remote_get(other);
-	transport = transport_get(remote, other);
+	strbuf_setlen(&path, base_len);
+
+	remote = remote_get(path.buf);
+	transport = transport_get(remote, path.buf);
 	for (extra = transport_get_remote_refs(transport);
 	     extra;
 	     extra = extra->next)
 		cb->fn(extra, cb->data);
 	transport_disconnect(transport);
 out:
-	free(other);
+	strbuf_release(&path);
 	return 0;
 }
 
-- 
2.11.0.765.g454d2182f

Re: [PATCH 03/12] for_each_alternate_ref: use strbuf for path allocation

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> We have a string with ".../objects" pointing to the
> alternate object store, and overwrite bits of it to look at
> other paths in the (potential) git repository holding it.
> This works because the only path we care about is "refs",
> which is shorter than "objects".

Yup, this was probably copied from a lazy original I wrote ;-)
Thanks for cleaning up.

Re: [PATCH 03/12] for_each_alternate_ref: use strbuf for path allocation

[Jeff King]

On Wed, Jan 25, 2017 at 10:29:05AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > We have a string with ".../objects" pointing to the
> > alternate object store, and overwrite bits of it to look at
> > other paths in the (potential) git repository holding it.
> > This works because the only path we care about is "refs",
> > which is shorter than "objects".
> 
> Yup, this was probably copied from a lazy original I wrote ;-)
> Thanks for cleaning up.

To be fair, the original predates all of the helper functions I used
here. :)

-Peff

[PATCH 04/12] for_each_alternate_ref: pass name/oid instead of ref struct

[Jeff King]

Breaking down the fields in the interface makes it easier to
change the backend of for_each_alternate_ref to something
that doesn't use "struct ref" internally.

The only field that callers actually look at is the oid,
anyway. The refname is kept in the interface as a plausible
thing for future code to want.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c |  6 ++++--
 fetch-pack.c           | 12 ++++++++----
 transport.c            |  2 +-
 transport.h            |  2 +-
 4 files changed, 14 insertions(+), 8 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 6b97cbdbe..b9f2c0cc5 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -277,10 +277,12 @@ static int show_one_alternate_sha1(const unsigned char sha1[20], void *unused)
 	return 0;
 }
 
-static void collect_one_alternate_ref(const struct ref *ref, void *data)
+static void collect_one_alternate_ref(const char *refname,
+				      const struct object_id *oid,
+				      void *data)
 {
 	struct sha1_array *sa = data;
-	sha1_array_append(sa, ref->old_oid.hash);
+	sha1_array_append(sa, oid->hash);
 }
 
 static void write_head_info(void)
diff --git a/fetch-pack.c b/fetch-pack.c
index 601f0779a..54f84c573 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -253,9 +253,11 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_ref(const struct ref *ref, void *unused)
+static void insert_one_alternate_ref(const char *refname,
+				     const struct object_id *oid,
+				     void *unused)
 {
-	rev_list_insert_ref(NULL, ref->old_oid.hash);
+	rev_list_insert_ref(NULL, oid->hash);
 }
 
 #define INITIAL_FLUSH 16
@@ -619,9 +621,11 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(const struct ref *ref, void *unused)
+static void mark_alternate_complete(const char *refname,
+				    const struct object_id *oid,
+				    void *unused)
 {
-	mark_complete(ref->old_oid.hash);
+	mark_complete(oid->hash);
 }
 
 static int everything_local(struct fetch_pack_args *args,
diff --git a/transport.c b/transport.c
index 594533d88..983d8fec1 100644
--- a/transport.c
+++ b/transport.c
@@ -1231,7 +1231,7 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 	for (extra = transport_get_remote_refs(transport);
 	     extra;
 	     extra = extra->next)
-		cb->fn(extra, cb->data);
+		cb->fn(extra->name, &extra->old_oid, cb->data);
 	transport_disconnect(transport);
 out:
 	strbuf_release(&path);
diff --git a/transport.h b/transport.h
index 9820f10b8..b7bb07d2c 100644
--- a/transport.h
+++ b/transport.h
@@ -254,6 +254,6 @@ int transport_refs_pushed(struct ref *ref);
 void transport_print_push_status(const char *dest, struct ref *refs,
 		  int verbose, int porcelain, unsigned int *reject_reasons);
 
-typedef void alternate_ref_fn(const struct ref *, void *);
+typedef void alternate_ref_fn(const char *refname, const struct object_id *oid, void *);
 extern void for_each_alternate_ref(alternate_ref_fn, void *);
 #endif
-- 
2.11.0.765.g454d2182f

[PATCH 05/12] for_each_alternate_ref: replace transport code with for-each-ref

[Jeff King]

The current method for getting the refs from an alternate is
to run upload-pack in the alternate and parse its output
using the normal transport code.  This works and is
reasonably short, but it has a very bad memory footprint
when there are a lot of refs in the alternate. There are two
problems:

  1. It reads in all of the refs before passing any back to
     us. Which means that our peak memory usage has to store
     every ref (including duplicates for peeled variants),
     even if our callback could determine that some are not
     interesting (e.g., because they point to the same sha1
     as another ref).

  2. It allocates a "struct ref" for each one. Among other
     things, this contains 3 separate 20-byte oids, along
     with the name and various pointers.  That can add up,
     especially if the callback is only interested in the
     sha1 (which it can store in a sha1_array as just 20
     bytes).

On a particularly pathological case, where the alternate had
over 80 million refs pointing to only around 60,000 unique
objects, the peak heap usage of "git clone --reference" grew
to over 25GB.

This patch instead calls git-for-each-ref in the alternate
repository, and passes each line to the callback as we read
it. That drops the peak heap of the same command to 50MB.

I considered and rejected a few alternatives.

We could read all of the refs in the alternate using our own
ref code, just as we do with submodules.  However, as memory
footprint is one of the concerns here, we want to avoid
loading those refs into our own memory as a whole.

It's possible that this will be a better technique in the
future when the ref code can more easily iterate without
loading all of packed-refs into memory.

Another option is to keep calling upload-pack, and just
parse its output ourselves in a streaming fashion. Besides
for-each-ref being simpler (we get to define the format
ourselves, and don't have to deal with speaking the git
protocol), it's more flexible for possible future changes.

For instance, it might be useful for the caller to be able
to limit the set of "interesting" alternate refs.  The
motivating example is one where many "forks" of a particular
repository share object storage, and the shared storage has
refs for each fork (which is why so many of the refs are
duplicates; each fork has the same tags).  A plausible
future optimization would be to ask for the alternate refs
for just _one_ fork (if you had some out-of-band way of
knowing which was the most interesting or important for the
current operation).

Similarly, no callbacks actually care about the symref value
of alternate refs, and as before, this patch ignores them
entirely.  However, if we wanted to add them, for-each-ref's
"%(symref)" is going to be more flexible than upload-pack,
because the latter only handles the HEAD symref due to
historical constraints.

There is one potential downside, though: unlike upload-pack,
our for-each-ref command doesn't report the peeled value of
refs. The existing code calls the alternate_ref_fn callback
twice for tags: once for the tag, and once for the peeled
value with the refname set to "ref^{}".

For the callers in fetch-pack, this doesn't matter at all.
We immediately peel each tag down to a commit either way (so
there's a slight improvement, as do not bother passing the
redundant data over the pipe). For the caller in
receive-pack, it means we will not advertise the peeled
values of tags in our alternate. However, we also don't
advertise peeled values for our _own_ tags, so this is
actually making things more consistent.

It's unclear whether receive-pack advertising peeled values
is a win or not. On one hand, giving more information to the
other side may let it omit some objects from the push. On
the other hand, for tags which both sides have, they simply
bloat the advertisement. The upload-pack advertisement of
git.git is about 30% larger than the receive-pack
advertisement due to its peeled information.

This patch omits the peeled information from
for_each_alternate_ref entirely, and leaves it up to the
caller whether they want to dig up the information.

Signed-off-by: Jeff King <peff@peff.net>
---
I also tried adding "%(*objectname)" to for-each-ref to just
grab the peeled information, but the peel implementation in
ref-filter is _really_ slow. It doesn't use the packed-ref
peel information, and it doesn't recognize duplicates (so in
the 80 million case, it really parses 80 million tags).

 transport.c | 48 ++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 38 insertions(+), 10 deletions(-)

diff --git a/transport.c b/transport.c
index 983d8fec1..ef8e09298 100644
--- a/transport.c
+++ b/transport.c
@@ -1199,6 +1199,42 @@ char *transport_anonymize_url(const char *url)
 	return xstrdup(url);
 }
 
+static void read_alternate_refs(const char *path,
+				alternate_ref_fn *cb,
+				void *data)
+{
+	struct child_process cmd = CHILD_PROCESS_INIT;
+	struct strbuf line = STRBUF_INIT;
+	FILE *fh;
+
+	cmd.git_cmd = 1;
+	argv_array_pushf(&cmd.args, "--git-dir=%s", path);
+	argv_array_push(&cmd.args, "for-each-ref");
+	argv_array_push(&cmd.args, "--format=%(objectname) %(refname)");
+	cmd.env = local_repo_env;
+	cmd.out = -1;
+
+	if (start_command(&cmd))
+		return;
+
+	fh = xfdopen(cmd.out, "r");
+	while (strbuf_getline_lf(&line, fh) != EOF) {
+		struct object_id oid;
+
+		if (get_oid_hex(line.buf, &oid) ||
+		    line.buf[GIT_SHA1_HEXSZ] != ' ') {
+			warning("invalid line while parsing alternate refs: %s",
+				line.buf);
+			break;
+		}
+
+		cb(line.buf + GIT_SHA1_HEXSZ + 1, &oid, data);
+	}
+
+	fclose(fh);
+	finish_command(&cmd);
+}
+
 struct alternate_refs_data {
 	alternate_ref_fn *fn;
 	void *data;
@@ -1209,9 +1245,6 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 {
 	struct strbuf path = STRBUF_INIT;
 	size_t base_len;
-	struct remote *remote;
-	struct transport *transport;
-	const struct ref *extra;
 	struct alternate_refs_data *cb = data;
 
 	if (!strbuf_realpath(&path, e->path, 0))
@@ -1226,13 +1259,8 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 		goto out;
 	strbuf_setlen(&path, base_len);
 
-	remote = remote_get(path.buf);
-	transport = transport_get(remote, path.buf);
-	for (extra = transport_get_remote_refs(transport);
-	     extra;
-	     extra = extra->next)
-		cb->fn(extra->name, &extra->old_oid, cb->data);
-	transport_disconnect(transport);
+	read_alternate_refs(path.buf, cb->fn, cb->data);
+
 out:
 	strbuf_release(&path);
 	return 0;
-- 
2.11.0.765.g454d2182f

Re: [PATCH 05/12] for_each_alternate_ref: replace transport code with for-each-ref

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> ...
> This patch omits the peeled information from
> for_each_alternate_ref entirely, and leaves it up to the
> caller whether they want to dig up the information.
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> I also tried adding "%(*objectname)" to for-each-ref to just
> grab the peeled information, but the peel implementation in
> ref-filter is _really_ slow. It doesn't use the packed-ref
> peel information, and it doesn't recognize duplicates (so in
> the 80 million case, it really parses 80 million tags).

That's an interesting tangent that may want to be looked into.

>  transport.c | 48 ++++++++++++++++++++++++++++++++++++++----------
>  1 file changed, 38 insertions(+), 10 deletions(-)

The updated code is a more pleasant read.

[PATCH 06/12] clone: disable save_commit_buffer

[Jeff King]

Normally git caches the raw commit object contents in
"struct commit". This makes it fast to run parse_commit()
followed by a pretty-print operation.

For commands which don't actually pretty-print the commits,
the caching is wasteful (and may use quite a lot of memory
if git accesses a large number of commits).

For fetching operations like clone, we already disable
save_commit_buffer in everything_local(), where we may
traverse. But clone also parses commits before it even gets
there; it looks at commits reachable from its refs, and from
alternate refs.

In one real-world case with a large number of tags, this
cut about 10MB off of clone's heap usage. Not spectacular,
but there's really no downside.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/clone.c | 1 +
 1 file changed, 1 insertion(+)

diff --git a/builtin/clone.c b/builtin/clone.c
index 5ef81927a..3fca45e7e 100644
--- a/builtin/clone.c
+++ b/builtin/clone.c
@@ -858,6 +858,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
 	struct refspec *refspec;
 	const char *fetch_pattern;
 
+	save_commit_buffer = 0;
 	packet_trace_identity("clone");
 	argc = parse_options(argc, argv, prefix, builtin_clone_options,
 			     builtin_clone_usage, 0);
-- 
2.11.0.765.g454d2182f

Re: [PATCH 06/12] clone: disable save_commit_buffer

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Normally git caches the raw commit object contents in
> "struct commit". This makes it fast to run parse_commit()
> followed by a pretty-print operation.
>
> For commands which don't actually pretty-print the commits,
> the caching is wasteful (and may use quite a lot of memory
> if git accesses a large number of commits).
>
> For fetching operations like clone, we already disable

s/clone/fetch/ you meant?

> In one real-world case with a large number of tags, this
> cut about 10MB off of clone's heap usage. Not spectacular,
> but there's really no downside.

"There is no downside" is especially true in the modern world post
v2.1, where get_commit_buffer() is what everybody has to go through
to access this information.  I would have been very hesitant to
accept a patch like this one if we didn't do that clean-up, as a
stray codepath could have just done "commit->buffer" and segfaulted
or said "ah, there is no message", neither of which is satisfactory.

Thanks.

> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  builtin/clone.c | 1 +
>  1 file changed, 1 insertion(+)
>
> diff --git a/builtin/clone.c b/builtin/clone.c
> index 5ef81927a..3fca45e7e 100644
> --- a/builtin/clone.c
> +++ b/builtin/clone.c
> @@ -858,6 +858,7 @@ int cmd_clone(int argc, const char **argv, const char *prefix)
>  	struct refspec *refspec;
>  	const char *fetch_pattern;
>  
> +	save_commit_buffer = 0;
>  	packet_trace_identity("clone");
>  	argc = parse_options(argc, argv, prefix, builtin_clone_options,
>  			     builtin_clone_usage, 0);

Re: [PATCH 06/12] clone: disable save_commit_buffer

[Jeff King]

On Wed, Jan 25, 2017 at 11:11:01AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Normally git caches the raw commit object contents in
> > "struct commit". This makes it fast to run parse_commit()
> > followed by a pretty-print operation.
> >
> > For commands which don't actually pretty-print the commits,
> > the caching is wasteful (and may use quite a lot of memory
> > if git accesses a large number of commits).
> >
> > For fetching operations like clone, we already disable
> 
> s/clone/fetch/ you meant?

Well, no, because this patch deals with clone.

It's likely that builtin/fetch.c would want the same treatment. It
didn't come up for me because I've disabled the alternates check for
that case (but you can't do that with stock git), and I didn't dig
further.

Possibly this should just go into fetch-pack.c, right before we walk
over all of the refs and call parse_object() and deref_tag() on all of
them. It feels a little funny to tweak the global save_commit_buffer
flag there, but it already do so in everything_local(), so I don't think
we're really losing much.

> > In one real-world case with a large number of tags, this
> > cut about 10MB off of clone's heap usage. Not spectacular,
> > but there's really no downside.
> 
> "There is no downside" is especially true in the modern world post
> v2.1, where get_commit_buffer() is what everybody has to go through
> to access this information.  I would have been very hesitant to
> accept a patch like this one if we didn't do that clean-up, as a
> stray codepath could have just done "commit->buffer" and segfaulted
> or said "ah, there is no message", neither of which is satisfactory.

Yep, I had a similar thought while writing it. I would have been very
hesitant to propose it back then, too. :)

-Peff

Re: [PATCH 06/12] clone: disable save_commit_buffer

[Jeff King]

On Wed, Jan 25, 2017 at 02:27:40PM -0500, Jeff King wrote:

> > > For fetching operations like clone, we already disable
> > 
> > s/clone/fetch/ you meant?
> 
> Well, no, because this patch deals with clone.
> 
> It's likely that builtin/fetch.c would want the same treatment. It
> didn't come up for me because I've disabled the alternates check for
> that case (but you can't do that with stock git), and I didn't dig
> further.
> 
> Possibly this should just go into fetch-pack.c, right before we walk
> over all of the refs and call parse_object() and deref_tag() on all of
> them. It feels a little funny to tweak the global save_commit_buffer
> flag there, but it already do so in everything_local(), so I don't think
> we're really losing much.

Hrm. So I thought it might be useful to write a patch that just tweaks
save_commit_buffer at the start of fetch_pack(). But looking it over,
we call everything_local() _before_ we walk over all the refs. So
save_commit_buffer should already be turned off for my case.

I wonder if I made a mistake while measuring the peak RSS. Or if clone
parses some commits before it calls into fetch_pack() (but which
objects? It doesn't have any until it does the fetch).

Perhaps we should just drop this patch (though I think it is logically
consistent and wouldn't hurt anything).

-Peff

Re: [PATCH 06/12] clone: disable save_commit_buffer

[Jeff King]

On Wed, Jan 25, 2017 at 02:35:41PM -0500, Jeff King wrote:

> On Wed, Jan 25, 2017 at 02:27:40PM -0500, Jeff King wrote:
> 
> > > > For fetching operations like clone, we already disable
> > > 
> > > s/clone/fetch/ you meant?
> > 
> > Well, no, because this patch deals with clone.
> > 
> > It's likely that builtin/fetch.c would want the same treatment. It
> > didn't come up for me because I've disabled the alternates check for
> > that case (but you can't do that with stock git), and I didn't dig
> > further.
> > 
> > Possibly this should just go into fetch-pack.c, right before we walk
> > over all of the refs and call parse_object() and deref_tag() on all of
> > them. It feels a little funny to tweak the global save_commit_buffer
> > flag there, but it already do so in everything_local(), so I don't think
> > we're really losing much.
> 
> Hrm. So I thought it might be useful to write a patch that just tweaks
> save_commit_buffer at the start of fetch_pack(). But looking it over,
> we call everything_local() _before_ we walk over all the refs. So
> save_commit_buffer should already be turned off for my case.
> 
> I wonder if I made a mistake while measuring the peak RSS. Or if clone
> parses some commits before it calls into fetch_pack() (but which
> objects? It doesn't have any until it does the fetch).
> 
> Perhaps we should just drop this patch (though I think it is logically
> consistent and wouldn't hurt anything).

OK, I just repeated my heap measurements with valgrind's massif tool,
specifically checking builds of this patch and its parent. I couldn't
find any improvement. So I must have screwed something up in my earlier
measurements.

Sorry for the noise. I think we should probably just drop this patch.

-Peff

[PATCH 07/12] fetch-pack: cache results of for_each_alternate_ref

[Jeff King]

We may run for_each_alternate_ref() twice, once in
find_common() and once in everything_local(). This operation
can be expensive, because it involves running a sub-process
which must freshly load all of the alternate's refs from
disk.

Let's cache and reuse the results between the two calls. We
can make some optimizations based on the particular use
pattern in fetch-pack to keep our memory usage down.

The first is that we only care about the sha1s, not the refs
themselves. So it's OK to store only the sha1s, and to
suppress duplicates. The natural fit would therefore be a
sha1_array.

However, sha1_array's de-duplication happens only after it
has read and sorted all entries. It still stores each
duplicate. For an alternate with a large number of refs
pointing to the same commits, this is a needless expense.

Instead, we'd prefer to eliminate duplicates before putting
them in the cache, which implies using a hash. We can
further note that fetch-pack will call parse_object() on
each alternate sha1. We can therefore keep our cache as a
set of pointers to "struct object". That gives us a place to
put our "already seen" bit with an optimized hash lookup.
And as a bonus, the object stores the sha1 for us, so
pointer-to-object is all we need.

There are two extra optimizations I didn't do here:

  - we actually store an array of pointer-to-object.
    Technically we could just walk the obj_hash table
    looking for entries with the ALTERNATE flag set (because
    our use case doesn't care about the order here).

    But that hash table may be mostly composed of
    non-ALTERNATE entries, so we'd waste time walking over
    them. So it would be a slight win in memory use, but a
    loss in CPU.

  - the items we pull out of the cache are actual "struct
    object"s, but then we feed "obj->sha1" to our
    sub-functions, which promptly call parse_object().

    This second parse is cheap, because it starts with
    lookup_object() and will bail immediately when it sees
    we've already parsed the object. We could save the extra
    hash lookup, but it would involve refactoring the
    functions we call. It may or may not be worth the
    trouble.

Signed-off-by: Jeff King <peff@peff.net>
---
 fetch-pack.c | 52 ++++++++++++++++++++++++++++++++++++++++++----------
 object.h     |  2 +-
 2 files changed, 43 insertions(+), 11 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 54f84c573..e0f5d5ce8 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -35,6 +35,7 @@ static const char *alternate_shallow_file;
 #define COMMON_REF	(1U << 2)
 #define SEEN		(1U << 3)
 #define POPPED		(1U << 4)
+#define ALTERNATE	(1U << 5)
 
 static int marked;
 
@@ -67,6 +68,41 @@ static inline void print_verbose(const struct fetch_pack_args *args,
 	fputc('\n', stderr);
 }
 
+struct alternate_object_cache {
+	struct object **items;
+	size_t nr, alloc;
+};
+
+static void cache_one_alternate(const char *refname,
+				const struct object_id *oid,
+				void *vcache)
+{
+	struct alternate_object_cache *cache = vcache;
+	struct object *obj = parse_object(oid->hash);
+
+	if (!obj || (obj->flags & ALTERNATE))
+		return;
+
+	obj->flags |= ALTERNATE;
+	ALLOC_GROW(cache->items, cache->nr + 1, cache->alloc);
+	cache->items[cache->nr++] = obj;
+}
+
+static void for_each_cached_alternate(void (*cb)(struct object *))
+{
+	static int initialized;
+	static struct alternate_object_cache cache;
+	size_t i;
+
+	if (!initialized) {
+		for_each_alternate_ref(cache_one_alternate, &cache);
+		initialized = 1;
+	}
+
+	for (i = 0; i < cache.nr; i++)
+		cb(cache.items[i]);
+}
+
 static void rev_list_push(struct commit *commit, int mark)
 {
 	if (!(commit->object.flags & mark)) {
@@ -253,11 +289,9 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_ref(const char *refname,
-				     const struct object_id *oid,
-				     void *unused)
+static void insert_one_alternate_object(struct object *obj)
 {
-	rev_list_insert_ref(NULL, oid->hash);
+	rev_list_insert_ref(NULL, obj->oid.hash);
 }
 
 #define INITIAL_FLUSH 16
@@ -300,7 +334,7 @@ static int find_common(struct fetch_pack_args *args,
 	marked = 1;
 
 	for_each_ref(rev_list_insert_ref_oid, NULL);
-	for_each_alternate_ref(insert_one_alternate_ref, NULL);
+	for_each_cached_alternate(insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -621,11 +655,9 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(const char *refname,
-				    const struct object_id *oid,
-				    void *unused)
+static void mark_alternate_complete(struct object *obj)
 {
-	mark_complete(oid->hash);
+	mark_complete(obj->oid.hash);
 }
 
 static int everything_local(struct fetch_pack_args *args,
@@ -661,7 +693,7 @@ static int everything_local(struct fetch_pack_args *args,
 
 	if (!args->deepen) {
 		for_each_ref(mark_complete_oid, NULL);
-		for_each_alternate_ref(mark_alternate_complete, NULL);
+		for_each_cached_alternate(mark_alternate_complete);
 		commit_list_sort_by_date(&complete);
 		if (cutoff)
 			mark_recent_complete_commits(args, cutoff);
diff --git a/object.h b/object.h
index 614a00675..f52957dcb 100644
--- a/object.h
+++ b/object.h
@@ -29,7 +29,7 @@ struct object_array {
 /*
  * object flag allocation:
  * revision.h:      0---------10                                26
- * fetch-pack.c:    0---4
+ * fetch-pack.c:    0---5
  * walker.c:        0-2
  * upload-pack.c:       4       11----------------19
  * builtin/blame.c:               12-13
-- 
2.11.0.765.g454d2182f

Re: [PATCH 07/12] fetch-pack: cache results of for_each_alternate_ref

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> +struct alternate_object_cache {
> +	struct object **items;
> +	size_t nr, alloc;
> +};
> +
> +static void cache_one_alternate(const char *refname,
> +				const struct object_id *oid,
> +				void *vcache)
> +{
> +	struct alternate_object_cache *cache = vcache;
> +	struct object *obj = parse_object(oid->hash);
> +
> +	if (!obj || (obj->flags & ALTERNATE))
> +		return;
> +
> +	obj->flags |= ALTERNATE;
> +	ALLOC_GROW(cache->items, cache->nr + 1, cache->alloc);
> +	cache->items[cache->nr++] = obj;
> +}

Nice.  I love simplicity.

> diff --git a/object.h b/object.h
> index 614a00675..f52957dcb 100644
> --- a/object.h
> +++ b/object.h
> @@ -29,7 +29,7 @@ struct object_array {
>  /*
>   * object flag allocation:
>   * revision.h:      0---------10                                26
> - * fetch-pack.c:    0---4
> + * fetch-pack.c:    0---5
>   * walker.c:        0-2
>   * upload-pack.c:       4       11----------------19
>   * builtin/blame.c:               12-13

This is a tangent, but I am not sure how much it buys us to keep
track of the information here in object.h, as all that picture says
is "revision traversal machinery given by revision.[ch] can never be
used inside fetch-pack and upload-pack", and that is already said by
the current picture that says fetch-pack.c uses 0 thru 4, and
updating it to say that we now use 0 thru 5 would not change the
conclusion.

What I am trying to get at is that we may want to (re)consider how
we manage these bits.  But that is totally outside the scope of this
series, and updating the above is the right thing to do here.

Thanks.

Re: [PATCH 07/12] fetch-pack: cache results of for_each_alternate_ref

[Jeff King]

On Wed, Jan 25, 2017 at 11:21:11AM -0800, Junio C Hamano wrote:

> > diff --git a/object.h b/object.h
> > index 614a00675..f52957dcb 100644
> > --- a/object.h
> > +++ b/object.h
> > @@ -29,7 +29,7 @@ struct object_array {
> >  /*
> >   * object flag allocation:
> >   * revision.h:      0---------10                                26
> > - * fetch-pack.c:    0---4
> > + * fetch-pack.c:    0---5
> >   * walker.c:        0-2
> >   * upload-pack.c:       4       11----------------19
> >   * builtin/blame.c:               12-13
> 
> This is a tangent, but I am not sure how much it buys us to keep
> track of the information here in object.h, as all that picture says
> is "revision traversal machinery given by revision.[ch] can never be
> used inside fetch-pack and upload-pack", and that is already said by
> the current picture that says fetch-pack.c uses 0 thru 4, and
> updating it to say that we now use 0 thru 5 would not change the
> conclusion.

I agree that bumping 4 to 5 does not help at all, given the current
allocations. But it could eventually, if another allocation wanted to
pick up 5, and might plausibly be used together with fetch-pack.

The main thing is that we should keep this up to date, and that it
should cause textual conflicts when two topics update the allocation, so
that a human looks at it. I actually think we fail at the latter,
because a change to revision.h to use bit 20 would probably get
auto-resolved against a change to allocate the same bit to blame.c.

Probably a better organization is:

  bit 0: revision.h, fetch-pack.c, walker.c
  bit 1: revision.h, fetch-pack.c, walker.c
  ...
  bit 10: revision.h
  bit 11: upload-pack.c

and so forth. It's more tedious to read and write, but any two changes
to the same bit would be forced to generate a conflict (assuming a
line-oriented merge, of course :) ).

> What I am trying to get at is that we may want to (re)consider how
> we manage these bits.  But that is totally outside the scope of this
> series, and updating the above is the right thing to do here.

Perhaps you meant something like the above when you said this. But what
I'd _really_ love is to stop using global bits entirely, and have some
way to allocate a bitset and efficiently convert "struct object" to an
index into the bitset. Then cleaning up just becomes throwing out your
bitset, and by default operations do not see the bits from other
unrelated operations. That makes it impossible to have bugs like the one
fixed by 5c08dc48a (checkout: clear commit marks after detached-orphan
check, 2011-03-20).

I can't think of a way to do that efficiently besides something like the
commit-slab system, but extended to all objects. The lookups there are
fairly cheap, though it does have worse cache performance. I don't know
if that would matter in practice or not.

But yeah, definitely outside the scope of this series. :)

-Peff

[PATCH 08/12] add oidset API

[Jeff King]

This is similar to many of our uses of sha1-array, but it
overcomes one limitation of a sha1-array: when you are
de-duplicating a large input with relatively few unique
entries, sha1-array uses 20 bytes per non-unique entry.
Whereas this set will use memory linear in the number of
unique entries (albeit a few more than 20 bytes due to
hashmap overhead).

Signed-off-by: Jeff King <peff@peff.net>
---
This may be overkill. You can get roughly the same thing by making
actual object structs via lookup_unknown_object(). But see the next
patch for some comments on that.

 Makefile |  1 +
 oidset.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 oidset.h | 45 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 95 insertions(+)
 create mode 100644 oidset.c
 create mode 100644 oidset.h

diff --git a/Makefile b/Makefile
index 27afd0f37..e41efc2d8 100644
--- a/Makefile
+++ b/Makefile
@@ -774,6 +774,7 @@ LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
 LIB_OBJS += notes-utils.o
 LIB_OBJS += object.o
+LIB_OBJS += oidset.o
 LIB_OBJS += pack-bitmap.o
 LIB_OBJS += pack-bitmap-write.o
 LIB_OBJS += pack-check.o
diff --git a/oidset.c b/oidset.c
new file mode 100644
index 000000000..6094cff8c
--- /dev/null
+++ b/oidset.c
@@ -0,0 +1,49 @@
+#include "cache.h"
+#include "oidset.h"
+
+struct oidset_entry {
+	struct hashmap_entry hash;
+	struct object_id oid;
+};
+
+int oidset_hashcmp(const void *va, const void *vb,
+			  const void *vkey)
+{
+	const struct oidset_entry *a = va, *b = vb;
+	const struct object_id *key = vkey;
+	return oidcmp(&a->oid, key ? key : &b->oid);
+}
+
+int oidset_contains(const struct oidset *set, const struct object_id *oid)
+{
+	struct hashmap_entry key;
+
+	if (!set->map.cmpfn)
+		return 0;
+
+	hashmap_entry_init(&key, sha1hash(oid->hash));
+	return !!hashmap_get(&set->map, &key, oid);
+}
+
+int oidset_insert(struct oidset *set, const struct object_id *oid)
+{
+	struct oidset_entry *entry;
+
+	if (!set->map.cmpfn)
+		hashmap_init(&set->map, oidset_hashcmp, 0);
+
+	if (oidset_contains(set, oid))
+		return 1;
+
+	entry = xmalloc(sizeof(*entry));
+	hashmap_entry_init(&entry->hash, sha1hash(oid->hash));
+	oidcpy(&entry->oid, oid);
+
+	hashmap_add(&set->map, entry);
+	return 0;
+}
+
+void oidset_clear(struct oidset *set)
+{
+	hashmap_free(&set->map, 1);
+}
diff --git a/oidset.h b/oidset.h
new file mode 100644
index 000000000..b7eaab5b8
--- /dev/null
+++ b/oidset.h
@@ -0,0 +1,45 @@
+#ifndef OIDSET_H
+#define OIDSET_H
+
+/**
+ * This API is similar to sha1-array, in that it maintains a set of object ids
+ * in a memory-efficient way. The major differences are:
+ *
+ *   1. It uses a hash, so we can do online duplicate removal, rather than
+ *      sort-and-uniq at the end. This can reduce memory footprint if you have
+ *      a large list of oids with many duplicates.
+ *
+ *   2. The per-unique-oid memory footprint is slightly higher due to hash
+ *      table overhead.
+ */
+
+/**
+ * A single oidset; should be zero-initialized (or use OIDSET_INIT).
+ */
+struct oidset {
+	struct hashmap map;
+};
+
+#define OIDSET_INIT { { NULL } }
+
+/**
+ * Returns true iff `set` contains `oid`.
+ */
+int oidset_contains(const struct oidset *set, const struct object_id *oid);
+
+/**
+ * Insert the oid into the set; a copy is made, so "oid" does not need
+ * to persist after this function is called.
+ *
+ * Returns 1 if the oid was already in the set, 0 otherwise. This can be used
+ * to perform an efficient check-and-add.
+ */
+int oidset_insert(struct oidset *set, const struct object_id *oid);
+
+/**
+ * Remove all entries from the oidset, freeing any resources associated with
+ * it.
+ */
+void oidset_clear(struct oidset *set);
+
+#endif /* OIDSET_H */
-- 
2.11.0.765.g454d2182f

Re: [PATCH 08/12] add oidset API

[Ramsay Jones]

On 24/01/17 00:46, Jeff King wrote:
> This is similar to many of our uses of sha1-array, but it
> overcomes one limitation of a sha1-array: when you are
> de-duplicating a large input with relatively few unique
> entries, sha1-array uses 20 bytes per non-unique entry.
> Whereas this set will use memory linear in the number of
> unique entries (albeit a few more than 20 bytes due to
> hashmap overhead).
> 
> Signed-off-by: Jeff King <peff@peff.net>
> ---
> This may be overkill. You can get roughly the same thing by making
> actual object structs via lookup_unknown_object(). But see the next
> patch for some comments on that.
> 
>  Makefile |  1 +
>  oidset.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
>  oidset.h | 45 +++++++++++++++++++++++++++++++++++++++++++++
>  3 files changed, 95 insertions(+)
>  create mode 100644 oidset.c
>  create mode 100644 oidset.h
> 
> diff --git a/Makefile b/Makefile
> index 27afd0f37..e41efc2d8 100644
> --- a/Makefile
> +++ b/Makefile
> @@ -774,6 +774,7 @@ LIB_OBJS += notes-cache.o
>  LIB_OBJS += notes-merge.o
>  LIB_OBJS += notes-utils.o
>  LIB_OBJS += object.o
> +LIB_OBJS += oidset.o
>  LIB_OBJS += pack-bitmap.o
>  LIB_OBJS += pack-bitmap-write.o
>  LIB_OBJS += pack-check.o
> diff --git a/oidset.c b/oidset.c
> new file mode 100644
> index 000000000..6094cff8c
> --- /dev/null
> +++ b/oidset.c
> @@ -0,0 +1,49 @@
> +#include "cache.h"
> +#include "oidset.h"
> +
> +struct oidset_entry {
> +	struct hashmap_entry hash;
> +	struct object_id oid;
> +};
> +
> +int oidset_hashcmp(const void *va, const void *vb,

static int oidset_hashcmp( ...

ATB,
Ramsay Jones

Re: [PATCH 08/12] add oidset API

[Jeff King]

On Tue, Jan 24, 2017 at 08:26:40PM +0000, Ramsay Jones wrote:

> > +++ b/oidset.c
> > @@ -0,0 +1,49 @@
> > +#include "cache.h"
> > +#include "oidset.h"
> > +
> > +struct oidset_entry {
> > +	struct hashmap_entry hash;
> > +	struct object_id oid;
> > +};
> > +
> > +int oidset_hashcmp(const void *va, const void *vb,
> 
> static int oidset_hashcmp( ...

Yep, thanks.

-Peff

[PATCH 09/12] receive-pack: use oidset to de-duplicate .have lines

[Jeff King]

If you have an alternate object store with a very large
number of refs, the peak memory usage of the sha1_array can
grow high, even if most of them are duplicates that end up
not being printed at all.

The similar for_each_alternate_ref() code-paths in
fetch-pack solve this by using flags in "struct object" to
de-duplicate (and so are relying on obj_hash at the core).

But we don't have a "struct object" at all in this case. We
could call lookup_unknown_object() to get one, but if our
goal is reducing memory footprint, it's not great:

 - an unknown object is as large as the largest object type
   (a commit), which is bigger than an oidset entry

 - we can free the memory after our ref advertisement, but
   "struct object" entries persist forever (and the
   receive-pack may hang around for a long time, as the
   bottleneck is often client upload bandwidth).

So let's use an oidset. Note that unlike a sha1-array it
doesn't sort the output as a side effect. However, our
output is at least stable, because for_each_alternate_ref()
will give us the sha1s in ref-sorted order.

In one particularly pathological case with an alternate that
has 60,000 unique refs out of 80 million total, this reduced
the peak heap usage of "git receive-pack . </dev/null" from
13GB to 14MB.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 26 ++++++++++++--------------
 1 file changed, 12 insertions(+), 14 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index b9f2c0cc5..27bb52988 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -21,6 +21,7 @@
 #include "sigchain.h"
 #include "fsck.h"
 #include "tmp-objdir.h"
+#include "oidset.h"
 
 static const char * const receive_pack_usage[] = {
 	N_("git receive-pack <git-dir>"),
@@ -271,27 +272,24 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	return 0;
 }
 
-static int show_one_alternate_sha1(const unsigned char sha1[20], void *unused)
+static void show_one_alternate_ref(const char *refname,
+				   const struct object_id *oid,
+				   void *data)
 {
-	show_ref(".have", sha1);
-	return 0;
-}
+	struct oidset *seen = data;
 
-static void collect_one_alternate_ref(const char *refname,
-				      const struct object_id *oid,
-				      void *data)
-{
-	struct sha1_array *sa = data;
-	sha1_array_append(sa, oid->hash);
+	if (oidset_insert(seen, oid))
+		return;
+
+	show_ref(".have", oid->hash);
 }
 
 static void write_head_info(void)
 {
-	struct sha1_array sa = SHA1_ARRAY_INIT;
+	static struct oidset seen = OIDSET_INIT;
 
-	for_each_alternate_ref(collect_one_alternate_ref, &sa);
-	sha1_array_for_each_unique(&sa, show_one_alternate_sha1, NULL);
-	sha1_array_clear(&sa);
+	for_each_alternate_ref(show_one_alternate_ref, &seen);
+	oidset_clear(&seen);
 	for_each_ref(show_ref_cb, NULL);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
-- 
2.11.0.765.g454d2182f

Re: [PATCH 09/12] receive-pack: use oidset to de-duplicate .have lines

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> If you have an alternate object store with a very large
> number of refs, the peak memory usage of the sha1_array can
> grow high, even if most of them are duplicates that end up
> not being printed at all.
> ...
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  builtin/receive-pack.c | 26 ++++++++++++--------------
>  1 file changed, 12 insertions(+), 14 deletions(-)

Nice.  

Incidentally, this also shows that the refnames in alternate ref
namespace will not matter.  We are to only show just one of many
anyway (and that name is masked and replaced with ".have").  Perhaps
we want to do 04/12 without refname?

> diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
> index b9f2c0cc5..27bb52988 100644
> --- a/builtin/receive-pack.c
> +++ b/builtin/receive-pack.c
> @@ -21,6 +21,7 @@
>  #include "sigchain.h"
>  #include "fsck.h"
>  #include "tmp-objdir.h"
> +#include "oidset.h"
>  
>  static const char * const receive_pack_usage[] = {
>  	N_("git receive-pack <git-dir>"),
> @@ -271,27 +272,24 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
>  	return 0;
>  }
>  
> -static int show_one_alternate_sha1(const unsigned char sha1[20], void *unused)
> +static void show_one_alternate_ref(const char *refname,
> +				   const struct object_id *oid,
> +				   void *data)
>  {
> -	show_ref(".have", sha1);
> -	return 0;
> -}
> +	struct oidset *seen = data;
>  
> -static void collect_one_alternate_ref(const char *refname,
> -				      const struct object_id *oid,
> -				      void *data)
> -{
> -	struct sha1_array *sa = data;
> -	sha1_array_append(sa, oid->hash);
> +	if (oidset_insert(seen, oid))
> +		return;
> +
> +	show_ref(".have", oid->hash);
>  }
>  
>  static void write_head_info(void)
>  {
> -	struct sha1_array sa = SHA1_ARRAY_INIT;
> +	static struct oidset seen = OIDSET_INIT;
>  
> -	for_each_alternate_ref(collect_one_alternate_ref, &sa);
> -	sha1_array_for_each_unique(&sa, show_one_alternate_sha1, NULL);
> -	sha1_array_clear(&sa);
> +	for_each_alternate_ref(show_one_alternate_ref, &seen);
> +	oidset_clear(&seen);
>  	for_each_ref(show_ref_cb, NULL);
>  	if (!sent_capabilities)
>  		show_ref("capabilities^{}", null_sha1);

Re: [PATCH 09/12] receive-pack: use oidset to de-duplicate .have lines

[Jeff King]

On Wed, Jan 25, 2017 at 11:32:05AM -0800, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > If you have an alternate object store with a very large
> > number of refs, the peak memory usage of the sha1_array can
> > grow high, even if most of them are duplicates that end up
> > not being printed at all.
> > ...
> > Signed-off-by: Jeff King <peff@peff.net>
> > ---
> >  builtin/receive-pack.c | 26 ++++++++++++--------------
> >  1 file changed, 12 insertions(+), 14 deletions(-)
> 
> Nice.  
> 
> Incidentally, this also shows that the refnames in alternate ref
> namespace will not matter.  We are to only show just one of many
> anyway (and that name is masked and replaced with ".have").  Perhaps
> we want to do 04/12 without refname?

I kept the refnames there as a "plausible" thing that a callback might
want. But I have ulterior motives. :)

I have another series which uses alternate refs as part of
check_connected(). Since that function calls rev-list, it needs to add
something like "rev-list --alternate-refs". Even check_connected() does
not care about the refnames, it seems like that rev-list option should
have some useful name for each ref. It can make things like "--source"
more sensible, instead of just reporting everything as a blank ".have".

I could be persuaded otherwise, though.  I don't think we pay a huge for
the refnames here. The generating for-each-ref has them either way, and
the receiving side only keeps one in memory at a time. So we are really
only paying to send them across the pipe and parse them, which doesn't
seem extravagant. I didn't actually measure it, though.

-Peff

[PATCH 10/12] receive-pack: fix misleading namespace/.have comment

[Jeff King]

The comment claims that we handle alternate ".have" lines
through this function, but that hasn't been the case since
85f251045 (write_head_info(): handle "extra refs" locally,
2012-01-06).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 27bb52988..8f8762e4a 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -261,10 +261,7 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	/*
 	 * Advertise refs outside our current namespace as ".have"
 	 * refs, so that the client can use them to minimize data
-	 * transfer but will otherwise ignore them. This happens to
-	 * cover ".have" that are thrown in by add_one_alternate_ref()
-	 * to mark histories that are complete in our alternates as
-	 * well.
+	 * transfer but will otherwise ignore them.
 	 */
 	if (!path)
 		path = ".have";
-- 
2.11.0.765.g454d2182f

[PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Jeff King]

Namely, de-duplicate them. We use the same set as the
alternates, since we call them both ".have" (i.e., there is
no value in showing one versus the other).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 8f8762e4a..c55e2f993 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -251,8 +251,9 @@ static void show_ref(const char *path, const unsigned char *sha1)
 }
 
 static int show_ref_cb(const char *path_full, const struct object_id *oid,
-		       int flag, void *unused)
+		       int flag, void *data)
 {
+	struct oidset *seen = data;
 	const char *path = strip_namespace(path_full);
 
 	if (ref_is_hidden(path, path_full))
@@ -263,8 +264,11 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	 * refs, so that the client can use them to minimize data
 	 * transfer but will otherwise ignore them.
 	 */
-	if (!path)
+	if (!path) {
+		if (oidset_insert(seen, oid))
+			return 0;
 		path = ".have";
+	}
 	show_ref(path, oid->hash);
 	return 0;
 }
@@ -287,7 +291,7 @@ static void write_head_info(void)
 
 	for_each_alternate_ref(show_one_alternate_ref, &seen);
 	oidset_clear(&seen);
-	for_each_ref(show_ref_cb, NULL);
+	for_each_ref(show_ref_cb, &seen);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
 
-- 
2.11.0.765.g454d2182f

Re: [PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Namely, de-duplicate them. We use the same set as the
> alternates, since we call them both ".have" (i.e., there is
> no value in showing one versus the other).
>
> Signed-off-by: Jeff King <peff@peff.net>
> ---
>  builtin/receive-pack.c | 10 +++++++---
>  1 file changed, 7 insertions(+), 3 deletions(-)
>
> diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
> index 8f8762e4a..c55e2f993 100644
> --- a/builtin/receive-pack.c
> +++ b/builtin/receive-pack.c
> @@ -251,8 +251,9 @@ static void show_ref(const char *path, const unsigned char *sha1)
>  }
>  
>  static int show_ref_cb(const char *path_full, const struct object_id *oid,
> -		       int flag, void *unused)
> +		       int flag, void *data)
>  {
> +	struct oidset *seen = data;
>  	const char *path = strip_namespace(path_full);
>  
>  	if (ref_is_hidden(path, path_full))
> @@ -263,8 +264,11 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
>  	 * refs, so that the client can use them to minimize data
>  	 * transfer but will otherwise ignore them.
>  	 */
> -	if (!path)
> +	if (!path) {
> +		if (oidset_insert(seen, oid))
> +			return 0;
>  		path = ".have";
> +	}

This is very sensible as an optimization that does not change
semantics.

This is an unrelated tangent, but there may want to be a knob to
make the code return here without even showing, to make the
advertisement even smaller and also to stop miniscule information
leakage?  If the namespaced multiple projects are totally unrelated
(i.e. "My sysadmin gave me a write access only to this single
directory, so I am using the namespace feature to host these three
projects that have nothing to do with each other"), showing objects
of other namespaces will buy us nothing and the user is better off
without this code showing these refs as ".have".

>  	show_ref(path, oid->hash);
>  	return 0;
>  }
> @@ -287,7 +291,7 @@ static void write_head_info(void)
>  
>  	for_each_alternate_ref(show_one_alternate_ref, &seen);
>  	oidset_clear(&seen);
> -	for_each_ref(show_ref_cb, NULL);
> +	for_each_ref(show_ref_cb, &seen);
>  	if (!sent_capabilities)
>  		show_ref("capabilities^{}", null_sha1);

Re: [PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Jeff King]

On Wed, Jan 25, 2017 at 11:51:17AM -0800, Junio C Hamano wrote:

> This is an unrelated tangent, but there may want to be a knob to
> make the code return here without even showing, to make the
> advertisement even smaller and also to stop miniscule information
> leakage?  If the namespaced multiple projects are totally unrelated
> (i.e. "My sysadmin gave me a write access only to this single
> directory, so I am using the namespace feature to host these three
> projects that have nothing to do with each other"), showing objects
> of other namespaces will buy us nothing and the user is better off
> without this code showing these refs as ".have".

Yeah, I'd agree it's a potential issue. And I definitely do the same
with alternates (in my case it isn't "they're not relevant" as much as
"they are too big, and the optimization backfires").

I don't use namespaces myself[1], though, so I'd prefer to leave that to
somebody who has that itch, and could think it through better.

-Peff

[1] They _seem_ like they'd be a good fit for the way GitHub uses
    alternates, but since they're only implemented for fetch/push,
    they're only a small part of the story. Plus the ref storage has
    traditionally been a scaling bottleneck for us, so it's nice for
    each fork to have its own ref storage for operations that just touch
    that fork.

Re: [PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Lukas Fleischer]

On Wed, 25 Jan 2017 at 20:51:17, Junio C Hamano wrote:
> [...]
> > diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
> > index 8f8762e4a..c55e2f993 100644
> > --- a/builtin/receive-pack.c
> > +++ b/builtin/receive-pack.c
> > @@ -251,8 +251,9 @@ static void show_ref(const char *path, const unsigned char *sha1)
> [...]
> >       if (ref_is_hidden(path, path_full))
> [...]
> This is an unrelated tangent, but there may want to be a knob to
> make the code return here without even showing, to make the
> advertisement even smaller and also to stop miniscule information
> leakage?  If the namespaced multiple projects are totally unrelated
> (i.e. "My sysadmin gave me a write access only to this single
> directory, so I am using the namespace feature to host these three
> projects that have nothing to do with each other"), showing objects
> of other namespaces will buy us nothing and the user is better off
> without this code showing these refs as ".have".

I think this is already possible using receive.hideRefs (which causes
the ref_is_hidden() branch above to return if applicable).

Having support for suppressing .have lines corresponding to different
namespaces was actually the reason I implemented 78a766ab6 (hideRefs:
add support for matching full refs, 2015-11-03). We have been using
namespaces for hosting the package Git repositories of the Arch Linux
User Repository [1] with a shared object storage for several months now.
See [2] for *some* technical details on how things are implemented; the
last section explains how the hideRefs mechanism can be used to limit
ref advertisement to the "active" namespace.

Regards,
Lukas

[1] https://aur.archlinux.org/
[2] https://git.archlinux.org/aurweb.git/plain/doc/git-interface.txt

Re: [PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Jeff King]

On Fri, Jan 27, 2017 at 06:45:26PM +0100, Lukas Fleischer wrote:

> > This is an unrelated tangent, but there may want to be a knob to
> > make the code return here without even showing, to make the
> > advertisement even smaller and also to stop miniscule information
> > leakage?  If the namespaced multiple projects are totally unrelated
> > (i.e. "My sysadmin gave me a write access only to this single
> > directory, so I am using the namespace feature to host these three
> > projects that have nothing to do with each other"), showing objects
> > of other namespaces will buy us nothing and the user is better off
> > without this code showing these refs as ".have".
> 
> I think this is already possible using receive.hideRefs (which causes
> the ref_is_hidden() branch above to return if applicable).
> 
> Having support for suppressing .have lines corresponding to different
> namespaces was actually the reason I implemented 78a766ab6 (hideRefs:
> add support for matching full refs, 2015-11-03). We have been using
> namespaces for hosting the package Git repositories of the Arch Linux
> User Repository [1] with a shared object storage for several months now.
> See [2] for *some* technical details on how things are implemented; the
> last section explains how the hideRefs mechanism can be used to limit
> ref advertisement to the "active" namespace.

Thanks for the pointers. I think a "turn off namespace .have lines"
option would be easier for some cases, but what you've implemented is
much more flexible. So if people using namespaces are happy with it, I
don't see any need to add another way to do the same thing.

-Peff

Re: [PATCH 11/12] receive-pack: treat namespace .have lines like alternates

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Fri, Jan 27, 2017 at 06:45:26PM +0100, Lukas Fleischer wrote:
>
>> I think this is already possible using receive.hideRefs (which causes
>> the ref_is_hidden() branch above to return if applicable).
>> ...
>
> Thanks for the pointers. I think a "turn off namespace .have lines"
> option would be easier for some cases, but what you've implemented is
> much more flexible. So if people using namespaces are happy with it, I
> don't see any need to add another way to do the same thing.

Yeah, I agree.  Thanks, both.

[PATCH 12/12] receive-pack: avoid duplicates between our refs and alternates

[Jeff King]

We de-duplicate ".have" refs among themselves, but never
check if they are duplicates of our local refs. It's not
unreasonable that they would be if we are a "--shared" or
"--reference" clone of a similar repository; we'd have all
the same tags.

We can handle this by inserting our local refs into the
oidset, but obviously not suppressing duplicates (since the
refnames are important).

Note that this also switches the order in which we advertise
refs, processing ours first and then any alternates. The
order shouldn't matter (and arguably showing our refs first
makes more sense).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c |  4 +++-
 t/t5400-send-pack.sh   | 38 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+), 1 deletion(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index c55e2f993..bc7ce0ea2 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -268,6 +268,8 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 		if (oidset_insert(seen, oid))
 			return 0;
 		path = ".have";
+	} else {
+		oidset_insert(seen, oid);
 	}
 	show_ref(path, oid->hash);
 	return 0;
@@ -289,9 +291,9 @@ static void write_head_info(void)
 {
 	static struct oidset seen = OIDSET_INIT;
 
+	for_each_ref(show_ref_cb, &seen);
 	for_each_alternate_ref(show_one_alternate_ref, &seen);
 	oidset_clear(&seen);
-	for_each_ref(show_ref_cb, &seen);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
 
diff --git a/t/t5400-send-pack.sh b/t/t5400-send-pack.sh
index 305ca7a93..3331e0f53 100755
--- a/t/t5400-send-pack.sh
+++ b/t/t5400-send-pack.sh
@@ -255,4 +255,42 @@ test_expect_success 'deny pushing to delete current branch' '
 	)
 '
 
+extract_ref_advertisement () {
+	perl -lne '
+		# \\ is there to skip capabilities after \0
+		/push< ([^\\]+)/ or next;
+		exit 0 if $1 eq "0000";
+		print $1;
+	'
+}
+
+test_expect_success 'receive-pack de-dupes .have lines' '
+	git init shared &&
+	git -C shared commit --allow-empty -m both &&
+	git clone -s shared fork &&
+	(
+		cd shared &&
+		git checkout -b only-shared &&
+		git commit --allow-empty -m only-shared &&
+		git update-ref refs/heads/foo HEAD
+	) &&
+
+	# Notable things in this expectation:
+	#  - local refs are not de-duped
+	#  - .have does not duplicate locals
+	#  - .have does not duplicate itself
+	local=$(git -C fork rev-parse HEAD) &&
+	shared=$(git -C shared rev-parse only-shared) &&
+	cat >expect <<-EOF &&
+	$local refs/heads/master
+	$local refs/remotes/origin/HEAD
+	$local refs/remotes/origin/master
+	$shared .have
+	EOF
+
+	GIT_TRACE_PACKET=$(pwd)/trace git push fork HEAD:foo &&
+	extract_ref_advertisement <trace >refs &&
+	test_cmp expect refs
+'
+
 test_done
-- 
2.11.0.765.g454d2182f

Re: [PATCH 12/12] receive-pack: avoid duplicates between our refs and alternates

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> We de-duplicate ".have" refs among themselves, but never
> check if they are duplicates of our local refs. It's not
> unreasonable that they would be if we are a "--shared" or
> "--reference" clone of a similar repository; we'd have all
> the same tags.
>
> We can handle this by inserting our local refs into the
> oidset, but obviously not suppressing duplicates (since the
> refnames are important).

Makes sense.

> +extract_ref_advertisement () {
> +	perl -lne '
> +		# \\ is there to skip capabilities after \0
> +		/push< ([^\\]+)/ or next;
> +		exit 0 if $1 eq "0000";
> +		print $1;
> +	'

Parsing TRACE_PACKET output?  Yuck.  But I think this has to do, as
any other solution will bound to be uglier.

> +test_expect_success 'receive-pack de-dupes .have lines' '
> +	git init shared &&
> +	git -C shared commit --allow-empty -m both &&
> +	git clone -s shared fork &&
> +	(
> +		cd shared &&
> +		git checkout -b only-shared &&
> +		git commit --allow-empty -m only-shared &&
> +		git update-ref refs/heads/foo HEAD
> +	) &&
> +
> +	# Notable things in this expectation:
> +	#  - local refs are not de-duped
> +	#  - .have does not duplicate locals
> +	#  - .have does not duplicate itself
> +	local=$(git -C fork rev-parse HEAD) &&
> +	shared=$(git -C shared rev-parse only-shared) &&
> +	cat >expect <<-EOF &&
> +	$local refs/heads/master
> +	$local refs/remotes/origin/HEAD
> +	$local refs/remotes/origin/master
> +	$shared .have
> +	EOF

We may want to sort this thing and the extracted one when comparing;
the order of the entries is not part of the feature we cast in stone.

> +
> +	GIT_TRACE_PACKET=$(pwd)/trace git push fork HEAD:foo &&
> +	extract_ref_advertisement <trace >refs &&
> +	test_cmp expect refs
> +'
> +
>  test_done

Re: [PATCH 12/12] receive-pack: avoid duplicates between our refs and alternates

[Jeff King]

On Wed, Jan 25, 2017 at 12:02:30PM -0800, Junio C Hamano wrote:

> > +extract_ref_advertisement () {
> > +	perl -lne '
> > +		# \\ is there to skip capabilities after \0
> > +		/push< ([^\\]+)/ or next;
> > +		exit 0 if $1 eq "0000";
> > +		print $1;
> > +	'
> 
> Parsing TRACE_PACKET output?  Yuck.  But I think this has to do, as
> any other solution will bound to be uglier.

Agreed. My initial attempt was to just run "git receive-pack </dev/null"
and parse the advertisement. But then you have to parse pktlines. :)

> > +	# Notable things in this expectation:
> > +	#  - local refs are not de-duped
> > +	#  - .have does not duplicate locals
> > +	#  - .have does not duplicate itself
> > +	local=$(git -C fork rev-parse HEAD) &&
> > +	shared=$(git -C shared rev-parse only-shared) &&
> > +	cat >expect <<-EOF &&
> > +	$local refs/heads/master
> > +	$local refs/remotes/origin/HEAD
> > +	$local refs/remotes/origin/master
> > +	$shared .have
> > +	EOF
> 
> We may want to sort this thing and the extracted one when comparing;
> the order of the entries is not part of the feature we cast in stone.

True (and in fact the .have moved in the previous patch). I wondered,
though, if it might not be a reasonable thing for somebody to have to
look at the output and verify it when the order _does_ change.

I dunno.

-Peff

Re: [PATCH 0/12] reducing resource usage of for_each_alternate_ref

[Brandon Williams]

On 01/23, Jeff King wrote:
> 
> A brief overview of the patches:
> 
>   [01/12]: for_each_alternate_ref: handle failure from real_pathdup()
>   [02/12]: for_each_alternate_ref: stop trimming trailing slashes
>   [03/12]: for_each_alternate_ref: use strbuf for path allocation
> 
>     Bugfixes and cleanups (the first one is actually a recent-ish
>     regression).

Which is most likely my fault, Sorry! :)

I think the old behavior was to die and not return NULL.

-- 
Brandon Williams

Re: [PATCH 0/12] reducing resource usage of for_each_alternate_ref

[Jeff King]

On Mon, Jan 23, 2017 at 05:33:41PM -0800, Brandon Williams wrote:

> On 01/23, Jeff King wrote:
> > 
> > A brief overview of the patches:
> > 
> >   [01/12]: for_each_alternate_ref: handle failure from real_pathdup()
> >   [02/12]: for_each_alternate_ref: stop trimming trailing slashes
> >   [03/12]: for_each_alternate_ref: use strbuf for path allocation
> > 
> >     Bugfixes and cleanups (the first one is actually a recent-ish
> >     regression).
> 
> Which is most likely my fault, Sorry! :)
> 
> I think the old behavior was to die and not return NULL.

Yes, it is. :)

But I think it's probably pretty hard to trigger in practice. And on the
plus side, I think the new behavior after my patch is much more sensible
than even the original.

-Peff

[PATCH v2 0/11] reducing resource usage of for_each_alternate_ref

[Jeff King]

This is a minor re-roll of the patches from:

  http://public-inbox.org/git/20170124003729.j4ygjcgypdq7hceg@sigill.intra.peff.net/

(which got some review, but I don't think was picked up for even 'pu').

I won't repeat the numbers and background from that message, but the
gist of it is that this reduces memory usage significantly when your
alternate has a lot of refs in it.

This version makes two minor changes:

  - it drops the save_commit_buffer patch to clone; it's redundant with
    what fetch_pack() is doing internally, and I wasn't able to measure
    any improvement

  - it adds a missing "static" to an internal function

The only other possible change from the review would be sorting the
expected output in the test of the final script. I'm on the fence
whether it is a feature that we expect a particular ordering. It's not
set in stone ,but it _is_ deterministic, and if we change the order, it
might be worth somebody actually noticing.

  [01/11]: for_each_alternate_ref: handle failure from real_pathdup()
  [02/11]: for_each_alternate_ref: stop trimming trailing slashes
  [03/11]: for_each_alternate_ref: use strbuf for path allocation
  [04/11]: for_each_alternate_ref: pass name/oid instead of ref struct
  [05/11]: for_each_alternate_ref: replace transport code with for-each-ref
  [06/11]: fetch-pack: cache results of for_each_alternate_ref
  [07/11]: add oidset API
  [08/11]: receive-pack: use oidset to de-duplicate .have lines
  [09/11]: receive-pack: fix misleading namespace/.have comment
  [10/11]: receive-pack: treat namespace .have lines like alternates
  [11/11]: receive-pack: avoid duplicates between our refs and alternates

 Makefile               |  1 +
 builtin/receive-pack.c | 41 +++++++++++++++-------------
 fetch-pack.c           | 48 ++++++++++++++++++++++++++++-----
 object.h               |  2 +-
 oidset.c               | 49 ++++++++++++++++++++++++++++++++++
 oidset.h               | 45 +++++++++++++++++++++++++++++++
 t/t5400-send-pack.sh   | 38 ++++++++++++++++++++++++++
 transport.c            | 72 +++++++++++++++++++++++++++++++++++---------------
 transport.h            |  2 +-
 9 files changed, 249 insertions(+), 49 deletions(-)
 create mode 100644 oidset.c
 create mode 100644 oidset.h

[PATCH v2 01/11] for_each_alternate_ref: handle failure from real_pathdup()

[Jeff King]

In older versions of git, if real_path() failed to resolve
the alternate object store path, we would die() with an
error. However, since 4ac9006f8 (real_path: have callers use
real_pathdup and strbuf_realpath, 2016-12-12) we use the
real_pathdup() function, which may return NULL. Since we
don't check the return value, we can segfault.

This is hard to trigger in practice, since we check that the
path is accessible before creating the alternate_object_database
struct. But it could be removed racily, or we could see a
transient filesystem error.

We could restore the original behavior by switching back to
xstrdup(real_path()).  However, dying is probably not the
best option here. This whole function is best-effort
already; there might not even be a repository around the
shared objects at all. And if the alternate store has gone
away, there are no objects to show.

So let's just quietly return, as we would if we failed to
open "refs/", or if upload-pack failed to start, etc.

Signed-off-by: Jeff King <peff@peff.net>
---
 transport.c | 2 ++
 1 file changed, 2 insertions(+)

diff --git a/transport.c b/transport.c
index d72e08948..9ce0ee96b 100644
--- a/transport.c
+++ b/transport.c
@@ -1222,6 +1222,8 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 	struct alternate_refs_data *cb = data;
 
 	other = real_pathdup(e->path);
+	if (!other)
+		return 0;
 	len = strlen(other);
 
 	while (other[len-1] == '/')
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 02/11] for_each_alternate_ref: stop trimming trailing slashes

[Jeff King]

The real_pathdup() function will have removed extra slashes
for us already (on top of the normalize_path() done when we
created the alternate_object_database struct in the first
place).

Incidentally, this also fixes the case where the path is
just "/", which would read off the start of the array.
That doesn't seem possible to trigger in practice, though,
as link_alt_odb_entry() blindly eats trailing slashes,
including a bare "/".

Signed-off-by: Jeff King <peff@peff.net>
---
 transport.c | 2 --
 1 file changed, 2 deletions(-)

diff --git a/transport.c b/transport.c
index 9ce0ee96b..6fba9e95b 100644
--- a/transport.c
+++ b/transport.c
@@ -1226,8 +1226,6 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 		return 0;
 	len = strlen(other);
 
-	while (other[len-1] == '/')
-		other[--len] = '\0';
 	if (len < 8 || memcmp(other + len - 8, "/objects", 8))
 		goto out;
 	/* Is this a git repository with refs? */
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 03/11] for_each_alternate_ref: use strbuf for path allocation

[Jeff King]

We have a string with ".../objects" pointing to the
alternate object store, and overwrite bits of it to look at
other paths in the (potential) git repository holding it.
This works because the only path we care about is "refs",
which is shorter than "objects".

Using a strbuf to hold the path lets us get rid of some
magic numbers, and makes it more obvious that the memory
operations are safe.

Signed-off-by: Jeff King <peff@peff.net>
---
 transport.c | 28 ++++++++++++++--------------
 1 file changed, 14 insertions(+), 14 deletions(-)

diff --git a/transport.c b/transport.c
index 6fba9e95b..6b7847131 100644
--- a/transport.c
+++ b/transport.c
@@ -1214,34 +1214,34 @@ struct alternate_refs_data {
 static int refs_from_alternate_cb(struct alternate_object_database *e,
 				  void *data)
 {
-	char *other;
-	size_t len;
+	struct strbuf path = STRBUF_INIT;
+	size_t base_len;
 	struct remote *remote;
 	struct transport *transport;
 	const struct ref *extra;
 	struct alternate_refs_data *cb = data;
 
-	other = real_pathdup(e->path);
-	if (!other)
-		return 0;
-	len = strlen(other);
-
-	if (len < 8 || memcmp(other + len - 8, "/objects", 8))
+	if (!strbuf_realpath(&path, e->path, 0))
+		goto out;
+	if (!strbuf_strip_suffix(&path, "/objects"))
 		goto out;
+	base_len = path.len;
+
 	/* Is this a git repository with refs? */
-	memcpy(other + len - 8, "/refs", 6);
-	if (!is_directory(other))
+	strbuf_addstr(&path, "/refs");
+	if (!is_directory(path.buf))
 		goto out;
-	other[len - 8] = '\0';
-	remote = remote_get(other);
-	transport = transport_get(remote, other);
+	strbuf_setlen(&path, base_len);
+
+	remote = remote_get(path.buf);
+	transport = transport_get(remote, path.buf);
 	for (extra = transport_get_remote_refs(transport);
 	     extra;
 	     extra = extra->next)
 		cb->fn(extra, cb->data);
 	transport_disconnect(transport);
 out:
-	free(other);
+	strbuf_release(&path);
 	return 0;
 }
 
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 04/11] for_each_alternate_ref: pass name/oid instead of ref struct

[Jeff King]

Breaking down the fields in the interface makes it easier to
change the backend of for_each_alternate_ref to something
that doesn't use "struct ref" internally.

The only field that callers actually look at is the oid,
anyway. The refname is kept in the interface as a plausible
thing for future code to want.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c |  6 ++++--
 fetch-pack.c           | 12 ++++++++----
 transport.c            |  2 +-
 transport.h            |  2 +-
 4 files changed, 14 insertions(+), 8 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 1dbb8a069..d21332d9e 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -277,10 +277,12 @@ static int show_one_alternate_sha1(const unsigned char sha1[20], void *unused)
 	return 0;
 }
 
-static void collect_one_alternate_ref(const struct ref *ref, void *data)
+static void collect_one_alternate_ref(const char *refname,
+				      const struct object_id *oid,
+				      void *data)
 {
 	struct sha1_array *sa = data;
-	sha1_array_append(sa, ref->old_oid.hash);
+	sha1_array_append(sa, oid->hash);
 }
 
 static void write_head_info(void)
diff --git a/fetch-pack.c b/fetch-pack.c
index 601f0779a..54f84c573 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -253,9 +253,11 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_ref(const struct ref *ref, void *unused)
+static void insert_one_alternate_ref(const char *refname,
+				     const struct object_id *oid,
+				     void *unused)
 {
-	rev_list_insert_ref(NULL, ref->old_oid.hash);
+	rev_list_insert_ref(NULL, oid->hash);
 }
 
 #define INITIAL_FLUSH 16
@@ -619,9 +621,11 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(const struct ref *ref, void *unused)
+static void mark_alternate_complete(const char *refname,
+				    const struct object_id *oid,
+				    void *unused)
 {
-	mark_complete(ref->old_oid.hash);
+	mark_complete(oid->hash);
 }
 
 static int everything_local(struct fetch_pack_args *args,
diff --git a/transport.c b/transport.c
index 6b7847131..c87147046 100644
--- a/transport.c
+++ b/transport.c
@@ -1238,7 +1238,7 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 	for (extra = transport_get_remote_refs(transport);
 	     extra;
 	     extra = extra->next)
-		cb->fn(extra, cb->data);
+		cb->fn(extra->name, &extra->old_oid, cb->data);
 	transport_disconnect(transport);
 out:
 	strbuf_release(&path);
diff --git a/transport.h b/transport.h
index e597b31b3..bc5571574 100644
--- a/transport.h
+++ b/transport.h
@@ -255,6 +255,6 @@ int transport_refs_pushed(struct ref *ref);
 void transport_print_push_status(const char *dest, struct ref *refs,
 		  int verbose, int porcelain, unsigned int *reject_reasons);
 
-typedef void alternate_ref_fn(const struct ref *, void *);
+typedef void alternate_ref_fn(const char *refname, const struct object_id *oid, void *);
 extern void for_each_alternate_ref(alternate_ref_fn, void *);
 #endif
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 05/11] for_each_alternate_ref: replace transport code with for-each-ref

[Jeff King]

The current method for getting the refs from an alternate is
to run upload-pack in the alternate and parse its output
using the normal transport code.  This works and is
reasonably short, but it has a very bad memory footprint
when there are a lot of refs in the alternate. There are two
problems:

  1. It reads in all of the refs before passing any back to
     us. Which means that our peak memory usage has to store
     every ref (including duplicates for peeled variants),
     even if our callback could determine that some are not
     interesting (e.g., because they point to the same sha1
     as another ref).

  2. It allocates a "struct ref" for each one. Among other
     things, this contains 3 separate 20-byte oids, along
     with the name and various pointers.  That can add up,
     especially if the callback is only interested in the
     sha1 (which it can store in a sha1_array as just 20
     bytes).

On a particularly pathological case, where the alternate had
over 80 million refs pointing to only around 60,000 unique
objects, the peak heap usage of "git clone --reference" grew
to over 25GB.

This patch instead calls git-for-each-ref in the alternate
repository, and passes each line to the callback as we read
it. That drops the peak heap of the same command to 50MB.

I considered and rejected a few alternatives.

We could read all of the refs in the alternate using our own
ref code, just as we do with submodules.  However, as memory
footprint is one of the concerns here, we want to avoid
loading those refs into our own memory as a whole.

It's possible that this will be a better technique in the
future when the ref code can more easily iterate without
loading all of packed-refs into memory.

Another option is to keep calling upload-pack, and just
parse its output ourselves in a streaming fashion. Besides
for-each-ref being simpler (we get to define the format
ourselves, and don't have to deal with speaking the git
protocol), it's more flexible for possible future changes.

For instance, it might be useful for the caller to be able
to limit the set of "interesting" alternate refs.  The
motivating example is one where many "forks" of a particular
repository share object storage, and the shared storage has
refs for each fork (which is why so many of the refs are
duplicates; each fork has the same tags).  A plausible
future optimization would be to ask for the alternate refs
for just _one_ fork (if you had some out-of-band way of
knowing which was the most interesting or important for the
current operation).

Similarly, no callbacks actually care about the symref value
of alternate refs, and as before, this patch ignores them
entirely.  However, if we wanted to add them, for-each-ref's
"%(symref)" is going to be more flexible than upload-pack,
because the latter only handles the HEAD symref due to
historical constraints.

There is one potential downside, though: unlike upload-pack,
our for-each-ref command doesn't report the peeled value of
refs. The existing code calls the alternate_ref_fn callback
twice for tags: once for the tag, and once for the peeled
value with the refname set to "ref^{}".

For the callers in fetch-pack, this doesn't matter at all.
We immediately peel each tag down to a commit either way (so
there's a slight improvement, as do not bother passing the
redundant data over the pipe). For the caller in
receive-pack, it means we will not advertise the peeled
values of tags in our alternate. However, we also don't
advertise peeled values for our _own_ tags, so this is
actually making things more consistent.

It's unclear whether receive-pack advertising peeled values
is a win or not. On one hand, giving more information to the
other side may let it omit some objects from the push. On
the other hand, for tags which both sides have, they simply
bloat the advertisement. The upload-pack advertisement of
git.git is about 30% larger than the receive-pack
advertisement due to its peeled information.

This patch omits the peeled information from
for_each_alternate_ref entirely, and leaves it up to the
caller whether they want to dig up the information.

Signed-off-by: Jeff King <peff@peff.net>
---
 transport.c | 48 ++++++++++++++++++++++++++++++++++++++----------
 1 file changed, 38 insertions(+), 10 deletions(-)

diff --git a/transport.c b/transport.c
index c87147046..48864b3a9 100644
--- a/transport.c
+++ b/transport.c
@@ -1206,6 +1206,42 @@ char *transport_anonymize_url(const char *url)
 	return xstrdup(url);
 }
 
+static void read_alternate_refs(const char *path,
+				alternate_ref_fn *cb,
+				void *data)
+{
+	struct child_process cmd = CHILD_PROCESS_INIT;
+	struct strbuf line = STRBUF_INIT;
+	FILE *fh;
+
+	cmd.git_cmd = 1;
+	argv_array_pushf(&cmd.args, "--git-dir=%s", path);
+	argv_array_push(&cmd.args, "for-each-ref");
+	argv_array_push(&cmd.args, "--format=%(objectname) %(refname)");
+	cmd.env = local_repo_env;
+	cmd.out = -1;
+
+	if (start_command(&cmd))
+		return;
+
+	fh = xfdopen(cmd.out, "r");
+	while (strbuf_getline_lf(&line, fh) != EOF) {
+		struct object_id oid;
+
+		if (get_oid_hex(line.buf, &oid) ||
+		    line.buf[GIT_SHA1_HEXSZ] != ' ') {
+			warning("invalid line while parsing alternate refs: %s",
+				line.buf);
+			break;
+		}
+
+		cb(line.buf + GIT_SHA1_HEXSZ + 1, &oid, data);
+	}
+
+	fclose(fh);
+	finish_command(&cmd);
+}
+
 struct alternate_refs_data {
 	alternate_ref_fn *fn;
 	void *data;
@@ -1216,9 +1252,6 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 {
 	struct strbuf path = STRBUF_INIT;
 	size_t base_len;
-	struct remote *remote;
-	struct transport *transport;
-	const struct ref *extra;
 	struct alternate_refs_data *cb = data;
 
 	if (!strbuf_realpath(&path, e->path, 0))
@@ -1233,13 +1266,8 @@ static int refs_from_alternate_cb(struct alternate_object_database *e,
 		goto out;
 	strbuf_setlen(&path, base_len);
 
-	remote = remote_get(path.buf);
-	transport = transport_get(remote, path.buf);
-	for (extra = transport_get_remote_refs(transport);
-	     extra;
-	     extra = extra->next)
-		cb->fn(extra->name, &extra->old_oid, cb->data);
-	transport_disconnect(transport);
+	read_alternate_refs(path.buf, cb->fn, cb->data);
+
 out:
 	strbuf_release(&path);
 	return 0;
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 06/11] fetch-pack: cache results of for_each_alternate_ref

[Jeff King]

We may run for_each_alternate_ref() twice, once in
find_common() and once in everything_local(). This operation
can be expensive, because it involves running a sub-process
which must freshly load all of the alternate's refs from
disk.

Let's cache and reuse the results between the two calls. We
can make some optimizations based on the particular use
pattern in fetch-pack to keep our memory usage down.

The first is that we only care about the sha1s, not the refs
themselves. So it's OK to store only the sha1s, and to
suppress duplicates. The natural fit would therefore be a
sha1_array.

However, sha1_array's de-duplication happens only after it
has read and sorted all entries. It still stores each
duplicate. For an alternate with a large number of refs
pointing to the same commits, this is a needless expense.

Instead, we'd prefer to eliminate duplicates before putting
them in the cache, which implies using a hash. We can
further note that fetch-pack will call parse_object() on
each alternate sha1. We can therefore keep our cache as a
set of pointers to "struct object". That gives us a place to
put our "already seen" bit with an optimized hash lookup.
And as a bonus, the object stores the sha1 for us, so
pointer-to-object is all we need.

There are two extra optimizations I didn't do here:

  - we actually store an array of pointer-to-object.
    Technically we could just walk the obj_hash table
    looking for entries with the ALTERNATE flag set (because
    our use case doesn't care about the order here).

    But that hash table may be mostly composed of
    non-ALTERNATE entries, so we'd waste time walking over
    them. So it would be a slight win in memory use, but a
    loss in CPU.

  - the items we pull out of the cache are actual "struct
    object"s, but then we feed "obj->sha1" to our
    sub-functions, which promptly call parse_object().

    This second parse is cheap, because it starts with
    lookup_object() and will bail immediately when it sees
    we've already parsed the object. We could save the extra
    hash lookup, but it would involve refactoring the
    functions we call. It may or may not be worth the
    trouble.

Signed-off-by: Jeff King <peff@peff.net>
---
 fetch-pack.c | 52 ++++++++++++++++++++++++++++++++++++++++++----------
 object.h     |  2 +-
 2 files changed, 43 insertions(+), 11 deletions(-)

diff --git a/fetch-pack.c b/fetch-pack.c
index 54f84c573..e0f5d5ce8 100644
--- a/fetch-pack.c
+++ b/fetch-pack.c
@@ -35,6 +35,7 @@ static const char *alternate_shallow_file;
 #define COMMON_REF	(1U << 2)
 #define SEEN		(1U << 3)
 #define POPPED		(1U << 4)
+#define ALTERNATE	(1U << 5)
 
 static int marked;
 
@@ -67,6 +68,41 @@ static inline void print_verbose(const struct fetch_pack_args *args,
 	fputc('\n', stderr);
 }
 
+struct alternate_object_cache {
+	struct object **items;
+	size_t nr, alloc;
+};
+
+static void cache_one_alternate(const char *refname,
+				const struct object_id *oid,
+				void *vcache)
+{
+	struct alternate_object_cache *cache = vcache;
+	struct object *obj = parse_object(oid->hash);
+
+	if (!obj || (obj->flags & ALTERNATE))
+		return;
+
+	obj->flags |= ALTERNATE;
+	ALLOC_GROW(cache->items, cache->nr + 1, cache->alloc);
+	cache->items[cache->nr++] = obj;
+}
+
+static void for_each_cached_alternate(void (*cb)(struct object *))
+{
+	static int initialized;
+	static struct alternate_object_cache cache;
+	size_t i;
+
+	if (!initialized) {
+		for_each_alternate_ref(cache_one_alternate, &cache);
+		initialized = 1;
+	}
+
+	for (i = 0; i < cache.nr; i++)
+		cb(cache.items[i]);
+}
+
 static void rev_list_push(struct commit *commit, int mark)
 {
 	if (!(commit->object.flags & mark)) {
@@ -253,11 +289,9 @@ static void send_request(struct fetch_pack_args *args,
 		write_or_die(fd, buf->buf, buf->len);
 }
 
-static void insert_one_alternate_ref(const char *refname,
-				     const struct object_id *oid,
-				     void *unused)
+static void insert_one_alternate_object(struct object *obj)
 {
-	rev_list_insert_ref(NULL, oid->hash);
+	rev_list_insert_ref(NULL, obj->oid.hash);
 }
 
 #define INITIAL_FLUSH 16
@@ -300,7 +334,7 @@ static int find_common(struct fetch_pack_args *args,
 	marked = 1;
 
 	for_each_ref(rev_list_insert_ref_oid, NULL);
-	for_each_alternate_ref(insert_one_alternate_ref, NULL);
+	for_each_cached_alternate(insert_one_alternate_object);
 
 	fetching = 0;
 	for ( ; refs ; refs = refs->next) {
@@ -621,11 +655,9 @@ static void filter_refs(struct fetch_pack_args *args,
 	*refs = newlist;
 }
 
-static void mark_alternate_complete(const char *refname,
-				    const struct object_id *oid,
-				    void *unused)
+static void mark_alternate_complete(struct object *obj)
 {
-	mark_complete(oid->hash);
+	mark_complete(obj->oid.hash);
 }
 
 static int everything_local(struct fetch_pack_args *args,
@@ -661,7 +693,7 @@ static int everything_local(struct fetch_pack_args *args,
 
 	if (!args->deepen) {
 		for_each_ref(mark_complete_oid, NULL);
-		for_each_alternate_ref(mark_alternate_complete, NULL);
+		for_each_cached_alternate(mark_alternate_complete);
 		commit_list_sort_by_date(&complete);
 		if (cutoff)
 			mark_recent_complete_commits(args, cutoff);
diff --git a/object.h b/object.h
index 614a00675..f52957dcb 100644
--- a/object.h
+++ b/object.h
@@ -29,7 +29,7 @@ struct object_array {
 /*
  * object flag allocation:
  * revision.h:      0---------10                                26
- * fetch-pack.c:    0---4
+ * fetch-pack.c:    0---5
  * walker.c:        0-2
  * upload-pack.c:       4       11----------------19
  * builtin/blame.c:               12-13
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 07/11] add oidset API

[Jeff King]

This is similar to many of our uses of sha1-array, but it
overcomes one limitation of a sha1-array: when you are
de-duplicating a large input with relatively few unique
entries, sha1-array uses 20 bytes per non-unique entry.
Whereas this set will use memory linear in the number of
unique entries (albeit a few more than 20 bytes due to
hashmap overhead).

Signed-off-by: Jeff King <peff@peff.net>
---
 Makefile |  1 +
 oidset.c | 49 +++++++++++++++++++++++++++++++++++++++++++++++++
 oidset.h | 45 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 95 insertions(+)
 create mode 100644 oidset.c
 create mode 100644 oidset.h

diff --git a/Makefile b/Makefile
index 8e4081e06..a5433978e 100644
--- a/Makefile
+++ b/Makefile
@@ -781,6 +781,7 @@ LIB_OBJS += notes-cache.o
 LIB_OBJS += notes-merge.o
 LIB_OBJS += notes-utils.o
 LIB_OBJS += object.o
+LIB_OBJS += oidset.o
 LIB_OBJS += pack-bitmap.o
 LIB_OBJS += pack-bitmap-write.o
 LIB_OBJS += pack-check.o
diff --git a/oidset.c b/oidset.c
new file mode 100644
index 000000000..ac169f05d
--- /dev/null
+++ b/oidset.c
@@ -0,0 +1,49 @@
+#include "cache.h"
+#include "oidset.h"
+
+struct oidset_entry {
+	struct hashmap_entry hash;
+	struct object_id oid;
+};
+
+static int oidset_hashcmp(const void *va, const void *vb,
+			  const void *vkey)
+{
+	const struct oidset_entry *a = va, *b = vb;
+	const struct object_id *key = vkey;
+	return oidcmp(&a->oid, key ? key : &b->oid);
+}
+
+int oidset_contains(const struct oidset *set, const struct object_id *oid)
+{
+	struct hashmap_entry key;
+
+	if (!set->map.cmpfn)
+		return 0;
+
+	hashmap_entry_init(&key, sha1hash(oid->hash));
+	return !!hashmap_get(&set->map, &key, oid);
+}
+
+int oidset_insert(struct oidset *set, const struct object_id *oid)
+{
+	struct oidset_entry *entry;
+
+	if (!set->map.cmpfn)
+		hashmap_init(&set->map, oidset_hashcmp, 0);
+
+	if (oidset_contains(set, oid))
+		return 1;
+
+	entry = xmalloc(sizeof(*entry));
+	hashmap_entry_init(&entry->hash, sha1hash(oid->hash));
+	oidcpy(&entry->oid, oid);
+
+	hashmap_add(&set->map, entry);
+	return 0;
+}
+
+void oidset_clear(struct oidset *set)
+{
+	hashmap_free(&set->map, 1);
+}
diff --git a/oidset.h b/oidset.h
new file mode 100644
index 000000000..b7eaab5b8
--- /dev/null
+++ b/oidset.h
@@ -0,0 +1,45 @@
+#ifndef OIDSET_H
+#define OIDSET_H
+
+/**
+ * This API is similar to sha1-array, in that it maintains a set of object ids
+ * in a memory-efficient way. The major differences are:
+ *
+ *   1. It uses a hash, so we can do online duplicate removal, rather than
+ *      sort-and-uniq at the end. This can reduce memory footprint if you have
+ *      a large list of oids with many duplicates.
+ *
+ *   2. The per-unique-oid memory footprint is slightly higher due to hash
+ *      table overhead.
+ */
+
+/**
+ * A single oidset; should be zero-initialized (or use OIDSET_INIT).
+ */
+struct oidset {
+	struct hashmap map;
+};
+
+#define OIDSET_INIT { { NULL } }
+
+/**
+ * Returns true iff `set` contains `oid`.
+ */
+int oidset_contains(const struct oidset *set, const struct object_id *oid);
+
+/**
+ * Insert the oid into the set; a copy is made, so "oid" does not need
+ * to persist after this function is called.
+ *
+ * Returns 1 if the oid was already in the set, 0 otherwise. This can be used
+ * to perform an efficient check-and-add.
+ */
+int oidset_insert(struct oidset *set, const struct object_id *oid);
+
+/**
+ * Remove all entries from the oidset, freeing any resources associated with
+ * it.
+ */
+void oidset_clear(struct oidset *set);
+
+#endif /* OIDSET_H */
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 08/11] receive-pack: use oidset to de-duplicate .have lines

[Jeff King]

If you have an alternate object store with a very large
number of refs, the peak memory usage of the sha1_array can
grow high, even if most of them are duplicates that end up
not being printed at all.

The similar for_each_alternate_ref() code-paths in
fetch-pack solve this by using flags in "struct object" to
de-duplicate (and so are relying on obj_hash at the core).

But we don't have a "struct object" at all in this case. We
could call lookup_unknown_object() to get one, but if our
goal is reducing memory footprint, it's not great:

 - an unknown object is as large as the largest object type
   (a commit), which is bigger than an oidset entry

 - we can free the memory after our ref advertisement, but
   "struct object" entries persist forever (and the
   receive-pack may hang around for a long time, as the
   bottleneck is often client upload bandwidth).

So let's use an oidset. Note that unlike a sha1-array it
doesn't sort the output as a side effect. However, our
output is at least stable, because for_each_alternate_ref()
will give us the sha1s in ref-sorted order.

In one particularly pathological case with an alternate that
has 60,000 unique refs out of 80 million total, this reduced
the peak heap usage of "git receive-pack . </dev/null" from
13GB to 14MB.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 26 ++++++++++++--------------
 1 file changed, 12 insertions(+), 14 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index d21332d9e..a4926fcfb 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -21,6 +21,7 @@
 #include "sigchain.h"
 #include "fsck.h"
 #include "tmp-objdir.h"
+#include "oidset.h"
 
 static const char * const receive_pack_usage[] = {
 	N_("git receive-pack <git-dir>"),
@@ -271,27 +272,24 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	return 0;
 }
 
-static int show_one_alternate_sha1(const unsigned char sha1[20], void *unused)
+static void show_one_alternate_ref(const char *refname,
+				   const struct object_id *oid,
+				   void *data)
 {
-	show_ref(".have", sha1);
-	return 0;
-}
+	struct oidset *seen = data;
 
-static void collect_one_alternate_ref(const char *refname,
-				      const struct object_id *oid,
-				      void *data)
-{
-	struct sha1_array *sa = data;
-	sha1_array_append(sa, oid->hash);
+	if (oidset_insert(seen, oid))
+		return;
+
+	show_ref(".have", oid->hash);
 }
 
 static void write_head_info(void)
 {
-	struct sha1_array sa = SHA1_ARRAY_INIT;
+	static struct oidset seen = OIDSET_INIT;
 
-	for_each_alternate_ref(collect_one_alternate_ref, &sa);
-	sha1_array_for_each_unique(&sa, show_one_alternate_sha1, NULL);
-	sha1_array_clear(&sa);
+	for_each_alternate_ref(show_one_alternate_ref, &seen);
+	oidset_clear(&seen);
 	for_each_ref(show_ref_cb, NULL);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 09/11] receive-pack: fix misleading namespace/.have comment

[Jeff King]

The comment claims that we handle alternate ".have" lines
through this function, but that hasn't been the case since
85f251045 (write_head_info(): handle "extra refs" locally,
2012-01-06).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 5 +----
 1 file changed, 1 insertion(+), 4 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index a4926fcfb..1821ad5fa 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -261,10 +261,7 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	/*
 	 * Advertise refs outside our current namespace as ".have"
 	 * refs, so that the client can use them to minimize data
-	 * transfer but will otherwise ignore them. This happens to
-	 * cover ".have" that are thrown in by add_one_alternate_ref()
-	 * to mark histories that are complete in our alternates as
-	 * well.
+	 * transfer but will otherwise ignore them.
 	 */
 	if (!path)
 		path = ".have";
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 10/11] receive-pack: treat namespace .have lines like alternates

[Jeff King]

Namely, de-duplicate them. We use the same set as the
alternates, since we call them both ".have" (i.e., there is
no value in showing one versus the other).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index 1821ad5fa..c23b0cce8 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -251,8 +251,9 @@ static void show_ref(const char *path, const unsigned char *sha1)
 }
 
 static int show_ref_cb(const char *path_full, const struct object_id *oid,
-		       int flag, void *unused)
+		       int flag, void *data)
 {
+	struct oidset *seen = data;
 	const char *path = strip_namespace(path_full);
 
 	if (ref_is_hidden(path, path_full))
@@ -263,8 +264,11 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 	 * refs, so that the client can use them to minimize data
 	 * transfer but will otherwise ignore them.
 	 */
-	if (!path)
+	if (!path) {
+		if (oidset_insert(seen, oid))
+			return 0;
 		path = ".have";
+	}
 	show_ref(path, oid->hash);
 	return 0;
 }
@@ -287,7 +291,7 @@ static void write_head_info(void)
 
 	for_each_alternate_ref(show_one_alternate_ref, &seen);
 	oidset_clear(&seen);
-	for_each_ref(show_ref_cb, NULL);
+	for_each_ref(show_ref_cb, &seen);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
 
-- 
2.12.0.rc0.371.ga6cf8653b

[PATCH v2 11/11] receive-pack: avoid duplicates between our refs and alternates

[Jeff King]

We de-duplicate ".have" refs among themselves, but never
check if they are duplicates of our local refs. It's not
unreasonable that they would be if we are a "--shared" or
"--reference" clone of a similar repository; we'd have all
the same tags.

We can handle this by inserting our local refs into the
oidset, but obviously not suppressing duplicates (since the
refnames are important).

Note that this also switches the order in which we advertise
refs, processing ours first and then any alternates. The
order shouldn't matter (and arguably showing our refs first
makes more sense).

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/receive-pack.c |  4 +++-
 t/t5400-send-pack.sh   | 38 ++++++++++++++++++++++++++++++++++++++
 2 files changed, 41 insertions(+), 1 deletion(-)

diff --git a/builtin/receive-pack.c b/builtin/receive-pack.c
index c23b0cce8..9ed8fbbfa 100644
--- a/builtin/receive-pack.c
+++ b/builtin/receive-pack.c
@@ -268,6 +268,8 @@ static int show_ref_cb(const char *path_full, const struct object_id *oid,
 		if (oidset_insert(seen, oid))
 			return 0;
 		path = ".have";
+	} else {
+		oidset_insert(seen, oid);
 	}
 	show_ref(path, oid->hash);
 	return 0;
@@ -289,9 +291,9 @@ static void write_head_info(void)
 {
 	static struct oidset seen = OIDSET_INIT;
 
+	for_each_ref(show_ref_cb, &seen);
 	for_each_alternate_ref(show_one_alternate_ref, &seen);
 	oidset_clear(&seen);
-	for_each_ref(show_ref_cb, &seen);
 	if (!sent_capabilities)
 		show_ref("capabilities^{}", null_sha1);
 
diff --git a/t/t5400-send-pack.sh b/t/t5400-send-pack.sh
index 305ca7a93..3331e0f53 100755
--- a/t/t5400-send-pack.sh
+++ b/t/t5400-send-pack.sh
@@ -255,4 +255,42 @@ test_expect_success 'deny pushing to delete current branch' '
 	)
 '
 
+extract_ref_advertisement () {
+	perl -lne '
+		# \\ is there to skip capabilities after \0
+		/push< ([^\\]+)/ or next;
+		exit 0 if $1 eq "0000";
+		print $1;
+	'
+}
+
+test_expect_success 'receive-pack de-dupes .have lines' '
+	git init shared &&
+	git -C shared commit --allow-empty -m both &&
+	git clone -s shared fork &&
+	(
+		cd shared &&
+		git checkout -b only-shared &&
+		git commit --allow-empty -m only-shared &&
+		git update-ref refs/heads/foo HEAD
+	) &&
+
+	# Notable things in this expectation:
+	#  - local refs are not de-duped
+	#  - .have does not duplicate locals
+	#  - .have does not duplicate itself
+	local=$(git -C fork rev-parse HEAD) &&
+	shared=$(git -C shared rev-parse only-shared) &&
+	cat >expect <<-EOF &&
+	$local refs/heads/master
+	$local refs/remotes/origin/HEAD
+	$local refs/remotes/origin/master
+	$shared .have
+	EOF
+
+	GIT_TRACE_PACKET=$(pwd)/trace git push fork HEAD:foo &&
+	extract_ref_advertisement <trace >refs &&
+	test_cmp expect refs
+'
+
 test_done
-- 
2.12.0.rc0.371.ga6cf8653b