Computer Science from the Bottom Up
		Next

Computer Science from the Bottom Up

Ian Wienand

<ian@wienand.org>

A PDF version is available at http://www.bottomupcs.com/csbu.pdf. 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.

Abstract

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.

Table of Contents

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 Adressing
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. Convert 203 to binary
2.5. Bytes
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 flags
2.2. Example of warnings when types are not matched
2.3. Floats versus Doubles
2.4. Program to find first set bit
2.5. Examining Floats
2.6. 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. Example of creating a core dump and using it with gdb™
8.11. Example of stripping debugging information into separate files using objcopy™
8.12. Example of using readelf™ and eu-readelf™ to examine a coredump.
8.13. Segments of an executable file
8.14. Creating and using a static library
8.15. Disassembley of program startup
8.16. 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