Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Analysis of pthread_barriers #1652

Draft
wants to merge 17 commits into
base: master
Choose a base branch
from
Draft

Analysis of pthread_barriers #1652

wants to merge 17 commits into from

Conversation

michael-schwarz
Copy link
Member

@michael-schwarz michael-schwarz commented Dec 24, 2024

Makes use of the $$||_{\mathcal{A}}: \mathcal{A} \to \mathcal{A} \to \{ \textsf{false},\top \}$$ predicate we want to define for (abstract) digests to provide a sound basis for all of our MHP stuff for races and give a principled account of what I added in #518 .

Interestingly, it even does so outside of the context of data races --- which may be a cute insight on top of putting the race analysis on solid foundations with this predicate (and hopefully finding a way to get pthread_once to also fit (potentially in a reduced fashion)).

Technically, it accumulates the capacity and MHP information for all calls to wait for each barrier at a global unknown, and checks upon a call to wait that there are at least min(capacity)-1 other accesses where $$||_{\mathcal{A}}$$ is true pairwise among these, as well as with the caller to wait.

TODO:

  • Use TIDs and Joins
  • Use further abstract digests (such as must-lockset digest)
  • Use information also for excluding races (beyond unreachability)
  • Come up with a less expensive algorithm for checking there are min(capacity)-1 elements where $$||_{\mathcal{A}}$$ holds pairwise
  • Handle barriers configured for inter-process communication soundly by not doing anything for them

Closes #1651.

@michael-schwarz
Copy link
Member Author

michael-schwarz commented Dec 24, 2024

OS X CI does OS X things, I'll just ignore that for now.

Turns out OS X does not support barriers.

in
if not can_proceed then raise Analyses.Deadcode;
(* limit to this case to avoid having to construct all permutations above *)
if List.length waiters = min_cap - 1 then

Check warning

Code scanning / Semgrep OSS

computing list length is inefficient for length comparison, use compare_length_with instead Warning

computing list length is inefficient for length comparison, use compare_length_with instead
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

Analysis of pthread_barrier for race detection
1 participant