From patchwork Wed Dec 1 14:27:51 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Siddhesh Poyarekar X-Patchwork-Id: 1562179 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: bilbo.ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gotplt.org header.i=@gotplt.org header.a=rsa-sha1 header.s=gotplt.org header.b=XjvfnJKF; dkim-atps=neutral Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by bilbo.ozlabs.org (Postfix) with ESMTPS id 4J41gL5zBQz9sR4 for ; Thu, 2 Dec 2021 01:29:17 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 3189F3858037 for ; Wed, 1 Dec 2021 14:29:15 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from fossa.ash.relay.mailchannels.net (fossa.ash.relay.mailchannels.net [23.83.222.62]) by sourceware.org (Postfix) with ESMTPS id EA60E3858C60 for ; Wed, 1 Dec 2021 14:28:13 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org EA60E3858C60 Authentication-Results: sourceware.org; dmarc=none (p=none dis=none) header.from=gotplt.org Authentication-Results: sourceware.org; spf=pass smtp.mailfrom=gotplt.org X-Sender-Id: dreamhost|x-authsender|siddhesh@gotplt.org Received: from relay.mailchannels.net (localhost [127.0.0.1]) by relay.mailchannels.net (Postfix) with ESMTP id BCA54E1D4C; Wed, 1 Dec 2021 14:28:09 +0000 (UTC) Received: from pdx1-sub0-mail-a307.dreamhost.com (unknown [127.0.0.6]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 7AE38E2197; Wed, 1 Dec 2021 14:28:06 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|siddhesh@gotplt.org Received: from pdx1-sub0-mail-a307.dreamhost.com (pop.dreamhost.com [64.90.62.162]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.127.242.146 (trex/6.4.3); Wed, 01 Dec 2021 14:28:09 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|siddhesh@gotplt.org X-MailChannels-Auth-Id: dreamhost X-Gusty-Oafish: 3cce973a5ad8804e_1638368889589_465649135 X-MC-Loop-Signature: 1638368889588:128237879 X-MC-Ingress-Time: 1638368889588 Received: from rhbox.intra.reserved-bit.com (unknown [1.186.123.150]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) (Authenticated sender: siddhesh@gotplt.org) by pdx1-sub0-mail-a307.dreamhost.com (Postfix) with ESMTPSA id 4J41dw4DJGz23; Wed, 1 Dec 2021 06:28:04 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gotplt.org; s=gotplt.org; t=1638368886; bh=JWgw3ZZQxPNZWpRXX+pbi6R2T7g=; h=From:To:Cc:Subject:Date:Content-Transfer-Encoding; b=XjvfnJKFsD3C8t3N0zZIF07e2/f4rR5CBBvSycI5HIFT2u6aEG21djSjla0b3znZ3 XO+cdthsOzLNfWw0jvLt0TDjEWhSJnHX9UZeJUBeJE2D+FpxLJBDRwSG/2HygxqhwN Uk8nYtdc4X7uOOfig8rvpYW9e1Y86uzSw4cwaZ1E= From: Siddhesh Poyarekar To: gcc-patches@gcc.gnu.org Subject: [PATCH v4 0/6] __builtin_dynamic_object_size Date: Wed, 1 Dec 2021 19:57:51 +0530 Message-Id: <20211201142757.4086840-1-siddhesh@gotplt.org> X-Mailer: git-send-email 2.31.1 In-Reply-To: <20211109190137.1107736-1-siddhesh@gotplt.org> References: <20211109190137.1107736-1-siddhesh@gotplt.org> MIME-Version: 1.0 X-Spam-Status: No, score=-3032.3 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_DNSWL_NONE, RCVD_IN_MSPIKE_H2, RCVD_IN_SBL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=no autolearn_force=no version=3.4.4 X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Cc: jakub@redhat.com Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patchset implements the __builtin_dynamic_object_size builtin for gcc. The primary motivation to have this builtin in gcc is to enable _FORTIFY_SOURCE=3 support with gcc, thus allowing greater fortification in use cases where the potential performance tradeoff is acceptable. Semantics: ---------- __builtin_dynamic_object_size has the same signature as __builtin_object_size; it accepts a pointer and type ranging from 0 to 3 and it returns an object size estimate for the pointer based on an analysis of which objects the pointer could point to. The actual properties of the object size estimate are different: - In the best case __builtin_dynamic_object_size evaluates to an expression that represents a precise size of the object being pointed to. - In case a precise object size expression cannot be evaluated, __builtin_dynamic_object_size attempts to evaluate an estimate size expression based on the object size type. - In what situations the builtin returns an estimate vs a precise expression is an implementation detail and may change in future. Users must always assume, as in the case of __builtin_object_size, that the returned value is the maximum or minimum based on the object size type they have provided. - In the worst case of failure, __builtin_dynamic_object_size returns a constant (size_t)-1 or (size_t)0. Implementation: --------------- - The __builtin_dynamic_object_size support is implemented in tree-object-size. In most cases the first pass (early_objsz) the builtin is treated like __builtin_object_size to preserve subobject bounds. - Each element of the object_sizes vector is now an object_size struct holding bytes to the end of the object and the full size of the object. This allows proper handling of negative offsets, allowing them to the extent of the whole object bounds. This improves __builtin_object_size usage too with negative offsets, consistently returning valid results for pointer decrementing loops too. - The patchset begins with structural modification of the tree-object-size pass, followed by enhancement to return size expressions. I have split the implementation into one feature per patch (calls, function parameters, PHI, etc.) to hopefully ease review. Performance: ------------ Expressions generated by this pass in theory could be arbitrarily complex. I have not made an attempt to limit nesting of objects since it seemed too early to do that. In practice based on the few applications I built, most of the complexity of the expressions got folded away. Even so, the performance overhead is likely to be non-zero. If we find performance degradation to be significant, we could later add nesting limits to bail out if a size expression gets too complex. I have implemented simplification of __*_chk to their normal variants if we can determine at compile time that it is safe. This should limit the performance overhead of the expressions in valid cases. Build time performance doesn't seem to be affected much based on an unscientific check to time `make check-gcc RUNTESTFLAGS="dg.exp=builtin*"`. It only increases by about a couple of seconds when the dynamic tests are added and remains more or less in the same ballpark otherwise. Testing: -------- I have added tests for dynamic object sizes as well as wrappers for all __builtin_object_size tests to provide wide coverage. I have also done a full bootstrap build and test run on x86_64. Further I did a bootstrap build with --with-build-config=bootstrap-ubsan for additional coverage since it managed to find an issue with the earlier cleanup patches. It is however only useful to ensure there are no regressions since ubsan does not yet use dynamic size expressions. I have also built bash, cmake, wpa_supplicant and systemtap with _FORTIFY_SOURCE=2 and _FORTIFY_SOURCE=3 (with a hacked up glibc to make sure it works) and saw no issues in any of those builds. I did some rudimentary analysis of the generated binaries using fortify-metrics[1] to confirm that there was a difference in coverage between the two fortification levels. (Unchanged since v3) Here is a summary of coverage in the above packages: F = number of fortified calls T = Total number of calls to fortifiable functions (fortified as well as unfortified) C = F * 100/ T Package F(2) T(2) F(3) T(3) C(2) C(3) bash 428 1220 1005 1196 35.08% 84.03% wpa_supplicant 1635 3232 2350 3408 50.59% 68.96% systemtap 324 1990 343 1994 16.28% 17.20% cmake 830 14181 958 14196 5.85% 6.75% The numbers are slightly lower than the previous patch series because in the interim I pushed an improvement to folding of the _chk builtins so that they can use ranges to simplify the calls to their regular variants. Also note that even _FORTIFY_SOURCE=2 coverage should be improved due to negative offset handling. Additional testing plans (i.e. I've already started to do some of this): - Build packages to compare values returned by __builtin_object_size with the older pass and this new one. Also compare with __builtin_dynamic_object_size. - Expand the list of packages to get more coverage metrics. - Explore performance impact on applications on building with _FORTIFY_SOURCE=3. Limitations/Future work: ------------------------ - I need to enable _FORTIFY_SOURCE=3 for gcc in glibc; currently it is llvm-only. It's a fairly simple fix that I'll push once this series is in. - Explore ways to use the non-constant sizes returned for __builtin_object_size to arrive at a constant estimate to improve _FORTIFY_SOURCE=2 coverage in a way that accounts for undefined behaviour. - More work could to be done to reduce the performance impact of the computation. One way could be to add a heuristic where the pass keeps track of nesting in the expression and either bail out or compute an estimate if nesting crosses a threshold. I'll take this up once we have more data on the nature of the bottlenecks. Changes from v3: - Made a custom struct object_size to hold size and wholesize in the object_sizes arrays instead of the TREE_VEC. Changes from v2: Changes to individual patches have been mentioned in the patches themselves. - Dropped patch to remove check_for_plus_in_for_loops and osi->pass - Merge negative offset support (10/10 in v2) into 3/8 and support static object sizes - Merge dynamic offset (10/10 in v2) support into 8/8 Siddhesh Poyarekar (6): tree-object-size: Use trees and support negative offsets __builtin_dynamic_object_size: Recognize builtin tree-object-size: Support dynamic sizes in conditions tree-object-size: Handle function parameters tree-object-size: Handle GIMPLE_CALL tree-object-size: Dynamic sizes for ADDR_EXPR gcc/builtins.c | 23 +- gcc/builtins.def | 1 + gcc/doc/extend.texi | 13 + gcc/gimple-fold.c | 11 +- .../g++.dg/ext/builtin-dynamic-object-size1.C | 5 + .../g++.dg/ext/builtin-dynamic-object-size2.C | 5 + .../gcc.dg/builtin-dynamic-alloc-size.c | 7 + .../gcc.dg/builtin-dynamic-object-size-0.c | 464 +++++++ .../gcc.dg/builtin-dynamic-object-size-1.c | 6 + .../gcc.dg/builtin-dynamic-object-size-10.c | 11 + .../gcc.dg/builtin-dynamic-object-size-11.c | 7 + .../gcc.dg/builtin-dynamic-object-size-12.c | 5 + .../gcc.dg/builtin-dynamic-object-size-13.c | 5 + .../gcc.dg/builtin-dynamic-object-size-14.c | 5 + .../gcc.dg/builtin-dynamic-object-size-15.c | 5 + .../gcc.dg/builtin-dynamic-object-size-16.c | 6 + .../gcc.dg/builtin-dynamic-object-size-17.c | 7 + .../gcc.dg/builtin-dynamic-object-size-18.c | 8 + .../gcc.dg/builtin-dynamic-object-size-19.c | 104 ++ .../gcc.dg/builtin-dynamic-object-size-2.c | 6 + .../gcc.dg/builtin-dynamic-object-size-3.c | 6 + .../gcc.dg/builtin-dynamic-object-size-4.c | 6 + .../gcc.dg/builtin-dynamic-object-size-5.c | 7 + .../gcc.dg/builtin-dynamic-object-size-6.c | 5 + .../gcc.dg/builtin-dynamic-object-size-7.c | 5 + .../gcc.dg/builtin-dynamic-object-size-8.c | 5 + .../gcc.dg/builtin-dynamic-object-size-9.c | 5 + gcc/testsuite/gcc.dg/builtin-object-size-1.c | 184 ++- gcc/testsuite/gcc.dg/builtin-object-size-16.c | 2 + gcc/testsuite/gcc.dg/builtin-object-size-17.c | 2 + gcc/testsuite/gcc.dg/builtin-object-size-2.c | 163 +++ gcc/testsuite/gcc.dg/builtin-object-size-3.c | 182 +++ gcc/testsuite/gcc.dg/builtin-object-size-4.c | 123 ++ gcc/testsuite/gcc.dg/builtin-object-size-5.c | 37 + gcc/tree-object-size.c | 1085 +++++++++++++---- gcc/tree-object-size.h | 12 +- gcc/ubsan.c | 5 +- 37 files changed, 2312 insertions(+), 226 deletions(-) create mode 100644 gcc/testsuite/g++.dg/ext/builtin-dynamic-object-size1.C create mode 100644 gcc/testsuite/g++.dg/ext/builtin-dynamic-object-size2.C create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-alloc-size.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-0.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-1.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-10.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-11.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-12.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-13.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-14.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-15.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-16.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-17.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-18.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-19.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-2.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-3.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-4.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-5.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-6.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-7.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-8.c create mode 100644 gcc/testsuite/gcc.dg/builtin-dynamic-object-size-9.c