. 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.
