第三章 程序的转换与机器级表示 程序转换概述 IA-32 /x86-64指令系统 C语言程序的机器级表示 复杂数据类型的分配和访问 越界访问和缓冲区溢出、x86-64架构

程序的转换与机器级表示 主要教学目标 了解高级语言与汇编语言、汇编语言与机器语言之间的关系 掌握有关指令格式、操作数类型、寻址方式、操作类型等内容 了解高级语言源程序中的语句与机器级代码之间的对应关系 了解复杂数据类型（数组、结构等）的机器级实现 主要教学内容 介绍C语言程序与IA-32机器级指令之间的对应关系。 主要包括：程序转换概述、IA-32指令系统、C语言中控制语 句和过程调用等机器级实现、复杂数据类型（数组、结构等） 的机器级实现等。 本章所用的机器级表示主要以汇编语言形式表示为主。

程序的机器级表示 分以下五个部分介绍 第一讲：程序转换概述 机器指令和汇编指令 机器级程序员感觉到的属性和功能特性 高级语言程序转换为机器代码的过程 第二讲：IA-32 /x86-64指令系统 第三讲： C语言程序的机器级表示 过程调用的机器级表示 选择语句的机器级表示 循环结构的机器级表示 第四讲：复杂数据类型的分配和访问 数组的分配和访问 结构体数据的分配和访问 联合体数据的分配和访问 数据的对齐 第五讲：越界访问和缓冲区溢出 从高级语言程序出发，用其对应的机器级代码以及内存（栈）中信息的变化来说明底层实现 围绕C语言中的语句和复杂数据类型，解释其在底层机器级的实现方法

过程调用的机器级表示 以下过程（函数）调用对应的机器级代码是什么？ 如何将t1(125)、t2(80)分别传递给add中的形式参数x、y add函数执行的结果如何返回给caller? int add ( int x, int y ) { return x+y; } int main ( ) { int t1 = 125; int t2 = 80; int sum = add (t1, t2); return sum; main： add： 存放参数 取出参数 调出add执行 执行 存返回结果 返回main add main

过程调用的机器级表示 过程调用的执行步骤(P为调用者，Q为被调用者) main： add： 何为现场？ 存放参数 取出参数 存放参数 取出参数 调出add执行 执行 存返回结果 返回main 何为现场？ 通用寄存器的内容！ 为何要保存现场？ 因为所有过程共享一套通用寄存器 想象：妈妈和你做菜时共用一套盘 子的情况。 过程调用的执行步骤(P为调用者，Q为被调用者) （1）P将入口参数（实参）放到Q能访问到的地方； （2）P保存返回地址，然后将控制转移到Q； （3）Q保存P的现场，并为自己的非静态局部变量分配空间； （4）执行Q的过程体（函数体）； （5）Q恢复P的现场，释放局部变量空间； （6）Q取出返回地址，将控制转移到P。 P过程 CALL指令 准备阶段 Q过程 处理阶段 结束阶段 RET指令

过程调用的机器级表示 IA-32的寄存器使用约定 调用者保存寄存器：EAX、EDX、ECX 当过程P调用过程Q时，Q可以直接使用这三个寄存器，不用将它们的值保存到栈中。如果P在从Q返回后还要用这三个寄存器的话，P应在转到Q之前先保存，并在从Q返回后先恢复它们的值再使用。 被调用者保存寄存器：EBX、ESI、EDI Q必须先将它们的值保存到栈中再使用它们，并在返回P之前恢复它们的值。 EBP和ESP分别是帧指针寄存器和栈指针寄存器，分别用来指向当前栈帧的底部和顶部。 问题：为减少准备和结束阶段的开销，每个过程应先使用哪些寄存器？ EAX、ECX、EDX！

过程调用的机器级表示 过程调用过程中栈和栈帧的变化 (Q为被调用过程) ① ② ⑤ ③ Q(参数1，…，参数n);

一个简单的过程调用例子 caller 帧底 -4 -8 -12 -16 ESP+4 -20 int add ( int x, int y ) { return x+y; } int caller ( ) { int t1 = 125; int t2 = 80; int sum = add (t1, t2); return sum; 一个简单的过程调用例子 caller 帧底 add caller -4 -8 -12 -16 -20 caller： pushl %ebp movl %esp, %ebp subl $24, %esp movl $125, -12(%ebp) movl $80, -8(%ebp) movl -8(%ebp), %eax movl %eax, 4(%esp) movl -12(%ebp), %eax movl %eax, (%esp) call add movl %eax, -4(%ebp) movl -4(%ebp), %eax leave ret ESP+4 准备阶段 分配局部变量 准备入口参数 返回参数总在EAX中 准备返回参数 add函数开始是什么？ pushl %ebp movl %esp, %ebp 结束阶段 movl %ebp, %esp popl %ebp

可执行文件的存储器映像 内核区 栈区 共享库的代码 堆区 程序(段)头表描述如何映射 brk 从可执行文件装入 Kernel virtual memory Memory-mapped region for shared libraries Run-time heap (created by malloc) User stack (created at runtime) Unused Read/write segment (.data, .bss) Read-only segment (.init, .text, .rodata) 内核区 0xC00000000 ELF header Segment header table .text section .data section .bss section .symtab .debug .rodata section .line .init section .strtab 栈区 %esp (栈顶) 共享库的代码 brk 堆区 从可执行文件装入 0x08048000

过程调用参数传递举例 按地址传递参数 按值传递参数 执行结果？为什么？ 程序二 程序一 #include <stdio.h> main ( ) { int a=15, b=22; printf (“a=%d\tb=%d\n”, a, b); swap (&a, &b); } swap (int *x, int *y ) int t=*x; *x=*y; *y=t; 程序二 #include <stdio.h> main ( ) { int a=15, b=22; printf (“a=%d\tb=%d\n”, a, b); swap (a, b); } swap (int x, int y ) int t=x; x=y; y=t; 按地址传递参数 按值传递参数 执行结果？为什么？ 程序一的输出： a=15 b=22 a=22 b=15 程序二的输出： a=15 b=22

过程调用参数传递举例 局部变量a和b确实交换 22 15 EBP+12 EBP+8 返回地址 EBP EBP在main中的值 EBX在main中的值 R[ecx]←M[&a]=15 局部变量a和b确实交换 R[ebx]←M[&b]=22 M[&a] ← R[ebx] =22 M[&b] ← R[ecx] = 15

过程调用参数传递举例 EBP+12 15 EBP+8 22 返回地址 EBP EBP在main中的值 局部变量a和b没有交换，交换的仅是入口参数！ R[edx]←15 R[eax]←22 M[R[ebp]+8] ← R[eax] =22 M[R[ebp]+12] ← R[edx] =15

入口参数的位置 每个过程开始两条指令总是 pushl %ebp movl %esp, %ebp 在IA-32中，若栈中存放的参数的类型是char、unsigned char或short、unsigned short，也都分配4个字节。 因而，在被调用函数的执行过程中，可以使用R[ebp]+8、R[ebp]+12、R[ebp]+16、…… 作为有效地址来访问函数的入口参数。 movl ……. 准备入口参数 call ……. EBP+16 入口参数3 EBP+12 入口参数2 入口参数1 EBP+8 返回地址 EBP EBP在main中的值

过程调用举例 &y: 300 1 void test ( int x, int *ptr ) 2 { P &a: 2 { 3 if ( x>0 && *ptr>0 ) 4 *ptr+=x; 5 } 6 7 void caller (int a, int y ) 8 { 9 int x = a>0 ? a : a+100; 10 test (x, &y)； 11 } 调用caller的过程为P，P中给出形参a和y的 实参分别是100和200，画出相应栈帧中的状态，并回答下列问题。 （1）test的形参是按值传递还是按地址传递？test的形参ptr对应的实参是一个 什么类型的值？ （2）test中被改变的*ptr的结果如何返回给它的调用过程caller？ （3）caller中被改变的y的结果能否返回给过程P？为什么？ test caller P caller 100 200 caller执行过程中，在进入test之前一刻栈中的状态如何？ 则函数返回400 若return x+y； 进入test并生成其栈帧后，栈中状态如何？ 前者按值、后者按地址。一定是一个地址 第10行执行后，P帧中200变成300，test退帧后，caller中通过y引用该值300 第11行执行后caller退帧并返回P，因P中无变量与之对应，故无法引用该值300

递归过程调用举例 int nn_sum ( int n) { nn_sum(n) int result; if (n<=0 ) P int nn_sum ( int n) { int result; if (n<=0 ) result=0; else result=n+nn_sum(n-1); return result； } P Sum(n) Sum(n-1) n R[ebx]←n R[eax]←0 if (n≤0）转L2 R[eax]←n-1 每次递归调用都会增加一个栈帧，所以空间开销很大。 R[eax] ← 0+1+2+…+(n-1)+n

过程调用的机器级表示 递归函数nn_sum的执行流程 过程功能由过程体实现，为支持过程调用，每个过程包含准备阶段和结束阶段。因而每增加一次过程调用，就要增加许多条包含在准备阶段和结束阶段的额外指令，它们对程序性能影响很大，应尽量避免不必要的过程调用，特别是递归调用。

过程调用举例 例：应始终返回d[0]中的3.14，但并非如此。Why? 不同系统上执行结果可能不同 double fun(int i) { volatile double d[1] = {3.14}; volatile long int a[2]; a[i] = 1073741824; /* Possibly out of bounds */ return d[0]; } fun(0)  3.14 fun(1)  3.14 fun(2)  3.1399998664856 fun(3)  2.00000061035156 fun(4)  3.14, 然后存储保护错 为何每次返回不一样？为什么会引起保护错？栈帧中的状态如何？ 不同系统上执行结果可能不同

double fun(int i) { volatile double d[1] = {3.14}; volatile long int a[2]; a[i] = 1073741824; return d[0]; } EBP EBP的旧值 ESP a[i]=1073741824; 0x40000000 =230 =1073741824 return d[0];

选择结构的机器级表示 if ~ else语句的机器级表示 if (cond_expr) then_statement else else_statement

If-else语句举例 p1和p2对应实参的存储地址分别为R[ebp]+8、R[ebp]+12，EBP指向当前栈帧底部，结果存放在EAX。 int get_cont( int *p1, int *p2 ) { if ( p1 > p2 ) return *p2; else return *p1; } p1和p2对应实参的存储地址分别为R[ebp]+8、R[ebp]+12，EBP指向当前栈帧底部，结果存放在EAX。

switch-case语句举例 int sw_test(int a, int b, int c) R[eax]=a-10=i { int result; switch(a) { case 15: c=b&0x0f; case 10: result=c+50; break; case 12: case 17: result=b+50; case 14: result=b default: result=a; } return result; R[eax]=a-10=i if (a-10)>7 转 L5 转.L8+4*i 处的地址 跳转表在目标文件的只读节中，按4字节边界对齐。 10 11 12 13 14 15 16 17 a=

循环结构的机器级表示 红色处为条件转移指令！ do~while循环的机器级表示 do loop_body_statement while (cond_expr); 红色处为条件转移指令！ loop： loop_body_statement c=cond_expr; if (c) goto loop; for循环的机器级表示 for (begin_expr; cond_expr; update_expr) loop_body_statement while循环的机器级表示 begin_expr; c=cond_expr; if (!c) goto done; loop： loop_body_statement update_expr; if (c) goto loop; done： while (cond_expr) loop_body_statement c=cond_expr; if (!c) goto done; loop： loop_body_statement if (c) goto loop; done：

循环结构与递归的比较 递归函数nn_sum仅为说明原理，实际上可直接用公式，为说明循环的机器级表示，这里用循环实现。 movl 8(%ebp), %ecx movl $0, %eax movl $1, %edx cmpl %ecx, %edx jg .L2 .L1: addl %edx, %eax addl $1, %edx jle .L1 .L2 局部变量 i 和 result 被分别分配在EDX和EAX中。 通常复杂局部变量被分配在栈中，而这里都是简单变量 int nn_sum ( int n) { int i; int result=0; for (i=1; i <=n; i++) result+=i; return result； } SKIP 过程体中没用到被调用过程保存寄存器。因而，该过程栈帧中仅需保留EBP，即其栈帧仅占用4字节空间，而递归方式则占用了(16n+12)字节栈空间，多用了(16n+8)字节，每次递归调用都要执行16条指令，一共多了n次过程调用，因而，递归方式比循环方式至少多执行了16n条指令。由此可以看出，为了提高程序的性能，若能用非递归方式执行则最好用非递归方式。

递归过程调用举例 时间开销：每次递归执行16条指令，共16n条指令 空间开销：一次调用增加16B栈帧，共16n+12 P的栈帧至少占12B int nn_sum ( int n) { int result; if (n<=0 ) result=0; else result=n+nn_sum(n-1); return result； } P的栈帧至少占12B P Sum(n) Sum(n-1) n BACK 时间开销：每次递归执行16条指令，共16n条指令 空间开销：一次调用增加16B栈帧，共16n+12

逆向工程举例 ① 处为i=0，② 处为i≠32，③ 处为i++。 movl 8(%ebp), %ebx movl $0, %eax movl $0, %ecx .L12: leal (%eax,%eax), %edx movl %ebx, %eax andl $1, %eax orl %edx, %eax shrl %ebx addl $1, %ecx cmpl $32, %ecx jne .L12 int function_test( unsigned x) { int result=0; int i； for ( ① ; ② ; ③ ) { ④ ； } return result; ① 处为i=0，② 处为i≠32，③ 处为i++。 入口参数 x 在EBX中，返回参数 result 在EAX中。LEA实现“2*result”，即：将result左移一位；第6和第7条指令则实现“x&0x01”；第8条指令实现“result=(result<<1) | (x & 0x01)”，第9条指令实现“x>>=1”。综上所述，④ 处的C语言语句是“result=(result<<1) | (x & 0x01); x>>=1;”。