Trampolin (Informatik)

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche

Ein Trampolin ist ein Stück Code, das nach Konfiguration von Umgebungsvariablen zu einer anderen Funktion springt. Ein Trampolin dient quasi als Sprungbrett, um andere Funktionen aufzurufen. Dies ist insbesondere nützlich, wenn man Parameter übergeben möchte, die sich nicht in der Signatur der Funktion wiederfinden.

Motivation[Bearbeiten]

In der Sprache C kann man die Funktion qsort verwenden, um Felder von Daten zu sortieren. qsort hat folgende Signatur:

 void qsort(void *feld,
            size_t elementzahl,
            size_t elementgroesse,
            int(*vergleichsfunktion)(const void *a, const void *b));

Der Funktion werden ein Feld als Zeiger, die Anzahl der Elemente des Feldes, die Größe jedes Elementes in Bytes und eine Vergleichsfunktion übergeben. Die Vergleichsfunktion erhält als Argument zwei Zeiger zu den zu vergleichenden Elementen (a und b) und liefert einen Wert kleiner Null für a < b, Null für a == b und einen Wert größer Null für den Fall a > b zurück.

Angenommen, man möchte eine Funktion schreiben, die ein Feld von vorzeichenlosen Ganzzahlen unsigned int zuerst nach ihrem Rest bzgl. eines festen Divisors und dann nach ihrer Größe sortiert. Wenn der Divisor eine feste Konstante DIVISOR ist, dann ist die Funktion modsort leicht zu implementieren:

#include <stdlib.h>
 
/* Hilfsfunktion zum Vergleich */
static int modvergleich(unsigned int *a, unsigned int *b) {
  unsigned int rest_a = a % DIVISOR, rest_b = b % DIVISOR;
 
  /* nach Rest sortieren, dann nach Wert sortieren */
  if (rest_a != rest_b) {
    if (rest_a > rest_b)
      return 1;
    else
      return -1;
  } else {
    if (a == b) return 0;
    else if (a > b) return 1;
    else return -1;
  }
}
 
/* eigentliche Sortierfunktion */
void modsort(unsigned int *feld, size_t elementzahl) {
  qsort(feld,elementzahl,sizeof(unsigned int),&modvergleich);
}

Aber was tut man, wenn DIVISOR erst zur Laufzeit bekannt ist? Man könnte hier eine global Variable verwenden, dies ist aber insbesondere bei parallelem Code ein Problem: Ein anderer Thread könnte die Variable überschreiben und so die Ergebnisse verfälschen (Mit modernen Compiler-Erweiterungen wie z.B. Thread-local storage ist dies lösbar). Was tut man also? Hier kommen Trampoline ins Spiel: Es wird die Adresse eines zur Laufzeit berechneten Trampolins an die Funktion qsort übergeben. Dieses füllt den Divisor als zusätzliches Argument ein und erlaubt so eine Lösung des Problems.

Verwendung von Trampolinen[Bearbeiten]

In der Regel werden Trampoline nicht direkt verwendet, weil die meisten Sprachen für diese keine direkte Unterstützung bieten. GCC hat eine Spracherweiterung für die Sprache C, die verschachtelte Funktionen, also Funktionsdefinitionen in anderen Funktionsdefinitionen, erlaubt. Fordert man einen Zeiger auf eine innere Funktion an, so generiert gcc ein Trampolin[1] auf dem Stack:

#include <stdlib.h>
 
/* Sortierfunktion mit Extra-Divisor */
void modsort2(unsigned int *feld, size_t elementzahl, unsigned int divisor) {
  int modvergleich(unsigned int *a, unsigned int *b) {
    unsigned int rest_a = a % divisor, rest_b = b % divisor;
 
    /* nach Rest sortieren, dann nach Wert sortieren */
    if (rest_a != rest_b) {
      if (rest_a > rest_b)
        return 1;
      else
        return -1;
    } else {
      if (a == b) return 0;
      else if (a > b) return 1;
      else return -1;
    }
  }
 
  qsort(feld,elementzahl,sizeof(unsigned int),&modvergleich);
}

Trampoline können auch auf anderen Speicherbereichen angelegt werden, die schreibbar und ausführbar sind. Dies muss nicht gleichzeitig der Fall sein; die Speicher-Attribute können ggf. zwischen Erzeugen und Ausführen umgeschaltet werden. Harvard-Architekturen, wie in Mikrocontrollern typisch, kommen für Trampoline nicht in Betracht.

Die dynamische Erzeugung von Maschinenkode erfordert prozessorspezifische Quelltext-Stückchen, wenn dies nicht im (ohnehin prozessorspezifischen) Compiler eingebaut ist.

Sicherheit[Bearbeiten]

Trampoline bergen an sich keine Sicherheitsprobleme. Bei der automatischen Erzeugung dieser durch den Compiler wie oben beschrieben ist es jedoch nötig, die Ausführung von Code auf dem Stack zu erlauben. Dies ist möglicherweise ein Sicherheitsrisiko, weil man dazu Mechanismen deaktivieren muss, die sonst die normalerweise unerwünschte Ausführung von Code aus dem Stack heraus verbieten.

Moderne APIs vermeiden den Zwang zu Trampolinen oder thread-lokalen Variablen, indem bei jedem Funktionszeiger auch ein Datenzeiger mitgegeben wird. Das „Herumschleppen“ solcher Datenzeiger macht jedoch solche APIs etwas unhandlich.

Einzelnachweise[Bearbeiten]

  1. Frage zum Thema »Implementation of nested functions« auf Stack Overflow. Abgerufen am 20. Mai 2012.