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=store;
 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   unsigned int machinenumber;
 156   objheader_t *tmp, *objheader;
 157   objheader_t *objcopy;
 158   int size;
 159
 160   //quick case for new objects
 161   if (((struct ___Object___ *)oid)->___objstatus___ & NEW)
 162     return oid;
 163
 164   /* Read from the main heap */
 165   //No lock for now
 166   objheader_t *header = (objheader_t *)(((char *)oid) - sizeof(objheader_t));
 167   GETSIZE(size, header);
 168   size += sizeof(objheader_t);
 169   objcopy = (objheader_t *) objstrAlloc(&t_cache, size);
 170   memcpy(objcopy, header, size);
 171   /* Insert into cache's lookup table */
 172   STATUS(objcopy)=0;
 173   t_chashInsert((unsigned int)oid, &objcopy[1]);
 174   return &objcopy[1];
 175 }
 176
 177 void freenewobjs() {
 178   struct objlist *ptr=newobjs;
 179   while(ptr->next!=NULL) {
 180     struct objlist *tmp=ptr->next;
 181     free(ptr);
 182     ptr=tmp;
 183   }
 184   ptr->offset=0;
 185   newobjs=ptr;
 186 }
 187
 188 /* ================================================================
 189  * transCommit
 190  * - This function initiates the transaction commit process
 191  * - goes through the transaction cache and decides
 192  * - a final response
 193  * ================================================================
 194  */
 195 int transCommit() {
 196 #ifdef TRANSSTATS
 197   int softaborted=0;
 198 #endif
 199   do {
 200     /* Look through all the objects in the transaction hash table */
 201     int finalResponse = traverseCache();
 202     if(finalResponse == TRANS_ABORT) {
 203 #ifdef TRANSSTATS
 204       numTransAbort++;
 205       if (softaborted) {
 206         nSoftAbortAbort++;
 207       }
 208 #endif
 209       freenewobjs();
 210       objstrDelete(t_cache);
 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_chashDelete();
 224       return 0;
 225     }
 226     /* wait a random amount of time before retrying to commit transaction*/
 227     if(finalResponse == TRANS_SOFT_ABORT) {
 228 #ifdef TRANSSTATS
 229       nSoftAbort++;
 230       softaborted=1;
 231 #endif
 232       randomdelay();
 233     } else {
 234       printf("Error: in %s() Unknown outcome", __func__);
 235       exit(-1);
 236     }
 237   } while (1);
 238 }
 239
 240 /* ==================================================
 241  * traverseCache
 242  * - goes through the transaction cache and
 243  * - decides if a transaction should commit or abort
 244  * ==================================================
 245  */
 246 int traverseCache() {
 247   /* Create info to keep track of objects that can be locked */
 248   int numoidrdlocked=0;
 249   int numoidwrlocked=0;
 250   unsigned int oidrdlocked[c_numelements];
 251   unsigned int oidwrlocked[c_numelements];
 252   int softabort=0;
 253   int i;
 254   chashlistnode_t *ptr = c_table;
 255   /* Represents number of bins in the chash table */
 256   unsigned int size = c_size;
 257   for(i = 0; i<size; i++) {
 258     chashlistnode_t *curr = &ptr[i];
 259     /* Inner loop to traverse the linked list of the cache lookupTable */
 260     while(curr != NULL) {
 261       //if the first bin in hash table is empty
 262       if(curr->key == 0)
 263         break;
 264       objheader_t * headeraddr=&((objheader_t *) curr->val)[-1];
 265
 266       unsigned int version = headeraddr->version;
 267       objheader_t *header=(objheader_t *) (((char *)curr->key)-sizeof(objheader_t));
 268
 269       if(STATUS(headeraddr) & DIRTY) {
 270         /* Read from the main heap  and compare versions */
 271         if(write_trylock(&header->lock)) { //can aquire write lock
 272           if (version == header->version) {/* versions match */
 273             /* Keep track of objects locked */
 274             oidwrlocked[numoidwrlocked++] = OID(header);
 275           } else {
 276             oidwrlocked[numoidwrlocked++] = OID(header);
 277             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 278             return TRANS_ABORT;
 279           }
 280         } else { /* cannot aquire lock */
 281           if(version == header->version) /* versions match */
 282             softabort=1;
 283           else {
 284             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 285             return TRANS_ABORT;
 286           }
 287         }
 288       } else {
 289         /* Read from the main heap  and compare versions */
 290         if(read_trylock(&header->lock)) { //can further aquire read locks
 291           if(version == header->version) {/* versions match */
 292             oidrdlocked[numoidrdlocked++] = OID(header);
 293           } else {
 294             oidrdlocked[numoidrdlocked++] = OID(header);
 295             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 296             return TRANS_ABORT;
 297           }
 298         } else { /* cannot aquire lock */
 299           if(version == header->version)
 300             softabort=1;
 301           else {
 302             transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 303             return TRANS_ABORT;
 304           }
 305         }
 306       }
 307
 308       curr = curr->next;
 309     }
 310   } //end of for
 311
 312   /* Decide the final response */
 313   if (softabort) {
 314     transAbortProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 315     return TRANS_SOFT_ABORT;
 316   } else {
 317     transCommitProcess(oidrdlocked, &numoidrdlocked, oidwrlocked, &numoidwrlocked);
 318     return TRANS_COMMIT;
 319   }
 320 }
 321
 322 /* ===========================================================================
 323  * decideResponse
 324  * - increments counters that keep track of objects read, modified or locked
 325  * - updates the oids locked and oids newly created
 326  * ===========================================================================
 327  */
 328
 329
 330 /* ==================================
 331  * transAbortProcess
 332  *
 333  * =================================
 334  */
 335 int transAbortProcess(unsigned int *oidrdlocked, int *numoidrdlocked, unsigned int *oidwrlocked, int *numoidwrlocked) {
 336   int i;
 337   objheader_t *header;
 338   /* Release read locks */
 339   for(i=0; i< *numoidrdlocked; i++) {
 340     /* Read from the main heap */
 341     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 342     read_unlock(&header->lock);
 343   }
 344
 345   /* Release write locks */
 346   for(i=0; i< *numoidwrlocked; i++) {
 347     /* Read from the main heap */
 348     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 349     write_unlock(&header->lock);
 350   }
 351 }
 352
 353 /* ==================================
 354  * transCommitProcess
 355  *
 356  * =================================
 357  */
 358 int transCommitProcess(unsigned int *oidrdlocked, int *numoidrdlocked,
 359                     unsigned int *oidwrlocked, int *numoidwrlocked) {
 360   objheader_t *header;
 361   void *ptrcreate;
 362   int i;
 363   struct objlist *ptr=newobjs;
 364   while(ptr!=NULL) {
 365     int max=ptr->offset;
 366     for(i=0;i<max;i++) {
 367       //clear the new flag
 368       ((struct ___Object___ *)ptr->objs[i])->___objstatus___=0;
 369     }
 370     ptr=ptr->next;
 371   }
 372
 373   /* Copy from transaction cache -> main object store */
 374   for (i = 0; i < *numoidwrlocked; i++) {
 375     /* Read from the main heap */
 376     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 377     int tmpsize;
 378     GETSIZE(tmpsize, header);
 379     struct ___Object___ *dst=(struct ___Object___*)oidwrlocked[i];
 380     struct ___Object___ *src=t_chashSearch(oidwrlocked[i]);
 381     dst->___cachedCode___=src->___cachedCode___;
 382     dst->___cachedHash___=src->___cachedHash___;
 383     memcpy(&dst[1], &src[1], tmpsize-sizeof(struct ___Object___));
 384     header->version += 1;
 385   }
 386
 387   /* Release read locks */
 388   for(i=0; i< *numoidrdlocked; i++) {
 389     /* Read from the main heap */
 390     header = (objheader_t *)(((char *)(oidrdlocked[i])) - sizeof(objheader_t));
 391     read_unlock(&header->lock);
 392   }
 393
 394   /* Release write locks */
 395   for(i=0; i< *numoidwrlocked; i++) {
 396     header = (objheader_t *)(((char *)(oidwrlocked[i])) - sizeof(objheader_t));
 397     write_unlock(&header->lock);
 398   }
 399
 400   return 0;
 401 }
 402