Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit fef0679

Browse filesBrowse files
author
Nikita Kraiouchkine
authored
Merge pull request #15 from jsinglet/jsinglet/concurrency-2-fork
Concurrency 2
2 parents e444f7c + f2765f3 commit fef0679
Copy full SHA for fef0679

File tree

33 files changed

+701
-85
lines changed
Filter options

33 files changed

+701
-85
lines changed

‎c/cert/src/rules/CON35-C/DeadlockByLockingInPredefinedOrder.ql

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/**
2+
* @id c/cert/deadlock-by-locking-in-predefined-order
3+
* @name CON35-C: Avoid deadlock by locking in a predefined order
4+
* @description Circular waits leading to thread deadlocks may be avoided by locking in a predefined
5+
* order.
6+
* @kind problem
7+
* @precision very-high
8+
* @problem.severity error
9+
* @tags external/cert/id/con35-c
10+
* correctness
11+
* concurrency
12+
* external/cert/obligation/rule
13+
*/
14+
15+
import cpp
16+
import codingstandards.c.cert
17+
import codingstandards.cpp.rules.preventdeadlockbylockinginpredefinedorder.PreventDeadlockByLockingInPredefinedOrder
18+
19+
class DeadlockByLockingInPredefinedOrderQuery extends PreventDeadlockByLockingInPredefinedOrderSharedQuery {
20+
DeadlockByLockingInPredefinedOrderQuery() {
21+
this = Concurrency2Package::deadlockByLockingInPredefinedOrderQuery()
22+
}
23+
}

‎c/cert/src/rules/CON36-C/WrapFunctionsThatCanSpuriouslyWakeUpInLoop.ql

Copy file name to clipboard
+23Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
/**
2+
* @id c/cert/wrap-functions-that-can-spuriously-wake-up-in-loop
3+
* @name CON36-C: Wrap functions that can spuriously wake up in a loop
4+
* @description Not wrapping functions that can wake up spuriously in a conditioned loop can result
5+
* race conditions.
6+
* @kind problem
7+
* @precision very-high
8+
* @problem.severity error
9+
* @tags external/cert/id/con36-c
10+
* correctness
11+
* concurrency
12+
* external/cert/obligation/rule
13+
*/
14+
15+
import cpp
16+
import codingstandards.c.cert
17+
import codingstandards.cpp.rules.wrapspuriousfunctioninloop.WrapSpuriousFunctionInLoop
18+
19+
class WrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery extends WrapSpuriousFunctionInLoopSharedQuery {
20+
WrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery() {
21+
this = Concurrency2Package::wrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery()
22+
}
23+
}

‎c/cert/test/rules/CON35-C/DeadlockByLockingInPredefinedOrder.testref

Copy file name to clipboard
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
c/common/test/rules/preventdeadlockbylockinginpredefinedorder/PreventDeadlockByLockingInPredefinedOrder.ql

‎c/cert/test/rules/CON36-C/WrapFunctionsThatCanSpuriouslyWakeUpInLoop.testref

Copy file name to clipboard
+1Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1 @@
1+
c/common/test/rules/wrapspuriousfunctioninloop/WrapSpuriousFunctionInLoop.ql

‎c/common/test/rules/preventdeadlockbylockinginpredefinedorder/PreventDeadlockByLockingInPredefinedOrder.expected

Copy file name to clipboard
+3Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
| test.c:15:5:15:6 | d1 | Threaded function may be called from a context that uses $@ and $@ which may lead to deadlocks. | test.c:22:3:22:10 | call to mtx_lock | lock 1 | test.c:23:3:23:10 | call to mtx_lock | lock 2 |
2+
| test.c:33:5:33:6 | d2 | Threaded function may be called from a context that uses $@ and $@ which may lead to deadlocks. | test.c:41:3:41:10 | call to mtx_lock | lock 1 | test.c:45:3:45:10 | call to mtx_lock | lock 2 |
3+
| test.c:88:5:88:6 | d4 | Threaded function may be called from a context that uses $@ and $@ which may lead to deadlocks. | test.c:111:3:111:10 | call to mtx_lock | lock 1 | test.c:112:3:112:10 | call to mtx_lock | lock 2 |

‎c/common/test/rules/preventdeadlockbylockinginpredefinedorder/PreventDeadlockByLockingInPredefinedOrder.ql

Copy file name to clipboard
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
// GENERATED FILE - DO NOT MODIFY
2+
import codingstandards.cpp.rules.preventdeadlockbylockinginpredefinedorder.PreventDeadlockByLockingInPredefinedOrder

‎c/common/test/rules/preventdeadlockbylockinginpredefinedorder/test.c

Copy file name to clipboard
+166Lines changed: 166 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,166 @@
1+
#include <stdlib.h>
2+
#include <threads.h>
3+
4+
typedef struct {
5+
int sum;
6+
mtx_t mu;
7+
} B;
8+
9+
typedef struct {
10+
B *from;
11+
B *to;
12+
int amount;
13+
} thread_arg;
14+
15+
int d1(void *arg) { // NON_COMPLIANT
16+
thread_arg *targ = (thread_arg *)arg;
17+
18+
B *from = targ->from;
19+
B *to = targ->to;
20+
int amount = targ->amount;
21+
22+
mtx_lock(&from->mu);
23+
mtx_lock(&to->mu);
24+
25+
if (from->sum >= amount) {
26+
from->sum = from->sum - amount;
27+
to->sum = to->sum + amount;
28+
return 0;
29+
}
30+
return -1;
31+
}
32+
33+
int d2(void *arg) { // NON_COMPLIANT
34+
35+
thread_arg *targ = (thread_arg *)arg;
36+
37+
B *from = targ->from;
38+
B *to = targ->to;
39+
int amount = targ->amount;
40+
41+
mtx_lock(&from->mu);
42+
if (from->sum < amount) {
43+
return -1;
44+
}
45+
mtx_lock(&to->mu);
46+
from->sum = (from->sum - amount);
47+
to->sum = (to->sum + amount);
48+
49+
return 0;
50+
}
51+
52+
int getA() { return 0; }
53+
int getARand() { return rand(); }
54+
55+
int d3(void *arg) { // COMPLIANT
56+
57+
thread_arg *targ = (thread_arg *)arg;
58+
59+
B *from = targ->from;
60+
B *to = targ->to;
61+
int amount = targ->amount;
62+
63+
mtx_t *one;
64+
mtx_t *two;
65+
66+
int a = getARand();
67+
68+
// here a may take on multiple different
69+
// values and thus different values may flow
70+
// into the locks
71+
if (a == 9) {
72+
one = &from->mu;
73+
two = &to->mu;
74+
} else {
75+
one = &to->mu;
76+
two = &from->mu;
77+
}
78+
79+
mtx_lock(one);
80+
mtx_lock(two);
81+
82+
from->sum = (from->sum - amount);
83+
to->sum = (to->sum + amount);
84+
85+
return 0;
86+
}
87+
88+
int d4(void *arg) { // NON_COMPLIANT
89+
90+
thread_arg *targ = (thread_arg *)arg;
91+
92+
B *from = targ->from;
93+
B *to = targ->to;
94+
int amount = targ->amount;
95+
96+
mtx_t *one;
97+
mtx_t *two;
98+
int a = getARand();
99+
100+
// here a may take on multiple different
101+
// values and thus different values may flow
102+
// into the locks
103+
if (a == 9) {
104+
one = &from->mu;
105+
two = &to->mu;
106+
} else {
107+
one = &to->mu;
108+
two = &from->mu;
109+
}
110+
111+
mtx_lock(&from->mu);
112+
mtx_lock(&to->mu);
113+
114+
from->sum = (from->sum - amount);
115+
to->sum = (to->sum + amount);
116+
117+
return 0;
118+
}
119+
120+
void f(B *ba1, B *ba2) {
121+
thrd_t t1, t2;
122+
123+
// unsafe - but used for testing
124+
thread_arg a1 = {.from = ba1, .to = ba2, .amount = 100};
125+
126+
thread_arg a2 = {.from = ba2, .to = ba1, .amount = 100};
127+
128+
thrd_create(&t1, d1, &a1);
129+
thrd_create(&t2, d1, &a2);
130+
}
131+
132+
void f2(B *ba1, B *ba2) {
133+
thrd_t t1, t2;
134+
135+
// unsafe - but used for testing
136+
thread_arg a1 = {.from = ba1, .to = ba2, .amount = 100};
137+
138+
thread_arg a2 = {.from = ba2, .to = ba1, .amount = 100};
139+
140+
thrd_create(&t1, d2, &a1);
141+
thrd_create(&t2, d2, &a2);
142+
}
143+
144+
void f3(B *ba1, B *ba2) {
145+
thrd_t t1, t2;
146+
147+
// unsafe - but used for testing
148+
thread_arg a1 = {.from = ba1, .to = ba2, .amount = 100};
149+
150+
thread_arg a2 = {.from = ba2, .to = ba1, .amount = 100};
151+
152+
thrd_create(&t1, d3, &a1);
153+
thrd_create(&t2, d3, &a2);
154+
}
155+
156+
void f4(B *ba1, B *ba2) {
157+
thrd_t t1, t2;
158+
159+
// unsafe - but used for testing
160+
thread_arg a1 = {.from = ba1, .to = ba2, .amount = 100};
161+
162+
thread_arg a2 = {.from = ba2, .to = ba1, .amount = 100};
163+
164+
thrd_create(&t1, d4, &a1);
165+
thrd_create(&t2, d4, &a2);
166+
}

‎c/common/test/rules/wrapspuriousfunctioninloop/WrapSpuriousFunctionInLoop.expected

Copy file name to clipboard
+3Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,3 @@
1+
| test.c:11:5:11:12 | call to cnd_wait | Use of a function that may wake up spuriously without a controlling loop. |
2+
| test.c:49:3:49:10 | call to cnd_wait | Use of a function that may wake up spuriously without a controlling loop. |
3+
| test.c:59:5:59:12 | call to cnd_wait | Use of a function that may wake up spuriously without a controlling loop. |

‎c/common/test/rules/wrapspuriousfunctioninloop/WrapSpuriousFunctionInLoop.ql

Copy file name to clipboard
+2Lines changed: 2 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,2 @@
1+
// GENERATED FILE - DO NOT MODIFY
2+
import codingstandards.cpp.rules.wrapspuriousfunctioninloop.WrapSpuriousFunctionInLoop

‎c/common/test/rules/wrapspuriousfunctioninloop/test.c

Copy file name to clipboard
+62Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,62 @@
1+
#include <stddef.h>
2+
#include <threads.h>
3+
4+
static mtx_t lk;
5+
static cnd_t cnd;
6+
7+
void f1() {
8+
mtx_lock(&lk);
9+
10+
if (1) {
11+
cnd_wait(&cnd, &lk); // NON_COMPLIANT
12+
}
13+
}
14+
15+
void f2() {
16+
mtx_lock(&lk);
17+
int i = 2;
18+
while (i > 0) {
19+
cnd_wait(&cnd, &lk); // COMPLIANT
20+
i--;
21+
}
22+
}
23+
24+
void f3() {
25+
mtx_lock(&lk);
26+
int i = 2;
27+
do {
28+
cnd_wait(&cnd, &lk); // COMPLIANT
29+
i--;
30+
} while (i > 0);
31+
}
32+
33+
void f4() {
34+
mtx_lock(&lk);
35+
36+
for (;;) {
37+
cnd_wait(&cnd, &lk); // COMPLIANT
38+
}
39+
}
40+
41+
void f5() {
42+
mtx_lock(&lk);
43+
44+
int i = 2;
45+
while (i > 0) {
46+
i--;
47+
}
48+
49+
cnd_wait(&cnd, &lk); // NON_COMPLIANT
50+
}
51+
52+
void f6() {
53+
mtx_lock(&lk);
54+
55+
for (int i = 0; i < 10; i++) {
56+
}
57+
int i = 0;
58+
if (i > 0) {
59+
cnd_wait(&cnd, &lk); // NON_COMPLIANT
60+
i--;
61+
}
62+
}

‎change_notes/2022-07-13-improvements-to-lock-detection.md

Copy file name to clipboard
+6Lines changed: 6 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,6 @@
1+
- `CON53-CPP` - `DeadlockByLockingInPredefinedOrder.ql`
2+
- Optimized performance and expanded coverage to include cases where locking
3+
order is not serialized
4+
- `CON52-CPP` - `PreventBitFieldAccessFromMultipleThreads.ql`
5+
- Fixed an issue with RAII-style locks and scope causing locks to not be
6+
correctly identified.

‎cpp/cert/src/rules/CON53-CPP/DeadlockByLockingInPredefinedOrder.ql

Copy file name to clipboardExpand all lines: cpp/cert/src/rules/CON53-CPP/DeadlockByLockingInPredefinedOrder.ql
+5-62Lines changed: 5 additions & 62 deletions
Original file line numberDiff line numberDiff line change
@@ -14,67 +14,10 @@
1414

1515
import cpp
1616
import codingstandards.cpp.cert
17-
import codingstandards.cpp.Concurrency
17+
import codingstandards.cpp.rules.preventdeadlockbylockinginpredefinedorder.PreventDeadlockByLockingInPredefinedOrder
1818

19-
/**
20-
* Gets a pair of locks guarding a `LockProtectedControlFlowNode` in an order
21-
* specified by the locking function's call site.
22-
*/
23-
pragma[inline]
24-
predicate getAnOrderedLockPair(
25-
FunctionCall lock1, FunctionCall lock2, LockProtectedControlFlowNode node
26-
) {
27-
lock1 = node.coveredByLock() and
28-
lock2 = node.coveredByLock() and
29-
not lock1 = lock2 and
30-
lock1.getFile() = lock2.getFile() and
31-
exists(Location l1Loc, Location l2Loc |
32-
l1Loc = lock1.getLocation() and
33-
l2Loc = lock2.getLocation()
34-
|
35-
l1Loc.getEndLine() < l2Loc.getStartLine()
36-
or
37-
l1Loc.getStartLine() = l2Loc.getEndLine() and
38-
l1Loc.getEndColumn() < l2Loc.getStartColumn()
39-
)
19+
class DeadlockByLockingInPredefinedOrderQuery extends PreventDeadlockByLockingInPredefinedOrderSharedQuery {
20+
DeadlockByLockingInPredefinedOrderQuery() {
21+
this = ConcurrencyPackage::deadlockByLockingInPredefinedOrderQuery()
22+
}
4023
}
41-
42-
/*
43-
* There are two ways to safely avoid deadlock. One involves doing the locking
44-
* in a specific order that is guaranteed to be the same across all thread
45-
* invocations. This is especially hard to check and thus we adopt an
46-
* alternative viewpoint wherein we view a "safe" usage of multiple locks to be
47-
* one that uses the built in `std::lock` functionality which avoids this
48-
* problem.
49-
*
50-
* To properly deadlock, a thread must have at least two different locks (i.e.,
51-
* mutual exclusion) which are used in an order that causes a problem. Thus we
52-
* look for functions with CFNs wherein there may be two locks active at the
53-
* same time that are invoked from a thread.
54-
*/
55-
56-
from LockProtectedControlFlowNode node, Function f, FunctionCall lock1, FunctionCall lock2
57-
where
58-
not isExcluded(node, ConcurrencyPackage::deadlockByLockingInPredefinedOrderQuery()) and
59-
// we can get into trouble when we get into a situation where there may be two
60-
// locks in the same threaded function active at the same time.
61-
// simple ordering
62-
// lock1 = node.coveredByLock() and
63-
// lock2 = node.coveredByLock() and
64-
getAnOrderedLockPair(lock1, lock2, node) and
65-
// To reduce the noise (and increase usefulness) we alert the user at the
66-
// level of the function, which is the unit the synchronization should be
67-
// performed.
68-
f = node.getEnclosingStmt().getEnclosingFunction() and
69-
// Because `std::lock` isn't included in our definition of a 'lock'
70-
// it is not necessary to check to see if it is in fact what is protecting
71-
// these CNFs.
72-
// However, to reduce noise, we shall require that the function we are
73-
// reporting makes some sort of locking call since this is likely where the
74-
// user intends to perform the locking operations. Our implementation will
75-
// currently look into all of these nodes which is less helpful for the user
76-
// but useful for our analysis.
77-
any(LockingOperation l).getEnclosingFunction() = f
78-
select f,
79-
"Threaded function may be called from a context that uses $@ and $@ which may lead to deadlocks.",
80-
lock1, "lock 1", lock2, "lock 2"

‎cpp/cert/src/rules/CON54-CPP/WrapFunctionsThatCanSpuriouslyWakeUpInLoop.ql

Copy file name to clipboardExpand all lines: cpp/cert/src/rules/CON54-CPP/WrapFunctionsThatCanSpuriouslyWakeUpInLoop.ql
+6-6Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -14,10 +14,10 @@
1414

1515
import cpp
1616
import codingstandards.cpp.cert
17-
import codingstandards.cpp.Concurrency
17+
import codingstandards.cpp.rules.wrapspuriousfunctioninloop.WrapSpuriousFunctionInLoop
1818

19-
from ConditionalWait cw
20-
where
21-
not isExcluded(cw, ConcurrencyPackage::wrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery()) and
22-
not cw.getEnclosingStmt().getParentStmt*() instanceof Loop
23-
select cw, "Use of a function that may wake up spuriously without a controlling loop."
19+
class WrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery extends WrapSpuriousFunctionInLoopSharedQuery {
20+
WrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery() {
21+
this = ConcurrencyPackage::wrapFunctionsThatCanSpuriouslyWakeUpInLoopQuery()
22+
}
23+
}

‎cpp/cert/test/rules/CON53-CPP/DeadlockByLockingInPredefinedOrder.expected

Copy file name to clipboardExpand all lines: cpp/cert/test/rules/CON53-CPP/DeadlockByLockingInPredefinedOrder.expected
-2Lines changed: 0 additions & 2 deletions
This file was deleted.

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.