From patchwork Tue Jun 15 13:39:47 2021 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 8bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1492221 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@bilbo.ozlabs.org Authentication-Results: ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=8.43.85.97; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: ozlabs.org; dkim=pass (1024-bit key; unprotected) header.d=gcc.gnu.org header.i=@gcc.gnu.org header.a=rsa-sha256 header.s=default header.b=LTVBqgxG; dkim-atps=neutral Received: from sourceware.org (ip-8-43-85-97.sourceware.org [8.43.85.97]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits) server-digest SHA256) (No client certificate requested) by ozlabs.org (Postfix) with ESMTPS id 4G48b12S2Sz9t10 for ; Tue, 15 Jun 2021 23:40:29 +1000 (AEST) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id E4EBC3893676 for ; Tue, 15 Jun 2021 13:40:26 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org E4EBC3893676 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1623764426; bh=eLq99UY0sL7laU43BAX4J2HyvegPVoQcJDeTQlLa0Z0=; h=To:Subject:Date:List-Id:List-Unsubscribe:List-Archive:List-Post: List-Help:List-Subscribe:From:Reply-To:From; b=LTVBqgxGwapZh264lGbyz1VS7wz8LVPS9nFgK/vT8vMjiW3cPoipUntuiJYHej/5l YyVeJHLJt2xiWxW6qew6moF5Rsp7QmBOjRylOclmm8DS4zNR57UQrTXVOkHs6qD3+3 uetLDE/inIMUs4CGz11FFUgk6ckd7CEs5/YNTW8o= X-Original-To: gcc-patches@gcc.gnu.org Delivered-To: gcc-patches@gcc.gnu.org Received: from us-smtp-delivery-124.mimecast.com (us-smtp-delivery-124.mimecast.com [170.10.133.124]) by sourceware.org (Postfix) with ESMTP id D64393947427 for ; Tue, 15 Jun 2021 13:39:52 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.1 sourceware.org D64393947427 Received: from mimecast-mx01.redhat.com (mimecast-mx01.redhat.com [209.132.183.4]) (Using TLS) by relay.mimecast.com with ESMTP id us-mta-338-UD9mZUsuMGqQlcI2WU9vXA-1; Tue, 15 Jun 2021 09:39:49 -0400 X-MC-Unique: UD9mZUsuMGqQlcI2WU9vXA-1 Received: from smtp.corp.redhat.com (int-mx05.intmail.prod.int.phx2.redhat.com [10.5.11.15]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx01.redhat.com (Postfix) with ESMTPS id 343821006914 for ; Tue, 15 Jun 2021 13:39:49 +0000 (UTC) Received: from t14s.localdomain.com (ovpn-112-247.phx2.redhat.com [10.3.112.247]) by smtp.corp.redhat.com (Postfix) with ESMTP id 9169C5D6D1; Tue, 15 Jun 2021 13:39:48 +0000 (UTC) To: gcc-patches@gcc.gnu.org Subject: [committed] analyzer: track dynamic extents of regions Date: Tue, 15 Jun 2021 09:39:47 -0400 Message-Id: <20210615133947.348186-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 2.79 on 10.5.11.15 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-13.4 required=5.0 tests=BAYES_00, DKIMWL_WL_HIGH, DKIM_SIGNED, DKIM_VALID, DKIM_VALID_AU, DKIM_VALID_EF, GIT_PATCH_0, RCVD_IN_DNSWL_LOW, RCVD_IN_MSPIKE_H4, RCVD_IN_MSPIKE_WL, SPF_HELO_NONE, SPF_PASS, TXREP autolearn=ham autolearn_force=no version=3.4.2 X-Spam-Checker-Version: SpamAssassin 3.4.2 (2018-09-13) on server2.sourceware.org X-BeenThere: gcc-patches@gcc.gnu.org X-Mailman-Version: 2.1.29 Precedence: list List-Id: Gcc-patches mailing list List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-Patchwork-Original-From: David Malcolm via Gcc-patches From: David Malcolm Reply-To: David Malcolm Errors-To: gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org Sender: "Gcc-patches" This patch extends region_model to add tracking of the sizes of dynamically-allocated regions, both on the heap (via malloc etc) and stack (via alloca). It adds enough purging of this state to avoid blowing up any existing analyzer test cases. The state can be queried via a new "__analyzer_dump_capacity" for use in DejaGnu tests but other than that doesn't do anything - I have various followup experiments that make use of this. Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as 9a2c9579fdbf5d24dfe27fb961286ad7a9c3a98b. gcc/analyzer/ChangeLog: * engine.cc (exploded_node::on_stmt): Handle __analyzer_dump_capacity. (exploded_node::on_stmt): Drop m_sm_changes from on_stmt_flags. (state_change_requires_new_enode_p): New function... (exploded_graph::process_node): Call it, rather than querying flags.m_sm_changes, so that dynamic-extent differences can also trigger the splitting of nodes. * exploded-graph.h (struct on_stmt_flags): Drop field m_sm_changes. * program-state.cc (program_state::detect_leaks): Purge dead heap-allocated regions from dynamic extents. (selftest::test_program_state_1): Fix type of "size_in_bytes". (selftest::test_program_state_merging): Likewise. * region-model-impl-calls.cc (region_model::impl_call_analyzer_dump_capacity): New. (region_model::impl_call_free): Remove dynamic extents from the freed region. * region-model-reachability.h (reachable_regions::begin_mutable_base_regs): New. (reachable_regions::end_mutable_base_regs): New. * region-model.cc: Include "tree-object-size.h". (region_model::region_model): Support new field m_dynamic_extents. (region_model::operator=): Likewise. (region_model::operator==): Likewise. (region_model::dump_to_pp): Dump sizes of dynamic regions. (region_model::handle_unrecognized_call): Purge dynamic extents from any regions that have escaped mutably:. (region_model::get_capacity): New function. (region_model::add_constraint): Unset dynamic extents when a heap-allocated region's address is NULL. (region_model::unbind_region_and_descendents): Purge dynamic extents of unbound regions. (region_model::can_merge_with_p): Call m_dynamic_extents.can_merge_with_p. (region_model::create_region_for_heap_alloc): Assert that size_in_bytes's type is compatible with size_type_node. Update for renaming of record_dynamic_extents to set_dynamic_extents. (region_model::create_region_for_alloca): Likewise. (region_model::record_dynamic_extents): Rename to... (region_model::set_dynamic_extents): ...this. Assert that size_in_bytes's type is compatible with size_type_node. Add it to the m_dynamic_extents map. (region_model::get_dynamic_extents): New. (region_model::unset_dynamic_extents): New. (selftest::test_state_merging): Fix type of "size". (selftest::test_malloc_constraints): Likewise. (selftest::test_malloc): Verify dynamic extents. (selftest::test_alloca): Likewise. * region-model.h (region_to_value_map::is_empty): New. (region_model::dynamic_extents_t): New typedef. (region_model::impl_call_analyzer_dump_capacity): New decl. (region_model::get_dynamic_extents): New function. (region_model::get_dynamic_extents): New decl. (region_model::set_dynamic_extents): New decl. (region_model::unset_dynamic_extents): New decl. (region_model::get_capacity): New decl. (region_model::record_dynamic_extents): Rename to set_dynamic_extents. (region_model::m_dynamic_extents): New field. gcc/ChangeLog: * doc/analyzer.texi (Special Functions for Debugging the Analyzer): Add __analyzer_dump_capacity. gcc/testsuite/ChangeLog: * gcc.dg/analyzer/analyzer-decls.h (__analyzer_dump_capacity): New decl. * gcc.dg/analyzer/capacity-1.c: New test. * gcc.dg/analyzer/capacity-2.c: New test. * gcc.dg/analyzer/capacity-3.c: New test. Signed-off-by: David Malcolm --- gcc/analyzer/engine.cc | 40 +++++- gcc/analyzer/exploded-graph.h | 20 +-- gcc/analyzer/program-state.cc | 13 +- gcc/analyzer/region-model-impl-calls.cc | 20 +++ gcc/analyzer/region-model-reachability.h | 8 ++ gcc/analyzer/region-model.cc | 130 ++++++++++++++++-- gcc/analyzer/region-model.h | 33 ++++- gcc/doc/analyzer.texi | 7 + .../gcc.dg/analyzer/analyzer-decls.h | 3 + gcc/testsuite/gcc.dg/analyzer/capacity-1.c | 106 ++++++++++++++ gcc/testsuite/gcc.dg/analyzer/capacity-2.c | 53 +++++++ gcc/testsuite/gcc.dg/analyzer/capacity-3.c | 82 +++++++++++ 12 files changed, 473 insertions(+), 42 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-2.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/capacity-3.c diff --git a/gcc/analyzer/engine.cc b/gcc/analyzer/engine.cc index 50652b2cfa6..df04b0ba5d6 100644 --- a/gcc/analyzer/engine.cc +++ b/gcc/analyzer/engine.cc @@ -1185,6 +1185,8 @@ exploded_node::on_stmt (exploded_graph &eg, to stderr. */ state->dump (eg.get_ext_state (), true); } + else if (is_special_named_call_p (call, "__analyzer_dump_capacity", 1)) + state->m_region_model->impl_call_analyzer_dump_capacity (call, &ctxt); else if (is_special_named_call_p (call, "__analyzer_dump_path", 0)) { /* Handle the builtin "__analyzer_dump_path" by queuing a @@ -1237,7 +1239,6 @@ exploded_node::on_stmt (exploded_graph &eg, if (terminate_path) return on_stmt_flags::terminate_path (); - bool any_sm_changes = false; int sm_idx; sm_state_map *smap; FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap) @@ -1276,14 +1277,12 @@ exploded_node::on_stmt (exploded_graph &eg, /* Allow the state_machine to handle the stmt. */ if (sm.on_stmt (&sm_ctxt, snode, stmt)) unknown_side_effects = false; - if (*old_smap != *new_smap) - any_sm_changes = true; } if (const gcall *call = dyn_cast (stmt)) state->m_region_model->on_call_post (call, unknown_side_effects, &ctxt); - return on_stmt_flags (any_sm_changes); + return on_stmt_flags (); } /* Consider the effect of following superedge SUCC from this node. @@ -2925,6 +2924,36 @@ stmt_requires_new_enode_p (const gimple *stmt, return false; } +/* Return true if OLD_STATE and NEW_STATE are sufficiently different that + we should split enodes and create an exploded_edge separating them + (which makes it easier to identify state changes of intereset when + constructing checker_paths). */ + +static bool +state_change_requires_new_enode_p (const program_state &old_state, + const program_state &new_state) +{ + /* Changes in dynamic extents signify creations of heap/alloca regions + and resizings of heap regions; likely to be of interest in + diagnostic paths. */ + if (old_state.m_region_model->get_dynamic_extents () + != new_state.m_region_model->get_dynamic_extents ()) + return true; + + /* Changes in sm-state are of interest. */ + int sm_idx; + sm_state_map *smap; + FOR_EACH_VEC_ELT (old_state.m_checker_states, sm_idx, smap) + { + const sm_state_map *old_smap = old_state.m_checker_states[sm_idx]; + const sm_state_map *new_smap = new_state.m_checker_states[sm_idx]; + if (*old_smap != *new_smap) + return true; + } + + return false; +} + /* The core of exploded_graph::process_worklist (the main analysis loop), handling one node in the worklist. @@ -3067,7 +3096,8 @@ exploded_graph::process_node (exploded_node *node) next_state = next_state.prune_for_point (*this, next_point, node, &uncertainty); - if (flags.m_sm_changes || flag_analyzer_fine_grained) + if (flag_analyzer_fine_grained + || state_change_requires_new_enode_p (old_state, next_state)) { program_point split_point = program_point::before_stmt (point.get_supernode (), diff --git a/gcc/analyzer/exploded-graph.h b/gcc/analyzer/exploded-graph.h index c67f7b70605..eb1baefad69 100644 --- a/gcc/analyzer/exploded-graph.h +++ b/gcc/analyzer/exploded-graph.h @@ -198,33 +198,21 @@ class exploded_node : public dnode /* The result of on_stmt. */ struct on_stmt_flags { - on_stmt_flags (bool sm_changes) - : m_sm_changes (sm_changes), - m_terminate_path (false) + on_stmt_flags () : m_terminate_path (false) {} static on_stmt_flags terminate_path () { - return on_stmt_flags (true, true); + return on_stmt_flags (true); } - static on_stmt_flags state_change (bool any_sm_changes) - { - return on_stmt_flags (any_sm_changes, false); - } - - /* Did any sm-changes occur handling the stmt. */ - bool m_sm_changes : 1; - /* Should we stop analyzing this path (on_stmt may have already added nodes/edges, e.g. when handling longjmp). */ bool m_terminate_path : 1; private: - on_stmt_flags (bool sm_changes, - bool terminate_path) - : m_sm_changes (sm_changes), - m_terminate_path (terminate_path) + on_stmt_flags (bool terminate_path) + : m_terminate_path (terminate_path) {} }; diff --git a/gcc/analyzer/program-state.cc b/gcc/analyzer/program-state.cc index 76959c135db..67dd785297e 100644 --- a/gcc/analyzer/program-state.cc +++ b/gcc/analyzer/program-state.cc @@ -1270,6 +1270,15 @@ program_state::detect_leaks (const program_state &src_state, /* Purge dead svals from constraints. */ dest_state.m_region_model->get_constraints ()->on_liveness_change (maybe_dest_svalues, dest_state.m_region_model); + + /* Purge dead heap-allocated regions from dynamic extents. */ + for (const svalue *sval : dead_svals) + if (const region_svalue *region_sval = sval->dyn_cast_region_svalue ()) + { + const region *reg = region_sval->get_pointee (); + if (reg->get_kind () == RK_HEAP_ALLOCATED) + dest_state.m_region_model->unset_dynamic_extents (reg); + } } #if CHECKING_P @@ -1426,7 +1435,7 @@ test_program_state_1 () program_state s (ext_state); region_model *model = s.m_region_model; const svalue *size_in_bytes - = mgr->get_or_create_unknown_svalue (integer_type_node); + = mgr->get_or_create_unknown_svalue (size_type_node); const region *new_reg = model->create_region_for_heap_alloc (size_in_bytes); const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg); model->set_value (model->get_lvalue (p, NULL), @@ -1482,7 +1491,7 @@ test_program_state_merging () region_model *model0 = s0.m_region_model; const svalue *size_in_bytes - = mgr->get_or_create_unknown_svalue (integer_type_node); + = mgr->get_or_create_unknown_svalue (size_type_node); const region *new_reg = model0->create_region_for_heap_alloc (size_in_bytes); const svalue *ptr_sval = mgr->get_ptr_svalue (ptr_type_node, new_reg); model0->set_value (model0->get_lvalue (p, &ctxt), diff --git a/gcc/analyzer/region-model-impl-calls.cc b/gcc/analyzer/region-model-impl-calls.cc index 4052bb393f8..099520a95b0 100644 --- a/gcc/analyzer/region-model-impl-calls.cc +++ b/gcc/analyzer/region-model-impl-calls.cc @@ -206,6 +206,25 @@ region_model::impl_call_analyzer_describe (const gcall *call, warning_at (call->location, 0, "svalue: %qs", desc.m_buffer); } +/* Handle a call to "__analyzer_dump_capacity". + + Emit a warning describing the capacity of the base region of + the region pointed to by the 1st argument. + This is for use when debugging, and may be of use in DejaGnu tests. */ + +void +region_model::impl_call_analyzer_dump_capacity (const gcall *call, + region_model_context *ctxt) +{ + tree t_ptr = gimple_call_arg (call, 0); + const svalue *sval_ptr = get_rvalue (t_ptr, ctxt); + const region *reg = deref_rvalue (sval_ptr, t_ptr, ctxt); + const region *base_reg = reg->get_base_region (); + const svalue *capacity = get_capacity (base_reg); + label_text desc = capacity->get_desc (true); + warning_at (call->location, 0, "capacity: %qs", desc.m_buffer); +} + /* Handle a call to "__analyzer_eval" by evaluating the input and dumping as a dummy warning, so that test cases can use dg-warning to validate the result (and so unexpected warnings will @@ -312,6 +331,7 @@ region_model::impl_call_free (const call_details &cd) poisoning pointers. */ const region *freed_reg = ptr_to_region_sval->get_pointee (); unbind_region_and_descendents (freed_reg, POISON_KIND_FREED); + m_dynamic_extents.remove (freed_reg); } } diff --git a/gcc/analyzer/region-model-reachability.h b/gcc/analyzer/region-model-reachability.h index c6a21e98e61..57daf7255fb 100644 --- a/gcc/analyzer/region-model-reachability.h +++ b/gcc/analyzer/region-model-reachability.h @@ -89,6 +89,14 @@ public: { return m_mutable_svals.end (); } + hash_set::iterator begin_mutable_base_regs () + { + return m_mutable_base_regs.begin (); + } + hash_set::iterator end_mutable_base_regs () + { + return m_mutable_base_regs.end (); + } void dump_to_pp (pretty_printer *pp) const; diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index 43f991a2a29..e02a89765f0 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -66,6 +66,7 @@ along with GCC; see the file COPYING3. If not see #include "analyzer/analyzer-selftests.h" #include "stor-layout.h" #include "attribs.h" +#include "tree-object-size.h" #if ENABLE_ANALYZER @@ -225,7 +226,8 @@ region_to_value_map::can_merge_with_p (const region_to_value_map &other, /* Ctor for region_model: construct an "empty" model. */ region_model::region_model (region_model_manager *mgr) -: m_mgr (mgr), m_store (), m_current_frame (NULL) +: m_mgr (mgr), m_store (), m_current_frame (NULL), + m_dynamic_extents () { m_constraints = new constraint_manager (mgr); } @@ -235,7 +237,8 @@ region_model::region_model (region_model_manager *mgr) region_model::region_model (const region_model &other) : m_mgr (other.m_mgr), m_store (other.m_store), m_constraints (new constraint_manager (*other.m_constraints)), - m_current_frame (other.m_current_frame) + m_current_frame (other.m_current_frame), + m_dynamic_extents (other.m_dynamic_extents) { } @@ -261,6 +264,8 @@ region_model::operator= (const region_model &other) m_current_frame = other.m_current_frame; + m_dynamic_extents = other.m_dynamic_extents; + return *this; } @@ -285,6 +290,9 @@ region_model::operator== (const region_model &other) const if (m_current_frame != other.m_current_frame) return false; + if (m_dynamic_extents != other.m_dynamic_extents) + return false; + gcc_checking_assert (hash () == other.hash ()); return true; @@ -346,6 +354,13 @@ region_model::dump_to_pp (pretty_printer *pp, bool simple, m_constraints->dump_to_pp (pp, multiline); if (!multiline) pp_string (pp, "}"); + + /* Dump sizes of dynamic regions, if any are known. */ + if (!m_dynamic_extents.is_empty ()) + { + pp_string (pp, "dynamic_extents:"); + m_dynamic_extents.dump_to_pp (pp, simple, multiline); + } } /* Dump a representation of this model to FILE. */ @@ -1140,6 +1155,17 @@ region_model::handle_unrecognized_call (const gcall *call, /* Update bindings for all clusters that have escaped, whether above, or previously. */ m_store.on_unknown_fncall (call, m_mgr->get_store_manager ()); + + /* Purge dynamic extents from any regions that have escaped mutably: + realloc could have been called on them. */ + for (hash_set::iterator + iter = reachable_regs.begin_mutable_base_regs (); + iter != reachable_regs.end_mutable_base_regs (); + ++iter) + { + const region *base_reg = (*iter); + unset_dynamic_extents (base_reg); + } } /* Traverse the regions in this model, determining what regions are @@ -1972,6 +1998,41 @@ region_model::check_for_writable_region (const region* dest_reg, } } +/* Get the capacity of REG in bytes. */ + +const svalue * +region_model::get_capacity (const region *reg) const +{ + switch (reg->get_kind ()) + { + default: + break; + case RK_DECL: + { + const decl_region *decl_reg = as_a (reg); + tree decl = decl_reg->get_decl (); + if (TREE_CODE (decl) == SSA_NAME) + { + tree type = TREE_TYPE (decl); + tree size = TYPE_SIZE (type); + return get_rvalue (size, NULL); + } + else + { + tree size = decl_init_size (decl, false); + if (size) + return get_rvalue (size, NULL); + } + } + break; + } + + if (const svalue *recorded = get_dynamic_extents (reg)) + return recorded; + + return m_mgr->get_or_create_unknown_svalue (sizetype); +} + /* Set the value of the region given by LHS_REG to the value given by RHS_SVAL. */ @@ -2241,6 +2302,12 @@ region_model::add_constraint (tree lhs, enum tree_code op, tree rhs, if (ctxt) ctxt->on_condition (lhs, op, rhs); + /* If we have ®ION == NULL, then drop dynamic extents for REGION (for + the case where REGION is heap-allocated and thus could be NULL). */ + if (op == EQ_EXPR && zerop (rhs)) + if (const region_svalue *region_sval = lhs_sval->dyn_cast_region_svalue ()) + unset_dynamic_extents (region_sval->get_pointee ()); + return true; } @@ -3146,7 +3213,8 @@ region_model::get_frame_at_index (int index) const /* Unbind svalues for any regions in REG and below. Find any pointers to such regions; convert them to - poisoned values of kind PKIND. */ + poisoned values of kind PKIND. + Also purge any dynamic extents. */ void region_model::unbind_region_and_descendents (const region *reg, @@ -3167,6 +3235,15 @@ region_model::unbind_region_and_descendents (const region *reg, /* Find any pointers to REG or its descendents; convert to poisoned. */ poison_any_pointers_to_descendents (reg, pkind); + + /* Purge dynamic extents of any base regions in REG and below + (e.g. VLAs and alloca stack regions). */ + for (auto iter : m_dynamic_extents) + { + const region *iter_reg = iter.first; + if (iter_reg->descendent_of_p (reg)) + unset_dynamic_extents (iter_reg); + } } /* Implementation of BindingVisitor. @@ -3241,6 +3318,10 @@ region_model::can_merge_with_p (const region_model &other_model, &m)) return false; + if (!m_dynamic_extents.can_merge_with_p (other_model.m_dynamic_extents, + &out_model->m_dynamic_extents)) + return false; + /* Merge constraints. */ constraint_manager::merge (*m_constraints, *other_model.m_constraints, @@ -3322,7 +3403,8 @@ const region * region_model::create_region_for_heap_alloc (const svalue *size_in_bytes) { const region *reg = m_mgr->create_region_for_heap_alloc (); - record_dynamic_extents (reg, size_in_bytes); + assert_compat_types (size_in_bytes->get_type (), size_type_node); + set_dynamic_extents (reg, size_in_bytes); return reg; } @@ -3333,18 +3415,38 @@ const region * region_model::create_region_for_alloca (const svalue *size_in_bytes) { const region *reg = m_mgr->create_region_for_alloca (m_current_frame); - record_dynamic_extents (reg, size_in_bytes); + assert_compat_types (size_in_bytes->get_type (), size_type_node); + set_dynamic_extents (reg, size_in_bytes); return reg; } -/* Placeholder hook for recording that the size of REG is SIZE_IN_BYTES. - Currently does nothing. */ +/* Record that the size of REG is SIZE_IN_BYTES. */ void -region_model:: -record_dynamic_extents (const region *reg ATTRIBUTE_UNUSED, - const svalue *size_in_bytes ATTRIBUTE_UNUSED) +region_model::set_dynamic_extents (const region *reg, + const svalue *size_in_bytes) +{ + assert_compat_types (size_in_bytes->get_type (), size_type_node); + m_dynamic_extents.put (reg, size_in_bytes); +} + +/* Get the recording of REG in bytes, or NULL if no dynamic size was + recorded. */ + +const svalue * +region_model::get_dynamic_extents (const region *reg) const { + if (const svalue * const *slot = m_dynamic_extents.get (reg)) + return *slot; + return NULL; +} + +/* Unset any recorded dynamic size of REG. */ + +void +region_model::unset_dynamic_extents (const region *reg) +{ + m_dynamic_extents.remove (reg); } /* struct model_merger. */ @@ -4644,7 +4746,7 @@ test_state_merging () { test_region_model_context ctxt; region_model model0 (&mgr); - tree size = build_int_cst (integer_type_node, 1024); + tree size = build_int_cst (size_type_node, 1024); const svalue *size_sval = mgr.get_or_create_constant_svalue (size); const region *new_reg = model0.create_region_for_heap_alloc (size_sval); const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg); @@ -5034,7 +5136,7 @@ test_malloc_constraints () tree null_ptr = build_int_cst (ptr_type_node, 0); const svalue *size_in_bytes - = mgr.get_or_create_unknown_svalue (integer_type_node); + = mgr.get_or_create_unknown_svalue (size_type_node); const region *reg = model.create_region_for_heap_alloc (size_in_bytes); const svalue *sval = mgr.get_ptr_svalue (ptr_type_node, reg); model.set_value (model.get_lvalue (p, NULL), sval, NULL); @@ -5259,7 +5361,7 @@ test_malloc () const region *reg = model.create_region_for_heap_alloc (size_sval); const svalue *ptr = mgr.get_ptr_svalue (int_star, reg); model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt); - // TODO: verify dynamic extents + ASSERT_EQ (model.get_capacity (reg), size_sval); } /* Verify that alloca works. */ @@ -5294,7 +5396,7 @@ test_alloca () ASSERT_EQ (reg->get_parent_region (), frame_reg); const svalue *ptr = mgr.get_ptr_svalue (int_star, reg); model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt); - // TODO: verify dynamic extents + ASSERT_EQ (model.get_capacity (reg), size_sval); /* Verify that the pointers to the alloca region are replaced by poisoned values when the frame is popped. */ diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h index 0afcb8635a9..8b669df00be 100644 --- a/gcc/analyzer/region-model.h +++ b/gcc/analyzer/region-model.h @@ -163,6 +163,8 @@ public: m_hash_map.remove (reg); } + bool is_empty () const { return m_hash_map.is_empty (); } + void dump_to_pp (pretty_printer *pp, bool simple, bool multiline) const; void dump (bool simple) const; @@ -450,12 +452,16 @@ private: a tree of regions, along with their associated values. The representation is graph-like because values can be pointers to regions. - It also stores a constraint_manager, capturing relationships between - the values. */ + It also stores: + - a constraint_manager, capturing relationships between the values, and + - dynamic extents, mapping dynamically-allocated regions to svalues (their + capacities). */ class region_model { public: + typedef region_to_value_map dynamic_extents_t; + region_model (region_model_manager *mgr); region_model (const region_model &other); ~region_model (); @@ -495,6 +501,8 @@ class region_model bool impl_call_alloca (const call_details &cd); void impl_call_analyzer_describe (const gcall *call, region_model_context *ctxt); + void impl_call_analyzer_dump_capacity (const gcall *call, + region_model_context *ctxt); void impl_call_analyzer_eval (const gcall *call, region_model_context *ctxt); bool impl_call_builtin_expect (const call_details &cd); @@ -606,6 +614,16 @@ class region_model store *get_store () { return &m_store; } const store *get_store () const { return &m_store; } + const dynamic_extents_t & + get_dynamic_extents () const + { + return m_dynamic_extents; + } + const svalue *get_dynamic_extents (const region *reg) const; + void set_dynamic_extents (const region *reg, + const svalue *size_in_bytes); + void unset_dynamic_extents (const region *reg); + region_model_manager *get_manager () const { return m_mgr; } void unbind_region_and_descendents (const region *reg, @@ -629,6 +647,8 @@ class region_model void loop_replay_fixup (const region_model *dst_state); + const svalue *get_capacity (const region *reg) const; + 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; @@ -676,9 +696,6 @@ class region_model void on_top_level_param (tree param, region_model_context *ctxt); - void record_dynamic_extents (const region *reg, - const svalue *size_in_bytes); - bool called_from_main_p () const; const svalue *get_initial_value_for_global (const region *reg) const; @@ -693,6 +710,12 @@ class region_model constraint_manager *m_constraints; // TODO: embed, rather than dynalloc? const frame_region *m_current_frame; + + /* Map from base region to size in bytes, for tracking the sizes of + dynamically-allocated regions. + This is part of the region_model rather than the region to allow for + memory regions to be resized (e.g. by realloc). */ + dynamic_extents_t m_dynamic_extents; }; /* Some region_model activity could lead to warnings (e.g. attempts to use an diff --git a/gcc/doc/analyzer.texi b/gcc/doc/analyzer.texi index 26808ff5d22..2ca4bf61352 100644 --- a/gcc/doc/analyzer.texi +++ b/gcc/doc/analyzer.texi @@ -479,6 +479,13 @@ __analyzer_dump (); will dump the copious information about the analyzer's state each time it reaches the call in its traversal of the source. +@smallexample +extern void __analyzer_dump_capacity (const void *ptr); +@end smallexample + +will emit a warning describing the capacity of the base region of +the region pointed to by the 1st argument. + @smallexample __analyzer_dump_path (); @end smallexample diff --git a/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h b/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h index d96b3f2f29a..24466939882 100644 --- a/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h +++ b/gcc/testsuite/gcc.dg/analyzer/analyzer-decls.h @@ -15,6 +15,9 @@ extern void __analyzer_describe (int verbosity, ...); /* Dump copious information about the analyzer’s state when reached. */ extern void __analyzer_dump (void); +/* Emit a warning describing the size of the base region of (*ptr). */ +extern void __analyzer_dump_capacity (const void *ptr); + /* Dump information after analysis on all of the exploded nodes at this program point. diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-1.c b/gcc/testsuite/gcc.dg/analyzer/capacity-1.c new file mode 100644 index 00000000000..9ea41f72e1d --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/capacity-1.c @@ -0,0 +1,106 @@ +#include +#include "analyzer-decls.h" + +typedef unsigned __INT32_TYPE__ u32; + +void +test_1 (void) +{ + char buf[16]; + __analyzer_dump_capacity (buf); /* { dg-warning "capacity: '\\(sizetype\\)16'" } */ +} + +void +test_2 (void) +{ + char ch; + __analyzer_dump_capacity (&ch); /* { dg-warning "capacity: '\\(sizetype\\)1'" } */ +} + +struct s3 { char buf[100]; }; + +void +test_3 (void) +{ + struct s3 s; + __analyzer_dump_capacity (&s); /* { dg-warning "capacity: '\\(sizetype\\)100'" } */ +} + +/* Capacity refers to the base region, not any offset within it. */ + +void +test_4 (void) +{ + char buf[1024]; + __analyzer_dump_capacity (buf + 100); /* { dg-warning "capacity: '\\(sizetype\\)1024'" } */ +} + +void +test_5 (void *p) +{ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ +} + +void +test_malloc (void) +{ + void *p = malloc (1024); + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */ + free (p); +} + +void +test_alloca (size_t sz) +{ + void *p = alloca (sz); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */ +} + +void +test_vla (size_t sz) +{ + char buf[sz]; + __analyzer_dump_capacity (buf); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */ +} + +static void * __attribute__((noinline)) +called_by_test_interproc_malloc (size_t a) +{ + return malloc (a); +} + +void * +test_interproc_malloc (size_t sz) +{ + void *p = called_by_test_interproc_malloc (sz); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */ + return p; +} + +struct s +{ + u32 f1; + char arr[]; +}; + +static struct s * __attribute__((noinline)) +alloc_s (size_t num) +{ + struct s *p = malloc (sizeof(struct s) + num); + return p; +} + +struct s * +test_trailing_array (void) +{ + struct s *p = alloc_s (5); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(\[^\n\r\]*\\)9'" } */ + return p; +} + +void +test_unknown_arr (int p[]) +{ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-2.c b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c new file mode 100644 index 00000000000..9f92bcfc0a4 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/capacity-2.c @@ -0,0 +1,53 @@ +#include +#include "analyzer-decls.h" + +extern void might_realloc (void *); +extern void cant_realloc (const void *); + +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\\)'" } */ + return q; +} + +void * +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; +} + +void * +test_might_realloc (void) +{ + void *p = malloc (1024); + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */ + + might_realloc (p); + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ + + return p; +} + +void * +test_cant_realloc (void) +{ + void *p = malloc (1024); + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */ + + cant_realloc (p); + + __analyzer_dump_capacity (p); /* { dg-warning "capacity: '\\(size_t\\)1024'" } */ + + return p; +} + + diff --git a/gcc/testsuite/gcc.dg/analyzer/capacity-3.c b/gcc/testsuite/gcc.dg/analyzer/capacity-3.c new file mode 100644 index 00000000000..41e282cee92 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/capacity-3.c @@ -0,0 +1,82 @@ +#include +#include "analyzer-decls.h" + +static void __attribute__((noinline)) +__analyzer_callee_1 (size_t inner_sz) +{ + void *p = alloca (inner_sz); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(outer_sz_\[^\n\r\]*\\)'" } */ +} + +void +test_1 (int flag, size_t outer_sz) +{ + if (flag) + __analyzer_callee_1 (outer_sz); + + /* Verify that we merge state; in particular, the dynamic size of "p" + in the called frame should have been purged. */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ +} + +void +test_2 (int flag, size_t sz) +{ + if (flag) + { + void *p = malloc (sz); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */ + free (p); + /* The dynamic size of "p" should have been purged. */ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ + } + + /* Verify that we merge state. */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ +} +/* Verify that we purge state on the NULL branch when a malloc result is + tested against NULL. */ + +void +test_3 (size_t sz) +{ + void *p = malloc (sz); + + if (p) + { + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(sz_\[^\n\r\]*\\)'" } */ + } + else + { + /* The dynamic size of "p" should have been purged + due to "p" being equal to NULL. */ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ + } + + free (p); + + /* The dynamic size of "p" should have been purged. */ + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'UNKNOWN\\(sizetype\\)'" } */ + + /* Verify that we merge state. */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ +} + +/* Verify that we purge dynamic extent of a pointer when it leaks. */ + +static void __attribute__((noinline)) +__analyzer_callee_4 (size_t inner_sz) +{ + void *p = malloc (inner_sz); + __analyzer_dump_capacity (p); /* { dg-warning "capacity: 'INIT_VAL\\(outer_sz_\[^\n\r\]*\\)'" } */ +} /* { dg-warning "leak of 'p'" } */ + +void +test_4 (int flag, size_t outer_sz) +{ + if (flag) + __analyzer_callee_4 (outer_sz); + + /* Verify that we merge state. */ + __analyzer_dump_exploded_nodes (0); /* { dg-warning "1 processed enode" } */ +}