diff options
Diffstat (limited to 'doc/ck_elide')
| -rw-r--r-- | doc/ck_elide | 252 |
1 files changed, 252 insertions, 0 deletions
diff --git a/doc/ck_elide b/doc/ck_elide new file mode 100644 index 0000000..c068567 --- /dev/null +++ b/doc/ck_elide @@ -0,0 +1,252 @@ +.\" +.\" Copyright 2013 Samy Al Bahra. +.\" All rights reserved. +.\" +.\" Redistribution and use in source and binary forms, with or without +.\" modification, are permitted provided that the following conditions +.\" are met: +.\" 1. Redistributions of source code must retain the above copyright +.\" notice, this list of conditions and the following disclaimer. +.\" 2. Redistributions in binary form must reproduce the above copyright +.\" notice, this list of conditions and the following disclaimer in the +.\" documentation and/or other materials provided with the distribution. +.\" +.\" THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND +.\" ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE +.\" IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE +.\" ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE +.\" FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL +.\" DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS +.\" OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) +.\" HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT +.\" LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY +.\" OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF +.\" SUCH DAMAGE. +.\" +.\" +.Dd July 13, 2013. +.Dt ck_elide 3 +.Sh NAME +.Nm CK_ELIDE_PROTOTYPE , +.Nm CK_ELIDE_LOCK_ADAPTIVE , +.Nm CK_ELIDE_UNLOCK_ADAPTIVE , +.Nm CK_ELIDE_LOCK , +.Nm CK_ELIDE_UNLOCK , +.Nm CK_ELIDE_TRYLOCK_PROTOTYPE , +.Nm CK_ELIDE_TRYLOCK +.Nd lock elision wrappers +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_elide.h +.Pp +.Dv ck_elide_stat_t stat = CK_ELIDE_STAT_INITIALIZER; +.Pp +.Ft void +.Fn ck_elide_stat_init "ck_elide_stat_t *" +.Pp +.Dv struct ck_elide_config config = CK_ELIDE_CONFIG_DEFAULT_INITIALIZER; +.Pp +.Bd -literal -offset +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; +}; +.Ed +.Pp +.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" +.Sh 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. +.Pp +.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 . +.Pp +.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 . +.Pp +.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. +.Pp +Both ck_spinlock.h and ck_rwlock.h define ck_elide wrappers under +the ck_spinlock and ck_rwlock namespace, respectively. +.Sh EXAMPLES +This example utilizes built-in lock elision facilities in ck_rwlock and ck_spinlock. +.Bd -literal -offset indent +#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); +} +.Ed +.Pp +In this example, user-defined locking functions are provided an elision +implementation. +.Bd -literal -offset indent +/* 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); +} +.Ed +.Sh SEE ALSO +.Xr ck_rwlock 3 , +.Xr ck_spinlock 3 +.Pp +Ravi Rajwar and James R. Goodman. 2001. Speculative lock elision: enabling highly concurrent multithreaded execution. In Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture (MICRO 34). IEEE Computer Society, Washington, DC, USA, 294-305. +.Pp +Additional information available at http://en.wikipedia.org/wiki/Transactional_Synchronization_Extensions and http://concurrencykit.org/ |