improve context handling

PATCH In review Johannes Berg 3 participants 26 messages Apr 10, 2008 – Apr 21, 2008 Sparse checker

lore

Share & tools

lore

Johannes Berg

author

2008-04-10 14:41 UTC #0 lore raw

cover improve context handling

Hi,

Here are three patches to improve context tracking in sparse. For example, with the patches, one could define

spin_lock_irqsave() __acquires(local_irq) __acquires(spinlock) spin_unlock_irqrestore() __releases(local_irq) __releases(spinlock)

local_irq_save() __acquires(local_irq)
local_irq_restore() __releases(local_irq)

spin_lock() __acquires(spinlock)
spin_unlock() __releases(spinlock)

spin_trylock() __attribute__((conditional_context(spinlock,0,1,0)))

and sparse should be able to check constructs like the one in sungem completely:

        local_irq_save(flags);
        if (!spin_trylock(&gp->tx_lock)) {
                /* Tell upper layer to requeue */
                local_irq_restore(flags);
                return ...;
        }
        if (..) {
                spin_unlock_irqrestore(&gp->tx_lock, flags);
                return ...;
        }
        [...]
        spin_unlock_irqrestore(&gp->tx_lock, flags);

I haven't tried this particular case, but I have tried simpler versions of all the primivites used, those are in the test suite.

Also, one can now define, as the sparse man page already suggests without patches:

/* needs irqs disabled */
void myfunc(void) __attribute__((context(local_irq,1,1))) {...}

and sparse will warn when the function is called from a context that doesn't have local_irq. Of course, if the context comes from outside the calling function then the calling function needs to use that attribute as well to indicate that it too needs irqs disabled.

Comments welcome!

johannes

Johannes Berg

author

2008-04-10 14:41 UTC #1 lore raw

PATCH 1/3 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 <[email protected]>

---
 inline.c                       |   12 
 linearize.c                    |   10 
 linearize.h                    |    2 
 parse.c                        |   82 +++++-
 parse.h                        |    3 
 sparse.1                       |   32 +-
 sparse.c                       |  209 +++++++++++++----
 symbol.h                       |    1 
 validation/context-named.c     |  496 +++++++++++++++++++++++++++++++++++++++++
 validation/context-statement.c |   58 ++++
 validation/context.c           |   40 ++-
 11 files changed, 860 insertions(+), 85 deletions(-)

sparse.c +161 ~~-48~~

@@ -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);
+
+	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);
 
-static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
+	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 entrypo
 {
 	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 entrypo
 	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)

validation/context.c +26 ~~-14~~

@@ -314,23 +314,35 @@ static void warn_cond_lock1(void)
         condition2 = 1; /* do stuff */
     r();
 }
+
+static void warn_odd_looping(void)
+{
+    int i;
+
+    for (i = 0; i < 2; i++)
+        a();
+    for (i = 0; i < 2; i++)
+        r();
+}
+
 /*
  * check-name: Check -Wcontext
  *
  * check-error-start
-context.c:69:13: warning: context imbalance in 'warn_lock1' - wrong count at exit
-context.c:74:13: warning: context imbalance in 'warn_lock2' - wrong count at exit
-context.c:81:13: warning: context imbalance in 'warn_lock3' - wrong count at exit
-context.c:88:13: warning: context imbalance in 'warn_unlock1' - unexpected unlock
-context.c:93:13: warning: context imbalance in 'warn_unlock2' - unexpected unlock
-context.c:131:12: warning: context imbalance in 'warn_if1' - wrong count at exit
-context.c:140:12: warning: context imbalance in 'warn_if2' - different lock contexts for basic block
-context.c:202:2: warning: context imbalance in 'warn_while1' - different lock contexts for basic block
-context.c:210:3: warning: context imbalance in 'warn_while2' - unexpected unlock
-context.c:216:2: warning: context imbalance in 'warn_while3' - wrong count at exit
-context.c:274:13: warning: context imbalance in 'warn_goto1' - wrong count at exit
-context.c:283:13: warning: context imbalance in 'warn_goto2' - wrong count at exit
-context.c:300:5: warning: context imbalance in 'warn_goto3' - different lock contexts for basic block
-context.c:315:5: warning: context imbalance in 'warn_cond_lock1' - different lock contexts for basic block
+context.c:71:3: warning: context imbalance in 'warn_lock1' - wrong count at exit
+context.c:78:3: warning: context imbalance in 'warn_lock2' - wrong count at exit
+context.c:85:3: warning: context imbalance in 'warn_lock3' - wrong count at exit
+context.c:90:3: warning: context problem in 'warn_unlock1' - function 'r' expected different context
+context.c:97:3: warning: context problem in 'warn_unlock2' - function 'r' expected different context
+context.c:137:9: warning: context imbalance in 'warn_if1' - wrong count at exit
+context.c:147:9: warning: context imbalance in 'warn_if2' - wrong count at exit
+context.c:203:4: warning: context imbalance in 'warn_while1' - wrong count at exit
+context.c:210:4: warning: context problem in 'warn_while2' - function 'r' expected different context
+context.c:220:4: warning: context imbalance in 'warn_while3' - wrong count at exit
+context.c:280:5: warning: context imbalance in 'warn_goto1' - wrong count at exit
+context.c:290:6: warning: context imbalance in 'warn_goto2' - wrong count at exit
+context.c:300:6: warning: context problem in 'warn_goto3' - function 'r' expected different context
+context.c:315:6: warning: context problem in 'warn_cond_lock1' - function 'r' expected different context
+context.c:325:10: warning: context problem in 'warn_odd_looping' - function 'r' expected different context
  * check-error-end
  */

parse.c +72 ~~-10~~

134 lines not on this page · raw message

symbol.h +1 -0

@@ -72,6 +72,7 @@ enum keyword {
 struct context {
 	struct expression *context;
 	unsigned int in, out;
+	int exact;
 };
 
 extern struct context *alloc_context(void);

sparse.1 +23 -9

@@ -73,20 +73,34 @@ Warn about potential errors in synchroni
 Sparse supports several means of designating functions or statements that
 delimit contexts, such as synchronization.  Functions with the extended
 attribute
-.BI __attribute__((context( expression , in_context , out_context ))
-require the context \fIexpression\fR (for instance, a lock) to have the value
+.BI __attribute__((context( [expression ,] in_context , out_context ))
+require the context \fIexpression\fR (for instance, a lock) to have at least the value
 \fIin_context\fR (a constant nonnegative integer) when called, and return with
-the value \fIout_context\fR (a constant nonnegative integer).  For APIs
-defined via macros, use the statement form
-.BI __context__( expression , in_value , out_value )
-in the body of the macro.
+the value adjusted by \fIout_context - in_context\fR (where
+\fIout_context\fR is a constant nonnegative integer).  To change the value
+of a context (for example in macros), use the statement
+.BI __context__( [expression , ]adjust_value[ , required] )
+where \fIadjust_value\fR is a constant integer and \fIrequired\fR is a
+constant nonnegative integer. Not giving \fIrequired\fR is equivalent to
+giving zero and means that the statement does not need the context as a
+precondition, when given it means that the context must at least have the
+value of \fIrequired\fR.
+
+To indicate that a function requires
+.BI exactly
+a certain lock context (not "at least" as above), use the form
+.BI __attribute__((exact_context( [expression ,] in_context , out_context ))
+There currently is no corresponding
+.BI __exact_context__( [expression , ]adjust_value[ , required] )
+statement.
 
-With \fB-Wcontext\fR Sparse will warn when it sees a function change the
-context without indicating this with a \fBcontext\fR attribute, either by
+Sparse will warn when it sees a function change a
+context without indicating this with a \fBcontext\fR or \fBexact_context\fR attribute, either by
 decreasing a context below zero (such as by releasing a lock without acquiring
 it), or returning with a changed context (such as by acquiring a lock without
 releasing it).  Sparse will also warn about blocks of code which may
-potentially execute with different contexts.
+potentially execute with different contexts and about functions that are
+executed without a lock they require.
 
 Sparse issues these warnings by default.  To turn them off, use
 \fB\-Wno\-context\fR.

inline.c +10 -2

@@ -331,10 +331,18 @@ static struct statement *copy_one_statem
 	case STMT_CONTEXT:
 	case STMT_EXPRESSION: {
 		struct expression *expr = copy_expression(stmt->expression);
+		struct statement *newstmt;
 		if (expr == stmt->expression)
 			break;
-		stmt = dup_statement(stmt);
-		stmt->expression = expr;
+		newstmt = dup_statement(stmt);
+		newstmt->expression = expr;
+		if (stmt->required) {
+			expr = copy_expression(stmt->required);
+			if (expr == stmt->required)
+				break;
+			newstmt->required = expr;
+		}
+		stmt = newstmt;
 		break;
 	}
 	case STMT_RANGE: {

linearize.c +10 -0

@@ -1247,6 +1247,7 @@ static pseudo_t linearize_call_expressio
 			if (check || context_diff) {
 				insn = alloc_instruction(OP_CONTEXT, 0);
 				insn->increment = context_diff;
+				/* what's check for? */
 				insn->check = check;
 				insn->context_expr = context->context;
 				add_one_insn(ep, insn);

@@ -1683,6 +1684,15 @@ static pseudo_t linearize_context(struct
 		value = expr->value;
 
 	insn->increment = value;
+
+	expr = stmt->required;
+	value = 0;
+
+	if (expr && expr->type == EXPR_VALUE)
+		value = expr->value;
+
+	insn->required = value;
+
 	insn->context_expr = stmt->context;
 	add_one_insn(ep, insn);
 	return VOID;

linearize.h +1 -1

@@ -116,7 +116,7 @@ struct instruction {
 			struct pseudo_list *arguments;
 		};
 		struct /* context */ {
-			int increment;
+			int increment, required;
 			int check;
 			struct expression *context_expr;
 		};

parse.h +2 -1

@@ -39,9 +39,10 @@ struct statement {
 			struct symbol *label;
 			struct statement *label_statement;
 		};
-		struct {
+		struct { /* __context__ */
 			struct expression *expression;
 			struct expression *context;
+			struct expression *required;
 		};
 		struct /* return_statement */ {
 			struct expression *ret_value;

validation/context-statement.c new file +58 -0

58 lines not on this page · raw message

validation/context-named.c new file +496 -0

496 lines not on this page · raw message

Philipp Reisner

2008-04-10 15:24 UTC #2 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Am Donnerstag, 10. April 2008 15:25:20 schrieb Johannes Berg:

Quoted 9 lines

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).

Quoted 3 lines

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

Hi Josh,
Hi Johannes,

I just have implemented nearly the same here. Hopefully Josh will decide for one of these patches soon.

expression.c +0 -0

index 289927a..00cfb00 100644
@@ -929,4 +929,76 @@ struct token *parse_expression(struct token *token,

struct expression **tree)
return comma_expression(token,tree);
}

+int ident_equal(struct ident *ident1, struct ident *ident2) +{
+ return ident1->len == ident2->len &&
+ !strncmp(ident1->name, ident2->name, ident1->len);
+}
+
+int expressions_equal(struct expression *expr1, struct expression *expr2) +{
+ if (expr1 == expr2)
+ return 1;
+
+ if (expr1 == NULL || expr2 == NULL)
+ return 0;
+
+ if (expr1->type != expr2->type)
+ return 0;
+
+ switch (expr1->type) {
+ case EXPR_SYMBOL:
+ return ident_equal(expr1->symbol_name, expr2->symbol_name);
+
+ case EXPR_VALUE:
+ return expr1->value == expr2->value;
+
+ case EXPR_FVALUE:
+ return expr1->fvalue == expr2->fvalue;
+
+ case EXPR_STRING:
+ return expr1->string->length == expr2->string->length &&
+ !strncmp(expr1->string->data, expr2->string->data, expr1->string->length);
+
+ case EXPR_BINOP:
+ return expr1->op == expr2->op &&
+ expressions_equal(expr1->left, expr2->left) &&
+ expressions_equal(expr1->right, expr2->right);
+
+ case EXPR_COMMA:
+ case EXPR_ASSIGNMENT:
+ return expressions_equal(expr1->left, expr2->left) &&
+ expressions_equal(expr1->right, expr2->right);
+
+ case EXPR_DEREF:
+ return expressions_equal(expr1->deref, expr2->deref) &&
+ ident_equal(expr1->member, expr2->member);
+
+ case EXPR_PREOP:
+ case EXPR_POSTOP:
+ return expr1->op == expr2->op &&
+ expressions_equal(expr1->unop, expr2->unop);
+
+ /* Not needed right now, but for sake of completness ...
+ case EXPR_LABEL:
+ case EXPR_STATEMENT:
+ case EXPR_CALL:
+ case EXPR_LOGICAL:
+ case EXPR_COMPARE:
+ case EXPR_SELECT:
+ case EXPR_CONDITIONAL:
+ case EXPR_CAST:
+ case EXPR_FORCE_CAST:
+ case EXPR_IMPLIED_CAST:
+ case EXPR_SLICE:
+ case EXPR_INITIALIZER:
+ case EXPR_POS:
+ */
+
+ default:
+ printf("Missing code in expressions_equal for %d\n", expr1->type);
+ }
+
+ return 0;
+}

expression.h +0 -0

index 5136b9b..e89ddb7 100644
@@ -216,4 +216,5 @@ struct token *compound_statement(struct token *, struct

statement *);
void cast_value(struct expression *expr, struct symbol *newtype,
struct expression *old, struct symbol *oldtype);

+extern int expressions_equal(struct expression *expr1, struct expression *expr2);
#endif

linearize.c +0 -0

index 8a68f05..5aae3d6 100644
@@ -67,6 +67,7 @@ static struct basic_block *alloc_basic_block(struct

entrypoint *ep, struct posit
{
struct basic_block *bb = __alloc_basic_block(0); bb->context = -1;
+ bb->context_expr = NULL;
bb->pos = pos;
bb->ep = ep;
return bb;

linearize.h +1 -0

index 7b2961b..a71f9aa 100644
@@ -225,6 +225,7 @@ struct basic_block {
 	struct position pos;
 	unsigned long generation;
 	int context;
+	struct expression *context_expr;
 	struct entrypoint *ep;
 	struct basic_block_list *parents; /* sources */
 	struct basic_block_list *children; /* destinations */

sparse.c +30 -1

index 4026ba7..50c5e51 100644
@@ -24,7 +24,110 @@
 #include "expression.h"
 #include "linearize.h"
 
-static int context_increase(struct basic_block *bb, int entry)
+
+int ident_str(struct ident *ident, char *buffer, int length)
+{
+	return snprintf(buffer, length, "%.*s", ident->len, ident->name);
+}
+
+
+int expression_str(struct expression *expr, char *buffer, int length)
+{
+	int n;
+
+	if (!expr) {
+		buffer[0] = 0;
+		return 0;
+	}
+
+	/* TODO, think about necessary braces () */
+
+	switch (expr->type) {
+	case EXPR_SYMBOL:
+		return ident_str(expr->symbol_name, buffer, length);
+
+	case EXPR_VALUE:
+		return snprintf(buffer, length, "%llu", expr->value);
+
+	case EXPR_FVALUE:
+		return snprintf(buffer, length, "%Lf", expr->fvalue);
+
+	case EXPR_STRING:
+		return snprintf(buffer, length, "%.*s", expr->string->length,

expr->string->data);
+
+ case EXPR_BINOP:
+ n = expression_str(expr->left, buffer, length);
+ n += snprintf(buffer+n, length-n, "%c", expr->op);
+ n += expression_str(expr->right, buffer+n, length-n);
+ return n;
+
+ case EXPR_COMMA:
+ n = expression_str(expr->left, buffer, length);
+ n += snprintf(buffer+n, length-n, ",");
+ n += expression_str(expr->right, buffer+n, length-n);
+ return n;
+
+ case EXPR_ASSIGNMENT:
+ n = expression_str(expr->left, buffer, length);
+ n += snprintf(buffer+n, length-n, "=");
+ n += expression_str(expr->right, buffer+n, length-n);
+ return n;
+
+ case EXPR_DEREF:
+ if (expr->left->type == EXPR_PREOP &&
+ expr->left->op == '*') {
+ n = expression_str(expr->left->unop, buffer, length);
+ n += snprintf(buffer+n, length-n, "->");
+ n += ident_str(expr->member, buffer+n, length-n);
+ } else {
+ n = expression_str(expr->left, buffer, length);
+ n += snprintf(buffer+n, length-n, ".");
+ n += ident_str(expr->member, buffer+n, length-n);
+ }
+ return n;
+
+ case EXPR_PREOP:
+ n = snprintf(buffer, length, "%c", expr->op);
+ n += expression_str(expr->unop, buffer+n, length-n);
+ return n;
+
+ case EXPR_POSTOP:
+ n = expression_str(expr->unop, buffer, length);
+ n += snprintf(buffer+n, length-n, "%c", expr->op);
+ return n;
+
+ /* Not needed right now, but for sake of completness ...
+ case EXPR_LABEL:
+ case EXPR_STATEMENT:
+ case EXPR_CALL:
+ case EXPR_LOGICAL:
+ case EXPR_COMPARE:
+ case EXPR_SELECT:
+ case EXPR_CONDITIONAL:
+ case EXPR_CAST:
+ case EXPR_FORCE_CAST:
+ case EXPR_IMPLIED_CAST:
+ case EXPR_SLICE:
+ case EXPR_INITIALIZER:
+ case EXPR_POS:
+ */
+
+ default:
+ printf("Missing code in expression_str for %d\n", expr->type);
+ }
+
+ return 0;
+}
+
+char *expression_sstr(struct expression *expr)
+{
+ static char expr_string[37] = " for ";
+ static char empty[] = "";
+
+ return expression_str(expr, expr_string+5, 32) ? expr_string : empty;
+}
+
+static int context_increase(struct basic_block *bb, struct expression *expr, int entry)
{
int sum = 0;
struct instruction *insn;
@@ -33,6 +136,8 @@ static int context_increase(struct basic_block *bb, int entry)
int val;
if (insn->opcode != OP_CONTEXT)
continue;
+ if (!expressions_equal(expr, insn->context_expr))
+ continue;
val = insn->increment;
if (insn->check) {
int current = sum + entry;
@@ -49,18 +154,19 @@ static int context_increase(struct basic_block *bb, int entry)
return sum;
}

-static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
+static int imbalance(struct basic_block *bb, struct expression *expr, int entry, int exit, const char *why)
{
if (Wcontext) {
- struct symbol *sym = ep->name;
- warning(bb->pos, "context imbalance in '%s' - %s", show_ident(sym->ident),
why);
+ struct symbol *sym = bb->ep->name;
+ warning(bb->pos, "context imbalance in '%s' - %s%s",
show_ident(sym->ident), why,
+ expression_sstr(expr));
}
return -1;
}

-static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int entry, int exit);
+static int check_bb_context(struct basic_block *bb, struct expression *expr, int entry, int exit);

-static int check_children(struct entrypoint *ep, struct basic_block *bb, int entry, int exit)
+static int check_children(struct basic_block *bb, struct expression *expr, int entry, int exit)
{
struct instruction *insn;
struct basic_block *child;
@@ -69,32 +175,36 @@ static int check_children(struct entrypoint *ep, struct basic_block *bb, int ent
if (!insn)
return 0;
if (insn->opcode == OP_RET)
- return entry != exit ? imbalance(ep, bb, entry, exit, "wrong count at
exit") : 0;
+ return entry != exit ? imbalance(bb, expr, entry, exit, "wrong count at
exit") : 0;

FOR_EACH_PTR(bb->children, child) {
- if (check_bb_context(ep, child, entry, exit))
+ if (check_bb_context(child, expr, entry, exit))
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)
+static int check_bb_context(struct basic_block *bb, struct expression *expr, int entry, int exit)
{
+ int eq;
+
if (!bb)
return 0;
- if (bb->context == entry)
+ eq = expressions_equal(expr, bb->context_expr);
+ if (eq && bb->context == entry)
return 0;

/* Now that's not good.. */
- if (bb->context >= 0)
- return imbalance(ep, bb, entry, bb->context, "different lock contexts for
basic block");
+ if (eq && bb->context >= 0)
+ return imbalance(bb, expr, entry, bb->context, "different lock contexts for
basic block");

bb->context = entry;
- entry += context_increase(bb, entry);
+ bb->context_expr = expr;
+ entry += context_increase(bb, expr, entry);
if (entry < 0)
- return imbalance(ep, bb, entry, exit, "unexpected unlock");
+ return imbalance(bb, expr, entry, exit, "unexpected unlock");

- return check_children(ep, bb, entry, exit);
+ return check_children(bb, expr, entry, exit);
}

static void check_cast_instruction(struct instruction *insn)
@@ -195,7 +305,31 @@ static void check_call_instruction(struct instruction *insn)
}
}

-static void check_one_instruction(struct instruction *insn) +static void add_expression_once(struct expression_list **expr_list, struct expression* expr)
+{
+ struct expression *e;
+
+ FOR_EACH_PTR(*expr_list, e) {
+ if (expressions_equal(e, expr))
+ return;
+ } END_FOR_EACH_PTR(e);
+
+ add_expression(expr_list, expr);
+}
+
+static void remove_expression(struct expression_list **expr_list, struct expression* expr)
+{
+ struct expression *e;
+
+ FOR_EACH_PTR(*expr_list, e) {
+ if (expressions_equal(e, expr)) {
+ DELETE_CURRENT_PTR(e);
+ return;
+ }
+ } END_FOR_EACH_PTR(e);
+}
+
+static void check_one_instruction(struct instruction *insn, struct expression_list **expr_list)
{
switch (insn->opcode) {
case OP_CAST: case OP_SCAST:
@@ -208,26 +342,29 @@ static void check_one_instruction(struct instruction *insn)
case OP_CALL:
check_call_instruction(insn);
break;
+ case OP_CONTEXT:
+ add_expression_once(expr_list, insn->context_expr);
+ break;
default:
break;
}
}

-static void check_bb_instructions(struct basic_block *bb) +static void check_bb_instructions(struct basic_block *bb, struct expression_list **expr_list)
{
struct instruction *insn; FOR_EACH_PTR(bb->insns, insn) {
if (!insn->bb)
continue;
- check_one_instruction(insn);
+ check_one_instruction(insn, expr_list);
} END_FOR_EACH_PTR(insn);
}

-static void check_instructions(struct entrypoint *ep)
+static void check_instructions(struct entrypoint *ep, struct expression_list **expr_list)
{
struct basic_block *bb;
FOR_EACH_PTR(ep->bbs, bb) {
- check_bb_instructions(bb);
+ check_bb_instructions(bb, expr_list);
} END_FOR_EACH_PTR(bb);
}

@@ -235,7 +372,8 @@ static void check_context(struct entrypoint *ep)
{
struct symbol *sym = ep->name;
struct context *context;
- unsigned int in_context = 0, out_context = 0;
+ struct expression_list *expr_list = NULL;
+ struct expression *expr;

if (Wuninitialized && verbose && ep->entry->bb->needs) {
pseudo_t pseudo;
@@ -246,13 +384,16 @@ static void check_context(struct entrypoint *ep)
} END_FOR_EACH_PTR(pseudo);
}

- check_instructions(ep);
+ check_instructions(ep, &expr_list);

FOR_EACH_PTR(sym->ctype.contexts, context) {
- in_context += context->in;
- out_context += context->out;
+ remove_expression(&expr_list, context->context);
+ check_bb_context(ep->entry->bb, context->context, context->in,
context->out);
} END_FOR_EACH_PTR(context);
- check_bb_context(ep, ep->entry->bb, in_context, out_context);
+
+ FOR_EACH_PTR(expr_list, expr) {
+ check_bb_context(ep->entry->bb, expr, 0, 0);
+ } END_FOR_EACH_PTR(expr);
}

static void check_symbols(struct symbol_list *list)

validation/named_context.c new file +29 -0

new file mode 100644
index 0000000..9b6d77f
@@ -0,0 +1,32 @@
+#ifdef __CHECKER__
+# define __acquires(x)	__attribute__((context(x,0,1)))
+# define __releases(x)	__attribute__((context(x,1,0)))
+# define __acquire(x)	__context__(x,1)
+# define __release(x)	__context__(x,-1)
+#else
+# define __acquires(x)
+# define __releases(x)
+# define __acquire(x) (void)0
+# define __release(x) (void)0
+#endif
+
+static void invalid1(void)
+{
+	__acquire(lock1);
+	__release(lock2);
+}
+
+static void global_lock(void) __acquires(lock1) __acquires(lock2)
+{
+	__acquire(lock1);
+	__acquire(lock2);
+}
+
+/*
+ * check-name: Check -Wcontext
+ *
+ * check-error-start
+named_context.c:13:13: warning: context imbalance in 'invalid1' - wrong count

at exit for lock1
+named_context.c:13:13: warning: context imbalance in 'invalid1' - unexpected unlock for lock2
+ * check-error-end
+ */

Signature · 3 lines

: Dipl-Ing Philipp Reisner                      Tel +43-1-8178292-50 :
: LINBIT Information Technologies GmbH          Fax +43-1-8178292-82 :
: Vivenotgasse 48, 1120 Vienna, Austria        http://www.linbit.com :

Johannes Berg

author

2008-04-10 15:31 UTC #3 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Hi Philip,

Review

Quoted 7 lines

I just have implemented nearly the same here. Hopefully Josh will decide for one of these patches soon.
(quoted diff) +2 -0
+int ident_equal(struct ident *ident1, struct ident *ident2)
 
+int expressions_equal(struct expression *expr1, struct expression *expr2)

That code looks pretty nice, I guess I should look at getting that into my version instead of just printing the identifier to a string.

As far as I can see your version doesn't actually implement __attribute__((context(x,1,1))) as the man-page envisioned it for checking that a function is run under the lock context it wants, which was one of the more important goals to me. Doing separate locks sort of fell out.

johannes

Philipp Reisner

2008-04-10 15:46 UTC #4 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Am Donnerstag, 10. April 2008 17:30:54 schrieb Johannes Berg:

Quoted 14 lines

Hi Philip,
Quoted 8 lines
I just have implemented nearly the same here. Hopefully Josh will decide for one of these patches soon.
(quoted diff) +2 -0
+int ident_equal(struct ident *ident1, struct ident *ident2)
 
+int expressions_equal(struct expression *expr1, struct expression
*expr2)
That code looks pretty nice, I guess I should look at getting that into my version instead of just printing the identifier to a string.

Quoted 6 lines

As far as I can see your version doesn't actually implement __attribute__((context(x,1,1))) as the man-page envisioned it for checking that a function is run under the lock context it wants, which was one of the more important goals to me. Doing separate locks sort of fell out.

Hi Johannes,

I also worked on that part, although I have to admitt that I did not got that part of the manpage. Instead I invented the require_context attribute.

Here is the second patch. It applies on top of the first one...

I hope that we get the good ideas of our two works combined and accepted into sparse...

-Phil

allocate.c +1 -0

index 5cc52a9..198297b 100644
@@ -114,6 +114,7 @@ void show_allocations(struct allocator_struct *x)
 ALLOCATOR(ident, "identifiers");
 ALLOCATOR(token, "tokens");
 ALLOCATOR(context, "contexts");
+ALLOCATOR(context_requirement, "context requirements");
 ALLOCATOR(symbol, "symbols");
 ALLOCATOR(expression, "expressions");
 ALLOCATOR(statement, "statements");

allocate.h +1 -0

index 9f1dc8c..8fa3efd 100644
@@ -65,6 +65,7 @@ extern void show_allocations(struct allocator_struct *);
 DECLARE_ALLOCATOR(ident);
 DECLARE_ALLOCATOR(token);
 DECLARE_ALLOCATOR(context);
+DECLARE_ALLOCATOR(context_requirement);
 DECLARE_ALLOCATOR(symbol);
 DECLARE_ALLOCATOR(expression);
 DECLARE_ALLOCATOR(statement);

linearize.c +52 -2

120 lines not on this page · raw message

linearize.h +6 -0

index a71f9aa..8901a82 100644
@@ -124,6 +124,11 @@ struct instruction {
 			const char *string;
 			struct asm_rules *asm_rules;
 		};
+		struct /* context_req */ {
+			int access_type;
+			struct context_requirement* ctx_req;
+		};
+
 	};
 };

@@ -212,6 +217,7 @@ enum opcode {
 
 	/* Sparse tagging (line numbers, context, whatever) */
 	OP_CONTEXT,
+	OP_CONTEXT_REQ,
 	OP_RANGE,
 
 	/* Needed to translate SSA back to normal form */

parse.c +77 -0

119 lines not on this page · raw message

sparse.c +42 ~~-15~~

89 lines not on this page · raw message

symbol.c +9 -0

index 7539817..4564843 100644
@@ -57,6 +57,11 @@ struct context *alloc_context(void)
 	return __alloc_context(0);
 }
 
+struct context_requirement *alloc_context_requirement(void)
+{
+	return __alloc_context_requirement(0);
+}
+
 struct symbol *alloc_symbol(struct position pos, int type)
 {
 	struct symbol *sym = __alloc_symbol(0);

@@ -201,6 +206,8 @@ static struct symbol *examine_base_type(struct symbol *sym)
 	sym->ctype.modifiers |= base_type->ctype.modifiers & MOD_PTRINHERIT;
 	concat_ptr_list((struct ptr_list *)base_type->ctype.contexts,
 			(struct ptr_list **)&sym->ctype.contexts);
+	concat_ptr_list((struct ptr_list *)base_type->ctype.ctx_reqs,
+			(struct ptr_list **)&sym->ctype.ctx_reqs);
 	if (base_type->type == SYM_NODE) {
 		base_type = base_type->ctype.base_type;
 		sym->ctype.base_type = base_type;

@@ -257,6 +264,8 @@ void merge_type(struct symbol *sym, struct symbol *base_type)
 	sym->ctype.modifiers |= (base_type->ctype.modifiers & ~MOD_STORAGE);
 	concat_ptr_list((struct ptr_list *)base_type->ctype.contexts,
 	                (struct ptr_list **)&sym->ctype.contexts);
+	concat_ptr_list((struct ptr_list *)base_type->ctype.ctx_reqs,
+			(struct ptr_list **)&sym->ctype.ctx_reqs);
 	sym->ctype.base_type = base_type->ctype.base_type;
 	if (sym->ctype.base_type->type == SYM_NODE)
 		merge_type(sym, sym->ctype.base_type);

symbol.h +9 -0

index 4362f9a..cdb2452 100644
@@ -74,14 +74,23 @@ struct context {
 	unsigned int in, out;
 };
 
+struct context_requirement {
+	struct expression *context;
+	unsigned int min, max;
+	enum { READ, WRITE, RDWR, CALL } access_type;
+};
+
 extern struct context *alloc_context(void);
+extern struct context_requirement *alloc_context_requirement(void);
 
 DECLARE_PTR_LIST(context_list, struct context);
+DECLARE_PTR_LIST(ctx_req_list, struct context_requirement);
 
 struct ctype {
 	unsigned long modifiers;
 	unsigned long alignment;
 	struct context_list *contexts;
+	struct ctx_req_list *ctx_reqs;
 	unsigned int as;
 	struct symbol *base_type;
 };

validation/context_requirement.c new file +185 -0

185 lines not on this page · raw message

Signature · 3 lines

: Dipl-Ing Philipp Reisner                      Tel +43-1-8178292-50 :
: LINBIT Information Technologies GmbH          Fax +43-1-8178292-82 :
: Vivenotgasse 48, 1120 Vienna, Austria        http://www.linbit.com :

Johannes Berg

author

2008-04-10 15:51 UTC #5 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 4 lines

I also worked on that part, although I have to admitt that I did not got that part of the manpage. Instead I invented the require_context attribute.

Heh.

Quoted 1 line

Here is the second patch. It applies on top of the first one...

I don't really have time to look through it right now, sorry.

Quoted 2 lines

I hope that we get the good ideas of our two works combined and accepted into sparse...

That would be good :)

validation/context_requirement.c line 10

Quoted 5 lines

validation/context_requirement.c new file +5 -0

+# define __cond_lock(x,c)	((c) ? ({ __acquire(x); 1; }) : 0)
+# define __protected_by(x)       __attribute__((require_context(x,1,1,"rdwr")))
+# define __protected_read_by(x)  __attribute__((require_context(x,1,1,"read")))
+# define __protected_write_by(x) __attribute__((require_context(x,1,1,"write")))
+# define __must_hold(x)       __attribute__((context(x,1,1), require_context(x,1,1,"call")))

What's this "rdwr" etc. for? And "call"? Also, how are you planning to handle nested contexts, where 1,1 doesn't cut it any >0,>0 is really more like what we need?

johannes

Philipp Reisner

2008-04-10 16:05 UTC #6 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Am Donnerstag, 10. April 2008 17:51:27 schrieb Johannes Berg:

Quoted 13 lines

Quoted 3 lines
I also worked on that part, although I have to admitt that I did not got that part of the manpage. Instead I invented the require_context attribute.
Heh.
Quoted 1 line
Here is the second patch. It applies on top of the first one...
I don't really have time to look through it right now, sorry.
Quoted 2 lines
I hope that we get the good ideas of our two works combined and accepted into sparse...

Quoted 8 lines

That would be good :)
What's this "rdwr" etc. for? And "call"? Also, how are you planning to handle nested contexts, where 1,1 doesn't cut it any >0,>0 is really more like what we need?

I also use it to check a recusive lock mechanism.

The sematics of what I implemented is:
You simply use the __attribute__((context(ctx,in,out))) to annotate the context changes of functions.

to annotate a variable, struct/union member or a function that a certain locking primitive is required for accessing it, you do it by

__attribute__((require_context(ctx,min,max,"type")))

ctx ... the expression that describes the locking primitive min ... the minimum of locks required of that locking primitive max ... the maximum allowed of locks of that locking primitive. type .. read, write, rdwr or call for the access type.

So you can express you need to hold this and that locking primitive to write to something. But an other locking primitive might be sufficient for reading that something.

The annotation for a variable foo protected by a recursive lock bar would be:

int foo __attribute__((require_context(bar,1,99999,"rdwr")))

PS: I just realized that there my e-mail client introduced linebreakes
in the first patch I posted. I will repost on request of course.

-Phil

Signature · 3 lines

: Dipl-Ing Philipp Reisner                      Tel +43-1-8178292-50 :
: LINBIT Information Technologies GmbH          Fax +43-1-8178292-82 :
: Vivenotgasse 48, 1120 Vienna, Austria        http://www.linbit.com :

Johannes Berg

author

2008-04-10 16:12 UTC #7 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 6 lines

I also use it to check a recusive lock mechanism.
The sematics of what I implemented is:
You simply use the __attribute__((context(ctx,in,out))) to annotate the context changes of functions.

Yeah, mostly because that's how the man page documents it :)

Quoted 11 lines

to annotate a variable, struct/union member or a function that a certain locking primitive is required for accessing it, you do it by
__attribute__((require_context(ctx,min,max,"type")))
ctx ... the expression that describes the locking primitive min ... the minimum of locks required of that locking primitive max ... the maximum allowed of locks of that locking primitive. type .. read, write, rdwr or call for the access type.

Quoted 8 lines

So you can express you need to hold this and that locking primitive to write to something. But an other locking primitive might be sufficient for reading that something.
The annotation for a variable foo protected by a recursive lock bar would be:
int foo __attribute__((require_context(bar,1,99999,"rdwr")))

Ah. Makes sense as well, though now you can't do something like "require context count two and decrement by one", can you? Or do you just do that by combining the various attributes?

Anyhow, I don't really care which patch gets chosen.

Though, how can you actually track multiple contexts within a single function if you have just a "struct expression *context_expr" for each basic block? I guess I should just try your code :)

johannes

Philipp Reisner

2008-04-10 21:21 UTC #8 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 6 lines

Quoted 2 lines
int foo __attribute__((require_context(bar,1,99999,"rdwr")))
Ah. Makes sense as well, though now you can't do something like "require context count two and decrement by one", can you? Or do you just do that by combining the various attributes?

Right, by combining a context and a require_context attribute.

Quoted 3 lines

Anyhow, I don't really care which patch gets chosen.

Nor do I really care. I just hope that there is some reaction from Josh that indicates how he wishes to continue with that toppic... I am also ready to do further work in this area.

Quoted 4 lines

Though, how can you actually track multiple contexts within a single function if you have just a "struct expression *context_expr" for each basic block? I guess I should just try your code :)

In the check_context() I build a expression_list of all the context expressions that are of interest for that entrypoint. Then check_bb_context() is called for each of these expressions that describe a locking primitive.

-Phil

Signature · 3 lines

: Dipl-Ing Philipp Reisner                      Tel +43-1-8178292-50 :
: LINBIT Information Technologies GmbH          Fax +43-1-8178292-82 :
: Vivenotgasse 48, 1120 Vienna, Austria        http://www.linbit.com :

Josh Triplett

2008-04-11 19:53 UTC #9 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 5 lines · Philipp Reisner

Quoted 1 line
Anyhow, I don't really care which patch gets chosen.
Nor do I really care. I just hope that there is some reaction from Josh that indicates how he wishes to continue with that toppic... I am also ready to do further work in this area.

Definitely interested in the patches, just spoiled for choice. However, having now reviewed the various proposals, I think I will accept Johannes Berg's patches to support his corresponding proposed changes in Linux's include/linux/compiler.h.

- Josh Triplett

Johannes Berg

author

2008-04-18 12:35 UTC #10 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 11 lines · Josh Triplett

Quoted 5 lines · Philipp Reisner
Quoted 1 line
Anyhow, I don't really care which patch gets chosen.
Nor do I really care. I just hope that there is some reaction from Josh that indicates how he wishes to continue with that toppic... I am also ready to do further work in this area.
Definitely interested in the patches, just spoiled for choice. However, having now reviewed the various proposals, I think I will accept Johannes Berg's patches to support his corresponding proposed changes in Linux's include/linux/compiler.h.

Do you want me to fold the later cleanup patches into the first two/three?

johannes

Johannes Berg

author

2008-04-11 12:08 UTC #11 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

In reply to Philipp Reisner

Hi,

Managed to take a closer look now.

Quoted 22 lines

Quoted 4 lines
What's this "rdwr" etc. for? And "call"? Also, how are you planning to handle nested contexts, where 1,1 doesn't cut it any >0,>0 is really more like what we need?
I also use it to check a recusive lock mechanism.
The sematics of what I implemented is:
You simply use the __attribute__((context(ctx,in,out))) to annotate the context changes of functions.
to annotate a variable, struct/union member or a function that a certain locking primitive is required for accessing it, you do it by
__attribute__((require_context(ctx,min,max,"type")))
ctx ... the expression that describes the locking primitive min ... the minimum of locks required of that locking primitive max ... the maximum allowed of locks of that locking primitive. type .. read, write, rdwr or call for the access type.

Quoted 8 lines

So you can express you need to hold this and that locking primitive to write to something. But an other locking primitive might be sufficient for reading that something.
The annotation for a variable foo protected by a recursive lock bar would be:
int foo __attribute__((require_context(bar,1,99999,"rdwr")))

To be honest, that confuses me. I haven't been able to come up with a way to make this test case I have result in a warning:

static void bad_macro1(void)

{
    m();
    a();
    r();
}

where a() is acquire(), r() is release() and m() should require the lock, and all should be implemented as macros. I even tried playing with dummy inline functions that are called from the macros.

As for read/write, what's wrong with encoding that in the context?

Something like
void read_lock(something) __attribute__((context(read_something,0,1))); void write_lock(something) __attribute__((context(write_something,0,1)));

or similar. And if it has to be a parameter, why a string?

Another thing I actually like a lot about the fact that my patch changes the warnings is that it tells you
- which function caused the error
- where that function is

I recently had the pleasure of digging through a huge switch statement that looked like this:

function {

[lots of code]

lock();

[lots more code]

switch(something) {
case A:

	[lots of code]
	unlock();
	[lots of code]
	break;
[repeat a dozen times]
case M:
	[lots of code]
	unlock();
	[lots of code]
	// *** NOTE MISSING break;
case N:
	[lots of code]
	unlock();		// <----- this is where my code tells you the error is
	[lots of code]
	break;

[repeat another dozen times]
}

[lots more code in the function]

} // <--- this is where current sparse tells you the error is

Also, my code tells you the function name, and not just "oh, some lock context was wrong" :) I have just created another patch on top of mine that will make the error look like this:

context.c:360:10: warning: context problem in 'warn_huge_switch': 'r' expected different context
context.c:360:10: default context: wanted >= 1, got 0

I like the cond_lock() trick, but I was actually planning on expanding the checking to switch() statements as well and I don't think we can make it work there with such a trick.

Maybe something like __attribute__((conditional_context(ctx,req,default,val=ctxchange,...)))

where you could have e.g.
__attribute__((conditional_context(L,1,0,1=1,-1=-1)))

Not sure yet though whether that is useful or not.

Finally, I think you have a bit of an inconsistency: You introduced the require_context attribute, yet your context() macro still partially fulfils that role, i.e. if you say that a function decreases a context then you require that it gets one when called. Hence, extending that to arbitrary context changes defined via the context attribute seems more natural to me than to require using the require_context attribute for positive assertions and the context attribute for negative assertions.

Quoted 2 lines

PS: I just realized that there my e-mail client introduced linebreakes
in the first patch I posted. I will repost on request of course.

No worries, was easy enough to fix up.

johannes

Josh Triplett

2008-04-21 19:34 UTC #12 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

In reply to Philipp Reisner

Quoted 15 lines · Philipp Reisner

The sematics of what I implemented is:
You simply use the __attribute__((context(ctx,in,out))) to annotate the context changes of functions.
to annotate a variable, struct/union member or a function that a certain locking primitive is required for accessing it, you do it by
__attribute__((require_context(ctx,min,max,"type")))
ctx ... the expression that describes the locking primitive min ... the minimum of locks required of that locking primitive max ... the maximum allowed of locks of that locking primitive. type .. read, write, rdwr or call for the access type.

Quoted 8 lines

So you can express you need to hold this and that locking primitive to write to something. But an other locking primitive might be sufficient for reading that something.
The annotation for a variable foo protected by a recursive lock bar would be:
int foo __attribute__((require_context(bar,1,99999,"rdwr")))

I would *love* to see this work applied on top of the patches I applied from Johannes. I really want the ability to mark a variable or struct field as requiring a context to access.

I would probably call this new attribute something like "data_context". Also, I'd prefer an explicit way of saying "no maximum context", rather than the hack of using a large number.

I hestiate to introduce a third semantic for a pair of numbers describing a context. The context attribute uses in and out contexts, __context__ uses a delta and a required minimum, and this proposed attribute uses a minimum and a maximum.

Similar to GCC's format attribute using the identifier printf rather than the string "printf", I think I'd prefer the last argument as an identifier. Also, a minor nit: could you please use "readwrite" rather than "rdwr"?

- Josh Triplett

Johannes Berg

author

2008-04-21 19:38 UTC #13 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 5 lines

I would *love* to see this work applied on top of the patches I applied from Johannes. I really want the ability to mark a variable or struct field as requiring a context to access.

Quoted 8 lines

I would probably call this new attribute something like "data_context". Also, I'd prefer an explicit way of saying "no maximum context", rather than the hack of using a large number.
I hestiate to introduce a third semantic for a pair of numbers describing a context. The context attribute uses in and out contexts, __context__ uses a delta and a required minimum, and this proposed attribute uses a minimum and a maximum.

I have a fairly simple patch on top of my work for this
http://johannes.sipsolutions.net/patches/sparse/all/LATEST/001-context-on-vars.patch

however, it doesn't really work with struct variables...

johannes

Johannes Berg

author

2008-04-10 15:54 UTC #14 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

In reply to Philipp Reisner

validation/context_requirement.c line 46

Quoted 11 lines

validation/context_requirement.c new file +10 -0

+# define __cond_lock(x,c)	((c) ? ({ __acquire(x); 1; }) : 0)
 
+#define try_inc_local() __cond_lock(local, _try_inc_local())
+static int _try_inc_local(void)
+{
+	if (random() > RAND_MAX/2) {
+		local_cnt++;
+		return 1;
+	}
+	return 0;
+}

That actually works? I guess it shows that I haven't slept enough while working on this.

johannes

Josh Triplett

2008-04-21 19:22 UTC #15 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

In reply to Johannes Berg

Quoted 9 lines · Johannes Berg

Review
Quoted 6 lines
I just have implemented nearly the same here. Hopefully Josh will decide for one of these patches soon.
(quoted diff) +2 -0
+int ident_equal(struct ident *ident1, struct ident *ident2)
 
+int expressions_equal(struct expression *expr1, struct expression *expr2)
That code looks pretty nice, I guess I should look at getting that into my version instead of just printing the identifier to a string.

I would love to see this work applied on top of the merged patches as well.

- Josh Triplett

Josh Triplett

2008-04-21 18:04 UTC #16 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

In reply to Johannes Berg

One comment on your patch description, by the way:

Quoted 13 lines · Johannes Berg

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

Quoted 8 lines

    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);
            [...]
    }

I don't understand why you count this as wrong. read_lock should handle acquiring the context itself, either via an __acquires annotation if written as a function, or via an __acquire__ statement if written as a macro. Callers of read_lock shouldn't need to explicitly call __acquire__.

- Josh Triplett

Johannes Berg

author

2008-04-21 18:11 UTC #17 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 10 lines

Quoted 9 lines

    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);
            [...]
    }

Quoted 5 lines

I don't understand why you count this as wrong. read_lock should handle acquiring the context itself, either via an __acquires annotation if written as a function, or via an __acquire__ statement if written as a macro. Callers of read_lock shouldn't need to explicitly call __acquire__.

Well, the question is how you want to name things. What I did is that the context identifier is just a name and bears no other relation to the code. Hence, read_lock() can't say that it acquires 'dev_base_lock' because it doesn't know what the name should be.

With a slightly different sparse patch than mine you could declare read_lock() something like this:

#define read_lock(x) do { \
	__acquire__(x); \
	__read_lock((x)); \
} while (0)

but then you'd have different names everywhere, say somebody passed '&dev_base_lock' and somebody else used

readlock_t *dbl = &dev_base_lock;
read_lock(dbl)

and you'd end up with one context named "dbl" and another one named "&dev_base_lock".

If you have suggestions on how to solve this I'm all ears, so far I decided it wasn't worth it and opted for explicitly naming all the contexts.

(with my patch the above would just create a context called "x")

johannes

Josh Triplett

2008-04-21 18:25 UTC #18 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 27 lines · Johannes Berg

Quoted 8 lines
Quoted 8 lines
    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);
            [...]
    }
Quoted 5 lines
I don't understand why you count this as wrong. read_lock should handle acquiring the context itself, either via an __acquires annotation if written as a function, or via an __acquire__ statement if written as a macro. Callers of read_lock shouldn't need to explicitly call __acquire__.
Well, the question is how you want to name things. What I did is that the context identifier is just a name and bears no other relation to the code. Hence, read_lock() can't say that it acquires 'dev_base_lock' because it doesn't know what the name should be.
With a slightly different sparse patch than mine you could declare read_lock() something like this:
#define read_lock(x) do { \
	__acquire__(x); \
	__read_lock((x)); \
} while (0)

Quoted 8 lines

but then you'd have different names everywhere, say somebody passed '&dev_base_lock' and somebody else used
readlock_t *dbl = &dev_base_lock;
read_lock(dbl)
and you'd end up with one context named "dbl" and another one named "&dev_base_lock".

That might still work, depending on how consistently kernel code uses the same argument. If you suggest explicitly changing calls to read_lock to call __acquire__ with the appropriate context, it might prove equally easy to make the argument of read_lock that context.

Quoted 5 lines

If you have suggestions on how to solve this I'm all ears, so far I decided it wasn't worth it and opted for explicitly naming all the contexts.
(with my patch the above would just create a context called "x")

That doesn't make sense to me; after preprocessing, x no longer exists, so I don't see how you could pick up the identifier "x". I can understand that you might pick up two different expressions in place of x which you can't easily compare, though.

And as for how to solve it: I think alias analysis might work.

- Josh Triplett

Johannes Berg

author

2008-04-21 18:31 UTC #19 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 8 lines

Quoted 3 lines
and you'd end up with one context named "dbl" and another one named "&dev_base_lock".
That might still work, depending on how consistently kernel code uses the same argument. If you suggest explicitly changing calls to read_lock to call __acquire__ with the appropriate context, it might prove equally easy to make the argument of read_lock that context.

True.

Quoted 4 lines

That doesn't make sense to me; after preprocessing, x no longer exists, so I don't see how you could pick up the identifier "x". I can understand that you might pick up two different expressions in place of x which you can't easily compare, though.

Oops, yes, preprocessing will remove it, of course. But yeah, you can end up with two different expressions.

Quoted 1 line

And as for how to solve it: I think alias analysis might work.

How would I do that?

johannes

Josh Triplett

2008-04-21 18:51 UTC #20 lore raw

Re: [PATCH 1/3] make sparse keep its promise about context tracking

Quoted 3 lines · Johannes Berg

Quoted 1 line
And as for how to solve it: I think alias analysis might work.
How would I do that?

Real compilers have alias analysis code, which builds up information on which variables and expressions may/must alias each other. I think that that alias information might prove sufficient to compare
contexts: if two contexts alias each other then they represent the same context.

Basic type-based alias analysis should prove sufficient to handle cases like:

spinlock_t s;
struct something_with_a_spinlock st;

spin_lock(&st.s);
spin_unlock(&st.s); /* contexts match */

spin_lock(&st.s);
spin_unlock(&s); /* warn */

Flow-based alias analysis may also handle cases like you mentioned, where you assign a lock to a variable and then use it through that variable.

Alternatively, some simple dataflow analysis and symbolic execution might let you figure out the lock a variable points to in most cases.

As a simpler solution, you could just do what lockdep does: make assumptions that handle the common cases, and allow explicit overrides for the uncommon cases. I suspect that most code does not assign a lock to a variable and use the lock through that variable.

In particular, you could perhaps make the assumption that any expression which resolves to the "foo" field of a "struct bar" represents the same context, rather than attempting to distinguish between them.

- Josh Triplett

Johannes Berg

author

2008-04-10 14:41 UTC #21 lore raw

PATCH 2/3 sparse test suite: add test mixing __context__ and __attribute__((context(...)))

In reply to Johannes Berg

An earlier version of the next patch had a bug that this test catches.

Signed-off-by Johannes Berg <[email protected]>

---
 validation/context-named.c |   21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)

validation/context-named.c +21 -0

@@ -465,6 +465,27 @@ static void warn_exact_fn2(void)
     r2();
 }
 
+#define __acquire(x)	__context__(x,1)
+#define __release(x)	__context__(x,-1)
+
+#define rl() \
+  do { __acquire(RCU); } while (0)
+
+#define ru() \
+  do { __release(RCU); } while (0)
+
+static void good_mixed_with_if(void)
+{
+    rl();
+
+    if (condition) {
+        a();
+        r();
+    }
+
+    ru();
+}
+
 /*
  * check-name: Check -Wcontext with lock names
  *

Johannes Berg

author

2008-04-10 14:41 UTC #22 lore raw

PATCH 3/3 sparse: simple conditional context tracking

In reply to Johannes Berg

This patch enables a very simple form of conditional context tracking, namely something like

if (spin_trylock(...)) {
	[...]
	spin_unlock(...);
}

Note that
__ret = spin_trylock(...);

if (__ret) {
	[...]
	spin_unlock(...);
}

does /not/ work since that would require tracking the variable and doing extra checks to ensure the variable isn't globally accessible or similar which could lead to race conditions.

To declare a trylock, one uses:

int spin_trylock(...) __attribute__((conditional_context(spinlock,0,1,0))) {...}

Note that doing this currently excludes that function itself from context checking completely.

Signed-off-by Johannes Berg <[email protected]>

---
 linearize.c                  |   22 +----
 linearize.h                  |    3 
 parse.c                      |   52 +++++++++++++
 sparse.1                     |    9 ++
 sparse.c                     |   54 ++++++++++----
 symbol.h                     |    2 
 validation/context-dynamic.c |  161 +++++++++++++++++++++++++++++++++++++++++++
 7 files changed, 270 insertions(+), 33 deletions(-)

sparse.c +40 ~~-14~~

@@ -25,7 +25,7 @@
 #include "linearize.h"
 
 struct context_check {
-	int val;
+	int val, val_false;
 	char name[32];
 };

@@ -42,7 +42,7 @@ static const char *context_name(struct c
 	return unnamed_context;
 }
 
-static void context_add(struct context_check_list **ccl, const char *name, int offs)
+static void context_add(struct context_check_list **ccl, const char *name, int offs, int offs_false)
 {
 	struct context_check *check, *found = NULL;

@@ -60,6 +60,7 @@ static void context_add(struct context_c
 		add_ptr_list(ccl, found);
 	}
 	found->val += offs;
+	found->val_false += offs_false;
 }
 
 static int imbalance(struct entrypoint *ep, struct position pos, const char *name, const char *why)

@@ -83,7 +84,7 @@ static int context_list_check(struct ent
 
 	/* make sure the loop below checks all */
 	FOR_EACH_PTR(ccl_target, c1) {
-		context_add(&ccl_cur, c1->name, 0);
+		context_add(&ccl_cur, c1->name, 0, 0);
 	} END_FOR_EACH_PTR(c1);
 
 	FOR_EACH_PTR(ccl_cur, c1) {

@@ -108,12 +109,13 @@ static int context_list_check(struct ent
 
 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 *ccl_target,
+			    int in_false)
 {
 	struct context_check_list *combined = NULL;
 	struct context_check *c;
 	struct instruction *insn;
-	struct basic_block *child;
+	struct multijmp *mj;
 	struct context *ctx;
 	const char *name;
 	int ok, val;

@@ -125,7 +127,10 @@ static int check_bb_context(struct entry
 	bb->context++;
 
 	FOR_EACH_PTR(ccl_in, c) {
-		context_add(&combined, c->name, c->val);
+		if (in_false)
+			context_add(&combined, c->name, c->val_false, c->val_false);
+		else
+			context_add(&combined, c->name, c->val, c->val);
 	} END_FOR_EACH_PTR(c);
 
 	FOR_EACH_PTR(bb->insns, insn) {

@@ -182,7 +187,23 @@ static int check_bb_context(struct entry
 				free((void *)name);
 				return -1;
 			}
-			context_add(&combined, name, insn->increment);
+
+			context_add(&combined, name, insn->increment, insn->inc_false);
+			break;
+		case OP_BR:
+			if (insn->bb_true)
+				if (check_bb_context(ep, insn->bb_true, combined, ccl_target, 0))
+					return -1;
+			if (insn->bb_false)
+				if (check_bb_context(ep, insn->bb_false, combined, ccl_target, 1))
+					return -1;
+			break;
+		case OP_SWITCH:
+		case OP_COMPUTEDGOTO:
+			FOR_EACH_PTR(insn->multijmp_list, mj) {
+				if (check_bb_context(ep, mj->target, combined, ccl_target, 0))
+					return -1;
+			} END_FOR_EACH_PTR(mj);
 			break;
  		}
 	} END_FOR_EACH_PTR(insn);

@@ -193,10 +214,12 @@ static int check_bb_context(struct entry
 	if (insn->opcode == OP_RET)
 		return context_list_check(ep, insn->pos, combined, ccl_target);
 
-	FOR_EACH_PTR(bb->children, child) {
-		if (check_bb_context(ep, child, combined, ccl_target))
-			return -1;
-	} END_FOR_EACH_PTR(child);
+	FOR_EACH_PTR(bb->insns, insn) {
+		if (!insn->bb)
+			continue;
+		switch (insn->opcode) {
+		}
+	} END_FOR_EACH_PTR(insn);
 
 	/* contents will be freed once we return out of recursion */
 	free_ptr_list(&combined);

@@ -358,11 +381,14 @@ static void check_context(struct entrypo
 	FOR_EACH_PTR(sym->ctype.contexts, context) {
 		const char *name = context_name(context);
 
-		context_add(&ccl_in, name, context->in);
-		context_add(&ccl_target, name, context->out);
+		context_add(&ccl_in, name, context->in, context->in);
+		context_add(&ccl_target, name, context->out, context->out_false);
+		/* we don't currently check the body of trylock functions */
+		if (context->out != context->out_false)
+			return;
 	} END_FOR_EACH_PTR(context);
 
-	check_bb_context(ep, ep->entry->bb, ccl_in, ccl_target);
+	check_bb_context(ep, ep->entry->bb, ccl_in, ccl_target, 0);
 	free_ptr_list(&ccl_in);
 	free_ptr_list(&ccl_target);
 	clear_context_check_alloc();

symbol.h +1 -1

@@ -71,7 +71,7 @@ enum keyword {
 
 struct context {
 	struct expression *context;
-	unsigned int in, out;
+	unsigned int in, out, out_false;
 	int exact;
 };

validation/context-dynamic.c new file +161 -0

161 lines not on this page · raw message

linearize.c +6 ~~-16~~

@@ -439,7 +439,7 @@ const char *show_instruction(struct inst
 		break;
 
 	case OP_CONTEXT:
-		buf += sprintf(buf, "%s%d", insn->check ? "check: " : "", insn->increment);
+		buf += sprintf(buf, "%s%d,%d", "", insn->increment, insn->inc_false);
 		break;
 	case OP_RANGE:
 		buf += sprintf(buf, "%s between %s..%s", show_pseudo(insn->src1), show_pseudo(insn->src2), show_pseudo(insn->src3));

@@ -1233,23 +1233,12 @@ static pseudo_t linearize_call_expressio
 		FOR_EACH_PTR(ctype->contexts, context) {
 			int in = context->in;
 			int out = context->out;
-			int check = 0;
-			int context_diff;
-			if (in < 0) {
-				check = 1;
-				in = 0;
-			}
-			if (out < 0) {
-				check = 0;
-				out = 0;
-			}
-			context_diff = out - in;
-			if (check || context_diff) {
+
+			if (out - in || context->out_false - in) {
 				insn = alloc_instruction(OP_CONTEXT, 0);
-				insn->increment = context_diff;
-				/* what's check for? */
-				insn->check = check;
+				insn->increment = out - in;
 				insn->context_expr = context->context;
+				insn->inc_false = context->out_false - in;
 				add_one_insn(ep, insn);
 			}
 		} END_FOR_EACH_PTR(context);

@@ -1684,6 +1673,7 @@ static pseudo_t linearize_context(struct
 		value = expr->value;
 
 	insn->increment = value;
+	insn->inc_false = value;
 
 	expr = stmt->required;
 	value = 0;

linearize.h +1 -2

@@ -116,8 +116,7 @@ struct instruction {
 			struct pseudo_list *arguments;
 		};
 		struct /* context */ {
-			int increment, required;
-			int check;
+			int increment, required, inc_false;
 			struct expression *context_expr;
 		};
 		struct /* asm */ {

parse.c +52 -0

82 lines not on this page · raw message

sparse.1 +9 -0

@@ -94,6 +94,15 @@ There currently is no corresponding
 .BI __exact_context__( [expression , ]adjust_value[ , required] )
 statement.
 
+To indicate that a certain function acquires a context depending on its
+return value, use
+.BI __attribute__((conditional_context( [expression ,] in_context , out_success , out_failure ))
+where \fIout_success\fR and \fIout_failure\fR indicate the context change
+done depending on success (non-zero) or failure (zero) return of the
+function. Note that currently, using this attribute on a function means that
+the function itself won't be checked for context handling at all. See the
+testsuite for examples.
+
 Sparse will warn when it sees a function change a
 context without indicating this with a \fBcontext\fR or \fBexact_context\fR attribute, either by
 decreasing a context below zero (such as by releasing a lock without acquiring

Johannes Berg

author

2008-04-11 12:08 UTC #23 lore raw

[PATCH 4/3] inlined call bugfix & test

In reply to Johannes Berg

This patch fixes an oversight in my other patches, inlined calls weren't checked for context properly. Also adds a test case for this.

Signed-off-by Johannes Berg <[email protected]>

---
I'll roll this into the other patches if wanted.

 sparse.c                   |    1 +
 validation/context-named.c |   12 ++++++++++++
 2 files changed, 13 insertions(+)

sparse.c +1 -0

@@ -137,6 +137,7 @@ static int check_bb_context(struct entry
 		if (!insn->bb)
 			continue;
 		switch (insn->opcode) {
+		case OP_INLINED_CALL:
 		case OP_CALL:
 			if (!insn->func || !insn->func->sym || insn->func->type != PSEUDO_SYM)
 				break;

validation/context-named.c +12 -0

@@ -465,6 +465,17 @@ static void warn_exact_fn2(void)
     r2();
 }
 
+static inline void need_lock3(void) __attribute__((context(TEST,1,1)))
+{
+}
+
+static void warn_fn3(void)
+{
+    a2();
+    need_lock3();
+    r2();
+}
+
 #define __acquire(x)	__context__(x,1)
 #define __release(x)	__context__(x,-1)

@@ -513,5 +524,6 @@ context-named.c:434:14: warning: context
 context-named.c:441:15: warning: context problem in 'warn_fn2' - function 'need_lock2' expected different context
 context-named.c:456:20: warning: context problem in 'warn_exact_fn1' - function 'need_lock_exact' expected different context
 context-named.c:464:20: warning: context problem in 'warn_exact_fn2' - function 'need_lock_exact' expected different context
+context-named.c:475:15: warning: context problem in 'warn_fn3' - function 'need_lock3' expected different context
  * check-error-end
  */

Johannes Berg

author

2008-04-11 12:08 UTC #24 lore raw

[PATCH 5/3] improve -Wcontext code and messages

In reply to Johannes Berg

This builds on my previous code improving the code and the messages, the messages now always tell you the expected and actual context value. Also add another test since I had mentioned that case.

Signed-off-by Johannes Berg <[email protected]>

---
I can also roll this into the other patches if wanted.

 sparse.c                       |  234 +++++++++++++++++++++++++++--------------
 validation/context-dynamic.c   |   14 ++
 validation/context-named.c     |   72 ++++++++----
 validation/context-statement.c |   17 ++
 validation/context.c           |   90 +++++++++++++--
 5 files changed, 307 insertions(+), 120 deletions(-)

sparse.c +158 ~~-76~~

@@ -42,7 +42,8 @@ static const char *context_name(struct c
 	return unnamed_context;
 }
 
-static void context_add(struct context_check_list **ccl, const char *name, int offs, int offs_false)
+static void context_add(struct context_check_list **ccl, const char *name,
+			int offs, int offs_false)
 {
 	struct context_check *check, *found = NULL;

@@ -63,16 +64,19 @@ static void context_add(struct context_c
 	found->val_false += offs_false;
 }
 
-static int imbalance(struct entrypoint *ep, struct position pos, const char *name, const char *why)
+#define IMBALANCE_IN "context imbalance in '%s': "
+#define DEFAULT_CONTEXT_DESCR "   default context: "
+
+static void get_context_string(char **buf, const char **name)
 {
-	if (Wcontext) {
-		struct symbol *sym = ep->name;
-		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);
+	if (strcmp(*name, unnamed_context)) {
+		*buf = malloc(strlen(*name) + 16);
+		sprintf(*buf, "   context '%s': ", *name);
+		*name = *buf;
+	} else {
+		*name = DEFAULT_CONTEXT_DESCR;
+		*buf = NULL;
 	}
-	return -1;
 }
 
 static int context_list_check(struct entrypoint *ep, struct position pos,

@@ -81,6 +85,8 @@ static int context_list_check(struct ent
 {
 	struct context_check *c1, *c2;
 	int cur, tgt;
+	const char *name;
+	char *buf;
 
 	/* make sure the loop below checks all */
 	FOR_EACH_PTR(ccl_target, c1) {

@@ -98,15 +104,131 @@ static int context_list_check(struct ent
 			break;
 		} END_FOR_EACH_PTR(c2);
 
+		if (cur == tgt || !Wcontext)
+			continue;
+
 		if (cur > tgt)
-			return imbalance(ep, pos, c1->name, "wrong count at exit");
+			warning(pos, IMBALANCE_IN "wrong count at exit",
+				show_ident(ep->name->ident));
 		else if (cur < tgt)
-			return imbalance(ep, pos, c1->name, "unexpected unlock");
+			warning(pos, IMBALANCE_IN "unexpected unlock",
+				show_ident(ep->name->ident));
+
+		name = c1->name;
+		get_context_string(&buf, &name);
+
+		info(pos, "%swanted %d, got %d",
+		     name, tgt, cur);
+
+		free(buf);
+
+		return -1;
 	} END_FOR_EACH_PTR(c1);
 
 	return 0;
 }
 
+static int handle_call(struct entrypoint *ep, struct basic_block *bb,
+		       struct instruction *insn,
+		       struct context_check_list *combined)
+{
+	struct context *ctx;
+	struct context_check *c;
+	const char *name, *call, *cmp;
+	char *buf;
+	int val, ok;
+
+	if (!insn->func || !insn->func->sym ||
+	    insn->func->type != PSEUDO_SYM)
+		return 0;
+
+	/*
+	 * Check all contexts the function wants.
+	 */
+	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;
+			cmp = "";
+		} else {
+			ok = ctx->in <= val;
+			cmp = ">= ";
+		}
+
+		if (!ok && Wcontext) {
+			get_context_string(&buf, &name);
+			call = strdup(show_ident(insn->func->ident));
+
+			warning(insn->pos, "context problem in '%s': "
+				"'%s' expected different context",
+				show_ident(ep->name->ident), call);
+
+			info(insn->pos, "%swanted %s%d, got %d",
+			     name, cmp, ctx->in, val);
+
+			free((void *)call);
+			free(buf);
+
+			return -1;
+		}
+	} END_FOR_EACH_PTR (ctx);
+
+	return 0;
+}
+
+static int handle_context(struct entrypoint *ep, struct basic_block *bb,
+			  struct instruction *insn,
+			  struct context_check_list **combined)
+{
+	struct context_check *c;
+	const char *name;
+	char *buf;
+	int val, ok;
+
+	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 && Wcontext) {
+		get_context_string(&buf, &name);
+
+		warning(insn->pos,
+			IMBALANCE_IN
+			"__context__ statement expected different context",
+			show_ident(ep->name->ident));
+
+		info(insn->pos, "%swanted >= %d, got %d",
+		     name, insn->required, val);
+
+		free(buf);
+		return -1;
+	}
+
+	context_add(combined, name, insn->increment, insn->inc_false);
+
+	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,

@@ -116,16 +238,21 @@ static int check_bb_context(struct entry
 	struct context_check *c;
 	struct instruction *insn;
 	struct multijmp *mj;
-	struct context *ctx;
-	const char *name;
-	int ok, val;
 
-	/* recurse in once to catch bad loops */
+	/*
+	 * recurse in once to catch bad loops,
+	 * bb->context is initialised to -1.
+	 */
 	if (bb->context > 0)
 		return 0;
-
 	bb->context++;
 
+	/*
+	 * We're starting with a completely new local list of contexts, so
+	 * initialise it according to what we got from the parent block.
+	 * That may use either the 'false' or the 'true' part of the context
+	 * for the conditional_context() attribute.
+	 */
 	FOR_EACH_PTR(ccl_in, c) {
 		if (in_false)
 			context_add(&combined, c->name, c->val_false, c->val_false);

@@ -133,76 +260,37 @@ static int check_bb_context(struct entry
 			context_add(&combined, c->name, c->val, c->val);
 	} END_FOR_EACH_PTR(c);
 
+	/*
+	 * Now walk the instructions for this block, recursing into any
+	 * instructions that have children. We need to have the right
+	 * order so we cannot iterate bb->children instead.
+	 */
 	FOR_EACH_PTR(bb->insns, insn) {
-		if (!insn->bb)
-			continue;
 		switch (insn->opcode) {
 		case OP_INLINED_CALL:
 		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);
+			if (handle_call(ep, bb, insn, combined))
+				return -1;
 			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);
+			if (handle_context(ep, bb, insn, &combined))
 				return -1;
-			}
-
-			context_add(&combined, name, insn->increment, insn->inc_false);
 			break;
 		case OP_BR:
 			if (insn->bb_true)
-				if (check_bb_context(ep, insn->bb_true, combined, ccl_target, 0))
+				if (check_bb_context(ep, insn->bb_true,
+						     combined, ccl_target, 0))
 					return -1;
 			if (insn->bb_false)
-				if (check_bb_context(ep, insn->bb_false, combined, ccl_target, 1))
+				if (check_bb_context(ep, insn->bb_false,
+						     combined, ccl_target, 1))
 					return -1;
 			break;
 		case OP_SWITCH:
 		case OP_COMPUTEDGOTO:
 			FOR_EACH_PTR(insn->multijmp_list, mj) {
-				if (check_bb_context(ep, mj->target, combined, ccl_target, 0))
+				if (check_bb_context(ep, mj->target,
+					             combined, ccl_target, 0))
 					return -1;
 			} END_FOR_EACH_PTR(mj);
 			break;

@@ -212,16 +300,10 @@ static int check_bb_context(struct entry
 	insn = last_instruction(bb->insns);
 	if (!insn)
 		return 0;
+
 	if (insn->opcode == OP_RET)
 		return context_list_check(ep, insn->pos, combined, ccl_target);
 
-	FOR_EACH_PTR(bb->insns, insn) {
-		if (!insn->bb)
-			continue;
-		switch (insn->opcode) {
-		}
-	} END_FOR_EACH_PTR(insn);
-
 	/* contents will be freed once we return out of recursion */
 	free_ptr_list(&combined);

validation/context-dynamic.c +12 -2

@@ -151,11 +151,21 @@ static int good_switch(void)
     r();
 }
 
+static void bad_lock1(void)
+{
+    r();
+    a();
+}
+
 /*
  * check-name: Check -Wcontext with lock trylocks
  *
  * check-error-start
-context-dynamic.c:83:6: warning: context problem in 'bad_trylock1' - function 'r' expected different context
-context-dynamic.c:133:6: warning: context problem in 'bad_trylock2' - function 'r' expected different context
+context-dynamic.c:83:6: warning: context problem in 'bad_trylock1': 'r' expected different context
+context-dynamic.c:83:6:    context 'A': wanted >= 1, got 0
+context-dynamic.c:133:6: warning: context problem in 'bad_trylock2': 'r' expected different context
+context-dynamic.c:133:6:    context 'A': wanted >= 1, got 0
+context-dynamic.c:156:6: warning: context problem in 'bad_lock1': 'r' expected different context
+context-dynamic.c:156:6:    context 'A': wanted >= 1, got 0
  * check-error-end
  */

validation/context-named.c +48 ~~-24~~

77 lines not on this page · raw message

validation/context-statement.c +14 -3

@@ -47,12 +47,23 @@ static void bad_macro2(void)
     m();
 }
 
+static void bad_macro3(void)
+{
+    r();
+    a();
+}
+
 /*
  * check-name: Check __context__ statement with required context
  *
  * check-error-start
-context-statement.c:16:8: warning: context imbalance in 'bad_arr' - unexpected unlock (LOCK)
-context-statement.c:38:5: warning: context imbalance in 'bad_macro1' - __context__ statement expected different lock context (LOCK)
-context-statement.c:47:5: warning: context imbalance in 'bad_macro2' - __context__ statement expected different lock context (LOCK)
+context-statement.c:16:8: warning: context imbalance in 'bad_arr': unexpected unlock
+context-statement.c:16:8:    context 'LOCK': wanted 0, got -1
+context-statement.c:38:5: warning: context imbalance in 'bad_macro1': __context__ statement expected different context
+context-statement.c:38:5:    context 'LOCK': wanted >= 1, got 0
+context-statement.c:47:5: warning: context imbalance in 'bad_macro2': __context__ statement expected different context
+context-statement.c:47:5:    context 'LOCK': wanted >= 1, got 0
+context-statement.c:53:5: warning: context imbalance in 'bad_macro3': __context__ statement expected different context
+context-statement.c:53:5:    context 'LOCK': wanted >= 0, got -1
  * check-error-end
  */

validation/context.c +75 ~~-15~~

99 lines not on this page · raw message

Josh Triplett

2008-04-21 18:37 UTC #25 lore raw

In reply to Johannes Berg

Quoted 1 line · Johannes Berg

Here are three patches to improve context tracking in sparse.

All five patches applied and pushed. Thanks for your great work!

- Josh Triplett