Home
Reading
Searching
Subscribe
Sponsors
Statistics
Posting
Contact
Spam
Lists
Links
About
Hosting
Filtering
Features Download
Marketing
Archives
FAQ
Blog
 
Gmane
From: Andi Kleen <andi <at> firstfloor.org>
Subject: [PATCH 10/10] Add manual for lock elision
Newsgroups: gmane.comp.lib.glibc.alpha
Date: Thursday 10th January 2013 20:19:42 UTC (over 5 years ago)
From: Andi Kleen 

pthreads are not described in the documentation, but I decided to document
lock elision there at least.

2013-01-09  Andi Kleen  

	* manual/Makefile: Add elision.texi.
	* manual/debug.texi: Link to elision.
	* manual/elision.texi: New file.
	* manual/intro.texi: Link to elision.
	* manual/lang.texi: dito.
---
 manual/Makefile     |    2 +-
 manual/debug.texi   |    2 +-
 manual/elision.texi |  316
+++++++++++++++++++++++++++++++++++++++++++++++++++
 manual/intro.texi   |    3 +
 manual/lang.texi    |    2 +-
 5 files changed, 322 insertions(+), 3 deletions(-)
 create mode 100644 manual/elision.texi

diff --git a/manual/Makefile b/manual/Makefile
index c1a304c..abcc744 100644
--- a/manual/Makefile
+++ b/manual/Makefile
@@ -42,7 +42,7 @@ chapters = $(addsuffix .texi, \
 		       message search pattern io stdio llio filesys	\
 		       pipe socket terminal syslog math arith time	\
 		       resource setjmp signal startup process job nss	\
-		       users sysinfo conf crypt debug)
+		       users sysinfo conf crypt debug elision)
 add-chapters = $(wildcard $(foreach d, $(add-ons), ../$d/$d.texi))
 appendices = lang.texi header.texi install.texi maint.texi platform.texi \
 	     contrib.texi
diff --git a/manual/debug.texi b/manual/debug.texi
index b2bcb31..722e660 100644
--- a/manual/debug.texi
+++ b/manual/debug.texi
@@ -1,5 +1,5 @@
 @node Debugging Support
[email protected] @node Debugging Support, , Cryptographic Functions, Top
[email protected] @node Debugging Support, Lock elision, Cryptographic Functions, Top
 @c %MENU% Functions to help debugging applications
 @chapter Debugging support
 
diff --git a/manual/elision.texi b/manual/elision.texi
new file mode 100644
index 0000000..7a19c2d
--- /dev/null
+++ b/manual/elision.texi
@@ -0,0 +1,316 @@
[email protected] Lock elision, Language Features, Debugging Support, Top
[email protected] %MENU% Lock elision
[email protected] Lock elision
+
[email protected] create the bizarre situation that lock elision is documented, but
pthreads isn't
+
+This chapter describes the lock implementation implementation for pthread
+locks.
+
[email protected]
+* Lock elision introduction::	What is lock elision?
+* Semantic differences of elided locks::
+* Tuning lock elision::
+* Setting elision for individual @code{pthread_mutex_t}::
+* Setting @code{pthread_mutex_t} elision using environment variables::
+* Setting elision for individual @code{pthread_rwlock_t}::
+* Setting @code{pthread_rwlock_t} elision using environment variables::
+* Abort hooks::
[email protected] menu 
+
[email protected] Lock elision introduction
[email protected] Lock elision introduction
+
+Lock elision is a technique to improve lock scaling. It runs
+lock regions in parallel using hardware support for a transactional
execution
+mode. The lock region is executed speculatively, and as long
+as there is no conflict or other reason for transaction abort the lock
+will executed in parallel. If an transaction abort occurs, any 
+side effect of the speculative execution is undone, the lock is taken
+for real and the lock region re-executed. This improves scalability
+of the program because locks do not need to wait for each other.
+
+The standard @code{pthread_mutex_t} mutexes and @code{pthread_rwlock_t}
rwlocks
+can be transparently elided by the C library.
+
+Lock elision may lower performance if transaction aborts occur too
frequently.
+In this case it is recommended to use a PMU profiler to find the causes
for
+the aborts first and try to eliminate them. If that is not possible
+elision can be disabled for a specific lock or for the whole program.
+Alternatively elision can be disabled completely, and only enabled for 
+specific locks that are known to be elision friendly.
+
+The defaults locks are adaptive. The lock library decides whether elision
+is profitable based on the abort rates, and automatically disables
+elision for a lock when it aborts too often. After some time elision
+is retried, in case the workload changed.
+
+Lock elision is currently supported for default (timed) mutexes and for
+adaptive mutexes. Other lock types do not elide. Condition variables
+also do not elide. This may change in future versions.
+
[email protected] Semantic differences of elided locks
[email protected] Semantic differences of elided locks
+
+Elided locks have some semantic differences to classic locks. These
differences 
+are only visible when the lock is successfully elided. Since elision may
always
+fail a program cannot rely on any of these semantics.
+
[email protected]
[email protected] 
+Elided locks always behave like read-write locks.
+
[email protected]
+Locks can be locked recursively inside the lock region. 
+This behavior is visible through @code{pthread_mutex_trylock}:
+
[email protected]
+pthread_mutex_lock (&lock);
+if (pthread_mutex_trylock (&lock) == 0) 
+      /* with elision we come here */
+else
+      /* with no elision we always come here */
[email protected] smallexample
+
+And also through @code{pthread_mutex_timedlock}:
+
[email protected]
+pthread_mutex_lock (&lock);
+if (pthread_mutex_timedlock (&lock, &timeout) == 0) 
+     /* With elision we always come here */
+else
+     /* With no elision we always come here because timeout happens. */
[email protected] smallexample
+
+Similar semantic changes apply to @code{pthread_rwlock_trywrlock} and
[email protected]{pthread_rwlock_timedwrlock}.
+
[email protected]
[email protected]{pthread_mutex_destroy} does not return an error when the lock is
locked
+and will clear the lock state.
+
[email protected]
[email protected]{pthread_mutex_t} and @code{pthread_rwlock_t} appear free from other
threads.
+
+This can be visible through trylock or timedlock.
+In most cases checking this is a existing latent race in the program, but
there may 
+be rare cases when it is not.
+
[email protected]
[email protected]{EAGAIN} and @code{EDEADLK} in rwlocks will not happen under elision.
+
[email protected]
[email protected]{pthread_mutex_unlock} does not return an error when unlocking a free
lock.
+
[email protected]
+Elision changes timing because locks now run in parallel.
+Timing differences may expose latent race bugs in the program. Programs
using time based synchronization (as opposed to using data dependencies)
may change behaviour.
+
[email protected] itemize
+
[email protected] Tuning lock elision
[email protected] Tuning lock elision
+
+Critical regions may need some tuning to get the benefit of lock elision.
+This is based on the abort rates, which can be determined by a PMU
profiler
+(e.g. perf on GNU/Linux systems). When the abort rate is too high lock
+scaling will not improve. Generally lock elision feedback should be done
+only based on profile feedback.
+
+Most of these optimizations will improve performance even without lock
elision
+because they will minimize cache line bouncing between threads or make
+lock regions smaller.
+
+Common causes of transactional aborts:
+
[email protected]
[email protected] 
+Not elidable operations like system calls, IO, CPU exceptions.
+
+Try to move out of the critical section when common. Note that these often
happen at program startup only.
[email protected]
+Global statistic counts
+
+Global statistic variables tend to cause conflicts. Either disable, or
make per thread or as a last resort sample
+(not update every operation)
[email protected]
+False sharing of variables or data structures causing conflicts with other
threads
+
+Add padding as needed.
[email protected] 
+Other conflicts on the same cache lines with other threads
+
+Minimize conflicts with other threads. This may require changes to the
data structures.
[email protected]
+Capacity overflow
+
+The memory transaction used for lock elision has a limited capacity. Make
the critical region smaller
+or move operations that do not need to be protected by the lock outside.
+
[email protected]
+Rewriting already set flags
+
+Setting flags or variables in shared objects that are already set may
cause conflicts. Add a check
+to only write when the value changed.
[email protected] itemize
+
[email protected] Setting elision for individual @code{pthread_mutex_t}
[email protected] Setting elision for individual @code{pthread_mutex_t}
+
+Elision can be explicitly disabled or enabled for each
@code{pthread_mutex_t} in the program. 
+This overrides any other defaults set by environment variables for this
lock.
+
[email protected]{pthrex_mutex_t} Initializers for using in variable initializations.
+
[email protected]
[email protected]
+PTHREAD_TIMED_NO_ELISION_MUTEX_INITIALIZER_NP
+Force lock elision for a (default) timed mutex.
+
[email protected]
+PTHREAD_TIMED_NO_ELISION_MUTEX_INITIALIZER_NP
+Force no lock elision for a (default) timed mutex.
+
[email protected]
+PTHREAD_ADAPTIVE_ELISION_MUTEX_INITIALIZER_NP
+Force lock elision for an adaptive mutex.
+
[email protected]
+PTHREAD_ADAPTIVE_NO_ELISION_MUTEX_INITIALIZER_NP
+Force no lock elision for an adaptive mutex.
[email protected] itemize
+
[email protected]
+/* Disable lock elision for mylock */
+pthread_mutex_t mylock = PTHREAD_TIMED_NO_ELISION_MUTEX_INITIALIZER_NP;
[email protected] smallexample
+
+The lock type can also be set at runtime using
@code{pthread_mutexattr_settype} and @code{pthread_mutex_init}.
+
[email protected]
+/* Force lock elision for a dynamically allocated mutex */
+pthread_mutexattr_t attr;
+pthread_mutexattr_init (&attr);
+pthread_mutexattr_settype (&attr, PTHREAD_MUTEX_TIMED_ELISION_NP);
+pthread_mutex_init (&object->mylock, &attr);
[email protected] smallexample
+
+
[email protected] Setting @code{pthread_mutex_t} elision using environment variables
[email protected] Setting @code{pthread_mutex_t} elision using environment
variables
+The elision of @code{pthread_mutex_t} mutexes can be configured at runtime
with the @code{PTHREAD_MUTEX}
+environment variable.  This will force a specific lock type for all
+mutexes in the program that do not have another type set explicitly.
+An explicitly set lock type will override the environment variable.
+
[email protected]
+# run myprogram with no elision
+PTHREAD_MUTEX=none myprogram
[email protected] smallexample
+
+The default depends on the C library build configuration and whether the
hardware
+supports lock elision.
+
[email protected]
[email protected]    
[email protected]{PTHREAD_MUTEX=elision}
+Use elided mutexes, unless explicitely disabled in the program.
+    
[email protected]
[email protected]{PTHREAD_MUTEX=none}
+Don't use elide mutexes, unless explicitly enable in the program.
[email protected] itemize
+
+In addition additional tunables can be configured through the environment
variable,
+like this:
[email protected]{PTHREAD_MUTEX=adaptive:retry_lock_busy=10,retry_lock_internal_abort=20}

+Note these parameters do not consistitute an ABI and may change or
disappear 
+at any time as the lock elision algorithm evolves. 
+
+Currently supported parameters are:
+    
[email protected]
[email protected]
+retry_lock_busy
+How often to not attempt a transaction when the lock is seen as busy.
+    
[email protected]
+retry_lock_internal_abort
+How often to not attempt a transaction after an internal abort is seen.
+
[email protected]    
+retry_try_xbegin
+How often to retry the transaction on external aborts.
[email protected] itemize
+
[email protected] Setting elision for individual @code{pthread_rwlock_t}
[email protected] Setting elision for individual @code{pthread_rwlock_t}
+
+Elision can be explicitly disabled or enabled for each
@code{pthread_rwlock_t} in the program. 
+This overrides any other defaults set by environment variables for this
lock.
+
+Valid flags are @code{PTHREAD_RWLOCK_ELISION_NP} to force elision and
@code{PTHREAD_RWLOCK_NO_ELISION_NP}
+to disable elision. These can be ored with other rwlock types.
+
[email protected]
+/* Force no lock elision for a dynamically allocated rwlock */
+pthread_rwlockattr_t rwattr;
+pthread_rwlockattr_init (&rwattr);
+pthread_rwlockattr_settype (&rwattr, PTHREAD_RWLOCK_NO_ELISION_NP);
+pthread_rwlock_init (&object->myrwlock, &rwattr);
[email protected] smallexample
+
[email protected] Setting @code{pthread_rwlock_t} elision using environment variables
[email protected] Setting @code{pthread_rwlock_t} elision using environment
variables
+The elision of @code{pthread_rwlock_t} rwlockes can be configured at
+runtime with the @code{PTHREAD_RWLOCK} environment variable.
+This will force a specific lock type for all
+rwlockes in the program that do not have another type set explicitly.
+An explicitly set lock type will override the environment variable.
+
[email protected]
+# run myprogram with no elision
+PTHREAD_RWLOCK=none myprogram
[email protected] smallexample
+
+The default depends on the C library build configuration and whether the
hardware
+supports lock elision.
+
[email protected]
[email protected]    
[email protected]{PTHREAD_RWLOCK=elision}
+Use elided rwlockes, unless explicitely disabled in the program.
+    
[email protected]
[email protected]{PTHREAD_RWLOCK=none}
+Don't use elided rwlocks, unless explicitely enabled in the program.
[email protected] itemize
+
[email protected] Abort hooks
[email protected] Abort hooks
[email protected] abort hooks for lock elision
[email protected] pthread.h
[email protected] GNU
[email protected] {__pthread_abort_hook_t} __pthread_set_abort_hook
(__pthread_abort_hook_t @var{hook}) 
+
+For some debugging situations it can be useful to call custom code on all
transaction aborts.
+The C Library allows to set a hook that is called from all of its
transaction abort handlers.
+
+The hook can be set with the @code{__pthread_set_abort_hook} function. It
consists of a callback
[email protected]{hook} that gets the CPU specific abort code as first argument.
@code{__pthread_set_abort_hook} returns
+the previous hook. Passing NULL for @var{hook} removes the hook.
+
+With TSX this hook can be used to pass up to one byte of information out
of a transaction using
+the _xabort() intrinsic (there is no other way to do this).
+
[email protected] xxx how do i do { } in the examples?
[email protected]
+void my_abort_hook (unsigned code);
+...
+
+__pthread_set_abort_hook (my_abort_hook);
[email protected] smallexample
+
[email protected]{__pthread_set_abort_hook} is a GNU extension.
[email protected] deftypefun
+
diff --git a/manual/intro.texi b/manual/intro.texi
index deaf089..3af44c6 100644
--- a/manual/intro.texi
+++ b/manual/intro.texi
@@ -703,6 +703,9 @@ information about the hardware and software
configuration your program
 is executing under.
 
 @item
[email protected]{Lock elision} describes elided locks in pthreads.
+
[email protected]
 @ref{System Configuration}, tells you how you can get information about
 various operating system limits.  Most of these parameters are provided
for
 compatibility with POSIX.
diff --git a/manual/lang.texi b/manual/lang.texi
index ee04e23..72e06b0 100644
--- a/manual/lang.texi
+++ b/manual/lang.texi
@@ -1,6 +1,6 @@
 @c This node must have no pointers.
 @node Language Features
[email protected] @node Language Features, Library Summary, , Top
[email protected] @node Language Features, Library Summary, Lock elision, Top
 @c %MENU% C language features provided by the library
 @appendix C Language Facilities in the Library
 
-- 
1.7.7.6
 
CD: 4ms