Hallo Habr! Ich präsentiere Ihnen die Übersetzung des Artikels "Zeiger sind kompliziert oder: Was ist in einem Byte?" Urheberschaft von Ralf Jung.
Diesen Sommer arbeite ich wieder ganztägig an Rust und werde (unter anderem) wieder an einem „Speichermodell“ für Rust / MIR arbeiten. Bevor ich jedoch über meine Ideen spreche, muss ich endlich den Mythos zerstreuen, dass "Zeiger einfach sind: Sie sind nur Zahlen". Beide Teile dieser Aussage sind fehlerhaft, zumindest in Sprachen mit unsicheren Merkmalen wie Rust oder C: Zeiger können weder als Primzahlen noch als (gewöhnliche) Zahlen bezeichnet werden.
Ich möchte auch den Teil des Speichermodells diskutieren, der angesprochen werden muss, bevor wir über die komplexeren Teile sprechen können: In welcher Form werden die Daten im Speicher gespeichert? Ein Speicher besteht aus Bytes, minimal adressierbaren Einheiten und den kleinsten Elementen, auf die zugegriffen werden kann (zumindest auf den meisten Plattformen). Was sind jedoch die möglichen Bytewerte? Wieder stellt sich heraus, dass "es ist nur eine 8-Bit-Zahl" nicht als Antwort geeignet ist.
Ich hoffe, dass Sie mir nach dem Lesen dieses Beitrags in Bezug auf beide Aussagen zustimmen.
Zeiger sind kompliziert
Was ist das Problem mit "Zeiger sind reguläre Zahlen"? Schauen wir uns das folgende Beispiel an: (Ich verwende hier C ++, da das Schreiben von unsicherem Code in C ++ einfacher ist als das Schreiben in Rust, und unsicherer Code nur der Ort ist, an dem die Probleme auftreten. Unsicheres Rust und C haben dieselben Probleme wie das und C ++).
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; int i = ; auto x_ptr = &x[i]; *x_ptr = 23; return y[0]; }
Die Optimierung des letzten Lesevorgangs von y [0] mit einer Rückgabe von 42 ist immer sehr vorteilhaft. Der Grund für diese Optimierung ist, dass das Ändern von x_ptr, das auf x zeigt, y nicht ändern kann.
Wenn wir uns jedoch mit einfachen Sprachen wie C ++ befassen, können wir diese Annahme verletzen, indem wir i den Wert yx zuweisen. Da & x [i] dasselbe ist wie x + i, schreiben wir 23 in & y [0].
Dies hindert C ++ - Compiler natürlich nicht daran, solche Optimierungen vorzunehmen. Um dies zu beheben, sagt der Standard, dass unser Code UB hat .
Erstens ist es nicht zulässig, arithmetische Operationen an Zeigern durchzuführen (wie im Fall von & x [i]), wenn in diesem Fall der Zeiger eine der Grenzen des Arrays überschreitet . Unser Programm verstößt gegen diese Regel: x [i] geht über x hinaus, es ist also UB. Mit anderen Worten, selbst die Berechnung des x_ptr-Werts ist UB, sodass wir nicht einmal an die Stelle gelangen, an der wir diesen Zeiger verwenden möchten.
(Es stellt sich heraus, dass i = yx auch UB ist, da nur Zeiger, die auf dieselbe Speicherzuordnung zeigen , subtrahiert werden dürfen . Wir könnten jedoch i = ((size_t) y - (size_t) x) / sizeof (int) schreiben, um zu umgehen Dies ist eine Einschränkung.)
Aber wir sind noch nicht fertig: Diese Regel hat die einzige Ausnahme, die wir zu unserem Vorteil nutzen können. Wenn die arithmetische Operation den Wert des Zeigers auf die Adresse genau nach dem Ende des Arrays berechnet, ist alles in Ordnung. (Diese Ausnahme wird benötigt, um vec.end () für die häufigsten Schleifen in C ++ 98 zu berechnen.)
Lassen Sie uns das Beispiel ein wenig ändern:
int test() { auto x = new int[8]; auto y = new int[8]; y[0] = 42; auto x_ptr = x+8;
Stellen Sie sich nun vor, dass x und y nacheinander zugewiesen wurden, wobei y eine größere Adresse hat. Dann zeigt x_ptr auf den Anfang von y! Dann ist die Bedingung wahr und die Zuordnung erfolgt. Gleichzeitig gibt es keine UB aufgrund des Austritts des Zeigers ins Ausland.
Dies scheint keine Optimierung zu ermöglichen. Der C ++ - Standard hat jedoch ein weiteres Ass im Ärmel, um Compiler-Erstellern zu helfen: Tatsächlich erlaubt es uns nicht, x_ptr zu verwenden. Gemäß den Angaben des Standards zum Hinzufügen von Zahlen zu Zeigern zeigt x_ptr auf die Adresse nach dem letzten Element des Arrays. Es zeigt nicht auf ein bestimmtes Element eines anderen Objekts, selbst wenn diese dieselbe Adresse haben . (Zumindest ist dies eine gängige Interpretation des Standards, auf dessen Grundlage LLVM diesen Code optimiert .)
Und obwohl x_ptr und & y [0] auf dieselbe Adresse zeigen , werden sie dadurch nicht zum selben Zeiger , dh sie können nicht austauschbar verwendet werden: & y [0] zeigt auf das erste Element von y; x_ptr zeigt auf die Adresse nach x. Wenn wir * x_ptr = 23 durch die Zeichenfolge * & y [0] = 0 ersetzen, ändern wir den Wert des Programms, obwohl die beiden Zeiger auf Gleichheit überprüft wurden.
Dies ist es wert, wiederholt zu werden:
Nur weil zwei Zeiger auf dieselbe Adresse zeigen, bedeutet dies nicht, dass sie gleich sind und austauschbar verwendet werden können.
Ja, dieser Unterschied ist schwer zu fassen. Tatsächlich führt dies immer noch zu Unterschieden bei Programmen, die mit LLVM und GCC kompiliert wurden.
Beachten Sie auch, dass diese One-After-Regel nicht der einzige Ort in C / C ++ ist, an dem wir einen solchen Effekt beobachten können. Ein weiteres Beispiel ist das Schlüsselwort "Einschränken" in C, mit dem ausgedrückt werden kann, dass sich Zeiger nicht überlappen (nicht gleich sind):
int foo(int *restrict x, int *restrict y) { *x = 42; if (x == y) { *y = 23; } return *x; } int test() { int x; return foo(&x, &x); }
Der Aufruf test () ruft UB auf, da zwei Speicherzugriffe in foo nicht an derselben Adresse erfolgen sollten. Wenn Sie * y durch * x in foo ersetzen, ändern wir den Wert des Programms und es wird UB nicht mehr aufgerufen. Noch einmal: Obwohl x und y dieselbe Adresse haben, können sie nicht austauschbar verwendet werden.
Zeiger sind definitiv nicht nur Zahlen.
Einfaches Zeigermodell
Was ist ein Zeiger? Ich kenne die vollständige Antwort nicht. In der Tat ist dies ein offener Bereich für die Forschung.
Ein wichtiger Punkt: Hier betrachten wir ein abstraktes Zeigermodell. Auf einem echten Computer sind Zeiger natürlich Zahlen. Ein echter Computer führt jedoch nicht die Optimierungen durch, die moderne C ++ - Compiler vornehmen. Wenn wir die obigen Programme in Assembler schreiben würden, gäbe es keine UB, keine Optimierungen. C ++ und Rust verfolgen einen "übergeordneten" Ansatz für Speicher und Zeiger und beschränken den Programmierer auf den Compiler. Wenn Sie formal beschreiben müssen, was ein Programmierer in diesen Sprachen tun kann und was nicht, ist das Modell der Zeiger als Zahlen zerbrochen, sodass wir etwas anderes finden müssen. Dies ist ein weiteres Beispiel für die Verwendung einer "virtuellen Maschine", die sich von einem realen Computer für Spezifikationszwecke unterscheidet - eine Idee, über die ich zuvor geschrieben habe .
Hier ist ein einfacher Satz (tatsächlich wird dieses Zeigermodell von CompCert und meiner Arbeit von RustBelt verwendet sowie die Art und Weise , wie der Miri-Interpreter Zeiger implementiert): Ein Zeiger ist ein Paar einer ID, die einen Speicherbereich eindeutig identifiziert (Zuordnung), und der Versatz ist relativ zu dieser Bereich. Wenn Sie dies in Rust schreiben:
struct Pointer { alloc_id: usize, offset: isize, }
Die Operationen zum Hinzufügen (Subtrahieren) einer Zahl zu einem Zeiger (von einem Zeiger) wirken sich nur auf den Versatz aus, und daher kann der Zeiger den Speicherbereich niemals verlassen. Das Subtrahieren von Zeigern ist nur möglich, wenn sie zum selben Speicherbereich gehören (gemäß C ++ ).
(Wie wir sehen können, wendet der C ++ - Standard diese Regeln auf Arrays an, nicht auf Speicherbereiche. LLVM wendet sie jedoch auf Bereichsebene an .)
Es stellt sich heraus (und Miri zeigt dasselbe), dass dieses Modell uns gute Dienste leisten kann. Wir erinnern uns immer daran, zu welchem Speicherbereich der Zeiger gehört, sodass wir den nachfolgenden Zeiger eines Speicherbereichs vom Zeiger auf den Anfang eines anderen Bereichs unterscheiden können. So kann miri feststellen, dass unser zweites Beispiel (mit & x [8]) UB hat.
Unser Modell fällt auseinander
In unserem Modell sind Zeiger, obwohl sie keine Zahlen sind, zumindest einfach. Dieses Modell wird jedoch vor unseren Augen auseinanderfallen, sobald Sie sich an die Umwandlung von Zeigern in Zahlen erinnern. In miri bewirkt das Umsetzen eines Zeigers auf eine Zahl eigentlich nichts. Wir erhalten lediglich eine numerische Variable (d. H. Ihr Typ sagt, dass es sich um eine Zahl handelt), deren Wert ein Zeiger ist (d. H. Ein Paar aus Speicherbereich und Versatz). Das Multiplizieren dieser Zahl mit 2 führt jedoch zu einem Fehler, da völlig unklar ist, was es bedeutet, "einen solchen abstrakten Zeiger mit 2 zu multiplizieren".
Ich muss klarstellen: Dies ist keine gute Lösung, wenn es darum geht, die Semantik einer Sprache zu definieren. Dies funktioniert jedoch gut für den Interpreter. Dies ist der einfachste Ansatz, und wir haben ihn gewählt, weil nicht klar ist, wie dies anders gemacht werden kann (außer um solche Reduzierungen überhaupt nicht zu unterstützen - aber mit ihrer Unterstützung kann miri mehr Programme ausführen): In unserer abstrakten Maschine gibt es keinen einzigen "Adressraum". in dem sich alle zugewiesenen Speicherbereiche befinden würden und alle Zeiger auf bestimmte unterschiedliche Nummern abgebildet wurden. Jeder Speicherbereich wird durch eine (versteckte) ID identifiziert. Jetzt können wir beginnen, unserem Modell zusätzliche Daten hinzuzufügen, wie z. B. die Basisadresse für jeden Speicherbereich, und sie irgendwie verwenden, um die Nummer wieder auf den Zeiger zu bringen ... und an diesem Punkt wird der Prozess wirklich sehr kompliziert und auf jeden Fall eine Diskussion darüber Modelle sind nicht der Zweck, einen Beitrag zu schreiben. Ziel ist es, die Notwendigkeit eines solchen Modells zu erörtern. Wenn Sie interessiert sind, empfehle ich Ihnen, dieses Dokument zu lesen, in dem die obige Idee des Hinzufügens einer Basisadresse näher erläutert wird.
Kurz gesagt, die Abgüsse von Zeigern und Zahlen zueinander sind verwirrend und angesichts der oben diskutierten Optimierungen formal schwer zu bestimmen. Es besteht ein Konflikt zwischen dem für Optimierungen erforderlichen Ansatz auf hoher Ebene und dem Ansatz auf niedriger Ebene, der zur Beschreibung von Casting-Zeigern auf Zahlen erforderlich ist, und umgekehrt. Zum größten Teil ignorieren wir dieses Problem in miri einfach und versuchen, wann immer möglich, mit dem einfachen Modell, mit dem wir arbeiten, so viel wie möglich zu tun. Eine vollständige Definition von Sprachen wie C ++ oder Rust kann natürlich nicht so einfach sein, sondern sollte erklären, was wirklich passiert. Soweit ich weiß, gibt es keine geeignete Lösung, aber die akademische Forschung nähert sich der Wahrheit .
Deshalb sind Zeiger auch nicht einfach.
Von Zeigern zu Bytes
Ich hoffe, ich habe ein überzeugendes Argument vorgebracht, dass Zahlen nicht der einzige Datentyp sind, der berücksichtigt werden muss, wenn wir Low-Level-Sprachen wie C ++ oder den (unsicheren) Teil von Rust formal beschreiben möchten. Dies bedeutet jedoch, dass eine einfache Operation wie das Lesen eines Bytes aus dem Speicher nicht einfach u8 zurückgeben kann. Stellen Sie sich vor, wir implementieren memcpy, indem wir jedes Byte der Quelle nacheinander in eine lokale Variable v lesen und diesen Wert dann am Zielspeicherort speichern. Was aber, wenn dieses Byte Teil eines Zeigers ist? Wenn der Zeiger ein Paar aus Speicherbereichs-ID und Offset ist, welches ist dann sein erstes Byte? Wir müssen sagen, was der Wert von v ist, also müssen wir diese Frage irgendwie beantworten. (Und dies ist ein völlig anderes Problem als das Problem mit der Multiplikation, das im vorherigen Abschnitt beschrieben wurde. Wir gehen nur davon aus, dass es einen abstrakten Typ von Ponter gibt.)
Wir können das Byte des Zeigers nicht als Wert des Bereichs 0..256 darstellen (Hinweis: Im Folgenden wird 0 aktiviert, 256 nicht). Wenn wir ein naives Speicherrepräsentationsmodell verwenden, geht im Allgemeinen der zusätzliche „versteckte“ Teil des Zeigers (der ihn zu mehr als nur einer Zahl macht) verloren, wenn der Zeiger in den Speicher geschrieben und daraus erneut gelesen wird. Wir müssen dies beheben und dafür unser Konzept des „Bytes“ erweitern, um diesen zusätzlichen Zustand darzustellen. Somit ist das Byte nun entweder der Wert des Bereichs 0..256 ("Rohbits") oder das n-te Byte eines abstrakten Zeigers. Wenn wir unser Speichermodell in Rust implementieren müssten, könnte es so aussehen:
enum ByteV1 { Bits(u8), PtrFragment(Pointer, u8), }
Beispielsweise repräsentiert PtrFragment (ptr, 0) das erste Byte des ptr-Zeigers. Somit kann memcpy den Zeiger in separate Bytes "zerlegen", die diesen Zeiger im Speicher darstellen, und sie einzeln kopieren. In einer 32-Bit-Architektur enthält die vollständige ptr-Darstellung 4 Byte:
[PtrFragment(ptr, 0), PtrFragment(ptr, 1), PtrFragment(ptr, 2), PtrFragment(ptr, 3)]
Diese Darstellung unterstützt alle Operationen zum Verschieben von Daten über Zeiger auf Byte-Ebene, was für die Speicherung völlig ausreicht. Arithmetik- oder Bitoperationen werden nicht vollständig unterstützt. Wie oben erwähnt, würde dies eine komplexere Darstellung von Zeigern erfordern.
Nicht initialisierter Speicher
Wir haben jedoch unsere Definition von "Byte" noch nicht abgeschlossen. Um das Verhalten des Programms vollständig zu beschreiben, müssen wir eine andere Option in Betracht ziehen: Ein Byte im Speicher kann nicht initialisiert werden . Die Definition des letzten Bytes sieht folgendermaßen aus (nehmen wir an, wir haben einen Zeigertyp für Zeiger):
enum Byte { Bits(u8), PtrFragment(Pointer, u8), Uninit, }
Wir verwenden den Uninit-Wert für alle Bytes im zugewiesenen Speicher, in die wir noch keinen Wert geschrieben haben. Es ist möglich, nicht initialisierten Speicher ohne Probleme zu lesen, aber alle anderen Aktionen mit diesen Bytes (z. B. numerische Arithmetik) führen zu UB.
Dies ist den LLVM-Regeln in Bezug auf den speziellen Giftwert sehr ähnlich. Beachten Sie, dass LLVM auch einen undef-Wert hat, der für nicht initialisierten Speicher verwendet wird und etwas anders funktioniert. Das Kompilieren unserer Uninit zu undef ist jedoch korrekt (undef ist in gewisser Weise „schwächer“), und es gibt Vorschläge , undef aus LLVM zu entfernen und stattdessen Gift zu verwenden .
Sie fragen sich vielleicht, warum wir überhaupt einen besonderen Uninit-Wert haben. Warum nicht für jedes neue Byte ein beliebiges b: u8 auswählen und dann Bits (b) als Anfangswert verwenden? Dies ist wirklich eine Option. Zunächst kamen jedoch alle Compiler zu diesem Ansatz, indem sie einen speziellen Wert für nicht initialisierten Speicher verwendeten. Wenn Sie diesen Ansatz nicht befolgen, werden nicht nur Kompilierungsprobleme durch LLVM verursacht, sondern auch alle Optimierungen überprüft und sichergestellt, dass sie mit diesem modifizierten Modell ordnungsgemäß funktionieren. Der entscheidende Punkt hier: Sie können Uninit immer sicher durch einen anderen Wert ersetzen: Jede Operation, die diesen Wert empfängt, führt in jedem Fall zu UB.
Zum Beispiel ist dieser C-Code mit Uninit einfacher zu optimieren:
int test() { int x; if (condA()) x = 1;
Mit Uninit können wir leicht sagen, dass x entweder einen Uninit-Wert oder einen Wert von 1 hat, und da das Ersetzen von Uninit durch 1 funktioniert, ist die Optimierung leicht zu erklären. Ohne Uninit ist x entweder „eine Art beliebiges Bitmuster“ oder 1, und dieselbe Optimierung ist schwerer zu erklären.
(Wir können argumentieren, dass wir Operationen austauschen können, wenn wir eine nicht deterministische Entscheidung treffen, aber dann müssen wir beweisen, dass der schwer zu analysierende Code in keiner Weise x verwendet. Uninit vermeidet dieses Problem mit unnötigen Beweisen.)
Schließlich ist Uninit die beste Wahl für Dolmetscher wie miri. Solche Interpreter haben Probleme mit Operationen wie „Wählen Sie einfach einen dieser Werte aus“ (dh nicht deterministische Operationen), da sie dazu neigen, alle möglichen Pfade der Programmausführung zu durchlaufen, was bedeutet, dass sie alle möglichen Werte ausprobieren müssen. Die Verwendung von Uninit anstelle eines beliebigen Bitmusters bedeutet, dass miri Ihnen nach einem Programmlauf mitteilen kann, ob Ihr Programm nicht initialisierte Werte falsch verwendet.
Fazit
Wir haben gesehen, dass in Sprachen wie C ++ und Rust (im Gegensatz zu echten Computern) Zeiger unterschiedlich sein können, selbst wenn sie auf dieselbe Adresse verweisen, und dass ein Byte mehr als nur eine Zahl im Bereich 0..256 ist. Wenn die C-Sprache 1978 "portabler Assembler" sein könnte, ist dies jetzt eine unglaublich falsche Aussage.