Computer Systems

Randal E. Bryant received the Bachelor's degree from the University of Michigan in 1973 and then attended graduate school at the Massachusetts Institute of Technology, receiving the Ph.D. degree in computer science in 1981. He spent three years as an Assistant Professor at the California Institute of Technology and has been on the faculty at Carnegie Mellon since 1984. He is currently the President's Professor of Computer Science and head of the Department of Computer Science. He also holds a courtesy appointment with the Department of Electrical and Computer Engineering. He has taught courses in computer systems at both the undergraduate and graduate level for over 20 years. Over many years of teaching computer architecture courses, he began shifting the focus from how computers are designed to one of how programmers can write more efficient and reliable programs if they understand the system better. Together with Prof. O'Hallaron, he developed the course "Introduction to Computer Systems" at Carnegie Mellon that is the basis for this book. He has also taught courses in algorithms and programming. Prof. Bryant's research concerns the design of software tools to help hardware designers verify the correctness of their systems. These include several types of simulators, as well as formal verification tools that prove the correctness of a design using mathematical methods. He has published over 100 technical papers. His research results are used by major computer manufacturers including Intel, Motorola, IBM, and Fujitsu. He has won several major awards for his research. These include two inventor recognition awards and a technical achievement award from the Semiconductor Research Corporation, the Kanellakis Theory and Practice Award from the Association for Computer Machinery (ACM), and the W. R. G. Baker Award and a Golden Jubilee Medal from the Institute of Electrical and Electronics Engineers (IEEE). He is a Fellow of both the ACM and the IEEE. David R. O'Hallaron received the Ph.D. degree in computer science from the University of Virginia in 1986. After a stint at General Electric, he joined the Carnegie Mellon faculty in 1989 as a Systems Scientist. He is currently an Associate Professor in the Departments of Computer Science and Electrical and Computer Engineering. He has taught computer systems courses at the undergraduate and graduate levels, on such topics as computer architecture, introductory computer systems, parallel processor design, and Internet services. Together with Prof. Bryant, he developed the course "Introduction to Computer Systems" that is the basis for this book. Prof. O'Hallaron and his students perform research in the area of computer -systems. In particular, they develop software systems to help scientists and engineers simulate nature on computers. The best known example of their work is the Quake project, a group of computer scientists, civil engineers, and seismologists who have developed the ability to predict the motion of the ground during strong earthquakes, including major quakes in Southern California, Kobe, Japan, Mexico, and New Zealand. Along with the other members of the Quake Project, he received the Allen Newell Medal for Research Excellence from the CMU School of Computer Science. A benchmark he developed for the Quake project, 183.equake, was selected by SPEC for inclusion in the influential SPEC CPU and OMP (Open MP) benchmark suites.

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