Lauf, Forest, lauf!

Der Verfasser studiert Informatik an der Hochschule Karlsruhe. Der Artikel entstand im Rahmen einer Semesterarbeit und ist für diese Seite aufbereitet worden. Feedback an den Verfasser ist über den entsprechenden Link am Ende der Artikelseiten möglich.

Dieser Artikel ist noch zu Zeiten von Tiger entstanden und bezieht sich daher auf Objective-C 1. Die verlinkte Dokumentation ist daher als Legacy bezeichnet. In weiten Teilen dürfte sich indessen kein Unterschied zu Objective-C 2.0 ergeben.

In diesem Artikel, werde ich einige essentielle Datenstrukturen und Funktionen der Objective-C-Laufzeitumgebung von Darwin, die die hohe Dynamik von Objective-C ermöglicht, erläutern.

Die Laufzeitumgebung ist Open Source und kann über  die ▹ Darwin-Projektseite herunter geladen werden. Neben dem Quellcode der Laufzeitumgebung gibt es von Apple auch die ▹ Objective-C-Runtime-Reference, die einige Funktionen der Laufzeitumgebung näher erläutert.

Aus Sicht des Objective-C-Programmierers existiert zur dynamischen Typisierung der Typ id. Aus Sicht der Laufzeitumgebung ist id ein Zeiger auf die C-Datenstruktur objc_object. Diese Struktur ist in dem Header objc.h wie folgt deklariert:

objc.h

typedef struct objc_object {
    Class isa;
} *id;

Ist ein Objekt statisch typisiert, zeigt der Zeiger ebenfalls auf diese Struktur. Der Compiler kennt hier lediglich bereits die Klasse des Objekts und kann somit auf die Kompatibilität der Typen prüfen. Das Verhalten zur Laufzeit ist jedoch identisch.

objc_object repräsentiert also irgendein konkretes Objekt. Das isa-Element zeigt auf das so genannte Klassenobjekt, welches u.a. die Instanzmethoden, einer Klasse speichert. Alle Instanzen einer Klasse zeigen auf das gleiche Klassenobjekt. Der ein oder andere wird sich jetzt vermutlich fragen "Und wo ist dann der Speicher für die Instanzvariablen des Objekts?". Die Instanzvariablen eines Objektes befinden im Speicher nach dem isa-Element. Dazu später mehr.

Ein "Hidden Feature" der Objective-C-Laufzeitumgebung ist es eine beliebige Anzahl von zusätzlichen Bytes für eine Instanz zu alloziieren. Hierzu existiert die Funktion class_createInstance(), die als Parameter theClass die Klasse und als additionalByteCount die Anzahl zusätzlicher Bytes erhält.

Der Rückgabewert dieser Funktion ist eine Instanz der Klasse theClass für die eine ausreichende Menge Speicher reserviert wurde um den Zeiger auf das Klassenobjekt, die Instanzvariablen und den zusätzlichen Speicher unterzubringen. Die zusätzlichen Bytes können für einen beliebigen Zweck verwendet werden. Denkbar wäre z.B. das Geburtsdatum der Großmutter als ASCII Zeichenkette oder ein Array von Integerwerten um die Telefonnummern der Freundinnen sicher vor der eigenen Frau zu verstecken.

Soll der Speicher von einer bestimmten Speicherzone (memory zone) reserviert werden existiert die Methode class_createInstanceFromZone().

Der Typ Class

Jetzt aber ein genauerer Blick auf das isa-Element. Dieses ist vom Typ Class, und als Zeiger auf die Datenstruktur objc_class deklariert:

objc.h

typedef struct objc_class {
    struct objc_class *isa;
    struct objc_class *super_class;
    const char *name;
    long version;
    long info;
    long instance_size;
    struct objc_ivar_list *ivars;
    struct objc_method_list **methodLists;
    struct objc_cache *cache;
    struct objc_protocol_list *protocols;
} *Class;

isa 

Auffällig ist, dass diese Struktur genau wie die objc_object-Struktur als erstes Element das isa-Element besitzt. Dies hat zur Konsequenz, dass ein Klassenobjekt auch Nachrichten empfangen kann und in Situationen verwendet werden kann, wie jedes andere Objekt auch. Das isa-Element eines Klassenobjekt, zeigt auf das so genannten Metaklassenobjekt, welches die Klassenmethoden der Klasse enthält (bzw. darauf verweist). Nochmal: Ein Klassenobjekt speichert die Instanzmethoden einer Klasse. Ein Metaklassenobjekt speichert alle Klassenmethoden der Klasse.

Das isa-Element eines Metaklassenobjekts zeigt auf das Metaklassenobjekt der Wurzelklasse (in der Regel also das Metaklassenobjekt von NSObject). Das isa-Element des Metaklassenobjekts der Wurzelklasse zeigt auf sich selbst.

super_class

Das zweite Element super_class der Struktur zeigt ebenfalls auf eine objc_class-Struktur. Im Falle eines Klassenobjekts ist dies das Klassenobjekt der Elternklasse. Handelt es sich um ein Metaklassenobjekt zeigt dieses Element auf das Metaklassenobjekt der Elternklasse. Dieses Element wird bei der Suche nach einer Methode verwendet, falls die Empfängerklasse der Nachricht diese nicht selbst besitzt. Dazu später mehr.

Die Zusammenhang zwischen Klassen- und Metaklassenobjekten ist in der folgenden Abbildung nochmals illustriert.

name

Das dritte Element name speichert den Namen der Klasse als ASCII Zeichenkette. Klassennamen müssen in Objective-C eindeutig sein. Die Laufzeitumgebung überprüft dies beim Laden einer Klasse anhand dieses Elements. Die Funktionen objc_lookUpClass() oder auch objc_getClass() verwenden dieses Element ebenfalls: Sie nehmen einen Klassenname als Parameter entgegen, und liefern einen Zeiger auf das Klassenobjekt dieser Klasse zurück, falls diese bei der Laufzeitumgebung registriert ist.

version

Das Element version speichert die Version der Klasse als Integer. Die Funktion class_getVersion() liefert diesen Wert zurück. version ist zum Beispiel bei der Serialisierung von Objekten wichtig: Wird ein serialisiertes Objekt geladen (decodiert), muss eine abweichende Version festgestellt werden können, falls sich z.B. die Anordnung von Instanzvariablen in einer neueren Version der Klasse geändert hat. -versionForClassName: (NSCoder) aus dem Foundation Framework verwendet hierzu die eben erwähnte Funktion der Laufzeitumgebung. Wie auch die Methode +version (NSObject).

info

Das Element info speichert eine Reihe von Flags, die die Laufzeitumgebung auswertet. Eine ▹ vollständige Liste befindet sich in der Objective-C Runtime Reference von Apple. Erwähnt seien hier vielleicht die Flags CLS_CLASS und CLS_META, welche der Laufzeitumgebung ermöglichen zu unterscheiden ob es sich bei einer objc_class-Struktur um ein Klassen- oder ein Metaklassenobjekt handelt. Das Flag CLS_METHOD_ARRAY sagt der Laufzeitumgebung, dass das Element methodLists auf ein Array von objc_method_list-Strukturen zeigt. Ist dieses Flag nicht gesetzt zeigt das Element auf eine einzige objc_method_list-Struktur. Zur Struktur objc_method_list werde ich später was schreiben.

ivars

Das Element ivars zeigt auf die Struktur objc_ivar_list, die wie folgt deklariert ist:

objc.h

struct objc_ivar_list {
    int ivar_count;
    struct objc_ivar ivar_list[1]; // Größe des Arrays variabel
};

In Abhängigkeit der Anzahl der Instanzvariabeln der Klasse speichert diese Struktur ein dynamisch alloziiertes Array von objc_ivar Strukturen. Besitzt die Klasse keine Instanzvariablen ist der Zeiger ivars NULL. Die Struktur objc_ivar ist wie folgt deklariert:

objc.h

typedef struct objc_ivar {
    char *ivar_name;
    char *ivar_type; 
    int ivar_offset;
} *Ivar;

Sie speichert also den Namen sowie den Typ einer Instanzvariable. Mittels der Compilerdirektive @encode() kann eine Zeichenkette erzeugt werden, die einen bestimmten Variablentyp entspricht. Außerdem wird zu jeder Instanzvariable ihr Offset innerhalb des Speichers, der das Objekt repräsentiert, gespeichert.

Die Laufzeitumgebung stellt folgende zwei Funktionen zur Verfügung, die es erlauben den Wert einer Instanzvariable eines Objekts zu ändern bzw. auszulesen: object_setInstanceVariable() und object_getInstanceVariable().

Die Funktion class_getInstanceVariable() ermöglicht Informationen über eine Instanzvariable einer Klasse zu erhalten. Hierzu liefert die Funktion den entsprechenden Zeiger auf die objc_ivar Struktur zurück.

methodLists

Das Element methodLists verweist auf die Instanz- bzw. Klassenmethoden (in Abhängigkeit des info-Elements) einer Klasse. Ebenfalls das info-Element entscheidet darüber, ob es sich hierbei um ein Array von objc_method_list Strukturen handelt, oder um eine einzige. Die Struktur ist wie folgt deklariert:

objc.h

struct objc_method_list {
    struct objc_method_list *obsolete; // reserviert für zukünftige Verwendung
    int method_count; 
    struct objc_method method_list[1]; // variable Größe
};

Wieder steckt hinter der Struktur ein dynamisch alloziertes Array, dessen Größe von der Anzahl Methoden abhängig ist. Die Struktur objc_method hält die nötigen Informationen zu einer Methode:

objc.h

typedef struct objc_method { 
    SEL method_name; 
    char *method_types; 
    IMP method_imp; 
} *Method;

Das erste Element dieser Struktur ist ein Selektor. Zur Erinnerung: In Objective-C werden Methoden über ihre Namen unterschieden. Hierzu wird jedem Namen beim Kompilieren ein eindeutiger Wert zugewiesen. Wichtig: Selektoren identifizieren Methodennamen und nicht Methodenimplementierungen. Darum haben zwei Methoden verschiedener Klassen, die den gleichen Namen besitzen den gleichen Selektor! Das ist wichtig für den Polymorphismus und die dynamische Bindung - nur so können nämlich gleiche Nachrichten an unterschiedliche Empfänger, die zu unterschiedlichen Klassen gehören, gesendet werden. Würde jede Methode ihren eigenen Selektor haben, wäre ein Methodenaufruf nichts anderes als ein Old-School-Funktionsaufruf.

Okay, und was ist jetzt der Typ SEL genau? In manchen Objective-C- bzw. Cocoa-Büchern wird der SEL Typ gerne als "eindeutiger Integerwert" bezeichnet. Das ist Quatsch – im Prinzip aber eine völlig ausreichende Information zum Erstellen von korrekten Objective-C-Programmen. Wir wollen uns das aber genauer anschauen:

Wir schreiben das Jahr 1789 n.Chr. - in Frankreich beginnt die französische Revolution. Wir sind aber in Amerika und heißen Brad Cox. Darum müssen wir jetzt Objective-C erfinden: Selektoren müssen also eindeutig sein? Wäre es da nicht fantastisch wenn man den bereits existierenden C Linker verwenden könnten um dies zu garantieren? Stimmt. Hey, wir verwenden einfach globale Variablen als Selektoren. Nicht schlecht, aber globale Variablen sind nicht so cool um als Index in unserem Methodencache (kommt später) zu verwenden. Ja stimmt, daran habe ich gar nicht gedacht. Wie wäre es dann mit Zeigern auf globale Variablen? Das ist es!

Darum ist der SEL-Typ in objc.h folgendermaßen deklariert:

objc.h

typedef struct objc_selector *SEL;

Der SEL-Typ ist also ein Zeiger. Worauf er genau zeigt, spielt erstmal keine Rolle. Trifft der Compiler auf die @selector()-Direktive, erzeugt er Objektcode für einen Zeiger auf eine entsprechende globale Variable. Jeder Selektor hat also seine globale Variable. Wird ein Objecitve-C-Programm gebunden, löst der Linker alle Referenzen zu den globalen Variablen auf.

Was wirklich hinter der Struktur objc_selector steckt, ist Implementationsdetail. In der Laufzeitumgebung findet man jedoch folgende Funktion:

objc-sel.m

const char *sel_getName(SEL sel) {
    return sel ? (const char *)sel : "<null selector>";
}

Die Methode liefert den Namen einer Methode für den übergebenen Selektor zurück. Aha, und was macht sie? Sie castet den Selektor nach const char*. Hinter dem Selektor steckt also letztlich der Methodenname. Dennoch sollte man niemals auf die blöde Idee kommen Selektoren selbst zu casten um den Methodennamen zu erhalten! Immer schön die Methode sel_getName als Blackbox verwenden. So jetzt aber zurück zur objc_method Struktur:

Das zweite Element method_types der Struktur objc_method spezifiziert wieder mit Hilfe der @encode()-Compilerdirektive die Parametertypen dieser Methode als ASCII Zeichenkette. Das letzte Element (method_imp) ist vom Typ IMP, welcher einem C-Funktionszeiger auf die Implementierung der Methode entspricht. Diesen Typ werde ich später detailierter erläutern.

Sehr viel Funktionen der Laufzeitumgebung verwenden das methodLists-Element und ermöglichen eine große Dynamik. Sie ermöglichen, dass Methoden zu einer Klasse hinzugefügt oder entfernt werden können. Oder auch Informationen über existierende Methoden erfragt werden können. Die wichtigsten Funktionen sind selbsterläuternd:

• class_addMethods()

• class_removeMethods()

• method_getNumberOfArguments()

• method_getSizeOfArguments()

• method_getArgumentInfo()

• class_nextMethodList()

cache

Wie den meisten sicherlich bekannt ist, besitzt jede Klasse (also das Klassenobjekt) einen Cache, der die zuletzt aufgerufenen Methoden speichert. Bevor die Laufzeitumgebung bei einem Methodenaufruf  methodLists linear durchsucht, schaut sie zuerst im Cache nach. In diesem Cache werden auch Methoden vorgehalten, die zu einem Klassenobjekt einer Elternklasse gehören. Gerade hier gibt es ja Optimierungsbedarf, da ja sonst beispielsweise bei jedem Aufruf einer Methode der Wurzelklasse, die Laufzeitumgebung  die komplette Vererbungshierarchie durchgehen müsste und in jedem Klassenobjekt nach der Methode suchen müsste, bis sie diese endlich in der Wurzelklasse finden würde. Mit dem Cache ist dies nur beim ersten Aufruf dieser Methode der Fall. Beim zweiten Aufruf findet sie diese Methode sofort im Cache. Der Cache ist mit folgender Hashtabellen Datenstruktur implementiert:

objc-class.h

typedef struct objc_cache {
    unsigned int mask;
    unsigned int occupied;
    Method buckets[1]; // Maximal mask + 1 Einträge
} *Cache;

Fangen wir am besten mit dem dritten Element an. In dem Array buckets werden Zeiger auf objc_method-Strukturen gespeichert (also die Methoden – siehe Erläuterung oben). Dieses Array besitzt maximal mask + 1 Einträge. Wenn Zeiger im Array NULL sind, bedeutet dies, das dieser Cache bucket (Eintrag) frei ist. Das Array wird in der Regel mit der Zeit größer.

Das zweite Element occupied dieser Struktur speichert die Gesamtzahl belegter Einträge in buckets.

mask gibt der Gesamtanzahl möglicher Einträge (minus eins) an. Außerdem wird es von der Laufzeitumgebung verwendet zum Entscheiden bei welchem Index des buckets-Array die lineare Suche begonnen werden soll. Hierzu dient die einfache Hashing-Funktion index = mask & selector. Der Selektor der Methode, die gesucht wird, wird mit mask bitweise und-verknüpft.

protocols

Eine Objective-C Klasse kann bestimmte Protokolle implementieren. Alle Protokolle die eine Klasse implementiert sind in der Datenstruktur objc_protocol_list gespeichert:

@class Protocol;
struct objc_protocol_list {
    struct objc_protocol_list *next;
    int count;         // Anzahl Protokolle in list
    Protocol *list[1]; // variable Größe
}; 

Wie man sieht ist die Struktur als verkettete Liste implementiert. Angeblich ist es dies ein Überbleibsel der ersten Implementierung der distributed Objects. Egal – für jedes implementierte Protokoll einer Klasse wird in list ein Zeiger auf eine Protocol-Instanz gespeichert. Für jedes Protokoll das man erstellt, erzeugt die Compilerdirektive @protocol eine Instanz der Klasse Protocol. Diese Instanz speichert u.a. den Namen des Protokolls und Informationen zu den Instanz- und Klassenmethoden des Protokolls. Wohlgemerkt, dies sind die Methoden, die eine Klasse, die dieses Protokoll implementiert, besitzen muss. Protokolle können, andere Protokolle erweitern. Darum wird in der zugehörigen Protocol-Instanz eines Protokolls auch eine Liste der erweiterten Protokolle gespeichert (wieder als Zeiger auf eine objc_protocol_list Struktur).

Kategorien

Die Methoden und implementierten Protokolle der Kategorien einer Klasse werden zusammen mit den anderen Methoden und Protokollen der Klasse in dem jeweiligen Element der objc_class Struktur gespeichert. Um Kategorien in ein laufendes Programm zu laden, existiert folgende Datenstruktur:

typedef struct objc_category { 
    char *category_name;  // Name der Kategorie
    char *class_name;     // Name der Klasse, die erweitert wird
    struct objc_method_list *instance_methods; 
    struct objc_method_list *class_methods; 
    struct objc_protocol_list *protocols; 
};

Diese Struktur speichert  die zusätzlichen Instanz- und Klassenmethoden, sowie die implementierten Protokollen. Diese werden von der Laufzeitumgebung in das bestehende Klassen- bzw. Metaklassenobjekt kopiert. Danach wird diese Struktur nicht mehr länger benötigt.