Use of C++ undefined behavior in various `IteratorComparators` #19496

Expected behavior

All C++ code to be 100% using legal C++ and not UB which can lead to subtle bugs if not now, then perhaps in the future.

Actual behavior

Use of undefined behavior in at least two places:

• https://github.com/bitcoin/bitcoin/blob/42fe6aad326f62c7e6ea12ee873149257f67ce5d/src/net_processing.cpp#L227
• https://github.com/bitcoin/bitcoin/blob/42fe6aad326f62c7e6ea12ee873149257f67ce5d/src/miner.h#L67

Background

Please see this part of the C++ specification: https://en.cppreference.com/w/cpp/language/operator_comparison

In particular I will quote the relevant section here:

If two pointers are not specified to compare greater or compare equal, the result of the comparison is unspecified. The result may be nondeterministic, and need not be consistent even for multiple evaluations of the same expression with the same operands in the same execution of the program:

int x, y;
 
bool f(int* p, int* q) { return p < q; }
 
assert(f(&x, &y) == f(&x, &y)); // may fire in a conforming implementation

Note that in the above-linked section (which I admit is difficult to decipher) -- pointers are only specified to have a legal < or > comparison operations if the objects they point to either belong to the same array, or if the objects they point to live basically as members in the same object (i.e. as class members). This is unlike in C. The code will compile.. it will run -- but like the above section states, and the above sample program illustrates -- the results may be non-deterministic!

In practice it appears the code works in bitcoin for all known compilers and platforms -- but is not guaranteed to do so forever and may lead to subtle bugs in the future as compilers evolve or as libstdc++ evolves.

Is this one of those cases where std::less is more? :)

Ha ha ha 😄

No, I don't believe so. :) (The iterators in question don't define operator< .. one would have to actually examine the underlying .first perhaps and do < on those...)

I am not convinced this is UB.

Pointer comparison of objects that are not in the same array (or one past it) is unspecified in C++, not undefined. This means the compiler can choose whatever it likes about the order of the two objects, but it's one or the other, and cannot do anything else.

However, there is no guaranteed total ordering on unrelated pointers. This means that while not UB, the code in IteratorComparator may in theory not do what it's intended to do. E.g. a<b and b<a might both be simultaneously true.

I'm not sure if this is what @practicalswift was alluding to, but std::less (and friends) when specialized to any given pointer type is a well defined total ordering, even when < etc are not.

So it seems that to be fully compliant, it is sufficient to replace < with std::less in these sorts of operations.

@sipa

This means that while not UB, the code in IteratorComparator may in theory not do what it's intended to do. E.g. a<b and b<a might both be simultaneously true.

I'm not sure if this is what @practicalswift was alluding to, but std::less (and friends) when specialized to any given pointer type is a well defined total ordering, even when < etc are not.

So it seems that to be fully compliant, it is sufficient to replace < with std::less in these sorts of operations.

Exactly! That's why std::less is more :)

Hmm. In theory std::less is supposed to be a demarcation point where the compiler's optimizer "lays off" with the assumptions -- there are known bugs in GCC for example (many gcc stdlibcc++'s just default to < anyway without any magic given to the optimizer). The problem is not all compilers do the right thing with std::less.. it's not easy. Here is a relevant blog post about this from 2016 that is quite informative: https://quuxplusone.github.io/blog/2019/01/20/std-less-nightmare/

But yes.. it does appear that std::less is more.. as @practicalswift originally asserted. At least in theory. :/

There be dragons here...

@cculianu

Nice find BTW and thanks for reporting!

May I ask how you found this case? Static analysis?

Nit: Perhaps "undefined behaviour" in the title could be replaced with "unspecified behaviour" in order to not confuse readers?

The subtle differences between undefined, unspecified and implementation-defined in the C++ standard:

• undefined behavior: "behavior, upon use of a nonportable or erroneous program construct or of erroneous data, for which this International Standard imposes no requirements."
• unspecified behavior: "use of an unspecified value, or other behavior where this International Standard provides two or more possibilities and imposes no further requirements on which is chosen in any instance"
• implementation-defined behavior: "unspecified behavior where each implementation documents how the choice is made"

Nice find BTW and thanks for reporting! @practicalswift -- My pleasure. You guys have a lot of influence on what happens in to the Bitcoins* (what BTC people refer to as altcoins such as Bitcoin Cash, Bitcoin SV, Bitcoin Gold, etc) -- so Core software being top notch impacts us all.

May I ask how you found this case? Static analysis?

Ha -- strangely the free static analyzers didn't catch this. I do have a PVS Studio license -- I should try that and see if it catches it. No.. I used "Eyeball analysis". I'm maintaining a downstream version of your code -- I work for the Bitcoin Cash Node project. So -- we have a lot of similarities in terms of large parts of the system. I initially found this in our software then went to the source (you guys) to discuss it.

As for the delineation between UB vs. unspecified -- I'll leave it up to you. I am not exactly sure either here without reading the "standardese" more carefully. If you like I can modify the title of this issue or you can as well without objection.

The problem is not all compilers do the right thing with std::less

Not sure what to do here then. For now the current code happens to work for some reason and when changing to std::less doesn't give additional checks, then it might be best to leave the code as is? Or just change to std::less and treat it as upstream bug if something goes wrong?

This issue hasn’t attracted much interest from other contributors in quite some time.

Given that, it doesn’t seem important enough to keep open indefinitely. I’m going to close it for now due to lack of activity, but pull requests or renewed discussion are always welcome.

Comment here if you think this shoudl be re-opened.

This was fixed in e009bf681c0e38a6451afa594ba3c7c8861f61c3 , no?