Add hle.h base header

Add a header to use the RTM _x* intrinsics to start/stop transactions.

Newer compilers / assembler implement those directly, but do it ourselves
here to be more compatible with older toolchains.

2012-12-22  Andi Kleen <ak@linux.intel.com>

	* nptl/sysdeps/unix/sysv/linux/x86/hle.h New file.
Add internal IFUNC call workaround

Avoid problems with internal hidden IFUNC calls.
See the referenced linker bug for detail

2012-12-22  Andi Kleen <ak@linux.intel.com>
            Hongjiu Lu <hongjiu.lu@intel.com>

	* nptl/pthreadP.h (extern void __pthread_disable_asynccancel):
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/Implies:
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/nptl-init.c:
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/Implies:
Adaptive lock elision implementation for glibc pthreads

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 upcoming Intel CPUs.

See http://software.intel.com/file/41604 for the full
specification.

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. Only the pthread
mutexes are currently adaptive.

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.  IFUNC is used
to select functions with these checks based on the RTM availability.

I cannot post performance numbers at this point.

The user can also tune this by setting the mutex type and environment
variables.

The lock transactions have a abort hook mechanism to hook into the abort
path. This is quite useful for some debugging, so I kept this
functionality.

Lock elision can be enabled/disabled using environment variables.
It can be also enabled or disabled using new lock types for
mutex and rwlocks.

The IFUNC implementation currently triggers some linker bugs,
that show up in the test suite when libc calls locks internally.
It works with HJ Lu's latest linker, but other linkers may
show additional failures.

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:

- A broken program that unlocks a free lock will crash.
  There are ways around this with some tradeoffs (more code in hot paths)
  This will also happen on systems without RTM with the patchkit.
  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.
- mutex appears free when elided.
  pthread_mutex_lock(mutex);
  if (pthread_mutex_trylock(mutex) != 0) do_something
  will not do something when the lock elided.
  However note that if the check is an assert it works as expected because the
  assert failure aborts and the region is re-executed non transactionally,
  with the old behaviour.
- 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.)

Currently elision is enabled by default on systems that support RTM,
unless explicitely disabled either in the program or by the user.
Given more experience we can decide if that is a good idea, or if it
should be opt-in.

This patch implements the basic infrastructure for elision.

Open issues:
- XTEST or not XTEST in unlock, see above.
- Find workarounds for the linker bugs
- There's a obscure race when first setting the elision type
the first time.
- Adaptation for rwlocks
- Condition variables don't use elision so far
- Better adaptation algorithms
- Elide spinlocks too?

2012-12-22  Andi Kleen  <ak@linux.intel.com>
            Hongjiu Lu <hongjiu.lu@intel.com>

	* nptl/nptl-init.c (__pthread_force_elision): Add.
	* nptl/pthreadP.h (__pthread_force_elision): Add.
	* nptl/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.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/Makefile: Imply x86
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-conf.c: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-conf.h: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-lock.c: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-timed.c: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-trylock.c: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/elision-unlock.c: New file
	* nptl/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.
Add external interface changes: new lock types for pthread_mutex_t

Essentially timed and adaptive mutexes have new variants
that enable or disable elision.

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* nptl/pthreadP.h: Add elision flags.
	* nptl/sysdeps/pthread/pthread.h: Add elision initializers.
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.

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.

We use IFUNC to avoid any fast path overhead on systems without RTM.

Condition variables currently do not support elision.

2012-12-22  Andi Kleen  <ak@linux.intel.com>
            Hongjiu Lu  <hongjiu.lu@intel.com>

	* nptl/pthread_mutex_lock.c (adaptive_lock): Add
	(__pthread_mutex_lock): Add lock elision support.
	* nptl/pthread_mutex_timedlock.c (pthread_mutex_timedlock): dito.
	* nptl/pthread_mutex_trylock.c (__pthread_mutex_trylock): dito.
	* nptl/pthread_mutex_unlock.c (__pthread_mutex_unlock_usercnt): dito.
	* nptl/sysdeps/unix/sysv/linux/pthread_mutex_cond_lock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/bits/pthreadtypes.h: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/Makefile: Newfile
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/force-elision.h: New file
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_cond_lock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_lock-nortm.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_lock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_timedlock-nortm.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_timedlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_trylock-nortm.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_trylock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_mutex_unlock.c: dito.
Support setting elision in pthread_mutexattr_settype

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* nptl/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. IFUNC is used to avoid any
fast path overhead on non RTM systems.

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.

No adaptation at this point.

2012-12-22  Andi Kleen <ak@linux.intel.com>
            Hongjiu Lu <hongjiu.lu@intel.com>

	* nptl/pthread_rwlock_init.c (__pthread_rwlock_init): Support elision.
	* nptl/pthread_rwlockattr_setkind_np.c (pthread_rwlockattr_setkind_np): Support elision.
	* nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_rdlock.S: New file.
	* nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_timedrdlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_timedwrlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_unlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i486/pthread_rwlock_wrlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/Makefile: New file.
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_rdlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_rdlock-rtm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_timedrdlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_timedrdlock-rtm.S:
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_timedwrlock-nortm.S:
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_timedwrlock-rtm.S:
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_wrlock-nortm.S:
	* nptl/sysdeps/unix/sysv/linux/i386/i686/multiarch/pthread_rwlock_wrlock-rtm.S:
	* nptl/sysdeps/unix/sysv/linux/internaltypes.h (struct pthread_condattr):
	(struct pthread_rwlockattr): Support elision flags in internal rwlock.
	* nptl/sysdeps/unix/sysv/linux/lowlevelrwlock.sym: Add ELIDED.
	* nptl/sysdeps/unix/sysv/linux/x86/bits/pthreadtypes.h: Add elision flags
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_rdlock.c: New file.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_timedrdlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_timedwrlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_tryrdlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_trywrlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86/multiarch/pthread_rwlock_wrlock.c: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/Makefile: New file
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_rdlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_rdlock-rtm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_timedrdlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_timedrdlock-rtm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_timedwrlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_timedwrlock-rtm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_wrlock-nortm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/multiarch/pthread_rwlock_wrlock-rtm.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_rdlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_timedrdlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_timedwrlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_unlock.S: dito.
	* nptl/sysdeps/unix/sysv/linux/x86_64/pthread_rwlock_wrlock.S: dito
Add __pthread_set_abort_hook export

Separate patch because it changes the external ABI.

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* Versions.def: Add GLIBC_2.17
	* nptl/Versions: Add __pthread_set_abort_hook.
	* nptl/sysdeps/pthread/pthread.h (__pthread_set_abort_hook,
         __pthread_abort_hook_t): Add.
	* sysdeps/unix/sysv/linux/i386/nptl/libpthread.abilist: Add 2.17.
	* sysdeps/unix/sysv/linux/x86_64/64/nptl/libpthread.abilist: 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.

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* nptl/Makefile: Add elision tests. Disable elision for some existing
        tests.
	* nptl/tst-abstime.c: Fix for elision.
	* nptl/tst-abstime1b.c: New file.
	* nptl/tst-abstime1c.c:dito.
	* nptl/tst-elision-common.c: New file.
	* nptl/tst-elision1.c: dito.
	* nptl/tst-elision1b.c: dito.
	* nptl/tst-elision2.c: dito.
	* nptl/tst-initializers2-c89.c: dito.
	* nptl/tst-initializers2-c99.c: dito.
	* nptl/tst-initializers2-gnu89.c: dito.
	* nptl/tst-initializers2-gnu99.c: dito.
	* nptl/tst-initializers2.c: dito.
	* nptl/tst-mutex5.c: dito.
	* nptl/tst-mutex5b.c: dito.
	* nptl/tst-mutex5c.c: dito.
	* nptl/tst-mutex5d.c: dito
	* nptl/tst-mutex5e.c: dito.
	* nptl/tst-mutex7b.c: dito.
	* nptl/tst-mutex7c.c: dito.
	* nptl/tst-mutex7d.c: dito.
	* nptl/tst-mutex7e.c: dito.
	* nptl/tst-mutex8.c: dito.
	* nptl/tst-mutex8b.c: dito.
	* nptl/tst-mutex8c.c: dito.
	* nptl/tst-mutex8d.c: dito.
	* nptl/tst-mutex8e.c: dito.
	* nptl/tst-mutex8f.c: dito.
	* nptl/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.

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* nptl/tst-mutex8.c: Check for ENABLE_PI
	* nptl/tst-mutexpi8.c:  Set ENABLE_PI.
Add manual for lock elision

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

2012-12-22  Andi Kleen  <ak@linux.intel.com>

	* 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.
add README.md for github