Data race analysis (race).
Data race analysis with tries for offsets and type-based memory locations for open code.
Accesses are to memory locations (memos) which consist of a root and offset. Root can be:
- variable, if access is to known global variable or alloc-variable;
- type, if access is to unknown pointer.
Accesses are (now) collected to sets for each corresponding memo, after points-to sets are resolved, during postsolving.
Race checking is performed per-memo, except must additionally account for accesses to other memos (see diagram below):
- access to
s.f can race with access to a prefix like s, which writes an entire struct at once; - access to
s.f can race with type-based access like (struct S).f; - access to
(struct S).f can race with type-based access to a suffix like (int). - access to
(struct T).s.f can race with type-based access like (struct S), which is a combination of the above.
These are accounted for lazily (unlike in the past).
Prefixes (a.k.a. inner distribution) are handled using a trie data structure enriched with lattice properties. Race checking starts at the root and passes accesses to ancestor nodes down to children.
Type suffixes (a.k.a. outer distribution) are handled by computing successive immediate type suffixes transitively and accessing corresponding offsets from corresponding root tries in the global invariant.
Type suffix prefixes (for the combination of the two) are handled by passing type suffix accesses down when traversing the prefix trie.
Race checking happens at each trie node with the above three access sets at hand using Access.group_may_race. All necessary combinations between the four classes are handled, but unnecessary repeated work is carefully avoided. E.g. accesses which are pairwise checked at some prefix are not re-checked pairwise at a node. Thus, races (with prefixes or type suffixes) are reported for most precise memos with actual accesses: at the longest prefix and longest type suffix.
Additionally, accesses between prefix and type suffix intersecting at a node are checked. These races are reported at the unique memo at the intersection of the prefix and the type suffix. This requires an implementation hack to still eagerly do outer distribution, but only of empty access sets. It ensures that corresponding trie nodes exist for traversal later.
Given C declarations:
struct S {
int f;
};
struct T {
struct S s;
};
struct T t;
Example structure of related memos for race checking:
(int) (S) (T)
\ / \ / \
f s t
\ / \ /
f s
\ /
fwhere:
(int) is a type-based memo root for the primitive int type;(S) and (T) are short for (struct S) and (struct T), which are type-based memo roots;- prefix relations are indicated by
/, so access paths run diagonally from top-right to bottom-left; - type suffix relations are indicated by
\ .
All same-node races:
- Race between
t.s.f and t.s.f is checked/reported at t.s.f. - Race between
t.s and t.s is checked/reported at t.s. - Race between
t and t is checked/reported at t. - Race between
(T).s.f and (T).s.f is checked/reported at (T).s.f. - Race between
(T).s and (T).s is checked/reported at (T).s. - Race between
(T) and (T) is checked/reported at (T). - Race between
(S).f and (S).f is checked/reported at (S).f. - Race between
(S) and (S) is checked/reported at (S). - Race between
(int) and (int) is checked/reported at (int).
All prefix races:
- Race between
t.s.f and t.s is checked/reported at t.s.f. - Race between
t.s.f and t is checked/reported at t.s.f. - Race between
t.s and t is checked/reported at t.s. - Race between
(T).s.f and (T).s is checked/reported at (T).s.f. - Race between
(T).s.f and (T) is checked/reported at (T).s.f. - Race between
(T).s and (T) is checked/reported at (T).s. - Race between
(S).f and (S) is checked/reported at (S).f.
All type suffix races:
- Race between
t.s.f and (T).s.f is checked/reported at t.s.f. - Race between
t.s.f and (S).f is checked/reported at t.s.f. - Race between
t.s.f and (int) is checked/reported at t.s.f. - Race between
(T).s.f and (S).f is checked/reported at (T).s.f. - Race between
(T).s.f and (int) is checked/reported at (T).s.f. - Race between
(S).f and (int) is checked/reported at (S).f. - Race between
t.s and (T).s is checked/reported at t.s. - Race between
t.s and (S) is checked/reported at t.s. - Race between
(T).s and (S) is checked/reported at (T).s. - Race between
t and (T) is checked/reported at t.
All type suffix prefix races:
- Race between
t.s.f and (T).s is checked/reported at t.s.f. - Race between
t.s.f and (T) is checked/reported at t.s.f. - Race between
t.s.f and (S) is checked/reported at t.s.f. - Race between
(T).s.f and (S) is checked/reported at (T).s.f. - Race between
t.s and (T) is checked/reported at t.s.
All prefix-type suffix races:
- Race between
t.s and (T).s.f is checked/reported at t.s.f. - Race between
t.s and (S).f is checked/reported at t.s.f. - Race between
t.s and (int) is checked/reported at t.s.f. - Race between
t and (T).s.f is checked/reported at t.s.f. - Race between
t and (S).f is checked/reported at t.s.f. - Race between
t and (int) is checked/reported at t.s.f. - Race between
t and (T).s is checked/reported at t.s. - Race between
t and (S) is checked/reported at t.s. - Race between
(T).s and (S).f is checked/reported at (T).s.f. - Race between
(T).s and (int) is checked/reported at (T).s.f. - Race between
(T) and (S).f is checked/reported at (T).s.f. - Race between
(T) and (int) is checked/reported at (T).s.f. - Race between
(T) and (S) is checked/reported at (T).s. - Race between
(S) and (int) is checked/reported at (S).f.
module Spec : sig ... endData race analyzer without base --- this is the new standard