재미있는 유튜브 영상을 봤습니다. 기술면접의 인터뷰 문제였는데, 마침 최근 컴퓨터구조 스터디에서 다루었던 내용과 연결되는 부분이 있어서 제 답변을 적어보고자 합니다.
문제는 단순합니다.
Write a program in C that can compute if the stack grows "up or down"
다음 함수를 만들어야 한다고 생각하겠습니다(stdbool.h를 참조하는 것을 잊지 마세요!):
/*
* bool stack_grows_up(void)
* returns true if stack grows up, false if not
*/
bool stack_grows_up(void);
문제에서 말하는 스택을 정의할 필요가 있을 것 같습니다. 여기서의 스택은 후입선출(Last In - First Out) 방식을 갖는 자료구조로서의 스택이 아니라, 프로그램이 실행될 때 프로시저 각각이 갖는 Stack Frame에서의 스택을 의미합니다. 어느 프로시저(함수)가 실행될 때, 프로시저 각각은 지역 변수를 스택 영역에 저장합니다. 함수가 호출될 때 마다 새로운 스택 프레임을 생성하고(함수 프롤로그), 함수의 실행이 끝나면 스택 프레임을 정리한 후 호출자(Caller)로 리턴합니다(함수 에필로그).
이렇게 스택에 프레임을 만들어 자료를 저장하고 할당 해제하는 과정을 함수를 호출 할 때 마다 진행하게 됩니다. 덕분에 재귀함수같이 같은 함수를 반복해서 실행하는 경우에도, 매 번 다른 스택 프레임을 가지고 있기 때문에 간섭 없이 실행될 수 있습니다. 이러한 특성을 재진입성(Reentrance)을 보장한다고 합니다.
일반적으로 ARM 아키텍쳐나 x86-64 아키텍쳐의 경우 스택은 높은 주소에서 아래 주소로 자란다고 표현합니다. 실제로 함수의 프롤로그 과정을 어셈블리어로 살펴보면 스택의 탑을 가리키는 rsp 포인터에서 지역변수의 크기만큼 빼 주어 메모리를 할당하고, 에필로그 과정에서는 뺀 만큼 다시 더해 메모리를 할당 해제합니다. 하지만 모든 아키텍쳐에서 이와 같이 스택이 높은 주소에서 아래 주소로 자라는 것은 아닙니다. 대표적으로 8051 프로세서의 경우 스택이 아래에서 위로 자라는 방식을 선택하고 있습니다. 이러한 구조는 ABI에서 정의됩니다.
참고) 영상의 댓글에서 사람들이 지적한 것과 같이, C언어 표준은 스택 메모리를 이용할 것을 명시하지 않습니다. 따라서 스택이 자라는 방향을 알아내는 C 프로그램은 본질적으로 플랫폼-의존적일 수 밖에 없습니다 :(
스택 프레임은 지역 변수들을 담기 위해 할당되기에, 지역 변수들을 선언하고 그 주소들을 비교한다면 스택이 어떤 방향으로 자라는지를 쉽게 판단할 수 있을 것입니다. 지역 변수 a와 b를 선언해 스택에 푸시되도록 만들고, 만약 나중에 푸시된 b의 주소가 더 낮은 주소라면 스택은 위에서 아래로 자란다고 판단하면 됩니다. 이를 위해서는 다음과 같은 코드를 만들 수 있습니다.
bool stack_grows_up(void)
{
int a = 0, b = 1;
return &a < &b;
}
인터뷰 문제라고 생각하고, 조금 더 구체적으로 적어봅시다.
auto여야만 합니다. 또한, 컴파일러 최적화에 의해 이 변수들이 스택이 아닌 레지스터에 담기는 것도 바라지 않습니다. 따라서 volatile 을 이용해 최적화에서 제거해줄 수 있습니다.물론, 기본적으로 지역변수는 auto 클래스를 가지므로 생략 가능합니다. 그냥 아는척좀 해봤어요 헤헤...
void *로 캐스팅해 자료형에 대한 정보 없이 비교하도록 만들 수 있습니다.