Ist der "Struktur-Hack" technisch undefiniertes Verhalten?

111

Was ich frage, ist der bekannte Trick "Das letzte Mitglied einer Struktur hat eine variable Länge". Es geht ungefähr so:

struct T {
    int len;
    char s[1];
};

struct T *p = malloc(sizeof(struct T) + 100);
p->len = 100;
strcpy(p->s, "hello world");

Aufgrund der Art und Weise, wie die Struktur im Speicher angeordnet ist, können wir die Struktur über einen größeren als den erforderlichen Block legen und das letzte Element so behandeln, als wäre es größer als der 1 charangegebene.

Die Frage ist also: Ist diese Technik technisch undefiniertes Verhalten? . Ich würde das erwarten, war aber neugierig, was der Standard dazu sagt.

PS: Ich bin mir des C99-Ansatzes bewusst. Ich möchte, dass sich die Antworten speziell an die oben aufgeführte Version des Tricks halten.

Evan Teran
quelle
33
Dies scheint eine ganz klare, vernünftige und vor allem beantwortbare Frage zu sein. Den Grund für die enge Abstimmung nicht sehen.
CHao
2
Wenn Sie einen "ansi c" -Compiler einführen würden, der den struct-Hack nicht unterstützt, würden die meisten mir bekannten c-Programmierer nicht akzeptieren, dass Ihr Compiler "richtig funktioniert". Ungeachtet dessen, dass sie eine strikte Lesart des Standards akzeptieren würden. Das Komitee hat einfach einen verpasst.
dmckee --- Ex-Moderator Kätzchen
4
@james Der Hack funktioniert durch Mallocieren eines Objekts, das groß genug für das Array ist, das Sie meinen, obwohl Sie ein minimales Array deklariert haben. Sie greifen also außerhalb der strengen Definition der Struktur auf den zugewiesenen Speicher zu. Das Schreiben über Ihre Zuordnung hinaus ist unbestreitbar ein Fehler, aber das unterscheidet sich vom Schreiben in Ihrer Zuordnung, jedoch außerhalb der "Struktur".
dmckee --- Ex-Moderator Kätzchen
2
@ James: Das übergroße Malloc ist hier entscheidend. Es stellt sicher, dass nach dem nominalen Ende der Struktur Speicher vorhanden ist - Speicher mit legaler Adresse und "im Besitz" der Struktur (dh es ist für jede andere Entität illegal, ihn zu verwenden). Beachten Sie, dass dies bedeutet, dass Sie den Struktur-Hack nicht für automatische Variablen verwenden können: Sie müssen dynamisch zugewiesen werden.
dmckee --- Ex-Moderator Kätzchen
5
@detly: Es ist einfacher, eine Sache zuzuweisen / aufzuheben, als zwei Dinge zuzuweisen / aufzuheben, zumal letztere zwei Arten von Fehlern aufweist, mit denen Sie sich befassen müssen. Dies ist mir wichtiger als die Grenzkosten- / Geschwindigkeitseinsparungen.
Jamesdlin

Antworten:

52

Wie die C FAQ sagt:

Es ist nicht klar, ob es legal oder portabel ist, aber es ist ziemlich beliebt.

und:

... eine offizielle Interpretation hat festgestellt, dass es nicht streng mit dem C-Standard übereinstimmt, obwohl es unter allen bekannten Implementierungen zu funktionieren scheint. (Compiler, die die Array-Grenzen sorgfältig prüfen, geben möglicherweise Warnungen aus.)

Die Begründung für das "streng konforme" Bit befindet sich in der Spezifikation, Abschnitt J.2 Undefiniertes Verhalten , die in der Liste des undefinierten Verhaltens Folgendes enthält:

  • Ein Array-Index liegt außerhalb des Bereichs, selbst wenn ein Objekt anscheinend mit dem angegebenen Index zugänglich ist (wie im lvalue-Ausdruck a[1][7]in der Deklaration int a[4][5]) (6.5.6).

In Abschnitt 8 von Abschnitt 6.5.6 Additive Operatoren wird erneut erwähnt, dass der Zugriff über definierte Array-Grenzen hinaus nicht definiert ist:

Wenn sowohl der Zeigeroperand als auch das Ergebnis auf Elemente desselben Arrayobjekts oder eines nach dem letzten Element des Arrayobjekts zeigen, darf die Auswertung keinen Überlauf erzeugen. Andernfalls ist das Verhalten undefiniert.

Carl Norum
quelle
1
Wird im OP-Code p->sniemals als Array verwendet. Es wird an übergeben strcpy, in diesem Fall zerfällt es in eine Ebene char *, die zufällig auf ein Objekt verweist, das legal als char [100];innerhalb des zugewiesenen Objekts interpretiert werden kann .
R .. GitHub STOP HELPING ICE
3
Möglicherweise besteht eine andere Sichtweise darin, dass die Sprache möglicherweise den Zugriff auf tatsächliche Array-Variablen einschränkt, wie in J.2 beschrieben. Es gibt jedoch keine Möglichkeit, solche Einschränkungen für ein von zugewiesenes Objekt vorzunehmen malloc, wenn Sie lediglich die zurückgegebenen konvertiert haben void *auf einen Zeiger auf [eine Struktur, die] ein Array enthält. Es ist weiterhin gültig, mit einem Zeiger auf char(oder vorzugsweise unsigned char) auf einen Teil des zugewiesenen Objekts zuzugreifen .
R .. GitHub STOP HELPING ICE
@R. - Ich kann sehen, dass J2 dies möglicherweise nicht abdeckt, aber wird es nicht auch von 6.5.6 abgedeckt?
Detly
1
Sicher könnte es! Typ- und Größeninformationen könnten in jeden Zeiger eingebettet werden, und jede fehlerhafte Zeigerarithmetik könnte dann zum Abfangen gebracht werden - siehe z . B. CCured . Auf einer philosophischeren Ebene spielt es keine Rolle, ob keine mögliche Implementierung Sie fangen könnte, es ist immer noch undefiniertes Verhalten (es gibt Fälle von undefiniertem Verhalten, die ein Orakel erfordern würden, damit das Halting-Problem festnagelt - und genau deshalb sie sind undefiniert).
zwol
4
Das Objekt ist kein Array-Objekt, daher ist 6.5.6 irrelevant. Das Objekt ist der von zugewiesene Speicherblock von malloc. Suchen Sie im Standard nach "Objekt", bevor Sie bs ausspucken.
R .. GitHub STOP HELPING ICE
34

Ich glaube, dass es technisch gesehen undefiniertes Verhalten ist. Der Standard spricht ihn (wohl) nicht direkt an, so dass er unter das "oder durch das Weglassen einer expliziten Definition des Verhaltens" fällt. Klausel (§4 / 2 von C99, §3.16 / 2 von C89), die besagt, dass es sich um undefiniertes Verhalten handelt.

Das obige "wohl" hängt von der Definition des Array-Subskriptionsoperators ab. Insbesondere heißt es: "Ein Postfix-Ausdruck, gefolgt von einem Ausdruck in eckigen Klammern [], ist eine tiefgestellte Bezeichnung eines Array-Objekts." (C89, §6.3.2.1 / 2).

Sie können argumentieren, dass das "eines Array-Objekts" hier verletzt wird (da Sie außerhalb des definierten Bereichs des Array-Objekts abonnieren). In diesem Fall ist das Verhalten (ein kleines bisschen mehr) explizit undefiniert und nicht nur undefiniert mit freundlicher Genehmigung von nichts, was es ganz definiert.

Theoretisch kann ich mir einen Compiler vorstellen, der Array-Grenzen überprüft und (zum Beispiel) das Programm abbricht, wenn Sie versuchen, einen Index außerhalb des Bereichs zu verwenden. Tatsächlich weiß ich nicht, dass so etwas existiert, und angesichts der Popularität dieses Codestils ist es schwer vorstellbar, dass sich irgendjemand damit abfinden würde, selbst wenn ein Compiler unter bestimmten Umständen versucht hätte, Indizes durchzusetzen diese Situation.

Jerry Sarg
quelle
2
Ich kann mir auch einen Compiler vorstellen, der entscheiden könnte, ob ein Array der Größe 1 arr[x] = y;wie folgt umgeschrieben wird arr[0] = y;. Für ein Array der Größe 2 wird arr[i] = 4;möglicherweise Folgendes umgeschrieben: i ? arr[1] = 4 : arr[0] = 4; Während ich noch nie einen Compiler gesehen habe, der solche Optimierungen durchführt, können sie auf einigen eingebetteten Systemen sehr produktiv sein. Auf einem PIC18x, der 8-Bit-Datentypen verwendet, wäre der Code für die erste Anweisung sechzehn Bytes, die zweite, zwei oder vier und die dritte, acht oder zwölf. Keine schlechte Optimierung, wenn legal.
Supercat
Wenn der Standard den Array-Zugriff außerhalb der Array-Grenzen als undefiniertes Verhalten definiert, ist dies auch der Struktur-Hack. Wenn der Standard jedoch den Array-Zugriff als syntaktischen Zucker für die Zeigerarithmetik ( a[2] == a + 2) definiert, ist dies nicht der Fall. Wenn ich richtig bin, definieren alle C-Standards den Array-Zugriff als Zeigerarithmatik.
yyny
13

Ja, es ist undefiniertes Verhalten.

Der C-Sprachfehlerbericht Nr. 051 gibt eine endgültige Antwort auf diese Frage:

Die Redewendung ist zwar üblich, aber nicht streng konform

http://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_051.html

Im C99-Begründungsdokument fügt der C-Ausschuss Folgendes hinzu:

Die Gültigkeit dieses Konstrukts war immer fraglich. In der Antwort auf einen Fehlerbericht entschied der Ausschuss, dass es sich um ein undefiniertes Verhalten handelt, da das Array p-> Elemente nur ein Element enthält, unabhängig davon, ob der Speicherplatz vorhanden ist.

ouah
quelle
2
+1 für das Finden, aber ich behaupte immer noch, dass es widersprüchlich ist. Zwei Zeiger auf dasselbe Objekt (in diesem Fall das angegebene Byte) sind gleich, und ein Zeiger darauf (der Zeiger auf das Darstellungsarray des gesamten Objekts, das von erhalten wurde malloc) ist in der Addition gültig. Wie kann also der identische Zeiger? über eine andere Route erhalten, in der Hinzufügung ungültig sein? Selbst wenn sie behaupten wollen, es sei UB, ist das ziemlich bedeutungslos, da eine Implementierung rechnerisch nicht zwischen der genau definierten und der angeblich undefinierten Verwendung unterscheiden kann.
R .. GitHub STOP HELPING ICE
Es ist schade, dass C-Compiler damit begonnen haben, die Deklaration von Arrays mit der Länge Null zu verbieten. Ohne dieses Verbot hätten viele Compiler keine spezielle Behandlung durchführen müssen, damit sie so funktionieren, wie sie "sollten", wären aber dennoch in der Lage gewesen, Sonderfallcode für Einzelelement-Arrays zu erstellen (z. B. wenn a *fooenthalten ist) Einzelelement-Array boz, der Ausdruck foo->boz[biz()*391]=9;könnte vereinfacht werden als biz(),foo->boz[0]=9;). Leider bedeutet die Ablehnung von Nullelement-Arrays durch Compiler, dass viel Code stattdessen Einzelelement-Arrays verwendet und durch diese Optimierung beschädigt würde.
Supercat
11

Diese spezielle Vorgehensweise ist in keinem C-Standard explizit definiert, aber C99 enthält den "Struktur-Hack" als Teil der Sprache. In C99 kann das letzte Mitglied einer Struktur ein "flexibles Array-Mitglied" sein, das als char foo[](mit dem gewünschten Typ anstelle von char) deklariert ist .

Futter
quelle
Pedantisch zu sein, das ist nicht der Struktur-Hack. Der Struktur-Hack verwendet ein Array mit einer festen Größe, kein flexibles Array-Mitglied. Der Struktur-Hack ist das, wonach gefragt wurde und ist UB. Flexible Array-Mitglieder scheinen nur ein Versuch zu sein, die Art von Leuten zu beschwichtigen, die in diesem Thread gesehen werden und sich über diese Tatsache beschweren.
underscore_d
7

Es ist kein undefiniertes Verhalten , unabhängig davon, was jemand, offiziell oder anderweitig , sagt, da es durch den Standard definiert ist. p->s, außer wenn es als l-Wert verwendet wird, wird zu einem Zeiger ausgewertet, der mit identisch ist (char *)p + offsetof(struct T, s). Dies ist insbesondere ein gültiger charZeiger innerhalb des malloc'd-Objekts, und unmittelbar darauf folgen 100 (oder mehr, abhängig von Ausrichtungsüberlegungen) aufeinanderfolgende Adressen, die auch als charObjekte innerhalb des zugewiesenen Objekts gültig sind . Die Tatsache, dass der Zeiger durch Verwenden ->von abgeleitet wurde, anstatt den Versatz explizit zu dem Zeiger hinzuzufügen, der von malloc, in den umgewandelt wurde char *, zurückgegeben wird, ist irrelevant.

Technisch gesehen p->s[0]ist das einzelne Element des charArrays innerhalb der Struktur, die nächsten paar Elemente (z. B. p->s[1]bis p->s[3]) sind wahrscheinlich Auffüllbytes innerhalb der Struktur, die beschädigt werden können, wenn Sie die Zuordnung zur Struktur als Ganzes durchführen, aber nicht, wenn Sie nur auf einzelne zugreifen Mitglieder und der Rest der Elemente sind zusätzlicher Speicherplatz im zugewiesenen Objekt, den Sie nach Belieben verwenden können, solange Sie die Ausrichtungsanforderungen erfüllen (und charkeine Ausrichtungsanforderungen haben).

Wenn Sie befürchten, dass die Möglichkeit einer Überlappung mit Auffüllbytes in der Struktur Nasen-Dämonen hervorrufen könnte, können Sie dies vermeiden, indem Sie das 1In [1]durch einen Wert ersetzen, der sicherstellt, dass am Ende der Struktur kein Auffüllen erfolgt. Eine einfache, aber verschwenderische Möglichkeit, dies zu tun, besteht darin, eine Struktur mit identischen Elementen außer keinem Array am Ende zu erstellen und s[sizeof struct that_other_struct];für das Array zu verwenden. Dann p->s[i]ist klar definiert als ein Element des Arrays in der Struktur für i<sizeof struct that_other_structund als ein char-Objekt an einer Adresse nach dem Ende der Struktur für i>=sizeof struct that_other_struct.

Bearbeiten: Bei dem obigen Trick, um die richtige Größe zu erhalten, müssen Sie möglicherweise auch eine Vereinigung mit jedem einfachen Typ vor das Array setzen, um sicherzustellen, dass das Array selbst mit maximaler Ausrichtung beginnt und nicht in der Mitte des Auffüllens eines anderen Elements . Auch hier glaube ich nicht, dass dies notwendig ist, aber ich biete es den paranoidesten Sprachanwälten da draußen an.

Bearbeiten 2: Die Überlappung mit Füllbytes ist aufgrund eines anderen Teils des Standards definitiv kein Problem. C erfordert, dass, wenn zwei Strukturen in einer anfänglichen Teilsequenz ihrer Elemente übereinstimmen, auf die gemeinsamen Anfangselemente über einen Zeiger auf einen der beiden Typen zugegriffen werden kann. Wenn daher eine Struktur struct Tdeklariert würde, die mit einem größeren endgültigen Array identisch ist, jedoch mit einem größeren endgültigen Array, s[0]müsste das Element mit dem Element s[0]in übereinstimmen struct T, und das Vorhandensein dieser zusätzlichen Elemente könnte den Zugriff auf gemeinsame Elemente der größeren Struktur nicht beeinflussen oder durch diesen beeinflusst werden mit einem Zeiger auf struct T.

R .. GitHub HÖREN SIE AUF, EIS ZU HELFEN
quelle
4
Sie haben Recht, dass die Art der Zeigerarithmetik irrelevant ist, aber Sie haben Unrecht , wenn der Zugriff über die deklarierte Größe des Arrays hinausgeht. Siehe N1494 (letzter öffentlicher C1x-Entwurf), Abschnitt 6.5.6, Absatz 8 - Sie dürfen nicht einmal den Zusatz ausführen, bei dem ein Zeiger mehr als ein Element über die deklarierte Größe des Arrays hinausgeht, und Sie können ihn auch dann nicht dereferenzieren, wenn Es ist nur ein Element vorbei.
zwol
1
@Zack: Das stimmt, wenn das Objekt ein Array ist. Es ist nicht wahr, wenn es sich bei dem Objekt um ein Objekt mallochandelt, das als Array zugewiesen wird, oder wenn es sich um eine größere Struktur handelt, auf die über einen Zeiger auf eine kleinere Struktur zugegriffen wird, deren Elemente unter anderem eine anfängliche Teilmenge der Elemente der größeren Struktur sind Fälle.
R .. GitHub STOP HELPING ICE
6
+1 Wenn mallockein Speicherbereich zugewiesen wird, auf den mit Zeigerarithmetik zugegriffen werden kann, welchen Nutzen hätte dies? Und wenn p->s[1]wird definiert durch den Standard als syntaktischer Zucker für Zeigerarithmetik, dann dieser Antwort lediglich bekräftigt , die mallocnützlich ist. Was gibt es noch zu besprechen? :)
Daniel Earwicker
3
Sie können argumentieren, dass es so gut definiert ist, wie Sie möchten, aber das ändert nichts an der Tatsache, dass es nicht so ist. Der Standard ist sehr klar über den Zugriff über die Grenzen eines Arrays hinaus, und die Grenze dieses Arrays ist 1. So einfach ist das.
Leichtigkeitsrennen im Orbit
3
@R .., ich denke, Ihre Annahme, dass zwei Zeiger, die gleich sind, sich gleich verhalten müssen, ist falsch. Betrachten wir int m[1]; int n[1]; if(m+1 == n) m[1] = 0;die Annahme ifZweig eingegeben wird . Dies ist UB (und es wird nicht garantiert, dass es initialisiert wird n) gemäß 6.5.6 p8 (letzter Satz), wie ich es gelesen habe. Siehe auch: 6.5.9 S. 6 mit Fußnote 109. (Verweise auf C11 n1570.) [...]
Mafso
7

Ja, es ist technisch undefiniertes Verhalten.

Beachten Sie, dass es mindestens drei Möglichkeiten gibt, den "Struktur-Hack" zu implementieren:

(1) Deklarieren des nachfolgenden Arrays mit der Größe 0 (die "beliebteste" Methode im Legacy-Code). Dies ist offensichtlich UB, da die Array-Deklarationen der Größe Null in C immer unzulässig sind. Selbst wenn sie kompiliert werden, übernimmt die Sprache keine Garantie für das Verhalten von Code, der gegen Einschränkungen verstößt.

(2) Deklarieren des Arrays mit minimaler zulässiger Größe - 1 (Ihr Fall). In diesem Fall ist jeder Versuch, einen Zeiger auf eine Zeigerarithmetik zu p->s[0]verwenden, die darüber hinausgeht, p->s[1]undefiniertes Verhalten. Beispielsweise kann eine Debugging-Implementierung einen speziellen Zeiger mit eingebetteten Bereichsinformationen erzeugen, der jedes Mal abgefangen wird, wenn Sie versuchen, einen Zeiger darüber hinaus zu erstellen p->s[1].

(3) Deklarieren des Arrays mit einer "sehr großen" Größe wie beispielsweise 10000. Die Idee ist, dass die deklarierte Größe größer sein soll als alles, was Sie in der Praxis benötigen könnten. Diese Methode ist hinsichtlich des Array-Zugriffsbereichs frei von UB. In der Praxis werden wir jedoch natürlich immer weniger Speicher zuweisen (nur so viel, wie wirklich benötigt wird). Ich bin mir nicht sicher, ob dies legal ist, dh ich frage mich, wie legal es ist, weniger Speicher für das Objekt zuzuweisen als die deklarierte Größe des Objekts (vorausgesetzt, wir greifen niemals auf die "nicht zugewiesenen" Mitglieder zu).

Ameise
quelle
1
In (2) s[1]ist nicht undefiniertes Verhalten. Es ist dasselbe wie *(s+1), was dasselbe ist wie *((char *)p + offsetof(struct T, s) + 1), was ein gültiger Zeiger auf a charim zugewiesenen Objekt ist.
R .. GitHub STOP HELPING ICE
Andererseits bin ich mir fast sicher, dass (3) undefiniertes Verhalten ist. Immer wenn Sie eine Operation ausführen, die von einer solchen Struktur abhängt, die sich an dieser Adresse befindet, kann der Compiler Maschinencode generieren, der aus einem beliebigen Teil der Struktur liest. Es könnte nutzlos sein oder ein Sicherheitsmerkmal für die strikte Zuordnungsprüfung sein, aber es gibt keinen Grund, warum eine Implementierung dies nicht tun könnte.
R .. GitHub STOP HELPING ICE
R: Wenn für ein Array eine Größe deklariert wurde (dies ist nicht nur der foo[]syntaktische Zucker für *foo), ist jeder Zugriff über die kleinere deklarierte Größe und die zugewiesene Größe hinaus UB, unabhängig davon, wie die Zeigerarithmetik ausgeführt wurde.
zwol
1
@Zack, du liegst in mehreren Dingen falsch. foo[]in einer Struktur ist kein syntaktischer Zucker für *foo; Es ist ein flexibles C99-Array-Mitglied. Im Übrigen siehe meine Antwort und Kommentare zu anderen Antworten.
R .. GitHub STOP HELPING ICE
6
Das Problem ist, dass einige Mitglieder des Komitees unbedingt wollen, dass dieser "Hack" UB ist, weil sie sich ein Märchenland vorstellen, in dem eine C-Implementierung Zeigergrenzen erzwingen könnte. Ob gut oder schlecht, dies würde jedoch mit anderen Teilen des Standards in Konflikt stehen - Dinge wie die Fähigkeit, Zeiger auf Gleichheit zu vergleichen (wenn Grenzen im Zeiger selbst codiert wären) oder die Anforderung, dass auf jedes Objekt über ein imaginäres überlagertes unsigned char [sizeof object]Array zugegriffen werden kann . Ich stehe zu meiner Behauptung, dass das flexible Array-Mitglied "Hack" für Pre-C99 ein genau definiertes Verhalten aufweist.
R .. GitHub STOP HELPING ICE
3

Der Standard ist ziemlich klar, dass Sie nicht auf Dinge neben dem Ende eines Arrays zugreifen können. (und das Übergehen von Zeigern hilft nicht, da Sie nach dem Ende des Arrays nicht einmal Zeiger nach einem inkrementieren dürfen).

Und für "Arbeiten in der Praxis". Ich habe gesehen, dass der gcc / g ++ - Optimierer diesen Teil des Standards verwendet und somit falschen Code generiert, wenn dieses ungültige C erfüllt wird.

Bernhard R. Link
quelle
Kannst du ein Beispiel geben?
Tal
1

Wenn ein Compiler so etwas akzeptiert

typedef struct {
  int len;
  char dat [];
};

Ich denke, es ist ziemlich klar, dass es bereit sein muss, einen Index für 'dat' über seine Länge hinaus zu akzeptieren. Auf der anderen Seite, wenn jemand etwas codiert wie:

typedef struct {
  int was auch immer;
  char dat [1];
} MY_STRUCT;

und greift dann später auf somestruct-> dat [x] zu; Ich würde nicht glauben, dass der Compiler verpflichtet ist, Adressberechnungscode zu verwenden, der mit großen Werten von x funktioniert. Ich denke, wenn man wirklich sicher sein wollte, wäre das richtige Paradigma eher wie folgt:

#define LARGEST_DAT_SIZE 0xF000
typedef struct {
  int was auch immer;
  char dat [LARGEST_DAT_SIZE];
} MY_STRUCT;

und dann ein Malloc von (sizeof (MYSTRUCT) -LARGEST_DAT_SIZE + gewünschte_array_length) Bytes ausführen (wobei zu berücksichtigen ist, dass die Ergebnisse undefiniert sein können, wenn die gewünschte_Array_Länge größer als LARGEST_DAT_SIZE ist).

Übrigens denke ich, dass die Entscheidung, Arrays mit der Länge Null zu verbieten, unglücklich war (einige ältere Dialekte wie Turbo C unterstützen dies), da ein Array mit der Länge Null als Zeichen dafür angesehen werden kann, dass der Compiler Code generieren muss, der mit größeren Indizes funktioniert .

Superkatze
quelle