Linux Kernel Development (3rd Edition)

1 PtgLinux Kernel DevelopmentThird Edition s LibraryESSENTIAL REFERENCES FOR PROGRAMMING PROFESSIONALSD eveloper s Library books are designed to provide practicing programmers with unique, high-quality references and tutorials on the programming languages and technologies they use in their daily books in the Developer s Library are written by expert technology practitioners who are especially skilled at organizing and presenting information in a way that s useful for other titles include some of the best, most widely acclaimed books within their topic areas:PHP & MySQL Web Development Luke Welling & Laura Thomson ISBN 978-0-672-32916-6 MySQL Paul DuBois ISBN-13: 978-0-672-32938-8 Linux Kernel Development Robert Love ISBN-13: 978-0-672-32946-3 Python Essential Reference David Beazley ISBN-13: 978-0-672-32978-6 Programming in Objective-C Stephen G.

2 Kochan ISBN-13: 978-0-321-56615-7 PostgreSQL Korry Douglas ISBN-13: 978-0-672-33015-5 Developer s Library books are available at most retail and online bookstores, as well as by subscription from Safari Books Online at s Library ptgLinux Kernel DevelopmentThird EditionRobert LoveUpper Saddle River, NJ Boston Indianapolis San Francisco New York Toronto Montreal London Munich Paris Madrid Cape Town Sydney Tokyo Singapore Mexico City ptgLinux Kernel Development Third EditionCopyright 2010 Pearson Education, rights reserved. Printed in the United States of America. This publication is protected bycopyright, and permission must be obtained from the publisher prior to any prohibited repro-duction, storage in a retrieval system, or transmission in any form or by any means, elec-tronic, mechanical, photocopying, recording, or : 978-0-672-32946-3 ISBN-10: 0-672-32946-8 Library of Congress Cataloging-in-Publication Data: Love, Kernel Development / Robert Love.

3 3rd bibliographical references and 978-0-672-32946-3 (pbk. : alk. paper) 1. Linux . 2. Operating systems (Computers)I. Title. 32 dc222010018961 Te x t p r i n t e d i n t h e U n i t e d S t a t e s o n r e c y c l e d p a p e r a t R R D o n n e l l ey, C r aw f o r d s v i l l e , I n d i a n a .First printing June 2010 Many of the designations used by manufacturers and sellers to distinguish their productsare claimed as trademarks. Where those designations appear in this book, and the publish-er was aware of a trademark claim, the designations have been printed with initial capitalletters or in all author and publisher have taken care in the preparation of this book, but make noexpressed or implied warranty of any kind and assume no responsibility for errors or omis-sions.

4 No liability is assumed for incidental or consequential damages in connection with orarising out of the use of the information or programs contained publisher offers excellent discounts on this book when ordered in quantity for bulk pur-chases or special sales, which may include electronic versions and/or custom covers andcontent particular to your business, training goals, marketing focus, and branding more information, please contact: Corporate and Government Sales(800) For sales outside the United States please contact: International Visit us on the Web: EditorMark Taber DevelopmentEditorMichael Thurston Technical EditorRobert P.

5 J. Day Managing EditorSandra Schroeder Senior ProjectEditorTo nya S i m p s o n Copy EditorApostrophe EditingServices IndexerBrad Herriman ProofreaderDebbie Williams PublishingCoordinatorVanessa Evans Book DesignerGary Adair CompositorMark Shirar ptg For Doris and Helen. ptgContents at a Glance1 Introduction to the Linux Kernel 12 Getting Started with the Kernel 113 Process Management 234 Process Scheduling 415 System Calls 696 Kernel Data Structures 857 interrupts and Interrupt Handlers 1138 Bottom Halves and Deferring Work 1339An Introduction to Kernel Synchronization 16110 Kernel Synchronization Methods 17511 Timers and Time Management 20712 Memory Management 23113 The Virtual Filesystem 26114 The Block I/O Layer 28915 The Process Address Space 30516 The Page Cache and Page Writeback 32317 Devices and Modules 33718 Debugging 36319 Portability 37920 Patches, Hacking.

6 And the Community 395 Bibliography 407 Index 411 ptgTable of Contents1 Introduction to the Linux Kernel 1 History of Unix 1 Along Came Linus: Introduction to Linux 3 Overview of Operating Systems and Kernels 4 Linux Versus Classic Unix Kernels 6 Linux Kernel Versions 8 The Linux Kernel Development Community 10 Before We Begin 102 Getting Started with the Kernel 11 Obtaining the Kernel Source 11 Using Git 11 Installing the Kernel Source 12 Using Patches 12 The Kernel Source Tree 12 Building the Kernel 13 Configuring the Kernel 14 Minimizing Build Noise 15 Spawning Multiple Build Jobs 16 Installing the New Kernel 16A Beast of a Different Nature 16No libc or Standard Headers 17 GNU C 18 Inline

7 Functions 18 Inline Assembly 19 Branch Annotation 19No Memory Protection 20No (Easy) Use of Floating Point 20 Small, Fixed-Size Stack 20 Synchronization and Concurrency 21 Importance of Portability 21 Conclusion 21 ptgviii Contents3 Process Management 23 The Process 23 Process Descriptor and the Task Structure 24 Allocating the Process Descriptor 25 Storing the Process Descriptor 26 Process State 27 Manipulating the Current Process State 29 Process Context 29 The Process Family Tree 29 Process Creation 31 Copy-on-Write 31 Forking 32 vfork() 33 The Linux Implementation of Threads 33 Creating Threads 34 Kernel Threads 35 Process Termination 36 Removing the Process Descriptor 37 The Dilemma of the Parentless Task 38 Conclusion 404 Process Scheduling 41 Multitasking 41 Linux s Process Scheduler 42 Policy 43I/O-Bound Versus Processor-Bound Processes 43 Process Priority 44 Timeslice 45 The Scheduling Policy in Action 45 The Linux Scheduling Algorithm 46 Scheduler Classes 46 Process Scheduling in Unix Systems 47 Fair Scheduling 48 The Linux Scheduling Implementation 50 Time Accounting 50 The

8 Scheduler Entity Structure 50 The Virtual Runtime 51 ptgixContentsProcess Selection 52 Picking the Next Task 53 Adding Processes to the Tree 54 Removing Processes from the Tree 56 The Scheduler Entry Point 57 Sleeping and Waking Up 58 Wait Queues 58 Waking Up 61 Preemption and Context Switching 62 User Preemption 62 Kernel Preemption 63 Real-Time Scheduling Policies 64 Scheduler-Related System Calls 65 Scheduling Policy and Priority-Related System Calls 66 Processor Affinity System Calls 66 Yielding Processor Time 66 Conclusion 675 System Calls 69 Communicating with the Kernel 69 APIs, POSIX.

9 And the C Library 70 Syscalls 71 System Call Numbers 72 System Call Performance 72 System Call Handler 73 Denoting the Correct System Call 73 Parameter Passing 74 System Call Implementation 74 Implementing System Calls 74 Verifying the Parameters 75 System Call Context 78 Final Steps in Binding a System Call 79 Accessing the System Call from User-Space 81 Why Not to Implement a System Call 82 Conclusion 83 ptgx Contents6 Kernel Data Structures 85 Linked Lists 85 Singly and Doubly Linked Lists 85 Circular Linked Lists 86 Moving Through a Linked List 87 The Linux Kernel s Implementation 88 The Linked List Structure 88 Defining a Linked List 89 List Heads 90 Manipulating Linked Lists 90 Adding a Node to a Linked List 90 Deleting a Node from a Linked List 91 Moving and Splicing Linked List Nodes 92Tr av e r s i n g L i n ke d L i s t s 9 3 The Basic Approach 93 The Usable Approach 93 Iterating Through a List Backward 94 Iterating While Removing 95 Other Linked List Methods 96 Queues 96 kfifo 97 Creating a Queue 97 Enqueuing Data 98 Dequeuing Data 98 Obtaining the Size of a Queue 98 Resetting and

10 Destroying the Queue 99 Example Queue Usage 99 Maps 100 Initializing an idr 101 Allocating a New UID 101 Looking Up a UID 102 Removing a UID 103 Destroying an idr 103 Binary Trees 103 Binary Search Trees 104 Self-Balancing Binary Search Trees 105 Red-Black Trees 105 rbtrees 106 ptgxiContentsWhat Data Structure to Use, When 108 Algorithmic Complexity 109 Algorithms 109 Big-O Notation 109 Big Theta Notation 109 Time Complexity 110 Conclusion 1117 interrupts and Interrupt Handlers 113 interrupts 113 Interrupt Handlers 114 To p H a l v e s Ve r s u s B o t t o m H a l v e s 1 1 5 Registering an Interrupt Handler 116 Interrupt Handler Flags 116An Interrupt Example 117 Freeing an Interrupt Handler 118 Writing an Interrupt Handler 118 Shared Handlers 119A Real-Life Interrupt Handler 120 Interrupt Context 122 Implementing Interrupt Handlers 123 /proc/ interrupts 126