Robust/src/Runtime/DSTM/interface_recovery/singleTMCommit.c

   1 /* ============================================================
   2  * singleTMCommit.c
   3  * - single thread commit on local machine
   4  * =============================================================
   5  * Copyright (c) 2009, University of California, Irvine, USA.
   6  * All rights reserved.
   7  * Author: Alokika Dash
   8  *         adash@uci.edu
   9  * =============================================================
  10  *
  11  */
  12
  13 #include "tm.h"
  14 #include "garbage.h"
  15 #define likely(x) x
  16 /* Per thread transaction variables */
  17 __thread objstr_t *t_cache;
  18 __thread objstr_t *t_reserve;
  19 __thread struct objlist * newobjs;
  20
  21 #ifdef DELAYCOMP
  22 #include "delaycomp.h"
  23 __thread struct pointerlist ptrstack;
  24 __thread struct primitivelist primstack;
  25 __thread struct branchlist branchstack;
  26 struct pointerlist *c_ptrstack;
  27 struct primitivelist *c_primstack;
  28 struct branchlist *c_branchstack;
  29 #endif
  30
  31 #ifdef TRANSSTATS
  32 int numTransCommit = 0;
  33 int numTransAbort = 0;
  34 int nSoftAbort = 0;
  35 int nSoftAbortCommit = 0;
  36 int nSoftAbortAbort = 0;
  37 #endif
  38
  39 #ifdef STMSTATS
  40 int timeInMS ()
  41 {
  42   struct timeval t;
  43
  44   gettimeofday(&t, NULL);
  45   return (
  46       (int)t.tv_sec * 1000000 +
  47       (int)t.tv_usec
  48       );
  49 }
  50 /* Thread variable for locking/unlocking */
  51 __thread threadrec_t *trec;
  52 __thread struct objlist * lockedobjs;
  53 __thread int t_objnumcount=0;
  54
  55 /* Collect stats for object classes causing abort */
  56 objtypestat_t typesCausingAbort[TOTALNUMCLASSANDARRAY];
  57 /******Keep track of objects and types causing aborts******/
  58 /* TODO uncomment for later use
  59 #define DEBUGSTMSTAT(args...) { \
  60   printf(args); \
  61   fflush(stdout); \
  62 }
  63 */
  64
  65 /**
  66  * Inline fuction to get Transaction size per object type for those
  67  * objects that cause
  68  *
  69  **/
  70 INLINE void getTransSize(objheader_t *header , int *isObjTypeTraverse) {
  71   (typesCausingAbort[TYPE(header)]).numabort++;
  72   if(isObjTypeTraverse[TYPE(header)] != 1) {
  73     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
  74     (typesCausingAbort[TYPE(header)]).numtrans+=1; //should this count be kept per object
  75   }
  76   isObjTypeTraverse[TYPE(header)]=1;
  77 }
  78 #define DEBUGSTMSTAT(args...)
  79 #else
  80 #define DEBUGSTMSTAT(args...)
  81 #endif
  82
  83 #ifdef STMDEBUG
  84 #define DEBUGSTM(x...) printf(x);
  85 #else
  86 #define DEBUGSTM(x...);
  87 #endif
  88
  89 #ifdef STATDEBUG
  90 #define DEBUGSTATS(x...) printf(x);
  91 #else
  92 #define DEBUGSTATS(x...);
  93 #endif
  94
  95 //#ifdef FASTMEMCPY
  96 //void * A_memcpy (void * dest, const void * src, size_t count);
  97 //#else
  98 //#define A_memcpy memcpy
  99 //#endif
 100
 101 void * A_memcpy (void * dest, const void * src, size_t count) {
 102   int off=0;
 103   INTPTR *desti=(INTPTR *)dest;
 104   INTPTR *srci=(INTPTR *)src;
 105
 106   //word copy
 107   while(count>=sizeof(INTPTR)) {
 108     desti[off]=srci[off];
 109     off+=1;
 110     count-=sizeof(INTPTR);
 111   }
 112   off*=sizeof(INTPTR);
 113   //byte copy
 114   while(count>0) {
 115     ((char *)dest)[off]=((char *)src)[off];
 116     off++;
 117     count--;
 118   }
 119 }
 120
 121
 122 extern void * curr_heapbase;
 123 extern void * curr_heapptr;
 124 extern void * curr_heaptop;
 125
 126 #ifdef STMSTATS
 127 /*** Global variables *****/
 128 objlockstate_t *objlockscope;
 129 /**
 130  * ABORTCOUNT
 131  * params: object header
 132  * Increments the abort count for each object
 133  **/
 134 void ABORTCOUNT(objheader_t * x) {
 135   int avgTransSize = typesCausingAbort[TYPE(x)].numaccess / typesCausingAbort[TYPE(x)].numtrans;
 136   float transAbortProbForObj = (PERCENT_ALLOWED_ABORT*FACTOR)/(float) avgTransSize;
 137   float ObjAbortProb = x->abortCount/(float) (x->accessCount);
 138   DEBUGSTM("ABORTSTATS: oid= %x, type= %2d, transAbortProb= %2.2f, ObjAbortProb= %2.2f, Typenumaccess= %3d, avgtranssize = %2d, ObjabortCount= %2d, ObjaccessCount= %3d\n", OID(x), TYPE(x), transAbortProbForObj, ObjAbortProb, typesCausingAbort[TYPE(x)].numaccess, avgTransSize, x->abortCount, x->accessCount);
 139   /* Condition for locking objects */
 140   if (((ObjAbortProb*100) >= transAbortProbForObj) && (x->riskyflag != 1)) {
 141     DEBUGSTATS("AFTER LOCK ABORTSTATS: oid= %x, type= %2d, transAbortProb= %2.2f, ObjAbortProb= %2.2f, Typenumaccess= %3d, avgtranssize = %2d, ObjabortCount= %2d, ObjaccessCount= %3d\n", OID(x), TYPE(x), transAbortProbForObj, ObjAbortProb, typesCausingAbort[TYPE(x)].numaccess, avgTransSize, x->abortCount, x->accessCount);
 142     //makes riskflag sticky
 143     pthread_mutex_lock(&lockedobjstore);
 144     if (objlockscope->offset<MAXOBJLIST) {
 145       x->objlock=&(objlockscope->lock[objlockscope->offset++]);
 146     } else {
 147       objlockstate_t *tmp=malloc(sizeof(objlockstate_t));
 148       tmp->next=objlockscope;
 149       tmp->offset=1;
 150       x->objlock=&(tmp->lock[0]);
 151       objlockscope=tmp;
 152     }
 153     pthread_mutex_unlock(&lockedobjstore);
 154     pthread_mutex_init(x->objlock, NULL);
 155     //should put a memory barrier here
 156     x->riskyflag = 1;
 157   }
 158 }
 159 #endif
 160
 161 /* ==================================================
 162  * stmStartup
 163  * This function starts up the transaction runtime.
 164  * ==================================================
 165  */
 166 int stmStartup() {
 167   return 0;
 168 }
 169
 170 /* ======================================
 171  * objstrCreate
 172  * - create an object store of given size
 173  * ======================================
 174  */
 175 objstr_t *objstrCreate(unsigned int size) {
 176   objstr_t *tmp;
 177   if((tmp = calloc(1, (sizeof(objstr_t) + size))) == NULL) {
 178     printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__);
 179     return NULL;
 180   }
 181   tmp->size = size;
 182   tmp->next = NULL;
 183   tmp->top = tmp + 1; //points to end of objstr_t structure!
 184   return tmp;
 185 }
 186
 187 void objstrReset() {
 188   while(t_cache->next!=NULL) {
 189     objstr_t *next=t_cache->next;
 190     t_cache->next=t_reserve;
 191     t_reserve=t_cache;
 192     t_cache=next;
 193   }
 194   t_cache->top=t_cache+1;
 195 #ifdef STMSTATS
 196   t_objnumcount=0;
 197 #endif
 198 }
 199
 200 //free entire list, starting at store
 201 void objstrDelete(objstr_t *store) {
 202   objstr_t *tmp;
 203   while (store != NULL) {
 204     tmp = store->next;
 205     free(store);
 206     store = tmp;
 207   }
 208   return;
 209 }
 210
 211 /* =================================================
 212  * transStart
 213  * This function initializes things required in the
 214  * transaction start
 215  * =================================================
 216  */
 217 void transStart() {
 218   //Transaction start is currently free...commit and aborting is not
 219 #ifdef DELAYCOMP
 220   c_ptrstack=&ptrstack;
 221   c_primstack=&primstack;
 222   c_branchstack=&branchstack;
 223 #endif
 224 }
 225
 226 /* =======================================================
 227  * transCreateObj
 228  * This function creates objects in the transaction record
 229  * =======================================================
 230  */
 231 objheader_t *transCreateObj(void * ptr, unsigned int size) {
 232   objheader_t *tmp = mygcmalloc(ptr, (sizeof(objheader_t) + size));
 233   objheader_t *retval=&tmp[1];
 234   tmp->lock=RW_LOCK_BIAS;
 235   tmp->version = 1;
 236   //initialize obj lock to the header
 237   STATUS(tmp)=NEW;
 238   // don't insert into table
 239   if (newobjs->offset<MAXOBJLIST) {
 240     newobjs->objs[newobjs->offset++]=retval;
 241   } else {
 242     struct objlist *tmp=malloc(sizeof(struct objlist));
 243     tmp->next=newobjs;
 244     tmp->objs[0]=retval;
 245     tmp->offset=1;
 246     newobjs=tmp;
 247   }
 248   return retval; //want space after object header
 249 }
 250
 251 /* This functions inserts randowm wait delays in the order of msec
 252  * Mostly used when transaction commits retry*/
 253 void randomdelay(int softaborted) {
 254   struct timespec req;
 255   struct timeval t;
 256
 257   gettimeofday(&t,NULL);
 258
 259   req.tv_sec = 0;
 260   req.tv_nsec = (long)((t.tv_usec)%(1<<softaborted))<<1; //1-11 microsec
 261   nanosleep(&req, NULL);
 262   return;
 263 }
 264
 265 /* ==============================================
 266  * objstrAlloc
 267  * - allocate space in an object store
 268  * ==============================================
 269  */
 270 void *objstrAlloc(unsigned int size) {
 271   void *tmp;
 272   int i=0;
 273   objstr_t *store=t_cache;
 274   if ((size&7)!=0) {
 275     size+=(8-(size&7));
 276   }
 277
 278   for(; i<2; i++) {
 279     if (OSFREE(store)>=size) {
 280       tmp=store->top;
 281       store->top +=size;
 282       return tmp;
 283     }
 284     if ((store=store->next)==NULL)
 285       break;
 286   }
 287
 288   {
 289     unsigned int newsize=size>DEFAULT_OBJ_STORE_SIZE ? size : DEFAULT_OBJ_STORE_SIZE;
 290     objstr_t **otmp=&t_reserve;
 291     objstr_t *ptr;
 292     while((ptr=*otmp)!=NULL) {
 293       if (ptr->size>=newsize) {
 294         //remove from list
 295         *otmp=ptr->next;
 296         ptr->next=t_cache;
 297         t_cache=ptr;
 298         ptr->top=((char *)(&ptr[1]))+size;
 299         return &ptr[1];
 300       }
 301     }
 302
 303     objstr_t *os=(objstr_t *)calloc(1,(sizeof(objstr_t) + newsize));
 304     void *nptr=&os[1];
 305     os->next=t_cache;
 306     t_cache=os;
 307     os->size=newsize;
 308     os->top=((char *)nptr)+size;
 309     return nptr;
 310   }
 311 }
 312
 313
 314 /* =============================================================
 315  * transRead
 316  * -finds the objects either in main heap
 317  * -copies the object into the transaction cache
 318  * =============================================================
 319  */
 320 //__attribute__ ((pure))
 321 void *transRead(void * oid, void *gl) {
 322   objheader_t *tmp, *objheader;
 323   objheader_t *objcopy;
 324   int size;
 325
 326   /* Read from the main heap */
 327   //No lock for now
 328   objheader_t *header = (objheader_t *)(((char *)oid) - sizeof(objheader_t));
 329   GETSIZE(size, header);
 330   size += sizeof(objheader_t);
 331   objcopy = (objheader_t *) objstrAlloc(size);
 332 #ifdef STMSTATS
 333   header->accessCount++;
 334   if(header->riskyflag) {
 335     header=needLock(header,gl);
 336   }
 337 #endif
 338   A_memcpy(objcopy, header, size);
 339 #ifdef STMSTATS
 340   /* keep track of the object's access sequence in a transaction */
 341   objheader_t *tmpheader = objcopy;
 342   tmpheader->accessCount = ++t_objnumcount;
 343 #endif
 344
 345   /* Insert into cache's lookup table */
 346   STATUS(objcopy)=0;
 347   if (((unsigned INTPTR)oid)<((unsigned INTPTR ) curr_heapbase)|| ((unsigned INTPTR)oid) >((unsigned INTPTR) curr_heapptr))
 348     printf("ERROR! Bad object address!\n");
 349   t_chashInsert(oid, &objcopy[1]);
 350   return &objcopy[1];
 351 }
 352
 353 void freenewobjs() {
 354   struct objlist *ptr=newobjs;
 355   while(ptr->next!=NULL) {
 356     struct objlist *tmp=ptr->next;
 357     free(ptr);
 358     ptr=tmp;
 359   }
 360   ptr->offset=0;
 361   newobjs=ptr;
 362 }
 363
 364 #ifdef STMSTATS
 365 void freelockedobjs() {
 366   struct objlist *ptr=lockedobjs;
 367   while(ptr->next!=NULL) {
 368     struct objlist *tmp=ptr->next;
 369     free(ptr);
 370     ptr=tmp;
 371   }
 372   ptr->offset=0;
 373   lockedobjs=ptr;
 374 }
 375 #endif
 376
 377 /* ================================================================
 378  * transCommit
 379  * - This function initiates the transaction commit process
 380  * - goes through the transaction cache and decides
 381  * - a final response
 382  * ================================================================
 383  */
 384 #ifdef DELAYCOMP
 385 int transCommit(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 386 #else
 387 int transCommit() {
 388 #endif
 389 #ifdef TRANSSTATS
 390   numTransCommit++;
 391 #endif
 392   int softaborted=0;
 393   do {
 394     /* Look through all the objects in the transaction hash table */
 395     int finalResponse;
 396 #ifdef DELAYCOMP
 397     if (c_numelements<(c_size>>3))
 398       finalResponse= alttraverseCache(commitmethod, primitives, locals, params);
 399     else
 400       finalResponse= traverseCache(commitmethod, primitives, locals, params);
 401 #else
 402     if (c_numelements<(c_size>>3))
 403       finalResponse= alttraverseCache();
 404     else
 405       finalResponse= traverseCache();
 406 #endif
 407     if(finalResponse == TRANS_ABORT) {
 408 #ifdef TRANSSTATS
 409       numTransAbort++;
 410       if (softaborted) {
 411         nSoftAbortAbort++;
 412       }
 413 #endif
 414       freenewobjs();
 415 #ifdef STMSTATS
 416       freelockedobjs();
 417 #endif
 418       objstrReset();
 419       t_chashreset();
 420 #ifdef READSET
 421       rd_t_chashreset();
 422 #endif
 423 #ifdef DELAYCOMP
 424       dc_t_chashreset();
 425       ptrstack.count=0;
 426       primstack.count=0;
 427       branchstack.count=0;
 428 #endif
 429       return TRANS_ABORT;
 430     }
 431     if(finalResponse == TRANS_COMMIT) {
 432 #ifdef TRANSSTATS
 433       //numTransCommit++;
 434       if (softaborted) {
 435         nSoftAbortCommit++;
 436       }
 437 #endif
 438       freenewobjs();
 439 #ifdef STMSTATS
 440       freelockedobjs();
 441 #endif
 442       objstrReset();
 443       t_chashreset();
 444 #ifdef READSET
 445       rd_t_chashreset();
 446 #endif
 447 #ifdef DELAYCOMP
 448       dc_t_chashreset();
 449       ptrstack.count=0;
 450       primstack.count=0;
 451       branchstack.count=0;
 452 #endif
 453       return 0;
 454     }
 455
 456     /* wait a random amount of time before retrying to commit transaction*/
 457     if(finalResponse == TRANS_SOFT_ABORT) {
 458 #ifdef TRANSSTATS
 459       nSoftAbort++;
 460 #endif
 461       softaborted++;
 462 #ifdef SOFTABORT
 463       if (softaborted>1) {
 464 #else
 465       if (1) {
 466 #endif
 467         //retry if too many soft aborts
 468         freenewobjs();
 469 #ifdef STMSTATS
 470     freelockedobjs();
 471 #endif
 472         objstrReset();
 473         t_chashreset();
 474 #ifdef READSET
 475         rd_t_chashreset();
 476 #endif
 477 #ifdef DELAYCOMP
 478         dc_t_chashreset();
 479         ptrstack.count=0;
 480         primstack.count=0;
 481         branchstack.count=0;
 482 #endif
 483         return TRANS_ABORT;
 484       }
 485       //randomdelay(softaborted);
 486     } else {
 487       printf("Error: in %s() Unknown outcome", __func__);
 488       exit(-1);
 489     }
 490   } while (1);
 491 }
 492
 493 #ifdef DELAYCOMP
 494 #define freearrays   if (c_numelements>=200) { \
 495     free(oidrdlocked); \
 496     free(oidrdversion); \
 497     free(oidrdage); \
 498   } \
 499   if (t_numelements>=200) { \
 500     free(oidwrlocked); \
 501   }
 502 #else
 503 #define freearrays   if (c_numelements>=200) { \
 504     free(oidrdlocked); \
 505     free(oidrdversion); \
 506     free(oidrdage); \
 507     free(oidwrlocked); \
 508   }
 509 #endif
 510
 511 #ifdef DELAYCOMP
 512 #define allocarrays int t_numelements=c_numelements+dc_c_numelements; \
 513   if (t_numelements<200) { \
 514     oidwrlocked=wrlocked; \
 515   } else { \
 516     oidwrlocked=malloc(t_numelements*sizeof(void *)); \
 517   } \
 518   if (c_numelements<200) { \
 519     oidrdlocked=rdlocked; \
 520     oidrdversion=rdversion; \
 521     oidrdage=rdage; \
 522   } else { \
 523     int size=c_numelements*sizeof(void*); \
 524     oidrdlocked=malloc(size); \
 525     oidrdversion=malloc(size); \
 526     oidrdage=malloc(size); \
 527   }
 528 #else
 529 #define allocarrays if (c_numelements<200) { \
 530     oidrdlocked=rdlocked; \
 531     oidrdversion=rdversion; \
 532     oidrdage=rdage; \
 533     oidwrlocked=wrlocked; \
 534   } else { \
 535     int size=c_numelements*sizeof(void*); \
 536     oidrdlocked=malloc(size); \
 537     oidrdversion=malloc(size); \
 538     oidwrlocked=malloc(size); \
 539     oidrdage=malloc(size); \
 540   }
 541 #endif
 542
 543
 544
 545
 546 /* ==================================================
 547  * traverseCache
 548  * - goes through the transaction cache and
 549  * - decides if a transaction should commit or abort
 550  * ==================================================
 551  */
 552 #ifdef DELAYCOMP
 553 int traverseCache(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 554 #else
 555 int traverseCache() {
 556 #endif
 557   /* Create info to keep track of objects that can be locked */
 558   int numoidrdlocked=0;
 559   int numoidwrlocked=0;
 560   void * rdlocked[200];
 561   int rdversion[200];
 562   int rdage[200];
 563   void * wrlocked[200];
 564   int softabort=0;
 565   int i;
 566   void ** oidrdlocked;
 567   void ** oidwrlocked;
 568   int * oidrdage;
 569   int * oidrdversion;
 570   allocarrays;
 571   int objtypetraverse[TOTALNUMCLASSANDARRAY];
 572   int ObjSeqId;
 573
 574   for(i=0; i<TOTALNUMCLASSANDARRAY; i++)
 575     objtypetraverse[i] = 0;
 576
 577   chashlistnode_t *ptr = c_table;
 578   /* Represents number of bins in the chash table */
 579   unsigned int size = c_size;
 580   for(i = 0; i<size; i++) {
 581     chashlistnode_t *curr = &ptr[i];
 582     /* Inner loop to traverse the linked list of the cache lookupTable */
 583     while(curr != NULL) {
 584       //if the first bin in hash table is empty
 585       if(curr->key == NULL)
 586         break;
 587       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1]; //cached object
 588       objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t)); //real object
 589       unsigned int version = headeraddr->version;
 590
 591       if(STATUS(headeraddr) & DIRTY) {
 592         /* Read from the main heap  and compare versions */
 593         if(write_trylock(&header->lock)) { //can aquire write lock
 594           if (version == header->version) { /* versions match */
 595             /* Keep track of objects locked */
 596             oidwrlocked[numoidwrlocked++] = header;
 597           } else {
 598             oidwrlocked[numoidwrlocked++] = header;
 599             transAbortProcess(oidwrlocked, numoidwrlocked);
 600 #ifdef STMSTATS
 601         header->abortCount++;
 602         ObjSeqId = headeraddr->accessCount;
 603             (typesCausingAbort[TYPE(header)]).numabort++;
 604             (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 605         (typesCausingAbort[TYPE(header)]).numtrans+=1;
 606         objtypetraverse[TYPE(header)]=1;
 607         getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
 608 #endif
 609             DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 610             DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 611             freearrays;
 612             if (softabort)
 613             return TRANS_SOFT_ABORT;
 614               else
 615             return TRANS_ABORT;
 616           }
 617         } else {
 618           if(version == header->version) {
 619             /* versions match */
 620             softabort=1;
 621           }
 622           transAbortProcess(oidwrlocked, numoidwrlocked);
 623 #ifdef STMSTATS
 624       header->abortCount++;
 625       ObjSeqId = headeraddr->accessCount;
 626       (typesCausingAbort[TYPE(header)]).numabort++;
 627       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 628       (typesCausingAbort[TYPE(header)]).numtrans+=1;
 629       objtypetraverse[TYPE(header)]=1;
 630           //(typesCausingAbort[TYPE(header)])++;
 631 #endif
 632 #if defined(STMSTATS)||defined(SOFTABORT)
 633       if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
 634             softabort=0;
 635 #endif
 636           DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 637           DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 638           freearrays;
 639           if (softabort)
 640             return TRANS_SOFT_ABORT;
 641           else
 642             return TRANS_ABORT;
 643
 644         }
 645       } else {
 646 #ifdef STMSTATS
 647         oidrdversion[numoidrdlocked]=version;
 648         oidrdlocked[numoidrdlocked]=header;
 649     oidrdage[numoidrdlocked++]=headeraddr->accessCount;
 650 #else
 651     oidrdversion[numoidrdlocked]=version;
 652     oidrdlocked[numoidrdlocked++]=header;
 653 #endif
 654       }
 655       curr = curr->next;
 656     }
 657   } //end of for
 658
 659 #ifdef DELAYCOMP
 660   //acquire access set locks
 661   unsigned int numoidwrtotal=numoidwrlocked;
 662
 663   chashlistnode_t *dc_curr = dc_c_list;
 664   /* Inner loop to traverse the linked list of the cache lookupTable */
 665   while(likely(dc_curr != NULL)) {
 666     //if the first bin in hash table is empty
 667     objheader_t * headeraddr=&((objheader_t *) dc_curr->val)[-1];
 668     objheader_t *header=(objheader_t *)(((char *)dc_curr->key)-sizeof(objheader_t));
 669     if(write_trylock(&header->lock)) { //can aquire write lock
 670       oidwrlocked[numoidwrtotal++] = header;
 671     } else {
 672       //maybe we already have lock
 673       void * key=dc_curr->key;
 674       chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 675
 676       do {
 677         if(node->key == key) {
 678           objheader_t * headeraddr=&((objheader_t *) node->val)[-1];
 679           if(STATUS(headeraddr) & DIRTY) {
 680             goto nextloop;
 681           } else
 682             break;
 683         }
 684         node = node->next;
 685       } while(node != NULL);
 686
 687       //have to abort to avoid deadlock
 688       transAbortProcess(oidwrlocked, numoidwrtotal);
 689 #ifdef STMSTATS
 690       ObjSeqId = headeraddr->accessCount;
 691       header->abortCount++;
 692       (typesCausingAbort[TYPE(header)]).numabort++;
 693       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 694       (typesCausingAbort[TYPE(header)]).numtrans+=1;
 695       objtypetraverse[TYPE(header)]=1;
 696 #endif
 697 #if defined(STMSTATS)||defined(SOFTABORT)
 698       if(getTotalAbortCount(i+1, size, (void *)(curr->next), numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
 699         softabort=0;
 700 #endif
 701       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 702       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 703       freearrays;
 704       if (softabort)
 705         return TRANS_SOFT_ABORT;
 706       else
 707         return TRANS_ABORT;
 708     }
 709   nextloop:
 710     dc_curr = dc_curr->lnext;
 711   }
 712 #endif
 713
 714   //THIS IS THE SERIALIZATION END POINT (START POINT IS END OF EXECUTION)*****
 715
 716   for(i=0; i<numoidrdlocked; i++) {
 717     /* Read from the main heap  and compare versions */
 718     objheader_t *header=oidrdlocked[i];
 719     unsigned int version=oidrdversion[i];
 720     if(header->lock>0) { //not write locked
 721       CFENCE;
 722       if(version != header->version) { /* versions do not match */
 723 #ifdef DELAYCOMP
 724         transAbortProcess(oidwrlocked, numoidwrtotal);
 725 #else
 726         transAbortProcess(oidwrlocked, numoidwrlocked);
 727 #endif
 728 #ifdef STMSTATS
 729     ObjSeqId = oidrdage[i];
 730     header->abortCount++;
 731     (typesCausingAbort[TYPE(header)]).numabort++;
 732     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 733     (typesCausingAbort[TYPE(header)]).numtrans+=1;
 734     objtypetraverse[TYPE(header)]=1;
 735         getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
 736 #endif
 737         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 738         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 739         freearrays;
 740         return TRANS_ABORT;
 741       }
 742 #if DELAYCOMP
 743     } else if (dc_t_chashSearch(((char *)header)+sizeof(objheader_t))!=NULL) {
 744       //couldn't get lock because we already have it
 745       //check if it is the right version number
 746       if (version!=header->version) {
 747         transAbortProcess(oidwrlocked, numoidwrtotal);
 748 #ifdef STMSTATS
 749     ObjSeqId = oidrdage[i];
 750     header->abortCount++;
 751     (typesCausingAbort[TYPE(header)]).numabort++;
 752     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 753     (typesCausingAbort[TYPE(header)]).numtrans+=1;
 754     objtypetraverse[TYPE(header)]=1;
 755         getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
 756 #endif
 757         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u, oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 758         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 759         freearrays;
 760         return TRANS_ABORT;
 761       }
 762 #endif
 763     } else { /* cannot aquire lock */
 764       //do increment as we didn't get lock
 765       if(version == header->version) {
 766         softabort=1;
 767       }
 768 #ifdef DELAYCOMP
 769       transAbortProcess(oidwrlocked, numoidwrtotal);
 770 #else
 771       transAbortProcess(oidwrlocked, numoidwrlocked);
 772 #endif
 773 #ifdef STMSTATS
 774       ObjSeqId = oidrdage[i];
 775       header->abortCount++;
 776       (typesCausingAbort[TYPE(header)]).numabort++;
 777       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 778       (typesCausingAbort[TYPE(header)]).numtrans+=1;
 779       objtypetraverse[TYPE(header)]=1;
 780 #endif
 781 #if defined(STMSTATS)||defined(SOFTABORT)
 782       if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
 783         softabort=0;
 784 #endif
 785       DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 786       DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 787       freearrays;
 788       if (softabort)
 789         return TRANS_SOFT_ABORT;
 790       else
 791         return TRANS_ABORT;
 792     }
 793   }
 794
 795 #ifdef READSET
 796   //need to validate auxilary readset
 797   rdchashlistnode_t *rd_curr = rd_c_list;
 798   /* Inner loop to traverse the linked list of the cache lookupTable */
 799   while(likely(rd_curr != NULL)) {
 800     //if the first bin in hash table is empty
 801     unsigned int version=rd_curr->version;
 802     objheader_t *header=(objheader_t *)(((char *)rd_curr->key)-sizeof(objheader_t));
 803     if(header->lock>0) { //object is not locked
 804       if (version!=header->version) {
 805         //have to abort
 806 #ifdef DELAYCOMP
 807         transAbortProcess(oidwrlocked, numoidwrtotal);
 808 #else
 809         transAbortProcess(oidwrlocked, numoidwrlocked);
 810 #endif
 811 #ifdef STMSTATS
 812         //ABORTCOUNT(header);
 813         (typesCausingAbort[TYPE(header)])++;
 814 #endif
 815 #if defined(STMSTATS)||defined(SOFTABORT)
 816         //if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion))
 817         //  softabort=0;
 818 #endif
 819         DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 820         DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 821         freearrays;
 822         if (softabort)
 823           return TRANS_SOFT_ABORT;
 824         else
 825           return TRANS_ABORT;
 826       }
 827     } else {
 828       //maybe we already have lock
 829       if (version==header->version) {
 830         void * key=rd_curr->key;
 831 #ifdef DELAYCOMP
 832         //check to see if it is in the delaycomp table
 833         {
 834           chashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>4];
 835           do {
 836             if(node->key == key)
 837               goto nextloopread;
 838             node = node->next;
 839           } while(node != NULL);
 840         }
 841 #endif
 842         //check normal table
 843         {
 844           chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 845           do {
 846             if(node->key == key) {
 847               objheader_t * headeraddr=&((objheader_t *) node->val)[-1];
 848               if(STATUS(headeraddr) & DIRTY) {
 849                 goto nextloopread;
 850               }
 851             }
 852             node = node->next;
 853           } while(node != NULL);
 854         }
 855       }
 856 #ifdef DELAYCOMP
 857       //have to abort to avoid deadlock
 858       transAbortProcess(oidwrlocked, numoidwrtotal);
 859 #else
 860       transAbortProcess(oidwrlocked, numoidwrlocked);
 861 #endif
 862
 863 #ifdef STMSTATS
 864       //ABORTCOUNT(header);
 865       (typesCausingAbort[TYPE(header)])++;
 866 #endif
 867 #if defined(STMSTATS)||defined(SOFTABORT)
 868       //if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion))
 869         //softabort=0;
 870 #endif
 871       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 872       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 873       freearrays;
 874       if (softabort)
 875         return TRANS_SOFT_ABORT;
 876       else
 877         return TRANS_ABORT;
 878     }
 879   nextloopread:
 880     rd_curr = rd_curr->lnext;
 881   }
 882 #endif
 883
 884   /* Decide the final response */
 885 #ifdef DELAYCOMP
 886   transCommitProcess(oidwrlocked, numoidwrlocked, numoidwrtotal, commitmethod, primitives, locals, params);
 887 #else
 888   transCommitProcess(oidwrlocked, numoidwrlocked);
 889 #endif
 890   DEBUGSTM("Commit: rd: %u wr: %u tot: %u\n", numoidrdlocked, numoidwrlocked, c_numelements);
 891   freearrays;
 892   return TRANS_COMMIT;
 893 }
 894
 895 /* ==================================================
 896  * alttraverseCache
 897  * - goes through the transaction cache and
 898  * - decides if a transaction should commit or abort
 899  * ==================================================
 900  */
 901
 902 #ifdef DELAYCOMP
 903 int alttraverseCache(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 904 #else
 905 int alttraverseCache() {
 906 #endif
 907   /* Create info to keep track of objects that can be locked */
 908   int numoidrdlocked=0;
 909   int numoidwrlocked=0;
 910   void * rdlocked[200];
 911   int rdversion[200];
 912   int rdage[200];
 913   void * wrlocked[200];
 914   int softabort=0;
 915   int i;
 916   void ** oidrdlocked;
 917   int * oidrdversion;
 918   int * oidrdage;
 919   void ** oidwrlocked;
 920   allocarrays;
 921   int ObjSeqId;
 922   int objtypetraverse[TOTALNUMCLASSANDARRAY];
 923
 924   for(i=0; i<TOTALNUMCLASSANDARRAY; i++)
 925     objtypetraverse[i] = 0;
 926   chashlistnode_t *curr = c_list;
 927   /* Inner loop to traverse the linked list of the cache lookupTable */
 928   while(likely(curr != NULL)) {
 929     //if the first bin in hash table is empty
 930     objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 931     objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
 932     unsigned int version = headeraddr->version;
 933
 934     if(STATUS(headeraddr) & DIRTY) {
 935       /* Read from the main heap  and compare versions */
 936       if(likely(write_trylock(&header->lock))) { //can aquire write lock
 937         if (likely(version == header->version)) { /* versions match */
 938           /* Keep track of objects locked */
 939           oidwrlocked[numoidwrlocked++] = header;
 940         } else {
 941           oidwrlocked[numoidwrlocked++] = header;
 942           transAbortProcess(oidwrlocked, numoidwrlocked);
 943 #ifdef STMSTATS
 944       header->abortCount++;
 945       ObjSeqId = headeraddr->accessCount;
 946       (typesCausingAbort[TYPE(header)]).numabort++;
 947       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 948       (typesCausingAbort[TYPE(header)]).numtrans+=1;
 949       objtypetraverse[TYPE(header)]=1;
 950       getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
 951 #endif
 952           DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 953           DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 954           freearrays;
 955           return TRANS_ABORT;
 956         }
 957       } else { /* cannot aquire lock */
 958         if(version == header->version) {
 959           /* versions match */
 960           softabort=1;
 961         }
 962         transAbortProcess(oidwrlocked, numoidwrlocked);
 963 #ifdef STMSTATS
 964     header->abortCount++;
 965     ObjSeqId = headeraddr->accessCount;
 966     (typesCausingAbort[TYPE(header)]).numabort++;
 967     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
 968     (typesCausingAbort[TYPE(header)]).numtrans+=1;
 969     objtypetraverse[TYPE(header)]=1;
 970 #endif
 971 #if defined(STMSTATS)||defined(SOFTABORT)
 972     if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
 973           softabort=0;
 974 #endif
 975         DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
 976         DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 977         freearrays;
 978         if (softabort)
 979           return TRANS_SOFT_ABORT;
 980         else
 981           return TRANS_ABORT;
 982       }
 983     } else {
 984       /* Read from the main heap  and compare versions */
 985       oidrdversion[numoidrdlocked]=version;
 986       oidrdlocked[numoidrdlocked++] = header;
 987     }
 988     curr = curr->lnext;
 989   }
 990
 991 #ifdef DELAYCOMP
 992   //acquire other locks
 993   unsigned int numoidwrtotal=numoidwrlocked;
 994   chashlistnode_t *dc_curr = dc_c_list;
 995   /* Inner loop to traverse the linked list of the cache lookupTable */
 996   while(likely(dc_curr != NULL)) {
 997     //if the first bin in hash table is empty
 998     objheader_t * headeraddr=&((objheader_t *) dc_curr->val)[-1];
 999     objheader_t *header=(objheader_t *)(((char *)dc_curr->key)-sizeof(objheader_t));
1000     if(write_trylock(&header->lock)) { //can aquire write lock
1001       oidwrlocked[numoidwrtotal++] = header;
1002     } else {
1003       //maybe we already have lock
1004       void * key=dc_curr->key;
1005       chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
1006
1007       do {
1008         if(node->key == key) {
1009           objheader_t * headeraddr=&((objheader_t *) node->val)[-1];
1010           if(STATUS(headeraddr) & DIRTY) {
1011             goto nextloop;
1012           }
1013         }
1014         node = node->next;
1015       } while(node != NULL);
1016
1017       //have to abort to avoid deadlock
1018       transAbortProcess(oidwrlocked, numoidwrtotal);
1019 #ifdef STMSTATS
1020       header->abortCount++;
1021       ObjSeqId = headeraddr->accessCount;
1022       (typesCausingAbort[TYPE(header)]).numabort++;
1023       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
1024       (typesCausingAbort[TYPE(header)]).numtrans+=1;
1025       objtypetraverse[TYPE(header)]=1;
1026 #endif
1027 #if defined(STMSTATS)||defined(SOFTABORT)
1028       if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
1029         softabort=0;
1030 #endif
1031       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
1032       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1033       freearrays;
1034       if (softabort)
1035         return TRANS_SOFT_ABORT;
1036       else
1037         return TRANS_ABORT;
1038     }
1039   nextloop:
1040     dc_curr = dc_curr->lnext;
1041   }
1042 #endif
1043
1044   //THIS IS THE SERIALIZATION END POINT (START POINT IS END OF EXECUTION)*****
1045
1046   for(i=0; i<numoidrdlocked; i++) {
1047     objheader_t * header=oidrdlocked[i];
1048     unsigned int version=oidrdversion[i];
1049     if(header->lock>0) {
1050       CFENCE;
1051       if(version != header->version) {
1052 #ifdef DELAYCOMP
1053         transAbortProcess(oidwrlocked, numoidwrtotal);
1054 #else
1055         transAbortProcess(oidwrlocked, numoidwrlocked);
1056 #endif
1057 #ifdef STMSTATS
1058     ObjSeqId = oidrdage[i];
1059     header->abortCount++;
1060     (typesCausingAbort[TYPE(header)]).numabort++;
1061     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
1062     (typesCausingAbort[TYPE(header)]).numtrans+=1;
1063     objtypetraverse[TYPE(header)]=1;
1064         getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
1065 #endif
1066         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
1067         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1068         freearrays;
1069         return TRANS_ABORT;
1070       }
1071 #ifdef DELAYCOMP
1072     } else if (dc_t_chashSearch(((char *)header)+sizeof(objheader_t))!=NULL) {
1073       //couldn't get lock because we already have it
1074       //check if it is the right version number
1075       if (version!=header->version) {
1076         transAbortProcess(oidwrlocked, numoidwrtotal);
1077 #ifdef STMSTATS
1078     ObjSeqId = oidrdage[i];
1079     header->abortCount++;
1080         getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse);
1081 #endif
1082         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u oid: %x\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version, OID(header));
1083         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1084         freearrays;
1085         return TRANS_ABORT;
1086       }
1087 #endif
1088     } else { /* cannot aquire lock */
1089       if(version == header->version) {
1090         softabort=1;
1091       }
1092 #ifdef DELAYCOMP
1093       transAbortProcess(oidwrlocked, numoidwrtotal);
1094 #else
1095       transAbortProcess(oidwrlocked, numoidwrlocked);
1096 #endif
1097 #ifdef STMSTATS
1098       ObjSeqId = oidrdage[i];
1099       header->abortCount++;
1100       (typesCausingAbort[TYPE(header)]).numabort++;
1101       (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
1102       (typesCausingAbort[TYPE(header)]).numtrans+=1;
1103       objtypetraverse[TYPE(header)]=1;
1104 #endif
1105 #if defined(STMSTATS)||defined(SOFTABORT)
1106       if(getReadAbortCount(i+1, numoidrdlocked, oidrdlocked, oidrdversion, oidrdage, ObjSeqId, header, objtypetraverse))
1107         softabort=0;
1108 #endif
1109       DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
1110       DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1111       freearrays;
1112       if (softabort)
1113         return TRANS_SOFT_ABORT;
1114       else
1115         return TRANS_ABORT;
1116     }
1117   }
1118
1119 #ifdef READSET
1120   //need to validate auxilary readset
1121   rdchashlistnode_t *rd_curr = rd_c_list;
1122   /* Inner loop to traverse the linked list of the cache lookupTable */
1123   while(likely(rd_curr != NULL)) {
1124     //if the first bin in hash table is empty
1125     int version=rd_curr->version;
1126     objheader_t *header=(objheader_t *)(((char *)rd_curr->key)-sizeof(objheader_t));
1127     if(header->lock>0) { //object is not locked
1128       if (version!=header->version) {
1129         //have to abort
1130 #ifdef DELAYCOMP
1131         transAbortProcess(oidwrlocked, numoidwrtotal);
1132 #else
1133         transAbortProcess(oidwrlocked, numoidwrlocked);
1134 #endif
1135 #ifdef STMSTATS
1136         //ABORTCOUNT(header);
1137         (typesCausingAbort[TYPE(header)])++;
1138 #endif
1139 #if defined(STMSTATS)||defined(SOFTABORT)
1140         //if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion))
1141         //  softabort=0;
1142 #endif
1143         DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
1144         DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1145         freearrays;
1146         if (softabort)
1147           return TRANS_SOFT_ABORT;
1148         else
1149           return TRANS_ABORT;
1150       }
1151     } else {
1152       if (version==header->version) {
1153         void * key=rd_curr->key;
1154 #ifdef DELAYCOMP
1155         //check to see if it is in the delaycomp table
1156         {
1157           chashlistnode_t *node = &dc_c_table[(((unsigned INTPTR)key) & dc_c_mask)>>4];
1158           do {
1159             if(node->key == key)
1160               goto nextloopread;
1161             node = node->next;
1162           } while(node != NULL);
1163         }
1164 #endif
1165         //check normal table
1166         {
1167           chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
1168           do {
1169             if(node->key == key) {
1170               objheader_t * headeraddr=&((objheader_t *) node->val)[-1];
1171               if(STATUS(headeraddr) & DIRTY) {
1172                 goto nextloopread;
1173               }
1174             }
1175             node = node->next;
1176           } while(node != NULL);
1177         }
1178       }
1179 #ifdef DELAYCOMP
1180         //have to abort to avoid deadlock
1181         transAbortProcess(oidwrlocked, numoidwrtotal);
1182 #else
1183         transAbortProcess(oidwrlocked, numoidwrlocked);
1184 #endif
1185 #ifdef STMSTATS
1186       //ABORTCOUNT(header);
1187       (typesCausingAbort[TYPE(header)])++;
1188 #endif
1189 #if defined(STMSTATS)||defined(SOFTABORT)
1190      // if(getTotalAbortCount2((void *) curr->next, numoidrdlocked, oidrdlocked, oidrdversion))
1191         //softabort=0;
1192 #endif
1193       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
1194       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
1195       freearrays;
1196       if (softabort)
1197         return TRANS_SOFT_ABORT;
1198       else
1199         return TRANS_ABORT;
1200     }
1201   nextloopread:
1202     rd_curr = rd_curr->lnext;
1203   }
1204 #endif
1205
1206   /* Decide the final response */
1207 #ifdef DELAYCOMP
1208   transCommitProcess(oidwrlocked, numoidwrlocked, numoidwrtotal, commitmethod, primitives, locals, params);
1209 #else
1210   transCommitProcess(oidwrlocked, numoidwrlocked);
1211 #endif
1212   DEBUGSTM("Commit: rd: %u wr: %u tot: %u\n", numoidrdlocked, numoidwrlocked, c_numelements);
1213   freearrays;
1214   return TRANS_COMMIT;
1215 }
1216
1217 /* ==================================
1218  * transAbortProcess
1219  *
1220  * =================================
1221  */
1222 void transAbortProcess(void **oidwrlocked, int numoidwrlocked) {
1223   int i;
1224   objheader_t *header;
1225   /* Release read locks */
1226
1227   /* Release write locks */
1228   for(i=numoidwrlocked-1; i>=0; i--) {
1229     /* Read from the main heap */
1230     header = (objheader_t *)oidwrlocked[i];
1231     write_unlock(&header->lock);
1232   }
1233
1234 #ifdef STMSTATS
1235   /* clear trec and then release objects locked */
1236   struct objlist *ptr=lockedobjs;
1237   while(ptr!=NULL) {
1238     int max=ptr->offset;
1239     for(i=max-1; i>=0; i--) {
1240       header = (objheader_t *)ptr->objs[i];
1241       header->trec = NULL;
1242       pthread_mutex_unlock(header->objlock);
1243     }
1244     ptr=ptr->next;
1245   }
1246 #endif
1247 }
1248
1249 /* ==================================
1250  * transCommitProcess
1251  *
1252  * =================================
1253  */
1254 #ifdef DELAYCOMP
1255  void transCommitProcess(void ** oidwrlocked, int numoidwrlocked, int numoidwrtotal, void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
1256 #else
1257    void transCommitProcess(void ** oidwrlocked, int numoidwrlocked) {
1258 #endif
1259   objheader_t *header;
1260   void *ptrcreate;
1261   int i;
1262   struct objlist *ptr=newobjs;
1263   while(ptr!=NULL) {
1264     int max=ptr->offset;
1265     for(i=0; i<max; i++) {
1266       //clear the new flag
1267       ((struct ___Object___ *)ptr->objs[i])->___objstatus___=0;
1268     }
1269     ptr=ptr->next;
1270   }
1271
1272   /* Copy from transaction cache -> main object store */
1273   for (i = numoidwrlocked-1; i >=0; i--) {
1274     /* Read from the main heap */
1275     header = (objheader_t *)oidwrlocked[i];
1276     int tmpsize;
1277     GETSIZE(tmpsize, header);
1278     struct ___Object___ *dst=(struct ___Object___*)(((char *)oidwrlocked[i])+sizeof(objheader_t));
1279     struct ___Object___ *src=t_chashSearch(dst);
1280     dst->___cachedCode___=src->___cachedCode___;
1281     dst->___cachedHash___=src->___cachedHash___;
1282     A_memcpy(&dst[1], &src[1], tmpsize-sizeof(struct ___Object___));
1283   }
1284   CFENCE;
1285
1286 #ifdef DELAYCOMP
1287   //  call commit method
1288   ptrstack.count=0;
1289   primstack.count=0;
1290   branchstack.count=0;
1291   commitmethod(params, locals, primitives);
1292 #endif
1293
1294   /* Release write locks */
1295 #ifdef DELAYCOMP
1296   for(i=numoidwrtotal-1; i>=0; i--) {
1297 #else
1298   for(i=numoidwrlocked-1; i>=0; i--) {
1299 #endif
1300     header = (objheader_t *)oidwrlocked[i];
1301     header->version++;
1302     write_unlock(&header->lock);
1303   }
1304
1305 #ifdef STMSTATS
1306   /* clear trec and then release objects locked */
1307   ptr=lockedobjs;
1308   while(ptr!=NULL) {
1309     int max=ptr->offset;
1310     for(i=max-1; i>=0; i--) {
1311       header = (objheader_t *)ptr->objs[i];
1312       header->trec = NULL;
1313       pthread_mutex_unlock(header->objlock);
1314     }
1315     ptr=ptr->next;
1316   }
1317 #endif
1318 }
1319
1320 #if defined(STMSTATS)||defined(SOFTABORT)
1321 /** ========================================================================================
1322  * getTotalAbortCount (for traverseCache only)
1323  * params : start: start index of the loop
1324  *        : stop: stop index of the loop
1325  *        : startptr: pointer that points to where to start looking in the cache hash table
1326  *        : numoidrdlocked : number of objects read that are locked
1327  *        : oidrdlocked : array of objects read and currently locked
1328  *        : oidrdversion : array of versions of object read
1329  *        : oidrdage : array of ages of objects read ina transaction cache
1330  *        : ObjSeqId : sequence Id/age to start the comparision with
1331  * =========================================================================================
1332  **/
1333 int getTotalAbortCount(int start, int stop, void *startptr, int numoidrdlocked,
1334     void *oidrdlocked, int *oidrdversion, int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) {
1335   int i;
1336   int hardabort=0;
1337   int isFirstTime=0;
1338   objheader_t *ObjToBeLocked=header;
1339   chashlistnode_t *curr = (chashlistnode_t *) startptr;
1340   chashlistnode_t *ptr = c_table;
1341   /* First go through all objects left in the cache that have not been covered yet */
1342   for(i = start; i < stop; i++) {
1343     if(!isFirstTime)
1344       curr = &ptr[i];
1345     /* Inner loop to traverse the linked list of the cache lookupTable */
1346     while(curr != NULL) {
1347       if(curr->key == NULL)
1348         break;
1349       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
1350       objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
1351       unsigned int version = headeraddr->version;
1352       /* versions do not match */
1353       if(version != header->version) {
1354 #ifdef STMSTATS
1355         header->abortCount++;
1356         if(ObjSeqId > headeraddr->accessCount) {
1357           ObjSeqId = headeraddr->accessCount;
1358           ObjToBeLocked = header;
1359         }
1360         getTransSize(header, isObjTypeTraverse);
1361 #endif
1362         hardabort=1;
1363       }
1364       curr = curr->next;
1365     }
1366     isFirstTime = 1;
1367   }
1368
1369   /* Then go through all objects that are read and are currently present in the readLockedArray */
1370   if(numoidrdlocked>0) {
1371     for(i=0; i<numoidrdlocked; i++) {
1372       objheader_t *header = ((void **) oidrdlocked)[i];
1373       int OidAge = oidrdage[i];
1374       unsigned int version = oidrdversion[i];
1375       if(version != header->version) { /* versions do not match */
1376 #ifdef STMSTATS
1377         header->abortCount++;
1378         if(ObjSeqId > OidAge) {
1379           ObjSeqId = OidAge;
1380           ObjToBeLocked = header;
1381         }
1382         getTransSize(header, isObjTypeTraverse);
1383 #endif
1384         hardabort=1;
1385       }
1386     }
1387   }
1388
1389   /* Acquire lock on the oldest object accessed in the transaction cache */
1390   if(ObjToBeLocked != NULL) {
1391     ABORTCOUNT(ObjToBeLocked);
1392   }
1393
1394   return hardabort;
1395 }
1396
1397 /** ========================================================================================
1398  * getTotalAbortCount2 (for alttraverseCache only)
1399  * params : startptr: pointer that points to where to start looking in the cache hash table
1400  *        : numoidrdlocked : number of objects read that are locked
1401  *        : oidrdlocked : array of objects read and currently locked
1402  *        : oidrdversion : array of versions of object read
1403  *        : oidrdage : array of ages of objects read ina transaction cache
1404  *        : ObjSeqId : sequence Id/age to start the comparision with
1405  * =========================================================================================
1406  **/
1407 int getTotalAbortCount2(void *startptr, int numoidrdlocked, void *oidrdlocked,
1408     int *oidrdversion, int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) {
1409   int hardabort=0;
1410   chashlistnode_t *curr = (chashlistnode_t *) startptr;
1411   objheader_t *ObjToBeLocked=header;
1412
1413   /* Inner loop to traverse the linked list of the cache lookupTable */
1414   while(curr != NULL) {
1415     objheader_t *headeraddr=&((objheader_t *) curr->val)[-1];
1416     objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
1417     unsigned int version = headeraddr->version;
1418     /* versions do not match */
1419     if(version != header->version) {
1420 #ifdef STMSTATS
1421       header->abortCount++;
1422       if(ObjSeqId > headeraddr->accessCount) {
1423         ObjSeqId = headeraddr->accessCount;
1424         ObjToBeLocked = header;
1425       }
1426       getTransSize(header, isObjTypeTraverse);
1427 #endif
1428       hardabort=1;
1429     }
1430     curr = curr->next;
1431   }
1432
1433   /* Then go through all objects that are read and are currently present in the readLockedArray */
1434   if(numoidrdlocked>0) {
1435     int i;
1436     for(i=0; i<numoidrdlocked; i++) {
1437       objheader_t *header = ((void **)oidrdlocked)[i];
1438       unsigned int version = oidrdversion[i];
1439       int OidAge = oidrdage[i];
1440       if(version != header->version) { /* versions do not match */
1441 #ifdef STMSTATS
1442         header->abortCount++;
1443         if(ObjSeqId > OidAge) {
1444           ObjSeqId = OidAge;
1445           ObjToBeLocked = header;
1446         }
1447         getTransSize(header, isObjTypeTraverse);
1448 #endif
1449         hardabort=1;
1450       }
1451     }
1452   }
1453
1454   if(ObjToBeLocked!=NULL) {
1455     ABORTCOUNT(ObjToBeLocked);
1456   }
1457
1458   return hardabort;
1459 }
1460
1461 /**
1462  * getReadAbortCount : Tells the number of aborts caused by objects that are read by
1463  *                    visiting the read array
1464  * params: int start, int stop are indexes to readLocked array
1465  *         void  *oidrdlocked = readLocked array
1466  *         int *oidrdversion = version array
1467  *        : oidrdage : array of ages of objects read ina transaction cache
1468  *        : ObjSeqId : sequence Id/age to start the comparision with
1469  **/
1470 int getReadAbortCount(int start, int stop, void *oidrdlocked, int *oidrdversion,
1471     int *oidrdage, int ObjSeqId, objheader_t *header, int *isObjTypeTraverse) {
1472   int i;
1473   int hardabort=0;
1474   objheader_t *ObjToBeLocked=header;
1475
1476   /* Go through oids read that are locked */
1477   for(i = start; i < stop; i++) {
1478     objheader_t *header = ((void **)oidrdlocked)[i];
1479     unsigned int version = oidrdversion[i];
1480     int OidAge = oidrdage[i];
1481     if(version != header->version) { /* versions do not match */
1482 #ifdef STMSTATS
1483       header->abortCount++;
1484       if(ObjSeqId > OidAge) {
1485         ObjSeqId = OidAge;
1486         ObjToBeLocked = header;
1487       }
1488       getTransSize(header, isObjTypeTraverse);
1489 #endif
1490       hardabort=1;
1491     }
1492   }
1493
1494   if(ObjToBeLocked != NULL) {
1495     ABORTCOUNT(ObjToBeLocked);
1496   }
1497
1498   return hardabort;
1499 }
1500
1501
1502 /**
1503  * needLock
1504  * params: Object header, ptr to garbage collector
1505  * Locks an object that causes aborts
1506  **/
1507 objheader_t * needLock(objheader_t *header, void *gl) {
1508   int lockstatus;
1509   threadrec_t *ptr;
1510   while((lockstatus = pthread_mutex_trylock(header->objlock))
1511       && ((ptr = header->trec) == NULL)) { //retry
1512     ;
1513   }
1514   if(lockstatus==0) { //acquired lock
1515     /* Set trec */
1516     header->trec = trec;
1517   } else { //failed to get lock
1518     trec->blocked=1;
1519     //memory barrier
1520     CFENCE;
1521     //see if other thread is blocked
1522     if(ptr->blocked == 1) {
1523       //it might be block, so ignore lock and clear our blocked flag
1524       trec->blocked=0;
1525       return;
1526     } else {
1527 #ifdef PRECISE_GC
1528       INTPTR ptrarray[]={1, (INTPTR)gl, (INTPTR) header};
1529       void *lockptr=header->objlock;
1530       stopforgc((struct garbagelist *)ptrarray);
1531       //grab lock and wait our turn
1532       pthread_mutex_lock(lockptr);
1533       restartaftergc();
1534       header=(objheader_t *) ptrarray[2];
1535 #else
1536       pthread_mutex_lock(header->objptr);
1537 #endif
1538       /* we have lock, so we are not blocked anymore */
1539       trec->blocked = 0;
1540       /* Set our trec */
1541       header->trec = trec;
1542     }
1543   }
1544   //trec->blocked is zero now
1545
1546   /* Save the locked object */
1547   if (lockedobjs->offset<MAXOBJLIST) {
1548     lockedobjs->objs[lockedobjs->offset++]=header;
1549   } else {
1550     struct objlist *tmp=malloc(sizeof(struct objlist));
1551     tmp->next=lockedobjs;
1552     tmp->objs[0]=header;
1553     tmp->offset=1;
1554     lockedobjs=tmp;
1555   }
1556   return header;
1557 }
1558
1559 /**
1560  * Inline fuction to get Transaction size per object type for those
1561  * objects that cause
1562  *
1563  **/
1564 /*
1565 INLINE void getTransSize(objheader_t *header , int *isObjTypeTraverse) {
1566   (typesCausingAbort[TYPE(header)]).numabort++;
1567   if(isObjTypeTraverse[TYPE(header)] != 1)
1568     (typesCausingAbort[TYPE(header)]).numaccess+=c_numelements;
1569   isObjTypeTraverse[TYPE(header)]=1;
1570 }
1571 */
1572
1573 #endif