Robust/src/Runtime/runtime.c

   1 #include "runtime.h"
   2 #include "structdefs.h"
   3 #include <string.h>
   4 #include <signal.h>
   5 #include "mem.h"
   6 #include<fcntl.h>
   7 #include<sys/types.h>
   8 #include<sys/mman.h>
   9 #include<errno.h>
  10 #include<signal.h>
  11 #include<stdio.h>
  12 #include "option.h"
  13
  14 extern int classsize[];
  15 jmp_buf error_handler;
  16 int instructioncount;
  17
  18 char *options;
  19 int injectfailures=0;
  20 float failurechance=0;
  21 int debugtask=0;
  22 int injectinstructionfailures;
  23 int failurecount;
  24 float instfailurechance=0;
  25 int numfailures;
  26 int instaccum=0;
  27 #ifdef DMALLOC
  28 #include "dmalloc.h"
  29 #endif
  30
  31
  32 #ifdef TASK
  33 #include "checkpoint.h"
  34 #include "Queue.h"
  35 #include "SimpleHash.h"
  36 #include "GenericHashtable.h"
  37 #include <sys/select.h>
  38
  39 #ifdef CONSCHECK
  40 #include "instrument.h"
  41 #endif
  42
  43 struct genhashtable * activetasks;
  44 struct parameterwrapper * objectqueues[NUMCLASSES];
  45 struct genhashtable * failedtasks;
  46 struct taskparamdescriptor * currtpd;
  47 struct RuntimeHash * forward;
  48 struct RuntimeHash * reverse;
  49
  50
  51 int main(int argc, char **argv) {
  52 #ifdef BOEHM_GC
  53   GC_init(); // Initialize the garbage collector
  54 #endif
  55 #ifdef CONSCHECK
  56   initializemmap();
  57 #endif
  58   processOptions();
  59   initializeexithandler();
  60   /* Create table for failed tasks */
  61   failedtasks=genallocatehashtable((unsigned int (*)(void *)) &hashCodetpd,
  62                                    (int (*)(void *,void *)) &comparetpd);
  63   /* Create queue of active tasks */
  64   activetasks=genallocatehashtable((unsigned int (*)(void *)) &hashCodetpd,
  65                                    (int (*)(void *,void *)) &comparetpd);
  66
  67
  68   /* Process task information */
  69   processtasks();
  70
  71   /* Create startup object */
  72   createstartupobject(argc, argv);
  73
  74   /* Start executing the tasks */
  75   executetasks();
  76 }
  77
  78 void createstartupobject(int argc, char ** argv) {
  79   int i;
  80
  81   /* Allocate startup object     */
  82 #ifdef PRECISE_GC
  83   struct ___StartupObject___ *startupobject=(struct ___StartupObject___*) allocate_new(NULL, STARTUPTYPE);
  84   struct ArrayObject * stringarray=allocate_newarray(NULL, STRINGARRAYTYPE, argc-1);
  85 #else
  86   struct ___StartupObject___ *startupobject=(struct ___StartupObject___*) allocate_new(STARTUPTYPE);
  87   struct ArrayObject * stringarray=allocate_newarray(STRINGARRAYTYPE, argc-1);
  88 #endif
  89   /* Build array of strings */
  90   startupobject->___parameters___=stringarray;
  91   for(i=1;i<argc;i++) {
  92     int length=strlen(argv[i]);
  93 #ifdef PRECISE_GC
  94     struct ___String___ *newstring=NewString(NULL, argv[i],length);
  95 #else
  96     struct ___String___ *newstring=NewString(argv[i],length);
  97 #endif
  98     ((void **)(((char *)& stringarray->___length___)+sizeof(int)))[i-1]=newstring;
  99   }
 100
 101   /* Set initialized flag for startup object */
 102   flagorand(startupobject,1,0xFFFFFFFF);
 103 }
 104
 105 int hashCodetpd(struct taskparamdescriptor *ftd) {
 106   int hash=(int)ftd->task;
 107   int i;
 108   for(i=0;i<ftd->numParameters;i++) {
 109     hash^=(int)ftd->parameterArray[i];
 110   }
 111   return hash;
 112 }
 113
 114 int comparetpd(struct taskparamdescriptor *ftd1, struct taskparamdescriptor *ftd2) {
 115   int i;
 116   if (ftd1->task!=ftd2->task)
 117     return 0;
 118   for(i=0;i<ftd1->numParameters;i++)
 119     if (ftd1->parameterArray[i]!=ftd2->parameterArray[i])
 120       return 0;
 121   return 1;
 122 }
 123
 124
 125 /* This function sets a tag. */
 126 #ifdef PRECISE_GC
 127 void tagset(void *ptr, struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 128 #else
 129 void tagset(struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 130 #endif
 131   struct ___Object___ * tagptr=obj->___tags___;
 132   if (tagptr==NULL) {
 133     obj->___tags___=(struct ___Object___ *)tagd;
 134   } else {
 135     /* Have to check if it is already set */
 136     if (tagptr->type==TAGTYPE) {
 137       struct ___TagDescriptor___ * td=(struct ___TagDescriptor___ *) tagptr;
 138       if (td==tagd)
 139         return;
 140 #ifdef PRECISE_GC
 141       int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 142       struct ArrayObject * ao=allocate_newarray(&ptrarray,TAGARRAYTYPE,TAGARRAYINTERVAL);
 143       obj=(struct ___Object___ *)ptrarray[2];
 144       tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 145       td=(struct ___TagDescriptor___ *) obj->___tags___;
 146 #else
 147       struct ArrayObject * ao=allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL);
 148 #endif
 149       ARRAYSET(ao, struct ___TagDescriptor___ *, 0, td);
 150       ARRAYSET(ao, struct ___TagDescriptor___ *, 1, tagd);
 151       obj->___tags___=(struct ___Object___ *) ao;
 152       ao->___cachedCode___=2;
 153     } else {
 154       /* Array Case */
 155       int i;
 156       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 157       for(i=0;i<ao->___cachedCode___;i++) {
 158         struct ___TagDescriptor___ * td=ARRAYGET(ao, struct ___TagDescriptor___*, i);
 159         if (td==tagd)
 160           return;
 161       }
 162       if (ao->___cachedCode___<ao->___length___) {
 163         ARRAYSET(ao, struct ___TagDescriptor___ *, ao->___cachedCode___, tagd);
 164         ao->___cachedCode___++;
 165       } else {
 166 #ifdef PRECISE_GC
 167         int ptrarray[]={2,(int) ptr, (int) obj, (int) tagd};
 168         struct ArrayObject * aonew=allocate_newarray(&ptrarray,TAGARRAYTYPE,TAGARRAYINTERVAL+ao->___length___);
 169         obj=(struct ___Object___ *)ptrarray[2];
 170         tagd=(struct ___TagDescriptor___ *) ptrarray[3];
 171         ao=(struct ArrayObject *)obj->___tags___;
 172 #else
 173         struct ArrayObject * aonew=allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL+ao->___length___);
 174 #endif
 175         aonew->___cachedCode___=ao->___length___+1;
 176         for(i=0;i<ao->___length___;i++) {
 177           ARRAYSET(aonew, struct ___TagDescriptor___*, i, ARRAYGET(ao, struct ___TagDescriptor___*, i));
 178         }
 179         ARRAYSET(aonew, struct ___TagDescriptor___ *, ao->___length___, tagd);
 180       }
 181     }
 182   }
 183
 184   {
 185     struct ___Object___ * tagset=tagd->flagptr;
 186
 187     if(tagset==NULL) {
 188       tagd->flagptr=obj;
 189     } else if (tagset->type!=OBJECTARRAYTYPE) {
 190 #ifdef PRECISE_GC
 191       int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 192       struct ArrayObject * ao=allocate_newarray(&ptrarray,OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
 193       obj=(struct ___Object___ *)ptrarray[2];
 194       tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 195 #else
 196       struct ArrayObject * ao=allocate_newarray(OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
 197 #endif
 198       ARRAYSET(ao, struct ___Object___ *, 0, tagd->flagptr);
 199       ARRAYSET(ao, struct ___Object___ *, 1, obj);
 200       ao->___cachedCode___=2;
 201       tagd->flagptr=(struct ___Object___ *)ao;
 202     } else {
 203       struct ArrayObject *ao=(struct ArrayObject *) tagset;
 204       if (ao->___cachedCode___<ao->___length___) {
 205         ARRAYSET(ao, struct ___Object___*, ao->___cachedCode___++, obj);
 206       } else {
 207         int i;
 208 #ifdef PRECISE_GC
 209         int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 210         struct ArrayObject * aonew=allocate_newarray(&ptrarray,OBJECTARRAYTYPE,OBJECTARRAYINTERVAL+ao->___length___);
 211         obj=(struct ___Object___ *)ptrarray[2];
 212         tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 213         ao=(struct ArrayObject *)tagd->flagptr;
 214 #else
 215         struct ArrayObject * aonew=allocate_newarray(OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
 216 #endif
 217         aonew->___cachedCode___=ao->___cachedCode___+1;
 218         for(i=0;i<ao->___length___;i++) {
 219           ARRAYSET(aonew, struct ___Object___*, i, ARRAYGET(ao, struct ___Object___*, i));
 220         }
 221         ARRAYSET(aonew, struct ___Object___ *, ao->___cachedCode___, obj);
 222         tagd->flagptr=(struct ___Object___ *) ao;
 223       }
 224     }
 225   }
 226 }
 227
 228 /* This function clears a tag. */
 229 #ifdef PRECISE_GC
 230 void tagclear(void *ptr, struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 231 #else
 232 void tagclear(struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 233 #endif
 234   /* We'll assume that tag is alway there.
 235      Need to statically check for this of course. */
 236   struct ___Object___ * tagptr=obj->___tags___;
 237
 238   if (tagptr->type==TAGTYPE) {
 239     if ((struct ___TagDescriptor___ *)tagptr==tagd)
 240       obj->___tags___=NULL;
 241     else
 242       printf("ERROR 1 in tagclear\n");
 243   } else {
 244     struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 245     int i;
 246     for(i=0;i<ao->___cachedCode___;i++) {
 247       struct ___TagDescriptor___ * td=ARRAYGET(ao, struct ___TagDescriptor___ *, i);
 248       if (td==tagd) {
 249         ao->___cachedCode___--;
 250         if (i<ao->___cachedCode___)
 251           ARRAYSET(ao, struct ___TagDescriptor___ *, i, ARRAYGET(ao, struct ___TagDescriptor___ *, ao->___cachedCode___));
 252         ARRAYSET(ao, struct ___TagDescriptor___ *, ao->___cachedCode___, NULL);
 253         if (ao->___cachedCode___==0)
 254           obj->___tags___=NULL;
 255         goto PROCESSCLEAR;
 256       }
 257     }
 258     printf("ERROR 2 in tagclear\n");
 259   }
 260  PROCESSCLEAR:
 261   {
 262     struct ___Object___ *tagset=tagd->flagptr;
 263     if (tagset->type!=OBJECTARRAYTYPE) {
 264       if (tagset==obj)
 265         tagd->flagptr=NULL;
 266       else
 267         printf("ERROR 3 in tagclear\n");
 268     } else {
 269       struct ArrayObject *ao=(struct ArrayObject *) tagset;
 270       int i;
 271       for(i=0;i<ao->___cachedCode___;i++) {
 272         struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, i);
 273         if (tobj==obj) {
 274           ao->___cachedCode___--;
 275           if (i<ao->___cachedCode___)
 276             ARRAYSET(ao, struct ___Object___ *, i, ARRAYGET(ao, struct ___Object___ *, ao->___cachedCode___));
 277           ARRAYSET(ao, struct ___Object___ *, ao->___cachedCode___, NULL);
 278           if (ao->___cachedCode___==0)
 279             tagd->flagptr=NULL;
 280           goto ENDCLEAR;
 281         }
 282       }
 283       printf("ERROR 4 in tagclear\n");
 284     }
 285   }
 286  ENDCLEAR:
 287   return;
 288
 289 }
 290
 291 /* This function allocates a new tag. */
 292 #ifdef PRECISE_GC
 293 struct ___TagDescriptor___ * allocate_tag(void *ptr, int index) {
 294   struct ___TagDescriptor___ * v=(struct ___TagDescriptor___ *) mygcmalloc((struct garbagelist *) ptr, classsize[TAGTYPE]);
 295 #else
 296 struct ___TagDescriptor___ * allocate_tag(int index) {
 297   struct ___TagDescriptor___ * v=FREEMALLOC(classsize[TAGTYPE]);
 298 #endif
 299   v->type=TAGTYPE;
 300   v->flag=index;
 301   return v;
 302 }
 303
 304
 305
 306 /* This function updates the flag for object ptr.  It or's the flag
 307    with the or mask and and's it with the andmask. */
 308
 309 void flagbody(struct ___Object___ *ptr, int flag);
 310
 311 void flagorand(void * ptr, int ormask, int andmask) {
 312   int oldflag=((int *)ptr)[1];
 313   int flag=ormask|oldflag;
 314   flag&=andmask;
 315   // Not sure why this was necessary
 316   //  if (flag==oldflag) /* Don't do anything */
 317   //  return;
 318   //else
 319   flagbody(ptr, flag);
 320 }
 321
 322 void intflagorand(void * ptr, int ormask, int andmask) {
 323   int oldflag=((int *)ptr)[1];
 324   int flag=ormask|oldflag;
 325   flag&=andmask;
 326   if (flag==oldflag) /* Don't do anything */
 327     return;
 328   else flagbody(ptr, flag);
 329 }
 330
 331 void flagorandinit(void * ptr, int ormask, int andmask) {
 332   int oldflag=((int *)ptr)[1];
 333   int flag=ormask|oldflag;
 334   flag&=andmask;
 335   flagbody(ptr,flag);
 336 }
 337
 338 void flagbody(struct ___Object___ *ptr, int flag) {
 339   struct parameterwrapper *flagptr=(struct parameterwrapper *)ptr->flagptr;
 340   ptr->flag=flag;
 341
 342   /*Remove object from all queues */
 343   while(flagptr!=NULL) {
 344     struct parameterwrapper *next;
 345     struct ___Object___ * tag=ptr->___tags___;
 346     RuntimeHashget(flagptr->objectset, (int) ptr, (int *) &next);
 347     RuntimeHashremove(flagptr->objectset, (int)ptr, (int) next);
 348     flagptr=next;
 349   }
 350
 351   {
 352     struct QueueItem *tmpptr;
 353     struct parameterwrapper * parameter=objectqueues[ptr->type];
 354     int i;
 355     struct parameterwrapper * prevptr=NULL;
 356     struct ___Object___ *tagptr=ptr->___tags___;
 357
 358     /* Outer loop iterates through all parameter queues an object of
 359        this type could be in.  */
 360
 361     while(parameter!=NULL) {
 362       /* Check tags */
 363       if (parameter->numbertags>0) {
 364         if (tagptr==NULL)
 365           goto nextloop;
 366         else if(tagptr->type==TAGTYPE) {
 367           struct ___TagDescriptor___ * tag=(struct ___TagDescriptor___*) tagptr;
 368           for(i=0;i<parameter->numbertags;i++) {
 369             //slotid is parameter->tagarray[2*i];
 370             int tagid=parameter->tagarray[2*i+1];
 371             if (tagid!=tagptr->flag)
 372               goto nextloop; /*We don't have this tag */
 373           }
 374         } else {
 375           struct ArrayObject * ao=(struct ArrayObject *) tagptr;
 376           for(i=0;i<parameter->numbertags;i++) {
 377             //slotid is parameter->tagarray[2*i];
 378             int tagid=parameter->tagarray[2*i+1];
 379             int j;
 380             for(j=0;j<ao->___cachedCode___;j++) {
 381               if (tagid==ARRAYGET(ao, struct ___TagDescriptor___*, i)->flag)
 382                 goto foundtag;
 383             }
 384             goto nextloop;
 385           foundtag:
 386             ;
 387           }
 388         }
 389       }
 390
 391       /* Check flags */
 392       for(i=0;i<parameter->numberofterms;i++) {
 393         int andmask=parameter->intarray[i*2];
 394         int checkmask=parameter->intarray[i*2+1];
 395         if ((flag&andmask)==checkmask) {
 396           enqueuetasks(parameter, prevptr, ptr);
 397           prevptr=parameter;
 398           break;
 399         }
 400       }
 401     nextloop:
 402       parameter=parameter->next;
 403     }
 404     ptr->flagptr=prevptr;
 405   }
 406 }
 407
 408 void enqueuetasks(struct parameterwrapper *parameter, struct parameterwrapper *prevptr, struct ___Object___ *ptr) {
 409   void * taskpointerarray[MAXTASKPARAMS];
 410   int j;
 411   int numparams=parameter->task->numParameters;
 412   int numiterators=parameter->task->numTotal-1;
 413
 414   struct taskdescriptor * task=parameter->task;
 415
 416   RuntimeHashadd(parameter->objectset, (int) ptr, (int) prevptr);
 417
 418   /* Add enqueued object to parameter vector */
 419   taskpointerarray[parameter->slot]=ptr;
 420
 421   /* Reset iterators */
 422   for(j=0;j<numiterators;j++) {
 423     toiReset(&parameter->iterators[j]);
 424   }
 425
 426   /* Find initial state */
 427   for(j=0;j<numiterators;j++) {
 428   backtrackinit:
 429     if(toiHasNext(&parameter->iterators[j], taskpointerarray))
 430       toiNext(&parameter->iterators[j], taskpointerarray);
 431     else if (j>0) {
 432       /* Need to backtrack */
 433       toiReset(&parameter->iterators[j]);
 434       j--;
 435       goto backtrackinit;
 436     } else {
 437       /* Nothing to enqueue */
 438       return;
 439     }
 440   }
 441
 442
 443   while(1) {
 444     /* Enqueue current state */
 445     struct taskparamdescriptor *tpd=RUNMALLOC(sizeof(struct taskparamdescriptor));
 446     tpd->task=task;
 447     tpd->numParameters=numiterators+1;
 448     tpd->parameterArray=RUNMALLOC(sizeof(void *)*(numiterators+1));
 449     for(j=0;j<=numiterators;j++)
 450       tpd->parameterArray[j]=taskpointerarray[j];
 451
 452     /* Enqueue task */
 453     if (!gencontains(failedtasks, tpd)&&!gencontains(activetasks,tpd)) {
 454       genputtable(activetasks, tpd, tpd);
 455     } else {
 456       RUNFREE(tpd->parameterArray);
 457       RUNFREE(tpd);
 458     }
 459
 460     /* This loop iterates to the next parameter combination */
 461     if (numiterators==0)
 462       return;
 463
 464     for(j=numiterators-1; j<numiterators;j++) {
 465     backtrackinc:
 466       if(toiHasNext(&parameter->iterators[j], taskpointerarray))
 467         toiNext(&parameter->iterators[j], taskpointerarray);
 468       else if (j>0) {
 469         /* Need to backtrack */
 470         toiReset(&parameter->iterators[j]);
 471         j--;
 472         goto backtrackinc;
 473       } else {
 474         /* Nothing more to enqueue */
 475         return;
 476       }
 477     }
 478   }
 479 }
 480
 481 /* Handler for signals. The signals catch null pointer errors and
 482    arithmatic errors. */
 483
 484 void myhandler(int sig, siginfo_t *info, void *uap) {
 485 #ifdef DEBUG
 486   printf("sig=%d\n",sig);
 487   printf("signal\n");
 488 #endif
 489   longjmp(error_handler,1);
 490 }
 491
 492 fd_set readfds;
 493 int maxreadfd;
 494 struct RuntimeHash *fdtoobject;
 495
 496 void addreadfd(int fd) {
 497   if (fd>=maxreadfd)
 498     maxreadfd=fd+1;
 499   FD_SET(fd, &readfds);
 500 }
 501
 502 void removereadfd(int fd) {
 503   FD_CLR(fd, &readfds);
 504   if (maxreadfd==(fd+1)) {
 505     maxreadfd--;
 506     while(maxreadfd>0&&!FD_ISSET(maxreadfd-1, &readfds))
 507       maxreadfd--;
 508   }
 509 }
 510
 511 #ifdef PRECISE_GC
 512 #define OFFSET 2
 513 #else
 514 #define OFFSET 0
 515 #endif
 516
 517 void executetasks() {
 518   void * taskpointerarray[MAXTASKPARAMS+OFFSET];
 519
 520   /* Set up signal handlers */
 521   struct sigaction sig;
 522   sig.sa_sigaction=&myhandler;
 523   sig.sa_flags=SA_SIGINFO;
 524   sigemptyset(&sig.sa_mask);
 525
 526   /* Catch bus errors, segmentation faults, and floating point exceptions*/
 527   sigaction(SIGBUS,&sig,0);
 528   sigaction(SIGSEGV,&sig,0);
 529   sigaction(SIGFPE,&sig,0);
 530   sigaction(SIGPIPE,&sig,0);
 531
 532   /* Zero fd set */
 533   FD_ZERO(&readfds);
 534   maxreadfd=0;
 535   fdtoobject=allocateRuntimeHash(100);
 536
 537   /* Map first block of memory to protected, anonymous page */
 538   mmap(0, 0x1000, 0, MAP_SHARED|MAP_FIXED|MAP_ANON, -1, 0);
 539
 540   newtask:
 541   while((hashsize(activetasks)>0)||(maxreadfd>0)) {
 542
 543     /* Check if any filedescriptors have IO pending */
 544     if (maxreadfd>0) {
 545       int i;
 546       struct timeval timeout={0,0};
 547       fd_set tmpreadfds;
 548       int numselect;
 549       tmpreadfds=readfds;
 550       numselect=select(maxreadfd, &tmpreadfds, NULL, NULL, &timeout);
 551       if (numselect>0) {
 552         /* Process ready fd's */
 553         int fd;
 554         for(fd=0;fd<maxreadfd;fd++) {
 555           if (FD_ISSET(fd, &tmpreadfds)) {
 556             /* Set ready flag on object */
 557             void * objptr;
 558             //      printf("Setting fd %d\n",fd);
 559             if (RuntimeHashget(fdtoobject, fd,(int *) &objptr)) {
 560               intflagorand(objptr,1,0xFFFFFFFF); /* Set the first flag to 1 */
 561             }
 562           }
 563         }
 564       }
 565     }
 566
 567     /* See if there are any active tasks */
 568     if (hashsize(activetasks)>0) {
 569       int i;
 570       currtpd=(struct taskparamdescriptor *) getfirstkey(activetasks);
 571       genfreekey(activetasks, currtpd);
 572
 573       /* Check if this task has failed */
 574       if (gencontains(failedtasks, currtpd)) {
 575         // Free up task parameter descriptor
 576         RUNFREE(currtpd->parameterArray);
 577         RUNFREE(currtpd);
 578         goto newtask;
 579       }
 580       int numparams=currtpd->task->numParameters;
 581       int numtotal=currtpd->task->numTotal;
 582
 583       /* Make sure that the parameters are still in the queues */
 584       for(i=0;i<numparams;i++) {
 585         void * parameter=currtpd->parameterArray[i];
 586         struct parameterdescriptor * pd=currtpd->task->descriptorarray[i];
 587         struct parameterwrapper *pw=(struct parameterwrapper *) pd->queue;
 588         int j;
 589         /* Check that object is still in queue */
 590         if (!RuntimeHashcontainskey(pw->objectset, (int) parameter)) {
 591           RUNFREE(currtpd->parameterArray);
 592           RUNFREE(currtpd);
 593           goto newtask;
 594         }
 595         /* Check that object still has necessary tags */
 596         for(j=0;j<pd->numbertags;j++) {
 597           int slotid=pd->tagarray[2*i]+numparams;
 598           struct ___TagDescriptor___ *tagd=currtpd->parameterArray[slotid];
 599           if (!containstag(parameter, tagd)) {
 600             RUNFREE(currtpd->parameterArray);
 601             RUNFREE(currtpd);
 602             goto newtask;
 603           }
 604         }
 605
 606         taskpointerarray[i+OFFSET]=parameter;
 607       }
 608       /* Copy the tags */
 609       for(;i<numtotal;i++) {
 610         taskpointerarray[i+OFFSET]=currtpd->parameterArray[i];
 611       }
 612
 613       {
 614         /* Checkpoint the state */
 615         forward=allocateRuntimeHash(100);
 616         reverse=allocateRuntimeHash(100);
 617         void ** checkpoint=makecheckpoint(currtpd->task->numParameters, currtpd->parameterArray, forward, reverse);
 618         int x;
 619         if (x=setjmp(error_handler)) {
 620           /* Recover */
 621           int h;
 622 #ifdef DEBUG
 623           printf("Fatal Error=%d, Recovering!\n",x);
 624 #endif
 625           genputtable(failedtasks,currtpd,currtpd);
 626           restorecheckpoint(currtpd->task->numParameters, currtpd->parameterArray, checkpoint, forward, reverse);
 627           freeRuntimeHash(forward);
 628           freeRuntimeHash(reverse);
 629           freemalloc();
 630           forward=NULL;
 631           reverse=NULL;
 632         } else {
 633           if (injectfailures) {
 634             if ((((double)random())/RAND_MAX)<failurechance) {
 635               printf("\nINJECTING TASK FAILURE to %s\n", currtpd->task->name);
 636               longjmp(error_handler,10);
 637             }
 638           }
 639           /* Actually call task */
 640 #ifdef PRECISE_GC
 641           ((int *)taskpointerarray)[0]=currtpd->task->numParameters;
 642           taskpointerarray[1]=NULL;
 643 #endif
 644
 645           if (debugtask) {
 646             printf("ENTER %s count=%d\n",currtpd->task->name, (instaccum-instructioncount));
 647             ((void (*) (void **)) currtpd->task->taskptr)(taskpointerarray);
 648             printf("EXIT %s count=%d\n",currtpd->task->name, (instaccum-instructioncount));
 649           } else
 650             ((void (*) (void **)) currtpd->task->taskptr)(taskpointerarray);
 651           freeRuntimeHash(forward);
 652           freeRuntimeHash(reverse);
 653           freemalloc();
 654           // Free up task parameter descriptor
 655           RUNFREE(currtpd->parameterArray);
 656           RUNFREE(currtpd);
 657           forward=NULL;
 658           reverse=NULL;
 659         }
 660       }
 661     }
 662   }
 663 }
 664
 665 /* This function processes an objects tags */
 666 void processtags(struct parameterdescriptor *pd, int index, struct parameterwrapper *parameter, int * iteratorcount, int *statusarray, int numparams) {
 667   int i;
 668
 669   for(i=0;i<pd->numbertags;i++) {
 670     int slotid=pd->tagarray[2*i];
 671     int tagid=pd->tagarray[2*i+1];
 672
 673     if (statusarray[slotid+numparams]==0) {
 674       parameter->iterators[*iteratorcount].istag=1;
 675       parameter->iterators[*iteratorcount].tagid=tagid;
 676       parameter->iterators[*iteratorcount].slot=slotid+numparams;
 677       parameter->iterators[*iteratorcount].tagobjectslot=index;
 678       statusarray[slotid+numparams]=1;
 679       (*iteratorcount)++;
 680     }
 681   }
 682 }
 683
 684
 685 void processobject(struct parameterwrapper *parameter, int index, struct parameterdescriptor *pd, int *iteratorcount, int * statusarray, int numparams) {
 686   int i;
 687   int tagcount=0;
 688   struct RuntimeHash * objectset=((struct parameterwrapper *)pd->queue)->objectset;
 689
 690   parameter->iterators[*iteratorcount].istag=0;
 691   parameter->iterators[*iteratorcount].slot=index;
 692   parameter->iterators[*iteratorcount].objectset=objectset;
 693   statusarray[index]=1;
 694
 695   for(i=0;i<pd->numbertags;i++) {
 696     int slotid=pd->tagarray[2*i];
 697     int tagid=pd->tagarray[2*i+1];
 698     if (statusarray[slotid+numparams]!=0) {
 699       /* This tag has already been enqueued, use it to narrow search */
 700       parameter->iterators[*iteratorcount].tagbindings[tagcount]=slotid+numparams;
 701       tagcount++;
 702     }
 703   }
 704   parameter->iterators[*iteratorcount].numtags=tagcount;
 705
 706   (*iteratorcount)++;
 707 }
 708
 709 /* This function builds the iterators for a task & parameter */
 710
 711 void builditerators(struct taskdescriptor * task, int index, struct parameterwrapper * parameter) {
 712   int statusarray[MAXTASKPARAMS];
 713   int i;
 714   int numparams=task->numParameters;
 715   int iteratorcount=0;
 716   for(i=0;i<MAXTASKPARAMS;i++) statusarray[i]=0;
 717
 718   statusarray[index]=1; /* Initial parameter */
 719   /* Process tags for initial iterator */
 720
 721   processtags(task->descriptorarray[index], index, parameter, & iteratorcount, statusarray, numparams);
 722
 723   while(1) {
 724   loopstart:
 725     /* Check for objects with existing tags */
 726     for(i=0;i<numparams;i++) {
 727       if (statusarray[i]==0) {
 728         struct parameterdescriptor *pd=task->descriptorarray[i];
 729         int j;
 730         for(j=0;j<pd->numbertags;j++) {
 731           int slotid=pd->tagarray[2*j];
 732           if(statusarray[slotid+numparams]!=0) {
 733             processobject(parameter, i, pd, &iteratorcount, statusarray, numparams);
 734             processtags(pd, i, parameter, &iteratorcount, statusarray, numparams);
 735             goto loopstart;
 736           }
 737         }
 738       }
 739     }
 740     /* Nothing with a tag enqueued */
 741
 742     for(i=0;i<numparams;i++) {
 743       if (statusarray[i]==0) {
 744         struct parameterdescriptor *pd=task->descriptorarray[i];
 745         processobject(parameter, i, pd, &iteratorcount, statusarray, numparams);
 746         processtags(pd, i, parameter, &iteratorcount, statusarray, numparams);
 747         goto loopstart;
 748       }
 749     }
 750
 751     /* Nothing left */
 752     return;
 753   }
 754 }
 755
 756
 757
 758
 759 /* This function processes the task information to create queues for
 760    each parameter type. */
 761
 762 void processtasks() {
 763   int i;
 764   for(i=0;i<numtasks;i++) {
 765     struct taskdescriptor * task=taskarray[i];
 766     int j;
 767
 768     for(j=0;j<task->numParameters;j++) {
 769       struct parameterdescriptor *param=task->descriptorarray[j];
 770       struct parameterwrapper * parameter=RUNMALLOC(sizeof(struct parameterwrapper));
 771       struct parameterwrapper ** ptr=&objectqueues[param->type];
 772
 773       param->queue=parameter;
 774       parameter->objectset=allocateRuntimeHash(10);
 775       parameter->numberofterms=param->numberterms;
 776       parameter->intarray=param->intarray;
 777       parameter->numbertags=param->numbertags;
 778       parameter->tagarray=param->tagarray;
 779       parameter->task=task;
 780       /* Link new queue in */
 781       while((*ptr)!=NULL)
 782         ptr=&((*ptr)->next);
 783       (*ptr)=parameter;
 784     }
 785
 786     /* Build iterators for parameters */
 787     for(j=0;j<task->numParameters;j++) {
 788       struct parameterdescriptor *param=task->descriptorarray[j];
 789       struct parameterwrapper *parameter=param->queue;
 790       parameter->slot=j;
 791       builditerators(task, j, parameter);
 792     }
 793   }
 794 }
 795
 796 void toiReset(struct tagobjectiterator * it) {
 797   if (it->istag) {
 798     it->tagobjindex=0;
 799   } else if (it->numtags>0) {
 800     it->tagobjindex=0;
 801   } else {
 802     RuntimeHashiterator(it->objectset, &it->it);
 803   }
 804 }
 805
 806 int toiHasNext(struct tagobjectiterator *it, void ** objectarray) {
 807   if (it->istag) {
 808     /* Iterate tag */
 809     /* Get object with tags */
 810     struct ___Object___ *obj=objectarray[it->tagobjectslot];
 811     struct ___Object___ *tagptr=obj->___tags___;
 812     if (tagptr->type==TAGTYPE) {
 813       if ((it->tagobjindex==0)&& /* First object */
 814           (it->tagid==((struct ___TagDescriptor___ *)tagptr)->flag)) /* Right tag type */
 815         return 1;
 816       else
 817         return 0;
 818     } else {
 819       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 820       int tagindex=it->tagobjindex;
 821       for(;tagindex<ao->___cachedCode___;tagindex++) {
 822         struct ___TagDescriptor___ *td=ARRAYGET(ao, struct ___TagDescriptor___ *, tagindex);
 823         if (td->flag==it->tagid) {
 824           it->tagobjindex=tagindex; /* Found right type of tag */
 825           return 1;
 826         }
 827       }
 828       return 0;
 829     }
 830   } else if (it->numtags>0) {
 831     /* Use tags to locate appropriate objects */
 832     struct ___TagDescriptor___ *tag=objectarray[it->tagbindings[0]];
 833     struct ___Object___ *objptr=tag->flagptr;
 834     int i;
 835     if (objptr->type!=OBJECTARRAYTYPE) {
 836       if (it->tagobjindex>0)
 837         return 0;
 838       if (!RuntimeHashcontainskey(it->objectset, (int) objptr))
 839         return 0;
 840       for(i=1;i<it->numtags;i++) {
 841         struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
 842         if (!containstag(objptr,tag2))
 843           return 0;
 844       }
 845       return 1;
 846     } else {
 847       struct ArrayObject *ao=(struct ArrayObject *) objptr;
 848       int tagindex;
 849       int i;
 850       for(tagindex=it->tagobjindex;tagindex<ao->___cachedCode___;tagindex++) {
 851         struct ___Object___ *objptr=ARRAYGET(ao, struct ___Object___*, tagindex);
 852         if (!RuntimeHashcontainskey(it->objectset, (int) objptr))
 853           continue;
 854         for(i=1;i<it->numtags;i++) {
 855           struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
 856           if (!containstag(objptr,tag2))
 857             goto nexttag;
 858         }
 859         return 1;
 860       nexttag:
 861         ;
 862       }
 863       it->tagobjindex=tagindex;
 864       return 0;
 865     }
 866   } else {
 867     return RunhasNext(&it->it);
 868   }
 869 }
 870
 871 int containstag(struct ___Object___ *ptr, struct ___TagDescriptor___ *tag) {
 872   int j;
 873   struct ___Object___ * objptr=tag->flagptr;
 874   if (objptr->type==OBJECTARRAYTYPE) {
 875     struct ArrayObject *ao=(struct ArrayObject *)objptr;
 876     for(j=0;j<ao->___cachedCode___;j++) {
 877       if (ptr==ARRAYGET(ao, struct ___Object___*, j))
 878         return 1;
 879     }
 880     return 0;
 881   } else
 882     return objptr==ptr;
 883 }
 884
 885 void toiNext(struct tagobjectiterator *it , void ** objectarray) {
 886   /* hasNext has all of the intelligence */
 887   if(it->istag) {
 888     /* Iterate tag */
 889     /* Get object with tags */
 890     struct ___Object___ *obj=objectarray[it->tagobjectslot];
 891     struct ___Object___ *tagptr=obj->___tags___;
 892     if (tagptr->type==TAGTYPE) {
 893       it->tagobjindex++;
 894       objectarray[it->slot]=tagptr;
 895     } else {
 896       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 897       objectarray[it->slot]=ARRAYGET(ao, struct ___TagDescriptor___ *, it->tagobjindex++);
 898     }
 899   } else if (it->numtags>0) {
 900     /* Use tags to locate appropriate objects */
 901     struct ___TagDescriptor___ *tag=objectarray[it->tagbindings[0]];
 902     struct ___Object___ *objptr=tag->flagptr;
 903     if (objptr->type!=OBJECTARRAYTYPE) {
 904       it->tagobjindex++;
 905       objectarray[it->slot]=objptr;
 906     } else {
 907       struct ArrayObject *ao=(struct ArrayObject *) objptr;
 908       objectarray[it->slot]=ARRAYGET(ao, struct ___Object___ *, it->tagobjindex++);
 909     }
 910   } else {
 911     /* Iterate object */
 912     objectarray[it->slot]=(void *)Runkey(&it->it);
 913     Runnext(&it->it);
 914   }
 915 }
 916
 917
 918 #endif
 919
 920 void exithandler(int sig, siginfo_t *info, void * uap) {
 921   exit(0);
 922 }
 923
 924 void initializeexithandler() {
 925   struct sigaction sig;
 926   sig.sa_sigaction=&exithandler;
 927   sig.sa_flags=SA_SIGINFO;
 928   sigemptyset(&sig.sa_mask);
 929   sigaction(SIGUSR2, &sig, 0);
 930 }
 931
 932
 933 /* This function inject failures */
 934
 935 void injectinstructionfailure() {
 936 #ifdef TASK
 937   if (injectinstructionfailures) {
 938     if (numfailures==0)
 939       return;
 940     instructioncount=failurecount;
 941     instaccum+=failurecount;
 942     if ((((double)random())/RAND_MAX)<instfailurechance) {
 943       if (numfailures>0)
 944         numfailures--;
 945       printf("FAILURE!!! %d\n",numfailures);
 946       longjmp(error_handler,11);
 947     }
 948   }
 949 #else
 950 #ifdef THREADS
 951   if (injectinstructionfailures) {
 952     if (numfailures==0)
 953       return;
 954     instaccum+=failurecount;
 955     if ((((double)random())/RAND_MAX)<instfailurechance) {
 956       if (numfailures>0)
 957         numfailures--;
 958       printf("FAILURE!!! %d\n",numfailures);
 959       threadexit();
 960     }
 961   }
 962 #endif
 963 #endif
 964 }
 965
 966 void CALL01(___System______printString____L___String___,struct ___String___ * ___s___) {
 967     struct ArrayObject * chararray=VAR(___s___)->___value___;
 968     int i;
 969     int offset=VAR(___s___)->___offset___;
 970     for(i=0;i<VAR(___s___)->___count___;i++) {
 971         short sc=((short *)(((char *)& chararray->___length___)+sizeof(int)))[i+offset];
 972         putchar(sc);
 973     }
 974 }
 975
 976 /* Object allocation function */
 977
 978 #ifdef PRECISE_GC
 979 void * allocate_new(void * ptr, int type) {
 980   struct ___Object___ * v=(struct ___Object___ *) mygcmalloc((struct garbagelist *) ptr, classsize[type]);
 981   v->type=type;
 982 #ifdef THREADS
 983   v->tid=0;
 984   v->lockentry=0;
 985   v->lockcount=0;
 986 #endif
 987   return v;
 988 }
 989
 990 /* Array allocation function */
 991
 992 struct ArrayObject * allocate_newarray(void * ptr, int type, int length) {
 993   struct ArrayObject * v=mygcmalloc((struct garbagelist *) ptr, sizeof(struct ArrayObject)+length*classsize[type]);
 994   v->type=type;
 995   if (length<0) {
 996     printf("ERROR: negative array\n");
 997     return NULL;
 998   }
 999   v->___length___=length;
1000 #ifdef THREADS
1001   v->tid=0;
1002   v->lockentry=0;
1003   v->lockcount=0;
1004 #endif
1005   return v;
1006 }
1007
1008 #else
1009 void * allocate_new(int type) {
1010   void * v=FREEMALLOC(classsize[type]);
1011   *((int *)v)=type;
1012   return v;
1013 }
1014
1015 /* Array allocation function */
1016
1017 struct ArrayObject * allocate_newarray(int type, int length) {
1018   struct ArrayObject * v=FREEMALLOC(sizeof(struct ArrayObject)+length*classsize[type]);
1019   v->type=type;
1020   v->___length___=length;
1021   return v;
1022 }
1023 #endif
1024
1025
1026 /* Converts C character arrays into Java strings */
1027 #ifdef PRECISE_GC
1028 struct ___String___ * NewString(void * ptr, const char *str,int length) {
1029 #else
1030 struct ___String___ * NewString(const char *str,int length) {
1031 #endif
1032   int i;
1033 #ifdef PRECISE_GC
1034   struct ArrayObject * chararray=allocate_newarray((struct garbagelist *)ptr, CHARARRAYTYPE, length);
1035   int ptrarray[]={1, (int) ptr, (int) chararray};
1036   struct ___String___ * strobj=allocate_new((struct garbagelist *) &ptrarray, STRINGTYPE);
1037   chararray=(struct ArrayObject *) ptrarray[2];
1038 #else
1039   struct ArrayObject * chararray=allocate_newarray(CHARARRAYTYPE, length);
1040   struct ___String___ * strobj=allocate_new(STRINGTYPE);
1041 #endif
1042   strobj->___value___=chararray;
1043   strobj->___count___=length;
1044   strobj->___offset___=0;
1045
1046   for(i=0;i<length;i++) {
1047     ((short *)(((char *)& chararray->___length___)+sizeof(int)))[i]=(short)str[i];  }
1048   return strobj;
1049 }
1050
1051 /* Generated code calls this if we fail a bounds check */
1052
1053 void failedboundschk() {
1054 #ifndef TASK
1055   printf("Array out of bounds\n");
1056 #ifdef THREADS
1057   threadexit();
1058 #else
1059   exit(-1);
1060 #endif
1061 #else
1062   longjmp(error_handler,2);
1063 #endif
1064 }
1065
1066 /* Abort task call */
1067 void abort_task() {
1068 #ifdef TASK
1069   longjmp(error_handler,4);
1070 #else
1071   printf("Aborting\n");
1072   exit(-1);
1073 #endif
1074 }