CSE 351 Notes

Where \(w\) is word width:

• Umax: \(2^w-1\)
• Umin: 0
• Tmax: \(2^{w-1}-1\)
• Tmin: \(-2^{w-1}\)

The first bit is 1 when negative, and if so, the value of the number is \(-2^{w-1}\) plus the value of the remaining bits. Inverting a number is ~​b+1.

Casting a number between signed and unsigned reinterprets the bits in-place.

Two's complement numbers with width w can be between \(-2^w\) and \(2^w-1\), inclusive. It is evenly distributed across positive and negative in the sense that "There are an equal number of nonnegative numbers and nonzero negative numbers representable in a given

Most bitwise operations don't care about the type, with the primary exception of >>: If you right-shift a signed number, rather than filling with zeroes from the left, it fills with whatever the leftmost bit was. So 0b10010001 >> 3 = 0b11110010.

Sizes:

• %rax: 64-bit
• %eax: 32-bit
• %ax: 16-bit
• %ah: Upper 8 bits of %ax
• %al: Lower 8 bits of %ax
• %r11: 64-bit (general purpose)
• %r11d: 32-bit
• %r11w: 16-bit
• %r11l: 8-bit (no upper)

Some registers (si, di, sp, bp) do not have upper and lower 8-bit parts. Best reference (not mine):

• b: Byte, 1 byte
• w: Word, 2 bytes
• l: Long, 4 bytes
• q: Quad, 8 bytes

Normal:

• mov: Move arg 1 into arg 2
• add: Add arg 1 to arg 2
• sub: Subtract arg 1 from arg 2
• or, and, xor, not
• movs: Takes two length suffixes. Does a signed extension that takes a value of the first length and puts it into the second length.
• lea: The first argument must be a memory operand, and the second must be a register (because you can't have both operands to any instruction be memory). lea, while primarily for pointer arithmetic, can also be used for arbitrary arithmetic
• mul, imul: Unsigned and signed multiplication, respectively.
• div, idiv: ^^^ division. Remainder stored into first operand.
• cltq: aka cdqe in Intel, performs extension of eax into rax. Equiv to movlq %eax, %rax?

Flow Control:

• cmp: Set condition flags equivalent to sub on the same arguments, but do not mutate the second argument.
• test: Like cmp, but flags set according to and.

The following bits are set by many arithmetic functions:

• ZF: Whether the result was zero (Zero Flag).
• SF: Whether the result was negative (Sign Flag).
• OF: Signed Overflow (Overflow Flag). Eg, 127+127 will trigger it, but not 127+(-5), even though the last case sets both SF and CF.
• CF: Unsigned Overflow (Carry Flag). During subtraction, it means a borrow was required (i.e, the first argument is smaller than the second, unsigned-wise. So the CF is set when subtracting a negative from a positive).

The "jump" commands go to a certain label, while the "set" commands update a certain location (1-byte set only):

Perhaps untinuitively, jmpge, for example, doesn't actually check that the first operand of the preceding cmp was greater than or equal to the second operand – it checks that the result of subtraction is greater than or equal to zero.

• %rdi: (for example) a register
• $95: Immediate integer. May be negative, with signed stuff based on the context (expected argument type of the instruction, which is always inferrable from the instruction).
• D(base,index,scale): Dereference the memory at base+index*scale+D (except for lea, which does not dereference). Scale must be 1, 2, 4, or 8. Note that D is not affected by scale.

Introduced by writing asm or __asm__ (if using –std which disables un-prefixed GNU extensions):

asm("xorw $-1, %[output_name]"
        : "output_name" "+r" (c_var)
        : "input_name" "I" (other_c_var), "input_2" "r" (third_c_var)
        : "r16", "eax");

Each output operand has three parts (though the first is optional):

1. The symbolic name that can then be used inside the asm as %[sym_name]
2. A "constraint" with regards to how the value can be passed into the program. Here, + indicates that the variable is for both input and output, and the r indicates that it must be placed into a register. An = instead of a + makes it for output only.
3. A single c variable, in parenthesis for some reason, where the value should come from.

The inputs are similar, but no = or + needed in constraint. Useful constraints other than r include:

• i: Immediate integer.
• p: Memory address.
• F: Immediate float.
• m: "Memory operand" (not sure how it's passed in…maybe the same way as p, but it takes the address of the c variable passed in rather than assuming the c variable itself is a pointer?)

Finally, the last comma separated "clobbers" "list is other registers that the asm may dirty.

It's also possible to specify memory and stuff here using special syntax.

Full documentation: https://gcc.gnu.org/onlinedocs/gcc/Extended-Asm.html

call (which does require a length suffix, eg callq?) jumps to the specified location in memory and begins executing from there. Call pushes the next instruction (after call) onto the stack. Then, ret pops from the stack then jumps to the address stored there. And that's how babies are made!

Arguments are in the following order:

1. rdi
2. rsi
3. rdx
4. rcx
5. r8
6. r9

"Di​ane's Si​lk D​ress C​osts $​89.

Additional arguments are stored on the stack, with the first arguments pushed last, so that when popped they can be accessed first. Arguments are pushed before the return address (necessarily, because call must be invoked after any pushing).

%rax stores the return value.

These registers are all "calling conventions". These are GNU's.

Some registers are, by convention, "callee-saved", while others are "caller-saved". The callee-saved ones are expected to be pushed and popped from the stack at the beginning and end of any function that uses them. On the other hand, it's safe to mutate caller-saved registers whenever you want; just be aware that subroutines may mangle them.

Caller-saved: RAX, RCX, RDX, R8, R9, R10, R11 (ie, subroutines may mangle them)

Callee-saved: RBX, RBP, RDI, RSI, RSP, R12, R13, R14, R15 (all the non-caller-saved)

Historically, %rbp points to the beginning of the current stack frame (depending on convention, either the addres to jump to after the current procedure, or the first byte of either the saved stack variables or local variables.

• continue or c: Run to breakpoint.
• step: Step until next line of C code. If no -g, keeps going until a function with debug symbols (not recommended!)
• stepi: Step one assembly instruction.
• next: Like step, but will not enter functions.
• nexti: Like stepi, but doesn't step into call instructions.
• finish: Run until ret.

Lets you view source, assembly, and/or registers, breakpoint locations, etc as you run.

Enter by running layout <layout>, with:

• split: Asm + C
• src
• asm
• regs

c-x 2 will toggle through the side-by-side modes. unfortunately, c-x 1 doesn't toggle.

run focus next to switch focus to the next window if necessary.

The "top" of the stack (lowest address) is stored in %rsp. Usually push and pop (with appropriate suffixes) will automatically manipulate the pointer and add or remove data from the stack (pop places that data into the specified location). However, if multiple items need to be removed from the stack, it's totally legal to just addq $12, rsp to remove 12 bytes.

Several layers, from DRAM system memory down to close-to-the-chip SRAM caches. Main performance metrics:

• Hit time: How long it takes to retrieve data on cache hit
• Miss time: How long it takes to retrieve data from the next layer on cache miss, in addition to hit time.
• Average Memory Access Time (AMAT): Takes into account both hit time, miss time, and hit rate. Equal to hitTime+(missRate*missTime).

A "block" is a piece of memory that can be moved into the cache in a single operation.

Different "placement" and "replacement" (eviction) schemes determine how memory is put into caches, and what data is removed from those caches to make space for the new data.

Each process thinks it has 64 bits of free memory! The fools! In reality, memory is split into pages (4KiB by default?), and the Memory Management Unit/MMU maintains a "page table" for each process. On the left side of the table are Virtual Page Numbers, and on the right side are Physical Page Numbers. The table also contains, for example, permissions (read/write/execute) and information about pages that are swapped out to disk.

The MSBs of the virtual address refer to the page number, and the LSBs refer to the page offset.

Although page tables are stored in memory, VPN-to-PPN translation is performed by hardware in the MMU. When the MMU encounters a VPN that is not mapped to a PPN, eg it's swapped out, then it triggers a fault and jumps to a handler in the kernel which loads the page into physical memory, updates the page table, then restarts the failed instruction, at which point the MMU does a normal lookup. The kernel can see and modify page tables; it's just memory!

Header bytes count as internal fragmentation for purposes of the exam. So, if you have an 8-byte header on each page, then all pages have at least 8 bytes of internal fragmentation.