Dive Into Systems: A Gentle Introduction to Computer Systems

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