MSan failures in pack-bitmap

MSan failures in pack-bitmap

[Kyle Lippincott]

While running t/t5326-multi-pack-bitmaps:

test 24:
expecting success of 5326.24 'clone from bitmapped repository':
rm -fr clone.git &&
git clone --no-local --bare . clone.git &&
git rev-parse HEAD >expect &&
git --git-dir=clone.git rev-parse HEAD >actual &&
test_cmp expect actual

Cloning into bare repository 'clone.git'...
remote: ==7474==WARNING: MemorySanitizer: use-of-uninitialized-value
remote: #0 0x55c5cd191dde in try_partial_reuse pack-bitmap.c:1887:8
remote: #1 0x55c5cd191dde in reuse_partial_packfile_from_bitmap_1
pack-bitmap.c:2001:8
remote: #2 0x55c5cd191dde in reuse_partial_packfile_from_bitmap
pack-bitmap.c:2105:3
remote: #3 0x55c5cce0bd0e in get_object_list_from_bitmap
builtin/pack-objects.c:4043:3
remote: #4 0x55c5cce0bd0e in get_object_list builtin/pack-objects.c:4156:27
remote: #5 0x55c5cce0bd0e in cmd_pack_objects builtin/pack-objects.c:4596:3
remote: #6 0x55c5ccc8fac8 in run_builtin git.c:474:11
remote: #7 0x55c5ccc8d660 in handle_builtin git.c:729:3
remote: #8 0x55c5ccc8b634 in run_argv git.c:793:4
remote: #9 0x55c5ccc8b634 in cmd_main git.c:928:19
remote: #10 0x55c5ccf10a5b in main common-main.c:62:11
remote: #11 0x7f9ef142e3d3 in __libc_start_main
remote: #12 0x55c5ccbf28e9 in _start
remote:
remote: Uninitialized value was stored to memory at
remote: #0 0x55c5cd191dd7 in try_partial_reuse pack-bitmap.c:1888:15
remote: #1 0x55c5cd191dd7 in reuse_partial_packfile_from_bitmap_1
pack-bitmap.c:2001:8
remote: #2 0x55c5cd191dd7 in reuse_partial_packfile_from_bitmap
pack-bitmap.c:2105:3
remote: #3 0x55c5cce0bd0e in get_object_list_from_bitmap
builtin/pack-objects.c:4043:3
remote: #4 0x55c5cce0bd0e in get_object_list builtin/pack-objects.c:4156:27
remote: #5 0x55c5cce0bd0e in cmd_pack_objects builtin/pack-objects.c:4596:3
remote: #6 0x55c5ccc8fac8 in run_builtin git.c:474:11
remote: #7 0x55c5ccc8d660 in handle_builtin git.c:729:3
remote: #8 0x55c5ccc8b634 in run_argv git.c:793:4
remote: #9 0x55c5ccc8b634 in cmd_main git.c:928:19
remote: #10 0x55c5ccf10a5b in main common-main.c:62:11
remote: #11 0x7f9ef142e3d3 in __libc_start_main
remote: #12 0x55c5ccbf28e9 in _start
remote:
remote: Uninitialized value was created by a heap allocation
remote: #0 0x55c5ccc052ca in realloc msan/msan_interceptors.cpp:1009:3
remote: #1 0x55c5cd3d04d6 in xrealloc wrapper.c:137:8
remote: #2 0x55c5cd190d95 in reuse_partial_packfile_from_bitmap
pack-bitmap.c:2091:3
remote: #3 0x55c5cce0bd0e in get_object_list_from_bitmap
builtin/pack-objects.c:4043:3
remote: #4 0x55c5cce0bd0e in get_object_list builtin/pack-objects.c:4156:27
remote: #5 0x55c5cce0bd0e in cmd_pack_objects builtin/pack-objects.c:4596:3
remote: #6 0x55c5ccc8fac8 in run_builtin git.c:474:11
remote: #7 0x55c5ccc8d660 in handle_builtin git.c:729:3
remote: #8 0x55c5ccc8b634 in run_argv git.c:793:4
remote: #9 0x55c5ccc8b634 in cmd_main git.c:928:19
remote: #10 0x55c5ccf10a5b in main common-main.c:62:11
remote: #11 0x7f9ef142e3d3 in __libc_start_main
remote: #12 0x55c5ccbf28e9 in _start
remote:
remote: SUMMARY: MemorySanitizer: use-of-uninitialized-value
pack-bitmap.c:1887:8 in try_partial_reuse
remote: Exiting
error: git upload-pack: git-pack-objects died with error.
fatal: git upload-pack: aborting due to possible repository corruption
on the remote side.
remote: aborting due to possible repository corruption on the remote side.
fatal: early EOF
fatal: fetch-pack: invalid index-pack output
not ok 24 - clone from bitmapped repository
#
# rm -fr clone.git &&
# git clone --no-local --bare . clone.git &&
# git rev-parse HEAD >expect &&
# git --git-dir=clone.git rev-parse HEAD >actual &&
# test_cmp expect actual
#

There are similar failures in test 25, 198, 199, 319, and 320.
---

I believe what's happening is that pack-bitmap.c:2091 grows the packs
list and sets up some of the fields, but doesn't set pack_int_id. We
then use it at pack-bitmap.c:1888.

I investigated, but couldn't prove to myself what value should be
placed there while growing it, or if it's incorrect to read from it in
this case (so we shouldn't be in pack-bitmap.c:1888 with this pack).

Reproducing is potentially non-trivial. This may work:

make -j CFLAGS="-fsanitize=memory -fsanitize-memory-track-origins
-fno-omit-frame-pointer -g -O2" CC=clang && \
make -C t t5326-multi-pack-bitmaps.sh GIT_TEST_OPTS="--verbose --debug"

Re: MSan failures in pack-bitmap

[Jeff King]

On Fri, Jun 07, 2024 at 07:43:56PM -0700, Kyle Lippincott wrote:

> I believe what's happening is that pack-bitmap.c:2091 grows the packs
> list and sets up some of the fields, but doesn't set pack_int_id. We
> then use it at pack-bitmap.c:1888.
> 
> I investigated, but couldn't prove to myself what value should be
> placed there while growing it, or if it's incorrect to read from it in
> this case (so we shouldn't be in pack-bitmap.c:1888 with this pack).

Hmm, I'm not sure.

In reuse_partial_packfile_from_bitmap(), the code path that creates the
struct only kicks in when the "multi_pack_reuse" flag isn't set. Which
generally would correspond to whether we have a midx. And then the code
in try_partial_reuse() that uses the struct similarly checks
bitmap_is_midx() before looking at the pack_int_id field.

But that changed in 795006fff4 (pack-bitmap: gracefully handle missing
BTMP chunks, 2024-04-15), where we also disable multi_pack_reuse if we
have a midx but it has no BTMP chunk. So we end up in the non-multi code
path to create the struct, but then try_partial_reuse() still realizes
we have a midx and uses that code path.

I guess this gets into the "we have a midx, but are only doing reuse out
of a single pack" case. Which I think is supported, but I'm not familiar
enough with the code to know where the assumption is going wrong.

Anyway...

> Reproducing is potentially non-trivial. This may work:
> 
> make -j CFLAGS="-fsanitize=memory -fsanitize-memory-track-origins
> -fno-omit-frame-pointer -g -O2" CC=clang && \
> make -C t t5326-multi-pack-bitmaps.sh GIT_TEST_OPTS="--verbose --debug"

Yeah, I forgot what a pain MSan is:

  - I needed to use a recent version of clang (the default for Debian
    unstable is clang-16, which is missing intercepts for newer versions
    of glibc strtoimax(), and complains that it does not set the
    outgoing "end" pointer). Using clang-19 fixed that.

  - Since I didn't recompile all of the dependent libraries with MSan
    support, I hit the usual zlib problems discussed long ago in:

     https://lore.kernel.org/git/20171004101932.pai6wzcv2eohsicr@sigill.intra.peff.net/

    and had to resurrect the patch there.

  - While bisecting (which is how I found 795006fff4), some versions
    complain that attr.c does:

      buf = read_blob_data_from_index(istate, path, &size);
      stack = read_attr_from_buf(buf, size, path, flags);

    If reading failed, then "buf" is NULL and size is uninitialized.
    Inside read_attr_from_buf() we bail immediately when we see the NULL
    buf, but MSan complains that we passed the uninitialized "size" at
    all. Newer versions (starting with c793f9cb08) move the NULL check
    into the caller.

An easier (but slower) reproduction is to just use valgrind. After doing
a normal build, running:

  ./t5326-multi-pack-bitmaps.sh --run=1-24 --valgrind-only=24 -i

is enough to see the problem.

-Peff

Re: MSan failures in pack-bitmap

[Taylor Blau]

On Sat, Jun 08, 2024 at 04:18:55AM -0400, Jeff King wrote:
> On Fri, Jun 07, 2024 at 07:43:56PM -0700, Kyle Lippincott wrote:
>
> > I believe what's happening is that pack-bitmap.c:2091 grows the packs
> > list and sets up some of the fields, but doesn't set pack_int_id. We
> > then use it at pack-bitmap.c:1888.
> >
> > I investigated, but couldn't prove to myself what value should be
> > placed there while growing it, or if it's incorrect to read from it in
> > this case (so we shouldn't be in pack-bitmap.c:1888 with this pack).
>
> Hmm, I'm not sure.
>
> In reuse_partial_packfile_from_bitmap(), the code path that creates the
> struct only kicks in when the "multi_pack_reuse" flag isn't set. Which
> generally would correspond to whether we have a midx. And then the code
> in try_partial_reuse() that uses the struct similarly checks
> bitmap_is_midx() before looking at the pack_int_id field.
>
> But that changed in 795006fff4 (pack-bitmap: gracefully handle missing
> BTMP chunks, 2024-04-15), where we also disable multi_pack_reuse if we
> have a midx but it has no BTMP chunk. So we end up in the non-multi code
> path to create the struct, but then try_partial_reuse() still realizes
> we have a midx and uses that code path.
>
> I guess this gets into the "we have a midx, but are only doing reuse out
> of a single pack" case. Which I think is supported, but I'm not familiar
> enough with the code to know where the assumption is going wrong.

That's right. We support single-pack reuse even with a MIDX either (a)
because it was configured that way with
pack.allowPackReuse=(true|single), or (b) because the MIDX has no BTMP
chunk, which is what prompted the change in 795006fff4.

When in that case, our reuse packfile is either the pack attached to a
single-pack bitmap, or the MIDX's preferred pack. When using the MIDX's
preferred pack, we need to make sure that we correctly assign the
pack_int_id to be the ID of the preferred pack. (We use this field to
reject cross-pack deltas later on in try_partial_reuse(), which is where
the MSan failure is happening).

The fix should be to set pack_int_id to the preferred pack's ID in the
MIDX case, and an arbitrary value in the single-pack bitmap case. I
posted a patch which should fix that here:

    https://lore.kernel.org/git/4aceb9233ed24fb1e1a324a77b665eea2cf22b39.1717946847.git.me@ttaylorr.com/T/#u

Unfortunately, the regression happened in 795006fff4, so this is in a
released version of Git. But this is all behind a configuration option,
so affected users can reasonably work around this issue.

Thanks,
Taylor

Re: MSan failures in pack-bitmap

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> Unfortunately, the regression happened in 795006fff4, so this is in a
> released version of Git. But this is all behind a configuration option,
> so affected users can reasonably work around this issue.

Can you elaborate a bit about "reasonably work around"?

I am imagining that you are saying that the user can say "do not use
bitmap, because it may be corrupted due to an earlier regression" in
some configuration, so that a corrupt bitmap data is not used to
further spread the damage, but how does a user find out that on-disc
midx is broken and a workaround needs to be employed in the first
place?  After working around the issue by avoiding to use the
corrupt on-disc data while waiting for a fixed version of Git to
come, what does the user need to do to start using the now-corrected
feature again?  Does the fixed code notice there is an existing
breakage caused by the regression and remove the broken file
automatically?

Thanks.

Re: MSan failures in pack-bitmap

[Taylor Blau]

On Sun, Jun 09, 2024 at 11:55:07AM -0700, Junio C Hamano wrote:
> Taylor Blau <me@ttaylorr.com> writes:
>
> > Unfortunately, the regression happened in 795006fff4, so this is in a
> > released version of Git. But this is all behind a configuration option,
> > so affected users can reasonably work around this issue.
>
> Can you elaborate a bit about "reasonably work around"?
>
> I am imagining that you are saying that the user can say "do not use
> bitmap, because it may be corrupted due to an earlier regression" in
> some configuration, so that a corrupt bitmap data is not used to
> further spread the damage, but how does a user find out that on-disc
> midx is broken and a workaround needs to be employed in the first
> place?

I don't think the issue here is a corrupt on-disk bitmap or MIDX. The
regression that Kyle reported was a logic issue reading a
ordinary/non-corrupt MIDX file, not a result of some on-disk corruption.

I think it is possible to generate a corrupt pack as a result of this
bug which would incorrectly "reuse" parts of an existing MIDX's
preferred pack, but the result would be far worse than a corrupt MIDX
(which, again, I don't think is what's happening here).

But I do not think that repository corruption is a likely outcome here,
since we only do pack reuse when packing to stdout (i.e. by passing the
`--stdout` option to `pack-objects`). So repacks (which would otherwise
be the thing I'm most worried about) are safe: repacks trigger
pack-objects to write a tempfile directly, and so `pack_to_stdout` is
zero'd, and we do not allow verbatim pack reuse to take place.

So a doomsday scenario whereby we'd write a corrupt pack based on this
bug and then delete a non-corrupt pack is not directly possible via
'repack' alone. The lesser-used 'git multi-pack-index repack' is also
not affected, since it similarly does not use `pack-objects --stdout`.

A more likely outcome would be if a Git client who was using MIDX
bitmaps, but only doing single-pack reuse tried to generate a pack to
push to some remote (or vice-versa, replacing client and server/remote)
which ended up being corrupt in some fashion. I haven't had enough of a
chance to determine if this possible, though I suspect it is.

Thanks,
Taylor

Re: MSan failures in pack-bitmap

[Junio C Hamano]

Taylor Blau <me@ttaylorr.com> writes:

> I don't think the issue here is a corrupt on-disk bitmap or MIDX. The
> regression that Kyle reported was a logic issue reading a
> ordinary/non-corrupt MIDX file, not a result of some on-disk corruption.
> ...
> But I do not think that repository corruption is a likely outcome here,

Yes, exactly.  What I was asking was how on-disk corruption that
would result from the logic issue of reading a correct MIDX file.

> A more likely outcome would be if a Git client who was using MIDX
> bitmaps, but only doing single-pack reuse tried to generate a pack
> to push to some remote (or vice-versa, replacing client and
> server/remote) which ended up being corrupt in some fashion. I
> haven't had enough of a chance to determine if this possible,
> though I suspect it is.

So, ...

>> > Unfortunately, the regression happened in 795006fff4, so this is in a
>> > released version of Git. But this is all behind a configuration option,
>> > so affected users can reasonably work around this issue.
>>
>> Can you elaborate a bit about "reasonably work around"?

... there is no reasonable work around here, is there?  We do not
even know exactly what kind of breakage this will cause (which is
expected, as we would be "reading" a garbage value and basing future
actions on it)?

Re: MSan failures in pack-bitmap

[Taylor Blau]

On Sun, Jun 09, 2024 at 04:00:57PM -0400, Taylor Blau wrote:
> A more likely outcome would be if a Git client who was using MIDX
> bitmaps, but only doing single-pack reuse tried to generate a pack to
> push to some remote (or vice-versa, replacing client and server/remote)
> which ended up being corrupt in some fashion. I haven't had enough of a
> chance to determine if this possible, though I suspect it is.

OK. I looked a little more, and I think that though this is possible in
theory, it is exceedingly rare to hit in practice.

The thing that we care about reading pack_int_id is for rejecting
cross-pack deltas in try_partial_reuse(). A cross-pack delta occurs, for
some delta/base pair when either half of the pair was selected from
different packs in the MIDX. When this is the case, we can't verbatim
reuse the delta object, since the base object may be selected from a
pack that was reused later in the MIDX, thus we'd have to convert to a
REF_DELTA on the fly.

(This is a bit of an aside, but it is technically possible to allow
cross-pack deltas if you are careful, I just didn't implement it thus
far, though I would like to do so in the future).

So when we try and do a partial reuse (i.e. on a single object instead
of saying, "these N words in the bitmap of objects that we want to pack
are all ones, so we can blindly reuse a chunk of objects from the
beginning of this pack) we check if the object we're reusing is either
an OFS_DELTA or a REF_DELTA. If it is, *and* we're reusing it from a
MIDX, we need to check that its base object was selected in the same
pack.

That's what we're doing when we call:

    midx_pair_to_pack_pos(bitmap_git->midx, pack->pack_int_id,
                          base_offset, &base_bitmap_pos);

If we can't find the base object in the same pack, we toss out the
cross-pack delta and kick it back to the regular pack generation logic.

So in order to hit this in a way that would produce a broken pack, you'd
have to have the uninitialized memory at pack->pack_int_id be set to the
same value as some MIDX'd pack's pack_int_id, *and* have that pack
happen to contain the same object as the base of some delta that you
would otherwise want to throw out.

If that were all to happen, then you would likely end up with a broken
pack. But I think in the vast majority of cases try_partial_reuse()
would read garbage out of pack->pack_int_id, and kick it back to the
regular pack generation logic, and produce a correct pack (albeit doing
so using a slightly slower path).

But this is all much too close for comfort for me. I think that this
points to a gap in our test coverage, and that we should ensure that
this case is covered.

(Note, I'm not sure exactly how to do this, since such a test would
depend on an uninitialized read. I'll think about this a bit more and
see if it is possible to write such a test.)

But in summary, though I think it is possible for either a client to
send a broken push to a server (if the client were using MIDX bitmaps
and only doing single-pack reuse) or for a server to send a broken pack
to a client (if the server was also using MIDX bitmaps in the same
fashion), I think that it is exceedingly rare to hit in practice. Which
is not the same as saying that it is impossible, of course, but I am
confident with the fix I posted in:

    https://lore.kernel.org/git/4aceb9233ed24fb1e1a324a77b665eea2cf22b39.1717946847.git.me@ttaylorr.com/T/#u

to fix the issue. Note also that I don't think a repository would be
able to actually corrupt itself using this bug, since we don't bother
taking this code path at all during repacks.

So in short, I think the fix I posted above should be tracked down to
'maint' at least for the 2.45.x series. It will avoid the MSan failures
and more importantly the issue I described above. I would also like to
find a way to further test this case so that we aren't bit by such a bug
in the future.

Thanks,
Taylor

Re: MSan failures in pack-bitmap

[Taylor Blau]

On Sun, Jun 09, 2024 at 01:23:48PM -0700, Junio C Hamano wrote:
> Taylor Blau <me@ttaylorr.com> writes:
>
> > I don't think the issue here is a corrupt on-disk bitmap or MIDX. The
> > regression that Kyle reported was a logic issue reading a
> > ordinary/non-corrupt MIDX file, not a result of some on-disk corruption.
> > ...
> > But I do not think that repository corruption is a likely outcome here,
>
> Yes, exactly.  What I was asking was how on-disk corruption that
> would result from the logic issue of reading a correct MIDX file.

OK, I think I misunderstood your original email.

> ... there is no reasonable work around here, is there?  We do not
> even know exactly what kind of breakage this will cause (which is
> expected, as we would be "reading" a garbage value and basing future
> actions on it)?

I think the end-result would be that packs sent between client and
server during fetches or pushes would be broken, resulting in index-pack
failing to index them, thus causing one side or the other to (correctly)
throw away the received pack.

The only thing I can think of to avoid this would be to enable
multi-pack reuse, which is only possible if your MIDX has a BTMP chunk.
The other work around would be to disable pack-reuse altogether, which
is very unfortunate.

Thanks,
Taylor

Re: MSan failures in pack-bitmap

[Jeff King]

On Sun, Jun 09, 2024 at 04:24:46PM -0400, Taylor Blau wrote:

> But in summary, though I think it is possible for either a client to
> send a broken push to a server (if the client were using MIDX bitmaps
> and only doing single-pack reuse) or for a server to send a broken pack
> to a client (if the server was also using MIDX bitmaps in the same
> fashion), I think that it is exceedingly rare to hit in practice. Which
> is not the same as saying that it is impossible, of course, but I am
> confident with the fix I posted in:
> 
>     https://lore.kernel.org/git/4aceb9233ed24fb1e1a324a77b665eea2cf22b39.1717946847.git.me@ttaylorr.com/T/#u
> 
> to fix the issue. Note also that I don't think a repository would be
> able to actually corrupt itself using this bug, since we don't bother
> taking this code path at all during repacks.

Right, I think this is mostly just a vanilla bug. It could cause bogus
packs on fetch, but the clients would realize it. If people aren't
screaming about broken fetches, then it is not happening very often (and
your analysis nicely explains why). But I don't see how it could ever
cause corruption.

Directing the fix to "maint" as you suggest is sensible, but I don't
think it merits any special treatment.

> So in short, I think the fix I posted above should be tracked down to
> 'maint' at least for the 2.45.x series. It will avoid the MSan failures
> and more importantly the issue I described above. I would also like to
> find a way to further test this case so that we aren't bit by such a bug
> in the future.

I don't think we can test the case where the bug would produce a bogus
pack, since that implies guessing the uninitialized data. I guess we
could come up with a case where try_partial_reuse() should say "this is
OK to reuse", but the bogus pack_int_id prevents it. Which implies
looking at the resulting pack and checking that some delta is there that
we expect?

-Peff

Re: MSan failures in pack-bitmap

[Jeff King]

On Tue, Jun 11, 2024 at 04:02:20AM -0400, Jeff King wrote:

> > So in short, I think the fix I posted above should be tracked down to
> > 'maint' at least for the 2.45.x series. It will avoid the MSan failures
> > and more importantly the issue I described above. I would also like to
> > find a way to further test this case so that we aren't bit by such a bug
> > in the future.
> 
> I don't think we can test the case where the bug would produce a bogus
> pack, since that implies guessing the uninitialized data. I guess we
> could come up with a case where try_partial_reuse() should say "this is
> OK to reuse", but the bogus pack_int_id prevents it. Which implies
> looking at the resulting pack and checking that some delta is there that
> we expect?

Ah, never mind. I see you worked up a test in the v2 patches you sent.

-Peff