Heap 메모리 구조2 - bins

Index

bins

Bin이라는 구조를 이용하여 해제된 청크를 크기 단위로 관리한다. 이는 메모리 할당 요청시 이전에 사용했던 크기의 chunk가 있다면 신속하게 재할당하기 위함이다. 크기에 따라 4가지 유형으로 나뉜다(glibc-2.26 이후 tcachebins가 추가되어 5가지의 bins). 크기가 클 수록 할당/해제가 느려지고, 크기가 작을 수록 할당/해제가 빠른 bins를 사용한다.

fast bin

이름 그대로 메모리 할당과 해제가 가장 빠른 bin이다. LIFO(후입선출) 방식을 사용하고, Freed chunk구조에서 fd의 값을 이용해서 단일 연결리스트로 chunk를 관리한다. 예제 코드를 통해서 chunk의 할당과 해제 시 어떻게 관리하는지 확인해보자.

//Name : fastbin.c
//Compiler : gcc -o fastbin fastbin.c -no-pie -fno-stack-protector
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

int main(){
        char *chunk0 = (char *)malloc(0x0);
        char *chunk1 = (char *)malloc(0x10);
        char *chunk2 = (char *)malloc(0x20);
        char *chunk3 = (char *)malloc(0x25);
        char *chunk4 = (char *)malloc(0x30);
        char *chunk5 = (char *)malloc(0x80);
        char *chunk6 = (char *)malloc(0x88);
        char *chunk7 = (char *)malloc(0x90);
        free(chunk0);
        free(chunk1);
        free(chunk2);
        strcpy(chunk3, "1234567890123456789012345678901234567");
        free(chunk3);
        free(chunk4);
        free(chunk5);
        free(chunk6);
        free(chunk7);
        return 0;
}

fastbin이 관리하는 chunk의 크기는 32bit 운영체제에서는 16~88byte(10개의 bin)이고, 64bit 운영체제에서는 32~128byte(7개의 bin만 사용)이다. 64bit 기준으로 fastbin에 속하는 여러 사이즈의 청크를 할당하고 해제하면서 메모리를 확인해보자.

위 메모리 상태는 예제 코드의 모든 chunk를 할당하고, 아직 해제(free)가 진행되지 않은 상태이다.

free(chunk0);

malloc(0)이 할당된 chunk0이 해제되었다. malloc 인자로 0을 줬지만, 해제되었을 때의 chunk의 기본구조를 나타내기 위해서 0x20의 size를 가진다. 0x20크기의 chunk를 관리하는 fastbin[0]에 들어간 것을 확인할 수 있다.

free(chunk1);

chunk1은 malloc(0x10)이었다. 하지만 chunk의 실제 크기는 data를 담는 영역(0x10)과 헤더(0x10)가 합쳐져서 0x20크기가 구성된다. 기본 구성을 갖추기 위해 0x20 크기만큼 할당된 chunk0과 같은 크기를 할당받게 되고, 해제 시에 0x20 크기를 담는 fastbin[0]에 들어간다. 이때 fastbin은 LIFO(후입선출) 구조를 가지기 때문에 나중에 들어간 chunk1(d49020)이 재할당 필요 시 먼저 할당된다. 위 사진에서도 chunk1(d49020)의 fd 값은 chunk0(0xd49000)으로 fd를 통해 연결되어 관리하는 것을 확인할 수 있다.

free(chunk2);

chunk2는 malloc(0x20)이다. 헤더 크기 0x10을 더하여 0x30의 크기를 가지고, 해제 시 fastbin[1]에 들어간 것을 확인할 수 있다. 앞서 설명한 내용과 중복되는 설명은 생략한다.

strcpy(chunk3, "1234567890123456789012345678901234567");

chunk3은 malloc(0x25)으로, 헤더 값까지 0x35 크기의 공간이 필요하다. 이때, chunk는 16byte 정렬된 크기로 할당된다. 그러면 0x30으로 담을 수 없으니, 0x40의 크기를 할당할 것이라고 생각할 수 있다. 하지만 위 사진에서 size가 0x30인 것을 확인할 수 있다.

색 별로 다른 chunk이다. 아래 chunk의 prev_size 필드가 덮여 데이터를 담고 있다. allocated chunk인 경우, 인접한 뒤 chunk에서 prev_size 부분까지 데이터를 담아 사용한다.

free(chunk3);

chunk3 해제 시, 0x30 크기인 chunk를 담는 fastbin[1]으로 잘 들어갔다.

free(chunk4);

chunk4는 malloc(0x30)이다. 정상적으로 잘 free되었다.

free(chunk5);

chunk5는 malloc(0x80)을 했다. 헤더 정보의 크기인 0x10을 더하면 0x90의 크기를 가진다. 0x90은 144byte이고, 64bit 기준으로 32~128byte를 fastbin으로 관리한다고 했으므로, fastbin에 들어가지 않는다. heapinfo 시 size가 0이었던 unsorted bin이 0x90으로 바뀐 것을 확인할 수 있고, 해제된 chunk의 주소 값이 써져 있다. 또한 parseheap으로 해당 청크의 fd와 bk가 어떠한 특정 주소 값으로 동일하게 들어간 것도 볼 수 있다.

free(chunk6);

chunk6은 malloc(0x88)로 할당하였고, chunk의 크기는 0x90이다. 이 또한 free했을 때, fastbin에 들어갈 크기가 아니며, unsorted bin에 size가 증가한 것을 볼 수 있다. 이는 chunk와 chunk가 인접했기 때문에 병합과정이 일어난 것이다. 그에 반해 fastbin은 인접한 chunk라고 하더라도, 앞서 본 것 처럼 병합과정이 일어나지 않는다.

free(chunk7);

모든 chunk가 free되었다. 마지막 free여서 인가(?)

unsorted bin

앞서 fastbin을 보면서 마지막에 살짝 확인했던 bin이다. fastbin과는 다르게 FIFO(선입선출) 방식을 사용하고 1개의 bin만을 사용한다. Freed chunk구조에서 fd와 bk를 사용하여 이중 연결리스트로 관리한다.

unsorted bin은 fastbin에 들어가지 않는 chunk가 small bin과 large bin에 들어가기 전, 할당과 해제의 속도를 높이기 위해 chunk를 unsorted bin에 잠시 저장한다. chunk를 할당할 때 fastbin에 맞는 크기가 없다면, unsorted bin을 확인하여 재할당되거나 원래의 bin으로 돌아간다. unsorted bin에 들어간 chunk는 NON_MAIN_ARENA 플래그가 true가 되지 않는다.

unsorted bin으로 free되는 과정을 예제 코드로 확인해보자.

//Name : unsortedbin.c
//Compiler : gcc -o unsortedbin unsortedbin.c -no-pie -fno-stack-protector
#include <stdio.h>
#include <stdlib.h>
int main()
{
        char* chunk1 = malloc(0x80);
        char* chunk2 = malloc(0x10);
        char* chunk3 = malloc(0x80);
        char* chunk4 = malloc(0x10);
        char* chunk5 = malloc(0x80);
        char* chunk6 = malloc(0x10);
        free(chunk1);
        free(chunk3);
        free(chunk5);
				char* chunk7 = malloc(0x500);
        free(chunk7);
				return 0;
}

위 사진은 예제 코드에서 모든 chunk가 할당된 상태의 메모리 구조이다. 먼저, unsorted bin으로 넣을 chunk는 fastbin의 크기 범위보다 큰 0x90으로 할당해줬고, 이 0x90 크기의 chunk들이 연속적으로 인접해있으면 해제과정에서 병합이 이뤄지기 때문에 중간중간 fastbin 크기의 chunk를 할당해줬다.

free(chunk1);

chunk1의 해제가 이뤄지면 unsorted bin으로 chunk가 들어간다. 이때, 해제된 청크는 이중 연결리스트로 관리가 된다. fd와 bk를 보면 주소 값이 들어가 있다. 이 값을 확인해보면 main_arena+88 위치의 주소인 것을 알 수 있다. 만약 이 주소를 leak 할 수 있다면, 이를 통해 libc base를 구할 수 있다.

free(chunk3);

chunk3이 해제되면, 역시 unsorted bin에 우선적으로 들어간다. main_arena+88을 기준으로 fd와 bk로 chunk가 연결되어 있는 것을 확인할 수 있다. 만약 여기서 재할당이 이루어지면, 먼저들어왔던 0xa7d000이 할당되게 될 것이다.

free(chunk5);

chunk5가 해제된 메모리 구조이다. 앞선 설명과 같이 unsorted bin에 잘 들어갔다. 현재까지의 bins 상태에서 재할당을 하면서 bins의 변화를 살펴보자.

char* chunk7 = malloc(0x500);

chunk7에 malloc(0x500)을 해줬다. 할당 시 제일 먼저 fast bin 크기가 아니기 때문에 unsorted bin에서 알맞는 chunk를 확인할 것이다. 하지만 unsorted bin의 chunk들의 크기는 0x90이었으므로, malloc(0x500)에 적합하지 않다. 재할당 과정이 unsorted bin에서 이뤄지지 않았기 때문에 해당 chunk들을 크기에 맞는 small bin으로 옮긴다.

free(chunk7);

다시 0x500 크기의 chunk7을 해제해주면, unsorted bin에 들어가지 않았다. 이 과정은 top chunk와 바로 인접했기 때문에 병합과정이 이뤄진 것이다. 만약 그 아래 다른 chunk가 존재했다면, unsorted bin에 들어갔을 것이다.

다음 예제 코드로 small bin과 large bin, 그리고 last_remainder에 대해 알아보자.

//Name : bins.c
//Compiler : gcc -o bins bins.c -no-pie -fno-stack-protector
#include <stdio.h>
#include <stdlib.h>
void main()
{
        char* chunk1 = malloc(1000);
        char* chunk2 = malloc(0x10);
        char* chunk3 = malloc(1024);
        char* chunk4 = malloc(0x10);
        free(chunk1);
        free(chunk3);
        char* chunk5 = malloc(1200);
        char* chunk6 = malloc(0x10);
        free(chunk5);
}

small bin

앞서 unsorted bin에서 재할당되지 못한 경우, chunk의 크기가 fast bin보다 크고 512byte(64bit 운영체제인 경우 1024byte) 보다 미만인 경우에 small bin으로 관리하게 된다. 이 bin 또한 FIFO(선입선출) 방식이고, 크기에 따라 62개의 bin을 가진다.

chunk4까지 할당되고 chunk1과 chunk3을 free한 상태이다. 이 상태에서 1200byte 크기로 malloc을 해주면, unsorted bin에서 해당하는 크기의 chunk가 없으므로, unsorted bin 안의 두개의 chunk는 각자 크기에 해당하는 bin에 들어갈 것이다.

이때 smallbin에 들어간 chunk를 확인해보자.

역시나 fd와 bk를 이용해서 chunk를 관리하고, 크기에 따라 main_arena를 기준으로 관리한다.

large bin

앞서 설명했던 small bin과 같이 FIFO(선입선출) 방식이며, 63개의 bin을 가진다. 512byte(64bit 운영체제인 경우 1024byte) 보다 큰 chunk를 관리한다.

small bin에 있는 사진과 동일하다. 이때 largebin을 들어간 chunk를 확인해보자.

fd와 bk를 이용해서 chunk를 관리한다. 하지만, 그 아래 fd_nextsize와 bk_nextsize의 필드 값이 들어간 것을 확인할 수 있다. 현재의 chunk 크기보다 작은 chunk를 fd_nextsize, 큰 chunk를 bk_nextsize로 설정하여 chunk를 관리한다. 현재는 하나의 chunk가 존재하기 때문에 두 필드의 값이 같다.

last_remainder

chunk6의 할당이 이뤄진 상태의 메모리 구조이다.

fast bin 크기이고, small bin에 있는 chunk를 분리하여 0x18a3000 주소를 가지는 것을 볼 수 있다. 이때 fast bin 만큼 크기를 할당해주고, top chunk와는 인접하지 않아 병합되지 않는다. 이러한 chunk를 last_remainder chunk라고 한다.

자세히 확인해보면 0x20만큼 fastbin으로 분리하고, 0x18a3020부터 다시 chunk를 구성한다. 이때 앞 청크가 사용중이므로, size필드의 PREV_INUSE 플래그가 true가 된다.

tcache bin

💡

glibc 2.26부터 멀티 스레드 환경에서 메모리 할당 속도를 높이기 위해 생겨났다. 기본적인 heap 구조를 먼저 이해하고, 추후에 따로 공부할 계획이다.

Uploaded by N2T