Linker의 역할 - 2. Relocation(재배치)

일단 링커가 심볼 해석 단계를 완료하면, 코드 내 각 심볼 참조는 정확히 한 개의 심볼 정의에 연결되게 된다. (즉, 입력 목적 모듈 중 하나의 심볼 테이블 엔트리에 대응되게 된다). 이 시점에 링커는 입력 목적 모듈 들 안에 코드와 데이터 섹션들의 정확한 크기를 알고 있다. 이제 재배치 단계를 시작할 준비가 되었다. 해당 단계에서는 입력 모듈들을 합치고 각 심볼에 런타임 주소를 할당하게 된다.

재배치는 두 단계로 구성된다.

1. 섹션과 심볼 정의를 재배치한다.

이 단계에서 링커는 같은 종류의 모든 섹션들을 하나의 새로운 통합된 동일한 타입의 섹션으로 합친다. 예를 들어, 입력 모듈들의 .data 섹션들은 출력 실행 목적파일을 위한 한 개의 .data 섹션으로 합쳐진다. 

이후 링커는 런타임 메모리 주소를 새로운 통합된 섹션들, 입력 모듈들에 의해 정의된 각 섹션들, 입력 모듈들에서 정의된 각 심볼들에 할당한다. 이 단계가 마무리될 경우 프로그램 내의 모든 인스트럭션과 전역변수들은 유일한 런타임 메모리 주소를 가진다.

2. 섹션 내 심볼 참조를 재배치한다.

이 단계에서 링커는 코드와 데이터 섹션 내의 모든 심볼 참조들을 수정해서 이들이 정확한 런타임 주소를 가리키게 한다. 이 단계를 수행하기 위해서 링커는 재배치 엔트리라고 알려진 재배치 가능 목적 모듈들 안의 자료구조에 의존하게 된다.

심볼 참조의 재배치

typedef struct {
    int offset;     // offset of the field in the structure
    int symbol:24;  // symbol index 
    type: 8;        // type of the field
} Elf32_Rel;

foreach section s {
    foreach relocation entry r {
        ref = s + r.offset;
        if (r.type == R_386_PC32)
            refaddr = ADDR(s) + r.offset;
            *refptr = ADDR(r.symbol) + *refptr - refaddr;
            
        if (r.type == R_386_32)
            *refptr = ADDR(r.symbol) + *refptr;
    }
}

 

해당 코드는 링커의 재배치 알고리즘을 위한 의사코드를 보여준다. 두 번의 foreach 구문은 각 섹션와 각 섹션에 연결된 재배치 엔트리들에 대해 반복 실행된다.

설명의 편의성을 위해 각 섹션은 바이트들의 배열이고,  재배치 엔트리 r은 Elf32_Rel 타입의 구조체라고 가정한다. 또한 알고리즘이 실행될 때, 링커가 이미 각 섹션과 심볼[ADDR(r.s)]들을 위한 런타임 주소[ADDR(r.symbol)]를 선택했다고 가정한다.

이때 3 번째 줄의 ref = s + r.offset에서는 재배치될 필요가 있는 4 바이트 참조의 배열 s 내의 주소를 계산한다. 만일 이 참조(ref)가 PC-상대 주소 방식을 사용한다면, 이것은 아래 첫 번째 조건문에 해당하여 재배치된다. 만일 이 참조가 절대 주소방식을 사용한다면 이는 그 아래의 조건문에 의해 재배치된다.

앞서 자세히 설명하지는 않았지만 심볼 참조의 재배치를 수행하는 방법에는 여러 가지 방법이 존재한다. 해당 글에서 다루는 범위를 초과하여 담지는 못하였으나 대신 참조할 수 있는 링크를 첨부하며 마무리하고자 한다.

https://www.intezer.com/blog/malware-analysis/executable-and-linkable-format-101-part-3-relocations/