The linker32 is written for 32 bit platforms. The linker performs various tasks like:

• Place code in the memory
• Create type descriptors and constant blocks
• Create system table
• Create target image

As a first step the linker must be initialized with the method init(). What happens is:

• Determine size of java/lang/Object and add this size to string header
• Search segments for the system table
• Delete previous target image

Each class has a constant block. Certain interfaces need a reduced constant block and arrays just need a type descriptor, see Type Descriptor. The constant block holds information about the class, which is constant:

• Header (base, size, …)
• Global pointer list
• Type descriptor
• String pool
• Constant pool
• Checksum

Structure of the constant pool for a class

The const pool contains values of type float and double which are not placed directly into the code. After all elements are added the constBlockSize can be determined and the indices (Item.index) of all elements will be fixed. It's important to note that all elements, which are addresses (AddressItem, ConstantBlockItem, …), simply contain a reference to the according item. Only later, after address fixing, can the real addresses be inserted!
When the system ist starting up, the Runtime System reads the start addresses of the constant block for all classes from the System Table (see below). With the predefined offset cblkClinitAddrOffset the address of the class constructor can be fetched in order to load a class. With another offset the heap manager can read the global references of this class. This information is used by the garbage collection. codeBase holds the start address of code of a class whereas codeSize is the size of the code. Methods, which are defined in the configuration as system methods and which are assigned a fixed offset are excluded from codeSize (Exception Handlers).

In the compiler the constant block is modeled as linked list of ch.ntb.inf.deep.linker.ConstBlkEntry. Depending on the type of entry one of the following classes is used.

• AddressEntry: For entries representing an address.
• ConstantEntry: For entries representing a constant (StdConstant).
• FixedValueEntry: For entries representing a fixed value (e.g. a size).
• InterfaceEntry: For entries representing an interface entry (id and offset).
• StringEntry: For entries representing a constant string (StringLiteral).
• OffsetEntry: For entries representing an offset to the table with all instance references.

The structure and purpose of the Type Descriptor is described separately.

The string pool holds the constant strings of a class. They are stored as follows (also see Strings:

[ tag                ]
[ stringClassAddress ]
[ Object             ]
[ nofChars           ]
[ chars              ]
[ ⋮                  ]

The characters of the string are stored in 2-Byte-Unicode.

The constant pool holds the constants of a class. Currently we only store there floating point numbers (float and double). Integer numbers are packed into the instructions directly (even long). Floating point numbers are stored in IEEE 754 format, the high word of a 64 bit double is at the lower address (bid endian).

Example:

[40490FDB] 3.1415927 (float)
[401921FB] 6.283185307179586 (double)
[54442D18]

Machine Code: Size and Offsets

Before the memory map can be fixed, a couple sizes and offsets must be calculated for each class:

• void calculateCodeSizeAndOffsets(Class): This methods determines the size of the machine code of the whole class and sets the field offset of each method of this class. offset is the byte offset of the machine code of a method in the memory starting from the start address of the code of this class. If a method offset is given by the configuration (e.g. exception handlers), then this method is not included in the culculation of the code size. The offset given by the configuration is not relative to the base of a class but to the base of the appropriate segment.
• void calculateGlobalConstantTableSize(): This method calculates the size of the global constant table.

The linker assembles a system table for the whole system. This table must be loaded to a prefixed address in the target system and holds information for the Runtime System. Various settings must be handled:

1. The system runs from the flash
2. The system runs from the RAM.
3. The base system is in the flash. Further classes are later loaded into the RAM. This case needs two system tables. The flash holds a system table which contains only classes which are present in the flash. The system table in the RAM must hold all classes. This feature is not implemented yet

In the compiler the system table is modeled as list. as elements it uses the same blocks as for the constant block. Additionally SysTabEntry is used to reference the constant block of a class.

The structure of the system table is:

Structure of the system table

Bevor die Systemtabelle zusammengestellt werden kann, muss der Klassenkonstruktor der Kernel-Klasse gefunden werden. Dazu wird der Klassennamen aus der Konfiguration geladen und anschliessend die Methode <clinit> gesucht.

Nun kann die Systemtabelle aufgebaut werden. Dazu wird als erstes der Offset zum Beginn der Klassenliste (Liste mit der Basisadresse des Konstantenblocks jeder Klasse) eingefügt. Anschliessend werden die Informationen zu Heap und Stack eingefügt. Anschliessend die Anzahl vorhandener Klassen und die bereits erwähnte Liste mit den Basisadressen der Konstantenblöcke. Die Systemtabelle wird mit dem Wert 0x0 abgeschlossen.

Der letzte Teil mit den Referenzen auf den Konstantenblock der einzelnen Klassen ist wie folgt zusammengestellt. Zuerst kommen alle Klassen mit einem Klassenkonstruktor. Diese Klassen sind bereits in der korrekten Reihenfolge gemäss class_initialization sortiert. Anschliessend kommen alle nicht-initialisierten Klassen. Arrays und Interfaces haben keinen Konstantenblock und kommen nicht in die Liste mit Ausnahme von Interfaces, die einen Klassenkonstruktor haben, siehe Interfacemethoden in type_descriptor.
Beim MPC555 wird die Systemtabelle in der Dual-Mapped-Section direkt nach dem Exceptioncode positioniert (Addresse 0x2000 → siehe Memory Map).

Maschinencode: Grösse und Offsets

Das Platzieren des Codes, der statischen Variablen und der Konstanten im Speicher geschieht wie folgt. Als erstes wird jeder Klasse ein Memory-Segment für den Code (Class.codeSegment), die statischen Variablen (Class.varSegment) und die Konstanten (Class.constSegment) zugeteilt. Welche Segmente das sind, wird der Konfiguration entnommen. Dabei läuft der Linker rekursiv durch die möglichen Segmente und wählt das erste passende aus. Während dieser Zuteilung wird der im Segment benutzte Platz gespeichert (Segment.usedSize) und der entsprechende Offset (Class.codeOffset, Class.varOffset und Class.constOffset) zugeteilt. Auch für jedes Array und für jedes benötigte Interface wird ein Segment (Class.constSegment) für den Typedescriptor gesucht und der Offset (Array.offset, Class.offset) gesetzt. Anschliessend wird die verwendete Grösse auch noch für das Systemtabellen-Segment gesetzt und das Speichersegment für die globale Konstantentabelle festgelegt. In einem weiteren Schritt wird die Grösse für jedes verwendete Segment festgelegt (sofern nicht bereits in der Konfiguration vorgegeben). Nun kann für jedes verwendete Segment die Basisadresse berechnet werden.
Achtung: Ganz zu Beginn müssen Systemmethoden, die einen in von Konfiguration gegebenen Offset haben (Exception-Handlers), bereits im passenden Segment platziert werden. Das führt zu „Löchern“ in diesem Segment. Diese Löcher können durch eine effizientere Allokation eliminiert werden, was aber zur Zeit nicht gemacht ist.

Nachdem der Code, die statischen Variablen und der Konstantenblock jeder Klasse und auch die Systemtabelle und die globale Konstantentabelle platziert sind, werden nun die absoluten Adressen berechnet. Dazu steht die Methode void calculateAbsoluteAddresses(Class) bereit. In einem ersten Schritt werden die Adressen für die statischen Felder bestimmt. Dazu läuft der Linker durch die entsprechende Liste (Class.classFields) durch und berechnet die absolute Adresse (Item.address). Die Adresse wird nur bei nicht konstanten Feldern gesetzt. Im nächsten Schritt werden die Adressen der Methoden berechnet. Dabei müssen die durch die Konfiguration absolut positionierten Methoden (Exception-Handlers)wiederum speziell behandelt werden. Als drittes werden die Adressen für die Konstanten im Constant pool und die Strings im String pool berechnet.

Als letztes wird noch die Adresse der Klasse selbst (Class.address) auf den Eintrag size im Typ-Deskriptor gesetzt.

Diese Methode muss vom Launcher für jede Klasse aufgerufen werden.

Nach dem Festlegen der Adressen kann nun der Konstantenblock aktualisiert werden. Dazu legt die Methode void updateConstantBlock(Class) als erstes die Basisadresse des Codes (codeBase) fest. Anschliessend werden auch noch die Basisadresse für die Klassen-Variablen (varBase) und die Gesamtgrösse der Klassen-Variablen (varSize) festgelegt. Als letztes wird noch die Grösse eines Objektes der Klasse (size) im Type descriptor aktualisiert.

In der globalen Konstantentabelle werden Konstanten gespeichert, die nicht zu einer Klasse gehören, sondern z.B. zur Laufzeit für die Konvertierung von int zu float verwendet werden.

Zum Schluss wird das Target Image erstellt. Dabei wird für jede Methode jeder Klasse und für Konstantenblock (einer pro Klasse, Array oder Interface) je ein TargetSegment erzeugt und in einer Liste abgelegt.

Die Felder index, offset und address der Klasse ch.ntb.inf.deep.classItems.Item werden, je nach dem was Item repräsentiert, anders verwendet. Die untenstehende Liste gibt einen Überblick, wann welches Feld wie verwendet wird.

Bemerkung: Angaben in Eckigen Klammern bezeichnen den Typ. Beispiel: [Class] bedeutet das dieses Objekt vom Typ ch.ntb.inf.deep.classItems.Class ist.

• index: Wird verwendet, um Interfaces für Interfacemethoden zu nummerieren.
• offset: Wird nicht verwendet, ist immer -1.
• address: Die absolute Adresse des Typdescriptors (des Eintrags size).

• index: Wird nicht verwendet, ist immer -1.
• offset: Offset des Typdescriptors im Segment.
• address: Die absolute Adresse des Typdescriptors.

• index: Bei Instanzmethoden der Index der Methode in der Methodentabelle (beginnend bei 0). Bei Klassenmethoden ist index immer -1. → Wird vom CFR gesetzt.
• offset: Byteoffset der Methode ausgehend von der Startadresse des Codes der Klasse.
• address: Absolute Adresse der Methode.

static final Object o = new Object();

1. Klassen-Felder [DataItem]:
   1. Konstante Felder [NamedConst]:
      • index: Wird nicht verwendet, ist immer -1;
      • offset: Wird nicht verwendet, ist immer -1;
      • address: Wird nicht verwendet, ist immer -1;
   2. Nicht konstante Felder [DataItem]:
      • index: Wird nicht verwendet, ist immer -1.
      • offset: Byteoffset des Feldes (beginnend bei 0 für das erste Feld).
      • address: Absolute Adresse des Feldes.
2. Instanz-Felder [DataItem]:
   • index: Wird nicht verwendet, ist immer -1;
   • offset: Byteoffset des Feldes beginnend bei 0 (inkl. Berücksichtung der Felder der Oberklassen).
   • address: Wird nicht verwendet, ist immer -1;

1. Zahlen [StdConstant]:
   • index: Wenn die Konstante vom Typ float oder double ist, ist index der Index der Konstante im Konstantenpool. Ansonsten immer -1;
   • offset: Wenn die Konstante vom Typ float oder double ist, ist offset der Byteoffset der Konstante im Konstantenpool. Ansonsten immer -1;
   • address: Wenn es sich um eine Konstante vom Typ float oder double handelt, ist address die absolute Adresse der Konstante (direkt im Konstantenblock). Ansonsten immer -1.
2. Stings [StringLiteral]:
   • index: Wenn es sich bei der Konstante um einen String handelt, so wird in index der Index des Strings im Stringpool abgelegt.
   • offset: Wenn es sich bei der Konstante um einen String handelt, so wird in offset der Byteoffset des Strings im Stringpool abgelegt.
   • address: Absolute Adresse des konstanten Strings (direkt im Konstantenblock).