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