bin

对堆操作的是由堆管理器(ptmalloc2)来实现的,而不是操作系统内核。因为程序每次申请或者释放堆时都需要进行系统调用,系统调用的开销巨大,当频繁进行堆操作时,就会严重影响程序的性能

概述

我们曾经说过,用户释放掉的 chunk 不会马上归还给系统,ptmalloc 会统一管理 heap 和 mmap 映射区域中的空闲的 chunk。当用户再一次请求分配内存时,ptmalloc 分配器会试图在空闲的 chunk 中挑选一块合适的给用户。这样可以避免频繁的系统调用,降低内存分配的开销。

在具体的实现中,ptmalloc 采用分箱式方法对空闲的 chunk 进行管理。首先,它会根据空闲的 chunk 的大小以及使用状态将 chunk 初步分为 4 类:fast bins,small bins,large bins,unsorted bin。每类中仍然有更细的划分,相似大小的 chunk 会用双向链表链接起来。也就是说,在每类 bin 的内部仍然会有多个互不相关的链表来保存不同大小的 chunk。

申请堆块的本质

堆管理器 ptmalloc2 主要是通过 malloc/free 函数来分配和释放内存块。

ptmalloc2 的作用通俗的讲就是相当于一个”中间商”,在程序想要申请向系统申请堆空间时,这里的 ptmalloc2 就会申请一块很大的空间,并根据算法从这些内存中把空间真正的分配给程序。

简单点说就是下面这个图中的情况:

bin

free 函数和 bins

bins 这个概念是与内存回收相关的,也就是堆管理器会根据用户已经申请到的内存空间大小进行释放,来决定放入哪类 bins 当作去。bins 直接翻译过来就是”垃圾桶”的意思,所以在系统在决定使用哪个 bins 时可以看作为”垃圾的分类”。

free 函数的使用是和 bins 的分配息息相关的。用一个简单的例子来理解一下 free 函数的实现原理。

代码如下:

#include <stdlib.h>
#include <string.h>

int main(){

        char *p;

        p = malloc(10);

        memcpy(p,"Hello",5);
        free(p);
        return 0;
}
  • 程序将 “Hello” 字符串复制到申请到的堆内存空间中。

编译后用 gdb 调试,在 call memcpy 处下一个断点,单步后将 “Hello” 复制到堆块中

bin

继续使用 x/32gx 0x602010-0x10 命令查看堆块情况

bin

继续单步 n,执行 free 函数之后,查看堆块情况

bin

这里可以看出原本堆块中存储的内容已经被清空,然后查看一下 main_arena 的值,发现其中 +0x8 的偏移处,存储了指向已经 free 了的指针(指向头部,而不是 user data)

小总结

所以调用 free 函数以后程序做了两件事:
1.清空此堆块的 user data
2.将此堆块的指针存储到 main_arena 中了(或是 fast bin 中)

fast bin

顾名思义,就是为了快速重新分配回内存而存在的一个结构。

fastbin所包含chunk的大小为16 Bytes, 24 Bytes, 32 Bytes,, 80 Bytes。当分配一块较小的内存(mem<=64 Bytes)时,会首先检查对应大小的fastbin中是否包含未被使用的chunk,如果存在则直接将其从fastbin中移除并返回;否则通过其他方式(剪切top chunk)得到一块符合大小要求的chunk并返回。

引用一张图:

这里的横向排列的就是 main_arene(fast bin)的内存地址

假如此时 0x0804a000 处的堆块(实际堆块中的 size 字段要减去 PREV_INUSE 字段值 1,)已经被 free 了,那么他就会被存储在表示 40 bytes 的 fast bin 的内存地址里

注意:这里把指针和地址区别开。地址存储的是指针,64 位的指针占 8 个字节。

假设我们现在还是以 64 位下的 malloc(10) 为例子。

根据前面那个 free 函数的例子,查看 main_arena 地址中的指针值我们可以看出来,+0x8 偏移处才是指向 malloc(10) 的堆块的指针(这个堆块分配后的 user data 实际大小是 16 字节)

gdb-peda$ x/2gx &main_arena                           (16 bytes 的链表头)
0x7ffff7dd3760 <main_arena>:    0x0000000000000000    0x0000000000602000

所以这个 16 字节的堆块的指针会被插入属于他的这个链表队列中,也就是如下的情况。

所以这也就印证了在 main_arena 中分别表示 16 Bytes, 24 Bytes, 32 Bytes, … , 80 Bytes 的内存地址中分别存储着已经 free 的而且满足这个大小的 chunk的指针。

fast bin 的特性

1.使用单链表来维护释放的堆块
也就是和上图一样,从main_arena 到 free 第一个块的地方是采用单链表形式进行存储的,若还有 free 掉的堆块,则这个堆块的 fk 指针域就会指针前一个堆块。

如下图所示,此时就是一个单链表结构

2.采用后进先出的方式维护链表(类似于栈的结构)
当程序需要重新 malloc 内存并且需要从fastbin 中挑选堆块时,会选择后面新加入的堆块拿来先进行内存分配

如上图,如果程序重新请求和上面的堆块大小一样时候(malloc),堆管理器就会直接使用 fast bin 里的堆块。

这里的话也就是直接使用第二次释放的这个堆块,然后将这个堆块从链表中移除,接着根据堆块的 fk 指针找到这个堆块,此时 main_arena 就指向了这里。也就是恢复到了上面第一个图中的情况。

small bin

顾名思义,这个是一个 small chunk ,满足的内存空间比 fast bin 大一点。

如果程序请求的内存范围不在 fast bin 的范围内,就会考虑small bin。简单点说就是大于 80 Bytes 小于某一个值时,就会选择他。

unsorted bin

当 fast bin、small bin 中的 chunk 都不能满足用户请求 chunk 大小时,堆管理器就会考虑使用 unsorted bin 。它会在分配 large chunk 之前对堆中碎片 chunk 进行合并,以便减少堆中的碎片。
unsorted bin 与 fast bin 不同,他使用双向链表对 chunk 进行连接

unsorted 的字面意思就是”不可回收”的意思,可以看作将不可回收的垃圾(不满足能够进行内存分配的堆块)都放到这个”垃圾桶”中。

参考

本文章首发在 网安wangan.com 网站上。

上一篇 下一篇
讨论数量: 0
只看当前版本


暂无话题~