توسعه هسته لینوکس: راهنمای جامع طراحی و پیاده‌سازی هسته لینوکس

Linux Kernel Development details the design and implementation of the Linux kernel, presenting the content in a manner that is beneficial to those writing and developing kernel code, as well as to programmers seeking to better understand the operating system and become more efficient and productive in their coding. The book details the major subsystems and features of the Linux kernel, including its design, implementation, and interfaces. It covers the Linux kernel with both a practical and theoretical eye, which should appeal to readers with a variety of interests and needs. The author, a core kernel developer, shares valuable knowledge and experience on the 2.6 Linux kernel. Specific topics covered include process management, scheduling, time management and timers, the system call interface, memory addressing, memory management, the page cache, the VFS, kernel synchronization, portability concerns, and debugging techniques. This book covers the most interesting features of the Linux 2.6 kernel, including the CFS scheduler, preemptive kernel, block I/O layer, and I/O schedulers. The third edition of Linux Kernel Development includes new and updated material throughout the book: An all-new chapter on kernel data structures Details on interrupt handlers and bottom halves Extended coverage of virtual memory and memory allocation Tips on debugging the Linux kernel In-depth coverage of kernel synchronization and locking Useful insight into submitting kernel patches and working with the Linux kernel community Cover 1 Half Title 2 Developer’s Library 3 Title 4 Copyright 5 Dedication 6 Contents at a Glance 7 Table of Contents 8 1 Introduction to the Linux Kernel 28 History of Unix 28 Along Came Linus: Introduction to Linux 30 Overview of Operating Systems and Kernels 31 Linux Versus Classic Unix Kernels 33 Linux Kernel Versions 35 The Linux Kernel Development Community 37 Before We Begin 37 2 Getting Started with the Kernel 38 Obtaining the Kernel Source 38 Using Git 38 Installing the Kernel Source 39 Using Patches 39 The Kernel Source Tree 39 Building the Kernel 40 Configuring the Kernel 41 Minimizing Build Noise 42 Spawning Multiple Build Jobs 43 Installing the New Kernel 43 A Beast of a Different Nature 43 No libc or Standard Headers 44 GNU C 45 No Memory Protection 47 No (Easy) Use of Floating Point 47 Small, Fixed-Size Stack 47 Synchronization and Concurrency 48 Importance of Portability 48 Conclusion 48 3 Process Management 50 The Process 50 Process Descriptor and the Task Structure 51 Allocating the Process Descriptor 52 Storing the Process Descriptor 53 Process State 54 Manipulating the Current Process State 56 Process Context 56 The Process Family Tree 56 Process Creation 58 Copy-on-Write 58 Forking 59 vfork() 60 The Linux Implementation of Threads 60 Creating Threads 61 Kernel Threads 62 Process Termination 63 Removing the Process Descriptor 64 The Dilemma of the Parentless Task 65 Conclusion 67 4 Process Scheduling 68 Multitasking 68 Linux’s Process Scheduler 69 Policy 70 I/O-Bound Versus Processor-Bound Processes 70 Process Priority 71 Timeslice 72 The Scheduling Policy in Action 72 The Linux Scheduling Algorithm 73 Scheduler Classes 73 Process Scheduling in Unix Systems 74 Fair Scheduling 75 The Linux Scheduling Implementation 77 Time Accounting 77 Process Selection 79 The Scheduler Entry Point 84 Sleeping and Waking Up 85 Preemption and Context Switching 89 User Preemption 89 Kernel Preemption 90 Real-Time Scheduling Policies 91 Scheduler-Related System Calls 92 Scheduling Policy and Priority-Related System Calls 93 Processor Affinity System Calls 93 Yielding Processor Time 93 Conclusion 94 5 System Calls 96 Communicating with the Kernel 96 APIs, POSIX, and the C Library 97 Syscalls 98 System Call Numbers 99 System Call Performance 99 System Call Handler 100 Denoting the Correct System Call 100 Parameter Passing 101 System Call Implementation 101 Implementing System Calls 101 Verifying the Parameters 102 System Call Context 105 Final Steps in Binding a System Call 106 Accessing the System Call from User-Space 108 Why Not to Implement a System Call 109 Conclusion 110 6 Kernel Data Structures 112 Linked Lists 112 Singly and Doubly Linked Lists 112 Circular Linked Lists 113 Moving Through a Linked List 114 The Linux Kernel’s Implementation 115 Manipulating Linked Lists 117 Traversing Linked Lists 120 Queues 123 kfifo 124 Creating a Queue 124 Enqueuing Data 125 Dequeuing Data 125 Obtaining the Size of a Queue 125 Resetting and Destroying the Queue 126 Example Queue Usage 126 Maps 127 Initializing an idr 128 Allocating a New UID 128 Looking Up a UID 129 Removing a UID 130 Destroying an idr 130 Binary Trees 130 Binary Search Trees 131 Self-Balancing Binary Search Trees 132 What Data Structure to Use, When 135 Algorithmic Complexity 136 Algorithms 136 Big-O Notation 136 Big Theta Notation 136 Time Complexity 137 Conclusion 138 7 Interrupts and Interrupt Handlers 140 Interrupts 140 Interrupt Handlers 141 Top Halves Versus Bottom Halves 142 Registering an Interrupt Handler 143 Interrupt Handler Flags 143 An Interrupt Example 144 Freeing an Interrupt Handler 145 Writing an Interrupt Handler 145 Shared Handlers 146 A Real-Life Interrupt Handler 147 Interrupt Context 149 Implementing Interrupt Handlers 150 /proc/interrupts 153 Interrupt Control 154 Disabling and Enabling Interrupts 154 Disabling a Specific Interrupt Line 156 Status of the Interrupt System 157 Conclusion 158 8 Bottom Halves and Deferring Work 160 Bottom Halves 161 Why Bottom Halves? 161 A World of Bottom Halves 162 Softirqs 164 Implementing Softirqs 164 Using Softirqs 167 Tasklets 169 Implementing Tasklets 169 Using Tasklets 171 ksoftirqd 173 The Old BH Mechanism 175 Work Queues 176 Implementing Work Queues 176 Using Work Queues 180 The Old Task Queue Mechanism 182 Which Bottom Half Should I Use? 183 Locking Between the Bottom Halves 184 Disabling Bottom Halves 184 Conclusion 186 9 An Introduction to Kernel Synchronization 188 Critical Regions and Race Conditions 189 Why Do We Need Protection? 189 The Single Variable 190 Locking 192 Causes of Concurrency 194 Knowing What to Protect 195 Deadlocks 196 Contention and Scalability 198 Conclusion 199 10 Kernel Synchronization Methods 202 Atomic Operations 202 Atomic Integer Operations 203 64-Bit Atomic Operations 207 Atomic Bitwise Operations 208 Spin Locks 210 Spin Lock Methods 211 Other Spin Lock Methods 213 Spin Locks and Bottom Halves 214 Reader-Writer Spin Locks 215 Semaphores 217 Counting and Binary Semaphores 218 Creating and Initializing Semaphores 219 Using Semaphores 220 Reader-Writer Semaphores 221 Mutexes 222 Semaphores Versus Mutexes 224 Spin Locks Versus Mutexes 224 Completion Variables 224 BKL: The Big Kernel Lock 225 Sequential Locks 227 Preemption Disabling 228 Ordering and Barriers 230 Conclusion 233 11 Timers and Time Management 234 Kernel Notion of Time 235 The Tick Rate: HZ 235 The Ideal HZ Value 237 Advantages with a Larger HZ 237 Disadvantages with a Larger HZ 238 Jiffies 239 Internal Representation of Jiffies 240 Jiffies Wraparound 241 User-Space and HZ 243 Hardware Clocks and Timers 243 Real-Time Clock 244 System Timer 244 The Timer Interrupt Handler 244 The Time of Day 247 Timers 249 Using Timers 249 Timer Race Conditions 251 Timer Implementation 251 Delaying Execution 252 Busy Looping 252 Small Delays 253 schedule_timeout() 254 Conclusion 257 12 Memory Management 258 Pages 258 Zones 260 Getting Pages 262 Getting Zeroed Pages 263 Freeing Pages 264 kmalloc() 265 gfp_mask Flags 265 kfree() 270 vmalloc() 271 Slab Layer 272 Design of the Slab Layer 273 Slab Allocator Interface 276 Statically Allocating on the Stack 279 Single-Page Kernel Stacks 279 Playing Fair on the Stack 280 High Memory Mappings 280 Permanent Mappings 281 Temporary Mappings 281 Per-CPU Allocations 282 The New percpu Interface 283 Per-CPU Data at Compile-Time 283 Per-CPU Data at Runtime 284 Reasons for Using Per-CPU Data 285 Picking an Allocation Method 286 Conclusion 287 13 The Virtual Filesystem 288 Common Filesystem Interface 288 Filesystem Abstraction Layer 289 Unix Filesystems 290 VFS Objects and Their Data Structures 292 The Superblock Object 293 Superblock Operations 294 The Inode Object 297 Inode Operations 298 The Dentry Object 302 Dentry State 303 The Dentry Cache 303 Dentry Operations 305 The File Object 306 File Operations 307 Data Structures Associated with Filesystems 312 Data Structures Associated with a Process 313 Conclusion 315 14 The Block I/O Layer 316 Anatomy of a Block Device 317 Buffers and Buffer Heads 318 The bio Structure 321 I/O vectors 322 The Old Versus the New 323 Request Queues 324 I/O Schedulers 324 The Job of an I/O Scheduler 325 The Linus Elevator 326 The Deadline I/O Scheduler 327 The Anticipatory I/O Scheduler 329 The Complete Fair Queuing I/O Scheduler 330 The Noop I/O Scheduler 330 I/O Scheduler Selection 331 Conclusion 331 15 The Process Address Space 332 Address Spaces 332 The Memory Descriptor 333 Allocating a Memory Descriptor 335 Destroying a Memory Descriptor 336 The mm_struct and Kernel Threads 336 Virtual Memory Areas 336 VMA Flags 338 VMA Operations 339 Lists and Trees of Memory Areas 340 Memory Areas in Real Life 341 Manipulating Memory Areas 342 find_vma() 343 find_vma_prev() 344 find_vma_intersection() 344 mmap() and do_mmap(): Creating an Address Interval 345 munmap() and do_munmap(): Removing an Address Interval 347 Page Tables 347 Conclusion 349 16 The Page Cache and Page Writeback 350 Approaches to Caching 350 Write Caching 351 Cache Eviction 351 The Linux Page Cache 353 The address_space Object 353 address_space Operations 355 Radix Tree 357 The Old Page Hash Table 357 The Buffer Cache 357 The Flusher Threads 358 Laptop Mode 360 History: bdflush, kupdated, and pdflush 360 Avoiding Congestion with Multiple Threads 361 Conclusion 362 17 Devices and Modules 364 Device Types 364 Modules 365 Hello, World! 365 Building Modules 367 Installing Modules 369 Generating Module Dependencies 369 Loading Modules 370 Managing Configuration Options 371 Module Parameters 373 Exported Symbols 375 The Device Model 375 Kobjects 376 Ktypes 377 Ksets 378 Interrelation of Kobjects, Ktypes, and Ksets 378 Managing and Manipulating Kobjects 379 Reference Counts 380 sysfs 382 Adding and Removing kobjects from sysfs 384 Adding Files to sysfs 385 The Kernel Events Layer 388 Conclusion 389 18 Debugging 390 Getting Started 390 Bugs in the Kernel 391 Debugging by Printing 391 Robustness 392 Loglevels 392 The Log Buffer 393 syslogd and klogd 394 Transposing printf() and printk() 394 Oops 394 ksymoops 396 kallsyms 396 Kernel Debugging Options 397 Asserting Bugs and Dumping Information 397 Magic SysRq Key 398 The Saga of a Kernel Debugger 399 gdb 399 kgdb 400 Poking and Probing the System 400 Using UID as a Conditional 400 Using Condition Variables 401 Using Statistics 401 Rate and Occurrence Limiting Your Debugging 402 Binary Searching to Find the Culprit Change 403 Binary Searching with Git 403 When All Else Fails: The Community 404 Conclusion 405 19 Portability 406 Portable Operating Systems 406 History of Portability in Linux 407 Word Size and Data Types 408 Opaque Types 411 Special Types 411 Explicitly Sized Types 412 Signedness of Chars 413 Data Alignment 413 Avoiding Alignment Issues 414 Alignment of Nonstandard Types 414 Structure Padding 414 Byte Order 416 Time 418 Page Size 418 Processor Ordering 419 SMP, Kernel Preemption, and High Memory 420 Conclusion 420 20 Patches, Hacking, and the Community 422 The Community 422 Linux Coding Style 423 Indention 423 Switch Statements 423 Spacing 424 Braces 425 Line Length 426 Naming 427 Functions 427 Comments 427 Typedefs 428 Use Existing Routines 429 Minimize ifdefs in the Source 429 Structure Initializers 429 Fixing Up Code Ex Post Facto 430 Chain of Command 430 Submitting Bug Reports 430 Patches 431 Generating Patches 431 Generating Patches with Git 432 Submitting Patches 433 Conclusion 433 Bibliography 434 Index 438 A 438 B 440 C 441 D 442 E 445 F 445 G 447 H 447 I 448 J 450 K 450 L 451 M 453 N 455 O 455 P 456 Q 459 R 459 S 460 T 464 U 465 V 466 W-X-Y 467 Z 467 0672329468,9780672329463 Linux Kernel Development details the design and implementation of the Linux kernel, presenting the content in a manner that is beneficial to those writing and developing kernel code. While the book discusses topics that are theoretical, it does so with the goal of assisting programmers so they better understand the topics and become more efficient and productive in their coding.The book discusses the major subsystems and features of the Linux kernel, including design and implementation, their purpose and goals, and their interfaces. Important computer science and operating system design details are also addressed. The book covers the Linux kernel from both angles -- theoretical and applied -- which should appeal to both types of readers.The author is involved in Linux kernel development, so the latest kernel version is detailed, as the author has access to the not-yet-released development releases.Specific topics covered will include: all the important algorithms, relevant subsystems, process management, scheduling, time management and timers, system call interface, memory addressing, memory management, paging strategies, caching layers, VFS, kernel synchronization, and signals.