rcu源碼

⑴ 嵌入式系統linux內核開發實戰指南的目錄

第1部分 嵌入式系統硬體開發
第1章 嵌入式系統概述 2
這一章對嵌入式系統的概念及其特點和應用作了概括介紹，筆者根據自己多年的經驗闡述了對嵌入式系統的理解，並對一些常見的嵌入式處理器的硬體數據進行了比較。
1.1 嵌入式系統概念 2
1.2 嵌入式處理器 3
1.3 嵌入式系統應用 4
1.4 嵌入式系統發展 4
1.5 一些嵌入式處理器的硬體特性比較 5
第2章 ARM處理器概述 16
為了使本書內容完整，從第2章到第7章中的內容大部分是筆者閱讀《ARM體系結構與編程》（詳情參見附錄中的參考文獻）的筆記和心得，把與嵌入式系統開發和Linux內核密切相關的硬體知識進行了概括和整理，本章主要介紹了ARM處理器的特點、ARM處理器的體系架構版本和ARM處理器系列。
2.1 ARM發展歷程 16
2.2 ARM處理器特點 17
2.3 ARM處理器應用 17
2.4 ARM體系架構 18
2.4.1 ARM體系架構版本 18
2.4.2 ARM體系架構變種（Variant） 20
2.4.3 ARM體系架構版本命名格式 22
2.5 ARM處理器 22
2.5.1 ARM7系列處理器 23
2.5.2 ARM9系列處理器 24
2.5.3 ARM9E系列處理器 24
2.5.4 ARM10E系列處理器 25
2.5.5 SecurCore系列處理器 25
2.5.6 StrongARM處理器 26
2.5.7 Xscale處理器 26
第3章 ARM指令及其定址方式 27
本章主要介紹了ARM處理器的指令和定址方式以及ARM匯編偽指令，這是做ARM處理器應用系統底層軟體開發必備的知識。
3.1 ARM處理器的程序狀態寄存器（PSR） 27
3.2 ARM指令的條件碼 28
3.3 ARM指令介紹 29
3.3.1 跳轉指令 29
3.3.2 數據處理指令 30
3.3.3 乘法指令 31
3.3.4 雜類算術指令 32
3.3.5 狀態寄存器訪問指令 32
3.3.6 Load/Store內存訪問指令 33
3.3.7 批量Load/Store內存訪問指令 34
3.3.8 LDREX和STREX指令 35
3.3.9 信號量操作指令 37
3.3.10 異常中斷產生指令 37
3.3.11 ARM協處理器指令 37
3.4 ARM指令定址方式 39
3.4.1 數據處理指令的操作數的定址方式 39
3.4.2 字及無符號位元組的Load/Store指令的定址方式 43
3.4.3 雜類Load/Store指令的定址方式 47
3.4.4 批量Load/Store指令的定址方式 49
3.4.5 協處理器Load/Store指令的定址方式 51
3.4.6 ARM指令的定址方式總結 52
3.5 ARM匯編偽操作（Directive） 53
3.5.1 符號定義偽操作 54
3.5.2 數據定義偽操作 54
3.5.3 匯編控制偽操作 56
3.5.4 棧中數據幀描述偽操作 57
3.5.5 信息報告偽操作 57
3.5.6 其他偽操作 58
3.6 ARM匯編偽指令 59
3.7 Thumb指令介紹 60
第4章 ARM處理器內存管理單元（MMU） 61
本章主要介紹了ARM處理器內存管理單元（MMU）的工作原理，Linux內存管理功能是通過處理器硬體MMU實現的，在沒有MMU的處理器系統中，Linux只能工作在物理地址模式，沒有虛擬（線性）地址空間的概念。
4.1 ARM處理器中CP15協處理器的寄存器 61
4.1.1 訪問CP15寄存器的指令 61
4.1.2 CP15寄存器介紹 62
4.2 MMU簡介 70
4.3 系統訪問存儲空間的過程 71
4.3.1 使能MMU時的情況 71
4.3.2 禁止MMU時的情況 71
4.3.3 使能/禁止MMU時應注意的問題 72
4.4 ARM處理器地址變換過程 72
4.4.1 MMU的一級映射描述符 73
4.4.2 MMU的二級映射描述符 74
4.4.3 基於段的地址變換過程 75
4.4.4 粗粒度大頁地址變換過程 75
4.4.5 粗粒度小頁地址變換過程 76
4.4.6 細粒度大頁地址變換過程 76
4.4.7 細粒度小頁地址變換過程 77
4.4.8 細粒度極小頁地址變換過程 77
4.5 ARM存儲空間訪問許可權控制 78
4.6 TLB操作 79
4.6.1 使TLB內容無效 79
4.6.2 鎖定TLB內容 79
4.6.3 解除TLB中被鎖定的地址變換條目 80
4.7 存儲訪問失效 80
4.7.1 MMU失效（MMU Fault） 80
4.7.2 外部存儲訪問失效（External Abort） 81
第5章 ARM處理器的Cache和Write Buffer 82
本章主要介紹了ARM處理器高速緩存（Cache）和寫緩存（Write Buffer）的工作原理，使讀者了解如何提高處理器的性能。
5.1 Cache和Write Buffer一般性介紹 82
5.1.1 Cache工作原理 82
5.1.2 地址映像方式 83
5.1.3 Cache寫入方式原理簡介 84
5.1.4 關於Write-through和Write-back 85
5.1.5 Cache替換策略 86
5.1.6 使用Cache的必要性 87
5.1.7 使用Cache的可行性 87
5.2 ARM處理器中的Cache和Write Buffer 88
5.2.1 基本概念 88
5.2.2 Cache工作原理 88
5.2.3 Cache地址映射和變換方法 89
5.2.4 Cache分類 90
5.2.5 Cache替換演算法 91
5.2.6 Cache內容鎖定 91
5.2.7 MMU映射描述符中B位和C位的含義 92
5.2.8 Cache和Writer Buffer編程介面 93
5.3 ARM處理器的快速上下文切換技術 94
5.3.1 FCSE概述 94
5.3.2 FCSE原理 94
5.3.3 FCSE編程介面 95
第6章 ARM處理器存儲訪問一致性問題 97
本章介紹了在支持MMU、Cache和DMA的系統中可能出現的存儲訪問一致性問題，以及Linux中解決類似問題的方法。
6.1 存儲訪問一致性問題介紹 97
6.1.1 地址映射關系變化造成的數據不一致性 97
6.1.2 指令cache的數據不一致性問題 98
6.1.3 DMA造成的數據不一致問題 99
6.1.4 指令預取和自修改代碼 99
6.2 Linux中解決存儲訪問一致性問題的方法 99
第7章 ARM處理器工作模式與異常中斷處理 101
本章主要介紹了ARM處理器的工作模式和異常中斷處理過程，這是ARM處理器系統啟動程序編寫者或Bootloader開發人員的必備知識。
7.1 ARM處理器工作模式 101
7.2 ARM處理器異常中斷向量表和優先順序 103
7.3 ARM處理器異常中斷處理 104
7.3.1 進入異常中斷處理 104
7.3.2 退出異常中斷處理 105
7.4 ARM處理器的中斷（IRQ或FIQ） 109
第8章 ARM處理器啟動過程 110
本章根據筆者的開發經驗介紹了ARM處理器系統的啟動過程以及編寫ARM處理器系統啟動程序需要注意的事項。
8.1 ARM處理器上電/復位操作 110
8.2 ARM處理器系統初始化過程 111
8.3 ARM處理器系統初始化編程注意事項 111
第9章 嵌入式系統設計與調試 113
本章根據筆者10多年的開發經驗介紹了嵌入式系統的設計流程和調試方法，列舉了大量筆者工作中碰到的實際案例。本章內容對於嵌入式系統硬體開發和調試有較高的參考、指導價值。
9.1 嵌入式系統設計流程 113
9.2 嵌入式系統硬體原理設計與審核 114
9.3 硬體設計工具軟體 117
9.4 嵌入式系統調試模擬工具 117
9.5 嵌入式系統調試診斷方法 118
第10章 自製簡易JTAG下載燒寫工具 123
本章根據筆者自己製作簡易JTAG線纜的經驗，介紹了簡易JTAG線纜的硬體原理和軟體流程，這是初學者必備的最廉價的工具，必須掌握。
10.1 JTAG簡介 123
10.1.1 一些基本概念 124
10.1.2 JTAG介面信號 124
10.1.3 TAP控制器的狀態機 125
10.1.4 JTAG介面指令集 129
10.2 簡易JTAG線纜原理 130
10.2.1 PC並口定義 130
10.2.2 PC並口的寄存器 131
10.2.3 簡易JTAG線纜原理圖 133
10.2.4 簡易JTAG線纜燒寫連接圖（見圖10-5） 134
10.3 簡易JTAG燒寫代碼分析 135
10.3.1 簡易JTAG燒寫程序（flashp）使用說明 135
10.3.2 flash與CPU連接及flash屬性描述文件 136
10.3.3 簡易JTAG燒寫程序的執行邏輯和流程 138
第2部分 Linux內核開發初步
第11章 Bootloader 142
本章根據筆者的工作經驗介紹了流行的幾種Bootloader、Bootloader應該具備的基本功能以及Bootloader的裁剪與移植。
11.1 Bootloader的任務和作用 142
11.2 各種各樣的Bootloader 143
11.3 Bootloader編譯環境 144
11.4 Bootloader的移植與裁減 145
11.5 編譯Bootloader 145
11.6 燒寫Bootloader 146
11.7 Bootloader使用舉例 148
11.8 Bootloader修改舉例 149
第12章 創建嵌入式Linux開發環境 151
本章介紹了如何創建嵌入式系統Linux內核交叉開發環境，本章和後續3章的內容是嵌入式系統Linux內核開發的基礎，必須掌握。
12.1 安裝Linux host 151
12.2 在虛擬機中安裝Linux host 152
12.3 安裝Linux交叉編譯環境 157
12.4 在主機上設置TFTP Server 160
12.5 在主機上設置DHCP Server 161
12.6 在主機上設置Telnet server 161
12.7 在開發過程中使用NFS 162
12.8 設置超級終端 163
第13章 編譯Linux內核 166
本章介紹了Linux內核的配置和編譯方法。
13.1 獲取Linux內核源代碼 166
13.2 Linux內核目錄結構 166
13.3 配置Linux內核 167
13.4 編譯Linux內核 168
第14章 創建Linux根文件系統 170
本章介紹了Linux的根文件系統的結構以及創建根文件系統的方法。
14.1 根文件系統概述 170
14.2 根文件系統目錄結構 171
14.3 獲取根文件系統組件源代碼 171
14.4 編譯根文件系統源代碼 171
14.5 創建一個32MB的RAMDISK根文件系統 173
14.6 在根文件系統中添加驅動模塊或者應用程序 173
第15章 固化Linux內核和根文件系統 174
本章介紹了固化（燒寫）Linux內核和根文件系統的方法。
第16章 關於Clinux 176
本章簡要介紹了Clinux與標准Linux的區別。
16.1 Clinux簡介 176
16.2 Clinux源代碼目錄結構 177
16.3 Clinux與標准Linux的區別 178
16.4 編譯Clinux 179
第3部分 Linux 2.6內核原理
第17章 Linux 2.6.10@ARM啟動過程 182
本章以start_kernel()和init()函數中調用到的函數說明的方式，介紹了從Linux匯編代碼入口到init內核進程最後調用用戶空間init命令的Linux整個啟動過程。本章內容是筆者第一次閱讀Linux內核源代碼時對這些函數的注釋，僅供讀者了解start_kernel()和init()函數中調用到的每個函數的大致功能時使用。
17.1 Linux 2.6.10中與ARM處理器平台硬體相關的結構和全局變數 182
17.1.1 相關數據結構 182
17.1.2 相關全局變數 187
17.2 Linux匯編代碼入口 189
17.3 Linux匯編入口處CPU的狀態 189
17.4 start_kernel()函數之前的匯編代碼執行過程 190
17.5 start_kernel()函數中調用的函數介紹 192
17.5.1 lock_kernel()函數 192
17.5.2 page_address_init()函數 192
17.5.3 printk(linux_banner) 193
17.5.4 setup_arch(&command_line)函數 193
17.5.5 setup_per_cpu_areas()函數 198
17.5.6 smp_prepare_boot_cpu()函數 199
17.5.7 sched_init()函數 199
17.5.8 build_all_zonelists()函數 200
17.5.9 page_alloc_init()函數 200
17.5.10 printk(Kernel command line: %s , saved_command_line) 201
17.5.11 parse_early_param()函數 201
17.5.12 parse_args()函數 201
17.5.13 sort_main_extable()函數 202
17.5.14 trap_init()函數 202
17.5.15 rcu_init()函數 202
17.5.16 init_IRQ()函數 203
17.5.17 pidhash_init()函數 203
17.5.18 init_timers()函數 203
17.5.19 softirq_init()函數 204
17.5.20 time_init()函數 204
17.5.21 console_init()函數 205
17.5.22 profile_init()函數 206
17.5.23 local_irq_enable()函數 207
17.5.24 vfs_caches_init_early()函數 207
17.5.25 mem_init()函數 208
17.5.26 kmem_cache_init()函數 210
17.5.27 numa_policy_init()函數 225
17.5.28 calibrate_delay()函數 227
17.5.29 pidmap_init()函數 228
17.5.30 pgtable_cache_init()函數 229
17.5.31 prio_tree_init()函數 229
17.5.32 anon_vma_init()函數 229
17.5.33 fork_init(num_physpages)函數 229
17.5.34 proc_caches_init()函數 230
17.5.35 buffer_init()函數 231
17.5.36 unnamed_dev_init()函數 231
17.5.37 security_init()函數 231
17.5.38 vfs_caches_init(num_physpages)函數 232
17.5.39 radix_tree_init()函數 237
17.5.40 signals_init()函數 237
17.5.41 page_writeback_init()函數 237
17.5.42 proc_root_init()函數 238
17.5.43 check_bugs()函數 240
17.5.44 acpi_early_init()函數 244
17.5.45 rest_init()函數 244
17.6 init()進程執行過程 265
17.6.1 smp_prepare_cpus(max_cpus)函數 265
17.6.2 do_pre_smp_initcalls()函數 265
17.6.3 fixup_cpu_present_map()函數 267
17.6.4 smp_init()函數 267
17.6.5 sched_init_smp()函數 268
17.6.6 populate_rootfs()函數 268
17.6.7 do_basic_setup()函數 283
17.6.8 sys_access()函數 292
17.6.9 free_initmem()函數 301
17.6.10 unlock_kernel()函數 301
17.6.11 numa_default_policy()函數 302
17.6.12 sys_p()函數 302
17.6.13 execve()函數 302
第18章 Linux內存管理 305
從本章開始，筆者將帶領讀者走進神秘的Linux內核世界。筆者在閱讀內核源代碼以及兩本相關參考書（見參考文獻）的基礎上，以自己的理解和語言總結概括了Linux內核每個組件的原理。筆者對與每個內核組件相關的關鍵數據結構和全局變數作了盡量詳盡的說明，並且對核心函數進行了詳細注釋，在向讀者灌輸理論知識的同時引導讀者自己去閱讀、分析Linux內核源代碼。本章講解了Linux內核第一大核心組件「內存管理」的原理和實現內幕。
18.1 Linux內存管理概述 305
18.1.1 Linux內存管理的一些基本概念 305
18.1.2 內存管理相關數據結構 309
18.1.3 內存管理相關宏和全局變數 330
18.1.4 Linux內存管理的任務 341
18.1.5 Linux中的物理和虛擬存儲空間布局 341
18.2 為虛擬（線性地址）存儲空間建立頁表 345
18.3 設置存儲空間的訪問控制屬性 348
18.4 Linux中的內存分配和釋放 350
18.4.1 在系統啟動初期申請內存 350
18.4.2 系統啟動之後的內存分配與釋放 360
第19章 Linux進程管理 480
本章講解了Linux內核第二大核心組件「進程管理」的原理和實現內幕。
19.1 進程管理概述 480
19.1.1 進程相關概念 480
19.1.2 進程分類 481
19.1.3 0號進程 481
19.1.4 1號進程 481
19.1.5 其他一些內核線程 482
19.1.6 進程描述符（struct task_struct） 482
19.1.7 進程狀態 482
19.1.8 進程標識符（PID） 483
19.1.9 current宏定義 484
19.1.10 進程鏈表 484
19.1.11 PID hash表和鏈表 485
19.1.12 硬體上下文（Hardware Context） 485
19.1.13 進程資源限制 485
19.1.14 進程管理相關數據結構 486
19.1.15 進程管理相關宏定義 502
19.1.16 進程管理相關全局變數 514
19.2 進程管理相關初始化 520
19.3 進程創建與刪除 529
19.4 進程調度 551
19.4.1 進程類型 553
19.4.2 進程調度類型 554
19.4.3 基本時間片計算方法 555
19.4.4 動態優先順序演算法 556
19.4.5 互動式進程 556
19.4.6 普通進程調度 557
19.4.7 實時進程調度 557
19.4.8 進程調度函數分析 558
19.5 進程切換 576
19.6 用戶態進程間通信 581
19.6.1 信號（Signal） 581
19.6.2 管道（pipe）和FIFO（命名管道） 627
19.6.3 進程間通信原語（System V IPC） 641
第20章 Linux文件管理 651
本章講解了Linux內核第三大核心組件「文件系統」的原理和實現內幕。
20.1 文件系統概述 651
20.1.1 Linux文件管理相關概念 652
20.1.2 Linux文件管理相關數據結構 657
20.1.3 Linux文件管理相關宏定義 682
20.1.4 Linux文件管理相關全局變數 691
20.2 文件管理相關初始化 699
20.3 文件系統類型注冊 711
20.4 掛接文件系統 712
20.5 文件系統類型超級塊讀取 730
20.5.1 get_sb_single()通用超級塊讀取函數 731
20.5.2 get_sb_nodev()通用超級塊讀取函數 737
20.5.3 get_sb_bdev()通用超級塊讀取函數 738
20.5.4 get_sb_pseudo()通用超級塊讀取函數 740
20.6 路徑名查找 747
20.7 訪問文件操作 759
20.7.1 打開文件 759
20.7.2 關閉文件 766
20.7.3 讀文件 768
20.7.4 寫文件 785
20.8 非同步I/O系統調用 792
20.9 Linux特殊文件系統 792
20.9.1 rootfs文件系統 793
20.9.2 sysfs文件系統 797
20.9.3 devfs設備文件系統 800
20.9.4 bdev塊設備文件系統 803
20.9.5 ramfs文件系統 804
20.9.6 proc文件系統 804
20.10 磁碟文件系統 813
20.10.1 ext2文件系統相關數據結構 813
20.10.2 ext2文件系統磁碟分區格式 819
20.10.3 ext2文件系統的各種文件 820
20.10.4 創建ext2文件系統 821
20.10.5 ext2文件系統的操作方法 822
20.11 關於initramfs 824
20.11.1 initramfs概述 824
20.11.2 initramfs與initrd的區別 824
20.11.3 initramfs相關全局變數 825
20.11.4 initramfs被編譯鏈接的位置 825
20.11.5 initramfs文件的生成過程 825
20.11.6 initramfs二進制文件格式說明（cpio格式） 828
20.11.7 initramfs二進制文件和列表文件對照示例 829
20.11.8 initramfs利弊 830
20.12 關於initrd 830
20.12.1 initrd概述 830
20.12.2 initrd相關全局變數 831
20.13 關於gzip壓縮文件 832
第21章 Linux模塊設計 834
本章講解了Linux內核模塊程序與應用程序的區別以及如何編寫和載入Linux內核模塊程序。
21.1 Linux模塊設計概述 834
21.2 Linux的內核空間和用戶空間 834
21.3 內核模塊與應用程序的區別 835
21.4 編譯模塊 837
21.5 裝載和卸載模塊 837
21.6 模塊層疊 838
21.7 模塊版本依賴 839
21.8 模塊編程示例 839
第22章 Linux系統異常中斷管理 841
本章講解了Linux內核如何管理系統異常中斷以及Linux系統調用的實現內幕。
22.1 Linux異常中斷處理 841
22.2 指令預取和數據訪問中止異常中斷處理 849
22.2.1 指令預取中止異常中斷處理 850
22.2.2 數據訪問中止異常中斷處理 858
22.3 Linux中斷處理 863
22.3.1 內核模式下的中斷處理 863
22.3.2 用戶模式下的中斷處理 867
22.4 從中斷返回 868
22.5 Linux中斷管理 869
22.5.1 Linux中斷管理相關數據結構與全局變數 870
22.5.2 Linux中斷管理初始化 872
22.5.3 安裝和卸載中斷處理程序 874
22.5.4 使能和禁止中斷 878
22.6 Linux系統調用 880
22.6.1 Linux系統調用內核實現過程 880
22.6.2 從系統調用返回 889
22.6.3 Linux系統調用用戶程序介面函數 890
22.6.4 Linux系統調用用戶介面函數與內核實現函數之間參數傳遞 899
第23章 Linux軟中斷和工作隊列 901
本章講解了Linux內核中的兩種延遲處理機制「軟中斷」和「工作隊列」的原理和實現。
23.1 概述 901
23.2 Linux軟中斷 902
23.2.1 軟中斷相關數據結構和全局變數 903
23.2.2 軟中斷初始化 904
23.2.3 軟中斷的核心操作函數do_softirq() 908
23.2.4 軟中斷看護進程執行函數ksoftirqd() 912
23.2.5 如何使用軟中斷 913
23.3 Linux工作隊列 918
23.3.1 Linux工作隊列相關數據結構和全局變數 918
23.3.2 Linux工作隊列初始化 921
23.3.3 將工作加入到工作隊列中 924
23.3.4 工作者進程執行函數worker_thread() 928
23.3.5 使用Linux工作隊列 931
第24章 Linux並發與競態 933
本章講解了Linux內核同步機制，包括幾種鎖定技術以及免鎖演算法。
24.1 並發與競態概述 933
24.1.1 Linux中的並發源 934
24.1.2 競態可能導致的後果 934
24.1.3 避免競態的規則 934
24.2 消除競態的「鎖定」技術 935
24.2.1 信號量（semphore）和互斥體（mutual exclusion） 935
24.2.2 讀寫信號量（rw_semaphore） 938
24.2.3 完成量（completion） 941
24.2.4 自旋鎖（spinlock_t） 942
24.2.5 讀寫自旋鎖（rwlock_t） 946
24.2.6 使用「鎖定」技術的注意事項 949
24.3 消除競態的非「鎖定」方法 949
24.3.1 免鎖演算法 949
24.3.2 原子操作 950
24.3.3 位操作 951
24.3.4 順序鎖 952
24.3.5 讀-復制-更新（Read-Copy-Update，RCU） 954
第25章 Linux設備驅動程序 958
本章講解了Linux內核第四大核心組件「設備驅動」的原理和實現內幕。同時還總結歸納了編寫各種設備驅動程序的方法和步驟。
25.1 設備驅動程序概述 958
25.1.1 設備驅動程序組成部分 959
25.1.2 設備號 959
25.1.3 設備文件 960
25.1.4 編寫設備驅動程序的關鍵 961
25.2 字元設備驅動程序 961
25.2.1 字元設備相關數據結構 961
25.2.2 字元設備相關全局變數 963
25.2.3 字元設備驅動程序全局初始化 963
25.2.4 為字元設備分配設備號 964
25.2.5 注冊字元設備驅動程序 968
25.2.6 字元設備的操作方法 971
25.2.7 用戶對字元設備驅動程序的調用過程 972
25.2.8 如何編寫字元設備驅動程序 974
25.2.9 關於TTY設備驅動程序 974
25.2.10 控制台設備驅動程序 975
25.3 塊設備驅動程序 986
25.3.1 塊設備相關數據結構 986
25.3.2 塊設備相關宏定義 997
25.3.3 塊設備相關全局變數 999
25.3.4 塊設備驅動程序全局初始化 1004
25.3.5 為塊設備分配主設備號 1006
25.3.6 注冊塊設備驅動程序 1009
25.3.7 塊設備驅動程序的操作方法 1017
25.3.8 調用塊設備驅動程序過程 1017
25.3.9 I/O調度 1031
25.3.10 如何編寫塊設備驅動程序 1032
25.4 網路設備驅動程序 1033
25.4.1 網路設備驅動程序概述 1033
25.4.2 網路設備相關數據結構 1034
25.4.3 網路設備相關宏定義 1044
25.4.4 網路設備相關全局變數 1045
25.4.5 創建net_device結構 1046
25.4.6 注冊網路設備 1048
25.4.7 網路設備的操作方法 1050
25.4.8 網路設備中斷服務程序 1051
25.4.9 如何編寫網路設備驅動程序 1051
25.5 PCI設備驅動程序 1052
25.5.1 PCI介面定義 1053
25.5.2 PCI設備的三個地址空間 1057
25.5.3 PCI匯流排仲裁 1058
25.5.4 PCI設備編號 1059
25.5.5 如何訪問PCI配置空間 1059
25.5.6 如何配置PCI設備 1061
25.5.7 PCI驅動程序相關數據結構 1062
25.5.8 PCI驅動程序相關宏定義 1068
25.5.9 PCI驅動程序相關全局變數 1068
25.5.10 Bootloader和內核做的事 1069
25.5.11 PCI驅動程序注冊 1069
25.5.12 PCI驅動程序介面函數 1071
25.5.13 如何編寫PCI驅動程序 1072
第4部分 Linux內核開發高級指南
第26章 Linux系統參數設置 1076
從本章開始的後續章節主要講解了比較高級或者平時較少關注的Linux內核方面的知識，本章講解了Linux中的4種系統參數格式和設置方法。
26.1 旗語系統參數（tag） 1076
26.1.1 與旗語系統參數相關數據結構和全局變數 1076
26.1.2 旗語系統參數說明 1082
26.1.3 旗語系統參數設置方法 1084
26.2 前期命令行設置的系統參數 1084
26.2.1 與前期命令行系統參數相關數據結構和全局變數 1084
26.2.2 前期命令行設置的系統參數說明 1085
26.2.3 前期命令行系統參數設置方法 1086
26.2.4 如何添加自己的前期命令行設置的系統參數 1087
26.3 老式命令行系統參數 1087
26.3.1 與老式命令行系統參數相關數據結構和全局變數 1087
26.3.2 老式命令行設置的系統參數說明 1088
26.3.3 老式命令行設置的系統參數設置方法 1089
26.3.4 如何添加自己的老式命令行設置的系統參數 1089
26.4 命令行系統參數 1089
26.4.1 與命令行系統參數相關數據結構和全局變數 1089
26.4.2 命令行設置的系統參數說明 1090
26.4.3 命令行設置的系統參數設置方法 1090
第27章 Linux內核調試 1091
本章介紹了Linux內核的調試方法。
27.1 打開Linux內核及其各模塊自帶的調試開關 1091
27.2 內核剖析（Profiling） 1093
27.3 通過列印調試（printk） 1095
27.3.1 關於printk() 1095
27.3.2 內核信息級別 1096
27.3.3 列印速度限制 1097
27.3.4 控制台重定向 1098
27.4 使用proc文件系統調試 1098
27.5 oops消息 1098
27.6 通過跟蹤命令strace調試 1099
27.7 使用gdb、kdb、kgdb調試 1099
第28章 Linux內核移植 1101
本章介紹了Linux內核的移植方法。
第29章 Linux內核優化 1104
本章介紹了Linux內核的優化方法。
29.1 編譯優化 1104
29.2 根據CPU特性進行優化 1105
29.3 對內核進行裁減 1105
29.4 優化系統內存配置 1106
29.5 優化系統啟動過程以縮減系統啟動時間 1106
29.6 內存映射優化 1107
29.7 工具軟體輔助優化 1107
第30章 Linux定時器 1109
本章介紹了Linux內核的軟體定時器。
30.1 定時器相關數據結構 1109
30.2 定時器相關宏定義 1111
30.3 定時器相關全局變數 1112
30.4 定時器和時鍾初始化 1113
30.5 獲取系統時間 1114
30.6 延遲函數 1115
30.7 與定時器相關系統調用 1115
30.8 使用定時器方法 1116
第31章 雜項 1117
本章介紹了PER_CPU變數以及Linux中的數據類型定義。
31.1 per_cpu變數 1117
31.2 Linux中的數據類型定義 1118
第32章 編譯鏈接文件說明 1119
本章注釋了ARM處理器系統中Linux內核的鏈接文件，以幫助讀者了解編譯出來的Linux內核各區段在內存中的存放位置。
參考文獻 1125

⑵ 面試必問的epoll技術，從內核源碼出發徹底搞懂epoll

epoll是linux中IO多路復用的一種機制，I/O多路復用就是通過一種機制，一個進程可以監視多個描述符，一旦某個描述符就緒（一般是讀就緒或者寫就緒），能夠通知程序進行相應的讀寫操作。當然linux中IO多路復用不僅僅是epoll，其他多路復用機制還有select、poll，但是接下來介紹epoll的內核實現。

events可以是以下幾個宏的集合：

epoll相比select/poll的優勢 ：

epoll相關的內核代碼在fs/eventpoll.c文件中，下面分別分析epoll_create、epoll_ctl和epoll_wait三個函數在內核中的實現，分析所用linux內核源碼為4.1.2版本。

epoll_create用於創建一個epoll的句柄，其在內核的系統實現如下：

sys_epoll_create:

可見，我們在調用epoll_create時，傳入的size參數，僅僅是用來判斷是否小於等於0，之後再也沒有其他用處。
整個函數就3行代碼，真正的工作還是放在sys_epoll_create1函數中。

sys_epoll_create -> sys_epoll_create1:

sys_epoll_create1 函數流程如下：

sys_epoll_create -> sys_epoll_create1 -> ep_alloc:

sys_epoll_create -> sys_epoll_create1 -> ep_alloc -> get_unused_fd_flags:

linux內核中，current是個宏，返回的是一個task_struct結構（我們稱之為進程描述符）的變數，表示的是當前進程，進程打開的文件資源保存在進程描述符的files成員裡面，所以current->files返回的當前進程打開的文件資源。rlimit(RLIMIT_NOFILE) 函數獲取的是當前進程可以打開的最大文件描述符數，這個值可以設置，默認是1024。

相關視頻推薦：

支撐億級io的底層基石 epoll實戰揭秘

網路原理tcp/udp，網路編程epoll/reactor，面試中正經「八股文」

學習地址：C/C++Linux伺服器開發/後台架構師【零聲教育】-學習視頻教程-騰訊課堂

需要更多C/C++ Linux伺服器架構師學習資料加群 812855908 獲取（資料包括C/C++，Linux，golang技術，Nginx，ZeroMQ，MySQL，Redis，fastdfs，MongoDB，ZK，流媒體，CDN，P2P，K8S，Docker，TCP/IP，協程，DPDK，ffmpeg等），免費分享

__alloc_fd的工作是為進程在[start,end)之間(備註：這里start為0， end為進程可以打開的最大文件描述符數)分配一個可用的文件描述符,這里就不繼續深入下去了，代碼如下：

sys_epoll_create -> sys_epoll_create1 -> ep_alloc -> get_unused_fd_flags -> __alloc_fd:

然後，epoll_create1會調用anon_inode_getfile，創建一個file結構，如下：

sys_epoll_create -> sys_epoll_create1 -> anon_inode_getfile:

anon_inode_getfile函數中首先會alloc一個file結構和一個dentry結構，然後將該file結構與一個匿名inode節點anon_inode_inode掛鉤在一起，這里要注意的是，在調用anon_inode_getfile函數申請file結構時，傳入了前面申請的eventpoll結構的ep變數，申請的file->private_data會指向這個ep變數，同時，在anon_inode_getfile函數返回來後，ep->file會指向該函數申請的file結構變數。

簡要說一下file/dentry/inode，當進程打開一個文件時，內核就會為該進程分配一個file結構，表示打開的文件在進程的上下文，然後應用程序會通過一個int類型的文件描述符來訪問這個結構，實際上內核的進程裡面維護一個file結構的數組，而文件描述符就是相應的file結構在數組中的下標。

dentry結構（稱之為「目錄項」）記錄著文件的各種屬性，比如文件名、訪問許可權等，每個文件都只有一個dentry結構，然後一個進程可以多次打開一個文件，多個進程也可以打開同一個文件，這些情況，內核都會申請多個file結構，建立多個文件上下文。但是，對同一個文件來說，無論打開多少次，內核只會為該文件分配一個dentry。所以，file結構與dentry結構的關系是多對一的。

同時，每個文件除了有一個dentry目錄項結構外，還有一個索引節點inode結構，裡面記錄文件在存儲介質上的位置和分布等信息，每個文件在內核中只分配一個inode。 dentry與inode描述的目標是不同的，一個文件可能會有好幾個文件名（比如鏈接文件），通過不同文件名訪問同一個文件的許可權也可能不同。dentry文件所代表的是邏輯意義上的文件，記錄的是其邏輯上的屬性，而inode結構所代表的是其物理意義上的文件，記錄的是其物理上的屬性。dentry與inode結構的關系是多對一的關系。

sys_epoll_create -> sys_epoll_create1 -> fd_install:

總結epoll_create函數所做的事：調用epoll_create後，在內核中分配一個eventpoll結構和代表epoll文件的file結構，並且將這兩個結構關聯在一塊，同時，返回一個也與file結構相關聯的epoll文件描述符fd。當應用程序操作epoll時，需要傳入一個epoll文件描述符fd，內核根據這個fd，找到epoll的file結構，然後通過file，獲取之前epoll_create申請eventpoll結構變數，epoll相關的重要信息都存儲在這個結構裡面。接下來，所有epoll介面函數的操作，都是在eventpoll結構變數上進行的。

所以，epoll_create的作用就是為進程在內核中建立一個從epoll文件描述符到eventpoll結構變數的通道。

epoll_ctl介面的作用是添加/修改/刪除文件的監聽事件，內核代碼如下：

sys_epoll_ctl:

根據前面對epoll_ctl介面的介紹，op是對epoll操作的動作（添加/修改/刪除事件），ep_op_has_event(op)判斷是否不是刪除操作，如果op != EPOLL_CTL_DEL為true，則需要調用_from_user函數將用戶空間傳過來的event事件拷貝到內核的epds變數中。因為，只有刪除操作，內核不需要使用進程傳入的event事件。

接著連續調用兩次fdget分別獲取epoll文件和被監聽文件（以下稱為目標文件）的file結構變數（備註：該函數返回fd結構變數，fd結構包含file結構）。

接下來就是對參數的一些檢查，出現如下情況，就可以認為傳入的參數有問題，直接返回出錯：

當然下面還有一些關於操作動作如果是添加操作的判斷，這里不做解釋，比較簡單，自行閱讀。

在ep裡面，維護著一個紅黑樹，每次添加註冊事件時，都會申請一個epitem結構的變數表示事件的監聽項，然後插入ep的紅黑樹裡面。在epoll_ctl裡面，會調用ep_find函數從ep的紅黑樹裡面查找目標文件表示的監聽項，返回的監聽項可能為空。

接下來switch這塊區域的代碼就是整個epoll_ctl函數的核心，對op進行switch出來的有添加(EPOLL_CTL_ADD)、刪除(EPOLL_CTL_DEL)和修改(EPOLL_CTL_MOD)三種情況，這里我以添加為例講解，其他兩種情況類似，知道了如何添加監聽事件，其他刪除和修改監聽事件都可以舉一反三。

為目標文件添加監控事件時，首先要保證當前ep裡面還沒有對該目標文件進行監聽，如果存在(epi不為空)，就返回-EEXIST錯誤。否則說明參數正常，然後先默認設置對目標文件的POLLERR和POLLHUP監聽事件，然後調用ep_insert函數，將對目標文件的監聽事件插入到ep維護的紅黑樹裡面：

sys_epoll_ctl -> ep_insert:

前面說過，對目標文件的監聽是由一個epitem結構的監聽項變數維護的，所以在ep_insert函數裡面，首先調用kmem_cache_alloc函數，從slab分配器裡面分配一個epitem結構監聽項，然後對該結構進行初始化，這里也沒有什麼好說的。我們接下來看ep_item_poll這個函數調用：

sys_epoll_ctl -> ep_insert -> ep_item_poll:

ep_item_poll函數裡面，調用目標文件的poll函數，這個函數針對不同的目標文件而指向不同的函數，如果目標文件為套接字的話，這個poll就指向sock_poll，而如果目標文件為tcp套接字來說，這個poll就是tcp_poll函數。雖然poll指向的函數可能會不同，但是其作用都是一樣的，就是獲取目標文件當前產生的事件位，並且將監聽項綁定到目標文件的poll鉤子裡面（最重要的是注冊ep_ptable_queue_proc這個poll callback回調函數），這步操作完成後，以後目標文件產生事件就會調用ep_ptable_queue_proc回調函數。

接下來，調用list_add_tail_rcu將當前監聽項添加到目標文件的f_ep_links鏈表裡面，該鏈表是目標文件的epoll鉤子鏈表，所有對該目標文件進行監聽的監聽項都會加入到該鏈表裡面。

然後就是調用ep_rbtree_insert，將epi監聽項添加到ep維護的紅黑樹裡面,這里不做解釋，代碼如下：

sys_epoll_ctl -> ep_insert -> ep_rbtree_insert:

前面提到，ep_insert有調用ep_item_poll去獲取目標文件產生的事件位，在調用epoll_ctl前這段時間，可能會產生相關進程需要監聽的事件，如果有監聽的事件產生，(revents & event->events 為 true)，並且目標文件相關的監聽項沒有鏈接到ep的准備鏈表rdlist裡面的話，就將該監聽項添加到ep的rdlist准備鏈表裡面，rdlist鏈接的是該epoll描述符監聽的所有已經就緒的目標文件的監聽項。並且，如果有任務在等待產生事件時，就調用wake_up_locked函數喚醒所有正在等待的任務，處理相應的事件。當進程調用epoll_wait時，該進程就出現在ep的wq等待隊列裡面。接下來講解epoll_wait函數。

總結epoll_ctl函數：該函數根據監聽的事件，為目標文件申請一個監聽項，並將該監聽項掛人到eventpoll結構的紅黑樹裡面。

epoll_wait等待事件的產生，內核代碼如下：

sys_epoll_wait:

首先是對進程傳進來的一些參數的檢查：

參數全部檢查合格後，接下來就調用ep_poll函數進行真正的處理：

sys_epoll_wait -> ep_poll:

ep_poll中首先是對等待時間的處理，timeout超時時間以ms為單位，timeout大於0，說明等待timeout時間後超時，如果timeout等於0，函數不阻塞，直接返回，小於0的情況，是永久阻塞，直到有事件產生才返回。

當沒有事件產生時（(!ep_events_available(ep))為true）,調用__add_wait_queue_exclusive函數將當前進程加入到ep->wq等待隊列裡面，然後在一個無限for循環裡面，首先調用set_current_state(TASK_INTERRUPTIBLE)，將當前進程設置為可中斷的睡眠狀態，然後當前進程就讓出cpu，進入睡眠，直到有其他進程調用wake_up或者有中斷信號進來喚醒本進程，它才會去執行接下來的代碼。

如果進程被喚醒後，首先檢查是否有事件產生，或者是否出現超時還是被其他信號喚醒的。如果出現這些情況，就跳出循環，將當前進程從ep->wp的等待隊列裡面移除，並且將當前進程設置為TASK_RUNNING就緒狀態。

如果真的有事件產生，就調用ep_send_events函數，將events事件轉移到用戶空間裡面。

sys_epoll_wait -> ep_poll -> ep_send_events:

ep_send_events沒有什麼工作，真正的工作是在ep_scan_ready_list函數裡面：

sys_epoll_wait -> ep_poll -> ep_send_events -> ep_scan_ready_list:

ep_scan_ready_list首先將ep就緒鏈表裡面的數據鏈接到一個全局的txlist裡面，然後清空ep的就緒鏈表，同時還將ep的ovflist鏈表設置為NULL，ovflist是用單鏈表，是一個接受就緒事件的備份鏈表，當內核進程將事件從內核拷貝到用戶空間時，這段時間目標文件可能會產生新的事件，這個時候，就需要將新的時間鏈入到ovlist裡面。

僅接著，調用sproc回調函數(這里將調用ep_send_events_proc函數)將事件數據從內核拷貝到用戶空間。

sys_epoll_wait -> ep_poll -> ep_send_events -> ep_scan_ready_list -> ep_send_events_proc:

ep_send_events_proc回調函數循環獲取監聽項的事件數據，對每個監聽項，調用ep_item_poll獲取監聽到的目標文件的事件，如果獲取到事件，就調用__put_user函數將數據拷貝到用戶空間。

回到ep_scan_ready_list函數，上面說到，在sproc回調函數執行期間，目標文件可能會產生新的事件鏈入ovlist鏈表裡面，所以，在回調結束後，需要重新將ovlist鏈表裡面的事件添加到rdllist就緒事件鏈表裡面。

同時在最後，如果rdlist不為空（表示是否有就緒事件），並且由進程等待該事件，就調用wake_up_locked再一次喚醒內核進程處理事件的到達（流程跟前面一樣，也就是將事件拷貝到用戶空間）。

到這，epoll_wait的流程是結束了，但是有一個問題，就是前面提到的進程調用epoll_wait後會睡眠，但是這個進程什麼時候被喚醒呢？在調用epoll_ctl為目標文件注冊監聽項時，對目標文件的監聽項注冊一個ep_ptable_queue_proc回調函數，ep_ptable_queue_proc回調函數將進程添加到目標文件的wakeup鏈表裡面，並且注冊ep_poll_callbak回調，當目標文件產生事件時，ep_poll_callbak回調就去喚醒等待隊列裡面的進程。

總結一下epoll該函數： epoll_wait函數會使調用它的進程進入睡眠（timeout為0時除外），如果有監聽的事件產生，該進程就被喚醒，同時將事件從內核裡面拷貝到用戶空間返回給該進程。

⑶ Android socket源碼解析(三)socket的connect源碼解析

上一篇文章著重的聊了socket服務端的bind，listen，accpet的邏輯。本文來著重聊聊connect都做了什麼？

如果遇到什麼問題，可以來本文 https://www.jianshu.com/p/da6089fdcfe1 下討論

當服務端一切都准備好了。客戶端就會嘗試的通過 connect 系統調用，嘗試的和服務端建立遠程連接。

首先校驗當前socket中是否有正確的目標地址。然後獲取IP地址和埠調用 connectToAddress 。

在這個方法中，能看到有一個 NetHooks 跟蹤socket的調用，也能看到 BlockGuard 跟蹤了socket的connect調用。因此可以hook這兩個地方跟蹤socket，不過很少用就是了。

核心方法是 socketConnect 方法，這個方法就是調用 IoBridge.connect 方法。同理也會調用到jni中。

能看到也是調用了 connect 系統調用。

文件：/ net / ipv4 / af_inet.c

在這個方法中做的事情如下：

注意 sk_prot 所指向的方法是， tcp_prot 中 connect 所指向的方法，也就是指 tcp_v4_connect .

文件：/ net / ipv4 / tcp_ipv4.c

本質上核心任務有三件:

想要能夠理解下文內容，先要明白什麼是路由表。

路由表分為兩大類：

每個路由器都有一個路由表(RIB)和轉發表 (fib表)，路由表用於決策路由，轉發表決策轉發分組。下文會接觸到這兩種表。

這兩個表有什麼區別呢？

網上雖然給了如下的定義：

但實際上在Linux 3.8.1中並沒有明確的區分。整個路由相關的邏輯都是使用了fib轉發表承擔的。

先來看看幾個和FIB轉發表相關的核心結構體：

熟悉Linux命令朋友一定就能認出這裡面大部分的欄位都可以通過route命令查找到。

命令執行結果如下：

在這route命令結果的欄位實際上都對應上了結構體中的欄位含義：

知道路由表的的內容後。再來FIB轉發表的內容。實際上從下面的源碼其實可以得知，路由表的獲取，實際上是先從fib轉發表的路由字典樹獲取到後在同感加工獲得路由表對象。

轉發表的內容就更加簡單

還記得在之前總結的ip地址的結構嗎？

需要進行一次tcp的通信，意味著需要把ip報文准備好。因此需要決定源ip地址和目標IP地址。目標ip地址在之前通過netd查詢到了，此時需要得到本地發送的源ip地址。

然而在實際情況下，往往是面對如下這么情況：公網一個對外的ip地址，而內網會被映射成多個不同內網的ip地址。而這個過程就是通過DDNS動態的在內存中進行更新。

因此 ip_route_connect 實際上就是選擇一個緩存好的，通過DDNS設置好的內網ip地址並找到作為結果返回，將會在之後發送包的時候填入這些存在結果信息。而查詢內網ip地址的過程，可以成為RTNetLink。

在Linux中有一個常用的命令 ifconfig 也可以實現類似增加一個內網ip地址的功能：

比如說為網卡eth0增加一個IPV6的地址。而這個過程實際上就是調用了devinet內核模塊設定好的添加新ip地址方式，並在回調中把該ip地址刷新到內存中。

注意 devinet 和 RTNetLink 嚴格來說不是一個存在同一個模塊。雖然都是使用 rtnl_register 注冊方法到rtnl模塊中：

文件：/ net / ipv4 / devinet.c

文件：/ net / ipv4 / route.c

實際上整個route模塊，是跟著ipv4 內核模塊一起初始化好的。能看到其中就根據不同的rtnl操作符號注冊了對應不同的方法。

整個DDNS的工作流程大體如下：

當然，在tcp三次握手執行之前，需要得到當前的源地址，那麼就需要通過rtnl進行查詢內存中分配的ip。

文件：/ include / net / route.h

這個方法核心就是 __ip_route_output_key .當目的地址或者源地址有其一為空，則會調用 __ip_route_output_key 填充ip地址。目的地址為空說明可能是在回環鏈路中通信，如果源地址為空，那個說明可能往目的地址通信需要填充本地被DDNS分配好的內網地址。

在這個方法中核心還是調用了 flowi4_init_output 進行flowi4結構體的初始化。

文件：/ include / net / flow.h

能看到這個過程把數據中的源地址，目的地址，源地址埠和目的地址埠，協議類型等數據給記錄下來，之後內網ip地址的查詢與更新就會頻繁的和這個結構體進行交互。

能看到實際上 flowi4 是一個用於承載數據的臨時結構體，包含了本次路由操作需要的數據。

執行的事務如下：

想要弄清楚ip路由表的核心邏輯，必須明白路由表的幾個核心的數據結構。當然網上搜索到的和本文很可能大為不同。本文是基於LInux 內核3.1.8.之後的設計幾乎都沿用這一套。

而內核將路由表進行大規模的重新設計，很大一部分的原因是網路環境日益龐大且復雜。需要全新的方式進行優化管理系統中的路由表。

下面是fib_table 路由表所涉及的數據結構：

依次從最外層的結構體介紹：

能看到路由表的存儲實際上通過字典樹的數據結構壓縮實現的。但是和常見的字典樹有點區別，這種特殊的字典樹稱為LC-trie 快速路由查找演算法。

這一篇文章對於快速路由查找演算法的理解寫的很不錯: https://blog.csdn.net/dog250/article/details/6596046

首先理解字典樹：字典樹簡單的來說，就是把一串數據化為二進制格式，根據左0，右1的方式構成的。

如圖下所示：

這個過程用圖來展示，就是沿著字典樹路徑不斷向下讀，比如依次讀取abd節點就能得到00這個數字。依次讀取abeh就能得到010這個數字。

說到底這種方式只是存儲數據的一種方式。而使用數的好處就能很輕易的找到公共前綴，在字典樹中找到公共最大子樹，也就找到了公共前綴。

而LC-trie 則是在這之上做了壓縮優化處理，想要理解這個演算法，必須要明白在 tnode 中存在兩個十分核心的數據：

這負責什麼事情呢？下面就簡單說說整個lc-trie的演算法就能明白了。

當然先來看看方法 __ip_dev_find 是如何查找

文件：/ net / ipv4 / fib_trie.c

整個方法就是通過 tkey_extract_bits 生成tnode中對應的葉子節點所在index，從而通過 tnode_get_child_rcu 拿到tnode節點中index所對應的數組中獲取葉下一級別的tnode或者葉子結點。

其中查找index最為核心方法如上，這個過程，先通過key左移動pos個位，再向右邊移動（32 - bits）演算法找到對應index。

在這里能對路由壓縮演算法有一定的理解即可，本文重點不在這里。當從路由樹中找到了結果就返回 fib_result 結構體。

查詢的結果最為核心的就是 fib_table 路由表，存儲了真正的路由轉發信息

文件：/ net / ipv4 / route.c

這個方法做的事情很簡單，本質上就是想要找到這個路由的下一跳是哪裡？

在這裡面有一個核心的結構體名為 fib_nh_exception 。這個是指fib表中去往目的地址情況下最理想的下一跳的地址。

而這個結構體在上一個方法通過 find_exception 獲得.遍歷從 fib_result 獲取到 fib_nh 結構體中的 nh_exceptions 鏈表。從這鏈表中找到一模一樣的目的地址並返回得到的。

文件：/ net / ipv4 / tcp_output.c