amd64 atomic ops

lock-free alloc (WL#3229), lock-free hash (WL#3230)
bit functions made inline


include/Makefile.am:
  lf.h added
mysys/Makefile.am:
  lf_hash.c lf_dynarray.c lf_alloc-pin.c
include/atomic/nolock.h:
  amd64 atomic ops
include/atomic/rwlock.h:
  s/rw_lock/mutex/g
include/atomic/x86-gcc.h:
  amd64 atomic ops
  try PAUSE
include/my_global.h:
  STATIC_INLINE
mysys/mf_keycache.c:
  make bit functions inline
mysys/my_atomic.c:
  STATIC_INLINE
mysys/my_bitmap.c:
  make bit functions inline
sql/ha_myisam.cc:
  make bit functions inline
sql/item_func.cc:
  make bit functions inline
include/my_atomic.h:
  STATIC_INLINE
mysys/my_bit.c:
  make bit functions inline
sql/sql_select.cc:
  make bit functions inline
storage/myisam/mi_create.c:
  make bit functions inline
storage/myisam/mi_test2.c:
  make bit functions inline
storage/myisam/myisamchk.c:
  make bit functions inline
mysys/my_init.c:
  thread_size moved to mysys
sql/mysql_priv.h:
  thread_size moved to mysys
sql/set_var.cc:
  thread_size moved to mysys
include/my_sys.h:
  thread_size moved to mysys
sql/mysqld.cc:
  thread_size moved to mysys
sql/sql_parse.cc:
  thread_size moved to mysys
sql/sql_test.cc:
  thread_size moved to mysys
include/lf.h:
  dylf_dynarray refactored to remove 65536 elements limit
mysys/lf_alloc-pin.c:
  dylf_dynarray refactored to remove 65536 elements limit
mysys/lf_dynarray.c:
  dylf_dynarray refactored to remove 65536 elements limit
mysys/lf_hash.c:
  dylf_dynarray refactored to remove 65536 elements limit
unittest/mysys/my_atomic-t.c:
  fix to commit (remove debug code)

1 files changed, 186 insertions, 0 deletions

diff --git a/mysys/lf_dynarray.c b/mysys/lf_dynarray.c
new file mode 100644
index 00000000000..dcf99163ca1
--- /dev/null
+++ b/mysys/lf_dynarray.c
@@ -0,0 +1,186 @@
+/* Copyright (C) 2000 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; either version 2 of the License, or
+   (at your option) any later version.
+
+   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 */
+
+/*
+  Analog of DYNAMIC_ARRAY that never reallocs
+  (so no pointer into the array may ever become invalid).
+
+  Memory is allocated in non-contiguous chunks.
+  This data structure is not space efficient for sparce arrays.
+
+  The number of elements is limited to 2^16
+
+  Every element is aligned to sizeof(element) boundary
+  (to avoid false sharing if element is big enough).
+
+  Actually, it's wait-free, not lock-free ;-)
+*/
+
+#undef DBUG_OFF
+#include <my_global.h>
+#include <strings.h>
+#include <my_sys.h>
+#include <lf.h>
+
+void lf_dynarray_init(LF_DYNARRAY *array, uint element_size)
+{
+  bzero(array, sizeof(*array));
+  array->size_of_element=element_size;
+  my_atomic_rwlock_init(&array->lock);
+}
+
+static void recursive_free(void **alloc, int level)
+{
+  if (!alloc) return;
+
+  if (level)
+  {
+    int i;
+    for (i=0; i < LF_DYNARRAY_LEVEL_LENGTH; i++)
+      recursive_free(alloc[i], level-1);
+    my_free((void *)alloc, MYF(0));
+  }
+  else
+    my_free(alloc[-1], MYF(0));
+}
+
+void lf_dynarray_end(LF_DYNARRAY *array)
+{
+  int i;
+  for (i=0; i < LF_DYNARRAY_LEVELS; i++)
+    recursive_free(array->level[i], i);
+  my_atomic_rwlock_destroy(&array->lock);
+  bzero(array, sizeof(*array));
+}
+
+static const int dynarray_idxes_in_level[LF_DYNARRAY_LEVELS]=
+{
+  0, /* +1 here to to avoid -1's below */
+  LF_DYNARRAY_LEVEL_LENGTH,
+  LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH,
+  LF_DYNARRAY_LEVEL_LENGTH * LF_DYNARRAY_LEVEL_LENGTH *
+    LF_DYNARRAY_LEVEL_LENGTH
+};
+
+void *_lf_dynarray_lvalue(LF_DYNARRAY *array, uint idx)
+{
+  void * ptr, * volatile * ptr_ptr=0;
+  int i;
+
+  for (i=3; i > 0; i--)
+  {
+    if (ptr_ptr || idx >= dynarray_idxes_in_level[i])
+    {
+      if (!ptr_ptr)
+      {
+        ptr_ptr=&array->level[i];
+        idx-= dynarray_idxes_in_level[i];
+      }
+      ptr=*ptr_ptr;
+      if (!ptr)
+      {
+        void *alloc=my_malloc(LF_DYNARRAY_LEVEL_LENGTH * sizeof(void *),
+                              MYF(MY_WME|MY_ZEROFILL));
+        if (!alloc)
+          return(NULL);
+        if (my_atomic_casptr(ptr_ptr, &ptr, alloc))
+          ptr= alloc;
+        else
+          my_free(alloc, MYF(0));
+      }
+      ptr_ptr=((void **)ptr) + idx / dynarray_idxes_in_level[i];
+      idx%= dynarray_idxes_in_level[i];
+    }
+  }
+  if (!ptr_ptr)
+    ptr_ptr=&array->level[0];
+  ptr=*ptr_ptr;
+  if (!ptr)
+  {
+    void *alloc, *data;
+    alloc=my_malloc(LF_DYNARRAY_LEVEL_LENGTH * array->size_of_element +
+                    max(array->size_of_element, sizeof(void *)),
+                    MYF(MY_WME|MY_ZEROFILL));
+    if (!alloc)
+      return(NULL);
+    /* reserve the space for free() address */
+    data= alloc + sizeof(void *);
+    { /* alignment */
+      intptr mod= ((intptr)data) % array->size_of_element;
+      if (mod)
+        data+= array->size_of_element - mod;
+    }
+    ((void **)data)[-1]=alloc; /* free() will need the original pointer */
+    if (my_atomic_casptr(ptr_ptr, &ptr, data))
+      ptr= data;
+    else
+      my_free(alloc, MYF(0));
+  }
+  return ptr + array->size_of_element * idx;
+}
+
+void *_lf_dynarray_value(LF_DYNARRAY *array, uint idx)
+{
+  void * ptr, * volatile * ptr_ptr=0;
+  int i;
+
+  for (i=3; i > 0; i--)
+  {
+    if (ptr_ptr || idx >= dynarray_idxes_in_level[i])
+    {
+      if (!ptr_ptr)
+      {
+        ptr_ptr=&array->level[i];
+        idx-= dynarray_idxes_in_level[i];
+      }
+      ptr=*ptr_ptr;
+      if (!ptr)
+        return(NULL);
+      ptr_ptr=((void **)ptr) + idx / dynarray_idxes_in_level[i];
+      idx %= dynarray_idxes_in_level[i];
+    }
+  }
+  if (!ptr_ptr)
+    ptr_ptr=&array->level[0];
+  ptr=*ptr_ptr;
+  if (!ptr)
+    return(NULL);
+  return ptr + array->size_of_element * idx;
+}
+
+static int recursive_iterate(LF_DYNARRAY *array, void *ptr, int level,
+                             lf_dynarray_func func, void *arg)
+{
+  int res, i;
+  if (!ptr)
+    return 0;
+  if (!level)
+    return func(ptr, arg);
+  for (i=0; i < LF_DYNARRAY_LEVEL_LENGTH; i++)
+    if ((res=recursive_iterate(array, ((void **)ptr)[i], level-1, func, arg)))
+      return res;
+  return 0;
+}
+
+int _lf_dynarray_iterate(LF_DYNARRAY *array, lf_dynarray_func func, void *arg)
+{
+  int i, res;
+  for (i=0; i < LF_DYNARRAY_LEVELS; i++)
+    if ((res=recursive_iterate(array, array->level[i], i, func, arg)))
+      return res;
+  return 0;
+}
+