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

List

Table of Contents

exclude	List

Arena

Arena?

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

Main Arena

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

Code Block

language	cpp
title	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들을 관리합니다.

Code Block

language	cpp
title	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에서 다음과 같이 확인할 수 있습니다.

Code Block

title	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" 구조체를 이용해 필요한 정보를 저장합니다.

Code Block

language	cpp
title	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

...

title	Allocated chunk Sample(64 bit)

...

User data

...

Next chunk(Size of chunk)

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

...

이전 Chunk가 해제되면, 이 필드에 이전 Chunk의 크기가 저장됩니다.
이전 Chunk가 할당되면, 이 필드에 이전 Chunk의 사용자 데이터가 저장됩니다.

...

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

Include Page

	00.Notice
	00.Notice

List

Panel

Content Report Table

labels	malloc

Example - Allocated chunk

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

Code Block

language	cpp
title	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

Code Block

title	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의 구조는 다음과 같습니다.

...

title	Free chunk Sample(64 bit)

...

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

...

Free chunk는 연속으로 붙어 있을 수 없습니다.
각 청크를 해제하는 경우 하나의 단일 free chunk로 결합됩니다.
따라서 항상 해제된 청크의 이전 청크를 할당하고 있어서 prev_size는 이전 청크의 사용자 데이터를 저장하고 있습니다.

...

Free chunk의 크기를 저장하며, 필드의 맨 끝 3bit는 flag 정보를 나타냅니다.

...

동일한 Bin의 다음 Free Chunk address를 저장됩니다.

...

동일한 Bin의 이전 Free Chunk address를 저장됩니다.

Example - Free chunk

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

Code Block

language	cpp
title	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 영역의 주소가 저장되어 있습니다.

Code Block

title	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)의 크기에 따라 다음과 같이 구분됩니다.

...

title	Chunk의 크기에 따른 분류

...

Bin

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

...

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로 병합되지 않습니다.

Code Block

title	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가 등록되는 것을 확인할 수 있습니다.

Code Block

language	cpp
title	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영역이 추가되지 않았습니다.

Code Block

title	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을 확인 할 수 있습니다.

Code Block

language	cpp
title	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영역의 주소 값이 저장되었습니다.

Code Block

title	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

...

Panel

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

...

Page tree

Versions Compared

Old Version 4

New Version Current

Key

List

Arena

Arena?

Main Arena

Chunk

Chunk type

struct malloc_chunk

Allocated chunk

List

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

Page tree

Page History

Versions Compared

Old Version 4

New Version Current

Key

List

Arena

Arena?

Main Arena

Chunk

Chunk type

struct malloc_chunk

Allocated chunk

List

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