12주차 'linked list 구현' 문제 관련 질문글

[JJong2003]

안녕하세요? malloc() - free() 에 대해 한 가지 질문이 있어 글을 작성합니다.
아직 실습 과제가 진행 중인 관계로 전체 코드를 제공해도 괜찮을지 몰라서 일부 문제가 있는 코드만 제공하는 점 양해바랍니다.

struct node {
    int value;
    struct node *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
( loop when v!=0 )
        // create new node
        struct node *new_node = malloc(sizeof(struct node));
...
...

    // print answer
    print_linked_list(head.next);

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

문제 상황
현재 free_nodes() 함수에서 자꾸만 segmentation fault가 발생하고 있습니다.
그 이유는 이미 해제된 메모리가 free()에 다시 사용되면서 생기는 것이라고 판단했고, 실제로 hackerrank에 free_nodes() 함수에 주석 처리만 하면 바로 통과가 되고 있습니다.

질문
아무래도 해커랭크에서는 매우 많은 양의 input 을 넣음으로써 malloc이 이미 할당 된 메모리를 가져다 사용하거나 하는 등의 이슈가 있는 것 같습니다.

1. 대량의 동적 메모리를 생성하면 이미 제공한 메모리malloc()된 블록이 겹쳐질 수도 있는 것인가요?
2. 재귀적인 방법으로 free()를 사용하는 것에 문제가 있는 것인지도 궁금합니다.
3. 이외의 다른 이유가 있을까요?

대량의 input 제공이 제 local에서는 테스트 하기 어려운 관계로 제 생각이 맞는 것인지, 다른 이유가 있는 것인지 도움을 구해보고자 글을 남깁니다.

[HELLOOOOOOW]

안녕하세요, 01분반 조교입니다.

우선 학생이 생각한 대로 재귀함수를 사용해 발생한 문제가 맞는 것 같습니다.
단, 이미 free된 메모리를 다시 free 했기 때문에 발생한 문제는 아닐 가능성이 높습니다.
학생이 해커랭크에 제출한 코드를 봤는데, free 뿐 아니라 print 함수도 처음에 재귀로 구현하셨습니다.
재귀함수로 구현했을 때, 입력이 1,000,000개가 들어오면 출력 또는 free하는 재귀함수가 1,000,000번 불리게 됩니다.
매 호출 시 새로운 스택 프레임이 메모리에 생성되고, 생성된 스택 프레임이 리턴되어 사라지지 못하고,
또 새로운 스택 프레임을 생성하는 방식으로 스택이 호출된 함수의 스택 프레임으로 가득 차게 됩니다.
해당 문제의 메모리 제한은 512MB로 재귀함수를 사용해 대량의 데이터를 처리하면 주어진 메모리 공간을 초과하여 segmentation fault가 발생할 수 있습니다.

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

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

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

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

[JJong2003]

답변 잘 읽었습니다. 그리고 스택 프레임에 의한 것이라는 점에서 큰 영감을 받은 것 같습니다.
"많은 양의 입력 때문에 노드를 생성(힙 영역)과 함수 호출(스택 영역)에 의해 메모리가 부족하다"라고 이해했습니다.
하지만 이것이 문제라면 앞에 호출한 print_linked_list() 함수도 문제가 일어나야 할 것 같습니다.

문제 상황
print_linked_list() 또한 마찬가지로 재귀함수로 호출하고 있습니다.

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

만약 '재귀호출 + 많은 양의 노드'로 인한 메모리 less 가 문제라면 위 호출에서 먼저 segmentation fault가 발생했어야 한다고 생각합니다.
하지만 여기선 문제가 나타나지 않았고, 뒤에 호출하는 free_nodes(head.next); 부분에서 문제가 발생했습니다.

질문
저는 이것이 꼬리재귀와 머리재귀의 차이에서 약간의 메모리 차이에서 나타난 erorr 라고 생각합니다. 혹시 다른 이유가 있을까요?

[HELLOOOOOOW]

학생의 의견이 맞는 것 같습니다.

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

코드를 위처럼 임의로 수정해서 꼬리 재귀가 아닌 방식으로 print_linked_list함수를 호출했을 때 segfault가 발생합니다.
기존에 작성한 free_nodes함수도 꼬리 재귀가 아니었기 때문에 발생한 문제로 추정됩니다.

https://stackoverflow.com/questions/33923/what-is-tail-recursion
꼬리 재귀를 사용하면 재귀 함수를 호출할 때 새로운 스택프레임이 생기지 않고 기존 스택프레임을 재활용해 사용합니다.
따라서 이번 문제처럼 대량의 데이터를 처리하려면 꼬리 재귀로 잘 구현하거나, 일반적인 반복문을 통해 처리하는 것을 추천합니다.

[JJong2003]

감사합니다. 덕분에 큰 도움 됐습니다.