On the finer points of Dynamic Linking (32-bit x86 ELF)

[mallard]

I've been working on adding a dynamic linker to my OS and have something that's basically functional; I can load and link an executable linked with a test library. I do however have a few questions that I can't seem to find obvious answers to (either in the SysV ABI docs or other sources).

1. What is the correct order in which to process relocations? I've found in my tests that if a library exports a string (char* symbol) then this is the target of an R_386_RELATIVE relocation (i.e. it needs to have the library's base address added to it; makes sense) and another module that uses said string will have an R_386_COPY relocation to copy the address of the string into its own data segment. However, this causes a problem; if the R_386_COPY relocation in the "user" module is processed before the R_386_RELATIVE relocation in the "owner" module, then the user will end up with an incorrect address.

Currently, I process relocations for modules in reverse order (i.e. the last loaded module gets processed first), but this is probably not the best solution since the order modules are loaded is not necessarily their "dependency order" since, for instance if both the executable and a library depend on the C runtime library, it's highly likely that the CRT will have been loaded before (and therefore will have its relocations processed after) the library that depends on it.

I've thought that I could split the relocation processing in two; do the non-symbol-dependent relocations (basically just R_386_RELATIVE) for all modules before the symbol-dependent relocations. Is this the right approach?

2. How do I tell which module holds the "real" version of a particular symbol? In the above example, the string will appear in both the executable and the library's symbol tables. They both have an address, section, size, type, etc. but the executable doesn't actually have the value (the memory is zero'd) until the R_386_COPY relocation has been processed.

At the moment I have a check to prevent a symbol lookup from finding the symbols in the module itself (which is probably incorrect), but this won't work if there were a third module that referenced the same symbol (and also wouldn't actually have the value until after an R_386_COPY had been processed). There doesn't seem to be any way to tell from looking at the symbol/hash tables of a module whether it really has that symbol at load or whether it will only have it once a relocation has taken place. Short of scanning the relocation tables of the module during symbol lookup, is there a way to actually ensure that a symbol lookup returns the "real" symbol and not one of these "placeholder" symbols?

3. How do I convince GNU automake-based packages that, yes, my OS does support shared libraries and it should build them? I've had some success with adding "CFLAGS=-fPIC" to the "./configure" line and then un-ar-ing the .a files and relinking them into a dynamic library, but this feels like a massive hack. Surely there's a better way...

[simeonz]

I'm not expert on the subject, but while someone more knowledgeable comes around to answer this, I can give my view.

R_386_COPY overrides a symbol, in practice is used in executables only (ET_EXEC), and allows them to work around their non-PIC nature.

A symbol value is provided by the original exporting module. There is at most one copy relocation for it (practically coming from ET_EXEC modules only), which overrides the default symbol value and points into a .bss section. There is at most one relocation affecting the memory location pointed by the default address/value of the symbol in the original exporting module.

You can use two passes and I don't see a problem, assuming you cache some information from the first pass. Alternatively, you can have two patch structures of sorts. A map between symbols and affected locations from the ordinary relocations. This must be a bidirectional map, but the second index can be built at the end. Second, a remap coming from the copy relocation records, mapping symbols to their overrides. Once you read all relocations, you can merge those two structures and apply the remapping to both the symbol values (overriding them) and the patched address locations that match those overriden symbols (redirecting them), where necessary. But the performance may turn out slower, because you are essentially creating memory overlay that you pre-patch this way, instead of addressing and patching the relevant memory directly.

Again, not an expert, so take my opinion with a grain of salt.

[mallard]

So if R_386_COPY only occurs in non-relocatable executables and never in libraries then the approach of processing modules in reverse-loading order (i.e. so the executable is always processed last) should be fine?

As for "A symbol value is provided by the original exporting module." this doesn't seem to be the case. Here is the relocation table and dynamic symbol table for my test library:

Code: Select all

Relocation section '.rel.dyn' at offset 0x184 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
00001264  00000008 R_386_RELATIVE   

Symbol table '.dynsym' contains 8 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 0000018c     0 NOTYPE  GLOBAL DEFAULT    5 _init
     2: 00001268     0 NOTYPE  GLOBAL DEFAULT   11 __bss_start
     3: 00000190    10 FUNC    GLOBAL DEFAULT    6 ell_func
     4: 0000019c     0 NOTYPE  GLOBAL DEFAULT    7 _fini
     5: 00001268     0 NOTYPE  GLOBAL DEFAULT   11 _edata
     6: 00001268     0 NOTYPE  GLOBAL DEFAULT   11 _end
     7: 00001264     4 OBJECT  GLOBAL DEFAULT   11 teststring

And here is the same for the the executable that links to it:

Code: Select all

Relocation section '.rel.dyn' at offset 0x1dc contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
4000df20  00000705 R_386_COPY        4000df20   teststring

Relocation section '.rel.plt' at offset 0x1e4 contains 1 entries:
 Offset     Info    Type            Sym.Value  Sym. Name
4000d5cc  00000307 R_386_JUMP_SLOT   00000000   ell_func

Symbol table '.dynsym' contains 8 entries:
   Num:    Value  Size Type    Bind   Vis      Ndx Name
     0: 00000000     0 NOTYPE  LOCAL  DEFAULT  UND 
     1: 400001ec     0 NOTYPE  GLOBAL DEFAULT    7 _init
     2: 4000df10     0 NOTYPE  GLOBAL DEFAULT   19 __bss_start
     3: 00000000     0 FUNC    GLOBAL DEFAULT  UND ell_func
     4: 4000a484     0 NOTYPE  GLOBAL DEFAULT   10 _fini
     5: 4000df10     0 NOTYPE  GLOBAL DEFAULT   18 _edata
     6: 4000f7f0     0 NOTYPE  GLOBAL DEFAULT   19 _end
     7: 4000df20     4 OBJECT  GLOBAL DEFAULT   19 teststring

Note that "teststring" appears in both symbol tables and there doesn't seem to be any way to tell which is the "real" object. Looking at the relocations, both are "targets", but only one is symbol-dependent, so is the only way to work it out by scanning the relocation tables for the module? That seems hacky and unreliable...

[simeonz]

So if R_386_COPY only occurs in non-relocatable executables and never in libraries then the approach of processing modules in reverse-loading order (i.e. so the executable is always processed last) should be fine?

Copy relocations are designed to appear only in ET_EXEC in practice. I haven't seen this plainly stated in the specification though. If you are going to apply the copy relocations at the end, what will happen to already relocated references from the previous modules - won't they already be assigned the value of the original symbol from the shared library?

Note that "teststring" appears in both symbol tables and there doesn't seem to be any way to tell which is the "real" object. Looking at the relocations, both are "targets", but only one is symbol-dependent, so is the only way to work it out by scanning the relocation tables for the module? That seems hacky and unreliable...

I don't think you need this correspondence. I think, all you need to do when you discover copy relocation is to copy the initial value for the new storage location from memory address pointed by symbol defined in another module. But this is all you need to observe. Then all references have to be redirected to that new location - the target address of the copy relocation, not of any whichever symbol. If you never encounter copy relocation for a symbol, then you have only one definition (unless we are talking weak symbols.) Knowing directly which symbol is genuine in one sense or another, seems to me more of a compiler's job in this context.

[mallard]

Ok, so I've updated my loader/linker to resolve R_386_RELATIVE relocations at load time, rather than at link time and made the symbol lookup code also search in reverse-load order. I've also removed the "don't return symbols in the module itself" check for all lookups except R_386_COPY (because after checking the relocation tables of "real" libraries, it's obvious that it's very common for libraries to have relocations that depend on their own symbols).

Therefore as long as a symbol in a library is not itself the target of a symbol-dependent relocation (this seems to only happen with R_386_COPY relocations in the executable, which due to the reverse-load processing and symbol lookup order will always be processed last and will never be found by a lookup if a library has a symbol of the same name), everything should work correctly. I suppose a problem could occur if the executable exports a copy of a library symbol under a different name and another library uses said renamed symbol, but I think that's a fairly unlikely occurrence.

Also, now that I've updated my system call code's inline assembly to preserve the value of EBX (so system calls can be made from position-independent code) I've started to compile "real" shared libraries for my OS. I'm still doing the "CFLAGS=-fPIC ./configure" and "un-ar and relink into a shared library" hack for building 3rd-party libraries (e.g. Newlib), but at least this seems to work. Now all I need to do is modify GCC/LD's library search logic so it will recognize my naming convention...