Advanced Procedures - 스택 프레임, 재귀

스택 프레임은 활성화 기록(activation record)이라고도 불리며, 프로시저의 반환 주소, 전달된 매개변수, 저장된 레지스터, 지역 변수 등을 위한 스택의 일부이다.
 
 
스택 프레임은 다음과 같은 단계로 생성된다.

1. 호출 프로그램이 인수를 스택에 푸시하고 프로시저를 호출한다.
2. 호출된 프로시저는 EBP를 스택에 푸시하고, EBP를 ESP로 설정한다.
3. 지역 변수가 필요하면, 상수를 ESP에서 빼서 스택에 공간을 만든다.

 
 
 
스택 프레임의 구성요소와 재귀를 통해서 서브루틴(함수)과 서브루틴 호출 기반 구조가 어떻게 이루어지는지 알아보자.
 
 
 
 

스택 매개변수 Stack Parameters

 
지금까지는 프로시저가 레지스터 매개변수를 사용해왔다.
하지만 레지스터 매개변수를 사용하면 코드가 복잡해졌다.
 
 
스택 매개변수는 레지스터 매개변수보다 더 편리한 방법을 제공한다.
서브루틴 호출 바로 전에 인수들이 스택에 푸쉬된다.

pushad
mov esi, OFFSET array
mov ecx, LENGTHOF array
mov ebx, TYPE array
popad
push TYPE array
push LENGTHOF array
push OFFSET array

 
 
 
서브루틴 호출 동안 두 가지 일반적인 타입의 인수가 스택에 푸쉬된다.
 
 

값으로 인수 전달 (Passing Arguments by Value)

• 인수 값을 스택에 푸시한다.
• 호출된 프로시저를 호출한다.
• 호출된 프로시저가 인수를 제거하지 않았다면 스택에서 인수를 제거한다.

 

.data
val1 DWORD 5
val2 DWORD 6
.code
push val2
push val1

 
스택의 호출 전 ESP의 상태는 다음과 같다.

 
 
 

참조로 전달 (Passing by Reference)

• 인수의 오프셋을 스택에 푸시한다.
• 프로시저를 호출한다.
• 호출된 프로시저가 인수를 제거하지 않았다면 스택에서 인수를 제거한다.

 

.data
val1 DWORD 5
val2 DWORD 6
.code
push OFFSET val2
push OFFSET val1

 
스택의 호출 전 ESP의 상태는 다음과 같다.
 

 
 
이렇게 스택의 호출이 진행되면 ESP는 다음을 가리킨다.

 
 
 

배열 참조로 전달 (Passing an Array by Reference)

• ArrayFill 프로시저는 배열을 16비트 난수로 채운다.
• 호출 프로그램은 배열의 주소와 배열 요소의 개수를 전달한다.

 

.data
count = 100
array WORD count DUP(?)
.code
push OFFSET array
push COUNT
call ArrayFill

 
 
 

 

ArrayFill PROC
push ebp
mov ebp, esp
pushad
mov esi, [ebp + 12]
mov ecx, [ebp + 8]

 
ESI는 배열의 시작을 가리키므로 루프를 사용하여 각 배열 요소에 접근하기 쉽다.
 
 
 

스택 매개변수 접근(Accessing Stack Parameters)

• 함수는 EBP로부터 일정한 오프셋을 사용하여 스택 매개변수에 접근한다.
  예: [ebp + 8]
• EBP는 스택 프레임의 기준 주소를 저장하므로 기준 포인터(frame pointer)라고 한다.
• 함수가 반환될 때 EBP는 원래 값으로 복원되어야 하고, 함수가 진행 중에 값이 바뀌지 않는다.

 
 
 

RET 명령어

• RET 명령어는 서브루틴에서 반환할 때 사용된다.
• 스택에서 값을 꺼내어 명령 포인터(EIP 또는 IP)에 넣어 제어를 목표 주소로 이동시킨다.
• 문법은 RET n 형식이다.
• 선택적 피연산자 n이, 값이 EIP나 IP에 할당된 후 스택 포인터에 n 바이트를 더한다.

 
 
스택에서 매개변수는 누가 제거하냐면
호출자(Caller) 또는 호출된 절차(STDCALL)에 따라 다르다.
 
호출자(Caller) 코드

push val2
push val1
call AddTwo
add   esp,8

 
 
Called-procedure (STDCALL) 코드

AddTwo PROC
push ebp
mov ebp, esp
mov eax, [ebp + 12]
add eax, [ebp + 8]
pop ebp
ret 8

 
 
 
 
Difference라는 프로시저를 만들어 첫 번째 인수를 두 번째 인수에서 빼는 예제

Difference PROC
push ebp
mov ebp, esp
mov eax, [ebp + 8]
sub eax, [ebp + 12]
pop ebp
ret 8
Difference ENDP

 
 
 

레지스터 저장 및 복원

ESP를 EBP에 할당한 직후 레지스터를 스택에 푸시하여 저장한다.

MySub PROC
push ebp
mov ebp, esp
push ecx
push edx

 
 
 
USES 연산자는 레지스터를 저장하고 복원하는 코드를 생성한다.

MySub1 PROC USES ecx edx
ret
MySub1 ENDP

 
 
 
 
 

Local Variables

 
 
서브루틴 내에서만 지역 변수를 수정하거나 볼 수 있다.
서브루틴이 종료되면 지역 변수가 사용하는 저장 공간은 해제된다.
 
 
지역 변수를 생성하는 코드 예제

MySub PROC
push ebp
mov ebp, esp
sub esp, 8
mov DWORD PTR [ebp - 4], 10
mov DWORD PTR [ebp - 8], 20

int x = 10, y = 20; 이런 두 개의 지역변수를 생성하고 초기화하는 코드이다.

 
 
 

LEA 명령어

LEA(Load Effective Address)는 직접 및 간접 피연산자의 오프셋을 반환한다.
오프셋 연산자는 오직 상수만을 반환한다.

CopyString PROC
count: DWORD
LOCAL temp[20]: BYTE
lea edi, count
lea esi, temp

 
 
아래는 지역변수의 주소를 ESI에 저장하는 코드이다.

lea esi, [ebp - 8]

 
 
 
 
 

ENTER and LEAVE Instructions 

 
ENTER 명령어는 호출된 프로시저의 스택 프레임을 생성한다.

MySub PROC
enter 8, 0

 
EBP를 스택에 푸시한 후, EBP를 스택 프레임의 기준으로 설정하고, 지역 변수를 위한 공간을 확보한다.
 
 
 
LEAVE 명령어는 프로시저의 스택 프레임을 종료한다.

 
 
 
 
 

LOCAL 지시어 Directive

 
LOCAL 지시어는 지역 변수 목록을 선언한다.

MySub PROC
LOCAL var1: BYTE, var2: WORD, var3: SDWORD

 
 
로컬 사용 예시 1

 LOCAL flagVals[20]:BYTE	; array of bytes
 LOCAL pArray:PTR WORD		; pointer to an array	
 myProc PROC,			; procedure
 LOCAL t1:BYTE,			; local variables

 
 
 
로컬 사용 예시 2
BubbleSort 프로시저의 스택 프레임 다이어그램

 BubbleSort PROC
 	push ebp
 	mov  ebp,esp
 	add  esp,0FFFFFFF8h	; add -8 to ESP
 	. . .
 	mov  esp,ebp
 	pop  ebp
 	ret
 BubbleSort ENDP

 
 
 
로컬 바이트 변수

Example1 PROC
LOCAL var1: BYTE
mov al, var1
ret
Example1 ENDP

 
 
 
 
 

INVOKE Directive 

INVOKE 지시어는 여러 인수를 전달할 수 있는 Intel의 CALL 명령어 대체이다.

INVOKE procedureName [, argumentList]

 
 

.data
byteVal BYTE 10
wordVal WORD 1000h
.code
	; direct operands:
	INVOKE Sub1, byteVal, wordVal
	
     ; address of variable:
    INVOKE Sub2, ADDR byteVal
	
    ; register name, integer expression
    INVOKE Sub3, eax, (10 * 20)
	
    ; address expression (indirect operand)
    INVOKE Sub4, [ebx]

 
 
 
 
 

PROC 지시어

PROC 지시어는 선택적 명명된 매개변수 목록과 함께 프로시저를 선언한다.
 
문법

label PROC paramList

 
 
paramList는 쉼표로 구분된 매개변수 목록이다.
각 매개변수는 다음과 같은 문법을 가진다.

paramName : type

 
type은 표준 ASM 유형(BYTE, SBYTE, WORD 등) 중 하나이거나 이러한 유형 중 하나의 포인터여야 한다.
 
 
 
대체할 수 있는 형식으로는, 매개변수 목록이 한 줄 또는 여러 개의 별도 줄에 있을 수 있도록 허용한다.

label PROC,
    paramList

여기에서 꼭 쉼표를 넣어야 한다.
 
이와 같이 매개변수 또한 같은 줄에 있거나, 쉼표를 통해 별도의 줄에 배치할 수 있다.
 
 
 
FillArray는 바이트 배열에 대한 포인터, 배열의 각 요소에 복사될 단일 바이트 채움 값, 배열의 크기를 인자로 받는다.

FillArray PROC,
    pArray:PTR BYTE, fillVal:BYTE
    arraySize:DWORD

    mov ecx, arraySize       ; 배열 크기를 ecx에 저장
    mov esi, pArray          ; 배열 포인터를 esi에 저장
    mov al, fillVal          ; 채움 값을 al에 저장
L1: mov [esi], al            ; al의 값을 esi가 가리키는 메모리 위치에 저장
    inc esi                  ; esi를 증가시켜 다음 배열 요소를 가리키도록 함
    loop L1                  ; ecx를 감소시키고 ecx가 0이 아닐 때 L1으로 점프
    ret                      ; 프로시저 반환
FillArray ENDP

 
 
 
 
 

Recursion

 
 

• 재귀는 다음과 같은 경우에 발생합니다:
  • 절차가 자신을 호출할 때
  • 절차 A가 절차 B를 호출하고, 절차 B가 다시 절차 A를 호출할 때
• 각 노드가 절차이고 각 엣지가 절차 호출인 그래프를 사용하여 순환을 형성합니다

 
 
 
 
재귀적으로 합 계산하기

CalcSum PROC
	cmp ecx, 0        ; 카운터 값 확인
	jz L2             ; 0이면 종료
	add eax, ecx      ; 그렇지 않으면 합에 추가
	dec ecx           ; 카운터 감소
	call CalcSum      ; 재귀 호출
L2: ret
CalcSum ENDP

 
이에 따른 스택 프레임은 다음과 같다.

 
 
 
 
 
팩토리얼 계산하기
 

Factorial PROC
	push ebp
	mov  ebp, esp
	mov  eax, [ebp+8] ; n 값을 가져옴
	cmp  eax, 0       ; n < 0 인가?
	ja   L1           ; 그렇다면 계속
	mov  eax, 1       ; 그렇지 않다면 1 반환
	jmp  L2

L1: dec  eax
	push eax          ; Factorial(n-1)
	call Factorial

ReturnFact:
	mov  ebx, [ebp+8] ; n 값을 가져옴
	mul  ebx          ; eax = eax * ebx

L2: pop  ebp      	; EAX 반환
	ret  4            ; 스택 정리
Factorial ENDP

 
 
팩토리얼의 재귀 호출로 생성되는 첫 번째 몇 개의 스택 프레임을 보여주는 다이어그램

 
여기에서 각 재귀 호출은 스택 공간 12바이트를 사용힌다.