Computer Systems - A Programmer's Perspective

Contents
Preface
About the Authors

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 4
1.3 It Pays to Understand How Compilation Systems Work 6
1.4 Processors Read and Interpret Instructions Stored in Memory 6
1.4.1 Hardware Organization of a System 7
1.4.2 Running the hello Program 9
1.5 Caches Matter 11
1.6 Storage Devices Form a Hierarchy 12
1.7 The Operating System Manages the Hardware 13
1.7.1 Processes 15
1.7.2 Threads 16
1.7.3 Virtual Memory 16
1.7.4 Files 18
1.8 Systems Communicate With Other Systems Using Networks 18
1.9 The Next Step 20
1.10 Summary 20
Bibliographies Notes 21

Part I Program Structure and Execution

2 Representing and Manipulating Information 24
2.1 Information Storage 28
2.1.1 Hexadecimal Notation 28
2.1.2 Words 32
2.1.3 Data Sizes 32
2.1.4 Addressing and Byte Ordering 34
2.1.5 Representing Strings 40
2.1.6 Representing Code 41
2.1.7 Boolean Algebras and Rings 42
2.1.8 Bit-Level Operations in C 46
2.1.9 Logical Operations in C 49
2.1.10 Shift Operations in C 50
2.2 Integer Representations 51
2.2.1 Integral Data Types 51
2.2.2 Unsigned and Two's-Complement Encodings 51
2.2.3 Conversions Between Signed and Unsigned 56
2.2.4 Signed vs. Unsigned in C 59
2.2.5 Expanding the Bit Representation of a Number 61
2.2.6 Truncating Numbers 63
2.2.7 Advice on Signed vs. Unsigned 65
2.3 Integer Arithmetic 65
2.3.1 Unsigned Addition 66
2.3.2 Two's-Complement Addition 69
2.3.3 Two's-Complement Negation 72
2.3.4 Unsigned Multiplication 74
2.3.5 Two's-Complement Multiplication 75
2.3.6 Multiplying by Powers of Two 76
2.3.7 Dividing by Powers of Two 77
2.4 Floating Point 80
2.4.1 Fractional Binary Numbers 81
2.4.2 IEEE Floating-Point Representation 83
2.4.3 Example Numbers 85
2.4.4 Rounding 89
2.4.5 Floating- Point Operations 91
2.4.6 Floating Point in C 92
2.5 Summary 98
Bibliographic Notes 99
Homework Problems 99
Solution to Practice Problems 108

3 Machine- Level Representation of Programs 122
3.1 A Historical Perspective 125
3.2 Program Encodings 128
3.2.1 Machine-Level Code 129
3.2.2 Code Examples 130
3.2.3 A Note on Formatting 133
3.3 Data Formats 135
3.4 Accessing Information 136
3.4.1 Operand Specifiers 137
3.4.2 Data Movement Instructions 138
3.4.3 Data Movement Example 141
3.5 Arithmetic and Logical Operations 143
3.5.1 Load Effective Address 143
3.5.2 Unary and Binary Operations 144
3.5.3 Shift Operations 145
3.5.4 Discussion 146
3.5.5 Special Arithmetic Operations 147
3.6 Control 148
3.6.1 Condition Codes 149
3.6.2 Accessing the Condition Codes 150
3.6.3 Jump Instructions and their Encodings 152
3.6.4 Translating Conditional Branches 156
3.6.5 Loops 158
3.6.6 Switch Statements 166
3.7 Procedures 170
3.7.1 Stack Frame Structure 170
3.7.2 Transferring Control 172
3.7.3 Register Usage Conventions 173
3.7.4 Procedure Example 174
3.7.5 Recursive Procedures 178
3.8 Array Allocation and Access 180
3.8.1 Basic Principles 180
3.8.2 Pointer Arithmetic 182
3.8.3 Arrays and Loops 183
3.8.4 Nested Arrays 183
3.8.5 Fixed Size Arrays 186
3.8.6 Dynamically Allocated Arrays 188
3.9 Heterogeneous Data Structures 191
3.9.1 Structures 191
3.9.2 Unions 194
3.10 Alignment 198
3.11 Putting it Together: Understanding Pointers 201
3.12 Life in the Real World: Using the GDB Debugger 204
3.13 Out-of-Bounds Memory References and Buffer Overflow 206
3.14 *Floating-Point Code 211
3.14.1 Floating-Point Registers 211
3.14.2 Stack Evaluation of Expressions 212
3.14.3 Floating-Point Data Movement and Conversion Operations 215
3.14.4 Floating-Point Arithmetic Instructions 217
3.14.5 Using Floating Point in Procedures 220
3.14.6 Testing and Comparing Floating-Point Values 221
3.15 *Embedding Assembly Code in C Programs 223
3.15.1 Basic Inline Assembly 224
3.15.2 Extended Form of asm 226
3.16 Summary 230
Bibliographic Notes 231
Homework Problems 231
Solutions to Practice Problems 238

4 Processor Architecture 254
4.1 The Y86 Instruction Set Architecture 258
4.2 Logic Design and the Hardware Control Language HCL 271
4.2.1 Logic Gates 271
4.2.2 Combinational Circuits and HCL Boolean Expressions 272
4.2.3 Word-Level Combinational Circuits and HCL Integer Expressions 274
4.2.4 Set Membership 278
4.2.5 Memory and Clocking 279
4.3 Sequential Y86 Implementations 280
4.3.1 Organizing Processing into Stages 281
4.3.2 SEQ Hardware Structure 291
4.3.3 SEQ Timing 295
4.3.4 SEQ Stage Implementations 298
4.3.5 SEQ+: Rearranging the Computation Stages 305
4.4 General Principles of Pipelining 309
4.4.1 Computational Pipelines 3()
4.4.2 A Detailed Look at Pipeline Operation 311
4.4.3 Limitations of Pipelining 313
4.4.4 Pipelining a System with Feedback 315
4.5 Pipelined Y86 Implementations 317
4.5.1 Inserting Pipeline Registers 317
4.5.2 Rearranging and Relabeling Signals 321
4.5.3 N ext PC Prediction 322
4.5.4 Pipeline Hazards 323
4.5.5 Avoiding Data Hazards by Stalling 328
4.5.6 Avoiding Data Hazards by Forwarding 330
4.5.7 Load/Use Data Hazards 335
4.5.8 PIPE Stage Implementations 337
4.5.9 Pipeline Control Logic 343
4.5.10 Performance Analysis 352
4.5.11 Unfinished Business 354
4.6 Summary 359
4.6.1 Y86 Simulators 360
Bibliographic Notes 360
Homework Problems 360
Solutions to Practice Problems 365

5 Optimizing Program Performance 376
5.1 Capabilities and Limitations of Optimizing Compilers 379
5.2 Expressing Program Performance 382
5.3 Program Example 384
5.4 Eliminating Loop Inefficiencies 387
5.5 Reducing Procedure Calls 391
5.6 Eliminating Unneeded Memory References 393
5.7 Understanding Modern Processors 395
5.7.1 Overall Operation 395
5.7.2 Functional Unit Performance 399
5.7.3 A Closer Look at Processor Operation 400
5.8 Reducing Loop Overhead 408
5.9 Converting to Pointer Code 412
5.10 Enhancing Parallelism 415
5.10.1 Loop Splitting 415
5.10.2 Register Spilling 420
5.10.3 Limits to Parallelism 421
5.11 Putting it Together: Summary of Results for Optimizing Combining Code 423
5.11.1 Floating-Point Performance Anorl1aly 423
5.11.2 Changing Platforms 425
5.12 Branch Prediction and Misprediction Penalties 425
5.13 Understanding Memory Performance 429
5.13.1 Load Latency 429
5.13.2 S tore Latency 431
5.14 Life in the Real World: Performance Improvement Techniques 436
5.15 Identifying and Eliminating Performance Bottlenecks 437
5.15.1 Program Profiling 437
5.15.2 Using a Profiler to Guide Optimization 439
5.15.3 Amdahl's Law 443
5.16 Summary 444
Bibliographic Notes 445
Homework Problems 445
Solutions to Practice Problems 450

6 The Memory Hierarchy 454
6.1 Storage Technologies 457
6.1.1 Random-Access Memory 457
6.1.2 Disk Storage 464
6.1.3 Storage Technology Trends 476
6.2 Locality 478
6.2.1 Locality of References to Program Data 478
6.2.2 Locality of Instruction Fetches 480
6.2.3 Summary of Locality 481
6.3 The Memory Hierarchy 482
6.3.1 Caching in the Memory Hierarchy 484
6.3.2 Summary of Memory Hierarchy Concepts 486
6.4 Cache Memories 487
6.4.1 Generic Cache Memory Organization 488
6.4.2 Direct-Mapped Caches 490
6.4.3 Set Associative Caches 497
6.4.4 Fully Associative Caches 499
6.4.5 Issues with Writes 503
6.4.6 Instruction Caches and Unified Caches 504
6.4.7 Performance Impact of Cache Parameters 505
6.5 Writing Cache-Friendly Code 507
6.6 Putting it Together: The Impact of Caches on Program Performance 511
6.6.1 The Memory Mountain 512
6.6.2 Rearranging Loops to Increase Spatial Locality 517
6.6.3 Using Blocking to Increase Temporal Locality 520
6.7 Putting It Together: Exploiting Locality in Your Programs 523
6.8 Summary 524
Bibliographic Notes 524
Homework Problems 525
Solutions to Practice Problems 531

Part II Running Programs on a System

7 Linking 538
7.1 Compiler Drivers 541
7.2 Static Linking 542
7.3 Object Files 543
7.4 Relocatable Object Files 544
7.5 Symbols and Symbol Tables 545
7.6 Symbol Resolution 548
7.6.1 How Linkers Resolve Multiply Defined Global Symbols 549
7.6.2 Linking with Static Libraries 553
7.6.3 How Linkers Use Static Libraries to Resolve References 556
7.7 Relocation 557
7.7.1 Relocation Entries 558
7.7.2 Relocating Symbol References 558
7.8 Executable Object Files 561
7.9 Loading Executable Object Files 564
7.10 Dynamic Linking with Shared Libraries 566
7.11 Loading and Linking Shared Libraries from Applications 568
7.12 *Position-Independent Code (PIC) 570
7.12.1 PIC Data References 572
7.12.2 PIC Function Calls 572
7.13 Tools for Manipulating Object Files 574
7.14 Summary 575
Bibliographic Notes 575
Homework Problems 576
Solutions to Practice Problems 582

8 Exceptional Control Flow 584
8.1 Exceptions 587
8.1.1 Exception Handling 588
8.1.2 Classes of Exceptions 590
8.1.3 Exceptions in Intel Processors 592
8.2 Processes 594
8.2.1 Logical Control Flow 594
8.2.2 Private Address Space 595
8.2.3 User and Kernel Modes 596
8.2.4 Context Switches 597
8.3 System Calls and Error Handling 599
8.4 Process Control 600
8.4.1 Obtaining Process ID's 600
8.4.2 Creating and Terminating Processes 600
8.4.3 Reaping Child Processes 605
8.4.4 Putting Processes to Sleep 610
8.4.5 Loading and Running Programs 611
8.4.6 Using fork and execve to Run Programs 614
8.5 Signals 61 7
8.5.1 Signal Terminology 617
8.5.2 Sending Signals 619
8.5.3 Receiving Signals 623
8.5.4 Signal Handling Issues 625
8.5.5 Portable Signal Handling 631
8.5.6 Explicitly Blocking Signals 633
8.6 Nonlocal Jumps 635
8.7 Tools for Manipulating Processes 638
8.8 Summary 638
Bibliographic Notes 639
Homework Problems 639
Solutions to Practice Problems 645

9 Measuring Program Execution Time 650
9.1 The Flow of Time on a Computer System 653
9.1.1 Process Scheduling and Timer Interrupts 654
9.1.2 Time from an Application Program's Perspective 655
9.2 Measuring Time by Interval Counting 658
9.2.1 Operation 658
9.2.2 Reading the Process Timers 659
9.2.3 Accuracy of Process Timers 660
9.3 Cycle Counters 663
9.3.1 IA32 Cycle Counters 663
9.4 Measuring Program Execution Time with Cycle Counters 665
9.4.1 The Effects of Context Switching 665
9.4.2 Caching and Other Effects 667
9.4.3 The K -Best Measurement Scheme 671
9.5 Time-of-Day Measurements 680
9.6 Putting it Together: An Experimental Protocol 683
9.7 Looking into the Future 684
9.8 Life in the Real World: An Implementation of the K -Best Measurement Scheme 684
9.9 Lessons Learned 685
9.10 Summary 686
Bibliographic Notes 686
Homework Problems 687
Solutions to Practice Problems 688

10 Virtual Memory 690
10.1 Physical and Virtual Addressing 693
10.2 Address Spaces 694
10.3 VM as a Tool for Caching 695
10.3.1 DRAM Cache Organization 696
10.3.2 Page Tables 696
10.3.3 Page Hits 698
10.3.4 Page Faults 698
10.3.5 Allocating Pages 700
10.3.6 Locality to the Rescue Again 700
10.4 VM as a Tool for Memory Management 701
10.4.1 Simplifying Linking 701
10.4.2 Simplifying Sharing 702
10.4.3 Simplifying Memory Allocation 702
10.4.4 Simplifying Loading 703
10.5 VM as a Tool for Memory Protection 703
10.6 Address Translation 704
10.6.1 Integrating Caches and VM 707
10.6.2 Speeding up Address Translation with a TLB 707
10.6.3 Multi-Level Page Tables 709
10.6.4 Putting it Together: End-to-End Address Translation 711
10.7 Case Study: The Pentium/Linux Memory System 715
10.7.1 Pentium Address Translation 716
10.7.2 Linux Virtual Memory System 721
10.8 Memory Mapping 724
10.8.1 Shared Objects Revisited 725
10.8.2 The fork Function Revisited 727
10.8.3 The execve Function Revisited 727
10.8.4 U ser- Level Memory Mapping with the mmap Function 728
10.9 Dynamic Memory Allocation 730
10.9.1 The malloc and free Functions 731
10.9.2 Why Dynamic Memory Allocation? 733
10.9.3 Allocator Requirements and Goals 735
10.9.4 Fragmentation 736
10.9.5 Implementation Issues 737
10.9.6 Implicit Free Lists 737
10.9.7 Placing Allocated Blocks 739
10.9.8 Splitting Free Blocks 740
10.9.9 Getting Additional Heap Memory 740
10.9.10 Coalescing Free Blocks 741
10.9.11 Coalescing with Boundary Tags 741
10.9.12 Putting it Together: Implementing a Simple Allocator 744
10.9.13 Explicit Free Lists 751
10.9.14 Segregated Free Lists 752
10.10 Garbage Collection 755
10.10.1 Garbage Collector Basics 756
10.10.2 Mark&Sweep Garbage Collectors 757
10.10.3 Conservative Mark&Sweep for C Programs 758
10.11 Common Memory-Related Bugs in C Programs 759
10.11.1 Dereferencing Bad Pointers 759
10.11.2 Reading Uninitialized Memory 760
10.11.3 Allowing Stack Buffer Overflows 760
10.11.4 Assuming that Pointers and the Objects they Point to Are the Same Size 761
10.11.5 Making Off-by-One Errors 761
10.11.6 Referencing a Pointer Instead of the Object it Points to 762
10.11.7 Misunderstanding Pointer Arithmetic 762
10.11.8 Referencing Nonexistent Variables 763
10.11.9 Referencing Data in Free Heap Blocks 763
10.11.10 Introducing Memory Leaks 764
10.12 Recapping Some Key Ideas About Virtual Memory 764
10.13 Summary 764
Bibliographic Notes 765
Homework Problems 766
Solutions to Practice Problems 770

Part III Interaction and Communication Between Programs

11 System-Level I/O 776
11.1 Unix I/O 778
11.2 Opening and Closing Files 779
11.3 Reading and Writing Files 781
11.4 Robust Reading and Writing with the RIO Package 783
11.4.1 RIO Unbuffered Input and Output Functions 783
11.4.2 RIO Buffered Input Functions 784
11.5 Reading File Metadata 789
11.6 Sharing Files 791
11.7 I/O Redirection 793
11.8 Standard I/O 795
11.9 Putting It Together: Which I/O Functions Should I Use? 796
11.10 Summary 797
Bibliographic Notes 798
Homework Problems 798

12 Network Programming 800
12.1 The Client-Server Programming Model 802
12.2 Networks 803
12.3 The Global IP Internet 807
12.3.1 IP Addresses 809
12.3.2 Internet Domain Names 811
12.3.3 Internet Connections 815
12.4 The Sockets Interface 816
12.4.1 Socket Address Structures 817
12.4.2 The socket Function 818
12.4.3 The connect Function 818
12.4.4 The open_clientfd Function 819
12.4.5 The bind Function 819
12.4.6 The 1 i s t en Function 820
12.4.7 The open_listenfd Function 821
12.4.8 The accept Function 821
12.4.9 Example Echo Client and Server 823
12.5 Web Servers 826
12.5.1 Web Basics 826
12.5.2 Web Content 827
12.5.3 HTTP Transactions 828
12.5.4 Serving Dynamic Content 831
12.6 Putting it Together: The TINY Web Server 834
12.7 Summary 841
Bibliographic Notes 842
Homework Problems 842
Solutions to Practice Problems 843

13 Concurrent Programming 846
13.1 Concurrent Programming With Processes 849
13.1.1 A Concurrent Server Based on Processes 851
13.1.2 Pros and Cons of Processes 851
13.2 Concurrent Programming With I/O Multiplexing 853
13.2.1 A Concurrent Event-Driven Server Based on I/O Multiplexing 856
13.2.2 Pros and Cons of I/O Multiplexing 860
13.3 Concurrent Programming With Threads 861
13.3.1 Thread Execution Model 862
13.3.2 Posix Threads 863
13.3.3 Creating Threads 864
13.3.4 Terminating Threads 864
13.3.5 Reaping Terminated Threads 865
13.3.6 Detaching Threads 865
13.3.7 Initializing Threads 866
13.3.8 A Concurrent Server Based on Threads 866
13.4 Shared Variables in Threaded Programs 868
13.4.1 Threads Memory Model 869
13.4.2 Mapping Variables to Memory 870
13.4.3 Shared Variables 870
13.5 Synchronizing Threads with Semaphores 871
13.5.1 Progress Graphs 874
13.5.2 Using Semaphores to Access Shared Variables 877
13.5.3 Posix Semaphores 878
13.5.4 Using Semaphores to Schedule Shared Resources 879
13.6 Putting It Together: A Concurrent Server Based on Prethreading 882
13.7 Other Concurrency Issues 885
13.7.1 Thread Safety 885
13.7.2 Reentrancy 888
13.7.3 Using Existing Library Functions in Threaded Programs 889
13.7.4 Races 890
13.7.5 Deadlocks 891
13.8 Summary 894
Bibliographic Notes 895
Homework Problems 895
Solutions to Practice Problems 899
A HCL Descriptions of Processor Control Logic 905
B Error Handling 925
Bibliography 949
Index 953