ownership-eval: Add an ownership_* attribute evaluator WIPwip/pwithnall/ownership

The fledgling ownership-eval checker currently implements the same thing
as defaultEvalCall(), invalidating all non-const regions. It needs to be
modified to take GIR annotations into account, so that parameters are
not marked as invalidated as appropriate. I suspect the regions for
objects will be marked as invalidated, but their pointers will not
escape, for example.

7 files changed, 473 insertions, 1 deletions

diff --git a/Makefile.am b/Makefile.am
index 2222c59..ccf374c 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -32,6 +32,8 @@ clang_plugin_libtartan_la_SOURCES = \
 	clang-plugin/gvariant-checker.h \
 	clang-plugin/nullability-checker.cpp \
 	clang-plugin/nullability-checker.h \
+	clang-plugin/ownership-eval.cpp \
+	clang-plugin/ownership-eval.h \
 	clang-plugin/checker.cpp \
 	clang-plugin/checker.h \
 	clang-plugin/type-manager.cpp \
diff --git a/clang-plugin/ownership-eval.cpp b/clang-plugin/ownership-eval.cpp
new file mode 100644
index 0000000..214d315
--- /dev/null
+++ b/clang-plugin/ownership-eval.cpp
@@ -0,0 +1,310 @@
+/* -*- Mode: C++; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
+/*
+ * Tartan
+ * Copyright © 2014 Collabora Ltd.
+ *
+ * Tartan is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Tartan is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Tartan.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors:
+ *     Philip Withnall <philip.withnall@collabora.co.uk>
+ */
+
+/**
+ * OwnershipEval:
+ *
+ * This is a checker for #GError usage, both with the g_error_*() API, and with
+ * normal C pointer operations on #GErrors. It validates that all #GError
+ * pointers are initialised to %NULL, that valid #GErrors are not overwritten,
+ * and that #GErrors are not double-freed or leaked. It also validates more
+ * mundane things, like whether error codes actually belong in the domain passed
+ * to g_error_new() (for example).
+ *
+ * This is effectively a highly specific memory allocation checker, imposing the
+ * rules about clearing #GError pointers to %NULL which #GError convention
+ * dictates.
+ *
+ * The checker uses full path-dependent analysis, so will catch bugs arising
+ * from #GErrors being handled differently on different control paths, which is
+ * empirically where most #GError bugs arise.
+ *
+ * The checker is implemented using a combination of Clang’s internal symbolic
+ * value model, and a custom ErrorMap using Clang’s program state maps. The
+ * ErrorMap tracks state for each GError* pointer it knows about, using three
+ * states:
+ *  • Clear: error = NULL
+ *  • Set: error ≠ NULL ∧ valid_allocation(error)
+ *  • Freed: error ≠ NULL ∧ ¬valid_allocation(error)
+ *
+ * In the comments below, the following modelling functions are used:
+ *     valid_allocation(error):
+ *         True iff error has been allocated as a GError, but not yet freed.
+ *         Corresponds to the ErrorState.Set state.
+ *     error_codes(domain):
+ *         Returns a set of error codes which are valid for the given domain,
+ *         as defined by the enum associated with that error domain.
+ *
+ * FIXME: Future work could be to implement:
+ *  • Support for user-defined functions which take GError** parameters.
+ *  • Add support for g_error_copy()
+ *  • Add support for g_error_matches()
+ *  • Add support for g_prefix_error()
+ *  • Implement check::DeadSymbols  (for cleaning up internal state)
+ *  • Implement check::PointerEscape  (for leaks)
+ *  • Implement check::ConstPointerEscape  (for leaks)
+ *  • Implement check::PreStmt<ReturnStmt>  (for leaks)
+ *  • Implement check::PostStmt<BlockExpr>  (for leaks)
+ *  • Implement check::Location  (for bad dereferences)
+ *  • Implement eval::Assume
+ *  • Check that error codes match their domains.
+ *  • Set the MemRegion contents more explicitly in _gerror_new() — it would be
+ *    nice to get static analysis on code and domain values.
+ *  • Domain analysis on propagated GErrors: track which error domains each
+ *    function can possibly return, and warn if they’re not all handled by
+ *    callers.
+ *
+ * TODO
+ */
+
+#include <clang/StaticAnalyzer/Core/Checker.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h>
+
+#include "ownership-eval.h"
+#include "type-manager.h"
+#include "debug.h"
+// TODO
+
+namespace tartan {
+
+/* Dispatch call-evaluation events to the different per-function handlers.
+ * Return true iff the call was evaluated. */
+bool
+OwnershipEval::evalCall (const CallExpr *call,
+                         CheckerContext &context) const
+{
+	const FunctionDecl *func_decl = context.getCalleeDecl (call);
+
+	if (func_decl == NULL ||
+	    func_decl->getKind() != Decl::Function ||
+	    !CheckerContext::isCLibraryFunction (func_decl)) {
+		return false;
+	}
+
+	/* Try to find typelib information about the function. */
+	const std::string func_name = func_decl->getNameAsString ();
+	GIBaseInfo *info =
+		this->_gir_manager.get ()->find_function_info (func_name);
+
+	if (info == NULL ||
+	    g_base_info_get_type (info) != GI_INFO_TYPE_FUNCTION) {
+		return false;
+	}
+
+	/* Evaluate the call. */
+	ProgramStateRef new_state = this->_evaluate_gir_call (context, *call,
+	                                                      info);
+
+	if (new_state != NULL) {
+		context.addTransition (new_state);
+	}
+
+	return (new_state != NULL);
+}
+
+static bool
+is_callback_sval (SVal sval, QualType type) {
+	// If the parameter is 0, it's harmless.
+	if (sval.isZeroConstant ()) {
+		return false;
+	}
+
+	// If a parameter is a block or a callback, assume it can modify pointer.
+	if (type->isFunctionPointerType ()) {
+		return true;
+	}
+
+	// Check if a callback is passed inside a struct (for both, struct passed by
+	// reference and by value). Dig just one level into the struct for now.
+	if (type->isAnyPointerType () || type->isReferenceType ()) {
+		type = type->getPointeeType ();
+	}
+
+	if (const RecordType *record_type = type->getAsStructureType ()) {
+		const RecordDecl *record = record_type->getDecl ();
+		for (const auto *i : record->fields ()) {
+			QualType field_type = i->getType ();
+
+			if (field_type->isFunctionPointerType ()) {
+				return true;
+			}
+		}
+	}
+
+	return false;
+}
+
+static bool
+has_callback_args (CheckerContext &context,
+                   const CallExpr &call_expr)
+{
+	unsigned int num_args = call_expr.getNumArgs ();
+	unsigned int idx = 0;
+
+	for (CallExpr::const_arg_iterator i = call_expr.arg_begin (),
+	     e = call_expr.arg_end ();
+	     i != e && idx < num_args; ++i, ++idx) {
+		if (num_args <= idx) {
+			break;
+		}
+
+		SVal arg_sval = context.getSVal (call_expr.getArg (idx));
+
+		if (is_callback_sval (arg_sval, (*i)->getType ())) {
+			return true;
+		}
+	}
+
+	return false;
+}
+
+static bool
+args_may_escape (CheckerContext &context,
+                 const CallExpr &call_expr)
+{
+	return has_callback_args (context, call_expr);
+}
+
+// Try to retrieve the function declaration and find the function parameter
+// types which are pointers/references to a non-pointer const.
+// We will not invalidate the corresponding argument regions.
+// @info may be %NULL.
+static void
+preserve_const_args (llvm::SmallSet<unsigned int, 4> &preserve_args,
+                     const CallExpr &call, GIFunctionInfo *info)
+{
+	unsigned int idx = 0;
+
+	for (CallExpr::const_arg_iterator i = call.arg_begin (),
+	     e = call.arg_end ();
+	     i != e; ++i, ++idx) {
+		QualType type = (*i)->getType ();
+		QualType pointee_type = type->getPointeeType ();
+
+		if (pointee_type != QualType () &&
+		    pointee_type.isConstQualified () &&
+		    !pointee_type->isAnyPointerType ()) {
+			preserve_args.insert (idx);
+		}
+	}
+
+	/* Load the GIR info, iterate through the arguments and mark all
+	 * of them as to be preserved, except those with (transfer !none)
+	 * (direction in|out). */
+	GICallableInfo *callable_info = (GICallableInfo *) info;
+
+	/* GError formal parameters aren’t included in the number of
+	 * callable arguments. */
+	unsigned int k = g_callable_info_get_n_args (callable_info);
+	unsigned int self_params =
+		(g_function_info_get_flags (callable_info) &
+		 GI_FUNCTION_IS_METHOD) ? 1 : 0;
+	unsigned int j;
+
+	/* TODO: unit test this */
+	for (j = self_params; j < k + self_params; j++) {
+		GIArgInfo arg;
+		GITransfer transfer;
+
+		g_callable_info_load_arg (callable_info,
+		                          j - self_params, &arg);
+		transfer = g_arg_info_get_ownership_transfer (&arg);
+
+		if (transfer == GI_TRANSFER_NOTHING) {
+			preserve_args.insert (j);
+		}
+	}
+}
+
+/* TODO */
+ProgramStateRef
+OwnershipEval::_evaluate_gir_call (CheckerContext &context,
+                                   const CallExpr &call_expr,
+                                   GIFunctionInfo *info) const
+{
+	ProgramStateRef state = context.getState ();
+	const FunctionDecl *callee = call_expr.getDirectCallee ();
+	unsigned int count = context.blockCount ();
+
+	/* Invalidate regions. Don’t invalidate anything if the callee is pure
+	 * or const. */
+	if (callee == NULL ||
+	    !(callee->hasAttr<PureAttr> () || callee->hasAttr<ConstAttr> ())) {
+		SmallVector<SVal, 8> values_to_invalidate;
+		RegionAndSymbolInvalidationTraits traits;
+
+		/* Indexes of arguments whose values will be preserved by the
+		 * call. */
+		llvm::SmallSet<unsigned int, 4> preserve_args;
+		if (!args_may_escape (context, call_expr))
+			preserve_const_args (preserve_args, call_expr, info);
+
+		for (unsigned int i = 0, j = call_expr.getNumArgs ();
+		     i != j; i++) {
+			SVal arg_sval = context.getSVal (call_expr.getArg (i));
+
+			// Mark this region for invalidation.  We batch invalidate regions
+			// below for efficiency.
+			const MemRegion *region = arg_sval.getAsRegion ();
+
+			if (preserve_args.count (i) && region != NULL) {
+				traits.setTrait (region->StripCasts (),
+				                 RegionAndSymbolInvalidationTraits::TK_PreserveContents);
+			}
+
+			values_to_invalidate.push_back (arg_sval);
+		}
+
+		// Invalidate designated regions using the batch invalidation API.
+		// NOTE: Even if RegionsToInvalidate is empty, we may still invalidate
+		//  global variables.
+  // Get the call in its initial state. We use this as a template to perform
+  // all the checks.
+  CallEventManager &CEMgr = context.getStateManager().getCallEventManager();
+  CallEventRef<> CallTemplate
+    = CEMgr.getSimpleCall(&call_expr, state, context.getLocationContext());
+
+		state = state->invalidateRegions (values_to_invalidate,
+		                                  &call_expr, count,
+		                                  context.getLocationContext (),
+		                                  /*CausedByPointerEscape*/ true,
+		                                  /*Symbols=*/ NULL, NULL  /* TODO */,
+		                                  &traits);
+	}
+
+	/* Bind a new return value. */
+	if (callee != NULL) {
+		// Conjure a symbol if the return value is unknown.
+		QualType result_type = callee->getReturnType ();
+		SValBuilder &sval_builder = context.getSValBuilder ();
+		SVal sval = sval_builder.conjureSymbolVal (NULL, &call_expr,
+		                                           context.getLocationContext (),
+		                                           result_type, count);
+		state = state->BindExpr (&call_expr,
+		                         context.getLocationContext (), sval);
+	}
+
+	return state;
+}
+
+} /* namespace tartan */
diff --git a/clang-plugin/ownership-eval.h b/clang-plugin/ownership-eval.h
new file mode 100644
index 0000000..76e3689
--- /dev/null
+++ b/clang-plugin/ownership-eval.h
@@ -0,0 +1,61 @@
+/* -*- Mode: C++; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
+/*
+ * Tartan
+ * Copyright © 2014 Collabora Ltd.
+ *
+ * Tartan is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * Tartan is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with Tartan.  If not, see <http://www.gnu.org/licenses/>.
+ *
+ * Authors:
+ *     Philip Withnall <philip.withnall@collabora.co.uk>
+ */
+
+#ifndef TARTAN_OWNERSHIP_EVAL_H
+#define TARTAN_OWNERSHIP_EVAL_H
+
+#include <clang/AST/AST.h>
+#include <clang/StaticAnalyzer/Core/Checker.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h>
+
+#include "checker.h"
+#include "gir-manager.h"
+
+namespace tartan {
+
+using namespace clang;
+using namespace ento;
+
+class OwnershipEval : public ento::Checker<eval::Call>,
+                      public tartan::Checker {
+public:
+	explicit OwnershipEval () : _gir_manager (global_gir_manager) {};
+
+protected:
+	std::shared_ptr<const GirManager> _gir_manager;
+
+private:
+	ProgramStateRef _evaluate_gir_call (CheckerContext &context,
+	                                    const CallExpr &call_expr,
+	                                    GIFunctionInfo *info) const;
+
+public:
+	bool evalCall (const CallExpr *call,
+	               CheckerContext &context) const;
+
+	const std::string get_name () const { return "ownership"; }
+};
+
+} /* namespace tartan */
+
+#endif /* !TARTAN_OWNERSHIP_EVAL_H */
diff --git a/clang-plugin/plugin.cpp b/clang-plugin/plugin.cpp
index ad9acda..81a563c 100644
--- a/clang-plugin/plugin.cpp
+++ b/clang-plugin/plugin.cpp
@@ -37,6 +37,7 @@
 #include "gsignal-checker.h"
 #include "gvariant-checker.h"
 #include "nullability-checker.h"
+#include "ownership-eval.h"
 
 using namespace clang;
 
@@ -355,6 +356,8 @@ extern "C"
 void clang_registerCheckers (ento::CheckerRegistry &registry) {
 	registry.addChecker<GErrorChecker> ("tartan.GErrorChecker",
 	                                    "Check GError API usage");
+	registry.addChecker<OwnershipEval> ("tartan.OwnershipEval",
+	                                    "Evaluate transfers on calls");
 }
 
 extern "C"
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 00c0b4f..13763b5 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -18,6 +18,7 @@ c_tests = \
 	non-glib.c \
 	nonnull.c \
 	gerror-api.c \
+	ownership.c \
 	$(NULL)
 
 templates = \
diff --git a/tests/ownership.c b/tests/ownership.c
new file mode 100644
index 0000000..a185028
--- /dev/null
+++ b/tests/ownership.c
@@ -0,0 +1,91 @@
+/* Template: generic */
+
+/*
+ * warning: Potential memory leak
+ * }
+ * ^
+ */
+{
+	// Sanity check that we have specified
+	// -analyzer-checker=alpha.unix.MallocWithAnnotations
+	malloc (15);
+}
+
+/*
+ * warning: Potential leak of memory pointed to by 'str'
+ * }
+ * ^
+ */
+{
+	GString *str = g_string_new ("");
+	printf ("%p\n", str);
+}
+
+/*
+ * warning: Potential leak of memory pointed to by 'str'
+ * }
+ * ^
+ */
+{
+	GString *str = g_string_new ("");
+	printf ("%p\n", str);
+	str = NULL;
+}
+
+/*
+ * No error
+ */
+{
+	GString *str = g_string_new ("");
+	printf ("%p\n", str);
+	g_string_free (str, TRUE);
+}
+
+/*
+ * warning: Potential leak of memory pointed to by 'str'
+ * }
+ * ^
+ */
+{
+	GString *str = g_string_new ("");
+
+	// Something path-dependent.
+	if (rand ()) {
+		printf ("%p\n", str);
+	} else {
+		g_string_free (str, TRUE);
+	}
+}
+
+/*
+ * warning: Potential leak of memory pointed to by 'obj'
+ * }
+ * ^
+ */
+{
+	GMountOperation *obj = g_mount_operation_new ();
+	printf ("%p\n", obj);
+}
+
+/*
+ * No error
+ */
+{
+	GMountOperation *obj = g_mount_operation_new ();
+	printf ("%p\n", obj);
+	g_object_unref (obj);
+}
+
+/*
+ * No error
+ */
+{
+	GMountOperation *obj = g_mount_operation_new ();
+	printf ("%p\n", obj);
+	// FIXME: Unfortunately, since arbitrary functions aren’t modelled and
+	// there’s no way to inject a non-ownership attribute into the
+	// MallocChecker, opaque functions cause pointers to escape.
+	// Clang needs a better representation of transfer than the ownership
+	// attributes.
+	g_mount_operation_set_username (obj, "blah");
+}
diff --git a/tests/wrapper-compiler-errors b/tests/wrapper-compiler-errors
index 264618c..a04675a 100755
--- a/tests/wrapper-compiler-errors
+++ b/tests/wrapper-compiler-errors
@@ -90,10 +90,14 @@ while [[ -f `printf "${temp_dir}/${input_filename}_%02d.c" ${num}` ]]; do
 	# e.g. Set
 	# TARTAN_TEST_OPTIONS="-analyzer-checker=debug.ViewExplodedGraph" to
 	# debug the ExplodedGraph
+	#
+	# The MallocWithAnnotations checker is needed for ownership.c.
 	TARTAN_PLUGIN=$tartan_plugin \
 	TARTAN_OPTIONS=--quiet \
 	$tartan \
-		-cc1 -analyze -std=c89 -Wno-visibility $TARTAN_TEST_OPTIONS \
+		-cc1 -analyze -std=c89 -Wno-visibility \
+		-analyzer-checker=alpha.unix.MallocWithAnnotations \
+		$TARTAN_TEST_OPTIONS \
 		`pkg-config --cflags glib-2.0` \
 		$system_includes \
 		$section_filename > $actual_error_filename 2>&1