Context Switching

juin 10th, 2007 at 02:21 admin

Cette fois ci, le contenu du post est sous licence no-brain, tout ceux ayant un QI de plus de 2 sont invités à aller se brancher devant la TV pendant 24h pour le faire diminuer. Pourquoi une telle licence ? Tout simplement parce que ce qui va suivre risque de transformé votre cerveau en éponge. Je prévient d’emblé, ce qui va suivre est un voyage dans le hal et le kernel à travers le fonctionnement du context switching, alors préparez votre aspirine.

Comme vous le savez un processeur monocore ne peut réaliser qu’une seule chose à la fois, l’impression du multitâche sur l’OS est donc réalisée en effectuant plein de petites actions rapidement. Chaque tâche est appelé un thread, un thread représente un ensemble d’instructions à être exécuté, ainsi l’OS pour être multitâche va sauter de thread en thread et le processeur va effectuer quelques instructions de ceux-ci à chaque fois avant de changer de thread. Ca va là, tout le monde suit encore :], je vous conseil quand même d’avoir le chapitre du Windows Internals sur le thread scheduling ouvert pour être plus à l’aise avec la suite.

Un thread peut ainsi avoir 7 états :

- Initialized : thread en cour d’initialisation.
- Ready : le thread est prêt à être éxécuté.
- Running : le thread est en court d’exécution.
- Waiting : le thread est en attente.
- Terminated : le thread à finit son exécution.
- Transition : le thread est ready mais sa kernel stack doit être inswappée pour être rechargée en mémoire.
- Standby : attend d’être exécuté sur un processeur précis.

Chaque thread dispose aussi d’une priorité (en faite il y en à 2, une statique et une dynamique mais osef), celle-ci permet au thread scheduler de déterminer quel sera le thread suivant à être lancé. De plus avant d’être exécuté chaque thread reçois un quantum, cette valeur comparable à une unité de temps, permet à l’OS de définir combien de temps va tourner un thread. En fait, le BIOS va régulièrement générer une interruption qui va décrémenté le quantum du thread courant. Lorsque le quantum est nul, le noyau change de thread. Chez moi cette interruption intervient toutes les 15.625 ms. Cette valeur peut être retrouvée en utilisant l’API GetSystemTimeAdjustment.

En fait il y plusieurs raisons pour que l’OS décide de changer de thread :
- Quand un thread passe en mode Waiting après par un appel à WaitForSingleObject par exemple.
- Un thread de priorité supérieure devient Ready, on appel cela la preemption.
- Le thread à finit son exécution.
- Le quantum du thread courant est expiré.

L’interruption qui intervient toutes les 15.625 ms est généré par le BIOS et est handler par la routine HalpClockInterrupt qu’on retrouve dans l’IDT à l’indice 0×30 :

!idt -a
[...]
30:	806f3d48 hal!HalpClockInterrupt

Comme nous nous trouvons dans le cadre d’une interruption le processeur va automatiquement pusher sur la kernel stack du thread courant les valeurs suivantes :

error code  <- esp after interrupt
registre EIP
registre  CS
registre  EFLAGS
registre  ESP
segment SS

Toutes ces valeurs sont évidemment celles qui existaient avant l’apparition de l’interruption. Si on désassemble le début de la routine HalpClockInterrupt on peut voir :

kd> u hal!HalpClockInterrupt l 20
hal!HalpClockInterrupt:
806f3d48 push    esp
806f3d49 push    ebp
806f3d4a push    ebx
806f3d4b push    esi
806f3d4c push    edi
806f3d4d sub     esp,54h
806f3d50 mov     ebp,esp
806f3d52 mov     dword ptr [esp+44h],eax
806f3d56 mov     dword ptr [esp+40h],ecx
806f3d5a mov     dword ptr [esp+3Ch],edx
806f3d5e test    dword ptr [esp+70h],20000h
806f3d66 jne     hal!V86_Hci_a (806f3d20)
806f3d68 cmp     word ptr [esp+6Ch],8
806f3d6e je      hal!HalpClockInterrupt+0x4b (806f3d93)
806f3d70 mov     word ptr [esp+50h],fs
806f3d74 mov     word ptr [esp+38h],ds
806f3d78 mov     word ptr [esp+34h],es
806f3d7c mov     word ptr [esp+30h],gs
806f3d80 mov     ebx,30h
806f3d85 mov     eax,23h
806f3d8a mov     fs,bx
806f3d8d mov     ds,ax
806f3d90 mov     es,ax
806f3d93 mov     ebx,dword ptr fs:[0]
806f3d9a mov     dword ptr fs:[0],0FFFFFFFFh
806f3da5 mov     dword ptr [esp+4Ch],ebx
[...]

Ce prologue sert à sauvegarde sur la stack les valeurs des autres registres de notre thread interrompu. Plus loin, cette routine élève l’IRQL à CLOCK2_LEVEL (28=0x1C) en appelant HalBeginSystemInterrupt, c’est un des IRQL les plus élevé sachant que le maximum HIGH_LEVEL vaut 31. A la fin de HalpClockInterrupt on voit un jmp sur la fonction du kernel KeUpdateSystemTime qui à pour rôle de mettre à jour l’horloge système.

Plus loin KeUpdateSystemTime appel KeUpdateRunTime qui se charge d’actualiser le compteur d’interruptions, le user ou kernel time du thread et surtout de décrémenter le quantum !

Si on regarde la stack lorsque qu’on est dans KeUpdateRunTime on a :

kd> kv
ChildEBP RetAddr  Args to Child
f98f8d50 804e32f6 00000000 00000000 00000030 nt!KeUpdateRunTime+0x122 (FPO: [1,1,0])
f98f8d50 77bfc7c0 00000000 00000000 00000030 nt!KeUpdateSystemTime+0x137 (FPO: [0,2] TrapFrame @ f98f8d64)

[INTERRUPT OCCURS !!!]

00e3e07c 77c10017 00e3e094 7ca839e4 00e3e104 msvcrt!_aulldvrm
00e3e0b4 7c9ffd32 00e3e46c 0000005b 7ca839e4 msvcrt!_vsnwprintf+0x30 (FPO: [Non-Fpo])
00e3e0d8 7c9ffd02 00e3e46c 0000005c 7ca839e4 SHELL32!StringVPrintfWorkerW+0x2c (FPO: [Non-Fpo])
[...]

Le trapframe correspond aux valeurs des registres sauvegardés sur la kernel stack du thread courant avant que l’interruption ne débute. On peut dumper le contenu du trapframe avec la commande .trap du KD.

kd> .trap f98f8d64
ErrCode = 00000000
eax=00000010 ebx=00000401 ecx=00000007 edx=00000000 esi=00e3de77 edi=00000000
eip=77bfc7c0 esp=00e3dbf8 ebp=00e3e07c iopl=0         nv up ei pl nz na po nc
cs=001b  ss=0023  ds=0023  es=0023  fs=003b  gs=0000             efl=00000202
msvcrt!_aulldvrm:
001b:77bfc7c0 push    esi

Ici l’interruption à débarqué avant l’exécution du « push esi » de la fonction msvcrt!_aulldvrm.

Dans la routine KeUpdateSystemTime on peut voir le bout ce bout de code :

[...]
nt!KeUpdateSystemTime+0x124:
804e32e3 mov     eax,dword ptr [nt!KeMaximumIncrement (8055168c)]
804e32e8 add     dword ptr [nt!KiTickOffset (80551694)],eax
804e32ee push    dword ptr [esp]
804e32f1 call    nt!KeUpdateRunTime (804e332a)
804e32f6 cli
804e32f7 call    dword ptr [nt!_imp__HalEndSystemInterrupt (804d7608)]
804e32fd jmp     nt!Kei386EoiHelper (804df05c)
[...]

HalEndSystemInterrupt fait redescendre l’IRQL au niveau ou il se trouvait avant l’interruption et Kei386EoiHelper est la fonction qui va nous faire quitter l’interruption. En effet si on la disass on peut voir :

[...]
nt!Kei386EoiHelper+0x12c:
804df188 add     esp,3Ch
804df18b pop     edx
804df18c pop     ecx
804df18d pop     eax
804df18e lea     esp,[ebp+54h]
804df191 pop     edi
804df192 pop     esi
804df193 pop     ebx
804df194 pop     ebp
804df195 cmp     word ptr [esp+8],80h
804df19c ja      nt!Kei386EoiHelper+0x148 (804df1a4)

nt!Kei386EoiHelper+0x142:
804df19e add     esp,4
804df1a1 iretd

nt!Kei386EoiHelper+0x148:
804df1a4 cmp     word ptr [esp+2],0
804df1aa je      nt!Kei386EoiHelper+0x142 (804df19e)

nt!Kei386EoiHelper+0x150:
804df1ac cmp     word ptr [esp],0
804df1b1 jne     nt!Kei386EoiHelper+0x142 (804df19e)

nt!Kei386EoiHelper+0x157:
804df1b3 shr     dword ptr [esp],10h
804df1b7 mov     word ptr [esp+2],0F8h
804df1be lss     sp,dword ptr [esp]
804df1c3 movzx   esp,sp
804df1c6 iretd

Les pop avant sont la pour remettre les registres avant l’arrivé de l’interruption et iretd effectue le retour. Tout est nickel le thread repart.

Je résume donc un peu, le système balance périodiquement une interruption, la routine qui doit gérer cette interruption fait péter l’IRQL à CLOCK2_LEVEL, se charge de mettre à jour l’horloge système et décrémente le quantum du thread courant (en gros). Le contexte de ce dernier est sauvegardé dans sa kernel stack (même si celui était tournait en userland avant que l’interruption arrive). A la fin de l’interrpution la fonction Kei386EoiHelper va reloader le contexte, PAF ! le thread repart et ca fait des chocapics :]

Maintenant on s’intéresse au moment ou la fonction KeUpdateRunTime décrémente le quantum et que celui-ci devient nul. Cela signifie que le temps d’exécution alloué au thread est écoulé et qu’il faut soit recharger son quantum, soit swapper sur le prochain thread. Désassemblons donc un peu KeUpdateRunTime :

kd> uf nt!KeUpdateRunTime
[...]
nt!KeUpdateRunTime+0x114:
804e343e sub     byte ptr [ebx+6Fh],3 ; on soustrait 3 au quantum
804e3442 jg      nt!KeUpdateRunTime+0x133 (804e345d) ; si plus grand que 0 on leave normalement la fct 

nt!KeUpdateRunTime+0x11a:
804e3444 cmp     ebx,dword ptr [eax+12Ch] ; eax=ffdff000=KPCR, compare le thread courant au idle thread
804e344a je      nt!KeUpdateRunTime+0x133 (804e345d) ; si egal on leave

nt!KeUpdateRunTime+0x122:
804e344c mov     dword ptr [eax+9ACh],esp ; met champ QuantumEnd du KPRCB à une valeur !=0 :p
804e3452 mov     ecx,2
804e3457 call    dword ptr [nt!_imp_HalRequestSoftwareInterrupt (804d7680)]

nt!KeUpdateRunTime+0x133:
804e345d pop     ebx
804e345e ret     4

Lorsque le quantum est nul, KeUpdateRunTime va mettre le ULONG QuantumEnd du KPRCB à true puis fait un appel à HalRequestSoftwareInterrupt. Cette fonction devant être appeler en convention fastcall, ses arguments sont passés par les registres. Ecx contient la valeur du seul argument de HalRequestSoftwareInterrupt qui est 2 (IRQL valant DISPATCH_LEVEL) dans le cas présent.

Regardons le code de HalRequestSoftwareInterrupt :

kd> uf hal!HalRequestSoftwareInterrupt
hal!HalRequestSoftwareInterrupt:
806f3884 mov     eax,1
806f3889 shl     eax,cl ; si cl=2 alors eax vaut 4
806f388b pushfd
806f388c cli
806f388d or      dword ptr ds:[0FFDFF028h],eax
806f3893 mov     cl,byte ptr ds:[0FFDFF024h] ; cl= current IRQL
806f3899 mov     eax,dword ptr ds:[FFDFF028h] ; IRR=4

d> !pcr
KPCR for Processor 0 at ffdff000:
    Major 1 Minor 1
	NtTib.ExceptionList: fcd395d4
	    NtTib.StackBase: fcd39df0
	   NtTib.StackLimit: fcd37000
	 NtTib.SubSystemTib: 00000000
	      NtTib.Version: 00000000
	  NtTib.UserPointer: 00000000
	      NtTib.SelfTib: 7ffde000

	            SelfPcr: ffdff000
	               Prcb: ffdff120
	               Irql: 0000001c
	                IRR: 00000004 <= !
	                IDR: ffff20f0
	      InterruptMode: 00000000
	                IDT: 8003f400
	                GDT: 8003f000
	                TSS: 80042000

	      CurrentThread: ffb47618
	         NextThread: 00000000
	         IdleThread: 80559020

806f389e and     eax,3 ; si eax=2 alors apres le ‘and’ eax=0
806f38a1 xor     edx,edx
806f38a3 mov     dl,byte ptr hal!SWInterruptLookUpTable (806f4784)[eax]

kd> db SWInterruptLookUpTable l 10
806f4784  00 00 01 01 02 02 02 02

eax=0 dionc après le mov, dl=0

806f38a9 cmp     dl,cl ; si IRQL > 0 on leave
806f38ab jbe     hal!HalRequestSoftwareInterrupt+0x30 (806f38b4)

hal!HalRequestSoftwareInterrupt+0x29:
806f38ad call    dword ptr hal!SWInterruptHandlerTable (806f476c)[edx*4]

hal!HalRequestSoftwareInterrupt+0x30:
806f38b4 popfd
806f38b5 ret

En détaillant un peu, on voit que HalRequestSoftwareInterrupt va mettre le champ IRR du KPCR à la valeur 4. Je ne connais pas la signification exacte de se champ mais je pense qu’il sert au mettre en place les DPC (Dispatch/Deferred Procedure Call). En effet lors de l’appel à cette fonction l’IRQL courant vaut CLOCK2_LEVEL, nous on veut obtenir une interruption software, or celles ci ne sont pas accessibles à un IRQL si élevé, elles devront donc être appelées lorsque celui ci redescendra. Ainsi le champ devrait donc permettre de dire qu’une demande d’interruption software est en attente.

Alors lorsque l’IRQL redescend, notre interruption software doit être activée. Hop straff-bunny-rail ! On disass halEndSystemInterrupt, la fonction appelé du hal juste avant qu’on quitte l’interruption int 30 avec Kei386EoiHelper.

kd> uf hal!HalEndSystemInterrupt
[...]
hal!HalEndSystemInterrupt+0x22:
806ee23e mov     byte ptr ds:[0FFDFF024h],cl ; met l'IRQL à la valeur qu'il avait avant l'interruption
806ee244 mov     eax,dword ptr ds:[FFDFF028h]
806ee249 mov     al,byte ptr hal!SWInterruptLookUpTable (806f4784)[eax]

kd> db SWInterruptLookUpTable l 10
806f4784  00 00 01 01 02 02 02 02

si IRR=4 alors al=2

hal!HalEndSystemInterrupt+0x37:
806ee253 ret     8

hal!HalEndSystemInterrupt+0x3a:
806ee256 add     esp,0Ch
806ee259 jmp     dword ptr hal!SWInterruptHandlerTable2 (806f4778)[eax*4]

kd> dps sWInterruptHandlerTable2
806f4778  806f3494 hal!KiUnexpectedInterrupt
806f477c  806f3bd1 hal!HalpApcInterrupt2ndEntry
806f4780  806f3a39 hal!HalpDispatchInterrupt2ndEntry

si eax=2 on call hal!HalpDispatchInterrupt2ndEntry

HalEndSystemInterrupt va lire la valeur IRR du KPCR et jump sur un interrupt handler si nécessaire. Dans notre cas c’est la fonction HalpDispatchInterrupt2ndEntry qui est appelé pour réaliser le DPC.

Now on regarde gentiment HalpDispatchInterrupt2ndEntry

hal!HalpDispatchInterrupt2ndEntry:
806f3a39 push    dword ptr ds:[0FFDFF024h]
806f3a3f mov     byte ptr ds:[0FFDFF024h],2 ; on définit l'IRQL à DISPATCH_LEVEL
806f3a46 and     dword ptr ds:[0FFDFF028h],0FFFFFFFBh
806f3a4d sti
806f3a4e call    dword ptr [hal!_imp__KiDispatchInterrupt (806ed428)]
806f3a54 cli
806f3a55 call    hal!HalpEndSoftwareInterrupt (806ee260)
806f3a5a jmp     dword ptr [hal!_imp_Kei386EoiHelper (806ed4f8)] ; quitte l'exception

Si on disass KiDispatchInterrupt :

kd> uf nt!KiDispatchInterrupt
nt!KiDispatchInterrupt:
804db874 mov     ebx,dword ptr ds:[0FFDFF01Ch]
804db87a lea     eax,[ebx+980h]
804db880 cli
804db881 cmp     eax,dword ptr [eax]
804db883 je      nt!KiDispatchInterrupt+0x2e (804db8a2)

nt!KiDispatchInterrupt+0x11:
804db885 push    ebp
804db886 push    dword ptr [ebx]
804db888 mov     dword ptr [ebx],0FFFFFFFFh
804db88e mov     edx,esp
804db890 mov     esp,dword ptr [ebx+988h]
804db896 push    edx
804db897 mov     ebp,eax
804db899 call    nt!KiRetireDpcList (804dbb8e)
804db89e pop     esp
804db89f pop     dword ptr [ebx]
804db8a1 pop     ebp

nt!KiDispatchInterrupt+0x2e:
804db8a2 sti
804db8a3 cmp     dword ptr [ebx+9ACh],0 ; si KPRC->QuantumEnd != on saute !
804db8aa jne     nt!KiDispatchInterrupt+0x8e (804db902)

nt!KiDispatchInterrupt+0x38:
804db8ac cmp     dword ptr [ebx+128h],0
804db8b3 je      nt!KiDispatchInterrupt+0x8d (804db901)

nt!KiDispatchInterrupt+0x41:
804db8b5 mov     eax,dword ptr [ebx+128h]

nt!KiDispatchInterrupt+0x47:
804db8bb sub     esp,0Ch
804db8be mov     dword ptr [esp+8],esi
804db8c2 mov     dword ptr [esp+4],edi
804db8c6 mov     dword ptr [esp],ebp
804db8c9 mov     esi,eax
804db8cb mov     edi,dword ptr [ebx+124h]
804db8d1 mov     dword ptr [ebx+128h],0
804db8db mov     dword ptr [ebx+124h],esi
804db8e1 mov     ecx,edi
804db8e3 mov     byte ptr [edi+50h],1
804db8e7 call    nt!KiReadyThread (804db6da)
804db8ec mov     cl,1
804db8ee call    nt!SwapContext (804db924)
804db8f3 mov     ebp,dword ptr [esp]
804db8f6 mov     edi,dword ptr [esp+4]
804db8fa mov     esi,dword ptr [esp+8]
804db8fe add     esp,0Ch

nt!KiDispatchInterrupt+0x8d:
804db901 ret

nt!KiDispatchInterrupt+0x8e:
804db902 mov     dword ptr [ebx+9ACh],0 ; le champ QuantumEnd est mit à 0
804db90c call    nt!KiQuantumEnd (804e7446)
804db911 or      eax,eax
804db913 jne     nt!KiDispatchInterrupt+0x47 (804db8bb)

nt!KiDispatchInterrupt+0xa1:
804db915 ret

KiDispatchInterrupt se charge d’exécuté les différents DPC existant à un IRQL de DISPATCH_LEVEL, puis elle vérifie la valeur du champ QuantumEnd du KPRCB. Si celui ci n’est pas nul alors il se produit un call à KiQuantumEnd.

Pour résumer un peu voici la call stack lors de l’appel à KiQuantumEnd.

kd> kv
ChildEBP RetAddr  Args to Child
f9a48908 804db911 806f3a54 00000000 f9a489bc nt!KiQuantumEnd (FPO: [Non-Fpo])
f9a4890c 806f3a54 00000000 f9a489bc 80567cea nt!KiDispatchInterrupt+0x9d (FPO: [Uses EBP] [0,0,3])
f9a4890c 00000000 00000000 f9a489bc 80567cea hal!HalpDispatchInterrupt2ndEntry+0x1b (FPO: [0,1] TrapFrame @ 00000000)

KiQuantumEnd à pour rôle de vérifier si la priorité du thread doit être augmenté et de renvoyé le next thread à lancer.
Plus loin KiDispatchInterrupt va call KiFindReadyThread et mettre dans la liste des thread ready le thread courant avec KiReadyThread. Puis intervient un changement de context pour charger non pas les registres du nouveau thread (pas de façon directe en tout cas) mais bien des éléments comme la nouvelle stack et recharger les nouveaux paramètres dans le KPCR.

Ainsi si on regarde un peu la liste des threads en state ready avec la commande !ready on remarque que la dernière fonction qu’ils ont appelé est celle qui à call SwapContext. Ce qui fait que, lors du changement de context le retn de la fin de la fonction SwapContext se situant dans la nouvelle stack relance l’exécution tu thread. Ainsi si le changement du thread à eu lieu après un DPC provenant de l’interruption int 30, la fonction SwapContext va gentiment retourner de KiDispatchInterrupt puis enfin de la fin de HalpDispatchInterrupt2ndEntry qui contient :

hal!HalpDispatchInterrupt2ndEntry:
[...]
806f3a4e call    dword ptr [hal!_imp__KiDispatchInterrupt (806ed428)]
806f3a54 cli
806f3a55 call    hal!HalpEndSoftwareInterrupt (806ee260)
806f3a5a jmp     dword ptr [hal!_imp_Kei386EoiHelper (806ed4f8)] ; recharge le contexte et quitte l'exception

Le magnifique jmp sur Kei386EoiHelper qui va recharger les registres de notre thread :] et le relancer.

C’est donc grâce à ce model que peut se mettre en place la préemption de threads ou le changement de contexte alors que le thread n’a pas finit son exécution. Remarquez que cela est loin d’être trivial à mettre en place mais se révèle extrêmes puissant par la suite. J’ai bien fait fumé mon IDA et mon KD pour retrouvez cela.

J’espère avoir été le plus clair possible, en cas de question n’hésitez pas à laissez un post ou à me contacter.

Entry Filed under: Non classé