[patch] 3/n: trans-mem: runtime
Aldy Hernandez
aldyh@redhat.com
Thu Nov 3 17:53:00 GMT 2011
Index: libitm/method-wbetl.cc
===================================================================
--- libitm/method-wbetl.cc (.../trunk) (revision 0)
+++ libitm/method-wbetl.cc (.../branches/transactional-memory) (revision
180773)
@@ -0,0 +1,628 @@
+/* Copyright (C) 2009 Free Software Foundation, Inc.
+ Contributed by Richard Henderson <rth@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/>. */
+
+#include "libitm_i.h"
+
+namespace {
+
+using namespace GTM;
+
+class wbetl_dispatch : public abi_dispatch
+{
+ private:
+ static const size_t RW_SET_SIZE = 4096;
+
+ struct r_entry
+ {
+ gtm_version version;
+ gtm_stmlock *lock;
+ };
+
+ r_entry *m_rset_entries;
+ size_t m_rset_nb_entries;
+ size_t m_rset_size;
+
+ struct w_entry
+ {
+ /* There's a hashtable where the locks are held, so multiple
+ cachelines can hash to a given bucket. This link points to the
+ possible next cacheline that also hashes to this bucket. */
+ struct w_entry *next;
+
+ /* Every entry in this bucket (accessed by NEXT) has the same LOCK
+ address below. */
+ gtm_stmlock *lock;
+
+ gtm_cacheline *addr;
+ gtm_cacheline *value;
+ gtm_version version;
+ };
+
+ w_entry *m_wset_entries;
+ size_t m_wset_nb_entries;
+ size_t m_wset_size;
+ bool m_wset_reallocate;
+
+ gtm_version m_start;
+ gtm_version m_end;
+
+ gtm_cacheline_page *m_cache_page;
+ unsigned m_n_cache_page;
+
+ private:
+ bool local_w_entry_p (w_entry *w);
+ bool has_read (gtm_stmlock *lock);
+ bool validate();
+ bool extend();
+
+ gtm_cacheline *do_write_lock(gtm_cacheline *);
+ gtm_cacheline *do_after_write_lock(gtm_cacheline *);
+ const gtm_cacheline *do_read_lock(const gtm_cacheline *, bool);
+
+ public:
+ wbetl_dispatch();
+
+ virtual const gtm_cacheline *read_lock(const gtm_cacheline *,
ls_modifier);
+ virtual mask_pair write_lock(gtm_cacheline *, ls_modifier);
+
+ virtual bool trycommit();
+ virtual void rollback();
+ virtual void reinit();
+ virtual void fini();
+ virtual bool trydropreference (void *, size_t);
+};
+
+/* Check if W is one of our write locks. */
+
+inline bool
+wbetl_dispatch::local_w_entry_p (w_entry *w)
+{
+ return (m_wset_entries <= w && w < m_wset_entries + m_wset_nb_entries);
+}
+
+/* Check if stripe has been read previously. */
+
+inline bool
+wbetl_dispatch::has_read (gtm_stmlock *lock)
+{
+ // ??? Consider using an AA tree to lookup the r_set entries.
+ size_t n = m_rset_nb_entries;
+ for (size_t i = 0; i < n; ++i)
+ if (m_rset_entries[i].lock == lock)
+ return true;
+
+ return false;
+}
+
+/* Validate read set, i.e. check if all read addresses are still valid
now. */
+
+bool
+wbetl_dispatch::validate ()
+{
+ __sync_synchronize ();
+
+ size_t n = m_rset_nb_entries;
+ for (size_t i = 0; i < n; ++i)
+ {
+ r_entry *r = &m_rset_entries[i];
+ gtm_stmlock l = *r->lock;
+
+ if (gtm_stmlock_owned_p (l))
+ {
+ w_entry *w = (w_entry *) gtm_stmlock_get_addr (l);
+
+ // If someone has locked us, it better be by someone in the
+ // current thread.
+ if (!local_w_entry_p (w))
+ return false;
+ }
+ else if (gtm_stmlock_get_version (l) != r->version)
+ return false;
+ }
+
+ return true;
+}
+
+/* Extend the snapshot range. */
+
+bool
+wbetl_dispatch::extend ()
+{
+ gtm_version now = gtm_get_clock ();
+
+ if (validate ())
+ {
+ m_end = now;
+ return true;
+ }
+ return false;
+}
+
+/* Acquire a write lock on ADDR. */
+
+gtm_cacheline *
+wbetl_dispatch::do_write_lock(gtm_cacheline *addr)
+{
+ gtm_stmlock *lock;
+ gtm_stmlock l, l2;
+ gtm_version version;
+ w_entry *w, *prev = NULL;
+
+ lock = gtm_get_stmlock (addr);
+ l = *lock;
+
+ restart_no_load:
+ if (gtm_stmlock_owned_p (l))
+ {
+ w = (w_entry *) gtm_stmlock_get_addr (l);
+
+ /* Did we previously write the same address? */
+ if (local_w_entry_p (w))
+ {
+ prev = w;
+ while (1)
+ {
+ if (addr == prev->addr)
+ return prev->value;
+ if (prev->next == NULL)
+ break;
+ prev = prev->next;
+ }
+
+ /* Get version from previous entry write set. */
+ version = prev->version;
+
+ /* If there's not enough entries, we must reallocate the array,
+ which invalidates all pointers to write set entries, which
+ means we have to restart the transaction. */
+ if (m_wset_nb_entries == m_wset_size)
+ {
+ m_wset_size *= 2;
+ m_wset_reallocate = true;
+ gtm_tx()->restart (RESTART_REALLOCATE);
+ }
+
+ w = &m_wset_entries[m_wset_nb_entries];
+ goto do_write;
+ }
+
+ gtm_tx()->restart (RESTART_LOCKED_WRITE);
+ }
+ else
+ {
+ version = gtm_stmlock_get_version (l);
+
+ /* We might have read an older version previously. */
+ if (version > m_end)
+ {
+ if (has_read (lock))
+ gtm_tx()->restart (RESTART_VALIDATE_WRITE);
+ }
+
+ /* Extend write set, aborting to reallocate write set entries. */
+ if (m_wset_nb_entries == m_wset_size)
+ {
+ m_wset_size *= 2;
+ m_wset_reallocate = true;
+ gtm_tx()->restart (RESTART_REALLOCATE);
+ }
+
+ /* Acquire the lock. */
+ w = &m_wset_entries[m_wset_nb_entries];
+ l2 = gtm_stmlock_set_owned (w);
+ l = __sync_val_compare_and_swap (lock, l, l2);
+ if (l != l2)
+ goto restart_no_load;
+ }
+
+ do_write:
+ m_wset_nb_entries++;
+ if (prev != NULL)
+ prev->next = w;
+ w->next = 0;
+ w->lock = lock;
+ w->addr = addr;
+ w->version = version;
+
+ gtm_cacheline_page *page = m_cache_page;
+ unsigned index = m_n_cache_page;
+
+ if (page == NULL || index == gtm_cacheline_page::LINES)
+ {
+ gtm_cacheline_page *npage = new gtm_cacheline_page;
+ npage->prev = page;
+ m_cache_page = page = npage;
+ m_n_cache_page = 1;
+ index = 0;
+ }
+ else
+ m_n_cache_page = index + 1;
+
+ gtm_cacheline *line = &page->lines[index];
+ w->value = line;
+ page->masks[index] = 0;
+ *line = *addr;
+
+ return line;
+}
+
+gtm_cacheline *
+wbetl_dispatch::do_after_write_lock (gtm_cacheline *addr)
+{
+ gtm_stmlock *lock;
+ gtm_stmlock l;
+ w_entry *w;
+
+ lock = gtm_get_stmlock (addr);
+ l = *lock;
+ assert (gtm_stmlock_owned_p (l));
+
+ w = (w_entry *) gtm_stmlock_get_addr (l);
+ assert (local_w_entry_p (w));
+
+ while (1)
+ {
+ if (addr == w->addr)
+ return w->value;
+ w = w->next;
+ }
+}
+
+/* Acquire a read lock on ADDR. */
+
+const gtm_cacheline *
+wbetl_dispatch::do_read_lock (const gtm_cacheline *addr, bool after_read)
+{
+ gtm_stmlock *lock;
+ gtm_stmlock l, l2;
+ gtm_version version;
+ w_entry *w;
+
+ lock = gtm_get_stmlock (addr);
+ l = *lock;
+
+ restart_no_load:
+ if (gtm_stmlock_owned_p (l))
+ {
+ w = (w_entry *) gtm_stmlock_get_addr (l);
+
+ /* Did we previously write the same address? */
+ if (local_w_entry_p (w))
+ {
+ while (1)
+ {
+ if (addr == w->addr)
+ return w->value;
+ if (w->next == NULL)
+ return addr;
+ w = w->next;
+ }
+ }
+
+ gtm_tx()->restart (RESTART_LOCKED_READ);
+ }
+
+ version = gtm_stmlock_get_version (l);
+
+ /* If version is no longer valid, re-validate the read set. */
+ if (version > m_end)
+ {
+ if (!extend ())
+ gtm_tx()->restart (RESTART_VALIDATE_READ);
+
+ if (!after_read)
+ {
+ // Verify that the version has not yet been overwritten. The read
+ // value has not yet been added to read set and may not have been
+ // checked during the extend.
+ //
+ // ??? This only makes sense if we're actually reading the value
+ // and returning it now -- which I believe the original TinySTM
+ // did. This doesn't make a whole lot of sense when we're
+ // manipulating cachelines as we are now. Do we need some other
+ // form of lock verification here, or is the validate call in
+ // trycommit sufficient?
+
+ __sync_synchronize ();
+ l2 = *lock;
+ if (l != l2)
+ {
+ l = l2;
+ goto restart_no_load;
+ }
+ }
+ }
+
+ if (!after_read)
+ {
+ r_entry *r;
+
+ /* Add the address and version to the read set. */
+ if (m_rset_nb_entries == m_rset_size)
+ {
+ m_rset_size *= 2;
+
+ m_rset_entries = (r_entry *)
+ xrealloc (m_rset_entries, m_rset_size * sizeof(r_entry));
+ }
+ r = &m_rset_entries[m_rset_nb_entries++];
+ r->version = version;
+ r->lock = lock;
+ }
+
+ return addr;
+}
+
+const gtm_cacheline *
+wbetl_dispatch::read_lock (const gtm_cacheline *addr, ls_modifier ltype)
+{
+ switch (ltype)
+ {
+ case NONTXNAL:
+ return addr;
+ case R:
+ return do_read_lock (addr, false);
+ case RaR:
+ return do_read_lock (addr, true);
+ case RaW:
+ return do_after_write_lock (const_cast<gtm_cacheline *>(addr));
+ case RfW:
+ return do_write_lock (const_cast<gtm_cacheline *>(addr));
+ default:
+ abort ();
+ }
+}
+
+abi_dispatch::mask_pair
+wbetl_dispatch::write_lock (gtm_cacheline *addr, ls_modifier ltype)
+{
+ gtm_cacheline *line;
+
+ switch (ltype)
+ {
+ case NONTXNAL:
+ return mask_pair (addr, &mask_sink);
+ case W:
+ case WaR:
+ line = do_write_lock (addr);
+ break;
+ case WaW:
+ line = do_after_write_lock (addr);
+ break;
+ default:
+ abort ();
+ }
+
+ return mask_pair (line, gtm_cacheline_page::mask_for_page_line (line));
+}
+
+/* Commit the transaction. */
+
+bool
+wbetl_dispatch::trycommit ()
+{
+ const size_t n = m_wset_nb_entries;
+ if (n != 0)
+ {
+ /* Get commit timestamp. */
+ gtm_version t = gtm_inc_clock ();
+
+ /* Validate only if a concurrent transaction has started since. */
+ if (m_start != t - 1 && !validate ())
+ return false;
+
+ /* Install new versions. */
+ for (size_t i = 0; i < n; ++i)
+ {
+ w_entry *w = &m_wset_entries[i];
+ gtm_cacheline_mask mask
+ = *gtm_cacheline_page::mask_for_page_line (w->value);
+
+ /* Filter out any updates that overlap the libitm stack. */
+ mask = gtm_mask_stack (w->addr, mask);
+
+ gtm_cacheline::copy_mask (w->addr, w->value, mask);
+ }
+
+ /* Only emit barrier after all cachelines are copied. */
+ gtm_cacheline::copy_mask_wb ();
+
+ /* Drop locks. */
+ for (size_t i = 0; i < n; ++i)
+ {
+ w_entry *w = &m_wset_entries[i];
+
+ /* Every link along the chain has the same lock, but only
+ bother dropping the lock once per bucket (at the end). */
+ if (w->next == NULL)
+ *w->lock = gtm_stmlock_set_version (t);
+ }
+ }
+
+ __sync_synchronize ();
+ return true;
+}
+
+void
+wbetl_dispatch::rollback ()
+{
+ /* Drop locks. */
+ const size_t n = m_wset_nb_entries;
+ for (size_t i = 0; i < n; ++i)
+ {
+ w_entry *w = &m_wset_entries[i];
+
+ /* Every link along the chain has the same lock, but only
+ bother dropping the lock once per bucket (at the end). */
+ if (w->next == NULL)
+ *w->lock = gtm_stmlock_set_version (w->version);
+ }
+
+ __sync_synchronize ();
+}
+
+void
+wbetl_dispatch::reinit ()
+{
+ gtm_cacheline_page *page;
+
+ m_rset_nb_entries = 0;
+ m_wset_nb_entries = 0;
+
+ if (m_wset_reallocate)
+ {
+ m_wset_reallocate = 0;
+ m_wset_entries = (w_entry *)
+ xrealloc (m_wset_entries, m_wset_size * sizeof(w_entry));
+ }
+
+ page = m_cache_page;
+ if (page)
+ {
+ /* Release all but one of the pages of cachelines. */
+ gtm_cacheline_page *prev = page->prev;
+ if (prev)
+ {
+ page->prev = 0;
+ delete prev;
+ }
+
+ /* Start the next cacheline allocation from the beginning. */
+ m_n_cache_page = 0;
+ }
+
+ m_start = m_end = gtm_get_clock ();
+}
+
+void
+wbetl_dispatch::fini ()
+{
+ delete m_cache_page;
+ free (m_rset_entries);
+ free (m_wset_entries);
+ delete this;
+}
+
+/* Attempt to drop any internal references to PTR. Return TRUE if
successful.
+
+ This is an adaptation of the transactional memcpy function.
+
+ What we do here is flush out the current transactional content of
+ PTR to real memory, and remove the write mask bits associated with
+ it so future commits will ignore this piece of memory. */
+
+bool
+wbetl_dispatch::trydropreference (void *ptr, size_t size)
+{
+ if (size == 0)
+ return true;
+
+ if (!validate ())
+ return false;
+
+ uintptr_t isrc = (uintptr_t)ptr;
+ // The position in the source cacheline where *PTR starts.
+ uintptr_t sofs = isrc & (CACHELINE_SIZE - 1);
+ gtm_cacheline *src
+ = reinterpret_cast<gtm_cacheline *>(isrc & -CACHELINE_SIZE);
+ unsigned char *dst = (unsigned char *)ptr;
+ abi_dispatch::mask_pair pair;
+
+ // If we're trying to drop a reference, we should already have a
+ // write lock on it. If we don't have one, there's no work to do.
+ if (!gtm_stmlock_owned_p (*gtm_get_stmlock (src)))
+ return true;
+
+ // We copy the data in three stages:
+
+ // (a) Copy stray bytes at the beginning that are smaller than a
+ // cacheline.
+ if (sofs != 0)
+ {
+ size_t sleft = CACHELINE_SIZE - sofs;
+ size_t min = (size <= sleft ? size : sleft);
+
+ // WaW will give us the current locked entry.
+ pair = this->write_lock (src, WaW);
+
+ // *jedi mind wave*...these aren't the droids you're looking for.
+ *pair.mask &= ~((((gtm_cacheline_mask)1 << min) - 1) << sofs);
+
+ memcpy (dst, &pair.line->b[sofs], min);
+ dst += min;
+ src++;
+ size -= min;
+ }
+
+ // (b) Copy subsequent cacheline sized chunks.
+ while (size >= CACHELINE_SIZE)
+ {
+ pair = this->write_lock(src, WaW);
+ *pair.mask = 0;
+ memcpy (dst, pair.line, CACHELINE_SIZE);
+ dst += CACHELINE_SIZE;
+ src++;
+ size -= CACHELINE_SIZE;
+ }
+
+ // (c) Copy anything left over.
+ if (size != 0)
+ {
+ pair = this->write_lock(src, WaW);
+ *pair.mask &= ~(((gtm_cacheline_mask)1 << size) - 1);
+ memcpy (dst, pair.line, size);
+ }
+
+ // No need to drop locks, since we're going to abort the transaction
+ // anyhow.
+
+ return true;
+}
+
+
+wbetl_dispatch::wbetl_dispatch ()
+ : abi_dispatch (false, false)
+{
+ m_rset_entries = (r_entry *) xmalloc (RW_SET_SIZE * sizeof(r_entry));
+ m_rset_nb_entries = 0;
+ m_rset_size = RW_SET_SIZE;
+
+ m_wset_entries = (w_entry *) xmalloc (RW_SET_SIZE * sizeof(w_entry));
+ m_wset_nb_entries = 0;
+ m_wset_size = RW_SET_SIZE;
+ m_wset_reallocate = false;
+
+ m_start = m_end = gtm_get_clock ();
+
+ m_cache_page = 0;
+ m_n_cache_page = 0;
+}
+
+} // anon namespace
+
+abi_dispatch *
+GTM::dispatch_wbetl ()
+{
+ return new wbetl_dispatch ();
+}
Index: libitm/alloc_c.cc
===================================================================
--- libitm/alloc_c.cc (.../trunk) (revision 0)
+++ libitm/alloc_c.cc (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,72 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+ Contributed by Richard Henderson <rth@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/>. */
+
+#include "libitm_i.h"
+
+
+using namespace GTM;
+
+extern "C" {
+
+/* Wrap: malloc (size_t sz) */
+void *
+_ITM_malloc (size_t sz)
+{
+ void *r = malloc (sz);
+ if (r)
+ gtm_thr()->record_allocation (r, free);
+ return r;
+}
+
+/* Wrap: calloc (size_t nm, size_t sz) */
+void *
+_ITM_calloc (size_t nm, size_t sz)
+{
+ void *r = calloc (nm, sz);
+ if (r)
+ gtm_thr()->record_allocation (r, free);
+ return r;
+}
+
+/* Wrap: free (void *ptr) */
+void
+_ITM_free (void *ptr)
+{
+ if (ptr)
+ gtm_thr()->forget_allocation (ptr, free);
+}
+
+/* Forget any internal references to PTR. */
+
+__attribute__((transaction_pure))
+void ITM_REGPARM
+_ITM_dropReferences (void *ptr, size_t len)
+{
+ // The semantics of _ITM_dropReferences are not sufficiently defined
in the
+ // ABI specification, so it does not make sense to support it right
now. See
+ // the libitm documentation for details.
+ GTM_fatal("_ITM_dropReferences is not supported");
+}
+
+} // extern "C"
Index: libitm/clone.cc
===================================================================
--- libitm/clone.cc (.../trunk) (revision 0)
+++ libitm/clone.cc (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,184 @@
+/* Copyright (C) 2009, 2010, 2011 Free Software Foundation, Inc.
+ Contributed by Richard Henderson <rth@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/>. */
+
+#include "libitm_i.h"
+
+using namespace GTM;
+
+struct clone_entry
+{
+ void *orig, *clone;
+};
+
+struct clone_table
+{
+ clone_entry *table;
+ size_t size;
+ clone_table *next;
+};
+
+static clone_table *all_tables;
+
+static void *
+find_clone (void *ptr)
+{
+ clone_table *table;
+
+ for (table = all_tables; table ; table = table->next)
+ {
+ clone_entry *t = table->table;
+ size_t lo = 0, hi = table->size, i;
+
+ /* Quick test for whether PTR is present in this table. */
+ if (ptr < t[0].orig || ptr > t[hi - 1].orig)
+ continue;
+
+ /* Otherwise binary search. */
+ while (lo < hi)
+ {
+ i = (lo + hi) / 2;
+ if (ptr < t[i].orig)
+ hi = i;
+ else if (ptr > t[i].orig)
+ lo = i + 1;
+ else
+ return t[i].clone;
+ }
+
+ /* Given the quick test above, if we don't find the entry in
+ this table then it doesn't exist. */
+ break;
+ }
+
+ return NULL;
+}
+
+
+void * ITM_REGPARM
+_ITM_getTMCloneOrIrrevocable (void *ptr)
+{
+ void *ret = find_clone (ptr);
+ if (ret)
+ return ret;
+
+ gtm_thr()->serialirr_mode ();
+
+ return ptr;
+}
+
+void * ITM_REGPARM
+_ITM_getTMCloneSafe (void *ptr)
+{
+ void *ret = find_clone (ptr);
+ if (ret == NULL)
+ abort ();
+ return ret;
+}
+
+static int
+clone_entry_compare (const void *a, const void *b)
+{
+ const clone_entry *aa = (const clone_entry *)a;
+ const clone_entry *bb = (const clone_entry *)b;
+
+ if (aa->orig < bb->orig)
+ return -1;
+ else if (aa->orig > bb->orig)
+ return 1;
+ else
+ return 0;
+}
+
+namespace {
+
+// Within find_clone, we know that we are inside a transaction. Because
+// of that, we have already synchronized with serial_lock. By taking the
+// serial_lock for write, we exclude all transactions while we make this
+// change to the clone tables, without having to synchronize on a separate
+// lock. Do be careful not to attempt a recursive write lock.
+
+class ExcludeTransaction
+{
+ bool do_lock;
+
+ public:
+ ExcludeTransaction()
+ {
+ gtm_thread *tx = gtm_thr();
+ do_lock = !(tx && (tx->state & gtm_thread::STATE_SERIAL));
+
+ if (do_lock)
+ gtm_thread::serial_lock.write_lock ();
+ }
+
+ ~ExcludeTransaction()
+ {
+ if (do_lock)
+ gtm_thread::serial_lock.write_unlock ();
+ }
+};
+
+} // end anon namespace
+
+
+void
+_ITM_registerTMCloneTable (void *xent, size_t size)
+{
+ clone_entry *ent = static_cast<clone_entry *>(xent);
+ clone_table *table;
+
+ table = (clone_table *) xmalloc (sizeof (clone_table));
+ table->table = ent;
+ table->size = size;
+
+ qsort (ent, size, sizeof (clone_entry), clone_entry_compare);
+
+ // Hold the serial_lock while we update the ALL_TABLES datastructure.
+ {
+ ExcludeTransaction exclude;
+ table->next = all_tables;
+ all_tables = table;
+ }
+}
+
+void
+_ITM_deregisterTMCloneTable (void *xent)
+{
+ clone_entry *ent = static_cast<clone_entry *>(xent);
+ clone_table *tab;
+
+ // Hold the serial_lock while we update the ALL_TABLES datastructure.
+ {
+ ExcludeTransaction exclude;
+ clone_table **pprev;
+
+ for (pprev = &all_tables;
+ tab = *pprev, tab->table != ent;
+ pprev = &tab->next)
+ continue;
+ *pprev = tab->next;
+ }
+
+ free (tab);
+}
Index: libitm/dispatch.h
===================================================================
--- libitm/dispatch.h (.../trunk) (revision 0)
+++ libitm/dispatch.h (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,334 @@
+/* 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 DISPATCH_H
+#define DISPATCH_H 1
+
+#include "libitm.h"
+#include "common.h"
+
+// Creates ABI load/store methods (can be made virtual or static using M,
+// use M2 to create separate methods names for virtual and static)
+// The _PV variants are for the pure-virtual methods in the base class.
+#define ITM_READ_M(T, LSMOD, M, M2)
\
+ M _ITM_TYPE_##T ITM_REGPARM ITM_##LSMOD##T##M2 (const _ITM_TYPE_##T
*ptr) \
+ {
\
+ return load(ptr, abi_dispatch::LSMOD);
\
+ }
+
+#define ITM_READ_M_PV(T, LSMOD, M, M2)
\
+ M _ITM_TYPE_##T ITM_REGPARM ITM_##LSMOD##T##M2 (const _ITM_TYPE_##T
*ptr) \
+ = 0;
+
+#define ITM_WRITE_M(T, LSMOD, M, M2) \
+ M void ITM_REGPARM ITM_##LSMOD##T##M2 (_ITM_TYPE_##T *ptr, \
+ _ITM_TYPE_##T val) \
+ { \
+ store(ptr, val, abi_dispatch::LSMOD); \
+ }
+
+#define ITM_WRITE_M_PV(T, LSMOD, M, M2) \
+ M void ITM_REGPARM ITM_##LSMOD##T##M2 (_ITM_TYPE_##T *ptr, \
+ _ITM_TYPE_##T val) \
+ = 0;
+
+// Creates ABI load/store methods for all load/store modifiers for a
particular
+// type.
+#define CREATE_DISPATCH_METHODS_T(T, M, M2) \
+ ITM_READ_M(T, R, M, M2) \
+ ITM_READ_M(T, RaR, M, M2) \
+ ITM_READ_M(T, RaW, M, M2) \
+ ITM_READ_M(T, RfW, M, M2) \
+ ITM_WRITE_M(T, W, M, M2) \
+ ITM_WRITE_M(T, WaR, M, M2) \
+ ITM_WRITE_M(T, WaW, M, M2)
+#define CREATE_DISPATCH_METHODS_T_PV(T, M, M2) \
+ ITM_READ_M_PV(T, R, M, M2) \
+ ITM_READ_M_PV(T, RaR, M, M2) \
+ ITM_READ_M_PV(T, RaW, M, M2) \
+ ITM_READ_M_PV(T, RfW, M, M2) \
+ ITM_WRITE_M_PV(T, W, M, M2) \
+ ITM_WRITE_M_PV(T, WaR, M, M2) \
+ ITM_WRITE_M_PV(T, WaW, M, M2)
+
+// Creates ABI load/store methods for all types.
+// See CREATE_DISPATCH_FUNCTIONS for comments.
+#define CREATE_DISPATCH_METHODS(M, M2) \
+ CREATE_DISPATCH_METHODS_T (U1, M, M2) \
+ CREATE_DISPATCH_METHODS_T (U2, M, M2) \
+ CREATE_DISPATCH_METHODS_T (U4, M, M2) \
+ CREATE_DISPATCH_METHODS_T (U8, M, M2) \
+ CREATE_DISPATCH_METHODS_T (F, M, M2) \
+ CREATE_DISPATCH_METHODS_T (D, M, M2) \
+ CREATE_DISPATCH_METHODS_T (E, M, M2) \
+ CREATE_DISPATCH_METHODS_T (CF, M, M2) \
+ CREATE_DISPATCH_METHODS_T (CD, M, M2) \
+ CREATE_DISPATCH_METHODS_T (CE, M, M2)
+#define CREATE_DISPATCH_METHODS_PV(M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (U1, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (U2, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (U4, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (U8, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (F, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (D, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (E, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (CF, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (CD, M, M2) \
+ CREATE_DISPATCH_METHODS_T_PV (CE, M, M2)
+
+// Creates memcpy/memmove/memset methods.
+#define CREATE_DISPATCH_METHODS_MEM() \
+virtual void memtransfer(void *dst, const void* src, size_t size, \
+ bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod) \
+{ \
+ memtransfer_static(dst, src, size, may_overlap, dst_mod, src_mod); \
+} \
+virtual void memset(void *dst, int c, size_t size, ls_modifier mod) \
+{ \
+ memset_static(dst, c, size, mod); \
+}
+
+#define CREATE_DISPATCH_METHODS_MEM_PV() \
+virtual void memtransfer(void *dst, const void* src, size_t size, \
+ bool may_overlap, ls_modifier dst_mod, ls_modifier src_mod) = 0; \
+virtual void memset(void *dst, int c, size_t size, ls_modifier mod) = 0;
+
+
+// Creates ABI load/store functions that can target either a class or an
+// object.
+#define ITM_READ(T, LSMOD, TARGET, M2) \
+ _ITM_TYPE_##T ITM_REGPARM _ITM_##LSMOD##T (const _ITM_TYPE_##T *ptr) \
+ { \
+ return TARGET ITM_##LSMOD##T##M2(ptr); \
+ }
+
+#define ITM_WRITE(T, LSMOD, TARGET, M2)
\
+ void ITM_REGPARM _ITM_##LSMOD##T (_ITM_TYPE_##T *ptr, _ITM_TYPE_##T
val) \
+ {
\
+ TARGET ITM_##LSMOD##T##M2(ptr, val); \
+ }
+
+// Creates ABI load/store functions for all load/store modifiers for a
+// particular type.
+#define CREATE_DISPATCH_FUNCTIONS_T(T, TARGET, M2) \
+ ITM_READ(T, R, TARGET, M2) \
+ ITM_READ(T, RaR, TARGET, M2) \
+ ITM_READ(T, RaW, TARGET, M2) \
+ ITM_READ(T, RfW, TARGET, M2) \
+ ITM_WRITE(T, W, TARGET, M2) \
+ ITM_WRITE(T, WaR, TARGET, M2) \
+ ITM_WRITE(T, WaW, TARGET, M2)
+
+// Creates ABI memcpy/memmove/memset functions.
+#define ITM_MEMTRANSFER_DEF(TARGET, M2, NAME, READ, WRITE) \
+void ITM_REGPARM _ITM_memcpy##NAME(void *dst, const void *src, size_t
size) \
+{
\
+ TARGET memtransfer##M2 (dst, src, size,
\
+ false, GTM::abi_dispatch::WRITE, GTM::abi_dispatch::READ);
\
+}
\
+void ITM_REGPARM _ITM_memmove##NAME(void *dst, const void *src, size_t
size) \
+{
\
+ TARGET memtransfer##M2 (dst, src, size,
\
+ GTM::abi_dispatch::memmove_overlap_check(dst, src, size,
\
+ GTM::abi_dispatch::WRITE, GTM::abi_dispatch::READ),
\
+ GTM::abi_dispatch::WRITE, GTM::abi_dispatch::READ);
\
+}
+
+#define ITM_MEMSET_DEF(TARGET, M2, WRITE) \
+void ITM_REGPARM _ITM_memset##WRITE(void *dst, int c, size_t size) \
+{ \
+ TARGET memset##M2 (dst, c, size, GTM::abi_dispatch::WRITE); \
+} \
+
+
+// ??? The number of virtual methods is large (7*4 for integers, 7*6
for FP,
+// 7*3 for vectors). Is the cache footprint so costly that we should go for
+// a small table instead (i.e., only have two virtual load/store
methods for
+// each supported type)? Note that this doesn't affect custom code paths at
+// all because these use only direct calls.
+// A large cache footprint could especially decrease HTM performance (due
+// to HTM capacity). We could add the modifier (RaR etc.) as parameter,
which
+// would give us just 4*2+6*2+3*2 functions (so we'd just need one line for
+// the integer loads/stores), but then the modifier can be checked only at
+// runtime.
+// For memcpy/memmove/memset, we just have two virtual methods (memtransfer
+// and memset).
+#define CREATE_DISPATCH_FUNCTIONS(TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (U1, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (U2, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (U4, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (U8, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (F, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (D, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (E, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (CF, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (CD, TARGET, M2) \
+ CREATE_DISPATCH_FUNCTIONS_T (CE, TARGET, M2) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RnWt, NONTXNAL, W) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RnWtaR, NONTXNAL, WaR) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RnWtaW, NONTXNAL, WaW) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtWn, R, NONTXNAL) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtWt, R, W) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtWtaR, R, WaR) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtWtaW, R, WaW) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaRWn, RaR, NONTXNAL) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaRWt, RaR, W) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaRWtaR, RaR, WaR) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaRWtaW, RaR, WaW) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaWWn, RaW, NONTXNAL) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaWWt, RaW, W) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaWWtaR, RaW, WaR) \
+ ITM_MEMTRANSFER_DEF(TARGET, M2, RtaWWtaW, RaW, WaW) \
+ ITM_MEMSET_DEF(TARGET, M2, W) \
+ ITM_MEMSET_DEF(TARGET, M2, WaR) \
+ ITM_MEMSET_DEF(TARGET, M2, WaW)
+
+
+// Creates ABI load/store functions that delegate to a transactional
memcpy.
+#define ITM_READ_MEMCPY(T, LSMOD, TARGET, M2) \
+ _ITM_TYPE_##T ITM_REGPARM _ITM_##LSMOD##T (const _ITM_TYPE_##T *ptr)\
+ { \
+ _ITM_TYPE_##T v; \
+ TARGET memtransfer##M2(&v, ptr, sizeof(_ITM_TYPE_##T), false, \
+ GTM::abi_dispatch::NONTXNAL, GTM::abi_dispatch::LSMOD); \
+ return v; \
+ }
+
+#define ITM_WRITE_MEMCPY(T, LSMOD, TARGET, M2) \
+ void ITM_REGPARM _ITM_##LSMOD##T (_ITM_TYPE_##T *ptr, _ITM_TYPE_##T val)\
+ { \
+ TARGET memtransfer##M2(ptr, &val, sizeof(_ITM_TYPE_##T), false, \
+ GTM::abi_dispatch::LSMOD, GTM::abi_dispatch::NONTXNAL); \
+ }
+
+#define CREATE_DISPATCH_FUNCTIONS_T_MEMCPY(T, TARGET, M2) \
+ ITM_READ_MEMCPY(T, R, TARGET, M2) \
+ ITM_READ_MEMCPY(T, RaR, TARGET, M2) \
+ ITM_READ_MEMCPY(T, RaW, TARGET, M2) \
+ ITM_READ_MEMCPY(T, RfW, TARGET, M2) \
+ ITM_WRITE_MEMCPY(T, W, TARGET, M2) \
+ ITM_WRITE_MEMCPY(T, WaR, TARGET, M2) \
+ ITM_WRITE_MEMCPY(T, WaW, TARGET, M2)
+
+
+namespace GTM HIDDEN {
+
+struct gtm_transaction_cp;
+
+struct method_group
+{
+ // Start using a TM method from this group. This constructs required meta
+ // data on demand when this method group is actually used. Will be called
+ // either on first use or after a previous call to fini().
+ virtual void init() = 0;
+ // Stop using any method from this group for now. This can be used to
+ // destruct meta data as soon as this method group is not used anymore.
+ virtual void fini() = 0;
+};
+
+
+// This is the base interface that all TM methods have to implement.
+struct abi_dispatch
+{
+public:
+ enum ls_modifier { NONTXNAL, R, RaR, RaW, RfW, W, WaR, WaW };
+
+private:
+ // Disallow copies
+ abi_dispatch(const abi_dispatch &) = delete;
+ abi_dispatch& operator=(const abi_dispatch &) = delete;
+
+public:
+ // Starts or restarts a transaction. Is called right before executing the
+ // transactional application code (by either returning from
+ // gtm_thread::begin_transaction or doing the longjmp when restarting).
+ // Returns NO_RESTART if the transaction started successfully. Returns
+ // a real restart reason if it couldn't start and does need to abort.
This
+ // allows TM methods to just give up and delegate ensuring progress
to the
+ // restart mechanism. If it returns a restart reason, this call must be
+ // idempotent because it will trigger the restart mechanism, which could
+ // switch to a different TM method.
+ virtual gtm_restart_reason begin_or_restart() = 0;
+ // Tries to commit the transaction. Iff this returns true, the
transaction
+ // got committed and all per-transaction data will have been reset.
+ // Currently, this is called only for the commit of the outermost
+ // transaction, or when switching to serial mode (which can happen in a
+ // nested transaction).
+ // If privatization safety must be ensured in a quiescence-based way, set
+ // priv_time to a value different to 0. Nontransactional code will not be
+ // executed after this commit until all registered threads'
shared_state is
+ // larger than or equal to this value.
+ virtual bool trycommit(gtm_word& priv_time) = 0;
+ // Rolls back a transaction. Called on abort or after trycommit()
returned
+ // false.
+ virtual void rollback(gtm_transaction_cp *cp = 0) = 0;
+
+ // Return an alternative method that is compatible with the current
+ // method but supports closed nesting. Return zero if there is none.
+ // Note that too be compatible, it must be possible to switch to this
other
+ // method on begin of a nested transaction without committing or
restarting
+ // the parent method.
+ virtual abi_dispatch* closed_nesting_alternative() { return 0; }
+
+ bool read_only () const { return m_read_only; }
+ bool write_through() const { return m_write_through; }
+ bool can_run_uninstrumented_code() const
+ {
+ return m_can_run_uninstrumented_code;
+ }
+ // Returns true iff this TM method supports closed nesting.
+ bool closed_nesting() const { return m_closed_nesting; }
+ method_group* get_method_group() const { return m_method_group; }
+
+ static void *operator new(size_t s) { return xmalloc (s); }
+ static void operator delete(void *p) { free (p); }
+
+public:
+ static bool memmove_overlap_check(void *dst, const void *src, size_t
size,
+ ls_modifier dst_mod, ls_modifier src_mod);
+
+ // Creates the ABI dispatch methods for loads and stores.
+ // ??? Should the dispatch table instead be embedded in the dispatch
object
+ // to avoid the indirect lookup in the vtable?
+ CREATE_DISPATCH_METHODS_PV(virtual, )
+ // Creates the ABI dispatch methods for memcpy/memmove/memset.
+ CREATE_DISPATCH_METHODS_MEM_PV()
+
+protected:
+ const bool m_read_only;
+ const bool m_write_through;
+ const bool m_can_run_uninstrumented_code;
+ const bool m_closed_nesting;
+ method_group* const m_method_group;
+ abi_dispatch(bool ro, bool wt, bool uninstrumented, bool closed_nesting,
+ method_group* mg) :
+ m_read_only(ro), m_write_through(wt),
+ m_can_run_uninstrumented_code(uninstrumented),
+ m_closed_nesting(closed_nesting), m_method_group(mg)
+ { }
+};
+
+}
+
+#endif // DISPATCH_H
Index: libitm/aatree.cc
===================================================================
--- libitm/aatree.cc (.../trunk) (revision 0)
+++ libitm/aatree.cc (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,222 @@
+/* Copyright (C) 2009 Free Software Foundation, Inc.
+ Contributed by Richard Henderson <rth@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/>. */
+
+// Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
+// integer key, and data attached to the node via flexible array member.
+
+#include "libitm_i.h"
+
+namespace GTM HIDDEN {
+
+// The code for rebalancing the tree is greatly simplified by never
+// having to check for null pointers. Instead, leaf node links point
+// to this node, NIL, which points to itself.
+const aa_node_base aa_node_base::s_nil(0);
+
+
+// Remove left horizontal links. Swap the pointers of horizontal left
links.
+
+aa_node_base *
+aa_node_base::skew ()
+{
+ aa_node_base *l = this->link(L);
+ if (this->m_level != 0 && l->m_level == this->m_level)
+ {
+ this->set_link(L, l->link(R));
+ l->set_link(R, this);
+ return l;
+ }
+ return this;
+}
+
+
+// Remove consecutive horizontal links. Take the middle node,
+// elevate it, and return it.
+
+aa_node_base *
+aa_node_base::split ()
+{
+ aa_node_base *r = this->link(R);
+ if (this->m_level != 0 && r->link(R)->m_level == this->m_level)
+ {
+ this->set_link(R, r->link(L));
+ r->set_link(L, this);
+ r->m_level += 1;
+ return r;
+ }
+ return this;
+}
+
+// Decrease the level of THIS to be one more than the level of its
children.
+
+void
+aa_node_base::decrease_level ()
+{
+ aa_node_base *l = this->link(L);
+ aa_node_base *r = this->link(R);
+ level_type llev = l->m_level;
+ level_type rlev = r->m_level;
+ level_type should_be = (llev < rlev ? llev : rlev) + 1;
+
+ if (should_be < this->m_level)
+ {
+ this->m_level = should_be;
+ if (should_be < rlev)
+ r->m_level = should_be;
+ }
+}
+
+// Find and return the node in the tree with key K.
+
+template<typename KEY>
+typename aa_tree_key<KEY>::node_ptr
+aa_tree_key<KEY>::find(KEY k) const
+{
+ node_ptr t = m_tree;
+ if (t != 0)
+ do
+ {
+ if (t->key == k)
+ return t;
+ t = t->link(k > t->key);
+ }
+ while (!t->is_nil());
+ return 0;
+}
+
+// Insert N into T and rebalance. Return the new balanced tree.
+
+template<typename KEY>
+typename aa_tree_key<KEY>::node_ptr
+aa_tree_key<KEY>::insert_1 (node_ptr t, node_ptr n)
+{
+ bool dir = n->key > t->key;
+ node_ptr c = t->link(dir);
+
+ // Insert the node, recursively.
+ if (c->is_nil())
+ c = n;
+ else
+ c = insert_1 (c, n);
+ t->set_link(dir, c);
+
+ // Rebalance the tree, as needed.
+ t = t->skew();
+ t = t->split();
+
+ return t;
+}
+
+template<typename KEY>
+void
+aa_tree_key<KEY>::insert(node_ptr n)
+{
+ if (m_tree == 0)
+ m_tree = n;
+ else
+ m_tree = insert_1 (m_tree, n);
+}
+
+// Delete K from T and rebalance. Return the new balanced tree.
+
+template<typename KEY>
+typename aa_tree_key<KEY>::node_ptr
+aa_tree_key<KEY>::erase_1 (node_ptr t, KEY k, node_ptr *pfree)
+{
+ node_ptr r;
+ bool dir;
+
+ // If this is the node we're looking for, delete it. Else recurse.
+ if (k == t->key)
+ {
+ node_ptr l, sub, end;
+
+ l = t->link(node::L);
+ r = t->link(node::R);
+
+ if (pfree)
+ *pfree = t;
+
+ // If this is a leaf node, simply remove the node. Otherwise,
+ // we have to find either a predecessor or a successor node to
+ // replace this one.
+ if (l->is_nil())
+ {
+ if (r->is_nil())
+ return r;
+ sub = r, dir = node::L;
+ }
+ else
+ sub = l, dir = node::R;
+
+ // Find the successor or predecessor.
+ for (end = sub; !end->link(dir)->is_nil(); end = end->link(dir))
+ continue;
+
+ // Remove it (but don't free) from the subtree.
+ sub = erase_1 (sub, end->key, 0);
+
+ // Replace T with the successor we just extracted.
+ end->set_link(!dir, sub);
+ t = end;
+ }
+ else
+ {
+ dir = k > t->key;
+ t->set_link(dir, erase_1 (t->link(dir), k, pfree));
+ }
+
+ // Rebalance the tree.
+ t->decrease_level();
+ t = t->skew();
+ r = t->link(node::R)->skew();
+ t->set_link(node::R, r);
+ r->set_link(node::R, r->link(node::R)->skew());
+ t = t->split ();
+ t->set_link(node::R, t->link(node::R)->split());
+
+ return t;
+}
+
+template<typename KEY>
+typename aa_tree_key<KEY>::node_ptr
+aa_tree_key<KEY>::erase (KEY k)
+{
+ node_ptr t = m_tree;
+ if (t == 0)
+ return 0;
+
+ node_ptr do_free = 0;
+ t = erase_1 (t, k, &do_free);
+ if (t->is_nil())
+ t = 0;
+ m_tree = t;
+ return do_free;
+}
+
+// Instantiate key classes.
+
+template class aa_tree_key<uintptr_t>;
+
+} // namespace GTM
Index: libitm/aatree.h
===================================================================
--- libitm/aatree.h (.../trunk) (revision 0)
+++ libitm/aatree.h (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,215 @@
+/* Copyright (C) 2009, 2011 Free Software Foundation, Inc.
+ Contributed by Richard Henderson <rth@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/>. */
+
+/* Implements an AA tree (http://en.wikipedia.org/wiki/AA_tree) with an
+ integer key, and data attached to the node via flexible array
member. */
+
+#ifndef LIBITM_AATREE_H
+#define LIBITM_AATREE_H 1
+
+namespace GTM HIDDEN {
+
+template<typename KEY> class aa_tree_key;
+
+class aa_node_base
+{
+ public:
+ static const bool L = false;
+ static const bool R = true;
+
+ private:
+ typedef unsigned int level_type;
+
+ aa_node_base *m_link[2];
+ level_type m_level;
+
+ static const aa_node_base s_nil;
+
+ public:
+ aa_node_base(level_type l = 1)
+ : m_link { const_cast<aa_node_base *>(&s_nil),
+ const_cast<aa_node_base *>(&s_nil) },
+ m_level(l)
+ { }
+
+ bool is_nil() const { return this == &s_nil; }
+
+ aa_node_base * link(bool d) { return m_link[d]; }
+ void set_link(bool d, aa_node_base *val) { m_link[d] = val; }
+
+ aa_node_base *skew();
+ aa_node_base *split();
+ void decrease_level();
+
+ static void *operator new (size_t s) { return xmalloc (s); }
+ static void operator delete (void *p) { free (p); }
+};
+
+template<typename KEY>
+struct aa_node_key : public aa_node_base
+{
+ typedef aa_node_base base;
+
+ KEY key;
+
+ explicit aa_node_key(KEY k) : key(k) { }
+
+ aa_node_key * link(bool d)
+ {
+ return static_cast<aa_node_key *>(base::link(d));
+ }
+
+ aa_node_key *skew() { return static_cast<aa_node_key *>(base::skew()); }
+ aa_node_key *split() { return static_cast<aa_node_key
*>(base::split()); }
+};
+
+template<typename KEY, typename DATA>
+struct aa_node : public aa_node_key<KEY>
+{
+ typedef aa_node_key<KEY> base;
+
+ DATA data;
+
+ explicit aa_node(KEY k) : base(k) { }
+
+ aa_node * link(bool d)
+ {
+ return static_cast<aa_node *>(base::link(d));
+ }
+};
+
+template<typename KEY>
+class aa_tree_key
+{
+ public:
+ typedef aa_node_key<KEY> node;
+ typedef node *node_ptr;
+
+ protected:
+ node_ptr m_tree;
+
+ protected:
+ aa_tree_key() : m_tree(0) { }
+
+ node_ptr find(KEY k) const;
+
+ static node_ptr insert_1 (node_ptr t, node_ptr n);
+ void insert(node_ptr n);
+
+ static node_ptr erase_1 (node_ptr t, KEY k, node_ptr *pfree);
+ node_ptr erase(KEY k);
+};
+
+extern template class aa_tree_key<uintptr_t>;
+
+template<typename KEY, typename DATA>
+class aa_tree : public aa_tree_key<KEY>
+{
+ public:
+ typedef aa_tree_key<KEY> base;
+ typedef aa_node<KEY, DATA> node;
+ typedef node *node_ptr;
+
+ typedef void (*trav_callback)(KEY, DATA *, void *);
+
+ private:
+ static void clear_1 (node_ptr);
+ static void traverse_1 (node_ptr, trav_callback, void *);
+
+ public:
+ aa_tree() = default;
+ ~aa_tree() { clear(); }
+
+ static void *operator new (size_t s, aa_tree<KEY, DATA>* p) { return p; }
+
+ DATA *find(KEY k) const
+ {
+ node_ptr n = static_cast<node_ptr>(base::find (k));
+ return n ? &n->data : 0;
+ }
+
+ DATA *insert(KEY k)
+ {
+ node_ptr n = new node(k);
+ base::insert(n);
+ return &n->data;
+ }
+
+ void erase(KEY k)
+ {
+ node_ptr n = static_cast<node_ptr>(base::erase (k));
+ delete n;
+ }
+
+ node_ptr remove(KEY k, DATA** data)
+ {
+ node_ptr n = static_cast<node_ptr>(base::erase (k));
+ *data = (n ? &n->data : 0);
+ return n;
+ }
+
+ void clear()
+ {
+ node_ptr n = static_cast<node_ptr>(this->m_tree);
+ if (n)
+ {
+ this->m_tree = 0;
+ clear_1 (n);
+ }
+ }
+
+ void traverse (trav_callback cb, void *cb_data)
+ {
+ node_ptr t = static_cast<node_ptr>(this->m_tree);
+ if (t != 0)
+ traverse_1 (t, cb, cb_data);
+ }
+};
+
+
+template<typename KEY, typename DATA>
+void
+aa_tree<KEY, DATA>::clear_1 (node_ptr t)
+{
+ if (t->is_nil())
+ return;
+ clear_1 (t->link(node::L));
+ clear_1 (t->link(node::R));
+ delete t;
+}
+
+template<typename KEY, typename DATA>
+void
+aa_tree<KEY, DATA>::traverse_1 (node_ptr t, trav_callback cb, void
*cb_data)
+{
+ if (t->is_nil())
+ return;
+ cb (t->key, &t->data, cb_data);
+ traverse_1 (t->link(node::L), cb, cb_data);
+ traverse_1 (t->link(node::R), cb, cb_data);
+}
+
+} // namespace GTM
+
+#endif // LIBITM_AATREE_H
Index: libitm/libitm.texi
===================================================================
--- libitm/libitm.texi (.../trunk) (revision 0)
+++ libitm/libitm.texi (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,778 @@
+\input texinfo @c -*-texinfo-*-
+
+@c %**start of header
+@setfilename libitm.info
+@settitle GNU libitm
+@c %**end of header
+
+
+@copying
+Copyright @copyright{} 2011 Free Software Foundation, Inc.
+
+Permission is granted to copy, distribute and/or modify this document
+under the terms of the GNU Free Documentation License, Version 1.2 or
+any later version published by the Free Software Foundation; with the
+Invariant Sections being ``Funding Free Software'', the Front-Cover
+texts being (a) (see below), and with the Back-Cover Texts being (b)
+(see below). A copy of the license is included in the section entitled
+``GNU Free Documentation License''.
+
+(a) The FSF's Front-Cover Text is:
+
+ A GNU Manual
+
+(b) The FSF's Back-Cover Text is:
+
+ You have freedom to copy and modify this GNU Manual, like GNU
+ software. Copies published by the Free Software Foundation raise
+ funds for GNU development.
+@end copying
+
+@ifinfo
+@dircategory GNU Libraries
+@direntry
+* libitm: (libitm). GNU Transactional Memory Library
+@end direntry
+
+This manual documents the GNU Transactional Memory Library.
+
+Published by the Free Software Foundation
+51 Franklin Street, Fifth Floor
+Boston, MA 02110-1301 USA
+
+@insertcopying
+@end ifinfo
+
+
+@setchapternewpage odd
+
+@titlepage
+@title The GNU Transactional Memory Library
+@page
+@vskip 0pt plus 1filll
+@comment For the @value{version-GCC} Version*
+@sp 1
+Published by the Free Software Foundation @*
+51 Franklin Street, Fifth Floor@*
+Boston, MA 02110-1301, USA@*
+@sp 1
+@insertcopying
+@end titlepage
+
+@summarycontents
+@contents
+@page
+
+
+@node Top
+@top Introduction
+@cindex Introduction
+
+This manual documents the usage and internals of libitm, the GNU
Transactional
+Memory Library. It provides transaction support for accesses to a process'
+memory, enabling easy-to-use synchronization of accesses to shared
memory by
+several threads.
+
+
+@comment
+@comment When you add a new menu item, please keep the right hand
+@comment aligned to the same column. Do not use tabs. This provides
+@comment better formatting.
+@comment
+@menu
+* Enabling libitm:: How to enable libitm for your applications.
+* C/C++ Language Constructs for TM::
+ Notes on the language-level interface
supported
+ by gcc.
+* The libitm ABI:: Notes on the external ABI provided by
libitm.
+* Internals:: Notes on libitm's internal synchronization.
+* Copying:: GNU general public license says
+ how you can copy and share libgomp.
+* GNU Free Documentation License::
+ How you can copy and share this manual.
+* Funding:: How to help assure continued work for free
+ software.
+* Index:: Index of this documentation.
+@end menu
+
+
+@c ---------------------------------------------------------------------
+@c Enabling libitm
+@c ---------------------------------------------------------------------
+
+@node Enabling libitm
+@chapter Enabling libitm
+
+To activate support for TM in C/C++, the compile-time flag
@option{-fgnu-tm}
+must be specified. This enables TM language-level constructs such as
+transaction statements (@code{__transaction}, @pxref{C/C++ Language
+Constructs for TM} for details).
+
+@c ---------------------------------------------------------------------
+@c C/C++ Language Constructs for TM
+@c ---------------------------------------------------------------------
+
+@node C/C++ Language Constructs for TM
+@chapter C/C++ Language Constructs for TM
+
+TODO: link to the C++ TM spec. a few examples. how gcc's support differs.
+
+@c ---------------------------------------------------------------------
+@c The libitm ABI
+@c ---------------------------------------------------------------------
+
+@node The libitm ABI
+@chapter The libitm ABI
+
+The ABI provided by libitm is basically equal to the Linux variant of
Intel's
+current TM ABI specification document (Revision 1.1, May 6 2009) but
with the
+differences listed in this chapter. It would be good if these changes would
+eventually be merged into a future version of this specification. To ease
+look-up, the following subsections mirror the structure of this
specification.
+
+@section [No changes] Objectives
+@section [No changes] Non-objectives
+
+@section Library design principles
+@subsection [No changes] Calling conventions
+@subsection [No changes] TM library algorithms
+@subsection [No changes] Optimized load and store routines
+@subsection [No changes] Aligned load and store routines
+
+@subsection Data logging functions
+
+The memory locations accessed with transactional loads and stores and the
+memory locations whose values are logged must not overlap. This required
+separation only extends to the scope of the execution of one transaction
+including all the executions of all nested transactions.
+
+The compiler must be consistent (within the scope of a single transaction)
+about which memory locations are shared and which are not shared with other
+threads (i.e., data must be accessed either transactionally or
+nontransactionally). Otherwise, non-write-through TM algorithms would
not work.
+
+@subsection [No changes] Scatter/gather calls
+@subsection [No changes] Serial and irrevocable mode
+@subsection [No changes] Transaction descriptor
+@subsection Store allocation
+
+There is no @code{getTransaction} function.
+
+@subsection [No changes] Naming conventions
+
+@subsection Function pointer encryption
+
+Currently, this is not implemented.
+
+
+@section Types and macros list
+
+@code{_ITM_codeProperties} has changed,
@pxref{txn-code-properties,,Starting a
+transaction}.
+@code{_ITM_srcLocation} is not used.
+
+
+@section Function list
+
+@subsection Initialization and finalization functions
+These functions are not part of the ABI.
+
+@subsection [No changes] Version checking
+@subsection [No changes] Error reporting
+@subsection [No changes] inTransaction call
+
+@subsection State manipulation functions
+There is no @code{getTransaction} function. Transaction identifiers for
+nested transactions will be ordered but not necessarily sequential
(i.e., for
+a nested transaction's identifier @var{IN} and its enclosing transaction's
+identifier @var{IE}, it is guaranteed that @math{IN >= IE}).
+
+@subsection [No changes] Source locations
+
+@subsection Starting a transaction
+
+@subsubsection Transaction code properties
+
+@anchor{txn-code-properties}
+The bit @code{hasNoXMMUpdate} is instead called @code{hasNoVectorUpdate}.
+Iff it is set, vector register save/restore is not necessary for any target
+machine.
+
+The @code{hasNoFloatUpdate} bit (@code{0x0010}) is new. Iff it is set,
floating
+point register save/restore is not necessary for any target machine.
+
+@code{undoLogCode} is not supported and a fatal runtime error will be
raised
+if this bit is set. It is not properly defined in the ABI why barriers
+other than undo logging are not present; Are they not necessary (e.g., a
+transaction operating purely on thread-local data) or have they been
omitted by
+the compiler because it thinks that some kind of global synchronization
+(e.g., serial mode) might perform better? The specification suggests
that the
+latter might be the case, but the former seems to be more useful.
+
+The @code{readOnly} bit (@code{0x4000}) is new. @strong{TODO} Lexical
or dynamic
+scope?
+
+@code{hasNoRetry} is not supported. If this bit is not set, but
+@code{hasNoAbort} is set, the library can assume that transaction
+rollback will not be requested.
+
+It would be useful if the absence of externally-triggered rollbacks
would be
+reported for the dynamic scope as well, not just for the lexical scope
+(@code{hasNoAbort}). Without this, a library cannot exploit this together
+with flat nesting.
+
+@code{exceptionBlock} is not supported because exception blocks are not
used.
+
+@subsubsection [No changes] Windows exception state
+@subsubsection [No changes] Other machine state
+
+@subsubsection [No changes] Results from beginTransaction
+
+@subsection Aborting a transaction
+
+@code{_ITM_rollbackTransaction} is not supported.
@code{_ITM_abortTransaction}
+is supported but the abort reasons @code{exceptionBlockAbort},
+@code{TMConflict}, and @code{userRetry} are not supported. There are no
+exception blocks in general, so the related cases also do not have to be
+considered. To encode @code{__transaction_cancel [[outer]]}, compilers must
+set the new @code{outerAbort} bit (@code{0x10}) additionally to the
+@code{userAbort} bit in the abort reason.
+
+@subsection Committing a transaction
+
+The exception handling (EH) scheme is different. The Intel ABI requires the
+@code{_ITM_tryCommitTransaction} function that will return even when the
+commit failed and will have to be matched with calls to either
+@code{_ITM_abortTransaction} or @code{_ITM_commitTransaction}. In contrast,
+gcc relies on transactional wrappers for the functions of the Exception
+Handling ABI and on one additional commit function (shown below). This
allows
+the TM to keep track of EH internally and thus it does not have to
embed the
+cleanup of EH state into the existing EH code in the program.
+@code{_ITM_tryCommitTransaction} is not supported.
+@code{_ITM_commitTransactionToId} is also not supported because the
+propagation of thrown exceptions will not bypass commits of nested
+transactions.
+
+@example
+void _ITM_commitTransactionEH(void *exc_ptr) ITM_REGPARM;
+void *_ITM_cxa_allocate_exception (size_t);
+void _ITM_cxa_throw (void *obj, void *tinfo, void *dest);
+void *_ITM_cxa_begin_catch (void *exc_ptr);
+void _ITM_cxa_end_catch (void);
+@end example
+
+@code{_ITM_commitTransactionEH} must be called to commit a transaction
if an
+exception could be in flight at this position in the code.
@code{exc_ptr} is
+the current exception or zero if there is no current exception.
+The @code{_ITM_cxa...} functions are transactional wrappers for the
respective
+@code{__cxa...} functions and must be called instead of these in
transactional
+code.
+
+To support this EH scheme, libstdc++ needs to provide one additional
function
+(@code{_cxa_tm_cleanup}), which is used by the TM to clean up the exception
+handling state while rolling back a transaction:
+
+@example
+void __cxa_tm_cleanup (void *unthrown_obj, void *cleanup_exc,
+ unsigned int caught_count);
+@end example
+
+@code{unthrown_obj} is non-null if the program called
+@code{__cxa_allocate_exception} for this exception but did not yet called
+@code{__cxa_throw} for it. @code{cleanup_exc} is non-null if the program is
+currently processing a cleanup along an exception path but has not
caught this
+exception yet. @code{caught_count} is the nesting depth of
+@code{__cxa_begin_catch} within the transaction (which can be counted
by the TM
+using @code{_ITM_cxa_begin_catch} and @code{_ITM_cxa_end_catch});
+@code{__cxa_tm_cleanup} then performs rollback by essentially performing
+@code{__cxa_end_catch} that many times.
+
+
+
+@subsection Exception handling support
+
+Currently, there is no support for functionality like
+@code{__transaction_cancel throw} as described in the C++ TM specification.
+Supporting this should be possible with the EH scheme explained previously
+because via the transactional wrappers for the EH ABI, the TM is able to
+observe and intercept EH.
+
+
+@subsection [No changes] Transition to serial--irrevocable mode
+@subsection [No changes] Data transfer functions
+@subsection [No changes] Transactional memory copies
+
+@subsection Transactional versions of memmove
+
+If either the source or destination memory region is to be accessed
+nontransactionally, then source and destination regions must not be
+overlapping. The respective @code{_ITM_memmove} functions are still
+available but a fatal runtime error will be raised if such regions do
overlap.
+To support this functionality, the ABI would have to specify how the
+intersection of the regions has to be accessed (i.e., transactionally or
+nontransactionally).
+
+@subsection [No changes] Transactional versions of memset
+@subsection [No changes] Logging functions
+
+@subsection User-registered commit and undo actions
+
+Commit actions will get executed in the same order in which the respective
+calls to @code{_ITM_addUserCommitAction} happened. Only
+@code{_ITM_noTransactionId} is allowed as value for the
+@code{resumingTransactionId} argument. Commit actions get executed after
+privatization safety has been ensured.
+
+Undo actions will get executed in reverse order compared to the order
in which
+the respective calls to @code{_ITM_addUserUndoAction} happened. The
ordering of
+undo actions w.r.t. the roll-back of other actions (e.g., data transfers or
+memory allocations) is undefined.
+
+@code{_ITM_getThreadnum} is not supported currently because its only
purpose
+is to provide a thread ID that matches some assumed performance tuning
output,
+but this output is not part of the ABI nor further defined by it.
+
+@code{_ITM_dropReferences} is not supported currently because its
semantics and
+the intention behind it is not entirely clear. The
+specification suggests that this function is necessary because of certain
+orderings of data transfer undos and the releasing of memory regions (i.e.,
+privatization). However, this ordering is never defined, nor is the
ordering of
+dropping references w.r.t. other events.
+
+@subsection [New] Transactional indirect calls
+
+Indirect calls (i.e., calls through a function pointer) within transactions
+should execute the transactional clone of the original function (i.e.,
a clone
+of the original that has been fully instrumented to use the TM runtime), if
+such a clone is available. The runtime provides two functions to
+register/deregister clone tables:
+
+@example
+struct clone_entry
+@{
+ void *orig, *clone;
+@};
+
+void _ITM_registerTMCloneTable (clone_entry *table, size_t entries);
+void _ITM_deregisterTMCloneTable (clone_entry *table);
+@end example
+
+Registered tables must be writable by the TM runtime, and must be live
+throughout the life-time of the TM runtime.
+
+@strong{TODO} The intention was always to drop the registration functions
+entirely, and create a new ELF Phdr describing the linker-sorted table.
Much
+like what currently happens for @code{PT_GNU_EH_FRAME}.
+This work kept getting bogged down in how to represent the @var{N}
different
+code generation variants. We clearly needed at least two---SW and HW
+transactional clones---but there was always a suggestion of more
variants for
+different TM assumptions/invariants.
+
+The compiler can then use two TM runtime functions to perform indirect
calls in
+transactions:
+@example
+void *_ITM_getTMCloneOrIrrevocable (void *function) ITM_REGPARM;
+void *_ITM_getTMCloneSafe (void *function) ITM_REGPARM;
+@end example
+
+If there is a registered clone for supplied function, both will return a
+pointer to the clone. If not, the first runtime function will attempt
to switch
+to serial--irrevocable mode and return the original pointer, whereas
the second
+will raise a fatal runtime error.
+
+@subsection [New] Transactional dynamic memory management
+
+@example
+void *_ITM_malloc (size_t)
+ __attribute__((__malloc__)) ITM_PURE;
+void *_ITM_calloc (size_t, size_t)
+ __attribute__((__malloc__)) ITM_PURE;
+void _ITM_free (void *) ITM_PURE;
+@end example
+
+These functions are essentially transactional wrappers for @code{malloc},
+@code{calloc}, and @code{free}. Within transactions, the compiler should
+replace calls to the original functions with calls to the wrapper
functions.
+
+
+@section [No changes] Future Enhancements to the ABI
+
+@section Sample code
+
+The code examples might not be correct w.r.t. the current version of
the ABI,
+especially everything related to exception handling.
+
+
+@section [New] Memory model
+
+The ABI should define a memory model and the ordering that is
guaranteed for
+data transfers and commit/undo actions, or at least refer to another memory
+model that needs to be preserved. Without that, the compiler cannot
ensure the
+memory model specified on the level of the programming language (e.g.,
by the
+C++ TM specification).
+
+For example, if a transactional load is ordered before another
load/store, then
+the TM runtime must also ensure this ordering when accessing shared
state. If
+not, this might break the kind of publication safety used in the C++ TM
+specification. Likewise, the TM runtime must ensure privatization safety.
+
+
+
+@c ---------------------------------------------------------------------
+@c Internals
+@c ---------------------------------------------------------------------
+
+@node Internals
+@chapter Internals
+
+@section TM methods and method groups
+
+libitm supports several ways of synchronizing transactions with each other.
+These TM methods (or TM algorithms) are implemented in the form of
+subclasses of @code{abi_dispatch}, which provide methods for
+transactional loads and stores as well as callbacks for rollback and
commit.
+All methods that are compatible with each other (i.e., that let
concurrently
+running transactions still synchronize correctly even if different methods
+are used) belong to the same TM method group. Pointers to TM methods can be
+obtained using the factory methods prefixed with @code{dispatch_} in
+@file{libitm_i.h}. There are two special methods,
@code{dispatch_serial} and
+@code{dispatch_serialirr}, that are compatible with all methods because
they
+run transactions completely in serial mode.
+
+@subsection TM method life cycle
+
+The state of TM methods does not change after construction, but they do
alter
+the state of transactions that use this method. However, because
+per-transaction data gets used by several methods, @code{gtm_thread} is
+responsible for setting an initial state that is useful for all methods.
+After that, methods are responsible for resetting/clearing this state
on each
+rollback or commit (of outermost transactions), so that the transaction
+executed next is not affected by the previous transaction.
+
+There is also global state associated with each method group, which is
+initialized and shut down (@code{method_group::init()} and @code{fini()})
+when switching between method groups (see @file{retry.cc}).
+
+@subsection Selecting the default method
+
+The default method that libitm uses for freshly started transactions (but
+not necessarily for restarted transactions) can be set via an environment
+variable (@env{ITM_DEFAULT_METHOD}), whose value should be equal to the
name
+of one of the factory methods returning abi_dispatch subclasses but without
+the "dispatch_" prefix (e.g., "serialirr" instead of
+@code{GTM::dispatch_serialirr()}).
+
+Note that this environment variable is only a hint for libitm and might not
+be supported in the future.
+
+
+@section Nesting: flat vs. closed
+
+We support two different kinds of nesting of transactions. In the case of
+@emph{flat nesting}, the nesting structure is flattened and all nested
+transactions are subsumed by the enclosing transaction. In contrast,
+with @emph{closed nesting}, nested transactions that have not yet committed
+can be rolled back separately from the enclosing transactions; when they
+commit, they are subsumed by the enclosing transaction, and their effects
+will be finally committed when the outermost transaction commits.
+@emph{Open nesting} (where nested transactions can commit independently
of the
+enclosing transactions) are not supported.
+
+Flat nesting is the default nesting mode, but closed nesting is
supported and
+used when transactions contain user-controlled aborts
+(@code{__transaction_cancel} statements). We assume that user-controlled
+aborts are rare in typical code and used mostly in exceptional situations.
+Thus, it makes more sense to use flat nesting by default to avoid the
+performance overhead of the additional checkpoints required for closed
+nesting. User-controlled aborts will correctly abort the innermost
enclosing
+transaction, whereas the whole (i.e., outermost) transaction will be
restarted
+otherwise (e.g., when a transaction encounters data conflicts during
+optimistic execution).
+
+
+@section Locking conventions
+
+This section documents the locking scheme and rules for all uses of locking
+in libitm. We have to support serial(-irrevocable) mode, which is
implemented
+using a global lock as explained next (called the @emph{serial lock}). To
+simplify the overall design, we use the same lock as catch-all locking
+mechanism for other infrequent tasks such as (de)registering clone
tables or
+threads. Besides the serial lock, there are @emph{per-method-group
locks} that
+are managed by specific method groups (i.e., groups of similar TM
concurrency
+control algorithms), and lock-like constructs for quiescence-based
operations
+such as ensuring privatization safety.
+
+Thus, the actions that participate in the libitm-internal locking are
either
+@emph{active transactions} that do not run in serial mode, @emph{serial
+transactions} (which (are about to) run in serial mode), and management
tasks
+that do not execute within a transaction but have acquired the serial mode
+like a serial transaction would do (e.g., to be able to register
threads with
+libitm). Transactions become active as soon as they have successfully
used the
+serial lock to announce this globally (@pxref{serial-lock-impl,,Serial lock
+implementation}). Likewise, transactions become serial transactions as
soon as
+they have acquired the exclusive rights provided by the serial lock (i.e.,
+serial mode, which also means that there are no other concurrent active or
+serial transactions). Note that active transactions can become serial
+transactions when they enter serial mode during the runtime of the
+transaction.
+
+@subsection State-to-lock mapping
+
+Application data is protected by the serial lock if there is a serial
+transaction and no concurrently running active transaction (i.e.,
non-serial).
+Otherwise, application data is protected by the currently selected method
+group, which might use per-method-group locks or other mechanisms. Also
note
+that application data that is about to be privatized might not be
allowed to be
+accessed by nontransactional code until privatization safety has been
ensured;
+the details of this are handled by the current method group.
+
+libitm-internal state is either protected by the serial lock or accessed
+through custom concurrent code. The latter applies to the public/shared
part
+of a transaction object and most typical method-group-specific state.
+
+The former category (protected by the serial lock) includes:
+@itemize @bullet
+@item The list of active threads that have used transactions.
+@item The tables that map functions to their transactional clones.
+@item The current selection of which method group to use.
+@item Some method-group-specific data, or invariants of this data. For
example,
+resetting a method group to its initial state is handled by switching
to the
+same method group, so the serial lock protects such resetting as well.
+@end itemize
+In general, such state is immutable whenever there exists an active
+(non-serial) transaction. If there is no active transaction, a serial
+transaction (or a thread that is not currently executing a transaction
but has
+acquired the serial lock) is allowed to modify this state (but must of
course
+be careful to not surprise the current method group's implementation
with such
+modifications).
+
+@subsection Lock acquisition order
+
+To prevent deadlocks, locks acquisition must happen in a globally
agreed-upon
+order. Note that this applies to other forms of blocking too, but does not
+necessarily apply to lock acquisitions that do not block (e.g., trylock()
+calls that do not get retried forever). Note that serial transactions are
+never return back to active transactions until the transaction has
committed.
+Likewise, active transactions stay active until they have committed.
+Per-method-group locks are typically also not released before commit.
+
+Lock acquisition / blocking rules:
+@itemize @bullet
+
+@item Transactions must become active or serial before they are allowed to
+use method-group-specific locks or blocking (i.e., the serial lock must be
+acquired before those other locks, either in serial or nonserial mode).
+
+@item Any number of threads that do not currently run active
transactions can
+block while trying to get the serial lock in exclusive mode. Note that
active
+transactions must not block when trying to upgrade to serial mode
unless there
+is no other transaction that is trying that (the latter is ensured by the
+serial lock implementation.
+
+@item Method groups must prevent deadlocks on their locks. In
particular, they
+must also be prepared for another active transaction that has acquired
+method-group-specific locks but is blocked during an attempt to upgrade to
+being a serial transaction. See below for details.
+
+@item Serial transactions can acquire method-group-specific locks
because there
+will be no other active nor serial transaction.
+
+@end itemize
+
+There is no single rule for per-method-group blocking because this
depends on
+when a TM method might acquire locks. If no active transaction can
upgrade to
+being a serial transaction after it has acquired per-method-group locks
(e.g.,
+when those locks are only acquired during an attempt to commit), then
the TM
+method does not need to consider a potential deadlock due to serial mode.
+
+If there can be upgrades to serial mode after the acquisition of
+per-method-group locks, then TM methods need to avoid those deadlocks:
+@itemize @bullet
+@item When upgrading to a serial transaction, after acquiring exclusive
rights
+to the serial lock but before waiting for concurrent active transactions to
+finish (@pxref{serial-lock-impl,,Serial lock implementation} for details),
+we have to wake up all active transactions waiting on the upgrader's
+per-method-group locks.
+@item Active transactions blocking on per-method-group locks need to
check the
+serial lock and abort if there is a pending serial transaction.
+@item Lost wake-ups have to be prevented (e.g., by changing a bit in each
+per-method-group lock before doing the wake-up, and only blocking on
this lock
+using a futex if this bit is not group).
+@end itemize
+
+@strong{TODO}: Can reuse serial lock for gl-*? And if we can, does it make
+sense to introduce further complexity in the serial lock? For gl-*, we can
+really only avoid an abort if we do -wb and -vbv.
+
+
+@subsection Serial lock implementation
+@anchor{serial-lock-impl}
+
+The serial lock implementation is optimized towards assuming that serial
+transactions are infrequent and not the common case. However, the
performance
+of entering serial mode can matter because when only few transactions
are run
+concurrently or if there are few threads, then it can be efficient to run
+transactions serially.
+
+The serial lock is similar to a multi-reader-single-writer lock in that
there
+can be several active transactions but only one serial transaction.
However,
+we do want to avoid contention (in the lock implementation) between active
+transactions, so we split up the reader side of the lock into
per-transaction
+flags that are true iff the transaction is active. The exclusive writer
side
+remains a shared single flag, which is acquired using a CAS, for example.
+On the fast-path, the serial lock then works similar to Dekker's
algorithm but
+with several reader flags that a serial transaction would have to check.
+A serial transaction thus requires a list of all threads with potentially
+active transactions; we can use the serial lock itself to protect this list
+(i.e., only threads that have acquired the serial lock can modify this
list).
+
+We want starvation-freedom for the serial lock to allow for using it to
ensure
+progress for potentially starved transactions (@pxref{progress-guarantees,,
+Progress Guarantees} for details). However, this is currently not
enforced by
+the implementation of the serial lock.
+
+Here is pseudo-code for the read/write fast paths of acquiring the serial
+lock (read-to-write upgrade is similar to write_lock:
+@example
+// read_lock:
+tx->shared_state |= active;
+__sync_synchronize(); // or STLD membar, or C++0x seq-cst fence
+while (!serial_lock.exclusive)
+ if (spinning_for_too_long) goto slowpath;
+
+// write_lock:
+if (CAS(&serial_lock.exclusive, 0, this) != 0)
+ goto slowpath; // writer-writer contention
+// need a membar here, but CAS already has full membar semantics
+bool need_blocking = false;
+for (t: all txns)
+ @{
+ for (;t->shared_state & active;)
+ if (spinning_for_too_long) @{ need_blocking = true; break; @}
+ @}
+if (need_blocking) goto slowpath;
+@end example
+
+Releasing a lock in this spin-lock version then just consists of resetting
+@code{tx->shared_state} to inactive or clearing
@code{serial_lock.exclusive}.
+
+However, we can't rely on a pure spinlock because we need to get the OS
+involved at some time (e.g., when there are more threads than CPUs to
run on).
+Therefore, the real implementation falls back to a blocking slow path,
either
+based on pthread mutexes or Linux futexes.
+
+
+@subsection Reentrancy
+
+libitm has to consider the following cases of reentrancy:
+@itemize @bullet
+
+@item Transaction calls unsafe code that starts a new transaction: The
outer
+transaction will become a serial transaction before executing unsafe code.
+Therefore, nesting within serial transactions must work, even if the nested
+transaction is called from within uninstrumented code.
+
+@item Transaction calls either a transactional wrapper or safe code,
which in
+turn starts a new transaction: It is not yet defined in the specification
+whether this is allowed. Thus, it is undefined whether libitm supports
this.
+
+@item Code that starts new transactions might be called from within any
part
+of libitm: This kind of reentrancy would likely be rather complex and can
+probably be avoided. Therefore, it is not supported.
+
+@end itemize
+
+@subsection Privatization safety
+
+Privatization safety is ensured by libitm using a quiescence-based
approach.
+Basically, a privatizing transaction waits until all concurrent active
+transactions will either have finished (are not active anymore) or
operate on
+a sufficiently recent snapshot to not access the privatized data
anymore. This
+happens after the privatizing transaction has stopped being an active
+transaction, so waiting for quiescence does not contribute to deadlocks.
+
+In method groups that need to ensure publication safety explicitly, active
+transactions maintain a flag or timestamp in the public/shared part of the
+transaction descriptor. Before blocking, privatizers need to let the other
+transactions know that they should wake up the privatizer.
+
+@strong{TODO} Ho to implement the waiters? Should those flags be
+per-transaction or at a central place? We want to avoid one wake/wait call
+per active transactions, so we might want to use either a tree or combining
+to reduce the syscall overhead, or rather spin for a long amount of time
+instead of doing blocking. Also, it would be good if only the last
transaction
+that the privatizer waits for would do the wake-up.
+
+@subsection Progress guarantees
+@anchor{progress-guarantees}
+
+Transactions that do not make progress when using the current TM method
will
+eventually try to execute in serial mode. Thus, the serial lock's progress
+guarantees determine the progress guarantees of the whole TM.
Obviously, we at
+least need deadlock-freedom for the serial lock, but it would also be
good to
+provide starvation-freedom (informally, all threads will finish executing a
+transaction eventually iff they get enough cycles).
+
+However, the scheduling of transactions (e.g., thread scheduling by the OS)
+also affects the handling of progress guarantees by the TM. First, the TM
+can only guarantee deadlock-freedom if threads do not get stopped.
Likewise,
+low-priority threads can starve if they do not get scheduled when other
+high-priority threads get those cycles instead.
+
+If all threads get scheduled eventually, correct lock implementations will
+provide deadlock-freedom, but might not provide starvation-freedom. We can
+either enforce the latter in the TM's lock implementation, or assume that
+the scheduling is sufficiently random to yield a probabilistic
guarantee that
+no thread will starve (because eventually, a transaction will encounter a
+scheduling that will allow it to run). This can indeed work well in
practice
+but is not necessarily guaranteed to work (e.g., simple spin locks can be
+pretty efficient).
+
+Because enforcing stronger progress guarantees in the TM has a higher
runtime
+overhead, we focus on deadlock-freedom right now and assume that the
threads
+will get scheduled eventually by the OS (but don't consider threads with
+different priorities). We should support starvation-freedom for serial
+transactions in the future. Everything beyond that is highly related to
proper
+contention management across all of the TM (including with TM method to
+choose), and is future work.
+
+@strong{TODO} Handling thread priorities: We want to avoid priority
inversion
+but it's unclear how often that actually matters in practice. Workloads
that
+have threads with different priorities will likely also require lower
latency
+or higher throughput for high-priority threads. Therefore, it probably
makes
+not that much sense (except for eventual progress guarantees) to use
+priority inheritance until the TM has priority-aware contention management.
+
+
+@c ---------------------------------------------------------------------
+@c GNU General Public License
+@c ---------------------------------------------------------------------
+
+@include gpl.texi
+
+
+
+@c ---------------------------------------------------------------------
+@c GNU Free Documentation License
+@c ---------------------------------------------------------------------
+
+@include fdl.texi
+
+
+
+@c ---------------------------------------------------------------------
+@c Funding Free Software
+@c ---------------------------------------------------------------------
+
+@include funding.texi
+
+@c ---------------------------------------------------------------------
+@c Index
+@c ---------------------------------------------------------------------
+
+@node Index
+@unnumbered Index
+
+@printindex cp
+
+@bye
Index: libitm/containers.h
===================================================================
--- libitm/containers.h (.../trunk) (revision 0)
+++ libitm/containers.h (.../branches/transactional-memory) (revision
180773)
@@ -0,0 +1,108 @@
+/* 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"
+
+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 (unlikely(m_size == m_capacity)) resize_noinline();
+ return &entries[m_size++];
+ }
+
+ iterator pop() {
+ if (likely(m_size > 0))
+ {
+ m_size--;
+ return entries + m_size;
+ }
+ else return 0;
+ }
+};
+
+} // namespace GTM
+
+#endif // LIBITM_CONTAINERS_H
Index: libitm/libitm.map
===================================================================
--- libitm/libitm.map (.../trunk) (revision 0)
+++ libitm/libitm.map (.../branches/transactional-memory) (revision 180773)
@@ -0,0 +1,185 @@
+LIBITM_1.0 {
+ global:
+ _ITM_abortTransaction;
+ _ITM_addUserCommitAction;
+ _ITM_addUserUndoAction;
+ _ITM_beginTransaction;
+ _ITM_changeTransactionMode;
+ _ITM_commitTransaction;
+ _ITM_commitTransactionEH;
+ _ITM_error;
+ _ITM_getThreadnum;
+ _ITM_getTransactionId;
+ _ITM_inTransaction;
+ _ITM_libraryVersion;
+ _ITM_versionCompatible;
+
+ _ITM_registerTMCloneTable;
+ _ITM_deregisterTMCloneTable;
+ _ITM_getTMCloneOrIrrevocable;
+ _ITM_getTMCloneSafe;
+
+ _ITM_LB;
+ _ITM_LCD;
+ _ITM_LCE;
+ _ITM_LCF;
+ _ITM_LD;
+ _ITM_LE;
+ _ITM_LF;
+ _ITM_LM128;
+ _ITM_LM256;
+ _ITM_LM64;
+ _ITM_LU1;
+ _ITM_LU2;
+ _ITM_LU4;
+ _ITM_LU8;
+
+ _ITM_RCD;
+ _ITM_RCE;
+ _ITM_RCF;
+ _ITM_RD;
+ _ITM_RE;
+ _ITM_RF;
+ _ITM_RM128;
+ _ITM_RM256;
+ _ITM_RM64;
+ _ITM_RU1;
+ _ITM_RU2;
+ _ITM_RU4;
+ _ITM_RU8;
+ _ITM_RaRCD;
+ _ITM_RaRCE;
+ _ITM_RaRCF;
+ _ITM_RaRD;
+ _ITM_RaRE;
+ _ITM_RaRF;
+ _ITM_RaRM128;
+ _ITM_RaRM256;
+ _ITM_RaRM64;
+ _ITM_RaRU1;
+ _ITM_RaRU2;
+ _ITM_RaRU4;
+ _ITM_RaRU8;
+ _ITM_RaWCD;
+ _ITM_RaWCE;
+ _ITM_RaWCF;
+ _ITM_RaWD;
+ _ITM_RaWE;
+ _ITM_RaWF;
+ _ITM_RaWM128;
+ _ITM_RaWM256;
+ _ITM_RaWM64;
+ _ITM_RaWU1;
+ _ITM_RaWU2;
+ _ITM_RaWU4;
+ _ITM_RaWU8;
+ _ITM_RfWCD;
+ _ITM_RfWCE;
+ _ITM_RfWCF;
+ _ITM_RfWD;
+ _ITM_RfWE;
+ _ITM_RfWF;
+ _ITM_RfWM128;
+ _ITM_RfWM256;
+ _ITM_RfWM64;
+ _ITM_RfWU1;
+ _ITM_RfWU2;
+ _ITM_RfWU4;
+ _ITM_RfWU8;
+
+ _ITM_WCD;
+ _ITM_WCE;
+ _ITM_WCF;
+ _ITM_WD;
+ _ITM_WE;
+ _ITM_WF;
+ _ITM_WM128;
+ _ITM_WM256;
+ _ITM_WM64;
+ _ITM_WU1;
+ _ITM_WU2;
+ _ITM_WU4;
+ _ITM_WU8;
+ _ITM_WaRCD;
+ _ITM_WaRCE;
+ _ITM_WaRCF;
+ _ITM_WaRD;
+ _ITM_WaRE;
+ _ITM_WaRF;
+ _ITM_WaRM128;
+ _ITM_WaRM256;
+ _ITM_WaRM64;
+ _ITM_WaRU1;
+ _ITM_WaRU2;
+ _ITM_WaRU4;
+ _ITM_WaRU8;
+ _ITM_WaWCD;
+ _ITM_WaWCE;
+ _ITM_WaWCF;
+ _ITM_WaWD;
+ _ITM_WaWE;
+ _ITM_WaWF;
+ _ITM_WaWM128;
+ _ITM_WaWM256;
+ _ITM_WaWM64;
+ _ITM_WaWU1;
+ _ITM_WaWU2;
+ _ITM_WaWU4;
+ _ITM_WaWU8;
+
+ _ITM_memcpyRnWt;
+ _ITM_memcpyRnWtaR;
+ _ITM_memcpyRnWtaW;
+ _ITM_memcpyRtWn;
+ _ITM_memcpyRtWt;
+ _ITM_memcpyRtWtaR;
+ _ITM_memcpyRtWtaW;
+ _ITM_memcpyRtaRWn;
+ _ITM_memcpyRtaRWt;
+ _ITM_memcpyRtaRWtaR;
+ _ITM_memcpyRtaRWtaW;
+ _ITM_memcpyRtaWWn;
+ _ITM_memcpyRtaWWt;
+ _ITM_memcpyRtaWWtaR;
+ _ITM_memcpyRtaWWtaW;
+ _ITM_memmoveRnWt;
+ _ITM_memmoveRnWtaR;
+ _ITM_memmoveRnWtaW;
+ _ITM_memmoveRtWn;
+ _ITM_memmoveRtWt;
+ _ITM_memmoveRtWtaR;
+ _ITM_memmoveRtWtaW;
+ _ITM_memmoveRtaRWn;
+ _ITM_memmoveRtaRWt;
+ _ITM_memmoveRtaRWtaR;
+ _ITM_memmoveRtaRWtaW;
+ _ITM_memmoveRtaWWn;
+ _ITM_memmoveRtaWWt;
+ _ITM_memmoveRtaWWtaR;
+ _ITM_memmoveRtaWWtaW;
+ _ITM_memsetW;
+ _ITM_memsetWaR;
+ _ITM_memsetWaW;
+
+ _ITM_malloc;
+ _ITM_calloc;
+ _ITM_free;
+ _ITM_dropReferences;
+
+ _ZGTtnw?;
+ _ZGTtna?;
+ _ZGTtdlPv;
+ _ZGTtdaPv;
+ _ZGTtnw?RKSt9nothrow_t;
+ _ZGTtna?RKSt9nothrow_t;
+ _ZGTtdlPvRKSt9nothrow_t;
+ _ZGTtdaPvRKSt9nothrow_t;
+
+ _ITM_cxa_allocate_exception;
+ _ITM_cxa_begin_catch;
+ _ITM_cxa_end_catch;
+ _ITM_cxa_throw;
+
+ local:
+ *;
+};
More information about the Gcc-patches
mailing list