_int_malloc함수 분석(3)

2019/08/09 - [분류 전체보기] - _int_malloc 함수 분석 (2)

_int_malloc 함수 분석 (2)

이 글과 이어지는 내용입니다. 안보셨으면 보고 오시는 것을 추천드립니다.

 

            }

          /* place chunk in bin */

          if (in_smallbin_range (size))
            {
              victim_index = smallbin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;
            }

unsorted bin에 가장 앞에 있는 청크의 크기가 smallbin 범위라면 index를 구하고 bin 주소를 구한다, 그리고 fwd에 bck->fd 가장 나중에 free된 청크의 주소를 넣는다.

          else
            {
              victim_index = largebin_index (size);
              bck = bin_at (av, victim_index);
              fwd = bck->fd;

아니라면 large bin이기 때문에 index를 구하고 위의 과정을 똑같이 한다.

              /* maintain large bins in sorted order */
              if (fwd != bck)
                {
                  /* Or with inuse bit to speed comparisons */
                  size |= PREV_INUSE;
                  /* if smaller than smallest, bypass loop below */
                  assert (chunk_main_arena (bck->bk));

fwd와 bck가 같지 않다면 즉 구한 large bin안에 어떤 청크가 들어가 있다면, 참이 된다

size 에 prev_inuse bit를 속도를 높이기 위해 셋팅한다.

bck -> bk가 main_arena가 아니면 프로그램을 종료한다.

                 if ((unsigned long) (size)
		      < (unsigned long) chunksize_nomask (bck->bk))
                    {
                      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;
                    }

size가 bck->bk 즉 large bin에 가장 먼저 들어왔던 청크와 크기를 비교한다.

이하 내용은 fd_nextsize와 bk_nextsize를 이용한 circular double linked list로 linking을 하기위한 코드이다.

 

circular double linked list에 관한 것들을 보실려면 아래를 참고해주세요,

https://www.javatpoint.com/circular-doubly-linked-list

Circular Doubly Linked List - javatpoint

                  else
                    {
                      assert (chunk_main_arena (fwd));
                      while ((unsigned long) size < chunksize_nomask (fwd))
                        {
                          fwd = fwd->fd_nextsize;
			  assert (chunk_main_arena (fwd));
                        }

main_arena가 아니면 종료한다.

size와 fwd 즉 가장 나중에 free된 청크와 크기를 비교한다.

size가 fwd의 크기보다 작으면 fwd를 fwd -> fd_nextsize로 계속하여 바꾼다.

                      if ((unsigned long) size
			  == (unsigned long) chunksize_nomask (fwd))
                        /* Always insert in the second position.  */
                        fwd = fwd->fd;

size와 fwd의 크기를 비교한다.

같으면 fwd에 fwd -> fd를 넣어준다.

                      else
                        {
                          victim->fd_nextsize = fwd;
                          victim->bk_nextsize = fwd->bk_nextsize;
                          fwd->bk_nextsize = victim;
                          victim->bk_nextsize->fd_nextsize = victim;
                        }
                      bck = fwd->bk;
                    }
                }

아니라면 그 청크를 청크들 중간에 넣어준다. 즉 large bin을 크기로 오름차순 정렬을 하는 것이다.

다음으로는 bck에 fwd -> bk를 넣어준다.

              else
                victim->fd_nextsize = victim->bk_nextsize = victim;
            }

large bin에 처음으로 victim이 들어가는 것이면 fd_nextsize와 bk_nextsize를 자기 자신으로 초기화시켜준다.

 

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

mark_bin함수는 binmap 관련 함수로서 차후 포스팅에서 설명하겠습니다.

bck에는 끼어넣을 두 청크 중 뒷부분을 저장해놓았고, fwd는 앞청크의 주소를 담고 있다.

victim의 bk와 fd를 셋팅하는 과정이다.

 

여기서 주의깊게 봐야할 것이 우리는 size가 같을 때에는 fwd만 값을 셋팅해주었다. 즉 fd_nextsize나 bk_nextsize는 건드리지 않는 것이다.

#if USE_TCACHE
      /* If we've processed as many chunks as we're allowed while
	 filling the cache, return one of the cached ones.  */
      ++tcache_unsorted_count;
      if (return_cached
	  && mp_.tcache_unsorted_limit > 0
	  && tcache_unsorted_count > mp_.tcache_unsorted_limit)
	{
	  return tcache_get (tc_idx);
	}
#endif

tcache를 사용했을 때 정의된다.

 

tcache_unsorted_count를 증가시킨다.

return_cached는 for(;;)무한 반복문안에서 요청한 크기와 대상의 크기가 같을 때 1로 셋팅된다. 따라서 이게 셋팅되어 있다는 말은 같은 크기의 청크가 tcache에 있다는 말이다.

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

이 값과 조건문의 의미는 잘 모르겠습니다. ㅠ.ㅠ

#if USE_TCACHE
      /* If all the small chunks we found ended up cached, return one now.  */
      if (return_cached)
	{
	  return tcache_get (tc_idx);
	}
#endif

tcache에 있으면 가져오는 함수이다.

      /*
         If a large request, scan through the chunks of current bin in
         sorted order to find smallest that fits.  Use the skip list for this.
       */

만약에 큰 요청이라면, 맞는 가장 작은 것을 찾기 위해서 현재 정렬된 bin을 탐색한다. 이것을 위해 무시 리스트를 만든다.

      if (!in_smallbin_range (nb))
        {
          bin = bin_at (av, idx);

largebin범위가 아닐때

bin 주소를 가져온다.

          /* skip scan if empty or largest chunk is too small */
          if ((victim = first (bin)) != bin
	      && (unsigned long) chunksize_nomask (victim)
	        >= (unsigned long) (nb))

bin에 청크가 없거나 가장 작은 청크의 크기가 요청한 크기보다 작으면 거짓이 되는 조건문이다.

           {
              victim = victim->bk_nextsize;
              while (((unsigned long) (size = chunksize (victim)) <
                      (unsigned long) (nb)))
                victim = victim->bk_nextsize;

참이면 victim에 victim -> bk_nextsize를 저장하는데 이것은 처음으로 largebin에 들어온 청크이다.

요청한 크기가 더 커질때까지 bk_nextsize로 갱신한다.

              /* Avoid removing the first entry for a size so that the skip
                 list does not have to be rerouted.  */
              if (victim != last (bin)
		  && chunksize_nomask (victim)
		    == chunksize_nomask (victim->fd))
                victim = victim->fd;

다시 반복을 돌지 않기 위해 크기의 첫번째 청크를 없애는 것은 피한다.

조건을 통과하면 victim의 fd를 저장한다.

              remainder_size = size - nb;
              unlink (av, victim, bck, fwd);

remainder_size를 size에서 필요한 바이트만큼 빼서 갱신한다.

그런 뒤 unlink함수를 통해 그 청크를 bin에서 빼온다.

             /* Exhaust */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
		    set_non_main_arena (victim);
                }

남은 크기가 최소크기보다 작을때

victim의 다음 청크의 prev_inuse bit를 셋팅한다.

상황에 따라 non_main_arena bit를 셋팅한다.

              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb);
                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;

최소크기보다 클때이다.

remainder에 뗴주고 남은 청크의 시작 주소를 저장한다.

unsorted list가 비어있는지 몰라서 완벽한 삽입을 해야한다고 말하고 있다.

bck에는 unsorted bin 관련 포인터를 저장한다. (자세한 것은 bin 관련 포스팅에서)

fwd 에는 bck ->fd 즉 가장 나중에 free된 청크를 저장한다.

		  if (__glibc_unlikely (fwd->bk != bck))
		    malloc_printerr ("malloc(): corrupted unsorted chunks");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;

double linked list 보안검사이다.

남은 청크를 linking 시키는 과정이다.

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

만약 large bin 범위이면, fd_nextsize와 bk_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);
                }

새로 생긴 청크의 free한 것처럼 여러가지 값을 셋팅해준다.

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

제대로 할당받았는지 검사한다.

그 뒤 가공한뒤 반환한다.

      /*
         Search for a chunk by scanning bins, starting with next largest
         bin. This search is strictly by best-fit; i.e., the smallest
         (with ties going to approximately the least recently used) chunk
         that fits is selected.
         The bitmap avoids needing to check that most blocks are nonempty.
         The particular case of skipping all bins during warm-up phases
         when no chunks have been returned yet is faster than it might look.
       */

bins들을 검사해서 청크를 찾기 위해서는 가장 큰 bin에서 시작한다. 이 검색은 엄격히 잘 맞는다. 예를들어, 가장 최근에 쓰인 가장 맞는 작은 청크가 선택되었다고 생각해봐라.

bitmap은 모든 블럭이 비어있지 않은 것을 체크하는 것을 피한다. 초기시간 동안에 모든 bin들을 생략하는 특별한 경우 즉 어떤 청크도 아직 반환되지 않았을 경우가 이것보다 빠르다.

 

      ++idx;
      bin = bin_at (av, idx);
      block = idx2block (idx);
      map = av->binmap[block];
      bit = idx2bit (idx);

여기까지 왔다는 것은 현재 idx에 맞는 bin에 청크가 없다는 것이다. 따라서 idx를 1증가시킨다.

새로 bin주소를 구해온다.

idx에 맞는 block을 구해오고

거기에 담긴 값도 읽어온다.

idx에 맞는 bit도 구해온다.

 

      for (;; )
        {
          /* Skip rest of block if there are no more set bits in this block.  */
          if (bit > map || bit == 0)
            {
              do
                {
                  if (++block >= BINMAPSIZE) /* out of bins */
                    goto use_top;
                }
              while ((map = av->binmap[block]) == 0);

              bin = bin_at (av, (block << BINMAPSHIFT));
              bit = 1;
            }

무한반복이다.

bit가 map보다 작으면 즉, idx에 맞는 청크가 free된적이 없거나 bit가 0 즉 잘못 구해졌을 경우에 거짓이 된다.

끝까지 검사했으면 top 청크를 이용해 할당하는 부분으로 간다.

binmap이 0이면 즉, 청크가 free된 적이 없으면 반복한다.

다시 새로 bin을 얻어오고,

bit를 1로 즉 binmap의 첫번째로 바꾼다.

          /* Advance to bin with set bit. There must be one. */
          while ((bit & map) == 0)
            {
              bin = next_bin (bin);
              bit <<= 1;
              assert (bit != 0);
            }

bit와 map의 and 연산 했을 때 0이라는 것은 bit에 맞는 청크가 free되지 않았다는 것이다

다음 bin으로 바꾸고

그에 맞게 bit도 갱신한다.

bit가 0이면 프로그램 종료한다.

          /* Inspect the bin. It is likely to be non-empty */
          victim = last (bin);

          /*  If a false alarm (empty bin), clear the bit. */
          if (victim == bin)
            {
              av->binmap[block] = map &= ~bit; /* Write through */
              bin = next_bin (bin);
              bit <<= 1;
            }

victim이 bin의 bk 즉 bin중에 가장 크기가 작은 청크가 된다.

victim이 bin이라는 것은 bin에 아무것도 없다는 것이다.

그러면 binmap[block]의 bit부분만 0으로 초기화 시킨다.

다음 bin을 선택한다.

bit에 2를 곱해준다.

          else
            {
              size = chunksize (victim);

              /*  We know the first chunk in this bin is big enough to use. */
              assert ((unsigned long) (size) >= (unsigned long) (nb));

bin에 청크가 있었다면 size를 셋팅해준다.

우린는 우리가 요청한 크기보다 저 청크의 크기가 크다는 것을 알고 있기 때문에 크기가 더 작으면 프로그램을 종료한다.

              remainder_size = size - nb;

              /* unlink */
              unlink (av, victim, bck, fwd);

              /* Exhaust */
              if (remainder_size < MINSIZE)
                {
                  set_inuse_bit_at_offset (victim, size);
                  if (av != &main_arena)
		    set_non_main_arena (victim);
                }

              /* Split */
              else
                {
                  remainder = chunk_at_offset (victim, nb);

                  /* We cannot assume the unsorted list is empty and therefore
                     have to perform a complete insert here.  */
                  bck = unsorted_chunks (av);
                  fwd = bck->fd;
		  if (__glibc_unlikely (fwd->bk != bck))
		    malloc_printerr ("malloc(): corrupted unsorted chunks 2");
                  remainder->bk = bck;
                  remainder->fd = fwd;
                  bck->fd = remainder;
                  fwd->bk = remainder;

                  /* advertise as last remainder */
                  if (in_smallbin_range (nb))
                    av->last_remainder = remainder;
                  if (!in_smallbin_range (remainder_size))
                    {
                      remainder->fd_nextsize = NULL;
                      remainder->bk_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);
                }
              check_malloced_chunk (av, victim, nb);
              void *p = chunk2mem (victim);
              alloc_perturb (p, bytes);
              return p;
            }
        }

이 부분은 요청한 크기가 smallbin범위이고, unsorted bin에 remainder 청크만 있을 때 remainder 청크를 분할해주는 루틴이랑 같다.

    use_top:
      /*
         If large enough, split off the chunk bordering the end of memory
         (held in av->top). Note that this is in accord with the best-fit
         search rule.  In effect, av->top is treated as larger (and thus
         less well fitting) than any other available chunk since it can
         be extended to be as large as necessary (up to system
         limitations).
         We require that av->top always exists (i.e., has size >=
         MINSIZE) after initialization, so if it would otherwise be
         exhausted by current request, it is replenished. (The main
         reason for ensuring it exists is that we may need MINSIZE space
         to put in fenceposts in sysmalloc.)
       */

만약 충분히 크다면, av->top에 있는 메모리의 끝이라 접하는 청크를 분할해준다. 이것은 검색 방식에 딱 맞는다는 것을 기억해두라.

사실상, av->top은 그것이 필요하다면 시스템 제한까지 확장할 수 있기 때문에 다른 아무 이용가능한 청크보다 크게 다루어진다.

 av->top이 항상 존재해야한다. 시작 뒤에, 그래서 만약 그것이 그렇지 않다면 현재 요청에 의해 다 써버릴 것이고, 그것은 다시 채워질 것이다. (그것이 존재하는 것을 확실히 하는 주요한 이유는 우리가 sysmalloc에서 최소 크기를 요구하기 때문이다.) 

 

      victim = av->top;
      size = chunksize (victim);

      if (__glibc_unlikely (size > av->system_mem))
        malloc_printerr ("malloc(): corrupted top size");

top 청크에서 분할할 것이므로 victim은 top이 된다.

av->system_mem보다 top 청크 크기가 크다는 것은 잘못된 것이므로 프로그램을 종료한다.

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

요청한 크기보다 top 청크 크기가 작고, atomic ops는 공유 자원을 프로세스 하나만 쓸 수 있게 하는 것이다. 

이 조건문이 참이되면 malloc_consolidate를 통해 fast bin 청크를 free 시키고, bin index를 복구 시킨다.

      /*
         Otherwise, relay to handle system-dependent cases
       */
      else
        {
          void *p = sysmalloc (nb, av);
          if (p != NULL)
            alloc_perturb (p, bytes);
          return p;
        }
    }
}

그렇지 않으면, sysmalloc을 통해 청크를 할당하고 반환한다.

p가 NULL 즉 잘못 얻어지면 perturb를 셋팅한다.