#title uClinux 의 malloc 이 다른 이유
'''''uClinux 의 malloc 이 다른 이유'''''
저자: David McCullough [[MailTo(davidm@snapgear.com)]][[BR]]
번역: 김남형 [[MailTo(namhyung@gmail.com)]]
--------------------------
먼저 '''uClinux''' 에서는 가상 메모리 (VM - Virtual Memory) 시스템을 사용하지 않는다. 이것은 당신이 이미 실행중인 프로세스에 대해서 임의로 메모리를 추가할 수 없다는 것을 의미한다. ''VM'' 이 보통 ''MMU'' (Memory Management Unit)라 불리우는 처리 장치를 이용해 구현되므로 당신은 uClinux 의 세계를 여행하는 동안 ''NOMMU'' 라는 단어를 자주 접하게 될 것이다. 매우 고수준(high-level)에서 MMU 나 VM 이 없는 것이 '''malloc''' 에 어떠한 영향을 미치는지에 대해서 알아보도록 하자.
VM 상에서는 모든 프로세스는 (비록 가상 주소이기는 하지만) 동일한 주소공간에서 실행되며 가상 메모리 시스템은 이 영역이 실제로 어느 물리 메모리에 매핑되는지를 관리한다. 게다가 프로세스가 보는 가상 메모리는 연속적인 것 일지라도 실제 물리 메모리 상에서는 동떨어진 영역에 흩어져 있을 수도 있다. 그 중에는 아마 디스크 상에 스왑 (swap) 되어 있는 것도 있을 것이다.
VM이 없다면 각각의 프로세스는 반드시 그들이 실행될 수 있는 메모리 영역 안에 위치해야 한다. 단순하게 생각해보면, 이 영역은 연속적인 공간이어야 하며 이 영역의 위아래로 다른 프로세스가 위치하고 있을 수 있으므로 일반적으로 메모리 영역을 확장할 수 없다.
원래의 주제로 돌아가보면, '''malloc''' 은 일반적으로 프로세스의 주소 공간의 크기를 확장하거나 변경하는 시스템 콜인 '''sbrk/brk''' 를 이용하여 구현된다. 그리고 malloc 라이브러리는 프로세스를 대신하여 '''sbrk()''' 에 의해 얻어진 여분의 메모리를 관리한다. 이 여분의 공간이 없어지면 다시 sbrk() 를 호출하여 더 많은 공간을 확보하게 되고, 또한 '''brk()''' 를 이용하여 메모리의 크기를 줄일 수도 있지만 대부분의 malloc 구현은 이러한 일은 하지 않는다. sbrk() 는 프로세스 메모리 영역의 끝부분에 메모리를 추가하는 일을 하고 (프로세스 크기 증가), brk() 는 프로세스 메모리 영역의 끝부분을 시작 부분의 가까운 임의의 영역으로 옮기거나 (프로세스 크기 감소) 뒤로 확장하는 일을 한다 (프로세스 크기 증가). sbrk()/brk() 의 표준적인 행동은 프로세스의 크기를 확장/감소 시키는 것이다.
uClinux 상에서는 프로세스의 크기를 증가시킬 수 없기 때문에, malloc 이 동작하기 위해서는 저수준(low-level)에서 몇가지 변화가 필요하게 되었다.
이에 관련된 많은 방법들이 있다. 대표적인 몇가지를 살펴보면:
1. 프로세스가 동적 메모리를 할당하지 못하게 한다.
2. 프로세스마다 sbrk/brk 가 사용할 수 있는 힙(heap) 영역을 할당한다. 프로세스는 힙의 크기를 변경할 수 없으며 힙의 크기는 프로세스가 생성될 때 정해진다.
3. 프로세스가 (시스템 전체에 걸친) 이용 가능한 전역 메모리 풀(global pool of free memory)에서 메모리를 할당받을 수 있도록 한다.
우선 1번은 문제가 있다. 대부분의 응용 프로그램들은 동적 메모리 할당 기능을 사용하고 있기 때문에 이 기능을 사용하지 못하게 된다면 수많은 오픈 소스 응용 프로그램들이 uClinux 상에서 제대로 동작하도록 수정하는 데 막대한 노력이 필요하게 된다.
2번은 그 나름의 장점을 가지고 있다. 이 기능을 이용하면 프로세스가 사용할 수 있는 메모리의 양을 제한할 수 있다 (장점이 될 수 있다). 하지만 힙 영역이 단지 일시적인 용도로만 사용되는 경우에도 항상 할당된다는 것을 의미한다. 힙 영역은 프로세스가 생성될 때 할당되어져 있으므로 sbrk/brk 는 표준적인 행동을 취할 수 있고 일반적인 malloc 라이브러리가 사용될 수 있다.
마지막으로 3번을 살펴보자. 여기에는 단점이 존재한다. 잘못된 프로세스 하나가 모든 메모리 영역을 다 차지해 버릴 수 있다. 시스템의 메모리 풀에서 메모리를 할당받는 것은 프로세스 메모리 영역의 마지막 부분에 대해 연산을 하는 sbrk/brk 와 호환되지 않는다. 따라서 기존의 malloc 구현으로는 불가능하고 새로운 구현이 필요하게 된다. 이 방식의 장점은 실제로 필요한 만큼의 메모리 만이 사용된다는 것이다. 사용된 메모리는 바로 커널의 전역 메모리 풀로 반환될 수 있으며 이 메모리 영역을 관리하는 기존의 커널 할당자를 이용하여 malloc 을 구현할 수 있다.
현재 uClinux 에서는 3번째 방식이 사용되고 있다. 가장 단순한 malloc 구현에서는 커널의 이용가능한 메모리 풀에서 메모리를 얻기 위해 '''mmap''' 을 호출하고 반환하기 위해서 '''munmap''' 을 호출한다. 이것으로 매우 작은 malloc 구현이 가능하다 (단지 1개의 시스템 콜 만이 사용된다).
이러한 단순한 malloc 구현에서는 다음과 같은 문제점이 발생된다:
1. uClinux 상에서 mmap 을 사용하는 오버헤드는 각각의 할당에 대해 56 바이트 정도이다. 이는 (''Zebra'' 라우팅 데몬과 같이) 작은 크기의 메모리 할당을 매우 많이 요청하는 경우에 극히 나빠질 수 있다. uClinux 상의 사용자 프로그램에서 mmap 을 호출하면 커널 메모리 할당자인 kmalloc 을 사용하여 단순히 전역 메모리 풀에서 할당된 후에 프로세스에 연관된 연결 리스트로 연결된다. 위에서 말한 56 바이트는 kmalloc 의 오버헤드에 연결 리스트의 오버헤드를 합한 것이다. 단지 56 바이트의 오버헤드 만이 문제가 아니라 많은 수의 작은 할당이 일어난 경우에는 리스트의 길이가 길어지게 되므로 메모리의 해제나 재할당을 느리게 만든다 (할당 시에는 단지 연결 리스트의 첫부분에 추가하면 된다).
2. 표준 커널 메모리 할당자는 오직 2의 배수 단위로만 할당하므로 (최대 1MB 로 제한) 비효율적이며 제한적이다. 이것은 특히 큰 단위의 할당에서 문제가 된다. 33KB 를 할당받고자 하는 경우에는 거의 2배에 가까운 64KB 가 할당되어야 한다.
몇가지 작은 malloc 구현들은 1번 문제점을 해결하기 위해 더 큰 블럭을 할당받은 후 내부적으로 이를 관리하게 하여 56 바이트의 오버헤드를 줄이도록 하였다.
커널 메모리 할당자는 최대 할당 크기를 충분히 늘일 수 있도록 수정되었다. 몇몇 경우에서 이것은 커널 설정 옵션을 조정하는 것만으로 가능하다. 이것은 더 큰 메모리 할당을 가능하게 하므로 큰 응용 프로그램을 실행할 수 있도록 한다.
uClinux 에는 새로운 커널 메모리 할당자가 추가되어 더이상 2의 배수 단위 할당이 필요치 않게 되었고 메모리 할당 시의 낭비가 많이 제거되었다. 이 할당자는 일반적으로 '''Kmalloc2''' 라고 부르며 NOMMU 환경에서 메모리 할당의 오버헤드를 상당히 감소시켰고 다른 태스크에서 사용할 수 있는 메모리의 양을 증가시켰다.
기존의 커널 메모리 할당자는 오직 2의 배수 단위로 메모리를 할당하였다. 예를 들어 12000 바이트가 필요한 경우에는 16KB 를 할당받게 되어 나머지 4KB 에 대해서는 사용할 수가 없었다. 이것은 응용 프로그램을 시작시킬 때 매우 낭비가 심해진다. 예를 들어 응용 프로그램의 크기가 130KB 라면 이 프로그램이 실행되기 위해선 실제로 256KB 가 필요하게 된다.
Kmalloc2 는 1 페이지 크기 (4KB) 의 요청까지는 2의 배수 단위로 할당하는 정책을 그대로 사용한다. 하지만 1 페이지 크기 이상의 요청에 대해서는 가장 가까운 페이지 단위로 조정하여 할당하도록 한다. 앞의 예제에서라면 130KB 의 응용 프로그램에 대해서 132KB 의 메모리가 할당된다. 기존의 커널 메모리 할당자에 비해 124KB 를 절약한 셈이다.
Kmalloc2 는 또한 단편화된 메모리를 피하는 기능을 포함한다. 2KB 혹은 그 이하의 할당에 대해서는 메모리 영역의 끝에서부터 아래로 내려오며 처리하고, 큰 할당에 대해서는 메모리의 시작 부분에서부터 위로 올라오며 처리한다. 이렇게 함으로써 네트워크 버퍼와 같은 일시적인 할당에 의해 메모리가 단편화되어 커다란 응용 프로그램이 실행되지 않는 상황을 막아준다.
Kmalloc2 가 완벽한 것은 아니다. 비록 기존의 커널 메모리 할당자가 더 많은 메모리 단편화를 만들어 낸다고는 하지만 Kmalloc2 에서도 메모리 단편화가 꽤 일어날 수 있다. Kmalloc2 는 uClinux 가 동작하는 임베디드 환경 - 주로 (상대적으로) 고정된 그룹의 오랫 동안 실행되는 응용 프로그램들이 존재하는 환경 - 에서 실제적으로 잘 동작한다.
이제까지 메모리 할당에 대한 커널 수준의 옵션에 대해서 약간 살펴보았다, 이제는 사용자 프로그램에서 사용할 수 있는 옵션에 대해서 살펴보기로 한다. 앞서 살펴본 몇가지 제한 사항들이 있기 때문에 사용자 프로그램에서 사용할 수 있는 솔루션은 많지가 않다. 그들은 각자 자신의 역할들을 명확히 수행한다.
먼저 "libc" 의 선택에 대한 문제가 있다. -- 이것은 다른 토픽으로 다뤄질 것이다. "malloc" 의 선택은 보통 당신이 사용하는 "libc" 에 의존한다: '''uC-libc''' 와 '''uClibc''' 가 있다. 둘 다 모두 단순한 메모리 할당자인 '''malloc-simple''' 을 제공한다.
malloc-simple 은 실제적인 메모리 요청에 대한 처리를 커널에서 수행하도록 mmap 과 munmap 을 사용한다. malloc-simple 의 구현은 매우 단순하고 코드의 크기도 무시할 만큼 작으므로 응용 프로그램에서 이를 포함하는 데 드는 비용은 매우 적다.
malloc-simple 의 단점은 - 앞서 살펴본대로 - 각각의 할당에 사용되는 약 56 바이트의 커널 오버헤드이다. 만약 응용 프로그램이 작은 크기의 메모리 할당을 많이 수행하는 경우, 메모리 사용량은 매우 커질 것이다. 예를 들어 당신이 짠 프로그램이 10 바이트 크기의 메모리를 1000번 할당받는 경우, 필요한 전체 메모리 양은 10000 바이트가 된다. 하지만 56 바이트의 오버헤드로 인해 실제로 할당되는 전체 메모리는 66000 바이트가 되며, 실제로 필요한 양보다 560% 나 많은 오버헤드를 감수해야 한다. Zebra 라는 라우팅 데몬은 시작될 때 각각의 명령 (command) 에 대한 자료 구조를 할당받기 때문에 - Zebra 에는 매우 많은 수의 명령/키워드가 존재한다 - 이러한 빈번한 작은 할당의 문제에 심각한 피해를 보는 대표적인 예이다.
uC-libc 는 libsmalloc 라고 하는 Zebra 와 같이 빈번한 작은 할당 문제를 겪는 프로그램에 특화된 버전의 malloc 을 제공한다. 이 버전은 malloc-simple 의 외부 코드로 통합되어 졌으므로 더이상 uClinux 에서 [http://www.cyberguard.com/snapgear/tb20020409.html 공유 라이브러리]를 사용하는 데 드는 매우 큰 오버헤드를 감수하지 않아도 된다.
uClibc 는 다음과 같은 몇가지 선택안을 제공한다:
|| '''malloc''' ||<align="left">NOMMU 에서 지원하지 않는 mmap 의 기능을 사용하기는 하지만 NOMMU 환경을 지원하는 것처럼 보이는? 덩어리 (hunk) 단위의 할당자. 현 시점에서 이 할당자는 NOMMU 시스템에서 동작하지 않는 것 같다. 이 문제점을 수정하는 것은 상대적으로 쉬울 것이다. 만약 문제점이 수정된다면 이 할당자는 몇가지 잠재적인 장점을 가진다. ||
|| '''malloc-930716''' ||<align="left">이 할당자는 오직 MMU 를 가진 시스템에서만 동작한다. 이 할당자는 sbrk/brk 에 기반하여 동작한다. 비록 이 함수들이 uClinux 시스템에서 작은 양의 메모리를 반환하겠지만 그것은 메모리 할당자가 사용하기 위한 메모리 풀로는 의미가 없다. ||
|| '''malloc-simple''' ||<align="left">가장 단순한 할당자로 MMU 와 NOMMU 시스템에서 모두 동작한다. ||
[[BR]]
일반적으로 더 복잡한 malloc 의 구현에서는 더 빠른 메모리 할당과 작은 할당에 대한 효율적인 처리가 이루어 지지만 uClinux 환경에서 실행되는 작은 응용 프로그램들에 포함되기 에는 부담스러운 코드 크기를 가진다.
malloc 구현에 대한 몇가지 선택안이 존재한다. 어떤 것을 사용해야 할까? malloc-simple 은 일반적으로 사용하기에 좋은 기본 malloc 구현이다. 그런 다음에는 각 응용 프로그램에 알맞은 malloc 을 선택할 수 있다. 위에서 살펴본 대로 당신이 하고자 하는 목적에 따라 약간의 제한이 있을 수 있다.
부득이 하게도, 당신이 어떤 할당자를 선택했든 결국엔 모든 메모리가 바닥나고 말 것이다. 새로운 사용자가 공통적으로 접하게 되는 문제점으로는 "missing memory" 문제가 있다. 시스템은 많은 양의 사용 가능한 메모리를 가지고 있어도 사용자의 응용 프로그램에서 X 라는 크기의 버퍼를 할당받지 못하는 현상이다. 이것은 메모리 단편화에서 오는 문제로서 현재에는 가능한 해결책이 없는 실정이다. uClinux 환경에는 VM 이 없기 때문에 메모리 단편화 없이 모든 메모리를 고루 사용하는 것은 거의 불가능해 보인다. 예제를 하나 살펴보도록 하자. 시스템에는 500KB 의 사용 가능한 메모리가 있고 당신은 100KB 의 메모리를 할당받으려고 하는 상황이다. 당연히 이것이 가능한 일이라고 생각될 것이다. 하지만 메모리를 할당하기 위해서는 100KB 의 연속적인 공간이 있어야 한다는 것을 기억하자. 메모리 맵을 아래와 같이 표현해 보도록 하겠다. 하나의 문자는 약 20KB 의 메모리를 나타낸다. X 문자는 메모리가 할당되었거나 사용자의 응용 프로그램 혹은 커널에서 이미 사용 중인 영역을 나타낸다.
{{{
0 100 200 300 400 500 600 700 800 900 1000
-+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+--
|XXXXX|XXXXX|---XX|--X--|-X---|XX---|-X---|-XX--|-X---|XXXXX|
}}}
위에서 볼 수 있듯이 시스템의 전체 사용 가능한 메모리 양은 500KB 이다. 하지만 그중에서 가장 큰 연속적인 영역의 크기는 오직 80KB 뿐이다. 이러한 상황이 될 수 있는 가능성은 많이 존재한다. 어떤 프로그램에서 메모리를 할당받은 후에 메모리의 중간 부분을 제외한 다른 부분들만 해제하는 경우라면 이러한 문제가 쉽게 발생될 수 있다. 일시적으로 실행되는 프로그램들 또한 메모리의 할당에 영향을 줄 수 있다.
종종 듣게되는 질문으로 왜 메모리의 단편화를 제거할 수 없느냐? 라는 질문이 있다. 문제는 uClinux 에는 VM 이 존재하지 않고 프로그램에서 사용되는 메모리 영역을 옮길 수 없다는 것이다. 일반적으로 프로그램에서는 할당된 메모리 영역 내의 주소에 대한 참조를 가지고 있으며 VM 이 없는 환경에서는 메모리가 항상 올바른 주소에 존재하도록 해야 한다. 만약 임의로 해당 메모리 영역을 다른 곳으로 옮겨 버린다면 프로그램은 정상적으로 동작되지 않을 (crash) 것이다. uClinux 상에서 이러한 상황에 대한 해결책은 없다. uClinux 의 응용 프로그램 개발자들은 항상 이러한 문제점을 인식하고 작은 메모리 블럭들을 활용하도록 노력해야 한다.
uClinux 환경에서의 메모리 할당은 위에서 살펴 보았듯이 일반적인 리눅스 환경에서의 메모리 할당과 비슷하다. 하지만 uClinux 만의 특징과 단점들을 포함한다. 메모리 할당에 관련되어 다음으로 진행되어야 할 작업은 의심할 여지없이 공유 라이브러리 구현일 것이다? (Further progress will no doubt be made on the memory allocation front now that uClinux is enjoying its first shared library implementations) 이것이 가능해 져서 malloc 의 구현이 공유 라이브러리에 존재하면 malloc 의 구현을 가능한 한 작게 만들어야 한다는 제한 사항이 적어진다. 그러므로 크기는 더 커져도, 메모리 단편화 문제와 할당시의 오버헤드 문제를 감소시킬 수 있는 효율적인 사용자 레벨의 malloc 구현이 가능해 질 것이다.
몇가지 질문에 대해 답변해 준 Phil Wilshire [[MailTo(philwil@earthlink.net)]] 에게 감사한다.
참고문헌 (http://www.uclinux.org/pub/uClinux/dist 에서 다운로드 받을 수 있는 uClinux 배포판의 소스)
커널 할당자와 mmap 구현:
* linux-2.4.x/mmnommu/slab.c
* linux-2.4.x/mmnommu/page_alloc.c
* linux-2.4.x/mmnommu/page_alloc2.c
* linux-2.4.x/mmnommu/mmap.c
* linux-2.0.x/mmnommu/kmalloc.c
* linux-2.0.x/mmnommu/page_alloc.c
* linux-2.0.x/mmnommu/kmalloc2.c
* linux-2.0.x/mmnommu/page_alloc2.c
* linux-2.0.x/mmnommu/mmap.c
uC-libc 의 malloc 구현:
* lib/libc/malloc/alloc.c
* lib/libc/malloc-simple/alloc.c
uClibc 의 malloc 구현:
* uClibc/libc/stdlib/malloc
* uClibc/libc/stdlib/malloc-930716
* uClibc/libc/stdlib/malloc-simple