Linux Kernel勉強会メモ

Created on 2018-02-14
Modified on 2018-06-23
Published on 2018-02-21

第1回 (2018-02-15 10:00 ~)

syscallが呼ばれる際の動作

割り込みベクターテーブル (Interrupt Vector Table; IVT)

参考: Interrupt vector table - Wikipedia

OSの起動プロセス

Memory Layout

Overview

こんな感じのレイアウトになっている。 このリストは、アドレスが小さい順に並べてある。

  1. User space
    1. Text segment
    2. Data segment
    3. BSS segment
    4. Heap
    5. Memory mapping segment
    6. Stack
  2. Kernel space

参考: 「Segmentation mémoire et Buffer Overflow – 0x0ff.info」に掲載されている画像

User Space

Kernel Space

参考: Anatomy of a Program in Memory | Many But Finite

Linuxのファイルシステムの構造

VFS

物理ファイルシステム

ELF

その他

x86-64 CPUのレジスタ

第2回 (2018-02-21 10:00 ~)

Ext2

Linux v4.16-rc2 (commit 91ab883eb21325ad80f3473633f794c78ac87f51)でのext2の実装を調査してみた。

Ext2 - file_operations

Ext2 - inode_operations

Dirをreadするとき (ext2の場合)

  1. readdir.c:459:getdents(2): アプリケーションがgetdents(2)を呼び出す。
    ※ readdir(2)は廃止され、代わりにgetdents(2)を使用する。
  2. readdir.c:478:getdents(2): direntをキャッシュに読み込んで、user spaceにコピー
    1. readdir.c:40:iterate_dir: inodeのロックを取る
    2. readdir.c:51:iterate_dir: file->f_op->iterate_shared()
      1. dir.c:308:ext2_readdir: ページキャッシュを取得する (何を? どこから?)
        この中の処理は、よく分からない。
        ページキャッシュに乗ってたらそれのアドレスを返す。 キャッシュに乗ってなかったら…? (mm/filemap.c:2768:wait_on_page_read)
      2. dir.c:341:ext2_readdir: readdir.c:218で指定したコールバック関数(filldir)を呼び出す。 filldirの中では、user spaceにある配列にdirentの内容をコピーしている。
      3. dir.c:350:ext2_readdir: 確保したページを開放する。
    3. readdir.c:58:iterate_dir: inodeのロックを開放
  3. readdir.c:488:getdents(2): fdのposを更新

Fileをopenしたとき (ext2の場合)

  1. open.c:1077:open(2): do_sys_open()
    1. open.c:1057:do_sys_open: fd構造体を割り当てる
    2. open.c:1059:do_sys_open: do_filp_open()
      1. namei.c:3553:do_filp_open: path_openat()
        1. namei.c:3496:path_openat: file構造体を割り当てる
        2. namei.c:3518:path_openat: link_path_walk() - パス名解決をする (後述)
        3. namei.c:3519:path_openat: do_last()
          1. namei.c::do_last: 色々チェックしたり、automountしたり。
          2. namei.c:3378:do_last: vfs_open()
            1. open.c:857:vfs_open: do_dentry_open
            2. open.c:750:do_dentry_open: f_op->open()
              openには、dquot_file_open()へのポインタが入ってる。
              1. dquot.c:2153:dquot_file_open: generic_file_open()
              2. dquot.c:2154:dquot_file_open: 書き込みモードで開いた (dquot.c:2154) & quotaが有効化されていたとき
                1. dquot.c:1436:__dquot_initialize: 3種類のQuotaを初期化されているかチェック
                2. dquot.c:1487:__dquot_initialize: 初期化されて無ければ、初期化する。
    3. open.c:1065:do_sys_open: fdをfdtableに書き込む

Fileをreadしたとき (ext2の場合)

  1. read_write:568:read(2): fd(数値)からfd構造体を取得する。
  2. read_write:573:read(2): vfs_read()
    1. read_write:440:vfs_read: ユーザが指定したバッファがvalidなものかチェック
    2. read_write:443:vfs_read: readアクセス可能な領域かチェック
    3. read_write:447:vfs_read: __vfs_read()
      1. read_write:413:__vfs_read: new_sync_read()
        1. read_write:401:new_sync_read: call_read_iter() ==> f_op.read_iter()
          1. file.c:170:ext2_file_read_iter: generic_file_read_iter()
            1. filemap.c:2364:generic_file_read_iter: generic_file_buffered_read()
              1. filemap:2071:generic_file_buffered_read: indexとoffsetを計算
              2. filemap:2071:generic_file_buffered_read: 色々やってる
  3. read_write:575:read(2): positionをファイル構造体のf_posに保存

使用されていた略語

処理の最小単位

第3回 (2018-02-27 10:00 ~)

(VFS) パス解決の流れ

パス解決は、fs/namei.cの中のlink_path_walk()に実装されている。 パスのコンポーネント (“/”で区切られたディレクトリやファイル名のこと) 1つ1つを、以下のような手順で走査していき、最終的に目的とするinodeを得る。

  1. 親ディレクトリのアクセス権限 (executeビットが立っているかなど) をチェック
  2. コンポーネント名から、32bitのハッシュ値を計算する。 戻り値の64bit整数は、上位32bitがコンポーネント名の長さ、下位32bitがハッシュ値が入っている。
  3. 連続する”/“を全て除去する。 例えば、”/usr//////lib”でもちゃんとパス解決出来るようにするため。
  4. walk_component()

ext2のdisk layout

参考: Disk layout of ext2 and ocfs2の9ページ目

ext2

ext2のinode_operations

Fileをmapする

ext2_fiemapから、generic_block_fiemapを呼び出しているだけ

Dirにファイルを作る

  1. ext2/namei.c:106:ext2_create:
    1. ext2/ialloc.c:447:ext2_new_inode: struct inodeを作る
    2. ext2/ialloc.c:454:ext2_new_inode: inodeを配置するgroupを決定。directoryのinodeを配置するgroupを決めるアルゴリズムは2種類ある。
      参考: The Second Extended Filesystemのoldallocとorlovを参照。
    3. ext2/ialloc.c:467:ext2_new_inode: inode tableが空いているgroupを探す。全て埋まっていた場合は、隣のgroupから探す。
    4. ext2/ialloc.c:482:ext2_new_inode: inode bitmapをスキャンして、空いている場所にflagを立てる。
    5. ext2/ialloc.c:519:ext2_new_inode: inode bitmapに対応するbuffer_headをdirty (diskと同期が取れていない状態) にする。
    6. ext2/ialloc.c:534:ext2_new_inode: カウンタを更新
    7. ext2/ialloc.c:551:ext2_new_inode: struct inodeとstruct ext2_inode_infoのフィールドを初期化
    8. ext2/ialloc.c:602:ext2_new_inode: 新しく確保したinodeをdirtyにする。
    9. ext2/ialloc.c:604:ext2_new_inode: デバイスが混雑していなければ先読み

bio周り

わからん

第4回 (2018-03-06 16:00 ~)

ネットワーク

パケットフォーマット

通信手順 (TCPクライアント)

  1. socket(2)
  2. bind(2)
  3. connect(2)
  4. read(2) / write(2) / send(2) / recv(2)
  5. close(2)

TCPクライアント側でwrite(2)/send(2)したときに起きること (概要)

  1. 送信したいデータをsocket bufferに保存
  2. 送信先のmacアドレスを決める
    1. ルーティングテーブルを見て、本当の送信先のIPアドレスを引く
    2. ARPテーブルを見て、送信先のmacアドレスを引く
  3. NICがパケットを送信
  4. ACKが帰ってきた分のデータをsocket bufferから削除

実装

プロトコル毎にハンドラが異なるため、input/outputハンドラをプロトコル毎に定義してもらう実装になっているみたい。

プロセス切り替え

プロセス切り替えをするときに起こること

第5回 (2018-03-26 15:00 ~)

デバイスドライバ: パケットをmacパケットを受信 デバイスドライバ: macパケットのヘッダーに書いてあるプロトコル番号を見て、それぞれのプロトコルのルーチンをcallする。 ip_input.c: ip_recv() IP headerのverifyをする nf_hookの中で、これ以降の処理を処理をするスレッドを割り当てる。

ルーティングテーブルの確認。 dst_input(): ???

packet: forward/receive/drop ## TCP層 パケットを受信したとき * ACK返し、ついでにWindow Sizeを更新。 * バッファに追加。 * readシステムコールでブロックされているプロセスを起こす。

TCP層 パケットを送信するとき

pci_driver.prove

inet_add_protocol

kernelで使われている同期命令の種類の一覧

mmの仕事

第6回 (2018-04-05 13:00 ~)

Semaphore

User processで使うsemaphore

Kernelで使うsemaphore

使われ方

スレッド間・プロセス間でデータ共有するとき

mutexの実装

mutex_lock()

ロック取れなかったら、schedule()を呼び出し、その中でアーキテクチャごとに実装されている __switch_to_asm() と __switch_to() に飛ぶ。 レジスタの中身とアドレススペースを切り替え、TLBを消す。

Thread

Linuxでは、一つの論理アドレス空間を共有している複数のプロセスとして実装されている。

https://mookjp.github.io/memo/linux%E3%81%AE%E3%83%A1%E3%83%A2%E3%83%AA%E7%AE%A1%E7%90%86%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6/

第7回 (2018-04-17 18:30 ~)

プロセス切り替えの仕方

__schedule()で次に切り替えるタスクを選び、context_switch()を呼び出す。 その中でswitch_mm_irqs_off()が呼び出され、ユーザ空間のアドレス空間を切り替える。 その後、__switch_to_asm()を呼び出し、タスクを切り替える。 __switch_to_asm()は、先頭でレジスタを保存しているが、C言語から呼び出したときに自動的に保存されるなどの事情で、asmでは一部のレジスタしかpushしてない。

task_struct 構造体

プロセスに関するデータが詰まっている。 実行状態(state)や、pidなど。 レジスタの内容など、アーキテクチャ依存な部分はthread_structに実装されている。

略語

smp: shared memory processer rq: runqueue