Computer Science from the Bottom Up

✍ Scribed by Ian Wienand

• Publisher: Ian Wienand
• Year: 2022
• Tongue: English
• Leaves: 309
• Edition: 2022 Edition
• Category: Library

✦ Synopsis

Computer Science from the Bottom Up — A free, online book designed to teach computer science from the bottom end up. Topics covered include binary and binary logic, operating systems internals, toolchain fundamentals and system library fundamentals.

www.bottomupcs.com

✦ Table of Contents

Computer Science from the Bottom Up
Ian Wienand
Introduction
Welcome
Philosophy
Why from the bottom up?
Enabling Technologies
Chapter 1. General Unix and Advanced C
1  Everything is a file!
2 Implementing abstraction
2.1 Implementing abstraction with C
2.2 Libraries
3 File Descriptors
3.1 The Shell
3.1.1 Redirection
3.1.2 Implementing pipe
Chapter 2. Binary and Number Representation
1 Binary — the basis of computing
1.1 Binary Theory
1.1.1 Introduction
1.1.2 The basis of computing
1.1.3 Bits and Bytes
1.1.3.1 ASCII
1.1.3.2 Parity
1.1.3.3 16, 32 and 64 bit computers
1.1.3.4 Kilo, Mega and Giga Bytes
1.1.3.5 Kilo, Mega and Giga Bits
1.1.3.6 Conversion
1.1.4 Boolean Operations
1.1.4.1 Not
1.1.4.2 And
1.1.4.3 Or
1.1.4.4 Exclusive Or (xor)
1.1.5 How computers use boolean operations
1.1.6 Working with binary in C
1.2 Hexadecimal
1.3 Practical Implications
1.3.1 Use of binary in code
1.3.2 Masking and Flags
1.3.2.1 Masking
1.3.2.2 Flags
2 Types and Number Representation
2.1 C Standards
2.1.1 GNU C
2.2 Types
2.2.1 64 bit
2.2.2 Type qualifiers
2.2.3 Standard Types
2.2.4 Types in action
2.3 Number Representation
2.3.1 Negative Values
2.3.1.1 Sign Bit
2.3.1.2 One's Complement
2.3.1.3 Two's Complement
2.3.1.3.1 Sign-extension
2.3.2 Floating Point
2.3.2.1 Normalised Values
2.3.2.1.1 Normalisation Tricks
2.3.2.2 Bringing it together
Chapter 3. Computer Architecture
1 The CPU
1.1 Branching
1.2 Cycles
1.3 Fetch, Decode, Execute, Store
1.3.1 Looking inside a CPU
1.3.2 Pipelining
1.3.2.1 Branch Prediction
1.3.3 Reordering
1.4 CISC v RISC
1.4.1 EPIC
2 Memory
2.1 Memory Hierarchy
2.2 Cache in depth
2.2.1 Cache Addressing
3 Peripherals and buses
3.1 Peripheral Bus concepts
3.1.1 Interrupts
3.1.1.1 Saving state
3.1.1.2 Interrupts v traps and exceptions
3.1.1.3 Types of interrupts
3.1.1.4 Non-maskable interrupts
3.1.2 IO Space
3.2 DMA
3.3 Other Buses
3.3.1 USB
4 Small to big systems
4.1 Symmetric Multi-Processing
4.1.1 Cache Coherency
4.1.1.1 Cache exclusivity in SMP systems
4.1.2 Hyperthreading
4.1.3 Multi Core
4.2 Clusters
4.3 Non-Uniform Memory Access
4.3.1 NUMA Machine Layout
4.3.2 Cache Coherency
4.3.3 NUMA Applications
4.4 Memory ordering, locking and atomic operations
4.4.1 Processors and memory models
4.4.2 Locking
4.4.2.1 Locking difficulties
4.4.2.2 Locking strategies
4.4.3 Atomic Operations
Chapter 4. The Operating System
1 The role of the operating system
1.1 Abstraction of hardware
1.2 Multitasking
1.3 Standardised Interfaces
1.4 Security
1.5 Performance
2 Operating System Organisation
2.1 The Kernel
2.1.1 Monolithic v Microkernels
2.1.1.1 Modules
2.1.2 Virtualisation
2.1.2.1 Covert Channels
2.2 Userspace
3 System Calls
3.1 Overview
3.1.1 System call numbers
3.1.2 Arguments
3.1.3 The trap
3.1.4 libc
3.2 Analysing a system call
3.2.1 PowerPC
3.2.2 x86 system calls
4 Privileges
4.1 Hardware
4.1.1 Privilege Levels
4.1.1.1 386 protection model
4.1.1.2 Raising Privilege
4.1.1.3 Fast System Calls
4.2 Other ways of communicating with the kernel
4.2.1 ioctl
4.3 File Systems
Chapter 5. The Process
1 What is a process?
2 Elements of a process
2.1 Process ID
2.2 Memory
2.2.1 Code and Data
2.2.2 The Stack
2.2.3 The Heap
2.2.4 Memory Layout
2.3 File Descriptors
2.4 Registers
2.5 Kernel State
2.5.1 Process State
2.5.2 Priority
2.5.3 Statistics
3 Process Hierarchy
4 Fork and Exec
4.1 Fork
4.2 Exec
4.3 How Linux actually handles fork and exec
4.3.1  clone
4.3.1.1 Threads
4.3.1.2 Copy on write
4.4 The init process
4.4.1 Zombie example
5 Context Switching
6 Scheduling
6.1 Preemptive v co-operative scheduling
6.2 Realtime
6.3 Nice value
6.4 A brief look at the Linux Scheduler
7 The Shell
8 Signals
8.1 Example
Chapter 6. Virtual Memory
1 What Virtual Memory isn't
2 What virtual memory is
2.1 64 bit computing
2.1.1 Canonical Addresses
2.2 Using the address space
3 Pages
4 Physical Memory
5 Pages + Frames = Page Tables
6 Virtual Addresses
6.1 Page
6.2 Offset
6.3 Virtual Address Translation
7 Consequences of virtual addresses, pages and page tables
7.1 Individual address spaces
7.2 Protection
7.3 Swap
7.3.1 mmap
7.4 Sharing memory
7.5 Disk Cache
7.5.1 Page Cache
8 Hardware Support
8.1 Physical v Virtual Mode
8.1.1 Issues with segmentation
8.2 The TLB
8.2.1 Page Faults
8.2.1.1 Finding the page table
8.2.2 Other page related faults
8.3 TLB Management
8.3.1 Flushing the TLB
8.3.2 Hardware v Software loaded TLB
9 Linux Specifics
9.1 Address Space Layout
9.2 Three Level Page Table
10 Hardware support for virtual memory
10.1 x86-64
10.2 Itanium
10.2.1 Address spaces
10.2.1.1 Protection Keys
10.2.2 Itanium Hardware Page-Table Walker
10.2.2.1 Virtual Linear Page-Table
10.2.2.2 Virtual Hash Table
Chapter 7. The Toolchain
1 Compiled v Interpreted Programs
1.1 Compiled Programs
1.2 Interpreted programs
1.2.1 Virtual Machines
2 Building an executable
3 Compiling
3.1 The process of compiling
3.1.1 C code
3.2 Syntax
3.3 Assembly Generation
3.3.1 Alignment
3.3.1.1 Structure Padding
3.3.1.2 Cache line alignment
3.3.1.3 Space - Speed Trade off
3.3.1.4 Making Assumptions
3.3.1.5 C Idioms with alignment
3.4 Optimisation
3.4.1 General Optimising
3.4.2 Unrolling loops
3.4.3 Inlining functions
3.4.4 Branch Prediction
4 Assembler
5 Linker
5.1 Symbols
5.1.1 Symbols
5.1.2 Symbol Visibility
5.2 The linking process
6 A practical example
6.1 Compiling
6.2 Assembly
6.3 Linking
6.4 The Executable
Chapter 8. Behind the process
1 Review of executable files
2 Representing executable files
2.1 Three Standard Sections
2.2 Binary Format
2.3 Binary Format History
2.3.1 a.out
2.3.2 COFF
3 ELF
3.1 ELF File Header
3.2 Symbols and Relocations
3.3 Sections and Segments
3.3.1 Segments
3.3.2 Sections
3.3.3 Sections and Segments together
4 ELF Executables
5 Libraries
5.1 Static Libraries
5.1.1 Inside static libraries
5.1.2 Static Linking Drawbacks
5.2 Shared Libraries
6 Extending ELF concepts
6.1 Debugging
6.1.1 Symbols and Debugging Information
6.1.2 Inside coredumps
6.2 Custom sections
6.3 Linker Scripts
7 ABIs
7.1 Byte Order
7.2 Calling Conventions
7.2.1 Passing parameters
7.2.2 Function Descriptors
8 Starting a process
8.1 Kernel communication to programs
8.1.1 Kernel Library
8.2 Starting the program
Chapter 9. Dynamic Linking
1 Code Sharing
1.1 Dynamic Library Details
1.2 Including libraries in an executable
1.2.1 Compilation
1.2.2 Linking
2 The Dynamic Linker
2.1 Relocations
2.1.1 Relocations in action
2.2 Position Independence
3 Global Offset Tables
3.1 The Global Offset Table
3.1.1 The GOT in action
4 Libraries
4.1 The Procedure Lookup Table
4.1.1 The PLT in action
4.1.2 Summary
5 Working with libraries and the linker
5.1 Library versions
5.1.1  sonames
5.1.1.1 How the dynamic linker looks up libraries
5.2 Finding symbols
5.2.1 Dynamic Symbol Table
5.2.2 Symbol Binding
5.2.2.1 Overriding symbols
5.2.2.1.1 Weak symbols over time
5.2.2.2 Specifying binding order
5.2.2.3 Symbol Versioning
Glossary