Relocatable Code: How do you do it?

Aras Vaichas asks: "I am designing the kernel software for a radio modem. The processor is an AMD186ED - 1MB address space split evenly between DRAM and FLASH/SRAM. Initially I was going to port FreeBSD to it but after scouring the FreeBSD kernel code discovered that there was too much 80386 code there (memory manager, etc). This makes life a little more difficult so I am going with another commercially available realtime operating system. My problem is that I want to implement a Flash File System and be able to execute programs (EXE style) from it. How does the BIOS in a PC relocate the EXE file? This is done via a BIOS call and therefore the code is in the BIOS. Does anyone have or know where I can get the (any flavour of) BIOS source code? "

and now: my flippant answer!

[dutky]

The real answer to your question (instead of the balsphemous tripe I already posted) is that you can't do relocatable code on an x86 in real mode. If you want to write position independant code, get yourself a real computer, not some piece of Intel inspired trash. I would suggest either a 68K based MCU, or a RISC MCU (MIPS, ARM, or PowerPC) any one of which can be had cheaply from a wide range of sources.

This is, of course, an absurdly flippant and condescending answer, given that you already have the hardware in hand and it would be rediculous to go out and spend more money on extra hardware when you can just code around the brokeness of what you have.

However, if it takes you an extra several weeks to code up the relocating linker-loader, and you are paid the average for a good programmer, you will end up spending more on the relocation software that you would have on a real computer. But your boss (or the bookkeepers, at least) probably won't see it that way.

Cheers!

-- Jeff Dutky

a few more remarks

[dutky]

First I'd like to comment on the remark concerning double linking of .COM files: this is both wastefull (it makes your resultant program twice as large as it otherwise needs to be) and unnecessary (.COM files are already relocatable, since the code fits entirely within a single segment. In order to relocate a .COM just modify the CS register when you load the program).

Second, as for shared ELF libraries: you will notice that the poster specified that he is using a 80186 clone (AMD186ED) which is simply an 8086 with some extra peripheral hardware (timers, parrallel I/O, etc.) on chip and a couple extra instructions. It does not implement any of the 80386 extensions that ELF shared most likely relies on. In 80386 protected mode you can have full 32-bit offsets for NEAR jumps, which gives you true position-independant code without having to resort to load-time kludgery. The 8086 and it's real-mode/16-bit bretheren don't have such niceties. Shared ELF stuff is probably not applicable here.

-- Jeff Dutky

Shared libs...

[Trojan]

If I'm not mistaken, shared ELF libraries are location independent. They do everything relative to the contents of a register. Compiling with -fpic makes sure the compiler doesn't use this register.

EXE tools

[Stonehead]

The link http://www.suddendischarge.com [suddendischarge.com] contains a large collection of tools for playing around with DOS executables. I wrote myself a PKLite-alike wrapper for EXE executables, called Mess 1.31, which includes some "anti-debugging" code. It is open-sourced, except for the anti-debugging part (you may still find the full 1.07 :). The HackStop [tripod.de] project is the same - version 1.11 [suddendischarge.com] has been open-sourced too. Nowadays, DOS is about dead; that's why these projects get open. Most of them still have a taste of the old virus/cracking scene, when the .EXE format was as scary as the NE (for Win16) and PE format (used for Win32 and BeOS applications) were a few years ago. Micros~1's PE format is still being researched. The UPX [nexus.hu] program can compress these PE programs, it might be open-sourced soon. Uncompressors like Procdump exist too, but ProcDump is probably not going open-source. What you might be looking for, is the code that wrappers like HackStop or UPX add to the program being compressed or "protected": if the program is run, the compressed part is decompressed and the relocations must be "filled in". Basically this is what Dutky says above: add DS+10h (10h=16 bytes for the Program Segment Prefix) to all offsets named in the relocation table in the EXE header of the original program.

Check out ecos from cygnus

[A nonymous Coward]

I'll get to your relocatable code question , but as an aside, you might want to check out Ecos [cygnus.com] from Cygnus. I haven't dealt with rom based code for several years now, so I don't know much about ecos. But it comes from Cygnus, is free source (not GPL; their variation on the Mozilla license), and who knows, it may even be ported to your setup.

In general, processors have two kinds of addresses for data and instructions: absolute and relative. Absolute is faster since no airithmetic is involved. A .o file has the symbol name, a static link resolves it immediately, and a dynamic linker resolves it at load/run time.

Relative branches are slower because of the arithmetic, but on some machines the instructions can be quite a bit shorter because a full address is not necessary. Of course, this itself may make enough of a speed difference to cancel the arithmetic, and the code size reduction may be worthwhile too. The linker probably has to compute relative distances at link time.

None of this helps directly with your request for BIOS code, but if you want that just to figure out how it copies code, you may not need it. If your processor supports relative addressing, you probably don't. Make sure you can do everything you want with relative addressing. Some processors are troublesome this way, at least memory says so, but I spent 7 years on just m68k, so I'm a bit hazy on others now.

Of course, you may still need absolute addressing if system subroutines are at absolute locations in low or high memory, and if you have memory mapped I/O.

--

Other Techniques

[Detritus]

Does it have to be an EXE file?

There is an old trick that I've used on 8-bit CPUs. Link the program as an absolute memory image at two different load addresses. Write a program that compares the two images and outputs a relocation list to a file. Then you can use a simple loader that takes an absolute memory image and the relocation list to load the program at any desired address. You should be able to do this with COM files on the 80x86.

relocatable code on x86

[dutky]

You are pretty well screwed if you want to do position independant code on iAPx86 processors prior to the 80386, because of the glorious fun we call Segmented Memory.

On the 8088/8086/80186/80286 and compatibles, you have essentially two kinds of jump instructions: short jumps that add a 8-bot or 16-bit offset to the IP register but do not affect the CS register (remember, your full instruction counter is the 20-bit sum IP+16*CS), and far jumps that replace both the IP and the CS with new values, but do not allow relative addressing.

So you see, you can either have position independant code (jumps addressed from the current IP) or you can have more than 64k of code, but not both. The way around this is to use far jumps in your executable files and modify the target addresses when you load the code into memory at runtime.

I rather doubt that there is a BIOS call to relocate the executable file. I've written a multitasking OS for 8086's, and I don't remember there being such a BIOS call. In fact, I had to write a relocating linking loader myself, so I feel pretty comfortable saying there is no such beast in the motherboard BIOS. You are probably confusing the MS-DOS BIOS (loaded from the file BIOS.SYS on the boot disk) with the motherboard BIOS (contained in ROM). The basics of an .EXE relocating linking loader are, however, pretty simple:

In their header, .EXE files have a table of the offsets of all absolute addresses in the program that are in need of relocation. All you do is, once you have loaded the .EXE into it's new home in RAM, go through the table and add the new base address of the program in RAM to each indicated address in the program image in memory.

There is a reasonable explaination of the .EXE file format and the relocation process on pages 83-85 of the Microsoft MS-DOS Programmer's Reference (Microsoft Press, ISBN 1-55615-546-8, US$27.95) and on page 307 of Disecting DOS (Michael Podanoffsky, Addison Wesley, ISBN 0-201-62687-X, US$39.95)

The Podanoffsky book will provide you with real code to perform this bit of sorcery, but I will quote from the M$ book, since it should be considered more authoritative:

The relocation table is an array of relocation pointers, each of which points to a relocatable-segment address in the program image. The exRelocItems field in the file header specifies the number of pointers in the array, and the exRelocTable field specifies the file offset at which the relocation table starts. Each relocation pointer consists of two 16-bit values and a segment number.

To load an .EXE program, MS-DOS first reads the file header to determine the .EXE signature and calculate the size of the program image. It then attempts to allocate memory. ... [if there isn't enough memory for the program + any extra memory the .EXE file specifies + the OS's bookkeeping data structures (in MS-DOS called the Program Segment Prefix, or PSP) then MS-DOS returns an error, otherwise it allocates the memory -- JSD]

After allocating memory, MS-DOS determines the segment address, called the start-segment address, at which to load the program image. If the value in both the exMinAlloc and exMaxAlloc fields is zero, MS-DOS loads the image as high as possible in memory. Otherwise, it loads the image immediately above the area reserved for the PSP.

Next, MS-DOS reads the items in the relocation table and adjusts all segment addresses specified by the relocation pointers. For each pointer in the relocation table, MS-DOS findes the corresponding relocatable-segment address in the program image and adds the start-segment address to it. Once adjusted, the segment address points to the segments in memory where the program's code and data are loaded.

The preceeding excerpt refers to a memory structure that contains the contents of the .EXE header file. In C structure notation the header looks like this: (in this case, int is 16-bits)

struct EXEHEADER {
int exSignature; /* .EXE signature = 0x5a4d */
int exEstraBytes; /* number of unused bytes in last page of file */
int exPages; /* size of file in 512-byte pages */
int exRelocItems; /* number of pointers in relocation table */
int exHeaderSize; /* header size in paragraphs (16-bytes/paragraph) */
int exMinAlloc; /* minimum extra memory required (paragraphs) */
int exMacAlloc; /* extra memory requested (paragraphs) */
int exInitSS; /* initial stack segment value */
int exInitSP; /* initial stack pointer value */
int exCheckSum; /* checksum, unused, usually zero */
int exInitIP; /* initial instruction pointer value: entry point offset */
int exInitCS; /* initial code segment value: entry point's segment */
int exRelocTable; /* byte offset to relocation table */
int exOverlay; /* overlay number, 0 for resident part */
}

DISCLAIMER: If the OS you are using uses a different executable file format, all of the above is inaccurate, but may be helpfull for purely theoretic purposes, since anything running in x86 real mode needs to be able to solve this bit of kludgery.

-- Jeff Dutky