程序编码
对于机器级编程来说,两种抽象比较重要,一种是机器级程序的格式和行为,为指令集体系结构(ISA),包括IA32和x86-64.另外一种则是虚拟内存地址,这个在第一章提过两次.
回到代码本身,在程序编译里讲过,一段c程序会经历hello.c到hello.i,hello.s,hello.o再到hello可执行程序.
假设一段c代码code,c,如下
int accum=0;
int sum(int x,int y){
int t=x+y;
accum+=t;
return t;
}
我们用GCC编译器,加上"-S"命令,gcc -01 -S code.c
可以得到汇编文件code.s(这里-01表示使用第一级优化).
汇编代码如下:
sum:
pushl %ebp
movl %esp,%ebp
movl 12(%ebp),%eax
addl 8(%ebp),%eax
addl %eax,accum
popl %ebp
ret
如果使用"-c"命令,即gcc -01 -c code.c
就会产生code.o,是二进制格式的.
我们还可以用反汇编,使用"-d"命令可以把二进制文件变成汇编格式,例如objdump -d code.o
,得到code.s文件,但是还是和上面稍有区别.
sum:
pushl %ebp
movl %esp,%ebp
movl 0xc(%ebp),%eax
addl 0x8(%ebp),%eax
addl %eax,0x0
popl %ebp
ret
如果要产生可执行代码的话,需要一个main函数,例如main.c有以下代码
int main(){
return sum(1,3);
}
那么可以用"-o"命令,即gcc -01 -o pro code.o main.c
来生成一个名字是pro的程序.
当然我们还可以对pro来反汇编,objdump -d pro
得到
sum:
pushl %ebp
movl %esp,%ebp
movl 0xc(%ebp),%eax
addl 0x8(%ebp),%eax
addl %eax,0x804a018
popl %ebp
ret
我们看到accum的地址已经确定了.
数据访问
这基本可以用几张图来表示.
-
数据格式
先说数据格式.首先我们习惯称16位为“字”,而32位则为“双字”,相应的,64位则为“四字”.我们以IA32架构为例,来看一下各个数据格式对应的后缀是什么
比如mov指令,它是一个数据传送的指令,那么movb就代表传送一个字节的数据,movw就代表传送两个字节的数据,而movl就代表传送四个字节的数据.
-
访问信息
接着我们看看如何访问数据.
一个IA32的cpu包含一组8个存储32位值的寄存器.
对于%esp和%ebp寄存器来讲,图中标注了它们分别是栈指针以及帧指针.
其他的%eax常用于作为返回值,而且%eax,%ecx,%edx与%ebx,%edi,%esi的使用惯例也不同,之后会写.
怎么访问数据呢,一般数据保存在寄存器或者存储器中,访问方式是不同的.所以根据访问方式不同会分为,立即数,寄存器以及存储器.
3
图的解释非常清晰了,不同的寻址方式都有,不再赘述.
把一个位置的数据复制到另一个位置是频繁使用的指令,称为数据传送指令.
4
值得一说的是最后两个指令压栈以及出栈.涉及到栈指针%esp的操作.根据惯例,栈是倒过来的,栈顶在底部,所以压栈就是栈指针减4,出栈反之.
5
图上例子压栈指令相当于
subl $4,%esp
movl %eax,(%esp)
很好理解,而出栈要说明的是栈指针%esp加4了,原来的值0x123先赋给%edx再被抛弃了.相当于以下指令
movl(%esp),%edx
addl $4,%esp
在c语言中,指针就是地址
int exchange(int *xp,int y){
int x=*xp;
*xp=y;
return x;
}
xp在%ebp+8,y在%ebp+12,抛开栈的建立与完成,其汇编代码为
movl 8(%ebp), %edx
movl (%edx), %eax
movl 12(%ebp), %ecx
movl %ecx, (%edx)</pre>
算术与逻辑操作
6值得一讲的是leal这个指令,称为加载有效地址.比如对于
leal 4(%edx,%edx,4),%eax
这条指令来讲,我们假设%edx寄存器的值为x的话,那么这条指令的作用就是将 4 + x + 4x = 5x + 4赋给%eax寄存器。它和mov指令的区别就在于,假设是movl 4(%edx,%edx,4),%eax
这个指令,它的作用是将内存地址为5x+4的内存区域的值赋给%eax寄存器,而leal指令只是将5x+4这个地址赋给目的操作数%eax而已,它并不对存储器进行引用的值的计算.7
注意上图中%edx,%eax都是默认加载的.
来看个小例子
int arith(int x, int y , int z){
int t1 = x+y;
int t2 = z*48;
int t3 = t1&0xFFFF;
int t4 = t2*t3;
return t4;
}
x在%ebp+8,y在%ebp+12,z在%ebp+16(%ebp+4的地方储存返回值的).同样不考虑栈的建立与完成,那么汇编代码为
movl 16(%ebp), %eax
leal (%eax,%eax,2), %edx
sall $4, %edx
movl 12(%ebp), %eax
addl 8(%ebp), %eax
andl $65535, %eax
imull %edx, %eax</pre>
注意到48z是拆分成先乘以3,再左移4位的操作的.
控制
-
条件码
四种常用的条件码,它们的名字与作用分别如下所述。
CF:进位标志寄存器,它记录无符号操作的溢出,当溢出时会被设为1
ZF:零标志寄存器,当计算结果为0时将会被设为1
SF:符号标志寄存器,当计算结果为负数时会被设为1
OF:溢出标志寄存器,当计算结果导致了补码溢出时,会被设为1
leal指令不会改变任何条件码,除他之外前面的指令都会改变条件码.还有两种指令也会改变条件码但不会影响任何其他寄存器,即CMP和TEST.
test指令用来检测是负数,正数还是零.
我们可以通过一些指令访问条件码
9
一条SET指令的目的操作数是8个单字节寄存器元素之一,或是存储一个字节的存储器位置,将这个字节设置成0或1.而如果想得到32位的结果,显然我们要对最高的24位清零.以
a<b
为例,a在%edx,b在%eax.
cmpl %eax,%edx
setl %al
movzbl %al,%eax
其中movzbl指令就是用来清零%eax的三个高位字节的. '
跳转指令显然是对条件码的主要应用.跳转会导致切换到程序中一个全新的位置,位置一般用标号指明.
jmp是无条件跳转,可以是直接跳转jmp L1
,也可以是间接跳转jmp *%eax
或者jmp *(%eax)
.
带条件的指令如下:
跳转指令是基于PC的偏移量寻址的.举个例子
jle L2
.L5
movl %edx,%eax
sarl %eax
subl %eax,%edx
leal (%edx,%edx,2),%edx
testl %edx,%edx
jg .L5
.L2
movl %edx,%eax
汇编器产生的.o
格式反汇编如下
8:7e 0d jle 17<silly+0x17>
a:89 d0 movl %edx,%eax
c:d1 f8 sarl %eax
e:29 c2 subl %eax,%edx
10:8d 14 52 leal (%edx,%edx,2),%edx
13:85 d2 testl %edx,%edx
15:7f f3 jg a<silly+0xa>
17:89 d0 movl %edx,%eax
看到跳转是基于偏移寻址的,第一个跳转左边第二个代码是0d,下一行的地址是a,加起来刚好是0x17,即跳转目标的地址.而第二个跳转左边第二个值是f3,下一行的地址是17,补码相加是0xa,即跳转目标的地址.
-
翻转条件分支
也就是if else语句的表达
int min(int a,int b){
if( a < b ){
return a;
}else{
return b;
}
}
汇编代码如下:
min:
pushl %ebp
movl %esp, %ebp
movl 8(%ebp), %edx //a
movl 12(%ebp), %eax //b
cmpl %edx, %eax
jle .L2
movl %edx, %eax
.L2:
popl %ebp
ret
代码很直接,不赘述
-
do-while循环
int fact(int n){
int result=1;
do{
result*=n;
n=n-1;
}while(n>1);
return result;
}
n在%ebp+8,对应汇编代码
movl 8(%ebp),%edx
movl $1,%eax
.L2
imull %edx,%eax
subl $1,%edx
cmpl $1,%edx
jg .L2
-
while循环
int fact(int n){
int result=1;
while(n>1){
result*=n;
n=n-1;
}
return result;
}
对于while循环,一般先转换成do-while循环.
int fact(int n){
int result=1;
if(n<=1)
goto done;
loop:
result*=n;
n=n-1;
if(n>1)
goto loop;
done:
return result;
}
汇编代码为:
movl 8(%ebp),%edx
movl $1,%eax
cmp $1,%edx
jle .L7
.L10
imull %edx,%eax
subl $1,%edx
cmpl $1,%edx
jg .L10
.L7
可以看到和do-while基本差不多,多做了刚开始的判断.
-
for循环
for循环同样是转化成do-while模式的
int fact(int n){
int i;
int result=1;
for(i=2;i<=n;i++)
result*=i;
return result;
}
do-while循环模式
int fact(int n){
int i;
int result=1;
if(!(i<=n)) //n<=1
goto done;
loop:
result*=i;
i++;
if(i<=n)
goto loop;
done:
return result;
}
汇编代码为
movl 8(%ebp),%ecx
movl $2,%edx
movl $1,%eax
cmpl $1,%ecx
jle .L7
.L10
imull %edx,%eax
addl $1,%edx
cmpl %edx,%ecx
jge .L10
.L7
-
条件传送指令
说白了是三目运算符那种
int fact(int x,int y){
return x<y?y-x:x-y;
}
使用条件赋值实现
movl 8(%ebp),%ecx //x
movl 12(%ebp),%edx //y
movl %edx,%ebx
subl %ecx,%ebx
movl %ecx,%eax
subl %edx,%eax
cmpl %edx,%ecx
cmovl %ebx,%eax
cmovl是一个替换的条件传送指令
意思是将S值复制到R中.
然而有时候会产生一些副作用
int cread(int *xp){
return (xp?*xp:0);
}
汇编为
movl $0,%eax
test1 %edx,%edx
cmovne (%edx),%eax
这个实现是非法的,好好琢磨
-
switch 语句
switch语句是使用跳跃表实现的,把要跳转的地址都存在一个数组里.
int switch(int x,int n){
int result=x;
switch(n){
case 100:
result*=13;
break;
case 102:
result+=10;
case 103:
result+=11
break;
case 104:
case 106:
result*=result;
break;
default:
result=0;
}
return result;
}
首先汇编的注释,主要是跳跃表的数组
.L7:
.long .L3 case 100:
.long .L2 case 101:
.long .L4 case 102:
.long .L5 case 103:
.long .L6 case 104:
.long .L2 case 105:
.long .L6 case 106:
汇编代码
movl 8(%ebp),%edx
movl 12(%ebp),%eax
subl $100,%eax
cmpl $6,%eax
ja .L2
jmp *.L7(,%eax,4)
.L2:
movl $0,%eax
jmp .L8
.L5:
movl %edx,%eax
jmp .L9
.L3:
leal (%edx,%ed,2),%eax
leal (%edx,%ed,4),%eax
jmp .L8
.L4:
leal 10(%edx),%eax
.L9:
addl $11,%eax
jmp .L8
.L6:
movl %edx,%eax
imull %edx,%eax
.L8:
过程
一个过程调用包括将数据和控制从代码的一部分传递到另一部分.它必须在进入的时候为过程的局部变量分配空间,并在退出时释放这些空间.数据传递,局部变量的分配和释放通过操纵程序栈来实现.
-
针栈
栈帧其实可以认为是程序栈的一段,而程序栈又是存储器的一段,因此栈帧说到底还是存储器的一段.这两个端点其实就是两个地址,一个标识着起始地址,一个标识着结束地址,而这两个地址,则分别存储在固定的寄存器当中,即起始地址存在%ebp寄存器当中,结束地址存在%esp寄存器当中.起始地址和结束地址还有另外的名字,起始地址通常称为帧指针,结束地址通常称为栈指针(也就是栈顶的地址)。因此,我们就把过程的存储器内存使用区域称为栈帧.
这个图基本上已经包括了程序栈的构成,它由一系列栈帧构成,这些栈帧每一个都对应一个过程,而且每一个帧指针+4的位置都存储着函数的返回地址,每一个帧指针指向的存储器位置当中都备份着调用者的帧指针.每一个栈帧都建立在调用者的下方(也就是地址递减的方向),当被调用者执行完毕时,这一段栈帧会被释放。还有一点很重要的是,%ebp和%esp的值指示着栈帧的两端,而栈指针会在运行时移动,所以大部分时候,在访问存储器的时候会基于帧指针访问,因为在一直移动的栈指针无法根据偏移量准确的定位一个存储器位置.
-
过程的实现
总的来说,过程实现当中,参数传递以及局部变量内存的分配和释放都是通过以上介绍的栈帧来实现的,大部分情况下,我们认为过程调用当中做了以下几个操作。
1、备份原来的帧指针,调整当前的帧指针到栈指针的位置,这个过程就是我们经常看到的如下两句汇编代码做的事情。
pushl %ebp
movl %esp, %ebp</pre>
2、建立起来的栈帧就是为被调用者准备的,当被调用者使用栈帧时,需要给临时变量分配预留内存,这一步一般是经过下面这样的汇编代码处理的。
subl $16,%ebp
3、备份被调用者保存的寄存器当中的值,如果有值的话,备份的方式就是压入栈顶。因此会采用如下的汇编代码处理。
pushl %ebx
4、使用建立好的栈帧,比如读取和写入,一般使用mov,push以及pop指令等等。
5、恢复被调用者寄存器当中的值,这一过程其实是从栈帧中将备份的值再恢复到寄存器,不过此时这些值可能已经不在栈顶了。因此在恢复时,大多数会使用pop指令,但也并非一定如此。
6、释放被调用者的栈帧,释放就意味着将栈指针加大,而具体的做法一般是直接将栈指针指向帧指针,因此会采用类似下面的汇编代码处理(也可能是addl)。
movl %ebo,%esp
7、恢复调用者的栈帧,恢复其实就是调整栈帧两端,使得当前栈帧的区域又回到了原始的位置。因为栈指针已经在第六步调整好了,因此此时只需要将备份的原帧指针弹出到%ebp即可。类似的汇编代码如下。
popl %ebp
8、弹出返回地址,跳出当前过程,继续执行调用者的代码。此时会将栈顶的返回地址弹出到PC,然后程序将按照弹出的返回地址继续执行。这个过程一般使用ret指令完成。
-
转移控制
支持过程调用与返回的指令一般是三个
call指令:它一共做两件事,第一件是将返回地址(也就是call指令执行时PC的值)压入栈顶,第二件是将程序跳转到当前调用的方法的起始地址。第一件事是为了为过程的返回做准备,而第二件事则是真正的指令跳转。
leave指令:它也是一共做两件事,第一件是将栈指针指向帧指针,第二件是弹出备份的原帧指针到%ebp。第一件事是为了释放当前栈帧,第二件事是为了恢复调用者的栈帧。
ret指令:它同样也是做两件事,第一件是将栈顶的返回地址弹出到PC,第二件事则是按照PC此时指示的指令地址继续执行程序。这两件事其实也可以认为是一件事,因为第二件事是系统自己保证的,系统总是按照PC的指令地址执行程序。
-
寄存器使用惯例
使用寄存器会有一些惯例,我们假设这里在过程P中调用了过程Q,P是调用者,Q是被调用者.
%eax、%edx、%ecx:这三个寄存器被称为调用者保存寄存器。意思就是说,这三个寄存器由调用者P来保存,而对于Q来说,Q可以随便使用,用完了就不用再管了.
%ebx、%esi、%edi:这三个寄存器被称为被调用者保存寄存器。同样的,这里是指这三个寄存器由被调用者Q来保存,换句话说,Q可以使用这三个寄存器,但是如果里面有P的变量值,Q必须保证使用完以后将这三个寄存器恢复到原来的值,这里的备份,其实就是上面那8个步骤中第3个步骤做的事情.
另外%ebp和%esp都是要保存的.
-
过程示例
int swap_add(int a,int b){
register int c = a + b;
return c;
}
int main(){
int a = 100;
int b = 101;
int c = swap_add(a,b);
return c;
}
汇编代码为:
main:
pushl %ebp
movl %esp,%ebp
subl $24,%esp
movl $100,-4(%ebp)
movl $101,-8(%ebp)
movl -8(%ebp),%eax
movl %eax,4(%esp)
movl -4(%ebp),%eax
movl %eax,(%esp)
call add
leave
ret
swap_add:
pushl %ebp
movl %esp,%ebp
pushl %ebx
movl 12(%ebp),%eax
movl 8(%ebp),%edx
leal (%edx,%eax),%ebx
movl %ebx,%eax
popl %ebx
popl %ebp
ret
13
图中可以看到,两个参数先是通过帧指针保存,随后保存到栈指针上面.call之后跳到返回地址,接着push%ebx,两个参数自然变到+12与+8的位置.如果我们用-01优化的话,主函数那而可以直接把参数写入到相对于栈指针的寄存器.
main:
pushl %ebp
movl %esp,%ebp
subl $24,%esp
movl $100,4(%esp)
movl $101,(%esp)
call add
leave
ret
另外之所以分配未使用的空间,是为了数据对齐.
-
递归调用
int rfact(int n){
int result;
if(n<=1){
result = 1;
}else{
result = n * rfact(n-1);
}
return result;
}
不去看主函数的调用,汇编代码为:
rfact:
pushl %ebp
movl %esp,%ebp
pushl %ebx
subl $20,%esp
movl 8(%ebp),%ebx
movl $1,%eax
cmpl $1,%ebx
jle .L3
leal -1(%ebx),%eax
movl %eax,(%esp)
call rfact
imull %ebx,%eax
.L3:
addl $20,%esp
popl %ebx
popl %ebp
ret
14
数组
定义一个数组T N[L]
这当中T表示数据类型,N是变量名称,L是数组长度。这样的声明会做两件事,首先是在内存当中开辟一个长为L*length(T)的内存空间(其中length(T)是指数据类型的字节长度),然后将这块内存空间的起始地址赋给变量N.
看看以下这些声明
char A[12];
char *B[8];
double C[6];
double *D[5];
15
-
指针运算
可以用一张表来表示关系
-
嵌套数组
这个就是多重数组,同样很简单,一张图表示
上图表示一个5行3列的数组
考虑将一个A[i][j]复制到寄存器%eax中,那么显然元素地址应该计算为
Xa+4(3i+j)
汇编为
movl 12(%ebp),%eax
leal (%eax,%eax,2),%eax
movl 16(%ebp),%edx
sall $2,%edx
addl 8(%ebp),%edx
movl (%edx,%eax,4),%eax
使用移位,加法和伸缩的组合来避免过大的开销.
-
定长和变长数组
如果在编译时数组的长度确定,我们就称为定长数组,反之则称为变长数组.
先看一个定长数组的例子
int main(){
int a[5];
int i,sum;
for(i = 0 ; i < 5; i++){
a[i] = i * 3;
}
for(i = 0 ; i < 5; i++){
sum += a[i];
}
return sum;
}
汇编代码
main:
pushl %ebp
movl %esp, %ebp//到此准备好栈帧
subl $32, %esp//分配32个字节的空间
leal -20(%ebp), %edx//将帧指针减去20赋给%edx寄存器
movl $0, %eax//将%eax设置为0,这里的%eax寄存器是重点
.L2:
movl %eax, (%edx)//将0放入帧指针减去20的位置
addl $3, %eax//第一次循环时,%eax为3,对于i来说,%eax=(i+1)*3。
addl $4, %edx//将%edx加上4,第一次循环%edx指向帧指针-16的位置
cmpl $15, %eax//比较%eax和15
jne .L2//如果不相等的话就回到L2
movl -20(%ebp), %eax//下面这五句指令,很明显从-20到-4。
addl -16(%ebp), %eax
addl -12(%ebp), %eax
addl -8(%ebp), %eax
addl -4(%ebp), %eax
leave
ret
开始将%ebp减去20是为了依次给数组赋值。这里编译器用了优化技巧.。那就是编译器发现了a[i+1] = a[i] + 3的规律,因此使用加法(将%eax不断加3)代替了i3的乘法操作,另外也使用了加法(即地址不断加4,而不使用起始地址加上索引乘以4的方式)代替了数组元素地址计算过程中的乘法操作。而循环条件当中的i<5,也变成了3i<15,而3*i又等于a[i],因此当整个数组当中循环的索引i,满足a[i+1]=15(注意,在循环内的时候,%eax一直储存着a[i+1]的值,除了刚开始的0)的时候,说明循环该结束了,也就是coml和jne指令所做的事.
那如果是变长数组呢,似乎很难算出类似15这样的值
int fact(int n,intA[n][n],int i,int j){
return A[i][j];
}
汇编为
movl 8(%ebp),%eax
sall $2,%eax
movl %eax,%edx
imull 16(%ebp),%edx
movl 20(%ebp),%eax
sall $2,%eax
addl 12(%ebp),%eax
movl (%eax,%edx),%eax
注意这里相对于定长数组不同的是一定得用乘法指令来对i伸展n倍,而不能用移位和加法.
编译器常常可以利用访问的规律性来进行优化,例如计算两个nxn矩阵A和B的乘积元素i,k.产生的代码如下.首先注册Arow在%esi,Bptr在%ecx,j在%edx,result在%ebx,4*n在%edi.那么
.L30
movl (%ecx),%eax
imull (%esi,%edx,4),%eax
addl %eax,%ebx
addl $1,%edx
addl %edi,%ecx
cmpl %edx,8(%ebp)
jg .L30
-
异质结构与数据对齐
异质结构是指不同数据类型的数组组合,比如C语言当中的结构(struct)与联合(union).
struct {
int a;
int b;
char c;
} mystruct;
int main(){
printf("%d\n",sizeof mystruct);
}
这段代码输出多少呢,反正不是9,在我的机器上输出12,这里涉及到数据对齐.
另外联合会复用内存空间,以节省内存.
union {
int a;
int b;
char c;
} myunion;
int main(){
printf("%d\n",sizeof myunion);
}
这段程序输出的结果是4,这是因为a、b、c会共用4个字节,之间没有偏移量.
对齐的大致规则,一般会依据数据类型的长度来对齐(比如int为4位对齐,double为8位对齐等等),但最低为2。不过这些都不是绝对的,比如double也可能会依据4位对齐,因此具体的对齐规则还是需要根据硬件设施和操作系统决定.
可以通过.align 4
指令保证后面的数据起始地址都是4的倍数,也就是声明4字节对齐.
缓冲区溢出
C对于数组是不进行任何边界检查的,而且局部变量和状态信息都会放在栈中.
一种常见的状态破坏就是缓冲区溢出.
可以预想的结果,如果数组的元素不止这几个,溢出后可能破坏%ebx的值,破坏%ebp的值,甚至破坏返回地址.
而针对这个,常常会有蠕虫攻击.应对方式大致会有三种
-
栈随机化
就是使得栈的位置在程序每次运行时候都有变化.在程序开始的时候,在栈上分配一段0~n字节的随记大小的空间.
在linux系统中.栈随机化是地址空间布局随机化(ASLR)的一种,它使得包括代码,库代码,栈,全局变量和堆数据都加载到不同的位置.
然而通过在攻击代码前插入一段连续的nop,然后枚举起始地址可以无效随机化,称为空操作雪橇(nop-sled).
-
栈破坏检测
在产生的代码中加入一段金丝雀值,在恢复寄存器前看看这个金丝雀值有没有被改变,如果改变了程序就中止.
加入的不同的汇编代码如下
movl %gs:20,%eax
movl %eax,-8(%ebp)
xorl eax,%eax
和
movl -8(%ebp),%eax
xorl %gs:20,%eax
je .L19
call __stack_chk_fail
指令参数%gs:20
表示金丝雀值用段寻址从存储器中读入.
-
限制可执行代码区域
引入"NX"位,把读和执行访问模式分开,限制哪部分存储器才可以存储可执行代码,就消除了攻击者向系统中插入可执行代码的能力.
X86-64
64位机器不细讲,和32位没有多大区别.
主要的不同是,指令后缀都是q,也就是四字.其次没有帧指针和栈指针,因为寄存器数量多了许多,基本上直接用寄存器就可以,不用栈啊帧啊搞来高去存来存去.
网友评论