Windows Low Fragmentation Heap

Windows LFH

• LFH : Low Fragmentation Heap, 단편화가 적은 힙
• windows 2k SP4, windows XP, windows 2k3 부터 적용

Heap Fragmentation (힙 단편화)

http://javagosu.tistory.com

사용자가 힙의 메모리를 할당받아서 사용하면, 메모리 관리자는 가능한 영역에서 연속된 공간을 사용자한테 할당해줄 것이다. 단일 객체는 연속된 메모리 공간을 사용하기 때문이다. 사용자가 메모리를 사용하는 패턴을 생각해보면, 메모리의 할당 순서는 연속적이어서 착착 힙을 순서대로 사용하는 것 같지만, 할당한 해제 순서는 뒤죽 박죽이다. 그렇기 때문의 위 그림처럼 쓸수 있는 공간이 파편화되는 현상이 발생한다. 이것을 Heap Fragmentation이라고 한다. 문제는 이렇게 파편화된 메모리 상황에서 메모리 할당을 요청할 때 발생한다. 위 그림처럼 남은 메모리 총량은 충분하지만, 조각난 연속된 메모리 공간중 어떤 것도 원하는 사이즈가 들어갈 만큼 충분히 크지 않으면 메모리 할당이 실패한다.

Heap Chunk

OS 프로그래머들은 위의 파편화 상태를 내버려두지 않았다. 그래서 Heap Chunk 그리고 Free List (bins management)방식을 고안하여 파편화를 해결하려고 노력했다. 일단 연속된 메모리의 한 단위를 chunk라고 부르자. chunk가 사용자에 의해 요청된 후 반환되면, free 상태의 메모리가 된다. 반환된 메모리들은 기존의 데이터를 이전에 반환된 메모리의 주소와 앞으로 연결된 주소를 저장할 공간으로 사용한다. 운영체제는 반환된 free chunk (bin)에 대한 Linked List를 구성하여 빈 영역에 대해서 관리할 수 있게 장치를 마련해 두었다.

http://www.slideshare.net/ffri/mr201312-history-and-current-state-of-heap-exploit-eng

새로 메모리 할당 요청이 들어오면 OS는 우선적으로 free list를 순회하면서 적절한 메모리 영역을 찾는다. free list의 chunk들을 이용가능한 사이즈로 sorting한다면 이 순회작업이 훨씬 효과적일 것이다. 이렇게 최대한 적합한 빈 chunk를 찾은뒤 유저가 원하는 사이즈로 분할하여 반환하는 방식으로 동작한다. 이 방식의 단점은 적은 단위의 메모리를 매우 빈번하게 할당 / 해제하는 경우에 발생한다. 처음 할당한 메모리의 크기를 가지고 free chunk를 만들었고, 요청에 따라 또다시 chunk를 분할하여 사용한다. 그러면 매우 많고 작은 chunk들이 발생할 것이고, 이것을 원활하게 사용하는 것은 힘든 일이 될 것이다.

Low Fragmentation Heap

최신 Windows 운영체제는 위의 Heap Chunk 방식에서 좀더 발전한 Heap 관리 정책을 적용시켰다. 이름부터 패기 넘치는 Low Fragmentation Heap (이하 LFH), 단편화 현상이 적은 힙이다. 아이디어는 미리 힙의 Chunk를 정해진 크기로 나눠서 해당 Chunk영역를 할당/해제 하는 방식으로 직접 메모리를 관리하는 방식이다. 앞에서 이야기한 free list 방식은 작은 chunk들을 계속해서 분할하여 할당하는 방식을 진행하여 관리하기 어려운 문제가 있었다. 하지만 직접 정해진 사이즈별로 Chunk를 미리 만들어 두고 필요한 메모리에 적합한 최소한의 세그먼트를 할당하는 방식으로 지나친 분할과 관리의 어려움을 극복했다. 이렇게 미리 정해진 사이즈로 나뉘어진 Chunk를 Bucket이라고 부른다. 이런 Bucket 형식이 유용한 부분은 작은 사이즈의 Chunk를 사용하는 경우이다. 이 때 사용하는 관리자를 front-end heap매니저라고 한다. 그리고 큰 사이즈의 Chunk들은 기존의 free list방식을 유지할 수 있게 back-end heap manager에게 일을 맡긴다.

http://www.slideshare.net/ffri/mr201312-history-and-current-state-of-heap-exploit-eng

그리고 LFH는 미리 Bucket으로 분할하여 관리하는 것으로 적합한 메모리영역을 찾는 속도를 빠르게 가져간다. 크기별 Free List들을 분할하여 Look-Aside List에 나눠서 관리하는 것이다. 말하자면 Free List에 대한 List를 만드는 것이다. 정해진 사이즈의 Free List들을 관리하는 각각의 BlocksIndex에 정보를 담아서 이 Free List에 원하는 사이즈가 있는지 체크한 뒤에 넘어가는 방식으로 접근 성능을 높였다.

//원하는 사이즈가 현재 인덱스의 최대 크기보다 큰지 체크한다.
while(BlockSize >= BlocksIndex -> ArraySize )
{
   //다음번 인덱스(더 큰 단위의 free list)를 찾는다.
   if(BlocksIndex -> ExtendedLookup == NULL) 
   {
       //없으면 back-end heap manager에게 패스
   }
   //있다면 다음번 인덱스로 넘어가서 체크
   BlocksIndex = BlocksIndex -> ExtendedLookup;
}

//그리고 해당 Index에 알맞은 free list에서 원하는 Chunk를 찾아서 할당

더하여 high-end windows의 LFH는 힙의 멀티쓰레딩이슈까지 처리했다고 한다. 힙은 private힙을 별도로 만들어 주지 않는 이상, 프로세스의 쓰레드들이 공유한다. 그래서 힙 영역을 다루는 API는 힙 할당이 경쟁상태가 되는 경우를 막기위해 atomic한 연산으로 동작한다. 쓰레드들은 힙을 다루는데 비싼 Lock연산을 통해 동작할 수 밖에 없는 문제가 있었다.

LFH는 affinity한 관리자를 제공한다. 자주 사용되는 bucket들을 내부적인 counter를 통해 접근 수준을 파악하고, 빈번한 bucket에 대해서 해당 bucket의 개수를 두배로 늘린다. 그리고 경쟁상태에 있는 bucket이 발생하면(아마도 빈번한 접근 때문에 개수가 많아졌을것), 대기중인 쓰레드를 다른 bucket으로 접근할 수 있게 해준다.

기타 힙 관리 라이브러리

힙의 효율성은 빠른 성능을 위해서 매우 중요한 부분이다. 그래서 다양한 힙 관리 라이브러리들이 힙의 성능을 최적화하기 위해 노력하였다. 그중 대표적인 tcmalloc과 jemalloc을 소개한다.

tcmalloc

그 이름도 거창한 thread cache malloc은 구글에서 야심차게 들고나온 메모리 할당 라이브러리이다. 쓰레드별로 private힙을 만들어서 thread local cache 힙으로 사용한다. 그리고 메인 힙은 central heap으로 전체적인 데이터를 관리한다. 쓰레드들이 빈번하게 사용하는 데이터를 local cache힙에 저장하여 힙 경쟁상태에 빠지는 것을 회피한다. thread local cache가 있음으로 해서 메모리 할당시 불필요한 동기화를 줄이고 그에 따른 lock cost가 꽤 많이 감소되어 성능을 향상시킨다. 멀티 쓰레드환경에서 적은 데이터를 많이 다룰 때 많은 성능 향상을 기대할 수 있다. 라이브러리 설치가 간단하고, 기존 malloc을 변경시키는 방식으로 동작하여 쉽게 사용하기 좋다.

jemalloc

페이스북에서 만들어준 힙 관리 라이브러리이다. 기존 구조는 tcmalloc과 비슷하게 thread cache 힙을 사용한다. 리눅스 용으로 포팅했다는 것말고는 겉으로 보기에 그리 신선해보이지는 않는다.(직접 구현체를 보지는 않았지만...) 같은 이유에서 멀티쓰레드 환경에 작은 할당이 빈번하게 이루어지는 경우 성능향상을 체감할 수 있다고 한다.