Chapter 1 Overview 1
1.1 History of UNIX 2
1.2 Standards and Common Interfaces 4
1.3 Free Software and Open Source 5
1.4 A Quick Survey of Linux Distributions 5
1.4.1 Debian 6
1.4.2 Red Hat/Fedora 6
1.4.3 Mandriva 7
1.4.4 SUSE 7
1.4.5 Gentoo 7
1.4.6 Yellow Dog 7
1.4.7 Other Distros 8
1.5 Kernel Release Information 8
1.6 Linux on Power 8
1.7 What Is an Operating System? 9
1.8 Kernel Organization 11
1.9 Overview of the Linux Kernel 11
1.9.1 User Interface 12
1.9.2 User Identification 13
1.9.3 Files and Filesystems 13
1.9.4 Processes 20
1.9.5 System Calls 24
1.9.6 Linux Scheduler 24
1.9.7 Linux Device Drivers 25
1.10 Portability and Architecture Dependence 26
Summary 27
Exercises 27
Chapter 2 Exploration Toolkit 29
2.1 Common Kernel Datatypes 30
2.1.1 Linked Lists 30
2.1.2 Searching 34
2.1.3 Trees 35
2.2 Assembly 38
2.2.1 PowerPC 39
2.2.2 x86 42
2.3 Assembly Language Example 46
2.3.1 x86 Assembly Example 47
2.3.2 PowerPC Assembly Example 50
2.4 Inline Assembly 55
2.4.1 Ouput Operands 55
2.4.2 Input Operands 56
2.4.3 Clobbered Registers(or Clobber List) 56
2.4.4 Parameter Numbering 56
2.4.5 Constraints 56
2.4.6 asm 57
2.4.7 __volatile__ 57
2.5 Quirky C Language Usage 62
2.5.1 asmlinkage 62
2.5.2 UL 63
2.5.3 inline 63
2.5.4 const and volatile 64
2.6 A Quick Tour of Kernel Exploration Tools 65
2.6.1 objdump/readelf 65
2.6.2 hexdump 66
2.6.3 nm 66
2.6.4 objcopy 67
2.6.5 ar 67
2.7 Kernel Speak:Listening to Kernel Messages 67
2.7.1 printk() 67
2.7.2 dmesg 68
2.7.3 /var/log/messages 68
2.8 Miscellaneous Quirks 68
2.8.1 __init 68
2.8.2 likely() and unlikely() 69
2.8.3 IS_ERRand PTR ERR 71
2.8.4 Notifier Chains 71
Summary 71
Project:Hellomod 72
Step 1:Writing the Linux Module Skeleton 72
Step 2:Compiling the Module 74
Step 3:Running the Code 75
Exercises 76
Chapter 3 Processes:The Principal Model of Execution 77
3.1 Introducing Our Program 80
3.2 Process Descriptor 82
3.2.1 Process Attribute-Related Fields 84
3.2.2 Scheduling Related Fields 87
3.2.3 Process Relations-Related Fields 90
3.2.4 Process Credentials-Related Fields 92
3.2.5 Process Capabilities-Related Fields 94
3.2.6 Process Limitations-Related Fields 97
3.2.7 Filesystem- and Address Space-Related Fields 99
3.3 Process Creation:fork(),vfork(),and clone() System Calls 101
3.3.1 fork() Function 103
3.3.2 vfork() Function 104
3.3.3 clone() Function 105
3.3.4 do_fork() Function 106
3.4 Process Lifespan 109
3.4.1 Process States 109
3.4.2 Process State Transitions 111
3.5 Process Termination 116
3.5.1 sys_exit()Function 117
3.5.2 do_exit()Function 117
3.5.3 Parent Notification and sys_wait4() 120
3.6 Keeping Track of Processes:Basic Scheduler Construction 124
3.6.1 Basic Structure 125
3.6.2 Waking Up From Waiting or Activation 126
3.7 Wait Queues 133
3.7.1 Adding to the Wait Queue 136
3.7.2 Waiting on the Event 137
3.7.3 Waking Up 140
3.8 Asynchronous Execution Flow 142
3.8.1 Exceptions 143
3.8.2 Interrupts 146
Summary 173
Project:current System Variable 174
Project Source Code 175
Running the Code 177
Exercises 177
Chapter 4 Memory Management 179
4.1 Pages 183
4.1.1 flags 184
4.2 Memory Zones 187
4.2.1 Memory Zone Descriptor 187
4.2.2 Memory Zone Helper Functions 190
4.3 Page Frames 191
4.3.1 Functions for Requesting Page Frames 191
4.3.2 Functions for Releasing Page Frames 193
4.3.3 Buddy System 194
4.4 Slab Allocator 200
4.4.1 Cache Descriptor 203
4.4.2 General Purpose Cache Descriptor 207
4.4.3 Slab Descriptor 208
4.5 Slab Allocator's Lifecycle 211
4.5.1 Global Variables of the Slab Allocator 211
4.5.2 Creating a Cache 213
4.5.3 Slab Creation and cache_grow() 219
4.5.4 Slab Destruction:Returning Memory and kmem_cache_destroy() 222
4.6 Memory Request Path 224
4.6.1 kmalloc() 224
4.6.2 kmem_cache_alloc() 225
4.7 Linux Process Memory Structures 226
4.7.1 mm_struct 227
4.7.2 vm_area_struct 230
4.8 Process Image Layout and Linear Address Space 232
4.9 Page Tables 236
4.10 Page Fault 237
4.10.1 x86 Page Fault Exception 238
4.10.2 Page Fault Handler 239
4.10.3 PowerPC Page Fault Exception 249
Summary 249
Project:Process Memory Map 250
Exercises 251
Chapter 5 Input/Output 253
5.1 How Hardware Does It:Busses,Bridges,Ports,and Interfaces 255
5.2 Devices 260
5.2.1 Block Device Overview 260
5.2.2 Request Queues and Scheduling I/O 263
5.2.3 Example:"Generic" Block Driver 274
5.2.4 Device Operations 277
5.2.5 Character Device Overview 279
5.2.6 A Note on Network Devices 280
5.2.7 Clock Devices 280
5.2.8 Terminal Devices 280
5.2.9 Direct Memory Access(DMA) 281
Summary 281
Project:Building a Parallel Port Driver 282
Parallel Port Hardware 282
Parallel Port Software 285
Exercises 293
Chapter 6 Filesystems 295
6.1 General Filesystem Concepts 296
6.1.1 File and Filenames 296
6.1.2 File Types 297
6.1.3 Additional File Attributes 298
6.1.4 Directories and Pathnarnes 298
6.1.5 File Operations 299
6.1.6 File Descriptors 300
6.1.7 Disk Blocks,Partitions,and Implementation 301
6.1.8 Performance 302
6.2 Linux Virtual Filesystem 302
6.2.1 VFS Data Structures 305
6.2.2 Global and Local List References 322
6.3 Structures Associated with VFS 324
6.3.1 fs_struct Structure 324
6.3.2 files_struct Structure 326
6.4 Page Cache 330
6.4.1 address_space Structure 331
6.4.2 Buffer_head Structure 334
6.5 VFS System Calls and the Filesystem Layer 336
6.5.1 open() 337
6.5.2 close() 345
6.5.3 read() 348
6.5.4 write() 369
Summary 371
Exercises 372
Chapter 7 Scheduling and Kernel Synchronization 373
7.1 Linux Scheduler 375
7.1.1 Choosing the Next Task 376
7.1.2 Context Switch 383
7.1.3 Yielding the CPU 394
7.2 Preemption 405
7.2.1 Explicit Kernel Preemption 405
7.2.2 Implicit User Preemption 405
7.2.3 Implicit Kernel Preemption 407
7.3 Spinlocks and Semaphores 409
7.4 System Clock:Of Time and Timers 411
7.4.1 Real-Time Clock:What Time Is It? 412
7.4.2 Reading the PPC Real-Time Clock 414
7.4.3 Reading the x86 Real-Time Clock 417
Summary 418
Exercises 419
Chapter 8 Booting the Kernel 421
8.1 BIOS and Open Firmware 423
8.2 Boot Loaders 424
8.2.1 GRUB 426
8.2.2 LILO 429
8.2.3 PowerPC and Yaboot 430
8.3 Architecture-Dependent Memory Initialization 431
8.3.1 PowerPC Hardware Memory Management 431
8.3.2 x86 Intel-Based Hardware Memory Management 444
8.3.3 PowerPC and x86 Code Convergence 455
8.4 Initial RAM Disk 456
8.5 The Beginning:start_kernel() 456
8.5.1 The Call to lock_kernel() 458
8.5.2 The Call to page_address_init() 460
8.5.3 The Call to printk(linux_banner) 464
8.5.4 The Call to setup_arch 464
8.5.5 The Call to setup_per_cpu_areas() 469
8.5.6 The Call to smp_prepare_boot_cpu() 470
8.5.7 The Call to sched_init() 471
8.5.8 The Call to build_all_zonelists() 474
8.5.9 The Call to page_alloc_init 475
8.5.10 The Call to parse_args() 476
8.5.11 The Call to trap_init() 479
8.5.12 The Call to rcu_init() 479
8.5.13 The Call to init_IRQ() 480
8.5.14 The Call to softirq_init() 481
8.5.15 The Call to time_init() 482
8.5.16 The Call to console_init() 484
8.5.17 The Call to profile_init() 485
8.5.18 The Call to local_irq_enable() 485
8.5.19 initrd Configuration 486
8.5.20 The Call to mem_init() 486
8.5.21 The Call to late_time_init() 493
8.5.22 The Call to calibrate_delay() 494
8.5.23 The Call to pgtable_cache_init() 495
8.5.24 The Call to buffer_init() 497
8.5.25 The Call to security_scaffolding_startup() 497
8.5.26 The Call to vfs_caches_init() 498
8.5.27 The Call to radix_tree_init() 508
8.5.28 The Call to signals_init() 509
8.5.29 The Call to page_writeback_init() 509
8.5.30 TheCall to proc_root_init() 512
8.5.31 The Call to init_idle() 514
8.5.32 The Call to rest_init() 515
8.6 The initThread(or Process 1) 517
Summary 522
Exercises 523
Chapter 9 Building the Linux Kernel 525
9.1 Toolchain 526
9.1.1 Compilers 527
9.1.2 Cross Compilers 528
9.1.3 Linker 528
9.1.4 ELF Object Files 529
9.2 Kernel Source Build 536
9.2.1 Source Explained 536
9.2.2 Building the Kernel Image 542
Summary 551
Exercises 551
Chapter 10 Adding Your Code to the Kernel 553
10.1 Traversing the Source 554
10.1.1 Getting Familiar with the Filesystem 555
10.1.2 Filps and Fops 556
10.1.3 User Memory and Kernel Memory 558
10.1.4 Wait Queues 559
10.1.5 Work Queues and Interrupts 564
10.1.6 System Calls 567
10.1.7 Other Types of Drivers 567
10.1.8 Device Model and sysfs 572
10.2 Writing the Code 575
10.2.1 Device Basics 575
10.2.2 Symbol Exporting 578
10.2.3 IOCTL 578
10.2.4 Polling and Interrupts 582
10.2.5 Work Queues and Tasklets 586
10.2.6 Adding Code for a System Call 588
10.3 Building and Debugging 590
10.3.1 Debugging Device Drivers 590
Summary 591
Exercises 593
Bibliography 595
Index 599