[FAIL 0/5] Static lock analysis

[FAIL 0/5] Static lock analysis

[Daniel Wagner]

Hi,

Locking can be tricky to get right and sometimes things go wrong. This
here is/was an attempt to come up with a simple static code analysis tool
which tries to point to problematic looking.

Especially figurering out if an access to variables wihtout holding
the right lock is happenin was of interest for me.

There are alot of small and bigger problems I faced and some of
them I was able to solve a lot of them not. Surprise surprise.

Anyway I learned quite a lot by doing this and maybe this epic fail
helps someone else in some way. :)

Maybe the first 3 patches might be okay to get merged.

cheers,
daniel

Daniel Wagner (5):
  parse: Add comment to struct statement
  inspect: Show context information
  linearize: Add context symbol name when showing context instructions
  parse: Add acquire, release, requires and guarded_by attributes
  test-locks: Add lock tester

 Makefile          |    3 +-
 allocate.c        |    1 +
 allocate.h        |    1 +
 ast-inspect.c     |   27 +-
 lib.c             |    2 +
 lib.h             |    7 +
 linearize.c       |    2 +-
 parse.c           |   64 ++++
 parse.h           |    2 +-
 symbol.c          |    5 +
 symbol.h          |   17 +
 test-locks.c      | 1020 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 validation/caps.c |   80 +++++
 13 files changed, 1227 insertions(+), 4 deletions(-)
 create mode 100644 test-locks.c
 create mode 100644 validation/caps.c

-- 
2.5.0

[FAIL 1/5] parse: Add comment to struct statement

[Daniel Wagner]

All the other members of the union got a nice comment
what they represent. Let's fix for context as well.

Signed-off-by: Daniel Wagner <daniel.wagner@bmw-carit.de>
---
 parse.h | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/parse.h b/parse.h
index 0c34ec2..195f0fd 100644
--- a/parse.h
+++ b/parse.h
@@ -51,7 +51,7 @@ struct statement {
 		struct /* declaration */ {
 			struct symbol_list *declaration;
 		};
-		struct {
+		struct /* context */ {
 			struct expression *expression;
 			struct expression *context;
 		};
-- 
2.5.0

[FAIL 2/5] inspect: Show context information

[Daniel Wagner]

Add the function context attributes and the context instruction
to the model.

Signed-off-by: Daniel Wagner <daniel.wagner@bmw-carit.de>
---
 ast-inspect.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/ast-inspect.c b/ast-inspect.c
index 24d4a4a..4502575 100644
--- a/ast-inspect.c
+++ b/ast-inspect.c
@@ -83,7 +83,10 @@ void inspect_statement(AstNode *node)
 			ast_append_child(node, "ret_value:", stmt->ret_value, inspect_expression);
 			ast_append_child(node, "ret_target:", stmt->ret_target, inspect_symbol);
 			break;
-
+		case STMT_CONTEXT:
+			ast_append_child(node, "expression:", stmt->expression, inspect_expression);
+			ast_append_child(node, "context:", stmt->context, inspect_expression);
+			break;
 		default:
 			break;
 	}
@@ -96,6 +99,27 @@ void inspect_statement_list(AstNode *node)
 }
 
 
+static const char *unnamed_context = "<unnamed>";
+
+static const char *context_name(struct context *context)
+{
+	if (context->context && context->context->symbol_name)
+		return show_ident(context->context->symbol_name);
+	return unnamed_context;
+}
+
+static void inspect_context(AstNode *node)
+{
+	struct context *context = node->ptr;
+	node->text = g_strdup_printf("%s %s: in %d out %d", node->text,
+				context_name(context), context->in, context->out);
+}
+
+static void inspect_context_list(AstNode *node)
+{
+	inspect_ptr_list(node, "context_list", inspect_context);
+}
+
 static const char *symbol_type_name(enum type type)
 {
 	static const char *type_name[] = {
@@ -134,6 +158,7 @@ void inspect_symbol(AstNode *node)
 		case NS_PREPROCESSOR:
 			break;
 		default:
+			ast_append_child(node, "contexts:", sym->ctype.contexts, inspect_context_list);
 			ast_append_child(node, "arguments:", sym->arguments, inspect_symbol_list);
 			ast_append_child(node, "symbol_list:", sym->symbol_list, inspect_symbol_list);
 			ast_append_child(node, "stmt:", sym->stmt, inspect_statement);
-- 
2.5.0

[FAIL 3/5] linearize: Add context symbol name when showing context instructions

[Daniel Wagner]

Signed-off-by: Daniel Wagner <daniel.wagner@bmw-carit.de>
---
 linearize.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

diff --git a/linearize.c b/linearize.c
index c6ada1e..da3a190 100644
--- a/linearize.c
+++ b/linearize.c
@@ -441,7 +441,7 @@ const char *show_instruction(struct instruction *insn)
 		break;
 
 	case OP_CONTEXT:
-		buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
+		buf += sprintf(buf, "%s %s%d", insn->context_expr? show_ident(insn->context_expr->symbol_name) : "",  insn->check ? "check: " : "", insn->increment);
 		break;
 	case OP_RANGE:
 		buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));
-- 
2.5.0

[FAIL 4/5] parse: Add acquire, release, requires and guarded_by attributes

[Daniel Wagner]

The static clang and also gcc knows this attributes and they
are used to do thread safety analysis.

Signed-off-by: Daniel Wagner <daniel.wagner@bmw-carit.de>
Link: http://clang.llvm.org/docs/ThreadSafetyAnalysis.html
---
 allocate.c |  1 +
 allocate.h |  1 +
 parse.c    | 64 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 symbol.c   |  5 +++++
 symbol.h   | 17 +++++++++++++++++
 5 files changed, 88 insertions(+)

diff --git a/allocate.c b/allocate.c
index f597caf..6506fcd 100644
--- a/allocate.c
+++ b/allocate.c
@@ -130,6 +130,7 @@ void show_allocations(struct allocator_struct *x)
 ALLOCATOR(ident, "identifiers");
 ALLOCATOR(token, "tokens");
 ALLOCATOR(context, "contexts");
+ALLOCATOR(capability, "capability");
 ALLOCATOR(symbol, "symbols");
 ALLOCATOR(expression, "expressions");
 ALLOCATOR(statement, "statements");
diff --git a/allocate.h b/allocate.h
index 9f1dc8c..ce0677d 100644
--- a/allocate.h
+++ b/allocate.h
@@ -65,6 +65,7 @@ extern void show_allocations(struct allocator_struct *);
 DECLARE_ALLOCATOR(ident);
 DECLARE_ALLOCATOR(token);
 DECLARE_ALLOCATOR(context);
+DECLARE_ALLOCATOR(capability);
 DECLARE_ALLOCATOR(symbol);
 DECLARE_ALLOCATOR(expression);
 DECLARE_ALLOCATOR(statement);
diff --git a/parse.c b/parse.c
index b43d683..aef71f1 100644
--- a/parse.c
+++ b/parse.c
@@ -80,6 +80,8 @@ typedef struct token *attr_t(struct token *, struct symbol *,
 static attr_t
 	attribute_packed, attribute_aligned, attribute_modifier,
 	attribute_address_space, attribute_context,
+	attribute_acquire, attribute_release, attribute_requires,
+	attribute_guarded_by,
 	attribute_designated_init,
 	attribute_transparent_union, ignore_attribute,
 	attribute_mode, attribute_force;
@@ -336,6 +338,22 @@ static struct symbol_op context_op = {
 	.attribute = attribute_context,
 };
 
+static struct symbol_op acquire_op = {
+	.attribute = attribute_acquire,
+};
+
+static struct symbol_op release_op = {
+	.attribute = attribute_release,
+};
+
+static struct symbol_op requires_op = {
+	.attribute = attribute_requires,
+};
+
+static struct symbol_op guarded_by_op = {
+	.attribute = attribute_guarded_by,
+};
+
 static struct symbol_op designated_init_op = {
 	.attribute = attribute_designated_init,
 };
@@ -476,6 +494,10 @@ static struct init_keyword {
 	{ "address_space",NS_KEYWORD,	.op = &address_space_op },
 	{ "mode",	NS_KEYWORD,	.op = &mode_op },
 	{ "context",	NS_KEYWORD,	.op = &context_op },
+	{ "acquire_capability",	NS_KEYWORD,	.op = &acquire_op },
+	{ "release_capability",	NS_KEYWORD,	.op = &release_op },
+	{ "requires_capability",	NS_KEYWORD,	.op = &requires_op },
+	{ "guarded_by", NS_KEYWORD,	.op = &guarded_by_op },
 	{ "designated_init",	NS_KEYWORD,	.op = &designated_init_op },
 	{ "__transparent_union__",	NS_KEYWORD,	.op = &transparent_union_op },
 	{ "noreturn",	NS_KEYWORD,	MOD_NORETURN,	.op = &attr_mod_op },
@@ -1197,6 +1219,48 @@ static struct token *attribute_context(struct token *token, struct symbol *attr,
 	return token;
 }
 
+static const char *cap_ops[] = {
+	[CAP_ACQUIRE] = "after acquire_capability attribute",
+	[CAP_RELEASE] = "after release_capability attribute",
+	[CAP_REQUIRES] = "after requires_capability attribute",
+	[CAP_GUARDED_BY] = "after guarded_by attribute",
+};
+
+static struct token *attribute_capability(struct token *token, struct decl_state *ctx, enum cap_op op)
+{
+	struct expression *expr = NULL;
+	struct capability *cap;
+
+	token = expect(token, '(', cap_ops[op]);
+	token = conditional_expression(token, &expr);
+	cap = alloc_capability();
+	cap->op = op;
+	cap->expr = expr;
+	add_ptr_list(&ctx->ctype.capabilities, cap);
+	token = expect(token, ')', cap_ops[op]);
+	return token;
+}
+
+static struct token *attribute_acquire(struct token *token, struct symbol *attr, struct decl_state *ctx)
+{
+	return attribute_capability(token, ctx, CAP_ACQUIRE);
+}
+
+static struct token *attribute_release(struct token *token, struct symbol *attr, struct decl_state *ctx)
+{
+	return attribute_capability(token, ctx, CAP_RELEASE);
+}
+
+static struct token *attribute_requires(struct token *token, struct symbol *attr, struct decl_state *ctx)
+{
+	return attribute_capability(token, ctx, CAP_REQUIRES);
+}
+
+static struct token *attribute_guarded_by(struct token *token, struct symbol *attr, struct decl_state *ctx)
+{
+	return attribute_capability(token, ctx, CAP_GUARDED_BY);
+}
+
 static struct token *attribute_designated_init(struct token *token, struct symbol *attr, struct decl_state *ctx)
 {
 	if (ctx->ctype.base_type && ctx->ctype.base_type->type == SYM_STRUCT)
diff --git a/symbol.c b/symbol.c
index 0ceff62..12e23b4 100644
--- a/symbol.c
+++ b/symbol.c
@@ -73,6 +73,11 @@ struct context *alloc_context(void)
 	return __alloc_context(0);
 }
 
+struct capability *alloc_capability(void)
+{
+	return __alloc_capability(0);
+}
+
 struct symbol *alloc_symbol(struct position pos, int type)
 {
 	struct symbol *sym = __alloc_symbol(0);
diff --git a/symbol.h b/symbol.h
index ccb5dcb..bcb41b7 100644
--- a/symbol.h
+++ b/symbol.h
@@ -97,10 +97,27 @@ extern struct context *alloc_context(void);
 
 DECLARE_PTR_LIST(context_list, struct context);
 
+enum cap_op {
+	CAP_ACQUIRE,
+	CAP_RELEASE,
+	CAP_REQUIRES,
+	CAP_GUARDED_BY,
+};
+
+struct capability {
+	struct expression *expr;
+	enum cap_op op;
+};
+
+extern struct capability *alloc_capability(void);
+
+DECLARE_PTR_LIST(capability_list, struct capability);
+
 struct ctype {
 	unsigned long modifiers;
 	unsigned long alignment;
 	struct context_list *contexts;
+	struct capability_list *capabilities;
 	unsigned int as;
 	struct symbol *base_type;
 };
-- 
2.5.0

[FAIL 5/5] test-locks: Add lock tester

[Daniel Wagner]

I was playing a bit around to see if it is possible to figure out if a
variable is accessed without holding the corresponding lock. This never
got anywhere and that's why I abandon it. In case someone wants to
use parts of it or whatever, please be my guest.

Example output:

./test-locks validation/caps.c
validation/caps.c:49:13: warning: function 'set_str' not holding 'anon'
validation/caps.c:25:13: warning: leaks lock 'anon'
  frame: ep 0x7f0af437e010 a
  frame: ep 0x7f0af437e0a0 okay1 (call        a)
  frame: ep 0x7f0af437e0d0 bad2 (call        okay1)

validation/caps.c:70:8: warning: leaks lock 'global_lock'
  frame: ep 0x7f0af437e100 wtf_lock
  frame: ep 0x7f0af437e1f0 bad4 (call        wtf_lock, global_lock)

Signed-off-by: Daniel Wagner <daniel.wagner@bmw-carit.de>
---
 Makefile          |    3 +-
 lib.c             |    2 +
 lib.h             |    7 +
 test-locks.c      | 1020 +++++++++++++++++++++++++++++++++++++++++++++++++++++
 validation/caps.c |   80 +++++
 5 files changed, 1111 insertions(+), 1 deletion(-)
 create mode 100644 test-locks.c
 create mode 100644 validation/caps.c

diff --git a/Makefile b/Makefile
index c7031af..db0c343 100644
--- a/Makefile
+++ b/Makefile
@@ -54,7 +54,8 @@ INCLUDEDIR=$(PREFIX)/include
 PKGCONFIGDIR=$(LIBDIR)/pkgconfig
 
 PROGRAMS=test-lexing test-parsing obfuscate compile graph sparse \
-	 test-linearize example test-unssa test-dissect ctags
+	 test-linearize example test-unssa test-dissect ctags \
+	 test-locks
 INST_PROGRAMS=sparse cgcc
 INST_MAN1=sparse.1 cgcc.1
 
diff --git a/lib.c b/lib.c
index 8dc5bcf..7b49e2f 100644
--- a/lib.c
+++ b/lib.c
@@ -244,6 +244,7 @@ int Wvla = 1;
 
 int dbg_entry = 0;
 int dbg_dead = 0;
+int dbg_caps = 0;
 
 int preprocess_only;
 
@@ -518,6 +519,7 @@ static char **handle_switch_W(char *arg, char **next)
 static struct warning debugs[] = {
 	{ "entry", &dbg_entry},
 	{ "dead", &dbg_dead},
+	{ "caps", &dbg_caps},
 };
 
 
diff --git a/lib.h b/lib.h
index 15b69fa..87d1948 100644
--- a/lib.h
+++ b/lib.h
@@ -130,6 +130,7 @@ extern int Wvla;
 
 extern int dbg_entry;
 extern int dbg_dead;
+extern int dbg_caps;
 
 extern int arch_m64;
 
@@ -189,6 +190,12 @@ static inline struct basic_block *first_basic_block(struct basic_block_list *hea
 {
 	return first_ptr_list((struct ptr_list *)head);
 }
+
+static inline struct basic_block *last_basic_block(struct basic_block_list *head)
+{
+	return last_ptr_list((struct ptr_list *)head);
+}
+
 static inline struct instruction *last_instruction(struct instruction_list *head)
 {
 	return last_ptr_list((struct ptr_list *)head);
diff --git a/test-locks.c b/test-locks.c
new file mode 100644
index 0000000..f311f4c
--- /dev/null
+++ b/test-locks.c
@@ -0,0 +1,1020 @@
+/*
+ * This is an miserable attempt in static code analysis. The test
+ * executes the program and maintains a current set of locks. At every
+ * function entry and exit point all the current lock set is attached
+ * to the function and the current calling stack is also added to the lock.
+ *
+ * In the second phase the check_leaking() function then looks at all
+ * locks and the calling stacks and reports all those function which
+ * have an lock in the exit lock set and no other function is calling them.
+ * Obvioysly reallity is much more complex and this simple testing
+ * will not catch a lot of wrong cases.
+ *
+ * There is also the attempt to figure out if a variable has been accessed
+ * without holding the corresponding lock.
+ *
+ * If you want to understand what is doing run it with
+ *
+ *   $ test-locks validation/caps.c -vcaps -v -v -v
+ *
+ * which print a lot of details.
+ *
+ * Copyright (C) 2016  BMW Car IT GmbH.
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a copy
+ * of this software and associated documentation files (the "Software"), to deal
+ * in the Software without restriction, including without limitation the rights
+ * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+ * copies of the Software, and to permit persons to whom the Software is
+ * furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice shall be included in
+ * all copies or substantial portions of the Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+ * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+ * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
+ * THE SOFTWARE.
+ */
+
+#include <stdarg.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <string.h>
+#include <ctype.h>
+#include <unistd.h>
+#include <fcntl.h>
+
+#include "lib.h"
+#include "allocate.h"
+#include "token.h"
+#include "parse.h"
+#include "symbol.h"
+#include "expression.h"
+#include "linearize.h"
+#include "flow.h"
+#include "scope.h"
+
+#define dbg_level0 (dbg_caps)
+#define dbg_level1 (dbg_caps && verbose > 0)
+#define dbg_level2 (dbg_caps && verbose > 1)
+#define dbg_level3 (dbg_caps && verbose > 2)
+
+struct frame {
+	struct instruction *insn;
+	struct entrypoint *ep;
+};
+
+ALLOCATOR(frame, "call stack");
+DECLARE_PTR_LIST(frame_list, struct frame);
+
+struct frame *alloc_frame(struct entrypoint *ep, struct instruction *insn)
+{
+	struct frame *frame = __alloc_frame(0);
+
+	frame->ep = ep;
+	frame->insn = insn;
+	return frame;
+}
+
+static inline struct frame *last_frame(struct frame_list *head)
+{
+	return last_ptr_list((struct ptr_list *)head);
+}
+
+static inline struct frame *first_frame(struct frame_list *head)
+{
+	return first_ptr_list((struct ptr_list *)head);
+}
+
+static inline struct frame *delete_last_frame(struct frame_list **head)
+{
+	return delete_ptr_list_last((struct ptr_list **)head);
+}
+
+static inline void add_frame(struct frame_list **list, struct frame *frame)
+{
+	add_ptr_list(list, frame);
+}
+
+static inline struct frame *lookup_frame(struct frame_list *list,
+					struct  entrypoint *ep)
+{
+	struct frame *c;
+
+	FOR_EACH_PTR(list, c) {
+		if (c->ep == ep)
+			return c;
+	} END_FOR_EACH_PTR(c);
+
+	return NULL;
+}
+
+static inline int frame_list_size(struct frame_list *head)
+{
+	return ptr_list_size((struct ptr_list *)head);
+}
+
+static inline int frame_cmp(struct frame *f1, struct frame *f2)
+{
+	return !(f1->ep == f2->ep && f1->insn == f2->insn);
+}
+
+static int stack_cmp(struct frame_list *s1, struct frame_list *s2)
+{
+	struct frame *f1, *f2;
+
+	PREPARE_PTR_LIST(s1, f1);
+	PREPARE_PTR_LIST(s2, f2);
+	for (;;) {
+		if (!f1 || !f2)
+			return 1;
+
+		if (frame_cmp(f1, f2))
+			return 1;
+
+		NEXT_PTR_LIST(f1);
+		NEXT_PTR_LIST(f2);
+	}
+	FINISH_PTR_LIST(f2);
+	FINISH_PTR_LIST(f1);
+
+	return 0;
+}
+
+static int stack_frame_position(struct frame_list *stack, struct entrypoint *ep)
+{
+	struct frame *f;
+	int pos = 0;
+
+	FOR_EACH_PTR(stack, f) {
+		if (f->ep == ep)
+			return pos;
+		pos++;
+	} END_FOR_EACH_PTR(f);
+
+	return -1;
+}
+
+static void copy_stack(struct frame_list *from, struct frame_list **to)
+{
+	struct frame *c;
+
+	FOR_EACH_PTR(from, c) {
+		add_frame(to, alloc_frame(c->ep, c->insn));
+	} END_FOR_EACH_PTR(c);
+}
+
+/* Better naming wouldn't hurt. we could also do a frame_list** in
+ * struct lock but that is really hard to read. Let's wrap it here and
+ * use it as 2 dimensional list.
+ */
+struct stack {
+	struct frame_list *stack;
+};
+ALLOCATOR(stack, "stack list");
+DECLARE_PTR_LIST(stack_list, struct stack);
+
+static inline void add_stack(struct stack_list **list, struct stack *stack)
+{
+	add_ptr_list(list, stack);
+}
+
+struct lock {
+	unsigned int ref;
+	struct symbol *sym;
+	struct capability_list *caps;
+	struct stack_list *stacks;
+};
+
+ALLOCATOR(lock, "lock list");
+DECLARE_PTR_LIST(lock_list, struct lock);
+
+static struct lock *alloc_lock(struct symbol *sym)
+{
+	struct lock *lock = __alloc_lock(0);
+
+	lock->ref = 1;
+	lock->sym = sym;
+
+	return lock;
+};
+
+static inline void ref_lock(struct lock *lock)
+{
+	lock->ref++;
+}
+
+static inline unsigned int unref_lock(struct lock *lock)
+{
+	return --lock->ref;
+}
+
+static inline void add_lock(struct lock_list **list, struct lock *lock)
+{
+	add_ptr_list(list, lock);
+}
+
+static inline void remove_lock(struct lock_list **list, struct lock *lock)
+{
+	delete_ptr_list_entry((struct ptr_list **)list, lock, 1);
+}
+
+static struct lock *lookup_lock(struct lock_list *list, struct symbol *sym)
+{
+	struct lock *l;
+
+	FOR_EACH_PTR(list, l) {
+		if (sym == l->sym)
+			return l;
+	} END_FOR_EACH_PTR(l);
+
+	return NULL;
+}
+
+static struct lock_list *all_locks;
+
+static void add_stack_trace(struct frame_list *stack, struct lock *lock)
+{
+	struct stack *st;
+
+	/* Filter out duplicates */
+	FOR_EACH_PTR(lock->stacks, st) {
+		if (!stack_cmp(stack, st->stack))
+			return;
+	} END_FOR_EACH_PTR(st);
+
+	st = __alloc_stack(0);
+	copy_stack(stack, &st->stack);
+	add_stack(&lock->stacks, st);
+}
+
+/* Copy the current lock set to either the entry or exit list of the
+ * function. Remember also the calling stack. This will be handy
+ * in the second step of the analysis when we check for leaking
+ * locks etc.
+ */
+static void copy_lock_list(struct frame_list *stack,
+				struct lock_list *from, struct lock_list **to)
+{
+	struct lock *lock, *l;
+
+	FOR_EACH_PTR(from, lock) {
+		/* let's colapse symbols with the same addresse to one
+		 * lock and remove duplicates by this.
+		 */
+		l = lookup_lock(all_locks, lock->sym);
+		if (!l) {
+			l = alloc_lock(lock->sym);
+			add_lock(&all_locks, l);
+		} else
+			ref_lock(l);
+
+		if (!lookup_lock(*to, lock->sym))
+			add_lock(to, l);
+
+		add_stack_trace(stack, l);
+	} END_FOR_EACH_PTR(lock);
+}
+
+static inline int lock_list_size(struct lock_list *list)
+{
+	return ptr_list_size((struct ptr_list *)list);
+}
+
+struct bb_info {
+	struct lock_list *entry;
+	struct lock_list *exit;
+};
+ALLOCATOR(bb_info, "bb info");
+
+/* debug printfs helpers */
+
+static void show_call_stack(struct frame_list *list, int level)
+{
+	struct frame *c;
+
+	FOR_EACH_PTR_REVERSE(list, c) {
+		printf("%*sframe: ep %p %s", level * 2, "", c->ep,
+			show_ident(c->ep->name->ident));
+		if (c->insn)
+			printf(" (%s)", show_instruction(c->insn));
+		printf("\n");
+	} END_FOR_EACH_PTR_REVERSE(c);
+}
+
+static void show_short_symbol_list(struct symbol_list *list, const char *name)
+{
+	struct symbol *sym;
+	const char *prepend = "";
+
+	printf("%s:\t", name);
+	FOR_EACH_PTR(list, sym) {
+		printf("%s", prepend);
+		prepend = ", ";
+		printf("%s",  show_ident(sym->ident));
+	} END_FOR_EACH_PTR(sym);
+	puts("");
+}
+
+static void show_pseudo_user_list(struct pseudo_user_list *list,
+				  const char *name)
+{
+	struct pseudo_user *pu;
+
+	if (ptr_list_empty(list))
+		return;
+	printf("%s:\n", name);
+	FOR_EACH_PTR(list, pu) {
+		printf("\t%s used by %p, %s\n",
+			show_pseudo(*pu->userp), pu->insn,
+			show_instruction(pu->insn));
+	} END_FOR_EACH_PTR(pu);
+}
+
+static void show_pseudo_list(struct pseudo_list *list, const char *name)
+{
+	struct pseudo *p;
+	struct symbol *s;
+
+	printf("%s:\n", name);
+	FOR_EACH_PTR(list, p) {
+		printf("\t%s",  show_pseudo(p));
+		switch (p->type) {
+		case PSEUDO_SYM:
+			printf(" (symbol %p scope %p ", p->sym, p->sym->scope);
+			s = p->sym->next_id;
+			while (s) {
+				printf("next_id %p ", s);
+				s = s->next_id;
+			}
+			show_type(p->sym);
+			printf(")\n");
+			break;
+		case PSEUDO_ARG:
+			printf(" (");
+			show_pseudo_user_list(p->users, "users");
+			printf(" )\n");
+			break;
+		default:
+			break;
+		}
+	} END_FOR_EACH_PTR(p);
+}
+
+static void show_basic_block_list(struct basic_block_list *list,
+				  const char *name)
+{
+	struct basic_block *bb;
+	const char *prepend = "";
+
+	printf("%s:\t", name);
+	FOR_EACH_PTR(list, bb) {
+		printf("%s", prepend);
+		prepend = ", ";
+		printf("%p",  bb);
+	} END_FOR_EACH_PTR(bb);
+	puts("");
+}
+
+static const char * const cap_ops[] = {
+	[CAP_ACQUIRE] = "acquire",
+	[CAP_RELEASE] = "release",
+	[CAP_REQUIRES] = "requires",
+	[CAP_GUARDED_BY] = "guarded_by",
+};
+
+static void show_cap(struct capability *cap)
+{
+	printf("cap %p %s '%s'\n", cap,
+		cap_ops[cap->op],
+		cap->expr ? show_ident(cap->expr->symbol_name) : "anon");
+}
+
+static void show_lock(struct lock *lock, const char *prepend,
+		const char *postfix)
+{
+	printf("%ssym %p '%s' %s",
+		prepend, lock->sym,
+		lock->sym ? show_ident(lock->sym->ident) : "anon",
+		postfix);
+}
+
+static void show_lock_list(struct lock_list *locks,
+			const char *prepend, const char *postfix)
+{
+	struct lock *lock;
+
+	FOR_EACH_PTR(locks, lock) {
+		show_lock(lock, prepend, postfix);
+	} END_FOR_EACH_PTR(lock);
+}
+
+static void show_cap_list(struct capability_list *list, const char *name)
+{
+	struct capability *cap;
+	const char *prepend = "";
+
+	printf("%s:\t", name);
+	FOR_EACH_PTR(list, cap) {
+		printf("%s", prepend);
+		prepend = ", ";
+		show_cap(cap);
+	} END_FOR_EACH_PTR(cap);
+	puts("");
+}
+
+static void show_bb_lock_list(struct basic_block_list *list, const char *name)
+{
+	struct basic_block *bb;
+
+	printf("%s:\n", name);
+	FOR_EACH_PTR(list, bb) {
+		struct bb_info *info = bb->priv;
+
+		printf("\tbb %p\n", bb);
+		printf("\t\tlocks entry:\n");
+		show_lock_list(info->entry, "\t\t\t", "\n");
+		printf("\t\tlocks exit:\n");
+		show_lock_list(info->exit, "\t\t\t", "\n");
+	} END_FOR_EACH_PTR(bb);
+}
+
+static void show_entry_lock_list(struct entrypoint *ep, int level)
+{
+	struct basic_block *bb = ep->entry->bb;
+	struct bb_info *info = bb->priv;
+
+	printf("%*slocks entry:", level * 2, "");
+	show_lock_list(info->entry, " ", ",");
+	printf("\n");
+}
+
+static void show_exit_lock_list(struct entrypoint *ep, int level)
+{
+	struct basic_block *bb = last_basic_block(ep->bbs);
+	struct bb_info *info = bb->priv;
+
+	printf("%*slocks exit:", level * 2, "");
+	show_lock_list(info->exit, " ", ",");
+	printf("\n");
+}
+
+static void show_entrypoint(struct entrypoint *ep)
+{
+	printf("ep:\t%s\n", ep->name->ident->name);
+	show_short_symbol_list(ep->name->ctype.base_type->arguments, "args");
+	show_short_symbol_list(ep->syms, "syms");
+	show_pseudo_list(ep->accesses, "accesses");
+	show_basic_block_list(ep->bbs, "bbs");
+	show_pseudo_list(ep->entry->arg_list, "arg_list");
+	show_cap_list(ep->name->ctype.capabilities, "caps");
+	show_bb_lock_list(ep->bbs, "locks");
+}
+
+static struct pseudo *lookup_accesses(struct entrypoint *ep,
+					struct ident *ident)
+{
+	struct pseudo *p;
+
+	if (!ident)
+		return NULL;
+
+	FOR_EACH_PTR(ep->accesses, p) {
+		if (p->ident && !strcmp(p->ident->name, ident->name))
+			return p;
+	} END_FOR_EACH_PTR(p);
+
+	return NULL;
+}
+
+static struct pseudo *get_argument_pseudo(struct pseudo_list *list, int nr)
+{
+	struct pseudo *p;
+	int i = 1;
+
+	FOR_EACH_PTR(list, p) {
+		if (i == nr)
+			return p;
+		i++;
+	} END_FOR_EACH_PTR(p);
+
+	return NULL;
+}
+
+static int get_argument_nr(struct symbol_list *list, struct pseudo *p)
+{
+	int i = 0;
+	struct symbol *sym;
+
+	FOR_EACH_PTR(list, sym) {
+		i++;
+		if (strcmp(sym->ident->name, p->ident->name))
+			continue;
+		return i;
+	} END_FOR_EACH_PTR(sym);
+
+	return -1;
+}
+
+static struct symbol *figure_access(struct pseudo *p, struct frame_list *stack)
+{
+	struct symbol *sym, *type;
+	struct frame *f;
+	int argc = -1;
+
+	FOR_EACH_PTR_REVERSE(stack, f) {
+		if (argc >= 0) {
+			p = get_argument_pseudo(f->insn->arguments, argc);
+			if (!p) {
+				printf("bug bug bug bug for YOUUUUU!!\n");
+				return NULL;
+			}
+
+			argc = -1;
+		}
+
+		if (p->type == PSEUDO_ARG) {
+			/* this is an argument so we can just go on
+			 * frame up and look at the caller.
+			 */
+			argc = p->nr;
+			continue;
+		}
+
+		if (p->type == PSEUDO_SYM) {
+			sym = get_base_type(p->sym);
+			if (is_ptr_type(sym)) {
+				/* so we have a pointer. was it passed
+				 * in as argument?
+				 */
+				type = f->ep->name->ctype.base_type;
+				argc = get_argument_nr(type->arguments, p);
+				continue;
+			} else
+				return p->sym;
+		}
+
+		/* p is not ARG nor SYM, that's the end of the story */
+		break;
+	} END_FOR_EACH_PTR_REVERSE(f);
+
+	return NULL;
+}
+
+static struct symbol *figure_capability(struct capability *cap,
+					struct entrypoint *ep,
+					struct frame_list *stack)
+{
+	struct symbol *sym;
+	struct pseudo *p;
+
+	if (!cap->expr)
+		return NULL;
+
+	if (cap->expr->symbol) {
+		/* so from the linearization step we have a proper symbol,
+		 * just get the pseudo.
+		 */
+		p = lookup_accesses(ep, cap->expr->symbol->ident);
+	} else {
+		/* no luck, we only have the name so let's use that one
+		 * instead.
+		 */
+		p = lookup_accesses(ep, cap->expr->symbol_name);
+	}
+
+	if (p) {
+		/* we found a pseudo in this function, let's try to
+		 * defer it, that is where is defined. note the final
+		 * call frame also handles the global symbols because
+		 * they are also listed in the accesses list.
+		 */
+		sym = figure_access(p, stack);
+	} else {
+		/* the context attributes didn't get the linearize
+		 * treatment, that means the access has not been
+		 * added to the accesses list. first we tried
+		 * to lookup in the accesses list but it is not there
+		 * so we just try to see if it is a global symbol.
+		 */
+		sym = lookup_symbol(cap->expr->symbol_name, NS_SYMBOL);
+	}
+
+	return sym;
+}
+
+static void acquire_lock(struct lock_list **lset, struct entrypoint *ep,
+			struct frame_list *stack, struct capability *cap)
+{
+	struct symbol *sym;
+	struct lock *lock;
+
+	sym = figure_capability(cap, ep, stack);
+	lock = lookup_lock(*lset, sym);
+
+	if (!lock) {
+		lock = alloc_lock(sym);
+		add_lock(lset, lock);
+	} else
+		ref_lock(lock);
+}
+
+static void release_lock(struct lock_list **lset, struct entrypoint *ep,
+			struct frame_list *stack, struct capability *cap)
+{
+	struct symbol *sym;
+	struct lock *lock;
+
+	sym = figure_capability(cap, ep, stack);
+	lock = lookup_lock(*lset, sym);
+
+	if (!lock)
+		return;
+
+	if (!unref_lock(lock)) {
+		remove_lock(lset, lock);
+		__free_lock(lock);
+	}
+}
+
+static void check_cap_requires(struct lock_list **lset,
+				struct entrypoint *ep, struct frame_list *stack)
+{
+	struct capability *cap;
+
+	if (frame_list_size(stack) == 1) {
+		/* there is little point in checking if the caller holds
+		 * the required locks if there is no caller.
+		 */
+		return;
+	}
+
+	/* First step of validation. Let's check if we see
+	 * the required lock in the working set.
+	 */
+	FOR_EACH_PTR(ep->name->ctype.capabilities, cap) {
+		struct symbol *s = figure_capability(cap, ep, stack);
+		struct lock *l;
+
+		switch (cap->op) {
+		case CAP_REQUIRES:
+			l = lookup_lock(*lset, s);
+			if (!l) {
+				warning(ep->name->pos,
+					"function '%s' not holding '%s'",
+					show_ident(ep->name->ident),
+					s ? s->ident->name : "anon");
+			}
+			break;
+		default:
+			break;
+		}
+	} END_FOR_EACH_PTR(cap);
+}
+
+static void update_locks_on_entry(struct lock_list **lset,
+				  struct entrypoint *ep,
+				  struct frame_list *stack,
+				  int level)
+{
+	struct basic_block *bb = ep->entry->bb;
+	struct bb_info *info = bb->priv;
+
+	copy_lock_list(stack, *lset, &info->entry);
+
+	check_cap_requires(lset, ep, stack);
+
+	if (dbg_level0)
+		show_entry_lock_list(ep, level);
+}
+
+static void update_locks_on_exit(struct lock_list **lset,
+				 struct entrypoint *ep,
+				 struct frame_list *stack,
+				 int level)
+{
+	struct basic_block *bb = last_basic_block(ep->bbs);
+	struct bb_info *info = bb->priv;
+	struct capability *cap;
+
+	FOR_EACH_PTR(ep->name->ctype.capabilities, cap) {
+		struct symbol *s = figure_capability(cap, ep, stack);
+		struct lock *l;
+
+		switch (cap->op) {
+		case CAP_ACQUIRE:
+			acquire_lock(lset, ep, stack, cap);
+			break;
+		case CAP_RELEASE:
+			release_lock(lset, ep, stack, cap);
+			break;
+		case CAP_REQUIRES:
+			l = lookup_lock(*lset, s);
+			if (!l) {
+				warning(ep->name->pos,
+					"function '%s' not holding '%s'",
+					show_ident(ep->name->ident),
+					s ? s->ident->name : "anon");
+			}
+			break;
+		default:
+			break;
+		}
+	} END_FOR_EACH_PTR(cap);
+
+	copy_lock_list(stack, *lset, &info->exit);
+
+	if (dbg_level0)
+		show_exit_lock_list(ep, level);
+}
+
+static int function_acquires_lock(struct entrypoint *ep)
+{
+	struct capability *cap;
+
+	FOR_EACH_PTR(ep->name->ctype.capabilities, cap) {
+		if (cap->op == CAP_ACQUIRE)
+			return 1;
+	} END_FOR_EACH_PTR(cap);
+
+	return 0;
+}
+
+static void check_leaking(struct entrypoint *ep)
+{
+	struct basic_block *bb = last_basic_block(ep->bbs);
+	struct bb_info *info = bb->priv;
+	struct lock *lock;
+
+	/* Let's ignore function which acquire locks for the time
+	 * beeing.
+	 */
+	if (function_acquires_lock(ep))
+		return;
+
+	FOR_EACH_PTR(info->exit, lock) {
+		struct stack *st;
+		struct frame_list *leak = NULL;
+		int pos;
+
+		FOR_EACH_PTR(lock->stacks, st) {
+			/* Find a call stack where this ep is the first
+			 * one.
+			 */
+			pos = stack_frame_position(st->stack, ep);
+			if (pos == 0) {
+				if (function_acquires_lock(
+						last_frame(st->stack)->ep)) {
+					leak = st->stack;
+				}
+			} else if (pos > 0) {
+				leak = NULL;
+			}
+		} END_FOR_EACH_PTR(st);
+
+		if (!leak)
+			continue;
+
+		warning(ep->name->pos, "leaks lock '%s'",
+			lock->sym ? show_ident(lock->sym->ident) : "anon");
+		show_call_stack(leak, 1);
+		printf("\n");
+	} END_FOR_EACH_PTR(lock);
+}
+
+static void check_sym_access(struct instruction *insn,
+			struct symbol *sym, struct basic_block *bb,
+			struct lock_list *lset,
+			struct frame_list *stack)
+{
+	struct capability *c;
+	struct lock *l;
+
+	FOR_EACH_PTR(sym->ctype.capabilities, c) {
+		struct symbol *s = figure_capability(c, bb->ep, stack);
+
+		l = lookup_lock(lset, s);
+		if (!l) {
+			warning(insn->pos,
+				"accessing '%s' without holding '%s'",
+				sym->ident->name,
+				s->ident->name);
+		}
+	} END_FOR_EACH_PTR(c);
+}
+
+static void check_bb(struct basic_block *bb, struct lock_list **lset,
+		struct frame_list *stack, unsigned long generation,
+		int level);
+
+static void handle_call(struct instruction *insn, struct lock_list **lset,
+			struct frame_list *stack, int level)
+{
+	struct entrypoint *ep;
+	struct symbol *sym;
+	struct frame *frame;
+
+	if (!insn->func->ident)
+		return;
+
+	sym = lookup_symbol(insn->func->ident, NS_SYMBOL);
+	if (!sym)
+		return;
+	ep = sym->ep;
+
+	/* no code/entrypoint for this symbol, decleration only */
+	if (!ep)
+		return;
+
+	/* prevent recursions */
+	frame = lookup_frame(stack, ep);
+	if (frame)
+		return;
+
+	frame = last_frame(stack);
+	frame->insn = insn;
+	frame = alloc_frame(ep, NULL);
+	add_frame(&stack, frame);
+
+	if (dbg_level0)
+		printf("%*scall %s\n", level * 2, "",
+			show_ident(ep->name->ident));
+	level++;
+	if (dbg_level2)
+		show_call_stack(stack, level);
+
+	update_locks_on_entry(lset, ep, stack, level);
+	check_bb(ep->entry->bb, lset, stack, ++bb_generation, level);
+	update_locks_on_exit(lset, ep, stack, level);
+	level--;
+
+	if (dbg_level0)
+		printf("%*sret %s\n", level * 2, "",
+			show_ident(ep->name->ident));
+
+	frame = delete_last_frame(&stack);
+	__free_frame(frame);
+}
+
+static void check_bb(struct basic_block *bb,
+		struct lock_list **lset, struct frame_list *stack,
+		unsigned long generation, int level)
+{
+	struct instruction *insn;
+	struct multijmp *mj;
+	struct symbol *sym;
+	struct bb_info *info = bb->priv;
+
+	if (!info) {
+		info = __alloc_bb_info(0);
+		bb->priv = info;
+	}
+
+	if (generation == bb->generation)
+		return;
+	bb->generation = generation;
+
+	if (dbg_level2)
+		printf("%*sentry bb %p\n", level * 2, "", bb);
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		switch (insn->opcode) {
+		case OP_CALL:
+			handle_call(insn, lset, stack, level);
+			break;
+		case OP_BR:
+			if (dbg_level2)
+				level++;
+
+			if (insn->bb_true)
+				check_bb(insn->bb_true, lset, stack,
+					 generation, level);
+			if (insn->bb_false)
+				check_bb(insn->bb_false, lset, stack,
+					 generation, level);
+			if (dbg_level2)
+				level--;
+			break;
+		case OP_SWITCH:
+		case OP_COMPUTEDGOTO:
+			/* Note this one might jump backwards, which means
+			 * we need to be careful and not endup in an endless
+			 * loop.
+			 */
+			if (dbg_level2)
+				level++;
+			FOR_EACH_PTR(insn->multijmp_list, mj) {
+				check_bb(mj->target, lset, stack,
+					 generation, level);
+			} END_FOR_EACH_PTR(mj);
+			if (dbg_level2)
+				level--;
+			break;
+
+		case OP_LOAD:
+		case OP_STORE:
+			sym = figure_access(insn->src, stack);
+			if (dbg_level1)
+				printf("%*sld/st: %p %s\n", level * 2, "",
+					sym, sym ? show_ident(sym->ident) : "");
+			if (sym)
+				check_sym_access(insn, sym, bb, *lset, stack);
+			break;
+		}
+	} END_FOR_EACH_PTR(insn);
+
+	if (dbg_level2)
+		printf("%*sexit  bb %p\n", level * 2, "", bb);
+}
+
+static void check_entrypoint(struct entrypoint *ep)
+{
+	struct frame_list *stack;
+	struct frame *frame;
+	struct lock_list *lset = NULL;
+	struct bb_info *info = ep->entry->bb->priv;
+	int level = 0;
+
+	if (!info) {
+		info = __alloc_bb_info(0);
+		ep->entry->bb->priv = info;
+	}
+
+	stack = NULL;
+	frame = alloc_frame(ep, NULL);
+	add_frame(&stack, frame);
+
+	update_locks_on_entry(&lset, ep, stack, level);
+	check_bb(ep->entry->bb, &lset, stack, ++bb_generation, level);
+	update_locks_on_exit(&lset, ep, stack, level);
+
+	frame = delete_last_frame(&stack);
+	__free_frame(frame);
+}
+
+DECLARE_PTR_LIST(entrypoint_list, struct entrypoint);
+
+static inline void add_entrypoint(struct entrypoint_list **list,
+				  struct entrypoint *ep)
+{
+	add_ptr_list(list, ep);
+}
+
+static void check_symbols(struct symbol_list *list)
+{
+	struct entrypoint_list *eps = NULL;
+	struct entrypoint *ep;
+	struct symbol *sym;
+
+	/* First pass collect all locks */
+	FOR_EACH_PTR(list, sym) {
+		expand_symbol(sym);
+		ep = linearize_symbol(sym);
+		if (ep) {
+			if (dbg_level0)
+				printf("\n## %s()\n",
+					show_ident(ep->name->ident));
+
+			/* Call each function and collect all locks
+			 * taken at entry and exit point of function.
+			 */
+			check_entrypoint(ep);
+
+			add_entrypoint(&eps, ep);
+		}
+	} END_FOR_EACH_PTR(sym);
+
+	FOR_EACH_PTR(eps, ep) {
+		if (dbg_level3) {
+			printf("\n## %s()\n",
+				show_ident(ep->name->ident));
+			show_entrypoint(ep);
+			printf("\n");
+		}
+
+		check_leaking(ep);
+	} END_FOR_EACH_PTR(ep);
+}
+
+int main(int argc, char **argv)
+{
+	struct string_list *filelist = NULL;
+	char *file;
+
+	add_pre_buffer("#define __TESTLOCK__ 1\n");
+
+	check_symbols(sparse_initialize(argc, argv, &filelist));
+	FOR_EACH_PTR_NOTAG(filelist, file) {
+		check_symbols(sparse(file));
+	} END_FOR_EACH_PTR_NOTAG(file);
+
+#if 0
+	show_frame_alloc();
+	show_lock_alloc();
+#endif
+	return 0;
+}
diff --git a/validation/caps.c b/validation/caps.c
new file mode 100644
index 0000000..0ffa407
--- /dev/null
+++ b/validation/caps.c
@@ -0,0 +1,80 @@
+#define __must_hold(x)	__attribute__((requires_capability(x)))
+#define __acquires(x)	__attribute__((acquire_capability(x)))
+#define __releases(x)	__attribute__((release_capability(x)))
+#define __guarded_by(x)	__attribute__((guarded_by(x)))
+
+static void a(void) __acquires()
+{
+}
+
+static void r(void) __releases()
+{
+}
+
+static void good1(void)
+{
+	a();
+	r();
+}
+
+static void okay1(void)
+{
+	a();
+}
+
+static void bad2(void)
+{
+	okay1();
+}
+
+struct hello {
+	char *str;
+	int lock;
+};
+
+static struct hello info __guarded_by(info.lock);
+
+static void wtf_lock(int *lock)
+	__acquires(lock)
+{
+	*lock = 1;
+}
+
+static void wtf_unlock(int *lock)
+	__releases(lock)
+{
+	*lock = 0;
+}
+
+static void set_str(struct hello *h)
+	__must_hold(h->lock)
+{
+	h->str = "hello";
+}
+
+static good2(void)
+{
+	wtf_lock(&info.lock);
+	set_str(&info);
+	wtf_unlock(&info.lock);
+}
+
+static int global_lock;
+
+static good3(void)
+{
+	wtf_lock(&global_lock);
+	wtf_unlock(&global_lock);
+}
+
+static bad4(void)
+{
+	wtf_lock(&global_lock);
+}
+
+/*
+ * check-name: Check capabilities
+ *
+ * check-error-start
+ * check-error-end
+ */
-- 
2.5.0

Re: [FAIL 0/5] Static lock analysis

[Christopher Li]

On Wed, Feb 17, 2016 at 1:51 AM, Daniel Wagner
<daniel.wagner@bmw-carit.de> wrote:
>
> Maybe the first 3 patches might be okay to get merged.

Yes, the first 3 looks simple and obvious correct.

Chris