malloc()의 구현 방법?

C 언어에서 흔하게 사용되는 메모리 할당 함수인 malloc()은 어떻게 구현되어 있을까?
함께 짝으로 사용되는 free()는 어떻게 구현되어 있을까?

흔하게 공룡책으로 불리우는 Operating System Concepts에서 배웠던 기억으로는 first-fit과 best-fit이라는 전략이 있다는... 어렴풋한 기억이 있을 뿐이다.
당시의 그 책은 매우 유용하기도 했지만, 다분히 교과서적이고 개념 위주였기에 실제 구현과는 거리가 좀 있었던 것으로 기억한다.

아무튼...
커다란 메모리 공간을 확보해서 힙으로 사용하도록 정한 후에, malloc()이라는 함수를 통해 메모리 할당 요청이 들어왔을 때, 그리고 메모리를 다 사용한 후에 free()라는 함수를 통해 메모리를 반납할 때, 이들을 어떤 식으로 처리하는 것이 좋을까?

우선은 잠시 생각해 본 아이디어를 끄적여 보겠다.

- 일단은 first-fit으로 구현.

- 메모리의 할당과 반납의 반복으로 힙은 여기 저기 조각난 상태가 될 것인데, 이 경우에 메모리 할당 요구가 발생하면, 비어있는 조각들 중에 크기가 맞는 것을 골라서 할당해 주어야 한다.
- 이를 위해 메모리 할당 테이블과 같은 별도의 정보를 관리하는 것도 하나의 방법이지만, 아주 작은 메모리의 할당이 많이 발생하면 관리를 위한 정보가 급격히 늘어나는 문제가 있다.
- 예전에 어떤 프로토콜 스택을 사용하면서 소스를 살펴보니, 이런 관리 정보를 힙 내부에 보관했던 기억이 있다. 즉, 사용하지 않은 힙의 메모리 내부에 비어있는 메모리 블럭들에 대한 정보를 저장하여 관리하는 것.
- 비어있는 메모리 블럭의 시작 부분에 블럭의 크기와 이전 블럭의 주소, 다음 블럭의 주소를 가지고 있는 구조. 최초의 힙은 블럭의 크기가 힙의 크기와 일치하고 이전 블럭의 주소와 다음 블럭의 주소는 null 값이 될 것이다. 전역 변수로 비어있는 첫번째 블럭의 주소만을 가지고 있으면 되고, 이 변수의 최초값은 힙의 시작 주소와 일치.
- 메모리 할당 요청이 들어오면 전역변수로 첫번째 빈 블럭부터 시작하여, 할당할수 있는 크기의 블럭이 나올 때까지 링크드 리스트처럼 연결된 블럭을 순회한다.
- 할당 가능한 블럭이 나오면, 할당 요청된 크기만큼을 할당하여 돌려주고, 블럭의 남은 조각을 새로운 블럭으로 리스트에 넣어주면 된다.

- 메모리 반납은 시작 주소만 있을 뿐, 크기는 없다. 위와같은 구조에서 해당 주소만이 주어졌을 때, 크기는 어떻게 알아내야 하는가?
- 할당된 메모리의 앞 부분에 할당된 블럭의 크기를 넣는다? --> 오케이.
- 그러면 비어있는 블럭의 맨 처음에도, 할당된 블럭의 맨 처음에도 그 블럭의 크기가 들어가는 셈.

- 메모리 얼라인먼트 문제?
- malloc()함수에서 할당 크기가 아니라, 메모리 단위와 개수로 할당을 받는 이유는 뭘까?