Pointer-Overflow bei Iterator

[FlorianB82]

Hallo zusammen,

die folgende Frage ist etwas theoretischer Natur - nichtdestotrotz interessiert sie mich sehr, zumal ich dazu auch sonst im Netz nichts finden konnte.

Ich iteriere des öfteren gerne direkt über Speicherbereiche, was so aussieht:

Code: Alles auswählen

unsigned char *bufferEnd = buffer + bufferSize;
for (unsigned char *p = buffer; p < bufferEnd; ++p)
{
    foo(*p);
}

wobei der Speicherbereich gegeben ist durch:

Code: Alles auswählen

unsigned char *buffer = ...;
size_t bufferSize = ...;

In der Variable bufferEnd steht dabei die erste Adresse hinter dem Puffer (also analog zu den End-Iteratoren der STL).

Soweit, so gut. Ich frage mich allerdings, ob der Vergleich im Kopf der for-Schleife aus theoretischer Sicht OK ist (aus der Praxis weiß ich natürlich, dass er funktioniert).

Konkret sehe das folgende Problem: Wenn die letzte gültige Speicherzelle des gegeben Speicherbereiches auf der höchstmöglichen durch den Pointer darstellbaren Adresse liegt (also z.B. auf 0xffffffff bei x86), dann würde bufferEnd wrappen, somit die Adresse 0 erhalten, und die Schleife gar nicht ausgeführt werden. Fatal.

Könnte dies denn passieren? Habe ich in der Praxis bisher einfach nur "Glück" gehabt, dass dieser doch recht unwahrscheinliche Fall nicht eingetreten ist? Teilt das Betriebssystem solche Adressen von vorneherein nicht aus? Oder, was mir lieber wäre: Gibt es irgendwas im C++-Standard, was solche Iterator-Schleifen legitimieren würde? Soweit ich weiß, verwenden viele STL-Implementierungen im Release-Modus für ihre Iteratoren auch Roh-Zeiger, also muss es doch offensichtlich wassserdicht sein?

[eXile]

Gibt es irgendwas im C++-Standard, was solche Iterator-Schleifen legitimieren würde?

Ja. :)

When an expression that has integral type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integral expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i + n-th and i − n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

[FlorianB82]

Ahhhh, danke! Jetzt bin ich wieder glücklich!

[Krishty]

If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined.

Was bedeutet das jetzt? Ich lese das so, dass ich darauf achten muss, dass ich nicht bis inklusive ~uintptr_t(0) allokiere, weil ich sonst undefiniertes Verhalten erreiche. Da steht ja nirgends, dass „the implementation“ (also Compiler oder CRT) dafür verantwortlich sind, oder? Und wäre dem so, sprächen sie von einer nicht-konformen Implementierung und Ähnlichem; aber nicht von undefiniertem Verhalten, oder?

[eXile]

So wie ich das lese, bezieht sich das shall auf die Evaluation. Der Absatz dort definiert ja gerade die Evaluation; und die Evaluation ist so definiert, dass kein Overflow stattfinden darf. Die Implementierung implementiert eben (insbesondere) diese Evaluation, so wie sie eben den ganzen Rest vom C++-Standard implementiert (als ob).

Davon abgesehen bezieht sich das Zitat von Section 5.7, Clause 5 auf die Zeile

Code: Alles auswählen

unsigned char *bufferEnd = buffer + bufferSize;

sowie das ++p der Schleife selbst. Wenn man jetzt wissen will, warum der Vergleich p < bufferEnd in

Code: Alles auswählen

for (unsigned char *p = buffer; p < bufferEnd; ++p)

funktioniert, kann man sich anschauen:

If two pointers point to elements of the same array or one beyond the end of the array, the pointer to the object with the higher subscript compares higher.

D.h. zumindest nach C++-Standard darf, wenn eine Implementierung ein Array genau am Ende des Speicherbereichs zulassen würde, die Implementierung kein einfaches cmp emitten, sondern müsste noch weitere Dinge überprüfen; eben um diese Garantie sicherzustellen. In der Praxis ist auf Windows vermutlich die letzte Memory-Page irgendwie geschützt, damit so etwas nie eintreten kann.

In den oben zitieren Sections sind extrem viele Spezialfälle mit diesen besonderem, herausgehobenen Speicherplatz eins nach dem Array drin. Zumindest nach schnellem Lesen scheint es so, dass man (solange man keinen Zeiger darauf dereferenziert!) man mit einem Zeiger auf diesen Speicherplatz alles sinnvolle tun kann (Zeigeraddition, Zeigersubtraktion, Zeigervergleiche).

Dahingegen wäre es wohl so, dass wenn man für ein Array char arr[10]; die Zeigerarithmetik char * afterLastElement = (arr + 11) - 1; ausführen will, dies undefiniertes Verhalten ist. Der Compiler darf das dann wegoptimieren, was zu hervorragenden Fehlern führen kann.

Ebenso natürlich char * firstElement = (arr - 1) + 1;. Damit ist auch klar, dass Assoziatitivät bei Zeigerarithmetik nicht gilt, denn char * firstElement = arr - 1 + 1; ist undefiniert, wohingegen char * firstElement = arr + 1 - 1; natürlich OK ist.

[Krishty]

So wie ich das lese, bezieht sich das shall auf die Evaluation. Der Absatz dort definiert ja gerade die Evaluation; und die Evaluation ist so definiert, dass kein Overflow stattfinden darf. Die Implementierung implementiert eben (insbesondere) diese Evaluation, so wie sie eben den ganzen Rest vom C++-Standard implementiert (als ob).

Davon abgesehen bezieht sich das Zitat von Section 5.7, Clause 5 auf die Zeile

Code: Alles auswählen

unsigned char *bufferEnd = buffer + bufferSize;

sowie das ++p der Schleife selbst. […]

Ah danke; das ergibt Sinn! :)

In der Praxis ist auf Windows vermutlich die letzte Memory-Page irgendwie geschützt, damit so etwas nie eintreten kann.

Ja; und Raymond Chen ist schon auf die Ursprungsfrage eingegangen: The Old New Thing – The C language specification describes an abstract computer, not a real one

Und er hatte auch irgendwo eine Karte des Adressraums, auf der man das jetzt nachschauen könnte (aber Google lässt sie mich nicht finden). Die unteren 64 KiB Speicher sind für Systemressourcen reserviert (damit Strings 16-Bit-IDs zugeordnet werden können, die von Zeigern unterscheidbar sind; und um Nullzugriffe abzufangen); die hohen 64 KiB des 32-Bit-Adressraums werden unter Windows sowieso nicht benutzt um zum Alpha AXP-Prozessor kompatibel zu bleiben (The Old New Thing – Why is address space allocation granularity 64K?), und kurz davor werden relokierbare DLLs platziert; die hohen 16 Bits des 64-Bit-Adressraums sind üblicherweise noch nicht erreichbar, und selbst wenn sie es denn sind, ist anzunehmen, dass das obere Ende wegen solchen Spezialfällen reserviert bleibt.

Nochmal deutlich: Ihr bekommt auf Windows niemals einen Zeiger zurück, der einen numerischen Wert unter 65536 hat (oder 64 KiB an der 2-GiB-Grenze). Wer also Dinge programmiert, die Windows-only sind, kann das für Zusatzinformationen und Zweckentfremdung nutzen (wie die WinAPI selber – MAKEINTRESOURCE() konvertiert die 16-Bit-ID einfach hart zu einem Zeiger, und daran, ob der Zeiger kleiner als 65536 ist, erkennt z.B. LoadIcon(), ob ihr eine Ressource meint oder einen „echten“ String-Zeiger übergeben habt).

In den oben zitieren Sections sind extrem viele Spezialfälle mit diesen besonderem, herausgehobenen Speicherplatz eins nach dem Array drin. Zumindest nach schnellem Lesen scheint es so, dass man (solange man keinen Zeiger darauf dereferenziert!) man mit einem Zeiger auf diesen Speicherplatz alles sinnvolle tun kann (Zeigeraddition, Zeigersubtraktion, Zeigervergleiche).

Dahingegen wäre es wohl so, dass wenn man für ein Array char arr[10]; die Zeigerarithmetik char * afterLastElement = (arr + 11) - 1; ausführen will, dies undefiniertes Verhalten ist. Der Compiler darf das dann wegoptimieren, was zu hervorragenden Fehlern führen kann.

Ebenso natürlich char * firstElement = (arr - 1) + 1;. Damit ist auch klar, dass Assoziatitivät bei Zeigerarithmetik nicht gilt, denn char * firstElement = arr - 1 + 1; ist undefiniert, wohingegen char * firstElement = arr + 1 - 1; natürlich OK ist.

Ja; afaik absolut richtig. Darum ist einfache Rückwärtsiteration auch nicht mehr standardkonform, sobald man rohe Zeiger nutzt.