Skip to contentSkip to conversation

pack-refs: fail on falsely sorted packed-refs

RFC PATCH Superseded Max Kirillov 5 participants 12 messages Jan 30, 2019 – Feb 23, 2019 1 message not in the archive

lore
Share & tools
lore
#0 lore raw

RFC PATCH 1/1 pack-refs: fail on falsely sorted packed-refs

If packed-refs is marked as sorted but not really sorted it causes very hard to comprehend misbehavior of reference resolving - a reference is reported as not found.

As the scope of the issue is not clear, make it visible by failing pack-refs command - the one which would not suffer performance penalty to verify the sortedness - when it encounters not really sorted existing data.

---
I happened to have a not really sorted packed-refs file. As you might guess, it was quite wtf-ing experience. It worked, mostly, but there was one branch which just did not resolve, regardless of existing and being presented in for-each-refs output.

I don't know where the corruption came from. I should admit it could even be a manual editing but last time I did it (in that reporitory) was several years ago so it is unlikely.

I am not sure what should be the proper fix. I did a minimal detection, so that it does not go unnoticed. Probably next step would be either fixing in git fsck call.

 refs/packed-backend.c               | 15 +++++++++++++++
 t/t3212-pack-refs-broken-sorting.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100755 t/t3212-pack-refs-broken-sorting.sh
refs/packed-backend.c +15 -0
index c01c7f5901..505f4535b5 100644
@@ -1088,6 +1088,7 @@ static int write_with_updates(struct packed_ref_store *refs,
 	FILE *out;
 	struct strbuf sb = STRBUF_INIT;
 	char *packed_refs_path;
+	struct strbuf prev_ref = STRBUF_INIT;
 
 	if (!is_lock_file_locked(&refs->lock))
 		BUG("write_with_updates() called while unlocked");
@@ -1137,6 +1138,20 @@ static int write_with_updates(struct packed_ref_store *refs,
 		struct ref_update *update = NULL;
 		int cmp;
 
+		if (iter)
+		{
+			if (prev_ref.len &&  strcmp(prev_ref.buf, iter->refname) > 0)
+			{
+				strbuf_addf(err, "broken sorting in packed-refs: '%s' > '%s'",
+					    prev_ref.buf,
+					    iter->refname);
+				goto error;
+			}
+
+			strbuf_init(&prev_ref, 0);
+			strbuf_addstr(&prev_ref, iter->refname);
+		}
+
 		if (i >= updates->nr) {
 			cmp = -1;
 		} else {
t/t3212-pack-refs-broken-sorting.sh new file +26 -0
new file mode 100755
index 0000000000..37a98a6fb1
@@ -0,0 +1,26 @@
+#!/bin/sh
+
+test_description='tests for the falsely sorted refs'
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m commit &&
+	for num in $(test_seq 10)
+	do
+		git branch b$(printf "%02d" $num) || break
+	done &&
+	git pack-refs --all &&
+	head_object=$(git rev-parse HEAD) &&
+	printf "$head_object refs/heads/b00\\n" >>.git/packed-refs &&
+	git branch b11
+'
+
+test_expect_success 'off-order branch not found' '
+	! git show-ref --verify --quiet refs/heads/b00
+'
+
+test_expect_success 'subsequent pack-refs fails' '
+	! git pack-refs --all
+'
+
+test_done
Signature · 1 line
2.19.0.1202.g68e1e8f04e
#1 lore raw
Quoted 15 lines · Max Kirillov

If packed-refs is marked as sorted but not really sorted it causes very hard to comprehend misbehavior of reference resolving - a reference is reported as not found.

As the scope of the issue is not clear, make it visible by failing pack-refs command - the one which would not suffer performance penalty to verify the sortedness - when it encounters not really sorted existing data.

---

refs/packed-backend.c +1 -0
@@ -1088,6 +1088,7 @@ static int write_with_updates(struct packed_ref_store *refs,
+       struct strbuf prev_ref = STRBUF_INIT;

refs/packed-backend.c static int write_with_updates(struct packed_ref_store *refs, · line 1144

Quoted 7 lines
refs/packed-backend.c +7 -0
@@ -1137,6 +1138,20 @@ static int write_with_updates(struct packed_ref_store *refs,
+               if (iter)
+               {
+                       if (prev_ref.len &&  strcmp(prev_ref.buf, iter->refname) > 0)
+                       {
+                               strbuf_addf(err, "broken sorting in packed-refs: '%s' > '%s'",
+                                           prev_ref.buf,
+                                           iter->refname);

strbuf_release(&prev_ref) either here or after the "error" label.

t/t3212-pack-refs-broken-sorting.sh line 5

Quoted 13 lines
refs/packed-backend.c +6 -0
+                               goto error;
+                       }
+
+                       strbuf_init(&prev_ref, 0);
+                       strbuf_addstr(&prev_ref, iter->refname);
+               }
t/t3212-pack-refs-broken-sorting.sh +5 -0
@@ -0,0 +1,26 @@
+test_expect_success 'setup' '
+       git commit --allow-empty -m commit &&
+       for num in $(test_seq 10)
+       do
+               git branch b$(printf "%02d" $num) || break

This should probably be "|| return 1" rather than "|| break" in order to fail the test immediately.

t/t3212-pack-refs-broken-sorting.sh line 20

Quoted 10 lines
t/t3212-pack-refs-broken-sorting.sh +10 -0
+       done &&
+       git pack-refs --all &&
+       head_object=$(git rev-parse HEAD) &&
+       printf "$head_object refs/heads/b00\\n" >>.git/packed-refs &&
+       git branch b11
+'
+
+test_expect_success 'off-order branch not found' '
+       ! git show-ref --verify --quiet refs/heads/b00
+'

Use test_must_fail() rather than '!' when expecting a Git command to fail.

t/t3212-pack-refs-broken-sorting.sh line 24

Quoted 3 lines
t/t3212-pack-refs-broken-sorting.sh +3 -0
+test_expect_success 'subsequent pack-refs fails' '
+       ! git pack-refs --all
+'

Ditto.

#2 lore raw
Quoted 6 lines · Eric Sunshine

refs/packed-backend.c static int write_with_updates(struct packed_ref_store *refs, · line 1147

Quoted 3 lines · Max Kirillov
refs/packed-backend.c +3 -0
+                               strbuf_addf(err, "broken sorting in packed-refs: '%s' > '%s'",
+                                           prev_ref.buf,
+                                           iter->refname);

strbuf_release(&prev_ref) either here or after the "error" label.

Thanks! I seem to forget about it.

Quoted 4 lines
Quoted 1 line

+ git branch b$(printf "%02d" $num) || break

This should probably be "|| return 1" rather than "|| break" in order to fail the test immediately.

I've been looking for the correct way, and have seen the break somewhere. Now I see the "return 1" is mostly user. Thanks, will fix.

Quoted 1 line

Use test_must_fail() rather than '!' when expecting a Git command to fail.

Will fix in both places

#3 lore raw

PATCH v2 1/1 pack-refs: fail on falsely sorted packed-refs

In reply to Eric Sunshine

If packed-refs is marked as sorted but not really sorted it causes very hard to comprehend misbehavior of reference resolving - a reference is reported as not found, though it is listed by commands which output the references list.

As the scope of the issue is not clear, make it visible by failing pack-refs command - the one which would not suffer performance penalty to verify the sortedness - when it encounters not really sorted existing data.

---
Fixed the notes

 refs/packed-backend.c               | 18 ++++++++++++++++++
 t/t3212-pack-refs-broken-sorting.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 44 insertions(+)
 create mode 100755 t/t3212-pack-refs-broken-sorting.sh
refs/packed-backend.c +18 -0
index c01c7f5901..c89a5eb899 100644
@@ -1088,6 +1088,7 @@ static int write_with_updates(struct packed_ref_store *refs,
 	FILE *out;
 	struct strbuf sb = STRBUF_INIT;
 	char *packed_refs_path;
+	struct strbuf prev_ref = STRBUF_INIT;
 
 	if (!is_lock_file_locked(&refs->lock))
 		BUG("write_with_updates() called while unlocked");
@@ -1137,6 +1138,21 @@ static int write_with_updates(struct packed_ref_store *refs,
 		struct ref_update *update = NULL;
 		int cmp;
 
+		if (iter)
+		{
+			if (prev_ref.len &&  strcmp(prev_ref.buf, iter->refname) > 0)
+			{
+				strbuf_addf(err, "broken sorting in packed-refs: '%s' > '%s'",
+					    prev_ref.buf,
+					    iter->refname);
+				strbuf_release(&prev_ref);
+				goto error;
+			}
+
+			strbuf_init(&prev_ref, 0);
+			strbuf_addstr(&prev_ref, iter->refname);
+		}
+
 		if (i >= updates->nr) {
 			cmp = -1;
 		} else {
@@ -1240,6 +1256,8 @@ static int write_with_updates(struct packed_ref_store *refs,
 		}
 	}
 
+	strbuf_release(&prev_ref);
+
 	if (ok != ITER_DONE) {
 		strbuf_addstr(err, "unable to write packed-refs file: "
 			      "error iterating over old contents");
t/t3212-pack-refs-broken-sorting.sh new file +26 -0
new file mode 100755
index 0000000000..a44785c8fc
@@ -0,0 +1,26 @@
+#!/bin/sh
+
+test_description='tests for the falsely sorted refs'
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m commit &&
+	for num in $(test_seq 10)
+	do
+		git branch b$(printf "%02d" $num) || return 1
+	done &&
+	git pack-refs --all &&
+	head_object=$(git rev-parse HEAD) &&
+	printf "$head_object refs/heads/b00\\n" >>.git/packed-refs &&
+	git branch b11
+'
+
+test_expect_success 'off-order branch not found' '
+	test_must_fail git show-ref --verify --quiet refs/heads/b00
+'
+
+test_expect_success 'subsequent pack-refs fails' '
+	test_must_fail git pack-refs --all
+'
+
+test_done
Signature · 1 line
2.19.0.1202.g68e1e8f04e
#4 lore raw
Quoted 16 lines · Max Kirillov

If packed-refs is marked as sorted but not really sorted it causes very hard to comprehend misbehavior of reference resolving - a reference is reported as not found, though it is listed by commands which output the references list.

As the scope of the issue is not clear, make it visible by failing pack-refs command - the one which would not suffer performance penalty to verify the sortedness - when it encounters not really sorted existing data.

---

refs/packed-backend.c +2 -0
@@ -1137,6 +1138,21 @@ static int write_with_updates(struct packed_ref_store *refs,
+               if (iter)
+               {

refs/packed-backend.c static int write_with_updates(struct packed_ref_store *refs, · line 1149

Quoted 10 lines
refs/packed-backend.c +10 -0
+                       if (prev_ref.len &&  strcmp(prev_ref.buf, iter->refname) > 0)
+                       {
+                               [...]
+                               strbuf_release(&prev_ref);
+                               goto error;
+                       }
+
+                       strbuf_init(&prev_ref, 0);
+                       strbuf_addstr(&prev_ref, iter->refname);
+               }

The call to strbuf_init() is leaking the allocated strbuf buffer each time through the loop. The typical way to re-use a strbuf, and the way you should do it here, is strbuf_reset().

#5 lore raw
Quoted 3 lines · Eric Sunshine

The call to strbuf_init() is leaking the allocated strbuf buffer each time through the loop. The typical way to re-use a strbuf, and the way you should do it here, is strbuf_reset().

Thank you! Will fix it

A message that is not in the archive (sent off-list or not yet received): CAMy9T_EX_L80-V4zD626nFCxw6qa90+pZwcbd6wHw9ZHcj2rNA@mail.gmail.com

#7 lore raw
Quoted 4 lines · Michael Haggerty

The change to write_with_updates() doesn't only affect pack-refs. That function is also called when the packed-refs file has to be rewritten when a packed reference is deleted. This is another thing that you could test.

Ok, I'll check ti and add to the tests.

Quoted 7 lines

But that also means that fairly common commands like git branch -d could be slowed down by this change. I doubt that the slowdown is prohibitive, but it would be great to see numbers to prove it. For example, create a repository with a lot (say 10000) references, pack them, then run git branch -d to delete one of them. Benchmark that once with master and once with your modification and document the difference.

At my hardware, with 1M references, "branch -d" takes 0.31s of user time before change vs 0.38 after change. Should I mention it in the commit message?

Quoted 8 lines

t/t3212-pack-refs-broken-sorting.sh line 20

Quoted 3 lines
t/t3212-pack-refs-broken-sorting.sh new file +3 -0
+test_expect_success 'off-order branch not found' '
+       test_must_fail git show-ref --verify --quiet refs/heads/b00
+'

I don't think that the above test makes sense. We don't *guarantee* that an out-of-order reference won't be found. That is an implementation detail that we are free to change. I think that it would be OK to just omit this test.

Thanks, will remove this one

#8 lore raw
In reply to Max Kirillov
Quoted 19 lines · Max Kirillov

If packed-refs is marked as sorted but not really sorted it causes very hard to comprehend misbehavior of reference resolving - a reference is reported as not found.

As the scope of the issue is not clear, make it visible by failing pack-refs command - the one which would not suffer performance penalty to verify the sortedness - when it encounters not really sorted existing data.

---
I happened to have a not really sorted packed-refs file. As you might guess, it was quite wtf-ing experience. It worked, mostly, but there was one branch which just did not resolve, regardless of existing and being presented in for-each-refs output.

I don't know where the corruption came from. I should admit it could even be a manual editing but last time I did it (in that reporitory) was several years ago so it is unlikely.

Quoted 7 lines

I am not sure what should be the proper fix. I did a minimal detection, so that it does not go unnoticed. Probably next step would be either fixing in git fsck call.

 refs/packed-backend.c               | 15 +++++++++++++++
 t/t3212-pack-refs-broken-sorting.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100755 t/t3212-pack-refs-broken-sorting.sh

This is not an area I'm very familiar with. So mostly commeting on cosmetic issues with the patch. FWIW the "years back" issue you had could be that an issue didn't manifest until now, i.e. in a sorted file format you can get lucky and not see corruption for a while with a random insert.

Quoted 13 lines
refs/packed-backend.c +1 -0
index c01c7f5901..505f4535b5 100644
@@ -1088,6 +1088,7 @@ static int write_with_updates(struct packed_ref_store *refs,
 	FILE *out;
 	struct strbuf sb = STRBUF_INIT;
 	char *packed_refs_path;
+	struct strbuf prev_ref = STRBUF_INIT;
 
 	if (!is_lock_file_locked(&refs->lock))
 		BUG("write_with_updates() called while unlocked");

refs/packed-backend.c static int write_with_updates(struct packed_ref_store *refs, · line 1143

Quoted 6 lines
refs/packed-backend.c +3 -0
@@ -1137,6 +1138,20 @@ static int write_with_updates(struct packed_ref_store *refs,
 		struct ref_update *update = NULL;
 		int cmp;
 
+		if (iter)
+		{
+			if (prev_ref.len &&  strcmp(prev_ref.buf, iter->refname) > 0)

You have an extra two whitespaces after "&&" there.

Quoted 20 lines
refs/packed-backend.c +11 -0
+			{
+				strbuf_addf(err, "broken sorting in packed-refs: '%s' > '%s'",
+					    prev_ref.buf,
+					    iter->refname);
+				goto error;
+			}
+
+			strbuf_init(&prev_ref, 0);
+			strbuf_addstr(&prev_ref, iter->refname);
+		}
+
 		if (i >= updates->nr) {
 			cmp = -1;
 		} else {
t/t3212-pack-refs-broken-sorting.sh new file +0 -0
new file mode 100755
index 0000000000..37a98a6fb1

t/t3212-pack-refs-broken-sorting.sh line 7

Quoted 7 lines
t/t3212-pack-refs-broken-sorting.sh new file +7 -0
@@ -0,0 +1,26 @@
+#!/bin/sh
+
+test_description='tests for the falsely sorted refs'
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m commit &&

Looks like just "test_commit A" would do here.

t/t3212-pack-refs-broken-sorting.sh line 11

Quoted 4 lines
t/t3212-pack-refs-broken-sorting.sh new file +4 -0
+	for num in $(test_seq 10)
+	do
+		git branch b$(printf "%02d" $num) || break
+	done &&

We can fail in these sorts of loops. There's a few ways to deal with that. Doing it like this with "break" will still silently hide errors:

    $ for i in $(seq 1 3); do if test $i = 2; then false || break; else echo $i; fi; done && echo success
    1
    success

One way to deal with that is to e.g. before the loop say "had_fail=", then set "had_fail=t" in that "||" case, and test for it after the loop.

But perhaps in this case we're better off e.g. running for-each-ref after and either using test_cmp or test_line_count to see that we created the refs successfully?

t/t3212-pack-refs-broken-sorting.sh line 14

Quoted 3 lines
t/t3212-pack-refs-broken-sorting.sh new file +3 -0
+	git pack-refs --all &&
+	head_object=$(git rev-parse HEAD) &&
+	printf "$head_object refs/heads/b00\\n" >>.git/packed-refs &&

Looks like just "echo" here would be simpler since we only use printf to add a newline.

t/t3212-pack-refs-broken-sorting.sh line 24

Quoted 10 lines
t/t3212-pack-refs-broken-sorting.sh new file +10 -0
+	git branch b11
+'
+
+test_expect_success 'off-order branch not found' '
+	! git show-ref --verify --quiet refs/heads/b00
+'
+
+test_expect_success 'subsequent pack-refs fails' '
+	! git pack-refs --all
+'

Instead of "! git ..." use "test_must_fail git ...". See t/README. This will hide e.g. segfaults.

Also, perhaps:

test_must_fail git ... 2>stderr &&
grep "broken sorting in packed-refs" stderr

Would make this more obvious/self-documenting so we know we failed due to that issue in particular.

#9 lore raw
Quoted 10 lines · Ævar Arnfjörð Bjarmason
Quoted 4 lines · Max Kirillov
 refs/packed-backend.c               | 15 +++++++++++++++
 t/t3212-pack-refs-broken-sorting.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100755 t/t3212-pack-refs-broken-sorting.sh

This is not an area I'm very familiar with. So mostly commeting on cosmetic issues with the patch.

Just two quick comments in addition to Ævar's:

Quoted 6 lines

refs/packed-backend.c static int write_with_updates(struct packed_ref_store *refs, · line 1142

Quoted 6 lines
refs/packed-backend.c +2 -0
@@ -1137,6 +1138,20 @@ static int write_with_updates(struct packed_ref_store *refs,
 		struct ref_update *update = NULL;
 		int cmp;
 
+		if (iter)
+		{

According to our CodingGuidelines, the opening bracket should go on the same line as the condition, i.e.

  if (iter) {
Quoted 24 lines

t/t3212-pack-refs-broken-sorting.sh line 7

Quoted 13 lines
t/t3212-pack-refs-broken-sorting.sh new file +7 -0
new file mode 100755
index 0000000000..37a98a6fb1
@@ -0,0 +1,26 @@
+#!/bin/sh
+
+test_description='tests for the falsely sorted refs'
+. ./test-lib.sh
+
+test_expect_success 'setup' '
+	git commit --allow-empty -m commit &&

Looks like just "test_commit A" would do here.

t/t3212-pack-refs-broken-sorting.sh line 11

Quoted 4 lines
t/t3212-pack-refs-broken-sorting.sh new file +4 -0
+	for num in $(test_seq 10)
+	do
+		git branch b$(printf "%02d" $num) || break
+	done &&

We can fail in these sorts of loops. There's a few ways to deal with that. Doing it like this with "break" will still silently hide errors:

Quoted 6 lines
    $ for i in $(seq 1 3); do if test $i = 2; then false || break; else echo $i; fi; done && echo success
    1
    success

One way to deal with that is to e.g. before the loop say "had_fail=", then set "had_fail=t" in that "||" case, and test for it after the loop.

No, you can simply do 'cmd1 && cmd2 || return 1' in the body of the for loop; that's why we have a separate test_eval_inner() helper function in test-lib.

#10 lore raw
Quoted 7 lines · SZEDER Gábor
Quoted 2 lines

Review

Quoted 2 lines
(quoted diff) +2 -0
+		if (iter)
+		{

According to our CodingGuidelines, the opening bracket should go on the same line as the condition, i.e.

  if (iter) {

Oh, thanks. I must have been professionally deformed.

#11 lore raw
In reply to Ævar Arnfjörð Bjarmason
Quoted 16 lines · Ævar Arnfjörð Bjarmason
Quoted 8 lines

I happened to have a not really sorted packed-refs file. As you might guess, it was quite wtf-ing experience. It worked, mostly, but there was one branch which just did not resolve, regardless of existing and being presented in for-each-refs output.

I don't know where the corruption came from. I should admit it could even be a manual editing but last time I did it (in that reporitory) was several years ago so it is unlikely.

Quoted 7 lines

I am not sure what should be the proper fix. I did a minimal detection, so that it does not go unnoticed. Probably next step would be either fixing in git fsck call.

 refs/packed-backend.c               | 15 +++++++++++++++
 t/t3212-pack-refs-broken-sorting.sh | 26 ++++++++++++++++++++++++++
 2 files changed, 41 insertions(+)
 create mode 100755 t/t3212-pack-refs-broken-sorting.sh
Quoted 5 lines

This is not an area I'm very familiar with. So mostly commeting on cosmetic issues with the patch. FWIW the "years back" issue you had could be that an issue didn't manifest until now, i.e. in a sorted file format you can get lucky and not see corruption for a while with a random insert.

It actually shouldn't be that old a breakage. Until 02b920f3f7 (read_packed_refs(): ensure that references are ordered when read, 2017-09-25), we did not assume the file was sorted (even though we always wrote it out sorted). And we continue to not assume the file is sorted unless it is written out with an explicit "sorted" trait in the header (which we started doing in that commit, too).

So a years-old manual edit would not have the "sorted" trait, and should not have manifested as a problem, even now. Likewise for a years-old bug. It would have to be a bug in a _new_ writer which writes out the sorted trait. If there is such a bug in our implementation, this would be the first report we've seen. Given the number of times pack-refs has been run, without further evidence I'm inclined to think it was some weird manual edit, or maybe an alternate implementation (though one would _hope_ they would not write out the sorted trait without actually sorting!).

I agree with all of the cosmetic issues you mentioned. As far as what the patch itself does, I think it's OK. We could probably go further and actually sort it (or even just write it out without a "sorted" trait, which means the next read would load it all into memory and sort it). That's a little friendlier, since just dying leaves the user to fix it up themselves. But given that we expect this code to trigger approximately never, it's probably not worth spending much time on a fancy solution.

-Peff

#12 lore raw
In reply to Ævar Arnfjörð Bjarmason
Quoted 1 line · Ævar Arnfjörð Bjarmason

You have an extra two whitespaces after "&&" there.

Thanks, will check it.

Quoted 2 lines

t/t3212-pack-refs-broken-sorting.sh line 7

Quoted 1 line
t/t3212-pack-refs-broken-sorting.sh new file +1 -0
+	git commit --allow-empty -m commit &&

Looks like just "test_commit A" would do here.

About this I'm not sure. AFAIK test_commit does lots of stuff, so can it be considered "just" compared to "commit --allow-empty" or the opposite? I could replace it with test_commit for uniformity reason though.

Quoted 2 lines

We can fail in these sorts of loops. There's a few ways to deal with that. Doing it like this with "break" will still silently hide errors:

Thanks, this was pointed point

Quoted 4 lines

t/t3212-pack-refs-broken-sorting.sh line 14

Quoted 1 line
t/t3212-pack-refs-broken-sorting.sh new file +1 -0
+	printf "$head_object refs/heads/b00\\n" >>.git/packed-refs &&

Looks like just "echo" here would be simpler since we only use printf to add a newline.

Could it happen so that "echo" adds '\r\n' at Windows? I could use echo.

Quoted 2 lines

Instead of "! git ..." use "test_must_fail git ...". See t/README. This will hide e.g. segfaults.

Thanks, this was pointed point

Quoted 7 lines

Also, perhaps:

test_must_fail git ... 2>stderr &&
grep "broken sorting in packed-refs" stderr

Would make this more obvious/self-documenting so we know we failed due to that issue in particular.

Thanks, will change it