Pseudocode from article of the above name in PODC'02 (earlier but extended version available as a technical report). Copyright (c) 2002, by Michael L. Scott.
The CLH-NB try lock is derived from a version without timeout due to Craig, Landin, and Hagersten. It performs well on cache-coherent machines. Requires two words of space per uncontested lock. Worst-case space is unbounded; expected case is O(L+T) for L locks and T threads. Requires SWAP and either CAS or LL/SC, and supports a standard SPI, for compatibility with binary-only appliations.
The MCS-NB try lock is derived from our earlier version without timeout, due to Mellor-Crummey and Scott. It can be expected to perform well on both cache-coherent and non-cache-coherent machines. Also requires two words of space per lock, and has worst-case unbounded, expected case O(L+T) space. Significantly more complicated than the CLH-NB try lock. Like that lock, requires SWAP and either CAS or LL/SC, and supports a standard API, for compatibility with binary-only applications.
Both algorithms require space management code for dynamic allocation and reclamation of queue nodes. To avoid the ABA problem, the code must ensure that the space occupied by a reclaimed queue node is never reallocated by a different thread.
// Code to manage a local but shared pool of qnodes.
// All nodes are allocated by, and used by, a given thread, and may
// reside in local memory on an ncc-numa machine. The nodes belonging
// to a given thread form a circular singly linked list. The head
// pointer points to the node most recently successfully allocated.
// A thread allocates from its own pool by searching forward from the
// pointer for a node that's marked "unused". A thread (any thread)
// deallocates a node by marking it "unused".
typedef struct local_qnode {
union {
clh_nb_qnode cnq; // members of this union are
mcs_nb_qnode mnq; // never accessed by name
} real_qnode;
volatile bool allocated;
struct local_qnode *next_in_pool;
} local_qnode;
typedef struct {
local_qnode *try_this_one; // pointer into circular list
local_qnode initial_qnode;
} local_head_node;
inline local_qnode *alloc_local_qnode(local_head_node *hp)
{
local_qnode *p = hp->try_this_one;
if (!p->allocated) {
p->allocated = true;
return p;
} else {
local_qnode *q = p->next_in_pool;
while (q != p) {
if (!q->allocated) {
hp->try_this_one = q;
q->allocated = true;
return q;
} else {
q = q->next_in_pool;
}
}
// All qnodes are in use. Allocate new one and link into list.
q = (local_qnode *) malloc(sizeof(local_qnode));
q->next_in_pool = p->next_in_pool;
p->next_in_pool = q;
hp->try_this_one = q;
q->allocated = true;
return q;
}
}
#define free_local_qnode(p) ((p)->allocated = false)
typedef struct clh_nb_qnode {
struct clh_nb_qnode *volatile prev;
} clh_nb_qnode;
typedef struct {
clh_nb_qnode *volatile tail;
clh_nb_qnode *lock_holder; // node allocated by lock holder
} clh_nb_lock;
#define AVAILABLE ((clh_nb_qnode *) 1)
#define cqn_swap(p,v) (clh_nb_qnode *) \
swap((volatile unsigned long*) (p), (unsigned long) (v))
#define compare_and_store(p,o,n) \
(cas((volatile unsigned long *) (p), \
(unsigned long) (o), (unsigned long) (n)) \
== (unsigned long) (o))
#define alloc_qnode() (clh_nb_qnode *) alloc_local_qnode(my_head_node_ptr())
#define free_qnode(p) free_local_qnode((local_qnode *) p)
bool clh_nb_try_acquire(clh_nb_lock *L, hrtime_t T)
{
clh_nb_qnode *I = alloc_qnode();
I->prev = 0;
clh_nb_qnode pred = cqn_swap(&L->tail, I);
if (!pred) {
// lock was free and uncontested; just return
L->lock_holder = I;
return true;
}
if (pred->prev == AVAILABLE) {
// lock was free; just return
L->lock_holder = I;
free_qnode(pred);
return true;
}
hrtime_t start = START_TIME;
while (CUR_TIME - start < T) {
clh_nb_qnode *pred_pred = pred->prev;
if (pred_pred == AVAILABLE) {
L->lock_holder = I;
free_qnode(pred);
return true;
} else if (pred_pred) {
free_qnode(pred);
pred = pred_pred;
}
}
// timed out; reclaim or abandon own node
if (compare_and_store(&L->tail, I, pred)) {
// last process in line
free_qnode(I);
} else {
I->prev = pred;
}
return false;
}
void clh_nb_try_release(clh_nb_lock *L)
{
clh_nb_qnode *I = L->lock_holder;
if (compare_and_store(&L->tail, I, 0)) {
// no competition for lock; reclaim qnode
free_qnode(I);
} else {
I->prev = AVAILABLE;
}
}
typedef enum {available, leaving, transient, waiting, recycled} qnode_status;
typedef struct mcs_nb_qnode {
struct mcs_nb_qnode *volatile prev;
struct mcs_nb_qnode *volatile next;
volatile qnode_status status;
} mcs_nb_qnode;
typedef struct {
mcs_nb_qnode *volatile tail;
mcs_nb_qnode *lock_holder; // node allocated by lock holder
} mcs_nb_lock;
#define AVAILABLE ((mcs_nb_qnode *) 1)
#define LEAVING ((mcs_nb_qnode *) 2)
#define TRANSIENT ((mcs_nb_qnode *) 3)
// Thread puts TRANSIENT in its next pointer and, if possible, transient
// in its successor's status word, when it wants to leave but was unable
// to break the link to it from its precedessor.
#define mqn_swap(p,v) (mcs_nb_qnode *) \
swap((volatile unsigned long *) (p), (unsigned long) (v))
#define s_swap(p,v) (qnode_status)
swap((volatile unsigned long *) (p), (unsigned long) (v))
#define alloc_qnode() (mcs_nb_qnode *) alloc_local_qnode(my_head_node_ptr())
bool mcs_nb_try_acquire(mcs_nb_lock *L, hrtime_t T)
{
mcs_nb_qnode *I = alloc_qnode();
mcs_nb_qnode *pred_next;
I->next = 0;
mcs_nb_qnode *pred = mqn_swap(&L->tail, I);
if (!pred) {
L->lock_holder = I;
return true;
}
hrtime_t start = START_TIME;
I->status = waiting;
while (1) {
pred_next = mqn_swap(&pred->next, I);
/* If pred_next is not nil then my predecessor tried to leave or
grant the lock before I was able to tell it who I am. Since it
doesn't know who I am, it won't be trying to change my status
word, and since its CAS on the tail pointer, if any, will have
failed, it won't have reclaimed its own qnode, so I'll have to. */
if (pred_next == AVAILABLE) {
L->lock_holder = I;
free_qnode(pred);
return true;
} else if (!pred_next) {
while (1) {
if (CUR_TIME - start > T) {
goto timeout1;
}
qnode_status stat = I->status;
if (stat == available) {
L->lock_holder = I;
free_qnode(pred);
return true;
} else if (stat == leaving) {
mcs_nb_qnode *new_pred = pred->prev;
free_qnode(pred);
pred = new_pred;
I->status = waiting;
break; // exit inner loop; continue outer loop
} else if (stat == transient) {
mcs_nb_qnode *new_pred = pred->prev;
if (s_swap(&pred->status, recycled) != waiting) {
free_qnode(pred);
} /* else when new predecessor changes this to available,
leaving, or transient it will find recycled, and will
reclaim old predecessor's node. */
pred = new_pred;
I->status = waiting;
break; // exit inner loop; continue outer loop
} // else stat == waiting; continue inner loop
}
} else if (CUR_TIME - start > T) {
goto timeout2;
} else if (pred_next == LEAVING) {
mcs_nb_qnode *new_pred = pred->prev;
free_qnode(pred);
pred = new_pred;
} else if (pred_next == TRANSIENT) {
mcs_nb_qnode *new_pred = pred->prev;
if (s_swap(&pred->status, recycled) != waiting) {
free_qnode(pred);
} /* else when new predecessor changes this to available,
leaving, or transient it will find recycled, and will
reclaim old predecessor's node. */
pred = new_pred;
}
}
timeout1: {
I->prev = pred;
if (compare_and_store(&pred->next, I, 0)) {
// predecessor doesn't even know I've been here
mcs_nb_qnode *succ = mqn_swap(&I->next, LEAVING);
if (succ) {
if (s_swap(&succ->status, leaving) == recycled) {
/* Timing window: successor already saw my modified
next pointer and declined to modify it. Nobody is
going to look at my successor node, but they will
see my next pointer and know what happened. */
free_qnode(succ);
} /* else successor will reclaim me when it sees my
change to its status word. */
} else {
// I don't seem to have a successor.
if (compare_and_store(&L->tail, I, pred)) {
free_qnode(I);
} /* else a newcomer hit the timing window or my successor
is in the process of leaving. Somebody will discover
I'm trying to leave, and will free my qnode for me. */
}
} else {
/* Predecessor is trying to leave or to give me (or somebody)
the lock. It has a pointer to my qnode, and is planning
to use it. I can't wait for it to do so, so I can't free
my own qnode. */
mcs_nb_qnode *succ = mqn_swap(&I->next, TRANSIENT);
if (succ) {
if (s_swap(&succ->status, transient) == recycled) {
/* Timing window: successor already saw my modified
next pointer and declined to modify it. Nobody is
going to look at my successor node, but they will see
my next pointer and know what happened. */
free_qnode(succ);
} /* else successor will reclaim me when it sees my
change to its status word. */
} /* else I don't seem to have a successor, and nobody can
wait for my status word to change. This is the
pathological case where we can temporarily require
non-linear storage. */
}
return false;
}
timeout2: {
/* pred_next is LEAVING or TRANSIENT; pred->next is I.
Put myself in transient state, so some successor can
eventually clean up. */
mcs_nb_qnode *succ;
/* put predecessor's next field back, as it would be if I
had timed out in the inner while loop and been unable to
update predecessor's next pointer: */
pred->next = pred_next;
I->status = (pred_next == LEAVING ? leaving : transient);
I->prev = pred;
succ = mqn_swap(&I->next, TRANSIENT);
if (succ) {
if (s_swap(&succ->status, transient) == recycled) {
/* Timing window: successor already saw my modified next
pointer and declined to modify it. Nobody is going
to look at my successor node, but they will see my
next pointer and know what happened. */
free_qnode(succ);
} /* else successor will reclaim me when it sees my change
to its status word. */
} /* else I don't seem to have a successor, and nobody can wait
for my status word to change. This is the pathological case
where we can temporarily require non-linear storage. */
return false;
}
}
void mcs_nb_try_release(mcs_nb_lock *L)
{
mcs_nb_qnode *I = L->lock_holder;
mcs_nb_qnode *succ = mqn_swap(&I->next, AVAILABLE);
/* As a general rule, I can't reclaim my own qnode on release because
my successor may be leaving, in which case somebody is going to
have to look at my next pointer to realize that the lock is
available. The one exception (when I *can* reclaim my own node)
is when I'm able to change the lock tail pointer back to nil. */
if (succ) {
if (s_swap(&succ->status, available) == recycled) {
/* Timing window: successor already saw my modified next
pointer and declined to modify it. Nobody is going to
look at my successor node, but they will see my next
pointer and know what happened. */
free_qnode(succ);
} /* else successor (old or new) will reclaim me when it sees my
change to the old successor's status word. */
} else {
// I don't seem to have a successor.
if (compare_and_store(&L->tail, I, 0)) {
free_qnode(I);
} /* else a newcomer hit the timing window or my successor is in
the process of leaving. Somebody will discover I'm giving
the lock away, and will free my qnode for me. */
}
}
