Linux Kernel Architecture

Mauerer ftoc.tex V4 - 09/03/2008 11:13pm Page xviii

• Chapter 1: Introductionand Overview.......................................... Introduction..................................................................xxvii


• Chapter 2: Process Management and Scheduling.............................


• Chapter 3: Memory Management............................................


• Chapter 4: Virtual Process Memory..........................................


• Chapter 5: Locking and InterprocessCommunication.......................


• Chapter 6: Device Drivers....................................................


• Chapter 7: Modules..........................................................


• Chapter 8: The Virtual Filesystem............................................


• Chapter 9: The Extended Filesystem Family.................................


• Chapter 10: Filesystems without Persistent Storage.......................


• Chapter 11: Extended Attributes and Access Control Lists.................


• Chapter 12: Networks........................................................


• Chapter 13: System Calls....................................................


• Chapter 14: Kernel Activities................................................


• Chapter 15: Time management..............................................


• Chapter 16: Page and Buffer Cache..........................................


• Chapter 17: Data Synchronization...........................................


• Chapter 18: Page Reclaim and Swapping...................................


• Chapter 19: Auditing........................................................


• Appendix A: Architecture Specifics.........................................


• Appendix B: Working with the Source Code


• Appendix C: Notes on C.....................................................


• Appendix D: System Startup................................................


• Appendix E: The ELF Binary Format.........................................


• Appendix F: The Kernel Development Process..............................


• Bibliography.................................................................


• Index........................................................................


• Chapter 1: Introduction and Overview Introduction xxvii


• Tasks of the Kernel


• Implementation Strategies


• Elements of the Kernel


• Processes, Task Switching, and Scheduling


• UnixProcesses


• Address Spaces and Privilege Levels


• Page Tables


• Allocation of Physical Memory


• Timing


• System Calls


• Device Drivers, Block and Character Devices


• Networks


• Filesystems


• Modules and Hotplugging


• Caching


• List Handling


• Object Management and Reference Counting


• Data Types


• ...and Beyond the Infinite


• Why the Kernel Is Special


• Some Notes on Presentation


• Summary


• Chapter 2: Process Management and Scheduling


• Process Priorities


• Process Life Cycle


• Preemptive Multitasking


• Process Representation


• Process Types


• Namespaces


• Process Identification Numbers Contents


• Task Relationships


• Process Management System Calls


• Process Duplication


• Kernel Threads


• Starting New Programs


• Exiting Processes


• Implementation of the Scheduler


• Overview


• Data Structures


• Dealing with Priorities


• Core Scheduler


• The Completely Fair Scheduling Class


• Data Structures


• CFS Operations


• Queue Manipulation


• Selecting the Next Task


• Handling the Periodic Tick


• Wake-up Preemption


• Handling New Tasks


• The Real-Time Scheduling Class


• Properties


• Data Structures


• Scheduler Operations


• Scheduler Enhancements


• SMP Scheduling


• Scheduling Domains and Control Groups


• Kernel Preemption and Low Latency Efforts


• Summary


• Chapter 3: Memory Management


• Overview


• Organization in the (N)UMA Model


• Overview


• Data Structures


• Page Tables


• Data Structures


• Creating and Manipulating Entries


• Initialization of Memory Management


• Data Structure Setup


• Architecture-Specific Setup


• Memory Management during the Boot Process


• Management of Physical Memory Contents


• Structure of the Buddy System


• Avoiding Fragmentation


• Initializing the Zone and Node Data Structures


• Allocator API


• Reserving Pages


• Freeing Pages


• Allocation of Discontiguous Pages in the Kernel


• Kernel Mappings


• The Slab Allocator


• Alternative Allocators


• Memory Management in the Kernel


• The Principle of Slab Allocation


• Implementation


• General Caches


• Processor Cache and TLB Control


• Summary


• Chapter 4: Virtual Process Memory


• Introduction


• Virtual Process Address Space


• Layout of the Process Address Space


• Creating the Layout


• Principle of Memory Mappings


• Data Structures


• Trees and Lists


• Representation of Regions


• The Priority Search Tree


• Operations on Regions


• Associating Virtual Addresses with a Region


• Merging Regions


• Inserting Regions


• Creating Regions


• Address Spaces


• Memory Mappings


• Creating Mappings


• Removing Mappings


• Nonlinear Mappings


• Reverse Mapping


• Data Structures


• Creating a Reverse Mapping


• Using Reverse Mapping


• Managing the Heap Contents


• Handling of Page Faults


• Correction of Userspace Page Faults


• Demand Allocation/Paging


• Anonymous Pages


• Copy on Write


• Getting Nonlinear Mappings


• Kernel Page Faults


• Copying Data between Kernel and Userspace


• Summary


• Chapter 5: Locking and Interprocess Communication


• Control Mechanisms


• Race Conditions


• Critical Sections


• Kernel Locking Mechanisms


• Atomic Operations on Integers


• Spinlocks


• Semaphores


• The Read-Copy-Update Mechanism


• Memory and Optimization Barriers


• Reader/Writer Locks


• The Big Kernel Lock


• Mutexes


• Approximate Per-CPU Counters


• Lock Contention and Fine-Grained Locking


• System V Interprocess Communication


• System V Mechanisms


• Semaphores


• Message Queues


• Shared Memory


• Other IPC Mechanisms


• Signals


• Pipes and Sockets


• Summary


• Chapter 6: Device Drivers


• I/O Architecture


• Expansion Hardware


• Access to Devices


• Device Files


• Character, Block, and Other Devices


• Device Addressing Using Ioctls Contents


• Representation of Major and Minor Numbers


• Registration


• Association with the Filesystem


• Device File Elements in Inodes


• Standard File Operations


• Standard Operations for Character Devices


• Standard Operations for Block Devices


• Character Device Operations


• Representing Character Devices


• Opening Device Files


• Reading and Writing


• Block Device Operations


• Representation of Block Devices


• Data Structures


• Adding Disks and Partitions to the System


• Opening Block Device Files


• Request Structure


• BIOs


• Submitting Requests


• I/O Scheduling


• Implementation of Ioctls


• Resource Reservation


• Resource Management


• I/O Memory


• I/O Ports


• Bus Systems


• The Generic Driver Model


• The PCI Bus


• USB


• Summary


• Chapter 7: Modules


• Overview


• Using Modules


• Adding and Removing


• Dependencies


• Querying Module Information


• Automatic Loading


• Inserting and Deleting Modules


• Module Representation


• Dependencies and References


• Binary Structure of Modules Contents


• Inserting Modules


• Removing Modules


• Automation and Hotplugging


• Automatic Loading withkmod


• Hotplugging


• Version Control


• Checksum Methods


• Version Control Functions


• Summary


• Chapter 8: The Virtual Filesystem


• Filesystem Types


• The Common File Model


• Inodes


• Links


• Programming Interface


• Files as a Universal Interface


• Structure of the VFS


• Structural Overview


• Inodes


• Process-Specific Information


• File Operations


• Directory Entry Cache


• Working with VFS Objects


• Filesystem Operations


• File Operations


• Standard Functions


• Generic Read Routine


• ThefaultMechanism


• Permission-Checking


• Summary


• Chapter 9: The Extended Filesystem Family


• Introduction


• Second Extended Filesystem


• Physical Structure


• Data Structures


• Creating a Filesystem Contents


• Filesystem Actions


• Third Extended Filesystem


• Concepts


• Data Structures


• Summary


• Chapter 10: Filesystems without Persistent Storage


• TheprocFilesystem


• Contents of/proc


• Data Structures


• Initialization


• Mounting the Filesystem


• Managing/procEntries


• Reading and Writing Information


• Task-Related Information


• System Control Mechanism


• Simple Filesystems


• Sequential Files


• Writing Filesystems with Libfs


• The Debug Filesystem


• Pseudo Filesystems


• Sysfs


• Overview


• Data Structures


• Mounting the Filesystem


• File and Directory Operations


• Populating Sysfs


• Summary


• Chapter 11: Extended Attributes and Access Control Lists


• Extended Attributes


• Interface to the Virtual Filesystem


• Implementation in Ext3


• Implementation in Ext2


• Access Control Lists


• Generic Implementation


• Implementation in Ext3


• Implementation in Ext2


• Summary


• Chapter 12: Networks Contents


• Linked Computers


• ISO/OSI and TCP/IP Reference Model


• Communication via Sockets


• Creating a Socket


• Using Sockets


• Datagram Sockets


• The Layer Model of Network Implementation


• Networking Namespaces


• Socket Buffers


• Data Management Using Socket Buffers


• Management Data of Socket Buffers


• Network Access Layer


• Representation of Network Devices


• Receiving Packets


• Sending Packets


• Network Layer


• IPv4


• Receiving Packets


• Local Delivery to the Transport Layer


• Packet Forwarding


• Sending Packets


• Netfilter


• IPv6


• Transport Layer


• UDP


• TCP


• Application Layer


• Socket Data Structures


• Sockets and Files


• ThesocketcallSystem Call


• Creating Sockets


• Receiving Data


• Sending Data


• Networking from within the Kernel


• Communication Functions


• The Netlink Mechanism


• Summary