Fix context checking detection of a reversed lock-pair within a basic block

PATCH In review David Holmer 2 participants 2 messages Nov 17, 2015 – Jan 5, 2016 Sparse checker

Share & tools

David Holmer

author

2015-11-17 17:18 UTC #0 lore raw

PATCH 1/1 Fix context checking detection of a reversed lock-pair within a basic block

This commit adds a new validation test case with a simple lock context issue that was not previously caught by sparse. This test case is a simple "reversed" lock pair (unlock/lock instead of lock/unlock):
+static void warn_reverse(void)
+{
+ r();
+ a();
+}

Previously, sparse would not flag this context imbalance because it happens WITHIN a single basic block and imbalance checking was only done at the boundaries of basic blocks. In this case, the lock following the unlock results in a net context change of zero for this basic block, so checking only at the boundaries of basic blocks is insufficient.

Primarily, this commit moves the checking for "unexpected unlock" inside the context_increase function where it can correctly detect the new test case as well as all other existing test cases.

In order to accommodate the primary change, some additional ancillary changes are made:
* The entry point is added as an argument to context_increase() so that it can be passed to imbalance() if needed.
* The two arguments entry and exit are removed from imbalance() as they are currently unused in the function and it simplifies calling it in the new location (all call sites of imbalance() are changed).
* A prototype for imbalance() is added at top of the file as a call is now made before the function is defined.

Signed-off-by David Holmer <[email protected]>

---
 sparse.c             | 19 ++++++++++++-------
 validation/context.c |  8 ++++++++
 2 files changed, 20 insertions(+), 7 deletions(-)

sparse.c +12 -7

index 6b3324c..85b92e9 100644
@@ -40,7 +40,9 @@
 #include "expression.h"
 #include "linearize.h"
 
-static int context_increase(struct basic_block *bb, int entry)
+static int imbalance(struct entrypoint *ep, struct basic_block *bb, const char *why);
+
+static int context_increase(struct entrypoint *ep, struct basic_block *bb, int entry)
 {
 	int sum = 0;
 	struct instruction *insn;

@@ -61,11 +63,15 @@ static int context_increase(struct basic_block *bb, int entry)
 			continue;
 		}
 		sum += val;
+		if (entry + sum < 0) {
+			imbalance(ep, bb, "unexpected unlock");
+			return sum;
+		}
 	} END_FOR_EACH_PTR(insn);
 	return sum;
 }
 
-static int imbalance(struct entrypoint *ep, struct basic_block *bb, int entry, int exit, const char *why)
+static int imbalance(struct entrypoint *ep, struct basic_block *bb, const char *why)
 {
 	if (Wcontext) {
 		struct symbol *sym = ep->name;

@@ -85,7 +91,7 @@ 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(ep, bb, "wrong count at exit") : 0;
 
 	FOR_EACH_PTR(bb->children, child) {
 		if (check_bb_context(ep, child, entry, exit))

@@ -103,12 +109,11 @@ static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int e
 
 	/* Now that's not good.. */
 	if (bb->context >= 0)
-		return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
+		return imbalance(ep, bb, "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");
+	entry += context_increase(ep, bb, entry);
+	if (entry < 0) return -1;
 
 	return check_children(ep, bb, entry, exit);
 }

validation/context.c +8 -0

index 33b70b8..c0a5357 100644
@@ -314,6 +314,13 @@ static void warn_cond_lock1(void)
         condition2 = 1; /* do stuff */
     r();
 }
+
+static void warn_reverse(void)
+{
+    r();
+    a();
+}
+
 /*
  * check-name: Check -Wcontext
  *

@@ -332,5 +339,6 @@ context.c:274:13: warning: context imbalance in 'warn_goto1' - wrong count at ex
 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:318:13: warning: context imbalance in 'warn_reverse' - unexpected unlock
  * check-error-end
  */

Signature · 1 line

1.9.1

Luc Van Oostenryck

2016-01-05 13:23 UTC #1 lore raw

Quoted 9 lines · David Holmer

This commit adds a new validation test case with a simple lock context issue that was not previously caught by sparse. This test case is a simple "reversed" lock pair (unlock/lock instead of lock/unlock):
validation/context.c +5 -0
+static void warn_reverse(void)
+{
+    r();
+    a();
+}

Quoted 5 lines

Previously, sparse would not flag this context imbalance because it happens WITHIN a single basic block and imbalance checking was only done at the boundaries of basic blocks. In this case, the lock following the unlock results in a net context change of zero for this basic block, so checking only at the boundaries of basic blocks is insufficient.

Indeed, nice catch.

I have a few remarks and suggestions here under.

Quoted 8 lines

Primarily, this commit moves the checking for "unexpected unlock" inside the context_increase function where it can correctly detect the new test case as well as all other existing test cases.
In order to accommodate the primary change, some additional ancillary changes are made:
* The entry point is added as an argument to context_increase() so that it can be passed to imbalance() if needed.

This is not needed because a basic block's entry point is available as bb->ep.

Quoted 3 lines

* The two arguments entry and exit are removed from imbalance() as they are currently unused in the function and it simplifies calling it in the new location (all call sites of imbalance() are changed).

Better put this is a separate patch.

Quoted 25 lines

* A prototype for imbalance() is added at top of the file as a call is now made before the function is defined.

Signed-off-by David Holmer <[email protected]>

---
 sparse.c             | 19 ++++++++++++-------
 validation/context.c |  8 ++++++++
 2 files changed, 20 insertions(+), 7 deletions(-)

sparse.c +3 -1

index 6b3324c..85b92e9 100644
@@ -40,7 +40,9 @@
 #include "expression.h"
 #include "linearize.h"
 
-static int context_increase(struct basic_block *bb, int entry)
+static int imbalance(struct entrypoint *ep, struct basic_block *bb, const char *why);
+
+static int context_increase(struct entrypoint *ep, struct basic_block *bb, int entry)
 {
 	int sum = 0;
 	struct instruction *insn;

sparse.c static int context_increase(struct basic_block *bb, int entry) · line 68

Quoted 6 lines

sparse.c +3 -0

@@ -61,11 +63,15 @@ static int context_increase(struct basic_block *bb, int entry)
 			continue;
 		}
 		sum += val;
+		if (entry + sum < 0) {
+			imbalance(ep, bb, "unexpected unlock");
+			return sum;

This early return is wrong to me.
We want to check the other instructions too and have the correct value for the basic block's net context change.

sparse.c static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int e · line 116

Quoted 13 lines

sparse.c +3 -4

@@ -103,12 +109,11 @@ static int check_bb_context(struct entrypoint *ep, struct basic_block *bb, int e
 
 	/* Now that's not good.. */
 	if (bb->context >= 0)
-		return imbalance(ep, bb, entry, bb->context, "different lock contexts for basic block");
+		return imbalance(ep, bb, "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");
+	entry += context_increase(ep, bb, entry);
+	if (entry < 0) return -1;

1) Better leave the 'if' and the 'return' on separate lines, like they were.
2) Without the early return here above, the return -1 is nor needed, nor desirable. What I would suggest is:
- to leave the call to imbalance() here; it give a warning message about a *basic block* imbalance (non-zero net context change).
- add another small helper to give a warning message about other kind of context errors, using the position on the offending *instruction*, Use this one in your new check in context_increase(), maybe using a message stating more explicitly that we're trying to unlock a lock that is not held.

Quoted 5 lines

validation/context.c +0 -0
index 33b70b8..c0a5357 100644

validation/context.c static void warn_cond_lock1(void) · line 323

Quoted 10 lines

validation/context.c +7 -0

@@ -314,6 +314,13 @@ static void warn_cond_lock1(void)
         condition2 = 1; /* do stuff */
     r();
 }
+
+static void warn_reverse(void)
+{
+    r();
+    a();
+}
+

It would be nice to also add a case for when the function is annotated with context entry and exit values; something like

	+static void warn_reverse2(void)__attribute__((context(0,0)))
	+{
	+    r();
	+    a();
	+}
	+
	+static void good_reverse2(void)__attribute__((context(1,1)))
	+{
	+    r();
	+    a();
	+}
	+

Yours,
Luc