Patchwork [trans-mem] Beginning of refactoring

login
register
mail settings
Submitter Torvald Riegel
Date July 1, 2011, 8:23 p.m.
Message ID <1309551790.5106.3.camel@triegel.csb>
Download mbox | patch
Permalink /patch/102967/
State New
Headers show

Comments

Torvald Riegel - July 1, 2011, 8:23 p.m.
Attached patch adds a vector-like container implementation and uses it
for a transaction's undo log. Also, adds a flag to xmalloc/xrealloc that
requests the allocated data to be on cache lines that are not shared
with data accessed by other threads (this will get an actual
implementation in a later patch).

Ok for branch?
commit f8953dec8a791e691938cd2abc96eff3b9712024
Author: Torvald Riegel <triegel@redhat.com>
Date:   Fri Jul 1 22:18:33 2011 +0200

    Add vector-like container, use it for gtm_transaction::undo_log.
    
    	* containers.h: New file.
    	* util.cc (xmalloc, xrealloc): Accept cacheline-alloc flag.
    	* libitm_i.h (xmalloc, xrealloc): Moved declarations from here ...
    	* common.h: ... to here.
    	(local_undo): Use GTM::vector for gtm_transaction::local_undo.
    	* local.cc: Same.
Richard Henderson - July 1, 2011, 8:32 p.m.
On 07/01/2011 01:23 PM, Torvald Riegel wrote:
>     Add vector-like container, use it for gtm_transaction::undo_log.
>     
>     	* containers.h: New file.
>     	* util.cc (xmalloc, xrealloc): Accept cacheline-alloc flag.
>     	* libitm_i.h (xmalloc, xrealloc): Moved declarations from here ...
>     	* common.h: ... to here.
>     	(local_undo): Use GTM::vector for gtm_transaction::local_undo.
>     	* local.cc: Same.

Ok.


r~

Patch

diff --git a/libitm/common.h b/libitm/common.h
index d94ca94..9db566a 100644
--- a/libitm/common.h
+++ b/libitm/common.h
@@ -40,4 +40,24 @@ 
 #define likely(X)	__builtin_expect((X) != 0, 1)
 #define unlikely(X)	__builtin_expect((X), 0)
 
+namespace GTM HIDDEN {
+
+// Locally defined protected allocation functions.
+//
+// To avoid dependency on libstdc++ new/delete, as well as to not
+// interfere with the wrapping of the global new/delete we wrap for
+// the user in alloc_cpp.cc, use class-local versions that defer
+// to malloc/free.  Recall that operator new/delete does not go through
+// normal lookup and so we cannot simply inject a version into the
+// GTM namespace.
+// If separate_cl is true, the allocator will try to return memory that is on
+// cache lines that are not shared with any object used by another thread.
+extern void * xmalloc (size_t s, bool separate_cl = false)
+  __attribute__((malloc, nothrow));
+extern void * xrealloc (void *p, size_t s, bool separate_cl = false)
+  __attribute__((malloc, nothrow));
+
+} // namespace GTM
+
+
 #endif // COMMON_H
diff --git a/libitm/containers.h b/libitm/containers.h
new file mode 100644
index 0000000..13a6cbc
--- /dev/null
+++ b/libitm/containers.h
@@ -0,0 +1,110 @@ 
+/* Copyright (C) 2011 Free Software Foundation, Inc.
+   Contributed by Torvald Riegel <triegel@redhat.com>.
+
+   This file is part of the GNU Transactional Memory Library (libitm).
+
+   Libitm 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 3 of the License, or
+   (at your option) any later version.
+
+   Libitm 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.
+
+   Under Section 7 of GPL version 3, you are granted additional
+   permissions described in the GCC Runtime Library Exception, version
+   3.1, as published by the Free Software Foundation.
+
+   You should have received a copy of the GNU General Public License and
+   a copy of the GCC Runtime Library Exception along with this program;
+   see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+   <http://www.gnu.org/licenses/>.  */
+
+#ifndef LIBITM_CONTAINERS_H
+#define LIBITM_CONTAINERS_H 1
+
+#include "common.h"
+#include <stdio.h>
+
+namespace GTM HIDDEN {
+
+// A simple vector-like container.
+// If alloc_seperate_cl is true, allocations will happen on separate cache
+// lines.
+template <typename T, bool alloc_separate_cl = true>
+class vector
+{
+ private:
+  size_t m_capacity;
+  size_t m_size;
+  T* entries;
+
+  // Initial capacity of the vector.
+  static const size_t default_initial_capacity = 32;
+  // Above that capacity, grow vector by that size for each call.
+  static const size_t default_resize_max = 2048;
+  // Resize vector to at least this capacity.
+  static const size_t default_resize_min = 32;
+
+  // Don't try to copy this vector.
+  vector<T, alloc_separate_cl>(const vector<T, alloc_separate_cl>& x);
+
+ public:
+  typedef T datatype;
+  typedef T* iterator;
+
+  iterator begin() const { return entries; }
+  iterator end() const { return entries + m_size; }
+  T& operator[] (size_t pos) { return entries[pos]; }
+  const T& operator[] (size_t pos) const  { return entries[pos]; }
+
+  vector<T, alloc_separate_cl>(size_t initial_size = default_initial_capacity)
+    : m_capacity(initial_size),
+      m_size(0)
+  {
+    if (m_capacity > 0)
+      entries = (T*) xmalloc(sizeof(T) * m_capacity, alloc_separate_cl);
+    else
+      entries = 0;
+  }
+  ~vector<T, alloc_separate_cl>() { if (m_capacity) free(entries); }
+
+  void resize()
+  {
+    if (m_capacity >= default_resize_max)
+      m_capacity = m_capacity + default_resize_max;
+    else
+      m_capacity = m_capacity * 2;
+    if (m_capacity < default_resize_min)
+      m_capacity = default_resize_min;
+    entries = (T*) xrealloc(entries, sizeof(T) * m_capacity, alloc_separate_cl);
+  }
+  void resize_noinline() __attribute__((noinline)) { resize(); }
+
+  size_t size() const { return m_size; }
+  size_t capacity() const { return this->capacity; }
+
+  void clear() { m_size = 0; }
+
+  iterator push() {
+    // We don't want inlining here since push() is often on the fast path.
+    if (m_size == m_capacity) resize_noinline();
+    fprintf(stdout, "cap=%zu size=%zu ent=%p\n", m_capacity, m_size, entries);
+    return &entries[m_size++];
+  }
+
+  iterator pop() {
+    if (m_size > 0)
+      {
+        m_size--;
+        return entries + m_size;
+      }
+    else return 0;
+  }
+};
+
+} // namespace GTM
+
+#endif // LIBITM_CONTAINERS_H
diff --git a/libitm/libitm_i.h b/libitm/libitm_i.h
index 98c2c75..01b2e4a 100644
--- a/libitm/libitm_i.h
+++ b/libitm/libitm_i.h
@@ -53,18 +53,6 @@  template<> struct sized_integral<8> { typedef uint64_t type; };
 
 typedef unsigned int gtm_word __attribute__((mode (word)));
 
-// Locally defined protected allocation functions.
-//
-// To avoid dependency on libstdc++ new/delete, as well as to not
-// interfere with the wrapping of the global new/delete we wrap for
-// the user in alloc_cpp.cc, use class-local versions that defer
-// to malloc/free.  Recall that operator new/delete does not go through
-// normal lookup and so we cannot simply inject a version into the
-// GTM namespace.
-
-extern void * xmalloc (size_t s) __attribute__((malloc, nothrow));
-extern void * xrealloc (void *p, size_t s) __attribute__((malloc, nothrow));
-
 } // namespace GTM
 
 #include "target.h"
@@ -74,6 +62,7 @@  extern void * xrealloc (void *p, size_t s) __attribute__((malloc, nothrow));
 #include "cachepage.h"
 #include "stmlock.h"
 #include "dispatch.h"
+#include "containers.h"
 
 namespace GTM HIDDEN {
 
@@ -118,9 +107,7 @@  struct gtm_transaction
   gtm_jmpbuf jb;
 
   // Data used by local.c for the local memory undo log.
-  struct gtm_local_undo **local_undo;
-  size_t n_local_undo;
-  size_t size_local_undo;
+  vector<gtm_local_undo*> local_undo;
 
   // Data used by alloc.c for the malloc/free undo log.
   aa_tree<uintptr_t, gtm_alloc_action> alloc_actions;
diff --git a/libitm/local.cc b/libitm/local.cc
index 1681222..a1a5655 100644
--- a/libitm/local.cc
+++ b/libitm/local.cc
@@ -37,28 +37,20 @@  struct gtm_local_undo
 void
 gtm_transaction::commit_local ()
 {
-  gtm_local_undo **local_undo = this->local_undo;
-  size_t i, n = this->n_local_undo;
+  size_t i, n = local_undo.size();
 
   if (n > 0)
     {
       for (i = 0; i < n; ++i)
 	free (local_undo[i]);
-      this->n_local_undo = 0;
-    }
-  if (local_undo)
-    {
-      free (local_undo);
-      this->local_undo = NULL;
-      this->size_local_undo = 0;
+      this->local_undo.clear();
     }
 }
 
 void
 gtm_transaction::rollback_local (void)
 {
-  gtm_local_undo **local_undo = this->local_undo;
-  size_t i, n = this->n_local_undo;
+  size_t i, n = local_undo.size();
 
   if (n > 0)
     {
@@ -71,7 +63,7 @@  gtm_transaction::rollback_local (void)
 	      free (u);
 	    }
 	}
-      this->n_local_undo = 0;
+      local_undo.clear();
     }
 }
 
@@ -80,8 +72,7 @@  gtm_transaction::rollback_local (void)
 void
 gtm_transaction::drop_references_local (const void *ptr, size_t len)
 {
-  gtm_local_undo **local_undo = this->local_undo;
-  size_t i, n = this->n_local_undo;
+  size_t i, n = local_undo.size();
 
   if (n > 0)
     {
@@ -110,19 +101,7 @@  GTM_LB (const void *ptr, size_t len)
   undo->addr = (void *) ptr;
   undo->len = len;
 
-  if (tx->local_undo == NULL)
-    {
-      tx->size_local_undo = 32;
-      tx->local_undo = (gtm_local_undo **)
-	xmalloc (sizeof (undo) * tx->size_local_undo);
-    }
-  else if (tx->n_local_undo == tx->size_local_undo)
-    {
-      tx->size_local_undo *= 2;
-      tx->local_undo = (gtm_local_undo **)
-	xrealloc (tx->local_undo, sizeof (undo) * tx->size_local_undo);
-    }
-  tx->local_undo[tx->n_local_undo++] = undo;
+  tx->local_undo.push()[0] = undo;
 
   memcpy (undo->saved, ptr, len);
 }
diff --git a/libitm/util.cc b/libitm/util.cc
index b9a8727..e4ff778 100644
--- a/libitm/util.cc
+++ b/libitm/util.cc
@@ -59,8 +59,11 @@  GTM_fatal (const char *fmt, ...)
 }
 
 void *
-xmalloc (size_t size)
+xmalloc (size_t size, bool separate_cl)
 {
+  // TODO Use posix_memalign if separate_cl is true, or some other allocation
+  // method that will avoid sharing cache lines with data used by other
+  // threads.
   void *r = malloc (size);
   if (r == 0)
     GTM_fatal ("Out of memory allocating %lu bytes", (unsigned long) size);
@@ -68,8 +71,11 @@  xmalloc (size_t size)
 }
 
 void *
-xrealloc (void *old, size_t size)
+xrealloc (void *old, size_t size, bool separate_cl)
 {
+  // TODO Use posix_memalign if separate_cl is true, or some other allocation
+  // method that will avoid sharing cache lines with data used by other
+  // threads.
   void *r = realloc (old, size);
   if (r == 0)
     GTM_fatal ("Out of memory allocating %lu bytes", (unsigned long) size);