diff options
Diffstat (limited to 'gcc')
| -rw-r--r-- | gcc/Makefile.in | 1 | ||||
| -rw-r--r-- | gcc/analyzer/analyzer.h | 51 | ||||
| -rw-r--r-- | gcc/analyzer/call-info.cc | 162 | ||||
| -rw-r--r-- | gcc/analyzer/call-info.h | 83 | ||||
| -rw-r--r-- | gcc/analyzer/engine.cc | 271 | ||||
| -rw-r--r-- | gcc/analyzer/exploded-graph.h | 62 | ||||
| -rw-r--r-- | gcc/analyzer/program-state.cc | 6 | ||||
| -rw-r--r-- | gcc/analyzer/region-model-impl-calls.cc | 176 | ||||
| -rw-r--r-- | gcc/analyzer/region-model.cc | 28 | ||||
| -rw-r--r-- | gcc/analyzer/region-model.h | 36 | ||||
| -rw-r--r-- | gcc/analyzer/sm-malloc.cc | 136 | ||||
| -rw-r--r-- | gcc/analyzer/sm-signal.cc | 15 | ||||
| -rw-r--r-- | gcc/analyzer/sm.h | 5 | ||||
| -rw-r--r-- | gcc/analyzer/svalue.cc | 3 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/capacity-2.c | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr99193-1.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/pr99193-3.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/realloc-1.c | 47 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/analyzer/realloc-2.c | 80 |
19 files changed, 1042 insertions, 132 deletions
diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 9714fca..f0c560f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -1249,6 +1249,7 @@ ANALYZER_OBJS = \ analyzer/analyzer-pass.o \ analyzer/analyzer-selftests.o \ analyzer/bar-chart.o \ + analyzer/call-info.o \ analyzer/call-string.o \ analyzer/checker-path.o \ analyzer/complexity.o \ diff --git a/gcc/analyzer/analyzer.h b/gcc/analyzer/analyzer.h index 05d4751..7ad1081 100644 --- a/gcc/analyzer/analyzer.h +++ b/gcc/analyzer/analyzer.h @@ -220,6 +220,57 @@ enum access_direction DIR_WRITE }; +/* Abstract base class for associating custom data with an + exploded_edge, for handling non-standard edges such as + rewinding from a longjmp, signal handlers, etc. + Also used when "bifurcating" state: splitting the execution + path in non-standard ways (e.g. for simulating the various + outcomes of "realloc"). */ + +class custom_edge_info +{ +public: + virtual ~custom_edge_info () {} + + /* Hook for making .dot label more readable. */ + virtual void print (pretty_printer *pp) const = 0; + + /* Hook for updating MODEL within exploded_path::feasible_p + and when handling bifurcation. */ + virtual bool update_model (region_model *model, + const exploded_edge *eedge, + region_model_context *ctxt) const = 0; + + virtual void add_events_to_path (checker_path *emission_path, + const exploded_edge &eedge) const = 0; +}; + +/* Abstract base class for splitting state. + + Most of the state-management code in the analyzer involves + modifying state objects in-place, which assumes a single outcome. + + This class provides an escape hatch to allow for multiple outcomes + for such updates e.g. for modelling multiple outcomes from function + calls, such as the various outcomes of "realloc". */ + +class path_context +{ +public: + virtual ~path_context () {} + + /* Hook for clients to split state with a non-standard path. + Take ownership of INFO. */ + virtual void bifurcate (custom_edge_info *info) = 0; + + /* Hook for clients to terminate the standard path. */ + virtual void terminate_path () = 0; + + /* Hook for clients to determine if the standard path has been + terminated. */ + virtual bool terminate_path_p () const = 0; +}; + } // namespace ana extern bool is_special_named_call_p (const gcall *call, const char *funcname, diff --git a/gcc/analyzer/call-info.cc b/gcc/analyzer/call-info.cc new file mode 100644 index 0000000..1d44cb8 --- /dev/null +++ b/gcc/analyzer/call-info.cc @@ -0,0 +1,162 @@ +/* Subclasses of custom_edge_info for describing outcomes of function calls. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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 +<http://www.gnu.org/licenses/>. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tree.h" +#include "function.h" +#include "basic-block.h" +#include "gimple.h" +#include "gimple-iterator.h" +#include "diagnostic-core.h" +#include "options.h" +#include "cgraph.h" +#include "tree-pretty-print.h" +#include "tristate.h" +#include "bitmap.h" +#include "selftest.h" +#include "function.h" +#include "json.h" +#include "analyzer/analyzer.h" +#include "analyzer/analyzer-logging.h" +#include "ordered-hash-map.h" +#include "cfg.h" +#include "digraph.h" +#include "analyzer/supergraph.h" +#include "sbitmap.h" +#include "analyzer/call-string.h" +#include "analyzer/program-point.h" +#include "analyzer/store.h" +#include "analyzer/region-model.h" +#include "analyzer/constraint-manager.h" +#include "diagnostic-event-id.h" +#include "analyzer/sm.h" +#include "analyzer/pending-diagnostic.h" +#include "analyzer/region-model-reachability.h" +#include "analyzer/analyzer-selftests.h" +#include "analyzer/program-state.h" +#include "diagnostic-path.h" +#include "analyzer/checker-path.h" +#include "analyzer/diagnostic-manager.h" +#include "alloc-pool.h" +#include "fibonacci_heap.h" +#include "shortest-paths.h" +#include "analyzer/exploded-graph.h" +#include "analyzer/call-info.h" + +#if ENABLE_ANALYZER + +namespace ana { + +/* class call_info : public custom_eedge_info_t. */ + +/* Implementation of custom_edge_info::print vfunc for call_info: + use get_desc to get a label_text, and print it to PP. */ + +void +call_info::print (pretty_printer *pp) const +{ + label_text desc (get_desc (pp_show_color (pp))); + pp_string (pp, desc.m_buffer); + desc.maybe_free (); +} + +/* Implementation of custom_edge_info::add_events_to_path vfunc for + call_info: add a custom_event using call_info::get_desc as its + description. */ + +void +call_info::add_events_to_path (checker_path *emission_path, + const exploded_edge &eedge) const +{ + class call_event : public custom_event + { + public: + call_event (location_t loc, tree fndecl, int depth, + const call_info *call_info) + : custom_event (loc, fndecl, depth), + m_call_info (call_info) + {} + + label_text get_desc (bool can_colorize) const + { + return m_call_info->get_desc (can_colorize); + } + + private: + const call_info *m_call_info; + }; + + const exploded_node *src_node = eedge.m_src; + const program_point &src_point = src_node->get_point (); + tree caller_fndecl = src_point.get_fndecl (); + const int stack_depth = src_point.get_stack_depth (); + + emission_path->add_event (new call_event (get_call_stmt ()->location, + caller_fndecl, + stack_depth, + this)); +} + +/* Recreate a call_details instance from this call_info. */ + +call_details +call_info::get_call_details (region_model *model, + region_model_context *ctxt) const +{ + return call_details (m_call_stmt, model, ctxt); +} + +/* call_info's ctor. + + The call_info instance will outlive the call_details instance; + call_details instances are typically created on the stack. */ + +call_info::call_info (const call_details &cd) +: m_call_stmt (cd.get_call_stmt ()), + m_fndecl (cd.get_fndecl_for_call ()) +{ + gcc_assert (m_fndecl); +} + +/* class success_call_info : public call_info. */ + +/* Implementation of call_info::get_desc vfunc for success_call_info. */ + +label_text +success_call_info::get_desc (bool can_colorize) const +{ + return make_label_text (can_colorize, "when %qE succeeds", get_fndecl ()); +} + +/* class failed_call_info : public call_info. */ + +/* Implementation of call_info::get_desc vfunc for failed_call_info. */ + +label_text +failed_call_info::get_desc (bool can_colorize) const +{ + return make_label_text (can_colorize, "when %qE fails", get_fndecl ()); +} + +} // namespace ana + +#endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/call-info.h b/gcc/analyzer/call-info.h new file mode 100644 index 0000000..369d217 --- /dev/null +++ b/gcc/analyzer/call-info.h @@ -0,0 +1,83 @@ +/* Subclasses of custom_edge_info for describing outcomes of function calls. + Copyright (C) 2021 Free Software Foundation, Inc. + Contributed by David Malcolm <dmalcolm@redhat.com>. + +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 +<http://www.gnu.org/licenses/>. */ + +#ifndef GCC_ANALYZER_CALL_INFO_H +#define GCC_ANALYZER_CALL_INFO_H + +namespace ana { + +/* Subclass of custom_edge_info for an outcome of a call. + This is still abstract; the update_model and get_desc vfuncs must be + implemented. */ + +class call_info : public custom_edge_info +{ +public: + void print (pretty_printer *pp) const FINAL OVERRIDE; + void add_events_to_path (checker_path *emission_path, + const exploded_edge &eedge) const FINAL OVERRIDE; + + const gcall *get_call_stmt () const { return m_call_stmt; } + tree get_fndecl () const { return m_fndecl; } + + virtual label_text get_desc (bool can_colorize) const = 0; + + call_details get_call_details (region_model *model, + region_model_context *ctxt) const; + +protected: + call_info (const call_details &cd); + +private: + const gcall *m_call_stmt; + tree m_fndecl; +}; + +/* Subclass of call_info for a "success" outcome of a call, + adding a "when `FNDECL' succeeds" message. + This is still abstract: the custom_edge_info::update_model vfunc + must be implemented. */ + +class success_call_info : public call_info +{ +public: + label_text get_desc (bool can_colorize) const FINAL OVERRIDE; + +protected: + success_call_info (const call_details &cd) : call_info (cd) {} +}; + +/* Subclass of call_info for a "failure" outcome of a call, + adding a "when `FNDECL' fails" message. + This is still abstract: the custom_edge_info::update_model vfunc + must be implemented. */ + +class failed_call_info : public call_info +{ +public: + label_text get_desc (bool can_colorize) const FINAL OVERRIDE; + +protected: + failed_call_info (const call_details &cd) : call_info (cd) {} +}; + +} // namespace ana + +#endif /* GCC_ANALYZER_CALL_INFO_H */ diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 9c604d1..24f0931 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -62,9 +62,11 @@ along with GCC; see the file COPYING3. If not see #include "analyzer/checker-path.h" #include "analyzer/state-purge.h" #include "analyzer/bar-chart.h" +#include "analyzer/call-info.h" #include <zlib.h> #include "plugin.h" #include "target.h" +#include <memory> /* For an overview, see gcc/doc/analyzer.texi. */ @@ -80,6 +82,7 @@ impl_region_model_context (exploded_graph &eg, const program_state *old_state, program_state *new_state, uncertainty_t *uncertainty, + path_context *path_ctxt, const gimple *stmt, stmt_finder *stmt_finder) : m_eg (&eg), m_logger (eg.get_logger ()), @@ -89,7 +92,8 @@ impl_region_model_context (exploded_graph &eg, m_stmt (stmt), m_stmt_finder (stmt_finder), m_ext_state (eg.get_ext_state ()), - m_uncertainty (uncertainty) + m_uncertainty (uncertainty), + m_path_ctxt (path_ctxt) { } @@ -104,7 +108,8 @@ impl_region_model_context (program_state *state, m_stmt (NULL), m_stmt_finder (NULL), m_ext_state (ext_state), - m_uncertainty (uncertainty) + m_uncertainty (uncertainty), + m_path_ctxt (NULL) { } @@ -183,6 +188,37 @@ impl_region_model_context::purge_state_involving (const svalue *sval) smap->purge_state_involving (sval, m_ext_state); } +void +impl_region_model_context::bifurcate (custom_edge_info *info) +{ + if (m_path_ctxt) + m_path_ctxt->bifurcate (info); + else + delete info; +} + +void +impl_region_model_context::terminate_path () +{ + if (m_path_ctxt) + return m_path_ctxt->terminate_path (); +} + +bool +impl_region_model_context::get_malloc_map (sm_state_map **out_smap, + const state_machine **out_sm, + unsigned *out_sm_idx) +{ + unsigned malloc_sm_idx; + if (!m_ext_state.get_sm_idx_by_name ("malloc", &malloc_sm_idx)) + return false; + + *out_smap = m_new_state->m_checker_states[malloc_sm_idx]; + *out_sm = &m_ext_state.get_sm (malloc_sm_idx); + *out_sm_idx = malloc_sm_idx; + return true; +} + /* struct setjmp_record. */ int @@ -237,12 +273,14 @@ public: program_state *new_state, const sm_state_map *old_smap, sm_state_map *new_smap, + path_context *path_ctxt, stmt_finder *stmt_finder = NULL) : sm_context (sm_idx, sm), m_logger (eg.get_logger ()), m_eg (eg), m_enode_for_diag (enode_for_diag), m_old_state (old_state), m_new_state (new_state), m_old_smap (old_smap), m_new_smap (new_smap), + m_path_ctxt (path_ctxt), m_stmt_finder (stmt_finder) { } @@ -252,7 +290,7 @@ public: tree get_fndecl_for_call (const gcall *call) FINAL OVERRIDE { impl_region_model_context old_ctxt - (m_eg, m_enode_for_diag, NULL, NULL/*m_enode->get_state ()*/, + (m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/, NULL, call); region_model *model = m_new_state->m_region_model; return model->get_fndecl_for_call (call, &old_ctxt); @@ -292,7 +330,7 @@ public: LOG_FUNC (logger); impl_region_model_context new_ctxt (m_eg, m_enode_for_diag, m_old_state, m_new_state, - NULL, + NULL, NULL, stmt); const svalue *var_new_sval = m_new_state->m_region_model->get_rvalue (var, &new_ctxt); @@ -320,12 +358,12 @@ public: logger * const logger = get_logger (); LOG_FUNC (logger); impl_region_model_context old_ctxt - (m_eg, m_enode_for_diag, NULL, NULL/*m_enode->get_state ()*/, + (m_eg, m_enode_for_diag, NULL, NULL, NULL/*m_enode->get_state ()*/, NULL, stmt); impl_region_model_context new_ctxt (m_eg, m_enode_for_diag, m_old_state, m_new_state, - NULL, + NULL, NULL, stmt); const svalue *origin_new_sval = m_new_state->m_region_model->get_rvalue (origin, &new_ctxt); @@ -353,7 +391,7 @@ public: LOG_FUNC (get_logger ()); gcc_assert (d); // take ownership impl_region_model_context old_ctxt - (m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, NULL); + (m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, NULL, NULL); const svalue *var_old_sval = m_old_state->m_region_model->get_rvalue (var, &old_ctxt); @@ -418,7 +456,7 @@ public: if (!assign_stmt) return NULL_TREE; impl_region_model_context old_ctxt - (m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, stmt); + (m_eg, m_enode_for_diag, m_old_state, m_new_state, NULL, NULL, stmt); if (const svalue *sval = m_new_state->m_region_model->get_gassign_result (assign_stmt, &old_ctxt)) @@ -428,6 +466,11 @@ public: return NULL_TREE; } + path_context *get_path_context () const FINAL OVERRIDE + { + return m_path_ctxt; + } + log_user m_logger; exploded_graph &m_eg; exploded_node *m_enode_for_diag; @@ -435,6 +478,7 @@ public: program_state *m_new_state; const sm_state_map *m_old_smap; sm_state_map *m_new_smap; + path_context *m_path_ctxt; stmt_finder *m_stmt_finder; }; @@ -751,9 +795,13 @@ impl_region_model_context::on_condition (const svalue *lhs, impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag, m_old_state, m_new_state, m_old_state->m_checker_states[sm_idx], - m_new_state->m_checker_states[sm_idx]); + m_new_state->m_checker_states[sm_idx], + m_path_ctxt); sm.on_condition (&sm_ctxt, - m_enode_for_diag->get_supernode (), m_stmt, + (m_enode_for_diag + ? m_enode_for_diag->get_supernode () + : NULL), + m_stmt, lhs, op, rhs); } } @@ -773,7 +821,8 @@ impl_region_model_context::on_phi (const gphi *phi, tree rhs) impl_sm_context sm_ctxt (*m_eg, sm_idx, sm, m_enode_for_diag, m_old_state, m_new_state, m_old_state->m_checker_states[sm_idx], - m_new_state->m_checker_states[sm_idx]); + m_new_state->m_checker_states[sm_idx], + m_path_ctxt); sm.on_phi (&sm_ctxt, m_enode_for_diag->get_supernode (), phi, rhs); } } @@ -1190,7 +1239,8 @@ exploded_node::on_stmt (exploded_graph &eg, const supernode *snode, const gimple *stmt, program_state *state, - uncertainty_t *uncertainty) + uncertainty_t *uncertainty, + path_context *path_ctxt) { logger *logger = eg.get_logger (); LOG_SCOPE (logger); @@ -1215,7 +1265,7 @@ exploded_node::on_stmt (exploded_graph &eg, impl_region_model_context ctxt (eg, this, &old_state, state, uncertainty, - stmt); + path_ctxt, stmt); bool unknown_side_effects = false; bool terminate_path = false; @@ -1235,13 +1285,16 @@ exploded_node::on_stmt (exploded_graph &eg, = old_state.m_checker_states[sm_idx]; sm_state_map *new_smap = state->m_checker_states[sm_idx]; impl_sm_context sm_ctxt (eg, sm_idx, sm, this, &old_state, state, - old_smap, new_smap); + old_smap, new_smap, path_ctxt); /* Allow the state_machine to handle the stmt. */ if (sm.on_stmt (&sm_ctxt, snode, stmt)) unknown_side_effects = false; } + if (path_ctxt->terminate_path_p ()) + return on_stmt_flags::terminate_path (); + on_stmt_post (stmt, state, unknown_side_effects, &ctxt); return on_stmt_flags (); @@ -1592,7 +1645,7 @@ exploded_node::detect_leaks (exploded_graph &eg) uncertainty_t uncertainty; impl_region_model_context ctxt (eg, this, - &old_state, &new_state, &uncertainty, + &old_state, &new_state, &uncertainty, NULL, get_stmt ()); const svalue *result = NULL; new_state.m_region_model->pop_frame (NULL, &result, &ctxt); @@ -1627,27 +1680,30 @@ exploded_node::dump_succs_and_preds (FILE *outf) const } } -/* class dynamic_call_info_t : public exploded_edge::custom_info_t. */ +/* class dynamic_call_info_t : public custom_edge_info. */ -/* Implementation of exploded_edge::custom_info_t::update_model vfunc +/* Implementation of custom_edge_info::update_model vfunc for dynamic_call_info_t. Update state for the dynamically discorverd calls */ -void +bool dynamic_call_info_t::update_model (region_model *model, - const exploded_edge &eedge) + const exploded_edge *eedge, + region_model_context *) const { - const program_state &dest_state = eedge.m_dest->get_state (); + gcc_assert (eedge); + const program_state &dest_state = eedge->m_dest->get_state (); *model = *dest_state.m_region_model; + return true; } -/* Implementation of exploded_edge::custom_info_t::add_events_to_path vfunc +/* Implementation of custom_edge_info::add_events_to_path vfunc for dynamic_call_info_t. */ void dynamic_call_info_t::add_events_to_path (checker_path *emission_path, - const exploded_edge &eedge) + const exploded_edge &eedge) const { const exploded_node *src_node = eedge.m_src; const program_point &src_point = src_node->get_point (); @@ -1671,21 +1727,23 @@ dynamic_call_info_t::add_events_to_path (checker_path *emission_path, } -/* class rewind_info_t : public exploded_edge::custom_info_t. */ +/* class rewind_info_t : public custom_edge_info. */ -/* Implementation of exploded_edge::custom_info_t::update_model vfunc +/* Implementation of custom_edge_info::update_model vfunc for rewind_info_t. Update state for the special-case of a rewind of a longjmp to a setjmp (which doesn't have a superedge, but does affect state). */ -void +bool rewind_info_t::update_model (region_model *model, - const exploded_edge &eedge) + const exploded_edge *eedge, + region_model_context *) const { - const program_point &longjmp_point = eedge.m_src->get_point (); - const program_point &setjmp_point = eedge.m_dest->get_point (); + gcc_assert (eedge); + const program_point &longjmp_point = eedge->m_src->get_point (); + const program_point &setjmp_point = eedge->m_dest->get_point (); gcc_assert (longjmp_point.get_stack_depth () >= setjmp_point.get_stack_depth ()); @@ -1693,14 +1751,15 @@ rewind_info_t::update_model (region_model *model, model->on_longjmp (get_longjmp_call (), get_setjmp_call (), setjmp_point.get_stack_depth (), NULL); + return true; } -/* Implementation of exploded_edge::custom_info_t::add_events_to_path vfunc +/* Implementation of custom_edge_info::add_events_to_path vfunc for rewind_info_t. */ void rewind_info_t::add_events_to_path (checker_path *emission_path, - const exploded_edge &eedge) + const exploded_edge &eedge) const { const exploded_node *src_node = eedge.m_src; const program_point &src_point = src_node->get_point (); @@ -1727,7 +1786,7 @@ rewind_info_t::add_events_to_path (checker_path *emission_path, exploded_edge::exploded_edge (exploded_node *src, exploded_node *dest, const superedge *sedge, - custom_info_t *custom_info) + custom_edge_info *custom_info) : dedge<eg_traits> (src, dest), m_sedge (sedge), m_custom_info (custom_info) { @@ -2432,7 +2491,7 @@ exploded_graph::get_or_create_node (const program_point &point, exploded_edge * exploded_graph::add_edge (exploded_node *src, exploded_node *dest, const superedge *sedge, - exploded_edge::custom_info_t *custom_info) + custom_edge_info *custom_info) { if (get_logger ()) get_logger ()->log ("creating edge EN: %i -> EN: %i", @@ -2866,7 +2925,7 @@ maybe_process_run_of_before_supernode_enodes (exploded_node *enode) uncertainty_t uncertainty; impl_region_model_context ctxt (*this, iter_enode, &state, next_state, - &uncertainty, NULL); + &uncertainty, NULL, NULL); const cfg_superedge *last_cfg_superedge = iter_sedge->dyn_cast_cfg_superedge (); if (last_cfg_superedge) @@ -3095,6 +3154,72 @@ exploded_graph::maybe_create_dynamic_call (const gcall *call, return false; } +/* Subclass of path_context for use within exploded_graph::process_node, + so that we can split states e.g. at "realloc" calls. */ + +class impl_path_context : public path_context +{ +public: + impl_path_context (const program_state *cur_state) + : m_cur_state (cur_state), + m_terminate_path (false) + { + } + + bool bifurcation_p () const + { + return m_custom_eedge_infos.length () > 0; + } + + const program_state &get_state_at_bifurcation () const + { + gcc_assert (m_state_at_bifurcation); + return *m_state_at_bifurcation; + } + + void + bifurcate (custom_edge_info *info) FINAL OVERRIDE + { + if (m_state_at_bifurcation) + /* Verify that the state at bifurcation is consistent when we + split into multiple out-edges. */ + gcc_assert (*m_state_at_bifurcation == *m_cur_state); + else + /* Take a copy of the cur_state at the moment when bifurcation + happens. */ + m_state_at_bifurcation + = std::unique_ptr<program_state> (new program_state (*m_cur_state)); + + /* Take ownership of INFO. */ + m_custom_eedge_infos.safe_push (info); + } + + void terminate_path () FINAL OVERRIDE + { + m_terminate_path = true; + } + + bool terminate_path_p () const FINAL OVERRIDE + { + return m_terminate_path; + } + + const vec<custom_edge_info *> & get_custom_eedge_infos () + { + return m_custom_eedge_infos; + } + +private: + const program_state *m_cur_state; + + /* Lazily-created copy of the state before the split. */ + std::unique_ptr<program_state> m_state_at_bifurcation; + + auto_vec <custom_edge_info *> m_custom_eedge_infos; + + bool m_terminate_path; +}; + /* The core of exploded_graph::process_worklist (the main analysis loop), handling one node in the worklist. @@ -3150,7 +3275,7 @@ exploded_graph::process_node (exploded_node *node) { impl_region_model_context ctxt (*this, node, &state, &next_state, - &uncertainty, NULL); + &uncertainty, NULL, NULL); const cfg_superedge *last_cfg_superedge = point.get_from_edge ()->dyn_cast_cfg_superedge (); if (last_cfg_superedge) @@ -3188,6 +3313,9 @@ exploded_graph::process_node (exploded_node *node) the sm-state-change occurs on an edge where the src enode has exactly one stmt, the one that caused the change. */ program_state next_state (state); + + impl_path_context path_ctxt (&next_state); + uncertainty_t uncertainty; const supernode *snode = point.get_supernode (); unsigned stmt_idx; @@ -3210,7 +3338,8 @@ exploded_graph::process_node (exploded_node *node) /* Process the stmt. */ exploded_node::on_stmt_flags flags - = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty); + = node->on_stmt (*this, snode, stmt, &next_state, &uncertainty, + &path_ctxt); node->m_num_processed_stmts++; /* If flags.m_terminate_path, stop analyzing; any nodes/edges @@ -3222,7 +3351,7 @@ exploded_graph::process_node (exploded_node *node) { impl_region_model_context ctxt (*this, node, &old_state, &next_state, - &uncertainty, stmt); + &uncertainty, NULL, stmt); program_state::detect_leaks (old_state, next_state, NULL, get_ext_state (), &ctxt); } @@ -3238,7 +3367,9 @@ exploded_graph::process_node (exploded_node *node) &uncertainty); if (flag_analyzer_fine_grained - || state_change_requires_new_enode_p (old_state, next_state)) + || state_change_requires_new_enode_p (old_state, next_state) + || path_ctxt.bifurcation_p () + || path_ctxt.terminate_path_p ()) { program_point split_point = program_point::before_stmt (point.get_supernode (), @@ -3282,9 +3413,66 @@ exploded_graph::process_node (exploded_node *node) point.get_call_string ()) : program_point::after_supernode (point.get_supernode (), point.get_call_string ())); - exploded_node *next = get_or_create_node (next_point, next_state, node); - if (next) - add_edge (node, next, NULL); + if (path_ctxt.terminate_path_p ()) + { + if (logger) + logger->log ("not adding node: terminating path"); + } + else + { + exploded_node *next + = get_or_create_node (next_point, next_state, node); + if (next) + add_edge (node, next, NULL); + } + + /* If we have custom edge infos, "bifurcate" the state + accordingly, potentially creating a new state/enode/eedge + instances. For example, to handle a "realloc" call, we + might split into 3 states, for the "failure", + "resizing in place", and "moving to a new buffer" cases. */ + for (auto edge_info : path_ctxt.get_custom_eedge_infos ()) + { + if (logger) + { + logger->start_log_line (); + logger->log_partial ("bifurcating for edge: "); + edge_info->print (logger->get_printer ()); + logger->end_log_line (); + } + program_state bifurcated_new_state + (path_ctxt.get_state_at_bifurcation ()); + + /* Apply edge_info to state. */ + impl_region_model_context + bifurcation_ctxt (*this, + NULL, // enode_for_diag + &path_ctxt.get_state_at_bifurcation (), + &bifurcated_new_state, + NULL, // uncertainty_t *uncertainty + NULL, // path_context *path_ctxt + stmt); + if (edge_info->update_model (bifurcated_new_state.m_region_model, + NULL, /* no exploded_edge yet. */ + &bifurcation_ctxt)) + { + exploded_node *next2 + = get_or_create_node (next_point, bifurcated_new_state, node); + if (next2) + { + /* Take ownership of edge_info. */ + add_edge (node, next2, NULL, edge_info); + } + else + delete edge_info; + } + else + { + if (logger) + logger->log ("infeasible state, not adding node"); + delete edge_info; + } + } } break; case PK_AFTER_SUPERNODE: @@ -3351,6 +3539,7 @@ exploded_graph::process_node (exploded_node *node) &state, &next_state, &uncertainty, + NULL, point.get_stmt()); region_model *model = state.m_region_model; @@ -3968,7 +4157,7 @@ feasibility_state::maybe_update_for_edge (logger *logger, } else if (eedge->m_custom_info) { - eedge->m_custom_info->update_model (&m_model, *eedge); + eedge->m_custom_info->update_model (&m_model, eedge, NULL); } } diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index 6890e84..b9c1767 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -37,6 +37,7 @@ class impl_region_model_context : public region_model_context const program_state *old_state, program_state *new_state, uncertainty_t *uncertainty, + path_context *path_ctxt, const gimple *stmt, stmt_finder *stmt_finder = NULL); @@ -76,6 +77,16 @@ class impl_region_model_context : public region_model_context void purge_state_involving (const svalue *sval) FINAL OVERRIDE; + void bifurcate (custom_edge_info *info) FINAL OVERRIDE; + void terminate_path () FINAL OVERRIDE; + const extrinsic_state *get_ext_state () const FINAL OVERRIDE + { + return &m_ext_state; + } + bool get_malloc_map (sm_state_map **out_smap, + const state_machine **out_sm, + unsigned *out_sm_idx) FINAL OVERRIDE; + exploded_graph *m_eg; log_user m_logger; exploded_node *m_enode_for_diag; @@ -85,6 +96,7 @@ class impl_region_model_context : public region_model_context stmt_finder *m_stmt_finder; const extrinsic_state &m_ext_state; uncertainty_t *m_uncertainty; + path_context *m_path_ctxt; }; /* A <program_point, program_state> pair, used internally by @@ -224,7 +236,8 @@ class exploded_node : public dnode<eg_traits> const supernode *snode, const gimple *stmt, program_state *state, - uncertainty_t *uncertainty); + uncertainty_t *uncertainty, + path_context *path_ctxt); void on_stmt_pre (exploded_graph &eg, const gimple *stmt, program_state *state, @@ -319,28 +332,9 @@ public: class exploded_edge : public dedge<eg_traits> { public: - /* Abstract base class for associating custom data with an - exploded_edge, for handling non-standard edges such as - rewinding from a longjmp, signal handlers, etc. */ - class custom_info_t - { - public: - virtual ~custom_info_t () {} - - /* Hook for making .dot label more readable . */ - virtual void print (pretty_printer *pp) = 0; - - /* Hook for updating MODEL within exploded_path::feasible_p. */ - virtual void update_model (region_model *model, - const exploded_edge &eedge) = 0; - - virtual void add_events_to_path (checker_path *emission_path, - const exploded_edge &eedge) = 0; - }; - exploded_edge (exploded_node *src, exploded_node *dest, const superedge *sedge, - custom_info_t *custom_info); + custom_edge_info *custom_info); ~exploded_edge (); void dump_dot (graphviz_out *gv, const dump_args_t &args) const FINAL OVERRIDE; @@ -356,7 +350,7 @@ class exploded_edge : public dedge<eg_traits> a signal is delivered to a signal-handler. Owned by this class. */ - custom_info_t *m_custom_info; + custom_edge_info *m_custom_info; private: DISABLE_COPY_AND_ASSIGN (exploded_edge); @@ -365,7 +359,7 @@ private: /* Extra data for an exploded_edge that represents dynamic call info ( calls that doesn't have an underlying superedge representing the call ). */ -class dynamic_call_info_t : public exploded_edge::custom_info_t +class dynamic_call_info_t : public custom_edge_info { public: dynamic_call_info_t (const gcall *dynamic_call, @@ -374,7 +368,7 @@ public: m_is_returning_call (is_returning_call) {} - void print (pretty_printer *pp) FINAL OVERRIDE + void print (pretty_printer *pp) const FINAL OVERRIDE { if (m_is_returning_call) pp_string (pp, "dynamic_return"); @@ -382,11 +376,12 @@ public: pp_string (pp, "dynamic_call"); } - void update_model (region_model *model, - const exploded_edge &eedge) FINAL OVERRIDE; + bool update_model (region_model *model, + const exploded_edge *eedge, + region_model_context *ctxt) const FINAL OVERRIDE; void add_events_to_path (checker_path *emission_path, - const exploded_edge &eedge) FINAL OVERRIDE; + const exploded_edge &eedge) const FINAL OVERRIDE; private: const gcall *m_dynamic_call; const bool m_is_returning_call; @@ -396,7 +391,7 @@ private: /* Extra data for an exploded_edge that represents a rewind from a longjmp to a setjmp (or from a siglongjmp to a sigsetjmp). */ -class rewind_info_t : public exploded_edge::custom_info_t +class rewind_info_t : public custom_edge_info { public: rewind_info_t (const setjmp_record &setjmp_record, @@ -405,16 +400,17 @@ public: m_longjmp_call (longjmp_call) {} - void print (pretty_printer *pp) FINAL OVERRIDE + void print (pretty_printer *pp) const FINAL OVERRIDE { pp_string (pp, "rewind"); } - void update_model (region_model *model, - const exploded_edge &eedge) FINAL OVERRIDE; + bool update_model (region_model *model, + const exploded_edge *eedge, + region_model_context *ctxt) const FINAL OVERRIDE; void add_events_to_path (checker_path *emission_path, - const exploded_edge &eedge) FINAL OVERRIDE; + const exploded_edge &eedge) const FINAL OVERRIDE; const program_point &get_setjmp_point () const { @@ -829,7 +825,7 @@ public: exploded_node *enode_for_diag); exploded_edge *add_edge (exploded_node *src, exploded_node *dest, const superedge *sedge, - exploded_edge::custom_info_t *custom = NULL); + custom_edge_info *custom = NULL); per_program_point_data * get_or_create_per_program_point_data (const program_point &); diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index ea53c61..c1ff0d8 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -1013,7 +1013,7 @@ program_state::on_edge (exploded_graph &eg, impl_region_model_context ctxt (eg, enode, &enode->get_state (), this, - uncertainty, + uncertainty, NULL, last_stmt); if (!m_region_model->maybe_update_for_edge (*succ, last_stmt, @@ -1052,6 +1052,7 @@ program_state::push_call (exploded_graph &eg, &enode->get_state (), this, uncertainty, + NULL, last_stmt); m_region_model->update_for_gcall (call_stmt, &ctxt); } @@ -1074,6 +1075,7 @@ program_state::returning_call (exploded_graph &eg, &enode->get_state (), this, uncertainty, + NULL, last_stmt); m_region_model->update_for_return_gcall (call_stmt, &ctxt); } @@ -1152,7 +1154,7 @@ program_state::prune_for_point (exploded_graph &eg, impl_region_model_context ctxt (eg, enode_for_diag, this, &new_state, - uncertainty, + uncertainty, NULL, point.get_stmt ()); detect_leaks (*this, new_state, NULL, eg.get_ext_state (), &ctxt); } diff --git a/gcc/analyzer/region-model-impl-calls.cc b/gcc/analyzer/region-model-impl-calls.cc index e5a6cb2..875719f 100644 --- a/gcc/analyzer/region-model-impl-calls.cc +++ b/gcc/analyzer/region-model-impl-calls.cc @@ -56,6 +56,7 @@ along with GCC; see the file COPYING3. If not see #include "analyzer/program-point.h" #include "analyzer/store.h" #include "analyzer/region-model.h" +#include "analyzer/call-info.h" #include "gimple-pretty-print.h" #if ENABLE_ANALYZER @@ -158,6 +159,15 @@ call_details::get_arg_string_literal (unsigned idx) const return NULL; } +/* Attempt to get the fndecl used at this call, if known, or NULL_TREE + otherwise. */ + +tree +call_details::get_fndecl_for_call () const +{ + return m_model->get_fndecl_for_call (m_call, m_ctxt); +} + /* Dump a multiline representation of this call to PP. */ void @@ -486,15 +496,169 @@ region_model::impl_call_operator_delete (const call_details &cd) } } -/* Handle the on_call_pre part of "realloc". */ +/* Handle the on_call_post part of "realloc": + + void *realloc(void *ptr, size_t size); + + realloc(3) is awkward, since it has various different outcomes + that are best modelled as separate exploded nodes/edges. + + We first check for sm-state, in + malloc_state_machine::on_realloc_call, so that we + can complain about issues such as realloc of a non-heap + pointer, and terminate the path for such cases (and issue + the complaints at the call's exploded node). + + Assuming that these checks pass, we split the path here into + three special cases (and terminate the "standard" path): + (A) failure, returning NULL + (B) success, growing the buffer in-place without moving it + (C) success, allocating a new buffer, copying the content + of the old buffer to it, and freeing the old buffer. + + Each of these has a custom_edge_info subclass, which updates + the region_model and sm-state of the destination state. */ void -region_model::impl_call_realloc (const call_details &) +region_model::impl_call_realloc (const call_details &cd) { - /* Currently we don't support bifurcating state, so there's no good - way to implement realloc(3). - For now, malloc_state_machine::on_realloc_call has a minimal - implementation to suppress false positives. */ + /* Three custom subclasses of custom_edge_info, for handling the various + outcomes of "realloc". */ + + /* Concrete custom_edge_info: a realloc call that fails, returning NULL. */ + class failure : public failed_call_info + { + public: + failure (const call_details &cd) + : failed_call_info (cd) + { + } + + bool update_model (region_model *model, + const exploded_edge *, + region_model_context *ctxt) const FINAL OVERRIDE + { + /* Return NULL; everything else is unchanged. */ + const call_details cd (get_call_details (model, ctxt)); + const svalue *zero + = model->m_mgr->get_or_create_int_cst (cd.get_lhs_type (), 0); + model->set_value (cd.get_lhs_region (), + zero, + cd.get_ctxt ()); + return true; + } + }; + + /* Concrete custom_edge_info: a realloc call that succeeds, growing + the existing buffer without moving it. */ + class success_no_move : public call_info + { + public: + success_no_move (const call_details &cd) + : call_info (cd) + { + } + + label_text get_desc (bool can_colorize) const FINAL OVERRIDE + { + return make_label_text (can_colorize, + "when %qE succeeds, without moving buffer", + get_fndecl ()); + } + + bool update_model (region_model *model, + const exploded_edge *, + region_model_context *ctxt) const FINAL OVERRIDE + { + /* Update size of buffer and return the ptr unchanged. */ + const call_details cd (get_call_details (model, ctxt)); + const svalue *ptr_sval = cd.get_arg_svalue (0); + const svalue *size_sval = cd.get_arg_svalue (1); + if (const region *buffer_reg = ptr_sval->maybe_get_region ()) + model->set_dynamic_extents (buffer_reg, size_sval); + model->set_value (cd.get_lhs_region (), ptr_sval, cd.get_ctxt ()); + const svalue *zero + = model->m_mgr->get_or_create_int_cst (cd.get_lhs_type (), 0); + return model->add_constraint (ptr_sval, NE_EXPR, zero, cd.get_ctxt ()); + } + }; + + /* Concrete custom_edge_info: a realloc call that succeeds, freeing + the existing buffer and moving the content to a freshly allocated + buffer. */ + class success_with_move : public call_info + { + public: + success_with_move (const call_details &cd) + : call_info (cd) + { + } + + label_text get_desc (bool can_colorize) const FINAL OVERRIDE + { + return make_label_text (can_colorize, + "when %qE succeeds, moving buffer", + get_fndecl ()); + } + bool update_model (region_model *model, + const exploded_edge *, + region_model_context *ctxt) const FINAL OVERRIDE + { + const call_details cd (get_call_details (model, ctxt)); + const svalue *old_ptr_sval = cd.get_arg_svalue (0); + const svalue *new_size_sval = cd.get_arg_svalue (1); + + /* Create the new region. */ + const region *new_reg + = model->create_region_for_heap_alloc (new_size_sval); + const svalue *new_ptr_sval + = model->m_mgr->get_ptr_svalue (cd.get_lhs_type (), new_reg); + if (cd.get_lhs_type ()) + cd.maybe_set_lhs (new_ptr_sval); + + if (const region *freed_reg = old_ptr_sval->maybe_get_region ()) + { + /* Copy the data. */ + const svalue *old_size_sval = model->get_dynamic_extents (freed_reg); + if (old_size_sval) + { + const region *sized_old_reg + = model->m_mgr->get_sized_region (freed_reg, NULL, + old_size_sval); + const svalue *buffer_content_sval + = model->get_store_value (sized_old_reg, cd.get_ctxt ()); + model->set_value (new_reg, buffer_content_sval, cd.get_ctxt ()); + } + + /* Free the old region, so that pointers to the old buffer become + invalid. */ + + /* If the ptr points to an underlying heap region, delete it, + poisoning pointers. */ + model->unbind_region_and_descendents (freed_reg, POISON_KIND_FREED); + model->m_dynamic_extents.remove (freed_reg); + } + + /* Update the sm-state: mark the old_ptr_sval as "freed", + and the new_ptr_sval as "nonnull". */ + model->on_realloc_with_move (cd, old_ptr_sval, new_ptr_sval); + + const svalue *zero + = model->m_mgr->get_or_create_int_cst (cd.get_lhs_type (), 0); + return model->add_constraint (new_ptr_sval, NE_EXPR, zero, + cd.get_ctxt ()); + } + }; + + /* Body of region_model::impl_call_realloc. */ + + if (cd.get_ctxt ()) + { + cd.get_ctxt ()->bifurcate (new failure (cd)); + cd.get_ctxt ()->bifurcate (new success_no_move (cd)); + cd.get_ctxt ()->bifurcate (new success_with_move (cd)); + cd.get_ctxt ()->terminate_path (); + } } /* Handle the on_call_pre part of "strcpy" and "__builtin_strcpy_chk". */ diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 787f2ed..3bfc4ba 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -1132,7 +1132,6 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt, return false; break; case BUILT_IN_REALLOC: - impl_call_realloc (cd); return false; case BUILT_IN_STRCPY: case BUILT_IN_STRCPY_CHK: @@ -1276,9 +1275,9 @@ region_model::on_call_post (const gcall *call, { if (tree callee_fndecl = get_fndecl_for_call (call, ctxt)) { + call_details cd (call, this, ctxt); if (is_named_call_p (callee_fndecl, "free", call, 1)) { - call_details cd (call, this, ctxt); impl_call_free (cd); return; } @@ -1286,7 +1285,6 @@ region_model::on_call_post (const gcall *call, || is_named_call_p (callee_fndecl, "operator delete", call, 2) || is_named_call_p (callee_fndecl, "operator delete []", call, 1)) { - call_details cd (call, this, ctxt); impl_call_operator_delete (cd); return; } @@ -1294,10 +1292,19 @@ region_model::on_call_post (const gcall *call, __attribute__((malloc(FOO)))? */ if (lookup_attribute ("*dealloc", DECL_ATTRIBUTES (callee_fndecl))) { - call_details cd (call, this, ctxt); impl_deallocation_call (cd); return; } + if (fndecl_built_in_p (callee_fndecl, BUILT_IN_NORMAL) + && gimple_builtin_call_types_compatible_p (call, callee_fndecl)) + switch (DECL_UNCHECKED_FUNCTION_CODE (callee_fndecl)) + { + default: + break; + case BUILT_IN_REALLOC: + impl_call_realloc (cd); + return; + } } if (unknown_side_effects) @@ -3765,6 +3772,19 @@ region_model::unset_dynamic_extents (const region *reg) m_dynamic_extents.remove (reg); } +/* class noop_region_model_context : public region_model_context. */ + +void +noop_region_model_context::bifurcate (custom_edge_info *info) +{ + delete info; +} + +void +noop_region_model_context::terminate_path () +{ +} + /* struct model_merger. */ /* Dump a multiline representation of this merger to PP. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index f2c82b0..5fabf78 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -487,11 +487,15 @@ public: unsigned num_args () const; + const gcall *get_call_stmt () const { return m_call; } + tree get_arg_tree (unsigned idx) const; tree get_arg_type (unsigned idx) const; const svalue *get_arg_svalue (unsigned idx) const; const char *get_arg_string_literal (unsigned idx) const; + tree get_fndecl_for_call () const; + void dump_to_pp (pretty_printer *pp, bool simple) const; void dump (bool simple) const; @@ -732,6 +736,11 @@ class region_model const svalue *get_capacity (const region *reg) const; + /* Implemented in sm-malloc.cc */ + void on_realloc_with_move (const call_details &cd, + const svalue *old_ptr_sval, + const svalue *new_ptr_sval); + private: const region *get_lvalue_1 (path_var pv, region_model_context *ctxt) const; const svalue *get_rvalue_1 (path_var pv, region_model_context *ctxt) const; @@ -867,6 +876,21 @@ class region_model_context /* Hook for clients to purge state involving SVAL. */ virtual void purge_state_involving (const svalue *sval) = 0; + + /* Hook for clients to split state with a non-standard path. + Take ownership of INFO. */ + virtual void bifurcate (custom_edge_info *info) = 0; + + /* Hook for clients to terminate the standard path. */ + virtual void terminate_path () = 0; + + virtual const extrinsic_state *get_ext_state () const = 0; + + /* Hook for clients to access the "malloc" state machine in + any underlying program_state. */ + virtual bool get_malloc_map (sm_state_map **out_smap, + const state_machine **out_sm, + unsigned *out_sm_idx) = 0; }; /* A "do nothing" subclass of region_model_context. */ @@ -899,6 +923,18 @@ public: uncertainty_t *get_uncertainty () OVERRIDE { return NULL; } void purge_state_involving (const svalue *sval ATTRIBUTE_UNUSED) OVERRIDE {} + + void bifurcate (custom_edge_info *info) OVERRIDE; + void terminate_path () OVERRIDE; + + const extrinsic_state *get_ext_state () const OVERRIDE { return NULL; } + + bool get_malloc_map (sm_state_map **, + const state_machine **, + unsigned *) OVERRIDE + { + return false; + } }; /* A subclass of region_model_context for determining if operations fail diff --git a/gcc/analyzer/sm-malloc.cc b/gcc/analyzer/sm-malloc.cc index 74c6fee..bf5e3c3 100644 --- a/gcc/analyzer/sm-malloc.cc +++ b/gcc/analyzer/sm-malloc.cc @@ -45,6 +45,7 @@ along with GCC; see the file COPYING3. If not see #include "stringpool.h" #include "attribs.h" #include "analyzer/function-set.h" +#include "analyzer/program-state.h" #if ENABLE_ANALYZER @@ -387,6 +388,12 @@ public: static bool unaffected_by_call_p (tree fndecl); + void on_realloc_with_move (region_model *model, + sm_state_map *smap, + const svalue *old_ptr_sval, + const svalue *new_ptr_sval, + const extrinsic_state &ext_state) const; + standard_deallocator_set m_free; standard_deallocator_set m_scalar_delete; standard_deallocator_set m_vector_delete; @@ -1836,54 +1843,65 @@ malloc_state_machine::on_deallocator_call (sm_context *sm_ctxt, } } -/* Implementation of realloc(3): - - void *realloc(void *ptr, size_t size); - - realloc(3) is awkward. +/* Handle a call to "realloc". + Check for free of non-heap or mismatching allocators, + transitioning to the "stop" state for such cases. - We currently don't have a way to express multiple possible outcomes - from a function call, "bifurcating" the state such as: - - success: non-NULL is returned - - failure: NULL is returned, existing buffer is not freed. - or even an N-way state split e.g.: - - buffer grew successfully in-place - - buffer was successfully moved to a larger allocation - - buffer was successfully contracted - - realloc failed, returning NULL, without freeing existing buffer. - (PR analyzer/99260 tracks this) - - Given that we can currently only express one outcome, eliminate - false positives by dropping state from the buffer. */ + Otherwise, region_model::impl_call_realloc will later + get called (which will handle other sm-state transitions + when the state is bifurcated). */ void malloc_state_machine::on_realloc_call (sm_context *sm_ctxt, - const supernode *node ATTRIBUTE_UNUSED, + const supernode *node, const gcall *call) const { - tree ptr = gimple_call_arg (call, 0); + const unsigned argno = 0; + const deallocator *d = &m_realloc; + + tree arg = gimple_call_arg (call, argno); - state_t state = sm_ctxt->get_state (call, ptr); + state_t state = sm_ctxt->get_state (call, arg); - /* Detect mismatches. */ if (unchecked_p (state) || nonnull_p (state)) { const allocation_state *astate = as_a_allocation_state (state); gcc_assert (astate->m_deallocators); - if (astate->m_deallocators != &m_free) + if (!astate->m_deallocators->contains_p (&m_free.m_deallocator)) { /* Wrong allocator. */ - tree diag_ptr = sm_ctxt->get_diagnostic_tree (ptr); + tree diag_arg = sm_ctxt->get_diagnostic_tree (arg); pending_diagnostic *pd - = new mismatching_deallocation (*this, diag_ptr, + = new mismatching_deallocation (*this, diag_arg, astate->m_deallocators, - &m_realloc); - sm_ctxt->warn (node, call, ptr, pd); + d); + sm_ctxt->warn (node, call, arg, pd); + sm_ctxt->set_next_state (call, arg, m_stop); + if (path_context *path_ctxt = sm_ctxt->get_path_context ()) + path_ctxt->terminate_path (); } } - - /* Transition ptr to "stop" state. */ - sm_ctxt->set_next_state (call, ptr, m_stop); + else if (state == m_free.m_deallocator.m_freed) + { + /* freed -> stop, with warning. */ + tree diag_arg = sm_ctxt->get_diagnostic_tree (arg); + sm_ctxt->warn (node, call, arg, + new double_free (*this, diag_arg, "free")); + sm_ctxt->set_next_state (call, arg, m_stop); + if (path_context *path_ctxt = sm_ctxt->get_path_context ()) + path_ctxt->terminate_path (); + } + else if (state == m_non_heap) + { + /* non-heap -> stop, with warning. */ + tree diag_arg = sm_ctxt->get_diagnostic_tree (arg); + sm_ctxt->warn (node, call, arg, + new free_of_non_heap (*this, diag_arg, + d->m_name)); + sm_ctxt->set_next_state (call, arg, m_stop); + if (path_context *path_ctxt = sm_ctxt->get_path_context ()) + path_ctxt->terminate_path (); + } } /* Implementation of state_machine::on_phi vfunc for malloc_state_machine. */ @@ -2015,6 +2033,30 @@ malloc_state_machine::on_zero_assignment (sm_context *sm_ctxt, sm_ctxt->set_next_state (stmt, lhs, m_null); } +/* Special-case hook for handling realloc, for the "success with move to + a new buffer" case, marking OLD_PTR_SVAL as freed and NEW_PTR_SVAL as + non-null. + + This is similar to on_deallocator_call and on_allocator_call, + but the checks happen in on_realloc_call, and by splitting the states. */ + +void +malloc_state_machine:: +on_realloc_with_move (region_model *model, + sm_state_map *smap, + const svalue *old_ptr_sval, + const svalue *new_ptr_sval, + const extrinsic_state &ext_state) const +{ + smap->set_state (model, old_ptr_sval, + m_free.m_deallocator.m_freed, + NULL, ext_state); + + smap->set_state (model, new_ptr_sval, + m_free.m_nonnull, + NULL, ext_state); +} + } // anonymous namespace /* Internal interface to this file. */ @@ -2025,6 +2067,40 @@ make_malloc_state_machine (logger *logger) return new malloc_state_machine (logger); } +/* Specialcase hook for handling realloc, for use by + region_model::impl_call_realloc::success_with_move::update_model. */ + +void +region_model::on_realloc_with_move (const call_details &cd, + const svalue *old_ptr_sval, + const svalue *new_ptr_sval) +{ + region_model_context *ctxt = cd.get_ctxt (); + if (!ctxt) + return; + const extrinsic_state *ext_state = ctxt->get_ext_state (); + if (!ext_state) + return; + + sm_state_map *smap; + const state_machine *sm; + unsigned sm_idx; + if (!ctxt->get_malloc_map (&smap, &sm, &sm_idx)) + return; + + gcc_assert (smap); + gcc_assert (sm); + + const malloc_state_machine &malloc_sm + = (const malloc_state_machine &)*sm; + + malloc_sm.on_realloc_with_move (this, + smap, + old_ptr_sval, + new_ptr_sval, + *ext_state); +} + } // namespace ana #endif /* #if ENABLE_ANALYZER */ diff --git a/gcc/analyzer/sm-signal.cc b/gcc/analyzer/sm-signal.cc index fcbf322..e8cbe2d 100644 --- a/gcc/analyzer/sm-signal.cc +++ b/gcc/analyzer/sm-signal.cc @@ -206,10 +206,10 @@ update_model_for_signal_handler (region_model *model, /* Custom exploded_edge info: entry into a signal-handler. */ -class signal_delivery_edge_info_t : public exploded_edge::custom_info_t +class signal_delivery_edge_info_t : public custom_edge_info { public: - void print (pretty_printer *pp) FINAL OVERRIDE + void print (pretty_printer *pp) const FINAL OVERRIDE { pp_string (pp, "signal delivered"); } @@ -220,15 +220,18 @@ public: return custom_obj; } - void update_model (region_model *model, - const exploded_edge &eedge) FINAL OVERRIDE + bool update_model (region_model *model, + const exploded_edge *eedge, + region_model_context *) const FINAL OVERRIDE { - update_model_for_signal_handler (model, eedge.m_dest->get_function ()); + gcc_assert (eedge); + update_model_for_signal_handler (model, eedge->m_dest->get_function ()); + return true; } void add_events_to_path (checker_path *emission_path, const exploded_edge &eedge ATTRIBUTE_UNUSED) - FINAL OVERRIDE + const FINAL OVERRIDE { emission_path->add_event (new precanned_custom_event diff --git a/gcc/analyzer/sm.h b/gcc/analyzer/sm.h index 6bb036e..02faffb 100644 --- a/gcc/analyzer/sm.h +++ b/gcc/analyzer/sm.h @@ -257,6 +257,11 @@ public: Otherwise return NULL_TREE. */ virtual tree is_zero_assignment (const gimple *stmt) = 0; + virtual path_context *get_path_context () const + { + return NULL; + } + protected: sm_context (int sm_idx, const state_machine &sm) : m_sm_idx (sm_idx), m_sm (sm) {} diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc index 6913161..5f2fe4c 100644 --- a/gcc/analyzer/svalue.cc +++ b/gcc/analyzer/svalue.cc @@ -105,7 +105,8 @@ svalue::to_json () const tree svalue::maybe_get_constant () const { - if (const constant_svalue *cst_sval = dyn_cast_constant_svalue ()) + const svalue *sval = unwrap_any_unmergeable (); + if (const constant_svalue *cst_sval = sval->dyn_cast_constant_svalue ()) return cst_sval->get_constant (); else return NULL_TREE; diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-2.c b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c index 9f92bcf..2db1b3f 100644 --- a/gcc/testsuite/gcc.dg/analyzer/capacity-2.c +++ b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c @@ -8,7 +8,8 @@ void * test_realloc_1 (void *p, size_t new_sz) { void *q = realloc (p, new_sz); - __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ + __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" "failure" } */ + /* { dg-warning "capacity: 'INIT_VAL\\(new_sz\[^\n\r\]*\\)'" "success" { target *-*-* } .-1 } */ return q; } @@ -18,8 +19,9 @@ test_realloc_2 (size_t sz_a, size_t sz_b) void *p = malloc (sz_a); __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_a_\[^\n\r\]*\\)'" } */ void *q = realloc (p, sz_b); - __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ - return p; + __analyzer_dump_capacity (q); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" "failure" } */ + /* { dg-warning "capacity: 'INIT_VAL\\(sz_b\[^\n\r\]*\\)'" "success" { target *-*-* } .-1 } */ + return q; /* { dg-warning "leak of 'p'" } */ } void * diff --git a/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c b/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c index c6179e9..459357c 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c @@ -1,3 +1,5 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + /* Verify absence of false positive from -Wanalyzer-mismatching-deallocation on realloc(3). Based on https://github.com/libguestfs/libguestfs/blob/f19fd566f6387ce7e4d82409528c9dde374d25e0/daemon/command.c#L115 diff --git a/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c b/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c index 3e7ffd6..d64b045 100644 --- a/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c +++ b/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c @@ -1,3 +1,5 @@ +/* { dg-additional-options "-Wno-analyzer-too-complex" } */ + /* Verify absence of false positive from -Wanalyzer-mismatching-deallocation on realloc(3). Based on https://github.com/libguestfs/libguestfs/blob/f19fd566f6387ce7e4d82409528c9dde374d25e0/daemon/debug.c#L115 diff --git a/gcc/testsuite/gcc.dg/analyzer/realloc-1.c b/gcc/testsuite/gcc.dg/analyzer/realloc-1.c index a6c6bfc..606a19a 100644 --- a/gcc/testsuite/gcc.dg/analyzer/realloc-1.c +++ b/gcc/testsuite/gcc.dg/analyzer/realloc-1.c @@ -1,3 +1,5 @@ +/* { dg-additional-options "-Wno-free-nonheap-object" } */ + typedef __SIZE_TYPE__ size_t; #define NULL ((void *)0) @@ -20,11 +22,10 @@ void *test_1 (void *ptr) void *test_2 (void *ptr) { - void *p = malloc (1024); - p = realloc (p, 4096); - /* TODO: should warn about the leak when the above call fails (PR analyzer/99260). */ + void *p = malloc (1024); /* { dg-message "allocated here" } */ + p = realloc (p, 4096); /* { dg-message "when 'realloc' fails" } */ free (p); -} +} /* { dg-warning "leak of 'p'" } */ // ideally this would be on the realloc stmt void *test_3 (void *ptr) { @@ -44,8 +45,8 @@ void *test_4 (void) int *test_5 (int *p) { *p = 42; - int *q = realloc (p, sizeof(int) * 4); - *q = 43; /* { dg-warning "possibly-NULL 'q'" "PR analyzer/99260" { xfail *-*-* } } */ + int *q = realloc (p, sizeof(int) * 4); /* { dg-message "when 'realloc' fails" } */ + *q = 43; /* { dg-warning "dereference of NULL 'q'" } */ return q; } @@ -53,3 +54,37 @@ void test_6 (size_t sz) { void *p = realloc (NULL, sz); } /* { dg-warning "leak of 'p'" } */ + +/* The analyzer should complain about realloc of non-heap. */ + +void *test_7 (size_t sz) +{ + char buf[100]; + void *p = realloc (&buf, sz); /* { dg-warning "'realloc' of '&buf' which points to memory not on the heap" } */ + return p; +} + +/* Mismatched allocator. */ + +struct foo +{ + int m_int; +}; + +extern void foo_release (struct foo *); +extern struct foo *foo_acquire (void) + __attribute__ ((malloc (foo_release))); + +void test_8 (void) +{ + struct foo *p = foo_acquire (); + void *q = realloc (p, 1024); /* { dg-warning "'p' should have been deallocated with 'foo_release' but was deallocated with 'realloc'" } */ +} + +/* We should complain about realloc on a freed pointer. */ + +void test_9 (void *p) +{ + free (p); + void *q = realloc (p, 1024); /* { dg-warning "double-'free' of 'p'" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/realloc-2.c b/gcc/testsuite/gcc.dg/analyzer/realloc-2.c new file mode 100644 index 0000000..a397753 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/realloc-2.c @@ -0,0 +1,80 @@ +#include "analyzer-decls.h" + +typedef __SIZE_TYPE__ size_t; + +#define NULL ((void *)0) + +extern void *malloc (size_t __size) + __attribute__ ((__nothrow__ , __leaf__)) + __attribute__ ((__malloc__)) + __attribute__ ((__alloc_size__ (1))); +extern void *realloc (void *__ptr, size_t __size) + __attribute__ ((__nothrow__ , __leaf__)) + __attribute__ ((__warn_unused_result__)) + __attribute__ ((__alloc_size__ (2))); +extern void free (void *__ptr) + __attribute__ ((__nothrow__ , __leaf__)); + +char *test_8 (size_t sz) +{ + char *p, *q; + + p = malloc (3); + if (!p) + return NULL; + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)3'" } */ + + p[0] = 'a'; + p[1] = 'b'; + p[2] = 'c'; + + __analyzer_eval (p[0] == 'a'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[1] == 'b'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[2] == 'c'); /* { dg-warning "TRUE" } */ + + q = realloc (p, 6); + + /* We should have 3 nodes, corresponding to "failure", + "success without moving", and "success with moving". */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "3 processed enodes" } */ + + if (q) + { + __analyzer_dump_capacity (q); /* { dg-warning "capacity: '\\(size_t\\)6'" } */ + q[3] = 'd'; + q[4] = 'e'; + q[5] = 'f'; + if (q == p) + { + /* "realloc" success, growing the buffer in-place. */ + __analyzer_eval (p[0] == 'a'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[1] == 'b'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[2] == 'c'); /* { dg-warning "TRUE" } */ + // TODO + } + else + { + /* "realloc" success, moving the buffer (and thus freeing "p"). */ + __analyzer_eval (q[0] == 'a'); /* { dg-warning "TRUE" } */ + __analyzer_eval (q[1] == 'b'); /* { dg-warning "TRUE" } */ + __analyzer_eval (q[2] == 'c'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[0] == 'a'); /* { dg-warning "UNKNOWN" "unknown" } */ + /* { dg-warning "use after 'free' of 'p'" "use after free" { target *-*-* } .-1 } */ + } + __analyzer_eval (q[3] == 'd'); /* { dg-warning "TRUE" } */ + __analyzer_eval (q[4] == 'e'); /* { dg-warning "TRUE" } */ + __analyzer_eval (q[5] == 'f'); /* { dg-warning "TRUE" } */ + } + else + { + /* "realloc" failure. p should be unchanged. */ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)3'" } */ + __analyzer_eval (p[0] == 'a'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[1] == 'b'); /* { dg-warning "TRUE" } */ + __analyzer_eval (p[2] == 'c'); /* { dg-warning "TRUE" } */ + return p; + } + + return q; +} |