A memory Allocator (Doug Lea의 글) (dlmalloc)

https://gee.cs.oswego.edu/dl/html/malloc.html

오래된 글이지만 유용한 개념같아 번역하여 정리해둔다.

해당 내용은 매우 오래되었으며, malloc의 현재 버전에 대한 세부 정보를 반영하지 않음에 유의 (그래도 ptmalloc의 기본 알고리즘은 dlmalloc과 흡사하게 작동함)

Introduction

---

메모리 할당자는 인프라 소프트웨어 엔지니어링에서 흥미로운 case study를 형성한다. 나(Doug Lea)는 1987년에 하나를 작성하기 시작했고, 이 할당자는 malloc(), free()의 구현, realloc()과 몇가지 보조 유틸리티 루틴을 제공한다.

할당자는 특정 이름을 받은 적은 없지만, 대부분의 사람들은 이를 Doug Lea’s Malloc 또는 줄여서 dlmalloc이라고 부른다.

이 할당자에 대한 코드는 퍼블릭 도메인에 공개되었으며, 널리 사용되고 있는 것으로 보인다. 이 코드는 일부 Linux 버전에서 malloc의 기본 네이티브 버전으로 제공되며, 일반적으로 사용 가능한 여러 소프트웨어 패키지(네이티브 malloc을 재정의)에 컴파일되었으며, 내가 모르는 다른 많은 곳에서 사용되었다.

 

나는 동적 메모리 할당에 거의 전적으로 의존하는 C++ 프로그램을 작성한 후 할당자의 첫번째 버전을 작성하였다. 예상보다 훨씬 느리게 실행되거나 총 메모리 소비량이 훨씬 더 많다는 것을 알게 되었다. 이는 내가 실행중이던 시스템(주로 당시 최신 버전의 SunOs 및 BSD)의 메모리 할당자의 특성 때문이었다. 이를 해결하기 위해 처음에는 C++에서 다양한 클래스에 대해 operator new를 오버로딩하여 여러 특수 목적 할당자를 작성했다. 이 중 일부는 1989년 C++ 보고서에 실린 “Some storage allocation techniques for container classes“이라는 기사로 각색된 논문에서 설명되었다.

 

하지만, 나는 동적으로 할당되고 자주 사용되는 클래스마다 특수 할당기를 구축하는 것은 내가 당시 작성중이던 범용 프로그래밍 지원 클래스를 구축할 때 좋은 전략이 아님을 곧 깨달았다.(1986년 부터 1991년까지 나는 GNU C++ 라이브러리(libg++)의 주요 작성자였다.) 보다 넓은 해결책이 필요했는데, 이는 C++ 및 C의 일반적인 로드에서 충분히 성능이 좋은 할당기를 작성하는 것이었다. 이렇게 하면 프로그래머들이 매우 특별한 조건을 제외하고는 특수 목적의 할당기를 작성하려는 유혹을 느끼지 않을 것이다.

 

이 글에서는 이 할당기의 주요 설계 목표, 알고리즘, 구현 고려사항에 대한 설명을 제시한다. 보다 자세한 문서는 코드 배포본과 함께 제공된다.

 

Goals

---

좋은 메모리 할당기는 다음과 같은 목표를 균형 있게 고려해야 한다.

• 호환성 극대화(Maximizing compatibility)
  • 할당기는 다른 할당기와 플러그-호환성(plug-compatible)을 가져야하며, 특히 ANSI/POSIX 규격을 준수해야 한다.
• 이식성 극대화(Maximizing Portability)
  • 시스템 종속적인 기능(e.g., system call)에 대한 의존성을 최소화하면서, 특정 시스템에만 제공되는 유용한 기능은 선택적으로 지원해야 한다.
  • 정렬 및 주소지정 규칙과 같은 모든 알려진 시스템 제약 조건을 준수해야 한다
• 공간 최소화(Minimizing Space)
  • 할당기는 공간 낭비를 최소화해야한다.
  • 시스템에서 메모리를 가능한 적게 가져와야 하며, 메모리를 유지 관리할 때 프로그램이 사용하지 않는 청크의 단편화(fragmentation)을 최소화해야 한다.
• 시간 최소화(Minimizing Time)
  • malloc(), free(), realloc() 루틴은 평균적인 경우 가능한 빨라야 한다 .
• 튜닝 가능성 극대화(Maximizing Tunability)
  • 선택적 기능과 동작은 사용자가 정적(e.g., #define 등) 또는 동적(e.g., mallopt 와 같은 제어명령)으로 제어할 수 있어야 한다.
• 지역성 극대화(Maximizing Locallity)
  • 일반적으로 함께 사용되는 메모리 청크를 서로 가까운 위치에 할당해야 한다. 이는 프로그램 실행 중 페이지 및 캐시 미스를 최소화하는데 도움이 된다.
• 오류 감지 극대화(Maximizing Error Detection)
  • 일반적인 할당자가 Purify와 같은 일반적인 메모리 오류 테스트 도구로도 사용되기는 어렵지만, 할당자는 메모리 덮어쓰기, 다중 해제 등으로 발생하는 손상을 감지하는 수단을 제공해야 한다.
• 이상 현상 최소화(Minimizing Anomalies)
  • 기본 설정으로 구성된 할당자는 동적 할당에 크게 의존하는 실제 워크로드(e.g., 윈도잉 툴킷, GUI 어플리케이션, 컴파일러, 인터프리터, 개발 도구, 네트워크 패킷 집중 프로그램, 그래픽 집중 패키지, 웹 브라우저, 문자열 처리 애플리케이션)에서 잘 동작해야 한다.

 

참고

Paul Wilson과 그의 동료들은 이러한 목표 중 일부를 더 자세히 논의하는 훌륭한 할당 기술 서베이 논문을 작성했다. 이 논문은

Paul R. Wilson, Mark S. Johnstone, Michael Neely, and David Boles, ``Dynamic Storage Allocation: A Survey and Critical Review'' in International Workshop on Memory Management, September 1995

이다.

Winson et al. 이 논의한 바와 같이 어떠한 할당자에서도 공간 낭비(주로 단편화에 의한)를 최소화하는 것이 가장 중요한 목표여야 한다.

극단적인 예

가장 빠른 버전의 malloc() 중 하나는 시스템에서 사용할 수 있는 다음 연속 메모리 위치를 항상 할당하는 방식으로 구현된다. 이 경우, 가장 빠른 free()는 아무 작업도 하지 않는다.

하지만 이러한 구현은 거의 받아들여질 수 없다. 이는 사용하지 않는 공간을 절대 회수하지 않으므로, 프로그램이 메모리를 빠르게 소진하게 된다. 실제 사용되는 일부 할당자에서 특정 워크로드는 이와 비슷한 극단적인 낭비가 발생할 수 있다. Wilson이 지적한 바와 같이, 낭비는 금전적으로 측정할 수도 있다.

전 세계적으로 보면, 잘못된 할당 방식은 메모리 칩에서 수십억 달러의 손실을 초래할 수 있다.

 

Trade-off 예시

시간과 공간 문제는 지배적인 요소이지만, Trade-off와 절충안의 조합은 거의 무한하다. 다음은 많은 사례 중 몇가지 예시이다:

• 최악의 정렬 요구 사항을 수용하는 것은 청크를 정렬하기 위해 할당자가 바이트를 건너뛰도록 강제하여 낭비를 증가시킨다.
• 동적 튜닝(e.g., 디버그 모드 설정)에 대한 대부분의 규정은 indirection 레벨을 추가하고 분기 수를 증가시켜 시간 효율성을 심각하게 저하시킬 수 있다.
• 오류를 잡기 위해 설계된 일부 규정은 적용 범위를 제한한다. 예를 들어 2.6.6 버전 이전에는 플랫폼에 관계없이 malloc이 내부적으로 할당 크기 인수를 부호있는 32비트 정수로 처리했으며, 0 이하의 인수를 요청크기 0으로 간주했다. (그러나 2.6.6 부터는 음수 인수가 POSIX 표준을 준수하기 위해 null 값을 반환한다)
• 다른 할당기의 특이점을 수용하여 플러그-호환성을 유지하려면 유연성과 성능이 감소할 수 있다. 가장 특이한 예로, 초기 Unix 할당기의 일부 버전은 이미 해제된 메모리를 realloc하는 것을 허용했다. 1993년까지는 호환성을 위해 이를 허용했지만, 이 기능이 제거되었을 때 아무도 불평하지 않았다.
• 소규모 프로그램의 시간/공간을 개선하는 일부 휴리스틱은 요즘 대부분의 시스템 로드를 지배하는 대규모 프로그램에서 시간/공간 특성을 용납할 수 없을 정도로 악화시킬 수 있다.

이와 같은 절충안 중 어떤 것도 완벽할 수 없다. 그러나 수년에 걸쳐 할당자는 대다수 사용자가 수용할 수 있는 Trade-off를 제공하도록 진화해왔다.

 

이 malloc의 진화를 계속해서 이끄는 주요 요인들은 다음과 같다:

• malloc 성능에 대한 다른 사람들의 실증적 연구
  • (위에서 언급한 Wilson 등의 논문과 그 논문이 인용한 다른 논문 포함).
  • 이 논문들은 이 malloc 버전이 시간 및 공간 효율성 측면에서 가장 효율적인 메모리 할당기 중 하나로 순위가 매겨진다고 밝히고 있다. 그러나 각 논문은 약점이나 추가 개선 가능성을 드러낸다.
• 대상 워크로드의 변화
  • malloc 구현에 민감한 프로그램 종류의 특성은 지속적으로 변화한다.
  • 대표적인 예로, X 및 기타 윈도잉 시스템의 메모리 특성이 점점 더 지배적이 되고 있다.
• 시스템 및 프로세서의 변화
  • 전형적인 프로세서에서 코드를 최적화하려는 구현 세부사항 및 미세 조정이 시간이 지남에 따라 변화한다.
  • 추가적으로, Linux와 Solaris와 같은 운영 체제는 자체적으로 진화하여 메모리 매핑을 시스템 수준 할당에 있어서 현명한 선택으로 만드는 경우가 있다.
• 사용자 및 기여자로부터의 제안, 경험 보고서, 코드
  • 이 코드는 여러 정기적인 자원봉사 기여자들의 도움으로 발전해왔다. 최근의 변경 사항 대부분은 Linux에서 제공된 버전을 사용하는 사람들로부터 시작되었으며, 많은 부분이 Linux 버전을 위해 Wolfram Gloger(ptmalloc 제작자)에 의해 구현되었고, 이후 내가 통합하였다.

Algorithms

---

malloc 알고리즘의 두 가지 핵심 요소는 초기 버전 이후로 변하지 않았다:

Boundary Tags (경계 태그)

메모리 청크에는 청크의 앞과 뒤에 크기를 정보를 포함한 필드가 있다. 이를 통해 두 가지 중요한 기능을 제공한다:

1. 서로 인접한 사용되지 않은 청크를 하나의 더 큰 청크로 병합(coalescing) 할 수 있다.
   이는 사용 불가능한 작은 청크의 수를 최소화한다.
2. 모든 청크는 알려진 청크를 기준으로 앞쪽(forwrad) 또는 뒤쪽(backward) 방향으로 순회할 수 있다.

 

 

초기 버전에는 경계 태그가 정확히 이 방식으로 구현되었다. 하지만 최신 버전에서는 프로그램에서 사용중인 청크에 대한 후방 필드(trailer fields)를 생략한다.

이는 소소한 트레이드 오프로, 활성 상태인 청크에서는 해당 필드를 절대 사용하지 않으므로 필요하지 않다. 이를 제거하면 오버헤드와 낭비를 줄일 수 있다.

하지만, 이러한 필드가 없으면 사용자가 필드를 덮어쓰는 실수를 감지하기 어려워져 오류 감지 기능이 약화된다.

Binning (분류)

사용 가능한 청크는 크기별로 그룹화되어 빈(bin)에 저장된다.

bin은 놀랍게도 많은 수(128개)의 고정 폭을 가지며, 대략 로그함수적 간격으로 크기가 배치된다.

 

512 바이트 이하 크기를 위한 빈은 각 크기마다 정확히 하나씩만 유지한다.(청크 크기는 8바이트 간격으로 나뉘어 있어, 8바이트 정렬을 간단히 보장한다.)

사용 가능한 청크를 검색할 때는 가장 작은 크기부터 시작하여, 가장 적합한 (best-fit) 순서로 처리된다. Wilson 등의 연구에 따르면, 다른 일반적인 접근 방식보다 실제 워크로드에서 단편화를 덜 유발한다.

 

 

 

 

1995년 이전 버전까지는 빈 내에서 청크가 정렬되지 않았기 때문에, best-fit 전략이 근사적으로만 적용되었다.

최신 버전에서는 대신 빈 내에서 청크를 크기 순서로 정렬하며, 크기가 동일한 경우 가장 오래된 것부터(first-in) 사용하는 규칙으로 정렬한다. (이는 약간의 시간이 추가로 소요되더라도 관찰된 문제를 피할 가치가 있다고 판단되어 변경되었다.)

따라서, 이 알고리즘의 일반적인 분류는 coalescing(병합) 가능한 best-fit 전략이다. 해제된 청크는 이웃한 청크와 병합되고, 크기 순서대로 검색되는 빈에서 관리된다.

 

이 접근 방식은 청크당 고정된 부가 작업 오버헤드를 초래한다. 크기 정보와 이진 링크를 각각의 사용 가능한 청크에 보유해야 하므로, 32비트 포인터를 사용하는 시스템에서는 최소 할당 가능 청크 크기가 16바이트이고, 64비트 포인터를 사용하는 시스템에서는 24바이트이다. 이러한 최소 크기는 대부분의 사람들이 선호하는 것보다 크며, 예를 들어 작은 연결 리스트 노드를 많이 할당하는 애플리케이션에서는 상당한 낭비를 초래할 수 있다. 그러나 16바이트 크기는 8바이트 정렬을 요구하고 malloc 부가 작업 오버헤드가 있는 시스템의 특징이다.

 

이 기본 알고리즘은 매우 빠르게 동작하도록 설계될 수 있다. 최적 크기를 찾기 위해 검색 메커니즘에 의존하더라도, 색인 기법(indexing techniques), 특수 사례 활용(exploitation of special cases), 세심한 코딩(careful coding)을 통해 평균적으로 몇십 개의 명령어만 필요하다(물론 이는 기계 및 할당 패턴에 따라 달라질 수 있다.).

 

경계 태그를 통한 병합(coalescing)과 이진화를 통한 최적 적합(best-fit)은 이 알고리즘의 주요 아이디어를 나타낸다. 하지만 추가적인 고려 사항들이 여러 휴리스틱 개선으로 이어지며 이는 다음을 포함한다:

• 지역성 유지(locality preservation)
• 미사용 영역 보존(wilderness preservation)
• 메모리 매핑(memory mapping)
• 캐싱(caching)

 

지역성 유지(Locality preservation)

프로그램에 의해 비슷한 시점에 할당된 청크는 유사한 참조 패턴과 공존 패턴을 가지는 경향이 있다. 지역성(locality)을 유지하면 페이지 폴트(page fault)와 캐시 미스(cache miss)를 최소화할 수 있으며, 이는 현대 프로세서에서 성능에 큰 영향을 미칠 수 있다. 만약 지역성만이 목표라면, 할당자는 연속적인 청크를 가능한 이전 청크에 가깝게 할당할 수 있다. 그러나 이 근접 적합(nearest-fit) 방식(주로 다음 적합(next-fit)으로 근사됨)은 매우 심각한 단편화를 초래할 수 있다.

현재 malloc 버전에서는 제한된 맥락에서만 다음 적합(next-fit)이 사용되며, 이는 지역성이 다른 목표와 가장 적게 충돌하는 경우에 유지하도록 설계되었다. 예를 들어, 정확히 원하는 크기의 청크가 없는 경우, 가장 최근에 분할된 공간을 사용(재분할)할 수 있을 만큼 크다면 이를 사용하고, 그렇지 않으면 최적 적합(best-fit)을 사용한다. 이러한 제한된 사용은 완벽히 사용 가능한 기존 청크가 할당되지 않는 경우를 방지하여 단편화를 제거한다. 또한, 이 형태의 다음 적합은 최적 적합 이진 검색보다 더 빠르므로 평균 malloc 속도를 높인다.

 

미사용 영역 보존(Wilderness preservation)

미사용 영역(wilderness) 청크는 시스템에서 할당된 최상위 주소를 경계로 하는 공간을 나타내며, Kiem-Phong Vo에 의해 명명되었다. 이 경계에 있으므로, 이는 sbrk(Unix에서 사용)를 통해 임의로 확장할 수 있는 유일한 청크이다. (단, 모든 메모리가 소진되어 sbrk가 실패하지 않는 한 가능하다.)

미사용 영역 청크를 처리하는 한 가지 방법은 다른 청크와 동일하게 다루는 것이다. (이 방법은 1994년까지 대부분의 malloc 버전에서 사용되었다.) 이는 구현을 단순화하고 속도를 높이지만, 신중하지 않으면 매우 나쁜 최악의 공간 특성을 초래할 수 있다. 예를 들어, 다른 사용 가능한 청크가 존재하는데도 미사용 영역 청크를 사용할 경우, 나중에 요청 시 방지할 수 있었던 sbrk를 초래할 가능성이 높아진다.

현재 사용되는 더 나은 전략은 미사용 영역 청크를 다른 청크보다 더 큰 것으로 취급하는 것이다. 이는 시스템 한계까지 확장 가능하므로 최적 우선(best-first) 검색에서 이를 가장 큰 것으로 간주한다. 결과적으로, 미사용 영역 청크는 다른 청크가 없을 때만 사용되며, 방지 가능한 단편화를 최소화한다.

 

메모리 매핑(Memory mapping)

sbrk를 통해 일반적인 할당 영역을 관리하는 것 외에도, 대부분의 Unix 버전은 mmap과 같은 시스템 콜을 지원하여 프로그램에서 사용하기 위한 비연속 메모리 영역을 별도로 할당한다. 이는 malloc이 메모리 요청을 충족하기 위한 두 번째 옵션을 제공한다.

mmap된 청크를 요청하고 반환하면 다운스트림 단편화를 줄일 수 있다. 이는 해제된 메모리 맵이 관리해야 할 구멍(hole)을 생성하지 않기 때문이다. 하지만 mmap과 관련된 제한 및 오버헤드로 인해 이는 매우 제한적인 상황에서만 유용하다. 예를 들어:

• 모든 현재 시스템에서 매핑된 영역은 페이지 정렬(page-aligned)이 필요하다.
• mmap과 mfree를 호출하는 것은 기존 메모리 청크를 분할하는 것보다 훨씬 느리다.

 

이러한 이유로 현재 malloc 버전은 다음 두 조건을 충족할 때만 mmap을 사용한다:

1. 요청이 동적으로 조정 가능한 임계값 크기(현재 기본값 1MB)를 초과하는 경우
2. 요청된 공간이 기존 영역에 없어서 sbrk를 통해 확보해야 하는 경우

 

또한, 현재 malloc 버전은 메인 영역의 트리밍을 지원한다. 이는 사용되지 않는 공간을 시스템에 반환하여 메모리 매핑 효과 중 하나를 달성한다. 예를 들어, sbrk는 음수 인수를 사용하여 이 효과를 달성할 수 있다. 이러한 공간 반환은 운영 체제의 스왑 공간 요구 사항을 줄이고 메모리 매핑 테이블을 재사용할 수 있게 한다. 하지만 mmap과 마찬가지로 호출 자체가 비용이 많이 들기 때문에, 이는 후행 미사용 메모리가 조정 가능한 임계값을 초과할 경우에만 시도된다.

 

캐싱(Caching)

가장 기본적인 알고리즘에서, 해제된 청크는 즉시 이웃 청크들과 병합하여 가능한 가장 큰 미사용 청크를 형성한다. 마찬가지로, 청크는 명시적으로 요청될 때만(더 큰 청크를 나눔으로써) 생성된다.

청크를 분할하거나 병합하는 작업은 시간이 소요된다. 이 시간 오버헤드는 두 가지 캐싱 전략 중 하나 또는 둘 모두를 사용함으로써 줄일 수 있다.

1. 지연 병합(Deferred Coalescing)
   • 해제된 청크를 병합하지 않고 현재 크기로 그대로 두어 동일한 크기에 대한 다른 요청이 곧 들어올 가능성에 대비한다. 이를 통해 병합과 나중의 분할, 그리고 정확히 일치하지 않는 청크를 찾는데 드는 시간을 절약할 수 있다.
2. 사전 할당(Preallocation)
   • 새 청크를 하나씩 나누는 대신 여러개를 한 꺼번에 나눈다. 이는 일반적으로 한 번에 하나 씩 나누는 것보다 더 빠르다.

malloc, free, realloc 등의 기본 데이터 구조는 언제든지 병합을 허용하므로, 관련된 캐싱 휴리스틱을 쉽게 적용할 수 있다.

캐싱의 효과는 분할, 병합, 검색 비용에 따라 달라진다. 또한, 캐싱과 병합 시점에 대한 정책에 따라 효과가 달라질 수 있다.

캐싱은 소수의 크기만 할당하고 해제하는 프로그램에서 좋은 선택이 될 수 있다. 예를 들어, 많은 트리 노드를 할당하고 해제하는 프로그램에서는 일부 노드를 캐싱하는 것이 효율적일 수 있다. 하지만 프로그램에 대한 사전 지식이 없는 경우, malloc은 작은 캐시된 청크를 병합하여 더 큰 요청을 충족시키는 것이 좋은지 아니면 다른 곳에서 가져와야 하는지를 판단하기 어렵다.

이전의 malloc 버전은 캐싱에 대해 적절한 추정을 하기 위해 몇 가지 검색 순서 휴리스틱(search-ordering huristics)을 사용했지만, 때로는 나쁜 최악의 사례 결과를 초래했다. 시간이 지남에 따라 이러한 휴리스틱은 실제 작업 부하에서 점점 덜 효과적인 것으로 나타났다. 이는 malloc에 크게 의존하는 실제 프로그램들이 점점 더 다양한 크기의 청크를 사용하는 경향이 있기 때문이다 .

예를 들어, C++ 프로그램에서는 클래스 수가 증가하는 경향과 관련이 있을 가능성이 있다. 서로 다른 클래스는 서로 다른 크기를 가지는 경향이 있다.

참고: 최신 malloc은 작은 청크(small chunks)만 캐싱한다.

 

Lookasides

Lookasides는 일부 애플리케이션에서 매우 바람직하지만, 이 할당자에서는 구현되지 않는 캐싱 유형으로, 매우 작은 청크를 위한 것이다. 위에서 언급했듯이, 기본 알고리즘은 최소 청크 크기를 강제하면, 이는 매우 작은 요청에 대해 매우 낭비적을 수 있다. 예를 들어 4바이트 포인터를 사용하는 시스템에서 연결 리스트는 두 개의 포인터만 포함하는 노드를 할당할 수 있으며, 이는 8바이트만 필요하다. 그러나 최소 청크 크기가 16바이트이기 때문에, 리스트 노드에만 할당하는 사용자 프로그램은 100%의 오버헤드를 겪게 된다.

이 문제를 해결하면서도 이식 가능한 정렬을 유지하려면 할당자가 어떤 오버헤드도 부과하지 않아야 한다. 이를 수행하기 위한 기술은 존재한다. 예를 들어, 청크가 더 큰 집합된 공간에 속하는지 여부를 주소 비교를 통해 확인할 수 있다. 그러나 이렇게 하는 것은 상당한 비용을 초래할 수 있으며, 실제로 이 할당자에서는 그 비용이 허용될 수 없는 수준이다. 청크가 주소로는 따로 추적되지 않으므로, 임의로 제한하지 않는다면 이러한 확인 과정은 메모리를 무작위로 검색하는 결과를 초래할 수 있다. 또한, 작은 청크를 병합할지 여부와 방법을 제어하는 하나 이상의 정책을 채택해야 한다.

이러한 문제와 제한은 프로그래머가 특수 목적의 메모리 관리 루틴(e.g., C++에서 operator new()를 오버로딩)을 작성해야 하는 매우 적은 종류의 상황 중 하나로 이어진다. 대규모이지만 대략적으로 알려진 숫자의 매우 작은 청크를 사용하는 프로그램은 매우 간단한 할당자를 구축하는 것이 유리할 수 있다. 예를 들어, 고정된 배열에서 청크를 할당하고 임베디드 free 리스트를 사용하며, 배열이 소진된 경우 malloc을 백업으로 사용하는 방식을 들 수 있다. 약간 더 유연하게는, 이는 GNU gcc와 libg++에서 제공되는 C 또는 C++ 버전의 obstack을 기반으로 할 수도 있다.