Egloos | Log-in
F/OSS study
F/OSS study
[glibc] 동적 메모리 관리 (2)
glibc: 2.10.1
arch: x86

이전 글 보기:

이번에는 malloc() 함수의 실행 과정을 따라가 보자.
malloc() 함수의 서비스 루틴은 public_mALLOc() 함수이며
실제로는 전처리 과정에 의해 __libc_malloc()이라는 이름으로 바뀐다.
(__malloc과 malloc은 이 함수에 대한 alias이다.)

public_mALLOc() 함수는 다음과 같은 작업을 수행한다.
  1. __malloc_hook이 정의되어 있다면 해당 hook을 호출한 후 종료한다.
  2. 그렇지 않으면 malloc을 처리할 heap 영역(arena)를 찾는데 일반적으로 main_arena가 사용된다.
  3. arena에 대한 lock을 건 후에 실제 malloc의 처리 루틴인 _int_malloc() 내부 함수를 호출한다. (아래 참조)
  4. 만약 _int_malloc() 함수가 NULL을 반환했다면 다른 arena에 대해 _int_malloc()을 다시 한 번 호출한다.
  5. arena에 걸린 lock을 해제한다.
  6. _int_malloc() 함수가 반환한 값을 반환하고 종료한다.

_int_malloc() 함수는 다음과 같은 작업을 수행한다.
  1. 요청한 크기를 chunk 크기에 맞춘다. 즉, 헤더를 위한 4 바이트를 더한 후 8 바이트 단위로 정렬(align)한다. 이 후로는 chunk 크기를 기준으로 계산한다.
  2. 주어진 크기가 fast bin에 속한다면 (<= 72) fast bin 내의 free chunk를 찾아본다.
    1.  주어진 크기에 맞는 fast bin의 인덱스를 계산한다.
    2.  해당 인덱스의 포인터가 가리키는 chunk를 victim 지역 변수에 저장한다.
    3.  victim이 NULL이 아니라면 fast bin의 해당 인덱스에 victim->fb가 가리키는 chunk를 저장하고 victim의 데이터 영역에 대한 포인터를 반환한다. (종료)
  3. 주어진 크기가 small bin에 속한다면 (< 512) small bin 내에서 free chunk를 찾아본다.
    1.  주어진 크기에 맞는 small bin의 인덱스를 계산하여 idx 지역 변수에 저장한다.
    2.  해당 인덱스 내에 가장 오래된 chunk를 victim 지역 변수에 저장한다.
    3.  victim이 올바른 chunk를 가리킨다면 해당 인덱스 내의 리스트에서 victim을 제거하고, victim 바로 다음에 위치한 chunk의 헤더에 P (PREV_INUSE) 플래그를 설정한 뒤 victim의 데이터 영역에 대한 포인터를 반환한다. (종료) 설명을 단순하게 하기 위해 앞으로 'victim을 반환한다'라는 표현은 P 플래그를 설정하는 것과 데이터 포인터를 반환하는 작업을 뜻하는 것으로 사용할 것이다.
    4.  victim이 올바른 chunk를 가리키지 않는다는 것은 다음의 두 경우 중 하나이다.
    5.   victim이 NULL이면 최초로 malloc() 함수가 호출된 경우이다. 아직 초기화가 제대로 이루어지지 않았으므로 malloc_init_state() 내부 함수를 호출하여 초기화를 수행한다.
    6.   victim이 NULL이 아니고 bin 자신을 가리킨다면 해당 bin은 비어있는 것이다. (초기화 과정에서 각 bin의 리스트는 자기 자신을 가리키도록 설정된다.)
  4. 여기까지 왔다면 주어진 크기는 large bin에 속한다. large bin은 바로 찾아보지 않고 다음과 같은 준비 과정을 거친다.
    1.  주어진 크기에 맞는 large bin의 인덱스를 계산하여 idx 지역 변수에 저장한다.
    2.  만약 fast bin을 포함하고 있다면 이들을 모두 병합(consolidate)하여 보다 큰 chunk로 만든다. 이는 큰 메모리 요청을 받은 경우에는 더 이상 작은 크기의 요청이 (최소한 당분간은) 없을 것이라고 가정하기 때문이다. (이로 인해 fast bin으로 인한 fragmentation 문제를 줄일 수 있다.)
  5. 이제 unsorted bin을 검색하여 일치하는 크기의 free chunk가 있는지 검색한다.
    1.  unsorted bin 내의 가장 오래된 chunk를 victim 지역 변수에 저장한다.
    2.  victim을 unsorted bin의 리스트에서 분리한다. (unsorted bin 내의 chunk들은 오직 한 번만 검사된다.)
    3.  victim의 크기와 주어진 크기가 일치한다면 victim을 반환한다. (종료)
    4.  만약 victim의 unsorted bin 내의 마지막 chunk이고 주어진 크기가 small bin에 속하는 작은 크기이며 victim이 이전 요청을 처리하고 남은 자투리 영역이고 (last_remainder), victim의 크기가 주어진 크기를 처리하고 다른 chunk를 만들만한 여유가 있다면 victim을 분할하여 요청을 처리하고 나머지는 다시 unsorted bin 내에 남겨둔다. (종료) 이는 작은 크기의 연속된 요청이 메모리 상의 연속된 위치에 존재하도록 하여 locality를 높이기 위함이다.
    5.  victim의 크기에 맞는 bin의 리스트의 제일 처음에 삽입한다.
    6.  만약 victim이 large bin에 속한다면 large bin 내의 다른 chunk들과 크기를 비교하여 적절한 위치에 삽입된다.
  6. 이제 large bin에 속하는 경우 해당 리스트를 검사한다. large bin은 (일정 범위 내에서) 크기가 다른 chunk들이 섞여있으므로 현재의 요청을 만족시킬 수 있는 가장 작은 크기의 chunk를 찾아야 한다.
    1.  앞서 계산한 idx에 해당하는 bin의 제일 앞에 있는 chunk를 victim 지역 변수에 저장한다.
    2.  victim의 크기가 주어진 크기보다 큰지 검사하여 그렇지 않다면 탐색을 중지한다. large bin은 앞쪽부터 큰 chunk가 놓이고 뒤로 갈수록 (즉, fd_nextsize 링크를 따라갈수록) 크기가 작아진다. 현재 검사한 victim의 크기는 해당 bin 내에 있는 가장 큰 chunk의 크기이므로 이보다 큰 요청은 해당 bin에서 처리할 수 없다.
    3.  victim을 victim->bk_nextsize로 설정한다. 이제 victim은 해당 bin 내의 가장 작은 크기의 chunk이다.
    4.  victim의 크기가 주어진 크기보다 커질 때까지 victim을 victim->bk_nextsize로 변경한다.
    5.  이제 요청을 처리할 chunk를 찾았다. victim을 리스트에서 분리한다.
    6.  victim의 크기가 요청을 처리하고도 다른 chunk를 구성할 수 있을 정도로 크다면 분할하여 나머지 영역을 chunk로 만들어서 unsorted bin에 추가한다.
    7.  victim을 반환한다. (종료)
  7. 여기까지 왔다면 해당하는 bin 내에서 적당한 chunk를 찾지 못한 것이다. idx 값을 하나 증가시킨 후 더 큰 크기의 bin 내에 free chunk가 있는지 검사한다. (이는 bitmap을 통해 빨리 확인할 수 있다.)
    1.  현재 인덱스에 해당하는 bitmap을 검사하여 free chunk가 있는지 확인한다. 만약 해당 bin이 비어있다면 인덱스를 하나 증가시킨 후 검사를 다시한다. 모든 bitmap을 검사했다면 8번 과정으로 넘어간다.
    2.  bitmap이 설정된 bin이 있다면 해당 bin 내의 (가장 작은 크기의) 가장 오래된 chunk를 victim 지역 변수에 저장한다.
    3.  victim을 리스트에서 분리한다.
    4.  victim의 크기가 요청을 처리하고도 다른 chunk를 구성할 수 있을 정도로 크다면 분할하여 나머지 영역을 chunk로 만들어서 unsorted bin에 추가한다. 나머지 영역의 크기가 small bin에 속한다면 last_remainder 변수가 나머지 영역을 가리키도록 설정한다.
    5.  victim을 반환한다. (종료)
  8. 여기까지 왔다면 bin 내에 모든 chunk가 비어있거나 요청을 만족할 수 없는 상황이다. 이제 top chunk를 사용한다.
    1.  만약 top chunk의 크기가 주어진 요청을 만족하고도 새로운 chunk를 만들 수 있는 크기라면 분할하여 victim을 반환하고 나머지 영역을 top chunk로 설정한다. (종료)
    2.  그렇지 않고 주어진 크기가 small bin 영역에 속한다면 fast bin이 남아있을 것이다. fast bin을 병합한 후 다시 2번 과정으로 돌아가서 할당을 시도한다.
    3.  그렇지 않다면 시스템의 heap 영역을 늘려야 한다. 이는 sYSMALLOc() 함수가 처리하며, 이 함수의 반환값을 반환하고 종료한다.

sYSMALLOc() 함수는 다음과 같은 작업을 수행한다.
  1. 먼저 요청된 크기가 mmap() 시스템 콜을 이용하도록 설정된 범위에 속하고 (>= 128K) mmap() 사용 횟수 제한을 넘지 않는다면 (< 65536회) mmap()을 호출한다. 호출이 성공하면 chunk에 M (IS_MMAPPED) 플래그를 설정하고 데이터 영역의 포인터를 반환한다. mmap()으로 할당한 chunk는 분할할 수 없으므로 크기에 여유가 있더라도 하나의 chunk로 사용된다.
  2. 그 보다 작은 크기거나 mmap() 호출이 실패했다면 heap 영역을 늘려야 한다. 증가시킬 크기는 요청한 크기에서 원래의 top chunk 크기를 빼고 top chunk가 기본적으로 가져야 할 여유 공간의 크기(pad)를 더한 후 할당 후 남은 영역에 chunk를 구성하기 위한 최소 크기(16)를 더한 값이다. 또한 이는 시스템의 페이지 크기에 맞춰 조정된다.
  3. 위에서 계산한 크기에 대해 sbrk() (MORCORE라는 이름을 사용한다) 시스템 콜을 호출한다.
  4. 호출이 성공했다면 __after_morecore_hook이 정의되어 있는지 검사하여 이를 호출한다.
  5. 호출이 실패했다면 크기와 횟수 제한에 상관없이 mmap() 시스템 콜을 호출하여 메모리 할당을 시도한다. 이것이 성공하면 해당 arena는 더 이상 연속된 주소 공간에 속하지 않으므로 NONCONTIGUOUS_BIT를 설정한다. 실패했다면 errno 변수를 ENOMEM으로 설정하고 NULL을 반환한다. (종료)
  6. 할당된 영역이 chunk 단위로 정렬되었는지 다시 확인하여 필요한 경우 sbrk()를 다시 호출한다.
  7. 이전의 sbrk() 호출이 성공적으로 수행되었다면 top 영역의 크기를 그에 맞게 늘린다.
  8. 그렇지 않다면 메모리 정렬이 맞지 않거나 mmap() 호출을 통해 불연속적인 구간이 할당된 경우이다. 메모리 주소를 정렬하여 다시 한 번 sbrk()를 호출하고 불연속적인 구간의 끝부분에 dummy chunk (fence) 2개를 할당하여 원래의 top chunk가 불연속적인 공간과 consolidate되지 않도록 한다.
  9. 이제 새로 할당된 영역을 분할하여 요청을 처리하고 나머지 영역을 새로운 top chunk로 설정한다.

중요한 과정을 간단하게 (순서대로) 다시 정리해보면 다음과 같다.
  • fast bin에 속한다면 해당 bin 내의 chunk를 반환 (LIFO, exact fit)
  • small bin에 속한다면 해당 bin 내의 chunk를 반환 (FIFO, exact fit)
  • large bin에 속한다면 fast bin을 병합하여 큰 chunk로 만듬
  • unsorted bin을 검사하여 일치하는 chunk를 반환 (FIFO, exact fit)
  • 단 unsorted bin 내에 이전에 분할한 chunk가 있고 요청이 small bin에 속하면 해당 chunk를 다시 분할하여 반환 (next fit)
  • large bin에 속한다면 해당 bin 내에서 요청을 만족하는 가장 작은 chunk를 반환 (FIFO, best fit)
  • bitmap을 검사하여 요청을 만족하는 가장 작고 오래된 chunk를 반환 (FIFO, best fit)
  • 현재 top chunk가 요청을 처리할 수 있다면 분할하여 반환 (exact fit)
  • 충분히 큰 크기의 요청이라면 mmap()을 통해 chunk를 생성 후 반환 (best fit)
  • sbrk()로 top chunk를 늘리거나 mmap()으로 새로운 top chunk를 할당하여 요청한 크기만큼 분할하여 반환 (exact fit)

fast bin 내의 chunk들을 병합하는 일은 malloc_consolidate() 내부 함수가 수행한다.
이 함수는 먼저 동적 메모리 관리자가 제대로 초기화 되었는지 검사하여 필요한 경우 malloc_init_state() 함수를 호출한 후 종료한다.
초기화된 후라면 fast bin 내의 모든 chunk에 대해 인접한 이전 chunk와 다음 chunk가 사용 중인 검사하고
사용 중이 아니라면 이를 하나로 합친다.
이전 chunk와 다음 chunk를 얻는 작업은 다음과 같은 chunk_at_offset() 매크로를 이용하여 간단하게 처리할 수 있다.

/* Treat space at ptr + offset as a chunk */
#define chunk_at_offset(p, s)  ((mchunkptr)(((char*)(p)) + (s)))

이전 chunk는 chunk_at_offset(p, -(p->prev_size)), 다음 chunk는 chunk_at_offset(p, chunksize(p))로 구할 수 있다.
fast bin 내의 chunk들은 free되었어도 아직 해당하는 P (PREV_INUSE) 플래그가 지워지지 않았다.
이제 (병합되지 않은) 다음 chunk에서 해당 P 플래그를 지운다.
이렇게 병합된 chunk는 top chunk로 들어가거나 (top chunk와 인접한 chunk인 경우), unsorted bin으로 들어간다.

calloc() 함수의 구현은 (malloc()과 동일하게) 내부적으로 _int_malloc() 함수를 이용하며
주어진 size와 nmemb 인자를 곱해서 할당할 크기를 결정한 후 _int_malloc()을 호출하고
할당된 메모리를 모두 0으로 채운 후 반환한다.

realloc() 함수는 먼저 현재 chunk에 요청을 처리할 만한 여유 공간이 있거나
바로 다음 chunk가 free chunk이고 이 둘을 합친 크기가 요청을 처리할 수 있다면
둘을 병합하여 반환한다. 그렇지 않으면 _int_malloc() 함수를 호출한 뒤
이전의 메모리 내용을 새로 할당된 영역으로 복사하고 이전 영역을 free한 뒤 새로운 영역을 반환한다.

이제 free()의 경우를 살펴보도록 하자.
free() 함수는 실제로 public_fREe() 함수가 처리하며 실제 이름은 __libc_free()이다.
(마찬가지로 __free, free가 alias로 설정되어 있다.)

public_fREe() 함수는 다음과 같은 작업을 수행한다.
  1. __free_hook이 설정되어 있다면 해당 hook을 호출하고 종료한다.
  2. 주어진 메모리 영역의 포인터로부터 chunk의 포인터를 얻는다.
  3. 해당 chunk가 mmap()으로 할당된 것이라면 munmap()을 호출하여 해당 메모리 영역을 해지한다. (종료)
  4. 그렇지 않다면 해당 chunk가 속한 arena의 포인터를 얻고 lock을 건다.
  5. _int_free() 함수를 호출하여 실제 해지 작업을 수행한다.
  6. arena에 대한 lock을 푼다.

_int_free() 함수는 다음과 같은 작업을 수행한다.
  1. chunk의 헤더 정보를 통해 해당 chunk의 크기를 얻는다.
  2. 주어진 크기가 fast bin에 속한다면 (<= 72) fast bin에 해당 chunk를 삽입한다.
    1.  해당 arena가 fast bin에 chunk를 포함한다고 표시한다.
    2.  주어진 크기에 해당하는 인덱스를 계산하여 fast bin의 포인터를 얻는다.
    3.  포인터에 저장된 chunk가 현재 chunk가 일치한다면 중복해서 free()를 호출한 경우이다. 에러를 반환한다.
    4.  그렇지 않다면 fast bin의 제일 앞에 현재 chunk를 삽입한다. (종료)
  3. 이제 일반적인 해지 작업을 처리하기 전에 몇 가지 기본적인 검사를 수행한다.
  4. 현재 chunk를 인접한 (free) chunk들과 병합시킨다.
    1.  이전 chunk가 free chunk라면 현재 chunk와 병합하고, 병합된 chunk를 현재 chunk로 설정한다.
    2.  다음 chunk가 top chunk라면 현재 chunk를 top chunk로 병합하고 top chunk의 크기를 조정한다.
    3.  다음 chunk가 top chunk가 아니고 free chunk라면 병합한다.
    4.  다음 chunk가 top chunk가 아니고 사용 중인 chunk라면 다음 chunk의 P 플래그를 지운다.
  5. 현재 chunk가 top chunk가 아니라면 unsorted bin에 추가하고 현재 chunk의 size 필드와 다음 chunk의 prev_size 필드에 현재 chunk의 크기를 기록한다.
  6. (병합된) 현재 chunk의 크기가 64K 이상이고 현재 arena가 fast bin을 포함하면 malloc_consolidate()를 호출하여 fast bin을 병합한다.
  7. 현재 chunk의 크기가 정해진 크기 (128K) 이상이면 sYSTRIm() 함수를 호출하여 top chunk의 크기를 줄이려고 시도한다.

sYSTRIm() 함수는 top chunk가 (sbrk()를 통해 확장된) heap 영역에 속할 경우에만 수행되며
현재 top chunk의 크기에서 chunk 정보를 저장하기 위한 최소 크기(16)와
top chunk가 기본적으로 가져야 할 여유 공간의 크기(pad)만큼을 뺀 크기를 페이지 단위로 조정하여 sbrk()를 호출한다.
또한 __after_morecore_hook이 정의되어 있다면 해당 hook을 호출한 뒤 top chunk의 크기를 조정한다.
by namhyung | 2009/12/26 21:51 | System | 트랙백(2) | 덧글(5)
트랙백 주소 : http://studyfoss.egloos.com/tb/5206979
☞ 내 이글루에 이 글과 관련된 글 쓰기 (트랙백 보내기) [도움말]
Tracked from F/OSS study at 2009/12/29 18:48

제목 : [glibc] 동적 메모리 관리 (3)
glibc: 2.10.1 arch: x86 이전 글 보기: [glibc] 동적 메모리 관리 (1)[glibc] 동적 메모리 관리 (2) 이번에는 malloc 모듈 내의 다른 보조 함수들에 대해서 알아보기로 한다. 가장 먼저 살펴볼 함수는 mallopt() 함수이다. 이 함수는 malloc() 시의 동작을 제어하는 다음과 같은 매개 변수들을 조정할 수 있다. M_MXFAST: fast bin의 최대 크기이다. 기본값은 64로 설정......more

Tracked from tomato_house at 2010/02/09 17:23

제목 : [glibc] 동적 메모리 관리 (2)
[glibc] 동적 메모리 관리 (2)...more

Commented by SY Kim at 2009/12/27 05:38
잘보고 갑니다.
Commented by namhyung at 2009/12/27 10:39
매번 답글 남겨주셔서 감사합니다.. ^^
Commented by namhyung at 2009/12/27 18:48
정정합니다. fast bin의 최대 크기 기본값은 64이지만 실제로는 chunk header를 위한 overhead와 정렬 제한으로 인해 72 바이트 chunk에 해당합니다. 본문도 수정해 두었습니다.
Commented by taso at 2012/07/23 20:23
와..직접 소스분석하신건가요 ? ㄷㄷ..
Commented at 2013/05/06 11:05
비공개 덧글입니다.

:         :

:

비공개 덧글

◀ 이전 페이지 다음 페이지 ▶

카테고리
General
Application
System
Kernel
Book
Tips
태그
build memory C sed glibc patch kernel scm algorithm blktrace git elf CAaQA3 synchronization emacs SMP x86 awk vcs documentation compiler gcc block-layer CARM script computer-architecture bash perf binutils linux
전체보기
이글루 파인더

최근 등록된 덧글
informsi yang bagus dan be..
by pordanaia at 08/05
Informsi yang bagus dan b..
by jamalsu at 08/01
as inforasi yang menarik http..
by jamalsu at 07/22
최근 등록된 트랙백
Tod's Ferrari Homme
by Tods Pas Cher,Kodak did ..
Mocassin Femme
by Mocassins Homme, I got so..
natural garcinia cambogia
by
rss

skin by jiinny


X