浅谈内存分配

Posted on | In | Visitors:

许多系统程序需要为动态数据结构分配额外内存，此类数据结构的大小在程序运行时才能确定。本文介绍下在堆或者堆栈上分配内存的函数

在堆上分配内存

概述

进程可以通过增加堆的大小来分配内存，所谓的堆是一段长度可变的连续虚拟内存，其位于进程的未初始化数据段和栈段之间（始于未初始化数据段末尾），从低地址向高地址增长，通常将堆的当前内存边界称为“program break”。最初时program break位于未初始化数据段末尾，与&end位置相同。在program break位置抬升后，程序可以访问新分配的区域内的任何内存地址，但此时物理内存页还没有分配，内核会在进程首次访问这些虚拟内存地址时自动分配物理内存页

函数介绍

malloc()和free()

1
2
3
#include<unistd.h>
int brk(void *end_data_segment);    //成功返回0出错返回-1
void *sbrk(intptr_t increment);    //成功返回新分配的内存地址，出错返回-1

系统调用brk()会将program break设置为参数end_data_segment所指定的位置。由于虚拟内存以页为单位进行内存分配，end_data_segment实际会四舍五入到下一个内存页的边界处

调用sbrk()会将program break在原有地址上增加参数increment的大小（intptr_t 即整数数据类型），如果program break增加（即调用成功），返回新分配的内存起始位置的指针。

1
2
3
#include<stdlib.h>
void *malloc(size_t size);    //成功返回分配的内存起始地址，出错返回NULL
void free(void *ptr);

malloc()返回类型为void*类型，故可以赋值给任意类型的C指针。其分配的内存块采用字节对齐方式（可参考本人另一篇博客），这样可以提高内存访问效率。

free()函数释放ptr参数所指向的内存块，该参数可以是malloc(),calloc(),realloc()函数返回的地址。一般情况下free()并不会降低program break的位置，而是将这块内存添加到空闲内存列表中，供后续的内存分配函数使用。如此之举，原因有三：

  • 一般释放的内存位于堆的中间位置，而非堆的顶部（言外之意，如果释放堆顶的内存，program break位置会下降），所以不可能改变program break的位置。
  • 可以最大限度的减少程序调用brk()的次数，虽然系统调用开销小，但也比较可观（因为只用调用brk才可能改变program break 的位置）
  • 没有必要，对分配大量内存的程序没什么帮助，因为它们通常是持有已分配内存或是反复释放和重新分配内存，而非释放所有内存后再持续运行一段时间。
    绝对不允许对ptr所指的空间释放大于一次，否则会引发未知错误，也就是说，鬼知道会发生什么…

malloc()和free()的实现

调用malloc()时，它首先会扫描之前由free()所释放的空闲内存列表，以求找到尺寸大于或等于要求的一块内存块。如果一个内存块的大小与要求的相当，则将其返回给调用者，如果太大，那么将其分割，将大小相当的一块返回给调用者的同时，把剩余的那块保留在空闲内存列表中。
如果找不到足够大的空闲内存块，那么malloc()会调用sbrk()以分配更多的内存。为减少对sbrk()的调用次数，malloc()不会只是严格按所需字节数来分配内存，而是以虚存页的大小的数倍来增加program break，并将超出的部分添加到空闲内存列表中。

当free()将空闲内存块置于空闲列表之上时，是如何知道空闲内存块的大小的呢？其实，当malloc()分配内存块时，会额外分配几个字节来记录这块内存的大小的整数值。该值位于内存块的起始处，而实际返回给调用者的内存地址位于该记录之后

当将内存块置于空闲内存列表时，free会使用内存块本身的空间来存放列表指针，将自身添加到列表中

在编写长期运行的程序时，如果需要反复分配内存，应当确保释放所有已使用完毕的内存，否则堆将稳步增长，直至抵达可用虚拟内存的上限，此后的分配内存操作将以失败告终，这种情况被称为“内存泄漏”

calloc()和realloc()

1
2
3
4
5
#include<stdlib.h>
void *calloc(size_t numitems,size_t size);   
 //成功返回内存起始位置地址，出错返回NULL
void *realloc(void *ptr,size_t size);
//成功返回内存起始位置地址，出错返回NULL

函数calloc()用于给一组相同对象分配内存，参数numitems指定对象数量，size指定每个对象的大小，与malloc()不同，calloc会将已分配的内存初始化为0
使用范例：

1
2
3
4
5
struct {...}myStruct;
struct myStruct *p;
p = calloc(1000,sizeof(struct myStruct));
if(p == NULL)
    exit(1);

realloc() 函数用来调整（通常是增加）一块内存的大小，而这块内存应是之前由malloc包中的函数所分配的。参数ptr指向需要调整的内存块的指针，参数size指定所需调整大小的期望值。调用成功返回调整后的内存块的地址，与调用前的内存地址可能不同。若realloc()增加了已分配内存块的大小，则不会对额外分配的字节进行初始化
使用calloc()和realloc()分配的内存应该用free()来释放

调用realloc(ptr,0)等效于在free(ptr)之后调用malloc(0)，若ptr为NULL，则realloc(NULL,size)相当于调用malloc(size)

通常情况下，当增大已分配内存时，realloc()会试图去合并在空闲列表中紧随其后且大小满足要求的内存块。若原内存块位于堆的顶部，那么realloc()将对堆空间进行扩展(这两种情况原地址与新地址相同)。如果位于堆的中间，且紧邻的内存块大小不足，realloc()会分配一块新内存，并将原有数据复制到新内存块中，（原地址与新地址不同，也是最常见情况），此举占用大量CPU资源,应尽量避免使用realloc()

在堆栈上分配内存

和malloc()函数包中的函数功能一样，alloca()也可以动态的分配内存，不顾不是从堆上分配，而是从堆栈上通过增加栈帧的大小来分配。因调用函数的栈帧位于堆栈的顶部，故帧的上方还有扩展空间，只需修改堆栈指针值即可。

1
2
#include<alloca.h>
void *alloca(size_t size);    //返回已分配内存块的指针

参数size指定在堆栈上分配的字节数。不需要（也不能）调用free()来释放由alloca()分配的内存，也不可能用realloc()调整alloca()分配的大小（一个堆操作，一个栈操作，这两根本就在不同的世界嘛！）。
调用alloca()造成堆栈溢出时程序无法预知，且不会收到一个NULL返回值（可能会收到一个SIGSEGV信号）。不能在一个函数的参数列表中调用alloca(),这会使alloca()分配的堆栈空间出现在函数参数的空间内（函数参数位于栈帧内的固定位置）

1
2
3
4
5
fun(x,alloca(size),z);    //WRONG!!!!
应该这样写：
void *y;
y = alloca(size);
fun(x,y,z);

使用alloca()来分配内存相对于malloc()有一定优势：1.alloca()分配内存的速度要快于malloc()，因为编译器将alloca()作为内联代码处理，并通过直接调整堆栈指针来实现，并且alloca()也不需要维护空闲内存列表。2.由alloca()分配的内存随栈帧的移除而自动释放

参考资料：
《linux/UNIX系统编程手册》(tlpi)