{"thread":{"id":"47051","subject":"[PATCH v2 1/2] t1409: check that `packed-refs` is not rewritten unnecessarily","startedAt":"2017-10-28T09:16:18Z","lastAt":"2017-11-01T07:38:07Z","messageCount":5,"participants":["Michael Haggerty","Junio C Hamano","Jeff King"],"isPatch":true,"patchVersion":2,"patchTotal":2},"messages":[{"id":"331206","messageId":"aac0252b94120fcfc6ae9c09531f76a252d423cc.1509181545.git.mhagger@alum.mit.edu","threadId":"47051","inReplyTo":"cover.1509181545.git.mhagger@alum.mit.edu","subject":"[PATCH v2 1/2] t1409: check that `packed-refs` is not rewritten unnecessarily","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-10-28T09:16:01Z","receivedAt":"2017-10-28T09:16:18Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"There is no need to rewrite the `packed-refs` file except for the case\nthat we are deleting a reference that has a packed version. Verify\nthat `packed-refs` is not rewritten when it shouldn't be.\n\nIn fact, two of these tests fail:\n\n* A new (empty) `packed-refs` file is created when deleting any loose\n  reference and no `packed-refs` file previously existed.\n\n* The `packed-refs` file is rewritten unnecessarily when deleting a\n  loose reference that has no packed counterpart.\n\nBoth problems will be fixed in the next commit.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++\n 1 file changed, 118 insertions(+)\n create mode 100755 t/t1409-avoid-packing-refs.sh\n\ndiff --git a/t/t1409-avoid-packing-refs.sh b/t/t1409-avoid-packing-refs.sh\nnew file mode 100755\nindex 0000000000..a2397c7b71\n--- /dev/null\n+++ b/t/t1409-avoid-packing-refs.sh\n@@ -0,0 +1,118 @@\n+#!/bin/sh\n+\n+test_description='avoid rewriting packed-refs unnecessarily'\n+\n+. ./test-lib.sh\n+\n+# Add an identifying mark to the packed-refs file header line. This\n+# shouldn't upset readers, and it should be omitted if the file is\n+# ever rewritten.\n+mark_packed_refs () {\n+\tsed -e \"s/^\\(#.*\\)/\\1 t1409 /\" <.git/packed-refs >.git/packed-refs.new &&\n+\tmv .git/packed-refs.new .git/packed-refs\n+}\n+\n+# Verify that the packed-refs file is still marked.\n+check_packed_refs_marked () {\n+\tgrep -q '^#.* t1409 ' .git/packed-refs\n+}\n+\n+test_expect_success 'setup' '\n+\tgit commit --allow-empty -m \"Commit A\" &&\n+\tA=$(git rev-parse HEAD) &&\n+\tgit commit --allow-empty -m \"Commit B\" &&\n+\tB=$(git rev-parse HEAD) &&\n+\tgit commit --allow-empty -m \"Commit C\" &&\n+\tC=$(git rev-parse HEAD)\n+'\n+\n+test_expect_failure 'do not create packed-refs file gratuitously' '\n+\ttest_must_fail test -f .git/packed-refs &&\n+\tgit update-ref refs/heads/foo $A &&\n+\ttest_must_fail test -f .git/packed-refs &&\n+\tgit update-ref refs/heads/foo $B &&\n+\ttest_must_fail test -f .git/packed-refs &&\n+\tgit update-ref refs/heads/foo $C $B &&\n+\ttest_must_fail test -f .git/packed-refs &&\n+\tgit update-ref -d refs/heads/foo &&\n+\ttest_must_fail test -f .git/packed-refs\n+'\n+\n+test_expect_success 'check that marking the packed-refs file works' '\n+\tgit for-each-ref >expected &&\n+\tgit pack-refs --all &&\n+\tmark_packed_refs &&\n+\tcheck_packed_refs_marked &&\n+\tgit for-each-ref >actual &&\n+\ttest_cmp expected actual &&\n+\tgit pack-refs --all &&\n+\ttest_must_fail check_packed_refs_marked &&\n+\tgit for-each-ref >actual2 &&\n+\ttest_cmp expected actual2\n+'\n+\n+test_expect_success 'leave packed-refs untouched on update of packed' '\n+\tgit update-ref refs/heads/packed-update $A &&\n+\tgit pack-refs --all &&\n+\tmark_packed_refs &&\n+\tgit update-ref refs/heads/packed-update $B &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_success 'leave packed-refs untouched on checked update of packed' '\n+\tgit update-ref refs/heads/packed-checked-update $A &&\n+\tgit pack-refs --all &&\n+\tmark_packed_refs &&\n+\tgit update-ref refs/heads/packed-checked-update $B $A &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_success 'leave packed-refs untouched on verify of packed' '\n+\tgit update-ref refs/heads/packed-verify $A &&\n+\tgit pack-refs --all &&\n+\tmark_packed_refs &&\n+\techo \"verify refs/heads/packed-verify $A\" | git update-ref --stdin &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_success 'touch packed-refs on delete of packed' '\n+\tgit update-ref refs/heads/packed-delete $A &&\n+\tgit pack-refs --all &&\n+\tmark_packed_refs &&\n+\tgit update-ref -d refs/heads/packed-delete &&\n+\ttest_must_fail check_packed_refs_marked\n+'\n+\n+test_expect_success 'leave packed-refs untouched on update of loose' '\n+\tgit pack-refs --all &&\n+\tgit update-ref refs/heads/loose-update $A &&\n+\tmark_packed_refs &&\n+\tgit update-ref refs/heads/loose-update $B &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_success 'leave packed-refs untouched on checked update of loose' '\n+\tgit pack-refs --all &&\n+\tgit update-ref refs/heads/loose-checked-update $A &&\n+\tmark_packed_refs &&\n+\tgit update-ref refs/heads/loose-checked-update $B $A &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_success 'leave packed-refs untouched on verify of loose' '\n+\tgit pack-refs --all &&\n+\tgit update-ref refs/heads/loose-verify $A &&\n+\tmark_packed_refs &&\n+\techo \"verify refs/heads/loose-verify $A\" | git update-ref --stdin &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_expect_failure 'leave packed-refs untouched on delete of loose' '\n+\tgit pack-refs --all &&\n+\tgit update-ref refs/heads/loose-delete $A &&\n+\tmark_packed_refs &&\n+\tgit update-ref -d refs/heads/loose-delete &&\n+\tcheck_packed_refs_marked\n+'\n+\n+test_done\n-- \n2.14.1\n\n"},{"id":"331207","messageId":"cover.1509181545.git.mhagger@alum.mit.edu","threadId":"47051","inReplyTo":null,"subject":"[PATCH v2 0/2] Avoid rewriting \"packed-refs\" unnecessarily","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-10-28T09:16:00Z","receivedAt":"2017-10-28T09:16:23Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"This reroll make some logically small changes to v1 [1] that are\ntextually very big:\n\n* Invert the sense of `is_packed_transaction_noop()` and rename it to\n  `is_packed_transaction_needed()`. This makes the logic easier to\n  follow and document.\n\n* Add a big comment to that function, describing the cases when it\n  returns false positives and explaining why that isn't a problem.\n\n* In the commit message for patch 02, gives a lot more information\n  about the regression that it is fixing. Thanks to Eric for the\n  suggestion.\n\nThese patches are also available as branch\n`avoid-rewriting-packed-refs` on my GitHub fork [2]. They now use\n`mh/packed-ref-transactions` as the base, since that is where Junio\nchose to apply v1.\n\nMichael\n\n[1] https://public-inbox.org/git/cover.1508924577.git.mhagger@alum.mit.edu/\n[2] https://github.com/mhagger/git\n\nMichael Haggerty (2):\n  t1409: check that `packed-refs` is not rewritten unnecessarily\n  files-backend: don't rewrite the `packed-refs` file unnecessarily\n\n refs/files-backend.c          |  18 ++++++-\n refs/packed-backend.c         |  94 +++++++++++++++++++++++++++++++++\n refs/packed-backend.h         |   9 ++++\n t/t1409-avoid-packing-refs.sh | 118 ++++++++++++++++++++++++++++++++++++++++++\n 4 files changed, 238 insertions(+), 1 deletion(-)\n create mode 100755 t/t1409-avoid-packing-refs.sh\n\n-- \n2.14.1\n\n"},{"id":"331208","messageId":"6004e1dea6af33cb41c523855757aa6b04b912bc.1509181545.git.mhagger@alum.mit.edu","threadId":"47051","inReplyTo":"cover.1509181545.git.mhagger@alum.mit.edu","subject":"[PATCH v2 2/2] files-backend: don't rewrite the `packed-refs` file unnecessarily","fromName":"Michael Haggerty","fromEmail":"mhagger@alum.mit.edu","sentAt":"2017-10-28T09:16:02Z","receivedAt":"2017-10-28T09:16:25Z","isPatch":true,"sender":{"key":"mhagger@alum.mit.edu","avatar":"https://avatars.githubusercontent.com/u/119718?v=4"},"body":"Even when we are deleting references, we needn't overwrite the\n`packed-refs` file if the references that we are deleting only exist\nas loose references. Implement this optimization as follows:\n\n* Add a function `is_packed_transaction_needed()`, which checks\n  whether a given packed-refs transaction actually needs to be carried\n  out (i.e., it returns false if the transaction obviously wouldn't\n  have any effect). This function must be called while holding the\n  `packed-refs` lock to avoid races.\n\n* Change `files_transaction_prepare()` to check whether the\n  packed-refs transaction is actually needed. If not, squelch it, but\n  continue holding the `packed-refs` lock until the end of the\n  transaction to avoid races.\n\nThis fixes a mild regression caused by dc39e09942 (files_ref_store:\nuse a transaction to update packed refs, 2017-09-08). Before that\ncommit, unnecessary rewrites of `packed-refs` were suppressed by\n`repack_without_refs()`. But the transaction-based writing introduced\nby that commit didn't perform that optimization.\n\nNote that the pre-dc39e09942 code still had to *read* the whole\n`packed-refs` file to determine that the rewrite could be skipped, so\nthe performance for the cases that the write could be elided was\n`O(N)` in the number of packed references both before and after\ndc39e09942. But after that commit the constant factor increased.\n\nThis commit reimplements the optimization of eliding unnecessary\n`packed-refs` rewrites. That, plus the fact that since\ncfa2e29c34 (packed_ref_store: get rid of the `ref_cache` entirely,\n2017-03-17) we don't necessarily have to read the whole `packed-refs`\nfile at all, means that deletes of one or a few loose references can\nnow be done with `O(n lg N)` effort, where `n` is the number of loose\nreferences being deleted and `N` is the total number of packed\nreferences.\n\nThis commit fixes two tests in t1409.\n\nSigned-off-by: Michael Haggerty <mhagger@alum.mit.edu>\n---\n refs/files-backend.c          | 18 ++++++++-\n refs/packed-backend.c         | 94 +++++++++++++++++++++++++++++++++++++++++++\n refs/packed-backend.h         |  9 +++++\n t/t1409-avoid-packing-refs.sh |  4 +-\n 4 files changed, 122 insertions(+), 3 deletions(-)\n\ndiff --git a/refs/files-backend.c b/refs/files-backend.c\nindex 961424a4ea..da8a986697 100644\n--- a/refs/files-backend.c\n+++ b/refs/files-backend.c\n@@ -2562,7 +2562,23 @@ static int files_transaction_prepare(struct ref_store *ref_store,\n \t\t\tgoto cleanup;\n \t\t}\n \t\tbackend_data->packed_refs_locked = 1;\n-\t\tret = ref_transaction_prepare(packed_transaction, err);\n+\n+\t\tif (is_packed_transaction_needed(refs->packed_ref_store,\n+\t\t\t\t\t\t packed_transaction)) {\n+\t\t\tret = ref_transaction_prepare(packed_transaction, err);\n+\t\t} else {\n+\t\t\t/*\n+\t\t\t * We can skip rewriting the `packed-refs`\n+\t\t\t * file. But we do need to leave it locked, so\n+\t\t\t * that somebody else doesn't pack a reference\n+\t\t\t * that we are trying to delete.\n+\t\t\t */\n+\t\t\tif (ref_transaction_abort(packed_transaction, err)) {\n+\t\t\t\tret = TRANSACTION_GENERIC_ERROR;\n+\t\t\t\tgoto cleanup;\n+\t\t\t}\n+\t\t\tbackend_data->packed_transaction = NULL;\n+\t\t}\n \t}\n \n cleanup:\ndiff --git a/refs/packed-backend.c b/refs/packed-backend.c\nindex 0279aeceea..0b0a17ca8e 100644\n--- a/refs/packed-backend.c\n+++ b/refs/packed-backend.c\n@@ -754,6 +754,100 @@ static int write_with_updates(struct packed_ref_store *refs,\n \treturn -1;\n }\n \n+int is_packed_transaction_needed(struct ref_store *ref_store,\n+\t\t\t\t struct ref_transaction *transaction)\n+{\n+\tstruct packed_ref_store *refs = packed_downcast(\n+\t\t\tref_store,\n+\t\t\tREF_STORE_READ,\n+\t\t\t\"is_packed_transaction_needed\");\n+\tstruct strbuf referent = STRBUF_INIT;\n+\tsize_t i;\n+\tint ret;\n+\n+\tif (!is_lock_file_locked(&refs->lock))\n+\t\tBUG(\"is_packed_transaction_needed() called while unlocked\");\n+\n+\t/*\n+\t * We're only going to bother returning false for the common,\n+\t * trivial case that references are only being deleted, their\n+\t * old values are not being checked, and the old `packed-refs`\n+\t * file doesn't contain any of those reference(s). This gives\n+\t * false positives for some other cases that could\n+\t * theoretically be optimized away:\n+\t *\n+\t * 1. It could be that the old value is being verified without\n+\t *    setting a new value. In this case, we could verify the\n+\t *    old value here and skip the update if it agrees. If it\n+\t *    disagrees, we could either let the update go through\n+\t *    (the actual commit would re-detect and report the\n+\t *    problem), or come up with a way of reporting such an\n+\t *    error to *our* caller.\n+\t *\n+\t * 2. It could be that a new value is being set, but that it\n+\t *    is identical to the current packed value of the\n+\t *    reference.\n+\t *\n+\t * Neither of these cases will come up in the current code,\n+\t * because the only caller of this function passes to it a\n+\t * transaction that only includes `delete` updates with no\n+\t * `old_id`. Even if that ever changes, false positives only\n+\t * cause an optimization to be missed; they do not affect\n+\t * correctness.\n+\t */\n+\n+\t/*\n+\t * Start with the cheap checks that don't require old\n+\t * reference values to be read:\n+\t */\n+\tfor (i = 0; i < transaction->nr; i++) {\n+\t\tstruct ref_update *update = transaction->updates[i];\n+\n+\t\tif (update->flags & REF_HAVE_OLD)\n+\t\t\t/* Have to check the old value -> needed. */\n+\t\t\treturn 1;\n+\n+\t\tif ((update->flags & REF_HAVE_NEW) && !is_null_oid(&update->new_oid))\n+\t\t\t/* Have to set a new value -> needed. */\n+\t\t\treturn 1;\n+\t}\n+\n+\t/*\n+\t * The transaction isn't checking any old values nor is it\n+\t * setting any nonzero new values, so it still might be able\n+\t * to be skipped. Now do the more expensive check: the update\n+\t * is needed if any of the updates is a delete, and the old\n+\t * `packed-refs` file contains a value for that reference.\n+\t */\n+\tret = 0;\n+\tfor (i = 0; i < transaction->nr; i++) {\n+\t\tstruct ref_update *update = transaction->updates[i];\n+\t\tunsigned int type;\n+\t\tstruct object_id oid;\n+\n+\t\tif (!(update->flags & REF_HAVE_NEW))\n+\t\t\t/*\n+\t\t\t * This reference isn't being deleted -> not\n+\t\t\t * needed.\n+\t\t\t */\n+\t\t\tcontinue;\n+\n+\t\tif (!refs_read_raw_ref(ref_store, update->refname,\n+\t\t\t\t       oid.hash, &referent, &type) ||\n+\t\t    errno != ENOENT) {\n+\t\t\t/*\n+\t\t\t * We have to actually delete that reference\n+\t\t\t * -> this transaction is needed.\n+\t\t\t */\n+\t\t\tret = 1;\n+\t\t\tbreak;\n+\t\t}\n+\t}\n+\n+\tstrbuf_release(&referent);\n+\treturn ret;\n+}\n+\n struct packed_transaction_backend_data {\n \t/* True iff the transaction owns the packed-refs lock. */\n \tint own_lock;\ndiff --git a/refs/packed-backend.h b/refs/packed-backend.h\nindex 61687e408a..640245d3b9 100644\n--- a/refs/packed-backend.h\n+++ b/refs/packed-backend.h\n@@ -23,4 +23,13 @@ int packed_refs_lock(struct ref_store *ref_store, int flags, struct strbuf *err)\n void packed_refs_unlock(struct ref_store *ref_store);\n int packed_refs_is_locked(struct ref_store *ref_store);\n \n+/*\n+ * Return true if `transaction` really needs to be carried out against\n+ * the specified packed_ref_store, or false if it can be skipped\n+ * (i.e., because it is an obvious NOOP). `ref_store` must be locked\n+ * before calling this function.\n+ */\n+int is_packed_transaction_needed(struct ref_store *ref_store,\n+\t\t\t\t struct ref_transaction *transaction);\n+\n #endif /* REFS_PACKED_BACKEND_H */\ndiff --git a/t/t1409-avoid-packing-refs.sh b/t/t1409-avoid-packing-refs.sh\nindex a2397c7b71..e5cb8a252d 100755\n--- a/t/t1409-avoid-packing-refs.sh\n+++ b/t/t1409-avoid-packing-refs.sh\n@@ -26,7 +26,7 @@ test_expect_success 'setup' '\n \tC=$(git rev-parse HEAD)\n '\n \n-test_expect_failure 'do not create packed-refs file gratuitously' '\n+test_expect_success 'do not create packed-refs file gratuitously' '\n \ttest_must_fail test -f .git/packed-refs &&\n \tgit update-ref refs/heads/foo $A &&\n \ttest_must_fail test -f .git/packed-refs &&\n@@ -107,7 +107,7 @@ test_expect_success 'leave packed-refs untouched on verify of loose' '\n \tcheck_packed_refs_marked\n '\n \n-test_expect_failure 'leave packed-refs untouched on delete of loose' '\n+test_expect_success 'leave packed-refs untouched on delete of loose' '\n \tgit pack-refs --all &&\n \tgit update-ref refs/heads/loose-delete $A &&\n \tmark_packed_refs &&\n-- \n2.14.1\n\n"},{"id":"331327","messageId":"xmqqzi895jab.fsf@gitster.mtv.corp.google.com","threadId":"47051","inReplyTo":"6004e1dea6af33cb41c523855757aa6b04b912bc.1509181545.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 2/2] files-backend: don't rewrite the `packed-refs` file unnecessarily","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2017-10-30T04:52:44Z","receivedAt":"2017-10-30T04:52:51Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Michael Haggerty <mhagger@alum.mit.edu> writes:\n\n> +int is_packed_transaction_needed(struct ref_store *ref_store,\n> +\t\t\t\t struct ref_transaction *transaction)\n> +{\n> +\tstruct packed_ref_store *refs = packed_downcast(\n> +\t\t\tref_store,\n> +\t\t\tREF_STORE_READ,\n> +\t\t\t\"is_packed_transaction_needed\");\n> +\tstruct strbuf referent = STRBUF_INIT;\n> +\tsize_t i;\n> +\tint ret;\n> +\n> +\tif (!is_lock_file_locked(&refs->lock))\n> +\t\tBUG(\"is_packed_transaction_needed() called while unlocked\");\n> +\n> +\t/*\n> +\t * We're only going to bother returning false for the common,\n> +\t * trivial case that references are only being deleted, their\n> +\t * old values are not being checked, and the old `packed-refs`\n> +\t * file doesn't contain any of those reference(s). This gives\n> +\t * false positives for some other cases that could\n> +\t * theoretically be optimized away:\n\nThe way I understand \"the old file does not contain these\nreferences\" part of the condition is \"if there were any of these\nrefs, removing them from the loose ref storage may expose them,\nwhich necessitates us to remove them from the packed-refs (and if\nthere is no loose ref for them, we do noeed to remove them from the\npacked-refs)---so that definitely is not a no-op\".\n\nI was confused by the \"is_noop?\" version, especially about \"do we\ncheck the old value?\" condition.  The above does not help me all\nthat much to reach the same level of understanding as I have for the\nother condition; sorry.\n\nIs the reason why we know we want to play safe when the caller wants\nto check the old value because that could cause the transaction to\nabort if it does not match?\n\nThanks.\n"},{"id":"331550","messageId":"20171101073414.rwi426whpinv226l@sigill.intra.peff.net","threadId":"47051","inReplyTo":"cover.1509181545.git.mhagger@alum.mit.edu","subject":"Re: [PATCH v2 0/2] Avoid rewriting \"packed-refs\" unnecessarily","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2017-11-01T07:34:14Z","receivedAt":"2017-11-01T07:38:07Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sat, Oct 28, 2017 at 11:16:00AM +0200, Michael Haggerty wrote:\n\n> This reroll make some logically small changes to v1 [1] that are\n> textually very big:\n> \n> * Invert the sense of `is_packed_transaction_noop()` and rename it to\n>   `is_packed_transaction_needed()`. This makes the logic easier to\n>   follow and document.\n> \n> * Add a big comment to that function, describing the cases when it\n>   returns false positives and explaining why that isn't a problem.\n> \n> * In the commit message for patch 02, gives a lot more information\n>   about the regression that it is fixing. Thanks to Eric for the\n>   suggestion.\n> \n> These patches are also available as branch\n> `avoid-rewriting-packed-refs` on my GitHub fork [2]. They now use\n> `mh/packed-ref-transactions` as the base, since that is where Junio\n> chose to apply v1.\n\nThis all makes sense to me. I agree that the \"is_needed\" logic-flip in\nv2 makes it a little easier to think about.\n\nLike Junio, I was thrown off at first by the HAVE_OLD check. Especially\nsince we would not ever set that flag for the transaction we care about\nhere.  But I think the crux of it is that the packed_ref store code\ncould in theory operate independently of the loose ref code, where we\nfeed it more exotic inputs. And what you've written here is\nfuture-proofing against the more general case, even though it would not\nbe strictly necessary.\n\n-Peff\n"}]}