Skip to content
New issue

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

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

Already on GitHub? # to your account

Refactor and fix different lockset analyses #659

Closed
sim642 opened this issue Mar 22, 2022 · 0 comments · Fixed by #662
Closed

Refactor and fix different lockset analyses #659

sim642 opened this issue Mar 22, 2022 · 0 comments · Fixed by #662
Assignees
Labels
bug cleanup Refactoring, clean-up unsound
Milestone

Comments

@sim642
Copy link
Member

sim642 commented Mar 22, 2022

We have at least three lockset analyses:

  1. mutex – must locksets,
  2. maylocks – may locksets,
  3. deadlock – may locking events (locks with location).

These could be combined into a single framework, where Lock and Unlock events work for all of them.


We don't have a maintained may lockset analysis. Besides the deadlock analysis keeping its own may locks events, we also have some ancient maylocks analysis, which is very outdated compared to mutex analysis. With path-sensitivity they should almost always coincide.

The case code you linked is just the tip of the ice berg though of a more general issue that we need to refactor our must/may lockset analyses. Ideally the Lock/Unlock events would be emitted the same regardless and the difference is just in whether the local domain is reversed or not. For example, both mutex and maylocks analyses could be just instantiated from a functor with local domains having locksets with differing lattice orderings. And similarly this deadlock analysis would just instantiate it with a may lock events set.

The code you point out isn't just a problem for the deadlock analysis, but probably also some privatizations, where we require mutex path-sensitivity to avoid the may-must distinction. With ambiguous lockings the code avoids any events altogether (which is just appropriate for must locksets), but then we also lack any path-sensitivity accounting for the actual possibilities, which in turn could make such privatizations unsound.

Originally posted by @sim642 in #655 (comment)

@sim642 sim642 added cleanup Refactoring, clean-up bug labels Mar 22, 2022
@sim642 sim642 self-assigned this Mar 23, 2022
@sim642 sim642 mentioned this issue Mar 23, 2022
5 tasks
@sim642 sim642 added the unsound label Mar 23, 2022
@sim642 sim642 added this to the v2.0.0 milestone Aug 12, 2022
sim642 added a commit to sim642/opam-repository that referenced this issue Aug 18, 2022
CHANGES:

Goblint "lean" release after a lot of cleanup.

* Remove unmaintained analyses: OSEK, ARINC, shapes, containment, deadlocksByRaces (goblint/analyzer#460, goblint/analyzer#736, goblint/analyzer#812, goblint/analyzer#474).
* Add interactive analysis (goblint/analyzer#391).
* Add server mode (goblint/analyzer#522).
* Add Compilation Database support (goblint/analyzer#406, goblint/analyzer#448).
* Add floating point domain, unrolled array domain and improved struct domains (goblint/analyzer#734, goblint/analyzer#761, goblint/analyzer#577, goblint/analyzer#419).
* Add static loop unrolling and heap variable unrolling (goblint/analyzer#563, goblint/analyzer#722).
* Improve race detection with may-happen-in-parallel analysis (goblint/analyzer#529, goblint/analyzer#518, goblint/analyzer#595).
* Reimplement lockset and deadlock analyses (goblint/analyzer#659, goblint/analyzer#662, goblint/analyzer#650, goblint/analyzer#655).
* Add pthread extraction to Promela (goblint/analyzer#220).
* Add location spans to output (goblint/analyzer#428, goblint/analyzer#449).
* Improve race reporting (goblint/analyzer#550, goblint/analyzer#551).
* Improve dead code reporting (goblint/analyzer#94, goblint/analyzer#353, goblint/analyzer#785).
* Refactor warnings (goblint/analyzer#55, goblint/analyzer#783).
* Add JSON schema for configuration (goblint/analyzer#476, goblint/analyzer#499).
* Refactor option names (goblint/analyzer#28, goblint/analyzer#192, goblint/analyzer#516, goblint/analyzer#675).
* Add bash completion (goblint/analyzer#669).
* Add OCaml 4.13 and 4.14 support, remove OCaml 4.09 support (goblint/analyzer#503, goblint/analyzer#672).
sim642 added a commit to sim642/opam-repository that referenced this issue Aug 18, 2022
CHANGES:

Goblint "lean" release after a lot of cleanup.

* Remove unmaintained analyses: OSEK, ARINC, shapes, containment, deadlocksByRaces (goblint/analyzer#460, goblint/analyzer#736, goblint/analyzer#812, goblint/analyzer#474).
* Add interactive analysis (goblint/analyzer#391).
* Add server mode (goblint/analyzer#522).
* Add Compilation Database support (goblint/analyzer#406, goblint/analyzer#448).
* Add floating point domain, unrolled array domain and improved struct domains (goblint/analyzer#734, goblint/analyzer#761, goblint/analyzer#577, goblint/analyzer#419).
* Add static loop unrolling and heap variable unrolling (goblint/analyzer#563, goblint/analyzer#722).
* Improve race detection with may-happen-in-parallel analysis (goblint/analyzer#529, goblint/analyzer#518, goblint/analyzer#595).
* Reimplement lockset and deadlock analyses (goblint/analyzer#659, goblint/analyzer#662, goblint/analyzer#650, goblint/analyzer#655).
* Add pthread extraction to Promela (goblint/analyzer#220).
* Add location spans to output (goblint/analyzer#428, goblint/analyzer#449).
* Improve race reporting (goblint/analyzer#550, goblint/analyzer#551).
* Improve dead code reporting (goblint/analyzer#94, goblint/analyzer#353, goblint/analyzer#785).
* Refactor warnings (goblint/analyzer#55, goblint/analyzer#783).
* Add JSON schema for configuration (goblint/analyzer#476, goblint/analyzer#499).
* Refactor option names (goblint/analyzer#28, goblint/analyzer#192, goblint/analyzer#516, goblint/analyzer#675).
* Add bash completion (goblint/analyzer#669).
* Add OCaml 4.13 and 4.14 support, remove OCaml 4.09 support (goblint/analyzer#503, goblint/analyzer#672).
# for free to join this conversation on GitHub. Already have an account? # to comment
Labels
bug cleanup Refactoring, clean-up unsound
Projects
None yet
Development

Successfully merging a pull request may close this issue.

1 participant