本文共 8747 字,大约阅读时间需要 29 分钟。
首先看一下linux 下的4G的虚拟地址空间的分布
linux系统向用户提供申请的内存有brk(sbrk)和mmap函数。下面我们先来了解一下这几个函数#includeint brk(void *addr); void *sbrk(intptr_t increment);
#includevoid *mmap(void *addr, size_t length, int prot, int flags, int fd, off_t offset);int munmap(void *addr, size_t length)
ptmalloc 实现了 malloc(),free()以及一组其它的函数. 以提供动态内存管理的支持。分配器处在用户程序和内核之间,它响应用户的分配请求,向操作系统申请内存,然后将其返回给用户程序,为了保持高效的分配,分配器一般都会预先分配一块大于用户请求的内存,并通过某种算法管理这块内存。来满足用户的内存分配要求,用户释放掉的内存也并不是立即就返回给操作系统,相反,分配器会管理这些被释放掉的空闲空间,以应对用户以后的内存分配要求。也就是说,分配器不但要管理已分配的内存块,还需要管理空闲的内存块,当响应用户分配要求时,分配器会首先在空闲空间中寻找一块合适的内存给用户,在空闲空间中找不到的情况下才分配一块新的内存。为实现一个高效的分配器,需要考虑很多的因素。比如,分配器本身管理内存块所占用的内存空间必须很小,分配算法必须要足够的快。
在 Doug Lea实现的内存分配器中只有一个主分配区(main arena),每次分配内存都必须对主分配区加锁,分配完成后释放锁,在 SMP 多线程环境下,对主分配区的锁的争用很激烈,严重影响了 malloc 的分配效率。
每个进程只有一个主分配区,但可能存在多个非主分配区,ptmalloc 根据系统对分配的争用情况动态增加非主分配区的数量,分配区的数量一旦增加,就不会再减少了。主分配区可以访问进程的 heap 区域和 mmap 映射区域,也就是说主分配区可以使用 sbrk 和 mmap向操作系统申请虚拟内存。而非主分配区只能访问进程的 mmap 映射区域。
当某一线程需要调用 malloc()分配内存空间时,该线程先查看线程私有变量中是否已经存在一个分配区,如果存在,尝试对该分配区加锁,如果加锁成功,使用该分配区分配内存,如果失败,该线程搜索循环链表试图获得一个没有加锁的分配区。如果所有的分配区都已经加锁,那么 malloc()会开辟一个新的分配区,把该分配区加入到全局分配区循环链表并加锁,然后使用该分配区进行分配内存操作。在释放操作中,线程同样试图获得待释放内存块所在分配区的锁,如果该分配区正在被别的线程使用,则需要等待直到其他线程释放该分配区的互斥锁之后才可以进行释放操作。
不管内存是在哪里被分配的,用什么方法分配,用户请求分配的空间在 ptmalloc 中都使
用一个 chunk 来表示。用户调用 free()函数释放掉的内存也并不是立即就归还给操作系统,相反,它们也会被表示为一个 chunk,ptmalloc 使用特定的数据结构来管理这些空闲的 chunk。 说明: chunk 指针指向一个 chunk 的开始,一个 chunk 中包含了用户请求的内存区域和相关的控制信息。图中的 mem 指针才是真正返回给用户的内存指针。用户 free 掉的内存并不是都会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk,当用户进行下一次分配请求时,ptmalloc 会首先试图在空闲的chunk 中挑选一块给用户,这样就避免了频繁的系统调用,降低了内存分配的开销。ptmalloc将相似大小的 chunk 用双向链表链接起来,这样的一个链表被称为一个 bin。Ptmalloc 一共维护了 128 个 bin,并使用一个数组来存储这些 bin(如下图所示)。
数组中的第一个为 unsorted bin,数组中从 2 开始编号的前 64 个 bin 称为 small bins,同一个small bin中的chunk具有相同的大小。两个相邻的small bin中的chunk大小相差8bytes。small bins 中的 chunk 按照最近使用顺序进行排列,最后释放的 chunk 被链接到链表的头部,而申请 chunk 是从链表尾部开始,这样,每一个 chunk 都有相同的机会被 ptmalloc 选中。Small bins 后面的 bin 被称作 large bins。large bins 中的每一个 bin 分别包含了一个给定范围内的 chunk,其中的 chunk 按大小序排列。相同大小的 chunk 同样按照最近使用顺序排列。ptmalloc 使用“smallest-first,best-fit”原则在空闲 large bins 中查找合适的 chunk一般的情况是,程序在运行时会经常需要申请和释放一些较小的内存空间。当分配器合
并了相邻的几个小的 chunk 之后,也许马上就会有另一个小块内存的请求,这样分配器又需要从大的空闲内存中切分出一块,这样无疑是比较低效的,故而,ptmalloc 中在分配过程中引入了 fast bins,不大于 max_fast (默认值为 64B)的 chunk 被释放后,首先会被放到 fast bins 中,fast bins 中的 chunk 并不改变它的使用标志 P。这样也就无法将它们合并,当需要给用户分配的 chunk 小于或等于 max_fast 时,ptmalloc 首先会在 fast bins 中查找相应的空闲块,然后才会去查找bins中的空闲chunk。在某个特定的时候,ptmalloc会遍历fast bins中的chunk,将相邻的空闲 chunk 进行合并,并将合并后的 chunk 加入 unsorted bin 中,然后再将 unsorted bin 里的 chunk 加入 bins 中.unsorted bin 的队列使用 bins 数组的第一个,如果被用户释放的 chunk 大于 max_fast,或者 fast bins 中的空闲 chunk 合并后,这些 chunk 首先会被放到 unsorted bin 队列中,在进行 malloc 操作的时候,如果在 fast bins 中没有找到合适的 chunk,则 ptmalloc 会先在 unsorted bin 中查找合适的空闲 chunk,然后才查找 bins。如果 unsorted bin 不能满足分配要求。malloc便会将 unsorted bin 中的 chunk 加入 bins 中。然后再从 bins 中继续进行查找和分配过程。从这个过程可以看出来,unsorted bin 可以看做是 bins 的一个缓冲区,增加它只是为了加快分配的速度。
并不是所有的 chunk 都按照上面的方式来组织,实际上,有三种例外情况。Top chunk,mmaped chunk 和 last remainder,下面会分别介绍这三类特殊的 chunk。top chunk 对于主分配区和非主分配区是不一样的。对于非主分配区会预先从 mmap 区域分配一块较大的空闲内存模拟 sub-heap,通过管理 sub-heap 来响应用户的需求,因为内存是按地址从低向高进行分配的,在空闲内存的最高处,必然存在着一块空闲 chunk,叫做 top chunk。当 bins 和 fast bins 都不能满足分配需要的时候,ptmalloc 会设法在 top chunk 中分出一块内存给用户,如果 top chunk 本身不够大,分配程序会重新分配一个 sub-heap,并将 top chunk 迁移到新的 sub-heap 上,新的 sub-heap 与已有的 sub-heap 用单向链表连接起来,然后在新的 top chunk 上分配所需的内存以满足分配的需要,实际上,top chunk 在分配时总是在 fast bins 和 bins 之后被考虑,所以,不论 top chunk 有多大,它都不会被放到 fast bins 或者是 bins 中。Top chunk 的大小是随着分配和回收不停变换的,如果从 top chunk 分配内存会导致 top chunk 减小,如果回收的 chunk 恰好与 top chunk 相邻,那么这两个 chunk 就会合并成新的 top chunk,从而使 top chunk 变大。如果在 free 时回收的内存大于某个阈值,并且 top chunk 的大小也超过了收缩阈值,ptmalloc会收缩 sub-heap,如果 top-chunk 包含了整个 sub-heap,ptmalloc 会调用 munmap 把整个sub-heap 的内存返回给操作系统。由于主分配区是唯一能够映射进程 heap 区域的分配区,它可以通过 sbrk()来增大或是收缩进程 heap 的大小,ptmalloc 在开始时会预先分配一块较大的空闲内存(也就是所谓的 heap),主分配区的 top chunk 在第一次调用 malloc 时会分配一块(chunk_size + 128KB) align 4KB 大小的空间作为初始的 heap,用户从 top chunk 分配内存时,可以直接取出一块内存给用户。在回收内存时,回收的内存恰好与 top chunk 相邻则合并成新的 top chunk,当该次回收的空闲内存大小达到某个阈值,并且 top chunk 的大小也超过了收缩阈值,会执行内存收缩,减小 top chunk 的大小,但至少要保留一个页大小的空闲内存,从而把内存归还给操作系统。如果向主分配区的 top chunk 申请内存,而 top chunk 中没有空闲内存,ptmalloc会调用 sbrk()将的进程 heap 的边界 brk 上移,然后修改 top chunk 的大小。
当需要分配的 chunk 足够大,而且 fast bins 和 bins 都不能满足要求,甚至 top chunk 本
身也不能满足分配需求时,ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间。这样分配的 chunk 在被 free 时将直接解除映射,于是就将内存归还给了操作系统,再次对这样的内存区的引用将导致 segmentation fault 错误。这样的 chunk 也不会包含在任何bin 中Last remainder 是另外一种特殊的 chunk,就像 top chunk 和 mmaped chunk 一样,不会在任何 bins 中找到这种 chunk。当需要分配一个 small chunk,但在 small bins 中找不到合适的 chunk,如果 last remainder chunk 的大小大于所需的 small chunk 大小,last remainder chunk被分裂成两个 chunk,其中一个 chunk 返回给用户,另一个 chunk 变成新的 last remainder chuk。
分配算法概述,以 32 系统为例,64 位系统类似。
ptmalloc 的响应用户内存分配要求的具体步骤为:
free()函数同样首先需要获取分配区的锁,来保证线程安全。
判断传入的指针是否为 0,如果为 0,则什么都不做,直接 return。否则转下一步。
判断所需释放的 chunk 是否为 mmaped chunk,如果是,则调用 munmap()释放mmaped chunk,解除内存空间映射,该该空间不再有效。如果开启了 mmap 分配阈值的动态调整机制,并且当前回收的 chunk 大小大于 mmap 分配阈值,将 mmap分配阈值设置为该 chunk 的大小,将 mmap 收缩阈值设定为 mmap 分配阈值的 2倍,释放完成,否则跳到下一步。
判断 chunk 的大小和所处的位置,若 chunk_size <= max_fast,并且 chunk 并不位于heap 的顶部,也就是说并不与 top chunk 相邻,则转到下一步,否则跳到第 6步。(因为与 top chunk 相邻的小 chunk 也和 top chunk 进行合并,所以这里不仅需要判断大小,还需要判断相邻情况)
将 chunk 放到 fast bins 中,chunk 放入到 fast bins 中时,并不修改该 chunk 使用状态位 P。也不与相邻的 chunk 进行合并。只是放进去,如此而已。这一步做完之后释放便结束了,程序从 free()函数中返回。
判断前一个 chunk 是否处在使用中,如果前一个块也是空闲块,则合并。并转下一步。
判断当前释放 chunk 的下一个块是否为 top chunk,如果是,则转第 9 步,否则转下一步。
判断下一个 chunk 是否处在使用中,如果下一个 chunk 也是空闲的,则合并,并将合并后的 chunk 放到 unsorted bin 中。注意,这里合并的过程中,要更新 chunk的大小,以反映合并后的 chunk 的大小。并转到第 10 步。
如果执行到这一步,说明释放了一个与 top chunk 相邻的 chunk。则无论它有多大,都将它与 top chunk 合并,并更新 top chunk 的大小等信息。转下一步。
判断合并后的 chunk 的大小是否大于FASTBIN_CONSOLIDATION_THRESHOLD(默认64KB),如果是的话,则会触发进行 fast bins 的合并操作,fast bins 中的 chunk 将被遍历,并与相邻的空闲 chunk 进行合并,合并后的 chunk 会被放到 unsorted bin 中。fast bins 将变为空,操作完成之后转下一步。
判断 top chunk 的大小是否大于 mmap 收缩阈值(默认为 128KB),如果是的话,对于主分配区,则会试图归还 top chunk 中的一部分给操作系统。但是最先分配的128KB 空间是不会归还的,ptmalloc 会一直管理这部分内存,用于响应用户的分配请求;如果为非主分配区,会进行 sub-heap 收缩,将 top chunk 的一部分返回给操作系统,如果 top chunk 为整个 sub-heap,会把整个 sub-heap 还回给操作系统。做完这一步之后,释放结束,从 free() 函数退出。可以看出,收缩堆的条件是当前free 的 chunk 大小加上前后能合并 chunk 的大小大于 64k,并且要 top chunk 的大小要达到 mmap 收缩阈值,才有可能收缩堆。
转载地址:http://yanwi.baihongyu.com/