[gcc/devel/c++-modules] analyzer: fix leak false positive/widening on pointer iteration [PR94858]

[gcc/devel/c++-modules] analyzer: fix leak false positive/widening on pointer iteration [PR94858]

[Nathan Sidwell]

https://gcc.gnu.org/g:2fc201382d3498778934f1262b57acd20f76f300

commit 2fc201382d3498778934f1262b57acd20f76f300
Author: David Malcolm <dmalcolm@redhat.com>
Date:   Fri Aug 21 18:34:16 2020 -0400

    analyzer: fix leak false positive/widening on pointer iteration [PR94858]
    
    PR analyzer/94858 reports a false diagnostic from
    -Wanalyzer-malloc-leak, where the allocated pointer is pointed to by a
    field of a struct, and a loop writes to a buffer, writing through an
    iterating pointer value.
    
    There were several underlying problems, relating to clobbering of the
    struct holding the malloc-ed pointer; in each case the analyzer was
    conservatively assuming that a write could affect this region,
    clobbering it to "unknown", and this was detected as a leak.
    
    The initial write within the loop dereferences the initial value of
    a field, and the analyzer was assuming that that pointer could
    point to the result of the malloc call.  The patch extends
    store::eval_alias_1 so that it "knows" that the initial value of a
    pointer at the beginning of a path can't point to a region that was
    allocated on the heap after the beginning of the path.
    
    On fixing that, the next issue is that within the loop the iterated
    pointer value becomes "unknown", and hence *ptr becomes a write to a
    symbolic region, and thus might clobber the struct (which it can't).
    This patch adds enough logic to svalue::can_merge_p to merge the
    iterating pointer value so that at the 2nd iteration analyzing
    the loop it becomes a widening_svalue from the initial svalue, so
    that this becomes a fixed point of the analysis, and is not an
    unknown_svalue.  The patch further extends store::eval_alias_1 so that
    it "knows" that this widening_svalue can only point to the same base
    region as the initial value did; in particular, symbolic writes through
    this pointer can only clobber that base region, not the struct holding
    the malloc-ed pointer.
    
    gcc/analyzer/ChangeLog:
            PR analyzer/94858
            * region-model-manager.cc
            (region_model_manager::get_or_create_widening_svalue): Assert that
            neither of the inputs are themselves widenings.
            * store.cc (store::eval_alias_1): The initial value of a pointer
            can't point to a region that was allocated on the heap after the
            beginning of the path.  A widened pointer value can't alias anything
            that the initial pointer value can't alias.
            * svalue.cc (svalue::can_merge_p): Merge BINOP (X, OP, CST) with X
            to a widening svalue.  Merge
            BINOP(WIDENING(BASE, BINOP(BASE, X)), X) and BINOP(BASE, X) to
            to the LHS of the first BINOP.
    
    gcc/testsuite/ChangeLog:
            PR analyzer/94858
            * gcc.dg/analyzer/loop-start-up-to-end-by-1.c: Remove xfail.
            * gcc.dg/analyzer/pr94858-1.c: New test.
            * gcc.dg/analyzer/pr94858-2.c: New test.
            * gcc.dg/analyzer/torture/loop-inc-ptr-2.c: Update expected number
            of enodes.
            * gcc.dg/analyzer/torture/loop-inc-ptr-3.c: Likewise.

Diff:
---
 gcc/analyzer/region-model-manager.cc               |  2 ++
 gcc/analyzer/store.cc                              | 29 +++++++++++++++
 gcc/analyzer/svalue.cc                             | 23 ++++++++++++
 .../gcc.dg/analyzer/loop-start-up-to-end-by-1.c    |  2 --
 gcc/testsuite/gcc.dg/analyzer/pr94858-1.c          | 42 ++++++++++++++++++++++
 gcc/testsuite/gcc.dg/analyzer/pr94858-2.c          | 25 +++++++++++++
 .../gcc.dg/analyzer/torture/loop-inc-ptr-2.c       |  2 +-
 .../gcc.dg/analyzer/torture/loop-inc-ptr-3.c       |  2 +-
 8 files changed, 123 insertions(+), 4 deletions(-)

diff --git a/gcc/analyzer/region-model-manager.cc b/gcc/analyzer/region-model-manager.cc
index ce949322db7..9bfb0812998 100644
--- a/gcc/analyzer/region-model-manager.cc
+++ b/gcc/analyzer/region-model-manager.cc
@@ -651,6 +651,8 @@ region_model_manager::get_or_create_widening_svalue (tree type,
 						     const svalue *base_sval,
 						     const svalue *iter_sval)
 {
+  gcc_assert (base_sval->get_kind () != SK_WIDENING);
+  gcc_assert (iter_sval->get_kind () != SK_WIDENING);
   widening_svalue::key_t key (type, point, base_sval, iter_sval);
   if (widening_svalue **slot = m_widening_values_map.get (key))
     return *slot;
diff --git a/gcc/analyzer/store.cc b/gcc/analyzer/store.cc
index 8439366f0b5..14f7c00bde6 100644
--- a/gcc/analyzer/store.cc
+++ b/gcc/analyzer/store.cc
@@ -1606,6 +1606,35 @@ store::eval_alias_1 (const region *base_reg_a,
 	      /* The initial value of a pointer can't point to a local.  */
 	      return tristate::TS_FALSE;
 	    }
+      if (sval_a->get_kind () == SK_INITIAL
+	  && base_reg_b->get_kind () == RK_HEAP_ALLOCATED)
+	{
+	  /* The initial value of a pointer can't point to a
+	     region that was allocated on the heap after the beginning of the
+	     path.  */
+	  return tristate::TS_FALSE;
+	}
+      if (const widening_svalue *widening_sval_a
+	  = sval_a->dyn_cast_widening_svalue ())
+	{
+	  const svalue *base = widening_sval_a->get_base_svalue ();
+	  if (const region_svalue *region_sval
+		= base->dyn_cast_region_svalue ())
+	    {
+	      const region *pointee = region_sval->get_pointee ();
+	      /* If we have sval_a is WIDENING(&REGION, OP), and
+		 B can't alias REGION, then B can't alias A either.
+		 For example, A might arise from
+		   for (ptr = &REGION; ...; ptr++)
+		 where sval_a is ptr in the 2nd iteration of the loop.
+		 We want to ensure that "*ptr" can only clobber things
+		 within REGION's base region.  */
+	      tristate ts = eval_alias (pointee->get_base_region (),
+					base_reg_b);
+	      if (ts.is_false ())
+		return tristate::TS_FALSE;
+	    }
+	}
     }
   return tristate::TS_UNKNOWN;
 }
diff --git a/gcc/analyzer/svalue.cc b/gcc/analyzer/svalue.cc
index 99b5507a43c..a1c6241a0ba 100644
--- a/gcc/analyzer/svalue.cc
+++ b/gcc/analyzer/svalue.cc
@@ -196,6 +196,18 @@ svalue::can_merge_p (const svalue *other,
 						 other, this);
     }
 
+  /* Merger of:
+	 this: BINOP (X, OP, CST)
+	other: X, where X is non-widening
+	   to: WIDENING (other, this).  */
+  if (const binop_svalue *binop_sval = dyn_cast_binop_svalue ())
+    if (binop_sval->get_arg0 () == other
+	&& binop_sval->get_arg1 ()->get_kind () == SK_CONSTANT
+	&& other->get_kind () != SK_WIDENING)
+      return mgr->get_or_create_widening_svalue (other->get_type (),
+						 merger->m_point,
+						 other, this);
+
   /* Merge: (Widen(existing_val, V), existing_val) -> Widen (existing_val, V)
      and thus get a fixed point.  */
   if (const widening_svalue *widen_sval = dyn_cast_widening_svalue ())
@@ -231,6 +243,17 @@ svalue::can_merge_p (const svalue *other,
 	  {
 	    return widen_arg0;
 	  }
+
+	/* Merger of:
+	    this: BINOP(WIDENING(BASE, BINOP(BASE, X)), X)
+	   other: BINOP(BASE, X)
+	      to: WIDENING(BASE, BINOP(BASE, X)).  */
+	if (widen_arg0->get_iter_svalue () == other)
+	  if (const binop_svalue *other_binop_sval
+		= other->dyn_cast_binop_svalue ())
+	    if (other_binop_sval->get_arg0 () == widen_arg0->get_base_svalue ()
+		&& other_binop_sval->get_arg1 () == binop_sval->get_arg1 ())
+	      return widen_arg0;
       }
 
   return mgr->get_or_create_unknown_svalue (get_type ());
diff --git a/gcc/testsuite/gcc.dg/analyzer/loop-start-up-to-end-by-1.c b/gcc/testsuite/gcc.dg/analyzer/loop-start-up-to-end-by-1.c
index ca6a862092c..5e21890bfea 100644
--- a/gcc/testsuite/gcc.dg/analyzer/loop-start-up-to-end-by-1.c
+++ b/gcc/testsuite/gcc.dg/analyzer/loop-start-up-to-end-by-1.c
@@ -8,8 +8,6 @@ void test(int start, int end)
 
   for (i = start; i < end; i++) {
       __analyzer_eval (i < end); /* { dg-warning "TRUE" "true" } */
-      /* { dg-bogus "UNKNOWN" "unknown" { xfail *-*-* } .-1 } */
-      /* TODO(xfail^^^): should report TRUE twice. */
 
       __analyzer_eval (i == start); /* { dg-warning "TRUE" "1st" } */
       /* { dg-warning "FALSE" "2nd" { xfail *-*-* } .-1 } */
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c b/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c
new file mode 100644
index 00000000000..f7be1c617da
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr94858-1.c
@@ -0,0 +1,42 @@
+#include <stdlib.h>
+
+typedef short hashNx;
+
+typedef struct hashSt {
+  hashNx *hs_index;
+  int hs_used;
+  int hs_slots;
+} hashSt;
+
+void hashEmpty(hashSt *td);
+
+int hashAlloc(hashSt *td, int slots) {
+  hashNx *index;
+
+  if (slots > td->hs_slots) {
+    if (td->hs_index != NULL)
+      index = realloc(td->hs_index, (size_t)slots * sizeof(hashNx));
+    else
+      index = malloc((size_t)slots * sizeof(hashNx));
+
+    if (index == NULL)
+      return 0;
+
+    td->hs_index = index;
+    td->hs_slots = slots;
+  }
+
+  hashEmpty(td);
+
+  return 1;
+}
+
+void hashEmpty(hashSt *td) {
+  hashNx *index;
+  int slots;
+
+  for (slots = td->hs_slots, index = td->hs_index; --slots >= 0;)
+    *index++ = -1;
+
+  td->hs_used = 0;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr94858-2.c b/gcc/testsuite/gcc.dg/analyzer/pr94858-2.c
new file mode 100644
index 00000000000..874fe8b2c75
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr94858-2.c
@@ -0,0 +1,25 @@
+#include <stdlib.h>
+
+typedef short hashNx;
+
+typedef struct hashSt {
+  hashNx *hs_index;
+  int hs_used;
+  int hs_slots;
+} hashSt;
+
+int test (hashSt *td, int slots)
+{
+  hashNx *index;
+
+  index = malloc((size_t)slots * sizeof(hashNx));
+  if (index == NULL)
+    return 0;
+  td->hs_index = index;
+  td->hs_slots = slots;
+
+  for (slots = td->hs_slots, index = td->hs_index; --slots >= 0;)
+    *index++ = -1;
+
+  return 1;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-2.c b/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-2.c
index 95d8c53ade1..d5b10ab2572 100644
--- a/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-2.c
+++ b/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-2.c
@@ -9,7 +9,7 @@ void test (int *p, int val, int count)
 
   while (n--)
     {
-      __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */
+      __analyzer_dump_exploded_nodes (0); /* { dg-warning "3 processed enodes" } */
       *p++ = val;
     }
 
diff --git a/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-3.c b/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-3.c
index 1d3576d9308..c3a1e110e16 100644
--- a/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-3.c
+++ b/gcc/testsuite/gcc.dg/analyzer/torture/loop-inc-ptr-3.c
@@ -9,7 +9,7 @@ void test (int *p, int a, int b, int count)
 
   while (n--)
     {
-      __analyzer_dump_exploded_nodes (0); /* { dg-warning "2 processed enode" } */
+      __analyzer_dump_exploded_nodes (0); /* { dg-warning "2|3 processed enodes" } */
       *p++ = a;
       *p++ = b;
     }