[컴퓨터 구조] MIPS 기반 컴퓨터 명령어 체계(3)

4 minute read

MIPS

Linking Object Modules

실행 파일(Executable Image)을 만들기 위한 링커(Linker)의 역할

주요 작업

1. Merge segments(세그먼트 병합)

여러 개의 오브젝트 파일을 하나로 결합할 때, .text, .data, .bss 같은 세그먼트를 합친다.
예: main.o의 .text와 math.o의 .text를 합쳐 하나의 실행 가능한 .text 세그먼트를 만든다.

2. Resolve Labels(심볼 주소 결정)

전역 함수나 변수 등의 심볼(label)의 실제 주소를 결정한다.
예: 함수 foo()의 위치가 컴파일 당시에는 모르지만, 링크 시 결정되어 해당 위치로 점프하게 패치된다.

3. Patch location-dependent and externel references(주소 종속 및 외부 참조 수정)

명령어 중 일부는 메모리 주소에 따라 변하는데, 이걸 실제 주소로 수정한다.
다른 파일에 정의된 함수/변수를 참조할 경우 그 위치도 패치한다.
이전에는 링커가 모든 위치 종속을 고쳐야 했지만, Relocating Loader가 일부를 맡을 수도 있었음
하지만 오늘날에는 가상 메모리(Virtual Memory) 덕분에, 프로그램은 고정된 가상 주소에 로드할 수 있어서 이 작업이 단순해졌다.

Loading a Program(프로그램 로딩)

디스크에 저장된 실행 이미지를 메모리에 적재하여 실행 가능하게 만드는 과정

로딩 단계

1. Read header to determine segment sizes

실행 파일 헤더에서 .text, .data, .bss의 크기 등 정보를 읽는다.

2. Create virtual address space

OS가 프로세스마다 고유한 가상 주소 공간을 생성한다.

3. Copy segments into memory(or use lazy loading)

.text와 초기화된 .data는 메모리에 복사
또는 실제 접근 시 로딩(lazy loading, demand paging)되도록 페이지 테이블 설정

4. Set up stack with program arguments

명령줄 인자(예: argc, argv)를 스택에 설정

5. Initialize registers

스택 포인터 $sp, 프레임 포인터 $fp, 전역 포인터 $gp 등을 초기화

6. Jump to startup routine

런타임 초기화 코드로 점프
여기서 main(argc, argv)를 호출한다.
main()이 종료되면 시스템 호출을 통해 프로세스를 종료시킨다.
시작 루틴(Startup routine): C언어 기준으로 _start() 같은 함수가 여기에 해당한다. 라이브러리 초기화도 여기서 이루어진다.
.bss 세그먼트는 초기화된 데이터가 없기 때문에 실제로 메모리에서 0으로 초기화만 된다.

Dynamic Linking(동적 링킹)

라이브러리를 실행 중 필요한 시점에 링크하여 사용하는 기법

장점 및 작동 방식

Link/load only when needed : 함수가 호출될 때 해당 라이브러리를 로딩(예: dlopen(), dlsym() 등 사용)
Requires relocatable code : 메모리 주소가 달라져도 실행 가능하도록 코드가 작성되어야 한다.(PIC: Position-Independent Code)
Avoids image blaot : 정적 링킹(static linking)은 참조된 모든 코드가 실행 파일에 포함되어 커지지만, 동적 링킹은 필요할 때만 로딩하여 크기를 절약한다.
Automatic library version updates : 시스템에 설치된 최신 버전의 라이브러리를 자동 사용. 보안 패치 적용에도 유리하다.
.so(shared object, 유닉스) 또는 .dll(windows) 파일이 동적 라이브러리이다.
OS의 dynamic linker/loader가 실행 중에 해당 라이브러리를 찾고 메모리에 로딩한다.
단점 : 실행 중 라이브러리가 없거나 버전이 맞지 않으면 오류 발생 가능
전체 흐름 요약

Alt text

MIPS 버블 정렬 예제 분석 (Assembly)

C Code

void swap(int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

void sort(int v[], int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = i-1; j >= 0 && v[j] > v[j+1]; j--) {
            swap(v, j);
        }
    }
}

swap 함수 어셈블리 분석(leaf procedure)

void sort(int v[], int n) {
    int i, j;
    for (i = 0; i < n; i++) {
        for (j = i-1; j >= 0 && v[j] > v[j+1]; j--) {
            swap(v, j);
        }
    }
}

$a0 : 배열 v, $a1 : 인덱스 k, $t0 : temp 저장용, $t1 : v[k]의 주소, $t2 : v[k+1] 값

swap:
  sll $t1, $a1, 2       # $t1 = k * 4 (int는 4바이트니까 offset 계산)
  add $t1, $a0, $t1     # $t1 = &v[k]
  lw  $t0, 0($t1)       # temp = v[k]
  lw  $t2, 4($t1)       # $t2 = v[k+1]
  sw  $t2, 0($t1)       # v[k] = v[k+1]
  sw  $t0, 4($t1)       # v[k+1] = temp
  jr  $ra               # return

v[k]와 v[k+1]의 주소를 구하고 값을 반환
leaf procedure이므로 스택을 사용하지 않는다.(함수 호출 없음)

Procedure Body

# Move params
  move $s2, $a0          # save v[] in $s2
  move $s3, $a1          # save n in $s3
  move $s0, $zero        # i = 0

for1tst: # outer loop
  slt $t0, $s0, $s3      # if i < n -> $t0 = 1
  beq $t0, $zero, exit1  # if i >= n, go to exit1

  addi $s1, $s0, -1      # j = i - 1

for2tst: # inner loop
  slti $t0, $s1, 0       # if j < 0 -> $t0 = 1
  bne $t0, $zero, exit2  # if j < 0, exit inner loop

  sll $t1, $s1, 2        # t1 = j * 4
  add $t2, $s2, $t1      # t2 = &v[j]
  lw $t3, 0($t2)         # t3 = v[j]
  lw $t4, 4($t2)         # t4 = v[j+1]
  slt $t0, $t4, $t3      # if v[j+1] < v[j]
  beq $t0, $zero, exit2  # if not, exit inner loop

# pass params & call
  move $a0, $s2          # pass v[] to swap
  move $a1, $s1          # pass j to swap
  jal swap               # call swap(v, j)

# inner loop
  addi $s1, $s1, -1      # j--
  j for2tst              # repeat inner loop

exit2: # outer loop
  addi $s0, $s0, 1       # i++
  j for1tst              # repeat outer loop

Full Procedure

sort:
  addi $sp, $sp, -20     # make room on stack for 5 registers
  sw   $ra, 16($sp)      # save $ra on stack
  sw   $s3, 12($sp)      # save $s3 on stack
  sw   $s2, 8($sp)       # save $s2 on stack
  sw   $s1, 4($sp)       # save $s1 on stack
  sw   $s0, 0($sp)       # save $s0 on stack

  # ... procedure body ...

exit1:
  lw   $s0, 0($sp)       # restore $s0 from stack
  lw   $s1, 4($sp)       # restore $s1 from stack
  lw   $s2, 8($sp)       # restore $s2 from stack
  lw   $s3, 12($sp)      # restore $s3 from stack
  lw   $ra, 16($sp)      # restore $ra from stack
  addi $sp, $sp, 20      # restore stack pointer
  jr   $ra               # return to calling routine

Share on

Twitter Facebook LinkedIn

Yeontachi