[Heap] malloc.c 분석(4) - malloc()

이 포스트에서는 malloc()함수가 호출되는 과정을 분석해보겠다. 사실상 malloc.c에서 가장 핵심적인 부분이다.

 

 

 

__libc_malloc() 함수 호출.

[ Thread Arena ]

• mstate ar_ptr 변수에 arena_get(ar_ptr, bytes)를 이용해 Arena 정보를 저장한다.
• victim = _int_malloc(ar_ptr, bytes); 을 통해 victim에 할당받은 chunk정보 저장.

[ Main Arena ]

• victim = _int_malloc(&main_arena, bytes); 를 통해 victim에 할당받은 chunk정보 저장.
• assert( !victim | &main_arena == areana_for_chunk(mem2chunk(victim)));

이후 공통적으로 victim에 할당받은 chunk정보가 저장되어 있으니, return victim;을 통해 함수 종료.

 

 

 

__int_malloc() 함수 호출.

 

가장먼저 요청된 size(여기서는 nb)가 fastbin의 크기에 속하는지 검사해서 속한다면, fastbin에서 chunk를 재할당한다.

 

[Code]

  idx = fastbin_index(nb); → 요청된 사이즈가 fastbinY배열의 몇번째 인덱스인지 조회

  mfastbinptr* fb = &fastbin(av, idx); → 해당 인덱스의 fastbin list의 시작주소 저장

  victim = *fb; → 해당 인덱스의 fastbin의 첫번째 주소를 저장

 

  if ( victim != NULL ) { → 해당 fastbin에 chunk가 있다면

    if ( SINGLE_THREAD_P )

      *fb = victim->fd; → unlink단계를 거친다.(Single Linked List기 때문에 이 과정만 있으면 된다. 속도UP)

    else

      .................생략

    

    if ( victim != NULL ) { 

      victim_index = fast_bin_index(chunksize(victim)); 

      assert( victim_index != idx ); → unlink한 chunk의 사이즈가 해당 fastbin list의 사이즈와 일치하지 않으면 임의의 조작이 있던 것으로 판단해 프로그램 종료.

      .................생략

      void* p = chunk2mem(victim); → 실제로 반환되는 주소는 헤더를 제외한 +8byte(32비트 기준) 주소기 때문에 변환을 해주는 과정이다.

      alloc_pertub(p, bytes); → 뭘까..?

      return p;

    }

  }

 

 

fastbin에 적절한 chunk가 없다면, 그 다음은 small bin에서 적절한 chunk를 탐색한다.

 

[Code]

  idx = smallbin_index(nb); → 이 과정은 항상 존재한다..! smallbin에서 몇번째 bins배열에 해당하는지 조회.

  bin = bin_at(av, idx); → 그 인덱스의 bins배열 첫 번째 chunk를 bin 변수에 담는다.

  if (( victim = last(bin)) != bin ) { → 생각보다 중요한 부분이다. 우선 last(bin)을 victim에 담는 이유는, small bin은 FIFO구조이기 때문이다. 그리고 victim에 담은 chunk가 bin이랑 같다는 것은, 해당 bin이 비어있다는 뜻이다. (malloc_init_state()함수 참조)

    if ( victim == null ) → 음...?

      malloc_consolidate(); → 이 함수는 fastbin을 병합해서 맞는 bin에 넣는함수이다.

    

    bck = victim->bk; → 할당받을 chunk의 bk를 담고, 그 담은 chunk의 fd가 할당받을 chunk와 다르면 에러. 어찌보면 당연히 맞아야 되는거지만, 임의의 조작을 방지하기 위한 예외처리 정도이다.

    if ( bck->fd != victim )  Error!

    set_inuse_bit_at_offset(victim, nb); → victim에서 nb만큼 떨어진 chunk (즉, 다음 chunk)의 inuse bit 세팅.

    

    bin->bk = bck; 

    bck->fd = bin; → 환형 Double Linked List의 unlink 하는 과정이다.

   

    void* p = chunk2mem(victim);

    alloc_pertub(p, bytes);

    return p;

  }

 

 

우선 여기까지오면, malloc_consolidate()함수를 호출해, fastbin을 병합한다.

그리고 unsored bin에서 적절한 chunk가 있는지 확인하는 단계를 거친다.

 

[Code]

  idx = largebin_index(nb);

  int iter = 0;

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

            → unsorted_chunks의 bk를 담는 다는말은 곧 unsorted bin의 제일 뒤의 chunk를 담는 다는 말이고, small bin과 마찬가지로 그 chunk가 자기 자신이라면 unsorted bin은 비어있는게 된다.

    bck = victim->bk;

    size = chunksize(victim); → 여러가지 예외상황을 검사하기위해 세팅.

 

    (여기서 Error체크) → 보이는 그대로의 검사들을 하고, 비정상이라면 프로그램을 종료한다.

      - size <= 2 * SIZE_SZ

      - size > av->system_mem

      - chunk_size_nomask(next) < 2 * SIZE_SZ

      - chunk_size_nomask(next) > av->system_mem

      - prev_size(next) & ~(SIZE_BITS)) != size

      - bck->fd != victim

      - victim->fd != unsorted_chunks(av)

      - prev_inuse(next)가 unset

 

      if ( in_smallbin_range(nb) && bck == unsorted_chunks(av) &&

                             victim == av->lastremainder && size > nb + MINSIZE ) {

        → 여기가 조금 특이한데, 요청한 크기가 smallbin 영역이고 (즉, small bin에 적당한 chunk가 없었다라는 말), victim이 unsorted bin의 가장 마지막에 들어온 chunk고, victim이 last_remainder 즉, 가장 최근에 분할되어 할당해주고 남은 찌꺼기 chunk이고, 그 크기가 분할해줄만큼 충분한 크기가 된다면 해당 조건문을 실행한다. 

        remainder_size = size - nb; → last_remainder에 저장할 chunk를 만드는 과정 (chunk - 요청사이즈)

        remainder = chunk_at_offset(victim, nb); 

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

                   → 만들어진 remainder를 unsorted bin 제일 앞에 저장한다.

        av->last_remainder = remainder;

        remainder->bk = remainder->fd = unsorted_chunks(av); → remainder 셋팅 끝.

                   → unsorted bin에 존재하는 다른 chunk들은 어쩌고 이렇게 세팅을 하냐는 의문을 가졌었는데, 위에 조건을 만족하려면 기본적으로 unsorted bin이 비어있을 거라는 생각을 했다.

  

        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);

  

        void* p = chunk2mem(victim);

        alloc_pertub(p, bytes);

        return p;

      }

  

    if ( bck->fd != victim )  Error!!

    unsorted_chunks(av)->bk = bck; (bck는 위에서 victim->bk)

    bck->fd = unsorted_chunks(av); → 이제 해당 chunk를 unsorted bin에서 unlink하는 작업.

  

    if ( size == nb ) { → unlink한 chunk가 요청한 사이즈와 같다면 바로 할당.

      set_inuse_bit_at_offset(victim, size);

      if ( av != &main_arena )

         set_non_main_arena(victim);

      void* p = chunk2mem(victim);

      alloc_perturb(p, bytes);

      return p;

    }

    → 여기까지 왔다는건 사이즈가 적절하지 않다는 뜻. unsorted bin에서 꺼낸 Chunk를 이제,

        크기에 맞는 bin에 집어넣는 과정을 할 것이다.

 

    if ( in_smallbin_range(size) ) { 

         → 요청한 사이즈와 다르고, small bin이라면, 해당 chunk를 small bin에 위치 시킬계획.

      victim_index = smallbin_index(size); → 인덱스 파악 하고~

      bck = bin_at(av, victim_index); → 제일 앞지포인터를 bck변수에 저장하고

      fwd = bck->fd; → 그 chunk의 fd를 fwd에 저장한다.

        → 이렇게 하는 이유는 결국 마지막에 bk와 fd사이에 chunk를 끼워 넣을것이기 때문!!

    }

    else { → large bin에 해당하는 크기라면 large bin에 위치 시킬계획.

      → large bin에 속하면 크기별로 정렬되어야 하기 때문에, 크기를 비교해 적절한 위치에 삽입한다. large bin에는 한 bin에 여러 사이즈가 들어가 있으므로 요청을 만족하는 가장 작은 크기의 chunk를 찾는다. 제일 앞의 chunk를 victim에 저장하고, 주어진 크기보다 victim이 큰지 비교 후 크면 중지한다. (내림차순)  그리고 victim = victim->bk_nextsize로 설정. 이제 주어진 크기보다 커질때 까지 반복해 찾은 후 찾으면 그 자리에 chunk를 삽입한다.

      victim_index = largebin_index(size);

      bck = bin_at(av, victim_index);

      fwd = bck->fd; → 여기까지는 마찬가지로 동작.

  

      if ( fwd != bck ) { → 근데! fwd와 bck가 같다..? 라는건 비어있다는 뜻이다.

        size |= PREV_INUSE;

        if ( size < chunksize_nomask(bck->bk)) { 

            → 해당 large bin에서 제일 작은 사이즈보다 작으면 제일 마지막에 삽입.

          fwd = bck;

          bck = bck->bk;

  

          victim->fd_nextsize = fwd->fd;

          victim->bk_nextsize = fwd->fd->bk_nextsize;

          fwd->fd->bk_nextsize = victim->bk_nextsize->fd_nextsize = victim; → 단순한 링크과정이다.

        } else { 

          while ( size < chunksize_nomask(fwd) ) → 아니라면 while문을 통해 찾는다.

            fwd = fwd->fd_nextsize;

  

          if ( size == chunksize_nomask(fwd) ) → 찾았더니 사이즈가 동일한 chunk가 이미있으면, fwd를 한칸 이동하고, 그 사이에 victim을 넣는다. 굳이 2번째에 넣는 이유는 fd_nextsize, bk_nextsize를 조정하지 않아도되는 속도적 이득 때문.

            fwd = fwd->fd;

          else { → 해당 사이즈가 존재하지 않지만, 위치는 찾았으면 그 사이에 넣고 nextsize들 링크과정을 거친다.

            victim->fd_nextsize = fwd;

            victim->bk_nextsize = fwd->bk_nextsize;

  

            if ( fwd->bk_nextsize->fd_nextsize != fwd ) Error!!

            fwd->bk_nextsize = fwd;

            victim->bk_nextsize->fd_nextsize = victim;

         }

         bck = fwd->bk;

         if ( bck->fd != fwd )  Error!!

       }

     } else {

       victim->fd_nextsize = victim->bk_nextsize = victim;

     } → 여기까지 왔으면 fwd와 bck가 올바르게 설정되었다는 뜻.

           그냥 단순하게 fwd와 bck 사이에 victim을 집어 넣기만 하면된다.

   victim->bk = bck;

   victim->fd = fwd;

   fwd->bk = victim;

   bck->fd = victim;

 } → 여기가 제일처음 (victim = unsorted_chunks(av)->bk) != unsorted_chunks(av) while문이 끝나는 지점. 이 while문이 끝나면, unsorted bin은 비워져 있고, small bin/large bin에 모든 freed chunk들이 들어가 있다. 또한 unsorted bin에서 적절한 chunk를 찾지 못했다는 뜻이다.

 

여기까지 와서야 large bin에서 반환가능한 chunk가 있는지 찾아본다.

 

[Code]

  bin = bin_at(av, idx); → large bin에서의 인덱스를 통해 bin list의 시작부를 bin에 담는다.

  if ( (victim = first(bin)) != bin && chunksize_nomask(victim) >= nb ) {

    → 일단 제일큰걸 넣고, 작은게 나올 때까지 반복문을 돌려서 가장 적합한 chunk를 찾는다.

        두번째 조건은 제일큰거 조차도 nb보다 작으면 안되기 때문에 넣어준 것.

    victim = victim->bk_nextsize;

    while ( (size = chunksize(victim)) < nb )

      victim = victim->bk_nextsize;

 

    if ( victim != last(bin) && chunksize_nomask(victim) == chunksize_nomask(victim->fd) )

      victim = victim->fd; → 이 과정은, 만약 해당 bin에 적절한 사이즈의 chunk가 두개 이상일 경우에 첫 번째가아니라 두번째 chunk를 반환하게 하기 위함이다. nextsize linked list의 연결과정을 생략하기 위해 이렇게 동작한다.

    remainder_size = size - nb; → remainder를 만들수 있다면, 만들기 위해서 !

    unlink_chunk(av, victim); → 해당 chunk를 large bin에서 분리(unlink) 한다.

 

    if ( remainder < MINSIZE ) { → remainder가 사용할 수 없는 크기라면 ?

      set_inuse_bit_at_offset(victim, size); → 그냥 전부 소진해버린다(Exhaust 라고 표현되어 있다.)

      if ( av != &main_arena )

        set_non_main_arena(victim);

    } else {

      remainder = chunk_at_offset(victim, nb); → remainder 만드는 과정.

      bck = unsorted_chunks(av); 

      if ( bck != fwd->bk )  Error!!

     

      remainder->bk = bck;

      remainder->fd = fwd;

      bck->fd = remainder;

      fwd->bk = remainder; → 만들어진 remainder를 unsorted bin의 제일 앞에 넣는다.

                                        이 때 unsorted bin은 반드시 비어있기 때문에, 이렇게 해줘도 무방하다.

 

      .........생략 → large bin이라면 nextsize를 null로 초기화 해주는 과정.

 

      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);

    }

    void* p = chunk2mem(victim);

    alloc_pertub(p, bytes);

    return p;

  }

  

  ++idx; → 다음 large bin (조금더 큰 사이즈 bin배열)

  bin = bin_at(av, idx);

  block = idx2block(idx);

  map = av->binmap[block];

  bit = idx2bit(idx);

 

  for ( ; ; ) {

    .........생략 → bitmap을 이용한다고 하는데, 구체적인 내용은 모르겠다.

 

    victim = last(bin);

    if ( victim == bin )

       .........생략 → bitmap을 초기화 해주는 과정.

    else {

      size = chunksize(victim);

      if ( !(size >= nb) ) Error!! → 충분한 공간이 없다면 에러.

      remainder_size = size - nb;

      unlink_chunk(av, victim);

 

      remainder->bk = bck;

      remainder->fd = fwd;

      bck->fd = remainder;

      fwd->bk = remainder; → 만들어진 remainder를 unsorted bin의 제일 앞에 넣는다.

                                        이 때 unsorted bin은 반드시 비어있기 때문에, 이렇게 해줘도 무방하다.

 

      .........생략 → large bin이라면 nextsize를 null로 초기화 해주는 과정.

 

      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);

    }

    void* p = chunk2mem(victim);

    alloc_pertub(p, bytes);

    return p;

  }

 

결국 모든 large bin을 확인. 여기까지 도달했다는 것은 각 bin에 사용 가능한 적절한 chunk가 없다라는 말!

그러면 Top Chunk에서 분리하여 할당한다.

 

[Code]

  victim = av->top; → top chunk를 victim에 담고,

  size = chunksize(victim);

  if ( size > av->system_mem )  Error!! → 당연한 에러.

  if ( size >= nb + MINSIZE ) { → top chunk의 size가 요청한 사이즈를 반환해주고 MINSIZE만큼 남는다면

    remainder_size = size - nb;

    remainder = chunk_at_offset(victim, nb);

    av->top = remainder; → 남은걸 다시 top chunk에 저장한다.

 

    set_head(victim, nb | PREV_INUSE | (av != &main_arena ? NON_MAIN_ARENA : 0));

    set_head(remainder, remainder_size | PREV_INUSE);

 

    void* p = chunk2mem(victim);

    alloc_pertub(p, bytes);

    return p;

  } else if ( atomic_load_relaxed(&av->have_fastchunks) ) { → 마지막으로 fast bin을 검사해 뭔가 있으면

                                                                                병합 후 idx 재설정 후 위로 올라가서 다시 확인.

    malloc_consolidate(av);

    if ( in_smallbin_range(nb) )

      idx = smallbin_index(nb);

    else

      idx = largebin_index(nb);

  } else { → top chunk에도 할당 해줄만한 size가 없다면, sysmalloc()함수를 통해 할당한다.

    void* p = sysmalloc(nb, av);

    if ( p != NULL )

      alloc_pertub(p, bytes);

    return p;

  }