Contentsx856KernelDataStructuresLinked Lists85Singly and Doubly Linked Lists856Circular Linked Lists686Moving Through a Linked List87The LinuxKernel's Implementation88TheLinkedListStructure88Defining a Linked List 89ListHeads90Manipulating Linked Lists690Adding a Node to a Linked List90Deleting a Node froma Linked List91Moving and Splicing Linked List Nodes92Traversing Linked Lists93TheBasicApproach93TheUsableApproach9394Iterating Through a List BackwardIteratingWhileRemoving95Other Linked List Methods96Queues96kfifo9797Creatinga Queue98EnqueuingDataDequeuing Data98Obtaining the Size of a Queue98Resetting and Destroying the Queue9999ExampleQueueUsageMaps100Initializing an idr101101AllocatingaNewUIDLooking Up a UID102RemovingaUID103Destroying an idr103BinaryTrees103104BinarySearchTreesSelf-Balancing BinarySearch Trees105105Red-Black Trees6rbtrees106www.it-ebooks.info
ptg x Contents 6 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 92 Traversing Linked Lists 93 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 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 www.it-ebooks.info
ContentsxiWhatDataStructuretoUse,When108AlgorithmicComplexity109Algorithms109Big-0 Notation109Big Theta Notation 109TimeComplexity110Conclusion1117 Interrupts and InterruptHandlers113Interrupts113114InterruptHandlersTopHalvesVersusBottomHalves115Registering an Interrupt Handler 116InterruptHandlerFlags116AnInterruptExample117Freeingan InterruptHandler118Writing an Interrupt Handler 118SharedHandlers119A Real-Life Interrupt Handler120Interrupt Context122123ImplementingInterruptHandlers/proc/interrupts126InterruptControl 127Disabling and Enabling Interrupts127Disablinga Specific Interrupt Line129Statusof the Interrupt System130Conclusion 1311338BottomHalvesand Deferring WorkBottomHalves134WhyBottomHalves?134AWorldofBottomHalves135The Original"Bottom Half"135TaskQueues135SoftirsandTasklets136Dispellingthe Confusion 137www.it-ebooks.info
ptg Contents xi What Data Structure to Use, When 108 Algorithmic Complexity 109 Algorithms 109 Big-O Notation 109 Big Theta Notation 109 Time Complexity 110 Conclusion 111 7 Interrupts and Interrupt Handlers 113 Interrupts 113 Interrupt Handlers 114 Top Halves Versus Bottom Halves 115 Registering an Interrupt Handler 116 Interrupt Handler Flags 116 An Interrupt Example 117 Freeing an Interrupt Handler 118 Writing an Interrupt Handler 118 Shared Handlers 119 A Real-Life Interrupt Handler 120 Interrupt Context 122 Implementing Interrupt Handlers 123 /proc/interrupts 126 Interrupt Control 127 Disabling and Enabling Interrupts 127 Disabling a Specific Interrupt Line 129 Status of the Interrupt System 130 Conclusion 131 8 Bottom Halves and Deferring Work 133 Bottom Halves 134 Why Bottom Halves? 134 A World of Bottom Halves 135 The Original “Bottom Half” 135 Task Queues 135 Softirqs and Tasklets 136 Dispelling the Confusion 137 www.it-ebooks.info
xiiContentsSoftirqs137ImplementingSoftirqs137The Softirg Handler138Executing SoftirqsS138Using Softirqs140Assigning an Index140141RegisteringYourHandler141Raising Your Softirg142Tasklets142ImplementingTasklets142TheTaskletStructure143SchedulingTaskletsUsingTasklets 144Declaring Your Tasklet 144Writing Your Tasklet Handler 145SchedulingYourTasklet145ksoftirqd146TheOldBHMechanism148WorkQueues149149ImplementingWorkQueuesDataStructuresRepresentingtheThreads149DataStructuresRepresentingtheWork150152WorkQueueImplementationSummaryUsingWorkQueues153CreatingWork153Your Work Queue Handler153SchedulingWork153FlushingWork 154CreatingNewWorkQueues154155TheOldTaskQueueMechanismWhichBottomHalfShouldIUse?156LockingBetweentheBottomHalves157157DisablingBottomHalves6Conclusion1599 An Introductionto Kernel Synchronization1619Critical RegionsandRaceConditions162WhyDoWeNeedProtection?162TheSingleVariable163www.it-ebooks.info
ptg xii Contents Softirqs 137 Implementing Softirqs 137 The Softirq Handler 138 Executing Softirqs 138 Using Softirqs 140 Assigning an Index 140 Registering Your Handler 141 Raising Your Softirq 141 Tasklets 142 Implementing Tasklets 142 The Tasklet Structure 142 Scheduling Tasklets 143 Using Tasklets 144 Declaring Your Tasklet 144 Writing Your Tasklet Handler 145 Scheduling Your Tasklet 145 ksoftirqd 146 The Old BH Mechanism 148 Work Queues 149 Implementing Work Queues 149 Data Structures Representing the Threads 149 Data Structures Representing the Work 150 Work Queue Implementation Summary 152 Using Work Queues 153 Creating Work 153 Your Work Queue Handler 153 Scheduling Work 153 Flushing Work 154 Creating New Work Queues 154 The Old Task Queue Mechanism 155 Which Bottom Half Should I Use? 156 Locking Between the Bottom Halves 157 Disabling Bottom Halves 157 Conclusion 159 9 An Introduction to Kernel Synchronization 161 Critical Regions and Race Conditions 162 Why Do We Need Protection? 162 The Single Variable 163 www.it-ebooks.info
ContentsxiliLocking165Causesof Concurrency167Knowing What toProtect168Deadlocks169171Contention and ScalabilityConclusion17210KernelSynchronizationMethods175AtomicOperations6175176AtomicIntegerOperations64-BitAtomicOperations6180181AtomicBitwiseOperationsSpinLocks183Spin LockMethods184OtherSpinLockMethods186SpinLocksandBottomHalves187Reader-Writer Spin Locks188Semaphores190Countingand Binary Semaphores191Creating and Initializing Semaphores192UsingSemaphores193Reader-WriterSemaphores194Mutexes195197SemaphoresVersusMutexes197Spin Locks Versus MutexesCompletionVariables197BKL:The BigKernel Lock198Sequential Locks200PreemptionDisabling201Orderingand Barriers203Conclusion20611 Timers and Time Management207Kernel Notionof Time208TheTickRate:HZ208TheIdealHZValue210Advantages witha Larger HZ2210211Disadvantages witha LargerHZwww.it-ebooks.info
ptg Contents xiii Locking 165 Causes of Concurrency 167 Knowing What to Protect 168 Deadlocks 169 Contention and Scalability 171 Conclusion 172 10 Kernel Synchronization Methods 175 Atomic Operations 175 Atomic Integer Operations 176 64-Bit Atomic Operations 180 Atomic Bitwise Operations 181 Spin Locks 183 Spin Lock Methods 184 Other Spin Lock Methods 186 Spin Locks and Bottom Halves 187 Reader-Writer Spin Locks 188 Semaphores 190 Counting and Binary Semaphores 191 Creating and Initializing Semaphores 192 Using Semaphores 193 Reader-Writer Semaphores 194 Mutexes 195 Semaphores Versus Mutexes 197 Spin Locks Versus Mutexes 197 Completion Variables 197 BKL: The Big Kernel Lock 198 Sequential Locks 200 Preemption Disabling 201 Ordering and Barriers 203 Conclusion 206 11 Timers and Time Management 207 Kernel Notion of Time 208 The Tick Rate: HZ 208 The Ideal HZ Value 210 Advantages with a Larger HZ 210 Disadvantages with a Larger HZ 211 www.it-ebooks.info
ContentsxivJiffies212213InternalRepresentationofJiffiesJiffies Wraparound214216User-Space and HZ216HardwareClocksandTimersReal-Time Clock 217SystemTimer217The Timer Interrupt Handler217220The Time of DayTimers222222UsingTimers224TimerRaceConditions224TimerImplementationDelayingExecution：225Busy Looping225Small Delays226227schedule_timeout()schedule_timeout()Implementation228Sleeping on a Wait Queue,with a Timeout229Conclusion 23012MemoryManagement231Pages231Zones233235GettingPages236GettingZeroedPagesFreeingPages237238kmalloc()2gfp_maskFlags238Action Modifiers239ZoneModifiers240TypeFlags241kfree()243244vmalloc()SlabLayer245DesignoftheSlabLayer246www.it-ebooks.info
ptg xiv Contents Jiffies 212 Internal Representation of Jiffies 213 Jiffies Wraparound 214 User-Space and HZ 216 Hardware Clocks and Timers 216 Real-Time Clock 217 System Timer 217 The Timer Interrupt Handler 217 The Time of Day 220 Timers 222 Using Timers 222 Timer Race Conditions 224 Timer Implementation 224 Delaying Execution 225 Busy Looping 225 Small Delays 226 schedule_timeout() 227 schedule_timeout() Implementation 228 Sleeping on a Wait Queue, with a Timeout 229 Conclusion 230 12 Memory Management 231 Pages 231 Zones 233 Getting Pages 235 Getting Zeroed Pages 236 Freeing Pages 237 kmalloc() 238 gfp_mask Flags 238 Action Modifiers 239 Zone Modifiers 240 Type Flags 241 kfree() 243 vmalloc() 244 Slab Layer 245 Design of the Slab Layer 246 www.it-ebooks.info