Linux笔记--堆简介

我不是女神ヾ 2022-09-03 14:18 120阅读 0赞

### Linux笔记--堆简介 ###

*  1、前言
 *  2、堆的由来
 *  3、Linux中堆简介
 *  4、堆分类
 *  4.1、请求堆
 *  4.2、释放堆
 *  5、内存分配背后的系统调用
 *  6、堆相关数据结构
 *  7、堆的申请
 *  8、调试验证

# 1、前言 #

当前针对各大平台主要有如下几种堆内存管理机制：

<table> 
 <thead> 
  <tr> 
   <th>平台</th> 
   <th>堆管理机制</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>dlmalloc</td> 
   <td>General purpose allocator</td> 
  </tr> 
  <tr> 
   <td>ptmalloc2</td> 
   <td>glibc</td> 
  </tr> 
  <tr> 
   <td>jemalloc</td> 
   <td>FreeBSD and Firefox</td> 
  </tr> 
  <tr> 
   <td>tcmalloc</td> 
   <td>Google</td> 
  </tr> 
  <tr> 
   <td>libumem</td> 
   <td>Solaris</td> 
  </tr> 
 </tbody> 
</table>

**在本文中我们主要说的是Linux中glibc的堆管理机制。**

# 2、堆的由来 #

*  Linux中早期的堆分配与回收由Doug Lea 实现。 但是它在并行处理多线程的时候，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。
 *  然而，与此同时，加锁会导致其他线程无法使用堆，降低了内存分配和回收的高效性。同时，如果多线程使用时，没能正确控制，也有可能引起内存分配和回收的正确性。
 *  Wolfram Gloger 在Doug Lea 的基础上进行改进使其支持多线程，这个堆分配器就是ptmalloc。**在glibc-2.3.x.之后，glibc中集成了ptmalloc2**。

# 3、Linux中堆简介 #

*  目前Linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。**ptmalloc2主要是通过malloc/free函数来分配和释放内存块**。
 *  需要注意的是， 在内存的分配与使用过程中，Linux有这样的一个基本内存管理思想：

1、只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。
    
    2、所以虽然操作系统已经给程序分配了很大的一块内存，
    但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，
    系统才会真正分配物理内存给用户使用。

# 4、堆分类 #

# 4.1、请求堆 #

*  相应用户的申请内存请求，向操作系统申请内存，然后将其返回给用户程序。同时，为了保持内存管理的高效性，内存一般都会预先分配一块很大的连续的内存(这块很大的内存称之为top\_chunk)，然后让堆管理器通过某种算法管理这块内存。只有当出现堆空间不足的情况，堆管理器才会再次与操作系统交互。

通俗的说就是我们的malloc或者new等申请内存的操作函数。

# 4.2、释放堆 #

*  管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。

通俗的说就是我们的free或者delete等释放内存的操作函数。

# 5、内存分配背后的系统调用 #

*  我们在申请与释放内存的函数中，无论是malloc还是free函数，一般都会经常的使用，但是他们并不是真正与系统交互的函数。
 *  这些函数背后的系统调用主要是(s)brk函数以及mmap，unmmap函数。

具体流程如下图所示：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70]

*  对于堆的操作，操作系统提供了brk函数，我们可以通过增加brk的大小来向操作系统申请内存。
 *  初始时，堆得起始地址start\_brk以及堆的当前末尾brk指向的地址。根据是否开启ALSR（地址随机化）保护时，两者的具体位置会有所不同。
 *  **不开启ALSR保护时，start\_brk以及brk会指向data/bss段的结尾。**
 *  **开启ALSR保护时，start\_brk以及brk也会指向同一位置，只是这个位置是在data/bss段的结尾后的随机偏移处。**

可参考下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 1]

# 6、堆相关数据结构 #

*  堆的操作是十分的复杂的，那么在glibc内部必然也有精心设计的数据结构（链表）来管理它，与堆相应的数据结构主要分为：

宏观结构：
    	1、包含堆的宏观信息，可以通过这些数据结构索引堆的基本信息
    	2、主要是堆块之间的链接
    	
    微观结构：
    	1、用于处理堆分配与回收的内存块
    	2、主要还是怎么处理堆的分配与回收中的内存块
    	3、malloc & free

# 7、堆的申请 #

*  在程序的执行中，我们由malloc申请的内存称之为chunk。这块内存在ptmalloc内部用malloc\_chunk 结构体来表示。当程序申请的chunk被free后，会被加入到空闲管理列表中，这个列表被称之为binlist。
 *  无论一个chunk的大小如何，处于分配状态还是释放状态，他们都使用一个统一的结构体。
 *  虽然他们都使用同一个数据结构，但是根据是否被释放，他们的表现形式会不一样。

malloc\_chunk 的具体形式如下：

struct malloc_chunk
    { 
    	INTERNAL_SIZE_T  prev_size;
    	INTERNAL_SIZE_T  size;
    	struct malloc_chunk *fd;
    	struct malloc_chunk *bk;
    	struct malloc_chunk *fd_nextsize;
    	struct malloc_chunk *bk_nextsize;
    }

我们由malloc申请一块0x100的内存的时候，这块内存在ptmalloc内部用malloc\_chunk来表示，但是他的大小并不是0x100的大小，还得加上我们操作不了的prev\_size和size大小，一般为0x10。

参数详解：

*  size

1、他是一个标志位
    
    2、该字段的低三个比特对chunk的大小没有影响，他们从低到高分别表示NON_MAIN_ARENA，记录
       当前chunk是否不属于主线程，1表示不属于，0表示属于。
       
    3、IS_MAPPED ,记录当前chunk是否有mmap分配的。
    
    4、PREV_INUSE，记录前一个chunk块是否被分配。一般来说，堆中的第一个被分配的内存块的size字段的P位
       都会被置位1，以便于防止访问前面的非法内存。当一个chunk的size的P位为0时，我们能通过pre_size字
       段来获取上一个chunk的大小以及地址。这也方便进行空闲chunk之间的合并。
       A|M|P

*  fd，bk

1、chunk处于分配状态时，从fd字段开始是用户数据。chunk空闲时，会被添加到空闲的管理列表中（binlist），其字段的含义是指向下一个（非物理相邻）空闲的chunk。
    
    2、bk指向上一个（非物理相邻）空闲chunk
    
    3、通过fd和bk可以将空闲的chunk块加入到空闲的chunk块链表进行统一管理

*  fd\_nextsize bk\_nextsize

1、也是同样只有chunk空闲的时候才可以使用，不过其用于较大的chunk（large chunk）
    
    2、fd_nextsize指向前一个与当前chunk大小不用的第一个空闲块，不包含bin的头指针
    
    3、bk_nextsize指向后一个与当前chunk大小不用的第一个空闲块，包含bin的头指针
    
    4、一般空闲的large chunk 在fd的遍历顺序中按照由大到小顺序排列。这样可以避免在寻找合适
      chunk时挨个遍历

# 8、调试验证 #

我们使用gdb调试验证一下

调试的C代码如下：

#include<stdio.h>
    #include<malloc.h>
    #include<unistd.h>
    #include<string.h>
    int main(){ 
    	int size = 0x100;
    	void *p = malloc(size);
    	void *junk = malloc(size);
    	void *q = malloc(size);
    	void *r = malloc(size);
    	printf("p:0x%x\n",p);
    	printf("q:0x%x\n",q);
    	printf("r:0x%x\n",r);
    	strcpy(p,"aaaaaaaabbbbbbbb");
    	strcpy(q,"ccccccccdddddddd");
    	strcpy(r,"eeeeeeeeffffffff");
    	sleep(0);
    	free(p);
    	sleep(0);
    	free(q);
    	sleep(0);
    // q = malloc(0x600);
    // sleep(0);
    	return 0;
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 2]

可以看到在程序起来后并没有堆的任何信息，本来我们也没申请嘛，咱们接着往下调

让其走完一个malloc走完，看一看：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 3]

这里我们申请的是0x100的大小，真是大小却是273（0x111），因为加上了我们不可操作的prev\_size和size的大小。

接着往下看，走完printf：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 4]

我们发现printf也会创建堆块，为了存放标准输入标准输出的，咱们接着往下走，到给p,q,r赋值之后：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 5]  
堆中的fd和bk都赋值为了我们赋值的东西。

再接着我们free掉p，再看一下堆的情况：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 6]  
他的fd和bk已经被改变了，其值为libc中的地址，我们在把q给free掉：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 7]  
我们会发现q的bk已经指向了q这个堆块的地址了，而q这个堆的fd就变成了p这个堆的地址了，他们被ptmalloc组成了链表形成了bin链。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70]: /images/20220829/218ccaaa5ca440448df2ae3515c0b035.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 1]: /images/20220829/869e437d2a6344079628c1b171c96685.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 2]: /images/20220829/6b66c868a1914383a79e4e4e2f3cca05.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 3]: /images/20220829/f7d8be8068114bbab963984ca94cfe63.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 4]: /images/20220829/2588e502c8644a9a984f78fae250955e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 5]: /images/20220829/9bea5eec3b444091ad0e596ce888edd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 6]: /images/20220829/91913aeb27e1490da19ed738f240a44a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTMwOTkxNg_size_16_color_FFFFFF_t_70 7]: /images/20220829/424544b535704f4587fd64fd6607980a.png