Robust/src/Runtime/bamboo/multicoretask.c

   1 #ifdef TASK
   2 #include "runtime.h"
   3 #include "multicoreruntime.h"
   4 #include "multicoretaskprofile.h"
   5 #include "multicoretask.h"
   6
   7 #ifndef INLINE
   8 #define INLINE    inline __attribute__((always_inline))
   9 #endif
  10
  11 //  data structures for task invocation
  12 struct genhashtable * activetasks;
  13 struct taskparamdescriptor * currtpd;
  14 struct LockValue runtime_locks[MAXTASKPARAMS];
  15 int runtime_locklen;
  16
  17 // specific functions used inside critical sections
  18 void enqueueObject_I(void * ptr,
  19                      struct parameterwrapper ** queues,
  20                      int length);
  21 int enqueuetasks_I(struct parameterwrapper *parameter,
  22                    struct parameterwrapper *prevptr,
  23                    struct ___Object___ *ptr,
  24                    int * enterflags,
  25                    int numenterflags);
  26
  27 INLINE void initlocktable() {
  28 #ifdef MULTICORE_GC
  29   // do nothing
  30 #else
  31   // create the lock table, lockresult table and obj queue
  32   locktable.size = 20;
  33   locktable.bucket =
  34     (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*20);
  35   /* Set allocation blocks*/
  36   locktable.listhead=NULL;
  37   locktable.listtail=NULL;
  38   /*Set data counts*/
  39   locktable.numelements = 0;
  40   lockobj = 0;
  41   lock2require = 0;
  42   lockresult = 0;
  43   lockflag = false;
  44   lockRedirectTbl = allocateRuntimeHash_I(20);
  45   objRedirectLockTbl = allocateRuntimeHash_I(20);
  46 #endif
  47 }
  48
  49 INLINE void dislocktable() {
  50 #ifdef MULTICORE_GC
  51   // do nothing
  52 #else
  53   freeRuntimeHash(lockRedirectTbl);
  54   freeRuntimeHash(objRedirectLockTbl);
  55   RUNFREE(locktable.bucket);
  56 #endif
  57 }
  58
  59 INLINE void inittaskdata() {
  60   if(STARTUPCORE == BAMBOO_NUM_OF_CORE) {
  61     // startup core to initialize corestatus[]
  62     total_num_t6 = 0; // TODO for test
  63   }
  64   totransobjqueue = createQueue_I();
  65   objqueue.head = NULL;
  66   objqueue.tail = NULL;
  67   currtpd = NULL;
  68   for(int i = 0; i < MAXTASKPARAMS; i++) {
  69     runtime_locks[i].redirectlock = 0;
  70     runtime_locks[i].value = 0;
  71   }
  72   runtime_locklen = 0;
  73   initlocktable();
  74   INIT_TASKPROFILE_DATA();
  75 }
  76
  77 INLINE void distaskdata() {
  78   if(activetasks != NULL) {
  79     genfreehashtable(activetasks);
  80   }
  81   if(currtpd != NULL) {
  82     RUNFREE(currtpd->parameterArray);
  83     RUNFREE(currtpd);
  84     currtpd = NULL;
  85   }
  86   dislocktable();
  87 }
  88
  89 INLINE bool checkObjQueue() {
  90   bool rflag = false;
  91   struct transObjInfo * objInfo = NULL;
  92   int grount = 0;
  93
  94 #ifdef ACCURATEPROFILE
  95   PROFILE_TASK_START("objqueue checking");
  96 #endif
  97
  98   while(!isEmpty(&objqueue)) {
  99     void * obj = NULL;
 100     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 101     rflag = true;
 102     objInfo = (struct transObjInfo *)getItem(&objqueue);
 103     obj = objInfo->objptr;
 104     // grab lock and flush the obj
 105     grount = 0;
 106     struct ___Object___ * tmpobj = (struct ___Object___ *)obj;
 107     while(tmpobj->lock != NULL) {
 108       tmpobj = (struct ___Object___ *)(tmpobj->lock);
 109     }
 110     getwritelock_I(tmpobj);
 111     while(!lockflag) {
 112       BAMBOO_WAITING_FOR_LOCK(0);
 113     }
 114     grount = lockresult;
 115
 116     lockresult = 0;
 117     lockobj = 0;
 118     lock2require = 0;
 119     lockflag = false;
 120 #ifndef INTERRUPT
 121     reside = false;
 122 #endif
 123
 124     if(grount == 1) {
 125       int k = 0;
 126       // flush the object
 127       BAMBOO_CACHE_FLUSH_RANGE((int)obj,sizeof(int));
 128       BAMBOO_CACHE_FLUSH_RANGE((int)obj,
 129           classsize[((struct ___Object___ *)obj)->type]);
 130       // enqueue the object
 131       for(k = 0; k < objInfo->length; k++) {
 132         int taskindex = objInfo->queues[2 * k];
 133         int paramindex = objInfo->queues[2 * k + 1];
 134         struct parameterwrapper ** queues =
 135           &(paramqueues[BAMBOO_NUM_OF_CORE][taskindex][paramindex]);
 136         enqueueObject_I(obj, queues, 1);
 137       }
 138       releasewritelock_I(tmpobj);
 139       RUNFREE_I(objInfo->queues);
 140       RUNFREE_I(objInfo);
 141     } else {
 142       // can not get lock
 143       // put it at the end of the queue if no update version in the queue
 144       struct QueueItem * qitem = getHead(&objqueue);
 145       struct QueueItem * prev = NULL;
 146       while(qitem != NULL) {
 147                 struct transObjInfo * tmpinfo =
 148                         (struct transObjInfo *)(qitem->objectptr);
 149                 if(tmpinfo->objptr == obj) {
 150                   // the same object in the queue, which should be enqueued
 151                   // recently. Current one is outdate, do not re-enqueue it
 152                   RUNFREE_I(objInfo->queues);
 153                   RUNFREE_I(objInfo);
 154                   goto objqueuebreak;
 155                 } else {
 156                   prev = qitem;
 157                 }
 158                 qitem = getNextQueueItem(prev);
 159           }
 160       // try to execute active tasks already enqueued first
 161       addNewItem_I(&objqueue, objInfo);
 162 objqueuebreak:
 163       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 164       break;
 165     }
 166     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 167   }
 168
 169 #ifdef ACCURATEPROFILE
 170   PROFILE_TASK_END();
 171 #endif
 172
 173   return rflag;
 174 }
 175
 176 struct ___createstartupobject____I_locals {
 177   INTPTR size;
 178   void * next;
 179   struct  ___StartupObject___ * ___startupobject___;
 180   struct ArrayObject * ___stringarray___;
 181 };
 182
 183 void createstartupobject(int argc,
 184                          char ** argv) {
 185   int i;
 186
 187   /* Allocate startup object     */
 188 #ifdef MULTICORE_GC
 189   struct ___createstartupobject____I_locals ___locals___ =
 190   {2, NULL, NULL, NULL};
 191   struct ___StartupObject___ *startupobject=
 192     (struct ___StartupObject___*) allocate_new(&___locals___, STARTUPTYPE);
 193   ___locals___.___startupobject___ = startupobject;
 194   struct ArrayObject * stringarray=
 195     allocate_newarray(&___locals___, STRINGARRAYTYPE, argc-1);
 196   ___locals___.___stringarray___ = stringarray;
 197 #else
 198   struct ___StartupObject___ *startupobject=
 199     (struct ___StartupObject___*) allocate_new(STARTUPTYPE);
 200   struct ArrayObject * stringarray=
 201     allocate_newarray(STRINGARRAYTYPE, argc-1);
 202 #endif
 203   /* Build array of strings */
 204   startupobject->___parameters___=stringarray;
 205   for(i=1; i<argc; i++) {
 206     int length=strlen(argv[i]);
 207 #ifdef MULTICORE_GC
 208     struct ___String___ *newstring=NewString(&___locals___, argv[i],length);
 209 #else
 210     struct ___String___ *newstring=NewString(argv[i],length);
 211 #endif
 212     ((void **)(((char *)&stringarray->___length___)+sizeof(int)))[i-1]=
 213       newstring;
 214   }
 215
 216   startupobject->version = 0;
 217   startupobject->lock = NULL;
 218
 219   /* Set initialized flag for startup object */
 220   flagorandinit(startupobject,1,0xFFFFFFFF);
 221   enqueueObject(startupobject, NULL, 0);
 222   BAMBOO_CACHE_FLUSH_ALL();
 223 }
 224
 225 int hashCodetpd(struct taskparamdescriptor *ftd) {
 226   int hash=(int)ftd->task;
 227   int i;
 228   for(i=0; i<ftd->numParameters; i++) {
 229     hash^=(int)ftd->parameterArray[i];
 230   }
 231   return hash;
 232 }
 233
 234 int comparetpd(struct taskparamdescriptor *ftd1,
 235                struct taskparamdescriptor *ftd2) {
 236   int i;
 237   if (ftd1->task!=ftd2->task)
 238     return 0;
 239   for(i=0; i<ftd1->numParameters; i++)
 240     if(ftd1->parameterArray[i]!=ftd2->parameterArray[i])
 241       return 0;
 242   return 1;
 243 }
 244
 245 /* This function sets a tag. */
 246 #ifdef MULTICORE_GC
 247 void tagset(void *ptr,
 248             struct ___Object___ * obj,
 249             struct ___TagDescriptor___ * tagd) {
 250 #else
 251 void tagset(struct ___Object___ * obj,
 252             struct ___TagDescriptor___ * tagd) {
 253 #endif
 254   struct ArrayObject * ao=NULL;
 255   struct ___Object___ * tagptr=obj->___tags___;
 256   if (tagptr==NULL) {
 257     obj->___tags___=(struct ___Object___ *)tagd;
 258   } else {
 259     /* Have to check if it is already set */
 260     if (tagptr->type==TAGTYPE) {
 261       struct ___TagDescriptor___ * td=(struct ___TagDescriptor___ *) tagptr;
 262       if (td==tagd) {
 263                 return;
 264       }
 265 #ifdef MULTICORE_GC
 266       int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 267       struct ArrayObject * ao=
 268         allocate_newarray(&ptrarray,TAGARRAYTYPE,TAGARRAYINTERVAL);
 269       obj=(struct ___Object___ *)ptrarray[2];
 270       tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 271       td=(struct ___TagDescriptor___ *) obj->___tags___;
 272 #else
 273       ao=allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL);
 274 #endif
 275
 276       ARRAYSET(ao, struct ___TagDescriptor___ *, 0, td);
 277       ARRAYSET(ao, struct ___TagDescriptor___ *, 1, tagd);
 278       obj->___tags___=(struct ___Object___ *) ao;
 279       ao->___cachedCode___=2;
 280     } else {
 281       /* Array Case */
 282       int i;
 283       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 284       for(i=0; i<ao->___cachedCode___; i++) {
 285                 struct ___TagDescriptor___ * td=
 286                   ARRAYGET(ao, struct ___TagDescriptor___*, i);
 287                 if (td==tagd) {
 288                   return;
 289                 }
 290       }
 291       if (ao->___cachedCode___<ao->___length___) {
 292                 ARRAYSET(ao, struct ___TagDescriptor___ *,ao->___cachedCode___,tagd);
 293                 ao->___cachedCode___++;
 294       } else {
 295 #ifdef MULTICORE_GC
 296                 int ptrarray[]={2,(int) ptr, (int) obj, (int) tagd};
 297                 struct ArrayObject * aonew=
 298                   allocate_newarray(&ptrarray,TAGARRAYTYPE,
 299                                                         TAGARRAYINTERVAL+ao->___length___);
 300                 obj=(struct ___Object___ *)ptrarray[2];
 301                 tagd=(struct ___TagDescriptor___ *) ptrarray[3];
 302                 ao=(struct ArrayObject *)obj->___tags___;
 303 #else
 304                 struct ArrayObject * aonew=
 305                   allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL+ao->___length___);
 306 #endif
 307
 308                 aonew->___cachedCode___=ao->___length___+1;
 309                 for(i=0; i<ao->___length___; i++) {
 310                   ARRAYSET(aonew, struct ___TagDescriptor___*, i,
 311                                    ARRAYGET(ao, struct ___TagDescriptor___*, i));
 312                 }
 313                 ARRAYSET(aonew, struct ___TagDescriptor___ *, ao->___length___,tagd);
 314       }
 315     }
 316   }
 317
 318   {
 319     struct ___Object___ * tagset=tagd->flagptr;
 320     if(tagset==NULL) {
 321       tagd->flagptr=obj;
 322     } else if (tagset->type!=OBJECTARRAYTYPE) {
 323 #ifdef MULTICORE_GC
 324       int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 325       struct ArrayObject * ao=
 326         allocate_newarray(&ptrarray,OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
 327       obj=(struct ___Object___ *)ptrarray[2];
 328       tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 329 #else
 330       struct ArrayObject * ao=
 331         allocate_newarray(OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
 332 #endif
 333       ARRAYSET(ao, struct ___Object___ *, 0, tagd->flagptr);
 334       ARRAYSET(ao, struct ___Object___ *, 1, obj);
 335       ao->___cachedCode___=2;
 336       tagd->flagptr=(struct ___Object___ *)ao;
 337     } else {
 338       struct ArrayObject *ao=(struct ArrayObject *) tagset;
 339       if (ao->___cachedCode___<ao->___length___) {
 340         ARRAYSET(ao, struct ___Object___*, ao->___cachedCode___++, obj);
 341       } else {
 342         int i;
 343 #ifdef MULTICORE_GC
 344         int ptrarray[]={2, (int) ptr, (int) obj, (int)tagd};
 345         struct ArrayObject * aonew=
 346           allocate_newarray(&ptrarray,OBJECTARRAYTYPE,
 347                             OBJECTARRAYINTERVAL+ao->___length___);
 348         obj=(struct ___Object___ *)ptrarray[2];
 349         tagd=(struct ___TagDescriptor___ *)ptrarray[3];
 350         ao=(struct ArrayObject *)tagd->flagptr;
 351 #else
 352         struct ArrayObject * aonew=allocate_newarray(OBJECTARRAYTYPE,
 353                                                      OBJECTARRAYINTERVAL+ao->___length___);
 354 #endif
 355         aonew->___cachedCode___=ao->___cachedCode___+1;
 356         for(i=0; i<ao->___length___; i++) {
 357           ARRAYSET(aonew, struct ___Object___*, i,
 358                    ARRAYGET(ao, struct ___Object___*, i));
 359         }
 360         ARRAYSET(aonew, struct ___Object___ *, ao->___cachedCode___, obj);
 361         tagd->flagptr=(struct ___Object___ *) aonew;
 362       }
 363     }
 364   }
 365 }
 366
 367 /* This function clears a tag. */
 368 #ifdef MULTICORE_GC
 369 void tagclear(void *ptr, struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 370 #else
 371 void tagclear(struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
 372 #endif
 373   /* We'll assume that tag is alway there.
 374      Need to statically check for this of course. */
 375   struct ___Object___ * tagptr=obj->___tags___;
 376
 377   if (tagptr->type==TAGTYPE) {
 378     if ((struct ___TagDescriptor___ *)tagptr==tagd)
 379       obj->___tags___=NULL;
 380   } else {
 381     struct ArrayObject *ao=(struct ArrayObject *) tagptr;
 382     int i;
 383     for(i=0; i<ao->___cachedCode___; i++) {
 384       struct ___TagDescriptor___ * td=
 385         ARRAYGET(ao, struct ___TagDescriptor___ *, i);
 386       if (td==tagd) {
 387         ao->___cachedCode___--;
 388         if (i<ao->___cachedCode___)
 389           ARRAYSET(ao, struct ___TagDescriptor___ *, i,
 390                    ARRAYGET(ao,struct ___TagDescriptor___*,ao->___cachedCode___));
 391         ARRAYSET(ao,struct ___TagDescriptor___ *,ao->___cachedCode___, NULL);
 392         if (ao->___cachedCode___==0)
 393           obj->___tags___=NULL;
 394         goto PROCESSCLEAR;
 395       }
 396     }
 397   }
 398  PROCESSCLEAR:
 399   {
 400     struct ___Object___ *tagset=tagd->flagptr;
 401     if (tagset->type!=OBJECTARRAYTYPE) {
 402       if (tagset==obj)
 403         tagd->flagptr=NULL;
 404     } else {
 405       struct ArrayObject *ao=(struct ArrayObject *) tagset;
 406       int i;
 407       for(i=0; i<ao->___cachedCode___; i++) {
 408         struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, i);
 409         if (tobj==obj) {
 410           ao->___cachedCode___--;
 411           if (i<ao->___cachedCode___)
 412             ARRAYSET(ao, struct ___Object___ *, i,
 413                      ARRAYGET(ao, struct ___Object___ *, ao->___cachedCode___));
 414           ARRAYSET(ao, struct ___Object___ *, ao->___cachedCode___, NULL);
 415           if (ao->___cachedCode___==0)
 416             tagd->flagptr=NULL;
 417           goto ENDCLEAR;
 418         }
 419       }
 420     }
 421   }
 422  ENDCLEAR:
 423   return;
 424 }
 425
 426 /* This function allocates a new tag. */
 427 #ifdef MULTICORE_GC
 428 struct ___TagDescriptor___ * allocate_tag(void *ptr, int index) {
 429   struct ___TagDescriptor___ * v=
 430     (struct ___TagDescriptor___ *) FREEMALLOC((struct garbagelist *) ptr,
 431                                               classsize[TAGTYPE]);
 432 #else
 433 struct ___TagDescriptor___ * allocate_tag(int index) {
 434   struct ___TagDescriptor___ * v=FREEMALLOC(classsize[TAGTYPE]);
 435 #endif
 436   v->type=TAGTYPE;
 437   v->flag=index;
 438   return v;
 439 }
 440
 441 /* This function updates the flag for object ptr.  It or's the flag
 442    with the or mask and and's it with the andmask. */
 443
 444 void flagbody(struct ___Object___ *ptr, int flag, struct parameterwrapper ** queues, int length, bool isnew);
 445
 446 int flagcomp(const int *val1, const int *val2) {
 447   return (*val1)-(*val2);
 448 }
 449
 450 void flagorand(void * ptr, int ormask, int andmask, struct parameterwrapper ** queues, int length) {
 451   int oldflag=((int *)ptr)[2]; // the flag field is now the third one
 452   int flag=ormask|oldflag;
 453   flag&=andmask;
 454   flagbody(ptr, flag, queues, length, false);
 455 }
 456
 457 bool intflagorand(void * ptr, int ormask, int andmask) {
 458   int oldflag=((int *)ptr)[2]; // the flag field is the third one
 459   int flag=ormask|oldflag;
 460   flag&=andmask;
 461   if (flag==oldflag)   /* Don't do anything */
 462     return false;
 463   else {
 464     flagbody(ptr, flag, NULL, 0, false);
 465     return true;
 466   }
 467 }
 468
 469 void flagorandinit(void * ptr, int ormask, int andmask) {
 470   int oldflag=((int *)ptr)[2]; // the flag field is the third one
 471   int flag=ormask|oldflag;
 472   flag&=andmask;
 473   flagbody(ptr,flag,NULL,0,true);
 474 }
 475
 476 void flagbody(struct ___Object___ *ptr,
 477               int flag,
 478               struct parameterwrapper ** vqueues,
 479               int vlength,
 480               bool isnew) {
 481   struct parameterwrapper * flagptr = NULL;
 482   int i = 0;
 483   struct parameterwrapper ** queues = vqueues;
 484   int length = vlength;
 485   int next;
 486   int UNUSED, UNUSED2;
 487   int * enterflags = NULL;
 488   if((!isnew) && (queues == NULL)) {
 489     if(BAMBOO_NUM_OF_CORE < NUMCORESACTIVE) {
 490       queues = objectqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 491       length = numqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 492     } else {
 493       return;
 494     }
 495   }
 496   ptr->flag=flag;
 497
 498   /*Remove object from all queues */
 499   for(i = 0; i < length; i++) {
 500     flagptr = queues[i];
 501     ObjectHashget(flagptr->objectset, (int) ptr, (int *) &next,
 502                   (int *) &enterflags, &UNUSED, &UNUSED2);
 503     ObjectHashremove(flagptr->objectset, (int)ptr);
 504     if (enterflags!=NULL)
 505       RUNFREE(enterflags);
 506   }
 507 }
 508
 509 void enqueueObject(void * vptr,
 510                    struct parameterwrapper ** vqueues,
 511                    int vlength) {
 512   struct ___Object___ *ptr = (struct ___Object___ *)vptr;
 513
 514   {
 515     struct parameterwrapper * parameter=NULL;
 516     int j;
 517     int i;
 518     struct parameterwrapper * prevptr=NULL;
 519     struct ___Object___ *tagptr=NULL;
 520     struct parameterwrapper ** queues = vqueues;
 521     int length = vlength;
 522     if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
 523       return;
 524     }
 525     if(queues == NULL) {
 526       queues = objectqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 527       length = numqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 528     }
 529     tagptr=ptr->___tags___;
 530
 531     /* Outer loop iterates through all parameter queues an object of
 532        this type could be in.  */
 533     for(j = 0; j < length; j++) {
 534       parameter = queues[j];
 535       /* Check tags */
 536       if (parameter->numbertags>0) {
 537         if (tagptr==NULL)
 538           goto nextloop;  //that means the object has no tag
 539         //but that param needs tag
 540         else if(tagptr->type==TAGTYPE) {     //one tag
 541           for(i=0; i<parameter->numbertags; i++) {
 542             //slotid is parameter->tagarray[2*i];
 543             int tagid=parameter->tagarray[2*i+1];
 544             if (tagid!=tagptr->flag)
 545               goto nextloop;   /*We don't have this tag */
 546           }
 547         } else {   //multiple tags
 548           struct ArrayObject * ao=(struct ArrayObject *) tagptr;
 549           for(i=0; i<parameter->numbertags; i++) {
 550             //slotid is parameter->tagarray[2*i];
 551             int tagid=parameter->tagarray[2*i+1];
 552             int j;
 553             for(j=0; j<ao->___cachedCode___; j++) {
 554               if (tagid==ARRAYGET(ao, struct ___TagDescriptor___*, j)->flag)
 555                 goto foundtag;
 556             }
 557             goto nextloop;
 558           foundtag:
 559             ;
 560           }
 561         }
 562       }
 563
 564       /* Check flags */
 565       for(i=0; i<parameter->numberofterms; i++) {
 566         int andmask=parameter->intarray[i*2];
 567         int checkmask=parameter->intarray[i*2+1];
 568         if ((ptr->flag&andmask)==checkmask) {
 569           enqueuetasks(parameter, prevptr, ptr, NULL, 0);
 570           prevptr=parameter;
 571           break;
 572         }
 573       }
 574     nextloop:
 575       ;
 576     }
 577   }
 578 }
 579
 580 void enqueueObject_I(void * vptr,
 581                      struct parameterwrapper ** vqueues,
 582                      int vlength) {
 583   struct ___Object___ *ptr = (struct ___Object___ *)vptr;
 584
 585   {
 586     struct parameterwrapper * parameter=NULL;
 587     int j;
 588     int i;
 589     struct parameterwrapper * prevptr=NULL;
 590     struct ___Object___ *tagptr=NULL;
 591     struct parameterwrapper ** queues = vqueues;
 592     int length = vlength;
 593     if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
 594       return;
 595     }
 596     if(queues == NULL) {
 597       queues = objectqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 598       length = numqueues[BAMBOO_NUM_OF_CORE][ptr->type];
 599     }
 600     tagptr=ptr->___tags___;
 601
 602     /* Outer loop iterates through all parameter queues an object of
 603        this type could be in.  */
 604     for(j = 0; j < length; j++) {
 605       parameter = queues[j];
 606       /* Check tags */
 607       if (parameter->numbertags>0) {
 608         if (tagptr==NULL)
 609           goto nextloop;      //that means the object has no tag
 610         //but that param needs tag
 611         else if(tagptr->type==TAGTYPE) {   //one tag
 612           for(i=0; i<parameter->numbertags; i++) {
 613             //slotid is parameter->tagarray[2*i];
 614             int tagid=parameter->tagarray[2*i+1];
 615             if (tagid!=tagptr->flag)
 616               goto nextloop;            /*We don't have this tag */
 617           }
 618         } else {    //multiple tags
 619           struct ArrayObject * ao=(struct ArrayObject *) tagptr;
 620           for(i=0; i<parameter->numbertags; i++) {
 621             //slotid is parameter->tagarray[2*i];
 622             int tagid=parameter->tagarray[2*i+1];
 623             int j;
 624             for(j=0; j<ao->___cachedCode___; j++) {
 625               if (tagid==ARRAYGET(ao, struct ___TagDescriptor___*, j)->flag)
 626                 goto foundtag;
 627             }
 628             goto nextloop;
 629           foundtag:
 630             ;
 631           }
 632         }
 633       }
 634
 635       /* Check flags */
 636       for(i=0; i<parameter->numberofterms; i++) {
 637         int andmask=parameter->intarray[i*2];
 638         int checkmask=parameter->intarray[i*2+1];
 639         if ((ptr->flag&andmask)==checkmask) {
 640           enqueuetasks_I(parameter, prevptr, ptr, NULL, 0);
 641           prevptr=parameter;
 642           break;
 643         }
 644       }
 645     nextloop:
 646       ;
 647     }
 648   }
 649 }
 650
 651
 652 int * getAliasLock(void ** ptrs, int length, struct RuntimeHash * tbl) {
 653 #ifdef TILERA_BME
 654   int i = 0;
 655   int locks[length];
 656   int locklen = 0;
 657   // sort all the locks required by the objs in the aliased set
 658   for(; i < length; i++) {
 659     struct ___Object___ * ptr = (struct ___Object___ *)(ptrs[i]);
 660     int lock = 0;
 661     int j = 0;
 662     if(ptr->lock == NULL) {
 663       lock = (int)(ptr);
 664     } else {
 665       lock = (int)(ptr->lock);
 666     }
 667     bool insert = true;
 668     for(j = 0; j < locklen; j++) {
 669       if(locks[j] == lock) {
 670         insert = false;
 671         break;
 672       } else if(locks[j] > lock) {
 673         break;
 674       }
 675     }
 676     if(insert) {
 677       int h = locklen;
 678       for(; h > j; h--) {
 679         locks[h] = locks[h-1];
 680       }
 681       locks[j] = lock;
 682       locklen++;
 683     }
 684   }
 685   // use the smallest lock as the shared lock for the whole set
 686   return (int *)(locks[0]);
 687 #else // TILERA_BME
 688   // TODO possible bug here!!!
 689   if(length == 0) {
 690     return (int*)(RUNMALLOC(sizeof(int)));
 691   } else {
 692     int i = 0;
 693     int locks[length];
 694     int locklen = 0;
 695     bool redirect = false;
 696     int redirectlock = 0;
 697     for(; i < length; i++) {
 698       struct ___Object___ * ptr = (struct ___Object___ *)(ptrs[i]);
 699       int lock = 0;
 700       int j = 0;
 701       if(ptr->lock == NULL) {
 702         lock = (int)(ptr);
 703       } else {
 704         lock = (int)(ptr->lock);
 705       }
 706       if(redirect) {
 707         if(lock != redirectlock) {
 708           RuntimeHashadd(tbl, lock, redirectlock);
 709         }
 710       } else {
 711         if(RuntimeHashcontainskey(tbl, lock)) {
 712           // already redirected
 713           redirect = true;
 714           RuntimeHashget(tbl, lock, &redirectlock);
 715           for(; j < locklen; j++) {
 716             if(locks[j] != redirectlock) {
 717               RuntimeHashadd(tbl, locks[j], redirectlock);
 718             }
 719           }
 720         } else {
 721           bool insert = true;
 722           for(j = 0; j < locklen; j++) {
 723             if(locks[j] == lock) {
 724               insert = false;
 725               break;
 726             } else if(locks[j] > lock) {
 727               break;
 728             }
 729           }
 730           if(insert) {
 731             int h = locklen;
 732             for(; h > j; h--) {
 733               locks[h] = locks[h-1];
 734             }
 735             locks[j] = lock;
 736             locklen++;
 737           }
 738         }
 739       }
 740     }
 741     if(redirect) {
 742       return (int *)redirectlock;
 743     } else {
 744       // use the first lock as the shared lock
 745       for(j = 1; j < locklen; j++) {
 746         if(locks[j] != locks[0]) {
 747           RuntimeHashadd(tbl, locks[j], locks[0]);
 748         }
 749       }
 750       return (int *)(locks[0]);
 751     }
 752   }
 753 #endif // TILERA_BME
 754 }
 755
 756 void addAliasLock(void * ptr, int lock) {
 757   struct ___Object___ * obj = (struct ___Object___ *)ptr;
 758   if(((int)ptr != lock) && (obj->lock != (int*)lock)) {
 759     // originally no alias lock associated or have a different alias lock
 760     // flush it as the new one
 761 #ifdef TILERA_BME
 762     while(obj->lock != NULL) {
 763       // previously have alias lock, trace the 'root' obj and redirect it
 764       obj = (struct ___Object___ *)(obj->lock);
 765     }
 766 #endif // TILERA_BME
 767     obj->lock = (int *)lock;
 768   }
 769 }
 770
 771 int enqueuetasks(struct parameterwrapper *parameter,
 772                  struct parameterwrapper *prevptr,
 773                  struct ___Object___ *ptr,
 774                  int * enterflags,
 775                  int numenterflags) {
 776   void * taskpointerarray[MAXTASKPARAMS];
 777   int j;
 778   int numiterators=parameter->task->numTotal-1;
 779   int retval=1;
 780
 781   struct taskdescriptor * task=parameter->task;
 782
 783   //this add the object to parameterwrapper
 784   ObjectHashadd(parameter->objectset, (int) ptr, 0, (int) enterflags,
 785       numenterflags, enterflags==NULL);
 786
 787   /* Add enqueued object to parameter vector */
 788   taskpointerarray[parameter->slot]=ptr;
 789
 790   /* Reset iterators */
 791   for(j=0; j<numiterators; j++) {
 792     toiReset(&parameter->iterators[j]);
 793   }
 794
 795   /* Find initial state */
 796   for(j=0; j<numiterators; j++) {
 797 backtrackinit:
 798     if(toiHasNext(&parameter->iterators[j],taskpointerarray OPTARG(failed)))
 799       toiNext(&parameter->iterators[j], taskpointerarray OPTARG(failed));
 800     else if (j>0) {
 801       /* Need to backtrack */
 802       toiReset(&parameter->iterators[j]);
 803       j--;
 804       goto backtrackinit;
 805     } else {
 806       /* Nothing to enqueue */
 807       return retval;
 808     }
 809   }
 810
 811   while(1) {
 812     /* Enqueue current state */
 813     //int launch = 0;
 814     struct taskparamdescriptor *tpd=
 815       RUNMALLOC(sizeof(struct taskparamdescriptor));
 816     tpd->task=task;
 817     tpd->numParameters=numiterators+1;
 818     tpd->parameterArray=RUNMALLOC(sizeof(void *)*(numiterators+1));
 819
 820     for(j=0; j<=numiterators; j++) {
 821       //store the actual parameters
 822       tpd->parameterArray[j]=taskpointerarray[j];
 823     }
 824     /* Enqueue task */
 825     if (!gencontains(activetasks,tpd)) {
 826       genputtable(activetasks, tpd, tpd);
 827     } else {
 828       RUNFREE(tpd->parameterArray);
 829       RUNFREE(tpd);
 830     }
 831
 832     /* This loop iterates to the next parameter combination */
 833     if (numiterators==0)
 834       return retval;
 835
 836     for(j=numiterators-1; j<numiterators; j++) {
 837 backtrackinc:
 838       if(toiHasNext(&parameter->iterators[j],taskpointerarray OPTARG(failed)))
 839         toiNext(&parameter->iterators[j], taskpointerarray OPTARG(failed));
 840       else if (j>0) {
 841         /* Need to backtrack */
 842         toiReset(&parameter->iterators[j]);
 843         j--;
 844         goto backtrackinc;
 845       } else {
 846         /* Nothing more to enqueue */
 847         return retval;
 848       }
 849     }
 850   }
 851   return retval;
 852 }
 853
 854 int enqueuetasks_I(struct parameterwrapper *parameter,
 855                    struct parameterwrapper *prevptr,
 856                    struct ___Object___ *ptr,
 857                    int * enterflags,
 858                    int numenterflags) {
 859   void * taskpointerarray[MAXTASKPARAMS];
 860   int j;
 861   int numiterators=parameter->task->numTotal-1;
 862   int retval=1;
 863
 864   struct taskdescriptor * task=parameter->task;
 865
 866   //this add the object to parameterwrapper
 867   ObjectHashadd_I(parameter->objectset, (int) ptr, 0, (int) enterflags,
 868                   numenterflags, enterflags==NULL);
 869
 870   /* Add enqueued object to parameter vector */
 871   taskpointerarray[parameter->slot]=ptr;
 872
 873   /* Reset iterators */
 874   for(j=0; j<numiterators; j++) {
 875     toiReset(&parameter->iterators[j]);
 876   }
 877
 878   /* Find initial state */
 879   for(j=0; j<numiterators; j++) {
 880 backtrackinit:
 881     if(toiHasNext(&parameter->iterators[j],taskpointerarray OPTARG(failed)))
 882       toiNext(&parameter->iterators[j], taskpointerarray OPTARG(failed));
 883     else if (j>0) {
 884       /* Need to backtrack */
 885       toiReset(&parameter->iterators[j]);
 886       j--;
 887       goto backtrackinit;
 888     } else {
 889       /* Nothing to enqueue */
 890       return retval;
 891     }
 892   }
 893
 894   while(1) {
 895     /* Enqueue current state */
 896     //int launch = 0;
 897     struct taskparamdescriptor *tpd=
 898       RUNMALLOC_I(sizeof(struct taskparamdescriptor));
 899     tpd->task=task;
 900     tpd->numParameters=numiterators+1;
 901     tpd->parameterArray=RUNMALLOC_I(sizeof(void *)*(numiterators+1));
 902
 903     for(j=0; j<=numiterators; j++) {
 904       //store the actual parameters
 905       tpd->parameterArray[j]=taskpointerarray[j];
 906     }
 907     /* Enqueue task */
 908     if (!gencontains(activetasks,tpd)) {
 909       genputtable_I(activetasks, tpd, tpd);
 910     } else {
 911       RUNFREE_I(tpd->parameterArray);
 912       RUNFREE_I(tpd);
 913     }
 914
 915     /* This loop iterates to the next parameter combination */
 916     if (numiterators==0)
 917       return retval;
 918
 919     for(j=numiterators-1; j<numiterators; j++) {
 920 backtrackinc:
 921       if(toiHasNext(&parameter->iterators[j], taskpointerarray OPTARG(failed)))
 922         toiNext(&parameter->iterators[j], taskpointerarray OPTARG(failed));
 923       else if (j>0) {
 924         /* Need to backtrack */
 925         toiReset(&parameter->iterators[j]);
 926         j--;
 927         goto backtrackinc;
 928       } else {
 929         /* Nothing more to enqueue */
 930         return retval;
 931       }
 932     }
 933   }
 934   return retval;
 935 }
 936
 937 #ifdef MULTICORE_GC
 938 #define OFFSET 2
 939 #else
 940 #define OFFSET 0
 941 #endif
 942
 943 int containstag(struct ___Object___ *ptr,
 944                 struct ___TagDescriptor___ *tag);
 945
 946 #ifndef MULTICORE_GC
 947 void releasewritelock_r(void * lock, void * redirectlock) {
 948   int targetcore = 0;
 949   int reallock = (int)lock;
 950   targetcore = (reallock >> 5) % NUMCORES;
 951
 952   if(targetcore == BAMBOO_NUM_OF_CORE) {
 953     BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
 954     // reside on this core
 955     if(!RuntimeHashcontainskey(locktbl, reallock)) {
 956       // no locks for this object, something is wrong
 957       BAMBOO_EXIT();
 958     } else {
 959       int rwlock_obj = 0;
 960       struct LockValue * lockvalue = NULL;
 961       RuntimeHashget(locktbl, reallock, &rwlock_obj);
 962       lockvalue = (struct LockValue *)rwlock_obj;
 963       lockvalue->value++;
 964       lockvalue->redirectlock = (int)redirectlock;
 965     }
 966     BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
 967     return;
 968   } else {
 969     // send lock release with redirect info msg
 970     // for 32 bit machine, the size is always 4 words
 971     send_msg_4(targetcore,REDIRECTRELEASE,1,(int)lock,(int)redirectlock,false);
 972   }
 973 }
 974 #endif
 975
 976 void executetasks() {
 977   void * taskpointerarray[MAXTASKPARAMS+OFFSET];
 978   int numparams=0;
 979   int numtotal=0;
 980   struct ___Object___ * tmpparam = NULL;
 981   struct parameterdescriptor * pd=NULL;
 982   struct parameterwrapper *pw=NULL;
 983   int j = 0;
 984   int x = 0;
 985   bool islock = true;
 986
 987   int grount = 0;
 988   int andmask=0;
 989   int checkmask=0;
 990
 991 newtask:
 992   while(hashsize(activetasks)>0) {
 993     GCCHECK(NULL);
 994
 995     /* See if there are any active tasks */
 996     int i;
 997 #ifdef ACCURATEPROFILE
 998     PROFILE_TASK_START("tpd checking");
 999 #endif
1000
1001     busystatus = true;
1002     currtpd=(struct taskparamdescriptor *) getfirstkey(activetasks);
1003     genfreekey(activetasks, currtpd);
1004
1005     numparams=currtpd->task->numParameters;
1006     numtotal=currtpd->task->numTotal;
1007
1008     // (TODO, this table should be empty after all locks are released)
1009     // reset all locks
1010     // get all required locks
1011     runtime_locklen = 0;
1012     // check which locks are needed
1013     for(i = 0; i < numparams; i++) {
1014       void * param = currtpd->parameterArray[i];
1015       int tmplock = 0;
1016       int j = 0;
1017       bool insert = true;
1018       if(((struct ___Object___ *)param)->type == STARTUPTYPE) {
1019         islock = false;
1020         taskpointerarray[i+OFFSET]=param;
1021         goto execute;
1022       }
1023       struct ___Object___ * obj = (struct ___Object___ *)param;
1024       while(obj->lock != NULL) {
1025         obj = (struct ___Object___ *)(obj->lock);
1026       }
1027       tmplock = (int)(obj);
1028       // insert into the locks array
1029       for(j = 0; j < runtime_locklen; j++) {
1030         if(runtime_locks[j].value == tmplock) {
1031           insert = false;
1032           break;
1033         } else if(runtime_locks[j].value > tmplock) {
1034           break;
1035         }
1036       }
1037       if(insert) {
1038         int h = runtime_locklen;
1039         for(; h > j; h--) {
1040           runtime_locks[h].redirectlock = runtime_locks[h-1].redirectlock;
1041           runtime_locks[h].value = runtime_locks[h-1].value;
1042         }
1043         runtime_locks[j].value = tmplock;
1044         runtime_locks[j].redirectlock = (int)param;
1045         runtime_locklen++;
1046       }
1047     }  // for(i = 0; i < numparams; i++)
1048     // grab these required locks
1049
1050     for(i = 0; i < runtime_locklen; i++) {
1051       int * lock = (int *)(runtime_locks[i].value);
1052       islock = true;
1053       // require locks for this parameter if it is not a startup object
1054       getwritelock(lock);
1055       BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1056       while(!lockflag) {
1057         BAMBOO_WAITING_FOR_LOCK(0);
1058       }
1059 #ifndef INTERRUPT
1060       if(reside) {
1061         while(BAMBOO_WAITING_FOR_LOCK(0) != -1) {
1062         }
1063       }
1064 #endif
1065       grount = lockresult;
1066
1067       lockresult = 0;
1068       lockobj = 0;
1069       lock2require = 0;
1070       lockflag = false;
1071 #ifndef INTERRUPT
1072       reside = false;
1073 #endif
1074       BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
1075
1076       if(grount == 0) {
1077         // check if has the lock already
1078         // can not get the lock, try later
1079         // release all grabbed locks for previous parameters
1080         for(j = 0; j < i; j++) {
1081           lock = (int*)(runtime_locks[j].value/*redirectlock*/);
1082           releasewritelock(lock);
1083         }
1084         genputtable(activetasks, currtpd, currtpd);
1085         if(hashsize(activetasks) == 1) {
1086           // only one task right now, wait a little while before next try
1087           int halt = 10000;
1088           while(halt--) {
1089           }
1090         }
1091 #ifdef ACCURATEPROFILE
1092         // fail, set the end of the checkTaskInfo
1093         PROFILE_TASK_END();
1094 #endif
1095         goto newtask;
1096       }
1097     }   // line 2752:  for(i = 0; i < runtime_locklen; i++)
1098
1099     /* Make sure that the parameters are still in the queues */
1100     for(i=0; i<numparams; i++) {
1101       void * parameter=currtpd->parameterArray[i];
1102
1103       // flush the object
1104       BAMBOO_CACHE_FLUSH_RANGE((int)parameter,
1105           classsize[((struct ___Object___ *)parameter)->type]);
1106       tmpparam = (struct ___Object___ *)parameter;
1107       pd=currtpd->task->descriptorarray[i];
1108       pw=(struct parameterwrapper *) pd->queue;
1109       /* Check that object is still in queue */
1110       {
1111         if (!ObjectHashcontainskey(pw->objectset, (int) parameter)) {
1112           // release grabbed locks
1113           for(j = 0; j < runtime_locklen; j++) {
1114             int * lock = (int *)(runtime_locks[j].value);
1115             releasewritelock(lock);
1116           }
1117           RUNFREE(currtpd->parameterArray);
1118           RUNFREE(currtpd);
1119           currtpd = NULL;
1120           goto newtask;
1121         }
1122       }
1123       /* Check if the object's flags still meets requirements */
1124       {
1125         int tmpi = 0;
1126         bool ismet = false;
1127         for(tmpi = 0; tmpi < pw->numberofterms; tmpi++) {
1128           andmask=pw->intarray[tmpi*2];
1129           checkmask=pw->intarray[tmpi*2+1];
1130           if((((struct ___Object___ *)parameter)->flag&andmask)==checkmask) {
1131             ismet = true;
1132             break;
1133           }
1134         }
1135         if (!ismet) {
1136           // flags are never suitable
1137           // remove this obj from the queue
1138           int next;
1139           int UNUSED, UNUSED2;
1140           int * enterflags;
1141           ObjectHashget(pw->objectset, (int) parameter, (int *) &next,
1142               (int *) &enterflags, &UNUSED, &UNUSED2);
1143           ObjectHashremove(pw->objectset, (int)parameter);
1144           if (enterflags!=NULL)
1145             RUNFREE(enterflags);
1146           // release grabbed locks
1147           for(j = 0; j < runtime_locklen; j++) {
1148             int * lock = (int *)(runtime_locks[j].value/*redirectlock*/);
1149             releasewritelock(lock);
1150           }
1151           RUNFREE(currtpd->parameterArray);
1152           RUNFREE(currtpd);
1153           currtpd = NULL;
1154 #ifdef ACCURATEPROFILE
1155           // fail, set the end of the checkTaskInfo
1156           PROFILE_TASK_END();
1157 #endif
1158           goto newtask;
1159         }   //if (!ismet)
1160       }
1161 parameterpresent:
1162       ;
1163       /* Check that object still has necessary tags */
1164       for(j=0; j<pd->numbertags; j++) {
1165         int slotid=pd->tagarray[2*j]+numparams;
1166         struct ___TagDescriptor___ *tagd=currtpd->parameterArray[slotid];
1167         if (!containstag(parameter, tagd)) {
1168           // release grabbed locks
1169           int tmpj = 0;
1170           for(tmpj = 0; tmpj < runtime_locklen; tmpj++) {
1171             int * lock = (int *)(runtime_locks[tmpj].value/*redirectlock*/);
1172             releasewritelock(lock);
1173           }
1174           RUNFREE(currtpd->parameterArray);
1175           RUNFREE(currtpd);
1176           currtpd = NULL;
1177           goto newtask;
1178         }
1179       }
1180
1181       taskpointerarray[i+OFFSET]=parameter;
1182     }   // for(i=0; i<numparams; i++)
1183     /* Copy the tags */
1184     for(; i<numtotal; i++) {
1185       taskpointerarray[i+OFFSET]=currtpd->parameterArray[i];
1186     }
1187
1188     {
1189 execute:
1190       /* Actually call task */
1191 #ifdef MULTICORE_GC
1192       ((int *)taskpointerarray)[0]=currtpd->numParameters;
1193       taskpointerarray[1]=NULL;
1194 #endif
1195 #ifdef ACCURATEPROFILE
1196       // check finish, set the end of the checkTaskInfo
1197       PROFILE_TASK_END();
1198 #endif
1199       PROFILE_TASK_START(currtpd->task->name);
1200
1201       ((void (*)(void **))currtpd->task->taskptr)(taskpointerarray);
1202
1203 #ifdef ACCURATEPROFILE
1204       // task finish, set the end of the checkTaskInfo
1205       PROFILE_TASK_END();
1206       // new a PostTaskInfo for the post-task execution
1207       PROFILE_TASK_START("post task execution");
1208 #endif
1209
1210       if(islock) {
1211         for(i = runtime_locklen; i>0; i--) {
1212           void * ptr = (void *)(runtime_locks[i-1].redirectlock);
1213           int * lock = (int *)(runtime_locks[i-1].value);
1214 #ifndef MULTICORE_GC
1215 #ifndef TILERA_BME
1216           if(RuntimeHashcontainskey(lockRedirectTbl, (int)lock)) {
1217             int redirectlock;
1218             RuntimeHashget(lockRedirectTbl, (int)lock, &redirectlock);
1219             RuntimeHashremovekey(lockRedirectTbl, (int)lock);
1220             releasewritelock_r(lock, (int *)redirectlock);
1221           } else {
1222 #else
1223           {
1224 #endif
1225 #else
1226           {
1227 #endif
1228             releasewritelock(lock); // ptr
1229           }
1230         }
1231       }     // if(islock)
1232
1233       // post task execution finish, set the end of the postTaskInfo
1234       PROFILE_TASK_END();
1235
1236       // Free up task parameter descriptor
1237       RUNFREE(currtpd->parameterArray);
1238       RUNFREE(currtpd);
1239       currtpd = NULL;
1240     }
1241   } //  while(hashsize(activetasks)>0)
1242 }
1243
1244 /* This function processes an objects tags */
1245 void processtags(struct parameterdescriptor *pd,
1246                  int index,
1247                  struct parameterwrapper *parameter,
1248                  int * iteratorcount,
1249                  int *statusarray,
1250                  int numparams) {
1251   int i;
1252
1253   for(i=0; i<pd->numbertags; i++) {
1254     int slotid=pd->tagarray[2*i];
1255     int tagid=pd->tagarray[2*i+1];
1256
1257     if (statusarray[slotid+numparams]==0) {
1258       parameter->iterators[*iteratorcount].istag=1;
1259       parameter->iterators[*iteratorcount].tagid=tagid;
1260       parameter->iterators[*iteratorcount].slot=slotid+numparams;
1261       parameter->iterators[*iteratorcount].tagobjectslot=index;
1262       statusarray[slotid+numparams]=1;
1263       (*iteratorcount)++;
1264     }
1265   }
1266 }
1267
1268 void processobject(struct parameterwrapper *parameter,
1269                    int index,
1270                    struct parameterdescriptor *pd,
1271                    int *iteratorcount,
1272                    int * statusarray,
1273                    int numparams) {
1274   int i;
1275   int tagcount=0;
1276   struct ObjectHash * objectset=
1277     ((struct parameterwrapper *)pd->queue)->objectset;
1278
1279   parameter->iterators[*iteratorcount].istag=0;
1280   parameter->iterators[*iteratorcount].slot=index;
1281   parameter->iterators[*iteratorcount].objectset=objectset;
1282   statusarray[index]=1;
1283
1284   for(i=0; i<pd->numbertags; i++) {
1285     int slotid=pd->tagarray[2*i];
1286     if (statusarray[slotid+numparams]!=0) {
1287       /* This tag has already been enqueued, use it to narrow search */
1288       parameter->iterators[*iteratorcount].tagbindings[tagcount]=
1289         slotid+numparams;
1290       tagcount++;
1291     }
1292   }
1293   parameter->iterators[*iteratorcount].numtags=tagcount;
1294
1295   (*iteratorcount)++;
1296 }
1297
1298 /* This function builds the iterators for a task & parameter */
1299
1300 void builditerators(struct taskdescriptor * task,
1301                     int index,
1302                     struct parameterwrapper * parameter) {
1303   int statusarray[MAXTASKPARAMS];
1304   int i;
1305   int numparams=task->numParameters;
1306   int iteratorcount=0;
1307   for(i=0; i<MAXTASKPARAMS; i++) statusarray[i]=0;
1308
1309   statusarray[index]=1; /* Initial parameter */
1310   /* Process tags for initial iterator */
1311
1312   processtags(task->descriptorarray[index], index, parameter,
1313               &iteratorcount, statusarray, numparams);
1314
1315   while(1) {
1316 loopstart:
1317     /* Check for objects with existing tags */
1318     for(i=0; i<numparams; i++) {
1319       if (statusarray[i]==0) {
1320         struct parameterdescriptor *pd=task->descriptorarray[i];
1321         int j;
1322         for(j=0; j<pd->numbertags; j++) {
1323           int slotid=pd->tagarray[2*j];
1324           if(statusarray[slotid+numparams]!=0) {
1325             processobject(parameter,i,pd,&iteratorcount,
1326                           statusarray,numparams);
1327             processtags(pd,i,parameter,&iteratorcount,statusarray,numparams);
1328             goto loopstart;
1329           }
1330         }
1331       }
1332     }
1333
1334     /* Next do objects w/ unbound tags*/
1335
1336     for(i=0; i<numparams; i++) {
1337       if (statusarray[i]==0) {
1338         struct parameterdescriptor *pd=task->descriptorarray[i];
1339         if (pd->numbertags>0) {
1340           processobject(parameter,i,pd,&iteratorcount,statusarray,numparams);
1341           processtags(pd,i,parameter,&iteratorcount,statusarray,numparams);
1342           goto loopstart;
1343         }
1344       }
1345     }
1346
1347     /* Nothing with a tag enqueued */
1348
1349     for(i=0; i<numparams; i++) {
1350       if (statusarray[i]==0) {
1351         struct parameterdescriptor *pd=task->descriptorarray[i];
1352         processobject(parameter,i,pd,&iteratorcount,statusarray,numparams);
1353         processtags(pd,i,parameter,&iteratorcount,statusarray,numparams);
1354         goto loopstart;
1355       }
1356     }
1357
1358     /* Nothing left */
1359     return;
1360   }
1361 }
1362
1363 void printdebug() {
1364   int i;
1365   int j;
1366   if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
1367     return;
1368   }
1369   for(i=0; i<numtasks[BAMBOO_NUM_OF_CORE]; i++) {
1370     struct taskdescriptor * task=taskarray[BAMBOO_NUM_OF_CORE][i];
1371 #ifndef RAW
1372     printf("%s\n", task->name);
1373 #endif
1374     for(j=0; j<task->numParameters; j++) {
1375       struct parameterdescriptor *param=task->descriptorarray[j];
1376       struct parameterwrapper *parameter=param->queue;
1377       struct ObjectHash * set=parameter->objectset;
1378       struct ObjectIterator objit;
1379 #ifndef RAW
1380       printf("  Parameter %d\n", j);
1381 #endif
1382       ObjectHashiterator(set, &objit);
1383       while(ObjhasNext(&objit)) {
1384         struct ___Object___ * obj=(struct ___Object___ *)Objkey(&objit);
1385         struct ___Object___ * tagptr=obj->___tags___;
1386         int nonfailed=Objdata4(&objit);
1387         int numflags=Objdata3(&objit);
1388         int flags=Objdata2(&objit);
1389         Objnext(&objit);
1390 #ifndef RAW
1391         printf("    Contains %lx\n", obj);
1392         printf("      flag=%d\n", obj->flag);
1393 #endif
1394         if (tagptr==NULL) {
1395         } else if (tagptr->type==TAGTYPE) {
1396 #ifndef RAW
1397           printf("      tag=%lx\n",tagptr);
1398 #endif
1399         } else {
1400           int tagindex=0;
1401           struct ArrayObject *ao=(struct ArrayObject *)tagptr;
1402           for(; tagindex<ao->___cachedCode___; tagindex++) {
1403 #ifndef RAW
1404             printf("      tag=%lx\n",ARRAYGET(ao,struct ___TagDescriptor___*, tagindex));
1405 #else
1406             ;
1407 #endif
1408           }
1409         }
1410       }
1411     }
1412   }
1413 }
1414
1415 /* This function processes the task information to create queues for
1416    each parameter type. */
1417 void processtasks() {
1418   int i;
1419   if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
1420     return;
1421   }
1422   for(i=0; i<numtasks[BAMBOO_NUM_OF_CORE]; i++) {
1423     struct taskdescriptor * task=taskarray[BAMBOO_NUM_OF_CORE][i];
1424     int j;
1425
1426     /* Build objectsets */
1427     for(j=0; j<task->numParameters; j++) {
1428       struct parameterdescriptor *param=task->descriptorarray[j];
1429       struct parameterwrapper *parameter=param->queue;
1430       parameter->objectset=allocateObjectHash(10);
1431       parameter->task=task;
1432     }
1433
1434     /* Build iterators for parameters */
1435     for(j=0; j<task->numParameters; j++) {
1436       struct parameterdescriptor *param=task->descriptorarray[j];
1437       struct parameterwrapper *parameter=param->queue;
1438       builditerators(task, j, parameter);
1439     }
1440   }
1441 }
1442
1443 void toiReset(struct tagobjectiterator * it) {
1444   if (it->istag) {
1445     it->tagobjindex=0;
1446   } else if (it->numtags>0) {
1447     it->tagobjindex=0;
1448   } else {
1449     ObjectHashiterator(it->objectset, &it->it);
1450   }
1451 }
1452
1453 int toiHasNext(struct tagobjectiterator *it,
1454                void ** objectarray OPTARG(int * failed)) {
1455   if (it->istag) {
1456     /* Iterate tag */
1457     /* Get object with tags */
1458     struct ___Object___ *obj=objectarray[it->tagobjectslot];
1459     struct ___Object___ *tagptr=obj->___tags___;
1460     if (tagptr->type==TAGTYPE) {
1461       if ((it->tagobjindex==0)&& /* First object */
1462                   (it->tagid==((struct ___TagDescriptor___ *)tagptr)->flag)) /* Right tag type */
1463                 return 1;
1464           else
1465                 return 0;
1466     } else {
1467       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
1468       int tagindex=it->tagobjindex;
1469       for(; tagindex<ao->___cachedCode___; tagindex++) {
1470                 struct ___TagDescriptor___ *td=
1471                   ARRAYGET(ao, struct ___TagDescriptor___ *, tagindex);
1472                 if (td->flag==it->tagid) {
1473                   it->tagobjindex=tagindex; /* Found right type of tag */
1474                   return 1;
1475                 }
1476       }
1477       return 0;
1478     }
1479   } else if (it->numtags>0) {
1480     /* Use tags to locate appropriate objects */
1481     struct ___TagDescriptor___ *tag=objectarray[it->tagbindings[0]];
1482     struct ___Object___ *objptr=tag->flagptr;
1483     int i;
1484     if (objptr->type!=OBJECTARRAYTYPE) {
1485       if (it->tagobjindex>0)
1486         return 0;
1487       if (!ObjectHashcontainskey(it->objectset, (int) objptr))
1488         return 0;
1489       for(i=1; i<it->numtags; i++) {
1490         struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
1491         if (!containstag(objptr,tag2))
1492           return 0;
1493       }
1494       return 1;
1495     } else {
1496       struct ArrayObject *ao=(struct ArrayObject *) objptr;
1497       int tagindex;
1498       int i;
1499       for(tagindex=it->tagobjindex;tagindex<ao->___cachedCode___;tagindex++){
1500         struct ___Object___ *objptr=
1501           ARRAYGET(ao,struct ___Object___*,tagindex);
1502         if (!ObjectHashcontainskey(it->objectset, (int) objptr))
1503           continue;
1504         for(i=1; i<it->numtags; i++) {
1505           struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
1506           if (!containstag(objptr,tag2))
1507             goto nexttag;
1508         }
1509         it->tagobjindex=tagindex;
1510         return 1;
1511       nexttag:
1512         ;
1513       }
1514       it->tagobjindex=tagindex;
1515       return 0;
1516     }
1517   } else {
1518     return ObjhasNext(&it->it);
1519   }
1520 }
1521
1522 int containstag(struct ___Object___ *ptr,
1523                 struct ___TagDescriptor___ *tag) {
1524   int j;
1525   struct ___Object___ * objptr=tag->flagptr;
1526   if (objptr->type==OBJECTARRAYTYPE) {
1527     struct ArrayObject *ao=(struct ArrayObject *)objptr;
1528     for(j=0; j<ao->___cachedCode___; j++) {
1529       if (ptr==ARRAYGET(ao, struct ___Object___*, j)) {
1530         return 1;
1531       }
1532     }
1533     return 0;
1534   } else {
1535     return objptr==ptr;
1536   }
1537 }
1538
1539 void toiNext(struct tagobjectiterator *it,
1540              void ** objectarray OPTARG(int * failed)) {
1541   /* hasNext has all of the intelligence */
1542   if(it->istag) {
1543     /* Iterate tag */
1544     /* Get object with tags */
1545     struct ___Object___ *obj=objectarray[it->tagobjectslot];
1546     struct ___Object___ *tagptr=obj->___tags___;
1547     if (tagptr->type==TAGTYPE) {
1548       it->tagobjindex++;
1549       objectarray[it->slot]=tagptr;
1550     } else {
1551       struct ArrayObject *ao=(struct ArrayObject *) tagptr;
1552       objectarray[it->slot]=
1553         ARRAYGET(ao, struct ___TagDescriptor___ *, it->tagobjindex++);
1554     }
1555   } else if (it->numtags>0) {
1556     /* Use tags to locate appropriate objects */
1557     struct ___TagDescriptor___ *tag=objectarray[it->tagbindings[0]];
1558     struct ___Object___ *objptr=tag->flagptr;
1559     if (objptr->type!=OBJECTARRAYTYPE) {
1560       it->tagobjindex++;
1561       objectarray[it->slot]=objptr;
1562     } else {
1563       struct ArrayObject *ao=(struct ArrayObject *) objptr;
1564       objectarray[it->slot]=
1565         ARRAYGET(ao, struct ___Object___ *, it->tagobjindex++);
1566     }
1567   } else {
1568     /* Iterate object */
1569     objectarray[it->slot]=(void *)Objkey(&it->it);
1570     Objnext(&it->it);
1571   }
1572 }
1573 #endif