4
\$\begingroup\$

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 <unistd.h>
  #include <limits.h>
  #include <sys/syscall.h>
  #include <linux/futex.h>
  #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
\$\endgroup\$
  • \$\begingroup\$ Doesn't pthreads map the mutex implementation onto a futex on Linux platforms for you for free? \$\endgroup\$ – Flexo Aug 10 '11 at 12:51
  • \$\begingroup\$ it does, but the use case that i am looking for does not permits using the pthread library \$\endgroup\$ – Sudhanshu Aug 10 '11 at 20:25
5
\$\begingroup\$

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);
            }
        }
    }
    
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.