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 /* Thread transaction variables */
  16 __thread objstr_t *t_cache;
  17 __thread objstr_t *t_reserve;
  18 __thread struct objlist * newobjs;
  19
  20 #ifdef TRANSSTATS
  21 int numTransCommit = 0;
  22 int numTransAbort = 0;
  23 int nSoftAbort = 0;
  24 int nSoftAbortCommit = 0;
  25 int nSoftAbortAbort = 0;
  26 #endif
  27
  28
  29 /* ==================================================
  30  * stmStartup
  31  * This function starts up the transaction runtime.
  32  * ==================================================
  33  */
  34 int stmStartup() {
  35   return 0;
  36 }
  37
  38 /* ======================================
  39  * objstrCreate
  40  * - create an object store of given size
  41  * ======================================
  42  */
  43 objstr_t *objstrCreate(unsigned int size) {
  44   objstr_t *tmp;
  45   if((tmp = calloc(1, (sizeof(objstr_t) + size))) == NULL) {
  46     printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__);
  47     return NULL;
  48   }
  49   tmp->size = size;
  50   tmp->next = NULL;
  51   tmp->top = tmp + 1; //points to end of objstr_t structure!
  52   return tmp;
  53 }
  54
  55 void objstrReset() {
  56   while(t_cache->next!=NULL) {
  57     objstr_t *next=t_cache->next;
  58     t_cache->next=t_reserve;
  59     t_reserve=t_cache;
  60     t_cache=next;
  61   }
  62   t_cache->top=t_cache+1;
  63 }
  64
  65 //free entire list, starting at store
  66 void objstrDelete(objstr_t *store) {
  67   objstr_t *tmp;
  68   while (store != NULL) {
  69     tmp = store->next;
  70     free(store);
  71     store = tmp;
  72   }
  73   return;
  74 }
  75
  76 /* =================================================
  77  * transStart
  78  * This function initializes things required in the
  79  * transaction start
  80  * =================================================
  81  */
  82 void transStart() {
  83   //Transaction start is currently free...commit and aborting is not
  84 }
  85
  86 /* =======================================================
  87  * transCreateObj
  88  * This function creates objects in the transaction record
  89  * =======================================================
  90  */
  91 objheader_t *transCreateObj(void * ptr, unsigned int size) {
  92   objheader_t *tmp = mygcmalloc(ptr, (sizeof(objheader_t) + size));
  93   objheader_t *retval=&tmp[1];
  94   tmp->lock=RW_LOCK_BIAS;
  95   tmp->version = 1;
  96   STATUS(tmp)=NEW;
  97   // don't insert into table
  98   if (newobjs->offset<MAXOBJLIST) {
  99     newobjs->objs[newobjs->offset++]=retval;
 100   } else {
 101     struct objlist *tmp=malloc(sizeof(struct objlist));
 102     tmp->next=newobjs;
 103     tmp->objs[0]=retval;
 104     tmp->offset=1;
 105     newobjs=tmp;
 106   }
 107   return retval; //want space after object header
 108 }
 109
 110 /* This functions inserts randowm wait delays in the order of msec
 111  * Mostly used when transaction commits retry*/
 112 void randomdelay(int softaborted) {
 113   struct timespec req;
 114   struct timeval t;
 115
 116   gettimeofday(&t,NULL);
 117
 118   req.tv_sec = 0;
 119   req.tv_nsec = (long)((t.tv_usec)%(1<<softaborted))<<1; //1-11 microsec
 120   nanosleep(&req, NULL);
 121   return;
 122 }
 123
 124 /* ==============================================
 125  * objstrAlloc
 126  * - allocate space in an object store
 127  * ==============================================
 128  */
 129 void *objstrAlloc(unsigned int size) {
 130   void *tmp;
 131   int i=0;
 132   objstr_t *store=t_cache;
 133   if ((size&7)!=0) {
 134     size+=(8-(size&7));
 135   }
 136
 137   for(;i<2;i++) {
 138     if (OSFREE(store)>=size) {
 139       tmp=store->top;
 140       store->top +=size;
 141       return tmp;
 142     }
 143     if ((store=store->next)==NULL)
 144       break;
 145   }
 146
 147   {
 148     unsigned int newsize=size>DEFAULT_OBJ_STORE_SIZE?size:DEFAULT_OBJ_STORE_SIZE;
 149     objstr_t **otmp=&t_reserve;
 150     objstr_t *ptr;
 151     while((ptr=*otmp)!=NULL) {
 152       if (ptr->size>=newsize) {
 153         //remove from list
 154         *otmp=ptr->next;
 155         ptr->next=t_cache;
 156         t_cache=ptr;
 157         ptr->top=((char *)(&ptr[1]))+size;
 158         return &ptr[1];
 159       }
 160     }
 161
 162     objstr_t *os=(objstr_t *)calloc(1,(sizeof(objstr_t) + newsize));
 163     void *nptr=&os[1];
 164     os->next=t_cache;
 165     t_cache=os;
 166     os->size=newsize;
 167     os->top=((char *)nptr)+size;
 168     return nptr;
 169   }
 170 }
 171
 172 /* =============================================================
 173  * transRead
 174  * -finds the objects either in main heap
 175  * -copies the object into the transaction cache
 176  * =============================================================
 177  */
 178 __attribute__((pure)) void *transRead(void * oid) {
 179   objheader_t *tmp, *objheader;
 180   objheader_t *objcopy;
 181   int size;
 182
 183   //quick case for new objects
 184   if (((struct ___Object___ *)oid)->___objstatus___ & NEW)
 185     return oid;
 186
 187   /* Read from the main heap */
 188   //No lock for now
 189   objheader_t *header = (objheader_t *)(((char *)oid) - sizeof(objheader_t));
 190   GETSIZE(size, header);
 191   size += sizeof(objheader_t);
 192   objcopy = (objheader_t *) objstrAlloc(size);
 193   memcpy(objcopy, header, size);
 194   /* Insert into cache's lookup table */
 195   STATUS(objcopy)=0;
 196   t_chashInsert(oid, &objcopy[1]);
 197   return &objcopy[1];
 198 }
 199
 200 void freenewobjs() {
 201   struct objlist *ptr=newobjs;
 202   while(ptr->next!=NULL) {
 203     struct objlist *tmp=ptr->next;
 204     free(ptr);
 205     ptr=tmp;
 206   }
 207   ptr->offset=0;
 208   newobjs=ptr;
 209 }
 210
 211 /* ================================================================
 212  * transCommit
 213  * - This function initiates the transaction commit process
 214  * - goes through the transaction cache and decides
 215  * - a final response
 216  * ================================================================
 217  */
 218 int transCommit() {
 219 #ifdef TRANSSTATS
 220   int softaborted=0;
 221 #endif
 222   do {
 223     /* Look through all the objects in the transaction hash table */
 224     int finalResponse;
 225     if (c_numelements<(c_size>>3))
 226       finalResponse= alttraverseCache();
 227     else
 228       finalResponse= traverseCache();
 229     if(finalResponse == TRANS_ABORT) {
 230 #ifdef TRANSSTATS
 231       numTransAbort++;
 232       if (softaborted) {
 233         nSoftAbortAbort++;
 234       }
 235 #endif
 236       freenewobjs();
 237       objstrReset();
 238       t_chashreset();
 239       return TRANS_ABORT;
 240     }
 241     if(finalResponse == TRANS_COMMIT) {
 242 #ifdef TRANSSTATS
 243       numTransCommit++;
 244       if (softaborted) {
 245         nSoftAbortCommit++;
 246       }
 247 #endif
 248       freenewobjs();
 249       objstrReset();
 250       t_chashreset();
 251       return 0;
 252     }
 253     /* wait a random amount of time before retrying to commit transaction*/
 254     if(finalResponse == TRANS_SOFT_ABORT) {
 255 #ifdef TRANSSTATS
 256       nSoftAbort++;
 257       softaborted++;
 258 #endif
 259       if (softaborted>4) {
 260         //retry if to many soft aborts
 261         freenewobjs();
 262         objstrReset();
 263         t_chashreset();
 264         return TRANS_ABORT;
 265       }
 266       randomdelay(softaborted);
 267     } else {
 268       printf("Error: in %s() Unknown outcome", __func__);
 269       exit(-1);
 270     }
 271   } while (1);
 272 }
 273
 274 /* ==================================================
 275  * traverseCache
 276  * - goes through the transaction cache and
 277  * - decides if a transaction should commit or abort
 278  * ==================================================
 279  */
 280 int traverseCache() {
 281   /* Create info to keep track of objects that can be locked */
 282   int numoidrdlocked=0;
 283   int numoidwrlocked=0;
 284   void * rdlocked[200];
 285   void * wrlocked[200];
 286   int softabort=0;
 287   int i;
 288   void ** oidrdlocked;
 289   void ** oidwrlocked;
 290   if (c_numelements<200) {
 291     oidrdlocked=rdlocked;
 292     oidwrlocked=wrlocked;
 293   } else {
 294     int size=c_numelements*sizeof(void*);
 295     oidrdlocked=malloc(size);
 296     oidwrlocked=malloc(size);
 297   }
 298   chashlistnode_t *ptr = c_table;
 299   /* Represents number of bins in the chash table */
 300   unsigned int size = c_size;
 301   for(i = 0; i<size; i++) {
 302     chashlistnode_t *curr = &ptr[i];
 303     /* Inner loop to traverse the linked list of the cache lookupTable */
 304     while(curr != NULL) {
 305       //if the first bin in hash table is empty
 306       if(curr->key == NULL)
 307         break;
 308       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 309
 310       unsigned int version = headeraddr->version;
 311       objheader_t *header=(objheader_t *) (((char *)curr->key)-sizeof(objheader_t));
 312
 313       if(STATUS(headeraddr) & DIRTY) {
 314         /* Read from the main heap  and compare versions */
 315         if(write_trylock(&header->lock)) { //can aquire write lock
 316           if (version == header->version) {/* versions match */
 317             /* Keep track of objects locked */
 318             oidwrlocked[numoidwrlocked++] = OID(header);
 319           } else {
 320             oidwrlocked[numoidwrlocked++] = OID(header);
 321             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 322             return TRANS_ABORT;
 323           }
 324         } else { /* cannot aquire lock */
 325           if(version == header->version) {
 326             /* versions match */
 327             softabort=1;
 328           } else {
 329             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 330             return TRANS_ABORT;
 331           }
 332         }
 333       } else {
 334         /* Read from the main heap  and compare versions */
 335         if(read_trylock(&header->lock)) { //can further acquire read locks
 336           if(version == header->version) {/* versions match */
 337             oidrdlocked[numoidrdlocked++] = OID(header);
 338           } else {
 339             oidrdlocked[numoidrdlocked++] = OID(header);
 340             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 341             return TRANS_ABORT;
 342           }
 343         } else { /* cannot aquire lock */
 344           if(version == header->version) {
 345             softabort=1;
 346           } else {
 347             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 348             return TRANS_ABORT;
 349           }
 350         }
 351       }
 352
 353       curr = curr->next;
 354     }
 355   } //end of for
 356
 357   /* Decide the final response */
 358   if (softabort) {
 359     transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 360     return TRANS_SOFT_ABORT;
 361   } else {
 362     transCommitProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 363     return TRANS_COMMIT;
 364   }
 365 }
 366
 367 /* ==================================================
 368  * traverseCache
 369  * - goes through the transaction cache and
 370  * - decides if a transaction should commit or abort
 371  * ==================================================
 372  */
 373 int alttraverseCache() {
 374   /* Create info to keep track of objects that can be locked */
 375   int numoidrdlocked=0;
 376   int numoidwrlocked=0;
 377   void * rdlocked[200];
 378   void * wrlocked[200];
 379   int softabort=0;
 380   int i;
 381   void ** oidrdlocked;
 382   void ** oidwrlocked;
 383   if (c_numelements<200) {
 384     oidrdlocked=rdlocked;
 385     oidwrlocked=wrlocked;
 386   } else {
 387     int size=c_numelements*sizeof(void*);
 388     oidrdlocked=malloc(size);
 389     oidwrlocked=malloc(size);
 390   }
 391   chashlistnode_t *curr = c_list;
 392   /* Inner loop to traverse the linked list of the cache lookupTable */
 393   while(curr != NULL) {
 394     //if the first bin in hash table is empty
 395     objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 396
 397     unsigned int version = headeraddr->version;
 398     objheader_t *header=(objheader_t *) (((char *)curr->key)-sizeof(objheader_t));
 399
 400     if(STATUS(headeraddr) & DIRTY) {
 401       /* Read from the main heap  and compare versions */
 402       if(write_trylock(&header->lock)) { //can aquire write lock
 403         if (version == header->version) {/* versions match */
 404           /* Keep track of objects locked */
 405           oidwrlocked[numoidwrlocked++] = OID(header);
 406         } else {
 407           oidwrlocked[numoidwrlocked++] = OID(header);
 408           transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 409           return TRANS_ABORT;
 410         }
 411       } else { /* cannot aquire lock */
 412         if(version == header->version) {
 413           /* versions match */
 414           softabort=1;
 415         } else {
 416           transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 417           return TRANS_ABORT;
 418         }
 419       }
 420     } else {
 421       /* Read from the main heap  and compare versions */
 422       if(read_trylock(&header->lock)) { //can further aquire read locks
 423         if(version == header->version) {/* versions match */
 424           oidrdlocked[numoidrdlocked++] = OID(header);
 425         } else {
 426           oidrdlocked[numoidrdlocked++] = OID(header);
 427           transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 428           return TRANS_ABORT;
 429         }
 430       } else { /* cannot aquire lock */
 431         if(version == header->version) {
 432           softabort=1;
 433         } else {
 434           transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 435           return TRANS_ABORT;
 436         }
 437       }
 438     }
 439
 440     curr = curr->lnext;
 441   }
 442
 443   /* Decide the final response */
 444   if (softabort) {
 445     transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 446     return TRANS_SOFT_ABORT;
 447   } else {
 448     transCommitProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 449     return TRANS_COMMIT;
 450   }
 451 }
 452
 453
 454 /* ==================================
 455  * transAbortProcess
 456  *
 457  * =================================
 458  */
 459 int transAbortProcess(void **oidrdlocked, int *numoidrdlocked, void **oidwrlocked, int *numoidwrlocked) {
 460   int i;
 461   objheader_t *header;
 462   /* Release read locks */
 463   for(i=0; i< *numoidrdlocked; i++) {
 464     /* Read from the main heap */
 465     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 466     read_unlock(&header->lock);
 467   }
 468
 469   /* Release write locks */
 470   for(i=0; i< *numoidwrlocked; i++) {
 471     /* Read from the main heap */
 472     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 473     write_unlock(&header->lock);
 474   }
 475   if (c_numelements>=200) {
 476     free(oidrdlocked);
 477     free(oidwrlocked);
 478   }
 479 }
 480
 481 /* ==================================
 482  * transCommitProcess
 483  *
 484  * =================================
 485  */
 486 int transCommitProcess(void ** oidrdlocked, int *numoidrdlocked,
 487                     void ** oidwrlocked, int *numoidwrlocked) {
 488   objheader_t *header;
 489   void *ptrcreate;
 490   int i;
 491   struct objlist *ptr=newobjs;
 492   while(ptr!=NULL) {
 493     int max=ptr->offset;
 494     for(i=0;i<max;i++) {
 495       //clear the new flag
 496       ((struct ___Object___ *)ptr->objs[i])->___objstatus___=0;
 497     }
 498     ptr=ptr->next;
 499   }
 500
 501   /* Copy from transaction cache -> main object store */
 502   for (i = 0; i < *numoidwrlocked; i++) {
 503     /* Read from the main heap */
 504     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 505     int tmpsize;
 506     GETSIZE(tmpsize, header);
 507     struct ___Object___ *dst=(struct ___Object___*)oidwrlocked[i];
 508     struct ___Object___ *src=t_chashSearch(oidwrlocked[i]);
 509     dst->___cachedCode___=src->___cachedCode___;
 510     dst->___cachedHash___=src->___cachedHash___;
 511     memcpy(&dst[1], &src[1], tmpsize-sizeof(struct ___Object___));
 512     header->version += 1;
 513   }
 514
 515   /* Release read locks */
 516   for(i=0; i< *numoidrdlocked; i++) {
 517     /* Read from the main heap */
 518     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 519     read_unlock(&header->lock);
 520   }
 521
 522   /* Release write locks */
 523   for(i=0; i< *numoidwrlocked; i++) {
 524     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 525     write_unlock(&header->lock);
 526   }
 527   if (c_numelements>=200) {
 528     free(oidrdlocked);
 529     free(oidwrlocked);
 530   }
 531   return 0;
 532 }
 533