Unaligned accesses in sha1dc

Unaligned accesses in sha1dc

[Andreas Schwab]

The sh1dc implementation is making unaligned accesses, which will crash
on some architectures, others have to emulate them in software.

Breakpoint 4, sha1_compression_states (ihv=0x600ffffffffe7010, 
    m=<optimized out>, W=0x600ffffffffe70a8, states=0x600ffffffffe7328)
    at sha1dc/sha1.c:398
398             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 21, temp);
(gdb) n
403             SHA1COMPRESS_FULL_ROUND2_STEP(d, e, a, b, c, W, 22, temp);
(gdb) 
408             SHA1COMPRESS_FULL_ROUND2_STEP(c, d, e, a, b, W, 23, temp);
(gdb) 
413             SHA1COMPRESS_FULL_ROUND2_STEP(b, c, d, e, a, W, 24, temp);
(gdb) 
418             SHA1COMPRESS_FULL_ROUND2_STEP(a, b, c, d, e, W, 25, temp);
(gdb) 
291             SHA1COMPRESS_FULL_ROUND1_STEP_LOAD(a, b, c, d, e, m, W, 0, temp);
(gdb) 
git(21728): unaligned access to 0x600000000009f8d5, ip=0x40000000003336d0
423             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 26, temp);

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Unaligned accesses in sha1dc

[Andreas Schwab]

SHA1DCUpdate calls sha1_process with buf being unaligned.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Is this with or without a0103914 ("sha1dc: update from upstream",
2017-05-20)?

Re: Unaligned accesses in sha1dc

[Andreas Schwab]

This is git 2.13.0.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Unaligned accesses in sha1dc

[brian m. carlson]

[-- Attachment #1: Type: text/plain, Size: 1274 bytes --]

On Thu, Jun 01, 2017 at 10:28:52AM +0200, Andreas Schwab wrote:
> The sh1dc implementation is making unaligned accesses, which will crash
> on some architectures, others have to emulate them in software.
> 
> Breakpoint 4, sha1_compression_states (ihv=0x600ffffffffe7010, 
>     m=<optimized out>, W=0x600ffffffffe70a8, states=0x600ffffffffe7328)
>     at sha1dc/sha1.c:398
> 398             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 21, temp);
> (gdb) n
> 403             SHA1COMPRESS_FULL_ROUND2_STEP(d, e, a, b, c, W, 22, temp);
> (gdb) 
> 408             SHA1COMPRESS_FULL_ROUND2_STEP(c, d, e, a, b, W, 23, temp);
> (gdb) 
> 413             SHA1COMPRESS_FULL_ROUND2_STEP(b, c, d, e, a, W, 24, temp);
> (gdb) 
> 418             SHA1COMPRESS_FULL_ROUND2_STEP(a, b, c, d, e, W, 25, temp);
> (gdb) 
> 291             SHA1COMPRESS_FULL_ROUND1_STEP_LOAD(a, b, c, d, e, m, W, 0, temp);
> (gdb) 
> git(21728): unaligned access to 0x600000000009f8d5, ip=0x40000000003336d0
> 423             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 26, temp);

What architecture are you seeing this on?
-- 
brian m. carlson / brian with sandals: Houston, Texas, US
https://www.crustytoothpaste.net/~bmc | My opinion only
OpenPGP: https://keybase.io/bk2204

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 868 bytes --]

Re: Unaligned accesses in sha1dc

[Lars Schneider]

> On 01 Jun 2017, at 10:28, Andreas Schwab <schwab@suse.de> wrote:
> 
> The sh1dc implementation is making unaligned accesses, which will crash
> on some architectures, others have to emulate them in software.

Is SPARC an architecture that would run into this problem? I think
there was a thread a few days ago about this...

What architectures are affected by this? I think I read somewhere
that ARM requires aligned accesses, too, right?

I wonder if it makes sense to emulate SPARC/ARM/... with QEMU on TravisCI [1].
Is this what you had in mind with "emulate" or do you see a better way?
If we compile and test in this environment - we should be able to catch
those bugs, right?

- Lars


[1] https://www.tomaz.me/2013/12/02/running-travis-ci-tests-on-arm.html

Re: Unaligned accesses in sha1dc

[Andreas Schwab]

On Jun 01 2017, "brian m. carlson" <sandals@crustytoothpaste.net> wrote:

> On Thu, Jun 01, 2017 at 10:28:52AM +0200, Andreas Schwab wrote:
>> The sh1dc implementation is making unaligned accesses, which will crash
>> on some architectures, others have to emulate them in software.
>> 
>> Breakpoint 4, sha1_compression_states (ihv=0x600ffffffffe7010, 
>>     m=<optimized out>, W=0x600ffffffffe70a8, states=0x600ffffffffe7328)
>>     at sha1dc/sha1.c:398
>> 398             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 21, temp);
>> (gdb) n
>> 403             SHA1COMPRESS_FULL_ROUND2_STEP(d, e, a, b, c, W, 22, temp);
>> (gdb) 
>> 408             SHA1COMPRESS_FULL_ROUND2_STEP(c, d, e, a, b, W, 23, temp);
>> (gdb) 
>> 413             SHA1COMPRESS_FULL_ROUND2_STEP(b, c, d, e, a, W, 24, temp);
>> (gdb) 
>> 418             SHA1COMPRESS_FULL_ROUND2_STEP(a, b, c, d, e, W, 25, temp);
>> (gdb) 
>> 291             SHA1COMPRESS_FULL_ROUND1_STEP_LOAD(a, b, c, d, e, m, W, 0, temp);
>> (gdb) 
>> git(21728): unaligned access to 0x600000000009f8d5, ip=0x40000000003336d0
>> 423             SHA1COMPRESS_FULL_ROUND2_STEP(e, a, b, c, d, W, 26, temp);
>
> What architecture are you seeing this on?

It doesn't matter.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Andreas Schwab <schwab@suse.de> writes:

> This is git 2.13.0.

Thanks.  It is a known issue with a known fix cooking in 'next' to
be merged down to 'master' and 'maint' not in a too distant future.
An extra testing to ensure that the "fix" actually works before it
is merged down to a maintenance release is very much appreciated.

    $ git fetch git://git.kernel.org/pub/scm/git/git.git/ next
    $ git checkout v2.13.0^0
    $ git merge a0103914

should show what the proposed v2.13.x would look like wrt to this
issue.

Thanks.

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Lars Schneider <larsxschneider@gmail.com> writes:

>> On 01 Jun 2017, at 10:28, Andreas Schwab <schwab@suse.de> wrote:
>> 
>> The sh1dc implementation is making unaligned accesses, which will crash
>> on some architectures, others have to emulate them in software.
>
> Is SPARC an architecture that would run into this problem? I think
> there was a thread a few days ago about this...
>
> What architectures are affected by this? I think I read somewhere
> that ARM requires aligned accesses, too, right?
>
> I wonder if it makes sense to emulate SPARC/ARM/... with QEMU on TravisCI [1].
> Is this what you had in mind with "emulate" or do you see a better way?

I think Andreas's "emulate" is that on these architectures often the
kernel catches the hardware trap and makes the unaligned access
appear to "just work" to the userland software, just like in very
old days, i386 and i486 without 387/487 used software floating point
"emulation" to give illusion to the userland softare that the co
processor was available.

Having to trap and emulate of course costs cycles, and if the
userland is written in such a way not to do an unaligned access in
the first place.

Depending on the model of "ARM" (or "SPARC") emulated with QEMU, and
depending on the OS that runs on such an "ARM" or "SPARC", we may
not see this---if the emulated OS has the "software unaligned-access
emulation" our userland may not see a SIGBUS.

Re: Unaligned accesses in sha1dc

[Andreas Schwab]

On Jun 01 2017, Junio C Hamano <gitster@pobox.com> wrote:

> Depending on the model of "ARM" (or "SPARC") emulated with QEMU, and
> depending on the OS that runs on such an "ARM" or "SPARC", we may
> not see this---if the emulated OS has the "software unaligned-access
> emulation" our userland may not see a SIGBUS.

Even if the architecture implements unaligned accesses in hardware, it
is still undefined behaviour, and the compiler will (eventually) take
advantage of it.

Andreas.

-- 
Andreas Schwab, SUSE Labs, schwab@suse.de
GPG Key fingerprint = 0196 BAD8 1CE9 1970 F4BE  1748 E4D4 88E3 0EEA B9D7
"And now for something completely different."

Re: Unaligned accesses in sha1dc

[Martin Ågren]

On 1 June 2017 at 12:08, Andreas Schwab <schwab@suse.de> wrote:
> On Jun 01 2017, Junio C Hamano <gitster@pobox.com> wrote:
>
>> Depending on the model of "ARM" (or "SPARC") emulated with QEMU, and
>> depending on the OS that runs on such an "ARM" or "SPARC", we may
>> not see this---if the emulated OS has the "software unaligned-access
>> emulation" our userland may not see a SIGBUS.
>
> Even if the architecture implements unaligned accesses in hardware, it
> is still undefined behaviour, and the compiler will (eventually) take
> advantage of it.

I tried to optically follow the macros and ended up on line 87/89 in
lib/sha1.c of the sha1dc-library, where there is undefined behavior if
the address is unaligned, which it seems it could be. Maybe Git uses
some particular combination of macro-definitions and I went down the
wrong path... There might also be other spots; I haven't thrown UBSan
at the code.

Using memcpy on those lines should not be a performance problem on
platforms where unaligned access is ok, of course assuming the
compiler sees the opportunity.

Martin

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren <martin.agren@gmail.com> wrote:
> On 1 June 2017 at 12:08, Andreas Schwab <schwab@suse.de> wrote:
>> On Jun 01 2017, Junio C Hamano <gitster@pobox.com> wrote:
>>
>>> Depending on the model of "ARM" (or "SPARC") emulated with QEMU, and
>>> depending on the OS that runs on such an "ARM" or "SPARC", we may
>>> not see this---if the emulated OS has the "software unaligned-access
>>> emulation" our userland may not see a SIGBUS.
>>
>> Even if the architecture implements unaligned accesses in hardware, it
>> is still undefined behaviour, and the compiler will (eventually) take
>> advantage of it.
>
> I tried to optically follow the macros and ended up on line 87/89 in
> lib/sha1.c of the sha1dc-library, where there is undefined behavior if
> the address is unaligned, which it seems it could be. Maybe Git uses
> some particular combination of macro-definitions and I went down the
> wrong path... There might also be other spots; I haven't thrown UBSan
> at the code.
>
> Using memcpy on those lines should not be a performance problem on
> platforms where unaligned access is ok, of course assuming the
> compiler sees the opportunity.

This is what the upstream version of sha1dc now in the next branch
does, i.e. just does a memcpy() on platforms which aren't on a
whitelist of CPUs that allow unaligned access.

Re: Unaligned accesses in sha1dc

[Martin Ågren]

On 1 June 2017 at 12:33, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren <martin.agren@gmail.com> wrote:
>> On 1 June 2017 at 12:08, Andreas Schwab <schwab@suse.de> wrote:
>>> Even if the architecture implements unaligned accesses in hardware, it
>>> is still undefined behaviour, and the compiler will (eventually) take
>>> advantage of it.
>>
>> I tried to optically follow the macros and ended up on line 87/89 in
>> lib/sha1.c of the sha1dc-library, where there is undefined behavior if
>> the address is unaligned, which it seems it could be. Maybe Git uses
>> some particular combination of macro-definitions and I went down the
>> wrong path... There might also be other spots; I haven't thrown UBSan
>> at the code.
>>
>> Using memcpy on those lines should not be a performance problem on
>> platforms where unaligned access is ok, of course assuming the
>> compiler sees the opportunity.
>
> This is what the upstream version of sha1dc now in the next branch
> does, i.e. just does a memcpy() on platforms which aren't on a
> whitelist of CPUs that allow unaligned access.

Ok, now I get it. Undefined behavior can occur on line 1772 in
sha1dc/sha1.c on "next", but only if SHA1DC_ALLOW_UNALIGNED_ACCESS is
defined. I don't think the macro does what its name suggests, though.
To me, it behaves more like
SHA1DC_RELY_ON_UNDEFINED_BEHAVIOR_TO_DO_THE_RIGHT_THING_BY_CHANCE...

So it seems the call chain of commands and macros could be redesigned
to work with "char*" instead of "uint32_t*"... Then the lines I
mentioned earlier could be converted to memcpy and "should" be
compiled to efficient loads where possible. Yes, I know, patches speak
for themselves, and no, this mail is not a patch.

Re: Unaligned accesses in sha1dc

[Martin Ågren]

On 1 June 2017 at 13:53, Martin Ågren <martin.agren@gmail.com> wrote:
> On 1 June 2017 at 12:33, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Thu, Jun 1, 2017 at 12:26 PM, Martin Ågren <martin.agren@gmail.com> wrote:
>>> On 1 June 2017 at 12:08, Andreas Schwab <schwab@suse.de> wrote:
>>>> Even if the architecture implements unaligned accesses in hardware, it
>>>> is still undefined behaviour, and the compiler will (eventually) take
>>>> advantage of it.
>>>
>>> I tried to optically follow the macros and ended up on line 87/89 in
>>> lib/sha1.c of the sha1dc-library, where there is undefined behavior if
>>> the address is unaligned, which it seems it could be. Maybe Git uses
>>> some particular combination of macro-definitions and I went down the
>>> wrong path... There might also be other spots; I haven't thrown UBSan
>>> at the code.
>>>
>>> Using memcpy on those lines should not be a performance problem on
>>> platforms where unaligned access is ok, of course assuming the
>>> compiler sees the opportunity.
>>
>> This is what the upstream version of sha1dc now in the next branch
>> does, i.e. just does a memcpy() on platforms which aren't on a
>> whitelist of CPUs that allow unaligned access.
>
> Ok, now I get it. Undefined behavior can occur on line 1772 in
> sha1dc/sha1.c on "next", but only if SHA1DC_ALLOW_UNALIGNED_ACCESS is
> defined. I don't think the macro does what its name suggests, though.
> To me, it behaves more like
> SHA1DC_RELY_ON_UNDEFINED_BEHAVIOR_TO_DO_THE_RIGHT_THING_BY_CHANCE...
>
> So it seems the call chain of commands and macros could be redesigned
> to work with "char*" instead of "uint32_t*"... Then the lines I
> mentioned earlier could be converted to memcpy and "should" be
> compiled to efficient loads where possible. Yes, I know, patches speak
> for themselves, and no, this mail is not a patch.

I looked into this some more. It turns out it is possible to trigger
undefined behavior on "next". Here's what I did:

diff --git a/Makefile b/Makefile
index 7c621f7..e3fdad0 100644
--- a/Makefile
+++ b/Makefile
@@ -402,7 +402,7 @@ GIT-VERSION-FILE: FORCE

 # CFLAGS and LDFLAGS are for the users to override from the command line.

-CFLAGS = -g -O2 -Wall
+CFLAGS = -g -O2 -Wall -fsanitize=undefined -fsanitize-recover=undefined
 DEVELOPER_CFLAGS = -Werror \
     -Wdeclaration-after-statement \
     -Wno-format-zero-length \
@@ -412,7 +412,7 @@ DEVELOPER_CFLAGS = -Werror \
     -Wstrict-prototypes \
     -Wunused \
     -Wvla
-LDFLAGS =
+LDFLAGS = -fsanitize=undefined -fsanitize-recover=undefined
 ALL_CFLAGS = $(CPPFLAGS) $(CFLAGS)
 ALL_LDFLAGS = $(LDFLAGS)
 STRIP ?= strip
diff --git a/t/helper/test-sha1.c b/t/helper/test-sha1.c
index a1c13f5..d4e1463 100644
--- a/t/helper/test-sha1.c
+++ b/t/helper/test-sha1.c
@@ -24,6 +24,8 @@ int cmd_main(int ac, const char **av)
         if (bufsz < 1024)
             die("OOPS");
     }
+    buffer++;
+    bufsz--;

     git_SHA1_Init(&ctx);



Then I ran

$ ./test-sha1 < ../t0013/shattered-1.pdf

in t/helper. No doubt an experienced Git developer would not patch the
Makefile and would not run the test like that, but that's what I did.
UBSan reports an unaligned load (the UB happened already as the
pointer was cast). Of course, tweaking the alignment of "buffer" is
cheating, but similar alignments can supposedly occur in the wild, or
the bug reports wouldn't be coming in.

This "fixes" the problem:

diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 3dff80a..d6f4c44 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -66,9 +66,9 @@
 #define sha1_mix(W, t)  (rotate_left(W[t - 3] ^ W[t - 8] ^ W[t - 14]
^ W[t - 16], 1))

 #ifdef SHA1DC_BIGENDIAN
-    #define sha1_load(m, t, temp)  { temp = m[t]; }
+    #define sha1_load(m, t, temp)  { memcpy(&temp, m+t*4, 4); }
 #else
-    #define sha1_load(m, t, temp)  { temp = m[t]; sha1_bswap32(temp); }
+    #define sha1_load(m, t, temp)  { memcpy(&temp, m+t*4, 4);
sha1_bswap32(temp); }
 #endif

 #define sha1_store(W, t, x)    *(volatile uint32_t *)&W[t] = x
@@ -309,7 +309,7 @@ static void sha1_compression_W(uint32_t ihv[5],
const uint32_t W[80])



-void sha1_compression_states(uint32_t ihv[5], const uint32_t m[16],
uint32_t W[80], uint32_t states[80][5])
+void sha1_compression_states(uint32_t ihv[5], const uint8_t m[64],
uint32_t W[80], uint32_t states[80][5])
 {
     uint32_t a = ihv[0], b = ihv[1], c = ihv[2], d = ihv[3], e = ihv[4];
     uint32_t temp;
@@ -1639,7 +1639,7 @@ static void sha1_recompression_step(uint32_t
step, uint32_t ihvin[5], uint32_t i



-static void sha1_process(SHA1_CTX* ctx, const uint32_t block[16])
+static void sha1_process(SHA1_CTX* ctx, const uint8_t block[64])
 {
     unsigned i, j;
     uint32_t ubc_dv_mask[DVMASKSIZE] = { 0xFFFFFFFF };
@@ -1759,7 +1759,7 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char*
buf, size_t len)
     {
         ctx->total += fill;
         memcpy(ctx->buffer + left, buf, fill);
-        sha1_process(ctx, (uint32_t*)(ctx->buffer));
+        sha1_process(ctx, (uint8_t*)(ctx->buffer));
         buf += fill;
         len -= fill;
         left = 0;
@@ -1769,10 +1769,10 @@ void SHA1DCUpdate(SHA1_CTX* ctx, const char*
buf, size_t len)
         ctx->total += 64;

 #if defined(SHA1DC_ALLOW_UNALIGNED_ACCESS)
-        sha1_process(ctx, (uint32_t*)(buf));
+        sha1_process(ctx, (uint8_t*)(buf));
 #else
         memcpy(ctx->buffer, buf, 64);
-        sha1_process(ctx, (uint32_t*)(ctx->buffer));
+        sha1_process(ctx, (uint8_t*)(ctx->buffer));
 #endif /* defined(SHA1DC_ALLOW_UNALIGNED_ACCESS) */
         buf += 64;
         len -= 64;
@@ -1809,7 +1809,7 @@ int SHA1DCFinal(unsigned char output[20], SHA1_CTX *ctx)
     ctx->buffer[61] = (unsigned char)(total >> 16);
     ctx->buffer[62] = (unsigned char)(total >> 8);
     ctx->buffer[63] = (unsigned char)(total);
-    sha1_process(ctx, (uint32_t*)(ctx->buffer));
+    sha1_process(ctx, (uint8_t*)(ctx->buffer));
     output[0] = (unsigned char)(ctx->ihv[0] >> 24);
     output[1] = (unsigned char)(ctx->ihv[0] >> 16);
     output[2] = (unsigned char)(ctx->ihv[0] >> 8);
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index a0ff5d1..1d181a1 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -18,7 +18,7 @@ extern "C" {

 /* sha-1 compression function that takes an already expanded message,
and additionally store intermediate states */
 /* only stores states ii (the state between step ii-1 and step ii)
when DOSTORESTATEii is defined in ubc_check.h */
-void sha1_compression_states(uint32_t[5], const uint32_t[16],
uint32_t[80], uint32_t[80][5]);
+void sha1_compression_states(uint32_t[5], const uint8_t[64],
uint32_t[80], uint32_t[80][5]);

 /*
 // Function type for sha1_recompression_step_T (uint32_t ihvin[5],
uint32_t ihvout[5], const uint32_t me2[80], const uint32_t state[5]).



With this diff, various tests which seem relevant for SHA-1 pass,
including t0013, and the UBSan-error is gone. The second diff is just
a monkey-patch. I have no reason to believe I will be able to come up
with a proper and complete patch for sha1dc. And I guess such a thing
would not really be Git's patch to carry, either. But at least Git
could consider whether to keep relying on undefined behavior or not.

There's a fair chance I've mangled the whitespace. I'm using gmail's
web interface... Sorry about that.

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Martin Ågren <martin.agren@gmail.com> writes:

> I looked into this some more. It turns out it is possible to trigger
> undefined behavior on "next". Here's what I did:
> ...
>
> This "fixes" the problem:
> ...
> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
> index 3dff80a..d6f4c44 100644
> --- a/sha1dc/sha1.c
> +++ b/sha1dc/sha1.c
> @@ -66,9 +66,9 @@
> ...
> With this diff, various tests which seem relevant for SHA-1 pass,
> including t0013, and the UBSan-error is gone. The second diff is just
> a monkey-patch. I have no reason to believe I will be able to come up
> with a proper and complete patch for sha1dc. And I guess such a thing
> would not really be Git's patch to carry, either. But at least Git
> could consider whether to keep relying on undefined behavior or not.
>
> There's a fair chance I've mangled the whitespace. I'm using gmail's
> web interface... Sorry about that.

Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
that the final "fix" would come from his sha1collisiondetection
repository via Ævar.

In the meantime, I am wondering if it makes sense to merge the
earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
would at least unblock those on platforms v2.13.0 did not work
correctly at all.

Ævar, thoughts?

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
> Martin Ågren <martin.agren@gmail.com> writes:
>
>> I looked into this some more. It turns out it is possible to trigger
>> undefined behavior on "next". Here's what I did:
>> ...
>>
>> This "fixes" the problem:
>> ...
>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>> index 3dff80a..d6f4c44 100644
>> --- a/sha1dc/sha1.c
>> +++ b/sha1dc/sha1.c
>> @@ -66,9 +66,9 @@
>> ...
>> With this diff, various tests which seem relevant for SHA-1 pass,
>> including t0013, and the UBSan-error is gone. The second diff is just
>> a monkey-patch. I have no reason to believe I will be able to come up
>> with a proper and complete patch for sha1dc. And I guess such a thing
>> would not really be Git's patch to carry, either. But at least Git
>> could consider whether to keep relying on undefined behavior or not.
>>
>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>> web interface... Sorry about that.
>
> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
> that the final "fix" would come from his sha1collisiondetection
> repository via Ævar.
>
> In the meantime, I am wondering if it makes sense to merge the
> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
> would at least unblock those on platforms v2.13.0 did not work
> correctly at all.
>
> Ævar, thoughts?

I think we're mixing up several things here, which need to be untangled:

1) The sha1dc works just fine on most platforms even with undefined
behavior, as evidenced by 2.13.0 working.

2) There was a bug in practice with unaligned access on SPARC. It's
not clear to me whether anyone (Andreas, Liam?) still has any issues
in practice on any platform without specifying compile flags like what
Martin Ågren suggested above.

Andreas: Is your initial report of unaligned access here fixed in the
next branch with my "sha1dc: update from upstream" commit? You didn't
say what platform you were on.

Liam: How about your issue on SPARC?

3) Now we have another issue reported by Martin Ågren here, which is
that while the code works in practice on most platforms it's using
undefined behavior. On my GCC 7.1.1 it's sufficient to:

    make -j8 CFLAGS="-fsanitize=undefined
-fsanitize-recover=undefined" LDFLAGS="-fsanitize=undefined
-fsanitize-recover=undefined" all

And then run e.g.:

    ./t0020-crlf.sh -v

To get spiel like:

    sha1dc/sha1.c:346:2: runtime error: load of misaligned address
0x5610bf16d005 for type 'const uint32_t', which requires 4 byte
alignment
    0x5610bf16d005: note: pointer points here
     65 6e 74 20 66 30 34  66 61 39 37 36 36 64 62  62 38 65 34 63 37
33 38  34 37 30 61 31 36 63 61  62

I think that this is definitely something worth looking into /
coordinating with upstream, but I haven't seen anything to suggest
that we need to be rushing to get a patch in to fix this given 1) and
nobody saying yet that 2) doesn't solve their issue as long as they're
not supplying some -fsanitize=* flags.

Now, stepping a bit back from this whole thing: I didn't read the
entire discussion back in February when sha1dc was integrated, but I
really don't see given all this churn / bug reporting we're getting
now why another acceptable solution wouldn't be to just revert
e6b07da278 ("Makefile: make DC_SHA1 the default", 2017-03-17) &
release 2.13.1 with that.

Clearly there are outstanding issues with it, and needing to do a
memcpy() as my `next` patch does will harm performance on some
platforms, and something like Martin's patch on top will slow it down
even more.

It seems to me that we should give it more time to cook, and better
understand the various trade-offs involved. The shattered attack is
very unlikely to impact anything in practice, and users who are
paranoid about it can opt-in to this extra protection.

Re: Unaligned accesses in sha1dc

[Martin Ågren]

On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> Martin Ågren <martin.agren@gmail.com> writes:
>>
>>> I looked into this some more. It turns out it is possible to trigger
>>> undefined behavior on "next". Here's what I did:
>>> ...
>>>
>>> This "fixes" the problem:
>>> ...
>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>> index 3dff80a..d6f4c44 100644
>>> --- a/sha1dc/sha1.c
>>> +++ b/sha1dc/sha1.c
>>> @@ -66,9 +66,9 @@
>>> ...
>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>> including t0013, and the UBSan-error is gone. The second diff is just
>>> a monkey-patch. I have no reason to believe I will be able to come up
>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>> would not really be Git's patch to carry, either. But at least Git
>>> could consider whether to keep relying on undefined behavior or not.
>>>
>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>> web interface... Sorry about that.
>>
>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>> that the final "fix" would come from his sha1collisiondetection
>> repository via Ævar.
>>
>> In the meantime, I am wondering if it makes sense to merge the
>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>> would at least unblock those on platforms v2.13.0 did not work
>> correctly at all.
>>
>> Ævar, thoughts?
>
> I think we're mixing up several things here, which need to be untangled:
>
> 1) The sha1dc works just fine on most platforms even with undefined
> behavior, as evidenced by 2.13.0 working.

Right, with "platform" meaning "combination of hardware-architecture
and compiler". Nothing can be said about how the current code behaves
on "x86". Such statements can only be made with regard to "x86 and
this or that compiler". Even then, short of studying the compiler
implementation/documentation in detail, one cannot be certain that
seemingly unrelated changes in Git don't make the code do something
else entirely.

> 2) There was a bug in practice with unaligned access on SPARC. It's
> not clear to me whether anyone (Andreas, Liam?) still has any issues
> in practice on any platform without specifying compile flags like what
> Martin Ågren suggested above.

True.

> 3) Now we have another issue reported by Martin Ågren here, which is
> that while the code works in practice on most platforms it's using
> undefined behavior.
...
> I think that this is definitely something worth looking into /
> coordinating with upstream, but I haven't seen anything to suggest
> that we need to be rushing to get a patch in to fix this given 1) and
> nobody saying yet that 2) doesn't solve their issue as long as they're
> not supplying some -fsanitize=* flags.
>
> Now, stepping a bit back from this whole thing: I didn't read the
> entire discussion back in February when sha1dc was integrated, but I
> really don't see given all this churn / bug reporting we're getting
> now why another acceptable solution wouldn't be to just revert
> e6b07da278 ("Makefile: make DC_SHA1 the default", 2017-03-17) &
> release 2.13.1 with that.
>
> Clearly there are outstanding issues with it, and needing to do a
> memcpy() as my `next` patch does will harm performance on some
> platforms, and something like Martin's patch on top will slow it down
> even more.

The only thing in my second "patch" which could possibly affect
performance as I see it would be the call to memcpy(.. ,.. ,4),
including pointer-calculation. Focusing on x86, I would not say that
it "will" slow it down until I'd measured performance. I wouldn't even
rule out that the compiled assembler could be identical. I would just
say the patch "would most likely slow it down even more on some
architectures, with some compilers and/or with some
compiler-settings".

If undefined behavior is avoided with memcpy(.., .., 4) then there
should be no formal need for your "big" memcpy where things are copied
into a known-to-be-aligned buffer. The behavior will be defined on all
architectures, anyway. Then your memcpy would simply be part of an
optimization to prefer one big memcpy and many loads instead of many
small memcpy-calls. On some architectures, that might be a very good
optimization. But on others, if the small memcpy is compiled to a
simple load, then I believe such an optimization would most likely be
a slow-down (modulo crazy-clever compiler optimizations).

> It seems to me that we should give it more time to cook, and better
> understand the various trade-offs involved. The shattered attack is
> very unlikely to impact anything in practice, and users who are
> paranoid about it can opt-in to this extra protection.

Regarding reverting and cooking, I don't feel like I'm in a position
to express an opinion. Thanks for thinking about this undefined
behavior, though, and I hope I'm contributing in some way, although
I'm aware I'm just standing at the side-line, waving my hands, and not
contributing any actual code.

Re: Unaligned accesses in sha1dc

[Liam R. Howlett]

* ?var Arnfj?r? Bjarmason <avarab@gmail.com> [170602 04:53]:
> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
> > Martin Ågren <martin.agren@gmail.com> writes:
> >
> >> I looked into this some more. It turns out it is possible to trigger
> >> undefined behavior on "next". Here's what I did:
> >> ...
> >>
> >> This "fixes" the problem:
> >> ...
> >> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
> >> index 3dff80a..d6f4c44 100644
> >> --- a/sha1dc/sha1.c
> >> +++ b/sha1dc/sha1.c
> >> @@ -66,9 +66,9 @@
> >> ...
> >> With this diff, various tests which seem relevant for SHA-1 pass,
> >> including t0013, and the UBSan-error is gone. The second diff is just
> >> a monkey-patch. I have no reason to believe I will be able to come up
> >> with a proper and complete patch for sha1dc. And I guess such a thing
> >> would not really be Git's patch to carry, either. But at least Git
> >> could consider whether to keep relying on undefined behavior or not.
> >>
> >> There's a fair chance I've mangled the whitespace. I'm using gmail's
> >> web interface... Sorry about that.
> >
> > Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
> > that the final "fix" would come from his sha1collisiondetection
> > repository via Ævar.
> >
> > In the meantime, I am wondering if it makes sense to merge the
> > earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
> > SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
> > would at least unblock those on platforms v2.13.0 did not work
> > correctly at all.
> >
> > Ævar, thoughts?
> 
> I think we're mixing up several things here, which need to be untangled:
> 
> 1) The sha1dc works just fine on most platforms even with undefined
> behavior, as evidenced by 2.13.0 working.
> 
> 2) There was a bug in practice with unaligned access on SPARC. It's
> not clear to me whether anyone (Andreas, Liam?) still has any issues
> in practice on any platform without specifying compile flags like what
> Martin Ågren suggested above.
> 
> Andreas: Is your initial report of unaligned access here fixed in the
> next branch with my "sha1dc: update from upstream" commit? You didn't
> say what platform you were on.
> 
> Liam: How about your issue on SPARC?

2.13.0 is very much broken for me on SPARC.
{maint//git} $ make -j120
[...]
{maint//git} $ ./git log
[1]    1004506 bus error (core dumped)  ./git log

This is with b06d36431 (maint).

The same thing happens on v2.13.0-384-g826c06412 (master).

v2.13.0-539-g4b9c06c7d (next) works for me, as did following the
instructions on upgrading the sha1dc code myself.

> 
> 3) Now we have another issue reported by Martin Ågren here, which is
> that while the code works in practice on most platforms it's using
> undefined behavior. On my GCC 7.1.1 it's sufficient to:

My platforms gcc is older than 7.1.1.

> 
>     make -j8 CFLAGS="-fsanitize=undefined
> -fsanitize-recover=undefined" LDFLAGS="-fsanitize=undefined
> -fsanitize-recover=undefined" all
> 
> And then run e.g.:
> 
>     ./t0020-crlf.sh -v

These tests pass With my older gcc - which those flags are not
recognized.

# passed all 35 test(s)


> 
> To get spiel like:
> 
>     sha1dc/sha1.c:346:2: runtime error: load of misaligned address
> 0x5610bf16d005 for type 'const uint32_t', which requires 4 byte
> alignment
>     0x5610bf16d005: note: pointer points here
>      65 6e 74 20 66 30 34  66 61 39 37 36 36 64 62  62 38 65 34 63 37
> 33 38  34 37 30 61 31 36 63 61  62
> 
> I think that this is definitely something worth looking into /
> coordinating with upstream, but I haven't seen anything to suggest
> that we need to be rushing to get a patch in to fix this given 1) and
> nobody saying yet that 2) doesn't solve their issue as long as they're
> not supplying some -fsanitize=* flags.
> 
> Now, stepping a bit back from this whole thing: I didn't read the
> entire discussion back in February when sha1dc was integrated, but I
> really don't see given all this churn / bug reporting we're getting
> now why another acceptable solution wouldn't be to just revert
> e6b07da278 ("Makefile: make DC_SHA1 the default", 2017-03-17) &
> release 2.13.1 with that.
> 
> Clearly there are outstanding issues with it, and needing to do a
> memcpy() as my `next` patch does will harm performance on some
> platforms, and something like Martin's patch on top will slow it down
> even more.
> 
> It seems to me that we should give it more time to cook, and better
> understand the various trade-offs involved. The shattered attack is
> very unlikely to impact anything in practice, and users who are
> paranoid about it can opt-in to this extra protection.

I have not seen issues with DC_SAH1 with the newer code base on SPARC.

Thanks,
Liam

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Fri, Jun 2, 2017 at 4:46 PM, Liam R. Howlett <Liam.Howlett@oracle.com> wrote:
> * ?var Arnfj?r? Bjarmason <avarab@gmail.com> [170602 04:53]:
>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>> > Martin Ågren <martin.agren@gmail.com> writes:
>> >
>> >> I looked into this some more. It turns out it is possible to trigger
>> >> undefined behavior on "next". Here's what I did:
>> >> ...
>> >>
>> >> This "fixes" the problem:
>> >> ...
>> >> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>> >> index 3dff80a..d6f4c44 100644
>> >> --- a/sha1dc/sha1.c
>> >> +++ b/sha1dc/sha1.c
>> >> @@ -66,9 +66,9 @@
>> >> ...
>> >> With this diff, various tests which seem relevant for SHA-1 pass,
>> >> including t0013, and the UBSan-error is gone. The second diff is just
>> >> a monkey-patch. I have no reason to believe I will be able to come up
>> >> with a proper and complete patch for sha1dc. And I guess such a thing
>> >> would not really be Git's patch to carry, either. But at least Git
>> >> could consider whether to keep relying on undefined behavior or not.
>> >>
>> >> There's a fair chance I've mangled the whitespace. I'm using gmail's
>> >> web interface... Sorry about that.
>> >
>> > Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>> > that the final "fix" would come from his sha1collisiondetection
>> > repository via Ævar.
>> >
>> > In the meantime, I am wondering if it makes sense to merge the
>> > earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>> > SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>> > would at least unblock those on platforms v2.13.0 did not work
>> > correctly at all.
>> >
>> > Ævar, thoughts?
>>
>> I think we're mixing up several things here, which need to be untangled:
>>
>> 1) The sha1dc works just fine on most platforms even with undefined
>> behavior, as evidenced by 2.13.0 working.
>>
>> 2) There was a bug in practice with unaligned access on SPARC. It's
>> not clear to me whether anyone (Andreas, Liam?) still has any issues
>> in practice on any platform without specifying compile flags like what
>> Martin Ågren suggested above.
>>
>> Andreas: Is your initial report of unaligned access here fixed in the
>> next branch with my "sha1dc: update from upstream" commit? You didn't
>> say what platform you were on.
>>
>> Liam: How about your issue on SPARC?
>
> 2.13.0 is very much broken for me on SPARC.
> {maint//git} $ make -j120
> [...]
> {maint//git} $ ./git log
> [1]    1004506 bus error (core dumped)  ./git log
>
> This is with b06d36431 (maint).
>
> The same thing happens on v2.13.0-384-g826c06412 (master).
>
> v2.13.0-539-g4b9c06c7d (next) works for me, as did following the
> instructions on upgrading the sha1dc code myself.

Thanks a lot. So that works as I suspect on SPARC, hopefully it'll be
in master (and 2.13.1) soon.

>>
>> 3) Now we have another issue reported by Martin Ågren here, which is
>> that while the code works in practice on most platforms it's using
>> undefined behavior. On my GCC 7.1.1 it's sufficient to:
>
> My platforms gcc is older than 7.1.1.

Right, shouldn't matter. Just thought I'd note the version for context
to note what version was producing that warning.

>>
>>     make -j8 CFLAGS="-fsanitize=undefined
>> -fsanitize-recover=undefined" LDFLAGS="-fsanitize=undefined
>> -fsanitize-recover=undefined" all
>>
>> And then run e.g.:
>>
>>     ./t0020-crlf.sh -v
>
> These tests pass With my older gcc - which those flags are not
> recognized.
>
> # passed all 35 test(s)
>
>
>>
>> To get spiel like:
>>
>>     sha1dc/sha1.c:346:2: runtime error: load of misaligned address
>> 0x5610bf16d005 for type 'const uint32_t', which requires 4 byte
>> alignment
>>     0x5610bf16d005: note: pointer points here
>>      65 6e 74 20 66 30 34  66 61 39 37 36 36 64 62  62 38 65 34 63 37
>> 33 38  34 37 30 61 31 36 63 61  62
>>
>> I think that this is definitely something worth looking into /
>> coordinating with upstream, but I haven't seen anything to suggest
>> that we need to be rushing to get a patch in to fix this given 1) and
>> nobody saying yet that 2) doesn't solve their issue as long as they're
>> not supplying some -fsanitize=* flags.
>>
>> Now, stepping a bit back from this whole thing: I didn't read the
>> entire discussion back in February when sha1dc was integrated, but I
>> really don't see given all this churn / bug reporting we're getting
>> now why another acceptable solution wouldn't be to just revert
>> e6b07da278 ("Makefile: make DC_SHA1 the default", 2017-03-17) &
>> release 2.13.1 with that.
>>
>> Clearly there are outstanding issues with it, and needing to do a
>> memcpy() as my `next` patch does will harm performance on some
>> platforms, and something like Martin's patch on top will slow it down
>> even more.
>>
>> It seems to me that we should give it more time to cook, and better
>> understand the various trade-offs involved. The shattered attack is
>> very unlikely to impact anything in practice, and users who are
>> paranoid about it can opt-in to this extra protection.
>
> I have not seen issues with DC_SAH1 with the newer code base on SPARC.

Great, thanks!

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>
>>>> I looked into this some more. It turns out it is possible to trigger
>>>> undefined behavior on "next". Here's what I did:
>>>> ...
>>>>
>>>> This "fixes" the problem:
>>>> ...
>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>> index 3dff80a..d6f4c44 100644
>>>> --- a/sha1dc/sha1.c
>>>> +++ b/sha1dc/sha1.c
>>>> @@ -66,9 +66,9 @@
>>>> ...
>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>> would not really be Git's patch to carry, either. But at least Git
>>>> could consider whether to keep relying on undefined behavior or not.
>>>>
>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>> web interface... Sorry about that.
>>>
>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>> that the final "fix" would come from his sha1collisiondetection
>>> repository via Ævar.
>>>
>>> In the meantime, I am wondering if it makes sense to merge the
>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>> would at least unblock those on platforms v2.13.0 did not work
>>> correctly at all.
>>>
>>> Ævar, thoughts?
>>
>> I think we're mixing up several things here, which need to be untangled:
>>
>> 1) The sha1dc works just fine on most platforms even with undefined
>> behavior, as evidenced by 2.13.0 working.
>
> Right, with "platform" meaning "combination of hardware-architecture
> and compiler". Nothing can be said about how the current code behaves
> on "x86". Such statements can only be made with regard to "x86 and
> this or that compiler". Even then, short of studying the compiler
> implementation/documentation in detail, one cannot be certain that
> seemingly unrelated changes in Git don't make the code do something
> else entirely.

I think you're veering into a theoretical discussion here that has
little to no bearing on the practicalities involved here.

Yes if something is undefined behavior in C the compiler &
architecture is free to do anything they want with it. In practice
lots of undefined behavior is de-facto standardized across various
platforms.

As far as I can tell unaligned access is one of those things. I don't
think there's ever been an x86 chip / compiler that would run this
code with any semantic differences when it comes to unaligned access,
and such a chip / compiler is unlikely to ever exist.

I'm not advocating that we rely on undefined behavior willy-nilly,
just that we should consider the real situation is (i.e. what actual
architectures / compilers are doing or are likely to do) as opposed to
the purely theoretical (if you gave a bunch of aliens who'd never
heard of our technology the ANSI C standard to implement from
scratch).

Here's a performance test of your patch above against p3400-rebase.sh.
I don't know how much these error bars from t/perf can be trusted.
This is over 30 runs with -O3:

- 3400.2: rebase on top of a lot of unrelated changes
  v2.12.0     : 1.25(1.10+0.06)
  v2.13.0     : 1.21(1.06+0.06) -3.2%
  origin/next : 1.22(1.04+0.07) -2.4%
  martin        : 1.23(1.06+0.07) -1.6%
- 3400.4: rebase a lot of unrelated changes without split-index
  v2.12.0     : 6.49(3.60+0.52)
  v2.13.0     : 8.21(4.18+0.55) +26.5%
  origin/next : 8.27(4.34+0.64) +27.4%
  martin        : 8.80(4.36+0.62) +35.6%
- 3400.6: rebase a lot of unrelated changes with split-index
  v2.12.0     : 6.77(3.56+0.51)
  v2.13.0     : 4.09(2.67+0.38) -39.6%
  origin/next : 4.13(2.70+0.36) -39.0%
  martin        : 4.30(2.80+0.32) -36.5%

And just your patch v.s. next:

- 3400.2: rebase on top of a lot of unrelated changes
  origin/next : 1.22(1.06+0.06)
  martin      : 1.22(1.06+0.05) +0.0%
- 3400.4: rebase a lot of unrelated changes without split-index
  origin/next : 7.54(4.13+0.60)
  martin      : 7.75(4.34+0.67) +2.8%
- 3400.6: rebase a lot of unrelated changes with split-index
  origin/next : 4.19(2.92+0.31)
  martin      : 4.14(2.84+0.39) -1.2%

It seems to be a bit slower, is that speedup worth the use of
unaligned access? I genuinely don't know. I'm just interested to find
what if anything we need to urgently fix in a release version of git.

One data point there is that the fallback blk-sha1 implementation
we've shipped since 2009 has the same errors about unaligned access as
before your patch with -fsanitize[..], and looking at the commit
message this was something Linus knew about at the time, see
d7c208a92e ("Add new optimized C 'block-sha1' routines", 2009-08-05).

That's strong empirical data suggesting that whatever we want to do
about unaligned access in the future it's not something which in
practice would cause wrong sha1 results for the implementation
shipping with v2.13.0.

As an aside, when I was trying to apply your patch I made a mistake,
and found that git's test suite could run 100% OK with a bad sha1
implementation, I didn't apply this part (word diff):

diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
index 04b104fe58..d6f4c442b5 100644
--- a/sha1dc/sha1.c
+++ b/sha1dc/sha1.c
@@ -312 +312 @@ static void sha1_compression_W(uint32_t ihv[5], const
uint32_t W[80])
void sha1_compression_states(uint32_t ihv[5], const
[-uint32_t-]{+uint8_t+} m[64], uint32_t W[80], uint32_t states[80][5])
@@ -1642 +1642 @@ static void sha1_recompression_step(uint32_t step,
uint32_t ihvin[5], uint32_t i
static void sha1_process(SHA1_CTX* ctx, const [-uint32_t-]{+uint8_t+} block[64])
diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
index 1d1d2b8d7c..1d181a1403 100644
--- a/sha1dc/sha1.h
+++ b/sha1dc/sha1.h
@@ -21 +21 @@ extern "C" {
void sha1_compression_states(uint32_t[5], const
[-uint32_t-]{+uint8_t+}[64], uint32_t[80], uint32_t[80][5]);

The p3400-rebase.sh test will fail with your patch without that
change, but not any of the tests, gulp!

>> 2) There was a bug in practice with unaligned access on SPARC. It's
>> not clear to me whether anyone (Andreas, Liam?) still has any issues
>> in practice on any platform without specifying compile flags like what
>> Martin Ågren suggested above.
>
> True.
>
>> 3) Now we have another issue reported by Martin Ågren here, which is
>> that while the code works in practice on most platforms it's using
>> undefined behavior.
> ...
>> I think that this is definitely something worth looking into /
>> coordinating with upstream, but I haven't seen anything to suggest
>> that we need to be rushing to get a patch in to fix this given 1) and
>> nobody saying yet that 2) doesn't solve their issue as long as they're
>> not supplying some -fsanitize=* flags.
>>
>> Now, stepping a bit back from this whole thing: I didn't read the
>> entire discussion back in February when sha1dc was integrated, but I
>> really don't see given all this churn / bug reporting we're getting
>> now why another acceptable solution wouldn't be to just revert
>> e6b07da278 ("Makefile: make DC_SHA1 the default", 2017-03-17) &
>> release 2.13.1 with that.
>>
>> Clearly there are outstanding issues with it, and needing to do a
>> memcpy() as my `next` patch does will harm performance on some
>> platforms, and something like Martin's patch on top will slow it down
>> even more.
>
> The only thing in my second "patch" which could possibly affect
> performance as I see it would be the call to memcpy(.. ,.. ,4),
> including pointer-calculation. Focusing on x86, I would not say that
> it "will" slow it down until I'd measured performance. I wouldn't even
> rule out that the compiled assembler could be identical. I would just
> say the patch "would most likely slow it down even more on some
> architectures, with some compilers and/or with some
> compiler-settings".
>
> If undefined behavior is avoided with memcpy(.., .., 4) then there
> should be no formal need for your "big" memcpy where things are copied
> into a known-to-be-aligned buffer. The behavior will be defined on all
> architectures, anyway. Then your memcpy would simply be part of an
> optimization to prefer one big memcpy and many loads instead of many
> small memcpy-calls. On some architectures, that might be a very good
> optimization. But on others, if the small memcpy is compiled to a
> simple load, then I believe such an optimization would most likely be
> a slow-down (modulo crazy-clever compiler optimizations).
>
>> It seems to me that we should give it more time to cook, and better
>> understand the various trade-offs involved. The shattered attack is
>> very unlikely to impact anything in practice, and users who are
>> paranoid about it can opt-in to this extra protection.
>
> Regarding reverting and cooking, I don't feel like I'm in a position
> to express an opinion. Thanks for thinking about this undefined
> behavior, though, and I hope I'm contributing in some way, although
> I'm aware I'm just standing at the side-line, waving my hands, and not
> contributing any actual code.

Re: Unaligned accesses in sha1dc

[Martin Ågren]

On 2 June 2017 at 21:32, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>>
>>>>> I looked into this some more. It turns out it is possible to trigger
>>>>> undefined behavior on "next". Here's what I did:
>>>>> ...
>>>>>
>>>>> This "fixes" the problem:
>>>>> ...
>>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>>> index 3dff80a..d6f4c44 100644
>>>>> --- a/sha1dc/sha1.c
>>>>> +++ b/sha1dc/sha1.c
>>>>> @@ -66,9 +66,9 @@
>>>>> ...
>>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>>> would not really be Git's patch to carry, either. But at least Git
>>>>> could consider whether to keep relying on undefined behavior or not.
>>>>>
>>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>>> web interface... Sorry about that.
>>>>
>>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>>> that the final "fix" would come from his sha1collisiondetection
>>>> repository via Ævar.
>>>>
>>>> In the meantime, I am wondering if it makes sense to merge the
>>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>>> would at least unblock those on platforms v2.13.0 did not work
>>>> correctly at all.
>>>>
>>>> Ævar, thoughts?
>>>
>>> I think we're mixing up several things here, which need to be untangled:
>>>
>>> 1) The sha1dc works just fine on most platforms even with undefined
>>> behavior, as evidenced by 2.13.0 working.
>>
>> Right, with "platform" meaning "combination of hardware-architecture
>> and compiler". Nothing can be said about how the current code behaves
>> on "x86". Such statements can only be made with regard to "x86 and
>> this or that compiler". Even then, short of studying the compiler
>> implementation/documentation in detail, one cannot be certain that
>> seemingly unrelated changes in Git don't make the code do something
>> else entirely.
>
> I think you're veering into a theoretical discussion here that has
> little to no bearing on the practicalities involved here.
>
> Yes if something is undefined behavior in C the compiler &
> architecture is free to do anything they want with it. In practice
> lots of undefined behavior is de-facto standardized across various
> platforms.
>
> As far as I can tell unaligned access is one of those things. I don't
> think there's ever been an x86 chip / compiler that would run this
> code with any semantic differences when it comes to unaligned access,
> and such a chip / compiler is unlikely to ever exist.
>
> I'm not advocating that we rely on undefined behavior willy-nilly,
> just that we should consider the real situation is (i.e. what actual
> architectures / compilers are doing or are likely to do) as opposed to
> the purely theoretical (if you gave a bunch of aliens who'd never
> heard of our technology the ANSI C standard to implement from
> scratch).

Yeah, that's an argument. I just thought I'd provide whatever input I
could, albeit in text form. The only thing that matters in the end is
that you (the Git project) feel that you make the correct decision,
possibly going beyond "theoretical" reasoning into engineering-land.

Take care,
Martin

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Fri, Jun 2, 2017 at 10:11 PM, Martin Ågren <martin.agren@gmail.com> wrote:
> On 2 June 2017 at 21:32, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>>> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>>>
>>>>>> I looked into this some more. It turns out it is possible to trigger
>>>>>> undefined behavior on "next". Here's what I did:
>>>>>> ...
>>>>>>
>>>>>> This "fixes" the problem:
>>>>>> ...
>>>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>>>> index 3dff80a..d6f4c44 100644
>>>>>> --- a/sha1dc/sha1.c
>>>>>> +++ b/sha1dc/sha1.c
>>>>>> @@ -66,9 +66,9 @@
>>>>>> ...
>>>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>>>> would not really be Git's patch to carry, either. But at least Git
>>>>>> could consider whether to keep relying on undefined behavior or not.
>>>>>>
>>>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>>>> web interface... Sorry about that.
>>>>>
>>>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>>>> that the final "fix" would come from his sha1collisiondetection
>>>>> repository via Ævar.
>>>>>
>>>>> In the meantime, I am wondering if it makes sense to merge the
>>>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>>>> would at least unblock those on platforms v2.13.0 did not work
>>>>> correctly at all.
>>>>>
>>>>> Ævar, thoughts?
>>>>
>>>> I think we're mixing up several things here, which need to be untangled:
>>>>
>>>> 1) The sha1dc works just fine on most platforms even with undefined
>>>> behavior, as evidenced by 2.13.0 working.
>>>
>>> Right, with "platform" meaning "combination of hardware-architecture
>>> and compiler". Nothing can be said about how the current code behaves
>>> on "x86". Such statements can only be made with regard to "x86 and
>>> this or that compiler". Even then, short of studying the compiler
>>> implementation/documentation in detail, one cannot be certain that
>>> seemingly unrelated changes in Git don't make the code do something
>>> else entirely.
>>
>> I think you're veering into a theoretical discussion here that has
>> little to no bearing on the practicalities involved here.
>>
>> Yes if something is undefined behavior in C the compiler &
>> architecture is free to do anything they want with it. In practice
>> lots of undefined behavior is de-facto standardized across various
>> platforms.
>>
>> As far as I can tell unaligned access is one of those things. I don't
>> think there's ever been an x86 chip / compiler that would run this
>> code with any semantic differences when it comes to unaligned access,
>> and such a chip / compiler is unlikely to ever exist.
>>
>> I'm not advocating that we rely on undefined behavior willy-nilly,
>> just that we should consider the real situation is (i.e. what actual
>> architectures / compilers are doing or are likely to do) as opposed to
>> the purely theoretical (if you gave a bunch of aliens who'd never
>> heard of our technology the ANSI C standard to implement from
>> scratch).
>
> Yeah, that's an argument. I just thought I'd provide whatever input I
> could, albeit in text form. The only thing that matters in the end is
> that you (the Git project) feel that you make the correct decision,
> possibly going beyond "theoretical" reasoning into engineering-land.

I forgot to note, I think it would be very useful if you could submit
that patch of yours in cleaned up form to the upstream sha1dc project:
https://github.com/cr-marcstevens/sha1collisiondetection

They might be interested in taking it, even if it's guarded by some
macro "don't do unaligned access even on archs that seem OK with it".

My comments are just focusing on this in the context of whether we
should be hotfixing our copy due to an issue in the wild, like e.g.
the SPARC issue.

Re: Unaligned accesses in sha1dc

[demerphq]

On 2 June 2017 at 21:32, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>>
>>>>> I looked into this some more. It turns out it is possible to trigger
>>>>> undefined behavior on "next". Here's what I did:
>>>>> ...
>>>>>
>>>>> This "fixes" the problem:
>>>>> ...
>>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>>> index 3dff80a..d6f4c44 100644
>>>>> --- a/sha1dc/sha1.c
>>>>> +++ b/sha1dc/sha1.c
>>>>> @@ -66,9 +66,9 @@
>>>>> ...
>>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>>> would not really be Git's patch to carry, either. But at least Git
>>>>> could consider whether to keep relying on undefined behavior or not.
>>>>>
>>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>>> web interface... Sorry about that.
>>>>
>>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>>> that the final "fix" would come from his sha1collisiondetection
>>>> repository via Ævar.
>>>>
>>>> In the meantime, I am wondering if it makes sense to merge the
>>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>>> would at least unblock those on platforms v2.13.0 did not work
>>>> correctly at all.
>>>>
>>>> Ævar, thoughts?
>>>
>>> I think we're mixing up several things here, which need to be untangled:
>>>
>>> 1) The sha1dc works just fine on most platforms even with undefined
>>> behavior, as evidenced by 2.13.0 working.
>>
>> Right, with "platform" meaning "combination of hardware-architecture
>> and compiler". Nothing can be said about how the current code behaves
>> on "x86". Such statements can only be made with regard to "x86 and
>> this or that compiler". Even then, short of studying the compiler
>> implementation/documentation in detail, one cannot be certain that
>> seemingly unrelated changes in Git don't make the code do something
>> else entirely.
>
> I think you're veering into a theoretical discussion here that has
> little to no bearing on the practicalities involved here.
>
> Yes if something is undefined behavior in C the compiler &
> architecture is free to do anything they want with it. In practice
> lots of undefined behavior is de-facto standardized across various
> platforms.
>
> As far as I can tell unaligned access is one of those things. I don't
> think there's ever been an x86 chip / compiler that would run this
> code with any semantic differences when it comes to unaligned access,
> and such a chip / compiler is unlikely to ever exist.
>
> I'm not advocating that we rely on undefined behavior willy-nilly,
> just that we should consider the real situation is (i.e. what actual
> architectures / compilers are doing or are likely to do) as opposed to
> the purely theoretical (if you gave a bunch of aliens who'd never
> heard of our technology the ANSI C standard to implement from
> scratch).
>
> Here's a performance test of your patch above against p3400-rebase.sh.
> I don't know how much these error bars from t/perf can be trusted.
> This is over 30 runs with -O3:
>
> - 3400.2: rebase on top of a lot of unrelated changes
>   v2.12.0     : 1.25(1.10+0.06)
>   v2.13.0     : 1.21(1.06+0.06) -3.2%
>   origin/next : 1.22(1.04+0.07) -2.4%
>   martin        : 1.23(1.06+0.07) -1.6%
> - 3400.4: rebase a lot of unrelated changes without split-index
>   v2.12.0     : 6.49(3.60+0.52)
>   v2.13.0     : 8.21(4.18+0.55) +26.5%
>   origin/next : 8.27(4.34+0.64) +27.4%
>   martin        : 8.80(4.36+0.62) +35.6%
> - 3400.6: rebase a lot of unrelated changes with split-index
>   v2.12.0     : 6.77(3.56+0.51)
>   v2.13.0     : 4.09(2.67+0.38) -39.6%
>   origin/next : 4.13(2.70+0.36) -39.0%
>   martin        : 4.30(2.80+0.32) -36.5%
>
> And just your patch v.s. next:
>
> - 3400.2: rebase on top of a lot of unrelated changes
>   origin/next : 1.22(1.06+0.06)
>   martin      : 1.22(1.06+0.05) +0.0%
> - 3400.4: rebase a lot of unrelated changes without split-index
>   origin/next : 7.54(4.13+0.60)
>   martin      : 7.75(4.34+0.67) +2.8%
> - 3400.6: rebase a lot of unrelated changes with split-index
>   origin/next : 4.19(2.92+0.31)
>   martin      : 4.14(2.84+0.39) -1.2%
>
> It seems to be a bit slower, is that speedup worth the use of
> unaligned access? I genuinely don't know. I'm just interested to find
> what if anything we need to urgently fix in a release version of git.
>
> One data point there is that the fallback blk-sha1 implementation
> we've shipped since 2009 has the same errors about unaligned access as
> before your patch with -fsanitize[..], and looking at the commit
> message this was something Linus knew about at the time, see
> d7c208a92e ("Add new optimized C 'block-sha1' routines", 2009-08-05).
>
> That's strong empirical data suggesting that whatever we want to do
> about unaligned access in the future it's not something which in
> practice would cause wrong sha1 results for the implementation
> shipping with v2.13.0.
>
> As an aside, when I was trying to apply your patch I made a mistake,
> and found that git's test suite could run 100% OK with a bad sha1
> implementation, I didn't apply this part (word diff):
>
> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
> index 04b104fe58..d6f4c442b5 100644
> --- a/sha1dc/sha1.c
> +++ b/sha1dc/sha1.c
> @@ -312 +312 @@ static void sha1_compression_W(uint32_t ihv[5], const
> uint32_t W[80])
> void sha1_compression_states(uint32_t ihv[5], const
> [-uint32_t-]{+uint8_t+} m[64], uint32_t W[80], uint32_t states[80][5])
> @@ -1642 +1642 @@ static void sha1_recompression_step(uint32_t step,
> uint32_t ihvin[5], uint32_t i
> static void sha1_process(SHA1_CTX* ctx, const [-uint32_t-]{+uint8_t+} block[64])
> diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
> index 1d1d2b8d7c..1d181a1403 100644
> --- a/sha1dc/sha1.h
> +++ b/sha1dc/sha1.h
> @@ -21 +21 @@ extern "C" {
> void sha1_compression_states(uint32_t[5], const
> [-uint32_t-]{+uint8_t+}[64], uint32_t[80], uint32_t[80][5]);


That change doesnt look right anyway.

The original code asserts that it will receive a pointer to 64
uint32_t's as the second argument.

The changed code asserts that it will receive a pointer to 64
uint8_t's as the second argument.

If you change the type you will need to change the *number* correspondingly.

I would expect to see the uint32_t[64] to turn into uint8_t[256]

I have noticed that gcc does not necessarily enforce these types of
declarations and I believe that the change might not have any affect
at all depending on how the pointers are being used. (C passes
pointers on the stack, so afaik these things are more hints than
anything else.)

Looking at the code it looks like it conflates endianness with
alignedness when they arent the same thing, except that the majority
of little-endian boxes are x86 which do not require aligned access,
and many big-endian boxes do require aligned access. IOW, even they
are often related they are distinct properties.

Most hash function implementations have code like the following
(extracted and reduced from hv_macro.h in perl.git [which only
supports little-endian hash functions]):

#ifndef U32_ALIGNMENT_REQUIRED
  #if (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678)
    #define U8TO32_LE(ptr)   (*((const U32*)(ptr)))
#elif (BYTEORDER == 0x4321 || BYTEORDER == 0x87654321)
    #if defined(__GNUC__) && (__GNUC__>4 || (__GNUC__==4 && __GNUC_MINOR__>=3))
      #define U8TO32_LE(ptr)   (__builtin_bswap32(*((U32*)(ptr))))
    #endif
  #endif
#endif

#ifndef U8TO16_LE
    /* Without a known fast bswap32 we're just as well off doing this */
  #define U8TO32_LE(ptr)
((U32)(ptr)[0]|(U32)(ptr)[1]<<8|(U32)(ptr)[2]<<16|(U32)(ptr)[3]<<24)
#endif

Of course, in the case of SHA1 it is defined as being big-endian
(making it a relatively poor choice for use on x86), so you would need
to reverse a bit of this logic.

Note the form shown in that last block will work regardless of
endianness or alignedness requirements and should be optimised
properly by most compilers into the most efficient operation.

In other words, if you guys just switch to that kind of pattern this
problem will go away everywhere, and the only issue you will have to
consider is if it makes some oddball platforms too slow.

Yves

-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

Re: Unaligned accesses in sha1dc

[demerphq]

On 2 June 2017 at 22:14, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
> On Fri, Jun 2, 2017 at 10:11 PM, Martin Ågren <martin.agren@gmail.com> wrote:
>> On 2 June 2017 at 21:32, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>> On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>>>> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>>>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>>>>
>>>>>>> I looked into this some more. It turns out it is possible to trigger
>>>>>>> undefined behavior on "next". Here's what I did:
>>>>>>> ...
>>>>>>>
>>>>>>> This "fixes" the problem:
>>>>>>> ...
>>>>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>>>>> index 3dff80a..d6f4c44 100644
>>>>>>> --- a/sha1dc/sha1.c
>>>>>>> +++ b/sha1dc/sha1.c
>>>>>>> @@ -66,9 +66,9 @@
>>>>>>> ...
>>>>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>>>>> would not really be Git's patch to carry, either. But at least Git
>>>>>>> could consider whether to keep relying on undefined behavior or not.
>>>>>>>
>>>>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>>>>> web interface... Sorry about that.
>>>>>>
>>>>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>>>>> that the final "fix" would come from his sha1collisiondetection
>>>>>> repository via Ævar.
>>>>>>
>>>>>> In the meantime, I am wondering if it makes sense to merge the
>>>>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>>>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>>>>> would at least unblock those on platforms v2.13.0 did not work
>>>>>> correctly at all.
>>>>>>
>>>>>> Ævar, thoughts?
>>>>>
>>>>> I think we're mixing up several things here, which need to be untangled:
>>>>>
>>>>> 1) The sha1dc works just fine on most platforms even with undefined
>>>>> behavior, as evidenced by 2.13.0 working.
>>>>
>>>> Right, with "platform" meaning "combination of hardware-architecture
>>>> and compiler". Nothing can be said about how the current code behaves
>>>> on "x86". Such statements can only be made with regard to "x86 and
>>>> this or that compiler". Even then, short of studying the compiler
>>>> implementation/documentation in detail, one cannot be certain that
>>>> seemingly unrelated changes in Git don't make the code do something
>>>> else entirely.
>>>
>>> I think you're veering into a theoretical discussion here that has
>>> little to no bearing on the practicalities involved here.
>>>
>>> Yes if something is undefined behavior in C the compiler &
>>> architecture is free to do anything they want with it. In practice
>>> lots of undefined behavior is de-facto standardized across various
>>> platforms.
>>>
>>> As far as I can tell unaligned access is one of those things. I don't
>>> think there's ever been an x86 chip / compiler that would run this
>>> code with any semantic differences when it comes to unaligned access,
>>> and such a chip / compiler is unlikely to ever exist.
>>>
>>> I'm not advocating that we rely on undefined behavior willy-nilly,
>>> just that we should consider the real situation is (i.e. what actual
>>> architectures / compilers are doing or are likely to do) as opposed to
>>> the purely theoretical (if you gave a bunch of aliens who'd never
>>> heard of our technology the ANSI C standard to implement from
>>> scratch).
>>
>> Yeah, that's an argument. I just thought I'd provide whatever input I
>> could, albeit in text form. The only thing that matters in the end is
>> that you (the Git project) feel that you make the correct decision,
>> possibly going beyond "theoretical" reasoning into engineering-land.
>
> I forgot to note, I think it would be very useful if you could submit
> that patch of yours in cleaned up form to the upstream sha1dc project:
> https://github.com/cr-marcstevens/sha1collisiondetection
>
> They might be interested in taking it, even if it's guarded by some
> macro "don't do unaligned access even on archs that seem OK with it".
>
> My comments are just focusing on this in the context of whether we
> should be hotfixing our copy due to an issue in the wild, like e.g.
> the SPARC issue.

A good way to get the sha1dc project properly tests on all platforms
would be to wrap it in a cpan distribution and let cpants (cpan
testers) test it for you on all the platforms under the sun.

In the Sereal project we found and fixed many portability issues with
the csnappy code simply because there are people testing modules in
the cpan world on every platform you can think of, and a few you might
be surprised to find out people still use.

Yves

Yves


-- 
perl -Mre=debug -e "/just|another|perl|hacker/"

Re: Unaligned accesses in sha1dc

[Ævar Arnfjörð Bjarmason]

On Fri, Jun 2, 2017 at 10:17 PM, demerphq <demerphq@gmail.com> wrote:
> On 2 June 2017 at 21:32, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>> On Fri, Jun 2, 2017 at 11:49 AM, Martin Ågren <martin.agren@gmail.com> wrote:
>>> On 2 June 2017 at 10:51, Ævar Arnfjörð Bjarmason <avarab@gmail.com> wrote:
>>>> On Fri, Jun 2, 2017 at 2:15 AM, Junio C Hamano <gitster@pobox.com> wrote:
>>>>> Martin Ågren <martin.agren@gmail.com> writes:
>>>>>
>>>>>> I looked into this some more. It turns out it is possible to trigger
>>>>>> undefined behavior on "next". Here's what I did:
>>>>>> ...
>>>>>>
>>>>>> This "fixes" the problem:
>>>>>> ...
>>>>>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>>>>>> index 3dff80a..d6f4c44 100644
>>>>>> --- a/sha1dc/sha1.c
>>>>>> +++ b/sha1dc/sha1.c
>>>>>> @@ -66,9 +66,9 @@
>>>>>> ...
>>>>>> With this diff, various tests which seem relevant for SHA-1 pass,
>>>>>> including t0013, and the UBSan-error is gone. The second diff is just
>>>>>> a monkey-patch. I have no reason to believe I will be able to come up
>>>>>> with a proper and complete patch for sha1dc. And I guess such a thing
>>>>>> would not really be Git's patch to carry, either. But at least Git
>>>>>> could consider whether to keep relying on undefined behavior or not.
>>>>>>
>>>>>> There's a fair chance I've mangled the whitespace. I'm using gmail's
>>>>>> web interface... Sorry about that.
>>>>>
>>>>> Thanks.  I see Marc Stevens is CC'ed in the thread, so I'd expect
>>>>> that the final "fix" would come from his sha1collisiondetection
>>>>> repository via Ævar.
>>>>>
>>>>> In the meantime, I am wondering if it makes sense to merge the
>>>>> earlier update with #ifdef ALLOW_UNALIGNED_ACCESS and #ifdef
>>>>> SHA1DC_FORCE_LITTLEENDIAN for the v2.13.x maintenance track, which
>>>>> would at least unblock those on platforms v2.13.0 did not work
>>>>> correctly at all.
>>>>>
>>>>> Ævar, thoughts?
>>>>
>>>> I think we're mixing up several things here, which need to be untangled:
>>>>
>>>> 1) The sha1dc works just fine on most platforms even with undefined
>>>> behavior, as evidenced by 2.13.0 working.
>>>
>>> Right, with "platform" meaning "combination of hardware-architecture
>>> and compiler". Nothing can be said about how the current code behaves
>>> on "x86". Such statements can only be made with regard to "x86 and
>>> this or that compiler". Even then, short of studying the compiler
>>> implementation/documentation in detail, one cannot be certain that
>>> seemingly unrelated changes in Git don't make the code do something
>>> else entirely.
>>
>> I think you're veering into a theoretical discussion here that has
>> little to no bearing on the practicalities involved here.
>>
>> Yes if something is undefined behavior in C the compiler &
>> architecture is free to do anything they want with it. In practice
>> lots of undefined behavior is de-facto standardized across various
>> platforms.
>>
>> As far as I can tell unaligned access is one of those things. I don't
>> think there's ever been an x86 chip / compiler that would run this
>> code with any semantic differences when it comes to unaligned access,
>> and such a chip / compiler is unlikely to ever exist.
>>
>> I'm not advocating that we rely on undefined behavior willy-nilly,
>> just that we should consider the real situation is (i.e. what actual
>> architectures / compilers are doing or are likely to do) as opposed to
>> the purely theoretical (if you gave a bunch of aliens who'd never
>> heard of our technology the ANSI C standard to implement from
>> scratch).
>>
>> Here's a performance test of your patch above against p3400-rebase.sh.
>> I don't know how much these error bars from t/perf can be trusted.
>> This is over 30 runs with -O3:
>>
>> - 3400.2: rebase on top of a lot of unrelated changes
>>   v2.12.0     : 1.25(1.10+0.06)
>>   v2.13.0     : 1.21(1.06+0.06) -3.2%
>>   origin/next : 1.22(1.04+0.07) -2.4%
>>   martin        : 1.23(1.06+0.07) -1.6%
>> - 3400.4: rebase a lot of unrelated changes without split-index
>>   v2.12.0     : 6.49(3.60+0.52)
>>   v2.13.0     : 8.21(4.18+0.55) +26.5%
>>   origin/next : 8.27(4.34+0.64) +27.4%
>>   martin        : 8.80(4.36+0.62) +35.6%
>> - 3400.6: rebase a lot of unrelated changes with split-index
>>   v2.12.0     : 6.77(3.56+0.51)
>>   v2.13.0     : 4.09(2.67+0.38) -39.6%
>>   origin/next : 4.13(2.70+0.36) -39.0%
>>   martin        : 4.30(2.80+0.32) -36.5%
>>
>> And just your patch v.s. next:
>>
>> - 3400.2: rebase on top of a lot of unrelated changes
>>   origin/next : 1.22(1.06+0.06)
>>   martin      : 1.22(1.06+0.05) +0.0%
>> - 3400.4: rebase a lot of unrelated changes without split-index
>>   origin/next : 7.54(4.13+0.60)
>>   martin      : 7.75(4.34+0.67) +2.8%
>> - 3400.6: rebase a lot of unrelated changes with split-index
>>   origin/next : 4.19(2.92+0.31)
>>   martin      : 4.14(2.84+0.39) -1.2%
>>
>> It seems to be a bit slower, is that speedup worth the use of
>> unaligned access? I genuinely don't know. I'm just interested to find
>> what if anything we need to urgently fix in a release version of git.
>>
>> One data point there is that the fallback blk-sha1 implementation
>> we've shipped since 2009 has the same errors about unaligned access as
>> before your patch with -fsanitize[..], and looking at the commit
>> message this was something Linus knew about at the time, see
>> d7c208a92e ("Add new optimized C 'block-sha1' routines", 2009-08-05).
>>
>> That's strong empirical data suggesting that whatever we want to do
>> about unaligned access in the future it's not something which in
>> practice would cause wrong sha1 results for the implementation
>> shipping with v2.13.0.
>>
>> As an aside, when I was trying to apply your patch I made a mistake,
>> and found that git's test suite could run 100% OK with a bad sha1
>> implementation, I didn't apply this part (word diff):
>>
>> diff --git a/sha1dc/sha1.c b/sha1dc/sha1.c
>> index 04b104fe58..d6f4c442b5 100644
>> --- a/sha1dc/sha1.c
>> +++ b/sha1dc/sha1.c
>> @@ -312 +312 @@ static void sha1_compression_W(uint32_t ihv[5], const
>> uint32_t W[80])
>> void sha1_compression_states(uint32_t ihv[5], const
>> [-uint32_t-]{+uint8_t+} m[64], uint32_t W[80], uint32_t states[80][5])
>> @@ -1642 +1642 @@ static void sha1_recompression_step(uint32_t step,
>> uint32_t ihvin[5], uint32_t i
>> static void sha1_process(SHA1_CTX* ctx, const [-uint32_t-]{+uint8_t+} block[64])
>> diff --git a/sha1dc/sha1.h b/sha1dc/sha1.h
>> index 1d1d2b8d7c..1d181a1403 100644
>> --- a/sha1dc/sha1.h
>> +++ b/sha1dc/sha1.h
>> @@ -21 +21 @@ extern "C" {
>> void sha1_compression_states(uint32_t[5], const
>> [-uint32_t-]{+uint8_t+}[64], uint32_t[80], uint32_t[80][5]);
>
>
> That change doesnt look right anyway.
>
> The original code asserts that it will receive a pointer to 64
> uint32_t's as the second argument.
>
> The changed code asserts that it will receive a pointer to 64
> uint8_t's as the second argument.
>
> If you change the type you will need to change the *number* correspondingly.
>
> I would expect to see the uint32_t[64] to turn into uint8_t[256]

Indeed, the full change is one where "uint32_t m[16]" is changed to
"uint8_t m[64]". See Martin's patch upthread.

The word-diff I posted is in the context of my misapplying that patch
(since GMail destroyed it I manually typed in the change). That
produced "uint32_t m[16]" -> "uint32_t m[64]" instead of Martin's
version.

That's obviously incorrect and results in a broken SHA-1
implementation, but git's test suite isn't exhaustive enough that
nothing in t/ caught it, only the t/perf rebase performance test.

> I have noticed that gcc does not necessarily enforce these types of
> declarations and I believe that the change might not have any affect
> at all depending on how the pointers are being used. (C passes
> pointers on the stack, so afaik these things are more hints than
> anything else.)
>
> Looking at the code it looks like it conflates endianness with
> alignedness when they arent the same thing, except that the majority
> of little-endian boxes are x86 which do not require aligned access,
> and many big-endian boxes do require aligned access. IOW, even they
> are often related they are distinct properties.
>
> Most hash function implementations have code like the following
> (extracted and reduced from hv_macro.h in perl.git [which only
> supports little-endian hash functions]):
>
> #ifndef U32_ALIGNMENT_REQUIRED
>   #if (BYTEORDER == 0x1234 || BYTEORDER == 0x12345678)
>     #define U8TO32_LE(ptr)   (*((const U32*)(ptr)))
> #elif (BYTEORDER == 0x4321 || BYTEORDER == 0x87654321)
>     #if defined(__GNUC__) && (__GNUC__>4 || (__GNUC__==4 && __GNUC_MINOR__>=3))
>       #define U8TO32_LE(ptr)   (__builtin_bswap32(*((U32*)(ptr))))
>     #endif
>   #endif
> #endif
>
> #ifndef U8TO16_LE
>     /* Without a known fast bswap32 we're just as well off doing this */
>   #define U8TO32_LE(ptr)
> ((U32)(ptr)[0]|(U32)(ptr)[1]<<8|(U32)(ptr)[2]<<16|(U32)(ptr)[3]<<24)
> #endif
>
> Of course, in the case of SHA1 it is defined as being big-endian
> (making it a relatively poor choice for use on x86), so you would need
> to reverse a bit of this logic.
>
> Note the form shown in that last block will work regardless of
> endianness or alignedness requirements and should be optimised
> properly by most compilers into the most efficient operation.
>
> In other words, if you guys just switch to that kind of pattern this
> problem will go away everywhere, and the only issue you will have to
> consider is if it makes some oddball platforms too slow.

I think this is something Marc Stevens & co would be very interested
to hear about at
https://github.com/cr-marcstevens/sha1collisiondetection

He's CC'd here but I suspect he's not keeping up with this deluge of
E-Mails from the git project very closely, we're just using his
software as-is.

Re: Unaligned accesses in sha1dc

[Linus Torvalds]

On Fri, Jun 2, 2017 at 1:17 PM, demerphq <demerphq@gmail.com> wrote:
> Most hash function implementations have code like the following
> (extracted and reduced from hv_macro.h in perl.git [which only
> supports little-endian hash functions]):

Yes.

Please do *not* try to make things overly portable by adding random
memcpy() functions.

Yes, many compilers will do ok with it, and generate the right code
(single load from an unaligned address). But many won't. Gcc
completely screws it up in older versions on ARM, for example.

Dereferencing an unaligned pointer may be "undefined" in some
technical meaning, but it sure as hell isn't undefined in reality, and
compilers that willfully do stupid things should not be catered to
overly. Reality is a lot more important.

And I think gcc can be tweaked to use "movbe" on x86 with the right
magic incantation (ie not just __builtin_bswap32(), but also the
switch to enable the new instructions).  So having code to detect gcc
and using __builtin_bswap32() would indeed be a good thing.

                     Linus

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Linus Torvalds <torvalds@linux-foundation.org> writes:

> Dereferencing an unaligned pointer may be "undefined" in some
> technical meaning, but it sure as hell isn't undefined in reality, and
> compilers that willfully do stupid things should not be catered to
> overly. Reality is a lot more important.

Thanks for succinctly putting it this way.  I think you said the
above number of times, and I was looking for one of them to include
a reference to in the response I was preparing, but this message
made it unnecessary ;-)

> And I think gcc can be tweaked to use "movbe" on x86 with the right
> magic incantation (ie not just __builtin_bswap32(), but also the
> switch to enable the new instructions).  So having code to detect gcc
> and using __builtin_bswap32() would indeed be a good thing.

Re: Unaligned accesses in sha1dc

[Junio C Hamano]

Ævar Arnfjörð Bjarmason <avarab@gmail.com> writes:

> On Fri, Jun 2, 2017 at 4:46 PM, Liam R. Howlett <Liam.Howlett@oracle.com> wrote:
>
>> 2.13.0 is very much broken for me on SPARC.
>> {maint//git} $ make -j120
>> [...]
>> {maint//git} $ ./git log
>> [1]    1004506 bus error (core dumped)  ./git log
>>
>> This is with b06d36431 (maint).
>>
>> The same thing happens on v2.13.0-384-g826c06412 (master).
>>
>> v2.13.0-539-g4b9c06c7d (next) works for me, as did following the
>> instructions on upgrading the sha1dc code myself.
>
> Thanks a lot. So that works as I suspect on SPARC, hopefully it'll be
> in master (and 2.13.1) soon.

Thanks.  Hopefully your ab/sha1dc-maint a0103914 ("sha1dc: update
from upstream", 2017-05-20) should be sufficient for helping the
users in the real-world, then.