Elf32 relocation

[Caleb1994]

I have Elf32 loading working fine. It only loads statically addressed ET_EXEC executables. Loads, and executes fine. No dynamic linking, and no relocation. The problem is that I want to implement drivers, and I wanted to make them super simple with no actual "task." In my idea, the space for the drivers data,stack, and code would be allocated on the kernel heap, then the function pointers would be saved and the kernel could call any driver from any interrupt from any task. Granted, this would make it very simple for a driver to COMPLETELY crash the system, but isn't this always an issue?

To be able to load the executables to an arbitrarily allocated kernel heap address, I need relocation. I have been reading an Elf manual (not sure where I got it... it is a PDF and is simply entitled "Executable and Linkable Format (ELF)" I'm not sure if it's the official but it got me going with statically linked executables so it's pretty good ) and I have also been googling out of my mind. I've seen multiple questions on this forum but not one that outlines the relocation process.

I understand what the GOT and PLT do, but I don't understand when they are created. I've seen places in my Elf manual that says that a certain dynamic structure should signify the dynamic linker to CREATE a PLT, but I have also seen references to a section that is already in the file called ".plt" which should hold the PLT! To be honest, I'm just really confused at this point.

Should I be searching the section headers for REL and RELA entries or get them from the .dynamic section (e.g. from DT_REL and DT_RELA entries in the dynamic entries)? Also, there are three Elf32_Dyn entries in the dynamic section which pertain to relocation. One says the address of the Relocation entry array (could either be DT_REL or DT_RELA), and the other holds the array size, and the last holds the size of each entry. There can apperantly be more than one DT_REL and DT_RELA entries in the .dynamic section (and the section headers for the matter), and these dynamic entries are do not come in any specific order. How do you know which size/length entry goes with which relocation array?

I understand most of the relocation entry types, and should be able to handle that, but as far as finding the relocation entries, the PLT, and the GOT, that is my problem.

[Combuster]

Dynamic linking != relocation != PIC. Your mixup of PLT/GOT/REL/RELA/Dynamic shows that you have no idea what the linker is actually doing for you:

Dynamic linking is the process of completing resolution of undefined functions when the program is run (by filling in the gap with references to shared libraries)

Relocation is modifying the addresses embedded in the binary so that an executable can be run at a different address than previous linking assumed.

Position independent code is a method of generating code such that no modification ever needs to be performed whenever the code is loaded to a different address than linking assumed (which means that the addresses specified by linking can be ignored to some extent).


Now, did you figure out yet what you are actually trying to do?

[Owen]

Incidentally, the section header table is completely irrelevant for a program loader (In unlinked executables it contains information for the linker, and in linked executables it primarily contains information for debuggers)

[Jezze]

For me doing relocation of drivers was a pain. I used the same pdf as you and I found it was difficult to figure out exactly how to translate addresses and what the exact meaning of the letters ment in the calculations described in the pdf. Even if I would normally recommend you to figure this out for yourself I think in this case it is not worth it because it is a lot of work for little gain.

In my operating system I have a very simple elf relocator that you can take a look at. It probably doesn't handle every case but at least it will help you get over the initial threshold of figuring out how stuff is translated.

Look at the elf_relocate function in this file:

https://github.com/Jezze/fudge/blob/master/kernel/elf.c

Use it as a reference, don't copy it without knowing what it does.

[Caleb1994]

Dynamic linking != relocation != PIC. Your mixup of PLT/GOT/REL/RELA/Dynamic shows that you have no idea what the linker is actually doing for you:

Dynamic linking is the process of completing resolution of undefined functions when the program is run (by filling in the gap with references to shared libraries)

Relocation is modifying the addresses embedded in the binary so that an executable can be run at a different address than previous linking assumed.

Position independent code is a method of generating code such that no modification ever needs to be performed whenever the code is loaded to a different address than linking assumed (which means that the addresses specified by linking can be ignored to some extent).


Now, did you figure out yet what you are actually trying to do?

Yes, I was getting all of this mixed up. When reading through this manual, it gets blurred. I had multiple ideas in my head about what needed to be done to load drivers. E.g. either PIC or Relocation (should have been obvious but thanks for the clarification) and dynamic linking for runtime linking to the kernel functions like printk and register_irq, etc...

I've been playing with PIC. I see now I can load it anywhere, so I tried using that as a driver format, but how do you tell if an executable is compiled as PIC. I haven't seen anything, and without it, a driver can easily fail because someone compiles the driver wrong.

I can load a driver, and find the driver structure ( I just keep a structure in a section called "driver_ops" and then I load that in and fix the function addresses for the new base). This works, and I'm able to run the load,unload,start,stop, and get_name functions but I'm stuck on how exactly to link to the kernel. I've been going over possibilities in my head and I've thought of a few:

1. abandon dynamic linking for now, until I get a better grasp and just pass a function pointer structure to the drivers. Bad for the long run, but its the lazy mans way out I guess
2. I thought linking to the kernels symbol file (extracted from the kernel using objcopy). I thought this was the best. The function pointers would all be correct (since it was from an already linked executable) and these function pointers do not change in my kernel, but doesn't seem to work. It seems the linker is relinking the symbols in the symbol file to the new load address.
3. Don't link the drivers, and use object files with references to kernel functions, which I can resolve at runtime.

Which one sounds the best to you guys? Choice one provides a quick working driver interface, but not very flexible. Choice two sounds like the best. It lets me link my drivers like normal. Essentially a dynamic library for my kernel. Choice three doesn't sound right, but could work. From what I've read about the linux kernel, that is how they are compiled (the makefiles are cryptic and don't show any actual compilation commands to build them. It seems that part is built into make).

For me doing relocation of drivers was a pain. I used the same pdf as you and I found it was difficult to figure out exactly how to translate addresses and what the exact meaning of the letters ment in the calculations described in the pdf. Even if I would normally recommend you to figure this out for yourself I think in this case it is not worth it because it is a lot of work for little gain.

In my operating system I have a very simple elf relocator that you can take a look at. It probably doesn't handle every case but at least it will help you get over the initial threshold of figuring out how stuff is translated.

Look at the elf_relocate function in this file:

https://github.com/Jezze/fudge/blob/master/kernel/elf.c

Use it as a reference, don't copy it without knowing what it does.

I also have a very simple relocator, which seems to work for x86 relocations usually found in relocatable files.

Start here.

These were great references! It really did help me get my head around how it is done. I don't plan on copying any code. I honestly understand what this code is doing 10x better than what this dumb manual is saying but anyways. I'm reading over it, and not writing any code until I understand everything.

Do you think relocatable files or Position Independent Code is better for drivers? PIC seems like less work, but that usually means it will end up not working right. :/ lol

[Combuster]

I've been playing with PIC. I see now I can load it anywhere, so I tried using that as a driver format, but how do you tell if an executable is compiled as PIC. I haven't seen anything, and without it, a driver can easily fail because someone compiles the driver wrong.

You can guess, but you can't be sure. PIC does not contain absolute addresses. You can check for the obvious cases by disassembling the code section and check if there are any memory operands that lack a register. Still, such a register might contain an absolute address loaded elsewhere. You can test for relocatable binaries by looking for relocation entries, but if you have nicely designed code there might not even be any references that need relocation (caused by the fact that x86 jumps are position-independent).

1. abandon dynamic linking for now, until I get a better grasp and just pass a function pointer structure to the drivers.

Ever thought of passing GetFunctionByName(const char *) to a driver's entry point?

2. I thought linking to the kernels symbol file (extracted from the kernel using objcopy). I thought this was the best.

This breaks all existing drivers on a different kernel build, even minor updates.

3. Don't link the drivers, and use object files with references to kernel functions, which I can resolve at runtime.

In other words, another way of dynamic linking. Only now you don't know if you have undefined references until you actually try to execute it.

Which one sounds the best to you guys?

4: IPC

Actually, any form of dynamic linking can be sufficient. It's just that you need to know how it works and how your tools can help you and others with it. Client-initialised dynamic linking offers the most freedom as you can have optional kernel interfaces that way. It's also the most elaborate method to take from the driver developer's perspective.

What is bad is not taking one road because you can't figure out why it breaks for you.

[Caleb1994]

You can guess, but you can't be sure. PIC does not contain absolute addresses. You can check for the obvious cases by disassembling the code section and check if there are any memory operands that lack a register. Still, such a register might contain an absolute address loaded elsewhere. You can test for relocatable binaries by looking for relocation entries, but if you have nicely designed code there might not even be any references that need relocation (caused by the fact that x86 jumps are position-independent).

Alright, that is annoying. Haha

1. Ever thought of passing GetFunctionByName(const char *) to a driver's entry point?
2. This breaks all existing drivers on a different kernel build, even minor updates.
3. In other words, another way of dynamic linking. Only now you don't know if you have undefined references until you actually try to execute it.
4: IPC

1. No I did not. That is a better idea if I was going to do it that way.
2. Hadn't thought of that.
3. Ew. That is true.
4. Haha well my goal was to not have an individual tasks for each driver. That way I don't need IPC and task switches to call the driver. Well, it cuts down on task switches (I need at least one interrupt to get to ring 0, but still) Right now, I'm just allocating the driver sections on the kernel heap, so I can call them anywhere in the kernel (I think I said that... idk... haha).

What I need is a dynamic library which has the same set of functions as the kernel. Then, when the dynamic linker sees that library, it will link to the kernel itself instead. How would I build such a library? To avoid undefined references, the library would need definitions of each function (even if they were invalid definitions since the driver next actually links to that library). I guess I could do that, but it would be a pain... how would you guys suggest linking to the kernel (at runtime lol)?

[computafreak]

A few years ago, I hacked together a dynamic linker and recorded the steps it performs (link.) That should be enough for a simple base to work from, as long as you bear in mind that it was somewhat messy in 2009, so there are probably assumptions with regard to the symbol tables you need to scan and the relocation types which crop up.

[Caleb1994]

Okay, well after a lot of code fiddling and staring at code/manuals, I've got it! I uploaded a picture of my little kernel testing "shell" where I dynamically loaded a kernel module! It feels like this project is actually getting to the point where it can do something. It is very exciting. I honestly never thought I'd make it this far.

The "test-driver successfully loaded" and "test-driver successfully unloaded" messages are from the driver calling printk().

I was researching how linux has done kernel modules in the past and current, and I read somewhere that they just used relocatable object files generated from "gcc -c" (e.g. e_type == ET_REL). It seems to work well. I link at runtime with the kernel symbols, and have a nice setup for when I allow dynamic linking with other libraries (currently, an undefined symbol in both the kernel and the file throws an error, but there is an easy change to allow recursive searching of dependencies).

I was going with Position Independent Code, but it was giving me problems. Everything I read stated that with PIC you can just change the base address and no relocation has to be done, but when I did that, it was impossible to access global data. It seems that the global data was accessed via the GOT (expected) but the addresses in the GOT are absolute. These addresses were wrong since I had moved the code and data. I tried manually fixing the GOT entries like this: "got=got-base+load_address" (it didn't seem like a good idea, but it was a last resort), but that didn't work.

If anyone could give some insight into PIC and global data, that would be great. I researched on the internet, but everything just kept telling me that PIC accessed global data through the GOT, which holds absolute addresses. And everything about loading PIC said that there were no changes that needed to be done. These two statements seem to conflict. One says there are absolute addresses within the file (which would need fixing if you move the base address) and the other says we don't need to change anything to load at a new base address...

Anyways, all in all a great day. I'm very happy with being able to load drivers/modules.

[Jezze]

Congratulations! It sure is a nice feeling to have it working.

[kscguru]

Congrats!

I was researching how linux has done kernel modules in the past and current, and I read somewhere that they just used relocatable object files generated from "gcc -c" (e.g. e_type == ET_REL). It seems to work well. I link at runtime with the kernel symbols, and have a nice setup for when I allow dynamic linking with other libraries (currently, an undefined symbol in both the kernel and the file throws an error, but there is an easy change to allow recursive searching of dependencies).

Very close ... ld's "-r" option does the magic stuff. It can merge together a bunch of object files into what is technically a shared library but can act as a combined object file with relocation information intact. (I expect this will only matter to you once your kernel module grows beyond one file; when there is only one file, there is almost no difference.)

I was going with Position Independent Code, but it was giving me problems. Everything I read stated that with PIC you can just change the base address and no relocation has to be done, but when I did that, it was impossible to access global data. It seems that the global data was accessed via the GOT (expected) but the addresses in the GOT are absolute. These addresses were wrong since I had moved the code and data. I tried manually fixing the GOT entries like this: "got=got-base+load_address" (it didn't seem like a good idea, but it was a last resort), but that didn't work.

If anyone could give some insight into PIC and global data, that would be great. I researched on the internet, but everything just kept telling me that PIC accessed global data through the GOT, which holds absolute addresses. And everything about loading PIC said that there were no changes that needed to be done. These two statements seem to conflict. One says there are absolute addresses within the file (which would need fixing if you move the base address) and the other says we don't need to change anything to load at a new base address...

Position Independent Code does have relocations. The difference is that PIC points the relocations to the .data section (specifically, the GOT, which is in the .got section that tends to be part of .data) instead of in the .text section. This tends to consolidate relocations so there are fewer of them to apply. The cost is that actual CPU instructions tend to use indirect addressing for data / small trampolines for function calls (the PLT) so the code runs slightly slower, and that PIC has several additional and more complex relocation types.

PIC matters a lot for userlevel code because .text tends to be copy-on-write memory and thus applying relocations costs significant amounts of duplicated memory, plus the writing to .text means you cannot mark .text read-only which weakens security. For kernel code where there is only one copy and memory protection doesn't matter but speed matters more, PIC is less of an advantage.

[Caleb1994]

Thanks guys! Now I'm realizing some of my interfaces needed some work, before being able to write suitable drivers, so I'm working on that.

Very close ... ld's "-r" option does the magic stuff.

Awesome, I was wondering how I was going to do that, but hadn't gotten past one file per module, so I hadn't researched it yet. Thanks a lot!

Position Independent Code does have relocations. The difference is that PIC points the relocations to the .data section (specifically, the GOT, which is in the .got section that tends to be part of .data) instead of in the .text section.

That makes sense, but my problem was that I wasn't getting any relocation entries at all. It was weird. I specified -fPIC and referenced global data, which ld linked to an absolute address. I guess that ld didn't know it was PIC, therefore it didn't know to generate relocation entries. I just thought if I specified -fPIC to gcc, then I would be able to load the code independent of the position haha

Congratulations! It sure is a nice feeling to have it working.

Congrats!

It definitely is! I'm really excited to fix up my interface and start writing drivers!