실습 환경 : Ubuntu 16.04

실습코드

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int main() {
    char* a=(char*)malloc(0x20);
    char* a2=(char*)malloc(0x100); // small chunk
    char* b=(char*)malloc(0x14);
    char* b2=(char*)malloc(0x111); // small chunk
    char* c=(char*)malloc(0x30);
    char* c2=(char*)malloc(0x122); // small chunk
    char* d=(char*)malloc(0x24);
    char* e=(char*)malloc(0x22);

    free(b); // insert fastbin
    free(d); // insert fastbin

    free(a2); // insert unsorted bin
    free(b2); // insert unsorted bin
    free(c2); // insert unsorted bin

    char* f=(char*)malloc(0x100);
    char* g=(char*)malloc(0x122);   
    free(g);

    return 0;
}

Untitled

현재 free(b), free(d)가 호출되었으므로 fastbin[0]과 fastbin[1]에는 해제된 b, d가 들어가 있습니다. 이 두 청크를 제외하곤 해제된 청크가 없으므로 unsorted bin에는 아무것도 없는걸 확인할 수 있습니다.

Untitled

free(a2)를 호출한 후 상황입니다. unsorted bin에 a2청크가 있는걸 확인할 수 있습니다. 여기서 추가로 free(b2)가 호출된다면 b2청크도 unsorted bin에 추가될 것입니다.

Untitled

free(b2), free(c2)를 호출한 후 상황입니다. unsorted bin에 a2, b2, c2가 이중연결리스트로 연결되어 있는 것을 확인할 수 있습니다. unsorted bin은 FIFO구조 이므로 이 후 malloc 요청이 들어오면, unsorted bin을 뒤져 적절한 사이즈가 존재하는지를 제일 오른쪽부터 탐색할 것입니다.

만일 들어온 요청 사이즈가 0x100이면 헤더 포함 0x110이므로 한번에 찾게 되고, 바로 재할당을 해줍니다. 하지만 요청 사이즈가 0x120이면 헤더포함 0x130이므로 제일 왼쪽에 있는 청크를 할당할 것입니다.

이를 위해 우측부터 검색을 시작하고, 0x110 탈락 → 0x120 탈락 후 마지막 청크 사이즈가 딱 맞으므로 이를 재할당 할 것입니다. 따라서 앞서 검색을 진행했던 두 개의 청크는 즉시 small bin으로 들어갈 것입니다. 직접 확인해보겠습니다.