Contest: make 32-bit PEs & ELFs easy bootable & relocateable

[technik3k]

GOAL
The goal of this contest is to be able to compile boot executable and modules in a "standard" manner and then load and relocate them at boot time with minimum effort and maximum ease.

Essentially, I am looking for a utility that reads PEs and ELFs executables and replaces headers with an init code that will do base relocations to a reasonable target address specified at runtime. Initially you can pick as input either 32-bit PE or ELF executable and make resulting boot binary either multiboot compliant or be loadable directly from a boot sector (if you want to switch to 32-bit protected mode yourself).

TEST PLAN

One of the test cases will be a little C program that writes something directly to the video memory at address 0xB8000 and then halts itself with while(1). It will be compiled using a "standard" compiler with options to generate either PE or ELF 32-bit executable with base relocations information and do not include any c0sx init code. Test programs will use at least one of each: global string constant, global variable, and a function address.

• 1. Compile test.c into test.exe:
  • let say, it will have default base (4Mb),
  • code section and entry point at (4Mb+4k),
  • data section at (4Mb+8k), and bss section (4Mb+12k)
• 2. Your utility should take text.exe as input and produce test.bin
• 3. Somehow set new target address by changing 4 bytes inside test.bin (specific offset?) to (2Mb)
• 4. Use modified test.bin to create floppy image with GRUB that will load test.bin to some address (64k)
• 5. Test it under QEMU or VMware:
  • your init code should copy and rebase
  • original code section to (2Mb+4k),
  • data section to (2Mb+8k), clear bss, and
  • jump to the proper entry point at (2Mb+4k).

Obviously, it needs to work with any reasonable values. I will test with different executables and various grub load and target load addresses. You can assume that everything will properly fit in memory and not overlap itself or the initial stack but your shouldn't assume any of those values to stay 64k, 2Mb, 4Mb, +4k, +8k, etc...

Test cases will include C/C++ command line executables generated by the following compilers: gcc, tcc, msvs/cl. I intend to use default compile and link options, but if anyone runs into any issues speak up and we could tweak them. Sample test code and compile instructions will be posted in this thread later.

RULES

• Your source code must be ISC licensed similarly to other contests on this forum
• All entries must be posted to this thread with source code and compile instructions attached (no links)
• You can use GRUB only to load boot binary, set up initial stack, and get control in 32-bit protected mode
• You cannot utilize any advanced GRUB functionality or additional modules (compression, ELF handling, etc...)
• Accepted are C, C++, and x86 assembler sources compilable with tcc, gcc, gasm, fasm, nasm, or msvs/cl/masm
• Prizes will be awarded via PayPal in USD within two weeks of contest closing date (i.e. entry submission deadline)

Part I of the contest

• Entries are accepted starting May 1, 2010 00:00:01 UTC
• For entry to qualify resulting boot binaries must be less or equal to the original executable size.
• There are three separate $25 prizes:
• First entry that successfully boots PE executable (generated by one of compilers) gets $25
• First entry that successfully boots ELF executable (generated by one of compilers) gets $25
• First entry that successfully handles both PE and ELF executables and all compilers (tcc,gcc,msvc) gets remaining $25
• Deadline for the first part of the contest is May 31, 2010 23:59:59 UTC

Part II of the contest

This is preliminary rules for the Part II: dates are TBD

• Your utility needs to build upon the best solution from the Part I and create a compressed boot binaries for each test case
• There will be three test executables: ~12k (public), ~64k (hidden), ~256k (public) ;; (size, gzipped size, and md5s will be public)
• Each executable will be compressible by ~2 times using gzip and will contain similar proportion of code, globals, and text messages.
• Init code should decompress original code, perform base relocations and jump to the executable entry address
• In order to qualify first entry must produce binaries at least 1024 bytes less than ones produced by the uncompressed winning entry from the Part I
• Each subsequent entry must improve total compressed size by at least 1024 bytes and no binary should be larger than best result of the previously qualified entry
• Example:
  • First entry: 9k, 51k, 180k (total=240k) -> quilifies.
  • Second entry: 11k, 49k, 160k (total=220k) -> nop
  • Third entry: 9k, 49k, 142k (total=200k) -> quilifies.
  • Fourth entry: 8k, 42k, 140k (total=190k) -> quilifies.
• Last Qualified entry on the contest closing date wins $60 prize!
• There will be a extra $40 prize if winning entry uses decompressor code attached below.

Note: If you intend to use any existing compression / decompression algorithm it must be compatible with ISC licensing.

Questions and suggestions are welcome. If anyone wants to co-sponsor this contest and bump-up prizes it will be greatly appreciated!!!

[technik3k]

This post holds helpful info and file attachments...

PE header format:
OS Dev Wiki: PE
http://msdn.microsoft.com/en-us/library/ms809762.aspx
http://msdn.microsoft.com/en-us/magazine/bb985992.aspx
http://www.codeproject.com/kb/system/in ... nloadLink4

[Combuster]

I'm going to cast magic missile at your attempt.

Stock PE/ELF files do not come with relocation information. It is thus impossible to relocate such binaries.

[Gigasoft]

As I understand it, this is obviously not meant for random PE or ELF files taken out of the blue (which it would be useless to convert). The PE or ELF files will be linked with /FIXED:NO or /DLL (for PE using the Microsoft Linker) or whatever options ELF linkers use to specify that they should output a relocatable executable. In PE files, this is accomplished by inlucding a base relocation data directory. In ELF files, a standard relocation table is used with all entries having a symbol index of 0.

[technik3k]

As I understand it, this is obviously not meant for random PE or ELF files taken out of the blue (which it would be useless to convert). The PE or ELF files will be linked with /FIXED:NO or /DLL (for PE using the Microsoft Linker) or whatever options ELF linkers use to specify that they should output a relocatable executable. In PE files, this is accomplished by inlucding a base relocation data directory. In ELF files, a standard relocation table is used with all entries having a symbol index of 0.

Yes, this is correct. ELF files will need to be generated with "-shared" option and the simplest way to generate relocatable PE is to build a *.dll.

If you want your OS project to load arbitrary modules you will need either have a very customized compile/link process and/or elaborate runtime loader which understands executable format. In addition you may have to implement virtual memory with paging if each module is linked at the same address (i.e. doesn't have base relocation information). As you can see this gets complicated fast.

The idea here is to push all complexity, uncertainty, and error checking into external utility that is run once. Then have very simple runtime that could load and relocate modules to any address in the memory. According to my calculations you can implement that with overhead (over statically linked executables) as little as 100 bytes.

I know gcc has pie and pic options, but it advertised only for ELFs and needs global offset table which requires too much runtime overhead. However, with external utility approach this will work with both ELF and PE generated by pretty much any compiler.

Consider the following test.c and compiler options:

Code: Select all

int x=42;
int _start(void)
{
 return x;
}

Code: Select all

gcc -nostdlib -shared test.c -o test.elf

Code: Select all

cl /nologo /c test.c
link /nologo /NODEFAULTLIB /SUBSYSTEM:CONSOLE  /FIXED:NO /ENTRY:_start test.obj

[Owen]

Code: Select all

owenshep@Asuka:~$ gcc -nostdlib -shared test.c -o test.elf
Text relocation remains                 	referenced
    against symbol		    offset	in file
x                                   0x4       	/var/tmp//cc1wa4Nz.o
ld: fatal: relocations remain against allocatable but non-writable sections
collect2: ld returned 1 exit status

Hmm? It looks like my linker dislikes your proposal - namely, it enforces strict W^X.

Really, I don't see the point. Linker scripts aren't hard, and kernels generally make some assumptions about the region they are loaded into anyway.

[technik3k]

Really, I don't see the point. Linker scripts aren't hard, and kernels generally make some assumptions about the region they are loaded into anyway.

That's true for the kernel, but what about loading additional modules at different addresses? If you trust the module, the simplest way to do it would be to read module from disk, pass target address as an argument and let a small stub at the beginning of the module decompress / relocate itself to proper location and do necessary rebasing.

Hmm? It looks like my linker dislikes your proposal - namely, it enforces strict W^X.

Which version of binutils do you have? I have gcc 4.3.3 and ld 2.19.1 running on Xubuntu - they work fine for me. However, I don't claim it is the best way to compile ELFs. If you know simpler/better way, please, post.

[Owen]

Thats actually the Solaris linker. GCC uses the native linker on most systems. (The GCC is 4.3.3)

As for loadable modules, that probably indicates a monolithic system, in which case the kernel probably has a linker anyway and adapting it to load modules should not be overly difficult.

[tharkun]

Shouldn't you be using -fPIC?

[technik3k]

Shouldn't you be using -fPIC?

Compile the following code:

Code: Select all

int foo(char*p) { return 42; }
char *p="Hello World";
int (*fooPtr)(char*)=&foo;

int _start(void)
{
  return (*fooPtr)(p);
}

Code: Select all

gcc -nostdlib -fPIC test1.c -o test1.elf
objdump -rxds test1.elf

From the disassembly you will see that generated code has some overhead and relies on GOT (Global Offset Table) to lookup effective addresses. This might have benefits on Linux where same binary could exist at different virtual addresses in different processes.

For the simplified system that I have in mind It doesn't really help that much because code is longer and you still have to properly load sections and fix up GOT entries.

Using "-fPIE" option instead of "-fPIC" produces slightly cleaner code, but I am not sure if it will help either.

[Gigasoft]

Isn't there any way to specify that a section should be writeable when using ld? I'd be surprised if there wasn't.

[Combuster]

Contest: make 32-bit PEs & ELFs easy bootable & relocateable

Emphasis mine. I think this experiment has failed. It is just as easy to add -T link.ld to all the mess you already have to supply to gcc/ld instead of adding yet another step in the process - especially when the former has been tried and supported for like the past decade.

[technik3k]

Contest: make 32-bit PEs & ELFs easy bootable & relocateable

Emphasis mine. I think this experiment has failed. It is just as easy to add -T link.ld to all the mess you already have to supply to gcc/ld instead of adding yet another step in the process - especially when the former has been tried and supported for like the past decade.

I am not sure if I am missing something or you do, but how do you compile any module except kernel that might need to be loaded at arbitrary address on a system with single address space and no paging?

Yes, you can link kernel at predefined address, but all other modules that share same address space have to be relocatable. You have to have dynamic relocation code somewhere (either inside kernel or attached to each executable). I say that it is possible to save space by adding less than 100 bytes of code to each module and removing most of relocation information that is not efficiently stored in both PE and ELF formats. As a bonus if you want to run something on my system you can compile it with either gcc->ELF, gcc->PE, or msvc->PE - whichever you feel more comfortable with.

[Combuster]

So, you're writing out a contest in order to get a desgin specifically for you?

But seriously, look at the introduction of GCC Cross-Compiler to know why it is generally a bad idea to use a random compiler for OS development - they are not designed to make code for *your* OS, but for linux, windows, ... and the effort you ask to be spent on a tool that can not possibly undo all those Bad Things can be used better to just create a proper cross-compiling toolchain.

[technik3k]

So, you're writing out a contest in order to get a desgin specifically for you?

What's wrong with making contest? Nobody forces you to participate. But if solution is posted anybody could use it since it will be ISC Licensed.

Anyone who wants to load PEs or ELFs from their kernel needs to have some loader. It could reside inside the OS or be an external utility.

I think utility is better, because it will report any errors/issues right at the compile stage and OS will need to handle smaller set of potential problem (like not enough memory, etc...). I am working on PE implementation myself, and hope somebody else could come up with ELF and even beat me with PE submission.

... it is generally a bad idea to use a random compiler for OS development ...

Well, somebody could say to you: "... it is generally bad idea to use random OS ... stick with Windows ..." I suspect you wouldn't like that. You want to try something else, like build your own OS.

I want to experiment with very compact OS which could run modules compiled by a number of established compilers and not limit the choice to gcc or msvc or whatever.

Do you really think I shouldn't experiment with new ideas?