堆栈认知——堆简介

参考：Linux笔记–堆简介
地址：https://qingmu.blog.csdn.net/article/details/119510863

1、前言

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

平台	堆管理机制
dlmalloc	General purpose allocator
ptmalloc2	glibc
jemalloc	FreeBSD and Firefox
tcmalloc	Google
libumem	Solaris

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

2、堆的由来

• Linux中早期的堆分配与回收由Doug Lea 实现。 但是它在并行处理多线程的时候，会共享进程的堆内存空间。因此，为了安全性，一个线程使用堆时，会进行加锁。

• 然而，与此同时，加锁会导致其他线程无法使用堆，降低了内存分配和回收的高效性。同时，如果多线程使用时，没能正确控制，也有可能引起内存分配和回收的正确性。

• Wolfram Gloger 在Doug Lea 的基础上进行改进使其支持多线程，这个堆分配器就是ptmalloc。在glibc-2.3.x.之后，glibc中集成了ptmalloc2。

1、只有当真正访问一个地址的时候，系统才会建立虚拟页面与物理页面的映射关系。

2、所以虽然操作系统已经给程序分配了很大的一块内存，
但是这块内存其实只是虚拟内存。只有当用户使用到相应的内存时，
系统才会真正分配物理内存给用户使用。

3、Linux中堆简介

• 目前Linux标准发行版中使用的堆分配器是glibc中的堆分配器：ptmalloc2。ptmalloc2主要是通过malloc/free函数来分配和释放内存块。

• 需要注意的是， 在内存的分配与使用过程中，Linux有这样的一个基本内存管理思想：

4、堆分类

4.1、请求堆

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

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

4.2、释放堆

管理用户所释放的内存。一般来说，用户释放的内存并不是直接返还给操作系统的，而是由堆管理器进行管理。这些释放的内存可以来响应用户新申请的内存的请求。
通俗的说就是我们的free或者delete等释放内存的操作函数。

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

• 我们在申请与释放内存的函数中，无论是malloc还是free函数，一般都会经常的使用，但是他们并不是真正与系统交互的函数。

• 这些函数背后的系统调用主要是(s)brk函数以及mmap，unmmap函数。

具体流程如下图所示：

• 对于堆的操作，操作系统提供了brk函数，我们可以通过增加brk的大小来向操作系统申请内存。

• 初始时，堆得起始地址start_brk以及堆的当前末尾brk指向的地址。根据是否开启ALSR（地址随机化）保护时，两者的具体位置会有所不同。

• 不开启ALSR保护时，start_brk以及brk会指向data/bss段的结尾。

• 开启ALSR保护时，start_brk以及brk也会指向同一位置，只是这个位置是在data/bss段的结尾后的随机偏移处。

可参考下图：

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;
}

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

让其走完一个malloc走完，看一看：

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

接着往下看，走完printf：

我们发现printf也会创建堆块，为了存放标准输入标准输出的，咱们接着往下走，到给p,q,r赋值之后：

堆中的fd和bk都赋值为了我们赋值的东西。

再接着我们free掉p，再看一下堆的情况：

他的fd和bk已经被改变了，其值为libc中的地址，我们在把q给free掉：

我们会发现q的bk已经指向了q这个堆块的地址了，而q这个堆的fd就变成了p这个堆的地址了，他们被ptmalloc组成了链表形成了bin链。