Project Alexandria

4.3 Linker

3 min read

Linker

A linker is a specialized software tool in the build process that groups all *.o machine code files generated by the assembler into ordered code segments of a *.out executable and resolving all references to ensure that all symbols (such as functions and labels) are correctly linked to their addresses.

Note!

The RISC-V linker is static. Therefore, if a library is used, all of it will be included in the executable. If a library is added, the programmer will have to re-compile the executable.

Understanding

The linker is the third (and final) stage of the build pipeline. It is used to “link” all missing entries from a file’s relocation table with their addresses in other files and external libraries’ symbol tables. Usually, the addresses that need relocation include:

  • Absolute function addresses (using auipc/jalr).
  • External function references (using auipc/jalr, jal).
  • Static data references (using lui, addi).

By the end of the linker stage, all absolute addresses are linked. The linker then stores all machine code in one executable, grouping different code segments together. The following figure displays how two *.o files are linked into a single a.out file:

\begin{document}
\begin{tikzpicture}
 
    % .o file 1 nodes
    \node (o1) at (0, 1.75) {.o file 1};
    \node (text1) [draw, color=blue!50, minimum height=1cm, minimum width=2cm] at (0, 1) {Text 1};
    \node (data1) [draw, color=blue!50, minimum height=1cm, minimum width=2cm] at (0, 0) {Data 1};
    \node (info1) [draw, color=blue!50, minimum height=1cm, minimum width=2cm] at (0, -1) {Info 1};
 
    % .o file 2 nodes
    \node (o2) at (0, -3.25) {.o file 2};
    \node (text2) [draw, color=green!75, minimum height=1cm, minimum width=2cm] at (0, -4) {Text 2};
    \node (data2) [draw, color=green!75, minimum height=1cm, minimum width=2cm] at (0, -5) {Data 2};
    \node (info2) [draw, color=green!75, minimum height=1cm, minimum width=2cm] at (0, -6) {Info 2};
 
    % Linker node
    \node (linker) [draw, color=orange, minimum height=1cm, minimum width=2cm] at (4, -2.5) {Linker};
 
    % a.out nodes
    \node (aout) at (8, -0.2) {a.out};
    \node (reltext1) [draw, color=blue!50, minimum height=1cm, minimum width=2cm] at (8, -0.925) {Relocated Text 1};
    \node (reltext2) [draw, color=green!75, minimum height=1cm, minimum width=2cm] at (8, -1.975) {Relocated Text 2};
    \node (reldata1) [draw, color=blue!50, minimum height=1cm, minimum width=2cm] at (8, -3.025) {Relocated Data 1};
    \node (reldata2) [draw, color=green!75, minimum height=1cm, minimum width=2cm] at (8, -4.075) {Relocated Data 2};
 
    % Arrows from .o file 1 to linker
    \draw[->, very thick, orange] (info1.east) -- (linker.north west);
    \draw[->, very thick, orange] (text2.east) -- (linker.south west);
 
    % Arrows from linker to a.out
    \draw[->, very thick, orange] (linker.east) -- (reltext2.south west);
 
\end{tikzpicture}
\end{document}

We can infer the following steps that the linker takes:

  1. Take the text segments of each .o file in the program and gather them together.
    • Store the first word of the text segment at 0x10000 (0x40000000 for RV64).
  2. Take the data segment of each .o file, gather them together, and concatenate them to the end of the grouped text segment.
  3. Resolve all unknown references as seen above.
    • First, search in all program files’ symbol tables.
    • If not found, search library files.
  4. Generate the *.out executable, containing:
    • A header containing the size of the text and data segments.
    • The text and data segments themselves.

Graph View