Ian Wienand - Computer Science From The Bottom Up
Computer Science from the Bottom UpIan Wienand
Computer Science from the Bottom UpIan WienandA 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/bottomupcsCopyright 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012, 2013, 2014, 2015, 2016, 2017, 2018,2019 Ian WienandThis 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 ContentsIntroduction . xiWelcome . xiPhilosophy . xiWhy from the bottom up? . xiEnabling Technologies . xi1. General Unix and Advanced C . 1Everything is a file! . 1Implementing abstraction . 2Implementing abstraction with C . 2Libraries . 4File Descriptors . 5The Shell . 82. Binary and Number Representation . 11Binary — the basis of computing . 11Binary Theory . 11Hexadecimal . 17Practical Implications . 19Types and Number Representation . 21C Standards . 21Types . 22Number Representation . 273. Computer Architecture . 36The CPU . 36Branching . 37Cycles . 37Fetch, Decode, Execute, Store . 37CISC v RISC . 40Memory . 42Memory Hierarchy . 42Cache in depth . 43Peripherals and buses . 47Peripheral Bus concepts . 47DMA . 49Other Buses . 50Small to big systems . 52Symmetric Multi-Processing . 52Clusters . 54Non-Uniform Memory Access . 55Memory ordering, locking and atomic operations . 584. The Operating System . 63The role of the operating system . 63Abstraction of hardware . 63Multitasking . 63Standardised Interfaces . 63Security . 64Performance . 64iii
Computer Sciencefrom the Bottom UpOperating System Organisation . 64The Kernel . 65Userspace . 70System Calls . 70Overview . 70Analysing a system call . 71Privileges . 77Hardware . 77Other ways of communicating with the kernel . 82File Systems . 835. The Process . 84What is a process? . 84Elements of a process . 84Process ID . 84Memory . 85File Descriptors . 90Registers . 90Kernel State . 90Process Hierarchy . 91Fork and Exec . 91Fork . 91Exec . 92How Linux actually handles fork and exec . 92The init process . 94Context Switching . 96Scheduling . 96Preemptive v co-operative scheduling . 96Realtime . 97Nice value . 97A brief look at the Linux Scheduler . 97The Shell . 98Signals . 99Example . 1006. Virtual Memory . 102What Virtual Memory isn't . 102What virtual memory is . 10264 bit computing . 102Using the address space . 103Pages . 104Physical Memory . 104Pages Frames Page Tables . 105Virtual Addresses . 105Page . 105Offset . 105Virtual Address Translation . 106Consequences of virtual addresses, pages and page tables . 107Individual address spaces . 107Protection . 107Swap . 108iv
Computer Sciencefrom the Bottom UpSharing memory . 108Disk Cache . 109Hardware Support . 109Physical v Virtual Mode . 109The TLB . 111TLB Management . 112Linux Specifics . 113Address Space Layout . 114Three Level Page Table . 114Hardware support for virtual memory . 116x86-64 . 116Itanium . 1167. The Toolchain . 124Compiled v Interpreted Programs . 124Compiled Programs . 124Interpreted programs . 124Building an executable . 125Compiling . 125The process of compiling . 125Syntax . 125Assembly Generation . 126Optimisation . 130Assembler . 131Linker . 131Symbols . 132The linking process . 133A practical example . 133Compiling . 134Assembly . 135Linking . 136The Executable . 1378. Behind the process . 141Review of executable files . 141Representing executable files . 141Three Standard Sections . 141Binary Format . 141Binary Format History . 142ELF . 142ELF File Header . 143Symbols and Relocations . 145Sections and Segments . 145ELF Executables . 150Libraries . 151Static Libraries . 152Shared Libraries . 154Extending ELF concepts . 154Debugging . 154Custom sections . 158Linker Scripts . 160v
Computer Sciencefrom the Bottom UpABIs . 161Byte Order . 162Calling Conventions . 162Starting a process . 162Kernel communication to programs . 163Starting the program . 1649. Dynamic Linking . 169Code Sharing . 169Dynamic Library Details . 169Including libraries in an executable . 169The Dynamic Linker . 171Relocations . 171Position Independence . 173Global Offset Tables . 173The Global Offset Table . 174Libraries . 177The Procedure Lookup Table . 177Working with libraries and the linker . 185Library versions . 185Finding symbols . 188Glossary . 194vi
List of Figures1.1. Abstraction . 21.2. Default Unix Files . 61.3. Abstraction . 71.4. A pipe in action . 102.1. Masking . 192.2. Types . 233.1. The CPU . 363.2. Inside the CPU . 383.3. Reorder buffer example . 403.4. Cache Associativity . 443.5. Cache tags . 463.6. Overview of handling an interrupt . 483.7. Overview of a UHCI controller operation . 513.8. A Hypercube . 573.9. Acquire and Release semantics . 604.1. The Operating System . 654.2. The Operating System . 684.3. Rings . 784.4. x86 Segmentation Addressing . 804.5. x86 segments . 815.1. The Elements of a Process . 845.2. The Stack . 865.3. Process memory layout . 895.4. Threads . 935.5. The O(1) scheduler . 986.1. Illustration of canonical addresses . 1036.2. Virtual memory pages . 1046.3. Virtual Address Translation . 1066.4. Segmentation . 1106.5. Linux address space layout . 1146.6. Linux Three Level Page Table . 1156.7. Illustration Itanium regions and protection keys . 1176.8. Illustration of Itanium TLB translation . 1186.9. Illustration of a hierarchical page-table . 1206.10. Itanium short-format VHPT implementation . 1216.11. Itanium PTE entry formats . 1227.1. Alignment . 1267.2. Alignment . 1288.1. ELF Overview . 1439.1. Memory access via the GOT . 1759.2. sonames . 187vii
List of Tables1.1. Standard Files Provided by Unix . 51.2. Standard Shell Redirection Facilities . 92.1. Binary . 112.2. 203 in base 10 . 112.3. 203 in base 2 . 112.4. Base 2 and 10 factors related to bytes . 142.5. Convert 203 to binary . 152.6. Truth table for not . 162.7. Truth table for and . 162.8. Truth table for or . 162.9. Truth table for xor . 162.10. Boolean operations in C . 172.11. Hexadecimal, Binary and Decimal . 182.12. Convert 203 to hexadecimal . 182.13. Standard Integer Types and Sizes . 242.14. Standard Scalar Types and Sizes . 242.15. One's Complement Addition . 282.16. Two's Complement Addition . 282.17. IEEE Floating Point . 302.18. Scientific Notation for 1.98765x10 6 . 302.19. Significands in binary . 302.20. Example of normalising 0.375 . 313.1. Memory Hierarchy . 429.1. Relocation Example . 1729.2. ELF symbol fields . 188viii
List of Examples1.1. Abstraction with function pointers . 21.2. Abstraction in include/linux/virtio.h . 41.3. Example of major and minor numbers . 82.1. Using masks . 202.2. Using flags . 202.3. Example of warnings when types are not matched . 262.4. Floats versus Doubles . 312.5. Program to find first set bit . 322.6. Examining Floats . 332.7. Analysis of 8.45 . 343.1. Memory Ordering . 594.1. getpid() example . 714.2. PowerPC system call example . 724.3. x86 system call example . 755.1. Stack pointer example . 875.2. pstree example . 915.3. Zombie example process . 955.4. Signals Example . 1007.1. Struct padding example . 1277.2. Stack alignment example . 1297.3. Page alignment manipulations . 1297.4. Hello World . 1337.5. Function Example . 1347.6. Compilation Example . 1347.7. Assembly Example . 1357.8. Readelf Example . 1357.9. Linking Example . 1367.10. Executable Example . 1388.1. The ELF Header .
Welcome to Computer Science from the Bottom Up Philosophy In a nutshell, what you are reading is intended to be a shop class for computer science. Young computer science students are taught to "drive" the computer; but where do you go to learn what is under the hood? Trying to understand the operating system is
1. a. Ian loves looking at the country from the ocean. b. Ian loves looking at the country from the sky. 2. a. Ian loves the feeling of security. b. Ian loves the feeling of freedom. 3. a. Ian is a lucky young man. b. Ian is a happy young man. 4. a. When Ian flies, he is sad. b. When Ian flies, he is excited. 5. a. Ian sees lions. He is .
This handbook supplement applies to students entering the fourth year of their degree in Computer Science, Mathematics & Computer Science or Computer Science . Undergraduate Course Handbook 1.2 Mathematics & Computer Science The Department of Computer Science offers the following joint degrees with the Department of Mathematics: BA .
Going Postal-Thud! -Wintersmith (for younger readers) Making Money The Science of Discworld(with Ian Stowart and Jack Cohen) The Science of Discworld II: The Globe (with Ian Stewart and Jack Cohen) The Science of Discworld III: Darwin s Watch (with Ian Stewart and J ack Cohen) The New Discworld Companion (with Stephen Briggs)
Trends in the State of Computer Science in U.S. K-12 Schools 2016 Table of Contents Executive Summary 3 Introduction 5 Value of Computer Science in Schools 6 Opportunities to Learn Computer Science 9 Perceptions of Computer Science 14 Challenges and Opportunities for Computer Science in K-12
Introduction to Computer Science I Course Overview Computer Science 111 Boston University Welcome to CS 111! Computer science is not so much the science of computers as it is the science of solving pro
Computer Science Teachers Association, Cyber Innovation Center, and National Math and Science Initiative have answered the call by organizing states, districts, and the computer science education community to develop conceptual guidelines for computer science education. The K-12 Computer Science Framework was developed for -12 Computer Science
irm was founded in 1850 by George and Arthur Maw and during the second half of the nineteenth century it grew to become one of the largest tile irms in England. By the beginning of the twentieth cen-tury Maw & Co. was making dust-pressed Art Nouveau tiles, some of which were designed by their in-house artists Charles Henry Temple
ASTM E 989-06 (2012), Classification for Determination of Impact Insulation Class (IIC) ASTM E 2235-04 (2012) Standard Test Method for Determination of Decay Rates for Use in Sound Insulation Test Methods Test Procedure All testing was conducted in the VT test chambers at Intertek-ATI located in York, Pennsylvania. The microphones were calibrated before conducting the tests. The airborne .
