Call Stack 이해하기

- 목차

 

* 소개

어떤 프로그램을 사용한다는 의미에 대해서 생각해 볼 필요가 있습니다.

예를 들어, 크롬같은 웹 브라우저를 사용한다거나 Spring 같은 서버를 실행시킨다거나 하는 행동들을 말이죠.

프로그램은 컴파일 과정을 거쳐 바이너리 파일이 되는데요.

우리가 흔히 아는 0과 1로 구성된 상태가 되어 CPU 에 의해서 인식될 수 있게 됩니다.
 
이러한 바이너리 상태의 프로그램이 실행 상태가 되면 프로세스라고 불립니다.
프로세스는 CPU 를 비롯한 컴퓨터 리소스에 의해서 순차적으로 실행되게 됩니다.
 
실행 방식은 여러 종류가 있습니다.
 
- Sequential Execution : 일반적인 실행입니다. Top-Down 방식으로 한 줄 씩 실행되는 방식
- Branching Execution : If-else 와 같은 조건식에 의한 실행 방식입니다.
- Thread Execution : Multi-Threaded 환경에서의 실행방식입니다.
- Function Call Execution : 함수 호출에 의한 실행 방식입니다.
그 외에도 여러가지가 있지만,
 
Call Stack 은 여러가지 프로세스의 실행 방식들 중 Function Call Execution 방식에서 사용되는 자료구조입니다.
 

* Call Stack 이란

Call Stack 은 프로그램의 실행을 위해 사용되는 Stack 자료구조입니다.
assembly code 에서 push, pop 등 과 같은 명령어가 존재하는데요.
push 와 pop 이 Call Stack 데이터를 추가하고 제거하는 명령어입니다.
 
예를 들어,
아래와 같은 sum 함수와 main 함수가 있다고 가정하겠습니다.
 

function sum (int a, int b) {

	int sum_result = a * b;

	return sum_result;
}

function main () {

	int a = 5;
	int b = 7;
    
	int result = sum(a, b);
    
    return;
}

 
위 코드를 assembly code 로 표현하는 아래와 같습니다.
( 문법적으로 정확한 assembly code 는 아니니 참고해주십쇼 )

_start:
    push 5              
    push 7              
    call sum			 

sum:
    push ebp            
    mov ebp, esp        

    mov eax, [ebp+8]    
    mov ebx, [ebp+12]   

    add eax, ebx        

    pop ebp             
    ret

 
위 내용을 요약하면 다음과 같습니다.
 
1. push 7

- 7 과 5 를 더하는 연산을 수행하기 위해 7 를 Call Stack 에 넣습니다.
 

call stack : 
[7]

 
2. push 5

- 7 과 5 를 더하는 연산을 수행하기 위해 5 를 Call Stack 에 넣습니다. 
 

call stack : 
[7, 5]

 
3. call sum

- call sum 의 memory address 를 Call Stack 에 넣습니다.
- call sum 의 memory address 를 return address 라고 부릅니다.
- 그리고 sum 함수를 실행하기 위해 sum 함수로 이동합니다.
- program counter 는 sum 함수의 시작 memory address 로 변경됩니다.
- program counter 는 실행 중인 code 의 memory address 를 저장하는 레지스터입니다.

call stack : 
[ 7, 5, return_address ]

program counter :
sum 함수의 memory address

 
4. push ebp

- ebp 는 Stack Frame 의 base pointer 를 저장하는 레지스터입니다.
- Stack Frame 은 이어질 글에서 살펴보도록 하겠습니다.
- 현 단계에서 "push ebp" 는 main function 의 base memory address 라고 이해하시면 됩니다.
 

call stack : 
[ 7, 5, return_address, main_function_memory_address ]

program counter :
sum 함수의 위치 주소 + 1 // sum 함수에서 1 line 이동

 

5. mov eax, [ebp+8]
 
- eax 저장소에 ebp+8 을 저장합니다.
- 참고로 ebp + 8 은 7 이 저장된 Call Stack 위치입니다.
- eax 는 범용적으로 사용되는 레지스터인데요. 데이터 1개를 임시로 저장할 수 있습니다.
- Stack 은 메모리 상에서 Top-Down 으로 데이터가 추가됩니다.
- 그래서 ebp (base pointer) 로부터 +4, +8, +12 와 같은 형식으로 Call Stack 에 쌓인 값에 접근할 수 있습니다.

 

call stack : 
[ 7, 5, return_address, main_function_memory_address ]

program counter :
sum 함수의 위치 주소 + 2 // sum 함수에서 2 line 이동

eax : 
7

 

6. mov ebx, [ebp+12]
- ebx 저장소에 ebp+12 을 저장합니다.

 

call stack : 
[ 7, 5, return_address, main_function_memory_address ]

program counter :
sum 함수의 위치 주소 + 3 // sum 함수에서 3 line 이동

eax : 
7

ebx : 
5

 

7. add eax, ebx
- 7과 5를 더합니다.
- "add eax, ebx" 는 두 레지스터의 합을 eax 인 첫번째 레지스터에 저장합니다.

 

call stack : 
[ 7, 5, return_address, main_function_memory_address ]

program counter :
sum 함수의 위치 주소 + 4 // sum 함수에서 4 line 이동

eax : 
12

ebx : 
5

 
8. pop ebp
- Call Stack 에 저장된 main function 의 memory address 를 꺼냅니다.
- 그리고 ebp 에 새롭게 저장합니다.
- sum 함수가 종료되기 때문에 sum 함수의 Stack Frame 이 아니라 main 함수의 Stack Frame 을 사용하게 됩니다.

 

call stack : 
[ 7, 5, return_address ]

program counter :
sum 함수의 위치 주소 + 5 // sum 함수에서 5 line 이동

eax : 
12

ebx : 
5

ebp : 
main_function_memory_address

 

9. ret

- Call Stack 에서 return address 를 pop 합니다.
- 그리고 return address 로 돌아감으로써 sum 함수를 종료하고 call sum 이후의 코드를 실행합니다.
 

call stack : 
[ 7, 5 ]

program counter :
return_address

eax : 
12

ebx : 
5

ebp : 
main_function_memory_address

 
 

* Stack Frame

Stack Frame 은 물리적인 관점과 논리적인 관점에서 이해해야하는 단위입니다.

 

먼저 논리적인 관점에서 Stack Frame 을 설명하겠습니다.

 

논리적인 관점에서 Stack Frame 은 Call Stack 을 논리적으로 나눈 단위입니다.
함수 당 하나의 Stack Frame 이 생성된다고 생각하시면 되는데요.

예를 들어, main 함수에서 sum 함수가 실행된다면

main 함수의 frame 와 sum 함수의 frame 이 생성되어 총 2개의 Stack Frame 이 생성될 수 있습니다.

 

재귀함수의 경우에는 하나의 함수가 내부적으로 자신을 호출하는 방식이기 때문에

하나의 함수더라도 Stack Frame 이 여러번 생성될 수 있습니다.

즉 실행 중인 함수마다 하나의 Stack Frame 이 생성된다고 이해하시면 됩니다.

 

Stack Frame 은 위의 예시처럼 push 와 pop 명령어를 통해서 연산에 필요한 값들이 추가됩니다.

 

물리적인 관점에서 보았을 때,

하나의 Thread 는 하나의 Call Stack 을 가집니다.

즉, 하나의 Stack 자료구조가 메모리 상에 존재하는데요.

모든 Stack Frame 은 하나의 Call Stack 위에 층층이 쌓이게 됩니다.

그래서 물리적인 관점에서 보았을 때, Stack Frame 은 물리적으로 나뉘어져 있지 않습니다.

연속적으로 나열되어있고, 이를 구분짓는 것이 ebp 라고 하는 base pointer 입니다.

 

Stack Frame 의 시작 메모리 주소가 base pointer 이며 스택 프레임마다 자신만의 base pointer 를 가집니다.

 

예를 들어보겠습니다.

 

main, a, b 함수가 있으며,

실행되는 구조는 main -> a -> b 입니다.

function main() {
	a();
}

function a() {
	b();
}

function b() {
	// nothing.
}

 

이를 assembly code 로 표현하면 아래와 같습니다.

 

_start:
    call a

a:
    push ebp
    mov ebp, esp
    
    call b
    
    mov esp, ebp
    pop ebp
    ret
    
b:
    push ebp
    mov ebp, esp
    
    mov esp, ebp
    pop ebp
    ret

 

1. call a, in main function

- a 함수를 호출합니다.

- main 함수의 return address 를 Call Stack 에 저장합니다.

 

Call Stack : 
[
main function return address
]

program counter : 
a 함수의 Staring memory address

ebp :
main function base pointer

esp:
main function stack frame base pointer + 1

 

2. push ebp, in a function

Call Stack : 
[

main function return address,
main function stack frame base pointer 

]

program counter : 
a 함수의 Staring memory address + 1

ebp :
main function base pointer

esp:
main function stack frame base pointer + 2

 

 

3. mov ebp, esp in a function

- 현재 Stack Pointer 를 ebp 에 저장합니다.

- Stack Pointer 는 자동으로 increment 되는데, 현재 Stack Pointer 값이 a 함수의 새로운 base pointer 가 됩니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer 

]

program counter : 
a 함수의 Staring memory address + 2

ebp : 
a function stack frame base pointer

esp:
main function stack frame base pointer + 3
a function stack frame base pointer

 

4. call b in a function

- b 함수를 호출합니다.

- a 함수의 return address 를 Call Stack 에 저장합니다.

- program counter 를 b 함수의 시작 메모리 주소로 변경합니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer,
a function return address

]

program counter : 
b 함수의 Staring memory address

ebp : 
a function stack frame base pointer

esp:
main function stack frame base pointer + 4
a function stack frame base pointer + 1

 

5. push ebp, in b function

- ebp 를 Call Stack 에 저장합니다.

- 여기서 ebp 는 a 함수의 base pointer 를 의미합니다.

Call Stack : 
[

main function return address,
main function stack frame base pointer,
a function return address,
a function stack frame base pointer

]

program counter : 
b 함수의 Staring memory address + 1

ebp : 
a function stack frame base pointer

esp:
main function stack frame base pointer + 5
a function stack frame base pointer + 2

 

6. mov ebp, esp in b function

- 현재 Stack Pointer 를 ebp 에 저장합니다.

- Stack Pointer 는 자동으로 increment 되는데, 현재 Stack Pointer 값이 b 함수의 새로운 base pointer 가 됩니다.

- 즉, 새로운 Stack Frame 이 시작됩니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer,
a function return address,
a function stack frame base pointer

]

program counter : 
b 함수의 Staring memory address + 2

ebp : 
b function stack frame base pointer

esp:
b function stack frame base pointer

 

 

7. mov esp, ebp in b function

- b 함수의 stack frame 의 base pointer 를 stack pointer 로 변경합니다.

- b 함수에서 코드들이 실행되며 increment 되었던 stack pointer 가 초기화됩니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer,
a function return address,
a function stack frame base pointer

]

program counter : 
b 함수의 Staring memory address + 2

ebp : 
b function stack frame base pointer

esp:
b function stack frame base pointer

 

 

8. pop ebp in b function

- Call Stack 에 존재하는 a 함수의 base pointer 를 꺼내어 ebp 레지스터에 저장합니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer,
a function return address,

]

ebp : 
a function stack frame base pointer

esp:
b function stack frame base pointer - 1

 

 

9. ret in b function

- Call Stack 의 a function return address 를 Pop 하여 꺼냅니다.

- 그리고 program counter 를 a function return address 로 변경하여 b 함수를 종료합니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer

]

program counter : 
a function return address

ebp : 
a function stack frame base pointer

esp:
b function stack frame base pointer - 2

 

 

 

10. mov esp, ebp in a function

- a 함수의 stack frame 의 base pointer 를 stack pointer 로 변경합니다.

- a 함수에서 코드들이 실행되며 increment 되었던 stack pointer 가 초기화됩니다.

 

Call Stack : 
[

main function return address,
main function stack frame base pointer

]

program counter : 
a function return address

ebp : 
a function stack frame base pointer

esp:
a function stack frame base pointer

 

11. pop ebp in a function

- Call Stack 에 존재하는 a 함수의 base pointer 를 꺼내어 ebp 레지스터에 저장합니다.

 

Call Stack : 
[

main function return address,


]

program counter : 
a function return address

ebp : 
main function stack frame base pointer

esp:
a function stack frame base pointer - 1

 

 

12. ret in b function

- Call Stack 의 a function return address 를 Pop 하여 꺼냅니다.

- 그리고 program counter 를 a function return address 로 변경하여 b 함수를 종료합니다.

 

Call Stack : 
[

]

program counter : 
main function return address

ebp : 
main function stack frame base pointer

esp:
a function stack frame base pointer - 2

 

 

다소 복잡하긴 하지만, Stack Frame 의 base pointer 를 기존으로 Stack Frame 이 논리적으로 구분됩니다.

 

* Thread

쓰레드는 프로그램의 실행 단위입니다.

하나의 쓰레드가 하나의 실행 흐름을 가집니다.

실행이라는 말의 애매할 수 있는데요.

여기서 무언가를 실행한다는 의미는 cpu 를 점유한다는 의미입니다.

이런 관점에서 Stack Frame 에서 사용되는 데이터들도 CPU 의 레지스터를 사용하게 됩니다.