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