[C] 스택의 방향을 판단하는 코드 작성하기
문제는 단순합니다.
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);
C
복사
0. 스택이란
문제에서 말하는 스택을 정의할 필요가 있을 것 같습니다. 여기서의 스택은 후입선출(Last In - First Out) 방식을 갖는 자료구조로서의 스택이 아니라, 프로그램이 실행될 때 프로시저 각각이 갖는 Stack Frame에서의 스택을 의미합니다. 어느 프로시저(함수)가 실행될 때, 프로시저 각각은 지역 변수를 스택 영역에 저장합니다. 함수가 호출될 때 마다 새로운 스택 프레임을 생성하고(함수 프롤로그), 함수의 실행이 끝나면 스택 프레임을 정리한 후 호출자(Caller)로 리턴합니다(함수 에필로그).
이렇게 스택에 프레임을 만들어 자료를 저장하고 할당 해제하는 과정을 함수를 호출 할 때 마다 진행하게 됩니다. 덕분에 재귀함수같이 같은 함수를 반복해서 실행하는 경우에도, 매 번 다른 스택 프레임을 가지고 있기 때문에 간섭 없이 실행될 수 있습니다. 이러한 특성을 재진입성(Reentrance)을 보장한다고 합니다.
일반적으로 ARM 아키텍쳐나 x86-64 아키텍쳐의 경우 스택은 높은 주소에서 아래 주소로 자란다고 표현합니다. 실제로 함수의 프롤로그 과정을 어셈블리어로 살펴보면 스택의 탑을 가리키는 rsp 포인터에서 지역변수의 크기만큼 빼 주어 메모리를 할당하고, 에필로그 과정에서는 뺀 만큼 다시 더해 메모리를 할당 해제합니다. 하지만 모든 아키텍쳐에서 이와 같이 스택이 높은 주소에서 아래 주소로 자라는 것은 아닙니다. 대표적으로 8051 프로세서의 경우 스택이 아래에서 위로 자라는 방식을 선택하고 있습니다. 이러한 구조는 ABI에서 정의됩니다.
참고) 영상의 댓글에서 사람들이 지적한 것과 같이, C언어 표준은 스택 메모리를 이용할 것을 명시하지 않습니다. 따라서 스택이 자라는 방향을 알아내는 C 프로그램은 본질적으로 플랫폼-의존적일 수 밖에 없습니다 :(
1. 지역변수 비교하기
스택 프레임은 지역 변수들을 담기 위해 할당되기에, 지역 변수들을 선언하고 그 주소들을 비교한다면 스택이 어떤 방향으로 자라는지를 쉽게 판단할 수 있을 것입니다. 지역 변수 a와 b를 선언해 스택에 푸시되도록 만들고, 만약 나중에 푸시된 b의 주소가 더 낮은 주소라면 스택은 위에서 아래로 자란다고 판단하면 됩니다. 이를 위해서는 다음과 같은 코드를 만들 수 있습니다.
bool stack_grows_up(void)
{
int a = 0, b = 1;
return &a < &b;
}
C
복사
인터뷰 문제라고 생각하고, 조금 더 구체적으로 적어봅시다.
1.
여기서 변수 a, b는 스택 프레임에 담기길 바라는 변수들입니다. 이 경우 변수들의 storage class는 auto여야만 합니다. 또한, 컴파일러 최적화에 의해 이 변수들이 스택이 아닌 레지스터에 담기는 것도 바라지 않습니다. 따라서 volatile 을 이용해 최적화에서 제거해줄 수 있습니다.
물론, 기본적으로 지역변수는 auto 클래스를 가지므로 생략 가능합니다. 그냥 아는척좀 해봤어요 헤헤...
1.
C언어에서 포인터 연산은 자료형의 정보를 활용하고, 같은 배열의 원소가 아니면 연산 결과는 Undefined Behavior라고 정의합니다. 안전하게 두 자료 사이의 주소 비교를 하기 위해, void *로 캐스팅해 자료형에 대한 정보 없이 비교하도록 만들 수 있습니다.
수정한 코드는 다음과 같습니다.
bool stack_grows_up(void)
{
auto volatile int a = 0, b = 1;
return (void *) &a < (void *) &b;
}
C
복사
참고) 위 코드를 그냥 컴파일하면 다양한 보호기법 때문에 예상하지 못한 결과가 나올 수 있습니다. gcc에서는 -fno-stack-protector 옵션을 사용하면 정상적인 결과를 볼 수 있습니다.
2. 스택 프레임 사용하기
위의 접근은 컴파일러가 지역변수의 선언 순서대로 스택에 삽입한다라는 가정이 참일 때에만 올바르게 작동합니다. 컴파일러가 지역변수들을 스택 프레임에 어떤 순서를 넣는지 또한 Implementation-Define Behavior이므로, 위 코드는 올바르지 않은 결과를 반환할 수 있습니다. 실제로, x86-64에서 gcc 11.4로 위 코드를 실행했을 때 (stack protector 때문에) down이 아니라 up이라는 결과를 얻었습니다.
대신, 스택 프레임을 비교할 수 있습니다. 더 나중에 호출된 프로시저(함수)는 스택에 나중에 삽입되는 것이 보장됩니다. 따라서 지역변수를 만들고 그 포인터를 반환하는 함수를 만들고, 여기서 반환한 주소를 비교하면 스택이 어떤 방향으로 자라는지 알 수 있습니다. 코드는 다음과 같습니다.
void * stack_function(void)
{
auto volatile int b = 0;
return (void *) &b;
}
bool stack_grows_up(void)
{
auto volatile int a = 1;
void *b = stack_function();
return (void *) &a < b;
}
C
복사
참고) auto stroage class를 갖는 변수의 주소를 반환하는 것은 할당 해제된 변수의 포인터를 반환하는 것이기 때문에 Undefined Behavior의 가능성을 높입니다. 다만, 이 코드에서는 역참조하지 않고 단순히 주소 비교만 하기 때문에 문제는 없습니다.
3. inline assembly 이용하기
스택 프레임을 활용하기 위해 별도의 함수를 호출시키고 프레임에 저장된 변수를 비교하는 방식도 몇 가지 가정에 근거를 두고 있습니다.
1.
아키텍쳐의 ABI가 프로시저 호출 시마다 프레임을 새로 만들고, 스택에 푸시한다고 가정
2.
컴파일러가 인라인 최적화를 하지 않는다고 가정
특히, 2번 가정이 문제입니다. 만약 gcc에서 -O1으로 컴파일하면 최적화에 의해 stack_function을 콜한 후 리턴값을 비교하는 것이 아니라 인라인 함수로 처리되어 값이 담겨있는 것을 확인할 수 있습니다.
원래의 코드 (인라인 최적화 없음)
Dump of assembler code for function stack_grows_up:
0x00000000000011e5 <+0>: endbr64
0x00000000000011e9 <+4>: push %rbp
0x00000000000011ea <+5>: mov %rsp,%rbp
0x00000000000011ed <+8>: sub $0x20,%rsp
0x00000000000011f1 <+12>: mov %fs:0x28,%rax
0x00000000000011fa <+21>: mov %rax,-0x8(%rbp)
0x00000000000011fe <+25>: xor %eax,%eax
0x0000000000001200 <+27>: movl $0x1,-0x14(%rbp) // rbp - 0x14: a = 1
0x0000000000001207 <+34>: call 0x11a8 <stack_function>
0x000000000000120c <+39>: mov %rax,-0x10(%rbp) // rbp - 0x10: *b = stack_function()
0x0000000000001210 <+43>: lea -0x14(%rbp),%rax
0x0000000000001214 <+47>: cmp %rax,-0x10(%rbp) // &a > &b?
0x0000000000001218 <+51>: seta %al
0x000000000000121b <+54>: mov -0x8(%rbp),%rdx
0x000000000000121f <+58>: sub %fs:0x28,%rdx
0x0000000000001228 <+67>: je 0x122f <stack_grows_up+74>
0x000000000000122a <+69>: call 0x1060 <__stack_chk_fail@plt>
0x000000000000122f <+74>: leave
0x0000000000001230 <+75>: ret
End of assembler dump.
Plain Text
복사
최적화된 코드
Dump of assembler code for function stack_grows_up:
0x000000000000115b <+0>: endbr64
0x000000000000115f <+4>: movl $0x1,-0x8(%rsp)
0x0000000000001167 <+12>: movl $0x0,-0x4(%rsp)
0x000000000000116f <+20>: mov $0x0,%eax
0x0000000000001174 <+25>: ret
End of assembler dump.
Plain Text
복사
최적화로 인해 원하는 동작을 보지 못하게 되었습니다. 이런 상황을 방지하기 위해, 인라인 어셈블리를 활용할 수 있습니다. 물론 C 프로그램을 작성해라라는 문제에서 벗어나긴 하지만... 가장 확실한 방법입니다! 저는 gcc의 인라인 어셈블리를 사용하겠습니다.
스택을 지원하는 아키텍쳐라면 push 인스트럭션이 있을 것이니, 이것을 활용하겠습니다. 제 어셈블리 코드는 다음과 같이 구성됩니다.
1.
초기의 rsp 값을 저장
2.
임의의 값을 push
3.
푸시한 이후의 rsp 값을 저장
4.
푸시한 값을 pop해서 원상태로 복구
이때, pop 인스트럭션은 오퍼랜드로 레지스터나 메모리를 요구합니다. 여기서는 스크래치 레지스터(caller-saved register)인 r8을 이용하겠습니다.
인라인 어셈블리를 활용하여 작성한 코드는 다음과 같습니다.
bool stack_grows_up(void)
{
void *prev, *after;
__asm__ __volatile__ (
"mov %%rsp, %0;\\n"
"push $0;\\n"
"mov %%rsp, %1;\\n"
"pop %%r8;\\n"
: "=r" (prev), "=r" (after)
:
: "%r8"
);
return prev < after;
}
C
복사
이렇게 작성한 코드는 -O3(가장 높은 최적화 수준)으로 컴파일해도 형태가 유지됩니다.
Dump of assembler code for function stack_grows_up:
0x00000000000011a0 <+0>: endbr64
0x00000000000011a4 <+4>: mov %rsp,%rdx
0x00000000000011a7 <+7>: push $0x0
0x00000000000011a9 <+9>: mov %rsp,%rax
0x00000000000011ac <+12>: pop %r8
0x00000000000011ae <+14>: cmp %rax,%rdx
0x00000000000011b1 <+17>: setb %al
0x00000000000011b4 <+20>: ret
End of assembler dump.
Plain Text
복사
비록 gcc 컴파일러의 특정 기능에 의존해 작성한 코드이기는 하지만, 최적화 수준과 관련없이 (스택을 지원한다면) 어느 아키텍쳐에서나 안정적으로 실행될 수 있는 코드가 만들어졌습니다.
4. 정리
"스택이 어떤 방향으로 자라는지 확인하는 프로그램을 작성해라"라는 간단한 질문을 대답하는 과정에서 컴퓨터 구조와 C언어의 많은 것들을 복습할 수 있었습니다.
•
스택 프레임과 포인터 연산부터 시작해서
•
컴파일러 최적화가 어떻게 다른 코드를 생성할 수 있는지,
•
인라인 어셈블리를 이용해 정확한 코드를 실행하는 과정까지 다루어 보았습니다.
최근에 C언어 표준과 컴퓨터구조를 공부하면서, 왜 이런 저수준의 지식까지 필요한지 의문 가진적이 많았는데 나름의 답을 한 것 같아 기분이 좋네요!
