heap

2025-02-15

1. what is heap?

heap其实指的是程序当中动态分配的内存空间
其用途在于灵活的控制程序当中的内存大小。常见的使用例子是:游戏中NPC们的可变长度列表

1.1 古早的动态分配:mmap

mmap其实是最初的动态分配的雏形,它允许程序根据需要申请/释放内存,且内存长期存在,不会随函数结束就释放。
但是mmap的缺点也有:1、mmap申请/释放的内存大小必须是4096字节的整数倍,不够灵活;2、mmap申请/释放内存速度非常慢,因为涉及到系统调用,陷入内核

1.2 更聪明的做法: 维护mmap得到的内存,按需取用

如果我们先用mmap得到一块内存,将这块内存管理起来,按需求分配,这样在需求小于一定值的时候,不需要进行系统调用,方便快捷!
这个思路直接导致Dynamic Allocators诞生
不同系统使用的Dynamic Allocators版本也不一样:

General Purpose:
Doug Lea (pictured) releases dlmalloc into public domain in 1987.

Linux:
ptmalloc (Posix Thread aware fork of dlmalloc)

FreeBSD:
jemalloc (also used in Firefox, Android)

Windows:
Segment Heap, NT Heap

Kernel allocators:
kmalloc (Linux kernel memory allocator)
kalloc (iOS kernel memory allocator)

1.3 ptmalloc

本篇文章中描述全都是ptmalloc相关特性,不同的动态分配器机制不同,请不要混淆
大部分动态分配器(当然包括ptmalloc)都提供了如下功能:

1. malloc() - allocate some memory
2. free() - free a prior allocated chunk

And some auxiliary functions:
3. realloc() - change the size of an allocation
4. calloc() - allocate and zero-out memory

1.3.1 ptmalloc工作原理

2. dangers

3. tcache

4. Chunks and Metadata

5. Metadata Corruption

6. Safe-Linking