The Sum of All Fears

Dive into Systems is a vivid introduction to computer organization, architecture, and operating systems that is already being used as a classroom textbook at more than 25 universities. This textbook is a crash course in the major hardware and software components of a modern computer system. Designed for use in a wide range of introductory-level computer science classes, it guides readers through the vertical slice of a computer so they can develop an understanding of the machine at various layers of abstraction. Early chapters begin with the basics of the C programming language often used in systems programming. Other topics explore the architecture of modern computers, the inner workings of operating systems, and the assembly languages that translate human-readable instructions into a binary representation that the computer understands. Later chapters explain how to optimize code for various architectures, how to implement parallel computing with shared memory, and how memory management works in multi-core CPUs. Accessible and easy to follow, the book uses images and hands-on exercise to break down complicated topics, including code examples that can be modified and executed. Acknowledgments Formal Reviewers Early Adopters 2019–2020 Early Adopters Preface What This Book Is About Ways to Use This Book Summary of Chapter Topics Example Uses of This Book Available Online Introduction What Is a Computer System? What Do Modern Computer Systems Look Like? What You Will Learn In This Book Getting Started with This Book Linux, C, and the GNU Compiler Other Types of Notation and Callouts Chapter 1: By the C, by the C, by the Beautiful C Getting Started Programming in C Compiling and Running C Programs Variables and C Numeric Types C Types Input/Output (printf and scanf) printf scanf Conditionals and Loops Boolean Values in C Loops in C Functions The Stack Arrays and Strings Introduction to Arrays Array Access Methods Arrays and Functions Introduction to Strings and the C String Library Structs Defining a Struct Type Declaring Variables of Struct Types Accessing Field Values Passing Structs to Functions Summary Chapter 2: A Deeper Dive into C Programming Parts of Program Memory and Scope C's Pointer Variables Pointer Variables Pointers and Functions Dynamic Memory Allocation Heap Memory malloc and free Dynamically Allocated Arrays and Strings Pointers to Heap Memory and Functions Arrays in C Single-Dimensional Arrays Two-Dimensional Arrays Strings and the String Library C's Support for Statically Allocated Strings (Arrays of char) Dynamically Allocating Strings Libraries for Manipulating C Strings and Characters C Structs Review of the C struct Type Pointers and Structs Pointer Fields in Structs Arrays of Structs Self-Referential Structs I/O in C (Standard and File) Standard Input/Output File Input/Output Using Text Files in C Standard and File I/O Functions in stdio.h Some Advanced C Features switch Statements Command Line Arguments The void * Type and Type Recasting Pointer Arithmetic C Libraries: Using, Compiling, and Linking Writing and Using Your Own C Libraries Compiling C to Assembly, and Compiling and Linking Assembly and C Code Summary Chapter 3: C Debugging Tools Debugging with GDB Getting Started with GDB Example GDB Sessions GDB Commands in Detail Keyboard Shortcuts in GDB Common GDB Commands Debugging Memory with Valgrind An Example Program with a Heap Memory Access Error How to Use Memcheck Advanced GDB Features GDB and make Attaching GDB to a Running Process Following a Process on a Fork Signal Control DDD Settings and Bug Fixes Debugging Assembly Code Using GDB to Examine Binary Code Using DDD to Debug at the Assembly Level GDB Assembly Code Debugging Commands and Examples Quick Summary of Common Commands for Assembly Debugging Debugging Multithreaded Programs with GDB GDB and Pthreads GDB Thread-Specific Commands Examples Summary Chapter 4: Binary and Data Representation Number Bases and Unsigned Integers Decimal Numbers Unsigned Binary Numbers Hexadecimal Storage Limitations Converting Between Bases Converting Between Binary and Hexadecimal Converting to Decimal Converting from Decimal Signed Binary Integers Signed Magnitude Two's Complement Binary Integer Arithmetic Addition Subtraction Multiplication and Division Integer Overflow Odometer Analogy Binary Integer Overflow Overflow Summary Overflow Consequences Bitwise Operators Bitwise AND Bitwise OR Bitwise XOR (Exclusive OR) Bitwise NOT Bit Shifting Integer Byte Order Real Numbers in Binary Fixed-Point Representation Floating-Point Representation Rounding Consequences Summary Chapter 5: What von Neumann Knew: Computer Architecture The Origin of Modern Computing Architectures The Turing Machine Early Electronic Computers So What Did von Neumann Know? The von Neumann Architecture The CPU The Processing Unit The Control Unit The Memory Unit The Input and Output (I/O) Units The von Neumann Machine in Action: Executing a Program Logic Gates Basic Logic Gates Other Logic Gates Circuits Arithmetic and Logic Circuits Arithmetic Circuits Control Circuits Storage Circuits Building a Processor: Putting It All Together The ALU The Register File The CPU The Processor's Execution of Program Instructions Clock-Driven Execution Putting It All Together: The CPU in a Full Computer Pipelining: Making the CPU Faster Advanced Pipelined Instruction Considerations Pipelining Consideration: Data Hazards Pipelining Hazards: Control Hazards Looking Ahead: CPUs Today Instruction-Level Parallelism Multicore and Hardware Multithreading Some Example Processors Summary Chapter 6: Under the C: Diving into Assembly The Benefits of Learning Assembly Higher-Level Abstraction Hides Valuable Program Details Some Computing Systems Are Too Resource-Constrained for Compilers Vulnerability Analysis Critical Code Sequences in System-Level Software What You Will Learn in the Coming Chapters Chapter 7: 64-bit x86 Assembly (x86-64) Diving into Assembly: Basics Registers Advanced Register Notation Instruction Structure An Example with Operands Instruction Suffixes Common Instructions Putting It All Together: A More Concrete Example Arithmetic Instructions Bit Shifting Instructions Bitwise Instructions The Load Effective Address Instruction Conditional Control and Loops Preliminaries if Statements in Assembly Loops in Assembly Functions in Assembly Function Parameters Tracing Through an Example Tracing Through main Recursion Animation: Observing How the Call Stack Changes Arrays Matrices Contiguous Two-Dimensional Arrays Noncontiguous Matrix structs in Assembly Data Alignment and structs Real World: Buffer Overflow Famous Examples of Buffer Overflow A First Look: The Guessing Game Taking a Closer Look (Under the C) Buffer Overflow: First Attempt A Smarter Buffer Overflow: Second Attempt Protecting Against Buffer Overflow Chapter 8: 32-bit x86 Assembly (IA32) Diving into Assembly: Basics Registers Advanced Register Notation Instruction Structure An Example with Operands Instruction Suffixes Common Instructions Putting It All Together: A More Concrete Example Arithmetic Instructions Bit Shifting Instructions Bitwise Instructions The Load Effective Address Instruction Conditional Control and Loops Preliminaries if Statements in Assembly Loops in Assembly Functions in Assembly Tracing Through an Example Tracing Through main Recursion Animation: Observing How the Call Stack Changes Arrays Matrices Contiguous Two-Dimensional Arrays Noncontiguous Matrix structs in Assembly Data Alignment and structs Real World: Buffer Overflow Famous Examples of Buffer Overflow A First Look: The Guessing Game Taking a Closer Look (Under the C) Buffer Overflow: First Attempt A Smarter Buffer Overflow: Second Attempt Protecting Against Buffer Overflow Chapter 9: ARM Assembly Diving into Assembly: Basics Registers Advanced Register Notation Instruction Structure An Example with Operands Common Instructions Putting It All Together: A More Concrete Example Arithmetic Instructions Common Arithmetic Instructions Bit Shifting Instructions Bitwise Instructions Conditional Control and Loops Preliminaries if Statements in Assembly Loops in Assembly Functions in Assembly Function Parameters Tracing Through an Example Tracing Through main Recursion Animation: Observing How the Call Stack Changes Arrays Matrices Contiguous Two-Dimensional Arrays Noncontiguous Matrix structs in Assembly Data Alignment and structs Real World: Buffer Overflow Famous Examples of Buffer Overflow A First Look: The Guessing Game Taking a Closer Look (Under the C) Buffer Overflow: First Attempt A Smarter Buffer Overflow: Second Attempt Protecting Against Buffer Overflow Chapter 10: Key Assembly Takeaways Common Features Further Reading Chapter 11: Storage and the Memory Hierarchy The Memory Hierarchy Storage Devices Primary Storage Secondary Storage Locality Locality Examples in Code From Locality to Caches Temporal Locality Spatial Locality CPU Caches Direct-Mapped Caches Cache Misses and Associative Designs Set Associative Caches Cache Analysis and Valgrind A First Cut: Theoretical Analysis and Benchmarking Cache Analysis in the Real World: Cachegrind Looking Ahead: Caching on Multicore Processors Cache Coherency The MSI Protocol Implementing Cache Coherency Protocols More About Multicore Caching Summary Chapter 12: Code Optimization What Compilers Already Do What Compilers Cannot Always Do: Benefits of Learning Code Optimization Partnering with Your Compiler: A Sample Program Code Optimization First Steps: Code Profiling Using Callgrind to Profile Loop-Invariant Code Motion Other Compiler Optimizations: Loop Unrolling and Function Inlining Function Inlining Loop Unrolling Memory Considerations Loop Interchange Some Other Compiler Optimizations for Improving Locality:Fission and Fusion Memory Profiling with Massif Key Takeaways and Summary Choose Good Data Structures and Algorithms Use Standard Library Functions Whenever Possible Optimize Based on Data and Not on Feelings Split Complex Code into Multiple Functions Prioritize Code Readability Pay Attention to Memory Use Compilers Are Constantly Improving Chatper 13: The Operating System How the OS Works and How It Runs OS Booting Getting the OS to Do Something: Interrupts and Traps Processes Multiprogramming and Context Switching Process State Creating (and Destroying) Processes fork exec exit and wait Virtual Memory Memory Addresses Virtual Address to Physical Address Translation Paging Memory Efficiency Interprocess Communication Signals Message Passing Shared Memory Summary and Other OS Functionality Chapter 14: Leveraging Shared Memory in the Multicore Era Programming Multicore Systems The Impact of Multicore Systems on Process Execution Expediting Process Execution with Threads Hello Threading! Writing Your First Multithreaded Program Creating and Joining Threads The Thread Function Running the Code Revisiting Scalar Multiplication Improving Scalar Multiplication: Multiple Arguments Synchronizing Threads Mutual Exclusion Semaphores Other Synchronization Constructs Measuring the Performance of Parallel Programs Parallel Performance Basics Advanced Topics Cache Coherence and False Sharing Caches on Multicore Systems False Sharing Fixing False Sharing Thread Safety Fixing Issues of Thread Safety Implicit Threading with OpenMP Common Pragmas Hello Threading: OpenMP Flavored A More Complex Example: CountSort in OpenMP Learning More About OpenMP Summary Key Takeaways Further Reading Chapter 15: Looking Ahead: Other Parallel Systems and Parallel Programming Models A Whole New World: Flynn's Taxonomy of Architecture Heterogeneous Computing: Hardware Accelerators, GPGPU Computing,and CUDA Hardware Accelerators GPU Architecture Overview GPGPU Computing CUDA Other Languages for GPGPU Programming Distributed Memory Systems, Message Passing, and MPI Parallel and Distributed Processing Models Communication Protocols Message Passing Interface MPI Hello World MPI Scalar Multiplication Distributed Systems Challenges To Exascale and Beyond: Cloud Computing, Big Data, and the Future of Computing Cloud Computing MapReduce Looking Toward the Future: Opportunities and Challenges Index