Adding upstream version 0.6.0.upstream/0.6.0

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

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/