Relocation

RELOCATIONby Torbjørn Ose (from ST-Klubben, Norway)

Hello World

This is the answer to the real question: What the heck is going
on when my ST loads a executable file and executes it?

Some of you have undoubtly looked at a .PRG,.APP,.TTP,.TOS or
similar file at least once in your life. If you know anything at
all about 68000 assembly language you have probably seen that
your files looks as though they are supposed to run from adress
zero (thats $0). Since we all know that this is impossible due to
system variables, vector tables and other important things, it is
obvious that something happens. Well it does, and I am now going
to explain what it is.

The operating system loads the file and then relocates it. It
really is that simple! But I am going one step further and I will
tell you HOW the relocation is done by the operating system.

An executable file is stored on a disk like this:

- Header (28 bytes)(thats $1c)
Contains: Facts about the programfile

- Text
Contains: Your program
(Don't ask me why it's called "Text")

- Data
Contains: Your programs data segment

- Symbol
Contains: Your programs symbol table (Used by linkers?)

- Reloc
Contains: The relocation table

In this article I will tell you about the relocation table. It is
built up like this:

- 1 Long Word
- Usually a lot of bytes
- A terminating zero byte

As I already told you at the beginning of this article a program
is assembled to start from memory location zero. Due to this all
absolute adresses are stored as long words relative to zero. This
is important to understand so make sure you do just that. The
long word in the relocation table points to the first absolute
adress in your program. The bytes follwing the long word in the
relocation table show the distance from one absolute adress to
the next one and so on. I can now hear all your freaks out there
shout:"What happens if the distance is more than 254 bytes and
why 254 and not 255?" Since we only deal with even adresses we
must use 254. What happens is that a byte containing 1 is placed
in the table. This shows that we should move our pointer 254
bytes forwards before we go on with the next byte in the
relocation table. The longer the distance to the next adress the
more 1's are placed in the table. All this continues until we
reach a byte containing nothing. (This indicates the end of the
table)

Well now we know how to find the absolute adresses that needs to
be relocated. How do we relocate them?

Since all the absolute adresses are relative to zero, it is very
easy to relocate them to our new adress. All we have to do is to
take the start adress of our program (The "Text" bit) and add to
the value already stored in the absolute adresses.

Lets look at an example:

This is the programs source file

move.l #text,-(a7)
move.w #9,-(a7)
trap #1
addq.l #6,a7
bra Go_on
text:
dc.b "this is an example",0
ds.b 300 ;to get a 1 in the table
dc.b 0
Go_on:
move.l #text2,-(a7)
move.w #9,-(a7)
trap #1
addq.l #6,a7
rts
text2:
dc.b "Bye",0
end

Then we are going to have a look at the file as it is before it
is relocated.

Address Objectcode Line Sourcetext
000000 :2F3C00000012 1 MOVE.L #TEXT,-(A7)
000006 :3F3C0009 2 MOVE.W #9,-(A7)
00000A :4E41 3 TRAP #1
00000C :5C8F 4 ADDQ.L #6,A7
00000E :60000142 5 BRA GO_ON
000012 : 6 TEXT:
000012 :7468697320697320616E 7 DC.B "this is an example",0
206578616D706C6500
000025 : ^ 12C 8 DS.B 300
000151 :00 9 DC.B 0
000152 : 10 GO_ON:
000152 :2F3C00000162 11 MOVE.L #TEXT2,-(A7)
000158 :3F3C0009 12 MOVE.W #9,-(A7)
00015C :4E41 13 TRAP #1
00015E :5C8F 14 ADDQ.L #6,A7
000160 :4E75 15 RTS
000162 : 16 TEXT2:
000162 :42796500 17 DC.B "Bye",0
000166 : 18 END

As you can see all the adresses are now relative to zero. There
are only two absolute adresses ($00000012 and $00000162). You can
see that these are used to point to the text strings. Allright,
lets say we relocate this file to memory location $53bc4. Then it
looks like this:

Adr Objectcode Disassembled
053BC4 2F3C00053BD6 MOVE.L #$53BD6,-(A7) ; $12+$53BC4
053BCA 3F3C0009 MOVE.W #9,-(A7)
053BCE 4E41 TRAP #1
053BD0 5C8F ADDQ.L #6,A7
053BD2 60000142 BRA $53D16
053BD6 7468 DC.B "th"
053BD8 6973 DC.B "is"
053BDA 20697320 DC.B " is "
053BDE 616E DC.B "an"
053BE0 2065 DC.B " e"
053BE2 7861 DC.B "xa"
053BE4 6D70 DC.B "mp"
053BE6 6C65 DC.B "le"
053BE8 00... DS.B 302 ; 302 Empty bytes
053D16 2F3C00053D26 MOVE.L #$53D26,-(A7) ; $162+$53BC4
053D1C 3F3C0009 MOVE.W #9,-(A7)
053D20 4E41 TRAP #1
053D22 5C8F ADDQ.L #6,A7
053D24 4E75 RTS
053D26 42796500 DC.B "Bye",0
053D2A 000000020154 ;This is the relocation table
053D30 00

Looking at the relocation table we find that the long word
contains $00000002 and then we find three bytes containing 1,$54
and 0. As we know the zero byte indicates the end of the table.
If we then look at the relocated program we can see that the
first adress that is relocated is indeed the start adress of the
program+$2 (The long word in the relocation table). As you
noticed from my remark statement the new value of this absolute
adress is $12+$53BC4 ($53BC4 is the start adress of the program).
Then we look at the next byte in the relocation table, it is a 1.
Then we know that we are supposed to jump 254 bytes forwards
before we continue. We are now at memory location $53BC6 and when
we add 254 to it we end up at memory location $53CC4. Then we
look at the next byte in the relocation table and find that it is
$54. We add this to our adress and get $53D18. If we look at our
program we discover that this is the memory location for the next
absoulte adress that needs to be relocated. Then $53BC4 are added
to $162 and we get the correct absolute adress. The next byte in
the relocation table is a zero and the program is relocated and
ready for execution.

To find the relocation table you have to add together the length
of the individual parts of the program file. The lengths can be
found in the header at the following offsets from the start of
the header:

$02 Program lengt (Text bit)
$06 Length of initialised data
$0E Length of symbol table

They are all 32 bit. Initialised data and symbol tables are
rarely used.

In the programs folder on this disk you will find a short
assembly language routine that relocates a file. It is documentet
and I will not explain it any further in this aritcle. The file
is called: RELOCATE.S

I hope you have been able to understand what I have tried to
explain, and that at least some of you find the information
useful. The examples are made with DEVPAC2 and ASSEMPRO.