실습 12주차 segmentation fault

이번 실습의 문제는 struct를 활용한 linked list 구현하기였다.

---

실패

segmentation fault

계속해서 나타나는 segmentation fault. 이유가 뭘까

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct node {
    int value;
    struct node *next;
};

void print_linked_list(struct node *ptr) {
    if (ptr==NULL) return;
    printf("%d\n",ptr->value);
    print_linked_list(ptr->next);
}

void free_nodes(struct node *ptr) {
    if (ptr==NULL) return;
    free_nodes(ptr->next);
    free(ptr);
}

int main() {
    int v;
    
    struct node head = {-1, NULL};  // dummy
    struct node *next_node;

    for (;;) {
        // input
        scanf("%d", &v);
        if (v == 0) break;
        
        // create new node
        struct node *new_node = malloc(sizeof(struct node));
        new_node->value = v;
        new_node->next = NULL;
        
        // link
        next_node = head.next;
        head.next = new_node;
        new_node->next = next_node;
    }

    // print answer
    print_linked_list(head.next);

    //malloc free
    free_nodes(head.next);
    head.next = NULL;
    return 0;
}

결론부터 말하면 free_nodes 메서드에서 생긴 문제이다.
내가 만든 테케들로는 도저히 저 경우가 나오지 않아서, free_nodes 메서드를 주석처리 해놓고 제출하니, 결국 correct 결과를 얻을 수 있었다.
 
그렇다면 무엇때문에 생긴 문제였을까?
 
1. 스택프레임
2. 꼬리재귀 vs 머리재귀

---

스택프레임

동적 메모리 할당은 힙 메모리 영역에서 해줌.
재귀함수가 쌓이는 곳은 스택 메모리 영역임.
힙 영역과 스택 영역은 서로 다른 메모리 공간이지만, 충분히 많은 메모리를 사용하게 되면 서로 만나게 됨.

---

머리재귀

기본 조건에 의해 재귀의 끝에 도달하고, 돌아오면서 미뤄둔 할 일을 처리함.

---

꼬리재귀

할 일을 미리 다 해놓고 결과 반환

---

코드의 스택프레임 시각화

 
[ 힙 ////////////////////////////////////////////////// 스택 ]   malloc 동적 메모리 할당 시작
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]   print_linked_list(꼬리재귀) 시작
[ 힙 ////////////////////////////////////////////////// 스택 ]   printf() 를 먼저 하고, 재귀를 함.
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]
[ 힙 ////////////////////////////////////////////////// 스택 ]   print_linked_list(꼬리재귀) 종료
[ 힙 ////////////////////////////////////////////////// 스택 ]   free_nodes(머리재귀) 호출 시작
[ 힙 ////////////////////////////////////////////////// 스택 ]   재귀호출로 끝(ptr == NULL)에 
[ 힙 ////////////////////////////////////////////////// 스택 ]   도달 후 돌아오면서 free()
[ 힙 ////////////////////////////////////////////////// 스택 ]   
[ 힙 ////////////////////////////////////////////////// 스택 ]   하지만 끝까지 가지 못하면 free()를 못 해줌.
[ 힙 ////////////////////////////////////////////////// 스택 ]   Segmentation fault !
 
질의응답 내용
이 문제의 제한 메모리는 512MB 였고, segfault가 발생한 케이스는 입력이 1,000,000개 가량 된다고 설명해주셨다.
 
꼬리재귀를 사용하면 재귀 함수를 호출할 때 새로운 스택프레임이 생기지 않고 기존 스택프레임을 재활용하는 반면
머리재귀를 사용하면 재귀 함수를 호출할 때마다 스택프레임에 계속 스택이 쌓임. 그런데 free()는 해주지도 않고있으니 결국 할당 된 메모리 영역까지 침범해서 결국 메모리 초과가 발생함.

---

추가 질문에 대해 답변

1.대량의 동적 메모리를 생성하면 이미 제공한 메모리malloc()된 블록이 겹쳐질 수도 있는 것인가요?

malloc을 통한 메모리 할당은 운영체제에 의해 잘 관리되기 때문에 새로 할당받은 공간이 겹치기는 어렵습니다.
추가로 할당해줄 공간이 없으면 NULL을 리턴해 줍니다.
 

2.재귀적인 방법으로 free()를 사용하는 것에 문제가 있는 것인지도 궁금합니다.

재귀적인 방법으로 free를 사용하는 것은 상관없으나, 대량의 데이터를 처리하는 함수를 재귀함수로 구현하는 것은 위에서 얘기한 것처럼 위험합니다.