From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: by sourceware.org (Postfix, from userid 2140) id B7A423856254; Fri, 6 May 2022 07:19:09 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org B7A423856254 Content-Type: text/plain; charset="us-ascii" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit From: Alexandre Oliva To: gcc-cvs@gcc.gnu.org Subject: [gcc(refs/users/aoliva/heads/testme)] Control flow redundancy hardening X-Act-Checkin: gcc X-Git-Author: Alexandre Oliva X-Git-Refname: refs/users/aoliva/heads/testme X-Git-Oldrev: bd4f52dff4ea17f204e2371bd8f8cc929291ce13 X-Git-Newrev: 02acdab6fd66c7e76fb3c1923309032ff4ecd42c Message-Id: <20220506071909.B7A423856254@sourceware.org> Date: Fri, 6 May 2022 07:19:09 +0000 (GMT) X-BeenThere: gcc-cvs@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-cvs mailing list List-Unsubscribe: , List-Archive: List-Help: List-Subscribe: , X-List-Received-Date: Fri, 06 May 2022 07:19:09 -0000 https://gcc.gnu.org/g:02acdab6fd66c7e76fb3c1923309032ff4ecd42c commit 02acdab6fd66c7e76fb3c1923309032ff4ecd42c Author: Alexandre Oliva Date: Thu Feb 17 03:12:36 2022 -0300 Control flow redundancy hardening This patch introduces an optional hardening pass to catch unexpected execution flows. Functions are transformed so that basic blocks set a bit in an automatic array, and (non-exceptional) function exit edges check that the bits in the array represent an expected execution path in the CFG. Functions with multiple exit edges, or with too many blocks, call an out-of-line checker builtin implemented in libgcc. For simpler functions, the verification is performed in-line. -fharden-control-flow-redundancy enables the pass for eligible functions, --param hardcfr-max-blocks sets a block count limit for functions to be eligible, and --param hardcfr-max-inline-blocks tunes the "too many blocks" limit for in-line verification. for gcc/ChangeLog * Makefile.in (OBJS): Add gimple-harden-control-flow.o. * builtins.def (BUILT_IN___HARDCFR_CHECK): New. * common.opt (fharden-control-flow-redundancy): New. * doc/invoke.texi (fharden-control-flow-redundancy): New. (hardcfr-max-blocks, hardcfr-max-inline-blocks): New params. * gimple-harden-control-flow.cc: New. * params.opt (-param=hardcfr-max-blocks=): New. (-param=hradcfr-max-inline-blocks=): New. * passes.def (pass_harden_control_flow_redundancy): Add. * tree-pass.h (make_pass_harden_control_flow_redundancy): Declare. for gcc/ada/ChangeLog * doc/gnat_rm/security_hardening_features.rst: Add subsection on Control Flow Redundancy. for gcc/testsuite/ChangeLog * c-c++-common/torture/harden-cfr.c: New. * c-c++-common/torture/harden-abrt.c: New. * c-c++-common/torture/harden-bref.c: New. * c-c++-common/torture/harden-tail.c: New. * gnat.dg/hardcfr.adb: New. for libgcc/ChangeLog * Makefile.in (LIB2ADD): Add hardcfr.c. * hardcfr.c: New. Diff: --- gcc/Makefile.in | 1 + .../doc/gnat_rm/security_hardening_features.rst | 87 ++- gcc/builtins.def | 3 + gcc/common.opt | 4 + gcc/doc/invoke.texi | 19 + gcc/gimple-harden-control-flow.cc | 710 +++++++++++++++++++++ gcc/params.opt | 8 + gcc/passes.def | 1 + .../c-c++-common/torture/harden-cfr-abrt.c | 11 + .../c-c++-common/torture/harden-cfr-bret.c | 11 + .../c-c++-common/torture/harden-cfr-tail.c | 17 + gcc/testsuite/c-c++-common/torture/harden-cfr.c | 81 +++ gcc/testsuite/gnat.dg/hardcfr.adb | 76 +++ gcc/tree-pass.h | 2 + libgcc/Makefile.in | 1 + libgcc/hardcfr.c | 176 +++++ 16 files changed, 1188 insertions(+), 20 deletions(-) diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 31ff95500c9..518525eb2d7 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1397,6 +1397,7 @@ OBJS = \ gimple-iterator.o \ gimple-fold.o \ gimple-harden-conditionals.o \ + gimple-harden-control-flow.o \ gimple-laddress.o \ gimple-loop-interchange.o \ gimple-loop-jam.o \ diff --git a/gcc/ada/doc/gnat_rm/security_hardening_features.rst b/gcc/ada/doc/gnat_rm/security_hardening_features.rst index 5322d987fab..8c4c1f64a4e 100644 --- a/gcc/ada/doc/gnat_rm/security_hardening_features.rst +++ b/gcc/ada/doc/gnat_rm/security_hardening_features.rst @@ -15,7 +15,7 @@ Register Scrubbing GNAT can generate code to zero-out hardware registers before returning from a subprogram. -It can be enabled with the *-fzero-call-used-regs* command line +It can be enabled with the :switch:`-fzero-call-used-regs` command-line option, to affect all subprograms in a compilation, and with a :samp:`Machine_Attribute` pragma, to affect only specific subprograms. @@ -31,7 +31,7 @@ option, to affect all subprograms in a compilation, and with a -- Before returning, Bar scrubs all call-clobbered registers. -For usage and more details on the command line option, and on the +For usage and more details on the command-line option, and on the ``zero_call_used_regs`` attribute, see :title:`Using the GNU Compiler Collection (GCC)`. @@ -64,10 +64,10 @@ specific subprograms and variables. -- of the stack space used by the subprogram. -There are also *-fstrub* command line options to control default -settings. For usage and more details on the command line option, and -on the ``strub`` attribute, see :title:`Using the GNU Compiler -Collection (GCC)`. +There are also :switch:`-fstrub` command-line options to control +default settings. For usage and more details on the command-line +option, and on the ``strub`` attribute, see :title:`Using the GNU +Compiler Collection (GCC)`. Note that Ada secondary stacks are not scrubbed. The restriction ``No_Secondary_Stack`` avoids their use, and thus their accidental @@ -126,18 +126,18 @@ Bar_Callable_Ptr. Hardened Conditionals ===================== -GNAT can harden conditionals to protect against control flow attacks. +GNAT can harden conditionals to protect against control-flow attacks. This is accomplished by two complementary transformations, each activated by a separate command-line option. -The option *-fharden-compares* enables hardening of compares that -compute results stored in variables, adding verification that the +The option :switch:`-fharden-compares` enables hardening of compares +that compute results stored in variables, adding verification that the reversed compare yields the opposite result. -The option *-fharden-conditional-branches* enables hardening of -compares that guard conditional branches, adding verification of the -reversed compare to both execution paths. +The option :switch:`-fharden-conditional-branches` enables hardening +of compares that guard conditional branches, adding verification of +the reversed compare to both execution paths. These transformations are introduced late in the compilation pipeline, long after boolean expressions are decomposed into separate compares, @@ -155,8 +155,9 @@ options ensures that every compare that is neither optimized out nor optimized into implied conditionals will be hardened. The addition of reversed compares can be observed by enabling the dump -files of the corresponding passes, through command line options -*-fdump-tree-hardcmp* and *-fdump-tree-hardcbr*, respectively. +files of the corresponding passes, through command-line options +:switch:`-fdump-tree-hardcmp` and :switch:`-fdump-tree-hardcbr`, +respectively. They are separate options, however, because of the significantly different performance impact of the hardening transformations. @@ -181,18 +182,64 @@ variables of such types hold values corresponding to the selected representations. There are multiple strategies for where to introduce validity checking -(see *-gnatV* options). Their goal is to guard against various kinds -of programming errors, and GNAT strives to omit checks when program -logic rules out an invalid value, and optimizers may further remove -checks found to be redundant. +(see :switch:`-gnatV` options). Their goal is to guard against +various kinds of programming errors, and GNAT strives to omit checks +when program logic rules out an invalid value, and optimizers may +further remove checks found to be redundant. For additional hardening, the ``hardbool`` :samp:`Machine_Attribute` pragma can be used to annotate boolean types with representation clauses, so that expressions of such types used as conditions are -checked even when compiling with *-gnatVT*. +checked even when compiling with :switch:`-gnatVT`. .. code-block:: ada pragma Machine_Attribute (HBool, "hardbool"); -Note that *-gnatVn* will disable even ``hardbool`` testing. +Note that :switch:`-gnatVn` will disable even ``hardbool`` testing. + + +.. Control Flow Redundancy: + +Control Flow Redundancy +======================= + +GNAT can guard against unexpected execution flows, such as branching +into the middle of subprograms, as in Return Oriented Programming +exploits. + +In units compiled with :switch:`-fharden-control-flow-redundancy`, +subprograms are instrumented so that, every time they are called, +basic blocks take note as control flows through them, and, before +returning, subprograms verify that the taken notes are consistent with +the control-flow graph. + +Functions with too many basic blocks, or with multiple return points, +call a run-time function to perform the verification. Other functions +perform the verification inline before returning. + +Optimizing the inlined verification can be quite time consuming, so +the default upper limit for the inline mode is set at 16 blocks. +Command-line option :switch:`--param hardcfr-max-inline-blocks=` can +override it. + +Even though typically sparse control-flow graphs exhibit run-time +verification time nearly proportional to the block count of a +subprogram, it may become very significant for generated subprograms +with thousands of blocks. Command-line option +:switch:`--param hardcfr-max-blocks=` can set an upper limit for +instrumentation. + +For each block that is marked as visited, the mechanism checks that at +least one of its predecessors, and at least one of its successors, are +also marked as visited. + +Verification is performed just before returning. Subprogram +executions that complete by raising or propagating an exception bypass +verification-and-return points. A subprogram that can only complete +by raising or propagating an exception may have instrumentation +disabled altogether. + +The instrumentation for hardening with control flow redundancy can be +observed in dump files generated by the command-line option +:switch:`-fdump-tree-hardcfr`. diff --git a/gcc/builtins.def b/gcc/builtins.def index 005976f34e9..b987f9af425 100644 --- a/gcc/builtins.def +++ b/gcc/builtins.def @@ -1055,6 +1055,9 @@ DEF_GCC_BUILTIN (BUILT_IN_FILE, "FILE", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LI DEF_GCC_BUILTIN (BUILT_IN_FUNCTION, "FUNCTION", BT_FN_CONST_STRING, ATTR_NOTHROW_LEAF_LIST) DEF_GCC_BUILTIN (BUILT_IN_LINE, "LINE", BT_FN_INT, ATTR_NOTHROW_LEAF_LIST) +/* Control Flow Redundancy hardening out-of-line checker. */ +DEF_BUILTIN_STUB (BUILT_IN___HARDCFR_CHECK, "__builtin___hardcfr_check") + /* Synchronization Primitives. */ #include "sync-builtins.def" diff --git a/gcc/common.opt b/gcc/common.opt index 8a0dafc522d..cb0ce11eee1 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -1770,6 +1770,10 @@ fharden-conditional-branches Common Var(flag_harden_conditional_branches) Optimization Harden conditional branches by checking reversed conditions. +fharden-control-flow-redundancy +Common Var(flag_harden_control_flow_redundancy) Optimization +Harden control flow by recording and checking execution paths. + ; Nonzero means ignore `#ident' directives. 0 means handle them. ; Generate position-independent code for executables if possible ; On SVR4 targets, it also controls whether or not to emit a diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index 3f4d6f2db7b..5327f1a6cb9 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -607,6 +607,7 @@ Objective-C and Objective-C++ Dialects}. -fsanitize-undefined-trap-on-error -fbounds-check @gol -fcf-protection=@r{[}full@r{|}branch@r{|}return@r{|}none@r{|}check@r{]} @gol -fharden-compares -fharden-conditional-branches @gol +-fharden-control-flow-redundancy @gol -fstack-protector -fstack-protector-all -fstack-protector-strong @gol -fstack-protector-explicit -fstack-check @gol -fstack-limit-register=@var{reg} -fstack-limit-symbol=@var{sym} @gol @@ -14674,6 +14675,16 @@ A value of zero can be used to lift the bound. A variable whose value is unknown at compilation time and defined outside a SCoP is a parameter of the SCoP. +@item hardcfr-max-blocks +Disable @option{-fharden-control-flow-redundancy} for functions with a +larger number of blocks than the specified value. Zero removes any +limit. + +@item hardcfr-max-inline-blocks +Force @option{-fharden-control-flow-redundancy} to use out-of-line +checking for functions with a larger number of basic blocks than the +specified value. + @item loop-block-tile-size Loop blocking or strip mining transforms, enabled with @option{-floop-block} or @option{-floop-strip-mine}, strip mine each @@ -16080,6 +16091,14 @@ condition, and to call @code{__builtin_trap} if the result is unexpected. Use with @samp{-fharden-compares} to cover all conditionals. +@item -fharden-control-flow-redundancy +@opindex fharden-control-flow-redundancy +Emit extra code to set booleans when entering basic blocks, and to +verify, at function exits, that they amount to an execution path that is +consistent with the control flow graph, trapping otherwise. Tuning +options @option{--param hardcfr-max-blocks} and @option{--param +hardcfr-max-inline-blocks} are available. + @item -fstack-protector @opindex fstack-protector Emit extra code to check for buffer overflows, such as stack smashing diff --git a/gcc/gimple-harden-control-flow.cc b/gcc/gimple-harden-control-flow.cc new file mode 100644 index 00000000000..f3538c895fb --- /dev/null +++ b/gcc/gimple-harden-control-flow.cc @@ -0,0 +1,710 @@ +/* Control flow redundancy hardening. + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Alexandre Oliva . + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "backend.h" +#include "tree.h" +#include "fold-const.h" +#include "gimple.h" +#include "gimplify.h" +#include "tree-pass.h" +#include "ssa.h" +#include "gimple-iterator.h" +#include "tree-cfg.h" +#include "basic-block.h" +#include "cfghooks.h" +#include "cfgloop.h" +#include "cgraph.h" +#include "alias.h" +#include "varasm.h" +#include "output.h" +#include "langhooks.h" +#include "diagnostic.h" +#include "intl.h" + +namespace { + +/* This pass introduces verification, at function exits, that booleans + set in each basic block during function execution reflect the + control flow graph: for each visited block, check that at least one + predecessor and at least one successor were also visited. This + sort of hardening may detect various kinds of attacks. */ + +/* Define a pass to harden code through control flow redundancy. */ + +const pass_data pass_data_harden_control_flow_redundancy = { + GIMPLE_PASS, + "hardcfr", + OPTGROUP_NONE, + TV_NONE, + PROP_cfg | PROP_ssa, // properties_required + 0, // properties_provided + 0, // properties_destroyed + TODO_cleanup_cfg, // properties_start + TODO_update_ssa + | TODO_cleanup_cfg + | TODO_verify_il, // properties_finish +}; + +class pass_harden_control_flow_redundancy : public gimple_opt_pass +{ +public: + pass_harden_control_flow_redundancy (gcc::context *ctxt) + : gimple_opt_pass (pass_data_harden_control_flow_redundancy, ctxt) + {} + opt_pass *clone () { return new pass_harden_control_flow_redundancy (m_ctxt); } + virtual bool gate (function *fun) { + /* Return quickly if the pass is disabled, without checking any of + the conditions that might give rise to warnings that would only + be appropriate if hardening was requested. */ + if (!flag_harden_control_flow_redundancy) + return false; + + /* We don't verify when an exception escapes, propagated or raised + by the function itself, so we're only concerned with edges to + the exit block. If there aren't any, the function doesn't + return normally, so there won't be any checking point, so + there's no point in running the pass. Should we add + verification at exception escapes, we should at least look at + !flag_exceptions here. */ + if (EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (fun)->preds) == 0) + return false; + + /* Functions that return more than once, like setjmp and vfork + (that also gets this flag set), will start recording a path + after the first return, and then may take another path when + they return again. The unterminated path may then be flagged + as an error. ??? We could save the visited array before the + call and restore it if it returns again. */ + if (fun->calls_setjmp) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD calls % or similar," + " %<-fharden-control-flow-redundancy%> is not supported", + fun->decl); + return false; + } + + /* Some targets bypass the abnormal dispatcher block in nonlocal + gotos, and then we'd miss its visited bit. It might be doable + to make it work uniformly, but this feature is not used often + enough to make it worthwhile. */ + if (fun->has_nonlocal_label) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD receives nonlocal gotos," + " %<-fharden-control-flow-redundancy%> is not supported", + fun->decl); + return false; + } + + if (param_hardcfr_max_blocks > 0 + && n_basic_blocks_for_fn (fun) - 2 > param_hardcfr_max_blocks) + { + warning_at (DECL_SOURCE_LOCATION (fun->decl), 0, + "%qD has more than %u blocks, the requested" + " maximum for %<-fharden-control-flow-redundancy%>", + fun->decl, param_hardcfr_max_blocks); + return false; + } + + return true; + } + virtual unsigned int execute (function *); +}; + +} + +class rt_bb_visited +{ + /* Use a sufficiently wide unsigned type to hold basic block numbers. */ + typedef size_t blknum; + + /* Record the original block count of the function. */ + blknum nblocks; + /* Record the number of bits per VWORD (short for VISITED WORD), an + efficient mode to set and test bits for blocks we visited, and to + encode the CFG in case out-of-line verification is used. */ + unsigned vword_bits; + + /* Hold the unsigned integral VWORD type. */ + tree vword_type; + /* Hold a pointer-to-VWORD type. */ + tree vword_ptr; + + /* Hold a growing sequence used to check, inline or out-of-line, + that VISITED encodes an expected execution path. */ + gimple_seq ckseq; + /* If nonNULL, hold a growing representation of the CFG for + out-of-line testing. */ + tree rtcfg; + + /* Hold the declaration of an array of VWORDs, used as an array of + NBLOCKS-2 bits. */ + tree visited; + + /* If performing inline checking, hold a declarations of boolean + variables used for inline checking. CKBLK holds the result of + testing whether the VISITED bit corresponding to a predecessor or + successor is set, CKINV inverts that bit, CKPART gets cleared if + a block was not visited or if CKINV for any of its predecessors + or successors is set, and CKFAIL gets set if CKPART remains set + at the end of a block's predecessors or successors list. */ + tree ckfail, ckpart, ckinv, ckblk; + + /* Convert a block index N to a block vindex, the index used to + identify it in the VISITED array. Check that it's in range: + neither ENTRY nor EXIT, but maybe one-past-the-end, to compute + the visited array length. */ + blknum num2idx (blknum n) { + gcc_checking_assert (n >= 2 && n <= nblocks); + return (n - 2); + } + /* Return the block vindex for BB, that must not be ENTRY or + EXIT. */ + blknum bb2idx (basic_block bb) { + gcc_checking_assert (bb != ENTRY_BLOCK_PTR_FOR_FN (cfun) + && bb != EXIT_BLOCK_PTR_FOR_FN (cfun)); + gcc_checking_assert (blknum (bb->index) < nblocks); + return num2idx (bb->index); + } + + /* Compute the type to be used for the VISITED array. */ + tree vtype () + { + blknum n = num2idx (nblocks); + return build_array_type_nelts (vword_type, + (n + vword_bits - 1) / vword_bits); + } + + /* Compute and return the index into VISITED for block BB. If BITP + is non-NULL, also compute and store the bit mask corresponding to + block BB in *BITP, so that (visited[index] & mask) tells whether + BB was visited. */ + tree vwordidx (basic_block bb, tree *bitp = NULL) + { + blknum idx = bb2idx (bb); + if (bitp) + { + unsigned bit = idx % vword_bits; + if (BITS_BIG_ENDIAN) + bit = vword_bits - bit - 1; + wide_int wbit = wi::set_bit_in_zero (bit, vword_bits); + *bitp = wide_int_to_tree (vword_type, wbit); + } + return build_int_cst (vword_ptr, idx / vword_bits); + } + + /* Return an expr to accesses the visited element that holds + information about BB. If BITP is non-NULL, set it to the mask to + tell which bit in that expr refers to BB. */ + tree vword (basic_block bb, tree *bitp = NULL) + { + return build2 (MEM_REF, vword_type, + build1 (ADDR_EXPR, vword_ptr, visited), + int_const_binop (MULT_EXPR, vwordidx (bb, bitp), + fold_convert (vword_ptr, + TYPE_SIZE_UNIT + (vword_type)))); + } + + /* Return an expr that evaluates to true iff BB was marked as + VISITED. Add any gimple stmts to SEQP. */ + tree vindex (basic_block bb, gimple_seq *seqp) + { + if (bb == ENTRY_BLOCK_PTR_FOR_FN (cfun) + || bb == EXIT_BLOCK_PTR_FOR_FN (cfun)) + return boolean_true_node; + + tree bit, setme = vword (bb, &bit); + tree temp = create_tmp_var (vword_type, ".cfrtemp"); + + gassign *vload = gimple_build_assign (temp, setme); + gimple_seq_add_stmt (seqp, vload); + + gassign *vmask = gimple_build_assign (temp, BIT_AND_EXPR, temp, bit); + gimple_seq_add_stmt (seqp, vmask); + + return build2 (NE_EXPR, boolean_type_node, + temp, build_int_cst (vword_type, 0)); + } + + /* Set the bit corresponding to BB in VISITED. Add to SEQ any + required gimple statements, and return SEQ, possibly + modified. */ + gimple_seq vset (basic_block bb, gimple_seq seq = NULL) + { + tree bit, setme = vword (bb, &bit); + tree temp = create_tmp_var (vword_type, ".cfrtemp"); + + gassign *vload = gimple_build_assign (temp, setme); + gimple_seq_add_stmt (&seq, vload); + + gassign *vbitset = gimple_build_assign (temp, BIT_IOR_EXPR, temp, bit); + gimple_seq_add_stmt (&seq, vbitset); + + gassign *vstore = gimple_build_assign (unshare_expr (setme), temp); + gimple_seq_add_stmt (&seq, vstore); + + return seq; + } + +public: + /* Prepare to add control flow redundancy testing to CFUN. */ + rt_bb_visited () + : nblocks (n_basic_blocks_for_fn (cfun)), + vword_type (NULL), ckseq (NULL), rtcfg (NULL) + { + /* If we've already added a declaration for the builtin checker, + extract vword_type and vword_bits from its declaration. */ + if (tree checkfn = builtin_decl_explicit (BUILT_IN___HARDCFR_CHECK)) + { + tree check_arg_list = TYPE_ARG_TYPES (TREE_TYPE (checkfn)); + tree vword_const_ptr_type = TREE_VALUE (TREE_CHAIN (check_arg_list)); + vword_type = TYPE_MAIN_VARIANT (TREE_TYPE (vword_const_ptr_type)); + vword_bits = tree_to_shwi (TYPE_SIZE (vword_type)); + } + /* Otherwise, select vword_bits, vword_type et al, and use it to + declare the builtin checker. */ + else + { + /* This setting needs to be kept in sync with libgcc/hardcfr.c. + We aim for at least 28 bits, which enables us to refer to as + many as 28 << 28 blocks in a function's CFG. That's way over + 4G blocks. */ + machine_mode VWORDmode; + if (BITS_PER_UNIT >= 28) + { + VWORDmode = QImode; + vword_bits = BITS_PER_UNIT; + } + else if (BITS_PER_UNIT >= 14) + { + VWORDmode = HImode; + vword_bits = 2 * BITS_PER_UNIT; + } + else + { + VWORDmode = SImode; + vword_bits = 4 * BITS_PER_UNIT; + } + + vword_type = lang_hooks.types.type_for_mode (VWORDmode, 1); + gcc_checking_assert (vword_bits == tree_to_shwi (TYPE_SIZE + (vword_type))); + + vword_type = build_variant_type_copy (vword_type); + TYPE_ALIAS_SET (vword_type) = new_alias_set (); + + tree vword_const = build_qualified_type (vword_type, TYPE_QUAL_CONST); + tree vword_const_ptr = build_pointer_type (vword_const); + tree type = build_function_type_list (void_type_node, sizetype, + vword_const_ptr, vword_const_ptr, + NULL_TREE); + tree decl = add_builtin_function_ext_scope + ("__builtin___hardcfr_check", + type, BUILT_IN___HARDCFR_CHECK, BUILT_IN_NORMAL, + "__hardcfr_check", NULL_TREE); + TREE_NOTHROW (decl) = true; + set_builtin_decl (BUILT_IN___HARDCFR_CHECK, decl, true); + } + + /* The checker uses a qualified pointer, so we can't reuse it, + so build a new one. */ + vword_ptr = build_pointer_type (vword_type); + + tree visited_type = vtype (); + visited = create_tmp_var (visited_type, ".cfrvisited"); + + /* Prevent stores into visited from being used to optimize the + control flow redundancy checks. asm ("" : "+m" (visited)); */ + vec *inputs = NULL; + vec *outputs = NULL; + vec_safe_push (outputs, + build_tree_list + (build_tree_list + (NULL_TREE, build_string (2, "=m")), + visited)); + vec_safe_push (inputs, + build_tree_list + (build_tree_list + (NULL_TREE, build_string (1, "m")), + visited)); + gasm *detach = gimple_build_asm_vec ("", inputs, outputs, + NULL, NULL); + gimple_seq_add_stmt (&ckseq, detach); + + if (nblocks - 2 > blknum (param_hardcfr_max_inline_blocks) + || !single_pred_p (EXIT_BLOCK_PTR_FOR_FN (cfun))) + { + /* Make sure vword_bits is wide enough for the representation + of nblocks in rtcfg. Compare with vword_bits << vword_bits, + but avoiding overflows, shifting nblocks right instead. If + vword_bits is wider than HOST_WIDE_INT, assume it fits, so + as to avoid undefined shifts. */ + gcc_assert (HOST_BITS_PER_WIDE_INT <= vword_bits + || (((unsigned HOST_WIDE_INT)(num2idx (nblocks)) + >> vword_bits) < vword_bits)); + + /* Build a terminator for the constructor list. */ + rtcfg = build_tree_list (NULL_TREE, NULL_TREE); + return; + } + + ckfail = create_tmp_var (boolean_type_node, ".cfrfail"); + ckpart = create_tmp_var (boolean_type_node, ".cfrpart"); + ckinv = create_tmp_var (boolean_type_node, ".cfrinv"); + ckblk = create_tmp_var (boolean_type_node, ".cfrblk"); + + gassign *ckfail_init = gimple_build_assign (ckfail, boolean_false_node); + gimple_seq_add_stmt (&ckseq, ckfail_init); + } + + /* Insert SEQ on E, or close enough (e.g., before a noreturn or tail + call at the end of E->src). */ + void insert_exit_check (gimple_seq seq, edge e) + { + basic_block insbb = e->src; + + /* If the returning block ends with a noreturn call, insert + checking before it. This is particularly important for + __builtin_return. Other noreturn calls won't have an edge to + the exit block, so they won't even be considered as exit paths. + + Insert-on-edge inserts before other return stmts, but not + before calls, and if a single-block function had the check + sequence inserted after a noreturn call, it would be useless, + but checking would still flag it as malformed if block 2 has a + fallthru edge to the exit block. + + Also avoid disrupting tail calls, inserting the check before + them. This works for must-tail calls, but tail calling as an + optimization is detected too late for us. */ + gimple_stmt_iterator gsi = gsi_last_bb (insbb); + gimple *ret = gsi_stmt (gsi); + if (ret && is_a (ret)) + { + gsi_prev (&gsi); + if (!gsi_end_p (gsi)) + ret = gsi_stmt (gsi); + } + if (ret && is_a (ret) + && (gimple_call_noreturn_p (ret) + || gimple_call_must_tail_p (as_a (ret)) + || gimple_call_tail_p (as_a (ret)))) + gsi_insert_seq_before (&gsi, seq, GSI_SAME_STMT); + else + gsi_insert_seq_on_edge_immediate (e, seq); + } + + /* Add checking code on every exit edge, and initialization code on + the entry edge. Before this point, the CFG has been undisturbed, + and all the needed data has been collected and safely stowed. */ + void check () + { + /* Insert initializers for visited at the entry. */ + gimple_seq iseq = NULL; + + gcall *vinit = gimple_build_call (builtin_decl_explicit + (BUILT_IN_MEMSET), 3, + build1 (ADDR_EXPR, + build_pointer_type + (TREE_TYPE (visited)), + visited), + integer_zero_node, + TYPE_SIZE_UNIT (TREE_TYPE (visited))); + gimple_seq_add_stmt (&iseq, vinit); + + gsi_insert_seq_on_edge_immediate (single_succ_edge + (ENTRY_BLOCK_PTR_FOR_FN (cfun)), + iseq); + + /* If we're using out-of-line checking, create and statically + initialize the CFG checking representation, generate the + checker call for the checking sequence, and insert it in all + exit edges, if there's more than one. If there's only one, we + use the same logic as the inline case to insert the check + sequence. */ + if (rtcfg) + { + /* Unreverse the list, and drop the tail node turned into head. */ + rtcfg = TREE_CHAIN (nreverse (rtcfg)); + + /* Turn the indices stored in TREE_PURPOSE into separate + nodes. It was useful to keep them together to enable + combination of masks and for clear separation of + terminators while constructing it, but now we have to turn + it into a sequence of words. */ + for (tree node = rtcfg; node; node = TREE_CHAIN (node)) + { + tree wordidx = TREE_PURPOSE (node); + if (!wordidx) + continue; + + TREE_PURPOSE (node) = NULL_TREE; + TREE_CHAIN (node) = tree_cons (NULL_TREE, + fold_convert (vword_type, wordidx), + TREE_CHAIN (node)); + } + + /* Build the static initializer for the array with the CFG + representation for out-of-line checking. */ + tree init = build_constructor_from_list (NULL_TREE, rtcfg); + TREE_TYPE (init) = build_array_type_nelts (vword_type, + CONSTRUCTOR_NELTS (init)); + char buf[32]; + ASM_GENERATE_INTERNAL_LABEL (buf, "Lhardcfg", + current_function_funcdef_no); + rtcfg = build_decl (UNKNOWN_LOCATION, VAR_DECL, + get_identifier (buf), + TREE_TYPE (init)); + TREE_READONLY (rtcfg) = 1; + TREE_STATIC (rtcfg) = 1; + TREE_ADDRESSABLE (rtcfg) = 1; + TREE_USED (rtcfg) = 1; + DECL_ARTIFICIAL (rtcfg) = 1; + DECL_IGNORED_P (rtcfg) = 1; + DECL_INITIAL (rtcfg) = init; + make_decl_rtl (rtcfg); + varpool_node::finalize_decl (rtcfg); + + /* Add the checker call to ckseq. */ + gcall *call_chk = gimple_build_call (builtin_decl_explicit + (BUILT_IN___HARDCFR_CHECK), 3, + build_int_cst (sizetype, + num2idx (nblocks)), + build1 (ADDR_EXPR, vword_ptr, + visited), + build1 (ADDR_EXPR, vword_ptr, + rtcfg)); + gimple_seq_add_stmt (&ckseq, call_chk); + + /* If we have multiple exit edges, insert (copies of) + ckseq in all of them. */ + for (int i = EDGE_COUNT (EXIT_BLOCK_PTR_FOR_FN (cfun)->preds); + i--; ) + { + gimple_seq seq = ckseq; + /* Copy the sequence, unless we're dealing with the + last edge (we're counting down to zero). */ + if (i) + seq = gimple_seq_copy (seq); + + insert_exit_check (seq, + EDGE_PRED (EXIT_BLOCK_PTR_FOR_FN (cfun), i)); + } + } + else + { + /* Inline checking requires a single exit edge. */ + gimple *last = gsi_stmt (gsi_last (ckseq)); + + insert_exit_check (ckseq, + single_pred_edge (EXIT_BLOCK_PTR_FOR_FN (cfun))); + + /* The inserted ckseq computes CKFAIL at LAST. Now we have to + conditionally trap on it. */ + basic_block insbb = gimple_bb (last); + + /* Create a block with the unconditional trap. */ + basic_block trp = create_empty_bb (insbb); + gimple_stmt_iterator gsit = gsi_after_labels (trp); + + gcall *trap = gimple_build_call (builtin_decl_explicit + (BUILT_IN_TRAP), 0); + gsi_insert_before (&gsit, trap, GSI_SAME_STMT); + + if (BB_PARTITION (insbb)) + BB_SET_PARTITION (trp, BB_COLD_PARTITION); + + if (current_loops) + add_bb_to_loop (trp, current_loops->tree_root); + + /* Insert a conditional branch to the trap block. If the + conditional wouldn't be the last statement, split the + block. */ + gimple_stmt_iterator gsi = gsi_for_stmt (last); + if (!gsi_one_before_end_p (gsi)) + split_block (gsi_bb (gsi), gsi_stmt (gsi)); + + gcond *cond = gimple_build_cond (NE_EXPR, ckfail, + fold_convert (TREE_TYPE (ckfail), + boolean_false_node), + NULL, NULL); + gsi_insert_after (&gsi, cond, GSI_SAME_STMT); + + /* Adjust the edges. */ + single_succ_edge (gsi_bb (gsi))->flags &= ~EDGE_FALLTHRU; + single_succ_edge (gsi_bb (gsi))->flags |= EDGE_FALSE_VALUE; + make_edge (gsi_bb (gsi), trp, EDGE_TRUE_VALUE); + + /* Set the trap's dominator after splitting. */ + if (dom_info_available_p (CDI_DOMINATORS)) + set_immediate_dominator (CDI_DOMINATORS, trp, gimple_bb (last)); + } + } + + /* Push onto RTCFG a (mask, index) pair to test for IBB when BB is + visited. XSELF is to be the ENTRY or EXIT block (depending on + whether we're looking at preds or succs), to be remapped to BB + because we can't represent them, and there's no point in testing + them anyway. Return true if no further blocks need to be visited + in the list, because we've already encountered a + self-reference. */ + bool + push_rtcfg_pair (basic_block ibb, basic_block bb, + basic_block xself) + { + /* We don't have a bit to test for the entry and exit + blocks, but it is always visited, so we test for the + block itself, which gets us the right result and + enables the self-test optimization below. */ + if (ibb == xself) + ibb = bb; + + tree mask, idx = vwordidx (ibb, &mask); + /* Combine masks with the same idx, but not if we're going + to optimize for self-test. */ + if (ibb != bb && TREE_PURPOSE (rtcfg) + && tree_int_cst_equal (idx, TREE_PURPOSE (rtcfg))) + TREE_VALUE (rtcfg) = int_const_binop (BIT_IOR_EXPR, mask, + TREE_VALUE (rtcfg)); + else + rtcfg = tree_cons (idx, mask, rtcfg); + + /* For self-tests (i.e., tests that the block itself was + also visited), testing anything else is pointless, + because it's a tautology, so just drop other edges. */ + if (ibb == bb) + { + while (TREE_PURPOSE (TREE_CHAIN (rtcfg))) + TREE_CHAIN (rtcfg) = TREE_CHAIN (TREE_CHAIN (rtcfg)); + return true; + } + + return false; + } + + /* Add to CKSEQ statements to clear CKPART if OBB is visited. */ + void + build_block_check (basic_block obb) + { + tree vobb = fold_convert (TREE_TYPE (ckblk), + vindex (obb, &ckseq)); + gassign *blkrunp = gimple_build_assign (ckblk, vobb); + gimple_seq_add_stmt (&ckseq, blkrunp); + + gassign *blknotrunp = gimple_build_assign (ckinv, + EQ_EXPR, + ckblk, + fold_convert + (TREE_TYPE (ckblk), + boolean_false_node)); + gimple_seq_add_stmt (&ckseq, blknotrunp); + + gassign *andblk = gimple_build_assign (ckpart, + BIT_AND_EXPR, + ckpart, ckinv); + gimple_seq_add_stmt (&ckseq, andblk); + } + + /* Add to BB code to set its bit in VISITED, and add to RTCFG or + CKSEQ the data or code needed to check BB's predecessors and + successors. Do NOT change the CFG. */ + void visit (basic_block bb) + { + /* Set the bit in VISITED when entering the block. */ + gimple_stmt_iterator gsi = gsi_after_labels (bb); + gsi_insert_seq_before (&gsi, vset (bb), GSI_SAME_STMT); + + if (rtcfg) + { + /* Build a list of (index, mask) terminated by (NULL, 0). + Consolidate masks with the same index when they're + adjacent. First, predecessors. Count backwards, because + we're going to reverse the list. The order shouldn't + matter, but let's not make it surprising. */ + for (int i = EDGE_COUNT (bb->preds); i--; ) + if (push_rtcfg_pair (EDGE_PRED (bb, i)->src, bb, + ENTRY_BLOCK_PTR_FOR_FN (cfun))) + break; + rtcfg = tree_cons (NULL_TREE, build_int_cst (vword_type, 0), rtcfg); + + /* Then, successors. */ + for (int i = EDGE_COUNT (bb->succs); i--; ) + if (push_rtcfg_pair (EDGE_SUCC (bb, i)->dest, bb, + EXIT_BLOCK_PTR_FOR_FN (cfun))) + break; + rtcfg = tree_cons (NULL_TREE, build_int_cst (vword_type, 0), rtcfg); + } + else + { + /* Schedule test to fail if the block was reached but somehow none + of its predecessors were. */ + tree bit = fold_convert (TREE_TYPE (ckpart), vindex (bb, &ckseq)); + gassign *blkrunp = gimple_build_assign (ckpart, bit); + gimple_seq_add_stmt (&ckseq, blkrunp); + + for (int i = 0, e = EDGE_COUNT (bb->preds); i < e; i++) + build_block_check (EDGE_PRED (bb, i)->src); + gimple *orfailp = gimple_build_assign (ckfail, BIT_IOR_EXPR, + ckfail, ckpart); + gimple_seq_add_stmt (&ckseq, orfailp); + + /* Likewise for successors. */ + gassign *blkruns = gimple_build_assign (ckpart, unshare_expr (bit)); + gimple_seq_add_stmt (&ckseq, blkruns); + + for (int i = 0, e = EDGE_COUNT (bb->succs); i < e; i++) + build_block_check (EDGE_SUCC (bb, i)->dest); + + gimple *orfails = gimple_build_assign (ckfail, BIT_IOR_EXPR, + ckfail, ckpart); + gimple_seq_add_stmt (&ckseq, orfails); + } + } +}; + +/* Control flow redundancy hardening: record the execution path, and + verify at exit that an expect path was taken. */ + +unsigned int +pass_harden_control_flow_redundancy::execute (function *) +{ + rt_bb_visited vstd; + + basic_block bb; + FOR_EACH_BB_FN (bb, cfun) + vstd.visit (bb); + + vstd.check (); + + return 0; +} + +/* Instantiate a hardcfr pass. */ + +gimple_opt_pass * +make_pass_harden_control_flow_redundancy (gcc::context *ctxt) +{ + return new pass_harden_control_flow_redundancy (ctxt); +} diff --git a/gcc/params.opt b/gcc/params.opt index b88e1372005..b5dd3a92d06 100644 --- a/gcc/params.opt +++ b/gcc/params.opt @@ -201,6 +201,14 @@ Maximum number of arrays per SCoP. Common Joined UInteger Var(param_graphite_max_nb_scop_params) Init(10) Param Optimization Maximum number of parameters in a SCoP. +-param=hardcfr-max-blocks= +Common Joined UInteger Var(param_hardcfr_max_blocks) Init(0) Param Optimization +Maximum number of blocks for -fharden-control-flow-redundancy. + +-param=hardcfr-max-inline-blocks= +Common Joined UInteger Var(param_hardcfr_max_inline_blocks) Init(16) Param Optimization +Maximum number of blocks for in-line -fharden-control-flow-redundancy. + -param=hash-table-verification-limit= Common Joined UInteger Var(param_hash_table_verification_limit) Init(10) Param The number of elements for which hash table verification is done for each searched element. diff --git a/gcc/passes.def b/gcc/passes.def index 375d3d62d51..7e4eb94fe45 100644 --- a/gcc/passes.def +++ b/gcc/passes.def @@ -191,6 +191,7 @@ along with GCC; see the file COPYING3. If not see NEXT_PASS (pass_omp_device_lower); NEXT_PASS (pass_omp_target_link); NEXT_PASS (pass_adjust_alignment); + NEXT_PASS (pass_harden_control_flow_redundancy); NEXT_PASS (pass_all_optimizations); PUSH_INSERT_PASSES_WITHIN (pass_all_optimizations) NEXT_PASS (pass_remove_cgraph_callee_edges); diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c new file mode 100644 index 00000000000..4aada93ad94 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-abrt.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +int f(int i) { + if (!i) + __builtin_abort (); + return i; +} + +/* No checking before the noreturn abort, so single inline check. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c new file mode 100644 index 00000000000..70acdc95f25 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-bret.c @@ -0,0 +1,11 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +int f(int i) { + if (i) + __builtin_return (&i); + return i; +} + +/* Out-of-line checking, before both builtin_return and return. */ +/* { dg-final { scan-tree-dump-times "__hardcfr_check" 2 "hardcfr" } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c b/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c new file mode 100644 index 00000000000..40d76c5c163 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr-tail.c @@ -0,0 +1,17 @@ +/* { dg-do compile } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr -ffat-lto-objects" } */ + +/* We'd like to check that we insert checking so as to not disrupt tail calls, + but unfortunately mandatory tail calls are not available in C, and optimizing + calls as tail calls only takes place after hardcfr. */ + +extern int g(int i); + +int f(int i) { + return g (i); +} + +/* Inline checking before the tail call. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ +/* Inline checking before the tail call. */ +/* { dg-final { scan-tree-dump-times "\\\[tail\]" 1 "hardcfr" { xfail *-*-* } } } */ diff --git a/gcc/testsuite/c-c++-common/torture/harden-cfr.c b/gcc/testsuite/c-c++-common/torture/harden-cfr.c new file mode 100644 index 00000000000..2f5946c0387 --- /dev/null +++ b/gcc/testsuite/c-c++-common/torture/harden-cfr.c @@ -0,0 +1,81 @@ +/* { dg-do run } */ +/* { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr --param hardcfr-max-blocks=9 --param hardcfr-max-inline-blocks=5 -ffat-lto-objects" } */ + +int +f (int i, int j) +{ + if (i < j) + return 2 * i; + else + return 3 * j; +} + +int +g (unsigned i, int j) +{ + switch (i) + { + case 0: + return j * 2; + + case 1: + return j * 3; + + case 2: + return j * 5; + + default: + return j * 7; + } +} + +int +h (unsigned i, int j) /* { dg-warning "has more than 9 blocks, the requested maximum" } */ +{ + switch (i) + { + case 0: + return j * 2; + + case 1: + return j * 3; + + case 2: + return j * 5; + + case 3: + return j * 7; + + case 4: + return j * 11; + + case 5: + return j * 13; + + case 6: + return j * 17; + + case 7: + return j * 19; + + default: + return j * 23; + } +} + +int +main () +{ + if (f (1, 2) != 2 || f (3, 2) != 6 + || g (2, 5) != 25 || h (4, 3) != 33) + __builtin_abort (); + /* Call exit, instead of returning, to avoid an edge to the exit block and + thus implicitly disable hardening of main. */ + __builtin_exit (0); +} + +/* Inlined checking thus trap for f. */ +/* { dg-final { scan-tree-dump-times "__builtin_trap" 1 "hardcfr" } } */ +/* Out-of-line checking for g. */ +/* { dg-final { scan-tree-dump-times "__hardcfr_check" 1 "hardcfr" } } */ +/* No checking for h (too many blocks) or main (no edges to exit block). */ diff --git a/gcc/testsuite/gnat.dg/hardcfr.adb b/gcc/testsuite/gnat.dg/hardcfr.adb new file mode 100644 index 00000000000..b578a913d75 --- /dev/null +++ b/gcc/testsuite/gnat.dg/hardcfr.adb @@ -0,0 +1,76 @@ +-- { dg-do run } +-- { dg-options "-fharden-control-flow-redundancy -fdump-tree-hardcfr --param=hardcfr-max-blocks=22 --param=hardcfr-max-inline-blocks=12 -O0" } + +procedure HardCFR is + function F (I, J : Integer) return Integer is + begin + if (I < J) then + return 2 * I; + else + return 3 * J; + end if; + end F; + + function G (I : Natural; J : Integer) return Integer is + begin + case I is + when 0 => + return J * 2; + + when 1 => + return J * 3; + + when 2 => + return J * 5; + + when others => + return J * 7; + end case; + end G; + + function H (I : Natural; -- { dg-warning "has more than 22 blocks, the requested maximum" } + J : Integer) + return Integer is + begin + case I is + when 0 => + return J * 2; + + when 1 => + return J * 3; + + when 2 => + return J * 5; + + when 3 => + return J * 7; + + when 4 => + return J * 11; + + when 5 => + return J * 13; + + when 6 => + return J * 17; + + when 7 => + return J * 19; + + when others => + return J * 23; + end case; + end H; +begin + if (F (1, 2) /= 2 or else F (3, 2) /= 6 + or else G (2, 5) /= 25 or else H (4, 3) /= 33) + then + raise Program_Error; + end if; +end HardCFR; + +-- HardCFR and HardCFR.F: +-- { dg-final { scan-tree-dump-times ".builtin_trap" 2 "hardcfr" } } + +-- This is __builtin___hardcfr_check in HardCFR.G: +-- { dg-final { scan-tree-dump-times ".builtin " 1 "hardcfr" } } diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 606d1d60b85..c45648fa2e4 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -647,6 +647,8 @@ extern gimple_opt_pass *make_pass_gimple_isel (gcc::context *ctxt); extern gimple_opt_pass *make_pass_harden_compares (gcc::context *ctxt); extern gimple_opt_pass *make_pass_harden_conditional_branches (gcc::context *ctxt); +extern gimple_opt_pass *make_pass_harden_control_flow_redundancy (gcc::context + *ctxt); /* Current optimization pass. */ extern opt_pass *current_pass; diff --git a/libgcc/Makefile.in b/libgcc/Makefile.in index 09b3ec8bc2e..ff76d29f25b 100644 --- a/libgcc/Makefile.in +++ b/libgcc/Makefile.in @@ -429,6 +429,7 @@ iterator = $(patsubst %,$(srcdir)/static-object.mk,$(iter-items)) endif LIB2ADD += enable-execute-stack.c +LIB2ADD += $(srcdir)/hardcfr.c # While emutls.c has nothing to do with EH, it is in LIB2ADDEH* # instead of LIB2ADD because that's the way to be sure on some targets diff --git a/libgcc/hardcfr.c b/libgcc/hardcfr.c new file mode 100644 index 00000000000..8ef29428111 --- /dev/null +++ b/libgcc/hardcfr.c @@ -0,0 +1,176 @@ +/* Control flow redundancy hardening + Copyright (C) 2022 Free Software Foundation, Inc. + Contributed by Alexandre Oliva + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it under +the terms of the GNU General Public License as published by the Free +Software Foundation; either version 3, or (at your option) any later +version. + +GCC is distributed in the hope that it will be useful, but WITHOUT ANY +WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +Under Section 7 of GPL version 3, you are granted additional +permissions described in the GCC Runtime Library Exception, version +3.1, as published by the Free Software Foundation. + +You should have received a copy of the GNU General Public License and +a copy of the GCC Runtime Library Exception along with this program; +see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +. */ + +/* Avoid infinite recursion. */ +#pragma GCC optimize ("-fno-harden-control-flow-redundancy") + +#include +#include + +/* This should be kept in sync with gcc/gimple-harden-control-flow.cc. */ +#if __CHAR_BIT__ >= 28 +# define VWORDmode __QI__ +#elif __CHHAR_BIT__ >= 14 +# define VWORDmode __HI__ +#else +# define VWORDmode __SI__ +#endif + +typedef unsigned int __attribute__ ((__mode__ (VWORDmode))) vword; + +/* This function is optionally called at the end of a function to verify that + the VISITED array represents a sensible execution path in the CFG. It is + always expected to pass; the purpose is to detect attempts to subvert + execution by taking unexpected paths, or other execution errors. The + function, instrumented by pass_harden_control_flow_redundancy at a time in + which it had BLOCKS basic blocks (not counting ENTER and EXIT, so block 2 + maps to index 0, the first bit of the first VWORD), sets a bit in the bit + array VISITED as it enters the corresponding basic block. CFG holds a + representation of the control flow graph at the time of the instrumentation: + an array of VWORDs holding, for each block, a sequence of predecessors, and + a sequence of successors. Each pred and succ sequence is represented as a + sequence of pairs (mask, index), terminated by an index-less all-zero mask. + If the bit corresponding to the block is set, then at least one of the pred + masks, and at least one of the succ masks, must have a bit set in + VISITED[index]. An ENTRY block predecessor and an EXIT block successor are + represented in a (mask, index) pair that tests the block's own bit. */ +extern void __hardcfr_check (size_t blocks, + vword const *visited, + vword const *cfg); + + +/* Check whether the bit corresponding to BLOCK is set in VISITED. */ +static inline bool +visited_p (size_t const block, vword const *const visited) +{ + size_t wbits = __CHAR_BIT__ * sizeof (vword); + vword w = visited[block / wbits]; + return (w & ((vword)1 << (block % wbits))) != 0; +} + +/* Read and consume a mask from **CFG_IT. (Consume meaning advancing the + iterator to the next word). If the mask is zero, return FALSE. Otherwise, + also read and consume an index, and set *MASK and/or *WORDIDX, whichever are + nonNULL, to the corresponding read values, and finally return TRUE. */ +static inline bool +next_pair (vword const **const cfg_it, + vword *const mask, + size_t *const wordidx) +{ + vword m = **cfg_it; + ++*cfg_it; + if (!m) + return false; + + if (mask) + *mask = m; + + size_t word = **cfg_it; + ++*cfg_it; + + if (wordidx) + *wordidx = word; + + return true; +} + +/* Return TRUE iff any of the bits in MASK is set in VISITED[WORDIDX]. */ +static inline bool +test_mask (vword const *const visited, + vword const mask, size_t const wordidx) +{ + return (visited[wordidx] & mask) != 0; +} + +/* Scan a sequence of pairs (mask, index) at **CFG_IT until its terminator is + reached and consumed. */ +static inline void +consume_seq (vword const **const cfg_it) +{ + while (next_pair (cfg_it, NULL, NULL)) + /* Do nothing. */; +} + +/* Check that at least one of the MASK bits in a sequence of pairs (mask, + index) at **CFG_IT is set in the corresponding VISITED[INDEX] word. Trap if + we reach the terminator without finding any. Consume the entire sequence + otherwise, so that *CFG_IT points just past the terminator, which may be the + beginning of the next sequence. */ +static inline void +check_seq (vword const *const visited, vword const **const cfg_it) +{ + vword mask; + size_t wordidx; + + /* If the block was visited, check that at least one of the + preds was also visited. */ + do + /* If we get to the end of the sequence without finding any + match, something is amiss. */ + if (!next_pair (cfg_it, &mask, &wordidx)) + __builtin_trap (); + /* Keep searching until we find a match, at which point the + condition is satisfied. */ + while (!test_mask (visited, mask, wordidx)); + + /* Consume the remaining entries in the sequence, whether we found a match or + skipped the block, so as to position the iterator at the beginning of the + next . */ + consume_seq (cfg_it); +} + +/* Check that, for each of the BLOCKS basic blocks, if its bit is set in + VISITED, at least one of its predecessors in CFG is also set, and at also + that at least one of its successors in CFG is also set. */ +void +__hardcfr_check (size_t const blocks, + vword const *const visited, + vword const *const cfg) +{ + vword const *cfg_it = cfg; + for (size_t i = 0; i < blocks; i++) + { + bool v = visited_p (i, visited); + + /* For each block, there are two sequences of pairs (mask, index), each + sequence terminated by a single all-zero mask (no index). The first + sequence is for predecessor blocks, the second is for successors. At + least one of each must be set. */ + if (!v) + { + /* Consume predecessors. */ + consume_seq (&cfg_it); + /* Consume successors. */ + consume_seq (&cfg_it); + } + else + { + /* Check predecessors. */ + check_seq (visited, &cfg_it); + /* Check successors. */ + check_seq (visited, &cfg_it); + } + } +}