From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mail-yb1-xb2e.google.com (mail-yb1-xb2e.google.com [IPv6:2607:f8b0:4864:20::b2e]) by sourceware.org (Postfix) with ESMTPS id 0898D3858D32; Sat, 18 Nov 2023 11:07:48 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 0898D3858D32 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=gmail.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gmail.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 0898D3858D32 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=2607:f8b0:4864:20::b2e ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700305671; cv=none; b=Csa1c8vn9zyC14O45uDgvYVWAUsjyxcCb2sau4m7EEXpIHfc1wq9+LaA4NkusICrkPv0jIXrModUZjYZO8pGXF6dg81u2nYCesJdmZwHhQlbhXWyxPpJnWypQJV//6AV/oQVeyY1rGH4/x4+066PawM9FVZ4UyhxB/YhoOfKX68= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1700305671; c=relaxed/simple; bh=k3utmxO5FqceCeNOuI6x5P8hOG3yC0SHxV6ScAy8jDY=; h=DKIM-Signature:MIME-Version:From:Date:Message-ID:Subject:To; b=S+OVrZC4VzzBOHUJLbCvsJZDIxENnXFF2eYENTQuq5CakpuxWz1B3ag5Aj/WAYOUQ4x7BWvuY5ga5Jafh5mPmaAwE6JooUcc7YFdrhFyeAcDfxHu5vKtNv1Eu0MWCxnzgKEFE94JZbP8fhbZhP5bjjCHBxJ0p9m4ZeP7AGQeUyI= ARC-Authentication-Results: i=1; server2.sourceware.org Received: by mail-yb1-xb2e.google.com with SMTP id 3f1490d57ef6-daf2eda7efaso2858324276.0; Sat, 18 Nov 2023 03:07:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20230601; t=1700305666; x=1700910466; darn=gcc.gnu.org; h=to:subject:message-id:date:from:reply-to:in-reply-to:references :mime-version:from:to:cc:subject:date:message-id:reply-to; bh=RbDKoG8SezrAHBGalAiiSsc0XH53QrCV5g02Y33guPA=; b=FgEvsw6RCYMpG57lLyj8rfr/yebzDtxkYBizraa3qYTonETnBd+Y00Uc+0XZ/Ca8Bp Y1PFpZQVmiWBmuU9+bX2f3bBUaqlMVI8Khs2CO9mUHR1RitvqDLrhgPLW2FKIFFhzWoF Id2+0e1nATT1eAw1yKUEpdC8ivkTQmSZvS117mAeCByO/REtGqLFVc6s/6G8y3RmMoqm 1p5onTLugXdLgpN8XC8QB7oS6Ao8QTKXmZg69A1nTZsaBvh+v5SzCtsy5JxpRLSd3va3 j5HSwc0NVmtCp7nqbo9m2fp0TZbnTJPe6olsg/mvhuUycG0hSJe7mxdHQ9ExjGNB2tsh msvg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20230601; t=1700305666; x=1700910466; h=to:subject:message-id:date:from:reply-to:in-reply-to:references :mime-version:x-gm-message-state:from:to:cc:subject:date:message-id :reply-to; bh=RbDKoG8SezrAHBGalAiiSsc0XH53QrCV5g02Y33guPA=; b=lnkWmWUtsSAFFcQd8uAfGythHKc+jSnZB8Xn7ErTtDP6p+P08svyPiJk+Fr35vxPtW nMFeYDKcyZFGNhV145Q/Ya99CVd9E/3SnmW6BfNgyX5DXsOnD4GbmGxREBwv/3YDQO8j pL/VUe5y7J/oYkZigpfbAsU+hGkpHpNaBMjLJjvNV/yiCTqfTkSR9/RLE/iuY4HI+w6W LQQ2LiuEATNN7VHgUi7CrNHqvqvylRtqRs8jdJBN4fO+xUa4d1DXKI+M6PRXdC+pkUZQ ekxIWc+KgnTT5Xe8LxbnI7cN5q+aRdTYoP2+t8cJI4PBxl4kE4pNg8koTMnwC6MVtQbb dmqQ== X-Gm-Message-State: AOJu0YxnRuBXizQDc5EoUb0vJpn5QGd5A7W5KFerMH/pNEjGrwEaRr/W ORJf7ExUo9WNHYbaPrJ2HbYXF9BS2ntwfhLJUE0ac0aG X-Google-Smtp-Source: AGHT+IFgF9gZjAP+ypkH0LhxkIbABTwPrK2HEObuu2+wrH1WGwzBD6q0e1MWx2GIP6K42TxER/P4n6Gc9VfVLUBtUlc= X-Received: by 2002:a25:8487:0:b0:d9a:4839:68fe with SMTP id v7-20020a258487000000b00d9a483968femr2180126ybk.43.1700305665751; Sat, 18 Nov 2023 03:07:45 -0800 (PST) MIME-Version: 1.0 References: <20231118000653.6924-1-cassio.neri@gmail.com> <20231118001932.8033-1-cassio.neri@gmail.com> In-Reply-To: <20231118001932.8033-1-cassio.neri@gmail.com> Reply-To: cassio.neri@gmail.com From: Cassio Neri Date: Sat, 18 Nov 2023 11:07:33 +0000 Message-ID: Subject: Re: [PATCH v3] libstdc++: Remove UB from operator+ of months and weekdays. To: "libstdc++" , Gcc-patches Content-Type: multipart/alternative; boundary="0000000000003780fc060a6b4388" X-Spam-Status: No, score=-8.6 required=5.0 tests=BAYES_00,DKIM_SIGNED,DKIM_VALID,DKIM_VALID_AU,DKIM_VALID_EF,FREEMAIL_FROM,GIT_PATCH_0,HTML_MESSAGE,RCVD_IN_DNSWL_NONE,SPF_HELO_NONE,SPF_PASS,TXREP,T_SCC_BODY_TEXT_LINE autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org List-Id: --0000000000003780fc060a6b4388 Content-Type: text/plain; charset="UTF-8" Actually, disregard this patch. I'm preparing a better one which also tackles UB in month - months{INT_MIN} weekday - days{INT_MIN} Best wishes, Cassio. On Sat, 18 Nov 2023, 00:19 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 problem is that in libstdc++ days::rep is int64_t. Other > implementations use int32_t and cast operands to int64_t. Hence then > perform > arithmetic operations without fear of overflowing. For instance, #1 > evaluates: > > modulo(static_cast(unsigned{x}._M_wd) + __y.count(), 7); > > For x86-64, long long is int64 so the cast is useless. For #2, casting to > a > larger type could help but all implementations follow the Standard's > "Returns > clause" and evaluate: > > modulo(static_cast(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(unsigned{__x}) + 11 + __y.count(), 12); > > Again, this is not possible for libstdc++. The fix uses this new function: > > template > 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); > > 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. > --- > > Changes with respect to previous versions: > v3: Fix screwed up email send with v2. (Sorry about that. I shall learn at > some point.) > v2: Replaced _T with _Tp and _U with _Up. Removed copyright+license from > test. > > libstdc++-v3/include/std/chrono | 61 ++++++++++++-------- > libstdc++-v3/testsuite/std/time/month/1.cc | 9 +++ > libstdc++-v3/testsuite/std/time/month/2.cc | 30 ++++++++++ > libstdc++-v3/testsuite/std/time/weekday/1.cc | 8 +++ > libstdc++-v3/testsuite/std/time/weekday/2.cc | 30 ++++++++++ > 5 files changed, 114 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..691bb106bb9 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(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>(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 > constexpr unsigned > - __modulo(long long __n, unsigned __d) > - { > - if (__n >= 0) > - return __n % __d; > - else > - return (__d + (__n % __d)) % __d; > + __add_modulo(unsigned __x, _Tp __y) > + { > + using _Up = make_unsigned_t<_Tp>; > + // For __y >= 0, _Up(__y) has the same mathematical value as __y > and > + // this function simply returns (__x + _Up(__y)) % d. Typically, > this > + // doesn't overflow since the range of _Up contains many more > positive > + // values than _Tp's. For __y < 0, _Up(__y) has a mathematical > value in > + // the upper-half range of _Up so that adding a positive value to > it > + // might overflow. Moreover, most likely, _Up(__y) != __y mod d. > To > + // fix both issues we from _Up(__y)"subtract" an __offset >= > + // 255 + d - 1 to make room for the addition to __x and shift the > modulo > + // to the correct value. > + auto constexpr __a = _Up(-1) - _Up(255 + __d - 2); > + auto constexpr __b = _Up(__d * (__a / __d) - 1); > + // Notice: b <= a - 1 <= _Up(-1) - _Up(255 + d - 1) and b % d = d > - 1. > + auto const __offset = __y >= 0 ? _Up(0) : __b - _Up(-1); > + return (__x + _Up(__y) + __offset) % __d; > } > > inline constexpr unsigned __days_per_month[12] > @@ -700,8 +720,10 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > friend constexpr month > operator+(const month& __x, const months& __y) noexcept > { > - auto __n = static_cast(unsigned{__x}) + (__y.count() - > 1); > - return month{__detail::__modulo(__n, 12) + 1}; > + // modulo(x + (y - 1), 12) = modulo(x + (y - 1) + 12, 12) > + // = modulo((x + 11) - y, 12) > + return month{1 + __detail::__add_modulo<12>( > + unsigned{__x} + 11, __y.count())}; > } > > friend constexpr month > @@ -930,15 +952,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > static constexpr weekday > _S_from_days(const days& __d) > { > - using _Rep = days::rep; > - using _URep = make_unsigned_t<_Rep>; > - const auto __n = __d.count(); > - const auto __m = static_cast<_URep>(__n); > - > - // 1970-01-01 (__n = 0, __m = 0 ) -> Thursday (4) > - // 1969-31-12 (__n = -1, __m = _URep(-1)) -> Wednesday (3) > - const auto __offset = __n >= 0 ? _URep(4) : 3 - _URep(-1) % 7 - 7; > - return weekday((__m + __offset) % 7); > + return weekday{__detail::__add_modulo<7>(4, __d.count())}; > } > > public: > @@ -1028,8 +1042,7 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION > friend constexpr weekday > operator+(const weekday& __x, const days& __y) noexcept > { > - auto __n = static_cast(__x._M_wd) + __y.count(); > - return weekday{__detail::__modulo(__n, 7)}; > + return weekday{__detail::__add_modulo<7>(__x._M_wd, __y.count())}; > } > > friend constexpr weekday > diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc > b/libstdc++-v3/testsuite/std/time/month/1.cc > index 773f772bf07..f72a4ab9a5d 100644 > --- a/libstdc++-v3/testsuite/std/time/month/1.cc > +++ b/libstdc++-v3/testsuite/std/time/month/1.cc > @@ -20,6 +20,7 @@ > // Class template day [time.cal.month] > > #include > +#include > > constexpr void > constexpr_month() > @@ -71,4 +72,12 @@ constexpr_month() > static_assert(month{0} <=> month{1} == std::strong_ordering::less); > static_assert(month{3} <=> month{3} == std::strong_ordering::equal); > static_assert(month{5} <=> month{2} == std::strong_ordering::greater); > + > + auto constexpr months_min = > months{std::numeric_limits::min()}; > + auto constexpr m0_min = month{ 0 } + months_min; > + auto constexpr m255_min = month{255} + months_min; > + > + auto constexpr months_max = > months{std::numeric_limits::max()}; > + auto constexpr m0_max = month{ 0 } + months_max; > + auto constexpr m255_max = month{255} + months_max; > } > 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..85895949e4e > --- /dev/null > +++ b/libstdc++-v3/testsuite/std/time/month/2.cc > @@ -0,0 +1,30 @@ > +// { dg-do run { target c++20 } } > + > +// Class month [time.cal.month] > + > +#include > +#include > +#include > + > +using namespace std::chrono; > + > +void test_extreme_values(months extreme) > +{ > + for (unsigned m = 0; m < 254; ++m) > + { > + auto const m1 = month{ m } + extreme; > + auto const m2 = month{m + 1} + extreme; > + > + auto const u1 = unsigned{m1}; > + auto const u2 = unsigned{m2}; > + > + VERIFY(u1 == 12 ? u2 == 1 : u2 == u1 + 1); > + } > +} > + > +int main() > +{ > + test_extreme_values(months{std::numeric_limits::max()}); > + test_extreme_values(months{std::numeric_limits::min()}); > + return 0; > +} > diff --git a/libstdc++-v3/testsuite/std/time/weekday/1.cc > b/libstdc++-v3/testsuite/std/time/weekday/1.cc > index e89fca47d4b..cc8b0db78f8 100644 > --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc > +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc > @@ -107,4 +107,12 @@ constexpr_weekday() > static_assert(weekday{7} == weekday{0}); > static_assert(!(weekday{0} == weekday{1})); > static_assert( (weekday{0} != weekday{2})); > + > + auto constexpr days_min = days{std::numeric_limits::min()}; > + auto constexpr wd0_min = weekday{ 0 } + days_min; > + auto constexpr wd255_min = weekday{255} + days_min; > + > + auto constexpr days_max = days{std::numeric_limits::max()}; > + auto constexpr m0_max = weekday{ 0 } + days_max; > + auto constexpr m255_max = weekday{255} + days_max; > } > diff --git a/libstdc++-v3/testsuite/std/time/weekday/2.cc > b/libstdc++-v3/testsuite/std/time/weekday/2.cc > new file mode 100644 > index 00000000000..82284976152 > --- /dev/null > +++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc > @@ -0,0 +1,30 @@ > +// { dg-do run { target c++20 } } > + > +// Class weekday [time.cal.wd] > + > +#include > +#include > +#include > + > +using namespace std::chrono; > + > +void test_extreme_values(days extreme) > +{ > + for (unsigned d = 0; d < 254; ++d) > + { > + auto const m1 = weekday{ d } + extreme; > + auto const m2 = weekday{d + 1} + extreme; > + > + auto const u1 = m1.c_encoding(); > + auto const u2 = m2.c_encoding(); > + > + VERIFY(u1 == 6 ? u2 == 0 : u2 == u1 + 1); > + } > +} > + > +int main() > +{ > + test_extreme_values(days{std::numeric_limits::max()}); > + test_extreme_values(days{std::numeric_limits::min()}); > + return 0; > +} > -- > 2.41.0 > > --0000000000003780fc060a6b4388--