glibc--strcpy源码分析
strcpy是各大计算机考试和面试中几乎不可少的考点。我们平时看到最多的是下面这个版本（不考虑参数检查等操作）
char * strcpy (char * dst, const char * src)
{
char * cp = dst;
while( *cp++ = *src++ )
; /* Copy src over dst */
return( dst );
}不得不说的是，诸如*cp++ = *src++之类的代码太泛滥了，我甚至听有的人说这是老鸟才能写出的代码，⊙﹏⊙b汗！
但我们要明白的是代码最终是要机器来运行的，这样的语句翻译成机器码后，机器没有得到任何好处 -- 具体原因下文会分析... ...
glibc中的strcpy的效率要高于上面的代码，代码如下
#include <stddef.h>
#include <string.h>
#include <memcopy.h>
#include <bp-checks.h>
#undef strcpy
/* Copy SRC to DEST. */
char *
strcpy (dest, src)
char *dest;
const char *src;
{
char c;
char *__unbounded s = (char *__unbounded) CHECK_BOUNDS_LOW (src);
const ptrdiff_t off = CHECK_BOUNDS_LOW (dest) - s - 1;
size_t n;
do
{
c = *s++;
s[off] = c;
}
while (c != '\0');
n = s - src;
(void) CHECK_BOUNDS_HIGH (src + n);
(void) CHECK_BOUNDS_HIGH (dest + n);
return dest;
}
libc_hidden_builtin_def (strcpy)
/* Int 5 is the "bound range" exception also raised by the "bound"
instruction. */
# define BOUNDS_VIOLATED int $5
/* Verify that pointer's value >= low. Return pointer value. */
# define CHECK_BOUNDS_LOW(ARG) \
(((__ptrvalue (ARG) < __ptrlow (ARG)) && BOUNDS_VIOLATED), \
__ptrvalue (ARG))
/* Verify that pointer's value < high. Return pointer value. */
# define CHECK_BOUNDS_HIGH(ARG) \
(((__ptrvalue (ARG) > __ptrhigh (ARG)) && BOUNDS_VIOLATED), \
__ptrvalue (ARG))
不要被以上的代码给吓了，其实很多已经不用了。首先我们了解下bounded pointer（只是了解下）
GCC支持bounded类型指针（bounded指针用__bounded关键字标出，若默认为bounded指针，则普通指针用__unbounded标出），这种指针占用3个指针的空间，在第一个空间里存储原指针的值，第二个空间里存储下限值，第三个空间里存储上限值。__ptrvalue、__ptrlow、__ptrhigh分别返回这3个值，有了3个值以后，内存越界错误便很容易查出来了。并且要定义了__BOUNDED_POINTERS__这个宏才有作用，否则这3个宏定义都是空的。
不过，尽管bounded指针看上去似乎很有用，但是这个功能却在2003年被去掉了。因此现在所有关于bounded指针的关键字其实都是一个空的宏。
不过还是分析下这几个宏的作用吧。__ptrvalue (ARG) < __ptrlow (ARG)判断目标指针是否小于合法指针的下界，如果其结果为真，即指针越界，则执行 && 后面的BOUNDS_VIOLATED 陷入中断程序；反之，指针没有越界，则不执行BOUNDS_VIOLATED，整个表达式的值为逗号表达式后面的值，即__ptrvalue (ARG)，即目标指针的值。 这么写主要是为了后面可以直接对CHECK_BOUNDS_LOW(ARG) 进行操作。
好了，鉴于此， 以上代码等价于一下代码：
char *
strcpy(char *dest, const char *src)
{
char c;
char *s = src;
const ptrdiff_t off = dest - s - 1;
do {
c = *s++;
s[off] = c;
} while (c != '\0');
return dest;
}
值得指出的是：此算法利用了进程平坦的内存模型，虚拟内存平坦铺开，于是任意两个指针的差就是两者之间的距离。得到地址间的相对距离off后，就不需要再用绝对地址寻址了，这样在每一次的循环中可以少一次dest++操作，而多出来的相对地址操作则完全可以用寄存器高效地完成！
接下来我们通过具体的实验来看看到底glibc的实现是否真的高效！
实验代码如下:
#include <stdio.h>
#include <stdlib.h>
#include <stddef.h>
#include <string.h>
char *strcpy_mcrt(char *dest, const char *src);
char *strcpy_glibc(char *dest, const char *src);
int main(int argc, const char *argv[])
{
int i = 0;
char dest[20] = {0};
char src[20] = {"hello world~!"};
for (; i < 100000000; i++)
{
strcpy_mcrt(dest, src);
strcpy_glibc(dest, src);
}
return 0;
}
char *strcpy_mcrt(char *dest, const char *src)
{
char *ret = dest;
while (*dest++ = *src++);
return ret;
}
char *strcpy_glibc(char *dest, const char *src)
{
char c;
char *s = (char *)src;
const ptrdiff_t off = dest - src - 1;
do {
c = *s++;
s[off] = c;
} while (c != '\0');
return dest;
}
第一次测试strcpy_mcrt函数：
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m5.925s
user 0m5.852s
sys 0m0.020s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m5.906s
user 0m5.872s
sys 0m0.016s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m5.908s
user 0m5.872s
sys 0m0.016s
平均下来有5.913s
再来测试strcpy_glibc函数：
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m6.061s
user 0m6.024s
sys 0m0.016s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m6.058s
user 0m6.028s
sys 0m0.016s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m6.092s
user 0m6.040s
sys 0m0.016s
平均下来有6.070s
这是怎么回事？ strcpy_glibc函数并不高效，反而效率更低？ 不能够啊
于是我在strcpy_glibc中将变量c改成register char c，再来看看结果如何？
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m3.933s
user 0m3.908s
sys 0m0.008s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m3.333s
user 0m3.316s
sys 0m0.008s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m3.941s
user 0m3.912s
sys 0m0.016s
平均下来有3.735s
哇！效果很明显啊！效率提高的原因也很简单：编译器将变量c放入一个寄存器，省去了每次循环中对变量c的两次内存访问。
Dump of assembler code for function strcpy_glibc:
0x080484e9 <+0>: push ebp
0x080484ea <+1>: mov ebp,esp
0x080484ec <+3>: push ebx
0x080484ed <+4>: sub esp,0x10
0x080484f0 <+7>: mov eax,DWORD PTR [ebp+0xc]
0x080484f3 <+10>: mov DWORD PTR [ebp-0x8],eax
0x080484f6 <+13>: mov edx,DWORD PTR [ebp+0x8]
0x080484f9 <+16>: mov eax,DWORD PTR [ebp+0xc]
0x080484fc <+19>: mov ecx,edx
0x080484fe <+21>: sub ecx,eax
0x08048500 <+23>: mov eax,ecx
0x08048502 <+25>: sub eax,0x1
0x08048505 <+28>: mov DWORD PTR [ebp-0xc],eax
0x08048508 <+31>: mov eax,DWORD PTR [ebp-0x8]
0x0804850b <+34>: movzx ebx,BYTE PTR [eax]
0x0804850e <+37>: add DWORD PTR [ebp-0x8],0x1
0x08048512 <+41>: mov eax,DWORD PTR [ebp-0xc]
0x08048515 <+44>: add eax,DWORD PTR [ebp-0x8]
0x08048518 <+47>: mov BYTE PTR [eax],bl
0x0804851a <+49>: test bl,bl
0x0804851c <+51>: jne 0x8048508 <strcpy_glibc+31>
0x0804851e <+53>: mov eax,DWORD PTR [ebp+0x8]
0x08048521 <+56>: add esp,0x10
0x08048524 <+59>: pop ebx
0x08048525 <+60>: pop ebp
0x08048526 <+61>: ret
End of assembler dump.可以看到，编译器将变量c放入寄存器ebx了。
可是想想不对啊，这不公平，这就相当于变相做了优化！
我的疑问有：
1、为什么要用一个中间变量c？
2、为什么定义指针s代替指针src，而不直接使用src？
于是我将代码修改成如下所示：
char *strcpy_glibc(char *dest, const char *src)
{
// register char c;
// char *s = (char *)src;
const ptrdiff_t off = dest - src;
do {
src[off] = *src;
} while (*src++ != '\0');
return dest;
}
编译却出现如下错误提示：
strcpy_test.c: In function ‘strcpy_glibc’:
strcpy_test.c:42: error: assignment of read-only location ‘*(src + (unsigned int)off)’
这就解释了为什么需要定义指针s而不能直接使用指针src了！因为src[off] = *src是写操作（尽管写的内容并不是src指针指向的真实内容）。
继续修改代码：
char *strcpy_glibc(char *dest, const char *src)
{
// char c;
char *s = (char *)src;
const ptrdiff_t off = dest - src;
do {
s[off] = *s;
} while (*s++ != '\0');
return dest;
}
测试strcpy_glibc结果如下：
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m4.795s
user 0m4.764s
sys 0m0.016s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m4.787s
user 0m4.764s
sys 0m0.012s
astrol@astrol:~/c++/9c++$ time ./strcpy_test
real 0m4.881s
user 0m4.844s
sys 0m0.016s
平均下来有4.821s
可见这种利用进程平坦内存模型的办法的确比机械的复制要高效，反汇编如下：
Dump of assembler code for function strcpy_glibc:
38 {
0x080484e9 <+0>: push ebp
0x080484ea <+1>: mov ebp,esp
0x080484ec <+3>: sub esp,0x10
39 // char c;
40 char *s = (char *)src;
0x080484ef <+6>: mov eax,DWORD PTR [ebp+0xc]
0x080484f2 <+9>: mov DWORD PTR [ebp-0x4],eax
41 const ptrdiff_t off = dest - src;
0x080484f5 <+12>: mov edx,DWORD PTR [ebp+0x8]
0x080484f8 <+15>: mov eax,DWORD PTR [ebp+0xc]
0x080484fb <+18>: mov ecx,edx
0x080484fd <+20>: sub ecx,eax
0x080484ff <+22>: mov eax,ecx
0x08048501 <+24>: mov DWORD PTR [ebp-0x8],eax
42
43 do {
44 s[off] = *s;
0x08048504 <+27>: mov eax,DWORD PTR [ebp-0x8]
0x08048507 <+30>: add eax,DWORD PTR [ebp-0x4]
0x0804850a <+33>: mov edx,DWORD PTR [ebp-0x4]
0x0804850d <+36>: movzx edx,BYTE PTR [edx]
0x08048510 <+39>: mov BYTE PTR [eax],dl
45 } while (*s++ != '\0');
0x08048512 <+41>: mov eax,DWORD PTR [ebp-0x4]
0x08048515 <+44>: movzx eax,BYTE PTR [eax]
0x08048518 <+47>: test al,al
0x0804851a <+49>: setne al
0x0804851d <+52>: add DWORD PTR [ebp-0x4],0x1
0x08048521 <+56>: test al,al
0x08048523 <+58>: jne 0x8048504 <strcpy_glibc+27>
46
47 return dest;
0x08048525 <+60>: mov eax,DWORD PTR [ebp+0x8]
48 }
0x08048528 <+63>: leave
0x08048529 <+64>: ret
为了作对比，输出strcpy_mcrt函数的反汇编如下：
Dump of assembler code for function strcpy_mcrt:
30 {
0x080484b6 <+0>: push ebp
0x080484b7 <+1>: mov ebp,esp
0x080484b9 <+3>: sub esp,0x10
31 char *ret = dest;
0x080484bc <+6>: mov eax,DWORD PTR [ebp+0x8]
0x080484bf <+9>: mov DWORD PTR [ebp-0x4],eax
32 while (*dest++ = *src++);
0x080484c2 <+12>: mov eax,DWORD PTR [ebp+0xc]
0x080484c5 <+15>: movzx edx,BYTE PTR [eax]
0x080484c8 <+18>: mov eax,DWORD PTR [ebp+0x8]
0x080484cb <+21>: mov BYTE PTR [eax],dl
0x080484cd <+23>: mov eax,DWORD PTR [ebp+0x8]
0x080484d0 <+26>: movzx eax,BYTE PTR [eax]
0x080484d3 <+29>: test al,al
0x080484d5 <+31>: setne al
0x080484d8 <+34>: add DWORD PTR [ebp+0x8],0x1
0x080484dc <+38>: add DWORD PTR [ebp+0xc],0x1
0x080484e0 <+42>: test al,al
0x080484e2 <+44>: jne 0x80484c2 <strcpy_mcrt+12>
33
34 return ret;
0x080484e4 <+46>: mov eax,DWORD PTR [ebp-0x4]
35 }
0x080484e7 <+49>: leave
0x080484e8 <+50>: ret
End of assembler dump.
计算出off值的内存访问可以忽略不计。其实不看汇编也可以得到结论：每一次循环中省去了*dest++操作，当字符串很长，或者像上面一样，重复很对此，那么这种优势就显现出来了。
那么，为什么glibc要用中间变量c呢？这岂不是吃力不讨好吗？
百度了下，在http://blog.chinaunix.net/uid-23629988-id-2853291.html中找到了答案：
1. glibc这个strcpy的效率在Intel的某些CPU上确实效率不高——我测试了
(Intel(R) Pentium(R) 4和Pentium(R) Dual-Core CPU E5300。有兴趣的朋友可以在其它CPU上测试一下，最好不是Intel的；
2. 一般glibc会根据不同的CPU实现不同版本的库函数，如strcpy。当然，我之前也知道这一点，不过我并没有去特意的看特定CPU的strcpy的代码。而是看这个generic的代码——当时我认为generic的strcpy仍然会高效。那么实际上对于intel的CPU来说，有特定的strcpy实现代码。所以在intel的CPU上，glibc的strcpy肯定会高效。
最好的答案就是glibc中的generic的实现代码，并不一定会高效。如果真的要学习且实现代码，看来还是要学习该CPU上的特定的实现代码。
参考链接：http://blog.chinaunix.net/space.php?uid=23629988&do=blog&frmd=147168&classid=116191&view=me
参考链接： http://blog.csdn.net/dog250/article/details/5302947