Avoid rewriting "packed-refs" unnecessarily

This reroll make some logically small changes to v1 [1] that are textually very big:

* Invert the sense of is_packed_transaction_noop() and rename it to is_packed_transaction_needed(). This makes the logic easier to follow and document.

* Add a big comment to that function, describing the cases when it returns false positives and explaining why that isn't a problem.

* In the commit message for patch 02, gives a lot more information about the regression that it is fixing. Thanks to Eric for the suggestion.

These patches are also available as branch avoid-rewriting-packed-refs on my GitHub fork [2]. They now use mh/packed-ref-transactions as the base, since that is where Junio chose to apply v1.

Michael

[1] https://public-inbox.org/git/[email protected]/
[2] 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         |  94 +++++++++++++++++++++++++++++++++
 refs/packed-backend.h         |   9 ++++
 t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 238 insertions(+), 1 deletion(-)
 create mode 100755 t/t1409-avoid-packing-refs.sh

2.14.1

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.

---
 t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 118 insertions(+)
 create mode 100755 t/t1409-avoid-packing-refs.sh

new file mode 100755
index 0000000000..a2397c7b71
@@ -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

Even when we are deleting references, we needn't overwrite the packed-refs file if the references that we are deleting only exist as loose references. Implement this optimization as follows:

* Add a function is_packed_transaction_needed(), which checks whether a given packed-refs transaction actually needs to be carried out (i.e., it returns false if the transaction obviously wouldn't have any effect). 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 actually needed. If not, squelch it, but continue holding the packed-refs lock until the end of the transaction to avoid races.

This fixes a mild regression caused by dc39e09942 (files_ref_store:
use a transaction to update packed refs, 2017-09-08). Before that commit, unnecessary rewrites of packed-refs were suppressed by repack_without_refs(). But the transaction-based writing introduced by that commit didn't perform that optimization.

Note that the pre-dc39e09942 code still had to *read* the whole packed-refs file to determine that the rewrite could be skipped, so the performance for the cases that the write could be elided was O(N) in the number of packed references both before and after dc39e09942. But after that commit the constant factor increased.

This commit reimplements the optimization of eliding unnecessary packed-refs rewrites. That, plus the fact that since cfa2e29c34 (packed_ref_store: get rid of the ref_cache entirely, 2017-03-17) we don't necessarily have to read the whole packed-refs file at all, means that deletes of one or a few loose references can now be done with O(n lg N) effort, where n is the number of loose references being deleted and N is the total number of packed references.

This commit fixes two tests in t1409.

---
 refs/files-backend.c          | 18 ++++++++-
 refs/packed-backend.c         | 94 +++++++++++++++++++++++++++++++++++++++++++
 refs/packed-backend.h         |  9 +++++
 t/t1409-avoid-packing-refs.sh |  4 +-
 4 files changed, 122 insertions(+), 3 deletions(-)

index 961424a4ea..da8a986697 100644
@@ -2562,7 +2562,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_needed(refs->packed_ref_store,
+						 packed_transaction)) {
+			ret = ref_transaction_prepare(packed_transaction, err);
+		} else {
+			/*
+			 * 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;
+		}
 	}
 
 cleanup:

index 61687e408a..640245d3b9 100644
@@ -23,4 +23,13 @@ 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` really needs to be carried out against
+ * the specified packed_ref_store, or false if it can be skipped
+ * (i.e., because it is an obvious NOOP). `ref_store` must be locked
+ * before calling this function.
+ */
+int is_packed_transaction_needed(struct ref_store *ref_store,
+				 struct ref_transaction *transaction);
+
 #endif /* REFS_PACKED_BACKEND_H */

index a2397c7b71..e5cb8a252d 100755
@@ -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

This all makes sense to me. I agree that the "is_needed" logic-flip in v2 makes it a little easier to think about.

Like Junio, I was thrown off at first by the HAVE_OLD check. Especially since we would not ever set that flag for the transaction we care about here. But I think the crux of it is that the packed_ref store code could in theory operate independently of the loose ref code, where we feed it more exotic inputs. And what you've written here is future-proofing against the more general case, even though it would not be strictly necessary.

-Peff