Add the low level infrastructure for pthreads lock elision with TSX

Lock elision using TSX is a technique to optimize lock scaling
It allows to run locks in parallel using hardware support for
a transactional execution mode in 4th generation Intel Core CPUs.
See http://www.intel.com/software/tsx for more Information.

This patch implements a simple adaptive lock elision algorithm based
on RTM. It enables elision for the pthread mutexes and rwlocks.
The algorithm keeps track whether a mutex successfully elides or not,
and stops eliding for some time when it is not.

When the CPU supports RTM the elision path is automatically tried,
otherwise any elision is disabled.

The adaptation algorithm and its tuning is currently preliminary.

The code adds some checks to the lock fast paths. Micro-benchmarks
show little to no difference without RTM.

This patch implements the low level "lll_" code for lock elision.
Followon patches hook this into the pthread implementation

Changes with the RTM mutexes:
-----------------------------
Lock elision in pthreads is generally compatible with existing programs.
There are some obscure exceptions, which are expected to be uncommon.
See the manual for more details.

- A broken program that unlocks a free lock will crash.
  There are ways around this with some tradeoffs (more code in hot paths)
  I'm still undecided on what approach to take here; have to wait for testing reports.
- pthread_mutex_destroy of a lock mutex will not return EBUSY but 0.
- There's also a similar situation with trylock outside the mutex,
  "knowing" that the mutex must be held due to some other condition.
  In this case an assert failure cannot be recovered. This situation is
  usually an existing bug in the program.
- Same applies to the rwlocks. Some of the return values changes
  (for example there is no EDEADLK for an elided lock, unless it aborts.
   However when elided it will also never deadlock of course)
- Timing changes, so broken programs that make assumptions about specific timing
  may expose already existing latent problems.  Note that these broken programs will
  break in other situations too (loaded system, new faster hardware, compiler
  optimizations etc.)
- Programs with non recursive mutexes that take them recursively in a thread and
  which would always deadlock without elision may not always see a deadlock.
  The deadlock will only happen on an early or delayed abort (which typically
  happens at some point)
  This only happens for mutexes not explicitely set to PTHREAD_MUTEX_NORMAL
  or PTHREAD_MUTEX_ADAPTIVE_NP.  PTHREAD_MUTEX_NORMAL mutexes do not elide.

The elision default can be set at configure time.

This patch implements the basic infrastructure for elision.

2013-06-27  Andi Kleen  <ak@linux.intel.com>
            Hongjiu Lu  <hongjiu.lu@intel.com>

	* sysdeps/unix/sysv/linux/i386/lowlevellock.h (__lll_timedwait_tid,
          lll_timedlock_elision, __lll_lock_elision, __lll_unlock_elision,
          __lll_trylock_elision, lll_lock_elision, lll_unlock_elision,
	  lll_trylock_elision): Add.
	* sysdeps/unix/sysv/linux/x86/Makefile: Imply x86
	* sysdeps/unix/sysv/linux/x86/elision-conf.c: New file.
	* sysdeps/unix/sysv/linux/x86/elision-conf.h: New file.
	* sysdeps/unix/sysv/linux/x86/elision-lock.c: New file.
	* sysdeps/unix/sysv/linux/x86/elision-timed.c: New file.
	* sysdeps/unix/sysv/linux/x86/elision-trylock.c: New file.
	* sysdeps/unix/sysv/linux/x86/elision-unlock.c: New file
	* sysdeps/unix/sysv/linux/x86_64/lowlevellock.h (__lll_timedwait_tid,
          lll_timedlock_elision, __lll_lock_elision, __lll_unlock_elision,
          __lll_trylock_elision, lll_lock_elision, lll_unlock_elision,
	  lll_trylock_elision): Add.
	* nptl/sysdeps/unix/sysv/linux/x86/hle.h: New file.
	* elision-conf.h: New file.
Add new internal mutex type flags for elision.

Add Enable/disable flags used internally

Extend the mutex initializers to have the fields needed for
elision. The layout stays the same, and this is not visible
to programs.

These changes are not exposed outside pthread

2013-06-18  Andi Kleen  <ak@linux.intel.com>

	* pthreadP.h: Add elision types.
          (PTHREAD_MUTEX_TYPE_ELISION): Add.
	* sysdeps/pthread/pthread.h: Add elision initializers.
	  (PTHREAD_MUTEX_ELISION_NP, PTHREAD_MUTEX_NO_ELISION_NP,
	   PTHREAD_MUTEX_PSHARED_NP): Add new flags.
          (__PTHREAD_SPINS): Add.
Add minimal test suite changes for elision enabled kernels

tst-mutex5 and 8 test some behaviour not required by POSIX,
that elision changes. This changes these tests to not check
this when elision is enabled at configure time.

2013-06-28  Andi Kleen  <ak@linux.intel.com>

	* tst-mutex5.c: Include config.h.
	  (do_test): Add checks for ENABLE_LOCK_ELISION.
	* tst-mutex8.c: Include config.h
	  (tf): Add checks for ENABLE_LOCK_ELISION.
	  (check_type): Likewise.
Add elision to pthread_mutex_{try,timed,un}lock

Add elision paths to the basic mutex locks.

The normal path has a check for RTM and upgrades the lock
to RTM when available. Trylocks cannot automatically upgrade,
so they check for elision every time.

We use a 4 byte value in the mutex to store the lock
elision adaptation state. This is separate from the adaptive
spin state and uses a separate field.

Condition variables currently do not support elision.

Recursive mutexes and condition variables may be supported at some point,
but are not in the current implementation. Also "trylock" will
not automatically enable elision unless some other lock call
has been already called on the lock.

This version does not use IFUNC, so it means every lock has one
additional check for elision. Benchmarking showed the overhead
to be negligible.

2013-06-27  Andi Kleen  <ak@linux.intel.com>
            Hongjiu Lu  <hongjiu.lu@intel.com>

	* pthread_mutex_lock.c
	(__pthread_mutex_lock): Add lock elision support.
	* pthread_mutex_timedlock.c (pthread_mutex_timedlock): Likewise.
	* pthread_mutex_trylock.c (__pthread_mutex_trylock): Likewise.
	* pthread_mutex_unlock.c (__pthread_mutex_unlock_usercnt): Likewise.
	* sysdeps/unix/sysv/linux/pthread_mutex_cond_lock.c: Likewise.
	* sysdeps/unix/sysv/linux/x86/bits/pthreadtypes.h: Likewise.
	* sysdeps/unix/sysv/linux/x86/Makefile: New file.
	* sysdeps/unix/sysv/linux/x86/force-elision.h: New file
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_cond_lock.c: Likewise.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_lock.c: Likewise.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_timedlock.c: Likewise.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_trylock.c: Likewise.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_unlock.c: Likewise.
Disable elision for any pthread_mutexattr_settype call

PTHREAD_MUTEX_NORMAL requires deadlock for nesting, DEFAULT
does not. Since glibc uses the same value (0) disable elision
for any call to pthread_mutexattr_settype() with a 0 value.
This implies that a program can disable elision by doing
pthread_mutexattr_settype(&attr, PTHREAD_MUTEX_NORMAL)

Based on a original proposal by Rich Felker.

nptl/:
2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* pthread_mutexattr_settype.c (__pthread_mutexattr_settype):
	Disable elision for PTHREAD_MUTEX_DEFAULT.
Add lock elision to rwlocks

This code is very similar to the main pthread mutex code, but we have
to implement part of it in assembler.

The patch kit is large because there are so many combinations
of reader and writer locks, but it is fairly repetive.

The basic elision algorithm is very similar to normal mutexes:
a wrapper checks if the lock is free (both reader and writer)
We have to check both reader and writer because separating them
would require putting state on different cache lines.

The algorithm is very basic currently and may be tuned
more in the future.

No adaptation at this point, the elision will not automatically
disable itself. The programmer or user can do it explicitely though.

We use some padding in the internal rwlock as a elision flag.
This is 8 bytes on 64bits currently, but could be made smaller later
without compatibility problems (or to share some bytes with a
adaptation count). 32bit uses one byte.

2013-06-24  Andi Kleen <ak@linux.intel.com>
            Hongjiu Lu <hongjiu.lu@intel.com>

	* sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_rdlock.S: dito.
	* sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_timedrdlock.S: dito
	* sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_timedwrlock.S: dito.
	* sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_unlock.S: dito.
	* sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_wrlock.S: dito.
	* sysdeps/unix/sysv/linux/internaltypes.h (struct pthread_condattr):
	(struct pthread_rwlockattr): Support elision flags in internal rwlock.
	* sysdeps/unix/sysv/linux/lowlevelrwlock.sym: Add RW_ELISION.
	* sysdeps/unix/sysv/linux/x86/bits/pthreadtypes.h: Add elision flags
	* sysdeps/unix/sysv/linux/x86/pthread_rwlock_tryrdlock.c: New file
	* sysdeps/unix/sysv/linux/x86/pthread_rwlock_trywrlock.c: dito.
	* sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_rdlock.S: Handle elision.
	* sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_timedrdlock.S: dito.
	* sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_timedwrlock.S: dito.
	* sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_unlock.S: dito.
	* sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_wrlock.S: dito.
Add a configure option to enable lock elision and disable by default

Can be enabled with --enable-lock-elision=yes at configure time.

Note the committer needs to regenerate configure and INSTALL.

nptl/:
2013-06-27  Andi Kleen <ak@linux.intel.com>

	* config.h.in (ENABLE_LOCK_ELISION): Add.
	* configure.in (--enable-lock-elision): Add option.
	* manual/install.texi: Document --enable lock elision.
	* sysdeps/unix/sysv/linux/x86/elision-conf.c (elision_init):
	  Check ENABLE_LOCK_ELISION.
Add a new distinctive PTHREAD_MUTEX_NORMAL

There was a lot of discussion about the POSIX statement that
PTHREAD_MUTEX_NORMAL "shall" deadlock for mutexes that
get re-acquired by the same thread.

Elided mutexes act like recursive locks and would only deadlock
sometimes (any time an abort happens, e.g. at program startup
or when context switches or syscalls happen), but not guaranteed
every time.

This does not apply to DEFAULT mutexes.  But currently in glibc DEFAULT and
NORMAL is the same number.

The original elision code always disabled elision for any
pthread_mutexattr_settype/setkind()

So what we do here is:
- Add a new numeric value for PTHREAD_MUTEX_NORMAL
- Add a new symbol version for pthread_mutexattr_setkind
(and its aliases pthread_mutexattr_settype_np and __pthread_mutexattr_settype)
that disables elision for the new PTHREAD_MUTEX_NORMAL value
- The compat version for the old symbol version always
disables elision when a 0 type (old ambigious DEFAULT/NORMAL)
is passed (behaviour before this patch)

The result is that old binaries that use pthread_mutexattr_setkind()
for NORMAL/DEFAULT/TIMED_NP will disable elision, and new programs that
use it with PTHREAD_MUTEX_NORMAL only (but not default/timed) will
also disable elision. Any mutex not using pthread_mutexattr_setkind
or setting an ADAPTIVE type uses elision. The use of
pthread_mutexattr_setkind() for the default type is expected to be
rare, so this should not affect many programs.

Note an alternative would be to just disable nesting for these
normal mutexes (so always _xabort() before starting a transaction).
This would require additional checks in the fast path, and
since this case should be rare we just disable elision instead.

This adds new symbol versions to pthread, so the ABI test
files needed to be updated.

Thanks to Torvald Riegel, Roland McGrath, Richard Henderson, Rich Felker
for input on the discussion. This patch is based on the proposal from
Rich Felker, with some help from H.J. on the aliases.

nptl/:
2013-06-21  Andi Kleen  <ak@linux.intel.com>
            H.J. Lu  <hongjiu.lu@intel.com>
            Rich Felker <dalias@aerifal.cx>

	* Versions (pthread_mutexattr_settype,
	  pthread_mutexattr_setkind_np, __pthread_mutexattr_settype): Add
	  new version for GLIBC_2.18.
	* pthreadP.h: Use PTHREAD_MUTEX_DEFAULT to define derived
	  NORMAL mutexes. These disable elision in any case.
	* pthread_mutexattr_init.c (pthread_mutexattr_init):
	  Use PTHREAD_MUTEX_DEFAULT instead of PTHREAD_MUTEX_NORMAL.
	* pthread_mutex_init.c (default_mutexattr): Use
	  PTHREAD_MUTEX_DEFAULT as base value.
	  (__pthread_mutex_init): Add elision checks.
	* pthread_mutexattr_settype.c
	  (pthread_mutexattr_settype_worker): Rename from
	  __pthread_mutexattr_settype.
	  (__pthread_mutexattr_settype_new):
          Add new symbol version. Disable lock elision for NORMAL type.
	  (__pthread_mutexattr_settype_old): New function to disable lock
	  elision for old DEFAULT/NORMAL/TIMED type.
	* sysdeps/pthread/pthread.h (PTHREAD_MUTEX_NORMAL): Redefine
	  as new value.
        * pthreadP.h (PTHREAD_MUTEX_NORMAL_INT): Add.
	  (PTHREAD_MUTEX_KIND_MASK_NP): Update.
	  Change various NORMAL users to DEFAULT.
	* tst-mutex5.c: Use PTHREAD_MUTEX_DEFAULT.

/:
2013-06-21  Andi Kleen  <ak@linux.intel.com>

	* sysdeps/unix/sysv/linux/i386/nptl/libpthread.abilist: Add
          pthread_mutexattr_settype and related functions.
        * sysdeps/unix/sysv/linux/powerpc/powerpc32/fpu/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/powerpc/powerpc64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/s390/s390-32/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/s390/s390-64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sh/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sparc/sparc32/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sparc/sparc64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/x86_64/64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/x86_64/x32/nptl/libpthread.abilist: dito.
Add a new pthread_mutexattr_setelision_np interface.

Add a new pthread_mutexattr_setelision_np() export function
that allows enabling or disabling elision for a mutex.

This now implies no behaviour changes that are not undefined or
are "may" in POSIX to my knowledge. The previous trylock
changes have been eliminated.

It is purely a tuning hint.

nptl/:
2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* Makefile: Add pthread_mutexattr_setelision_np.
	* Versions: Add pthread_mutexattr_setelision_np for 2.18.
	* pthread_mutexattr_setelision_np.c (pthread_mutexattr_setelision_np):
	  New file to set elision attributes for a mutex attr.
	* sysdeps/unix/sysv/linux/x86/pthread_mutexattr_setelision_np.c: New file.
	* nptl/sysdeps/pthread/pthread.h (pthread_mutexattr_settype_np):
	  New prototype.

/:
2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* sysdeps/unix/sysv/linux/i386/nptl/libpthread.abilist: Add
          pthread_mutexattr_setelision_np and related functions.
        * sysdeps/unix/sysv/linux/powerpc/powerpc32/fpu/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/powerpc/powerpc64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/s390/s390-32/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/s390/s390-64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sh/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sparc/sparc32/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/sparc/sparc64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/x86_64/64/nptl/libpthread.abilist: dito.
        * sysdeps/unix/sysv/linux/x86_64/x32/nptl/libpthread.abilist: dito.
Add a new pthread_rwlockattr_setelision_np function for rwlocks

Add a new exported pthread_rwlockattr_setelision_np() function that allows
enabling or disabling elision for a rwlock.

This now implies no behaviour changes that are not undefined or
are "may" in POSIX to my knowledge. The previous trylock
changes have been eliminated.

This is now purely a tuning hint.

nptl/:
2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* Makefile (pthread_rwlockattr_setelision_np): Add new file.
	* Versions (pthread_rwlockattr_setelision_np): Add new symbol.
	* pthread_rwlockattr_setelision_np.c: New file.
	* pthread_rwlock_init (pthread_rwlock_init): Transfer elision state.
	* sysdeps/pthread/pthread.h (pthread_rwlockattr_setkind_np):
	  Add new prototype.
	* sysdeps/unix/sysv/linux/x86/pthread_rwlockattr_setelision_np.c:
	  New file.

/:
2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* sysdeps/unix/sysv/linux/i386/nptl/libpthread.abilist: Add
	  pthread_rwlockattr_setelision_np.
	* sysdeps/unix/sysv/linux/powerpc/powerpc32/fpu/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/powerpc/powerpc64/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/s390/s390-32/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/s390/s390-64/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/sh/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/sparc/sparc32/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/sparc/sparc64/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/x86_64/64/nptl/libpthread.abilist: dito.
	* sysdeps/unix/sysv/linux/x86_64/x32/nptl/libpthread.abilist: dito.
Add elision test cases

These rely on the in program tuning interfaces

2013-06-27  Andi Kleen  <ak@linux.intel.com>

	* Makefile (tst-elision1, tst-elision2): Add.
	* tst-elision1.c: New file to test elision.
	* tst-elision2.c: Likewise.
	* tst-elision-common.c: Likewise.
Add manual for lock elision

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

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.
Add vectorized getenv for glibc use

This adds a general "vectorized getenv" for glibc internal use.
The motivation is to allow subsystems to access environment variables
cheaply without having to rescan the environment completely.

The dynamic linker already walks the environment to look for its
LD_* variables. Extend this code to look for a number of
pre-registered GLIBC_* variables too. This can be done at basically
no additional cost. The only two variables currently pre-registered
are for the lock elision code.

For static builds which do not use the dynamic linker a similar
environment walking function is called at init time.

The variable values are saved in a global array that can be directly
accessed by libc and related libraries like libpthread.

2013-06-18  Andi Kleen  <ak@linux.intel.com>

	* elf/Makefile (dl-glibc-var.o): Add new file.
	* elf/Versions (_dl_glibc_var, __glibc_var_init): Export new symbols
	as GLIBC_PRIVATE.
	* elf/dl-environ.c (_dl_next_ld_env_entry): Look for GLIBC_ prefixes
	too. Return first character in new argument.
	* elf/dl-glibc-var.c (struct glibc_var): Define global array.
	(__record_glibc_var): New function to save glibc variables.
	(next_env_entry): Function to walk environment.
	(__glibc_var_init): Fallback function for static builds.
	* elf/rtld.c: Update comment.
	(process_envvars): Handle GLIBC_ variables and call __record_glibc_var.
	* include/glibc-var.h: New file.
	* sysdeps/generic/ldsodefs.h (_dl_next_ld_env_entry): Update prototype.
	* .gitignore: Add exception for glibc-var.h.
Add environment variable tuning for elision parameters.

Add tunables for enabling/disabling elision and tuning the elision retry
and skip counts.

This builds on the glibc-var infrastructure added earlier.

nptl/:
2013-06-18    Andi Kleen <ak@linux.intel.com>

	* sysdeps/unix/sysv/linux/x86/elision-conf.c (struct elision_config): Add.
	(struct tune): dito.
	(complain): New function to write error message.
	(elision_aconf_setup): New function to parse parameters.
	(elision_mutex_init): New function to parse GLIBC_PTHREAD_MUTEX.
	(elision_rwlock_init): New function to parse GLIBC_PTHREAD_RWLOCK.
	(elision_init): Call elision_mutex_init and elision_rwlock_init.

/:
2013-06-18    Andi Kleen <ak@linux.intel.com>

	* manual/elision.texi: Add sections describing environment variables.
regenerate configure
Add README.md