第 1章 準(zhǔn)備工作 1
1.1 DIM-SUM簡(jiǎn)介 1
1.2 DIM-SUM是什么 1
1.2.1 DIM-SUM的第一個(gè)版本為什么是HOT-POT 1
1.2.2 DIM-SUM歡迎什么 2
1.2.3 DIM-SUM不歡迎什么 3
1.3 獲得源代碼 3
1.3.1 通過(guò)網(wǎng)頁(yè)下載源代碼 3
1.3.2 通過(guò)Git獲取源代碼 3
1.4 搭建調(diào)試開(kāi)發(fā)環(huán)境 4
1.4.1 安裝ubuntu 16.04 4
1.4.2 ubuntu 16.04環(huán)境配置 5
1.4.3 搭建編譯環(huán)境 6
1.4.4 編譯HOT-POT 7
1.4.5 運(yùn)行HOT-POT 8
1.4.6 開(kāi)始調(diào)試 10
1.5 向DIM-SUM操作系統(tǒng)提交補(bǔ)丁 11
1.5.1 心態(tài) 11
1.5.2 準(zhǔn)備工作 11
1.5.3 制作補(bǔ)丁 13
1.5.4 制作正確的補(bǔ)丁 14
1.5.5 發(fā)送補(bǔ)丁 16
1.6 獲得幫助 17
1.7 提醒 17
第 2章 算法基礎(chǔ) 18
2.1 鏈表 18
2.2 散列表 19
2.3 紅黑樹(shù) 20
2.4 基樹(shù) 22


第 3章 計(jì)數(shù)與互斥同步 23
3.1 計(jì)數(shù) 23
3.1.1 計(jì)數(shù)的難題 24
3.1.2 精確計(jì)數(shù)器 24
3.1.3 近似計(jì)數(shù)器 27
3.1.4 引用計(jì)數(shù) 31
3.2 內(nèi)核互斥原語(yǔ) 32
3.2.1 每CPU變量 32
3.2.2 自旋鎖 38
3.2.3 自旋位鎖 42
3.2.4 自旋順序鎖 44
3.2.5 自旋讀/寫(xiě)鎖 47
3.2.6 讀/寫(xiě)信號(hào)量 50
3.2.7 互斥鎖 56
3.3 內(nèi)核同步原語(yǔ) 60
3.3.1 信號(hào)量的設(shè)計(jì)原理 60
3.3.2 信號(hào)量的數(shù)據(jù)結(jié)構(gòu) 61
3.3. 3 信號(hào)量API 61
3.3.4 信號(hào)量的實(shí)現(xiàn) 62
第 4章 調(diào)度 65
4.1 基本概念 65
4.1.1 進(jìn)程和線程 65
4.1.2 任務(wù) 66
4.1.3 任務(wù)搶占 66
4.1.4 idle線程 66
4.2 SMP CPU初始化 66
4.3 數(shù)據(jù)結(jié)構(gòu) 71
4.3.1 線程 71
4.3.2 調(diào)度隊(duì)列 76
4.3.3 雜項(xiàng) 77
4.4 調(diào)度子系統(tǒng)初始化 77
4.4.1 init_sched_early函數(shù) 78
4.4.2 init_idle_process函數(shù) 78
4.4.3 init_sched函數(shù) 79
4.5 線程調(diào)度 79
4.5.1 上下文切換 79
4.5.2 喚醒線程 82
4.6 高級(jí)調(diào)度API 85
4.6.1 等待隊(duì)列 85
4.6.2 位等待隊(duì)列 89
4.6.3 線程睡眠 93
4.6.4 消息隊(duì)列 96
第 5章 中斷及定時(shí)器 108
5.1 中斷控制器初始化 108
5.1.1 主CPU中斷控制器初始化 109
5.1.2 從CPU中斷控制器初始化 110
5.2 中斷控制器維護(hù) 110
5.2.1 中斷號(hào)映射 110
5.2.2 邏輯中斷的控制 113
5.2.3 設(shè)備中斷處理函數(shù) 116
5.3 中斷處理 119
5.3.1 序言 119
5.3.2 中斷處理通用流程 120
5.3.3 處理外部設(shè)備中斷 122
5.3.4 處理核間中斷 126
5.3.5 軟中斷 126
5.3.6 尾聲 126
5.4 工作隊(duì)列 128
5.4.1 工作隊(duì)列的數(shù)據(jù)結(jié)構(gòu) 128
5.4.2 工作隊(duì)列的全局變量 130
5.4.3 工作隊(duì)列的API 130
5.4.4 工作隊(duì)列的實(shí)現(xiàn) 131
5.5 定時(shí)器與時(shí)間管理 139
5.5.1 初始化 139
5.5.2 定時(shí)器的數(shù)據(jù)結(jié)構(gòu) 139
5.5.3 定時(shí)器的全局變量 141
5.5.4 定時(shí)器的API 141
5.5.5 定時(shí)器的實(shí)現(xiàn) 141
5.5.6 定時(shí)器中斷處理 144
5.5.7 時(shí)間管理 148
第 6章 內(nèi)存管理 151
6.1 內(nèi)存初始化 151
6.1.1 艱難地準(zhǔn)備C運(yùn)行環(huán)境 151
6.1.2 準(zhǔn)備BOOT內(nèi)存空間 152
6.1.3 物理內(nèi)存塊管理 152
6.1.4 早期設(shè)備內(nèi)存映射 153
6.1.5 初始化每CPU變量 157
6.1.6 初始化線性映射 157
6.1.7 其他內(nèi)存初始化工作 160
6.2 BOOT內(nèi)存分配器 160
6.2.1 BOOT內(nèi)存分配API 161
6.2.2 BOOT內(nèi)存分配器的實(shí)現(xiàn) 161
6.2.3 BOOT內(nèi)存分配器的銷(xiāo)毀 163
6.3 頁(yè)面編號(hào) 163
6.3.1 頁(yè)面編號(hào)的數(shù)據(jù)結(jié)構(gòu) 164
6.3.2 頁(yè)面編號(hào)的全局變量 165
6.3.3 頁(yè)面編號(hào)的API 165
6.3.4 頁(yè)面編號(hào)的實(shí)現(xiàn) 165
6.4 頁(yè)面分配器 168
6.4.1 頁(yè)面分配器的設(shè)計(jì)原理 168
6.4.2 頁(yè)面分配器的數(shù)據(jù)結(jié)構(gòu) 169
6.4.3 頁(yè)面分配器的全局變量 174
6.4.4 頁(yè)面分配器的API 175
6.4.5 頁(yè)面分配器的實(shí)現(xiàn) 176
6.4.6 頁(yè)面分配器的初始化 192
6.5 Beehive內(nèi)存分配器 193
6.5.1 Beehive內(nèi)存分配器的設(shè)計(jì)原理 193
6.5.2 Beehive內(nèi)存分配器的數(shù)據(jù)結(jié)構(gòu) 195
6.5.3 Beehive內(nèi)存分配器的全局變量 197
6.5.4 Beehive內(nèi)存分配器的API 199
6.5.5 Beehive內(nèi)存分配器的實(shí)現(xiàn) 199
6.5.6 Beehive內(nèi)存分配器的初始化 214
6.6 I/O內(nèi)存映射 216
第 7章 塊設(shè)備 219
7.1 磁盤(pán)及其分區(qū) 220
7.1.1 磁盤(pán)及其分區(qū)的數(shù)據(jù)結(jié)構(gòu) 220
7.1.2 磁盤(pán)及其分區(qū)的全局變量 222
7.1.3 磁盤(pán)及其分區(qū)的API 222
7.1.4 磁盤(pán)及其分區(qū)的實(shí)現(xiàn) 222
7.2 塊設(shè)備維護(hù) 228
7.2.1 塊設(shè)備的數(shù)據(jù)結(jié)構(gòu) 228
7.2.2 塊設(shè)備的全局變量 230
7.2.3 塊設(shè)備的API 231
7.2.4 塊設(shè)備的實(shí)現(xiàn) 231
7.3 I/O請(qǐng)求 242
7.3.1 I/O請(qǐng)求的數(shù)據(jù)結(jié)構(gòu) 243
7.3.2 I/O請(qǐng)求的全局變量 250
7.3.3 I/O請(qǐng)求的API 250
7.3.4 I/O請(qǐng)求的實(shí)現(xiàn) 251
7.4 I/O調(diào)度 265
7.4.1 I/O調(diào)度的數(shù)據(jù)結(jié)構(gòu) 265
7.4.2 I/O調(diào)度的全局變量 267
7.4.3 I/O調(diào)度的API 267
7.4.4 I/O調(diào)度的實(shí)現(xiàn) 268
第 8章 虛擬文件系統(tǒng) 271
8.1 掛載、卸載文件系統(tǒng) 271
8.1.1 掛載、卸載文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu) 272
8.1.2 掛載、卸載文件系統(tǒng)的全局變量 277
8.1.3 掛載、卸載文件系統(tǒng)的API 278
8.1.4 掛載、卸載文件系統(tǒng)的實(shí)現(xiàn) 278
8.2 文件節(jié)點(diǎn)緩存 285
8.2.1 文件節(jié)點(diǎn)緩存的數(shù)據(jù)結(jié)構(gòu) 286
8.2.2 文件節(jié)點(diǎn)緩存的全局變量 288
8.2.3 文件節(jié)點(diǎn)緩存的API 289
8.2.4 文件節(jié)點(diǎn)緩存的實(shí)現(xiàn) 290
8.3 打開(kāi)、關(guān)閉文件 304
8.3.1 打開(kāi)、關(guān)閉文件的數(shù)據(jù)結(jié)構(gòu) 305
8.3.2 打開(kāi)、關(guān)閉文件的全局變量 308
8.3.3 打開(kāi)、關(guān)閉文件的API 309
8.3.4 打開(kāi)、關(guān)閉文件的實(shí)現(xiàn) 309
8.4 讀/寫(xiě)文件 319
8.4.1 讀/寫(xiě)文件的數(shù)據(jù)結(jié)構(gòu) 320
8.4.2 讀/寫(xiě)文件的全局變量 323
8.4.3 讀/寫(xiě)文件的API 323
8.4.4 讀/寫(xiě)文件的實(shí)現(xiàn) 323
8.5 其他功能 337
第 9章 雜項(xiàng)文件系統(tǒng) 338
9.1 文件系統(tǒng)的掛載 338
9.1.1 第一次加載根文件系統(tǒng) 338
9.1.2 第二次加載根文件系統(tǒng) 340
9.2 內(nèi)存文件系統(tǒng) 340
9.2.1 內(nèi)存文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu) 340
9.2.2 內(nèi)存文件系統(tǒng)的全局變量 340
9.2.3 內(nèi)存文件系統(tǒng)的API 341
9.2.4 內(nèi)存文件系統(tǒng)的實(shí)現(xiàn) 341
9.3 設(shè)備文件系統(tǒng) 349
9.3.1 設(shè)備文件系統(tǒng)的數(shù)據(jù)結(jié)構(gòu) 349
9.3.2 設(shè)備文件系統(tǒng)的全局變量 350
9.3.3 設(shè)備文件系統(tǒng)的API 351
9.3.4 設(shè)備文件系統(tǒng)的實(shí)現(xiàn) 351
第 10章 LEXT3文件系統(tǒng) 358
10.1 簡(jiǎn)介 358
10.1.1 超級(jí)塊 359
10.1.2 塊組描述符 359
10.1.3 塊位圖 360
10.1.4 文件節(jié)點(diǎn)位圖 360
10.1.5 文件節(jié)點(diǎn)表 360
10.1.6 文件節(jié)點(diǎn) 360
10.1.7 文件日志 362
10.2 LEXT3 363
10.2.1 LEXT3的數(shù)據(jù)結(jié)構(gòu) 363
10.2.2 LEXT3的全局變量 371
10.2.3 LEXT3的API 372
10.2.4 LEXT3的實(shí)現(xiàn) 373
10.3 文件系統(tǒng)日志 397
10.3.1 日志的數(shù)據(jù)結(jié)構(gòu) 397
10.3.2 日志的全局變量 405
10.3.3 日志的API 405
10.3.4 日志的實(shí)現(xiàn) 406
第 11章 雜項(xiàng) 438
11.1 klibc 438
11.2 網(wǎng)絡(luò)子系統(tǒng) 440
11.3 SIMPLE-KSHELL 440