01.malloc

复制本地路径 | 在线编辑
./malloc/mallo.c/_int_malloc
1. 检查 fast bins  
if (如果申请块大小 < fast bins 阈值):
    检查Fast bins: 根据申请块的大小立刻能找到索引值 idx, 然后看看对应链表是否为空

2. 检查 small bins
if (如果申请块大小 < small bins 阈值):
    检查Small bins: 能立刻找到索引值 idx, 然后看对应链表是否为空
else:
    合并Fast bins: 遍历Fast bins，如果不可合并，放入Unsorted中，如果可以合并，合并完之后放入Unsorted中

3. 检查 unsorted bins
条件1
* Unsorted bins 只有一块
* 这一块是 Last Remainder (这是 Unsorted 中切割剩下的块，而且每次发生 Unsorted 切割，都会更新 Last Remainder，看 6.3)
* 这一块大小足够使用(大于等于申请的块大小)

if (条件1):
    - 分离Last Remainder，剩下的块重新放入Unsorted，返回分掉的块，结束
    - 这里没有使用 unlink_chunk 方法，因此没有一些检查(作为对比，可以看 6.3)

    - 问答：现在有唯一一块，大小为(0x100)，需要分配(0x90)，剩下(0x10)怎么办？
    - 答案：这种情况，不满足步骤2，大小足够使用的要求是(0x90 + 0x20)
else:
    - 遍历Unsorted，根据块大小放入对应的Small 和 Large 中
    - 如果某个块满足要求(等于块大小)，返回，结束

    - 问答：现在有大小(0x100)的块，需要分配(0x90)，如何处理？
    - 答案：只是放入对于的small bins中，步骤3要求严格相等才可返回该块

4. 检查 large bins

* 步骤1: 找块
- 首先要明确 Large bins 每个索引对应的链表上的块是一个范围, 所以通过块大小找到对应索引, 是指块大小在该索引对应链表的块大小范围中, 所以有可能链表中的块还是都小于要申请的块的. 不像 Fast bins 和 Small bins, 索引对应的就是一个具体值而不是范围.
- 在Large bins 找到对应索引，然后开始遍历那个链表，找到第一个要求的块. 这里符合要求的块一定是大于我们要的块，因为如果是等于，那么第四步就检测完毕了

* 步骤2: 切割块
- 如果当前块和下一块大小相等，那么返回下一块，而不是返回当前块(WHY: Answer_01)
- 如果当前块拆掉之后，小于最小chunk(0x20)(WHY: Answer_02)

- 问答：为什么不先去看看Small bins，在第3步中，有块加入到了Small bins中了呀
- 答案：如果第3步中有块加入Small bins，那么它一定不等于我们想要的块，否则第3步会检测到然后返回了。

5. 利用Bit Map 查找需要的块

* 步骤1
- 到了这一步，来看看堆的情况，Fast 为空，Unsorted 为空，Small 对应idx 没有完全相等块，Large 对应的idx 没有大的块
- 所以很明显，一定要去看看比 idx 大的那些链表，如果有块，就分割

* 步骤2
- 使用Bit Map，具体实现不细说，注释给出了，就是使用位示图，找出比当前块大的最小块(min-max)
- 说明一下，为什么可以使用位示图，是因为系统始终保存了Bins 的使用情况，有为1，无为0

* 步骤3
- 找到的话，就从对应链表中取出来，然后分割就OK，注意此时，割下的块放入Unsorted bin中
- 此时从链表取出来，会触发 unlink_chunk 方法，该方法有一些检测机制，如下面这条语句
    if (chunksize (p) != prev_size (next_chunk (p)))
- 此时，如果是从 Small bin 中抽取的话，那么会把截断后剩下的块设置为 Last Remainder

- 问答：这里的链表取出，有的是单向链表，有的是双向链表，如何判断
- 答案：判断你个头哇，这里面Fast 为空，一定要么是Small，要么是Large，肯定是双向链表

- 问答：这里的链表取出，取出第一个还是最后一个
- 答案：肯定是取得最后一个, 首先Small 无所谓的，但是Large bin 是从大到小排的，所以就最后一个喽

6. 以上还不行，那就从Top chunk 分离，如果还不行，那就要执行Sysmalloc

Answer_01
- 如果当前块和下一块大小相等，那么返回下一块，而不是返回当前块，为什么？
这个要知道 fast bins 中有 nextsize, 类似于 fd/bk, fast bins 各个链表中有 fd_nextsize/bk_nextsize.
我们找到的当前块, 此时它一定是和他相同大小的块的第一个. 
也就是说前一个大小的块的 fd_nextsize 指向这个块, 这个块也有 bk_nextsize 指向前一个大小的块.

所以如果我们发现下一个块和它是同一大小, 那么就返回下一个块, 去 unlink 该块
在 unlink 的时候, 就可以刚开始判断 nextsize 是否为 NULL, 这样就不用去修改 nextsize 指针了, 省事快一点.

Answer_02
- 如果当前块拆掉之后，小于最小chunk(0x20)，该如何处理？
TODO: 暂时不知道
01.malloc

Comments
