From a831b57ca9bf0c42e5158660b64d4c25c3a674fc Mon Sep 17 00:00:00 2001 From: bdemsky Date: Fri, 30 Oct 2009 09:35:57 +0000 Subject: [PATCH] bug fixes --- Robust/src/Runtime/STM/array.h | 33 +++---- Robust/src/Runtime/STM/commit.c | 139 ++++++++++++++++++++--------- Robust/src/Runtime/STM/delaycomp.h | 4 +- Robust/src/Runtime/STM/stm.c | 29 ++++-- Robust/src/Runtime/STM/stmlock.h | 9 +- Robust/src/Runtime/STM/stmlookup.c | 10 +-- Robust/src/Runtime/garbage.c | 7 +- 7 files changed, 153 insertions(+), 78 deletions(-) diff --git a/Robust/src/Runtime/STM/array.h b/Robust/src/Runtime/STM/array.h index 23aaa18f..d4ecd73f 100644 --- a/Robust/src/Runtime/STM/array.h +++ b/Robust/src/Runtime/STM/array.h @@ -34,36 +34,39 @@ } #define STMGETARRAY(dst, array, index, type) { \ - int byteindex=index*sizeof(type); \ - int * lengthoff=&array->___length___; \ if (((char *)array)!=((char *)array->___objlocation___)) { \ if(!(array->___objstatus___&NEW)) { \ + int byteindex=index*sizeof(type); \ int *status; \ - GETLOCKPTR(status, array, byteindex>>INDEXSHIFT); \ - if ((*status)==STMNONE) { \ + int metaindex=(byteindex&HIGHMASK)>>INDEXSHIFT; \ + GETLOCKPTR(status, array, metaindex); \ + if (metaindexlowindex||metaindex>array->highindex \ + ||(*status)==STMNONE) { \ arraycopy(array, byteindex); \ - *status=STMCLEAN;} \ + (*status)=STMCLEAN;} \ } \ } \ - dst=((type *)(((char *) lengthoff)+sizeof(int)))[index]; \ + dst=((type *)(((char *) &array->___length___)+sizeof(int)))[index]; \ } #define STMSETARRAY(array, index, src, type) { \ - int byteindex=index*sizeof(type); \ - int * lengthoff=&array->___length___; \ if (!(array->___objstatus___&NEW)) { \ int *status; \ - GETLOCKPTR(status, array, byteindex>>INDEXSHIFT); \ - if ((*status)==STMNONE) \ + int byteindex=index*sizeof(type); \ + int metaindex=(byteindex&HIGHMASK)>>INDEXSHIFT; \ + GETLOCKPTR(status, array, metaindex); \ + if (metaindexlowindex||metaindex>array->highindex \ + ||(*status)==STMNONE) { \ arraycopy(array, byteindex); \ - *status=STMDIRTY; \ + } \ + (*status)=STMDIRTY; \ } \ - ((type *)(((char *) lengthoff)+sizeof(int)))[index]=src; \ + ((type *)(((char *) &array->___length___)+sizeof(int)))[index]=src; \ } #endif -#define VERSIONINCREMENT(array, index, type) { \ - unsigned int * versionptr; \ +#define VERSIONINCREMENT(array, index, type) { \ + unsigned int * versionptr; \ GETVERSIONPTR(versionptr, array,((sizeof(type)*index)>>INDEXSHIFT)); \ - (*versionptr)++; \ + (*versionptr)++; \ } diff --git a/Robust/src/Runtime/STM/commit.c b/Robust/src/Runtime/STM/commit.c index 8e47228d..f7272674 100644 --- a/Robust/src/Runtime/STM/commit.c +++ b/Robust/src/Runtime/STM/commit.c @@ -61,12 +61,12 @@ int transCommit() { /* Look through all the objects in the transaction hash table */ int finalResponse; #ifdef DELAYCOMP - if (c_numelements<(c_size>>3)) + if (c_numelements<(c_size>>1)) finalResponse=alttraverseCache(commitmethod, primitives, locals, params); else finalResponse=traverseCache(commitmethod, primitives, locals, params); #else - if (c_numelements<(c_size>>3)) + if (c_numelements<(c_size>>1)) finalResponse=alttraverseCache(); else finalResponse=traverseCache(); @@ -278,6 +278,14 @@ int transCommit() { else \ return TRANS_ABORT; +#define ABORTREAD \ + transAbortProcess(oidwrlocked, numoidwrtotal ARRAYDELAYWRAP1(dirwrindex) ARRAYDELAYWRAP1(numoidwrlocked)); \ + freearrays; \ + if (softabort) \ + return TRANS_SOFT_ABORT; \ + else \ + return TRANS_ABORT; + #define ARRAYABORT \ for(;j>=lowoffset;j--) { \ @@ -290,23 +298,30 @@ int transCommit() { ABORT #ifdef DUALVIEW -#define DVGETLOCK(x) \ - unsigned int * objlock=&(&((objheader_t *)x)[-1])->lock; \ - if(!rwread_trylock(objlock)) { \ - ABORT; \ +#define DVGETLOCK(x) if (!addwrobject) { \ + unsigned int * objlock=&(&((objheader_t *)x)[-1])->lock; \ + if(!rwread_trylock(objlock)) { \ + ABORT; \ + } \ +} + +#define DVRELEASELOCK(x) { \ + unsigned int * objlock=&(&((objheader_t *)x)[-1])->lock; \ + rwread_unlock(objlock); \ } //not finished...if we can't get the lock, it is okay if it is in our access set #define DVCHECKLOCK(x) \ - unsigned int * objlock=&(&((objheader_t *)x)[-1])->lock; \ + unsigned int * objlock=&(&((objheader_t *)x)[-1])->lock; \ if (objlock<=0) { \ if (dc_t_chashSearch(x)==NULL) { \ - ABORT; \ + ABORTREAD; \ } \ } #else #define DVGETLOCK(x) #define DVCHECKLOCK(x) +#define DVRELEASELOCK(x) #endif #if defined(DELAYCOMP)&&!defined(DUALVIEW) @@ -332,15 +347,15 @@ int transCommit() { if (type>=NUMCLASSES) { \ struct ArrayObject *transao=(struct ArrayObject *) cachedobj; \ struct ArrayObject *mainao=(struct ArrayObject *) objptr; \ - DVGETLOCK(mainao); \ - int lowoffset=(transao->lowindex)>>INDEXSHIFT; \ - int highoffset=(transao->highindex)>>INDEXSHIFT; \ + int lowoffset=(transao->lowindex); \ + int highoffset=(transao->highindex); \ int j; \ int addwrobject=0, addrdobject=0; \ for(j=lowoffset; j<=highoffset;j++) { \ unsigned int status; \ GETLOCKVAL(status, transao, j); \ if (status==STMDIRTY) { \ + DVGETLOCK(mainao); \ unsigned int * lockptr; \ GETLOCKPTR(lockptr, mainao,j); \ if (likely(write_trylock(lockptr))) { \ @@ -351,10 +366,12 @@ int transCommit() { if (likely(localversion == remoteversion)) { \ addwrobject=1; \ } else { \ + DVRELEASELOCK(mainao); \ ARRAYABORT; \ } \ } else { \ j--; \ + DVRELEASELOCK(mainao); \ ARRAYABORT; \ } \ } else if (status==STMCLEAN) { \ @@ -363,20 +380,32 @@ int transCommit() { } \ if (addwrobject) { \ dirwrlocked[numoidwrlocked++] = objptr; \ - DUALVIEWWRAP(transao->___objstatus___ |=DIRTY;) \ - } \ + } \ if (addrdobject) { \ oidrdlockedarray[numoidrdlockedarray++]=objptr; \ } \ } else + +#ifdef DUALVIEW +#define QUICKCHECK { \ + objheader_t * head=&((objheader_t *)mainao)[-1]; \ + if (head->lock==RW_LOCK_BIAS&& \ + ((objheader_t *)transao)[-1].version==head->version) \ + continue; \ + } +#else +#define QUICKCHECK +#endif + #define READARRAYS \ for(i=0; i___objlocation___; \ + QUICKCHECK; \ DVCHECKLOCK(mainao); \ - int lowoffset=(transao->lowindex)>>INDEXSHIFT; \ - int highoffset=(transao->highindex)>>INDEXSHIFT; \ + int lowoffset=(transao->lowindex); \ + int highoffset=(transao->highindex); \ int j; \ for(j=lowoffset; j<=highoffset;j++) { \ unsigned int locallock;GETLOCKVAL(locallock,transao,j); \ @@ -455,8 +484,8 @@ int transCommit() { #elif defined(STMARRAY)&&defined(DUALVIEW) #define ARRAYLOCK \ if (((struct ___Object___ *)objptr)->type>=NUMCLASSES) { \ - if (!rwwrite_trylock(&header->lock)) { \ - ARRAYDELAYWRAP(dirwrindex[numoidwrtotal]=0;); \ + if (likely(rwwrite_trylock(&header->lock))) { \ + dirwrindex[numoidwrtotal]=0; \ dirwrlocked[numoidwrtotal++] = objptr; \ } else { \ chashlistnode_t *node = &c_table[(((unsigned INTPTR)objptr) & c_mask)>>4]; \ @@ -464,8 +493,8 @@ int transCommit() { if(node->key == objptr) { \ objheader_t * headeraddr=&((objheader_t *) node->val)[-1]; \ if(STATUS(headeraddr) & DIRTY) { \ - if (rwconvert_trylock(&header->lock)) { \ - ARRAYDELAYWRAP(dirwrindex[numoidwrtotal]=1;); \ + if (likely(rwconvert_trylock(&header->lock))) { \ + dirwrindex[numoidwrtotal]=1; \ dirwrlocked[numoidwrtotal++] = objptr; \ goto nextloop; \ } \ @@ -474,7 +503,7 @@ int transCommit() { } \ node = node->next; \ } while(node != NULL); \ - ABORT; \ + ABORTREAD; \ } \ } else #else @@ -577,9 +606,8 @@ int traverseCache() { objheader_t *header=(objheader_t *)(((char *)objptr)-sizeof(objheader_t)); //real object unsigned int version = headeraddr->version; - PROCESSARRAY; - if(STATUS(headeraddr) & DIRTY) { + PROCESSARRAY /* Read from the main heap and compare versions */ if(likely(write_trylock(&header->lock))) { //can aquire write lock if (likely(version == header->version)) { /* versions match */ @@ -668,9 +696,16 @@ int traverseCache() { while(likely(rd_curr != NULL)) { //if the first bin in hash table is empty unsigned int version=rd_curr->version; - objheader_t *header=(objheader_t *)(((char *)rd_curr->key)-sizeof(objheader_t)); - if(header->lock>0) { //object is not locked - if (version!=header->version) { + struct ___Object___ * objptr=rd_curr->key; + objheader_t *header=(objheader_t *)(((char *)objptr)-sizeof(objheader_t)); +#ifdef STMARRAY + int isobject=objptr->typelock>0)||(!isobject&&header->lock==RW_LOCK_BIAS))) { +#else + if(header->lock>0) { +#endif + //object is not locked + if (unlikely(version!=header->version)) { //have to abort transAbortProcess(oidwrlocked, NUMWRTOTAL ARRAYDELAYWRAP1(dirwrindex) ARRAYDELAYWRAP1(numoidwrlocked)); STMWRAP((typesCausingAbort[TYPE(header)])++;); @@ -678,25 +713,30 @@ int traverseCache() { if (softabort) return TRANS_SOFT_ABORT; else - return TRANS_ABORT; + return TRANS_ABORT; } } else { //maybe we already have lock - if (version==header->version) { + if (likely(version==header->version)) { void * key=rd_curr->key; #ifdef DELAYCOMP //check to see if it is in the delaycomp table { dchashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>4]; do { - if(node->key == key) + if(node->key == key) { goto nextloopread; + } node = node->next; } while(node != NULL); } #endif //check normal table +#ifdef STMARRAY + if (likely(isobject||header->lock==(RW_LOCK_BIAS-1))) { +#else { +#endif chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4]; do { if(node->key == key) { @@ -777,9 +817,8 @@ int alttraverseCache() { objheader_t *header=(objheader_t *)(((char *)objptr)-sizeof(objheader_t)); unsigned int version = headeraddr->version; - PROCESSARRAY; - if(STATUS(headeraddr) & DIRTY) { + PROCESSARRAY /* Read from the main heap and compare versions */ if(likely(write_trylock(&header->lock))) { //can aquire write lock if (likely(version == header->version)) { /* versions match */ @@ -821,9 +860,9 @@ int alttraverseCache() { for(i=0; ilock>0) { + if(likely(header->lock>0)) { CFENCE; - if(version != header->version) { + if(unlikely(version != header->version)) { transAbortProcess(oidwrlocked, NUMWRTOTAL ARRAYDELAYWRAP1(dirwrindex) ARRAYDELAYWRAP1(numoidwrlocked)); ABORTSTAT2; freearrays; @@ -861,9 +900,15 @@ int alttraverseCache() { while(likely(rd_curr != NULL)) { //if the first bin in hash table is empty int version=rd_curr->version; - objheader_t *header=(objheader_t *)(((char *)rd_curr->key)-sizeof(objheader_t)); - if(header->lock>0) { //object is not locked - if (version!=header->version) { + struct ___Object___ * objptr=rd_curr->key; + objheader_t *header=(objheader_t *)(((char *)objptr)-sizeof(objheader_t)); +#ifdef STMARRAY + int isobject=objptr->typelock>0)||(!isobject&&header->lock==RW_LOCK_BIAS))) { +#else + if(likely(header->lock>0)) { //object is not locked +#endif + if (unlikely(version!=header->version)) { //have to abort transAbortProcess(oidwrlocked, NUMWRTOTAL ARRAYDELAYWRAP1(dirwrindex) ARRAYDELAYWRAP1(numoidwrlocked)); STMWRAP((typesCausingAbort[TYPE(header)])++;); @@ -888,7 +933,11 @@ int alttraverseCache() { } #endif //check normal table - { +#ifdef STMARRAY + if (likely(isobject||header->lock==(RW_LOCK_BIAS-1))) { +#else + { +#endif chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4]; do { if(node->key == key) { @@ -952,8 +1001,8 @@ void transAbortProcess(struct garbagelist *oidwrlocked, int numoidwrlocked) { if (type>=NUMCLASSES) { //have array, do unlocking of bins struct ArrayObject *src=(struct ArrayObject *)t_chashSearch(dst); - int lowoffset=(src->lowindex)>>INDEXSHIFT; - int highoffset=(src->highindex)>>INDEXSHIFT; + int lowoffset=(src->lowindex); + int highoffset=(src->highindex); int j; int addwrobject=0, addrdobject=0; for(j=lowoffset; j<=highoffset;j++) { @@ -1060,8 +1109,8 @@ void transCommitProcess(struct garbagelist * oidwrlocked, int numoidwrlocked) { int type=dst->type; if (type>=NUMCLASSES) { //have array, do copying of bins - int lowoffset=(((struct ArrayObject *)src)->lowindex)>>INDEXSHIFT; - int highoffset=(((struct ArrayObject *)src)->highindex)>>INDEXSHIFT; + int lowoffset=(((struct ArrayObject *)src)->lowindex); + int highoffset=(((struct ArrayObject *)src)->highindex); int j; int addwrobject=0, addrdobject=0; int elementsize=classsize[type]; @@ -1111,8 +1160,8 @@ void transCommitProcess(struct garbagelist * oidwrlocked, int numoidwrlocked) { if (type>=NUMCLASSES) { //have array, do unlocking of bins struct ArrayObject *src=(struct ArrayObject *)t_chashSearch(dst); - int lowoffset=(src->lowindex)>>INDEXSHIFT; - int highoffset=(src->highindex)>>INDEXSHIFT; + int lowoffset=(src->lowindex); + int highoffset=(src->highindex); int j; int addwrobject=0, addrdobject=0; for(j=lowoffset; j<=highoffset;j++) { @@ -1126,6 +1175,7 @@ void transCommitProcess(struct garbagelist * oidwrlocked, int numoidwrlocked) { write_unlock(intptr); } } + atomic_inc(&header->version); #ifdef DUALVIEW rwread_unlock(&header->lock); #endif @@ -1143,13 +1193,13 @@ void transCommitProcess(struct garbagelist * oidwrlocked, int numoidwrlocked) { int wrlock=dirwrindex[i]; header = &((objheader_t *)dst)[-1]; if (wrlock==-1) { - //problem...what if we are double locked header->version++; write_unlock(&header->lock); } else if (wrlock==0) { + header->version++; rwwrite_unlock(&header->lock); } else { - //normal object + header->version++; rwconvert_unlock(&header->lock); } } @@ -1167,6 +1217,7 @@ void transCommitProcess(struct garbagelist * oidwrlocked, int numoidwrlocked) { } else { //array element unsigned int *intptr; + atomic_inc(&header->version); GETVERSIONPTR(intptr, ((struct ArrayObject *)dst), wrindex); (*intptr)++; GETLOCKPTR(intptr, ((struct ArrayObject *)dst), wrindex); diff --git a/Robust/src/Runtime/STM/delaycomp.h b/Robust/src/Runtime/STM/delaycomp.h index 4f5d9588..c5657cfc 100644 --- a/Robust/src/Runtime/STM/delaycomp.h +++ b/Robust/src/Runtime/STM/delaycomp.h @@ -69,9 +69,9 @@ extern __thread struct arraylist arraystack; //Branches -#define RESTOREANDBRANCH(loc) if (branchstack.array[branchstack.count++]) goto loc +#define RESTOREBRANCH(loc) (branchstack.array[branchstack.count++]) -#define STOREANDBRANCH(cond, loc) if (branchstack.array[branchstack.count++]=cond) goto loc +#define STOREBRANCH(cond) branchstack.array[branchstack.count++]=cond //Integers diff --git a/Robust/src/Runtime/STM/stm.c b/Robust/src/Runtime/STM/stm.c index fb37e3f2..1faa91f1 100644 --- a/Robust/src/Runtime/STM/stm.c +++ b/Robust/src/Runtime/STM/stm.c @@ -175,7 +175,7 @@ void *transRead(void * oid, void *gl) { int metasize=sizeof(int)*2*(basesize>>INDEXSHIFT); size = basesize + sizeof(objheader_t)+metasize+sizeof(struct ArrayObject); char *tmpptr = (char *) objstrAlloc(size); - bzero(tmpptr, metasize);//clear out stm data + // bzero(tmpptr, metasize);//clear out stm data objcopy=(objheader_t *) (tmpptr+metasize); A_memcpy(objcopy, header, sizeof(objheader_t)+sizeof(struct ArrayObject)); //copy the metadata and base array info } else { @@ -210,13 +210,32 @@ void *transRead(void * oid, void *gl) { int baseoffset=byteindex&HIGHMASK; unsigned int mainversion; int baseindex=baseoffset>>INDEXSHIFT; + if (oid->lowindex>baseindex) { + unsigned int * ptr; + if (oid->lowindex==MAXARRAYSIZE) { + GETLOCKPTR(ptr, oid, baseindex); + bzero(ptr, sizeof(int)*2); + } else { + GETLOCKPTR(ptr, oid, oid->lowindex-1); + int length=oid->lowindex-baseindex; + bzero(ptr, sizeof(int)*2*length); + } + oid->lowindex=baseindex; + } + if (oid->highindexhighindex==-1) { + GETLOCKPTR(ptr, oid, baseindex); + bzero(ptr, 2*sizeof(int)); + } else { + GETLOCKPTR(ptr, oid, baseindex); + bzero(ptr, 2*sizeof(int)*(baseindex-oid->highindex)); + } + oid->highindex=baseindex; + } GETVERSIONVAL(mainversion, orig, baseindex); SETVERSION(oid, baseindex, mainversion); A_memcpy(((char *)&oid[1])+baseoffset, ((char *)&orig[1])+baseoffset, INDEXLENGTH); - if (oid->lowindex>baseoffset) - oid->lowindex=baseoffset; - if (oid->highindexhighindex=baseoffset; } #endif diff --git a/Robust/src/Runtime/STM/stmlock.h b/Robust/src/Runtime/STM/stmlock.h index 19230fe4..1898f2de 100644 --- a/Robust/src/Runtime/STM/stmlock.h +++ b/Robust/src/Runtime/STM/stmlock.h @@ -1,6 +1,9 @@ #ifndef _STMLOCK_H_ #define _STMLOCK_H_ +#define likely(x) __builtin_expect((x),1) +#define unlikely(x) __builtin_expect((x),0) + #define SWAP_LOCK_BIAS 1 #define CFENCE asm volatile("":::"memory"); @@ -80,14 +83,14 @@ static inline int atomic_sub_and_test(int i, volatile unsigned int *v) { static inline int rwread_trylock(volatile unsigned int *lock) { atomic_dec(lock); - if (atomic_read(lock) >= 0) + if (likely(atomic_read(lock) >= 0)) return 1; //can aquire a new read lock atomic_inc(lock); return 0; //failure } static inline int rwwrite_trylock(volatile unsigned int *lock) { - if (atomic_sub_and_test(RW_LOCK_BIAS, lock)) { + if (likely(atomic_sub_and_test(RW_LOCK_BIAS, lock))) { return 1; // get a write lock } atomic_add(RW_LOCK_BIAS, lock); @@ -95,7 +98,7 @@ static inline int rwwrite_trylock(volatile unsigned int *lock) { } static inline int rwconvert_trylock(volatile unsigned int *lock) { - if (atomic_sub_and_test((RW_LOCK_BIAS-1), lock)) { + if (likely(atomic_sub_and_test((RW_LOCK_BIAS-1), lock))) { return 1; // get a write lock } atomic_add((RW_LOCK_BIAS-1), lock); diff --git a/Robust/src/Runtime/STM/stmlookup.c b/Robust/src/Runtime/STM/stmlookup.c index 97131b30..e8f5d562 100644 --- a/Robust/src/Runtime/STM/stmlookup.c +++ b/Robust/src/Runtime/STM/stmlookup.c @@ -261,18 +261,18 @@ void dc_t_chashreset() { void dc_t_chashInsertOnce(void * key, void *val) { dchashlistnode_t *ptr; - if (key==NULL) + if (unlikely(key==NULL)) { return; + } - if(dc_c_numelements > (dc_c_threshold)) { + if(unlikely(dc_c_numelements > dc_c_threshold)) { //Resize unsigned int newsize = dc_c_size << 1; dc_t_chashResize(newsize); } ptr = &dc_c_table[(((unsigned INTPTR)key)&dc_c_mask)>>4]; - - if(ptr->key==0) { + if(likely(ptr->key==0)) { ptr->key=key; ptr->val=val; #if defined(STMARRAY)&&!defined(DUALVIEW) @@ -294,7 +294,7 @@ void dc_t_chashInsertOnce(void * key, void *val) { } while(search != NULL); dc_c_numelements++; - if (dc_c_structs->numnumarray[dc_c_structs->num]; dc_c_structs->num++; } else { diff --git a/Robust/src/Runtime/garbage.c b/Robust/src/Runtime/garbage.c index 7255a357..1bc6c255 100644 --- a/Robust/src/Runtime/garbage.c +++ b/Robust/src/Runtime/garbage.c @@ -201,14 +201,13 @@ void fixtable(chashlistnode_t ** tc_table, chashlistnode_t **tc_list, cliststruc int i; SENQUEUE((void *)ao->___objlocation___, *((void **)&ao->___objlocation___)); #ifdef STMARRAY - int lowindex=ao->lowindex>>INDEXSHIFT; - int highind=ao->highindex; - int highindex=(highind==-1)?-1:(highind>>INDEXSHIFT); + int lowindex=ao->lowindex; + int highindex=ao->highindex; int j; for(j=lowindex; j<=highindex; j++) { unsigned int lockval; GETLOCKVAL(lockval, ao, j); - if (lockval==STMDIRTY) { + if (lockval!=STMNONE) { int lowi=(j<