全部博文（104）
分类：
2008-11-20 17:18:19
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。
