(glibc) malloc - 4

malloc sequence

1. 너무 큰 heap memory 할당을 요청하는 경우, mmap()을 사용해 아예 다른 곳에 공간을 할당한다. * mmap’ing threshold 값은 따로 설정되지 않은 경우 dynamic하게 결정된다. 보통은 대략 0x20800 이상일 때.
2. 요청에 맞는 fastbin에 chunk가 있는 경우 반환한다.
3. 요청에 맞는 smallbin에 chunk가 있는 경우 반환한다.
4. large bin size request일 경우, 모든 fastbins’s chunks를 (적당히 합치면서) unsorted bin으로 옮긴다. if (have\_fastchunks (av)) malloc_consolidate (av);
5. unsorted bin에 있는 chunk들을 (적당히 합치면서) small/large bins로 옮긴다.적당한 사이즈의 chunk가 있는 경우 반환한다. * 여기가 small/large bins에 chunk를 추가하는 유일한 지점이다.
6. 요청이 큰 경우, large bin을 탐색한다.
7. 필요하다면 top을 증가시키고(brk()), top chunk를 잘라 반환한다.

4, 5 번에서 fastbin chunk는 결국 small/large bins로 옮겨지게 되는데, 이 때 chunk가 합쳐지지 않을 경우 fastbin size 그대로 smallbins로 옮겨진다. 즉, smallbins는 fastbin size도 포함한다.

small chunk는 unsorted_bin으로 들어갔다가, 다음 malloc() 때 small bins로 옮겨진다. size = 0x91, 0xa1일 때 smallbins 로 옮겨진 모습.

0x7ffff7dd3838 <main\_arena+216>:    0x00007ffff7dd3828      0x00007ffff7dd3828
0x7ffff7dd3848 <main\_arena+232>:    0x0000000000602510      0x0000000000602510
0x7ffff7dd3858 <main\_arena+248>:    0x00000000006025e0      0x00000000006025e0

free’d fastbin chunk는 대기하고 있다가 large request가 들어올 경우 small / large bins로 옮겨진다. size = 0x21, 0x31일 때 small bins 로 옮겨진 모습. ( main_arena+88 : av->top )

0x7ffff7dd37b0 <main\_arena+80> :    0x0000000000000000      0x0000000000602560
0x7ffff7dd37c0 <main\_arena+96> :    0x0000000000000000      0x00007ffff7dd37b8
0x7ffff7dd37d0 <main\_arena+112>:    0x00007ffff7dd37b8      0x0000000000602000
0x7ffff7dd37e0 <main\_arena+128>:    0x0000000000602000      0x0000000000602040
0x7ffff7dd37f0 <main\_arena+144>:    0x0000000000602040      0x00007ffff7dd37e8

free sequence

Note) 일반적으로 메모리를 free하는 것은 다른 application이 사용할 수 있도록 OS로 메모리를 반환하는 것이 아니라, 메모리에 있는 그 chunk가 app 내에서 “free to be reused” 상태임을 표시하는 것이다. OS로 메모리를 반환하는 것이 아니기 때문에 OS의 관점에서 보면 메모리는 여전히 app에 속한 상태다. 그러나 top chunk가 충분히 크다면 일부는 unmap되어 OS로 반환된다. free(chunk)하면 다음과 같이 동작한다.

1. fastbin size에 속하는 경우, fastbin에 추가한다.
2. mmap’d chunk이면, munmap 한다.
3. PREV_INUSE가 unset이면, 인접한 다른 free chunk가 있는지 확인하고 있다면 합친다.
4. 이 chunk가 “top” chunk인 경우를 제외하고, chunk를 unsorted list에 위치시킨다. “top” chunk일 경우, top을 감소시킨다.(brk()) * fastbin chunk는 1.만 수행하고 넘어가기 때문에 unsorted bin에 들어가지 않는다.
5. chunk가 충분히 크다면, fastbins와 합치고 system에 메모리를 반환할 수 있을 만큼 top chunk가 충분히 큰지 확인한다. 이 단계는 일단 연기되었다가 다른 call이 수행되는 동안 진행될 수 있다. ( for performance reasons )

realloc sequence

1. If ptr == NULL, then the call is equivalent to malloc(size), for all values of size;
2. ptr = 0 && size = 0인 경우 malloc(0)이기 때문에 이 경우도 포인터를 반환한다.
3. if size == 0, and ptr != NULL, then the call is equivalent to free(ptr). free()는 return value가 없는데 반해, realloc()은 내부에서 free()를 호출하는 경우 0을 반환한다. 그리고 더 중요한건, 꼭 realloc(ptr, 0)이 아니라, 더 작은 사이즈로 realloc(ptr, small)하는 경우도 줄어든 부분은 c free()한 것 처럼 fd/bk로 채워진다.

mmap’d chunk

realloc이 가능할지 아닐지는 kernel에 달려있으며 가능한 경우 mremap()을 사용한다. system이 munmap()을 지원하지 않는 경우나, new size가 old size보다 작은 경우 그냥 바로 old address를 리턴해도 상관 없으므로 old address를 리턴하게 된다.

arena chunk

1. 할당된 size를 감소시키는 요청이 들어왔고 이렇게 하는게 충분히 가치있는 일이면, chunk가 둘로 나뉜다. 첫 번째 부분은 리턴되고, 두 번째 부분은 arena에 free chunk로 남는다.
2. 할당된 size를 증가시키는 요청이라면 다음 인접 chunk를 확인한다. free chunk이거나, “top” block이면서 충분히 크다면 그 chunk를 합병한다. 이렇게 만들어진 chunk도 사이즈 조정을 위해 1처럼 나뉠 수 있다.
3. 할당된 size를 증가시켜야 하는데 2가 불가능하다면, malloc-copy-free sequence가 일어난다. 이 때 chunk의 내용 전체가 new chunk로 복사되기 때문에, new chunk 자리에 있던 내용은 모두 사라진다.