TL2_x86代码的分析（1） - 我的文章 - freearth's blog

http://stamp.stanford.edu

TL2的实现代码很短，而且很容易实际的应用。它不需要修改编译器，不需要特殊的运行时环境的支持等。只要程
序员在编写代码的时候，指定Transaction的开始和结束就好了（编程的附加工作量就像是你有一个全局的锁，
每个线程在访问共享数据的时候，都先取得这个锁一样）。下面是简单的分析了一下它是怎么处理在Transaction
中分配和释放堆内存的。这里，我省去了一个很重要的方面，那就是它怎么保证被一个Transaction释放的内存
不会被其它transaction在后继的时间内访问。这个方面以后再补上吧。

一、TL2提供的几个API(这个是原来的ReleaseNote中的，在现在的版本中可能有变)
    1、TxStart(): 开始一个新的Transaction；
    2、TxLD(), TxST():Transaction中的load和store；
    3、TxCommit():尝试提交当前的Transaction；
    4、TxOnce():只运行一次的全局初始化；
    5、TxNewThread():生成一个新的线程来完成Transaction的操作；

二、在STAMP中是如何使用TL2的
    1、这里，比较重要的两个接口定义文件是tl2/stm.h和stamp/lib/tm.h。正式这两个文件定义了怎么使用tl2。
    2、下面是一个详细的说明和例子:
 * Transactional Memory System Interface
 *
 * TM_ARG(定义为STM_SELF,{Self,})
 * TM_ARG_ALONE(定义为STM_SELF{Self})
 * TM_ARGDECL(定义为STM_THREAD_T* TM_ARG{Thread* Self,})
 * TM_ARGDECL_ALONE(定义为STM_THREAD_T* TM_ARG_ALONE{Thread* Self})
 *     用于将某个TM系统中的线程的原数据传递给函数。
 *
 * TM_STARTUP(numThread)(定义为STM_STARTUP(){TxOnce()}，忽略numThread)
 *     TM系统初始化。
 *
 * TM_SHUTDOWN()(定义为STM_SHUTDOWN(){TxShutdown()})
 *     终止TM系统。
 *
 * TM_THREAD_ENTER()
 *     (定义为
 * TM_ARGDECL_ALONE = STM_NEW_THREAD();STM_INIT_THREAD(TM_ARG_ALONE, thread_getId()){
 *     Thread* Self=TxNewThread();
 *     TxInitThread(Self, thread_getId())
 *     })
 *     在刚刚进入一个并行区(一个新线程)时调用。
 *
 * TM_THREAD_EXIT()(定义为STM_FREE_THREAD(TM_ARG_ALONE){TxFreeThread(Self)})
 *     离开一个并行区(退出一个线程)时调用。
 *
 * P_MALLOC(size)(定义为malloc(size){tmalloc_reserve(size)})
 *     在并行区中分配空间。
 *
 * P_FREE(ptr)(定义为free(ptr){tmalloc_release(ptr)})
 *     在并行区中释放空间。
 *
 * TM_MALLOC(size)(定义为STM_MALLOC(size){TxAlloc(size)})
 *     在Transaction中分配空间。
 *
 * TM_FREE(ptr)(定义为STM_FREE(size){TxFree(size)})
 *     在Transaction中释放空间。
 *
 * TM_BEGIN()(定义为STM_BEGIN_WR(){
 *    do { \
 *              STM_JMPBUF_T STM_JMPBUF; \
 *              int STM_RO_FLAG = 0; \
 *              sigsetjmp(STM_JMPBUF, 1); \
 *              TxStart(STM_SELF, &STM_JMPBUF, &STM_RO_FLAG); \
 *        } while (0) /* enforce comma */
 * })
 *     开始一个Transaction
 *
 * TM_BEGIN_RO()
 *     开始一个只读Transaction，定义类似上面。
 *
 * TM_END()(定义为STM_END(){TxCommit(Self)})
 *     结束(提交)一个Transaction
 *
 * TM_RESTART()(定义为STM_RESTART(){TxAbort(Self)})
 *     重新开始一个Transaction
 *
 * TM_EARLY_RELEASE()
 *    早释放，在tl2中不用。 
 *
 * =============================================================================
 *
 * Example Usage:
 *
 *     MAIN(argc,argv)
 *     {
 *         TM_STARTUP(8);
 *         // create 8 threads and go parallel
 *         TM_SHUTDOWN();
 *     }
 *
 *     void parallel_region ()
 *     {
 *         TM_THREAD_ENTER();
 *         subfunction1(TM_ARG_ALONE);
 *         subfunction2(TM_ARG  1, 2, 3);
 *         TM_THREAD_EXIT();
 *     }
 *
 *     void subfunction1 (TM_ARGDECL_ALONE)
 *     {
 *         TM_BEGIN_RO()
 *         // ... do work that only reads shared data ...
 *         TM_END()
 *
 *         long* array = (long*)P_MALLOC(10 * sizeof(long));
 *         // ... do work ...
 *         P_FREE(array);
 *     }
 *
 *     void subfunction2 (TM_ARGDECL  long a, long b, long c)
 *     {
 *         TM_BEGIN();
 *         long* array = (long*)TM_MALLOC(a * b * c * sizeof(long));
 *         // ... do work that may read or write shared data ...
 *         TM_FREE(array);
 *         TM_END();
 *     }

 三、tl2中堆内存管理的分析
1、首先，我们来分析一下tmalloc的实现。这个是tl2中堆内存管理的基础。
tmalloc是一个为TM包含额外的元信息的堆分配器。先来看两个用到的数据结构。
 * typedef struct tmalloc {
 *     long size; //当前管理了多少个块，每个块用elements中一个指针指向
 *     long capacity; //当前elements中有多少个元素
 *     void** elements;
 * } tmalloc_t;

 * typedef struct tmalloc_info {
 *     size_t size; //所在块的用户数据的大小
 *     char pad[sizeof(long) - sizeof(size_t)];
 * } tmalloc_info_t;

前者tmalloc_t记录了某个分配器整体的信息，而后者则记录了在该分配器中某次分配的一个块的信息。
在分配器中，一个块(block)的开始部分包含了一个tmalloc_info_t类型的原数据，之后就是这个块中包含的
用户数据了。由上面的padding可见，用户数据时long类型对齐的。
2、下面是接口定义:
void* tmalloc_reserve(size_t size)
该函数申请一块大小为size+sizeof(tmalloc_info_t)大小的空间，将头部的tmalloc_info_t信息设置正确(
将其中的size成员设置为参数size)，返回用户数据指针。如果申请失败则返回空。

void* tmalloc_reserveAgain(void *ptr, size_t size)
相当于realloc，成功返回一个新的用户数据大小为size的块的用户数据指针，否则返回空。

void tmalloc_release(void *dataPtr)
将dataPtr所在的块释放。

tmalloc_t* tmalloc_alloc(long initCapacity)
分配一个tmalloc_t类型的管理器，并返回其指针。分配失败返回空。该管理器elements中的元素的个数是
initCapacity个，如果initCapacity是<1，则元素个数是1, size是0.

void tmalloc_free(tmalloc_t *ptr)
释放一个管理器。释放管理器中的elements数组，但是不负责释放数组中元素指向的块。

long tmalloc_append (tmalloc_t* tmallocPtr, void* dataPtr)
将用户数据指针所在的块加入到tmallocPtr指向的管理器elements数组的最后，必要的话可能会扩大该数组。成
功返回1，否则返回0。

void tmalloc_clear (tmalloc_t* tmallocPtr)
将管理器中的size置为0。即，认为管理器没有管理任何块。

void tmalloc_releaseAllForward (tmalloc_t* tmallocPtr, void (*visit)(void*, size_t))
从前向后一次释放tmallocPtr管理的块，如果visit不空的话，在释放前以这个块的用户数据指针和大小为参数调
用visit函数。最后，将管理器的size置为0

void tmalloc_releaseAllReverse (tmalloc_t* tmallocPtr, void (*visit)(void*, size_t))
与上面的函数类似，只是顺序为从后向前。

3、有了上面的结果，我们可以开始分析TL2到底是怎么管理堆内存的了。
在TL2系统中，对于每一个可以并发执行的线程，都要维护该线程的元数据。以下是这个数据结构。其中，我们关
心的是CCM注释的那两个成员。

 *struct _Thread {
 *    long UniqID;     //每个线程独一的ID
 *    volatile long Mode; //该线程目前所处的模式(Tran or Non-trans)
 *    volatile long HoldsLocks; /* passed start of update */
 *    volatile long Retries;
 *    volatile vwLock rv;  //Transaction开始时读取的全局时钟值
 *    vwLock wv;
 *    vwLock abv;
 *    int* ROFlag;
 *    int IsRO;
 *    long Starts;
 *    long Aborts; /* Tally of # of aborts */
 *    unsigned long long rng; //这个和下一个用于随机数产生器
 *    unsigned long long xorrng [1];
 *    void* memCache;
 *    tmalloc_t* allocPtr; /* CCM: 在transaction中分配的内存 */
 *    tmalloc_t* freePtr;  /* CCM: 在transaction中释放的内存 */
 *    Log rdSet;  //本地的ReadSet，下面是WriteSet
 *#ifdef TL2_OPTIM_HASHLOG
 *    HashLog wrSet;
 *#else
 *    Log wrSet;
 *#endif
 *    Log LocalUndo;
 *    sigjmp_buf* envPtr;
 *#ifdef TL2_STATS
 *    long stats[12];
 *    long TxST;
 *    long TxLD;
 *#endif /* TL2_STATS */
 *};

 在刚刚进入一个新的线程的时候，调用TM_THREAD_ENTER()宏，该宏回初始化本thread的Thread数据结构。
首先定义一个Self指针指向本thread的Thread数据结构(通过调用TxNewThread()函数分配)，然后调用
TxInitThread对这个Thread数据结构进行初始化，其中，会分别初始化allocPtr和freePtr两个成员为
capacity为1的tmalloc_t类型的管理器。
在Transaction中，用户程序通过调用
void* TxAlloc(Thread* Self, size_t size)来分配堆内存。该函数通过tmalloc_researve函数分配一个带有头
信息的堆上的块，并把这个块通过tmalloc_append函数添加到Self中的allocPtr所指向的tmalloc_t管理器中。
该函数失败的时候返回空。
在Transaction中，用户程序通过调用
void TxFree(Thread* Self, void* ptr)来释放堆内存。该函数首先通过tmalloc_append()将ptr指向的块添加到
Self的freePtr指向的tmalloc_t管理器中，之后，找出ptr中指针对应的锁，并将地址ptr、它对应的锁和假设的
它的内容0存入本线程的WriteSet中(这样，在成功提交的时候，这个地址对应的锁的版本号会增加，避免未来的
悬挂引用)。在提交成功的时候，freePtr中的东西才会被真的释放掉。在失败的时候，freePtr中的东西不会被释
放掉，相反，allocPtr中的东西会被释放掉。
线程结束的时候，调用TxFreeThread，它就是完成一些统计信息的记录，并释放Thread结构。

四、TL2对于ReadSet和WriteSet的管理
在Thread结构中看到，ReadSet由Log类型的数据结构保存，而WriteSet则可以在编译时选择使用什么结构保存。
1、Log数据结构分析。
首先，我们来看一下ReadSet和WriteSet中的每一个元素的样子:
 *typedef struct _AVPair {
 *    struct _AVPair* Next; //所有的元素构成一个双向链表，这两个成员用于构造链表
 *    struct _AVPair* Prev;
 *    volatile intptr_t* Addr; //该元素对应的地址
 *    intptr_t Valu;           //该元素对应的值
 *    volatile vwLock* LockFor; /* points to the vwLock covering Addr */
 *    vwLock rdv;               /* read-version @ time of 1st read - observed */
 *    struct _Thread* Owner; //该成员所属的线程
 *    long Ordinal;        //该元素的序号(如果在数组中，就是其下标)
 *} AVPair;
 Log数据结构如下
 *typedef struct _Log {
 *    AVPair* List;
 *    AVPair* put;        
 *    AVPair* tail;      
 *    AVPair* end;        
 *    long ovf;           
 *#ifndef TL2_OPTIM_HASHLOG
 *    BitMap BloomFilter; /* Address exclusion fast-path test */
 *#endif
 *} Log;

以下分析针对ReadSet
在初始化一个线程的Thread结构时，会初始化它的ReadSet成员。首先，分配一个固定大小的数组来放所有的
AVPair元素(在数组中也要串成)，该数组由List指向，期望遇到的所有的读元素都可以放到这个数组中，如果
数组用完，仍然需要插入，则在后面使用链表。put表示下一个元素的插入点，tail表示最后一个使用中的元素，
end表示最后一个使用中的元素(仅对数组后的链表有效，当这个链表不存在时为空)。ovf表示数组后的链表中有
多少个元素。
下面分析的时定义了TL2_OPTIM_HASHLOG时的WriteSet(未定义该宏时，WriteSet和ReadSet实现一样)。WriteSet
的数据结构如下，使HashLog:
 *typedef struct _HashLog {
 *    Log* logs;
 *    long numLog;   //在logs数组中一共有多少个Log
 *    long numEntry; //该HashLog中使用中的AVPair项
 *    BitMap BloomFilter; /* Address exclusion fast-path test */
 *} HashLog;
 一个地址addr对应的项被放到logs数组中下标为addr>>2 % numLog的Log数据结构中。此处，对于同一个地址的写
在Log中可能存在多项，这多个项保持FIFO顺序，最后一个项是这个地址的最终得值。
如果WriteSet使用HashLog，则判断一个地址是否存在时使用的是HashLog中的BloomFilter，否则，使用的是Log
中的BloomFilter。