glibc-malloc源码阅读二

1
2
3
4
5
6
7
8
9

struct malloc_chunk {
  INTERNAL_SIZE_T      mchunk_prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      mchunk_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;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

    chunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of previous chunk, if unallocated (P clear)  |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of chunk, in bytes                     |A|M|P|
      mem-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             User data starts here...                          .
            .                                                               .
            .             (malloc_usable_size() bytes)                      .
            .                                                               |
nextchunk-> +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             (size of chunk, but used for application data)    |
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
            |             Size of next chunk, in bytes                |A|0|1|
            +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

struct malloc_state
{
  /* Serialize access.  */
  __libc_lock_define (, mutex);
  /* Flags (formerly in max_fast).  */
  int flags;
  /* Set if the fastbin chunks contain recently inserted free blocks.  */
  /* Note this is a bool but not all targets support atomics on booleans.  */
  int have_fastchunks;
  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];
  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;
  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;
  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];
  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];
  /* Linked list */
  struct malloc_state *next;
  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;
  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;
  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* There are several instances of this struct ("arenas") in this
   malloc.  If you are adapting this malloc in a way that does NOT use
   a static or mmapped malloc_state, you MUST explicitly zero-fill it
   before using. This malloc relies on the property that malloc_state
   is initialized to all zeroes (as is true of C statics).  */
static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

#define arena_get(ptr, size) do { \
      ptr = thread_arena;                                                      \
      arena_lock (ptr, size);                                                      \
  } while (0)

#define arena_lock(ptr, size) do {                                              \
      if (ptr)                                                                      \
        __libc_lock_lock (ptr->mutex);                                              \
      else                                                                      \
        ptr = arena_get2 ((size), NULL);                                      \
  } while (0)

1
2

//ptmalloc_init (void)
thread_arena = &main_arena;

1
2
3
4
5
6
7

if (SINGLE_THREAD_P)
{
  victim = _int_malloc (&main_arena, bytes);
  assert (!victim || chunk_is_mmapped (mem2chunk (victim)) ||
          &main_arena == arena_for_chunk (mem2chunk (victim)));
  return victim;
}

1
2
3
4
5
6
7
8
9

a = get_free_list ();
if (a == NULL)
{
  //......
  a = _int_new_arena (size);
  //......
  a = reused_arena (avoid_arena);
  //......
}

1
2
3
4
5
6

mstate replaced_arena = thread_arena;
thread_arena = a;
//......
__libc_lock_lock (free_list_lock);
detach_arena (replaced_arena);
__libc_lock_unlock (free_list_lock);

1
2
3
4
5
6
7

/* Add the new arena to the global list.  */
a->next = main_arena.next;
/* FIXME: The barrier is an attempt to synchronize with read access
    in reused_arena, which does not acquire list_lock while
    traversing the list.  */
atomic_write_barrier ();
main_arena.next = a;

1
2
3
4

/* FIXME: Access to next_to_use suffers from data races.  */
static mstate next_to_use;
if (next_to_use == NULL)
  next_to_use = &main_arena;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

/* Iterate over all arenas (including those linked from
    free_list).  */
result = next_to_use;
do
  {
    if (!__libc_lock_trylock (result->mutex))
      goto out;
    /* FIXME: This is a data race, see _int_new_arena.  */
    result = result->next;
  }
while (result != next_to_use);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

/* Attach the arena to the current thread.  */
{
  /* Update the arena thread attachment counters.   */
  mstate replaced_arena = thread_arena;
  __libc_lock_lock (free_list_lock);
  detach_arena (replaced_arena);
  /* We may have picked up an arena on the free list.  We need to
      preserve the invariant that no arena on the free list has a
      positive attached_threads counter (otherwise,
      arena_thread_freeres cannot use the counter to determine if the
      arena needs to be put on the free list).  We unconditionally
      remove the selected arena from the free list.  The caller of
      reused_arena checked the free list and observed it to be empty,
      so the list is very short.  */
  remove_from_free_list (result);
  ++result->attached_threads;
  __libc_lock_unlock (free_list_lock);
}

1
2
3

LIBC_PROBE (memory_arena_reuse, 2, result, avoid_arena);
thread_arena = result;
next_to_use = result->next;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

void
__malloc_arena_thread_freeres (void)
{
  /* Shut down the thread cache first.  This could deallocate data for
     the thread arena, so do this before we put the arena on the free
     list.  */
  tcache_thread_shutdown ();
  mstate a = thread_arena;
  thread_arena = NULL;
  if (a != NULL)
    {
      __libc_lock_lock (free_list_lock);
      /* If this was the last attached thread for this arena, put the
         arena on the free list.  */
      assert (a->attached_threads > 0);
      if (--a->attached_threads == 0)
        {
          a->next_free = free_list;
          free_list = a;
        }
      __libc_lock_unlock (free_list_lock);
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

p = mem2chunk (mem);
if (chunk_is_mmapped (p))                       /* release mmapped memory. */
{
  /* See if the dynamic brk/mmap threshold needs adjusting.
      Dumped fake mmapped chunks do not affect the threshold.  */
  if (!mp_.no_dyn_threshold
      && chunksize_nomask (p) > mp_.mmap_threshold
      && chunksize_nomask (p) <= DEFAULT_MMAP_THRESHOLD_MAX
      && !DUMPED_MAIN_ARENA_CHUNK (p))
    {
      mp_.mmap_threshold = chunksize (p);
      mp_.trim_threshold = 2 * mp_.mmap_threshold;
      LIBC_PROBE (memory_mallopt_free_dyn_thresholds, 2,
                  mp_.mmap_threshold, mp_.trim_threshold);
    }
  munmap_chunk (p);
  return;
}

1
2

ar_ptr = arena_for_chunk (p);
_int_free (ar_ptr, p, 0);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

if ((unsigned long)(size) <= (unsigned long)(get_max_fast ())
{
  //...
  unsigned int idx = fastbin_index(size);
  fb = &fastbin (av, idx);
  /* Atomically link P to its fastbin: P->FD = *FB; *FB = P;  */
  mchunkptr old = *fb, old2;
  //...
  p->fd = old2 = old;
  //...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

else if (!chunk_is_mmapped(p)) {
  //...

  // 获取下一个chunk
  nextchunk = chunk_at_offset(p, size);

  // 拿到下一个chunk的size
  nextsize = chunksize(nextchunk);

  /* consolidate backward */
  // 如果上一个chunk可被访问, 合并上一个chunk到当前chunk
  if (!prev_inuse(p)) {
    // 获取上一个chunk的大小
    prevsize = prev_size (p);

    // 扩充当前chunk的size
    size += prevsize;

    // 获取上一个chunk的位置
    p = chunk_at_offset(p, -((long) prevsize));
    if (__glibc_unlikely (chunksize(p) != prevsize))
      malloc_printerr ("corrupted size vs. prev_size while consolidating");

    // 将上一个chunk从arena中移除(因为被合并到当前chunk了)
    unlink_chunk (av, p);
  }
  //...

  // 下一个chunk同理, 但是需要考虑是不是在top, 以下假设下一个chunk也合并了

  // 合并后的chunk插入到unsorted_bin的头部
  bck = unsorted_chunks(av);
  fwd = bck->fd;
  if (__glibc_unlikely (fwd->bk != bck))
    malloc_printerr ("free(): corrupted unsorted chunks");
  p->fd = fwd;
  p->bk = bck;
  if (!in_smallbin_range(size))
    {
      p->fd_nextsize = NULL;
      p->bk_nextsize = NULL;
    }
  bck->fd = p;
  fwd->bk = p;

  // 设置新chunk的size
  set_head(p, size | PREV_INUSE);
  set_foot(p, size);
}

1
2
3
4

if ((unsigned long)(size) >= FASTBIN_CONSOLIDATION_THRESHOLD) {
  if (atomic_load_relaxed (&av->have_fastchunks))
    malloc_consolidate(av);
//......

1

while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))

1
2
3
4

// bck表示上一个chunk
bck = victim->bk;
size = chunksize (victim);
mchunkptr next = chunk_at_offset (victim, size);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

// 检查大小以及unsorted_bin中chunk是不是只有一个
if (in_smallbin_range (nb) &&
    // 判断unsorted_chunks中只有一个chunk
    bck == unsorted_chunks (av) &&
    victim == av->last_remainder &&
    (unsigned long) (size) > (unsigned long) (nb + MINSIZE))
{
  /* split and reattach remainder */
  // 只分配需要的大小
  remainder_size = size - nb;

  // 多余的部分继续塞在unsorted_chunks
  remainder = chunk_at_offset (victim, nb);
  unsorted_chunks (av)->bk = unsorted_chunks (av)->fd = remainder;
  av->last_remainder = remainder;
  remainder->bk = remainder->fd = unsorted_chunks (av);
  if (!in_smallbin_range (remainder_size))
    {
      remainder->fd_nextsize = NULL;
      remainder->bk_nextsize = NULL;
    }

  // 设置chunk信息
  set_head (victim, nb | PREV_INUSE |
            (av != &main_arena ? NON_MAIN_ARENA : 0));
  set_head (remainder, remainder_size | PREV_INUSE);
  set_foot (remainder, remainder_size);
  check_malloced_chunk (av, victim, nb);
  void *p = chunk2mem (victim);
  alloc_perturb (p, bytes);
  return p;
}

1
2

unsorted_chunks (av)->bk = bck;
bck->fd = unsorted_chunks (av);

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

if (in_smallbin_range (size))
  {
    victim_index = smallbin_index (size);
    bck = bin_at (av, victim_index);
    fwd = bck->fd;
  }
else
  {
    //...
    //largebin的塞入位置是有序的, 会判断当前chunk的size而返回不同的插入部位
    //总之, 这一步之后, largebin会变得有序
  }

1
2
3
4
5

mark_bin (av, victim_index);
victim->bk = bck;
victim->fd = fwd;
fwd->bk = victim;
bck->fd = victim;

1
2
3

#define MAX_ITERS       10000
if (++iters >= MAX_ITERS)
  break;

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

if (!in_smallbin_range (nb))
  {
    /* skip scan if empty or largest chunk is too small */
    if ((victim = first (bin)) != bin
        && (unsigned long) chunksize_nomask (victim)
          >= (unsigned long) (nb))
      {
        victim = victim->bk_nextsize;
        while (((unsigned long) (size = chunksize (victim)) <
                (unsigned long) (nb)))
          victim = victim->bk_nextsize;
        //...

        if (remainder_size < MINSIZE)
          {
            //...
          }
        /* Split */
        else
          {
            //...
          }
        //...
      }
  }

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38

victim = av->top;
size = chunksize (victim);
if (__glibc_unlikely (size > av->system_mem))
  malloc_printerr ("malloc(): corrupted top size");
if ((unsigned long) (size) >= (unsigned long) (nb + MINSIZE))
  {
    remainder_size = size - nb;
    remainder = chunk_at_offset (victim, nb);
    av->top = remainder;
    set_head (victim, nb | PREV_INUSE |
              (av != &main_arena ? NON_MAIN_ARENA : 0));
    set_head (remainder, remainder_size | PREV_INUSE);
    check_malloced_chunk (av, victim, nb);
    void *p = chunk2mem (victim);
    alloc_perturb (p, bytes);
    return p;
  }
/* When we are using atomic ops to free fast chunks we can get
    here for all block sizes.  */
else if (atomic_load_relaxed (&av->have_fastchunks))
  {
    malloc_consolidate (av);
    /* restore original bin index */
    if (in_smallbin_range (nb))
      idx = smallbin_index (nb);
    else
      idx = largebin_index (nb);
  }
/*
    Otherwise, relay to handle system-dependent cases
  */
else
  {
    void *p = sysmalloc (nb, av);
    if (p != NULL)
      alloc_perturb (p, bytes);
    return p;
  }