diff options
Diffstat (limited to 'doc/ck_spinlock')
| -rw-r--r-- | doc/ck_spinlock | 259 |
1 files changed, 259 insertions, 0 deletions
diff --git a/doc/ck_spinlock b/doc/ck_spinlock new file mode 100644 index 0000000..564d185 --- /dev/null +++ b/doc/ck_spinlock @@ -0,0 +1,259 @@ +.\" +.\" 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 26, 2013. +.Dt ck_spinlock 3 +.Sh NAME +.Nm ck_spinlock_init , +.Nm ck_spinlock_lock , +.Nm ck_spinlock_unlock , +.Nm ck_spinlock_locked , +.Nm ck_spinlock_trylock , +.Nm ck_spinlock_anderson_init , +.Nm ck_spinlock_anderson_locked , +.Nm ck_spinlock_anderson_lock , +.Nm ck_spinlock_anderson_unlock , +.Nm ck_spinlock_cas_init , +.Nm ck_spinlock_cas_locked , +.Nm ck_spinlock_cas_lock , +.Nm ck_spinlock_cas_lock_eb , +.Nm ck_spinlock_cas_trylock , +.Nm ck_spinlock_cas_unlock , +.Nm ck_spinlock_clh_init , +.Nm ck_spinlock_clh_locked , +.Nm ck_spinlock_clh_lock , +.Nm ck_spinlock_clh_unlock , +.Nm ck_spinlock_dec_init , +.Nm ck_spinlock_dec_locked , +.Nm ck_spinlock_dec_lock , +.Nm ck_spinlock_dec_lock_eb , +.Nm ck_spinlock_dec_trylock , +.Nm ck_spinlock_dec_unlock , +.Nm ck_spinlock_fas_init , +.Nm ck_spinlock_fas_lock , +.Nm ck_spinlock_fas_lock_eb , +.Nm ck_spinlock_fas_locked , +.Nm ck_spinlock_fas_trylock , +.Nm ck_spinlock_fas_unlock , +.Nm ck_spinlock_hclh_init , +.Nm ck_spinlock_hclh_locked , +.Nm ck_spinlock_hclh_lock , +.Nm ck_spinlock_hclh_unlock , +.Nm ck_spinlock_mcs_init , +.Nm ck_spinlock_mcs_locked , +.Nm ck_spinlock_mcs_lock , +.Nm ck_spinlock_mcs_trylock , +.Nm ck_spinlock_mcs_unlock , +.Nm ck_spinlock_ticket_init , +.Nm ck_spinlock_ticket_locked , +.Nm ck_spinlock_ticket_lock , +.Nm ck_spinlock_ticket_lock_pb , +.Nm ck_spinlock_ticket_trylock , +.Nm ck_spinlock_ticket_unlock +.Nd spinlock implementations +.Sh LIBRARY +Concurrency Kit (libck, \-lck) +.Sh SYNOPSIS +.In ck_spinlock.h +.Pp +.Dv ck_spinlock_t spinlock = CK_SPINLOCK_INITIALIZER; +.Ft void +.Fn ck_spinlock_init "ck_spinlock_t *lock" +.Ft void +.Fn ck_spinlock_lock "ck_spinlock_t *lock" +.Ft void +.Fn ck_spinlock_unlock "ck_spinlock_t *lock" +.Ft bool +.Fn ck_spinlock_locked "ck_spinlock_t *lock" +.Ft bool +.Fn ck_spinlock_trylock "ck_spinlock_t *lock" +.Ft void +.Fn ck_spinlock_anderson_init "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slots" "unsigned int count" +.Ft bool +.Fn ck_spinlock_anderson_locked "ck_spinlock_anderson_t *lock" +.Ft void +.Fn ck_spinlock_anderson_lock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t **slot" +.Ft void +.Fn ck_spinlock_anderson_unlock "ck_spinlock_anderson_t *lock" "ck_spinlock_anderson_thread_t *slot" +.Pp +.Dv ck_spinlock_cas_t spinlock = CK_SPINLOCK_CAS_INITIALIZER; +.Ft void +.Fn ck_spinlock_cas_init "ck_spinlock_cas_t *lock" +.Ft bool +.Fn ck_spinlock_cas_locked "ck_spinlock_cas_t *lock" +.Ft void +.Fn ck_spinlock_cas_lock "ck_spinlock_cas_t *lock" +.Ft void +.Fn ck_spinlock_cas_lock_eb "ck_spinlock_cas_t *lock" +.Ft bool +.Fn ck_spinlock_cas_trylock "ck_spinlock_cas_t *lock" +.Ft void +.Fn ck_spinlock_cas_unlock "ck_spinlock_cas_t *lock" +.Ft void +.Fn ck_spinlock_clh_init "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *unowned" +.Ft bool +.Fn ck_spinlock_clh_locked "ck_spinlock_clh_t **lock" +.Ft void +.Fn ck_spinlock_clh_lock "ck_spinlock_clh_t **lock" "ck_spinlock_clh_t *node" +.Ft void +.Fn ck_spinlock_clh_unlock "ck_spinlock_clh_t **node" +.Pp +.Dv ck_spinlock_dec_t spinlock = CK_SPINLOCK_DEC_INITIALIZER; +.Ft void +.Fn ck_spinlock_dec_init "ck_spinlock_dec_t *lock" +.Ft bool +.Fn ck_spinlock_dec_locked "ck_spinlock_dec_t *lock" +.Ft void +.Fn ck_spinlock_dec_lock "ck_spinlock_dec_t *lock" +.Ft void +.Fn ck_spinlock_dec_lock_eb "ck_spinlock_dec_t *lock" +.Ft bool +.Fn ck_spinlock_dec_trylock "ck_spinlock_dec_t *lock" +.Ft void +.Fn ck_spinlock_dec_unlock "ck_spinlock_dec_t *lock" +.Pp +.Dv ck_spinlock_fas_t spinlock = CK_SPINLOCK_FAS_INITIALIZER; +.Ft void +.Fn ck_spinlock_fas_init "ck_spinlock_fas_t *lock" +.Ft void +.Fn ck_spinlock_fas_lock "ck_spinlock_fas_t *lock" +.Ft void +.Fn ck_spinlock_fas_lock_eb "ck_spinlock_fas_t *lock" +.Ft bool +.Fn ck_spinlock_fas_locked "ck_spinlock_fas_t *lock" +.Ft bool +.Fn ck_spinlock_fas_trylock "ck_spinlock_fas_t *lock" +.Ft void +.Fn ck_spinlock_fas_unlock "ck_spinlock_fas_t *lock" +.Pp +.Ft void +.Fn ck_spinlock_hclh_init "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *unowned" +.Ft bool +.Fn ck_spinlock_hclh_locked "ck_spinlock_hclh_t **lock" +.Ft void +.Fn ck_spinlock_hclh_lock "ck_spinlock_hclh_t **lock" "ck_spinlock_hclh_t *node" +.Ft void +.Fn ck_spinlock_hclh_unlock "ck_spinlock_hclh_t **node" +.Pp +.Dv ck_spinlock_mcs_t spinlock = CK_SPINLOCK_MCS_INITIALIZER; +.Ft void +.Fn ck_spinlock_mcs_init "ck_spinlock_mcs_t **lock" +.Ft bool +.Fn ck_spinlock_mcs_locked "ck_spinlock_mcs_t **lock" +.Ft void +.Fn ck_spinlock_mcs_lock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node" +.Ft bool +.Fn ck_spinlock_mcs_trylock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node" +.Ft void +.Fn ck_spinlock_mcs_unlock "ck_spinlock_mcs_t **lock" "ck_spinlock_mcs_t *node" +.Pp +.Dv ck_spinlock_ticket_t spinlock = CK_SPINLOCK_TICKET_INITIALIZER; +.Ft void +.Fn ck_spinlock_ticket_init "ck_spinlock_ticket_t *lock" +.Ft bool +.Fn ck_spinlock_ticket_locked "ck_spinlock_ticket_t *lock" +.Ft void +.Fn ck_spinlock_ticket_lock "ck_spinlock_ticket_t *lock" +.Ft void +.Fn ck_spinlock_ticket_lock_pb "ck_spinlock_ticket_t *lock" "unsigned int period" +.Ft bool +.Fn ck_spinlock_ticket_trylock "ck_spinlock_ticket_t *lock" +.Ft void +.Fn ck_spinlock_ticket_unlock "ck_spinlock_ticket_t *lock" +.Sh DESCRIPTION +A family of busy-wait spinlock implementations. The ck_spinlock_t implementation is simply +a wrapper around the fetch-and-swap (ck_spinlock_fas_t) implementation. The table below +provides a summary of the current implementations. +.Bd -literal +| Namespace | Algorithm | Type | Restrictions | Fair | +\'----------------------|-----------------------------|---------------|-------------------------|--------' + ck_spinlock_anderson Anderson Array Fixed number of threads Yes + ck_spinlock_cas Compare-and-Swap Centralized None No + ck_spinlock_clh Craig, Landin and Hagersten Queue Lifetime requirements Yes + ck_spinlock_dec Decrement (Linux kernel) Centralized UINT_MAX concurrency No + ck_spinlock_fas Fetch-and-store Centralized None No + ck_spinlock_hclh Hierarchical CLH Queue Lifetime requirements Yes * + ck_spinlock_mcs Mellor-Crummey and Scott Queue None Yes + ck_spinlock_ticket Ticket Centralized None Yes +.Ed +.Pp +* Hierarchical CLH only offers weak fairness for threads accross cluster +nodes. +.Pp +If contention is low and there is no hard requirement for starvation-freedom +then a centralized greedy (unfair) spinlock is recommended. If contention is +high and there is no requirement for starvation-freedom then a centralized +greedy spinlock is recommended to be used with an exponential backoff +mechanism. If contention is generally low and there is a hard requirement for +starvation-freedom then the ticket lock is recommended. If contention is high +and there is a hard requirement for starvation-freedom then the Craig and +Landin and Hagersten queue spinlock is recommended unless stack allocation is +necessary or NUMA factor is high, in which case the Mellor-Crummey and Scott +spinlock is recommended. If you cannot afford O(n) space-usage from array +or queue spinlocks but still require fairness under high contention then +the ticket lock with proportional back-off is recommended. +If NUMA factor is high but prefer a greedy lock, then please see +.Xr ck_cohort 3 . +.Sh EXAMPLE +.Bd -literal -offset indent +#include <ck_spinlock.h> +#include <stdbool.h> + +/* + * Alternatively, the mutex may be initialized at run-time with + * ck_spinlock_init(&mutex). + */ +ck_spinlock_t mutex = CK_SPINLOCK_INITIALIZER; + +void +example(void) +{ + + ck_spinlock_lock(&mutex); + /* + * Critical section. + */ + ck_spinlock_unlock(&mutex); + + ck_spinlock_lock_eb(&mutex); + /* + * Critical section. + */ + ck_spinlock_unlock(&mutex); + + if (ck_spinlock_trylock(&mutex) == true) { + /* + * Critical section. + */ + ck_spinlock_unlock(&mutex); + } +} +.Ed +.Sh SEE ALSO +.Xr ck_cohort 3 , +.Xr ck_elide 3 +.Pp +Additional information available at http://concurrencykit.org/ |