RB-Tree 구현 회고 - 실패하면 디버그 성공하면 리눅스 아닙니까!
실패하면 디버그 성공하면 리눅스 아닙니까!
안녕하세요 6주 차 RB-Tree 트리 생성 발표를 맡은 고웅입니다.
어쩌다 보니 2주 연속 오프닝을 맡게 되었습니다??
우선 저는 RB-Tree를 구현하며 가장 처음 만나게 되는 생성함수에 대한 발표를 맡았습니다.
너무 쉬운거 맡아서 날먹 하려고 하네?? 맞습! 아!👊(퍽!) 아닙니다. 😅
제가 트리 생성을 발표하려던 이유는 제가 겪었던 디버깅의 추억?을 소개 시켜드리기 위해서 이런 쉬운 주제를 냉큼 주웠습니다.
먼저 오늘 준비된 코드부터 보시죠
🔬구현 코드
rbtree *new_rbtree(void) {
rbtree *p = (rbtree *) calloc(1, sizeof(rbtree));
// TODO: initialize struct if needed
if (p == NULL) {
return NULL;
}
node_t *nil = (node_t *)calloc(1, sizeof(node_t));
if (nil == NULL) {
free(p);
return NULL;
}
nil->color = RBTREE_BLACK;
nil->key = 0;
nil->parent = NULL
nil->left = NULL
nil->right = NULL
p->nil = nil;
p->root = nil;
return p;
}모두 이 정도는 당연히 구현하셨을 겁니다.
근데 이상한 부분을 발견하셨나요? 만약 발견하셨다면 박수드리겠습니다. 👏
발견하지 못하셨더라도 괜찮습니다. 저도 처음에는 발견하지 못했거든요 🤕
nil->parent = NULL
nil->left = NULL
nil->right = NULL좀 더 확대를 했습니다. 바로 nil의 부모, 자식 노드들을 NULL로 초기화 했던 겁니다.
네? 뭐가 잘못된 거냐 고요? 네 문제는 없을지 모릅니다.
이렇게 해도 테스트는 통과하니까요
하지만 이 경우는 제가 모든 코드를 정상적으로 작성했다는 가정 아래 문제가 없습니다. 하지만 만약 당장 검증하기 어려운 생성과 삽입 코드에서 문제가 있는데 그걸 제대로 해결하지 못한 경우에는 어떻게 되나요?
네 겁나 고생합니다.🤕
처음 삭제 기능을 구현하던 때 전 날 밤 RB 트리 동영상을 여러 번 돌려보고 나서 필(feel) 받았다. 내일 바로 삭제 조져버리겠다는 자신감으로 다음 날 아침에 도착해 삭제 기능을 구현을 했지만 저는 네 조져지는 것은 저였습니다.
종료 코드 139 (interrupted by signal 11:SIGSEGV)(으)로 완료된 프로세스이 오류는 아주 흔하게 마주치는 세그멘테이션 오류입니다. 즉 코드에서 잘못된 메모리 주소에 접근했을 때 발생하는 오류입니다.
저는 이 오류가 발생한 것이 당연히 내가 삭제 구현을 잘 못 했겠지 하면서 몇 시간씩 디버그 하고 printf 여기저기 찍어가면서 어디서 문제가 있는지 확인했지만 오류 범위를 좁혀갈수록 의문에 빠졌습니다.
왜 틀린거지? 책에서도 같은 의미로 작성된 코드가 있고 인터넷 서치 후에 확인한 코드에도 같은 의미로 작성됐는데?? 🤔
그러다가 우연히 다른 개발자의 코드를 보다가 저의 코드를 보던 순간 nil의 부모, 자식 노드를 NULL로 설정하고 있는 것을 발견했습니다.
그리고 바로 nil로 바꿔보니 드디어 문제가 있던 코드가 문제는 모두 사라지고
다른 곳이 문제가 생기는 쌔드? 엔딩(해피 엔딩은 없어)을 맞이했습니다.
하지만 일단 몇 시간이나 괴롭히던 오류가 사라지니 나머지 수정은 매우 쉽게 넘어갔습니다.
그렇다면 무엇이 맞는 방법일까요?
레드-블랙 트리 구현에서 nil->left , nil->right , nil->parent 를 자기 자신 nil로 설정하는 것이 맞고 더 안전한 방식이라고 합니다.
if (node→left ≠ t→nil) 처럼 비교를 하고는 하는데 이때 운 없게도 t→nil의 자식 혹은 부모노드로 무엇인가 비교를 하는 로직이 있었다면 이때 nil이어야 하는데 NULL 이 오니 당연히 세그멘테이션 오류가 발생한 것이었습니다.
if (node->left->color == RBTREE\_RED) 만약 이렇게 코드를 작성한 경우 node(nil)→left == NULL 인 상황이 발생하면 이 줄에서 문제가 발생하는 것 입니다.
그럼 왜 맨 위에 코드 예시에 NULL을 쓴 코드는 문제없이 동작하고 있는 것이지?
그것은 코드가 온전히? 잘 구현되었기 때문일 수 있습니다.
그래서 아~ 그렇구나 하고 넘어가지 않고 실무에서 작성한 RB-Tree의 예시를 찾아보기로 결정했고 결국
그 코드를 확인해 봤습니다.
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/include/linux/rbtree.h
https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/lib/rbtree.c
위 코드는 리누스 토발즈의 전설적인 리눅스 코드의 일부입니다. 네 그리고 이 코드에서 nil 혹은 그와 비슷한 코드를 발견하지는 못했습니다.
그래서 이 부분은 GPT와 대화해 보니 우리가 자주 참고한 CLRS 스타일 즉 책의 설명은 안정성/일관성/교육 목적에서는 nil을 사용하여 논리 흐름에 초점을 둔 것에 비해
제가 처음 작성했던 코드는 성능/최소화/최적화를 중시하던 리눅스 커널의 방식(좋게 포장해서)인 것이었습니다.
결론
하지만 이번 구현을 통해 철저히 겪은 교훈은 나는 아직 전문가가 아니니 일단 안전한 이론을 채득하고 그걸 구현으로 완성하는 것이 더 우선이라는 것을 느꼈습니다.
물론 리눅스 커널처럼 구현하기 위해서는 모든 포인터 접근 전에 NULL 체크를 잘하고 작성이 되어야 할 것입니다.