Building a Simple Linker in Go

Understanding how code is linked together is fundamental to comprehending the software development process. This challenge involves building a simplified linker in Go, which takes compiled object files and combines them into a single executable program. This exercise will deepen your knowledge of symbol resolution, relocation, and the structure of executable formats.

Problem Description

Your task is to implement a rudimentary linker that can process multiple object files and produce a linked executable. The linker needs to perform two primary functions:

1. Symbol Resolution: Identify and resolve all external symbols. This means ensuring that every symbol defined in one object file and used by another is correctly mapped to its definition.
2. Relocation: Adjust memory addresses in the code and data sections of object files to reflect their final positions in the combined executable.

For this challenge, we will assume a simplified object file format. Each object file will contain:

• Code Section: Raw machine code.
• Data Section: Raw initialized data.
• Symbol Table: A list of symbols defined or referenced by this object file. Each symbol will have a name, type (e.g., "global", "local"), and its address or offset.
• Relocation Entries: Instructions for the linker to modify code or data based on symbol addresses. For simplicity, we'll focus on relocation entries that update absolute addresses.

The linker will take a list of object file paths and produce a single output executable file. The output executable will essentially be a concatenation of the code and data sections of the input object files, with addresses adjusted by the linker.

Examples

Example 1: Simple Function Call Between Two Files

Let's assume we have two simplified object files: main.o and utils.o.

utils.o (Conceptual Structure):

• Code Section: [0x10 push rbp, 0x11 mov rsp, rbp, ..., 0x25 mov eax, 1, ..., 0x30 ret]
  • Contains a function add_one starting at address 0x20.
• Symbol Table:
  • add_one: type="global", address=0x20

main.o (Conceptual Structure):

• Code Section: [0x10 push rbp, 0x11 mov rsp, rbp, ..., 0x25 mov edi, 5, 0x28 call add_one, ..., 0x30 ret]
  • Calls add_one at address 0x28.
• Symbol Table:
  • (No global symbols defined)
• Relocation Entries:
  • At address 0x28 (within the call instruction), there's a relocation entry for symbol add_one. This entry indicates that the address 0x28 needs to be updated with the actual address of add_one.

Input: linker main.o utils.o -o program

Output: program (a single executable file)

Explanation: The linker will:

1. Load utils.o and main.o.
2. Observe that main.o calls add_one which is defined in utils.o.
3. Determine the final address of add_one after all sections are laid out. Let's say utils.o's code starts at 0x1000 and main.o's code starts at 0x2000.
   • add_one's actual address in the final executable would be 0x1000 + (0x20 - 0x10) = 0x1010.
   • The call instruction at 0x28 in main.o needs to be updated to 0x1010. So, the instruction at 0x2000 + (0x28 - 0x10) = 0x2018 will be modified.
4. The output program will contain the concatenated code sections with the call instruction correctly updated to jump to the add_one function.

Example 2: Data Usage and Symbol Resolution

data_producer.o (Conceptual Structure):

• Data Section: [0x00 'H', 0x01 'e', 0x02 'l', 0x03 'l', 0x04 'o']
  • Contains a string "Hello" starting at data offset 0x00.
• Symbol Table:
  • greeting_message: type="global", section="data", offset=0x00

data_consumer.o (Conceptual Structure):

• Code Section: [0x10 push rbp, ..., 0x20 mov esi, greeting_message, ..., 0x30 ret]
  • Loads the address of greeting_message into esi at address 0x20.
• Symbol Table:
  • (No global symbols defined)
• Relocation Entries:
  • At address 0x20 (within the instruction loading greeting_message), there's a relocation entry for symbol greeting_message.

Input: linker data_producer.o data_consumer.o -o my_app

Output: my_app

Explanation: The linker will:

1. Load data_producer.o and data_consumer.o.
2. Identify that data_consumer.o references greeting_message defined in data_producer.o.
3. Allocate space for data. Let's say data_producer.o's data starts at 0x8000 and data_consumer.o's code starts at 0x1000.
   • The greeting_message will reside at 0x8000 + 0x00 = 0x8000.
   • The instruction at 0x20 in data_consumer.o (which is at actual address 0x1000 + (0x20 - 0x10) = 0x1010) needs to be updated to load the address 0x8000.
4. The output my_app will have the combined code and data, with the instruction correctly referencing the greeting_message at its final location.

Constraints

• Input Object Files: Assume a custom, simplified object file format. You will need to define this format yourself (e.g., using Go structs or encoding/gob). This format should be able to represent code, data, a symbol table, and relocation entries.
• Symbol Naming: Symbol names will be strings.
• Relocation Types: Focus on absolute address relocation for code references (e.g., function calls, jumps) and data references.
• Memory Model: Assume a flat memory model where code and data sections are placed contiguously. The linker should decide the order and starting addresses of these sections.
• Error Handling: Implement basic error handling for cases like undefined symbols or invalid object file formats.
• Performance: For this challenge, focus on correctness over extreme performance.

Notes

• You will need to design your own simplified object file format. Consider how you'll represent byte arrays for code/data, symbol tables (name, type, address/offset), and relocation entries (address to fix, symbol name).
• The linker needs to maintain a global symbol table of all symbols defined across all input object files.
• When laying out sections, the linker will need to determine the final starting address of each section (code, data) from each object file.
• Relocation entries will tell the linker where in the code or data to apply an address fix and which symbol's address to use.
• Think about the order in which you process files and resolve symbols. A common approach is a multi-pass linker.
• This is a simplified model. Real-world linkers handle many more complexities like different relocation types, section alignment, libraries, dynamic linking, etc.