pwn

glibc堆管理一些思考

一些想说给自己的话

思考过程：学会了怎么用->想知道它的原理->为什么它要这样实现，而不是那样。

一样的东西，每次重新看它都会不一样的体会，这是因为你还不够了解它，如果想要了解某个东西，无非两种方法，重复使用它或者了解它的本质。而我曾经陷入了尴尬的境遇，没有重复使用，也没有究其本质，我以为我懂了，却只是停留在思考过程的第二个阶段。学会的东西始终会忘记，即使你写下来，以后再来看的时候，也需要很多时间去重新理解，因为万事万物并不是独立存在，而是通过一根根细微的线，相互关联。我现在能理解当前的东西，随着时间的流失，这些线会断，而重新面对的时候又需要把线连接起来，费事费力。

那么又如何去面对这种问题呢？取决于你的抽象能力，把当前理解的事物尽可能抽象成独立的东西。例如php里面的数组，其实这一种很抽象的结构，基本结构里面没有这样的数组类型。但是说到php数组的时候，大多数情况下我也不会去考虑它底层是怎么实现的。

终其事物的本质，本质似乎是一个无穷远点，应该去找到一个合适的位置，位置以下都抽象成一个点，当做事物的本质，已然足够，善。

ptmalloc 分配器模型值得了解的点

  • ptmalloc封装的是系统调用，避免频繁的系统调用的中断
  • ptmalloc会带来最大影响是内存碎片，最坏的情况到最坏可能导致OOM
  • 还有很多像ptmalloc一样的分配器模型，它们区别在于metadata 和 算法。
  • ptmalloc的算法原理是 边界标记: 赋予了chunk之间合并和从任意块遍历其他块的能力 装箱结构: bins查找顺序smallest-first, best-fit顺序。

ptmalloc里面会考虑的一些情况： - 局部性：在CPU访问寄存器时，无论是存取数据抑或存取指令，都趋于聚集在一片连续的区域中，这就被称为局部性原理。 时间局部性（temporal locality） ：被引用过一次的存储器位置在未来会被多次引用（通常在循环中）。
空间局部性（spatial locality）：如果一个存储器的位置被引用，那么将来他附近的位置也会被引用。 ptmalloc局部性应用在fastbin的FILO结构上，充分考虑局部性，在一定周期类密集的操作，减少cpu 的cache miss。 - 荒野区域： 相当于topchunk的位置，最靠近边界的区域，topchunk的大小可以看做是最大的chunk,因为sbrk可以扩张，对它的处理应该放在最后。 - 内存映射：何时用mmap，用mmap带来的开销，内置threshold size，超过该值就应该使用mmap，同时arena可以设置threshold size不仅考虑sbrk的扩展，也需要考虑其收缩的过程。 - 缓存：chunk在合并和分割的过程需要成本，这里衍生了两种缓存方式 延迟合并: fastbin 预先分割 - Lookaside: 由于metadata里面固定字段损耗，在某些时刻是不能忽视的，比如一个分配最小的chunk为16字节，但是程序需要大量使用大小为8字节的node，那么这个时候的损耗就达到了%100. 这个时候就需要设计一种没有metadata的方式，但是还要兼容以前的设计。这个时候唯一能做文章就是内存地址，划分一块特殊的内存出来。但是在ptmalloc并没有实现这种，因为无法很好的猜测用户使用的不同的内存块。在这一块更加鼓励应用自己构造一个简单的分配器，自己构造一个nodefreelist，然后使用malloc作为后备，类似malloc使用mmap和brk作为后备。

request2size 设计细节

这是一段_int_malloc里面根据用户请求计算真实大小的chunk的过程。 

1
2
3
4
#define request2size(req)                                         \
  (((req) + SIZE_SZ + MALLOC_ALIGN_MASK < MINSIZE)  ?             \
   MINSIZE :                                                      \
   ((req) + SIZE_SZ + MALLOC_ALIGN_MASK) & ~MALLOC_ALIGN_MASK)
我第一次看这个地方的时候， 其实有一点不理解为什么要这样写。如果按照我的理解应该是下面这么写： 
1
2
3
4
#define request2size(req) \
(((SIZE_SZ+(req)) <=MINSIZE) ? \
MINSIZE : \
((SIZE_SZ+(req)+ALLOC_ALIGN_MASK) & ~ ALLOC_ALIGN_MASK))
首先为什么是SIZE_SZ+(req)? 
1
2
`SIZE_SZ*2+(req)` //考虑虚拟地址上连续的下一个chunk的prev字段也可以用
`SIZE_SZ+(req)`
可以看到按照我的理解写的过程后面是一样，前面不太一样。应该是设计者的想法和我不太一致，我考虑了MINSIZE里面究竟多少可用。而设计者应该单纯的想用padding 固定长度，然后直接考虑对齐。究竟谁的代码要更好呢？

细细向来后者更好，可以复用SIZE_SZ+(req)+ALLOC_ALIGN_MASK，两段代码的判断意图不太一样。我的代码着眼于把MINSIZE这个位置分割出来。而设计者的代码却着眼于用SIZE_SZ+(req)+ALLOC_ALIGN_MASK一致计算会出现分叉的点。这种设计细节值得细细来品:)

fast_index最大为什么只是8？

在malloc_state中fastbins是一个大小为10的数组，理论上是可以存储10种不同size的chunk,且看下面片段： 

1
2
3
#define MAX_FAST_SIZE     (80 * SIZE_SZ / 4)
#define fastbin_index(sz) \
  ((((unsigned int) (sz)) >> (SIZE_SZ == 8 ? 4 : 3)) - 2)
无论是32位还是64位最后用MAX_FAST_SIZE计算出来的index都是8，那么似乎fastbins[9]并没有用到？如果按理论上计算： 
1
2
3
4
5
6
7
SIZE_SZ*2+1*SIZE_SZ*2
SIZE_SZ*2+2*SIZE_SZ*2
...
SIZE_SZ*2+10*SIZE_SZ*2

SIZE_SZ*2(1+10)
SIZE_SZ*21
而设计者直接指定了80，相比这其中，一定有其原因，可能是性能测试的时候80是一个标记线？超过80就失去了其fastbin cache的效果？但这里我产生了一个有意思的思考: 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
struct malloc_state {
    mutex_t mutex;
    int flags;
    mfastbinptr fastbinsY[10];
    mchunkptr top;
    mchunkptr last_remainder;
    mchunkptr bins[254];
    unsigned int binmap[4];
    struct malloc_state *next;
    struct malloc_state *next_free;
    size_t attached_threads;
    size_t system_mem;
    size_t max_system_mem;
}
看看arena的结构，其中bins[0]和bins[1]应该是unsorted_chunk的fd和bk,那么top的位置应该是该chunk的开始，如果考虑一点点设计“哲学”，这个地方也需要2*SIZE_SZ对齐,在32位是对齐的，但是64位并不是，所以我的思考并不是和设计者相契合的，这里我最终还是没有想清楚why，留下个一个问题，看日后能不能想个所以然。

ptmalloc 中metadata的演变

资料：

https://sourceware.org/glibc/wiki/MallocInternals glibc_wiki http://gee.cs.oswego.edu/dl/html/malloc.html ptmalloc具体细节