Zeigerindizierung

11

Ich lese gerade ein Buch mit dem Titel "Numerical Recipes in C". In diesem Buch beschreibt der Autor, wie bestimmte Algorithmen von Natur aus besser funktionieren, wenn Indizes mit 1 beginnen (ich folge seinem Argument nicht vollständig und das ist nicht der Sinn dieses Beitrags), aber C indiziert seine Arrays immer beginnend mit 0 Um dies zu umgehen, schlägt er vor, den Zeiger nach der Zuweisung einfach zu dekrementieren, z.

float *a = malloc(size);
a--;

Dies, sagt er, gibt Ihnen effektiv einen Zeiger, dessen Index mit 1 beginnt und der dann frei wird mit:

free(a + 1);

Soweit mir bekannt ist, ist dies jedoch ein undefiniertes Verhalten des C-Standards. Dies ist anscheinend ein sehr seriöses Buch innerhalb der HPC-Community, daher möchte ich nicht einfach ignorieren, was er sagt, sondern nur einen Zeiger außerhalb des zugewiesenen Bereichs zu dekrementieren, scheint mir sehr lückenhaft. Ist dieses "erlaubte" Verhalten in C? Ich habe es sowohl mit gcc als auch mit icc getestet und beide Ergebnisse scheinen darauf hinzudeuten, dass ich mir um nichts Sorgen mache, aber ich möchte absolut positiv sein.

wolfPack88
quelle
3
Auf welchen C-Standard beziehen Sie sich? Ich frage, weil nach meiner Erinnerung "Numerical Recipes in C" in den 1990er Jahren veröffentlicht wurde, in alten Zeiten von K & R und vielleicht ANSI C
gnat
2
Verwandte SO Frage: stackoverflow.com/questions/10473573/…
dan04
3
"Ich habe es sowohl mit gcc als auch mit icc getestet, und beide Ergebnisse scheinen darauf hinzudeuten, dass ich mir um nichts Sorgen mache, aber ich möchte absolut positiv sein." Gehen Sie niemals davon aus, dass die C-Sprache dies zulässt, da Ihr Compiler dies zulässt. Es sei denn natürlich, Sie können Ihren Code in Zukunft nicht mehr ändern.
Doval
5
"Numerical Recipies" wird im Allgemeinen als nützliches, schnelles und schmutziges Buch angesehen, ohne ein Paradigma der Softwareentwicklung oder der numerischen Analyse zu sein. Im Wikipedia-Artikel zu "Numerical Recipies" finden Sie eine Zusammenfassung einiger Kritikpunkte.
Charles E. Grant
1
Nebenbei
bemerkt

Antworten:

16

Sie haben Recht, dass Code wie

float a = malloc(size);
a--;

ergibt undefiniertes Verhalten gemäß ANSI C-Standard, Abschnitt 3.3.6:

Sofern nicht sowohl der Zeigeroperand als auch das Ergebnis auf ein Mitglied desselben Arrayobjekts oder auf eines nach dem letzten Mitglied des Arrayobjekts verweisen, ist das Verhalten undefiniert

Für Code wie diesen wurde die Qualität des C-Codes im Buch (damals, als ich ihn Ende der 90er Jahre verwendete) nicht als sehr hoch angesehen.

Das Problem mit undefiniertem Verhalten ist, dass unabhängig vom Ergebnis, das der Compiler erzeugt, dieses Ergebnis per Definition korrekt ist (auch wenn es sehr destruktiv und unvorhersehbar ist).
Glücklicherweise bemühen sich nur sehr wenige Compiler, in solchen Fällen tatsächlich unerwartetes Verhalten zu verursachen, und die typische mallocImplementierung auf für HPC verwendeten Computern enthält einige Buchhaltungsdaten unmittelbar vor der zurückgegebenen Adresse, sodass Sie durch die Dekrementierung normalerweise einen Zeiger auf diese Buchhaltungsdaten erhalten. Es ist keine gute Idee, dort zu schreiben, aber nur das Erstellen des Zeigers ist auf diesen Systemen harmlos.

Seien Sie sich bewusst sein , dass der Code könnte brechen , wenn die Laufzeitumgebung geändert wird oder wenn der Code in eine andere Umgebung portiert.

Bart van Ingen Schenau
quelle
4
Genau in einer Multi-Bank-Architektur ist es möglich, dass malloc Ihnen die 0. Adresse in einer Bank gibt und die Dekrementierung eine CPU-Falle mit einem Unterlauf für eine verursacht.
Vality
1
Ich bin nicht der Meinung, dass das "Glück" ist. Ich denke, es wäre viel besser, wenn Compiler Code ausgeben würden, der sofort abstürzte, wenn Sie undefiniertes Verhalten aufriefen.
David Conrad
4
@ DavidConrad: Dann ist C nicht die Sprache für dich. Ein Großteil des undefinierten Verhaltens in C kann nicht leicht oder nur mit einem schweren Leistungseinbruch erkannt werden.
Bart van Ingen Schenau
Ich dachte daran, "mit einem Compiler-Schalter" hinzuzufügen. Offensichtlich möchten Sie das nicht für optimierten Code. Aber Sie haben Recht, und deshalb habe ich vor zehn Jahren das Schreiben von C aufgegeben.
David Conrad
@BartvanIngenSchenau Je nachdem, was Sie unter "schwerer Leistungseinbußen" verstehen, gibt es eine symbolische Ausführung für C (z. B. clang + klee) sowie für Sanatizer (asan, tsan, ubsan, valgrind usw.), die für das Debuggen sehr nützlich sind.
Maciej Piechotka
10

Offiziell ist es undefiniertes Verhalten, einen Zeigerpunkt außerhalb des Arrays zu haben (mit Ausnahme eines nach dem Ende), auch wenn er nie dereferenziert wird .

In der Praxis , wenn Ihr Prozessor eine flache Speichermodell (im Gegensatz zu seltsam diejenigen wie hat x86-16 ), und wenn die Compiler Ihnen nicht einen Laufzeitfehler oder falsche Optimierung nicht geben , wenn Sie einen ungültigen Zeiger erstellen, dann Arbeit des Code Alles gut.

dan04
quelle
1
Das macht Sinn. Leider sind das zwei zu viele, wenn es mir gefällt.
WolfPack88
3
Der letzte Punkt ist meiner Meinung nach der problematischste. Da Compiler in diesen Zeiten nicht einfach alles zulassen, was die Plattform "natürlich" im Fall von UB tut, sondern Optimierer es aggressiv ausnutzen , würde ich nicht so leichtfertig damit spielen.
Matteo Italia
3

Erstens ist es undefiniertes Verhalten. Einige optimierende Compiler werden heutzutage sehr aggressiv gegenüber undefiniertem Verhalten. Da a-- in diesem Fall ein undefiniertes Verhalten ist, könnte der Compiler beispielsweise entscheiden, einen Befehl und einen Prozessorzyklus zu speichern und a nicht zu dekrementieren. Welches ist offiziell korrekt und legal.

Wenn Sie dies ignorieren, können Sie 1, 2 oder 1980 subtrahieren. Wenn ich beispielsweise Finanzdaten für die Jahre 1980 bis 2013 habe, kann ich 1980 subtrahieren. Wenn wir nun float * a = malloc (Größe) nehmen; es gibt sicherlich eine große Konstante k, so dass a - k ein Nullzeiger ist. In diesem Fall erwarten wir wirklich, dass etwas schief geht.

Nehmen Sie jetzt eine große Struktur, sagen wir ein Megabyte groß. Ordnen Sie einen Zeiger p zu, der auf zwei Strukturen zeigt. p - 1 kann ein Nullzeiger sein. p - 1 wird möglicherweise umbrochen (wenn eine Struktur ein Megabyte ist und der Malloc-Block 900 KB vom Beginn des Adressraums entfernt ist). So könnte es ohne Böswilligkeit des Compilers sein, dass p - 1> p. Dinge können interessant werden.

gnasher729
quelle
1

... einfach einen Zeiger außerhalb des zugewiesenen Bereichs zu dekrementieren, erscheint mir sehr lückenhaft. Ist dieses "erlaubte" Verhalten in C?

Dürfen? Ja. Gute Idee? Nicht gewöhnlich.

C ist eine Abkürzung für Assemblersprache, und in Assemblersprache gibt es keine Zeiger, nur Speicheradressen. Cs Zeiger sind Speicheradressen, die ein Nebenverhalten aufweisen, bei dem sie um die Größe dessen, worauf sie zeigen, inkrementiert oder dekrementiert werden, wenn sie einer Arithmetik unterzogen werden. Dies macht aus Syntaxperspektive Folgendes gut:

double *p = (double *)0xdeadbeef;
--p;  // p == 0xdeadbee7, assuming sizeof(double) == 8.
double d = p[0];

Arrays sind in C nicht wirklich eine Sache; Sie sind nur Zeiger auf zusammenhängende Speicherbereiche, die sich wie Arrays verhalten. Der []Operator ist eine Abkürzung für Zeigerarithmetik und Dereferenzierung, a[x]bedeutet also eigentlich *(a + x).

Es gibt gute Gründe , die oben, wie einige E / A - Gerät mit ein paar zu tun doubles in die kartierte 0xdeadbee7und 0xdeadbeef. Sehr wenige Programme müssten das tun.

Wenn Sie die Adresse von etwas erstellen, z. B. mithilfe des &Operators oder durch Aufrufen malloc(), möchten Sie den ursprünglichen Zeiger intakt halten, damit Sie wissen, dass das, worauf er verweist, tatsächlich etwas Gültiges ist. Das Dekrementieren des Zeigers bedeutet, dass ein Teil des fehlerhaften Codes versuchen könnte, ihn zu dereferenzieren, fehlerhafte Ergebnisse zu erhalten, etwas zu blockieren oder, abhängig von Ihrer Umgebung, eine Segmentierungsverletzung zu begehen. Dies gilt insbesondere für malloc(), weil Sie die Last auf free()denjenigen legen, der anruft , sich daran zu erinnern, den ursprünglichen Wert zu übergeben, und nicht auf eine geänderte Version, die dazu führt, dass alles zum Teufel losbricht.

Wenn Sie in C 1-basierte Arrays benötigen, können Sie dies sicher tun, indem Sie ein zusätzliches Element zuweisen, das niemals verwendet wird:

double *array_create(size_t size) {
    // Wasting one element, so don't allow it to be full-sized
    assert(size < SIZE_MAX);
    return malloc((size+1) * sizeof(double));
}

inline double array_index(double *array, size_t index) {
    assert(array != NULL);
    assert(index >= 1);  // This is a 1-based array
    return array[index];
}

Beachten Sie, dass dies keinen Schutz gegen das Überschreiten der Obergrenze bietet, aber das ist einfach genug zu handhaben.


Nachtrag:

Einige Kapitel und Verse aus dem C99-Entwurf (Entschuldigung, das ist alles, worauf ich verlinken kann):

§6.5.2.1.1 besagt, dass der zweite ("andere") Ausdruck, der mit dem Indexoperator verwendet wird, vom Typ Integer ist. -1ist eine ganze Zahl, und das macht p[-1]gültig und macht daher auch den Zeiger &(p[-1])gültig. Dies bedeutet nicht, dass der Zugriff auf Speicher an dieser Stelle ein definiertes Verhalten erzeugen würde, aber der Zeiger ist immer noch ein gültiger Zeiger.

§6.5.2.2 besagt, dass der Array-Indexoperator das Äquivalent zum Hinzufügen der Elementnummer zum Zeiger p[-1]ergibt und daher äquivalent zu ist *(p + (-1)). Immer noch gültig, aber möglicherweise nicht erwünscht.

§6.5.6.8 sagt (Hervorhebung von mir):

Wenn ein Ausdruck mit einem ganzzahligen Typ zu einem Zeiger hinzugefügt oder von diesem subtrahiert wird, hat das Ergebnis den Typ des Zeigeroperanden.

... wenn der Ausdruck Pauf das i-te Element eines Array-Objekts zeigt, zeigen die Ausdrücke (P)+N(äquivalent N+(P)) und (P)-N (wo Nder Wert ist n) jeweils auf das i+n-te und i−n-te Element des Array-Objekts, sofern sie vorhanden sind .

Dies bedeutet, dass die Ergebnisse der Zeigerarithmetik auf ein Element in einem Array zeigen müssen. Es heißt nicht, dass die Arithmetik auf einmal durchgeführt werden muss. Deshalb:

double a[20];

// This points to element 9 of a; behavior is defined.
double d = a[-1 + 10];

double *p = a - 1;  // This is just a pointer.  No dereferencing.

double e = p[0];   // Does not point at any element of a; behavior is undefined.
double f = p[1];   // Points at element 0 of a; behavior is defined.

Empfehle ich, die Dinge so zu machen? Ich nicht, und meine Antwort erklärt warum.

Blrfl
quelle
8
-1 Eine Definition von 'erlaubt', die Code enthält, den der C-Standard als undefinierte Ergebnisse deklariert, ist nicht sinnvoll.
Pete Kirkham
Andere haben darauf hingewiesen, dass es sich um undefiniertes Verhalten handelt, daher sollte man nicht sagen, dass es "erlaubt" ist. Der Vorschlag, ein zusätzliches nicht verwendetes Element 0 zuzuweisen, ist jedoch gut.
200_erfolg
Dies ist wirklich nicht richtig, bitte beachten Sie zumindest, dass dies durch den C-Standard verboten ist.
Vality
@ PeteKirkham: Ich bin anderer Meinung. Siehe den Nachtrag zu meiner Antwort.
Blrfl
4
In @Blrfl 6.5.6 des ISO C11-Standards heißt es, wenn einem Zeiger eine Ganzzahl hinzugefügt wird: "Wenn sowohl der Zeigeroperand als auch das Ergebnis auf Elemente desselben Arrayobjekts oder eines nach dem letzten Element des Arrayobjekts zeigen Die Bewertung darf keinen Überlauf erzeugen. Andernfalls ist das Verhalten undefiniert. "
Vality