Nintendo 3DS Kernel scheduler findings

kernel_scheduling.md

Kernel synchronization

The AppCore uses a mostly cooperative scheduler, however, it is allowed to preempt threads under some specific circumstances, see the Rescheduling section for the cases where the scheduler may preempt a lower-priority thread to let a higher-priority run.

Each core has its own KScheduler instance.

KObject waitlists

Each KObject manages a list of threads that are waiting on it. This list is iterated over each time the KObject is signalled.

The KObject will try to retrieve the KThread with the highest priority from this list, check if it is ready to run (see KThread waitlist), and append it to the scheduler's queue (and remove it from the KObject's waitlist) if it is ready.

This awakening operation is performed for every KThread that is ready to run.

KThread waitlist

Each KThread has a list of objects that it is waiting on as a result of a WaitSynchronizationN call. A KThread will only be added to the scheduler's queue if all of the objects in this list are signalled and ready.

This list is reset during a WaitSynchronizationN call, and is unused otherwise.

WaitSynchronization1

When called with Timeout = 0, WaitSynchronization1 does not cause a reschedule if the KObject is already signalled, it only acquires it and returns control to the caller thread.

On the other hand, if Timeout is 0 but the KObject is not ready, it will immediately return error code 0x9401BFE and return control to the caller thread.

If the KObject is not ready and the Timeout is greater than 0, WaitSynchronization1 will add the KThread to the KObject's waitlist and suspend the thread, to be awoken later by the KObject during the signalling procedure.

If the KObject is ready and Timeout is not 0, the KObject is acquired and no reschedule happens.

The KThread waitlist is left untouched by this function.

WaitSynchronizationN

WaitSynchronizationN has two divergent behaviors, it either waits until all the objects are ready, or waits until one of the objects are ready.

WaitSynchronizationN will clear the KThread's waitlist and add the KThread to each of the KObjects' waitlist regardless of the wait mode used. However, only wait_all = true will re-populate the KThread's waitlist with the KObjects.

Waiting for any object (wait_all = false)

In this mode, WaitSynchronizationN will iterate over the KObjects in order and acquire the first one that is ready.

If the specified Timeout is 0, no rescheduling will be performed and error code 0x9401BFE will be returned in case that no KObjects were available.

If no Timeout was specified (-1) and an object was available, said object will be acquired and no rescheduling will be performed.

However, if a Timeout value greater than 0 was given, then the thread will be suspended for up to the specified amount of time if no KObjects were ready.

Waiting for all objects (wait_all = true)

In this mode, the kernel will first check if all the objects are ready before acquiring them all.

If the specified Timeout is 0, no rescheduling will be performed and error code 0x9401BFE will be returned in case that not all the KObjects were available.

If the KThread couldn't acquire all objects, and it's marked for termination (offset 0x36 in the KThread structure), then the thread is descheduled and added to the scheduler's queue again (presumably so that cleanup actions can be performed at the end of the SVC handler), and the WaitSynchronizationN call returns 0xD920060D

If the KThread is not marked for termination, WaitSynchronizationN will add the thread to each object's waitlist and add all objects to the thread's waitlist. The thread will be suspended with the specified timeout (if it is greater than zero).

There is some weird behavior in this last case, after the thread is suspended, WaitSynchronizationN will remove the thread from each of the objects' waitlist, and clear the thread's waitlist again. It is speculated that something akin to a coroutine return occurs somewhere between putting the thread to sleep, and running this code, as it appears to be the code that sets the return value of WaitSynchronizationN.

ReplyAndReceive

TODO

Rescheduling

Cases when a reschedule attempt happens:

• At the end of each SVC if the thread is marked for termination. This is different than just calling svcExitThread.
• At the end of each SVC if the thread's owner process has a KDebug event associated with it.
• After a call to svcExitThread.
• After a call to svcSleepThread.
• After a call to svcExitProcess.
• After a call to svcTerminateProcess.
• After a KProcess is destroyed and at least one thread was waiting for it.
• After a KThread is destroyed and at least one thread was waiting for it.
• After a KThread is awakened by a timeout interrupt (WaitSynch timeout, Sleep timeout).
• In a WaitSynchronization1 call if the given timeout is greater than 0 and the thread has to wait for the object.
• After a SyncRequest to a KClientSession.
• After a call to svcSetResourceLimit values with resource type = CPU_TIME (9) and resource value < 0x5A.
• After a call to svcReplyAndReceive to reply to a KServerSession.
• In a WaitSynchronizationN call if the given timeout is greater than 0 and the thread has to wait for the objects.
• After a thread resumes from wait due to a KObject signal.
• After a KClientSession is closed. This also causes any waiting threads to awake with an error code.
• After a KServerSession is closed. This also causes any waiting threads to awake with an error code.
• After svcCreateThread.
• After svcSetThreadPriority.
• After svcReleaseMutex if the mutex lock count reached 0.

From here on, everything should be re-verified.

• TODO: Some magic related to AddressArbiters.
• TODO: Some magic related to memory mappings (svcControlMemory, some cache cleaning ops also cause a reschedule?).
• TODO: After a DMA transfer?
• TODO: After svcMapProcessMemory?
• TODO: After svcUnmapProcessMemory?