Computer Systems A Programmer’s Perspective

Front Cover......Page 1
Contents......Page 8
Preface......Page 20
About the Authors......Page 36
Chapter 1: A Tour of Computer Systems......Page 38
1.1: Information Is Bits + Context......Page 40
1.2: Programs Are Translated by Other Programs into Different Forms......Page 41
1.3: It Pays to Understand How Compilation Systems Work......Page 43
1.4: Processors Read and Interpret Instructions Stored in Memory......Page 44
1.4.1: Hardware Organization of a System......Page 45
1.4.2: Running the hello Program......Page 47
1.5: Caches Matter......Page 48
1.7: The Operating System Manages the Hardware......Page 51
1.7.1: Processes......Page 52
1.7.2: Threads......Page 54
1.7.3: Virtual Memory......Page 55
1.8: Systems Communicate with Other Systems Using Networks......Page 56
1.9.1: Amdahl’s Law......Page 59
1.9.2: Concurrency and Parallelism......Page 61
1.9.3: The Importance of Abstractions in Computer Systems......Page 63
1.10: Summary......Page 64
Solutions to Practice Problems......Page 65
Part I: Program Structure and Execution......Page 66
Chapter 2: Representing and Manipulating Information......Page 68
2.1: Information Storage......Page 71
2.1.1: Hexadecimal Notation......Page 73
2.1.2: Data Sizes......Page 76
2.1.3: Addressing and Byte Ordering......Page 79
2.1.5: Representing Code......Page 86
2.1.6: Introduction to Boolean Algebra......Page 87
2.1.7: Bit-Level Operations in C......Page 91
2.1.8: Logical Operations in C......Page 93
2.1.9: Shift Operations in C......Page 94
2.2: Integer Representations......Page 96
2.2.1: Integral Data Types......Page 97
2.2.2: Unsigned Encodings......Page 99
2.2.3: Two’s-Complement Encodings......Page 101
2.2.4: Conversions between Signed and Unsigned......Page 107
2.2.5: Signed versus Unsigned in C......Page 111
2.2.6: Expanding the Bit Representation of a Number......Page 113
2.2.7: Truncating Numbers......Page 118
2.2.8: Advice on Signed versus Unsigned......Page 120
2.3.1: Unsigned Addition......Page 121
2.3.2: Two’s-Complement Addition......Page 127
2.3.3: Two’s-Complement Negation......Page 132
2.3.4: Unsigned Multiplication......Page 133
2.3.5: Two’s-Complement Multiplication......Page 134
2.3.6: Multiplying by Constant......Page 138
2.3.7: Dividing by Powers of 2......Page 140
2.3.8: Final Thoughts on Integer Arithmetic......Page 144
2.4: Floating Point......Page 145
2.4.1: Fractional Binary Numbers......Page 146
2.4.2: IEEE Floating-Point Representation......Page 149
2.4.3: Example Numbers......Page 152
2.4.4: Rounding......Page 157
2.4.5: Floating-Point Operations......Page 159
2.4.6: Floating Point in C......Page 161
2.5: Summary......Page 163
Bibliographic Notes......Page 164
Homework Problems......Page 165
Solutions to Practice Problems......Page 180
Chapter 3: Machine-Level Representation of Program......Page 200
3.1: A Historical Perspective......Page 203
3.2: Program Encodings......Page 206
3.2.1: Machine-Level Code......Page 207
3.2.2: Code Examples......Page 209
3.2.3: Notes on Formatting......Page 212
3.3: Data Formats......Page 214
3.4: Accessing Information......Page 216
3.4.1: Operand Specifiers......Page 217
3.4.2: Data Movement Instructions......Page 219
3.4.3: Data Movement Example......Page 223
3.4.4: Pushing and Popping Stack Data......Page 226
3.5.1: Load Effective Address......Page 228
3.5.3: Shift Operations......Page 231
3.5.4: Discussion......Page 233
3.5.5: Special Arithmetic Operations......Page 234
3.6: Control......Page 237
3.6.1: Condition Codes......Page 238
3.6.2: Accessing the Condition Codes......Page 239
3.6.3: Jump Instructions......Page 242
3.6.4: Jump Instruction Encodings......Page 244
3.6.5: Implementing Conditional Branches with Conditional Control......Page 246
3.6.6: Implementing Conditional Branches with Conditional Moves......Page 251
3.6.7: Loop......Page 257
3.6.8: Switch Statements......Page 269
3.7: Procedures......Page 275
3.7.1: The Run-Time Stack......Page 276
3.7.2: Control Transfer......Page 278
3.7.3: Data Transfer......Page 282
3.7.4: Local Storage on the Stack......Page 285
3.7.5: Local Storage in Registers......Page 286
3.7.6: Recursive Procedures......Page 290
3.8.1: Basic Principles......Page 292
3.8.2: Pointer Arithmetic......Page 294
3.8.3: Nested Arrays......Page 295
3.8.4: Fixed-Size Arrays......Page 297
3.8.5: Variable-Size Arrays......Page 299
3.9.1: Structures......Page 302
3.9.2: Unions......Page 306
3.9.3: Data Alignment......Page 310
3.10: Combining Control and Data in Machine-Level Programs......Page 313
3.10.1: Understanding Pointers......Page 314
3.10.3: Out-of-Bounds Memory References and Buffer Overflow......Page 316
3.10.4: Thwarting Buffer Overflow Attacks......Page 321
3.10.5: Supporting Variable-Size Stack Frames......Page 327
3.11: Floating-Point Code......Page 330
3.11.1: Floating-Point Movement and Conversion Operations......Page 333
3.11.2: Floating-Point Code in Procedures......Page 338
3.11.3: Floating-Point Arithmetic Operations......Page 339
3.11.4: Defining and Using Floating-Point Constants......Page 341
3.11.5: Using Bitwise Operations in Floating-Point Code......Page 342
3.11.6: Floating-Point Comparison Operations......Page 343
3.12: Summary......Page 346
Bibliographic Notes......Page 347
Homework Problems......Page 348
Solutions to Practice Problems......Page 362
Chapter 4: Processor Architecture......Page 388
4.1.1: Programmer-Visible State......Page 392
4.1.2: Y86-64 Instructions......Page 393
4.1.3: Instruction Encoding......Page 395
4.1.4: Y86-64 Exceptions......Page 400
4.1.5: Y86-64 Programs......Page 401
4.1.6: Some Y86-64 Instruction Details......Page 407
4.2: Logic Design and the Hardware Control Language HCL......Page 409
4.2.1: Logic Gates......Page 410
4.2.2: Combinational Circuits and HCL Boolean Expressions......Page 411
4.2.3: Word-Level Combinational Circuits and HCL Integer Expressions......Page 413
4.2.4: Set Membership......Page 417
4.2.5: Memory and Clocking......Page 418
4.3.1: Organizing Processing into Stages......Page 421
4.3.2: SEQ Hardware Structure......Page 433
4.3.3: SEQ Timing......Page 437
4.3.4: SEQ Stage Implementations......Page 441
4.4.1: Computational Pipelines......Page 449
4.4.2: A Detailed Look at Pipeline Operation......Page 451
4.4.3: Limitations of Pipelining......Page 453
4.4.4: Pipelining a System with Feedback......Page 456
4.5.1: SEQ+: Rearranging the Computation Stages......Page 458
4.5.2: Inserting Pipeline Registers......Page 459
4.5.3: Rearranging and Relabeling Signals......Page 463
4.5.4: Next PC Prediction......Page 464
4.5.5: Pipeline Hazards......Page 466
4.5.6: Exception Handling......Page 481
4.5.7: PIPE Stage Implementations......Page 484
4.5.8: Pipeline Control Logic......Page 492
4.5.9: Performance Analysis......Page 501
4.5.10: Unfinished Business......Page 505
4.6: Summary......Page 507
4.6.1: Y86-64 Simulators......Page 509
Homework Problems......Page 510
Solutions to Practice Problems......Page 517
Chapter 5: Optimizing Program Performance......Page 532
5.1: Capabilities and Limitations of Optimizing Compilers......Page 535
5.2: Expressing Program Performance......Page 539
5.3: Program Example......Page 541
5.4: Eliminating Loop Inefficiencies......Page 545
5.5: Reducing Procedure Calls......Page 549
5.6: Eliminating Unneeded Memory References......Page 551
5.7: Understanding Modern Processors......Page 554
5.7.1: Overall Operation......Page 555
5.7.2: Functional Unit Performance......Page 560
5.7.3: An Abstract Model of Processor Operation......Page 562
5.8: Loop Unrolling......Page 568
5.9.1: Multiple Accumulators......Page 573
5.9.2: Reassociation Transformation......Page 578
5.10: Summary of Results for Optimizing Combining Code......Page 584
5.11.1: Register Spilling......Page 585
5.11.2: Branch Prediction and Misprediction Penalties......Page 586
5.12: Understanding Memory Performance......Page 590
5.12.1: Load Performance......Page 591
5.12.2: Store Performance......Page 592
5.13: Life in the Real World: Performance Improvement Techniques......Page 598
5.14.1: Program Profiling......Page 599
5.14.2: Using a Profiler to Guide Optimization......Page 602
5.15: Summary......Page 605
Bibliographic Notes......Page 606
Homework Problems......Page 607
Solutions to Practice Problems......Page 610
Chapter 6: The Memory Hierarchy......Page 616
6.1.1: Random Access Memory......Page 618
6.1.2: Disk Storage......Page 626
6.1.3: Solid State Disks......Page 637
6.1.4: Storage Technology Trends......Page 639
6.2: Locality......Page 641
6.2.1: Locality of References to Program Data......Page 643
6.2.2: Locality of Instruction Fetches......Page 644
6.2.3: Summary of Locality......Page 645
6.3: The Memory Hierarchy......Page 646
6.3.1: Caching in the Memory Hierarchy......Page 647
6.4: Cache Memories......Page 651
6.4.1: Generic Cache Memory Organization......Page 652
6.4.2: Direct-Mapped Caches......Page 654
6.4.3: Set Associative Caches......Page 661
6.4.4: Fully Associative Caches......Page 663
6.4.5: Issues with Writes......Page 667
6.4.7: Performance Impact of Cache Parameters......Page 668
6.5: Writing Cache-Friendly Code......Page 670
6.6.1: The Memory Mountain......Page 676
6.6.2: Rearranging Loops to Increase Spatial Locality......Page 680
6.6.3: Exploiting Locality in Your Programs......Page 684
Bibliographic Notes......Page 685
Homework Problems......Page 686
Solutions to Practice Problems......Page 697
Part II: Running Programs on a System......Page 704
Chapter 7: Linking......Page 706
7.1: Compiler Drivers......Page 708
7.2: Static Linking......Page 709
7.3: Object Files......Page 710
7.4: Relocatable Object Files......Page 711
7.5: Symbols and Symbol Tables......Page 712
7.6: Symbol Resolution......Page 716
7.6.1: How Linkers Resolve Duplicate Symbol Names......Page 717
7.6.2: Linking with Static Libraries......Page 721
7.6.3: How Linkers Use Static Libraries to Resolve References......Page 725
7.7: Relocation......Page 726
7.7.1: Relocation Entries......Page 727
7.7.2: Relocating Symbol References......Page 728
7.8: Executable Object Files......Page 732
7.9: Loading Executable Object Files......Page 734
7.10: Dynamic Linking with Shared Libraries......Page 735
7.11: Loading and Linking Shared Libraries from Applications......Page 738
7.12: Position-Independent Code (PIC)......Page 741
7.13: Library Interpositioning......Page 744
7.13.2: Link-Time Interpositioning......Page 745
7.13.3: Run-Time Interpositioning......Page 747
7.15: Summary......Page 750
Homework Problems......Page 751
Solutions to Practice Problems......Page 754
Chapter 8: Exceptional Control Flow......Page 758
8.1: Exceptions......Page 760
8.1.1: Exception Handling......Page 761
8.1.2: Classes of Exceptions......Page 763
8.1.3: Exceptions in Linux/x86-64 Systems......Page 766
8.2.1: Logical Control Flow......Page 769
8.2.2: Concurrent Flows......Page 770
8.2.4: User and Kernel Modes......Page 771
8.2.5: Context Switches......Page 773
8.3: System Call Error Handling......Page 774
8.4: Process Control......Page 775
8.4.2: Creating and Terminating Processes......Page 776
8.4.3: Reaping Child Processes......Page 780
8.4.4: Putting Processes to Sleep......Page 786
8.4.5: Loading and Running Programs......Page 787
8.4.6: Using fork and execve to Run Programs......Page 790
8.5: Signals......Page 793
8.5.1: Signal Terminology......Page 795
8.5.2: Sending Signals......Page 796
8.5.3: Receiving Signals......Page 799
8.5.4: Blocking and Unblocking Signals......Page 801
8.5.5: Writing Signal Handlers......Page 803
8.5.6: Synchronizing Flows to Avoid Nasty Concurrency Bugs......Page 813
8.5.7: ExplicitlyWaiting for Signals......Page 815
8.6: Nonlocal Jumps......Page 818
8.7: Tools for Manipulating Processes......Page 823
Bibliographic Notes......Page 824
Homework Problems......Page 825
Solutions to Practice Problems......Page 832
Chapter 9: Virtual Memory......Page 838
9.1: Physical and Virtual Addressing......Page 840
9.2: Address Spaces......Page 841
9.3: VM as a Tool for Caching......Page 842
9.3.2: Page Tables......Page 843
9.3.4: Page Faults......Page 845
9.3.6: Locality to the Rescue Again......Page 847
9.4: VM as a Tool for Memory Management......Page 848
9.5: VM as a Tool for Memory Protection......Page 849
9.6: Address Translation......Page 850
9.6.2: Speeding Up Address Translation with a TLB......Page 854
9.6.3: Multi-Level Page Tables......Page 856
9.6.4: Putting It Together: End-to-End Address Translation......Page 858
9.7: Case Study: The Intel Core i7/Linux Memory System......Page 862
9.7.1: Core i7 Address Translation......Page 863
9.7.2: Linux Virtual Memory System......Page 865
9.8.1: Shared Objects Revisited......Page 870
9.8.3: The execve Function Revisited......Page 873
9.8.4: User-Level Memory Mapping with the mmap Function......Page 874
9.9: Dynamic Memory Allocation......Page 876
9.9.1: The malloc and free Functions......Page 877
9.9.2: Why Dynamic Memory Allocation?......Page 880
9.9.3: Allocator Requirements and Goals......Page 881
9.9.5: Implementation Issues......Page 883
9.9.6: Implicit Free Lists......Page 884
9.9.8: Splitting Free Blocks......Page 886
9.9.10: Coalescing Free Blocks......Page 887
9.9.11: Coalescing with Boundary Tags......Page 888
9.9.12: Putting It Together: Implementing a Simple Allocator......Page 891
9.9.13: Explicit Free Lists......Page 899
9.9.14: Segregated Free Lists......Page 900
9.10: Garbage Collection......Page 902
9.10.1: Garbage Collector Basics......Page 903
9.10.2: Mark&Sweep Garbage Collectors......Page 904
9.10.3: Conservative Mark&Sweep for C Programs......Page 906
9.11.1: Dereferencing Bad Pointers......Page 907
9.11.3: Allowing Stack Buffer Overflows......Page 908
9.11.5: Making Off-by-One Errors......Page 909
9.11.7: Misunderstanding Pointer Arithmetic......Page 910
9.11.9: Referencing Data in Free Heap Blocks......Page 911
9.12: Summary......Page 912
Homework Problems......Page 913
Solutions to Practice Problems......Page 917
Part III: Interaction and Communication between Programs......Page 924
Chapter 10: System-Level I/O......Page 926
10.1: Unix I/O......Page 927
10.2: Files......Page 928
10.3: Opening and Closing Files......Page 930
10.4: Reading and Writing Files......Page 932
10.5.1: Rio Unbuffered Input and Output Functions......Page 934
10.5.2: Rio Buffered Input Functions......Page 935
10.6: Reading File Metadata......Page 940
10.7: Reading Directory Contents......Page 942
10.8: Sharing Files......Page 943
10.9: I/O Redirection......Page 946
10.11: Putting It Together: Which I/O Functions Should I Use?......Page 948
10.12: Summary......Page 950
Homework Problems......Page 951
Solutions to Practice Problems......Page 952
Chapter 11: Network Programming......Page 954
11.1: The Client-Server Programming Model......Page 955
11.2: Networks......Page 956
11.3: The Global IP Internet......Page 961
11.3.1: IP Addresses......Page 962
11.3.2: Internet Domain Names......Page 964
11.3.3: Internet Connections......Page 966
11.4: The Sockets Interface......Page 969
11.4.1: Socket Address Structures......Page 970
11.4.3: The connect Function......Page 971
11.4.5: The listen Function......Page 972
11.4.6: The accept Function......Page 973
11.4.7: Host and Service Conversion......Page 974
11.4.8: Helper Functions for the Sockets Interface......Page 979
11.4.9: Example Echo Client and Server......Page 981
11.5.1: Web Basics......Page 985
11.5.2: Web Content......Page 986
11.5.3: HTTP Transactions......Page 987
11.5.4: Serving Dynamic Content......Page 990
11.6: Putting It Together: The Tiny Web Server......Page 993
11.7: Summary......Page 1001
Homework Problems......Page 1002
Solutions to Practice Problems......Page 1003
Chapter 12: Concurrent Programming......Page 1008
12.1: Concurrent Programming with Processes......Page 1010
12.1.1: A Concurrent Server Based on Processes......Page 1011
12.1.2: Pros and Cons of Processes......Page 1012
12.2: Concurrent Programming with I/O Multiplexing......Page 1014
12.2.1: A Concurrent Event-Driven Server Based on I/O Multiplexing......Page 1017
12.3: Concurrent Programming with Threads......Page 1022
12.3.1: Thread Execution Model......Page 1023
12.3.2: Posix Threads......Page 1024
12.3.4: Terminating Threads......Page 1025
12.3.6: Detaching Threads......Page 1026
12.3.7: Initializing Threads......Page 1027
12.3.8: A Concurrent Server Based on Threads......Page 1028
12.4: Shared Variables in Threaded Programs......Page 1029
12.4.1: Threads Memory Model......Page 1030
12.4.2: Mapping Variables to Memory......Page 1031
12.5: Synchronizing Threads with Semaphores......Page 1032
12.5.1: Progress Graphs......Page 1036
12.5.2: Semaphores......Page 1038
12.5.3: Using Semaphores for Mutual Exclusion......Page 1039
12.5.4: Using Semaphores to Schedule Shared Resources......Page 1041
12.5.5: Putting It Together: A Concurrent Server Based on Prethreading......Page 1045
12.6: Using Threads for Parallelism......Page 1050
12.7.1: Thread Safety......Page 1057
12.7.2: Reentrancy......Page 1060
12.7.3: Using Existing Library Functions in Threaded Programs......Page 1061
12.7.4: Races......Page 1062
12.7.5: Deadlocks......Page 1064
Bibliographic Notes......Page 1067
Homework Problems......Page 1068
Solutions to Practice Problems......Page 1073
Appendix A: Error Handling......Page 1078
A.1: Error Handling in Unix Systems......Page 1079
A.2: Error-Handling Wrappers......Page 1080
References......Page 1084
Index......Page 1090
Back Cover......Page 1122