RFC patchpack-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.
>
> Signed-off-by: Max Kirillov <max@max630.net>
> ---
> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> @@ -1088,6 +1088,7 @@ static int write_with_updates(struct packed_ref_store *refs,
> +       struct strbuf prev_ref = STRBUF_INIT;
> @@ -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);

> +                               goto error;
> +                       }
> +
> +                       strbuf_init(&prev_ref, 0);
> +                       strbuf_addstr(&prev_ref, iter->refname);
> +               }
> diff --git a/t/t3212-pack-refs-broken-sorting.sh b/t/t3212-pack-refs-broken-sorting.sh
> @@ -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

> +       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
> +'

> 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.
>
> Signed-off-by: Max Kirillov <max@max630.net>
> ---
> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> @@ -1137,6 +1138,21 @@ static int write_with_updates(struct packed_ref_store *refs,
> +               if (iter)
> +               {
> +                       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);
> +               }

> 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.
>
> Signed-off-by: Max Kirillov <max@max630.net>
> ---
> 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

> diff --git a/refs/packed-backend.c b/refs/packed-backend.c
> index c01c7f5901..505f4535b5 100644
> --- a/refs/packed-backend.c
> +++ b/refs/packed-backend.c
> @@ -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 {
> diff --git a/t/t3212-pack-refs-broken-sorting.sh b/t/t3212-pack-refs-broken-sorting.sh
> new file mode 100755
> index 0000000000..37a98a6fb1
> --- /dev/null
> +++ b/t/t3212-pack-refs-broken-sorting.sh
> @@ -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 &&

> +	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
> +'

> >  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. 

> > @@ -1137,6 +1138,20 @@ static int write_with_updates(struct packed_ref_store *refs,
> >  		struct ref_update *update = NULL;
> >  		int cmp;
> >
> > +		if (iter)
> > +		{

> > diff --git a/t/t3212-pack-refs-broken-sorting.sh b/t/t3212-pack-refs-broken-sorting.sh
> > new file mode 100755
> > index 0000000000..37a98a6fb1
> > --- /dev/null
> > +++ b/t/t3212-pack-refs-broken-sorting.sh
> > @@ -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.
> 
> > +	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.

>>> +		if (iter)
>>> +		{
> 
> According to our CodingGuidelines, the opening bracket should go on
> the same line as the condition, i.e.
> 
>   if (iter) {

> > 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
> 
> 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.

> 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.

> 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.

>> +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.