About malloc () and free ().

About malloc() and free().

malloc(10)이라는 호출은 '최소' 10byte의 공간을 확보하고, 확보된 공간의 첫 주소를 반환한다.

따라서 malloc이 리턴한 주소가 1000이라면, 1000부터 1009번지까지는 안전하게 사용할 수 있다고 보장할 수 있다. 

단, 1010번지 이후의 주소에 대한 접근은 안전이 보장되지 않는다.

물론, 보통의 경우는, malloc()계열의 함수는 일정크기의 memory chunk 단위로 할당을 수행한다. 

즉, malloc(1) 이라는 호출이 있을 때, 1바이트 만을 할당하는 것은 비효율적이기 때문에 환경에 따라 다르지만, 

예를 들어, chunk의 크기가 64바이트라면, 그 미만의 크기는 64바이트로 일괄적으로 할당하곤 한다. 

즉, 안전하게 접근할 수 있어야 하는 크기 이상의 메모리 영역을 할당받는 것이 malloc()함수의 역할이다. 

물론, 그렇다고 할지라도 지정된 크기를 벗어나는 범위를 참조하는 것은 안전성을 보장할 수 없다는 것에는 변함이 없다.

free()함수는 주소 자체만으로는, 그 주소로부터 몇바이트가 할당되었는지는 전혀 알 수 없다.

ptr = (char*)malloc( 20 ); //  1

free( ptr ); // A

ptr = (char*)malloc( 10  ); // 2

free( ptr ); // B

위 코드에서 1과 2에서 리턴하는 주소는 같게 나온다. 이는 동적힙이 대개는 min heap으로 구성되어 있기 때문이다. 

즉, 주어진 크기보다 큰 블럭 중에서 가장 작은 메모리 블럭을 할당해 준다. 따라서, free()함수에 전달되는 인자는 A와 B에서 같다. 

하지만, A에서는 20바이트를 해제해야 하고, B에서는 10바이트를 해제해야 한다.

OS에서는 모든 메모리 블럭을 heap으로 관리한다. (사실 heap은 자유 할당 영역을 관리하기 위한 자료 구조의 이름일 뿐.) 정확히는, OS의 커널 코드가 어플리케이션의 주소공간에 매핑되어 메모리 할당 서비스를 수행해 주는 구조다. 이 힙에는 주소-사이즈의 쌍이 사이즈순으로 min heap으로 구성된 구조를 가진다. 즉 가장 사이즈가 작은 힙이 상위로 올라가는 구조다. 따라서 할당 요청이 들어오면 OS에서는 힙을 루트부터 검색하여 요청된 크기보다 큰 최소크기의 블럭을 찾아내어 이 블럭을 '할당' 상태로 바꾸고 자유 힙으로부터 빼내고 할당 블럭 리스트로 이동한다.

이때, 자유 힙이건, 할당 블럭 리스트이건, <주소-사이즈> 쌍을 관리하는 것은 변함이 없다. 즉, 하나의 독립된 블럭에 대해서, 32비트 시스템에서는 최소 8바이트의 오버헤드가 존재한다. 또한 자료구조의 유지를 위해 필요한 기타 태그와 정보를 포함한다면 오버헤드가 더 커지리라는 점을 짐작할 수 있다. 

따라서 너무 작은 블럭, 이를테면 1바이트짜리 블럭을 할당한다면 힙 유지를 위한 자료의 크기가 블럭의 크기보다 커져서 배보다 배꼽이 더 크다는 것을 알 수 있다. 따라서, 보통의 경우 메모리 할당은 최소 크기의 메모리 청크를 정하여 이 크기의 배수로 할당한다.

free()호출로 할당된 블럭을 해제할 때는, 할당 블럭 리스트를 검색하여 지정된 주소의 블럭을 찾아내서 '사용가능' 상태로 바꾸고 다시 자유 힙에 삽입하게 된다. 즉, 힙으로부터의 메모리 할당과 해제는 모두 자료구조 검색을 통해 이루어지는 작업이며, 이 자료구조에는 <주소-사이즈>쌍이 저장되어 있으므로 OS는 언제나 어떤 주소에 얼마만큼의 메모리가 할당되어 있는지를 알아낼 수 있다.

하지만, 자료구조의 검색은 시간이 많이 걸리는 작업이다. 즉, 할당작업은 기본적으로 힙 검색이며, 힙 검색은 기본적으로 바이너리 트리 검색과 동일한 작업이 되므로 블럭수의 log에 비례하는 시간이 걸린다. 대체적으로 할당이 시간이 오래 걸리는 작업이다.

물론, 해제 역시 시간이 많이 걸린다. 위에서 말씀드린대로 해제 작업을 하려면, 할당 블럭 리스트를 검색하여 해당 블럭의 주소를 찾아야 하는데, 이 할당 블럭 리스트가 주소 순으로 정렬되어 있다면 블럭 수의 로그에 비례하는 시간이 걸리겠지만, 자유 힙의 사용하지 않는 영역을 할당 블럭 리스트로 사용한다면 블럭 수에 비례하는 시간이 걸리게 된다. 물론, 주소 순으로 정렬한다고 쳐도, 이는 할당시에 정렬해야 하므로 할당에 걸리는 시간이 더욱 길어진다.

그래서 작업시간 절약을 위해서 할당 대상이 되는 memory chunk 앞부분에는 헤더가 붙는 경우가 있다. 즉, 최소 memory chunk의 크기가 64바이트라면, 앞부분 4바이트에는 이 chunk에 할당된 크기가 얼마인지를 나타내는 헤더가 붙어 있는 식이다. (이는 시스템에 따라 다르다) 즉, 앞의 예제에서, (1)에서 20바이트를 할당받은 주소가 1000번지라면, 1000번지 근처의 메모리 구성은 (인텔 계열 CPU 기준으로) 다음과 같은 식이다. 

Ex)

9996:0x14 <-- malloc()이 실제로 할당하는 주소.
9997:0x00
9998:0x00
9999:0x00
1000:undetermined <-- malloc()이 리턴하는 주소.
1001:undetermined
1002:undetermined
1003:undetermined
1004:undetermined
1005:undetermined
1006:undetermined
1007:undetermined
1008:undetermined
1009:undetermined
.................
1019:undetermined <-- malloc()에 의해 확보된 영역의 끝.
1020:unsafe

이제 free()함수에 1000이라는 주소가 전달되었다면, free함수는 1000으로부터 4번지를 앞으로 이동하여 0x00000014를 읽어서 1000번지 이후로 할당된 범위가 20바이트라는 것을 알아내고, 그만한 영역을 다시 heap에 되돌려 놓는다.

물론, 위의 예는 예시에 불과하며, 실제로는 OS의 메모리 할당 매커니즘에 다분히 의존적이다.

또한 이 태그의 크기가 32bit 시스템에서는 최소 4바이트가 되어야 하므로, 메모리 할당시의 오버헤드가 조금 더 커지는 단점이 있고, 

이는 속도를 위해 메모리를 희생하는 전형적인 예라고 보면 된다.

물론, 사이즈 태그를 붙이는 것은 어디까지나 속도를 위한 OS 설계시의 선택사항일 뿐이며, 기본적으로는 <주소-사이즈> 쌍을 자유 힙과 

할당블럭리스트 사이에서 검색하는 방식이 일반적이다.