Randomized Scheduler Lock for Valgrind.md

Globals

    // List of waiters...
    node *head;
    // -1: Free-for-All
    // 0 - N: Owned by thread id corresponding to lock value
    atomic<int> lock;

Acquire

// Ensure that no release is on-going and ensures we'd be visible...
// Reader lock?
enterAcquireBarrier();
if lock.CAS(-1, tid) {
 exitAcquireBarrier();
 return; // We have the lock
} else {
    node *n = new node();
    insert(&head, n);
    exitAcquireBarrier();
    waitFor(lock, tid);
    return; // Our turn to go...
 }
}

Release

// Ensure that no acquire operations occurs while we are doing this...
// Writer-lock?
enterReleaseBarrier();
if head != nullptr {
  // Someone is waiting; do not release lock, transfer ownership instead to random thread
  int tid = chooseRandom(head);
  lock.store(tid);
} else {
  lock.store(-1);
}
exitReleaseBarrier();