1 /* ScummVM - Graphic Adventure Engine 2 * 3 * ScummVM is the legal property of its developers, whose names 4 * are too numerous to list here. Please refer to the COPYRIGHT 5 * file distributed with this source distribution. 6 * 7 * This program is free software; you can redistribute it and/or 8 * modify it under the terms of the GNU General Public License 9 * as published by the Free Software Foundation; either version 2 10 * of the License, or (at your option) any later version. 11 * 12 * This program is distributed in the hope that it will be useful, 13 * but WITHOUT ANY WARRANTY; without even the implied warranty of 14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 * GNU General Public License for more details. 16 * 17 * You should have received a copy of the GNU General Public License 18 * along with this program; if not, write to the Free Software 19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. 20 * 21 */ 22 23 #ifndef COMMON_COROUTINES_H 24 #define COMMON_COROUTINES_H 25 26 #include "common/scummsys.h" 27 #include "common/util.h" // for SCUMMVM_CURRENT_FUNCTION 28 #include "common/list.h" 29 #include "common/singleton.h" 30 31 namespace Common { 32 33 /** 34 * @defgroup Coroutine support for simulating multi-threading. 35 * 36 * The following is loosely based on an article by Simon Tatham: 37 * <http://www.chiark.greenend.org.uk/~sgtatham/coroutines.html>. 38 * However, many improvements and tweaks have been made, in particular 39 * by taking advantage of C++ features not available in C. 40 */ 41 //@{ 42 43 #define CoroScheduler (Common::CoroutineScheduler::instance()) 44 45 46 // Enable this macro to enable some debugging support in the coroutine code. 47 //#define COROUTINE_DEBUG 48 49 /** 50 * The core of any coroutine context which captures the 'state' of a coroutine. 51 * Private use only. 52 */ 53 struct CoroBaseContext { 54 int _line; 55 int _sleep; 56 CoroBaseContext *_subctx; 57 #ifdef COROUTINE_DEBUG 58 const char *_funcName; 59 #endif 60 /** 61 * Creates a coroutine context 62 */ 63 CoroBaseContext(const char *func); 64 65 /** 66 * Destructor for coroutine context 67 */ 68 virtual ~CoroBaseContext(); 69 }; 70 71 typedef CoroBaseContext *CoroContext; 72 73 74 /** This is a special constant that can be temporarily used as a parameter to call coroutine-ised 75 * methods from code that haven't yet been converted to being a coroutine, so code at least 76 * compiles correctly. Be aware, though, that an error will occur if a coroutine that was passed 77 * the nullContext tries to sleep or yield control. 78 */ 79 extern CoroContext nullContext; 80 81 /** 82 * Wrapper class which holds a pointer to a pointer to a CoroBaseContext. 83 * The interesting part is the destructor, which kills the context being held, 84 * but ONLY if the _sleep val of that context is zero. This way, a coroutine 85 * can just 'return' w/o having to worry about freeing the allocated context 86 * (in Simon Tatham's original code, one had to use a special macro to 87 * return from a coroutine). 88 */ 89 class CoroContextHolder { 90 CoroContext &_ctx; 91 public: CoroContextHolder(CoroContext & ctx)92 CoroContextHolder(CoroContext &ctx) : _ctx(ctx) { 93 assert(ctx); 94 assert(ctx->_sleep >= 0); 95 ctx->_sleep = 0; 96 } ~CoroContextHolder()97 ~CoroContextHolder() { 98 if (_ctx && _ctx->_sleep == 0) { 99 delete _ctx; 100 _ctx = nullptr; 101 } 102 } 103 }; 104 105 /** Methods that have been converted to being a coroutine should have this as the first parameter */ 106 #define CORO_PARAM Common::CoroContext &coroParam 107 108 109 /** 110 * Begin the declaration of a coroutine context. 111 * This allows declaring variables which are 'persistent' during the 112 * lifetime of the coroutine. An example use would be: 113 * 114 * CORO_BEGIN_CONTEXT; 115 * int var; 116 * char *foo; 117 * CORO_END_CONTEXT(_ctx); 118 * 119 * It is not possible to initialize variables here, due to the way this 120 * macro is implemented. Furthermore, to use the variables declared in 121 * the coroutine context, you have to access them via the context variable 122 * name that was specified as parameter to CORO_END_CONTEXT, e.g. 123 * _ctx->var = 0; 124 * 125 * @see CORO_END_CONTEXT 126 * 127 * @note We declare a variable 'DUMMY' to allow the user to specify an 'empty' 128 * context, and so compilers won't complain about ";" following the macro. 129 */ 130 #define CORO_BEGIN_CONTEXT \ 131 struct CoroContextTag : Common::CoroBaseContext { \ 132 CoroContextTag() : CoroBaseContext(SCUMMVM_CURRENT_FUNCTION) { DUMMY = 0; } \ 133 int DUMMY 134 135 /** 136 * End the declaration of a coroutine context. 137 * @param x name of the coroutine context 138 * @see CORO_BEGIN_CONTEXT 139 */ 140 #define CORO_END_CONTEXT(x) } *x = (CoroContextTag *)coroParam 141 142 /** 143 * Begin the code section of a coroutine. 144 * @param x name of the coroutine context 145 * @see CORO_BEGIN_CODE 146 */ 147 #define CORO_BEGIN_CODE(x) \ 148 if (&coroParam == &Common::nullContext) assert(!Common::nullContext); \ 149 if (!x) { coroParam = x = new CoroContextTag(); } \ 150 x->DUMMY = 0; \ 151 Common::CoroContextHolder tmpHolder(coroParam); \ 152 switch (coroParam->_line) { case 0:; 153 154 /** 155 * End the code section of a coroutine. 156 * @see CORO_END_CODE 157 */ 158 #define CORO_END_CODE \ 159 if (&coroParam == &Common::nullContext) { \ 160 delete Common::nullContext; \ 161 Common::nullContext = NULL; \ 162 } \ 163 } 164 165 /** 166 * Sleep for the specified number of scheduler cycles. 167 */ 168 #define CORO_SLEEP(delay) \ 169 do { \ 170 coroParam->_line = __LINE__; \ 171 coroParam->_sleep = delay; \ 172 assert(&coroParam != &Common::nullContext); \ 173 return; case __LINE__:; \ 174 } while (0) 175 176 #define CORO_GIVE_WAY do { CoroScheduler.giveWay(); CORO_SLEEP(1); } while (0) 177 #define CORO_RESCHEDULE do { CoroScheduler.reschedule(); CORO_SLEEP(1); } while (0) 178 179 /** 180 * Stop the currently running coroutine and all calling coroutines. 181 * 182 * This sets _sleep to -1 rather than 0 so that the context doesn't get 183 * deleted by CoroContextHolder, since we want CORO_INVOKE_ARGS to 184 * propogate the _sleep value and return immediately (the scheduler will 185 * then delete the entire coroutine's state, including all subcontexts). 186 */ 187 #define CORO_KILL_SELF() \ 188 do { if (&coroParam != &Common::nullContext) { coroParam->_sleep = -1; } return; } while (0) 189 190 191 /** 192 * This macro is to be used in conjunction with CORO_INVOKE_ARGS and 193 * similar macros for calling coroutines-enabled subroutines. 194 */ 195 #define CORO_SUBCTX coroParam->_subctx 196 197 /** 198 * Invoke another coroutine. 199 * 200 * If the subcontext still exists after the coroutine is invoked, it has 201 * either yielded/slept or killed itself, and so we copy the _sleep value 202 * to our own context and return (execution will continue at the case 203 * statement below, where we loop and call the coroutine again). 204 * If the subcontext is null, the coroutine ended normally, and we can 205 * simply break out of the loop and continue execution. 206 * 207 * @param subCoro name of the coroutine-enabled function to invoke 208 * @param ARGS list of arguments to pass to subCoro 209 * 210 * @note ARGS must be surrounded by parentheses, and the first argument 211 * in this list must always be CORO_SUBCTX. For example, the 212 * regular function call 213 * myFunc(a, b); 214 * becomes the following: 215 * CORO_INVOKE_ARGS(myFunc, (CORO_SUBCTX, a, b)); 216 */ 217 #define CORO_INVOKE_ARGS(subCoro, ARGS) \ 218 do { \ 219 coroParam->_line = __LINE__; \ 220 coroParam->_subctx = 0; \ 221 do { \ 222 subCoro ARGS; \ 223 if (!coroParam->_subctx) break; \ 224 coroParam->_sleep = coroParam->_subctx->_sleep; \ 225 assert(&coroParam != &Common::nullContext); \ 226 return; case __LINE__:; \ 227 } while (1); \ 228 } while (0) 229 230 /** 231 * Invoke another coroutine. Similar to CORO_INVOKE_ARGS, 232 * but allows specifying a return value which is returned 233 * if invoked coroutine yields (thus causing the current 234 * coroutine to yield, too). 235 */ 236 #define CORO_INVOKE_ARGS_V(subCoro, RESULT, ARGS) \ 237 do { \ 238 coroParam->_line = __LINE__; \ 239 coroParam->_subctx = 0; \ 240 do { \ 241 subCoro ARGS; \ 242 if (!coroParam->_subctx) break; \ 243 coroParam->_sleep = coroParam->_subctx->_sleep; \ 244 assert(&coroParam != &Common::nullContext); \ 245 return RESULT; case __LINE__:; \ 246 } while (1); \ 247 } while (0) 248 249 /** 250 * Convenience wrapper for CORO_INVOKE_ARGS for invoking a coroutine 251 * with no parameters. 252 */ 253 #define CORO_INVOKE_0(subCoroutine) \ 254 CORO_INVOKE_ARGS(subCoroutine, (CORO_SUBCTX)) 255 256 /** 257 * Convenience wrapper for CORO_INVOKE_ARGS for invoking a coroutine 258 * with one parameter. 259 */ 260 #define CORO_INVOKE_1(subCoroutine, a0) \ 261 CORO_INVOKE_ARGS(subCoroutine, (CORO_SUBCTX, a0)) 262 263 /** 264 * Convenience wrapper for CORO_INVOKE_ARGS for invoking a coroutine 265 * with two parameters. 266 */ 267 #define CORO_INVOKE_2(subCoroutine, a0,a1) \ 268 CORO_INVOKE_ARGS(subCoroutine, (CORO_SUBCTX, a0, a1)) 269 270 /** 271 * Convenience wrapper for CORO_INVOKE_ARGS for invoking a coroutine 272 * with three parameters. 273 */ 274 #define CORO_INVOKE_3(subCoroutine, a0,a1,a2) \ 275 CORO_INVOKE_ARGS(subCoroutine, (CORO_SUBCTX, a0, a1, a2)) 276 277 /** 278 * Convenience wrapper for CORO_INVOKE_ARGS for invoking a coroutine 279 * with four parameters. 280 */ 281 #define CORO_INVOKE_4(subCoroutine, a0,a1,a2,a3) \ 282 CORO_INVOKE_ARGS(subCoroutine, (CORO_SUBCTX, a0, a1, a2, a3)) 283 284 285 286 // the size of process specific info 287 #define CORO_PARAM_SIZE 32 288 289 // the maximum number of processes 290 #define CORO_NUM_PROCESS 100 291 #define CORO_MAX_PROCESSES 100 292 #define CORO_MAX_PID_WAITING 5 293 294 #define CORO_INFINITE 0xffffffff 295 #define CORO_INVALID_PID_VALUE 0 296 297 /** Coroutine parameter for methods converted to coroutines */ 298 typedef void (*CORO_ADDR)(CoroContext &, const void *); 299 300 /** process structure */ 301 struct PROCESS { 302 PROCESS *pNext; ///< pointer to next process in active or free list 303 PROCESS *pPrevious; ///< pointer to previous process in active or free list 304 305 CoroContext state; ///< the state of the coroutine 306 CORO_ADDR coroAddr; ///< the entry point of the coroutine 307 308 int sleepTime; ///< number of scheduler cycles to sleep 309 uint32 pid; ///< process ID 310 uint32 pidWaiting[CORO_MAX_PID_WAITING]; ///< Process ID(s) process is currently waiting on 311 char param[CORO_PARAM_SIZE]; ///< process specific info 312 }; 313 typedef PROCESS *PPROCESS; 314 315 316 /** Event structure */ 317 struct EVENT { 318 uint32 pid; 319 bool manualReset; 320 bool signalled; 321 bool pulsing; 322 }; 323 324 325 /** 326 * Creates and manages "processes" (really coroutines). 327 */ 328 class CoroutineScheduler : public Singleton<CoroutineScheduler> { 329 public: 330 /** Pointer to a function of the form "void function(PPROCESS)" */ 331 typedef void (*VFPTRPP)(PROCESS *); 332 333 private: 334 friend class Singleton<CoroutineScheduler>; 335 336 /** 337 * Constructor 338 */ 339 CoroutineScheduler(); 340 341 /** 342 * Destructor 343 */ 344 ~CoroutineScheduler(); 345 346 347 /** list of all processes */ 348 PROCESS *processList; 349 350 /** active process list - also saves scheduler state */ 351 PROCESS *active; 352 353 /** pointer to free process list */ 354 PROCESS *pFreeProcesses; 355 356 /** the currently active process */ 357 PROCESS *pCurrent; 358 359 /** Auto-incrementing process Id */ 360 int pidCounter; 361 362 /** Event list */ 363 Common::List<EVENT *> _events; 364 365 #ifdef DEBUG 366 // diagnostic process counters 367 int numProcs; 368 int maxProcs; 369 370 /** 371 * Checks both the active and free process list to insure all the links are valid, 372 * and that no processes have been lost 373 */ 374 void checkStack(); 375 #endif 376 377 /** 378 * Called from killProcess() to enable other resources 379 * a process may be allocated to be released. 380 */ 381 VFPTRPP pRCfunction; 382 383 PROCESS *getProcess(uint32 pid); 384 EVENT *getEvent(uint32 pid); 385 public: 386 /** 387 * Kills all processes and places them on the free list. 388 */ 389 void reset(); 390 391 #ifdef DEBUG 392 /** 393 * Shows the maximum number of process used at once. 394 */ 395 void printStats(); 396 #endif 397 398 /** 399 * Give all active processes a chance to run 400 */ 401 void schedule(); 402 403 /** 404 * Reschedules all the processes to run again this tick 405 */ 406 void rescheduleAll(); 407 408 /** 409 * If the specified process has already run on this tick, make it run 410 * again on the current tick. 411 */ 412 void reschedule(PPROCESS pReSchedProc = nullptr); 413 414 /** 415 * Moves the specified process to the end of the dispatch queue 416 * allowing it to run again within the current game cycle. 417 * @param pGiveProc Which process 418 */ 419 void giveWay(PPROCESS pReSchedProc = nullptr); 420 421 /** 422 * Continously makes a given process wait for another process to finish or event to signal. 423 * 424 * @param pid Process/Event identifier 425 * @param duration Duration in milliseconds 426 * @param expired If specified, set to true if delay period expired 427 */ 428 void waitForSingleObject(CORO_PARAM, int pid, uint32 duration, bool *expired = nullptr); 429 430 /** 431 * Continously makes a given process wait for given prcesses to finished or events to be set 432 * 433 * @param nCount Number of Id's being passed 434 * @param evtList List of pids to wait for 435 * @param bWaitAll Specifies whether all or any of the processes/events 436 * @param duration Duration in milliseconds 437 * @param expired Set to true if delay period expired 438 */ 439 void waitForMultipleObjects(CORO_PARAM, int nCount, uint32 *pidList, bool bWaitAll, 440 uint32 duration, bool *expired = nullptr); 441 442 /** 443 * Make the active process sleep for the given duration in milliseconds 444 * 445 * @param duration Duration in milliseconds 446 * @remarks This duration won't be precise, since it relies on the frequency the 447 * scheduler is called. 448 */ 449 void sleep(CORO_PARAM, uint32 duration); 450 451 /** 452 * Creates a new process. 453 * 454 * @param pid process identifier 455 * @param coroAddr Coroutine start address 456 * @param pParam Process specific info 457 * @param sizeParam Size of process specific info 458 */ 459 PROCESS *createProcess(uint32 pid, CORO_ADDR coroAddr, const void *pParam, int sizeParam); 460 461 /** 462 * Creates a new process with an auto-incrementing Process Id. 463 * 464 * @param coroAddr Coroutine start address 465 * @param pParam Process specific info 466 * @param sizeParam Size of process specific info 467 */ 468 uint32 createProcess(CORO_ADDR coroAddr, const void *pParam, int sizeParam); 469 470 /** 471 * Creates a new process with an auto-incrementing Process Id, and a single pointer parameter. 472 * 473 * @param coroAddr Coroutine start address 474 * @param pParam Process specific info 475 */ 476 uint32 createProcess(CORO_ADDR coroAddr, const void *pParam); 477 478 /** 479 * Kills the specified process. 480 * 481 * @param pKillProc Which process to kill 482 */ 483 void killProcess(PROCESS *pKillProc); 484 485 /** 486 * Returns a pointer to the currently running process. 487 */ 488 PROCESS *getCurrentProcess(); 489 490 /** 491 * Returns the process identifier of the currently running process. 492 */ 493 int getCurrentPID() const; 494 495 /** 496 * Kills any process matching the specified PID. The current 497 * process cannot be killed. 498 * 499 * @param pidKill Process identifier of process to kill 500 * @param pidMask Mask to apply to process identifiers before comparison 501 * @return The number of processes killed is returned. 502 */ 503 int killMatchingProcess(uint32 pidKill, int pidMask = -1); 504 505 /** 506 * Set pointer to a function to be called by killProcess(). 507 * 508 * May be called by a resource allocator, the function supplied is 509 * called by killProcess() to allow the resource allocator to free 510 * resources allocated to the dying process. 511 * 512 * @param pFunc Function to be called by killProcess() 513 */ 514 void setResourceCallback(VFPTRPP pFunc); 515 516 /* Event methods */ 517 /** 518 * Creates a new event (semaphore) object 519 * 520 * @param bManualReset Events needs to be manually reset. Otherwise, 521 * events will be automatically reset after a 522 * process waits on the event finishes 523 * @param bInitialState Specifies whether the event is signalled or not 524 * initially 525 */ 526 uint32 createEvent(bool bManualReset, bool bInitialState); 527 528 /** 529 * Destroys the given event 530 * @param pidEvent Event Process Id 531 */ 532 void closeEvent(uint32 pidEvent); 533 534 /** 535 * Sets the event 536 * @param pidEvent Event Process Id 537 */ 538 void setEvent(uint32 pidEvent); 539 540 /** 541 * Resets the event 542 * @param pidEvent Event Process Id 543 */ 544 void resetEvent(uint32 pidEvent); 545 546 /** 547 * Temporarily sets a given event to true, and then runs all waiting 548 * processes,allowing any processes waiting on the event to be fired. It 549 * then immediately resets the event again. 550 * 551 * @param pidEvent Event Process Id 552 * 553 * @remarks Should not be run inside of another process 554 */ 555 void pulseEvent(uint32 pidEvent); 556 }; 557 558 //@} 559 560 } // end of namespace Common 561 562 #endif // COMMON_COROUTINES_H 563