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;

};

未释放(分配)的堆块只使用prev_size和size
已经释放的堆块还会使用fd和bk字段，作为漏洞利用字段

所以我们可以画个图

使用中的堆

+-----+-----+
|prev_size  |
+-----------+
|size    | p|
+-----+-----+
|chunk(data)|
+-----+-----+

free掉的堆

+--------+--------+
|prev_size        |
+-----------------+
|size    |    p   |
+--------+--------+
|fd(next)|bk(prev)|
+--------+--------+
|chunk(data)      |
+--------+--------+

在glibc堆块中是8字节对齐的。为了简化内存的管理，堆块的大小总是8字节的倍数。这就表示size的最后3位可以是其他用途（正常情况下总是置0）。只有第一位对我们很重要(我们把后三位叫做p,那么这个很重要的就是p的最低位了)。如果这位置1，就表示前面的堆块在使用。如果没有置1，表示 前面 的堆块没有被使用。如果相关的内存被释放了，堆块就不会被使用（通过调用函数去释放）。

这个
注意是前面的堆块
所以要知道本堆块是否在使用，需要顺着指针找到下一堆块，看下一堆块size的标志位(不是prev_size)

prev_size 表示前一个chunk的size, 那么可以使用这个值来找到前一个chunk的开始

我有一个问题,这个前后是怎么分的…什么叫前,什么叫后

当前堆块释放后，下一堆块的size字段关键位会被清零。此外，prev_size字段会被设置为堆块释放状态(但好像是当p=0,这个prev_size才有意义)

被释放的堆块通过fd和bk连入一个双向链表中(据说还是一个环形的，首尾相接的链表,是的,这个在0day安全里看到了)
大概长这个样子,这个表win下他叫空表[FreeList],0day安全里面这样子叫他(下面来自win)

这部分内容切到Windows

Free|0]   -> ... 这个Free[0]比较特殊,连了介于1~512KB的空闲堆块,大小升序连接
Free|0]   <- ... 其他的连接的堆块连接的堆块大小为`Index * 8` byte

Free|1]   -> [8    ] -> [8    ]  -> [8    ] -> [8    ] -> Free[1]开头
Free|1]   <- [bytes] <- [bytes]  <- [bytes] <- [bytes] <- 来自Free[1]开头
...
Free|127] -> [1016 ] -> [1016 ] -> [1016 ] -> [1016 ] -> Free[127]开头
Free|127] <- [bytes] <- [bytes] <- [bytes] <- [bytes] <- 来自Free[127]开头

同时提到快表
这是windows为了加快堆的分配而采用的一种堆表,这类单向链表不会发生堆合并(其中空闲块块首被设置为占用)
也是有128条,只是其中的堆块采用单链表组织,其他和普通空表类似

对于堆块的分配,对于大小不同的块,有不同分配方式

• 小块: 快表分配 -> 普通空表分配 -> 堆缓存(我也不知道这个是啥)分配 -> 零号空表分配 -> NULL
• 大块: 堆缓存 -> 零号空表分配

• 巨块: 虚分配

• 堆块大小Size是包含块首在内的,如果我们请求32字节,则实际会分配32+8(块首大小)字节,但空表里的大小应该是data的大小,不包含表头

• 堆块的单位是8字节,不足8字节按照8字节分配

• 初始状态下,快表空表都为空,不能精确分配,所以使用次优块(好像有的地方叫尾块,有的地方叫顶块)

• 快表只会精确匹配,快表每一条只允许有4项

• 快表单恋,比较快,所以分配和释放优先用快表

都是书上看来的,我没有windows,暂时也不能试验

那么如果我的快表里只有4个16字节的块,然而我的空表里也只有16字节的,那么我需要8字节的时候,是要切割普通空表里的这个16字节的块嘛,还是顶块分配

欢迎切换回来到linux

上面的是说windows的情况,现在回到Linux里glibc的ptmalloc
然后在网上找到资料

下面来自资料

bins

ptmalloc 将 heap 中相似大小的 chunk 用双向链表链接起来, 这样的一个链表被称为一个bin. ptmalloc 共维护了128个bin, 并使用一个数组来存储这些 bin
但,不太一样的地方在这里

前64个bin叫做exact bins, 每一个 bin 分别包含了相同大小的chunk
后面的bin叫做ordered bins,每一个 bin 分别包含了一个给定范围内的chunk

fast bins

一般的情况是, 程序在运行时会经常需要分配和释放一些较小的内存空间. 当 allocator 合并了相邻的几个小的 chunk 之后, 也许马上就会有另一个小块内存的请求, 这样 allocator 又需要从大的空闲内存中分出一块出来, 这样无疑是比较低效的,所以就有了不合并的fastbins(就是win里面的快表)

不大于 max_fast (72 bytes) 的 chunk 被 free 后, 首先会被放到 fastbins 中, fastbins 中的 chunk 并不改变它的使用标志p. 这样也就无法将它们合并, 当需要给用户分配的 chunk 小于或等于 max_fast 时, ptmalloc 首先会在 fastbins 中查找相应的空闲块(具体的分配算法请参考第7节), 然后才会去查找 bins 中的空间 chunk. 在某个特定的时候, ptmalloc 会遍历 fastbins 中的 chunk, 将相邻的空闲 chunk 进行合并, 并将合并后的 chunk 放到 bins 中去.

unsorted bins

如果被用户释放的 chunk 大于 max_fast, 则按上面的叙述它应该会被放到 bins中. 但实际上, ptmalloc 还引入了一个称为 “unsorted bins”的队列. 这些大于 max_fast 的chunk 首先会被放到 “unsorted bins” 队列中, 在进行 malloc 操作的时候, 如果在 fastbins 中没有找到合适的 chunk, 则 ptmalloc 会先在 “unsorted bins”中查找合适的空闲 chunk, 然后才查找 bins. 如果 “unsorted bins” 不能满足分配要求. malloc 便会将 “unsorted bins” 中的 chunk 放到 bins 中, 然后再在 bins 中继续进行查找和分配过程. 从这个过程可以看出来, “unsorted bins”可以看做是 bins 的一个缓冲区, 增加它只是为了加快分配的速度(就是上面windows部分提到的堆缓存)

top chunk

在前面一直提到, ptmalloc 会预先分配一块较大的空闲内存(也就是所为的 heap), 而通过管理这块内存来响应用户的需求, 因为内存是按地址从低向高进行分配的, 在空闲内存的最高处, 必然存在着一块空闲 chunk, 叫做 “top chunk”. 当 bins 和 fastbins 都不能满足分配需要的时候, ptmalloc 会设法在 “top chunk” 中分出一块内存给用户, 如果 “top chunk” 本身不够大, 则 ptmalloc 会适当的增加它的大小(也就增加了 heap 的大小). 以满足分配的需要, 实际上, “top chunk” 在分配时总是在 ‘fastbins 和 bins 之后被考虑, 所以, 不论 “top chunk” 有多大, 它都不会被放到 fastbins 或者是 bins 中. (应该就是上面windows提到的尾块)

mmaped chunk

当需要分配的 chunk 足够大, 而且 fastbins 和 bins 都不能满足要求, 甚至 “top chunk” 本身也不能满足分配需求时, ptmalloc 会使用 mmap 来直接使用内存映射来将页映射到进程空间(具体的情况, 请参考第6节). 这样分配的 chunk 在被 free 时将直接解除映射, 于是就将内存归还给了系统, 再次对这样的内存区的引用将导致一个 “segmentation fault” 错误. 这样的 chunk 也不会包含在任何 bin 中.(应该就是上面提到的巨块的虚分配)

分配主要靠brk和mmap

资料上具体过程写的有点乱,再找吧

当申请内存时，首先从具有相同大小的已经释放的堆块（或者大一点的堆块,言外之意就是可以切割稍大一点的空闲堆块）中查找并重新使用这段内存。仅仅当没有找到合适的堆块时才会使用顶块。

当一个堆块释放了（通过调用free函数），它会检查之前的堆块是否被释放了。如果之前的堆块没有在使用，那么就会和当前的堆块合并。这样就会增加堆块的大小。结果就是这个堆块需要被放置在不同的链表中。这样的话，之前释放的堆块就需要首先从原来的空闲链表中删除(执行unlink操作),这个时候会改变bk,fd指针,就是利用的时候，接着再和当前堆块合并到另一个合适的链表中。从一个链表中删除一个堆块的代码如下：

这个前后大概是说在空间上chunk和chunk相邻的关系吧,这个和链表中的前后关系无关

据说这是老版本glic里的unlink

void unlink(malloc_chunk * P, malloc_chunk * BK, malloc_chunk * FD) {
    FD = P -> fd;
    BK = P -> bk;
    FD -> bk = BK;
    BK -> fd = FD;
}

学习中

我的天，并没有学会TAT

参考

http://www.tuicool.com/articles/E3Ezu2u (包含了老版本的unlink和新版的)
http://blog.csdn.net/heiyeshuwu/article/details/27325719
http://www.ms509.com/?p=49 (后来看到的)
http://www.cnblogs.com/0xJDchen/category/885258.html