[Linux] 메모리 영역 (2) - Heap

1. Heap

Heap은 동적으로 생성되는 data에 대하여 할당을 해주는 메모리 영역으로 bss를 기준으로 stack과의 사이에 위치한다.

기본적으로 stack은 거꾸로 쌓이며 heap은 code, data영역 다음부터 쌓이게되어 HEAP의 메모리 시작주소 값을 보면 어중간한 중간부터 시작되는 것을 linux memory 명령어를 통해서 확인할 수 있다.

 

1) Chunk

HEAP의 메모리는 Chunk로 이루어져있으며 Chunk단위의 linked List 연결을 통해서 Heap 메모리를 구성하고 있다. 때문에 malloc을 통해서 동적할당이 진행되면 기본적으로 하나의 Chunk를 할당하는 것으로 이해하면 된다.

기본적으로 malloc 1회시 위와 같은 하나의 Chunk가 만들어 진다.

 

• Chunk 속성

Prev_size : Prev_size는 이전 Chunk의 size값을 나타낸다. 단, 이전 chunk가 free된 경우 이전 chunk의 size 값을 나타낸다.

Size : 현재 Chunk의 size값을 나타낸다.

A (Non Main Arena) : 현재 chunk가 main이 아니고 thread 영역에 생성된 경우 해당 Flag set이 된다.

M (Is MMap) : Chunk가 malloc을 사용하지 않고 직접 mmap() system call을 통해서 할당한 경우 Flag가 set이 된다.

P (Prev use) : 이전 Chunk가 아직 할당되어 있는 경우 해당 Flag가 set이 된다.

data : 실제 data가 들어있는 영역이다.

 

위와 같은 구성으로 하나의 Chunk가 이루어져 있으며 여기서 보는 바와 같이 malloc시에 할당 되는 하나의 Chunk는 위와 같으나 실제적으로 하나의 Chunk를 Chunk별 연관된 data끼리 연결하면 아래와 같은 단위를 가지게 된다.

즉 주황색으로 된 부분이 실제 하나의 역할을 진행하는 chunk를 나타내는 것이며 해당 chunk가 free되면 size는 두 개의 영역에서 중복으로 가지고 있게 된다. (실제 하나의 chunk란 해당 chunk의 size,(A,M,P 포함) data부분과 다음 chunk의 pre_size 이다)

 

위와 같이 현재 chunk가 free하면 다음 chunk에 중복으로 현재 chunk의 size를 기록하는 방법을 boundary tag 방식이라고 한다.

해당 방식을 사용하는 이유는 free data는 할당된 데이터와 달리 할당된 chunk별로 구분하지 않고 모두 하나의 free chunk로 합쳐지게된다. 이는 곧 현재 chunk가 free된다면 이전 chunk의 free chunk에 합쳐져야 함을 의미한다.

 

즉 free된 이전 chunk의 size를 가지고 있다가 해당 size에 현재 free된 chunk의 사이즈를 더해줌으로써 free된 영역을 정확이 표시할 수 있고 다음 chunk역시 이렇게 만들어진 prev_size를 바탕으로 free를 진행할 수 있다.

 

결과적으로 하나의 free chunk를 만들기 위하여 위와 같이 boundary tag방식이 필요한 것이다.

 

2) Free Chunk

실제적으로 Free Chunk는 위와 같이 구성되며 위 Free chunk는 malloc으로 인해 할당 받은 하나의 chunk가 free된 경우의 structure이다. 여기서 Free Chunk는 논리적으로 하나의 Free Chunk지만 실제적으로 malloc 을 통해 할당 받은 여러 개의 작은 chunk들로 구성되어 있는 것이 비순차적으로 free된 영역들을 모아둔 것으로 free chunk의 physical한 chunk단위는 연속적이지 않다.

즉 위와 같이 여러 개의 나눠진 free들을 논리적으로 연결하여 하나의 free chunk로 만든 것이다.

때문에 위와 같이 physical적으로 떨어진 free들을 하나로 연결하기 위한 방법이 필요하고 이 방법으로는 double linked list 방식을 주로 사용한다.

 

Free Chunk를 보면 Fd, Bk 속성이 있는데 해당 값이 이전 Chunk의 주소와, 다음 Chunk의 주소를 저장하는 double linked list 기법이다.

추가적으로 Fd_nextsize, Bk_nextsize의 경우 large_bin에서만 사용한다.

 

3) Top Chunk

Top Chunk는 malloc에 의해 할당된 chunk들의 가장 마지막에 붙는 chunk이다 기본적으로 사용자가 요청한 malloc보다 많은 사이즈를 heap 영역에 할당하는데 이 때 사용자 요청외에 남는 부분이 바로 top chunk이다.

 

top chunk는 기본적으로 main, thread에서 더 많은 heap을 요구할 때 메모리 공간을 추가적으로 제공하기 위해 존재하는 것이다.

위와 같은 문제가 발생하는 이유는 기존에 사용자가 동적할당 및 해제를 하는 과정에서 잉여 공간이 생성될 수 있고 이러한 잉여공간으로 인해 정상적으로 할당을 못해주는 문제를 막고자 Top chunk를 두어 따로 여분의 공간을 만들어 둔것이다.

 

결론적으로 잉여 공간에 의해 부족한 부분은 Top chunk의 일부를 가져와 사용할 수 있으며 Top chunk마저도 부족한 경우 thread에서는 mmap을 다시 진행하여 할당요청하고 main에서는 sbrk로 Top chunk의 크기를 늘린다.

• sbrk : malloc과 같은 상위 함수에서 메모리 할당을 위해 실질적으로 호출하는 함수로 세그먼트 메모리 할당을 담당하는 API이다.

4) Bin

Bin은 Free chunk들을 수용하기 위해 사용하는 것으로 free chunk들의 크기에 따라서

 

• large bin
• small bin
• fast bin
• unsorted bin

총 4가지로 나뉘게 된다

 

여기서 free chunk의 요소 중 fd_nextsize와 bk_nextsize는 Large bin에서만 사용되는데 이 이유는 Large bin을 제외한 나머지는 free chunk의 크기가 모두 같으나 Large bin의 경우 크기가 달라 해당 인덱스를 통해 크기를 알 수 있도록 하기 위함이다.

 

기본적으로 unsorted bin은 특별한 Bins이며 Bins의 첫 번째 index에서 관리한다 나머지 small bin은 Bins의 2~63, Large bin은 Bins의 64~126이다.

Bins 1 index = unsorted bin

Bins 2~63 index = small bin

Bins 64~126 inde = large bin

FastbinsY = fast bin

 

• 결합과 비결합

기본적으로 Fastbin의 경우에는 free chunk들이 모두 연속적으로 존재한다. 하지만 free chunk를 하나로 뭉치지 않는 특성을 가지고 있다.

이와 반대로 small, large는 free chunk들이 physical 주소로 비연속적인 경우가 많으며 만약 연속적으로 존재하게 되면 해당 free chunk는 하나의 free chunk로 합쳐지게 된다. 참고로 unsorted freechunk는 1개의 bin만 관리하며 특수한 경우로 위 사항에서 제외한다.

 

5) FastbinsY

Fast bin을 관리하기 위한 bins로 다른 Bin과 달리 double linked list가 아닌 single linked list를 사용한다.

 

총 10개의 bin을 가질 수 있어 FastBinsY의 인덱스는 최대 10개 보통 7개라고 생각하면 된다.

여기서 각각의 인덱스 즉 bin에 free chunk들이 연결되어 관리를 받게 되는데 이 때 서로 연결된 free chunk들은 LIFO 방식으로 bin에 연결된다. (스택과 같은 구조로 이는 single linked list를 사용하기 때문이다)

LIFO 방식이란 위 FastBinsY의 배열에서 앞에서부터 free chunk가 차기 시작하며 사용자가 malloc으로 chunk요청 시에도 배열의 앞쪽 chunk부터 할당하는데 사용됨을 의미한다.

 

6) Bins

Fast Bin을 제외한 나머지 unsorted bin, small bin, large bin을 관리하기 위한 배열을 의미한다.

 

bins의 가장 첫 번 째 index는 unsorted bin이다.

unsorted bin은 특별한 bin으로 large, small bin의 cache역할을 수행한다. large 혹은 small의 chunk가 free되면 처음 unsorted bin으로 들어오게 되며 사용자가 같은 크기를 재할당 요구시 unsorted bin에서 해당 chunk를 할당해준다.

만약 사용자아 요구한 크기와 다를 시에는 해당 chunk는 자신의 크기에 맞는 small or large bin으로 들어가게 된다.

 

bins의 특징은 모두 double linked list를 활용하며 기본적으로 FIFO 구조인 것이다.