Why need to understand machine code?
So why should we spend our time learning machine code? Even though com- pilers do most of the work in generating assembly code, being able to read and understand it is an important skill for serious programmers. By invoking the compiler with appropriate command-line parameters, the compiler will generate a file showing its output in assembly-code form. By reading this code, we can under- stand the optimization capabilities of the compiler and analyze the underlying inefficiencies in the code.
Programmers seeking to maximize the performance of a critical section of code often try different variations of the source code, each time compiling and examining the generated assembly code to get a sense of how efficiently the program will run. Furthermore, there are times when the layer of abstraction provided by a high-level language hides information about the run-time behavior of a program that we need to understand. For example, when writing concurrent programs using a thread package, as covered in Chapter12, it is important to understand how program data are shared or kept private by the different threads and precisely how and where shared data are accessed. Such information is visible at the machine-code level. As another example, many of the ways programs can be attacked, allowing malware to infest a system, involve nuances of the way programs store their run-time control information. Many attacks involve exploiting weaknesses in system programs to overwrite information and thereby take control of the system. Understanding how these vulnerabilities arise and how to guard against them requires a knowledge of machine-level representation of programs.
The need for programmers to learn machine code has shifted over the years from one of being able to write programs directly in assembly code to one of being able to read and understand the code generated by compilers.
上次提到为什么要用C学系统：
x86 is intel product line
Instruction set architecture
The format and behavior of a machine-level program is defined by the instruction set architecture or ISA. Most ISA describe the behavior of a program as if each instruction is executed in sequence, with one instructino completing before the next one begins.
机器底层的实现逻辑永远是简单的，只不过经过了各种组合以及叠加才变得复杂并且能够实现近乎神奇般的功能
就好像air foil的作用，能组成gas turbines，也可以用来做机翼
Assembly code
Assembly-code representation is very close to machine code. Its main feature is that it is a more readable textual format.
Whereas C provides a model in which objects of different data types can be declared and allocated in memory, machine code views the memory as simply a large byte-addressable array. Aggregate data types in C such as arrays and structures are represented in machine code as contiguous collections of bytes.
The machine code for x86-64 differs greatly from the original C code. Parts of the processor state are visible that normally are hidden from the C programmer.
- The program counter (known as PC, and called %rip in x86-64) indicates the address in memory of the next instruction to be executed.
- The integer register file contains 16 named locations storing 64 bit values. These registers can hold addresses (corresponding to C pointers) or integer data. Some registers are used to keep track of critical parts of the program state, while others are used to hold temporary data, such as the arguments and local variables of a procedure, as well as the value to be returned by a function.
- The condition code registers hold status information about the most recently executed arithmetic or logical instruction. These are used to implement if and while statements.
- A set of vector registers can each hold one or more integer or floating-point values.
Machine code views the memory as simply a large byte-addressable array. Aggregate data types in C such as arrays are represented in machine code as contiguous collections of bytes.
A single machine instruction performs only a very elementary operation. For example, it might add two numbers stored in registers, transfer data between memory and a register, or conditionally branch to a new instruction address. The compiler must generate sequences of such instructions to implement program constructs such as arithmetic expression evaluation, loops, or procedure calls and returns.
The program memory contains the executable machine code for the program, some information required by the OS, a run-time stack for managing procedure calls and returns (这里没准还要回来看), and blocks of memory allocated by the user (by malloc function). A program memory is addressed using virtual addresses. More typical programs will only have access to a few megabytes, or perhaps several gigabytes. OS manages this virtual address space, translating virtual addresses into the physical addresses of values in the actual processor memory.
running code on linux
rax rbp 名字由来
An x86-64 central processing unit (CPU) contains a set of 16 general-purpose registers storing 64-bit values. These registers are used to store integer data as well as pointers. Figure 3.2 diagrams the 16 registers. Their names all begin with %r, but otherwise follow multiple different naming conventions, owing to the historical evolution of the instruction set.
The original 8086 had eight 16-bit registers, shown in Figure 3.2 as registers %ax through %bp. Each had a specific purpose, and hence they were given names that reflected how they were to be used. With the extension to IA32, these registers were expanded to 32-bit registers, labeled %eax through %ebp.
In the extension to x86-64, the original eight registers were expanded to 64 bits, labeled %rax through %rbp. In addition, eight new registers were added, and these were given labels according to a new naming convention: %r8 through %r15.
下面这张图很好表达了register 不同名字以及他们对应的大小
Data movement instructions
Among the most heavily used instructions are those that copy data from one location to another. The generality of the operand notation allows a simple data movement instruction to express a range of possibilities that in many machines would require a number of different instructions.
Figure 3.4 lists the simplest form of data movement instructions—mov class. These instructions copy data from a source location to a destination location, without any transformation. The class consists of four instructions: movb, movw, movl, and movq. All four of these instructions have similar effects; they differ primarily in that they operate on data of different sizes: 1, 2, 4, and 8 bytes, respectively.
The source operand designates a value that is immediate, stored in a register, or stored in memory. The destination operand designates a location that is either a register or a memory operand designates a location that is either a register or memory address.
x86-64 imposes the restriction that a move instruction cannot have both operands refer to memory locations. Copying a value from one memory location to another requires two instructions -- the first to load the source value into a register, and the second to write this register value to the destination.
Data movement example
When the procedure begins execution, procedure parameters xp and y are stored in registers %rdi and %rsi, respectively. Instruction 2 then reads x from memory and stores the value in register %rax, a direct implementation of the operation x = *xp in the C program. Later, register %rax will be used to return a value from the function, and so the return value will be x. Instruction 3 writes y to the memory location designated by xp in register %rdi, a direct implementation of the operation *xp = y. This example illustrates how the mov instructions can be used to read from memory to a register (line 2), and to write from a register to memory (line 3).
pointer dereferencing. 如果*是在assignment 右边，那就是读取。如果在左边，那就是写入
practice problem 3.5
反馈还是挺重要的。根据这道题给的assembly code 写出c source code。
下面是我的c code， 用gcc -Og -S compile之后的assembly code 也是对应上了，可以加深对于how register works 的理解
Procedure call
这个之前leon问到过，procedure call is same as function call or method call in OOD. It utilize stack to return to previous state.
Pushing and poping stack data
The pushq instruction provides the ability to push data onto the stack, while the popq instruction pops it. Each of these instructions takes a single operand --the data source for pushing and the data destination for popping.
Pushing a quad word value onto the stack involves first decrementing the stack pointer by 8 and then writing the value at the new top-of-stack address. Therefore, the behavior of the instruction pushq %rbp is equivalent to that of the pair of instructions
subq $8, %rsp //Decrement stack pointer
movq %rbp, (%rsp) //store %rbp on stack
except that the pushq instruction is encoded in the machine code as a single byte, whereas the pair of instructions shown above requires a total of 8 bytes. The first two columns in Figure 3.9 illustrate the effect of executing the instruction pushq %rax when %rsp is 0x108 and %rax is 0x123.
The third column of Figure 3.9 illustrates the effect of executing the instruction opoq %edx immediately after executing the pushq. Value 0x123 is read from memory and written to register %rdx. Register %rsp is incremented back to 0x108. As shown in the figure, the value 0x123 remains at memory location 0x104 until it is overwritten (e.g. by another push operation). However, the stack popo is always considered to be the address indicated by %rsp.
Since the stack is contained in the same memory as the program code and other forms of program data, programs can access arbitrary positions within the stack using the standard memory addressing methods. For example, assuming the topmost element of the stack is quad word, the instruction **movq 8(%rsp), %rdx will copy the second quad word from the stack to register %rdx
3.5 Arithmetic and logical operations
Most of the operations are given as instructions classes, as they can have different variants with different operand sizes. (same as movb, movw, movl, movq) b stands for byte, w stands for word, l stands for double word, q stands for quad word
For example, the instruction class ADD consists of four addition instructions: addb, addw, addl, and addq
(same as move class with different sizes)
The operations are divided into four groups: load effective address, unary, binary, and shifts. Binary operations have two operands, while unary operations have one operand. These operands are specified using the same notation as described in Section 3.4
3.5.1 Load effective address
The load effective address instruction leaq is actully a variant of the moveq instruction. It has the form of an instruction that reads from memory to a register, but it does not reference memory at all. Its first operand appears to be a memory reference, but instead of reading from the designated location, the instruction copies the effective address to the destination.
这里就更加清楚为什么C语言里会有&这个这个operator了，因为他能从cpu instruction里面调用effective address 然后进行后面的操作。
We indicate this computation in Figure 3.10 using the C address operator &S. This instruction can be used to generate pointers for later memory references. In addition, it can be used to compactly describe common arithmetic operations. For example, if register %rdx contains value x, then the instruction
leaq 7(%rdx, %rdx, 4), %rax
will set register %rax to 5x + 7. Compilers often find clever uses of leaq that have nothing to do with effective address computations. The destination operand must be a register.
Operations in the second group are unary operations (位运算）, with the single operand serving as both source and destination. This operand can be either a register or a memory location. For example, the instruction incq(%rsp) causes the 8-byte element on the top of the stack to be incremented. This syntax is reminiscnet of the C increment(++) and decrement(--) operators.
The third group consists of binary operations, where the second operand is used as both a source and a destination. This syntax is reminiscent of the C assignment operators, such as x -= y. Observe, however, that the source operand is given first and the destination second. This looks peculiar for noncommutative operations. For example, the instruction subq %rax, %rdx decrements register %rdx by the value %rax The first operand can be either an immediate value, a register, or a memory location. The second can be either a register or a memory location. As with the MOV instructions, the two operands cannot both be memory locations. Note that when the second operand is a memory location, the processor must read the value from memory, perform the operation, and then write the result back to memory.
3.5.3 shift operations
The final group consists of shift operations, where the shift amount is given first and the value to shift is given second. Both arithmetic and logical right shifts are possible. the different shift instructions can specify the shift amount either as an immediate value or with the single-byte register %cl. In principle, having a 1-byte shift amount would make it possible to encode shift amounts ranging up to 2^8-1 = 255. With x86-64, a shift instruction operating on data values that are w bits long determines the shift amount from the low-order m bits of register %cl, where 2^m = w. The higher-order bits are ignored. So, for example, when register %cl has hexadecimal value 0xFF, then instruction salb would shift by 7 (one byte), while salw would shift by 15(2byte). sall would shift by 31, and salq would shift by 63.
There are two names for the left shift instruction: SAL and SHL, both have same effect, filling from the right with zeros. The right shift instructions differ in that SAR performs an arithmetic shift (fill with copies of the sign bit), for example -8 >> 1 gives 1100 in four digit representation. The destination operand of a shift operation can be either a register or a memory location. Right shift has two type (arithmetic and logical)
3.5.4 discussion
We see that most of the instructions shown in figure 3.10 can be used for either unsigned or two's complement arithmetic. Only right shifting requires instructions that differentiate between signed versus unsigned data. This is one of the features that makes two's-complement arithmetic the preferred way to implement signed integer arithmetic.
talk about figure 3.11 as example
Figure 3.11 shows an example of a function that performs arithmetic operations and its translation into assembly code. Arguments x, y, and z are initially stored in registers %rdi, %rsi, and %rdx, respectively. the assembly-code instructions correspond closely with the lines of C source code.
3.5.5 Special arithmetic operations
As we saw in Section 2.3, multiplying two 64-bit signed or unsigned integers can yield a product that requires 128 bits to represent. The x86-63 instruction set provides limited suport for operations involving 128-bit numbers. Continueing with the naming convention of word, double word, and quad word, Intel refers to a 16 byte quantity as an oct word.
void remdiv(long x, long y, long *qp, long *rp) {
long q = x/y;
long r = x%y;
*qp = q;
*rp = r;
}
remdiv:
movq %rdx, %r8
movq %rdi, %rax
cqto
idivq %rsi
movq %rax, (%r8)
movq %rdx, (%rcx)
ret
3.6 Control
Machine code provides two basic low-level mechanisms for implementing conditional behavior: it tests data values and then alters either the control flow or the data flow based on the results of these tests.
Data-dependent control flow is the more general and more common approach for implementing conditional behavior. The execution order of a set of machine code instructions can be altered with a jump instruction, indicating that control should pass to some other part of the program, possibly contingent on the result of some test. The compiler must generate instruction sequences that build upon this low-level mechanism to implement the control constructs of C.
%rsp is stack pointer to current stack top
%rip is instruction pointer to current instruction
3.6.1 Condition codes
Machine code provides two basic low-level mechanisms for implementing conditional behavior:
- it tests data values and then alters either the control flow
- the data flow based on the results of these tests
Book talked about data-dependent control flow first because it is more general
Normally, both statements in C and instructions in machine code are executed sequentially, in the order they appear in the program. jump instruction can alter the execution order, indicating that control should pass to some other part of the program, possibly result from some test.
CPU maintains a set of single-bit condition code registers describing attributes of the most recent arithmetic or logical operation. These registers can then be tested to perform conditional branches. These condition codes are the most useful:
CF: Carry flag. The most recent operation generated a carry out of the most significant bit. Used to detect overflow for unsigned operations.
ZF: Zero flag. The most recent operation yielded zero.
SF: Sign flag. The most recent operation yielded a negative value.
OF: Overflow flag. The most recent operation caused a two's complement overflow--either negative or positive.
Rather than reading the condition codes directly, there are three common ways of using the condition codes:
- we can set a single byte to 0 or 1 depending on some combination of the condition codes
- we canconditionally jump to some other part of the program
- we can conditionally transfer data.
In addition to the setting of condition codes by the instructions of Figure 3.10, there are two instruction classes (having 8-, 16-, 32-, and 64-bit forms) that set condition codes without altering any other registers;
compare instruction
cmpq src2, src1
cmpq b, a like computing a-b without setting destination
Test instruction
testq src2, src1
testq b, a like computing a&b without setting destination
3.6.3 Jump Instructions
A jump instruction can cause the execution to switch to a completely new position in the program. These jump destinations are generally indicated in assembly code by a label.
3.6.4 Jump instruction Encodings
For the most part, we will not concern ourselves with the detailed format of machine code. on the other hand, understanding how the targets of jump instructions are encoded will become more important when we study linking in Chapter 7. In addition, it helps when interpreting the output of a disassembler. In assembly code, jump targets are written using symbolic labels. The assembler, and later the linker, generate the proper encodings of the jump targets. there are several different encodings for jumps, but some of the most commonly used ones are PC relative. That is, they encode the difference between the address of the target instruction and the address of the instruction immediately following the jump. These offsets can be encoded using 1, 2, or 4 bytes. A second encoding method is to give an "absolute" address, using 4 bytes to directly specify the target.
- conditional control
- conditional move
The assembler and linker select the appropriate encodings of the jump destinations.
3.6.5 Implementing conditional branches with conditional control
The most general way to translate conditional expressions and statements from C into machine code is to use combinations of conditional and unconditional jumps. For example, Figure 3.16 shows the C code for a function that computes the absolute value of the difference of two numbers . The function also has a side effect of incrementing one of two counters, encoded as global variables It_cnt and ge_cnt. GCC generates the assembly code shown as Figure 3.16c.
3.16b shows goto version in C code of the original code
Assembly implementation typically adheres to the following form, where we use C syntax to describe the control flow:
t = test-expr;
if (!t) {
goto false;
then-statement
goto done;
false:
else-statement;
done:
why conditional data transfers can outperform code based on conditional control transfers?
As we will see in Chapters 4 and 5, processors achieve high performance through pipelining
When the machine encounters a conditional jump (re- ferred to as a “branch”), it cannot determine which way the branch will go until it has evaluated the branch condition. Processors employ sophisticated branch pre- diction logic to try to guess whether or not each jump instruction will be followed. Mispredicting a jump, on the other hand, requires that the processor discard much of the work it has already done on future instructions and then begin filling the pipeline with instructions starting at the correct location. In a typical application, the outcome of the test x < y is highly unpredictable, and so even the most sophisticated branch prediction hardware will guess correctly only around 50% of the time. In addition, the computations performed in each of the two code sequences require only a single clock cycle. As a consequence, the branch misprediction penalty dominates the performance of this function.
As described in class lecture, the CPU is like a boat with full speed. So it's hard for it to turn to different direction. Rather tell it to turn, we could run it until it have to turn
To understand how conditional operations can be implemented via condi- tional data transfers, consider the following general form of conditional expression and assignment:
v = test-expr ? then-expr : else-expr;
for the code based on a conditional move, both the then-expr and the else-expr are evaluated, with the final value choasen based on the evaluation test-expr. This can be described by the following abstract code:
v = then-expr;
ve = else-expr;
t = test-expr;
if (!t) v = ve;
The final statement in this sequence is implemented with a conditional move -- value ve is copied to v only if test condition t does not hold.
at the end, they still use conditional control transfer more.. So conditional data transfer is an alternative
Compilers must take into account the relative performance of wasted computation versus the potential for performance penalty due to branch misprediction. In truth, they do not really have enough information to make this decision reliably; for example, they do not know how well the branches will follow predictable patterns. Our experiments with gcc indicate that it only uses conditional moves when the two expressions can be computed very easily, for example, with single add instructions. In our experience, gcc uses conditional control transfers even in many cases where the cost of branch misprediction would exceed even more complex computations.
3.6.7 loops
C provides several looping
- do-while
- while
- for
No corresponding instructions exist in machine code. Combinations of conditional tests and jumps are used to implement the effect of loops
do while
do
body-statement;
while (test-expr);
while
while (test-expr)
body-statement
First translation method
The second translation method, which we refer to as guarded do, first transforms the code into a do-while loop by using a conditional branch to skip over the loop if the initial test fails.
GCC follows this strategy when compiling with higher levels of optimization, for example, with command-line option -O1. This method can be expressed by the following template for translating from the general while loop form to a do-while loop:
t = test-expr;
if (!t)
goto done;
do
body-statement;
while (test-expr);
done:
for loop
for (init-expr; test-expr; update-expr)
body-statement
The C language standard states (with one exception), that the behavior of such a loop is identical to the following code using a while loop:
init-expr;
while (test-expr) {
body-statement;
update-expr;
}
the program first evaluates the initialization expression init-expr. It enters a loop where it first evaluates the test condition test-expr, exiting if the test fails, then executes the body of the loop body-statement, and finally evaluates the update expression update-expr.
switch statement
Not only do they make the C code more readable, but they also allow an efficient implementation using a data structure called a jump table.
A jump table is an array where entry i is the address of a code segment implementing the action the program should take when the switch index equals i. The code performs an array reference into the jump table using the switch index to determine the target for a jump instruction.
highlighted in picture is the assembly code that referencing a jump table
3.7 procedures
Procedures come in many guises in different programming languages -- functions, methods, subroutines, handlers, and so on
The following will be involve with procedures
- Passing control. The program counter must be set to the starting address of the code for Q upon entry and then set to the instruction in P following the call to Q upon return.
- Passing data. P must be able to provide one or more parameters to Q, and Q must be able to return a value back to P.
- Allocating and deallocating memory. Q may need to allocate space for local variables when it begins and then free that storage before it returns.
if the procedure can be stored on the register, then this procedure call won't be allocated to new spaces,
when an x86 procedure requires storage beyond what it can hold in registers, it allocates space on the stack. (by decreasing sp address with appropriate size)
and when Q finishes, the caller address will be restored on sp and local storage it has allocated can be freed. (increase sp)
3.7.2 control transfer
Passing control from P to Q simply set the program counter (PC) to the starting address of the code for Q.
call Q will record the P address when it is invoked.
The effect of the call is to push the return address 0x400568 onto the stack and to jump to the first instruction in function multstore continues until it hits the ret instruction at address 0x40054d. This instruction pops the value 0x400568 from the stack and jumps to this address, resuming the excution of main just after the call instruction.
As a more detailed example of passing control to and from procedures, Figure 3.27 shows the disassembled code for two functions, top and leaf, as well as the portion of code in function main where top gets called.
stack pointer is a pointer to a value of memory space. When function returns, it dereference the sp to get its value and set that value back to the PC.
3.7.3 data transfer
In addition to passing control to a procedure when called, and then back again when the procedure returns, procedure calls may involve passing data as arguments, and returning from a procedure may also involve returning a value. With x86-64, most of these data passing to and from procedures take place via registers. For example, we have already seen numerous examples of functions where arguments are passed in registers %rdi, %rsi, and others. and where values are returned in register %rax.
When procedure P calls procedure Q, the code for P must first copy the arguments into the proper registers. Similarly, when Q returns back to P, the code for P can access the returned value in register %rax. In this section, we explore these conventions in greater detail.
With x86-64, up to six integral (i.e. integer and pointer) arguments can be passed via registers. The registers are used in a specified order, with the name used used for a register depending on the size of the data type being passed. these are shown in Figure 3.28. Arguments are allocated to these registers according to their
ordering in the argument list. Arguments smaller than 64 bits can be accessed using the appropriate subsection of the 64-bit register. For example, if the first argument is 32 bits, it can be accessed as %edi.
When a function has more than six integral arguments, the other ones are passed on the stack. Assume that procedure P calls procedure Q with n integral arguments, such that n > 6. Then the code for P must allocate a stack frame with enough storage for arguments 7 at the top of the stack. When passing parameters on the stack, all data sizes are rounded up to be multiples of eight. With the arguments in place, the program can then execute a call instruction to transfer control to procedure Q. Procedure Q can access its arguments via registers and possibly from the stack. If Q, in turn, calls some function that has more than six arguments, it can allocate space within its stack frame for these, as is illustrated by the area labeled "Argument build area" in Figure 3.25.
In summary, the procedure will copy the variable on to the stack first and then give the control to the callee
As an example of argument passing, consider the C function proc shown in Figure 3.29(a). This function has eight arguments, including integers with different numbers of bytes(8, 4, 2, and 1), as well as different types of pointers, each of which is 8 bytes.
The assembly code generated for proc is shown in Figure 3.29(b). The first
3.7.4 local storage on the stack
Most of the procedure examples we have seen so far did not require any local storage beyond what could be held in registers. At times, however, local data must be stored in memory.
suppose procedure P calls procedure Q, and Q then executes and returns back to P.
Common cases of this include these:
- There are not enough registers to hold all of the local data.
- The address operator '&' is applied to a local variable, and hence we must be able to generate an address for it.
- Some of the local variables are arrays or structures and hence must be accessed by array or structure references. We will discuss this possibility when we describe how arrays and structures are allocated.
Typically, a procedure allocates space on the stack frame by decrementing the stack pointer. This results in the portion of the stack frame labeled "Local variables" in figure 3.25
As an example of the handling of the address operator, consider the two functions shown in Figure 3.31(a)
The code for caller starts by decrementing the stack pointer by 16; this effectively allocates 16 bytes on the stack. Letting S denote the value of the stack pointer, we can see that the code computes &arg2 as S+8, &arg1 as S. Therefore, local variables arg1 and arg2 are stored within the stack frame at offsets 0 and 8 relative to the stack pointer.
Then when the function returns caller will get arg1 value by reading from (%rsp) and read arg2 from 8(%rsp) increase the pointer address by 8 byte then subtract it from arg1 (stored in rdx)
3.7.5 Local Storage in Registers
In order to make sure callee does not overwrite some register value that the caller planned to use later. x86 adopts a uniform set of conventions for register usage that must be respected by all procedures.
By convention, registers %rbx, %rbp, and %r12–%r15 are classified as callee- saved registers.
callee saved register must be preserved by the callee.
value x and y won't be changed after this procedure call.
recursive call
it is naturally implemented by the stack when we recursively call the function because %rbx will store the data by the callee and the %rax will give the return result. When condition has met, return. If not, it will keep calling itself and store rbx
