# HG changeset patch # User Me # Date 1289217521 28800 # Node ID 2845dca6a28b208a0ee4d3c511bf8f3d3d1f4e86 # Parent b6ce47a0909bc371af429a0c13db8c338703240f Updated VCilk to same VMS version as SSR, for correct blocked MM Nov 8 diff -r b6ce47a0909b -r 2845dca6a28b VCilk.h --- a/VCilk.h Sun Nov 07 06:53:21 2010 -0800 +++ b/VCilk.h Mon Nov 08 03:58:41 2010 -0800 @@ -13,9 +13,19 @@ #include "VMS/Hash_impl/PrivateHash.h" #include "VMS/VMS.h" + + /*This header defines everything specific to the VCilk semantic plug-in */ + +//=========================================================================== +#define NUM_STRUCS_IN_SEM_ENV 1000 + +//=========================================================================== typedef struct _VCilkSemReq VCilkSemReq; +typedef void (*PtrToAtomicFn ) ( void * ); //executed atomically in master + +//=========================================================================== /*Semantic layer-specific data sent inside a request from lib called in app @@ -25,35 +35,71 @@ { syncReq = 1, mallocReq, - freeReq + freeReq, + singleton, + atomic, + trans_start, + trans_end }; struct _VCilkSemReq { enum VCilkReqType reqType; VirtProcr *requestingPr; + int32 sizeToMalloc; void *ptrToFree; + VirtProcrFnPtr fnPtr; void *initData; int32 coreToSpawnOnto; + + int32 singletonID; + void *endJumpPt; + + PtrToAtomicFn fnToExecInMaster; + void *dataForFn; + + int32 transID; } /* VCilkSemReq */; typedef struct { + VirtProcr *VPCurrentlyExecuting; + PrivQueueStruc *waitingVPQ; + } +VCilkTrans; + +typedef struct + { PrivQueueStruc **readyVPQs; HashTable *commHashTbl; int32 numVirtPr; int32 nextCoreToGetNewPr; int32 primitiveStartTime; + + //fix limit on num with dynArray + int32 singletonHasBeenExecutedFlags[NUM_STRUCS_IN_SEM_ENV]; + VCilkTrans transactionStrucs[NUM_STRUCS_IN_SEM_ENV]; } VCilkSemEnv; +typedef struct _TransListElem TransListElem; +struct _TransListElem + { + int32 transID; + TransListElem *nextTrans; + }; +//TransListElem + typedef struct { - int32 syncPending; - int32 numLiveChildren; - VirtProcr *parentPr; + int32 syncPending; + int32 numLiveChildren; + VirtProcr *parentPr; + + int32 highestTransEntered; + TransListElem *lastTransEntered; } VCilkSemData; @@ -80,7 +126,7 @@ VCilk__init(); void -VCilk__cleanup_after_shutdown(); +VCilk__cleanup_at_end_of_shutdown(); //======================= @@ -103,10 +149,21 @@ void VCilk__dissipate_procr( VirtProcr *procrToDissipate ); -//======================= + +//======================= Concurrency Stuff ====================== +void +VCilk__start_singleton( int32 singletonID, void *endSingletonLabelAddr, + VirtProcr *animPr ); void -VCilk__free_semantic_request( VCilkSemReq *semReq ); +VCilk__animate_short_fn_in_isolation( PtrToAtomicFn ptrToFnToExecInMaster, + void *data, VirtProcr *animPr ); + +void +VCilk__start_transaction( int32 transactionID, VirtProcr *animPr ); + +void +VCilk__end_transaction( int32 transactionID, VirtProcr *animPr ); //========================= Internal use only ============================= diff -r b6ce47a0909b -r 2845dca6a28b VCilk_PluginFns.c --- a/VCilk_PluginFns.c Sun Nov 07 06:53:21 2010 -0800 +++ b/VCilk_PluginFns.c Mon Nov 08 03:58:41 2010 -0800 @@ -6,7 +6,6 @@ #include #include -#include #include "VMS/Queue_impl/PrivateQueue.h" #include "VCilk.h" @@ -27,15 +26,26 @@ handleDissipate( VirtProcr *requestingPr, VCilkSemEnv *semEnv ); void inline -handleSpawn( VCilkSemReq *semReq, VirtProcr *requestingPr, - VCilkSemEnv *semEnv ); +handleSpawn( VMSReqst *req, VirtProcr *requestingPr, VCilkSemEnv *semEnv ); void inline -dispatchSemReq( VCilkSemReq *semReq, VirtProcr *requestingPr, - VCilkSemEnv *semEnv ); +dispatchSemReq( VMSReqst *req, VirtProcr *requestingPr, VCilkSemEnv *semEnv); void inline -resumePr( VirtProcr *procr, VCilkSemEnv *semEnv ); +handleTransEnd( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv*semEnv); +void inline +handleTransStart( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ); +void inline +handleAtomic( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv); +void inline +handleSingleton( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ); + +void inline +resume_procr( VirtProcr *procr, VCilkSemEnv *semEnv ); //=========================================================================== @@ -87,21 +97,19 @@ while( req != NULL ) { switch( req->reqType ) - { case semantic: dispatchSemReq( VMS__take_sem_reqst_from(req), - requestingPr, semEnv ); + { case semantic: dispatchSemReq( req, requestingPr, semEnv ); break; case createReq: //create request has to come as a VMS request, // to allow MasterLoop to do stuff before gets // here, and maybe also stuff after all requests // done -- however, can still attach semantic // req data to req. - semReq = VMS__take_sem_reqst_from( req ); - handleSpawn( semReq, requestingPr, semEnv ); + handleSpawn( req, requestingPr, semEnv); break; - case dissipate: handleDissipate( requestingPr, semEnv ); + case dissipate: handleDissipate( requestingPr, semEnv); break; case VMSSemantic: VMS__handle_VMSSemReq(req, requestingPr, semEnv, - &resumePr ); + &resume_procr); break; default: break; @@ -115,17 +123,27 @@ } void inline -dispatchSemReq( VCilkSemReq *semReq, VirtProcr *requestingPr, - VCilkSemEnv *semEnv ) - { +dispatchSemReq( VMSReqst *req, VirtProcr *reqPr, VCilkSemEnv *semEnv ) + { VCilkSemReq *semReq; + + semReq = VMS__take_sem_reqst_from(req); + if( semReq == NULL ) return; switch( semReq->reqType ) { - case syncReq: handleSync( requestingPr, semEnv ); + case syncReq: handleSync( reqPr, semEnv ); break; - case mallocReq: handleMalloc( semReq, requestingPr, semEnv ); + case mallocReq: handleMalloc( semReq, reqPr, semEnv ); break; - case freeReq: handleFree( semReq, requestingPr, semEnv ); + case freeReq: handleFree( semReq, reqPr, semEnv ); + break; + case singleton: handleSingleton( semReq, reqPr, semEnv ); + break; + case atomic: handleAtomic( semReq, reqPr, semEnv ); + break; + case trans_start: handleTransStart( semReq, reqPr, semEnv ); + break; + case trans_end: handleTransEnd( semReq, reqPr, semEnv ); break; } //NOTE: semantic request data strucs allocated on stack in VCilk Lib calls @@ -135,7 +153,7 @@ //=========================== Request Handlers ============================== void inline -resumePr( VirtProcr *procr, VCilkSemEnv *semEnv ) +resume_procr( VirtProcr *procr, VCilkSemEnv *semEnv ) { writePrivQ( procr, semEnv->readyVPQs[ procr->coreAnimatedBy] ); } @@ -152,7 +170,7 @@ { if(((VCilkSemData *)(requestingPr->semanticData))->numLiveChildren == 0 ) { //no live children to wait for - resumePr( requestingPr, semEnv ); + resume_procr( requestingPr, semEnv ); } else { @@ -168,8 +186,8 @@ { void *ptr; ptr = VMS__malloc( semReq->sizeToMalloc ); - requestingPr->dataReturnedFromReq = ptr; - resumePr( requestingPr, semEnv ); + requestingPr->dataRetFromReq = ptr; + resume_procr( requestingPr, semEnv ); } /* @@ -179,21 +197,22 @@ VCilkSemEnv *semEnv ) { VMS__free( semReq->ptrToFree ); - resumePr( requestingPr, semEnv ); + resume_procr( requestingPr, semEnv ); } - +//============================== VMS requests =============================== /* */ void inline -handleSpawn( VCilkSemReq *semReq, VirtProcr *requestingPr, - VCilkSemEnv *semEnv ) - { +handleSpawn( VMSReqst *req, VirtProcr *requestingPr, VCilkSemEnv *semEnv ) + { VCilkSemReq *semReq; VirtProcr *newPr; VCilkSemData *semanticData; + semReq = VMS__take_sem_reqst_from(req); + //This is running in master, so use internal version newPr = VMS__create_procr( semReq->fnPtr, semReq->initData ); @@ -203,6 +222,9 @@ semanticData->parentPr = NULL; semanticData->syncPending = FALSE; + semanticData->highestTransEntered = -1; + semanticData->lastTransEntered = NULL; + newPr->semanticData = semanticData; /* add newly created to the list of live children of requester. @@ -234,8 +256,8 @@ } #endif - resumePr( newPr, semEnv ); - resumePr( requestingPr, semEnv ); + resume_procr( newPr, semEnv ); + resume_procr( requestingPr, semEnv ); } @@ -266,7 +288,7 @@ { //was waiting for last child to dissipate, so resume it ((VCilkSemData *) (parentPr->semanticData))->syncPending = FALSE; - resumePr( parentPr, semEnv ); + resume_procr( parentPr, semEnv ); } } } @@ -281,7 +303,137 @@ semEnv->numVirtPr -= 1; if( semEnv->numVirtPr == 0 ) { //no more work, so shutdown - VMS__handle_shutdown_reqst( requestingPr ); + VMS__shutdown(); } } + +//=============================== Atomic ==================================== +// +/*Uses ID as index into array of flags. If flag already set, resumes from + * end-label. Else, sets flag and resumes normally. + */ +void inline +handleSingleton( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ) + { + if( semEnv->singletonHasBeenExecutedFlags[ semReq->singletonID ] ) + requestingPr->nextInstrPt = semReq->endJumpPt; + else + semEnv->singletonHasBeenExecutedFlags[ semReq->singletonID ] = TRUE; + + resume_procr( requestingPr, semEnv ); + } + + +/*This executes the function in the masterVP, take the function + * pointer out of the request and call it, then resume the VP. + */ +void inline +handleAtomic( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ) + { + semReq->fnToExecInMaster( semReq->dataForFn ); + resume_procr( requestingPr, semEnv ); + } + +/*First, it looks at the VP's semantic data, to see the highest transactionID + * that VP + * already has entered. If the current ID is not larger, it throws an + * exception stating a bug in the code. + *Otherwise it puts the current ID + * there, and adds the ID to a linked list of IDs entered -- the list is + * used to check that exits are properly ordered. + *Next it is uses transactionID as index into an array of transaction + * structures. + *If the "VP_currently_executing" field is non-null, then put requesting VP + * into queue in the struct. (At some point a holder will request + * end-transaction, which will take this VP from the queue and resume it.) + *If NULL, then write requesting into the field and resume. + */ +void inline +handleTransStart( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ) + { VCilkSemData *semData; + TransListElem *nextTransElem; + + //check ordering of entering transactions is correct + semData = requestingPr->semanticData; + if( semData->highestTransEntered > semReq->transID ) + { //throw VMS exception, which shuts down VMS. + VMS__throw_exception( "transID smaller than prev", requestingPr, NULL); + } + //add this trans ID to the list of transactions entered -- check when + // end a transaction + semData->highestTransEntered = semReq->transID; + nextTransElem = VMS__malloc( sizeof(TransListElem) ); + nextTransElem->transID = semReq->transID; + nextTransElem->nextTrans = semData->lastTransEntered; + semData->lastTransEntered = nextTransElem; + + //get the structure for this transaction ID + VCilkTrans * + transStruc = &(semEnv->transactionStrucs[ semReq->transID ]); + + if( transStruc->VPCurrentlyExecuting == NULL ) + { + transStruc->VPCurrentlyExecuting = requestingPr; + resume_procr( requestingPr, semEnv ); + } + else + { //note, might make future things cleaner if save request with VP and + // add this trans ID to the linked list when gets out of queue. + // but don't need for now, and lazy.. + writePrivQ( requestingPr, transStruc->waitingVPQ ); + } + } + + +/*Use the trans ID to get the transaction structure from the array. + *Look at VP_currently_executing to be sure it's same as requesting VP. + * If different, throw an exception, stating there's a bug in the code. + *Next, take the first element off the list of entered transactions. + * Check to be sure the ending transaction is the same ID as the next on + * the list. If not, incorrectly nested so throw an exception. + * + *Next, get from the queue in the structure. + *If it's empty, set VP_currently_executing field to NULL and resume + * requesting VP. + *If get somethine, set VP_currently_executing to the VP from the queue, then + * resume both. + */ +void inline +handleTransEnd( VCilkSemReq *semReq, VirtProcr *requestingPr, + VCilkSemEnv *semEnv ) + { VCilkSemData *semData; + VirtProcr *waitingPr; + VCilkTrans *transStruc; + TransListElem *lastTrans; + + transStruc = &(semEnv->transactionStrucs[ semReq->transID ]); + + //make sure transaction ended in same VP as started it. + if( transStruc->VPCurrentlyExecuting != requestingPr ) + { + VMS__throw_exception( "trans ended in diff VP", requestingPr, NULL ); + } + + //make sure nesting is correct -- last ID entered should == this ID + semData = requestingPr->semanticData; + lastTrans = semData->lastTransEntered; + if( lastTrans->transID != semReq->transID ) + { + VMS__throw_exception( "trans incorrectly nested", requestingPr, NULL ); + } + + semData->lastTransEntered = semData->lastTransEntered->nextTrans; + + + waitingPr = readPrivQ( transStruc->waitingVPQ ); + transStruc->VPCurrentlyExecuting = waitingPr; + + if( waitingPr != NULL ) + resume_procr( waitingPr, semEnv ); + + resume_procr( requestingPr, semEnv ); + } diff -r b6ce47a0909b -r 2845dca6a28b VCilk_lib.c --- a/VCilk_lib.c Sun Nov 07 06:53:21 2010 -0800 +++ b/VCilk_lib.c Mon Nov 08 03:58:41 2010 -0800 @@ -6,7 +6,6 @@ #include #include -#include #include "VMS/VMS.h" #include "VCilk.h" @@ -106,14 +105,17 @@ // and which then calls create() to create more, thereby expanding work //Note, have to use external version of VMS__create_procr because // internal version uses VMS__malloc, which hasn't been set up by here - seedPr = VMS_ext__create_procr( fnPtr, initData ); + seedPr = VMS__create_procr( fnPtr, initData ); VCilkSemData * - semanticData = malloc( sizeof(VCilkSemData) ); + semanticData = VMS__malloc( sizeof(VCilkSemData) ); semanticData->numLiveChildren = 0; semanticData->parentPr = NULL; semanticData->syncPending = FALSE; + semanticData->highestTransEntered = -1; + semanticData->lastTransEntered = NULL; + seedPr->semanticData = semanticData; seedPr->coreAnimatedBy = semEnv->nextCoreToGetNewPr++; @@ -126,7 +128,7 @@ VMS__start_the_work_then_wait_until_done(); //normal multi-thd #endif - VCilk__cleanup_after_shutdown(); + VCilk__cleanup_at_end_of_shutdown(); } @@ -165,7 +167,8 @@ { int32 endTime, startTime; //TODO: fix by repeating time-measurement saveLowTimeStampCountInto( endTime ); - startTime = ((VCilkSemEnv *)(_VMSMasterEnv->semanticEnv))->primitiveStartTime; + startTime = ( (VCilkSemEnv *) + (_VMSMasterEnv->semanticEnv))->primitiveStartTime; return (endTime - startTime); } @@ -213,14 +216,14 @@ //create the semantic layer's environment (all its data) and add to // the master environment - semanticEnv = malloc( sizeof( VCilkSemEnv ) ); + semanticEnv = VMS__malloc( sizeof( VCilkSemEnv ) ); _VMSMasterEnv->semanticEnv = semanticEnv; //create the ready queue, hash tables used for pairing send to receive // and so forth //TODO: add hash tables for pairing sends with receives, and // initialize the data ownership system - readyVPQs = malloc( NUM_CORES * sizeof(PrivQueueStruc *) ); + readyVPQs = VMS__malloc( NUM_CORES * sizeof(PrivQueueStruc *) ); for( coreIdx = 0; coreIdx < NUM_CORES; coreIdx++ ) { @@ -230,6 +233,18 @@ semanticEnv->readyVPQs = readyVPQs; semanticEnv->nextCoreToGetNewPr = 0; + + //TODO: bug -- turn these arrays into dyn arrays to eliminate limit + //semanticEnv->singletonHasBeenExecutedFlags = makeDynArrayInfo( ); + //semanticEnv->transactionStrucs = makeDynArrayInfo( ); + //something like: setHighestIdx( dynArrayInfo, NUM_STRUCS_IN_SEM_ENV ) + int32 i; + for( i = 0; i < NUM_STRUCS_IN_SEM_ENV; i++ ) + { + semanticEnv->singletonHasBeenExecutedFlags[i] = FALSE; + semanticEnv->transactionStrucs[i].waitingVPQ = makePrivQ(); + } + } @@ -237,23 +252,23 @@ *Frees any memory allocated by VCilk__init() then calls VMS's cleanup */ void -VCilk__cleanup_after_shutdown() +VCilk__cleanup_at_end_of_shutdown() { VCilkSemEnv *semanticEnv; - int coreIdx; semanticEnv = _VMSMasterEnv->semanticEnv; -//TODO: double check all sem env locations freed - + /* + int32 coreIdx; for( coreIdx = 0; coreIdx < NUM_CORES; coreIdx++ ) { - free( semanticEnv->readyVPQs[coreIdx]->startOfData ); - free( semanticEnv->readyVPQs[coreIdx] ); + VMS__free( semanticEnv->readyVPQs[coreIdx]->startOfData ); + VMS__free( semanticEnv->readyVPQs[coreIdx] ); } - free( semanticEnv->readyVPQs ); + VMS__free( semanticEnv->readyVPQs ); - free( _VMSMasterEnv->semanticEnv ); - VMS__cleanup_after_shutdown(); + VMS__free( _VMSMasterEnv->semanticEnv ); + */ + VMS__cleanup_at_end_of_shutdown(); } @@ -322,7 +337,7 @@ VMS__send_sem_request( &reqData, animPr ); - return animPr->dataReturnedFromReq; + return animPr->dataRetFromReq; } @@ -339,3 +354,92 @@ VMS__send_sem_request( &reqData, animPr ); } +//=========================================================================== + +/*Uses ID as index into array of flags. If flag already set, resumes from + * end-label. Else, sets flag and resumes normally. + */ +void +VCilk__start_singleton( int32 singletonID, void *endSingletonLabelAddr, + VirtProcr *animPr ) + { + VCilkSemReq reqData; + + // + reqData.reqType = singleton; + reqData.singletonID = singletonID; + reqData.endJumpPt = endSingletonLabelAddr; + + VMS__send_sem_request( &reqData, animPr ); + } + +/*This executes the function in the masterVP, so it executes in isolation + * from any other copies -- only one copy of the function can ever execute + * at a time. + * + *It suspends to the master, and the request handler takes the function + * pointer out of the request and calls it, then resumes the VP. + *Only very short functions should be called this way -- for longer-running + * isolation, use transaction-start and transaction-end, which run the code + * between as work-code. + */ +void +VCilk__animate_short_fn_in_isolation( PtrToAtomicFn ptrToFnToExecInMaster, + void *data, VirtProcr *animPr ) + { + VCilkSemReq reqData; + + // + reqData.reqType = atomic; + reqData.fnToExecInMaster = ptrToFnToExecInMaster; + reqData.dataForFn = data; + + VMS__send_sem_request( &reqData, animPr ); + } + + +/*This suspends to the master. + *First, it looks at the VP's data, to see the highest transactionID that VP + * already has entered. If the current ID is not larger, it throws an + * exception stating a bug in the code. Otherwise it puts the current ID + * there, and adds the ID to a linked list of IDs entered -- the list is + * used to check that exits are properly ordered. + *Next it is uses transactionID as index into an array of transaction + * structures. + *If the "VP_currently_executing" field is non-null, then put requesting VP + * into queue in the struct. (At some point a holder will request + * end-transaction, which will take this VP from the queue and resume it.) + *If NULL, then write requesting into the field and resume. + */ +void +VCilk__start_transaction( int32 transactionID, VirtProcr *animPr ) + { + VCilkSemReq reqData; + + // + reqData.reqType = trans_start; + reqData.transID = transactionID; + + VMS__send_sem_request( &reqData, animPr ); + } + +/*This suspends to the master, then uses transactionID as index into an + * array of transaction structures. + *It looks at VP_currently_executing to be sure it's same as requesting VP. + * If different, throws an exception, stating there's a bug in the code. + *Next it looks at the queue in the structure. + *If it's empty, it sets VP_currently_executing field to NULL and resumes. + *If something in, gets it, sets VP_currently_executing to that VP, then + * resumes both. + */ +void +VCilk__end_transaction( int32 transactionID, VirtProcr *animPr ) + { + VCilkSemReq reqData; + + // + reqData.reqType = trans_end; + reqData.transID = transactionID; + + VMS__send_sem_request( &reqData, animPr ); + } \ No newline at end of file