Excuse the ads! We need some help to keep our site up.

List

Arena

Arena?

malloc()에서 메모리 영역과 메모리 관리 부분을 arena라고 합니다.
프로세스에 할당된 Heap 영역(non-mmapped )입니다.

Main Arena

main_arena는 Malloc.c 에서 "struct malloc_state" 구조체를 사용하는 변수 입니다.

static struct malloc_state main_arena =

static struct malloc_state main_arena =
{
  .mutex = _LIBC_LOCK_INITIALIZER,
  .next = &main_arena,
  .attached_threads = 1
};

malloc_state 구조체의 형태는 다음과 같습니다.
- 해당 구조체를 이용해 Arena의 세부 정보를 보관합니다.
- 해당 정보를 이용해 할당된 chunk들을 관리합니다.

struct malloc_state

struct malloc_state
{
  /* Serialize access.  */
  mutex_t mutex;

  /* Flags (formerly in max_fast).  */
  int flags;

  /* Fastbins */
  mfastbinptr fastbinsY[NFASTBINS];

  /* Base of the topmost chunk -- not otherwise kept in a bin */
  mchunkptr top;

  /* The remainder from the most recent split of a small request */
  mchunkptr last_remainder;

  /* Normal bins packed as described above */
  mchunkptr bins[NBINS * 2 - 2];

  /* Bitmap of bins */
  unsigned int binmap[BINMAPSIZE];

  /* Linked list */
  struct malloc_state *next;

  /* Linked list for free arenas.  Access to this field is serialized
     by free_list_lock in arena.c.  */
  struct malloc_state *next_free;

  /* Number of threads attached to this arena.  0 if the arena is on
     the free list.  Access to this field is serialized by
     free_list_lock in arena.c.  */
  INTERNAL_SIZE_T attached_threads;

  /* Memory allocated from the system in this arena.  */
  INTERNAL_SIZE_T system_mem;
  INTERNAL_SIZE_T max_system_mem;
};

이러한 정보들은 GDB에서 다음과 같이 확인할 수 있습니다.

p main_arena

gdb-peda$ p main_arena 
$1 = {
  mutex = 0x0, 
  flags = 0x1, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x602070, 
  last_remainder = 0x0, 
  bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37d8 <main_arena+120>, 0x7ffff7dd37d8 <main_arena+120>, 0x7ffff7dd37e8 <main_arena+136>, 0x7ffff7dd37e8 <main_arena+136>, 0x7ffff7dd37f8 <main_arena+152>, 0x7ffff7dd37f8 <main_arena+152>, 0x7ffff7dd3808 <main_arena+168>, 0x7ffff7dd3808 <main_arena+168>, 
    0x7ffff7dd3818 <main_arena+184>, 0x7ffff7dd3818 <main_arena+184>, 0x7ffff7dd3828 <main_arena+200>, 0x7ffff7dd3828 <main_arena+200>, 0x7ffff7dd3838 <main_arena+216>, 0x7ffff7dd3838 <main_arena+216>, 0x7ffff7dd3848 <main_arena+232>, 0x7ffff7dd3848 <main_arena+232>, 0x7ffff7dd3858 <main_arena+248>, 0x7ffff7dd3858 <main_arena+248>, 0x7ffff7dd3868 <main_arena+264>, 0x7ffff7dd3868 <main_arena+264>, 
    0x7ffff7dd3878 <main_arena+280>, 0x7ffff7dd3878 <main_arena+280>, 0x7ffff7dd3888 <main_arena+296>, 0x7ffff7dd3888 <main_arena+296>, 0x7ffff7dd3898 <main_arena+312>, 0x7ffff7dd3898 <main_arena+312>, 0x7ffff7dd38a8 <main_arena+328>, 0x7ffff7dd38a8 <main_arena+328>, 0x7ffff7dd38b8 <main_arena+344>, 0x7ffff7dd38b8 <main_arena+344>, 0x7ffff7dd38c8 <main_arena+360>, 0x7ffff7dd38c8 <main_arena+360>, 
    0x7ffff7dd38d8 <main_arena+376>, 0x7ffff7dd38d8 <main_arena+376>, 0x7ffff7dd38e8 <main_arena+392>, 0x7ffff7dd38e8 <main_arena+392>, 0x7ffff7dd38f8 <main_arena+408>, 0x7ffff7dd38f8 <main_arena+408>, 0x7ffff7dd3908 <main_arena+424>, 0x7ffff7dd3908 <main_arena+424>, 0x7ffff7dd3918 <main_arena+440>, 0x7ffff7dd3918 <main_arena+440>, 0x7ffff7dd3928 <main_arena+456>, 0x7ffff7dd3928 <main_arena+456>, 
    0x7ffff7dd3938 <main_arena+472>, 0x7ffff7dd3938 <main_arena+472>, 0x7ffff7dd3948 <main_arena+488>, 0x7ffff7dd3948 <main_arena+488>, 0x7ffff7dd3958 <main_arena+504>, 0x7ffff7dd3958 <main_arena+504>, 0x7ffff7dd3968 <main_arena+520>, 0x7ffff7dd3968 <main_arena+520>, 0x7ffff7dd3978 <main_arena+536>, 0x7ffff7dd3978 <main_arena+536>, 0x7ffff7dd3988 <main_arena+552>, 0x7ffff7dd3988 <main_arena+552>, 
    0x7ffff7dd3998 <main_arena+568>, 0x7ffff7dd3998 <main_arena+568>, 0x7ffff7dd39a8 <main_arena+584>, 0x7ffff7dd39a8 <main_arena+584>, 0x7ffff7dd39b8 <main_arena+600>, 0x7ffff7dd39b8 <main_arena+600>, 0x7ffff7dd39c8 <main_arena+616>, 0x7ffff7dd39c8 <main_arena+616>, 0x7ffff7dd39d8 <main_arena+632>, 0x7ffff7dd39d8 <main_arena+632>, 0x7ffff7dd39e8 <main_arena+648>, 0x7ffff7dd39e8 <main_arena+648>, 
    0x7ffff7dd39f8 <main_arena+664>, 0x7ffff7dd39f8 <main_arena+664>, 0x7ffff7dd3a08 <main_arena+680>, 0x7ffff7dd3a08 <main_arena+680>, 0x7ffff7dd3a18 <main_arena+696>, 0x7ffff7dd3a18 <main_arena+696>, 0x7ffff7dd3a28 <main_arena+712>, 0x7ffff7dd3a28 <main_arena+712>, 0x7ffff7dd3a38 <main_arena+728>, 0x7ffff7dd3a38 <main_arena+728>, 0x7ffff7dd3a48 <main_arena+744>, 0x7ffff7dd3a48 <main_arena+744>, 
    0x7ffff7dd3a58 <main_arena+760>, 0x7ffff7dd3a58 <main_arena+760>, 0x7ffff7dd3a68 <main_arena+776>, 0x7ffff7dd3a68 <main_arena+776>, 0x7ffff7dd3a78 <main_arena+792>, 0x7ffff7dd3a78 <main_arena+792>, 0x7ffff7dd3a88 <main_arena+808>, 0x7ffff7dd3a88 <main_arena+808>, 0x7ffff7dd3a98 <main_arena+824>, 0x7ffff7dd3a98 <main_arena+824>, 0x7ffff7dd3aa8 <main_arena+840>, 0x7ffff7dd3aa8 <main_arena+840>, 
    0x7ffff7dd3ab8 <main_arena+856>, 0x7ffff7dd3ab8 <main_arena+856>, 0x7ffff7dd3ac8 <main_arena+872>, 0x7ffff7dd3ac8 <main_arena+872>, 0x7ffff7dd3ad8 <main_arena+888>, 0x7ffff7dd3ad8 <main_arena+888>, 0x7ffff7dd3ae8 <main_arena+904>, 0x7ffff7dd3ae8 <main_arena+904>, 0x7ffff7dd3af8 <main_arena+920>, 0x7ffff7dd3af8 <main_arena+920>, 0x7ffff7dd3b08 <main_arena+936>, 0x7ffff7dd3b08 <main_arena+936>, 
    0x7ffff7dd3b18 <main_arena+952>, 0x7ffff7dd3b18 <main_arena+952>, 0x7ffff7dd3b28 <main_arena+968>, 0x7ffff7dd3b28 <main_arena+968>, 0x7ffff7dd3b38 <main_arena+984>, 0x7ffff7dd3b38 <main_arena+984>, 0x7ffff7dd3b48 <main_arena+1000>, 0x7ffff7dd3b48 <main_arena+1000>, 0x7ffff7dd3b58 <main_arena+1016>, 0x7ffff7dd3b58 <main_arena+1016>, 0x7ffff7dd3b68 <main_arena+1032>, 0x7ffff7dd3b68 <main_arena+1032>, 
    0x7ffff7dd3b78 <main_arena+1048>, 0x7ffff7dd3b78 <main_arena+1048>, 0x7ffff7dd3b88 <main_arena+1064>, 0x7ffff7dd3b88 <main_arena+1064>, 0x7ffff7dd3b98 <main_arena+1080>, 0x7ffff7dd3b98 <main_arena+1080>, 0x7ffff7dd3ba8 <main_arena+1096>, 0x7ffff7dd3ba8 <main_arena+1096>, 0x7ffff7dd3bb8 <main_arena+1112>, 0x7ffff7dd3bb8 <main_arena+1112>, 0x7ffff7dd3bc8 <main_arena+1128>, 0x7ffff7dd3bc8 <main_arena+1128>, 
    0x7ffff7dd3bd8 <main_arena+1144>, 0x7ffff7dd3bd8 <main_arena+1144>, 0x7ffff7dd3be8 <main_arena+1160>, 0x7ffff7dd3be8 <main_arena+1160>, 0x7ffff7dd3bf8 <main_arena+1176>, 0x7ffff7dd3bf8 <main_arena+1176>, 0x7ffff7dd3c08 <main_arena+1192>, 0x7ffff7dd3c08 <main_arena+1192>, 0x7ffff7dd3c18 <main_arena+1208>, 0x7ffff7dd3c18 <main_arena+1208>, 0x7ffff7dd3c28 <main_arena+1224>, 0x7ffff7dd3c28 <main_arena+1224>, 
    0x7ffff7dd3c38 <main_arena+1240>, 0x7ffff7dd3c38 <main_arena+1240>, 0x7ffff7dd3c48 <main_arena+1256>, 0x7ffff7dd3c48 <main_arena+1256>, 0x7ffff7dd3c58 <main_arena+1272>, 0x7ffff7dd3c58 <main_arena+1272>, 0x7ffff7dd3c68 <main_arena+1288>, 0x7ffff7dd3c68 <main_arena+1288>, 0x7ffff7dd3c78 <main_arena+1304>, 0x7ffff7dd3c78 <main_arena+1304>, 0x7ffff7dd3c88 <main_arena+1320>, 0x7ffff7dd3c88 <main_arena+1320>, 
    0x7ffff7dd3c98 <main_arena+1336>, 0x7ffff7dd3c98 <main_arena+1336>, 0x7ffff7dd3ca8 <main_arena+1352>, 0x7ffff7dd3ca8 <main_arena+1352>, 0x7ffff7dd3cb8 <main_arena+1368>, 0x7ffff7dd3cb8 <main_arena+1368>, 0x7ffff7dd3cc8 <main_arena+1384>, 0x7ffff7dd3cc8 <main_arena+1384>, 0x7ffff7dd3cd8 <main_arena+1400>, 0x7ffff7dd3cd8 <main_arena+1400>, 0x7ffff7dd3ce8 <main_arena+1416>, 0x7ffff7dd3ce8 <main_arena+1416>, 
    0x7ffff7dd3cf8 <main_arena+1432>, 0x7ffff7dd3cf8 <main_arena+1432>, 0x7ffff7dd3d08 <main_arena+1448>, 0x7ffff7dd3d08 <main_arena+1448>, 0x7ffff7dd3d18 <main_arena+1464>, 0x7ffff7dd3d18 <main_arena+1464>, 0x7ffff7dd3d28 <main_arena+1480>, 0x7ffff7dd3d28 <main_arena+1480>, 0x7ffff7dd3d38 <main_arena+1496>, 0x7ffff7dd3d38 <main_arena+1496>, 0x7ffff7dd3d48 <main_arena+1512>, 0x7ffff7dd3d48 <main_arena+1512>, 
    0x7ffff7dd3d58 <main_arena+1528>, 0x7ffff7dd3d58 <main_arena+1528>, 0x7ffff7dd3d68 <main_arena+1544>, 0x7ffff7dd3d68 <main_arena+1544>, 0x7ffff7dd3d78 <main_arena+1560>, 0x7ffff7dd3d78 <main_arena+1560>, 0x7ffff7dd3d88 <main_arena+1576>, 0x7ffff7dd3d88 <main_arena+1576>, 0x7ffff7dd3d98 <main_arena+1592>, 0x7ffff7dd3d98 <main_arena+1592>, 0x7ffff7dd3da8 <main_arena+1608>, 0x7ffff7dd3da8 <main_arena+1608>, 
    0x7ffff7dd3db8 <main_arena+1624>, 0x7ffff7dd3db8 <main_arena+1624>, 0x7ffff7dd3dc8 <main_arena+1640>, 0x7ffff7dd3dc8 <main_arena+1640>, 0x7ffff7dd3dd8 <main_arena+1656>, 0x7ffff7dd3dd8 <main_arena+1656>, 0x7ffff7dd3de8 <main_arena+1672>, 0x7ffff7dd3de8 <main_arena+1672>...}, 
  binmap = {0x0, 0x0, 0x0, 0x0}, 
  next = 0x7ffff7dd3760 <main_arena>, 
  next_free = 0x0, 
  system_mem = 0x21000, 
  max_system_mem = 0x21000
}
gdb-peda$

Chunk

Chunk type

다음과 같은 Chunk type 이 있습니다.
- Allocated chunk
- Free chunk
- Top chunk
- Last Remainder chunk

struct malloc_chunk

Allocated, Free Chunk는 "malloc_chunk" 구조체를 이용해 필요한 정보를 저장합니다.

struct malloc_chunk

/*
  -----------------------  Chunk representations -----------------------
*/

/*
  This struct declaration is misleading (but accurate and necessary).
  It declares a "view" into memory allowing access to necessary
  fields at known offsets from a given base. See explanation below.
*/

struct malloc_chunk {
  INTERNAL_SIZE_T      prev_size;  /* Size of previous chunk (if free).  */
  INTERNAL_SIZE_T      size;       /* Size in bytes, including overhead. */

  struct malloc_chunk* fd;         /* double links -- used only if free. */
  struct malloc_chunk* bk;

  /* Only used for large blocks: pointer to next larger size.  */
  struct malloc_chunk* fd_nextsize; /* double links -- used only if free. */
  struct malloc_chunk* bk_nextsize;
};

Allocated chunk

Allocated chunk의 구조는 다음과 같습니다.
- Allocated 최소 크기는 다음과 같습니다.
  - 32 Bit: 16 byte
  - 64 Bit: 32 byte

Allocated chunk Sample(64 bit)

prev_size

Size of chunk

A

M

P

User data

Next chunk(Size of chunk)

Allocated chunk는 다음과 같은 정보를 포함합니다.

prev_size	이전 Chunk가 해제되면, 이 필드에 이전 Chunk의 크기가 저장됩니다. 이전 Chunk가 할당되면, 이 필드에 이전 Chunk의 사용자 데이터가 저장됩니다.
size	이 필드는 Allocated chunk의 크기를 저장하며, 필드의 맨 끝 3bit는 flag 정보를 나타냅니다. PREV_INUSE [P] : 이 비트는 이전 청크가 할당되면 설정됩니다. IS_MMAPPED [M] : 이 비트는 현재 청크가 mmap을 통해 할당되면 설정됩니다. NON_MAIN_ARENA [A] : 이 비트는 현재 청크가 thread arena에 위치되면 설정됩니다.

Example - Allocated chunk

다음과 같은 코드를 이용해 Allocated chunk를 확인합니다.

allocated.c

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

void main(){
	char *heap = malloc(8);
	printf("Heap Addr : %p\n",heap);
	free(heap);
}

다음과 같은 방법으로 Allocated chunk의 구조를 확인할 수 있습니다.
- 해당 Chunk 앞에 해제된 Chunk가 없기 때문에 prev_size 영역은 비워져있습니다.
- size는 다음과 같은 값을 더한 값이 저장되어 있습니다.
  - Allocated chunk의 header 정보를 저장하는 공간 - 16byte
  - 사용자가 요청한 Heap 공간의 크기 - 8 byte
  - Next chunk 정보를 저장할 공간 - 8 byte

Check allocated

lazenca0x0@ubuntu:~/Documents/def$ gcc -o allocated allocated.c 
lazenca0x0@ubuntu:~/Documents/def$ gdb ./allocated 
gdb-peda$ disassemble main 
Dump of assembler code for function main:
   0x00000000004005bd <+0>:	push   rbp
   0x00000000004005be <+1>:	mov    rbp,rsp
   0x00000000004005c1 <+4>:	sub    rsp,0x10
   0x00000000004005c5 <+8>:	mov    edi,0x8
   0x00000000004005ca <+13>:	call   0x4004c0 <malloc@plt>
   0x00000000004005cf <+18>:	mov    QWORD PTR [rbp-0x8],rax
   0x00000000004005d3 <+22>:	mov    rax,QWORD PTR [rbp-0x8]
   0x00000000004005d7 <+26>:	mov    rsi,rax
   0x00000000004005da <+29>:	mov    edi,0x400684
   0x00000000004005df <+34>:	mov    eax,0x0
   0x00000000004005e4 <+39>:	call   0x400490 <printf@plt>
   0x00000000004005e9 <+44>:	mov    rax,QWORD PTR [rbp-0x8]
   0x00000000004005ed <+48>:	mov    rdi,rax
   0x00000000004005f0 <+51>:	call   0x400480 <free@plt>
   0x00000000004005f5 <+56>:	leave  
   0x00000000004005f6 <+57>:	ret    
End of assembler dump.
gdb-peda$ b *0x00000000004005cf
Breakpoint 1 at 0x4005cf
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/allocated 

Breakpoint 1, 0x00000000004005cf in main ()
gdb-peda$ heap
heapbase : 0x602000
gdb-peda$ x/10gx 0x602000
0x602000:	0x0000000000000000	0x0000000000000021
0x602010:	0x0000000000000000	0x0000000000000000
0x602020:	0x0000000000000000	0x0000000000020fe1
0x602030:	0x0000000000000000	0x0000000000000000
0x602040:	0x0000000000000000	0x0000000000000000
gdb-peda$

Free chunk

Free chunk의 구조는 다음과 같습니다.

Free chunk Sample(64 bit)

Chunk

Chunk size

A

M

P

fd

bk

Unused Space

Next chunk(Size of chunk)

Free chunk는 다음과 같은 정보를 포함합니다.

prev_size	Free chunk는 연속으로 붙어 있을 수 없습니다. 각 청크를 해제하는 경우 하나의 단일 free chunk로 결합됩니다. 따라서 항상 해제된 청크의 이전 청크를 할당하고 있어서 prev_size는 이전 청크의 사용자 데이터를 저장하고 있습니다.
size	Free chunk의 크기를 저장하며, 필드의 맨 끝 3bit는 flag 정보를 나타냅니다.
fd(Forward pointer)	동일한 Bin의 다음 Free Chunk address를 저장됩니다.
bk(Backward pointer)	동일한 Bin의 이전 Free Chunk address를 저장됩니다.

Example - Free chunk

다음과 같은 코드를 이용해 Free chunk를 확인합니다.

freechunk.c

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

void main(){
        char *heap1 = malloc(128);
        char *tmp2 = malloc(8);
        char *heap2 = malloc(128);
        char *tmp3 = malloc(8);
        char *heap3 = malloc(128);
        char *tmp1 = malloc(8);

        printf("Free chunk : %p\n",heap2);
        free(heap1);
        free(heap2);
        free(heap3);
        getchar();
}

다음과 같은 방법으로 Free chunk의 구조를 확인할 수 있습니다.
- Chunk size는 다음과 같은 값을 더한 값이 저장되어 있습니다.
- fd 영역에 해제된 heap1 영역의 주소가 저장되어 있습니다.
- bk 영역에 해제된 heap2 영역의 주소가 저장되어 있습니다.

Check Free chunk

lazenca0x0@ubuntu:~/Documents/def$ gcc -o freechunk freechunk.c 
lazenca0x0@ubuntu:~/Documents/def$ gdb ./freechunk
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/unsorted 
Free chunk : 0x6020c0
^C
Program received signal SIGINT, Interrupt.
gdb-peda$ x/4gx 0x6020c0 - 0x10
0x6020b0:	0x0000000000000000	0x0000000000000091
0x6020c0:	0x0000000000602000	0x0000000000602160
gdb-peda$

Top chunk

Top chunk는 Arena의 가장 상위 영역에 있는 Chunk입니다.
Top chunk는 bin에 포함되지 않습니다.
Top chunk는 PREV_INUSE 플래그가 설정됩니다.
Top chunk의 크기가 사용자가 요청한 크기보다 큰 경우 top chunk는 2개로 분리됩니다.
- User chunk(사용자가 요청한 크기)
- Remainder chunk(나머지 크기)
Remainder chunk는 새로운 Top chunk가 됩니다.
Top chunk의 크기가 사용자가 요청한 크기보다 작은 경우 syscall을 사용하여 Top chunk의 크기를 증가 시킵니다.
- sbrk(main arena)
- mmap(thread arena)

Fast chunk, Small chunk, Large chunk

Allocated chunk는 Chunk size(+User data)의 크기에 따라 다음과 같이 구분됩니다.

Chunk의 크기에 따른 분류

Chunk	size of Chunk (32bit)	size of Chunk (64bit)
Fast chunk	16 ~ 64 byte	32 ~ 128 byte
Small chunk	size of User data < 512 byte
Large chunk	size of User data >= 512 byte

Bin

Bin의 종류는 다음과 같습니다.
- Fast bin
- Small bin
- Large bin
- Unsorted bin
각 Bins의 속성은 다음과 같습니다.

Bins	Fast bin	Small bin	Large bin	Unsorted bin
Chunk type	Fast chunk	Small chunk	Large chunk	Small, Large chunk
the size of chunk	16 ~ 80 byte	512 byte 이하	512 byte이상	제한 없음 (Free chunk만 등록 가능)
Bin의 갯수	10	62	63	1
Free chunk 관리	Free chunk가 서로 인접해 있어도 하나의 단일 Free chunk로 병합되지 않습니다.	2개의 Free chunk는 서로 인접해 있을 수 없습니다. Free chunk가 서로 인접해 있으면 하나의 단일 Free chunk로 병합됩니다.		-

malloc_state

Bin 정보는 "malloc_state" 구조체에서 관리됩니다.
- FastbinsY : "Fast bin"을 관리합니다.
- Bins : "Unsorted bin", "Small bin", "Large bin"을 관리 합니다.
  - 총 126개의 bin을 관리 합니다.
Bins의 구성은 다음과 같습니다.
- Index 1 : Unsorted bin
- Index 2 ~ 63 : Small bin
- Index 64 ~ 126 : Large bin

Fast bin

Fast bin은 다음과 같습니다.
- 해당 bin은 LIFO방식을 사용합니다.
- 해당 bin은 10개의 bin을 사용합니다.
- 해당 bin은 해제된 Fast chunk를 보관합니다.
- 해당 bin은 속도 향상을 위해 single-linked list로 구성됩니다.
Bin의 구성
- Fast bin이 처리하는 메모리의 최대 크기 "global_max_fast"에 의해 결정됩니다.
- 32bit: 최소 크기 16 byte 부터 24, 32, 40, 48, 56, 64 byte 까지 포함합니다.
- 64bit: 최소 크기 32 byte 부터 48, 64, 80, 96, 112, 128 byte 까지 포함합니다.
Free chunk
- 해당 bind의 경우 Free chunk가 서로 인접해 있어도 하나의 Free chunk로 병합되지 않습니다.

64bit - global_max_fast

gdb-peda$ p global_max_fast
$2 = 0x80
gdb-peda$

Small bin

Small bin은 다음과 같습니다.
- 해당 bin은 FIFO방식을 사용합니다.
- 해당 bin은 62개의 bin을 사용합니다.
- 해당 bin은 해제된 Small chunk를 보관합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
Bin 구성
- 해당 bin은 512바이트 미만의 크기를 가지는 Chunk를 위한 Bin입니다.
- 최소 크기 16 byte 부터 24,32,48, ... 504byte 까지 총 62개의 bin으로 구성됩니다.
Free chunk
- 해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없습니다.
- 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합됩니다.

Large bin

Large bin은 다음과 같습니다.
- 해당 bin은 63개의 bin을 사용합니다.
- 해당 bin은 해제된 Large chunk를 보관합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
Bin의 구성
- 해당 Bin은 512 byte 이상의 크기를 가지는 Chunk를 위한 Bin입니다.
- Small Bin 처럼 동일한 크기의 chunk만을 포함하지 않습니다.
- 해당 index가 나타내는 크기 보다 작은 크기의 chunk들도 모두 포함됩니다.
- 예를 들어 4kb를 위한 bin 이 있다면 4096 byte의 chunk만을 포함하는 것이 아니라, 4088,4000,3968 등의 크기를 가지는 chunk들도 포함합니다.
  - 단지 이들의 할당의 효율성을 높이기 위해 해당 bin내에서 크기 별로 정렬됩니다.
  - 이 때 fd_nextsize와 bk_nextsize 필드가 이용됩니다.
Free Chunk
- 해당 bin에는 2개의 Free chunk가 서로 인접해 있을 수 없습니다.
- 해당 bin에 2개의 Free chunk가 서로 인접해 있을 경우 하나의 Free chunk로 병합됩니다.
128KB 이상의 큰 메모리
- 해당 크기의 메모리 영역은 mmap() 시스템 콜을 이용해 별도의 메모리 영역을 할당 후 Chunk를 생성합니다.
- 해당 크기의 Chunk들은 Bin에 속하지 않습니다.
- 해당 Chunk들은 IS_MMAPPED 플래그가 설정됩니다.
- 해당 영역이 Free 될 경우 munmap()을 호출해 해당 메모리 영역을 해지 합니다.

Unsorted bin

Unsorted bin은 다음과 같습니다.
- 해당 bin은 1개의 bin만 사용합니다.
- 해당 bin은 doubly-linked list로 구성됩니다.
- 해당 bin은 해제된 Small ,Large chunk를 보관합니다.
- 해당 bin을 이용해 적절한 bin을 찾는 시간이 적기 때문에 할당과 해제의 처리속도가 빠릅니다.
- 해당 bin은 Chunk 크기에 대한 제한이 없기 때문에 다양한 크기의 청크가 해당 Bin에 저장될 수 있습니다.
free()된 chunk는 unsorted bin에 보관되며, 메모리 할당 시 동일한 크기의 영역을 다시 요청하는 경우 해당 영역을 재사용합니다.
- 해당 Bin은 FIFO 방식을 사용합니다.
- 검색된 Chunk는 바로 재할당 되거나 아니면 원래의 Bin으로 돌아가게 됩니다.
- 즉, 해제한 Chunk를 재사용하기 위해서 Chunk 해제 후 곧 바로 동일한 크기의 Chunk를 생성해야 합니다.

Bins - Example

Fast bin

다음 소스코드를 이용해 fastbin에 해제된 chunk가 등록되는 것을 확인할 수 있습니다.

fastbin.c

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

void main(){
        char *heap = malloc(16);
        char *heap1 = malloc(32);
        char *heap2 = malloc(48);
        char *heap3 = malloc(64);
        char *heap4 = malloc(80);
        char *heap5 = malloc(96);
        char *heap6 = malloc(112);

        printf("Heap Addr : %p\n",heap);
        printf("Heap Addr : %p\n",heap1);
        printf("Heap Addr : %p\n",heap2);
        printf("Heap Addr : %p\n",heap3);
        printf("Heap Addr : %p\n",heap4);
        printf("Heap Addr : %p\n",heap5);
        printf("Heap Addr : %p\n",heap6);

   	 	free(heap);
   	 	free(heap1);
		free(heap2);
		free(heap3);
		free(heap4);
		free(heap5);
		free(heap6);
	
		getchar();
}

다음과 같은 방법으로 Fast bin을 확인할 수 있습니다.
- main_arena을 이용해 fastbinsY의 정보를 확인 할 수 있습니다.
- 해제된 모든 Heap 영역이 fastbinsY에 추가되었습니다.
- Unsorted bin 영역에 해제된 Heap영역이 추가되지 않았습니다.

Check fastbin(64bit)

lazenca0x0@ubuntu:~/Documents/def$ gcc -o fastbin fastbin.c
lazenca0x0@ubuntu:~/Documents/def$ gdb ./fastbin 
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/fastbin 
Heap Addr : 0x602010
Heap Addr : 0x602030
Heap Addr : 0x602060
Heap Addr : 0x6020a0
Heap Addr : 0x6020f0
Heap Addr : 0x602150
Heap Addr : 0x6021c0
^C
Program received signal SIGINT, Interrupt.

gdb-peda$ p main_arena 
$1 = {
  mutex = 0x0, 
  flags = 0x0, 
  fastbinsY = {0x602000, 0x602020, 0x602050, 0x602090, 0x6020e0, 0x602140, 0x6021b0, 0x0, 0x0, 0x0}, 
  top = 0x602230, 
  last_remainder = 0x0, 
  bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>,
...

Unsorted bin

다음과 같은 소스 코드를 이용해 Unsorted bin을 확인 할 수 있습니다.

unsorted.c

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

void main(){
        char *heap = malloc(8);
        char *heap2 = malloc(128);
        char *heap3 = malloc(8);

        free(heap2);
        getchar();
}

다음과 같은 방법으로 Unsort bin을 확인할 수 있습니다.
- free()가 호출 후에 bins의 1번째 Index 영역(0x7ffff7dd37c8,0x7ffff7dd37d0)에 해제된 heap영역의 주소 값이 저장되었습니다.

Check unsorted bin

lazenca0x0@ubuntu:~/Documents/def$ gcc -o unsorted unsorted.c 
lazenca0x0@ubuntu:~/Documents/def$ gdb ./unsorted 
gdb-peda$ disassemble main
Dump of assembler code for function main:
   0x00000000004005bd <+0>:	push   rbp
   0x00000000004005be <+1>:	mov    rbp,rsp
   0x00000000004005c1 <+4>:	sub    rsp,0x20
   0x00000000004005c5 <+8>:	mov    edi,0x8
   0x00000000004005ca <+13>:	call   0x4004c0 <malloc@plt>
   0x00000000004005cf <+18>:	mov    QWORD PTR [rbp-0x18],rax
   0x00000000004005d3 <+22>:	mov    edi,0x80
   0x00000000004005d8 <+27>:	call   0x4004c0 <malloc@plt>
   0x00000000004005dd <+32>:	mov    QWORD PTR [rbp-0x10],rax
   0x00000000004005e1 <+36>:	mov    edi,0x8
   0x00000000004005e6 <+41>:	call   0x4004c0 <malloc@plt>
   0x00000000004005eb <+46>:	mov    QWORD PTR [rbp-0x8],rax
   0x00000000004005ef <+50>:	mov    rax,QWORD PTR [rbp-0x10]
   0x00000000004005f3 <+54>:	mov    rdi,rax
   0x00000000004005f6 <+57>:	call   0x400480 <free@plt>
   0x00000000004005fb <+62>:	call   0x4004a0 <getchar@plt>
   0x0000000000400600 <+67>:	leave  
   0x0000000000400601 <+68>:	ret    
End of assembler dump.

gdb-peda$ b *0x00000000004005f6
Breakpoint 1 at 0x4005f6
gdb-peda$ r
Starting program: /home/lazenca0x0/Documents/def/unsorted 

Breakpoint 1, 0x00000000004005f6 in main ()
gdb-peda$ p main_arena 
$2 = {
  mutex = 0x0, 
  flags = 0x1, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x6020d0, 
  last_remainder = 0x0, 
  bins = {0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37b8 <main_arena+88>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8 

...
}
gdb-peda$ ni


0x00000000004005fb in main ()
gdb-peda$ p main_arena 
$3 = {
  mutex = 0x0, 
  flags = 0x1, 
  fastbinsY = {0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0}, 
  top = 0x6020d0, 
  last_remainder = 0x0, 
  bins = {0x602020, 0x602020, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37c8 <main_arena+104>, 0x7ffff7dd37d8 

...
}

Related site

Excuse the ads! We need some help to keep our site up.

Page tree

Malloc - glibc(ptmalloc2)

List

Arena

Arena?

Main Arena

Chunk

Chunk type

struct malloc_chunk

Allocated chunk

Example - Allocated chunk

Free chunk

Example - Free chunk

Top chunk

Fast chunk, Small chunk, Large chunk

Bin

malloc_state

Fast bin

Small bin

Large bin

Unsorted bin

Bins - Example

Fast bin

Unsorted bin

Related site