OSDev.org

Once again i feel this is wrongly placed and deserves a General Software or General (File) Format entry... but that is by the by

I have been reading the ELF specification trying to figure out how Linkers can place objects anywhere in memory/executable. The only references i can find in the document about relocation refer to connecting symbolic references. It does not however mention how code that says "JMP 0x03" is changed to "JMP 0x0743" How do Objects show all locations where specific memory locations are references... and if they do not.. is it upto the linker to understand the entire instruction set and parse the file looking for memory references and change specific Opcodes?

Neither. It is up to the compiler to generate position-independent code (PIC) when it is necessary / requested (GCC: -pic). This means using only relative addressing throughout the code, something which the IA32 architecture is very bad at BTW.

If the compiler didn't do PIC, the code in question cannot be "patched" into a PIE (position-independent executable) by the linker, since the linker doesn't know anything about opcodes.

Is it even possible to make 32-bit relative addresses on x86?

Also... if there is no patching done by the dynamic linker, how is it that pre-imported symbols can be used in executables when there final location (relative or definite) is unknown?

Ok not that i doubt Solar in anyway.. infact i normally take his word like i do that of some sort of... truthful bible of some sort.... but anyway

I was reading about the linking process and object fiels have to create an executable by having all addresses set to 0 and then it moves them based upon location in the final image. Does this not require knowledge of Opcodes?

No, the x86 cannot do IP-relative addressing. That is why you have to use register-relative addressing instead, i.e. using one of the scarce x86 registers to store the "base" address on which your offsets can operate... this doesn't benefit performance, obviously. (Although this factor has been much more severe in the olden times, when the CPU really had only those few registers the IA32 architecture advertises. Today's x86 CPUs are effectively IA32 emulators, with IA32 opcodes getting translated into microops and executed on a different architecture.)

The linker doesn't know about opcodes. It does very well know about relocation tables, where the location of any address fields are stored...

PS: Thanks for the compliments, but please take my words with a grain of salt. I haven't done any loader / linker stuff myself, just read about it, so people with more experience might tell you otherwise.

Tyler wrote:Ok not that i doubt Solar in anyway.. infact i normally take his word like i do that of some sort of... truthful bible of some sort.... but anyway

I was reading about the linking process and object fiels have to create an executable by having all addresses set to 0 and then it moves them based upon location in the final image. Does this not require knowledge of Opcodes?

It doesn't know the opcodes, all the opcodes it uses that can be / need to be relocated are N bits in offset and are preloaded with an offset that makes the location to be added the location of the variable minus the location of the offset or such.

Most offsets are then not 0 but -4, since ia32 addresses from the END of the instruction, not the start of the offset. You'll see a lot of FFFFFFFC addresses if you disassemble a not-linked object. It has a few relocation entry types that tell it what to add - the location of the data, the location of the code, the location of the data minus the location of the code, stuff like that.

IA32 PIC is generated by abusing EBX as base, loading it using a trick at startup and furthermore referencing it as such. It's screwed up still, since you need to reload EBX in every externally referenced function (and you can't use a local cache - catch 22) and you waste a register on a machine that's already really cramped for registers.

AMD64/EM64T/whatever you wanna call it does have an RIP relative addressing mode that should work in pretty new compilers, but I didn't check that yet. They didn't add it retroactively to the 32-bit code engine, so it's just in 64-bit mode.

Tyler wrote:Is it even possible to make 32-bit relative addresses on x86?

Solar wrote:No, the x86 cannot do IP-relative addressing.

Umm... last time I checked... all short jumps are relative displacements (-128/+127)... along with some near jump opcodes.

As per the i386 Programmer's Reference Manual...

JMP ── Jump
(Opcode) (Instruction) (Clocks) (Description)
EB cb JMP rel8 7+m Jump short
E9 cw JMP rel16 7+m Jump near, displacement relative to next instruction
E9 cd JMP rel32 7+m Jump near, displacement relative to next instruction

As Solar said, though, relative displacement can also be achieved using registers to store the corresponding base addresses.

Also, relative displacement instructions are pipe-lined fairly well, along with any other code that hasn't been modified... so the "inefficiency" isn't as drastic as stated.

Ideally, you could use only the short/near relative displacement jumps (and calls) in your code to achieve Position Independent Code.

*PLEASE NOTE*, however, that there is a huge difference in generating Position Independent Code (relative jump/call displacement instructions), and creating a Position Independent Executable (not only relative instructions, but also addressing relative data-space variables and the like).

In summary, Position Independent Code doesn't require anything fancy, just the correct use of such instructions... assemble/compile/link and go.

As for Position Independent Executables, the assemblers/compilers/linkers put all label/variable/etc... addressing into the relocation fix-up table (call it what you like) of the target file format. The Kernel/OS/loader parses the file format and uses the relocation fix-up table to map all the code/data addressing to their relative virtual address. Formats like the PE have a "preferred load address" and relocation is generally not required in such instances.

HtH

SpooK wrote:Ideally, you could use only the short/near relative displacement jumps (and calls) in your code to achieve Position Independent Code.

*PLEASE NOTE*, however, that there is a huge difference in generating Position Independent Code (relative jump/call displacement instructions), and creating a Position Independent Executable (not only relative instructions, but also addressing relative data-space variables and the like).

In summary, Position Independent Code doesn't require anything fancy, just the correct use of such instructions... assemble/compile/link and go.

So you claim that a piece of code that can't print a proper string that's supposed to be part of it because it can't address it is still the same valid program?

I claim that for position-independant code it needs to be able to either relocate the data segment (compared to itself) or have a base register for it.

SpooK wrote:Umm... last time I checked... all short jumps are relative displacements (-128/+127)... along with some near jump opcodes.

This may be true, hence my use of the term 32-bit relative. Jumps of 128 each way are not incredibly useful when wants to jump around an executable of more that 128 bytes. It all makes me wonder why we are continuing the x86 platform.

Umm... last time I checked... all short jumps are relative displacements (-128/+127)... along with some near jump opcodes.

This may be true, hence my use of the term 32-bit relative. Jumps of 128 each way are not incredibly useful when wants to jump around an executable of more that 128 bytes. It all makes me wonder why we are continuing the x86 platform.

it is not true:

the x86 supports reletive jumps (both conditional and absolute) with 8, 16, or 32bit offsets allowing reletive JMP and Jcc with +/-2GB (enough to cover the entire address range)

however, this still isnt useful for data addressing

the problem with IP-reletive addressing on x86, is there is a system in place for Position independant data -- that was the purpose for segmentation, and now that segmentation is not used, there is IP-reletive data references (in LMode)

Both Tyler and JAAman touched upon what seems to be a failure in communication on my behalf.

Perhaps it should have been stated as such...

Umm... last time I checked... all short jumps are relative displacements (-128/+127)... along with the existence of some near jump opcodes.

Short is 8-bit (-128/+127), near can be 16-bit (-32768/+32767) or 32-bit (-2147483648/+2147483647). All of them are "signed" values, though (which I hope is obvious by now).

Thanks for the corrections, though

Tyler wrote:Once again i feel this is wrongly placed and deserves a General Software or General (File) Format entry... but that is by the by

I have been reading the ELF specification trying to figure out how Linkers can place objects anywhere in memory/executable. The only references i can find in the document about relocation refer to connecting symbolic references. It does not however mention how code that says "JMP 0x03" is changed to "JMP 0x0743" How do Objects show all locations where specific memory locations are references... and if they do not.. is it upto the linker to understand the entire instruction set and parse the file looking for memory references and change specific Opcodes?

Ok, well, since everyone started drifting off topic i will attempt to bring it back. linkers placing these into memory has nothing to do with position independent code. it has a symbol table and/or relocation table. The relocation table basically consists of an offset and sometimes a size). So, when you are linking, you read the relocation table, and it tells you each offset that is dependant on the position it is loaded to... so, this is your code for example:

[bits 32]
jmp Start
SomeData dd [Start]
Start:
mov eax, [SomeData]

Your relocation table would be (unsure of the operand size of jmp, but assuming 1 for the jmp and mov)

offset = 1, offset = 5, offset = 7

So, when you parse this 'table', you would add the base address of the location you are loading it to... so you would do this:

char *Data; //This would point to the loaded program!

for (ctr = 0; ctr != RelocCount; ++ctr)
{
*((unsigned long*)(&Data[Reloc[ctr].Offset])) += BaseAddress;
}

So, after this runs, it would patch the base memory address into the jmp opcode, the location stored in SomeData, and the mov opcode. Pretty simple once you think about it some. So, to begin: it would store the value 6 into the offset 1 (for the jmp opcode). We load this to 0x1000 memory address...if you don't patch the relocation table, you will jump to memory address 0x0006, but once you parse the relocation table, it would add base address 0x1000 to offset 1, which would be 0x1006, which is the correct location to jump to! The symbol table is irrelevant to executeables, they are more used for dynamic libraries (it basically stores a list of variables and their offset, so if one file references an external symbol, it knows the location!)

Well i get how to change pointers based upon a relocation table now... though i haven't even begun to think how to implememnt this into a bootloader. Does GCC/LD create code that is automatically code location independent or do i have to tell it todo this? (and how do i?)

Tyler wrote:Well i get how to change pointers based upon a relocation table now... though i haven't even begun to think how to implememnt this into a bootloader. Does GCC/LD create code that is automatically code location independent or do i have to tell it todo this? (and how do i?)

As far as I have ever observed, jumps and calls are normally relative short/near types. Far jumps/calls are the exception, especially in 32-bit PM.

Relocation tables are generally a load-time data structure, not run-time. If the file format has a relocation table, and the loader recognizes this, the loader does all the relocation fix-ups to the "code" section by parsing the relocation table.

If you are using a privately made loader, it is only a matter of adding the generic relocation fix-up code. If properly coded, this function will do what it needs to do and your code will continue executing as if all the addresses were "correct" from the get-go.

I know this is a crude explanation, but I hope it helps

Hey... i have nearly completely implemented support for the ELF file format. But i do have a related query so i thought best to ask here and not waste more space. I am hoping at least one of you has had experience working on a linker.

If i was to compile code that was not "Position Independent" in a format that LD could take in and told it to create an Dynamic ELF File... would it simply resolve all symbols related to data or would it change code to make it Position Independent Code?