From patchwork Fri Mar 10 16:58:41 2023 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: David Malcolm X-Patchwork-Id: 1755397 Return-Path: X-Original-To: incoming@patchwork.ozlabs.org Delivered-To: patchwork-incoming@legolas.ozlabs.org Authentication-Results: legolas.ozlabs.org; spf=pass (sender SPF authorized) smtp.mailfrom=gcc.gnu.org (client-ip=2620:52:3:1:0:246e:9693:128c; helo=sourceware.org; envelope-from=gcc-patches-bounces+incoming=patchwork.ozlabs.org@gcc.gnu.org; receiver=) Authentication-Results: legolas.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=f/DwEqJf; dkim-atps=neutral Received: from sourceware.org (server2.sourceware.org [IPv6:2620:52:3:1:0:246e:9693:128c]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature ECDSA (P-384) server-digest SHA384) (No client certificate requested) by legolas.ozlabs.org (Postfix) with ESMTPS id 4PYC2B2tTqz2472 for ; Sat, 11 Mar 2023 03:59:12 +1100 (AEDT) Received: from server2.sourceware.org (localhost [IPv6:::1]) by sourceware.org (Postfix) with ESMTP id 248D93858410 for ; Fri, 10 Mar 2023 16:59:10 +0000 (GMT) DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 248D93858410 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org; s=default; t=1678467550; bh=XiBn5yZvBKzj29WE3jBwOH+DofcN/JBe1Wt7DG8uL/Y=; h=To:Cc:Subject:Date:List-Id:List-Unsubscribe:List-Archive: List-Post:List-Help:List-Subscribe:From:Reply-To:From; b=f/DwEqJf1gNDPARdfQOPDrYd1hwuJOv8UKZm0NyLu3pliIsgjiZK+rZYzUxjxehmr v0aduK96ESN4Fym3aMYG6ioXqU4TK6FIT3s1nglPTcpjIw4cCPJKmzdp1jZFbcaRPP erGSht/fVk3PtL17+pY8Yz65AhX9aVEaA39QSPHQ= 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 ESMTPS id 14AA33858D32 for ; Fri, 10 Mar 2023 16:58:46 +0000 (GMT) DMARC-Filter: OpenDMARC Filter v1.4.2 sourceware.org 14AA33858D32 Received: from mimecast-mx02.redhat.com (mimecast-mx02.redhat.com [66.187.233.88]) by relay.mimecast.com with ESMTP with STARTTLS (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_GCM_SHA384) id us-mta-74-RizaL_J2PTqLFXDwR2_r8g-1; Fri, 10 Mar 2023 11:58:43 -0500 X-MC-Unique: RizaL_J2PTqLFXDwR2_r8g-1 Received: from smtp.corp.redhat.com (int-mx04.intmail.prod.int.rdu2.redhat.com [10.11.54.4]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by mimecast-mx02.redhat.com (Postfix) with ESMTPS id 1D0B4800045 for ; Fri, 10 Mar 2023 16:58:43 +0000 (UTC) Received: from t14s.localdomain.com (unknown [10.2.17.70]) by smtp.corp.redhat.com (Postfix) with ESMTP id E0A062026D4B; Fri, 10 Mar 2023 16:58:42 +0000 (UTC) To: gcc-patches@gcc.gnu.org Cc: David Malcolm Subject: [pushed] analyzer: fix leak false +ve seen in haproxy's cfgparse.c [PR109059] Date: Fri, 10 Mar 2023 11:58:41 -0500 Message-Id: <20230310165841.3179375-1-dmalcolm@redhat.com> MIME-Version: 1.0 X-Scanned-By: MIMEDefang 3.1 on 10.11.54.4 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: redhat.com X-Spam-Status: No, score=-11.5 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_NONE, RCVD_IN_MSPIKE_H2, SPF_HELO_NONE, SPF_NONE, TXREP autolearn=ham autolearn_force=no version=3.4.6 X-Spam-Checker-Version: SpamAssassin 3.4.6 (2021-04-09) 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" If a bound region gets overwritten with UNKNOWN due to being possibly-aliased during a write, that could have been the only region keeping its value live, in which case we could falsely report a leak. This is hidden somewhat by the "uncertainty" mechanism for cases where the write happens in the same stmt as the last reference to the value goes away, but not in the general case, which occurs in PR analyzer/109059, which falsely complains about a leak whilst haproxy updates a doubly-linked list. The whole "uncertainty_t" class seems broken to me now; I think we need to track (in the store) what values could have escaped to the external part of the program. We do this to some extent for pointers by tracking the region as escaped, though we're failing to do this for this case: even though there could still be other pointers to the region, eventually they go away; we want to capture the fact that the external part of the state is still keeping it live. Also, this doesn't work for non-pointer svalues, such as for detecting file-descriptor leaks. As both a workaround and a step towards eventually removing "class uncertainty_t" this patch updates the "mark_region_as_unknown" code called by possibly-aliased set_value so that when old values are removed, any base region pointed to them is marked as escaped, fixing the leak false positive. The patch has this effect on my integration tests of -fanalyzer: Comparison: GOOD: 129 (19.20% -> 20.22%) BAD: 543 -> 509 (-34) where there's a big improvement in -Wanalyzer-malloc-leak: -Wanalyzer-malloc-leak: GOOD: 61 (45.19% -> 54.95%) BAD: 74 -> 50 (-24) Known false positives: 25 -> 2 (-23) haproxy-2.7.1: 24 -> 1 (-23) Suspected false positives: 49 -> 48 (-1) coreutils-9.1: 32 -> 31 (-1) and some churn in the other warnings: -Wanalyzer-use-of-uninitialized-value: GOOD: 0 BAD: 81 -> 80 (-1) -Wanalyzer-file-leak: GOOD: 0 BAD: 10 -> 11 (+1) -Wanalyzer-out-of-bounds: GOOD: 0 BAD: 24 -> 22 (-2) Successfully bootstrapped & regrtested on x86_64-pc-linux-gnu. Pushed to trunk as r13-6589-g14f5e56a8a766c. gcc/analyzer/ChangeLog: PR analyzer/109059 * region-model.cc (region_model::mark_region_as_unknown): Gather a set of maybe-live svalues and call on_maybe_live_values with it. * store.cc (binding_map::remove_overlapping_bindings): Add new "maybe_live_values" param; add any removed svalues to it. (binding_cluster::clobber_region): Add NULL as new param of remove_overlapping_bindings. (binding_cluster::mark_region_as_unknown): Add "maybe_live_values" param and pass it to remove_overlapping_bindings. (binding_cluster::maybe_get_compound_binding): Add NULL for new param of binding_map::remove_overlapping_bindings. (binding_cluster::remove_overlapping_bindings): Add "maybe_live_values" param and pass to binding_map::remove_overlapping_bindings. (store::set_value): Capture a set of maybe-live svalues, and call on_maybe_live_values with it. (store::on_maybe_live_values): New. (store::mark_region_as_unknown): Add "maybe_live_values" param and pass it to binding_cluster::mark_region_as_unknown. (store::remove_overlapping_bindings): Pass NULL for new param of binding_cluster::remove_overlapping_bindings. * store.h (binding_map::remove_overlapping_bindings): Add "maybe_live_values" param. (binding_cluster::mark_region_as_unknown): Likewise. (binding_cluster::remove_overlapping_bindings): Likewise. (store::mark_region_as_unknown): Likewise. (store::on_maybe_live_values): New decl. gcc/testsuite/ChangeLog: PR analyzer/109059 * gcc.dg/analyzer/flex-with-call-summaries.c: Remove xfail. * gcc.dg/analyzer/leak-pr109059-1.c: New test. * gcc.dg/analyzer/leak-pr109059-2.c: New test. Signed-off-by: David Malcolm --- gcc/analyzer/region-model.cc | 4 +- gcc/analyzer/store.cc | 70 +++++++++++++++---- gcc/analyzer/store.h | 11 ++- .../analyzer/flex-with-call-summaries.c | 3 +- .../gcc.dg/analyzer/leak-pr109059-1.c | 46 ++++++++++++ .../gcc.dg/analyzer/leak-pr109059-2.c | 42 +++++++++++ 6 files changed, 158 insertions(+), 18 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/analyzer/leak-pr109059-1.c create mode 100644 gcc/testsuite/gcc.dg/analyzer/leak-pr109059-2.c diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc index bf07cec2884..56beaa82f95 100644 --- a/gcc/analyzer/region-model.cc +++ b/gcc/analyzer/region-model.cc @@ -3296,8 +3296,10 @@ void region_model::mark_region_as_unknown (const region *reg, uncertainty_t *uncertainty) { + svalue_set maybe_live_values; m_store.mark_region_as_unknown (m_mgr->get_store_manager(), reg, - uncertainty); + uncertainty, &maybe_live_values); + m_store.on_maybe_live_values (maybe_live_values); } /* Determine what is known about the condition "LHS_SVAL OP RHS_SVAL" within diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc index e964545b084..e8c927b9fe9 100644 --- a/gcc/analyzer/store.cc +++ b/gcc/analyzer/store.cc @@ -1078,6 +1078,9 @@ binding_map::get_overlapping_bindings (const binding_key *key, If UNCERTAINTY is non-NULL, use it to record any svalues that were removed, as being maybe-bound. + If MAYBE_LIVE_VALUES is non-NULL, then use it to record any svalues that + were removed as being maybe-live. + If ALWAYS_OVERLAP, then assume that DROP_KEY can overlap anything in the map, due to one or both of the underlying clusters being symbolic (but not the same symbolic region). Hence even if DROP_KEY is a @@ -1089,6 +1092,7 @@ void binding_map::remove_overlapping_bindings (store_manager *mgr, const binding_key *drop_key, uncertainty_t *uncertainty, + svalue_set *maybe_live_values, bool always_overlap) { /* Get the bindings of interest within this map. */ @@ -1123,6 +1127,11 @@ binding_map::remove_overlapping_bindings (store_manager *mgr, || always_overlap)) uncertainty->on_maybe_bound_sval (old_sval); + /* Record any svalues that were removed to *MAYBE_LIVE_VALUES as being + maybe-live. */ + if (maybe_live_values) + maybe_live_values->add (old_sval); + /* Begin by removing the old binding. */ m_map.remove (iter_binding); @@ -1416,7 +1425,7 @@ binding_cluster::bind_compound_sval (store_manager *mgr, void binding_cluster::clobber_region (store_manager *mgr, const region *reg) { - remove_overlapping_bindings (mgr, reg, NULL); + remove_overlapping_bindings (mgr, reg, NULL, NULL); } /* Remove any bindings for REG within this cluster. */ @@ -1464,6 +1473,8 @@ binding_cluster::zero_fill_region (store_manager *mgr, const region *reg) Remove any bindings overlapping REG_FOR_OVERLAP. If UNCERTAINTY is non-NULL, use it to record any svalues that had bindings to them removed, as being maybe-bound. + If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that + had bindings to them removed, as being maybe-live. REG_TO_BIND and REG_FOR_OVERLAP are the same for store::mark_region_as_unknown, but are different in @@ -1474,12 +1485,14 @@ void binding_cluster::mark_region_as_unknown (store_manager *mgr, const region *reg_to_bind, const region *reg_for_overlap, - uncertainty_t *uncertainty) + uncertainty_t *uncertainty, + svalue_set *maybe_live_values) { if (reg_to_bind->empty_p ()) return; - remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty); + remove_overlapping_bindings (mgr, reg_for_overlap, uncertainty, + maybe_live_values); /* Add a default binding to "unknown". */ region_model_manager *sval_mgr = mgr->get_svalue_manager (); @@ -1748,7 +1761,7 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, it overlaps with offset_concrete_key. */ default_map.remove_overlapping_bindings (mgr, offset_concrete_key, - NULL, false); + NULL, NULL, false); } else if (bound_range.contains_p (reg_range, &subrange)) { @@ -1782,7 +1795,7 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, it overlaps with overlap_concrete_key. */ default_map.remove_overlapping_bindings (mgr, overlap_concrete_key, - NULL, false); + NULL, NULL, false); } } else @@ -1813,12 +1826,16 @@ binding_cluster::maybe_get_compound_binding (store_manager *mgr, in the map. If UNCERTAINTY is non-NULL, use it to record any svalues that - were removed, as being maybe-bound. */ + were removed, as being maybe-bound. + + If MAYBE_LIVE_VALUES is non-NULL, use it to record any svalues that + were removed, as being maybe-live. */ void binding_cluster::remove_overlapping_bindings (store_manager *mgr, const region *reg, - uncertainty_t *uncertainty) + uncertainty_t *uncertainty, + svalue_set *maybe_live_values) { if (reg->empty_p ()) return; @@ -1836,6 +1853,7 @@ binding_cluster::remove_overlapping_bindings (store_manager *mgr, && (cluster_base_reg->get_kind () == RK_SYMBOLIC || other_base_reg->get_kind () == RK_SYMBOLIC)); m_map.remove_overlapping_bindings (mgr, reg_binding, uncertainty, + maybe_live_values, always_overlap); } @@ -2600,7 +2618,10 @@ store::set_value (store_manager *mgr, const region *lhs_reg, Writes to symbolic clusters can affect both concrete and symbolic clusters. Invalidate our knowledge of other clusters that might have been - affected by the write. */ + affected by the write. + Gather the set of all svalues that might still be live even if + the store doesn't refer to them. */ + svalue_set maybe_live_values; for (cluster_map_t::iterator iter = m_cluster_map.begin (); iter != m_cluster_map.end (); ++iter) { @@ -2637,7 +2658,8 @@ store::set_value (store_manager *mgr, const region *lhs_reg, (mgr, iter_base_reg, /* reg_to_bind */ lhs_reg, /* reg_for_overlap */ - uncertainty); + uncertainty, + &maybe_live_values); break; case tristate::TS_TRUE: @@ -2651,6 +2673,11 @@ store::set_value (store_manager *mgr, const region *lhs_reg, } } } + /* Given the set of svalues that might still be live, process them + (e.g. marking regions as escaped). + We do this after the iteration to avoid potentially changing + m_cluster_map whilst iterating over it. */ + on_maybe_live_values (maybe_live_values); } /* Determine if BASE_REG_A could be an alias of BASE_REG_B. */ @@ -2731,6 +2758,21 @@ store::eval_alias_1 (const region *base_reg_a, return tristate::TS_UNKNOWN; } +/* Record all of the values in MAYBE_LIVE_VALUES as being possibly live. */ + +void +store::on_maybe_live_values (const svalue_set &maybe_live_values) +{ + for (auto sval : maybe_live_values) + { + if (const region_svalue *ptr_sval = sval->dyn_cast_region_svalue ()) + { + const region *base_reg = ptr_sval->get_pointee ()->get_base_region (); + mark_as_escaped (base_reg); + } + } +} + /* Remove all bindings overlapping REG within this store. */ void @@ -2798,14 +2840,16 @@ store::zero_fill_region (store_manager *mgr, const region *reg) void store::mark_region_as_unknown (store_manager *mgr, const region *reg, - uncertainty_t *uncertainty) + uncertainty_t *uncertainty, + svalue_set *maybe_live_values) { const region *base_reg = reg->get_base_region (); if (base_reg->symbolic_for_unknown_ptr_p () || !base_reg->tracked_p ()) return; binding_cluster *cluster = get_or_create_cluster (base_reg); - cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty); + cluster->mark_region_as_unknown (mgr, reg, reg, uncertainty, + maybe_live_values); } /* Purge state involving SVAL. */ @@ -3052,7 +3096,9 @@ store::remove_overlapping_bindings (store_manager *mgr, const region *reg, delete cluster; return; } - cluster->remove_overlapping_bindings (mgr, reg, uncertainty); + /* Pass NULL for the maybe_live_values here, as we don't want to + record the old svalues as being maybe-bound. */ + cluster->remove_overlapping_bindings (mgr, reg, uncertainty, NULL); } } diff --git a/gcc/analyzer/store.h b/gcc/analyzer/store.h index 7441e2a0bc0..7ded650b608 100644 --- a/gcc/analyzer/store.h +++ b/gcc/analyzer/store.h @@ -541,6 +541,7 @@ public: void remove_overlapping_bindings (store_manager *mgr, const binding_key *drop_key, uncertainty_t *uncertainty, + svalue_set *maybe_live_values, bool always_overlap); private: @@ -607,7 +608,8 @@ public: void mark_region_as_unknown (store_manager *mgr, const region *reg_to_bind, const region *reg_for_overlap, - uncertainty_t *uncertainty); + uncertainty_t *uncertainty, + svalue_set *maybe_live_values); void purge_state_involving (const svalue *sval, region_model_manager *sval_mgr); @@ -620,7 +622,8 @@ public: const region *reg) const; void remove_overlapping_bindings (store_manager *mgr, const region *reg, - uncertainty_t *uncertainty); + uncertainty_t *uncertainty, + svalue_set *maybe_live_values); template void for_each_value (void (*cb) (const svalue *sval, T user_data), @@ -746,7 +749,8 @@ public: void fill_region (store_manager *mgr, const region *reg, const svalue *sval); void zero_fill_region (store_manager *mgr, const region *reg); void mark_region_as_unknown (store_manager *mgr, const region *reg, - uncertainty_t *uncertainty); + uncertainty_t *uncertainty, + svalue_set *maybe_live_values); void purge_state_involving (const svalue *sval, region_model_manager *sval_mgr); @@ -801,6 +805,7 @@ public: void replay_call_summary_cluster (call_summary_replay &r, const store &summary, const region *base_reg); + void on_maybe_live_values (const svalue_set &maybe_live_values); private: void remove_overlapping_bindings (store_manager *mgr, const region *reg, diff --git a/gcc/testsuite/gcc.dg/analyzer/flex-with-call-summaries.c b/gcc/testsuite/gcc.dg/analyzer/flex-with-call-summaries.c index 0ff652b427b..79f2f8e1879 100644 --- a/gcc/testsuite/gcc.dg/analyzer/flex-with-call-summaries.c +++ b/gcc/testsuite/gcc.dg/analyzer/flex-with-call-summaries.c @@ -1469,8 +1469,7 @@ YY_BUFFER_STATE yy_scan_bytes (const char * yybytes, int _yybytes_len ) */ b->yy_is_our_buffer = 1; - return b; /* { dg-bogus "leak" "" { xfail *-*-* } } */ - /* TODO: leak false positive: PR analyzer/103546. */ + return b; /* { dg-bogus "leak" } */ } #ifndef YY_EXIT_FAILURE diff --git a/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-1.c b/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-1.c new file mode 100644 index 00000000000..033ab79460e --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-1.c @@ -0,0 +1,46 @@ +/* Reduced from haproxy-2.7.1's cfgparse.c. */ + +typedef __SIZE_TYPE__ size_t; + +extern void* +calloc(size_t __nmemb, size_t __size) + __attribute__((__nothrow__, __leaf__)) + __attribute__((__malloc__)) __attribute__((__alloc_size__(1, 2))); + +struct list +{ + struct list* n; + struct list* p; +}; + +struct cfg_postparser +{ + struct list list; + char* name; + int (*func)(); +}; + +extern struct list postparsers; + +int +cfg_register_postparser(char* name, int (*func)()) +{ + struct cfg_postparser* cp; + + cp = calloc(1, sizeof(*cp)); + if (!cp) { + /* [...snip...] */ + return 0; + } + cp->name = name; + cp->func = func; + + ({ + (&cp->list)->p = (&postparsers)->p; + (&cp->list)->p->n = (&postparsers)->p = (&cp->list); + (&cp->list)->n = (&postparsers); + (&cp->list); + }); + + return 1; /* { dg-bogus "leak of 'cp'" } */ +} diff --git a/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-2.c b/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-2.c new file mode 100644 index 00000000000..125bce84864 --- /dev/null +++ b/gcc/testsuite/gcc.dg/analyzer/leak-pr109059-2.c @@ -0,0 +1,42 @@ +/* Reduced from haproxy-2.7.1's cfgparse.c. */ + +typedef __SIZE_TYPE__ size_t; + +extern void* +calloc(size_t __nmemb, size_t __size) + __attribute__((__nothrow__, __leaf__)) + __attribute__((__malloc__)) __attribute__((__alloc_size__(1, 2))); + +struct list +{ + struct list* n; + struct list* p; +}; + +struct cfg_postparser +{ + struct list list; + char* name; +}; + +extern struct list postparsers; + +int +test_1 (char* name) +{ + struct cfg_postparser* cp; + + cp = calloc(1, sizeof(*cp)); + if (!cp) { + /* [...snip...] */ + return 0; + } + cp->name = name; + + (&cp->list)->p = (&postparsers)->p; + (&postparsers)->p = (&cp->list); + (&cp->list)->p->n = (&postparsers)->p; + (&cp->list)->n = (&postparsers); + + return 1; /* { dg-bogus "leak of 'cp'" } */ +}