Understanding the Linux Kernel
Understanding the Linux Kernel Daniel P. Bovet Marco Cesati Publisher: O’Reilly First Edition October 2000. ISBN: 0-596-00002-2, 702 pages Understanding the Linux Kernel helps readers understand how Linux performs best and how it meets the challenge of different environments. The authors introduce each topic by explaining its importance, and show how Kernel operations relate to the utilities that are familiar to Unix programmers and users. Table of Contents Preface .. 1. The Audience for This Book .. 1. Organization of the Material .. 1. Overview of the Book .. 3. Background Information .. 4. Conventions in This Book .. 4. How to Contact Us .. 4. Acknowledgments .. 5. 1. Introduction .. 6. Linux Versus Other Unix-Like Kernels .. 6. Hardware Dependency .. 10. Linux Versions .. 11. Basic Operating System Concepts .. 12. An Overview of the Unix Filesystem.
Understanding the Linux Kernel helps readers understand how Linux performs best and how it meets the challenge of different environments. The authors introduce each topic by explaining its importance, and show how kernel operations relate to the utilities that are
Tags:
Information
Link to this page:
Please notify us if you found a problem with this document:
Thank you for your participation!
Thank you for your participation!
Transcription of Understanding the Linux Kernel
1 Understanding the Linux Kernel Daniel P. Bovet Marco Cesati Publisher: O’Reilly First Edition October 2000. ISBN: 0-596-00002-2, 702 pages Understanding the Linux Kernel helps readers understand how Linux performs best and how it meets the challenge of different environments. The authors introduce each topic by explaining its importance, and show how Kernel operations relate to the utilities that are familiar to Unix programmers and users. Table of Contents Preface .. 1. The Audience for This Book .. 1. Organization of the Material .. 1. Overview of the Book .. 3. Background Information .. 4. Conventions in This Book .. 4. How to Contact Us .. 4. Acknowledgments .. 5. 1. Introduction .. 6. Linux Versus Other Unix-Like Kernels .. 6. Hardware Dependency .. 10. Linux Versions .. 11. Basic Operating System Concepts .. 12. An Overview of the Unix Filesystem.
2 16. An Overview of Unix Kernels .. 22. 2. Memory Addressing .. 36. Memory Addresses .. 36. Segmentation in Hardware .. 37. Segmentation in Linux .. 41. Paging in Hardware .. 44. Paging in Linux .. 52. Anticipating Linux .. 63. 3. Processes .. 64. Process Descriptor .. 64. Process Switching .. 78. Creating Processes .. 86. Destroying Processes .. 93. Anticipating Linux .. 94. 4. Interrupts and Exceptions .. 96. The Role of Interrupt Signals .. 96. Interrupts and Exceptions .. 97. Nested Execution of Exception and Interrupt Handlers .. 106. Initializing the Interrupt Descriptor Table .. 107. Exception Handling .. 109. Interrupt Handling .. 112. Returning from Interrupts and Exceptions .. 126. Anticipating Linux .. 129. 5. Timing Measurements .. 131. Hardware Clocks .. 131. The Timer Interrupt Handler .. 133. PIT’s Interrupt Service Routine .. 134. The TIMER_BH Bottom Half Functions.
3 136. System Calls Related to Timing Measurements .. 145. Anticipating Linux .. 148. 6. Memory Management .. 149. Page Frame Management .. 149. Memory Area Management .. 160. Noncontiguous Memory Area Management .. 176. Anticipating Linux .. 181. 7. Process Address Space .. 183. The Process’s Address Space .. 183. The Memory Descriptor .. 185. Memory Regions .. 186. Page Fault Exception Handler .. 201. Creating and Deleting a Process Address Space .. 212. Managing the Heap .. 214. Anticipating Linux .. 216. 8. System Calls .. 217. POSIX APIs and System Calls .. 217. System Call Handler and Service Routines .. 218. Wrapper Routines .. 229. Anticipating Linux .. 230. 9. Signals .. 231. The Role of Signals .. 231. Sending a Signal .. 239. Receiving a Signal .. 242. Real-Time Signals .. 251. System Calls Related to Signal Handling .. 252. Anticipating Linux .
4 257. 10. Process Scheduling .. 258. Scheduling Policy .. 258. The Scheduling Algorithm .. 261. System Calls Related to Scheduling .. 272. Anticipating Linux .. 276. 11. Kernel Synchronization .. 277. Kernel Control Paths .. 277. Synchronization Techniques .. 278. The SMP Architecture .. 286. The Linux /SMP Kernel .. 290. Anticipating Linux .. 302. 12. The Virtual Filesystem .. 303. The Role of the VFS .. 303. VFS Data Structures .. 308. Filesystem Mounting .. 324. Pathname Lookup .. 329. Implementations of VFS System Calls .. 333. File Locking .. 337. Anticipating Linux .. 342. 13. Managing I/O Devices .. 343. I/O Architecture .. 343. Associating Files with I/O Devices .. 348. Device Drivers .. 353. Character Device Handling .. 360. Block Device Handling .. 361. Page I/O Operations .. 377. Anticipating Linux .. 380. 14. Disk Caches .. 382. The Buffer Cache.
5 383. The Page Cache .. 396. Anticipating Linux .. 398. 15. Accessing Regular Files .. 400. Reading and Writing a Regular File .. 400. Memory Mapping .. 408. Anticipating Linux .. 416. 16. Swapping: Methods for Freeing Memory .. 417. What Is Swapping? .. 417. Swap Area .. 420. The Swap Cache .. 429. Transferring Swap Pages .. 433. Page Swap-Out .. 437. Page Swap-In .. 442. Freeing Page Frames .. 444. Anticipating Linux .. 450. 17. The Ext2 Filesystem .. 451. General Characteristics .. 451. Disk Data Structures .. 453. Memory Data Structures .. 459. Creating the Filesystem .. 463. Ext2 Methods .. 464. Managing Disk Space .. 466. Reading and Writing an Ext2 Regular File .. 473. Anticipating Linux .. 475. 18. Process Communication .. 476. Pipes .. 477. FIFOs .. 483. System V IPC .. 486. Anticipating Linux .. 499. 19. Program Execution .. 500. Executable Files.
6 500. Executable Formats .. 512. Execution Domains .. 514. The exec-like Functions .. 515. Anticipating Linux .. 519. A. System Startup .. 520. Prehistoric Age: The BIOS .. 520. Ancient Age: The Boot Loader .. 521. Middle Ages: The setup( ) Function .. 523. Renaissance: The startup_32( ) Functions .. 523. Modern Age: The start_kernel( ) Function .. 524. B. Modules .. 526. To Be (a Module) or Not to Be? .. 526. Module Implementation .. 527. Linking and Unlinking Modules .. 529. Linking Modules on Demand .. 531. C. Source Code Structure .. 533. Colophon .. 536. Understanding the Linux Kernel Preface In 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. To achieve this, we assigned term projects consisting of making changes to the Kernel and performing tests on the modified version.
7 We also wrote course notes for our students about a few critical features of Linux like task switching and task scheduling. We continued along this line in the spring semester of 1998, but we moved on to the Linux development version. Our course notes were becoming larger and larger. In July, 1998 we contacted O’Reilly & Associates, suggesting they publish a whole book on the Linux Kernel . The real work started in the fall of 1998 and lasted about a year and a half. 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. The Audience for This Book All people curious about how Linux works and why it is so efficient will find answers here.
8 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; in many cases, the relevant fragments of code are discussed line by line. Of course, you should have the Linux source code on hand and should be willing to spend some effort deciphering some of the functions that are not, for sake of brevity, fully described. On another level, the book will give valuable insights to people who want to know more about the critical design issues in a modern operating system. It is not specifically addressed to system administrators or programmers; it is mostly for people who want to understand how things really work inside the machine!
9 Like any good guide, we try to go beyond superficial features. We offer background, such as the history of major features and the reasons they were used. Organization of the Material When starting to write this book, we were faced with a critical decision: should we refer to a specific hardware platform or skip the hardware-dependent details and concentrate on the pure hardware-independent parts of the Kernel ? Others books on Linux Kernel internals have chosen the latter approach; we decided to adopt the former one for the following reasons: Efficient kernels take advantage of most available hardware features, such as addressing techniques, caches, processor exceptions, special instructions, processor control registers, and so on. If we want to convince you that the Kernel indeed does 1. Understanding the Linux Kernel quite a good job in performing a specific task, we must first tell what kind of support comes from the hardware.
10 Even if a large portion of a Unix Kernel source code is processor-independent and coded in C language, a small and critical part is coded in assembly language. A. thorough knowledge of the Kernel thus requires the study of a few assembly language fragments that interact with the hardware. When covering hardware features, our strategy will be quite simple: just sketch the features that are totally hardware-driven while detailing those that need some software support. In fact, we are interested in Kernel design rather than in computer architecture. The next step consisted of selecting the computer system to be described: although Linux is now running on several kinds of personal computers and workstations, we decided to concentrate on the very popular and cheap IBM-compatible personal computers thus, on the Intel 80×86 microprocessors and on some support chips included in these personal computers.
Understanding the Linux Kernel
, 702 pages Understanding the Linux Kernel helps readers understand how Linux performs best and how it meets the challenge of different environments. The authors introduce each topic by explaining its importance, and show how kernel operations relate to the utilities that are familiar to Unix programmers and users.
Related Papers
Download Free PDF View PDF
An operating system mediates among application programs, utilities, and users, on the one hand, and the computer system hardware on the other. To appreciate the functionality of the operating system and the design issues involved, one must have some appreciation for computer organization and architecture. Chapter 1 provides a brief survey of the processor, memory, and Input/Output (I/O) elements of a computer system. The topic of operating system (OS) design covers a huge territory, and it is easy to get lost in the details and lose the context of a discussion of a particular issue. Chapter 2 provides an overview to which the reader can return at any point in the book for context. We begin with a statement of the objectives and functions of an operating system. Then some historically important systems and OS functions are described. This discussion allows us to present some fundamental OS design principles in a simple environment so that the relationship among various OS functions is clear. The chapter next highlights important characteristics of modern operating systems. Throughout the book, as various topics are discussed, it is necessary to talk about both fundamental, well-established principles as well as more recent innovations in OS design. The discussion in this chapter alerts the reader to this blend of established and recent design approaches that must be addressed. Finally, we present an overview of Windows, UNIX, and Linux; this discussion establishes the general architecture of these systems, providing context for the detailed discussions to follow.
Download Free PDF View PDF