Skip to content

Instantly share code, notes, and snippets.

@LouisJenkinsCS
Last active March 11, 2020 22:44
Show Gist options
  • Save LouisJenkinsCS/9f318e92fb7a028d88015e08a02ac640 to your computer and use it in GitHub Desktop.
Save LouisJenkinsCS/9f318e92fb7a028d88015e08a02ac640 to your computer and use it in GitHub Desktop.
PMAT Durable Queue Bugs Found

The Durable Queue was slightly modified to ignore return value, and so the verifier does not look at this at all.

Bug #1 - Remove CLFLUSH of node->value [Found]

This bug will not explicitly CLFLUSH the value associated with the node. Within a single verification this bug was caught. The dumped information did show the location of the store.

Bug #2 - Remove CLFLUSH of last->next in successful enqueue [Found]

The bug will not explicitly CLFLUSH the last->next value, making inconsistency possible. Within two verifications, this bug was caught due to the tail not being found while traversing the list.

Bug #3 - Remove CLFLUSH of last->next in failed enqueue [Not Found]

This bug will not explicitly CLFLUSH the last->next value when a failed enqueue occurs, causing potential for inconsistency if successful thread gets preempted before it can flush it itself. This was not found even after 41600 verifications over the span of 5 minutes. Unfortunately, this is likely due to the specific interleavings required for this bug to come to light. A randomized/stochastic scheduler is required to better randomize the selection of threads, as currently a round-robin scheduler and unfair/biased scheduler is used; the former making this bug easier to be obscured, the latter being slow when stopping the application.

Bug #4 - Remove CLFLUSH of last->next when tail is outdated in dequeue [Not Found]

This bug will not explicitly CLFLUSH the last->next value when the queue tail has been detected as being outdated, causing potential for inconsistency if thread repairs the tail and then proceeds to modify the queue, resulting in a node missing in the queue. This requires a very specific interleaving, and so just like Bug #3, is not found.

Bug #5 - Remove CLFLUSH of head upon successful dequeue [Found]

This bug will not explicitly CLFLUSH the head after CAS'ing it forward. This results in an inconsistency where the head will refer to an outdated node that has already been reclaimed and can contain junk. This bug was found after 16 verifications; likely took longer due to undefined behavior.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment