粤嵌星计划，粤嵌我来了
今日所学内容：双向链表
链表(Linked List)是一种常见的线性结构。它不需要一块连续的内存空间，通过指针即可将一组零散的内存块串联起来。我们把内存块成为链表的节点，为了将所有的节点串起来，每个链表的节点除了存储数据之外，还需要记录链表的下一个节点的地址，这个记录下个节点地址的指针我们叫做后驱指针。搜索链表需要O(N)的时间复杂度，这点和数组类似，但是链表不能像数组一样，通过索引的方式以O(1)的时间读取第n个数。链表的优势在于能够以较高的效率在任意位置插入或者删除一个节点。
双向链表支持两个方向，每个节点不只有一个后驱指针next指向后面的节点，还有一个前驱指针prev指向前面的节点。

https://t.cn/A662HuUI
学了这么久堆漏洞了，我想应该把glibc的malloc和free源码解析写一下了，希望能帮助一下刚上路的师傅，同时也巩固一下自身知识。

内存分配：
我们平时写程序的时候，某些变量可能需要在开始就分配内存，这些内存是不可避免的。那么这些内存就是静态分配的，当程序编译完成之后，它就确定了占用这么多的内存。

但是有时候，实际问题的规模没有预期那么大，我们不一定需要很大的内存，如果每次都按最大考虑那么就有很大一部分内存是被浪费的，这就是静态分配内存的弊端，虽然咱打acm的时候都是静态分配的。

但是这没啥，因为每个问题不要超过它的总内存上限问题就不大(狗头。但是在内存不足的年代，如果都这样使用静态分配内存的方式，那么计算机的效率会被拖垮很多，所以就有动态分配内存的概念了。

glibc采用ptmalloc的管理方式去分配内存。

ptmalloc2的分配策略：
那么动态分配内存要怎么去分配呢？如果我们需要占用除了我程序本身占用的内存以外的一块内存，那程序指定是没权限用的，得先向操作系统申请这一块内存的使用权。

而操作系统没那么闲，分配几个字节的内存都要它去管，操作系统管理都是按页式的管理。而一页的内存是0x1000B，如果每一次申请我都向操作系统申请，每一次归还都直接归还给操作系统那么必定会增大操作系统的负担。

因此分配内存的时候可以按照一个策略去分配，分配一定得尽量避免过多地使用系统调用，归还的时候可以等到程序结束时一并归还，这样的话操作系统的负担就大大下降了。

ptmalloc2的分配方式会在你第一次malloc的时候向操作系统申请0x21000B(132KB)的内存，然后后续分配就不会向操作系统申请内存，只有用完了的时候才会再次申请内存。

操作系统的问题解决了之后我们再来看看glibc怎么处理具体的分配细节。分配的时候我一定是切出一块特定大小才是最优的策略的，比如程序malloc(4)，那我接切个4字节的内存给它用，malloc(1)那就给它一字节去使用。

然而现实没有那么理想，因为如果我切下来的块用户程序完全可写的话，那么我怎么区分这个内存块是否被使用呢？然后内存块的分界线又如何界定呢？

所以分割内存块的时候不可避免地要在内存块中额外开出一部分区域用于管理。那么可以在每个分配的内存块加上一个int数据作为此内存块的size，64位的操作系统可以使用long long。

同理，为了管理方便，glibc在分配chunk的时候也并不是分配这么多就只能写这么多的。它也不想闲到去管1字节2字节这样的内存块。而且如果有这样的内存块，那么在分配指针的时候内存没办法对齐会出现很多麻烦的事。

所以在分配内存块的时候，有一个SIZE_SZ，一次分配的内存必定是SIZE_SZ*2的整倍数，SIZE_SZ在32位操作系统下的值是4，64位的值是8。为了方便，以下把内存块统一叫chunk。

以32位操作系统为例，size的值必定为8的整数倍，二进制角度下看来，低三位永远是0，这样有点浪费了内存，因此规定size的低三位不作为实际的chunk大小，而是标志位。三个标志位从高位到低位分别是：
NON_MAIN_ARENA:是否为主分配，0表示是主分配，权值为4。

IS_MMAPPED:表示内存是否为mmap获得，0表示不是，权值为2。

PREV_INUSE:表示前面一个内存块是否被使用，0表示不被使用，权值为1。

在64位操作系统中，多出一个标志位，但是这个标志位无任何意义，可能后续会赋予别的意义，但是它一样不影响chunk的大小。

真的会怀念Desperate Housewives[泪][泪][泪]
浅在记单词的时候怀念一下吧

每次听到DH的例句
我还能迅速想起一些场景片段[开学季]不得不说每个人物都刻画得太丰满了
真的很难忘怀

Bree Lynette Susan Gaby…
主妇的生活永远不会结束
“即使是最绝望的生活，也是如此美妙。”

还有机会听到那句"Previously on desprate
housewives"吗？