Skip to content

Fix top thread ID set issues from sv-benchmarks#388

Merged
sim642 merged 12 commits intomasterfrom
issue-386
Oct 13, 2021
Merged

Fix top thread ID set issues from sv-benchmarks#388
sim642 merged 12 commits intomasterfrom
issue-386

Conversation

@sim642
Copy link
Copy Markdown
Member

@sim642 sim642 commented Oct 12, 2021

Closes #386.

Fixes three cases of top thread ID sets having appeared:

  1. Joining in partitioned arrays.
  2. Casting around malloc-ed thread ID arrays.
  3. Invalidation of thread ID sets during invalidation, e.g. free.

It's just hacks on top of hacks on top of hacks.

@sim642 sim642 added bug sv-comp SV-COMP (analyses, results), witnesses labels Oct 12, 2021
@sim642 sim642 added this to the SV-COMP 2022 milestone Oct 12, 2021
@michael-schwarz michael-schwarz self-requested a review October 12, 2021 10:52
Copy link
Copy Markdown
Member

@michael-schwarz michael-schwarz left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think this fixes the immediate issue.

For a more thorough approach: Would it be worth having something like we do for pointers, where we add an unknown_thread to the set (like we have unknown_pointer) but sill keep the threads that we have?

| (`Thread x, `Thread y) -> `Thread (Threads.join x y)
| (`Int x, `Thread y)
| (`Thread y, `Int x) ->
`Thread y (* TODO: ignores int! *)
Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Maybe at least produce a warning here and in the other similar cases?

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Since this is now required for normal operation (where the program doesn't even do weird stuff like try to manipulate a pthread_t as an integer), then it would be confusing, because it's not a fault in the program, but just in our handling of it. And you would always see this.

@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Oct 12, 2021

For a more thorough approach: Would it be worth having something like we do for pointers, where we add an unknown_thread to the set (like we have unknown_pointer) but sill keep the threads that we have?

It would make Thread invalidation a bit more sensible by not just keeping the current one but adding something. Although it will make absolutely no difference (other than having to filter it out everywhere) if we don't properly and soundly handle unknown threads. Given that we don't properly handle unknown pointers anyway, it's probably not worth the effort now.

Also, it wouldn't save us from all the weird lattice hacks between Thread and Int, just like how it doesn't save Address from them.

@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Oct 12, 2021

Ugh, this doesn't even work for macOS because there pthread_t isn't an integer but some struct pointer. So we also need Address and Thread to join into a Thread...

@michael-schwarz
Copy link
Copy Markdown
Member

Although it will make absolutely no difference (other than having to filter it out everywhere) if we don't properly and soundly handle unknown threads.

There are many cases where we actually do the sound thing (in creating all required threads) and as long as we are not overzealous about exploiting pthread_join(...) we are on the safe side.

Joining a thread id and and an int by ignoring the int means that when we call a pthread_join it looks as if we have a set of thread ids (or in the worst case a singleton), where in fact we incurred imprecision and our thread set does potentially not soundly describe all threads. In such a case, we should not exploit anything we learn through the pthread_join, because there are possibly other threads. But at this pthread_join there is no way of knowing if this issue occurred.

If we add this unknown_thread upon invalidation, we could warn on such a pthread_join (maybe it is indeed a bug), and offer an option how to proceed in such a case (as we do with unknown pointers).

@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Oct 12, 2021

There are many cases where we actually do the sound thing (in creating all required threads) and as long as we are not overzealous about exploiting pthread_join(...) we are on the safe side.

Not really, if we already have an unknown function pointer somehow, then spawning a thread from it will not spawn all the functions. Just like calling an unknown function pointer doesn't call all the functions.

If we add this unknown_thread upon invalidation, we could warn on such a pthread_join (maybe it is indeed a bug), and offer an option how to proceed in such a case (as we do with unknown pointers).

That only covers invalidation, but not any of the other cases Int and Thread might get joined (initialization, branched thread creation, joins inside partitioned arrays).

@michael-schwarz
Copy link
Copy Markdown
Member

That only covers invalidation, but not any of the other cases Int and Thread might get joined (initialization, branched thread creation, joins inside partitioned arrays).

Why would the same logic not apply for all the other cases you listed?

@sim642
Copy link
Copy Markdown
Member Author

sim642 commented Oct 12, 2021

Why would the same logic not apply for all the other cases you listed?

The solution you proposed was "add this unknown_thread upon invalidation". Or was it somehow unrelated?

@michael-schwarz
Copy link
Copy Markdown
Member

Ah, sorry, I should have been more specific.
I meant "add this unknown_thread upon invalidation or incompatible join/widen/...".

@sim642 sim642 merged commit e168a4e into master Oct 13, 2021
@sim642 sim642 deleted the issue-386 branch October 13, 2021 09:50
@sim642 sim642 mentioned this pull request Oct 13, 2021
@sim642 sim642 added the hacktoberfest-accepted https://hacktoberfest.digitalocean.com/ label Oct 16, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

bug hacktoberfest-accepted https://hacktoberfest.digitalocean.com/ sv-comp SV-COMP (analyses, results), witnesses

Projects

None yet

Development

Successfully merging this pull request may close these issues.

Top thread ID sets inside partitioned arrays

2 participants