Lab: Deadlock Detector

Assigned

• March 24, 2026

Due

• April 7, 2026 11:59pm

For the fourth and final lab in this course, you will implement a too, that can detect and report potential deadlocks in programs that use pthreads for concurrency. Specifically, your tool will use a technique called library interposition to catch calls to the pthread_mutex_lock and pthread_mutex_unlock to examine the locking behavior of the program before moving on to the actual lock and unlock operations. Your program will look for cases where a program holds multiple locks at one time, but does not acquire these locks in a consistent order. This technique is somewhat similar to the race detection in Eraser, since it can report a potential issue without requiring the precise timing required for deadlock to occur.

Deadlock Detection

You may recall from CSC 213 that there are four conditions that must all be met for deadlock to occur:

1. Mutual Exclusion: the program uses locks
2. No Preemption: locks cannot be taken from a thread that holds them
3. Hold and Wait: threads can hold one lock while they wait for another
4. Circular Wait: a cycle of threads holding a lock while waiting for the next thread in the cycle)

A standard technique to prevent deadlock is to force threads to acquire locks in a consistent order. This eliminates condition 4, making deadlock impossible. So, if thread T1 acquires lock A, lock B, and then lock C, all other threads that hold any combination of these locks must acquire them in the same order. Another thread T2 could safely acquire lock B then lock C, but if it then acquired lock A that creates the potential for deadlock.

Your deadlock detector will need to keep record these partial orderings of locks (A before B, B before C in the example above) any time the program acquires multiple locks. If it ever discovers a thread that acquires a lock in a disallowed order, it should report the error to the end user. You can use the backtrace and backtrace_symbols functions or the addr2line command line tool to give source location information to the user if the program being tested was built with debug information.

Library Interposition

Your deadlock detector will need to work with unmodified programs that use POSIX locks. To do this, you will implement your tool in a shared library that can be added to the program at runtime, similar to the mechanism we used to replace malloc and free in the memory allocator lab in CSC 213.

Your tool will be implemented in a shared library. For the sake of example, let’s presume that your entire tool implementation is in the file no_deadlock.c. To create a shared library from no_deadlock.c you can compile it with the command:

$ clang -shared -fPIC -o no_deadlock.so no_deadlock.c -ldl

You could technically leave off the -ldl flag at the end to compile a shared library, but we are going to use the dynamic linker library (libdl) in a moment so it is important to include it here.

Now that you have produced a shared library called no_deadlock.so, we can inject this library into a program by running it with the LD_PRELOAD environment variable:

$ LD_PRELOAD=./no_deadlock.so ~/csc213/exercises/bank/bank-test

The command above will run the program—in this case, the bank example from CSC 213—normally, but with one important change. The dynamic linker will look inside no_deadlock.so first any time it tries to find a library function for bank. If you wrote a function named pthread_mutex_lock in no_deadlock.c, the bank-test program will call that function instead of the one in the pthreads library. This allows you to catch all calls to pthread_mutex_lock and pthread_mutex_unlock so you can record and check the lock acquisition order as the program runs.

You can think of a lock’s address (the pthread_mutex_t* parameter) as its unique identifier; all lock or unlock operations on this mutex will use the same pointer value as the parameter. I recommend that you use an approach that only tracks ordering between locks that are actually acquired together. If two locks are never held at the same time, there is no reason to record anything about their acquisition order.

Once you’ve recorded information about the lock acquisition order, you need to perform the actual lock or unlock operation. We have two choices at this point; we could implement our own locks entirely within no_deadlock.so, or we could locate and call the real pthread_mutex_lock and pthread_mutex_unlock functions. We’ll opt for the second choice in this case, since it is less likely to change the runtime behavior of the program we are testing.

We’ll use the dlsym function from libdl to look up functions in the pthreads library. This function looks up a function by name in some specified shared library and returns it; we’ll use the special library identifier RTLD_NEXT to tell dlsym to begin looking in the next shared library after the current one. This ensures we don’t locate the pthread_mutex_lock function defined in no_deadlock.c, but instead find the one from pthreads that is hidden by our injected library. The following code should be able to call the real pthread_mutex_lock function:

#include <stdio.h>
#include <unistd.h>
#include <dlfcn.h>

typedef int (*mutex_fn_t)(pthread_mutex_t*);

// Call the real pthread_mutex_lock function from libpthread
int real_pthread_mutex_lock(pthread_mutex_t* m) {
  // Keep track of the real function so we only have to look it up once
  static mutex_fn_t real_fn = NULL;

  // Look up the real function if necessary
  if (real_fn == NULL) {
    real_fn = dlsym(RTLD_NEXT, "pthread_mutex_lock");
    if (real_fn == NULL) {
      fprintf(stderr, "Failed to locate pthread_mutex_lock: %s\n", dlerror());
    }
  }

  // Call the real function
  return real_fn(m);
}

Requirements

Here is a brief overview of the requirements for your deadlock detection tool. You are free to make many implementation decisions, but make sure your implementation meets these requirements.

Library Interposition

You must use the library interposition technique discussed above to track lock acquisition. There may be other ways to get information about locks, but

Lock Ordering

Your deadlock detector must check lock ordering to report potential deadlock. This is strictly more powerful than detecting when deadlock has actually occurred. In the same way that Eraser can report potential races even when they haven’t actually happened, your deadlock detector will be able to report potential errors without the precise timing required to result in an actual deadlock.

Source Location

Your deadlock detector must report source locations (e.g. using backtrace and backtrace_symbols or the addr2line command line tool) when it detects a potential deadlock. At a minimum, you should report the lock ordering that was violated and the source line where the disallowed lock acquisition was issued. It may be more helpful if you can report more information about other uses of the locks in question or the source location of the locks themselves, but this is not required.

Other Synchronization Primitives

Your deadlock detector does not need to work with programs that use condition variables or semaphores. Only pthread_mutex_lock and pthread_mutex_unlock will be used by the test programs.