私のひらめき日記

気持ちをめも

xv6の場合のExceptionとInterruptの挙動

ExceptionとInterruptの挙動

linux2.6.11の場合のExceptionとInterruptの挙動をまとめようと思って、xv6との比較を書いていたが分量が多くなりすぎたので、簡単にxv6ではException、Interruptをどう処理しているのかをまとめる。

Reference

Glosary

ExceptionやInterruptに関係する用語としては以下の通り(ややこしい..):

  • Exception: ゼロ除算やPage Faultなどのvector0~31までに割り当てられている。c.f) Table 6-1または、ch.6.15
  • Interrupt: timerやdiskなど外部I/O deviceが起こす。vector32~255まで割り当てることができる。int命令(software-generated interrupt)もinterruptに分類される。

  • Process switch .. process間の切り替え(linux2.6ではswitch_toで、xv6ではswtchでやったこと)

  • Interrupt switch .. Interruptが生じたときの切り替え(linux2.6の場合、同じプロセス内で完結するが、Interruptの処理のstackが異なる。Interruptの処理中にInterruptが重なるのも許す。)

  • IRQ(Interrupt ReQuests):

    • IRQ line: Hardware deviceがinterruptを発したいときのsignalを発する線(電話線みたいな). PIC(I/O APIC)につながっている
    • interrupt vector(IV): interruptやexceptionを識別するための番号1。xv6やlinuxではdefaultでIRQ+0x20(#define FIRST_EXTERNAL_VECTOR 0x20)。0~31まではreserved(systemのinterrupt)のためなので。
    • IRQ Descriptor: linuxではstruct irq_desc_rで定義されている。interruptが発生した時ISR(Interrupt Service Routine)が呼び出される。xv6にはISR(Interrupt Service Routine)という概念はないので、IRQ Descriptorは存在しない。
    • PIC(Programmable Interrupt Controller): 外部のdeviceから来たInterrupt達をCPUに伝達するためのcontroller。"Programmable"なので、register(memory上のaddressに配置されてる場合2もある。I/O APICやlocal APICはこれに当てはまる)にRead or Write(もしくはRead/Write両方)することでdeviceの設定を変更できる
      • 8259A PIC: [legacy] legacy CPUに搭載されていたInterrupt Controller。8つのinterruptまで受容できる。(slaveとmasterの2つを使い、15つまで対応) c.f) https://pdos.csail.mit.edu/6.828/2018/readings/hardware/8259A.pdf && pp.14 in http://www.cse.iitm.ac.in/~chester/courses/16o_os/slides/6_Interrupts.pdf
      • I/O APIC(Advanced PIC): 8259A PICの後進で、multiprocessorに対応するためのAPIC。こちらはLocal APICと違い、CPUの搭載数に依存しない。(random|特定)のCPUに指定のinterruptの処理をお願いしたりできる。
        • Interrupt Redirection Table(Redirection Tableとも): I/O APICでinterruptがどのCPUに振り分ける(redirect)べきかを決める表。vector numberとdest CPU(+その他オプション)を対応付ける。(24 entryある) xv6では、ioapicenableでtableの中身を設定できる。また、linux2.6ではset_ioapic_affinity(=set_ioapic_affinity_irq)でCPUの振り分けを変更できる。
      • local APIC: I/O APICとセットで使われる。各CPUに存在するAPIC(なので"local")で、HardWare Deviceが発したinterruptがI/O APICを介してlocal APICに振り分けられる。LAPICとも言ったりする。 c.f.) Table10-1にregister一覧がある
        • LVT(Local Vector Table): local APICにてvector number(32~)とLVTのindexを対応させる必要がある(32 ~ 255はuser-definedのinterruptなので)。その対応表。 c.f) Ch10.5.1 & Figure 10-8
        • TPR(task priority register): arbitration priorityが格納されているregister.
        • ICR(Interrupt Command Register): local APICにあるregister。IPI(InterProcessor Interrupt)を別のCPUに伝達する時の設定諸々を格納するregister c.f.) Figure10.12
        • EOI(End Of Interrupt) Register: Interruptの終わりを知らせるレジスタ
        • LINT0, LINT1: local APIC interruptに予約されてるIRQ line.
        • Local APICには他にもregister達があるようだ... c.f.) Table10-1
  • SMP(Symmetric MultiProcessing): 同等な2つ以上ののCPUが一つのmemoryとつながっている構造(CPU達がmaster-slaveの関係になっていない) 外部のI/O deviceから来たInterruptを各CPUに均等に振り分けたりできる。

    • IPI(InterProcessor Interrupt): あるCPUから他のCPU(broadcastも含め)に向かってやり取りするためのInterruptのこと。I/O APICを経由して、該当のCPUのlocal APICに伝達する。
      • SIPI(Startup IPI): 最初のCPUの初期化のときに、他のCPUをbootさせるための合図
  • NMI(NonMaskable Interrupt) .. disableにできないInterrupt. c.f) Interrupt 2—NMI Interrupt in ch. 6.15

    • INTR pin: [legacy] local APICがdisableのときに用いられる。externel interruptの受取先。
    • NMI pin: [legacy] local APICがdisableのときに用いられる。disableにできないexternel interruptの受取先。
  • IDT(Interrupt Descriptor Table) .. Gate Descriptorというentryが格納された配列。Interruptの番号が表のindexに対応してdispatchされる。IDTR命令でIDTのbase addressを登録。

    • gate descriptor: IDTのentryでOffset([63:48], [15:0])にcallbackのaddressを格納している
      • Interrupt gate (DPL:0): used for all interrupt handlers
        • System Interrupt gate .. same as Interrupt gate except DPL=3 (int3instruction)
      • Trap gate (DPL:0) .. used for most Linux exception handlers
        • System gate: same as Trap gate except DPL=3. It's used for int $0x80 instruction
      • Task gate (DPL:0) .. only used for "Double Fault Exception"
  • CPL(Current Priviledge Level): %cs(code segment register)のRPL([1:0]) c.f) Figure3.6

  • DPL(Descriptor Priviledge Level): (Segment|Gate) DescriptorのDPL([46:45])

  • kernel control path: the sequence of instructions executed by the kernel to handle a system call, an exception, or an interrupt.

用語が山のようにあるが、次の節以降で断りなく各種用語を使っていくので、適宜参照してください。

Note) 最初LVTをIDTのEntryのOffset([63:48], [15:0])(callback)の表かと勘違いしていたが、Local APICにあるregisterであって、IDTとは関係がない。LVTについては、Intel SDMのTable 10.1を見れば雰囲気がよく分かると思う。

ExceptionとInterruptの挙動

xv6のExceptionやInterruptの処理を追っていく。

初期化

InterruptやExceptionが起こる時のために、IDTのentryにcallbackが呼ばれるように設定できる。加えて、Interruptの場合は、IRQからvector numberの変換(といってもIRQ+32という単純なもの)並びに振り分けるcpuの設定をI/O APICのRedirection Tableに書き込む。

  • local APICの初期化と設定 (main 関数のlapicinitで。timer(IRQ_TIMER), LINT0, LINT1, End Of Interrupt(EOI) register, Error Status Register(ESR), Task Priority Register(TPR)の設定 etc..)
  • I/O APICの初期化(main関数のioapicinitでioapicwrite(REG_TABLE+2*i, INT_DISABLED | (T_IRQ0 + i)); ioapicwrite(REG_TABLE+2*i+1, 0);)

  • exception, interruptの設定

    • main() 関数の tvinitでIDTの初期化とsyscall(0x40)を呼び出すためのTrap-gate descriptorの設定( SETGATE(idt[T_SYSCALL], 1, SEG_KCODE<<3, vectors[T_SYSCALL], DPL_USER);
  • Interruptの設定(I/O APICの Interrupt Redirection Tableに設定を書き込む)
    • main() 関数の console_initでIRQ_KBD=1の設定(ioapicenable(IRQ_KBD, 0);)。interrupt vectorの#32をcpu#0に送る設定
    • main()関数のuart_initでIRQ_COM=1の設定(ioapicenable(IRQ_COM1, 0);)。interruptの#36をcpu#0に送る設定
    • main()関数の ideinit(DiskのR/W) でIRQ_IDE=14の設定(ioapicenable(IRQ_IDE, ncpu - 1);) interrupt vectorの#46をcpu#1に送る設定
  • idtinitでIDTのロード(lidt)

と設定。xv6の場合、Interruptの処理を任せるCPUは決め打ちにしている。linuxでは、もうちょっと洗練されて設定されてる。

Exception発生直後のhardware(x86)の対応

雑に言うと、Exception, Interruptが発生した時、権限の確認をした上で、各種レジスタをpushする。その後、Exception or Interruptの番号(vector number)から、IDTからそれに対応するentryがわかるので、callbackのアドレスに飛んで実行する。

この流れを詳しめにみていく。 User spaceでException, Interruptが発生することに注意する(linuxではinterruptについては入れ子を許すのでもうちょっと複雑) また、eflag.IFがONである必要がある。

  1. Exceptionが発生した(例えば、Divide Errorは#0) 以下の2~8はhardwareが自動的に行う処理
  2. IDTRからIDTの場所がわかるので、IDTのindexのidxを参照できる。(Base address(callback関数のアドレス)やselectorの場所がわかるよ)
  3. check (CPL=%csのRPL)<=(%csのindex[15:3]の場所のSegment DescriptorのDPL) && (CPL=%csのRPL)<=(IDT[idx](Gate Descriptor)のDPL)をチェック
  4. 3で、もし、(CPL=%csのRPL)!=(%csのSegment DescriptorのDPL) ならば、(%csのSegment DescriptorのDPL) の権限に対応するssとespをロード。TR=>TSS DescriptorのBase Address([63:56], [39:32], [31:16]) => TSSと辿れる。xv6の場合、4は原則当てはまる。右辺=0なので、%ss0(stack segment register)と%esp0となる。
  5. 古いssとespを新しいスタックにpushしておく
  6. eflags, cs, eipをスタックにpush, hardware error codeもあったらそれもスタックにpush
  7. eflagsのIFをOFFに。c.f) ch.6.12.1.
  8. IDT[idx]にSegment Selector[31:16]とOffset([63:48], [15:0])があるので、それぞれ%csと%eipにloadする。
  9. (%eipはinstruction pointerなので、そのアドレスにある命令を順次実行していく)

xv6では、vector numberがiのときはIDTのOffset(callbackのbase address)がvector_##iとなっているので、そちらの関数に飛んでソフトウェア的な(OS側の)処理が開始される。

Interrupt発生直後のhardware(x86)の対応

こちらは外部I/Oがinterruptを発生させるので、最初の部分がプログラム内で発生するExceptionよりもやや複雑。

  1. HardwareがInterruptを発する(Diskが読み終わったとか、Timerが0になったとか)
  2. I/O APICIRQ number(IRQ lineの状態)を受け取る。
  3. I/O APICIRQの番号をvectorの番号に変換して、対象のCPUのlocal APICにsignalを伝達する。(Interrupt Redirection Tableに設定したのだった)
  4. 動的に振り分ける場合、各CPUにarbitration priorityが振り分けられる(task priority register(TRR)に格納されてる) 今回は振り分けるCPUは決め打ちなので、skip

以下、Exceptionの場合と同じ。要するに、外部I/O deviceがInterruptを発生させた時、 I/O APICがどのCPUにInterruptを処理させるのかを決め、該当のCPUにお願いをするところが最初に挟まる。もし、自動で振り分ける場合は、SMPなので、いい感じにInterruptの配分をhardware側で行ってくれる3

Exception発生時

0~31までのexception及び、int $T_SYSCALLのsoftware generated interruptが起こったときが該当。

int $T_SYSCALLが起こった場合は http://cstmize.hatenablog.jp/entry/2019/03/14/GDT%E3%81%A8IDT%E5%91%A8%E8%BE%BA%E3%81%AE%E7%90%86%E8%A7%A3%28xv6%E3%82%92%E4%BE%8B%E3%81%AB%29#switchuvm の"forkretからinitまで"のところでだいたい確認している。ポイントとしては、trap()関数がException, Interruptを振り分けているところ。

// trap.c
void
trap(struct trapframe *tf)
{
  // if `int $T_SYSCALL` occurs..
  if(tf->trapno == T_SYSCALL){
    if(myproc()->killed)
      exit();
    myproc()->tf = tf;
    syscall();
    if(myproc()->killed)
      exit();
    return;
  }

  switch(tf->trapno){
  // skip
  default:
    // If Interrupt or Exception is occured at DPL_KERNEL, something wrong happens..
    if(myproc() == 0 || (tf->cs&3) == 0){
      // skip
      panic("trap");
    }
    // skip
    myproc()->killed = 1;
  }

  // if 0~31 exception occurs..
  if(myproc() && myproc()->killed && (tf->cs&3) == DPL_USER)
    exit();

Interrupt発生時のOS側の対応

vector_##iが呼ばれ、trap()関数で、IRQ_TIMERの場合、IRQ_IDEの場合..とswitch文により振り分けられ、個別のinterruptの処理が走る。これが終わったら、I/O deviceによるinterruptの場合はlapicw(EOI, 0);でEOI registerにInterruptの終わりをLocal APICに伝えて、Interruptが終わる。

コード的には、

// trap.c
trap(struct trapframe *tf)
{
 // skip // trapno means vector number.
  switch(tf->trapno){
  case T_IRQ0 + IRQ_KBD:
    kbdintr();
    lapiceoi();
    break;
  // skip

linux2.6では、Interrupt発生時にvectorに紐付いているcallbackが呼ばれるところまでは同じだが、その後、ISR(Interrupt Service Routine)を呼び出す。この呼び出し方複雑なので、次あたりにまとめたい。

trap関数終了後のOS側の対応

trap関数が終了した後は、trapasm.Sにて、stackをpopして、最後にiret命令を実行する。iret命令はinterrupt or exceptionでhardwareが自動的にやったことの逆を行う。

詳細は、以前 https://qiita.com/knknkn1162/items/0bc9afc3ae304590e16c#iret%E3%81%A8ret%E3%81%AF%E3%81%A9%E3%81%86%E9%81%95%E3%81%86 でまとめた。または、Understanding the linux kernelのHardware Handling of Interrupts and Exceptionsで詳しめの解説がある。

ポイントとしては、interrupt発生した後は、kernel landで作業していたものが、iretにより、user landに引き戻されるということだ。勿論、%eipやら%ssやら%espは前の状態に戻る。

ちなみに、linux2.6では、ret_from_intrおよび、ret_from_exceptionが同じ役割を担っている。


  1. pp.134に、Each interrupt or exception is identified by a number ranging from 0 to 255; Intel calls this 8-bit unsigned number a vectorとある。

  2. memory-mapped I/Oという。https://qiita.com/knknkn1162/items/cb06f19e1f999bf098a1#io-port%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6 を参照のこと。

  3. ただしhardwareによっては例外はあるらしく、linux2.6では、kirqd(kernel thread)で配分のバランスを適宜取るようだ。