Robust/src/Runtime/task.c

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