<chrono>: steady_clock potentially overflows

[AlexGuteniev]

Describe the bug

STL/stl/inc/chrono

Lines 616 to 618 in a83d8c0

	const long long _Whole = (_Ctr / _Freq) * period::den;
	const long long _Part = (_Ctr % _Freq) * period::den / _Freq;
	return time_point(duration(_Whole + _Part));

Line 617 causes overflow if _Ctr * period::den overflows 64 bit signed maximum, and _Freq is at least one greater than _Ctr.

Resulting _Freq that causes overflow is only 922 times greater than _Freq observed on my system. Future Windows version or future hardware may cause overflow.

Command-line test case

C:\Temp>type repro.cpp
#include <iostream>
#include <chrono>
#include <atomic>
#include <limits>


int main() {
    constexpr long long max_itermediate_value = (std::numeric_limits<long long>::max)();
    constexpr long long _Freq_max = max_itermediate_value / std::chrono::steady_clock::period::den + 1;
    constexpr long long _Freq_ovr = _Freq_max + 1;
    constexpr long long _Ctr_ovr = _Freq_ovr - 1;
    constexpr long long _Ctr_pre_ovr = _Ctr_ovr - 1;

    std::cout << _Freq_max << " is maximum _Query_perf_frequency() value not causing overflow\n\n";

    std::cout << "Otherwise with _Query_perf_frequency()=" << _Freq_ovr << " and _Query_perf_counter()=" << _Ctr_ovr <<"\n\n";

    std::cout << "The result of 'const long long _Part  = (_Ctr % _Freq) * period::den / _Freq;'\n"
        " with _Ctr=" << _Ctr_pre_ovr << " and _Freq=" << _Freq_ovr << " is:\n";

    std::cout << (_Ctr_pre_ovr % _Freq_ovr) * std::chrono::steady_clock::period::den / _Freq_ovr << "\n";

    std::cout << "The result of 'const long long _Part  = (_Ctr % _Freq) * period::den / _Freq;' \n"
        " with _Ctr=" << _Ctr_ovr << " and _Freq=" << _Freq_ovr << " is:\n";

    std::cout << (_Ctr_ovr % _Freq_ovr) * std::chrono::steady_clock::period::den / _Freq_ovr << "\n\n";

    std::cout << _Query_perf_frequency() << " is the current frequency\n"
        << "It is only " << _Freq_ovr / _Query_perf_frequency() << " times away\n";
}

C:\Temp>cl /EHsc /W4  .\repro.cpp
Microsoft (R) C/C++ Optimizing Compiler Version 19.26.28720.3 for x86
Copyright (C) Microsoft Corporation.  All rights reserved.

repro.cpp
.\repro.cpp(26): warning C4307: '*': signed integral constant overflow
Microsoft (R) Incremental Linker Version 14.26.28720.3
Copyright (C) Microsoft Corporation.  All rights reserved.

/out:repro.exe
repro.obj

C:\Temp>repro
9223372037 is maximum _Query_perf_frequency() value not causing overflow

Otherwise with _Query_perf_frequency()=9223372038 and _Query_perf_counter()=9223372037

The result of 'const long long _Part  = (_Ctr % _Freq) * period::den / _Freq;'
 with _Ctr=9223372036 and _Freq=9223372038 is:
999999999
The result of 'const long long _Part  = (_Ctr % _Freq) * period::den / _Freq;'
 with _Ctr=9223372037 and _Freq=9223372038 is:
-999999999

10000000 is the current frequency
It is only 922 times away

Expected behavior
I expect some algorithm that is robust for any values of _Freq and _Ctr. Maybe _div128 / _mul128. Maybe floating point.

STL version

• Option 1: Visual Studio version

Microsoft Visual Studio Professional 2019 Preview
Version 16.6.0 Preview 2.0

Additional context
I've tried to optimize the algorithm in PR #653 .
I assumed that the original code did not suffer from overflow, so changed would not suffer either.
But the overflow exists, and the proposed optimization changes overflow condition to a more complex but more likely condition.
So I closed that PR and reporting this issue.

[AlexGuteniev]

In practice this means, that overflow will start happening at 100 picosecond precision, or 10 GHz frequency QPF.

Currently I see 100 nanosecond precision, or 10 MHz frequency QPF on my system.

Is this valid bug? Or we hope processor counter is never going to reach that?

[AlexGuteniev]

And if the bug is invalid, that is QPF will never have resolution above 100 picoseconds, then this:

 const long long _Whole = (_Ctr / _Freq) * period::den;
 const long long _Part  = (_Ctr % _Freq) * period::den / _Freq;
 return time_point(duration(_Whole + _Part));

is likely to be superfluous, and probably should be rewritten as:

 return time_point(duration(_Ctr*period::den/_Freq));

The thing is that with 100 picosecond QPF resolution, time_point of maximum int64_t corresponds to 30 years since epoch, and with actually observed 100 nanosecond QPF resolution it corresponds to 30'000 years. A system lifecycle is shorter.

[CaseyCarter]

We discussed this during our planning meeting today, and we're not convinced that 100 picosecond period QPF is likely enough to happen in the next twenty years that we should call this a bug. @StephanTLavavej mentioned that QPC is not guaranteed to start at 0 and may therefore have a huge value even on machines that have been running for less than a decade, so we can't get away with a single multiply-and-divide.

Thanks for the analysis that went into this, and for making me learn about QPC and QPF, but for now we're going to WONTFIX this.

[AlexGuteniev]

Thanks for determining direction, but I think that discussion is not complete

we're not convinced that 100 picosecond period QPF is likely enough to happen in the next twenty years

I don't really feel like it is safe to assume that QPF frequency will not grow as real underlying counter value.
Whereas CPU frequency is not reaching 10 GHz, so even counting each CPU tick will not break it, there are different computer clocks, that already excess 10 GHz. Like, PCIe 4.0 is up to 16.0 GT/s, PCIe 5.0 is up to 32.0 GT/s, PCIe 6.0 is envisioned to be 64.0 GT/s, GT/s is GHz.

But probably it will not grow as WinAPI return value, specifically to avoid breaking STL.
Since a lot of programs already statically linked with this.

I'm suggesting that the assumption about not reaching 100 pico resolution would be documented at least here in now source. Maybe in Windows source too.

@StephanTLavavej mentioned that QPC is not guaranteed to start at 0 and may therefore have a huge value even on machines that have been running for less than a decade

As vNext improvement, counter can be rebased to zero and adding negation, this makes optimization to avoid extra division possible.
As even non-vNext, counter can be rebased the way that base is subtracted before division, but subtraction can be added later.

Non vNext version of this proposal is more non-thrivial, so may be not worth trouble, but vNext is simple enough to consider.

[AlexGuteniev]

I've updated #658 to make it explain the current resolution instead of fixing the overflow.

[AlexGuteniev]

And #653 is a way to get with one division.

[barcharcraz]

as far as I can tell PCIe doesn't have a central clock to keep track of, and you won't be counting individual "clocks" (bits) on a high speed serial bus without already knowing it may roll over. There are theoretical, and even some real, actual built CPU (more or less) designs that get past 10GHz, but they are really, really, different from what our STL runs on. Now if you are actually working on such a real machine then we would love input on getting things working. Without such a machine actually running this STL we are quite hesitant to sacrifice performance or maintainability for the ability to run on such oddball computers.

In any case, we won't fix this until we actually want to run our standard library on a platform where the overflow becomes a concern (or if the fix is literally free).

[AlexGuteniev]

@barcharcraz , I see. I now agree that the problem is not real. Anyway, Ive already changed PR #658 to explain that there are no problems, and PR #653 to make the best of the current situation.