시스템 프로그래밍 5. 어셈블리 프로그래밍

건국대학교 시스템 프로그래밍 진현욱 교수님의 수업을 정리한 내용입니다.

Languages

High Level Language => C, Java 사람의 관점에 가깝게 생각할 수 있는 언어이다.

Low Level Language => Assembly, Binary CPU의 관점에 가깝게 생각하는 언어이다.

따라서, 어셈블리를 사용하려면 CPU가 어떻게 동작하는지 알고 있어야한다.

CPU 동작 구조

Program Counter (PC) 는 Memory의 Code 부분을 한줄 한줄 읽어가며 명령어를 실행한다.

CPU에서 명령어를 처리하고, 연산을 하려면 Register에 값을 가져와야 한다.

따라서 Memory에 값을 요청해서 Register에 값을 가져와야 한다. 값을 가져오면, 연산을 수행하고 다시 Register에서 Memory에 값을 쓴다. 값들은 BUS라는 통로를 거쳐 주고받아진다.

Assembly’s Type

High Level Language에서는 변수라는 Box에 이름을 붙여서, 그 이름으로만 접근이 가능하다.

하지만 Assembly Language에서는 Box 그 자체에 접근이 가능하다.

• %{register} : 레지스터에 접근한다. ex) %rax
• (%{register}) : 레지스터에 들어있는 주소를 통해 메모리에 접근한다. ex) (%rbx)
• $${숫자} : 상수값. ex) \(-533 = -533,\)0x10 = 16

Register

Interger Register

• %rax : 산술 연산 용도에 사용.
• %rbx : 자유롭게 사용 가능.
• %rcx : 반복문 Count 저장할 때 사용. 또는 산술 연산 용도로 사용.

• %rdx : 산술 연산 용도에 사용. (큰 데이터)

• %rsi : 시작지 Index를 저장할 때 사용.

• %rdi : 목적지 Index를 저장할 때 사용.

• %rsp : 스택 메모리 영역의 Top 위치를 저장할 때 사용. 접근을 안하는게 좋다.
• %rip : 현재 CPU가 실행중인 메모리 주소. Program Counter. 접근을 안하는게 좋다.

• %rbp : 스택의 시작 위치.

• %r8 … 15 : 64bit Processor에서만 사용 가능. %8과 %9는 함수 호출시 매개변수로 사용될 수 있고, %10 ~ %15는 니 마음대로 써도 된다.

만약 32bit 환경이라면, r -> e로 바꾼다. (ex. rax -> eax)

[!tip] 서로 다른 함수끼리 레지스터의 값을 공유할까?{title} 아니.

만약 main 함수를 실행하다가 함수를 실행해야 되면, main 함수에서 작업중이던 Register을 메모리에 잠깐 저장해두고,

함수로 진입하면, 함수 입장에서는 깔끔하게 정리된 Register를 사용하게 된다.

Memory

(%rax)는 사실 메모리 주소를 표현하는데 있어 가장 많이 생략된 것이다.

일반적인 메모리 주소는 다음과 같다.

MATH_BLOCK_0

\(D\) : displacement (변위)값. 메모리 주소에 더해지는 상수 Offset이다. 1, 2, 4만 가능. \(rb\) : Base Register. 16개 Interger Register를 사용 가능. \(ri\) : Index Register. Base Register 주소에 더해지는 주소 Offset이다. \(S\) : Scale 값. Index Register에 곱해진다. 1, 2, 4, 8만 가능.

실제 메모리 주소는 다음과 같이 결정된다.

MATH_BLOCK_1

[!example] 4(%rbx, %rsi, 2){title} 메모리 주소 %rbx + 2 * %rsi + 4에 접근한다.

만약 %rdx = 0xf000, %rcx = 0x0100이라면

• 0x8(%rdx) = 0xf000 + 0x8 = 0xf008
• (%rdx, %rcx) = 0xf000 + 0x100 = 0xf100
• (%rdx, %rcx, 4) = 0xf000 + 4 * 0x100 = 0xf400
• 0x80(,%rdx,2) = 2 * 0xf000 + 0x80 - 0x1e080

[!example] (%rbx){title} 메모리 주소 %rbx에 접근한다.

Assembly’s Command

movq Source, Dest

데이터를 이동시키는 명령어.

[!example] 사용 예제{title}

1. moveq $$-147, (%rax) : 메모리에 상수값 저장. *p = -147 와 같음.
2. movq $$0x4, %rax : 레지스터에 상수값 저장.
3. movq $$rax, (%rax) : 메모리에 레지스터 값 저장.
4. movq %rax, %rdx : 레지스터에 레지스터 값 저장.

5. movq (%rax), %rdx : 레지스터에 메모리 값 저장.

6. movq (%rax), (%rbx) : 불가능하다. 메모리에서 메모리로 데이터를 바로 이동할 순 없으며, 레지스터를 무조건 거쳐야 한다. (메모리 -> 레지스터 -> 메모리)

[!example]- Swap 예제{title}

void swap(long *xp, long *yp)
{
    long t0 = *xp;
    long t1 = *yp;
    *xp = t1;
    *yp = t0;
}

이 C코드를 어셈블리로 바꾸면 어떻게 작성될까?

swap:
    movq   (%rdi), %rax
    movq   (%rsi), %rdx
    movq   %rdx, (%rdi)
    movq   %rax, (%rsi)
    ret

ret = return;

함수의 매개변수는, 총 6개까지 다음 레지스터에 저장된다.

• 첫 번째 매개변수 → %rdi
• 두 번째 매개변수 → %rsi
• 세 번째 매개변수 → %rdx
• 네 번째 매개변수 → %rcx
• 다섯 번째 매개변수 → %r8
• 여섯 번째 매개변수 → %r9

따라서 *xp와 *yp는 각각 (%rdi), (%rsi)에 저장되어 있으며, 이 저장된 값을 레지스터로 불러와서, 메모리 위치를 Swap하여 저장한다.

[!tip] Local Variable가 관리되는 방법{title} 앞에서 Local Variable은 메모리의 Stack 영역에 저장된다고 했는데, 여기서 보면 Local Variable을 메모리에 저장하지 않고, 레지스터 수준에서만 처리하고 있다.

Local Variable을 레지스터만으로 처리할 수 있으면, 그렇게 하도록 컴파일된다. 그게 훨씬 빠르니까!

Local Variable이 많아져 16개의 레지스터로 전부 처리할 수 없을때는, 어쩔 수 없이 메모리에 값을 저장해서 불러왔다가 저장했다가 왔다갔다 하면서 사용한다.

이때 사용되는 메모리 영역이 Stack이다.

movzbl Source, Dest

Mov Zero Byte Long, 데이터를 작은 크기의 레지스터에서 큰 크기의 레지스터로 옮길 때 사용한다. 상위 비트를 0으로 확장한다.

Arithmetic Operations (산술 연산 명령어)

이항 연산

• addq Source, Dest : Dest = Dest + Src
• subq Source, Dest : Dest = Dest - Src
• imulq Source, Dest : Dest = Dest x Src

단항 연산

• incq Dest : Dest += 1
• decq Dest : Dest -= 1
• negq Dest : Dest = -Dest
• notq Dest : Dest = ~Dest

Condition Codes를 바꾼다.

Condition Codes

• CF : Carry Flag : 전의 연산이 Carry가 있으면 1, 아니면 0.
• SF : Sign Flag : 전의 연산의 결과가 음수면 1.
• ZF : Zero Flag : 전의 연산의 결과가 0이면 1.
• OF : Overflow Flag : Overflow 발생시 1, 아니면 -.

연산이 수행되면 자동으로 바뀌는 Flag를 Condition Codes라고 한다.

[!question] What is Carry?{title} 덧셈에서 초과된 값을 상위로 올려보내거나, 뺄셈에서 상위 자리에서 1을 빌려오는 것을 Carry라고 한다.

1 + 1 = 10이므로 Carry 발생 100 - 001 = 011 (자리 내림 발생)이므로 Carry 발생

[!question] What is Overflow?{title} 연산의 결과가 범위를 넘어가 부호비트에 영향을 미치면 Overflow가 발생했다고 한다.

최대가 4bit인 타입이 있다고 해보자. 1000 + 1000 = 10000 => 0000, OverFlow가 일어나 부호비트가 바뀌었다.

0111 + 0001 = 1000, 이 경우도 부호 자리까지 연산이 넘친 경우이므로, Overflow가 일어난 것이다.

이는 어셈블리에서 조건문을 작성할 때 활용한다.

a와 b가 같은지 확인하는 방법은 a-b를 했을 때 ZF가 1인지 보면 된다. a>b인지 확인하는 방법은, b-a 했을 때 SF가 1인지 보면 된다.

Compare Instruction (비교 연산자)

• cmpq Source, Dest

Dest - Source 연산만 진행하고, 결과는 버린다. Condition Codes값만 관심 있을 때 쓰면 된다.

Reading Condition Codes (setX)

Condition Codes 조건에 따라 레지스터의 low-order byte 값을 바꾼다.

• setX $$al : %rax의 최하위 비트를 Condition Code 값으로 덮어쓴다.
  • sete : Equals / Zero(ZF)
  • setne : Not Equals / Not Zero (~ZF)
  • sets : Negative (SF)
  • setns : Nonnegative (~SF)
  • setg : \(>\) Greater (Signed) (~(SF^OF) & ~ZF)
  • setge : \(\geq\) Greater or Equal (Signed) (~(SF^OF))
  • setl : \(<\) Less (Signed) ((SF^OF))
  • setle : \(\leq\) Less or Equal (Signed) ((SF^OF) | ZF)
  • seta : Above (Unsigned) (~CF & ~ZF)
  • setb : Below (Unsigned) (CF)

[!example] setg{title} cmp %rax, %rbx setg %al

%rax와 %rbx를 비교 %rax > %rbx이면 %al = 1, 그렇지 않으면 %al = 0

[!example] 비교 결과를 리턴{title}

int gt (long x, long y)
{
    return x > y;
}

어셈 블리로 바꾸면 다음과 같다.

cmpq %rsi, %rdi
setg %al
movzbl %al, %eax
ret

반환해야 하는 값이 4바이트, 즉 32비트인 int 타입이므로 movzbl를 사용해서 32비트 레지스터인 %eax에 넣는다.

low-order byte

레지스터의 8개 비트 중, 첫번째 비트만 사용하는 것을 의미한다.

%rax의 첫번째 bit = %al

Jumping Instructions (jX)

Condition Codes 조건이 맞으면 프로그램의 특정 Label 또는 메모리 주소로 점프한다.

• jX label : 조건 성립시, label로 점프한다.
  • jmp : 무조건 점프
  • je : Equals / Zero (ZF)
  • jne : Not Equals / Not Zero (~ZF)
  • js : Negative (SF)Nonnegative (~SF)Nonnegative
  • jg : \(>\) Greater (Signed) (~(SF^OF) & ~ZF)
  • jge : \(\geq\) Greater or Equal (Signed) (~(SF^OF))
  • jl : \(<\) Less (Signed) ((SF^OF))
  • jle : \(\leq\) Less or Equal (Signed) ((SF^OF) | ZF)
  • ja : Above (Unsigned) (~CF & ~ZF)
  • jb : Below (Unsigned) (CF)

[!example] Example{title}

cmp %rax, %rbx    # %rax와 %rbx를 비교
je equal_label  # 같으면(equal) equal_label로 점프

Label

프로그램의 특정 지점(메모리 주소)를 가리키는 이름이다. 메모리 주소에 이름을 붙인다고 생각해도 될 듯.

start:              # 레이블 start
    cmp %rax, %rbx  # %rax와 %rbx를 비교
    je equal_label  # 두 값이 같으면 equal_label로 점프
    jne not_equal   # 두 값이 다르면 not_equal로 점프
    ...
equal_label:        # 레이블 equal_label
    ; 여기에 도착하면 두 값이 같음
    ; equal일 때 수행할 코드
    jmp end         # end 레이블로 점프
not_equal:          # 레이블 not_equal
    ; 여기에 도착하면 두 값이 다름
    ; not equal일 때 수행할 코드
end:                # 레이블 end
    ; 종료

Bit Operation (비트 연산자)

• salq Source, Dest : Dest = Dest << Src
• sarq Source, Dest : Dest = Dest >> Src
• shrq Source, Dest : Dest = Dest >> Src
• xorq Source, Dest : Dest ^ Src
• andq Source, Dest : Dest & Src
• orq Source, Dest : Dest | Src

[!question] sarq와 shrq의 차이는 무엇인가?{title} Shift Aithmetic(산술적) Right Quadword Shift Logical(논리적) Right Quadword

한칸씩 오른쪽으로 밀면, 왼쪽에 빈자리를 1 또는 0으로 채워야하는데, 이 방법에서 차이가 있다.

산술 쉬프트 연산은, 부호를 유지한다. 음수일 땐 1로 채우고, 양수일 땐 0으로 채운다. 논리 쉬프트 연산은, 무지성으로 0으로 채운다.

[!question] salq가 있으면 shrq는 없냐?{title} 오른쪽의 빈자리는 딱히 부호를 신경쓰거나 그런게 없어서, salq shrq 둘다 0으로 채운다.

Condition Codes를 바꾼다.

leaq Source, Dest

주소값을 계산해 저장하거나, 산술 연산을 최적화하는데 사용한다. Source = D(rb, ri, S). 다음과 같이 계산된다.

MATH_BLOCK_2

[!example] leaq (%rdi, %rdi, 2), %rax{title}

MATH_BLOCK_3

와 같다.

leaq 명령어는 D(rb, ri, S)가 Source로 들어오면, 약속된 방법으로 연산하고 Dest에 저장할 뿐인 연산이다.

그 연산을 우리가 의미부여해서 메모리 주소를 계산한다 라고 생각해도 되고, 그저 연산을 위해 써먹어도 된다.

[!example] return x * 12;{title}

leaq (%rdi, %rdi, 2), %rax  // t <- x+x*2
salq $$2, %rax     // return t<<2

그냥 산술 연산자 imulq $$12 %rax 쓰면 되는거 아니냐? 왤캐 복잡하게 해?

=> imulq 연산 자체가 무거운 연산이다. 따라서 컴파일러는 이 연산을 사용하지 않기 위해 애쓴다.

그 애쓴 결과가 이것.

★ Condition Codes를 바꾸지 않는다

pushq, popq, call

스택을 사용하고, call는 함수를 호출하는 명령어다.

• pushq Src
• popq Dest

Stack Memory는 Virtual Addres Space의 스택 영역에 저장된다. Stack Memory의 데이터는 위에서부터 아래로 차곡차곡 쌓인다.

Push하면, Top 메모리 주소보다 더 밑의 메모리에 쌓이며, Top 메모리 주소가 바뀐다.

Top 메모리 주소는 %rsp 레지스터가 항상 저장하고 있다.

Pop을 하면, %rsp 메모리 주소가 위로 올라간다. 즉 +가 더해진다.

[!tip] 스택의 사용 용도{title} Stack은 세가지 용도로 사용된다.

1. Function Address Stack (돌아갈 함수 주소 저장해두기)
2. Register Stack (래지스터 백업 후 복원)
3. Pass Function parameters (함수의 인자 전달)

이 세가지 유형의 데이터는 하나의 Stack Memory에 저장된다. (Virtual Address Space의 Stack 영역에 위치함) 컴파일러는 적절한 순서를 지켜가며 Push Pop을 하기 때문에, 뒤섞이지 않고 데이터를 사용할 수 있다.

Example

void sumstore(long x, long y, long *dest)
{
    long t = plus(x, y);
    *dest = t;
}

sumstore:
    pushq   %rbx
    movq    %rdx,  %rbx
    call    plus
    movq    %rax,  (%rbx)
    popq    %rbx
    ret

왼쪽에 있는게 명령어들이고, 오른쪽에 % 붙어있는건 레지스터다.

함수를 호출할 때 Stack을 사용하기 때문에 pushq와 popq를 사용한다.

• pushq %reg : %reg 레지스터를 스택에 넣는다.
• popq %reg : %reg 레지스터를 스택에서 꺼낸다.
• movq %val %reg : %val 레지스터의 값을 %reg 레지스터에 복사한다.
• call func : 함수를 호출한다.
• ret : 리턴

%rbx 레지스터를 스택에 저장하고 dest의 주소를 %rbx에 저장 plus 함수를 호출하고 plus의 반환값을 *dest에 저장함. %rbx 레지스터를 스택에서 꺼내고 함수 종료.

조건문 (if, else) 구현 방법

어셈블리에서는 if, else와 같은 분기문이 없다. 대신 if, elseif, else와 같은 조건문은 goto문으로 똑같이 바꿀 수 있다.

if-else Version

long absdiff(long x, long y)
{
    long result;
    if (x > y)
        result = x-y;
    else
        reuslt = y-x;
    return result;
}

Goto Version

long absdiff_j(long x, long y)
{
    long result;
    int ntest = x <= y;
    if (ntest) goto Else;
    result = x-y;
    goto Done;
Else:
    result = y-x;
Done:
    return result;
}

이것과 똑같은 방법으로, 어셈블리에서는 goto를 사용해서 if-else를 구현한다.

Assembly Version

%rdi = x
%rsi = y
%rax = return value

absdiff:
    cmpq  %rsi, %rdi
    jle   .L4
    movq  %rdi, %rax
    subq  %rsi, %rax
    ret
.L4:    # x <= y
    movq  %rsi, %rax
    subq  %rdi, %rax
    ret

정리

val = Test ? Then_Expr : Else_Expr;

// 또는

if (Test)
    Then_Expr;
else
    Else_Expr;

To

    ntest = !Test;
    if (ntest) goto Else;
    Then_Expr;
    goto Done;
Else:
    Else_Expr;
Done:
    ...

Do-While 구현 방법

마찬가지로 어셈블리에는 for, while같은 Loop문이 없다.

따라서 재귀적으로 루프를 작성해야 한다.

do-while Version

long pcount_do(unsigned long x)
{
    long result = 0;
    do {
        result += x & 0x1;
        x >>= 1;
    } while (x);
    
    return result;
}

Goto Version

long pcount_goto(unsigned long x)
{
    long result = 0;
loop:
    result += x & 0x1;
    x >>= 1;
    if (x) goto loop;
    return result;
}

Assembly Version

%rdi = x
%rax = result

    movl   $$0, %eax   # result = 0
.L2:
    movq   %rdi, %rdx
    andl   $$1, %edx   # t = x & 0x1
    addq   %rdx, %rax # result += t
    shrq   $$1, %rdi   # x >>= 1
    jne    .L2        # if (x) goto loop
    ret

[!tip] >>= 연산자는 shrq vs sarq??{title} shrq는 컴파일러가 컴파일 과정에서 코드를 쭉 읽고 적절한 연산자를 선택한거임.

unsigned long x 라서 부호에 상관없이 logic shift를 사용하면 된다. 만약 long x였다면 sarq를 사용했을 것.

정리

do 
    Body
    while (Test);

To

loop:
    Body
    if (Test)
        goto loop

Function Call 구현 방법

함수를 호출받으면 다른 메모리 주소로 건너뛰어야 하고, 함수가 반환되면 원래 메모리 주소로 돌아와야 한다.

또, 함수 사이의 인자값, 리턴값도 넘겨줘야 한다. 이걸 어셈블리에서 어떻게 구현할까?

보라색 : Stack Memory %rsp : Stack의 Top 메모리 주소를 가리킴 %rip : Program Counter

callq는 stack에 다음 라인 메모리 주소, 위 예제에선 400549 Memory Address를 스택에 넣고 해당 메모리 주소로 넘어간다. movq $0x400550 %rip

[!tip] 이때, 레지스트 백업이 일어난다.{title} 레지스터는 모든 변수와 1대1 대응하기에는 부족한 숫자이기 때문에, 새로운 함수에서는 깨끗한 공간의 레지스터를 사용할 수 있게 해야한다.

이를 위해 두가지 방법이 존재함.

1. Caller-Saved : 호출하는 애가 레지스터를 백업해둔다. 함수를 부르기 전에, 내가 쓰던 레지스터를 스택에 미리 다 저장해두고 깔끔한 상태의 레지스터를 다음 함수에게 넘겨준다.

2. Callee-Saved : 호출받는 애가 레지스터를 백업해준다. 원래 함수가 쓰던 레지스터를 스택에 저장해두고, 깔끔한 상태의 레지스터를 사용하다가 리턴하기 전에 레지스터를 복원시키고 반환한다.

지금은 두가지 방법을 적절하게 혼합해서 사용한다. 컴파일러가 어떤 방법이 더 적절할지 판단해서 알아서 컴파일해준다.

[!question] 인자 값은 어떻게 보내는가?{title} 첫번째, 두번째, …, 6번째 인자는 순서대로 %rdi, %rsi, %rdx, %rcx, %r8, %r9 레지스터에 미리 담아서 함수를 호출한다.

x = add(x, y); =>

movq %rbx %rdi # x 인자값을 %rdi로 옮기기 movq %rdx %rsi # y 인자값을 %rsi로 옮기기 callq add

만약 인자가 6개가 넘어가면? 7개부터는 Stack에 넣어서 보낸다.

[!question] 왜 레지스터 스택 반반씩 사용해서 인자를 넘기는가?{title} Stack Memory는 Memory에 접근하기 때문에 레지스터에 접근하는 것보다 느리다. 그렇다고 인자값을 전부 다 레지스터로 전달하기엔 레지스터 개수가 부족하다. 따라서 적당하게 6개까지는 인자로 보내고, 그 이후부터는 스택을 사용하는 것이다.

반환값은 무조건 %rax에 넣자고 약속되어 있다.

따라서 함수를 호출하고 나면, %rax 레지스터에 저장된 값을 사용하면 된다.

이후 함수에서 retq를 만나면, stack에서 pop하여 원래 위치의 Memory Address를 찾아내 그 위치로 다시 이동한다. (popq %rax, movq %rax %rip)

[!example] Callee-Saved{title}

void multsotre(long x, long y, long *dest)
{
    long t = mult2(x, y);
    *dest = t;
}

이 함수가 호출되는 곳이 한곳밖에 없고, 그곳에서 Local Variable 하나를 %rbx에 담아서 사용하고 있는 경우, 컴파일러는 Callee-Saved를 사용한다.

0000000000400540 <multstore>:
    400540: push   %rbx             # 레지스터 공간 사용 전에, %rbx 백업.
    400541: mov    %rdx, %rbx
    400544: callq  400550 <mult2>
    400549: mov    %rax, (%rbx)
    40054c: pop    %rbx             # 반환 하기 전에, 레지스터 값 복원.
    40054d: retq