3 #include "multicoreruntime.h"
4 #include "multicoretaskprofile.h"
5 #include "multicoretask.h"
8 #define INLINE inline __attribute__((always_inline))
11 // data structures for task invocation
12 struct genhashtable * activetasks;
13 struct taskparamdescriptor * currtpd;
14 struct LockValue runtime_locks[MAXTASKPARAMS];
17 // specific functions used inside critical sections
18 void enqueueObject_I(void * ptr,
19 struct parameterwrapper ** queues,
21 int enqueuetasks_I(struct parameterwrapper *parameter,
22 struct parameterwrapper *prevptr,
23 struct ___Object___ *ptr,
27 INLINE void initlocktable() {
31 // create the lock table, lockresult table and obj queue
34 (struct RuntimeNode **) RUNMALLOC_I(sizeof(struct RuntimeNode *)*20);
35 /* Set allocation blocks*/
36 locktable.listhead=NULL;
37 locktable.listtail=NULL;
39 locktable.numelements = 0;
44 lockRedirectTbl = allocateRuntimeHash_I(20);
45 objRedirectLockTbl = allocateRuntimeHash_I(20);
49 INLINE void dislocktable() {
53 freeRuntimeHash(lockRedirectTbl);
54 freeRuntimeHash(objRedirectLockTbl);
55 RUNFREE(locktable.bucket);
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
64 totransobjqueue = createQueue_I();
68 for(int i = 0; i < MAXTASKPARAMS; i++) {
69 runtime_locks[i].redirectlock = 0;
70 runtime_locks[i].value = 0;
74 INIT_TASKPROFILE_DATA();
77 INLINE void distaskdata() {
78 if(activetasks != NULL) {
79 genfreehashtable(activetasks);
82 RUNFREE(currtpd->parameterArray);
89 INLINE bool checkObjQueue() {
91 struct transObjInfo * objInfo = NULL;
94 #ifdef ACCURATEPROFILE
95 PROFILE_TASK_START("objqueue checking");
98 while(!isEmpty(&objqueue)) {
100 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
102 objInfo = (struct transObjInfo *)getItem(&objqueue);
103 obj = objInfo->objptr;
104 // grab lock and flush the obj
106 struct ___Object___ * tmpobj = (struct ___Object___ *)obj;
107 while(tmpobj->lock != NULL) {
108 tmpobj = (struct ___Object___ *)(tmpobj->lock);
110 getwritelock_I(tmpobj);
112 BAMBOO_WAITING_FOR_LOCK_I();
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);
138 releasewritelock_I(tmpobj);
139 RUNFREE_I(objInfo->queues);
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);
158 qitem = getNextQueueItem(prev);
160 // try to execute active tasks already enqueued first
161 addNewItem_I(&objqueue, objInfo);
163 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
166 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
169 #ifdef ACCURATEPROFILE
176 struct ___createstartupobject____I_locals {
179 struct ___StartupObject___ * ___startupobject___;
180 struct ArrayObject * ___stringarray___;
183 void createstartupobject(int argc,
187 /* Allocate startup object */
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;
198 struct ___StartupObject___ *startupobject=
199 (struct ___StartupObject___*) allocate_new(STARTUPTYPE);
200 struct ArrayObject * stringarray=
201 allocate_newarray(STRINGARRAYTYPE, argc-1);
203 /* Build array of strings */
204 startupobject->___parameters___=stringarray;
205 for(i=1; i<argc; i++) {
206 int length=strlen(argv[i]);
208 struct ___String___ *newstring=NewString(&___locals___, argv[i],length);
210 struct ___String___ *newstring=NewString(argv[i],length);
212 ((void **)(((char *)&stringarray->___length___)+sizeof(int)))[i-1]=
216 startupobject->version = 0;
217 startupobject->lock = NULL;
219 /* Set initialized flag for startup object */
220 flagorandinit(startupobject,1,0xFFFFFFFF);
221 enqueueObject(startupobject, NULL, 0);
222 BAMBOO_CACHE_FLUSH_ALL();
225 int hashCodetpd(struct taskparamdescriptor *ftd) {
226 int hash=(int)ftd->task;
228 for(i=0; i<ftd->numParameters; i++) {
229 hash^=(int)ftd->parameterArray[i];
234 int comparetpd(struct taskparamdescriptor *ftd1,
235 struct taskparamdescriptor *ftd2) {
237 if (ftd1->task!=ftd2->task)
239 for(i=0; i<ftd1->numParameters; i++)
240 if(ftd1->parameterArray[i]!=ftd2->parameterArray[i])
245 /* This function sets a tag. */
247 void tagset(void *ptr,
248 struct ___Object___ * obj,
249 struct ___TagDescriptor___ * tagd) {
251 void tagset(struct ___Object___ * obj,
252 struct ___TagDescriptor___ * tagd) {
254 struct ArrayObject * ao=NULL;
255 struct ___Object___ * tagptr=obj->___tags___;
257 obj->___tags___=(struct ___Object___ *)tagd;
259 /* Have to check if it is already set */
260 if (tagptr->type==TAGTYPE) {
261 struct ___TagDescriptor___ * td=(struct ___TagDescriptor___ *) tagptr;
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___;
273 ao=allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL);
276 ARRAYSET(ao, struct ___TagDescriptor___ *, 0, td);
277 ARRAYSET(ao, struct ___TagDescriptor___ *, 1, tagd);
278 obj->___tags___=(struct ___Object___ *) ao;
279 ao->___cachedCode___=2;
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);
291 if (ao->___cachedCode___<ao->___length___) {
292 ARRAYSET(ao, struct ___TagDescriptor___ *,ao->___cachedCode___,tagd);
293 ao->___cachedCode___++;
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___;
304 struct ArrayObject * aonew=
305 allocate_newarray(TAGARRAYTYPE,TAGARRAYINTERVAL+ao->___length___);
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));
313 ARRAYSET(aonew, struct ___TagDescriptor___ *, ao->___length___,tagd);
319 struct ___Object___ * tagset=tagd->flagptr;
322 } else if (tagset->type!=OBJECTARRAYTYPE) {
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];
330 struct ArrayObject * ao=
331 allocate_newarray(OBJECTARRAYTYPE,OBJECTARRAYINTERVAL);
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;
338 struct ArrayObject *ao=(struct ArrayObject *) tagset;
339 if (ao->___cachedCode___<ao->___length___) {
340 ARRAYSET(ao, struct ___Object___*, ao->___cachedCode___++, obj);
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;
352 struct ArrayObject * aonew=allocate_newarray(OBJECTARRAYTYPE,
353 OBJECTARRAYINTERVAL+ao->___length___);
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));
360 ARRAYSET(aonew, struct ___Object___ *, ao->___cachedCode___, obj);
361 tagd->flagptr=(struct ___Object___ *) aonew;
367 /* This function clears a tag. */
369 void tagclear(void *ptr, struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
371 void tagclear(struct ___Object___ * obj, struct ___TagDescriptor___ * tagd) {
373 /* We'll assume that tag is alway there.
374 Need to statically check for this of course. */
375 struct ___Object___ * tagptr=obj->___tags___;
377 if (tagptr->type==TAGTYPE) {
378 if ((struct ___TagDescriptor___ *)tagptr==tagd)
379 obj->___tags___=NULL;
381 struct ArrayObject *ao=(struct ArrayObject *) tagptr;
383 for(i=0; i<ao->___cachedCode___; i++) {
384 struct ___TagDescriptor___ * td=
385 ARRAYGET(ao, struct ___TagDescriptor___ *, i);
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;
400 struct ___Object___ *tagset=tagd->flagptr;
401 if (tagset->type!=OBJECTARRAYTYPE) {
405 struct ArrayObject *ao=(struct ArrayObject *) tagset;
407 for(i=0; i<ao->___cachedCode___; i++) {
408 struct ___Object___ * tobj=ARRAYGET(ao, struct ___Object___ *, i);
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)
426 /* This function allocates a new tag. */
428 struct ___TagDescriptor___ * allocate_tag(void *ptr, int index) {
429 struct ___TagDescriptor___ * v=
430 (struct ___TagDescriptor___ *) FREEMALLOC((struct garbagelist *) ptr,
433 struct ___TagDescriptor___ * allocate_tag(int index) {
434 struct ___TagDescriptor___ * v=FREEMALLOC(classsize[TAGTYPE]);
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. */
444 void flagbody(struct ___Object___ *ptr, int flag, struct parameterwrapper ** queues, int length, bool isnew);
446 int flagcomp(const int *val1, const int *val2) {
447 return (*val1)-(*val2);
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;
454 flagbody(ptr, flag, queues, length, false);
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;
461 if (flag==oldflag) /* Don't do anything */
464 flagbody(ptr, flag, NULL, 0, false);
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;
473 flagbody(ptr,flag,NULL,0,true);
476 void flagbody(struct ___Object___ *ptr,
478 struct parameterwrapper ** vqueues,
481 struct parameterwrapper * flagptr = NULL;
483 struct parameterwrapper ** queues = vqueues;
484 int length = vlength;
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];
498 /*Remove object from all queues */
499 for(i = 0; i < length; i++) {
501 ObjectHashget(flagptr->objectset, (int) ptr, (int *) &next,
502 (int *) &enterflags, &UNUSED, &UNUSED2);
503 ObjectHashremove(flagptr->objectset, (int)ptr);
504 if (enterflags!=NULL)
509 void enqueueObject(void * vptr,
510 struct parameterwrapper ** vqueues,
512 struct ___Object___ *ptr = (struct ___Object___ *)vptr;
515 struct parameterwrapper * parameter=NULL;
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) {
526 queues = objectqueues[BAMBOO_NUM_OF_CORE][ptr->type];
527 length = numqueues[BAMBOO_NUM_OF_CORE][ptr->type];
529 tagptr=ptr->___tags___;
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];
536 if (parameter->numbertags>0) {
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 */
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];
553 for(j=0; j<ao->___cachedCode___; j++) {
554 if (tagid==ARRAYGET(ao, struct ___TagDescriptor___*, j)->flag)
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);
580 void enqueueObject_I(void * vptr,
581 struct parameterwrapper ** vqueues,
583 struct ___Object___ *ptr = (struct ___Object___ *)vptr;
586 struct parameterwrapper * parameter=NULL;
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) {
597 queues = objectqueues[BAMBOO_NUM_OF_CORE][ptr->type];
598 length = numqueues[BAMBOO_NUM_OF_CORE][ptr->type];
600 tagptr=ptr->___tags___;
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];
607 if (parameter->numbertags>0) {
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 */
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];
624 for(j=0; j<ao->___cachedCode___; j++) {
625 if (tagid==ARRAYGET(ao, struct ___TagDescriptor___*, j)->flag)
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);
652 int * getAliasLock(void ** ptrs, int length, struct RuntimeHash * tbl) {
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]);
662 if(ptr->lock == NULL) {
665 lock = (int)(ptr->lock);
668 for(j = 0; j < locklen; j++) {
669 if(locks[j] == lock) {
672 } else if(locks[j] > lock) {
679 locks[h] = locks[h-1];
685 // use the smallest lock as the shared lock for the whole set
686 return (int *)(locks[0]);
688 // TODO possible bug here!!!
690 return (int*)(RUNMALLOC(sizeof(int)));
695 bool redirect = false;
696 int redirectlock = 0;
697 for(; i < length; i++) {
698 struct ___Object___ * ptr = (struct ___Object___ *)(ptrs[i]);
701 if(ptr->lock == NULL) {
704 lock = (int)(ptr->lock);
707 if(lock != redirectlock) {
708 RuntimeHashadd(tbl, lock, redirectlock);
711 if(RuntimeHashcontainskey(tbl, lock)) {
712 // already redirected
714 RuntimeHashget(tbl, lock, &redirectlock);
715 for(; j < locklen; j++) {
716 if(locks[j] != redirectlock) {
717 RuntimeHashadd(tbl, locks[j], redirectlock);
722 for(j = 0; j < locklen; j++) {
723 if(locks[j] == lock) {
726 } else if(locks[j] > lock) {
733 locks[h] = locks[h-1];
742 return (int *)redirectlock;
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]);
750 return (int *)(locks[0]);
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
762 while(obj->lock != NULL) {
763 // previously have alias lock, trace the 'root' obj and redirect it
764 obj = (struct ___Object___ *)(obj->lock);
767 obj->lock = (int *)lock;
771 int enqueuetasks(struct parameterwrapper *parameter,
772 struct parameterwrapper *prevptr,
773 struct ___Object___ *ptr,
776 void * taskpointerarray[MAXTASKPARAMS];
778 int numiterators=parameter->task->numTotal-1;
781 struct taskdescriptor * task=parameter->task;
783 //this add the object to parameterwrapper
784 ObjectHashadd(parameter->objectset, (int) ptr, 0, (int) enterflags,
785 numenterflags, enterflags==NULL);
787 /* Add enqueued object to parameter vector */
788 taskpointerarray[parameter->slot]=ptr;
790 /* Reset iterators */
791 for(j=0; j<numiterators; j++) {
792 toiReset(¶meter->iterators[j]);
795 /* Find initial state */
796 for(j=0; j<numiterators; j++) {
798 if(toiHasNext(¶meter->iterators[j],taskpointerarray OPTARG(failed)))
799 toiNext(¶meter->iterators[j], taskpointerarray OPTARG(failed));
801 /* Need to backtrack */
802 toiReset(¶meter->iterators[j]);
806 /* Nothing to enqueue */
812 /* Enqueue current state */
814 struct taskparamdescriptor *tpd=
815 RUNMALLOC(sizeof(struct taskparamdescriptor));
817 tpd->numParameters=numiterators+1;
818 tpd->parameterArray=RUNMALLOC(sizeof(void *)*(numiterators+1));
820 for(j=0; j<=numiterators; j++) {
821 //store the actual parameters
822 tpd->parameterArray[j]=taskpointerarray[j];
825 if (!gencontains(activetasks,tpd)) {
826 genputtable(activetasks, tpd, tpd);
828 RUNFREE(tpd->parameterArray);
832 /* This loop iterates to the next parameter combination */
836 for(j=numiterators-1; j<numiterators; j++) {
838 if(toiHasNext(¶meter->iterators[j],taskpointerarray OPTARG(failed)))
839 toiNext(¶meter->iterators[j], taskpointerarray OPTARG(failed));
841 /* Need to backtrack */
842 toiReset(¶meter->iterators[j]);
846 /* Nothing more to enqueue */
854 int enqueuetasks_I(struct parameterwrapper *parameter,
855 struct parameterwrapper *prevptr,
856 struct ___Object___ *ptr,
859 void * taskpointerarray[MAXTASKPARAMS];
861 int numiterators=parameter->task->numTotal-1;
864 struct taskdescriptor * task=parameter->task;
866 //this add the object to parameterwrapper
867 ObjectHashadd_I(parameter->objectset, (int) ptr, 0, (int) enterflags,
868 numenterflags, enterflags==NULL);
870 /* Add enqueued object to parameter vector */
871 taskpointerarray[parameter->slot]=ptr;
873 /* Reset iterators */
874 for(j=0; j<numiterators; j++) {
875 toiReset(¶meter->iterators[j]);
878 /* Find initial state */
879 for(j=0; j<numiterators; j++) {
881 if(toiHasNext(¶meter->iterators[j],taskpointerarray OPTARG(failed)))
882 toiNext(¶meter->iterators[j], taskpointerarray OPTARG(failed));
884 /* Need to backtrack */
885 toiReset(¶meter->iterators[j]);
889 /* Nothing to enqueue */
895 /* Enqueue current state */
897 struct taskparamdescriptor *tpd=
898 RUNMALLOC_I(sizeof(struct taskparamdescriptor));
900 tpd->numParameters=numiterators+1;
901 tpd->parameterArray=RUNMALLOC_I(sizeof(void *)*(numiterators+1));
903 for(j=0; j<=numiterators; j++) {
904 //store the actual parameters
905 tpd->parameterArray[j]=taskpointerarray[j];
908 if (!gencontains(activetasks,tpd)) {
909 genputtable_I(activetasks, tpd, tpd);
911 RUNFREE_I(tpd->parameterArray);
915 /* This loop iterates to the next parameter combination */
919 for(j=numiterators-1; j<numiterators; j++) {
921 if(toiHasNext(¶meter->iterators[j], taskpointerarray OPTARG(failed)))
922 toiNext(¶meter->iterators[j], taskpointerarray OPTARG(failed));
924 /* Need to backtrack */
925 toiReset(¶meter->iterators[j]);
929 /* Nothing more to enqueue */
943 int containstag(struct ___Object___ *ptr,
944 struct ___TagDescriptor___ *tag);
947 void releasewritelock_r(void * lock, void * redirectlock) {
949 int reallock = (int)lock;
950 targetcore = (reallock >> 5) % NUMCORES;
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
960 struct LockValue * lockvalue = NULL;
961 RuntimeHashget(locktbl, reallock, &rwlock_obj);
962 lockvalue = (struct LockValue *)rwlock_obj;
964 lockvalue->redirectlock = (int)redirectlock;
966 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
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);
976 void executetasks() {
977 void * taskpointerarray[MAXTASKPARAMS+OFFSET];
980 struct ___Object___ * tmpparam = NULL;
981 struct parameterdescriptor * pd=NULL;
982 struct parameterwrapper *pw=NULL;
992 while(hashsize(activetasks)>0) {
995 /* See if there are any active tasks */
997 #ifdef ACCURATEPROFILE
998 PROFILE_TASK_START("tpd checking");
1002 currtpd=(struct taskparamdescriptor *) getfirstkey(activetasks);
1003 genfreekey(activetasks, currtpd);
1005 numparams=currtpd->task->numParameters;
1006 numtotal=currtpd->task->numTotal;
1008 // (TODO, this table should be empty after all locks are released)
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];
1018 if(((struct ___Object___ *)param)->type == STARTUPTYPE) {
1020 taskpointerarray[i+OFFSET]=param;
1023 struct ___Object___ * obj = (struct ___Object___ *)param;
1024 while(obj->lock != NULL) {
1025 obj = (struct ___Object___ *)(obj->lock);
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) {
1033 } else if(runtime_locks[j].value > tmplock) {
1038 int h = runtime_locklen;
1040 runtime_locks[h].redirectlock = runtime_locks[h-1].redirectlock;
1041 runtime_locks[h].value = runtime_locks[h-1].value;
1043 runtime_locks[j].value = tmplock;
1044 runtime_locks[j].redirectlock = (int)param;
1047 } // for(i = 0; i < numparams; i++)
1048 // grab these required locks
1050 for(i = 0; i < runtime_locklen; i++) {
1051 int * lock = (int *)(runtime_locks[i].value);
1053 // require locks for this parameter if it is not a startup object
1055 BAMBOO_ENTER_RUNTIME_MODE_FROM_CLIENT();
1057 BAMBOO_WAITING_FOR_LOCK_I();
1061 while(BAMBOO_WAITING_FOR_LOCK_I() != -1) {
1065 grount = lockresult;
1074 BAMBOO_ENTER_CLIENT_MODE_FROM_RUNTIME();
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);
1084 genputtable(activetasks, currtpd, currtpd);
1085 if(hashsize(activetasks) == 1) {
1086 // only one task right now, wait a little while before next try
1091 #ifdef ACCURATEPROFILE
1092 // fail, set the end of the checkTaskInfo
1097 } // line 2752: for(i = 0; i < runtime_locklen; i++)
1099 /* Make sure that the parameters are still in the queues */
1100 for(i=0; i<numparams; i++) {
1101 void * parameter=currtpd->parameterArray[i];
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 */
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);
1117 RUNFREE(currtpd->parameterArray);
1123 /* Check if the object's flags still meets requirements */
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) {
1136 // flags are never suitable
1137 // remove this obj from the queue
1139 int UNUSED, UNUSED2;
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);
1151 RUNFREE(currtpd->parameterArray);
1154 #ifdef ACCURATEPROFILE
1155 // fail, set the end of the checkTaskInfo
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
1170 for(tmpj = 0; tmpj < runtime_locklen; tmpj++) {
1171 int * lock = (int *)(runtime_locks[tmpj].value/*redirectlock*/);
1172 releasewritelock(lock);
1174 RUNFREE(currtpd->parameterArray);
1181 taskpointerarray[i+OFFSET]=parameter;
1182 } // for(i=0; i<numparams; i++)
1184 for(; i<numtotal; i++) {
1185 taskpointerarray[i+OFFSET]=currtpd->parameterArray[i];
1190 /* Actually call task */
1192 ((int *)taskpointerarray)[0]=currtpd->numParameters;
1193 taskpointerarray[1]=NULL;
1195 #ifdef ACCURATEPROFILE
1196 // check finish, set the end of the checkTaskInfo
1199 PROFILE_TASK_START(currtpd->task->name);
1201 ((void (*)(void **))currtpd->task->taskptr)(taskpointerarray);
1203 #ifdef ACCURATEPROFILE
1204 // task finish, set the end of the checkTaskInfo
1206 // new a PostTaskInfo for the post-task execution
1207 PROFILE_TASK_START("post task execution");
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
1216 if(RuntimeHashcontainskey(lockRedirectTbl, (int)lock)) {
1218 RuntimeHashget(lockRedirectTbl, (int)lock, &redirectlock);
1219 RuntimeHashremovekey(lockRedirectTbl, (int)lock);
1220 releasewritelock_r(lock, (int *)redirectlock);
1228 releasewritelock(lock); // ptr
1233 // post task execution finish, set the end of the postTaskInfo
1236 // Free up task parameter descriptor
1237 RUNFREE(currtpd->parameterArray);
1241 } // while(hashsize(activetasks)>0)
1244 /* This function processes an objects tags */
1245 void processtags(struct parameterdescriptor *pd,
1247 struct parameterwrapper *parameter,
1248 int * iteratorcount,
1253 for(i=0; i<pd->numbertags; i++) {
1254 int slotid=pd->tagarray[2*i];
1255 int tagid=pd->tagarray[2*i+1];
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;
1268 void processobject(struct parameterwrapper *parameter,
1270 struct parameterdescriptor *pd,
1276 struct ObjectHash * objectset=
1277 ((struct parameterwrapper *)pd->queue)->objectset;
1279 parameter->iterators[*iteratorcount].istag=0;
1280 parameter->iterators[*iteratorcount].slot=index;
1281 parameter->iterators[*iteratorcount].objectset=objectset;
1282 statusarray[index]=1;
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]=
1293 parameter->iterators[*iteratorcount].numtags=tagcount;
1298 /* This function builds the iterators for a task & parameter */
1300 void builditerators(struct taskdescriptor * task,
1302 struct parameterwrapper * parameter) {
1303 int statusarray[MAXTASKPARAMS];
1305 int numparams=task->numParameters;
1306 int iteratorcount=0;
1307 for(i=0; i<MAXTASKPARAMS; i++) statusarray[i]=0;
1309 statusarray[index]=1; /* Initial parameter */
1310 /* Process tags for initial iterator */
1312 processtags(task->descriptorarray[index], index, parameter,
1313 &iteratorcount, statusarray, numparams);
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];
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);
1334 /* Next do objects w/ unbound tags*/
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);
1347 /* Nothing with a tag enqueued */
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);
1366 if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
1369 for(i=0; i<numtasks[BAMBOO_NUM_OF_CORE]; i++) {
1370 struct taskdescriptor * task=taskarray[BAMBOO_NUM_OF_CORE][i];
1372 printf("%s\n", task->name);
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;
1380 printf(" Parameter %d\n", j);
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);
1391 printf(" Contains %lx\n", obj);
1392 printf(" flag=%d\n", obj->flag);
1395 } else if (tagptr->type==TAGTYPE) {
1397 printf(" tag=%lx\n",tagptr);
1401 struct ArrayObject *ao=(struct ArrayObject *)tagptr;
1402 for(; tagindex<ao->___cachedCode___; tagindex++) {
1404 printf(" tag=%lx\n",ARRAYGET(ao,struct ___TagDescriptor___*, tagindex));
1415 /* This function processes the task information to create queues for
1416 each parameter type. */
1417 void processtasks() {
1419 if(BAMBOO_NUM_OF_CORE > NUMCORESACTIVE - 1) {
1422 for(i=0; i<numtasks[BAMBOO_NUM_OF_CORE]; i++) {
1423 struct taskdescriptor * task=taskarray[BAMBOO_NUM_OF_CORE][i];
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;
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);
1443 void toiReset(struct tagobjectiterator * it) {
1446 } else if (it->numtags>0) {
1449 ObjectHashiterator(it->objectset, &it->it);
1453 int toiHasNext(struct tagobjectiterator *it,
1454 void ** objectarray OPTARG(int * failed)) {
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 */
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 */
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;
1484 if (objptr->type!=OBJECTARRAYTYPE) {
1485 if (it->tagobjindex>0)
1487 if (!ObjectHashcontainskey(it->objectset, (int) objptr))
1489 for(i=1; i<it->numtags; i++) {
1490 struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
1491 if (!containstag(objptr,tag2))
1496 struct ArrayObject *ao=(struct ArrayObject *) objptr;
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))
1504 for(i=1; i<it->numtags; i++) {
1505 struct ___TagDescriptor___ *tag2=objectarray[it->tagbindings[i]];
1506 if (!containstag(objptr,tag2))
1509 it->tagobjindex=tagindex;
1514 it->tagobjindex=tagindex;
1518 return ObjhasNext(&it->it);
1522 int containstag(struct ___Object___ *ptr,
1523 struct ___TagDescriptor___ *tag) {
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)) {
1539 void toiNext(struct tagobjectiterator *it,
1540 void ** objectarray OPTARG(int * failed)) {
1541 /* hasNext has all of the intelligence */
1544 /* Get object with tags */
1545 struct ___Object___ *obj=objectarray[it->tagobjectslot];
1546 struct ___Object___ *tagptr=obj->___tags___;
1547 if (tagptr->type==TAGTYPE) {
1549 objectarray[it->slot]=tagptr;
1551 struct ArrayObject *ao=(struct ArrayObject *) tagptr;
1552 objectarray[it->slot]=
1553 ARRAYGET(ao, struct ___TagDescriptor___ *, it->tagobjindex++);
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) {
1561 objectarray[it->slot]=objptr;
1563 struct ArrayObject *ao=(struct ArrayObject *) objptr;
1564 objectarray[it->slot]=
1565 ARRAYGET(ao, struct ___Object___ *, it->tagobjindex++);
1568 /* Iterate object */
1569 objectarray[it->slot]=(void *)Objkey(&it->it);