[SP]系統程式筆記3

Thu, 2019 Oct 10

3.1 Introduction

loader四大功能

allocation: 分配記憶體給程式
Linking: 處理external reference，重新解決符號參考(symbolic reference)
relocation: 調整 address-dependent，進行relocation調整
Loading: 將程式指令與資料放入記憶體

Linkage Editor

行為

obj and library -> linkage Editor -> Linked Program (disk file)

載入程式

Linked Program -> Relocation Loader -> Memory

Linking Loader

連結載入器直接連結obj file並載入記憶體執行

obj and library -> linking Loader  -> Memory

3.2 absolute Loader

載入程式時，會將程式擺放到固定的主記憶體絕對位置

四大功能分配

absolute loader只做loading不做linking與relocation

Loader: loader
programmer: Allocation, Linking
assembler: relocation

啟動載入器(Bootstrap Loader)

載入kernal載入到絕對記憶體位置，如BIOS

流程

開機產生啟動中斷
PC指向Bootstrap Loader的起始位置
Bootstrap Loader將kernal載入到主記憶體
轉交控制權給os
轉交command Interpreter, shell

3.3 program linking

連結

連結用於處理外部參考，修改紀錄當中採用&的外部參考必須進行連結。

如果有做relocation時記憶體，連結的obj會擺在前一個obj之後，並且對每個修改紀錄進行修改，而連結的部份則會填上連結obj的symbol位置

重定位relocation

處理程式起始位置的變化

修改紀錄來進行relocation
機器碼之前擺上relocation bit，每個bit標記nibble(1byte)需要修改，節省修改紀錄的空間
基底暫存器(Base register或segment register)進行relocation

備註，現代電腦原則上同時採用修改紀錄與基底暫存器進行relocation

連結檔案

relocation

address constant

simple relocation: (start addr1 + loc1) - (loc2)，通常為一個修改資料
複雜重定位: (start addr1 + loc1) - (start addr2 + loc2)，兩個起始位置不同的相減，兩個以上的修改資料，使用外部參考時需要重定位與連結，產生兩個以上的修改資料。
絕對定址: 兩個地址都被定義在同一個function中，並且相減的結果為absolute address，並且在組譯器處理階段即可處理，因此不會有修改資料。(start addr1 + loc1) - (start addr1 + loc2)

重點分析

如何判斷修改紀錄中是在進行linking或relocation的行為？透過是否使用外部參考進行判斷。

何得出原始程式碼的modification record?

如何知道絕對定址、連結與重定位、重定位？通常牽涉到外部參考的修改資料，大多都是連結與重定位，透過自生程式結尾下去計算的可以算出絕對位置。

3.4 Design Linking Loader

two passes Linking loader

pass1: 用來assign addresses每個object的external stmbols，找到所有的external address, 進行allocation
pass2: loading, reloaction, linking

資料結構

object program
external symbol table (ESTAB)
program Load address (PROGADDR):
Function address (FADDR): function應該要安排的位置

輸入資料

轉譯器(language translator)必須提供

T紀錄: 機器碼
H紀錄: 程式長度
D紀錄: public symbol
R紀錄: extrn symbol
M紀錄: modification record

可以去除紀錄

Program length: H紀錄
Extrn symbol: R紀錄

external symbol table

在pass1的時候產生external symbol table，內容為function與function內的D紀錄的地址找出。

pseudo code

pass1

void pass1() {
  faddr = progAddr = os.getProgAddr() // 從作業系統獲取分配的地址
  while (!eof) {
    func = file.headerRecord()
    flth = func.length
    
    find func.name in ESTAB then
      throw duplicate "External symbol"
    unfounded
      ESTAB[func.name] = func.addr

    while (recode.type != 'E') {
      file.nextRecord()
      if (record.type == 'D') {
        for (symbol in record) {
            find func.name in ESTAB then
              throw duplicate "External symbol"
            unfounded
               ESTAB[func.name] = func.addr + record.D.address
        }
      }      
    }
  }
}

pass2， loading, reloaction, linking，後兩者要從modification records找

void pass2() {
  faddr = execaddr = progAddr
  while (!eof) {
    func = file.headerRecord()
    flth = func.length

    while (recode.type != 'E') {
      file.nextRecord()
      if (record.type == 'T') {
        faddr[specified addr] =  file.objectCode()
      } else if (record.type == 'M') {
        // relocation and linking
        find modifyName in ESTAB then
          if ('+' or '-') {
            faddr[specified addr] =  + or -            
          } else {
            get offset of symbol location            
          }
        unfounded
          throw duplicate "External symbol"
      }
    }
  }
}

3.5 The other Loaders

The Other Loaders

Linking Loader: allocation, linking, relocation, loading
Linkage Editor: Allocation, linking, relocation(透過修改紀錄進行L&R)
Relocating Loader: allocation, relocation, loading

Linkage Editor備註: start address是透過allocation分配，如com檔案的起始位置0100，而relocation是在處理修改資料與起始位置所進行的工作。

現代系統大多採用Linkage Editor與Relocating Loader處理程式載入，

linkage Editor已經確定個別obj載入的位置

若電腦有relocation register(bash register, segment register)，是否能夠去除M紀錄？依然不可能完全去除

可以去除: 都是相同的start address
無法去除:
- complex relocation
- linking
- 負值的(-main)
- &符號需要連結

Dynamic Linker

直接執行main function，在執行時(run time)需要使用時在進行連結。 (binder 為 linker 的意思，也因此會有 lazy binding 這類的術語)

動態連結會浪費時間，降低程式執行效率，程式無法連結時會導致程式崩潰。

Overlay

早期電腦因為記憶體空間不夠因此需要overlay，共用兩個不會同時呼叫的function記憶體

System Program