The Linux kernel is one of the most important and far-reaching open-source projects. That is why Novell Press is excited to bring you the second edition of Linux Kernel Development, Robert Love's widely acclaimed insider's look at the Linux kernel. This authoritative, practical guide helps developers better understand the Linux kernel through updated coverage of all the major subsystems as well as new features associated with the Linux 2.6 kernel. You'll be able to take an in-depth look at Linux kernel from both a theoretical and an applied perspective as you cover a wide range of topics, including algorithms, system call interface, paging strategies and kernel synchronization. Get the top information right from the source in Linux Kernel Development.
Table of Contents:
1. Introduction to the Linux Kernel.
Along Came Linus: Introduction to Linux
Overview of Operating Systems and Kernels
Linux Versus Classic Unix Kernels
Linux Kernel Versions
The Linux Kernel Development Community
Before We Begin
2. Getting Started with the Kernel.
Obtaining the Kernel Source
Installing the Kernel Source
Using Patches
The Kernel Source Tree
Building the Kernel
Minimizing Build Noise
Spawning Multiple Build Jobs
Installing the Kernel
A Beast of a Different Nature
No libc
GNU C
No Memory Protection
No (Easy) Use of Floating Point
Small, Fixed-Size Stack
Synchronization and Concurrency
Portability Is Important
So Here We Are
3. Process Management.
Process Descriptor and the Task Structure
Allocating the Process Descriptor
Storing the Process Descriptor
Process State
Manipulating the Current Process State
Process Context
The Process Family Tree
Process Creation
Copy-on-Write
fork()
vfork()
The Linux Implementation of Threads
Kernel Threads
Process Termination
Removal of the Process Descriptor
The Dilemma of the Parentless Task
Process Wrap Up
4. Process Scheduling.
Policy
I/O-Bound Versus Processor-Bound Processes
Process Priority
Timeslice
Process Preemption
The Scheduling Policy in Action
The Linux Scheduling Algorithm
Runqueues
The Priority Arrays
Recalculating Timeslices
schedule()
Calculating Priority and Timeslice
Sleeping and Waking Up
The Load Balancer
Preemption and Context Switching
User Preemption
Kernel Preemption
Real-Time
Scheduler-Related System Calls
Scheduling Policy and Priority-Related System Calls
Processor Affinity System Calls
Yielding Processor Time
Scheduler Finale
5. System Calls.
APIs, POSIX, and the C Library
Syscalls
System Call Numbers
System Call Performance
System Call Handler
Denoting the Correct System Call
Parameter Passing
System Call Implementation
Verifying the Parameters
System Call Context
Final Steps in Binding a System Call
Accessing the System Call from User-Space
Why Not to Implement a System Call
System Calls in Conclusion
6. Interrupts and Interrupt Handlers.
Interrupts
Interrupt Handlers
Top Halves Versus Bottom Halves
Registering an Interrupt Handler
Freeing an Interrupt Handler
Writing an Interrupt Handler
Shared Handlers
A Real-Life Interrupt Handler
Interrupt Context
Implementation of Interrupt Handling
/proc/interrupts
Interrupt Control
Disabling and Enabling Interrupts
Disabling a Specific Interrupt Line
Status of the Interrupt System
Don’t Interrupt Me; We’re Almost Done!
7. Bottom Halves and Deferring Work.
Bottom Halves
Why Bottom Halves?
A World of Bottom Halves
Softirqs
Implementation of Softirqs
Using Softirqs
Tasklets
Implementation of Tasklets
Using Tasklets
ksoftirqd
The Old BH Mechanism
Work Queues
Implementation of Work Queues
Using Work Queues
The Old Task Queue Mechanism
Which Bottom Half Should I Use?
Locking Between the Bottom Halves
Disabling Bottom Halves
The Bottom of Bottom-Half Processing
8. Kernel Synchronization Introduction.
Critical Regions and Race Conditions
Why Do We Need Protection?
Locking g
What Causes Concurrency, Anyway?
So, How Do I Know What Needs Protecting?
Deadlocks
Contention and Scalability
Locking and Your Code
9. Kernel Synchronization Methods.
Atomic Operations
Atomic Integer Operations
Atomic Bitwise Operations
Spin Locks
Other Spin Lock Methods
Spin Locks and Bottom Halves
Reader-Writer Spin Locks
Semaphores
Creating and Initializing Semaphores
Using Semaphores
Reader-Writer Semaphores
Spin Locks Versus Semaphores
Completion Variables
BKL: The Big Kernel Lock
Seq Locks
Preemption Disabling
Ordering and Barriers
Synchronization Summarization
10. Timers and Time Management.
Kernel Notion of Time
The Tick Rate: HZ
The Ideal HZ Value
Jiffies
Internal Representation of Jiffies
Jiffies Wraparound
User-Space and HZ
Hardware Clocks and Timers
Real-Time Clock
System Timer
The Timer Interrupt Handler
The Time of Day
Timers
Using Timers
Timer Race Conditions
The Timer Implementation
Delaying Execution
Busy Looping
Small Delays
schedule_timeout()
Out of Time
11. Memory Management.
Pages
Zones
Getting Pages
Getting Zeroed Pages
Freeing pages
kmalloc()
gfp_mask Flags
kfree()
vmalloc()
Slab Layer
Design of the Slab Layer
Slab Allocator Interface
Statically Allocating on the Stack
Playing Fair on the Stack
High Memory Mappings
Permanent Mappings
Temporary Mappings
Per-CPU Allocations
The New percpu Interface
Per-CPU Data at Compile-Time
Per-CPU Data at Runtime
Reasons for Using Per-CPU Data
Which Allocation Method Should I Use?
12. The Virtual Filesystem.
Common Filesystem Interface
Filesystem Abstraction Layer
Unix Filesystems
VFS Objects and Their Data Structures
Other VFS Objects
The Superblock Object
Superblock Operations
The Inode Object
Inode Operations
The Dentry Object
Dentry State
The Dentry Cache
Dentry Operations
The File Object
File Operations
Data Structures Associated with Filesystems
Data Structures Associated with a Process
Filesystems in Linux
13. The Block I/O Layer.
Anatomy of a Block Device
Buffers and Buffer Heads
The bio structure
The Old Versus the New
Request Queues
Requests
I/O Schedulers
The Job of an I/O Scheduler
The Linus Elevator
The Deadline I/O Scheduler
The Anticipatory I/O Scheduler
The Complete Fair Queuing I/O Scheduler
The Noop I/O Scheduler
I/O Scheduler Selection
Summary
14. The Process Address Space.
The Memory Descriptor
Allocating a Memory Descriptor
Destroying a Memory Descriptor
The mm_struct and Kernel Threads
Memory Areas
VMA Flags
VMA Operations
Lists and Trees of Memory Areas
Memory Areas in Real Life
Manipulating Memory Areas
find_vma()
find_vma_prev()
find_vma_intersection()
mmap() and do_mmap(): Creating an Address Interval
The mmap() System Call
munmap() and do_munmap(): Removing an Address Interval
The munmap() System Call
Page Tables
Conclusion
15. The Page Cache and Page Writeback.
Page Cache
The address_space Object
Radix Tree
The Old Page Hash Table
The Buffer Cache
The pdflush Daemon
Laptop Mode
bdflush and kupdated
Congestion Avoidance: Why We Have Multiple Threads
To Make a Long Story Short
16. Modules.
Hello, World!
Building Modules
At Home in the Source Tree
Living Externally
Installing Modules
Generating Module Dependencies
Loading Modules
Managing Configuration Options
Module Parameters
Exported Symbols
Wrapping Up Modules
17. kobjects and sysfs.
kobjects
ktypes
ksets
Subsystems
Structure Confusion
Managing and Manipulating kobjects
Reference Counts
krefs
sysfs
Adding and Removing kobjects from sysfs
Adding Files to sysfs
The Kernel Events Layer
kobjects and sysfs in a Nutshell
18. Debugging.
What You Need to Start
Bugs in the Kernel
printk()
The Robustness of printk()
Loglevels
The Log Buffer
syslogd and klogd
A Note About printk() and Kernel Hacking
Oops
ksymoops
kallsyms
Kernel Debugging Options
Atomicity Debugging
Asserting Bugs and Dumping Information
Magic SysRq Key
The Saga of a Kernel Debugger
gdb
kgdb
kdb
Poking and Probing the System
Using UID as a Conditional
Using Condition Variables
Using Statistics
Rate Limiting Your Debugging
Binary Searching to Find the Culprit Change
When All Else Fails: The Community
19. Portability.
History of Portability in Linux
Word Size and Data Types
Opaque Types
Special Types
Explicitly Sized Types
Signedness of Chars
Data Alignment
Avoiding Alignment Issues
Alignment of Nonstandard Types
Structure Padding
Byte Order
History of Big- and Little-Endian
Byte Ordering in the Kernel
Time
Page Size
Processor Ordering
SMP, Kernel Preemption, and High Memory
Portability Is Fun
20. Patches, Hacking, and the Community.
The Community
Linux Coding Style
Indention
Braces
Line Size
Naming
Functions
Comments
Typedefs
Using What Is Already Provided
No ifdefs in the Source
Structure Initializers
Fixing Code Up Ex Post Facto
Chain of Command
Submitting Bug Reports
Generating Patches
Submitting Patches
Conclusion
Appendix A. Linked Lists.
Circular Linked Lists
Moving Through a Linked List
The Linux Kernel’s Implementation
The Linked-List Structure
Manipulating Linked Lists
Traversing Linked Lists
Appendix B. Kernel Random Number Generator.
Design and Implementation
The Dilemma of System Startup
Interfaces to Input Entropy
Interfaces to Output Entropy
Appendix C. Algorithmic Complexity.
Algorithms
Big-O Notation
Big Theta Notation
Putting It All Together
Perils of Time Complexity
Bibliography and Reading List.
Books on Operating System Design
Books on Unix Kernels
Books on Linux Kernels
Books on Other Kernels
Books on the Unix API
Books on the C Programming Language
Other Works
Websites
Index.
