C-Strings: ein Fehler, der seit 50 Jahren anhält

 (longtran2904.substack.com)
1 Punkte von GN⁺ 4 시간 전 | 1 Kommentare | Auf WhatsApp teilen
  • NUL-terminierte Strings in C bewahren keine Längeninformation, führen zu wiederholtem Suchen und Grenzfehlern; heute sind längenbasierte Strings, die Zeiger und Größe gemeinsam speichern, als Grunddesign besser geeignet
  • Ohne explizite Länge kommt es wiederholt zu strlen-Aufrufen und Byte-Durchläufen, und bei snprintf, sizeof und strlen unterscheidet sich jeweils, ob das Terminierungsbyte enthalten ist, was Schreiben und Review von Code erschwert
  • Längenbasierte Strings behandeln leere Strings konsistent mit size == 0 und können Such-, Split- und Slicing-Operationen unverändert auch auf beliebige Binärdaten mit NUL-Bytes anwenden
  • Sie können Teilstrings zurückgeben, die auf einen Bereich des ursprünglichen Speichers zeigen, und so bei Trimmen, Suchen, Tokenisierung sowie beim Parsen von CSV, Markdown, JSON und C Zwischenallokationen und Kopien vermeiden
  • Sentinels bleiben für die Aufrechterhaltung von Invarianten und manche Token-Suchen nützlich, und Konvertierungen zu bestehenden C- und OS-APIs sind weiterhin nötig; in den meisten Codebasen ist jedoch die Kombination aus längenbasierten Strings und Unveränderlichkeit an API-Grenzen einfacher und flexibler

Zeiger und Länge statt NUL-Terminierung speichern

  • C-Strings stellen ihre Grenzen durch einen Zeiger auf einen Zeichenstrom und ein abschließendes NUL-Byte dar
    • Unter den Speicher- und Performance-Beschränkungen der 1970er-Jahre mag das sinnvoll gewesen sein, heute gibt es kaum noch Gründe, daran festzuhalten
  • Die von modernen Sprachen und wichtigen Frameworks gewählte Alternative ist eine Struktur, die Datenzeiger und Größe gemeinsam speichert
struct String
{
    u8* data;
    u64 size;
};
  • String-Literale lassen sich mit sizeof(s) - 1 in ein String umwandeln; Operationen wie Vergleichen und Ausgeben nutzen die gespeicherte Größe direkt
  • Auch Arrays verlieren Informationen wie ihre Länge, sobald sie in Zeiger umgewandelt werden, und leiden dann unter ähnlichen Sicherheits- und Usability-Problemen wie Strings

Die Kosten des Wegwerfens von Längeninformation

  • Wird die Länge nicht gespeichert, muss der nutzende Code immer wieder strlen aufrufen oder Byte für Byte durchlaufen, was unnötige Arbeit und zusätzliche Komplexität erzeugt
  • Auch das Prüfen und Erzwingen der Länge zur Laufzeit wird langsamer und umständlicher; Debugger und Analysewerkzeuge können char*, char[N] und char*[N] nur schwer konsistent behandeln
  • Es gibt die Ansicht, dass ein beträchtlicher Teil der Speicherprobleme und Overflow-Bugs in C aus diesem Design stammt; dagegen wird eingewandt, dass ein Sentinel ausreiche
  • Strings unbekannter Länge ähneln eher einem sequenziellen Zugriffsmuster wie bei verketteten Listen als dem wahlfreien Zugriff auf Arrays
  • Befürworter der NUL-Terminierung sehen sequenzielle Verarbeitung als effizient an, weil sie eher Single-Pass-Algorithmen statt mehrerer Durchläufe begünstige
    • Viele Programmierer, einschließlich Anfänger, schreiben Code unter der Annahme, dass die Stringlänge billig zu ermitteln ist
    • Auch typische String-Routinen lassen sich natürlicher in einer Form schreiben, in der die Länge übergeben wird; durch wiederholte strlen-Aufrufe wird derselbe String im realen Code mehrfach durchlaufen
    • Die Annahme, dass weniger Durchläufe immer schneller sind, beruht auf einem Missverständnis der Funktionsweise moderner CPUs

Die unterschiedlichen Längenbegriffe von snprintf, sizeof und strlen

  • Die zwei Zahlen bei snprintf sehen wie dieselbe „Länge“ aus, haben aber entgegengesetzte Regeln dazu, ob NUL enthalten ist
int snprintf(char *str, size_t size, const char *format, ...);
  • Die Eingabe size muss den Platz für die NUL-Terminierung des Ausgabepuffers enthalten, der Rückgabewert dagegen bezeichnet die Länge des Strings, der ohne NUL-Byte erzeugt worden wäre
  • Bei jeder String-Funktion oder API müssen die folgenden Bedingungen separat geprüft werden
    • ob die Funktion das NUL-Byte selbst schreibt
    • ob beim Allokieren Platz für das NUL-Byte hinzugefügt werden muss
    • ob Größenargumente und Rückgabewerte das NUL-Byte enthalten
  • sizeof("some string") enthält das NUL-Byte, strlen("some string") dagegen nicht
  • Wenn literaler Code in laufzeitbasierten Code mit Zeigern umgeschrieben wird und dasselbe - 1 beibehalten wird, entsteht ein Bug, bei dem die Länge um eins zu kurz ist
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

const char *str = "some string";
size_t size = strlen(str) - 1;

Wiederholtes Überschreiben von NUL-Bytes in der Mitte

  • Wenn man mehrere snprintf-Rückgabewerte auf einen Offset addiert, um Strings aneinanderzuhängen, wird das von jedem Aufruf geschriebene NUL-Terminierungsbyte vom nächsten Aufruf überschrieben
int offset = 0;
offset += snprintf(ptr + offset, size - offset, "%d", my_int);
offset += snprintf(ptr + offset, size - offset, "%s", my_str);
offset += snprintf(ptr + offset, size - offset, "%f", my_flt);
  • Das Schreiben der Zwischen-Terminierungsbytes ist unnötig, auch wenn die Performance-Auswirkung selbst gering sein kann
  • Das größere Problem ist, dass dieses Verhalten nicht intuitiv ist und zu dem Missverständnis führt, snprintf würde nicht NUL-terminieren
  • In der Folge entsteht Code, der am Ende ptr[offset] = 0; hinzufügt; auch das ist unnötig und verstärkt dasselbe Missverständnis weiter

Der doppelte Zustand von leerem String und Null-String

  • Im NUL-terminierten Modell werden leerer String und Null-Zeiger wie unterschiedliche ungültige Zustände behandelt, sodass String-Verarbeitungscode beides prüfen muss
  • Auch Strings und Arrays in C# sind Referenztypen; liest man in einem Null-Zustand Length oder iteriert darüber, wird eine Ausnahme ausgelöst, was Sonderbehandlung erfordert
  • Eine gängige Gegenmaßnahme ist, statt Null immer leere Strings oder leere Arrays zu übergeben und zurückzugeben
    • Regeln wie String.IsNullOrEmpty, „Don’t Return Null“ und „Don’t Pass Null“ sind ebenfalls Mittel, um mit dieser Unterscheidung umzugehen
  • In einer Struktur mit Zeiger und Länge lässt sich mit size == 0 allein bestimmen, ob ein String leer ist
    • Der Zeiger kann Null oder eine gültige Adresse sein
    • Wenn man bis ans Ende eines Strings vorgedrungen ist oder auf einen leeren Teilstring innerhalb eines großen Strings zeigt, kann auch bei Länge 0 ein gültiger Zeiger vorhanden sein
    • Wenn erst nach Prüfung der Länge dereferenziert wird, wird selbst ein Zeiger auf bereits freigegebenen Speicher bei Länge 0 nicht berührt

Dieselbe Repräsentation für Binärdaten verwenden

  • Längenbasierte Strings hängen nicht von Sentinels ab und können daher auch beliebige Binärdaten mit NUL-Bytes sicher speichern
  • So wie ASCII-String-Funktionen auch mit UTF-8 funktionieren, lassen sich längenbasierte Operationen wie Scannen, Splitten, Trimmen und Slicing auch auf Byte-Arrays anwenden
  • Bei NUL-terminierten Binärformaten muss separat entschieden werden, ob das Terminierungsbyte gespeichert wird
    • Wird es gespeichert, ähneln Lese- und Schreibcode der üblichen String-Verarbeitung
    • Wird es nicht gespeichert, lassen sich Platz und Verarbeitungs-Overhead reduzieren; das ist einer der Hauptgründe für den Einsatz von Binärformaten
  • Ein Format, das sowohl Länge als auch Inhalt speichert und zusätzlich ein NUL-Byte anhängt, lässt dieselbe Mehrdeutigkeit wieder aufleben, weil erneut geprüft werden muss, ob die gespeicherte Länge das Terminierungsbyte enthält

Teilstrings ohne Allokation und Kopie

  • Erzwingt man NUL-Terminierung, muss auch am Ende von Ergebnissen aus Trimmen, Slicing, Splitten, Tokenisierung und Suche ein Terminierungsbyte stehen, wodurch neue Strings und Zwischenpuffer alloziert und kopiert werden
  • Längenbasierte Strings können einfach einen Zeiger auf einen Teil des Originals und eine Länge zurückgeben
String StrPrefix(String str, u64 size);
String StrPostfix(String str, u64 size);
String StrChop(String str, u64 size);
String StrSkip(String str, u64 size);
String Substr(String a, u64 min, u64 max);

String StrFindNeedle(String str, String needle);
String StrTrim(String str);
  • Lexer und Parser für CSV, Markdown, JSON und C können Slices des Eingabepuffers als Namen und Werte im Parse Tree speichern, ohne jedes Token zu kopieren
  • Nachgelagerter Code, der den Parse Tree nutzt, kann dieselben Slices weitergereicht bekommen und ohne zusätzliches Speichermanagement verarbeiten

Fälle, in denen Sentinels weiterhin nützlich sind

  • Sentinels können dabei helfen, Invarianten von Datenstrukturen aufrechtzuerhalten, und in manchen Situationen Performance-Vorteile bieten
  • Auf moderner Hardware und mit modernen Compilern sind die Performance-Vorteile bis auf Spezialfälle meist schwächer geworden, doch der Effekt, die Zahl der vom Programm zu verwaltenden Invarianten zu verringern, bleibt bestehen
  • Bei handgeschriebenen Token-Prüfungen sorgt ein NUL-Sentinel dafür, dass eine Schleife das aktuelle Byte sicher lesen kann
    • Lookahead wie s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' kann durch Bytereihenfolge und Kurzschlussauswertung früh scheitern
    • Längenbasierte Strings müssen unterscheiden, ob ein Token durch Whitespace endet oder die Eingabe selbst zu Ende ist; auch für Lookahead sind systematischere Grenzprüfungen nötig
  • Die meisten bestehenden C-Bibliotheken und OS-APIs verlangen NUL-terminierte Strings, sodass Konvertierungskosten entstehen
    • Unter Windows muss UTF-8 ohnehin bereits nach UTF-16 konvertiert werden, daher ist der Zusatzaufwand für das Anhängen eines NUL-Bytes vergleichsweise gering
    • Die von Betriebssystemen und Anbietern auferlegten Einschränkungen können überschätzt werden, während die Vorteile längenbasierter Strings unterschätzt werden können

Unveränderlichkeit auf String-APIs anwenden

  • Das vollständige API-Design und die Abstraktion einer ausgereiften String-Schicht liegen außerhalb des Rahmens, als zentrales Strukturprinzip wird jedoch Unveränderlichkeit empfohlen
  • Strings sollten nach ihrer Erstellung nicht verändert, sondern wie Konstanten behandelt werden; Funktionen, die Strings entgegennehmen und Strings zurückgeben, sollten diese Eigenschaft ebenfalls erhalten
  • Es genügt, Unveränderlichkeit über Funktionssignaturen und API-Grenzen zu garantieren
    • Innerhalb einer Funktion können bei Bedarf In-place-Änderungen oder andere prozedurale Verarbeitung verwendet werden
    • Im übergeordneten Informationsfluss erhält man die Vorteile der Unveränderlichkeit aus der funktionalen Programmierung, während die untergeordnete Implementierung die Flexibilität prozeduraler Programmierung behält
  • Diese Regel lässt sich auch ohne Erzwingung durch Sprache oder Laufzeit als Coding- und API-Konvention betreiben
  • Wenn String-Typen und Operationen klar unterschieden werden, ist der Aufwand zur Einhaltung der Regeln nicht groß; eine Codebasis kann selbst bestimmen, wo sie gelten und wann sie gelockert werden
  • Auch eine Programmiersprache ist eine API, daher muss man sich nicht nur auf die von Sprachgremien festgelegten Einschränkungen verlassen, sondern kann Regeln in der nötigen Granularität entwerfen

Implementierungsbeispiele für längenbasierte Strings

Einschränkungen anderer String-Repräsentationen

  • Flexible Array Member

    • Wie Redis SDS speichern sie aktuelle Länge und maximale Kapazität am Anfang einer Struktur und legen die Zeichendaten ab, indem das letzte Feld als flexibles Array Member deklariert wird
    • Probleme von C-Strings wie den O(n)-Scan von strlen sowie manuelle Konkatenation und Grenzverwaltung lassen sich dadurch vermeiden
    • Sie sind schwer direkt mit String-Literalen kompatibel zu machen und unterstützen nicht den zentralen Vorteil längenbasierter Strings: effiziente Teilstrings

  • Stretch Buffer

    • Stretch Buffer ähneln dynamischen Arrays; sie speichern Längen- und Kapazitäts-Header nicht in einer expliziten Struktur, sondern in einem separaten Bereich vor dem Zeiger
    • Zusätzlich zu den Nachteilen flexibler Array Member versehen sie praktisch jedes char* mit einer nahezu unsichtbaren Metadatenregel, und bei jeder sinnvollen String-Operation muss dieser Header Teil des API-Modells sein
    • Die Zeigerdarstellung bietet Typsicherheit und vermeidet Zugriffe über .str oder ->str, doch dieser Vorteil allein rechtfertigt die verborgenen Regeln kaum
    • Ein separates capacity-Feld ist bei dynamischen Arrays natürlich, vermischt bei Strings aber unterschiedliche Konzepte in einem Typ und verwischt die Unterscheidung zwischen Typen
    • Flexible Array Member können dasselbe Problem haben; ein Unterschied ist jedoch, dass man die anfängliche feste Größe als Kapazität verwenden und dynamisches Wachstum vermeiden kann

  • Pascal-Stil

    • Kurze Strings im Pascal-Stil verwenden üblicherweise ein Zeichenarray fester Größe von 256 Bytes und reservieren ein Byte für die Länge oder nutzen NUL-Terminierung
    • Unter den realen Speicher- und Hardwarebeschränkungen der Vergangenheit war das sinnvoll, heute stehen jedoch gute Arena-Memory-Allocation-Strategien zur Verfügung, sodass es außer in speziellen Situationen nicht geeignet ist

Warum längenbasierte Strings der Standard sein sollten

  • Die Vorteile längenbasierter Strings sind in einigen Communities und unter erfahrenen Programmierern bekannt, doch viele Entwickler haben eine solche Implementierung weiterhin nie in Betracht gezogen
  • Relevantes Material ist über viele Stellen verstreut, was es schwer machte, Längenverlust, Mehrdeutigkeit von Terminierungsbytes, Binärdatenverarbeitung, Teilstrings sowie Vor- und Nachteile von Sentinels und alternativen Implementierungen gemeinsam zu vergleichen
  • Macht man den Standard-String-Typ zu einer Slice-Form aus Zeiger und Länge, lassen sich Bewahrung von Grenzinformationen, Vereinfachung von Zuständen, Binärkompatibilität und Teilstrings ohne Allokation in einem Design lösen

Verwandte Beiträge

1 Kommentare

 
GN⁺ 4 시간 전
Meinungen auf Lobste.rs

  • Um Padding-Bytes zu vermeiden, wäre es meiner Ansicht nach besser, die Reihenfolge der Struct-Member so zu ändern:

    struct String  
{  
    u8* data;  
    u64 size;  
};

    statt:

    struct String  
{  
    u64 size;  
    u8* data;  
};

    • In Umgebungen mit 64-Bit-Pointern sind beide Felder gleich groß, daher gibt es unabhängig von der Reihenfolge kein Padding; in 32-Bit-Umgebungen ist ein u64, der größer ist als der Bereich, den ein Pointer adressieren kann, ohnehin Verschwendung.
      Verwendet man wie bei CHERI 128-Bit-Pointer, entsteht bei der ersten Anordnung Padding zur Ausrichtung zwischen data und size, bei der zweiten am Ende des Structs; am Ende wird also in beiden Fällen etwas Platz verschwendet.

    • Die richtige Definition nutzt ein Member mit variabler Array-Länge:

      typedef struct {  
  u64 len;  
  u8 buf[];  
} String;

  • Im C-Standard sind die Typen u8 und u64 nicht definiert; das ist Rust-Schreibweise.
    In einer 32-Bit-Umgebung die Länge mit u64 darzustellen, passt ebenfalls nicht, und der idiomatische Typ für Array-Größen in C ist size_t; natürlicher wäre also:

    struct String  
{  
    char* data;  
    size_t size;  
};

    Die Person, die den Text geschrieben hat, oder das LLM, das ihn erzeugt hat, scheint C nicht richtig zu kennen.

    • Viele C-Projekte definieren u8 und u64 per typedef und verwenden sie; das ist eine sehr verbreitete Praxis.
      Viele empfinden die Standardnamen uintN_t als umständlich, einige große Projekte sind älter als dieser Standard, und auch der Linux-Kernel verwendet solche Aliasse.
      Eher zeigt diese Kritik, dass man mit C-Projekten nicht vertraut ist.

  • Wenn man länger als ein paar Monate C oder C++ geschrieben hat, ist die Übergabe von Pointer und Länge zusammen doch längst bekannt, oder?
    Fast jede moderne C-Codebasis endet irgendwann damit, einen Daten-Pointer zusammen mit einer Länge zu übergeben oder eine eigene String-Bibliothek zu haben.

    • Ob die Länge gespeichert wird, ist nur eines der Probleme von C-Strings; auch beim Lifetime-Management gibt es viele Stolperfallen.
      Das moderne C++-std::string_view macht ausdrücklich klar: „Du darfst diesen String betrachten, ihn aber nicht verändern oder behalten“, und reduziert dadurch Bugs erheblich.
      Bei APIs, die C-Strings entgegennehmen, sind solche Einschränkungen nur ein Versprechen in der Dokumentation.

  • Der eigentliche Fehler liegt meiner Ansicht nach nicht darin, ob eine Länge gespeichert wird oder ob es eine Nullterminierung gibt, sondern im Konzept String selbst, das viel zu breit ist, um in beliebigen Kontexten eine klare Bedeutung zu haben.
    Strings werden für alle möglichen Zwecke verwendet, weit über ein einfaches Zeichen-Array hinaus; selbst das Wort „Zeichen“ ist dabei eine übermäßige Vereinfachung, wie der Physikerwitz von der kugelförmigen Kuh im Vakuum.
    Schon bei der „Länge“ ist unklar, ob damit die Anzahl der Graphem-Cluster, der Codepoints oder die Gesamtzahl der Bytes gemeint ist.
    Man muss auch unterscheiden, welche Kodierung verwendet wird, ob der String Nutzern angezeigt wird und lokalisiert werden muss, ob er bereinigt wurde oder ob er ein unteilbarer Wert ist, der wie ein Map-Key keinen Grund zur Änderung hat.
    Aus dieser Perspektive will man den String-Typ einer üblichen Implementierung eigentlich nicht mehr.

    • Manchmal wird beklagt, Rust habe zu viele String-Typen, aber einige davon dienen dazu, solche Informationen im Typsystem abzubilden.
      Soweit ich weiß, nennt keine Bibliothek die Anzahl der Graphem-Cluster einfach „Länge“.
      Einige Probleme lassen sich dadurch lösen, dass man UTF-8 als Standardkodierung festlegt und für andere Kodierungen oder Byte-Arrays eigene Typen verwendet; das meiste lässt sich im Typsystem ausdrücken.

  • Soweit ich weiß, hat C kein sprachseitiges String-Konzept, wie es die meisten modernen Sprachen bieten.
    String-Manipulation wird nicht von der Sprache selbst bereitgestellt, sondern von der Standardbibliothek.
    K&R, 2. Auflage, erklärt, dass C eine relativ Low-Level-Sprache ist, die näher an Objekten liegt, mit denen Computer direkt umgehen, etwa Zeichen, Zahlen und Adressen, und keine Operationen bereitstellt, die komplexe Objekte wie Strings, Mengen, Listen oder Arrays als Ganzes direkt manipulieren.
    Das Fehlen solcher Funktionen mag wie ein großer Mangel wirken, doch weil die Sprache klein gehalten wurde, lässt sie sich knapp beschreiben und schnell lernen; außerdem kann ein Programmierer die gesamte Sprache verstehen und im Alltag verwenden.
    Um zu verstehen, warum C so entworfen wurde und warum heute selbstverständlich wirkende moderne Funktionen fehlen, empfehle ich dringend, das Vorwort und die Einleitung der 2. Auflage von K&R zu lesen.

    • Allerdings sind Strings in einem eingeschränkten Sinn auch Teil der C-Sprache, weil Typ und Speicherlayout von String-Literalen die Form der Bibliothek bestimmen.
      Das unterscheidet sich auch nicht wesentlich von der Trennung zwischen Sprache und Bibliothek in Low-Level-Sprachen wie Rust.

  • Als Serialisierungsformat gibt es Vorschläge wie https://cr.yp.to/proto/netstrings.txt, und es gibt auch Ansätze, die sogar komplexe Strukturen behandeln, wie https://web.archive.org/web/20230305073119/….
    Aber offenbar sehen sie zu einfach aus, um sicher geparst zu werden, sodass die leidenschaftlichen Anhänger von XML, JSON, YAML, Protocol Buffers und Co. weiter gut beschäftigt bleiben.