Chaînes C : une erreur qui dure depuis 50 ans

 (longtran2904.substack.com)
1 points par GN⁺ 4 시간 전 | 1 commentaires | Partager sur WhatsApp
  • Les chaînes terminées par NUL de C ne conservent pas l’information de longueur, ce qui entraîne des parcours répétés et des erreurs de limites ; aujourd’hui, des chaînes fondées sur une longueur, qui stockent ensemble un pointeur et une taille, conviennent mieux comme conception par défaut
  • Sans longueur explicite, les appels à strlen et les parcours octet par octet se répètent, et les règles d’inclusion de l’octet de terminaison diffèrent entre snprintf, sizeof et strlen, ce qui rend le code plus difficile à écrire et à relire
  • Les chaînes basées sur une longueur traitent systématiquement la chaîne vide comme size == 0 et permettent d’appliquer telles quelles les opérations de recherche, découpage et slicing à des données binaires arbitraires, y compris contenant des octets NUL
  • Elles peuvent renvoyer des sous-chaînes pointant vers une partie de la mémoire d’origine, ce qui évite des allocations et copies intermédiaires lors du rognage, de la recherche, de la tokenisation et du parsing de CSV, Markdown, JSON ou C
  • Les sentinelles restent utiles pour maintenir des invariants et pour certaines recherches de tokens, et les conversions avec les API C et OS existantes restent nécessaires ; mais, dans la plupart du code, combiner des chaînes basées sur une longueur avec l’immutabilité aux frontières d’API est plus simple et plus flexible

Stocker un pointeur et une longueur plutôt qu’une terminaison NUL

  • Une chaîne C représente ses limites par un pointeur vers un flux de caractères et un dernier octet NUL
    • Cela pouvait être raisonnable avec les contraintes de mémoire et de performance des années 1970, mais il n’y a presque plus de raison de conserver ce modèle aujourd’hui
  • L’alternative adoptée par les langages modernes et les grands frameworks consiste en une structure stockant ensemble un pointeur vers les données et une taille
struct String
{
    u8* data;
    u64 size;
};
  • La longueur d’un littéral de chaîne peut être calculée avec sizeof(s) - 1 pour créer un String, et les opérations comme la comparaison ou l’affichage utilisent directement la taille stockée
  • Les tableaux perdent eux aussi des informations comme leur longueur lorsqu’ils sont convertis en pointeurs, ce qui crée des problèmes de sécurité et d’ergonomie similaires à ceux des chaînes

Le coût de jeter l’information de longueur

  • Si la longueur n’est pas stockée, chaque code utilisateur doit appeler strlen à répétition ou parcourir les octets un par un, ce qui augmente le travail inutile et la complexité
  • Vérifier et imposer la longueur à l’exécution devient aussi plus lent et plus pénible, et les débogueurs comme les outils d’analyse ont du mal à traiter de manière cohérente char*, char[N] et char*[N]
  • Certains estiment qu’une grande partie des problèmes mémoire et des bugs de débordement de C provient de cette conception, même si d’autres répondent qu’une sentinelle suffit
  • Une chaîne dont on ne connaît pas la longueur se rapproche davantage d’un modèle d’accès séquentiel, comme une liste chaînée, que de l’accès aléatoire d’un tableau
  • Les défenseurs de la terminaison NUL considèrent que le traitement séquentiel favorise des algorithmes en un seul passage plutôt qu’en plusieurs passages, et donc l’efficacité
    • Beaucoup de programmeurs, débutants compris, écrivent du code en supposant que la longueur d’une chaîne est peu coûteuse à obtenir
    • Les routines de chaîne courantes s’écrivent aussi plus naturellement lorsque la longueur est fournie, et les appels répétés à strlen font qu’en pratique le même texte est parcouru plusieurs fois
    • L’idée selon laquelle moins de passages signifie toujours plus rapide résulte d’une mauvaise compréhension du fonctionnement des CPU modernes

Les différentes longueurs que signifient snprintf, sizeof et strlen

  • Les deux entiers de snprintf semblent désigner la même « longueur », mais leurs règles d’inclusion du NUL sont opposées
int snprintf(char *str, size_t size, const char *format, ...);
  • L’entrée size doit inclure l’espace pour la terminaison NUL du buffer de sortie, tandis que la valeur de retour indique la longueur de la chaîne qui aurait été produite, sans l’octet NUL
  • À chaque utilisation d’une fonction ou d’une API liée aux chaînes, il faut vérifier séparément les conditions suivantes
    • si la fonction écrit elle-même l’octet NUL
    • s’il faut ajouter de l’espace pour l’octet NUL à la taille d’allocation
    • si l’argument de taille et la valeur de retour incluent l’octet NUL
  • sizeof("some string") inclut l’octet NUL, mais strlen("some string") l’exclut
  • Si l’on transforme du code basé sur des littéraux en code basé sur des pointeurs à l’exécution tout en conservant le même - 1, on introduit un bug de longueur trop courte d’une unité
#define TEST_STRING "some string"
size_t size = sizeof(TEST_STRING) - 1;

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

Réécrire à répétition les octets NUL intermédiaires

  • Si l’on concatène des chaînes en ajoutant plusieurs valeurs de retour de snprintf à un décalage, chaque appel écrit un octet de terminaison NUL que l’appel suivant écrase
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);
  • Écrire ces octets de terminaison intermédiaires est inutile, même si son impact sur les performances peut rester faible
  • Le problème plus important est que ce comportement n’est pas intuitif et fait naître l’idée erronée que snprintf ne termine pas par NUL
  • Il en résulte du code qui ajoute ptr[offset] = 0; à la fin, une opération elle aussi inutile et qui renforce encore ce malentendu

Le double état de la chaîne vide et de la chaîne nulle

  • Dans le modèle à terminaison NUL, la chaîne vide et le pointeur nul sont traités comme deux états invalides distincts, que le code de traitement des chaînes doit tous deux vérifier
  • Les chaînes et tableaux de C# étant aussi des types référence, lire Length ou les parcourir à l’état nul déclenche une exception et nécessite un traitement séparé
  • Une réponse courante consiste à toujours passer et renvoyer une chaîne ou un tableau vide plutôt que null
    • Des règles comme String.IsNullOrEmpty, « Don’t Return Null » ou « Don’t Pass Null » servent aussi à gérer cette distinction
  • Avec une structure contenant un pointeur et une longueur, l’état de chaîne vide se détermine simplement par size == 0
    • Le pointeur peut être nul ou être une adresse valide
    • Si l’on a atteint la fin de la chaîne ou si l’on pointe vers une sous-chaîne vide à l’intérieur d’une grande chaîne, le pointeur peut rester valide même avec une longueur de 0
    • Tant que l’on ne déréférence qu’après avoir vérifié la longueur, même un pointeur vers une mémoire déjà libérée ne sera pas accédé lorsque la longueur vaut 0

Utiliser la même représentation pour les données binaires

  • Les chaînes basées sur une longueur ne dépendent pas d’une sentinelle et peuvent donc stocker en toute sécurité des données binaires arbitraires contenant des octets NUL
  • Tout comme les fonctions de chaînes ASCII fonctionnent aussi avec UTF-8, les opérations basées sur la longueur — scan, split, trim, slicing — peuvent s’appliquer à des tableaux d’octets
  • Un format binaire terminé par NUL doit décider séparément s’il stocke l’octet de terminaison
    • S’il le stocke, le code de lecture et d’écriture ressemble davantage au traitement classique des chaînes
    • S’il ne le stocke pas, il peut réduire l’espace et le surcoût de traitement, ce qui est l’une des principales raisons d’utiliser un format binaire
  • Un format qui stocke à la fois la longueur, le contenu et un octet NUL final doit de nouveau préciser si la longueur enregistrée inclut l’octet de terminaison, ce qui réintroduit la même ambiguïté

Des sous-chaînes sans allocation ni copie

  • Imposer la terminaison NUL oblige aussi à placer un octet de terminaison à la fin des résultats de trim, slicing, split, tokenisation ou recherche, ce qui force à allouer et copier de nouvelles chaînes et des buffers intermédiaires
  • Une chaîne basée sur une longueur peut simplement renvoyer un pointeur vers une partie de l’original et une longueur
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);
  • Les lexers et parsers pour CSV, Markdown, JSON ou C peuvent conserver chaque token sous forme de slice du buffer d’entrée comme nom ou valeur dans l’arbre de parsing, sans le copier
  • Le code qui consomme ensuite l’arbre de parsing peut recevoir ces mêmes slices et les traiter sans gestion mémoire supplémentaire

Quand les sentinelles restent utiles

  • Les sentinelles peuvent maintenir des invariants de structures de données et offrir dans certains cas des avantages de performance
  • Sur les matériels et compilateurs modernes, leurs gains de performance se sont pour l’essentiel affaiblis hors cas particuliers, mais leur effet de réduction du nombre d’invariants à gérer subsiste
  • Dans des tests de tokens écrits à la main, une sentinelle NUL permet à la boucle de lire l’octet courant en toute sécurité
    • Un lookahead comme s[i] == 'f' && s[i+1] == 'o' && s[i+2] == 'r' peut échouer tôt grâce à l’ordre des octets et à l’évaluation court-circuitée
    • Les chaînes basées sur une longueur doivent distinguer le cas où le token se termine par un espace de celui où l’entrée elle-même se termine, et le lookahead exige aussi des vérifications de limites plus systématiques
  • Comme la plupart des bibliothèques C existantes et des API d’OS exigent des chaînes terminées par NUL, des coûts de conversion apparaissent
    • Sous Windows, UTF-8 doit déjà être converti en UTF-16, donc le coût d’ajout d’un octet NUL est relativement faible
    • Les contraintes imposées par les OS et les fournisseurs peuvent être surestimées, tandis que les bénéfices des chaînes basées sur une longueur peuvent être sous-estimés

Appliquer l’immutabilité aux API de chaînes

  • La conception complète d’une couche de chaînes aboutie et de ses abstractions dépasse le cadre du sujet, mais le principe structurel clé recommandé est l’immutabilité
  • Une chaîne, une fois créée, est traitée comme une constante sans modification de son contenu, et les fonctions qui prennent et renvoient des chaînes doivent conserver cette propriété
  • Il suffit de garantir l’immutabilité dans les signatures de fonctions et aux frontières d’API
    • À l’intérieur d’une fonction, on peut au besoin modifier sur place ou utiliser d’autres traitements procéduraux
    • Dans le flux d’information de haut niveau, on obtient les bénéfices d’immutabilité de la programmation fonctionnelle, tout en conservant dans l’implémentation bas niveau la flexibilité de la programmation procédurale
  • Cette règle peut être appliquée comme convention de codage et d’API, même si le langage ou le runtime ne l’impose pas
  • Si l’on distingue clairement les types de chaînes et les opérations, maintenir la règle n’est pas très coûteux, et chaque codebase peut décider elle-même de son périmètre d’application et des moments où l’assouplir
  • Un langage étant aussi une API, il n’est pas nécessaire de s’en remettre uniquement aux contraintes fixées par les comités de langage : on peut concevoir les règles avec la granularité requise

Exemples d’implémentations de chaînes basées sur une longueur

Les limites d’autres représentations de chaînes

  • Membres de tableau flexibles

    • Comme le SDS de Redis, cette approche stocke la longueur courante et la capacité maximale au début de la structure, puis déclare le dernier champ comme membre de tableau flexible pour y placer les données de caractères
    • Elle évite les problèmes des chaînes C, comme le scan O(n) de strlen et la concaténation ou la gestion manuelle des limites
    • Elle est difficilement compatible directement avec les littéraux de chaîne et ne prend pas en charge les sous-chaînes efficaces, qui sont l’un des principaux avantages des chaînes basées sur une longueur

  • Stretch buffers

    • Les stretch buffers ressemblent à des tableaux dynamiques : ils stockent les en-têtes de longueur et de capacité dans une zone séparée située avant le pointeur, plutôt que dans une structure explicite
    • En plus des inconvénients de l’approche à membre de tableau flexible, ils imposent à tous les char* une règle de métadonnées presque invisible, et chaque opération significative sur les chaînes doit utiliser cet en-tête comme une partie du modèle d’API
    • La représentation par pointeur offre de la sécurité de type et évite les accès .str ou ->str, mais cet avantage ne suffit pas à justifier des règles cachées
    • Un champ capacity séparé est naturel pour un tableau dynamique, mais, dans une chaîne, il mélange des concepts différents dans un même type et brouille la distinction entre types
    • Le membre de tableau flexible peut avoir le même problème, avec toutefois la différence qu’une taille fixe initiale peut servir de capacité et éviter l’extension dynamique

  • Style Pascal

    • Les chaînes courtes de style Pascal utilisent généralement un tableau de caractères de taille fixe de 256 octets, en réservant un octet pour la longueur ou en utilisant une terminaison NUL
    • C’était pertinent avec les contraintes réelles de mémoire et de matériel d’autrefois, mais aujourd’hui on peut utiliser de bonnes stratégies d’allocation mémoire par arènes, ce qui rend ce modèle inadapté sauf dans des situations particulières

Pourquoi les chaînes basées sur une longueur devraient être le choix par défaut

  • Les avantages des chaînes basées sur une longueur sont connus dans certaines communautés et chez des programmeurs expérimentés, mais beaucoup de développeurs n’ont encore jamais envisagé ce type d’implémentation
  • Les ressources sur le sujet sont dispersées, ce qui rendait difficile de comparer ensemble la perte de longueur, l’ambiguïté de l’octet de terminaison, le traitement du binaire, les sous-chaînes, les avantages et limites des sentinelles, ainsi que les implémentations alternatives
  • Faire du type chaîne par défaut une slice composée d’un pointeur et d’une longueur permet de résoudre dans une seule conception la préservation des informations de limites, la simplification des états, la compatibilité binaire et les sous-chaînes sans allocation

À lire aussi

1 commentaires

 
GN⁺ 4 시간 전
Avis sur Lobste.rs

  • Pour éviter les octets de padding, il vaudrait mieux, à mon avis, changer l’ordre des membres de la structure comme suit

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

    au lieu de :

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

    • Dans un environnement à pointeurs 64 bits, les deux champs ont la même taille, donc il n’y a pas de padding quel que soit l’ordre ; en 32 bits, un u64 plus grand que ce qu’un pointeur peut adresser est lui-même du gaspillage
      Avec des pointeurs 128 bits comme dans CHERI, la première disposition ajoute du padding d’alignement entre data et size, et la seconde à la fin de la structure ; au final, on gaspille donc un peu d’espace

    • La bonne définition consiste à utiliser un membre tableau de longueur variable

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

  • La norme C ne définit pas les types u8 et u64 ; c’est une notation à la Rust
    Représenter une longueur avec u64 en 32 bits n’est pas très approprié non plus, et en C le type idiomatique pour exprimer la taille d’un tableau est size_t, il serait donc plus naturel d’écrire :

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

    La personne qui a écrit l’article, ou le LLM qui l’a généré, ne semble pas bien connaître le C

    • Beaucoup de projets C définissent et utilisent u8 et u64 via des typedef, et c’est une pratique très courante
      Beaucoup trouvent aussi les noms uintN_t de la norme fastidieux, certains grands projets sont même plus anciens que cette norme, et le noyau Linux utilise également ce type d’alias
      Cette critique révèle plutôt un manque de familiarité avec les projets C

  • Si l’on a écrit du C ou du C++ pendant plus de quelques mois, le fait de passer ensemble un pointeur et une longueur n’est-il pas déjà bien connu ?
    Presque toutes les bases de code C modernes finissent par passer ensemble un pointeur de données et une longueur, ou par disposer de leur propre bibliothèque de chaînes

    • Le stockage de la longueur n’est qu’un des problèmes des chaînes C ; la gestion de la durée de vie pose aussi beaucoup de soucis
      Le std::string_view du C++ moderne explicite le sens de « on peut voir cette chaîne, mais on ne doit ni la modifier ni la conserver », ce qui réduit fortement les bugs
      Dans les API qui acceptent des chaînes C, cette contrainte n’est qu’une promesse documentaire

  • La vraie erreur n’est pas le stockage de la longueur ni la terminaison par NUL, mais le concept même de String, trop vaste pour avoir un sens dans n’importe quel contexte
    Les chaînes servent à toutes sortes d’usages au-delà d’un simple tableau de caractères, et même le mot « caractère » est une simplification excessive, comme la blague de physique sur la vache sphérique dans le vide
    On ne sait même pas si la « longueur » désigne le nombre de grappes de graphèmes, de points de code ou le nombre total d’octets
    Il faut aussi distinguer l’encodage, le fait que la chaîne soit exposée à l’utilisateur et doive être localisée, qu’elle ait été assainie, ou qu’elle soit une valeur indivisible sans raison d’être modifiée, comme une clé de map
    Vu sous cet angle, on finit par ne plus vouloir du type chaîne des implémentations habituelles

    • On se plaint parfois que Rust a trop de types de chaînes, mais certains servent précisément à porter ce genre d’informations dans le système de types
      À ma connaissance, aucune bibliothèque n’appelle simplement « longueur » le nombre de grappes de graphèmes
      Définir UTF-8 comme encodage par défaut et utiliser des types distincts pour les autres encodages ou les tableaux d’octets permet de résoudre une partie du problème ; la plupart des cas peuvent être exprimés par le système de types

  • À ma connaissance, C n’a pas de concept de chaîne au niveau du langage comme en proposent la plupart des langages modernes
    La manipulation de chaînes est fournie par la bibliothèque standard, pas par le langage lui-même
    La 2e édition de K&R explique que C est un langage relativement bas niveau, proche des objets que l’ordinateur manipule directement, comme les caractères, les nombres et les adresses, et qu’il ne fournit pas d’opérations manipulant directement des objets composés entiers comme les chaînes, ensembles, listes ou tableaux
    L’absence de ces fonctionnalités peut sembler être un gros défaut, mais le fait d’avoir gardé le langage petit permet de le décrire brièvement et de l’apprendre rapidement, avec l’avantage qu’un programmeur peut comprendre l’ensemble du langage et l’utiliser au quotidien
    Pour comprendre pourquoi C a été conçu ainsi et pourquoi des fonctionnalités modernes tenues pour acquises n’y figurent pas, je recommande vivement de lire la préface et l’introduction de la 2e édition de K&R

    • Cela dit, dans le sens limité où le type des littéraux de chaînes et leur disposition en mémoire déterminent la forme de la bibliothèque, les chaînes font aussi partie du langage C
      Ce n’est pas très différent de la séparation entre langage et bibliothèque dans des langages bas niveau comme Rust

  • Il existe des propositions de formats de sérialisation comme https://cr.yp.to/proto/netstrings.txt, ainsi que des approches qui gèrent même des structures complexes, comme https://web.archive.org/web/20230305073119/…
    Mais elles semblent trop simples à parser de manière sûre, si bien que les fervents partisans de XML, JSON, YAML, Protocol Buffers, etc. ont pu continuer à avoir du pain sur la planche