Koroutinen Kontextwechsel

« | 02 Jan 2022 | »

Nach meinen Experimenten mit Koroutinen mit OS-Funktionen und meinem Fehlschlag mit setjmp/longjump, ist es an der Zeit, das Thema “neu zu denken”.

Denn jetzt, wo Assembler Patches im GATE Projekt leicht möglich sind und mit UEFI eine zur Zeit thread-lose Implementierung vor mir liegt, bekommen Koroutinen plötzlich eine neue Bedeutung.

Für Windows und Linux habe ich mit Boardmitteln akzeptable Lösungen gefunden, um innerhalb eines Threads zwischen Callstacks hin und her zu hüpfen.

In EFI-Apps gibt es keine Threads, doch wenn man mehrere Callstacks anlegen könnte und zwischen denen hin- und herhüpfen könnte, dann wäre eine einfache Art von kooperativem Multitasking geboren, mit der man z.B. einen Webserver dazu bringen könnte, mehrere Anfragen zu bearbeiten, oder man könnte UIs mit Background-Tasks aufwerten.

Callstacks erzeugen

Normaler Datenspeicher, wie er von malloc() zurückkommt, ist nicht automatisch Stack-tauglich. Oft muss man dem OS erst mitteilen, dass man auch “Code-Adressen” darauf nutzen möchte.

EFI nutzt offenbar keinen Speicherschutz womit ein
efi_sys_table->BootServices->AllocatePool(EfiLoaderData, mem_size, &ptr_mem); ausreicht um Speicher für einen Callstack zu allokieren.

Unter Windows braucht man APIs wie VirtualAlloc(), VirtualProtect() und VirtualFree() um Speicher mit den Protection-Flags PAGE_EXECUTE_READWRITE auf die Nutzung als Stack vorzubereiten.

Zu einem neuen Callstack springen

Hat man einen neuen Stack allokiert, muss man eigentlich nur noch das Stack-Register auf dessen Ende setzen und kann dann eine weitere Funktion aufrufen, die in dem neuen Kontext laufen soll.
Die Funktion kann ganz ähnlich wie eine Thread-Entry-Funktion aussehen.

Damit man beim Rücksprung aus der Funktion wieder zum alten Stack zurückfinden kann, wird die Adresse des alten Stacks auf den neuen Stack gepusht, um am Ende wieder zurückfinden zu können.

X86-32 Funktion auf neuem Stack ausführen

 1; typedef void* (enty_function_t)(void* entry_param);
 2
 3mov eax, [stack_top_ptr]  ; stack-alloc-ptr + stack-size
 4mov ecx, [entry_param]
 5mov edx, [entry_function_ptr]
 6
 7push ebp      ; backup old EBP on current stack
 8mov ebp, esp  ; backup of current stack
 9mov esp, eax  ; switch to new stack
10push ebp      ; save old stack-ptr on new stack
11
12push ecx      ; param for entry-function
13call edx      ; call entry-function
14add esp, 4    ; param cleanup
15
16pop ebp       ; restore old stack-ptr
17mov esp, ebp  ; switch back to old stack
18pop ebp       ; restore old EBP

X86-64 Funktion auf neuem Stack ausführen

 1; typedef void* (enty_function_t)(void* entry_param);
 2mov rax, [stack_top_ptr]
 3mov rcx, [entry_param]
 4mov rdx, [entry_function_ptr]
 5
 6push rbp      ; backup old RBP on current stack
 7mov rbp, rsp  ; backup of current stack
 8mov rsp, rax  ; switch to new stack
 9and rsp, 0fffffffffffffff0h  ; align(16) new stack
10sub rsp, 8    ; prepare call-alignment
11push rbp      ; save old stack-ptr on new stack
12
13sub rsp, 32   ; allocate x64 home space
14call rdx      ; call function on foreign stack
15add rsp, 32   ; deallocate x64 home space
16
17pop rbp       ; restore old stack-ptr
18mov rsp, rbp  ; switch back to old stack
19pop rbp       ; restore old RBP

Callstack wechseln

Um dynamisch zwischen Callstacks wechseln zu können, braucht eine “Callstack-Snapshot” - Struktur, die einige intptr_t bzw. void* speichern kann, um Register des aktuellen Callstacks zu speichern. Und eben genau diese gesicherten Register werden dann von einem anderen Callstack-Snapshot geladen.

X86-32 Callstack wechseln

 1;void* gate_win32_callstack_switch_x86(
 2;        gate_callstack_context_t* old_to_save, 
 3;        gate_callstack_context_t* new_to_load);
 4
 5gate_win32_callstack_switch_x86 PROC
 6  push ebp
 7  mov ebp, esp
 8
 9  mov ecx, [ebp + 8]  ; store-context
10  mov edx, [ebp + 12] ; load-context
11
12  ;store current context to ptr in ECX
13  mov DWORD PTR [ecx +  0], esp
14  mov DWORD PTR [ecx +  4], ebp
15  mov DWORD PTR [ecx +  8], ebx
16  mov DWORD PTR [ecx + 12], esi
17  mov DWORD PTR [ecx + 16], edi
18
19  ;load new context from ptr in EDX
20  mov edi, DWORD PTR[edx + 16]
21  mov esi, DWORD PTR[edx + 12]
22  mov ebx, DWORD PTR[edx +  8]
23  mov ebp, DWORD PTR[edx +  4]
24  mov esp, DWORD PTR[edx +  0]
25
26  mov eax, 0    ; default-return: no switch
27  cmp ecx, edx
28  jz callstack_switch_x86_exit
29
30  ;if ecx != edx, we have switched, 
31  ;otherwise current context is only saved
32  mov eax, edx  ; return: pointer to switched context
33
34callstack_switch_x86_exit:
35  mov esp, ebp
36  pop ebp
37  ret
38  ;EAX tells, if switch was performed
39gate_win32_callstack_switch_x86 ENDP

X86-64 Callstack wechseln

 1;void* gate_win32_callstack_switch_x64(
 2;        gate_callstack_context_t* old_to_save, 
 3;        gate_callstack_context_t* new_to_load);
 4gate_win32_callstack_switch_x64 PROC
 5  push rbp
 6  mov rbp, rsp
 7
 8  ; store current stack frame to ptr in RCX
 9  mov qword ptr [rcx +  0], rsp
10  mov qword ptr [rcx +  8], rbp
11  mov qword ptr [rcx + 16], rbx
12  mov qword ptr [rcx + 24], rsi
13  mov qword ptr [rcx + 32], rdi
14  mov qword ptr [rcx + 40], r12
15  mov qword ptr [rcx + 48], r13
16  mov qword ptr [rcx + 56], r14
17  mov qword ptr [rcx + 64], r15
18
19  ; load next stack frame from stored struct at ptr in RDX
20  mov r15, qword ptr [rdx + 64]
21  mov r14, qword ptr [rdx + 56]
22  mov r13, qword ptr [rdx + 48]
23  mov r12, qword ptr [rdx + 40]
24  mov rdi, qword ptr [rdx + 32]
25  mov rsi, qword ptr [rdx + 24]
26  mov rbx, qword ptr [rdx + 16]
27  mov rbp, qword ptr [rdx +  8]
28  mov rsp, qword ptr [rdx +  0]
29
30  mov rax, 0    ; default-return: no switch
31  cmp rcx, rdx
32  jz callstack_switch_x64_exit
33
34  ;if ecx != edx, we have switched, 
35  ;otherwise the context was only saved without a switch  
36  mov rax, rdx  ; return: pointer to switched context
37
38callstack_switch_x64_exit:
39  mov rsp, rbp
40  pop rbp
41  ret
42  ;RAX tells, if switch was performed
43gate_win32_callstack_switch_x64 ENDP

Fazit

Nachdem x64-EFI das gleiche ABI wie Windows X64 hat, konnte ich den Stack-Wechsel einfach unter Windows im MSVC Debugger testen und war fast erstaunt, dass das auch genau so funktioniert, bevor ich die ersten Tests direkt als EFI-App erfolgreich ausführen konnte.
Interessant sind jetzt die noch nicht entdeckten Seiteneffekte.

Meine aktuelle Koroutinen-Implementierung ist noch ein bisschen detailreicher als hier beschrieben, da eine Routine beim create() zu einem Dispatcher springt, der gleich wieder zum Aufrufer zurückwechselt und zur finale Routine wird erst später wieder per yield() hingewechselt.
Und obwohl oben im ASM-Code vorgesehen ist, dass man aus einem neuen Callstack auch “einfach so” wieder zum Aufrufer zurückwechseln kann, ist das im Endeffekt nicht vorgesehen, da der Aufrufer dann vielleicht nicht mehr existiert.
Man wechselt dann immer zu einer internen Scheduler-Routine, die alle anderen verwaltet und eine “beendete” Routine deallokiert.

Wie auch immer … hier geht es ja vorerst nur um das Konzept.
Und das scheint zumindest auf den ersten Blick zu funktionieren.