Study Notes of CS:APP (Till 1.3, Regularly Updated)

2023-11-28 19:41:46

Study Notes of the Book CS:APP and its ICS+ Course 15-213

Book & Course Information

Instructors

Randal E. Bryant and David R. O'Hallaron

Textbooks

Randal E. Bryant and David R. O'Halloron,

Computer Systems: A Programmer's Perspective, Third Edition, Pearson, 2016

Brian W. Kernighan and Dennis M. Ritchie,

The C Programming Language, Second Edition, Prentice Hall, 1988

Home

http://www.cs.cmu.edu/~213

Related Materials

Reading Notes:

https://www.cnblogs.com/dongxb/tag/%E8%AE%A1%E7%AE%97%E6%9C%BA%E5%9F%BA%E7%A1%80/default.html

My Foreword

Content Covered

Currently the common set of the five system courses suggested.

How I Take Notes

First, read a section of the book with the assistance of eudic and take down the key points. Second, watch the corresponding 15-213 video if available and add the complement provided by the lecture PPT.

Course Overview: Topics

Programs and Data

• Bits operations, arithmetic, assembly language programs

• Representation of C control and data structures

• Includes aspects of architecture and compilers

The Memory Hierarchy

• Memory technology, memory hierarchy, caches, disks, locality

• Includes aspects of architecture and OS

Exceptional Control Flow

• Hardware exceptions, processes, process control, Unix signals, nonlocal jumps

• Includes aspects of compilers, OS, and architecture

Virtual Memory

• Virtual memory, address translation, dynamic storage allocation

• Includes aspects of architecture and OS

Networking, and Concurrency

• High level and low-level I/O, network programming

• Internet services, Web servers

• concurrency, concurrent server design, threads

• I/O multiplexing with select

• Includes aspects of networking, OS, and architecture

Chapter 1 A Tour of Computer Systems

A computer system consists of hardware and systems software that work together to run application programs.

1.1 Information Is Bits + Context

A program begins life as a source program (or source file). The source program is a sequence of bits, each with a value of 0 or 1, organized in 8-bit chunks called bytes. Each byte represents some text character in the program.

Most computer systems represent text characters using the ASCII standard that represents each character with a unique byte-size integer value.

Text files: files that consist exclusively of ASCII characters. Binary files: all other files.

A fundamental idea: All information in a system is represented as a bunch of bits. The only thing that distinguishes different data objects is the context in which we view them.

1.2 Programs Are Translated by Other Programs into Different Forms

In order to run .c on the system, the individual C statements must be translated by other programs

into a sequence of low-level machine-language instructions. These instructions are then packaged in an executable object program (or an executable object file) and stored as a binary disk file.

The compilation system: the programs that perform the four phases (preprocessor, compiler, assembler, and linker).

• Preprocessing phase. The preprocessor (cpp) modifies the original C program according to directives that begin with the '#' character. The result is another C program, typically with the .i suffix.

• Compilation phase. The compiler (cc1) translates .i into .s, which contains an assembly-language program. Assembly language is useful because it provides a common output language for different compilers for different high-level languages.

• Assembly phase. Next, the assembler (as) translates .s into machine language instructions, packages them in a relocatable object program, and stores the result in the object file .o.

• Linking phase. The printf function is part of the standard C library provided by every C compiler. The printf function resides in a separate precompiled object file printf.o, which is merged with our .o program by the linker (ld). The result is an executable object file (or simply executable) that is ready to be loaded into memory and executed by the system.

1.3 It Pays to Understand How Compilation Systems Work

Some important reasons:

• Optimizing program performance.

• Understanding link-time errors.

• Avoiding security holes.

• Buffer overflow vulnerabilities

1.4 Processors Read and Interpret Instructions Stored in Memory

1.4.1 Hardware Organization of a System

1.4.2 Running the hello Program

1.5 Caches Matter

1.6 Storage Devices Form a Hierarchy

1.7 The Operating System Manages the Hardware

1.7.1 Processes

1.7.2 Threads

1.7.3 Virtual Memory

1.7.4 Files

1.8 Systems Communicate with Other Systems Using Networks

1.9 Important Themes

1.9.1 Amdahl's Law

1.9.2 Concurrency and Parallelism

1.9.3 The Importance of Abstractions in Computer Systems

1.10 Summary

Part II Program Structure and Execution

Chapter 2 Representing and Manipulating Information

2.1 Information Storage

2.1.1 Hexadecimal Notation

2.1.2 Data Sizes

2.1.3 Addressing and Byte Ordering

2.1.4 Representing Strings

2.1.5 Representing Code

2.1.6 Introduction to Boolean Algebra

2.1.7 Bit-Level Operations in C

2.1.8 Logical Operations in C

2.1.9 Shift Operations in C

2.2 Integer Representations

2.2.1 Integral Data Types

2.2.2 Unsigned Encodings

2.2.3 Two's-Complement Encodings

2.2.4 Conversions between Signed and Unsigned

2.2.5 Signed versus Unsigned in C

2.2.6 Expanding the Bit Representation of a Number

2.2.7 Truncating Numbers

2.2.8 Advice on Signed versus Unsigned

2.3 Integer Arithmetic

2.3.1 Unsigned Addition

2.3.2 Two's-Complement Addition

2.3.3 Two's-Complement Negation

2.3.4 Unsigned Multiplication

2.3.5 Two's-Complement Multiplication

2.3.6 Multiplying by Constants

2.3.7 Dividing by Powers of 2

2.3.8 Final Thoughts on Integer Arithmetic

2.4 Floating Point

2.4.1 Fractional Binary Numbers

2.4.2 IEEE Floating-Point Representation

2.4.3 Example Numbers

2.4.4 Rounding

2.4.5 Floating-Point Operations

2.4.6 Floating Point in C

2.5 Summary

Chapter 3 Machine-Level Representation of Programs

3.1 A Historical Perspective

3.2 Program Encodings

3.2.1 Machine-Level Code

3.2.2 Code Examples

3.2.3 Notes on Formatting

3.3 Data Formats

3.4 Accessing Information

3.4.1 Operand Specifiers

3.4.2 Data Movement Instructions

3.4.3 Data Movement Example

3.4.4 Pushing and Popping Stack Data

3.5 Arithmetic and Logical Operations

3.5.1 Load Effective Address

3.5.2 Unary and Binary Operations

3.5.3 Shift Operations

3.5.4 Discussion

3.5.5 Special Arithmetic Operations

3.6 Control

3.6.1 Condition Codes

3.6.2 Accessing the Condition Codes

3.6.3 Jump Instructions

3.6.4 Jump Instruction Encodings

3.6.5 Implementing Conditional Branches with Conditional Control

3.6.6 Implementing Conditional Branches with Conditional Moves

3.6.7 Loops

3.6.8 Switch Statements

3.7 Procedures

3.7.1 The Run-Time Stack

3.7.2 Control Transfer

3.7.3 Data Transfer

3.7.4 Local Storage on the Stack

3.7.5 Local Storage in Registers

3.7.6 Recursive Procedures

3.8 Array Allocation and Access

3.8.1 Basic Principles

3.8.2 Pointer Arithmetic

3.8.3 Nested Arrays

3.8.4 Fixed-Size Arrays

3.8.5 Variable-Size Arrays

3.9 Heterogeneous Data Structures

3.9.1 Structures

3.9.2 Unions

3.9.3 Data Alignment

3.10 Combining Control and Data in Machine-Level Programs

3.10.1 Understanding Pointers

3.10.2 Life in the RealWorld: Using the gdb Debugger

3.10.3 Out-of-Bounds Memory References and Buffer Overflow

3.10.4 Thwarting Buffer Overflow Attacks

3.10.5 Supporting Variable-Size Stack Frames

3.11 Floating-Point Code

3.11.1 Floating-Point Movement and Conversion Operations

3.11.2 Floating-Point Code in Procedures

3.11.3 Floating-Point Arithmetic Operations

3.11.4 Defining and Using Floating-Point Constants

3.11.5 Using Bitwise Operations in Floating-Point Code

3.11.6 Floating-Point Comparison Operations

3.11.7 Observations about Floating-Point Code

3.12 Summary

Chapter 4

Chapter 5

Chapter 6 The Memory Hierarchy

6.1 Storage Technologies

6.1.1 Random Access Memory

6.1.2 Disk Storage

6.1.3 Solid State Disks

6.1.4 Storage Technology Trends

6.2 Locality

6.2.1 Locality of References to Program Data

6.2.2 Locality of Instruction Fetches

6.2.3 Summary of Locality

6.3 The Memory Hierarchy

6.3.1 Caching in the Memory Hierarchy

6.3.2 Summary of Memory Hierarchy Concepts

6.4 Cache Memories

6.4.1 Generic Cache Memory Organization

6.4.2 Direct-Mapped Caches

6.4.3 Set Associative Caches

6.4.4 Fully Associative Caches

6.4.5 Issues with Writes

6.4.6 Anatomy of a Real Cache Hierarchy

6.4.7 Performance Impact of Cache Parameters

6.5 Summary

Part III Running Programs on a System

Chapter 1

Chapter 2

Chapter 3