컴퓨터공학을 공부하다 보면 어셈블리어라는걸 들어봤을 것이다.
우리가 사용하는 언어 - 파이썬, C, 자바 등은 전부 이 어셈블리어로 변환되어 컴퓨터가 실행할 수 있게 된다.
오늘의 주제가 어셈블리어이긴 하지만 이 강의에서는 어셈블리어로 직접 코딩하는 과제는 없을 것이다.
예전에는 어셈블리어로 연결리스트를 구현한다던지, 배열을 정렬한다더지의 과제가 있었지만, 현재는 그런 능력보다 컴파일러가 생성한 코드를 보고 원래의 C코드에 어떻게 대응되는지 아는 능력이 더 중요해졌다.
1. C, 어셈블리어, 기계어
이후의 내용을 이해할 수 있도록 간단한 용어 설명을 몇개 하겠다.
(1) 아키텍쳐란 어셈블리어 또는 기계어를 이해하기 위해 필요한 프로세서 디자인의 일부분이다.
(2) 명령어 집합 (ISA, Instruction Set Architecture)은 소프트웨어가 어떻게 CPU를 다룰 수 있는지 알려주는 추상적인 모델이다. ISA는 하드웨어와 소프트웨어 사이의 인터페이스처럼 작동하며 프로세서가 어떤 연산이 가능한지 정의한다.
(3) 아키텍쳐가 구현된 것을 마이크로아키텍쳐라 부르며, 이 강의에서는 x86 ISA를 다룰 것이다.
(4) 기계어란 프로세서가 실행하는 바이트 단위 프로그램이고, 어셈블리어는 기계어를 사람이 알아볼 수 있게 텍스트로 나타낸 것이다.
(5) PC(Program Counter)란 다음 명령의 주소를 가리키는 곳이다.
(6) CPU에는 레지스터라는 정보를 저장할 수 있는 장소가 몇곳 있는데, 64비트밖에 저장할 수 없지만 아주아주 빠르다.
(7) 조건코드(condition code)는 가장 최근에 실행된 연산의 정보를 저장하는 곳이며 조건문과 비슷한 역할을 하는 특정 명령어에 사용된다.
어셈블리어는 어떻게 만들어질까? 다음 도식을 보자.
우리가 gcc -Og -S 로 컴파일을 하면 (-Og는 기본적인 최적화를, -S는 사람이 읽을 수 있는 어셈블리어 파일을 만든다), 먼저 C 프로그램은 어셈블리어 프로그램으로 변환되고, 어셈블러가 그걸 오브젝트 파일로 변환하며, 마지막으로 링커가 라이브러리를 합쳐서 실행파일로 변환한다. 참고로 .s는 어셈블리어 파일이다.
예를 들어 다음 sum.c 파일을 gcc -Og -S sum.c -o sum 으로 컴파일하면 오른쪽과 비슷한 어셈블리어 파일이 나온다 (단, 컴퓨터 환경에 따라 다른 명령어가 생성될 수 있다).
%rbx, %rdx처럼 %로 시작하는건 레지스터의 이름이고 그 왼쪽에 있는건 명령어이다.
예를 들어 pushq는 %rbx 레지스터에 있는 값을 스택에 넣으라는거고 movq는 복사, call은 프로시저의 호출, ret는 return을 의미한다. 조금 있다가 더 자세히 설명하겠다.
사실 이건 원래 코드가 아니다. 원래는 이렇게 생겼었다.
중간중간에 .cfi_ 같은 이상한 코드가 보인다. .으로 시작하는 애들은 디버거와 링커를 위한 코드이고 우리에겐 중요하지 않다. 따라서 이 강의에서 저런것들은 다 제외하고 설명을 하겠다.
2. 어셈블리어 기초
레지스터는 1, 2, 4, 8 바이트의 정수를 담을 수 있는 레지스터와 4, 8, 10바이트의 부동소수점 값을 저장할 수 있는 레지스터가 있다. 메모리 주소도 정수 레지스터에 저장된다.
어셈블리어 코드는 그저 바이트의 시퀀스일 뿐, 배열이나 구조체같은 집계 타입이 없다. 애초에 타입이란건 존재하지 않으며 똑같은 바이트를 문자열로 해석하냐 정수로 해석하냐는 프로그래머가 알아서 기억해야 한다.
어셈블리어의 명령어는 레지스터나 메모리의 데이터를 대상으로 실행된다. 메모리에서 레지스터로 데이터를 옮기거나, 레지스터의 값을 메모리에 저장할 수도 있다. 또 명령어로 조건문이나 반복문 등을 구현할 수도 있다.
다음은 한줄짜리 C 코드가 어셈블리어로 변환되는 과정이다. 실제로는 맨 밑의 오브젝트 코드가 되며, 가독성을 위해 어셈블리어로 표시하는것 뿐이다 (지금 오브젝트 코드는 기계어가 되기 한단계 전이라고만 생각하자).
C 코드에선 t의 값을 dest가 가리키는 곳으로 옮긴다. 어셈블리 코드에서도 같은 일을 한다. 다만 t가 %rax 레지스터에, dest가 %rbx 레지스터에 담겨있을 뿐이다. 포인터 역참조는 괄호를 쓴다.
오브젝트 코드의 0x40059e는, 이 코드가 주소 0x40059e에 저장되어 있음을 의미한다.
C 소스파일이 없어도 a.out이나 .o 오브젝트 파일만 있다면 역어셈블러(disassembler)를 써서 어셈블리어 파일을 복원할 수 있다.
예를 들어 objdump -d <실행파일> 와 같이 쓴다.
이제 x86 아키텍쳐에 무슨 레지스터가 있는지 보자. r로 시작하는게 64비트 레지스터고 e로 시작하거나 d로 끝나는 오른쪽에 있는 것들은 32비트를 다룰때 쓴다 (같은 레지스터의 하위 절반을 쓴다). 그래서 %rax부터 %r15까지 총 16개의 레지스터가 존재한다.
레지스터가 많으면 많을수록 좋을텐데 왜 16개밖에 없을까? 라고 생각했었지만 찾아보니 레지스터 수가 16개에서 32로 두배로 증가해도 퍼포먼스는 고작 10%밖에 증가하지 않으며, 수가 두배가 되면 레지스터 이름을 표현하는데 1비트가 추가로 필요하니 전체적으로 비용이 증가하게 된다.
%rax, %ebx, … 레지스터는 이름이 왜 이렇게 괴상하게 생겨먹었을까? x86는 영어처럼 누군가 처음에 효율을 중시하고 만든게 아니고 시간이 지나면서 추가되고 수정되고 하면서 비직관적인 이름이 된 것이다. e는 extended라는 뜻으로, 원래 16비트 8086 어셈블리어라는게 있었는데 거기의 레지스터 이름을 확장하면서 나온것이다. r은 register의 약자다.
또 원래 레지스터는 8개밖에 없었지만 x86-64로 넘어오면서 16개로 늘어났다. 이때 %r8 ~ %r15가 추가된 것이다. 그러면 왜 %r1이 아니고 %rax일까?
아주아주 옛날에는 각 레지스터가 하는 일이 있어서, 이름이 그 하는 일을 나타냈다. 예를 들어 %rax는 accumulate, %ecx는 counter, %edx는 data 등등. 지금은 전혀 상관없게 돼버렸지만.
단 저 핑크색 %rsp는 스택 포인터라는 레지스터인데, 특별히 혼자 하는일이 다르다.
이제 레지스터 명령어를 배울것이다. 명령어의 인자로는 세가지 종류가 올 수 있다. 첫번째는 상수로, $0x400, $-533 같이 C에서의 상수와 비슷하지만 $로 시작해야한다. 두번째는 레지스터 이름이고, 세번째는 메모리 주소이다. (%rax)처럼 8바이트 메모리 주소가 인자로 올 수 있다.
movq src, dst 명령어는 단순히 src값을 dst로 복사한다. 단, src와 dst 둘다 메모리 주소가 될 수는 없다.
앞에서 봤었지만 레지스터를 괄호로 감싸면 레지스터의 값을 메모리 주소로 인식하라는 뜻이다 (포인터 역참조).
다음은 두 메모리 주소에 담긴 값을 바꾸는 간단한 함수이다. 어셈블리어를 읽어보자. 지금이라면 이해할 수 있다. 참고로 함수가 호출되면 첫번째 인자는 항상 %rdi에, 두번째 인자는 %rsi에 저장된다.
첫번째 명령어는 %rdi의 값을 메모리 주소로 인식해, 그 값을 %rax에 복사한다. 예를 들어 %rdi의 값이 그림과 같이 0x120이라는 주소이고 123이라는 값이 메모리에 담겨있다면 그 값을 복사한다.
이런 식으로 레지스터와 메모리 간 데이터 교환이 일어나게 된다.
참고로 movq의 q는 quadword의 약자로, 옛날 인텔 8086 아키텍쳐에서 word = 2바이트, doubleword = 4바이트, quadword = 8바이트라고 불렀던 용어가 아직까지 남아있는 것이다.
레지스터로 포인터 연산도 할 수 있다. 메모리 주소 앞에 숫자를 붙이면 그 숫자만큼 주소를 이동하라는 뜻이다. 예를 들어 movq 8(%rbp), %rdx 는 %rbp에서 8바이트 더 간 곳의 값을 %rdx로 복사하라는 뜻이다.
더 나아가 일반적으로는 D(Rb, Ri, S) 는 *[Reg[Rb] + S*Reg[Ri] + D] 를 축약한 형태이다. D는 변위(displacement)를 나타내며 1, 2, 또는 4 바이트이다. Rb는 베이스 레지스터, Ri는 인덱스 레지스터 (Ri ≠ %rsp)이며 S는 계수(scale)로, 1, 2, 4, 또는 8 바이트이다. 어셈블리어에서 배열을 다루는 법을 보게되면 이해가 더 잘될것이다.
다시 말하자면 D(Rb, Ri, S) 라고 쓰면 Rb레지스터에 있는 값과, Ri 레지스터에 있는 값 곱하기 S와, D를 전부 더해서 그 합을 메모리 주소로 인식한다.
연습문제로 다음을 보자.
0x8(%rdx)는 %rdx에 있는 값과 0x8을 더해 0xf008이라는 메모리 주소가 된다. (%rdx, %rcx)는 단순히 두 값을 더한 메모리 주소이고, (%rdx, %rcx, 4)는 아까와 똑같이 더하지만 두번째 인자에 4가 곱해진다. 또 첫번째 인자는 0x80(, %rdx, 2)처럼 생략될 수 있다.
3. 산술, 논리 명령어
학생들이 가장 헷갈리는 명령어인 leaq를 먼저 보자 (load effective address quadword). leaq src, dst 에서 src는 위와 같은 메모리 계산식이다. src의 메모리 식을 계산한 후 그 값을 dst에 저장한다.
예를 들어 leaq (%rdi, %rdi, 2) %rax 가 있고 %rdi에 x라는 값이 있으면 leaq는 %rax에 3x를 저장한다 (괄호로 감싸져 있지만 leaq는 3x라는 주소에 들어있는 값을 저장하지 않는다).
이처럼 leaq의 원래 목적은 메모리 계산식을 미리 계산하는 것이지만, 단순한 산술 연산에도 쓰일 수 있다.
예를 들어 아래와 같이 12x를 계산할때 컴파일러는 대신 leaq로 3x를 계산하고 salq로 4를 곱한다 (salq는 시프트 연산을 한다).
또 다음과 같이 산술 연산자가 있는데 간단한 것들이라서 빠르게 넘어가겠다. 주의할 점으로는 sarq는 산술 시프트를, shrq는 논리 시프트를 한다는 것이다. 그게 뭔지 잊어버렸다면 1강을 참조하자.
4. 조건코드
이제 주제를 바꿔서 프로세서가 어떻게 조건문을 다루는지 보자.
프로세서는 16개의 레지스터를 갖고 있고, 거기에 더해 %rip(instruction pointer) 레지스터가 있는데 이건 현재 수행할 명령의 주소를 가리킨다.
또 조건코드라는게 있는데 얘네들은 다른 명령어의 부수효과로 정해지는 1 비트 플래그이다.
몇가지만 설명하자면
- CF(Carry Flag)는 최근 명령에서 unsigned 오버플로우가 나면 1로 세팅된다.
- ZF(Zero Flag)는 최근 명령어의 결과값이 0이면 1로 세팅된다
- SF(Sign Flag)는 최근 명령어의 결과값이 음수면 1로 세팅된다.
- OF(Overflow Flag)는 최근 명령에서 signed 오버플로우가 나면 1로 세팅된다.
이 조건코드는 cmpq와 같이 특정 명령어에 반응한다. cmpq b a는 a - b를 계산하여 조건코드를 세팅한다 (계산만 하고 저장하진 않는다). testq b a 는 비슷하게 a & b를 계산한다.
이렇게 세팅한 조건코드는 SetX 명령어로 읽어들인다. SetX 명령어들은 조건코드의 값에 따라 dst의 최하위 바이트를 0 또는 1로 만든다.
예를 들어 sete dst 는 ZF 조건코드가 1이면 dst의 최하위 바이트를 1로 만든다.
setg dst 는 ~(SF^OF)&~ZF의 값이 1이면 dst의 최하위 바이트를 1로 만든다. 저 논리식은 마지막 계산이 >가 나왔을때라고 한다.
이게 1강에서 정수가 어떻게 비트로 표현되는지를 알아야 했던 이유다.
나는 어떻게 이해했냐면, cmpq b a ,setg c 가 있다면 조건코드가 어떻게 작동하는지는 상관하지 말고 a > b면 c의 최하위 비트를 1로 만든다 라고 이해했다.
다음의 gt 함수를 어셈블리어로 컴파일하면 다음과 같다.
cmpq 는 위에서 봤듯이 %rdi - %rsi를 계산하여 조건코드를 세팅하고, setg 는 조건코드를 잘 주물주물해서 %rdi > %rsi 였을때 %al을 1로 만든다 (setg 가 언제 1을 만드는지는 위의 표에 나타나 있다. 또 %al은 %rax의 최하위 바이트를 말한다).
movzbl 은 %al의 값을 %eax에 복사하고 이때 %al 왼쪽의 비트를 전부 0으로 초기화한다 (%eax는 $rax의 최하위 32비트를 말한다).
단, 이때 movzbl 이 초기화하는건 %eax의 비트 뿐이다. 아직 %rax에는 초기화할 32비트가 남아있다.
이 비트들은 x86의 별난 특성때문에 초기화가 되는데, 그 특성이란 레지스터에 32비트 수가 세팅되면 나머지 32개의 비트들은 전부 0이 된다는 것이다. 어쨌든 이렇게 해서 x > y면 1이, 아니면 0이 리턴이 된다.
5. 조건문
조건 코드는 어셈블리어가 조건문을 구현하는데 사용된다.
jX 명령어들은 타겟 주소가 주어지면 조건 코드가 적절히 세팅되었을때 그 주소로 점프를 한다. 점프를 한다는 것은 다음 명령을 그 주소에서부터 시작한다는 것이다.
두 숫자의 차를 구하는 코드를 보자.
우선 cmpq 로 인자를 비교한다. 이때 조건코드가 세팅된다. 세팅된 조건코드는 jle 가 읽어서 만약 ≤를 나타내는 조건코드였다면 .L4로 실행 흐름을 변경한다 (.x:는 레이블이라고 하며 점프 대상을 지정할때 유용하다).
그 후 적절히 리턴할 값을 %rax에 저장한다 (어셈블리어에서 리턴값은 항상 %rax에 놓아야 한다).
컴파일러는 조건문을 최적화하기 위해 특수한 기법을 쓸수도 있다. Conditional move이란 조건문이 있으면 조건이 참일때와 거짓일때 둘다 미리 계산해놓고, 그 후에 적절한 값을 선택하는 기법이다.
인간의 눈으로는 굉장히 비효율적인것처럼 보이지만, 사실 계산이 쉽다면 오히려 더 효율적인 방법이다.
이게 효율적인 이유는 프로세서는 바다를 떠다니는 커다란 유조선같은 존재라서이다.
유조선은 한 방향으로는 빠르게 이동할 수 있지만, 중간에 방향을 바꾸려면 엄청난 힘이 든다.
프로세서도 마찬가지로 한번에 수많은 명령을 처리하지만 중간에 조건문이 등장하면 조건을 계산하기 전에 한쪽을 미리 계산해놓는 분기 예측(branch prediction)이라는, 굉장히 성공적인 기법을 쓴다. 대략 98%의 경우 올바른 갈래를 예측해낸다.
하지만 틀릴경우 약 40 명령어 사이클을 낭비하게 된다(1 명령어 사이클은 프로세서가 명령어 하나를 실행하는 과정이다). 따라서 둘다 미리 계산해놓는게 더 효율적일 때도 있다.
위의 두 숫자의 차를 구하는 코드는 사실 conditional move를 쓴 아래 코드로 컴파일된다.
cmovle는 조건코드를 비교해서 ≤ 면 mov 명령을 실행한다. x ≤ y면 %rdx의 값 (y - x)가 %rax로 덮어씌워지는걸 볼 수 있다. x > y 면 cmovle 가 일어나지 않으니 미리 계산해둔 x - y가 리턴값이 된다.
6. 반복문
이번에는 어셈블리어는 반복문을 어떻게 구현하는지 살펴보자.
사실 C에서도 다음과 같이 간단한 do-while문은 goto를 이용해 반복문 없이 구현할 수 있다. goto loop은 loop:이라고 쓰여진 곳으로 점프하라 라는 뜻이다.
이게 어셈블리어가 반복문을 구현하는 방법이다. goto는 jX 명령어들로 대체하면 된다. 여기서 쓰인 jne 명령어는 최근 연산의 결과값이 0이 아니였을경우 점프한다.
while문은 비슷하지만 조건식이 먼저 계산된다는 차이점이 있다. 이건 goto를 하나 더 넣음으로서 해결할 수 있다.
어셈블리어로 어떻게 구현되는지 상상이 갈 것이다. 맨 위에 jmp 명령어를 하나 넣으면 된다.
For문도 본질적으로는 while문과 같으니 다음과 같이 while문으로 변형시킬 수 있다.
이렇게 모든 종류의 반복문을 어셈블리어로 구현할 수 있다.
7. switch문
switch문은 어떻게 컴파일될까? if문처럼 컴파일된다고 생각한다면 틀렸다.
다음과 같이 .s 어셈블리어 파일 안에 컴파일된 코드와 함께 점프 테이블이란걸 생성한다.
switch문에 n개의 case가 있을때 컴파일러는 각 case안의 코드 블록을 메모리 어딘가에 컴파일해서 따로 저장해놓는다. 그리고 그 블록들의 주소를 점프 테이블 이라는 곳에 차례대로 저장해놓는다.
우리는 다음의 switch문을 어셈블리어로 컴파일해볼 것이다.
참고로 함수의 인자는 각각 차례대로 %rdi, %rsi, %rdx에 저장된다. 밑의 사진에서 cmpq $6 을 하는 이유는 우리의 case중 제일 높은게 6이였기 때문이다.
ja 는 x > 6인 경우 점프한다. 이때 unsigned 비교를 하기 때문에 x가 음수인 경우 x는 unsigned로 아주 큰 수가 되어 x > 6이 된다. 따라서 x > 6이거나 x < 0 인 경우 점프를 한다고 할 수 있겠다.
jmp *.L4(,%rdi,8) 은 아까 말했던 점프테이블 (여기서 *.L4는 .L4의 주소를 의미한다)을 보고 적절한 코드블록의 주소로 점프한다.
잘 보면 그냥 메모리 식이다. 8 * Mem[%rdi] + Mem[L4]가 되어, L4의 어떤 오프셋 주소를 가리킨다고 이해하면 된다.
컴파일러는 또 점프테이블을 다음과 같이 생성한다.
.quad는 그 자리에 8바이트 수가 필요하다는 거고 .L8은 .L8의 메모리가 나중에 정해지면 이곳에 온다는 뜻이다.
각 줄은 switch문에서 x가 특정 값일때 어느 코드 블록을 실행시켜야 하는지에 대응한다.
잘 보면 x = 0일때와 x = 4일때의 코드블록이 L8로 같다. x = 5 와 x = 6일때도 같다. 이건 버그일까?
아니다. 원래의 switch문을 보면 x = 0인 case가 없으므로 x = 0은 default와 같은 코드 블록으로 가게 되고, case 5인 경우에는 break문이 없으니 폴스루가 되어 case 6과 같은 코드를 실행하게 된다.
각각의 코드 블록에는 우리가 아는 어셈블리 코드가 적혀 있다.
이렇게 switch문은 다른 제어문과는 다르게 점프테이블이라는걸 생성해 구현된다는걸 알게 되었다.
switch문을 컴파일할때 왜 이렇게 복잡해보이는 방식을 쓰는걸까?
첫번째 이유는 성능 향상이다. 점프 테이블을 쓰지 않는다면 cmp와 jmp명령어를 반복해서 쓸텐데, 이건 if문을 여러번 쓰는것과 크게 다르지 않다.
switch(x)에 n개의 case가 있다면 최악의 경우 n번의 조건을 비교해야 하므로 O(n)인데 반해, 점프 테이블은 x가 점프테이블의 어디에 속해있는지 비교를 한번만 하면 되므로 O(1)이다. (맞는 설명인지 잘 모르겠다. 잘 아는 사람이 있다면 댓글로 추가 설명을 부탁함...)
오늘 나간 진도는 CSAPP 3.1 ~ 3.6장이고 강의영상 05, 06에 해당한다. 더 자세히 알고 싶다면 책을 읽어보면 도움이 될 것이다.
궁금하거나 이해 잘 안되는거 있으면 댓글로 물어보면 내가 아는선에서 최대한 답변해줄테니 많이 물어봐라. 근데 나도 배우는 입장이라 정확하지 않을 수 있다.
긴글 읽어줘서 고맙고 이로써 여러분은 두번째 실습인 폭탄랩(bomblab)을 시작하기 위한 최소한의 지식이 주어졌다.
다음에는 두번째 실습인 폭탄랩과 gdb를 다루는 법을 배워보자.
