网站建设客户分析调查表,建设中学校园网站的来源,成都网站建设推来客,手机网站后台编辑器有哪些如果你完全理解如下内容#xff0c; 请联系我#xff1a;szu030606163.com#xff0c; 讨论更深层次合作 。 1. 大内高手—内存模型 单线程模型 多线程模型 2. 大内高手—栈/堆 backtrace的实现 alloca的实现 可变参数的实现。 malloc/free系列函数简介 new… 如果你完全理解如下内容 请联系我szu030606163.com 讨论更深层次合作 。 1. 大内高手—内存模型 单线程模型 多线程模型 2. 大内高手—栈/堆 backtrace的实现 alloca的实现 可变参数的实现。 malloc/free系列函数简介 new/delete系列操作符简介 3. 大内高手—全局内存 .bss说明 .data说明 .rodata说明 violatile关键字说明 static关键字说明 const关键字说明 4. 大内高手—内存分配算法 标准C(glibc)分配算法 STL(STLPort)分配算法 OS内部分配算法伙伴/SLAB 5. 大内高手—惯用手法 引用计数 预先分配 内存池 会话池 … 6. 大内高手—共享内存与线程局部存储 7. 大内高手—自动内存回收机制 8. 大内高手—常见内存错误 9. 大内高手—常用调试工具 大内高手—内存模型 了解linux的内存模型或许不能让你大幅度提高编程能力但是作为一个基本知识点应该熟悉。坐火车外出旅行时即时你对沿途的地方一无所知仍然可以到达目标地。但是你对整个路途都很比较清楚的话每到一个站都知道自己在哪里知道当地的风土人情对比一下所见所想旅程可能更有趣一些。 类似的了解linux的内存模型你知道每块内存每个变量在系统中处于什么样的位置。这同样会让你心情愉快知道这些有时还会让你的生活轻更松些。看看变量的地址你可以大致断定这是否是一个有效的地址。一个变量被破坏了你可以大致推断谁是犯罪嫌疑人。 Linux的内存模型一般为 地址 作用 说明 0xc000 0000 内核虚拟存储器 用户代码不可见区域 0xc000 0000 Stack用户栈 ESP指向栈顶 ↓ ↑ 空闲内存 0x4000 0000 文件映射区 0x4000 0000 ↑ 空闲内存 Heap(运行时堆) 通过brk/sbrk系统调用扩大堆向上增长。 .data、.bss(读写段) 从可执行文件中加载 0x0804 8000 .init、.text、.rodata(只读段) 从可执行文件中加载 0x0804 8000 保留区域 很多书上都有类似的描述本图取自于《深入理解计算机系统》p603略做修改。本图比较清析很容易理解但仍然有两点不足。下面补充说明一下 1. 第一点是关于运行时堆的。 为说明这个问题我们先运行一个测试程序并观察其结果 #includestdio.h intmain(intargc,char*argv[]) { int first 0; int*p0 malloc(1024); int*p1 malloc(1024 * 1024); int*p2 malloc(512 * 1024 * 1024 ); int*p3 malloc(1024 * 1024 * 1024 ); printf(main%p print%p\n,main,printf); printf(first%p\n, first); printf(p0%p p1%p p2%p p3%p\n,p0,p1,p2,p3); getchar(); return0; } 运行后输出结果为 main0x8048404 print0x8048324 first0xbfcd1264 p00x9253008 p10xb7ec0008 p20x97ebf008 p30x57ebe008 l main和print两个函数是代码段(.text)的其地址符合表一的描述。 l first是第一个临时变量由于在first之前还有一些环境变量它的值并非0xbfffffff而是0xbfcd1264这是正常的。 l p0是在堆中分配的其地址小于0x4000 0000这也是正常的。 l 但p1和p2也是在堆中分配的而其地址竟大于0x4000 0000与表一描述不符。 原因在于运行时堆的位置与内存管理算法相关也就是与malloc的实现相关。关于内存管理算法的问题我们在后继文章中有详细描述这里只作简要说明。在glibc实现的内存管理算法中Malloc小块内存是在小于0x4000 0000的内存中分配的通过brk/sbrk不断向上扩展而分配大块内存malloc直接通过系统调用mmap实现分配得到的地址在文件映射区所以其地址大于0x4000 0000。 从maps文件中可以清楚的看到一点 00514000-00515000 r-xp 00514000 00:00 0 00624000-0063e000 r-xp 00000000 03:01 718192 /lib/ld-2.3.5.so 0063e000-0063f000 r-xp 00019000 03:01 718192 /lib/ld-2.3.5.so 0063f000-00640000 rwxp 0001a000 03:01 718192 /lib/ld-2.3.5.so 00642000-00766000 r-xp 00000000 03:01 718193 /lib/libc-2.3.5.so 00766000-00768000 r-xp 00124000 03:01 718193 /lib/libc-2.3.5.so 00768000-0076a000 rwxp 00126000 03:01 718193 /lib/libc-2.3.5.so 0076a000-0076c000 rwxp 0076a000 00:00 0 08048000-08049000 r-xp 00000000 03:01 1307138 /root/test/mem/t.exe 08049000-0804a000 rw-p 00000000 03:01 1307138 /root/test/mem/t.exe 09f5d000-09f7e000 rw-p 09f5d000 00:00 0 [heap] 57e2f000-b7f35000 rw-p 57e2f000 00:00 0 b7f44000-b7f45000 rw-p b7f44000 00:00 0 bfb2f000-bfb45000 rw-p bfb2f000 00:00 0 [stack] 2. 第二是关于多线程的。 现在的应用程序多线程的居多。表一所描述的模型无法适用于多线程环境。按表一所述程序最多拥有上G的栈空间事实上在多线程情况下能用的栈空间是非常有限的。为了说明这个问题我们再看另外一个测试 #includestdio.h #includepthread.h void*thread_proc(void*param) { int first 0; int*p0 malloc(1024); int*p1 malloc(1024 * 1024); printf((0x%x): first%p\n, pthread_self(), first); printf((0x%x): p0%p p1%p \n, pthread_self(),p0,p1); return0; } #defineN5 intmain(intargc,char*argv[]) { intfirst 0; inti 0; void*ret NULL; pthread_ttid[N] {0}; printf(first%p\n, first); for(i 0; i N;i) { pthread_create(tidi,NULL,thread_proc,NULL); } for(i 0; i N;i) { pthread_join(tid[i], ret); } return0; } 运行后输出结果为 first0xbfd3d35c (0xb7f2cbb0): first0xb7f2c454 (0xb7f2cbb0): p00x84d52d8 p10xb4c27008 (0xb752bbb0): first0xb752b454 (0xb752bbb0): p00x84d56e0 p10xb4b26008 (0xb6b2abb0): first0xb6b2a454 (0xb6b2abb0): p00x84d5ae8 p10xb4a25008 (0xb6129bb0): first0xb6129454 (0xb6129bb0): p00x84d5ef0 p10xb4924008 (0xb5728bb0): first0xb5728454 (0xb5728bb0): p00x84d62f8 p10xb7e2c008 我们看一下: 主线程与第一个线程的栈之间的距离0xbfd3d35c - 0xb7f2c4540x7e10f08126M 第一个线程与第二个线程的栈之间的距离0xb7f2c454 - 0xb752b4540xa0100010M 其它几个线程的栈之间距离均为10M。 也就是说主线程的栈空间最大为126M而普通线程的栈空间仅为10M超这个范围就会造成栈溢出。 栈溢出的后果是比较严重的或者出现Segmentation fault错误或者出现莫名其妙的错误。 进阶2 l 栈 栈作为一种基本数据结构我并不感到惊讶用来实现函数调用这也司空见惯的作法。直到我试图找到另外一种方式实现递归操作时我才感叹于它的巧妙。要实现递归操作不用栈不是不可能而是找不出比它更优雅的方式。 尽管大多数编译器在优化时会把常用的参数或者局部变量放入寄存器中。但用栈来管理函数调用时的临时变量局部变量和参数是通用做法前者只是辅助手段且只在当前函数中使用一旦调用下一层函数这些值仍然要存入栈中才行。 通常情况下栈向下低地址增长每向栈中PUSH一个元素栈顶就向低地址扩展每从栈中POP一个元素栈顶就向高地址回退。一个有兴趣的问题在x86平台上栈顶寄存器为ESP那么ESP的值在是PUSH操作之前修改呢还是在PUSH操作之后修改呢PUSH ESP这条指令会向栈中存入什么数据呢据说x86系列CPU中除了286外都是先修改ESP再压栈的。由于286没有CPUID指令有的OS用这种方法检查286的型号。 一个函数内的局部变量以及其调用下一级函数的参数所占用的内存空间作为一个基本的单元称为一个帧(frame)。在gdb里f命令就是用来查看指定帧的信息的。在两个frame之间通过还存有其它信息比如上一层frame的分界地址(EBP)等。 关于栈的基本知识就先介绍这么多我们下面来看看一些关于栈的技巧及应用 1. backtrace的实现 callstack调试器的基本功能之一利用此功能你可以看到各级函数的调用关系。在gdb中这一功能被称为backtrace输入bt命令就可以看到当前函数的callstack。它的实现多少有些有趣我们在这里研究一下。 我们先看看栈的基本模型 参数N ↓高地址 参数… 函数参数入栈的顺序与具体的调用方式有关 参数3 参数2 参数1 EIP 返回本次调用后下一条指令的地址 EBP 保存调用者的EBP然后EBP指向此时的栈顶。 临时变量1 临时变量2 临时变量3 临时变量… 临时变量5 ↓低地址 要实现callstack我们需要知道以下信息 l 调用函数时的指令地址即当时的EIP。 l 指令地址对应的源代码代码位置。 关于第一点从上表中我们可以看出栈中存有各级EIP的值我们取出来就行了。用下面的代码可以轻易实现 #includestdio.h intbacktrace(void**BUFFER,int SIZE) { int n 0; int*p n; int i 0; int ebp p[1]; int eip p[2]; for(i 0; i SIZE; i) { BUFFER[i] (void*)eip; p (int*)ebp; ebp p[0]; eip p[1]; } return SIZE; } #defineN 4 staticvoid test2() { int i 0; void*BUFFER[N] {0}; backtrace(BUFFER,N); for(i 0; i N; i) { printf(%p\n, BUFFER[i]); } return; } staticvoid test1() { test2(); } staticvoid test() { test1(); } intmain(intargc,char*argv[]) { test(); return 0; } 程序输出 0x8048460 0x804849c 0x80484a9 0x80484cc 关于第二点如何把指令地址与行号对应起来这也很简单。可以从MAP文件或者ELF中查询。Binutil带有一个addr2line的小工具可以帮助实现这一点。 [rootlinux bt]# addr2line 0x804849c -e bt.exe /root/test/bt/bt.c:42 2. alloca的实现 大家都知道动态分配的内存一定要释放掉否则就会有内存泄露。可能鲜有人知动态分配的内存可以不用释放。Alloca就是这样一个函数最后一个a代表auto即自动释放的意思。 Alloca是在栈中分配内存的。即然是在栈中分配就像其它在栈中分配的临时变量一样在当前函数调用完成时这块内存自动释放。 正如我们前面讲过栈的大小是有限制的普通线程的栈只有10M大小所以在分配时要量力而行且不要分配过大内存。 Alloca可能会渐渐的退出历史舞台原因是新的C/C标准都支持变长数组。比如int array[n]老版本的编译器要求n是常量而新编译器允许n是变量。编译器支持的这一功能完全可以取代alloca。 这不是一个标准函数但像linux和win32等大多数平台都支持。即使少数平台不支持要自己实现也不难。这里我们简单介绍一下alloca的实现方法。 我们先看看一个小程序再看看它对应的汇编代码一切都清楚了。 #includestdio.h intmain(intargc,char*argv[]) { int n 0; int*p alloca(1024); printf(n%p p%p\n, n,p); return 0; } 汇编代码为 intmain(intargc,char*argv[]) { 8048394: 55 push p 8048395: 89 e5 mov %esp,p 8048397: 83 ec 18 sub $0x18,%esp 804839a: 83 e4 f0 and $0xfffffff0,%esp 804839d: b8 00 00 00 00 mov $0x0,x 80483a2: 83 c0 0f add $0xf,x 80483a5: 83 c0 0f add $0xf,x 80483a8: c1 e8 04 shr $0x4,x 80483ab: c1 e0 04 shl $0x4,x 80483ae: 29 c4 sub x,%esp int n 0; 80483b0: c7 45 fc 00 00 00 00 movl $0x0,0xfffffffc(p) int*p alloca(1024); 80483b7: 81 ec 10 04 00 00 sub $0x410,%esp 80483bd: 8d 44 24 0c lea 0xc(%esp),x 80483c1: 83 c0 0f add $0xf,x 80483c4: c1 e8 04 shr $0x4,x 80483c7: c1 e0 04 shl $0x4,x 80483ca: 89 45f8 mov x,0xfffffff8(p) printf(n%p p%p\n, n,p); 80483cd: 8b 45f8 mov 0xfffffff8(p),x 80483d0: 89 44 24 08 mov x,0x8(%esp) 80483d4: 8d 45 fc lea 0xfffffffc(p),x 80483d7: 89 44 24 04 mov x,0x4(%esp) 80483db: c7 04 24 98 84 04 08 movl $0x8048498,(%esp) 80483e2: e8d1 fe ff ff call 80482b8 printfplt return 0; 80483e7: b8 00 00 00 00 mov $0x0,x } 其中关键的一条指令为sub $0x410,%esp 由此可以看出实现alloca仅仅是把ESP减去指定大小扩大栈空间记记住栈是向下增长这块空间就是分配的内存。 3. 可变参数的实现。 对新手来说可变参数的函数也是比较神奇。还是以一个小程序来说明它的实现。 #includestdio.h #includestdarg.h intprint(constchar*fmt, ...) { int n1 0; int n2 0; int n3 0; va_list ap; va_start(ap,fmt); n1 va_arg(ap,int); n2 va_arg(ap,int); n3 va_arg(ap,int); va_end(ap); printf(n1%d n2%d n3%d\n, n1, n2, n3); return 0; } intmain(intarg, char argv[]) { print(%d\n, 1, 2, 3); return 0; } 我们看看对应的汇编代码 intprint(constchar*fmt, ...) { 8048394: 55 push p 8048395: 89 e5 mov %esp,p 8048397: 83 ec 28 sub $0x28,%esp int n1 0; 804839a: c7 45 fc 00 00 00 00 movl $0x0,0xfffffffc(p) int n2 0; 80483a1: c7 45f8 00 00 00 00 movl $0x0,0xfffffff8(p) int n3 0; 80483a8: c7 45f4 00 00 00 00 movl $0x0,0xfffffff4(p) va_list ap; va_start(ap,fmt); 80483af: 8d 45 0c lea 0xc(p),%eax 80483b2: 89 45 f0 mov %eax,0xfffffff0(p) n1 va_arg(ap,int); 80483b5: 8b 55 f0 mov 0xfffffff0(p),x 80483b8: 8d 45 f0 lea 0xfffffff0(p),%eax 80483bb: 83 00 04 addl $0x4,(%eax) 80483be: 8b 02 mov (x),%eax 80483c0: 89 45 fc mov %eax,0xfffffffc(p) n2 va_arg(ap,int); 80483c3: 8b 55 f0 mov 0xfffffff0(p),x 80483c6: 8d 45 f0 lea 0xfffffff0(p),%eax 80483c9: 83 00 04 addl $0x4,(%eax) 80483cc: 8b 02 mov (x),%eax 80483ce: 89 45f8 mov %eax,0xfffffff8(p) n3 va_arg(ap,int); 80483d1: 8b 55 f0 mov 0xfffffff0(p),x 80483d4: 8d 45 f0 lea 0xfffffff0(p),%eax 80483d7: 83 00 04 addl $0x4,(%eax) 80483da: 8b 02 mov (x),%eax 80483dc: 89 45f4 mov %eax,0xfffffff4(p) va_end(ap); printf(n1%d n2%d n3%d\n, n1, n2, n3); 80483df: 8b 45f4 mov 0xfffffff4(p),%eax 80483e2: 89 44 24 0c mov %eax,0xc(%esp) 80483e6: 8b 45f8 mov 0xfffffff8(p),%eax 80483e9: 89 44 24 08 mov %eax,0x8(%esp) 80483ed: 8b 45 fc mov 0xfffffffc(p),%eax 80483f0: 89 44 24 04 mov %eax,0x4(%esp) 80483f4: c7 04 24f8 84 04 08 movl $0x80484f8,(%esp) 80483fb: e8 b8 fe ff ff call 80482b8 printfplt return 0; 8048400: b8 00 00 00 00 mov $0x0,%eax } intmain(intarg,char argv[]) { 8048407: 55 push p 8048408: 89 e5 mov %esp,p 804840a: 83 ec 18 sub $0x18,%esp 804840d: 83 e4 f0 and $0xfffffff0,%esp 8048410: b8 00 00 00 00 mov $0x0,%eax 8048415: 83 c0 0f add $0xf,%eax 8048418: 83 c0 0f add $0xf,%eax 804841b: c1 e8 04 shr $0x4,%eax 804841e: c1 e0 04 shl $0x4,%eax 8048421: 29 c4 sub %eax,%esp int n print(%d\n, 1, 2, 3); 8048423: c7 44 24 0c 03 00 00 movl $0x3,0xc(%esp) 804842a: 00 804842b: c7 44 24 08 02 00 00 movl $0x2,0x8(%esp) 8048432: 00 8048433: c7 44 24 04 01 00 00 movl $0x1,0x4(%esp) 804843a: 00 804843b: c7 04 24 0b 85 04 08 movl $0x804850b,(%esp) 8048442: e8 4d ff ff ff call 8048394 print 8048447: 89 45 fc mov %eax,0xfffffffc(p) return 0; 804844a: b8 00 00 00 00 mov $0x0,%eax } 从汇编代码中我们可以看出参数是逆序入栈的。在取参数时先让ap指向第一个参数又因为栈是向下增长的不断把指针向上移动就可以取出所有参数了。 进阶3 全局内存 有人可能会说全局内存就是全局变量嘛有必要专门一章来介绍吗这么简单的东西还能玩出花来我从来没有深究它不一样写程序吗关于全局内存这个主题虽然玩不出花来但确实有些重要了解这些知识对于优化程序的时间和空间很有帮助。因为有好几次这样经历我才决定花一章篇幅来介绍它。 正如大家所知道的全局变量是放在全局内存中的但反过来却未必成立。用static修饰的局部变量就是放在放全局内存的它的作用域是局部的但生命期是全局的。在有的嵌入式平台中堆实际上就是一个全局变量它占用相当大的一块内存在运行时把这块内存进行二次分配。 这里我们并不强调全局变量和全局内存的差别。在本文中全局强调的是它的生命期而不是它的作用域所以有时可能把两者的概念互换。 一般来说在一起定义的两个全局变量在内存的中位置是相邻的。这是一个简单的常识但有时挺有用如果一个全局变量被破坏了不防先查查其前后相关变量的访问代码看看是否存在越界访问的可能。 在ELF格式的可执行文件中全局内存包括三种bss、data和rodata。其它可执行文件格式与之类似。了解了这三种数据的特点我们才能充分发挥它们的长处达到速度与空间的最优化。 1. bss 已经记不清bss代表Block Storage Start还是Block Started by Symbol。像这我这种没有用过那些史前计算机的人终究无法明白这样怪异的名字也就记不住了。不过没有关系重要的是我们要清楚bss全局变量有什么样特点以及如何利用它。 通俗的说bss是指那些没有初始化的和初始化为0的全局变量。它有什么特点呢让我们来看看一个小程序的表现。 intbss_array[1024 * 1024] {0}; intmain(intargc,char*argv[]) { return 0; } [rootlocalhost bss]# gcc -g bss.c -o bss.exe [rootlocalhost bss]# ll total 12 -rw-r--r-- 1root root 84Jun 22 14:32 bss.c -rwxr-xr-x1 root root 5683 Jun 22 14:32 bss.exe 变量bss_array的大小为4M而可执行文件的大小只有5K。由此可见bss类型的全局变量只占运行时的内存空间而不占文件空间。 另外大多数操作系统在加载程序时会把所有的bss全局变量全部清零无需要你手工去清零。但为保证程序的可移植性手工把这些变量初始化为0也是一个好习惯。 2. data 与bss相比data就容易明白多了它的名字就暗示着里面存放着数据。当然如果数据全是零为了优化考虑编译器把它当作bss处理。通俗的说data指那些初始化过非零的非const的全局变量。它有什么特点呢我们还是来看看一个小程序的表现。 intdata_array[1024 * 1024] {1}; intmain(intargc,char*argv[]) { return 0; } [rootlocalhostdata]# gcc-gdata.c -odata.exe [rootlocalhostdata]# ll total 4112 -rw-r--r-- 1root root 85Jun 22 14:35 data.c -rwxr-xr-x1 root root 4200025 Jun 22 14:35 data.exe 仅仅是把初始化的值改为非零了文件就变为4M多。由此可见data类型的全局变量是即占文件空间又占用运行时内存空间的。 3. rodata rodata的意义同样明显ro代表read only即只读数据(const)。关于rodata类型的数据要注意以下几点 l 常量不一定就放在rodata里有的立即数直接编码在指令里存放在代码段(.text)中。 l 对于字符串常量编译器会自动去掉重复的字符串保证一个字符串在一个可执行文件(EXE/SO)中只存在一份拷贝。 l rodata是在多个进程间是共享的这可以提高空间利用率。 l 在有的嵌入式系统中rodata放在ROM(如norflash)里运行时直接读取ROM内存无需要加载到RAM内存中。 l 在嵌入式linux系统中通过一种叫作XIP就地执行的技术也可以直接读取而无需要加载到RAM内存中。 由此可见把在运行过程中不会改变的数据设为rodata类型的是有很多好处的在多个进程间共享可以大大提高空间利用率甚至不占用RAM空间。同时由于rodata在只读的内存页面(page)中是受保护的任何试图对它的修改都会被及时发现这可以帮助提高程序的稳定性。 4. 变量与关键字 static关键字用途太多以致于让新手模糊。不过总结起来就有两种作用改变生命期和限制作用域。如 l 修饰inline函数限制作用域 l 修饰普通函数限制作用域 l 修饰局部变量改变生命期 l 修饰全局变量限制作用域 const关键字倒是比较明了用const修饰的变量放在rodata里字符串默认就是常量。对const注意以下几点就行了。 l 指针常量指向的数据是常量。如 const char* p “abc”; p指向的内容是常量但p本身不是常量你可以让p再指向”123”。 l 常量指针指针本身是常量。如char* const p “abc”; p本身就是常量你不能让p再指向”123”。 l 指针常量 常量指针指针和指针指向的数据都是常量。const char* const p ”abc”;两者都是常量不能再修改。 violatile关键字通常用来修饰多线程共享的全局变量和IO内存。告诉编译器不要把此类变量优化到寄存器中每次都要老老实实的从内存中读取因为它们随时都可能变化。这个关键字可能比较生僻但千万不要忘了它否则一个错误让你调试好几天也得不到一点线索。 进阶4 内存管理器(一) 作为一个C程序员每天都在和malloc/free/calloc/realloc系列函数打交道。也许和它们混得太熟了反而忽略了它们的存在甚至有了三五年的交情仍然对它们的实现一无所知。相反一些好奇心未泯的新手对它们的实现有着浓厚的兴趣。当初正是一个新同事的问题促使我去研究内存管理算法的实现。 内存管理算法多少有些神秘我们很少想着去实现自己的内存管理算法这也难怪有这样需求的情况并不多。其实至于内存分配算法的实现说简单也简单说复杂也复杂。要写一个简单的或许半天时间就可以搞掂而要写一个真正实用的可能要花上你几周甚至几个月的时间。 malloc和free是两个核心函数而calloc和realloc之所以存在完全是为了提高效率的缘故。否则完全可以用malloc和free的组合来模拟它们。 拿calloc函数的实现来说在32位机上内存管理器保证内存至少是4字节对齐的其长度也会扩展到能被4字节整除那么其清零算法就可以优化。可以一次清零4个字节这大大提高清零速度。 拿realloc函数的实现来说如果realloc的指针后面有足够的空间内存管理器可以直接扩展其大小而无须拷贝原有内容。当然新大小比原来还小时更不拷贝了。相反通过malloc和free来实现realloc时两种情况下都要拷贝效率自然会低不少。 另外还有两个非机标准的但很常用的函数也涉及到内存分配strdup和strndup。这两个函数在linux和win32下都支持非常方便。这完全可以用malloc来模拟而且没有性能上的损失。 这里我们主要关注malloc和free两个函数的实现并以glibc 2.3.5(32位linux)为例分析。 内存管理器的目标 内存管理器为什么难写在设计内存管理算法时要考虑什么因素管理内存这是内存管理器的功能需求。正如设计其它软件一样质量需求一样占有重要的地位。分析内存管理算法之前我们先看看对内存管理算法的质量需求有哪些 l 最大化兼容性 要实现内存管理器时先要定义出分配器的接口函数。接口函数没有必要标新立异而是要遵循现有标准(如POSIX或者Win32)让使用者可以平滑的过度到新的内存管理器上。 l 最大化可移植性 通常情况下内存管理器要向OS申请内存然后进行二次分配。所以在适当的时候要扩展内存或释放多余的内存这要调用OS提供的函数才行。OS提供的函数则是因平台而异尽量抽象出平台相关的代码保证内存管理器的可移植性。 l 浪费最小的空间 内存管理器要管理内存必然要使用自己一些数据结构这些数据结构本身也要占内存空间。在用户眼中这些内存空间毫无疑问是浪费掉了如果浪费在内存管理器身的内存太多显然是不可以接受的。 内存碎片也是浪费空间的罪魁祸首若内存管理器中有大量的内存碎片它们是一些不连续的小块内存它们总量可能很大但无法使用这也是不可以接受的。 l 最快的速度 内存分配/释放是常用的操作。按着2/8原则常用的操作就是性能热点热点函数的性能对系统的整体性能尤为重要。 l 最大化可调性以适应于不同的情况 内存管理算法设计的难点就在于要适应用不同的情况。事实上如果缺乏应用的上下文是无法评估内存管理算法的好坏的。可以说在任何情况下专用算法都比通用算法在时/空性能上的表现更优。 为每种情况都写一套内存管理算法显然是不太合适的。我们不需要追求最优算法那样代价太高能达到次优就行了。设计一套通用内存管理算法通过一些参数对它进行配置可以让它在特定情况也有相当出色的表现这就是可调性。 l 最大化局部性(Locality) 大家都知道使用cache可以提高程度的速度但很多人未必知道cache使程序速度提高的真正原因。拿CPU内部的cache和RAM的访问速度相比速度可能相差一个数量级。两者的速度上的差异固然重要但这并不是提高速度的充分条件只是必要条件。 另外一个条件是程序访问内存的局部性(Locality)。大多数情况下程序总访问一块内存附近的内存把附近的内存先加入到cache中下次访问cache中的数据速度就会提高。否则如果程序一会儿访问这里一会儿访问另外一块相隔十万八千里的内存这只会使数据在内存与cache之间来回搬运不但于提高速度无益反而会大大降低程序的速度。 因此内存管理算法要考虑这一因素减少cache miss和page fault。 l 最大化调试功能 作为一个C/C程序员内存错误可以说是我们的噩梦上一次的内存错误一定还让你记忆犹新。内存管理器提供的调试功能强大易用特别对于嵌入式环境来说内存错误检测工具缺乏内存管理器提供的调试功能就更是不可或缺了。 l 最大化适应性 前面说了最大化可调性以便让内存管理器适用于不同的情况。但是对于不同情况都要去调设置无疑太麻烦是非用户友好的。要尽量让内存管理器适用于很广的情况只有极少情况下才去调设置。 设计是一个多目标优化的过程有些目标之间存在着竞争。如何平衡这些竞争力是设计的难点之一。在不同的情况下这些目标的重要性又不一样所以根本不存在一个最好的内存分配算法。 关于glibc的内存分配器我们并打算做代码级分析只谈谈几点有趣的东西 1. Glibc分配算法概述 l 小于等于64字节用pool算法分配。 l 64到512字节之间在最佳凭配算法分配和pool算法分配中取一种合适的。 l 大于等于512字节用最佳凭配算法分配。 l 大于等于128K直接调用OS提供的函数(如mmap)分配。 2. Glibc扩展内存的方式 l int brk(void *end_data_segment); 本函数用于扩展堆空间堆空间的定义可参考内存模型一章用end_data_segment指明堆的结束地址。 l void *sbrk(ptrdiff_t increment); 本函数用于扩展堆空间堆空间的定义可参考内存模型一章用increment指定要增加的大小。 l void* mmap(void *start, size_t length, int prot , int flags, int fd, off_t offset); 本函数用于分配大块内存了如前面所述大于128K的内存。 3. 空指针和零长度内存 l free(NULL)会让程序crash吗答案是不会标准C要求free接受空指针然后什么也不做。 l malloc(0)会分配成功吗答案是会的它会返回一块最小内存给你。 4. 对齐与取整 l 内存管理器会保证分配出来的内存地址是对齐的通常是4或8字节对齐。 l 内存管理器会对要求内存长度取整让内存长度能被4或8的整除。 5. 已经分配内存的结构 如果前面有一块有效内存块的则第一个size_t指明前一块内存的大小。 第二个size_t指明自己的大小同时还指明自己是不是用mmap分配的(M)前面是否有一个效内存块P。你可能觉得奇怪在32位机上sizeof(size_t)就是32位怎么还能留下两个位来保存标志呢前面我们说了会对内存长度取整保证最低2或3bits为0即是空闲的。 6. 空闲内存的管理 由此可以看出最小内存块的长度为16字节 sizeof(size_t) sizeof(size_t) sizeof(void*) sizeof(void*) 0 这一招非常管用第一次看到时感觉简直太巧妙了。这使得无需要额外的内存来管理空闲块利用空闲块自己把空闲块强制转换成一个双向链表就行了。 大内高手—共享内存与线程局部存储 城里的人想出去城外的人想进来。这是《围城》里的一句话它可能比《围城》本身更加有名。我想这句话的前提是要么住在城里要么住在城外二者只能居其一。否则想住在城里就可以住在城里想住在城外就可以住在城外你大可以选择单日住在城里双日住在城外也就没有心思去想出去还是进来了。 理想情况是即可以住在城里又可以住在城外而不是走向极端。尽管像青蛙一样的两栖动物绝不会比人类更高级但能适应于更多环境的能力毕竟有它的优势。技术也是如此共享内存和线程局部存储就是实例它们是为了防止走向内存完全隔离和完全共享两个极端的产物。 当我们发明了MMU时大家认为天下太平了各个进程空间独立互不影响程序的稳定性将大提高。但马上又认识到进程完全隔离也不行因为各个进程之间需要信息共享。于是就搞出一种称为共享内存的东西。 当我们发明了线程的时大家认为这下可爽了线程可以并发执行创建和切换的开销相对进程来说小多了。线程之间的内存是共享的线程间通信快捷又方便。但马上又认识到有些信息还是不共享为好应该让各个线程保留一点隐私。于是就搞出一个线程局部存储的玩意儿。 共享内存和线程局部存储是两个重要又不常用的东西平时很少用但有时候又离不了它们。本文介绍将两者的概念、原理和使用方法把它们放在自己的工具箱里以供不时之需。 1. 共享内存 大家都知道进程空间是独立的它们之间互不影响。比如同是0xabcd1234地址的内存在不同的进程中它们的数据是不同的没有关系的。这样做的好处很多每个进程的地址空间变大了它们独占4G(32位)的地址空间让编程实现更容易。各个进程空间独立一个进程死掉了不会影响其它进程提高了系统的稳定性。 要做到进程空间独立光靠软件是难以实现的通常要依赖于硬件的帮助。这种硬件通常称为MMU(Memory Manage Unit)即所谓的内存管理单元。在这种体系结构下内存分为物理内存和虚拟内存两种。物理内存就是实际的内存你机器上装了多大内存就有多大内存。而应用程序中使用的是虚拟内存访问内存数据时由MMU根据页表把虚拟内存地址转换对应的物理内存地址。 MMU把各个进程的虚拟内存映射到不同的物理内存上这样就保证了进程的虚拟内存是独立的。然而物理内存往往远远少于各个进程的虚拟内存的总和。怎么办呢通常的办法是把暂时不用的内存写到磁盘上去要用的时候再加载回内存中来。一般会搞一个专门的分区保存内存数据这就是所谓的交换分区。 这些工作由内核配合MMU硬件完成内存管理是操作系统内核的重要功能。其中为了优化性能使用了不少高级技术所以内存管理通常比较复杂。比如在决定把什么数据换出到磁盘上时采用最近最少使用的策略把常用的内存数据放在物理内存中把不常用的写到磁盘上这种策略的假设是最近最少使用的内存在将来也很少使用。在创建进程时使用COW(Copy on Write)的技术大大减少了内存数据的复制。为了提高从虚拟地址到物理地址的转换速度硬件通常采用TLB技术把刚转换的地址存在cache里下次可以直接使用。 从虚拟内存到物理内存的映射并不是一个字节一个字节映射的而是以一个称为页(page)最小单位的为基础的页的大小视硬件平台而定通常是4K。当应用程序访问的内存所在页面不在物理内存中时MMU产生一个缺页中断并挂起当前进程缺页中断负责把相应的数据从磁盘读入内存中再唤醒挂起的进程。 进程的虚拟内存与物理内存映射关系如下图所示(灰色页为被不在物理内存中的页): 也许我们很少直接使用共享内存实际上除非性能上有特殊要求我更愿意采用socket或者管道作为进程间通信的方式。但我们常常间接的使用共享内存大家都知道共享库或称为动态库的优点是多个应用程序可以公用。如果每个应用程序都加载一份共享库到内存中显然太浪费了。所以操作系统把共享库放在共享内存中让多个应用程序共享。另外同一个应用程序运行多个实例时也采用同样的方式保证内存中只有一份可执行代码。这样的共享内存是设为只读属性的防止应用程序无意中破坏它们。当调试器要设置断点时相应的页面被拷贝一分设置为可写的再向其中写入断点指令。这些事情完全由操作系统等底层软件处理了应用程序本身无需关心。 共享内存是怎么实现的呢我们来看看下图(黄色页为共享内存) 由上图可见实现共享内存非常容易只是把两个进程的虚拟内存映射同一块物理内存就行了。不过要注意物理内存相同而虚拟地址却不一定相同如图中所示进程1的page5和进程2的page2都映射到物理内存的page1上。 如何在程序中使用共享内存呢通常很简单操作系统或者函数库提供了一些API给我们使用。如 Linux: void * mmap(void *start, size_t length, int prot , int flags, int fd, off_t offset); int munmap(void *start, size_t length); Win32: HANDLE CreateFileMapping(HANDLE hFile, // handle to fileLPSECURITY_ATTRIBUTES lpAttributes, // securityDWORD flProtect, // protectionDWORD dwMaximumSizeHigh, // high-order DWORD of sizeDWORD dwMaximumSizeLow, // low-order DWORD of sizeLPCTSTR lpName // object name);BOOL UnmapViewOfFile(LPCVOID lpBaseAddress // starting address);2. 线程局部存储(TLS) 同一个进程中的多个线程它们的内存空间是共享的栈除外在一个线程修改的内存内容对所有线程都生效。这是一个优点也是一个缺点。说它是优点线程的数据交换变得非常快捷。说它是缺点一个线程死掉了其它线程也性命不保;多个线程访问共享数据需要昂贵的同步开销也容易造成同步相关的BUG;。 在unix下大家一直都对线程不是很感兴趣直到很晚以后才引入线程这东西。像X Sever要同时处理N个客户端的连接每秒钟要响应上百万个请求开发人员宁愿自己实现调度机制也不用线程。让人很难想象X Server是单进程单线程模型的。再如Apache(1.3x)在unix下的实现也是采用多进程模型的把像记分板等公共信息放入共享内存中也不愿意采用多线程模型。 正如《unix编程艺术》中所说线程局部存储的出现使得这种情况出现了转机。采用线程局部存储每个线程有一定的私有空间。这可以避免部分无意的破坏不过仍然无法避免有意的破坏行为。 个人认为这完全是因为unix程序不喜欢面向对象方法引起的数据没有很好的封装起来全局变量满天飞在多线程情况下自然容易出问题。如果采用面向对象的方法可以让这种情况大为改观而无需要线程局部存储来帮忙。 当然多一种技术就多一种选择知道线程局部存储还是有用的。尽管只用过几次线程局部存储的方法在那种情况下没有线程局部存储确实很难用其它办法实现。 线程局部存储在不同的平台有不同的实现可移植性不太好。幸好要实现线程局部存储并不难最简单的办法就是建立一个全局表通过当前线程ID去查询相应的数据因为各个线程的ID不同查到的数据自然也不同了。 大多数平台都提供了线程局部存储的方法无需要我们自己去实现 linux: 方法一 int pthread_key_create(pthread_key_t *key, void (*destructor)(void*)); int pthread_key_delete(pthread_key_t key); void *pthread_getspecific(pthread_key_t key); int pthread_setspecific(pthread_key_t key, const void *value); 方法二 __thread int i; Win32 方法一 DWORD TlsAlloc(VOID); BOOL TlsFree( DWORD dwTlsIndex // TLS index ); BOOL TlsSetValue( DWORD dwTlsIndex, // TLS index LPVOID lpTlsValue // value to store ); LPVOID TlsGetValue( DWORD dwTlsIndex // TLS index ); 方法二 __declspec( thread ) int tls_i 1; ~~end~~ 进阶5 常见内存错误 随着诸如代码重构和单元测试等方法引入实践调试技能渐渐弱化了甚至有人主张废除调试器。这是有道理的原因在于调试的代价往往太大了特别是调试系统集成之后的BUG一个BUG花了几天甚至数周时间并非罕见。 而这些难以定位的BUG基本上可以归为两类内存错误和并发问题。而又以内存错误最为普遍即使是久经沙场的老手也有时也难免落入陷阱。前事不忘后世之师了解这些常见的错误在编程时就加以注意把出错的概率降到最低可以节省不少时间。 这些列举一些常见的内存错误供新手参考。 1. 内存泄露。 大家都知道在堆上分配的内存如果不再使用了应该把它释放掉以便后面其它地方可以重用。在C/C中内存管理器不会帮你自动回收不再使用的内存。如果你忘了释放不再使用的内存这些内存就不能被重用就造成了所谓的内存泄露。 把内存泄露列为首位倒并不是因为它有多么严重的后果而因为它是最为常见的一类错误。一两处内存泄露通常不至于让程序崩溃也不会出现逻辑上的错误加上进程退出时系统会自动释放该进程所有相关的内存所以内存泄露的后果相对来说还是比较温和的。当然了量变会产生质变一旦内存泄露过多以致于耗尽内存后续内存分配将会失败程序可能因此而崩溃。 现在的PC机内存够大了加上进程有独立的内存空间对于一些小程序来说内存泄露已经不是太大的威胁。但对于大型软件特别是长时间运行的软件或者嵌入式系统来说内存泄露仍然是致命的因素之一。 不管在什么情况下采取比较谨慎的态度杜绝内存泄露的出现都是可取的。相反认为内存有的是对内存泄露放任自流都不是负责的。尽管一些工具可以帮助我们检查内存泄露问题我认为还是应该在编程时就仔细一点及早排除这类错误工具只是用作验证的手段。 2. 内存越界访问。 内存越界访问有两种一种是读越界即读了不属于自己的数据如果所读的内存地址是无效的程度立刻就崩溃了。如果所读内存地址是有效的在读的时候不会出问题但由于读到的数据是随机的它会产生不可预料的后果。另外一种是写越界又叫缓冲区溢出。所写入的数据对别人来说是随机的它也会产生不可预料的后果。 内存越界访问造成的后果非常严重是程序稳定性的致命威胁之一。更麻烦的是它造成的后果是随机的表现出来的症状和时机也是随机的让BUG的现象和本质看似没有什么联系这给BUG的定位带来极大的困难。 一些工具可以够帮助检查内存越界访问的问题但也不能太依赖于工具。内存越界访问通常是动态出现的即依赖于测试数据在极端的情况下才会出现除非精心设计测试数据工具也无能为力。工具本身也有一些限制甚至在一些大型项目中工具变得完全不可用。比较保险的方法还是在编程是就小心特别是对于外部传入的参数要仔细检查。 3. 野指针。 野指针是指那些你已经释放掉的内存指针。当你调用free(p)时你真正清楚这个动作背后的内容吗你会说p指向的内存被释放了。没错p本身有变化吗答案是p本身没有变化。它指向的内存仍然是有效的你继续读写p指向的内存没有人能拦得住你。 释放掉的内存会被内存管理器重新分配此时野指针指向的内存已经被赋予新的意义。对野指针指向内存的访问无论是有意还是无意的都为此会付出巨大代价因为它造成的后果如同越界访问一样是不可预料的。 释放内存后立即把对应指针置为空值这是避免野指针常用的方法。这个方法简单有效只是要注意当然指针是从函数外层传入的时在函数内把指针置为空值对外层的指针没有影响。比如你在析构函数里把this指针置为空值没有任何效果这时应该在函数外层把指针置为空值。 4. 访问空指针。 空指针在C/C中占有特殊的地址通常用来判断一个指针的有效性。空指针一般定义为0。现代操作系统都会保留从0开始的一块内存至于这块内存有多大视不同的操作系统而定。一旦程序试图访问这块内存系统就会触发一个异常。 操作系统为什么要保留一块内存而不是仅仅保留一个字节的内存呢原因是一般内存管理都是按页进行管理的无法单纯保留一个字节至少要保留一个页面。保留一块内存也有额外的好处可以检查诸如pNULL; p[1]之类的内存错误。 在一些嵌入式系统(如arm7)中从0开始的一块内存是用来安装中断向量的没有MMU的保护直接访问这块内存好像不会引发异常。不过这块内存是代码段的不是程序中有效的变量地址所以用空指针来判断指针的有效性仍然可行。 在访问指针指向的内存时在确保指针不是空指针。访问空指针指向的内存通常会导致程度崩溃或者不可预料的错误。 5. 引用未初始化的变量。 未初始化变量的内容是随机的(像VC一类的编译器会把它们初始化为固定值如0xcc)使用这些数据会造成不可预料的后果调试这样的BUG也是非常困难的。 对于态度严谨的程度员来说防止这类BUG非常容易。在声明变量时就对它进行初始化是一个编程的好习惯。另外也要重视编译器的警告信息发现有引用未初始化的变量立即修改过来。 6. 不清楚指针运算。 对于一些新手来说指针常常让他们犯糊涂。 比如int *p …; p1等于(size_t)p 1吗 老手自然清楚新手可能就搞不清了。事实上, pn等于 (size_t)p n * sizeof(*p) 指针是C/C中最有力的武器功能非常强大无论是变量指针还是函数指针都应该掌握都非常熟练。只要有不确定的地方马上写个小程序验证一下。对每一个细节都了然于胸在编程时会省下不少时间。 7. 结构的成员顺序变化引发的错误。 在初始化一个结构时老手可能很少像新手那样老老实实的一个成员一个成员的为结构初始化而是采用快捷方式如 Structs { int l; char*p; }; intmain(intargc,char*argv[]) { struct s s1 {4, abcd}; return 0; } 以上这种方式是非常危险的原因在于你对结构的内存布局作了假设。如果这个结构是第三方提供的他很可能调整结构中成员的相对位置。而这样的调整往往不会在文档中说明你自然很少去关注。如果调整的两个成员具有相同数据类型编译时不会有任何警告而程序的逻辑上可能相距十万八千里了。 正确的初始化方法应该是当然一个成员一个成员的初始化也行 structs { int l; char*p; }; intmain(intargc,char*argv[]) { struct s s1 {.l4, .p abcd}; struct s s2 {l:4,p:abcd}; return 0; } 8. 结构的大小变化引发的错误。 我们看看下面这个例子 structbase { int n; }; structs { struct base b; int m; }; 在OOP中我们可以认为第二个结构继承了第一结构这有什么问题吗当然没有这是C语言中实现继承的基本手法。 现在假设第一个结构是第三方提供的第二个结构是你自己的。第三方提供的库是以DLL方式分发的DLL最大好处在于可以独立替换。但随着软件的进化问题可能就来了。 当第三方在第一个结构中增加了一个新的成员int k;编译好后把DLL给你你直接给了客户了。程序加载时不会有任何问题在运行逻辑可能完全改变原因是两个结构的内存布局重叠了。解决这类错误的唯一办法就是全部重新相关的代码。 解决这类错误的唯一办法就是重新编译全部代码。由此看来DLL并不见得可以动态替换如果你想了解更多相关内容建议阅读《COM本质论》。 9. 分配/释放不配对。 大家都知道malloc要和free配对使用new要和delete/delete[]配对使用重载了类new操作应该同时重载类的delete/delete[]操作。这些都是书上反复强调过的除非当时晕了头一般不会犯这样的低级错误。 而有时候我们却被蒙在鼓里两个代码看起来都是调用的free函数实际上却调用了不同的实现。比如在Win32下调试版与发布版单线程与多线程是不同的运行时库不同的运行时库使用的是不同的内存管理器。一不小心链接错了库那你就麻烦了。程序可能动则崩溃原因在于在一个内存管理器中分配的内存在另外一个内存管理器中释放时出现了问题。 10. 返回指向临时变量的指针 大家都知道栈里面的变量都是临时的。当前函数执行完成时相关的临时变量和参数都被清除了。不能把指向这些临时变量的指针返回给调用者这样的指针指向的数据是随机的会给程序造成不可预料的后果。 下面是个错误的例子 char* get_str(void) { char str[] {abcd}; return str; } intmain(intargc, char* argv[]) { char*p get_str(); printf(%s\n,p); return 0; } 下面这个例子没有问题大家知道为什么吗 char*get_str(void) { char*str {abcd}; return str; } intmain(intargc,char*argv[]) { char*p get_str(); printf(%s\n,p); return 0; } 11. 试图修改常量 在函数参数前加上const修饰符只是给编译器做类型检查用的编译器禁止修改这样的变量。但这并不是强制的你完全可以用强制类型转换绕过去一般也不会出什么错。 而全局常量和字符串用强制类型转换绕过去运行时仍然会出错。原因在于它们是是放在.rodata里面的而.rodata内存页面是不能修改的。试图对它们修改会引发内存错误。 下面这个程序在运行时会出错 intmain(intargc,char*argv[]) { char*p abcd; *p 1; return 0; } 12. 误解传值与传引用 在C/C中参数默认传递方式是传值的即在参数入栈时被拷贝一份。在函数里修改这些参数不会影响外面的调用者。如 #include stdlib.h #include stdio.h void get_str(char* p) { p malloc(sizeof(abcd)); strcpy(p, abcd); return; } int main(int argc, char* argv[]) { char* p NULL; get_str(p); printf(p%p\n, p); return 0; } 在main函数里p的值仍然是空值。 13. 重名符号。 无论是函数名还是变量名如果在不同的作用范围内重名自然没有问题。但如果两个符号的作用域有交集如全局变量和局部变量全局变量与全局变量之间重名的现象一定要坚决避免。gcc有一些隐式规则来决定处理同名变量的方式编译时可能没有任何警告和错误但结果通常并非你所期望的。 下面例子编译时就没有警告 t.c #includestdlib.h #includestdio.h intcount 0; intget_count(void) { return count; } main.c #include stdio.h extern int get_count(void); int count; int main(int argc, char* argv[]) { count 10; printf(get_count%d\n, get_count()); return 0; } 如果把main.c中的int count;修改为int count 0;gcc就会编辑出错说multiple definition of count。它的隐式规则比较奇妙吧所以还是不要依赖它为好。 14. 栈溢出。 我们在前面关于堆栈的一节讲过在PC上普通线程的栈空间也有十几M通常够用了定义大一点的临时变量不会有什么问题。 而在一些嵌入式中线程的栈空间可能只5K大小甚至小到只有256个字节。在这样的平台中栈溢出是最常用的错误之一。在编程时应该清楚自己平台的限制避免栈溢出的可能。 15. 误用sizeof。 尽管C/C通常是按值传递参数而数组则是例外在传递数组参数时数组退化为指针即按引用传递用sizeof是无法取得数组的大小的。 从下面这个例子可以看出 voidtest(charstr[20]) { printf(%s:size%d\n, __func__, sizeof(str)); } intmain(intargc,char*argv[]) { char str[20] {0}; test(str); printf(%s:size%d\n, __func__, sizeof(str)); return 0; } [rootlocalhost mm]# ./t.exe test:size4 main:size20 16. 字节对齐。 字节对齐主要目的是提高内存访问的效率。但在有的平台(如arm7)上就不光是效率问题了如果不对齐得到的数据是错误的。 所幸的是大多数情况下编译会保证全局变量和临时变量按正确的方式对齐。内存管理器会保证动态内存按正确的方式对齐。要注意的是在不同类型的变量之间转换时要小心如把char*强制转换为int*时要格外小心。 另外字节对齐也会造成结构大小的变化在程序内部用sizeof来取得结构的大小这就足够了。若数据要在不同的机器间传递时在通信协议中要规定对齐的方式避免对齐方式不一致引发的问题。 17. 字节顺序。 字节顺序历来是设计跨平台软件时头疼的问题。字节顺序是关于数据在物理内存中的布局的问题最常见的字节顺序有两种大端模式与小端模式。 大端模式是高位字节数据存放在低地址处低位字节数据存放在高地址处。 小端模式指低位字节数据存放在内存低地址处高位字节数据存放在内存高地址处 比如long n 0x11223344。 模式 第1个字节 第2个字节 第3个字节 第4个字节 大端模式 0x11 0x22 0x33 0x44 小端模式 0x44 0x33 0x22 0x11 在普通软件中字节顺序问题并不引人注目。而在开发与网络通信和数据交换有关的软件时字节顺序问题就要特殊注意了。 18. 多线程共享变量没有用valotile修饰。 在关于全局内存的一节中我们讲了valotile的作用它告诉编译器不要把变量优化到寄存器中。在开发多线程并发的软件时如果这些线程共享一些全局变量这些全局变量最好用valotile修饰。这样可以避免因为编译器优化而引起的错误这样的错误非常难查。 可能还有其它一些内存相关错误一时想不全面这里算是抛砖引玉吧希望各位高手补充。 进阶6 《POSA》中根据模式粒度把模式分为三类架构模式、设计模式和惯用手法。其中把分层模式、管道过滤器和微内核模式等归为架构模式把代理模式、命令模式和出版-订阅模式等归为设计模式而把引用计数等归为惯用手法。这三类模式间的界限比较模糊在特定的情况有的设计模式可以作为架构模式来用有的把架构模式也作为设计模式来用。 在通常情况下我们可以说架构模式、设计模式和惯用手法三者的重要性依次递减毕竟整体决策比局部决策的影响面更大。但是任何整体都是局部组成的局部的决策也会影响全局。惯用手法的影响虽然是局部的其作用仍然很重要。它不但在提高软件的质量方面而且在加快软件开发进度方面都有很大贡献。本文介绍几种关于内存的惯用手法这些手法对于老手来说已经习以为常对于新手来说则是必修秘技。 1. 预分配 假想我们实现了一个动态数组(vector)时当向其中增加元素时它会自动扩展(缩减)缓冲区的大小无需要调用者关心。扩展缓冲区的大小的原理都是一样的 l 先分配一块更大的缓冲区。 l 把数据从老的缓冲区拷贝到新的缓冲区。 l 释放老的缓冲区。 如果你使用realloc来实现内存管理器可能会做些优化如果老的缓冲区后面有连续的空闲空间它只需要简单的扩展老的缓冲区而跳过后面两个步骤。但在大多数情况下它都要通过上述三个步骤来完成扩展。 以此可见扩展缓冲区对调用者来说虽然是透明的但决不是免费的。它得付出相当大的时间代价以及由此产生的产生内存碎片问题。如果每次向vector中增加一个元素都要扩展缓冲区显然是不太合适的。 此时我们可以采用预分配机制每次扩展时不是需要多大就扩展多大而是预先分配一大块内存。这一大块可以供后面较长一段时间使用直到把这块内存全用完了再继续用同样的方式扩展。 预分配机制比较常见多见于一些带buffer的容器实现中比如像vector和string等。 2. 对象引用计数 在面向对象的系统中对象之间的协作关系非常复杂。所谓协作其实就调用对象的函数或者向对象发送消息但不管调用函数还是发送消息总是要通过某种方式知道目标对象才行。而最常见的做法就是保存目标对象的引用指针直接引用对象而不是拷贝对象提高了时间和空间上的效率也避免了拷贝对象的麻烦而且有的地方就是要对象共享才行。 对象被别人引用了但自己可能并不知道。此时麻烦就来了如果对象被释放了对该对象的引用就变成了野针系统随时可能因此而崩溃。不释放也不行因为那样会出现内存泄露。怎么办呢 此时我们可以采用对象引用计数对象有一个引用计数器不管谁要引用这个对象就要把对象的引用计数器加1如果不再该引用了就把对象的引用计数器减1。当对象的引用计数器被减为0时说明没有其它对象引用它该对象就可以安全的释放了。这样对象的生命周期就得到了有效的管理。 对象引用计数运用相当广泛。像在COM和glib里都是作为对象系统的基本设施之一。即使在像JAVA和C#等现代语言中对象引用计数也是非常重要的它是实现垃圾回收GC的基本手段之一。 代码示例: (atlcom.h: CcomObject) STDMETHOD_(ULONG,AddRef)() {returnInternalAddRef();} STDMETHOD_(ULONG,Release)() { ULONG l InternalRelease(); if (l 0) delete this; return l; } 3. 写时拷贝(COW) OS内核创建子进程的过程是最常见而且最有效的COW例子创建子进程时子进程要继承父进程内存空间中的数据。但继承之后两者各自有独立的内存空间修改各自的数据不会互相影响。 要做到这一点最简单的办法就是直接把父进程的内存空间拷贝一份。这样做可行但问题在于拷贝内容太多无论是时间还是空间上的开销都让人无法接受。况且在大多数情况下子进程只会使用少数继承过来的数据而且多数是读取只有少量是修改也就说大部分拷贝的动作白做了。怎么办呢 此时可以采用写时拷贝(COW)COW代表Copy on Write。最初的拷贝只是个假象并不是真正的拷贝只是把引用计数加1并设置适当的标志。如果双方都只是读取这些数据那好办直接读就行了。而任何一方要修改时为了不影响另外一方它要把数据拷贝一份然后修改拷贝的这一份。也就是说在修改数据时拷贝动作才真正发生。 当然在真正拷贝的时候你可以选择只拷贝修改的那一部分或者拷贝全部数据。在上面的例子中由于内存通常是按页面来管理的拷贝时只拷贝相关的页面而不是拷贝整个内存空间。 写时拷贝(COW)对性能上的贡献很大差不多任何带MMU的OS都会采用。当然它不限于内核空间在用户空间也可以使用比如像一些String类的实现也采用了这种方法。 代码示例(MFC:strcore.cpp) 拷贝时只是增加引用计数 CString::CString(constCStringstringSrc) { ASSERT(stringSrc.GetData()-nRefs! 0); if (stringSrc.GetData()-nRefs 0) { ASSERT(stringSrc.GetData() ! _afxDataNil); m_pchData stringSrc.m_pchData; InterlockedIncrement(GetData()-nRefs); } else { Init(); *this stringSrc.m_pchData; } } 修改前才拷贝 voidCString::MakeUpper() { CopyBeforeWrite(); _tcsupr(m_pchData); } voidCString::MakeLower() { CopyBeforeWrite(); _tcslwr(m_pchData); } 拷贝动作 voidCString::CopyBeforeWrite() { if (GetData()-nRefs 1) { CStringData*pData GetData(); Release(); AllocBuffer(pData-nDataLength); memcpy(m_pchData,pData-data(), (pData-nDataLength1)*sizeof(TCHAR)); } ASSERT(GetData()-nRefs 1); } 4. 固定大小分配 频繁的分配大量小块内存是内存管理器的挑战之一。 首先是空间利用率上的问题由于内存管理本身的需要一些辅助内存假设每块内存需要8字节用作辅助内存那么即使只要分配4个字节这样的小块内存仍然要浪费8字节内存。一块小内存不要紧若存在大量小块内存所浪费的空间就可观了。 其次是内存碎片问题频繁分配大量小块内存很容易造成内存碎片问题。这不但降低内存管理器的效率同时由于这些内存不连续虽然空闲却无法使用。 此时可以采用固定大小分配这种方式通常也叫做缓冲池(pool)分配。缓冲池(pool)先分配一块或者多块连续的大块内存把它们分成N块大小相等的小块内存然后进行二次分配。由于这些小块内存大小是固定的管理大开销非常小往往只要一个标识位用于标识该单元是否空闲或者甚至不需要任何标识位。另外缓冲池(pool)中所有这些小块内存分布在一块或者几块连接内存上所以不会有内存碎片问题。 固定大小分配运用比较广泛差不多所有的内存管理器都用这种方法来对付小块内存比如glibc、STLPort和linux的slab等。 5. 会话缓冲池分配(Session Pool) 服务器要长时间运行内存泄露是它的威胁之一任何小概率的内存泄露都可能会累积到具有破坏性的程度。从它们的运行模式来看它们总是不断的重复某个过程而在这个过程中又要分配大量(次数)内存。 比如像WEB服务器它不断的处理HTTP请求我们把一次HTTP请求称为一次会话。一次会话要经过很多阶段在这个过程要做各种处理要多次分配内存。由于处理比较复杂分配内存的地方又比较多内存泄露可以说防不甚防。 针对这种情况我们可以采用会话缓冲池分配。它基于多次分配一次释放的策略在过程开始时创建会话缓冲池(Session Pool)这个过程中所有内存分配都通过会话缓冲池(Session Pool)来分配当这个过程完成时销毁掉会话缓冲池(Session Pool)即释放这个过程中所分配的全部内存。 因为只需要释放一次内存泄露的可能大大降低。会话缓冲池分配并不是太常见apache采用的这种用法。后来自己用过两次感觉效果不错。 当然还有其一些内存惯用手法如cache等这里不再多说。上述部分手法在《实时设计模式》里有详细的描述大家可以参考一下。 进阶7 调试手段及原理 知其然也知其所以然是我们《大内高手》系列一贯做法本文亦是如此。这里我不打算讲解如何使用boundschecker、purify、valgrind或者gdb使用这些工具非常简单讲解它们只是多此一举。相反我们要研究一下这些工具的实现原理。 本文将从应用程序、编译器和调试器三个层次来讲解在不同的层次有不同的方法这些方法有各自己的长处和局限。了解这些知识一方面满足一下新手的好奇心另一方面也可能有用得着的时候。 从应用程序的角度 最好的情况是从设计到编码都扎扎实实的避免把错误引入到程序中来这才是解决问题的根本之道。问题在于理想情况并不存在现实中存在着大量有内存错误的程序如果内存错误很容易避免JAVA/C#的优势将不会那么突出了。 对于内存错误应用程序自己能做的非常有限。但由于这类内存错误非常典型所占比例非常大所付出的努力与所得的回报相比是非常划算的仍然值得研究。 前面我们讲了堆里面的内存是由内存管理器管理的。从应用程序的角度来看我们能做到的就是打内存管理器的主意。其实原理很简单 对付内存泄露。重载内存管理函数在分配时把这块内存的记录到一个链表中在释放时从链表中删除吧在程序退出时检查链表是否为空如果不为空则说明有内存泄露否则说明没有泄露。当然为了查出是哪里的泄露在链表还要记录是谁分配的通常记录文件名和行号就行了。 对付内存越界/野指针。对这两者我们只能检查一些典型的情况对其它一些情况无能为力但效果仍然不错。其方法如下(源于《Comparing and contrasting the runtime error detection technologies》) l 首尾在加保护边界值 Header Leading guard(0xFC) User data(0xEB) Tailing guard(0xFC) 在内存分配时内存管理器按如上结构填充分配出来的内存。其中Header是管理器自己用的前后各有几个字节的guard数据它们的值是固定的。当内存释放时内存管理器检查这些guard数据是否被修改如果被修改说明有写越界。 它的工作机制注定了有它的局限性:只能检查写越界不能检查读越界而且只能检查连续性的写越界对于跳跃性的写越界无能为力。 l 填充空闲内存 空闲内存(0xDD) 内存被释放之后它的内容填充成固定的值。这样从指针指向的内存的数据可以大致判断这个指针是否是野指针。 它同样有它的局限程序要主动判断才行。如果野指针指向的内存立即被重新分配了它又被填充成前面那个结构这时也无法检查出来。 从编译器的角度 boundschecker和purify的实现都可以归于编译器一级。前者采用一种称为CTI(compile-time instrumentation)的技术。VC的编译不是要分几个阶段吗boundschecker在预处理和编译两个阶段之间对源文件进行修改。它对所有内存分配释放、内存读写、指针赋值和指针计算等所有内存相关的操作进行分析并插入自己的代码。比如 Before if (m_hsession) gblHandles-ReleaseUserHandle( m_hsession ); if (m_dberr) delete m_dberr; After if (m_hsession) { _Insight_stack_call(0); gblHandles-ReleaseUserHandle(m_hsession); _Insight_after_call(); } _Insight_ptra_check(1994, (void **) m_dberr, (void *) m_dberr); if (m_dberr) { _Insight_deletea(1994, (void **) m_dberr, (void *) m_dberr, 0); delete m_dberr; } Purify则采用一种称为OCI(object code insertion)的技术。不同的是它对可执行文件的每条指令进行分析找出所有内存分配释放、内存读写、指针赋值和指针计算等所有内存相关的操作用自己的指令代替原始的指令。 boundschecker和purify是商业软件它们的实现是保密的甚至拥有专利的无法对其研究只能找一些皮毛性的介绍。无论是CTI还是OCI这样的名称多少有些神秘感。其实它们的实现原理并不复杂通过对valgrind和gcc的bounds checker扩展进行一些粗浅的研究我们可以知道它们的大致原理。 gcc的bounds checker基本上可以与boundschecker对应起来都是对源代码进行修改以达到控制内存操作功能如malloc/free等内存管理函数、memcpy/strcpy/memset等内存读取函数和指针运算等。Valgrind则与Purify类似都是通过对目标代码进行修改来达到同样的目的。 Valgrind对可执行文件进行修改所以不需要重新编译程序。但它并不是在执行前对可执行文件和所有相关的共享库进行一次性修改而是和应用程序在同一个进程中运行动态的修改即将执行的下一段代码。 Valgrind是插件式设计的。Core部分负责对应用程序的整体控制并把即将修改的代码转换成一种中间格式这种格式类似于RISC指令然后把中间代码传给插件。插件根据要求对中间代码修改然后把修改后的结果交给core。core接下来把修改后的中间代码转换成原始的x86指令并执行它。 由此可见无论是boundschecker、purify、gcc的bounds checker还是Valgrind修改源代码也罢修改二进制也罢都是代码进行修改。究竟要修改什么修改成什么样子呢别急下面我们就要来介绍 管理所有内存块。无论是堆、栈还是全局变量只要有指针引用它它就被记录到一个全局表中。记录的信息包括内存块的起始地址和大小等。要做到这一点并不难对于在堆里分配的动态内存可以通过重载内存管理函数来实现。对于全局变量等静态内存可以从符号表中得到这些信息。 拦截所有的指针计算。对于指针进行乘除等运算通常意义不大最常见运算是对指针加减一个偏移量如p、ppn、pa[n]等。所有这些有意义的指针操作都要受到检查。不再是由一条简单的汇编指令来完成而是由一个函数来完成。 有了以上两点保证要检查内存错误就非常容易了比如要检查p是否有效首先在全局表中查找p指向的内存块如果没有找到说明p是野指针。如果找到了再检查p1是否在这块内存范围内如果不是那就是越界访问否则是正常的了。怎么样简单吧无论是全局内存、堆还是栈无论是读还是写无一能够逃过出工具的法眼。 代码赏析(源于tcc) 对指针运算进行检查 void*__bound_ptr_add(void*p,int offset) { unsigned long addr (unsigned long)p; BoundEntry *e; #ifdefined(BOUND_DEBUG) printf(add: 0x%x %d\n, (int)p,offset); #endif e __bound_t1[addr (BOUND_T2_BITS BOUND_T3_BITS)]; e (BoundEntry*)((char*)e ((addr (BOUND_T3_BITS- BOUND_E_BITS)) ((BOUND_T2_SIZE- 1) BOUND_E_BITS))); addr - e-start; if (addr e-size) { e __bound_find_region(e,p); addr (unsigned long)p- e-start; } addr offset; if (addr e-size) return INVALID_POINTER; return p offset; } staticvoid __bound_check(constvoid *p,size_t size) { if (size 0) return; p __bound_ptr_add((void*)p,size); if (p INVALID_POINTER) bound_error(invalid pointer); } 重载内存管理函数 void*__bound_malloc(size_tsize,const void *caller) { void *ptr; ptr libc_malloc(size 1); if (!ptr) return NULL; __bound_new_region(ptr,size); return ptr; } void__bound_free(void*ptr,const void *caller) { if (ptr NULL) return; if (__bound_delete_region(ptr) ! 0) bound_error(freeing invalid region); libc_free(ptr); } 重载内存操作函数 void*__bound_memcpy(void*dst,const void *src,size_t size) { __bound_check(dst,size); __bound_check(src,size); if (src dst src dst size) bound_error(overlapping regions in memcpy()); return memcpy(dst,src,size); } 从调试器的角度 现在有OS的支持实现一个调试器变得非常简单至少原理不再神秘。这里我们简要介绍一下win32和linux中的调试器实现原理。 在Win32下实现调试器主要通过两个函数WaitForDebugEvent和ContinueDebugEvent。下面是一个调试器的基本模型(源于:《Debugging Applications for Microsoft .NET and Microsoft Windows》) voidmain ( void ) { CreateProcess ( ..., DEBUG_ONLY_THIS_PROCESS,... ) ; while ( 1 WaitForDebugEvent( ... ) ) { if ( EXIT_PROCESS ) { break ; } ContinueDebugEvent ( ... ) ; } } 由调试器起动被调试的进程并指定DEBUG_ONLY_THIS_PROCESS标志。按Win32下事件驱动的一贯原则由被调试的进程主动上报调试事件调试器然后做相应的处理。 在linux下实现调试器只要一个函数就行了ptrace。下面是个简单示例(源于《Playing with ptrace》)。 #includesys/ptrace.h #includesys/types.h #includesys/wait.h #includeunistd.h #includelinux/user.h intmain(intargc,char *argv[]) { pid_ttraced_process; struct user_regs_struct regs; long ins; if(argc! 2) { printf(Usage: %s pid to be traced\n, argv[0],argv[1]); exit(1); } traced_process atoi(argv[1]); ptrace(PTRACE_ATTACH,traced_process, NULL,NULL); wait(NULL); ptrace(PTRACE_GETREGS,traced_process, NULL, regs); ins ptrace(PTRACE_PEEKTEXT, traced_process, regs.eip,NULL); printf(EIP: %lx Instruction executed: %lx\n, regs.eip,ins); ptrace(PTRACE_DETACH,traced_process, NULL,NULL); return 0; } 由于篇幅有限这里对于调试器的实现不作深入讨论主要是给新手指一个方向。以后若有时间再写个专题来介绍linux下的调试器和ptrace本身的实现方法。
