clang-plugin: UNFINISHED work to add reference count checkingwip/pwithnall/refcounting

9 files changed, 499 insertions, 1 deletions

diff --git a/Makefile.am b/Makefile.am
index 18987ff..1675ec4 100644
--- a/Makefile.am
+++ b/Makefile.am
@@ -34,6 +34,8 @@ clang_plugin_libtartan_la_SOURCES = \
 	clang-plugin/checker.h \
 	clang-plugin/type-manager.cpp \
 	clang-plugin/type-manager.h \
+	clang-plugin/refcount-checker.cpp \
+	clang-plugin/refcount-checker.h \
 	$(NULL)
 
 clang_plugin_libtartan_la_CPPFLAGS = \
diff --git a/clang-plugin/plugin.cpp b/clang-plugin/plugin.cpp
index 30d2288..aee536d 100644
--- a/clang-plugin/plugin.cpp
+++ b/clang-plugin/plugin.cpp
@@ -21,6 +21,7 @@
  */
 
 #include <clang/Frontend/FrontendPluginRegistry.h>
+#include <clang/StaticAnalyzer/Core/CheckerRegistry.h>
 #include <clang/AST/AST.h>
 #include <clang/AST/ASTConsumer.h>
 #include <clang/Frontend/CompilerInstance.h>
@@ -33,6 +34,7 @@
 #include "gsignal-checker.h"
 #include "gvariant-checker.h"
 #include "nullability-checker.h"
+#include "refcount-checker.h"
 
 using namespace clang;
 
@@ -259,8 +261,17 @@ protected:
 };
 
 
-/* Register the plugin with LLVM. */
+/* Register the AST checkers with LLVM. */
 static FrontendPluginRegistry::Add<TartanAction>
 X("tartan", "add attributes and warnings using GLib-specific metadata");
 
+/* Register the path-dependent plugins with Clang. */
+extern "C"
+void clang_registerCheckers (ento::CheckerRegistry &registry) {
+	registry.addChecker<RefcountChecker> ("tartan.RefcountChecker", "TODO");
+}
+
+extern "C"
+const char clang_analyzerAPIVersionString[] = CLANG_ANALYZER_API_VERSION_STRING;
+
 } /* namespace tartan */
diff --git a/clang-plugin/refcount-checker.cpp b/clang-plugin/refcount-checker.cpp
new file mode 100644
index 0000000..989a372
--- /dev/null
+++ b/clang-plugin/refcount-checker.cpp
@@ -0,0 +1,320 @@
+/* -*- Mode: C++; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
+/*
+ * Tartan
+ * Copyright © 2014 Philip Withnall
+ *
+ * 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@tecnocode.co.uk>
+ */
+
+/**
+ * RefcountChecker:
+ *
+ * TODO
+ */
+
+#include <clang/StaticAnalyzer/Core/BugReporter/BugType.h>
+#include <clang/StaticAnalyzer/Core/Checker.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CallEvent.h>
+#include <clang/StaticAnalyzer/Core/PathSensitive/CheckerContext.h>
+
+#include "refcount-checker.h"
+
+namespace tartan {
+
+using namespace clang;
+
+/* TODO: docs */
+struct RefcountState {
+private:
+	int _delta;
+	bool _is_returned;
+
+	RefcountState (int delta, bool is_returned) :
+		_delta (delta), _is_returned (is_returned) {}
+
+public:
+	bool is_valid () const { return this->_delta >= 0; }
+	bool is_dead () const { return this->_delta == 0; }
+
+	static RefcountState constructed () {
+		return RefcountState (1, false);
+	}
+
+	static RefcountState returned (const RefcountState *old) {
+		if (old == NULL) {
+			return RefcountState (0, true);
+		}
+
+		assert (!old->_is_returned);
+		return RefcountState (old->_delta, true);
+	}
+
+	static RefcountState reffed (const RefcountState *old) {
+		if (old == NULL) {
+			return RefcountState (1, false);
+		}
+
+		assert (!old->_is_returned);
+		return RefcountState (old->_delta + 1, false);
+	}
+
+	static RefcountState unreffed (const RefcountState *old) {
+		if (old == NULL) {
+			return RefcountState (-1, false);
+		}
+
+		assert (!old->_is_returned);
+		return RefcountState (old->_delta - 1, false);
+	}
+
+	bool operator == (const RefcountState &other) const {
+		return (other._delta == this->_delta &&
+		        other._is_returned == this->_is_returned);
+	}
+
+	/* TODO: what's this for? */
+	void Profile (llvm::FoldingSetNodeID &id) const {
+		id.AddInteger (this->_delta);
+	}
+};
+
+} /* namespace tartan */
+
+/* Track objects and their refcounts in a map stored on the ProgramState.
+ * The namespacing is necessary to be able to specialise a Clang template. */
+REGISTER_MAP_WITH_PROGRAMSTATE (RefcountMap, clang::ento::SymbolRef,
+                                tartan::RefcountState)
+
+namespace tartan {
+
+#if 0
+RefcountChecker::RefcountChecker ()
+{
+	// TODO: initialise bug types
+//  DoubleCloseBugType.reset(new BugType("Double fclose",
+//                                       "Unix Stream API Error"));
+// TODO: suppress leak bugs on sinks?
+}
+#endif
+
+void
+RefcountChecker::checkPostStmt (const CallExpr *call,
+                                CheckerContext &context) const
+{
+	// TODO: handle arbitrary functions
+	// TODO: handle constructors
+	const ProgramStateRef state = context.getState ();
+	const LocationContext *location_context = context.getLocationContext ();
+	const Expr *callee = call->getCallee ();
+	const FunctionDecl *decl =
+		state->getSVal (callee, location_context).getAsFunctionDecl ();
+
+	this->_initialise_identifiers (context.getASTContext ());
+
+	IdentifierInfo *ident = decl->getIdentifier ();
+	llvm::errs () << "bzzzt\n";
+	if (ident == this->_g_object_ref_identifier &&
+	    call->getNumArgs () == 1) {
+		this->_check_g_object_ref (call, context);
+		return;
+	} else if (ident == this->_g_object_unref_identifier &&
+	           call->getNumArgs () == 1) {
+		this->_check_g_object_unref (call, context);
+		return;
+	}
+}
+
+void
+RefcountChecker::_check_g_object_ref (const CallExpr *call,
+                                      CheckerContext &context) const
+{
+	ProgramStateRef state = context.getState ();
+	const LocationContext *location_context = context.getLocationContext ();
+	llvm::errs () << "bzzzt ref\n";
+	/* Get the symbolic value for the object. */
+	const Expr *arg_expr = call->getArg (0);
+	SVal obj_sval = state->getSVal (arg_expr, location_context);
+	SymbolRef obj = obj_sval.getAsSymbol ();
+
+	if (obj == NULL) {
+		/* TODO: warning? */
+		return;
+	}
+
+	/* Add an artificial symbol dependency between the object parameter and
+	 * the return value for g_object_ref(). This is essentially modelling
+	 * the behaviour of g_object_ref() as:
+	 *     GObject *g_object_ref (GObject *x) { return x; }
+	 * (ignoring the side effect of increasing X's reference count). */
+	state = state->BindExpr (call, location_context, obj_sval);
+
+	/* Generate a new transition in the exploded graph, adding a reference
+	 * to the object. */
+	const RefcountState *r_state = state->get<RefcountMap> (obj);
+	state = state->set<RefcountMap> (obj, RefcountState::reffed (r_state));
+	context.addTransition (state);
+}
+
+void
+RefcountChecker::_check_g_object_unref (const CallExpr *call,
+                                        CheckerContext &context) const
+{
+	ProgramStateRef state = context.getState ();
+	const LocationContext *location_context = context.getLocationContext ();
+	llvm::errs () << "bzzzt unref\n";
+	/* Get the symbolic value for the object. */
+	const Expr *arg_expr = call->getArg (0);
+	SVal obj_sval = state->getSVal (arg_expr, location_context);
+	SymbolRef obj = obj_sval.getAsSymbol ();
+
+	if (obj == NULL) {
+		/* TODO: warning? */
+		return;
+	}
+
+	/* Generate a new transition in the exploded graph, removing a
+	 * reference from the object. */
+	const RefcountState *r_state = state->get<RefcountMap> (obj);
+	RefcountState new_state = RefcountState::unreffed (r_state);
+
+	if (!new_state.is_valid ()) {
+		ExplodedNode *node = context.generateSink ();
+
+		if (node == NULL) {
+			return;
+		}
+
+		this->_initialise_bug_reports ();
+
+		BugReport *report = new BugReport (*this->_unref_bug,
+		                                   this->_unref_bug->getDescription(),
+		                                   node);
+		context.emitReport (report);
+
+		return;
+	}
+
+	state = state->set<RefcountMap> (obj, RefcountState::unreffed (r_state));
+	context.addTransition (state);
+}
+
+#if 0
+TODO
+static bool isLeaked(SymbolRef Sym, const StreamState &SS,
+                     bool IsSymDead, ProgramStateRef State) {
+  if (IsSymDead && SS.isOpened()) {
+    // If a symbol is NULL, assume that fopen failed on this path.
+    // A symbol should only be considered leaked if it is non-null.
+    ConstraintManager &CMgr = State->getConstraintManager();
+    ConditionTruthVal OpenFailed = CMgr.isNull(State, Sym);
+    return !OpenFailed.isConstrainedTrue();
+  }
+  return false;
+}
+
+void SimpleStreamChecker::checkDeadSymbols(SymbolReaper &SymReaper,
+                                           CheckerContext &C) const {
+  ProgramStateRef State = C.getState();
+  SymbolVector LeakedStreams;
+  StreamMapTy TrackedStreams = State->get<StreamMap>();
+  for (StreamMapTy::iterator I = TrackedStreams.begin(),
+                             E = TrackedStreams.end(); I != E; ++I) {
+    SymbolRef Sym = I->first;
+    bool IsSymDead = SymReaper.isDead(Sym);
+
+    // Collect leaked symbols.
+    if (isLeaked(Sym, I->second, IsSymDead, State))
+      LeakedStreams.push_back(Sym);
+
+    // Remove the dead symbol from the streams map.
+    if (IsSymDead)
+      State = State->remove<StreamMap>(Sym);
+  }
+
+  ExplodedNode *N = C.addTransition(State);
+  reportLeaks(LeakedStreams, C, N);
+}
+
+void SimpleStreamChecker::reportDoubleClose(SymbolRef FileDescSym,
+                                            const CallEvent &Call,
+                                            CheckerContext &C) const {
+  // We reached a bug, stop exploring the path here by generating a sink.
+  ExplodedNode *ErrNode = C.generateSink();
+  // If we've already reached this node on another path, return.
+  if (!ErrNode)
+    return;
+
+  // Generate the report.
+  BugReport *R = new BugReport(*DoubleCloseBugType,
+      "Closing a previously closed file stream", ErrNode);
+  R->addRange(Call.getSourceRange());
+  R->markInteresting(FileDescSym);
+  C.emitReport(R);
+}
+
+// If the pointer we are tracking escaped, do not track the symbol as
+// we cannot reason about it anymore.
+ProgramStateRef
+SimpleStreamChecker::checkPointerEscape(ProgramStateRef State,
+                                        const InvalidatedSymbols &Escaped,
+                                        const CallEvent *Call,
+                                        PointerEscapeKind Kind) const {
+  // If we know that the call cannot close a file, there is nothing to do.
+  if (Kind == PSK_DirectEscapeOnCall && guaranteedNotToCloseFile(*Call)) {
+    return State;
+  }
+
+  for (InvalidatedSymbols::const_iterator I = Escaped.begin(),
+                                          E = Escaped.end();
+                                          I != E; ++I) {
+    SymbolRef Sym = *I;
+
+    // The symbol escaped. Optimistically, assume that the corresponding file
+    // handle will be closed somewhere else.
+    State = State->remove<StreamMap>(Sym);
+  }
+  return State;
+}
+#endif
+
+void
+RefcountChecker::_initialise_identifiers (ASTContext &context) const
+{
+	if (this->_g_object_ref_identifier != NULL) {
+		return;
+	}
+
+	this->_g_object_ref_identifier = &context.Idents.get ("g_object_ref");
+	this->_g_object_unref_identifier =
+		&context.Idents.get ("g_object_unref");
+}
+
+void
+RefcountChecker::_initialise_bug_reports () const
+{
+	if (this->_unref_bug) {
+		return;
+	}
+
+	this->_unref_bug.reset (new BuiltinBug ("Unowned unref",
+	                                        "Try to unref an object "
+	                                        "you do not have ownership "
+	                                        "of. Cause eventual "
+	                                        "double-unref."));
+}
+
+} /* namespace tartan */
diff --git a/clang-plugin/refcount-checker.h b/clang-plugin/refcount-checker.h
new file mode 100644
index 0000000..9df69f7
--- /dev/null
+++ b/clang-plugin/refcount-checker.h
@@ -0,0 +1,74 @@
+/* -*- Mode: C++; indent-tabs-mode: t; c-basic-offset: 8; tab-width: 8 -*- */
+/*
+ * Tartan
+ * Copyright © 2014 Philip Withnall
+ *
+ * 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@tecnocode.co.uk>
+ */
+
+#ifndef TARTAN_REFCOUNT_CHECKER_H
+#define TARTAN_REFCOUNT_CHECKER_H
+
+#include <clang/AST/AST.h>
+#include <clang/StaticAnalyzer/Core/BugReporter/BugType.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 RefcountChecker : public ento::Checker<check::PostStmt<CallExpr>> {
+public:
+	explicit RefcountChecker () :
+		_gir_manager () {};
+
+private:
+	/* TODO: Share this with other checkers. */
+	GirManager _gir_manager;
+
+	/* Cached function identifiers. */
+	mutable IdentifierInfo *_g_object_ref_identifier;
+	mutable IdentifierInfo *_g_object_unref_identifier;
+
+	void _initialise_identifiers (ASTContext &context) const;
+
+	/* Cached bug reports. */
+	mutable OwningPtr<BuiltinBug> _unref_bug;
+
+	void _initialise_bug_reports () const;
+
+	void _check_g_object_ref (const CallExpr *call,
+	                          CheckerContext &context) const;
+	void _check_g_object_unref (const CallExpr *call,
+	                            CheckerContext &context) const;
+
+public:
+	void checkPostStmt (const CallExpr *call, CheckerContext &context) const;
+
+	/* TODO: doesn't implement tartan::Checker */
+	const std::string get_name () const { return "refcount"; }
+};
+
+} /* namespace tartan */
+
+#endif /* !TARTAN_REFCOUNT_CHECKER_H */
diff --git a/scripts/tartan b/scripts/tartan
index 46fdcbe..66fdfaa 100755
--- a/scripts/tartan
+++ b/scripts/tartan
@@ -87,10 +87,13 @@ if [ "$first_arg" == "" ]; then
 fi
 
 # Exec Clang with the plugin loaded.
+# The -analyzer-checker argument loads all 'tartan.*' static checkers.
+# The -add-plugin argument loads the tartan AST frontend plugin.
 exec "$real_clang" \
 	"$first_arg" \
 	-load "$plugin_path" \
 	-add-plugin "$plugin_name" \
+	-analyzer-checker "$plugin_name" \
 	${plugin_gir_options[@]} \
 	${plugin_options[@]} \
 	$GNOME_CLANG_CFLAGS \
diff --git a/tests/Makefile.am b/tests/Makefile.am
index 3fc9e91..35fcbac 100644
--- a/tests/Makefile.am
+++ b/tests/Makefile.am
@@ -16,6 +16,7 @@ c_tests = \
 	gvariant-lookup.c \
 	gvariant-new.c \
 	nonnull.c \
+	refcount-gobject-intra.c \
 	$(NULL)
 
 templates = \
@@ -29,6 +30,8 @@ templates = \
 	gsignal.tail.c \
 	gvariant.head.c \
 	gvariant.tail.c \
+	refcount-intra.head.c \
+	refcount-intra.tail.c \
 	$(NULL)
 
 TESTS = $(c_tests)
diff --git a/tests/refcount-gobject-intra.c b/tests/refcount-gobject-intra.c
new file mode 100644
index 0000000..a9e7dbe
--- /dev/null
+++ b/tests/refcount-gobject-intra.c
@@ -0,0 +1,65 @@
+/* Template: refcount-intra */
+
+/*
+ * No error
+ */
+{
+	/* Pass the reference straight through. */
+	return in;
+}
+
+/*
+ * TODO
+ */
+{
+	/* Add and leak an extra reference. */
+	return g_object_ref (in);
+}
+
+/*
+ * TODO
+ */
+{
+	/* Add and leak an extra reference a different way. */
+	g_object_ref (in);
+	return in;
+}
+
+/*
+ * TODO
+ */
+{
+	/* Steal a reference and cause a double-unref. */
+	g_object_unref (in);
+	return in;
+}
+
+/*
+ * No error
+ */
+{
+	/* Steal a reference but then don't transfer the object out. */
+	g_object_unref (in);
+	return NULL;
+}
+
+/*
+ * No error
+ */
+{
+	/* Return a different object. */
+	g_object_unref (in);
+	return g_object_new (G_TYPE_OBJECT, NULL);
+}
+
+/*
+ * No error
+ */
+{
+	GObject *out;
+
+	/* Return a different object via a temporary. */
+	g_object_unref (in);
+	out = g_object_new (G_TYPE_OBJECT, NULL);
+	return out;
+}
diff --git a/tests/refcount-intra.head.c b/tests/refcount-intra.head.c
new file mode 100644
index 0000000..55e8312
--- /dev/null
+++ b/tests/refcount-intra.head.c
@@ -0,0 +1,8 @@
+#include <stdio.h>
+
+#include <glib.h>
+#include <glib-object.h>
+
+static GObject *  /* transfer full */
+transfer_full_func (GObject *in  /* transfer full */)
+{
diff --git a/tests/refcount-intra.tail.c b/tests/refcount-intra.tail.c
new file mode 100644
index 0000000..08b3c1a
--- /dev/null
+++ b/tests/refcount-intra.tail.c
@@ -0,0 +1,12 @@
+}
+
+int
+main (void)
+{
+	GObject *out;
+
+	out = transfer_full_func (g_object_new (G_TYPE_OBJECT, NULL));
+	g_object_unref (out);
+
+	return 0;
+}