Lucy Book Club
Contents
Agenda
The Lucy Book Club is open to anyone who is interested in search, parsing, compilers, and Lucy in general.
We are currently taking a MOOC, The Hardware/Software Interface, offered by the University of Washington in conjunction with Coursera.
Schedule
We currently meet weekly on Tuesday evenings at 19:00 PDT. The meeting takes place online with Google Plus Hangouts, a video chat service. For more information on how to access the chat room log into irc.freenode.net/#lucy_dev and ask for an invite.
Where To Get Information
irc.freenode.net/#lucy_dev
Upcoming Meetings
Tuesday May 21, 7:00 pm PDT:
Lectures from The Hardware/Software Interface
- Section 5: Procedures and Stacks
- Section 6: Arrays and Structs
Review questions:
- In the Linux process memory layout, the instructions and stack are at different ends of the address space. Which is on the high end, and which is on the low end?
- Under normal circumstances, what portions of memory can contain executable instructions? (stack, heap, static data, instructions)
- What is a return address? How is it stored when a procedure is called, so that the callee can get at it?
In what ways are the call and ret instructions complementary?
- Why might registers be divided between caller-saves and callee-saves, rather than being all one or the other?
- Where is the standard location for returning a value?
- Without a stack, only global variables are available for use by subroutines. What popular language feature would this cripple?
- Does the callee always return before the caller under all possible circumstances? No exceptions?
- What gets stored in a stack frame? How much less gets stored on the stack in x86-64 than in IA32?
Imagine a function which takes 8 arguments of type int named arg1 through arg8. How would they be passed under IA32? Under x86-64? Under IA32, what will you find at 8(%ebp)? How about at 4(%ebp)?
- What's the difference between a multi-dimensional array and a multi-level array? Which one is used by Java?
- When the compiler compiles a loop over a fixed range of elements in an array, it may use pointer math rather than indexing. Why might this be more efficient?
- Are C nested arrays guaranteed to be implemented using "row-major" or "column-major" order?
How can a single leal instruction be used to multiply the value in a register by 5?
- What is the definition of "aligned data"?
- Why is it inefficient (at best) to retrieve unaligned data?
What's the difference between IA32 and 32-bit Windows with regards to alignment of double?
- What are some of the countermeasures which have made stack-smashing attacks more difficult?
Bonus questions not answered by lecture:
- Under x86-64, the frame pointer (%ebp in IA32) is omitted. How will everything be addressed relative to the stack pointer when alloca() is invoked?
In C, array[2] and 2[array] are equivalent. So are array[-3] and -3[array]. Why?
Does sizeof include padding bytes at the end of a struct in its calculation?
- Is a non-executable stack in a JIT environment still helpful?
Community Notes
Below are an excerpt of notes from previous meetings and or anything of interest related to the meetings.
Tuesday May 14, 7:00 pm PDT:
Lectures from The Hardware/Software Interface
- Section 3: Basics of Architecture, Machine Code
- Section 4: x86 Assembly
Review questions:
- What are the four steps of C compilation?
- What's the difference between _instruction set architecture_ and _microarchitecture_? Under whose domain is cache size? Core frequency? Number of registers and their width?
- What processor introduced "flat addressing"?
- What are the four registers in x86 and x86-64 which describe condition codes? What purpose do they serve?
- What are the three basic categories of assembly instructions?
- How typesafe is assembly code?
What will disassembling a function with gdb tell you that disassembling with objdump will not?
- What are the origins of the names of the x86 registers?
- How would you get at a single byte within an x86 register?
What are the four integer op suffixes from AT&T assembler and what do they stand for?
What is the pointer dereferencing operator in AT&T assembler? What character is used as a sigil for constants?
- Describe _displacement_ and _indirect_ addressing modes. Describe the "general form" of the addressing idiom.
- How can the LEA instruction be abused to perform simple arithmetic using the general form of addressing? What checks are omitted by LEA which are performed by standard arithmetic instructions like ADD?
- What allows chips which implement the x86-64 ISA to perform fewer manipulations of the stack than x86 chips?
- What's the difference between the SARL and SHRL instructions?
- What register do the jX "jump" instructions modify?
- What do testX and cmpX do?
What it is the point of testl %eax %eax?
- Which control construct requires more JMP instructions: while or do-while? How many JMP instructions does a for-loop require?
How does the cmovC "conditional move" instruction make it possible to avoid a JMP?
- What advantage does PC-relative addressing offer over absolute addressing?
Under what circumstances can a switch statement be implemented as a "jump table"?
Explain the instruction jmp *.L62(,%edx,4)
Tuesday April 30, 7:00 pm PDT:
Lectures from The Hardware/Software Interface
- Section 0: Introduction
- Section 1: Memory, Data and Addressing
- Section 2: Integer and Floating Point Numbers
Review questions:
- What is hardware? What is software? What is the "hardware/software interface" as defined by the instructors? What do you, personally, hope to gain from studying the "hardware/software interface"?
- What attributes of assembly language make it easier to understand than machine code?
- Why might a computer process/thread be described as an "illusion"?
- What aspect of the low and high voltages representing zeroes and ones limits CPU clock speed?
- In what sense are CPU registers, CPU cache, main memory, persistent storage (e.g. hard disk), and offline storage (e.g. offsite backups) all "memory"? How do they differ?
- What are the advantages of little-endian architecture with respect to casting between integer widths?
- Adding 1 to a pointer adds how much to the address?
- In a C assignment statement, what must the left-hand side evaluate to, and what must the right-hand side evaluate to? What do scalar variable names in C represent?
What determines the value of the expression &array[1] - &array[0] ?
How would you implement a show_bits function to complement the show_bytes function from the lecture on arrays?
What are the practical applications of DeMorgan's Law?
- Why doesn't C provide support for bit arrays, instead only supporting the application of "bitwise" operators to integral data types? There has to be a better way... right?
- In C, how do the logical complement operator and the bitwise complement operator differ?
What set operations do the four bitwise operators & | ^ ! correspond to?
- What is a _one-hot_ encoding? A _two-hot_ encoding?
- What are the drawbacks of _sign-and-magnitude_ representation of negative numbers?
- In a 8-bit _two's-complement_ representation, what is the value of the LSB? Of bits 2-7? And finally, what is the value of the MSB?
- Which representation allows for reuse of the adder used for unsigned integers on the CPU chip: one's complement, or two's complement?
- How can an adder be adapted to perform binary subtraction?
- When casting, what operations does the processor actually perform? In what cases is casting just a matter of reinterpreting a bit pattern which exists in memory, and in what cases does the bit pattern have to be changed?
What is the result of the C expression -1 < 0U ?
- Of the problems you solved in bits.c programming assignment, which was the most satisfying and why?
Tuesday April 23, 7:00 pm PDT (Postponed from April 16th):
Drepper Paper:
2.5 Improving Generated Code
2.6 Increasing Security
2.7 Simple Profiling of Interface Security
3.0 Maintaining APIs and ABIs
3.1 What are APIs and ABIs?
3.2 Defining Stability
3.3 ABI Versioning
3.4 Restricting Exports
3.5 Handling Compatible Changes (GNU)
3.6 Handling Compatible Changes (Solaris)
3.7 Incompatible Changes
3.8 Using Versioned DSOs
3.9 Inter-Object File RelationsReview questions:
1. For IA-32, how can one help reduce access to the GOT address? Why is this a bad idea for IA-64?
2. The -z relro linker option will help fix what security issue with DSOs? How would one turn off lazy relocation?
3. Re-review, what is the PLT stand for again? And how is it different from the GOT?
4. What happens if one is profiling and the PLT is not used? What would the DL_CALL_FCT macro do?
5. What is the ABI?
6. What does LD_BIND_NOW do?
7. What was Sun's solution to versioning and how does it work?
8. Why should symbol maps be used all the time?
9. Take a look at the code sample on page 37, left hand column, what is the .symver doing this instance?
10. What does @@ mean? What does just @ mean?
11. In a mapping file what does local: * mean?
12. What does LD_LIBRARY_PATH do? What are run paths?
13. What is a DST and how are they useful?
Tuesday April 9, 7:00 pm PDT:
Drepper Paper:
2.2.4 Define Visibility for C++ classes
2.2.5 Use Export Maps
2.2.6 Libtool's -export-symbols
2.2.7 Avoid Using Exported Symbols
2.3 Shortening Symbol Names
2.4 Choosing the Right Type
2.4.1 Pointers vs Arrays
2.4.2 Forever Const
2.4.3 Array of Data Pointers
2.4.4 Array of Function Pointers
2.4.5 C++ Virtual Function TablesReview questions:
1. What purpose does -fvisibility-inlines-hiddens serve, especially in regard to C++?
2. Why is the strategy of using the most restrictive visibility possible a good practice when writing C++ to work with Elf?
3 What is a symbol map file for?
4 What is a wrapper function? And what are drawbacks of using wrapper functions?
5. What is an alias?
6. Is using DF_SYMBOLIC a good idea?
7. Why is the length of symbol name important? And why in C++ is this a problem?
8. Why is char str[] = "some string" more optimal than char *str = "some string"?
9 What are some other ways to make string lookup faster?
10. Why is using read only memory when possible more optimal?
11 Why is a switch statement a good way to implement an array of functions like behavior?
12. How do virtual function tables impact startup time?
Tuesday April 2, 7:00 pm PDT:
Drepper Paper:
2.0 Optimizations DSOs
2.1 Data Definitions
2.2 Export Control
2.2.1 Use static
2.2.2 Define Global Visibility
2.2.3 Define Per Symbol VisibilityReview questions:
Questions:
1. When compiling code that is going to be used as a DSO, why is it important to use the -fpic/-fPIC flags?
2. On page 16, right hand column, there are two code samples. What is different about them? And why is the second one significant?
3. What is the easiest way to not export a variable or function?
4. Why did the author add "static" to last and next in the first code sample on page 18, left hand column?
5. Since C doesn't provide a way to define visibility of a function or variable, how does GCC allow the programmer to indicate visibility within the code?
6. What does #pragma GCC visibility push(hidden) and #pragma GCC visibility pop do?
7. If -fvisibility=hidden is used, how would I enable a symbol to have default visibility?
Tuesday March 19, 7:00 pm PDT:
(Rescheduled from March 12.)
15.1.2 The Common Language Infrastructure
15.2 Late Binding of Machine Code
15.2.1 Just-In-Time and Dynamic Compilation
15.2.2 Binary Translation
15.2.3 Binary Rewriting
15.2.4 Mobile Code and Sandboxing
15.3 Inspection/Introspection
15.3.1 Reflection
15.3.2 Symbolic Debugging
15.3.3 Performance Analysis
15.4 Summary and Concluding Remarks
Tuesday March 5, 7:00 pm PDT:
From PLP3:
15.1 Virtual Machines
15.1.1 The Java Virtual MachineReview questions: 1-8 on page 784.
From How To Write Shared Libraries by Ulrich Drepper:
1.5 Startup in the Dynamic Linker
1.5.1 The Relocation Process
1.5.2 Symbol Relocations
1.5.3 The GNU-style Hash Table
1.5.4 Lookup Scope
1.5.5 GOT and PLT
1.5.6 Running the Constructors
1.6 Summary of the Costs of ELF
1.7 Measuring ld.so PerformanceReview questions for the Drepper:
- Why do NUL-terminated strings make horrible hash keys?
- How can _interposition_ be used to override the behavior of a named procedure?
- How can different C++ name mangling schemes have an impact on symbol hash lookup times?
- Compare ELF hash lookup with GNU-style hash lookup.
Consider this source code, which consists of a declaration of a function munge and an int foo which must be defined elsewhere, and a function munge_foo which references both.
int munge(int num); extern int foo; int munge_foo(void) { return munge(foo); }Narrate the following assembly generated for munge_foo when it is compiled as position-independent code.
movl foo@GOT(%ebx), %eax pushl (%eax) call munge@PLT
- Summarize the costs of the GOT (Global Offset Table) and the PLT (Procedure Linkage Table).
Tuesday February 12, 7:00 pm PDT:
From PLP3:
14.4 Address Space Organization
14.5 Assembly
14.5.1 Emitting Instructions
14.5.2 Assigning Addresses to Names
14.6 Linking
14.6.1 Relocation and Name Resolution
14.6.2 Type Checking
14.7 Dynamic Linking*
14.7.1 Position-Independent Code*
14.7.2 Fully Dynamic (Lazy) Linking*
14.8 Summary and Concluding Remarks
* includes auxiliary CD materialAdditionally, we'll cover the first few sections of Ulrich Drepper's paper, How To Write Shared Libraries:
1 Preface
1.1 A Little Bit of History
1.2 The Move To ELF
1.3 How Is ELF Implemented?
1.4 Startup: In The KernelHere are review questions for the Drepper material:
What limitations of the a.out format make it ill-suited for creating shared libraries? If a modern Linux system supplied shared libraries derived from a.out, how would that affect applications which use them?
- What is the main difference between a compiled ELF shared library and a compiled binary executable?
- If you're creating a very large application which takes a long time to link, how can you use shared libraries to minimize the edit-compile-test loop and maximize programmer efficiency? Compare this use of shared libraries to traditional separate compilation.
- When loading the contents of an executable file into memory, why is it desirable to mark as many pages as possible non-writable?
Where must the Elf32_Phdr and Elf64_Phdr program header structs be located in an ELF object file? What is the first member in these program header structs?
Tuesday February 5, 7:00 pm PDT:
14.1 Back-End Compiler Structure
14.1.1 A Plausible Set of Phases
14.1.2 Phases and Passes
14.2 Intermediate forms*
14.2.1 Diana*
14.2.2 The gcc IFs*
14.2.3 Stack-Based Intermediate Forms
14.3 Code Generation
14.3.1 An Attribute Grammar Example
14.3.2 Register Allocation
* includes auxiliary CD material
Tuesday January 29, 7:00 pm PDT:
13.3 Scripting the World Wide Web
13.3.1 CGI Scripts
13.3.2 Embedded Server-Side Scripts
13.3.3 Client-Side Scripts
13.3.4 Java Applets
13.3.5 XSLT
13.4 Innovative Features
13.4.1 Names and Scopes
13.4.2 String and Pattern Manipulation
13.4.3 Data Types
13.4.4 Object Orientation
13.5 Summary and Concluding Remarks
Tuesday January 22, 7:00 pm PDT:
13.1 What Is a Scripting Language?
13.1.1 Common Characteristics
13.2 Problem Domains
13.2.1 Shell (Command) Languages
13.2.2 Text Processing and Report Generation
13.2.3 Mathematics and Statistics
13.2.4 "Glue Languages" and General-Purpose Scripting
13.2.5 Extension Languages
Tuesday January 15, 7:00 pm PDT:
The Lucy Book Club is taking a break from our book-in-progress this week to read a paper on integer compression techniques. One of the algorithms described in the paper is PFOR-DELTA (Patched Frame-Of-Reference with delta encoding), which is particularly suitable for inverted lists.
Super-Scalar RAM-CPU Cache Compression by Marcin Zukowski, Sándor Héman, Niels Nes, Peter Boncz
We'll go over the following questions:
- Why is PFOR-DELTA interesting to Lucy?
What is a segment in PFOR-DELTA?
- What are the 4 major parts of a segment? What is in them?
What are the tradeoffs for choosing different sizes of b (bit width)?
- What type of data structure is used to keep track of exceptions?
What is a compulsory exception? How does it influence your choice of b?
- PFOR-DELTA is a very interesting compression technique, but why is it really faster? What is PFOR-DELTA really optimizing for?
- In their testing, was RAM-RAM or RAM-Cache faster and why?
- Fine-grained access has some extra cost -- what is it?
Tuesday January 8, 7:00 pm PDT:
12.5 Message Passing
12.5.1 Naming Communication Partners
12.5.2 Sending
12.5.3 Receiving
12.5.4 Remote Procedure Call
Thursday January 3, 7:00 pm PDT:
12.4 Language-Level Mechanisms
12.4.1 Monitors
12.4.2 Conditional Critical Regions
12.4.3 Synchronization in Java
12.4.4 Transactional Memory
12.4.5 Implicit Synchronization
12.5 Message Passing
12.6 Summary and Concluding Remarks
Tuesday December 18, 7:00 pm PDT:
12.3 Implementing Synchronization
12.3.1 Busy-Wait Synchronization
12.3.2 Nonblocking Algorithms
12.3.3 Memory Consistency Models
12.3.4 Scheduler Implementations
12.3.5 Semaphores
Tuesday December 11, 7:00 pm PDT:
12.1 Background and Motivation
12.1.1 The Case for Multithreaded Programs
12.1.2 Multiprocessor Architecture
12.2 Concurrent Programming Fundamentals
12.2.1 Communication and Synchronization
12.2.2 Languages and Libraries
12.2.3 Thread Creation Syntax
12.2.4 Implementation of Threads
Tuesday December 4, 7:00 pm PDT:
11 Logic Languages [the entire chapter -- dead-tree material only]
Tuesday November 27, 7:00 pm PDT:
9.5 Multiple Inheritance [including aux material on CD and questions]
10.4 Evaluation Order Revisited
10.4.1 Strictness and Lazy Evaluation
10.4.2 I/O: Streams and Monads
10.5 Higher Order Functions
10.6 Theoretical Foundations [book only]
10.7 Functional Programming in Perspective
10.8 Summary and Concluding Remarks
Tuesday November 13, 7:00 pm PDT:
9.6 Object-Oriented Programming Revisited
9.6.1 The Object Model of Smalltalk [including aux material on CD and questions]
10 Functional Languages
10.1 Historical Origins
10.2 Functional Programming Concepts
10.3 A Review/Overview of Scheme
10.3.1 Bindings
10.3.2 Lists and Numbers
10.3.3 Equality Testing
10.3.4 Control Flow and Assignment
10.3.5 Programs as Lists
10.3.6 Extended Example: DFA Simulation
# Optional:
9.5 Multiple Inheritance [including aux material on CD and questions]
Tuesday November 6, 7:00 pm PDT:
9.4 Dynamic Method Binding
9.4.1 Virtual and Nonvirtual Methods
9.4.2 Abstract Classes
9.4.3 Member Lookup
9.4.4 Polymorphism
9.4.5 Object Closures
9.5 Multiple Inheritance [book only]
9.6 Object-Oriented Programming Revisited
9.6.1 The Object Model of Smalltalk [including aux material on CD and questions]
9.7 Summary and Concluding Remarks
Tuesday October 30, 7:00 pm PDT:
9.2 Encapsulation and Inheritance
9.2.1 Modules
9.2.2 Classes
9.2.3 Nesting (Inner Classes)
9.2.4 Type Extensions
9.2.5 Extending without Inheritance
9.3 Initialization and Finalization
9.3.1 Choosing a Constructor
9.3.2 References and Values
9.3.3 Execution Order
9.3.4 Garbage Collection
Tuesday October 23, 7:00 pm PDT:
9.1 Object-Oriented Programming
Tuesday October 16, 7:00 pm PDT:
8.6 Coroutines
8.6.1 Stack Allocation
8.6.2 Transfer
8.6.3 Implementation of Iterators
8.6.4 Discrete Event Simulation
8.7 Events
8.7.1 Sequential Handlers
8.7.2 Thread-Based Handlers
8.8 Summary and Concluding Remarks
Tuesday October 9, 7:00 pm PDT:
8.4 Generic Subroutines and Modules
8.4.1 Implementation Options
8.4.2 Generic Parameter Constraints
8.4.3 Implicit Instantiation
8.4.4 Generics in C++, Java, and C#
8.5 Exception Handling
8.5.1 Defining Exceptions
8.5.2 Exception Propagation
8.5.3 Implementation of Exceptions
Tuesday October 2, 7:00 pm PDT:
8.1 Review of Stack Layout
8.2 Calling Sequences
8.2.1 Displays
8.2.2 Case Studies: Con on the MIPS; Pascal on the x86
8.2.3 Register Windows
8.2.4 In-Line Expansion
8.3 Parameter Passing
8.3.1 Parameter Modes
8.3.2 Call-by-Name
8.3.3 Special-Purpose Parameters
8.3.4 Function Returns
Tuesday September 25, 7:00 pm PDT:
7.7 Pointers and Recursive Types
7.7.1 Syntax and Operations
7.7.2 Dangling References
7.7.3 Garbage Collection
7.8 Lists
7.9 File and Input/Output
7.10 Equality Testing and Assignment
7.11 Summary and Concluding Remarks
Tuesday September 18, 7:00 pm PDT:
7.3 Records (Structures) and Variants (Unions)
7.3.1 Syntax and Operations
7.3.2 Memory Layout and Its Impact
7.3.3 `With` Statements
7.3.4 Variant Records (Unions)
7.4 Arrays
7.4.1 Syntax and Operations
7.4.2 Dimensions, Bounds and Allocation
7.4.3 Memory Layout
7.5 Strings
7.6 Sets
Tuesday September 11, 7:00 pm PDT:
7.1 Type Systems
7.1.1 Type Checking
7.1.2 Polymorphism
7.1.3 The Meaning of "Type"
7.1.4 Classifications of Types
7.1.5 Orthogonality
7.2 Type Checking
7.2.1 Type Equivalence
7.2.2 Type Compatibility
7.2.3 Type Inference
7.2.4 The ML Type System
Tuesday September 04, 7:00 pm PDT:
6.5 Iteration
6.5.1 Enumeration-Controlled Loops
6.5.2 Combination Loops
6.5.3 Iterators
6.5.4 Ordering within Expressions
6.5.5 Generators in Icon
6.5.6 Logically Controlled Loops
6.6 Recursion
6.6.1 Iteration and Recursion
6.6.2 Applicative-and Normal-Order Evaluation
6.7 Nondeterminancy
6.8 Summary and Concluding Remarks
Tuesday August 28, 7:00 pm PDT:
6.1 Expression Evaluation
6.1.1 Precedence and Associativity
6.1.2 Assignments
6.1.3 Ordering within Expressions
6.1.4 Short-Circuit Evaluation
6.2 Structured and Unstructured Flow
6.2.1 Structured Alternatives to goto
6.2.2 Continuations
6.3 Sequencing
6.4 Selection
6.4.1 Short-Circuited Conditions
6.4.2 Case/Switch Statements
Tuesday August 21, 7:00 pm PDT:
4.1 The Role of the Semantic Analyzer
4.2 Attribute Grammars
4.3 Evaluating Attributes
4.4 Action Routines
4.5 Space Management for Attributes
4.6 Decorating a Syntax Tree
4.7 Summary and Concluding Remarks
Tuesday August 14, 7:00 pm PDT:
3.5 The Meaning of Names within a Scope
3.5.1 Aliases
3.5.2 Overloading
3.5.3 Polymorphism and Related Concepts
3.6 The Binding of Referencing Environments
3.6.1 Subroutine Closures
3.6.2 First-Class Values and Unlimited Extent
3.6.3 Object Closures
3.7 Macro Expansion
3.8 Separate Compilation
3.9 Summary and Concluding Remarks
Tuesday August 7, 7:00 pm PDT:
3.1 The Notion of Binding Time
3.2 Object Lifetime and Storage Management
3.2.1 Static Allocation
3.2.2 Stack-Based Allocation
3.2.3 Heap-Based Allocation
3.2.4 Garbage Collection
3.3 Scope Rules
3.3.1 Static Scoping
3.3.2 Nested Subroutines
3.3.3 Declaration Order
3.3.4 Modules
3.3.5 Module Types and Classes
3.3.6 Dynamic Scoping
3.4 Implementing Scope
Tuesday July 31, 7:00 pm PDT:
2.3 Parsing
2.3.1 Recursive Descent
2.3.2 Table-Driven Top-Down Parsing
2.3.3 Bottom-Up Parsing
2.3.4 Syntax Errors
Tuesday July 17 Meeting
2.1 Specifying Syntax: Regular Expressions and Context-Free Grammars
2.1.1 Tokens and Regular Expressions
2.1.2 Context-Free Grammars
2.1.3 Derivations and Parse Trees
2.2 Scanning
2.2.1 Generating a Finite Automaton
2.2.2 Scanner Code
2.2.3 Table-Driven Scanning
2.2.4 Lexical Errors
2.2.5 Pragmas
Thursday July 12 Meeting
Had discussions surrounding the Check your understanding sections on pages 16, 25, and 35.
Possible Future Books
Managing Gigabytes, by Ian H Witten.
Object-Oriented Programming: An Evolutionary Approach, by Brad J Cox. The Art of Unix Programming, by Eric Steven Raymond.
Information Retrieval: Implementing and Evaluating Search Engines, by Some people. Communicating Sequential Processes, by C. A. R. Hoare
Object-Oriented Programming With ANSI-C, Axel Schreiner
Past Books
Programming Languages Pragmatics, by Michael L Scott