Heap에 대해... (process default heap, private heap, fragmentation)

Heap은 Stack과 함게 프로세스의 대표적인 메모리 처리 공간, 혹은 기법중 하나인데, 예를 들어, 일반적인 로컬 변수는 Stack에, malloc과 같은 동적 할당 메모리는 Heap에서 주로 사용되기도 합니다. 즉, 처음부터 그 크기가 결정되어 계획하에 잡히는 메모리는 주로 Stack이고, 그 크기가 결정되지 않아 계속 커지거나, 변동하거나, 매우 큰 경우에는 동적 할당 메모리, 즉, Heap을 사용하게 됩니다.

malloc(혹은 new)으로 대표되는 Heap은, Process Heap과 Private Heap으로 사용되는데, Process Heap은 프로세스 생성시에 함께 동반되어 생성되는 것이며(PE Loader에 의해... 확인필요), Private Heap은 Win32 API에 의해 만들수 있습니다.

malloc은 Process Heap을 사용하는가? Private Heap을 사용하는가?

malloc은 표준 C 함수로, parameter에 size만 들어가도록 되어 있습니다. 즉, 어떤 Heap을 선택할지는 포함되어 있지 않습니다. 그렇기 때문에, 위에서 설명한것 처럼 어떤 heap이 사용되는지가 궁금하기도 합니다.

일반적으로 malloc은 "시스템 Heap"을 사용한다고 하는데, 이는 Process Heap, Private Heap 두개로 설명되지 않습니다. 그래서 자세히 확인하기 위해 malloc 소스 코드를 따라 확인해 보도록 하겠습니다.

우선, C:\Program Files\Microsoft Visual Studio 9.0\VC\crt\src\heapinit.c를 열어서, _heap_init() 함수의 아래 부분에 break point를 걸고, F5로 디버깅을 시도해 봅니다.

int __cdecl _heap_init (

        int mtflag

        )

{

#if defined _M_AMD64 || defined _M_IA64

        // HEAP_NO_SERIALIZE is incompatible with the LFH heap

        mtflag = 1;

#endif  /* defined _M_AMD64 || defined _M_IA64 */

        //  Initialize the "big-block" heap first.

        if ( (_crtheap = HeapCreate( mtflag ? 0 : HEAP_NO_SERIALIZE,

                                     BYTES_PER_PAGE, 0 )) == NULL )

            return 0;

#ifndef _WIN64

        // Pick a heap, any heap

        __active_heap = __heap_select(); <-- break point

        if ( __active_heap == __V6_HEAP )

그럼, winmain()이 실행되기전, PE의 entry point에 포함된 코드(즉, VC++ Stub Code)가 실행되는 과정에서 위 함수가 호출되게 됩니다. 즉, PE가 시작될 때, Visual C++ Runtime library에서 winmain 실행되기 전에 heap을 초기화(즉, init)부터 시작하게 됩니다. (Runtime Library가 Multi-threaded Debug DLL (/MDd)인 경우에만 확인가능합니다.)

위 코드에서 녹색 부분인 _crtheap = HeapCreate(...)이 있는데, 전역 변수인 _crtheap을 초기화하고 있습니다. 갑자기 _crtheap을 적어둔 이유는, C Runtime 함수인 malloc은 내부에서 _crtheap을 사용하기 때문입니다. 아래의 붉은 부분을 참고하세요(malloc.c).

__forceinline void * __cdecl _heap_alloc (size_t size)

{

#ifndef _WIN64

    void *pvReturn;

#endif  /* _WIN64 */

    if (_crtheap == 0) {

        _FF_MSGBANNER();    /* write run-time error banner */

        _NMSG_WRITE(_RT_CRT_NOTINIT);  /* write message */

        __crtExitProcess(255);  /* normally _exit(255) */

    }

#ifdef _WIN64

    return HeapAlloc(_crtheap, 0, size ? size : 1);

#else  /* _WIN64 */

    if (__active_heap == __SYSTEM_HEAP) {

        return HeapAlloc(_crtheap, 0, size ? size : 1);

    } else

    if ( __active_heap == __V6_HEAP ) {

        if (pvReturn = V6_HeapAlloc(size)) {

            return pvReturn;

        }

즉, malloc에서 사용되는 heap은 _crtheap이며, 이는 Private heap(즉, HeapCreate)을 사용함이 확인됩니다. 그런데, 궁금한 것이 위 녹색 부분으로 __SYSTEM_HEAP이 active됨인 경우라는 if 조건문이 있다는 점입니다.

그럼 다시, 디버깅을 통해 확인해 보도록 하겠습니다.

우선, __heap_select()내부로 들어와 디버깅해 보면,

int __cdecl __heap_select(void)

{

        char *env_heap_type = NULL;

#ifdef CRTDLL

        DWORD HeapStringSize=0;

        DWORD actual_size=0;

        char *cp=NULL;

        char *env_heap_select_string = NULL;

        int heap_choice=0;

#endif  /* CRTDLL */

#ifdef CRTDLL

        // First, check the environment variable override

        if (HeapStringSize = GetEnvironmentVariableA(__HEAP_ENV_STRING, ...

        {

            env_heap_select_string = HeapAlloc(GetProcessHeap(), 0, ...

            if (env_heap_select_string)

            {

                ...

위 코드들을 분석하면, 우선 환경 변수를 체크하여 몇몇 논리를 실행한다음, active_heap을 리턴하는 구조입니다. 아래와 같이, batch file을 만들어 실행하면, active_heap을 변경하여 실행할 수 있습니다.

set __MSVCRT_HEAP_SELECT=__GLOBAL_HEAP_SELECTED, 1

"C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE\devenv.exe"

__GLOBAL_HEAP_SELECTED 뒤의 숫자는,

#define __SYSTEM_HEAP           1

#define __V5_HEAP               2

#define __V6_HEAP               3

의 값으로 정의됩니다. 즉, system heap을 사용하고 싶으면 1을 전달하면 됩니다(기본값).

V5나 V6 Heap은 잘 사용되지 않지만, 효율과 관련있다고 하는데, 자세한건 검색해 보시기 바랍니다.

여하튼, 특이한건, _heap_init이 호출되기 전에는 malloc류의 함수를 사용할수 없다는 점입니다. 왜냐하면, 전역 변수인 _crtheap이 초기화되지 않았기 때문입니다. 만일, heap을 초기화하는 과정에서, 동적 메모리 할당이 필요한 경우 어떻해야 할까요? 물론, malloc은 사용할 수 없는 상태인데 말이죠. 그때 바로 Process heap이 사용됩니다. 즉, 위 코드의 푸른색 부분을 보면, 내부 버퍼 할당을 위한 HeapAlloc 함수에 GetProcessHeap 결과를 전달하고 있습니다. 즉, Process Heap은 프로그램의 전체 Heap 운영을 위한다기 보다는, 프로그램 시작시 실행전에 프로그램의 운영을 위한 초기화 작업시 필요한 동적 할당 메모리의 생성시 사용됨이 확인됩니다. 물론, GetProcessHeap() 대신, CreateHeap()을 전달하여 Private heap을 전달할 수도 있을것 같은데, ... 그래도 Process heap을 사용하는 것이 설계 원칙에 부합하는 내용일 듯 합니다.

Heap 연속성, 단편화

Heap은 선형적인 Virtual Memory에 할당/해제를 통해 유지되는데, 호출 빈드가 높다면, 중간 중간 작은 영역이 비할당되고, 더이상 큰 영역이 할당될 수 없는 상태에 도달할 수 있는데, 이는 간단히 단편화라고 표현할 수 있습니다(최근 OS에서는 그리 발생할 빈도는 높지 않다고 합니다.)

어떻든, 아래 코드를 실행해 봅니다.

int _tmain(int argc, _TCHAR* argv[])

{

HANDLE h1 = NULL;

HANDLE h2 = NULL;

LPVOID p = NULL;

// Heap Fragmentation

printf("*** heap fragmentation\r\n");

{

h1 = HeapCreate(0, 1*1000*1000, 0);

p = HeapAlloc(h1, 0, 1000);

printf("[h1]  1K heap addr=0x%x\r\n", p);

h2 = HeapCreate(0, 1*1000*1000, 0);

p = HeapAlloc(h2, 0, 1000);

printf("[h2]  1K heap addr=0x%x\r\n", p);

p = HeapAlloc(h1, 0, 10*1000*1000);

printf("[h1] 10M heap addr=0x%x\r\n", p);

p = HeapAlloc(h1, 0, 1000);

printf("[h1]  1K heap addr=0x%x\r\n", p);

}

getche();

}

그리고, 실행하면 아래와 같습니다.(그 값은 매번 변경될 수 있습니다.)

*** heap fragmentation

[h1]  1K heap addr=0x77f7e0

[h2]  1K heap addr=0x8ff7e0

[h1] 10M heap addr=0x980020

[h1]  1K heap addr=0x77fbe0

즉, 1KB 크기의 메모리를 Heap 1에서, 1KB 크기의 메모리를 Heap 2에서 할당받습니다.

이를 통해, Heap 1은 0x77~에서, Heap 2는 0x8FF~에서 시작됨을 확인할 수 있습니다.

Heap 1에서, 10MB의 큰 크기를 할당받는다고 하면, 즉, Heap의 생성 크기인 1M 보다 큰 영역을 할당하려고 한다면, 당연히 다른 영역, 0x98~에 10MB의 크기의 메모리를 할당받았습니다.

그렇다면, 메모리의 위치는 아래와 같습니다.

여기서 확인가능한 것은, 하나의 Heap은 반드시 연속하지는 않는다는 점입니다. 즉, Heap 1은 연속된 메모리로 구성되지 않고, 중간에 뻥~ 뚤린채, 더군다나 다른 Heap인 h2도 포함될 수 있다는 점입니다. 

그럼 마지막으로 Heap 1에 1KB 메모리를 할당하고자 한다면, 어느 영역이 사용될까요? 0x77F7E0 근처에? 아니면, 0x980020 근처(사실, 10MB 뒤)에? 아니면, 아예 다른 영역에? 결론은, 0x77FBE0 근처, 즉, 0x77FBE0가 사용됨이 확인됩니다.

이와 같이 Heap은 단일 node가 아닌 linked list형태로 구현됨이 확인되며, 임의의 공간을 할당하기 위해서는, 선두의 비어 있는 영역이 사용됨이 확인됩니다(이는 heap 할당 알고리즘에 따라 변경가능).

여기서 확인하고자 하는 바는, 이와 같이 linked list로 구성된 heap이, 중간 중간 할당과 해제가 반복되다 보면, 단편화가 발생하여, 남은 전체 공간은 충분한데, 더이상 할당하지 못하는 상태가 발생하게 됩니다. 물론, disk인 경우, 조각모음을 하면 될거 같지만, 메모리인 경우, 이미 프로그램에의해 해당 주소를 사용하고 있기 때문에, 쉽게 메모리 단위(page)를 move하지도 못합니다. OS 발전에 따라, 빈도는 줄었다고는 하나, 이론적으로 충분히 가능한 얘기이니, 주의하여 작업하여야 합니다.

Heap의 사용?

앞선 설명처럼, Heap은 _crtheap이라는 시스템 heap(Private heap)이 사용된다고 확인하였습니다. 그럼, 어느 경우에 _crtheap으로 구성된 malloc 말고, 직접 다른 private heap을 사용할 수 있을까요?

일단, malloc은 heap lock을 발생시킵니다. 즉, malloc이 2개 이상의 thread에 의해 동시에 실행된다면, 하나의 thread는 block, 즉, wait하게 됩니다. 만일, 총 2개의 thread가 동작중인 프로그램을 설계하는데, thread간에 메모리 공유가 없다고 가정한다면, malloc에 의한 lock은 필요하지 않게 됩니다. 그런 경우, malloc대신, 각 thread마다 CreateHeap을한것을 HeapAlloc하여 사용한다면, thread간 lock없이 최대 성능을 만들어 낼 수 있습니다. 물론, Heap 생성시 HEAP_NO_SERIALIZE flag를 사용해야 합니다.

또라는 장점으로, 복잡한 메모리 해제 코드를 한방에 해결할 수 있다는 점입니다. 만일, Linked list나 Queue 혹은 Tree와 같은 object를 구현하여 유지하다보면, malloc과 free가 빈번히 발생하게 됩니다. 메모리 단편화도 물론 걱정되구요. 그리고, 해당 object의 사용이 끝나서 해제하는 경우, for나 while등을 이용하여 일일이 node 하나하나 해제해야 합니다. 이러한 부하 없이, 즉, node 하나하나 해제 없이 간단히 HeapDestroy 한번에 모든것을 다 해제할 수 있습니다. 즉, node가 100,000개 있다면, 100,000번 loop를 수행해야 하지만, HeapDestroy를 사용한다면, 한번의 호출로 모두 삭제가 가능해 진다는 뜻입니다. 더군다나 메모리 해제 코드의 버그로 인한 Memory leak도 상당부분 해결할 수 있습니다.