Weekly Readings

To comply with the College's 4th credit hour policy.

Weeks #13 and #14

The readings for this week and the next are the articles referenced in A5.

Week #12

Read the LWN article by David Drysdale on Anatomy of a system call, part I, that describes how Linux uses the SYSCALL and SYSRET instructions.

Optional, read part 2 in the series, which describes how Linux handles all the various ways in which system calls can be invoked in 32-bit x86.

Week #11

The Linux kernel is an OS kernel that runs on a wide variety of processors. Its documentation contains details on how it implements virtual memory. For this week, read the Concepts Overview in the Linux Memory Manager.

Then, read the documentation on examining process page tables. Note the path /proc/pid/ means replace /pid/ with the process identifier.

Week #10

The Intel 64 and IA-32 Architectures Optimization Reference Manual is the reference to use when optimizing code at the low level. It contains nearly all the information you need to write fast code.

For this week, you will read parts of Chapter 3, General Optimization Guidelines. In processors, the part of the pipeline that fetches and decodes instructions is called the front-end. Specifically, you will read Section 3.3 that serves as a (short) introduction, and then Section 3.4, Optimizing the Front End, which talks about how branches affect performance. You are only required to read Sections 3.4.1 Branch Prediction Optimization, Section 3.4.1.1 Eliminating Branches, and Section 3.4.1.2 Static Prediction.

(Optional reading) Read Section 2.5, Skylake Client Microarchitecture, to get a feel of how processor manufacturers describe the pipeline and other components inside a processor (referred to as microarchitecture). Note, to fully understand the components of an out-of-order pipeline, you need to take Computer architecture course (CSC 404). I selected the Skylake because it is old and reasonably accessible. The cycle1.csug machine uses the Cascade Lake microarchitecture. On Linux, you can do cat /proc/cpuinfo to get information about the processor on a machine, which you can then look up online.

Week #9

No reading assigned.

Week #8

Memory allocators implement the functions malloc and friends and are very important in programs that make heavy use of dynamically allocated structures (which is most non-trivial programs). This week's reading describes the internal design of dlmalloc, a memory allocator that was pretty common on most systems and used by most programs since it was part of the C standard library implementation (i.e. libc).

We have not covered many topics mentioned in the goals of dlmalloc, but reading this should give you a good grasp of your ability (or inability) to follow documents like this. Your goal is to be able to read and understand documents like this by the end of this course.

Optional reading: Memory allocators are so important to performance that nearly everybody has their own allocator. Two notable ones are Google's tcmalloc (this bizarrely replaces their old allocator, also called tcmalloc) and jemalloc which finds its use inside the erstwhile Facebook.

Week #7

I have written a short guide to using Address Sanitizer. The goal of this is to familiarize you with a tool that has the ability to save you lots of frustration debugging later assignments in this course (and in other courses). Another goal is to get you to read the official documentation for this tool.

Week #6

No readings in midterm week.

Week #5

What is the convention for passing parameters in registers on x86-64? The System V Application Binary Interface (ABI) for x86-64 is the reference document to answer this question. (Intel provides a supplement which I linked to in the lectures.)

You must read the whole of Section 3.2, "The Function Calling Sequence", pages 14--23. Other than the discussion on x87/MMX/AVX registers, everything you have studied in class should allow you to read and understand this section. Pay particular attention to Section 3.2.3 "Parameter Passing", which tells you how to classify arguments, how to pass arguments of different classes, and how to return values.

Post any questions you have on Blackboard.

Week #4

Who decides what sizes the C types char, int, long, long long are? Since software on a system must interact with other, they must all agree on these types. Therefore, the operating system usually sets the standard.

Unix (and Linux) follow the LP64 model which means that char is 8 bits, int is 32 bits, but all other types long, long long, and the size of an address are 64 bits (the P stands for pointer, which is the C equivalent of assembly's address).

You can read the rationale behind the LP64 model at the Opengroup's Unix website. Note: this document is dated -- going all the way back to 1998, before the C standard was updated in 1999 with new standard fixed-size integer types (which is why we don't talk about __int32, __int64, etc.).

Windows chose the LLP64 model instead, but also for good reasons (note that the word parity used in that article is used in its English sense). Raymond Chen elaborates on his The Old New Thing blog, which often contains fascinating insights into the history of Windows OS design.

Week #3

Read Prof. John Regehr's blog posts on undefined behaviour in C and C++, Part 2, and Part 3.

I encourage you to ask lots of questions about these blog posts using Blackboard Discussions.

Prof. Regehr recommends using good tools to catch these errors, see as example, LLVM's Undefined Behaviour Sanitizer (UBSan).

Week #2

Read Ken Shirriff's blog post on using die photographs to reverse engineer the circuitry in Intel's 8086 ALU that perform arithmetic and logical operations.

Because this blog post spans subjects from VLSI to logic design, no content from Week #2 will be evaluated in exams or assignments. Only Homework #2 will have a short question asking for a summary.

On an aside, Ken's blog covers many interesting reverse engineering projects, including computers from the Apollo 11 projects.

Week #1

Read the Wikipedia article on the Octal Number System.

Read the GNU C Reference Manual section on Integer Constants.

What is the numeric value stored in the variable x below, assuming C code?

int x = 010;

(Optional) Marianne Bellotti has a nice article on The Land Before Binary, a writeup of non-binary systems for representing numbers.