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 struct objlist * newobjs;
  18
  19 #ifdef TRANSSTATS
  20 int numTransCommit = 0;
  21 int numTransAbort = 0;
  22 int nSoftAbort = 0;
  23 int nSoftAbortCommit = 0;
  24 int nSoftAbortAbort = 0;
  25 #endif
  26
  27
  28 /* ==================================================
  29  * stmStartup
  30  * This function starts up the transaction runtime.
  31  * ==================================================
  32  */
  33 int stmStartup() {
  34   return 0;
  35 }
  36
  37 /* ======================================
  38  * objstrCreate
  39  * - create an object store of given size
  40  * ======================================
  41  */
  42 objstr_t *objstrCreate(unsigned int size) {
  43   objstr_t *tmp;
  44   if((tmp = calloc(1, (sizeof(objstr_t) + size))) == NULL) {
  45     printf("%s() Calloc error at line %d, %s\n", __func__, __LINE__, __FILE__);
  46     return NULL;
  47   }
  48   tmp->size = size;
  49   tmp->next = NULL;
  50   tmp->top = tmp + 1; //points to end of objstr_t structure!
  51   return tmp;
  52 }
  53
  54 //free entire list, starting at store
  55 void objstrDelete(objstr_t *store) {
  56   objstr_t *tmp;
  57   while (store != NULL) {
  58     tmp = store->next;
  59     free(store);
  60     store = tmp;
  61   }
  62   return;
  63 }
  64
  65 /* =================================================
  66  * transStart
  67  * This function initializes things required in the
  68  * transaction start
  69  * =================================================
  70  */
  71 void transStart() {
  72   t_cache = objstrCreate(1048576);
  73   t_chashCreate(CHASH_SIZE, CLOADFACTOR);
  74 }
  75
  76 /* =======================================================
  77  * transCreateObj
  78  * This function creates objects in the transaction record
  79  * =======================================================
  80  */
  81 objheader_t *transCreateObj(void * ptr, unsigned int size) {
  82   objheader_t *tmp = mygcmalloc(ptr, (sizeof(objheader_t) + size));
  83   objheader_t *retval=&tmp[1];
  84   tmp->lock=RW_LOCK_BIAS;
  85   tmp->version = 1;
  86   STATUS(tmp)=NEW;
  87   // don't insert into table
  88   if (newobjs->offset<MAXOBJLIST) {
  89     newobjs->objs[newobjs->offset++]=retval;
  90   } else {
  91     struct objlist *tmp=malloc(sizeof(struct objlist));
  92     tmp->next=newobjs;
  93     tmp->objs[0]=retval;
  94     tmp->offset=1;
  95     newobjs=tmp;
  96   }
  97   return retval; //want space after object header
  98 }
  99
 100 /* This functions inserts randowm wait delays in the order of msec
 101  * Mostly used when transaction commits retry*/
 102 void randomdelay() {
 103   struct timespec req;
 104   time_t t;
 105
 106   t = time(NULL);
 107   req.tv_sec = 0;
 108   req.tv_nsec = (long)(t%4); //1-11 microsec
 109   nanosleep(&req, NULL);
 110   return;
 111 }
 112
 113 /* ==============================================
 114  * objstrAlloc
 115  * - allocate space in an object store
 116  * ==============================================
 117  */
 118 void *objstrAlloc(objstr_t **osptr, unsigned int size) {
 119   void *tmp;
 120   int i=0;
 121   objstr_t *store=*osptr;
 122   if ((size&7)!=0) {
 123     size+=(8-(size&7));
 124   }
 125
 126   for(;i<3;i++) {
 127     if (OSFREE(store)>=size) {
 128       tmp=store->top;
 129       store->top +=size;
 130       return tmp;
 131     }
 132     if ((store=store->next)==NULL)
 133       break;
 134   }
 135
 136   {
 137     unsigned int newsize=size>DEFAULT_OBJ_STORE_SIZE?size:DEFAULT_OBJ_STORE_SIZE;
 138     objstr_t *os=(objstr_t *)calloc(1,(sizeof(objstr_t) + newsize));
 139     void *ptr=&os[1];
 140     os->next=*osptr;
 141     (*osptr)=os;
 142     os->size=newsize;
 143     os->top=((char *)ptr)+size;
 144     return ptr;
 145   }
 146 }
 147
 148 /* =============================================================
 149  * transRead
 150  * -finds the objects either in main heap
 151  * -copies the object into the transaction cache
 152  * =============================================================
 153  */
 154 __attribute__((pure)) void *transRead(void * oid) {
 155   objheader_t *tmp, *objheader;
 156   objheader_t *objcopy;
 157   int size;
 158
 159   //quick case for new objects
 160   if (((struct ___Object___ *)oid)->___objstatus___ & NEW)
 161     return oid;
 162
 163   /* Read from the main heap */
 164   //No lock for now
 165   objheader_t *header = (objheader_t *)(((char *)oid) - sizeof(objheader_t));
 166   GETSIZE(size, header);
 167   size += sizeof(objheader_t);
 168   objcopy = (objheader_t *) objstrAlloc(&t_cache, size);
 169   memcpy(objcopy, header, size);
 170   /* Insert into cache's lookup table */
 171   STATUS(objcopy)=0;
 172   t_chashInsert(oid, &objcopy[1]);
 173   return &objcopy[1];
 174 }
 175
 176 void freenewobjs() {
 177   struct objlist *ptr=newobjs;
 178   while(ptr->next!=NULL) {
 179     struct objlist *tmp=ptr->next;
 180     free(ptr);
 181     ptr=tmp;
 182   }
 183   ptr->offset=0;
 184   newobjs=ptr;
 185 }
 186
 187 /* ================================================================
 188  * transCommit
 189  * - This function initiates the transaction commit process
 190  * - goes through the transaction cache and decides
 191  * - a final response
 192  * ================================================================
 193  */
 194 int transCommit() {
 195 #ifdef TRANSSTATS
 196   int softaborted=0;
 197 #endif
 198   do {
 199     /* Look through all the objects in the transaction hash table */
 200     int finalResponse = traverseCache();
 201     if(finalResponse == TRANS_ABORT) {
 202 #ifdef TRANSSTATS
 203       numTransAbort++;
 204       if (softaborted) {
 205         nSoftAbortAbort++;
 206       }
 207 #endif
 208       freenewobjs();
 209       objstrDelete(t_cache);
 210       t_cache=NULL;
 211       t_chashDelete();
 212       return TRANS_ABORT;
 213     }
 214     if(finalResponse == TRANS_COMMIT) {
 215 #ifdef TRANSSTATS
 216       numTransCommit++;
 217       if (softaborted) {
 218         nSoftAbortCommit++;
 219       }
 220 #endif
 221       freenewobjs();
 222       objstrDelete(t_cache);
 223       t_cache=NULL;
 224       t_chashDelete();
 225       return 0;
 226     }
 227     /* wait a random amount of time before retrying to commit transaction*/
 228     if(finalResponse == TRANS_SOFT_ABORT) {
 229 #ifdef TRANSSTATS
 230       nSoftAbort++;
 231       softaborted=1;
 232 #endif
 233       randomdelay();
 234     } else {
 235       printf("Error: in %s() Unknown outcome", __func__);
 236       exit(-1);
 237     }
 238   } while (1);
 239 }
 240
 241 /* ==================================================
 242  * traverseCache
 243  * - goes through the transaction cache and
 244  * - decides if a transaction should commit or abort
 245  * ==================================================
 246  */
 247 int traverseCache() {
 248   /* Create info to keep track of objects that can be locked */
 249   int numoidrdlocked=0;
 250   int numoidwrlocked=0;
 251   void * oidrdlocked[c_numelements];
 252   void * oidwrlocked[c_numelements];
 253   int softabort=0;
 254   int i;
 255   chashlistnode_t *ptr = c_table;
 256   /* Represents number of bins in the chash table */
 257   unsigned int size = c_size;
 258   for(i = 0; i<size; i++) {
 259     chashlistnode_t *curr = &ptr[i];
 260     /* Inner loop to traverse the linked list of the cache lookupTable */
 261     while(curr != NULL) {
 262       //if the first bin in hash table is empty
 263       if(curr->key == NULL)
 264         break;
 265       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 266
 267       unsigned int version = headeraddr->version;
 268       objheader_t *header=(objheader_t *) (((char *)curr->key)-sizeof(objheader_t));
 269
 270       if(STATUS(headeraddr) & DIRTY) {
 271         /* Read from the main heap  and compare versions */
 272         if(write_trylock(&header->lock)) { //can aquire write lock
 273           if (version == header->version) {/* versions match */
 274             /* Keep track of objects locked */
 275             oidwrlocked[numoidwrlocked++] = OID(header);
 276           } else {
 277             oidwrlocked[numoidwrlocked++] = OID(header);
 278             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 279             return TRANS_ABORT;
 280           }
 281         } else { /* cannot aquire lock */
 282           if(version == header->version) /* versions match */
 283             softabort=1;
 284           else {
 285             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 286             return TRANS_ABORT;
 287           }
 288         }
 289       } else {
 290         /* Read from the main heap  and compare versions */
 291         if(read_trylock(&header->lock)) { //can further aquire read locks
 292           if(version == header->version) {/* versions match */
 293             oidrdlocked[numoidrdlocked++] = OID(header);
 294           } else {
 295             oidrdlocked[numoidrdlocked++] = OID(header);
 296             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 297             return TRANS_ABORT;
 298           }
 299         } else { /* cannot aquire lock */
 300           if(version == header->version)
 301             softabort=1;
 302           else {
 303             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 304             return TRANS_ABORT;
 305           }
 306         }
 307       }
 308
 309       curr = curr->next;
 310     }
 311   } //end of for
 312
 313   /* Decide the final response */
 314   if (softabort) {
 315     transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 316     return TRANS_SOFT_ABORT;
 317   } else {
 318     transCommitProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 319     return TRANS_COMMIT;
 320   }
 321 }
 322
 323
 324 /* ==================================
 325  * transAbortProcess
 326  *
 327  * =================================
 328  */
 329 int transAbortProcess(void **oidrdlocked, int *numoidrdlocked, void **oidwrlocked, int *numoidwrlocked) {
 330   int i;
 331   objheader_t *header;
 332   /* Release read locks */
 333   for(i=0; i< *numoidrdlocked; i++) {
 334     /* Read from the main heap */
 335     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 336     read_unlock(&header->lock);
 337   }
 338
 339   /* Release write locks */
 340   for(i=0; i< *numoidwrlocked; i++) {
 341     /* Read from the main heap */
 342     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 343     write_unlock(&header->lock);
 344   }
 345 }
 346
 347 /* ==================================
 348  * transCommitProcess
 349  *
 350  * =================================
 351  */
 352 int transCommitProcess(void ** oidrdlocked, int *numoidrdlocked,
 353                     void ** oidwrlocked, int *numoidwrlocked) {
 354   objheader_t *header;
 355   void *ptrcreate;
 356   int i;
 357   struct objlist *ptr=newobjs;
 358   while(ptr!=NULL) {
 359     int max=ptr->offset;
 360     for(i=0;i<max;i++) {
 361       //clear the new flag
 362       ((struct ___Object___ *)ptr->objs[i])->___objstatus___=0;
 363     }
 364     ptr=ptr->next;
 365   }
 366
 367   /* Copy from transaction cache -> main object store */
 368   for (i = 0; i < *numoidwrlocked; i++) {
 369     /* Read from the main heap */
 370     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 371     int tmpsize;
 372     GETSIZE(tmpsize, header);
 373     struct ___Object___ *dst=(struct ___Object___*)oidwrlocked[i];
 374     struct ___Object___ *src=t_chashSearch(oidwrlocked[i]);
 375     dst->___cachedCode___=src->___cachedCode___;
 376     dst->___cachedHash___=src->___cachedHash___;
 377     memcpy(&dst[1], &src[1], tmpsize-sizeof(struct ___Object___));
 378     header->version += 1;
 379   }
 380
 381   /* Release read locks */
 382   for(i=0; i< *numoidrdlocked; i++) {
 383     /* Read from the main heap */
 384     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 385     read_unlock(&header->lock);
 386   }
 387
 388   /* Release write locks */
 389   for(i=0; i< *numoidwrlocked; i++) {
 390     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 391     write_unlock(&header->lock);
 392   }
 393
 394   return 0;
 395 }
 396