oiehso0

malloc_chunk

이 구조체는 특정한 메모리의 청크를 나타낸다. 할당 / 비할당 청크에 따라 각각의 필드는 다른 의미를 가진다.

A (NON_MAIN_ARENA) :멀티스레드에 경우 각 스레드마다 다른 heap 영역을 사용할 수 있기 때문에 현재 chunk가 아레나에 속하는지

M (IS_MMAPPED) : mmap() 시스템 콜을 통해 할당 되었는지를 나타내는 플래그

P (PREV_INUSE) : 이전 청크의 사용 유무를 나타내는 플래그 0일때 free

참고 : 패스트빈의 청크는 인접한 free된 청크와 통합되지 않는다는 점에서 할당 된 청크로 처리된다.

small_bin이라면 fd_nextsize, bk_nextsize의 영역은 필요없다. large bin만 가지고 있는 구조체의 값들이다.

Allocated chunk

청크(자기자신)가 free되면 user data영역이 fd, bk로 사용된다.

이전 청크가 free상태가 아니라면 prev_size는 data영역으로 사용된다.

Free chunk

Understanding glibc malloc

커널로부터 힙 메모리는 어떻게 획득되는가?

어떻게 메모리는 능률적으로 관리되는가?

힙은 커널 또는 라이브러리 또는 어플리케이션에 의해 관리되는가?

힙 메모리를 exploit 가능한가?

많은 메모리 할당자가 존재한다.

dllmalloc - 일반적인 목적의 할당자

ptmalloc2 - glibc

jemalloc - FreeBSD와 Firefox

tcmalloc - Google(Chrome)

libumem - Solaris

등 ...

여러 메모리 할당자가 있지만 어플리케이션의 특징에 맞는 할당자를 사용해야 빠르고 확장 및 축소에 문제가 생기지 않으며, 능률적인 이다. 메모리를 효율적으로 사용해야하는 어플리케이션은 주로 메모리 할당자의 성능에 의지한다. 이 글에서는 'glibc malloc'에 대해 이야기하고 언젠가, 다른 메모리 할당자들에 대해서도 추가할 것이다. 

ptmalloc2

ptmalloc2는 dlmalloc에서 나뉘어졌다. 나뉘게 된 이후, 이것에 스레딩 지원 기능이 추가되어, 2006년에 배포되었다. 공식적인 배포 이후, ptmalloc2는 glibc 소스 코드에 통합되었다. 이 통합 이후에는, 코드의 수정을 위해서는 glibc malloc 소스 코드 자체를 직접 수정하는 것으로 변경되었다. 이런 이유로 ptmalloc2와 glibc의 malloc 실행 사이에는 많은 변화가 있었을지도 모른다.

 System Calls : 이 글에서 볼 수 있듯이 malloc은 내부에서 brk 또는 mmap syscall 중 하나를 호출한다.

Threading : 리눅스의 초창기에는, dlmalloc이 기본 메모리 할당자로 사용되었다. 그러나 ptmalloc2의 스레딩 지원 기능이 추가된 이후로는, 이것이 리눅스의 기본 메모리 할당자가 되었다. 스레딩 지원은 메모리 할당자 성능을 개량시켜주어, 어플리케이션의 성능 또한 개량된다. dlmalloc에서 동시에 2개의 스레드가 malloc을 호출할 경우, freelist 자료구조는 사용 가능한 모든 스레드 간에 공유되기 때문에 크리티컬 섹션진입으로 퍼포먼스 하락하는 문제가 있었다. ptmalloc2를 사용하면 스레드에서 메모리할당 요청을 할 때 스레드별로 분리된 힙 세그만트를 할당해 주며 그에 따라 freelist 자료구조 또한 힙과 같이 분리된 형태를 띄게 된다. 이렇게 분리되어 구성된 힙과 freelist 자료구조 형태를 per thread arena 라고 한다

예제 

pthread를 사용하기 위해 라이브러리 링크 옵션 주고 컴파일 해준다. 

예제를 실습해보고자 했지만 환경에 따라 코드설명에 따르면 동적할당을 하기 이전에는 heap이나 thread별 스택이 생성되지 않는다고 하지만

실제 환경마다 다르며 내 환경인 ubuntu의 경우 malloc과 관계없이 main heap은 프로그램 실행 시 할당되는 걸로 보인다.

문서의 본래 내용으로 설명하자면 

출력 분석 

1.

메인 스레드에서의 malloc 호출 이전 : 아래의 출력에서 힙 영역이 아직 없는 것과 thread1이 생성되지 않아 스레드의 스택이 없는 것을 볼 수 있다.

2.

메인 스레드에서의 malloc 호출 이후 : 아래의 출력에서 힙 영역이 생성되었고 데이터 영역(0x0804b000 - 0x0806c000) 위에 위치한 것을 볼 수 있고, 이는 힙 메모리가 프로그램의 break 위치를 증가시킴으로써 생성되는 것을 보여준다 ( ie) brk syscall 사용). 또한, 사용자는 오직 1000바이트만 요청했으나, 힙 메모리의 크기는 132KB나 생성되었다. 이러한 힙 메모리의 인접한 지역을 arena라고 부른다. 이 arena는 메인 스레드로써 생성되었기 때문에, 이것을 main arena라고 부른다. 이후, 할당 요청은 이 arena를 사용하여 비어있는 공간이 없어질 때 까지 유지하면서 사용한다. arena의 비어있는 공간이 고갈되었을 경우, 프로그램의 break 위치를 증가시킴으로써 더욱 성장할 수 있다 (top 청크의 크기를 증가시켜 여분의 공간을 포함할 수 있도록 조정한 후). 이와 비슷하게 top 청크에 비어있는 공간이 많은 경우, arena는 또한 줄어들 수도 있다.

NOTE : top 청크는 arena의 최상단의 청크를 말한다. 아래에서는 이것에 대해 자세하게 "Top Chunk" 섹션을 보여준다.

3.

메인 스레드에서의 free 호출 이후 : 아래의 출력에서 할당된 메모리 집단이 해제된 경우, 메모리의 뒤에서 해제된 메모리가 즉각 운영체제에 반환되지 않는 것을 볼 수 있다. 할당된 메모리의 일부분(1000바이트)은 오로지 main arena의 bin(glibc malloc에서, freelist data structures는 bin으로써 참조됨)에 이 해제된 블럭을 추가하고 'glibc malloc' 라이브러리에 반환된다. 이후, 사용자가 메모리를 요청하는 경우, 'glibc malloc'은 커널로부터 새로운 힙 메모리를 얻지 않고, 대신 bin에서 비어있는 블럭을 탐색해준다. 그리고 비어있는 공간이 존재하지 않는 경우, 커널로부터 메모리를 받는다.

4.

thread1에서의 malloc 호출 이전 : 아래의 출력에서 thread1의 힙 영역은 없으나, thread1의 스레드 스택은 생성된 것을 볼 수 있다.

5.

thread1에서의 malloc 호출 이후 : 아래의 출력에서 thread1의 힙 영역이 생성된 것을 볼 수 있다. 그리고 이 영역은 메모리의 메핑된 세그먼트 일부 (0xb7500000-0xb7521000, 132KB의 크기)에 위치하며, sbrk를 사용하는 main thread와 달리 mmap을 사용하여 힙 메모리가 생성된다. 여기서 다시 볼 수 있듯이, 사용자는 1000바이트만 요청했지만, 1MB 크기의 힙 메모리가 프로세스 주소 공간에 매핑되어 있다. 이 1MB 중, 132KB가 read-write 권한이 세트되어, 이 스레드를 위해 힙 메모리로 할당되었다. 이러한 메모리의 일부분(132KB)을 thread arena라고 부른다.

NOTE : 사용자가 128KB(malloc(132*1024))보다 큰 크기를 요청할 경우와 arena에 사용자의 요청을 만족시킬 수 있는 충분한 공간이 없는 경우, 비록 main arena 또는 thread arena에서 만들어진 요청이지만 이것을 무시하고 메모리는 mmap syscall(sbrk 미사용)을 사용하여 할당된다.

thread1에서의 free 호출 이후 : 아래의 출력에서 해제한 할당된 메모리 집단은 운영체제에 힙 메모리를 반환하지 않는다. 대신 할당된 메모리 지역(1000바이트)을 thread arena의 bin에 해제된 블럭을 추가하고 'glibc malloc'에 반환한다.

Bin : free로 해제된 Chunk들을 관리하기 위한 연결리스트, 해제된 Chunk의 크기에 따라 세세하게 분류(fast, small, large)하여 관리된다.

arena의 수 

위의 예제에서, 메인 스레드가 main arena를 가지고 thread1이 자신의 thread arena를 가지는 것을 보았다. 그래서 스레드의 수를 무시하고 스레드들과 arena 사이의 일대일 매핑은 존재할 수 있는가? 틀림없이 아니다. 맛이 간 어플리케이션은 core의 수보다 많은 스레드의 수를 가질 수 있으나, 이러한 경우는, 하나의 arena당 스레드를 가져 bit가 크게 낭비된다. 이런 이유로, 어플리케이션의 arena 제한은 현재 시스템의 core의 수에 기반된다.

For 32 bit systems:

Number of arena = 2 * number of cores.

For 64 bit systems:

Number of arena = 8 * number of cores.

다중 Arena 

예제 : 1개의 코어를 가진 32bit 시스템에서 다중스레드 어플리케이션(4개의 스레드 = 메인 스레드 + 3개의 사용자 스레드)을 실행시켜 보자. 여기서 스레드가 없는 경우 (4) > 2개의 코어가 없는 경우 (2)를 확인할 수 있다. 이런 이유로 이와 같은 상황에서, 'glibc malloc'는 다중 arena가 모든 사용가능한 스레드와 공유되는지를 확인한다. 그런데 어떻게 공유하는가?

메인 스레드의 경우, 처음으로 malloc을 호출하면 이미 생성되어 있던 main arena는 어떠한 충돌도 없이 사용된다.

thread1과 thread2가 처음으로 malloc을 호출하는 경우, 이 스레드들을 위해 새로운 arena가 생성되고 어떠한 충돌도 없이 사용된다. 여기까지는 스레드와 arena가 일대일 매핑을 가진다.

thread3이 처음으로 malloc을 호출하는 경우, arena의 제한 개수가 계산된다. 여기서 arena의 한계를 넘어, 현재 존재하는 arena들(Main arena나 Arena1 또는 Arena2)을 재사용한다.

재사용 

사용가능한 arena들이 한 번의 루프를 넘는 동안, arena에 lock을 반복한다.

만일 성공적으로 lock된 경우(main arena가 성공적으로 lock된 경우), 사용자에게 arena는 반환된다.

만일 어떠한 arena도 해제되지 않은 경우, 다음 행에 arena를 위한 블럭이 있다.

thread3이 malloc을 호출한 경우(두 번째 호출), malloc은 가장 마지막에 접근한 arena를 사용할 것이다(main arena). 만일 main arena를 해제하는 경우, 또 다른 thread3을 main arena가 해제된 곳까지 폐쇄시킨 후, 이를 사용한다. 그래서 main arena는 main thread와 thread3에 공유된다.

다중 힙 :

주로 'glibc malloc'의 소스 코드에서 아래와 같은 3개의 데이터 구조체를 확인할 수 있다 :

heap_info : Heap Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있다. 각 힙은 각자의 헤더를 가진다. 왜 여러 개의 힙이 필요한가? 모든 스레드 arena는 오직 하나의 힙만을 가지고 시작하지만, 힙 영역의 공간이 부족해지는 경우, arena에 새로운 힙(인접하지 않은 영역)을 할당해주어야 한다.

malloc_state : Arena Header - 단일 스레드 arena는 여러 개의 힙을 가질 수 있지만, 이러한 모든 힙에 대해서는 오직 하나의 arena header만이 존재한다. Arena header는 bin, top chunk, last remainder chunk 등에 대한 정보를 가진다.

malloc_chunk : Chunk Header - 힙은 사용자의 요청을 기반으로 다수의 청크로 분열된다. 그리고 각 청크는 각자의 청크 헤더를 가진다.

 NOTE :

Main arena는 여러 개의 힙과 heap_info 구조체를 가질 수 없다. main arena의 공간이 부족한 경우, sbrk 힙 영역은 메모리가 매핑된 영역까지 확장(인접한 영역)된다.

thread arena와 달리, main arena의 arena header는 sbrk 힙 영역의 일부가 아니다. main arena는 전역 변수이며, libc.so의 데이터 영역에서 찾을 수 있다.

main arena와 thread arena를 그림으로 나타낸 경우(단일 힙 영역) :

thread arena를 그림으로 나타낸 경우(여러 개의 힙 영역) :

Chunk : 청크는 힙 영역에서 찾을 수 있으며, 아래 중 하나의 타입을 가진다 :

Allocated chunk

Free chunk

Top chunk

Last Remainder chunk

Allocated chunk(할당되어 있는 청크) :

prev_size : 만일 이전 청크를 해제하는 경우, 이 필드는 이전 청크의 크기를 저장한다. 만일 이전 청크가 할당된 경우에는, 이 필드는 이전 청크의 사용자 데이터를 저장한다.

size : 이 필드는 할당된 청크의 크기를 저장한다. 이 필드의 맨 끝 3bit는 flag 정보를 저장한다.

PREV_INUSE (P) - 이 비트는 이전 청크가 할당된 경우 세트된다.

IS_MMAPPED (M) - 이 비트는 현재 청크가 mmap을 통해 할당된 경우 세트된다.

NON_MAIN_ARENA (N) - 이 비트는 현재 청크가 thread arena에 위치하는 경우 세트된다.

NOTE :

malloc_chunk의 다른 필드(fd,bk)는 할당되어 있는 청크에서는 사용하지 않는다. 따라서 할당되어 있는 청크는 사용자 데이터가 저장되어 있다.

사용자가 요청한 크기는 malloc_chunk를 저장하고 메모리를 정렬하기 위해서는 약간의 공간이 여분으로 필요하기 때문에 사용할 수 있는 크기(청크 내부를 나타내는 크기)로 변환된다.

Free Chunk(해제된 청크) :

prev_size : 2개의 free chunk는 함께 붙어 있을 수 없다. 각 청크를 해제하는 경우, 하나의 단일 free chunk로 결합된다. 따라서, 항상 해제된 청크의 이전 청크를 할당하고 있어서, prev_size는 이전 청크의 사용자 데이터를 저장하고 있다.

size : 이 필드는 free chunk의 크기를 저장하고 있다.

fd : Forward pointer - 동일한 빈에서의 다음 청크를 가리킨다(물리 메모리에서의 다음 청크가 아님).

bk : Backward pointer - 동일한 빈에서의 이전 청크를 가리킨다(물리 메모리에서의 이전 청크가 아님).

Bins : Bin은 freelist data structures이며, free chunk들을 수용하는데 사용한다. 청크의 크기를 기준으로 사용가능한 bin이 달라지게 된다 :

Fast bin

Unsorted bin

Small bin

Large bin

Data structures는 이 bin들을 수용하는데 사용한다 :

fastbinsY - 이 배열은 fast bin을 수용한다.

bins - 이 배열은 unsorted, small 그리고 large bin을 수용한다. 총 126개의 bin이 있고 다음과 같은 기준으로 나뉜다 :

Bin 1 - Unsorted bin

Bin 2 ~ Bin 63 - Small bin

Bin 64 ~ Bin 126 - Large bin

Fast Bin : 청크의 크기가 16 ~ 80바이트인 경우, fast chunk라고 부른다. fast chunk를 수용한 bin을 fast bin이라고 부른다. 모든 bin들 중 가운데, fast bin은 메모리 할당과 반납(해제)가 빠르다.

bin의 갯수 - 10

각 fast bin은 free chunk로 구성된 단일 연결리스트(다른 말로 binlist)를 가진다. 단일 연결리스트는 list의 중간으로부터 fast bin chunk을 제거할 수 없기 때문에 사용된다. 추가와 제거는 list의 앞쪽 끝에서 발생한다 - LIFO.

청크의 크기 - 각 8바이트씩

Fast bin은 각 8바이트 크기를 가지는 청크의 binlist를 가진다. ie) 첫 번째 fast bin(index 0)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 fast bin(index 1)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.

fast bin 내부의 청크는 동일한 크기이다.

malloc 초기화에서, fast bin의 최대 크기는 64(!80)바이트로 세트되어 있다. 따라서, 기본 청크의 크기는 16 ~ 64인 경우, fast chunk로 분류된다.

병합 없음 - 해제된 2개의 청크가 서로 인접해 있을 수 있으며, 단일 free chunk로 결합되지 않는다. 병합이 없다는 것은 외부 단편화라는 결과를 가져올 수 있지만 해제의 속도가 빠르다는 장점도 있다!!

malloc(fast chunk) -

초기의 fast bin의 최대 크기와 fast bin 인덱스는 비어 있기 때문에, 사용자가 fast chunk를 요청하더라도, fast bin code 대신, small bin code가 서비스할 수 있다.

이후에 비어있지 않게 된 경우, fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.

위에서 반환된 binlist의 첫 번째 청크는 삭제된 후, 사용자에게 반환된다.

free(fast chunk) -

Fast bin 인덱스는 해당하는 binlist로부터 검색을 하여 계산된다.

free chunk는 위에서 반환된 binlist의 앞쪽 위치에 추가된다.

Unsorted Bin : small 또는 large chunk는 각각의 bin에서 추가가 아닌 해제되는 경우, unsorted bin에 추가된다. 이러한 처리방법은 최근에 해제된 청크를 재사용할 수 있도록 'glibc malloc'가 2번째 기회를 제공하기 위해서 있다. 따라서, 적절한 bin을 찾는데 걸리는 시간이 적기 때문에 메모리 할당과 반납의 비트 처리 속도가 빠르다(unsorted bin이기 때문).

bin의 개수 - 1

Unsorted bin은 free chunk의 환형 이중 연결리스트(다른 말로 binlist)를 가진다.

청크의 크기 - 크기에 제한이 없기 때문에, 다양한 크기의 청크가 이 bin에 저장될 수 있다.

Small Bin : 청크의 크기가 512바이트보다 작은 경우, small chunk라고 부른다. small chunk를 수용한 Bin을 small bin이라고 부른다. Small bin은 메모리 할당 및 반환이 large bin보다 빠르다(다만, fast bin보다는 느리다).

bin의 개수 - 62

각 small bin은 free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 list의 중간에서 small bin chunk를 제거할 수 있기 때문에 사용된다. 노드의 추가는 앞쪽 끝에서 발생하고 삭제는 list의 뒤쪽 끝에서 발생한다 - FIFO.

청크의 크기 - 각 8바이트씩Small bin은 각 8바이트 크기를 가지는 청크 binlist를 가진다. ie) 첫 번째 Small bin(Bin 2)은 16바이트 크기의 청크 binlist를 가지며, 두 번째 small bin(Bin 3)은 24바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.

small bin 내부의 청크는 동일한 크기이며, 따라서 정렬이 필요없다.

병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다. 병합은 외부 단편화를 제거하지만, 해제의 속도가 느리다.

malloc(small chunk) -

초기의 모든 small bin은 NULL이기 때문에, 사용자가 small chunk를 요청했더라도, small bin code 대신, unsorted bin code가 서비스할 수 있다.

또한 malloc을 처음 호출할 경우, small bin과 large bin의 datastructures (bins)는 malloc_state는 초기화되어 있기 때문에 찾을 수 있다. ie) bin은 비어있는 자기자신을 가리키고 있다.

이후에 small bin이 비어있지 않은 경우, 해당하는 binlist의 마지막 청크는 제거된 후, 사용자에게 반환된다.

free(small chunk) -

이 청크를 해제하는 동안, 이전 또는 다음 청크가 해제되었는지 체크하여, 해제된 경우 병합한다. ie) 각각의 연결 리스트로부터 청크를 제거하고 unsorted bin의 연결 리스트의 시작 부분에 새롭게 합병된 청크를 추가한다.

Large Bin : 청크의 크기가 512바이트와 같거나 큰 경우, large chunk라고 부른다. large chunk를 수용한 Bin을 large bin이라고 부른다. Large bin은 메모리 할당 및 반환이 small bin보다 느리다.

bin의 개수 - 63

각 large bin은 free chunk로 구성된 환형 이중 연결리스트를 가진다. 이중 연결리스트는 어느 위치(맨 앞, 중간, 끝)에서나 large bins chunk를 추가하고 삭제할 수 있기 때문에 사용된다.

63개의 bins :

32개의 bin은 각 64바이트 크기를 가지는 청크의 binlist를 가진다. ie) 첫 번째 large bin(Bin 65)은 512바이트 ~ 568바이트 크기의 청크 binlist를 가지고, 두 번째 large bin(Bin 66)은 576바이트 ~ 632바이트 크기의 청크 binlist를 가지는 식으로, 이어진다.

16개의 bin은 각 512바이트 크기를 가지는 청크의 binlist를 가진다.

8개의 bin은 각 4,096바이트 크기를 가지는 청크의 binlist를 가진다.

4개의 bin은 각 32,768바이트 크기를 가지는 청크의 binlist를 가진다.

2개의 bin은 각 262,144바이트 크기를 가지는 청크의 binlist를 가진다.

1개의 bin은 남은 크기를 가지는 청크를 가진다.

small bin과 달리, large bin 내부의 청크는 동일한 크기를 가지고 있지 않다. 따라서, 내림차순으로 저장된다. 가장 큰 청크는 binlist의 가장 앞쪽에 저장되고, 가장 작은 청크는 binlist의 가장 뒷쪽에 저장된다.

병합 - 해제된 2개의 청크는 각각 인접해 있을 수 없으며, 단일 free chunk로 결합된다.

malloc(large chunk) -

초기의 모든 large bin은 NULL이기 때문에, 사용자가 large chunk를 요청했더라도, large bin code 대신, next largest bin code가 서비스할 수 있다.

또한 malloc을 처음 호출할 경우, small bin과 large bin의 datastructures (bins)는 malloc_state는 초기화되어 있기 때문에 찾을 수 있다. ie) bin은 비어있는 자기자신을 가리키고 있다.

이후에 large bin이 비어있지 않은 경우에서, largest chunk(이것의 binlist에서)의 크기가 사용자가 요청한 크기보다 크다면, binlist를 뒷쪽 끝부터 앞쪽 끝까지 확인하여, 사용자가 요청한 크기에 가깝거나 같은 적합한 크기의 청크를 찾는다. 찾게 되면, 해당 청크는 2개의 청크로 분리된다.

User chunk(사용자가 요청한 크기) - 사용자에게 반환

Remainder chunk(나머지 크기) - unsorted bin에 추가

만일 largest chunk(이것의 binlist에서)의 크기가 사용자가 요청한 크기보다 작다면, 비어있지 않는 다음 largest bin을 사용하여 사용자의 요청에 응답한다. 다음 largest bin code는 비어있지 않은 다음 largest bin을 찾기 위해 binmaps을 스캔하여, 해당하는 bin을 찾은 경우, 해당 binlist에서 적합한 청크가 검색되고, 적합한 청크를 분리하여 사용자에게 반환된다. 만일 찾지 못 한 경우에는, top chunk를 사용하여 사용자의 요청에 응답한다.

free(large chunk) - free(small chunk)와 절차가 비슷하다.

Top Chunk : arena의 가장 꼭대기 가장자리에 있는 청크를 top chunk라고 부른다. Top chunk는 어떤 bin에도 속하지 않는다. Top chunk는 bin들 중 하나에서 해제된 블럭이 없는 경우, 사용자의 요청에 응답하기 위해 사용된다. 만일 top chunk가 사용자가 요청한 크기보다 큰 경우, top chunk는 2개로 분리된다 :

User chunk(사용자가 요청한 크기)

Remainder chunk(나머지 크기)

remainder chunk는 새로운 꼭대기가 된다. 만일 top chunk의 크기가 사용자가 요청한 크기보다 작은 경우, sbrk(main arena) 또는 mmap(thread arena) syscall을 사용하여 top chunk를 확장시킨다.

Last Remainder Chunk : Remainder는 요청에 의해 너무 작게 분할되어 만들어진다. Last remainder chunk는 지역 참조성을 증가시키는데 도움을 준다. ie) 연속된 작은 청크의 malloc 요청은 결국 각각의 할당을 끝낼 것이다.

그러나 arena에서 사용가능한 많은 청크 중, last remainder chunk에 적합한 청크는?

사용자가 작은 청크를 요청했는데, small bin과 unsorted bin으로 제공할 수 없는 경우, binmaps는 비어있지 않는 다음 largest bin을 찾기 위해 스캔된다. 무사히, 비어있지 않는 다음 largest bin을 찾은 경우, 2개로 분리되어, user chunk는 사용자에게 반환되고 remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다.

어떻게 지역 참조성을 달성시키는가?

뒤늦게 사용자가 작은 청크를 요청했으나, last remainder chunk가 오로지 unsorted bin에만 있는 청크인 경우, last remainder chunk는 2개로 분리되어, user chunk는 사용자에게 반환되고 remainder chunk는 unsorted bin에 추가된다. 이 추가로 새로운 last remainder chunk가 생겼다. 이와 같은 후속 메모리 할당은 서로의 옆에 할당되는 것으로 끝난다.

Stub Code : 사용자가 입력한 코드가 아닌 컴파일러가 임의로 추가시킨 코드이다. 컴파일러 별로 Stub Code 모양이 상이하다.

OllyDbg 기본 명령어

Restart [Ctrl+F2] 다시 처음부터 디버깅 시작

Step Into [F7] 하나의 OP code 실행 (CALL 명령을 만나면, 그 함수 코드 내부로 따라 들어감)

Step over [F8] 하나의 OP code 실행 (CALL 명령을 만나면, 따라 들어가지 않고 그냥 함수 자체를 실행)

Execute til Return [Ctrl+F9] 함수 코드 내에서 RETN 명령어 까지 실행(함수 탈출 목적)

추가적 명령어

Go to [Ctrl+G] 원하는 주소로 이동(코드/메모리를 확인할 때 사용. 실행되는것은 아님)

Execute till Cursor [F4] cursor 위치까지 실행(디버깅하고 싶은 주소까지 바로 갈 수 있음)

Comment [ ; ] Comment 추가

User-defined comment 마우스 우측 메뉴 Search for User-defined comment

Label [ : ] Label 추가

User-defined label 마우스 우측 메뉴 Search for User-defined label

Set/Reset BreakPoint [F2]

Run [F9] 실행(BP가 걸려있으면 그곳에서 실행이 정지됨)

Show the current EIP  [ * ] 현재 EIP 위치를 보여줍니다.

Show the previous Cursor [ - ] 직전 커서 위치를 다시 보여줍니다.

Preview CALL/JMP address [Enter] 커서가 CALL/JMP등의 명령어에 위치한다면, 해당 주소를 따라가서 보여줌(실행되는 것이 아님. 간단히 함수 내용을 확인할 때 유용함)

Animate Into [Ctrl+F7] Step Into 명령 반복 화명 표시 됨

Animate Over [Ctrl+F8] Step Over 명령 반복

Trace Into [Ctrl+F11] Step Into 명령 반복 화면 표시 안됨

Trace Over [Ctrl+F12] Step Over 명령 반복

문자열 검색 마우스 우측 메뉴 - Search for - All referenced text strings

코드에서 사용된 API 호출 목록 보기 - All intermodular calls

(Packer/Protector를 사용하여 실행파일을 압축/보호해버리면, 파일 구조가 변경되어 API호출목록이 보이지 않는다.(심지어 디버깅 자체가 어려워짐)

바이트오더링 (빅엔디언 사람이보기에 직관적 / 리틀엔디언 산술 연산과 데이터의 타입이 확장,축소될 때 효율적)

타입    name    size    빅    리틀

BYTE       b      1      [12]    [12]

WORD     w     2     [12][34]    [34][12]

DWORD  dw    4     [12][34][56][78]    [78][56][34][12] 

스택창에서 마우스 우측 메뉴 Address - Relative to EBP - EBP 기준으로 표시되기 때문에 좀 더 직관적으로 보인다.

어셈블리와 C언어의 포인터 구문 형식

어셈블리 언어                        C언어                     Type casting

DWORD PTR SS:[EBP-4]        *(DWORD *)(EBP-4)          DWORD (4바이트)

WORD PTR SS:[EBP-4]          *(WORD *)(EBP-4)           WORD (2바이트)

BYTE PTR SS:[EBP-4]             *(BYTE *)(EBP-4)                BYTE

'DWORD PTR'과 'SS:' 안보이게 설정 가능

호출한 쪽(Caller)에서 스택에 저장된 파라미터를 정리하는 것을 'cdecl' 방식이라하고 호출당한 쪽(Callee)에서 스택에 저장된 파라미터를 정리하는 것을 'stdcall' 방식이라고 한다. 이러한 호출 규약을 일컬어 Calling Convention이라고 말한다.

Debugging options - Analysis1 - Show ARGs and LOCALs in procedures 메뉴를 이용하면 로컬 변수와 파라미터 형식으로 표시된다.

TEST : 논리비교 'AND' 연산과 동일하지만 operand 값이 변경되지 않고 EFLAGS 레지스터만 변명됨)

Process Explorer 프로세스들을 Parent/Child의 트리 구조로 표시한다. PID, CPU점유율, 프로세스에 로딩된 DLL 정보나 오픈한 object handle을 표시한다.

프로세스 Suspend/Resume, 종료기능도 있음 

fastcall 방식은 기본적으로 함수에 전달하는 파라미터 일부(2개까지)를 스택 메모리가 아닌 레지스터를 이용하여 전달한다는 것이 특징이다. 어떤 함수의 파라미터가 4개라면, 앞의 두개의 파라미터는 각각 ECX, EDX파라미터를 이용하여 전달합니다.

Search for - All intermodular calls 명령을 사용하면 프로그램에 사용되는 API 호출 목록이 나타납니다.

Set breakpoint on every call to rtcMsgBox 메뉴를 선택하면 rtcMsgBox를 호출하는 모든 코드에 BP가 설치된다.

PE파일의 종류

실행 계열 EXE, SCR        드라이버 계열 SYS, VXD        라이브러리 계열 DLL, OCX, CPL, DRV        오브젝트 파일 계열 OBJ

PE파일이 메모리에 로딩되는 모습

PE헤더의 구성

DOS Header - PE헤더의 앞부분에는 기존 DOS EXE Header를 확장시킨 IMAGE_DOS_HEADER구조체가 존재한다.

그중 e_magic : DOS signature와 e_lfanew : NT header의 옵셋을 표시  가 중요하다.

DOS Stub의 존재 여부는 옵션이며 코드와 데이터의 혼합으로 이루어져 있다.

32비트 Windows OS에서는 이쪽 명령어가 실행되지 않는다.(PE파일로 인식하기 때문에) 하지만 DOS 환경에서 실행하거나 DOS용 디버거를 이용해서 실행하면 실행된다.(한마디로 DOS EXE 파일로 인식한다. 이들은 PE File Format을 모르기 때문에.)

IMAGE_NT_HEADERS 구조체는 3개의 멤버로 되어 있는데 1번째 시그니처와 File Header와 Optional Header 구조체 멤버가 있습니다.

우선 IMAGE_FILE_HEADER는 4가지 멤버가 중요하다 1.Machine 2.NumberOfSections 3.SizeOfOptionalHeader(이 값을 보고 IMAGE_OPTIONAL_HEADER32 구조체 크기 인식, PE32+경우 64구조체를 사용) 4.Characteristics(파일의 속성을 나타내는 값으로, 실행가능 한지 OR DLL 파일인지 등의 정보들이 bit OR 형식으로 조합됩니다.

다음으로 PE헤더 구조체 중에서 가장 크기가 큰 IMAGE_OPTIONAL_HEADER32이다. 멤버 값이 파일실행에 필수적이라 잘못 세팅되면 파일이 정상 실행 X

1.Magic 2.AddressOfEntryPoint는 EP의 RVA 값을 가지고 있다. 프로그램에서 최초로 실행되는 코드의 시작 주소로, 매우 중요한 값

3.ImageBase PE파일이 로딩되는 시작 주소를 나타낸다.

4.SectionAlignment  메모리에서 섹션의 최소단위, FileAlignment 파일에서 섹션의 최소단위

5.SizeOfImage PE파일이 메모리에 로딩되었을 때 가상 메모리에서 PE Image가 차지하는 크기 

6.SizeOfHeader  PE헤더의 전체 크기를 나타냅니다. 이 값 역시 FileAlignment의 배수여야한다.

7.Subsystem 값에 따라 시스템 드라이버 파일(*.sys)인지 일반 실행(*.exe, *.dll)인지 구분할 수 있다.

8.NumberOfRvaAndSizes 마지막 멤버인 DataDirectory 배열의 개수를 나타냅니다.

9.DataDirectory는 IMAGE_DATA_DIRECTORY 구조체의 배열로, 배열의 각 항목마다 정의된 값을 가집니다.

RVA(Relative Virtual Address) < - > RAW(file offset) 변환 작업 중요

RAW(파일에서의 주소) - PointerToRawData(파일에서 섹션의 시작주소) = RVA(메모리에서의 주소) - VA(메모리에서의 섹션의 시작주소)

Packer 일반 PE파일을 실행 압축 파일로 만들어 주는 유틸리티

UPX 파일 트레이싱 루프를 만나면 역할을 살펴보고 탈출한다. 

DLL 로딩 방식

Explicit Linking 프로그램에서 사용되는 순간에 로딩하고 사용이 끝나면 메모리에서 해제되는 방법

Implicit Linking 프로그램 시작할 때 로딩되어 프로그램 종료할 때 메모리에서 해제되는 방법

IAT(Import Address Table)은 후자의 링킹 방식을 사용 Windows OS에서 사용

쓰이는 이유 DLL Relocation때문이다. DLL은 PE헤더에 명시된 ImageBase에 로딩된다는 보장이 없다. 반면에 process 생성 주체가 되는 EXE파일은 자신만의 가상 메모리 공간을 가지기 때문에 보장이 있다. windows 시스템 dll은 고유한 이미지베이스를 가지고 있어서 리로케이션 발생 x

INT(Import Name Table) 임포트하는 함수의 정보가 담긴 구조체 포인터 배열이다.

EAT는 라이브러리 파일에서 제공하는 함수를 다른 프로그램에서 가져다 사용할 수 있도록 해주는 핵심 메커니즘이다.

PE 재배치 작업의 기본 동작 원리

프로그램에서 하드코딩된 주소 위치를 찾는다. -> 값을 읽은 후 ImageBase만큼 뺀다.(VA->RVA) -> 실제 로딩 주소를 더한다.(RVA->VA)

.reloc섹션 수동으로 제거하기

1. .reloc 섹션 헤더 정리 (헥스에디터를 이용해서 0으로 덮어줌)

2. .reloc 섹션 제거 (섹션을 물리적으로 제거 HxD의 'Delete' 기능을 이용하면 편리)

3. IMAGE_FILE_HEADER 수정 (Number of Sections 항목에서 -1 해줌 섹션이 하나 줄었기 때문에)

4. IMAGE_OPTIONAL_HEADER 수정 (Size of Image 값에 이미지 크기를 수정해야함)

UPack은 두 번째 섹션에 압축된 원본 데이터가 존재하고, 이 데이터를 디코딩 루프를 돌면서 첫 번째 섹션에 압축해제 합니다.

UPACK은 IMAGE_DOS_HEADER의 e_lfanew 멤버에 값을 변경해 IMAGE_NT_HEADERS의 시작위치를 당겨 MZ헤더와 PE헤더의 겹쳐쓴다.

그리고 헤더 안에 디코딩 코드를 삽입하기 위해 IMAGE_FILE_HEADER.SizeOfOptionalHeader의 값을 변경한다. 이 값을 늘리면 IMAGE_SECTION_HEADER는 IMAGE_OPTIONAL_HEADER과의 사이 공간이 늘어나도 디코딩 코드를 추가할 수 있다. 

IMAGE_OPTIONAL_HEADER.NumberOfRvaAndSizes 값을 변경해 IMAGE_DATA_DIRECTORY 구조체 배열의 원소 개수를 변경한다. 정상적인 파일은 10개의 배열 개수를 갖는다. Upack에서는 A개로 변경하고 역시 남게되는 하나의 배열에 자신의 코드를 덮는다.

섹션과 헤더를 겹쳐쓰고 IMAGE_SECTION_HEADER에 정의된 값에 따라 같은 파일 이미지를 가지고 각각 다른 위치와 다른 크기의 메모리 이미지를 만들 수 있다.

헤더영역의 RVA와 RAW 값은 동일하다.

섹션 시작의 파일 옵셋을 가리키는 PointerToRawData 값은 FileAlignment의 배수가 되어야하는데 PointerToRawData가 10이므로 강제로 배수를 맞춰 0으로 인식한다. 이것이 바로 UPack파일이 실행은 되지만 PE 관련 유틸에서 에러가 발생했던 이유이다.

인라인 패치

Assemble [Space] 명령과 'Edit' [Ctrl+E] 명령을 이용하여 인라인 패치를 진행한다.

REP(Repeat String)

ECX 레지스터를 카운터로 사용해서 문자열 관련 명령을 ECX>0인 동안 반복한다.

한번 진행될 때마다 ECX 레지스터값이 -1 된다.

MOVS(Move String)

Source에서 Destination으로 데이터를 복사한다.

ex) REP MOVS destination, source

패치코드 끼워넣고 적당한 JMP문 패치

훅 (정보를 엿보거나 가로챔)

Windows 운영체제는 GUI를 제공하고, 이는 Event Driven 방식으로 동작한다. 키보드/마우스를 이용하여 메뉴 선택, 버튼 선택, 창 변경, 이동 모두 이벤트이다. 이벤트가 발생할때 OS는 미리 정의된 메세지를 해당 응용 프로그램에 통보한다.

ex) 키보드 입력 이벤트 메세지인 WM_KEYDOWN 메세지가 [OS message queue]에 추가되고 OS는 어느 응용프로그램에서 이벤트가 발생했는지 파악하고 큐에서 메세지를 꺼네 해당 응용 프로그램에 메세지 큐에 추가한다. 응용프로그램은 메세지큐를 모니터링 하고 있다가 추가된 게 확인되면 Event handler를 호출한다. 훅을 여러개 설치해 순서대로 호출되는 체인도 가능 

Break on new module 옵션 디버기 프로세스에 새로운 DLL이 로딩될때 자동으로 디버깅을 멈추는 옵션

시스템 자원은 OS가 직접 관리한다.(안정성, 보안, 효율, 기타)

이럴 때 사용자 애플리케이션은 시스템 커널에게 요청해 MS에서 제공한 Win32 API를 이용하는데 API 함수 없이는 어떤 의미 있는 프로그램도 만들 수 없다.(프로세스, 스레드, 메모리, 파일, 네트워크, 레지스트리, 그래픽, 사운드, 기타 시스템 자원에 접근) 

실제 어플리케이션 코드를 실행하기 위해 많은 시스템 라이브러리가 로딩된다.

ex) notepad.exe에서 c:/abc.txt라는 파일을 열고자 하면 msvcrt!fopen() API를 호출한다. 후에

-msvcrt!fopen()

 kernel32!CreatFileW()

  ntdll!ZwCreateFile()

   ntdll!KiFastSystemCall()

    SYSENTER

-> 커널 모드 진입           이런 과정으로 타고 내려간다.

후킹 API 호출 과정은 사용자가 DLL 인젝션 기술로 hook.dll을 프로세스 메모리 공간에 침투시키고 Kernel32!CreateFile() API가 호출될 때마다 hook!MyCreateFile()이 먼저 호출되어 사용자와 커널 사이에 return, call을 주고 받는다.

API 후킹 부분은 IAT, 프로세스 메모리에 매핑된 시스템 라이브러리에서 실제 API 주소를 찾아 직접 수정, EAT가 있다.