Linkers-Loaders-11

Linkers-Loaders-11

内存

程序的环境由:内存,运行库,系统调用组成。

我们在前面已经提到过了,大多数操作系统会将一部分内存挪用给内核使用,应用程序一般无法使用,一个 Linux 进程里的经典内存布局如下:

Linux进程地址空间分布

关于栈,我们其实已经相当熟悉了(陌生的可以去看汇编模块的过程调用篇,有对过程调用中栈的变化有说明)。

而在 C++ 里返回一个对象的时候,对象要经过2次拷贝构造函数的调用才可以完成返回对象的传递,1次拷贝到栈上的临时对象里,另一次把临时对象拷贝到存储返回值的对象里。

这样带来一个恶果,就是返回较大的对象时会有非常多的额外开销,因此 C++ 程序中避免返回对象,同时为了减小返回对象的开销,C++ 提出了返回值优化(Return Value Optimization, RVO)的技术,可以在某些场合减少对象的拷贝1次。如下:

1
2
3
4

cpp_obj re_test(){
return cpp_obj();
}

这时,构造一个 cpp_obj 对象会调用一次他的构造函数,在返回时会调用拷贝构造函数。c++的返回优化可以将这两部合并,直接构造在传出时使用的临时变量,减少一次复制的过程。

堆(Heap)是一块巨大的内存空间,常常占用整个虚拟空间的绝大部分,在这里,程序可以申请一块连续的内存空间,这块内存再程序主动放弃之前都会一直的有效。

我们常常使用 malloc() 分配空间,直到 free() 去释放它们之前,程序都可以自由的使用。

malloc() 是如何实现的?有一种做法是把进程的内存管理交给操作系统的内核去做,既然内核管理者进程的地址空间,那么它提供一个系统调用,让程序使用这个系统调用去申请内存就可以了。这是一个理论上可行的方法,但实践起来性能相当的差,程序每次需要申请或者释放内存的时候就需要系统调用,而系统调用的性能开销很大,这时就会极大的影响程序的性能。比较好的做法是程序向操作系统申请一块适当大小的堆空间,然后由程序自己管理这块空间。

进程堆管理

Linux 下进程堆的管理稍微有些复杂,它提供了两种堆空间的分配方式,即两个系统调用:一个是 brk() 系统调用,另外一个是 mmap()。

brk() 的实际作用就是设置进程数据段的结束地址,即它可以扩大或缩小数据段(Linux 下数据段和 BSS 一起统称数据段)。如果我们将数据段的结束地址向高地址移动,那么扩大的部分就可以被使用,把这块空间拿来作为堆空间是最常见做法之一。

mmap() 的作用就是向操作系统申请一段虚拟地址空间,这块虚拟地址空间可以映射到某一个文件(这也是这个系统调用的最初的作用),当你不将这块地址空间映射到某个文件时,我们又称这块空间为匿名(Anonymous)空间,匿名空间就拿来作堆空间。函数声明和官方文档解释如下:

void *mmap(void *addr, size_t length, int prot, int flags,int fd, off_t offset);

mmap() creates a new mapping in the virtual address space of the calling process. The starting address for
the new mapping is specified in addr. The length argument specifies the length of the mapping (which must be
greater than 0).

  If addr is NULL, then the kernel chooses the address at which to create the mapping; this is the most portable
  method of creating a new mapping.  If addr is not NULL, then the kernel takes it as  a  hint  about  where  to
  place  the  mapping;  on Linux, the mapping will be created at a nearby page boundary.  The address of the new
  mapping is returned as the result of the call.

brk()的文档看不懂就不贴了

  • prot/flags 用于设置申请的空间的权限(可读可写可执行),映射类型(文件,匿名)
  • 新的地址空间将会从一个页的边界开始(意思大概是会舍弃不够大小的一个页的剩余部分)

Glibc 的 malloc 函数是这样处理用户的空间请求的:如果小于 128KB,它会在现有的堆空间里按照堆分配算法分配一块空间出来并返回,对于大于 128KB 的请求来说,它会使用 mmap() 函数为它分配一块匿名空间,然后在这个匿名空间中为用户分配空间。

ps:我们注意一个点:分配内存都是对进程分配的,也就是说给我们正在运行的一个程序分配,当这个进程中止时,进程的相关资源(如进程的地址空间,物理内存,打开的文件,网络连接等)将会被操作系统关闭或回收,所以 malloc 申请的内存在程序结束后不会再存在。(这让我想起当时问c++老师和c老师的这个问题,老师很模糊的回答让我一度认为这样的空间会被一直占用直到内存断电)

堆内存分配算法

1. 空闲链表

空闲链表(Free List)就是将堆中各个空闲的块按照链表的方式连接起来,当用户申请空间时,遍历整个链表找到合适大小的块并将它拆分,释放空间时将它合并进入空闲链表。

一个链表的节点由空闲空间的开头,上一个空闲块的地址,下一个空闲块的地址组成,分配空间时找到大小合适的空闲块,将其分为两部分,一部分给用户,一部分作为新的空闲空间,将空闲链表中该位置节点的信息修改掉,如果刚好够,就删去这个点。

但是释放时就遇到一个问题,不知道块的大小,这时就需要一个额外字段(如用户要k分k+4,用多出来的4字节记录分配出去这一块的大小)来记录大小。当然,问题不只有这一个,一旦链表被破坏或者记录字段被修改,整个堆就无法正常的工作了。

2. 位图

针对空闲链表的弊端,人们提出了位图(Bitmap)方法,其核心思想就是将整个堆划分为大量的块(Block),每个块大小相同,当用户请求内存时总是分配整数个块的空间给用户,第一个块我们称为已分出去的头(Head),其余的称为分配区域的主体(Body),我们采取一个整数数组来记录块的使用情况,由于每个块只有头/空闲/主体3个状态,所以仅仅需要2位。

位图

位图为: (High)11 00 00 10 10 11 00 00 00 00 00 00 00 10 11(Low)

缺点同样很明显,如碎片内存会有很多,当位图很大时有可能失去Cache命中率高的优势

3. 对象池

对象池的思路很简单,如果每次分配的空间大小都是一样的,那么按照这个每次请求分配的大小作为一个单位,将堆空间划分为大量的小块,每次分一个出去。由于假定了每次请求都是一个固定的大小,所以可以快速满足请求。实现方法用空闲链表或者位图都可以。

实际上在现实的应用中,堆分配算法往往是采取多种算法复合而成的,比如对于 glibc 来说,它对于小于64字节的空间申请是采用类似对象池的方法,而对于大于512字节的空间采用的是最佳适配算法,在2者中间的采用上述方法的折中策略,对于大于 128KB 的申请,直接走 mmap() 向操作系统申请空间。

Glibc的分配方法

待更新,学习中……

Author

Ctwo

Posted on

2020-09-23

Updated on

2020-10-25

Licensed under

Comments