Mutex and condition variable implementation using futex

I have implemented mutex and conditional variables using the futex syscall. I believe that my implementation is correct, but would like it to be verified by someone else. Any suggestions for further improvements in the performance of the mutex and conditional variables would also be appreciated.

#ifndef __SYNCHRONIZATION__
  #define __SYNCHRONIZATION__

  #include 
  #include 
  #include 
  #include 
  #include "types.h"
  #include "assembly.h"

  typedef UINT32 mutex;
  typedef struct condvar condvar;

  struct condvar    {
   mutex *m;
   int seq;
  };

  void mutex_init(mutex *m) {
   *m = 0;
  }

  void mutex_destroy(mutex *m)  {
   *m = 0;
  }

  void mutex_lock(mutex *m) {
   UINT32 c;
   if((c = __sync_val_compare_and_swap(m, 0, 1)) != 0)  {
    do  {
        if((c == 2) || __sync_val_compare_and_swap(m, 1, 2) != 0)
            syscall(SYS_futex, m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
    } while((c = __sync_val_compare_and_swap(m, 0, 2)) != 0);
   }
  }

  void mutex_unlock(mutex *m)   {
   if(__sync_fetch_and_sub(m, 1) != 1)  {
    *m = 0;
    syscall(SYS_futex, m, FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
   }
  }

  void cond_init(condvar *c, mutex *m)  {
   c->m = m;
   c->seq = 0;
  }

  void cond_destroy(condvar *c) {
   c->m = NULL;
   c->seq = 0;
  }

  void cond_signal(condvar *c)  {
   __sync_fetch_and_add(&(c->seq), 1);
   syscall(SYS_futex, &(c->seq), FUTEX_WAKE_PRIVATE, 1, NULL, NULL, 0);
  }

  void cond_broadcast(condvar *c)   {
   __sync_fetch_and_add(&(c->seq), 1);
   syscall(SYS_futex, &(c->seq), FUTEX_REQUEUE_PRIVATE, 1, (void *) INT_MAX, c->m, 0);
  }

  void cond_wait(condvar *c)    {
   UINT32 oldSeq = c->seq;
   mutex_unlock(c->m);
   syscall(SYS_futex, &(c->seq), FUTEX_WAIT_PRIVATE, oldSeq, NULL, NULL, 0);
   while (xchg32(c->m, 2))  {
    syscall(SYS_futex, c->m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);
   }
  }

  #endif

I have no particular experience of Futex code, so take this with caution:

Looking at mutex_lock, I think some comments would have been useful. As I
understand it, this is what it does:

-
Firstly let's define what your values 0, 1, 2 mean. I understand them to
mean 'free', 'locked', 'locked and contested' respectively. Some #defined
constants would have made that clear (assuming it is right).

-
The first compare-and-swap tries to lock the mutex.

if((c = __sync_val_compare_and_swap(m, 0, 1)) != 0)  {

If this succeeds, the
function exits with the mutex locked (ie. its value is 1). However if the
mutex was not unlocked (0) this fails and we enter the do...while loop.

-
At this point we know the mutex is (or was, to be precise - it might have
changed) either locked or contested. If it was contested we want to make a
futex system call to wait for it to be unlocked.

if((c == 2) || __sync_val_compare_and_swap(m, 1, 2) != 0)
        syscall(SYS_futex, m, FUTEX_WAIT_PRIVATE, 2, NULL, NULL, 0);

Hence we make the system
call either if we know the mutex was contested (c == 2) or if it was
only locked and we succeeded in setting it contested. But because the mutex
might have changed since the first compare-and-swap, we have to do another
compare-and-swap to swap its locked 1 for a contested 2. If the mutex
changed state and is no longer locked, this will fail and we don't make the
system call. (Note that the system call itself has protection against the mutex changing state before it is entered, hence the '2' parameter which ensures that if *m is not 2 the kernel will not be entered.)

-
If we either didn't make the system call (because the mutex had changed) or
we made the call and it returned (again because the mutex state had changed)
we reach the while part of the loop.

} while((c = __sync_val_compare_and_swap(m, 0, 2)) != 0);

We can expect the mutex to be free
(0) at this point and that we can try to lock it. But instead the code
tries to set it to contested (2). If it succeeds the loop and function exit
with the mutex set to contested, not just locked. This seems wrong - the
last compare-and-swap should be setting '1', not '2'. If we replace the 2
with a 1, the loop exit condition is the same as the condition at the start
of the function and we can simplify to:

enum mutex_state {
    FREE = 0,
    LOCKED,
    CONTESTED
};

void mutex_lock(mutex *m)
{
    enum mutex_state c;
    while ((c = __sync_val_compare_and_swap(m, FREE, LOCKED)) != FREE)  // set locked
    {
        if ((c == CONTESTED) ||
            __sync_val_compare_and_swap(m, LOCKED, CONTESTED) != FREE)  // set contested
        {
            syscall(SYS_futex, m, FUTEX_WAIT_PRIVATE, CONTESTED, NULL, NULL, 0);
        }
    }
}

StackExchange Code Review Q#4005, answer score: 5