TECHNOLOGY LINUX KERNEL

【第7回】元東大教員から学ぶLinuxカーネル「割り込み」

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

前回を読んでいない方はこちらからどうぞ.

第6回Linuxカーネル
【第6回】元東大教員から学ぶLinuxカーネル「プロセススケジューリング」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマはプロセススケジューリングです. Linuxカーネルがどのようにタス ...

続きを見る

Linuxカーネルの記事一覧はこちらからどうぞ.

Linuxカーネル
元東大教員から学ぶLinuxカーネル

こういった私から学べます. Linuxカーネルとは,C言語で開発されたオープンソースのOSです. Linuxカーネルは主に以下のコンピュータで広く利用されています. スーパーコンピュータ サーバ An ...

続きを見る

今回のテーマは割り込みです.

割り込みを理解すると,ハードウェアとOSがどのようにやり取りしているかがわかります.

割り込みとは

割り込みとは,抽象化・多重化を実現するための仕組みのことです.

OSの割り込みは,カーネルにサービスを要求することです.

ソフトウェア(例:int命令)またはハードウェア(例:キーボード)によりカーネルにサービスを要求します.

Linuxにおける割り込み処理は,Top HalfとBottom Halfがありますので,それぞれ解説していきます.

ストレージであるHDD,SSD,CPUのキャッシュやメインメモリのアクセス時間は以下のようになります.

  • HDDのアクセス時間:数ms~10ms
  • SSDのアクセス時間:10μs~100μs
  • CPUのキャッシュやメインメモリのアクセス時間:数ns~100ns

参考までに,HDDとSSDの解説は以下の動画がわかりやすいです.

HDDやSSD(特にHDD)に頻繁にアクセスするとCPUのキャッシュやメインメモリよりアクセス時間がとても長いので,コンピュータの性能を最大限発揮することができません.

また,カーネルは,ハードウェアの処理が完了してから,他の処理を行うことができるようにしなければなりません.

ハードウェアの処理完了を知る方法として以下の2つがあります.

  • ポーリング:カーネルは定期的にハードウェアの状態をチェックする.
  • 割り込み:ハードウェアがプロセッサに完了を知らせる.

ポーリングは定期的にチェックするため,一定の割合でCPUを消費する必要があります.

チェック時間が短くなる可能性が高い場合はポーリングを採用するメリットがありますが,チェック時間が長い場合は他の処理を妨害してしまう可能性があります.

そこで,ハードウェアがプロセッサに完了を知らせる「割り込み」を採用することで,この問題を解決します.

割り込みの例として,以下があります.

  • ディスクの読み込み完了
  • キーボードのキー入力
  • ネットワークパケット到着

割り込みの種類

割り込みの種類はハードウェア割り込みとソフトウェア割り込みがありますので,それぞれ解説していきます.

ハードウェア割り込み

ハードウェア割り込みは,ハードウェア(デバイス)の割り込み要求端子の変化によりCPU外部から発生させる割り込みのことです.

ハードウェア割り込みには,以下の2種類があります.

  • ノンマスカブル割り込み(NMI:Non-Maskable Interrupt)
  • マスク可能な割り込み(MI:Maskable Interrupt)(狭義の割り込み要求(IRQ: Interrupt ReQuest)(または割り込みライン)を意味する)

NMIは電源障害,メモリエラー等の決して無視できない割り込みを処理します.

IRQは,割り込み要求番号を表します.

x86-64のMIはEFLAGSのIFビットが0の場合はIRQを無視します.

x86-64のsti命令でIRQを有効にし,cli命令でIRQを無効にします.

ARM64のMIには,通常のIRQと高速な割り込みをサポートするFast Interrupt reQuest(FIQ)があります.

ARM64のmsr命令でDAIF(割り込みマスクビットを管理するレジスタ)のIRQやFIQのビットを設定すると割り込みを無効,クリアすると割り込みを有効にします.

CPUが割り込みを受け付けるとINTerrupt Acknowledgement(INTA)をセットします.

そして,割り込みが終了する際,End of Interrupt(EOI)命令を発行します.

EOI命令はx86-64の場合はiret命令,ARM64の場合はeret命令になります.

ソフトウェア割り込み

これに対して,ソフトウェアが発生させる割り込みのことをソフトウェア割り込みと呼びます.

また,CPUが何らかのコードを実行することによって発行されるソフトウェア割り込みのことを例外と呼びます.

つまり,ハードウェア(デバイス)割り込みに対して,例外はソフトウェアで発生させます.

例外はプログラム異常,(一般的な)ソフトウェア割り込みは自発的例外と呼ばれます.

  • プログラム異常(一般的な例外):ゼロ除算(Division by Zero),ページフォールト(Page Fault),一般保護違反(General Protection Fault)
  • 自発的例外(CPU内部においてCPU命令によって要求される一般的なソフトウェア割り込み):intアセンブリ命令,例えばsyscallの呼び出し等

これらのソフトウェア割り込みはハードウェア割り込みと同様にカーネルで管理されます.

割り込みコントローラ(PIC:Programmable Interrupt Controller)

割り込みは,割り込みコントローラによって多重化された電気信号で,CPUの特定のピンで送信されます.

割り込みを受信すると,専用の関数(割込みハンドラ)が実行されます.

ユーザ空間やカーネル空間では,(ほぼ)いつでも割り込みをかけて処理することができます.

x86,x86-64,ARM64の割り込みコントローラについて解説します.

x86(32ビット)の割り込みコントローラ「Intel 8259」

x86(32ビット)の割り込みコントローラ「Intel 8259」の割り込みラインでは,Master 8259とSlave 8259があります.

Master 8259のIRQ番号は以下になります.

  • IRQ 0:システムタイマ
  • IRQ 1:キーボード
  • IRQ 2:Slave 8259にカスケード接続
  • IRQ 3:シリアルポートCOM2及びCOM4
  • IRQ 4:シリアルポートCOM1及びCOM3
  • IRQ 5:ハードディスクコントローラ
  • IRQ 6:フロッピーディスクコントローラ
  • IRQ 7:LPT1

Slave 8259のIRQ番号は以下になります.

  • IRQ 8:リアルタイムクロック
  • IRQ 9:割り当てなし
  • IRQ 10:割り当てなし
  • IRQ 11:割り当てなし
  • IRQ 12:PS/2マウス
  • IRQ 13:数値演算コプロセッサ
  • IRQ 14:ハードディスクコントローラ1
  • IRQ 15:ハードディスクコントローラ2

割り込みベクタテーブル(例外ベクタテーブル)とは,割り込み(例外を含む)が発生した際に,処理を開始するプログラム(後述する割り込みハンドラ)を実行するための命令や,アドレスを保存するテーブルのことです.

x86の例外ベクタテーブルは下表になります(詳細な解説は以下の記事).

例外は以下の3種類に分類されます.

  • Fault:修正することで,何事もなかったかのようにプログラムを継続することができます.
  • Trap:トラップ命令の実行後,直ちに報告されます.
  • Abort:回復不可能な重大なエラーです.
例外番号ニーモニック名前種類
0#DE Divide-by-zero ErrorFault
1#DBDebugFault/Trap
2-Non-maskable Interrupt-
3#BPBreakpointTrap
4#OFOverflowTrap
5#BRBound Range ExceededFault
6#UDInvalid OpcodeFault
7#NMDevice Not AvailableFault
8#DFDouble FaultAbort
9-Coprocessor Segment OverrunFault
10#TSInvalid TSSFault
11#NPSegment Not PresentFault
12#SSStack-Segment FaultFault
13#GPGeneral Protection FaultFault
14#PFPage FaultFault
15-Reserved-
16#MFx87 Floating-Point ExceptionFault
17#ACAlignment CheckFault
18#MCMachine CheckAbort
19#XM/#XFSIMD Floating-Point ExceptionFault
20#VEVirtualization ExceptionFault
21#CPControl Protection ExceptionFault
22~27-Reserved-
28#HVHypervisor Injection ExceptionFault
29#VCVMM Communication ExceptionFault
30#SXSecurity ExceptionFault
31-Reserved-

x86-64(64ビット)のマルチプロセッサ対応の割り込みコントローラ「Advanced PIC(APIC)」

x86-64(64ビット)の割り込みコントローラ「Advanced PIC(APIC)」を解説します.

APICは,Intel 8259のようなPICに対して,以下の点が改良されています.

  • マルチプロセッサ対応
  • 優先度制御

※x86-64でAPICはIntel 8259と共存していますが.APICを利用する際はIntel 8259を無効にします.

APICは,Local APICとI/O APICで構成されています.

Local APICは,プロセッサチップの内部にあり,タイマ割り込みを発生させるタイマやプロセッサ間割り込み(IPI:Inter-Processor Interrupt)を発生させます.

I/O APICは,システムチップセット(またはサウスブリッジ)にあり,ローカルAPICへの割り込みを再分配します.

私のx86-64のLinux環境におけるIRQ毎の割り込み数「/proc/interrupts」の表示結果は以下になります.

CPU毎にIRQ番号と割り込み数が表示されています.

3~13行目はI/O APICが管理しているIRQ番号0~19になります.

ここで,IRQ 0はシステムタイマ(timer),IRQ 1はキーボード(i8042),IRQ 8はリアルタイムクロック(rtc0)で,Intel 8259の割り当てと同様です.

ARM64の割り込みコントローラ「The Generic Interrupt Controller(GIC)」

ARM64の「The Generic Interrupt Controller(GIC)」は,アーキテクチャ共通の割り込みコントローラです.

ARM64の例外ベクタテーブルは以下になります.

※VBAR_ELnは例外レベルnにおける例外ベクタテーブルのベースアドレスになります.

アドレス
(VBAR_ELnからのオフセット)
例外タイプ説明
VBAR_ELn + 0x000SynchronousSP0(例外レベル0のスタックポインタ)を利用して現在の例外レベルで処理
VBAR_ELn + 0x080IRQ/vIRQ
VBAR_ELn + 0x100FIQ/vFIQ
VBAR_ELn + 0x180SError/vSError
VBAR_ELn + 0x200SynchronousSPx(例外レベルxのスタックポインタ)を利用して現在の例外レベルで処理
VBAR_ELn + 0x280IRQ/vIRQ
VBAR_ELn + 0x300FIQ/vFIQ
VBAR_ELn + 0x380SError/vSError
VBAR_ELn + 0x400SynchronousARM64の低い例外レベル
VBAR_ELn + 0x480IRQ/vIRQ
VBAR_ELn + 0x500FIQ/vFIQ
VBAR_ELn + 0x580SError/vSError
VBAR_ELn + 0x600SynchronousARM32の低い例外レベル
VBAR_ELn + 0x680IRQ/vIRQ
VBAR_ELn + 0x700FIQ/vFIQ
VBAR_ELn + 0x780SError/vSError

ARM64にはアーキテクチャ共通のGICだけでなく,ボード固有の割り込みコントローラを持つ場合があります.

例えば,Raspberry Pi固有の割り込みコントローラ「BCM2835,BCM2836,BCM2837,BCM2837B0,BCM2711,BCM2710A1」を知りたいあなたは,「Raspberry Pi Documentation Processors」を読みましょう!

割り込みハンドラ(割り込みサービスルーチン(ISR:Interrupt Service Routine))

割り込みハンドラ(割り込みサービスルーチン(ISR:Interrupt Service Routine))は,特定の割り込みに応答してCPUが実行する関数のことです.

Linuxでは,通常のC言語の関数が特定のプロトタイプにマッチして,割り込みハンドラの情報を渡します.

割り込みハンドラは,割り込みコンテキスト(またはアトミックコンテキスト)で実行されます.

通常のタスク実行やシステムコールによるプロセスコンテキストとは逆の操作になります.

割込みコンテキストはスケジューリング可能なエンティティではないので,タスクは割り込みハンドラでスリープできません.

Top HalfとBottom Halfの割り込み処理

割り込みハンドラには2つの相反する目標があります.

  • 割り込み処理は高速でなければならない.
    • 実行中のユーザプロセス(ユーザ/カーネル空間)に割り込みするため.
    • 割り込み処理中に他の割り込みを禁止する必要がある場合あり.
  • かなりの量の作業を行うことがある.
    • そのため,時間がかかる.
    • 例:ネットワークカードからのネットワークパケットを処理する.

そこで,Linuxを含む多くの最新OSでは,割り込み処理をTop HalfとBottom Halfの2つに分けています.

  • Top Half
    • (一部または全部の割り込みを無効に設定して)割り込みを受けたら即実行
    • タイムクリティカルな処理のみ
    • 例:割り込みの受信を確認やハードウェアのリセット
  • Bottom Half
    • あまり重要でなく,時間のかかる作業
    • 他の割り込みを有効にして後で実行

Top HalfとBottom Halfの割り込み処理をネットワークのパケット処理を例にして説明します.

  • Top Half:割り込みハンドラ
    • ハードウェアを認識する.
    • 新しいネットワークパケットをメインメモリにコピーする.
    • ネットワークカードにパケットを追加できるようにする.
    • ネットワークカードのパケットバッファは容量に制限があるため(パケットドロップ),時間的な制約がある.
  • Bottom Half:コピーされたパケットを処理
    • softirq,tasklet,work queue
    • ユーザ空間のスレッドプールに似ている.

Bottom Halfの種類「softirq,tasklet,work queue」

どのBottom Halfを使うかの決定は性能の観点において重要です.

LinuxカーネルにおけるBottom Halfは,softirq,tasklet,work queueの3種類があります.

taskletはsoftirqの上に構築されており,よく似ています.

これに対して,work queueは,カーネルスレッド上に構築されています.

softirqは,高度にマルチスレッド化されたコード向けに最小限の割り込みのシリアライズ(Serialize)を提供します.

ここで,割り込みのシリアライズとは,割り込みの1つの処理が終了するごとに次の処理を開始するように,順番に実行することです.

このため,softirqハンドラは共有データの安全性を確保するために余分なステップを踏む必要があります.

なぜなら,同じタイプのsoftirqが異なるプロセッサ上で2つ以上同時に実行される可能性があるからです.

もし,問題のコードがすでに高度にマルチスレッド化されている場合,例えば,プロセッサ毎の変数に深く入り込んでいるネットワークサブシステムでは,softirqは良い選択となります.

タイミングクリティカルで高頻度な用途では,(Top Half以外のBottom Halfの種類において)softirqは最速の選択肢となります.

taskletは,主にマルチスレッド化されていないコード向けのシンプルなインターフェースです.

taskletは,同じタイプの2つのtaskletは同時に実行しない(可能性が高い)ので,実装がより簡単です.

ドライバ開発者は,softirqが複数のプロセッサで安全に同時実行できることを保証するために,プロセッサ毎の変数等を利用しない場合は,softirqよりもtaskletを常に選択すべきです.

work queueは,プロセスコンテキストで実行する必要がある場合に利用されます.

プロセスコンテキストが要件でない場合(ブロックやスリープする必要がない場合),work queueよりsoftirqやtaskletの方が適しています.

work queueは,カーネルスレッドを含むため,コンテキストスイッチが必要なり,最もオーバヘッドが大きくなります.

なので,ネットワークサブシステムのような1秒間に数千回の割り込みを処理することを考慮すると,work queueよりsoftirqやtaskletの方が理にかなっています.

しかし,ほとんどの場合において,work queueで十分な性能を発揮できて,使いやすいです.

項目softirqtaskletwork queue
コンテキスト割り込み割り込みプロセス
シリアライズの継承なしsoftirqに対して継承なし
実行速度速い普通遅い
使いやすさ難しい普通易しい

softirq,tasklet,work queueの比較は上表になります.

これらはすべて,一般的に割り込みが有効な状態で実行されます.

割り込みハンドラとの共有データ(Top Half)がある場合は,割り込みを無効にするか,ロックを使用する必要があります.

割り込みハンドラの関数

linux/include/linux/interrupt.hに割り込みハンドラの関数があります.

  • irq_handler_t:割り込みハンドラ関数のtypedef定義で,割り込みハンドラ関数を書く時に利用する.
  • request_irq関数:割り込みハンドラを登録する.
  • free_irq関数:割り込みハンドラを削除する.

request_irq関数のflags引数でIRQF_SHAREDフラグを設定しなければならないことに注意して下さい.

また,dev引数は,登録された各ハンドラに一意でなければなりません.

デバイス毎の構造体(例:struct device構造体)へのポインタで十分です.

カーネルは割り込みを受けると,その行に登録されているハンドラを順次呼び出します.

そのため,ハンドラは自分が発生させた割り込みかどうかを識別できることが重要です.

割り込みハンドラで処理する割り込みコンテキストは,プロセスコンテキスト(通常のタスク実行,システムコール)とは異なり,以下の制約があります.

  • スケジュール・エンティティではないので,スリープやブロック不可
  • kmalloc(size, GFP_KERNEL)は利用できず(GFP_KERNELはスリープ可),引数にGFP_ATOMIC(高優先度,スリープ不可)を利用
  • ブロッキングロック(mutex等)は利用できないため,spinlockを利用
  • printk関数は利用できないため,trace_printk関数を利用

割り込みコンテキストは,小さいスタックサイズ(1ページ,4KB)を持ちます.

各割り込みは,linux/inlucde/linux/irqdesc.hで定義されている割り込みディスクリプタ構造体irq_descによって記述されます.

割り込みは,記述子構造体配列の中から対応する割り込み記述子構造体を選択します.

ディスクリプタ構造体には,ステータス情報と,この割込みに割り当てられた割込みフローメソッドと割込みチップ構造体へのポインタが含まれます.

割り込みが発生すると,低レベルアーキテクチャのコードは,desc->handle_irq()を呼び出すことによって,汎用割り込みコードを呼び出します.

この高レベルのIRQ処理機能は,割り当てられたチップ記述子構造体によって参照されるdesc->irq_data.chipプリミティブのみを利用します.

※古いLinuxカーネルではdo_IRQ関数/__do_IRQ関数によるスーパーハンドラを使用しており,あらゆるタイプの割り込みロジックに対応することが可能でしたが,現在のLinuxカーネルでは割り込みロジック毎(レベルトリガ,エッジトリガ等)に分けて処理します.

割り込み制御

カーネルコードは,コードのセクションのアトミックな実行を保証するために,割り込みを無効にする必要がある場合があります.

割り込みを無効にすることで,割り込みハンドラが現在のコードをプリエンプションしないことが保証されます.

また,割り込みを無効にすることで,カーネルのプリエンプションも無効になります.

ただし,割り込みを無効しても,他のコアからの同時アクセスは防げないことに注意して下さい.

この場合はロックが必要になり,割り込み無効と併用されることが多いです.

割り込みの無効/有効マクロ

linux/include/linux/irqflags.hに割り込みを無効/有効にするための以下のマクロを提供しています.

  • local_irq_disableマクロ:割り込みを無効にする.
  • local_irq_enableマクロ:割り込みを有効にする.
  • local_irq_saveマクロ:現在の割り込みの無効/有効状態を保存した後に割り込みを無効にする.
  • local_irq_restoreマクロ:保存した割り込み無効/有効状態に戻す.(必ず割り込み有効になるとは限りません.)

Bottom Halfの割り込みの無効/有効関数

linux/include/linux/bottom_half.hにBottom Halfのsoftirqとtaskletの処理の無効/有効関数を提供しています.

  • local_bh_disable関数:Bottom Halfのsoftirqとtaskletの処理を無効にする.
  • local_bh_enable関数:Bottom Halfのsoftirqとtaskletの処理を有効にする.

※これらの関数は,work queueの処理を無効/有効にしないことに注意してください.(work queueの処理は常に有効になります.)

まとめ

今回は割り込みを紹介しました.

具体的には,以下の内容を解説しました.

  • 割り込みとは
  • 割り込みの種類
  • 割り込みコントローラ(PIC:Programmable Interrupt Controller)
  • 割り込みハンドラ(割り込みサービスルーチン(ISR:Interrupt Service Routine))
  • 割り込み制御

割り込みを深掘りしたいあなたは以下の記事を読みましょう!

最後まで読んで頂きありがとうございました.

LinuxカーネルはC言語で書かれています.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

次回はこちらからどうぞ.

第8回Linuxカーネル
【第8回】元東大教員から学ぶLinuxカーネル「同期」

こういった私から学べます. 前回を読んでいない方はこちらからどうぞ. Linuxカーネルの記事一覧はこちらからどうぞ. 今回のテーマは同期です. 同期を理解すると,カーネルの本質的な課題が深く理解でき ...

続きを見る

-TECHNOLOGY, LINUX KERNEL
-, , , , , , ,