無料Wikiサービス | デモページ
Linux Kernel(2.6)の実装に関するメモ書き
リンク
最近更新したページ
検索

その他


BH
	マルチプロセッサでも複数実行は不可
	登録数は32まで。
	(2.4の実装としては高優先度タスクレットとして登録され実行される)

タスクキュー
	BHの拡張。
	一つのBHに複数のハンドラを登録できる。

	以下のタスクキューはBHの中で処理される。
	tq_immediate 即実行用タスクキュー
	tq_timer     タイマ用タスクキュー
	他にもタスクキューは存在する。

ソフト割り込み
	マルチプロセッサの場合、各プロセッサで同じ割り込みが動作可能

タスクレット
	ソフト割り込みの一つ。

	複数のハンドラを登録できる。
	複数のCPUで同時実行できるが同じタスクレットは同時実行できない。




softirq_vec[]
+--------------+
|              | HI_SOFTIRQ:tasklet_hi_action()
+--------------+
|              | NET_TX_SOFTIRQ
+--------------+
|              | NET_RX_SOFTIRQ
+--------------+
|              | TASKLET_SOFTIRQ:tasklet_action()
+--------------+
	:
+--------------+
|              |
+--------------+
ソフト割り込みのハンドラが登録される。
open_softirq()で登録する。
raise_softirq()でスケジュールする


tasklet_vec[] (HI_SOFTIRQ用にtasklet_hi_vec[]もある)
+--------------+
| CPU#0        | --> tasklet_struct -> tasklet_struct ->
+--------------+
| CPU#1        |
+--------------+
	:
タスクレットのハンドラを登録する。
tasklet_init()でtasklet_structを初期化して、
tasklet_schedule()によってtasklet_structをチェーンして、
TASKLET_SOFTIRQをスケジュールする


bh_task_vec[]
+--------------+
|              | bh_action()
+--------------+
|              | bh_action()
+--------------+
	:
+--------------+
|              | bh_action()
+--------------+
BHは高優先度タスクレット(HI_SOFTIRQ)の一つとして実行される。
BH呼出し用のタスクレット一覧。
mark_bh()によってtasklet_hi_vec[]にチェーンされる。


bh_base[]
+--------------+
|              |
+--------------+
|              |
+--------------+
	:
+--------------+
|              |
+--------------+
BHのハンドラが登録される。
init_bh()で登録。





do_softirq()
	softirq_vecに登録されているハンドラを呼出
	タスクレットのソフト割り込みが発生していたらtasklet_(hi_)action()
	を呼び出してタスクレットを処理

tasklet_hi_action()
	tasklet_hi_vec[]に登録されているタスクレットハンドラを呼出
	BHのタスクレットもここに登録される。
	BHのタスクレットはハンドラbh_action()を指している。


tasklet_action()
	tasklet_vec[]に登録されているタスクレットハンドラを呼出
	(チェーンされているタスクレットを全て実行)

bh_action() <-- 高優先度タスクレットとして実行
	bh_base[]に登録されているBHハンドラを呼出



queue_task()
	タスクキューに関数を追加

run_task_queue()
	タスクキュー内の関数を全て実行

IMMEDIATE_BH <--デバイスドライバ等から適宜スケジュールされる
immediate_bh()
	run_task_queue(&tq_immediate);


TQUEUE_BH <-- TIMER_BHと一緒にスケジュールされる。
tqueue_bh()
	run_task_queue(&tq_timer);



do_softirq()呼出契機
	ksoftirqd()
	do_irq()でハードウェア割り込みを処理した後

	例外やシステムコールからの戻りでは呼ばれなくなっている。
	代わりにraise_softirq()でソフト割り込みをスケジュールすると
	ksoftirqd()がwakeupされる。

	スケジュールしてからksoftirqd()が動き出す前に
	ユーザモードに戻ってしまう事はない?

ソフトウェア割り込みをマスクするには?
	Linux2.2ならdisable_bh()がある。
	各割り込み種別毎に独自に実施?
	cliする?


Kernel Thread
       UserProcessと異なりKernelMode(SupervisorMode)で動作するため、
       プリエンプトされない?
       明示的にBlockしてCPUを手放す必要がある?


-------------------------------------
排他制御

cli ハードウェア割り込み禁止
    Uniprocessor   - cli命令実行するだけ
    MultiPorcessor - 全CPUで割り込み禁止にする。
		     実際にはLocalCPUのみcliしてRemoteCPUについては
		     get_irqlock()でspinlockを取得し、
		     割り込みハンドラの実行を遅延させている。
		     (get_irqlock()コール時、既に他のCPUで割り込み処理中なら
		      終了までspinして待たされる。)

    cliでハードウェア割り込みを禁止している最中に
    Blockされる処理を実行してはいけない。
    Freezeする可能性あり。
    (Blockして切り替わった先がユーザプロセスでwhile(1);で
     Systemコールも呼ばない場合は、プロセスの切替えが発生できずに
     即Freeze)


atomic_add()
	addl命令に展開されている。
	1命令なのでUniProcessorならこれでatomicであるが、
	メモリアクセスはRead/Writeで2回発生するので
	MultiProcessorだとatomicとならない。
	このためSMPの時は、lock prefixをつけてatomicとなるようにする。

spin_lock()
	SpinLock取得
	取得できるまでSpin

spin_lock_irq()
	LocalCPUについてcliで割り込み禁止にして、
	SpinLock取得

	割り込みハンドラからも使用されるデータを排他制御する場合は、
	DeadLock防止のため、こちらを使用する。

	LocalCPUについて割り込み禁止しておかないと
	通常ContextでSpinLock取得した後、
	割り込みが発生して同じSpinLockを取ろうとした時、
	DeadLockする。
	他のCPUの割り込みは禁止にする必要はない。


-------------------------------------
VFS

sys_read(fd, buf, count)
	     fdからfile構造体を取得

	     file->f_op->read() - ext2ならgeneric_file_read()

-------------------------------------
Ext2

ページキャッシュへの読み込み
ext2_readpage(struct file *file, struct page *page)
	block_read_full_page() <-- 汎用ルーチン呼ぶだけ


(inode,オフセット(Block数)) -> ブロック番号変換ルーチン
ext2_get_block() - bhにBlock番号を設定して返す
	ext2_block_to_path()
		ファイル先頭からのオフセット(Block#)から
		i_block[]のどこをたどればよいかをoffsetsに格納する。

	ext2_get_branch()
		offsetsが指しているi_block[]に格納されているBlock番号をchainに格納していく。
		Indirectアクセス(オフセットBlock数が12以上)なら
		sb_bread()でi_block[]のあるBlockを読み込んでたどっていく。
		<--内部はbread()。デバイスの指定Blockの読み込み。
		   BufferCacheにCacheされる。(既にCacheにあればディスクアクセスはしない)
		chain[]の最後のエントリに格納されたBlock番号が取得したかったBlock番号

	取得したBlock番号をBHに設定して返す。

ext2_read_inode()
	inodeが格納されているBlock#を計算
	bread() - inodeのあるBlockを読み込み
	読み込んだBlockのinodeをメモリinodeへコピー



-------------------------------------
ページキャッシュ
mm/filemap.cがメイン

ファイルをキャッシュする。
キャッシュはPageそのもの。
inodeとファイル先頭からのオフセット(PageSize単位)で識別される。
キャッシュしているページは複数のバッファから構成される。
<--- バッファは"一時的なもの"でhash_table[]には登録されない?
     バッファキャッシュではない?
     バッファキャッシュへ書き込みした時の同期はどうする?


generic_file_read() - 指定ファイルの指定offsetからの読み込み
	ページキャッシュにデータがあればそのデータを
	ユーザバッファに返す。なければ、一旦ページキャッシュに
	読み込んでからそれを返す。(読み込み完了するまではBlock)

	do_generic_file_read()
	offset(*ppos)からページ番号とページ内のオフセットを算出


	:
	page_hash()でハッシュのエントリ取得
	__find_page_nolock() でハッシュエントリからページキャッシュを下す
	PageCacheが見付からなければno_cache_pageへ。

found_page:
	:
page_ok:
	actor() - file_read_actor()
		ユーザエリアのバッファへページのデータをコピー
	終了。

readpage:
	mapping->a_ops->readpage(filp, page) ページキャッシュへの読み込み
	(Ext2ならext2_readpage())
	PageがUptodate状態ならpage_okへ飛んでバッファにデータをコピー
	Uptodateでなければ、generic_file_readahead()で先読みを実施し
	Blockする。
	(end_buffer_io_async()でPageがUptodateになるとwakeupされる)
	(readpage()は非同期実行なので、ここでは基本的にUptodateではない?)
	:
	リードエラーなら。。。

no_cached_page: ページキャッシュが無かった場合
	page_cache_alloc() ページキャッシュ用にBuddySystemから1Page取得
	__add_to_page_cache() 取得したページをハッシュに登録
		add_page_to_inode_queue(mapping, page);
			mapping->clean_pagesに挿入
		add_page_to_hash_queue(page, hash);
			ハッシュエントリに挿入
	lru_cache_add() LRUキャッシュにも登録
		zone->active_listに登録
	goto readpage


ページキャッシュ管理方法
(1) ページハッシュテーブル
page_hash_table
+-------------+     struct page
|             |---> +--------+
+-------------+     |        | ----> ...
|             |     |        | next_hash
+-------------+     |        |
       :
+-------------+
|             |
+-------------+

(2) iノードキュー



以下、ソースはbuffer.cにあるがページキャッシュの処理
(ページとバッファの橋渡しをしている)

block_read_full_page(page,get_block) - ページキャッシュへの読み込み汎用ルーチン
	get_block引数に(inode,ファイルオフセット) -> ブロック番号
	変換関数を渡す。(ext2ではext2_get_block())

	page->buffersが無ければcreate_empty_buffer()で空のバッファ作成
		ページディスクリプタpageで指定したページ内に
		複数バッファが作成される。
		page->buffersに先頭のBufferHeadが格納される。


	ページ内の全バッファがUptodateならページをUptodate状態にして終了
	get_block(); - (inode,ファイルオフセット) -> ブロック番号変換
		       (Ext2ならext2_get_block())
		bh->b_blocknr にBlock#が設定され
		BH_Mappedがセットされる
	:
	以下、ページ内のUptodateでないBufferに対してI/O要求を出す
	set_buffer_async_io()
		BufferHeadを設定
		(1) I/O終了時のコールバックをend_buffer_io_async()に設定
		(2) BH_Asyncを設定

	submit_bh(READ, arr[i]);
		:
		"Blockデバイス - 共通部分"参照


end_buffer_io_async() バッファI/O完了時に呼ばれるコールバック
	BufferをUptodate状態にする。

	Page内のBufferが全て読み込み完了していたら、
	PageをUptodate状態にする。

	UnlockPage()
		Pageのリード待ちになっていたプロセスをwakeup


mappingとは???
struct address_space



-------------------------------------
バッファキャッシュ

	ディスクのブロックをキャッシュしている。



bread() - 指定デバイスの指定ブロックから読み込み
	BufferCacheに指定ブロックがキャッシュされていればそれを返す。
	BufferCacheにない場合は、デバイスからCacheに読み込んだ後
	Cacheを返す。(読み込みが完了するまでBlockする)

	BufferHeadをハッシュから取得。
	(なければ新規作成)
	Uptodate状態なら既にキャッシュが最新状態なので
	それを返す。
	そうでなければ、ll_rw_block(READ)で
	デバイスに読み込み要求を発行する。
	(実際には要求は即時に発行されるわけではない)
	wait_on_buffer(bh) - Lock解除までBlockする
		TaskQueue(tq_disk)に登録しているハンドラを処理する。
		<-- ここでDeviceがUnplugされてRequestが発行される?
		BufferがLockされていなければそのまま処理続行。
		LockされていたらWaitQueue(bh->b_wait)にtask_structを登録し
		Block(UNINTERRUPTIBLE状態にしてタスクスイッチ)する。


bwrite() は存在しない。
各書き込み処理で以下を行う?
	1. getblk()でBufferCacheを取得
	2. 書き込み
	3. BH_Dirtyセット
	4. I/O要求発行



バッファキャッシュ管理方法
hash_table[]
+-------------+      struct buffer_head
|             |----> +-------+ ----> ...
+-------------+      |       | b_next
|             |      |       |
+-------------+
       :
       :
+-------------+
|             |
+-------------+


---------------------
Blockデバイス - 共通部分

ll_rw_block() - BlockデバイスにRead/Write要求を出す
	        すぐにはデバイスにRequestを発行しない

	bh->b_end_io = end_buffer_io_sync

	submit_bh()
		generic_make_request()
			__make_request()
				RequestQueueが空なら
				q->plug_device_fn(generic_plug_device())
					q->plugged = 1

					q->plug_tq(generic_unplug_device())を
					tq_diskに追加する。

				Requestを可能ならマージする。
				マージできなければ、新規リクエスト作成
				RequestQueue(device毎に持つ)へ挿入。

end_buffer_io_sync(bh, uptodate) - I/O完了時のハンドラ
	BufferをUptodate状態に。
	(エラーならフラグクリア)
	unlock_buffer()
		BH_Lockクリア
		wake_up(&bh->b_wait)
		<-- Buffer読み込み待ちでBlockしていたProcess
		    をWakeup


run_task_queue(&tq_disk)すると、
登録されたハンドラ(generic_unplug_device())が実行され
Unplug(q->plugged = 0)された後、
q->request_fn(IDE-HDの場合、do_hd_request())を実行して
溜ったRequestを実際にデバイスに発行する。


run_task_queue(&tq_disk)する契機
	wait_on_buffer()
	:
	:


Plugされていると、、、


---------------------
Blockデバイス - IDE HardDiskの例

do_hd_request() - Requestの処理
	hd_request()
	:
	:


デバイスのRequestが完了もしくはエラー終了すると...
end_request()
	end_that_request_first()
		bh->b_end_io(bh, uptodate) - I/O完了ハンドラ
			例:
				バッファI/Oの場合 - end_buffer_io_sync()
				ページI/Oの場合   - end_buffer_io_async()


デバイスドライバの外部インタフェースは
	Request受け付け
	ioctl
だけ??


-------------------------------------
仮想記憶

kswapd() - PageOut用カーネルスレッド

最終更新 2006/03/27 14:14:21 - kztomita
(2006/03/27 14:14:21 作成)