malloc内存分配原理

【malloc内存分配原理】一、malloc的工作机制
它有一个将可用的内存块连接为一个长长的列表的所谓空闲链表。

调用malloc函数时,它沿连接表寻找一个大到足以满足用户请求所需要的内存块。然后,将该内存块一分为二(一块的大小与用户请求的大小相等,另一块的大小就是剩下的字节)。接下来,将分配给用户的那块内存传给用户,并将剩下的那块(如果有的话)返回到连接表上。
调用free函数时,它将用户释放的内存块连接到空闲链上。到最后,空闲链会被切成很多的小内存片段,如果这时用户申请一个大的内存片段,那么空闲链上可能没有可以满足用户要求的片段了。于是,malloc函数请求延时,并开始在空闲链上翻箱倒柜地检查各内存片段,对它们进行整理,将相邻的小空闲块合并成较大的内存块。

glibc维护了不止一个不定长的内存块链表,而是好几个,每一个这种链表负责一个大小范围,这种做法有效减少了分配大内存时的遍历开销
glibc另外的策略就是不止维护一类空闲链表,而是另外再维护一个缓冲链表和一个高速缓冲链表。
在分配的时候首先在高速缓存中查找,失败之后再在空闲链表查找,如果找到的内存块比较大,那么将切割之后的剩余内存块插入到缓存链表。
如果空闲链表查找失败那么就往缓存链表中查找. 如果还是没有合适的空闲块,就向内存申请比请求数更大的内存块,然后把剩下的内存放入链表中。
在对内存块进行了 free 调用之后,我们需要做的是诸如将它们标记为未被使用的等事情,并且,在调用 malloc 时,我们要能够定位未被使用的内存块。因此, malloc返回的每块内存的起始处首先要有这个结构:

struct mem_control_block { int is_available; int size; };

  • 1
  • 2
  • 3
  • 4
这就解释了,为什么在程序中free之后,但是堆的内存还是没有释放。
二、sbrk & brk
malloc所申请的内存主要从Heap区域分配(本文不考虑通过mmap申请大块内存的情况)。
进程所面对的虚拟内存地址空间,只有按页映射到物理内存地址,才能真正使用。受物理存储容量限制,整个堆虚拟内存空间不可能全部映射到实际的物理内存。Linux对堆的管理示意如下:

Linux维护一个break指针,这个指针指向堆空间的某个地址。从堆起始地址到break之间的地址空间为映射好的,可以供进程访问;而从break往上,是未映射的地址空间,如果访问这段空间则程序会报错。
由上文知道,要增加一个进程实际的可用堆大小,就需要将break指针向高地址移动。Linux通过brk和sbrk系统调用操作break指针。两个系统调用的原型如下:
int brk(void *addr); void *sbrk(intptr_t increment);

  • 1
  • 2
brk将break指针直接设置为某个地址,而sbrk将break从当前位置移动increment所指定的增量。brk在执行成功时返回0,否则返回-1并设置errno为ENOMEM;sbrk成功时返回break移动之前所指向的地址,否则返回(void *)-1。
一个小技巧是,如果将increment设置为0,则可以获得当前break的地址。
另外需要注意的是,由于Linux是按页进行内存映射的,所以如果break被设置为没有按页大小对齐,则系统实际上会在最后映射一个完整的页,从而实际已映射的内存空间比break指向的地方要大一些。但是使用break之后的地址是很危险的(尽管也许break之后确实有一小块可用内存地址)。

注意大部份UNIX虚拟内存的使用是只增不减的。
CODE:malloc(32 * 1024) --->; sbrk += 32 * 1024 free()--->; sbrk 不减少。 但如如果再来一次 malloc(32 * 1024) ---->; sbrk 也不增,使用原有空间. 但对于LINUX来说它是要以内存的最大数收缩的; CODE: a = malloc(32 * 1024) -->; sbrk += 32 * 1024 b = malloc(32 * 1024) -->; sbrk += 32 * 1024 if(****){ free(b); --->; sbrk -= 32 * 1024; } else{ free(a); --->; sbrk 不减少。只是多了个空洞. }

    推荐阅读