From: Siddhesh Poyarekar <siddhesh@gotplt.org>
To: gcc-patches@gcc.gnu.org
Cc: jakub@redhat.com
Subject: [PATCH v3 0/8] __builtin_dynamic_object_size
Date: Fri, 26 Nov 2021 10:58:43 +0530 [thread overview]
Message-ID: <20211126052851.2176408-1-siddhesh@gotplt.org> (raw)
In-Reply-To: <20211109190137.1107736-1-siddhesh@gotplt.org>
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 a TREE_VEC of size 2
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.
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.
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. I've started working on these patches too on the side.
- 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 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 (8):
tree-object-size: Replace magic numbers with enums
tree-object-size: Abstract object_sizes array
tree-object-size: Save sizes as 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 | 1219 +++++++++++++----
gcc/tree-object-size.h | 12 +-
gcc/ubsan.c | 5 +-
37 files changed, 2392 insertions(+), 280 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
--
2.31.1
next prev parent reply other threads:[~2021-11-26 5:29 UTC|newest]
Thread overview: 97+ messages / expand[flat|nested] mbox.gz Atom feed top
2021-11-09 19:01 [PATCH 00/10] __builtin_dynamic_object_size Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 01/10] tree-object-size: Replace magic numbers with enums Siddhesh Poyarekar
2021-11-19 16:00 ` Jakub Jelinek
2021-11-09 19:01 ` [PATCH 02/10] tree-object-size: Abstract object_sizes array Siddhesh Poyarekar
2021-11-19 16:18 ` Jakub Jelinek
2021-11-19 16:53 ` Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 03/10] tree-object-size: Use tree instead of HOST_WIDE_INT Siddhesh Poyarekar
2021-11-19 17:06 ` Jakub Jelinek
2021-11-19 19:01 ` Siddhesh Poyarekar
2021-11-19 19:16 ` Jakub Jelinek
2021-11-22 8:41 ` Richard Biener
2021-11-22 10:11 ` Siddhesh Poyarekar
2021-11-22 10:31 ` Jakub Jelinek
2021-11-22 12:00 ` Siddhesh Poyarekar
2021-11-22 12:31 ` Siddhesh Poyarekar
2021-11-22 12:32 ` Jakub Jelinek
2021-11-23 11:58 ` Jakub Jelinek
2021-11-23 13:33 ` Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 04/10] tree-object-size: Single pass dependency loop resolution Siddhesh Poyarekar
2021-11-23 12:07 ` Jakub Jelinek
2021-11-23 13:44 ` Siddhesh Poyarekar
2021-11-23 14:22 ` Jakub Jelinek
2021-11-09 19:01 ` [PATCH 05/10] __builtin_dynamic_object_size: Recognize builtin Siddhesh Poyarekar
2021-11-23 12:41 ` Jakub Jelinek
2021-11-23 13:53 ` Siddhesh Poyarekar
2021-11-23 14:00 ` Jakub Jelinek
2021-11-09 19:01 ` [PATCH 06/10] tree-object-size: Support dynamic sizes in conditions Siddhesh Poyarekar
2021-11-23 15:12 ` Jakub Jelinek
2021-11-23 15:36 ` Siddhesh Poyarekar
2021-11-23 15:38 ` Siddhesh Poyarekar
2021-11-23 16:17 ` Jakub Jelinek
2021-11-23 15:52 ` Jakub Jelinek
2021-11-23 16:00 ` Siddhesh Poyarekar
2021-11-23 16:19 ` Jakub Jelinek
2021-11-09 19:01 ` [PATCH 07/10] tree-object-size: Handle function parameters Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 08/10] tree-object-size: Handle GIMPLE_CALL Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 09/10] tree-object-size: Dynamic sizes for ADDR_EXPR Siddhesh Poyarekar
2021-11-09 19:01 ` [PATCH 10/10] tree-object-size: Handle dynamic offsets Siddhesh Poyarekar
2021-11-19 15:56 ` [PATCH 00/10] __builtin_dynamic_object_size Jakub Jelinek
2021-11-26 5:28 ` Siddhesh Poyarekar [this message]
2021-11-26 5:28 ` [PATCH v3 1/8] tree-object-size: Replace magic numbers with enums Siddhesh Poyarekar
2021-11-26 16:46 ` Jakub Jelinek
2021-11-26 17:53 ` Siddhesh Poyarekar
2021-11-26 18:01 ` Jakub Jelinek
2021-11-26 5:28 ` [PATCH v3 2/8] tree-object-size: Abstract object_sizes array Siddhesh Poyarekar
2021-11-26 16:47 ` Jakub Jelinek
2021-11-26 5:28 ` [PATCH v3 3/8] tree-object-size: Save sizes as trees and support negative offsets Siddhesh Poyarekar
2021-11-26 16:56 ` Jakub Jelinek
2021-11-26 17:59 ` Siddhesh Poyarekar
2021-11-26 18:04 ` Jakub Jelinek
2021-11-26 18:07 ` Siddhesh Poyarekar
2021-11-26 5:28 ` [PATCH v3 4/8] __builtin_dynamic_object_size: Recognize builtin Siddhesh Poyarekar
2021-11-26 5:28 ` [PATCH v3 5/8] tree-object-size: Support dynamic sizes in conditions Siddhesh Poyarekar
2021-11-26 5:28 ` [PATCH v3 6/8] tree-object-size: Handle function parameters Siddhesh Poyarekar
2021-11-26 5:28 ` [PATCH v3 7/8] tree-object-size: Handle GIMPLE_CALL Siddhesh Poyarekar
2021-11-26 5:28 ` [PATCH v3 8/8] tree-object-size: Dynamic sizes for ADDR_EXPR Siddhesh Poyarekar
2021-11-26 5:38 ` [PATCH v3 0/8] __builtin_dynamic_object_size Siddhesh Poyarekar
2021-12-01 14:27 ` [PATCH v4 0/6] __builtin_dynamic_object_size Siddhesh Poyarekar
2021-12-01 14:27 ` [PATCH v4 1/6] tree-object-size: Use trees and support negative offsets Siddhesh Poyarekar
2021-12-15 15:21 ` Jakub Jelinek
2021-12-15 17:12 ` Siddhesh Poyarekar
2021-12-15 18:43 ` Jakub Jelinek
2021-12-16 0:41 ` Siddhesh Poyarekar
2021-12-16 15:49 ` Jakub Jelinek
2021-12-16 18:56 ` Siddhesh Poyarekar
2021-12-16 21:16 ` Jakub Jelinek
2021-12-01 14:27 ` [PATCH v4 2/6] __builtin_dynamic_object_size: Recognize builtin Siddhesh Poyarekar
2021-12-15 15:24 ` Jakub Jelinek
2021-12-16 2:16 ` Siddhesh Poyarekar
2021-12-01 14:27 ` [PATCH v4 3/6] tree-object-size: Support dynamic sizes in conditions Siddhesh Poyarekar
2021-12-15 16:24 ` Jakub Jelinek
2021-12-15 17:56 ` Siddhesh Poyarekar
2021-12-15 18:52 ` Jakub Jelinek
2021-12-01 14:27 ` [PATCH v4 4/6] tree-object-size: Handle function parameters Siddhesh Poyarekar
2021-12-01 14:27 ` [PATCH v4 5/6] tree-object-size: Handle GIMPLE_CALL Siddhesh Poyarekar
2021-12-01 14:27 ` [PATCH v4 6/6] tree-object-size: Dynamic sizes for ADDR_EXPR Siddhesh Poyarekar
2021-12-18 12:35 ` [PATCH v5 0/4] __builtin_dynamic_object_size Siddhesh Poyarekar
2021-12-18 12:35 ` [PATCH v5 1/4] tree-object-size: Support dynamic sizes in conditions Siddhesh Poyarekar
2022-01-10 10:37 ` Jakub Jelinek
2022-01-10 23:55 ` Siddhesh Poyarekar
2021-12-18 12:35 ` [PATCH v5 2/4] tree-object-size: Handle function parameters Siddhesh Poyarekar
2022-01-10 10:50 ` Jakub Jelinek
2022-01-11 0:32 ` Siddhesh Poyarekar
2021-12-18 12:35 ` [PATCH v5 3/4] tree-object-size: Handle GIMPLE_CALL Siddhesh Poyarekar
2022-01-10 11:03 ` Jakub Jelinek
2021-12-18 12:35 ` [PATCH v5 4/4] tree-object-size: Dynamic sizes for ADDR_EXPR Siddhesh Poyarekar
2022-01-10 11:09 ` Jakub Jelinek
2022-01-04 3:24 ` [PING][PATCH v5 0/4] __builtin_dynamic_object_size Siddhesh Poyarekar
2022-01-11 8:57 ` [PATCH v6 " Siddhesh Poyarekar
2022-01-11 8:57 ` [PATCH v6 1/4] tree-object-size: Support dynamic sizes in conditions Siddhesh Poyarekar
2022-01-11 9:43 ` Jakub Jelinek
2022-01-11 9:44 ` Siddhesh Poyarekar
2022-01-11 8:57 ` [PATCH v6 2/4] tree-object-size: Handle function parameters Siddhesh Poyarekar
2022-01-11 9:44 ` Jakub Jelinek
2022-01-11 8:57 ` [PATCH v6 3/4] tree-object-size: Handle GIMPLE_CALL Siddhesh Poyarekar
2022-01-11 8:57 ` [PATCH v6 4/4] tree-object-size: Dynamic sizes for ADDR_EXPR Siddhesh Poyarekar
2022-01-11 9:47 ` Jakub Jelinek
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20211126052851.2176408-1-siddhesh@gotplt.org \
--to=siddhesh@gotplt.org \
--cc=gcc-patches@gcc.gnu.org \
--cc=jakub@redhat.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).