Understanding the Linux Kernel, 3rd Edition

1 Understanding the Linux kernel , 3rd EditionBy Daniel P. Bovet, Marco : O'ReillyPub Date: November 2005 ISBN: 0-596-00565-2 Pages: 942 Table of Contents | IndexIn order to thoroughly understand what makes Linux tick and why it works so well on a wide variety ofsystems, you need to delve deep into the heart of the kernel . The kernel handles all interactions between theCPU and the external world, and determines which programs will share processor time, in what order. Itmanages limited memory so well that hundreds of processes can share the system efficiently, and expertlyorganizes data transfers so that the CPU isn't kept waiting any longer than necessary for the relatively third Edition of Understanding the Linux kernel takes you on a guided tour of the most significant datastructures, algorithms, and programming tricks used in the kernel . Probing beyond superficial features, theauthors offer valuable insights to people who want to know how things really work inside their Intel-specific features are discussed.

2 Relevant segments of code are dissected line by line. But thebook covers more than just the functioning of the code; it explains the theoretical underpinnings of whyLinux does things the way it Edition of the book covers Version , which has seen significant changes to nearly every kernelsubsystem, particularly in the areas of memory management and block devices. The book focuses on thefollowing topics:Memory management, including file buffering, process swapping, and Direct memory Access(DMA) The Virtual Filesystem layer and the Second and Third Extended Filesystems Process creation and scheduling Signals, interrupts, and the essential interfaces to device drivers Timing Synchronization within the kernel Interprocess Communication (IPC) Program execution Understanding the Linux kernel will acquaint you with all the inner workings of Linux , but it's more thanjust an academic exercise. You'll learn what conditions bring out Linux 's best performance, and you'll seehow it meets the challenge of providing good system response during process scheduling, file access, andmemory management in a wide variety of environments.

3 This book will help you make the most of yourLinux the Linux kernel , 3rd EditionBy Daniel P. Bovet, Marco : O'ReillyPub Date: November 2005 ISBN: 0-596-00565-2 Pages: 942 Table of Contents | IndexCopyrightPrefaceThe Audience for This BookOrganization of the MaterialLevel of DescriptionOverview of the BookBackground InformationConventions in This BookHow to Contact UsSafari EnabledAcknowledgments Chapter 1. IntroductionSection Linux Versus Other Unix-Like KernelsSection Hardware DependencySection Linux VersionsSection Basic Operating System ConceptsSection An Overview of the Unix FilesystemSection An Overview of Unix Kernels Chapter 2. Memory AddressingSection Memory AddressesSection Segmentation in HardwareSection Segmentation in LinuxSection Paging in HardwareSection Paging in Linux Chapter 3. ProcessesSection Processes, Lightweight Processes, and ThreadsSection Process DescriptorSection Process SwitchSection Creating ProcessesSection Destroying Processes Chapter 4.

4 Interrupts and ExceptionsSection The Role of Interrupt SignalsSection Interrupts and ExceptionsSection Nested Execution of Exception and Interrupt HandlersSection Initializing the Interrupt Descriptor TableSection Exception HandlingSection Interrupt HandlingSection Softirqs and TaskletsSection Work QueuesSection Returning from Interrupts and Exceptions Chapter 5. kernel SynchronizationSection How the kernel Services Requests11 Section Synchronization PrimitivesSection Synchronizing Accesses to kernel Data StructuresSection Examples of Race Condition Prevention Chapter 6. Timing MeasurementsSection Clock and Timer CircuitsSection The Linux Timekeeping ArchitectureSection Updating the Time and DateSection Updating System StatisticsSection Software Timers and Delay FunctionsSection System Calls Related to Timing Measurements Chapter 7. Process SchedulingSection Scheduling PolicySection The Scheduling AlgorithmSection Data Structures Used by the SchedulerSection Functions Used by the SchedulerSection Runqueue Balancing in Multiprocessor SystemsSection System Calls Related to Scheduling Chapter 8.

5 Memory ManagementSection Page Frame ManagementSection Memory Area ManagementSection Noncontiguous Memory Area Management Chapter 9. Process Address SpaceSection The Process's Address SpaceSection The Memory DescriptorSection Memory RegionsSection Page Fault Exception HandlerSection Creating and Deleting a Process Address SpaceSection Managing the Heap Chapter 10. System CallsSection POSIX APIs and System CallsSection System Call Handler and Service RoutinesSection Entering and Exiting a System CallSection Parameter PassingSection kernel Wrapper Routines Chapter 11. SignalsSection The Role of SignalsSection Generating a SignalSection Delivering a SignalSection System Calls Related to Signal Handling Chapter 12. The Virtual FilesystemSection The Role of the Virtual Filesystem (VFS)Section VFS Data StructuresSection Filesystem TypesSection Filesystem HandlingSection Pathname LookupSection Implementations of VFS System CallsSection File Locking Chapter 13.

6 I/O Architecture and Device DriversSection I/O ArchitectureSection The Device Driver ModelSection Device FilesSection Device DriversSection Character Device Drivers Chapter 14. Block Device Drivers22 Section Block Devices HandlingSection The Generic Block LayerSection The I/O SchedulerSection Block Device DriversSection Opening a Block Device File Chapter 15. The Page CacheSection The Page CacheSection Storing Blocks in the Page CacheSection Writing Dirty Pages to DiskSection The sync( ), fsync( ), and fdatasync( ) System Calls Chapter 16. Accessing FilesSection Reading and Writing a FileSection Memory MappingSection Direct I/O TransfersSection Asynchronous I/O Chapter 17. Page Frame ReclaimingSection The Page Frame Reclaiming AlgorithmSection Reverse MappingSection Implementing the PFRAS ection Swapping Chapter 18. The Ext2 and Ext3 FilesystemsSection General Characteristics of Ext2 Section Ext2 Disk Data StructuresSection Ext2 Memory Data StructuresSection Creating the Ext2 FilesystemSection Ext2 MethodsSection Managing Ext2 Disk SpaceSection The Ext3 Filesystem Chapter 19.

7 Process CommunicationSection PipesSection FIFOsSection System V IPCS ection POSIX Message Queues Chapter 20. Program ExZecutionSection Executable FilesSection Executable FormatsSection Execution DomainsSection The exec Functions Appendix A. System StartupSection Prehistoric Age: the BIOSS ection Ancient Age: the Boot LoaderSection Middle Ages: the setup( ) FunctionSection Renaissance: the startup_32( ) FunctionsSection Modern Age: the start_kernel( ) Function Appendix B. ModulesSection To Be (a Module) or Not to Be?Section Module ImplementationSection Linking and Unlinking ModulesSection Linking Modules on DemandBibliographyBooks on Unix KernelsBooks on the Linux KernelBooks on PC Architecture and Technical Manuals on Intel MicroprocessorsOther Online Documentation Sources33 Research Papers Related to Linux DevelopmentAbout the AuthorsColophonIndex44 Understanding the Linux kernel , Third Editionby Daniel P. Bovet and Marco CesatiCopyright 2006 O'Reilly Media, Inc.

8 All rights reserved. Printed in the United States of by O'Reilly Media, Inc., 1005 Gravenstein Highway North, Sebastopol, CA 'Reilly books may be purchased for educational, business, or sales promotional use. Online editions are alsoavailable for most titles ( ). For more information, contact our corporate/institutional salesdepartment: (800) 998-9938 or OramProduction Editor:Darren KellyProduction Services:Amy ParkerCover Designer:Edie FreedmanInterior Designer:David FutatoPrinting History:November 2000:First 2002:Second 2005:Third Handbook, the Nutshell Handbook logo, and the O'Reilly logo are registered trademarks of O'ReillyMedia, Inc. The Linux series designations, Understanding the Linux kernel , Third Edition , the image of aman with a bubble, and related trade dress are trademarks of O'Reilly Media, of the designations used by manufacturers and sellers to distinguish their products are claimed astrademarks. Where those designations appear in this book, and O'Reilly Media, Inc.

9 Was aware of a trademarkclaim, the designations have been printed in caps or initial every precaution has been taken in the preparation of this book, the publisher and authors assume noresponsibility for errors or omissions, or for damages resulting from the use of the information : 0-596-00565-2[M]1122 PrefaceIn the spring semester of 1997, we taught a course on operating systems based on Linux The idea was toencourage students to read the source code. To achieve this, we assigned term projects consisting of makingchanges to the kernel and performing tests on the modified version. We also wrote course notes for ourstudents about a few critical features of Linux such as task switching and task of this work and with a lot of support from our O'Reilly editor Andy Oram came the first Edition ofUnderstanding the Linux kernel at the end of 2000, which covered Linux with a few anticipations onLinux The success encountered by this book encouraged us to continue along this line. At the end of2002, we came out with a second Edition covering Linux You are now looking at the third Edition , whichcovers Linux in our previous experiences, we read thousands of lines of code, trying to make sense of them.

10 After allthis work, we can say that it was worth the effort. We learned a lot of things you don't find in books, and wehope we have succeeded in conveying some of this information in the following Audience for This BookAll people curious about how Linux works and why it is so efficient will find answers here. After reading thebook, you will find your way through the many thousands of lines of code, distinguishing between crucialdata structures and secondary onesin short, becoming a true Linux work might be considered a guided tour of the Linux kernel : most of the significant data structures andmany algorithms and programming tricks used in the kernel are discussed. In many cases, the relevantfragments of code are discussed line by line. Of course, you should have the Linux source code on hand andshould be willing to expend some effort deciphering some of the functions that are not, for sake of brevity,fully another level, the book provides valuable insight to people who want to know more about the criticaldesign issues in a modern operating system.