메모리 할당의 본질

들어가며

메모리 할당은 모든 프로그램의 기초다. malloc과 free는 매일 호출되지만, 그 내부에서 무엇이 일어나는지는 잘 알려져 있지 않다. free()는 어떻게 해제할 크기를 알아내는가? 왜 malloc은 64비트 시스템에서 16바이트 정렬을 보장하는가? 디버그 빌드의 0xCD, 0xDD 패턴은 무엇을 위한 것인가?

이 글은 그 질문들을 하드웨어 제약과 캐시 라인부터 차근차근 풀어낸다. 블록 헤더와 boundary tag, 정렬과 SIMD, false sharing, 디버그 매직 넘버, 그리고 메타데이터를 들고 다니는 자료구조의 일반적 패턴까지 다룬다. 이 글에서 다지는 기초가 이후의 할당자, 컨테이너, 동기화 글의 토대가 된다.

---

목차

1. malloc/free의 내부 동작
2. 메모리 정렬
3. 할당과 False Sharing
4. 디버그 매직 넘버
5. 메모리 누수 추적
6. Arena와 String Builder의 유사성

---

1. malloc/free의 내부 동작

C 표준 라이브러리의 메모리 할당 함수를 보면 흥미로운 비대칭성이 있다:

void* malloc(size_t size);  // 크기를 명시적으로 전달
void free(void* ptr);        // 크기 정보가 없다!

free(ptr)는 어떻게 해제할 메모리 블록의 크기를 알 수 있을까? 답은 메타데이터에 있다.

Block Header 구조

대부분의 메모리 할당자는 사용자에게 반환하는 포인터 직전에 블록 헤더(block header)를 숨겨둔다. glibc의 malloc 구현을 간략화하면 다음과 같다:

struct malloc_chunk {
    size_t      prev_size;  // 이전 청크가 free 상태일 때만 사용
    size_t      size;       // 현재 청크 크기 + 플래그 비트
    // 사용자 데이터가 여기서 시작
};

malloc(100)을 호출하면 실제로는:

[Header: 16 bytes][User Data: 100+ bytes]
                  ^
                  malloc이 반환하는 포인터

이 구조 덕분에 free(ptr)는 간단한 포인터 산술로 헤더에 접근할 수 있다:

void free(void* ptr) {
    if (!ptr) return;

    // 포인터를 헤더 위치로 역산
    struct malloc_chunk* chunk = (struct malloc_chunk*)ptr - 1;
    size_t size = chunk->size & ~FLAGS_MASK;  // 플래그 비트 제거

    // 메모리 해제 로직...
}

(ptr - 1)의 의미는 무엇인가? C에서 포인터 산술은 타입의 크기만큼 이동한다. struct malloc_chunk*로 캐스팅된 상태에서 -1은 정확히 한 구조체 크기(16바이트) 뒤로 이동한다.

Boundary Tags: Knuth의 통찰

Donald Knuth는 1962년 "The Art of Computer Programming"에서 boundary tag 기법을 제안했다. 블록의 앞뒤에 크기 정보를 중복 저장하여 인접 블록 병합(coalescing)을 $O(1)$에 수행할 수 있게 만든 것이다:

[Header: size=100][User Data][Footer: size=100]

현대의 glibc malloc은 이를 최적화하여, free 블록만 footer를 유지한다. 할당된 블록은 헤더의 플래그 비트로 상태를 표시한다:

#define PREV_INUSE  0x1  // 이전 청크가 사용 중
#define IS_MMAPPED  0x2  // mmap으로 할당됨
#define NON_MAIN_ARENA 0x4

크기 필드의 하위 3비트를 플래그로 사용할 수 있는 이유는? 메모리 정렬 때문이다.

2. 메모리 정렬: CPU가 정렬을 요구하는 이유

하드웨어 관점: 메모리 버스의 제약

현대 CPU는 메모리를 워드(word) 단위로 읽는다. 64비트 시스템에서 한 번의 메모리 읽기는 8바이트를 가져온다. 메모리 주소 0x1000에서 8바이트를 읽으면:

Address:  0x1000 0x1001 0x1002 ... 0x1007
          [---- 8-byte word ----]

만약 4바이트 정수가 주소 0x1001에 정렬되지 않은 채로 저장되어 있다면?

0x1000: [XX][AA BB CC DD][...]
           ↑
        정렬되지 않은 int

CPU는 두 번의 메모리 읽기를 수행해야 한다:
1. 0x1000-0x1007 읽기 → AA, BB, CC 획득
2. 0x1008-0x100F 읽기 → DD 획득
3. 비트 시프트와 마스킹으로 재조합

x86-64는 이를 자동으로 처리하지만 성능 패널티가 있다. ARM과 MIPS 같은 일부 아키텍처는 정렬되지 않은 접근 시 하드웨어 예외를 발생시킨다.

플랫폼별 기본 정렬

glibc malloc은 다음과 같은 정렬을 보장한다:

• 32비트 시스템: 8바이트 정렬 (most restrictive type: long long, double)
• 64비트 시스템: 16바이트 정렬 (SIMD 타입 __m128 지원)

이것이 바로 블록 크기의 하위 3~4비트가 항상 0이고, 따라서 플래그 비트로 재사용할 수 있는 이유다.

Microsoft의 CRT debug heap은 8바이트 정렬을 사용한다:

#define nNoMansLandSize 4

typedef struct _CrtMemBlockHeader {
    struct _CrtMemBlockHeader* pBlockHeaderNext;
    struct _CrtMemBlockHeader* pBlockHeaderPrev;
    char* szFileName;
    int nLine;
    size_t nDataSize;
    int nBlockUse;
    long lRequest;
    unsigned char gap[nNoMansLandSize];  // 0xFD 패턴
    // 사용자 데이터
    // unsigned char gap[nNoMansLandSize];  // 후행 가드
} _CrtMemBlockHeader;

SIMD 정렬 요구사항

SIMD(Single Instruction Multiple Data) 명령어 중 aligned load/store 변종은 더 엄격한 정렬을 요구한다.

• SSE (movaps/movapd): 16바이트 정렬 필수
• AVX (vmovaps/vmovapd): 32바이트 정렬 필수
• AVX-512: 64바이트 정렬 필수

정렬되지 않은 데이터에 movaps를 사용하면 #GP(0) 일반 보호 fault가 발생한다(현대 OS에서는 SIGSEGV로 사용자에게 노출된다). 같은 SSE/AVX 명령군에는 unaligned 변종(movups/vmovups)이 별도로 있어 정렬되지 않은 주소도 동작한다. unaligned 명령은 과거에는 aligned 버전보다 느렸지만, Nehalem 이후의 인텔 CPU와 그에 대응하는 AMD CPU에서는 주소가 실제로 정렬된 경우 에 한해 두 명령의 비용이 거의 같다. 정렬이 깨지면 unaligned가 손해를 본다.

malloc 정렬의 본질은 SIMD 한 가지가 아니다. C/C++ 표준은 malloc이 어떤 표준 타입의 객체에도 적합한 정렬 을 보장하도록 요구한다. C에서는 _Alignof(max_align_t)(보통 16바이트), C++17 이후의 운영체제 메모리 할당자는 __STDCPP_DEFAULT_NEW_ALIGNMENT__(보통 16바이트)에 맞춘 주소를 돌려준다. SIMD 정렬은 이 보장 안에 자연스럽게 포함된다.

워드 크기 vs malloc 정렬: 혼동하기 쉬운 개념

두 개념은 다르다:

개념	의미	64비트에서
워드 크기	CPU 기본 연산 단위	8바이트
malloc 정렬	반환 주소가 N의 배수임을 보장	16바이트

CPU는 일반 MOV 명령으로 8바이트 단위로 읽지만, malloc이 16바이트 정렬을 보장하는 이유는 SIMD 때문이다:

__m128 simd_vec;      // SSE: 16바이트 정렬 필수
long double;          // 일부 플랫폼에서 16바이트

malloc은 "어떤 타입이든 안전하게 저장 가능"해야 하므로, 가장 까다로운 정렬 요구사항(16바이트)을 만족시킨다. 16바이트 정렬이면 8바이트 정렬도 자동으로 만족한다(16은 8의 배수).

16바이트 정렬: 주소가 0x10의 배수
  → 0x1000, 0x1010, 0x1020 ... ✓
  → 0x1008 ... ✗

8바이트 정렬: 주소가 0x8의 배수
  → 0x1000, 0x1008, 0x1010 ... ✓

커스텀 정렬 할당 구현: _aligned_malloc의 원리

만약 커스텀 할당자가 8바이트 정렬만 보장한다면 SIMD를 어떻게 쓸 수 있을까? 두 가지 방법이 있다:

1. Unaligned 명령어 사용: movups는 정렬 상관없이 동작한다. 현대 x86-64에서 성능 패널티가 거의 없다.
2. 정렬 할당 함수 별도 제공: 표준 라이브러리도 이 방식을 쓴다.

// POSIX
posix_memalign(&ptr, 16, size);
aligned_alloc(16, size);        // C11

// Windows
_aligned_malloc(size, 16);
_aligned_free(ptr);             // 반드시 짝으로!

Windows에서 _aligned_malloc으로 할당한 메모리는 반드시 _aligned_free로 해제해야 한다. 일반 free를 쓰면 힙 손상이 발생한다. 왜 그럴까?

문제: 정렬된 주소와 실제 할당 주소가 다르다

void* raw = malloc(...);         // 실제 할당 주소: 0x1004
void* aligned = ...;             // 정렬된 주소: 0x1010

return aligned;  // 사용자는 0x1010만 안다

나중에 free(0x1010)을 호출하면? 실제로 해제해야 할 건 0x1004인데, 그 정보가 없으면 해제할 수 없다.

해법: 원본 포인터를 정렬된 주소 직전에 저장

raw = 0x1004 (malloc 반환)

0x1004  [------------ 할당된 영역 ------------]
        [여유][원본 ptr][   사용자 데이터    ]
              ↓
0x1008  [0x1004]        ← raw 포인터 저장 (8바이트)
0x1010                  [데이터 시작] ← 16바이트 정렬됨
                         ↑
                    사용자에게 반환

"여유" 공간(0x1004~0x1007)은 정렬을 맞추다 남은 공간이다. 포인터는 aligned - 8 위치에 고정되어야 free 시 찾을 수 있으므로, 남는 공간이 자연스럽게 앞쪽에 생긴다.

구현

void* my_aligned_malloc(size_t size, size_t align) {
    // 1. 넉넉하게 할당
    //    - size: 실제 데이터
    //    - align - 1: 정렬 맞추기 위한 여유분 (최악의 경우)
    //    - sizeof(void*): 원본 포인터 저장 공간
    void* raw = malloc(size + align - 1 + sizeof(void*));
    if (!raw) return NULL;

    // 2. 정렬된 주소 계산
    //    - raw + sizeof(void*): 포인터 저장 공간 확보 후
    //    - + align - 1, & ~(align - 1): 올림하여 align 배수로
    uintptr_t aligned = ((uintptr_t)raw + sizeof(void*) + align - 1)
                        & ~(align - 1);

    // 3. aligned 직전에 원본 포인터 저장
    ((void**)aligned)[-1] = raw;

    return (void*)aligned;
}

void my_aligned_free(void* aligned) {
    if (!aligned) return;
    void* raw = ((void**)aligned)[-1];  // 저장해둔 원본 꺼냄
    free(raw);
}

비트 마스킹으로 정렬하기

align = 16 = 0b00010000
align - 1  = 0b00001111
~(align-1) = 0b11110000

주소 & ~(align-1) → 하위 4비트를 0으로 → 16의 배수로 내림

예를 들어 raw = 0x1004, align = 16일 때:

(0x1004 + 8 + 15) & ~15
= 0x101B & 0xFFF0
= 0x1010  ← 16바이트 정렬된 주소

3. 할당과 False Sharing

메모리 할당자가 만들어준 두 변수가 우연히 같은 캐시 라인에 들어가면 멀티스레드 환경에서 성능이 무너진다. 이 현상이 false sharing이다. 캐시 일관성 프로토콜(MESI)이 한 캐시 라인을 단위로 동작하기 때문에, 서로 다른 변수를 쓰는 두 스레드가 같은 라인을 두고 캐시 무효화를 주고받는다.

struct Counter {
    long count1;   // 스레드 1이 사용
    long count2;   // 스레드 2가 사용
};                 // 두 변수가 같은 64바이트 캐시 라인에 있음

스레드 1이 count1을 수정하면 CPU1의 해당 캐시 라인이 dirty가 되고, CPU2의 같은 라인은 invalidate된다. CPU2가 count2를 읽으려 하면 캐시 미스가 나서 메인 메모리에서 재로드해야 한다(약 100 cycle).

해결책은 패딩으로 변수를 다른 캐시 라인에 떨어뜨리는 것이다.

struct Counter {
    long count1;
    char padding1[64 - sizeof(long)];
    long count2;
    char padding2[64 - sizeof(long)];
};

C++17은 이를 표준화했다.

struct alignas(64) Counter {
    long count1;
};

std::hardware_destructive_interference_size도 같은 목적으로 사용할 수 있다. 할당자가 객체를 64의 배수 주소에 배치하도록 정렬을 맞추면, 서로 다른 객체가 같은 캐시 라인을 공유하지 않는다. 이것이 멀티스레드 친화적 풀 할당자가 객체마다 캐시 라인을 패딩하는 이유다.

4. 디버그 매직 넘버: 버그를 보이게 만들기

Microsoft Visual C++ Runtime은 디버그 빌드에서 특정 패턴으로 메모리를 초기화한다:

MSVC Debug Heap 패턴

패턴	의미	16진수 값
Clean Memory	스택 메모리 (초기화 안 됨)	0xCC
Dead Memory	해제된 힙 메모리	0xDD
No Man's Land	버퍼 오버플로우 감지용 가드	0xFD
Allocated Memory	새로 할당된 메모리	0xCD
Bad Food	32비트 0xBAADF00D	커밋되지 않은 메모리
Feee Feee	32비트 0xFEEEFEEE	OS로 반환된 메모리

이 패턴들은 단순히 0으로 초기화하는 것보다 훨씬 강력하다.

왜 0x00이 아닌가?

1. NULL 포인터 역참조 감지: 0xCCCCCCCC는 유효하지 않은 주소로, 즉시 segfault를 발생시킨다.
2. 초기화 안 된 변수 발견: if (value == 0xCDCDCDCD) 같은 조건이 우연히 참이 될 확률이 매우 낮다.
3. 버퍼 오버런 감지: 메모리 블록 앞뒤의 0xFD 패턴이 변경되었는지 검사한다.

Microsoft Learn의 CRT Debug Heap 문서는 다음과 같이 설명한다:

"The debug heap fills newly allocated memory with 0xCD and freed memory with 0xDD to help identify use-after-free bugs."

실제 구현 예시:

void* debug_malloc(size_t size) {
    size_t total = sizeof(Header) + size + 2 * NO_MANS_LAND;
    void* ptr = HeapAlloc(GetProcessHeap(), 0, total);

    Header* header = (Header*)ptr;
    header->size = size;
    header->magic = 0xABCD;

    // No man's land (전방 가드)
    memset(header + 1, 0xFD, NO_MANS_LAND);

    // 사용자 영역 (초기화 안 됨 표시)
    void* user = (char*)(header + 1) + NO_MANS_LAND;
    memset(user, 0xCD, size);

    // No man's land (후방 가드)
    memset((char*)user + size, 0xFD, NO_MANS_LAND);

    return user;
}

0xCC의 특별한 의미

x86 아키텍처에서 0xCC는 INT 3 명령어(디버거 breakpoint)다. 초기화되지 않은 함수 포인터가 0xCCCCCCCC를 가리키고 호출되면, CPU는 즉시 디버거 트랩을 발생시킨다.

5. 메모리 누수 추적: __FILE__과 __LINE__ 매크로

왜 매크로인가?

메모리 누수를 추적하려면 할당 위치를 기록해야 한다. 함수로는 불가능하다:

void* tracked_malloc(size_t size, const char* file, int line) {
    printf("Allocation at %s:%d\n", file, line);
    return malloc(size);
}

// 사용
void* p = tracked_malloc(100, __FILE__, __LINE__);  // OK, 하지만 번거로움

매크로를 사용하면 호출 지점의 정보를 자동으로 삽입할 수 있다:

#define MALLOC(size) tracked_malloc(size, __FILE__, __LINE__)

void* p = MALLOC(100);  // 자동으로 파일명과 행 번호 전달

Microsoft CRT는 이를 더 우아하게 처리한다:

#ifdef _DEBUG
#define malloc(size) _malloc_dbg(size, _NORMAL_BLOCK, __FILE__, __LINE__)
#define free(ptr) _free_dbg(ptr, _NORMAL_BLOCK)
#endif

C++20 std::source_location

C++20은 이를 표준 라이브러리로 제공한다:

#include <source_location>

void* tracked_new(
    size_t size,
    std::source_location loc = std::source_location::current()
) {
    std::cout << "Allocation at "
              << loc.file_name() << ":"
              << loc.line() << " in "
              << loc.function_name() << "\n";
    return ::operator new(size);
}

// 사용
auto p = tracked_new(100);  // 매크로 없이 위치 추적!

std::source_location::current()는 기본 인자로 평가되므로, 호출 지점의 정보를 자동으로 캡처한다. cppreference는 이를 "매크로의 타입 안전한 대안"이라고 설명한다.

실전 메모리 프로파일러

James Golick의 "Memory Allocators 101"에서 제안하는 간단한 프로파일러:

typedef struct {
    void* addr;
    size_t size;
    const char* file;
    int line;
} AllocInfo;

#define MAX_ALLOCS 10000
AllocInfo g_allocs[MAX_ALLOCS];
int g_alloc_count = 0;

void* debug_malloc(size_t size, const char* file, int line) {
    void* ptr = malloc(size);
    if (g_alloc_count < MAX_ALLOCS) {
        g_allocs[g_alloc_count++] = (AllocInfo){ptr, size, file, line};
    }
    return ptr;
}

void debug_free(void* ptr) {
    for (int i = 0; i < g_alloc_count; i++) {
        if (g_allocs[i].addr == ptr) {
            g_allocs[i] = g_allocs[--g_alloc_count];  // 제거
            break;
        }
    }
    free(ptr);
}

void print_leaks() {
    for (int i = 0; i < g_alloc_count; i++) {
        printf("Leak: %zu bytes at %s:%d\n",
               g_allocs[i].size, g_allocs[i].file, g_allocs[i].line);
    }
}

Valgrind와 AddressSanitizer는 이 개념을 극단까지 밀어붙여, 모든 메모리 접근을 추적하고 invalid access를 실시간으로 탐지한다.

6. Arena와 String Builder의 유사성

지금까지 살펴본 메모리 할당의 핵심은 "상태(메타데이터)를 어디에 저장하느냐"였다. Block header에 크기를 박고, free list 헤드를 들고 다니고, 마지막 사용 위치를 offset으로 기억한다. 같은 발상이 자료구조 전반에 반복된다.

class Arena {
    char* buffer;
    size_t offset;     // 현재 위치를 기억해 탐색을 제거
public:
    void* allocate(size_t size) {
        void* ptr = buffer + offset;
        offset += size;
        return ptr;
    }
};

class StringBuilder {
    char* buffer;
    size_t length;     // 현재 길이를 기억해 끝 탐색을 제거
public:
    void append(const char* s, size_t len) {
        memcpy(buffer + length, s, len);
        length += len;
    }
};

둘 다 마지막 위치를 멤버로 들고 있다. Arena는 그것을 다음 할당의 시작 주소로, StringBuilder는 다음 문자열 추가의 시작 주소로 사용한다. C 스타일 strcat이 매 호출마다 \0을 다시 찾아 누적 $O(n^2)$가 되는 것과 같은 문제를, 같은 방식으로 푼다. 메모리 할당자가 free list 탐색을 피하기 위해 cached free pointer를 두는 것도 같은 원리다.

이 글에서 다룬 메타데이터의 위치, 정렬, 캐시 라인이라는 세 가지 축은 자료구조와 알고리즘 모두에 등장한다. 같은 압력을 만나면 같은 형태의 해법이 나오는 셈이다.

---

결론

메모리 할당은 단순한 API가 아니라 하드웨어 제약, 성능 최적화, 디버깅 편의성이 얽힌 시스템이다. free()가 크기 정보 없이 동작하는 비밀은 사용자 포인터 직전의 block header에 있고, 16바이트 정렬은 SIMD가 강요한 하한이다. False sharing은 캐시 라인을 단위로 일관성을 유지하는 MESI 프로토콜의 부산물이고, 0xCD/0xDD 같은 디버그 패턴은 초기화 누락과 use-after-free를 즉시 가시화하기 위한 약속이다. 마지막으로, Arena와 String Builder가 같은 형태의 코드를 공유하는 데서 메타데이터 위치와 탐색 제거라는 일반 원리가 보였다.

이 글은 단일 객체 단위의 할당을 다뤘다. 다음 단계는 그 객체들이 어디에 어떻게 놓이는지, 즉 메모리 계층과 캐시의 구조다.

더 읽을거리

공식 문서

• Microsoft Learn: BSTR
• Microsoft Learn: CRT Debug Heap Details
• Microsoft Learn: HeapAlloc function
• cppreference: std::source_location
• Intel 64 and IA-32 Architectures Optimization Reference Manual

기술 논문 및 서적

• Ulrich Drepper, "What Every Programmer Should Know About Memory", 2007
• Joel Spolsky, "Back to Basics", 2001
• Donald Knuth, "The Art of Computer Programming, Volume 1: Fundamental Algorithms", Section 2.5 (Dynamic Storage Allocation)
• James Golick, "Memory Allocators 101 - Write a simple memory allocator"

소스 코드 분석

• glibc malloc implementation (malloc/malloc.c)
• jemalloc documentation
• mimalloc by Microsoft Research

도구

• Valgrind Memcheck
• AddressSanitizer (ASan)
• HeapTrack