The Archer: A Dark Fantasy Romance

Computer systems: A Programmer’s Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer’s perspective, this book strives to teach students how understanding basic elements of computer systems and executing real practice can lead them to create better programs.--Publisher's website. G1. A Tour of Computer Systems -- Part I. Program Structure and Execution : -- 2. Representing and Manipulating Information -- 3. Machine-Level Representation of Programs -- 4. Processor Architecture -- 5. Optimizing Program Performance -- 6. The Memory Hierarchy -- Part II. Running Programs on a System : -- 7. Linking -- 8. Exceptional Control Flow -- 9. Virtual Memory -- Part III. Interaction and Communication Between Programs : -- 10. System-Level I/O -- 11. Network Programming -- 12. Concurrent Programming -- Appendix. Error Handling -- References -- Index. Randal E. Bryant, Carnegie Mellon University, David R. O'Hallaron, Carnegie Mellon. University. Includes bibliographical references and index. Cover 1 Half title 3 THIRD EDITION 5 Coypright 6 Contents 9 Preface 21 Assumptions about the Reader's Background 21 How to Read the Book 22 Book Overview 24 New to This Edition 28 Origins of the Book 29 For Instructors: Courses Based on the Book 30 For Instructors: Classroom-Tested Laboratory Exercises 32 Acknowledgements for the Third Edition 33 Acknowledgements for the Second Edition 34 Acknowledgements for the First Edition 34 About the Authors 37 1 A Tour of Computer Systems 39 1.1 Information Is Bits + Context 41 1.2 Programs Are Translated by Other Programs into Different Forms 42 1.3 It Pays to Understand How Compilation Systems Work 44 1.4 Processors Read and Interpret Instructions Stored in Memory 45 1.4.1 Hardware Organization of a System 46 1.4.2 Running the helloProgram 48 1.5 Caches Matter 49 1.6 Storage Devices Form a Hierarchy 52 1.7 The Operating System Manages the Hardware 52 1.7.1 Processes 53 1.7.2 Threads 55 1.7.3 Virtual Memory 56 1.7.4 Files 57 1.8 Systems Communicate with Other Systems Using Networks 57 1.9 Important Themes 60 1.9.1 Amdahl’s Law 60 1.9.2 Concurrency and Parallelism 62 1.9.3 The Importance of Abstractions in Computer Systems 64 1.10 Summary 27 Bibliographic Notes 28 Solutions to Practice Problems 66 Part I Program Structure and Execution -1 2 Representing and Manipulating Information 69 2.1 Information Storage 72 2.1.1 Hexadecimal Notation 74 2.1.2 Data Sizes 77 2.1.3 Addressing and Byte Ordering 80 2.1.4 Representing Strings 87 2.1.5 Representing Code 87 2.1.6 Introduction to Boolean Algebra 88 2.1.7 Bit-Level Operations in C 92 2.1.8 Logical Operations in C 94 2.1.9 Shift Operations in C 95 2.2 Integer Representations 97 2.2.1 Integral Data Types 98 2.2.2 Unsigned Encodings 100 2.2.3 Two’s-Complement Encodings 102 2.2.4 Conversions between Signed and Unsigned 108 2.2.5 Signed versus Unsigned in C 112 2.2.6 Expanding the Bit Representation of a Number 114 2.2.7 Truncating Numbers 119 2.2.8 Advice on Signed versus Unsigned 121 2.3 Integer Arithmetic 122 2.3.1 Unsigned Addition 122 2.3.2 Two’s-Complement Addition 128 2.3.3 Two’s-Complement Negation 133 2.3.4 Unsigned Multiplication 134 2.3.5 Two’s-Complement Multiplication 135 2.3.6 Multiplying by Constants 139 2.3.7 Dividing by Powers of 2 141 2.3.8 Final Thoughts on Integer Arithmetic 145 2.4 Floating Point 146 2.4.1 Fractional Binary Numbers 147 2.4.2 IEEE Floating-Point Representation 150 2.4.3 Example Numbers 153 2.4.4 Rounding 158 2.4.5 Floating-Point Operations 160 2.4.6 Floating Point in C 162 2.5 Summary 164 Bibliographic Notes 165 Homework Problems 166 Solutions to Practice Problems 181 3 Machine-Level Representation of Programs 201 3.1 A Historical Perspective 204 3.2 Program Encodings 207 3.2.1 Machine-Level Code 208 3.2.2 Code Examples 210 3.2.3 Notes on Formatting 213 3.3 Data Formats 215 3.4 Accessing Information 217 3.4.1 Operand Speci.ers 218 3.4.2 Data Movement Instructions 220 3.4.3 Data Movement Example 224 3.4.4 Pushing and Popping Stack Data 227 3.5 Arithmetic and Logical Operations 229 3.5.1 Load Effective Address 229 3.5.2 Unary and Binary Operations 232 3.5.3 Shift Operations 232 3.5.4 Discussion 234 3.5.5 Special Arithmetic Operations 235 3.6 Control 238 3.6.1 Condition Codes 239 3.6.2 Accessing the Condition Codes 240 3.6.3 Jump Instructions 243 3.6.4 Jump Instruction Encodings 245 3.6.5 Implementing Conditional Branches withConditional Control 247 3.6.6 Implementing Conditional Branches withConditional Moves 252 3.6.7 Loops 258 3.6.8 Switch Statements 270 3.7 Procedures 276 3.7.1 The Run-Time Stack 277 3.7.2 Control Transfer 279 3.7.3 Data Transfer 283 3.7.4 Local Storage on the Stack 286 3.7.5 Local Storage in Registers 289 3.7.6 Recursive Procedures 291 3.8 Array Allocation and Access 293 3.8.1 Basic Principles 293 3.8.2 Pointer Arithmetic 295 3.8.3 Nested Arrays 296 3.8.4 Fixed-Size Arrays 298 3.8.5 Variable-Size Arrays 300 3.9 Heterogeneous Data Structures 303 3.9.1 Structures 303 3.9.2 Unions 307 3.9.3 Data Alignment 311 3.10 Combining Control and Data in Machine-Level Programs 314 3.10.1 Understanding Pointers 315 3.10.2 Life in the Real World: Using the gdbDebugger 317 3.10.3 Out-of-Bounds Memory References and Buffer Over.ow 317 3.10.4 Thwarting Buffer Over.ow Attacks 322 3.10.5 Supporting Variable-Size Stack Frames 328 3.11 Floating-Point Code 331 3.11.1 Floating-Point Movement and Conversion Operations 334 3.11.2 Floating-Point Code in Procedures 339 3.11.3 Floating-Point Arithmetic Operations 340 3.11.4 De.ning and Using Floating-Point Constants 342 3.11.5 Using Bitwise Operations in Floating-Point Code 343 3.11.6 Floating-Point Comparison Operations 344 3.11.7 Observations about Floating-Point Code 347 3.12 Summary 347 Bibliographic Notes 348 Homework Problems 349 Solutions to Practice Problems 363 4 Processor Architecture 389 4.1 The Y86-64 Instruction Set Architecture 393 4.1.1 Programmer-Visible State 393 4.1.2 Y86-64 Instructions 394 4.1.3 Instruction Encoding 396 4.1.4 Y86-64 Exceptions 401 4.1.5 Y86-64 Programs 402 4.1.6 Some Y86-64 Instruction Details 408 4.2 Logic Design and the Hardware Control Language HCL 410 4.2.1 Logic Gates 411 4.2.2 Combinational Circuits and HCL Boolean Expressions 412 4.2.3 Word-Level Combinational Circuits and HCLInteger Expressions 414 4.2.4 Set Membership 418 4.2.5 Memory and Clocking 419 4.3 Sequential Y86-64 Implementations 422 4.3.1 Organizing Processing into Stages 422 4.3.2 SEQ Hardware Structure 434 4.3.3 SEQ Timing 438 4.3.4 SEQ Stage Implementations 442 4.4 General Principles of Pipelining 450 4.4.1 Computational Pipelines 450 4.4.2 A Detailed Look at Pipeline Operation 452 4.4.3 Limitations of Pipelining 454 4.4.4 Pipelining a System with Feedback 457 4.5 Pipelined Y86-64 Implementations 459 4.5.1 SEQ+: Rearranging the Computation Stages 459 4.5.2 Inserting Pipeline Registers 460 4.5.3 Rearranging and Relabeling Signals 464 4.5.4 Next PC Prediction 465 4.5.5 Pipeline Hazards 467 4.5.6 Exception Handling 482 4.5.7 PIPE Stage Implementations 485 4.5.8 Pipeline Control Logic 493 4.5.9 Performance Analysis 502 4.5.10 Un.nished Business 506 4.6 Summary 508 4.6.1 Y86-64 Simulators 510 Bibliographic Notes 511 Homework Problems 511 Solutions to Practice Problems 518 5 Optimizing Program Performance 533 5.1 Capabilities and Limitations of Optimizing Compilers 536 5.2 Expressing Program Performance 540 5.3 Program Example 542 5.4 Eliminating Loop Inef.ciencies 546 5.5 Reducing Procedure Calls 550 5.6 Eliminating Unneeded Memory References 552 5.7 Understanding Modern Processors 555 5.7.1 Overall Operation 556 5.7.2 Functional Unit Performance 561 5.7.3 An Abstract Model of Processor Operation 563 5.8 Loop Unrolling 569 5.9 Enhancing Parallelism 574 5.9.1 Multiple Accumulators 574 5.9.2 Reassociation Transformation 579 5.10 Summary of Results for Optimizing Combining Code 585 5.11 Some Limiting Factors 586 5.11.1 Register Spilling 586 5.11.2 Branch Prediction and Misprediction Penalties 587 5.12 Understanding Memory Performance 591 5.12.1 Load Performance 592 5.12.2 Store Performance 593 5.13 Life in the Real World: Performance Improvement Techniques 599 5.14 Identifying and Eliminating Performance Bottlenecks 600 5.14.1 Program Pro.ling 600 5.14.2 Using a Pro.ler to Guide Optimization 603 5.15 Summary 606 Bibliographic Notes 607 Homework Problems 608 Solutions to Practice Problems 611 6 The Memory Hierarchy 617 6.1 Storage Technologies 619 6.1.1 Random Access Memory 619 6.1.2 Disk Storage 627 6.1.3 Solid State Disks 638 6.1.4 Storage Technology Trends 640 6.2 Locality 642 6.2.1 Locality of References to Program Data 644 6.2.2 Locality of Instruction Fetches 645 6.2.3 Summary of Locality 646 6.3 The Memory Hierarchy 647 6.3.1 Caching in the Memory Hierarchy 648 6.3.2 Summary of Memory Hierarchy Concepts 652 6.4 Cache Memories 652 6.4.1 Generic Cache Memory Organization 653 6.4.2 Direct-Mapped Caches 655 6.4.3 Set Associative Caches 662 6.4.4 Fully Associative Caches 664 6.4.5 Issues with Writes 668 6.4.6 Anatomy of a Real Cache Hierarchy 669 6.4.7 Performance Impact of Cache Parameters 669 6.5 Writing Cache-Friendly Code 671 6.6 Putting It Together: The Impact of Caches on Program Performance 677 6.6.1 The Memory Mountain 677 6.6.2 Rearranging Loops to Increase Spatial Locality 681 6.6.3 Exploiting Locality in Your Programs 685 6.7 Summary 686 Bibliographic Notes 686 Homework Problems 687 Solutions to Practice Problems 698 Part II Running Programs on a System -1 7 Linking 707 7.1 Compiler Drivers 709 7.2 Static Linking 710 7.3 Object Files 711 7.4 Relocatable Object Files 712 7.5 Symbols and Symbol Tables 713 7.6 Symbol Resolution 717 7.6.1 How Linkers Resolve Duplicate Symbol Names 718 7.6.2 Linking with Static Libraries 722 7.6.3 How Linkers Use Static Libraries to Resolve References 726 7.7 Relocation 727 7.7.1 Relocation Entries 728 7.7.2 Relocating Symbol References 729 7.8 Executable Object Files 733 7.9 Loading Executable Object Files 735 7.10 Dynamic Linking with Shared Libraries 736 7.11 Loading and Linking Shared Libraries from Applications 739 7.12 Position-Independent Code (PIC) 742 7.13 Library Interpositioning 745 7.13.1 Compile-Time Interpositioning 746 7.13.2 Link-Time Interpositioning 746 7.13.3 Run-Time Interpositioning 748 7.14 Tools for Manipulating Object Files 751 7.15 Summary 751 Bibliographic Notes 752 Homework Problems 752 Solutions to Practice Problems 755 8 Exceptional Control Flow 759 8.1 Exceptions 761 8.1.1 Exception Handling 762 8.1.2 Classes of Exceptions 764 8.1.3 Exceptions in Linux/x86-64 Systems 767 8.2 Processes 770 8.2.1 Logical Control Flow 770 8.2.2 Concurrent Flows 771 8.2.3 Private Address Space 772 8.2.4 User and Kernel Modes 772 8.2.5 Context Switches 774 8.3 System Call Error Handling 775 8.4 Process Control 776 8.4.1 Obtaining Process IDs 777 8.4.2 Creating and Terminating Processes 777 8.4.3 Reaping Child Processes 781 8.4.4 Putting Processes to Sleep 787 8.4.5 Loading and Running Programs 788 8.4.6 Using forkand execveto Run Programs 791 8.5 Signals 794 8.5.1 Signal Terminology 796 8.5.2 Sending Signals 797 8.5.3 Receiving Signals 800 8.5.4 Blocking and Unblocking Signals 802 8.5.5 Writing Signal Handlers 804 8.5.6 Synchronizing Flows to Avoid Nasty Concurrency Bugs 814 8.5.7 Explicitly Waiting for Signals 816 8.6 Nonlocal Jumps 819 8.7 Tools for Manipulating Processes 824 8.8 Summary 825 Bibliographic Notes 825 Homework Problems 826 Solutions to Practice Problems 833 9 Virtual Memory 839 9.1 Physical and Virtual Addressing 841 9.2 Address Spaces 842 9.3 VM as a Tool for Caching 843 9.3.1 DRAM Cache Organization 844 9.3.2 Page Tables 844 9.3.3 Page Hits 846 9.3.4 Page Faults 846 9.3.5 Allocating Pages 848 9.3.6 Locality to the Rescue Again 848 9.4 VM as a Tool for Memory Management 849 9.5 VM as a Tool for Memory Protection 850 9.6 Address Translation 851 9.6.1 Integrating Caches and VM 855 9.6.2 Speeding Up Address Translation with a TLB 855 9.6.3 Multi-Level Page Tables 857 9.6.4 Putting It Together: End-to-End Address Translation 859 9.7 Case Study: The Intel Core i7/Linux Memory System 863 9.7.1 Core i7 Address Translation 864 9.7.2 Linux Virtual Memory System 866 9.8 Memory Mapping 871 9.8.1 Shared Objects Revisited 871 9.8.2 The forkFunction Revisited 874 9.8.3 The execveFunction Revisited 874 9.8.4 User-Level Memory Mapping with the mmapFunction 875 9.9 Dynamic Memory Allocation 877 9.9.1 The mallocand freeFunctions 878 9.9.2 Why Dynamic Memory Allocation 881 9.9.3 Allocator Requirements and Goals 882 9.9.4 Fragmentation 884 9.9.5 Implementation Issues 884 9.9.6 Implicit Free Lists 885 9.9.7 Placing Allocated Blocks 887 9.9.8 Splitting Free Blocks 887 9.9.9 Getting Additional Heap Memory 888 9.9.10 Coalescing Free Blocks 888 9.9.11 Coalescing with Boundary Tags 889 9.9.12 Putting It Together: Implementing a Simple Allocator 892 9.9.13 Explicit Free Lists 900 9.9.14 Segregated Free Lists 901 9.10 Garbage Collection 903 9.10.1 Garbage Collector Basics 904 9.10.2 Mark&Sweep Garbage Collectors 905 9.10.3 Conservative Mark&Sweep for C Programs 907 9.11 Common Memory-Related Bugs in C Programs 908 9.11.1 Dereferencing Bad Pointers 908 9.11.2 Reading Uninitialized Memory 909 9.11.3 Allowing Stack Buffer Over.ows 909 9.11.4 Assuming That Pointers and the Objects They Point to Are the Same Size 910 9.11.5 Making Off-by-One Errors 910 9.11.6 Referencing a Pointer Instead of the Object It Points To 911 9.11.7 Misunderstanding Pointer Arithmetic 911 9.11.8 Referencing Nonexistent Variables 912 9.11.9 Referencing Data in Free Heap Blocks 912 9.11.10 Introducing Memory Leaks 913 9.12 Summary 913 Bibliographic Notes 914 Homework Problems 914 Solutions to Practice Problems 918 Part III Interaction and Communication between Programs -1 10 System-Level I/O 927 10.1 Unix I/O 928 10.2 Files 929 10.3 Opening and Closing Files 931 10.4 Reading and Writing Files 933 10.5 Robust Reading and Writing with the RioPackage 935 10.5.1 Rio Unbuffered Input and Output Functions 935 10.5.2 Rio Buffered Input Functions 936 10.6 Reading File Metadata 941 10.7 Reading Directory Contents 943 10.8 Sharing Files 944 10.9 I/O Redirection 947 10.10 Standard I/O 949 10.11 Putting It Together: Which I/O Functions Should I Use 949 10.12 Summary 951 Bibliographic Notes 952 Homework Problems 952 Solutions to Practice Problems 953 11 Network Programming 955 11.1 The Client-Server Programming Model 956 11.2 Networks 957 11.3 The Global IP Internet 962 11.3.1 IP Addresses 963 11.3.2 Internet Domain Names 965 11.3.3 Internet Connections 967 11.4 The Sockets Interface 970 11.4.1 Socket Address Structures 971 11.4.2 The socketFunction 972 11.4.3 The connectFunction 972 11.4.4 The bindFunction 973 11.4.5 The listenFunction 973 11.4.6 The acceptFunction 974 11.4.7 Host and Service Conversion 975 11.4.8 Helper Functions for the Sockets Interface 980 11.4.9 Example Echo Client and Server 982 11.5 Web Servers 986 11.5.1 Web Basics 986 11.5.2 Web Content 987 11.5.3 HTTP Transactions 988 11.5.4 Serving Dynamic Content 991 11.6 Putting It Together: The TinyWeb Server 994 11.7 Summary 1002 Bibliographic Notes 1003 Homework Problems 1003 Solutions to Practice Problems 1004 12 Concurrent Programming 1009 12.1 Concurrent Programming with Processes 1011 12.1.1 A Concurrent Server Based on Processes 1012 12.1.2 Pros and Cons of Processes 1013 12.2 Concurrent Programming with I/O Multiplexing 1015 12.2.1 A Concurrent Event-Driven Server Based on I/O Multiplexing 1018 12.2.2 Pros and Cons of I/O Multiplexing 1023 12.3 Concurrent Programming with Threads 1023 12.3.1 Thread Execution Model 1024 12.3.2 Posix Threads 1025 12.3.3 Creating Threads 1026 12.3.4 Terminating Threads 1026 12.3.5 Reaping Terminated Threads 1027 12.3.6 Detaching Threads 1027 12.3.7 Initializing Threads 1028 12.3.8 A Concurrent Server Based on Threads 1029 12.4 Shared Variables in Threaded Programs 1030 12.4.1 Threads Memory Model 1031 12.4.2 Mapping Variables to Memory 1032 12.4.3 Shared Variables 1033 12.5 Synchronizing Threads with Semaphores 1033 12.5.1 Progress Graphs 1037 12.5.2 Semaphores 1039 12.5.3 Using Semaphores for Mutual Exclusion 1040 12.5.4 Using Semaphores to Schedule Shared Resources 1042 12.5.5 Putting It Together: A Concurrent Server Based on Prethreading 1046 12.6 Using Threads for Parallelism 1051 12.7 Other Concurrency Issues 1058 12.7.1 Thread Safety 1058 12.7.2 Reentrancy 1061 12.7.3 Using Existing Library Functions in Threaded Programs 1062 12.7.4 Races 1063 12.7.5 Deadlocks 1065 12.8 Summary 1068 Bibliographic Notes 1068 Homework Problems 1069 Solutions to Practice Problems 1074 A Error Handling 1079 A.1 Error Handling in Unix Systems 1080 A.2 Error-Handling Wrappers 1081 References 1085 Index 1091 CS:APP 3e with scanned main text from the Chinese adaptation. Details and updates available at (in English and Chinese): https://forum.freemdict.com/t/topic/11216 Uploader's note: There are a few versions of electronic copies of the third edition available so far on the internet: - An EPUB file, likely scraped from somewhere similar to Pearson eText; - Some PDF file converted from the aforementioned EPUB file, the pages of which has no resemblance to the print copy; - A truePDF of the Global Edition, which the original authors complained about its modifications in exercises and problems in the online errata: https://csapp.cs.cmu.edu/3e/errata.html ; - A PDF, with the size of around 35 megabytes, of scanned, monochrome page images, with color front and back cover. The uploader made and uploaded this version to provide a reading experience similar to the original edition published in Norht America, with some tricks and tools to put several parts together. This file combines the color covers as well as references and index pages from the 35MB PDF file, the front matter (preface) PDF pages from CS:APP website, and main text from the book's adaptation in China. About the Chinese adaptation: Since book publishing in China are (nominally) restricted to those of the public sector, such foreign books are either sold directly or through importers, or as in this case, a domestic publisher obtains an authorization for an adaptation. The Chinese adaptation of CS:APP 3e, published by China Machine Press 机械工业出版社 in 2017, lacks certain sections of the original book, as what Pearson does in recent years, including in this case the English preface (replaced by a Chinese translation), list of references and index. But the main text remained mostly identical to the original North America edition. Some other adaptations or reprints of adaptations (such as a reprint of Weiss' Data Structure and Algorithms Analysis in C, an earlier adaptation published 2010 and a reprint in 2019) of Pearson textbooks in recent years, including those by China Machine Press and the Publishing House of Electronics Industory 电子工业出版社, among others, share similar issues. Some even redacted the original table of contents and a Chinese translation was put forward instead. About the source of the scanned main text: There is something called Chao Xing 超星 in China, which relies on libraries of colleges and public insitutions for book copies, and then scans the whole book for a digitized copy, many of which are for internal, proprietary use among those of the print copy providers. Some of these books are available online either within a group of higher education and research institutions or through access provided by public libraries. But such scanned data have had massive leaks in the past few years and in various forms, which enabled some third-party vendors to profit from the leaked database, by a single book (usually in the name of 代找, 'find (the scanned copy) on one's behalf') or in bulk. Some even provide access to a even larger collection of past leaks, known as 读秀 (Du Xiu) 2.0, 3.0, 4.0, etc. Such scanned copies have an SSID (SS means presumably 'super star', 超星) number, and the corresponding SSID for the adaptation used in this copy is 14679086. More details on the history as well as tools used to make this file can be found at cnblogs.com/stronghorse (in Chinese) or download the executables of the English edition at http://www.mediafire.com/folder/f0z2hexqdnr9a/Software . A brief description of making this copy: A few tools were used to implement the tricks to resemble the original book, including: - Extracting, renaming and reorganizing raw scanned image files. - Find the margins by inspecting and cropping the preface PDF. - Cut out the content, put it in a frame with the margins and other image processing using ComicEnhancerPro available from the aforementioned links to align the pages, in an attempt to smoothen the reading experience when switching between pages of different sources. - Make bookmarks of the covers and body text with `bookcontents.dat` using PdgCntEditor. - Combine and perform OCR of the processed front and back cover, the main text, references and index images using Pdg2Pic (no English version available). - Insert front matter PDF pages between the covers and the body text. - Edit the bookmarks of the combined PDF file with PdgCntEditor. \*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\*\* For courses in Computer Science and Programming Computer systems: A Programmer’s Perspective explains the underlying elements common among all computer systems and how they affect general application performance. Written from the programmer’s perspective, this book strives to teach readers how understanding basic elements of computer systems and executing real practice can lead them to create better programs. Spanning across computer science themes such as hardware architecture, the operating system, and systems software, the Third Edition serves as a comprehensive introduction to programming. This book strives to create programmers who understand all elements of computer systems and will be able to engage in any application of the field--from fixing faulty software, to writing more capable programs, to avoiding common flaws. It lays the groundwork for readers to delve into more intensive topics such as computer architecture, embedded systems, and cybersecurity. This book focuses on systems that execute an x86-64 machine code, and recommends that programmers have access to a Linux system for this course. Programmers should have basic familiarity with C or C++.