WL#3064 - waiting threads - wait-for graph and deadlock detection

client/mysqltest.c:
  compiler warnings
configure.in:
  remove old tests for unused programs
  disable the use of gcc built-ins if smp assembler atomics were selected explictily.
  add waiting_threads.o to THREAD_LOBJECTS
include/lf.h:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
  constructor/destructor in lf-alloc
include/my_pthread.h:
  shuffle set_timespec/set_timespec_nsec macros a bit to be able to fill
  several timeout structures with only one my_getsystime() call
include/waiting_threads.h:
  waiting threads - wait-for graph and deadlock detection
mysys/Makefile.am:
  add waiting_threads.c
mysys/lf_alloc-pin.c:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
  constructor/destructor in lf-alloc
mysys/lf_hash.c:
  constructor/destructor in lf-alloc
mysys/my_thr_init.c:
  remember end-of-stack pointer in the mysys_var
mysys/waiting_threads.c:
  waiting threads - wait-for graph and deadlock detection
storage/maria/ha_maria.cc:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
storage/maria/ma_commit.c:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
storage/maria/trnman.c:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
storage/maria/trnman_public.h:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
storage/maria/unittest/trnman-t.c:
  replace the end-of-stack pointer with the pointer to the end-of-stack pointer.
  the latter could be stored in THD (mysys_vars) and updated in pool-of-threads
  scheduler.
unittest/mysys/Makefile.am:
  add waiting_threads-t
unittest/mysys/lf-t.c:
  factor out the common code for multi-threaded stress unit tests
  move lf tests to a separate file
unittest/mysys/my_atomic-t.c:
  factor out the common code for multi-threaded stress unit tests
  move lf tests to a separate file
unittest/mysys/thr_template.c:
  factor out the common code for multi-threaded stress unit tests
unittest/mysys/waiting_threads-t.c:
  wt tests

1 files changed, 154 insertions, 0 deletions

diff --git a/include/waiting_threads.h b/include/waiting_threads.h
new file mode 100644
index 00000000000..92fbbf998be
--- /dev/null
+++ b/include/waiting_threads.h
@@ -0,0 +1,154 @@
+/* Copyright (C) 2008 MySQL AB
+
+   This program is free software; you can redistribute it and/or modify
+   it under the terms of the GNU General Public License as published by
+   the Free Software Foundation; version 2 of the License.
+
+   This program is distributed in the hope that it will be useful,
+   but WITHOUT ANY WARRANTY; without even the implied warranty of
+   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+   GNU General Public License for more details.
+
+   You should have received a copy of the GNU General Public License
+   along with this program; if not, write to the Free Software
+   Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA */
+
+#include <my_global.h>
+#include <my_sys.h>
+#include <lf.h>
+
+typedef struct st_wt_resource_id WT_RESOURCE_ID;
+
+typedef struct st_wt_resource_type {
+  int (*compare)(void *a, void *b);
+  const void *(*make_key)(WT_RESOURCE_ID *id, uint *len);
+} WT_RESOURCE_TYPE;
+
+struct st_wt_resource_id {
+  WT_RESOURCE_TYPE *type;
+  union {
+    void     *ptr;
+    ulonglong num;
+  } value;
+};
+
+extern uint wt_timeout_short, wt_deadlock_search_depth_short;
+extern uint wt_timeout_long, wt_deadlock_search_depth_long;
+
+#define WT_WAIT_STATS  24
+#define WT_CYCLE_STATS 32
+extern ulonglong wt_wait_table[WT_WAIT_STATS];
+extern uint32    wt_wait_stats[WT_WAIT_STATS+1];
+extern uint32    wt_cycle_stats[2][WT_CYCLE_STATS+1];
+extern uint32    wt_success_stats;
+
+/*
+  'lock' protects 'owners', 'state', and 'waiter_count'
+  'id' is read-only
+
+  a resource is picked up from a hash in a lock-free manner
+  it's returned pinned, so it cannot be freed at once
+  but it may be freed right after the pin is removed
+  to free a resource it should be
+    1. have no owners
+    2. have no waiters
+
+  two ways to access a resource:
+    1. find it in a hash
+       - it's returned pinned.
+        a) take a lock in exclusive mode
+        b) check the state, it should be ACTIVE
+        c) unpin
+    2. by a direct reference
+       - could only used if a resource cannot be freed
+       e.g. accessing a resource by thd->waiting_for is safe,
+       a resource cannot be freed as there's a thread waiting for it
+*/
+
+typedef struct st_wt_resource {
+  WT_RESOURCE_ID  id;
+  uint            waiter_count;
+  enum { ACTIVE, FREE } state;
+#ifndef DBUG_OFF
+  pthread_mutex_t  *mutex;
+#endif
+  /*
+    before the 'lock' all elements are mutable, after - immutable
+    in the sense that lf_hash_insert() won't memcpy() over them.
+    See wt_init().
+  */
+  pthread_rwlock_t lock;
+  pthread_cond_t   cond;
+  DYNAMIC_ARRAY    owners;
+} WT_RESOURCE;
+
+typedef struct st_wt_thd {
+  /*
+    XXX
+    there's no protection (mutex) against concurrent access of
+    the dynarray below. it is assumed that a caller will have it
+    automatically (not to protect this array but to protect its
+    own - caller's - data structures, and we'll get it for free.
+    If not, we'll need to add a mutex
+  */
+  DYNAMIC_ARRAY   my_resources;
+  /*
+    'waiting_for' is modified under waiting_for->lock, and only by thd itself
+    'waiting_for' is read lock-free (using pinning protocol), but a thd object
+    can read its own 'waiting_for' without any locks or tricks.
+  */
+  WT_RESOURCE    *waiting_for;
+  LF_PINS        *pins;
+  /*
+    weight relates to the desirability of a transaction being killed if it's
+    part of a deadlock. In a deadlock situation transactions with lower weights
+    are killed first.
+
+    Examples of using the weight to implement different selection strategies:
+
+    1. Latest
+        Keep all weights equal.
+    2. Random
+        Assight weights at random.
+        (variant: modify a weight randomly before every lock request)
+    3. Youngest
+        Set weight to -NOW()
+    4. Minimum locks
+        count locks granted in your lock manager, store the value as a weight
+    5. Minimum work
+        depends on the definition of "work". For example, store the number
+        of rows modifies in this transaction (or a length of REDO log for a
+        transaction) as a weight.
+
+    It is only statistically relevant and is not protected by any locks.
+  */
+  ulong volatile weight;
+  /*
+    'killed' is indirectly protected by waiting_for->lock -
+    a killed thread needs to clear its 'waiting_for', and thus needs a lock.
+    That is a thread needs an exclusive lock to read 'killed' reliably.
+    But other threads may change 'killed' from 0 to 1, a shared
+    lock is enough for that.
+   */
+  my_bool volatile killed;
+#ifndef DBUG_OFF
+  const char     *name;
+#endif
+} WT_THD;
+
+#define WT_TIMEOUT              ETIMEDOUT
+#define WT_OK                   0
+#define WT_DEADLOCK             -1
+#define WT_DEPTH_EXCEEDED       -2
+
+void wt_init(void);
+void wt_end(void);
+void wt_thd_init(WT_THD *);
+void wt_thd_destroy(WT_THD *);
+int wt_thd_will_wait_for(WT_THD *, WT_THD *, WT_RESOURCE_ID *);
+int wt_thd_dontwait(WT_THD *);
+int wt_thd_cond_timedwait(WT_THD *, pthread_mutex_t *);
+void wt_thd_release(WT_THD *, WT_RESOURCE_ID *);
+#define wt_thd_release_all(THD) wt_thd_release((THD), 0)
+int wt_resource_id_memcmp(void *, void *);
+