Structs und die Strict Aliasing Rule in C

Wer mit C programmiert, dirigiert Speicher – genauer gesagt Arbeitsspeicher. C wird gerne als portable Assemblersprache betrachtet, diese stellt den Speicher allerdings besonders in den Vordergrund. Der Kontakt mit Speicher tritt einerseits bei der dynamischen Speicherverwaltung mit malloc() und free() auf, erfolgt allerdings bereits mit der Verwendung von Datentypen. Ich umschreibe Datentypen gerne als „Schablone“ bzw. „Maske“ für Speicher. Der kleinste Datentyp ist der char, er umfasst 1 Byte. Hiernach folgt der short, der 2 Byte groß ist. Für besonders große Zahlen gibt es long mit 4 Byte. Spielt die Anzahl der Bytes keine Rolle, kann man den int nehmen, der mindestens 2 Byte groß sein soll, ich habe also keine Garantie, dass ein int immer wie unter Linux 4 Byte umfasst, wenn ich meinen Code auf eine andere Maschine zum Laufen bringen will. Im Zweifel muss ich ihn also portieren.

Obenstehende Abbildung zeigt, wie zwei Zahlen im Speicher liegen: im einfachsten Fall in Binärdarstellung, dicht an dicht. Haben wir zwei zusammenliegende Speicherstellen, die als char markiert sind, können wir in Versuchung kommen, diesen Speicher umzuinterpretieren. Was passiert, wenn wir diese 2 Bytes nicht als zwei chars, sondern als ein short betrachten? C gilt als schwach typisiert, weil wir genau das tun können. Und das geht so:

#include <stdio.h>
#include <stdlib.h>

int main(void)
{
    unsigned char *chrs = malloc(2);
    *chrs = 5;
    *(chrs + 1) = 44;

    unsigned short *shrt = chrs;
    printf("%d\n", *shrt);

    free(chrs);
    return 0;
}

Intern sieht es jetzt (fast) folgendermaßen aus:

Das ist der Grund, warum ich bei C an Programmierung mit Typenschablonen als Sicht auf den Speicher denke. Rechnen wir jetzt alles zusammen, müsste das Programm uns 1324 ausgeben – tut es aber nicht. Auf einem aktuellen 64-bit Linux-System wird stattdessen 11269 ausgegeben. Wir haben trotzdem fast alles richtig gedacht, nur müssen wir uns ins Gedächtnis rufen, dass x86-CPUs mit Little Endian arbeiten und wir deshalb die Bytes verdreht denken müssen. Dieser Fallstrick soll uns aber ein Gefühl dafür geben, wie oft bei C-Programmierung die lockere Standardisierung sowie die lokalen (i. S. v. Architektur) Gegebenheiten Herausforderungen bescheren.

Structs in C

Informationen kommen selten einzeln daher. Um sie sinnvoll im Code und im Speicher zu strukturieren, bietet C die structs, die eine Reihe von Mitgliedern (ähnlich wie Variablen) organisieren. Ein Beispiel:

struct country {
    char *name;
    char iso3166[3];
    unsigned short formation;
    char *capital;
};

Im Speicher können wir uns das so vorstellen, auch wenn wir ein entscheidendes Detail noch im Laufe des Beitrags kennenlernen werden:

Diese Vorstellung hilft zwar an der einen oder anderen Stelle, kann allerdings auch zu Missverständnissen führen, wenn wir uns zu sehr auf diese Speicherdarstellung verlassen.

Wir könnten zum Beispiel denken, dass wir vereinfacht die Werte verdrehen können:

#include <stdio.h>

struct country {
  char *name;
  char iso3166[3];
  unsigned short formation;
  char *capital;
};

struct country2 {
  char *capital;
  char iso3166[3];
  unsigned short formation;
  char *name;
};

int main (void)
{
  char *de_name = "Deutschland";
  char *de_capital = "Berlin";
  struct country germany = {
    de_name, "DE", 1949, de_capital
  };

  printf("Country Name: %s\n", germany.name);

  struct country2 *germany2 = (struct country2 *) &germany;

  printf("Country Name: %s\n", germany2->name);

  return 0;
}

Bei structs kommt es vor allem auf die Reihenfolge und die Datentypen an – allerdings kann man nicht darauf vertrauen.

Objektorientierung in C

Im voherigen Beispiel konnten wir eindrucksvoll sehen, dass wir besonders einfach Pointer auf structs umcasten – und somit uminterpretieren – können. Diese Technik ist als type punning bekannt, wurde schon vor knapp 40 Jahren bei den Berkley sockets (vgl. struct sockaddr_in) eingesetzt und lässt sich nun für viele verschiedene Zwecke einsetzen: zum Beispiel für Vererbung oder Bäume – oder die Kombination aus beidem.

Zur Veranschaulichung möchte ich einen Baum aus der Verwaltungsgliederung heranziehen: hier gibt es den Staat, die Bundesländer und die Landkreise, die jeweils unterschiedliche Informationen besitzen.

Ziel ist es, jeden Knoten am Baum aufzuhängen. Allerdings ist die Struktur komplex: so hilft es nicht, den Typen anhand der Ebene festzulegen, weil sonst Landkreise und kreisfreie Städte nicht unterschieden werden können. Die Lösung wäre, ein Unterscheidungsfeld am Anfang eines jeden Knotens festzulegen. Bei der Implementierung müssen wir bedenken, dass natürlich technsiche Informationen zur Baumimplementierung mitgegeben werden sollen:

struct country {
    char type;
    void *child;
    void *sibling;

    // data
    char *name;
    char *capital;
    //...
};


struct state {
    char type;
    void *child;
    void *sibling;

    // data
    char *name;
    //...
};


struct district {
    char type;
    void *child;
    void *sibling;

    // data
    char *name;
    //...
};

Strict Aliasing Rule

Doch halt! Wir dürfen bei C nicht vergessen, dass wir im Zweifel alles hinterfragen müssen. Unser Ziel ist es, dass die ersten drei Felder immer an der gleichen Stelle im Speicher liegen, sodass wir unabhängig von der Wahl der drei structs immer die gleichen Member an der gleichen Stelle erreichen können. Doch können wir uns darauf verlassen? Die Antwort ist im C-Standard zu finden und hier gibt der C99-Standard unter der Sektion „6.7.2.1 Structureand union specifiers“, Punkt 13 Aufschluss. Dieser Punkt beschreibt, dass bei structs die Reihenfolge der Members im Speicher unverändert sein und das erste Element auch am Anfang beginnen muss – er erlaubt aber auch Freiraum zwischen den Feldern, die der Compiler in Verbindung mit seinem Optimierungssystem selber bestimmen darf.

Für den Compiler hat dies Vorteile – für uns als Programmierer wird dies allerdings eine Herausforderung. Wir können uns also nur sicher sein, dass die Adresse des ersten Elements mit der Adresse des Structs selber übereinstimmt. Die Strict Aliasing Rule ist eine Folge aus diesem Umstand und sagt aus, dass wir nur dann standardkonform einen Pointer dereferenzieren können, wenn dessen Typ kompatibel zu dem Typ ist, der für die Speicherstelle festgelegt wurde.

Die Lösung

Wie können wir denn aber nun effizient unseren Baum umsetzen? Indem wir den Umstand ausnutzen und den gemeinsamen Anfang auslagern:

struct node_base {
    char type;
    void *child;
    void *sibling;
};

struct country {
    struct node_base base;

    // data
    char *name;
    char *capital;
    //...
};


struct state {
    struct node_base base;

    // data
    char *name;
    //...
};


struct district {
    struct node_base base;

    // data
    char *name;
    //...
};

Hierdurch erreichen wir, dass das (erste) Element garantiert an der gleichen Stelle (d. h. am Anfang) liegt und wir auf zusätzliche Indirektionen / Pointer oder Abstraktionen verzichten können.

Fazit

C ist weiterhin eine sehr effiziente und systemnahe Sprache, die einen unverblümten Blick auf das wichtigste Material eines Programmiers gibt, mit dem dieser seine Programme formt: den Speicher. Mit zunehmendem Optimierungswunsch gibt es jedoch seit knapp 20 Jahren eine Regel, die nur wenige kennen, aber große Auswirkungen besonders dem Portieren hat: die Strict Aliasing Rule. Es gibt noch weitere Anwendungsfälle für sie, ein wichtiger Anwendungsfall wurde in diesem Artikel besprochen. Dieser Fall tritt besonders dann auf, wenn Strukturen aus der Objektorientierten Programmierung (OOP) in C nachgebildet werden sollen.

Dass diese Regel eher unbekannt ist, lässt sich auch daran erkennen, dass die Referenzimplementierung von Python, CPython, noch bis zur Version 2.7 gegen diese Regel verstieß – was allerdings dank PEP 3123 mit CPython 3.0 gelöst wurde.

Strict Aliasing lässt sich übrigens in den meisten Compilern ausschalten, wer allerdings plattform- und compilerübergreifenden Code schreiben will, sollte die Regel allerdings beachten.

Weitere Informationen zu diesem Thema bietet dieses Gist sowie der StackOverflow-Thread zu diesem Thema.