Computer Science from the Bottom Up

Computer Science from the Bottom Up

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.

Copyright © 2004–2025 Ian Wienand

Table of Contents

• Introduction
  • Welcome
    • Philosophy
    • Why from the bottom up?
    • Enabling Technologies
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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
• 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

List of Figures

• 1.1. Abstraction
• 1.2. Default Unix Files
• 1.3. Abstraction
• 1.4. A pipe in action
• 2.1. Masking
• 2.2. Types
• 3.1. The CPU
• 3.2. Inside the CPU
• 3.3. Reorder buffer example
• 3.4. Cache Associativity
• 3.5. Cache tags
• 3.6. Overview of handling an interrupt
• 3.7. Overview of a UHCI controller operation
• 3.8. A Hypercube
• 3.9. Acquire and Release semantics
• 4.1. The Operating System
• 4.2. The Operating System
• 4.3. Rings
• 4.4. x86 Segmentation Addressing
• 4.5. x86 segments
• 5.1. The Elements of a Process
• 5.2. The Stack
• 5.3. Process memory layout
• 5.4. Threads
• 5.5. The O(1) scheduler
• 6.1. Illustration of canonical addresses
• 6.2. Virtual memory pages
• 6.3. Virtual Address Translation
• 6.4. Segmentation
• 6.5. Linux address space layout
• 6.6. Linux Three Level Page Table
• 6.7. Illustration Itanium regions and protection keys
• 6.8. Illustration of Itanium TLB translation
• 6.9. Illustration of a hierarchical page-table
• 6.10. Itanium short-format VHPT implementation
• 6.11. Itanium PTE entry formats
• 7.1. Alignment
• 7.2. Alignment
• 8.1. ELF Overview
• 9.1. Memory access via the GOT
• 9.2.  sonames

List of Tables

• 1.1. Standard Files Provided by Unix
• 1.2. Standard Shell Redirection Facilities
• 2.1. Binary
• 2.2. 203 in base 10
• 2.3. 203 in base 2
• 2.4. Base 2 and 10 factors related to bytes
• 2.5. Convert 203 to binary
• 2.6. Truth table for not
• 2.7. Truth table for and
• 2.8. Truth table for or
• 2.9. Truth table for xor
• 2.10. Boolean operations in C
• 2.11. Hexadecimal, Binary and Decimal
• 2.12. Convert 203 to hexadecimal
• 2.13. Standard Integer Types and Sizes
• 2.14. Standard Scalar Types and Sizes
• 2.15. One’s Complement Addition
• 2.16. Two’s Complement Addition
• 2.17. IEEE Floating Point
• 2.18. Scientific Notation for 1.98765x10^6
• 2.19. Significands in binary
• 2.20. Example of normalising 0.375
• 3.1. Memory Hierarchy
• 9.1. Relocation Example
• 9.2. ELF symbol fields

List of Examples

• 1.1. Abstraction with function pointers
• 1.2. Abstraction in include/linux/virtio.h
• 1.3. Example of major and minor numbers
• 2.1. Using masks
• 2.2. Using flags
• 2.3. Example of warnings when types are not matched
• 2.4. Floats versus Doubles
• 2.5. Program to find first set bit
• 2.6. Examining Floats
• 2.7. Analysis of 8.45
• 3.1. Memory Ordering
• 4.1. getpid() example
• 4.2. PowerPC system call example
• 4.3. x86 system call example
• 5.1. Stack pointer example
• 5.2. pstree example
• 5.3. Zombie example process
• 5.4. Signals Example
• 7.1. Struct padding example
• 7.2. Stack alignment example
• 7.3. Page alignment manipulations
• 7.4. Hello World
• 7.5. Function Example
• 7.6. Compilation Example
• 7.7. Assembly Example
• 7.8. Readelf Example
• 7.9. Linking Example
• 7.10. Executable Example
• 8.1. The ELF Header
• 8.2. The ELF Header, as shown by readelf
• 8.3. Inspecting the ELF magic number
• 8.4. Investigating the entry point
• 8.5. The Program Header
• 8.6. Sections
• 8.7. Sections
• 8.8. Sections readelf output
• 8.9. Sections and Segments
• 8.10. Segments of an executable file
• 8.11. Creating and using a static library
• 8.12. Example of creating a core dump and using it with gdb
• 8.13. Example of stripping debugging information into separate files using objcopy
• 8.14. Example of using readelf and eu-readelf to examine a coredump.
• 8.15. Example of modinfo output
• 8.16. Putting module info into sections
• 8.17. Module symbols in .modinfo sections
• 8.18. The default linker script
• 8.19. Disassembley of program startup
• 8.20. Constructors and Destructors
• 9.1. Specifying Dynamic Libraries
• 9.2. Looking at dynamic libraries
• 9.3. Checking the program interpreter
• 9.4. Relocation as defined by ELF
• 9.5. Specifying Dynamic Libraries
• 9.6. Using the GOT
• 9.7. Relocations against the GOT
• 9.8. Hello World PLT example
• 9.9. Hello world main()
• 9.10. Hello world sections
• 9.11. Hello world PLT
• 9.12. Hello world GOT
• 9.13. Dynamic Segment
• 9.14. Code in the dynamic linker for setting up special values (from libc sysdeps/ia64/dl-machine.h)
• 9.15. Symbol definition from ELF
• 9.16. Examples of symbol bindings
• 9.17. Example of LD_PRELOAD
• 9.18. Example of symbol versioning

		Next
		Introduction

Links

https://www.bottomupcs.com/