From patchwork Tue Nov 9 19:01:26 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Siddhesh Poyarekar X-Patchwork-Id: 1553129 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=l3XSld4U; 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 4HpcmK1zXrz9sCD for ; Wed, 10 Nov 2021 06:02:07 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 0C9D13858430 for ; Tue, 9 Nov 2021 19:02:05 +0000 (GMT) X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from antelope.elm.relay.mailchannels.net (antelope.elm.relay.mailchannels.net [23.83.212.4]) by sourceware.org (Postfix) with ESMTPS id 6D3293858404 for ; Tue, 9 Nov 2021 19:01:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org 6D3293858404 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 DCF62781A88; Tue, 9 Nov 2021 19:01:49 +0000 (UTC) Received: from pdx1-sub0-mail-a306.dreamhost.com (100-96-133-198.trex.outbound.svc.cluster.local [100.96.133.198]) (Authenticated sender: dreamhost) by relay.mailchannels.net (Postfix) with ESMTPA id 53B24781B16; Tue, 9 Nov 2021 19:01:49 +0000 (UTC) X-Sender-Id: dreamhost|x-authsender|siddhesh@gotplt.org Received: from pdx1-sub0-mail-a306.dreamhost.com (pop.dreamhost.com [64.90.62.162]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384) by 100.96.133.198 (trex/6.4.3); Tue, 09 Nov 2021 19:01:49 +0000 X-MC-Relay: Neutral X-MailChannels-SenderId: dreamhost|x-authsender|siddhesh@gotplt.org X-MailChannels-Auth-Id: dreamhost X-Ski-Stop: 1df527662b86822d_1636484509638_3078558558 X-MC-Loop-Signature: 1636484509638:3858384420 X-MC-Ingress-Time: 1636484509638 Received: from rhbox.redhat.com (unknown [1.186.121.127]) (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-a306.dreamhost.com (Postfix) with ESMTPSA id 4Hpclv6jV9z1WX; Tue, 9 Nov 2021 11:01:47 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha1; c=relaxed/relaxed; d=gotplt.org; s=gotplt.org; t=1636484509; bh=7FeENWYVU6PAqfPBQJFRNaZWYwk=; h=From:To:Cc:Subject:Date:Content-Transfer-Encoding; b=l3XSld4U0lo57TY+BQB37smnyZPHs5Oob2WFyENUKPcVT8W4wvLGPGxfJf7VB102n sSp/7kss72fYmj091UrUZGLOIt7DpAdncuzNz/uUSoVwDgeCc2v/WEQsU1DUbMOIkA 00XhZ4ZAFL7MV14gfnCgFXu7F7cO0UowYo2q/y1A= From: Siddhesh Poyarekar To: gcc-patches@gcc.gnu.org Subject: [PATCH 00/10] __builtin_dynamic_object_size Date: Wed, 10 Nov 2021 00:31:26 +0530 Message-Id: <20211109190137.1107736-1-siddhesh@gotplt.org> X-Mailer: git-send-email 2.31.1 MIME-Version: 1.0 X-Spam-Status: No, score=-3030.7 required=5.0 tests=BAYES_00, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, RCVD_IN_BARRACUDACENTRAL, 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) is able to evaluate object size expressions. The second phase mainly ends up simplifying the __builtin_dynamic_object_size to __builtin_object_size. - 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 also not implemented simplification of __*_chk to their normal variants if we can determine at compile time that it is safe, which still depends on the object size to be constant. I hope to do this as a minor performance improvement in stage 3. 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. With that in place I have run full bootstrap builds on Fedora rawhide by backporting the patches to the gcc11 branch and x86_64 and i686 have no failures in any of the builtin-*object-size* tests and no new failures. I have also built bash, cmake, zfs-fuse and systemtap with _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 to see if there was any difference in coverage and found that there was. In terms of pure numbers, there were far more _chk variants of calls than the regular ones due to _FORTIFY_SOURCE (from about 4% to 70% in bash), but that could well be due to the _chk variants not being folded into regular variants when safe. However, on manual inspection of some of these sites, it was clear that coverage was increasing significantly where __builtin_object_size was previously bailing out. Specifically for bash, the coverage went from 30.81% to 86.87% (it was 84.5% with the v1 patch). I actually hope to reduce this a bit with folding improvements for __builtin___memcpy_chk, etc. A bootstrap build is in progress on x86_64. Limitations/Future work: ------------------------ - The most immediate work is to fold _chk variants of builtins into regular ones when it can be proven at compile time that the object size will alwasy be less than the length of the write. I am working on it right now. - I need to enable _FORTIFY_SOURCE=3 for gcc in glibc; currently it is llvm-only. I've started working on these patches too on the side. - Instead of bailing out on non-constant sizes with __builtin_object_size, it should be possible to use ranger to get an upper and lower bound on the size expression and use that to implement __builtin_object_size. - 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. Siddhesh Poyarekar (10): tree-object-size: Replace magic numbers with enums tree-object-size: Abstract object_sizes array tree-object-size: Use tree instead of HOST_WIDE_INT tree-object-size: Single pass dependency loop resolution __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 tree-object-size: Handle dynamic offsets gcc/builtins.c | 22 +- gcc/builtins.def | 1 + gcc/doc/extend.texi | 13 + gcc/gimple-fold.c | 9 +- .../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 | 463 +++++ .../gcc.dg/builtin-dynamic-object-size-1.c | 7 + .../gcc.dg/builtin-dynamic-object-size-10.c | 9 + .../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 | 7 + .../gcc.dg/builtin-dynamic-object-size-17.c | 8 + .../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 | 7 + .../gcc.dg/builtin-dynamic-object-size-3.c | 7 + .../gcc.dg/builtin-dynamic-object-size-4.c | 7 + .../gcc.dg/builtin-dynamic-object-size-5.c | 8 + .../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 | 160 +- 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 | 134 ++ gcc/testsuite/gcc.dg/builtin-object-size-3.c | 151 ++ gcc/testsuite/gcc.dg/builtin-object-size-4.c | 99 + gcc/testsuite/gcc.dg/builtin-object-size-5.c | 12 + gcc/tree-object-size.c | 1766 +++++++++++------ gcc/tree-object-size.h | 3 +- gcc/ubsan.c | 46 +- 37 files changed, 2499 insertions(+), 620 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