Deadlock Empire

This is a short writeup of a small programming game @damageboy introduced me to. The game focuses on finding and exploiting race conditions in an environment similar to .net.

Link to the game and my forked copy of the game (to make sure the link keeps working). All credit for the game goes to the original programmers, Petr Hudeček and Michal Pokorný on HackCambridge 2016.

## The game

The game is simple, you are the scheduler and can control and interleave operations across threads. The operations can be atomic, such as semaphore.Release(); or non atomic operations such as x = x +1 . The goal is to reach a non safe state for each code snippet, non safe can be removing an item from an empty queue, a dead lock, livelock, etc.

Selected levels

Confused Counter

This level is a good introduction to the fact nothing should be considered atomic unless explicitly defined this way.

Many programmers are used to the idea that ++x is translated to x=x+1 and some programmers who understand machine instructions understand this may be transformed to the following instruction sequence.

mov eax, [x]
add x,1
mov [x],eax

Clearly this sequence is not atomic but some programmers believe that add [x],1 is atomic!

Clearly after this introduction, we notice that given careful scheduling we can reach the following state

And we will enter the if block and hit the assert.

Producer Consumer

Another good example that nothing is atomic unless explicitly mentioned as such.

This game is based on .net objects, which are not automatically thread safe and therfore, it’s easy to to reach a state where the Queue.Count is greater than 0 but there’s no object yet inside the queue.

Barriers

In .net, Barriers function like club bouncers. They wait for a specified amount of threads to reach the barrier then let them through at once. This is obviously problematic if you don’t know the precise amount of threads you want to participate.

Note the barrier here waits for 2 threads and we have 3. Our goal is to reach Debug.Assert. Note that at every stage, the counter is properly handled!

Given the above, can you reverse engineer how I reached the following state?

Locking scope

The following code for the Dragon Head threads is correct except for one basic flaw, the lock should be outside the lock :)

Why is this problematic?

A note

This game is a cute example but no one should be writing application code that looks like this in 2020 unless they’re doing low level programming.

Reactive programming, based on callbacks and with strong control of scope have proven to be safely usably by programmers without special training.