tlds
Transactional Operations for Linked Data Structures
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros
stm Namespace Reference

Namespaces

 iccsync
 

Classes

struct  Object
 
struct  DISPATCH
 
class  BitFilter
 
union  id_version_t
 
struct  orec_t
 
struct  nanorec_t
 
struct  bytelock_t
 
struct  pad_word_t
 
struct  rrec_t
 
struct  bitlock_t
 
struct  toxic_histogram_t
 
struct  toxic_nop_t
 
class  MiniVector
 
struct  TxThread
 
struct  WordLoggingUndoLogEntry
 
struct  ByteLoggingUndoLogEntry
 
class  UndoLog
 
class  WordLoggingValueListEntry
 
class  ByteLoggingValueListEntry
 
struct  ValueList
 
struct  limbo_t
 
class  WBMMPolicy
 
struct  WordLoggingWriteSetEntry
 
struct  ByteLoggingWriteSetEntry
 
class  WriteSet
 
struct  alg_t
 
struct  BackoffCM
 
struct  HyperAggressiveCM
 
struct  FCM
 
struct  StrongHourglassCM
 
struct  HourglassCM
 
struct  HourglassBackoffCM
 
struct  pol_t
 
struct  behavior_t
 
struct  dynprof_t
 
struct  qtable_t
 
struct  AbortWaitTrigger
 
struct  EmptyTrigger
 
struct  CommitTrigger
 
struct  MetaInitializer
 
struct  MetaInitializer< ALG_MAX >
 

Typedefs

typedef void(* AbortHandler )(TxThread *)
 
typedef void scope_t
 
typedef MiniVector< orec_t * > OrecList
 
typedef MiniVector< rrec_t * > RRecList
 
typedef MiniVector< bytelock_t * > ByteLockList
 
typedef MiniVector< bitlock_t * > BitLockList
 
typedef BitFilter< 1024 > filter_t
 
typedef MiniVector< nanorec_tNanorecList
 
typedef MiniVector< void * > AddressList
 
typedef toxic_nop_t toxic_t
 
typedef TM_FASTCALL void *(* ReadBarrier )(STM_READ_SIG(,,))
 
typedef TM_FASTCALL void(* WriteBarrier )(STM_WRITE_SIG(,,,))
 
typedef TM_FASTCALL void(* CommitBarrier )(STM_COMMIT_SIG(,))
 

Enumerations

enum  ALGS {
  CGL = 0, Ticket, TML, RingSW,
  OrecALA, OrecELA, TMLLazy, NOrecPrio,
  OrecFair, CToken, CTokenTurbo, Pipeline,
  BitLazy, LLT, TLI, ByteEager,
  MCS, Serial, BitEager, ByteLazy,
  ByEAR, OrecEagerRedo, ByteEagerRedo, BitEagerRedo,
  RingALA, Nano, Swiss, ByEAU,
  ByEAUFCM, ByEAUHA, ByEAUHour, OrEAU,
  OrEAUFCM, OrEAUHA, OrEAUHour, OrecEager,
  OrecEagerHour, OrecEagerBackoff, OrecEagerHB, OrecLazy,
  OrecLazyHour, OrecLazyBackoff, OrecLazyHB, NOrec,
  NOrecHour, NOrecBackoff, NOrecHB, ProfileTM,
  ProfileAppAvg, ProfileAppMax, ProfileAppAll, ALG_MAX
}
 
enum  POLS {
  Single, PROFILE_NOCHANGE, E, ER,
  R, X, CBR_RO, CBR_Read,
  CBR_Write, CBR_Time, CBR_RW, CBR_R_RO,
  CBR_R_Time, CBR_W_RO, CBR_W_Time, CBR_Time_RO,
  CBR_R_W_RO, CBR_R_W_Time, CBR_R_Time_RO, CBR_W_Time_RO,
  CBR_R_W_Time_RO, CBR_TxnRatio, CBR_TxnRatio_R, CBR_TxnRatio_W,
  CBR_TxnRatio_RO, CBR_TxnRatio_Time, CBR_TxnRatio_RW, CBR_TxnRatio_R_RO,
  CBR_TxnRatio_R_Time, CBR_TxnRatio_W_RO, CBR_TxnRatio_W_Time, CBR_TxnRatio_RO_Time,
  CBR_TxnRatio_RW_RO, CBR_TxnRatio_RW_Time, CBR_TxnRatio_R_RO_Time, CBR_TxnRatio_W_RO_Time,
  CBR_TxnRatio_RW_RO_Time, POL_MAX
}
 

Functions

void set_policy (const char *)
 
const char * get_algname ()
 
TM_INLINE void begin (TxThread *tx, scope_t *s, uint32_t)
 
TM_INLINE void commit (TxThread *tx)
 
void NORETURN UNRECOVERABLE (const char *)
 
void * tx_alloc (size_t size)
 
void tx_free (void *p)
 
void sys_init (void(*abort_handler)(TxThread *)=NULL)
 
void sys_shutdown ()
 
void thread_init ()
 
void thread_shutdown ()
 
bool become_irrevoc (STM_WHEN_PROTECT_STACK(void **top_of_stack))
 
void restart ()
 
template<typename T >
stm_read (T *addr, TxThread *thread)
 
template<typename T >
void stm_write (T *addr, T val, TxThread *thread)
 
void sys_init (AbortHandler conflict_abort)
 
bool is_irrevoc (const TxThread &)
 
void become_irrevoc ()
 
 THREAD_LOCAL_DECL_TYPE (TxThread *) Self
 
filter_t ring_wf[RING_ELEMENTSTM_ALIGN (16)
 
int stm_name_map (const char *phasename)
 
TM_INLINE orec_tget_orec (void *addr)
 
TM_INLINE orec_tget_nanorec (void *addr)
 
TM_INLINE rrec_tget_rrec (void *addr)
 
TM_INLINE bytelock_tget_bytelock (void *addr)
 
TM_INLINE bitlock_tget_bitlock (void *addr)
 
template<int I>
void initTM ()
 
TM_INLINE void exp_backoff (TxThread *tx)
 
TM_FASTCALL bool begin_CGL (TxThread *)
 
void OnReadWriteCommit (TxThread *tx, ReadBarrier read_ro, WriteBarrier write_ro, CommitBarrier commit_ro)
 
void OnReadWriteCommit (TxThread *tx)
 
void OnReadOnlyCommit (TxThread *tx)
 
void OnCGLCommit (TxThread *tx)
 
void OnReadOnlyCGLCommit (TxThread *tx)
 
void OnFirstWrite (TxThread *tx, ReadBarrier read_rw, WriteBarrier write_rw, CommitBarrier commit_rw)
 
void PreRollback (TxThread *tx)
 
scope_tPostRollback (TxThread *tx, ReadBarrier read_ro, WriteBarrier write_ro, CommitBarrier commit_ro)
 
scope_tPostRollback (TxThread *tx)
 
scope_tPostRollbackNoTrigger (TxThread *tx, stm::ReadBarrier r, stm::WriteBarrier w, stm::CommitBarrier c)
 
scope_tPostRollbackNoTrigger (TxThread *tx)
 
void GoTurbo (TxThread *tx, ReadBarrier r, WriteBarrier w, CommitBarrier c)
 
bool CheckTurboMode (TxThread *tx, ReadBarrier read_turbo)
 
template<>
void initTM< BitEager > ()
 
template<>
void initTM< BitEagerRedo > ()
 
template<>
void initTM< BitLazy > ()
 
template<>
void initTM< ByEAR > ()
 
template<>
void initTM< ByteEager > ()
 
template<>
void initTM< ByteEagerRedo > ()
 
template<>
void initTM< ByteLazy > ()
 
template<>
void initTM< CGL > ()
 
template<>
void initTM< CToken > ()
 
template<>
void initTM< CTokenTurbo > ()
 
template<>
void initTM< LLT > ()
 
template<>
void initTM< MCS > ()
 
template<>
void initTM< Nano > ()
 
template<>
void initTM< NOrecPrio > ()
 
template<>
void initTM< OrecALA > ()
 
template<>
void initTM< OrecEagerRedo > ()
 
template<>
void initTM< OrecELA > ()
 
template<>
void initTM< OrecFair > ()
 
template<>
void initTM< Pipeline > ()
 
template<>
void initTM< ProfileTM > ()
 
template<>
void initTM< RingALA > ()
 
template<>
void initTM< RingSW > ()
 
void serial_irrevoc_override (TxThread *tx)
 
template<>
void initTM< Serial > ()
 
template<>
void initTM< Swiss > ()
 
template<>
void initTM< Ticket > ()
 
template<>
void initTM< TLI > ()
 
template<>
void initTM< TML > ()
 
void afterread_TML (TxThread *tx)
 
void beforewrite_TML (TxThread *tx)
 
template<>
void initTM< TMLLazy > ()
 
void install_algorithm_local (int new_alg, TxThread *tx)
 
void install_algorithm (int new_alg, TxThread *tx)
 
void become_irrevoc (STM_WHEN_PROTECT_STACK(void **upper_stack_bound))
 
bool begin_blocker (TxThread *tx)
 
void init_pol_cbr ()
 
void init_pol_static ()
 
int pol_name_map (const char *phasename)
 
void init_adapt_pol (uint32_t PolicyID, int32_t startmode, int32_t abortThresh, int32_t waitThresh, bool isDynamic, bool isCBR, bool isCommitProfile, uint32_t TM_FASTCALL(*decider)(), const char *name)
 
void pol_init (const char *mode)
 
TM_INLINE unsigned long long get_nontxtime ()
 
void init_adapt_pol (uint32_t PolicyID, int32_t startmode, int32_t abortThresh, int32_t waitThresh, bool isDynamic, bool isCBR, bool isCommitProfile, uint32_t(*decider)() TM_FASTCALL, const char *name)
 
void profile_oncomplete (TxThread *tx)
 
void trigger_common (TxThread *tx)
 
void sys_init (stm::AbortHandler conflict_abort_handler)
 

Variables

pad_word_t threadcount = {0}
 
TxThreadthreads [MAX_THREADS] = {0}
 
static const unsigned MAX_THREADS = 256
 
union stm::id_version_t TM_ALIGN
 
pad_word_t trans_nums [MAX_THREADS] = {{0}}
 
pad_word_t timestamp = {0}
 
pad_word_t timestamp_max = {0}
 
orec_t orecs [NUM_STRIPES] = {{{{0}}}}
 
orec_t nanorecs [RING_ELEMENTS] = {{{{0}}}}
 
pad_word_t last_complete = {0}
 
pad_word_t last_init = {0}
 
pad_word_t prioTxCount = {0}
 
rrec_t rrecs [RREC_COUNT] = {{{0}}}
 
bytelock_t bytelocks [NUM_STRIPES] = {{0}}
 
bitlock_t bitlocks [NUM_STRIPES] = {{0}}
 
pad_word_t epochs [MAX_THREADS] = {{0}}
 
pad_word_t greedy_ts = {0}
 
mcs_qnode_tmcslock = NULL
 
ticket_lock_t ticketlock = {0}
 
pad_word_t fcm_timestamp = {0}
 
alg_t stms [ALG_MAX]
 
dynprof_tapp_profiles = NULL
 
uint32_t profile_txns = 1
 
dynprof_tprofiles = NULL
 
static const uint32_t NUM_STRIPES = 1048576
 
static const uint32_t RING_ELEMENTS = 1024
 
static const uint32_t KARMA_FACTOR = 16
 
static const uint32_t BACKOFF_MIN = 4
 
static const uint32_t BACKOFF_MAX = 16
 
static const uint32_t RREC_COUNT = 1048576
 
static const uint32_t WB_CHUNK_SIZE = 16
 
static const uint32_t EPOCH_MAX = INT_MAX
 
static const uint32_t ACTIVE = 0
 
static const uint32_t ABORTED = 1
 
static const uint32_t SWISS_PHASE2 = 10
 
pol_t pols [POL_MAX]
 
behavior_t curr_policy
 
MiniVector< qtable_t > * qtbl [MAX_THREADS+1] = {NULL}
 

Detailed Description

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information This file presents a simple library API for using RSTM without compiler support. The API consists of the following:

TM_ALLOC : Allocate memory inside a transaction TM_FREE : Deallocate memory inside a transaction TM_SYS_INIT : Initialize the STM library TM_SYS_SHUTDOWN : Shut down the STM library TM_THREAD_INIT : Initialize a thread before using TM TM_THREAD_SHUTDOWN : Shut down a thread TM_SET_POLICY(P) : Change the STM algorithm on the fly TM_BECOME_IRREVOC() : Become irrevocable or abort TM_READ(var) : Read from shared memory from a txn TM_WRITE(var, val) : Write to shared memory from a txn TM_BEGIN(type) : Start a transaction... use 'atomic' as type TM_END : End a transaction

Custom Features:

stm::restart() : Self-abort and immediately retry a txn TM_BEGIN_FAST_INITIALIZATION : For fast initialization TM_END_FAST_INITIALIZATION : For fast initialization TM_GET_ALGNAME() : Get the current algorithm name

Compiler Compatibility::Transaction Descriptor Management:

TM_GET_THREAD() : for getting the thread's descriptor, if needed TM_ARG_ALONE : for passing descriptors to transactional functions TM_ARG : (same) TM_PARAM : (same) TM_PARAM_ALONE : (same)

Compiler Compatibility::Annotations (unused in library):

TM_WAIVER : mark a block that does not get TM instrumentation TM_CALLABLE : mark a function as being callable by TM

Now we can make simple macros for reading and writing shared memory, by using templates to dispatch to the right code:

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information In the LIBRARY api, the transformation of reads and writes of addresses into correctly formed calls to the tmread and tmwrite functions is achieved through a set of templates. The role of the templates is to allow a single library call to be transformed into the right instructions to read at any supported size/type, even though the library itself only provides word-level read/write functions.

This file presents those templates, to reduce clutter in the main library.hpp file.

This file should be included in the middle of the library file. It has no includes of its own.

Also, BE WARNED: this implementation of the library API allows "granular lost updates". If transaction A writes a single char, and thread B writes an adjacent char, then B's write could be lost.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information In this file, we declare functions and variables that need to be visible to many parts of the STM library, but that do not need to be visible to application code.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information The global metadata types used by our STM implementations are defined in this file, along with many of the types used by the TxThread object of logging the progress of a transaction.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information A simple vector-like templated collection object. The main difference from the STL vector is that we can force uncommon code (such as resize) to be a function call by putting instantiations of the expand() method into their own .o file.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information Definitions for a common environment for all our STM implementations. The TxThread object holds all the metadata that a thread needs.

In addition, this file declares the thread-local pointer that a thread can use to access its TxThread object.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information Implement an undo log so that we can centralize all logic for stack-filtering and abort/throw behavior in in-place update STMs An undo log is a pretty simple structure. We never need to search it, so its only purpose is to store stuff and write stuff out when we abort. It's split out into its own class in order to deal with the configuration-based behavior that we need it to observe, like byte-accesses, stack protection, etc.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information We use the ValueList class to log address/value pairs for our value-based-validation implementations—NOrec and NOrecPrio currently. We generally log things at word granularity, and during validation we check to see if any of the bits in the word has changed since the word was originally read. If they have, then we have a conflict.

This word-granularity continues to be correct when we have enabled byte logging (because we're building for C++ TM compatibility), but it introduces the possibility of byte-level false conflicts. One of VBV's advantages is that there are no false conflicts. In order to preserve this behavior, we offer the user the option to use the byte-mask (which is already enabled for byte logging) to do byte-granularity validation. The disadvantage to this technique is that the read log entry size is increased by the size of the stored mask (we could optimize for 64-bit Linux and pack the mask into an unused part of the logged address, but we don't yet have this capability).

This file implements the value log given the current configuration settings in stm/config.h

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information In order to get allocation and deallocation to work correctly inside of a speculative transactional region, we need to be sure that a doomed transaction cannot access memory that has been returned to the OS.

WBMMPolicy is RSTM's variant of epoch-based reclamation. It is similar to proposals by [Fraser PhD 2003] and [Hudson ISMM 2006].

Note that this file has real code in it, and that code gets inlined into many places. It's not pretty, and we may eventually want to reduce the footprint of this file on the rest of the project.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information The RSTM backends that use redo logs all rely on this datastructure, which provides O(1) clear, insert, and lookup by maintaining a hashed index into a vector.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information This file declares global metadata that is used by all STM algorithms, along with some accessor functions

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information In order to support inlining of TML instrumentation, we must make some metadata and implementation code visible in this file. It is provided below:

Define the CM policies that can be plugged into our framework. For the time being, these only make sense in the context of attacker-wins conflict management

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information This file implements the code for switching installing an algorithm.

Copyright (C) 2011 University of Rochester Department of Computer Science and Lehigh University Department of Computer Science and Engineering

License: Modified BSD Please see the file LICENSE.RSTM for licensing information This code handles the profiling mechanism. It consists of three parts:

  • The code for requesting that a bunch of profiles are collected
  • The code for calling a policy after the profiles are collected, and using that result to change the algorithm
  • The code that is called on every commit/abort by any transaction, to determine when a request should be initiated

Typedef Documentation

typedef void(* stm::AbortHandler)(TxThread *)
typedef MiniVector<void*> stm::AddressList
typedef MiniVector<bitlock_t*> stm::BitLockList
typedef MiniVector<bytelock_t*> stm::ByteLockList
typedef TM_FASTCALL void(* stm::CommitBarrier)(STM_COMMIT_SIG(,))
typedef BitFilter<1024> stm::filter_t
typedef MiniVector<nanorec_t> stm::NanorecList
typedef MiniVector<orec_t*> stm::OrecList

Common TypeDefs

typedef TM_FASTCALL void*(* stm::ReadBarrier)(STM_READ_SIG(,,))
typedef MiniVector<rrec_t*> stm::RRecList
typedef void stm::scope_t

A scope_t is an opaque type used by an API to unwind.

typedef toxic_nop_t stm::toxic_t
typedef TM_FASTCALL void(* stm::WriteBarrier)(STM_WRITE_SIG(,,,))

Enumeration Type Documentation

enum stm::ALGS

The ALGS enum lists every STM algorithm we have

Enumerator
CGL 
Ticket 
TML 
RingSW 
OrecALA 
OrecELA 
TMLLazy 
NOrecPrio 
OrecFair 
CToken 
CTokenTurbo 
Pipeline 
BitLazy 
LLT 
TLI 
ByteEager 
MCS 
Serial 
BitEager 
ByteLazy 
ByEAR 
OrecEagerRedo 
ByteEagerRedo 
BitEagerRedo 
RingALA 
Nano 
Swiss 
ByEAU 
ByEAUFCM 
ByEAUHA 
ByEAUHour 
OrEAU 
OrEAUFCM 
OrEAUHA 
OrEAUHour 
OrecEager 
OrecEagerHour 
OrecEagerBackoff 
OrecEagerHB 
OrecLazy 
OrecLazyHour 
OrecLazyBackoff 
OrecLazyHB 
NOrec 
NOrecHour 
NOrecBackoff 
NOrecHB 
ProfileTM 
ProfileAppAvg 
ProfileAppMax 
ProfileAppAll 
ALG_MAX 
enum stm::POLS

The POLS enum lists every adaptive policy we have

Enumerator
Single 
PROFILE_NOCHANGE 
E 
ER 
R 
X 
CBR_RO 
CBR_Read 
CBR_Write 
CBR_Time 
CBR_RW 
CBR_R_RO 
CBR_R_Time 
CBR_W_RO 
CBR_W_Time 
CBR_Time_RO 
CBR_R_W_RO 
CBR_R_W_Time 
CBR_R_Time_RO 
CBR_W_Time_RO 
CBR_R_W_Time_RO 
CBR_TxnRatio 
CBR_TxnRatio_R 
CBR_TxnRatio_W 
CBR_TxnRatio_RO 
CBR_TxnRatio_Time 
CBR_TxnRatio_RW 
CBR_TxnRatio_R_RO 
CBR_TxnRatio_R_Time 
CBR_TxnRatio_W_RO 
CBR_TxnRatio_W_Time 
CBR_TxnRatio_RO_Time 
CBR_TxnRatio_RW_RO 
CBR_TxnRatio_RW_Time 
CBR_TxnRatio_R_RO_Time 
CBR_TxnRatio_W_RO_Time 
CBR_TxnRatio_RW_RO_Time 
POL_MAX 

Function Documentation

void stm::afterread_TML ( TxThread *  tx)
inline

TML requires this to be called after every read

void stm::become_irrevoc ( )
void stm::become_irrevoc ( STM_WHEN_PROTECT_STACK(void **upper_stack_bound)  )

Try to become irrevocable, inflight. This happens via mode switching. If the inflight irrevocability fails, we fall-back to an abort-and-restart-as-irrevocable scheme, based on the understanding that the begin_blocker tmbegin barrier will configure us as irrevocable and let us through if we have our irrevocable flag set. In addition to letting us through, it will set our barrier pointers to be the irrevocable barriers—it has to be done here because the rollback that the abort triggers will reset anything we try and set here.

Here is the call graph for this function:

bool stm::become_irrevoc ( STM_WHEN_PROTECT_STACK(void **top_of_stack)  )

Try to become irrevocable. Call this from within a transaction.

Here is the caller graph for this function:

void stm::beforewrite_TML ( TxThread *  tx)
inline

TML requires this to be called before every write

Here is the caller graph for this function:

TM_INLINE void stm::begin ( TxThread *  tx,
scope_t *  s,
uint32_t   
)
inline

Code to start a transaction. We assume the caller already performed a setjmp, and is passing a valid setjmp buffer to this function.

The code to begin a transaction could all live on the far side of a function pointer. By putting some of the code into this inlined function, we can:

(a) avoid overhead under subsumption nesting and (b) avoid code duplication or MACRO nastiness

Here is the caller graph for this function:

bool stm::begin_blocker ( TxThread tx)

Custom begin method that blocks the starting thread, in order to get rendezvous correct during mode switching and GRL irrevocability. It doubles as an irrevocability mechanism for implementations where we don't have (or can't write) an in-flight irrevocability mechanism.

custom begin method that blocks the starting thread, in order to get rendezvous correct during mode switching and GRL irrevocability (implemented in irrevocability.cpp because it uses some static functions declared there)

Here is the call graph for this function:

Here is the caller graph for this function:

bool stm::begin_CGL ( TxThread tx)

CGL begin:

We grab the lock, but we count how long we had to spin, so that we can possibly adapt after releasing the lock.

This is external and declared in algs.hpp so that we can access it as a default in places.

Here is the call graph for this function:

Here is the caller graph for this function:

bool stm::CheckTurboMode ( TxThread *  tx,
ReadBarrier  read_turbo 
)
inline
TM_INLINE void stm::commit ( TxThread *  tx)
inline

Code to commit a transaction. As in begin(), we are using forced inlining to save a little bit of overhead for subsumption nesting, and to prevent code duplication.

Here is the caller graph for this function:

TM_INLINE void stm::exp_backoff ( TxThread *  tx)
inline

A simple implementation of randomized exponential backoff.

NB: This uses getElapsedTime, which is slow compared to a granularity of 64 nops. However, we can't switch to tick(), because sometimes two successive tick() calls return the same value?

Here is the call graph for this function:

Here is the caller graph for this function:

const char * stm::get_algname ( )

Return the name of the algorithm with which the library was configured

TM_INLINE bitlock_t* stm::get_bitlock ( void *  addr)
inline

Map addresses to bitlock table entries

TM_INLINE bytelock_t* stm::get_bytelock ( void *  addr)
inline

Map addresses to bytelock table entries

TM_INLINE orec_t* stm::get_nanorec ( void *  addr)
inline

Map addresses to nanorec table entries

TM_INLINE unsigned long long stm::get_nontxtime ( )
inline

Helper function. This is a terrible thing, and one we must get rid of, especially since we are calling it far more often than we should!

Here is the caller graph for this function:

TM_INLINE orec_t* stm::get_orec ( void *  addr)
inline

These simple functions are used for common operations on the global metadata arrays Map addresses to orec table entries

Here is the caller graph for this function:

TM_INLINE rrec_t* stm::get_rrec ( void *  addr)
inline

Map addresses to rrec table entries

void stm::GoTurbo ( TxThread *  tx,
ReadBarrier  r,
WriteBarrier  w,
CommitBarrier  c 
)
inline
void stm::init_adapt_pol ( uint32_t  PolicyID,
int32_t  startmode,
int32_t  abortThresh,
int32_t  waitThresh,
bool  isDynamic,
bool  isCBR,
bool  isCommitProfile,
uint32_t TM_FASTCALL(*)()  decider,
const char *  name 
)

This helper function lets us easily configure our STM adaptivity policies. The idea is that an adaptive policy can get most of its configuration from the info in its starting state, and the rest of the information is easy to provide

Here is the caller graph for this function:

void stm::init_adapt_pol ( uint32_t  PolicyID,
int32_t  startmode,
int32_t  abortThresh,
int32_t  waitThresh,
bool  isDynamic,
bool  isCBR,
bool  isCommitProfile,
uint32_t(*)() TM_FASTCALL  decider,
const char *  name 
)
void stm::init_pol_cbr ( )

Here is the call graph for this function:

Here is the caller graph for this function:

void stm::init_pol_static ( )

To avoid excessive declarations in internal.hpp, we use this function to initialize all the policies declared in this file

Here is the call graph for this function:

Here is the caller graph for this function:

template<int I>
void stm::initTM ( )

We don't want to have to declare an init function for each of the STM algorithms that exist, because there are very many of them and they vary dynamically. Instead, we have a templated init function in namespace stm, and we instantiate it once per algorithm, in the algorithm's .cpp, using the ALGS enum. Then we can just call the templated functions from this code, and the linker will find the corresponding instantiation.

template<>
void stm::initTM< BitEager > ( )

BitEager initialization

Here is the call graph for this function:

template<>
void stm::initTM< BitEagerRedo > ( )

BitEagerRedo initialization

Here is the call graph for this function:

template<>
void stm::initTM< BitLazy > ( )

BitLazy initialization

Here is the call graph for this function:

template<>
void stm::initTM< ByEAR > ( )

ByEAR initialization

Here is the call graph for this function:

template<>
void stm::initTM< ByteEager > ( )

ByteEager initialization

Here is the call graph for this function:

template<>
void stm::initTM< ByteEagerRedo > ( )

ByteEagerRedo initialization

Here is the call graph for this function:

template<>
void stm::initTM< ByteLazy > ( )

ByteLazy initialization

Here is the call graph for this function:

template<>
void stm::initTM< CGL > ( )

CGL initialization

Here is the call graph for this function:

template<>
void stm::initTM< CToken > ( )

CToken initialization

Here is the call graph for this function:

template<>
void stm::initTM< CTokenTurbo > ( )

CTokenTurbo initialization

Here is the call graph for this function:

template<>
void stm::initTM< LLT > ( )

LLT initialization

Here is the call graph for this function:

template<>
void stm::initTM< MCS > ( )

MCS initialization

Here is the call graph for this function:

template<>
void stm::initTM< Nano > ( )

Nano initialization

Here is the call graph for this function:

template<>
void stm::initTM< NOrecPrio > ( )

NOrecPrio initialization

Here is the call graph for this function:

template<>
void stm::initTM< OrecALA > ( )

OrecALA initialization

Here is the call graph for this function:

template<>
void stm::initTM< OrecEagerRedo > ( )

OrecEagerRedo initialization

Here is the call graph for this function:

template<>
void stm::initTM< OrecELA > ( )

OrecELA initialization

Here is the call graph for this function:

template<>
void stm::initTM< OrecFair > ( )

OrecFair initialization

Here is the call graph for this function:

template<>
void stm::initTM< Pipeline > ( )

Pipeline initialization

Here is the call graph for this function:

template<>
void stm::initTM< ProfileTM > ( )

ProfileTM initialization

Here is the call graph for this function:

template<>
void stm::initTM< RingALA > ( )

RingALA initialization

Here is the call graph for this function:

template<>
void stm::initTM< RingSW > ( )

RingSW initialization

Here is the call graph for this function:

template<>
void stm::initTM< Serial > ( )

Serial initialization

Here is the call graph for this function:

template<>
void stm::initTM< Swiss > ( )

Every STM must provide an 'initialize' function that specifies how the algorithm is to be used when adaptivity is off.

Some of this is a bit ugly right now, but when we fix the way adaptive policies work it will clean itself.

Here is the call graph for this function:

template<>
void stm::initTM< Ticket > ( )

Ticket initialization

Here is the call graph for this function:

template<>
void stm::initTM< TLI > ( )

TLI initialization

Here is the call graph for this function:

template<>
void stm::initTM< TML > ( )

Here is the call graph for this function:

template<>
void stm::initTM< TMLLazy > ( )

TMLLazy initialization

Here is the call graph for this function:

void stm::install_algorithm ( int  new_alg,
TxThread *  tx 
)

Switch all threads to use a new STM algorithm.

Logically, there is an invariant that nobody is in a transaction. This is not easy to define, though, because a thread may call this with a non-null scope, which is our "in transaction" flag. In practice, such a thread is calling install_algorithm from the end of either its abort or commit code, so it is 'not in a transaction'

Another, and more important invariant, is that the caller must have personally installed begin_blocker. There are three reasons to install begin_blocker: irrevocability, thread creation, and mode switching. Each of those actions, independently, can only be done by one thread at a time. Furthermore, no two of those actions can be done simultaneously.

Here is the caller graph for this function:

void stm::install_algorithm_local ( int  new_alg,
TxThread *  tx 
)

Here is the caller graph for this function:

bool stm::is_irrevoc ( const TxThread tx)

True if the current algorithm is irrevocable.

void stm::OnCGLCommit ( TxThread *  tx)
inline

Here is the call graph for this function:

void stm::OnFirstWrite ( TxThread *  tx,
ReadBarrier  read_rw,
WriteBarrier  write_rw,
CommitBarrier  commit_rw 
)
inline

Here is the caller graph for this function:

void stm::OnReadOnlyCGLCommit ( TxThread *  tx)
inline

Here is the call graph for this function:

void stm::OnReadOnlyCommit ( TxThread *  tx)
inline

Here is the call graph for this function:

Here is the caller graph for this function:

void stm::OnReadWriteCommit ( TxThread *  tx,
ReadBarrier  read_ro,
WriteBarrier  write_ro,
CommitBarrier  commit_ro 
)
inline

Here is the call graph for this function:

Here is the caller graph for this function:

void stm::OnReadWriteCommit ( TxThread *  tx)
inline

Here is the call graph for this function:

void stm::pol_init ( const char *  mode)

Here is the call graph for this function:

Here is the caller graph for this function:

int stm::pol_name_map ( const char *  phasename)

Just like stm_name_map, we sometimes need to turn a policy name into its corresponding enum value

Here is the caller graph for this function:

scope_t* stm::PostRollback ( TxThread *  tx,
ReadBarrier  read_ro,
WriteBarrier  write_ro,
CommitBarrier  commit_ro 
)
inline

Here is the call graph for this function:

Here is the caller graph for this function:

scope_t* stm::PostRollback ( TxThread *  tx)
inline

Here is the call graph for this function:

scope_t* stm::PostRollbackNoTrigger ( TxThread *  tx,
stm::ReadBarrier  r,
stm::WriteBarrier  w,
stm::CommitBarrier  c 
)
inline

Custom PostRollback code for ProfileTM. If a transaction other than the last in the profile set aborts, we roll it back using this function, which does everything the prior PostRollback did except for calling the "Trigger::onAbort()" method.

Here is the call graph for this function:

scope_t* stm::PostRollbackNoTrigger ( TxThread *  tx)
inline

Custom PostRollback code for ProfileTM. If the last transaction in the profile set aborts, it will call profile_oncomplete before calling this. That means that it will adapt /out of/ ProfileTM, which in turn means that we cannot reset the pointers on abort.

Here is the call graph for this function:

void stm::PreRollback ( TxThread *  tx)
inline

Here is the caller graph for this function:

void stm::profile_oncomplete ( TxThread tx)

When a ProfileTM transaction commits, we end up in this code, which calls the current policy's 'decider' to pick the new algorithm, and then sets up metadata and makes the switch.

Here is the call graph for this function:

void stm::restart ( )

Abort the current transaction and restart immediately.

Simplified support for self-abort

void stm::serial_irrevoc_override ( TxThread tx)

As mentioned above, Serial needs a custom override to work with irrevocability.

The 'Serial' algorithm requires a custom override for irrevocability, which we implement here.

Here is the call graph for this function:

Here is the caller graph for this function:

void stm::set_policy ( const char *  phasename)

Set the current STM algorithm/policy. This should be called at the beginning of each program phase

for parsing input to determine the valid algorithms for a phase of execution.

Setting a policy is a lot like changing algorithms, but requires a little bit of custom synchronization

Here is the call graph for this function:

Here is the caller graph for this function:

int32_t stm::stm_name_map ( const char *  phasename)

Here is the caller graph for this function:

template<typename T >
T stm::stm_read ( T *  addr,
TxThread *  thread 
)
inline
template<typename T >
void stm::stm_write ( T *  addr,
val,
TxThread *  thread 
)
inline
void stm::sys_init ( AbortHandler  conflict_abort)
void stm::sys_init ( void(*)(TxThread *)  abort_handler = NULL)

Here we declare the rest of the api to the STM library Initialize the library (call before doing any per-thread initialization)

We rely on the default setjmp/longjmp abort handling when using the library API.

Here is the caller graph for this function:

void stm::sys_init ( stm::AbortHandler  conflict_abort_handler)

Initialize the TM system.

Here is the call graph for this function:

void stm::sys_shutdown ( )

Shut down the library. This just dumps some statistics.

When the transactional system gets shut down, we call this to dump stats

Here is the call graph for this function:

Here is the caller graph for this function:

void stm::thread_init ( )
inline

Here is the call graph for this function:

Here is the caller graph for this function:

stm::THREAD_LOCAL_DECL_TYPE ( TxThread *  )
void stm::thread_shutdown ( )
inline

Here is the caller graph for this function:

filter_t ring_wf [RING_ELEMENTS] stm::TM_ALIGN ( 16  )
void stm::trigger_common ( TxThread tx)

This is the code for deciding whether to adapt or not. It's a little bit messy because we want to limit what gets inlined. part 1: the thing that never gets inlined, and only gets called if we are definitely going to adapt

Here is the call graph for this function:

Here is the caller graph for this function:

void* stm::tx_alloc ( size_t  size)
inline

This portion of the API addresses allocation. We provide tx-safe malloc and free calls, which also work from nontransactional contexts. get a chunk of memory that will be automatically reclaimed if the caller is a transaction that ultimately aborts

Here is the caller graph for this function:

void stm::tx_free ( void *  p)
inline

Free some memory. If the caller is a transaction that ultimately aborts, the free will not happen. If the caller is a transaction that commits, the free will happen at commit time.

Here is the caller graph for this function:

void stm::UNRECOVERABLE ( const char *  msg)

The STM system provides a message that exits the program (preferable to 'assert(false)'). We use this in the API too, so it needs to be visible here

Here is the caller graph for this function:

Variable Documentation

const uint32_t stm::ABORTED = 1
static
const uint32_t stm::ACTIVE = 0
static
dynprof_t * stm::app_profiles = NULL
const uint32_t stm::BACKOFF_MAX = 16
static
const uint32_t stm::BACKOFF_MIN = 4
static
bitlock_t stm::bitlocks = {{0}}
bytelock_t stm::bytelocks = {{0}}
behavior_t stm::curr_policy
const uint32_t stm::EPOCH_MAX = INT_MAX
static
pad_word_t stm::epochs = {{0}}
pad_word_t stm::fcm_timestamp = {0}
pad_word_t stm::greedy_ts = {0}
const uint32_t stm::KARMA_FACTOR = 16
static
pad_word_t stm::last_complete = {0}
pad_word_t stm::last_init = {0}
const unsigned stm::MAX_THREADS = 256
static

Many of our data structures benefit from having a cap on the number of threads. Here we set that cap at 256

mcs_qnode_t * stm::mcslock = NULL
orec_t stm::nanorecs = {{{{0}}}}
const uint32_t stm::NUM_STRIPES = 1048576
static

These constants are used throughout the STM implementations

orec_t stm::orecs = {{{{0}}}}
pol_t stm::pols

Store the STM algorithms and adaptivity policies, so we can select one at will. The selected one is in curr_policy.

These globals are used by our adaptivity policies

pad_word_t stm::prioTxCount = {0}
uint32_t stm::profile_txns = 1
dynprof_t * stm::profiles = NULL
MiniVector< qtable_t > * stm::qtbl = {NULL}
const uint32_t stm::RING_ELEMENTS = 1024
static
const uint32_t stm::RREC_COUNT = 1048576
static
rrec_t stm::rrecs = {{{0}}}
alg_t stm::stms

These describe all our STM algorithms and adaptivity policies

const uint32_t stm::SWISS_PHASE2 = 10
static
pad_word_t stm::threadcount = {0}
TxThread * stm::threads = {0}
ticket_lock_t stm::ticketlock = {0}
pad_word_t stm::timestamp = {0}

This is the Orec Timestamp, the NOrec/TML seqlock, the CGL lock, and the RingSW ring index

These global fields are used for concurrency control and conflict detection in our STM systems

pad_word_t stm::timestamp_max = {0}

Sometimes we use the Timestamp not as a counter, but as a bool. If we want to switch back to using it as a counter, we need to know what the old value was. This holds the old value.

This is only used within STM implementations, to log and recover the value

union stm::id_version_t stm::TM_ALIGN
pad_word_t stm::trans_nums = {{0}}
const uint32_t stm::WB_CHUNK_SIZE = 16
static