diff options
Diffstat (limited to 'libitm/method-wbetl.cc')
| -rw-r--r-- | libitm/method-wbetl.cc | 628 |
1 files changed, 0 insertions, 628 deletions
diff --git a/libitm/method-wbetl.cc b/libitm/method-wbetl.cc deleted file mode 100644 index 093d1c7..0000000 --- a/libitm/method-wbetl.cc +++ /dev/null @@ -1,628 +0,0 @@ -/* 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" - -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 (); -} |