malloc笔记
glibc malloc (aka ptmalloc2)
resource:
http://gee.cs.oswego.edu/dl/html/malloc.html
malloc/malloc.c from http://ftp.gnu.org/gnu/glibc/glibc-2.15.tar.gz
基本结构:
struct malloc_chunk {
INTERNAL_SIZE_T prev_size; /* Size of previous chunk (if free). */
INTERNAL_SIZE_T size; /* Size in bytes, including overhead. */
struct malloc_chunk* fd; /* double links -- used only if free. */
struct malloc_chunk* bk;
/* Only used for large blocks: pointer to next larger size. */
struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
struct malloc_chunk* bk_nextsize;
};
细节：
- 已分配的chunk: `boundary tag'方法来管理内存.
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk, if free | | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk, in bytes |M|P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | User data starts here... . . . . (malloc_usable_size() bytes) . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
"chunk" 由malloc 代码使用, "mem" 是返回给用户的，"nextchunk" 是下一连续的块,
chunk 总是双字对齐的,所以mem也是双字对齐.
- 未分配的chunk: circular doubly-linked lists
chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Size of previous chunk | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `head:' | Size of chunk, in bytes |P| mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Forward pointer to next chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Back pointer to previous chunk in list | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ | Unused space (may be 0 bytes long) . . . . | nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ `foot:' | Size of chunk, in bytes | +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
注意到当前chunk 的`foot' 实际上是代表下一块的`prev_size'.
由于chunk size是双字的倍数, size的最低三比特分别用来表示:
P (PREV_INUSE) (最低比特):
1 前一块被分配, 此时pre_size未被使用,从而相当于给前一块,故overhead是1字(而不是2字)
0 未分配, 此时size的前一字表示前一块的大小
M (IS_MMAPPED): 由mmap 分配
NON_MAIN_ARENA: 每thread 都有一个arena linked-list, 第一个是main_arena
(malloc_state 结构, 详细见代码)
算法主要内部结构：
1. regular bins
An array of free chunks headers, 每个bin是双链表, size-order(small bins 相同
大小), 先进先出原则(freed chunk 放到最前面, 分配从最后开始)，128个bins:
64 bins of size 8
32 bins of size 64
16 bins of size 512
8 bins of size 4096
4 bins of size 32768
2 bins of size 262144
1 bin of size what's left
对于前64 bins, 即size < 512, 每个bin是同大小的块集合, 称之为smallbins;
其余为largebins, 且已排序.
布局：16 - 24 - 32 -..- 512 - 576 - 640 ---
2. unsorted chunks
所有split剩下块，返回块的集合.
在这些块放入regular bins之前malloc会有一次尝试对其分配
3. top
Top-most available chunk. (Wilderness preservation)
如果bins分配失败，从这里分配，否则尝试mmap, 再者通过MORECORE申请内存，
增加top.
see sbrk(2)
4. binmap
加快largebin的索引
5. fastbin
An array of lists 最近被释放小块(MAX_FAST_SIZE）, single-link, LIFO
malloc：
exact-fit, last_remaider chunk, best-fit. (Locality preservation)
malloc -> public_mALLOc -> _int_malloc
1. fastbins if any, returns
2. smallbins if any, returns
3. largebins if has fastchunks, consolidate fastchunks
4. unsorted-bin 寻找exact-fit 或 last_remaider chunk, if any returns
否则将块放入regular bins(largebins need to be sorted)
5. largebins if any, split or exhaust, and returns
6. best-fit if any, split or exhaust, and returns
7. top if available split and returns
8. if has fastchunks, consolidate, then go to step 4
9. calls sYSMALLOc,
sYSMALLOc:
1. mmap if condition is satisfied, if ok then returns
2. not main_arena, try grow_heap and new_heap, otherwise try mmap if mmap is not tried
3. main_arena, MORECORE, otherwise mmap and do some adjustments and fenceposts.
4. finally, do the allocation.
free:
free -> public_fREe -> _int_free
1. if <fastsize, put into fastbin
2. if mmapped, munmap
3. if not mmapped, consolidate backward/forward, put into the unsorted bin or top
4. if freeing a large space, possibly consolidate fastchunks, sYSTRIm
For other similiar routines, says realloc/mallopt, see the implementations for the
details.
