make sparse keep its promise about context tracking

The sparse man page promises that it will check this:

   Functions with the extended attribute
	__attribute__((context(expression,in_context,out_context))
   require the context expression (for instance, a lock) to have the
   value in_context (a constant nonnegative integer) when called,
   and return with the value out_context (a constant nonnegative
   integer).

It doesn't keep that promise though, nor can it, especially with
contexts that can be acquired recursively (like RCU in the kernel.)

This patch makes sparse track different contexts, and also follows
up on that promise, but with slightly different semantics:

  * the "require the context to have the value" is changed to require
    it to have /at least/ the value if 'in_context',
  * an exact_context(...) attribute is introduced with the previously
    described semantics (to be used for non-recursive contexts),
  * the __context__ statement is extended to also include a required
    context argument (same at least semantics),

Unfortunately, I wasn't able to keep the same output, so now you'll
see different messages from sparse, especially when trying to unlock
a lock that isn't locked you'll see a message pointing to the unlock
function rather than complaining about the basic block, you can see
that in the test suite changes.

This patch also contains test updates and a lot of new tests for the
new functionality. Except for the changed messages, old functionality
should not be affected.

However, the kernel use of __attribute__((context(...)) is actually
wrong, the kernel often does things like:

    static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos)
            __acquires(dev_base_lock)
    {
            [...]
            read_lock(&dev_base_lock);
            [...]
    }

rather than

    static void *dev_mc_seq_start(struct seq_file *seq, loff_t * pos)
            __acquires(dev_base_lock)
    {
            [...]
            __acquire__(dev_base_lock);
            read_lock(&dev_base_lock);
            [...]
    }

(and possibly more when read_lock() is annotated appropriately, such
as dropping whatever context read_lock() returns to convert the context
to the dev_base_lock one.)

Currently, sparse doesn't care, but if it's going to check the context
of functions contained within another function then we need to put the
actual __acquire__ together with acquiring the context.

The great benefit of this patch is that you can now document at least
some locking assumptions in a machine-readable way:

before:
    /* requires mylock held */
    static void myfunc(void)
    {...}

after:
    static void myfunc(void)
            __requires(mylock)
    {...}

where, for sparse,
    #define __requires(x) __attribute__((context(x,1,1)))

Doing so may result in lots of other functions that need to be annoated
along with it because they also have the same locking requirements, but
ultimately sparse can check a lot of locking assumptions that way.

I have already used this patch and identify a number of kernel bugs by
marking things to require certain locks or RCU-protection and checking
sparse output. To do that, you need a few kernel patches which I'll
send separately.

Signed-off-by: Johannes Berg <johannes@sipsolutions.net>

1 files changed, 161 insertions, 48 deletions

diff --git a/sparse.c b/sparse.c
index 4026ba7..de5a309 100644
--- a/sparse.c
+++ b/sparse.c
@@ -24,77 +24,184 @@
 #include "expression.h"
 #include "linearize.h"
 
-static int context_increase(struct basic_block *bb, int entry)
+struct context_check {
+	int val;
+	char name[32];
+};
+
+DECLARE_ALLOCATOR(context_check);
+DECLARE_PTR_LIST(context_check_list, struct context_check);
+ALLOCATOR(context_check, "context check list");
+
+static const char *unnamed_context = "<unnamed>";
+
+static const char *context_name(struct context *context)
 {
-	int sum = 0;
-	struct instruction *insn;
+	if (context->context && context->context->symbol_name)
+		return show_ident(context->context->symbol_name);
+	return unnamed_context;
+}
 
-	FOR_EACH_PTR(bb->insns, insn) {
-		int val;
-		if (insn->opcode != OP_CONTEXT)
-			continue;
-		val = insn->increment;
-		if (insn->check) {
-			int current = sum + entry;
-			if (!val) {
-				if (!current)
-					continue;
-			} else if (current >= val)
-				continue;
-			warning(insn->pos, "context check failure");
+static void context_add(struct context_check_list **ccl, const char *name, int offs)
+{
+	struct context_check *check, *found = NULL;
+
+	FOR_EACH_PTR(*ccl, check) {
+		if (strcmp(name, check->name))
 			continue;
-		}
-		sum += val;
-	} END_FOR_EACH_PTR(insn);
-	return sum;
+		found = check;
+		break;
+	} END_FOR_EACH_PTR(check);
+
+	if (!found) {
+		found = __alloc_context_check(0);
+		strncpy(found->name, name, sizeof(found->name));
+		found->name[sizeof(found->name) - 1] = '\0';
+		add_ptr_list(ccl, found);
+	}
+	found->val += offs;
 }
 
-static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
+static int imbalance(struct entrypoint *ep, struct position pos, const char *name, const char *why)
 {
 	if (Wcontext) {
 		struct symbol *sym = ep->name;
-		warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
+		if (strcmp(name, unnamed_context))
+			warning(pos, "context imbalance in '%s' - %s (%s)", show_ident(sym->ident), why, name);
+		else
+			warning(pos, "context imbalance in '%s' - %s", show_ident(sym->ident), why);
 	}
 	return -1;
 }
 
-static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
+static int context_list_check(struct entrypoint *ep, struct position pos,
+			      struct context_check_list *ccl_cur,
+			      struct context_check_list *ccl_target)
+{
+	struct context_check *c1, *c2;
+	int cur, tgt;
+
+	/* make sure the loop below checks all */
+	FOR_EACH_PTR(ccl_target, c1) {
+		context_add(&ccl_cur, c1->name, 0);
+	} END_FOR_EACH_PTR(c1);
 
-static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
+	FOR_EACH_PTR(ccl_cur, c1) {
+		cur = c1->val;
+		tgt = 0;
+
+		FOR_EACH_PTR(ccl_target, c2) {
+			if (strcmp(c2->name, c1->name))
+				continue;
+			tgt = c2->val;
+			break;
+		} END_FOR_EACH_PTR(c2);
+
+		if (cur > tgt)
+			return imbalance(ep, pos, c1->name, "wrong count at exit");
+		else if (cur < tgt)
+			return imbalance(ep, pos, c1->name, "unexpected unlock");
+	} END_FOR_EACH_PTR(c1);
+
+	return 0;
+}
+
+static int check_bb_context(struct entrypoint *ep, struct basic_block *bb,
+			    struct context_check_list *ccl_in,
+			    struct context_check_list *ccl_target)
 {
+	struct context_check_list *combined = NULL;
+	struct context_check *c;
 	struct instruction *insn;
 	struct basic_block *child;
+	struct context *ctx;
+	const char *name;
+	int ok, val;
+
+	/* recurse in once to catch bad loops */
+	if (bb->context > 0)
+		return 0;
+
+	bb->context++;
+
+	FOR_EACH_PTR(ccl_in, c) {
+		context_add(&combined, c->name, c->val);
+	} END_FOR_EACH_PTR(c);
+
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (!insn->bb)
+			continue;
+		switch (insn->opcode) {
+		case OP_CALL:
+			if (!insn->func || !insn->func->sym || insn->func->type != PSEUDO_SYM)
+				break;
+			FOR_EACH_PTR(insn->func->sym->ctype.contexts, ctx) {
+				name = context_name(ctx);
+				val = 0;
+
+				FOR_EACH_PTR(combined, c) {
+					if (strcmp(c->name, name) == 0) {
+						val = c->val;
+						break;
+					}
+				} END_FOR_EACH_PTR(c);
+
+				if (ctx->exact)
+					ok = ctx->in == val;
+				else
+					ok = ctx->in <= val;
+
+				if (!ok) {
+					const char *call = strdup(show_ident(insn->func->ident));
+					warning(insn->pos, "context problem in '%s' - function '%s' expected different context",
+						show_ident(ep->name->ident), call);
+					free((void *)call);
+					return -1;
+				}
+			} END_FOR_EACH_PTR (ctx);
+			break;
+		case OP_CONTEXT:
+			val = 0;
+
+			name = unnamed_context;
+			if (insn->context_expr)
+				name = show_ident(insn->context_expr->symbol_name);
+
+			FOR_EACH_PTR(combined, c) {
+				if (strcmp(c->name, name) == 0) {
+					val = c->val;
+					break;
+				}
+			} END_FOR_EACH_PTR(c);
+
+			ok = insn->required <= val;
+
+			if (!ok) {
+				name = strdup(name);
+				imbalance(ep, insn->pos, name, "__context__ statement expected different lock context");
+				free((void *)name);
+				return -1;
+			}
+			context_add(&combined, name, insn->increment);
+			break;
+		}
+	} END_FOR_EACH_PTR(insn);
 
 	insn = last_instruction(bb->insns);
 	if (!insn)
 		return 0;
 	if (insn->opcode == OP_RET)
-		return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at exit") : 0;
+		return context_list_check(ep, insn->pos, combined, ccl_target);
 
 	FOR_EACH_PTR(bb->children, child) {
-		if (check_bb_context(ep, child, entry, exit))
+		if (check_bb_context(ep, child, combined, ccl_target))
 			return -1;
 	} END_FOR_EACH_PTR(child);
-	return 0;
-}
 
-static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
-{
-	if (!bb)
-		return 0;
-	if (bb->context == entry)
-		return 0;
+	/* contents will be freed once we return out of recursion */
+	free_ptr_list(&combined);
 
-	/* Now that's not good.. */
-	if (bb->context >= 0)
-		return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
-
-	bb->context = entry;
-	entry += context_increase(bb, entry);
-	if (entry < 0)
-		return imbalance(ep, bb, entry, exit, "unexpected unlock");
-
-	return check_children(ep, bb, entry, exit);
+	return 0;
 }
 
 static void check_cast_instruction(struct instruction *insn)
@@ -235,7 +342,7 @@ static void check_context(struct entrypoint *ep)
 {
 	struct symbol *sym = ep->name;
 	struct context *context;
-	unsigned int in_context = 0, out_context = 0;
+	struct context_check_list *ccl_in = NULL, *ccl_target = NULL;
 
 	if (Wuninitialized && verbose && ep->entry->bb->needs) {
 		pseudo_t pseudo;
@@ -249,10 +356,16 @@ static void check_context(struct entrypoint *ep)
 	check_instructions(ep);
 
 	FOR_EACH_PTR(sym->ctype.contexts, context) {
-		in_context += context->in;
-		out_context += context->out;
+		const char *name = context_name(context);
+
+		context_add(&ccl_in, name, context->in);
+		context_add(&ccl_target, name, context->out);
 	} END_FOR_EACH_PTR(context);
-	check_bb_context(ep, ep->entry->bb, in_context, out_context);
+
+	check_bb_context(ep, ep->entry->bb, ccl_in, ccl_target);
+	free_ptr_list(&ccl_in);
+	free_ptr_list(&ccl_target);
+	clear_context_check_alloc();
 }
 
 static void check_symbols(struct symbol_list *list)