analyzer: fix false positive on realloc [PR99193]

PR analyzer/99193 describes various false positives from
-Wanalyzer-mismatching-deallocation on realloc(3) calls
of the form:

    |   31 |   void *p = malloc (1024);
    |      |             ^~~~~~~~~~~~~
    |      |             |
    |      |             (1) allocated here (expects deallocation with ‘free’)
    |   32 |   void *q = realloc (p, 4096);
    |      |             ~~~~~~~~~~~~~~~~~
    |      |             |
    |      |             (2) deallocated with ‘realloc’ here; allocation at (1) expects deallocation with ‘free’
    |

The underlying issue is that the analyzer has no knowledge of
realloc(3), and realloc has awkward semantics.

Unfortunately, the analyzer is currently structured so that each call
statement can only have at most one successor state; there is no
way to "bifurcate" the state, or have N-way splits into multiple
outcomes.  The existing "on_stmt" code works on a copy of the next
state, updating it in place, rather than copying it and making any
necessary changes.  I did this as an optimization to avoid unnecessary
copying of state objects, but it makes it hard to support multiple
outcomes.  (ideally our state objects would be immutable and thus
support trivial copying, alternatively, C++11 move semantics may
help here)

I attempted a few approaches to implementing bifurcation within the
existing state-update framework, but they were messy and thus likely
buggy; a proper implementation would rework state-updating to
generate copies, but this would be a major change, and seems too
late for GCC 11.

As a workaround, this patch implements enough of realloc(3) to
suppress the false positives.

This fixes the false positives in PR analyzer/99193.
I've filed PR analyzer/99260 to track "properly" implementing realloc(3).

gcc/analyzer/ChangeLog:
	PR analyzer/99193
	* region-model-impl-calls.cc (region_model::impl_call_realloc): New.
	* region-model.cc (region_model::on_call_pre): Call it.
	* region-model.h (region_model::impl_call_realloc): New decl.
	* sm-malloc.cc (enum wording): Add WORDING_REALLOCATED.
	(malloc_state_machine::m_realloc): New field.
	(use_after_free::describe_state_change): Add case for
	WORDING_REALLOCATED.
	(use_after_free::describe_final_event): Likewise.
	(malloc_state_machine::malloc_state_machine): Initialize
	m_realloc.
	(malloc_state_machine::on_stmt): Handle realloc by calling...
	(malloc_state_machine::on_realloc_call): New.

gcc/testsuite/ChangeLog:
	PR analyzer/99193
	* gcc.dg/analyzer/pr99193-1.c: New test.
	* gcc.dg/analyzer/pr99193-2.c: New test.
	* gcc.dg/analyzer/pr99193-3.c: New test.
	* gcc.dg/analyzer/realloc-1.c: New test.

8 files changed, 324 insertions, 2 deletions

diff --git a/gcc/analyzer/region-model-impl-calls.cc b/gcc/analyzer/region-model-impl-calls.cc
index 72404a5..f83c12b 100644
--- a/gcc/analyzer/region-model-impl-calls.cc
+++ b/gcc/analyzer/region-model-impl-calls.cc
@@ -428,6 +428,17 @@ region_model::impl_call_operator_delete (const call_details &cd)
   return false;
 }
 
+/* Handle the on_call_pre part of "realloc".  */
+
+void
+region_model::impl_call_realloc (const call_details &)
+{
+  /* Currently we don't support bifurcating state, so there's no good
+     way to implement realloc(3).
+     For now, malloc_state_machine::on_realloc_call has a minimal
+     implementation to suppress false positives.  */
+}
+
 /* Handle the on_call_pre part of "strcpy" and "__builtin_strcpy_chk".  */
 
 void
diff --git a/gcc/analyzer/region-model.cc b/gcc/analyzer/region-model.cc
index 2053f8f..96ed549 100644
--- a/gcc/analyzer/region-model.cc
+++ b/gcc/analyzer/region-model.cc
@@ -791,6 +791,9 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt,
 	    impl_call_memset (cd);
 	    return false;
 	    break;
+	  case BUILT_IN_REALLOC:
+	    impl_call_realloc (cd);
+	    return false;
 	  case BUILT_IN_STRCPY:
 	  case BUILT_IN_STRCPY_CHK:
 	    impl_call_strcpy (cd);
@@ -840,6 +843,11 @@ region_model::on_call_pre (const gcall *call, region_model_context *ctxt,
 	return impl_call_calloc (cd);
       else if (is_named_call_p (callee_fndecl, "alloca", call, 1))
 	return impl_call_alloca (cd);
+      else if (is_named_call_p (callee_fndecl, "realloc", call, 2))
+	{
+	  impl_call_realloc (cd);
+	  return false;
+	}
       else if (is_named_call_p (callee_fndecl, "error"))
 	{
 	  if (impl_call_error (cd, 3, out_terminate_path))
diff --git a/gcc/analyzer/region-model.h b/gcc/analyzer/region-model.h
index 7768394..54977f9 100644
--- a/gcc/analyzer/region-model.h
+++ b/gcc/analyzer/region-model.h
@@ -464,6 +464,7 @@ class region_model
   bool impl_call_malloc (const call_details &cd);
   void impl_call_memcpy (const call_details &cd);
   bool impl_call_memset (const call_details &cd);
+  void impl_call_realloc (const call_details &cd);
   void impl_call_strcpy (const call_details &cd);
   bool impl_call_strlen (const call_details &cd);
   bool impl_call_operator_new (const call_details &cd);
diff --git a/gcc/analyzer/sm-malloc.cc b/gcc/analyzer/sm-malloc.cc
index d7c76e3..ef250c8 100644
--- a/gcc/analyzer/sm-malloc.cc
+++ b/gcc/analyzer/sm-malloc.cc
@@ -142,7 +142,8 @@ enum wording
 {
   WORDING_FREED,
   WORDING_DELETED,
-  WORDING_DEALLOCATED
+  WORDING_DEALLOCATED,
+  WORDING_REALLOCATED
 };
 
 /* Base class representing a deallocation function,
@@ -387,6 +388,8 @@ public:
   standard_deallocator_set m_scalar_delete;
   standard_deallocator_set m_vector_delete;
 
+  standard_deallocator m_realloc;
+
   /* States that are independent of api.  */
 
   /* State for a pointer that's known to be NULL.  */
@@ -417,6 +420,9 @@ private:
 			    const gcall *call,
 			    const deallocator *d,
 			    unsigned argno) const;
+  void on_realloc_call (sm_context *sm_ctxt,
+			const supernode *node,
+			const gcall *call) const;
   void on_zero_assignment (sm_context *sm_ctxt,
 			   const gimple *stmt,
 			   tree lhs) const;
@@ -1151,6 +1157,7 @@ public:
 	switch (m_deallocator->m_wording)
 	  {
 	  default:
+	  case WORDING_REALLOCATED:
 	    gcc_unreachable ();
 	  case WORDING_FREED:
 	    return label_text::borrow ("freed here");
@@ -1170,6 +1177,7 @@ public:
       switch (m_deallocator->m_wording)
 	{
 	default:
+	case WORDING_REALLOCATED:
 	  gcc_unreachable ();
 	case WORDING_FREED:
 	  return ev.formatted_print ("use after %<%s%> of %qE; freed at %@",
@@ -1361,7 +1369,8 @@ malloc_state_machine::malloc_state_machine (logger *logger)
 : state_machine ("malloc", logger),
   m_free (this, "free", WORDING_FREED),
   m_scalar_delete (this, "delete", WORDING_DELETED),
-  m_vector_delete (this, "delete[]", WORDING_DELETED)
+  m_vector_delete (this, "delete[]", WORDING_DELETED),
+  m_realloc (this, "realloc", WORDING_REALLOCATED)
 {
   gcc_assert (m_start->get_id () == 0);
   m_null = add_state ("null", RS_FREED, NULL, NULL);
@@ -1553,6 +1562,13 @@ malloc_state_machine::on_stmt (sm_context *sm_ctxt,
 	    return true;
 	  }
 
+	if (is_named_call_p (callee_fndecl, "realloc", call, 2)
+	    || is_named_call_p (callee_fndecl, "__builtin_realloc", call, 2))
+	  {
+	    on_realloc_call (sm_ctxt, node, call);
+	    return true;
+	  }
+
 	/* Cast away const-ness for cache-like operations.  */
 	malloc_state_machine *mutable_this
 	  = const_cast <malloc_state_machine *> (this);
@@ -1764,6 +1780,56 @@ 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.
+
+   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.  */
+
+void
+malloc_state_machine::on_realloc_call (sm_context *sm_ctxt,
+				       const supernode *node ATTRIBUTE_UNUSED,
+				       const gcall *call) const
+{
+  tree ptr = gimple_call_arg (call, 0);
+  tree diag_ptr = sm_ctxt->get_diagnostic_tree (ptr);
+
+  state_t state = sm_ctxt->get_state (call, ptr);
+
+  /* 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)
+	{
+	  /* Wrong allocator.  */
+	  pending_diagnostic *pd
+	    = new mismatching_deallocation (*this, diag_ptr,
+					    astate->m_deallocators,
+					    &m_realloc);
+	  sm_ctxt->warn (node, call, ptr, pd);
+	}
+    }
+
+  /* Transition ptr to "stop" state.  */
+  sm_ctxt->set_next_state (call, ptr, m_stop);
+}
+
 /* Implementation of state_machine::on_phi vfunc for malloc_state_machine.  */
 
 void
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c b/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c
new file mode 100644
index 0000000..c6179e9
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr99193-1.c
@@ -0,0 +1,65 @@
+/* Verify absence of false positive from -Wanalyzer-mismatching-deallocation
+   on realloc(3).
+   Based on https://github.com/libguestfs/libguestfs/blob/f19fd566f6387ce7e4d82409528c9dde374d25e0/daemon/command.c#L115
+   which is GPLv2 or later.  */
+
+typedef __SIZE_TYPE__ size_t;
+typedef __builtin_va_list va_list;
+
+#define NULL ((void *)0)
+
+extern void *malloc (size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__malloc__))
+  __attribute__ ((__alloc_size__ (1)));
+extern void perror (const char *__s);
+extern void *realloc (void *__ptr, size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__warn_unused_result__))
+  __attribute__ ((__alloc_size__ (2)));
+
+extern void guestfs_int_cleanup_free (void *ptr);
+extern int commandrvf (char **stdoutput, char **stderror, unsigned flags,
+                       char const* const *argv);
+#define CLEANUP_FREE __attribute__((cleanup(guestfs_int_cleanup_free))) 
+
+int
+commandrf (char **stdoutput, char **stderror, unsigned flags,
+           const char *name, ...)
+{
+  va_list args;
+  CLEANUP_FREE const char **argv = NULL;
+  char *s;
+  int i, r;
+
+  /* Collect the command line arguments into an array. */
+  i = 2;
+  argv = malloc (sizeof (char *) * i);
+
+ if (argv == NULL) {
+    perror ("malloc");
+    return -1;
+  }
+  argv[0] = (char *) name;
+  argv[1] = NULL;
+
+  __builtin_va_start (args, name);
+
+  while ((s = __builtin_va_arg (args, char *)) != NULL) {
+    const char **p = realloc (argv, sizeof (char *) * (++i)); /* { dg-bogus "'free'" } */
+    if (p == NULL) {
+      perror ("realloc");
+      __builtin_va_end (args);
+      return -1;
+    }
+    argv = p;
+    argv[i-2] = s;
+    argv[i-1] = NULL;
+  }
+
+  __builtin_va_end (args);
+
+  r = commandrvf (stdoutput, stderror, flags, argv);
+
+  return r;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr99193-2.c b/gcc/testsuite/gcc.dg/analyzer/pr99193-2.c
new file mode 100644
index 0000000..40e6181
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr99193-2.c
@@ -0,0 +1,68 @@
+/* Verify absence of false positive from -Wanalyzer-mismatching-deallocation
+   on realloc(3).
+   Based on https://github.com/libguestfs/libguestfs/blob/f19fd566f6387ce7e4d82409528c9dde374d25e0/df/main.c#L404
+   which is GPLv2 or later.  */
+
+typedef __SIZE_TYPE__ size_t;
+typedef __builtin_va_list va_list;
+
+#define NULL ((void *)0)
+
+extern void free (void *);
+extern void *realloc (void *__ptr, size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__warn_unused_result__))
+  __attribute__ ((__alloc_size__ (2)));
+char *strdup (const char *)
+  __attribute__((malloc (free)));
+
+extern void error (int __status, int __errnum, const char *__format, ...)
+     __attribute__ ((__format__ (__printf__, 3, 4)));
+
+extern int errno;
+
+struct drv
+{
+  struct drv *next;
+};
+
+#define EXIT_FAILURE 1
+
+static char *
+single_drive_display_name (struct drv *)
+{
+  char *result = strdup ("placeholder");
+  if (!result)
+    __builtin_abort ();
+  return result;
+}
+
+char *
+make_display_name (struct drv *drvs)
+{
+  char *ret;
+
+  if (drvs->next == NULL)
+    ret = single_drive_display_name (drvs);
+  else {
+    size_t pluses = 0;
+    size_t i, len;
+
+    while (drvs->next != NULL) {
+      drvs = drvs->next;
+      pluses++;
+    }
+
+    ret = single_drive_display_name (drvs);
+    len = __builtin_strlen (ret);
+
+    ret = realloc (ret, len + pluses + 1); /* { dg-bogus "'free'" } */
+    if (ret == NULL)
+      error (EXIT_FAILURE, errno, "realloc");
+    for (i = len; i < len + pluses; ++i)
+      ret[i] = '+';
+    ret[i] = '\0';
+  }
+
+  return ret;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c b/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c
new file mode 100644
index 0000000..3e7ffd6
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/pr99193-3.c
@@ -0,0 +1,48 @@
+/* Verify absence of false positive from -Wanalyzer-mismatching-deallocation
+   on realloc(3).
+   Based on https://github.com/libguestfs/libguestfs/blob/f19fd566f6387ce7e4d82409528c9dde374d25e0/daemon/debug.c#L115
+   which is GPLv2 or later.  */
+
+typedef __SIZE_TYPE__ size_t;
+typedef __builtin_va_list va_list;
+
+#define NULL ((void *)0)
+
+extern void free (void *);
+extern void *realloc (void *__ptr, size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__warn_unused_result__))
+  __attribute__ ((__alloc_size__ (2)));
+extern char *strdup (const char *)
+  __attribute__((malloc (free)));
+extern char *strcat (char *__restrict __dest, const char *__restrict __src)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__nonnull__ (1, 2)));
+
+static char *
+debug_help (const char **cmds, size_t argc, char *const *const argv)
+{
+  size_t len, i;
+  char *r, *p;
+
+  r = strdup ("Commands supported:");
+  if (!r) {
+    return NULL;
+  }
+
+  len = __builtin_strlen (r);
+  for (i = 0; cmds[i] != NULL; ++i) {
+    len += __builtin_strlen (cmds[i]) + 1;
+    p = realloc (r, len + 1); /* { dg-bogus "'free'" } */
+    if (p == NULL) {
+      free (r);
+      return NULL;
+    }
+    r = p;
+
+    strcat (r, " ");
+    strcat (r, cmds[i]);
+  }
+
+  return r;
+}
diff --git a/gcc/testsuite/gcc.dg/analyzer/realloc-1.c b/gcc/testsuite/gcc.dg/analyzer/realloc-1.c
new file mode 100644
index 0000000..a6c6bfc
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/analyzer/realloc-1.c
@@ -0,0 +1,55 @@
+typedef __SIZE_TYPE__ size_t;
+
+#define NULL ((void *)0)
+
+extern void *malloc (size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__malloc__))
+  __attribute__ ((__alloc_size__ (1)));
+extern void *realloc (void *__ptr, size_t __size)
+  __attribute__ ((__nothrow__ , __leaf__))
+  __attribute__ ((__warn_unused_result__))
+  __attribute__ ((__alloc_size__ (2)));
+extern void free (void *__ptr)
+  __attribute__ ((__nothrow__ , __leaf__));
+
+void *test_1 (void *ptr)
+{
+  return realloc (ptr, 1024);
+}
+
+void *test_2 (void *ptr)
+{
+  void *p = malloc (1024);
+  p = realloc (p, 4096);
+  /* TODO: should warn about the leak when the above call fails (PR analyzer/99260).  */
+  free (p);
+}
+
+void *test_3 (void *ptr)
+{
+  void *p = malloc (1024);
+  void *q = realloc (p, 4096);
+  if (q)
+    free (q);
+  else
+    free (p);
+}
+
+void *test_4 (void)
+{
+  return realloc (NULL, 1024);
+}
+
+int *test_5 (int *p)
+{
+  *p = 42;
+  int *q = realloc (p, sizeof(int) * 4);
+  *q = 43; /* { dg-warning "possibly-NULL 'q'" "PR analyzer/99260" { xfail *-*-* } } */
+  return q;
+}
+
+void test_6 (size_t sz)
+{
+  void *p = realloc (NULL, sz);
+} /* { dg-warning "leak of 'p'" } */