- 개인적으로 공부하면서 지속적으로 정보를 추가, 수정, 삭제합니다.
- 정확하지 않은 부분 피드백 주시면 감사합니다.
- 본 노트는 크래프톤정글 6주차 주제인 “동적 메모리 할당기 구현” 과제를 위한 개발 일지입니다.
2022-12-02, 2022-12-03
말록 랩 - 동적 메모리 할당기 구현하기 이론
참고: Computer System A Programmers Perspective (3rd), Randal E. Bryan, David R. O’Hallaron, 김형신 번역, 피어슨에듀케이션코리아, 2016
무엇?
컴퓨터 시스템 정리 (CSAPP) Chapter 9 가상메모리 노트의 9.9.12절 내용을 가져왔습니다.
9.9.12 종합 설계: 간단한 할당기의 구현
- intro
- 즉시 경계 태그 연결을 사용하는 묵시적 가용 리스트에 기초한 간단한 할당기의 구현
- 최대 블록 크기는
- 최소 블록 크기는 16 byte (=4 워드)
- 코드는 32비트(
gcc -m32) 또는 64비트(gcc -m64)이며, 프로세스에서 수정 없이 돌 수 있는 것은 64비트 (The code is 64-bit clean, running without modification in 32-bit (gcc -m32) or 64-bit (gcc -m64) processes)
- 할당기 기본 설계:
memlib.c파일- 이 파일은 메모리 시스템 모델
- 우리가 설계한 할당기가 기존의 시스템 수준의
malloc패키지와 상관없이 돌아가게 하기 위함 mem_init함수: 힙으로 사용할 수 있는 가상메모리를, 큰 더블 워드로 정렬된 바이트의 배열로 초기화해주는 것mem_start_brk: 힙의 시작부분을 나타내는 포인터 (※ 책에서의mem_heap변수임! )mem_start_brk와mem_brk사이의 바이트들은 할당된 가상메모리mem_brk: 이 변수 다음에 오는 바이트들은 미할당 가상메모리mem_sbrk함수: 추가적인 힙 메모리를 요청함. 시스템sbrk함수와는 달리 힙을 축소하라는 요청을 거부함.
- 우리가 설계한 할당기가 기존의 시스템 수준의
- 묵시적 가용 리스트 & 블록 포맷
- 묵시적 가용 리스트의 형식
- 첫번째 워드: 더블 워드 경계로 정렬된 미사용 패딩용 워드
- 프롤로그 블록: 헤더와 풋터로만 구성된 8바이트 allocated 블록, 초기화 과정에서 생성되며 절대 반환하지 않음
- regular block:
malloc,free를 호출해서 생성된 0개 이상의 일반 블록들 (최소 블록 크기 4 워드) - 에필로그 블록: 헤더만으로 구성된 크기가 0으로 allocated 브록. 힙은 항상 에필로그 블록으로 끝남
- 프롤로그 블록과 에필로그 블록은 왜 존재하는가?
- 연결 과정 동안 가장자리 조건을 없애주기 위한 속임수 아마도 연결 연산에서 에러 방지를 위함이 아닐까
- 할당기는 한 개의 정적(static) 전역변수
heap_listp를 사용하며, 이것은 항상 프롤로그 블록을 가리킴(작은 최적화로 프롤로그 블록 대신 다음 블록을 가리키게 할 수 있음)
- 묵시적 가용 리스트의 형식
- 이 파일은 메모리 시스템 모델
- 가용 리스트 조작을 위한 기본 상수와 매크로
#define CHUNKSIZE (1<<12)가 뭐람?- 1 << 12는 이진수 연산자인 왼쪽 시프트(left shift)를 사용한 것입니다. 왼쪽 시프트 연산은 왼쪽으로 이동한 후, 오른쪽의 빈 자리를 0으로 채우는 연산자입니다. 예를 들어, 1 << 12는 1이라는 수를 왼쪽으로 12번 이동시킨 결과인 값인 4096을 나타냅니다. 이진수로 변환하면 1은 0001이며, 왼쪽 시프트 연산을 하면 0001 << 12는 000000000001이 되고, 이것을 십진수로 변환하면 4096이 됩니다.
- 초기 가용 리스트 만들기
extend_heap- 새 가용 블록으로 힙을 확장시킴
- 다음의 경우에 호출함
- 힙이 초기화 될 때
mm_malloc이 적당한 fit을 찾지 못했을 때, 정렬을 유지하기 위해extend_heap은 요청한 크기를 인접 2워의 배수(8바이트)로 반올림하며, 그 후에 메모리 시스템으로부터 추가적인 힙 공간을 요청함
- 크기가 더블 워드의 배수인 블록(즉 주소가 8의 배수인)을 리턴함
- 에필로그 블록의 헤더에 곧 이어서 더블 워드 정렬된 메모리 블록을 리턴
- 새 가용블록의 헤더, 풋터를
- 블록 반환과 연결
mm_free함수bp가 가리키는 블록을 free시키고, 인접한 가용 블록과 9.9.11절에서 설명한 경계 태그 연결 방식으로 연결함- 에필로그 블록, 프롤로그 블록을 설정함으로써 힙의 시작과 마지막 부분의 블록들의 previous, next 블록을 체크하는 과정의 성능에 도움 ⇒ 그렇지 않으면 매번 블록들이 경계에 위치해있는지 확인해야 하며(드문 케이스인), 더 느리고 에러날 가능성도 커짐
coalesce함수
- 위 그림 9.40의 네 케이스를 구현
- 블록 할당
mm_malloc함수 호출해서size바이트의 메모리 블록을 요청- 추가적인 요청을 체크한 후, 할당기는 요청한 블록 크기를 조절하여 헤더와 풋터를 위한 공간 확보, 더블 워드 요건 만족
2022-12-04
VScode WSL 우분투 환경에서 C 헤더 파일 오류 뜰 때
참고:
무엇?
잘 되던 C 소스 코드를 VScode가 헤더 파일 인식을 하지 못하는 에러 발생.
헤더를 작성한 코드에 빨간 줄이 쫙쫙가고 컴파일이 되지 않음.
어떻게?
프로젝트에 생성된 .vscode 폴더의 c_cpp_properties.json 파일에서
"name"이"Linux"로 되어 있는지 확인하고 (window 환경은win32로 표기되며, 이 경우는 다른 경로를 추가해야 함)"includePath"에"/usr/include/"이 경로를 하나 더 추가해줌.
→ 다음 날 똑같은 에러 발생!
문제는 CMake 익스텐션에 있었던 듯 싶다.
c_cpp_properties.json 파일에서 configurationProvider 항목을 주석 처리했더니 정상적으로 헤더를 인식했다.
말록 랩 - 동적 메모리 할당과 정적 메모리 할당 키포인트
참고: https://noirstar.tistory.com/10
무엇?
- 동적 메모리 할당과 정적 메모리 할당에 대한 key point ☞ 컴퓨터 시스템 노트에 정리
- 동적 메모리 할당은 프로그램으로 하여금 메모리를 런타임에(at runtime) 할당하게 함. 반면 정적 메모리 할당은 메모리가 컴파일시에(at a complie time) 할당되도록 함.
- 동적 메모리 할당이 정적 메모리 할당보다 더 유연하고 융통성이 있음. 왜냐하면 필요한 만큼 메모리를 할당할 수 있기 때문. 반면 정적 메모리 할당은 모든 메모리가 한번에 할당 됨.
- 동적 메모리 할당이 정적 메모리 할당보다 더 효율적임. 왜냐하면 필요할 때만 메모리를 할당할 수 있기 때문이며, 더 이상 필요하지 않을 때 메모리를 반환할 수 있기 때문.
- 동적 메모리 할당이 정적 메모리 할당보다 더 에러를 일으키기 쉬움. 왜냐하면 메모리 누수와 단편화로 이어질 수 있기 때문.
- 동적 메모리 할당은 정적 메모리 할당보다 더 많은 메모리 오버헤드를 필요로 함. 왜냐하면 메모리 할당과 할당 반환을 관리하는 프로그램이 필요하기 때문.
- 동적 메모리 할당은 메모리 크기에 빈번한 변화가 있는 프로그램에 적합하며, 정적 메모리 할당은 고정적인 메모리 크기를 갖는 프로그램에 적합함.
- 동적 메모리 할당은 연결 리스트, 스택, 큐와 같은 자료 구조를 만들 때 사용 될 수 있으며, 정적 메모리 할당은 배열같은 고정된 크기의 데이터 구조를 만드는데 사용 됨.
bits/libc-header-start.h: No such file or directory 오류
참고:https://my-repo.tistory.com/12
무엇?
mdriver.c 파일 컴파일 중 발생한 에러
왜?
gcc에서 32비트 컴파일 옵션이 없어서 그렇다고 함.
어떻게?
$ sudo apt-get install gcc-multilib g++-multilib
터미널 프롬프트에 위 명령어를 입력하고
32비트 컴파일을 가능하게 해주는 패키지를 인스톨하면 됨.
2022-12-05
C에서 malloc, calloc, realloc 함수의 사용 비교
참고:
무엇?
동적 메모리 할당을 위해 사용되는 C의 함수들
-> C언어 노트에도 추가함
왜? 어떻게?
- malloc 함수
- 동적 메모리 할당을 위해 사용
- 이 함수는 메모리를 할당하고 반환하는 포인터를 반환
- 예를 들어, int 형 변수를 선언하기 위해 메모리를 할당하려면 다음과 같이 malloc 함수를 사용
// int 형 변수를 선언하기 위해 메모리를 할당
int *ptr;
ptr = (int*) malloc(sizeof(int));
- calloc 함수
- 항상 malloc 함수와 비슷하게 사용
- 이 함수는 메모리를 할당하고 할당한 메모리를 0으로 초기화
- 예를 들어, int 형 변수를 선언하기 위해 메모리를 할당하려면 다음과 같이 calloc 함수를 사용
// int 형 변수를 선언하기 위해 메모리를 할당
int *ptr;
ptr = (int*) calloc(1, sizeof(int));
- realloc 함수
- 동적 메모리 할당을 위해 사용
- 이 함수는 메모리의 크기를 변경하고, 기존 메모리를 유지(ex: 배열의 크기를 늘려야 하는 경우)
- 식구가 더 늘어날 예정이라 기존 식구들 데리고 더 큰 집으로 이사하는 상황
- 먼저 메모리의 크기를 늘려야 하는 배열의 포인터를 인자로 받음 → 새로운 크기로 재할당한 메모리를 반환
- 예를 들어, int 형 변수를 선언하기 위해 메모리를 늘려야한다면 다음과 같이 realloc 함수를 사용
// int 형 변수를 선언하기 위해 메모리 크기 늘리기
int *ptr;
ptr = (int*) realloc(ptr, 2 * sizeof(int));
// A라는 리스트에 원소를 더 추가하기 위해 메모리 크기 늘리기
int *A = (int*) realloc(A, sizeof(int)*(n+1));
A[n] = x; // x를 배열 A의 마지막 인덱스에 추가합니다.
n++; // 원소 개수를 하나 늘립니다.
malloc과realloc의 사용 예시
// malloc으로 메모리를 할당 받아서 0부터 2까지 값 삽입
int *ptr;
ptr = (int*) malloc(3 * sizeof(int));
for(int i = 0; i < 3; i++)
ptr[i] = i+1;
// 3, 4를 추가하여 5개의 원소를 가지기 위해 메모리 크기를 늘려야한다면
ptr = (int*) realloc(ptr, 5 * sizeof(int)); // int 타입 5개가 들어갈 메모리 할당 받음
for(int i = 3; i < 5; i++) // 3, 4를 삽입
ptr[i] = i+1;
- 메모리 크기를 줄일 때도
realloc을 사용할까?- 사용한다!
- 주어진 크기보다 작은 값을 인자로 줄 경우, 해당 메모리 영역의 크기가 줄어들고 남은 부분은 반환
- 언제 그렇게 사용할까?
- realloc을 사용해 메모리 크기를 줄이는 것은 크기가 큰 메모리 공간을 줄여야 할 때 유용
- 특히 동적 메모리 할당을 사용하는 경우, 가비지 컬렉션을 사용하지 않는 C 프로그램이나 시스템 프로그래밍에서도 자주 사용
memcpy 사용법
참고: https://hand-over.tistory.com/49
무엇?
C의 memcpy() 함수
-> C언어 노트에도 추가함
왜?
말록 랩의 mm_realloc 함수를 구현하는데 필요함.
어떻게?
#include <string.h>
// src 영역에서, dest 영역으로, n 바이트만큼 복사 → dset의 포인터 반환
void *memcpy(void *dest, const void *src, size_t n);
말록 랩 - realloc 코드 구현하기
참고:
무엇?
- 기존 realloc 함수의 에러 메시지 해결하기
mm_realloc did not preserve the data from old block
▽ 수정 후
void *mm_realloc(void *oldptr, size_t size) // realloc할 포인터, 새롭게 필요한 총 사이즈
{
// 포인터가 Null이 아니고 이미 free된 상태가 아닌 경우 (지워도 점수 영향X)
if (oldptr != NULL && GET_ALLOC(HDRP(oldptr)))
{
size_t copySize; // 복사해야 할 기존 사이즈 선언
void *newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
// copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize); // 새로운 포인터로, 올드 포인터에서 copysize 만큼 복사
mm_free(oldptr);
return newptr;
}
return NULL;
}
▽ 수정 전 기존 realloc 함수
void *mm_realloc(void *ptr, size_t size)
{
void *oldptr = ptr;
void *newptr;
size_t copySize;
newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
// 이 부분이 문제
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE);
if (size < copySize)
copySize = size;
memcpy(newptr, oldptr, copySize);
mm_free(oldptr);
return newptr;
}
어떻게?
copySize = *(size_t *)((char *)oldptr - SIZE_T_SIZE); 이 부분 도저히 이해가 되지 않다가,
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE; 이렇게 바꾸니까 오류 없이 잘 돌아감
시간 점수에서 더 점수 나옴
왜?
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
복사할 사이즈 = 헤더에서 읽은 블록 사이즈 - 워드 2개 (헤더, 풋터 제외)
→ 데이터만 남게 됨
여기서 -DSIZE를 하지 않으면, 점수가 더 낮게 나옴 (헤더 풋터까지 계속 복사를 해야 하기 때문에?)
2022-12-06, 2022-12-07
컴퓨터 시스템 9장 가상메모리 정리 노트 업데이트
참고:
무엇?
컴퓨터 시스템 정리 (CSAPP) Chapter 9 가상메모리
왜?
사실 9장 앞부분을 읽지 않아도 9.9장만 보고 이해하면서 코드를 구현하기는 가능한 것 같다.
하지만 중요한 배경 개념이니 정리!
ChatGPT에게 가상 메모리 질문하고 배우기
간단하게 개념을 요약하고 설명해줘서 공부할 때 도움이 많이 된다!
- 가상 메모리와 실제 물리 메모리 중 어떤 것이 더 큰 용량을 갖는가?
실제 물리 메모리가 더 큰 용량을 갖는다. 가상 메모리는 실제 물리 메모리와 디스크 중 어느 것을 가상 메모리로 사용할지를 제어하기 위한 가상 메모리 관리 장치로 구성되어 있다. 따라서 가상 메모리는 임의로 실제 메모리보다 작거나 큰 용량으로 설정할 수 있지만, 실제 물리 메모리는 현재 시스템에 설치된 메모리 용량을 따른다.
- 가상 메모리는 왜 필요한가?
가상 메모리는 시스템에 설치된 물리 메모리의 용량을 넘어서는 데이터를 처리하기 위해 필요한 기술이다. 컴퓨터 프로그램이 메모리 용량보다 더 많은 데이터를 처리하기 위해서는 실제 물리 메모리를 증설하거나 디스크를 사용해 메모리 용량을 확장해야 한다. 가상 메모리는 물리 메모리를 증설하지 않고도 메모리 용량을 확장할 수 있게 해주는 용도로 사용된다.
- 어떻게 그게 가능한가?
가상 메모리가 가능하게 된 것은 디스크와 가상 메모리 관리 장치의 공동 작업에 의해 가능하게 되었다. 가상 메모리 관리 장치는 메모리에 저장된 데이터를 디스크의 특정 위치로 이동하는 등의 기능을 수행한다. 디스크는 데이터를 가상 메모리에 저장할 수 있는 저장 공간을 제공한다. 이렇게 디스크와 가상 메모리 관리 장치의 공동 작업으로 가상 메모리를 구현한 것이다.
- 만약 물리 메모리가 없으면 가상 메모리는 어떻게 되는가?
물리 메모리가 없으면 가상 메모리는 사용할 수 없다. 가상 메모리는 물리 메모리에 저장된 데이터를 디스크로 이동하거나 메모리로 불러오는 등의 기능을 수행하기 위해 필요한 물리 메모리가 있기 때문이다. 따라서 물리 메모리가 없으면 가상 메모리는 사용할 수 없다.
- 가상 메모리가 없다면 속도가 얼마나 느려지나요?
가상 메모리가 없다면 시스템의 속도가 현저하게 느려질 수 있다. 가상 메모리는 실제 메모리보다 큰 용량의 데이터를 처리하기 위해 디스크를 사용해 메모리 용량을 확장해준다. 따라서 가상 메모리가 없다면 메모리 용량이 제한되어 처리 속도가 느려질 수 밖에 없다.
- 만약 물리 메모리 용량이 크다면 가상 메모리 용량도 큰가요?
아니다. 물리 메모리 용량과 가상 메모리 용량은 다르기 때문에 물리 메모리 용량이 크더라도 가상 메모리 용량은 그렇지 않을 수도 있다. 가상 메모리 용량은 사용자가 임의로 설정할 수 있기 때문이다. 따라서 물리 메모리 용량이 크더라도 가상 메모리 용량이 작을 수도 있다.
- 가상 메모리 용량은 어떻게 설정하나요?
가상 메모리 용량은 사용자가 임의로 설정할 수 있다. 대부분의 운영체제에서는 사용자가 가상 메모리의 용량을 설정할 수 있는 기능이 제공된다. 또한 일부 운영체제는 가상 메모리 용량을 자동으로 조정하는 기능도 제공한다. 이 기능은 시스템의 자원을 최적화하기 위해 사용할 수 있다.
- 가상 메모리 용량은 크면 클수록 좋나요?
가상 메모리 용량이 클수록 좋지는 않다. 만약 가상 메모리 용량이 크면 디스크 저장 공간이 부족할 수 있다. 따라서 가상 메모리 용량을 적절하게 설정해야 한다. 또한 가상 메모리 용량이 너무 크면 시스템의 속도가 느려질 수도 있기 때문에 적절한 값을 설정해야 한다.
- 그 적절한 값은 어떻게 알 수 있나요?
가상 메모리 용량을 적절하게 설정하기 위해서는 사용자의 시스템 용량과 메모리 용량을 참고해야 한다. 시스템 용량과 메모리 용량을 고려해 가상 메모리 용량을 적절히 설정하면 좋다. 또한 운영체제가 제공하는 가상 메모리 용량 설정 기능을 이용해 가상 메모리 용량을 적절하게 설정할 수도 있다.
말록 랩 - realloc 코드 수정하기
참고:
무엇?
- realloc 기존 알고리즘
1. 말록으로 새로운 포인터를 받음
2. 새로운 포인터가 NULL이면 NULL 반환
3. 아니라면
1. copySize 지정(기존 포인터의 헤더를 통해 사이즈를 읽고, -DSIZE)
2. memcpy 함수로 새로운 포인터로 copySize만큼 복사
3. 기존 포인터 free
4. 새로운 포인터 반환
- 내가 생각한 알고리즘
1. 재할당받아야 하는 사이즈가 기존 사이즈보다 큰 경우
1. 기존 realloc 알고리즘으로 수행
2. 아닌 경우
1. 기존 bp에 그대로 배치
2. 나머지 블록의 사이즈가 4워드 이상인 경우
1. 나머지 블록 split & free
왜?
사이즈를 줄이는 경우 다른 가용 블록을 찾지 않아도 되니까 알고리즘보다 시간이 절약되지 않을까?
어떻게?
- 결과
mm_realloc did not preserve the data from old block
이 에러의 굴레에서 벗어날 수 없었다. ;ㅅ;
일단 디버깅할 시간이 부족할 거 같아 next block 검색을 우선하는 알고리즘으로 대체했다.
휴, 무엇이 잘못됐는지 발견하신분이 있다면 알려주세요. ㅠ
▽ 디버깅 못한 realloc 함수
// realloc 사이즈 비교 + 그 자리에 place
void *mm_realloc(void *oldptr, size_t size) // realloc할 포인터, 새롭게 필요한 총 사이즈
{
// 포인터가 Null이 아니고 이미 free된 상태가 아닌 경우 (지워도 점수 영향X)
if (oldptr != NULL && GET_ALLOC(HDRP(oldptr)))
{
size_t copySize; // 복사해야 할 기존 사이즈 선언
size_t needSize = ALIGN(size + DSIZE);
size_t nowSize = GET_SIZE(HDRP(oldptr));
// 블록 사이즈가 잘 맞으면 재할당 X
if (needSize == nowSize)
{
return oldptr;
}
// 블록 사이즈가 할당 요청하는 사이즈보다 작으면
if (needSize < nowSize)
{
size_t subSize = nowSize - needSize; // 사이즈의 차이 계산
if (subSize >= 2 * DSIZE) // 사이즈의 차이가 더블 워드보다 큼 -> 분할 가능
{
void *bp2 = FTRP(oldptr) - (subSize - DSIZE);
PUT(FTRP(oldptr), PACK(subSize, 1)); // 기존 풋터를 뉴 풋터로 갱신
PUT(HDRP(oldptr), PACK(needSize, 1)); // 기존 헤더의 사이즈, 비트 갱신
PUT(FTRP(oldptr), PACK(needSize, 1)); // 기존 블럭의 풋터를 새로 만듦
PUT(FTRP(oldptr) + WSIZE, PACK(subSize, 1)); // 남은 블럭의 헤더 갱신
mm_free(bp2);
}
else // 사이즈의 차이가 더블 워드보다 작음 -> 분할 못함, 기존 것만 place
{
PUT(HDRP(oldptr), PACK(needSize, 1)); // 기존 헤더의 사이즈, 비트 갱신
PUT(FTRP(oldptr), PACK(needSize, 1)); // 기존 풋터를 뉴 풋터로 갱신
}
return oldptr;
}
else // needSize > nowSize: 필요한 크기가 지금 크기보다 크면
{
void *newptr = mm_malloc(size);
if (newptr == NULL)
return NULL;
copySize = GET_SIZE(HDRP(oldptr)) - DSIZE;
memcpy(newptr, oldptr, copySize); // 새로운 포인터로, 올드 포인터에서 copysize 만큼 복사
mm_free(oldptr);
return newptr;
}
}
return NULL;
}
말록 랩 - 최종 코드 분석
참고:
점수에 영향을 준 포인트
find_fit함수에서 next fit 정책 사용realloc함수를 next block을 먼저 확인하고 재할당하게 수정- 기본
realloc함수에서는copysize를 조금 수정해서 작은 최적화를 이룰 수 있었음
- 기본
- 가용리스트 기본 상수 & 조작 매크로
/* 더블 워드 얼라인먼트; 싱글워드는 4, 더블워드는 8 */
#define ALIGNMENT 8
/* 얼라인먼트의 배수로 반올림 */
#define ALIGN(size) (((size) + (ALIGNMENT - 1)) & ~0x7)
#define SIZE_T_SIZE (ALIGN(sizeof(size_t)))
#define WSIZE 4 /* Word and header/footer size: 4바이트 */
#define DSIZE 8 /* Double word size: 8바이트 */
#define CHUNKSIZE (1 << 12) /* Extend heap by this amount (bytes): 1024개 워드 */
#define MAX(x, y) ((x) > (y) ? (x) : (y))
/* 블록 사이즈와, 할당/가용 비트를 워드 안에 packing */
#define PACK(size, alloc) ((size) | (alloc))
/* 주소 p에 담긴 워드를 읽고 쓰기 */
#define GET(p) (*(unsigned int *)(p)) // 워드 읽기
#define PUT(p, val) (*(unsigned int *)(p) = (val)) // 워드 쓰기
/* 주소 p에 담긴 블록 사이즈와 할당/가용 비트를 읽기 */
// 사이즈 값을 읽기 위한 비트 연산 & 할당/가용 비트를 읽기 위한 비트 연산
#define GET_SIZE(p) (GET(p) & ~0x7)
#define GET_ALLOC(p) (GET(p) & 0x1)
// bp = 블록의 *데이터의 시작 부분을 가리키는 포인터
// 헤더는 = 데이터 영역 - 1워드
#define HDRP(bp) ((char *)(bp)-WSIZE)
// 풋터 = bp + 전체사이즈 - 더블워드(풋터,헤더)
#define FTRP(bp) ((char *)(bp) + GET_SIZE(HDRP(bp)) - DSIZE)
/* 블록을 가리키는 포인터 bp가 주어졌을 때, 다음 블럭과 이전 블럭의 주소를 계산 */
#define NEXT_BLKP(bp) ((char *)(bp) + GET_SIZE(((char *)(bp)-WSIZE)))
#define PREV_BLKP(bp) ((char *)(bp)-GET_SIZE(((char *)(bp)-DSIZE)))
// 프로토타입 선언
static void *coalesce(void *bp);
static void *extend_heap(size_t words);
static void place(void *bp, size_t asize);
static void *find_fit(size_t asize);
// static 전역 변수 선언
static char *heap_listp; // 항상 힙의 프롤로그 블록을 가리킬 포인터 변수
static char *findp; // next-fit을 위한 변수
mm_init함수
/* 말록 패키지 초기화 */
int mm_init(void)
{
// 4 워드를 가져와서 빈 가용리스트를 만들도록 초기화
if ((heap_listp = mem_sbrk(4 * WSIZE)) == (void *)-1)
return -1;
PUT(heap_listp, 0); /* 정렬을 위한 unused 패딩 */
PUT(heap_listp + (1 * WSIZE), PACK(DSIZE, 1)); /* 프롤로그 헤더 */
PUT(heap_listp + (2 * WSIZE), PACK(DSIZE, 1)); /* 프롤로그 풋터 */
PUT(heap_listp + (3 * WSIZE), PACK(0, 1)); /* 에필로그 헤더 */
heap_listp += (2 * WSIZE);
/* CHUNKSIZE 바이트의 가용 블록으로 비어있는 힙을 확장함 */
// 청크사이즈(4096바이트)/워드사이즈(4바이트) = 워드개수(1024바이트)
if (extend_heap(CHUNKSIZE / WSIZE) == NULL)
return -1;
findp = (char *)heap_listp; // next-fit 탐색을 위한 findp
return 0;
}
/* 새 가용 블록으로 힙을 늘리기 */
static void *extend_heap(size_t words)
{
char *bp; // char 자료형을 쓰는 이유: 1바이트면 주소를 읽기 충분해서
size_t size;
/* 정렬을 유지하기 위해 짝수 개의 워드를 할당 */
// 워드를 2로 나눠서 홀수면 워드 한개 더 추가
size = (words % 2) ? (words + 1) * WSIZE : words * WSIZE;
// sbrk 함수로부터 힙 영역 더 못 받으면 NULL 반환
if ((long)(bp = mem_sbrk(size)) == -1)
return NULL;
// 새로 받은 가용 블럭의 헤더/푸터 + 에필로그 헤더를 초기화
// bp는 이전의 힙 메모리의 에필로그 블록 다음을 가리키게 됨
PUT(HDRP(bp), PACK(size, 0)); /* Free block header, 할당비트 0 */
PUT(FTRP(bp), PACK(size, 0)); /* Free block footer, 할당비트 0 */
PUT(HDRP(NEXT_BLKP(bp)), PACK(0, 1)); /* New epilogue header, 크기 0, 할당비트 1 */
/* 이전의 힙의 마지막 블럭이 가용 블록인 경우, 연결시켜주기 위해 연결 함수 호출 */
return coalesce(bp); // 통합된 블럭의 블럭 포인트 반환
}
/* 경계 태그 연결하는 함수. 합쳐진 블락의 bp를 반환함. */
static void *coalesce(void *bp)
{
size_t prev_alloc = GET_ALLOC(FTRP(PREV_BLKP(bp)));
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t size = GET_SIZE(HDRP(bp));
if (prev_alloc && next_alloc)
{ /* Case 1: prev와 next 모두 할당 */
findp = bp; // next-fit 코드 때문에 추가
return bp;
}
else if (prev_alloc && !next_alloc)
{ /* Case 2: prev는 할당, next는 free */
size += GET_SIZE(HDRP(NEXT_BLKP(bp)));
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
}
else if (!prev_alloc && next_alloc)
{ /* Case 3: prev는 free, next는 할당 */
size += GET_SIZE(HDRP(PREV_BLKP(bp)));
PUT(FTRP(bp), PACK(size, 0));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
else
{ /* Case 4: prev, next 모두 free */
size += GET_SIZE(HDRP(PREV_BLKP(bp))) +
GET_SIZE(FTRP(NEXT_BLKP(bp)));
PUT(HDRP(PREV_BLKP(bp)), PACK(size, 0));
PUT(FTRP(NEXT_BLKP(bp)), PACK(size, 0));
bp = PREV_BLKP(bp);
}
findp = bp; // next-fit 코드 때문에 추가
return bp;
}
mm_malloc, next fit 정책을 사용하는find_fit함수
/*
* mm_malloc - brk 포인터를 증가시킴으로서 블록을 할당.
* 항상 정렬의 배수의 사이즈를 가진 블럭을 할당함.
*/
void *mm_malloc(size_t size)
{
size_t asize; /* Adjusted block size for 더블워드 정렬, 헤더/풋터 */
size_t extendsize; /* Amount to extend heap if no fit */
char *bp;
/* Ignore spurious requests */
if (size == 0)
return NULL;
/* 블록 사이즈를 정렬 요건 맞추고, 헤더/풋터 공간을 확보하기 위해 조절 */
if (size <= DSIZE) // 만약 요청 크기가 2 워드(8 byte)랑 같거나 작으면
{
asize = 2 * DSIZE; // 최소 4 워드(16 byte) 블록으로 줌
}
else // 요청 크기가 2 워드 이상
{
// 오버헤드 바이트를 추가하고, 가까운 8의 배수로 반올림
asize = DSIZE * ((size + (DSIZE) + (DSIZE - 1)) / DSIZE);
}
/* Search the free list for a fit */
if ((bp = find_fit(asize)) != NULL) // fit하는 블록이 있을 때
{
place(bp, asize); // bp가 가리키는 블록에 해당 사이즈 할당
findp = bp; // next-fit 마지막 검색 지점 설정
return bp;
}
/* 맞는 가용 블럭이 없으면(No fit)
메모리를 더 받아서 힙을 새로운 가용 블럭으로 확장하고,
요청한 블록을 새 가용블럭에 배치 */
extendsize = MAX(asize, CHUNKSIZE);
if ((bp = extend_heap(extendsize / WSIZE)) == NULL)
return NULL;
place(bp, asize); // 필요한 경우 블록 분할
findp = bp; // next-fit 마지막 검색 지점 설정
return bp;
}
// next-fit search
static void *find_fit(size_t asize)
{
char *bp = findp;
// 에필로그 블록에 도달할 때까지 블록 탐색
for (bp = NEXT_BLKP(bp); GET_SIZE(HDRP(bp)) != 0; bp = NEXT_BLKP(bp))
{
// 가용 블록이고, 필요한 사이즈와 같거나 클 때 해당 블록 포인터 반환
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
findp = bp;
return bp;
}
}
// 에필로그 블록에 도달했는데 못 찾은 경우, 프롤로그 블록부터 다시 탐색
for (bp = heap_listp; bp < findp;)
{
bp = NEXT_BLKP(bp);
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
findp = bp;
return bp;
}
}
return NULL; /* No fit */
}
// 가용 블록의 시작 부분에 조절한 사이즈(asize)의 요청한 블록(bp)을 배치하고
// 헤더, 풋터 지정
// 나머지 부분의 크기가 최소 블록 크기와 같거나 큰 경우에만 분할함
static void place(void *bp, size_t asize)
{
size_t fsize = GET_SIZE(HDRP(bp)); // 가용 블럭의 전체 사이즈
// 가용 블럭의 사이즈와 배치하고자 사이즈의 차이가 워드 4개보다 같거나 크면 -> 분할 O
if ((fsize - asize) >= (2 * DSIZE))
{
PUT(HDRP(bp), PACK(asize, 1));
PUT(FTRP(bp), PACK(asize, 1));
bp = NEXT_BLKP(bp);
PUT(HDRP(bp), PACK(fsize - asize, 0));
PUT(FTRP(bp), PACK(fsize - asize, 0));
}
// 가용 블럭의 사이즈와 배치하고자 사이즈의 차이가 워드 4개보다 작으면 -> 분할 X
else
{
PUT(HDRP(bp), PACK(fsize, 1));
PUT(FTRP(bp), PACK(fsize, 1));
}
}
- 추가) first fit 정책을 사용하는
find_fit함수
// 묵시적 가용 리스트에서 first fit 검색을 수행하는 함수
static void *find_fit(size_t asize)
{
void *bp;
// 프롤로그 블록부터 맞는 블록 탐색
for (bp = heap_listp; GET_SIZE(HDRP(bp)) > 0; bp = NEXT_BLKP(bp))
{
if (!GET_ALLOC(HDRP(bp)) && (asize <= GET_SIZE(HDRP(bp))))
{
return bp;
}
}
return NULL; /* 맞는 fit이 없는 경우 */
}
mm_free함수
/*
* mm_free - Freeing a block does nothing.
* 블럭을 프리시키고 인접한 가용 블록과 경계 태그 연결함
*/
void mm_free(void *bp)
{
size_t size = GET_SIZE(HDRP(bp));
// 헤더와 풋터의 할당/가용 비트를 0으로 바꿈
PUT(HDRP(bp), PACK(size, 0));
PUT(FTRP(bp), PACK(size, 0));
coalesce(bp);
}
mm_realloc함수
// 인자로 받은 bp의 데이터를 새로운 사이즈의 블럭에 재할당
void *mm_realloc(void *bp, size_t size)
{
size_t old_size = GET_SIZE(HDRP(bp));
size_t new_size = size + DSIZE;
if (new_size <= old_size)
{
return bp;
}
else
{
size_t next_alloc = GET_ALLOC(HDRP(NEXT_BLKP(bp)));
size_t current_size = old_size + GET_SIZE(HDRP(NEXT_BLKP(bp)));
// next block이 Free이고, old, next block의 사이즈 합이 new_size보다 크면 바로 합쳐서 쓰기
if (!next_alloc && current_size >= new_size)
{
PUT(HDRP(bp), PACK(current_size, 1));
PUT(FTRP(bp), PACK(current_size, 1));
return bp;
}
// 아닌 경우 새로운 block malloc으로 할당 받아 데이터 복사
else
{
void *new_bp = mm_malloc(new_size);
place(new_bp, new_size);
memcpy(new_bp, bp, new_size); // old_bp로부터 new_size만큼 new_bp로 복사
mm_free(bp);
return new_bp;
}
}
}
'크래프톤정글 > TIL & WIL' 카테고리의 다른 글
| 백준 9663번 N-Queen 파이썬 (1) | 2023.01.19 |
|---|---|
| 크래프톤정글 7주차; WIL - 웹 서버 개발 일지 (0) | 2022.12.14 |
| 크래프톤정글 6주차; TIL - 백준 9020 골드바흐의 추측 재도전 (0) | 2022.12.08 |
| 크래프톤정글 5주차; TIL 2 - Red-Black Tree의 insert, delete 연산, C typedef, enum 활용, 메모리에서 스택과 힙의 자라나는 방향 (0) | 2022.12.03 |
| 크래프톤정글 5주차; TIL 1 - C 프로그래밍, 함수 호출 방식, C언어 extern, static 변수 (0) | 2022.12.03 |