Understanding the Linux Kernel, 2nd Edition

1 I l@ve RuBoard Table of Contents Index Reviews Reader Reviews ErrataUnderstanding the Linux kernel , 2nd EditionBy Daniel P. Bovet, Marco Cesati Publisher: O'ReillyPub Date: December 2002 ISBN: 0-596-00213-0 Pages: 784 The new Edition of Understanding the Linux kernel takes you on a guided tour through the most significant data structures, many algorithms, and programming tricks used in the kernel . The book has been updated to cover version of the kernel , which is quite different from version : the virtual memory system is entirely new, support for multiprocessor systems is improved, and whole new classes of hardware devices have been added. You'll learn what conditions bring out Linux 's best performance, and how it meets the challenge of providing good system response during process scheduling, file access, and memory management in a wide variety of environments.

2 I l@ve RuBoard I l@ve RuBoard Table of Contents Index Reviews Reader Reviews ErrataUnderstanding the Linux kernel , 2nd EditionBy Daniel P. Bovet, Marco Cesati Publisher: O'ReillyPub Date: December 2002 ISBN: 0-596-00213-0 Pages: 784 Copyright Preface The Audience for This Book Organization of the Material Overview of the Book Background Information Conventions in This Book How to Contact Us Acknowledgments Chapter 1. Introduction Section Linux Versus Other Unix-Like Kernels Section Hardware Dependency Section Linux Versions Section Basic Operating System Concepts Section An Overview of the Unix Filesystem Section An Overview of Unix Kernels Chapter 2. Memory Addressing Section Memory Addresses Section Segmentation in Hardware Section Segmentation in Linux Section Paging in Hardware Section Paging in Linux Chapter 3.

3 Processes Section Processes, Lightweight Processes, and Threads Section Process Descriptor Section Process Switch Section Creating Processes Section Destroying Processes Chapter 4. Interrupts and Exceptions Section The Role of Interrupt Signals Section Interrupts and Exceptions Section Nested Execution of Exception and Interrupt Handlers Section Initializing the Interrupt Descriptor Table Section Exception Handling Section Interrupt Handling Section Softirqs, Tasklets, and Bottom Halves Section Returning from Interrupts and Exceptions Chapter 5. kernel Synchronization Section kernel Control Paths Section When Synchronization Is Not Necessary Section Synchronization Primitives Section Synchronizing Accesses to kernel Data Structures Section Examples of Race Condition Prevention Chapter 6.

4 Timing Measurements Section Hardware Clocks Section The Linux Timekeeping Architecture Section CPU's Time Sharing Section Updating the Time and Date Section Updating System Statistics Section Software Timers Section System Calls Related to Timing Measurements Chapter 7. Memory Management Section Page Frame Management Section Memory Area Management Section Noncontiguous Memory Area Management Chapter 8. Process Address Space Section The Process's Address Space Section The Memory Descriptor Section Memory Regions Section Page Fault Exception Handler Section Creating and Deleting a Process Address Space Section Managing the Heap Chapter 9. System Calls Section POSIX APIs and System Calls Section System Call Handler and Service Routines Section kernel Wrapper Routines Chapter 10.

5 Signals Section The Role of Signals Section Generating a Signal Section Delivering a Signal Section System Calls Related to Signal Handling Chapter 11. Process Scheduling Section Scheduling Policy Section The Scheduling Algorithm Section System Calls Related to Scheduling Chapter 12. The Virtual Filesystem Section The Role of the Virtual Filesystem (VFS) Section VFS Data Structures Section Filesystem Types Section Filesystem Mounting Section Pathname Lookup Section Implementations of VFS System Calls Section File Locking Chapter 13. Managing I/O Devices Section I/O Architecture Section Device Files Section Device Drivers Section Block Device Drivers Section Character Device Drivers Chapter 14. Disk Caches Section The Page Cache Section The Buffer Cache Chapter 15.

6 Accessing Files Section Reading and Writing a File Section Memory Mapping Section Direct I/O Transfers Chapter 16. Swapping: Methods for Freeing Memory Section What Is Swapping? Section Swap Area Section The Swap Cache Section Transferring Swap Pages Section Swapping Out Pages Section Swapping in Pages Section Reclaiming Page Frame Chapter 17. The Ext2 and Ext3 Filesystems Section General Characteristics of Ext2 Section Ext2 Disk Data Structures Section Ext2 Memory Data Structures Section Creating the Ext2 Filesystem Section Ext2 Methods Section Managing Ext2 Disk Space Section The Ext3 Filesystem Chapter 18. Networking Section Main Networking Data Structures Section System Calls Related to Networking Section Sending Packets to the Network Card Section Receiving Packets from the Network Card Chapter 19.

7 Process Communication Section Pipes Section FIFOs Section System V IPC Chapter 20. Program Execution Section Executable Files Section Executable Formats Section Execution Domains Section The exec Functions Appendix A. System Startup Section Prehistoric Age: The BIOS Section Ancient Age: The Boot Loader Section Middle Ages: The setup( ) Function Section Renaissance: The startup_32( ) Functions Section Modern Age: The start_kernel( ) Function Appendix B. Modules Section To Be (a Module) or Not to Be? Section Module Implementation Section Linking and Unlinking Modules Section Linking Modules on Demand Appendix C. Source Code Structure Bibliography Books on Unix Kernels Books on the Linux kernel Books on PC Architecture and Technical Manuals on Intel Microprocessors Other Online Documentation Sources Colophon IndexI l@ve RuBoard I l@ve RuBoard CopyrightCopyright 2003 O'Reilly & Associates, Inc.

8 Printed in the United States of by O'Reilly & Associates, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 'Reilly & Associates books may be purchased for educational, business, or sales promotional use. Online editions are also available for most titles ( ). For more information, contact our corporate/institutional sales department: (800) 998-9938 or Handbook, the Nutshell Handbook logo, and the O'Reilly logo are registered trademarks of O'Reilly & Associates, Inc. Many of the designations used by manufacturers and sellers to distinguish their products are claimed as trademarks. Where those designations appear in this book, and O'Reilly & Associates, Inc. was aware of a trademark claim, the designations have been printed in caps or initial caps. The association between the images of the American West and the topic of Linux is a trademark of O'Reilly & Associates, every precaution has been taken in the preparation of this book, the publisher and authors assume no responsibility for errors or omissions, or for damages resulting from the use of the information contained l@ve RuBoard I l@ve RuBoard PrefaceIn the spring semester of 1997, we taught a course on operating systems based on Linux The idea was to encourage students to read the source code.

9 To achieve this, we assigned term projects consisting of making changes to the kernel and performing tests on the modified version. We also wrote course notes for our students about a few critical features of Linux such as task switching and task scheduling. Out of this work and with a lot of support from our O'Reilly editor Andy Oram came the first Edition of Understanding the Linux kernel and the end of 2000, which covered Linux with a few anticipations on Linux The success encountered by this book encouraged us to continue along this line, and in the fall of 2001 we started planning a second Edition covering Linux However, Linux is quite different from Linux Just to mention a few examples, the virtual memory system is entirely new, support for multiprocessor systems is much better, and whole new classes of hardware devices have been added.

10 As a result, we had to rewrite from scratch two-thirds of the book, increasing its size by roughly 25 percent. As in our first experience, we read thousands of lines of code, trying to make sense of them. After all this work, we can say that it was worth the effort. We learned a lot of things you don't find in books, and we hope we have succeeded in conveying some of this information in the following pages. I l@ve RuBoard I l@ve RuBoard The Audience for This BookAll people curious about how Linux works and why it is so efficient will find answers here. After reading the book, you will find your way through the many thousands of lines of code, distinguishing between crucial data structures and secondary ones in short, becoming a true Linux hacker. Our work might be considered a guided tour of the Linux kernel : most of the significant data structures and many algorithms and programming tricks used in the kernel are discussed.