Ist es sicher, auf x86 und x64 über das Ende eines Puffers innerhalb derselben Seite hinaus zu lesen?

Viele Methoden, die in Hochleistungsalgorithmen zu finden sind, könnten (und werden) vereinfacht, wenn sie eine kleine Menge über das Ende von Eingabepuffern hinaus lesen dürften. „Kleine Menge“ bedeutet hier im Allgemeinen bis zu W - 1 Bytes nach dem Ende, wo W ist die Wortgröße in Bytes des Algorithmus (z. B. bis zu 7 Bytes für einen Algorithmus, der die Eingabe in 64-Bit-Blöcken verarbeitet).

Es ist klar, dass Schreiben über das Ende eines Eingabepuffers hinaus ist im Allgemeinen niemals sicher, da Sie möglicherweise Daten über den Puffer hinaus verstopfen¹. Es ist auch klar, dass das Lesen über das Ende eines Puffers hinaus in eine andere Seite einen Segmentierungsfehler/eine Zugriffsverletzung auslösen kann, da die nächste Seite möglicherweise nicht lesbar ist.

Im Spezialfall des Lesens von ausgerichteten Werten scheint ein Seitenfehler jedoch zumindest auf x86 unmöglich. Auf dieser Plattform haben Seiten (und damit Speicherschutz-Flags) eine 4K-Granularität (größere Seiten, z. B. 2 MiB oder 1 GiB, sind möglich, aber dies sind Vielfache von 4 K), und daher greifen ausgerichtete Lesevorgänge nur auf Bytes auf derselben Seite wie die gültige zu Teil des Puffers.

Hier ist ein kanonisches Beispiel für eine Schleife, die ihre Eingabe ausrichtet und bis zu 7 Bytes nach dem Ende des Puffers liest:

int processBytes(uint8_t *input, size_t size) {

    uint64_t *input64 = (uint64_t *)input, end64 = (uint64_t *)(input + size);
    int res;

    if (size < 8) {
        // special case for short inputs that we aren't concerned with here
        return shortMethod();
    }

    // check the first 8 bytes
    if ((res = match(*input)) >= 0) {
        return input + res;
    }

    // align pointer to the next 8-byte boundary
    input64 = (ptrdiff_t)(input64 + 1) & ~0x7;

    for (; input64 < end64; input64++) {
        if ((res = match(*input64)) > 0) {
            return input + res < input + size ? input + res : -1;
        }
    }

    return -1;
}

Die innere Funktion int match(uint64_t bytes) wird nicht angezeigt, aber es ist etwas, das nach einem Byte sucht, das einem bestimmten Muster entspricht, und die niedrigste derartige Position (0-7) zurückgibt, wenn sie gefunden wird, oder -1 andernfalls.

Zunächst werden Fälle mit einer Größe < 8 zur Vereinfachung der Darstellung einer anderen Funktion verpfändet. Dann wird eine einzelne Prüfung für die ersten 8 (nicht ausgerichtete Bytes) durchgeführt. Dann wird eine Schleife für den Rest gemacht floor((size – 7) / 8) Blöcke von 8 Bytes². Diese Schleife kann bis zu 7 Bytes nach dem Ende des Puffers lesen (der 7-Byte-Fall tritt auf, wenn input & 0xF == 1). Rückruf hat jedoch eine Prüfung, die jeden ausschließt falsche Übereinstimmungen die über das Ende des Puffers hinaus auftreten.

Ist eine solche Funktion praktisch auf x86 und x86-64 sicher?

Diese Arten von überliest sind in Hochleistungscode üblich. Spezieller Endcode, um solches zu vermeiden überliest ist auch üblich. Manchmal sieht man, dass der letztere Typ den ersteren ersetzt, um Werkzeuge wie Valgrind zum Schweigen zu bringen. Manchmal sieht man ein Vorschlag eine solche Ersetzung durchzuführen, die mit der Begründung abgelehnt wird, dass das Idiom sicher und das Werkzeug fehlerhaft (oder einfach zu konservativ) ist.³.

Hinweis für Sprachjuristen:

Das Lesen von einem Zeiger über seine zugewiesene Größe hinaus ist im Standard definitiv nicht erlaubt. Ich schätze Antworten von Sprachjuristen und schreibe sie gelegentlich sogar selbst, und ich freue mich sogar, wenn jemand das Kapitel und den Vers ausgräbt, die den obigen Code zeigen undefiniertes Verhalten und daher im strengsten Sinne nicht sicher (und ich werde die Details hier kopieren). Letztlich ist das aber nicht das, was ich anstrebe. Aus praktischer Sicht sind viele gebräuchliche Redewendungen, die Zeigerkonvertierung, Strukturzugriff durch solche Zeiger usw. umfassen, technisch undefiniert, aber in Code hoher Qualität und hoher Leistung weit verbreitet. Oft gibt es keine Alternative, oder die Alternative läuft mit halber Geschwindigkeit oder weniger.

Wenn Sie möchten, ziehen Sie eine modifizierte Version dieser Frage in Betracht, die lautet:

Nachdem der obige Code in die x86/x86-64-Assembly kompiliert wurde und der Benutzer überprüft hat, dass er auf die erwartete Weise kompiliert wurde (dh der Compiler hat keinen nachweisbaren teilweise außerhalb der Grenzen liegenden Zugriff verwendet, um wirklich etwas zu tun clever, ist die Ausführung des kompilierten Programms sicher?

Insofern ist diese Frage sowohl eine C-Frage als auch eine x86-Assembler-Frage. Der größte Teil des Codes, der diesen Trick verwendet, den ich gesehen habe, ist in C geschrieben, und C ist immer noch die dominierende Sprache für Hochleistungsbibliotheken, die leicht Dinge auf niedrigerer Ebene wie asm und Dinge auf höherer Ebene wie in den Schatten stellt. Zumindest außerhalb der numerischen Hardcore-Nische, in der FORTRAN immer noch Ball spielt. Daher interessiere ich mich für die C-Compiler und darunter Sicht auf die Frage, weshalb ich sie nicht als reine x86-Assembler-Frage formuliert habe.

Alles in allem bin ich zwar nur mäßig an einem Link zum Standard interessiert, der zeigt, dass dies UD ist, aber ich bin sehr an allen Details tatsächlicher Implementierungen interessiert, die dieses spezielle UD verwenden können, um unerwarteten Code zu erzeugen. Jetzt tue ich es nicht denken Dies kann ohne eine tiefgreifende, ziemlich tiefgreifende verfahrensübergreifende Analyse passieren, aber das gcc-Überlaufzeug hat auch viele Leute überrascht …

¹ Auch in scheinbar harmlosen Fällen, zB wenn der gleiche Wert zurückgeschrieben wird, kann es passieren gleichzeitigen Code brechen.

² Hinweis: Damit diese Überlappung funktioniert, muss diese Funktion und match() Funktion, sich auf eine bestimmte idempotente Weise zu verhalten – insbesondere, dass der Rückgabewert überlappende Prüfungen unterstützt. Also ein “Erstes Byte passendes Muster finden” funktioniert da schon alles match() Anrufe sind noch in Ordnung. Ein “Zähle Bytes übereinstimmendes Muster”-Verfahren würde jedoch nicht funktionieren, da einige Bytes doppelt gezählt werden könnten. Nebenbei bemerkt: Einige Funktionen wie der Aufruf “Return the Minimum Byte” würden auch ohne die In-Order-Beschränkung funktionieren, müssen aber alle Bytes untersuchen.

³ Es ist erwähnenswert, dass dies für valgrinds Memcheck es gibt eine Fahne, --partial-loads-ok die steuert, ob solche Lesevorgänge tatsächlich als Fehler gemeldet werden. Die Voreinstellung ist Jawohlbedeutet, dass im Allgemeinen solche Ladevorgänge nicht als unmittelbare Fehler behandelt werden, sondern dass versucht wird, die nachfolgende Verwendung geladener Bytes zu verfolgen, von denen einige gültig und andere nicht sind, wobei ein Fehler gekennzeichnet wird, wenn das Out- Of-Range-Bytes sind Gebraucht. In Fällen wie dem obigen Beispiel, in denen auf das gesamte Wort zugegriffen wird match(), wird eine solche Analyse zu dem Schluss kommen, dass auf die Bytes zugegriffen wird, obwohl die Ergebnisse letztendlich verworfen werden. Valgrind kann es generell nicht festzustellen, ob tatsächlich ungültige Bytes aus einem Teilladevorgang verwendet werden (und die Erkennung im Allgemeinen wahrscheinlich ist sehr schwer).