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가 실행 중에 해당 라이브러리를 찾고 메모리에 로딩한다.

• 단점 : 실행 중 라이브러리가 없거나 버전이 맞지 않으면 오류 발생 가능

• 전체 흐름 요약

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