_int_malloc 함수 분석 (2)

2019/08/09 - [힙(heap)] - _int_malloc 함수 분석 (1)

_int_malloc 함수 분석 (1)

이 글과 이어지는 내용입니다. 이 글을 안보신 분들은 저 글을 먼저 봐주세요.

 

#if USE_TCACHE
	  /* While we're here, if we see other chunks of the same size,
	     stash them in the tcache.  */
	  size_t tc_idx = csize2tidx (nb);
	  if (tcache && tc_idx < mp_.tcache_bins)
	    {
	      mchunkptr tc_victim;

tcache를 이용할 때다.

여기 이 코드에 있는 동안에 만약 같은 크기의 다른 청크를 발견하면 tcache에 넣는다.

tc_idx에 chunk 크기를 이용해서 tcache의 index를 구해 넣는다.

tcache가 있고, index도 최대를 안넘을 때 참이되는 if문이다.

	      /* While bin not empty and tcache not full, copy chunks over.  */
	      while (tcache->counts[tc_idx] < mp_.tcache_count
		     && (tc_victim = last (bin)) != bin)

tcache에 들어있는 청크 갯수가 최대 미만이고, bin에 청크가 남아있다면 무한 반복한다.

		{
		  if (tc_victim != 0)
		    {
		      bck = tc_victim->bk;
		      set_inuse_bit_at_offset (tc_victim, nb);
		      if (av != &main_arena)
			set_non_main_arena (tc_victim);
		      bin->bk = bck;
		      bck->fd = bin;

		      tcache_put (tc_victim, tc_idx);
	            }
		}
	    }
#endif

tc_victim에 값이 있으면 참이된다.

다음은 위에서 (1)번 분석에서 말했듯이 FIFO방식으로 청크를 빼내는 것이다. 그런 뒤에 tcache에 그 청크를 넣는다.

즉 이 과정은 small bin 중에서 tcache에 들어갈 수 있는 청크가 있으면 tcache로 옮겨오는 것이다.

          void *p = chunk2mem (victim);
          alloc_perturb (p, bytes);
          return p;
        }
    }

(1)에서 설명한 것처럼 유저에게 알맞은 형태로 가공해서 반환하게 된다.

  /*
     If this is a large request, consolidate fastbins before continuing.
     While it might look excessive to kill all fastbins before
     even seeing if there is space available, this avoids
     fragmentation problems normally associated with fastbins.
     Also, in practice, programs tend to have runs of either small or
     large requests, but less often mixtures, so consolidation is not
     invoked all that often in most programs. And the programs that
     it is called frequently in otherwise tend to fragment.
   */

만약 큰 크기를 요청하게되면, 계속하기 전에 fastbin을 병합하게 된다. 거기(fastbin)에 이용가능한 크기가 있는지 보지도 않고 없애는 것은 너무하다고 생각할 수 있지만, 이것은 fastbin에 관련된 단편화 문제를 피하게 된다. 또한 실제로, 프로그램은 작거나 큰 요청을 가지는 경향이 있지만, 혼합해서 쓰는 경우가 많아서 병합이 대부분의 프로그램에서 자주일어나지 않는다. 그리고 자주 불러지는 프로그램들은 단편화가 되는 경향이 있다.

 else
    {
      idx = largebin_index (nb);
      if (atomic_load_relaxed (&av->have_fastchunks))
        malloc_consolidate (av);
    }

small bin 범위가 아닐때이다.

idx에 largebin의 index를 구해서 넣어준다.

그리고 fast chunk가 있으면 malloc_consolidate()를 실행시킨다. 이 함수의 기능은 fastbin에 존재하는 모든 청크를 free시킨뒤 병합할 수 있는 것은 병합해서 unsorted bin에 넣어주게 된다. 자세한 것은 차후 malloc_consolidate함수 분석 포스팅에서 볼 수 있을 것입니다.

 /*
     Process recently freed or remaindered chunks, taking one only if
     it is exact fit, or, if this a small request, the chunk is remainder from
     the most recent non-exact fit.  Place other traversed chunks in
     bins.  Note that this step is the only place in any routine where
     chunks are placed in bins.
     The outer loop here is needed because we might not realize until
     near the end of malloc that we should have consolidated, so must
     do so and retry. This happens at most once, and only when we would
     otherwise need to expand memory to service a "small" request.
   */

 그것이 정확하게 맞거나, 작은 요청일 때 free되거나 남은 청크들을 처리하십시오. bin안에 있는 청크들을 배치하십시오. 이 단계는 청크들이 bins안에 위치하게하는 아무 과정에서도 유일하다는 것을 메모해라. 여기밖의 과정은 우리가 우리가 병합해야하는 malloc의 마지막을 모르기 때문이다. 그래서 그렇게 해야되고, 재시도를 한다. 이것은 대부분은 1번만 일어나고, 그럴 때에만 일어난다. 그렇지 않으면 작은 요청을 처리하기 위해 메모리를 확장할 필요가 있다. 

#if USE_TCACHE
  INTERNAL_SIZE_T tcache_nb = 0;
  size_t tc_idx = csize2tidx (nb);
  if (tcache && tc_idx < mp_.tcache_bins)
    tcache_nb = nb;
  int return_cached = 0;

  tcache_unsorted_count = 0;
#endif

tcache를 사용할때 들어가게 된다. 요청한 크기가 tcache 범위면 tcache_nb를 요청한 크기로 셋팅한다.

위의 것외에 여러가지 변수를 셋팅해놓는 과정이다.

  for (;; )
    {
      int iters = 0;
      while ((victim = unsorted_chunks (av)->bk) != unsorted_chunks (av))
        {
          bck = victim->bk;
          size = chunksize (victim);
          mchunkptr next = chunk_at_offset (victim, size);

          if (__glibc_unlikely (size <= 2 * SIZE_SZ)
              || __glibc_unlikely (size > av->system_mem))
            malloc_printerr ("malloc(): invalid size (unsorted)");
          if (__glibc_unlikely (chunksize_nomask (next) < 2 * SIZE_SZ)
              || __glibc_unlikely (chunksize_nomask (next) > av->system_mem))
            malloc_printerr ("malloc(): invalid next size (unsorted)");
          if (__glibc_unlikely ((prev_size (next) & ~(SIZE_BITS)) != size))
            malloc_printerr ("malloc(): mismatching next->prev_size (unsorted)");
          if (__glibc_unlikely (bck->fd != victim)
              || __glibc_unlikely (victim->fd != unsorted_chunks (av)))
            malloc_printerr ("malloc(): unsorted double linked list corrupted");
          if (__glibc_unlikely (prev_inuse (next)))
            malloc_printerr ("malloc(): invalid next->prev_inuse (unsorted)");

무한반복이다.

while문으로 인해 unsorted_bin에 청크가 들어가 있으면 무한반복을 하게된다.

bck에 가장 처음에 unsorted_bin에 들어간 청크를 저장한다.

size에는 그 청크의 크기를 저장한다.

next에는 다음 청크의 주소를 저장한다.

 

size가 유효한 크기인지 확인하는 if문이다

next_size검사

다음 청크의 prev_size가 현재 청크의 크기와 일치하는지 확인

double linked list가 올바른지 확인한다.

다음 청크의 prev_inuse bit가 0인지 확인한다.

          /*
             If a small request, try to use last remainder if it is the
             only chunk in unsorted bin.  This helps promote locality for
             runs of consecutive small requests. This is the only
             exception to best-fit, and applies only when there is
             no exact fit for a small chunk.
           */

만약 작은 요청이고, 그 청크가 unsorted bin에 남은 유일한 청크라면, 분할하고 남은 나머지 청크를 사용하려 시도한다. 이것은 연속된 작은 요청의 지역성에 도움을 준다. 이것은 오직 가장 잘 맞을 때가 예외이고, 작은 청크를 위해 딱 맞는 것이 없을 경우에 적용된다.

          if (in_smallbin_range (nb) &&
              bck == unsorted_chunks (av) &&
              victim == av->last_remainder &&
              (unsigned long) (size) > (unsigned long) (nb + MINSIZE))

small bin 범위에 맞고, unsorted_bin에 있는 것이 없고, 분할하고 남은 나머지만이 unsorted bin에 들어가 있고, 그 size가 요청한 크기 + 최소 크기보다 클때 분할하게된다.

            {
              /* split and reattach remainder */
              remainder_size = size - nb;
              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);

remainder_size를 분할할 크기를 빼주어서 갱신을 한다.

그리고 remainder 포인터를 크기를 이용해 갱신한다.

double linked list를 위해 unsorted bin의 요소도 remainer로 갱신해준다.

malloc_state 구조체의 last_remainder까지 갱신해준다.

double linked list를 위해 remainer의 bk와 fd에 unsorted bin의 주소를 저장해준다. 자세한 것은 bin 포스팅에서 다루겠습니다.

              if (!in_smallbin_range (remainder_size))
                {
                  remainder->fd_nextsize = NULL;
                  remainder->bk_nextsize = NULL;
                }

smallbin의 범위가 아니면 즉 large bin에 드러갈 크기라면 large bin의 특징인 circular double linked list 구조를 가진 fd_nextsize와 bk_nextsize를 셋팅해준다.

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

/* Set size at head, without disturbing its use bit */
#define set_head_size(p, s)  ((p)->mchunk_size = (((p)->mchunk_size & SIZE_BITS) | (s)))

/* Set size/use field */
#define set_head(p, s)       ((p)->mchunk_size = (s))

/* Set size at footer (only when chunk is not in use) */
#define set_foot(p, s)       (((mchunkptr) ((char *) (p) + (s)))->mchunk_prev_size = (s))

각각의 매크로의 원형은 이렇다. 처음꺼는 size_bit(prev_inuse, non_main_arena, mmaped)를 망가뜨리지 않고 크기를 설정하는 것이다.

2번째는 size_bit에 상관없이 크기를 셋팅하는 것이다.

3번째는 대상 청크의 다음 청크의 prev_size를 셋팅하는 것이다.

 

그래서 이 함수들을 써서, 처음에는 분할해서 얻은 청크의 size를 다시 셋팅해주고, 2번째로는 remainder 즉 분할하고 남은 나머지의 크기를 셋팅해준다. 3번째로는 이 remainder 청크는 unsorted bin에 있는 것이므로 prev_size를 셋팅해준다.

             check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }

할당받은 청크를 검사한다.

청크의 주소를 가공하고 검사한뒤 반환해준다.

          /* remove from unsorted list */
          if (__glibc_unlikely (bck->fd != victim))
            malloc_printerr ("malloc(): corrupted unsorted chunks 3");
          unsorted_chunks (av)->bk = bck;
          bck->fd = unsorted_chunks (av);

double linked list가 잘되어있는지 검사한다.

unsorted bin에서 victim을 제거하는 과정이다.

          /* Take now instead of binning if exact fit */

          if (size == nb)
            {
              set_inuse_bit_at_offset (victim, size);
              if (av != &main_arena)
		set_non_main_arena (victim);

size가 nb랑 같을 때, 즉 요청하는 크기와 unsorted bin에서 가장 앞에 있는 청크의 크기가 같을 때 참이 된다.

대상 청크의 다음 청크의 prev_inuse bit를 셋팅시킨다.

main_arena가 아니면 non_main_arena bit를 셋팅시킨다.

#if USE_TCACHE
	      /* Fill cache first, return to user only if cache fills.
		 We may return one of these chunks later.  */
	      if (tcache_nb
		  && tcache->counts[tc_idx] < mp_.tcache_count)
		{
		  tcache_put (victim, tc_idx);
		  return_cached = 1;
		  continue;
		}
	      else
		{
#endif

tcache_nb가 0이 아니라는 것은 요청한 크기가 tcahce 범위라는 것이다. 그 tcache_nb가 셋팅되고, tcache count가 충부하다면 참이 된다.

tcache에 victim을 넣는다.

return_cached 값을 셋팅하고 반복문으로 들어간다.

             check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;

victim 청크를 검사한다.

그리고 p를 가공한 뒤에 반환한다.

#if USE_TCACHE
		}
#endif

열린 괄호를 닫기위한 부분이다.