To understand what the result will be from a series of HW ISA instructions, you need to mentally (or on paper) keep track of: What is the current program counter and what will it be for the next instruction, what is the content of each of the 16 registers, and what is the content of all 256 memory slots. Of course, you really only need to keep track of those registers and memory slots that the code actually reads from or writes to. Importantly, you really only have 14 registers to track, since R0 is always 0 and R1 is always 1. You can think of each instruction at two different levels of abstraction: as control signals from the control unit (which you should understand the truth table for if you want to deal with stuff at this level) OR as abstract logical/arithmetic operations, listed in the “meaning” column of the main HW ISA slide.

If you want to think about it at the bits/circuit level, trace through the full CPU architecture diagram for each instruction: from the opcode part, figure out the outputs that the control unit will send. From the Rs/Rt/Rd parts, figure out what inputs the register file, ALU, and/or BEQ mechanism will receive. From the control unit outputs, figure out which signals get dropped or forwarded by the multiplexers, which influences these inputs. Then, figure out what the ALU output is, and possibly, what address input the data memory will receive and what its output will be. Finally, figure out what value will be sent back to the register file (or written into the data memory, at what address, or what the BEQ/JMP address result will be). I think that this process is worth doing a few times so you really understand how the circuitry is connected and operating together. However, it’s a slow process. If we think more abstractly, we can reason through assembly code much faster…

To come up with the Boolean algebra expressions for the control unit, it’s easiest to start from a truth table: you already know how to use sum-of-products and/or simplification to get form there to an expression. To derive the truth table for the control unit, you need to understand what the other parts of the CPU circuit are doing, and then be able to deduce what the individual control wires need to be set to to make that happen. All of that is in terms of the “meaning” column of the ISA slide. So for example, if the “meaning” for a particular opcode says “R[d] <- R[s] + R[t]” you know that the steps for making that happen are: 1. read data from R[s], 2. read data from R[t], 3. Add those two numbers together, and 3. Store the result in R[d]. If that’s the work the circuit needs to do, then you know that the address inputs to the register file must be s and t, and the read data outputs from the register file must make it into the ALU. That implies that the “Mem” control line will be off for this operation, since otherwise, read data 2 is based on d, not t, and the t data as an offset would get put into the ALU instead of the read data 2 output from the register file. Additionally, it means that the ALU opcode must be the opcode for addition. Further, you can also deduce that Mem must be 0 because the ALU result needs to make it back to the register file data input, and Mem also controls the multiplexer that can swap that for a data memory result. Then you can deduce that the “write enable” bit for the register file should be on, since the result needs to be written into a register. Similarly, the result from the ALU and data value passed to the data memory won’t be sensible, so we need to make sure to set the “mem write” line to 0. Also, we are NOT doing any kind of jump or branch with this meaning, so the relevant control lines for those things should be off. That’s just a simple example, but the process is the same for the other opcodes.

(Note: lab 4 has an example RAM circuit where you can see these details.)

(Note: lab 4 has an example RAM circuit where you can see these details.)

RAM is general-purpose memory, there’s a lot of it, and it’s much faster to access than the hard drive, so it’s used for all of the data that programs and your operating system are actively using at any given moment. Unlike data stored on the hard drive, data stored in RAM will vanish if you turn off the computer though. So when you save something in a file, that gets written to the hard drive.

The BEQ instruction stands for “branch if equal.” It’s a very important instruction because without it, there’s no way for the computer to change its behavior based on the data it is processing. You can create quite complex programs with just JMP, but you can’t achieve anything nearly as rich as you can with BEQ available as well. BEQ will serve as our “if” statement, as well as “for” and “while” loops when combined with JMP. How does it work? First, “branch” in this case means “go somewhere else in the code, instead of continuing down as normal with PC <- PC + 2.” It could also have been called “JEQ” for “Jump if equal” because it is a kind of jump, but the word “branch” implies a splitting-off which is relevant to BEQ because there are two possible destinations: BEQ examines two registers (or possibly the same register twice) and if they’re equal, it performs the jump indicated by the offset, relative to where the PC would have ended up normally. On the other hand, if the two registers’ values are not equal, it skips the jump and just does PC <- PC + 2 as usual, continuing to the next instruction after it.

As an example of how it is used, consider a while loop: we want to “continue the loop if the continuation condition is true.” If we assume true = 1 and false = 0, you could use the following assembly code at the bottom of your loop:

BEQ Rn, R0, 1
JMP <top of loop>

Most likely, you’d see a garbled mess of random characters, possibly with some runs of similar characters where similar instructions happen in a row, and very likely with many unprintable characters where the necessary opcodes or register specifications of machine code, when translated through a symbol table, map to symbols that aren’t normally used. You can try this yourself: right-click on an executable file and choose “open with” and then select a text editor, like Notepad on Windows or TextEdit on a Mac. Alternatively, in the command line if you have a compiled program (like the program you wrote for the bits assignment) type “cat” and then the filename. Note that on the command line this may cause issues with the terminal if it happens to end up printing special output control characters; in that case using the terminal “reset” command (or just opening a new terminal) might be helpful.

The question in the lab was mostly to provoke you to think a bit more about what kinds of connections could be made and how pieces of a CPU might fit together, in preface to you actually looking at the (mostly) full CPU circuit diagram later in the lab. In that diagram, the ALU takes inputs from the register file (or possibly Instruction Memory directly for the offset part of a memory address) and sends output both to a register file and to the address input of Data Memory (another RAM). However, note that the data memory output goes into the register file, and the data memory input comes from a register file, Since the ALU can take input from register files and write output to them, it’s indirectly hooked up to the data input and output of the data memory, since values can go into a register for a cycle and in the next cycle go in to the ALU, or vice versa.

When translating a schematic diagram (like the CPU diagrams we show in various places) into LogicWorks or the Falstad Simulator, you need to first identify which component in the simulator corresponds to which part of the diagram (or what to search for and add to your diagram to get the right component). This is complicated by the fact that some components in the schematic diagram, like a sign extend or a shift, are created just using alternate wiring connections without there being an actual component.

The HW ISA is intentionally kept very simple, so that we can teach it to you in 5 weeks and you can understand how the hardware side of things implements the software specification. In the next part of the course, we’ll be reading and writing programs in Intel x86 assembly; other “popular” (at least, among hardware hacking people I follow on social media) assembly languages include ARM (a much simpler assembly language with a different design philosophy, found in some Macs and many embedded devices like TVs) and 6502 (an older CPU popular among retro tech enthusiasts and used in systems like the Super Nintendo). Each will implement a lot of the same basic instructions as the HW ISA, just with more different flavors. They might also use more than 16 bits, and some have instructions that are different sizes.

The basic operations of the HW ISA are the same operations we’ll use for about 70-80% of our assembly programming, just with slightly different syntax. The most common other instructions we’ll use will be specialized jump instructions for function calls and returns, and some specialized memory access instructions for dealing with the stack (which we’ll be learning about soon).

The choice of 16 bits as the word size in RAM is based on the fact that the HW ISA specifies a 16-bit word size for each instruction. If RAM used a different number of bits per word, you’d have to load either multiple words per instruction or only part of a word per instruction, vastly complicating the design either way. But you can easily build RAMs with any word size you want: you just need that many data input and output wires, and then you need to group the internal D flip-flops together in groups of that size.

The number of address bits for a RAM chip places an absolute limit on the number of data items it can contain, since with N bits, there are $$2^N$$ different possible bit patterns, so you can’t distinguish any more than that number of data items. This is also the formula for deducing either the number of address bits from the RAM size, or the RAM size from the number of address bits. Almost without exception, a RAM will always choose to have exactly that many data items, although in principle it could have fewer. In the simplest setup, each “data item” is a “word,” (16 bits for the HW ISA) and so the total size of the RAM is the word size times the number of distinct addresses.

There are multiple things you might be asked to draw a diagram of: you might be asked to draw a diagram based on a truth table, a boolean algebra expression, and/or an English description of how some components fit together. For the first two, you can convert between truth tables and boolean algebra expressions. I think if you’re given a truth table, converting to an expression is best because the expression can be directly translated into AND, OR, and NOT gates: Just use order-of-operations to figure out which operations happen in what order, and draw a gate for each one.

For an English description, just try to follow the description as best you can.

To practice drawing from a description, you can go to any of the diagrams in the lab pages and right-click to access the alt text (your browser should have some means of doing this). The alt text will be a description of how that circuit is connected, so you can try drawing from that description without looking at the image, and then compare your result with the image when you’re done (do let me know if you find an inconsistency!).

The JMP instruction lets us move from one part of the code to another. The BEQ instruction can also do this, but the BEQ instruction has a limited range, because the offset is a 4-bit signed value, so it can jump at most 8 instructions backwards (or 6, if you don’t count BEQ and the instruction after it) or 7 instructions forwards (8 if you count the instruction after BEQ). So JMP allows us to jump to a very different part of the code, since it can accept a 12-bit offset, and that offset is absolute, rather than relative. Remember that we always multiply the offset by 2, to ensure that the resulting PC address is even, because each instruction word (16 bits) takes up two address slots (8 bits each), so the address of the start of each instruction is a multiple of 2.

With BEQ and JMP instructions, it’s possible to create infinite loops. Of course, sometimes that’s what you want, like a program that’s always waiting to respond to input and only stops when you shut off the computer.

But to ensure that it does halt, you need to ensure that the sequence of BEQ and JMP instructions will always eventually lead to a HALT instruction. As it turns out, in the abstract this is a tricky theoretical problem, and if you are given a program supplied by an untrusted source, it can be prohibitively resource-intensive to prove whether or not it will eventually halt.

I don’t know all the specifics of the answer to this question, but some reasons include:

1. We ignore this detail in our circuits in this class, but a 1 or 0 indicated on a single wire may be insufficient to actually trigger all of the places that wire connects to if the wire connects to many different places. If you think of each output end of a wire as needing to “do some work” to assert either a 0 or a 1, and the input end as “doing some work” to assert 0 or 1, if there’s one input and thousands of outputs, the work of the input might not be sufficient to trigger each output as it is supposed to. This can be fixed with extra repeater gates, but…

2. We mostly ignore this detail in this class, but each gate in a circuit (really, each transistor) takes some time to operate. And the next gate in the circuit won’t be receiving valid inputs until the previous gate settles, so in a circuit with hundreds or thousands of gates, this propagation delay makes the whole circuit take more time to reach a valid state. This is called “gate delay.” A register file is small, and thus has a limited gate delay cost. A much larger RAM doesn’t necessarily seem to have a longer longest-single-path (which is what matters for gate delay) but in practice because of the repeaters from point 1, it may have a much higher delay.

3. A third consideration (which again we’ll ignore in this class) is that while the register file is built directly into the CPU, the RAM chip is actually a separate circuit on another board (this is why you can add more RAM to your computer by plugging in a new chip). There is some delay related to the communication between the two chips, which happens over a PCI bus that also has other things using it.

There are more issues, like the difference between SRAM and cheaper-but-slower DRAM, which I don’t fully know the details of. You should now be equipped to understand a lot of them though if you want to dig deeper on Wikipedia and/or in our textbooks.

In code, we are comparing situations like this:

int x = 0;
x += 1;

vs. modifying by dereferencing a pointer, like:

int x = 0;
int *xAddr = &x;
*xAddr += 1;

As far as I know, there are no differences whatsoever between these two cases. The compiler should produce almost identical assembly code for each. One caveat is that the second code may end up forcing x to be stored on the stack, since we need its address. But that shouldn’t change the effects of the code at the C level.

Note that if the pointer type of the pointer doesn’t match the type of the variable, there may be differences. The following code uses a char* and so when we modify the dereferenced value, we modify only 1 byte (notice that a cast is necessary to create the differently-typed pointer):

int x = 0xffff;
char *xAddr = (char*) &x;
*xAddr = 0;

malloc is short for “memory allocate” and it does just that: allocates (reserves for our use) some memory. To build a metaphor here, imagine you’re in a review session with a bunch of other students, and you each have a different problem to solve. You could just solve it in your head, but there are whiteboards in the room, and if solving it in your head means using registers only, there are times when there’s too much information and you need to write stuff down (i.e., use memory instead of a register). But with so many students (functions) in the same room, you need a way to share the whiteboard. While malloc uses the “heap”, it’s worth considering for a moment the other memory pool: the stack. Each function gets its own stack frame, so in our metaphor each student gets some reserved whiteboard space. However, after a student is done solving their problem, we erase that space so that other students can use it. Anything stored on the stack is theoretically invalid after the function returns. That’s where the heap comes in: In our metaphor, it’s an extra part of the board where students can write info from their solution that’s useful for other students. If you’re all solving related problems, sometimes part of the solution to one problem is useful in solving another. For this part of the board, not every student needs to use it, so we don’t allocate space for each student. Instead, when a student needs to use it, they can just walk up and draw a box to reserve some space, then put the information they want to share in that box. Later, if someone who needed that information decides it’s no longer necessary, they can erase the box, so that others can use that space. So this extra whiteboard space that anyone can use is called the heap, and it’s where we store values that need to be shared between functions.

malloc in our metaphor is walking up to the whiteboard and drawing a box. When we do it, we need to determine the amount of space we need, which is why we need to specify that when we call malloc. malloc returns a pointer to the allocated space; we usually want to cast that pointer to a specific type, based on what we plan to put in that space.

free in our metaphor is erasing the box so others can use it. If we forget to call free, the heap will fill up with junk values, and someone who needs to use space will end up unable to run because there’s no space left. This is called a “memory leak,” and valgrind is the tool that helps us detect memory leaks. The complicating factor is that since we use the heap to share information between functions, the function that calls free is often a different function than the one that calls malloc. This makes it extra easy to forget to call free when necessary, or to do something like accidentally calling free too early, before someone else comes along and tries to read the value we just erased. While in the whiteboard metaphor freeing actually erases the data, in the computer, freeing just marks the memory as fair game for re-use, and it may or may not be erased.

In general, since using malloc is complicated, if you can avoid it you should. But any time you need a value that’s bigger than a single return can carry to pass from one function to another, you’ll need to use it, or use other techniques that are almost as complex (like passing a pointer into the second function which it uses to write its answer into pre-allocated memory).

The specifics usage of malloc is that you give it a number of bytes, and it returns a pointer to allocated space where that many bytes are reserved. Because it doesn’t know what you wanted the bytes for, it always returns a void* generic pointer. This is why you almost always cast the result to indicate what type it is, and use sizeof in the argument to compute the correct number of bytes for a certain number of values, like:

int *data = (int*) malloc(sizeof(int)*10);

For free, you just give it the pointer that malloc returned and it marks that memory as no-longer-in-use. In this example you’d do:

free(data);

The compiler keeps tables that it fills in as it reads your code with the memory address (or register used) for each variable, as well as the types that they have. When producing assembly code, it uses these tables to pick which registers/addresses to use. It also uses the type information to pick which variants of assembly instructions to use, and whether to use full-size or part-size registers (e.g., using %eax for an int but %rax for a pointer). We won’t dig into that process in this class, but a compilers class would.

When computing the result of subtracting two pointers, we get a value of type ptrdiff_t rather than the same type as the pointers. Why not just have char* - char* → char*?

One reason is that pointers are unsigned, since there’s no such thing as negative addresses. But when we subtract, we care about direction, not just difference, so the value is signed.

The short answer is: “we can’t.” Each address specifies a particular byte in memory. For anything bigger than a byte, we can’t really “point to” the whole thing, without using two numbers: one for the start, and another for the length (or one for the start, and another for the end). In practice, pointers themselves always point to the starting byte of whatever they’re trying to indicate. Then the compiler keeps meta-information about the size of that value, so that it knows how many bytes to access at once (e.g., 4 bytes together for an int).

Segmentation faults can happen for several different reasons:

1. Code tries to write data to a memory address that’s read-only.
2. Code tries to read data from an unreadable address (like NULL).
3. Code tries to execute instructions from an address that’s not marked as executable (e.g., trying to jump to a location that’s not part of the program’s code).

The best way to think about this in my opinion is to consider all addition and subtraction operations with a pointer value to take place in units of “slots,” and then based on the size of the thing pointed to, that determines the size of a slot. So if we have:

int *array = {10, 11, 12, 13, 14};
int *ptr = array + 2;

In this case, the pointer will point to the third slot in the array, or to the number 12. In raw address terms, that’s 8 bytes beyond the address of the base array, and that’s where pointer scaling comes in: the actual value of 2 was multiplied by the stride of 4 to get +8 for the raw byte address. However, when doing subtraction, we effectively apply scaling in reverse. If we look at numerical values, ptr is 8 more than array. But if we ask C to print out ptr - array the subtraction happens in terms of “array slots” and the result will be 2, not 8. The reason for this is that we’d like the following equation to be true: array + (ptr - array) == ptr). In C, that expression does the (ptr - array) calculation in terms of “int-sized slots” to get 2 as the value, so that when it adds 2 to array which it also does in terms of “int-sized slots” it gets the correct value for ptr.

When a function returns, we move the stack pointer back up above its stack frame, but as soon as another function gets called, the stack pointer moves back down, across the same memory region. The new function then will write its own data into that region, erasing the data written by the old function. At that point, anyone who uses a pointer to the old data will see the new data instead. For example:

int* readThree() {
    int results[3] = {0, 0, 0}; // needs 
    scanf("%d %d %d", &result[0], &result[1], &result[2]);
    int *r = results; // otherwise the compiler substitues NULL for return
    return r;
}

int main(int argc, char** argv) {
    int* first3 = readThree(); // creates frame; then returns
    // first3 is technically invalid here, but the data is still there
    // ...until another function is called
    int* next3 = readThree(); // same frame position as first call
    // (printf itself doesn't use enough of the stack to pose a problem)
    printf("First 3 address: %p\n", first3);
    printf("Next 3 address: %p\n", next3);  // prints same address
    printf("First 3: %d, %d, %d\n", first3[0], first3[1], first3[2]);
    printf("Next 3: %d, %d, %d\n", next3[0], next3[1], next3[2]);
    // same numbers from second call are printed twice
    return 0;
}

If we were to run this and enter "1 2 3" the first time and "4 5 6" the
second time, the prints would print out "4 5 6" twice, and it would show
the same address for the two return values. Without the extra pointer
variable, compiling it will also produce a complier warning about
returning a pointer to stuff allocated on the stack. When it prints that
warning, our currrent compiler also sets the return value to NULL,
becuase since returning a pointer to a stack variable is "undefined
behavior" the compiler can do whatever it wants in that case. So if we
run this program without the `r` variable, we'll just get a segmentation
fault.

The stack usually has a fixed maximum size in the megabytes range. Given that most function call frames take a few dozen bytes, this is usually sufficient for thousands to hundreds of thousands of layered function calls, and since each function gives back space when it returns, the only case where you might be worried about the stack size limit is when using recursion and layering lots of stack frames. The heap on the other hand is usually only limited by the physical memory (and on 32-bit systems by the address space size). A 32-bit system is usually limited to ~3GB of heap, while a 64-bit system can use up to all of the physical RAM available (until we develop systems with exabytes of RAM…).

There’s actually a virtualization layer that allocates real physical memory between different programs on your computer. So if you have 8GB of RAM and Firefox is using 4GB, another program you run may encounter an out-of-memory error if it tries to allocated 6GB.

At a most basic level, if we want to use memory to store things, we need to allocate it, so that two different functions or programs don’t try to use the same memory for different purposes. The stack conventions provide an easy way to allocate memory for a particular function call: Just declare a local variable. However, that’s not good enough if we need to create values that will survive beyond the return from a function, like strings, arrays, or other objects that need to be passed around between functions. In those cases, we use malloc to ask for a permanent allocation, and then when we’re done with that memory, we use free to release it so that someone else could use that memory later.

In languages like Python, Java, or Javascript, we have a garbage collector and an automatic memory allocation system. Allocation is handled for us automatically, but to free it, we need to spend some time on “garbage collection” now and then. Those languages are in many cases 2-100 times slower than equivalent C code (with garbage collection being one part of that). Now, most of the time, we simply don’t care, and it’s better to use the garbage-collected language, because there are all sorts of errors that we can make when allocating memory, and for many programs, they spend most of their time waiting for user input or network data, not running their own code (so speedup doesn’t matter).

For some real-time applications, like videogames, performance actually does matter, and these are more typically written in C++ or another low-level language. Always try to judge whether a performance improvement actually impacts the user experience before reaching for the “fastest” language.

That said, understanding how memory is allocated by having to do it manually is super useful in understanding various things about the performance of automatic allocation systems. For example, knowing how strings are allocated can help you understand why certain Python programs would be faster than others. For example, these two functions:

def f(n):
    return 'a'*n  # string multiply can allocate once

def g(n):
    result = ''
    for i in range(n):
        result += 'a'  # needs to copy + reallocate each time
    return result

No. They will become exactly the same assembly code when compiled, so there’s absolutely no difference in terms of what the CPU will do.

Yes. No matter what language you’re working with, ultimately memory is used to hold data, and any pattern of memory access can be written up using pointers.

The computer’s memory is divided up into different “segments.” One of these holds the actual machine instructions to be executed, another holds the heap, another holds the stack, and other segments provide space for things like system calls. Each segment has certain permissions: can we read from it, can we write to it, can we execute code from it? A segmentation fault happens when we attempt to do something that’s forbidden, like write to a read-only segment. Most often, we will see:

1. Attempts to read from or write to the base segment, which is a small area of memory at the very low end of the address space that’s neither readable nor writeable. This segment exists to protect us from accidentally using a number value as if it were a pointer. If we say something like:

   int x = 3;
   int y = *x;

   This would attempt to read memory at address 3. You’ll get a segmentation fault becuase of that protected base segment. Most commonly, this will actually happen because you are using NULL as a default value for a pointer and accidentally tried to use the pointer before it received its correct value.

2. Attempts to execute code from the stack or heap. The stack is marked as non-executable, so trying to interpret data stored there as machine instructions will be a segfault. This usually happens when return addresses stored on the stack get corrupted, which shouldn’t happen much in practice, but which will happen in this class because we’ll be teaching you about how to corrupt the stack.

When storing an integer, which is 4 bytes, we have to decide how to store those bytes in memory. Let’s say we want to store the value 0x12ab34cd at address 0x40000. Do we store 0x12 at address 0x40000, 0xab at address 0x40001, 0x34 at address 0x40002, and 0xcd at address 0x40003? Or do we do the opposite, and store 0x12 at address 0x40003, 0xab at 0x40002, 0x34 at 0x40001, and 0xcd at 0x40000? This decision doesn’t really make much difference in terms of performance: either way we’ll load all 4 bytes at once; either way we’ll do things like carry between them in an adder, just in a different order. However, if two different systems make different choices, they won’t be able to directly transfer data to each other in binary: They’ll have to convert that data to swap around the bytes first. So even though within a particular design it doesn’t have big performance implications, differences between designs do.

The word “endian” comes from Gulliver’s Travels, in which there is a society deeply divided about whether eggs should be cracked from the little end or the big end. In other words: it’s a reference to making a big deal out of an ultimately unimportant distinction. There aren’t really good arguments for why one way is “better” than another, but people are still sharply divided into two camps about it.

Remembering which one is which is hard, but a mnemonic that you can try is that “little endian” means that the “little” part (i.e., the least significant byte, which is 0xcd in our example above) is stored at the “end” (i.e., the lowest address). Equivalently, you can remember that the end of the number (still 0xcd is stored at the little address. Big endian is the opposite: the end of the number 0xcd is stored in the byte with the biggest address, or equivalently, the biggest (most significant) part of the number (0x12 in our example) is stored at the end (at the smallest address).

I don’t actually know the history behind why different choices were made in these cases, but there are certainly tradeoffs between them. Note that if you want, you can create a character array that isn’t NUL-terminated, and store its length separately, although this may cause headaches if other don’t realize what’s going on.

For sentinel values, not having a separate length variable simplifies the code that deals with them. However, you pay a cost: you need to allocate one extra byte per string, and strings are no longer allowed to contain an all-0 byte as part of their data. That second cost is not really acceptable for arbitrary arrays, since not being able to store the number 0 in an integer array would be pretty silly. Of course, you could pick another data value as the sentinel, but things get complicated if each different kind of array needed to use a different kind of sentinel value. Also, because we often do arithmetic on numbers (but rarely on characters) the chance of accidentally producing the sentinel value would be greater for arrays of integers.

gdb is a debugger, so it lets us set breakpoints and get lots of information about what’s going on. If your program crashes, running it with gdb can let you figure out exactly what was going on when it crashed, and also inspect the variable values at that moment that might have led to the crash.

Lab 9 has several examples of this, but the basic idea is: the stack is in memory, so we can use examine (or just x) to view that memory. Of course, we have to know where in memory we want to look, but since %rsp stores the stack pointer, we can use $rsp as our target address to see values starting from the bottom of the stack.

There are two main avenues of approach here (although a computer security class can go into a lot more detail). The first one is instead of giving people code, run the code on your own computer and sell access to a web interface where they can send messages to the code and get messages back. Most modern apps are trending this way, and almost anything with a login these days involves at least one server besides the computer or phone actually using the app. This is complicated, but you get a lot more control over things. Sadly, this includes the ability to do a lot of nefarious stuff, like sell off the user’s data to make some extra profit, or force them to enable extra “features” they weren’t expecting and didn’t want.

The second approach is to use encryption to protect key information, even though you’re giving out a program people can download. For something like a password, there are encryption routines that can compute a value called a “hash” that’s based on the password, using a function that takes only a few seconds to run, but where running the reverse function to compute the password based on the hash would take millions of years. The math behind this is pretty cool (and out-of-scope for this class) but as one example, consider factoring a 100-digit number that was created by multiplying together 3 prime numbers, one of which was 50 digits long. If I tell you what the numbers are, it’s easy to multiply them and verify that they do indeed multiply to the correct value. But if you use a disassembler to look at the code and see that the correct password involves entering three numbers that are each prime and which multiply together to create the stored target value, you’re out of luck: actually finding what those numbers are requires searching through so many different possibilities it will take effectively forever to do it.

One of the first things to do when looking at a function in assembly code is to map out the jumps by identifying which ones go where, especially those that are internal to the function rather than jumps to call other code (although those are important too). From that, you’ll be able to identify loops because they involve one or more jump instructions where given the right condition results, we can jump in a loop from one instruction back up and eventually down again to the same instruction. In the simplest case, there’s just one conditional jump that goes upwards in the code, and the code will then flow back down to that jump until eventually its condition becomes false.

Typically, looking at the source code is much better in this case, and I wouldn’t recommend looking at the assembly unless it’s absolutely necessary. If there’s a bug in your compiler, it may be necessary since the assembly might not faithfully implement the source code in that case. Hope that you never run into such a bug: they’re very nasty since you typically try to rule out every possibility involving errors in your own code first, which is exhausting. Also, unless you’re very unlucky, the compiler bug will end up being fixed in a newer version of the compiler that’s already available, so simply upgrading your version will solve things. Discovering a new compiler bug is even more fun :)

Besides situations where the compiler’s buggy, the only other advantage of looking at assembly over source code I can think of is if you’re programming a performance-critical application. In some cases where one particular function runs many times inside a loop, hand-optimizing the assembly code could be enough to improve runtimes by 25-50%. Just be aware that often times working at the source code level to improve things like cache coherence can be just as if not more important, so hand-optimizing assembly code should only very rarely be the tool you reach for to improve performance.

That said, there are a lot of situations where you don’t have the source code: most programs you run are produced by private companies that keep their source code private as one means of protecting their secrets. A few examples of practical places you might want to use a disassembler:

1. If you’re working to understand and counteract a new computer virus, reading the assembly code of the virus is necessary since the hacker producing it isn’t likely to give you the source code.
2. If you’ve just found a new method of exploiting or taking over programs and you want to check whether common programs are vulnerable to it, you may need to disassemble those programs to check.
3. If you’re modding a videogame, you won’t have access to source code, but you need to figure out where key data and functions are so that you can change what they do. Some games might come with a programming API or even be open-source, but that’s not the norm.

The cmp instruction is short for “compare” but it doesn’t actually do that. It effectively does that in combination with one of the jump instructions, however. What it does do is subtract the two operands, throw away the result, but set flags based on that result. The flags are things like Zero, Sign, Overflow, etc. which we saw in the HW ISA. Since cmp sets the flags and instructions like je or jg check them, they work together. However, instructions like add that store results in registers also set flags, so the cmp instruction typically needs to be right before the jump instruction.

Since cmp subtracts and je checks the zero flag (jumping if it’s set), together cmp followed by je will jump if the things that were compared are equal. But je following a different instruction may have a different meaning. The test instruction works like cmp, except the operation it performs is bitwise AND (still setting flags based on the result of that operation). This means that jump instructions following test will have different meanings than usual.

We know that certain registers are used for specific arguments: the mnemonic “Diane’s silk dress costs $89.” helps name %rdi, %rsi, %rdx, %rcx, %r8, and %r9 as the registers for the first 6 arguments (with further arguments getting pushed on the stack, which complicated things).

We’ve talked about gdb and valgrind, including both more and less advanced ways of using gdb. We’ve also supplied testing files and had you write some tests so that if there are errors in your program you’re likely to catch them. You also know how to use printf to print out values after using #include <stdio.h>. My typical debugging flow would probably be:

1. Run tests, and look for errors either from valgrind or from the tests themselves. Note relevant line numbers in my code. If things are crashing badly, run with gdb and use backtrace to get line numbers of where the crash happens.
2. Do a quick spot-check of the relevant line to see if there’s something simple I can fix, like a missing semicolon. Note that the error may be on the line above or below in some cases, especially with missing semicolons or curly braces.
3. In all likelihood, I won’t see the error immediately, so I’ll throw a printf in there right before the line where the error is. If I don’t have any line number because a test is failing but the code isn’t crashing, I’ll try to figure out based on which test it is what part of the code might be wrong, and add printfs there. If I really have no idea, I’ll try to add printfs to the first loop in my program to see if I can validate its behavior, and then after doing that, I’ll move on to the next loop, etc., trying to isolate the source of the issue.
4. From the printed output, hopefully I can figure out what’s wrong and how to fix it. This would be a good time to ask on Zulip and/or during office hours if there’s something that you just don’t understand, although checking relevant references beforehand is also a good idea (e.g., is there a function you’re not 100% sure about that you might look up?).
5. If things are really tricky, I might consider using gdb to set breakpoints and step through the code. gdb lets me pause at any step and also print out any values that might be relevant. You can also use dispaly to set up automatic prints that will be shown every time a breakpoint triggers. Combining this with a breakpoint on the first line inside a loop can be very powerful, because unlike print statements in the code, it’s easier to change them around when you figure out the next thing you want to look at.

Basically, the CPU needs to do a lot of memory accesses, so in addition to general-purpose math circuits like an ALU, it has a specialized circuit to do pointer math. Since pointer math involves a base pointer, an index within that array, a scaling factor, and potentially an additional offset, this special-purpose circuit performs two additions and one multiplication in a single step: offset + base + index * scale. Since it’s designed to do exactly that sequence of operations, it’s faster to use that circuit than to perform three separate steps with a general-purpose ALU (especially since the multiplication is restricted to scales of 1, 2, 4, or 8 so it can be implemented using bit shifting). That means that if we have a sequence of operations that turns out to fit into the from A + B + C * D (where D is 1, 2, 4, or 8), it’s better to use lea to do them all at once.

One more advantage: lea does not set flags based on its result. This means that if for some reason you want to do some arithmetic between a compare and the associated jump, you can use lea for that (see the answer on the cmp for more details).

In terms of differences from mov, both lea and mov update their second argument based on their first argument. mov directly copies between them, and can use a memory address as one of the two: either the source or the destination. When mov receives a memory address, it uses the specialized address computation unit to compute the address based on the values it was given, and then accesses that value in memory, either reading from it into a register, or writing from a register into that memory location. lea always has a memory address as the first argument and a register as the second, and while it uses the memory address unit to compute the final address, it then loads that address value directly into the destination register, rather than actually reading from memory at that address. Since variables are often stored at particular memory addresses, lea computes a pointer: it stores the address of the data into a register, instead of storing the data itself.

In the HW ISA, mov corresponds to both SW and LW, plus it can be used to copy data directly between two registers. It just depends on what kind of arguments it gets. lea doesn’t have an equivalent in the HW ISA, although it wouldn’t be hard to add one. We already have the ALU set up to perform addition between a register value and a constant from the instruction bits for the LW and SW instructions. If we direct that value back into a register instead of using it to read from memory, that would be the lea equivalent. Of course, it doesn’t support an index or scaling like lea does, but the HW ISA can’t do that for normal memory reads either.

lea is usually used when we use the & operator in C. If we do this:

int x = 7
int y = x;
int* z = &x;

The assignment to x might be implemented using mov $7, 8(%rsp), which moves a constant value (also called an “immediate” value) into a memory location (since it’s based on an offset from %rsp, we know it’s on the stack).

The assignment to y might then be done using one instruction: mov 8(%rsp), %rbx. That’s assuming we’re just using a register (%rbx in this case) to store y. Unlike x, y’s address isn’t used in this code, so it’s possible we can just store it in a register. If we wanted to store it in memory like x, we’d need two instructions, since we can’t move directly from memory to memory. We could do: mov 8(%rsp), %rbx followed by mov %rbx, 12(%rsp).

Each function call needs a scratch pad to store local variables that are active during the call. Whenever possible it’s nice if it can just use registers for this purpose, but sometimes there’s too much data to fit in registers, or it needs to pass a pointer into a function it calls referring to one of those variables, so that variable needs a memory address. We use the stack to provide this. Since the list of active functions at any point in time can be represented as a stack, where we push when a function is called and pop when it returns, that’s the data structure we use.

This is confusing because gdb is a little inconsistent about this! When using print or examine you need the $, when using info reg you don’t need any prefix, and in assembly code you’ll see % as a prefix, even though you never need to type that yourself in gdb.

Each different assembly instruction has a different meaning, and reads and/or writes registers in different positions. For example mov reads from its first argument and writes to its second (although either could be a memory location, in which case we’re reading from the register used to compute that memory location and writing to memory).

We’ll expect you to be familiar with the instructions listed on this sheet which includes a list of common instructions.

Sure. Just look up “x86 assembly jobs” online and you’ll see a few. It’s not super common, but still very necessary here and there. In many cases, it’s probably not someone’s full job just to program in assembly, but it’s part of a larger job where they use other language as well. Here are some examples of people who would use at least some assembly in their day-to-day job:

1. People maintaining and updating older systems where either they are directly programmed in assembly code or where programs in higher-level languages like FORTRAN or C might be checked for accuracy at the assembly level. For example, NASA recently sent a software update to the Voyager 2 spacecraft. You can read about its computer, which was originally programmed in FORTRAN, here. Systems that are old but still critical, like nuclear missile control & management systems, are probably still maintained by people who need to write assembly code.
2. Many computer security workers who deal with viruses need to be able to read and understand assembly code, since that’s all they have to work with. They may use a decompiler to try to come up with approximate C code corresponding to the assembly they see, but since hackers could write some routines in custom assembly code, they can’t just rely on those tools for everything.
3. The people who write compilers and develop operating systems need to understand assembly code, even if they might not write much by hand.
4. People who develop new hardware, like new CPU designs, need to be intimately familiar with assembly so that they can design new assembly languages and/or maintain backwards compatibility with existing ones.

The gdb commands that we assume you will understand include print, info reg, examine, backtrace, disas, start/run, break, step, stepi, and continue. list is another helpful command sometimes but not as critical, especially for the x86 assignment where we don’t give you source code. Thankfully, the help command in gdb is pretty good, so you can get reminders easily as you’re learning these. By the end of the x86 assignment, you’ll know them, one way or another.

There are several different things you can do to get your bearings in unfamiliar assembly code, so I’ll list them here:

1. Highlight all of the memory addresses used for jumps, using a different color for each unique address. This will help you trace how control flows through the code, even before you figure out the conditions of each jump. Also note function calls during this process (especially calls to trip_alarm in the x86 assignment) and ret instructions.
2. Highlight uses of the rdi, rsi, rdx, rcx, r8, and/or r9 registers. These will usually tell you how many arguments a function accepts and/or where it passes arguments to other functions it calls.
3. Look at places where rax (or a part of it like %eax) is used, tracing backwards from ret instructions and respecting the various possible jump paths. This will help you understand what goes into computing the function’s return value.
4. Look for where parentheses are used, since they indicate memory access. Is memory accessed based on the stack pointer, or another register? If it’s another register, where does that register get its value? How many different memory locations are accessed, and are we dealing with arrays and/or strings based on the use of an index register during memory access? Remember to account for return values from any functions that this function calls since those can be the source of memory addresses.

I’d pursue some or all of these strategies a bit before really diving into all the details of a function, since having context can help a lot in understanding details. I’d use the strategies above to answer questions like: does this function use conditionals? Loops? Recursion? What are the main data structures it uses? Just individual variables, or any arrays or strings? What other functions does it call, what arguments does it give them, and what does it do with their return values?

For the x86 assignment in particular, I’m always looking to answer the question: what path can be taken through this function to get to a return instruction without hitting any trip_alarm calls? The conditions used for the jumps necessary to take that path are the next points of inquiry for figuring out how to solve the phase.

Once I feel like I have some orientation in terms of the big ideas for the function, the next step is to make some assumptions about argument values and then run through the code line by line, executing instructions in my head and/or writing down results on paper. This step is tedious, but skipping it can waste a lot of time. Here you can use stepi in gdb to run the actual code instruction-by-instruction and check your results, although I wouldn’t necessarily do that at every step. Running through the code step by step doesn’t have to mean writing down every specific value. Instead I often keep a sense of which variable each register or stack location is storing, with an eye for which ones will be used by key jumps in the function. Based on this rough trace-through, I’ll come up with hypotheses, like “the first input number must be a 5 to gt through the first check.” It’s important to try to test these hypotheses piece-by-piece. You don’t want to develop 17 hypotheses only to find out that your first one was wrong and so are all the others. Use gdb to test out your hypotheses, and once you figure out how to navigate one jump, start developing hypotheses about the next one.

The push instruction is equivalent to the sequence:

sub $8, %rsp
mov <target>, (%rsp)

where <target> is the argument to push. So it modifies the %rsp register by subtracting 8, and then uses that register as a memory address to save the target value there. Note that if the size of the target value is not 8 bytes, the stack pointer may be moved by the size of the target value instead, so push %eax would subtract 4 bytes instead of 8, since %eax is only half of the %rax register.

What this accomplishes is saving the target value onto the stack, and growing the stack (downwards) to accommodate the new value. After a push, an instruction referring to (%rsp) is referring to the saved value (although if there are multiple pushes, older values will need offsets since %rsp will have moved further).

pop is the inverse of push. It translates to:

mov (%rsp), <target>
add $8, %rsp

call and ret work somewhat like push and pop, except the thing they push and pop is the “instruction pointer” which is the x86 equivalent of the program counter, and there are a few other wrinkles:

call doesn’t push the current instruction pointer (which would be pointing at the call instruction that’s being executed) but instead it pushes the address of the next instruction after that call. This means that when ret happens, we can continue the current function after the function call we just made.

ret pops the value written by call (assuming there are no errors in your stack pointer maintenance) and sets the instruction pointer to that value, rather than setting it to point to the instruction after the ret. This is how we “jump back” from a function, and how we can jump back from the same function into many different places depending on who called it.

For the basic allocator, the main inefficiency lies in fragmentation and in the time it takes to find free space starting from the beginning of the heap when many things have been allocated and/or freed. I’m not knowledgable about it, but I’m sure that coming up with better allocation algorithms is still an active area of research. Different applications often call for different space/time tradeoffs, so in some cases you might use a custom memory allocator for special applications. For example, if you’ve got a scientific program to crunch a bunch of data and it’s running out of memory, you could buy more RAM, but you might also want to try out a different memory allocator, even if it is a bit less time efficient. At the same time, if you’re running this calculation for weeks, finding a more efficient allocator might speed things up in a meaningful way, so you might be willing to trade off some space (especially if you can afford to buy more RAM). Of course, you’d want to first ensure that memory allocation really is a bottleneck for the program, rather than some other issue.

This is intentionally a pretty hard objective, because there are so many facets to it, and in particular, different kinds of allocation & freeing patterns might behave differently for different allocators, so in many cases there’s not an obvious “best” thing to do. We’re asking you to consider this problem a bit because it’s more like real un-curated problems you’ll face in the real world.

That said, the assignment itself has a lot of good hints here. The section on performance mentions next-fit allocation and an explicit free list as two things you can do to improve performance. Doing better than an explicit free list for throughput is probably pretty tough.

Memory mapping has two meanings. There’s an ‘mmap’ C function which allows you to directly map files (or regions of files) into memory, so that any alteration to that memory alters the file, and reading that memory reads from the file. There’s also the concept of virtual memory: the actual physical RAM of the computer is mapped into a virtual address space for each process, so that the different processes each think they have access to all of memory, but in reality, the parts they each use are mapped to separate regions of the real memory, so that they don’t have access to each others’ data.

The way that virtual memory works is quite complicated, involving some specialized hardware that’s part of the memory load/store process for looking up where a certain area of memory is actually stored (the data this hardware uses is called “page tables,” and this is where the term “page size” comes from).

If you start trying to write “more efficient” code without understanding whether your code works yet, and/or whether it’s actually too slow or using too much memory, you might:

1. Make your code needlessly complex, in a way that doesn’t actually speed it up.
2. Relatedly, introduce bugs into your code because of that complexity, which you could have avoided with simpler code.
3. Spend a lot more time building that complex code, when a simpler version that seemed less efficient might have been faster to build, giving you more time to actually measure its performance and fix any real issues that came up.

The footer/epilogue of the heap is marked as a “size-0” “allocated” block, and its previously-allocated bit is updated based on the allocated status of the block before it. The size being 0 is a clearly-invalid value that makes it easy to see if you end up getting a pointer to that epilogue. The other information is useful because other operations (particularly coalesce) can treat it as if it’s a normal block, and they don’t need any extra special cases to handle the end of the heap.

Calling free is the responsibility of the person who called malloc, so in our mm.c, we don’t need to do that anywhere. In our testing code, we have a “trace” system set up where we can read in a trace and call free when the trace says to do that. If you’re writing other code (like you did for Pointers) then it’s your responsibility to call free once you’re done using some memory. Of course, there may be some pieces of memory that you need to use for the entire time the program is running, so they might only be freed at the end (and in any case, when the process ends everything will get cleaned up automatically).

In malloc, we’re writing a system that others are going to use to allocate memory. They may use that memory for whatever purpose they want (like storing a command array :). From the perspective of the malloc code, we don’t care what the memory gets used for, we just need to ensure that nobody else will write to that memory (ourselves or other people who called malloc and obey the size limit they requested).

For a code design question like this, I often start with idealized variables and then work backwards to see how I can get those variables. This helps break the problem into smaller pieces (one for each variable) and it also makes it easier to test and verify each piece independently when debugging. For the coalesce cases, we need to know two “bits” of information, which will distinguish our four cases:

1. Is the previous block free?
2. Is the next block free?

The combinations of no/no no/yes yes/no yes/yes will then be the four coalesce cases (although with some designs it’s possible to share code between the cases too). So I might start by defining:

int prev_free = 0;
int next_free = 0;

I think it’s clearest if we translate into decimal and binary:

0x11 = 16 + 1 = 17 0x13 = 16 + 3 = 19

0x11 = 0b10001 0x13 = 0b10011

I’m not familiar with all the different malloc variants out there, but I’m sure someone has used those extra bits for something in some implementation, I just don’t have an example that comes to mind.

If I try to imagine what they could be used for, I can try to think of further optimizations that might be possible, but this is hard. For example, there might be some gains in marking which free block is the largest, because if you get a request for a larger allocation and you happened to find that block while searching, you could immediately skip to expanding the heap rather than continuing to check further free blocks. But that’s probably a terrible idea, because the time spent trying to maintain that “largest” bit correctly in each block would be a lot (storing a pointer to the largest block in the heap header would be cheaper). Also, how frequent is it really that we get an allocation request that’s larger than our largest free block (maybe not frequent) and what’s the cost of checking an extra bit in each free block (probably not worth it even ignoring the other issues).

So you can see it’s not easy to come up with other things that it’s useful to store, because anything you might store incurs costs to maintain that information and to check it.

Whenever you need to start a new background process, it’s easiest to use fork. Typically, if you use an if statement to have only the parent process continue with the code for the original program while using exec in the child process to replace that code with some other program, there’s much less risk of forking too many times. Usually you also don’t need to place fork within a loop, which can increase the risk of forking too many times.

Why would you want a “background process?” One common use case is when you need to pay attention to user input, but also process some data in the background. You could use one process that waits for user input and gives immediate feedback, while sending data inputs over to a second process that does something slow/expensive with those inputs. Even something as simple as showing a spinning loading icon while data is loading requires two things to happen at once: the spinning icon needs to be constantly updated, and the loading needs to happen. This kind of thing is more often handled by threads than processes, because threads can more easily share data with each other, but the same logic applies.

We care about the order because if we want to coordinate work between multiple processes, there may be things that need to happen in a certain order, such as one process writing a result into a file before another process tries to read it.

The order becomes unpredictable because as soon as there are multiple processes, the operating system can choose to schedule them in any order. Depending on how many other processes there are and other uncontrollable factors, the OS may schedule different processes to run for different amounts of time, and in different orders.

jobs lists the running jobs in the current terminal. A “job” consists of one process that was launched directly from the terminal, plus all child processes of that parent. The fg command brings a paused job back to the foreground to resume it. You can use control-Z to pause a job, after which fg can resume it. The bg command also resumes a job, but lets it run in the background, so you can still use the terminal for other stuff while it’s running.

While threads (a related technique) can share some variables, processes do not share variables. Of course, they are created as clones of each other, so both the parent and child process have access to all the same variables when they start up. But they “don’t share” variables because when one of them changes a variable, the other one won’t see that change. Effectively, when we create the child process, we copy the entire state of memory over to the child, and any modifications in either the parent or the child are done on separate copies so they don’t affect each other.

fork is the main C library function for creating processes, although there are probably custom higher-level process-management libraries that you could use instead. However, there’s another simpler answer: the user might intentionally launch multiple processes. If you remember the Pointers Assignment, we made a big deal of ‘&’. That’s because in the shell, you can add ‘&’ after a command to start it running in the background, not the foreground. This lets you launch other programs immediately, so you can launch multiple at once. Same would apply if you open multiple terminals (each of which is its own process) and then launch multiple programs at the same time.

You “just” need to trace through the code and keep track of any forks that happen, tracing them separately. Then account for all the possible ways that those traces might be interleaved after the fork(s) happen(s). This is… hard. Drawing diagrams helps, but fundamentally parallel programming is an incredibly challenging thing, and often keeping forking patterns as simple as possible is a good idea if you’re the one writing the code.

All processes/threads share a single RAM. Sometimes this is actually multiple RAM chips if you’ve added extra RAM to your computer, but the operating system manages these as one unit to display a consistent pool of memory to running processes.

Of course, if that’s true, why don’t different processes overwrite each other’s data all the time? Well, there’s something called memory virtualization which means that where a process thinks things are stored is not where they’re actually stored. Every time memory is read or written, the address used by the process goes through a translation step that maps it to a different part of the actual hardware RAM. The OS makes sure to map memory used by different processes to different parts of the physical RAM, even while ensuring that they each think they have access to all available RAM. It also leaves unused sections of memory un-mapped until they’re requested, so that it can fit the active memory regions from many many processes together into the single actual RAM.

To find out the behavior of an unfamiliar function like atoi, a quick search for a reference site usually suffices, although the reference sites are becoming harder to find and less reliable these days… The man program (short for manual) also has references for most C library functions, so running man atoi in a terminal would work.

The OS has a “scheduler” which decides which process to run next whenever a process either voluntarily gives up control or is explicitly interrupted. Any time a system call is made (like when calling printf) this gives the OS a chance to smoothly interrupt the process, since the process is asking the system to do some work for it anyways. Once a process is selected, after it runs for a bit it will be interrupted and another process will be swapped in. The scheduler is responsible for making sure that each process gets a turn, while also ideally letting processes that are more important or which have more work to do get a bit more time than others. But since context swaps happen hundreds to tens of thousands of times per second, from a human perspective it looks like multiple processes are happening simultaneously.