[CSAPP] 3.7 procedures(프로시저)

학습 주제

함수와 배열에 관한 내용이다.

정리한 내용

3.7 procedures(프로시저)

SW 추상화에서 중요한 것이다.

프로그램의 다른 곳에서 호출될 수 있다.

많은 프로그래밍 언어에서 function, method 등 이렇게 불린다.

machine level에서 procedure 지원하기 위해서는 반드시 다뤄져야 하는 많은 attribute들 있다.

함수 P가 Q를 부르고 Q가 실행이 되고 다시 P로 돌아오는 상황을 가정해보자.

이때 아래의 메커니즘을 한번 또는 여러번 포함할 수 있다.

1. passing control
   1. program counter = PC는 Q의 코드의 시작 주소로 설정되어야 한다. 그리고 Q가 반환이 되면 P의 다음 명령어로 설정이 되어야 한다.
2. passing data
   1. P는 1개 이상의 parameter를 Q에게 제공할 수 있어야 하며 Q는 P에게 return value를 제공할 수 있어야 한다.
3. allocating and deallocating memory
   1. Q는 시작할 때 Q의 지역 변수를 위한 공간을 allocate=할당 받아야 한다. 그리고 반환하기 전에 그 공간을 free하고 반환해야 한다.

procedure를 호출할 때 overhead를 최소화 하기 위해서 많은 노력이 있었다.

그래서 특정 procedure에서 필요한 만큼만 위의 메커니즘을 구현해서 했다.

이제 위의 각 3개를 각각 살펴보자.

3.7.1 run time stack(런타임 스택)

C나 다른 언어에서 함수 호출 메커니즘의 중요 특징은 stack을 사용해서 last in first out 되는 메모리 관리 규칙 사용할 수 있는 것이다.

프로그램은 passing control and data, allocating memory에 필요한 정보들을 저장하는 stack, program registers 같은 함수에 필요한 저장공간을 stack을 사용해서 관리할 수 있다.

P가 Q를 호출하면 control, data 정보가 stack 끝에 추가되는 것이다. 그리고 이 정보는 P로 돌아오면 다시 반환된다.

 

데이터는 pushq, popq 명령어로 stack에 저장되고 나온다.

초기화 하지 않은 데이터를 위한 공간도 stack에 할당될 수 있는데 그냥 stack pointer를 데이터 크기만큼 감소시키면 되는 것이다.

그리고 그 공간은 stack pointer를 증가시킴으로 반환할 수 있다.

 

x86-64는 함수가 레지스터에 저장할 수 있는 이상의 공간 요구할 때 stack에 공간을 할당한다.

이 공간을 함수의 stack frame이라고 부른다.

아래 그림은 run time stack의 전체적인 구조를 보여주고 있다.

현재 실행중인 함수의 frame은 항상 stack의 top에 있는 것이다.

 

함수 P가 Q를 부르면 P는 stack에 반환될 주소를 push한다. Q가 반환이 되면 프로그램이 다시 실행 되어야 하는 P의 위치를 표시하는 것이다.

이 반환될 주소는 P와 관련 있기 때문에 P의 stack frame의 일부로 간주된다.

 

Q를 위한 공간은 stack의 경계를 늘려서 할당한다. 이 공간에서 함수가 사용할 레지스터의 값을 저장하거나 지역 변수를 위한 공간을 할당하거나 필요한 argument를 설정한다.

 

대부분의 함수들을 위한 stack frame은 고정된 크기이다. 하지만 어떤 함수들은 가변 크기의 frame이 필요하다. 이 부분은 나중에 설명한다.

 

P는 stack에 최대 6개 integer value를 전달할 수 있는데 Q가 더 많은 argument를 필요로 한다면 이 더 많은 argument들은 P의 stack frame에 호출전에 저장이 된다.

위에 그림에서 argument 7, n이 이런 argument들을 저장해 놓은 것 같다.

 

시간과 공간의 효율성을 위해 x86-64 procedure는 stack frame에 필요한 부분만 할당된다.

예를 들어 많은 함수들은 6개 이하의 argument들을 가지고 있어서 이것들은 전부 registers에 저장될 수 있다.

그래서 위의 그림의 stack frame에서 일부는 생략할 수 있다.

 

사실 많은 함수들은 stack frame이 필요하지도 않은 경우가 있다.

이 경우는 지역 변수가 모두 register에 들어가거나 함수가 다른 함수 부르지 않을 때 나타난다.

이렇게 다른 함수 부르지 않는 함수를 leaf procedure라고도 한다.

3.7.2 Control transfer(제어의 이동)

함수 P에서 함수 Q로 passing control하는 것은 PC를 함수 Q의 코드 시작 부분의 주소로 설정해주면 된다.

하지만 Q가 반환될 때 processor는 함수 P가 실행되던 곳에 대한 기록을 가지고 있어야 한다.

이 정보는 x86-64에서 함수 Q를 부를 때 call Q 명령어를 사용하면서 저장이 된다.

이 명령어는 주소 A를 stack에 넣고 PC를 Q의 시작 주소로 설정한다.

여기서 A는 다시 돌아올 주소다. 이 주소는 call 명령어 다음의 명령어 주소로 계산이 된다.

이제 반대되는 명령어로 ret은 주소 A를 stack에서 pop하고 PC를 A로 설정해주는 명령어다.

 

call과 ret 명령어에 대한 기본 형태는 아래와 같다.

call 명령어는 호출하는 함수가 시작되는 명령어의 주소를 가리키는 target이 있다.

jump 명령어처럼 call 명령어는 direct 또는 indirect가 될 수 있다.

direct는 call Label처럼 직접 호출할 것이 label로 주어진다.

indirect는 call *operand처럼 간접 호출할 것이 * 다음에 operand specifier로 제공된다.

 

아래 그림은 main 함수에서 multstore라는 함수를 부르는 것을 표현한 그림과 그것의 assembly code를 나타낸 것이다.

여기서 보면 main에서 0x400563 주소의 call 명령어로 multstore 함수를 부르는 것 알 수 있다.

이것은 그림 a에 나와 있는데 파란 부분이 main 함수 진행되는 것이고 rip는 PC, rsp는 stack pointer이다.

그림 a에서 call 명령어 사용한 것이다.

call 명령어 사용하면 돌아올 주소인 0x400568이 stack에 들어가고 multstore 함수의 첫번째 명령어로 jump하는데 첫번째 명령어 주소는 그림 b에서 볼 수 있듯이 0x400540이다.

multstore 함수는 ret 명령어 만날 때까지 계속된다. ret 명령어는 0x40054d에 있다.

이 ret 명령어는 stack에서 저장된 return address인 0x400568을 꺼내 다시 이 주소로 jump해서 main 함수를 call 명령어 다음에서 다시 실행하게 한다.

아래 그림은 main에서 top 함수를 호출하고 top 함수에서 leaf 함수를 호출하는 것을 나타낸 것이다.

rdi는 argument로 넘어가는 값이고 rax는 return value 같다.

top에서는 넘어온 값을 5빼고 leaf를 부른 후 *2해서 반환하는 함수다.

leaf는 넘어온 값을 2 더해서 반환하는 함수다.

call하면서 rsp 즉 stack pointer가 돌아갈 위치를 가리키고 있다.

그리고 ret하면서 rsp에 있는 값이 PC로 되면서 돌아가는 것이다.

 

이렇게 return address를 stack에 push하는 간단한 메커니즘을 함으로써 함수가 적절한 위치로 돌아올 수 있게 한 것이다.

이렇듯 C (및 대부분 프로그래밍 언어)에서 call, return 메커니즘은 stack이 제공하는 last in, first out 메모리 관리 원칙과 일치한다.

3.7.3 data transfer(데이터 전송)

passing control해서 함수 호출하고 반환했을 때 함수 호출은 argument로 데이터 넘겨주고 함수 반환할 때 return value로 역시 데이터 넘겨준다.

x86-64에서 대부분의 함수에서 일어나는 데이터 넘겨주고 받는 것은 레지스터에서 일어난다.

예를 들어 위에서 rdi, rsi 이런 레지스터로 argument를 넘기는 것을 보고 rax 레지스터로 return value 받는 것을 보았다.

 

함수 P가 Q를 부를 때 P의 코드는 적절한 레지스터로 argument를 복사한다.

비슷하게 Q가 반환될 때 P의 코드는 rax 레지스터에 있는 return value에 접근할 수 있다.

 

x86-64에서는 6개의 정수 argument가 레지스터를 통해 넘어갈 수 있다.

각 레지스터는 지정된 순서로 사용되고 전달되는 데이터 타입 크기에 따라 레지스터 이름이 달라진다.

argument 순서에 따라 아래 레지스터에 할당이 된다.

argument의 크기가 64bit = 8byte이고 첫번째 argument이면 rdi 레지스터를 사용하는 것이다.

 

만약에 함수가 6개보다 많은 argument를 가지면 더 많은 argument들은 stack으로 보내진다.

stack frame에 이 argument들을 위한 공간을 할당할 것이다. 이때 7번 argument를 stack에 가장 위에 둔다. 위에 그림에서 본 것이다.

 

stack에 있는 parameter를 전달할 때 모든 데이터 크기는 8의 배수로 반올림된다.

argument들이 제자리에 있는 상태에서 control을 함수 P에서 Q로 넘길 수 있는 것이다.

함수 Q는 argument들을 레지스터나 stack에서 접근할 수 있다.

 

함수 Q에서 6개보다 많은 argument 가지는 함수 호출하면 아래 그림에 Argument Build area에 공간을 할당해서 argument를 stack에 넣는 것이다.

8개의 argument가 있을 때 2개의 argument는 아래 그림처럼 stack에 들어가 있는 것이다.

나머지 6개는 레지스터에 있는 것이다.

이 stack에서 return address가 함수 호출의 부분으로 stack에 psuch 되어 있는 것을 볼 수 있다.

그래서 2개 argument들은 return address보다 뒤에 있다.

 

코드에서 보면 다른 버전의 add 명령어를 볼 수 있다.

다른 것은 피 연산자의 크기에 따라 다른 것이다.

long을 더할 때에는 addq, int를 더할 때에는 addl, short를 더할 때에는 addw, char를 더할 때에는 addb 명령어가 사용되었다.

보면 6번째 줄에 movl은 메모리 = stack에서 4바이트를 읽어오는데 addb 명령어가 마지막 하위 한 바이트만 사용하는 것이다.

그래서 char을 더하는 것이다.

3.7.4 local storage on the stack(스택에서의 지역 저장공간)

지금까지 본 예제는 레지스터에 저장하는 것 이상의 local 저장소가 필요하지 않았다.

하지만 local data는 반드시 memory에 저장이 된다. 보통의 경우는 아래와 같다.

1. 레지스터에 공간이 모든 local data를 저장하기 부족하다.
2. 주소 연산자 &가 지역 변수에 적용이 되면 그것을 위한 주소를 반드시 생성해줘야 한다.
3. 지역 변수가 배열이나 구조를 가질 때 우리는 reference로 접근해야 한다.

함수가 stack frame에 공간을 할당할 때에는 stack pointer를 감소 시키는 것으로 한다.

그림에서 local variables 부분에 되는 것이다.

예제 1

아래 예시를 보자.

pointer xp, yp가 가리키고 있는 2개의 값 swap하고 2개의 합을 반환하는 함수가 swap_add다.

caller 함수는 pointer를 만들어서 swap_add에 넘기는 것이다.

위 그림은 caller가 지역 변수를 구현하기 위해 어떻게 stack frame을 사용하는지 보여준다.

보면 처음에 stack pointer를 16 내리는 것으로부터 시작한다. 이것은 stack에 16 바이트를 할당하는 것과 똑같다.

5번줄 보면 &arg2 계산하는 것인데 8(%rsp)이고 6번줄 보면 &arg1 계산하는 것인데 (%rsp)이니 이것으로 지역변수 arg1, arg2는 stack frame에 0, 8에 있다는 것을 알 수 있다.

이때 0, 8은 stack pointer가 16일 때 상대적인 것이다.

 

그 다음 swap_add 함수가 끝난 다음 2개의 값을 가져와서 빼기를 계산한다. 이때 이 빼기의 값이 rdx 레지스터에 저장되는 것 같다.

그리고 swap_add에서 반환하는 값이 저장된 rax 레지스터의 값과 rdx에 저장된 값을 곱한다.

즉 rdx는 diff 값을 가지고 있고 rax 값은 sum 값을 가지고 있는 것이다.

그리고 11번줄에서 stack pointer를 16 올리면서 stack frame을 반환하는 것이다.

 

여기서 볼 수 있듯이 run time stack은 함수가 필요하면 local storage를 할당해주고 함수가 끝나면 다시 반환해주는 간단한 메커니즘을 제공해주는 것을 알 수 있다.

 

 

예제 2

다음 예제는 stack에 지역 변수를 위해 할당하는 것을 보여준다. 왜냐하면 8개의 argument를 전달해야 하기 때문이다.

보면 2-15번 줄은 proc 함수를 부르기 위해서 준비하는 부분이다.

여기서는 지역 변수와 parameters를 위한 stack frame을 설정하는 것과 레지스터에 argument를 loading하는 과정이 포함된다.

위의 그림에서 볼 수 있듯이 지역 변수 x1~x4는 다른 크기로 stak에 할당이 되어 있다.

보면 각각 데이터 형이 long, int, short, char이라 각각 8, 4, 2, 1 byte 차지하는 것을 볼 수 있다.

이 변수들을 위한 포인터들은 leaq 명령어에 의해 만들어진다. 위에 7, 10, 12, 14번 줄에서 볼 수 있다.

그리고 7, 8번째 argument들은 역시 stack에 저장된 것을 볼 수 있다.

그 다음 proc 함수가 불리면 아래 그림처럼 되는데 왜냐하면 return address가 stack에 쌓이기 때문이다.

이제 다시 call_proc으로 돌아오게 되면 17-20번 줄처럼 지역 변수의 값들을 가져와서 계산을 한다.

그 다음 stack pointer를 32 증가 시켜서 stack frame을 반환하는 것이다.

3.7.5 local storage in registers(레지스터를 이용하는 지역저장소)

레지스터의 집합은 모든 함수에서 공유되는 단일 리소스로 작동한다.

물론 한 시간에서 하나의 함수만 그 레지스터를 사용할 수 있지만 하나의 함수가 다른 함수를 호출할 때 호출된 함수가 레지스터의 값을 overwrite하지 않는다.

 

레지스터 사용에 대한 규칙이 있다.

rbx, rbp, r12~r15 레지스터는 callee saved 레지스터로 분류된다.

함수 P가 Q를 호출했을 때 Q는 이 레지스터의 값들을 보존해야 하고 Q가 호출 되었을 때와 같은 값을 같게 해야 한다.

함수 Q는 값을 건들지 않거나 기존 값을 stack에 push해서 값을 보존한다.

그리고 Q가 반환될 때 이 stack에 있는 값들을 pop한다.

이렇게 stack에 저장되는 레지스터 값들은 아래 그림에 saved registers에 저장된다.

이런 규칙을 통해 P는 callee saved 레지스터의 값을 Q가 호출되고 다시 돌아왔을 때에도 사용할 수 있는 것이다.

 

stack pointer rsp를 제외한 다른 모든 레지스터들은 caller saved 레지스터로 분류한다.

이것의 의미는 이 레지스터들은 어떤 함수던지 이 값들을 변경할 수 있다는 것이다.

그래서 함수 P는 함수 Q를 부르기 전에 Q가 이 레지스터의 값들을 다 바꿀 수 있으니 P가 이 레지스터의 값들을 저장해 놔야 한다는 것이다.

 

아래 예제에서 보면 P함수는 Q함수를 2번 호출한다. 각각 x, Q(y) 값을 유지해야 한다.

그래서 아래 코드를 보면 2개의 callee saved 레지스터를 사용한다.

rbp는 x의 값을 저장하기 위해, rbx는 Q(y)의 값을 저장하기 위해.

그래서 코드의 처음에 보면 이 rbp, rbx 두 레지스터에 원래 저장되어 있는 값들을 stack에 저장한다.

 

그리고 rbp에다가 x값을 저장해서 사용한다. 그리고 Q(y)의 값을 rbx에 저장한다.

그리고 P함수 마지막에는 원래 rbx, rbp 값을 복구해 놓기 위해 pop하는 것을 볼 수 있다.

3.7.6 recursive procedures(재귀 프로시저)

레지스터, stack 사용에 관한 규칙은 x86-64 함수들이 서로 recursive하게 호출할 수 있게 했다.

각 함수들은 자신의 고유의 공간을 stack에 가져서 각 지역 변수에 간섭하지 않는다.

또 함수 호출될 때 local storage를 할당하고 함수 반환 전에 할당 해제하는 적절한 방법을 stack 사용 규칙이 제공한다.

 

아래 예제는 재귀적인 팩토리얼 함수에 관한 예제다.

보면 2번 줄에서 argument n을 저장하기 위해 rbx 레지스터 사용할 것이라 stack에 원래 있던 값을 저장하는 것을 볼 수 있다.

그리고 11번 줄에서 다시 그 값을 복구 시킨다.

 

그리고 8번 줄에서 rfact(n-1)이 호출되고 반환된다.

이때 반환 값은 stack과 레지스터 저장 규칙에 따라 rax 레지스터에 저장이 될 것이다.

그리고 n은 위에서 rbx 레지스터에 저장이 된다고 했으니 아래 9번 줄에서 둘을 곱하는 것이다.

그래서 n*rfact(n-1)해서 결과가 나오는 것이다.

 

위의 예제에서 볼 수 있듯이 재귀적인 함수 호출도 이전에 그냥 다른 함수 호출과 같은 것을 볼 수 있다.

이렇게 함수 호출하고 반환되고 할 때 일어나는 이 방법은 재귀를 포함해 더 복잡한 패턴에도 똑같이 적용이 된다.