analyzer: revamp of heap-allocated regions [PR106473]

PR analyzer/106473 reports a false positive from -Wanalyzer-malloc-leak
on:

  void foo(char **args[], int *argc) {
      *argc = 1;
      (*args)[0] = __builtin_malloc(42);
  }

The issue is that at the write to *argc we don't know if argc could
point within *args, and so we conservatiely set *args to be unknown.
At the write "(*args)[0] = __builtin_malloc(42)" we have the result of
the allocation written through an unknown pointer, so we mark the
heap_allocated_region as having escaped.
Unfortunately, within store::canonicalize we overzealously purge the
heap allocated region, losing the information that it has escaped, and
thus errnoeously report a leak.

The first part of the fix is to update store::canonicalize so that it
doesn't purge heap_allocated_regions that are marked as escaping.

Doing so fixes the leak false positive, but leads to various state
explosions relating to anywhere we have a malloc/free pair in a loop,
where the analysis of the iteration appears to only have been reaching
a fixed state due to a bug in the state merger code that was erroneously
merging state about the region allocated in one iteration with that
of another.  On touching that, the analyzer fails to reach a fixed state
on any loops containing a malloc/free pair, since each analysis of a
malloc was creating a new heap_allocated_region instance.

Hence the second part of the fix is to revamp how heap_allocated_regions
are managed within the analyzer.  Rather than create a new one at each
analysis of a malloc call, instead we reuse them across the analysis,
only creating a new one if the current path's state is referencing all
of the existing ones.  Hence the heap_allocated_region instances get
used in a fixed order along every analysis path, so e.g. at:

  if (flag)
    p = malloc (4096);
  else
    p = malloc (1024);

both paths now use the same heap_allocated_region for their malloc
calls - but we still end up with two enodes after the CFG merger, by
rejecting merger of states with non-equal dynamic extents.

gcc/analyzer/ChangeLog:
	PR analyzer/106473
	* call-summary.cc
	(call_summary_replay::convert_region_from_summary_1): Update for
	change to creation of heap-allocated regions.
	* program-state.cc (test_program_state_1): Likewise.
	(test_program_state_merging): Likewise.
	* region-model-impl-calls.cc (kf_calloc::impl_call_pre): Likewise.
	(kf_malloc::impl_call_pre): Likewise.
	(kf_operator_new::impl_call_pre): Likewise.
	(kf_realloc::impl_call_postsuccess_with_move::update_model): Likewise.
	* region-model-manager.cc
	(region_model_manager::create_region_for_heap_alloc): Convert
	to...
	(region_model_manager::get_or_create_region_for_heap_alloc):
	...this, reusing an existing region if it's unreferenced in the
	client state.
	* region-model-manager.h (region_model_manager::get_num_regions): New.
	 (region_model_manager::create_region_for_heap_alloc): Convert to...
	 (region_model_manager::get_or_create_region_for_heap_alloc): ...this.
	* region-model.cc (region_to_value_map::can_merge_with_p): Reject
	merger when the values are different.
	(region_model::create_region_for_heap_alloc): Convert to...
	(region_model::get_or_create_region_for_heap_alloc): ...this.
	(region_model::get_referenced_base_regions): New.
	(selftest::test_state_merging):  Update for change to creation of
	heap-allocated regions.
	(selftest::test_malloc_constraints): Likewise.
	(selftest::test_malloc): Likewise.
	* region-model.h: Include "sbitmap.h".
	(region_model::create_region_for_heap_alloc): Convert to...
	(region_model::get_or_create_region_for_heap_alloc): ...this.
	(region_model::get_referenced_base_regions): New decl.
	* store.cc (store::canonicalize): Don't purge a heap-allocated region
	that's been marked as escaping.

gcc/testsuite/ChangeLog:
	PR analyzer/106473
	* gcc.dg/analyzer/aliasing-pr106473.c: New test.
	* gcc.dg/analyzer/allocation-size-2.c: Add
	-fanalyzer-fine-grained".
	* gcc.dg/analyzer/allocation-size-3.c: Likewise.
	* gcc.dg/analyzer/explode-1.c: Mark leak with XFAIL.
	* gcc.dg/analyzer/explode-3.c: New test.
	* gcc.dg/analyzer/malloc-reuse.c: New test.

Signed-off-by: David Malcolm <dmalcolm@redhat.com>

1 files changed, 53 insertions, 13 deletions

diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 92f8b94..7f2c0b6 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -209,8 +209,9 @@ region_to_value_map::dump (bool simple) const
    to OUT.
 
    For now, write (region, value) mappings that are in common between THIS
-   and OTHER to OUT, effectively taking the intersection, rather than
-   rejecting differences.  */
+   and OTHER to OUT, effectively taking the intersection.
+
+   Reject merger of different values.  */
 
 bool
 region_to_value_map::can_merge_with_p (const region_to_value_map &other,
@@ -222,8 +223,12 @@ region_to_value_map::can_merge_with_p (const region_to_value_map &other,
       const svalue *iter_sval = iter.second;
       const svalue * const * other_slot = other.get (iter_reg);
       if (other_slot)
-	if (iter_sval == *other_slot)
-	  out->put (iter_reg, iter_sval);
+	{
+	  if (iter_sval == *other_slot)
+	    out->put (iter_reg, iter_sval);
+	  else
+	    return false;
+	}
     }
   return true;
 }
@@ -5498,19 +5503,52 @@ region_model::check_dynamic_size_for_floats (const svalue *size_in_bytes,
 	}
 }
 
-/* Return a new region describing a heap-allocated block of memory.
-   Use CTXT to complain about tainted sizes.  */
+/* Return a region describing a heap-allocated block of memory.
+   Use CTXT to complain about tainted sizes.
+
+   Reuse an existing heap_allocated_region if it's not being referenced by
+   this region_model; otherwise create a new one.  */
 
 const region *
-region_model::create_region_for_heap_alloc (const svalue *size_in_bytes,
-					    region_model_context *ctxt)
-{
-  const region *reg = m_mgr->create_region_for_heap_alloc ();
+region_model::get_or_create_region_for_heap_alloc (const svalue *size_in_bytes,
+						   region_model_context *ctxt)
+{
+  /* Determine which regions are referenced in this region_model, so that
+     we can reuse an existing heap_allocated_region if it's not in use on
+     this path.  */
+  auto_sbitmap base_regs_in_use (m_mgr->get_num_regions ());
+  get_referenced_base_regions (base_regs_in_use);
+  const region *reg
+    = m_mgr->get_or_create_region_for_heap_alloc (base_regs_in_use);
   if (compat_types_p (size_in_bytes->get_type (), size_type_node))
     set_dynamic_extents (reg, size_in_bytes, ctxt);
   return reg;
 }
 
+/* Populate OUT_IDS with the set of IDs of those base regions which are
+   reachable in this region_model.  */
+
+void
+region_model::get_referenced_base_regions (auto_sbitmap &out_ids) const
+{
+  reachable_regions reachable_regs (const_cast<region_model *> (this));
+  m_store.for_each_cluster (reachable_regions::init_cluster_cb,
+			    &reachable_regs);
+  /* Get regions for locals that have explicitly bound values.  */
+  for (store::cluster_map_t::iterator iter = m_store.begin ();
+       iter != m_store.end (); ++iter)
+    {
+      const region *base_reg = (*iter).first;
+      if (const region *parent = base_reg->get_parent_region ())
+	if (parent->get_kind () == RK_FRAME)
+	  reachable_regs.add (base_reg, false);
+    }
+
+  bitmap_clear (out_ids);
+  for (auto iter_reg : reachable_regs)
+    bitmap_set_bit (out_ids, iter_reg->get_id ());
+}
+
 /* Return a new region describing a block of memory allocated within the
    current frame.
    Use CTXT to complain about tainted sizes.  */
@@ -7608,7 +7646,7 @@ test_state_merging ()
     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, &ctxt);
+      = model0.get_or_create_region_for_heap_alloc (size_sval, &ctxt);
     const svalue *ptr_sval = mgr.get_ptr_svalue (ptr_type_node, new_reg);
     model0.set_value (model0.get_lvalue (p, &ctxt),
 		      ptr_sval, &ctxt);
@@ -7996,7 +8034,8 @@ test_malloc_constraints ()
 
   const svalue *size_in_bytes
     = mgr.get_or_create_unknown_svalue (size_type_node);
-  const region *reg = model.create_region_for_heap_alloc (size_in_bytes, NULL);
+  const region *reg
+    = model.get_or_create_region_for_heap_alloc (size_in_bytes, NULL);
   const svalue *sval = mgr.get_ptr_svalue (ptr_type_node, reg);
   model.set_value (model.get_lvalue (p, NULL), sval, NULL);
   model.set_value (q, p, NULL);
@@ -8225,7 +8264,8 @@ test_malloc ()
 
   /* "p = malloc (n * 4);".  */
   const svalue *size_sval = model.get_rvalue (n_times_4, &ctxt);
-  const region *reg = model.create_region_for_heap_alloc (size_sval, &ctxt);
+  const region *reg
+    = model.get_or_create_region_for_heap_alloc (size_sval, &ctxt);
   const svalue *ptr = mgr.get_ptr_svalue (int_star, reg);
   model.set_value (model.get_lvalue (p, &ctxt), ptr, &ctxt);
   ASSERT_EQ (model.get_capacity (reg), size_sval);