1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/DESIGN_NOTES__VPThread__lib.txt	Fri Sep 17 11:34:02 2010 -0700
     1.3 @@ -0,0 +1,82 @@
     1.4 +
     1.5 +Implement VPThread this way:
     1.6 +
     1.7 +We implemented a subset of PThreads functionality, called VMSPThd, that
     1.8 +includes: mutex_lock, mutex_unlock, cond_wait, and cond_notify, which we name
     1.9 +as VMSPThd__mutix_lock and so forth. \ All VMSPThd functions take a reference
    1.10 +to the AppVP that is animating the function call, in addition to any other
    1.11 +parameters.
    1.12 +
    1.13 +A mutex variable is an integer, returned by VMSPThd__mutex_create(), which is
    1.14 +used inside the request handler as a key to lookup an entry in a hash table,
    1.15 +that lives in the SemanticEnv. \ Such an entry has a field holding a
    1.16 +reference to the AppVP that currently owns the lock, and a queue of AppVPs
    1.17 +waiting to acquire the lock. \
    1.18 +
    1.19 +Acquiring a lock is done with VMSPThd__mutex_lock(), which generates a
    1.20 +request. \ Recall that all request sends cause the suspention of the AppVP
    1.21 +that is animating the library call that generates the request, in this case
    1.22 +the AppVP animating VMSPThd__mutex_lock() is suspended. \ The request
    1.23 +includes a reference to that animating AppVP, and the mutex integer value.
    1.24 +\ When the request reaches the request handler, the mutex integer is used as
    1.25 +key to look up the hash entry, then if the owner field is null (or the same
    1.26 +as the AppVP in the request), the AppVP in the request is placed into the
    1.27 +owner field, and that AppVP is queued to be scheduled for re-animation.
    1.28 +\ However, if a different AppVP is listed in the owner field, then the AppVP
    1.29 +in the request is added to the queue of those trying to acquire. \ Notice
    1.30 +that this is a purely sequential algorithm that systematic reasoning can be
    1.31 +used on.
    1.32 +
    1.33 +VMSPThd__mutex_unlock(), meanwhile, generates a request that causes the
    1.34 +request handler to queue for re-animation the AppVP that animated the call.
    1.35 +\ It also pops the queue of AppVPs waiting to acquire the lock, and writes
    1.36 +the AppVP that comes out as the current owner of the lock and queues that
    1.37 +AppVP for re-animation (unless the popped value is null, in which case the
    1.38 +current owner is just set to null).
    1.39 +
    1.40 +Implementing condition variables takes a similar approach, in that
    1.41 +VMSPThd__init_cond() returns an integer that is then used to look up an entry
    1.42 +in a hash table, where the entry contains a queue of AppVPs waiting on the
    1.43 +condition variable. \ VMSPThd__cond_wait() generates a request that pushes
    1.44 +the AppVP into the queue, while VMSPThd__cond_signal() takes a wait request
    1.45 +from the queue.
    1.46 +
    1.47 +Notice that this is again a purely sequential algorithm, and sidesteps issues
    1.48 +such as ``simultaneous'' wait and signal requests -- the wait and signal get
    1.49 +serialized automatically, even though they take place at the same instant of
    1.50 +program virtual time. \
    1.51 +
    1.52 +It is the fact of having a program virtual time that allows ``virtual
    1.53 +simultaneous'' actions to be handled <em|outside> of the virtual time. \ That
    1.54 +ability to escape outside of the virtual time is what enables a
    1.55 +<em|sequential> algorithm to handle the simultaneity that is at the heart of
    1.56 +making implementing locks in physical time so intricately tricky
    1.57 +<inactive|<cite|LamportLockImpl>> <inactive|<cite|DijkstraLockPaper>>
    1.58 +<inactive|<cite|LamportRelativisticTimePaper>>.\
    1.59 +
    1.60 +What's nice about this approach is that the design and implementation are
    1.61 +simple and straight forward. \ It took just X days to design, implement, and
    1.62 +debug, and is in a form that should be amenable to proof of freedom from race
    1.63 +conditions, given a correct implementation of VMS. \ The hash-table based
    1.64 +approach also makes it reasonably high performance, with (essentially) no
    1.65 +slowdown when the number of locks or number of AppVPs grows large.
    1.66 +
    1.67 +===========================
    1.68 +Behavior:
    1.69 +Cond variables are half of a two-piece mechanism.  The other half is a mutex.
    1.70 + Every cond var owns a mutex -- the two intrinsically work
    1.71 + together, as a pair.  The mutex must only be used with the condition var
    1.72 + and not used on its own in other ways.
    1.73 +
    1.74 +cond_wait is called with a cond-var and its mutex.
    1.75 +The animating processor must have acquired the mutex before calling cond_wait
    1.76 +The call adds the animating processor to the queue associated with the cond
    1.77 +variable and then calls mutex_unlock on the mutex.
    1.78 +
    1.79 +cond_signal can only be called after acquiring the cond var's mutex.  It is
    1.80 +called with the cond-var.
    1.81 + The call takes the next processor from the condition-var's wait queue and
    1.82 + transfers it to the waiting-for-lock queue of the cond-var's mutex.
    1.83 +The processor that called the cond_signal next has to perform a mutex_unlock
    1.84 + on the cond-var's mutex -- that, finally, lets the waiting processor acquire
    1.85 + the mutex and proceed.

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/VPThread.h	Fri Sep 17 11:34:02 2010 -0700
     2.3 @@ -0,0 +1,153 @@
     2.4 +/*
     2.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     2.6 + *  Licensed under GNU General Public License version 2
     2.7 + *
     2.8 + * Author: seanhalle@yahoo.com
     2.9 + *
    2.10 + */
    2.11 +
    2.12 +#ifndef _VPThread_H
    2.13 +#define	_VPThread_H
    2.14 +
    2.15 +#include "VMS/VMS.h"
    2.16 +#include "VMS/Queue_impl/PrivateQueue.h"
    2.17 +#include "VMS/DynArray/DynArray.h"
    2.18 +
    2.19 +
    2.20 +//===========================================================================
    2.21 +#define INIT_NUM_MUTEX 10000
    2.22 +#define INIT_NUM_COND  10000
    2.23 +//===========================================================================
    2.24 +
    2.25 +/*This header defines everything specific to the VPThread semantic plug-in
    2.26 + */
    2.27 +typedef struct _VPThreadSemReq   VPThreadSemReq;
    2.28 +
    2.29 +
    2.30 +/*Semantic layer-specific data sent inside a request from lib called in app
    2.31 + * to request handler called in MasterLoop
    2.32 + */
    2.33 +enum VPThreadReqType
    2.34 + {
    2.35 +   make_mutex = 1,
    2.36 +   mutex_lock,
    2.37 +   mutex_unlock,
    2.38 +   make_cond,
    2.39 +   cond_wait,
    2.40 +   cond_signal,
    2.41 +   make_procr
    2.42 + };
    2.43 +
    2.44 +struct _VPThreadSemReq
    2.45 + { enum VPThreadReqType reqType;
    2.46 +   VirtProcr           *requestingPr;
    2.47 +   int32                mutexIdx;
    2.48 +   int32                condIdx;
    2.49 +   void                *initData;
    2.50 +   VirtProcrFnPtr       fnPtr;
    2.51 + }
    2.52 +/* VPThreadSemReq */;
    2.53 +
    2.54 +typedef struct
    2.55 + {
    2.56 +      //Standard stuff will be in most every semantic env
    2.57 +   PrivQueueStruc **readyVPQs;
    2.58 +   int32            numVirtPr;
    2.59 +   int32            nextCoreToGetNewPr;
    2.60 +
    2.61 +      //Specific to this semantic layer
    2.62 +   int32            currMutexIdx;
    2.63 +   DynArray32      *mutexDynArray;
    2.64 +   
    2.65 +   int32            currCondIdx;
    2.66 +   DynArray32      *condDynArray;
    2.67 +
    2.68 +   void            *applicationGlobals;
    2.69 + }
    2.70 +VPThreadSemEnv;
    2.71 +
    2.72 +
    2.73 +typedef struct
    2.74 + {
    2.75 +   int32           mutexIdx;
    2.76 +   VirtProcr      *holderOfLock;
    2.77 +   PrivQueueStruc *waitingQueue;
    2.78 + }
    2.79 +VPTMutex;
    2.80 +
    2.81 +
    2.82 +typedef struct
    2.83 + {
    2.84 +   int32           condIdx;
    2.85 +   PrivQueueStruc *waitingQueue;
    2.86 +   VPTMutex       *partnerMutex;
    2.87 + }
    2.88 +VPTCond;
    2.89 +
    2.90 +
    2.91 +//===========================================================================
    2.92 +
    2.93 +void
    2.94 +VPThread__create_seed_procr_and_do_work( VirtProcrFnPtr fn, void *initData );
    2.95 +
    2.96 +//=======================
    2.97 +
    2.98 +inline VirtProcr *
    2.99 +VPThread__create_thread( VirtProcrFnPtr fnPtr, void *initData,
   2.100 +                          VirtProcr *creatingPr );
   2.101 +
   2.102 +void
   2.103 +VPThread__dissipate_thread( VirtProcr *procrToDissipate );
   2.104 +
   2.105 +//=======================
   2.106 +void
   2.107 +VPThread__set_globals_to( void *globals );
   2.108 +
   2.109 +void *
   2.110 +VPThread__give_globals();
   2.111 +
   2.112 +//=======================
   2.113 +int32
   2.114 +VPThread__make_mutex( VirtProcr *animPr );
   2.115 +
   2.116 +void
   2.117 +VPThread__mutex_lock( int32 mutexIdx, VirtProcr *acquiringPr );
   2.118 +                                                    
   2.119 +void
   2.120 +VPThread__mutex_unlock( int32 mutexIdx, VirtProcr *releasingPr );
   2.121 +
   2.122 +
   2.123 +//=======================
   2.124 +int32
   2.125 +VPThread__make_cond( int32 ownedMutexIdx, VirtProcr *animPr);
   2.126 +
   2.127 +void
   2.128 +VPThread__cond_wait( int32 condIdx, VirtProcr *waitingPr);
   2.129 +
   2.130 +void *
   2.131 +VPThread__cond_signal( int32 condIdx, VirtProcr *signallingPr );
   2.132 +
   2.133 +
   2.134 +
   2.135 +
   2.136 +//=========================  Internal use only  =============================
   2.137 +void
   2.138 +VPThread__Request_Handler( VirtProcr *requestingPr, void *_semEnv );
   2.139 +
   2.140 +VirtProcr *
   2.141 +VPThread__schedule_virt_procr( void *_semEnv, int coreNum );
   2.142 +
   2.143 +//=======================
   2.144 +void
   2.145 +VPThread__free_semantic_request( VPThreadSemReq *semReq );
   2.146 +
   2.147 +//=======================
   2.148 +
   2.149 +void
   2.150 +VPThread__init();
   2.151 +
   2.152 +void
   2.153 +VPThread__cleanup_after_shutdown();
   2.154 +
   2.155 +#endif	/* _VPThread_H */
   2.156 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/VPThread__PluginFns.c	Fri Sep 17 11:34:02 2010 -0700
     3.3 @@ -0,0 +1,110 @@
     3.4 +/*
     3.5 + * Copyright 2010  OpenSourceCodeStewardshipFoundation
     3.6 + *
     3.7 + * Licensed under BSD
     3.8 + */
     3.9 +
    3.10 +#include <stdio.h>
    3.11 +#include <stdlib.h>
    3.12 +#include <malloc.h>
    3.13 +
    3.14 +#include "VMS/Queue_impl/PrivateQueue.h"
    3.15 +#include "VPThread.h"
    3.16 +#include "VPThread__Request_Handlers.h"
    3.17 +
    3.18 +
    3.19 +/*Will get requests to send, to receive, and to create new processors.
    3.20 + * Upon send, check the hash to see if a receive is waiting.
    3.21 + * Upon receive, check hash to see if a send has already happened.
    3.22 + * When other is not there, put in.  When other is there, the comm.
    3.23 + *  completes, which means the receiver P gets scheduled and
    3.24 + *  picks up right after the receive request.  So make the work-unit
    3.25 + *  and put it into the queue of work-units ready to go.
    3.26 + * Other request is create a new Processor, with the function to run in the
    3.27 + *  Processor, and initial data.
    3.28 + */
    3.29 +void
    3.30 +VPThread__Request_Handler( VirtProcr *requestingPr, void *_semEnv )
    3.31 + { VPThreadSemEnv *semEnv;
    3.32 +   VMSReqst    *req;
    3.33 +   VPThreadSemReq *semReq;
    3.34 + 
    3.35 +   semEnv = (VPThreadSemEnv *)_semEnv;
    3.36 +
    3.37 +   req = VMS__take_top_request_from( requestingPr );
    3.38 +   
    3.39 +   while( req != NULL )
    3.40 +    {
    3.41 +      if( VMS__isSemanticReqst( req ) )
    3.42 +       {
    3.43 +         semReq = VMS__take_sem_reqst_from( req );
    3.44 +         if( semReq == NULL ) goto DoneHandlingReqst;
    3.45 +         switch( semReq->reqType )
    3.46 +          {
    3.47 +            case make_mutex:     handleMakeMutex(  semReq, semEnv);
    3.48 +               break;
    3.49 +            case mutex_lock:     handleMutexLock(  semReq, semEnv);
    3.50 +               break;
    3.51 +            case mutex_unlock:   handleMutexUnlock(semReq, semEnv);
    3.52 +               break;
    3.53 +            case make_cond:      handleMakeCond(   semReq, semEnv);
    3.54 +               break;
    3.55 +            case cond_wait:      handleCondWait(   semReq, semEnv);
    3.56 +               break;
    3.57 +            case cond_signal:    handleCondSignal( semReq, semEnv);
    3.58 +               //need? VPThread__free_semantic_request( semReq );
    3.59 +               break;
    3.60 +            case make_procr:     handleMakeProcr(  semReq, semEnv);
    3.61 +               break;
    3.62 +            //TODO: make sure free the semantic request!
    3.63 +          }
    3.64 +         //NOTE: freeing semantic request data strucs handled inside these
    3.65 +       }
    3.66 +      else if( VMS__isDissipateReqst( req ) ) //Standard VMS request
    3.67 +       {    //Another standard VMS request that the plugin has to handle
    3.68 +            //This time, plugin has to free the semantic data it may have
    3.69 +            // allocated into the virt procr -- and clear the AppVP out of
    3.70 +            // any data structs the plug-in may have put it into, like hash
    3.71 +            // tables.
    3.72 +
    3.73 +            //Now, call VMS to free all AppVP state -- stack and so on
    3.74 +         VMS__handle_dissipate_reqst( requestingPr );
    3.75 +
    3.76 +            //Keep count of num AppVPs, so know when to shutdown
    3.77 +         semEnv->numVirtPr -= 1;
    3.78 +         if( semEnv->numVirtPr == 0 )
    3.79 +          {    //no more work, so shutdown
    3.80 +            VMS__handle_shutdown_reqst( requestingPr );
    3.81 +          }
    3.82 +       }
    3.83 +
    3.84 +      DoneHandlingReqst:
    3.85 +         //Here, free VMS's request structure, no matter what -- even though
    3.86 +         // semantic request struc instances may still be around..
    3.87 +         //This call frees VMS's portion, then returns the next request
    3.88 +      req = VMS__free_top_and_give_next_request_from( requestingPr );
    3.89 +    } //while( req != NULL )
    3.90 + }
    3.91 +
    3.92 +//===========================================================================
    3.93 +
    3.94 +
    3.95 +/*For VPThread, scheduling a slave simply takes the next work-unit off the
    3.96 + * ready-to-go work-unit queue and assigns it to the slaveToSched.
    3.97 + *If the ready-to-go work-unit queue is empty, then nothing to schedule
    3.98 + * to the slave -- return FALSE to let Master loop know scheduling that
    3.99 + * slave failed.
   3.100 + */
   3.101 +VirtProcr *
   3.102 +VPThread__schedule_virt_procr( void *_semEnv, int coreNum )
   3.103 + { VirtProcr   *schedPr;
   3.104 +   VPThreadSemEnv *semEnv;
   3.105 +
   3.106 +   semEnv = (VPThreadSemEnv *)_semEnv;
   3.107 +
   3.108 +   schedPr = readPrivQ( semEnv->readyVPQs[coreNum] );
   3.109 +      //Note, using a non-blocking queue -- it returns NULL if queue empty
   3.110 +
   3.111 +   return( schedPr );
   3.112 + }
   3.113 +

     4.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     4.2 +++ b/VPThread__Request_Handlers.c	Fri Sep 17 11:34:02 2010 -0700
     4.3 @@ -0,0 +1,222 @@
     4.4 +/*
     4.5 + * Copyright 2010  OpenSourceCodeStewardshipFoundation
     4.6 + *
     4.7 + * Licensed under BSD
     4.8 + */
     4.9 +
    4.10 +#include <stdio.h>
    4.11 +#include <stdlib.h>
    4.12 +#include <malloc.h>
    4.13 +
    4.14 +#include "VMS/VMS.h"
    4.15 +#include "VMS/Queue_impl/PrivateQueue.h"
    4.16 +#include "VMS/Hash_impl/PrivateHash.h"
    4.17 +#include "VPThread.h"
    4.18 +
    4.19 +
    4.20 +
    4.21 +//===============================  Mutexes  =================================
    4.22 +/*The semantic request has a mutexIdx value, which acts as index into array.
    4.23 + */
    4.24 +void
    4.25 +handleMakeMutex( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
    4.26 + { VPTMutex  *newMutex;
    4.27 +   VirtProcr  *pr;
    4.28 +   int32       mutexIdx;
    4.29 +
    4.30 +   newMutex = malloc( sizeof(VPTMutex) );
    4.31 +   newMutex->waitingQueue = makePrivQ();
    4.32 +   newMutex->holderOfLock = NULL;
    4.33 +   newMutex->mutexIdx = semEnv->currMutexIdx++;
    4.34 +   mutexIdx = newMutex->mutexIdx;
    4.35 +
    4.36 +      //The mutex struc contains an int that identifies it -- use that as
    4.37 +      // its index within the array of mutexes.  Add the new mutex to array.
    4.38 +   makeArray32BigEnoughForIndex( semEnv->mutexDynArray, mutexIdx );
    4.39 +   semEnv->mutexDynArray->array[ mutexIdx ] = newMutex;
    4.40 +
    4.41 +      //Now communicate the mutex's identifying int back to requesting procr
    4.42 +   semReq->requestingPr->semanticData = newMutex->mutexIdx;
    4.43 +
    4.44 +      //re-animate the requester
    4.45 +   pr = semReq->requestingPr;
    4.46 +   writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
    4.47 + }
    4.48 +
    4.49 +
    4.50 +void
    4.51 +handleMutexLock( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
    4.52 + { VPTMutex  *mutex;
    4.53 +   VirtProcr  *pr;
    4.54 +
    4.55 +   //===================  Deterministic Replay  ======================
    4.56 +   #ifdef RECORD_DETERMINISTIC_REPLAY
    4.57 +   
    4.58 +   #endif
    4.59 +   //=================================================================
    4.60 +      //lookup mutex struc, using mutexIdx as index
    4.61 +   mutex = semEnv->mutexDynArray->array[ semReq->mutexIdx ];
    4.62 +
    4.63 +      //see if mutex is free or not
    4.64 +   if( mutex->holderOfLock == NULL ) //none holding, give lock to requester
    4.65 +    {
    4.66 +      mutex->holderOfLock = semReq->requestingPr;
    4.67 +
    4.68 +         //re-animate requester, now that it has the lock
    4.69 +      pr = semReq->requestingPr;
    4.70 +      writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
    4.71 +    }
    4.72 +   else //queue up requester to wait for release of lock
    4.73 +    {
    4.74 +      writePrivQ( semReq->requestingPr, mutex->waitingQueue );
    4.75 +    }
    4.76 + }
    4.77 +
    4.78 +/*
    4.79 + */
    4.80 +void
    4.81 +handleMutexUnlock( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
    4.82 + { VPTMutex  *mutex;
    4.83 +   VirtProcr  *pr;
    4.84 +
    4.85 +      //lookup mutex struc, using mutexIdx as index
    4.86 +   mutex = semEnv->mutexDynArray->array[ semReq->mutexIdx ];
    4.87 +
    4.88 +      //set new holder of mutex-lock to be next in queue (NULL if empty)
    4.89 +   mutex->holderOfLock = readPrivQ( mutex->waitingQueue );
    4.90 +
    4.91 +      //if have new non-NULL holder, re-animate it
    4.92 +   if( mutex->holderOfLock != NULL )
    4.93 +    {
    4.94 +      pr = mutex->holderOfLock;
    4.95 +      writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
    4.96 +    }
    4.97 +
    4.98 +      //re-animate the releaser of the lock
    4.99 +   pr = semReq->requestingPr;
   4.100 +   writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
   4.101 + }
   4.102 +
   4.103 +//===========================  Condition Vars  ==============================
   4.104 +/*The semantic request has the cond-var value and mutex value, which are the
   4.105 + * indexes into the array.  Not worrying about having too many mutexes or
   4.106 + * cond vars created, so using array instead of hash table, for speed.
   4.107 + */
   4.108 +
   4.109 +
   4.110 +/*Make cond has to be called with the mutex that the cond is paired to
   4.111 + * Don't have to implement this way, but was confusing learning cond vars
   4.112 + * until deduced that each cond var owns a mutex that is used only for
   4.113 + * interacting with that cond var.  So, make this pairing explicit.
   4.114 + */
   4.115 +void
   4.116 +handleMakeCond( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
   4.117 + { VPTCond   *newCond;
   4.118 +   VirtProcr  *pr;
   4.119 +   int32       condIdx;
   4.120 +
   4.121 +   newCond = malloc( sizeof(VPTCond) );
   4.122 +   newCond->partnerMutex = semEnv->mutexDynArray->array[ semReq->mutexIdx ];
   4.123 +
   4.124 +   newCond->waitingQueue = makePrivQ();
   4.125 +   newCond->condIdx = semEnv->currCondIdx++;
   4.126 +   condIdx = newCond->condIdx;
   4.127 +
   4.128 +      //The cond struc contains an int that identifies it -- use that as
   4.129 +      // its index within the array of conds.  Add the new cond to array.
   4.130 +   makeArray32BigEnoughForIndex( semEnv->condDynArray, condIdx );
   4.131 +   semEnv->condDynArray->array[ condIdx ] = newCond;
   4.132 +
   4.133 +      //Now communicate the cond's identifying int back to requesting procr
   4.134 +   semReq->requestingPr->semanticData = newCond->condIdx;
   4.135 +   
   4.136 +      //re-animate the requester
   4.137 +   pr = semReq->requestingPr;
   4.138 +   writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
   4.139 + }
   4.140 +
   4.141 +
   4.142 +/*Mutex has already been paired to the cond var, so don't need to send the
   4.143 + * mutex, just the cond var.  Don't have to do this, but want to bitch-slap
   4.144 + * the designers of Posix standard  ; )
   4.145 + */
   4.146 +void
   4.147 +handleCondWait( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
   4.148 + { VPTCond   *cond;
   4.149 +   VPTMutex  *mutex;
   4.150 +   VirtProcr  *pr;
   4.151 +
   4.152 +      //get cond struc out of array of them that's in the sem env
   4.153 +   cond = semEnv->condDynArray->array[ semReq->condIdx ];
   4.154 +
   4.155 +      //add requester to queue of wait-ers
   4.156 +   writePrivQ( semReq->requestingPr, cond->waitingQueue );
   4.157 +    
   4.158 +      //unlock mutex -- can't reuse above handler 'cause not queuing releaser
   4.159 +   mutex = cond->partnerMutex;
   4.160 +   mutex->holderOfLock = readPrivQ( mutex->waitingQueue );
   4.161 +
   4.162 +   if( mutex->holderOfLock != NULL )
   4.163 +    {
   4.164 +      pr = mutex->holderOfLock;
   4.165 +      writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
   4.166 +   }
   4.167 + }
   4.168 +
   4.169 +
   4.170 +/*Note that have to implement this such that guarantee the waiter is the one
   4.171 + * that gets the lock
   4.172 + */
   4.173 +void
   4.174 +handleCondSignal( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
   4.175 + { VPTCond   *cond;
   4.176 +   VPTMutex  *mutex;
   4.177 +   VirtProcr  *waitingPr, *pr;
   4.178 +
   4.179 +      //get cond struc out of array of them that's in the sem env
   4.180 +   cond = semEnv->condDynArray->array[ semReq->condIdx ];
   4.181 +   
   4.182 +      //take next waiting procr out of queue
   4.183 +   waitingPr = readPrivQ( cond->waitingQueue );
   4.184 +
   4.185 +      //transfer waiting procr to wait queue of mutex
   4.186 +      // mutex is guaranteed to be held by signalling procr, so no check
   4.187 +   mutex = cond->partnerMutex;
   4.188 +   pushPrivQ( waitingPr, mutex->waitingQueue ); //is first out when read
   4.189 +
   4.190 +      //re-animate the signalling procr
   4.191 +   pr = semReq->requestingPr;
   4.192 +   writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
   4.193 + }
   4.194 +
   4.195 +
   4.196 +
   4.197 +/*Make cond has to be called with the mutex that the cond is paired to
   4.198 + * Don't have to implement this way, but was confusing learning cond vars
   4.199 + * until deduced that each cond var owns a mutex that is used only for
   4.200 + * interacting with that cond var.  So, make this pairing explicit.
   4.201 + */
   4.202 +void
   4.203 +handleMakeProcr( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv)
   4.204 + { VirtProcr  *newPr, *pr;
   4.205 +
   4.206 +   newPr = VMS__create_procr( semReq->fnPtr, semReq->initData );
   4.207 +
   4.208 +   semEnv->numVirtPr += 1;
   4.209 +
   4.210 +      //Assign new processor to next core in line & queue it up
   4.211 +   #ifdef SEQUENTIAL
   4.212 +   newPr->coreAnimatedBy = 0;
   4.213 +   #else
   4.214 +   newPr->coreAnimatedBy = semEnv->nextCoreToGetNewPr;
   4.215 +   if( semEnv->nextCoreToGetNewPr >= NUM_CORES - 1 )
   4.216 +       semEnv->nextCoreToGetNewPr  = 0;
   4.217 +   else
   4.218 +       semEnv->nextCoreToGetNewPr += 1;
   4.219 +   #endif
   4.220 +   writePrivQ( newPr, semEnv->readyVPQs[newPr->coreAnimatedBy] );
   4.221 +
   4.222 +      //re-animate the requester
   4.223 +   pr = semReq->requestingPr;
   4.224 +   writePrivQ( pr,    semEnv->readyVPQs[pr->coreAnimatedBy] );
   4.225 + }

     5.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     5.2 +++ b/VPThread__Request_Handlers.h	Fri Sep 17 11:34:02 2010 -0700
     5.3 @@ -0,0 +1,33 @@
     5.4 +/*
     5.5 + *  Copyright 2009 OpenSourceStewardshipFoundation.org
     5.6 + *  Licensed under GNU General Public License version 2
     5.7 + *
     5.8 + * Author: seanhalle@yahoo.com
     5.9 + *
    5.10 + */
    5.11 +
    5.12 +#ifndef _VPThread_REQ_H
    5.13 +#define	_VPThread_REQ_H
    5.14 +
    5.15 +#include "VPThread.h"
    5.16 +
    5.17 +/*This header defines everything specific to the VPThread semantic plug-in
    5.18 + */
    5.19 +
    5.20 +void
    5.21 +handleMakeMutex(  VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.22 +void
    5.23 +handleMutexLock(  VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.24 +void
    5.25 +handleMutexUnlock(VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.26 +void
    5.27 +handleMakeCond(   VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.28 +void
    5.29 +handleCondWait(   VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.30 +void
    5.31 +handleCondSignal( VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.32 +void
    5.33 +handleMakeProcr(  VPThreadSemReq *semReq, VPThreadSemEnv *semEnv);
    5.34 +
    5.35 +#endif	/* _VPThread_REQ_H */
    5.36 +

     6.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     6.2 +++ b/VPThread__lib.c	Fri Sep 17 11:34:02 2010 -0700
     6.3 @@ -0,0 +1,379 @@
     6.4 +/*
     6.5 + * Copyright 2010  OpenSourceCodeStewardshipFoundation
     6.6 + *
     6.7 + * Licensed under BSD
     6.8 + */
     6.9 +
    6.10 +#include <stdio.h>
    6.11 +#include <stdlib.h>
    6.12 +#include <malloc.h>
    6.13 +
    6.14 +#include "VMS/VMS.h"
    6.15 +#include "VPThread.h"
    6.16 +#include "VMS/Queue_impl/PrivateQueue.h"
    6.17 +#include "VMS/Hash_impl/PrivateHash.h"
    6.18 +
    6.19 +
    6.20 +//==========================================================================
    6.21 +
    6.22 +void
    6.23 +VPThread__init();
    6.24 +
    6.25 +void
    6.26 +VPThread__init_Seq();
    6.27 +
    6.28 +void
    6.29 +VPThread__init_Helper();
    6.30 +//==========================================================================
    6.31 +
    6.32 +
    6.33 +/*TODO: Q: dealing with library f()s and DKU vs WT vs FoR
    6.34 + * (still want to do FoR, with time-lines as syntax, could be super cool)
    6.35 + * A: thinking pin the coreLoops for all of BLIS -- let Master arbitrate
    6.36 + * among library, DKU, WT, FoR -- all the patterns in terms of virtual
    6.37 + * processors (or equivalently work-units), so Master picks which virt procr
    6.38 + * from which portions of app (DKU, WT, FoR) onto which sched slots
    6.39 + *Might even do hierarchy of masters -- group of sched slots for each core
    6.40 + * has its own master, that keeps generated work local
    6.41 + * single-reader-single-writer sync everywhere -- no atomic primitives
    6.42 + * Might have the different schedulers talk to each other, to negotiate
    6.43 + * larger-grain sharing of resources, according to predicted critical
    6.44 + * path, and expansion of work
    6.45 + */
    6.46 +
    6.47 +
    6.48 +
    6.49 +//===========================================================================
    6.50 +
    6.51 +
    6.52 +/*These are the library functions *called in the application*
    6.53 + * 
    6.54 + *There's a pattern for the outside sequential code to interact with the
    6.55 + * VMS_HW code.
    6.56 + *The VMS_HW system is inside a boundary..  every VPThread system is in its
    6.57 + * own directory that contains the functions for each of the processor types.
    6.58 + * One of the processor types is the "seed" processor that starts the
    6.59 + * cascade of creating all the processors that do the work.
    6.60 + *So, in the directory is a file called "EntryPoint.c" that contains the
    6.61 + * function, named appropriately to the work performed, that the outside
    6.62 + * sequential code calls.  This function follows a pattern:
    6.63 + *1) it calls VPThread__init()
    6.64 + *2) it creates the initial data for the seed processor, which is passed
    6.65 + *    in to the function
    6.66 + *3) it creates the seed VPThread processor, with the data to start it with.
    6.67 + *4) it calls startVPThreadThenWaitUntilWorkDone
    6.68 + *5) it gets the returnValue from the transfer struc and returns that
    6.69 + *    from the function
    6.70 + *
    6.71 + *For now, a new VPThread system has to be created via VPThread__init every
    6.72 + * time an entry point function is called -- later, might add letting the
    6.73 + * VPThread system be created once, and let all the entry points just reuse
    6.74 + * it -- want to be as simple as possible now, and see by using what makes
    6.75 + * sense for later..
    6.76 + */
    6.77 +
    6.78 +
    6.79 +
    6.80 +//===========================================================================
    6.81 +
    6.82 +/*This is the "border crossing" function -- the thing that crosses from the
    6.83 + * outside world, into the VMS_HW world.  It initializes and starts up the
    6.84 + * VMS system, then creates one processor from the specified function and
    6.85 + * puts it into the readyQ.  From that point, that one function is resp.
    6.86 + * for creating all the other processors, that then create others, and so
    6.87 + * forth.
    6.88 + *When all the processors, including the seed, have dissipated, then this
    6.89 + * function returns.  The results will have been written by side-effect via
    6.90 + * pointers read from, or written into initData.
    6.91 + *
    6.92 + *NOTE: no Threads should exist in the outside program that might touch
    6.93 + * any of the data reachable from initData passed in to here
    6.94 + */
    6.95 +void
    6.96 +VPThread__create_seed_procr_and_do_work( VirtProcrFnPtr fnPtr, void *initData )
    6.97 + { VPThreadSemEnv *semEnv;
    6.98 +   VirtProcr *seedPr;
    6.99 +
   6.100 +   #ifdef SEQUENTIAL
   6.101 +   VPThread__init_Seq();  //debug sequential exe
   6.102 +   #else
   6.103 +   VPThread__init();      //normal multi-thd
   6.104 +   #endif
   6.105 +   semEnv = _VMSMasterEnv->semanticEnv;
   6.106 +
   6.107 +      //VPThread starts with one processor, which is put into initial environ,
   6.108 +      // and which then calls create() to create more, thereby expanding work
   6.109 +   seedPr = VMS__create_procr( fnPtr, initData );
   6.110 +
   6.111 +   seedPr->coreAnimatedBy = semEnv->nextCoreToGetNewPr++;
   6.112 +
   6.113 +   writePrivQ( seedPr, semEnv->readyVPQs[seedPr->coreAnimatedBy] );
   6.114 +   semEnv->numVirtPr = 1;
   6.115 +
   6.116 +   #ifdef SEQUENTIAL
   6.117 +   VMS__start_the_work_then_wait_until_done_Seq();  //debug sequential exe
   6.118 +   #else
   6.119 +   VMS__start_the_work_then_wait_until_done();      //normal multi-thd
   6.120 +   #endif
   6.121 +
   6.122 +   VPThread__cleanup_after_shutdown();
   6.123 + }
   6.124 +
   6.125 +
   6.126 +//===========================================================================
   6.127 +
   6.128 +/*Initializes all the data-structures for a VPThread system -- but doesn't
   6.129 + * start it running yet!
   6.130 + *
   6.131 + * 
   6.132 + *This sets up the semantic layer over the VMS system
   6.133 + *
   6.134 + *First, calls VMS_Setup, then creates own environment, making it ready
   6.135 + * for creating the seed processor and then starting the work.
   6.136 + */
   6.137 +void
   6.138 +VPThread__init()
   6.139 + {
   6.140 +   VMS__init();
   6.141 +      //masterEnv, a global var, now is partially set up by init_VMS
   6.142 +
   6.143 +   VPThread__init_Helper();
   6.144 + }
   6.145 +
   6.146 +void
   6.147 +VPThread__init_Seq()
   6.148 + {
   6.149 +   VMS__init_Seq();
   6.150 +      //masterEnv, a global var, now is partially set up by init_VMS
   6.151 +
   6.152 +   VPThread__init_Helper();
   6.153 + }
   6.154 +
   6.155 +void
   6.156 +VPThread__init_Helper()
   6.157 + { VPThreadSemEnv       *semanticEnv;
   6.158 +   PrivQueueStruc **readyVPQs;
   6.159 +   int              coreIdx;
   6.160 + 
   6.161 +      //Hook up the semantic layer's plug-ins to the Master virt procr
   6.162 +   _VMSMasterEnv->requestHandler = &VPThread__Request_Handler;
   6.163 +   _VMSMasterEnv->slaveScheduler = &VPThread__schedule_virt_procr;
   6.164 +
   6.165 +      //create the semantic layer's environment (all its data) and add to
   6.166 +      // the master environment
   6.167 +   semanticEnv = malloc( sizeof( VPThreadSemEnv ) );
   6.168 +   _VMSMasterEnv->semanticEnv = semanticEnv;
   6.169 +
   6.170 +      //create the ready queue
   6.171 +   readyVPQs = malloc( NUM_CORES * sizeof(PrivQueueStruc *) );
   6.172 +
   6.173 +   for( coreIdx = 0; coreIdx < NUM_CORES; coreIdx++ )
   6.174 +    {
   6.175 +      readyVPQs[ coreIdx ] = makePrivQ();
   6.176 +    }
   6.177 +   
   6.178 +   semanticEnv->readyVPQs          = readyVPQs;
   6.179 +   
   6.180 +   semanticEnv->numVirtPr          = 0;
   6.181 +   semanticEnv->nextCoreToGetNewPr = 0;
   6.182 +
   6.183 +   semanticEnv->currMutexIdx       = 0;
   6.184 +   semanticEnv->mutexDynArray      = createDynArray32( INIT_NUM_MUTEX );
   6.185 +
   6.186 +   semanticEnv->currCondIdx        = 0;
   6.187 +   semanticEnv->condDynArray       = createDynArray32( INIT_NUM_COND );
   6.188 + }
   6.189 +
   6.190 +
   6.191 +/*Frees any memory allocated by VPThread__init() then calls VMS__shutdown
   6.192 + */
   6.193 +void
   6.194 +VPThread__cleanup_after_shutdown()
   6.195 + { VPThreadSemEnv *semEnv;
   6.196 +   int32           coreIdx,     idx,   highestIdx;
   6.197 +   VPTMutex      **mutexArray, *mutex;
   6.198 +   VPTCond       **condArray, *cond;
   6.199 + 
   6.200 +   semEnv = _VMSMasterEnv->semanticEnv;
   6.201 +
   6.202 +//TODO: double check that all sem env locations freed
   6.203 +
   6.204 +   for( coreIdx = 0; coreIdx < NUM_CORES; coreIdx++ )
   6.205 +    {
   6.206 +      free( semEnv->readyVPQs[coreIdx]->startOfData );
   6.207 +      free( semEnv->readyVPQs[coreIdx] );
   6.208 +    }
   6.209 +   
   6.210 +   free( semEnv->readyVPQs );
   6.211 +
   6.212 +   
   6.213 +   //==== Free mutexes and mutex array ====
   6.214 +   mutexArray = semEnv->mutexDynArray->array;
   6.215 +   highestIdx = semEnv->mutexDynArray->highestIdxInArray;
   6.216 +   for( idx=0; idx < highestIdx; idx++ )
   6.217 +    { mutex = mutexArray[ idx ];
   6.218 +      if( mutex == NULL ) continue;
   6.219 +      free( mutex );
   6.220 +    }
   6.221 +   free( mutexArray );
   6.222 +   free( semEnv->mutexDynArray );
   6.223 +   //======================================
   6.224 +   
   6.225 +
   6.226 +   //==== Free conds and cond array ====
   6.227 +   condArray  = semEnv->condDynArray->array;
   6.228 +   highestIdx = semEnv->condDynArray->highestIdxInArray;
   6.229 +   for( idx=0; idx < highestIdx; idx++ )
   6.230 +    { cond = condArray[ idx ];
   6.231 +      if( cond == NULL ) continue;
   6.232 +      free( cond );
   6.233 +    }
   6.234 +   free( condArray );
   6.235 +   free( semEnv->condDynArray );
   6.236 +   //===================================
   6.237 +
   6.238 +   
   6.239 +   free( _VMSMasterEnv->semanticEnv );
   6.240 +   VMS__cleanup_after_shutdown();
   6.241 + }
   6.242 +
   6.243 +
   6.244 +//===========================================================================
   6.245 +
   6.246 +/*
   6.247 + */
   6.248 +VirtProcr *
   6.249 +VPThread__create_thread( VirtProcrFnPtr fnPtr, void *initData,
   6.250 +                          VirtProcr *animPr )
   6.251 + { VPThreadSemReq *reqData;
   6.252 +
   6.253 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.254 +   reqData->reqType      = make_procr;
   6.255 +   reqData->initData     = initData;
   6.256 +   reqData->fnPtr        = fnPtr;
   6.257 +   reqData->requestingPr = animPr;
   6.258 +
   6.259 +   VMS__add_sem_request( reqData, animPr );
   6.260 +   VMS__suspend_procr( animPr ); //will suspend then resume and continue
   6.261 +   return animPr->semanticData;  //result communicated back via semData field
   6.262 + }
   6.263 +
   6.264 +
   6.265 +inline void
   6.266 +VPThread__dissipate_thread( VirtProcr *procrToDissipate )
   6.267 + {
   6.268 +   VMS__dissipate_procr( procrToDissipate );
   6.269 + }
   6.270 +
   6.271 +
   6.272 +//===========================================================================
   6.273 +
   6.274 +void
   6.275 +VPThread__set_globals_to( void *globals )
   6.276 + {
   6.277 +   ((VPThreadSemEnv *)
   6.278 +    (_VMSMasterEnv->semanticEnv))->applicationGlobals = globals;
   6.279 + }
   6.280 +
   6.281 +void *
   6.282 +VPThread__give_globals()
   6.283 + {
   6.284 +   return((VPThreadSemEnv *)
   6.285 +          (_VMSMasterEnv->semanticEnv))->applicationGlobals;
   6.286 + }
   6.287 +
   6.288 +
   6.289 +
   6.290 +//===========================================================================
   6.291 +
   6.292 +int32
   6.293 +VPThread__make_mutex( VirtProcr *animPr )
   6.294 + { VPThreadSemReq *reqData;
   6.295 +
   6.296 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.297 +   reqData->reqType      = make_mutex;
   6.298 +   reqData->requestingPr = animPr;
   6.299 +
   6.300 +   VMS__add_sem_request( reqData, animPr );
   6.301 +   VMS__suspend_procr( animPr ); //will suspend then resume and continue
   6.302 +   return animPr->semanticData;  //result communicated back via semData field
   6.303 + }
   6.304 +
   6.305 +void
   6.306 +VPThread__mutex_lock( int32 mutexIdx, VirtProcr *acquiringPr )
   6.307 + { VPThreadSemReq *reqData;
   6.308 +
   6.309 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.310 +   reqData->reqType      = mutex_lock;
   6.311 +   reqData->mutexIdx     = mutexIdx;
   6.312 +   reqData->requestingPr = acquiringPr;
   6.313 +
   6.314 +   VMS__add_sem_request( reqData, acquiringPr );
   6.315 +   VMS__suspend_procr( acquiringPr ); //will resume when has the lock
   6.316 + }
   6.317 +
   6.318 +void
   6.319 +VPThread__mutex_unlock( int32 mutexIdx, VirtProcr *releasingPr )
   6.320 + { VPThreadSemReq *reqData;
   6.321 +
   6.322 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.323 +   reqData->reqType      = mutex_unlock;
   6.324 +   reqData->mutexIdx     = mutexIdx;
   6.325 +   reqData->requestingPr = releasingPr;
   6.326 +
   6.327 +   VMS__add_sem_request( reqData, releasingPr );
   6.328 +   VMS__suspend_procr( releasingPr ); //lock released when resumes
   6.329 + }
   6.330 +
   6.331 +
   6.332 +//=======================
   6.333 +int32
   6.334 +VPThread__make_cond( int32 ownedMutexIdx, VirtProcr *animPr)
   6.335 + { VPThreadSemReq *reqData;
   6.336 +
   6.337 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.338 +   reqData->reqType      = make_cond;
   6.339 +   reqData->mutexIdx     = ownedMutexIdx;
   6.340 +   reqData->requestingPr = animPr;
   6.341 +
   6.342 +   VMS__add_sem_request( reqData, animPr );
   6.343 +   VMS__suspend_procr( animPr ); //will suspend then resume and continue
   6.344 +   return animPr->semanticData;  //result communicated back via semData field
   6.345 + }
   6.346 +
   6.347 +void
   6.348 +VPThread__cond_wait( int32 condIdx, VirtProcr *waitingPr)
   6.349 + { VPThreadSemReq *reqData;
   6.350 +
   6.351 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.352 +   reqData->reqType      = cond_wait;
   6.353 +   reqData->condIdx      = condIdx;
   6.354 +   reqData->requestingPr = waitingPr;
   6.355 +
   6.356 +   VMS__add_sem_request( reqData, waitingPr );
   6.357 +   VMS__suspend_procr( waitingPr ); //resume when signalled & has lock
   6.358 + }
   6.359 +
   6.360 +void *
   6.361 +VPThread__cond_signal( int32 condIdx, VirtProcr *signallingPr )
   6.362 + { VPThreadSemReq *reqData;
   6.363 +
   6.364 +   reqData = malloc( sizeof(VPThreadSemReq) );
   6.365 +   reqData->reqType      = cond_signal;
   6.366 +   reqData->condIdx      = condIdx;
   6.367 +   reqData->requestingPr = signallingPr;
   6.368 +
   6.369 +   VMS__add_sem_request( reqData, signallingPr );
   6.370 +   VMS__suspend_procr( signallingPr );//resumes right away, still having lock
   6.371 + }
   6.372 +//===========================================================================
   6.373 +
   6.374 +/*Just thin wrapper for now -- semantic request is still a simple thing
   6.375 + * (July 3, 2010)
   6.376 + */
   6.377 +inline void
   6.378 +VPThread__free_semantic_request( VPThreadSemReq *semReq )
   6.379 + {
   6.380 +   free( semReq );
   6.381 + }
   6.382 +