數據結構與算法(第3版)（簡體書）

《數據結構與算法（第3版）》根據作者多年的從業經驗，從開發實戰出發，全面深入地講解了Android驅動開發。本書以Android驅動本質為源，深入淺出地剖析了Android驅動程序開發要用到的DMA、中斷、同步、等待隊列與signal等多項技術。本書還從系統的角度描述了Android驅動與Android其他部分的有機結合，為Android用戶提供各類智能輸入/輸出服務。
本書適合從事Linux開發、Android底層驅動開發、系統框架開發，以及Android底層模塊驗證測試等的相關軟件工程人員閱讀；也適合從事Android智能手機其他領域的研發人員參考；還適合作為大、中專院校與培訓機構的相關實踐性指導教材。

 

前言
第一篇　Android的前世今生——Android概述篇
第1章　Android的前世今生 2
1.1　Android的起源 2
1.2　開放手機聯盟 2
1.3　開源與相關協議 3
1.4　系統的升級與發展 3
第2章　Android體系結構 4
2.1　四層空間基本結構 4
2.1.1　Android系統底層開發 6
2.1.2　應用程序開發 7
2.2　Android代碼目錄結構 7
2.3　Android開發環境搭建 8
第二篇　勿于浮砂筑高臺——Linux驅動基礎篇
第3章　Linux 內核綜述 14
3.1　OS基本概念 14
3.1.1　多用戶系統 15
3.1.2　用戶和組 15
3.1.3　進程 16
3.1.4　Linux單核架構 16
3.2　Linux內核綜述 18
3.2.1　進程/內核模型綜述 18
3.2.2　內存管理綜述 26
3.2.3　文件系統綜述 29
3.2.4　設備驅動簡述 34
第4章　Linux內核編程與內核模塊 35
4.1　Linux內核源代碼目錄結構 35
4.2　Linux內核的編譯與啟動 36
4.3　Linux內核的C編程 37
4.4　Linux內核模塊基礎與骨架 43
4.5　Linux模塊的加載與卸載 46
4.6　Linux模塊的參數與導出符號 46
4.7　Linux模塊的使用計數 48
第5章　Linux文件系統 50
5.1　Linux文件系統概述 50
5.1.1　Linux文件系統的目錄結構 50
5.1.2　設備驅動與Linux文件系統的關聯 51
5.2　Linux設備文件系統 55
5.2.1　devfs設備文件系統 55
5.2.2　udev設備文件系統 56
5.2.3　sysfs文件系統與Linux設備 57
5.2.4　udev的組成 67
5.2.5　udev規則文件 68
第6章　Linux字符設備驅動 70
6.1　Linux字符設備驅動結構 70
6.1.1　cdev結構體 70
6.1.2　分配和釋放設備號 71
6.1.3　file_operations結構體 72
6.1.4　Linux字符設備驅動的組成 74
6.2　一個字符設備驅動例子——virtualchar 77
6.2.1　頭文件、宏及設備結構體 77
6.2.2　加載與卸載設備驅動 78
6.2.3　驅動函數實現 79
6.2.4　驅動設備私有數據 83
6.3　對virtualchar設備的訪問 90
第7章　Linux設備驅動中的內存與I/O訪問 92
7.1　CPU與內存和I/O之間的故事 92
7.1.1內存空間與I/O空間 92
7.1.2　內存管理單元MMU 93
7.2　Linux內存管理 97
7.3　Linux內存訪問 99
7.4　Linux I/O訪問 102
7.4.1　訪問I/O 102
7.4.2　申請與釋放I/O資源 105
7.4.3　I/O訪問流程 107
7.4.4　設備地址與用戶空間的映射 107
7.5　DMA 114
7.5.1　DMA與Cache的一致性 114
7.5.2　Linux下的DMA編程 114
第8章　Linux設備驅動中的中斷 125
8.1　Linux中斷及中斷處理架構 125
8.2　Linux中斷編程 126
8.2.1　申請和釋放中斷 126
8.2.2　使能與屏蔽中斷 127
8.2.3　底半部機制 127
8.2.4　中斷共享 130
8.3　Linux定時器 132
8.4　Linux延時處理 134
8.4.1　短延時 135
8.4.2　長延時 135
8.4.3　睡眠延時 136
第9章　Linux設備驅動中的并發 138
9.1　Linux中的并發與競爭 138
9.2　Linux中常用的同步訪問技術 139
9.2.1　中斷屏蔽 139
9.2.2　原子操作 140
9.2.3　自旋鎖 142
9.2.4　信號量 147
9.2.5　互斥燈 152
9.3　增加并發控制的virtualchar驅動 153
第10章　Linux設備的阻塞式與非阻塞式訪問 157
10.1　阻塞式與非阻塞式訪問 157
10.1.1　等待隊列 158
10.1.2　支持阻塞操作的virtualfifo設備驅動 162
10.2　Linux的輪詢訪問 167
10.2.1　應用程序中的輪詢編程 167
10.2.2　設備驅動中的輪詢編程 168
10.2.3　支持輪詢操作的virtualfifo驅動 169
第11章　Linux設備驅動中的異步訪問 171
11.1　Linux 2.6 中的異步訪問 171
11.1.1　異步訪問概念與GNU C庫函數 171
11.1.2　使用信號作為異步訪問的通知 175
11.1.3　使用回調函數作為異步訪問的通知 177
11.1.4　異步訪問與設備驅動 178
11.2　異步Fifo驅動例子 180
11.2.1　在virtualfifo驅動中增加異步通知 180
11.2.2　在用戶空間驗證virtualfifo的異步通知 182
第12章　Linux塊設備驅動 184
12.1　塊設備的I/O操作特點 184
12.2　Linux塊設備驅動結構 184
12.2.1　block_device_operations結構體 184
12.2.2　gendisk結構體 186
12.2.3　request與bio結構體 188
12.2.4　塊設備驅動注冊與注銷 197
12.3　Linux塊設備驅動的模塊加載與卸載 198
12.4　塊設備的打開/釋放/IOCTL 200
第13章　Linux網絡設備驅動 202
13.1　Linux網絡設備驅動體系結構 202
13.2　Linux網絡設備驅動結構 203
13.3　Linux網絡設備驅動I/O實現 204
13.3.1　網絡設備初始化 204
13.3.2　網絡數據包的收發 205
第三篇　實踐出真知——Android驅動實踐篇
第14章　Android HAL層的設計 208
14.1　Android HAL概述 208
14.2　為Android開發虛擬驅動virtualio 209
14.3　Android集成C程序訪問virtualio 220
14.4　Android通過HAL訪問virtualio 222
14.4.1　virtualio HAL模塊實現 222
14.4.2　實現訪問virtualio HAL模塊JNI 226
14.4.3　在Framework層增加virtualio服務 229
第15章　Framebuffer子系統 231
15.1　Linux Framebuffer一般子系統 231
15.1.1　Framebuffer數據結構 231
15.1.2　Framebuffer驅動 237
15.2　Android Framebuffer子系統實踐 238
15.2.1　硬件基礎 238
15.2.2　CPU側顯示驅動模塊 240
15.2.3　LCM驅動模塊 242
15.3　Android系統對Framebuffer的使用 247
第16章　Input子系統 249
16.1　Linux Input一般子系統 249
16.1.1　Input數據結構 250
16.1.2　Input內核模塊 252
16.2　Android Input子系統實踐 257
16.2.1　硬件基礎 258
16.2.2　Input驅動模塊 258
16.3　Android系統對Input的使用 263
第17章　V4L2子系統 266
17.1　Linux V4L2一般子系統 266
17.1.1　V4L2數據結構 266
17.1.2　V4L2接口 268
17.1.3　V4L2虛擬驅動vivi 273
17.2　Android V4L2實踐 279
17.2.1　硬件基礎 280
17.2.2　CPU側CCIC驅動模塊 281
17.2.3　OV5642模組驅動模塊 283
17.3　Android系統對V4L2的使用 286
第18章　Binder IPC通信子系統 288
18.1　Binder驅動概述 288
18.2　Binder通信模型 288
18.3　Binder驅動 291
18.3.1　Binder相關的結構體 292
18.3.2　Android Binder子系統的架構設計 292
18.4　Binder的工作流程 293
第19章　USB子系統 295
19.1　USB協議基礎知識 295
19.1.1　USB物理連接 295
19.1.2　USB通信協議 297
19.2　USB子系統底層 299
19.2.1　USB Core 299
19.2.2　Linux USB gadget三層架構 303
19.3　Android USB子系統實踐 305
19.3.1　Android IPC通信補充 305
19.3.2　Android USB Mass Storage流程分析 309
第20章　Bootloader引導子系統 312
20.1　Bootloader流程分析 312
20.1.1　Bootloader概述 312
20.1.2　U-Boot啟動流程分析 314
20.2　Bootloader修改指南 317
20.2.1　開機第一幀圖的修改 317
20.2.2　開機模式的定制 318
參考文獻 321