Linux V2.4 カーネル内部解析報告 ドラフト 第4版

高橋浩和

改版履歴

本書は、Linux V2.4のカーネルソースの解析資料である。

ここで説明するデータ構造およびアルゴリズムは全てのことを網羅している訳ではなく、重要なデータ構造とその流れに重点をおいて説明してある。基本的に排他処理/エラー処理などの説明も行わない。

• もくじ
• 実行管理
  • プロセス管理
    • プロセスのモデル
      • プロセスを構成する資源
    • プロセスの状態遷移
    • プロセスの一生
      • fork
      • exec
      • exit
    • プロセススケジューリング
      • スケジューラ
      • プロセス切替え
      • プロセスの同期
    • プリエンプション処理
    • セマフォ
    • その他のスケジューリング関連関数の説明
    • プロセスの親子関係
    • プロセスID
      • 関数説明
    • シグナル
      • 関数説明
      • シグナルの無視とマスク
      • SIGCHLDシグナル
      • サスペンドシグナル
      • シグナル関連のデータ構造と、その他の関数
    • スレッド
  • 遅延処理
    • ソフト割り込みハンドラ
      • 関数説明
    • BHハンドラ
      • 関数説明
    • タスクキュー
      • 関数説明
  • 時計
    • クロックハンドラ
    • タイマーリスト
      • 関数説明
    • その他のタイマ関連機能
      • カーネル内時限待ち
      • setitimerシステムコール
  • 割り込み制御
    • 割り込みハンドラ
    • 割り込みハンドラの登録
    • 割り込みハンドラの起動
      • 問題点
    • 割り込み禁止
      • CPUレベルでの割り込み制御
      • 補足
      • 割り込みコントローラレベルでの割り込み制御
  • カーネルサービスのエントリ
    • システムコールエントリ
    • 割り込みエントリ
    • ページフォルト
    • 一般例外
• ファイルシステム
  • 構造
  • バッファキャッシュ
    • バッファの状態
    • バッファキャッシュの構造
    • バッファの確保
    • バッファの解放
    • ディスクブロックのバッファへの読み込み
    • ディスクブロックのバッファへの書き込み
    • ドライバに対するI/O要求
    • バッファに対するI/Oの待ち合わせ
    • バッファに対するI/O完了の通知
    • バッファ領域の拡張と解放
    • バッファとディスクブロックの同期
    • トリッキーなバッファ管理
    • その他の主なバッファ操作関数群
    • バッファの状態遷移
    • バッファ状態の監視
  • ページキャッシュ
    • iノードとページ
    • ページキャッシュハッシュ
    • ページに対するI/O要求の発行
      • ページ読み込み要求
      • ページに対するI/O完了の通知
      • ページ書き込み要求
    • ページキャッシュの確保と解放
    • その他の主なページキャッシュ操作関数群
  • メモリiノード
    • iノードキャッシュ
    • メモリiノードの確保
    • メモリiノードの解放
    • メモリiノード領域の解放
    • iノード域の更新
    • その他の主なiノード操作関数
    • iノードの状態遷移
    • iノード状態の監視
  • ディレクトリエントリキャッシュ
    • ディレクトリエントリキャッシュの検索と登録
    • dentryの参照要求と参照の終了
    • dentryのメモリ領域の拡張と解放
    • dentryのメモリ領域の強制解放
    • 主なdentry操作関数
    • キャッシュの相互関係
  • プロセスとfileの関係
    • ファイル構造体の確保と解放
    • その他、主なファイル構造体操作関数群
    • ファイル構造体の監視
  • ext2ファイルシステム構造と操作プリミティブ
    • ファイルシステムのレイアウト
    • ファイル構造
    • ディレクトリ構造
    • スーパブロックとブロックグループ操作
      • 主な処理関数
    • iノード確保アルゴリズム
      • アルゴリズム詳細
    • ディスクブロック確保アルゴリズム
      • アルゴリズム詳細
      • プリアロケート機能
    • ファイルオフセットからブロック番号への変換
      • ext2_getblk関数アルゴリズム
      • ext2_bread関数アルゴリズム
    • iノードとデータブロックの結合の解除
    • ディレクトリ操作
    • その他、主なプリミティブ関数群
  • vfsと各ファイルシステムのインターフェイス
    • ファイル操作
      • ファイル操作関数テーブル
      • iノード操作関数テーブル
      • アドレススペース操作関数テーブル
    • ファイルシステム操作
  • パス検索
    • その他の主なパス検索処理関数
    • ext2ファイルシステムでのパス名検索
  • 各種システムコールアルゴリズム
    • ファイルのオープン
    • ファイルの生成
    • ファイルの削除
    • トランケートシステムコール
    • ファイルの読み込み
    • ファイルへの書き込みとファイル拡張
    • lseekシステムコール
    • ファイルのクローズ
    • ディレクトリの生成
    • ディレクトリの削除
    • ディレクトリ内容の読みだし
    • ディレクトリ操作
      • link ファイルのリンク link
      • rename ファイルの移動 rename
    • シンボリックリンク
      • シンボリックリンクファイルの生成
      • シンボリックリンクファイルの読みだし
    • デバイスファイル作成と削除
    • fsyncシステムコール
    • statシステムコール
    • ioctlシステムコール
    • ファイルシステムのマウントとアンマウント
    • 主なシステムコールの関数呼び出し関係
    • ファイルアクセスの排他処理
  • システムコール以外のカーネル機能
    • 同期書き込み機能
      • 同期書き込みの種類

• • • /procファイルシステム
    • パイプ
  • デバイスドライバIF
    • ドライバの登録
    • I／O起動インターフェイス ブロック I/O起動インターフェイス
    • デバイスファイル
    • デバイスドライバのモデル
    • SCSIドライバの構成
  • RAID
  • コンフィギュレーション
  • まとめ、考察、問題点
    • 問題点
    • その他の注意点
• 空間管理
  • 空間レイアウト
  • ページングモデル
    • PGD、PMD、PTE操作関数群
    • カーネル空間
      • 物理アドレスとカーネル仮想空間の対応
  • プロセス空間
    • 空間モデル
    • 空間の生成
      • ヒープ領域の拡張とファイルマッピング
    • デマンドロード
    • 空間の複製
    • コピーオンライト
    • ページアウト
    • ページイン
    • スタックの成長
    • 空間の解放
    • 共有空間
    • PTEの状態遷移
    • ページ解放処理詳細
      • ページ解放の方針
      • メモリ解放要求の発生
      • スワップキャッシュ
  • フリーページ管理
  • メモリアロケーション
• ネットワーク
  • プロトコルスタック構造
    • スタックモジュール間インターフェイス
    • ソケットデータ形式
    • パケット形式
    • 操作関数群
  • ソケットレイヤ
    • ソケットの作成
    • 送受信準備
    • データ送受信操作
    • ソケットの解放
    • 操作関数群
  • ネットワークドライバインターフェイス
    • ドライバの登録
    • イーサヘッダ形式
    • 受信処理
    • 送信処理
      • 各種操作関数群
  • IPプロトコルスタック
    • IPヘッダ形式
    • 送信処理
    • 受信処理
    • IPパケット転送処理
    • IPパケットのフラグメント
  • ルーティング
    • データ構造
      • 静的ルーティングテーブル
      • ルーティングテーブルキャッシュ
    • 送信処理時のルーティング
    • 受信処理時のルーティング
  • ARP
    • ARPヘッダ形式
    • データ構造
    • アドレスの解決
  • UDPプロトコルスタック
    • UDPヘッダ形式
    • 送信処理
    • 受信処理
  • TCPプロトコルスタック
    • TCPヘッダ形式
    • シーケンス番号とACK
    • 送受信ウィンドウ
    • 送信処理
      • 送信キューデータ構造
      • 送信処理アルゴリズム
      • 応答(ACK)受信と送信再開
      • 再送処理
      • 輻輳回避とスロースタート
    • 受信処理
      • 受信キューデータ構造
      • 受信処理アルゴリズム
    • コネクション状態遷移
    • コネクションの確立
      • クライアント側処理
      • サーバ側処理前半
      • サーバ側処理後半
      • accept処理 サーバ側 accept処理
    • コネクションの切断
      • 切断処理第一段階
      • 切断処理第二段階
      • LISTEN状態のソケットの解放
      • コネクションのshutdown
    • TCPタイマ
      • 再送タイマ
      • KEEPALIVEタイマ
      • TIME_WAITタイマ
  • その他
    • loopbackデバイス
    • プロトコル実行コンテキスト
• システムの起動
  • Linuxカーネルの起動
    • エントリポイントとCPUの初期化
    • カーネル資源の初期化
    • initプロセスの起動
  • システムの終了
    • システムの正常終了
    • システムの異常終了
• マルチプロセッサ管理
  • スケジューリング
    • 対称型マルチプロセッサシステム
    • プロセススケジューラ
    • スケジューリングポリシー
  • ハードウェア割り込み
    • プロセッサ間割り込み
      • その他の関数説明
  • 時計
  • ソフト割り込みハンドラ
  • 排他制御
    • スピンロック
      • スピンロック関数
      • アトミック更新関数
    • カーネル全体のロック
    • スケジューラ資源
    • そのほかの資源
    • カーネルロック処理の流れ
    • カーネルロック関数の動作詳細
    • 割り込み処理の排他
      • 割り込み処理とソフト割り込み処理の排他メカニズム
      • その他の関数
    • 補足説明
  • マルチプロセッサシステムの起動
• このドキュメントについて