Re: [PATCH 08/14] Add manual for lock elision

["Carlos O'Donell" <carlos at redhat dot com>]

On 06/28/2013 01:51 AM, Andi Kleen wrote:
> From: Andi Kleen <ak@linux.intel.com>
> 
> pthreads are not described in the documentation, but I decided to document
> lock elision there at least.

Can we please split this into two manual patches?

The first will not have the discussion of the new API interfaces for
setting elision. Move those patches into the same patch for adding the
interface.

In the introduction you will have to say that the only way to enable
or disable elision is by rebuilding the library with it turned on or
off, or by using settype to disable it for DEFAULT locks (recursive
can't be disabled like that).

Otherwise only a few minor nits.
 
> 2013-06-18  Andi Kleen  <ak@linux.intel.com>
> 
> 	* manual/Makefile: Add elision.texi.
> 	* manual/threads.texi: Link to elision.
> 	* manual/elision.texi: New file.
> 	* manual/intro.texi: Link to elision.
> 	* manual/lang.texi: dito.
> ---
>  manual/Makefile     |   2 +-
>  manual/elision.texi | 208 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  manual/intro.texi   |   3 +
>  manual/lang.texi    |   2 +-
>  manual/threads.texi |   2 +-
>  5 files changed, 214 insertions(+), 3 deletions(-)
>  create mode 100644 manual/elision.texi
> 
> diff --git a/manual/Makefile b/manual/Makefile
> index 44c0fd4..5d78761 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 threads)
> +		       users sysinfo conf crypt debug threads 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/elision.texi b/manual/elision.texi
> new file mode 100644
> index 0000000..395819b
> --- /dev/null
> +++ b/manual/elision.texi
> @@ -0,0 +1,208 @@
> +@node Lock elision, Language Features, POSIX Threads, Top
> +@c %MENU% Lock elision
> +@chapter Lock elision
> +
> +@c create the bizarre situation that lock elision is documented, but pthreads isn't
> +
> +This chapter describes the elided lock implementation for POSIX thread locks.
> +
> +@menu
> +* Lock elision introduction::	What is lock elision?
> +* Semantic differences of elided locks::
> +* Tuning lock elision::
> +* Setting elision for individual @code{pthread_mutex_t}::
> +* Setting elision for individual @code{pthread_rwlock_t}::
> +@end menu 
> +
> +@node Lock elision introduction
> +@section 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 @theglibc{}.
> +
> +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 completly, and only enabled for 

s/completly/completely/g

> +specific locks that are known to be elision friendly.
> +
> +The defaults locks are adaptive. The lock library decides whether elision

s/lock library/library/g

> +is profitable based on the abort rates, and automatically disables
> +elision for a lock when it aborts too often. After some time elision
> +is re-tried, in case the workload changed.
> +
> +Lock elision is currently supported for default (timed) mutexes, and
> +rwlocks.  Other lock types (including @code{PTHREAD_MUTEX_NORMAL}) do not elide.
> +Condition variables also do not elide. This may change in future versions.
> +
> +@node Semantic differences of elided locks
> +@section Semantic differences of elided locks
> +
> +Elided locks have some semantic (visible) 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.
> +
> +@itemize
> +@item
> +timedlocks may not time out.
> +
> +@smallexample
> +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. */
> +@end smallexample
> +
> +Similar semantic changes apply to @code{pthread_rwlock_trywrlock} and
> +@code{pthread_rwlock_timedwrlock}.
> +
> +A program like
> +
> +@smallexample
> +/* lock is not a recursive lock type */
> +pthread_mutex_lock (&lock);
> +/* Relock same lock in same thread */
> +pthread_mutex_lock (&lock);
> +@end smallexample
> +
> +will immediately hang on the second lock (dead lock) without elision. With
> +elision the deadlock will only happen on an abort, which can happen
> +early or could happen later, but will likely not happen every time.
> +
> +This behaviour is allowed in POSIX for @code{PTHREAD_MUTEX_DEFAULT}, but not for
> +@code{PTHREAD_MUTEX_NORMAL}. When @code{PTHREAD_MUTEX_NORMAL} is
> +set for a mutex using @code{pthread_mutexattr_settype} elision is implicitely

s/implicitely/implicitly/g

> +disabled.  Note that @code{PTHREAD_MUTEX_INITIALIZER} sets a
> +@code{PTHREAD_MUTEX_DEFAULT} type, thus allows elision.
> +
> +Depending on the ABI version @theglibc{} may not distinguish between
> +@code{PTHREAD_MUTEX_NORMAL} and @code{PTHREAD_MUTEX_DEFAULT}, as they may
> +have the same numerical value. If that is the case any call to
> +@code{pthread_mutexattr_settype} with either type will disable elision.
> +
> +@item
> +@code{pthread_mutex_destroy} does not return an error when the lock is locked
> +and will clear the lock state.
> +
> +@item
> +@code{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 cases when it is not.
> +
> +@item
> +@code{EAGAIN} and @code{EDEADLK} in rwlocks will not happen under elision.
> +
> +@item
> +@code{pthread_mutex_unlock} does not return an error when unlocking a free lock.
> +
> +@item
> +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 behavior.
> +
> +@end itemize
> +
> +@node Tuning lock elision
> +@section 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 @gnulinuxsystems{}). 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:
> +
> +@itemize
> +@item 
> +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.
> +@item
> +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)
> +@item
> +False sharing of variables or data structures causing conflicts with other threads
> +
> +Add padding as needed.
> +@item 
> +Other conflicts on the same cache lines with other threads
> +
> +Minimize conflicts with other threads. This may require changes to the data structures.
> +@item
> +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.
> +
> +@item
> +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.
> +
> +@item
> +Using @code{pthread_mutex_trylock} or @code{pthread_rwlock_trywrlock}
> +nested in another elided lock.
> +
> +@end itemize
> +
> +@node Setting elision for individual @code{pthread_mutex_t}
> +@section Setting elision for individual @code{pthread_mutex_t}
> +
> +Elision can be explicitly disabled or enabled for each @code{pthread_mutex_t} in the program. 
> +The elision flags can only be set at runtime using @code{pthread_mutexattr_setelision_np} and
> +@code{pthread_mutex_init}. There is no support for initializers for them.
> +
> +@smallexample
> +/* Force lock elision for a mutex */
> +pthread_mutexattr_t attr;
> +pthread_mutexattr_init (&attr);
> +pthread_mutexattr_setelision_np (&attr, 1);
> +pthread_mutex_init (&object->mylock, &attr);
> +@end smallexample
> +
> +@smallexample
> +/* Force no lock elision for a mutex */
> +pthread_mutexattr_t attr;
> +pthread_mutexattr_init (&attr);
> +pthread_mutexattr_setelision_np (&attr, 0);
> +pthread_mutex_init (&object->mylock, &attr);
> +@end smallexample
> +
> +Setting a @code{PTHREAD_MUTEX_NORMAL} lock type will also disable elision.
> +In some versions of the library any call to @code{pthread_mutexattr_settype} 
> +may also disable elision for that lock.
> +
> +@node Setting elision for individual @code{pthread_rwlock_t}
> +@section Setting elision for individual @code{pthread_rwlock_t}
> +
> +Elision can be explicitly disabled or enabled for each @code{pthread_rwlock_t} in the program using @code{pthread_rwlockattr_setelision_np}.
> +
> +@smallexample
> +/* Force lock elision for a dynamically allocated rwlock */
> +pthread_rwlockattr_t rwattr;
> +pthread_rwlockattr_init (&rwattr);
> +pthread_rwlockattr_setelision_np (&rwattr, 1);
> +pthread_rwlock_init (&object->myrwlock, &rwattr);
> +@end smallexample
> +
> diff --git a/manual/intro.texi b/manual/intro.texi

OK.

> index deaf089..5914035 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
> +@ref{Lock elision} describes elided locks in POSIX threads.
> +
> +@item
>  @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.

OK.

> 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
> -@c @node Language Features, Library Summary, , Top
> +@c @node Language Features, Library Summary, Lock elision, Top
>  @c %MENU% C language features provided by the library
>  @appendix C Language Facilities in the Library
>  
> diff --git a/manual/threads.texi b/manual/threads.texi

OK.

> index a23ac26..f58ea6e 100644
> --- a/manual/threads.texi
> +++ b/manual/threads.texi
> @@ -1,5 +1,5 @@
>  @node POSIX Threads
> -@c @node POSIX Threads, , Cryptographic Functions, Top
> +@c @node POSIX Threads, Lock elision, Cryptographic Functions, Top
>  @chapter POSIX Threads
>  @c %MENU% POSIX Threads
>  @cindex pthreads
> 

Cheers,
Carlos.