---

首先，堆上的空闲内存都是以双向循环链表的形式组织和管理的。平时，用得最多的是通过new/delete或者malloc/free来申请和释放内存。那么，操作系统中对内存的管理是如何进行的呢？下面介绍一个最常用的内存管理算法，即伙伴算法。伙伴算法对内存的组织如下图所示：

图 伙伴算法内存管理

系统中的伙伴算法将内存所有的空闲页面分为N个块组。第K（0 =< K < N）组中块含2^k个页面大小。每一组中块的大小是相同的，且同样大小的块形成一个双向链表。

假设要求分配的块的大小为256个页面。那么算法就在块大小为256个页面的块组中进行查找，看是否有这样一个空闲块。如果有，就直接分配；如果没有，该算法会查找下一个更大的块。如果在512大小的块组中找到一个，就将512分为两部分，一分用于分配，一分插入大小为256大小的块中。

其中把满足下面两个条件的块称为伙伴：

1．两个块大小相同；

2．两个块的物理地址连续。

伙伴算法将满足以上的两个块合并为一个块，如果合并后的块还可以跟相邻的块进行合并，那么该算法就继续合并。

伙伴算法的回收过程就是将系统释放的空闲块按照伙伴算法合并后插入相应的块组中。

 

从堆上分配空闲内存，就是将一个大小符合要求链表结点从双向循环链表中移下来，而释放内存，就是将该空闲内存重新插入这个双向空闲循环链表。

 

如上图所示，学过数据结构的都知道，当把一个结点从双向循环链表中删除的时候，在设置结点中的bp和fp指针的时候，有2次内存写入机会。而又由于实际上双向循环链表相邻的2个结点是连续存储的，因此，当在拷贝数据的时候，在向分配的第一个结点拷贝的时候，多拷贝16个字节，就会覆盖相邻的下一个结点的bp和fp指针，经过精心构造之后，如果把bp指针覆盖为任意地址(where)，而把fp指针设置为任意数据(what)，因此在分配第二个结点内存的时候，将会造成任意地址写入任意数据漏洞，把任意数据覆盖到任意地址。

 

int main( void )

{

        char *p1 = malloc( Node0 ) ;//分配第一个结点

        strcpy( p1 , shellcode ) ;    //造成缓冲区溢出

        char *p2 = malloc( Node1 ) ; //分配第二个结点时，发生malloc堆溢出攻击

        return 0 ;

}