Allow thread switching within kernel functions

[StrikerX3]

While implementing the custom Xbox kernel outside of the emulated environment, I found that some of the kernel functions need to suspend execution due to various reasons (yielding, waiting for a signal, trying to enter a locked critical section).

Since we cannot suspend execution of the host thread, we need to figure out a way to allow the emulator to "suspend" execution of the host thread (but not really) and continue with the emulation, so that at a later point in time, when the suspension condition is no longer met, the original thread can resume execution from the point where it stopped.

[StrikerX3]

A possible solution (essentially a thread-based coroutine mechanism):

When a thread is going to be suspended because it is about to wait for an object, enter a locked critical section, yield, or a similar reason:

1. Create a single-shot synchronization object starting with an unsignaled state. (A Win32 Event would work, but prefer something similar using glib since it is portable and already a dependency.)
2. Establish a condition based on the cause of the thread suspension. (See below for examples of conditions.)
3. Save the CPU context of the current guest thread. (Probably unnecessary, but better safe than sorry.)
4. Build an object containing the condition, the current guest thread and the synchronization object and add it to the list of suspended threads.
5. Mark the current guest thread as suspended.
6. Create a host thread that will take over execution of the emulator.
7. Have the current host thread wait for the synchronization object to be signaled.

Every emulation thread (including the initial thread) will execute as follows:

1. Check the current state of emulation. If it is not Running, then exit immediately.
2. Emulate the code as is done right now.
3. After a time slice is executed, check if any one condition of the suspended threads is met. If that's the case, restore the original CPU context and guest thread associated with it, and mark the guest thread as active. Remove the object from the list.
   • If there is a synchronization object, signal it to wake up the original host thread, and exit. Execution should continue from the original host thread at the point it was suspended.
   • Otherwise, the current host thread continues execution.

A conditional variable could be used instead of the single-shot synchronization object.

Of course, the thread scheduler needs to be aware that these threads are suspended, so there needs to be a flag on the Thread object indicating that they're not available for scheduling, or they could be removed entirely from the vector of threads until they are ready to execute again, at which point they're added back in.

Examples of situations where this mechanism would be engaged and the corresponding conditions:

• If NtYieldExecution is invoked, the condition is going to be always true so that the secondary thread runs for what the emulator considers a single time slice before exiting.
• A sleep is essentially a wait on a KTIMER object. The condition is going to be based on a countdown until the timer expires, at which point it evaluates to true.
• The conditions for KeWaitForSingleObject / KeWaitForMultipleObjects are based on the object(s) they are waiting for and the wait type passed to the function call in the case of multiple objects.
• KeSuspendThread's condition is the thread's SuspendCount reaching zero again. Every call to KeSuspendThread increases the count by one, and every call to KeResumeThread decreases the count by one. Note that this affects the thread passed in as an argument which may not necessarily be the current guest thread. If the target thread is the current guest thread, the algorithm described above applies, otherwise the following algorithm is executed:
  1. Establish a condition based on the cause of the thread suspension.
  2. Build an object containing the condition, the current guest thread and NULL for the synchronization object and add it to the list of suspended threads.
  3. Mark the target guest thread as suspended.

If KeSuspendThread is invoked on a thread that is already suspended for another reason, its condition should be expanded to include the SuspensionCount.

Note that KeStallExecutionProcessor is used to perform time-sensitive hardware I/O operations. These operations always run on high IRQL, which means thread switches never happen. Since OpenXBOX does not strive for cycle-accurate emulation, the function is simply a no-op.

This approach runs the risk of creating an excessive number of short-lived threads if the game code abuses locks, waits, timers and such.

[StrikerX3]

Approaches I've considered and discarded:

• Abusing the exception handling mechanism: slightly invasive (can be mitigated with macros/templates), platform and compiler dependent, too abusive, too complex (especially with multiple nested calls).
• Functional C++ coroutines: invasive, still not well established (being discussed for inclusion on C++20), doesn't quite solve the problem.
• Boost::Future: invasive, requires a dependency to a large library, similar to functional C++ coroutines.

[StrikerX3]

One more thing: proper IRQL management is now required.
Oh, and KeBugCheck(Ex) really needs to stop emulation

[StrikerX3]

The above approach has been partially implemented, but is currently untested. Emulation state is still just a boolean indicating whether to continue running or not.
Proper IRQL management and KeBugCheck(Ex) will come next.

[StrikerX3]

I figured that since I'm going full on with implementing the entire kernel, I might as well leave thread scheduling up to the kernel itself instead of our own custom class. The host thread suspension technique will still be used, but in a different and simpler way. Basically the kernel will update the KPRCB's current and next thread fields taking into account priorities, thread queues, quantums and more (just like the real thing), and the scheduler will switch to whatever current thread is in there, creating a host thread or waking one up if a context switch happens in the middle of a kernel function call. The Thread class might disappear as we'll be using those KTHREADs instead.

I expect to be able to fully implement the majority (if not all) of the Ke* and Kf* functions. Also, big changes might happen.

One big thing that has to come next is interrupts. The system clock ticks 1000 times per second on the Xbox, updating KeSystemTime, KeInterruptTime and KeTickCount, and also handling thread switches when their quantum expire. Without it this approach will get stuck on a single thread. It seems Unicorn doesn't do interrupts on its own.

[StrikerX3]

This should work in most cases. Still needs more testing, but so far it goes all the way to the point where we got stuck before due to an unimplemented kernel function (NtReadFile in the case of Microsoft XDK software). The cool thing is, it automatically causes a BugCheck because of it!

The way the scheduler works is similar to what was described above, but much more simplified. A new host thread is created everytime a new guest thread is switched in, suspending the current host thread. When the scheduler switches back to the old thread, the corresponding host thread is resumed. No conditions are needed because the kernel handles them internally; all we need to do is check what is the current thread in the KPRCB and manage the host threads.

In order to get this to work, I also had to implement two function invocation mechanisms:

• InvokeGuest(): host-to-guest function calls.
• Internal Kernel functions: pointers to host functions that the guest can invoke. They are handled exactly like the Kernel Thunk table handlers.

By the way, over a third of the exported kernel functions are now fully implemented, with the majority being Ke* and Rtl* functions. Almost half of the functions have at least a partial or fake implementation.

In order to progress further, interrupts need to be implemented. As explained above, the system clock plays a role in thread switching; without it, threads may get stuck executing forever, starving other threads.