[시스템 프로그래밍] Malloc Lab Implicit (1)

 

 

 

이론에서 배운 것들을 활용해 Malloc Lab을 해결해보자.

 

 

 

 

 

 

WSIZE : 메모리 블록의 header와 footer 크기이다. (word 크기)

DSIZE : WSIZE의 두 배 크기.

CHUNKSIZE : 초기 가용 블록의 크기와 힙을 확장할 때 사용되는 값이다.

OVERHEAD : header와 footer를 더한 크기이다.

MAX, MIN : 말 그대로.. 두 수를 비교한다.

PACK : 크기(size)와 할당 비트(alloc)을 통합해 하나의 워드로 묶는다. header와 footer에 값을 저장 할 때 사용한다.

GET : 포인터 p가 가리키는 위치에서 word 크기의 값을 읽어온다.

PUT : 포인터 p가 가리키는 위치에서 word 크기의 값을 val 만큼 쓴다.

GET_SIZE : header의 크기를 읽을 때 사용한다.

GET_ALLOC : 현재 블록의 할당 가능 여부를 확인한다. (0은 할당 불가능 1은 가능)

HDRP : 현재 블록의 포인터인 bp의 header 주소를 얻는다.

FTRP : 현재 블록의 포인터인 bp의 footer 주소를 얻는다.

NEXT_BLKP : 현재 블록의 포인터인 bp를 기준으로 다음 블록의 주소를 계산한다.

PREV_BLKP : 현재 블록의 포인터인 bp를 기준으로 이전 블록의 주소를 계산한다.

ALIGN : ALIGNMENT와 가장 근접한 8배수로 반올림한다.

 

 

매크로는 위와 같이 설정되어있다. 이제 단계별로 implicit 방식의 malloc lab을 구현해보자.

 

 

 

 

1. mm_init 함수 구현

 

 

 

 

 

 

우선 mem_sbrk 함수를 호출해 비어있는 힙 공간을 할당받는다. (4워드 만큼)

이 때 힙의 최대 공간 이상의 공간을 요청할 시 실패한다.

 

heapq_list 는 전역변수로 선언되어있어 어디서든 접근할 수 있다.

 

이제 할당받은 힙 공간을 채워 주는데, 채우기 전에 메모리 블록을 어떻게 사용할지 먼저 확인하자.

 

 

 

 

 

 

블록은 위와 같은 형태로 디자인한다.

패딩, 프롤로그, 에필로그 부분으로 나눠지고 각각의 부분들은 여러 메모리 블록을 할당 할 때 유용하게 사용될 예정이다.

 

PUT 매크로를 사용해 메모리에 패딩, 프롤로그, 에필로그 부분을 할당하고 값을 채워준다.

 

 

 

 

 

 

 

PUT 함수를 모두 실행하고 나면 메모리 블록은 위와 같은 형태로 할당돼있고, heap_listp의 위치를 적절히 조절해 extend_heap 함수를 통해 heap을 늘렸을 때는

 

 

 

 

 

블록이 위와 같은 형태로 할당되도록 한다.

 

 

extend_heap 함수는 힙이 초기화 될 경우나 메모리를 할당할 적당한 공간을 찾지 못했을 때 호출돼 힙의 크기를 늘려준다. (지금은 힙이 초기화 되는 상황이다)

 

따라서 힙의 크기를 늘려주는 extend_heap 함수도 따로 구현해 줘야 한다.

 

 

 

 

 

 

 

bp는 현재 블록의 포인터를 의미한다. bp를 적절히 조작하며 메모리를 할당한다.

 

정렬을 위해 힙이 늘어나는 정도를 의미하는 변수인 size는 8의 배수로 설정되어야 한다.

 

mem_sbrk 함수를 호출해 힙의 크기를 size만큼 늘려준다. (bp는 새로 만들어진 공간의 끝 부분에 위치하게 된다)

 

이제 PUT 매크로를 사용해 free 블록의 header, footer를 설정하고 에필로그의 위치를 새로 지정해준다. (새로 할당받았으니 에필로그도 뒤로 밀려난다)

 

free 블록의 header와 footer는 프롤로그와 다르다!!!

bp가 지금 어디에 위치하는지 정확히 파악하자!!!

 

 

 

 

2. find_fit() 함수 구현

 

 

find_fit 함수는 가용 리스트에서 적절한 블록을 찾는 역할을 한다.

first fit / next fit / best fit 세 가지 방법이 있는데, 우선 first fit 으로 구현한 후 다른 방법을 적용해보자.

 

 

 

 

 

 

가장 첫 부분부터 검색을 시작해야 한다. bp를 heap_listp로 설정하자.

NEXT_BLKP 매크로를 사용해 계속해서 다음 블록으로 넘어가 가용 블록을 찾는데, 해당 블록이 가용 블록인지 확인 할 때는 GET_ALLOC 매크로를 사용한다.

 

GET_SIZE 매크로로 얻은 값이 0인 경우는 해당 블록이 에필로그 부분임을 의미한다.

에필로그 부분까지 탐색했는데 가용 블록을 찾지 못했을 경우 NULL을 반환한다.

 

 

 

 

3. place() 함수 구현

 

 

가용 블록을 찾았으면 해당 블록을 할당해 줘야 한다.

이 때 malloc 함수와 place 함수가 사용된다.

 

 

 

 

 

 

place 함수는 할당할 위치와 할당할 크기를 인자로 받는다.

GET_SIZE 매크로로 현재 블록의 크기를 계산하고 계산한 위치를 할당된 영역으로 바꿔준다.

 

 

 

 

4. malloc() 함수 구현

 

 

malloc 함수 역시 가용 리스트에서 블록을 할당할 때 사용된다.

 

 

 

 

 

malloc 함수는 블록을 할당할 크기를 인자로 받는다.

인자의 값으로는 아무거나 들어올 수 있기 때문에 정렬을 위해 함수 내부에서 크기를 다시 조정해야 한다.

 

먼저 인자로 들어온 값이 0이면 할당할 필요가 없으니 무시한다.

크기는 무조건 8의 배수로 설정되어야 한다. 인접한 8의 배수로 적절히 조절해준다.

 

할당할 가용 블록이 가용 리스트에 있는지 확인하는데, 이 때 find_fit 함수를 사용한다.

 

적절한 공간을 찾았으면 place 함수로 바로 공간을 할당해 주면 되지만, 찾지 못한 경우 위에서 정의한 extend_heap 함수를 호출해 힙의 크기를 늘린 후 place 함수를 호출한다.

 

 

 

5. realloc 함수 구현

 

 

realloc 함수는 할당된 블록의 크기를 조절할 때 사용한다.

 

 

 

 

 

realloc 함수는 크기를 재조정할 블록의 위치와 크기를 인자로 받는다.

 

인자로 받은 크기의 블록을 만든 후 C 라이브러리의 memcpy 함수를 통해 기존 블록의 내용을 새로 만든 블록에 옮긴 후 새로운 블록을 반환하는 방식으로 작동한다.

 

몇 가지 edge case의 경우 if-else 문으로 처리해줬다. (크기가 0보다 작은 경우, 인자로 받은 위치가 비어있는 경우 등..)

 

 

필요한 건 모두 구현 한 것 같으니 mdriver를 사용해 테스트 해 보자.

 

 

 

 

 

 

payload address가 8바이트로 할당되지 않았다며 오류가 발생한다 -_-

 

아마도 힙을 확장하면서 가용 블록들이 생길 때 현재 블록 근처의 가용 블록들을 합칠 수 있는데도 합치지 않아서 발생하는 것 같다.

 

합치지 않아도 8바이트로 할당되는건 보장될 것 같았는데.. 우선 합치는 함수를 구현하고 다시 테스트 해 보자.