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-05-16  Andi Kleen  <ak@linux.intel.com>
            Hongjiu Lu  <hongjiu.lu@intel.com>

	* pthread_mutex_lock.c (adaptive_lock): Add
	(__pthread_mutex_lock): Add lock elision support.
	* pthread_mutex_timedlock.c (pthread_mutex_timedlock): dito.
	* pthread_mutex_trylock.c (__pthread_mutex_trylock): dito.
	* pthread_mutex_unlock.c (__pthread_mutex_unlock_usercnt): dito.
	* sysdeps/unix/sysv/linux/pthread_mutex_cond_lock.c: dito.
	* sysdeps/unix/sysv/linux/x86/bits/pthreadtypes.h: dito.
	* 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: dito.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_lock.c: dito.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_timedlock.c: dito.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_trylock.c: dito.
	* sysdeps/unix/sysv/linux/x86/pthread_mutex_unlock.c: dito.
	* pthreadP.h: (PTHREAD_MUTEX_UPGRADED_ELISION_NP): Add.
Support setting elision in pthread_mutexattr_settype

2013-05-16 Andi Kleen  <ak@linux.intel.com>

	* pthread_mutexattr_settype.c (__pthread_mutexattr_settype):
        Support elision flags.
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.

New lock type flags are exposed to force enable/disable elision
for a specific rwlocks.

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-05-16  Andi Kleen <ak@linux.intel.com>
            Hongjiu Lu <hongjiu.lu@intel.com>

	* pthread_rwlock_init.c (__pthread_rwlock_init): Support elision.
	* pthread_rwlockattr_setkind_np.c (pthread_rwlockattr_setkind_np): Support elision.
	* 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 ELIDED.
	* 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.
Extend the test suite for TSX and add some new tests to test elision

- Some of the existing mutex tests do not work with lock elision
semantics. We run them with PTHREAD_MUTEX=none PTHREAD_RWLOCK=none,
but do not otherwise modify it.

This is expected behaviour, related to RTM lock elision's inability
to track the owner of lock (see the original description for more
details). It's not expected that these changes will break any programs,
it's mostly related to obscure behaviour.
- I added some ifdefs to these tests and add new variants that
set the defines to test elision behaviour.
- Add new tests that explicitely check for elision.
Note strictly this violates the TSX spec which never guarantees any transaction
ever succeeding. However we assume simple transactions will succeed and will
fail if not.
- Add tests covering the new lock kinds.

2013-05-16  Andi Kleen  <ak@linux.intel.com>

	* Makefile: Add elision tests. Disable elision for some existing
        tests. Add comments describing this.
	* tst-abstime.c: Fix for elision.
	* tst-abstime1b.c: New file for lock elision code.
	* tst-abstime1c.c:dito.
	* tst-elision-common.c: dito.
	* tst-elision1.c: dito.
	* tst-elision1b.c: dito.
	* tst-elision2.c: dito.
	* tst-initializers2-c89.c: Handle lock elision
	* tst-initializers2-c99.c: dito.
	* tst-initializers2-gnu89.c: dito.
	* tst-initializers2-gnu99.c: dito.
	* tst-initializers2.c: dito.
	* tst-mutex5.c: Handle lock elision.
	* tst-mutex5b.c: New file.
	* tst-mutex5c.c: dito.
	* tst-mutex5d.c: dito
	* tst-mutex5e.c: dito.
	* tst-mutex7b.c: dito.
	* tst-mutex7c.c: dito.
	* tst-mutex7d.c: dito.
	* tst-mutex7e.c: dito.
	* tst-mutex8.c: Handle lock elision.
	* tst-mutex8b.c: New file.
	* tst-mutex8c.c: dito.
	* tst-mutex8d.c: dito.
	* tst-mutex8e.c: dito.
	* tst-mutex8f.c: dito.
	* tst-mutex8g.c: dito.
Fix tst-mutexpi8

tst-mutexpi8 didn't actually test PI because tst-mutex8 didn't have any
code to enable priority inheritance. Add the needed code in a ifdef.

This also fixes it for lock elision because priority inheritance turns
off elision, so we don't need to explicitely disable it.

2013-05-16  Andi Kleen  <ak@linux.intel.com>

	* tst-mutex8.c: Check for ENABLE_PI
	* tst-mutexpi8.c:  Set TYPE to PTHREAD_MUTEX_TIMED_NP.
Add manual for lock elision

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

2013-05-16  Andi Kleen  <ak@linux.intel.com>

	* manual/Makefile: Add elision.texi.
	* manual/threads.texi: Link to elision.
	  Describe PTHREAD_MUTEX_INIT_NP.
	* manual/elision.texi: New file.
	* manual/intro.texi: Link to elision.
	* manual/lang.texi: dito.
Add a configure option to enable lock elision and disable by default

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

When the option is not specified elision can be still enabled
by setting the environment variables or by the program setting
elision lock types directly.

Later the default could be switched to be on by default.

2013-05-16  Andi Kleen <ak@linux.intel.com>

	* config.h.in (ENABLE_LOCK_ELISION): Add.
	* configure: Regenerate.
	* configure.in (--enable-lock-elision): Add option.
	* manual/install.texi: Document --enable lock elision.
	* nptl/sysdeps/unix/sysv/linux/x86/elision-conf.c (elision_mutex_init):
	(elision_rwlock_init): Check ENABLE_LOCK_ELISION.
Add README.md