Boost logo

Boost-Commit :

Subject: [Boost-commit] svn:boost r56298 - in sandbox/stm/branches/vbe/libs/stm/doc: . example image reference tutorial
From: vicente.botet_at_[hidden]
Date: 2009-09-18 13:45:56


Author: viboes
Date: 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
New Revision: 56298
URL: http://svn.boost.org/trac/boost/changeset/56298

Log:
TBoost.Stm vbe
* Adding DRAFT documentation

Added:
   sandbox/stm/branches/vbe/libs/stm/doc/example/
   sandbox/stm/branches/vbe/libs/stm/doc/image/
   sandbox/stm/branches/vbe/libs/stm/doc/image/Toward_Boost_STM.jpg (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/
   sandbox/stm/branches/vbe/libs/stm/doc/reference/base_contention_manager.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/base_transaction.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/data_types.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/exceptions.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/language_like.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/smart_pointers.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_bookkeeping.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_object.qbk (contents, props changed)
   sandbox/stm/branches/vbe/libs/stm/doc/tutorial/
Text files modified:
   sandbox/stm/branches/vbe/libs/stm/doc/appendices.qbk | 57 +++-
   sandbox/stm/branches/vbe/libs/stm/doc/getting_started.qbk | 16 +
   sandbox/stm/branches/vbe/libs/stm/doc/implementation.qbk | 32 ++
   sandbox/stm/branches/vbe/libs/stm/doc/installation.qbk | 53 +++-
   sandbox/stm/branches/vbe/libs/stm/doc/introduction.qbk | 38 +++
   sandbox/stm/branches/vbe/libs/stm/doc/overview.qbk | 14 +
   sandbox/stm/branches/vbe/libs/stm/doc/rationale.qbk | 370 +++++++++++++++++++++++++++++++++
   sandbox/stm/branches/vbe/libs/stm/doc/reference.qbk | 17 +
   sandbox/stm/branches/vbe/libs/stm/doc/references.qbk | 62 +++++
   sandbox/stm/branches/vbe/libs/stm/doc/stm.qbk | 15
   sandbox/stm/branches/vbe/libs/stm/doc/tutorial.qbk | 447 +++++++++++++++++++++++++++++++++++++++
   sandbox/stm/branches/vbe/libs/stm/doc/users_guide.qbk | 26 +
   12 files changed, 1100 insertions(+), 47 deletions(-)

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-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -28,49 +28,80 @@
 [section:todo Appendix E: Future plans]
 [/=====================================]
 
-[heading Tasks to do before review]
+[section Tasks to do before review]
 
-[section Boostifying STM]
+[heading Interface]
+
+* [*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.
+
+[heading Boostifying STM]
 
-[heading Porting to Boost]
 * [*DONE] set boost directory architecture
 * [*DONE] name files in lowercase
-* [*DONE] Replace bit_vector by std::bitset or boost::dynamic_bitset (BOOST_STM_BLOOM_FILTER_USE_DYNAMIC_BITSET)
 * [*DONE] Add a config file with all the configuration macros
 * [*DONE] Add a stm file at the boost level including all the STM interfaces
+* [*DONE] Replace bit_vector by std::bitset or boost::dynamic_bitset (BOOST_STM_BLOOM_FILTER_USE_DYNAMIC_BITSET)
 * [*DONE] Replace Sleep by boost::this_thread::sleep
 * [*DONE] Replace pthread_mutex by boost::mutex
 * 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
-* Redifine var_auto_lock
-* Add an scoped guard for transaction::lock/unlock
 * use 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)
+* Replace thread specific access using the thread id by boost:interthreads::thread_specific_shared_ptr
+* Replace the initialization to the library Boost.Interthreads (decorations and decorators)
+* Replace draco_move by boost::move and its emulation
+* Replace vector_set and vector map by the respectives Boost.Container flat_set and flat_map
+* Replace blom_filter by the Boost.BlomFilter blom_filter
+
+[heading Implementation]
 
-[heading Restructure the data]
-* Separate the data that is global, thread local or specific to a transaction.
+* [*DONE] Separate the data that is global, thread specific but shared to other threads using a lock, thread local or specific to a transaction.
+* [*DONE] Define access to these data using functions
 * Separate the interface from the implementation
-* Define access to these data using functions
+* Group all the cache containers (Read,Write,Delete,New) in only one cache in order to improve the lookup performance when using smart pointers.
 
 [heading Tests]
+
 * Add unit tests
 
 [heading Documentation]
+
 * [*DONE] Create the empty files and set the doc generation environement
 * Write the Motivation section
 * Write the Getting started section
+* [*DONE] Write the Installation section
 * Write the Tutorial section
 * Write the Example section
 * Write the Reference section
+* [*DONE] Write the Bibliography section
+* Write the Glossary section
+* Write the Rationale section
+* Write the Implementation notes section
+* Write the Acknowledgements section
 
-[heading Other tasks]
-* Implement a generic blom_filter
-* Replace the user class transactional_object by an internal transactional_object_cache
 
 [endsect]
 
-[heading For later releases]
+[section For later releases]
+
+* Integrate with STM test benchmarks as STAMP or STMBench7.
+* Add close nested transactions.
+* Allows configuration at compile-time and run-time.
+
+[section More recherch needed]
 
+* Mixing STM updating policies.
+* Mixing STM consistency checking.
+
+[endsect]
 [endsect]
 
 [endsect]
+[endsect]
 

Modified: sandbox/stm/branches/vbe/libs/stm/doc/getting_started.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/getting_started.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/getting_started.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -18,6 +18,22 @@
 [section Hello World! ]
 [/=============================]
 
+The below example gives a basic introduction into __Boost_STM_s__ transactional framework and demonstrates __Boost_STM_s__ ACI conformance.
+
+
+ tx_obj<int> counter;
+
+ int increment() {
+ int val = 0;
+ use_atomic(_) {
+ (*counter)++;
+ val = *counter;
+ }
+ return val;
+ }
+
+In the above example, (A) both the write on global_int and the read operations function atomically or neither operations are performed. In addition, (C) the transaction begins and ends in legal memory
+states, meaning global int is guaranteed to be read correctly, preventing thread data races from causing inconsistent results. Lastly, (I) the intermediate state of the incremented global int is isolated until the transaction commits. These three attributes fulfill __Boost_STM_s__ conformance to the ACI principles. The above example also gives a basic introduction into __Boost_STM_s__ transactional framework.
 
 [endsect]
 

Added: sandbox/stm/branches/vbe/libs/stm/doc/image/Toward_Boost_STM.jpg
==============================================================================
Binary file. No diff available.

Modified: sandbox/stm/branches/vbe/libs/stm/doc/implementation.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/implementation.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/implementation.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -8,8 +8,38 @@
 
 [section:implementation Appendix C: Implementation Notes]
 
+[section Why there is a `if (0 == rand()+1) {} else` preceding the for on the atomi macros?]
 
-TBC
+The `if (0 == rand()+1) {} else` expression in the preprocessor atomic macros is used
+to prevent for loop errors in non-standard conforming C++ compilers.
+In these non-compliant compilers, automatic objects constructed
+as index variables for the for loop are leaked out beyond
+the scope of the for loop, incorrectly extending the liveness of
+these variables. In order to correct this behavior, the for loops that
+are not encapsulated within trys are wrapped within if statements.
+The if statements and for loops naturally nest without delineated
+scope (e.g., f, g) allowing programmers to execute single or multiple
+operations based on their preference.
+
+(0 == rand()+1) always returns false and cannot be
+optimized away by an optimizing compiler. By using an always
+false non-optimizable function inside an if statement, a variable
+scope is generated that guarantees automatic objects which are
+placed within these scopes are properly destroyed once the scope
+is exited. These scopes properly terminate variables which would
+otherwise be leaked in non-compliant for loop C++ compilers. The
+proper termination of automatic auto_locks and transactions
+is necessary to release acquired locks, terminate transactions and
+release transactional memory.
+
+[endsect]
+
+[section Cache]
+
+[heading Dispersed]
+[heading Compact]
+
+[endsect]
 
 
 [endsect]

Modified: sandbox/stm/branches/vbe/libs/stm/doc/installation.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/installation.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/installation.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -11,15 +11,26 @@
 [section:install Installing STM]
 [/======================================]
 
+TBoost.STM is currently in an alpha release stage. This means our STM library is downloadable, but is undergoing some fundamental changes. Furthermore, our alpha release of TBoost.STM may exhibit some stability issues. While our internal tests have shown TBoost.STM to be fairly stable, your usage may vary.
+
+TBoost.STM's current alpha download is mainly intended for other researchers who are curious about TBoost.STM's implementation and transactional memory. While we encourage non-TM experts to download the library and explore writing parallel code within its framework, we want such users know the system is in its early stages. As such, your usage of TBoost.STM may reveal some weaknesses or stability issues. Until we are into a fully released version, these issues are to be expected. However, please let us know if you encounter any problems using our library and we will do our best to resolve such issues immediately.
+
+Thank you for considering TBoost.STM and we hope you enjoy exploring transactional memory!
+
 [/=================================]
 [heading Getting Boost.STM]
 [/=================================]
 
-You can get the last stable release of Boost.STM by downloading [^stm.zip] from the
-[@http://www.boost-consulting.com/vault/index.php?directory=Concurrent%20Programming Boost Vault]
+Visit our Toward Boost.Stm [@http://eces.colorado.edu/~gottschl/tboostSTM/index.html home page] be aware of the last news.
+
+You can get the last stable release of from the [@http://eces.colorado.edu/~gottschl/tboostSTM/downloads.html Download page].
+
+[/Boost.STM by downloading [^stm.zip] from the
+[@http://www.boost-consulting.com/vault/index.php?directory=Concurrent%20Programming Boost Vault]]
 
 You can also access the latest (unstable?) state from the [@https://svn.boost.org/svn/boost/sandbox/stm Boost Sandbox].
 
+
 [/=================================]
 [heading Building Boost.STM]
 [/=================================]
@@ -33,26 +44,37 @@
 [heading Requirements]
 [/=========================]
 
-[*Boost.STM] depends on Boost. We have tested it with the Boost version 1.38.x (even if Boost version 1.35.x should works also).
-In particular, [*Boost.STM] depends on:
+
+The POSIX threads (pthreads) library is needed to use TBoost.STM. Pthreads is part of the standard deployment for almost all Unix / Linux flavors, however, it is not standard in Windows. If you are doing Windows development you can find the POSIX threads library at the below link:
+[@http://sourceware.org/pthreads-win32/ POSIX threads (pthreads) for Windows]
 
 
+In order to be more portable [*Boost.STM] is migrating to Boost. You should use either Boost version 1.39.x
+or the version in SVN trunk (even if Boost version 1.35.x should works also).
+In particular, [*Boost.STM] will depends on:
+
 [variablelist
 [
     [[@http://www.boost.org/libs/dynamic_bitset [*Boost.DynamicBitset]]]
     [dynamic_bitsets]
 ]
 [
- [[@http://www.boost.org/libs/blom_filters [*Boost.BlomFilters]]]
- [dynamic_bitsets]
+ [[@http://www.boost.org/libs/thread [*Boost.Thread]] from Anthony Williams]
+ [threads and synchronization primitives]
+]
 ]
+
+In addition Boost.Stm will uses the following libraries on the Boost Sandbox
+
+[variablelist
 [
- [[@http://www.boost.org/libs/synchro [*Boost.Synchro]]]
- [synchronization primitives]
+ [[@https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction#Boost.Synchro [*Boost.Chrono]] from Vicente J. Botet Escriba]
+ [Standard Chrono library]
 ]
+
 [
- [[@http://www.boost.org/libs/thread [*Boost.Thread]]]
- [threads and synchronization primitives]
+ [[@https://svn.boost.org/trac/boost/wiki/LibrariesUnderConstruction#Boost.Synchro [*Boost.Synchro]] from Vicente J. Botet Escriba]
+ [Exception based timed locks synchronization primitives & Language-like Synchronized Block]
 ]
 ]
 
@@ -70,16 +92,21 @@
 
 All functions in the library are thread-unsafe except when noted explicitly.
 
-
 [/=======================]
 [heading Tested compilers]
 [/=======================]
 
+
 Currently, [*Boost.STM] has been tested in the following compilers/platforms:
 
-* GCC 3.4.4 Cygwin
+* Visual Studio 6 - Windows
+[/* GCC 4.4.0 - Cygwin]
+* GCC 3.4.4 - Cygwin
+[/* GCC 4.1.2 - Linux]
+[/* Sun Studio 12 - Solaris]
+[/* Sun Studio 11 - Solaris]
 
-[note Please send any questions, comments and bug reports to boost <at> lists <dot> boost <dot> org.]
+[note Please send any questions, comments and bug reports to boost <at> lists <dot> boost <dot> org]
 
 [endsect]
 

Modified: sandbox/stm/branches/vbe/libs/stm/doc/introduction.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/introduction.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/introduction.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -9,6 +9,44 @@
 [section:intro Introduction]
 
 
+Research in parallel programming has recently seen a flurry of attention.
+Among the active research is a push for high-level languages
+to offer native support for parallel programming primitives. The next version of C++ will incorporate library support
+for threads, while numerous researchers are exploring ways to
+extend C++ to support transactional memory (TM).
+
+A strength of C++ is its support for automatic objects.
+Rather than requiring that parallel primitives be added directly to
+the language, automatic objects in C++ can be
+used to implement much of their necessary infrastructure.
+The automatic object approach is natural from a language perspective,
+provides full algorithmic control to the end programmer, and
+demonstrates C++'s linguistic elegance. The disadvantage of this
+approach is its added programmatic overhead. Using only automatic
+objects, certain programming errors, such as accidental scope
+removal and incorrectly programmed transactional retry behavior,
+can arise.
+
+In light of this, there are unique trade-offs between language based
+and library-based parallel primitives. Language-based solutions
+minimize syntactic clutter which reduce programmer related
+errors, but are seemingly irreversible and, if incorrect, can
+have crippling effects upon the language. Library-based solutions
+increase programmer control and flexibility, but place substantial
+pressure on the programmer to avoid minute programming errors.
+A good compromise is a solution that behaves like a language extension,
+but is implemented within a library. By implementing parallel
+primitives within a library that uses language-like interfaces,
+programmer pressure is reduced, implementation updates are seamless,
+and full programmer control is achieved through library extensibility.
+
+
+
+__Boost_STM__ present such a language-like solution for C++
+using generic library coupled with a deliberate use of the
+preprocessor. The culmination of these components facilitate a
+simple, yet powerful, parallel programming interface in C++.
+
 
 
 [endsect]
\ No newline at end of file

Modified: sandbox/stm/branches/vbe/libs/stm/doc/overview.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/overview.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/overview.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -23,6 +23,18 @@
 
 [*Boost.STM] provides:
 
+* Optimistic concurrency
+* ACI transactions
+ * Atomic: all or nothing
+ * Consistent: only legal memory states
+ * Isolated: other txes cannot see until committed
+* Language-like atomic transaction macro blocks
+* Open-nested composable transactions
+* Direct/deffered updating policies
+* Validation/invalidation consistency checking policies
+* Lock-aware transaction
+* Contention management: Mechanism for transaction forward progress
+* Unrecoverable transaction to manage with I/O
 
 
 [/====================================]
@@ -44,7 +56,7 @@
 
 Finally, you can mentally add the following to any code fragments in this document:
 
- // Include all the stm header files
+ // Include all of InterThreads
     #include <boost/stm.hpp>
 
     // Create a namespace aliases

Modified: sandbox/stm/branches/vbe/libs/stm/doc/rationale.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/rationale.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/rationale.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -8,6 +8,374 @@
 
 [section:rationale Appendix B: Rationale]
 
-TBC
+[section TM-Specific Concepts]
+
+[section Optimistic concurrency]
+[endsect]
+
+[section ACI transactions]
+
+Transactional memory was founded on the database ACID principle (atomic, consistent, isolated and durable), except without the
+D [24].
+
+* Transactions are atomic; the operations all commit or none of them do.
+* Transactions are consistent; transactions must begin and end in legal memory states.
+* Transactions are isolated; memory changes made within a transaction are invisible until committed.
+
+The below example gives a basic introduction into __Boost_STM_s__ transactional framework and demonstrates __Boost_STM_s__ ACI conformance.
+
+ native_trans<int> global_int;
+ int increment_global() {
+ atomic(t) {
+ t.write(global_int)++;
+ val = t.read(global_int);
+ } end_atom
+ return val;
+ }
+
+In the above example, (A) both the t.write() and t.read() operations function atomically or neither operations are performed.
+In addition, (C) the transaction begins and ends in legal memory states, meaning global int is guaranteed to be read correctly, preventing thread data races from causing inconsistent results. Lastly, (I) the intermediate state of the incremented global int is isolated until the transaction commits. These three attributes fulfill __Boost_STM_s__
+conformance to the ACI principles. The above example also gives a basic introduction into __Boost_STM_s__ transactional
+framework.
+
+[endsect]
+
+[section STM Synchronization Types]
+
+There are two ways STM systems synchronize memory:
+
+# using non-blocking mechanisms (lock-free) or
+# using lock-based (or blocking) mechanisms.
+
+Non-blocking STM systems use atomic primitives, such as, compare-and-swap (CAS) or load-linked and store-conditional (LL-SC), that do not lock the STM system to perform their transactional operations. Lock-based STM systems use locks, such as mutual exclusion locks, which lock the STM system to perform some portion of their transactional operations.
+
+__Boost_STM__ is a lock-based STM system. At its core, __Boost_STM__ uses one lock per thread to implement transactional reads and writes. This allows multiple transactions to simultaneously read and write without blocking other transactions' progress. When a transaction is committing, a global locking strategy is used to temporarily block forward progress on all transactions except the committing one. Once the committing transaction completes, other transactions are allowed to resume their work. __Boost_STM_s__ lockbased strategy allows it to gain the performance benefits of a nonblocking system, such that when transactions are not committing, the transactions do not block each other and are guaranteed to make forward progress. Yet __Boost_STM__ maintains the benefits of a lockbased system, enabling it to perform commit-time invalidation, its primary consistency model mechanism.
+
+Recent research shows lock-based STM systems outperform non-blocking systems. Our own research shows that through
+__Boost_STM_s__ design, scaling concerns and other lock-based specific problems, such as deadlocking and priority inversion, can be overcome with specific contention management and conflict detection policies.
+
+[endsect]
+
+[section Updating policies]
+
+In any STM system, an updating protocol must be used to perform transactional commits for writes. Updating policies determine how a transaction commits its memory updates to global memory. Two general ways exist to perform updating:
+
+# direct updating, which copies the original global memory state off to the side and then writes directly to global memory, and
+# deferred updating, which copies the original global memory off to the side and the writes to the local copy.
+
+When a transaction of a direct updating system commits its changes, no changes to global memory are made as the STM system has written directly to global memory. When a transaction of a deferred updating system commits its changes, it writes the local changes to global memory. When a direct updating system aborts, it uses the original copy of memory to update global memory, restoring it to its original state. When a deferred updating system aborts, no changes to global memory are made as the STM system has not written anything to global memory. One of __Boost_STM_s__ novel features is its implementation of both direct and deferred updating.
+
+[endsect]
+
+[section Conflict Detection]
+
+Conflict detection is the process of identifying when two or more transactions conflict. Conflicts can exist when a transaction writes to memory that another transaction then reads or writes (write after write, write after read), or when a transaction reads memory that is then used in another transaction's write (read after write). Unlimited readers, on the other hand, can read the same piece of memory without any conflict (read after read).
+
+[table Comparaison with other STM systems
+ [
+ [[*Features]] [[*after write]] [[*after read]]
+ ]
+ [
+ [[*write]] [[*YES]] [[*YES]]
+ ]
+ [
+ [[*read]] [[*YES]] [[*NO]]
+ ]
+]
+
+
+Before determining how to handle a conflict, STM systems must determine when they will detect conflicts. There are two primary ways to detect conflicts:
+
+* Early conflict detection attempts to identify conflicts as soon as a transaction reads or writes to memory.
+* Late conflict detection attempts to identify conflicts some time after the initial read or write.
+
+For direct updating, __Boost_STM__ implements a run-time configurable early and late conflict detection mechanism. For deferred updating, __Boost_STM__ only implements late conflict detection. The decision to have __Boost_STM__ only support late conflict detection for deferred updating was made after identifying numerous lost optimizations using early conflict detection with deferred updating.
+
+Future work may lead to the implementation of early conflict detection for deferred updating simply for symmetry.
+
+[endsect]
+
+[section Consistency checking policies]
+
+An STM system can identify a conflict in two principal ways: through validation or invalidation.
+
+* Validation is the process a transaction performs on its own read and write set to check itself for consistency.
+* Invalidation is the process a transaction performs on other transaction's read and write sets to check them for consistency.
+
+Validation strategies usually have the the transaction abort itself if an inconsistency is found. Invalidation strategies usually do just the opposite, aborting the other transactions if an inconsistency is found. In addition, STM systems can use contention managers to determine how best to behave when inconsistent transactions are identified.
+
+__Boost_STM__ currently implements consistency checking only through invalidation. One of the next goals of __Boost_STM__ is to build run-time configuration of consistency checking for both invalidation and validation, as it is believed that both may be necessary for varying problems. This aside, __Boost_STM__ is unique in that it is the first STM system to implement commit-time invalidation. While other systems, such as __RSTM__, have implemented invalidation, no other system implements commit-time invalidation.
+
+We believe __Boost_STM__ is the first commit-time invalidating system due to commit-time invalidation being seemingly only possible in lock-based STM systems and as lock-based STM systems are relatively new, other lock-based systems not being far enough along to implement it yet. The two key differences we focus on in this work between invalidation and validation are;
+
+# invalidation can save many wasted operations by early notification of doomed transactions, whereas validation cannot and
+# invalidation can detect true priority inversion, whereas validation cannot
+
+(other significant differences exist, but are not discussed here).
+
+* Fully validating systems must iterate through all transactional operations and determine consistency only at commit-time. Thus, each transaction must fully execute its transactional operations. A substantial amount of work can be saved by an invalidating system which can flag doomed transactions early, as shown in table 1. Table 1 details 4, 8 and 12 threaded runs for red-black trees, linked lists and hash tables in __Boost_STM__. While the percentage of operational savings decreases for each benchmark as the structure size increases, the actual operational savings improves. For example, if a linked list is inserting at the end of a 1600 node list and receives an early termination notification saving 50% of its operations, the savings gained is an 800 node iteration and insert. Likewise, performing a 90% operations savings in a linked list insert operation of size 100, saves only a 90 node iteration and insert.
+
+Furthermore, not shown in the tables here, due to space limitations, is that abort percentages grow for each benchmark as the data structure size increases. Thus, the number of aborts increases, resulting in an even high amount of abort savings per benchmark. The increasing number of aborts as the data structure grows is quite intuitive as longer running transactions are more likely to incur collisions, especially while operating on the same data structure.
+
+* Priority inversion occurs in TM when a lower priority transaction causes a higher priority transaction to abort. Furthermore, priority inversion can be guaranteed to only abort true priority inverted transactions in an invalidating system. However, validating systems can also build priority inversion schemes, they simply must suffer penalties of potentially aborting transactions unnecessarily. The following section gives concrete examples of handling priority inversion in both validating and invalidating models.
+
+
+[endsect]
+
+[section Consistency versus Updating policies composition]
+
+While __Boost_STM__ benchmarks show that, deferred updating in our system usually outperforms direct updating, this is not always the case. In particular, direct updating eventually outperforms deferred updating in __Boost_STM__ as the data structure size grows. With this in mind, we believe that direct updating is useful for specific algorithms with highly innate parallelism (such as hash tables). Likewise, we believe validation may outperform invalidation for high thread counted uses. From these conclusions, we believe final STM systems may be required to implement direct updating, deferred updating, validation and invalidation, all of which should be configurable at run-time and compile-time. By doing this, each problem which demands a different four-way configuration can be handled appropriately. Rather than attempting to build a single implementation which solves all problems universally, the end resulting STM system will handle each specific problem with the most appropriate configuration.
+
+[table Consistency versus Updating policies composition
+ [
+ [[*Features]] [[*Direct]] [[*Deferred]]
+ ]
+ [
+ [[*Validation]] [[*YES]] [[*YES]]
+ ]
+ [
+ [[*Invalidation]] [[*Not Yet Implemented]] [[*YES]]
+ ]
+]
+
+[endsect]
+
+
+[section Memory Granularity]
+
+STM systems must use a memory granularity size of either word or object for transactions. Word memory granularity allows transactions to read and write at the machine's architectural word size. Type memory granularity allows transactions to read and write at the type level, usually controlled by implementation of a transactional object cache. Object memory granularity allows transactions to read and write at the object level, usually controlled by implementation of a transactional object base class using subtype polymorphism. __Boost_STM__ implements the latter, performing reads and writes at the object level.
+
+[endsect]
+
+[section Memory Rollback Capability]
+
+STM systems must implement memory rollback capabilities for aborted transactions. Memory rollbacking restores the original state of memory in the event a transaction aborts. There are three rollbacking aspects any STM system must handle when implemented in an unmanaged language;
+
+* updates to global,
+* allocated memory and
+* deallocated memory.
+
+__Boost_STM__ handles rollbacking to global memory internally for both direct and deferred updating, requiring no programmer-based code. However, allocated and deallocated memory rollbacking require programmer-specific interfaces to be used. These interfaces handle C++ memory operations in their native capacity - new and delete - as well as their transactional memory capacity, ensuring no memory is leaked nor deleted prematurely.
+
+Examples of this are presented in the following section.
+
+[endsect]
+
+[section Composable transactions]
+
+Composition is the process of taking separate transactions and adding them together to compose a larger single transaction. Composition is a very important aspect of transactions as, unlike locks, transactions can compose. Without a composable TM system, nested transactions each act independently committing their state as they complete. This is highly problematic if an outer transaction then aborts, as there may be no way to rollback the state of a nested (and already committed) transaction. Therefore, implementation of composable transactions is paramount to any TM system which hopes to build large transactions.
+
+__Boost_STM__ implements composition via subsumption and is a closed nested system. Composition via subsumption merges all nested transactional memory of a single thread into the outer most active transaction of that same thread. The outer transaction subsumes all the inner transactions' changes. Once the outer transaction completes, all the transactional memory from the nested transactions and their parent either commit or abort. __Boost_STM_s__ closed nesting system enables each nested transaction visibility into its parent's transactional memory and vice versa, but does not allow other transactions to see this intermediate state.
+
+Future versions of __Boost_STM__ will implement closed nested transactions.
+
+[endsect]
+
+[section Contention management]
+
+[endsect]
+[section Unrecoverable transactions to manage with I/O]
+
+[endsect]
+[section Lock-aware transaction]
+
+[endsect]
+
+[endsect]
+
+[section C++ and Library-Specific Concepts]
+
+This section briefly discusses some of the C++ and library-specific
+concepts of __Boost_STM__.
+
+[section Native Language Compatibility]
+
+Native Language Compatibility. Some existing STM systems require specific language extensions or compiler support for their proposed system to work. Other systems instead violate native language pragmatics by reducing or removing type-safety altogether. Yet other system's transactional functionality is significantly reliant on the preprocessor.
+
+__Boost_STM__ is built with native language compatibility as a top priority - as such, it does not require language extensions or violate natural language semantics. Native language compatibility is a foremost concern due to C++0x set to specifically resist language extensions [29]. While in other languages, such as Java, STM systems which require language extensions may be practical, within C++ this same approach seems unrealistic. Thus, there is a very practical need for a native language ready STM solution for C++.
+
+[endsect]
+
+[section Memory Management]
+
+For unmanaged languages like C++, STM designers can build memory managers to control heap-based memory allocation and deallocation. While building a memory manager is not necessary for STM systems, performance optimizations can be achieved through such implementations. In particular, a key memory observation for STM systems is that numerous allocations and deallocations happen within transactions, irrespective of the memory design decisions. As such, __Boost_STM__ provides a builtin templatized user-configurable memory manager which generally yields 20% performance improvement over direct calls to the default C++'s new and delete.
+
+As understood by most C++ experts, native new and delete operators in C++ are multi-threaded safe, using mutex locks to guarantee memory is retrieved and released in a safe manner for multiple contending threads. Improving the performance of direct calls to C++'s new and delete in a single-threaded application is relatively easy as a buffered free store can be created which requires no locking mechanism, thus naturally increasing performance. This same task is not quite as easy in a multi-threaded environment. __Boost_STM__ improves the native performance of C++'s operator new and delete by first implementing buffered allocations which naturally perform faster than single allocations. Secondly, performance gains are made by not relinquishing ownership of deallocated memory, making second-time memory allocations faster than first-time allocations. These two aspects enable __Boost_STM_s__ memory manager to perform faster than C++'s native new and delete operations.
+
+__Boost_STM__ also must lock around memory allocations and deallocations, just as native C++ new and delete must, however, it can build a more problem-specific implementation that would hinder a generalized C++ new and delete if implemented on a global scale. The techniques used in __Boost_STM__ are similar to those discussed in Bulka and Mayhew's, Efficient C++, Chapter 7, Multi-threaded Memory Pooling. In C++ semantics, the performance gains within __Boost_STM_s__ memory manager can be thought of as the differences between using an std::vector's push_back() iteratively compared to using an std::vector's push_back() iteratively after calling reserve(), and then continuing to reuse the allocated space to avoid performance penalties of reallocations.
+
+[endsect]
+
+
+[section RAII]
+
+An STM system needs a transaction interface to identify where transactions begin, end and which operations are performed within the transaction. __Boost_STM__ achieves this by implementing transactions as objects using the Resource Acquisition Is Initialization (RAII) principle.
+
+RAII is a common concept in C++ when dealing with resources that need to be both obtained and released, like opening and closing a file. RAII uses the concept that if a resource is obtained it must be released even if the programmer fails to do so. RAII's behavior is implemented per class, usually requiring the destructor of the class to guarantee any resources gathered in the lifetime of the object be released. A primary benefit of RAII is its natively correct behavior in the event of exceptions. If an exception occurs causing an RAII class instance to destruct, due to stack unwinding, the deterministic destruction of the object is invoked. The destructor then releases any resources previously collected. This guarantees any object implementing RAII semantics will always release resources it controls, irrespective of program flow (normal or abnormal).
+
+The __Boost_STM_s__ transaction class is based on the RAII concept for two primary reasons. First, C++ programmers implicitly understand stack based (automatic) objects and their native RAII semantics. In fact, all of C++'s Standard Template Library (STL) containers are implemented using the RAII philosophy. Second, exceptions in C++ are not required to be handled by the programmer as they are in other languages, like Java. Using RAII for transactions ensures proper and guaranteed termination of transactions regardless of program flow, a very important attribute for correct transactional behavior.
+
+[endsect]
+
+[section Exception Safety]
+
+__Boost_STM__ fulfills Abrahams' basic exception safety guarantee for deferred updating, but cannot supply any exception safety guarantee for direct updating. The basic guarantee for exception safety states that if an exception is thrown, the operation may have side-effects but is in a consistent state. The basic guarantee is less strict than the strong guarantee which specifies if an exception is thrown there are no side-effects. The highest level of exception safety, above the strong guarantee, is the nothrow guarantee which disallows exceptions from being thrown entirely.
+
+Within deferred updating, __Boost_STM__ can only afford to implement the basic guarantee because if memory is partially committed and then a user exception is thrown, no original state exists for the already committed memory. Therefore, already committed memory in a deferred updating system, must stay committed since no reverted original state can be used to revert the changes. To implement such a system would result in a substantial performance degradation to the overall system, effectively doubling memory size and copy operations. Due to these costs, a double-copy implementation is not performed and the basic guarantee for deferred updating is deemed acceptable.
+
+Within direct updating, memory updates are done immediately on global memory, so transactions naturally achieve strong exception safety guarantees for commits. Aborts within direct updating, however, invoke copy constructors for restoration of the original global memory state. These copy constructors can throw exceptions which then can lead to a partially restored global state for aborted exceptions that are short-circuited by user-defined copy constructor exceptions. As such, no exception safety guarantee can be made for direct updating when used in C++, a downfall of the updating policy.
+
+[endsect]
+
+[section Move semantics]
+
+We solve the problem of commit-time and abort-time exceptions by using
+move semantics in place of copy semantics. The idea of moving is new to C++
+and will be available in the next version of the standard.
+
+[endsect]
+
+[section Parametric Polymorphism and Subtype Polymorphism]
+
+Type
+abstraction in C++ to create general purpose code can be achieved in numerous ways. Some of these ways, such as the use of C++ template classes and template functions (parametric polymorphism), as well as inheritance (subtype polymorphism), are considered practical and robust ways to build general purpose functionality while still ensuring a certain degree of type-safety is maintained. C++ templates, also known as parametric polymorphism, exhibit the same type-safety as if the general purpose code was written specifically for the templated instantiated type. Inheritance, on the other hand, reduces type-safety to some degree, but gains run-time flexibility unachievable with C++ templates alone. Other mechanisms also exist to create general purpose code, such as void pointers or preprocessor macros, but are considered unsafe and error-prone [8] and thusly, not used in __Boost_STM__.
+
+__Boost_STM__ uses both parametric and subtype polymorphism throughout its internal implementation and exposed interfaces. In cases where strict type-safety can be achieved, C++ templates are used. In other cases where exact type-safety cannot be achieved without reducing __Boost_STM_s__ functionality, inheritance is used. All of these factors considered, __Boost_STM__ is a research library that requires type-safety to be a foremost concern, as its usage would hampered if type-safety was relaxed in areas where it could have been retained. As such, C++ templates are used due to their retention of full type information, in cases where inheritance would have also sufficed with a slight loss of type-safety.
+
+
+[endsect]
+
+[section Language-like atomic transaction macro blocks]
+
+Transactions allow an unlimited number of threads to execute their optimistic critical sections. Transactions can perform their writes off to the side, ensuring global memory is preserved until the transaction's atomic operations are complete. To ensure conflicting transactions are identified and prevented, transactions perform correctness verification immediately before committing. The consistency checking performed by transactions ensures that transactions that write to or read from the same memory are restricted in their concurrent execution. The code below demonstrates three different implementations for transactions from a library-based approach where x is shared memory that must be synchronized.
+
+transaction with begin()/end():
+
+ begin_transaction(t);
+ tx_write(t, x) = val;
+ end_transaction(t);
+
+
+transaction with automatic object:
+
+ {
+ transaction t;
+ t.write(x) = val;
+ t.end();
+ }
+
+language transaction:
+
+ atomic { x = val; }
+
+Inspection of the above code reveals that begin_transaction() and end_transaction() are susceptible to the problem when a thrown exception can interfere with correct interface calls. As such, the begin_transaction() and end_transaction() approach can be immediately discarded from further consideration. The two remaining approaches, similar to the prior locking implementations, use automatic objects and a language-like approach. An initial observable difference between the two approaches is that the language approach has a smaller programmatic footprint than the automatic object approach. Furthermore, the automatic object approach introduces more programmatic complexity for transactional retry mechanics and composed transactional behaviors.
+
+[heading Pitfalls in Transactional Execution of Automatic Objects]
+
+Transactions use optimistic critical sections which generally require transactions be retried if they do not commit. As such, transactions are usually implemented as loops which re-execute until they commit. The code below illustrates the client code necessary to implement a basic retry behavior for automatic objects and language-like transactions.
+
+automatic object transaction with retry:
+
+ for (transaction t; !t.committed(); t.restart()) {
+ try {
+ t.write(x) = val;
+ t.end();
+ } catch (...) {}
+ }
+
+language-like transaction with retry:
+
+ atomic(t) {
+ t.write(x) = val;
+ } end_atom
+
+To complicate matters, some transactions must not implement a retry. Failed subtransactions often require the entire transaction be re-executed from the beginning. While the methods used to perform transactional retries vary between TM implementations, __Boost_STM__ uses an exception-based approach for all transactional interfaces. These __Boost_STM__ interfaces throw exceptions if transactions are found to be inconsistent. Therefore, parent transactions should use retry mechanics while their child transactions should not. The code above shows the differences between an automatic object and language-like implementation for parent and child transactions.
+
+automatic object:
+
+ // parent tx with automatic object:
+ for (transaction t; !t.committed(); t.restart()) {
+ try {
+ t.write(x) -= val;
+ foo();
+ t.end();
+ } catch (...) {}
+ }
+
+ // child tx with automatic object.
+ void foo(int val) {
+ transaction t;
+ t.write(y) += val;
+ t.end();
+ }
+
+language-like transaction:
+
+ // parent tx with language-like transaction.
+ atomic(t) {
+ t.write(x) -= val;
+ foo();
+ } end_atom
+
+ // child tx with language-like transaction.
+ void foo(int val) {
+ atomic(t) {
+ t.write(y) += val;
+ } end_atom
+ }
+
+The retry mechanics' syntactic overhead for automatic objects is nearly double that of the language-like semantics. The complexity of the additional retry code is significant and exhibits a number of locations where programmer-induced errors could be made. The key benefit of the language-like atomic syntax is that its structure is identical for parent and nested transactions and it behaves correctly when any transaction is used as a parent or child (details to follow).
+
+While the automatic object syntax could also be created to be identical for parent and nested transactions, the impact of creating such identical behavior would result in an increase in the child transaction's code size by 266% for single instruction transactions. The resulting increased code size and complexity would increase the likelihood for programmer-induced errors. For these reasons, a number of TM researchers have been in favor of direct language integration of TM instead of API-only approaches.
+
+[heading Disadvantages of Language Based Transactional Integration]
+
+Unfortunately, there are a number of disadvantages to direct language-based support for transactions. To begin, transactional memory is still in the early stages of research investigation. A number of open TM questions should be answered before transactions are integrated directly into high-level languages. Some of the open questions for transactions are regarding validation and invalidation consistency checking, fairness and priority-based transactions, open and closed nesting, exception behavior within transactions, lock-based and non-blocking solutions, and hardware-software transactional communication. Furthermore, some TM problems, such as contention management strategy selection, seem more naturally placed within libraries than languages due to their continually evolving and workload-specific nature.
+
+In light of this, direct integration of TM into a programming language today may lead to errors that are irreversible. These errors may have long-term consequences for the language. Language based integrations are also slow to emerge, even in languages that are quick to evolve, such as Java. A language-based approach to TM may take several years before it is available. Yet, the emergence of multi-core hardware is rushing programmers to develop multithreaded applications today. Without wide TM availability, the primary parallel programming construct used today is locks. Parallel programming research experts unanimously agree that finegrained locking alone leads to notoriously complex software to implement and maintain.
+
+The culmination of the above points illustrate the need for an extensible, simplified, parallel programming model today. Our language-like approach provides such a solution for C++ that neither library-based automatic objects nor language-based parallel abstractions alone can provide.
+
+[endsect]
+
+[endsect]
+
+
+[section Comparaison with other STM systems]
+
+[table Comparaison with other STM systems
+ [
+ [[*Features]] [[*__Boost_STM__]] [[*TL2]]
+ ]
+ [
+ [[*Lock-free]] [[*NO]] [[*YES]]
+ ]
+ [
+ [[*Lock-based]] [[*YES]] [[*NO]]
+ ]
+ [
+ [[*Validation]] [[*YES]] [[*??]]
+ ]
+ [
+ [[*Invalidation]] [[*YES]] [[*NO]]
+ ]
+ [
+ [[*Direct-Updating]] [[*YES]] [[*YES]]
+ ]
+ [
+ [[*Deferred-Updating]] [[*YES]] [[*YES]]
+ ]
+ [
+ [[*Word memory granulatity]] [[*NO]] [[*YES]]
+ ]
+ [
+ [[*Object memory granulatity]] [[*NO]] [[*YES]]
+ ]
+]
+
+
+
+
+[endsect]
 
 [endsect]

Modified: sandbox/stm/branches/vbe/libs/stm/doc/reference.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/reference.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -1,5 +1,5 @@
 [/
- (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Justin E. Gottchlich.
   (C) Copyright 2009 Vicente J. Botet Escriba
  /
  / Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -8,7 +8,22 @@
 
 [section Reference]
 
+The following section presents the major design components identified in the background section and discusses how they are implemented within the __Boost_STM__ library.
 
+[/include reference/stm.qbk]
+[/include reference/rt_configuration.qbk]
+[include reference/data_types.qbk]
+[include reference/exceptions.qbk]
+[/include reference/synchro.qbk]
+[include reference/transaction.qbk]
+[include reference/transaction_object.qbk]
+[include reference/smart_pointers.qbk]
+[include reference/base_contention_manager.qbk]
+[include reference/language_like.qbk]
+[/include reference/contention_manager/default_contention_manager.qbk]
+[/include reference/contention_manager/NoExceptionOnAbortNoticeOnReadWritesCM.qbk]
+[/include reference/contention_manager/ExceptAndBackOffOnAbortNoticeCM.qbk]
+[include reference/transaction_bookkeeping.qbk]
 
 [endsect]
 

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/base_contention_manager.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/base_contention_manager.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,136 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[/==========================================================================================]
+[section:base_contention_manager_hpp Header `<boost/stm/base_contention_manager.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class base_contention_manager;
+ }}
+
+
+[section Abstract Class `base_contention_manager`]
+
+ class base_contention_manager {
+ public:
+ virtual void abort_on_new(boost::stm::transaction const &t) = 0;
+ virtual void abort_on_delete(
+ boost::stm::transaction const &t,
+ boost::stm::base_transaction_object const &in) = 0;
+ virtual void abort_on_read(
+ boost::stm::transaction const &t,
+ boost::stm::base_transaction_object const &in) = 0;
+ virtual void abort_on_write(
+ boost::stm::transaction &t,
+ boost::stm::base_transaction_object const &in) = 0;
+ virtual bool abort_before_commit(boost::stm::transaction const &t) = 0;
+ virtual bool permission_to_abort(
+ boost::stm::transaction const &lhs,
+ boost::stm::transaction const &rhs) = 0;
+ virtual bool allow_lock_to_abort_tx(
+ int const & lockWaitTime,
+ int const &lockAborted,
+ bool txIsIrrevocable,
+ boost::stm::transaction const &rhs) = 0;
+ virtual int lock_sleep_time();
+ virtual void perform_isolated_tx_wait_priority_promotion(
+ boost::stm::transaction &) = 0;
+ virtual void perform_irrevocable_tx_wait_priority_promotion(
+ boost::stm::transaction &) = 0;
+ virtual ~base_contention_manager() {};
+ };
+
+[section Virtual destructor `base_contention_manager`]
+
+ virtual ~base_contention_manager();
+
+[endsect]
+
+[section Virtual function `abort_on_new`]
+
+ virtual void abort_on_new(boost::stm::transaction const &t) = 0;
+
+Supplies the behavior for transactional aborts when identified as doomed from within a `new_memory()` or `new_memory_copy()` operation. The input parameter is the doomed transaction. Throwing `aborted_transaction_exceptions` are the usual mechanism for aborting.
+
+[endsect]
+
+[section Virtual function `abort_on_delete`]
+
+ virtual void abort_on_delete(
+ boost::stm::transaction const &t,
+ boost::stm::base_transaction_object const &in) = 0;
+
+Supplies the behavior for transactional aborts when identified as doomed from within a `delete_memory()` operation. The input parameters are the doomed transaction and the object being deleted. Throwing `aborted_transaction_exceptions` are the usual mechanism for aborting.
+
+[endsect]
+[section Virtual function `abort_on_read`]
+
+ virtual void abort_on_read(
+ boost::stm::transaction const &t,
+ boost::stm::base_transaction_object const &in) = 0;
+
+Supplies the behavior for transactional aborts when identified as doomed from within a `read()` operation. The input parameters are the doomed transaction and the object being read. Throwing `aborted_transaction_exceptions` are the usual mechanism for aborting.
+
+[endsect]
+[section Virtual function `abort_on_write`]
+
+ virtual void abort_on_write(
+ boost::stm::transaction &t,
+ boost::stm::base_transaction_object const &in) = 0;
+
+Supplies the behavior for transactional aborts when identified as doomed from within a `write()` operation. The input parameters are the doomed transaction and the object being written. Throwing `aborted_transaction_exceptions` are the usual mechanism for aborting.
+
+[endsect]
+[section Virtual function `abort_before_commit`]
+
+ virtual bool abort_before_commit(boost::stm::transaction const &t) = 0;
+
+This method is called prior to a transaction performing its commit operation. The parameter passed in is the transaction preparing to commit. The client code should return `true` if the transaction should abort before committing. Otherwise, client implementation should return `false`.
+
+[endsect]
+[section Virtual function `permission_to_abort`]
+
+ virtual bool permission_to_abort(
+ boost::stm::transaction const &lhs,
+ boost::stm::transaction const &rhs) = 0;
+
+This method is invoked when a transaction is requesting permission to abort another transaction due to a memory inconsistency. Client code should return `true` if the transaction should abort before committing. Otherwise, client implementation should return `false`. The `lhs` input parameter is the transaction requesting to abort `rhs`, the `rhs` input parameter is the transaction which will be aborted if return `true`. Otherwise, if the method returns `false`, `lhs` will be aborted.
+
+[endsect]
+[section Virtual function `allow_lock_to_abort_tx`]
+
+ virtual bool allow_lock_to_abort_tx(
+ int const & lockWaitTime,
+ int const &lockAborted,
+ bool txIsIrrevocable,
+ boost::stm::transaction const &rhs) = 0;
+
+[endsect]
+[section Virtual function `lock_sleep_time`]
+
+ virtual int lock_sleep_time();
+
+[endsect]
+[section Virtual function `perform_isolated_tx_wait_priority_promotion`]
+
+ virtual void perform_isolated_tx_wait_priority_promotion(
+ boost::stm::transaction &) = 0;
+[endsect]
+[section Virtual function `perform_irrevocable_tx_wait_priority_promotion`]
+
+ virtual void perform_irrevocable_tx_wait_priority_promotion(
+ boost::stm::transaction &) = 0;
+
+[endsect]
+
+
+[endsect]
+[endsect]
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/base_transaction.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/base_transaction.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,89 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+
+[/==========================================================================================]
+[section:transaction_object_hpp Header `<boost/stm/transaction_object.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class base_transaction_object;
+ template <class Derived> class transaction_object;
+ template <typename T> class native_trans;
+ }}
+
+[section Abstract Class `base_transaction_object`]
+
+ class base_transaction_object
+ {
+ public:
+
+ base_transaction_object();
+ virtual ~base_transaction_object() {};
+
+ virtual void copy_state(base_transaction_object const * const rhs) = 0;
+ virtual void move_state(base_transaction_object * rhs) = 0;
+
+ void transaction_thread(thread_id rhs) const;
+ thread_id transaction_thread() const;
+
+ void new_memory(bool rhs)
+ bool new_memory() const;
+
+ #if BOOST_STM_PERFORMING_VALIDATION
+ void version(std::size_t rhs);
+ std::size_t version() const;
+ #endif
+
+ };
+
+[endsect]
+
+[section Template Class `transaction_object<>`]
+
+ template <class Derived>
+ class transaction_object : public base_transaction_object {
+ public:
+
+ virtual void copy_state(base_transaction_object const * const rhs);
+ virtual void move_state(base_transaction_object * rhs);
+ };
+
+[endsect]
+
+[section Template Class `native_trans<>`]
+
+ template <typename T> class native_trans : public transaction_object< native_trans<T> > {
+ public:
+ native_trans(){}
+ native_trans(T const &rhs);
+ native_trans(native_trans const &rhs);
+ native_trans(native_trans &&rhs);
+ native_trans& operator=(native_trans &&rhs);
+
+ native_trans& operator=(T const &rhs);
+
+ native_trans& operator--();
+ native_trans operator--(int);
+ native_trans& operator++();
+ native_trans operator++(int);
+ native_trans& operator+=(T const &rhs);
+ native_trans operator+(native_trans const &rhs);
+
+ operator T() const;
+ T& value();
+ T const & value() const;
+ };
+
+[endsect]
+[section Class `base_transaction`]
+
+[endsect]
+[endsect]
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/data_types.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/data_types.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,46 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+
+[/==========================================================================================]
+[section:data_types_hpp Header `<boost/stm/data_types.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ enum transaction_type;
+ enum latm_type;
+ enum transaction_state;
+ typedef thread_id_t;
+ }}
+
+[section Enum `transaction_type`]
+
+[endsect]
+[section Enum `latm_type`]
+
+[endsect]
+[section Enum `transaction_state`]
+
+ enum transaction_state
+ {
+ e_no_state = -1, // no state is -1
+ e_aborted, // ensure aborted = 0
+ e_committed, // committed is positive
+ e_hand_off, // so is handoff in case bool conversion
+ e_in_flight
+ };
+
+[endsect]
+[section Typedef `thread_id_t`]
+
+[endsect]
+[endsect]
+
+
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/exceptions.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/exceptions.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,22 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+
+[/==========================================================================================]
+[section:exceptions_hpp Header `<boost/stm/exceptions.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class aborted_transaction_exception;
+ }}
+
+[section Class `aborted_transaction_exception`]
+
+[endsect]
+[endsect]
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/language_like.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/language_like.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,139 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[/==========================================================================================]
+[section:language_like_hpp Header `<boost/stm/language_like.hpp>`]
+[/==========================================================================================]
+
+The complexity behind the `atomic` macro is needed to guarantee two
+fundamental goals.
+
+*First, transactions must start and end correctly.
+Second, transactions must change their retry behavior based on
+whether they are a child or parent transaction to ensure proper
+closed nesting, flattened transaction behavior is performed.
+
+The `atomic` preprocessor behaves as follows. When the transactional for loop is entered,
+a transaction automatic object is constructed which initializes
+the transaction and puts it in-flight. The for loop conditional
+ensures the following conditions:
+
+# the transaction is uncommitted,
+# the transaction has the opportunity to throw an exception if necessary, and
+# the transaction is in-flight.
+
+Once a transaction commits, the check on (1) `!T.committed()` ensures
+the transaction is not executed again. If the transaction has been
+aborted but is a child transaction, the transaction must be restarted
+at the parent level. The call to (2) `T.check_throw_before_restart()`
+allows an aborted child transaction to throw an exception upward
+(before it is restarted) so the entire transaction can be restarted from
+the parent. The `check_throw_before_restart()` API checks
+the current run-time state of the thread to determine if another
+transaction is active above it. This behavior allows transactions to
+be used at any nesting level while dynamically ensuring the correct
+retry behavior. Finally, the call to `restart_if_not_inflight()`
+ensures the transaction is correctly restarted after each subsequent
+abort.
+
+Once all of the transactional operations within the for loop are
+executed, a call to no_throw_end() is made which ends the transaction.
+The `no_throw_end()` terminates the transaction by either
+committing or aborting it. Note, however, that `no_throw_end()`
+does not throw an exception if the transaction is aborted, whereas
+the prior __Boost_STM_s__ API end() does. This non-throwing behavior
+deviates from the prior __Boost_STM__ implementation of automatic
+objects when end() was invoked within the try / catch
+body. Furthermore, due to `no_throw_end()` not throwing an exception
+if the transaction is aborted, some cases may arise where
+`catch_before_retry` or `before_retry` operations are not invoked
+when a transaction is aborted. This is a current limitation of
+the system and is overcome by inserting a manual end() operation
+as the last operation in the atomic block. The explicit end()
+ensures any operations within the before_retry block are
+executed if the transaction is aborted.
+
+
+
+ #define atomic(T)
+ #define try_atomic(T)
+ #define use_atomic(T)
+ #define catch_before_retry(E)
+ #define before_retry
+ #define end_atom
+
+
+[section Macro `atomic`]
+
+Use atomic transaction T for optimistic critical section. Supports single-depth and multiple-depth (nested)
+transactions. Performs automatic retry when T is a parent transaction, throws exception when T is a
+child transaction. This automatic switch enables correctly behaved nested and non-nested transactions
+
+ #define atomic(T) \
+ for (transaction T; \
+ !T.committed() && T.check_throw_before_restart() && T.restart_if_not_inflight(); \
+ T.no_throw_end())
+ try
+
+
+
+[endsect]
+
+[section Macro `try_atomic`]
+
+ #define try_atomic(T) \
+ for (transaction T; \
+ !T.committed() && T.restart(); \
+ T.no_throw_end())
+ try
+
+[endsect]
+
+[section Macro `use_atomic`]
+
+ #define use_atomic(T) \
+ for (transaction T; \
+ !T.committed() && T.restart(); \
+ T.end())
+
+
+
+[endsect]
+[section Macro `catch_before_retry`]
+
+ #define catch_before_retry(E) catch (aborted_tx &E)
+
+Catches exception when transaction is aborted. This, before_retry, or end_atom must follow an
+atomic block. Once all operations within the catch_before_retry block are executed, control is
+returned to the local atomic where the transaction is retried (if it is the parent) or the atomic block
+is exited by exception (if it is a child).
+
+To be used pairwise with `try_atomic` or `atomic`.
+
+[endsect]
+[section Macro `before_retry`]
+
+ #define before_retry catch (aborted_tx &)
+
+Same as catch_before_retry(E) except the exception is discarded.
+
+To be used pairwise with `try_atomic` or `atomic`.
+
+[endsect]
+[section Macro `end_atom`]
+
+ #define end_atom catch (aborted_tx &) {}
+
+Same as before_retry except the exception is discarded and {} are automated.
+
+To be used pairwise with `try_atomic` or `atomic`.
+
+[endsect]
+[endsect]
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/smart_pointers.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/smart_pointers.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,279 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[/==========================================================================================]
+[section:tx_ptr_hpp Header `<boost/stm/tx_ptr.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+
+ template <typename T> class tx_obj;
+ template <typename T, typename U>
+ bool operator==(const tx_obj<T>& lhs, const tx_obj<U>& rhs);
+ template <typename T, typename U>
+ bool operator==(const T& lhs, const tx_obj<U>& rhs);
+ template <typename T, typename U>
+ bool operator==(const tx_obj<T>& lhs, const U& rhs);
+ template <typename T, typename U>
+ bool operator!=(const tx_obj<T>& lhs, const tx_obj<U>& rhs);
+ template <typename T, typename U>
+ bool operator!=(const tx_obj<T>& lhs, const tx_obj<U>& rhs);
+ template<class T> inline void swap(tx_obj<T> & a, tx_obj<T> & b);
+
+ template <typename T> class tx_ptr;
+ template <typename T, typename U>
+ bool operator==(const tx_ptr<T>& lhs, const tx_ptr<U>& rhs);
+ template <typename T, typename U>
+ bool operator!=(const tx_ptr<T>& lhs, const tx_ptr<U>& rhs);
+ template<class T> inline void swap(tx_ptr<T> & a, tx_ptr<T> & b);
+
+ template <typename T>
+ void delete_ptr(tx_ptr<T> ptr);
+ template <typename T>
+ void delete_ptr(transaction& tx, tx_ptr<T> ptr);
+
+ template <typename T, typename U>
+ static tx_ptr<T> tx_static_cast(tx_ptr<U> ptr);
+ template <typename T, typename U>
+ static tx_ptr<T>* tx_dynamic_cast(tx_ptr<U> ptr);
+
+ template <typename T> class rd_ptr;
+ template <typename T>
+ rd_ptr<T> make_rd_ptr(transaction& tx, tx_ptr<T> ptr);
+ template <typename T>
+ rd_ptr<T> make_rd_ptr(transaction& tx, tx_obj<T> const & ref);
+
+ template <typename T>
+ rd_ptr<T> make_rd_ptr(tx_ptr<T> ptr);
+ template <typename T>
+ rd_ptr<T> make_rd_ptr(tx_obj<T> const & ref);
+ template <typename T>
+ void delete_ptr(rd_ptr<T> ptr);
+ template <typename T>
+ void delete_ptr(transaction& tx, rd_ptr<T> ptr);
+
+ template <typename T> class upgrd_ptr;
+ template <typename T>
+ void delete_ptr(upgrd_ptr<T> const& ptr);
+ template <typename T>
+ void delete_ptr(transaction& tx, upgrd_ptr<T> const& ptr);
+
+ template <typename T> class wr_ptr;
+ template <typename T>
+ wr_ptr<T> make_wr_ptr(transaction& tx, tx_ptr<T>& ptr);
+ template <typename T>
+ wr_ptr<T> make_wr_ptr(tx_ptr<T>& ptr);
+ template <typename T>
+ void delete_ptr(wr_ptr<T> ptr);
+ template <typename T>
+ void delete_ptr(transaction& tx, wr_ptr<T> const& ptr);
+
+ template <typename T> class read_ptr;
+ template <typename T> class write_ptr;
+ }}
+
+[section Template Class `tx_obj<>`]
+
+tx_obj is a kind of smart pointer to a wrapped transactional_object T providing builting operators
+
+ template <typename T> class tx_obj {
+ public:
+ tx_obj();
+ template<ctypename Y> tx_obj(tx_obj<Y> const& r);
+
+ template <typename T1> tx_obj(T1 p1);
+
+ T* operator->();
+ const T* operator->() const;
+ T& operator*();
+ const T& operator*() const;
+ T* get();
+ const T* get() const;
+ T& ref();
+ const T& ref() const;
+
+ tx_obj& operator--();
+ T operator--(int);
+
+ tx_obj& operator++();
+ T operator++(int);
+
+ tx_obj& operator+=(T const &rhs);
+ T operator+(T const &rhs) const;
+ };
+
+[endsect]
+
+[section Template Class `tx_ptr<>`]
+
+a tx_ptr<T> is an smart pointer to a transactional_object<T> (which contains an instance of T).
+Reference fields in linked structures should always be tx_ptrs.
+The result of derreferencing it will be the pointer to the T instance
+When this pointer is derreference on a transaction the transactional_object<T> is set a written and
+the transaction specific storage will be used. Otherwise the shared storage is used.
+
+Used to initialize a rd_ptr<T>, wr_ptr<T>, or upgrd_ptr<T>.
+
+ template <typename T>
+ class tx_ptr {
+ public:
+ typedef tx_ptr<T> this_type;
+
+ tx_ptr();
+ template<class Y> explicit tx_ptr(Y * ptr);
+ explicit tx_ptr(transactional_object<T>* ptr);
+ tx_ptr(const tx_obj<T>& r);
+
+ template<class Y> tx_ptr(tx_ptr<Y> const& r);
+ template<class Y> tx_ptr(rd_ptr<Y> const & r);
+ template<class Y> tx_ptr(wr_ptr<Y> const & r);
+ template<class Y> tx_ptr(upgrd_ptr<Y> const & r);
+
+ template<class Y> tx_ptr& operator=(transactional_object<Y>* ptr);
+ template<class Y> tx_ptr & operator=(tx_ptr<Y> const & r);
+
+ T* operator->() const;
+ T& operator*() const;
+ T* get() const;
+
+ typedef transactional_object<T>* this_type::*unspecified_bool_type;
+
+ operator unspecified_bool_type() const;
+ void swap(tx_ptr & other);
+ };
+
+[endsect]
+
+[section Template Class `rd_ptr<>`]
+
+A rd_ptr<T> ("read pointer") points to an object that the current transaction has opened for read only access.
+You can only call a const method through a read pointer.
+
+A rd_ptr<T> is constructed from an tx_ptr<T> through an explicit constructor.
+Once a rd_ptr<T> has been constructed, an tx_ptr<T> can be opened for
+reading simply by assignment (operator=()) into the constructed rd_ptr<T>.
+
+It is not safe to derreference a rd_ptr<T> after having assigned the same
+tx_ptr<T> to a wr_ptr<T>. If this is the case the readen value do not match
+the writen one. If it is possible to write on the same transaction use
+upgrd_ptr instead which is safe.
+
+ template <typename T>
+ class rd_ptr {
+ public:
+ rd_ptr(transaction &t, tx_ptr<T> tx_obj);
+ rd_ptr(transaction &t, tx_obj<T> const& tx_obj);
+
+ template<class Y> rd_ptr & operator=(tx_ptr<Y> r);
+
+ template<class Y> rd_ptr& operator=(tx_obj<Y> const & r);
+
+ const T* get() const;
+
+ inline const T & operator*() const;
+ inline const T* operator->() const;
+
+ operator unspecified_bool_type() const;
+
+ };
+
+[endsect]
+
+[section Template Class `upgrd_ptr<>`]
+
+A upgrd_ptr<T> ("upgradable pointer") points to an object that the current transaction has opened for read only access.
+
+You can only call const method of the wrapped type through a upgradable pointer.
+
+A upgrd_ptr<T> is constructed from an tx_ptr<T> through a constructor
+having also the transaction as parameter. Once a rd_ptr<T> has been constructed, an tx_ptr<T> can be opened for
+reading simply by assignment (operator=()) into the constructed rd_ptr<T>.
+
+It is safe to derreference a rd_ptr<T> after having assigned the same
+tx_ptr<T> to a wr_ptr<T>.
+
+A upgrd_ptr<T> can be upgraded to a wr_ptr<T> through a constructor.
+
+ template <typename T>
+ class upgrd_ptr {
+ public:
+
+ inline upgrd_ptr(transaction &t, tx_ptr<T> tx_obj);
+ template<class Y>
+ upgrd_ptr & operator=(tx_ptr<Y> const& r);
+
+ const T* get() const;
+
+ inline T const & operator*() const;
+ inline T const * operator->() const;
+
+ operator unspecified_bool_type() const;
+
+ void write_ptr(transactional_object<T>* ptr);
+ T* write_ptr();
+
+ };
+
+
+[endsect]
+
+[section Template Class `wr_ptr<>`]
+
+A wr_ptr<T> ("write pointer") points to a shared object that the current transaction has opened for writing.
+
+A wr_ptr<T> is initialized explicitly from an tx_ptr<T>.
+
+A wr_ptr<T> can also be explicitly constructed from a upgrd_ptr<T> as an upgrade-to-writable operation.
+
+
+ template <typename T>
+ class wr_ptr {
+ public:
+ wr_ptr(transaction &t, tx_ptr<T> tx_obj);
+
+ wr_ptr(transaction &t, upgrd_ptr<T> tx_obj);
+
+ T* get();
+
+ inline T& operator*();
+ inline T* operator->();
+
+ operator unspecified_bool_type() const;
+ };
+
+[endsect]
+
+[section Template Class `read_ptr<>`]
+
+ template <typename T> class read_ptr {
+ public:
+ inline read_ptr(transaction &t, T const &tx_obj);
+ const T* get() const;
+ inline T const & operator*() const;
+ inline T const * operator->() const;
+
+ inline transaction &trans();
+ T* write_ptr();
+ };
+
+[endsect]
+[section Template Class `write_ptr<>`]
+
+ template <typename T> class write_ptr {
+ public:
+ inline write_ptr(transaction &t, T & tx_obj);
+
+ T* get() const;
+ inline T& operator*();
+ inline T* operator->();
+
+
+[endsect]
+[endsect]
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,502 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[/==========================================================================================]
+[section:transaction_hpp Header `<boost/stm/transaction.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class transaction;
+ }}
+
+
+[section Class `transaction`]
+
+__Boost_STM__ defines transactions as stackbased
+objects using RAII. In addition to the static interfaces for
+direct and deferred updating described earlier in this section, the
+following interfaces are necessary for performing transactions.
+
+ class transaction {
+ public:
+ // initialization
+ static void initialize();
+ static void initialize_thread();
+ static void terminate_thread();
+
+ // contention manager
+ static void contention_manager(base_contention_manager *rhs);
+ static base_contention_manager* get_contention_manager();
+
+ static bool enable_dynamic_priority_assignment();
+ static bool disable_dynamic_priority_assignment();
+ static bool doing_dynamic_priority_assignment();
+
+ // bookeeping
+ static void enableLoggingOfAbortAndCommitSetSize();
+ static void disableLoggingOfAbortAndCommitSetSize();
+ static const transaction_bookkeeping & bookkeeping();
+
+ // conflict detection
+ static bool early_conflict_detection();
+ static bool late_conflict_detection();
+ static bool do_early_conflict_detection();
+ static bool do_late_conflict_detection();
+
+ // consistency checking
+ static std::string consistency_checking_string();
+ static bool validating();
+ static bool invalidating();
+
+ // updating
+ static bool direct_updating()
+ static bool deferred_updating();
+ static bool do_direct_updating();
+ static bool do_deferred_updating();
+ static std::string update_policy_string();
+
+ // Lock Aware Transactional Memory support methods
+ static latm_type const latm_protection();
+ static std::string const latm_protection_str();
+ static void do_full_lock_protection();
+ static void do_tm_lock_protection();
+ static void do_tx_lock_protection();
+ static bool doing_full_lock_protection();
+ static bool doing_tm_lock_protection();
+ static bool doing_tx_lock_protection();
+
+ //in flight transactions
+ static InflightTxes const & in_flight_transactions();
+
+ // transaction
+ transaction();
+ ~transaction();
+
+ bool committed() const;
+ bool aborted() const;
+ bool in_flight() const;
+
+ void begin();
+ bool restart();
+ bool restart_if_not_inflight();
+ void end();
+ void no_throw_end();
+ void force_to_abort();
+ void unforce_to_abort();
+
+ std::size_t const &priority() const;
+ void set_priority(std::size_t const &rhs) const;
+ void raise_priority();
+
+ void make_irrevocable();
+ void make_isolated();
+ bool irrevocable() const;
+ bool isolated() const;
+
+ thread_id_t const & thread_id() const;
+
+
+ template <typename T> T& find_original(T& in);
+
+ template <typename T> T const & read(T const & in);
+ template <typename T> T const * read_ptr(T const * in);
+ template <typename T> T const & r(T const & in);
+
+ template <typename T> T& write(T& in);
+ template <typename T> T* write_ptr(T* in);
+ template <typename T> T& w(T& in);
+
+ template <typename T> T* get_written(T const & in);
+
+ template <typename T> void delete_memory(T &in)
+ template <typename T> T* new_memory();
+ template <typename T> T* new_memory_copy(T const &rhs);
+
+ };
+
+[section Static Function `initialize()`]
+
+ static void initialize();
+
+This method must called before any transaction objects are constructed. The initialize method initializes the overall transaction locking framework.
+
+[endsect]
+[section Static Function `initialize_thread()`]
+
+ static void initialize_thread();
+
+This method must be called for each thread before any transactions are constructed. This method initializes the thread's read and write sets, new and deleted memory sets, mutex locks and thread-based flags.
+
+
+[endsect]
+[section Static Function `terminate_thread()`]
+
+ static void terminate_thread();
+
+This method should be called before destroying a thread. While it is not needed, it will keep transaction operations functioning optimally by reducing static overhead within the transaction class that is no longer needed once a thread's lifetime has ended.
+
+
+[endsect]
+[section Static Function `contention_manager`]
+
+ static void contention_manager(base_contention_manager *rhs);
+
+Sets __Boost_STM__'s contention manager to point to the passed in contention manager. When a new CM is passed in to __Boost_STM__, it deletes the previously pointed to CM and points to the new one. Client code is responsible for constructing new CMs that are passed to this method, but __Boost_STM__ then takes ownership of these CMs.
+
+[endsect]
+[section Static Function `get_contention_manager`]
+
+ static base_contention_manager* get_contention_manager();
+
+Returns a pointer to the current CM used by __Boost_STM__. This method is mostly used for validation purposes after setting a CM to a user-specified implementation.
+
+[endsect]
+[section Static Function `enable_dynamic_priority_assignment`]
+
+ static bool enable_dynamic_priority_assignment();
+
+
+[endsect]
+[section Static Function `disable_dynamic_priority_assignment`]
+
+ static bool disable_dynamic_priority_assignment();
+
+[endsect]
+[section Static Function `doing_dynamic_priority_assignment`]
+
+ static bool doing_dynamic_priority_assignment();
+
+[endsect]
+[section Static Function `enableLoggingOfAbortAndCommitSetSize`]
+
+ static void enableLoggingOfAbortAndCommitSetSize();
+
+[endsect]
+[section Static Function `disableLoggingOfAbortAndCommitSetSize`]
+
+ static void disableLoggingOfAbortAndCommitSetSize();
+
+[endsect]
+[section Static Function `transaction_bookkeeping`]
+
+ static const transaction_bookkeeping & bookkeeping();
+
+[endsect]
+[section Static Function `early_conflict_detection`]
+
+ static bool early_conflict_detection();
+
+Returns true if direct updating is active and early conflict detection, otherwise returns false.
+
+[endsect]
+[section Static Function `late_conflict_detection`]
+
+ static bool late_conflict_detection();
+
+Returns true if deferred updating is active or if direct updating and late conflict detection are active, otherwise returns false.
+
+[endsect]
+[section Static Function `do_early_conflict_detection`]
+
+ static bool do_early_conflict_detection();
+
+Attempts to switch to early conflict detection. Returns false if in-flight transactions are found or if deferred updating is active. Otherwise returns true and enables early conflict detection.
+
+[endsect]
+[section Static Function `do_late_conflict_detection`]
+
+Attempts to switch to late conflict detection. Returns false if in-flight transactions are found, otherwise returns true and enables late conflict detection.
+
+ static bool do_late_conflict_detection();
+
+[endsect]
+[section Static Function `consistency_checking_string`]
+
+ static std::string consistency_checking_string();
+
+[endsect]
+[section Static Function `validating`]
+
+ static bool validating();
+
+[endsect]
+[section Static Function `invalidating`]
+
+ static bool invalidating();
+
+
+[endsect]
+[section Static Function `direct_updating`]
+
+ static bool direct_updating()
+
+Returns true if direct updating is active, otherwise returns false.
+
+[endsect]
+
+[section Static Function `deferred_updating`]
+
+ static bool deferred_updating();
+
+Returns true if deferred updating is active, otherwise returns false
+
+[endsect]
+[section Static Function `do_direct_updating`]
+
+ static bool do_direct_updating();
+
+Attempts to switch to direct updating. Returns false if inflight transactions are found and __Boost_STM__ is unable to switch updating models. Otherwise, returns true and enables direct updating.
+
+[endsect]
+[section Static Function `do_deferred_updating`]
+
+ static bool do_deferred_updating();
+
+Attempts to switch to deferred updating. Returns false if inflight transactions are found and __Boost_STM__ is unable to switch updating models. Otherwise, returns true and enables deferred updating.
+
+[endsect]
+[section Static Function `update_policy_string`]
+
+ static std::string update_policy_string();
+
+
+[endsect]
+[section Static Function `latm_protection`]
+
+ static latm_type const latm_protection();
+
+[endsect]
+[section Static Function `latm_protection_str`]
+
+ static std::string const latm_protection_str();
+
+[endsect]
+[section Static Function `do_full_lock_protection`]
+
+ static void do_full_lock_protection();
+
+[endsect]
+[section Static Function `do_tm_lock_protection`]
+
+ static void do_tm_lock_protection();
+
+[endsect]
+[section Static Function `do_tx_lock_protection`]
+
+ static void do_tx_lock_protection();
+
+[endsect]
+[section Static Function `doing_tx_lock_protection`]
+
+ static bool doing_tx_lock_protection();
+
+[endsect]
+[section Static Function `doing_full_lock_protection`]
+
+ static bool doing_full_lock_protection();
+
+[endsect]
+[section Static Function `doing_tm_lock_protection`]
+
+ static bool doing_tm_lock_protection();
+
+[endsect]
+[section Static Function `in_flight_transactions`]
+
+ static InflightTxes const & in_flight_transactions();
+
+
+[endsect]
+[section Constructor `transaction()`]
+
+ transaction();
+
+Default ctor for a transaction immediately puts the transaction in-flight. In addition, the ctor points referenced members to a number of thread-specific sets which it does by referencing the thread id.
+
+[endsect]
+[section Destructor `~transaction()`]
+
+ ~transaction();
+
+The transaction dtor releases the thread-specific transaction lock if it is obtained. The dtor then immediately returns if the transaction was not in-flight, or if the transaction was in-flight, it forces the transaction to abort which performs a number of clean-up operations.
+
+[endsect]
+[section Member Function `committed`]
+
+States if the state of the transaction is e_committed or e_hand_off
+
+ bool committed() const;
+
+
+[endsect]
+[section Member Function `aborted`]
+
+States if the state of the transaction is e_aborted
+
+ bool aborted() const;
+
+
+[endsect]
+[section Member Function `in_flight`]
+
+States if the state of the transaction is e_in_flight
+
+ bool in_flight() const;
+
+[endsect]
+[section Member Function `begin`]
+
+ void begin();
+
+
+[endsect]
+[section Member Function `restart`]
+
+ bool restart();
+
+This method is similar to the transaction ctor as it signals the start of a transaction and attempts to put it in-flight. A fundamental difference between restart_transaction() and the transaction ctor is that if the transaction is already in-flight, begin_transaction() aborts the transaction and restarts it. This behavior is important for composed transactions where the outer transaction is never destructed, due to continually excepting inner transactions which also prevent the outer transaction from reaching its call to end_transaction(). This is shown concretely in the composable transaction example
+
+[endsect]
+[section Member Function `restart_if_not_inflight`]
+
+ bool restart_if_not_inflight();
+
+[endsect]
+[section Member Function `end`]
+
+ void end();
+
+This method signals that the transaction should try to commit. The return value stored in a transaction_state enumeration is either 1) e_hand_off, meaning the transaction was nested and has handed off its state to the parent transaction or 2) e_committed, meaning the transaction was committed and global memory has been updated. If a transaction is aborted, an aborted_transaction_exception is thrown. A call to end_transaction() will never return an enumerated state which signals the transaction was aborted. Instead, if a transaction is found to be aborted at a call to end_transaction(), an aborted transaction exception is thrown. This behavior enables all aborted transactions to be handled in a similar fashion, resulting in an aborted transaction exception.
+
+[endsect]
+[section Member Function `no_throw_end`]
+
+ void no_throw_end();
+
+Do the same as end() by caching every exception.
+
+[endsect]
+[section Member Function `force_to_abort`]
+
+ void force_to_abort();
+
+[endsect]
+[section Member Function `unforce_to_abort`]
+
+ void unforce_to_abort();
+
+[endsect]
+[section Member Function `priority`]
+
+ std::size_t const &priority() const;
+
+[endsect]
+[section Member Function `set_priority`]
+
+ void set_priority(std::size_t const &rhs) const;
+
+[endsect]
+[section Member Function `raise_priority`]
+
+ void raise_priority();
+
+[endsect]
+[section Member Function `make_irrevocable`]
+
+ void make_irrevocable();
+
+[endsect]
+[section Member Function `make_isolated`]
+
+ void make_isolated();
+
+[endsect]
+[section Member Function `irrevocable`]
+
+ bool irrevocable() const;
+
+[endsect]
+[section Member Function `isolated`]
+
+ bool isolated() const;
+
+[endsect]
+[section Member Function `thread_id`]
+
+ thread_id_t const & thread_id() const;
+
+[endsect]
+[section Template Member Function `find_original<>`]
+
+ template <typename T> T& find_original(T& in);
+
+This method searches the transaction's write list for the original piece of memory referred to by the transactional memory passed in. If the memory passed in is the original global memory it is simply returned. Otherwise, the copied memory passed in, is used to find the original global memory stored in the transaction's write set and then the original memory is returned. While new memory constructed within a transaction can be passed into find_original(), it is not necessary as it always will return a reference to itself. However, to reduce the complexity of client-side code, it may be preferred to build a single method for both new and existing memory address lookup.
+
+[endsect]
+[section Template Function `read<>`]
+
+ template <typename T> T const & read(T const & in);
+ template <typename T> T const & r(T const & in);
+
+
+The read method is used when a transaction is attempting to read a piece of memory that is shared between threads (i.e. global heap space). The input argument is a reference to a derived base_transaction_object instance, the return value reference is the correct base_transaction_object to read based on the current state of the transaction and the currently employed updating policy.
+[endsect]
+
+[section Template Function `read_ptr<>`]
+
+ template <typename T> T const * read_ptr(T const * in);
+
+Identical to the read() interface, except the input parameter is a base_transaction_object pointer as is the return parameter
+
+[endsect]
+[section Template Function `write<>`]
+
+ template <typename T> T& write(T& in);
+ template <typename T> T& w(T& in);
+
+The templatized write method is used when a transaction is attempting to write to a piece of memory that is shared between threads (i.e. global heap space). The input argument is a reference to a derived base_transaction_object instance, the return value reference is the correct base_transaction_object to write to based on the current state of the transaction and the currently employed updating policy.
+
+[endsect]
+
+[section Template Function `write_ptr<>`]
+
+ template <typename T> T* write_ptr(T* in);
+
+Identical to the write() interface, except the input is a base_transaction_object pointer as is the return parameter.
+
+[endsect]
+
+[section Template Function `get_written<>`]
+
+ template <typename T> T* get_written(T const & in);
+
+[endsect]
+[section Template Function `delete_memory<>`]
+
+ template <typename T> void delete_memory(T &in)
+
+This method places the input parameter into a garbage set which is emptied (deleted) once the transaction commits.
+
+[endsect]
+[section Template Function `new_memory<>`]
+
+ template <typename T> T* new_memory();
+
+This method constructs new memory of a derived base_transaction_object type and returns a pointer to the newly allocated memory. While the input template parameter is not used, C++ does not allow functions to differ only by return type. Since different template function instantiations would be constructed here, one per derived base_transaction_object type used within the transaction, a compiler error would be generated for differing return types if an input parameter was not supplied. To overcome this, a void* could be used as the return value, but that would incur client-side casting on the return value, a costly side-effect. To overcome the limitations of C++, while still ensuring strong type-safety, an input parameter which is never referenced is required.
+
+[endsect]
+[section Template Function `new_memory_copy<>`]
+
+ template <typename T> T* new_memory_copy(T const &rhs);
+
+This method behaves similarly to the new_memory() interface except that it makes an exact replica of the input parameter. The return value is a pointer to the newly allocated, replicated object.
+
+[endsect]
+
+[endsect]
+[endsect]

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_bookkeeping.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_bookkeeping.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,87 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+[/==========================================================================================]
+[section:transaction_bookkeeping_hpp Header `<boost/stm/transaction_bookkeeping.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class transaction_bookkeeping
+ }}
+
+
+[section Class `transaction_bookkeeping`]
+
+ class transaction_bookkeeping
+ {
+ public:
+
+ typedef std::map<uint32, uint32> thread_commit_map;
+ typedef std::map<ThreadIdAndCommitId, uint32> CommitHistory;
+ typedef std::map<ThreadIdAndCommitId, uint32> AbortHistory;
+
+ transaction_bookkeeping();
+
+ uint32 const & lockConvoyMs();
+ uint32 const & commitTimeMs();
+ uint32 const & readAborts();
+ uint32 const & writeAborts();
+ uint32 const & abortPermDenied();
+ uint32 const totalAborts() const;
+ uint32 const & commits() const;
+ uint32 const & handOffs() const;
+ uint32 const & newMemoryAborts();
+ uint32 const & newMemoryCommits();
+ uint32 const & deletedMemoryAborts();
+ uint32 const & deletedMemoryCommits();
+ uint32 const & readChangedToWrite() const;
+ uint32 const & readStayedAsRead() const;
+
+ void inc_read_aborts();
+ void inc_write_aborts();
+
+ void inc_thread_commits(uint32 threadId);
+ void inc_thread_aborts(uint32 threadId);
+
+ thread_commit_map const & threadedCommits() const;
+ thread_commit_map const & threadedAborts() const;
+
+ void inc_lock_convoy_ms(uint32 const &rhs);
+ void inc_commit_time_ms(uint32 const &rhs);
+ void inc_commits();
+ void inc_abort_perm_denied(uint32 const &threadId);
+ void inc_handoffs();
+ void inc_new_mem_aborts_by(uint32 const &rhs);
+ void inc_new_mem_commits_by(uint32 const &rhs);
+ void inc_del_mem_aborts_by(uint32 const &rhs);
+ void inc_del_mem_commits_by(uint32 const &rhs);
+ void incrementReadChangedToWrite();
+ void incrementReadStayedAsRead();
+
+ CommitHistory const& getCommitReadSetList() const;
+ CommitHistory const& getCommitWriteSetList() const;
+ AbortHistory const& getAbortReadSetList() const;
+ AbortHistory const& getAbortWriteSetList() const;
+
+ void pushBackSizeOfReadSetWhenAborting(uint32 const &size);
+
+ void pushBackSizeOfWriteSetWhenAborting(uint32 const &size);
+
+ void pushBackSizeOfReadSetWhenCommitting(uint32 const &size);
+ void pushBackSizeOfWriteSetWhenCommitting(uint32 const &size);
+
+ bool isLoggingAbortAndCommitSize() const;
+ void setIsLoggingAbortAndCommitSize(bool const &in);
+
+ friend std::ostream& operator<<(std::ostream& out, transaction_bookkeeping const &that);
+ };
+
+[endsect]
+[endsect]
+
+

Added: sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_object.qbk
==============================================================================
--- (empty file)
+++ sandbox/stm/branches/vbe/libs/stm/doc/reference/transaction_object.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -0,0 +1,89 @@
+[/
+ (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Vicente J. Botet Escriba
+ /
+ / Distributed under the Boost Software License, Version 1.0. (See accompanying
+ / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
+ /]
+
+
+[/==========================================================================================]
+[section:transaction_object_hpp Header `<boost/stm/transaction_object.hpp>`]
+[/==========================================================================================]
+
+ namespace boost { namespace stm {
+ class base_transaction_object;
+ template <class Derived> class transaction_object;
+ template <typename T> class native_trans;
+ }}
+
+[section Abstract Class `base_transaction_object`]
+
+ class base_transaction_object
+ {
+ public:
+
+ base_transaction_object();
+ virtual ~base_transaction_object() {};
+
+ virtual void copy_state(base_transaction_object const * const rhs) = 0;
+ virtual void move_state(base_transaction_object * rhs) = 0;
+
+ void transaction_thread(thread_id rhs) const;
+ thread_id transaction_thread() const;
+
+ void new_memory(bool rhs)
+ bool new_memory() const;
+
+ #if BOOST_STM_PERFORMING_VALIDATION
+ void version(std::size_t rhs);
+ std::size_t version() const;
+ #endif
+
+ };
+
+[endsect]
+
+[section Template Class `transaction_object<>`]
+
+ template <class Derived>
+ class transaction_object : public base_transaction_object {
+ public:
+
+ virtual void copy_state(base_transaction_object const * const rhs);
+ virtual void move_state(base_transaction_object * rhs);
+ };
+
+[endsect]
+
+[section Template Class `native_trans<>`]
+
+ template <typename T> class native_trans : public transaction_object< native_trans<T> > {
+ public:
+ native_trans(){}
+ native_trans(T const &rhs);
+ native_trans(native_trans const &rhs);
+ native_trans(native_trans &&rhs);
+ native_trans& operator=(native_trans &&rhs);
+
+ native_trans& operator=(T const &rhs);
+
+ native_trans& operator--();
+ native_trans operator--(int);
+ native_trans& operator++();
+ native_trans operator++(int);
+ native_trans& operator+=(T const &rhs);
+ native_trans operator+(native_trans const &rhs);
+
+ operator T() const;
+ T& value();
+ T const & value() const;
+ };
+
+[endsect]
+[section Class `base_transaction`]
+
+[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-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -6,13 +6,69 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]
 
+
 [section:ext_references References]
+
+For details on the underlying software architecture of __Boost_STM__, including explanations of its API, please refer to our summary paper.
+
+[variablelist
+
+[
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs/lcsd07-dracostm.pdf [*DracoSTM: A Practical C++ Approach to Software Transactional Memory]]]
+ [Justin E. Gottschlich and Daniel A. Connors -
+ ['Proceedings of the ACM SIGPLAN Symposium on Library-Centric Software Design (LCSD), October 2007] ]
+]
+]
+
+TBoost.STM uses a novel method of consistency checking called invalidation. Invalidation can assist in both high performance and strict contention management control. For more information on how invalidation can improve overall system performance and ensure true user-defined contention management policies, see our below research papers.
+
+[variablelist
+[
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs/podc08_full_paper.pdf [*A Consistency Checking Optimization Algorithm for Memory-Intensive Transactions]]]
+ [Justin E. Gottschlich, Daniel A. Connors and Jeremy G. Siek -
+ ['Proceedings of the ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing (PODC) (brief announcement), August 2008] ] ]
+
+[
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs/epham08-stm.pdf [*Extending Contention Managers for User-Defined Priority Based Transactions]]]
+ [Justin E. Gottschlich and Daniel A. Connors -
+ ['Proceedings of the ACM Workshop on Exploiting Parallelism with Transactional Memory and other Hardware Assisted Methods (EPHAM), April 2008] ]
+]
+]
+
+__Boost_STM__ supports transaction-lock interaction. This support allows existing lock-based parallel code to interact safely with transactions. In addition, we provide three types of transaction-lock interaction with varying degrees of performance. Please see our research paper for more details.
+
 [variablelist
 [
- [ [*Toward Simplified Parallel Support in C++]]
- [Justin E. Gottschlich & Paul J. Rogers, 2009 - Not yet published]
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs/latm.pdf [*Lock-Aware Transactional Memory and Composable Locks]]]
+ [Justin E. Gottschlich, Daniel A. Connors and Jeremy G. Siek -
+ ]
 ]
-
+
+
 ]
 
+__Boost_STM__ uses the last C++ features to provide a friendly and efficient interface. See the following papers to see how.
+
+[variablelist
+[
+ [ [@http://eces.colorado.edu/~gottschl/pubs/boostcon.inter.2009.pdf [*Toward Simplified Parallel Support in C++]]]
+ [Justin E. Gottschlich, Jeremy G. Siek, Paul J. Rogers, and Manish Vachharajani -
+ ['BoostCon'09, the Third Boost Libraries Conference, May 2009] ]
+]
+
+[
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs/icooolps08-exception.pdf [*C++ Move Semantics for Exception Safety and Optimization in Software Transactional Memory Libraries]]]
+ [Justin E. Gottschlich, Jeremy G. Siek and Daniel A. Connors -
+ ['International Workshop on Implementation, Compilation, Optimization of Object-Oriented Languages, Programs and Systems (ICOOOLPS), July 2008]]
+]
+]
+
+Check for the last updates.
+
+[variablelist
+[
+ [ [@http://eces.colorado.edu/~gottschl/tboostSTM/pubs.html [*TBoost.STM (or Related) Peer-Reviewed Publications]]]
+ []
+]
+]
 [endsect]

Modified: sandbox/stm/branches/vbe/libs/stm/doc/stm.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/stm.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/stm.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -6,16 +6,16 @@
  / file LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
  /]
 
-[library Boost.STM
+[library Toward.Boost.STM
     [quickbook 1.3]
     [authors [Gottchlich, Justin E.]]
     [authors [Botet Escriba, Vicente J.]]
     [copyright 2009 Justin E. Gottchlich]
     [copyright 2009 Vicente J. Botet Escriba]
 
- [id boost.synchro]
- [dirname synchro]
- [purpose Concurrent synchronization utilities]
+ [id boost.stm]
+ [dirname stm]
+ [purpose Software Transaction Memory]
     [license
         Distributed under the Boost Software License, Version 1.0.
         (See accompanying file LICENSE_1_0.txt or copy at
@@ -23,6 +23,13 @@
     ]
 ]
 
+
+[def __Boost_STM_s__ TBoost.STM's]
+[def __Boost_STM__ TBoost.STM]
+[def __RSTM__ RSTM]
+[def __TL2__ TL2]
+
+
 [/
 [section Preface]
 

Modified: sandbox/stm/branches/vbe/libs/stm/doc/tutorial.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/tutorial.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/tutorial.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -1,5 +1,5 @@
 [/
- (C) Copyright 2009 Justin E. Gottchlich.
+ (C) Copyright 2009 Justin E. Gottchlich.
   (C) Copyright 2009 Vicente J. Botet Escriba
  /
  / Distributed under the Boost Software License, Version 1.0. (See accompanying
@@ -8,9 +8,450 @@
 
 
 
-[section:tutorial Tutorial]
+[section:tutorial Tutorial]
 
-[/include tutorial/xxx.qbk]
+A number of example transactions are presented in this section using the __Boost_STM__ library. The first example illustrates how to write a transactional linked list insert operation. The second example demonstrates composition, combining a transactional insert operation with a transactional remove operation which compose into a larger, single move transaction. Next, a minor but important detail regarding memory addresses within the transactional workspace is given. Finally, an example of how to handle priority inversion for validating and invalidating consistency schemes using __Boost_STM_s__ extensible contention manager and compositional framework is provided. The final example demonstrates a number of important aspects of __Boost_STM_s__ implementation, such as, differing priority inversion mechanics for different consistency models, transactional attribute enrichment via composition and threaded memory sharing amongst transactions.
 
+While most of the examples are intuitive and a complete understanding of the __Boost_STM__ API is not needed for a high-level understanding of its functionality, a complete description of all interfaces used below can found in referenced section.
+
+
+
+[section A Simple Transaction]
+
+In this example, we build a linked list insert transactional operation using __Boost_STM__. The example is shown in three segments: the client code which inserts 100 items into the list, the insert operation which client code calls, the internal insert operation which the exposed insert operation calls.
+
+[heading Client Invoked Inserts]
+
+ tx_ptr<linked_list<int> > llist;
+ ...
+ atomic(_) {
+ for (int i = 0; i < 100; ++i) {
+ llist->insert(i);
+ }
+ }
+
+After inspecting the above client invoked insert code it is apparent that the code itself shows no deep signs of being transactional. The two exceptions are the declaration of the list using a tx_ptr smart pointer and the fact that the insertion of te 100 elements is atomic. This is our desired behavior. As far as the client side programmer is concerned, there is no additional code needed to perform a transactional linked list insert over a non-transactional linked list insert. Obviously, this simplistic behavior eases the introduction of TM solutions into algorithms of new and legacy systems.
+
+[heading Linked list declaration]
+
+[heading Insert retry transaction]
+
+ void insert(T const &val) {
+ for (boost::stm::transaction _; !_.committed() && _.restart(); _.no_throw_end())
+ try {
+ // ... see below
+ } catch (aborted_transaction_exception&) {}
+ }
+
+The exposed insert code performs two key operations: (1) it retries the transaction until it succeeds (commits) and (2) it catches aborted transaction exceptions. The retry code is perhaps the largest visible section of code overhead for the transactional linked list insert operation. While there are other C++ mechanisms to retry transactions, like gotos or macro-based approaches, we believe a simple loop is currently the best solution for TM retry behavior in C++. Others before us have implemented differing solutions that have smaller code footprints, but violate large-scale design concerns, break compositionality potential and hide or impose large language penalties. As such, we currently accept the loop overhead as a small inconvenience and avoid breaking language semantics.
+
+The aborted_transaction_exception allows __Boost_STM__ to be exception neutral while also gaining performance benefits of early notification of doomed transactions. The above example demonstrates this behavior in practice with its absorption of aborted transactions and only aborted transactions.
+
+[heading Insert specific]
+
+ upgrd_ptr<list_node<T> > prev(_, head_);
+ upgrd_ptr<list_node<T> > curr(_, head_->next_);
+ while (curr) {
+ if (curr->value_ == val) return;
+ else if (curr->value_ > val) break;
+ prev = curr;
+ curr = curr->next_;
+ }
+ if (!curr || (curr->value_ > val)) {
+ make_wr_ptr(_, prev)->next_ =
+ BOOST_STM_NEW(_,transactional_object<list_node<T> >(val, curr));
+ }
+
+The above example illustrates the simplicity of __Boost_STM__ transactions and their interfaces. The transactional implementation is nearly identical to a non-transactional implementation with the exception of some annotations. The templatized functions within the transaction class ensure type-safety is maintained without any necessary type-casts. Due to exact type correctness, as demonstrated in the calls to make_wr_ptr(), daisy-chained method invocation can be performed allowing streamlined usage. These aspects help make __Boost_STM__ transactions small and easy to understand.
+
+One minor, but vital, detail is in way new objects are created on a transactional context. Rather than hide this difference, it is intentionally exposed here to draw out the memory access differences required for writes to new and existing memory. We explain this difference in detail later in this section.
+
+In order to simplify the retry mechanism a macro is provided so the user can just write
+
+ void insert(T const &val) {
+ atomic(_) {
+ upgrd_ptr<list_node<T> > prev(_, head_);
+ upgrd_ptr<list_node<T> > curr(_, head_->next_);
+ while (curr) {
+ if (curr->value_ == val) return;
+ else if (curr->value_ > val) break;
+ prev = curr;
+ curr = curr->next_;
+ }
+ if (!curr || (curr->value_ > val)) {
+ make_wr_ptr(_, prev)->next_ =
+ BOOST_STM_NEW(_,transactional_object<list_node<T> >(val, curr));
+ }
+ }
+ }
+
+
+[endsect]
+
+[section A Composable Transaction]
+
+The below example builds upon the previous example by adding
+a remove operation. We combine the insert and remove operations
+and build a transactional move operation that compose into a single
+transaction. Composition is a key aspect for TM systems. __Boost_STM_s__
+ability to compose transactions from pre-existing transactions
+is fundamental to its design.
+
+In the following example, the first section shows client code
+invoking the move operation. Next, the internal remove operation
+is shown, demonstrating its transactional independence. Last, the
+external move operation is explained, combining the internal insert
+and remove linked list operations resulting in a composed, single
+transaction.
+
+Client Invoked Inserts / Moves.
+
+ tx_ptr<linked_list<int> > llist;
+ ...
+ atomic(_) {
+ for (int i = 0; i < 100; ++i) {
+ llist->insert(i);
+ }
+ for (int j = 0; j < 100; ++j) {
+ llist->move(j, -j);
+ }
+ }
+
+The client invoked inserts and moves are fairly straight forward.
+The insert operations are performed first then the original items are
+moved to a new location by inverting their value. Again, from a
+client programming perspective, there is no hint that this code is
+transactional, which is our intended goal.
+
+Remove
+
+ void remove(const T& val) {
+ use_atomic(_) {
+ // find the node whose val matches the request
+ upgrd_ptr<list_node<T> > prev(_,head_);
+ upgrd_ptr<list_node<T> > curr(_,prev->next_);
+ while (curr) {
+ // if we find the node, disconnect it and end the search
+ if (curr->value_ == val) {
+ make_wr_ptr(_, prev)->next_=curr->next_;
+ delete_ptr(_,curr);
+ break;
+ } else if (curr->value_ > val) {
+ // this means the search failed
+ break;
+ }
+ prev = curr;
+ curr = prev->next_;
+ }
+ }
+ }
+
+As was the case with the insert(), the above
+remove() method is almost identical to how a normal
+linked list remove operation would be implemented, with the
+exception of the atomic guard and a few __Boost_STM__ API calls.
+Again, this is ideal, as it leads to intuitive transactional programming,
+requiring only a minor learning curve for the algorithms
+developer.
+
+Composed External Move
+
+ void move(T const &v1, T const &v2) {
+ use_atomic {
+ remove(v1);
+ insert(v2);
+ }
+ }
+
+The move() implementation do not requires any overhead
+required in non-transactional implementations, other than using the atomic guard.
+The remainder of the code
+
+[endsect]
+
+
+[section A Dynamically Prioritized, Composed Transaction]
+
+The following subsection discusses how priority inversion is handled
+within __Boost_STM__ using dynamic priority assignment. Two solutions
+are presented for the different consistency models, one for
+validation and one for invalidation. Following the two examples
+which detail how to override contention management interfaces,
+a dynamically prioritized transaction is presented, demonstrating
+how transactions interact with the prior implementations.
+Priority inversion in transactional memory occurs when a lower
+priority transaction causes a higher priority transaction to abort.
+With STM lock-based (and non-blocking) systems, priority inversion
+does not happen on the same scale as that of direct lock-based
+solutions. The different cases of priority inversion between direct
+locking solutions and TM solutions are due to TM's natural avoidance
+of critical sections. However, priority inversion in TM can easily
+occur if, for example, a long running transaction is continually
+preempted by shorter running transactions which always commit
+before the longer transaction.
+
+
+In order to prevent such priority inversion scenarios, two extensible
+contention manager (CM) virtual methods are provided
+to allow client-side implementations a way to handle different
+scenarios based on the consistency model currently in use. The
+first interface, abort_before_commit(), allows a user-defined
+contention manager mechanism to abort a transaction before it
+commits. Although __Boost_STM__ does not yet implement validation,
+once it becomes available, client-side validating algorithms
+which want to avoid priority inversion will need to override
+abort_before_commit() to iterate over in-flight transactions and
+abort the current in-process transaction if another in-flight transaction
+exists of higher priority. All in-flight transactions can be accessed
+by a call to in_flight_transactions() which returns
+the set of active transactions. As such, one could build an overridden
+abort_before_commit() which always caused lower priority
+committing transactions to abort in the event a higher priority
+transaction is currently in-flight. One possible implementation is
+shown below. For code simplicity, the following code has removed
+some static class accessors and namespaces.
+
+
+Priority Inversion for Validating Consistency.
+
+ class priority_cm :
+ public core::base_contention_manager {
+ public:
+ // method invoked prior tx commit
+ bool abort_before_commit(transaction const &t) {
+ in_flight_transaction_container::const_iterator i = in_flight_transactions().begin();
+ for (; in_flight_transactions().end() != i; ++i) {
+ if (t.priority() < (*i)->priority()){
+ return true;
+ }
+ }
+ return false;
+ }
+ };
+
+While the above approach is necessary for a validating system,
+it is largely a poor way to perform priority inversion checking.
+Firstly, it has the side-effect of causing unnecessary aborts for
+transactions which do not necessarily conflict, but simply have
+differing priority levels. Secondly, it is slow in that all transactions
+must be walked through each time a transaction commits.
+However, as an ad hoc solution for a validating system, the
+above priority inversion mechanism may be as close to correct
+as is possible. This solution is useful for validation, but should
+never be used for invalidation. Instead a second and more natural
+approach for invalidating systems to prevent priority inversion
+is to override the permission_to_abort() interface. The
+permission_to_abort() interface can only be used when __Boost_STM__
+is performing invalidation.
+
+The permission_to_abort() interface is called from __Boost_STM_s__
+end_transaction() method when a committing transaction
+has found a second transaction it needs to abort for consistency.
+As such, the method takes two parameters, an lhs (lefthand
+side), the committing transaction, and an rhs (right-hand side),
+the transaction requested to be aborted. If permission is granted to
+abort the second transaction, the method returns true and the second
+transaction is aborted. If permission is not granted to abort the
+second transaction, the method returns false and upon returning the
+committing transaction aborts itself. All consistency checking for
+
+
+deferred updating is performed prior to any updating operation and
+thus memory is still in a completely legal uncommitted state until
+all consistency is performed. For direct updating aborts, the system
+simply follows its normal semantics of aborting the transaction by
+restoring global memory to its original state. Similar to the prior
+example, overriding the permission_to_abort() method can be
+done in such a manner which prevents lower priority transaction
+from aborting a higher priority transaction as shown below:
+
+Priority Inversion for Invalidating Consistency.
+
+ class priority_cm :
+ public core::base_contention_manager {
+ public:
+ // method invoked before lhs transaction
+ // aborts rhs transaction
+ bool permission_to_abort(transaction const &lhs,
+ transaction const &rhs) {
+ return lhs.priority() >= rhs.priority();
+ }
+ };
+
+With priority inversion preventable for both validating and invalidating
+consistency modes, transactions now need some mechanism
+to control their priority. __Boost_STM__ allows for such control
+through the raise_priority() interface. By iteratively calling
+raise_priority(), preempted transactions can raise their
+priority at each preemption ensuring their eventual commit. The
+raise_priority() interface is implemented using a size_t
+type. Additionally, __Boost_STM__ supplies a set_priority() interface
+taking a size_t parameter allowing client code to set the
+priority directly.
+
+In order for raise_priority() to function correctly, the affected
+transaction must not be destroyed upon transactional abort.
+If the prioritized transaction is destroyed at each transactional abort,
+raise_priority() will only raise the transaction's priority by
+one each time. In order to demonstrate how raise_priority()
+can be used in practice, we use a wrapper transaction around
+the internal_insert()'s transaction. However, in this case the
+wrapper transaction is not destroyed upon successive iterations.
+The restart_transaction() interface must be called for
+transactions that are not destroyed after being aborted. This necessary
+step clears the state from the previously failed transactional
+run. As shown in the below code, the restart_transaction()
+is only called when an aborted exception is caught. This is because
+end_transaction() throws an exception when the transaction
+is aborted. Following this implementation paradigm, handling
+aborted transactions is relatively straightforward as all aborted
+transactions follow the same exception-based path.
+
+The below example combines all of these aspects together into
+a dynamically prioritized composed transaction. The composition
+is slightly different than what has been shown previously - instead
+of using composition for wrapping two methods into a larger transaction,
+we use composition to override the internal transaction's
+implementation to improve the richness of its behavior, a relatively
+novel concept for composition.
+
+Dynamically Prioritized Composed Transaction.
+
+ bool insert(list_node<T> const &node) {
+ bool success = true;
+ transaction_state s = e_no_state;
+ transaction t;
+ for (; s != e_committed; t.raise_priority()) {
+ try {
+ internal_insert(node, success);
+ s = t.end_transaction();
+ } catch (aborted_transaction_exception&) {
+ t.restart_transaction();
+ }
+ if (!success) return false; // on list
+ }
+ return true;
+ }
+
+The above example demonstrates a number of important concepts
+with __Boost_STM_s__ extensible contention manager and its implementation
+of composition. First, it shows how to avoid priority
+inversion, using dynamically prioritize transactions, in conjunction
+with a prioritized overridden contention manager for both validation
+and invalidation consistency schemes. Second, it demonstrates
+how transactions which are aborted but not destroyed can be
+restarted with the aborted transaction catch clause. Third, the example
+explains how ordinary transactions can be enriched by layering
+composed transactions on top of them without changing the underlying
+original code. Lastly, it reveals some of __Boost_STM_s__ internal
+priority processing which requires a additional amount of explanation,
+as follows.
+
+__Boost_STM_s__ Internal Write-Write Abort Process.
+
+As the above priority assigned transaction demonstrates, the outer transaction
+has increasing priority while the inner transaction, the one
+within internal_insert(), does not. Yet, the inner transaction
+is not aborted due to the outer transaction's priority. This is handled
+internally via __Boost_STM_s__ abort process by two fundamental
+ideas.
+
+# As previously explained, all transactions of the same
+thread share transactional memory, this allows the outer transaction
+to be seen as using the same memory as the inner transaction.
+Thus, when the inner transaction is flagged to be aborted, the outer
+transaction must also be flagged to be aborted as well, since it
+would have the same memory conflicts. However, when checking
+the outer transaction's priority, the contention manager's priority
+method would see the outer transaction as having higher priority
+than the committing transaction if it had already been aborted
+once and the committing transaction had not. The priority analysis
+of the outer transaction compared to the committing transaction
+would thereby force the committing transaction to abort instead of
+the outer transaction.
+
+# __Boost_STM_s__ abort mechanism does not
+abort any transactions until it has walked all transactions, passing
+all the permission_to_abort() checks. Therefore, even if the
+inner transaction is flagged to be aborted, since all transactions
+must be successfully walked in order to abort any transaction, the
+outer transaction's priority will cause the committing transaction
+to abort, thereby saving the inner transaction from being affected.
+An example of this, taken directly from __Boost_STM_s__ implementation,
+is shown below (some code has been removed or shorted to
+simplify the example):
+
+ void abort_conflicting_writes_on_write_set() {
+ trans_list aborted;
+ // iterate through all tx's written memory
+ for (write_set::iterator i = writes().begin(); writes().end() != i; ++i) {
+ // iterate through inflight transactions
+ for (trans::iterator j = inflight_.begin(); inflight_.end() != j; ++j) {
+ transaction *t = (transaction*)*j;
+ // if writing to this write_set, store it
+ if (t->writes().end() != t->writes().find(i->first)) {
+ if (cm_->permission_to_abort(*this, *t))
+ aborted.push_front(t);
+ else
+ throw aborted_transaction_exception("");
+ }
+ }
+ }
+ // ok, forced to aborts are allowed, do them
+ for (trans_list::iterator k = aborted.begin(); aborted.end() != k; ++k) {
+ (*k)->forced_to_abort() = true;
+ }
+ }
+
+Priority Inversion Allowed.
+
+From the above code examples,
+one may question why the default behavior implemented within
+__Boost_STM__ does not automatically integrate priority into transactions,
+as it could be integrated within restart_transaction().
+First, each problem is different and integrating priority only into
+restart_transaction() would not cover all cases (e.g., when
+the outer transaction was terminated). Second, building an automatic
+priority inversion handling scheme would eliminate some of
+the natural optimizations granted from different updating policies.
+For example, deferred updating allows multiple writers of the same
+memory to execute simultaneously. This behavior enables deferred
+updating the ability to process the fastest completing transactions
+first. If a priority system was integrated directly into __Boost_STM__,
+this optimization would be lost. In addition, direct updating optimizes
+writes by writing directly to global memory. As such, direct
+updating suffers greater penalties for aborted transactions due to
+required restoration of global memory. In this case, more transactional
+aborts would occur if __Boost_STM__ built-in a default priority
+inversion handler. Considering these factors, as well as many others,
+__Boost_STM__ does not build transactional priority into its system.
+Instead, we leave this implementation up to client-side implementors,
+as they will have a better understanding of their problem domain
+and be able to more correctly implement the right contention
+manager for their specific needs.
+
+The Future of Parallel Programming.
+
+An important distinction
+regarding priority within transactions versus priority within
+more classical synchronization mechanisms, like locks, is that
+same functional units can be executed simultaneously by different
+threads yielding different priorities. For example, two threads
+can be executing the above insert transaction, one thread which
+has just begun its first run will have a priority of 0, while a second
+transaction which has attempted to run the insert operation 99 times
+previously, would have a priority of 99. The important distinction
+here is that classical critical section synchronization mechanisms
+can have only a single priority per functional unit (e.g., insert,
+remove, lookup operation) due to the innate limitations of single
+thread critical section execution. With transactions, this limitation
+is removed and new concepts of priority begin to emerge. Priority
+inversion can then extend beyond its traditional meaning and
+extend into a new category which incorporates differing priority
+within the same functional unit. These new concepts may reshape
+the way classical parallel problems are thought of in the future,
+especially in relation to transactional memory.
+
+[endsect]
 
 [endsect]

Modified: sandbox/stm/branches/vbe/libs/stm/doc/users_guide.qbk
==============================================================================
--- sandbox/stm/branches/vbe/libs/stm/doc/users_guide.qbk (original)
+++ sandbox/stm/branches/vbe/libs/stm/doc/users_guide.qbk 2009-09-18 13:45:53 EDT (Fri, 18 Sep 2009)
@@ -23,13 +23,25 @@
 
 [variablelist
 
-[[lockable] [.]]
-[[reentrancy] [.]]
-[[lock] [.]]
-[[locker] [.]]
-[[lifetime] [.]]
-[[scope] [.]]
-[[scope] [.]]
+[[in fligh transaction] [.]]
+[[latm] [lock aware transaction memory]]
+[[STM] [Software Transaction Memory]]
+[[Conflict Detection] [.]]
+[[abort] [.]]
+[[commit] [.]]
+[[Consistency Checking] [.]]
+[[Direct Updating] [.]]
+[[Deferred Updating] [.]]
+[[LiT] [.]]
+[[LoT] [.]]
+[[Irrevocable transaction] [.]]
+[[Isolated transaction] [.]]
+[[Full-Lock protection] [.]]
+[[TM-Lock protection] [.]]
+[[TX-Lock protection] [.]]
+[[commit] [.]]
+[[commit] [.]]
+[[commit] [.]]
 ]
 
 [endsect]


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