Mercurial > cgi-bin > hgwebdir.cgi > VMS > VMS_Implementations > VMS_impls > VMS__MC_shared_impl

annotate MasterLoop.c @ 208:eaf7e4c58c9e

find changesets by author, revision, files, or words in the commit message
Create common_ancestor brch -- all branches will be closed, then new ones created with this as the common ancestor of all branches -- it is incomplete! only code that is common to all HW and Feat and FeatDev branches is in here
author Some Random Person <seanhalle@yahoo.com>
date Wed, 22 Feb 2012 11:39:12 -0800
parents
children 0c83ea8adefc
rev   line source
seanhalle@208 1 /*
seanhalle@208 2 * Copyright 2010 OpenSourceStewardshipFoundation
seanhalle@208 3 *
seanhalle@208 4 * Licensed under BSD
seanhalle@208 5 */
seanhalle@208 6
seanhalle@208 7
seanhalle@208 8
seanhalle@208 9 #include <stdio.h>
seanhalle@208 10 #include <stddef.h>
seanhalle@208 11
seanhalle@208 12 #include "VMS.h"
seanhalle@208 13 #include "ProcrContext.h"
seanhalle@208 14
seanhalle@208 15
seanhalle@208 16 //===========================================================================
seanhalle@208 17 void inline
seanhalle@208 18 stealWorkInto( SchedSlot *currSlot, VMSQueueStruc *readyToAnimateQ,
seanhalle@208 19 SlaveVP *masterPr );
seanhalle@208 20
seanhalle@208 21 //===========================================================================
seanhalle@208 22
seanhalle@208 23
seanhalle@208 24
seanhalle@208 25 /*This code is animated by the virtual Master processor.
seanhalle@208 26 *
seanhalle@208 27 *Polls each sched slot exactly once, hands any requests made by a newly
seanhalle@208 28 * done slave to the "request handler" plug-in function
seanhalle@208 29 *
seanhalle@208 30 *Any slots that need a virt procr assigned are given to the "schedule"
seanhalle@208 31 * plug-in function, which tries to assign a virt procr (slave) to it.
seanhalle@208 32 *
seanhalle@208 33 *When all slots needing a processor have been given to the schedule plug-in,
seanhalle@208 34 * a fraction of the procrs successfully scheduled are put into the
seanhalle@208 35 * work queue, then a continuation of this function is put in, then the rest
seanhalle@208 36 * of the virt procrs that were successfully scheduled.
seanhalle@208 37 *
seanhalle@208 38 *The first thing the continuation does is busy-wait until the previous
seanhalle@208 39 * animation completes. This is because an (unlikely) continuation may
seanhalle@208 40 * sneak through queue before previous continuation is done putting second
seanhalle@208 41 * part of scheduled slaves in, which is the only race condition.
seanhalle@208 42 *
seanhalle@208 43 */
seanhalle@208 44
seanhalle@208 45 /*May 29, 2010 -- birth a Master during init so that first core loop to
seanhalle@208 46 * start running gets it and does all the stuff for a newly born --
seanhalle@208 47 * from then on, will be doing continuation, but do suspension self
seanhalle@208 48 * directly at end of master loop
seanhalle@208 49 *So VMS__init just births the master virtual processor same way it births
seanhalle@208 50 * all the others -- then does any extra setup needed and puts it into the
seanhalle@208 51 * work queue.
seanhalle@208 52 *However means have to make masterEnv a global static volatile the same way
seanhalle@208 53 * did with readyToAnimateQ in core loop. -- for performance, put the
seanhalle@208 54 * jump to the core loop directly in here, and have it directly jump back.
seanhalle@208 55 *
seanhalle@208 56 *
seanhalle@208 57 *Aug 18, 2010 -- Going to a separate MasterVP for each core, to see if this
seanhalle@208 58 * avoids the suspected bug in the system stack that causes bizarre faults
seanhalle@208 59 * at random places in the system code.
seanhalle@208 60 *
seanhalle@208 61 *So, this function is coupled to each of the MasterVPs, -- meaning this
seanhalle@208 62 * function can't rely on a particular stack and frame -- each MasterVP that
seanhalle@208 63 * animates this function has a different one.
seanhalle@208 64 *
seanhalle@208 65 *At this point, the masterLoop does not write itself into the queue anymore,
seanhalle@208 66 * instead, the coreLoop acquires the masterLock when it has nothing to
seanhalle@208 67 * animate, and then animates its own masterLoop. However, still try to put
seanhalle@208 68 * several AppVPs into the queue to amortize the startup cost of switching
seanhalle@208 69 * to the MasterVP. Note, don't have to worry about latency of requests much
seanhalle@208 70 * because most requests generate work for same core -- only latency issue
seanhalle@208 71 * is case when other cores starved and one core's requests generate work
seanhalle@208 72 * for them -- so keep max in queue to 3 or 4..
seanhalle@208 73 */
seanhalle@208 74 void masterLoop( void *initData, SlaveVP *animatingPr )
seanhalle@208 75 {
seanhalle@208 76 int32 slotIdx, numSlotsFilled;
seanhalle@208 77 SlaveVP *schedVirtPr;
seanhalle@208 78 SchedSlot *currSlot, **schedSlots;
seanhalle@208 79 MasterEnv *masterEnv;
seanhalle@208 80 VMSQueueStruc *readyToAnimateQ;
seanhalle@208 81
seanhalle@208 82 Sched_Assigner slaveScheduler;
seanhalle@208 83 RequestHandler requestHandler;
seanhalle@208 84 void *semanticEnv;
seanhalle@208 85
seanhalle@208 86 int32 thisCoresIdx;
seanhalle@208 87 SlaveVP *masterPr;
seanhalle@208 88 volatile SlaveVP *volatileMasterPr;
seanhalle@208 89
seanhalle@208 90 volatileMasterPr = animatingPr;
seanhalle@208 91 masterPr = (SlaveVP*)volatileMasterPr; //used to force re-define after jmp
seanhalle@208 92
seanhalle@208 93 //First animation of each MasterVP will in turn animate this part
seanhalle@208 94 // of setup code.. (VP creator sets up the stack as if this function
seanhalle@208 95 // was called normally, but actually get here by jmp)
seanhalle@208 96 //So, setup values about stack ptr, jmp pt and all that
seanhalle@208 97 //masterPr->resumeInstrPtr = &&masterLoopStartPt;
seanhalle@208 98
seanhalle@208 99
seanhalle@208 100 //Note, got rid of writing the stack and frame ptr up here, because
seanhalle@208 101 // only one
seanhalle@208 102 // core can ever animate a given MasterVP, so don't need to communicate
seanhalle@208 103 // new frame and stack ptr to the MasterVP storage before a second
seanhalle@208 104 // version of that MasterVP can get animated on a different core.
seanhalle@208 105 //Also got rid of the busy-wait.
seanhalle@208 106
seanhalle@208 107
seanhalle@208 108 //masterLoopStartPt:
seanhalle@208 109 while(1){
seanhalle@208 110
seanhalle@208 111 //============================= MEASUREMENT STUFF ========================
seanhalle@208 112 #ifdef MEAS__TIME_MASTER
seanhalle@208 113 //Total Master time includes one coreloop time -- just assume the core
seanhalle@208 114 // loop time is same for Master as for AppVPs, even though it may be
seanhalle@208 115 // smaller due to higher predictability of the fixed jmp.
seanhalle@208 116 saveLowTimeStampCountInto( masterPr->startMasterTSCLow );
seanhalle@208 117 #endif
seanhalle@208 118 //========================================================================
seanhalle@208 119
seanhalle@208 120 masterEnv = (MasterEnv*)_VMSMasterEnv;
seanhalle@208 121
seanhalle@208 122 //GCC may optimize so doesn't always re-define from frame-storage
seanhalle@208 123 masterPr = (SlaveVP*)volatileMasterPr; //just to make sure after jmp
seanhalle@208 124 thisCoresIdx = masterPr->coreAnimatedBy;
seanhalle@208 125 readyToAnimateQ = masterEnv->readyToAnimateQs[thisCoresIdx];
seanhalle@208 126 schedSlots = masterEnv->allSchedSlots[thisCoresIdx];
seanhalle@208 127
seanhalle@208 128 requestHandler = masterEnv->requestHandler;
seanhalle@208 129 slaveScheduler = masterEnv->slaveSchedAssigner;
seanhalle@208 130 semanticEnv = masterEnv->semanticEnv;
seanhalle@208 131
seanhalle@208 132
seanhalle@208 133 //Poll each slot's Done flag
seanhalle@208 134 numSlotsFilled = 0;
seanhalle@208 135 for( slotIdx = 0; slotIdx < NUM_SCHED_SLOTS; slotIdx++)
seanhalle@208 136 {
seanhalle@208 137 currSlot = schedSlots[ slotIdx ];
seanhalle@208 138
seanhalle@208 139 if( currSlot->workIsDone )
seanhalle@208 140 {
seanhalle@208 141 currSlot->workIsDone = FALSE;
seanhalle@208 142 currSlot->needsProcrAssigned = TRUE;
seanhalle@208 143
seanhalle@208 144 //process requests from slave to master
seanhalle@208 145 //====================== MEASUREMENT STUFF ===================
seanhalle@208 146 #ifdef MEAS__TIME_PLUGIN
seanhalle@208 147 int32 startStamp1, endStamp1;
seanhalle@208 148 saveLowTimeStampCountInto( startStamp1 );
seanhalle@208 149 #endif
seanhalle@208 150 //============================================================
seanhalle@208 151 (*requestHandler)( currSlot->procrAssignedToSlot, semanticEnv );
seanhalle@208 152 //====================== MEASUREMENT STUFF ===================
seanhalle@208 153 #ifdef MEAS__TIME_PLUGIN
seanhalle@208 154 saveLowTimeStampCountInto( endStamp1 );
seanhalle@208 155 addIntervalToHist( startStamp1, endStamp1,
seanhalle@208 156 _VMSMasterEnv->reqHdlrLowTimeHist );
seanhalle@208 157 addIntervalToHist( startStamp1, endStamp1,
seanhalle@208 158 _VMSMasterEnv->reqHdlrHighTimeHist );
seanhalle@208 159 #endif
seanhalle@208 160 //============================================================
seanhalle@208 161 }
seanhalle@208 162 if( currSlot->needsProcrAssigned )
seanhalle@208 163 { //give slot a new virt procr
seanhalle@208 164 schedVirtPr =
seanhalle@208 165 (*slaveScheduler)( semanticEnv, thisCoresIdx );
seanhalle@208 166
seanhalle@208 167 if( schedVirtPr != NULL )
seanhalle@208 168 { currSlot->procrAssignedToSlot = schedVirtPr;
seanhalle@208 169 schedVirtPr->schedSlot = currSlot;
seanhalle@208 170 currSlot->needsProcrAssigned = FALSE;
seanhalle@208 171 numSlotsFilled += 1;
seanhalle@208 172
seanhalle@208 173 writeVMSQ( schedVirtPr, readyToAnimateQ );
seanhalle@208 174 }
seanhalle@208 175 }
seanhalle@208 176 }
seanhalle@208 177
seanhalle@208 178
seanhalle@208 179 #ifdef USE_WORK_STEALING
seanhalle@208 180 //If no slots filled, means no more work, look for work to steal.
seanhalle@208 181 if( numSlotsFilled == 0 )
seanhalle@208 182 { gateProtected_stealWorkInto( currSlot, readyToAnimateQ, masterPr );
seanhalle@208 183 }
seanhalle@208 184 #endif
seanhalle@208 185
seanhalle@208 186
seanhalle@208 187 #ifdef MEAS__TIME_MASTER
seanhalle@208 188 saveLowTimeStampCountInto( masterPr->endMasterTSCLow );
seanhalle@208 189 #endif
seanhalle@208 190
seanhalle@208 191 masterSwitchToCoreLoop(animatingPr);
seanhalle@208 192 flushRegisters();
seanhalle@208 193 }//MasterLoop
seanhalle@208 194
seanhalle@208 195
seanhalle@208 196 }
seanhalle@208 197
seanhalle@208 198
seanhalle@208 199
seanhalle@208 200 /*This has a race condition -- the coreloops are accessing their own queues
seanhalle@208 201 * at the same time that this work-stealer on a different core is trying to
seanhalle@208 202 */
seanhalle@208 203 void inline
seanhalle@208 204 stealWorkInto( SchedSlot *currSlot, VMSQueueStruc *readyToAnimateQ,
seanhalle@208 205 SlaveVP *masterPr )
seanhalle@208 206 {
seanhalle@208 207 SlaveVP *stolenPr;
seanhalle@208 208 int32 coreIdx, i;
seanhalle@208 209 VMSQueueStruc *currQ;
seanhalle@208 210
seanhalle@208 211 stolenPr = NULL;
seanhalle@208 212 coreIdx = masterPr->coreAnimatedBy;
seanhalle@208 213 for( i = 0; i < NUM_CORES -1; i++ )
seanhalle@208 214 {
seanhalle@208 215 if( coreIdx >= NUM_CORES -1 )
seanhalle@208 216 { coreIdx = 0;
seanhalle@208 217 }
seanhalle@208 218 else
seanhalle@208 219 { coreIdx++;
seanhalle@208 220 }
seanhalle@208 221 currQ = _VMSMasterEnv->readyToAnimateQs[coreIdx];
seanhalle@208 222 if( numInVMSQ( currQ ) > 0 )
seanhalle@208 223 { stolenPr = readVMSQ (currQ );
seanhalle@208 224 break;
seanhalle@208 225 }
seanhalle@208 226 }
seanhalle@208 227
seanhalle@208 228 if( stolenPr != NULL )
seanhalle@208 229 { currSlot->procrAssignedToSlot = stolenPr;
seanhalle@208 230 stolenPr->schedSlot = currSlot;
seanhalle@208 231 currSlot->needsProcrAssigned = FALSE;
seanhalle@208 232
seanhalle@208 233 writeVMSQ( stolenPr, readyToAnimateQ );
seanhalle@208 234 }
seanhalle@208 235 }
seanhalle@208 236
seanhalle@208 237 /*This algorithm makes the common case fast. Make the coreloop passive,
seanhalle@208 238 * and show its progress. Make the stealer control a gate that coreloop
seanhalle@208 239 * has to pass.
seanhalle@208 240 *To avoid interference, only one stealer at a time. Use a global
seanhalle@208 241 * stealer-lock.
seanhalle@208 242 *
seanhalle@208 243 *The pattern is based on a gate -- stealer shuts the gate, then monitors
seanhalle@208 244 * to be sure any already past make it all the way out, before starting.
seanhalle@208 245 *So, have a "progress" measure just before the gate, then have two after it,
seanhalle@208 246 * one is in a "waiting room" outside the gate, the other is at the exit.
seanhalle@208 247 *Then, the stealer first shuts the gate, then checks the progress measure
seanhalle@208 248 * outside it, then looks to see if the progress measure at the exit is the
seanhalle@208 249 * same. If yes, it knows the protected area is empty 'cause no other way
seanhalle@208 250 * to get in and the last to get in also exited.
seanhalle@208 251 *If the progress measure at the exit is not the same, then the stealer goes
seanhalle@208 252 * into a loop checking both the waiting-area and the exit progress-measures
seanhalle@208 253 * until one of them shows the same as the measure outside the gate. Might
seanhalle@208 254 * as well re-read the measure outside the gate each go around, just to be
seanhalle@208 255 * sure. It is guaranteed that one of the two will eventually match the one
seanhalle@208 256 * outside the gate.
seanhalle@208 257 *
seanhalle@208 258 *Here's an informal proof of correctness:
seanhalle@208 259 *The gate can be closed at any point, and have only four cases:
seanhalle@208 260 * 1) coreloop made it past the gate-closing but not yet past the exit
seanhalle@208 261 * 2) coreloop made it past the pre-gate progress update but not yet past
seanhalle@208 262 * the gate,
seanhalle@208 263 * 3) coreloop is right before the pre-gate update
seanhalle@208 264 * 4) coreloop is past the exit and far from the pre-gate update.
seanhalle@208 265 *
seanhalle@208 266 * Covering the cases in reverse order,
seanhalle@208 267 * 4) is not a problem -- stealer will read pre-gate progress, see that it
seanhalle@208 268 * matches exit progress, and the gate is closed, so stealer can proceed.
seanhalle@208 269 * 3) stealer will read pre-gate progress just after coreloop updates it..
seanhalle@208 270 * so stealer goes into a loop until the coreloop causes wait-progress
seanhalle@208 271 * to match pre-gate progress, so then stealer can proceed
seanhalle@208 272 * 2) same as 3..
seanhalle@208 273 * 1) stealer reads pre-gate progress, sees that it's different than exit,
seanhalle@208 274 * so goes into loop until exit matches pre-gate, now it knows coreloop
seanhalle@208 275 * is not in protected and cannot get back in, so can proceed.
seanhalle@208 276 *
seanhalle@208 277 *Implementation for the stealer:
seanhalle@208 278 *
seanhalle@208 279 *First, acquire the stealer lock -- only cores with no work to do will
seanhalle@208 280 * compete to steal, so not a big performance penalty having only one --
seanhalle@208 281 * will rarely have multiple stealers in a system with plenty of work -- and
seanhalle@208 282 * in a system with little work, it doesn't matter.
seanhalle@208 283 *
seanhalle@208 284 *Note, have single-reader, single-writer pattern for all variables used to
seanhalle@208 285 * communicate between stealer and victims
seanhalle@208 286 *
seanhalle@208 287 *So, scan the queues of the core loops, until find non-empty. Each core
seanhalle@208 288 * has its own list that it scans. The list goes in order from closest to
seanhalle@208 289 * furthest core, so it steals first from close cores. Later can add
seanhalle@208 290 * taking info from the app about overlapping footprints, and scan all the
seanhalle@208 291 * others then choose work with the most footprint overlap with the contents
seanhalle@208 292 * of this core's cache.
seanhalle@208 293 *
seanhalle@208 294 *Now, have a victim want to take work from. So, shut the gate in that
seanhalle@208 295 * coreloop, by setting the "gate closed" var on its stack to TRUE.
seanhalle@208 296 *Then, read the core's pre-gate progress and compare to the core's exit
seanhalle@208 297 * progress.
seanhalle@208 298 *If same, can proceed to take work from the coreloop's queue. When done,
seanhalle@208 299 * write FALSE to gate closed var.
seanhalle@208 300 *If different, then enter a loop that reads the pre-gate progress, then
seanhalle@208 301 * compares to exit progress then to wait progress. When one of two
seanhalle@208 302 * matches, proceed. Take work from the coreloop's queue. When done,
seanhalle@208 303 * write FALSE to the gate closed var.
seanhalle@208 304 *
seanhalle@208 305 */
seanhalle@208 306 void inline
seanhalle@208 307 gateProtected_stealWorkInto( SchedSlot *currSlot,
seanhalle@208 308 VMSQueueStruc *myReadyToAnimateQ,
seanhalle@208 309 SlaveVP *masterPr )
seanhalle@208 310 {
seanhalle@208 311 SlaveVP *stolenPr;
seanhalle@208 312 int32 coreIdx, i, haveAVictim, gotLock;
seanhalle@208 313 VMSQueueStruc *victimsQ;
seanhalle@208 314
seanhalle@208 315 volatile GateStruc *vicGate;
seanhalle@208 316 int32 coreMightBeInProtected;
seanhalle@208 317
seanhalle@208 318
seanhalle@208 319
seanhalle@208 320 //see if any other cores have work available to steal
seanhalle@208 321 haveAVictim = FALSE;
seanhalle@208 322 coreIdx = masterPr->coreAnimatedBy;
seanhalle@208 323 for( i = 0; i < NUM_CORES -1; i++ )
seanhalle@208 324 {
seanhalle@208 325 if( coreIdx >= NUM_CORES -1 )
seanhalle@208 326 { coreIdx = 0;
seanhalle@208 327 }
seanhalle@208 328 else
seanhalle@208 329 { coreIdx++;
seanhalle@208 330 }
seanhalle@208 331 victimsQ = _VMSMasterEnv->readyToAnimateQs[coreIdx];
seanhalle@208 332 if( numInVMSQ( victimsQ ) > 0 )
seanhalle@208 333 { haveAVictim = TRUE;
seanhalle@208 334 vicGate = _VMSMasterEnv->workStealingGates[ coreIdx ];
seanhalle@208 335 break;
seanhalle@208 336 }
seanhalle@208 337 }
seanhalle@208 338 if( !haveAVictim ) return; //no work to steal, exit
seanhalle@208 339
seanhalle@208 340 //have a victim core, now get the stealer-lock
seanhalle@208 341 gotLock =__sync_bool_compare_and_swap( &(_VMSMasterEnv->workStealingLock),
seanhalle@208 342 UNLOCKED, LOCKED );
seanhalle@208 343 if( !gotLock ) return; //go back to core loop, which will re-start master
seanhalle@208 344
seanhalle@208 345
seanhalle@208 346 //====== Start Gate-protection =======
seanhalle@208 347 vicGate->gateClosed = TRUE;
seanhalle@208 348 coreMightBeInProtected= vicGate->preGateProgress != vicGate->exitProgress;
seanhalle@208 349 while( coreMightBeInProtected )
seanhalle@208 350 { //wait until sure
seanhalle@208 351 if( vicGate->preGateProgress == vicGate->waitProgress )
seanhalle@208 352 coreMightBeInProtected = FALSE;
seanhalle@208 353 if( vicGate->preGateProgress == vicGate->exitProgress )
seanhalle@208 354 coreMightBeInProtected = FALSE;
seanhalle@208 355 }
seanhalle@208 356
seanhalle@208 357 stolenPr = readVMSQ ( victimsQ );
seanhalle@208 358
seanhalle@208 359 vicGate->gateClosed = FALSE;
seanhalle@208 360 //======= End Gate-protection =======
seanhalle@208 361
seanhalle@208 362
seanhalle@208 363 if( stolenPr != NULL ) //victim could have been in protected and taken
seanhalle@208 364 { currSlot->procrAssignedToSlot = stolenPr;
seanhalle@208 365 stolenPr->schedSlot = currSlot;
seanhalle@208 366 currSlot->needsProcrAssigned = FALSE;
seanhalle@208 367
seanhalle@208 368 writeVMSQ( stolenPr, myReadyToAnimateQ );
seanhalle@208 369 }
seanhalle@208 370
seanhalle@208 371 //unlock the work stealing lock
seanhalle@208 372 _VMSMasterEnv->workStealingLock = UNLOCKED;
seanhalle@208 373 }