Week06 동적할당(malloc lab 구현)

역대급으로 밤새면서 한 말록........ 디버깅을 이렇게까지 해본건 처음인 듯. 일요일 저녁에 구현 끝났는데 수요일 오후에 해결함.. 결국 다 풀진 못했지만 스스로 해냈다는 데에서 뿌듯하긴 했다!

트러블슈팅

• if문 내에서 변수 할당하는 새로운 문법을 알았다. if((x=y)==z)라고 쓰면 x에y를 할당한 뒤 z와 비교한다. 괄호는 빼먹으면 안된다.
• 매크로 함수를 정의할 때는 인자에 괄호를 감싸주는게 좋다. 들어오는 값에 따라 연산 우선순위가 달라져 예상치 못한 값이 될 수 있기 때문. 그래서 별거 없는데도 GET 함수를 따로 만든 것이었다. 매번 괄호며 우선순위 신경쓰지 말라고.
• 구현 후 실행하려고 했더니 optimized out 에러가 났다. 찾아보니 컴파일 과정에서의 최적화 문제라고 해서 최적화 단계를 낮췄더니 해결되었다. 참고 링크
• 매크로의 ALIGN은 원하는 크기를 넣으면 8 이하 자리 숫자를 버려서 반올림해주는게 맞다. 그랬다가 버림때문에 넣은 값보다 크기가 작아지면 안되니까 DSIZE-1인거고.
  그럼 SIZE_T_SIZE는? size_t의 크기만큼을 align 하는데, size_t를 까보면 unsigned long형이다. 지금 하는 32bit에서는 그게 4바이트이기 때문에 SIZE_T_SIZE가 8바이트가 되는거고 64비트 시스템에서는 16바이트가 될 것이다. 결국 DSIZE만큼인데, 운영체제가 바뀔 때 마다 DSIZE의 상수값을 바꿔줘야 하니까 DSIZE를 자동 계산하도록 한 것으로 보인다.
• explicit 구현할 때, adress ordering으로 하든 LIFO로 하든 free할 때의 복잡도는 크게 달라지지 않는다. adress ordering은 linked list의 앞뒤가 물리적으로 인접한 블록이기때문에 그걸로 coalesce하면 되고, LIFO는 링크드리스트의 predecessor와 successor로 이어진 블록이 물리적으로 인접한 블록은 아니기 때문에 implicit에서 했던 것처럼 HDRP(PREV_BLKP()) 해서 찾으면 되는 것이었음.
  => 그러면 adress ordering을 왜 쓰느냐하는 것은 외부단편화를 줄일 수 있기 때문이다. adress ordering은 할당해줄 때 주소값이 작은것부터 확인해서 주기 때문에 블록이 부족해서 extend를 할 때 쯤에는 제일 마지막 블록이 남아있을 확률이 높다. 그럼 extend한 뒤에 coalesce할 수 있음. 근데 LIFO는 마지막으로 free한것부터 다시 할당해주기 때문에 할당 순서도 뒤죽박죽이고 extend할 때 제일 마지막 블록이 남아있으리란 보장이 전혀 없음. 그럼 extend 한 뒤에 coalesce할 수 없기 때문에 외부단편화가 발생하게 되는 거임.
• 1조 디버깅을 도와줬다.
  implicit에서 find_fit의 while문 조건을 현재 bp의 푸터+WSIZE 위치의 사이즈를 가져오면 그게 에필로그에서 GET_SIZE한 것이기 때문에 0이 될거라고 생각했나보다. 그게 0이 되면 while문을 빠져나가서 NULL을 리턴하기. 근데 이러면 메모리가 부족해지는 이유는 맨 처음 init하고 블록이 하나만 있을 때는 무조건 while문의 조건이 0이 되기 때문에 NULL을 리턴하게 된다. 그럼 맨 처음 할당은 무조건 extend를 한번 하고 시작하게 되는거! 그러면 extend한 뒤에도 coalesce를 하기 때문에 같은 위치의 bp를 리턴하게되고 그럼 또 find를 못 찾기 때문에 무한 extend->find->extend...가 되는거 아닌가? 했는데 한번 extend를 한 뒤에는 find를 다시 하지 않고 바로 place를 해버리기 때문에 그건 아니었다. 대신 발견한 문제는 while문 첫번째 조건이 size<asize일 때 안됐던 것은 while문이 앞에서부터 돌면서 확인하는데, 지금 확인하는 블록은 asize보다 작지만 그 뒤의 블록은 asize보다 클 수 있다는 점이었다. 그러면 그 뒤의 블록을 할당하면 되는 건데 그게 안되고 while문을 빠져나가서 NULL을 리턴해버리는 문제였다.
• HDRP가 bp를 char 타입으로 변경해서 연산하는 이유가 뭔가 싶었는데 겨우 알아냈다. 포인터에 정수 사칙연산은 포인터가 가리키는 타입만큼 정수에 곱해서 이루어진다. 근데 우리는 WSIZE만큼 더하거나 빼고 싶은데 이건 바이트 단위이기 때문에 bp를 바이트 단위만큼 연산시키기 위해 char 타입으로 바꾸는 것! 그럼 헤더가 사실은 int 정보를 가지고 있는데 char 타입으로 리턴하는게 괜찮냐 하면은 사실은 안괜찮다. 포인터를 제대로 쓰려면 unsigned int* 타입으로 다시 바꿔줘야 함. 근데 우리가 지금까지 괜찮았던 건 HDRP랑 FTRP를 항상 GET_SIZE랑 GET_ALLOC 안에서 쓰는데 여기서 GET함수를 통해 타입을 바꿔주고 연산하기 때문이었다. 사실은 그냥 넣어준 걸로 보이는 식들도 다 PUT을 통해 넣어주기 때문에 괜찮은거였음.
• 주소값을 넣어두고, 거기의 값을 char 타입 변수에 받아와서 보려고 하면 1바이트만 읽어오기 때문에 이상한 값이 나온다. 주소는 넣어줄때도 변수로, 받아올때도 unsigned int로 해야 함.
• 형변환은 너무너무 중요하다!! 주소값에 +-해서 움직일 때는 우리가 WSIZE, DSIZE만큼 움직이는 게 바이트대로 움직이는 것이기 때문에 char로 변환해서 움직여야 한다. arr+i하면 arr의 타입*i만큼 움직여서 i번째 주소를 가져오는 것과 같은 원리. 근데 그걸 주소값으로 저장하고 싶거나 불러오고 싶으면 unsigned int*형으로 변환해야 한다. 심지어 리턴할때는 void형으로 리턴해야 함!
• simple segregated free lists 방식 진행하면서 엄청 헤멨다. 처음에는 8~15, 16~31, 이렇게 나누려고 했는데 책 읽어보니까 simply segregated는 쪼개지도 않고 합치지도 않는 방식인거다. 17 해제하면 16~31을 블록에 넣어주는 식. 그러면 헤더/푸터 필요없고 initial block은 패딩이랑 에필로그만 있으면 되나?라고 생각했는데 17을 할당해주려고 하면 헤더가 있어야 크기를 알 수 있는데 책에는 최소 크기가 헤더 없이 1워드라고 나와있었다. 그러면 헤더랑 successor가 같은 위치를 공유하면서 쓰는 건가? 할당돼있을 때는 헤더고 free일 때는 successor로? 요청받으면 free 블록 중 나보다 크거나 같은 애 찾아서 쪼개지 말고 할당하는 방식으로. 근데 생각해보니까 그러면 처음에 extend한걸 첫번째 요청에 통채로 줘버리고 없으니까 또 extend하고 또 줘버리고 무한 반복... 이거 이상한데? 싶어서 chuncksize를 현재 요청받은 같은 사이즈로 다 나눠주기로 했다. 엄청 많이 찾아봤는데 이게 simple segregate인듯.
  근데 다시 의문...... 2^12보다 큰 블록은 다 2^12~무한 클래스에 들어가는데 그럼 거기는 크기가 뒤죽박죽인 블록이 다 들어가 있네?? 그럼 거기 순회하면서 찾아야 하고 그럼 헤더가 필요한데? 싶어서 크기 클래스를 우리의 최대 사이즈인 2^31(2메가)까지 다 나누기로 했다. 그랬더니 최대 힙 사이즈를 20메가에서 21메가로 늘려야 늘려야만 통과한다. 근데 이건 realloc이 6만 얼마를 요구하기 때문에 어쩔 수 없는 듯? 그냥 물리적으로 안되는거임. 좀 되게 하려면 클래스 리스트를 동적으로 할당받아서 2^3~2^31까지 미리 만들어놓지 않고 새로운 요청이 들어올 때 마다 클래스를 동적으로 만들어야 하는데 말록을 구현하면서 말록을 쓴다는건 좀 이상한 듯. simple로 76점 나왔으니 이만 만족!
• explicit이 안됐던 이유는 coalesce에서 연결을 잘못 해줬던 거였다. 뭔가 계속 안될때는 반례를 보면서 찾지 말고 로직을 검토하자. 민규오빠 말이 맞았음. 어차피 로직이 틀린건데 반례만 고치면 다른 반례가 또 나오고 나중에는 코드가 덕지덕지 누더기가 된다.
  그냥 링크드리스트 그려가면서 어디랑 어디 연결하는건지 차분히 보니까 뒷 블록이랑 합쳐질 때 연결을 뒷 블록 주소로 넣어줬다는걸 발견했다. 이거 고쳤더니 점수 나옴! 이 때는 54점 나왔다가 find함수를 매번 coalesce 들어갈 때 마다 실행하지 말고 if문 안에 넣어서 네 경우 중 한번만 실행하도록 했더니 속도 때문인지 10점이 올랐다.