Computer Science from the Bottom Up

Ian Wienand

A PDF version is available at https://www.bottomupcs.com/csbu.pdf. A EPUB version is available at https://www.bottomupcs.com/csbu.epub The original souces are available at https://github.com/ianw/bottomupcs

This work is licensed under the Creative Commons Attribution-ShareAlike License. To view a copy of this license, visit http://creativecommons.org/licenses/by-sa/3.0/ or send a letter to Creative Commons, 559 Nathan Abbott Way, Stanford, California 94305, USA.

Table of Contents

Introduction
- Welcome
Chapter 1. General Unix and Advanced C
Chapter 2. Binary and Number Representation
- 1 Binary — the basis of computing
- 2 Types and Number Representation
Chapter 3. Computer Architecture
Chapter 4. The Operating System
Chapter 5. The Process
Chapter 6. Virtual Memory
Chapter 7. The Toolchain
Chapter 8. Behind the process
Chapter 9. Dynamic Linking
Glossary

List of Figures

1.1 Abstraction
3.1 Default Unix Files
3.2 Abstraction
3.1.2.1 A pipe in action
1.3.2.1.1 Masking
2.2.1 Types
1.1 The CPU
1.3.1.1 Inside the CPU
1.3.3.1 Reorder buffer example
2.2.1 Cache Associativity
2.2.1.1 Cache tags
3.1.1.1 Overview of handling an interrupt
3.3.1.1 Overview of a UHCI controller operation
4.3.1.1 A Hypercube
4.4.1 Acquire and Release semantics
2.1 The Operating System
2.1.2.1 The Operating System
4.1.1.1 Rings
4.1.1.3.1 x86 Segmentation Addressing
4.1.1.3.2 x86 segments
2.1 The Elements of a Process
2.2.2.1 The Stack
2.2.4.1 Process memory layout
4.3.1.1.1 Threads
6.4.1 The O(1) scheduler
2.1.1.1 Illustration of canonical addresses
3.1 Virtual memory pages
6.3.1 Virtual Address Translation
8.1.1.1 Segmentation
9.1.1 Linux address space layout
9.2.1 Linux Three Level Page Table
10.2.1.1 Illustration Itanium regions and protection keys
10.2.1.2 Illustration of Itanium TLB translation
10.2.2.1.1 Illustration of a hierarchical page-table
10.2.2.1.2 Itanium short-format VHPT implementation
10.2.2.1.3 Itanium PTE entry formats
3.3.1.1 Alignment
3.3.1.1.1 Alignment
3.1 ELF Overview
3.1.1 Memory access via the GOT
5.1.1.1 sonames

List of Examples

2.1.1 Abstraction with function pointers
2.1.2 Abstraction in include/linux/virtio.h
3.1 Example of major and minor numbers
1.3.2.1.1 Using masks
1.3.2.2.1 Using flags
2.2.4.1 Example of warnings when types are not matched
2.3.2.1 Floats versus Doubles
2.3.2.1.1.1 Program to find first set bit
2.3.2.2.1 Examining Floats
2.3.2.2.2 Analysis of 8.45
4.4.1 Memory Ordering
3.2.1 getpid() example
3.2.1.1 PowerPC system call example
3.2.2.1 x86 system call example
2.2.2.1 Stack pointer example
3.1 pstree example
4.4.1.1 Zombie example process
8.1.1 Signals Example
3.3.1.1.1 Struct padding example
3.3.1.4.1 Stack alignment example
3.3.1.5.1 Page alignment manipulations
6.1 Hello World
6.2 Function Example
6.1.1 Compilation Example
6.2.1 Assembly Example
6.2.2 Readelf Example
6.3.1 Linking Example
6.4.1 Executable Example
3.1.1 The ELF Header
3.1.2 The ELF Header, as shown by readelf
3.1.3 Inspecting the ELF magic number
3.1.4 Investigating the entry point
3.3.1.1 The Program Header
3.3.2.1 Sections
3.3.2.2 Sections
3.3.2.3 Sections readelf output
3.3.3.1 Sections and Segments
4.1 Segments of an executable file
5.1.1.1 Creating and using a static library
6.1.1 Example of creating a core dump and using it with gdb
6.1.1.1 Example of stripping debugging information into separate files using objcopy
6.1.2.1 Example of using readelf and eu-readelf to examine a coredump.
6.2.1 Example of modinfo output
6.2.2 Putting module info into sections
6.2.3 Module symbols in .modinfo sections
6.3.1 The default linker script
8.2.1 Disassembley of program startup
8.2.2 Constructors and Destructors
1.2.2.1 Specifying Dynamic Libraries
1.2.2.2 Looking at dynamic libraries
2.1 Checking the program interpreter
2.1.1 Relocation as defined by ELF
2.1.1.1 Specifying Dynamic Libraries
3.1.1.1 Using the GOT
3.1.1.2 Relocations against the GOT
4.1.1.1 Hello World PLT example
4.1.1.2 Hello world main()
4.1.1.3 Hello world sections
4.1.1.4 Hello world PLT
4.1.1.5 Hello world GOT
4.1.1.6 Dynamic Segment
4.1.1.7 Code in the dynamic linker for setting up special values (from libc sysdeps/ia64/dl-machine.h)
5.2.1.1 Symbol definition from ELF
5.2.2.1 Examples of symbol bindings
5.2.2.1.1 Example of LD_PRELOAD
5.2.2.3.1 Example of symbol versioning

		Next
		Introduction