[PATCH] libstdc++: Remove UB from operator+ of months and weekdays.

[Jonathan Wakely]

On Fri, 17 Nov 2023 at 01:34, Cassio Neri wrote:
>
> The following functions invoke signed integer overflow (UB) for some extreme
> values of days and months [1]:
>
>   weekday operator+(const weekday& x, const days& y); // #1
>   month operator+(const month& x, const months& y);   // #2
>
> For #1, the crux of the problem is that, in libstdc++, days::rep is int64_t.
> Other implementations use int32_t and cast operands to int64_t and perform
> arithmetic operations without fear of overflowing. For instance, #1 evaluates:
>
>   modulo(static_cast<long long>(unsigned{x}._M_wd) + __y.count(), 7);
>
> Sadly, libstdc++ doesn't have this luxury.  For #2, casting to a larger type
> could help but all implementations follow the Standard's "Returns clause"
> and evaluate:
>
>    modulo(static_cast<long long>(unsigned{__x}) + (__y.count() - 1), 12);
>
> Hence, overflow occurs when __y.count() is the minimum value of its type.  When
> long long is larger than months::rep, this is a fix:
>
>    modulo(static_cast<long long>(unsigned{__x}) + 11 + __y.count(), 12);
>
> Again, this is not possible for libstdc++. To fix these UB, this patch
> implements:
>
>   template <unsigned __d, typename _T>
>   unsigned __add_modulo(unsigned __x, _T __y);
>
> which returns the remainder of Euclidean division of __x +__y by __d without
> overflowing.  This function replaces
>
>   constexpr unsigned __modulo(long long __n, unsigned __d);
>
> which also calculates the reminder but takes the sum __n as argument at which
> point the overflow might have already occurred.
>
> In addition to solve the UB issues, __add_modulo allows shorter branchless code
> on x86-64 and ARM [2].
>
> [1] https://godbolt.org/z/WqvosbrvG
> [2] https://godbolt.org/z/o63794GEE
>
> libstdc++-v3/ChangeLog:
>
>         * include/std/chrono: Fix operator+ for months and weekdays.
>         * testsuite/std/time/month/1.cc: Add constexpr tests against overflow.
>         * testsuite/std/time/month/2.cc: New test for extreme values.
>         * testsuite/std/time/weekday/1.cc: Add constexpr tests against overflow.
>         * testsuite/std/time/weekday/2.cc: New test for extreme values.
> ---
>
> If desirable, I think I'm able to do something similar for operator-(x, y)
> (month/weekday x and months/days y) which is specified as:
>     Returns: x + -y;
> All implementations follow the above and -y overflows when y has the minimum
> value of its type.

I'm not sure we need to care about wday - days(INT_MIN), that seems
pretty unlikely to happen except in test suites.

I suppose somebody could use the minimum value as a placeholder for
"invalid value" and then forget to check for it before doing the
arithmetic.

More comments below ...

>
>  libstdc++-v3/include/std/chrono              | 61 ++++++++++++--------
>  libstdc++-v3/testsuite/std/time/month/1.cc   |  9 +++
>  libstdc++-v3/testsuite/std/time/month/2.cc   | 47 +++++++++++++++
>  libstdc++-v3/testsuite/std/time/weekday/1.cc |  8 +++
>  libstdc++-v3/testsuite/std/time/weekday/2.cc | 47 +++++++++++++++
>  5 files changed, 148 insertions(+), 24 deletions(-)
>  create mode 100644 libstdc++-v3/testsuite/std/time/month/2.cc
>  create mode 100644 libstdc++-v3/testsuite/std/time/weekday/2.cc
>
> diff --git a/libstdc++-v3/include/std/chrono b/libstdc++-v3/include/std/chrono
> index 10bdd1c4ede..02087a9374c 100644
> --- a/libstdc++-v3/include/std/chrono
> +++ b/libstdc++-v3/include/std/chrono
> @@ -497,18 +497,38 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION
>
>      namespace __detail
>      {
> -      // Compute the remainder of the Euclidean division of __n divided by __d.
> -      // Euclidean division truncates toward negative infinity and always
> -      // produces a remainder in the range of [0,__d-1] (whereas standard
> -      // division truncates toward zero and yields a nonpositive remainder
> -      // for negative __n).
> +      // Compute the remainder of the Euclidean division of __x + __y divided by
> +      // __d without overflowing.  Typically, __x <= 255 + d - 1 is sum of
> +      // weekday/month and an offset in [0, d - 1] and __y is a duration count.
> +      // For instance, [time.cal.month.nonmembers] says that given month x and
> +      // months y, to get x + y one must calculate:
> +      //
> +      // modulo(static_cast<long long>(unsigned{x}) + (y.count() - 1), 12) + 1.
> +      //
> +      // Since y.count() is a 64-bits signed value the subtraction y.count() - 1
> +      // or the addition of this value with static_cast<long long>(unsigned{x})
> +      // might overflow.  This function can be used to avoid this problem:
> +      //     __add_modulo<12>(unsigned{x} + 11, y.count()) + 1;
> +      // (More details in the implementation of operator+(month, months).)
> +      template <unsigned __d, typename _T>
>        constexpr unsigned
> -      __modulo(long long __n, unsigned __d)
> -      {
> -       if (__n >= 0)
> -         return __n % __d;
> -       else
> -         return (__d + (__n % __d)) % __d;
> +      __add_modulo(unsigned __x, _T __y)
> +      {
> +       using _U = make_unsigned_t<_T>;

We need to use _Tp and _Up here to avoid clashing with libc ctype constants, see
https://gcc.gnu.org/onlinedocs/libstdc++/manual/source_code_style.html#coding_style.bad_identifiers

> diff --git a/libstdc++-v3/testsuite/std/time/month/2.cc b/libstdc++-v3/testsuite/std/time/month/2.cc
> new file mode 100644
> index 00000000000..c53c5a2fc6f
> --- /dev/null
> +++ b/libstdc++-v3/testsuite/std/time/month/2.cc
> @@ -0,0 +1,47 @@
> +// { dg-do run { target c++20 } }
> +
> +// Copyright (C) 2020-2023 Free Software Foundation, Inc.

New files should have just 2023 as the copyright year, or leave the
copyright+license header off completely for trivial tests. I don't
bother with it these days. IMO there's no original idea being put to
use in tests like this, just fairly dull, repetitive operations
exercising the API.