[PATCH 0/2] Avoid rewriting "packed-refs" unnecessarily

[PATCH 0/2] Avoid rewriting "packed-refs" unnecessarily

[Michael Haggerty]

Since commit dc39e09942 (files_ref_store: use a transaction to update
packed refs, 2017-09-08), we've been rewriting the `packed-refs` file
unnecessarily when deleting a loose reference that has no packed
counterpart. Add some tests demonstrating this problem, then fix it by
teaching `files_backend` to see whether any references being deleted
have packed versions, and if not, skipping the packed_refs
transaction.

This is a mild regression since 2.14, which avoided rewriting the
`packed-refs` file in these cases (though it still had to *read* the
whole file to determine whether the rewrite could be skipped).
Therefore, it might be considered for 2.15. On the other hand, it is
late in the release cycle, so the risk of accepting this change might
be considered too risky.

These patches apply on top of master and commute with
mh/ref-locking-fix. They are also available from my GitHub fork [1] as
branch `avoid-rewriting-packed-refs`.

Michael

[1] https://github.com/mhagger/git

Michael Haggerty (2):
  t1409: check that `packed-refs` is not rewritten unnecessarily
  files-backend: don't rewrite the `packed-refs` file unnecessarily

 refs/files-backend.c          |  18 ++++++-
 refs/packed-backend.c         |  68 ++++++++++++++++++++++++
 refs/packed-backend.h         |   8 +++
 t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 211 insertions(+), 1 deletion(-)
 create mode 100755 t/t1409-avoid-packing-refs.sh

-- 
2.14.1

[PATCH 1/2] t1409: check that `packed-refs` is not rewritten unnecessarily

[Michael Haggerty]

There is no need to rewrite the `packed-refs` file except for the case
that we are deleting a reference that has a packed version. Verify
that `packed-refs` is not rewritten when it shouldn't be.

In fact, two of these tests fail:

* A new (empty) `packed-refs` file is created when deleting any loose
  reference and no `packed-refs` file previously existed.

* The `packed-refs` file is rewritten unnecessarily when deleting a
  loose reference that has no packed counterpart.

Both problems will be fixed in the next commit.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 118 insertions(+)
 create mode 100755 t/t1409-avoid-packing-refs.sh

diff --git a/t/t1409-avoid-packing-refs.sh b/t/t1409-avoid-packing-refs.sh
new file mode 100755
index 0000000000..a2397c7b71
--- /dev/null
+++ b/t/t1409-avoid-packing-refs.sh
@@ -0,0 +1,118 @@
+#!/bin/sh
+
+test_description='avoid rewriting packed-refs unnecessarily'
+
+. ./test-lib.sh
+
+# Add an identifying mark to the packed-refs file header line. This
+# shouldn't upset readers, and it should be omitted if the file is
+# ever rewritten.
+mark_packed_refs () {
+	sed -e "s/^\(#.*\)/\1 t1409 /" <.git/packed-refs >.git/packed-refs.new &&
+	mv .git/packed-refs.new .git/packed-refs
+}
+
+# Verify that the packed-refs file is still marked.
+check_packed_refs_marked () {
+	grep -q '^#.* t1409 ' .git/packed-refs
+}
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m "Commit A" &&
+	A=$(git rev-parse HEAD) &&
+	git commit --allow-empty -m "Commit B" &&
+	B=$(git rev-parse HEAD) &&
+	git commit --allow-empty -m "Commit C" &&
+	C=$(git rev-parse HEAD)
+'
+
+test_expect_failure 'do not create packed-refs file gratuitously' '
+	test_must_fail test -f .git/packed-refs &&
+	git update-ref refs/heads/foo $A &&
+	test_must_fail test -f .git/packed-refs &&
+	git update-ref refs/heads/foo $B &&
+	test_must_fail test -f .git/packed-refs &&
+	git update-ref refs/heads/foo $C $B &&
+	test_must_fail test -f .git/packed-refs &&
+	git update-ref -d refs/heads/foo &&
+	test_must_fail test -f .git/packed-refs
+'
+
+test_expect_success 'check that marking the packed-refs file works' '
+	git for-each-ref >expected &&
+	git pack-refs --all &&
+	mark_packed_refs &&
+	check_packed_refs_marked &&
+	git for-each-ref >actual &&
+	test_cmp expected actual &&
+	git pack-refs --all &&
+	test_must_fail check_packed_refs_marked &&
+	git for-each-ref >actual2 &&
+	test_cmp expected actual2
+'
+
+test_expect_success 'leave packed-refs untouched on update of packed' '
+	git update-ref refs/heads/packed-update $A &&
+	git pack-refs --all &&
+	mark_packed_refs &&
+	git update-ref refs/heads/packed-update $B &&
+	check_packed_refs_marked
+'
+
+test_expect_success 'leave packed-refs untouched on checked update of packed' '
+	git update-ref refs/heads/packed-checked-update $A &&
+	git pack-refs --all &&
+	mark_packed_refs &&
+	git update-ref refs/heads/packed-checked-update $B $A &&
+	check_packed_refs_marked
+'
+
+test_expect_success 'leave packed-refs untouched on verify of packed' '
+	git update-ref refs/heads/packed-verify $A &&
+	git pack-refs --all &&
+	mark_packed_refs &&
+	echo "verify refs/heads/packed-verify $A" | git update-ref --stdin &&
+	check_packed_refs_marked
+'
+
+test_expect_success 'touch packed-refs on delete of packed' '
+	git update-ref refs/heads/packed-delete $A &&
+	git pack-refs --all &&
+	mark_packed_refs &&
+	git update-ref -d refs/heads/packed-delete &&
+	test_must_fail check_packed_refs_marked
+'
+
+test_expect_success 'leave packed-refs untouched on update of loose' '
+	git pack-refs --all &&
+	git update-ref refs/heads/loose-update $A &&
+	mark_packed_refs &&
+	git update-ref refs/heads/loose-update $B &&
+	check_packed_refs_marked
+'
+
+test_expect_success 'leave packed-refs untouched on checked update of loose' '
+	git pack-refs --all &&
+	git update-ref refs/heads/loose-checked-update $A &&
+	mark_packed_refs &&
+	git update-ref refs/heads/loose-checked-update $B $A &&
+	check_packed_refs_marked
+'
+
+test_expect_success 'leave packed-refs untouched on verify of loose' '
+	git pack-refs --all &&
+	git update-ref refs/heads/loose-verify $A &&
+	mark_packed_refs &&
+	echo "verify refs/heads/loose-verify $A" | git update-ref --stdin &&
+	check_packed_refs_marked
+'
+
+test_expect_failure 'leave packed-refs untouched on delete of loose' '
+	git pack-refs --all &&
+	git update-ref refs/heads/loose-delete $A &&
+	mark_packed_refs &&
+	git update-ref -d refs/heads/loose-delete &&
+	check_packed_refs_marked
+'
+
+test_done
-- 
2.14.1

[PATCH 2/2] files-backend: don't rewrite the `packed-refs` file unnecessarily

[Michael Haggerty]

Even when we are deleting references, we needn't overwrite the
`packed-refs` file if the references that we are deleting are not
present in that file. Implement this optimization as follows:

* Add a function `is_packed_transaction_noop()`, which checks whether
  a given packed-refs transaction doesn't actually have to do
  anything. This function must be called while holding the
  `packed-refs` lock to avoid races.

* Change `files_transaction_prepare()` to check whether the
  packed-refs transaction is unneeded. If so, squelch it, but continue
  holding the `packed-refs` lock until the end of the transaction to
  avoid races.

This fixes two tests in t1409.

Signed-off-by: Michael Haggerty <mhagger@alum.mit.edu>
---
 refs/files-backend.c          | 18 +++++++++++-
 refs/packed-backend.c         | 68 +++++++++++++++++++++++++++++++++++++++++++
 refs/packed-backend.h         |  8 +++++
 t/t1409-avoid-packing-refs.sh |  4 +--
 4 files changed, 95 insertions(+), 3 deletions(-)

diff --git a/refs/files-backend.c b/refs/files-backend.c
index 014dabb0bf..5689e3a58d 100644
--- a/refs/files-backend.c
+++ b/refs/files-backend.c
@@ -2605,7 +2605,23 @@ static int files_transaction_prepare(struct ref_store *ref_store,
 			goto cleanup;
 		}
 		backend_data->packed_refs_locked = 1;
-		ret = ref_transaction_prepare(packed_transaction, err);
+
+		if (is_packed_transaction_noop(refs->packed_ref_store,
+					       packed_transaction)) {
+			/*
+			 * We can skip rewriting the `packed-refs`
+			 * file. But we do need to leave it locked, so
+			 * that somebody else doesn't pack a reference
+			 * that we are trying to delete.
+			 */
+			if (ref_transaction_abort(packed_transaction, err)) {
+				ret = TRANSACTION_GENERIC_ERROR;
+				goto cleanup;
+			}
+			backend_data->packed_transaction = NULL;
+		} else {
+			ret = ref_transaction_prepare(packed_transaction, err);
+		}
 	}
 
 cleanup:
diff --git a/refs/packed-backend.c b/refs/packed-backend.c
index 3279d42c5a..064b1b58a2 100644
--- a/refs/packed-backend.c
+++ b/refs/packed-backend.c
@@ -1261,6 +1261,74 @@ static int write_with_updates(struct packed_ref_store *refs,
 	return -1;
 }
 
+int is_packed_transaction_noop(struct ref_store *ref_store,
+			       struct ref_transaction *transaction)
+{
+	struct packed_ref_store *refs = packed_downcast(
+			ref_store,
+			REF_STORE_READ,
+			"is_packed_transaction_noop");
+	struct strbuf referent = STRBUF_INIT;
+	size_t i;
+	int ret;
+
+	if (!is_lock_file_locked(&refs->lock))
+		BUG("is_packed_transaction_noop() called while unlocked");
+
+	/*
+	 * We're only going to bother returning true for the common,
+	 * trivial case that references are only being deleted, their
+	 * old values are not being checked, and the old `packed-refs`
+	 * file doesn't contain any of those reference(s). More
+	 * complicated cases (1) are unlikely to be able to be
+	 * optimized away anyway, and (2) are more expensive to check.
+	 * Start with cheap checks:
+	 */
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+
+		if (update->flags & REF_HAVE_OLD)
+			/* Have to check the old value -> not a NOOP. */
+			return 0;
+
+		if ((update->flags & REF_HAVE_NEW) && !is_null_oid(&update->new_oid))
+			/* Have to set a new value -> not a NOOP. */
+			return 0;
+	}
+
+	/*
+	 * The transaction isn't checking any old values nor is it
+	 * setting any nonzero new values, so it still might be a
+	 * NOOP. Now do the more expensive check: the update is not a
+	 * NOOP if one of the updates is a delete, and the old
+	 * `packed-refs` file contains a value for that reference.
+	 */
+	ret = 1;
+	for (i = 0; i < transaction->nr; i++) {
+		struct ref_update *update = transaction->updates[i];
+		unsigned int type;
+		struct object_id oid;
+
+		if (!(update->flags & REF_HAVE_NEW))
+			/* This reference isn't being deleted -> NOOP. */
+			continue;
+
+		if (!refs_read_raw_ref(ref_store, update->refname,
+				       oid.hash, &referent, &type) ||
+		    errno != ENOENT) {
+			/*
+			 * We might have to actually delete that
+			 * reference -> not a NOOP.
+			 */
+			ret = 0;
+			break;
+		}
+	}
+
+	strbuf_release(&referent);
+	return ret;
+}
+
 struct packed_transaction_backend_data {
 	/* True iff the transaction owns the packed-refs lock. */
 	int own_lock;
diff --git a/refs/packed-backend.h b/refs/packed-backend.h
index 61687e408a..0b8b2b9695 100644
--- a/refs/packed-backend.h
+++ b/refs/packed-backend.h
@@ -23,4 +23,12 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)
 void packed_refs_unlock(struct ref_store *ref_store);
 int packed_refs_is_locked(struct ref_store *ref_store);
 
+/*
+ * Return true if `transaction` is an obvious NOOP with respect to the
+ * specified packed_ref_store. `ref_store` must be locked before
+ * calling this function.
+ */
+int is_packed_transaction_noop(struct ref_store *ref_store,
+			       struct ref_transaction *transaction);
+
 #endif /* REFS_PACKED_BACKEND_H */
diff --git a/t/t1409-avoid-packing-refs.sh b/t/t1409-avoid-packing-refs.sh
index a2397c7b71..e5cb8a252d 100755
--- a/t/t1409-avoid-packing-refs.sh
+++ b/t/t1409-avoid-packing-refs.sh
@@ -26,7 +26,7 @@ test_expect_success 'setup' '
 	C=$(git rev-parse HEAD)
 '
 
-test_expect_failure 'do not create packed-refs file gratuitously' '
+test_expect_success 'do not create packed-refs file gratuitously' '
 	test_must_fail test -f .git/packed-refs &&
 	git update-ref refs/heads/foo $A &&
 	test_must_fail test -f .git/packed-refs &&
@@ -107,7 +107,7 @@ test_expect_success 'leave packed-refs untouched on verify of loose' '
 	check_packed_refs_marked
 '
 
-test_expect_failure 'leave packed-refs untouched on delete of loose' '
+test_expect_success 'leave packed-refs untouched on delete of loose' '
 	git pack-refs --all &&
 	git update-ref refs/heads/loose-delete $A &&
 	mark_packed_refs &&
-- 
2.14.1

Re: [PATCH 0/2] Avoid rewriting "packed-refs" unnecessarily

[Eric Sunshine]

On Wed, Oct 25, 2017 at 5:53 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
> Since commit dc39e09942 (files_ref_store: use a transaction to update
> packed refs, 2017-09-08), we've been rewriting the `packed-refs` file
> unnecessarily when deleting a loose reference that has no packed
> counterpart. Add some tests demonstrating this problem, then fix it by
> teaching `files_backend` to see whether any references being deleted
> have packed versions, and if not, skipping the packed_refs
> transaction.
>
> This is a mild regression since 2.14, which avoided rewriting the
> `packed-refs` file in these cases [...]

Should the above information (that this fixes a regression) be
mentioned in the commit message of at least one of the patches
(probably 2/2)? Without such context, it may not be clear to someone
later reading those commit message -- someone who wasn't following
this email discussion -- that this behavior had been lost and is now
being restored.

Re: [PATCH 2/2] files-backend: don't rewrite the `packed-refs` file unnecessarily

[Junio C Hamano]

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

> Even when we are deleting references, we needn't overwrite the
> `packed-refs` file if the references that we are deleting are not
> present in that file. Implement this optimization as follows:

This goal I can understand.  files-transaction-prepare may see a
deletion and in order to avoid a deletion of a ref from the
file-backend to expose a stale entry in the packed-refs file, it
prepares a transaction to remove the same ref that might exist in
it.  If it turns out that there is no such ref in the packed-refs
file, then we can leave the packed-refs file as-is without
rewriting.

> * Add a function `is_packed_transaction_noop()`, which checks whether
>   a given packed-refs transaction doesn't actually have to do
>   anything. This function must be called while holding the
>   `packed-refs` lock to avoid races.

This checks three things only to cover the most trivial case (I am
perfectly happy that it punts on more complex cases).  If an update

 - checks the old value,

 - sets a new value, or

 - deletes a ref that is not on the filesystem,

it is not a trivial case.  I can understand the latter two (i.e. We
are special casing the deletion, and an update with a new value is
not.  If removing a file from the filesystem is not sufficient to
delete, we may have to rewrite the packed-refs), but not the first
one.  Is it because currently we do not say "delete this ref only
when its current value is X"?

Also it is not immediately obvious how the "is this noop" helper is
checking the absence of the same-named ref in the current
packed-refs file, which is what matters for the correctness of the
optimization.

Re: [PATCH 2/2] files-backend: don't rewrite the `packed-refs` file unnecessarily

[Michael Haggerty]

On 10/26/2017 08:46 AM, Junio C Hamano wrote:
> Michael Haggerty <mhagger@alum.mit.edu> writes:
> 
>> Even when we are deleting references, we needn't overwrite the
>> `packed-refs` file if the references that we are deleting are not
>> present in that file. Implement this optimization as follows:
> 
> This goal I can understand.  files-transaction-prepare may see a
> deletion and in order to avoid a deletion of a ref from the
> file-backend to expose a stale entry in the packed-refs file, it
> prepares a transaction to remove the same ref that might exist in
> it.  If it turns out that there is no such ref in the packed-refs
> file, then we can leave the packed-refs file as-is without
> rewriting.
> 
>> * Add a function `is_packed_transaction_noop()`, which checks whether
>>   a given packed-refs transaction doesn't actually have to do
>>   anything. This function must be called while holding the
>>   `packed-refs` lock to avoid races.
> 
> This checks three things only to cover the most trivial case (I am
> perfectly happy that it punts on more complex cases).  If an update
> 
>  - checks the old value,
> 
>  - sets a new value, or
> 
>  - deletes a ref that is not on the filesystem,
> 
> it is not a trivial case.  I can understand the latter two (i.e. We
> are special casing the deletion, and an update with a new value is
> not.  If removing a file from the filesystem is not sufficient to
> delete, we may have to rewrite the packed-refs), but not the first
> one.  Is it because currently we do not say "delete this ref only
> when its current value is X"?

It wouldn't be too hard to allow updates with REF_HAVE_OLD to be
optimized away too. I didn't do it because

1. We currently only create updates for that packed_refs backend with
REF_HAVE_OLD turned off, so such could would be unreachable (and
untestable).

2. I wanted to keep the patch as simple as possible in case you decide
to merge it into 2.15.

There would also be a little bit of a leveling violation (or maybe the
function name is not ideal). `is_packed_transaction_noop()` could check
that `old_oid` values are correct, and if they all are, declare the
transaction a NOOP. (It wasn't *really* a NOOP, but its OP, namely
checking old values, has already been carried out.) But what if it finds
that an `old_oid` was incorrect? Right now
`is_packed_transaction_noop()` has no way to report something like a
TRANSACTION_GENERIC_ERROR.

It could be that long-term it makes more sense for this optimization to
happen in `packed_transaction_prepare()`. Except that function is
sometimes called for its side-effects, like sorting an existing file, in
which case overwriting the `packed-refs` file shouldn't be optimized away.

So overall it seemed easier to punt on this optimization at this point.

> Also it is not immediately obvious how the "is this noop" helper is
> checking the absence of the same-named ref in the current
> packed-refs file, which is what matters for the correctness of the
> optimization.

The check is in the second loop in `is_packed_transaction_noop()`:

	if (!refs_read_raw_ref(ref_store, update->refname,
			       oid.hash, &referent, &type) ||
	    errno != ENOENT) {
		/*
		 * We might have to actually delete that
		 * reference -> not a NOOP.
		 */
		ret = 0;
		break;
	}

If the refname doesn't exist, then `refs_read_raw_ref()` returns -1 and
sets errno to ENOENT, and the loop continues. Otherwise we exit with a
value of 0, meaning that the transaction is not a NOOP.

There are a lot of double-negatives here. It might be easier to follow
the logic if the sense of the function were inverted:
`is_packed_transaction_needed()`. Let me know if you have a strong
feeling about it.

Michael

Re: [PATCH 0/2] Avoid rewriting "packed-refs" unnecessarily

[Michael Haggerty]

On 10/25/2017 10:10 PM, Eric Sunshine wrote:
> On Wed, Oct 25, 2017 at 5:53 AM, Michael Haggerty <mhagger@alum.mit.edu> wrote:
>> Since commit dc39e09942 (files_ref_store: use a transaction to update
>> packed refs, 2017-09-08), we've been rewriting the `packed-refs` file
>> unnecessarily when deleting a loose reference that has no packed
>> counterpart. Add some tests demonstrating this problem, then fix it by
>> teaching `files_backend` to see whether any references being deleted
>> have packed versions, and if not, skipping the packed_refs
>> transaction.
>>
>> This is a mild regression since 2.14, which avoided rewriting the
>> `packed-refs` file in these cases [...]
> 
> Should the above information (that this fixes a regression) be
> mentioned in the commit message of at least one of the patches
> (probably 2/2)? Without such context, it may not be clear to someone
> later reading those commit message -- someone who wasn't following
> this email discussion -- that this behavior had been lost and is now
> being restored.

Yes, that's a good idea. I'll send a re-roll with that change.

Michael