Making ostime_t unsigned?

[matthijskooijman]

This was previously discussed as an aside in #10, but it deserves its own issue.

I previously wrote:

Then, for something completely different but related: I noticed ostime_t is signed, but in C signed overflow is undefined, so I think that might cause compilers to misoptimize the current code in some circumstance. I already spent some time converting ostime_t to unsigned (and adding the needed casts in places where a subtraction result must be interpreted as signed again), I'll share that patch later.

And:

I've made the timestamp types unsigned in LacunaSpace/basicmac@a6ccbfb as suggested above. Seems to have no significant impact on the (size of) generated code, but should be safer (though I heard someone recently argue that the "signed overflow is undefined" is not really mandated by the C spec, it's just gcc's interpretation of it, but since we're using gcc, I guess that's what we have to deal with). This changes is pretty broad, but I think it's good.

Then @mkuyper wrote:

ostime_t signed vs. unsigned arithmetic
Yeah. I've been aware of this for a long time. Technically, signed integer overflow is UB in C. Fortunately, we can pretty much count on being on a platform that uses two's complement and that doesn't raise an exception on overflow. The other, more tricky bit is that overflow being UB means that the compiler can pretend that overflow can't occur, and optimize accordingly. The way we are using ostime_t arithmetic pretty much precludes any of these optimizations. But you definitely need to keep your fingers crossed -- or enable -fwrapv on GCC.

Changing ostime_t to signed
This is a tough one, as it is a major breaking change to the API. In principle, it feels like the right thing to do, but this will break pretty much any application code that uses the runtime and does time stamp comparisons. Some of those might generate warnings, if enabled, but not all. We might need to rename the type if we make such a fundamental change.

As a side note, while unsigned overflow is well defined in C, a cast from unsigned to signed, e.g. from ostime_t to ostimediff_t in your no-xtime branch, is implementation-defined behavior. Admittedly, that's not as bad as UB, and thanks to the ubiquity of two's complement hardware it does the right thing pretty much everywhere.

A while ago I started an effort to get rid of global state in LMiC. As part of that, I also created a clean version of the runtime without global state that also fixed the signed overflow issues and included macros for creating time deltas and doing time stamp comparisons. I'll dig that up and throw it onto GitHub, maybe that can serve as some inspiration.

And:

Here's my no-global runtime concept I mentioned earlier: https://github.com/mkuyper/rtic/blob/master/rtic.h
Note that ticks are unsigned and there are macros for comparisons making it easier to do right thing.

[matthijskooijman]

The other, more tricky bit is that overflow being UB means that the compiler can pretend that overflow can't occur, and optimize accordingly.

Exactly. I've also seen this happen in practice, though I've not seen any breakage yet (I suspect that in most cases the compiler would use this to ensure that it can just use plain addition and subtraction instructions without worrying about overflow, and those instructions typically just do the right thing for our usecase. Things are more tricky when multiplication and/or division is involved, but we don't really use those in a way that overflows anyway).

As a side note, while unsigned overflow is well defined in C, a cast from unsigned to signed, e.g. from ostime_t to ostimediff_t in your no-xtime branch, is implementation-defined behavior. Admittedly, that's not as bad as UB, and thanks to the ubiquity of two's complement hardware it does the right thing pretty much everywhere.

Good point, hadn't realized that. But in practice, all implementations chose 2-complements, I guess, so that should be guaranteed to work properly on all implementations that we'd actually use.

This is a tough one, as it is a major breaking change to the API. In principle, it feels like the right thing to do, but this will break pretty much any application code that uses the runtime and does time stamp comparisons. Some of those might generate warnings, if enabled, but not all. We might need to rename the type if we make such a fundamental change.

That's a good point, I hadn't thought about use of the type outside of BM itself. Renaming the type might not actually be enough to compile-break such application code, i.e. subtracting the result of two functions that (now) return an ostime_t would still compile then (but in practice, most of these cases would probaly store a timestamp, naming the ostime_t type, so you'd catch those with a rename).

Here's my no-global runtime concept I mentioned earlier: https://github.com/mkuyper/rtic/blob/master/rtic.h

Looks nice and clean :-)

When doing the conversion to unsigned, I also considered adding macros (or maybe nicer to use inline functions) for comparisons, to reduce the chance of messing up the needed type conversions, but ended up keeping things simple. Might still be good, though.

Maybe a compromise could be to, at least for now, keep ostime_t signed, but introduce a macro like your rtic_diff which actually casts its parameters to unsigned before doing the subtraction, which would (AFAICS) also fix the undefined behavior. Any application code that does not use this macro yet is still "vulnerable", but can be easily fixed by switching to the macro. Maybe also already introduce an alternative type name for unsigned ticks and recommend applications to use that to store timestamps. Then after applications have had some chance to be converted to use the new type and macro, we can remove the old osticks_t type and change all APIs to use the new type, which will be seamless for updated applications and breaks compilation (rather than runtime) for non-updated applications?