|
|
Boost-Commit : |
Subject: [Boost-commit] svn:boost r56866 - in sandbox/stm/branches/vbe: boost/stm boost/stm/detail boost/stm/tx libs/stm/doc libs/stm/test
From: vicente.botet_at_[hidden]
Date: 2009-10-15 09:14:49
Author: viboes
Date: 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
New Revision: 56866
URL: http://svn.boost.org/trac/boost/changeset/56866
Log:
TBoost.STM vbe:
* Fixed race condition found on member initialization access to shared maps which could be modified by threads upon entry and exit.
The entry condition should not have caused errors because of the assumption that no transactions were previously started prior to all threads initializing. However, the thread termination could have caused crashes.
Now a light_auto_lock object is initialized in the member initialization which prevents both thread entry/exit and transaction construction from occurring at the same time. This blocks the race condition of simultaneous, shared access to the maps.
* In addition, added the new code to the contention manager which now makes a single virtual call listing a committing transaction's conflicts with all other transactions. Previously, it would make a virtual call per transactional conflict. If the conflicts were high, the call overhead could cause performance degradation since a committing transaction is a critical serialization point.
* addition of throw and nothrow new operators
Text files modified:
sandbox/stm/branches/vbe/boost/stm/contention_manager.hpp | 83 ++++++++++++++++++++++++++++++++++++++++
sandbox/stm/branches/vbe/boost/stm/detail/transaction_impl.hpp | 7 +-
sandbox/stm/branches/vbe/boost/stm/language_like.hpp | 49 +++++++++++++++++++---
sandbox/stm/branches/vbe/boost/stm/synchro.hpp | 45 +++++++++++++++++++++
sandbox/stm/branches/vbe/boost/stm/transaction.hpp | 79 +++++++++++++++++++++++++++++++++++++
sandbox/stm/branches/vbe/boost/stm/transaction_object.hpp | 27 ++++++++++--
sandbox/stm/branches/vbe/boost/stm/tx/pointer.hpp | 1
sandbox/stm/branches/vbe/libs/stm/doc/appendices.qbk | 8 ++
sandbox/stm/branches/vbe/libs/stm/doc/references.qbk | 17 ++++++++
sandbox/stm/branches/vbe/libs/stm/test/Jamfile.v2 | 4
10 files changed, 297 insertions(+), 23 deletions(-)
Modified: sandbox/stm/branches/vbe/boost/stm/contention_manager.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/contention_manager.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/contention_manager.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -142,6 +142,89 @@
//return lhs.writes() + lhs.reads() >= rhs.writes() + rhs.reads();
}
+ virtual bool permission_to_abort
+ (transaction const &lhs,
+ std::list<transaction*> &rhs)
+ {
+#ifdef JUST_PRIORITY
+ int setSize = (lhs.writes() * lhs.priority()) +
+ (lhs.reads() * lhs.priority());
+ double abortSetSize = 0;
+ double abortPriority = 0;
+ double decrementing = 1.0;
+
+ double highestPriority = 0;
+
+ bool hasLargestReadSet = true;
+
+ for (std::list<core::transaction*>::iterator iter = rhs.begin();
+ iter != rhs.end(); ++iter)
+ {
+ if ((*iter)->priority() > highestPriority)
+ {
+ highestPriority = (*iter)->priority();
+ }
+
+ if ((*iter)->reads() > lhs.reads()) hasLargestReadSet = false;
+ if ((*iter)->writes() > 0) return true;
+
+ abortSetSize += (double)(*iter)->reads() / decrementing;
+ abortPriority += (double)(*iter)->priority() / decrementing;
+ decrementing += 0.5;
+ }
+
+ if (lhs.priority() >= highestPriority) return true;
+
+ if (hasLargestReadSet) return true;
+
+ if (setSize >= abortPriority + abortSetSize)
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+
+#else
+ double setSize = (lhs.writes() * lhs.priority()) +
+ (lhs.reads() * lhs.priority());
+ double abortSetSize = 0;
+ double abortPriority = 0;
+ bool hasLargestReadSet = true;
+
+ int mem = lhs.reads() + (lhs.writes() * 10);
+
+ double decrementing = 1.0;
+ for (std::list<transaction*>::iterator iter = rhs.begin();
+ iter != rhs.end(); ++iter)
+ {
+ if ((*iter)->reads() > mem) hasLargestReadSet = false;
+
+ if ((*iter)->writes() > 0) return true;
+
+ if (lhs.reads() < (*iter)->reads() / 8 &&
+ lhs.priority() * 100 < (*iter)->priority()) return false;
+
+ abortSetSize += (double)(*iter)->reads() / decrementing;
+ abortPriority += (double)(*iter)->priority() / decrementing;
+ decrementing += 0.5;
+ }
+
+ if (hasLargestReadSet) return true;
+
+ if (setSize >=
+ (abortPriority / setSize) + (abortSetSize / setSize))
+ {
+ return true;
+ }
+ else
+ {
+ return false;
+ }
+#endif
+ }
+
virtual bool allow_lock_to_abort_tx
(int const & lockWaitTime, int const &lockAborted,
bool txTryingToAbortIsIrrevocable, transaction const &rhs)
Modified: sandbox/stm/branches/vbe/boost/stm/detail/transaction_impl.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/detail/transaction_impl.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/detail/transaction_impl.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -383,6 +383,9 @@
//--------------------------------------------------------------------------
inline transaction::transaction() :
threadId_(THREAD_ID),
+ //transactionMutexLocker_(),
+ auto_general_lock_(general_lock()),
+
#if USE_SINGLE_THREAD_CONTEXT_MAP
////////////////////////////////////////
context_(*tss_context_map_.find(threadId_)->second),
@@ -431,7 +434,6 @@
#endif
transactionsRef_(transactions(threadId_)),
-
////////////////////////////////////////
#else
////////////////////////////////////////
@@ -466,10 +468,9 @@
obtainedLocksRef_(*threadObtainedLocks_.find(threadId_)->second),
currentlyLockedLocksRef_(*threadCurrentlyLockedLocks_.find(threadId_)->second),
#endif
-
+////////////////////////////////////////
transactionsRef_(transactions(threadId_)),
-////////////////////////////////////////
#endif
hasMutex_(0), priority_(0),
Modified: sandbox/stm/branches/vbe/boost/stm/language_like.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/language_like.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/language_like.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -46,7 +46,8 @@
#define BOOST_STM_USE_ATOMIC(TX) \
BOOST_STM_COMPILER_DONT_DESTROY_FOR_VARIABLES_WORKAROUND \
for (boost::stm::transaction TX; \
- !TX.committed() && TX.restart(); \
+ ! TX.committed() \
+ && TX.restart(); \
TX.end())
//---------------------------------------------------------------------------
@@ -111,13 +112,13 @@
//---------------------------------------------------------------------------
#define BOOST_STM_TX_ABORT_ON_EXCEPTION(TX, E) \
- catch (E&) {(TX).abort();}
+ catch (E&) {(TX).force_to_abort();}
//---------------------------------------------------------------------------
// Catch any exception and abort the transaction TX
//---------------------------------------------------------------------------
-#define BOOST_STM_TX_ABORT_ANY(TX) \
- catch (...) {(TX).abort();}
+#define BOOST_STM_TX_ABORT_ON_ANY_EXCEPTION(TX) \
+ catch (...) {(TX).force_to_abort();}
//---------------------------------------------------------------------------
// helper function to implement BOOST_STM_RETURN
@@ -167,7 +168,7 @@
//---------------------------------------------------------------------------
// aborts the transaction TX
//---------------------------------------------------------------------------
-#define BOOST_STM_TX_ABORT(TX) TX.abort()
+#define BOOST_STM_TX_ABORT(TX) (TX).force_to_abort()
//---------------------------------------------------------------------------
// aborts the current transaction
@@ -179,14 +180,46 @@
//---------------------------------------------------------------------------
// aborts the transaction TX
//---------------------------------------------------------------------------
-#define BOOST_STM_TX_ABORT_ALL(TX) TX.abort()
+#define BOOST_STM_TX_ABORT_OUTER(TX) (TX).force_to_abort()
//---------------------------------------------------------------------------
// aborts the current transaction
//---------------------------------------------------------------------------
-#define BOOST_STM_ABORT_ALL \
+#define BOOST_STM_ABORT_OUTER \
if (boost::stm::current_transaction()==0) ; \
- else BOOST_STM_ABORT_ALL(*boost::stm::current_transaction())
+ else BOOST_STM_TX_ABORT_OUTER(*boost::stm::current_transaction())
+
+
+//---------------------------------------------------------------------------
+// throw an exception
+//---------------------------------------------------------------------------
+#define BOOST_STM_TX_THROW(TX, EXCEPTION) throw (EXCEPTION)
+
+#define BOOST_STM_THROW(EXCEPTION) throw (EXCEPTION)
+
+//---------------------------------------------------------------------------
+// aborts the transaction TX and throw exception
+//---------------------------------------------------------------------------
+#define BOOST_STM_TX_ABORT_AND_THROW(TX, EXCEPTION) if ((TX).force_to_abort()) throw (EXCEPTION)
+
+//---------------------------------------------------------------------------
+// aborts the current transaction
+//---------------------------------------------------------------------------
+#define BOOST_STM_ABORT_AND_THROW(EXCEPTION) \
+ if (boost::stm::current_transaction()==0) ; \
+ else BOOST_STM_TX_ABORT_AND_THROW(*boost::stm::current_transaction(), EXCEPTION)
+
+//---------------------------------------------------------------------------
+// aborts the transaction TX and throw exception
+//---------------------------------------------------------------------------
+#define BOOST_STM_TX_ABORT_OUTER_AND_THROW(TX, EXCEPTION) if ((TX).force_to_abort()) throw (EXCEPTION)
+
+//---------------------------------------------------------------------------
+// aborts the current transaction
+//---------------------------------------------------------------------------
+#define BOOST_STM_ABORT_OUTER_AND_THROW(EXCEPTION) \
+ if (boost::stm::current_transaction()==0) ; \
+ else BOOST_STM_TX_ABORT_OUTER_AND_THROW(*boost::stm::current_transaction(), EXCEPTION)
//---------------------------------------------------------------------------
// Memory management
Modified: sandbox/stm/branches/vbe/boost/stm/synchro.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/synchro.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/synchro.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -137,6 +137,51 @@
//}
};
+//-----------------------------------------------------------------------------
+//-----------------------------------------------------------------------------
+
+class light_auto_lock
+{
+public:
+
+ light_auto_lock(Mutex &mutex) : lock_(NULL)
+ {
+ do_auto_lock(&mutex);
+ }
+
+ light_auto_lock(Mutex *mutex) : lock_(NULL)
+ {
+ do_auto_lock(mutex);
+ }
+
+ ~light_auto_lock() { do_auto_unlock(); }
+
+ bool has_lock() { return hasLock_; }
+
+ void release_lock() { do_auto_unlock(); }
+
+private:
+
+ void do_auto_lock(Mutex *mutex)
+ {
+ lock_ = mutex;
+ pthread_mutex_lock(mutex);
+ hasLock_ = true;
+ }
+
+ void do_auto_unlock()
+ {
+ if (hasLock_)
+ {
+ hasLock_ = false;
+ pthread_mutex_unlock(lock_);
+ }
+ }
+
+ bool hasLock_;
+ Mutex *lock_;
+};
+
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
Modified: sandbox/stm/branches/vbe/boost/stm/transaction.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/transaction.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/transaction.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -101,6 +101,13 @@
typedef std::pair<base_transaction_object*, base_transaction_object*> tx_pair;
+ template <typename MUTEX, MUTEX& mtx>
+ struct locker {
+ inline locker();
+ inline ~locker();
+ inline void unlock();
+ };
+
///////////////////////////////////////////////////////////////////////////////
// transaction Class
///////////////////////////////////////////////////////////////////////////////
@@ -710,6 +717,22 @@
delete_memory(*in);
}
+ template <typename T>
+ inline void delete_tx_array(T *in) {
+ if (direct_updating())
+ {
+#if PERFORMING_VALIDATION
+ throw "direct updating not implemented for validation yet";
+#else
+ direct_delete_tx_array(in);
+#endif
+ }
+ else
+ {
+ deferred_delete_tx_array(in);
+ }
+ }
+
//--------------------------------------------------------------------------
// allocation of new memory behaves the same for both deferred and direct
// transaction implementations
@@ -1039,6 +1062,40 @@
deletedMemoryList().push_back(detail::make(in));
}
}
+
+ //--------------------------------------------------------------------------
+ template <typename T>
+ void direct_delete_tx_array(T *in)
+ {
+ if (in.transaction_thread() == threadId_)
+ {
+ deletedMemoryList().push_back(detail::make(in));
+ return;
+ }
+
+ //-----------------------------------------------------------------------
+ // if we're here this item isn't in our writeList - get the global lock
+ // and see if anyone else is writing to it. if not, we add the item to
+ // our write list and our deletedList
+ //-----------------------------------------------------------------------
+ lock(&transactionMutex_);
+
+ if (in.transaction_thread() != kInvalidThread)
+ {
+ unlock(&transactionMutex_);
+ cm_abort_on_write(*this, (base_transaction_object&)(in));
+ }
+ else
+ {
+ in.transaction_thread(threadId_);
+ unlock(&transactionMutex_);
+ // is this really necessary? in the deferred case it is, but in direct it
+ // doesn't actually save any time for anything
+ //writeList()[(base_transaction_object*)&in] = 0;
+
+ deletedMemoryList().push_back(detail::make(in));
+ }
+ }
#endif
@@ -1272,7 +1329,7 @@
delete *i;
}
#endif
- deletedMemoryList().clear();
+ deletedMemoryList().clear();
}
void directAbortTransactionNewMemory() throw() { deferredAbortTransactionNewMemory(); }
void deferredAbortTransactionNewMemory() throw();
@@ -1440,6 +1497,9 @@
//--------------------------------------------------------------------------
size_t threadId_;
+ light_auto_lock auto_general_lock_;
+ //locker<Mutex, transactionMutex_> transactionMutexLocker_;
+
//--------------------------------------------------------------------------
// ******** WARNING ******** MOVING threadId_ WILL BREAK TRANSACTION.
// threadId_ MUST ALWAYS THE FIRST MEMBER OF THIS CLASS. THE MEMBER
@@ -1609,6 +1669,7 @@
public:
inline TransactionsStack& transactions() {return transactionsRef_;}
inline static TransactionsStack &transactions(thread_id_t id) {
+ light_auto_lock auto_general_lock_(general_lock());
return *threadTransactionsStack_.find(id)->second;
}
private:
@@ -1775,6 +1836,7 @@
public:
inline TransactionsStack& transactions() {return transactionsRef_;}
inline static TransactionsStack &transactions(thread_id_t id) {
+ light_auto_lock auto_general_lock_(general_lock());
tss_context_map_type::iterator i = tss_context_map_.find(id);
return i->second->transactions_;
}
@@ -1920,11 +1982,12 @@
inline static MutexSet ¤tlyLockedLocksRef(thread_id_t id) {return *threadCurrentlyLockedLocks_.find(id)->second;}
#endif
- //static ThreadTransactionsStack threadTransactionsStack_;
+ static ThreadTransactionsStack threadTransactionsStack_;
TransactionsStack& transactionsRef_;
public:
inline TransactionsStack& transactions() {return transactionsRef_;}
inline static TransactionsStack &transactions(thread_id_t id) {
+ light_auto_lock auto_general_lock_(general_lock());
return *threadTransactionsStack_.find(id)->second;
}
private:
@@ -1956,6 +2019,18 @@
inline transaction* current_transaction() {return transaction::current_transaction();}
+template <typename MUTEX, MUTEX& mtx>
+locker<MUTEX,mtx>::locker() {
+ boost::stm::lock(mtx);
+}
+template <typename MUTEX, MUTEX& mtx>
+locker<MUTEX,mtx>::~locker() {}
+
+template <typename MUTEX, MUTEX& mtx>
+void locker<MUTEX,mtx>::unlock() {
+ boost::stm::unlock(mtx);
+}
+
template <class T> T* cache_allocate(transaction* t) {
#if defined(BOOST_STM_CACHE_USE_MEMORY_MANAGER) && defined (USE_STM_MEMORY_MANAGER)
return reinterpret_cast<T*>(T::retrieve_mem(sizeof(T)));
Modified: sandbox/stm/branches/vbe/boost/stm/transaction_object.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/transaction_object.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/transaction_object.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -105,31 +105,48 @@
return boost::stm::cache_allocate<Derived>(t);
}
#if USE_STM_MEMORY_MANAGER
- void* operator new(size_t size) throw ()
+ void* operator new(size_t size, const nothrow_t&) throw ()
{
return retrieve_mem(size);
}
+ void* operator new(size_t size) throw (std::bad_alloc)
+ {
+ void* ptr= retrieve_mem(size);
+ if (ptr==0) throw std::bad_alloc;
+ return ptr;
+ }
- void operator delete(void* mem)
+ void operator delete(void* mem) throw ()
{
static Derived elem;
static size_t elemSize = sizeof(elem);
return_mem(mem, elemSize);
}
#else
- void* operator new(size_t size) throw ()
+ void* operator new(size_t size, const nothrow_t& nt) throw ()
+ {
+ return ::operator new(size, nt);
+ }
+ void* operator new(size_t size) throw (std::bad_alloc)
{
return ::operator new(size);
}
#endif
#else
#if USE_STM_MEMORY_MANAGER
- void* operator new(size_t size) throw ()
+ void* operator new(size_t size, const nothrow_t&) throw ()
{
return retrieve_mem(size);
}
- void operator delete(void* mem)
+ void* operator new(size_t size) throw (std::bad_alloc)
+ {
+ void* ptr= retrieve_mem(size);
+ if (ptr==0) throw std::bad_alloc;
+ return ptr;
+ }
+
+ void operator delete(void* mem) throw ()
{
static Derived elem;
static size_t elemSize = sizeof(elem);
Modified: sandbox/stm/branches/vbe/boost/stm/tx/pointer.hpp
==============================================================================
--- sandbox/stm/branches/vbe/boost/stm/tx/pointer.hpp (original)
+++ sandbox/stm/branches/vbe/boost/stm/tx/pointer.hpp 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -17,7 +17,6 @@
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
#include <boost/stm/transaction.hpp>
-#include <boost/stm/non_tx/detail/cache_map.hpp>
//-----------------------------------------------------------------------------
//-----------------------------------------------------------------------------
Modified: sandbox/stm/branches/vbe/libs/stm/doc/appendices.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/appendices.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/appendices.qbk 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -35,6 +35,7 @@
* [*DONE] Adding transactional smart pointers.
* Allows to have non transactional_object participating on transactions (separate the information related to a transactional object from the object itself and add two pointers to transactional_object_cache one to the object itself and the other to the transactional_object.
* [*DONE] Managing Movable and non CopyConstructible types.
+* Replace auto_lock by boost::stm::synchro::unique_locker and redefine language-like macros.
[heading Boostifying STM]
@@ -48,8 +49,7 @@
* Replace THREAD_ID by boost::thread_id
* [*DONE] Provide a unique array/tuple locker (Boost.Synchro)
* Replace var_auto_lock by boost::synchro::unique_array_locker
-* Replace auto_lock by boost::synchro::unique_locker and redefine use_lock macros
-* use lock_guard when lock/unlock
+* Use boost::lock_guard when lock/unlock
* Adapt the pool to Boost.Pool
* [*DONE] Provide a thread specific shared pointer (Boost.Interthreads)
* [*DONE] Provide a transparent initialization (Boost.Interthreads)
@@ -117,6 +117,10 @@
* Mixing STM updating policies.
* Mixing STM consistency checking.
+* Providing Closed Nested transaction that are not flat.
+Currently __Boost_STM__ provides closed nested transactions which are flat, i.e. all the nested transactions are flatten on the outer transaction of the thread.
+* Suspend/resume transactions
+* Add explicit outer transaction (those that can not be nested in aother transactions, i.e. root transactions).
[endsect]
[endsect]
Modified: sandbox/stm/branches/vbe/libs/stm/doc/references.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/references.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/references.qbk 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -73,6 +73,23 @@
]
]
+C++ Language based approaches.
+
+[variablelist
+[
+ [ [@http://www-949.ibm.com/software/rational/cafe/servlet/JiveServlet/download/3222-1-2389/C++-transactional-constructs-1.0.pdf [*Draft Specification of Transactional Language Constructs for C++]]]
+ [Transactional Memory Specification Drafting Group
+ ['Version: 1.0 - August 4, 2009] ]
+]
+
+[
+ [ [@http://www.cs.rochester.edu/meetings/TRANSACT07/papers/crowl.pdf [*Integrating Transactional Memory into C++]]]
+ [Lawrence Crowl, Yossi Lev, Victor Luchangco, Mark Moir and Dan Nussbaum -
+ ['TRANSACT 2007]]
+]
+]
+
+
Check for the last updates.
[variablelist
Modified: sandbox/stm/branches/vbe/libs/stm/test/Jamfile.v2
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/test/Jamfile.v2 (original)
+++ sandbox/stm/branches/vbe/libs/stm/test/Jamfile.v2 2009-10-15 09:14:48 EDT (Thu, 15 Oct 2009)
@@ -44,9 +44,9 @@
:
[ run stm.cpp testatom.cpp pointer_test.cpp smart.cpp globalIntArr.cpp testHashMapAndLinkedListsWithLocks.cpp irrevocableInt.cpp testHashMapWithLocks.cpp isolatedComposedIntLockInTx.cpp testInt.cpp isolatedComposedIntLockInTx2.cpp testLL_latm.cpp isolatedInt.cpp testLinkedList.cpp isolatedIntLockInTx.cpp testLinkedListWithLocks.cpp litExample.cpp testPerson.cpp lotExample.cpp testRBTree.cpp transferFun.cpp nestedTxs.cpp txLinearLock.cpp testHT_latm.cpp usingLockTx.cpp testHashMap.cpp ]
[ run ../example/bank.cpp ]
- [ run ../example/list.cpp ]
+ #[ run ../example/list.cpp ]
[ run ../example/counter.cpp ]
[ run ../example/numeric.cpp ]
[ run ../example/counter_ptr.cpp ]
- [ run ../example/non_tx_counter.cpp ]
+ #[ run ../example/non_tx_counter.cpp ]
;
Boost-Commit list run by bdawes at acm.org, david.abrahams at rcn.com, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk