MIPS Multi GOT
Document version: 1.2
Author: Sasa Stankovic
This document summarizes how multi-got is implemented in GNU ld. It first gives general overview of how got table is organized for Mips. It then describes the implementation of multi-got in GNU ld.
Got table consists of three parts - local, global and tls. How the got is laid out is specified by the values of dynamic tags DT_MIPS_LOCAL_GOTNO and DT_MIPS_GOTSYM (which linker emits to the .dynamic section), and by the order of symbols in dynamic symbol table.
Local got entries are at the beginning of got. Their number is given by the dynamic tag DT_MIPS_LOCAL_GOTNO.
Global got entries come after the local ones. There are two kinds of global got entries - normal and reloc-only. Normal global got entries are created for got relocations (like R_MIPS_GOT16 or R_MIPS_CALL16), and they are accessed in code with gp-relative addressing. Reloc-only global got entries (that's how GNU ld calls them) are created for symbols that are referenced by dynamic relocations R_MIPS_REL32. These entries are not accessed with gp-relative addressing, but MIPS ABI requires that these entries be present in global got. The reloc-only part of the got is actually not accessed at run-time at all, only at dynamic-link time.
MIPS ABI also specifies that the order of the symbols in global part of the got (normal and reloc-only) should match the order of the symbols in dynamic symbol table. The dynamic symbol table is therefore sorted so that symbols that have global got entries are placed at the end. The dynamic tag DT_MIPS_GOTSYM gives the index of the first entry in dynamic symbol table that has the entry in the global part of the got.
So got is laid out as follows: There are DT_MIPS_LOCAL_GOTNO local entries in the got. The first global got entry has index DT_MIPS_LOCAL_GOTNO in the got, and this entry is for the symbol that has index DT_MIPS_GOTSYM in dynamic symbol table. The second global got entry has index DT_MIPS_LOCAL_GOTNO + 1 in the got, and it is for the symbol that has index DT_MIPS_GOTSYM + 1 in the dynamic symbol table, etc. Normal global got entries are always placed before reloc-only entries.
The final part of got (after local and global) is for symbols with tls relocations, both local and global. For the tls part of the got it doesn't apply that the order of the got entries should match the order of symbols in the dynamic symbol table. Therefore tls symbols are always placed in the dynamic symbol table at indexes lower than DT_MIPS_GOTSYM.
In the pass that scans the relocations, the linker records every local, global and tls got reference in the link. If the sum of local, global and tls entries is less than 64K (meaning that all entries can be accessed with 16-bit offsets), only single got is enough. Otherwise, multi-got is created.
In the multi-got link, we have the primary got which is at the beginning of the .got section, and one or more secondary gots which come after the primary got.
When ld detects that multi-got link is needed, it starts by creating a got for every input object file that participates in the link, and allocates in that got all local, global and tls got entries for that object file.
ld then tries to merge the GOTs of input objects together, as long as they don't exceed the maximum got size of 64K, choosing one of them to be the primary got.
ld first tries to create primary got, or if primary got already exists it tries to merge with the primary got. If this isn't possible, ld tries to merge with the last-created got (secondary got). If this merge also isn't possible, ld creates a new secondary got.
ld tries to use as much as possible of the primary got, since primary got doesn't require explicit dynamic relocations (below will be explained what that means).
When deciding whether GOTs for two objects can be merged, ld sums the local entries for both objects, but doesn't sum the global and tls entries. Every global and tls symbol should have only one entry in the got. So if there are, for example, two got relocations for printf in two objects, ld will count only one entry when deciding whether two gots can be merged.
If the final calculated size is less than 64K, ld merges two gots into one. This process is repeated for every object. The final result is that we will have one primary got (which will be at the beginning of the .got section), and one or more secondary gots which will come after the primary got.
One thing that is important to note is that the size of the global part of the primary got must always equal the number of dynamic symbols with indexes greater or equal to DT_MIPS_GOTSYM. This is MIPS ABI requirement and this must always hold for both single and multi-got. The global part of the primary got therefore consists of three parts:
- First part is for normal global got entries of the primary got.
- Second part is for global symbols of secondary gots. This part is unused at
runtime (meaning that it is not accessed with gp-relative addressing), but it is used at dynamic-link time as usual - dynamic linker fills this entries with addresses of the symbols just as it does with first or third part. For every entry in this part of the primary got there is corresponding entry (for the same symbol) in one of the secondary gots. When resolving R_MIPS_REL32 relocations for global entries of secondary gots, dynamic linker reads the symbol address from this part of the primary got.
- Third part consists of reloc-only entries.
So, although the sum of local and normal global entries of the primary got should be less than 64K, the size of the primary got can be greater than 64K, because parts of the primary got that overflow the 64K limit are used only by the dynamic linker at dynamic link-time and not by 16-bit gp-relative addressing at run-time.
If the size of the primary got is greater than 64K, ld doesn't merge primary got with gots that have tls relocations. Tls entries always come at the end of got (both primary and secondary), and if the got size is greater than 64K we will not be able to access them with gp-relative 16-bit offsets.
Since secondary gots only have local, normal global and tls entries, the size of the secondary got must be less than 64K.
Dynamic relocation of secondary gots
One additional thing that needs to be done for multi-got links is creating dynamic relocations for secondary gots. We need to create R_MIPS_REL32 relocations for all global entries of secondary gots, and if we are generating shared object we also need to do this for all local got entries of secondary gots.
The reason for this is that dynamic linker is not aware of the secondary gots. It fills all global entries in primary got with correct addresses, and if creating shared object it also adjusts local got entries in the primary got by adding the shared object's displacement, but it does nothing for secondary gots. This is why we have to explicitly create R_MIPS_REL32 relocations for the entries in secondary gots that need them, so that dynamic linker can fill the entries with the right value.
For example, suppose that we have multi-got with one primary and one secondary got, and suppose that entry for printf symbol is in the secondary got. There is still a got entry for printf in the primary got since printf is a global symbol whose dynamic symbol index is greater than DT_MIPS_GOTSYM. The static linker will initialize secondary got entry for printf to 0, and it will also create R_MIPS_REL32 relocation for this printf secondary got entry. Dynamic linker ld.so will first resolve the entries in primary got. Note that there is no need for R_MIPS_REL32 relocations for the primary got because ld.so knows which entry corresponds to which symbol based on the entry index and the dynamic symbol table. After that ld.so will resolve the secondary got R_MISP_REL32 relocation for printf. When resolving this relocation, ld.so will use the resolved printf address from the primary got. At the end we will have two entries which contain the address of printf - one in primary and one in secondary got. At run-time, when calling printf only secondary got entry will be accessed.
Another thing that needs to be done for secondary gots is to forbid global symbols in secondary gots to have lazy-binding stubs.
When GNU ld cannot handle multi-got
The only case when GNU ld cannot handle multi-got is when there is a single input object file where the sum of local and normal global got entries is greater than 64K - more than 16378 (8188 in the n64 case) different got references (for different symbols) in single input object file. This situation should practically never happen.