[PATCH v2 0/7] speed up pack-objects counting with many packs

[PATCH v2 0/7] speed up pack-objects counting with many packs

[Jeff King]

This is a follow-up to the patches in

  http://public-inbox.org/git/20160725184938.GA12871@sigill.intra.peff.net/

that are currently queued in jk/pack-objects-optim-skimming. Roughly,
they try to optimize a loop that is O(nr_objects * nr_packs) by breaking
out early in some cases.

I had written those patches a while ago and confirmed that they did
speed up a particular nasty case I had. But when I tried to write a
t/perf test to show off the improvement, I found that they didn't help!
The reason is that the optimizations are heavily dependent on the order
of the packs, and which objects go in which pack. The loop has the same
worst-case complexity as it always did, but we rely on getting lucky to
break out early.

I think the perf test I've included here is more representative of a
real-world workloads, and with an extra optimization, I was able to show
good numbers with it.

The general strategy is to order the pack lookups in most-recently-used
order. This replaces an existing 1-element MRU cache in the normal pack
lookup code, and replaces a straight reverse-chronological iteration in
pack-objects.

All credit for thinking of this scheme goes to Michael Haggerty, who
suggested the idea to me about six months ago. It seemed like a lot of
work at the time, so I didn't do it. :) But as I started to implement
the same 1-element cache in pack-objects, I found that the code actually
gets rather awkward. The MRU solution makes the callers easier to read,
and of course it turns out to be faster, to boot.

Anyway, enough chit-chat. The patches are:

  [1/7]: t/perf: add tests for many-pack scenarios
  [2/7]: sha1_file: drop free_pack_by_name
  [3/7]: add generic most-recently-used list
  [4/7]: find_pack_entry: replace last_found_pack with MRU cache
  [5/7]: pack-objects: break out of want_object loop early
  [6/7]: pack-objects: compute local/ignore_pack_keep early
  [7/7]: pack-objects: use mru list when iterating over packs

The actual optimizations are in patches 4 and 7, which have their own
numbers. But here are end-to-end numbers for the series against the tip
of master (for the meanings, see the discussion in patch 1, and the
analysis in 4 and 7):

[p5303, linux.git]
Test                      origin                HEAD
-------------------------------------------------------------------------
5303.3: rev-list (1)      31.48(31.20+0.27)     31.18(30.95+0.22) -1.0%
5303.4: repack (1)        40.74(39.27+2.56)     40.30(38.96+2.47) -1.1%
5303.6: rev-list (50)     31.65(31.38+0.26)     31.26(31.02+0.23) -1.2%
5303.7: repack (50)       60.90(71.03+2.13)     46.95(57.46+1.85) -22.9%
5303.9: rev-list (1000)   38.63(38.25+0.37)     31.91(31.61+0.28) -17.4%
5303.10: repack (1000)    392.52(467.09+5.05)   87.38(159.98+2.92) -77.7%

[p5303, git.git]
Test                      origin              HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.55(1.54+0.00)     1.56(1.54+0.01) +0.6%
5303.4: repack (1)        1.83(1.82+0.06)     1.82(1.82+0.05) -0.5%
5303.6: rev-list (50)     1.58(1.56+0.02)     1.58(1.57+0.00) +0.0%
5303.7: repack (50)       2.50(3.16+0.04)     2.32(2.92+0.09) -7.2%
5303.9: rev-list (1000)   2.64(2.61+0.02)     2.23(2.21+0.01) -15.5%
5303.10: repack (1000)    12.68(19.07+0.30)   7.51(13.86+0.20) -40.8%

For curiosity, I also ran the git.git case with 10,000 packs. This is
even more silly, but it shows that the problem does get worse and worse
as the number grows, but that the patches do continue to help:

Test                        origin               HEAD
-------------------------------------------------------------------------
5303.12: rev-list (10,000)  26.00(25.86+0.13)    15.76(15.62+0.13) -39.4%
5303.13: repack (10,000)   164.11(175.30+1.34)   51.48(62.96+1.18) -68.6%

-Peff

[PATCH v2 1/7] t/perf: add tests for many-pack scenarios

[Jeff King]

Git's pack storage does efficient (log n) lookups in a
single packfile's index, but if we have multiple packfiles,
we have to linearly search each for a given object.  This
patch introduces some timing tests for cases where we have a
large number of packs, so that we can measure any
improvements we make in the following patches.

The main thing we want to time is object lookup. To do this,
we measure "git rev-list --objects --all", which does a
fairly large number of object lookups (essentially one per
object in the repository).

However, we also measure the time to do a full repack, which
is interesting for two reasons. One is that in addition to
the usual pack lookup, it has its own linear iteration over
the list of packs. And two is that because it it is the tool
one uses to go from an inefficient many-pack situation back
to a single pack, we care about its performance not only at
marginal numbers of packs, but at the extreme cases (e.g.,
if you somehow end up with 5,000 packs, it is the only way
to get back to 1 pack, so we need to make sure it performs
well).

We measure the performance of each command in three
scenarios: 1 pack, 50 packs, and 1,000 packs.

The 1-pack case is a baseline; any optimizations we do to
handle multiple packs cannot possibly perform better than
this.

The 50-pack case is as far as Git should generally allow
your repository to go, if you have auto-gc enabled with the
default settings. So this represents the maximum performance
improvement we would expect under normal circumstances.

The 1,000-pack case is hopefully rare, though I have seen it
in the wild where automatic maintenance was broken for some
time (and the repository continued to receive pushes). This
represents cases where we care less about general
performance, but want to make sure that a full repack
command does not take excessively long.

Signed-off-by: Jeff King <peff@peff.net>
---
By the way, a caution before you run this. It takes one the order of an
hour to run on linux.git. So if you're comparing a few builds, be
patient. :)

 t/perf/p5303-many-packs.sh | 87 ++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 87 insertions(+)
 create mode 100755 t/perf/p5303-many-packs.sh

diff --git a/t/perf/p5303-many-packs.sh b/t/perf/p5303-many-packs.sh
new file mode 100755
index 0000000..3779851
--- /dev/null
+++ b/t/perf/p5303-many-packs.sh
@@ -0,0 +1,87 @@
+#!/bin/sh
+
+test_description='performance with large numbers of packs'
+. ./perf-lib.sh
+
+test_perf_large_repo
+
+# A real many-pack situation would probably come from having a lot of pushes
+# over time. We don't know how big each push would be, but we can fake it by
+# just walking the first-parent chain and having every 5 commits be their own
+# "push". This isn't _entirely_ accurate, as real pushes would have some
+# duplicate objects due to thin-pack fixing, but it's a reasonable
+# approximation.
+#
+# And then all of the rest of the objects can go in a single packfile that
+# represents the state before any of those pushes (actually, we'll generate
+# that first because in such a setup it would be the oldest pack, and we sort
+# the packs by reverse mtime inside git).
+repack_into_n () {
+	rm -rf staging &&
+	mkdir staging &&
+
+	git rev-list --first-parent HEAD |
+	sed -n '1~5p' |
+	head -n "$1" |
+	perl -e 'print reverse <>' \
+	>pushes
+
+	# create base packfile
+	head -n 1 pushes |
+	git pack-objects --delta-base-offset --revs staging/pack
+
+	# and then incrementals between each pair of commits
+	last= &&
+	while read rev
+	do
+		if test -n "$last"; then
+			{
+				echo "$rev" &&
+				echo "^$last"
+			} |
+			git pack-objects --delta-base-offset --revs \
+				staging/pack || return 1
+		fi
+		last=$rev
+	done <pushes &&
+
+	# and install the whole thing
+	rm -f .git/objects/pack/* &&
+	mv staging/* .git/objects/pack/
+}
+
+# Pretend we just have a single branch and no reflogs, and that everything is
+# in objects/pack; that makes our fake pack-building via repack_into_n()
+# much simpler.
+test_expect_success 'simplify reachability' '
+	tip=$(git rev-parse --verify HEAD) &&
+	git for-each-ref --format="option no-deref%0adelete %(refname)" |
+	git update-ref --stdin &&
+	rm -rf .git/logs &&
+	git update-ref refs/heads/master $tip &&
+	git symbolic-ref HEAD refs/heads/master &&
+	git repack -ad
+'
+
+for nr_packs in 1 50 1000
+do
+	test_expect_success "create $nr_packs-pack scenario" '
+		repack_into_n $nr_packs
+	'
+
+	test_perf "rev-list ($nr_packs)" '
+		git rev-list --objects --all >/dev/null
+	'
+
+	# This simulates the interesting part of the repack, which is the
+	# actual pack generation, without smudging the on-disk setup
+	# between trials.
+	test_perf "repack ($nr_packs)" '
+		git pack-objects --keep-true-parents \
+		  --honor-pack-keep --non-empty --all \
+		  --reflog --indexed-objects --delta-base-offset \
+		  --stdout </dev/null >/dev/null
+	'
+done
+
+test_done
-- 
2.9.2.607.g98dce7b

[PATCH v2 2/7] sha1_file: drop free_pack_by_name

[Jeff King]

The point of this function is to drop an entry from the
"packed_git" cache that points to a file we might be
overwriting, because our contents may not be the same (and
hence the only caller was pack-objects as it moved a
temporary packfile into place).

In older versions of git, this could happen because the
names of packfiles were derived from the set of objects they
contained, not the actual bits on disk. But since 1190a1a
(pack-objects: name pack files after trailer hash,
2013-12-05), the name reflects the actual bits on disk, and
any two packfiles with the same name can be used
interchangeably.

Dropping this function not only saves a few lines of code,
it makes the lifetime of "struct packed_git" much easier to
reason about: namely, we now do not ever free these structs.

Signed-off-by: Jeff King <peff@peff.net>
---
 cache.h      |  1 -
 pack-write.c |  1 -
 sha1_file.c  | 30 ------------------------------
 3 files changed, 32 deletions(-)

diff --git a/cache.h b/cache.h
index 3855ddf..57ef726 100644
--- a/cache.h
+++ b/cache.h
@@ -1416,7 +1416,6 @@ extern unsigned char *use_pack(struct packed_git *, struct pack_window **, off_t
 extern void close_pack_windows(struct packed_git *);
 extern void close_all_packs(void);
 extern void unuse_pack(struct pack_window **);
-extern void free_pack_by_name(const char *);
 extern void clear_delta_base_cache(void);
 extern struct packed_git *add_packed_git(const char *path, size_t path_len, int local);
 
diff --git a/pack-write.c b/pack-write.c
index 33293ce..ea0b788 100644
--- a/pack-write.c
+++ b/pack-write.c
@@ -354,7 +354,6 @@ void finish_tmp_packfile(struct strbuf *name_buffer,
 		die_errno("unable to make temporary index file readable");
 
 	strbuf_addf(name_buffer, "%s.pack", sha1_to_hex(sha1));
-	free_pack_by_name(name_buffer->buf);
 
 	if (rename(pack_tmp_name, name_buffer->buf))
 		die_errno("unable to rename temporary pack file");
diff --git a/sha1_file.c b/sha1_file.c
index d5e1121..e045d2f 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -891,36 +891,6 @@ void close_pack_index(struct packed_git *p)
 	}
 }
 
-/*
- * This is used by git-repack in case a newly created pack happens to
- * contain the same set of objects as an existing one.  In that case
- * the resulting file might be different even if its name would be the
- * same.  It is best to close any reference to the old pack before it is
- * replaced on disk.  Of course no index pointers or windows for given pack
- * must subsist at this point.  If ever objects from this pack are requested
- * again, the new version of the pack will be reinitialized through
- * reprepare_packed_git().
- */
-void free_pack_by_name(const char *pack_name)
-{
-	struct packed_git *p, **pp = &packed_git;
-
-	while (*pp) {
-		p = *pp;
-		if (strcmp(pack_name, p->pack_name) == 0) {
-			clear_delta_base_cache();
-			close_pack(p);
-			free(p->bad_object_sha1);
-			*pp = p->next;
-			if (last_found_pack == p)
-				last_found_pack = NULL;
-			free(p);
-			return;
-		}
-		pp = &p->next;
-	}
-}
-
 static unsigned int get_max_fd_limit(void)
 {
 #ifdef RLIMIT_NOFILE
-- 
2.9.2.607.g98dce7b

[PATCH v2 3/7] add generic most-recently-used list

[Jeff King]

There are a few places in Git that would benefit from a fast
most-recently-used cache (e.g., the list of packs, which we
search linearly but would like to order based on locality).
This patch introduces a generic list that can be used to
store arbitrary pointers in most-recently-used order.

The implementation is just a doubly-linked list, where
"marking" an item as used moves it to the front of the list.
Insertion and marking are O(1), and iteration is O(n).

There's no lookup support provided; if you need fast
lookups, you are better off with a different data structure
in the first place.

There is also no deletion support. This would not be hard to
do, but it's not necessary for handling pack structs, which
are created and never removed.

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

diff --git a/Makefile b/Makefile
index 6a13386..ad3624d 100644
--- a/Makefile
+++ b/Makefile
@@ -755,6 +755,7 @@ LIB_OBJS += merge.o
 LIB_OBJS += merge-blobs.o
 LIB_OBJS += merge-recursive.o
 LIB_OBJS += mergesort.o
+LIB_OBJS += mru.o
 LIB_OBJS += name-hash.o
 LIB_OBJS += notes.o
 LIB_OBJS += notes-cache.o
diff --git a/mru.c b/mru.c
new file mode 100644
index 0000000..9dedae0
--- /dev/null
+++ b/mru.c
@@ -0,0 +1,50 @@
+#include "cache.h"
+#include "mru.h"
+
+void mru_append(struct mru *mru, void *item)
+{
+	struct mru_entry *cur = xmalloc(sizeof(*cur));
+	cur->item = item;
+	cur->prev = mru->tail;
+	cur->next = NULL;
+
+	if (mru->tail)
+		mru->tail->next = cur;
+	else
+		mru->head = cur;
+	mru->tail = cur;
+}
+
+void mru_mark(struct mru *mru, struct mru_entry *entry)
+{
+	/* If we're already at the front of the list, nothing to do */
+	if (mru->head == entry)
+		return;
+
+	/* Otherwise, remove us from our current slot... */
+	if (entry->prev)
+		entry->prev->next = entry->next;
+	if (entry->next)
+		entry->next->prev = entry->prev;
+	else
+		mru->tail = entry->prev;
+
+	/* And insert us at the beginning. */
+	entry->prev = NULL;
+	entry->next = mru->head;
+	if (mru->head)
+		mru->head->prev = entry;
+	mru->head = entry;
+}
+
+void mru_clear(struct mru *mru)
+{
+	struct mru_entry *p = mru->head;
+
+	while (p) {
+		struct mru_entry *to_free = p;
+		p = p->next;
+		free(to_free);
+	}
+	mru->head = mru->tail = NULL;
+}
diff --git a/mru.h b/mru.h
new file mode 100644
index 0000000..42e4aea
--- /dev/null
+++ b/mru.h
@@ -0,0 +1,45 @@
+#ifndef MRU_H
+#define MRU_H
+
+/**
+ * A simple most-recently-used cache, backed by a doubly-linked list.
+ *
+ * Usage is roughly:
+ *
+ *   // Create a list.  Zero-initialization is required.
+ *   static struct mru cache;
+ *   mru_append(&cache, item);
+ *   ...
+ *
+ *   // Iterate in MRU order.
+ *   struct mru_entry *p;
+ *   for (p = cache.head; p; p = p->next) {
+ *	if (matches(p->item))
+ *		break;
+ *   }
+ *
+ *   // Mark an item as used, moving it to the front of the list.
+ *   mru_mark(&cache, p);
+ *
+ *   // Reset the list to empty, cleaning up all resources.
+ *   mru_clear(&cache);
+ *
+ * Note that you SHOULD NOT call mru_mark() and then continue traversing the
+ * list; it reorders the marked item to the front of the list, and therefore
+ * you will begin traversing the whole list again.
+ */
+
+struct mru_entry {
+	void *item;
+	struct mru_entry *prev, *next;
+};
+
+struct mru {
+	struct mru_entry *head, *tail;
+};
+
+void mru_append(struct mru *mru, void *item);
+void mru_mark(struct mru *mru, struct mru_entry *entry);
+void mru_clear(struct mru *mru);
+
+#endif /* MRU_H */
-- 
2.9.2.607.g98dce7b

[PATCH v2 4/7] find_pack_entry: replace last_found_pack with MRU cache

[Jeff King]

Each pack has an index for looking up entries in O(log n)
time, but if we have multiple packs, we have to scan through
them linearly. This can produce a measurable overhead for
some operations.

We dealt with this long ago in f7c22cc (always start looking
up objects in the last used pack first, 2007-05-30), which
keeps what is essentially a 1-element most-recently-used
cache. In theory, we should be able to do better by keeping
a similar but longer cache, that is the same length as the
pack-list itself.

Since we now have a convenient generic MRU structure, we can
plug it in and measure. Here are the numbers for running
p5303 against linux.git:

Test                      HEAD^                HEAD
------------------------------------------------------------------------
5303.3: rev-list (1)      31.56(31.28+0.27)    31.30(31.08+0.20) -0.8%
5303.4: repack (1)        40.62(39.35+2.36)    40.60(39.27+2.44) -0.0%
5303.6: rev-list (50)     31.31(31.06+0.23)    31.23(31.00+0.22) -0.3%
5303.7: repack (50)       58.65(69.12+1.94)    58.27(68.64+2.05) -0.6%
5303.9: rev-list (1000)   38.74(38.40+0.33)    31.87(31.62+0.24) -17.7%
5303.10: repack (1000)    367.20(441.80+4.62)  342.00(414.04+3.72) -6.9%

The main numbers of interest here are the rev-list ones
(since that is exercising the normal object lookup code
path).  The single-pack case shouldn't improve at all; the
260ms speedup there is just part of the run-to-run noise
(but it's important to note that we didn't make anything
worse with the overhead of maintaining our cache). In the
50-pack case, we see similar results. There may be a slight
improvement, but it's mostly within the noise.

The 1000-pack case does show a big improvement, though. That
carries over to the repack case, as well. Even though we
haven't touched its pack-search loop yet, it does still do a
lot of normal object lookups (e.g., for the internal
revision walk), and so improves.

As a point of reference, I also ran the 1000-pack test
against a version of HEAD^ with the last_found_pack
optimization disabled. It takes ~60s, so that gives an
indication of how much even the single-element cache is
helping.

For comparison, here's a smaller repository, git.git:

Test                      HEAD^               HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.56(1.54+0.01)    1.54(1.51+0.02) -1.3%
5303.4: repack (1)        1.84(1.80+0.10)    1.82(1.80+0.09) -1.1%
5303.6: rev-list (50)     1.58(1.55+0.02)    1.59(1.57+0.01) +0.6%
5303.7: repack (50)       2.50(3.18+0.04)    2.50(3.14+0.04) +0.0%
5303.9: rev-list (1000)   2.76(2.71+0.04)    2.24(2.21+0.02) -18.8%
5303.10: repack (1000)    13.21(19.56+0.25)  11.66(18.01+0.21) -11.7%

You can see that the percentage improvement is similar.
That's because the lookup we are optimizing is roughly
O(nr_objects * nr_packs). Since the number of packs is
constant in both tests, we'd expect the improvement to be
linear in the number of objects. But the whole process is
also linear in the number of objects, so the improvement
is a constant factor.

The exact improvement does also depend on the contents of
the packs. In p5303, the extra packs all have 5 first-parent
commits in them, which is a reasonable simulation of a
pushed-to repository. But it also means that only 250
first-parent commits are in those packs (compared to almost
50,000 total in linux.git), and the rest are in the huge
"base" pack. So once we start looking at history in taht big
pack, that's where we'll find most everything, and even the
1-element cache gets close to 100% cache hits.  You could
almost certainly show better numbers with a more
pathological case (e.g., distributing the objects more
evenly across the packs). But that's simply not that
realistic a scenario, so it makes more sense to focus on
these numbers.

The implementation itself is a straightforward application
of the MRU code. We provide an MRU-ordered list of packs
that shadows the packed_git list. This is easy to do because
we only create and revise the pack list in one place. The
"reprepare" code path actually drops the whole MRU and
replaces it for simplicity. It would be more efficient to
just add new entries, but there's not much point in
optimizing here; repreparing happens rarely, and only after
doing a lot of other expensive work.  The key things to keep
optimized are traversal (which is just a normal linked list,
albeit with one extra level of indirection over the regular
packed_git list), and marking (which is a constant number of
pointer assignments, though slightly more than the old
last_found_pack was; it doesn't seem to create a measurable
slowdown, though).

Signed-off-by: Jeff King <peff@peff.net>
---
I could see an argument against this, which is basically:

  - this is touching a really critical and core part of the code

  - in normal cases, we should never grow beyond 50 packs

  - it seems to be a wash at 50 packs

So it's all risk and no benefit. But it definitely _does_ help in the
more pathological cases, which are sadly a thing I have seen more than
once. So I tried hard to show that it does no harm, performance-wise,
for the smaller cases. As for complexity, you can be the judge. I think
the call-site here is improved, but of course that's because the
complexity is hidden in the mru_mark() function.

 cache.h     |  7 +++++++
 sha1_file.c | 36 ++++++++++++++++++------------------
 2 files changed, 25 insertions(+), 18 deletions(-)

diff --git a/cache.h b/cache.h
index 57ef726..9b4b08f 100644
--- a/cache.h
+++ b/cache.h
@@ -1377,6 +1377,13 @@ extern struct packed_git {
 	char pack_name[FLEX_ARRAY]; /* more */
 } *packed_git;
 
+/*
+ * A most-recently-used ordered version of the packed_git list, which can
+ * be iterated instead of packed_git (and marked via mru_mark).
+ */
+struct mru;
+extern struct mru *packed_git_mru;
+
 struct pack_entry {
 	off_t offset;
 	unsigned char sha1[20];
diff --git a/sha1_file.c b/sha1_file.c
index e045d2f..4eb3318 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -23,6 +23,7 @@
 #include "bulk-checkin.h"
 #include "streaming.h"
 #include "dir.h"
+#include "mru.h"
 
 #ifndef O_NOATIME
 #if defined(__linux__) && (defined(__i386__) || defined(__PPC__))
@@ -59,14 +60,6 @@ static struct cached_object empty_tree = {
 	0
 };
 
-/*
- * A pointer to the last packed_git in which an object was found.
- * When an object is sought, we look in this packfile first, because
- * objects that are looked up at similar times are often in the same
- * packfile as one another.
- */
-static struct packed_git *last_found_pack;
-
 static struct cached_object *find_cached_object(const unsigned char *sha1)
 {
 	int i;
@@ -522,6 +515,9 @@ static size_t peak_pack_mapped;
 static size_t pack_mapped;
 struct packed_git *packed_git;
 
+static struct mru packed_git_mru_storage;
+struct mru *packed_git_mru = &packed_git_mru_storage;
+
 void pack_report(void)
 {
 	fprintf(stderr,
@@ -1355,6 +1351,15 @@ static void rearrange_packed_git(void)
 	free(ary);
 }
 
+static void prepare_packed_git_mru(void)
+{
+	struct packed_git *p;
+
+	mru_clear(packed_git_mru);
+	for (p = packed_git; p; p = p->next)
+		mru_append(packed_git_mru, p);
+}
+
 static int prepare_packed_git_run_once = 0;
 void prepare_packed_git(void)
 {
@@ -1370,6 +1375,7 @@ void prepare_packed_git(void)
 		alt->name[-1] = '/';
 	}
 	rearrange_packed_git();
+	prepare_packed_git_mru();
 	prepare_packed_git_run_once = 1;
 }
 
@@ -2574,21 +2580,15 @@ static int fill_pack_entry(const unsigned char *sha1,
  */
 static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e)
 {
-	struct packed_git *p;
+	struct mru_entry *p;
 
 	prepare_packed_git();
 	if (!packed_git)
 		return 0;
 
-	if (last_found_pack && fill_pack_entry(sha1, e, last_found_pack))
-		return 1;
-
-	for (p = packed_git; p; p = p->next) {
-		if (p == last_found_pack)
-			continue; /* we already checked this one */
-
-		if (fill_pack_entry(sha1, e, p)) {
-			last_found_pack = p;
+	for (p = packed_git_mru->head; p; p = p->next) {
+		if (fill_pack_entry(sha1, e, p->item)) {
+			mru_mark(packed_git_mru, p);
 			return 1;
 		}
 	}
-- 
2.9.2.607.g98dce7b

[PATCH v2 5/7] pack-objects: break out of want_object loop early

[Jeff King]

When pack-objects collects the list of objects to pack
(either from stdin, or via its internal rev-list), it
filters each one through want_object_in_pack().

This function loops through each existing packfile, looking
for the object. When we find it, we mark the pack/offset
combo for later use. However, we can't just return "yes, we
want it" at that point. If --honor-pack-keep is in effect,
we must keep looking to find it in _all_ packs, to make sure
none of them has a .keep. Likewise, if --local is in effect,
we must make sure it is not present in any non-local pack.

As a result, the sum effort of these calls is effectively
O(nr_objects * nr_packs). In an ordinary repository, we have
only a handful of packs, and this doesn't make a big
difference. But in pathological cases, it can slow the
counting phase to a crawl.

This patch notices the case that we have neither "--local"
nor "--honor-pack-keep" in effect and breaks out of the loop
early, after finding the first instance. Note that our worst
case is still "objects * packs" (i.e., we might find each
object in the last pack we look in), but in practice we will
often break out early. On an "average" repo, my git.git with
8 packs, this shows a modest 2% (a few dozen milliseconds)
improvement in the counting-objects phase of "git
pack-objects --all <foo" (hackily instrumented by sticking
exit(0) right after list_objects).

But in a much more pathological case, it makes a bigger
difference. I ran the same command on a real-world example
with ~9 million objects across 1300 packs. The counting time
dropped from 413s to 45s, an improvement of about 89%.

Note that this patch won't do anything by itself for a
normal "git gc", as it uses both --honor-pack-keep and
--local.

Signed-off-by: Jeff King <peff@peff.net>
---
Same as earlier, though I took the re-ordering and comment from Junio
that came out of the earlier discussion.

 builtin/pack-objects.c | 16 ++++++++++++++++
 1 file changed, 16 insertions(+)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index a2f8cfd..8ad11f2 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -977,6 +977,22 @@ static int want_object_in_pack(const unsigned char *sha1,
 				return 1;
 			if (incremental)
 				return 0;
+
+			/*
+			 * When asked to do --local (do not include an
+			 * object that appears in a pack we borrow
+			 * from elsewhere) or --honor-pack-keep (do not
+			 * include an object that appears in a pack marked
+			 * with .keep), we need to make sure no copy of this
+			 * object come from in _any_ pack that causes us to
+			 * omit it, and need to complete this loop.  When
+			 * neither option is in effect, we know the object
+			 * we just found is going to be packed, so break
+			 * out of the loop to return 1 now.
+			 */
+			if (!ignore_packed_keep && !local)
+				break;
+
 			if (local && !p->pack_local)
 				return 0;
 			if (ignore_packed_keep && p->pack_local && p->pack_keep)
-- 
2.9.2.607.g98dce7b

[PATCH v2 6/7] pack-objects: compute local/ignore_pack_keep early

[Jeff King]

In want_object_in_pack(), we can exit early from our loop if
neither "local" nor "ignore_pack_keep" are set. If they are,
however, we must examine each pack to see if it has the
object and is non-local or has a ".keep".

It's quite common for there to be no non-local or .keep
packs at all, in which case we know ahead of time that
looking further will be pointless. We can pre-compute this
by simply iterating over the list of packs ahead of time,
and dropping the flags if there are no packs that could
match.

Another similar strategy would be to modify the loop in
want_object_in_pack() to notice that we have already found
the object once, and that we are looping only to check for
"local" and "keep" attributes. If a pack has neither of
those, we can skip the call to find_pack_entry_one(), which
is the expensive part of the loop.

This has two advantages:

  - it isn't all-or-nothing; we still get some improvement
    when there's a small number of kept or non-local packs,
    and a large number of non-kept local packs

  - it eliminates any possible race where we add new
    non-local or kept packs after our initial scan. In
    practice, I don't think this race matters; we already
    cache the packed_git information, so somebody who adds a
    new pack or .keep file after we've started will not be
    noticed at all, unless we happen to need to call
    reprepare_packed_git() because a lookup fails.

    In other words, we're already racy, and the race is not
    a big deal (losing the race means we might include an
    object in the pack that would not otherwise be, which is
    an acceptable outcome).

However, it also has a disadvantage: we still loop over the
rest of the packs for each object to check their flags. This
is much less expensive than doing the object lookup, but
still not free. So if we wanted to implement that strategy
to cover the non-all-or-nothing cases, we could do so in
addition to this one (so you get the most speedup in the
all-or-nothing case, and the best we can do in the other
cases). But given that the all-or-nothing case is likely the
most common, it is probably not worth the trouble, and we
can revisit this later if evidence points otherwise.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c | 26 +++++++++++++++++++++++++-
 1 file changed, 25 insertions(+), 1 deletion(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 8ad11f2..c4c2a3c 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -46,6 +46,7 @@ static int keep_unreachable, unpack_unreachable, include_tag;
 static unsigned long unpack_unreachable_expiration;
 static int pack_loose_unreachable;
 static int local;
+static int have_non_local_packs;
 static int incremental;
 static int ignore_packed_keep;
 static int allow_ofs_delta;
@@ -990,7 +991,8 @@ static int want_object_in_pack(const unsigned char *sha1,
 			 * we just found is going to be packed, so break
 			 * out of the loop to return 1 now.
 			 */
-			if (!ignore_packed_keep && !local)
+			if (!ignore_packed_keep &&
+			    (!local || !have_non_local_packs))
 				break;
 
 			if (local && !p->pack_local)
@@ -2799,6 +2801,28 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 		progress = 2;
 
 	prepare_packed_git();
+	if (ignore_packed_keep) {
+		struct packed_git *p;
+		for (p = packed_git; p; p = p->next)
+			if (p->pack_local && p->pack_keep)
+				break;
+		if (!p) /* no keep-able packs found */
+			ignore_packed_keep = 0;
+	}
+	if (local) {
+		/*
+		 * unlike ignore_packed_keep above, we do not want to
+		 * unset "local" based on looking at packs, as it
+		 * also covers non-local objects
+		 */
+		struct packed_git *p;
+		for (p = packed_git; p; p = p->next) {
+			if (!p->pack_local) {
+				have_non_local_packs = 1;
+				break;
+			}
+		}
+	}
 
 	if (progress)
 		progress_state = start_progress(_("Counting objects"), 0);
-- 
2.9.2.607.g98dce7b

[PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

In the original implementation of want_object_in_pack(), we
always looked for the object in every pack, so the order did
not matter for performance.

As of the last few patches, however, we can now often break
out of the loop early after finding the first instance, and
avoid looking in the other packs at all. In this case, pack
order can make a big difference, because we'd like to find
the objects by looking at as few packs as possible.

This patch switches us to the same packed_git_mru list that
is now used by normal object lookups.

Here are timings for p5303 on linux.git:

Test                      HEAD^                HEAD
------------------------------------------------------------------------
5303.3: rev-list (1)      31.31(31.07+0.23)    31.28(31.00+0.27) -0.1%
5303.4: repack (1)        40.35(38.84+2.60)    40.53(39.31+2.32) +0.4%
5303.6: rev-list (50)     31.37(31.15+0.21)    31.41(31.16+0.24) +0.1%
5303.7: repack (50)       58.25(68.54+2.03)    47.28(57.66+1.89) -18.8%
5303.9: rev-list (1000)   31.91(31.57+0.33)    31.93(31.64+0.28) +0.1%
5303.10: repack (1000)    304.80(376.00+3.92)  87.21(159.54+2.84) -71.4%

The rev-list numbers are unchanged, which makes sense (they
are not exercising this code at all). The 50- and 1000-pack
repack cases show considerable improvement.

The single-pack repack case doesn't, of course; there's
nothing to improve. In fact, it gives us a baseline for how
fast we could possibly go. You can see that though rev-list
can approach the single-pack case even with 1000 packs,
repack doesn't. The reason is simple: the loop we are
optimizing is only part of what the repack is doing. After
the "counting" phase, we do delta compression, which is much
more expensive when there are multiple packs, because we
have fewer deltas we can reuse (you can also see that these
numbers come from a multicore machine; the CPU times are
much higher than the wall-clock times due to the delta
phase).

So the good news is that in cases with many packs, we used
to be dominated by the "counting" phase, and now we are
dominated by the delta compression (which is faster, and
which we have already parallelized).

Here are similar numbers for git.git:

Test                      HEAD^               HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.55(1.51+0.02)     1.54(1.53+0.00) -0.6%
5303.4: repack (1)        1.82(1.80+0.08)     1.82(1.78+0.09) +0.0%
5303.6: rev-list (50)     1.58(1.57+0.00)     1.58(1.56+0.01) +0.0%
5303.7: repack (50)       2.50(3.12+0.07)     2.31(2.95+0.06) -7.6%
5303.9: rev-list (1000)   2.22(2.20+0.02)     2.23(2.19+0.03) +0.5%
5303.10: repack (1000)    10.47(16.78+0.22)   7.50(13.76+0.22) -28.4%

Not as impressive in terms of percentage, but still
measurable wins.  If you look at the wall-clock time
improvements in the 1000-pack case, you can see that linux
improved by roughly 10x as many seconds as git. That's
because it has roughly 10x as many objects, and we'd expect
this improvement to scale linearly with the number of
objects (since the number of packs is kept constant). It's
just that the "counting" phase is a smaller percentage of
the total time spent for a git.git repack, and hence the
percentage win is smaller.

The implementation itself is a straightforward use of the
MRU code. We only bother marking a pack as used when we know
that we are able to break early out of the loop, for two
reasons:

  1. If we can't break out early, it does no good; we have
     to visit each pack anyway, so we might as well avoid
     even the minor overhead of managing the cache order.

  2. The mru_mark() function reorders the list, which would
     screw up our traversal. So it is only safe to mark when
     we are about to break out of the loop. We could record
     the found pack and mark it after the loop finishes, of
     course, but that's more complicated and it doesn't buy
     us anything due to (1).

Note that this reordering does have a potential impact on
the final pack, as we store only a single "found" pack for
each object, even if it is present in multiple packs. In
principle, any copy is acceptable, as they all refer to the
same content. But in practice, they may differ in whether
they are stored as deltas, against which base, etc. This may
have an impact on delta reuse, and even the delta search
(since we skip pairs that were already in the same pack).

It's not clear whether this change of order would hurt or
even help average cases, though. The most likely reason to
have duplicate objects is from the completion of thin packs
(e.g., you have some objects, then receive several pushes;
the packs you receive may be thin on the wire, with deltas
that refer to bases outside the pack, but we complete them
with duplicate base objects when indexing them).

In such a case the current code would always find the thin
duplicates (because we currently walk the packs in reverse
chronological order). With this patch, it's possible that
some of them would be found in older packs instead. But
again, it's unclear whether that is a net win or loss in
practice.

Signed-off-by: Jeff King <peff@peff.net>
---
So obviously the "unclear" at the end makes me nervous. My gut feeling
is that it will be a wash (the existing ordering was simply what
happened to occur, and was not really planned for this particular use,
so there may be some small wins and some small losses which will cancel
out).  But unlike the original two optimizations, this has not been
deployed at GitHub, so I don't have any empirical data (and even if it
were, I'm not quite sure what I'd measure. I guess pack size, there's so
much noise in such a measurement I expect any change would be lost).

 builtin/pack-objects.c | 10 +++++++---
 1 file changed, 7 insertions(+), 3 deletions(-)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c4c2a3c..d686e08 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -23,6 +23,7 @@
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "mru.h"
 
 static const char *pack_usage[] = {
 	N_("git pack-objects --stdout [<options>...] [< <ref-list> | < <object-list>]"),
@@ -957,7 +958,7 @@ static int want_object_in_pack(const unsigned char *sha1,
 			       struct packed_git **found_pack,
 			       off_t *found_offset)
 {
-	struct packed_git *p;
+	struct mru_entry *entry;
 
 	if (!exclude && local && has_loose_object_nonlocal(sha1))
 		return 0;
@@ -965,7 +966,8 @@ static int want_object_in_pack(const unsigned char *sha1,
 	*found_pack = NULL;
 	*found_offset = 0;
 
-	for (p = packed_git; p; p = p->next) {
+	for (entry = packed_git_mru->head; entry; entry = entry->next) {
+		struct packed_git *p = entry->item;
 		off_t offset = find_pack_entry_one(sha1, p);
 		if (offset) {
 			if (!*found_pack) {
@@ -992,8 +994,10 @@ static int want_object_in_pack(const unsigned char *sha1,
 			 * out of the loop to return 1 now.
 			 */
 			if (!ignore_packed_keep &&
-			    (!local || !have_non_local_packs))
+			    (!local || !have_non_local_packs)) {
+				mru_mark(packed_git_mru, entry);
 				break;
+			}
 
 			if (local && !p->pack_local)
 				return 0;
-- 
2.9.2.607.g98dce7b

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

On Fri, Jul 29, 2016 at 12:15:24AM -0400, Jeff King wrote:

> Note that this reordering does have a potential impact on
> the final pack, as we store only a single "found" pack for
> each object, even if it is present in multiple packs. In
> principle, any copy is acceptable, as they all refer to the
> same content. But in practice, they may differ in whether
> they are stored as deltas, against which base, etc. This may
> have an impact on delta reuse, and even the delta search
> (since we skip pairs that were already in the same pack).
> 
> It's not clear whether this change of order would hurt or
> even help average cases, though. The most likely reason to
> have duplicate objects is from the completion of thin packs
> (e.g., you have some objects, then receive several pushes;
> the packs you receive may be thin on the wire, with deltas
> that refer to bases outside the pack, but we complete them
> with duplicate base objects when indexing them).
> 
> In such a case the current code would always find the thin
> duplicates (because we currently walk the packs in reverse
> chronological order). With this patch, it's possible that
> some of them would be found in older packs instead. But
> again, it's unclear whether that is a net win or loss in
> practice.

Hmm, so the efficacy of packing aside, this does definitely have a
negative effect.

I happened to have a repository sitting around that has 15 million
objects and 3600 packs (don't ask), so this seemed like a good test.

With this patch series, it took 11 minutes to do the counting, delta
compression, and write phases. Without it, after 11 minutes git had not
even gotten 10% of the way through counting. So that's good news.

The not-so-good news is that during the write phase, it hit the
"recursive delta detected" warning in write_one(), many times.

I think what is happening is that in the original code, we cannot ever
see a delta cycle, because the pack ordering is fixed. So if `A` is a
delta of `B`, then we know that they must both exist in the same pack
(since we do not do cross-pack deltas on disk). And because we look at
the packs in the same order for each object, we know that if we are
going to find `A`, we must either find `B` in the same pack (or a prior
one if there is another duplicate). But if we do so, then we cannot
also find `B` as a delta of `A` in that pack (because we know that packs
do not have delta cycles themselves) or an earlier pack (because if so,
we would have found `A` in that pack, too).

But because this series switches the order of pack-lookup between
objects, it is possible for us to find a `B` which is a delta against
`A` in one pack, and then another copy of `A` which is a delta against
another copy of `B` from another pack. We add both of the deltas to our
packing list, but at write time when we try to write out all of the
bases for `A`, we realize that whoops, we are recursing infinitely.

As it turns out, Git actually handles this pretty well! Upon noticing
the recursion, it breaks the delta chain and writes out one of the
objects as a full base. This is due to Junio's f63c79d (pack-object:
tolerate broken packs that have duplicated objects, 2011-11-16), though
I think we later decided that duplicated objects were simply insane.

So one option is to simply silence the warning, because the resulting
pack is perfectly fine. But we do notice this during the write phase,
after the delta search is done. So it's possible that the resulting pack
is not as small as it could be (i.e., we break the chain with a base
object, but it's possible if we looked that we could have broken the
chain by making a delta against an existing base object). So I wonder if
it's possible to detect this case earlier, during the "can we reuse this
delta" bits of check_object().

Suggestions welcome. I haven't really dug past what I've written here,
and it's way too late here to go any further tonight.

-Peff

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> On Fri, Jul 29, 2016 at 12:15:24AM -0400, Jeff King wrote:
>
> But because this series switches the order of pack-lookup between
> objects, it is possible for us to find a `B` which is a delta against
> `A` in one pack, and then another copy of `A` which is a delta against
> another copy of `B` from another pack. We add both of the deltas to our
> packing list, but at write time when we try to write out all of the
> bases for `A`, we realize that whoops, we are recursing infinitely.
>
> As it turns out, Git actually handles this pretty well! Upon noticing
> the recursion, it breaks the delta chain and writes out one of the
> objects as a full base. This is due to Junio's f63c79d (pack-object:
> tolerate broken packs that have duplicated objects, 2011-11-16), though
> I think we later decided that duplicated objects were simply insane.
>
> So one option is to simply silence the warning, because the resulting
> pack is perfectly fine.

Thanks for a great analysis.

My gut feeling is that keeping the warning is preferred if possible,
because f63c79db (pack-object: tolerate broken packs that have
duplicated objects, 2011-11-16) was made as the last ditch effort to
warn about the presence of the problem in the delta-base selection
code without harming the users.

> So it's possible that the resulting pack
> is not as small as it could be (i.e., we break the chain with a base
> object, but it's possible if we looked that we could have broken the
> chain by making a delta against an existing base object). So I wonder if
> it's possible to detect this case earlier, during the "can we reuse this
> delta" bits of check_object().

I'd let the issue simmer in my mind a bit for now, as I do not
think of a neat trick offhand.

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

On Fri, Jul 29, 2016 at 08:02:51AM -0700, Junio C Hamano wrote:

> > So it's possible that the resulting pack
> > is not as small as it could be (i.e., we break the chain with a base
> > object, but it's possible if we looked that we could have broken the
> > chain by making a delta against an existing base object). So I wonder if
> > it's possible to detect this case earlier, during the "can we reuse this
> > delta" bits of check_object().
>
> I'd let the issue simmer in my mind a bit for now, as I do not
> think of a neat trick offhand.

Sorry, I let this go a bit longer than intended. Here's where I'm at
with my thinking.

To recap the issue for those just joining us, the series in question
changes the order in which pack-objects will look at the existing
packfiles (in order to make the counting step faster when you have many
packs). This can introduce cycles in reused deltas because we might find
"A" as a delta of "B" in one pack, but "B" as a delta of "A" in another
pack. Whereas the current code, with a static pack ordering, will always
find such an "A" and "B" in the same pack, so as long as that pack does
not have a cycle, our set of reused deltas won't either.

The current code does detect the cycle, but not until the write phase
(at which point we issue a warning, throw out the delta, and output the
full object).

Here's a list of approaches I think we can use to fix this:

  1. squelch the warning and ignore it. The downside here, besides not
     warning the user about true in-pack cycles, is that we have no
     opportunity to actually find a new delta (because we realize the
     problem only after the delta-compression phase).

     My test repository is a bad packing of all of the forks of
     torvalds/linux, with 3600 packs. I'm happy to share it if anybody
     wants to see it, but note that it is 11GB.

     The space overhead of the resulting pack in this case is ~3.2%
     (versus a pack generated by the original code, using the static
     pack order).  Which is really not that bad, but I'm sure there are
     more pathological cases (i.e., there were on the order of hundreds
     or maybe thousands of cycles that needed broken, out of about 15
     million total objects; but one could imagine the worst case as
     nr_of_objects/2).

  2. break the cycles in check_object(), when we consider whether we can
     reuse the delta.

     The obvious advantage here (over breaking it in the writing phase)
     is that we can then feed the object into the normal
     delta-compression phase.

     The question is: how?

     2a. One way to do so is to provide a total ordering over the packs.
	 I.e., if "A" is a delta of "B", then allow the delta to be
	 reused iff the pack containing "A" sorts before or equal to the
	 pack containing "B". The actual ordering doesn't matter for
	 purposes of the cycle-breaking, as long as its consistent.

	 I implemented this using the mtime of the packs (breaking ties
	 by their names), as that would give us results close to the

	 Unsurprisingly, this adds a bit of CPU time (because we have
	 more delta objects to search), though it's dwarfed by the wins
	 you get from the sped-up counting phase (in my tests, 20
	 seconds of extra delta search for 39 minutes of "counting
	 objects" savings).

	 But it doesn't actually help the resulting pack size. It's
	 still about 3.2% overhead (it's actually just slightly worse
	 than case 1).

	 I think what happens is that we throw out a lot of deltas, even
	 ones that _aren't_ cycles, but just happened to be found in
	 packs that are "backwards" in the total order. And then we have
	 to do a delta search on them, but of course that can't always
	 find a good match.

	 I also tried two other variants here. The pack order for the
	 cycle-breaking step shouldn't matter, so I wondered what would
	 happen if I reversed it. It does indeed produce different
	 results. The resulting pack is slightly better, at 2.6%
	 overhead. But we spend even more time looking for deltas (IOW,
	 we threw out more of them).

	 I also tried bumping the pack window size, under the theory
	 that maybe we just aren't finding great deltas for the ones we
	 throw out. But it didn't seem to make much difference.

	 So I like the simplicity of this idea (which, by the way, was
	 not mine, but came from an off-list discussion with Michael).
	 But I think it's a dead-end, because it throws away too many
	 deltas that _could_ be reused.

     2b. Another option is to do real cycle analysis, and break the
         cycles.

	 This is tricky to do in check_object() because we are actually
	 filling out the delta pointers as we go. So I think we would
	 have to make two passes: one to come up with a tentative list
	 of deltas to reuse, and then one to check them for cycles.

	 If done right, the cycle check should be linear in the number
	 of objects (it's basically a depth-first search). In fact, I
	 think it would look a lot like what write_object() is doing.
	 We'd just be moving the logic _before_ the delta-compression
	 phase, instead of after.

	 This is the one approach I've considered but have not yet
	 implemented. So no numbers.

  3. Pick a consistent pack order up front, and stop changing it
     mid-search.

     The question, of course, is which order.

     For my test repo, this is actually pretty easy. There's one
     gigantic pack with 15 million objects in it, and then 3600 small
     packs with a handful of objects from pushes. The giant pack is the
     oldest, so the normal "reverse chronological" pack order makes
     counting effectively O(m*n), because the majority of the objects
     are found in the very last pack.

     So an obvious thing to try is just reversing it. And indeed, the
     counting is quite fast then (similar to the MRU numbers). Though of
     course one can come up with a case where the objects are more
     evenly split across the packs, and it would not help (you can come
     up with pathological cases for MRU, too, but they're much less
     likely in practice, because it's really exploiting locality).

     But I was surprised to find that the resulting pack is even worse,
     at 4.5% overhead.

     I can't really explain that, and I'm starting to come to the
     conclusion that there's a fair bit of luck and black magic involved
     in delta reuse. I would not be at all surprised to find a test case
     where reversing the order actually _improved_ things.

     It may be that the numbers I saw in my (2a) tests were not because
     we broke deltas and couldn't find replacements, but simply because
     we get more and better deltas by looking in the smaller, newer
     packs first.

So that's where I'm at. Mostly puzzled, and wondering if any of my
experiments were even valid or showing anything interesting, and not
just somewhat random artifacts of the deltas that happen to be in this
particular test case. Worse, it may be that looking in the small packs
_is_ objectively better, and we're losing that in any kind of
pack-ordering changes (which is an inherent part of my speed-up strategy
for the counting phase[1]).

I've yet to implement 2b, true cycle-detection before delta-compression.
But I have a feeling it will somehow show that my resulting pack is
about 3% worse. :-/

-Peff

[1] So obviously one option is to figure out a way to speed up the
    counting phase without changing the pack order. The only way I can
    think of is to build a master object index, where each entry has all
    of the packs that a given object can be found in, in their correct
    pack order.

    That would be fairly easy to implement as a hash table, but:

      - it would require a fair bit of memory; the pack .idx for this
	repo is 500MB, and we usually get to just mmap it. OTOH, the
	biggest part of that is the sha1s, so we could possibly just
	reference them by pointer into the mmap'd data. And it's not
	like you don't need much more than 500MB to hold the list of
	objects to pack.

      - it's inherently O(nr_of_objects_in_repo) in CPU and memory to
	build the index, whereas some operations are
	O(nr_of_objects_to_be_packed). In this case it's probably OK (we
	do pay for extra entries for each of the duplicates, but it's
	largely on the order of 15 million objects). But it's a big
	expense if you're just packing a few of the objects.

    So I dunno. I really like the MRU approach if we can salvage it.

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Here's a list of approaches I think we can use to fix this:
>
>   1. squelch the warning and ignore it. The downside here, besides not
>      warning the user about true in-pack cycles, is that we have no
>      opportunity to actually find a new delta (because we realize the
>      problem only after the delta-compression phase).
>
>      My test repository is a bad packing of all of the forks of
>      torvalds/linux, with 3600 packs. I'm happy to share it if anybody
>      wants to see it, but note that it is 11GB.
>
>      The space overhead of the resulting pack in this case is ~3.2%
>      (versus a pack generated by the original code, using the static
>      pack order).  Which is really not that bad, but I'm sure there are
>      more pathological cases (i.e., there were on the order of hundreds
>      or maybe thousands of cycles that needed broken, out of about 15
>      million total objects; but one could imagine the worst case as
>      nr_of_objects/2).
> ...
>
>     So I dunno. I really like the MRU approach if we can salvage it.

I think I share the same feeling.  As long as the chance is small
enough that the pack reordering creates a new cycle, the resulting
pack would not become too bloated by the last-ditch cycle breaking
code and finding a replacement delta instead of inflating it may not
be worth the trouble.

It worries me a lot to lose the warning unconditionally, though.
That's the (only) coal-mine canary that lets us notice a problem
when we actually start hitting that last-ditch cycle breaking too
often.

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

On Mon, Aug 08, 2016 at 09:28:29AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > Here's a list of approaches I think we can use to fix this:
> >
> >   1. squelch the warning and ignore it. The downside here, besides not
> >      warning the user about true in-pack cycles, is that we have no
> >      opportunity to actually find a new delta (because we realize the
> >      problem only after the delta-compression phase).
> >
> >      My test repository is a bad packing of all of the forks of
> >      torvalds/linux, with 3600 packs. I'm happy to share it if anybody
> >      wants to see it, but note that it is 11GB.
> >
> >      The space overhead of the resulting pack in this case is ~3.2%
> >      (versus a pack generated by the original code, using the static
> >      pack order).  Which is really not that bad, but I'm sure there are
> >      more pathological cases (i.e., there were on the order of hundreds
> >      or maybe thousands of cycles that needed broken, out of about 15
> >      million total objects; but one could imagine the worst case as
> >      nr_of_objects/2).
> > ...
> >
> >     So I dunno. I really like the MRU approach if we can salvage it.
> 
> I think I share the same feeling.  As long as the chance is small
> enough that the pack reordering creates a new cycle, the resulting
> pack would not become too bloated by the last-ditch cycle breaking
> code and finding a replacement delta instead of inflating it may not
> be worth the trouble.

Let me see how complicated it is to do the cycle-detection earlier. It
really shouldn't be that hard (we don't even need an auxiliary data
structure; we can just smudge the index value like write_object does).
I'm very curious to see the pack resulting pack size.

> It worries me a lot to lose the warning unconditionally, though.
> That's the (only) coal-mine canary that lets us notice a problem
> when we actually start hitting that last-ditch cycle breaking too
> often.

The dedicated cycle-detection will lose that warning, too (it doesn't
touch that code, but it's effectively checking the same thing earlier).

I agree it's unfortunate to lose. On the other hand, it is being lost
because we are correctly handling the cycles, and there is nothing to
warn about. So it ceases to be a problem, and starts being a normal,
acceptable thing.

-Peff

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>> It worries me a lot to lose the warning unconditionally, though.
>> That's the (only) coal-mine canary that lets us notice a problem
>> when we actually start hitting that last-ditch cycle breaking too
>> often.
>
> The dedicated cycle-detection will lose that warning, too (it doesn't
> touch that code, but it's effectively checking the same thing earlier).
>
> I agree it's unfortunate to lose. On the other hand, it is being lost
> because we are correctly handling the cycles, and there is nothing to
> warn about. So it ceases to be a problem, and starts being a normal,
> acceptable thing.

That unfortunately is beside the point.  The existing cycle breaking
was meant to be a last ditch effort to avoid producing a broken pack
(i.e. a suboptimal pack without cycle is better than unusable pack
with delta cycle), while letting us know that we found a case where
the remainder of the pack building machinery does not function well
without it (so that we know we broke something when we tweaked the
machinery without intending to break it).  Squelching the warnings
feels similar to "we see too many valgrind warnings, so let's stop
running valgrind"; I was hoping there would be a solution more like
"instead of not running, let's teach valgrind this and that codepath
is OK".

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

On Mon, Aug 08, 2016 at 10:16:32AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> >> It worries me a lot to lose the warning unconditionally, though.
> >> That's the (only) coal-mine canary that lets us notice a problem
> >> when we actually start hitting that last-ditch cycle breaking too
> >> often.
> >
> > The dedicated cycle-detection will lose that warning, too (it doesn't
> > touch that code, but it's effectively checking the same thing earlier).
> >
> > I agree it's unfortunate to lose. On the other hand, it is being lost
> > because we are correctly handling the cycles, and there is nothing to
> > warn about. So it ceases to be a problem, and starts being a normal,
> > acceptable thing.
> 
> That unfortunately is beside the point.  The existing cycle breaking
> was meant to be a last ditch effort to avoid producing a broken pack
> (i.e. a suboptimal pack without cycle is better than unusable pack
> with delta cycle), while letting us know that we found a case where
> the remainder of the pack building machinery does not function well
> without it (so that we know we broke something when we tweaked the
> machinery without intending to break it).  Squelching the warnings
> feels similar to "we see too many valgrind warnings, so let's stop
> running valgrind"; I was hoping there would be a solution more like
> "instead of not running, let's teach valgrind this and that codepath
> is OK".

I don't think there is a way to do "this code path is OK", exactly.
Though by putting cycle-breaking at the check_object() stage, the
warning at the write_object() stage would continue to ensure that we
don't introduce any new cycles with our delta search. So that does have
some value.

Here's the code to do the cycle-breaking. Aside from the "hacky" bit,
it's quite simple.  I added a new state enum to object_entry to handle
the graph traversal. Since it only needs 2 bits, I _assume_ a compiler
can fit it in with the bitfields above (or at the very least give it its
own single byte so we just use what would otherwise be struct padding).
But I didn't check; if it turns out not to be the case we can easily
emulate it with two bitfields.  The write_object() check abuses the
"idx.offset" field to keep the same state, but we could convert it to
use these flags if we care.

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index c91d54a..07b6fea 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1499,6 +1499,67 @@ static int pack_offset_sort(const void *_a, const void *_b)
 			(a->in_pack_offset > b->in_pack_offset);
 }
 
+/*
+ * Follow the chain of deltas from this entry onward, throwing away any links
+ * that cause us to hit a cycle (as determined by the DFS state flags in
+ * the entries).
+ */
+static void break_delta_cycles(struct object_entry *entry)
+{
+	/* If it's not a delta, it can't be part of a cycle. */
+	if (!entry->delta) {
+		entry->dfs_state = DFS_DONE;
+		return;
+	}
+
+	switch (entry->dfs_state) {
+	case DFS_NONE:
+		/*
+		 * This is the first time we've seen the object. We become part
+		 * of the active potential cycle and recurse.
+		 */
+		entry->dfs_state = DFS_ACTIVE;
+		break_delta_cycles(entry->delta);
+		entry->dfs_state = DFS_DONE;
+		break;
+
+	case DFS_DONE:
+		/* object already examined, and not part of a cycle */
+		break;
+
+	case DFS_ACTIVE:
+		/*
+		 * We found a cycle that needs broken. We have to not only
+		 * drop our entry->delta link, but we need to remove
+		 * ourselves from the delta_sibling chain of our base.
+		 */
+		{
+			struct object_entry **p = &entry->delta->delta_child;
+			while (*p) {
+				if (*p == entry)
+					*p = (*p)->delta_sibling;
+				else
+					p = &(*p)->delta_sibling;
+			}
+		}
+		entry->delta = NULL;
+
+		/*
+		 * XXX This is hacky. We need to figure out our real size (not
+		 * the delta size). check_object() already does this, so let's
+		 * just re-run it, but telling it not to reuse any deltas. This
+		 * probably should just be a single function to track down the
+		 * size from the delta (or even just sha1_object_info(),
+		 * though that is a little less efficient because we already
+		 * know which pack we're in).
+		 */
+		reuse_delta = 0;
+		check_object(entry);
+		reuse_delta = 1;
+		break;
+	}
+}
+
 static void get_object_details(void)
 {
 	uint32_t i;
@@ -1516,6 +1577,13 @@ static void get_object_details(void)
 			entry->no_try_delta = 1;
 	}
 
+	/*
+	 * This must happen in a second pass, since we rely on the delta
+	 * information for the whole list being completed.
+	 */
+	for (i = 0; i < to_pack.nr_objects; i++)
+		break_delta_cycles(&to_pack.objects[i]);
+
 	free(sorted_by_offset);
 }
 
diff --git a/pack-objects.h b/pack-objects.h
index d1b98b3..cc9b9a9 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -27,6 +27,15 @@ struct object_entry {
 	unsigned no_try_delta:1;
 	unsigned tagged:1; /* near the very tip of refs */
 	unsigned filled:1; /* assigned write-order */
+
+	/*
+	 * State flags for depth-first search used for analyzing delta cycles.
+	 */
+	enum {
+		DFS_NONE = 0,
+		DFS_ACTIVE,
+		DFS_DONE
+	} dfs_state;
 };
 
 struct packing_data {


It seems to perform well, and it does break the cycles (the later check
during the write does not kick in, and we get no warnings). I didn't dig
into the fates of specific objects, but any cycles should be added to
the delta-compression phase.

The resulting pack size is almost exactly what it was with hitting the
write_object() check. So that means all of my testing was really not
that interesting, because the extra space isn't coming from the delta
cycles at all. It's simply an artifact of the different set of objects
we happen to find (just as reversing the pack list produces a different
order, with a different size).

So it happens to be a 3% loss in this case. I'm not convinced it would
not actually be a win in some other cases. But more importantly, in a
repository with fewer packs, it would likely be a much smaller
difference (in either direction), just because there's less play in
where we find a given object.

I think my preference is to clean up the "hacky" bit of this patch, and
then apply the earlier MRU patch on top of it (which takes my repack
from 44 minutes to 5 minutes for this particular test set). I see you
graduated the earlier bits of the series to "master" already.

-Peff

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Jeff King]

On Tue, Aug 09, 2016 at 10:04:11AM -0400, Jeff King wrote:

> Here's the code to do the cycle-breaking.
> [...]
> It seems to perform well, and it does break the cycles (the later check
> during the write does not kick in, and we get no warnings). I didn't dig
> into the fates of specific objects, but any cycles should be added to
> the delta-compression phase.

Curious about that last part, I did the repack both with and without
this patch. We should be able to see the difference in the progress
meter from the "Compressing" phase. And indeed, it goes from 3030778
objects to 3031056, an increase of 278 objects. Which just so happens to
be exactly the number of "warning: recursive delta detected" lines that
are printed without the patch.

Not surprising, but a nice confirmation that everything is working as
expected.  But while looking at this, I managed to unravel what's been
going on this whole time.

I ran the repack again with stock git (no MRU patch), and the number of
objects in the delta phase jumped to 3087880, around 56,000 more than
with the MRU patch. So that's probably where the magic "3%" is coming
from.  By looking at the smaller packs first, we are more likely to find
copies of objects which _aren't_ deltas, and then consider them for
delta compression. And that compression tends to find a better match
than reusing what was in the big pack, and we end up with a slightly
smaller output pack.

So why are the deltas we find so much better than what is in the big
pack?

There's something rather subtle going on, and it has to do with the fact
that the existing pack was _not_ made by a stock version of git.

I may have mentioned before that I have some patches which restrict the
delta selection process. The goal is that if you have several "islands"
of refs (in my case, refs corresponding to particular forks of a
repository), it's desirable that you don't make a delta against a base
that is not reachable from all of the same islands. Otherwise, when
somebody fetches or clones the fork, you have to throw away the delta
and find one from scratch. If this happens a lot, it gets expensive.
Unsurprisingly, the packfiles produced with the island-restrictions
turned on are slightly worse than normal packfiles (because we reject
some delta possibilities that might be better).

When I did my testing, I did not enable the delta islands, because I
didn't want them to influence the results. But of course their effect
could still be seen in the deltas in the existing packfile, because it
came off our production servers (because I wanted a real-world test
case). So any pack ordering which ends up reusing _fewer_ of those
deltas is going to be a net win in size, because it's going to find new
deltas without being hampered by the island restrictions. And that's
exactly what happened in my tests; the stock pack ordering finds more
objects in the newer packs, has fewer deltas to reuse, and is able to
find better unrestricted deltas.

Unfortunately I don't have a real-world test case that's been packed up
until now with stock git. So the next-best thing I can do is re-run my
tests with the island restrictions turned on, so that newly-found deltas
do not have an unfair advantage. And here are the sizes for each case
after doing so:

  7848512375 before.git/objects/pack/pack-2f5878f6569cd6682e7084318de311ed26d19af5.pack
  7851778788 mru.git/objects/pack/pack-7694766c660eaa0e27e4e51a77bd5c457c3d2f1d.pack
  7851165480 cycle-break.git/objects/pack/pack-cfaceb3423993c72e4ac588c30c94da2d087145a.pack

The MRU case _is_ slightly bigger, but only by 0.04%. And then adding
the cycle-breaking on top of that reclaims a little bit of space,
because rather than throwing out those 287 deltas at the write phase,
it's able to add those objects back to the delta search and find new
deltas for them.

So there. Mystery solved, and I feel confident in saying that the MRU
patches _don't_ represent a real regression in pack size. We do need to
deal with the cycles, of course, but it's less an issue of size and more
one of correctness (well, the pack is correct either way, but still, it
seems more correct to realize during the correct phase that we cannot
reuse those deltas).

I also suspect that one of the tricks I tried, simply reversing the pack
order (so the big pack is at the front, but the order is stable) would
work very well for this case. But as I mentioned before, I prefer the
MRU strategy because it's less susceptible to pathological cases.

-Peff

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> I ran the repack again with stock git (no MRU patch), and the number of
> objects in the delta phase jumped to 3087880, around 56,000 more than
> with the MRU patch. So that's probably where the magic "3%" is coming
> from.  By looking at the smaller packs first, we are more likely to find
> copies of objects which _aren't_ deltas, and then consider them for
> delta compression. And that compression tends to find a better match
> than reusing what was in the big pack, and we end up with a slightly
> smaller output pack.

Yeah, that is a very plausible explanation.

> So why are the deltas we find so much better than what is in the big
> pack?
>
> There's something rather subtle going on, and it has to do with the fact
> that the existing pack was _not_ made by a stock version of git.

;-)

> I may have mentioned before that I have some patches which restrict the
> delta selection process. The goal is that if you have several "islands"
> of refs (in my case, refs corresponding to particular forks of a
> repository), it's desirable that you don't make a delta against a base
> that is not reachable from all of the same islands. 

That also explains it.  It is expected (small) price to pay to
ensure the islands are standalone.

> I also suspect that one of the tricks I tried, simply reversing the pack
> order (so the big pack is at the front, but the order is stable) would
> work very well for this case. But as I mentioned before, I prefer the
> MRU strategy because it's less susceptible to pathological cases.

Yup, excellent.  Thanks for working on this.

Re: [PATCH v2 7/7] pack-objects: use mru list when iterating over packs

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> Here's the code to do the cycle-breaking. Aside from the "hacky" bit,
> it's quite simple.  I added a new state enum to object_entry to handle
> the graph traversal. Since it only needs 2 bits, I _assume_ a compiler
> can fit it in with the bitfields above (or at the very least give it its
> own single byte so we just use what would otherwise be struct padding).
> But I didn't check; if it turns out not to be the case we can easily
> emulate it with two bitfields.  The write_object() check abuses the
> "idx.offset" field to keep the same state, but we could convert it to
> use these flags if we care.

> @@ -1516,6 +1577,13 @@ static void get_object_details(void)
>  			entry->no_try_delta = 1;
>  	}
>  
> +	/*
> +	 * This must happen in a second pass, since we rely on the delta
> +	 * information for the whole list being completed.
> +	 */
> +	for (i = 0; i < to_pack.nr_objects; i++)
> +		break_delta_cycles(&to_pack.objects[i]);
> +
>  	free(sorted_by_offset);
>  }

A potential cycle can only come from reusing deltas across packs in
an unstable order, that happens way before we do the find_delta()
thing, so this is a good place to have the new call.  While reading
break_delta_cycles(), I was wondering if what it does is safe under
multi-threading but there is no need to worry.

The recursiveness of break-delta-cycles is not too bad for the same
reason why it is OK to recurse in check_delta_limit(), I would guess?

This is not new with this change, but I am not quite sure what in
the current code prevents us from busting the delta limit for reused
ones, though.

> I think my preference is to clean up the "hacky" bit of this patch, and
> then apply the earlier MRU patch on top of it (which takes my repack
> from 44 minutes to 5 minutes for this particular test set).

Yup, with something like this to break the delta chain _and_ allow
an object to go through the usual deltify machinery, I'd say the MRU
patch is a wonderful thing to have.

[PATCH v3 0/2] pack-objects mru

[Jeff King]

On Tue, Aug 09, 2016 at 03:29:33PM -0700, Junio C Hamano wrote:

> > @@ -1516,6 +1577,13 @@ static void get_object_details(void)
> >  			entry->no_try_delta = 1;
> >  	}
> >  
> > +	/*
> > +	 * This must happen in a second pass, since we rely on the delta
> > +	 * information for the whole list being completed.
> > +	 */
> > +	for (i = 0; i < to_pack.nr_objects; i++)
> > +		break_delta_cycles(&to_pack.objects[i]);
> > +
> >  	free(sorted_by_offset);
> >  }
> 
> A potential cycle can only come from reusing deltas across packs in
> an unstable order, that happens way before we do the find_delta()
> thing, so this is a good place to have the new call.  While reading
> break_delta_cycles(), I was wondering if what it does is safe under
> multi-threading but there is no need to worry.

It definitely is not multi-threaded safe (and I'm not sure it could
easily be made so). But yeah, it is quick and happens as part of the
get_object_details() look at the objects, which is where we make
decisions about delta reuse.

> The recursiveness of break-delta-cycles is not too bad for the same
> reason why it is OK to recurse in check_delta_limit(), I would guess?

Yes, and for the same reason that it is OK in write_one(); the recursion
is limited by the depth of the delta chains.

> This is not new with this change, but I am not quite sure what in
> the current code prevents us from busting the delta limit for reused
> ones, though.

I think in the current code you are limited by the depth you might find
in a single existing pack (since we never reuse cross-pack deltas).
There is a comment in check_object() that claims:

	* Depth value does not matter - find_deltas() will
	* never consider reused delta as the base object to
	* deltify other objects against, in order to avoid
	* circular deltas.

but I do not recall seeing code to enforce that (but presumably that is
just beacuse it is a corner of the code I have not seen yet).

However, I think with cross-pack deltas, you could have a situation
like:

  pack 1: A -> B -> C
  pack 2: C -> D -> E

and pick A and B from the first pack, and C, D, and E from the second.
Then you end up with:

  A -> B -> C -> D -> E

in the output. IOW, I think the absolute worst case chain is the
max_depth times the number of packs. In practice I'd expect it to be
much smaller.

I'm not sure how much we should be worried about it. We could fill in
the depth values when adding a reused delta, but I don't think we have
the number handy; we'd have to actually walk the chain (though with
delta-base-offset, that is reasonably cheap).

> > I think my preference is to clean up the "hacky" bit of this patch, and
> > then apply the earlier MRU patch on top of it (which takes my repack
> > from 44 minutes to 5 minutes for this particular test set).
> 
> Yup, with something like this to break the delta chain _and_ allow
> an object to go through the usual deltify machinery, I'd say the MRU
> patch is a wonderful thing to have.

Here are cleaned-up patches. The cycle-breaking patch is cleaned up and
has tests. I erred on the side of verbosity in the comments there,
because it literally took me hours to come up with a reliable working
set of commands (and a convincing argument that it's correct). Hopefully
it doesn't put anyone to sleep. :)

The second patch is the same as before, though I tweaked the commit
message a bit, so please replace what is at the tip of
jk/pack-objects-optim-mru.

  [1/2]: pack-objects: break delta cycles before delta-search phase
  [2/2]: pack-objects: use mru list when iterating over packs

-Peff

[PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase

[Jeff King]

We do not allow cycles in the delta graph of a pack (i.e., A
is a delta of B which is a delta of A) for the obvious
reason that you cannot actually access any of the objects in
such a case.

There's a last-ditch attempt to notice cycles during the
write phase, during which we issue a warning to the user and
write one of the objects out in full. However, this is
"last-ditch" for two reasons:

  1. By this time, it's too late to find another delta for
     the object, so the resulting pack is larger than it
     otherwise could be.

  2. The warning is there because this is something that
     _shouldn't_ ever happen. If it does, then either:

       a. a pack we are reusing deltas from had its own
          cycle

       b. we are reusing deltas from multiple packs, and
          we found a cycle among them (i.e., A is a delta of
          B in one pack, but B is a delta of A in another,
          and we choose to use both deltas).

       c. there is a bug in the delta-search code

     So this code serves as a final check that none of these
     things has happened, warns the user, and prevents us
     from writing a bogus pack.

Right now, (2b) should never happen because of the static
ordering of packs in want_object_in_pack(). If two objects
have a delta relationship, then they must be in the same
pack, and therefore we will find them from that same pack.

However, a future patch would like to change that static
ordering, which will make (2b) a common occurrence. In
preparation, we should be able to handle those kinds of
cycles better. This patch does by introducing a
cycle-breaking step during the get_object_details() phase,
when we are deciding which deltas can be reused. That gives
us the chance to feed the objects into the delta search as
if the cycle did not exist.

We'll leave the detection and warning in the write_object()
phase in place, as it still serves as a check for case (2c).

This does mean we will stop warning for (2a). That case is
caused by bogus input packs, and we ideally would warn the
user about it.  However, since those cycles show up after
picking reusable deltas, they look the same as (2b) to us;
our new code will break the cycles early and the last-ditch
check will never see them.

We could do analysis on any cycles that we find to
distinguish the two cases (i.e., it is a bogus pack if and
only if every delta in the cycle is in the same pack), but
we don't need to. If there is a cycle inside a pack, we'll
run into problems not only reusing the delta, but accessing
the object data at all. So when we try to dig up the actual
size of the object, we'll hit that same cycle and kick in
our usual complain-and-try-another-source code.

Signed-off-by: Jeff King <peff@peff.net>
---
Actually, skimming the sha1_file code, I am not 100% sure that we detect
cycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since
they always point backwards in the pack). But if that is the case, then
I think we should fix that, not worry about special-casing it here.

 builtin/pack-objects.c          |  83 +++++++++++++++++++++++++++++
 pack-objects.h                  |   9 ++++
 t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 205 insertions(+)
 create mode 100755 t/t5314-pack-cycle-detection.sh

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 4a63398..3e30eae 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1495,6 +1495,82 @@ static int pack_offset_sort(const void *_a, const void *_b)
 			(a->in_pack_offset > b->in_pack_offset);
 }
 
+/*
+ * Drop an on-disk delta we were planning to reuse. Naively, this would
+ * just involve blanking out the "delta" field, but we have to deal
+ * with two extra pieces of book-keeping:
+ *
+ *   1. Removing ourselves from the delta_sibling linked list.
+ *
+ *   2. Updating our size; check_object() will have filled in the size of our
+ *      delta, but a non-delta object needs it true size.
+ */
+static void drop_reused_delta(struct object_entry *entry)
+{
+	struct object_entry **p = &entry->delta->delta_child;
+	struct pack_window *w_curs = NULL;
+
+	while (*p) {
+		if (*p == entry)
+			*p = (*p)->delta_sibling;
+		else
+			p = &(*p)->delta_sibling;
+	}
+	entry->delta = NULL;
+
+	entry->size = get_size_from_delta(entry->in_pack, &w_curs,
+			  entry->in_pack_offset + entry->in_pack_header_size);
+	unuse_pack(&w_curs);
+
+	/*
+	 * If we failed to get the size from this pack for whatever reason,
+	 * fall back to sha1_object_info, which may find another copy. And if
+	 * that fails, the error will be recorded in entry->type and dealt
+	 * with in prepare_pack().
+	 */
+	if (entry->size == 0)
+		entry->type = sha1_object_info(entry->idx.sha1, &entry->size);
+}
+
+/*
+ * Follow the chain of deltas from this entry onward, throwing away any links
+ * that cause us to hit a cycle (as determined by the DFS state flags in
+ * the entries).
+ */
+static void break_delta_cycles(struct object_entry *entry)
+{
+	/* If it's not a delta, it can't be part of a cycle. */
+	if (!entry->delta) {
+		entry->dfs_state = DFS_DONE;
+		return;
+	}
+
+	switch (entry->dfs_state) {
+	case DFS_NONE:
+		/*
+		 * This is the first time we've seen the object. We mark it as
+		 * part of the active potential cycle and recurse.
+		 */
+		entry->dfs_state = DFS_ACTIVE;
+		break_delta_cycles(entry->delta);
+		entry->dfs_state = DFS_DONE;
+		break;
+
+	case DFS_DONE:
+		/* object already examined, and not part of a cycle */
+		break;
+
+	case DFS_ACTIVE:
+		/*
+		 * We found a cycle that needs broken. It would be correct to
+		 * break any link in the chain, but it's convenient to
+		 * break this one.
+		 */
+		drop_reused_delta(entry);
+		break;
+	}
+}
+
 static void get_object_details(void)
 {
 	uint32_t i;
@@ -1512,6 +1588,13 @@ static void get_object_details(void)
 			entry->no_try_delta = 1;
 	}
 
+	/*
+	 * This must happen in a second pass, since we rely on the delta
+	 * information for the whole list being completed.
+	 */
+	for (i = 0; i < to_pack.nr_objects; i++)
+		break_delta_cycles(&to_pack.objects[i]);
+
 	free(sorted_by_offset);
 }
 
diff --git a/pack-objects.h b/pack-objects.h
index d1b98b3..cc9b9a9 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -27,6 +27,15 @@ struct object_entry {
 	unsigned no_try_delta:1;
 	unsigned tagged:1; /* near the very tip of refs */
 	unsigned filled:1; /* assigned write-order */
+
+	/*
+	 * State flags for depth-first search used for analyzing delta cycles.
+	 */
+	enum {
+		DFS_NONE = 0,
+		DFS_ACTIVE,
+		DFS_DONE
+	} dfs_state;
 };
 
 struct packing_data {
diff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh
new file mode 100755
index 0000000..db9d71b
--- /dev/null
+++ b/t/t5314-pack-cycle-detection.sh
@@ -0,0 +1,113 @@
+#!/bin/sh
+
+test_description='test handling of inter-pack delta cycles during repack
+
+The goal here is to create a situation where we have two blobs, A and B, with A
+as a delta against B in one pack, and vice versa in the other. Then if we can
+persuade a full repack to find A from one pack and B from the other, that will
+give us a cycle when we attempt to reuse those deltas.
+
+The trick is in the "persuade" step, as it depends on the internals of how
+pack-objects picks which pack to reuse the deltas from. But we can assume
+that it does so in one of two general strategies:
+
+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can
+    happen. Any objects with a delta relationship must be present in the same
+    pack (i.e., no "--thin" packs on disk), so we will find all related objects
+    from that pack. So assuming there are no cycles within a single pack (and
+    we avoid generating them via pack-objects or importing them via
+    index-pack), then our result will have no cycles.
+
+    So this case should pass the tests no matter how we arrange things.
+
+ 2. Picking the next pack to examine based on locality (i.e., where we found
+    something else recently).
+
+    In this case, we want to make sure that we find the delta versions of A and
+    B and not their base versions. We can do this by putting two blobs in each
+    pack. The first is a "dummy" blob that can only be found in the pack in
+    question.  And then the second is the actual delta we want to find.
+
+    The two blobs must be present in the same tree, not present in other trees,
+    and the dummy pathname must sort before the delta path.
+
+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each
+which has two files: "dummy" and "file". Then we can make two packs which
+contain:
+
+  [pack one]
+  HEAD:dummy
+  HEAD:file  (as delta against HEAD^:file)
+  HEAD^:file (as base)
+
+  [pack two]
+  HEAD^:dummy
+  HEAD^:file (as delta against HEAD:file)
+  HEAD:file  (as base)
+
+Then no matter which order we start looking at the packs in, we know that we
+will always find a delta for "file", because its lookup will always come
+immediately after the lookup for "dummy".
+'
+. ./test-lib.sh
+
+
+
+# Create a pack containing the the tree $1 and blob $1:file, with
+# the latter stored as a delta against $2:file.
+#
+# We convince pack-objects to make the delta in the direction of our choosing
+# by marking $2 as a preferred-base edge. That results in $1:file as a thin
+# delta, and index-pack completes it by adding $2:file as a base.
+#
+# Note that the two variants of "file" must be similar enough to convince git
+# to create the delta.
+make_pack () {
+	 {
+		 echo "-$(git rev-parse $2)"
+		 echo "$(git rev-parse $1:dummy) dummy"
+		 echo "$(git rev-parse $1:file) file"
+	 } |
+	 git pack-objects --stdout |
+	 git index-pack --stdin --fix-thin
+}
+
+test_expect_success 'setup' '
+	test-genrandom base 4096 >base &&
+	for i in one two
+	do
+		# we want shared content here to encourage deltas...
+		cp base file &&
+		echo $i >>file &&
+
+		# ...whereas dummy should be short, because we do not want
+		# deltas that would create duplicates when we --fix-thin
+		echo $i >dummy &&
+
+		git add file dummy &&
+		test_tick &&
+		git commit -m $i ||
+		return 1
+	done &&
+
+	make_pack HEAD^ HEAD &&
+	make_pack HEAD HEAD^
+'
+
+test_expect_success 'repack' '
+	# We first want to check that we do not have any internal errors,
+	# and also that we do not hit the last-ditch cycle-breaking code
+	# in write_object(), which will issue a warning to stderr.
+	>expect &&
+	git repack -ad 2>stderr &&
+	test_cmp expect stderr &&
+
+	# And then double-check that the resulting pack is usable (i.e.,
+	# we did not fail to notice any cycles). We know we are accessing
+	# the objects via the new pack here, because "repack -d" will have
+	# removed the others.
+	git cat-file blob HEAD:file >/dev/null &&
+	git cat-file blob HEAD^:file >/dev/null
+'
+
+test_done
-- 
2.9.2.790.gaa5bc72

Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> ...
> We could do analysis on any cycles that we find to
> distinguish the two cases (i.e., it is a bogus pack if and
> only if every delta in the cycle is in the same pack), but
> we don't need to. If there is a cycle inside a pack, we'll
> run into problems not only reusing the delta, but accessing
> the object data at all. So when we try to dig up the actual
> size of the object, we'll hit that same cycle and kick in
> our usual complain-and-try-another-source code.

I agree with all of the above reasoning.

> Actually, skimming the sha1_file code, I am not 100% sure that we detect
> cycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since
> they always point backwards in the pack). But if that is the case, then
> I think we should fix that, not worry about special-casing it here.

Yes, but sha1_file.c?  It is the reading side and it is too late if
we notice a problem, I would think.

> +/*
> + * Drop an on-disk delta we were planning to reuse. Naively, this would
> + * just involve blanking out the "delta" field, but we have to deal
> + * with two extra pieces of book-keeping:
> + *
> + *   1. Removing ourselves from the delta_sibling linked list.
> + *
> + *   2. Updating our size; check_object() will have filled in the size of our
> + *      delta, but a non-delta object needs it true size.

Excellent point.

> +/*
> + * Follow the chain of deltas from this entry onward, throwing away any links
> + * that cause us to hit a cycle (as determined by the DFS state flags in
> + * the entries).
> + */
> +static void break_delta_cycles(struct object_entry *entry)
> +{
> +	/* If it's not a delta, it can't be part of a cycle. */
> +	if (!entry->delta) {
> +		entry->dfs_state = DFS_DONE;
> +		return;
> +	}
> +
> +	switch (entry->dfs_state) {
> +	case DFS_NONE:
> +		/*
> +		 * This is the first time we've seen the object. We mark it as
> +		 * part of the active potential cycle and recurse.
> +		 */
> +		entry->dfs_state = DFS_ACTIVE;
> +		break_delta_cycles(entry->delta);
> +		entry->dfs_state = DFS_DONE;
> +		break;
> +
> +	case DFS_DONE:
> +		/* object already examined, and not part of a cycle */
> +		break;
> +
> +	case DFS_ACTIVE:
> +		/*
> +		 * We found a cycle that needs broken. It would be correct to
> +		 * break any link in the chain, but it's convenient to
> +		 * break this one.
> +		 */
> +		drop_reused_delta(entry);
> +		break;
> +	}
> +}

Do we need to do anything to the DFS state of an entry when
drop_reused_delta() resets its other fields?  If we had this and
started from A (read "A--->B" as "A is based on B"):

    A--->B--->C--->A

we paint A as ACTIVE, visit B and then C and paint them as active,
and when we visit A for the second time, we drop it (i.e. break the
link between A and B), return and paint C as DONE, return and paint
B as DONE, and leaving A painted as ACTIVE, while the chain is now

         B--->C--->A

If we later find D that is directly based on A, wouldn't we end up
visiting A and attempt to drop it again?  drop_reused_delta() is
idempotent so there will be no data structure corruption, I think,
but we can safely declare that the entry is now DONE after calling
drop_reused_delta() on it (either in the function or in the caller
after it calls the function), no?

> + 2. Picking the next pack to examine based on locality (i.e., where we found
> +    something else recently).
> +
> +    In this case, we want to make sure that we find the delta versions of A and
> +    B and not their base versions. We can do this by putting two blobs in each
> +    pack. The first is a "dummy" blob that can only be found in the pack in
> +    question.  And then the second is the actual delta we want to find.
> +
> +    The two blobs must be present in the same tree, not present in other trees,
> +    and the dummy pathname must sort before the delta path.

> +# Create a pack containing the the tree $1 and blob $1:file, with
> +# the latter stored as a delta against $2:file.
> +#
> +# We convince pack-objects to make the delta in the direction of our choosing
> +# by marking $2 as a preferred-base edge. That results in $1:file as a thin
> +# delta, and index-pack completes it by adding $2:file as a base.

Tricky but clever and correct ;-)

> +make_pack () {
> +	 {
> +		 echo "-$(git rev-parse $2)"

Is everybody's 'echo' happy with dash followed by unknown string?

> +		 echo "$(git rev-parse $1:dummy) dummy"
> +		 echo "$(git rev-parse $1:file) file"
> +	 } |
> +	 git pack-objects --stdout |
> +	 git index-pack --stdin --fix-thin

An alternative

	git pack-objects --stdout <<-EOF |
	-$(git rev-parse $2)
        $(git rev-parse $1:dummy) dummy
        $(git rev-parse $1:file) file
	EOF
        git index-pack --stdin --fix-thin

looks somewhat ugly, though.

> +}

Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase

[Jeff King]

On Wed, Aug 10, 2016 at 01:17:22PM -0700, Junio C Hamano wrote:

> > Actually, skimming the sha1_file code, I am not 100% sure that we detect
> > cycles in OBJ_REF_DELTA (you cannot have cycles in OBJ_OFS_DELTA since
> > they always point backwards in the pack). But if that is the case, then
> > I think we should fix that, not worry about special-casing it here.
> 
> Yes, but sha1_file.c?  It is the reading side and it is too late if
> we notice a problem, I would think.

We already are covered on the writing side. That is what your code in
write_one() does. The reason to warn is on the reading side ("I fixed
this for you, but by the way, your existing packs were bogus").

But of more concern is whether read_sha1_file() would recurse
infinitely, which would be bad (though I do not think it would be a
feasible attack vector; index-pack already rejects such packs before
they are admitted to the repository).

> > + *   2. Updating our size; check_object() will have filled in the size of our
> > + *      delta, but a non-delta object needs it true size.
> 
> Excellent point.

I was not clever enough to think of it; the pack-objects code is filled
with nice assertions (Thanks, Nico!) that help out when you are stupid. :)

One thing to be careful of is that there are more things this
drop_reused_delta() should be doing. But I looked through the rest of
check_object() and could not find anything else.

> > +	case DFS_ACTIVE:
> > +		/*
> > +		 * We found a cycle that needs broken. It would be correct to
> > +		 * break any link in the chain, but it's convenient to
> > +		 * break this one.
> > +		 */
> > +		drop_reused_delta(entry);
> > +		break;
> > +	}
> > +}
> 
> Do we need to do anything to the DFS state of an entry when
> drop_reused_delta() resets its other fields?

Good catch. It should be marked DONE after we have broken the delta. It
doesn't matter in practice, because...

> If we later find D that is directly based on A, wouldn't we end up
> visiting A and attempt to drop it again?  drop_reused_delta() is
> idempotent so there will be no data structure corruption, I think,
> but we can safely declare that the entry is now DONE after calling
> drop_reused_delta() on it (either in the function or in the caller
> after it calls the function), no?

I think the idempotency of drop_reused_delta() doesn't matter. When we
visit A again later, its "delta" field will be NULL, so we'll hit the
condition at the top of the function: this is a base object, mark DONE
and don't recurse.

So it's correct as-is, but I agree it feels weird that the DFS would end
with some objects potentially marked ACTIVE. Everything should be DONE
at the end.

> > +# Create a pack containing the the tree $1 and blob $1:file, with
> > +# the latter stored as a delta against $2:file.
> > +#
> > +# We convince pack-objects to make the delta in the direction of our choosing
> > +# by marking $2 as a preferred-base edge. That results in $1:file as a thin
> > +# delta, and index-pack completes it by adding $2:file as a base.
> 
> Tricky but clever and correct ;-)

Thanks, it took a long time to think up. ;)

I actually wish we had better tools for making fake packs. Something
where you could say "add A, then add B as a delta of A, then...".
Because you often have to jump through quite a few hoops to convince
pack-objects to generate the pack you want, and even some things are
impossible (for example, I would like to make a chain of 10 deltas; how
do I convince the delta search to put my objects in the right order?).

I tried briefly yesterday to convince pack-objects to just take a list
of objects and their deltas, but it got ugly very quickly.  I think we'd
be better off writing a new tool that happens to reuse some of the
formatting functions from pack-objects. But even then, we've got to
write an .idx, which means going through index-pack (which will complain
if we are writing bogus packs for testing odd situations), or we have to
keep a valid list of "struct object_entry" to feed to the idx writer.

So even that approach is not quite trivial.

> > +make_pack () {
> > +	 {
> > +		 echo "-$(git rev-parse $2)"
> 
> Is everybody's 'echo' happy with dash followed by unknown string?

I'd assume so because it will be "-<sha1>", and I think echoes which
take options are careful about that.

Still, it would not be hard to tweak.

> > +		 echo "$(git rev-parse $1:dummy) dummy"
> > +		 echo "$(git rev-parse $1:file) file"
> > +	 } |
> > +	 git pack-objects --stdout |
> > +	 git index-pack --stdin --fix-thin
> 
> An alternative
> 
> 	git pack-objects --stdout <<-EOF |
> 	-$(git rev-parse $2)
>         $(git rev-parse $1:dummy) dummy
>         $(git rev-parse $1:file) file
> 	EOF
>         git index-pack --stdin --fix-thin
> 
> looks somewhat ugly, though.

Yeah, I think we would be better to just switch to printf if we want to
be careful.

I'll follow-up with a patch.

-Peff

[PATCH v4 1/2] pack-objects: break delta cycles before delta-search phase

[Jeff King]

On Thu, Aug 11, 2016 at 01:02:52AM -0400, Jeff King wrote:

> Yeah, I think we would be better to just switch to printf if we want to
> be careful.
> 
> I'll follow-up with a patch.

Here it is. It switches out the echos for printfs (which, ironically,
_do_ complain about the "-" argument if you do so naively, but of course
the right way is "printf '%s\n' -whatever").

It also sets the dfs_state flag to DONE after breaking a delta, as
discussed.

Patch 2/2 on top does not need any adjustment, so I won't bother sending
it.

-- >8 --
Subject: [PATCH] pack-objects: break delta cycles before delta-search phase

We do not allow cycles in the delta graph of a pack (i.e., A
is a delta of B which is a delta of A) for the obvious
reason that you cannot actually access any of the objects in
such a case.

There's a last-ditch attempt to notice cycles during the
write phase, during which we issue a warning to the user and
write one of the objects out in full. However, this is
"last-ditch" for two reasons:

  1. By this time, it's too late to find another delta for
     the object, so the resulting pack is larger than it
     otherwise could be.

  2. The warning is there because this is something that
     _shouldn't_ ever happen. If it does, then either:

       a. a pack we are reusing deltas from had its own
          cycle

       b. we are reusing deltas from multiple packs, and
          we found a cycle among them (i.e., A is a delta of
          B in one pack, but B is a delta of A in another,
          and we choose to use both deltas).

       c. there is a bug in the delta-search code

     So this code serves as a final check that none of these
     things has happened, warns the user, and prevents us
     from writing a bogus pack.

Right now, (2b) should never happen because of the static
ordering of packs in want_object_in_pack(). If two objects
have a delta relationship, then they must be in the same
pack, and therefore we will find them from that same pack.

However, a future patch would like to change that static
ordering, which will make (2b) a common occurrence. In
preparation, we should be able to handle those kinds of
cycles better. This patch does by introducing a
cycle-breaking step during the get_object_details() phase,
when we are deciding which deltas can be reused. That gives
us the chance to feed the objects into the delta search as
if the cycle did not exist.

We'll leave the detection and warning in the write_object()
phase in place, as it still serves as a check for case (2c).

This does mean we will stop warning for (2a). That case is
caused by bogus input packs, and we ideally would warn the
user about it.  However, since those cycles show up after
picking reusable deltas, they look the same as (2b) to us;
our new code will break the cycles early and the last-ditch
check will never see them.

We could do analysis on any cycles that we find to
distinguish the two cases (i.e., it is a bogus pack if and
only if every delta in the cycle is in the same pack), but
we don't need to. If there is a cycle inside a pack, we'll
run into problems not only reusing the delta, but accessing
the object data at all. So when we try to dig up the actual
size of the object, we'll hit that same cycle and kick in
our usual complain-and-try-another-source code.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c          |  84 +++++++++++++++++++++++++++++
 pack-objects.h                  |   9 ++++
 t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 206 insertions(+)
 create mode 100755 t/t5314-pack-cycle-detection.sh

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 4a63398..b8e4e41 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1495,6 +1495,83 @@ static int pack_offset_sort(const void *_a, const void *_b)
 			(a->in_pack_offset > b->in_pack_offset);
 }
 
+/*
+ * Drop an on-disk delta we were planning to reuse. Naively, this would
+ * just involve blanking out the "delta" field, but we have to deal
+ * with two extra pieces of book-keeping:
+ *
+ *   1. Removing ourselves from the delta_sibling linked list.
+ *
+ *   2. Updating our size; check_object() will have filled in the size of our
+ *      delta, but a non-delta object needs it true size.
+ */
+static void drop_reused_delta(struct object_entry *entry)
+{
+	struct object_entry **p = &entry->delta->delta_child;
+	struct pack_window *w_curs = NULL;
+
+	while (*p) {
+		if (*p == entry)
+			*p = (*p)->delta_sibling;
+		else
+			p = &(*p)->delta_sibling;
+	}
+	entry->delta = NULL;
+
+	entry->size = get_size_from_delta(entry->in_pack, &w_curs,
+			  entry->in_pack_offset + entry->in_pack_header_size);
+	unuse_pack(&w_curs);
+
+	/*
+	 * If we failed to get the size from this pack for whatever reason,
+	 * fall back to sha1_object_info, which may find another copy. And if
+	 * that fails, the error will be recorded in entry->type and dealt
+	 * with in prepare_pack().
+	 */
+	if (entry->size == 0)
+		entry->type = sha1_object_info(entry->idx.sha1, &entry->size);
+}
+
+/*
+ * Follow the chain of deltas from this entry onward, throwing away any links
+ * that cause us to hit a cycle (as determined by the DFS state flags in
+ * the entries).
+ */
+static void break_delta_cycles(struct object_entry *entry)
+{
+	/* If it's not a delta, it can't be part of a cycle. */
+	if (!entry->delta) {
+		entry->dfs_state = DFS_DONE;
+		return;
+	}
+
+	switch (entry->dfs_state) {
+	case DFS_NONE:
+		/*
+		 * This is the first time we've seen the object. We mark it as
+		 * part of the active potential cycle and recurse.
+		 */
+		entry->dfs_state = DFS_ACTIVE;
+		break_delta_cycles(entry->delta);
+		entry->dfs_state = DFS_DONE;
+		break;
+
+	case DFS_DONE:
+		/* object already examined, and not part of a cycle */
+		break;
+
+	case DFS_ACTIVE:
+		/*
+		 * We found a cycle that needs broken. It would be correct to
+		 * break any link in the chain, but it's convenient to
+		 * break this one.
+		 */
+		drop_reused_delta(entry);
+		entry->dfs_state = DFS_DONE;
+		break;
+	}
+}
+
 static void get_object_details(void)
 {
 	uint32_t i;
@@ -1512,6 +1589,13 @@ static void get_object_details(void)
 			entry->no_try_delta = 1;
 	}
 
+	/*
+	 * This must happen in a second pass, since we rely on the delta
+	 * information for the whole list being completed.
+	 */
+	for (i = 0; i < to_pack.nr_objects; i++)
+		break_delta_cycles(&to_pack.objects[i]);
+
 	free(sorted_by_offset);
 }
 
diff --git a/pack-objects.h b/pack-objects.h
index d1b98b3..cc9b9a9 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -27,6 +27,15 @@ struct object_entry {
 	unsigned no_try_delta:1;
 	unsigned tagged:1; /* near the very tip of refs */
 	unsigned filled:1; /* assigned write-order */
+
+	/*
+	 * State flags for depth-first search used for analyzing delta cycles.
+	 */
+	enum {
+		DFS_NONE = 0,
+		DFS_ACTIVE,
+		DFS_DONE
+	} dfs_state;
 };
 
 struct packing_data {
diff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh
new file mode 100755
index 0000000..f7dbdfb
--- /dev/null
+++ b/t/t5314-pack-cycle-detection.sh
@@ -0,0 +1,113 @@
+#!/bin/sh
+
+test_description='test handling of inter-pack delta cycles during repack
+
+The goal here is to create a situation where we have two blobs, A and B, with A
+as a delta against B in one pack, and vice versa in the other. Then if we can
+persuade a full repack to find A from one pack and B from the other, that will
+give us a cycle when we attempt to reuse those deltas.
+
+The trick is in the "persuade" step, as it depends on the internals of how
+pack-objects picks which pack to reuse the deltas from. But we can assume
+that it does so in one of two general strategies:
+
+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can
+    happen. Any objects with a delta relationship must be present in the same
+    pack (i.e., no "--thin" packs on disk), so we will find all related objects
+    from that pack. So assuming there are no cycles within a single pack (and
+    we avoid generating them via pack-objects or importing them via
+    index-pack), then our result will have no cycles.
+
+    So this case should pass the tests no matter how we arrange things.
+
+ 2. Picking the next pack to examine based on locality (i.e., where we found
+    something else recently).
+
+    In this case, we want to make sure that we find the delta versions of A and
+    B and not their base versions. We can do this by putting two blobs in each
+    pack. The first is a "dummy" blob that can only be found in the pack in
+    question.  And then the second is the actual delta we want to find.
+
+    The two blobs must be present in the same tree, not present in other trees,
+    and the dummy pathname must sort before the delta path.
+
+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each
+which has two files: "dummy" and "file". Then we can make two packs which
+contain:
+
+  [pack one]
+  HEAD:dummy
+  HEAD:file  (as delta against HEAD^:file)
+  HEAD^:file (as base)
+
+  [pack two]
+  HEAD^:dummy
+  HEAD^:file (as delta against HEAD:file)
+  HEAD:file  (as base)
+
+Then no matter which order we start looking at the packs in, we know that we
+will always find a delta for "file", because its lookup will always come
+immediately after the lookup for "dummy".
+'
+. ./test-lib.sh
+
+
+
+# Create a pack containing the the tree $1 and blob $1:file, with
+# the latter stored as a delta against $2:file.
+#
+# We convince pack-objects to make the delta in the direction of our choosing
+# by marking $2 as a preferred-base edge. That results in $1:file as a thin
+# delta, and index-pack completes it by adding $2:file as a base.
+#
+# Note that the two variants of "file" must be similar enough to convince git
+# to create the delta.
+make_pack () {
+	{
+		printf '%s\n' "-$(git rev-parse $2)"
+		printf '%s dummy\n' "$(git rev-parse $1:dummy)"
+		printf '%s file\n' "$(git rev-parse $1:file)"
+	} |
+	git pack-objects --stdout |
+	git index-pack --stdin --fix-thin
+}
+
+test_expect_success 'setup' '
+	test-genrandom base 4096 >base &&
+	for i in one two
+	do
+		# we want shared content here to encourage deltas...
+		cp base file &&
+		echo $i >>file &&
+
+		# ...whereas dummy should be short, because we do not want
+		# deltas that would create duplicates when we --fix-thin
+		echo $i >dummy &&
+
+		git add file dummy &&
+		test_tick &&
+		git commit -m $i ||
+		return 1
+	done &&
+
+	make_pack HEAD^ HEAD &&
+	make_pack HEAD HEAD^
+'
+
+test_expect_success 'repack' '
+	# We first want to check that we do not have any internal errors,
+	# and also that we do not hit the last-ditch cycle-breaking code
+	# in write_object(), which will issue a warning to stderr.
+	>expect &&
+	git repack -ad 2>stderr &&
+	test_cmp expect stderr &&
+
+	# And then double-check that the resulting pack is usable (i.e.,
+	# we did not fail to notice any cycles). We know we are accessing
+	# the objects via the new pack here, because "repack -d" will have
+	# removed the others.
+	git cat-file blob HEAD:file >/dev/null &&
+	git cat-file blob HEAD^:file >/dev/null
+'
+
+test_done
-- 
2.9.2.790.gaa5bc72

Re: [PATCH v3 1/2] pack-objects: break delta cycles before delta-search phase

[Jeff King]

On Thu, Aug 11, 2016 at 01:02:52AM -0400, Jeff King wrote:

> > > + *   2. Updating our size; check_object() will have filled in the size of our
> > > + *      delta, but a non-delta object needs it true size.
> > 
> > Excellent point.
> 
> I was not clever enough to think of it; the pack-objects code is filled
> with nice assertions (Thanks, Nico!) that help out when you are stupid. :)
> 
> One thing to be careful of is that there are more things this
> drop_reused_delta() should be doing. But I looked through the rest of
> check_object() and could not find anything else.

Argh, I spoke too soon.

It is true that the size lookup is the only part of check_object()
we skip if we are reusing the delta. But what I didn't notice is that
when we choose to reuse a delta, we overwrite entry->type (the real
type!) with the in_pack_type (OFS_DELTA, etc). We need to undo that so
that later stages see the real type.

I'm not sure how my existing tests worked (I confirmed that they do
indeed break the delta). It may be that only some code paths actually
care about the real type. But when playing with the depth-limit (which
uses the same drop_reused_delta() helper), I managed to make some pretty
broken packs.

So please disregard the v4 patch I just sent; I haven't triggered it,
but I imagine it has the same problem, and I just didn't manage to
trigger it.

I'll clean that up and send out a new series.

-Peff

[PATCH v5] pack-objects mru

[Jeff King]

On Thu, Aug 11, 2016 at 02:57:51AM -0400, Jeff King wrote:

> > One thing to be careful of is that there are more things this
> > drop_reused_delta() should be doing. But I looked through the rest of
> > check_object() and could not find anything else.
> 
> Argh, I spoke too soon.
> 
> It is true that the size lookup is the only part of check_object()
> we skip if we are reusing the delta. But what I didn't notice is that
> when we choose to reuse a delta, we overwrite entry->type (the real
> type!) with the in_pack_type (OFS_DELTA, etc). We need to undo that so
> that later stages see the real type.
> 
> I'm not sure how my existing tests worked (I confirmed that they do
> indeed break the delta). It may be that only some code paths actually
> care about the real type. But when playing with the depth-limit (which
> uses the same drop_reused_delta() helper), I managed to make some pretty
> broken packs.
> 
> So please disregard the v4 patch I just sent; I haven't triggered it,
> but I imagine it has the same problem, and I just didn't manage to
> trigger it.
> 
> I'll clean that up and send out a new series.

Here it is. It ended up needing a few preparatory patches.

  [1/4]: provide an initializer for "struct object_info"
  [2/4]: sha1_file: make packed_object_info public
  [3/4]: pack-objects: break delta cycles before delta-search phase
  [4/4]: pack-objects: use mru list when iterating over packs

I had originally intended to include an extra patch to handle the
--depth limits better. But after writing it, I'm not sure it's actually
a good idea. I'll post it as an addendum with more discussion.

-Peff

[PATCH v5 1/4] provide an initializer for "struct object_info"

[Jeff King]

An all-zero initializer is fine for this struct, but because
the first element is a pointer, call sites need to know to
use "NULL" instead of "0". Otherwise some static checkers
like "sparse" will complain; see d099b71 (Fix some sparse
warnings, 2013-07-18) for example.  So let's provide an
initializer to make this easier to get right.

But let's also comment that memset() to zero is explicitly
OK[1]. One of the callers embeds object_info in another
struct which is initialized via memset (expand_data in
builtin/cat-file.c). Since our subset of C doesn't allow
assignment from a compound literal, handling this in any
other way is awkward, so we'd like to keep the ability to
initialize by memset(). By documenting this property, it
should make anybody who wants to change the initializer
think twice before doing so.

There's one other caller of interest. In parse_sha1_header(),
we did not initialize the struct fully in the first place.
This turned out not to be a bug because the sub-function it
calls does not look at any other fields except the ones we
did initialize. But that assumption might not hold in the
future, so it's a dangerous construct. This patch switches
it to initializing the whole struct, which protects us
against unexpected reads of the other fields.

[1] Obviously using memset() to initialize a pointer
    violates the C standard, but we long ago decided that it
    was an acceptable tradeoff in the real world.

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/cat-file.c | 5 ++---
 cache.h            | 7 +++++++
 sha1_file.c        | 6 ++----
 streaming.c        | 2 +-
 4 files changed, 12 insertions(+), 8 deletions(-)

diff --git a/builtin/cat-file.c b/builtin/cat-file.c
index 2dfe626..2cbc31e 100644
--- a/builtin/cat-file.c
+++ b/builtin/cat-file.c
@@ -28,7 +28,7 @@ static int cat_one_file(int opt, const char *exp_type, const char *obj_name,
 	char *buf;
 	unsigned long size;
 	struct object_context obj_context;
-	struct object_info oi = {NULL};
+	struct object_info oi = OBJECT_INFO_INIT;
 	struct strbuf sb = STRBUF_INIT;
 	unsigned flags = LOOKUP_REPLACE_OBJECT;
 
@@ -378,8 +378,7 @@ static int batch_objects(struct batch_options *opt)
 	data.mark_query = 0;
 
 	if (opt->all_objects) {
-		struct object_info empty;
-		memset(&empty, 0, sizeof(empty));
+		struct object_info empty = OBJECT_INFO_INIT;
 		if (!memcmp(&data.info, &empty, sizeof(empty)))
 			data.skip_object_info = 1;
 	}
diff --git a/cache.h b/cache.h
index 95a0bd3..b2e4969 100644
--- a/cache.h
+++ b/cache.h
@@ -1550,6 +1550,13 @@ struct object_info {
 		} packed;
 	} u;
 };
+
+/*
+ * Initializer for a "struct object_info" that wants no items. You may
+ * also memset() the memory to all-zeroes.
+ */
+#define OBJECT_INFO_INIT {NULL}
+
 extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);
 
 /* Dumb servers support */
diff --git a/sha1_file.c b/sha1_file.c
index 02940f1..b8cc76b 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1730,11 +1730,9 @@ static int parse_sha1_header_extended(const char *hdr, struct object_info *oi,
 
 int parse_sha1_header(const char *hdr, unsigned long *sizep)
 {
-	struct object_info oi;
+	struct object_info oi = OBJECT_INFO_INIT;
 
 	oi.sizep = sizep;
-	oi.typename = NULL;
-	oi.typep = NULL;
 	return parse_sha1_header_extended(hdr, &oi, LOOKUP_REPLACE_OBJECT);
 }
 
@@ -2738,7 +2736,7 @@ int sha1_object_info_extended(const unsigned char *sha1, struct object_info *oi,
 int sha1_object_info(const unsigned char *sha1, unsigned long *sizep)
 {
 	enum object_type type;
-	struct object_info oi = {NULL};
+	struct object_info oi = OBJECT_INFO_INIT;
 
 	oi.typep = &type;
 	oi.sizep = sizep;
diff --git a/streaming.c b/streaming.c
index 811fcc2..431254b 100644
--- a/streaming.c
+++ b/streaming.c
@@ -135,7 +135,7 @@ struct git_istream *open_istream(const unsigned char *sha1,
 				 struct stream_filter *filter)
 {
 	struct git_istream *st;
-	struct object_info oi = {NULL};
+	struct object_info oi = OBJECT_INFO_INIT;
 	const unsigned char *real = lookup_replace_object(sha1);
 	enum input_source src = istream_source(real, type, &oi);
 
-- 
2.9.2.790.gaa5bc72

[PATCH v5 2/4] sha1_file: make packed_object_info public

[Jeff King]

Some code may have a pack/offset pair for an object, but
would like to look up more information. Using
sha1_object_info() is too heavy-weight; it starts from the
sha1 and has to find the pack again (so not only does it waste
time, it might not even find the same instance).

In some cases, this problem is solved by helpers like
get_size_from_delta(), which is used by pack-objects to take
a shortcut for objects whose packed representation has
already been found. But there's no similar function for
getting the object type, for instance. Rather than introduce
one, let's just make the whole packed_object_info() available.
It is smart enough to spend effort only on the items the
caller wants.

Signed-off-by: Jeff King <peff@peff.net>
---
 cache.h     | 1 +
 sha1_file.c | 4 ++--
 2 files changed, 3 insertions(+), 2 deletions(-)

diff --git a/cache.h b/cache.h
index b2e4969..f23968e 100644
--- a/cache.h
+++ b/cache.h
@@ -1558,6 +1558,7 @@ struct object_info {
 #define OBJECT_INFO_INIT {NULL}
 
 extern int sha1_object_info_extended(const unsigned char *, struct object_info *, unsigned flags);
+extern int packed_object_info(struct packed_git *pack, off_t offset, struct object_info *);
 
 /* Dumb servers support */
 extern int update_server_info(int);
diff --git a/sha1_file.c b/sha1_file.c
index b8cc76b..5ca0ffa 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1970,8 +1970,8 @@ static enum object_type packed_to_object_type(struct packed_git *p,
 	goto out;
 }
 
-static int packed_object_info(struct packed_git *p, off_t obj_offset,
-			      struct object_info *oi)
+int packed_object_info(struct packed_git *p, off_t obj_offset,
+		       struct object_info *oi)
 {
 	struct pack_window *w_curs = NULL;
 	unsigned long size;
-- 
2.9.2.790.gaa5bc72

[PATCH v5 3/4] pack-objects: break delta cycles before delta-search phase

[Jeff King]

We do not allow cycles in the delta graph of a pack (i.e., A
is a delta of B which is a delta of A) for the obvious
reason that you cannot actually access any of the objects in
such a case.

There's a last-ditch attempt to notice cycles during the
write phase, during which we issue a warning to the user and
write one of the objects out in full. However, this is
"last-ditch" for two reasons:

  1. By this time, it's too late to find another delta for
     the object, so the resulting pack is larger than it
     otherwise could be.

  2. The warning is there because this is something that
     _shouldn't_ ever happen. If it does, then either:

       a. a pack we are reusing deltas from had its own
          cycle

       b. we are reusing deltas from multiple packs, and
          we found a cycle among them (i.e., A is a delta of
          B in one pack, but B is a delta of A in another,
          and we choose to use both deltas).

       c. there is a bug in the delta-search code

     So this code serves as a final check that none of these
     things has happened, warns the user, and prevents us
     from writing a bogus pack.

Right now, (2b) should never happen because of the static
ordering of packs in want_object_in_pack(). If two objects
have a delta relationship, then they must be in the same
pack, and therefore we will find them from that same pack.

However, a future patch would like to change that static
ordering, which will make (2b) a common occurrence. In
preparation, we should be able to handle those kinds of
cycles better. This patch does by introducing a
cycle-breaking step during the get_object_details() phase,
when we are deciding which deltas can be reused. That gives
us the chance to feed the objects into the delta search as
if the cycle did not exist.

We'll leave the detection and warning in the write_object()
phase in place, as it still serves as a check for case (2c).

This does mean we will stop warning for (2a). That case is
caused by bogus input packs, and we ideally would warn the
user about it.  However, since those cycles show up after
picking reusable deltas, they look the same as (2b) to us;
our new code will break the cycles early and the last-ditch
check will never see them.

We could do analysis on any cycles that we find to
distinguish the two cases (i.e., it is a bogus pack if and
only if every delta in the cycle is in the same pack), but
we don't need to. If there is a cycle inside a pack, we'll
run into problems not only reusing the delta, but accessing
the object data at all. So when we try to dig up the actual
size of the object, we'll hit that same cycle and kick in
our usual complain-and-try-another-source code.

Signed-off-by: Jeff King <peff@peff.net>
---
This has the DONE and printf fixes from v4, along with using
packed_object_info() to fill in the correct type when drop a delta.

 builtin/pack-objects.c          |  84 +++++++++++++++++++++++++++++
 pack-objects.h                  |   9 ++++
 t/t5314-pack-cycle-detection.sh | 113 ++++++++++++++++++++++++++++++++++++++++
 3 files changed, 206 insertions(+)
 create mode 100755 t/t5314-pack-cycle-detection.sh

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 4a63398..32c1dba 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1495,6 +1495,83 @@ static int pack_offset_sort(const void *_a, const void *_b)
 			(a->in_pack_offset > b->in_pack_offset);
 }
 
+/*
+ * Drop an on-disk delta we were planning to reuse. Naively, this would
+ * just involve blanking out the "delta" field, but we have to deal
+ * with some extra book-keeping:
+ *
+ *   1. Removing ourselves from the delta_sibling linked list.
+ *
+ *   2. Updating our size/type to the non-delta representation. These were
+ *      either not recorded initially (size) or overwritten with the delta type
+ *      (type) when check_object() decided to reuse the delta.
+ */
+static void drop_reused_delta(struct object_entry *entry)
+{
+	struct object_entry **p = &entry->delta->delta_child;
+	struct object_info oi = OBJECT_INFO_INIT;
+
+	while (*p) {
+		if (*p == entry)
+			*p = (*p)->delta_sibling;
+		else
+			p = &(*p)->delta_sibling;
+	}
+	entry->delta = NULL;
+
+	oi.sizep = &entry->size;
+	oi.typep = &entry->type;
+	if (packed_object_info(entry->in_pack, entry->in_pack_offset, &oi) < 0) {
+		/*
+		 * We failed to get the info from this pack for some reason;
+		 * fall back to sha1_object_info, which may find another copy.
+		 * And if that fails, the error will be recorded in entry->type
+		 * and dealt with in prepare_pack().
+		 */
+		entry->type = sha1_object_info(entry->idx.sha1, &entry->size);
+	}
+}
+
+/*
+ * Follow the chain of deltas from this entry onward, throwing away any links
+ * that cause us to hit a cycle (as determined by the DFS state flags in
+ * the entries).
+ */
+static void break_delta_chains(struct object_entry *entry)
+{
+	/* If it's not a delta, it can't be part of a cycle. */
+	if (!entry->delta) {
+		entry->dfs_state = DFS_DONE;
+		return;
+	}
+
+	switch (entry->dfs_state) {
+	case DFS_NONE:
+		/*
+		 * This is the first time we've seen the object. We mark it as
+		 * part of the active potential cycle and recurse.
+		 */
+		entry->dfs_state = DFS_ACTIVE;
+		break_delta_chains(entry->delta);
+		entry->dfs_state = DFS_DONE;
+		break;
+
+	case DFS_DONE:
+		/* object already examined, and not part of a cycle */
+		break;
+
+	case DFS_ACTIVE:
+		/*
+		 * We found a cycle that needs broken. It would be correct to
+		 * break any link in the chain, but it's convenient to
+		 * break this one.
+		 */
+		drop_reused_delta(entry);
+		entry->dfs_state = DFS_DONE;
+		break;
+	}
+}
+
 static void get_object_details(void)
 {
 	uint32_t i;
@@ -1512,6 +1589,13 @@ static void get_object_details(void)
 			entry->no_try_delta = 1;
 	}
 
+	/*
+	 * This must happen in a second pass, since we rely on the delta
+	 * information for the whole list being completed.
+	 */
+	for (i = 0; i < to_pack.nr_objects; i++)
+		break_delta_chains(&to_pack.objects[i]);
+
 	free(sorted_by_offset);
 }
 
diff --git a/pack-objects.h b/pack-objects.h
index d1b98b3..cc9b9a9 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -27,6 +27,15 @@ struct object_entry {
 	unsigned no_try_delta:1;
 	unsigned tagged:1; /* near the very tip of refs */
 	unsigned filled:1; /* assigned write-order */
+
+	/*
+	 * State flags for depth-first search used for analyzing delta cycles.
+	 */
+	enum {
+		DFS_NONE = 0,
+		DFS_ACTIVE,
+		DFS_DONE
+	} dfs_state;
 };
 
 struct packing_data {
diff --git a/t/t5314-pack-cycle-detection.sh b/t/t5314-pack-cycle-detection.sh
new file mode 100755
index 0000000..f7dbdfb
--- /dev/null
+++ b/t/t5314-pack-cycle-detection.sh
@@ -0,0 +1,113 @@
+#!/bin/sh
+
+test_description='test handling of inter-pack delta cycles during repack
+
+The goal here is to create a situation where we have two blobs, A and B, with A
+as a delta against B in one pack, and vice versa in the other. Then if we can
+persuade a full repack to find A from one pack and B from the other, that will
+give us a cycle when we attempt to reuse those deltas.
+
+The trick is in the "persuade" step, as it depends on the internals of how
+pack-objects picks which pack to reuse the deltas from. But we can assume
+that it does so in one of two general strategies:
+
+ 1. Using a static ordering of packs. In this case, no inter-pack cycles can
+    happen. Any objects with a delta relationship must be present in the same
+    pack (i.e., no "--thin" packs on disk), so we will find all related objects
+    from that pack. So assuming there are no cycles within a single pack (and
+    we avoid generating them via pack-objects or importing them via
+    index-pack), then our result will have no cycles.
+
+    So this case should pass the tests no matter how we arrange things.
+
+ 2. Picking the next pack to examine based on locality (i.e., where we found
+    something else recently).
+
+    In this case, we want to make sure that we find the delta versions of A and
+    B and not their base versions. We can do this by putting two blobs in each
+    pack. The first is a "dummy" blob that can only be found in the pack in
+    question.  And then the second is the actual delta we want to find.
+
+    The two blobs must be present in the same tree, not present in other trees,
+    and the dummy pathname must sort before the delta path.
+
+The setup below focuses on case 2. We have two commits HEAD and HEAD^, each
+which has two files: "dummy" and "file". Then we can make two packs which
+contain:
+
+  [pack one]
+  HEAD:dummy
+  HEAD:file  (as delta against HEAD^:file)
+  HEAD^:file (as base)
+
+  [pack two]
+  HEAD^:dummy
+  HEAD^:file (as delta against HEAD:file)
+  HEAD:file  (as base)
+
+Then no matter which order we start looking at the packs in, we know that we
+will always find a delta for "file", because its lookup will always come
+immediately after the lookup for "dummy".
+'
+. ./test-lib.sh
+
+
+
+# Create a pack containing the the tree $1 and blob $1:file, with
+# the latter stored as a delta against $2:file.
+#
+# We convince pack-objects to make the delta in the direction of our choosing
+# by marking $2 as a preferred-base edge. That results in $1:file as a thin
+# delta, and index-pack completes it by adding $2:file as a base.
+#
+# Note that the two variants of "file" must be similar enough to convince git
+# to create the delta.
+make_pack () {
+	{
+		printf '%s\n' "-$(git rev-parse $2)"
+		printf '%s dummy\n' "$(git rev-parse $1:dummy)"
+		printf '%s file\n' "$(git rev-parse $1:file)"
+	} |
+	git pack-objects --stdout |
+	git index-pack --stdin --fix-thin
+}
+
+test_expect_success 'setup' '
+	test-genrandom base 4096 >base &&
+	for i in one two
+	do
+		# we want shared content here to encourage deltas...
+		cp base file &&
+		echo $i >>file &&
+
+		# ...whereas dummy should be short, because we do not want
+		# deltas that would create duplicates when we --fix-thin
+		echo $i >dummy &&
+
+		git add file dummy &&
+		test_tick &&
+		git commit -m $i ||
+		return 1
+	done &&
+
+	make_pack HEAD^ HEAD &&
+	make_pack HEAD HEAD^
+'
+
+test_expect_success 'repack' '
+	# We first want to check that we do not have any internal errors,
+	# and also that we do not hit the last-ditch cycle-breaking code
+	# in write_object(), which will issue a warning to stderr.
+	>expect &&
+	git repack -ad 2>stderr &&
+	test_cmp expect stderr &&
+
+	# And then double-check that the resulting pack is usable (i.e.,
+	# we did not fail to notice any cycles). We know we are accessing
+	# the objects via the new pack here, because "repack -d" will have
+	# removed the others.
+	git cat-file blob HEAD:file >/dev/null &&
+	git cat-file blob HEAD^:file >/dev/null
+'
+
+test_done
-- 
2.9.2.790.gaa5bc72

[PATCH v5 4/4] pack-objects: use mru list when iterating over packs

[Jeff King]

In the original implementation of want_object_in_pack(), we
always looked for the object in every pack, so the order did
not matter for performance.

As of the last few patches, however, we can now often break
out of the loop early after finding the first instance, and
avoid looking in the other packs at all. In this case, pack
order can make a big difference, because we'd like to find
the objects by looking at as few packs as possible.

This patch switches us to the same packed_git_mru list that
is now used by normal object lookups.

Here are timings for p5303 on linux.git:

Test                      HEAD^                HEAD
------------------------------------------------------------------------
5303.3: rev-list (1)      31.31(31.07+0.23)    31.28(31.00+0.27) -0.1%
5303.4: repack (1)        40.35(38.84+2.60)    40.53(39.31+2.32) +0.4%
5303.6: rev-list (50)     31.37(31.15+0.21)    31.41(31.16+0.24) +0.1%
5303.7: repack (50)       58.25(68.54+2.03)    47.28(57.66+1.89) -18.8%
5303.9: rev-list (1000)   31.91(31.57+0.33)    31.93(31.64+0.28) +0.1%
5303.10: repack (1000)    304.80(376.00+3.92)  87.21(159.54+2.84) -71.4%

The rev-list numbers are unchanged, which makes sense (they
are not exercising this code at all). The 50- and 1000-pack
repack cases show considerable improvement.

The single-pack repack case doesn't, of course; there's
nothing to improve. In fact, it gives us a baseline for how
fast we could possibly go. You can see that though rev-list
can approach the single-pack case even with 1000 packs,
repack doesn't. The reason is simple: the loop we are
optimizing is only part of what the repack is doing. After
the "counting" phase, we do delta compression, which is much
more expensive when there are multiple packs, because we
have fewer deltas we can reuse (you can also see that these
numbers come from a multicore machine; the CPU times are
much higher than the wall-clock times due to the delta
phase).

So the good news is that in cases with many packs, we used
to be dominated by the "counting" phase, and now we are
dominated by the delta compression (which is faster, and
which we have already parallelized).

Here are similar numbers for git.git:

Test                      HEAD^               HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.55(1.51+0.02)     1.54(1.53+0.00) -0.6%
5303.4: repack (1)        1.82(1.80+0.08)     1.82(1.78+0.09) +0.0%
5303.6: rev-list (50)     1.58(1.57+0.00)     1.58(1.56+0.01) +0.0%
5303.7: repack (50)       2.50(3.12+0.07)     2.31(2.95+0.06) -7.6%
5303.9: rev-list (1000)   2.22(2.20+0.02)     2.23(2.19+0.03) +0.5%
5303.10: repack (1000)    10.47(16.78+0.22)   7.50(13.76+0.22) -28.4%

Not as impressive in terms of percentage, but still
measurable wins.  If you look at the wall-clock time
improvements in the 1000-pack case, you can see that linux
improved by roughly 10x as many seconds as git. That's
because it has roughly 10x as many objects, and we'd expect
this improvement to scale linearly with the number of
objects (since the number of packs is kept constant). It's
just that the "counting" phase is a smaller percentage of
the total time spent for a git.git repack, and hence the
percentage win is smaller.

The implementation itself is a straightforward use of the
MRU code. We only bother marking a pack as used when we know
that we are able to break early out of the loop, for two
reasons:

  1. If we can't break out early, it does no good; we have
     to visit each pack anyway, so we might as well avoid
     even the minor overhead of managing the cache order.

  2. The mru_mark() function reorders the list, which would
     screw up our traversal. So it is only safe to mark when
     we are about to break out of the loop. We could record
     the found pack and mark it after the loop finishes, of
     course, but that's more complicated and it doesn't buy
     us anything due to (1).

Note that this reordering does have a potential impact on
the final pack, as we store only a single "found" pack for
each object, even if it is present in multiple packs. In
principle, any copy is acceptable, as they all refer to the
same content. But in practice, they may differ in whether
they are stored as deltas, against which base, etc. This may
have an impact on delta reuse, and even the delta search
(since we skip pairs that were already in the same pack).

It's not clear whether this change of order would hurt or
even help average cases, though. The most likely reason to
have duplicate objects is from the completion of thin packs
(e.g., you have some objects in a "base" pack, then receive
several pushes; the packs you receive may be thin on the
wire, with deltas that refer to bases outside the pack, but
we complete them with duplicate base objects when indexing
them).

In such a case the current code would always find the thin
duplicates (because we currently walk the packs in reverse
chronological order). Whereas with this patch, some of those
duplicates would be found in the base pack instead.

In my tests repacking a real-world case of linux.git with
3600 thin-pack pushes (on top of a large "base" pack), the
resulting pack was about 0.04% larger with this patch. On
the other hand, because we were more likely to hit the base
pack, there were more opportunities for delta reuse, and we
had 50,000 fewer objects to examine in the delta search.

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

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 32c1dba..b745280 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -23,6 +23,7 @@
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "mru.h"
 
 static const char *pack_usage[] = {
 	N_("git pack-objects --stdout [<options>...] [< <ref-list> | < <object-list>]"),
@@ -958,7 +959,7 @@ static int want_object_in_pack(const unsigned char *sha1,
 			       struct packed_git **found_pack,
 			       off_t *found_offset)
 {
-	struct packed_git *p;
+	struct mru_entry *entry;
 
 	if (!exclude && local && has_loose_object_nonlocal(sha1))
 		return 0;
@@ -966,7 +967,8 @@ static int want_object_in_pack(const unsigned char *sha1,
 	*found_pack = NULL;
 	*found_offset = 0;
 
-	for (p = packed_git; p; p = p->next) {
+	for (entry = packed_git_mru->head; entry; entry = entry->next) {
+		struct packed_git *p = entry->item;
 		off_t offset = find_pack_entry_one(sha1, p);
 		if (offset) {
 			if (!*found_pack) {
@@ -993,8 +995,10 @@ static int want_object_in_pack(const unsigned char *sha1,
 			 * out of the loop to return 1 now.
 			 */
 			if (!ignore_packed_keep &&
-			    (!local || !have_non_local_packs))
+			    (!local || !have_non_local_packs)) {
+				mru_mark(packed_git_mru, entry);
 				break;
+			}
 
 			if (local && !p->pack_local)
 				return 0;
-- 
2.9.2.790.gaa5bc72

Re: [PATCH v5] pack-objects mru

[Jeff King]

On Thu, Aug 11, 2016 at 05:20:30AM -0400, Jeff King wrote:

> Here it is. It ended up needing a few preparatory patches.
> 
>   [1/4]: provide an initializer for "struct object_info"
>   [2/4]: sha1_file: make packed_object_info public
>   [3/4]: pack-objects: break delta cycles before delta-search phase
>   [4/4]: pack-objects: use mru list when iterating over packs
> 
> I had originally intended to include an extra patch to handle the
> --depth limits better. But after writing it, I'm not sure it's actually
> a good idea. I'll post it as an addendum with more discussion.

And here's the depth patch. It does work, as you can see by running the
snippet at the bottom of the commit message.

But I began to wonder if it's actually a desirable thing. For instance,
if you do:

  git gc --aggressive
  ... time passes ...
  git gc

the first gc may generate chains up to 250 objects. When the second gc
runs (and you may not even run it yourself; it might be "gc --auto"!),
it will generally reuse most of your existing deltas, even though the
default depth is only 50.

But with the patch below, it will drop deltas from the middle of those
long chains, undoing the prior --aggressive results. Worse, we don't
find new deltas for those objects, because it falls afoul of the "they
are in the same pack, so don't bother looking for a delta" rule.

An --aggressive repack of my git.git is 52MB. Repacking that with the
patch below and "--depth=50" bumps it to 55MB. Dumping the "do not
bother" condition in try_delta() drops that to 54MB.

So it _is_ worse for the space to drop those high-depth deltas. Even if
we fixed the "do not bother" (e.g., by recording a bit that says "even
though these are in the same pack, try anyway, because we had to break
the delta for other reasons"), it's still a loss.

OTOH, I am not altogether convinced that the tradeoff of a giant --depth
is worth. I'm looking only at the space here, but deeper delta chains
cost more CPU to access (especially if they start to exceed the delta
cache size). And the space savings aren't that amazing. Doing a "git
repack -adf --depth=50 --window=250" (i.e., if aggressive had just
tweaked the window size and not the depth in the first place), the
result is only 53MB.

So considering "--depth" as a space-saving measure for --aggressive does
not seem that effective. But it feels weird to quietly drop actions
people might have done with previous aggressive runs.

-- >8 --
Subject: [PATCH] pack-objects: enforce --depth limit in reused deltas

Since 898b14c (pack-objects: rework check_delta_limit usage,
2007-04-16), we check the delta depth limit only when
figuring out whether we should make a new delta. We don't
consider it at all when reusing deltas, which means that
packing once with --depth=50, and then against with
--depth=10, the second pack my still contain chains larger
than 10.

This is probably not a huge deal, as it is limited to
whatever chains you happened to create in a previous run.
But as we start allowing cross-pack delta reuse in a future
commit, this maximum will rise to the number of packs times
the per-pack depth (in the worst case; on average, it will
likely be much smaller).

We can easily detect this as part of the existing search for
cycles, since we visit every node in a depth-first way. That
lets us compute the depth of any node based on the depth of
its base, because we know the base is DFS_DONE by the time
we look at it (modulo any cycles in the graph, but we know
there cannot be any because we break them as we see them).

There is some subtlety worth mentioning, though. We record
the depth of each object as we compute it. It might seem
like we could save the per-object storage space by just
keeping track of the depth of our traversal (i.e., have
break_delta_chains() report how deep it went). But we may
visit an object through multiple delta paths, and on
subsequent paths we want to know its depth immediately,
without having to walk back down to its final base (doing so
would make our graph walk quadratic rather than linear).

Likewise, one could try to record the depth not from the
base, but from our starting point (i.e., start
recursion_depth at 0, and pass "recursion_depth + 1" to each
invocation of break_delta_chains()). And then when
recursion_depth gets too big, we know that we must cut the
delta chain.  But that technique is wrong if we do not visit
the nodes in topological order. In a chain A->B->C, it
if we visit "C", then "B", then "A", we will never recurse
deeper than 1 link (because we see at each node that we have
already visited it).

Unfortunately there is no automated test, because it's hard
to convince pack-objects to reliably produce delta chains.
Naively, it would seem that a sequence of ever-increasing
blobs would work. E.g., something like:

  for i in 1 2 3 4 5; do
          test-genrandom $i 4096 >>file
          git add file
          git commit -m $i
  done

where a reasonable set of deltas would use "1:file" as the
base, then "2:file" as a delta against that, "3:file" as a
delta against "2:file", and so on, until we have a chain
with length 5.

But the delta search is much more fickle than that. It tends
to prefer deletions to additions (because they are smaller
than additions), so it prefers "5:file" as the base, and
then the deltas just say "remove N bytes from the end".
Moreover, the delta search has heuristics that penalize
increasing depth. So packing the script above actually ends
up with 2 chains of length 2.

So I've punted on adding an automated test. One can see the
effect on a real-world repository by repacking it with a
small --depth value, like:

  max_depth() {
    for i in .git/objects/pack/*.pack; do
      git verify-pack -v $i
    done |
    perl -lne '
      /chain length = (\d+)/ or next;
      $max = $1 if $1 > $max;
      END { print $max }
    '
  }

  echo "before: $(max_depth)"
  git repack -ad --depth=5
  echo "after: $(max_depth)"

Signed-off-by: Jeff King <peff@peff.net>
---
 builtin/pack-objects.c | 15 +++++++++++++++
 pack-objects.h         |  4 ++++
 2 files changed, 19 insertions(+)

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 32c1dba..d8132a4 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -1505,6 +1505,8 @@ static int pack_offset_sort(const void *_a, const void *_b)
  *   2. Updating our size/type to the non-delta representation. These were
  *      either not recorded initially (size) or overwritten with the delta type
  *      (type) when check_object() decided to reuse the delta.
+ *
+ *   3. Resetting our delta depth, as we are now a base object.
  */
 static void drop_reused_delta(struct object_entry *entry)
 {
@@ -1518,6 +1520,7 @@ static void drop_reused_delta(struct object_entry *entry)
 			p = &(*p)->delta_sibling;
 	}
 	entry->delta = NULL;
+	entry->depth = 0;
 
 	oi.sizep = &entry->size;
 	oi.typep = &entry->type;
@@ -1536,6 +1539,9 @@ static void drop_reused_delta(struct object_entry *entry)
  * Follow the chain of deltas from this entry onward, throwing away any links
  * that cause us to hit a cycle (as determined by the DFS state flags in
  * the entries).
+ *
+ * We also detect too-long reused chains that would violate our --depth
+ * limit.
  */
 static void break_delta_chains(struct object_entry *entry)
 {
@@ -1553,6 +1559,15 @@ static void break_delta_chains(struct object_entry *entry)
 		 */
 		entry->dfs_state = DFS_ACTIVE;
 		break_delta_chains(entry->delta);
+
+		/*
+		 * Once we've recursed, our base knows its depth, so we can
+		 * compute ours (and check it against the limit).
+		 */
+		entry->depth = entry->delta->depth + 1;
+		if (entry->depth > depth)
+			drop_reused_delta(entry);
+
 		entry->dfs_state = DFS_DONE;
 		break;
 
diff --git a/pack-objects.h b/pack-objects.h
index cc9b9a9..03f1191 100644
--- a/pack-objects.h
+++ b/pack-objects.h
@@ -30,12 +30,16 @@ struct object_entry {
 
 	/*
 	 * State flags for depth-first search used for analyzing delta cycles.
+	 *
+	 * The depth is measured in delta-links to the base (so if A is a delta
+	 * against B, then A has a depth of 1, and B a depth of 0).
 	 */
 	enum {
 		DFS_NONE = 0,
 		DFS_ACTIVE,
 		DFS_DONE
 	} dfs_state;
+	int depth;
 };
 
 struct packing_data {
-- 
2.9.2.790.gaa5bc72

Re: [PATCH v5] pack-objects mru

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

> So considering "--depth" as a space-saving measure for --aggressive does
> not seem that effective. But it feels weird to quietly drop actions
> people might have done with previous aggressive runs.

That argument cuts both ways, doesn't it?

If the user explicitly asks to use lower "--depth" from the command
line when the second repack runs, the intention is clear: the
existing pack may use delta chains that are too long and is
detrimental to the run-time performance, and the user wants to
correct it by repacking with shorter delta chain.

Should the act of letting "gc --auto" use lower "--depth", by not
configuring to always use deeper chain, be interpreted the same way?
I am not sure.  The old packing with large --depth is something the
user did long time ago, and the decision the user made not to use
large depth always is also something the user did long time ago.  I
do not think it is so cut-and-dried which one of the two conflicting
wishes we should honor when running the second repack, especially
when it is run unattended like "gc --auto" does.

Re: [PATCH v5] pack-objects mru

[Jeff King]

On Thu, Aug 11, 2016 at 08:11:33AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> > So considering "--depth" as a space-saving measure for --aggressive does
> > not seem that effective. But it feels weird to quietly drop actions
> > people might have done with previous aggressive runs.
> 
> That argument cuts both ways, doesn't it?
> 
> If the user explicitly asks to use lower "--depth" from the command
> line when the second repack runs, the intention is clear: the
> existing pack may use delta chains that are too long and is
> detrimental to the run-time performance, and the user wants to
> correct it by repacking with shorter delta chain.
> 
> Should the act of letting "gc --auto" use lower "--depth", by not
> configuring to always use deeper chain, be interpreted the same way?
> I am not sure.  The old packing with large --depth is something the
> user did long time ago, and the decision the user made not to use
> large depth always is also something the user did long time ago.  I
> do not think it is so cut-and-dried which one of the two conflicting
> wishes we should honor when running the second repack, especially
> when it is run unattended like "gc --auto" does.

Good points. Explicitly saying "repack --depth=..." carries a lot more
weight to me than "git gc --auto" randomly kicking in, as far as knowing
that what the user actually wants. My patch doesn't differentiate, of
course, but I think it could.

The other problem with my patch is the fact that we don't do a good job
of finding new, in-limit deltas for the ones we discard. If you want to
do that, you really need to "git repack -f" (at least with the current
code). At which point we do not reuse the on-disk deltas at all, and the
problem is moot (you could also interpret the fact that the user did
_not_ pass "-f" as "you want to reuse deltas, which means you want to
reuse even long chains", but as you've argued above, you can make a lot
of guesses about the user's intention from what they did or did not
say).

So if we were to go this route, I don't think my patch is quite
sufficient; we'd want something else on top to do a better job of
finding replacement deltas.

Regarding my "does not seem that effective" above, I think we should
drop the aggressive depth to 50, and I just posted a patch with
reasoning and numbers:

  http://public-inbox.org/git/20160811161309.ecmebaafcz6rkg6o@sigill.intra.peff.net/

That's maybe orthogonal, but it does remove the weird "gc --aggressive
followed by gc --auto produces a bad pack" issue, because unless you are
doing something clever, the depth will always be 50 (modulo people who
did an aggressive pack with an older version of git :-/ ).

-Peff

[PATCH v3 2/2] pack-objects: use mru list when iterating over packs

[Jeff King]

In the original implementation of want_object_in_pack(), we
always looked for the object in every pack, so the order did
not matter for performance.

As of the last few patches, however, we can now often break
out of the loop early after finding the first instance, and
avoid looking in the other packs at all. In this case, pack
order can make a big difference, because we'd like to find
the objects by looking at as few packs as possible.

This patch switches us to the same packed_git_mru list that
is now used by normal object lookups.

Here are timings for p5303 on linux.git:

Test                      HEAD^                HEAD
------------------------------------------------------------------------
5303.3: rev-list (1)      31.31(31.07+0.23)    31.28(31.00+0.27) -0.1%
5303.4: repack (1)        40.35(38.84+2.60)    40.53(39.31+2.32) +0.4%
5303.6: rev-list (50)     31.37(31.15+0.21)    31.41(31.16+0.24) +0.1%
5303.7: repack (50)       58.25(68.54+2.03)    47.28(57.66+1.89) -18.8%
5303.9: rev-list (1000)   31.91(31.57+0.33)    31.93(31.64+0.28) +0.1%
5303.10: repack (1000)    304.80(376.00+3.92)  87.21(159.54+2.84) -71.4%

The rev-list numbers are unchanged, which makes sense (they
are not exercising this code at all). The 50- and 1000-pack
repack cases show considerable improvement.

The single-pack repack case doesn't, of course; there's
nothing to improve. In fact, it gives us a baseline for how
fast we could possibly go. You can see that though rev-list
can approach the single-pack case even with 1000 packs,
repack doesn't. The reason is simple: the loop we are
optimizing is only part of what the repack is doing. After
the "counting" phase, we do delta compression, which is much
more expensive when there are multiple packs, because we
have fewer deltas we can reuse (you can also see that these
numbers come from a multicore machine; the CPU times are
much higher than the wall-clock times due to the delta
phase).

So the good news is that in cases with many packs, we used
to be dominated by the "counting" phase, and now we are
dominated by the delta compression (which is faster, and
which we have already parallelized).

Here are similar numbers for git.git:

Test                      HEAD^               HEAD
---------------------------------------------------------------------
5303.3: rev-list (1)      1.55(1.51+0.02)     1.54(1.53+0.00) -0.6%
5303.4: repack (1)        1.82(1.80+0.08)     1.82(1.78+0.09) +0.0%
5303.6: rev-list (50)     1.58(1.57+0.00)     1.58(1.56+0.01) +0.0%
5303.7: repack (50)       2.50(3.12+0.07)     2.31(2.95+0.06) -7.6%
5303.9: rev-list (1000)   2.22(2.20+0.02)     2.23(2.19+0.03) +0.5%
5303.10: repack (1000)    10.47(16.78+0.22)   7.50(13.76+0.22) -28.4%

Not as impressive in terms of percentage, but still
measurable wins.  If you look at the wall-clock time
improvements in the 1000-pack case, you can see that linux
improved by roughly 10x as many seconds as git. That's
because it has roughly 10x as many objects, and we'd expect
this improvement to scale linearly with the number of
objects (since the number of packs is kept constant). It's
just that the "counting" phase is a smaller percentage of
the total time spent for a git.git repack, and hence the
percentage win is smaller.

The implementation itself is a straightforward use of the
MRU code. We only bother marking a pack as used when we know
that we are able to break early out of the loop, for two
reasons:

  1. If we can't break out early, it does no good; we have
     to visit each pack anyway, so we might as well avoid
     even the minor overhead of managing the cache order.

  2. The mru_mark() function reorders the list, which would
     screw up our traversal. So it is only safe to mark when
     we are about to break out of the loop. We could record
     the found pack and mark it after the loop finishes, of
     course, but that's more complicated and it doesn't buy
     us anything due to (1).

Note that this reordering does have a potential impact on
the final pack, as we store only a single "found" pack for
each object, even if it is present in multiple packs. In
principle, any copy is acceptable, as they all refer to the
same content. But in practice, they may differ in whether
they are stored as deltas, against which base, etc. This may
have an impact on delta reuse, and even the delta search
(since we skip pairs that were already in the same pack).

It's not clear whether this change of order would hurt or
even help average cases, though. The most likely reason to
have duplicate objects is from the completion of thin packs
(e.g., you have some objects in a "base" pack, then receive
several pushes; the packs you receive may be thin on the
wire, with deltas that refer to bases outside the pack, but
we complete them with duplicate base objects when indexing
them).

In such a case the current code would always find the thin
duplicates (because we currently walk the packs in reverse
chronological order). Whereas with this patch, some of those
duplicates would be found in the base pack instead.

In my tests repacking a real-world case of linux.git with
3600 thin-pack pushes (on top of a large "base" pack), the
resulting pack was about 0.04% larger with this patch. On
the other hand, because we were more likely to hit the base
pack, there were more opportunities for delta reuse, and we
had 50,000 fewer objects to examine in the delta search.

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

diff --git a/builtin/pack-objects.c b/builtin/pack-objects.c
index 3e30eae..f89a206 100644
--- a/builtin/pack-objects.c
+++ b/builtin/pack-objects.c
@@ -23,6 +23,7 @@
 #include "reachable.h"
 #include "sha1-array.h"
 #include "argv-array.h"
+#include "mru.h"
 
 static const char *pack_usage[] = {
 	N_("git pack-objects --stdout [<options>...] [< <ref-list> | < <object-list>]"),
@@ -958,7 +959,7 @@ static int want_object_in_pack(const unsigned char *sha1,
 			       struct packed_git **found_pack,
 			       off_t *found_offset)
 {
-	struct packed_git *p;
+	struct mru_entry *entry;
 
 	if (!exclude && local && has_loose_object_nonlocal(sha1))
 		return 0;
@@ -966,7 +967,8 @@ static int want_object_in_pack(const unsigned char *sha1,
 	*found_pack = NULL;
 	*found_offset = 0;
 
-	for (p = packed_git; p; p = p->next) {
+	for (entry = packed_git_mru->head; entry; entry = entry->next) {
+		struct packed_git *p = entry->item;
 		off_t offset = find_pack_entry_one(sha1, p);
 		if (offset) {
 			if (!*found_pack) {
@@ -993,8 +995,10 @@ static int want_object_in_pack(const unsigned char *sha1,
 			 * out of the loop to return 1 now.
 			 */
 			if (!ignore_packed_keep &&
-			    (!local || !have_non_local_packs))
+			    (!local || !have_non_local_packs)) {
+				mru_mark(packed_git_mru, entry);
 				break;
+			}
 
 			if (local && !p->pack_local)
 				return 0;
-- 
2.9.2.790.gaa5bc72

Re: [PATCH v3 0/2] pack-objects mru

[Junio C Hamano]

Jeff King <peff@peff.net> writes:

>> This is not new with this change, but I am not quite sure what in
>> the current code prevents us from busting the delta limit for reused
>> ones, though.
>
> I think in the current code you are limited by the depth you might find
> in a single existing pack (since we never reuse cross-pack deltas).

Sorry for going deeper in the tangent, but I vaguely recall raising
it long time ago as a potential issue that delta reuse out of an
original pack created with deep delta chain may bust a delta chain
limit when repacking with shorter delta chain limit; I just do not
remember where that discussion went (i.e. decided to be a non-issue?
we added code to avoid it? etc.)

> However, I think with cross-pack deltas, you could have a situation
> like:
>
>   pack 1: A -> B -> C
>   pack 2: C -> D -> E
>
> and pick A and B from the first pack, and C, D, and E from the second.
> Then you end up with:
>
>   A -> B -> C -> D -> E
>
> in the output. IOW, I think the absolute worst case chain is the
> max_depth times the number of packs.

Also if pack1 and pack2 were created with depth limit of 3 and we
are repacking with depth limit of 2, then we are busting the limit
already with or without cross-pack chaining, I would think.

> I'm not sure how much we should be worried about it. We could fill in
> the depth values when adding a reused delta, but I don't think we have
> the number handy; we'd have to actually walk the chain (though with
> delta-base-offset, that is reasonably cheap).

True.  It is something we may want to keep back in our mind and
revisit later.  It is definitely not a low-hanging fruit, but
something that should go to the leftover-bits list.

> The second patch is the same as before, though I tweaked the commit
> message a bit, so please replace what is at the tip of
> jk/pack-objects-optim-mru.
>
>   [1/2]: pack-objects: break delta cycles before delta-search phase
>   [2/2]: pack-objects: use mru list when iterating over packs

Thanks.

Re: [PATCH v3 0/2] pack-objects mru

[Jeff King]

On Wed, Aug 10, 2016 at 09:47:52AM -0700, Junio C Hamano wrote:

> Jeff King <peff@peff.net> writes:
> 
> >> This is not new with this change, but I am not quite sure what in
> >> the current code prevents us from busting the delta limit for reused
> >> ones, though.
> >
> > I think in the current code you are limited by the depth you might find
> > in a single existing pack (since we never reuse cross-pack deltas).
> 
> Sorry for going deeper in the tangent, but I vaguely recall raising
> it long time ago as a potential issue that delta reuse out of an
> original pack created with deep delta chain may bust a delta chain
> limit when repacking with shorter delta chain limit; I just do not
> remember where that discussion went (i.e. decided to be a non-issue?
> we added code to avoid it? etc.)

Digging on the list and in the history, I found your e4c9327
(pack-objects: avoid delta chains that are too long., 2006-02-17). That
approach went away with Nico's 898b14c (pack-objects: rework
check_delta_limit usage, 2007-04-16), which I think is where we are at
today.

I found the patches for both on the list, but no interesting discussion.

It looks like 898b14c does the depth check dynamically in find_delta. So
we would not build on a too-long chain, but I do not see anything that
prevents us from creating a too-long chain purely out of reused deltas.

Which means that even without my patches, repacking with a shorter delta
chain does not guarantee you do not have a longer chain. And mine
introduces a potential "packs * max_depth" problem (I also think
check_delta_limit could recurse very deeply if given a pathologically
weird pack that has insane delta limits, but presumably we would just
run out of stack and crash, which seems like an OK outcome for such
maliciousness).

I guess it would not be that hard to break the reused chains as part of
the DFS search I introduced (we are recursing already; just stop
recursing and break when we hit the max-depth).

> > However, I think with cross-pack deltas, you could have a situation
> > like:
> >
> >   pack 1: A -> B -> C
> >   pack 2: C -> D -> E
> >
> > and pick A and B from the first pack, and C, D, and E from the second.
> > Then you end up with:
> >
> >   A -> B -> C -> D -> E
> >
> > in the output. IOW, I think the absolute worst case chain is the
> > max_depth times the number of packs.
> 
> Also if pack1 and pack2 were created with depth limit of 3 and we
> are repacking with depth limit of 2, then we are busting the limit
> already with or without cross-pack chaining, I would think.

Right, though that is at least bounded to "what you packed with before",
which people do not usually change (OTOH, we accept packs from random
strangers via the protocol).

-Peff