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