In this chapter, we'll go step-by-step on how the Linker resolves an undefined symbol in an object file.
More specifically, we'll know what happens when we execute the following command:
link msvcrt.lib page.o
- The first step of the Linker will be to read the Symbol Table of page.o file to check for undefined symbols. Let's take the example of
__imp__GetSystemInfo@4to see how the Linker resolves it. (And just as a reminder, we can get the Symbol Table of page.o using the following command:dumpbin /symbols page.o) - As we've given msvcrt.lib Library file to the Linker, it starts with that. As shown previously, we can check the complete Linker logs here.
- There's an object file inside msvcrt.lib called initializers.obj. That object file has a few more Library files mentioned in it's .drectve Section.
We can actually check that ourselves. Extract the initializers.obj file from msvcrt.lib Library:
lib /extract:d:\a01\_work\38\s\Intermediate\vctools\msvcrt.nativeproj_110336922\objr\x86\initializers.obj /out:initialzers.obj msvcrt.lib
Next, view the .drectve Section:
dumpbin /section:.drectve /rawdata initialzers.obj
We can see that kernel32.lib, vcruntime.lib and ucrt.lib are mentioned as defaultlibs in .drectve Section.
Linker goes on to check all the libraries mentioned there for our undefined symbol __imp__GetSystemInfo@4. It finds our symbol in kernel32.lib Library.
- kernel32.lib is a DLL Import Library. It's purpose is to redirect the Linker to a DLL file when it comes looking for a symbol. So, how does the Linker know which DLL file to look for when it reads the kernel32.lib file?
- kernel32.lib file has the following structure:
The import libraries have a portion called Linker Member in the beginning of their file structure (this is true for .lib Standard Libraries as well). Followed by the Linker Member, there are a bunch of pseudo-object files in the Import Library (as opposed to Standard Libraries which have actual object files in them).
The kernel32.lib file is an Import Library that follows the structure shown in the diagram. (Also, Import Libraries can have two different file structures: Long format and Short format. The above diagram is a short format structure and kernel32.lib file follows that. You can see how the Long format Import Library structure looks like here).
The Linker first searches the Linker Member portion of the Import Library. The Linker Member consists of all the symbols that can be found in that Import Library and also the symbol's offset within the Import Library file where it is defined.
We can view the Linker Member part of the Import Library file using the dumpbin utility:
dumpbin /linkermember kernel32.lib
Output:
...
3966C _GetSystemFirmwareTable@16
3966C __imp__GetSystemFirmwareTable@16
396E4 _GetSystemInfo@4
396E4 __imp__GetSystemInfo@4
39752 _GetSystemPowerStatus@4
39752 __imp__GetSystemPowerStatus@4
...
View the entire output of the above command here.
From the above output, we can see that the file offset for the "__imp__GetSystemInfo@4" symbol is "396E4". So if we open the kernel32.lib file in a Hex editor and go the 0x396E4 position, we can see the following:
The above highlighted region indicates the Archive member header, Import header, Import symbol name ("_GetSystemInfo@4") and the DLL name ("KERNEL32.DLL"). If we have to compare that to the Import Library structure shown previously, then here's how the layout for kernel32.lib file looks like:
So, when the Linker is reading the kernel32.lib file, it gets the file offset value for the symbol "__imp__GetSystemInfo@4" from the Linker Member and jumps to that offset location in the file. At that location, it sees that the symbol is defined in kernel32.dll file!
(Also, "__imp__GetSystemInfo@4" and "_GetSystemInfo@4" are both aliases for "GetSystemInfo" symbol defined in kernel32.dll. And as we discussed in the previous chapter, __imp_ prefix indicates that the symbol needs to be imported from a DLL file and "_GetSystemInfo@4" is a Decorated Name.)
Now that the Linker (link.exe) knows the name of the DLL (kernel32.dll), which path does it search to find this kernel32.dll?
To know in detail, refer to the DLL search order article from Microsoft docs here: https://docs.microsoft.com/en-us/windows/win32/dlls/dynamic-link-library-search-order
Basically, one of the paths where the DLL file is searched is the System folder.
But there are two types of System folders on Windows:
System32 for 64-bit executables. SysWOW64 for 32-bit executables.
Let's see what's the type of our link.exe file.
To get the path of link.exe, where link.exe gives the following output: C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.31.31103\bin\Hostx86\x86\link.exe.
The Machine field of the PE file header gives the info about which machine is the exe meant to be run. We can check this using dumpbin like dumpbin /headers "C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.31.31103\bin\Hostx86\x86\link.exe".
We get the following output:
Dump of file C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Tools\MSVC\14.31.31103\bin\Hostx86\x86\link.exe
PE signature found
File Type: EXECUTABLE IMAGE
FILE HEADER VALUES
14C machine (x86)
5 number of sections
DC7BF8A1 time date stamp
0 file pointer to symbol table
0 number of symbols
E0 size of optional header
122 characteristics
Executable
Application can handle large (>2GB) addresses
32 bit word machine
...
...
So, we can see that link.exe is a 32-bit executable (x86) and hence it refers to SysWOW64 system folder to search for kernel32.dll file. And the complete path of this kernel32.dll file will be: C:\Windows\SysWOW64\kernel32.dll.
"Export Tables" is a generic name I've given to a bunch of tables that are present in the .edata Section of the DLL file. Although, it is not mandatory that Export Tables need to be in .edata Section and in many cases they are just found in .rdata Section. The location of Export Tables and Import Tables (we'll be discussing Import Tables shortly) are mentioned in the Optional Headers part of the PE file. And both the .exe executable and .dll file have PE format.
So, the Export Tables are a very important component of a DLL file as they let the Static Linker and the Dynamic Linker (Loader) know what symbols are available in the DLL file and at which offset within the file they can be found.
Export Tables are shown below:
The Export Name Pointer Table has an array of addresses (RVAs) that point to the symbol name strings. And the index to this array is referred to as a hint (there's a reason why it's called as a "hint" and not as an "index". We'll get back to this later.). This hint to this array is calculated by the linker in it's memory as it goes through the array searching for the symbol (and the symbol here being "GetSystemInfo").
Export Ordinal Table is just an index for the entire Export Address Table as shown in the diagram above.
And Export Address Table has the RVA of the entry points to all the functions present in the DLL.
We can view the Export Tables data using dumpbin:
dumpbin /exports C:\Windows\SysWOW64\kernel32.dll
The output will be like this:
....
ordinal hint RVA name
4 0 AcquireSRWLockExclusive (forwarded to NTDLL.RtlAcquireSRWLockExclusive)
5 1 AcquireSRWLockShared (forwarded to NTDLL.RtlAcquireSRWLockShared)
6 2 00020AC0 ActivateActCtx
7 3 00020400 ActivateActCtxWorker
....
....
745 2E6 00021910 GetSystemInfo
....
We'll explore how Export Ordinal Table and Export Address Table are used when we will be discussing the Loader.
But, all that our Static Linker (link.exe) wants from the DLL file at this stage is the hint value and the symbol name string. Although link.exe already has the symbol name (because it's searching for that name), it just tries to verify whether that symbol name is actually present in the DLL file and where can it be found in the file (the hint).
Read about Export Tables in more detail here if you're interested: https://docs.microsoft.com/en-us/windows/win32/debug/pe-format#the-edata-section-image-only
Once link.exe is done with scanning the DLL file for the symbol, it gets the DLL file name, hint value and the symbol name for further processing. Now it starts creating the final executable file.
The final executable should have file headers, optional headers (optional headers are "optional" for COFF object files but mandatory for PE executable files), Sections etc. all according to the PE file format. And PE format is a simple extension to the COFF format. But amongst all the things, one of the most important thing that the Linker creates in the exe file (once it is done scanning the Export Tables of the DLL file) is the Import Tables.
"Import Tables" is the generic name I've given to a bunch of tables that are present in .idata Section. Again, just like the Export Tables, it's not mandatory that Import Tables should be in a Section called .idata. The Import Tables are found in .rdata Section of the exe in most cases. The location of the Import Tables is governed by the Optional Headers of the PE format.
The Import Table and Export Table fields of the Optional Header of PE file gives the size and RVA of the starting point of "Import Tables" and "Export Tables" respectively.
When constructing the Import Tables, the Linker first creates an Import Directory Table where it puts a list of DLL file names as shown below.
Next, it creates the Hint-Name Table and puts the export hint and the symbol name it got when it was scanning the DLL file.
The RVA of that Hint-Name Table entry is put in another table called Import Lookup Table
Next, it creates the Import Address Table (IAT). The Static Linker (link.exe) has nothing to do with IAT at this stage so it just copies the contents of Import Lookup Table into IAT for now. IAT will be filled with actual Virtual Addresses of symbols by the Loader when this exe is executed. But that discussion will be done later.
Lastly, Linker puts the address (RVA) of Import Lookup Table and Import Address Table into Import Directory Table. After this, we'll have a scenario as shown in the above diagram!
Import Tables data can be viewed with dumpbin using the following command:
dumpbin /imports page.exe
Output:
....
KERNEL32.dll
402000 Import Address Table
4025E4 Import Name Table
0 time date stamp
0 Index of first forwarder reference
2E3 GetSystemInfo
44D QueryPerformanceCounter
218 GetCurrentProcessId
....
VCRUNTIME140.dll
402038 Import Address Table
40261C Import Name Table
0 time date stamp
0 Index of first forwarder reference
1C __current_exception
1D __current_exception_context
48 memset
35 _except_handler4_common
....
It is important to note that there is a single Import Directory Table (IDT), multiple Import Lookup Tables (one for each DLL mentioned in IDT) and there is one Hint-Name Table. The arrangement of Import Tables looks like this in the actual file:
And of course, lastly there is IAT whose contents will be written by the Loader and hence that table is usually shown separate from the above diagram.
All of these Import Tables are required by the Loader to load necessary DLLs and find required symbols in those DLLs when the exe is executed.
Read about Import Tables in more detail here if you're interested: https://docs.microsoft.com/en-us/windows/win32/debug/pe-format#the-idata-section
Another important task of a Static Linker is to combine all the required code and data from different object file Sections into the exe.
Now is the right time to discuss about CRT Initialization (C Runtime Initialization).
We have our main() function in page.o file. But the execution of code doesn't start from our main function when we run our exe. The Static Linker includes some startup code before our main function and that will be the entry point into our exe when it starts running. This startup code will then call our main function and after our main function has finished it's execution, there will be some cleanup code included by the Static Linker as well.
If we go through the Linker logs, we can notice that the Linker is looking for a symbol called _mainCRTStartup and that symbol is found in exe_main.obj object file of msvcrt.lib Library that we provided to the Linker. The CRT startup code includes some function calls that provide security features (like ___security_init_cookie() function that provides Buffer Overflow protection, _guard_check_icall() that provides Control-flow integrity etc.), other CRT initialization functions, CRT cleanup functions etc.
- Read more about CRT Initialization: https://docs.microsoft.com/en-us/cpp/c-runtime-library/crt-initialization
- More about
___security_init_cookie(): https://docs.microsoft.com/en-us/cpp/c-runtime-library/reference/security-init-cookie - See how Control-flow integrity or Control-flow Guard works: https://lucasg.github.io/2017/02/05/Control-Flow-Guard/ and the Microsoft docs article on that same topic: https://docs.microsoft.com/en-us/windows/win32/secbp/control-flow-guard
The PE Optional Header contains AddressOfEntryPoint field that has the RVA from where the execution should start. And this address will point to the starting point of the CRT initialization code included by the Linker as described previously and this won't point to our main() function (although, AddressOfEntryPoint can be changed by using certain Linker options). And all these header fields are included in the exe by the Linker itself (obviously).
Each function has it's own Section in the object files that are inside Standard Libraries (.lib files). When the Linker finds the function it's looking for, it copies the whole Section of that function and puts it in the exe.
Linker also copies the Sections of our page.o object file. All the code, from all the relevant Sections of library object files and page.o file, are combined and placed in a single .text Section of the exe. Relevant initialized data Sections from all these object files are stored in .data Section of exe. Certain Sections from our page.o file that are not necessary (like .drectve and .llvm_addrsig Sections) are not included in the exe. The Symbol Tables of object files are not necessary and are also not included in the exe (unless debug option is set to True).
Before the relevant Sections are included into the exe Sections, the Linker needs to do some modifications to these Sections.
At this stage, the Linker is able to resolve the undefined symbols (like function calls). The Linker also knows the location of these functions in the exe file because it is including those functions in the .text Section of that final exe as explained above. The Linker needs to update these function locations wherever they are referenced (i.e., wherever these functions are called).
For example, we are calling GetSystemInfo() function in our main() function (in page.c). The Assembler didn't know the location of GetSystemInfo(). But the Linker now knows that GetSystemInfo() is in kernel32.dll and it has put this information in Import Table earlier. Now the Linker needs to put the address of Import Address Table (IAT) entry of GetSystemInfo() into the main() function. Later when the exe is executed, the Loader will put the actual Virtual Address (VA) of GetSystemInfo() into our IAT and as we're referencing that IAT entry in main(), we'll make a call to GetSystemInfo() through IAT.
But how will the Linker knows where to modify these newly fetched function addresses? That's where the COFF Relocation Table comes in!
COFF Relocation Table is where the Assembler has included all the info of where the changes needs to be done in a Section if that Section is being included by the Linker into the exe.
Let's take the example of GetSystemInfo() function to see how COFF Relocation Table is used. As the Linker has the IAT entry address of GetSystemInfo(), it will refer to the COFF Relocation Table of that Section to know where to put the address of the IAT entry.
We can view the COFF Relocation table using the following command:
dumpbin /relocations page.o
COFF Relocation table entry looks like this
Symbol Symbol
Offset Type Applied To Index Name
-------- ---------------- ----------------- -------- ------
00000015 DIR32 00000000 2A __imp__GetSystemInfo@4
....
0000002D REL32 00000000 14 _printf
....
(View the entire COFF Relocation table of page.o file here!)
The Offset column says number of bytes (in Hexadecimal) from the start of the Section where the IAT entry address needs to be filled. The DIR32 says that the Linker needs to put the Direct (and not Relative) 32-bit Virtual Address at that location and that direct Virtual Address is the IAT entry address (which in turn contains the Address of the "GetSystemInfo" symbol). That "Applied To" column says what are the current bytes at that Offset. And the current value for all the undefined symbols or function addresses will be assigned zero by the Assembler. Symbol Index is the index in the Symbol Table.
Let's try to visualize this.
The Section Header gives us the information about where to find the Section and it's Relocation Table. By running dumpbin /headers page.o, we'll get the following output:
SECTION HEADER #1
.text name
0 physical address
0 virtual address
38 size of raw data
26C file pointer to raw data (0000026C to 000002A3)
2A4 file pointer to relocation table
0 file pointer to line numbers
3 number of relocations
0 number of line numbers
60500020 flags
Code
16 byte align
Execute Read
...
(View the entire output here.)
From the above output, we know that the 1st .text Section (where GetSystemInfo() is called) starts at a file offset of 0x26C and ends at 0x2A3. If we open page.o file in a Hex editor and go to 0x26C offset, we'll see the following:
The blue filled area is our Section data (from 0x26C to 0x2A3 file offset), 0x2A4 is where the Relocation Table for this Section is (as indicated in the above dumpbin Section header output) and is indicated by the blue outline in the above diagram.
The bytes highlighted in yellow is the entire instruction (it's a x86 CALL instruction) and the black outline within that yellow highlighted region is where the Linker puts the IAT entry address (that black outline is at an offset of 0x15 bytes from the beginning of the Section as given in the Relocation Table. 0x15 is 21 in decimal format. So if we count 21 bytes from the beginning of the Section in the above diagram, we'll reach the 00 00 00 00 where the address will be put by the Linker).
So, in the final exe, that FF 15 00 00 00 00 instruction looks something like FF 15 00 B0 D9 00 in the exe as shown below (it's the disassembled output of a running page.exe and captured in WinDbg debugger program):
(Again, that 0x00D9B000 address is the direct Virtual Address of the "GetSystemInfo" row in Import Address Table (IAT))
What's the difference between REL32 and DIR32 relocation types mentioned in the above COFF Relocation Table?
So, we have CALL x86 assembly instruction to invoke a function call.
But there are different types of CALL x86 assembly instructions.
For example, the Near, relative CALL instruction has an opcode of E8 (hex value) and the address mentioned for this type of CALL instruction needs to be relative to it's next instruction. This type of CALL instruction is used to transfer control to a function in the same object. And the REL32 type of relocation is applied here where the Linker needs to put in the relative address of the target (relative to the next instruction) as explained.
In page.s file, we have the following call instruction where the Near, relative CALL instruction is used:
call _printf
Then there is Far, absolute CALL x86 assembly instruction with an opcode of FF (hex value) and the address mentioned for this type of CALL instruction needs to be the direct or absolute address of the target function. And DIR32 type of relocation is applied here where the Linker needs to put the absolute address of the target. This type of relocation usually applies to functions that are in some other shared object.
In page.s file, we have the following CALL instruction where the Far, absolute CALL instruction is used:
call dword ptr [__imp__GetSystemInfo@4]
Hence for the symbol __imp__GetSystemInfo@4, the relocation type is mentioned as DIR32 and for the symbol _printf, the relocation type is REL32 as seen in the Relocation Table of that Section.
Once the Linker modifies the Sections according to the COFF Relocation Table, it places those Sections in the exe but doesn't include the COFF Relocation Table as it's not required anymore.
Instead, the Linker creates a new Section in the exe called .reloc where it places a different kind of Relocation Table called Base Relocation Table.
Every PE file (both the .exe and .dll file have PE format) has a preferred starting address in the memory where it wants the OS (the Loader) to load it. This preferred starting address (called the base address) can be found in the ImageBase field of the Optional Header of the PE file.
But most of the times, the PE file is not fortunate enough to get the preferred starting address it wanted. When referring to various symbols and locations (such as the Import Address Table row location), direct addresses are used. And when assigning these addresses to various symbols, Linker assumes that the starting address will be the ImageBase address it chose. For example, if the ImageBase address is 0x00400000 (chosen by the Static Linker), then the rest of the instructions will be at subsequent addresses and the reference to the GetSystemInfo function in the IAT will be somewhere, let's say, at 0x0046B388 (because the Relative Virtual Address (RVA) for the GetSystemInfo symbol in the IAT is 0x0006B388 and hence the Virtual Address (VA) will be 0x00400000 (Base Address) + 0x0006B388 (RVA) = 0x0046B388 (VA)). And in the CALL instruction, the Linker will have the reference to GetSystemInfo IAT entry as CALL DWORD PTR [0x0046B388]. And if the Base Address (0x00400000) changes, then 0x0046B388 address becomes invalid.
Hence, when the Loader loads the executable at a different starting address, most of the direct addresses hardcoded in the instructions become invalid. That's where a new Relocation Table called Base Relocation Table comes into play.
Base Relocation Table is created by the Linker and it indicates to the Loader about what all changes need to be performed if the Loader decides to load the image at an address other than the one mentioned in the ImageBase field. So, in a way, Base Relocation Table is similar to COFF Relocation Table but serves a different purpose and is meant to be used by the Loader (Operating System).
And just like the DIR32 and REL32 COFF Relocation types, we also have different types of Base Relocations.
Also note that Base Relocations are stored in a separate Section in the PE file called .reloc Section.
We can view the Base Relocation Table of page.exe file with the following command:
dumpbin /relocations page.exe
The output will be something like:
BASE RELOCATIONS #4
1000 RVA, 10C SizeOfBlock
15 HIGHLOW 00412000
21 HIGHLOW 00412160
95 HIGHLOW 004198B0
138 HIGHLOW 004018AD
...
...
In the above output, the 1000 RVA is the RVA relative to the Base Address. And the Offset (the value 15 in the row 15 HIGHLOW 00412000) is the offset relative to the RVA. HIGHLOW indicates the type of Relocation. HIGHLOW simply says that the Relocation must be applied both to the higher (first half of the value) and lower (last half of the value) bits of the target value.
00412000 indicates the current value at that location. And the location here will be 0x00400000 (Base Address) + 0x1000 (RVA, shown in the above output) + 0x15 (Offset, shown in the above output) = 0x00401015. So the value at 0x00401015 is 00412000 which must be modified by the Loader if the Base Address changes. And, if the Base Address changes, the Loader calculates the location (where the Relocation must be applied) in the same way as shown above. See the screenshot below to see where the Relocation takes place:
(The above image is a screenshot of the disassembled output of page.exe from Ghidra.)
So, if the Image (PE file) is loaded at a different Base Address other than the preferred one, then the Loader calculates the difference between Preferred Base Address (given in ImageBase field of the PE file) and the actual Base Address where the Image got loaded. It then refers the Base Relocation Table to see where all the Relocation must be done. It then adds this difference value to each of the values at the locations mentioned in the Base Relocation Table!
Here is the official documentation for Base Relocation Table: https://docs.microsoft.com/en-us/windows/win32/debug/pe-format#the-reloc-section-image-only
Lastly, we'll have page.exe with Sections data, Section headers, File headers and Optional headers.
The Sections include:
dumpbin page.exe:
Microsoft (R) COFF/PE Dumper Version 14.31.31104.0
Copyright (C) Microsoft Corporation. All rights reserved.
Dump of file page.exe
File Type: EXECUTABLE IMAGE
Summary
1000 .data
1000 .rdata
1000 .reloc
1000 .text
The .text Section containing code, .reloc containing the Base Relocation Table and .rdata containing Data Directories (like Import Tables, Import Address Table, Debug info etc.), Strings (like "The page size for this system is %u bytes.\n" used in our page.c) and .data being the memory space for the code to store and data.
Linker has also included a lot of headers which can be viewed by the following command:
dumpbin /headers page.exe
That command gives us the File Headers, Optional Headers and Section Headers of page.exe. You can view the full output here!
That's it!
"An In-Depth Look into the Win32 Portable Executable File Format" blog written in 2002: