Machine-Level Program Representation

Created

Compilation

A computer can only directly execute machine code. So high level programming languages (Java, Python, C, C++, ...) need to be translated to machine code. The ways to do that are:

  • interpretation: a program "interprets" high-level code and carries out the specified computation
  • compilation: a compiler program translate the high-level code into macahine code
  • hybrid strategies (e.g., Java Virtual Machine).

When compiling a C program:

  1. C source code: cprog.c is compiled to Assembly code cprog.s through gcc -s cprog.c
  2. Assembly code is assmbled into object code cprog.o through gcc -c cprog.s
  3. Object code is linked through gcc- o cprog cprog.o into an executable cprog.

Comparing C vs Assembly code vs Machine code: C code

long times10(long x) {
	long result = (x<<3) + (x<<1);
	return result;
}

C code is compiled to Assembly code

times10:
	leaq (%rdi,%rdi), %rax
	leaq (%rax,%rdi,8), %rax
	ret

Assembly code must be assembled into machine code:

48 8d 04 3f
48 8d 04 f8
c3

The CPU directly decodes and executes machine instructions.

x86-64 assembly programming

We learn assembly in order to:

  • Have complete control over hardware
  • Understand hardware-level program execution
    • important for understanding security vulnerabilities, and how to avoid introducing them.
  • Optimize performance-critical code.
  • Implement code generators (compilers, JIT compilers).

x86-64 (often called "x64") is the most mainstream processor.

  • The first 64-bit x86 CPU was the "AMD64".
  • Subsequent Intel CPUs adopted the AMD64 architecture calling it "EM64T".

x86-64 Registers

Registers are like variables built in the processor. We use these instead of memory to store values to make the process faster and cleaner.

These registers are 8 bytes (64 bits).

  • %rip is an instruction pointer. Always stores the address of the next instruction. This is how instructions are sequenced. Naturally, we go sequentially. However, a branch instruction will jump to a different location. This is the basis of control constructs.
  • %rsp, %rbp: Stack pointer/frame pointer keeps track of where the stack frame is (the most recent one). Everytime you execute a function, we need to access temporary data.

These are the general-purpose registers

  • %rax: function return value.
  • %rdi, %rsi
  • %rbx , %rcx, %rdx
  • %r8, %r9, ...

"Sub"-registers

For historical reasons, each data register (e.g., %rax) is divided into

  • low byte (bit 0 to 8) (%al)
  • second lowest byte (bit 8 to 16) (%ah)
  • lowest 2 byte (16 bits) (%ax)
  • lowest 4 bytes (32 bits) (%eax)

Some of our data values are not necessarily 64 bits, so thats why you might put it in a sub register.

  • For %r10 the alias for the lower 32 bit is %r10d. When you store a value in this lower area, it will clear the upper 32 bits.

Memory

Conceptually, memory is a big array of byte-sized storage locations. Each of these locations has an address.

In x86-64, addresses are 64 bits, so 2642^64 addresses.

  • Not all these addresses are used
  • Virtual Memory creates an arbitrary mapping of address to physical memory (actual RAM). This is where your program is run. This allows every program to have their independent address space while letting them have their independent memory (not shared).
  • Virtual memory is mapped "sparsely": only some ranges of addresses are mapped to actual memory.

The memory layout of a C program can be inspected using hte pmap command. (view the memory map of the running program):

29208: ./art 
0000562d71c36000 4K r-x-- art
0000562d71e36000 4K r---- art
0000562d71e37000 4K rw--- art
0000562d735fc000 132K rw--- [ anon ]
00007f7b5b9a5000 1948K r-x-- libc-2.27.so
00007f7b5bb8c000 2048K ----- libc-2.27.so
00007f7b5bd8c000 16K r---- libc-2.27.so 
00007f7b5bd90000 8K rw--- libc-2.27.so 
00007f7b5bd92000 16K rw--- [ anon ]
00007f7b5bd96000 156K r-x-- ld-2.27.so
00007f7b5bfa0000 8K rw--- [ anon ]
00007f7b5bfbd000 4K r---- ld-2.27.so
00007f7b5bfbe000 4K rw--- ld-2.27.so
00007f7b5bfbf000 4K rw--- [ anon ]
00007fff84484000 132K rw--- [ stack ] 
00007fff845d4000 12K r---- [ anon ]
00007fff845d7000 8K r-x-- [ anon ]
ffffffffff6000004K r-x--[ anon ]
total 4512K
  • The first line is the process name (art) and its PID.
  • The first part (0000562d71c36000) is a mapped memory address
  • The second part (4K) is the amount of memory at that address
  • The last bit art, [ anon ], [ stack ] indicates the location: memory, heap, or stack

Stack

The stack is an important runtime data structure. It is a stack of activation records (a.k.a. "stack frames")

A stack frame represents an in-progress function call, and contains:

  • return address (address of instruction where controls should return to when the function returns)
  • local variables
  • temporary data

The %rsp register is the stack pointer.

  • Contains the address to the "top" of stack, which will be the most recent function called.
  • The actual stack grows down (higher addresses to lower addresses), so %rsp decreases as the stack grows.

Assembly Language

  • Assembly code is a sequence of instructions that is executed sequentially.

  • Each instruction has a mnemonic that show what it does (mov, push, add, etc.)

  • Most instructions will have one/two operands that specify data values (input and/or output).

On Linux, we use "AT&T" assembly syntax. Intel and Microsoft have different syntax, but you can focus on AT&T if you are working on Linux.

  • In this syntax, the source is the first operand, and the destination is the second.

Assembly Code Structure

Assembly code specifies both code and data. It is written like in high level languages.

A label is like a name that marks the location of a chunk of code and/or data. Syntax:

nameOfLabel:
	labled code or data
  • When assembly code is ran, then its code and data are loaded into memory.
  • The label is the address of the location in memory of the code/data
  • Synonymous with memory addresses. Use label as memory addresses in assembly code.

Operands

Operand size suffixes state what size operand the instruction is going to use.

  • b represents 1 byte as "Byte"
  • w represents 2 byte as "Word"
  • 1 represents 4 byte as "Long" word
  • q represents 8 byte as "Quad" word

You can omit the operand size suffix, but it is recommended you always use it. Being explicit helps for readability and you can catch bugs.

Example: movq means move a 64 bit value.

Assembly operand： Assume count and arr are labels indicating the addresses of global variables. R is a register, N is an immediate, S is 1, 2, 4, or 8.

  • addr is a Memory ref. It gets the content of memory location specified by absolute memory address.

    • e.g., count

  • $N is an immediate. Use the $ to indicate the literal numeric value.

    • E.g., $8 would be the value 8 and $arr would be the address of arr.

  • R is a register.

    • E.g., %rax

  • (R) is a memory ref.

    • E.g., (%rax) is a pointer deref. The address = %rax.

  • N(R) is a memory ref that has a offset.

    • E.g., 8(%ref) is a field ref. The address = %rax + 8

  • (R,R) is a memory ref with an offset

    • E.g., (%rax, %rsi) is the content of address = %rax + %rsi

  • N(R,R) accesses the address = R + R + N

  • (,R,S) accesses the contents of address = R*S

  • (R1,R2,S) accesses the contents of address = R1+(R2*4)

  • N(,R,S) accesses the contents of address = (R*S)+N

  • N(R1,R2,S) accesses the contents of address = R1+(R2*4)+N

Data Movement 90% of assembly code is data movement. These are common ways to move data:

mov: copy source operand to destination operand. You can operate on the:

  • Register
  • Memory Location (only one operand can be a memory location)
  • Immediate value (source operand only)

Stack manipulation: push and pop.

  • Generally used for saving and restoring callee-saved register values
  • push decrements %rsp by operand size (l, w, copy operand to (%rsp)
  • pop copies (%rsp) to operand, increment %rsp by operand size.

Examples:

  • movq $42 %rax stores the constant value 42 into %rax

Extension

When moving a smaller source vaue to a larger destination, sign-extension (copying sign bit to the high bits) is necessary to preserve the value of a signed value.

  • E.g., the value of -16381 is represented as 1100000000000011 (16 bits) or 11111111111111111100000000000011 (32 bits).

To perform data movement with sign-extension, use movsbw, movsbl, movswl, etc. For unsigned values, data movement with zero-extension (copy 0 into high bits), use movzbw, movzbl, movzwl, etc.

Essential Knowledge

Use .S extension for assembly code.

  • Will be run through the C preprocessor.
  • You can use C style comments (/**) and #define to define named constants.

Use gcc to assemble .S files into object code (.o). Then, use gcc to link these object files into executable.

/* hello.S */
.section .rodata
sHelloMsg: .string "Hello, world\n"
.section .text

        .globl main
main:

        subq $8, %rsp
        movl $0, %eax
        movq $sHelloMsg, %rdi
        call printf

        addq $8, %rsp
        ret
  • .section .rodata is the read only data section
    • sHelloMsg: .string "Hello, world\n": The label sHelloMsg reads a NUL terminated string constant (done automatically because of the "").
  • .section .text is where the code goes.
    • .globl main directive makes main visible to other modules. Mark as public symbol in the object file.
  • main: we define the main function.
    • subq $8, %rsp aligns the stack pointer. The x86 convention says that the stack pointer must point to a multiple of 16. After the call instruction, you are in the main function, and the return address has been pushed onto the stack. The stack is now misaligned by 8 bytes because the return address is 8 bytes. This is why we subtract 8 from the stack pointer. Now, the stack pointer is pointing to a multiple of 16.
    • movl $0, %eax When you call a function that takes a variable number of function arguments, the first 6 are store automatically. However, when there are more than 6 arguments, then you need to tell them how many vector arguments are there. So when we set %eax to 0, we are saying that printf is taking 0 arguments.
    • movq $sHelloMsg, %rdi passes the pointer to the address of the message string.
      • $ produces the memory address of the label's data.
      • We want %rdi to point to the address of the message instead of the actual characters.
    • call printf calls the function.
      • For any names that the assembler does not know, there will be a placeholder that will be resolved by the linker.
    • addq $8, %rsp restores the stack pointer because we moved it previously. Now, it'll point back at the return address that it was at initially.
    • ret returns the precise location that %rsp is at. It returns from main, and ends program.

Assembling, linking, executing

$ gcc -c -no-pie -o hello.o hello.S 
$ gcc -no-pie -o hello hello.o  
$ ./hello
  • Note that the -no-pie option disables support for position-independent code (which would require additional magic in the assembly source code)

Output

Hello, world

Linked from Computer System Fundamentals