From patchwork Fri Jan 5 10:24:33 2024 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Jonathan Wakely X-Patchwork-Id: 185359 Return-Path: Delivered-To: ouuuleilei@gmail.com Received: by 2002:a05:7301:6f82:b0:100:9c79:88ff with SMTP id tb2csp6159860dyb; Fri, 5 Jan 2024 03:31:46 -0800 (PST) X-Google-Smtp-Source: AGHT+IH0M+te2oOSBFG+w0t7WUHHl7O8OUyucYEi40i8i2oFVoGHLdPbqGEWA9ZK2fab+pJphfGZ X-Received: by 2002:a05:6214:250e:b0:680:9cb:344e with SMTP id gf14-20020a056214250e00b0068009cb344emr1903743qvb.21.1704454305792; Fri, 05 Jan 2024 03:31:45 -0800 (PST) ARC-Seal: i=2; a=rsa-sha256; t=1704454305; cv=pass; d=google.com; s=arc-20160816; b=jSJu1THek0p9DpE8hhYfq0uyEB55ecnFNvP1M+SSlEkqCxr3V90WeHUSxjyOAlpGUV Ykw2Bm+0o436qQjufsdIUtGp51t5WP+/VqZJjk616dxoodXoV4kcGOjGvbVM7PR1UUvT M4Meg4z/15a/t7wbMeHlqJ7WPyheTS0jfBo2w0bM5VY0O61iMU/PaZHaffV516qNiGpu d3HuRin80YdyJwQG6foIB16OgA4+jVUe4wuAiMSxv+EliTtgA0BCfj93gtuSvSPP9Slb P+CD1iIwLCOZQLhS5ixHVO+aNqBRb4W/UjLzbYxc8n11QhURkSSx/pBOYjruj0rV0YIW kp1Q== ARC-Message-Signature: i=2; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=errors-to:list-subscribe:list-help:list-post:list-archive :list-unsubscribe:list-id:precedence:content-transfer-encoding :mime-version:message-id:date:subject:cc:to:from:dkim-signature :arc-filter:dmarc-filter:delivered-to; bh=fwwVm+7p0gwQxoxGGku1IaBux4pFzu55rA+XX9joPzs=; fh=pZHFs+1cULgthMGKwVRmhEJYjHKwLLqMcqgibbiOqPs=; b=Ail2+XpB4pcKVOS9lOk3aog+1GkTL3iAqfbOMnCHt5QXJQxxi85c2C5R0SSte1qVWS wHqwsMBo/aHnhJn0p+9EHK6zFUcHjfk4tiilwyrBO1mFPdwUqkJnCofjghR1mKxfLl6b CtPP7mu83r3s3hHQBH/9DXfYo0/8IMQZLybKpKBpGpBByIvyv6hFN/daE89RUBi6A5o7 4p3F07JnWvcQFehWCVl5jtAPa684FWOf3lJ3ynuNbVKd3WZTcJFXfacPwJBrQdQbHtuV GYvbYerzB9W2FfWLoAaaK63s/la6721P8DUFXtPUfm8QJ+ehXHvgf55PTydLnLGSxdcG aOtQ== ARC-Authentication-Results: i=2; mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=gwJ9Oa0E; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (server2.sourceware.org. [2620:52:3:1:0:246e:9693:128c]) by mx.google.com with ESMTPS id j14-20020a0cf30e000000b0067f6151c9dcsi1534246qvl.140.2024.01.05.03.31.45 for (version=TLS1_3 cipher=TLS_AES_256_GCM_SHA384 bits=256/256); Fri, 05 Jan 2024 03:31:45 -0800 (PST) Received-SPF: pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) client-ip=2620:52:3:1:0:246e:9693:128c; Authentication-Results: mx.google.com; dkim=pass header.i=@redhat.com header.s=mimecast20190719 header.b=gwJ9Oa0E; arc=pass (i=1); spf=pass (google.com: domain of gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org designates 2620:52:3:1:0:246e:9693:128c as permitted sender) smtp.mailfrom="gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org"; dmarc=pass (p=NONE sp=NONE dis=NONE) header.from=redhat.com Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id C6F25386189E for ; Fri, 5 Jan 2024 10:28:33 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTPS id 52E003858D32 for ; Fri, 5 Jan 2024 10:25:19 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 52E003858D32 Authentication-Results: sourceware.org; dmarc=pass (p=none dis=none) header.from=redhat.com Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=redhat.com ARC-Filter: OpenARC Filter v1.0.0 sourceware.org 52E003858D32 Authentication-Results: server2.sourceware.org; arc=none smtp.remote-ip=170.10.133.124 ARC-Seal: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704450323; cv=none; b=CRW4x55titnDi9vfF1XiebSITYQWLD3Z86lpJgxEbH7bJOpmvwOX9+0Do7oFLW9PVBmGFDhzpPqKi7DldYZLSs3hLS/9vMtcBEft0OEhsgUXqL3Jua5ZIATcQEbTa8Bn6PYD6+CzUJBLtWjjyZdb/21g4qkhhRRhuISyLXyV4FA= ARC-Message-Signature: i=1; a=rsa-sha256; d=sourceware.org; s=key; t=1704450323; c=relaxed/simple; bh=Mjm4/w4ScRe4VufakDERkwTlGXeHrRk6qKVN9q1v5Fo=; h=DKIM-Signature:From:To:Subject:Date:Message-ID:MIME-Version; b=U7bDdYy6m8bS/SCEAwMGpo0DGt8nOG7KldbQpMYTRUj2yYPzEcSA1qrNULT66TQD35N9yOTy57ohSJkmWa/MBEKAPKFZWZ6k7GMkCIxeU/xVdcSI+K74Mo14+t3V3SafpZ6qebOfdkgMrMlHE7oc57DxMvZfWEJTdBjVZkcA0v4= ARC-Authentication-Results: i=1; server2.sourceware.org DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=redhat.com; s=mimecast20190719; t=1704450319; h=from:from:reply-to:subject:subject:date:date:message-id:message-id: to:to:cc:cc:mime-version:mime-version:content-type:content-type: content-transfer-encoding:content-transfer-encoding; bh=fwwVm+7p0gwQxoxGGku1IaBux4pFzu55rA+XX9joPzs=; b=gwJ9Oa0EQXGa+Oo5lDrE7kN2RI7Wpl6oOuwxlWE00apbYsPNkIaPomjer3bQ1LRVp5yzth bGXeoRSzkPX/vwHDANtVGBvdiXK8Tg/aUCajipIJPDP4tm+aIgByZZm3dw692GGgiFNAPo 7RJ2qc3z5p8QEfnXD0gk9cPjjKxr7n0= Received: from mimecast-mx02.redhat.com (mx-ext.redhat.com [66.187.233.73]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.3, cipher=TLS_AES_256_GCM_SHA384) id us-mta-564-bEcuq4IJMkGSpwL9tVj0zA-1; Fri, 05 Jan 2024 05:25:15 -0500 X-MC-Unique: bEcuq4IJMkGSpwL9tVj0zA-1 Received: from smtp.corp.redhat.com (int-mx09.intmail.prod.int.rdu2.redhat.com [10.11.54.9]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 4F1951C0514B; Fri, 5 Jan 2024 10:25:15 +0000 (UTC) Received: from localhost (unknown [10.42.28.185]) by smtp.corp.redhat.com (Postfix) with ESMTP id 00ACB492BC6; Fri, 5 Jan 2024 10:25:14 +0000 (UTC) From: Jonathan Wakely To: libstdc++@gcc.gnu.org, gcc-patches@gcc.gnu.org Cc: Cassio Neri Subject: [committed] libstdc++: Remove UB from month and weekday additions and subtractions. Date: Fri, 5 Jan 2024 10:24:33 +0000 Message-ID: <20240105102514.3180917-1-jwakely@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.4.1 on 10.11.54.9 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H3, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_NONE, TXREP, T_SCC_BODY_TEXT_LINE autolearn=unavailable autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.30 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: gcc-patches-bounces+ouuuleilei=gmail.com@gcc.gnu.org X-getmail-retrieved-from-mailbox: INBOX X-GMAIL-THRID: 1787249878054847507 X-GMAIL-MSGID: 1787249878054847507 From: Cassio Neri Tested x86_64-linux. Pushed to trunk. This seems suitable for backporting too, at least to gcc-13. -- >8 -- The following invoke signed integer overflow (UB) [1]: month + months{MAX} // where MAX is the maximum value of months::rep month + months{MIN} // where MIN is the maximum value of months::rep month - months{MIN} // where MIN is the minimum value of months::rep weekday + days {MAX} // where MAX is the maximum value of days::rep weekday - days {MIN} // where MIN is the minimum value of days::rep For the additions to MAX, the crux of the problem is that, in libstdc++, months::rep and days::rep are int64_t. Other implementations use int32_t, cast operands to int64_t and perform arithmetic operations without risk of overflowing. For month + months{MIN}, the implementation follows the Standard's "returns clause" and evaluates: modulo(static_cast(unsigned{__x}) + (__y.count() - 1), 12); Overflow occurs when MIN - 1 is evaluated. Casting to a larger type could help but, unfortunately again, this is not possible for libstdc++. For the subtraction of MIN, the problem is that -MIN is not representable. It's fair to say that the intention is for these additions/subtractions to be performed in modulus (12 or 7) arithmetic so that no overflow is expected. To fix these UB, this patch implements: template unsigned __add_modulo(unsigned __x, _T __y); template unsigned __sub_modulo(unsigned __x, _T __y); which respectively, returns the remainder of Euclidean division of, __x + __y and __x - __y by __d without overflowing. These functions replace constexpr unsigned __modulo(long long __n, unsigned __d); which also calculates the reminder of __n, where __n is the result of the addition or subtraction. Hence, these operations might invoke UB before __modulo is called and thus, __modulo can't do anything to remediate the issue. In addition to solve the UB issues, __add_modulo and __sub_modulo allow better codegen (shorter and branchless) on x86-64 and ARM [2]. [1] https://godbolt.org/z/a9YfWdn57 [2] https://godbolt.org/z/Gh36cr7E4 libstdc++-v3/ChangeLog: * include/std/chrono: Fix + and - 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. --- libstdc++-v3/include/std/chrono | 81 +++++++++++++------- libstdc++-v3/testsuite/std/time/month/1.cc | 19 +++++ libstdc++-v3/testsuite/std/time/month/2.cc | 32 ++++++++ libstdc++-v3/testsuite/std/time/weekday/1.cc | 16 +++- libstdc++-v3/testsuite/std/time/weekday/2.cc | 32 ++++++++ 5 files changed, 152 insertions(+), 28 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 b3ad2a0b1ac..a59af34567c 100644 --- a/libstdc++-v3/include/std/chrono +++ b/libstdc++-v3/include/std/chrono @@ -501,18 +501,47 @@ _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). - constexpr unsigned - __modulo(long long __n, unsigned __d) + // Helper to __add_modulo and __sub_modulo. + template + consteval auto + __modulo_offset() { - if (__n >= 0) - return __n % __d; - else - return (__d + (__n % __d)) % __d; + using _Up = make_unsigned_t<_Tp>; + auto constexpr __a = _Up(-1) - _Up(255 + __d - 2); + auto constexpr __b = _Up(__d * (__a / __d) - 1); + // Notice: b <= a - 1 <= _Up(-1) - (255 + d - 1) and b % d = d - 1. + return _Up(-1) - __b; // >= 255 + d - 1 + } + + // 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 with a shift in [0, d - 1] and __y is a duration count. + template + constexpr unsigned + __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 subtract from _Up(__y) an __offset >= + // 255 + d - 1 to make room for the addition to __x and shift the modulo + // to the correct value. + auto const __offset = __y >= 0 ? _Up(0) : __modulo_offset<__d, _Tp>(); + return (__x + _Up(__y) - __offset) % __d; + } + + // Similar to __add_modulo but for __x - __y. + template + constexpr unsigned + __sub_modulo(unsigned __x, _Tp __y) + { + using _Up = make_unsigned_t<_Tp>; + auto const __offset = __y <= 0 ? _Up(0) : __modulo_offset<__d, _Tp>(); + return (__x - _Up(__y) - __offset) % __d; } inline constexpr unsigned __days_per_month[12] @@ -704,8 +733,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 @@ -714,7 +745,12 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION friend constexpr month operator-(const month& __x, const months& __y) noexcept - { return __x + -__y; } + { + // modulo(x + (-y - 1), 12) = modulo(x + (-y - 1) + 12, 12) + // = modulo((x + 11) - y , 12) + return month{1 + __detail::__sub_modulo<12>( + unsigned{__x} + 11, __y.count())}; + } friend constexpr months operator-(const month& __x, const month& __y) noexcept @@ -934,15 +970,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: @@ -1032,8 +1060,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 @@ -1042,7 +1069,9 @@ _GLIBCXX_BEGIN_NAMESPACE_VERSION friend constexpr weekday operator-(const weekday& __x, const days& __y) noexcept - { return __x + -__y; } + { + return weekday{__detail::__sub_modulo<7>(__x._M_wd, __y.count())}; + } friend constexpr days operator-(const weekday& __x, const weekday& __y) noexcept diff --git a/libstdc++-v3/testsuite/std/time/month/1.cc b/libstdc++-v3/testsuite/std/time/month/1.cc index 0f8ce556434..0caf0f1f432 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() @@ -34,6 +35,24 @@ constexpr_month() dm += months{3}; dm -= months{3}; + // Test for UB (overflow). + { + using rep = months::rep; + using std::numeric_limits; + + auto constexpr months_min = months{numeric_limits::min()}; + auto constexpr month_000_plus_months_min = month{ 0 } + months_min; + auto constexpr month_255_plus_months_min = month{255} + months_min; + auto constexpr month_000_minus_months_min = month{ 0 } - months_min; + auto constexpr month_255_minus_months_min = month{255} - months_min; + + auto constexpr months_max = months{numeric_limits::max()}; + auto constexpr month_000_plus_months_max = month{ 0 } + months_max; + auto constexpr month_255_plus_months_max = month{255} + months_max; + auto constexpr month_000_minus_months_max = month{ 0 } - months_max; + auto constexpr month_255_minus_months_max = month{255} - months_max; + } + static_assert(February + months{11} == January); static_assert(January + months{1200} == January); static_assert(January + months{1201} == February); 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..3bcefa60003 --- /dev/null +++ b/libstdc++-v3/testsuite/std/time/month/2.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++20 } } + +// Class month [time.cal.month] + +#include +#include +#include + +using namespace std::chrono; + +void test_extreme_values(months extreme) +{ + auto const count = extreme.count(); + auto const safe = count < 0 ? count + 12 : count; + auto const mod = safe - 12 * ((safe < 0 ? safe - 11 : safe) / 12); + + for (unsigned m = 0; m < 256; ++m) + { + auto const month_plus_extreme = month{m} + extreme; + VERIFY(unsigned{month_plus_extreme } == (m + 11 + mod) % 12 + 1); + + auto const month_minus_extreme = month{m} - extreme; + VERIFY(unsigned{month_minus_extreme} == (m + 11 - mod) % 12 + 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 bb24a36d6db..758999d0e24 100644 --- a/libstdc++-v3/testsuite/std/time/weekday/1.cc +++ b/libstdc++-v3/testsuite/std/time/weekday/1.cc @@ -42,8 +42,20 @@ constexpr_weekday() { using rep = days::rep; using std::numeric_limits; - constexpr weekday max{sys_days{days{numeric_limits::max()}}}; - constexpr weekday min{sys_days{days{numeric_limits::min()}}}; + + auto constexpr days_min = days{numeric_limits::min()}; + auto constexpr weekday_from_sysdays_min = weekday{sys_days{days_min}}; + auto constexpr weekday_000_plus_days_min = weekday{ 0 } + days_min; + auto constexpr weekday_255_plus_days_min = weekday{255} + days_min; + auto constexpr weekday_000_minus_days_min = weekday{ 0 } - days_min; + auto constexpr weekday_255_minus_days_min = weekday{255} - days_min; + + auto constexpr days_max = days{numeric_limits::max()}; + auto constexpr weekday_from_sysdays_max = weekday{sys_days{days_max}}; + auto constexpr weekday_000_plus_days_max = weekday{ 0 } + days_max; + auto constexpr weekday_255_plus_days_max = weekday{255} + days_max; + auto constexpr weekday_000_minus_days_max = weekday{ 0 } - days_max; + auto constexpr weekday_255_minus_days_max = weekday{255} - days_max; } static_assert(weekday{sys_days{1900y/January/1}} == Monday); 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..924709321e5 --- /dev/null +++ b/libstdc++-v3/testsuite/std/time/weekday/2.cc @@ -0,0 +1,32 @@ +// { dg-do run { target c++20 } } + +// Class weekday [time.cal.wd] + +#include +#include +#include + +using namespace std::chrono; + +void test_extreme_values(days extreme) +{ + auto const count = extreme.count(); + auto const safe = count < 0 ? count + 7 : count; + auto const mod = safe - 7 * ((safe < 0 ? safe - 6 : safe) / 7); + + for (unsigned d = 0; d < 254; ++d) + { + auto const weekday_plus_extreme = weekday{d} + extreme; + VERIFY(weekday_plus_extreme.c_encoding() == (d + mod) % 7); + + auto const weekday_minus_extreme = weekday{d} - extreme; + VERIFY(weekday_minus_extreme.c_encoding() == (d + 7 - mod) % 7); + } +} + +int main() +{ + test_extreme_values(days{std::numeric_limits::max()}); + test_extreme_values(days{std::numeric_limits::min()}); + return 0; +}