Wozu Relocation?

[Namenloser]

Ich bereite mich gerade auf eine Betriebssysteme-Klausur vor, und da bin ich gerade am Punkt Relocation.

Also dabei werden ja wohl irgendwelche Adressen angepasst, wenn das Image (z.B. Exe, DLL) an eine bestimmte Stelle im Speicher geladen wird.

Ich frag mich nur: Wo braucht man das überhaupt? Ich habe mich ja mal ein bisschen mit der Generierung von Assembler-Code befasst, und alle JMPs, CALLs usw. beziehen sich in der Regel auf relative Offsets an und nicht auf absolute Adressen. Ich weiß, dass es auch zwar entsprechende Codes für absolute Adressen gibt, hab die aber noch nie in Verwendung gesehen. Ist Relocation nur für diese Instruktionen nötig, die sowieso in der Praxis praktisch nie verwendet werden? Bei relativen Sprüngen wüsste ich nicht, warum da etwas angepasst werden müsste.

Wozu/Wann verwendet man absolute Adressen überhaupt jemals? Der einzige Grund, den ich mir vorstellen könnte, wäre eine minimale Performancesteigerung, da man z.B., wenn man Code aus einer DLL anspringen will, nicht erst einen Pointer dereferenzieren muss, um das Sprungziel zu ermitteln*. Aber das könnte man auch zur Not im Programm selbst regeln mit selbstmodifizierendem Code, Betriebssystemunterstützung bräuchte man eigentlich nicht.

* Häufig macht man das ja so (in der Art):

Delphi-Quellcode:

type
  TMyAPICall = procedure (Foo: DWord); cdecl;
var
  MyAPICall: TMyAPICall = nil;
initialization
  MyAPICall := GetProcAdress(...);

Delphi-Quellcode:

MyAPICall(42); 
// =>
// MOV EAX, [MyAPICall]; <- dereferenzierung 
// CALL EAX; 
// (oder so ähnlich zumindest)

[dummzeuch]

Zitat:

Zitat von Namenloser (Beitrag 1252137)

Ich bereite mich gerade auf eine Betriebssysteme-Klausur vor, und da bin ich gerade am Punkt Relocation.

Also dabei werden ja wohl irgendwelche Adressen angepasst, wenn das Image (z.B. Exe, DLL) an eine bestimmte Stelle im Speicher geladen wird.

Ich frag mich nur: Wo braucht man das überhaupt? Ich habe mich ja mal ein bisschen mit der Generierung von Assembler-Code befasst, und alle JMPs, CALLs usw. beziehen sich in der Regel auf relative Offsets an und nicht auf absolute Adressen.

Das kann nicht sein, denn dazu muessten alle Prozessoren das auch koennen. Das ist aber definitiv nicht der Fall. Du hast Dir vermutlich nur halbwegs aktuelle Intel-kompatible Prozessoren angeschaut.

Zitat:

Zitat von Namenloser (Beitrag 1252137)

Ich weiß, dass es auch zwar entsprechende Codes für absolute Adressen gibt

Genau.

Zitat:

Zitat von Namenloser (Beitrag 1252137)

Wozu/Wann verwendet man absolute Adressen überhaupt jemals? Der einzige Grund, den ich mir vorstellen könnte, wäre eine minimale Performancesteigerung, da man z.B., wenn man Code aus einer DLL anspringen will, nicht erst einen Pointer dereferenzieren muss, um das Sprungziel zu ermitteln*. Aber das könnte man auch zur Not im Programm selbst regeln mit selbstmodifizierendem Code, Betriebssystemunterstützung bräuchte man eigentlich nicht.

Wie schon oben geschrieben: Nicht alle Prozessoren beherrschen relative Adressierung oder es ist ggf. ineffizienter als absolulte Adressierung. Selbst modifizierender Code wiederum ist ein Sicherheitsrisiko und wird deshalb von aktuellen Betriebssystemen teilweise blockiert.

[Namenloser]

Zitat:

Zitat von dummzeuch (Beitrag 1252138)

Das kann nicht sein, denn dazu muessten alle Prozessoren das auch koennen. Das ist aber definitiv nicht der Fall. Du hast Dir vermutlich nur halbwegs aktuelle Intel-kompatible Prozessoren angeschaut.

Ja, bei Prozessoren, die nur absolute Adressen unterstützen, leuchtet es mir ein. Also braucht man das wirklich nur da?

Und wenn Relocation ausgeführt wird, dann wird vom Betriebssystem jeder einzelne Sprung gepatcht, ist das richtig? Das heißt, das Betriebssystem müsste unter Umständen Assembler-Code disassemblieren können? Denn es ist ja nicht gesagt, dass auf jeder Prozessorarchitektur die Zieladresse einfach so „als Klartext“ an einer Byte-Grenze im Code steht.

[Uwe Raabe]

Zitat:

Zitat von Namenloser (Beitrag 1252139)

Und wenn Relocation ausgeführt wird, dann wird vom Betriebssystem jeder einzelne Sprung gepatcht, ist das richtig? Das heißt, das Betriebssystem müsste unter Umständen Assembler-Code disassemblieren können? Denn es ist ja nicht gesagt, dass auf jeder Prozessorarchitektur die Zieladresse einfach so „als Klartext“ an einer Byte-Grenze im Code steht.

Dafür schreibt der Compiler oder Linker eine Relocation Table mit den Adressen die gepatcht werden müssen.

[Namenloser]

Zitat:

Zitat von Uwe Raabe (Beitrag 1252141)

Zitat:

Zitat von Namenloser (Beitrag 1252139)

Und wenn Relocation ausgeführt wird, dann wird vom Betriebssystem jeder einzelne Sprung gepatcht, ist das richtig? Das heißt, das Betriebssystem müsste unter Umständen Assembler-Code disassemblieren können? Denn es ist ja nicht gesagt, dass auf jeder Prozessorarchitektur die Zieladresse einfach so „als Klartext“ an einer Byte-Grenze im Code steht.

Dafür schreibt der Compiler oder Linker eine Relocation Table mit den Adressen die gepatcht werden müssen.

Ja, aber es könnte ja sein, dass ein Pointer z.B. 20 Bits lang ist und die JMP-Instruction so aussieht:

Code:

jjjj aaaa aaaa aaaa aaaa aaaa

Wobei hier jedes Zeichen für 1 Bit stehen soll. Die ersten 4 Bit kodieren die JMP-Instruktion selbst, und die restlichen 20 Bit geben die Zieladresse an.

Dann kann man nicht einfach dem Betriebssystem eine Byte-Adresse zum Patchen geben, weil die zu patchende Adresse nicht an einer Byte-Grenze anfängt.

[BUG]

Zitat:

Zitat von Uwe Raabe (Beitrag 1252141)

Dafür schreibt der Compiler oder Linker eine Relocation Table mit den Adressen die gepatcht werden müssen.

Relocation ist das Konzept, wie es konkret umgesetzt wird, ist eine andere Sache. Es könnte auch einfach bedeuten, eine Sprungtabelle an einer wohl-bekannten Stelle im Code zu patchen.

Wenn Relocation vom Betriebssystem auf eine bestimmte Weise unterstützt wird, dann müssen sich die Programme daran halten. Wenn das Betriebssystem einen Sprungbefehl nicht unterstützt, darf der eben nicht verwendet werden.

[himitsu]

Zitat:

Ich frag mich nur: Wo braucht man das überhaupt?

Einer der Hauptgründe liegt z.B. dran, daß Viele einfach so doof sind und und blind die Vorgaben verwenden.

Drum liegen auch fast alle Delphi-DLLs an der selben Stelle, wenn man mal eigentliche Zieladresse aus den DLLs ausliest.
Nur gibt es da ein Problem, denn an einer Stelle kann nur eine DLL geladen werden, also müssen Nachfolgende verschoben werden.

Und dann gibt es auch noch den Sicherheitsaspekt, wo dann das System die DLLs absichtlich verschiebt.
Wenn eine DLL immer an der selben Stelle liegt, dann können Angreifer direkt auf statische Adressen zugreifen und z.B. Buffer-Overruns so auslegen, daß sie geziehlt bestimmte Strukturen angreifen.
Tja, und wenn man nun absichtlich die DLLs jedes Mal an einer anderen Stelle läd, dann kann man nicht mehr so einfach auf diese "festen" Adressen losgehen.

[Bernhard Geyer]

Zitat:

Zitat von Namenloser (Beitrag 1252143)

Ja, aber es könnte ja sein, dass ein Pointer z.B. 20 Bits lang ist ...

Kann er nicht! Für ein 32-Bit Anwendung sind die Pointer immer 32 Bit lang, unter 64 Bit immer 64 Bit. "Früher" gabs mal noch 16-Bit Adressen und sowas wie Pages um mehr als 64 kByte Adressraum zu haben.

[Bernhard Geyer]

Zitat:

Zitat von himitsu (Beitrag 1252148)

Zitat:

Ich frag mich nur: Wo braucht man das überhaupt?

Einer der Hauptgründe liegt z.B. dran, daß Viele einfach so doof sind und ...

Dem möchte ich widersprechen. Ich habe absichtlich alle unserer DLL's an die gleiche Base-Adresse gelegt damit Windows (auch ohne Adressverwürfler) diese immer nach eigener Logik optimal läd. Was nützt mir eine unterschiedliche Angabe pro DLL wenn ich nicht weiß wie viel Platz die aktuelle DLL-Inkarnation benötig und ich mit einer unterschiedlichen Base-Adresse mir meinen beschränkten 32-Bit Adressraum "zukleistere" so das ich nur noch sehr kleine nicht unterbrochene Adressräume habe.

Und die Zeit die Windows benötigt die zwangsweise nötige Realocation durchzuführen ist seit Jahren irrelevant.

[mkinzler]

Das gilt für heutige Intelprozessoren. Bei anderen Prozessoren kann es anders sein, bzw. war es.
So hatten 8-Bit-Prozessoren 16-Bit Adressregister ( den 256 Bytes wären etwas wenig Speicher). 68000er Prozessoren hatten auch bei 16-Bit Datenbus schon 32-Bit für Prozessoren ( von denen aber anfänglich nur 24 Bit ausgewertet wurden).

[Namenloser]

Richtig, und bei speziellen (Mikro-?)Prozessoren gibt es soweit ich weiß auch Pointer-Längen, die kein Vielfaches von 8 sind.

[himitsu]

Weiß Jemand, wie diese Relocationstabellen aufgebaut sind?

Entweder man gibt da mit an, was wie angepasst werden muß (bei jeder Stelle einzeln oder indem man Gleiches gruppiert),
oder man analysiert die Stelle, welche angepasst werden muß,
oder man definiert, daß die anzupassenden Stellen immer nur ein bestimmtes Format haben können/dürfen.

Ersteres und Letzeres ist einfacher und ich würde Eines davon verwenden,
denn es gibt nicht nut Jumps anzupassen, sondern auch "Zeiger" auf betimmte Resourcen, wie z.B. vielen String-Konstanten im Code.

[Namenloser]

Zitat:

Zitat von himitsu (Beitrag 1252155)

es gibt nicht nut Jumps anzupassen, sondern auch "Zeiger" auf betimmte Resourcen, wie z.B. vielen String-Konstanten im Code.

Stimmt, daran hatte ich gar nicht gedacht. Da macht Relocation auch Sinn.

[BUG]

Zitat:

Zitat von himitsu (Beitrag 1252155)

Weiß Jemand, wie diese Relocationstabellen aufgebaut sind?

Wenn du das wirklich wissen willst, ist vermutlich die Dokumentation des PE-Formats ein guter Recherche-Startpunkt.

Zitat:

Zitat von Namenloser (Beitrag 1252157)

Da macht Relocation auch Sinn.

Ich denke, warum Relocation Sinn macht, ist leicht zu erkennen: Adresskonflikte bei Laufzeitbibliotheken, Address-Randomisierung (Sicherheit) oder Kompaktierung (bei Maschinen ohne virtuelle Adressen). Wie es gemacht wird und welche Ansprüche dabei an den Code / Objektdateien gestellt werden, ist eine andere Sache.

Wenn man nur relativ (von wo aus auch immer) adressiert und das von der Hardware unterstützt wird, dann braucht man keine Relocationstabellen. Je mehr Adressierungsarten unterstützt werden, desto komplizierter werden auch die Tabellen (oder sonstige Methoden).

[Aphton]

Also ich hab das noch grob in Erinnerung, sind bereits zwei Semester her seit der BS VO xD

Im Grunde ist es ja so, dass DLLs als Shared Memory Objekte geladen werden, sprich das Betriebssystem weiß, ok, an diesem Modul wird sich im Speicher kaum etwas ändern, laden wirs ein einziges mal und jedesmal, wenn eine Anwendung, egal welche und wie viele, darauf zugreifen wollen, kriegen sie dieselbe Adresse im Hauptspeicher bzw. dieselbe (=einzige) Instanz des Moduls.
Folglich kann es der Fall sein, dass z.B. mehrere DLLs konfliktäre Anfangsadressen haben. Die DLL wird dann auf eine bestimmte andere freie Stelle im Speicher geladen/gemappt und die Relocation wird angewandt.
Ich weiß jetzt nicht genau, inwiefern Virtualisierung bei shared Objekten stattfindet..

Beispiel:

Code:

Shared Objekt "X":
Basisadresse: 10
Größe: 100
Adressraum: 10..110

Shared Objekt "Y":
Basisadresse: 100
Größe: 50
Adressraum: 100..150

- X wurde geladen, Y soll nun geladen werden
- Adressraum bereits belegt, Relocation muss stattfinden
-- Y an eine freie und genügend große Stelle laden
-- alle absoluten Adressen dementsprechen neu berechnen
(hier hilft dann evt. die Relocation Table iwie, kA. wie genau; relative Adressen werden übrigens nicht angerührt, was ja Sinn macht)

Dasselbe gilt im Grunde auch für non-shared Memory Objekte (Exe?). Deren Adresse kann auch mit bereits geladenen DLLs kollidieren.
Achja, wie genau dann die Relocation funktioniert weiß ich auch nicht. Das haben wir, glaub ich, gar nicht in Detail durchgenommen.

Bin mir da aber absolut nicht mehr sicher. Du kannst dir da vlt. etwas besseres daraus reimen?!

[Namenloser]

Danke für den ausführlichen Post, aber so weit war mir das schon klar. Ich stand nur irgendwie auf dem Schlauch, wo man sowas braucht, da ich beim Speicher nur gedacht habe an: Code (relative Sprünge), Stack (auch relativ) und Heap (sowieso dynamisch). An sowas wie Konstanten oder globale Variablen hatte ich nicht gedacht.

[BUG]

Zitat:

Zitat von Aphton (Beitrag 1252165)

Achja, wie genau dann die Relocation funktioniert weiß ich auch nicht. Das haben wir, glaub ich, gar nicht in Detail durchgenommen.

Weil es relativ nutzloses Wissen ist. 99% der Studenten werden niemals damit zu tun haben. Die, die es wissen müssen, weil sie entweder Loader oder Compiler/Linker schreiben, müssen sich eh mit der entsprechenden Dokumentation auseinandersetzen.

Das es passiert, ist wichtig zu wissen.
Warum es nötig ist, ist wichtig zu wissen.
Was allgemein gemacht wird / werden kann, ist relativ trivial.
Was im Detail passiert ist ziemlich System-spezifisch und interessiert nur sehr wenige.

[JamesTKirk]

Zitat:

Zitat von Namenloser (Beitrag 1252170)

Danke für den ausführlichen Post, aber so weit war mir das schon klar. Ich stand nur irgendwie auf dem Schlauch, wo man sowas braucht, da ich beim Speicher nur gedacht habe an: Code (relative Sprünge), Stack (auch relativ) und Heap (sowieso dynamisch). An sowas wie Konstanten oder globale Variablen hatte ich nicht gedacht.

Absolute Sprünge sind durchaus Gang und Gäbe. Calls von Subroutinen werden zum Beispiel meist mit nem Label gemacht und die sind dann absolut. Oder denke an Prozedurvariablen. Da speicherst du ja den Pointer zu der Prozedur in einer Variable und wenn der Compiler da jetzt die relative Adresse speichern würde, dann wäre die Adresse ja nur für den Punkt der Zuweisung gültig, aber nicht wenn er 2000 Befehle weiter dann letztendlich ausgeführt wird. Deswegen hat jede DLL (oder unter Linux ein Shared Object) eine Basisadresse, relativ zu der absolute Adressen angesehen werden. Die Relocationtable enthält dann die Positionen aller absoluten Adressen im Code (deren "Deklaration" und deren Verwendung), so dass Windows diese dann im Image anpassen kann. Linux macht das übrigens nicht (und Mac OS X auch nicht). Dort gibt es das Konzept von PIC, was für Position Independant Code steht. Da hält der Compiler in einem Register dann eine Global Offset Table (GOT), in der an bestimmten Offsets die Adressen von globalen Variablen, Prozeduren, etc. stehen und der dynamische Linker ist dann frei die Bibliothek an eine beliebige Stelle zu laden ohne erst noch das Image anpassen zu müssen.

Gruß,
Sven

[Zacherl]

Wenn du mehr über den Aufbau der .reloc Section wissen willst, schau mal hier rein:
http://msdn.microsoft.com/en-us/libr.../gg463119.aspx

Grob gesagt enthält die Tabelle (unter x86 und x64) die direkten Offsets zu den absoluten Adressen. Opcodes, Prefixes, etc. werden sozusagen einfach übersprungen. Unter Verwendung sind zur Zeit (bei Windows Kompilaten) nur zwei verschiedene Relocation Typen. Bei beiden wird erst die Differenz zwischen gewünschter ImageBase und reeller ImageBase gebildet und dann zur Adresse addiert.

BASED_HIGHLOW kommt hierbei bei 32 bit Kompilaten vor und besagt, dass die Zieladresse 32 Bit lang ist. 64 Bit Kompilate verwenden stattdessen BASED_DIR64, um zu signalisieren, dass volle 64 Bit für eine Adresse verwendet werden.

Laut Dokumentation gibt es noch weitere (zZ. unbenutze Typen), welche beispielsweise auch 16 Bit Adressen signalisieren könnten.

[Namenloser]

Okay, danke für die Info. (Das ist mal wieder typisch Microsoft, das Dokument nur als Word-Document bereitzustellen... ich habe hier gerade kein Programm um sowas zu öffnen.)

[himitsu]

Zitat:

Zitat von Namenloser (Beitrag 1252270)

(ich habe hier gerade kein Programm um sowas zu öffnen.)

Ich hab immer ein OpenOffice Portable an meinem Schlüsselbund (USB-Stick).

[p80286]

Zitat:

Zitat von JamesTKirk (Beitrag 1252195)

Absolute Sprünge sind durchaus Gang und Gäbe. Calls von Subroutinen werden zum Beispiel meist mit nem Label gemacht und die sind dann absolut.

Meine Assemblerzeiten sind schon ziemlich lange her, aber wird die Adressierung nicht immer relativ zu CodeSegment und/oder DatenSegment vorgenommen?

Einzige mir bekannte Ausnahme, das "Video-Segment" und die Interrupttabelle. Und auch da gehörte es zum guten Ton, den Segmentwert in einer Konstanten/Variablen vorzuhalten um auf evtl. Verschiebungen reagieren zu können.

Gruß
K-H

[BUG]

Zitat:

Zitat von p80286 (Beitrag 1252283)

Meine Assemblerzeiten sind schon ziemlich lange her, ...

Scheint so :mrgreen:
Das Ganze funktionierte mit segmentierten Speicher (z.B. auf Intel-Maschienen). Heutzutage ist diese Adressumsetzung abgeschaltet, weil es niemand mehr ernsthaft benutzt.
Zwar gibt es noch Legacy-Unterstützung, aber es war damals schon langsam und heute wird es nicht viel besser sein.

[Mikkey]

Zitat:

Zitat von p80286 (Beitrag 1252283)

Meine Assemblerzeiten sind schon ziemlich lange her, ...

Wohl wahr, Segmente gibt es seit den 32-Bit-Zeiten nicht mehr (18 Jahre her?). Aber Nomen est Omen...

[JamesTKirk]

Zitat:

Zitat von p80286 (Beitrag 1252283)

Zitat:

Zitat von JamesTKirk (Beitrag 1252195)

Absolute Sprünge sind durchaus Gang und Gäbe. Calls von Subroutinen werden zum Beispiel meist mit nem Label gemacht und die sind dann absolut.

Meine Assemblerzeiten sind schon ziemlich lange her, aber wird die Adressierung nicht immer relativ zu CodeSegment und/oder DatenSegment vorgenommen?

Wie der Rest schon gesagt hat: unter 32 (und 64) Bit gibt es keine Segmente mehr. CS und DS sind fest auf 0 gesetzt, FS wird von Microsoft verwendet, um in FS:0 den Thread Execution Block zu speichern (bei 32 Bit, bei 64 Bit ist das glaub ich GS) und GS ist soweit ich weiß auch 0. Somit erklärt sich das mit absoluten Sprüngen von selbst. ;)

Gruß,
Sven

[p80286]

Danke für die Erläuterung, ich bin davon audsgegangen, das CS und Konsorten vom Loader vorbelegt werden.

Gruß
K-H

[implementation]

Zitat:

Zitat von JamesTKirk (Beitrag 1252195)

Dort gibt es das Konzept von PIC, was für Position Independant Code steht.

PIC und Relocation hat doch nichts mit Windows oder Linux zu tun. Wenn ich auf Windows -fPIC übergebe, kriege ich da doch auch PICode, und wenn ich auf Linux kein -fPIC angebe, kriege ich da relozierbaren.

[JamesTKirk]

Ähm, nein (zumindest, wenn du von FPC sprichst). Unter Windows wird -fPIC ignoriert (da sollte auch eine entsprechende Warnung vom Compiler generiert werden) und bevor du fragst: ich hab das im Compiler Quellcode verifiziert. Alle vier Windows Targets (i386-win32, x86_64-win64, arm-wince, i386-wince) setzen das Flag

Delphi-Quellcode:

tf_no_pic_supported

. Selbst, wenn du unter Windows PIC Code generieren würdest, kämest du um Relocations allerdings nicht herum, da dies ja auch die restlichen Daten im Image betrifft.
Und unter Linux ist der wichtige Punkt, dass Linux nicht reloziert. Ein ELF Image hat keine Relocation Table, also kann der dynamische Linker auch nicht wissen, was er wohin verschieben muss.
Unter Linux kommt man um PIC quasi nicht herum, während du unter Windows quasi um Relocation nicht herum kommst.

Gruß,
Sven

[implementation]

Zitat:

Zitat von JamesTKirk (Beitrag 1252459)

Unter Linux kommt man um PIC quasi nicht herum, während du unter Windows quasi um Relocation nicht herum kommst.

Ich bekam gerade beim Kompilieren von kde-base/kdelibs auf Gentoo GNU/Linux folgende Fehlermeldung:

Zitat:

/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/../../../../x86_64-pc-linux-gnu/bin/ld: CMakeFiles/kdecore.dir/kernel/kstandarddirs.o: warning: relocation against `KStandardDirs::realFilePath(QString const&)' in readonly section `.text'.
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/../../../../x86_64-pc-linux-gnu/bin/ld: CMakeFiles/kdecore.dir/localization/klocalizedstring.o: relocation R_X86_64_PC32 against symbol `KLocalizedString::KLocalizedString(char const*, char const*, char const*)' can not be used when making a shared object; recompile with -fPIC
/usr/lib/gcc/x86_64-pc-linux-gnu/4.6.3/../../../../x86_64-pc-linux-gnu/bin/ld: final link failed: Bad value

Ich will jetzt nicht die Problemlösung diskutieren, aber die Meldung weist für mich darauf hin, dass auch hier Relocation möglich ist (und die GNU Build Chain dies sogar als Standardfall annimmt).

Und die Wikipedia sagt sogar:

Zitat:

The ELF executable format and SO shared library format used by most Unix-like systems allows several types of relocation to be defined.

Und so sieht die Tabelle wohl aus.