https://www.bottomupcs.com Computer Science from the Bottom Up Next --------------------------------------------------------------------- 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 Copyright (c) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018, 2019 Ian Wienand 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 o Philosophy o Why from the bottom up? o Enabling Technologies * 1. General Unix and Advanced C + Everything is a file! + Implementing abstraction o Implementing abstraction with C o Libraries + File Descriptors o The Shell * 2. Binary and Number Representation + Binary -- the basis of computing o Binary Theory o Hexadecimal o Practical Implications + Types and Number Representation o C Standards o Types o Number Representation * 3. Computer Architecture + The CPU o Branching o Cycles o Fetch, Decode, Execute, Store o CISC v RISC + Memory o Memory Hierarchy o Cache in depth + Peripherals and buses o Peripheral Bus concepts o DMA o Other Buses + Small to big systems o Symmetric Multi-Processing o Clusters o Non-Uniform Memory Access o Memory ordering, locking and atomic operations * 4. The Operating System + The role of the operating system o Abstraction of hardware o Multitasking o Standardised Interfaces o Security o Performance + Operating System Organisation o The Kernel o Userspace + System Calls o Overview o Analysing a system call + Privileges o Hardware o Other ways of communicating with the kernel o File Systems * 5. The Process + What is a process? + Elements of a process o Process ID o Memory o File Descriptors o Registers o Kernel State + Process Hierarchy + Fork and Exec o Fork o Exec o How Linux actually handles fork and exec o The init process + Context Switching + Scheduling o Preemptive v co-operative scheduling o Realtime o Nice value o A brief look at the Linux Scheduler + The Shell + Signals o Example * 6. Virtual Memory + What Virtual Memory isn't + What virtual memory is o 64 bit computing o Using the address space + Pages + Physical Memory + Pages + Frames = Page Tables + Virtual Addresses o Page o Offset o Virtual Address Translation + Consequences of virtual addresses, pages and page tables o Individual address spaces o Protection o Swap o Sharing memory o Disk Cache + Hardware Support o Physical v Virtual Mode o The TLB o TLB Management + Linux Specifics o Address Space Layout o Three Level Page Table + Hardware support for virtual memory o x86-64 o Itanium * 7. The Toolchain + Compiled v Interpreted Programs o Compiled Programs o Interpreted programs + Building an executable + Compiling o The process of compiling o Syntax o Assembly Generation o Optimisation + Assembler + Linker o Symbols o The linking process + A practical example o Compiling o Assembly o Linking o The Executable * 8. Behind the process + Review of executable files + Representing executable files o Three Standard Sections o Binary Format o Binary Format History + ELF o ELF File Header o Symbols and Relocations o Sections and Segments + ELF Executables + Libraries o Static Libraries o Shared Libraries + Extending ELF concepts o Debugging o Custom sections o Linker Scripts + ABIs o Byte Order o Calling Conventions + Starting a process o Kernel communication to programs o Starting the program * 9. Dynamic Linking + Code Sharing o Dynamic Library Details o Including libraries in an executable + The Dynamic Linker o Relocations o Position Independence + Global Offset Tables o The Global Offset Table + Libraries o The Procedure Lookup Table + Working with libraries and the linker o Library versions o Finding symbols * 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