Need for Speed

Schnittstelle zur Sprache C: Structs

In der Sprache C ist ein struct ein zusammengesetzter Typ, der aus verschiedenen Feldern besteht. Jedes Feld hat seinen eigenen Typ und seine eigene Größe.

Zum Beispiel definiert dies einen Typ, der aus drei Ganzzahlen besteht, zwei mit 4 Bytes und eine mit 8 Bytes:

struct example {
    int32_t first_four_byte_integer;
    uint32_t second_four_byte_integer;
    uint64_t eight_byte_integer;
};

Ein struct kann auch andere structs enthalten:

struct example_2 {
    struct example first;
    struct example second;
};

Wenn eines der Felder des structs ein Array ist, gehören alle für das Array reservierten Bytes zum struct. Ist das Feld jedoch nur ein Zeiger auf das Array, muss das Array woanders gespeichert werden:

struct with_array {
    char string[20];
};
// all 20 bytes of string are inside struct with_array

struct with_pointer {
    const char *string;
};
// only the 8-byte pointer to the string is inside struct with_pointer

Ausrichtung

Die Ausrichtung eines Typs ist eine nicht negative Zweierpotenz (1, 2, 4, 8, ...), die eine Anforderung an seine Adresse darstellt. Jedes Objekt dieses Typs muss an einer Adresse liegen, die ein Vielfaches seiner Ausrichtung ist.

Bei einem primitiven Typ ist die Ausrichtung normalerweise gleich seiner Größe; so hat ein int32_t zum Beispiel üblicherweise eine 4-Byte-Ausrichtung. Das bedeutet, dass int32_t an 4-Byte-Grenzen liegen muss.

Die Ausrichtung eines structs ist jedoch die maximale Ausrichtung seiner Felder. So hätte das oben definierte struct example zum Beispiel eine Ausrichtung von 8 Bytes, denn das ist die Ausrichtung von uint64_t.

Ist die Ausrichtung eines Feldes kleiner als die des structs, können nach diesem Feld Padding-Bytes eingefügt werden. So wird sichergestellt, dass die nachfolgenden Felder und das struct als Ganzes die Ausrichtungsanforderungen erfüllen. In der Praxis heißt das: Obwohl diese Padding-Bytes zur Größe des structs beitragen, sind sie nicht Teil des Werts des structs:

struct example_3 {
    char one_byte; // alignment of 1
    int four_byte; // alignment of 4
};
// example_3 has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one_byte'
// 3 padding bytes (with undefined value)
// 4 bytes for field 'four_byte'

Beachte, dass im oben definierten struct das Feld 'one_byte' eine Ausrichtung von 1 hat und an jeder Adresse liegen kann. Da das Feld 'four_byte' eine Ausrichtung von 4 hat, müssen die Felder im struct ebenfalls 4-Byte-Grenzen einhalten. Das bedeutet, dass zwischen zwei beliebigen Feldern im struct eine Anzahl von Bytes liegen muss, die ein Vielfaches von 4 ist. Da 'one_byte' nur 1 Byte belegt, werden danach 3 Padding-Bytes eingefügt, um diese Grenze einzuhalten.

Benachbarte Felder werden nach Möglichkeit gruppiert, um die Anzahl der nötigen Padding-Bytes zu minimieren:

struct two_padding {
    char one; // alignment of 1
    char two; // alignment of 1
    int three; // alignment of 4
};
// struct two_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 byte for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'

Diese Gruppierung muss auch die Ausrichtung jedes Feldes berücksichtigen:

struct one_padding {
    char one; // alignment of 1
    int16_t two; // alignment of 2
    int three; // alignment of 4
};
// struct one_padding has alignment of 4 (the same as int)
// it occupies 8 bytes in space:
// 1 byte for field 'one'
// 1 padding byte
// 2 bytes for field 'two'
// 4 bytes for field 'three'
// Since 'two' has alignment of 2, it must be placed in a 2-byte boundary
// So, there must be 1 padding byte between 'one' and 'two'

Das bedeutet, dass eine Änderung der Reihenfolge der Felder in einem struct manchmal zu einer anderen Größe führen kann:

struct example_4 {
    int64_t one;
    short two;
    int32_t three;
};
// example_4 has alignment of 8 (the same as int64_t)
// it occupies 16 bytes in space:
// 8 bytes for field 'one'
// 2 bytes for field 'two'
// 2 padding bytes
// 4 bytes for field 'three'
// two' and 'three' are adjacent and can be grouped to sum up 8 bytes with only 2 bytes of padding

struct example_5 {
    int16_t one;
    int64_t two;
    unsigned int three;
};
// example_5 also has alignment of 8 (the same as int64_t)
// however, it occupies 24 bytes in space:
// 2 bytes for field 'one'
// 6 bytes for padding
// 8 bytes for field 'two'
// 4 bytes for field 'three'
// 4 padding bytes
// 'one' can't be grouped with 'two' because their sum would be higher than the struct's alignment
// 'two' and 'three' also can't be grouped, for the same reason
// so padding bytes must be inserted in full after each field with less than 8 bytes in alignment

Beachte, dass die Ausrichtung eines Arrays dieselbe ist wie die Ausrichtung seines zugrunde liegenden Typs:

struct array_example {
    char string[10]; // alignment of 1
};
// array_example has alignment of 1 (it can be placed at any address)
// it occupies 10 bytes in space, one for each char in 'string'

Elemente eines Arrays können genauso gruppiert werden, als wären sie nicht Teil eines Arrays:

struct group_array {
    int16_t arr[3];
    int8_t one_byte;
    int32_t four_byte;
};
// group_array has alignment of 4 because this is the alignment of 'four_byte'
// it occupies 12 bytes in space:
// 4 bytes for arr[0] and arr[1]
// 2 bytes for arr[2]
// 1 byte for 'one_byte'
// 1 padding byte (arr[2] is grouped with 'one_byte')
// 4 bytes for 'four_byte'

Es ist wichtig, alle möglichen Padding-Bytes zu berücksichtigen, wenn du in Assembler auf ein struct zugreifst.

Aufrufkonvention

Im Allgemeinen werden Werte so an Funktionen übergeben und von ihnen zurückgegeben, wie man es erwarten würde:

• Ganzzahlige Werte, einschließlich Speicheradressen und Enums, werden in Allzweckregistern (General-Purpose Registers, GPR) übergeben.
• Gleitkommawerte werden in xmm-Registern übergeben.

Structs sind jedoch ein Sonderfall. Als Faustregel gilt: Alle Felder in einem struct belegen benachbarten Speicherplatz und sollten nach Möglichkeit in ein einzelnes Register gelegt werden:

struct single_type {
    int16_t first;
    int16_t second;
    int16_t third;
    int16_t fourth;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'first' is passed on the lowest 2 bytes
// each subsequent field is passed in the following 2 bytes

Wenn ein struct sowohl Felder mit ganzzahligen Werten als auch Felder mit Gleitkommawerten hat, sollte jeder aufeinanderfolgende 8-Byte-Block im struct separat klassifiziert werden:

struct mixed_types {
    double first;
    int second;
    int third;
};
// this struct occupies 16 bytes
// the field 'first' is passed in the first 8 bytes of a xmm register
// the fields 'second' and 'third' are passed in the same GPR register:
// the field 'second' is passed on the lowest 4 bytes
// the field 'third' is passed in the next 4 bytes

Wenn Ganzzahlen und Gleitkommawerte im selben 8-Byte-Block liegen, ist der Typ ganzzahlig, und der gesamte 8-Byte-Block (einschließlich des Gleitkommawerts) wird in ein GPR gelegt:

struct mixed_types {
    int32_t integer;
    float floating_point;
};
// this struct occupies 8 bytes
// it is entirely passed in the same GPR register:
// the field 'integer' is passed on the lowest 4 bytes
// the field 'floating_point' is passed on the next 4 bytes

Structs mit mehr als 16 Bytes Größe werden jedoch üblicherweise im Speicher abgelegt, unabhängig vom Typ jedes 8-Byte-Blocks:

struct big_struct {
    uint8_t first;
    double second;
    int64_t third;
};
// this struct occupies 24 bytes, including 7 padding bytes between 'first' and 'second'
// it is entirely passed in memory

Wenn ein struct als Argument an eine Funktion übergeben wird, verwendet es so viele Register wie nötig. Wird es im Speicher abgelegt, wird stattdessen der Stack verwendet.

Ähnliche Regeln gelten für structs, die von einer Funktion zurückgegeben werden. Sie werden üblicherweise zuerst in rax und rdx (bei ganzzahligem Wert) oder in xmm0 und xmm1 (bei Gleitkommawert) zurückgegeben. Wird das struct jedoch im Speicher abgelegt, muss der Aufrufer Speicher dafür reservieren und die Adresse dieser Speicherstelle als implizites erstes Argument (in rdi) an die Funktion übergeben. Die Funktion legt das struct dann in diesem Speicher ab und gibt seine Adresse in rax zurück.