For Computer Systems, Computer Organization and Architecture courses in CS, EE, and ECE departments. Few students studying computer science or computer engineering will ever have the opportunity to build a computer system. On the other hand, most students will be required to use and program computers on a near daily basis. Computer Systems: A Programmer’s Perspective introduces the important and enduring concepts that underlie computer systems by showing how these ideas affect the correctness, performance, and utility of application programs. The text's hands-on approach (including a comprehensive set of labs) helps students understand the “under-the-hood” operation of a modern computer system and prepares them for future courses in systems topics such as compilers, computer architecture, operating systems, and networking. Visit the CSS:AP web page http://csapp.cs.cmu.edu for more information and resources.

Table of Contents:
Contents Preface xv 1 A Tour of Computer Systems 1 1.1 Information is Bits + Context . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 Programs Are Translated by Other Programs into Different Forms . . . . . . . . . . . . . . 3 1.3 It Pays to Understand How Compilation Systems Work . . . . . . . . . . . . . . . . . . . . 5 1.4 Processors Read and Interpret Instructions Stored in Memory . . . . . . . . . . . . . . . . . 6 1.4.1 Hardware Organization of a System . . . . . . . . . . . . . . . . . . . . . . . . . . 6 1.4.2 Running the hello Program . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.5 Caches Matter . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.6 Storage Devices Form a Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.7 The Operating System Manages the Hardware . . . . . . . . . . . . . . . . . . . . . . . . . 12 1.7.1 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.7.2 Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.7.3 Virtual Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.7.4 Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 1.8 Systems Communicate With Other Systems Using Networks . . . . . . . . . . . . . . . . . 17 1.9 Important Themes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.9.1 Concurrency and Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.9.2 The Importance of Abstractions in Computer Systems . . . . . . . . . . . . . . . . 22 1.10 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 I Program Structure and Execution 25 2 Representing and Manipulating Information 29 2.1 Information Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.1.1 Hexadecimal Notation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.1.2 Words . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.1.3 Data Sizes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.1.4 Addressing and Byte Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.1.5 Representing Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.1.6 Representing Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.1.7 Introduction to Boolean Algebra . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.1.8 Bit-Level Operations in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.1.9 Logical Operations in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50 2.1.10 Shift Operations in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 2.2 Integer Representations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.1 Integral Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 2.2.2 Unsigned Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54 2.2.3 Two’s Complement Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 2.2.4 Conversions Between Signed and Unsigned . . . . . . . . . . . . . . . . . . . . . . 61 2.2.5 Signed vs. Unsigned in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 2.2.6 Expanding the Bit Representation of a Number . . . . . . . . . . . . . . . . . . . . 67 2.2.7 Truncating Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 2.2.8 Advice on Signed vs. Unsigned . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 2.3 Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.3.1 Unsigned Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 2.3.2 Two’s-Complement Addition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 2.3.3 Two’s-Complement Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 2.3.4 Unsigned Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.3.5 Two’s-Complement Multiplication . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 2.3.6 Multiplying by Constants . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 2.3.7 Dividing by Powers of Two . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 2.3.8 Final Thoughts on Integer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 93 2.4 Floating Point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 2.4.1 Fractional Binary Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 2.4.2 IEEE Floating-Point Representation . . . . . . . . . . . . . . . . . . . . . . . . . . 97 2.4.3 Example Numbers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 2.4.4 Rounding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 2.4.5 Floating-Point Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 2.4.6 Floating Point in C . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 108 2.5 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110 3 Machine-Level Representation of Programs 145 3.1 A Historical Perspective . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147 3.2 Program Encodings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 3.2.1 Machine-Level Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151 3.2.2 Code Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 152 3.2.3 Notes on Formatting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 3.3 Data Formats . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 3.4 Accessing Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 158 3.4.1 Operand Specifiers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 3.4.2 Data Movement Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160 3.4.3 Data Movement Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164 3.5 Arithmetic and Logical Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 166 3.5.1 Load Effective Address . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 167 3.5.2 Unary and Binary Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 168 3.5.3 Shift Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 3.5.4 Discussion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 169 3.5.5 Special Arithmetic Operations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 3.6 Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 173 3.6.1 Condition Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 174 3.6.2 Accessing the Condition Codes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 175 3.6.3 Jump Instructions and their Encodings . . . . . . . . . . . . . . . . . . . . . . . . . 177 3.6.4 Translating Conditional Branches . . . . . . . . . . . . . . . . . . . . . . . . . . . 181 3.6.5 Loops . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 184 3.6.6 Conditional Move Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 194 3.6.7 Switch Statements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 203 3.7 Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 3.7.1 Stack Frame Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 3.7.2 Transferring Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 208 3.7.3 Register Usage Conventions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 210 3.7.4 Procedure Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211 3.7.5 Recursive Procedures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 3.8 Array Allocation and Access . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 3.8.1 Basic Principles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 3.8.2 Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220 3.8.3 Nested Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 221 3.8.4 Fixed-Size Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 3.8.5 Variable-Size Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 225 3.9 Heterogeneous Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 3.9.1 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227 3.9.2 Unions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 3.9.3 Data Alignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234 3.10 Putting it Together: Understanding Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . 237 3.11 Life in the Real World: Using the GDB Debugger . . . . . . . . . . . . . . . . . . . . . . . 239 3.12 Out-of-Bounds Memory References and Buffer Overflow . . . . . . . . . . . . . . . . . . . 241 3.12.1 Thwarting Buffer Overflow Attacks . . . . . . . . . . . . . . . . . . . . . . . . . . 246 3.13 x86-64: Extending IA32 to 64 Bits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 251 3.13.1 History and Motivation for x86-64 . . . . . . . . . . . . . . . . . . . . . . . . . . . 252 3.13.2 An Overview of x86-64 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 253 3.13.3 Accessing Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 256 3.13.4 Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 262 3.13.5 Data Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 3.13.6 Concluding Observations about x86-64 . . . . . . . . . . . . . . . . . . . . . . . . 274 3.14 Machine-Level Representations of Floating-Point Programs . . . . . . . . . . . . . . . . . . 274 3.15 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 275 4 Processor Architecture 317 4.1 The Y86 Instruction Set Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 319 4.1.1 Programmer-Visible State . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 4.1.2 Y86 Instructions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 4.1.3 Instruction Encoding . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 322 4.1.4 Y86 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 326 4.1.5 Y86 Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 4.1.6 Some Y86 Instruction Details . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 332 4.2 Logic Design and the Hardware Control Language HCL . . . . . . . . . . . . . . . . . . . 334 4.2.1 Logic Gates . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 335 4.2.2 Combinational Circuits and HCL Boolean Expressions . . . . . . . . . . . . . . . . 335 4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions . . . . . . . . . . 337 4.2.4 Set Membership . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 341 4.2.5 Memory and Clocking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 342 4.3 Sequential Y86 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 4.3.1 Organizing Processing into Stages . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 4.3.2 SEQ Hardware Structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 355 4.3.3 SEQ Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 4.3.4 SEQ Stage Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 4.4 General Principles of Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 4.4.1 Computational Pipelines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 370 4.4.2 A Detailed Look at Pipeline Operation . . . . . . . . . . . . . . . . . . . . . . . . . 372 4.4.3 Limitations of Pipelining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374 4.4.4 Pipelining a System with Feedback . . . . . . . . . . . . . . . . . . . . . . . . . . 376 4.5 Pipelined Y86 Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 377 4.5.1 SEQ+: Rearranging the Computation Stages . . . . . . . . . . . . . . . . . . . . . 377 4.5.2 Inserting Pipeline Registers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 379 4.5.3 Rearranging and Relabeling Signals . . . . . . . . . . . . . . . . . . . . . . . . . . 383 4.5.4 Next PC Prediction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384 4.5.5 Pipeline Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 386 4.5.6 Avoiding Data Hazards by Stalling . . . . . . . . . . . . . . . . . . . . . . . . . . . 391 4.5.7 Avoiding Data Hazards by Forwarding . . . . . . . . . . . . . . . . . . . . . . . . . 393 4.5.8 Load/Use Data Hazards . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 397 4.5.9 Exception Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401 4.5.10 PIPE Stage Implementations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 403 4.5.11 Pipeline Control Logic . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 4.5.12 Performance Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 4.5.13 Unfinished Business . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 424 4.6 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426 4.6.1 Y86 Simulators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 5 Optimizing Program Performance 449 5.1 Capabilities and Limitations of Optimizing Compilers . . . . . . . . . . . . . . . . . . . . . 451 5.2 Expressing Program Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 5.3 Program Example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 457 5.4 Eliminating Loop Inefficiencies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 460 5.5 Reducing Procedure Calls . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 5.6 Eliminating Unneeded Memory References . . . . . . . . . . . . . . . . . . . . . . . . . . 466 5.7 Understanding Modern Processors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 470 5.7.1 Overall Operation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 471 5.7.2 Functional Unit Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 5.7.3 An Abstract Model of Processor Operation . . . . . . . . . . . . . . . . . . . . . . 476 5.8 Loop Unrolling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 481 5.9 Enhancing Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 5.9.1 Multiple Accumulators . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 486 5.9.2 Reassociation Transformation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 5.10 Summary of Results for Optimizing Combining Code . . . . . . . . . . . . . . . . . . . . . 497 5.11 Some Limiting Factors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 5.11.1 Register Spilling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 5.11.2 Branch Prediction and Misprediction Penalties . . . . . . . . . . . . . . . . . . . . 499 5.12 Understanding Memory Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 503 5.12.1 Load Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 504 5.12.2 Store Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505 5.13 Life in the Real World: Performance Improvement Techniques . . . . . . . . . . . . . . . . 511 5.14 Identifying and Eliminating Performance Bottlenecks . . . . . . . . . . . . . . . . . . . . . 512 5.14.1 Program Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512 5.14.2 Using a Profiler to Guide Optimization . . . . . . . . . . . . . . . . . . . . . . . . 514 5.14.3 Amdahl’s Law . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 518 5.15 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 519 6 The Memory Hierarchy 531 6.1 Storage Technologies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 6.1.1 Random-Access Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 532 6.1.2 Disk Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 539 6.1.3 Solid State Disks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 551 6.1.4 Storage Technology Trends . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553 6.2 Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 6.2.1 Locality of References to Program Data . . . . . . . . . . . . . . . . . . . . . . . . 557 6.2.2 Locality of Instruction Fetches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 6.2.3 Summary of Locality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 559 6.3 The Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560 6.3.1 Caching in the Memory Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . . 562 6.3.2 Summary of Memory Hierarchy Concepts . . . . . . . . . . . . . . . . . . . . . . . 564 6.4 Cache Memories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 6.4.1 Generic Cache Memory Organization . . . . . . . . . . . . . . . . . . . . . . . . . 566 6.4.2 Direct-Mapped Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 568 6.4.3 Set Associative Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 6.4.4 Fully Associative Caches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 6.4.5 Issues with Writes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 579 6.4.6 Anatomy of a Real Cache Hierarchy . . . . . . . . . . . . . . . . . . . . . . . . . . 580 6.4.7 Performance Impact of Cache Parameters . . . . . . . . . . . . . . . . . . . . . . . 581 6.5 Writing Cache-friendly Code . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583 6.6 Putting it Together: The Impact of Caches on Program Performance . . . . . . . . . . . . . 588 6.6.1 The Memory Mountain . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 588 6.6.2 Rearranging Loops to Increase Spatial Locality . . . . . . . . . . . . . . . . . . . . 592 6.6.3 Exploiting Locality in Your Programs . . . . . . . . . . . . . . . . . . . . . . . . . 596 6.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 597 II Running Programs on a System 619 7 Linking 623 7.1 Compiler Drivers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624 7.2 Static Linking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 7.3 Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 626 7.4 Relocatable Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 627 7.5 Symbols and Symbol Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 7.6 Symbol Resolution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 631 7.6.1 How Linkers Resolve Multiply Defined Global Symbols . . . . . . . . . . . . . . . 632 7.6.2 Linking with Static Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 635 7.6.3 How Linkers Use Static Libraries to Resolve References . . . . . . . . . . . . . . . 638 7.7 Relocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 7.7.1 Relocation Entries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 7.7.2 Relocating Symbol References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 641 7.8 Executable Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 7.9 Loading Executable Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 7.10 Dynamic Linking with Shared Libraries . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 7.11 Loading and Linking Shared Libraries from Applications . . . . . . . . . . . . . . . . . . . 650 7.12 *Position-Independent Code (PIC) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653 7.13 Tools for Manipulating Object Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656 7.14 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 656 8 Exceptional Control Flow 667 8.1 Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668 8.1.1 Exception Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670 8.1.2 Classes of Exceptions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 671 8.1.3 Exceptions in Linux/IA32 Systems . . . . . . . . . . . . . . . . . . . . . . . . . . 673 8.2 Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677 8.2.1 Logical Control Flow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 677 8.2.2 Concurrent Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 678 8.2.3 Private Address Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679 8.2.4 User and Kernel Modes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 679 8.2.5 Context Switches . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 8.3 System Call Error Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 682 8.4 Process Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683 8.4.1 Obtaining Process ID’s . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683 8.4.2 Creating and Terminating Processes . . . . . . . . . . . . . . . . . . . . . . . . . . 684 8.4.3 Reaping Child Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 688 8.4.4 Putting Processes to Sleep . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 694 8.4.5 Loading and Running Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 695 8.4.6 Using fork and execve to Run Programs . . . . . . . . . . . . . . . . . . . . . . 697 8.5 Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701 8.5.1 Signal Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 701 8.5.2 Sending Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703 8.5.3 Receiving Signals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 706 8.5.4 Signal Handling Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 710 8.5.5 Portable Signal Handling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 716 8.5.6 Explicitly Blocking and Unblocking Signals . . . . . . . . . . . . . . . . . . . . . . 717 8.5.7 Synchronizing Flows to Avoid Nasty Concurrency Bugs . . . . . . . . . . . . . . . 719 8.6 Nonlocal Jumps . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 721 8.7 Tools for Manipulating Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727 8.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727 9 Virtual Memory 741 9.1 Physical and Virtual Addressing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 742 9.2 Address Spaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 743 9.3 VM as a Tool for Caching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744 9.3.1 DRAM Cache Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745 9.3.2 Page Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745 9.3.3 Page Hits . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 746 9.3.4 Page Faults . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 747 9.3.5 Allocating Pages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 9.3.6 Locality to the Rescue Again . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749 9.4 VM as a Tool for Memory Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . 749 9.5 VM as a Tool for Memory Protection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751 9.6 Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 752 9.6.1 Integrating Caches and VM . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 755 9.6.2 Speeding up Address Translation with a TLB . . . . . . . . . . . . . . . . . . . . . 756 9.6.3 Multi Level Page Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 756 9.6.4 Putting it Together: End-to-end Address Translation . . . . . . . . . . . . . . . . . 759 9.7 Case Study: The Intel Core i7/Linux Memory System . . . . . . . . . . . . . . . . . . . . . 763 9.7.1 Core i7 Address Translation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 763 9.7.2 Linux Virtual Memory System . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 767 9.8 Memory Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 770 9.8.1 Shared Objects Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 771 9.8.2 The fork Function Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773 9.8.3 The execve Function Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . 773 9.8.4 User-level Memory Mapping with the mmap Function . . . . . . . . . . . . . . . . 774 9.9 Dynamic Memory Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 776 9.9.1 The malloc and free Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . 777 9.9.2 Why Dynamic Memory Allocation? . . . . . . . . . . . . . . . . . . . . . . . . . . 780 9.9.3 Allocator Requirements and Goals . . . . . . . . . . . . . . . . . . . . . . . . . . . 781 9.9.4 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 782 9.9.5 Implementation Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 783 9.9.6 Implicit Free Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 784 9.9.7 Placing Allocated Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 785 9.9.8 Splitting Free Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 9.9.9 Getting Additional Heap Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 9.9.10 Coalescing Free Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 786 9.9.11 Coalescing with Boundary Tags . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787 9.9.12 Putting it Together: Implementing a Simple Allocator . . . . . . . . . . . . . . . . . 789 9.9.13 Explicit Free Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 797 9.9.14 Segregated Free Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 798 9.10 Garbage Collection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 800 9.10.1 Garbage Collector Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 801 9.10.2 Mark&Sweep Garbage Collectors . . . . . . . . . . . . . . . . . . . . . . . . . . . 802 9.10.3 Conservative Mark&Sweep for C Programs . . . . . . . . . . . . . . . . . . . . . . 804 9.11 Common Memory-Related Bugs in C Programs . . . . . . . . . . . . . . . . . . . . . . . . 805 9.11.1 Dereferencing Bad Pointers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805 9.11.2 Reading Uninitialized Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 805 9.11.3 Allowing Stack Buffer Overflows . . . . . . . . . . . . . . . . . . . . . . . . . . . 806 9.11.4 Assuming that Pointers and the Objects they Point to Are the Same Size . . . . . . . 806 9.11.5 Making Off-by-One Errors . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 807 9.11.6 Referencing a Pointer Instead of the Object it Points to . . . . . . . . . . . . . . . . 807 9.11.7 Misunderstanding Pointer Arithmetic . . . . . . . . . . . . . . . . . . . . . . . . . 808 9.11.8 Referencing Nonexistent Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . 808 9.11.9 Referencing Data in Free Heap Blocks . . . . . . . . . . . . . . . . . . . . . . . . . 808 9.11.10 Introducing Memory Leaks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809 9.12 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 809 III Interaction and Communication Between Programs 819 10 System-Level I/O 823 10.1 Unix I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824 10.2 Opening and Closing Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824 10.3 Reading and Writing Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 826 10.4 Robust Reading and Writing with the RIO Package . . . . . . . . . . . . . . . . . . . . . . 828 10.4.1 RIO Unbuffered Input and Output Functions . . . . . . . . . . . . . . . . . . . . . 828 10.4.2 RIO Buffered Input Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 829 10.5 Reading File Metadata . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 832 10.6 Sharing Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 837 10.7 I/O Redirection . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 840 10.8 Standard I/O . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 841 10.9 Putting It Together: Which I/O Functions Should I Use? . . . . . . . . . . . . . . . . . . . 842 10.10Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 843 11 Network Programming 847 11.1 The Client-Server Programming Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . 847 11.2 Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 848 11.3 The Global IP Internet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 853 11.3.1 IP Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 854 11.3.2 Internet Domain Names . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 856 11.3.3 Internet Connections . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 860 11.4 The Sockets Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861 11.4.1 Socket Address Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 861 11.4.2 The socket Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 862 11.4.3 The connect Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 863 11.4.4 The open clientfd Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864 11.4.5 The bind Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865 11.4.6 The listen Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865 11.4.7 The open listenfd Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . 865 11.4.8 The accept Function . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 867 11.4.9 Example Echo Client and Server . . . . . . . . . . . . . . . . . . . . . . . . . . . . 868 11.5 Web Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871 11.5.1 Web Basics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 871 11.5.2 Web Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 872 11.5.3 HTTP Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 873 11.5.4 Serving Dynamic Content . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 876 11.6 Putting it Together: The TINY Web Server . . . . . . . . . . . . . . . . . . . . . . . . . . . 877 11.7 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 887 12 Concurrent Programming 893 12.1 Concurrent Programming With Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . 894 12.1.1 A Concurrent Server Based on Processes . . . . . . . . . . . . . . . . . . . . . . . 895 12.1.2 Pros and Cons of Processes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 896 12.2 Concurrent Programming With I/O Multiplexing . . . . . . . . . . . . . . . . . . . . . . . 898 12.2.1 A Concurrent Event-Driven Server Based on I/O Multiplexing . . . . . . . . . . . . 901 12.2.2 Pros and Cons of I/O Multiplexing . . . . . . . . . . . . . . . . . . . . . . . . . . . 903 12.3 Concurrent Programming With Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . 906 12.3.1 Thread Execution Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907 12.3.2 Posix Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 907 12.3.3 Creating Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 908 12.3.4 Terminating Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 909 12.3.5 Reaping Terminated Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910 12.3.6 Detaching Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 910 12.3.7 Initializing Threads . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 911 12.3.8 A Concurrent Server Based on Threads . . . . . . . . . . . . . . . . . . . . . . . . 911 12.4 Shared Variables in Threaded Programs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913 12.4.1 Threads Memory Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 913 12.4.2 Mapping Variables to Memory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915 12.4.3 Shared Variables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 915 12.5 Synchronizing Threads with Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . 916 12.5.1 Progress Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 919 12.5.2 Semaphores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 921 12.5.3 Using Semaphores for Mutual Exclusion . . . . . . . . . . . . . . . . . . . . . . . 922 12.5.4 Using Semaphores to Schedule Shared Resources . . . . . . . . . . . . . . . . . . . 924 12.5.5 Putting It Together: A Concurrent Server Based on Prethreading . . . . . . . . . . . 928 12.6 Using Threads for Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 929 12.7 Other Concurrency Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936 12.7.1 Thread Safety . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 936 12.7.2 Reentrancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 939 12.7.3 Using Existing Library Functions in Threaded Programs . . . . . . . . . . . . . . . 940 12.7.4 Races . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 941 12.7.5 Deadlocks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 943 12.8 Summary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945 A Error Handling 957 A.1 Error Handling in Unix Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 957 A.2 Error-Handling Wrappers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 959