Robust/src/Runtime/STM/stm.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 #endif
  26
  27 #ifdef TRANSSTATS
  28 int numTransCommit = 0;
  29 int numTransAbort = 0;
  30 int nSoftAbort = 0;
  31 int nSoftAbortCommit = 0;
  32 int nSoftAbortAbort = 0;
  33 #endif
  34
  35 #ifdef STMSTATS
  36 /* Thread variable for locking/unlocking */
  37 __thread threadrec_t *trec;
  38 __thread struct objlist * lockedobjs;
  39 /** Global lock **/
  40 int typesCausingAbort[TOTALNUMCLASSANDARRAY];
  41 /******Keep track of objects and types causing aborts******/
  42 /* TODO uncomment for later use
  43 #define DEBUGSTMSTAT(args...) { \
  44   printf(args); \
  45   fflush(stdout); \
  46 }
  47 */
  48 #define DEBUGSTMSTAT(args...)
  49 #else
  50 #define DEBUGSTMSTAT(args...)
  51 #endif
  52
  53 #ifdef STMDEBUG
  54 #define DEBUGSTM(x...) printf(x);
  55 #else
  56 #define DEBUGSTM(x...)
  57 #endif
  58
  59 #ifdef FASTMEMCPY
  60 void * A_memcpy (void * dest, const void * src, size_t count);
  61 #else
  62 #define A_memcpy memcpy
  63 #endif
  64
  65 extern void * curr_heapbase;
  66 extern void * curr_heapptr;
  67 extern void * curr_heaptop;
  68
  69 #ifdef STMSTATS
  70 /*** Global variables *****/
  71 objlockstate_t *objlockscope;
  72 /**
  73  * ABORTCOUNT
  74  * params: object header
  75  * Increments the abort count for each object
  76  **/
  77 void ABORTCOUNT(objheader_t * x) {
  78   x->abortCount++;
  79   if (x->abortCount > MAXABORTS && (x->riskyflag != 1)) {
  80     //makes riskflag sticky
  81     pthread_mutex_lock(&lockedobjstore);
  82     if (objlockscope->offset<MAXOBJLIST) {
  83       x->objlock=&(objlockscope->lock[objlockscope->offset++]);
  84     } else {
  85       objlockstate_t *tmp=malloc(sizeof(objlockstate_t));
  86       tmp->next=objlockscope;
  87       tmp->offset=1;
  88       x->objlock=&(tmp->lock[0]);
  89       objlockscope=tmp;
  90     }
  91     pthread_mutex_unlock(&lockedobjstore);
  92     pthread_mutex_init(x->objlock, NULL);
  93     //should put a memory barrier here
  94     x->riskyflag = 1;
  95   }
  96 }
  97 #endif
  98
  99 /* ==================================================
 100  * stmStartup
 101  * This function starts up the transaction runtime.
 102  * ==================================================
 103  */
 104 int stmStartup() {
 105   return 0;
 106 }
 107
 108 /* ======================================
 109  * objstrCreate
 110  * - create an object store of given size
 111  * ======================================
 112  */
 113 objstr_t *objstrCreate(unsigned int size) {
 114   objstr_t *tmp;
 115   if((tmp = calloc(1, (sizeof(objstr_t) + size))) == NULL) {
 116     printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__);
 117     return NULL;
 118   }
 119   tmp->size = size;
 120   tmp->next = NULL;
 121   tmp->top = tmp + 1; //points to end of objstr_t structure!
 122   return tmp;
 123 }
 124
 125 void objstrReset() {
 126   while(t_cache->next!=NULL) {
 127     objstr_t *next=t_cache->next;
 128     t_cache->next=t_reserve;
 129     t_reserve=t_cache;
 130     t_cache=next;
 131   }
 132   t_cache->top=t_cache+1;
 133 }
 134
 135 //free entire list, starting at store
 136 void objstrDelete(objstr_t *store) {
 137   objstr_t *tmp;
 138   while (store != NULL) {
 139     tmp = store->next;
 140     free(store);
 141     store = tmp;
 142   }
 143   return;
 144 }
 145
 146 /* =================================================
 147  * transStart
 148  * This function initializes things required in the
 149  * transaction start
 150  * =================================================
 151  */
 152 void transStart() {
 153   //Transaction start is currently free...commit and aborting is not
 154 }
 155
 156 /* =======================================================
 157  * transCreateObj
 158  * This function creates objects in the transaction record
 159  * =======================================================
 160  */
 161 objheader_t *transCreateObj(void * ptr, unsigned int size) {
 162   objheader_t *tmp = mygcmalloc(ptr, (sizeof(objheader_t) + size));
 163   objheader_t *retval=&tmp[1];
 164   tmp->lock=RW_LOCK_BIAS;
 165   tmp->version = 1;
 166   //initialize obj lock to the header
 167   STATUS(tmp)=NEW;
 168   // don't insert into table
 169   if (newobjs->offset<MAXOBJLIST) {
 170     newobjs->objs[newobjs->offset++]=retval;
 171   } else {
 172     struct objlist *tmp=malloc(sizeof(struct objlist));
 173     tmp->next=newobjs;
 174     tmp->objs[0]=retval;
 175     tmp->offset=1;
 176     newobjs=tmp;
 177   }
 178   return retval; //want space after object header
 179 }
 180
 181 /* This functions inserts randowm wait delays in the order of msec
 182  * Mostly used when transaction commits retry*/
 183 void randomdelay(int softaborted) {
 184   struct timespec req;
 185   struct timeval t;
 186
 187   gettimeofday(&t,NULL);
 188
 189   req.tv_sec = 0;
 190   req.tv_nsec = (long)((t.tv_usec)%(1<<softaborted))<<1; //1-11 microsec
 191   nanosleep(&req, NULL);
 192   return;
 193 }
 194
 195 /* ==============================================
 196  * objstrAlloc
 197  * - allocate space in an object store
 198  * ==============================================
 199  */
 200 void *objstrAlloc(unsigned int size) {
 201   void *tmp;
 202   int i=0;
 203   objstr_t *store=t_cache;
 204   if ((size&7)!=0) {
 205     size+=(8-(size&7));
 206   }
 207
 208   for(; i<2; i++) {
 209     if (OSFREE(store)>=size) {
 210       tmp=store->top;
 211       store->top +=size;
 212       return tmp;
 213     }
 214     if ((store=store->next)==NULL)
 215       break;
 216   }
 217
 218   {
 219     unsigned int newsize=size>DEFAULT_OBJ_STORE_SIZE ? size : DEFAULT_OBJ_STORE_SIZE;
 220     objstr_t **otmp=&t_reserve;
 221     objstr_t *ptr;
 222     while((ptr=*otmp)!=NULL) {
 223       if (ptr->size>=newsize) {
 224         //remove from list
 225         *otmp=ptr->next;
 226         ptr->next=t_cache;
 227         t_cache=ptr;
 228         ptr->top=((char *)(&ptr[1]))+size;
 229         return &ptr[1];
 230       }
 231     }
 232
 233     objstr_t *os=(objstr_t *)calloc(1,(sizeof(objstr_t) + newsize));
 234     void *nptr=&os[1];
 235     os->next=t_cache;
 236     t_cache=os;
 237     os->size=newsize;
 238     os->top=((char *)nptr)+size;
 239     return nptr;
 240   }
 241 }
 242
 243 /* =============================================================
 244  * transRead
 245  * -finds the objects either in main heap
 246  * -copies the object into the transaction cache
 247  * =============================================================
 248  */
 249 __attribute__((pure)) void *transRead(void * oid, void *gl) {
 250   objheader_t *tmp, *objheader;
 251   objheader_t *objcopy;
 252   int size;
 253
 254   /* Read from the main heap */
 255   //No lock for now
 256   objheader_t *header = (objheader_t *)(((char *)oid) - sizeof(objheader_t));
 257   GETSIZE(size, header);
 258   size += sizeof(objheader_t);
 259   objcopy = (objheader_t *) objstrAlloc(size);
 260 #ifdef STMSTATS
 261   header->accessCount++;
 262   if(header->riskyflag) {
 263     header=needLock(header,gl);
 264   }
 265 #endif
 266   A_memcpy(objcopy, header, size);
 267   /* Insert into cache's lookup table */
 268   STATUS(objcopy)=0;
 269   if (((unsigned int)oid)<((unsigned int ) curr_heapbase)|| ((unsigned int)oid) >((unsigned int) curr_heapptr))
 270     printf("ERROR! Bad object address!\n");
 271   t_chashInsert(oid, &objcopy[1]);
 272   return &objcopy[1];
 273 }
 274
 275 void freenewobjs() {
 276   struct objlist *ptr=newobjs;
 277   while(ptr->next!=NULL) {
 278     struct objlist *tmp=ptr->next;
 279     free(ptr);
 280     ptr=tmp;
 281   }
 282   ptr->offset=0;
 283   newobjs=ptr;
 284 }
 285
 286 #ifdef STMSTATS
 287 void freelockedobjs() {
 288   struct objlist *ptr=lockedobjs;
 289   while(ptr->next!=NULL) {
 290     struct objlist *tmp=ptr->next;
 291     free(ptr);
 292     ptr=tmp;
 293   }
 294   ptr->offset=0;
 295   lockedobjs=ptr;
 296 }
 297 #endif
 298
 299 /* ================================================================
 300  * transCommit
 301  * - This function initiates the transaction commit process
 302  * - goes through the transaction cache and decides
 303  * - a final response
 304  * ================================================================
 305  */
 306 #ifdef DELAYCOMP
 307 int transCommit(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 308 #else
 309 int transCommit() {
 310 #endif
 311   int softaborted=0;
 312   do {
 313     /* Look through all the objects in the transaction hash table */
 314     int finalResponse;
 315 #ifdef DELAYCOMP
 316     if (c_numelements<(c_size>>3))
 317       finalResponse= alttraverseCache(commitmethod, primitives, locals, params);
 318     else
 319       finalResponse= traverseCache(commitmethod, primitives, locals, params);
 320 #else
 321     if (c_numelements<(c_size>>3))
 322       finalResponse= alttraverseCache();
 323     else
 324       finalResponse= traverseCache();
 325 #endif
 326     if(finalResponse == TRANS_ABORT) {
 327 #ifdef TRANSSTATS
 328       numTransAbort++;
 329       if (softaborted) {
 330         nSoftAbortAbort++;
 331       }
 332 #endif
 333       freenewobjs();
 334 #ifdef STMSTATS
 335       freelockedobjs();
 336 #endif
 337       objstrReset();
 338       t_chashreset();
 339 #ifdef DELAYCOMP
 340       dc_t_chashreset();
 341       ptrstack.count=0;
 342       primstack.count=0;
 343 #endif
 344       return TRANS_ABORT;
 345     }
 346     if(finalResponse == TRANS_COMMIT) {
 347 #ifdef TRANSSTATS
 348       numTransCommit++;
 349       if (softaborted) {
 350         nSoftAbortCommit++;
 351       }
 352 #endif
 353       freenewobjs();
 354 #ifdef STMSTATS
 355       freelockedobjs();
 356 #endif
 357       objstrReset();
 358       t_chashreset();
 359 #ifdef DELAYCOMP
 360       dc_t_chashreset();
 361       ptrstack.count=0;
 362       primstack.count=0;
 363 #endif
 364       return 0;
 365     }
 366     /* wait a random amount of time before retrying to commit transaction*/
 367     if(finalResponse == TRANS_SOFT_ABORT) {
 368 #ifdef TRANSSTATS
 369       nSoftAbort++;
 370 #endif
 371       softaborted++;
 372 #ifdef SOFTABORT
 373       if (softaborted>1) {
 374 #else
 375       if (1) {
 376 #endif
 377         //retry if too many soft aborts
 378         freenewobjs();
 379 #ifdef STMSTATS
 380     freelockedobjs();
 381 #endif
 382         objstrReset();
 383         t_chashreset();
 384 #ifdef DELAYCOMP
 385         dc_t_chashreset();
 386         ptrstack.count=0;
 387         primstack.count=0;
 388 #endif
 389         return TRANS_ABORT;
 390       }
 391       //randomdelay(softaborted);
 392     } else {
 393       printf("Error: in %s() Unknown outcome", __func__);
 394       exit(-1);
 395     }
 396   } while (1);
 397 }
 398
 399 #ifdef DELAYCOMP
 400 #define freearrays   if (c_numelements>=200) { \
 401     free(oidrdlocked); \
 402     free(oidrdversion); \
 403   } \
 404   if (t_numelements>=200) { \
 405     free(oidwrlocked); \
 406   }
 407 #else
 408 #define freearrays   if (c_numelements>=200) { \
 409     free(oidrdlocked); \
 410     free(oidrdversion); \
 411     free(oidwrlocked); \
 412   }
 413 #endif
 414 /* ==================================================
 415  * traverseCache
 416  * - goes through the transaction cache and
 417  * - decides if a transaction should commit or abort
 418  * ==================================================
 419  */
 420 #ifdef DELAYCOMP
 421 int traverseCache(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 422 #else
 423 int traverseCache() {
 424 #endif
 425   /* Create info to keep track of objects that can be locked */
 426   int numoidrdlocked=0;
 427   int numoidwrlocked=0;
 428   void * rdlocked[200];
 429   int rdversion[200];
 430   void * wrlocked[200];
 431   int softabort=0;
 432   int i;
 433   void ** oidrdlocked;
 434   void ** oidwrlocked;
 435   int * oidrdversion;
 436 #ifdef DELAYCOMP
 437   int t_numelements=c_numelements+dc_c_numelements;
 438   if (t_numelements<200) {
 439     oidwrlocked=wrlocked;
 440   } else {
 441     oidwrlocked=malloc(t_numelements*sizeof(void *));
 442   }
 443   if (c_numelements<200) {
 444     oidrdlocked=rdlocked;
 445     oidrdversion=rdversion;
 446   } else {
 447     int size=c_numelements*sizeof(void*);
 448     oidrdlocked=malloc(size);
 449     oidrdversion=malloc(size);
 450   }
 451 #else
 452   if (c_numelements<200) {
 453     oidrdlocked=rdlocked;
 454     oidrdversion=rdversion;
 455     oidwrlocked=wrlocked;
 456   } else {
 457     int size=c_numelements*sizeof(void*);
 458     oidrdlocked=malloc(size);
 459     oidrdversion=malloc(size);
 460     oidwrlocked=malloc(size);
 461   }
 462 #endif
 463   chashlistnode_t *ptr = c_table;
 464   /* Represents number of bins in the chash table */
 465   unsigned int size = c_size;
 466   for(i = 0; i<size; i++) {
 467     chashlistnode_t *curr = &ptr[i];
 468     /* Inner loop to traverse the linked list of the cache lookupTable */
 469     while(curr != NULL) {
 470       //if the first bin in hash table is empty
 471       if(curr->key == NULL)
 472         break;
 473       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 474       objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
 475       unsigned int version = headeraddr->version;
 476
 477       if(STATUS(headeraddr) & DIRTY) {
 478         /* Read from the main heap  and compare versions */
 479         if(write_trylock(&header->lock)) { //can aquire write lock
 480           if (version == header->version) { /* versions match */
 481             /* Keep track of objects locked */
 482             oidwrlocked[numoidwrlocked++] = header;
 483           } else {
 484             oidwrlocked[numoidwrlocked++] = header;
 485             transAbortProcess(oidwrlocked, numoidwrlocked);
 486 #ifdef STMSTATS
 487             ABORTCOUNT(header);
 488             (typesCausingAbort[TYPE(header)])++;
 489             getTotalAbortCount(i+1, size, (void *)(curr->next), NULL, 1);
 490 #endif
 491             DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 492             DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 493             freearrays;
 494             if (softabort)
 495             return TRANS_SOFT_ABORT;
 496               else
 497             return TRANS_ABORT;
 498           }
 499         } else {
 500           if(version == header->version) {
 501             /* versions match */
 502             softabort=1;
 503           }
 504           transAbortProcess(oidwrlocked, numoidwrlocked);
 505 #ifdef STMSTATS
 506           ABORTCOUNT(header);
 507           (typesCausingAbort[TYPE(header)])++;
 508 #endif
 509 #if defined(STMSTATS)||defined(SOFTABORT)
 510           if (getTotalAbortCount(i+1, size, (void *)(curr->next), NULL, 1))
 511             softabort=0;
 512 #endif
 513           DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 514           DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 515           freearrays;
 516           if (softabort)
 517             return TRANS_SOFT_ABORT;
 518           else
 519             return TRANS_ABORT;
 520         }
 521       } else {
 522         oidrdversion[numoidrdlocked]=version;
 523         oidrdlocked[numoidrdlocked++] = header;
 524       }
 525       curr = curr->next;
 526     }
 527   } //end of for
 528
 529 #ifdef DELAYCOMP
 530   //acquire other locks
 531   unsigned int numoidwrtotal=numoidwrlocked;
 532
 533   chashlistnode_t *dc_curr = dc_c_list;
 534   /* Inner loop to traverse the linked list of the cache lookupTable */
 535   while(likely(dc_curr != NULL)) {
 536     //if the first bin in hash table is empty
 537     objheader_t * headeraddr=&((objheader_t *) dc_curr->val)[-1];
 538     objheader_t *header=(objheader_t *)(((char *)dc_curr->key)-sizeof(objheader_t));
 539     if(write_trylock(&header->lock)) { //can aquire write lock
 540       oidwrlocked[numoidwrtotal++] = header;
 541     } else {
 542       //maybe we already have lock
 543       void * key=dc_curr->key;
 544       chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 545
 546       do {
 547         if(node->key == key) {
 548           goto nextloop;
 549         }
 550         node = node->next;
 551       } while(node != NULL);
 552
 553       //have to abort to avoid deadlock
 554       transAbortProcess(oidwrlocked, numoidwrlocked);
 555 #ifdef STMSTATS
 556       ABORTCOUNT(header);
 557       (typesCausingAbort[TYPE(header)])++;
 558 #endif
 559 #if defined(STMSTATS)||defined(SOFTABORT)
 560       if (getTotalAbortCount(i+1, size, (void *)(curr->next), NULL, 1))
 561         softabort=0;
 562 #endif
 563       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 564       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 565       freearrays;
 566       if (softabort)
 567         return TRANS_SOFT_ABORT;
 568       else
 569         return TRANS_ABORT;
 570     }
 571   nextloop:
 572     dc_curr = dc_curr->lnext;
 573   }
 574 #endif
 575
 576   //THIS IS THE SERIALIZATION END POINT (START POINT IS END OF EXECUTION)*****
 577
 578   for(i=0; i<numoidrdlocked; i++) {
 579     /* Read from the main heap  and compare versions */
 580     objheader_t *header=oidrdlocked[i];
 581     unsigned int version=oidrdversion[i];
 582     if(header->lock>0) { //not write locked
 583       if(version != header->version) { /* versions do not match */
 584         oidrdlocked[numoidrdlocked++] = header;
 585         transAbortProcess(oidwrlocked, numoidwrlocked);
 586 #ifdef STMSTATS
 587         ABORTCOUNT(header);
 588         (typesCausingAbort[TYPE(header)])++;
 589         getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *) oidrdversion, 0);
 590 #endif
 591         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 592         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 593         freearrays;
 594         return TRANS_ABORT;
 595       }
 596     } else { /* cannot aquire lock */
 597       //do increment as we didn't get lock
 598       if(version == header->version) {
 599         softabort=1;
 600       }
 601       transAbortProcess(oidwrlocked, numoidwrlocked);
 602 #ifdef STMSTATS
 603       ABORTCOUNT(header);
 604       (typesCausingAbort[TYPE(header)])++;
 605 #endif
 606 #if defined(STMSTATS)||defined(SOFTABORT)
 607       if (getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *) oidrdversion, 0))
 608         softabort=0;
 609 #endif
 610       DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 611       DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 612       freearrays;
 613       if (softabort)
 614         return TRANS_SOFT_ABORT;
 615       else
 616         return TRANS_ABORT;
 617     }
 618   }
 619
 620   /* Decide the final response */
 621 #ifdef DELAYCOMP
 622   transCommitProcess(oidwrlocked, numoidwrlocked, numoidwrtotal, commitmethod, primitives, locals, params);
 623 #else
 624   transCommitProcess(oidwrlocked, numoidwrlocked);
 625 #endif
 626   DEBUGSTM("Commit: rd: %u wr: %u tot: %u\n", numoidrdlocked, numoidwrlocked, c_numelements);
 627   freearrays;
 628   return TRANS_COMMIT;
 629 }
 630
 631 /* ==================================================
 632  * alttraverseCache
 633  * - goes through the transaction cache and
 634  * - decides if a transaction should commit or abort
 635  * ==================================================
 636  */
 637
 638 #ifdef DELAYCOMP
 639 int alttraverseCache(void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
 640 #else
 641 int alttraverseCache() {
 642 #endif
 643   /* Create info to keep track of objects that can be locked */
 644   int numoidrdlocked=0;
 645   int numoidwrlocked=0;
 646   void * rdlocked[200];
 647   int rdversion[200];
 648   void * wrlocked[200];
 649   int softabort=0;
 650   int i;
 651   void ** oidrdlocked;
 652   int * oidrdversion;
 653   void ** oidwrlocked;
 654 #ifdef DELAYCOMP
 655   int t_numelements=c_numelements+dc_c_numelements;
 656   if (t_numelements<200) {
 657     oidwrlocked=wrlocked;
 658   } else {
 659     oidwrlocked=malloc(t_numelements*sizeof(void *));
 660   }
 661   if (c_numelements<200) {
 662     oidrdlocked=rdlocked;
 663     oidrdversion=rdversion;
 664   } else {
 665     int size=c_numelements*sizeof(void*);
 666     oidrdlocked=malloc(size);
 667     oidrdversion=malloc(size);
 668   }
 669 #else
 670   if (c_numelements<200) {
 671     oidrdlocked=rdlocked;
 672     oidrdversion=rdversion;
 673     oidwrlocked=wrlocked;
 674   } else {
 675     int size=c_numelements*sizeof(void*);
 676     oidrdlocked=malloc(size);
 677     oidrdversion=malloc(size);
 678     oidwrlocked=malloc(size);
 679   }
 680 #endif
 681   chashlistnode_t *curr = c_list;
 682   /* Inner loop to traverse the linked list of the cache lookupTable */
 683   while(likely(curr != NULL)) {
 684     //if the first bin in hash table is empty
 685     objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 686     objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
 687     unsigned int version = headeraddr->version;
 688
 689     if(STATUS(headeraddr) & DIRTY) {
 690       /* Read from the main heap  and compare versions */
 691       if(likely(write_trylock(&header->lock))) { //can aquire write lock
 692         if (likely(version == header->version)) { /* versions match */
 693           /* Keep track of objects locked */
 694           oidwrlocked[numoidwrlocked++] = header;
 695         } else {
 696           oidwrlocked[numoidwrlocked++] = header;
 697           transAbortProcess(oidwrlocked, numoidwrlocked);
 698 #ifdef STMSTATS
 699           ABORTCOUNT(header);
 700           (typesCausingAbort[TYPE(header)])++;
 701           getTotalAbortCount(0, 1, (void *) curr->next, NULL, 1);
 702 #endif
 703           DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 704           DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 705           freearrays;
 706           return TRANS_ABORT;
 707         }
 708       } else { /* cannot aquire lock */
 709         if(version == header->version) {
 710           /* versions match */
 711           softabort=1;
 712         }
 713         transAbortProcess(oidwrlocked, numoidwrlocked);
 714 #ifdef STMSTATS
 715         ABORTCOUNT(header);
 716         (typesCausingAbort[TYPE(header)])++;
 717 #endif
 718 #if defined(STMSTATS)||defined(SOFTABORT)
 719         if (getTotalAbortCount(0, 1, (void *) curr->next, NULL, 1))
 720           softabort=0;
 721 #endif
 722         DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 723         DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 724         freearrays;
 725         if (softabort)
 726           return TRANS_SOFT_ABORT;
 727         else
 728           return TRANS_ABORT;
 729       }
 730     } else {
 731       /* Read from the main heap  and compare versions */
 732       oidrdversion[numoidrdlocked]=version;
 733       oidrdlocked[numoidrdlocked++] = header;
 734     }
 735     curr = curr->lnext;
 736   }
 737
 738 #ifdef DELAYCOMP
 739   //acquire other locks
 740   unsigned int numoidwrtotal=numoidwrlocked;
 741   chashlistnode_t *dc_curr = dc_c_list;
 742   /* Inner loop to traverse the linked list of the cache lookupTable */
 743   while(likely(dc_curr != NULL)) {
 744     //if the first bin in hash table is empty
 745     objheader_t * headeraddr=&((objheader_t *) dc_curr->val)[-1];
 746     objheader_t *header=(objheader_t *)(((char *)dc_curr->key)-sizeof(objheader_t));
 747     if(write_trylock(&header->lock)) { //can aquire write lock
 748       oidwrlocked[numoidwrtotal++] = header;
 749     } else {
 750       //maybe we already have lock
 751       void * key=dc_curr->key;
 752       chashlistnode_t *node = &c_table[(((unsigned INTPTR)key) & c_mask)>>4];
 753
 754       do {
 755         if(node->key == key) {
 756           goto nextloop;
 757         }
 758         node = node->next;
 759       } while(node != NULL);
 760
 761       //have to abort to avoid deadlock
 762       transAbortProcess(oidwrlocked, numoidwrlocked);
 763 #ifdef STMSTATS
 764       ABORTCOUNT(header);
 765       (typesCausingAbort[TYPE(header)])++;
 766 #endif
 767 #if defined(STMSTATS)||defined(SOFTABORT)
 768       if (getTotalAbortCount(i+1, size, (void *)(curr->next), NULL, 1))
 769         softabort=0;
 770 #endif
 771       DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 772       DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 773       freearrays;
 774       if (softabort)
 775         return TRANS_SOFT_ABORT;
 776       else
 777         return TRANS_ABORT;
 778     }
 779   nextloop:
 780     dc_curr = dc_curr->lnext;
 781   }
 782 #endif
 783
 784   //THIS IS THE SERIALIZATION END POINT (START POINT IS END OF EXECUTION)*****
 785
 786   for(i=0; i<numoidrdlocked; i++) {
 787     objheader_t * header=oidrdlocked[i];
 788     unsigned int version=oidrdversion[i];
 789     if(header->lock>=0) {
 790       if(version != header->version) {
 791         transAbortProcess(oidwrlocked, numoidwrlocked);
 792 #ifdef STMSTATS
 793         ABORTCOUNT(header);
 794         (typesCausingAbort[TYPE(header)])++;
 795         getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *)oidrdversion, 0);
 796 #endif
 797         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 798         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 799         freearrays;
 800         return TRANS_ABORT;
 801       }
 802     } else { /* cannot aquire lock */
 803       if(version == header->version) {
 804         softabort=1;
 805       }
 806       transAbortProcess(oidwrlocked, numoidwrlocked);
 807 #ifdef STMSTATS
 808       ABORTCOUNT(header);
 809       (typesCausingAbort[TYPE(header)])++;
 810 #endif
 811 #if defined(STMSTATS)||defined(SOFTABORT)
 812       if (getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *)oidrdversion, 0))
 813         softabort=0;
 814 #endif
 815       DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 816       DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 817       freearrays;
 818       if (softabort)
 819         return TRANS_SOFT_ABORT;
 820       else
 821         return TRANS_ABORT;
 822     }
 823   }
 824
 825   /* Decide the final response */
 826 #ifdef DELAYCOMP
 827   transCommitProcess(oidwrlocked, numoidwrlocked, numoidwrtotal, commitmethod, primitives, locals, params);
 828 #else
 829   transCommitProcess(oidwrlocked, numoidwrlocked);
 830 #endif
 831   DEBUGSTM("Commit: rd: %u wr: %u tot: %u\n", numoidrdlocked, numoidwrlocked, c_numelements);
 832   freearrays;
 833   return TRANS_COMMIT;
 834 }
 835
 836 #if 0
 837 int altalttraverseCache() {
 838   /* Create info to keep track of objects that can be locked */
 839   int numoidrdlocked=0;
 840   int numoidwrlocked=0;
 841   void * rdlocked[200];
 842   int rdversion[200];
 843   void * wrlocked[200];
 844   int softabort=0;
 845   int i;
 846   void ** oidrdlocked;
 847   int * oidrdversion;
 848   void ** oidwrlocked;
 849   if (c_numelements<200) {
 850     oidrdlocked=rdlocked;
 851     oidrdversion=rdversion;
 852     oidwrlocked=wrlocked;
 853   } else {
 854     int size=c_numelements*sizeof(void*);
 855     oidrdlocked=malloc(size);
 856     oidrdversion=malloc(size);
 857     oidwrlocked=malloc(size);
 858   }
 859
 860   objstr_t * curr=t_cache;
 861
 862   while(curr != NULL) {
 863     char * bottom;
 864
 865     for(bottom=(char *)(curr+1);bottom < ((char *)curr->top);) {
 866       objheader_t *headeraddr=(objheader_t *)bottom;
 867       objheader_t *header=OID(headeraddr)-sizeof(objheader_t);
 868       unsigned int version = headeraddr->version;
 869
 870       if(STATUS(headeraddr) & DIRTY) {
 871         /* Read from the main heap  and compare versions */
 872         if(likely(write_trylock(&header->lock))) { //can aquire write lock
 873           if (likely(version == header->version)) { /* versions match */
 874             /* Keep track of objects locked */
 875             oidwrlocked[numoidwrlocked++] = header;
 876           } else {
 877             oidwrlocked[numoidwrlocked++] = header;
 878             transAbortProcess(oidwrlocked, numoidwrlocked);
 879 #ifdef STMSTATS
 880             ABORTCOUNT(header);
 881             (typesCausingAbort[TYPE(header)])++;
 882             //getTotalAbortCount(0, 1, (void *) curr->next, NULL, 1);
 883 #endif
 884             DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 885             DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 886             if (c_numelements>=200) {
 887               free(oidrdlocked);
 888               free(oidrdversion);
 889               free(oidwrlocked);
 890             }
 891             return TRANS_ABORT;
 892           }
 893         } else { /* cannot aquire lock */
 894           if(version == header->version) {
 895             /* versions match */
 896             softabort=1;
 897           }
 898           transAbortProcess(oidwrlocked, numoidwrlocked);
 899 #ifdef STMSTATS
 900           ABORTCOUNT(header);
 901           (typesCausingAbort[TYPE(header)])++;
 902 #endif
 903 #if defined(STMSTATS)||defined(SOFTABORT)
 904           // if (getTotalAbortCount(0, 1, (void *) curr->next, NULL, 1))
 905           // softabort=0;
 906 #endif
 907           DEBUGSTM("WR Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 908           DEBUGSTMSTAT("WR Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 909           if (c_numelements>=200) {
 910             free(oidrdlocked);
 911             free(oidrdversion);
 912             free(oidwrlocked);
 913           }
 914           if (softabort)
 915             return TRANS_SOFT_ABORT;
 916           else
 917             return TRANS_ABORT;
 918         }
 919       } else {
 920         /* Read from the main heap  and compare versions */
 921         oidrdversion[numoidrdlocked]=version;
 922         oidrdlocked[numoidrdlocked++] = header;
 923       }
 924       unsigned int size;
 925       GETSIZE(size, headeraddr);
 926       size+=sizeof(objheader_t);
 927       if ((size&7)!=0)
 928         size+=(8-(size&7));
 929
 930       bottom+=size;
 931     }
 932     curr = curr->next;
 933   }
 934   //THIS IS THE SERIALIZATION POINT *****
 935   for(i=0; i<numoidrdlocked; i++) {
 936     objheader_t * header = oidrdlocked[i];
 937     unsigned int version=oidrdversion[i];
 938     if(header->lock>=0) {
 939       if(version != header->version) {
 940         transAbortProcess(oidwrlocked, numoidwrlocked);
 941 #ifdef STMSTATS
 942         ABORTCOUNT(header);
 943         (typesCausingAbort[TYPE(header)])++;
 944         getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *)oidrdversion, 0);
 945 #endif
 946         DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 947         DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 948         if (c_numelements>=200) {
 949           free(oidrdlocked);
 950           free(oidrdversion);
 951           free(oidwrlocked);
 952         }
 953         return TRANS_ABORT;
 954       }
 955     } else { /* cannot aquire lock */
 956       if(version == header->version) {
 957         softabort=1;
 958       }
 959       transAbortProcess(oidwrlocked, numoidwrlocked);
 960 #ifdef STMSTATS
 961       ABORTCOUNT(header);
 962       (typesCausingAbort[TYPE(header)])++;
 963 #endif
 964 #if defined(STMSTATS)||defined(SOFTABORT)
 965       if (getTotalAbortCount(i+1, numoidrdlocked, oidrdlocked, (void *)oidrdversion, 0))
 966         softabort=0;
 967 #endif
 968       DEBUGSTM("RD Abort: rd: %u wr: %u tot: %u type: %u ver: %u\n", numoidrdlocked, numoidwrlocked, c_numelements, TYPE(header), header->version);
 969       DEBUGSTMSTAT("RD Abort: Access Count: %u AbortCount: %u type: %u ver: %u \n", header->accessCount, header->abortCount, TYPE(header), header->version);
 970       if (c_numelements>=200) {
 971         free(oidrdlocked);
 972         free(oidrdversion);
 973         free(oidwrlocked);
 974       }
 975       if (softabort)
 976         return TRANS_SOFT_ABORT;
 977       else
 978         return TRANS_ABORT;
 979     }
 980   }
 981
 982   /* Decide the final response */
 983   transCommitProcess(oidwrlocked, numoidwrlocked);
 984   DEBUGSTM("Commit: rd: %u wr: %u tot: %u\n", numoidrdlocked, numoidwrlocked, c_numelements);
 985   if (c_numelements>=200) {
 986     free(oidrdlocked);
 987     free(oidrdversion);
 988     free(oidwrlocked);
 989   }
 990   return TRANS_COMMIT;
 991 }
 992 #endif
 993
 994 /* ==================================
 995  * transAbortProcess
 996  *
 997  * =================================
 998  */
 999 void transAbortProcess(void **oidwrlocked, int numoidwrlocked) {
1000   int i;
1001   objheader_t *header;
1002   /* Release read locks */
1003
1004   /* Release write locks */
1005   for(i=numoidwrlocked-1; i>=0; i--) {
1006     /* Read from the main heap */
1007     header = (objheader_t *)oidwrlocked[i];
1008     write_unlock(&header->lock);
1009   }
1010
1011 #ifdef STMSTATS
1012   /* clear trec and then release objects locked */
1013   struct objlist *ptr=lockedobjs;
1014   while(ptr!=NULL) {
1015     int max=ptr->offset;
1016     for(i=max-1; i>=0; i--) {
1017       header = (objheader_t *)ptr->objs[i];
1018       header->trec = NULL;
1019       pthread_mutex_unlock(header->objlock);
1020     }
1021     ptr=ptr->next;
1022   }
1023 #endif
1024 }
1025
1026 /* ==================================
1027  * transCommitProcess
1028  *
1029  * =================================
1030  */
1031 #ifdef DELAYCOMP
1032  void transCommitProcess(void ** oidwrlocked, int numoidwrlocked, int numoidwrtotal, void (*commitmethod)(void *, void *, void *), void * primitives, void * locals, void * params) {
1033 #else
1034    void transCommitProcess(void ** oidwrlocked, int numoidwrlocked) {
1035 #endif
1036   objheader_t *header;
1037   void *ptrcreate;
1038   int i;
1039   struct objlist *ptr=newobjs;
1040   while(ptr!=NULL) {
1041     int max=ptr->offset;
1042     for(i=0; i<max; i++) {
1043       //clear the new flag
1044       ((struct ___Object___ *)ptr->objs[i])->___objstatus___=0;
1045     }
1046     ptr=ptr->next;
1047   }
1048
1049   /* Copy from transaction cache -> main object store */
1050   for (i = numoidwrlocked-1; i >=0; i--) {
1051     /* Read from the main heap */
1052     header = (objheader_t *)oidwrlocked[i];
1053     int tmpsize;
1054     GETSIZE(tmpsize, header);
1055     struct ___Object___ *dst=(struct ___Object___*)(((char *)oidwrlocked[i])+sizeof(objheader_t));
1056     struct ___Object___ *src=t_chashSearch(dst);
1057     dst->___cachedCode___=src->___cachedCode___;
1058     dst->___cachedHash___=src->___cachedHash___;
1059     A_memcpy(&dst[1], &src[1], tmpsize-sizeof(struct ___Object___));
1060     __asm__ __volatile__("": : :"memory");
1061     header->version++;
1062   }
1063   __asm__ __volatile__("": : :"memory");
1064
1065 #ifdef DELAYCOMP
1066   //  call commit method
1067   ptrstack.count=0;
1068   primstack.count=0;
1069   commitmethod(params, locals, primitives);
1070 #endif
1071
1072   /* Release write locks */
1073 #ifdef DELAYCOMP
1074   for(i=numoidwrtotal-1; i>=0; i--) {
1075 #else
1076   for(i=numoidwrlocked-1; i>=0; i--) {
1077 #endif
1078     header = (objheader_t *)oidwrlocked[i];
1079     write_unlock(&header->lock);
1080   }
1081
1082 #ifdef STMSTATS
1083   /* clear trec and then release objects locked */
1084   ptr=lockedobjs;
1085   while(ptr!=NULL) {
1086     int max=ptr->offset;
1087     for(i=max-1; i>=0; i--) {
1088       header = (objheader_t *)ptr->objs[i];
1089       header->trec = NULL;
1090       pthread_mutex_unlock(header->objlock);
1091     }
1092     ptr=ptr->next;
1093   }
1094 #endif
1095 }
1096
1097 /** ========================================================================================
1098  * getTotalAbortCount
1099  * params : start: start index of the loop
1100  *        : stop: stop index of the loop
1101  *        : startptr: pointer that points to where to start looking in the array/ linked list
1102  *          0='r'/1='w' if found when visiting objects read/ objects modified
1103  * =========================================================================================
1104  **/
1105 #if defined(STMSTATS)||defined(SOFTABORT)
1106 int getTotalAbortCount(int start, int stop, void *startptr, void *checkptr, int type) {
1107   int i;
1108   int hardabort=0;
1109   if(type) {
1110     int isFirstTime = 0;
1111     chashlistnode_t *curr = (chashlistnode_t *) startptr;
1112     chashlistnode_t *ptr = c_table;
1113     for(i = start; i < stop; i++) {
1114       if(!isFirstTime)
1115         curr = &ptr[i];
1116       /* Inner loop to traverse the linked list of the cache lookupTable */
1117       while(curr != NULL) {
1118         if(curr->key == NULL)
1119           break;
1120         objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
1121         objheader_t *header=(objheader_t *)(((char *)curr->key)-sizeof(objheader_t));
1122         unsigned int version = headeraddr->version;
1123         /* versions do not match */
1124         if(version != header->version) {
1125 #ifdef STMSTATS
1126           ABORTCOUNT(header);
1127           (typesCausingAbort[TYPE(header)])++;
1128 #endif
1129           hardabort=1;
1130         }
1131         curr = curr->next;
1132       }
1133       isFirstTime = 1;
1134     }
1135   } else {
1136     /* Go through oids read that are locked */
1137     for(i = start; i < stop; i++) {
1138       objheader_t *header = ((void **)startptr)[i];
1139       unsigned int version = ((int *)checkptr)[i];
1140       if(version != header->version) { /* versions do not match */
1141 #ifdef STMSTATS
1142         ABORTCOUNT(header);
1143         (typesCausingAbort[TYPE(header)])++;
1144 #endif
1145         hardabort=1;
1146       }
1147     }
1148   }
1149   return hardabort;
1150 }
1151
1152 /**
1153  * needLock
1154  * params: Object header
1155  * Locks an object that causes aborts
1156  **/
1157 objheader_t * needLock(objheader_t *header, void *gl) {
1158   int lockstatus;
1159   threadrec_t *ptr;
1160   while((lockstatus = pthread_mutex_trylock(header->objlock))
1161       && ((ptr = header->trec) == NULL)) { //retry
1162     ;
1163   }
1164   if(lockstatus==0) { //acquired lock
1165     /* Set trec */
1166     header->trec = trec;
1167   } else { //failed to get lock
1168     trec->blocked=1;
1169     //memory barrier
1170     __asm__ __volatile__("":::"memory");
1171     //see if other thread is blocked
1172     if(ptr->blocked == 1) {
1173       //it might be block, so ignore lock and clear our blocked flag
1174       trec->blocked=0;
1175       return;
1176     } else {
1177 #ifdef PRECISE_GC
1178       INTPTR ptrarray[]={1, (INTPTR)gl, (INTPTR) header};
1179       void *lockptr=header->objlock;
1180       stopforgc((struct garbagelist *)ptrarray);
1181       //grab lock and wait our turn
1182       pthread_mutex_lock(lockptr);
1183       restartaftergc();
1184       header=(objheader_t *) ptrarray[2];
1185 #else
1186       pthread_mutex_lock(header->objptr);
1187 #endif
1188       /* we have lock, so we are not blocked anymore */
1189       trec->blocked = 0;
1190       /* Set our trec */
1191       header->trec = trec;
1192     }
1193   }
1194   //trec->blocked is zero now
1195
1196   /* Save the locked object */
1197   if (lockedobjs->offset<MAXOBJLIST) {
1198     lockedobjs->objs[lockedobjs->offset++]=header;
1199   } else {
1200     struct objlist *tmp=malloc(sizeof(struct objlist));
1201     tmp->next=lockedobjs;
1202     tmp->objs[0]=header;
1203     tmp->offset=1;
1204     lockedobjs=tmp;
1205   }
1206   return header;
1207 }
1208 #endif