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 <trie...@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.
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 <trie...@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);
