context tracking updates

PATCH In review Johannes Berg 4 participants 27 messages May 29, 2008 – Sep 11, 2008 Sparse checker

Share & tools

Johannes Berg

author

2008-05-29 09:01 UTC #0 lore raw

cover context tracking updates

This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)

johannes

Johannes Berg

author

2008-05-29 09:00 UTC #1 lore raw

PATCH 1/9 add test for acquire/release

Test that giving

	__attribute__((context(TEST,1,0)))
	__attribute__((context(TEST,0,1)))
instead of
	__attribute__((context(TEST,1,1)))

works.

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

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

validation/context.c +15 -0

@@ -380,6 +380,21 @@ static int warn_conditional(void)
     return 0;
 }
 
+static void good_require(void)
+__attribute__((context(TEST,1,0)))
+__attribute__((context(TEST,0,1)))
+{
+    __context__(TEST,-1);
+    __context__(TEST,1);
+}
+
+static void good_require_caller(void)
+{
+    __context__(TEST,1,0);
+    good_require();
+    __context__(TEST,-1,1);
+}
+
 /*
  * check-name: Check -Wcontext
  *

Johannes Berg

author

2008-05-29 08:57 UTC #2 lore raw

PATCH 2/9 add __exact_context__

In reply to Johannes Berg

We also need a statement to indicate that an exact context is required, most notably the next patch will require it so that it can translate attributes on variables into statements.

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

---
 ident-list.h               |    1 
 linearize.c                |    1 
 linearize.h                |    2 -
 parse.c                    |   20 ++++++++++++-
 parse.h                    |    1 
 sparse.1                   |    2 -
 sparse.c                   |   14 ++++++---
 validation/context-exact.c |   67 +++++++++++++++++++++++++++++++++++++++++++++
 8 files changed, 101 insertions(+), 7 deletions(-)

ident-list.h +1 -0

@@ -96,6 +96,7 @@ __IDENT(__PRETTY_FUNCTION___ident, "__PR
 
 /* Sparse commands */
 IDENT_RESERVED(__context__);
+IDENT_RESERVED(__exact_context__);
 IDENT_RESERVED(__range__);
 
 /* Magic function names we recognize */

linearize.c +1 -0

@@ -1681,6 +1681,7 @@ static pseudo_t linearize_context(struct
 		value = expr->value;
 
 	insn->required = value;
+	insn->exact = stmt->exact;
 
 	insn->context_expr = stmt->context;
 	add_one_insn(ep, insn);

parse.c +19 -1

@@ -52,6 +52,7 @@ static struct token *parse_while_stateme
 static struct token *parse_do_statement(struct token *token, struct statement *stmt);
 static struct token *parse_goto_statement(struct token *token, struct statement *stmt);
 static struct token *parse_context_statement(struct token *token, struct statement *stmt);
+static struct token *parse_exact_context_statement(struct token *token, struct statement *stmt);
 static struct token *parse_range_statement(struct token *token, struct statement *stmt);
 static struct token *parse_asm_statement(struct token *token, struct statement *stmt);
 static struct token *toplevel_asm_declaration(struct token *token, struct symbol_list **list);

@@ -149,6 +150,10 @@ static struct symbol_op __context___op =
 	.statement = parse_context_statement,
 };
 
+static struct symbol_op __exact_context___op = {
+	.statement = parse_exact_context_statement,
+};
+
 static struct symbol_op range_op = {
 	.statement = parse_range_statement,
 };

@@ -254,6 +259,7 @@ static struct init_keyword {
 	{ "do",		NS_KEYWORD, .op = &do_op },
 	{ "goto",	NS_KEYWORD, .op = &goto_op },
 	{ "__context__",NS_KEYWORD, .op = &__context___op },
+	{ "__exact_context__",NS_KEYWORD, .op = &__exact_context___op },
 	{ "__range__",	NS_KEYWORD, .op = &range_op },
 	{ "asm",	NS_KEYWORD, .op = &asm_op },
 	{ "__asm",	NS_KEYWORD, .op = &asm_op },

@@ -1810,7 +1816,7 @@ static struct token *parse_goto_statemen
 	return expect(token, ';', "at end of statement");
 }
 
-static struct token *parse_context_statement(struct token *token, struct statement *stmt)
+static struct token *_parse_context_statement(struct token *token, struct statement *stmt, int exact)
 {
 	struct expression *args[3];
 	int argc = 0;

@@ -1835,6 +1841,8 @@ static struct token *parse_context_state
 	stmt->expression = args[0];
 	stmt->context = NULL;
 
+	stmt->exact = exact;
+
 	switch (argc) {
 	case 0:
 		sparse_error(token->pos, "__context__ statement needs argument(s)");

@@ -1864,6 +1872,16 @@ static struct token *parse_context_state
 	return expect(token, ')', "at end of __context__");
 }
 
+static struct token *parse_context_statement(struct token *token, struct statement *stmt)
+{
+	return _parse_context_statement(token, stmt, 0);
+}
+
+static struct token *parse_exact_context_statement(struct token *token, struct statement *stmt)
+{
+	return _parse_context_statement(token, stmt, 1);
+}
+
 static struct token *parse_range_statement(struct token *token, struct statement *stmt)
 {
 	stmt->type = STMT_RANGE;

sparse.1 +1 -1

@@ -90,7 +90,7 @@ 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
+There is also the corresponding
 .BI __exact_context__( [expression , ]adjust_value[ , required] )
 statement.

sparse.c +10 -4

@@ -239,7 +239,7 @@ static int handle_context(struct entrypo
 			  struct context_check_list **combined)
 {
 	struct context_check *c;
-	const char *name;
+	const char *name, *cmp;
 	char *buf;
 	int val, ok;

@@ -256,7 +256,13 @@ static int handle_context(struct entrypo
 		}
 	} END_FOR_EACH_PTR(c);
 
-	ok = insn->required <= val;
+	if (insn->exact) {
+		ok = insn->required == val;
+		cmp = "";
+	} else {
+		ok = insn->required <= val;
+		cmp = ">= ";
+	}
 
 	if (!ok && Wcontext) {
 		get_context_string(&buf, &name);

@@ -266,8 +272,8 @@ static int handle_context(struct entrypo
 			"__context__ statement expected different context",
 			show_ident(ep->name->ident));
 
-		info(insn->pos, "%swanted >= %d, got %d",
-		     name, insn->required, val);
+		info(insn->pos, "%swanted %s%d, got %d",
+		     name, cmp, insn->required, val);
 
 		free(buf);
 		return -1;

validation/context-exact.c new file +67 -0

67 lines not on this page · raw message

linearize.h +1 -1

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

parse.h +1 -0

@@ -43,6 +43,7 @@ struct statement {
 			struct expression *expression;
 			struct expression *context;
 			struct expression *required;
+			int exact;
 		};
 		struct /* return_statement */ {
 			struct expression *ret_value;

Johannes Berg

author

2008-05-29 09:02 UTC #3 lore raw

PATCH 3/9 allow context() attribute on variables

In reply to Johannes Berg

This patch makes it possible to add the context attribute on variables, to warn for example in this case:

    struct something {
        int x __attribute__((context(L,1,1)));
    };

    extern struct something *s;

    static void warn_access13(void)
    {
        s->x = 7;
    }

This is achieved by translating the context attribute on variables that are loaded from/stored to into a context expression internally. A number of tests are included, including tests for a struct member (as above) and array accesses.

To distinguish between reads and writes (the default is to check both) use the fourth parameter to the context attribute:

	__attribute__((context(L,1,1,read)))
or
	__attribute__((context(L,1,1,write)))

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

---
The exact_context() attribute is also allowed so we have the same max/no-max semantics as functions.

 linearize.c                    |   92 ++++++++++++++++-
 linearize.h                    |    1 
 parse.c                        |   25 ++++
 sparse.1                       |    7 +
 sparse.c                       |   18 ++-
 symbol.h                       |    7 +
 validation/context-exact.c     |    2 
 validation/context-on-vars.c   |  219 +++++++++++++++++++++++++++++++++++++++++
 validation/context-statement.c |    6 -
 9 files changed, 365 insertions(+), 12 deletions(-)

sparse.c +14 -4

@@ -114,6 +114,7 @@ static struct context_check_list *checke
 }
 
 #define IMBALANCE_IN "context imbalance in '%s': "
+#define CONTEXT_PROB "context problem in '%s': "
 #define DEFAULT_CONTEXT_DESCR "   default context: "
 
 static void get_context_string(char **buf, const char **name)

@@ -267,10 +268,19 @@ static int handle_context(struct entrypo
 	if (!ok && Wcontext) {
 		get_context_string(&buf, &name);
 
-		warning(insn->pos,
-			IMBALANCE_IN
-			"__context__ statement expected different context",
-			show_ident(ep->name->ident));
+		if (insn->access_var) {
+			char *symname = strdup(show_ident(insn->access_var->ident));
+			warning(insn->pos,
+				CONTEXT_PROB
+				"access to '%s' requires different context",
+				show_ident(ep->name->ident), symname);
+			free(symname);
+		} else {
+			warning(insn->pos,
+				CONTEXT_PROB
+				"__context__ statement expected different context",
+				show_ident(ep->name->ident));
+		}
 
 		info(insn->pos, "%swanted %s%d, got %d",
 		     name, cmp, insn->required, val);

validation/context-on-vars.c new file +219 -0

219 lines not on this page · raw message

linearize.c +90 -2

122 lines not on this page · raw message

linearize.h +1 -0

@@ -118,6 +118,7 @@ struct instruction {
 		struct /* context */ {
 			int increment, required, inc_false, exact;
 			struct expression *context_expr;
+			struct symbol *access_var;
 		};
 		struct /* asm */ {
 			const char *string;

validation/context-statement.c +3 -3

@@ -59,11 +59,11 @@ static void bad_macro3(void)
  * check-error-start
 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: warning: context problem 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: warning: context problem 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: warning: context problem in 'bad_macro3': __context__ statement expected different context
 context-statement.c:53:5:    context 'LOCK': wanted >= 0, got -1
  * check-error-end
  */

sparse.1 +7 -0

@@ -94,6 +94,13 @@ There is also the corresponding
 .BI __exact_context__( [expression , ]adjust_value[ , required] )
 statement.
 
+Both these can also be added to variable accesses but it is not recommended
+to make variable accesses modify the context. For variables, it is possible
+to distinguish between reads and writes (the regular context attribute will
+be required on both reads and writes) by using either the token "read" or
+the token "write" for an optional fourth argument:
+.BI __attribute__((context( expression , in_context , out_context , read|write )).
+
 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 ))

validation/context-exact.c +1 -1

@@ -61,7 +61,7 @@ static void good_5(void)
  * check-name: Check __exact_context__ statement with required context
  *
  * check-error-start
-context-exact.c:46:2: warning: context imbalance in 'warn_1': __context__ statement expected different context
+context-exact.c:46:2: warning: context problem in 'warn_1': __context__ statement expected different context
 context-exact.c:46:2:    context 'TEST': wanted 1, got 2
  * check-error-end
  */

parse.c +23 -2

@@ -883,16 +883,18 @@ static struct token *attribute_mode(stru
 static struct token *_attribute_context(struct token *token, struct symbol *attr, struct ctype *ctype, int exact)
 {
 	struct context *context = alloc_context();
-	struct expression *args[3];
+	struct expression *args[4];
 	int argc = 0;
+	struct token *last = NULL;
 
 	token = expect(token, '(', "after context attribute");
 	while (!match_op(token, ')')) {
 		struct expression *expr = NULL;
+		last = token;
 		token = conditional_expression(token, &expr);
 		if (!expr)
 			break;
-		if (argc < 3)
+		if (argc < 4)
 			args[argc++] = expr;
 		else
 			argc++;

@@ -917,6 +919,25 @@ static struct token *_attribute_context(
 		context->in = get_expression_value(args[1]);
 		context->out = get_expression_value(args[2]);
 		break;
+	case 4: {
+		const char *rw;
+		context->context = args[0];
+		context->in = get_expression_value(args[1]);
+		context->out = get_expression_value(args[2]);
+
+		if (last && token_type(last) == TOKEN_IDENT)
+			rw = show_token(last);
+		else
+			rw = NULL;
+
+		if (rw && strcmp(rw, "read") == 0)
+			context->rws = CTX_RWS_READ;
+		else if (rw && strcmp(rw, "write") == 0)
+			context->rws = CTX_RWS_WRITE;
+		else
+			sparse_error(last->pos, "invalid read/write specifier");
+		break;
+	}
 	default:
 		sparse_error(token->pos, "too many arguments to context attribute");
 		break;

symbol.h +7 -0

@@ -69,10 +69,17 @@ enum keyword {
 	KW_MODE		= 1 << 7,
 };
 
+enum context_read_write_specifier {
+	CTX_RWS_BOTH = 0,
+	CTX_RWS_READ,
+	CTX_RWS_WRITE,
+};
+
 struct context {
 	struct expression *context;
 	unsigned int in, out, out_false;
 	int exact;
+	enum context_read_write_specifier rws;
 };
 
 extern struct context *alloc_context(void);

Johannes Berg

author

2008-05-29 08:58 UTC #4 lore raw

PATCH 4/9 evaluate/expand context expressions

In reply to Johannes Berg

But still allow having a standalone symbol as the context expression, also evaluate the context change/requirement directly in the parser and pass them up as integers. Also fixes a number of bugs e.g. in the expression copier and a segfault when the default context is used as such:
__context__(1,1);

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

---
 evaluate.c           |    9 ++++++++-
 expand.c             |    2 +-
 inline.c             |   19 ++++++++++++-------
 linearize.c          |   17 +++--------------
 parse.c              |   22 +++++++++++++---------
 parse.h              |    6 ++++--
 validation/context.c |   28 ++++++++++++++++++++++++++++
 7 files changed, 69 insertions(+), 34 deletions(-)

evaluate.c +8 -1

@@ -3356,7 +3356,14 @@ struct symbol *evaluate_statement(struct
 		evaluate_asm_statement(stmt);
 		return NULL;
 	case STMT_CONTEXT:
-		evaluate_expression(stmt->expression);
+		/*
+		 * If this is an unknown symbol accept it as-is
+		 * as a context name.
+		 */
+		if (stmt->context &&
+		    (stmt->context->type != EXPR_SYMBOL ||
+		     stmt->context->symbol))
+			evaluate_expression(stmt->context);
 		return NULL;
 	case STMT_RANGE:
 		evaluate_expression(stmt->range_expression);

expand.c +1 -1

@@ -1169,7 +1169,7 @@ static int expand_statement(struct state
 		/* FIXME! Do the asm parameter evaluation! */
 		break;
 	case STMT_CONTEXT:
-		expand_expression(stmt->expression);
+		expand_expression(stmt->context);
 		break;
 	case STMT_RANGE:
 		expand_expression(stmt->range_expression);

inline.c +12 -7

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

@@ -336,12 +347,6 @@ static struct statement *copy_one_statem
 			break;
 		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;
 	}

linearize.c +3 ~~-14~~

@@ -1753,22 +1753,11 @@ static pseudo_t linearize_inlined_call(s
 static pseudo_t linearize_context(struct entrypoint *ep, struct statement *stmt)
 {
 	struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
-	struct expression *expr = stmt->expression;
-	int value = 0;
 
-	if (expr->type == EXPR_VALUE)
-		value = expr->value;
+	insn->increment = stmt->change;
+	insn->inc_false = stmt->change;
 
-	insn->increment = value;
-	insn->inc_false = value;
-
-	expr = stmt->required;
-	value = 0;
-
-	if (expr && expr->type == EXPR_VALUE)
-		value = expr->value;
-
-	insn->required = value;
+	insn->required = stmt->required;
 	insn->exact = stmt->exact;
 
 	insn->context_expr = stmt->context;

parse.c +13 -9

@@ -1859,9 +1859,7 @@ static struct token *_parse_context_stat
 		token = token->next;
 	}
 
-	stmt->expression = args[0];
 	stmt->context = NULL;
-
 	stmt->exact = exact;
 
 	switch (argc) {

@@ -1869,21 +1867,27 @@ static struct token *_parse_context_stat
 		sparse_error(token->pos, "__context__ statement needs argument(s)");
 		return token;
 	case 1:
-		/* already done */
+		stmt->change = get_expression_value(args[0]);
 		break;
 	case 2:
-		if (args[0]->type != STMT_EXPRESSION) {
+		/*
+		 * We should actually check whether we can evalulate
+		 * it as a constant expression and if so use as the
+		 * 'change' value. I hope nobody gives a calculation
+		 * for the number.
+		 */
+		if (args[0]->type != EXPR_VALUE) {
 			stmt->context = args[0];
-			stmt->expression = args[1];
+			stmt->change = get_expression_value(args[1]);
 		} else {
-			stmt->expression = args[0];
-			stmt->required = args[1];
+			stmt->change = get_expression_value(args[0]);
+			stmt->required = get_expression_value(args[1]);
 		}
 		break;
 	case 3:
 		stmt->context = args[0];
-		stmt->expression = args[1];
-		stmt->required = args[2];
+		stmt->change = get_expression_value(args[1]);
+		stmt->required = get_expression_value(args[2]);
 		break;
 	default:
 		sparse_error(token->pos, "too many arguments for __context__ statement");

parse.h +4 -2

@@ -39,10 +39,12 @@ struct statement {
 			struct symbol *label;
 			struct statement *label_statement;
 		};
-		struct { /* __context__ */
+		struct { /* expression */
 			struct expression *expression;
+		};
+		struct { /* __context__ */
 			struct expression *context;
-			struct expression *required;
+			int change, required;
 			int exact;
 		};
 		struct /* return_statement */ {

validation/context.c +28 -0

@@ -395,6 +395,32 @@ static void good_require_caller(void)
     __context__(TEST,-1,1);
 }
 
+static void areq(void) __attribute__((context(1,2)))
+{
+	__context__(1,1);
+}
+
+static void good_reqlock(void)
+{
+	a();
+	areq();
+	r();
+	r();
+}
+
+static void warn_reqlock(void)
+{
+	areq();
+	r();
+}
+
+
+static void dummy1(void) __attribute__((context(p,0,1)))
+{
+        void *p;
+	__context__(p,1);
+}
+
 /*
  * check-name: Check -Wcontext
  *

@@ -433,5 +459,7 @@ context.c:360:10: warning: context probl
 context.c:360:10:    default context: wanted >= 1, got 0
 context.c:380:12: warning: context imbalance in 'warn_conditional': wrong count at exit
 context.c:380:12:    default context: wanted 0, got 1
+context.c:413:6: warning: context problem in 'warn_reqlock': 'areq' expected different context
+context.c:413:6:    default context: wanted >= 1, got 0
  * check-error-end
  */

Johannes Berg

author

2008-05-29 09:03 UTC #5 lore raw

PATCH 5/9 revert the conditional_context patch

In reply to Johannes Berg

This patch removes the conditional_context attribute again, it turned out that my attempt to do this was rather misguided and contrary to what I thought we do not gain anything at all over using macros for it as the kernel and the tests have been doing for a while.

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

---
 linearize.c                  |   32 +++++---
 linearize.h                  |    2 
 parse.c                      |   52 -------------
 sparse.1                     |    9 --
 sparse.c                     |   39 +++------
 symbol.h                     |    2 
 validation/context-dynamic.c |  171 -------------------------------------------
 7 files changed, 37 insertions(+), 270 deletions(-)

linearize.c +20 ~~-12~~

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

@@ -958,7 +958,7 @@ static pseudo_t linearize_store_gen(stru
 			continue;
 		insn = alloc_instruction(OP_CONTEXT, 0);
 		insn->required = context->in;
-		insn->increment = insn->inc_false = context->out - context->in;
+		insn->increment = context->out - context->in;
 		insn->context_expr = context->context;
 		insn->access_var = ad->source_type;
 		insn->exact = context->exact;

@@ -971,7 +971,7 @@ static pseudo_t linearize_store_gen(stru
 			continue;
 		insn = alloc_instruction(OP_CONTEXT, 0);
 		insn->required = context->in;
-		insn->increment = insn->inc_false = context->out - context->in;
+		insn->increment = context->out - context->in;
 		insn->context_expr = context->context;
 		insn->access_var = ad->result_type;
 		insn->exact = context->exact;

@@ -986,7 +986,7 @@ static pseudo_t linearize_store_gen(stru
 				continue;
 			insn = alloc_instruction(OP_CONTEXT, 0);
 			insn->required = context->in;
-			insn->increment = insn->inc_false = context->out - context->in;
+			insn->increment = context->out - context->in;
 			insn->context_expr = context->context;
 			insn->access_var = ad->address->sym;
 			insn->exact = context->exact;

@@ -1047,7 +1047,7 @@ static pseudo_t linearize_load_gen(struc
 			continue;
 		insn = alloc_instruction(OP_CONTEXT, 0);
 		insn->required = context->in;
-		insn->increment = insn->inc_false = context->out - context->in;
+		insn->increment = context->out - context->in;
 		insn->context_expr = context->context;
 		insn->access_var = ad->source_type;
 		insn->exact = context->exact;

@@ -1060,7 +1060,7 @@ static pseudo_t linearize_load_gen(struc
 			continue;
 		insn = alloc_instruction(OP_CONTEXT, 0);
 		insn->required = context->in;
-		insn->increment = insn->inc_false = context->out - context->in;
+		insn->increment = context->out - context->in;
 		insn->context_expr = context->context;
 		insn->access_var = ad->result_type;
 		insn->exact = context->exact;

@@ -1075,7 +1075,7 @@ static pseudo_t linearize_load_gen(struc
 				continue;
 			insn = alloc_instruction(OP_CONTEXT, 0);
 			insn->required = context->in;
-			insn->increment = insn->inc_false = context->out - context->in;
+			insn->increment = context->out - context->in;
 			insn->context_expr = context->context;
 			insn->access_var = ad->address->sym;
 			insn->exact = context->exact;

@@ -1320,12 +1320,21 @@ static pseudo_t linearize_call_expressio
 		FOR_EACH_PTR(ctype->contexts, context) {
 			int in = context->in;
 			int out = context->out;
-
-			if (out - in || context->out_false - in) {
+			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) {
 				insn = alloc_instruction(OP_CONTEXT, 0);
-				insn->increment = out - in;
+				insn->increment = context_diff;
 				insn->context_expr = context->context;
-				insn->inc_false = context->out_false - in;
 				add_one_insn(ep, insn);
 			}
 		} END_FOR_EACH_PTR(context);

@@ -1755,7 +1764,6 @@ static pseudo_t linearize_context(struct
 	struct instruction *insn = alloc_instruction(OP_CONTEXT, 0);
 
 	insn->increment = stmt->change;
-	insn->inc_false = stmt->change;
 
 	insn->required = stmt->required;
 	insn->exact = stmt->exact;

parse.c +0 ~~-52~~

82 lines not on this page · raw message

sparse.1 +0 -9

@@ -101,15 +101,6 @@ be required on both reads and writes) by
 the token "write" for an optional fourth argument:
 .BI __attribute__((context( expression , in_context , out_context , read|write )).
 
-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

sparse.c +15 ~~-24~~

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

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

@@ -62,7 +62,6 @@ static void context_add(struct context_c
 		add_ptr_list(ccl, found);
 	}
 	found->val += offs;
-	found->val_false += offs_false;
 }
 
 static int context_list_has(struct context_check_list *ccl,

@@ -73,12 +72,11 @@ static int context_list_has(struct conte
 	FOR_EACH_PTR(ccl, check) {
 		if (strcmp(c->name, check->name))
 			continue;
-		return check->val == c->val &&
-		       check->val_false == c->val_false;
+		return check->val == c->val;
 	} END_FOR_EACH_PTR(check);
 
 	/* not found is equal to 0 */
-	return c->val == 0 && c->val_false == 0;
+	return c->val == 0;
 }
 
 static int context_lists_equal(struct context_check_list *ccl1,

@@ -107,7 +105,7 @@ static struct context_check_list *checke
 	struct context_check *c;
 
 	FOR_EACH_PTR(ccl, c) {
-		context_add(&result, c->name, c->val_false, c->val_false);
+		context_add(&result, c->name, c->val);
 	} END_FOR_EACH_PTR(c);
 
 	return result;

@@ -140,7 +138,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, 0);
+		context_add(&ccl_cur, c1->name, 0);
 	} END_FOR_EACH_PTR(c1);
 
 	FOR_EACH_PTR(ccl_cur, c1) {

@@ -289,15 +287,14 @@ static int handle_context(struct entrypo
 		return -1;
 	}
 
-	context_add(combined, name, insn->increment, insn->inc_false);
+	context_add(combined, name, insn->increment);
 
 	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,
-			    int in_false)
+			    struct context_check_list *ccl_target)
 {
 	struct context_check_list *combined = NULL, *done;
 	struct context_check *c;

@@ -327,10 +324,7 @@ static int check_bb_context(struct entry
 	 * 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);
-		else
-			context_add(&combined, c->name, c->val, c->val);
+		context_add(&combined, c->name, c->val);
 	} END_FOR_EACH_PTR(c);
 
 	/* Add the new context to the list of already-checked contexts */

@@ -356,18 +350,18 @@ static int check_bb_context(struct entry
 		case OP_BR:
 			if (insn->bb_true)
 				if (check_bb_context(ep, insn->bb_true,
-						     combined, ccl_target, 0))
+						     combined, ccl_target))
 					goto out;
 			if (insn->bb_false)
 				if (check_bb_context(ep, insn->bb_false,
-						     combined, ccl_target, 1))
+						     combined, ccl_target))
 					goto out;
 			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))
+					             combined, ccl_target))
 					goto out;
 			} END_FOR_EACH_PTR(mj);
 			break;

@@ -579,14 +573,11 @@ 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->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;
+		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, ccl_in, ccl_target, 0);
+	check_bb_context(ep, ep->entry->bb, ccl_in, ccl_target);
 	free_ptr_list(&ccl_in);
 	free_ptr_list(&ccl_target);
 	free_bb_context_lists(ep->entry->bb);

symbol.h +1 -1

@@ -77,7 +77,7 @@ enum context_read_write_specifier {
 
 struct context {
 	struct expression *context;
-	unsigned int in, out, out_false;
+	unsigned int in, out;
 	int exact;
 	enum context_read_write_specifier rws;
 };

validation/context-dynamic.c deleted +0 ~~-171~~

171 lines not on this page · raw message

linearize.h +1 -1

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

Johannes Berg

author

2008-05-29 09:03 UTC #6 lore raw

PATCH 6/9 check context expressions as expressions

In reply to Johannes Berg

This patch makes sparse evaluate context expressions allowing this:

    struct test {
        lock_t lock;
        int i;
    };

    extern void r(struct test *t) __attribute__((context(&t->lock,0,1)));
    extern struct test *find(int i) __attribute__((context(&RESULT->lock,1,0)));

    void test(void)
    {
       struct test *x = find(42);
       r(x);
       r(x);
    }

to work the way you think it would.

This works by rewriting the given attribute expression into __context__ statements and evaluating those in the caller scope.

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

---
Somewhat inspired by Philipp's patch. When it warns, the expression is given as evaluated, e.g. in above case would result in a warning about "**x+0". We can fix that later by keeping the original expression and not expanding/evaluating it, but we need to do both for it to work.

Note that there's a problem: You cannot give RESULT on a static function that is declared there without getting an error in the function itself...

 evaluate.c                |   18 ++-
 expand.c                  |    6 +
 expression.c              |  272 +++++++++++++++++++++++++++++++++++++++++++++-
 expression.h              |    7 +
 ident-list.h              |    1 
 inline.c                  |    4 
 linearize.c               |   63 ++++++----
 linearize.h               |    1 
 parse.c                   |   17 ++
 parse.h                   |    1 
 sparse.c                  |  144 ++++++------------------
 symbol.h                  |    4 
 validation/context-vars.c |  171 ++++++++++++++++++++++++++++
 13 files changed, 575 insertions(+), 134 deletions(-)

expression.c +271 -1

@@ -27,6 +27,8 @@
 #include "expression.h"
 #include "target.h"
 
+struct expression *current_assignment_expression = NULL;
+
 static int match_oplist(int op, ...)
 {
 	va_list args;

@@ -509,6 +511,63 @@ static struct token *expression_list(str
 	return token;
 }
 
+static int ident_equal(struct ident *ident1, struct ident *ident2)
+{
+	if (ident1 == ident2)
+		return 1;
+	if (!ident1 || !ident2)
+		return 0;
+
+	return ident1->len == ident2->len &&
+		!strncmp(ident1->name, ident2->name, ident1->len);
+}
+
+/* TODO: this is probably not complete */
+void replace_ident(struct expression **_in, struct ident *s, struct expression *r)
+{
+	struct expression *in = *_in;
+
+	switch (in->type) {
+	case EXPR_SYMBOL:
+		if (ident_equal(in->symbol_name, s))
+			*_in = r;
+		break;
+	case EXPR_IDENTIFIER:
+		if (ident_equal(in->expr_ident, s))
+			*_in = r;
+		break;
+	case EXPR_BINOP:
+	case EXPR_COMMA:
+	case EXPR_ASSIGNMENT:
+	case EXPR_COMPARE:
+	case EXPR_LOGICAL:
+		replace_ident(&in->left, s, r);
+		replace_ident(&in->right, s, r);
+		break;
+	case EXPR_DEREF:
+		replace_ident(&in->deref, s, r);
+		break;
+	case EXPR_PREOP:
+	case EXPR_POSTOP:
+		replace_ident(&in->unop, s, r);
+		break;
+	case EXPR_CAST:
+	case EXPR_FORCE_CAST:
+	case EXPR_IMPLIED_CAST:
+	case EXPR_SIZEOF:
+		replace_ident(&in->cast_expression, s, r);
+		break;
+	case EXPR_SLICE:
+		replace_ident(&in->base, s, r);
+		break;
+	case EXPR_CONDITIONAL:
+		replace_ident(&in->conditional, s, r);
+		replace_ident(&in->cond_true, s, r);
+		replace_ident(&in->cond_false, s, r);
+		break;
+	}
+}
+
 /*
  * extend to deal with the ambiguous C grammar for parsing
  * a cast expressions followed by an initializer.

@@ -570,10 +629,50 @@ static struct token *postfix_expression(
 
 		case '(': {			/* Function call */
 			struct expression *call = alloc_expression(token->pos, EXPR_CALL);
+			struct symbol *fn = NULL;
+			struct context *c;
+
+			if (expr->symbol_name)
+				fn = lookup_symbol(expr->symbol_name, NS_SYMBOL);
 			call->op = '(';
 			call->fn = expr;
 			token = expression_list(token->next, &call->args);
 			token = expect(token, ')', "in function call");
+
+			if (fn && fn->ctype.base_type) {
+				FOR_EACH_PTR(fn->ctype.contexts, c) {
+					struct context *copy = alloc_context();
+					struct symbol *fn_arg;
+					struct expression *passed_arg;
+
+					copy->in = c->in;
+					copy->out = c->out;
+					copy->exact = c->exact;
+					add_ptr_list(&call->contexts, copy);
+
+					if (!c->token)
+						continue;
+
+					/* re-parse the token at this place */
+					conditional_expression(c->token, &copy->context);
+
+					copy->context->pos = expr->pos;
+
+					if (current_assignment_expression)
+						replace_ident(&copy->context, &RESULT_ident,
+							      current_assignment_expression);
+
+					/* and replace the arg */
+					PREPARE_PTR_LIST(fn->ctype.base_type->arguments, fn_arg);
+					FOR_EACH_PTR(call->args, passed_arg);
+					if (fn_arg)
+						replace_ident(&copy->context, fn_arg->ident, passed_arg);
+					NEXT_PTR_LIST(fn_arg);
+					END_FOR_EACH_PTR(passed_arg);
+					FINISH_PTR_LIST(fn_arg);
+				} END_FOR_EACH_PTR(c);
+			}
+
 			expr = call;
 			continue;
 		}

@@ -894,6 +993,7 @@ struct token *conditional_expression(str
 
 struct token *assignment_expression(struct token *token, struct expression **tree)
 {
+	struct expression *old_cae = current_assignment_expression;
 	token = conditional_expression(token, tree);
 	if (*tree && token_type(token) == TOKEN_SPECIAL) {
 		static const int assignments[] = {

@@ -904,15 +1004,19 @@ struct token *assignment_expression(stru
 			SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 			SPECIAL_OR_ASSIGN,  SPECIAL_XOR_ASSIGN };
 		int i, op = token->special;
+		if (op == '=')
+			current_assignment_expression = *tree;
 		for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 			if (assignments[i] == op) {
 				struct expression * expr = alloc_expression(token->pos, EXPR_ASSIGNMENT);
 				expr->left = *tree;
 				expr->op = op;
 				*tree = expr;
-				return assignment_expression(token->next, &expr->right);
+				token = assignment_expression(token->next, &expr->right);
+				break;
 			}
 	}
+	current_assignment_expression = old_cae;
 	return token;
 }

@@ -929,4 +1033,170 @@ struct token *parse_expression(struct to
 	return comma_expression(token,tree);
 }
 
+int expressions_equal(const struct expression *expr1,
+		      const struct expression *expr2)
+{
+	if (expr1 == expr2)
+		return 1;
+
+	if (expr1 == NULL || expr2 == NULL)
+		return 0;
+
+	/* Is this the right way to handle casts? */
+	if (expr1->type == EXPR_CAST ||
+	    expr1->type == EXPR_FORCE_CAST ||
+	    expr1->type == EXPR_IMPLIED_CAST)
+		return expressions_equal(expr1->cast_expression, expr2);
+
+	if (expr2->type == EXPR_CAST ||
+	    expr2->type == EXPR_FORCE_CAST ||
+	    expr2->type == EXPR_IMPLIED_CAST)
+		return expressions_equal(expr2->cast_expression, expr1);
+
+	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:
+		/* nothing, we should already have had a warning */
+		;
+	}
+
+	return 0;
+}
+
+static int ident_str(struct ident *ident, char *buffer, int length)
+{
+	if (!ident)
+		return 0;
+	return snprintf(buffer, length, "%.*s", ident->len, ident->name);
+}
+
+int expression_str(const struct expression *expr,
+		   char *buffer, int length)
+{
+	int n;
+
+	memset(buffer, 0, length);
+
+	if (!expr)
+		return 0;
+
+	/* TODO, think about necessary parentheses () */
 
+	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;
+
+	case EXPR_CAST:
+	case EXPR_FORCE_CAST:
+	case EXPR_IMPLIED_CAST:
+		/* todo: print out the cast type's ctype */
+		*buffer++ = '('; length--;
+		*buffer++ = ')'; length--;
+		return expression_str(expr->cast_expression, buffer, length) + 2;
+
+	default:
+		printf("Missing code in expression_str for %d\n", expr->type);
+	}
+
+	return 0;
+}

expression.h +7 -0

@@ -121,6 +121,7 @@ struct expression {
 		struct /* call_expr */ {
 			struct expression *fn;
 			struct expression_list *args;
+			struct context_list *contexts;
 		};
 		// EXPR_LABEL
 		struct /* label_expr */ {

@@ -216,4 +217,10 @@ struct token *compound_statement(struct 
 void cast_value(struct expression *expr, struct symbol *newtype,
 	struct expression *old, struct symbol *oldtype);
 
+int expressions_equal(const struct expression *expr1,
+		      const struct expression *expr2);
+int expression_str(const struct expression *, char *buf, int buflen);
+struct expression *copy_expression(struct expression *expr);
+void replace_ident(struct expression **in, struct ident *s, struct expression *r);
+extern struct expression *current_assignment_expression;
 #endif

sparse.c +39 ~~-105~~

272 lines not on this page · raw message

validation/context-vars.c new file +171 -0

171 lines not on this page · raw message

evaluate.c +17 -1

@@ -2954,8 +2954,16 @@ struct symbol *evaluate_expression(struc
 		return evaluate_alignof(expr);
 	case EXPR_DEREF:
 		return evaluate_member_dereference(expr);
-	case EXPR_CALL:
+	case EXPR_CALL: {
+		struct context *c;
+		FOR_EACH_PTR(expr->contexts, c) {
+			if (c->context &&
+			    (c->context->type != EXPR_SYMBOL ||
+			     c->context->symbol))
+				evaluate_expression(c->context);
+		} END_FOR_EACH_PTR(c);
 		return evaluate_call(expr);
+	}
 	case EXPR_SELECT:
 	case EXPR_CONDITIONAL:
 		return evaluate_conditional_expression(expr);

@@ -3025,6 +3033,7 @@ static void check_duplicates(struct symb
 static struct symbol *evaluate_symbol(struct symbol *sym)
 {
 	struct symbol *base_type;
+	struct context *c;
 
 	if (!sym)
 		return sym;

@@ -3054,6 +3063,13 @@ static struct symbol *evaluate_symbol(st
 			evaluate_statement(base_type->stmt);
 
 		current_fn = curr;
+
+		FOR_EACH_PTR(sym->ctype.contexts, c) {
+		if (c->in_fn &&
+		    (c->in_fn->type != EXPR_SYMBOL ||
+		     c->in_fn->symbol))
+			evaluate_expression(c->in_fn);
+		} END_FOR_EACH_PTR(c);
 	}
 
 	return base_type;

expand.c +6 -0

@@ -1034,8 +1034,14 @@ int expand_symbol(struct symbol *sym)
 	retval = expand_expression(sym->initializer);
 	/* expand the body of the symbol */
 	if (base_type->type == SYM_FN) {
+		struct context *c;
+
 		if (base_type->stmt)
 			expand_statement(base_type->stmt);
+
+		FOR_EACH_PTR(sym->ctype.contexts, c) {
+			expand_expression(c->in_fn);
+		} END_FOR_EACH_PTR(c);
 	}
 	return retval;
 }

parse.c +16 -1

@@ -879,12 +879,13 @@ static struct token *_attribute_context(
 	struct context *context = alloc_context();
 	struct expression *args[4];
 	int argc = 0;
-	struct token *last = NULL;
+	struct token *first = NULL, *last = NULL;
 
 	token = expect(token, '(', "after context attribute");
 	while (!match_op(token, ')')) {
 		struct expression *expr = NULL;
 		last = token;
+		first = first ? : token;
 		token = conditional_expression(token, &expr);
 		if (!expr)
 			break;

@@ -910,12 +911,14 @@ static struct token *_attribute_context(
 		break;
 	case 3:
 		context->context = args[0];
+		context->token = first;
 		context->in = get_expression_value(args[1]);
 		context->out = get_expression_value(args[2]);
 		break;
 	case 4: {
 		const char *rw;
 		context->context = args[0];
+		context->token = first;
 		context->in = get_expression_value(args[1]);
 		context->out = get_expression_value(args[2]);

@@ -2096,6 +2099,7 @@ static struct token *parse_function_body
 	struct symbol *base_type = decl->ctype.base_type;
 	struct statement *stmt, **p;
 	struct symbol *arg;
+	struct context *c;
 
 	old_symbol_list = function_symbol_list;
 	if (decl->ctype.modifiers & MOD_INLINE) {

@@ -2124,6 +2128,11 @@ static struct token *parse_function_body
 
 	token = compound_statement(token->next, stmt);
 
+	FOR_EACH_PTR(decl->ctype.contexts, c) {
+		if (c->token)
+			conditional_expression(c->token, &c->in_fn);
+	} END_FOR_EACH_PTR(c);
+
 	end_function(decl);
 	if (!(decl->ctype.modifiers & MOD_INLINE))
 		add_symbol(list, decl);

@@ -2286,11 +2295,17 @@ struct token *external_declaration(struc
 
 	for (;;) {
 		if (!is_typedef && match_op(token, '=')) {
+			struct expression *old_cae = current_assignment_expression;
 			if (decl->ctype.modifiers & MOD_EXTERN) {
 				warning(decl->pos, "symbol with external linkage has initializer");
 				decl->ctype.modifiers &= ~MOD_EXTERN;
 			}
+			current_assignment_expression = alloc_expression(token->pos, EXPR_SYMBOL);
+			current_assignment_expression->symbol_name = decl->ident;
+			current_assignment_expression->symbol =
+				lookup_symbol(decl->ident, NS_SYMBOL | NS_TYPEDEF);
 			token = initializer(&decl->initializer, token->next);
+			current_assignment_expression = old_cae;
 		}
 		if (!is_typedef) {
 			if (!(decl->ctype.modifiers & (MOD_EXTERN | MOD_INLINE))) {

symbol.h +4 -0

@@ -77,6 +77,10 @@ enum context_read_write_specifier {
 
 struct context {
 	struct expression *context;
+	/* store the token pointer */
+	struct token *token;
+	/* to re-evaluate this context within the function it is for */
+	struct expression *in_fn;
 	unsigned int in, out;
 	int exact;
 	enum context_read_write_specifier rws;

inline.c +3 -1

@@ -56,7 +56,7 @@ static struct symbol_list *copy_symbol_l
 	return dst;
 }
 
-static struct expression * copy_expression(struct expression *expr)
+struct expression *copy_expression(struct expression *expr)
 {
 	if (!expr)
 		return NULL;

@@ -474,6 +474,7 @@ void copy_statement(struct statement *sr
 	dst->args = copy_one_statement(src->args);
 	dst->ret = copy_symbol(src->pos, src->ret);
 	dst->inline_fn = src->inline_fn;
+	dst->inlined_fn_expr = src->inlined_fn_expr;
 }
 
 static struct symbol *create_copy_symbol(struct symbol *orig)

@@ -555,6 +556,7 @@ int inline_function(struct expression *e
 		stmt->args = decl;
 	}
 	stmt->inline_fn = sym;
+	stmt->inlined_fn_expr = expr;
 
 	unset_replace_list(fn_symbol_list);

linearize.c +38 ~~-25~~

113 lines not on this page · raw message

parse.h +1 -0

@@ -61,6 +61,7 @@ struct statement {
 			struct symbol *ret;
 			struct symbol *inline_fn;
 			struct statement *args;
+			struct expression *inlined_fn_expr;
 		};
 		struct /* labeled_struct */ {
 			struct symbol *label_identifier;

linearize.h +1 -0

@@ -119,6 +119,7 @@ struct instruction {
 			int increment, required, exact;
 			struct expression *context_expr;
 			struct symbol *access_var;
+			struct symbol *called_fn;
 		};
 		struct /* asm */ {
 			const char *string;

ident-list.h +1 -0

@@ -98,6 +98,7 @@ __IDENT(__PRETTY_FUNCTION___ident, "__PR
 IDENT_RESERVED(__context__);
 IDENT_RESERVED(__exact_context__);
 IDENT_RESERVED(__range__);
+IDENT_RESERVED(RESULT);
 
 /* Magic function names we recognize */
 IDENT(memset); IDENT(memcpy);

Johannes Berg

author

2008-09-10 07:33 UTC #7 lore raw

PATCH v2 6/9 check context expressions as expressions

This patch makes sparse evaluate context expressions allowing this:

    struct test {
        lock_t lock;
        int i;
    };

    extern void r(struct test *t) __attribute__((context(&t->lock,0,1)));
    extern struct test *find(int i) __attribute__((context(&RESULT->lock,1,0)));

    void test(void)
    {
       struct test *x = find(42);
       r(x);
       r(x);
    }

to work the way you think it would.

This works by rewriting the given attribute expression into __context__ statements and evaluating those in the caller scope.

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

Note that there's a problem: You cannot give RESULT on a static function that is declared there without getting an error in the function itself...

v2: Harvey found a bug in this by running it on the Linux kernel and
I also cleaned up some functions and made them static.

 evaluate.c                |   18 ++-
 expand.c                  |    6 +
 expression.c              |  271 +++++++++++++++++++++++++++++++++++++++++++++-
 expression.h              |    5 
 ident-list.h              |    1 
 inline.c                  |    4 
 linearize.c               |   63 ++++++----
 linearize.h               |    1 
 parse.c                   |   17 ++
 parse.h                   |    1 
 sparse.c                  |  144 ++++++------------------
 symbol.h                  |    4 
 validation/context-vars.c |  171 +++++++++++++++++++++++++++++
 13 files changed, 572 insertions(+), 134 deletions(-)

expression.c +270 -1

@@ -27,6 +27,8 @@
 #include "expression.h"
 #include "target.h"
 
+struct expression *current_assignment_expression = NULL;
+
 static int match_oplist(int op, ...)
 {
 	va_list args;

@@ -509,6 +511,63 @@ static struct token *expression_list(str
 	return token;
 }
 
+static int ident_equal(struct ident *ident1, struct ident *ident2)
+{
+	if (ident1 == ident2)
+		return 1;
+	if (!ident1 || !ident2)
+		return 0;
+
+	return ident1->len == ident2->len &&
+		!strncmp(ident1->name, ident2->name, ident1->len);
+}
+
+/* TODO: this is probably not complete */
+static void replace_ident(struct expression **_in, struct ident *s, struct expression *r)
+{
+	struct expression *in = *_in;
+
+	switch (in->type) {
+	case EXPR_SYMBOL:
+		if (ident_equal(in->symbol_name, s))
+			*_in = r;
+		break;
+	case EXPR_IDENTIFIER:
+		if (ident_equal(in->expr_ident, s))
+			*_in = r;
+		break;
+	case EXPR_BINOP:
+	case EXPR_COMMA:
+	case EXPR_ASSIGNMENT:
+	case EXPR_COMPARE:
+	case EXPR_LOGICAL:
+		replace_ident(&in->left, s, r);
+		replace_ident(&in->right, s, r);
+		break;
+	case EXPR_DEREF:
+		replace_ident(&in->deref, s, r);
+		break;
+	case EXPR_PREOP:
+	case EXPR_POSTOP:
+		replace_ident(&in->unop, s, r);
+		break;
+	case EXPR_CAST:
+	case EXPR_FORCE_CAST:
+	case EXPR_IMPLIED_CAST:
+	case EXPR_SIZEOF:
+		replace_ident(&in->cast_expression, s, r);
+		break;
+	case EXPR_SLICE:
+		replace_ident(&in->base, s, r);
+		break;
+	case EXPR_CONDITIONAL:
+		replace_ident(&in->conditional, s, r);
+		replace_ident(&in->cond_true, s, r);
+		replace_ident(&in->cond_false, s, r);
+		break;
+	}
+}
+
 /*
  * extend to deal with the ambiguous C grammar for parsing
  * a cast expressions followed by an initializer.

@@ -570,10 +629,49 @@ static struct token *postfix_expression(
 
 		case '(': {			/* Function call */
 			struct expression *call = alloc_expression(token->pos, EXPR_CALL);
+			struct symbol *fn = NULL;
+			struct context *c;
+
+			if (expr->symbol_name)
+				fn = lookup_symbol(expr->symbol_name, NS_SYMBOL);
 			call->op = '(';
 			call->fn = expr;
 			token = expression_list(token->next, &call->args);
 			token = expect(token, ')', "in function call");
+			if (fn && fn->ctype.base_type) {
+				FOR_EACH_PTR(fn->ctype.contexts, c) {
+					struct context *copy = alloc_context();
+					struct symbol *fn_arg;
+					struct expression *passed_arg;
+
+					copy->in = c->in;
+					copy->out = c->out;
+					copy->exact = c->exact;
+					add_ptr_list(&call->contexts, copy);
+
+					if (!c->token)
+						continue;
+
+					/* re-parse the token at this place */
+					conditional_expression(c->token, &copy->context);
+
+					copy->context->pos = expr->pos;
+
+					if (current_assignment_expression)
+						replace_ident(&copy->context, &RESULT_ident,
+							      current_assignment_expression);
+
+					/* and replace the arg */
+					PREPARE_PTR_LIST(fn->ctype.base_type->arguments, fn_arg);
+					FOR_EACH_PTR(call->args, passed_arg);
+					if (fn_arg && passed_arg->type != EXPR_CALL)
+						replace_ident(&copy->context, fn_arg->ident, passed_arg);
+					NEXT_PTR_LIST(fn_arg);
+					END_FOR_EACH_PTR(passed_arg);
+					FINISH_PTR_LIST(fn_arg);
+				} END_FOR_EACH_PTR(c);
+			}
+
 			expr = call;
 			continue;
 		}

@@ -894,6 +992,7 @@ struct token *conditional_expression(str
 
 struct token *assignment_expression(struct token *token, struct expression **tree)
 {
+	struct expression *old_cae = current_assignment_expression;
 	token = conditional_expression(token, tree);
 	if (*tree && token_type(token) == TOKEN_SPECIAL) {
 		static const int assignments[] = {

@@ -904,15 +1003,19 @@ struct token *assignment_expression(stru
 			SPECIAL_SHR_ASSIGN, SPECIAL_AND_ASSIGN,
 			SPECIAL_OR_ASSIGN,  SPECIAL_XOR_ASSIGN };
 		int i, op = token->special;
+		if (op == '=')
+			current_assignment_expression = *tree;
 		for (i = 0; i < sizeof(assignments)/sizeof(int); i++)
 			if (assignments[i] == op) {
 				struct expression * expr = alloc_expression(token->pos, EXPR_ASSIGNMENT);
 				expr->left = *tree;
 				expr->op = op;
 				*tree = expr;
-				return assignment_expression(token->next, &expr->right);
+				token = assignment_expression(token->next, &expr->right);
+				break;
 			}
 	}
+	current_assignment_expression = old_cae;
 	return token;
 }

@@ -929,4 +1032,170 @@ struct token *parse_expression(struct to
 	return comma_expression(token,tree);
 }
 
+int expressions_equal(const struct expression *expr1,
+		      const struct expression *expr2)
+{
+	if (expr1 == expr2)
+		return 1;
+
+	if (expr1 == NULL || expr2 == NULL)
+		return 0;
 
+	/* Is this the right way to handle casts? */
+	if (expr1->type == EXPR_CAST ||
+	    expr1->type == EXPR_FORCE_CAST ||
+	    expr1->type == EXPR_IMPLIED_CAST)
+		return expressions_equal(expr1->cast_expression, expr2);
+
+	if (expr2->type == EXPR_CAST ||
+	    expr2->type == EXPR_FORCE_CAST ||
+	    expr2->type == EXPR_IMPLIED_CAST)
+		return expressions_equal(expr2->cast_expression, expr1);
+
+	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:
+		/* nothing, we should already have had a warning */
+		;
+	}
+
+	return 0;
+}
+
+static int ident_str(struct ident *ident, char *buffer, int length)
+{
+	if (!ident)
+		return 0;
+	return snprintf(buffer, length, "%.*s", ident->len, ident->name);
+}
+
+int expression_str(const struct expression *expr,
+		   char *buffer, int length)
+{
+	int n;
+
+	memset(buffer, 0, length);
+
+	if (!expr)
+		return 0;
+
+	/* TODO, think about necessary parentheses () */
+
+	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;
+
+	case EXPR_CAST:
+	case EXPR_FORCE_CAST:
+	case EXPR_IMPLIED_CAST:
+		/* todo: print out the cast type's ctype */
+		*buffer++ = '('; length--;
+		*buffer++ = ')'; length--;
+		return expression_str(expr->cast_expression, buffer, length) + 2;
+
+	default:
+		printf("Missing code in expression_str for %d\n", expr->type);
+	}
+
+	return 0;
+}

expression.h +5 -0

@@ -121,6 +121,7 @@ struct expression {
 		struct /* call_expr */ {
 			struct expression *fn;
 			struct expression_list *args;
+			struct context_list *contexts;
 		};
 		// EXPR_LABEL
 		struct /* label_expr */ {

@@ -216,4 +217,8 @@ struct token *compound_statement(struct 
 void cast_value(struct expression *expr, struct symbol *newtype,
 	struct expression *old, struct symbol *oldtype);
 
+int expressions_equal(const struct expression *expr1,
+		      const struct expression *expr2);
+int expression_str(const struct expression *, char *buf, int buflen);
+extern struct expression *current_assignment_expression;
 #endif

sparse.c +39 ~~-105~~

272 lines not on this page · raw message

validation/context-vars.c new file +171 -0

171 lines not on this page · raw message

evaluate.c +17 -1

@@ -2954,8 +2954,16 @@ struct symbol *evaluate_expression(struc
 		return evaluate_alignof(expr);
 	case EXPR_DEREF:
 		return evaluate_member_dereference(expr);
-	case EXPR_CALL:
+	case EXPR_CALL: {
+		struct context *c;
+		FOR_EACH_PTR(expr->contexts, c) {
+			if (c->context &&
+			    (c->context->type != EXPR_SYMBOL ||
+			     c->context->symbol))
+				evaluate_expression(c->context);
+		} END_FOR_EACH_PTR(c);
 		return evaluate_call(expr);
+	}
 	case EXPR_SELECT:
 	case EXPR_CONDITIONAL:
 		return evaluate_conditional_expression(expr);

@@ -3025,6 +3033,7 @@ static void check_duplicates(struct symb
 static struct symbol *evaluate_symbol(struct symbol *sym)
 {
 	struct symbol *base_type;
+	struct context *c;
 
 	if (!sym)
 		return sym;

@@ -3054,6 +3063,13 @@ static struct symbol *evaluate_symbol(st
 			evaluate_statement(base_type->stmt);
 
 		current_fn = curr;
+
+		FOR_EACH_PTR(sym->ctype.contexts, c) {
+		if (c->in_fn &&
+		    (c->in_fn->type != EXPR_SYMBOL ||
+		     c->in_fn->symbol))
+			evaluate_expression(c->in_fn);
+		} END_FOR_EACH_PTR(c);
 	}
 
 	return base_type;

expand.c +6 -0

@@ -1034,8 +1034,14 @@ int expand_symbol(struct symbol *sym)
 	retval = expand_expression(sym->initializer);
 	/* expand the body of the symbol */
 	if (base_type->type == SYM_FN) {
+		struct context *c;
+
 		if (base_type->stmt)
 			expand_statement(base_type->stmt);
+
+		FOR_EACH_PTR(sym->ctype.contexts, c) {
+			expand_expression(c->in_fn);
+		} END_FOR_EACH_PTR(c);
 	}
 	return retval;
 }

parse.c +16 -1

@@ -879,12 +879,13 @@ static struct token *_attribute_context(
 	struct context *context = alloc_context();
 	struct expression *args[4];
 	int argc = 0;
-	struct token *last = NULL;
+	struct token *first = NULL, *last = NULL;
 
 	token = expect(token, '(', "after context attribute");
 	while (!match_op(token, ')')) {
 		struct expression *expr = NULL;
 		last = token;
+		first = first ? : token;
 		token = conditional_expression(token, &expr);
 		if (!expr)
 			break;

@@ -910,12 +911,14 @@ static struct token *_attribute_context(
 		break;
 	case 3:
 		context->context = args[0];
+		context->token = first;
 		context->in = get_expression_value(args[1]);
 		context->out = get_expression_value(args[2]);
 		break;
 	case 4: {
 		const char *rw;
 		context->context = args[0];
+		context->token = first;
 		context->in = get_expression_value(args[1]);
 		context->out = get_expression_value(args[2]);

@@ -2096,6 +2099,7 @@ static struct token *parse_function_body
 	struct symbol *base_type = decl->ctype.base_type;
 	struct statement *stmt, **p;
 	struct symbol *arg;
+	struct context *c;
 
 	old_symbol_list = function_symbol_list;
 	if (decl->ctype.modifiers & MOD_INLINE) {

@@ -2124,6 +2128,11 @@ static struct token *parse_function_body
 
 	token = compound_statement(token->next, stmt);
 
+	FOR_EACH_PTR(decl->ctype.contexts, c) {
+		if (c->token)
+			conditional_expression(c->token, &c->in_fn);
+	} END_FOR_EACH_PTR(c);
+
 	end_function(decl);
 	if (!(decl->ctype.modifiers & MOD_INLINE))
 		add_symbol(list, decl);

@@ -2286,11 +2295,17 @@ struct token *external_declaration(struc
 
 	for (;;) {
 		if (!is_typedef && match_op(token, '=')) {
+			struct expression *old_cae = current_assignment_expression;
 			if (decl->ctype.modifiers & MOD_EXTERN) {
 				warning(decl->pos, "symbol with external linkage has initializer");
 				decl->ctype.modifiers &= ~MOD_EXTERN;
 			}
+			current_assignment_expression = alloc_expression(token->pos, EXPR_SYMBOL);
+			current_assignment_expression->symbol_name = decl->ident;
+			current_assignment_expression->symbol =
+				lookup_symbol(decl->ident, NS_SYMBOL | NS_TYPEDEF);
 			token = initializer(&decl->initializer, token->next);
+			current_assignment_expression = old_cae;
 		}
 		if (!is_typedef) {
 			if (!(decl->ctype.modifiers & (MOD_EXTERN | MOD_INLINE))) {

symbol.h +4 -0

@@ -77,6 +77,10 @@ enum context_read_write_specifier {
 
 struct context {
 	struct expression *context;
+	/* store the token pointer */
+	struct token *token;
+	/* to re-evaluate this context within the function it is for */
+	struct expression *in_fn;
 	unsigned int in, out;
 	int exact;
 	enum context_read_write_specifier rws;

inline.c +3 -1

@@ -56,7 +56,7 @@ static struct symbol_list *copy_symbol_l
 	return dst;
 }
 
-static struct expression * copy_expression(struct expression *expr)
+static struct expression *copy_expression(struct expression *expr)
 {
 	if (!expr)
 		return NULL;

@@ -474,6 +474,7 @@ void copy_statement(struct statement *sr
 	dst->args = copy_one_statement(src->args);
 	dst->ret = copy_symbol(src->pos, src->ret);
 	dst->inline_fn = src->inline_fn;
+	dst->inlined_fn_expr = src->inlined_fn_expr;
 }
 
 static struct symbol *create_copy_symbol(struct symbol *orig)

@@ -555,6 +556,7 @@ int inline_function(struct expression *e
 		stmt->args = decl;
 	}
 	stmt->inline_fn = sym;
+	stmt->inlined_fn_expr = expr;
 
 	unset_replace_list(fn_symbol_list);

linearize.c +38 ~~-25~~

113 lines not on this page · raw message

parse.h +1 -0

@@ -61,6 +61,7 @@ struct statement {
 			struct symbol *ret;
 			struct symbol *inline_fn;
 			struct statement *args;
+			struct expression *inlined_fn_expr;
 		};
 		struct /* labeled_struct */ {
 			struct symbol *label_identifier;

linearize.h +1 -0

@@ -119,6 +119,7 @@ struct instruction {
 			int increment, required, exact;
 			struct expression *context_expr;
 			struct symbol *access_var;
+			struct symbol *called_fn;
 		};
 		struct /* asm */ {
 			const char *string;

ident-list.h +1 -0

@@ -98,6 +98,7 @@ __IDENT(__PRETTY_FUNCTION___ident, "__PR
 IDENT_RESERVED(__context__);
 IDENT_RESERVED(__exact_context__);
 IDENT_RESERVED(__range__);
+IDENT_RESERVED(RESULT);
 
 /* Magic function names we recognize */
 IDENT(memset); IDENT(memcpy);

Christopher Li

maintainer

2008-09-10 19:21 UTC #8 lore raw

Re: [PATCH 6/9 v2] check context expressions as expressions

expression.c static struct token *expression_list(str · line 523

Quoted 10 lines · Johannes Berg

expression.c +10 -0

+static int ident_equal(struct ident *ident1, struct ident *ident2)
+{
+       if (ident1 == ident2)
+               return 1;
+       if (!ident1 || !ident2)
+               return 0;
+
+       return ident1->len == ident2->len &&
+               !strncmp(ident1->name, ident2->name, ident1->len);
+}

Nah, you pretty should never need to do that. Ident equal should just need to compare ident1 == ident2.

All ident has been hashed. Same ident, should show up as same pointer. Doing strncmp again is unnecessary.

I feel that this patch is adding too much hack to the sparse front end. At the very least, can you
just change __context__ parsing to accept symbol expression and the let the checking back end to do the code motions stuff?

I haven't study the new context checking very carefully. I actually prefer the Linus's old simple context checking. Yes, that does not distinguish which symbols taking the lock. But other than that it is working and counting the number correctly. And, it is very simple.

The new context checking seems able to do more features. But it has too many sore spots. I vote for back it out.

Instead of keep adding more hacks to fix up the problem. I think we should step back and ask ourselves what do we really want to achieve.

The fundamental problem I saw here is that, sparse does not support cross function checking. There is no good way to save some analyzed result for some function and used it later by other function. That is why we actually have to put __context__ around so many functions. The __context__ describe what these functions in forms of source code annotation. There is only so much we can do with source code annotations.
I am not saying that annotation is not useful. I agree source code annotation helps on the source code reading. But it shouldn't limit checker only use the annotations. The checker should be able to draw intelligent conclusions, by looking the the function source code itself.

e.g. Why do we have to annotate foo_lock(&bar->lock) will take a lock on &bar->lock? The checker should be able to find out foo_lock() just callers some lower level locking functions. For example, let say if we can force foo to be inlined into the caller even foo is not declared as inline. Then there is no need to annotate foo itself. The caller see exactly what foo does.

So, I think we should implement cross functions checking capability systematically rather than putting more hacks on source code annotation. The writer patch I send out earlier is one step towards it. I will write up more detail proposal.

Chris

Johannes Berg

author

2008-09-10 21:35 UTC #9 lore raw

Re: [PATCH 6/9 v2] check context expressions as expressions

Quoted 11 lines · Christopher Li

Nah, you pretty should never need to do that. Ident equal should just need to compare ident1 == ident2.
All ident has been hashed. Same ident, should show up as same pointer. Doing strncmp again is unnecessary.
I feel that this patch is adding too much hack to the sparse front end. At the very least, can you
just change __context__ parsing to accept symbol expression and the let the checking back end to do the code motions stuff?

Can you explain?

Quoted 5 lines

I haven't study the new context checking very carefully. I actually prefer the Linus's old simple context checking. Yes, that does not distinguish which symbols taking the lock. But other than that it is working and counting the number correctly. And, it is very simple.

Well, yeah, it's very simple, and that doesn't help. And it's not about cross-function checking either:

extern spinlock_t a;

spin_lock(&a);
rcu_read_unlock()

will not result in an error which is a pain.

Quoted 2 lines

The new context checking seems able to do more features. But it has too many sore spots. I vote for back it out.

I don't care, I don't have any more cycles to burn on this. For all I'm concerned it works pretty well and is a HUGE improvement over the current sparse which
* doesn't tell you what line the error really is in, it only warns about the last line of the function
* isn't able to check different contexts despite documenting it (see above)

Quoted 3 lines

Instead of keep adding more hacks to fix up the problem. I think we should step back and ask ourselves what do we really want to achieve.

See above.

Quoted 4 lines

The fundamental problem I saw here is that, sparse does not support cross function checking. There is no good way to save some analyzed result for some function and used it later by other function. That is why we actually have to put __context__

Quoted 8 lines

around so many functions. The __context__ describe what these functions in forms of source code annotation. There is only so much we can do with source code annotations. I am not saying that annotation is not useful. I agree source code annotation helps on the source code reading. But it shouldn't limit checker only use the annotations. The checker should be able to draw intelligent conclusions, by looking the the function source code itself.

Actually, I kinda disagree. Annotating *each and every function* with the locks it requires is _very_ useful, not just for sparse but also for human readers of the code. Hence, I don't just want sparse to check across functions, I want to be able to tell people what to do for calling a given function as well. The fact that sparse can check my annotations is great, but having them would be useful without that as well.

Quoted 6 lines

e.g. Why do we have to annotate foo_lock(&bar->lock) will take a lock on &bar->lock? The checker should be able to find out foo_lock() just callers some lower level locking functions. For example, let say if we can force foo to be inlined into the caller even foo is not declared as inline. Then there is no need to annotate foo itself. The caller see exactly what foo does.

It used to be like that. But I'm arguing (and others backed me up on this) that inlines are really just functions and as such should be annotated, not magically inlined into the code and then checked as sparse behaves right now.

Quoted 4 lines

So, I think we should implement cross functions checking capability systematically rather than putting more hacks on source code annotation. The writer patch I send out earlier is one step towards it. I will write up more detail proposal.

Please don't focus on cross-function checking so much. Having different contexts is way more desirable, and cross-function checking probably is _not_ desirable in that you _want_ the annotations.

johannes

Christopher Li

maintainer

2008-09-11 00:15 UTC #10 lore raw

Re: [PATCH 6/9 v2] check context expressions as expressions

Quoted 7 lines · Johannes Berg

Quoted 5 lines
I feel that this patch is adding too much hack to the sparse front end. At the very least, can you
just change __context__ parsing to accept symbol expression and the let the checking back end to do the code motions stuff?
Can you explain?

Maybe you can help to explain why do you need to make so many front end(parser) changes. I especially don't like the part that does the replace ident.

From what I can tell, you just need to know that context are using the same expression on accessing the locks. Let's put aside that it is right assumption or not. From the back end side, you should able to get to all the expression and verify they are the same without doing much front end changes.

All the code for "expression is equal test" should be move to back end using linearized byte code. As matter of fact, sparse have a simple common expression eliminate already.

Quoted 7 lines

Well, yeah, it's very simple, and that doesn't help. And it's not about cross-function checking either:
extern spinlock_t a;
spin_lock(&a);
rcu_read_unlock()

As I said, it is simple and does not take into account of which symbol take the lock. But using same expression is not solid either. How about:
extern spinlock_t a;

spinlock_t *p = &a;

spin_lock(&a);
spin_unlock(p);

Quoted 5 lines

will not result in an error which is a pain.
Quoted 2 lines
The new context checking seems able to do more features. But it has too many sore spots. I vote for back it out.

Quoted 7 lines

I don't care, I don't have any more cycles to burn on this. For all I'm concerned it works pretty well and is a HUGE improvement over the current sparse which
* doesn't tell you what line the error really is in, it only warns about the last line of the function
* isn't able to check different contexts despite documenting it (see above)

You should able to do the same thing in the linearized back byte code. You just linearized the context expression using pseudo. Then on the checker side you can use the byte code to evaluate the expression is same or not, by comparing expression instructions.
You can even get around the p=&a problem I mention above because in the linearized byte code level, you can do some real data flow analyze.

I think it is unnecessary to change the front end code to track expression. In the back end you can do that much better. That is the main reason I object to this patch.

Quoted 10 lines

Quoted 2 lines
I am not saying that annotation is not useful. I agree source code annotation helps on the source code reading. But it
Actually, I kinda disagree. Annotating *each and every function* with the locks it requires is _very_ useful, not just for sparse but also for human readers of the code. Hence, I don't just want sparse to check across functions, I want to be able to tell people what to do for calling a given function as well. The fact that sparse can check my annotations is great, but having them would be useful without that as well.

I don't think we have disagreement here. I do agree having source code annotation is good for human reading. Please read my email. But that shouldn't stop you having the checker to understand your code.

Even better, how do you know your annotation is in sync with your code? You can have the checker to warn you that your annotation is not in sync with code.

Quoted 6 lines

It used to be like that. But I'm arguing (and others backed me up on this) that inlines are really just functions and as such should be annotated, not magically inlined into the code and then checked as sparse behaves right now.

First of all, I am just give it as example of idea how this problem can be solved.

About annotate inline function or not, I don't have strong preference against it. But I can see it is imposing a burden to maintain the additional annotation. Now you update the code and you have to update the annotation as well. You require developers who write new function to understand the spase context checking and maintain the annotation as well. You are creating addition work for kernel developers.

Quoted 3 lines

Please don't focus on cross-function checking so much. Having different contexts is way more desirable, and cross-function checking probably is _not_ desirable in that you _want_ the annotations.

That is not what I said, you can keep your precious annotations for human reading. But that does not mean sparse checker should limited itself to only using annotations if it can be smarter about it.

Having cross-function checking is not exclusive to the annotations. But having cross-function checking can enable some very useful feature which we can't do right now.

Chris

Johannes Berg

author

2008-05-29 08:59 UTC #11 lore raw

PATCH 7/9 test conditional result locking

In reply to Johannes Berg

To test a function that can return a locked struct or NULL, a macro has to be invented. Add a test case for that.

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

---
 validation/context-vars.c |   29 +++++++++++++++++++++++++----
 1 file changed, 25 insertions(+), 4 deletions(-)

validation/context-vars.c +25 -4

@@ -1,3 +1,5 @@
+#include <stddef.h>
+
 static void a(void *p) __attribute__((context(p,0,1)))
 {
     __context__(p,1);

@@ -159,13 +161,32 @@ static void good_locked_val(void)
     ;
 }
 
+
+extern struct test *_search(int key);
+
+#define search(res, key) do {	\
+  (res) = _search((key));	\
+  if (res)			\
+      __context__(&(res)->lock,1);\
+  } while (0)
+
+static void test(void)
+{
+    struct test **x;
+
+    search(*x, 32);
+    if (*x)
+      unlock(*x);
+}
+
+
 /*
  * check-name: Check -Wcontext with lock variables
  *
  * check-error-start
-context-vars.c:53:7: warning: context imbalance in 'warn_lock1': wrong count at exit
-context-vars.c:53:7:    context '**v+4': wanted 0, got 1
-context-vars.c:137:11: warning: context problem in 'warn_unlock': 'unlock' expected different context
-context-vars.c:137:11:    context '*t+0': wanted >= 1, got 0
+context-vars.c:55:7: warning: context imbalance in 'warn_lock1': wrong count at exit
+context-vars.c:55:7:    context '**v+4': wanted 0, got 1
+context-vars.c:139:11: warning: context problem in 'warn_unlock': 'unlock' expected different context
+context-vars.c:139:11:    context '*t+0': wanted >= 1, got 0
  * check-error-end
  */

Johannes Berg

author

2008-05-29 08:57 UTC #12 lore raw

PATCH 8/9 show required context in instruction output

In reply to Johannes Berg

Just eases debugging sparse/the context tracking itself.

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

---
 expression.c |    2 ++
 linearize.c  |    2 +-
 2 files changed, 3 insertions(+), 1 deletion(-)

expression.c +2 -0

@@ -648,6 +648,8 @@ static struct token *postfix_expression(
 					copy->in = c->in;
 					copy->out = c->out;
 					copy->exact = c->exact;
+					copy->token = c->token;
+					copy->in_fn = c->context;
 					add_ptr_list(&call->contexts, copy);
 
 					if (!c->token)

linearize.c +1 -1

@@ -443,7 +443,7 @@ const char *show_instruction(struct inst
 			expression_str(insn->context_expr, ctxbuf, sizeof(ctxbuf));
 			buf += sprintf(buf, "%s, ", ctxbuf);
 		}
-		buf += sprintf(buf, "%d", insn->increment);
+		buf += sprintf(buf, "%d %d", insn->increment, insn->required);
 		break;
 	}
 	case OP_RANGE:

Johannes Berg

author

2008-05-29 09:00 UTC #13 lore raw

PATCH 9/9 check inlines explicitly

In reply to Johannes Berg

An earlier patch disabled checking through inline functions because inlining them clashes with the context tracking code, so this now makes sparse check the inline functions as though they were really functions.

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

---
 sparse.c |   15 ++++++++++++++-
 1 file changed, 14 insertions(+), 1 deletion(-)

sparse.c +14 -1

@@ -29,11 +29,12 @@ struct context_check {
 	const struct expression *expr;
 };
 
-DECLARE_ALLOCATOR(context_check);
 DECLARE_PTR_LIST(context_check_list, struct context_check);
 DECLARE_PTR_LIST(context_list_list, struct context_check_list);
 ALLOCATOR(context_check, "context check list");
 
+static struct symbol_list *inline_list = NULL;
+
 
 static void context_add(struct context_check_list **ccl,
 			const struct expression *expr,

@@ -277,6 +278,15 @@ static int check_bb_context(struct entry
 	 */
 	FOR_EACH_PTR(bb->insns, insn) {
 		switch (insn->opcode) {
+		case OP_INLINED_CALL: {
+			if (!insn->func->sym)
+				break;
+			if (insn->func->sym->visited)
+				break;
+			insn->func->sym->visited = 1;
+			add_ptr_list(&inline_list, insn->func->sym);
+			break;
+		}
 		case OP_CONTEXT:
 			if (handle_context(ep, bb, insn, &combined))
 				goto out;

@@ -545,6 +555,9 @@ int main(int argc, char **argv)
 	check_symbols(sparse_initialize(argc, argv, &filelist));
 	FOR_EACH_PTR_NOTAG(filelist, file) {
 		check_symbols(sparse(file));
+		evaluate_symbol_list(inline_list);
+		check_symbols(inline_list);
+		free_ptr_list(&inline_list);
 	} END_FOR_EACH_PTR_NOTAG(file);
 	return 0;
 }

Johannes Berg

author

2008-05-29 23:15 UTC #14 lore raw

PATCH v2 9/9 check inlines explicitly

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

---
Maybe linearize_symbol() should do the check and return sym->ep if not NULL?

 sparse.c |   24 ++++++++++++++++++++++--
 1 file changed, 22 insertions(+), 2 deletions(-)

sparse.c +22 -2

@@ -29,11 +29,12 @@ struct context_check {
 	const struct expression *expr;
 };
 
-DECLARE_ALLOCATOR(context_check);
 DECLARE_PTR_LIST(context_check_list, struct context_check);
 DECLARE_PTR_LIST(context_list_list, struct context_check_list);
 ALLOCATOR(context_check, "context check list");
 
+static struct symbol_list *inline_list = NULL;
+
 
 static void context_add(struct context_check_list **ccl,
 			const struct expression *expr,

@@ -277,6 +278,15 @@ static int check_bb_context(struct entry
 	 */
 	FOR_EACH_PTR(bb->insns, insn) {
 		switch (insn->opcode) {
+		case OP_INLINED_CALL: {
+			if (!insn->func->sym)
+				break;
+			if (insn->func->sym->visited)
+				break;
+			insn->func->sym->visited = 1;
+			add_ptr_list(&inline_list, insn->func->sym);
+			break;
+		}
 		case OP_CONTEXT:
 			if (handle_context(ep, bb, insn, &combined))
 				goto out;

@@ -526,7 +536,14 @@ static void check_symbols(struct symbol_
 		struct entrypoint *ep;
 
 		expand_symbol(sym);
-		ep = linearize_symbol(sym);
+		/*
+		 * If we're passing back an inline via the special code
+		 * that tests those, it might already be linearized, if
+		 * so just check it and don't linearize again.
+		 */
+		ep = sym->ep;
+		if (!ep)
+			ep = linearize_symbol(sym);
 		if (ep) {
 			if (dbg_entry)
 				show_entry(ep);

@@ -545,6 +562,9 @@ int main(int argc, char **argv)
 	check_symbols(sparse_initialize(argc, argv, &filelist));
 	FOR_EACH_PTR_NOTAG(filelist, file) {
 		check_symbols(sparse(file));
+		evaluate_symbol_list(inline_list);
+		check_symbols(inline_list);
+		free_ptr_list(&inline_list);
 	} END_FOR_EACH_PTR_NOTAG(file);
 	return 0;
 }

Harvey Harrison

2008-05-29 23:20 UTC #15 lore raw

Re: [PATCH 9/9 v2] check inlines explicitly

Quoted 6 lines · Johannes Berg

An earlier patch disabled checking through inline functions because inlining them clashes with the context tracking code, so this now makes sparse check the inline functions as though they were really functions.
Signed-off-by Johannes Berg <[email protected]>

Works for me.

Harvey

Harvey Harrison

2008-05-29 22:12 UTC #16 lore raw

In reply to Johannes Berg

Quoted 5 lines · Johannes Berg

This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)
johannes

From initial impressions, this works pretty well, at least in the kernel.

Looking a little deeper at the results now, but seems like a nice improvement.

Harvey

Harvey Harrison

2008-05-29 22:35 UTC #17 lore raw

In reply to Johannes Berg

Quoted 4 lines · Johannes Berg

This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)

With these applied I get a new error when checking fs/minix/itree_common.c

I'll try and track it down.

Harvey

Johannes Berg

author

2008-05-29 22:46 UTC #18 lore raw

Quoted 8 lines · Harvey Harrison

Quoted 4 lines · Johannes Berg
This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)
With these applied I get a new error when checking fs/minix/itree_common.c

What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!

johannes

Harvey Harrison

2008-05-29 22:47 UTC #19 lore raw

Quoted 7 lines · Johannes Berg

Quoted 6 lines · Harvey Harrison
Quoted 4 lines · Johannes Berg
This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)

Quoted 6 lines

Quoted 2 lines
With these applied I get a new error when checking fs/minix/itree_common.c
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!

That would be the one....after a long spew ending in:

fs/minix/itree_common.c:44:2: warning: label 'continue' already bound fs/minix/itree_common.c:44:2: warning: label 'break' already bound fs/minix/itree_common.c:19:2: warning: label 'continue' already bound fs/minix/itree_common.c:19:2: warning: label 'break' already bound

Something has gotten a bit confused somewhere.

Harvey

Harvey Harrison

2008-05-29 22:51 UTC #20 lore raw

In reply to Johannes Berg

Quoted 7 lines · Johannes Berg

Quoted 6 lines · Harvey Harrison
Quoted 4 lines · Johannes Berg
This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)

Quoted 6 lines

Quoted 2 lines
With these applied I get a new error when checking fs/minix/itree_common.c
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!

It's a problem introduced with 9/9 explicitly checking inlines.

Harvey

Johannes Berg

author

2008-05-29 22:55 UTC #21 lore raw

Quoted 5 lines

Quoted 3 lines
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!
It's a problem introduced with 9/9 explicitly checking inlines.

Cool, thanks, I'm just looking at it.

johannes

Pavel Roskin

2008-05-29 23:03 UTC #22 lore raw

Quoted 7 lines · Johannes Berg

Quoted 5 lines
Quoted 3 lines
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!
It's a problem introduced with 9/9 explicitly checking inlines.
Cool, thanks, I'm just looking at it.

You may want to look at this:
http://marc.info/?t=120287346100007&r=1&w=2
http://marc.info/?l=linux-sparse&m=120370800715845&w=2

It was happening in ndiswrapper because a typedef was forcing an inline function to be linearized twice.

Signature · 2 lines

Regards,
Pavel Roskin

Johannes Berg

author

2008-05-29 23:08 UTC #23 lore raw

Quoted 7 lines · Pavel Roskin

Quoted 6 lines · Johannes Berg
Quoted 5 lines
Quoted 3 lines
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!
It's a problem introduced with 9/9 explicitly checking inlines.

Quoted 8 lines

Quoted 1 line
Cool, thanks, I'm just looking at it.
You may want to look at this:
http://marc.info/?t=120287346100007&r=1&w=2
http://marc.info/?l=linux-sparse&m=120370800715845&w=2
It was happening in ndiswrapper because a typedef was forcing an inline function to be linearized twice.

Ah, thanks for the pointers, that might be the case. Wonder why it's being linearized twice, and I see it even without the linearization I force...? will take a look tomorrow.

johannes

Johannes Berg

author

2008-05-29 23:16 UTC #24 lore raw

Quoted 14 lines · Johannes Berg

Quoted 13 lines · Pavel Roskin
Quoted 7 lines · Johannes Berg
Quoted 5 lines
Quoted 3 lines
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!
It's a problem introduced with 9/9 explicitly checking inlines.
Cool, thanks, I'm just looking at it.
You may want to look at this:
http://marc.info/?t=120287346100007&r=1&w=2
http://marc.info/?l=linux-sparse&m=120370800715845&w=2

Quoted 6 lines

Quoted 2 lines
It was happening in ndiswrapper because a typedef was forcing an inline function to be linearized twice.
Ah, thanks for the pointers, that might be the case. Wonder why it's being linearized twice, and I see it even without the linearization I force...? will take a look tomorrow.

No, I'm just confused. That updated patch fixes it for me.

johannes

Johannes Berg

author

2008-05-29 23:05 UTC #25 lore raw

In reply to Harvey Harrison

Quoted 6 lines

Quoted 4 lines
What sort? Right now, it seems to go into a dead loop on fs/minix/itree_v1.c for me?!
It's a problem introduced with 9/9 explicitly checking inlines.

It is, indeed, very odd. I don't see it right now though.

johannes

Johannes Berg

author

2008-07-20 12:30 UTC #26 lore raw

In reply to Johannes Berg

Quoted 3 lines · Johannes Berg

This updates the context tracking, I just explained most of it in the mail "Re: sparse context warning problem ..."
(message ID <[email protected]>)

Ping? Josh, do you intend to merge this? I keep getting asked about the corresponding kernel patches. If you don't want it, please revert my previous patches and I'll stop bothering you either way.

johannes