1
/*
2
     处理最近释放的或剩余的（remaindered）块，仅当块完全匹配时才取用；
3
     或者，如果这是一个小请求，且该块是最近一次非精确匹配产生的剩余块（remainder），则取用。
4
     将遍历到的其他块放入对应的 bin 中。
5
     注意，这一步是所有流程中唯一将块放入 bin 的地方。
6

7
     这里需要外层循环，是因为我们可能直到 malloc 接近结束时才意识到应该进行合并（consolidate），
8
     因此必须合并并重试。这种情况最多发生一次，且仅当我们为了满足“小”请求而不得不扩展内存时才会发生。
9
   */
10

11
  for (;;)
12
    {
13
      int iters = 0;//一个循环计数器
14
      /* 遍历 Unsorted Bin 链表。unsorted_chunks(av) 是哨兵节点。
15
         它以 FIFO（先进先出）顺序从 bk 指针处取块。 */
16
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
17
        {
18
          bck = victim->bk;
19
          /* 安全检查：块的大小不能太小，也不能超过系统总内存 */
20
          if (__builtin_expect (victim->size <= 2 * SIZE_SZ, 0)
21
              || __builtin_expect (victim->size > av->system_mem, 0))
22
            malloc_printerr (check_action, "malloc(): memory corruption",
23
                             chunk2mem (victim), av);
24
          size = chunksize (victim);

1
       /*
2
             如果是小请求，且 Unsorted Bin 中只有这一个块，且它是 last_remainder，
3
             且大小足够切割：则直接进行切割分配。否则进入下一步
4
             这有助于连续的小请求在物理内存上保持局部性。
5
             这是“最佳匹配（best-fit）”策略的唯一例外。
6
           */
7
          if (in_smallbin_range (nb) &&
8
              bck == unsorted_chunks (av) &&
9
              victim == av->last_remainder &&
10
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
11
            {
12
              /* 切割块并重新挂载剩余部分 */
13
              remainder_size = size - nb;
14
              remainder = chunk_at_offset (victim, nb);
15
              /* 将剩余部分放回 Unsorted Bin */
16
              unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
17
              av->last_remainder = remainder;
18
              remainder->bk = remainder->fd = unsorted_chunks (av);
19

20
              /* 如果现在的last_remainder是一个大块，清空其 nextsize 指针
21
                 这是为了防止“脏数据”干扰*/
22
              if (!in_smallbin_range (remainder_size))
23
                {
24
                  remainder->fd_nextsize = NULL;
25
                  remainder->bk_nextsize = NULL;
26
                }
27

28
              /* 设置 victim（分配给用户）和 remainder（留下的）的 header */
29
              set_head (victim, nb | PREV_INUSE |
30
                        (av != &main_arena ? NON_MAIN_ARENA : 0));
31
              set_head (remainder, remainder_size | PREV_INUSE);
32
              set_foot (remainder, remainder_size);
33

34
              check_malloced_chunk (av, victim, nb);
35
              void *p = chunk2mem (victim);
36
              alloc_perturb (p, bytes);
37
              return p; /* 成功分配并返回 */
38
            }

1
    /* 将当前块从 Unsorted Bin 链表中移除 */
2
          unsorted_chunks (av)->bk = bck;
3
          bck->fd = unsorted_chunks (av);
4

5
        /* 如果大小完全符合请求，直接返回，不再放入 bin */
6
          if (size == nb)
7
            {
8
              set_inuse_bit_at_offset (victim, size);
9
              if (av != &main_arena)
10
                victim->size |= NON_MAIN_ARENA;
11
              check_malloced_chunk (av, victim, nb);
12
              void *p = chunk2mem (victim);
13
              alloc_perturb (p, bytes);
14
              return p;
15
            }

1
/* 根据大小决定放入 Small Bin 还是 Large Bin */
2
          if (in_smallbin_range (size))
3
            {
4
              victim_index = smallbin_index (size);
5
              bck = bin_at (av, victim_index);
6
              fwd = bck->fd;
7
            }
8
          else
9
            {
10
              victim_index = largebin_index (size);
11
              bck = bin_at (av, victim_index);
12
              fwd = bck->fd;
13

14
              /* 维护 Large Bins 的排序顺序（从大到小） */
15
              if (fwd != bck)
16
                {
17
                  /* 将 PREV_INUSE 参与比较以微幅加速 */
18
                  size |= PREV_INUSE;
19
                  //一个断言检查，检查bck的上一个chunk的size是否是合法的
20
                  assert ((bck->bk->size & NON_MAIN_ARENA) == 0);
21
                  /* 如果比当前 bin 中最小的块还要小，直接插到末尾 */
22
                  if ((unsigned long) (size) < (unsigned long) (bck->bk->size))
23
                    {
24
                      fwd = bck;
25
                      bck = bck->bk;
26
                      /* 更新 nextsize 链表（用于快速跳过相同大小的块） */
27
                      /*将victim的fd_nextsize指向最大块*/
28
                      victim->fd_nextsize = fwd->fd;
29
                      /*将victim的bk_nextsize指向原来的最小块*/
30
                      victim->bk_nextsize = fwd->fd->bk_nextsize;
31
                      /*这里是两个赋值操作*/
32
                      /*1.让最大块的bk_nextsize指向victim*/
33
                      /*2.让原来的最小快的fd_nextsize指向victim*/
34
                fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim;
35
                    }
36
                  else
37
                    {
38
                      /* 在 Large Bin 中寻找合适的插入位置 */
39
                      assert ((fwd->size & NON_MAIN_ARENA) == 0);
40
                      while ((unsigned long) size < fwd->size)
41
                        {
42
                          fwd = fwd->fd_nextsize;
43
                          assert ((fwd->size & NON_MAIN_ARENA) == 0);
44
                        }
45

46
                      /* 如果大小相等，则插入在同大小块的第二个位置(不进 nextsize 链表)*/
47
                      if ((unsigned long) size == (unsigned long) fwd->size)
48
                        fwd = fwd->fd;
49
                      else
50
                        {
51
                          /* 插入新大小的节点到 nextsize 链表 */
52
                          victim->fd_nextsize = fwd;
53
                          victim->bk_nextsize = fwd->bk_nextsize;
54
                          fwd->bk_nextsize = victim;
55
                          victim->bk_nextsize->fd_nextsize = victim;
56
                        }
57
                      bck = fwd->bk;
58
                    }
59
                }
60
              else
61
                /* 第一个进入该 Large Bin 的块 */
62
                victim->fd_nextsize = victim->bk_nextsize = victim;
63
            }
64

65
          /* 最终执行插入：将块放入目标 bin 的双向链表 */
66
          mark_bin (av, victim_index); /* 在 binmap 中标记该 bin 非空 */
67
          victim->bk = bck;
68
          victim->fd = fwd;
69
          fwd->bk = victim;
70
          bck->fd = victim;
71

72
          /* 安全限制：避免在 Unsorted Bin 过长时陷入死循环 */
73
#define MAX_ITERS        10000
74
          if (++iters >= MAX_ITERS)
75
            break;
76
        }//这个括号匹配的是第一步的while循环
77
    /*在第3步中，我们将victim移出了unsorted bin，如果这个块并没有精准匹配我们的需求
78
    那么我们将这个块放到small bins或者large bins中，我们最终的目的是在检查
79
    unsorted bins中有没有符合用户所需的chunk，于是现在重复第一步操作*/

1
/*
2
         如果是一个大请求，按排序顺序扫描当前 bin 中的 chunks，
3
         找到满足条件的最小块。为此使用跳表（skip list）。
4
       */
5

6
      if (!in_smallbin_range (nb))
7
        {
8
          /* 获取当前 size 对应的 large bin 头部 */
9
          bin = bin_at (av, idx);
10

11
          /* 如果 bin 为空，或者 bin 中最大的块（第一个块）都比请求的 nb 小，
12
             则跳过扫描。
13
           */
14
          if ((victim = first (bin)) != bin &&
15
              (unsigned long) (victim->size) >= (unsigned long) (nb))
16
            {
17
              /* 由于 large bin 中的 chunks 是按从大到小排序的，
18
                 first(bin) 指向最大的块。通过 bk_nextsize，
19
                 我们可以直接跳到该 bin 中【最小】的块，
20
                 然后从小往大搜，以实现“最佳匹配”。
21
               */
22
              victim = victim->bk_nextsize;
23
              while (((unsigned long) (size = chunksize (victim)) <
24
                      (unsigned long) (nb)))
25
                victim = victim->bk_nextsize;
26

27
              /* 【性能优化】
28
                 避免移除某种大小的第一个条目（即跳表节点），
29
                 这样就不必重新路由跳表（skip list）的指针。
30
               */
31
              if (victim != last (bin) && victim->size == victim->fd->size)
32
                victim = victim->fd;
33

34
              remainder_size = size - nb;
35
              /* 将选中的块从 bin 的双向链表和跳表中移除 */
36
              unlink (av, victim, bck, fwd);
37

38
              /* 耗尽（Exhaust）：如果切割后剩下的部分太小（小于最小 chunk 大小） */
39
              if (remainder_size < MINSIZE)
40
                {
41
                  /* 不进行切割，将整个块给用户，设置 inuse 位 */
42
                  set_inuse_bit_at_offset (victim, size);
43
                  if (av != &main_arena)
44
                    victim->size |= NON_MAIN_ARENA;
45
                }
46
              /* 切割（Split） */
47
              else
48
                {
49
                  /* 在 victim 偏移 nb 的地方切出一个新的 remainder */
50
                  remainder = chunk_at_offset (victim, nb);
51

52
                  /* 我们不能假设 unsorted list 是空的，
53
                     因此必须在这里执行一次完整的插入操作。
54
                   */
55
                  bck = unsorted_chunks (av);
56
                  fwd = bck->fd;
57

58
                  /* 【安全检查】检查 unsorted bin 双向链表的完整性 */
59
                  if (__glibc_unlikely (fwd->bk != bck))
60
                    {
61
                      errstr = "malloc(): corrupted unsorted chunks";
62
                      goto errout;
63
                    }
64

65
                  /* 将 remainder 插入到 unsorted bin 的头部 */
66
                  remainder->bk = bck;
67
                  remainder->fd = fwd;
68
                  bck->fd = remainder;
69
                  fwd->bk = remainder;
70

71
                  /* 如果 remainder 仍然属于 large bin 范围，清空其跳表指针 */
72
                  if (!in_smallbin_range (remainder_size))
73
                    {
74
                      remainder->fd_nextsize = NULL;
75
                      remainder->bk_nextsize = NULL;
76
                    }
77

78
                  /* 设置分配块（victim）和剩余块（remainder）的头部/脚部信息 */
79
                  set_head (victim, nb | PREV_INUSE |
80
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
81
                  set_head (remainder, remainder_size | PREV_INUSE);
82
                  set_foot (remainder, remainder_size);
83
                }
84

85
              /* 检查、扰动并返回内存指针 */
86
              check_malloced_chunk (av, victim, nb);
87
              void *p = chunk2mem (victim);
88
              alloc_perturb (p, bytes);
89
              return p;
90
            }
91
        }

1
     /*
2
         通过扫描 bins 来寻找块，从下一个更大的 bin 开始。
3
         这种搜索严格遵循最佳匹配（best-fit）原则；即选择满足条件的
4
         最小块（如果大小相同，则大致选择最久未使用的那个块）。
5

6
         位图（bitmap）避免了检查大多数 bin 是否为空的需要。
7
         在初始阶段（尚未有块返回时）跳过所有 bin 的特定情况，
8
         其实际执行速度比看起来要快。
9
       */
10

11
      /* 1. 从当前索引的下一个 bin 开始查找 */
12
      ++idx;
13
      bin = bin_at (av, idx);
14
      block = idx2block (idx); /* 获取该 bin 索引所在的位图块（通常是一个 32 位整数） */
15
      map = av->binmap[block]; /* 读取该块的位图内容 */
16
      bit = idx2bit (idx);     /* 获取该索引在位图块中对应的比特位 */
17

18
      for (;; )
19
        {
20
          /* 2. 如果当前位图块中，从当前 bit 往后没有设置位（即 map 后面的位全为 0） */
21
          if (bit > map || bit == 0)
22
            {
23
              do
24
                {
25
                  /* 3. 寻找下一个非零的位图块 */
26
                  if (++block >= BINMAPSIZE) /* 如果所有 bin 都找遍了 */
27
                    goto use_top;            /* 绝望了，去求助 top chunk */
28
                }
29
              while ((map = av->binmap[block]) == 0);
30

31
              /* 4. 找到了一个非空的位图块，重置 bin 指针和 bit 位到该块的起点 */
32
              bin = bin_at (av, (block << BINMAPSHIFT));
33
              bit = 1;
34
            }
35

36
          /* 5. 在当前位图块中前进，直到找到被设置为 1 的比特位（代表该 bin 非空） */
37
          while ((bit & map) == 0)
38
            {
39
              bin = next_bin (bin);
40
              bit <<= 1;
41
              assert (bit != 0);
42
            }
43

44
          /* 6. 检查这个 bin。它极大概率是非空的 */
45
          victim = last (bin);
46

47
          /* 7. 如果是误报（false alarm，即位图显示有但 bin 实际为空），清除该位并继续 */
48
          if (victim == bin)
49
            {
50
              av->binmap[block] = map &= ~bit; /* 修正位图，写回内存 */
51
              bin = next_bin (bin);
52
              bit <<= 1;
53
            }
54

55
          /* 8. 终于找到了真正可用的块！ */
56
          else
57
            {
58
              size = chunksize (victim);
59

60
              /* 我们确信这个 bin 里的第一个块肯定足够大（因为它属于更大的 bin） */
61
              assert ((unsigned long) (size) >= (unsigned long) (nb));
62

63
              remainder_size = size - nb;
64

65
              /* 9. 从链表中拆卸该块 */
66
              unlink (av, victim, bck, fwd);
67

68
              /* 耗尽（Exhaust）：如果剩下的小碎块不足以作为一个独立 chunk */
69
              if (remainder_size < MINSIZE)
70
                {
71
                  set_inuse_bit_at_offset (victim, size);
72
                  if (av != &main_arena)
73
                    victim->size |= NON_MAIN_ARENA;
74
                }
75
              /* 切割（Split）：把剩下的部分放回 Unsorted Bin */
76
              else
77
                {
78
                  remainder = chunk_at_offset (victim, nb);
79

80
                  /* 同样的，不能假设 unsorted 链表为空 */
81
                  bck = unsorted_chunks (av);
82
                  fwd = bck->fd;
83
                  if (__glibc_unlikely (fwd->bk != bck))
84
                    {
85
                      errstr = "malloc(): corrupted unsorted chunks 2";
86
                      goto errout;
87
                    }
88
                  remainder->bk = bck;
89
                  remainder->fd = fwd;
90
                  bck->fd = remainder;
91
                  fwd->bk = remainder;
92

93
                  /* 10. 更新 last_remainder 标记，方便下次局部性优化 */
94
                  if (in_smallbin_range (nb))
95
                    av->last_remainder = remainder;
96

97
                  if (!in_smallbin_range (remainder_size))
98
                    {
99
                      remainder->fd_nextsize = NULL;
100
                      remainder->bk_nextsize = NULL;
101
                    }
102

103
                  /* 设置头尾信息 */
104
                  set_head (victim, nb | PREV_INUSE |
105
                            (av != &main_arena ? NON_MAIN_ARENA : 0));
106
                  set_head (remainder, remainder_size | PREV_INUSE);
107
                  set_foot (remainder, remainder_size);
108
                }
109
              check_malloced_chunk (av, victim, nb);
110
              void *p = chunk2mem (victim);
111
              alloc_perturb (p, bytes);
112
              return p;
113
            }
114
        }