LIBRARY

Concurrency Kit (libck, -lck)

SYNOPSIS

In ck_elide.h

ck_elide_stat_t stat = CK_ELIDE_STAT_INITIALIZER;

Ft void Fn ck_elide_stat_init ck_elide_stat_t *

struct ck_elide_config config = CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;

struct ck_elide_config {
unsigned short skip_busy;
short retry_busy;
unsigned short skip_other;
short retry_other;
unsigned short skip_conflict;
short retry_conflict;
};

Fn CK_ELIDE_PROTOTYPE NAME TYPE LOCK_PREDICATE LOCK_FUNCTION UNLOCK_PREDICATE UNLOCK_FUNCTION Fn CK_ELIDE_LOCK_ADAPTIVE NAME ck_elide_stat_t * struct ck_elide_config * TYPE * Fn CK_ELIDE_UNLOCK_ADAPTIVE NAME ck_elide_stat_t * TYPE * Fn CK_ELIDE_LOCK NAME TYPE * Fn CK_ELIDE_UNLOCK NAME TYPE * Fn CK_ELIDE_TRYLOCK_PROTOTYPE NAME TYPE LOCK_PREDICATE TRYLOCK_FUNCTION

DESCRIPTION

These macros implement lock elision wrappers for a user-specified single-argument lock interface. The wrappers will attempt to elide lock acquisition, allowing concurrent execution of critical sections that do not issue conflicting memory operations. If any threads have successfully elided a lock acquisition, conflicting memory operations will roll-back any side-effects of the critical section and force every thread to retry the lock acquisition regularly.

Fn CK_ELIDE_LOCK , Fn CK_ELIDE_UNLOCK , Fn CK_ELIDE_LOCK_ADAPTIVE , and Fn CK_ELIDE_UNLOCK_ADAPTIVE macros require a previous Fn CK_ELIDE_PROTOTYPE with the same Fa NAME . Elision is attempted if the Fa LOCK_PREDICATE function returns false. If Fa LOCK_PREDICATE returns true then elision is aborted and Fa LOCK_FUNCTION is executed instead. If any threads are in an elided critical section, Fa LOCK_FUNCTION must force them to rollback through a conflicting memory operation. The Fa UNLOCK_PREDICATE function must return true if the lock is acquired by the caller, meaning that the lock was not successfully elided. If Fa UNLOCK_PREDICATE returns true, then the Fa UNLOCK_FUNCTION is executed. If RTM is unsupported (no CK_F_PR_RTM macro) then Fn CK_ELIDE_LOCK and Fn CK_ELIDE_LOCK_ADAPTIVE will immediately call Fn LOCK_FUNCTION . Fn CK_ELIDE_UNLOCK and Fn CK_ELIDE_UNLOCK_ADAPTIVE will immediately call Fn UNLOCK_FUNCTION .

Fn CK_ELIDE_TRYLOCK requires a previous Fn CK_ELIDE_TRYLOCK_PROTOTYPE with the same name. Elision is attempted if the Fa LOCK_PREDICATE function returns false. If Fa LOCK_PREDICATE returns true or if elision fails then the operation is aborted. If RTM is unsupported (no CK_F_PR_RTM macro) then Fn CK_ELIDE_TRYLOCK will immediately call Fn TRYLOCK_FUNCTION .

Fn CK_ELIDE_LOCK_ADAPTIVE and Fn CK_ELIDE_UNLOCK_ADAPTIVE will adapt the elision behavior associated with lock operations according to the run-time behavior of the program. This behavior is defined by the ck_elide_config structure pointer passed to Fn CK_ELIDE_LOCK_ADAPTIVE . A thread-local ck_elide_stat structure must be passed to both Fn CK_ELIDE_LOCK_ADAPTIVE and Fn CK_ELIDE_UNLOCK_ADAPTIVE . This structure is expected to be unique for different workloads, may not be re-used in recursive acquisitions and must match the lifetime of the lock it is associated with. It is safe to mix adaptive calls with best-effort calls.

Both ck_spinlock.h and ck_rwlock.h define ck_elide wrappers under the ck_spinlock and ck_rwlock namespace, respectively.

EXAMPLES

This example utilizes built-in lock elision facilities in ck_rwlock and ck_spinlock.

#include <ck_rwlock.h>
#include <ck_spinlock.h>
static ck_rwlock_t rw = CK_RWLOCK_INITIALIZER;
static struct ck_elide_config rw_config =
    CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
static __thread ck_elide_stat_t rw_stat =
    CK_ELIDE_STAT_INITIALIZER;
static ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER;
static struct ck_elide_config spinlock_config =
    CK_ELIDE_CONFIG_DEFAULT_INITIALIZER;
static __thread ck_elide_stat_t spinlock_stat =
    CK_ELIDE_STAT_INITIALIZER;
void
function(void)
{
        /* Lock-unlock write-side lock in weak best-effort manner. */
        CK_ELIDE_LOCK(ck_rwlock_write, &rw);
        CK_ELIDE_UNLOCK(ck_rwlock_write, &rw);
        /* Attempt to acquire the write-side lock. */
        if (CK_ELIDE_TRYLOCK(ck_rwlock_write, &rw) == true)
                CK_ELIDE_UNLOCK(ck_rwlock_write, &rw);
        /* Lock-unlock read-side lock in weak best-effort manner. */
        CK_ELIDE_LOCK(ck_rwlock_read, &rw);
        CK_ELIDE_UNLOCK(ck_rwlock_read, &rw);
        /* Attempt to acquire the read-side lock. */
        if (CK_ELIDE_TRYLOCK(ck_rwlock_read, &rw) == true)
                CK_ELIDE_UNLOCK(ck_rwlock_read, &rw);
        /* Lock-unlock write-side lock in an adaptive manner. */
        CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_write, &rw_stat,
            &rw_config, &rw);
        CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_write, &rw_stat,
            &rw_config, &rw);
        /* Lock-unlock read-side lock in an adaptive manner. */
        CK_ELIDE_LOCK_ADAPTIVE(ck_rwlock_read, &rw_stat,
            &rw_config, &rw);
        CK_ELIDE_UNLOCK_ADAPTIVE(ck_rwlock_read, &rw_stat,
            &rw_config, &rw);
        /* Lock-unlock spinlock in weak best-effort manner. */
        CK_ELIDE_LOCK(ck_spinlock, &spinlock);
        CK_ELIDE_UNLOCK(ck_spinlock, &spinlock);
        /* Attempt to acquire the lock. */
        if (CK_ELIDE_TRYLOCK(ck_spinlock, &lock) == true)
                CK_ELIDE_UNLOCK(ck_spinlock, &spinlock);
        /* Lock-unlock spinlock in an adaptive manner. */
        CK_ELIDE_LOCK_ADAPTIVE(ck_spinlock, &spinlock_stat,
            &spinlock_config, &spinlock);
        CK_ELIDE_UNLOCK_ADAPTIVE(ck_spinlock, &spinlock_stat,
            &spinlock_config, &spinlock);
}

In this example, user-defined locking functions are provided an elision implementation.

/* Assume lock_t has been previously defined. */
#include <ck_elide.h>
/*
 * This function returns true if the lock is unavailable at the time
 * it was called or false if the lock is available.
 */
bool is_locked(lock_t *);
/*
 * This function acquires the supplied lock.
 */
void lock(lock_t *);
/*
 * This function releases the lock.
 */
void unlock(lock_t *);
CK_ELIDE_PROTOTYPE(my_lock, lock_t, is_locked, lock, is_locked, unlock)
static lock_t lock;
void
function(void)
{
        CK_ELIDE_LOCK(my_lock, &lock);
        CK_ELIDE_UNLOCK(my_lock, &lock);
}