From eafa9d969237fd8f712c4b25a8c58932c01f44b4 Mon Sep 17 00:00:00 2001 From: David Malcolm Date: Mon, 30 Aug 2021 18:36:31 -0400 Subject: analyzer: support "bifurcation"; reimplement realloc [PR99260] Most of the state-management code in the analyzer involves modifying state objects in-place, which implies a single outcome. (I originally implemented in-place modification because I wanted to avoid having to create copies of state objects, and it's now very difficult to change this aspect of the analyzer's design) However, there are various special-cases such as "realloc" for which it's best to split the state into multiple outcomes. This patch adds a mechanism for "bifurcating" the analysis in places where there isn't a split in the CFG, and uses it to implement realloc, in this case treating it as having 3 possible outcomes: - failure, returning NULL - success, growing the buffer in-place without moving it - success, allocating a new buffer, copying the content of the old buffer to it, and freeing the old buffer. gcc/ChangeLog: PR analyzer/99260 * Makefile.in (ANALYZER_OBJS): Add analyzer/call-info.o. gcc/analyzer/ChangeLog: PR analyzer/99260 * analyzer.h (class custom_edge_info): New class, adapted from exploded_edge::custom_info_t. Make member functions const. Make update_model return bool, converting edge param from reference to a pointer, and adding a ctxt param. (class path_context): New class. * call-info.cc: New file. * call-info.h: New file. * engine.cc: Include "analyzer/call-info.h" and . (impl_region_model_context::impl_region_model_context): Update for new m_path_ctxt field. (impl_region_model_context::bifurcate): New. (impl_region_model_context::terminate_path): New. (impl_region_model_context::get_malloc_map): New. (impl_sm_context::impl_sm_context): Update for new m_path_ctxt field. (impl_sm_context::get_fndecl_for_call): Likewise. (impl_sm_context::set_next_state): Likewise. (impl_sm_context::warn): Likewise. (impl_sm_context::is_zero_assignment): Likewise. (impl_sm_context::get_path_context): New. (impl_sm_context::m_path_ctxt): New. (impl_region_model_context::on_condition): Update for new path_ctxt param. Handle m_enode_for_diag being NULL. (impl_region_model_context::on_phi): Update for new path_ctxt param. (exploded_node::on_stmt): Add path_ctxt param, updating ctor calls to use it as necessary. Use it to bail out after sm-handling, if needed. (exploded_node::detect_leaks): Update for new path_ctxt param. (dynamic_call_info_t::update_model): Update for conversion of exploded_edge::custom_info_t to custom_edge_info. (dynamic_call_info_t::add_events_to_path): Likewise. (rewind_info_t::update_model): Likewise. (rewind_info_t::add_events_to_path): Likewise. (exploded_edge::exploded_edge): Likewise. (exploded_graph::add_edge): Likewise. (exploded_graph::maybe_process_run_of_before_supernode_enodes): Update for new path_ctxt param. (class impl_path_context): New. (exploded_graph::process_node): Update for new path_ctxt param. Create an impl_path_context and pass it to exploded_node::on_stmt. Use it to terminate iterating stmts if terminate_path is called on it. After processing a run of stmts, query path_ctxt to potentially terminate the analysis path, and/or to "bifurcate" the analysis into multiple additional paths. (feasibility_state::maybe_update_for_edge): Update for new update_model ctxt param. * exploded-graph.h (impl_region_model_context::impl_region_model_context): Add path_ctxt param. (impl_region_model_context::bifurcate): New. (impl_region_model_context::terminate_path): New (impl_region_model_context::get_ext_state): New. (impl_region_model_context::get_malloc_map): New. (impl_region_model_context::m_path_ctxt): New field. (exploded_node::on_stmt): Add path_ctxt param. (class exploded_edge::custom_info_t): Move to analyzer.h, renaming to custom_edge_info, and making the changes as noted in analyzer.h above. (exploded_edge::exploded_edge): Update for these changes to exploded_edge::custom_info_t. (exploded_edge::m_custom_info): Likewise. (class dynamic_call_info_t): Likewise. (class rewind_info_t): Likewise. (exploded_graph::add_edge): Likewise. * program-state.cc (program_state::on_edge): Update for new path_ctxt param. (program_state::push_call): Likewise. (program_state::returning_call): Likewise. (program_state::prune_for_point): Likewise. * region-model-impl-calls.cc: Include "analyzer/call-info.h". (call_details::get_fndecl_for_call): New. (region_model::impl_call_realloc): Reimplement. * region-model.cc (region_model::on_call_pre): Move call to impl_call_realloc to... (region_model::on_call_post): ...here. Consolidate creation of call_details instance. (noop_region_model_context::bifurcate): New. (noop_region_model_context::terminate_path): New. * region-model.h (call_details::get_call_stmt): New. (call_details::get_fndecl_for_call): New. (region_model::on_realloc_with_move): New. (region_model_context::bifurcate): New. (region_model_context::terminate_path): New. (region_model_context::get_ext_state): New. (region_model_context::get_malloc_map): New. (noop_region_model_context::bifurcate): New. (noop_region_model_context::terminate_path): New. (noop_region_model_context::get_ext_state): New. (noop_region_model_context::get_malloc_map): New. * sm-malloc.cc: Include "analyzer/program-state.h". (malloc_state_machine::on_realloc_call): Reimplement. (malloc_state_machine::on_realloc_with_move): New. (region_model::on_realloc_with_move): New. * sm-signal.cc (class signal_delivery_edge_info_t): Update for conversion from exploded_edge::custom_info_t to custom_edge_info. * sm.h (sm_context::get_path_context): New. * svalue.cc (svalue::maybe_get_constant): Call unwrap_any_unmergeable. gcc/testsuite/ChangeLog: PR analyzer/99260 * gcc.dg/analyzer/capacity-2.c: Update for changes to realloc analysis. * gcc.dg/analyzer/pr99193-1.c: Likewise. * gcc.dg/analyzer/pr99193-3.c: Likewise. * gcc.dg/analyzer/realloc-1.c: Likewise. Add test coverage for realloc of non-heap pointer, realloc from mismatching allocator, and realloc on a freed pointer. * gcc.dg/analyzer/realloc-2.c: New test. --- gcc/analyzer/sm-malloc.cc | 136 ++++++++++++++++++++++++++++++++++++---------- 1 file changed, 106 insertions(+), 30 deletions(-) (limited to 'gcc/analyzer/sm-malloc.cc') 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 */ -- cgit v1.1