Non-Blocking Timeout in a NUMA-Aware Queue-Based Spin Lock

typedef struct qnode {
    struct qnode *volatile prev;
    volatile qnode_status status;
    struct qnode *volatile next;
} qnode;

typedef qnode *volatile qnode_ptr;

typedef struct {
    qnode_ptr tail;
    qnode_ptr lock_holder;   // node allocated by lock holder,
        // on which next process in line (if any) is spinning
} lock;

#define AVAILABLE   ((qnode_ptr) 0x1)
#define LEAVING     ((qnode_ptr) 0x2)

#define alloc_qnode() (qnode_ptr) \
    alloc_local_qnode(my_head_node_ptr())
#define free_qnode(p) free_local_qnode((local_qnode *) p)

#define qn_swap(p,v) (qnode_ptr) \
    swap((volatile unsigned long*) (p), (unsigned long) (v))
#define s_swap(p,v) (qnode_status) \
    swap((volatile unsigned long*) (p), (unsigned long) (v))

bool try_acquire(lock *L, hrtime_t T)
{
    qnode_ptr I = alloc_qnode();
    qnode_ptr tmp, pred, pred_pred;
    hrtime_t start;

    I->status = waiting;
    I->prev = NULL;
    I->next = NULL;
    pred = qn_swap(&L->tail, I);

    start = START_TIME;

    // On each pass through the loop we link to a new predecessor
    while (1) {
	tmp = qn_swap(&pred->next, I);
	if (tmp == AVAILABLE) {
	    // lock was free; just return
	    L->lock_holder = I;
	    free_qnode(pred);
	    return true;
	}
        if (!tmp) {
spin:       // We're linked into the queue, so we spin on our status
	    while (I->status == waiting)
		if (CUR_TIME - start > T)
		    goto timeout;
	    if (I->status == available) {
		L->lock_holder = I;
		free_qnode(pred);
		return true;
	    }
	    // else I->status == leaving
	    I->status = waiting; // reset status
	    // fall through to predecessor-timed-out case
	}

	// Predecessor timed out, get new predecessor
        pred_pred = pred->prev;
        tmp = qn_swap(&pred_pred->next, I);
        if (tmp == pred) {
            free_qnode(pred);
            pred = pred_pred;
            goto spin; // target is UP 20 lines
        }
        else if (tmp == AVAILABLE) {
            /* Pred_pred will try to access pred's status;
                we and it are in a race. */
            if (s_swap(&pred->status, available) == available) {
                /* Pred_pred got to the status before we did.  We're
                   going to get the lock (next time around).  We must
                   recycle pred. */
                free_qnode(pred);
            } /* else swap returned waiting.  We won the race to get to
                pred's status.  Pred_pred will still try to access the
                status at some point.  It will know to recycle pred. */

	    // Recycle pred_pred and take the lock
	    L->lock_holder = I;
	    free_qnode(pred_pred);
	    return true;
        }
        else {
            /* Pred_pred will try to access pred's status;
                we and it are in a race. */
            if (s_swap(&pred->status, leaving) == leaving) {
                /* Pred_pred got to the status before we did.  We are
                   responsible for recycling pred. */
                free_qnode(pred);
            } /* else we won the race.  Pred_pred will still try to
               access the status at some point.  It will know to
               recycle pred. */

            pred = pred_pred;
            pred->next = LEAVING;
                /* to fool ourselves into thinking this is a normal
                   top-of-loop case.  Note that pred (formerly
                   pred_pred) has already either tried to release the
                   lock or timed out, so it won't subsequently try to
                   change the field we just wrote into, so the plain
                   write (not swap) is safe.  */
	    if (CUR_TIME - start > T || pred->next != LEAVING) {
		break; // drop to timeout code below
	    }
        }
    }

    // At this point we have timed out, and need to leave
    // as quickly as possible
  timeout:
    I->prev = pred;
    tmp = qn_swap(&I->next, LEAVING);
    if (tmp) {
	// Tell my successor I've timed out
	if (s_swap(&tmp->status, leaving) == leaving) {
	    /* My succesor's successor beat me to this point, so I
	       need to recycle my succssor's node. This status value
	       implies that my successor is also timed out. */
	    free_qnode(tmp);
	}
    }
    return false;
}

void release(lock *L)
{
    qnode_ptr I = L->lock_holder;
    I->prev = AVAILABLE;
}

Last Change: 6 February 2004 /