Incorrect loop conditional

[andresag01]

I came across a problem while experimenting with MicroPython (v1.9.4). The program crashed while trying to execute this while loop:

        while (--d >= dig) {
            a = (a << DIG_SIZE) | *d;
            *d = a / base;
            a %= base;
        }

The pre-decrement (i.e. --) operation underflows the d pointer which caused the d >= dig condition to succeed (even though it shouldn't). Therefore, the line

*d = a / base

was mistakenly executed using an out-of-bounds pointer d.

[robert-hh]

The source code you are pointing at is that of today's version, 1.12.x and has at least been reformatted since Version 1.9.4. You said you have the issue with Version 1.9.4. What else can you tell about the platform you used? OS? port? Compiler type and version?

[dpgeorge]

If you can provide some Python code which show the problem (even running on v1.9.4) that would be great.

[dpgeorge]

The pre-decrement (i.e. --) operation underflows the d pointer which caused the d >= dig condition to succeed (even though it shouldn't).

By "underflows the d pointer" do you mean that d==0 before the loop and it wraps around to 0xffffffff, therefore passing the condition? That can only happen if dig itself is 0/NULL, but m_new() can never return NULL.

[andresag01]

@robert-hh @dpgeorge: I should have probably mentioned that I am a researcher experimenting with MicroPython when I came across this problem. I am working on a system that performs a lot of safety checks at run-time compared to a conventional system (like an ARM or x86). We are also using an alternative concurrent garbage collector as opposed to MicroPython's default one.

Our system handles pointers differently, and in this case, the pointer did underflow (and it wasn't ==NULL). The loop condition I showed above failed and this caused an out-of-bounds error that was caught by our system. I do not believe our system is at fault because the C standard indicates that creating a pointer to one element before the start of the array is undefined behaviour. I think that only pointers within allocated memory (or one past the end of the allocated memory) are properly defined.

Note that creating pointers one element before the start of properly allocated memory seems to occur in other places. For example, there is another case here:

    for (--idig; idig >= oidig && *idig == 0; --idig) {
    }

With regards to specific questions:

The source code you are pointing at is that of today's version, 1.12.x and has at least been reformatted since Version 1.9.4.

I havent looked what specific changes were introduced in the newer version, but I briefly compared the piece of code of interest in both versions and they seem functionally equivalent to me.

Compiler type and version?

Clang and LLVM, but I am using a custom LLVM backend.

What else can you tell about the platform you used? OS? port?

Baremetal port based off the minimal example in the ports directory. Currently running scripts directly from bytecode as the compiler is disabled.

[stinos]

the C standard indicates that creating a pointer to one element before the start of the array is undefined behaviour

Are you sure? dereferencing such pointer, ok, but creating it or comparing it or ... is not undefined behaviour right? I mean, is this undefined behaviour?

   int foo;
   int *x = &foo;
   --x;
   ++x;
   (void) *x;

The example you show works in the same way and decrements idig then compares it with odig before dereferencing it. So while it's the caller's task to make sure that doesn't happen unless the pointer actually points to something, the code by itself can be used without undefined beahviour. I think.

[andresag01]

@stinos: Fair question. I checked the C standard and this is what it says in 6.5.6.8:

When an expression that has integer type is added to or subtracted from a pointer, the
result has the type of the pointer operand. If the pointer operand points to an element of
an array object, and the array is large enough, the result points to an element offset from
the original element such that the difference of the subscripts of the resulting and original
array elements equals the integer expression. In other words, if the expression P points to
the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and
(P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of
the array object, provided they exist. Moreover, if the expression P points to the last
element of an array object, the expression (P)+1 points one past the last element of the
array object, and if the expression Q points one past the last element of an array object,
the expression (Q)-1 points to the last element of the array object. If both the pointer
operand and the result point to elements of the same array object, or one past the last
element of the array object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined. If the result points one past the last element of the array object, it
shall not be used as the operand of a unary * operator that is evaluated.

Its a long paragraph, but note the following bit:

If both the pointer
operand and the result point to elements of the same array object, or one past the last
element of the array object, the evaluation shall not produce an overflow; otherwise, the
behavior is undefined.

So I think its undefined behavior even if you do not derreference. After all, the MicroPython code is comparing something that potentially underflowed.

[stinos]

That doesn't leave much room for interpretation, so I think you're right indeed! Quite suprising that the 'one past the end' rules don't apply to 'one before the start' as well, makes me wonder when i'll finally know all of C's caveats.

[dpgeorge]

Thanks @andresag01 for the info.

I guess in the case where the standard MicroPython GC is used, m_new() and friends always return pointers which point within the big GC heap array, so it's safe to access just below any pointer returned from these functions. Pointer underflow should only be an issue on systems that have a custom m_new(), like yours.

The conditional you point out can be easily fixed (I think) by changing it to while (d-- > dig). Same should go for a lot of the other ones. The hard bit is finding them all. If you have some analysis tools that can point out all the cases then we can look at fixing them. But then ideally we'd also be able to run some CI which catches any new cases of this.

[andresag01]

@dpgeorge: Thanks for the reply.

I agree that the problem is finding all the cases to fix. So far, I have found two cases where it really became a problem in the scripts I was running: here and here. But I found other potential candidates while briefly reading through the mpz.c: here, here, here, here and in a few other places...

There are also some cases where the undefined pointer is created but never used at all (not even in a comparisons), so these have not caused me any pain.

Unfortunately, I do not have an analysis tool that I can share. I am currently using simulators specifically implemented for the experimental system that I am working on. So these are probably unsuitable for a CI system.