Heap堆管理机制 - SBH

CRT Strartup code

Importance

正确初始化C run-time library,即CRT

确保C++中静态对象的构造函数在正确的时机被调用

Entry-Point Symbol

使用一个 function name 作Entry-Point Symbol，指定startup code

The funtion must be defined with the __stdcall calling convention(公约)

  • mainCRTStartup

    控制台应用程序 Console

  • WinMainCRTStartup

    窗体应用程序 Windows

  • _DllMainCRTStartup

    动态链接库 Dll

Example - mainCRTStartup()

Code Abstract

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void mainCRTStartup(void) {
//...
int mainret;
if(!_heap_init(0)) // 1. heap初始化
__try{
  _ioinit(); //2. IO初始化  
  _acmdln = (char*)GetCommandLineA(); //3. 获取命令行参数
_aenvptr = (cahr*)__crtGetEnvironmentStringsA(); //4. 获取环境变量
_setargv(); //5. 字符串处理
_setenvp(); //6. 字符串处理
_cinit(); //7. data初始化
__initenv = _environ; //8. Main 
mainret = main(__argc,__argv,_environ); //8. Main 注意calling convention
exit(mainret); //9. Exit
  }
__eccept(...) {
//...
}
}

System heap management interface

HeapAlloc()

VirtualAlloc()

Heap堆管理机制 -VC6

Small Block Heap - SBH

小块堆管理机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//__sbh_threshpld 设置内存门限，所需要的分配的内存小于该值，使用SBH机制为其分配内存
//__sbh_threshpld = 3F8，i.e. 1016
//_ioinit()对内存的分配操作中，自下而上的调用中分配的内存在不断的膨胀,在base()这里还未分配8byte的cookie首尾
//共1024 1K
auto heap_alloc_base(...) {
    
//SBH堆管理机制
//从VirtualAlloc()取内存
if(size <= __sbh_threshold) {
  pvReturn = __sbh_alloc_block(size);
  if(pvReturn) return pvReturn;
}
    
//window提供的heap堆管理接口
//即调用HeapAlloc从_crtheap堆中取需要的内存
if(size==0) size=1;
size=(size+...)&~(...);
return HeapAlloc(_crtheap,0,size);
    
}

image-20210716152231050

Memory Mangement

先向操作系统申请1M的内存，取其中 1/32 = 32K 部分

再将32K分成8块4K的内存段，作为SBH内存管理的基本单元

Debug首部

用于标识已分配内存的一些状态

其中指针用于链接 Debug Heap 双向链表 ，使调试器掌握分配内存的状态

Debug Heap可以使物理上不连续的内存逻辑上有序

fill 部分为用户可见部分，其余部分用户不可见

image-20210716175659278

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
//内存块的标识符
#define _NORMAL_BLOCK 1 //用于应用程序的内存 / 用于APP的内存
#define _CRT_BLOCK 2 //用于CRT的内存

#define nNoMansLandSize 4
tydef struct _CrtMemBlockHeader {
struct __CrtMemBlockHeader* pBlockHeaderNext;
struct __CrtMemBlockHeader* pBlockHeaderPrev;
char* szFileNAME; //分配该区块代码所在的文件
int nLine; //分配该区块的代码所在文件代码行
size_t nDataSize;
int nBlockUse; //1 or 0 代表该内存的用途 CRT/APP
long lRequest;
unsigned char gap[nNoMansLandSize];
} _CrtMemBlockHeader;

Header结构

1
2
3
4
5
6
7
8
9
10
typedef unsigned int BITVEC;
typedef struct tagHeader {
 //32bit hign 与 32bit low 会组合为一组64bit
 BITVEC bitvEntryHi;
 BITVEC bitvEntryLo;
 BITVEC bitvCommit;

 void* pHeadData;
 struct tagRegion* pRegion;
}HEADER,*PHEADER;

_heap_init() 和 __sbh_heap_init()

CRT会先为自己建立一个**_crtheap**,然后从中分配SBH所需要的HEADERS,REGIONS作为管理之用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int __cdecl _heap_init (int mtflag) {
    
    //初始化 Big-bloc heap
    //建立一个_crtheap堆专门用于SBH堆管理
    if((_crtheap = HeapCreat(...))) {
        //失败处理
        return 0;
    }
    
    //初始化 Small-block heap
    if( __sbh_heap_init() == 0) {
        //失败处理
        HeapDestroy(_crtheap);
        return 0;
    }
}

int __cdecl __sbh_heap_init(void) {
    
    //从_crtheap中分配16个Header
    if(!(__sbh_pHeaderList = 
        HeapAlloc( _crtheap , 0 , 16*sizeof(HEADER) )
        )
      ){
        return FALSE;
    }
    
    //状态设置
    //...
    
    return TURE;
    
}

ioinit()

任何程序开始之前首次分配的内存大小为256byte，用于IO初始化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
//区分Debug模式的条件编译
#ifndef _DEBUG
//非debug模式下，分配的内存快无额外的debug首部
#define _malloc_crt malloc
//...
#else
//c++编译器提供的macro宏
#define _THISFILE __FILE__ //指明当前代码所在的文件,__LINE__还可指出是第几行
#define _malloc_crt(s) _malloc_dbg(s,_CRT_BLOCK,_THISFILE,__LINE__)
//...
#endif

void __cdecl _ioinit(void) {

 //...
 //内存分配
 //IOINFO_ARRAY_ELTS = 32
     //sizeof(ioinfo) = 8
    if(
        (pio = _malloc_crt(IOINFO_ARRAY_ELTS * sizeof(ioinfo))
      ) == NULL) {
        //..
    }
    //...
   
   }

heap_alloc_dbg()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
//...
blockSize = sizeof(_CrtMemBlockHeader) + nSize + nNoMansLandSize;
//...
pHead = (_CrtMemBlockHeader*)_heap _alloc_base(blockSize); //获取内存,并使用pHead指针临时指向

//设置Debug Heap
//将各heap内存块串为一个双向链表
//static  _CrtMemBlockHeader* pfirst
//static  _CrtMemBlockHeader* plast
if(pfirst) {
    pfirst -> pBlockHeaderPrev = pHead;
}else {
    plast = pHead;
}

pHead -> pBlockHeaderPrev = NULL;
pHead -> pBlockHeaderNext = pfirst;
//... Debug首部的其余6个属性的设置

pfirst = pHead;

//fill in gap
memset((void*)pHead->gap,_bNoMansLandFill,nNoMansLandSize);
memset((void*)( pbData(pHead) + nSize ),_bNoMansLandFill,nNoMansLandSize);
//fill data
memset((void*)pbData(pHead),_bCleanLandFill,nNoMansLandSize);

return (void*)pbData(pHead);

__sbh_alloc_block()

1
2
3
//BYTES_PER_PARA = 16
//添加cookie以及将内存大小调整到16的边界
sizeEntry = (intSize + 2*sizeof(int) + (BYTES_PER_PARA-1) &~ (BYTES_PER_PARA-1) )

__sbh_alloc_new_region()

Logic memory

REGION -> GROUP -> LISTHEAD -> ENTRY

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
typedef unsigned int BITVEC;
typedef struct tagRegion {
 //判断链表是否链接了区块，无法从空链表切割分配内存
 int indGroupUse;
 char cntRegionSize[64];
 //32组64bit的组合，组成一个64bit的变量
 BITVEC bitvEntryHi[32];
 BITVEC bitvEntryLo[32];

 struct tagGroup grpHeadList[32];
}REGION,*PREGION;

typedef struct tagGroup {
 int cntEntries;

 //自上而下第一个双向链表链接(维护)的区块大小范围为0~16B
 //第64个即63号双向链表链接(维护)的区块大小范围为>1KB and < 8KB
 // sign = Esize / 16 - 1
struct tagListHead listHead[64];
}GROUP,*PGROUP;

 typedef struct tagListHead {

 //用于组织管理大小相同的内存块
 //将大小相同的内存块串成双向链表
 struct tagEntry* pEntryNext;
  struct tagEntry* pEntryPrev;

}LISTHEAD,*PLISTHEAD;

 typedef struct tagEntry {

 int sizeFont;
 struct tagEntry* pEntryNext;
  struct tagEntry* pEntryPrev;

}ENTRY,*PENTRY;

image-20210717083105261

Physics memory
1
2
3
4
5
p = VirtualAlloc(0,1M,MEM_RESERVE,...);
//向操作系统申请1M的内存
VirtualAlloc(addr,32K,MEM_RESERVE,...)
//取其中 1/32 = 32K 部分
//再将32K分成8块小内存，通过 LISTHEADER 管理 4K=4096 的小内存段

image-20210717083750367

强制分隔字段

每段大小虽然为4k = 4096 但是其中8byte为强制分隔字段

在所有分配的内存全部回收时候，防止SBH内存管理的基本单元被合并

每个基本单元逻辑上由双向链表链接不连续，但是实际物理上是连续的内存

保留字段

4096 - 8 = 4088 所以需保留字段确保内存为16的整数倍

可分配内存

而只有4080可以用于分配内存因为有8byte的cookie字段指明长度

注意:

  1. 只要是可分配内存/空闲内存，一定有两个临时指针，该指针用于LISTHEAD登记管理
  2. 临时指针内存段被分配后，会被覆盖，不在用于LISTHEAD登记管理

image-20210717092728471

Memory Allocate

  1. 从由各LISTHEAD管理的所有空闲内存中找出与申请内存最接近的空闲内存进行分配
  2. 从空闲内存中切割分配用户所需要的的内存，并通过逐级的回溯最终返回给用户指向该分配内存的指针pUser

pUser当前所指位置并不是当前分配后的pUser的实际指向，该指针会最终移动到该位置

  1. 重新登记管理剩余内存的LISTHEAD

    ec0 / 10h > 1K 所以仍由63号LISTHEAD管理该剩余内存区块

image-20210717103245856

For the first time distribution

初始时仅由最后一个LISTHEAD管理8段基本单元，其余LISTHEAD为空

因此首次分配内存时申请的130h内存由最后一个listhead组织管理分配，而不是对应的 130h / 10h = 19 18号链表链接

image-20210717103332926

Memory recycle

free(pCurrnet);

Merge

每一次回收都将与该回收内存紧邻的空闲内存(cookie尾末位为0)进行合并

下一空闲内存的cookie头 = pCurrnet - 4 + 300

上一空闲内存的cookie尾 = pCurrnet - 8

通过判断cookie的首尾末位状态来判断是否进行合并

若只有cookie头或cookie尾，则只能朝反向单向检测内存块的状态

image-20210717175327399

Re-Register

重新登记管理该回收内存的LISTHEAD,将该内存”插入”到对应LISTHEAD链接的双向链表中

更新空闲内存的临时指针指向，将空闲内存”挂”到对应LISTHEAD管理的双向链表上

image-20210717104533693

b0内存分配出去后，该部分剩余190h内存需要重新又相应双向链表管理

image-20210717105611949

Verification

Blocks allocated befor main()

在进入main()之前，CRT已经进行一些内存分配的工作，例如环境变量的内存分配

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void mainCRTStartup(void) {
//...
    verification
  _acmdln = (char*)GetCommandLineA(); //3. 获取命令行参数
  //_acmdln为argv格式
  
  _aenvptr = (cahr*)__crtGetEnvironmentStringsA(); //4. 获取所有环境变量
  
    _setargv(); //5. 字符串处理
  //为_acmdln分配内存
  _setenvp(); //6. 字符串处理
  //为pointer table分配内存
    //10个字符串与10个指针(连续)，共11次内存分配操作
  
  __initenv = _environ;
  // _environ是指指向环境变量字符串的指针
  //环境变量字符串使用指针指向
  //因此 _environ 为pointer to pointer table
  
  mainret = main(__argc,__argv,_environ);
  //calling convention约束下，这里的参数无所谓有无
  //...
  }
    }

例一VC6操作系统有10个环境变量需要分配内存

image-20210718090713992

  1. 以argv格式获取命令行参数

    argv格式(假设argc为n)

    • 连续n个指针,指向n个字符串

    • 连续n个字符串，每个字符串以’/0’结束

    • \0结尾，4byte

  2. 使用一大段内存获取操作系统中的所有环境变量

  3. 通过10个独立的字符串内存段和1个指针内存段来管理所有环境变量

    每个内存段添加debug首部等便于调试器管理

  4. 设置命令行参数内存

image-20210718092728650

Heap堆管理机制 -VC10

VC10下并没有取消SBH堆管理机制，而是内置到了HeapAlloc操作系统下

1
hMyHeap = HeapCreate(0,4096,0); // 例中 hMyHeap=39000

LISTHEAD

hMyHeap指向的地址中，在offset = 178 即 39178地址处，有128 对 LISTHEAD指针 4byte为一个指针

每对LISTHEAD指针分别以双向链表登记，管理着不同的状态的内存

free[0]: >1K

初始登记管理所有基本单元

free[127]: 0~8 byte

初始两个指针都指向自己，表示该LISTHEAD连接的链表为空，无法分配内存

基本单元

cookie首部

8byte

不仅记录本区块的内存长度，还记录前一个区块的内存长度

长度单位为8byte

free[size] 可与 LISTHEAD 直接建立管理对应关系

首区块 前一区块内存长度字段值为 0303 有特殊意义

debug 尾部

16byte

image-20210718101857874

Verification

1
lp = HeapAlloc(hMyheap,HEAP_ZERO_MEMORY,1024);

image-20210718103359627