mbedtls_mpi_self_test fails with llvm 12.0-rc1 on amd64

[z-rui]

Bug

OS
linux

mbed TLS build:
Version: 2.7.18
Configuration: default
Compiler and options (if you used a pre-built binary, please indicate how you obtained it): LLVM 12.0-rc1

Expected behavior

  MPI test #1 (mul_mpi): passed
  MPI test #2 (div_mpi): passed
  MPI test #3 (exp_mod): passed
  MPI test #4 (inv_mod): passed
  MPI test #5 (simple gcd): passed

Actual behavior

  MPI test #1 (mul_mpi): passed
  MPI test #2 (div_mpi): passed
  MPI test #3 (exp_mod): failed
Unexpected error, return code = 00000001

Steps to reproduce

1. Unpack mbedtls-2.7.18 source code
2. Under library directory, create a file main.c:

extern int mbedtls_mpi_self_test( int verbose );
int main()
{
	return mbedtls_mpi_self_test(1);
}

3. run

clang-12 -O3 -I ../include/ bignum.c main.c
./a.out

4. The test fails.

Comments
The problem only occurs with -O3. It seems to be related to the following code fragment in bignum.c:

    for( i = 0; i < n; i++ )
    {
        /*
         * T = (T + u0*B + u1*N) / 2^biL
         */
        u0 = A->p[i];
        u1 = ( d[0] + u0 * B->p[0] ) * mm;

        mpi_mul_hlp( m, B->p, d, u0 );
        mpi_mul_hlp( n, N->p, d, u1 );

        *d++ = u0; d[n + 1] = 0;
    }

The compiler reorders u1 = ( d[0] + u0 * B->p[0] ) * mm; and mpi_mul_hlp( m, B->p, d, u0 );. It believes the reordering is valid because it thinks the latter doesn't affect any dependencies of the former, which is false, because mpi_mul_hlp will alter the values in d[]. However, the inline assembly of mpi_mul_hlp for amd64 doesn't indicate that it may alter the values in d[]. If I make a change in bn_mul.h:

 #define MULADDC_STOP                        \
-        : "+c" (c), "+D" (d), "+S" (s)      \
+        : "+c" (c), "+mD" (d), "+S" (s)      \
         : "b" (b)                           \
         : "rax", "rdx", "r8"                \
     );

Then the test no longer fails.

[hanno-becker]

Thanks a lot @z-rui for finding and reporting this, it's an exemplary issue 👍 We will look into this.

As for the proposed solution: Don't we need a memory clobber here to tell the compiler that the memory at d may change?

[gilles-peskine-arm]

@hanno-arm These days we use the absence of labels to keep track of untriaged issues, so please don't apply a label if you aren't doing the full triage (including prioritization).

I'm removing the "bug" label for now. I agree that it's a bug, and we'll reapply the label, but we also need to decide whether how to prioritize it, given that the only compiler that seems to make this optimization is a beta version. I can't promise that the fix will be merged in time for the last release of the 2.7 series which is scheduled for mid-March.

For information, I've reproduced this locally with Clang 12 from http://apt.llvm.org/focal/ at 12.0.0-++20210206062921+716eef9ad5b3-1exp120210206053625.18, but not with Clang 11 or earlier.

[gilles-peskine-arm]

Prioritization: we'll prioritize fixing the known issue with Clang 12 so that it can be included in the next release. The goal of this task is to pass the unit tests with clang 12. A broader review of potential issues with the assembly code is out of scope here.