You are previewing Linux Kernel Development, Second Edition.
O'Reilly logo
Linux Kernel Development, Second Edition

Book Description

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