Il y a eu beaucoup de suppositions (légèrement ou entièrement) erronées dans les commentaires sur certains détails / le contexte de ce projet.
Vous êtes en train de regarder l'implémentation optimisée du fallback C de la glibc. (Pour les ISA qui n'ont pas d'implémentation asm écrite à la main) . Ou une ancienne version de ce code, qui se trouve toujours dans l'arbre source de la glibc. https://code.woboq.org/userspace/glibc/string/strlen.c.html est un navigateur de code basé sur l'arbre git actuel de la glibc. Apparemment, il est encore utilisé par quelques cibles de la glibc courante, dont MIPS. (Merci @zwol).
Sur les ISA populaires comme x86 et ARM, glibc utilise des asm écrits à la main.
L'intérêt de changer quoi que ce soit à ce code est donc plus faible que vous ne le pensez.
Ce code bithack ( https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord ) n'est pas ce qui fonctionne réellement sur votre serveur/ordinateur/ordinateur portable/smartphone. C'est mieux qu'une boucle naïve d'octet par octet, mais même ce bithack est assez mauvais comparé à l'asm efficace pour les CPU modernes (en particulier x86 où AVX2 SIMD permet de vérifier 32 octets avec quelques instructions, permettant 32 à 64 octets par cycle d'horloge dans la boucle principale si les données sont chaudes dans le cache L1d sur les CPU modernes avec une charge vectorielle et un débit ALU de 2/clock. c'est-à-dire pour des chaînes de taille moyenne où l'overhead de démarrage ne domine pas).
La glibc utilise des astuces de liaison dynamique pour résoudre strlen à une version optimale pour votre processeur, donc même dans x86 il y a une Version SSE2 (vecteurs de 16 octets, base de référence pour x86-64) et une Version AVX2 (vecteurs de 32 octets).
Le x86 dispose d'un transfert de données efficace entre les registres vectoriels et les registres à usage général, ce qui le rend particulièrement adapté à l'utilisation de la SIMD pour accélérer les fonctions sur des chaînes de longueur implicite où le contrôle de la boucle dépend des données. pcmpeqb / pmovmskb permet de tester 16 octets distincts à la fois.
La glibc possède une version AArch64 comme celle-ci en utilisant AdvSIMD et une version pour les processeurs AArch64 où les registres vectoriels->GP bloquent le pipeline, de sorte qu'il n'y a pas d'erreur. utiliser réellement ce bithack . Mais utilise le comptage de zéros en tête pour trouver l'octet dans le registre une fois qu'il obtient un résultat, et profite de l'efficacité des accès non alignés de AArch64 après avoir vérifié le passage de page.
Voir aussi : Pourquoi ce code est-il 6,5 fois plus lent avec les optimisations activées ? a plus de détails sur ce qui est rapide ou lent dans l'asm x86 pour strlen avec un grand tampon et une implémentation asm simple qu'il serait bon que gcc sache comment mettre en ligne. (Certaines versions de gcc ont imprudemment mis en ligne rep scasb ce qui est très lent, ou un bithack de 4 octets à la fois comme ceci. Donc la recette inline-strlen de GCC doit être mise à jour ou désactivée).
L'Asm n'a pas de "comportement indéfini" à la C. il est possible d'accéder aux octets de la mémoire comme on le souhaite, et un chargement aligné qui inclut n'importe quel octet valide ne peut pas faire défaut. La protection de la mémoire se fait avec une granularité de page alignée ; les accès alignés plus étroits ne peuvent pas traverser une frontière de page. Est-il possible de lire au-delà de la fin d'un tampon dans la même page sur x86 et x64 ? Le même raisonnement s'applique au code machine que ce hack C fait créer par les compilateurs pour une implémentation non-inline autonome de cette fonction.
Lorsqu'un compilateur émet du code pour appeler une fonction non-inline inconnue, il doit supposer que cette fonction modifie toutes les variables globales et toute la mémoire sur laquelle elle pourrait éventuellement avoir un pointeur. En d'autres termes, tout, sauf les locales dont l'adresse n'a pas été échappée, doit être synchronisé en mémoire lors de l'appel. Ceci s'applique aux fonctions écrites en asm, évidemment, mais aussi aux fonctions des bibliothèques. Si vous n'activez pas l'optimisation au moment de la liaison, cela s'applique même aux unités de traduction séparées (fichiers sources).
Pourquoi c'est sûr dans le cadre de la glibc mais pas autrement.
Le facteur le plus important est que cette strlen ne peut pas s'insérer dans un autre élément. Ce n'est pas sûr pour ça ; ça contient UB à crénelage strict (lecture char données par le biais d'un unsigned long* ). char* est autorisé à aliaser toute autre chose mais l'inverse est pas vrai .
Il s'agit d'une fonction de bibliothèque pour une bibliothèque compilée en avance sur le temps (glibc). Il ne sera pas intégré dans les appelants avec une optimisation du temps de liaison. Cela signifie qu'il suffit de compiler en code machine sûr pour une version autonome de strlen . Il n'a pas besoin d'être portable / sûr C.
La bibliothèque GNU C doit seulement être compilée avec GCC. Apparemment, c'est non supporté pour le compiler avec clang ou ICC, même s'ils supportent les extensions GNU. GCC est un compilateur en avance sur le temps qui transforme un fichier source C en un fichier objet de code machine. Il ne s'agit pas d'un interprète, donc à moins qu'il ne s'aligne au moment de la compilation, les octets en mémoire ne sont que des octets en mémoire. Autrement dit, l'aliasing strict d'UB n'est pas dangereux lorsque les accès de types différents se produisent dans des fonctions différentes qui ne s'alignent pas les unes sur les autres.
Rappelez-vous que strlen Le comportement de la personne est défini par la norme ISO C. Le nom de cette fonction est précisément partie de la mise en œuvre. Les compilateurs comme GCC traitent même le nom comme une fonction intégrée, à moins que vous n'utilisiez la fonction -fno-builtin-strlen donc strlen("foo") peut être une constante de temps de compilation 3 . La définition dans la bibliothèque est uniquement utilisé lorsque gcc décide d'émettre un appel à cette fonction au lieu de mettre en ligne sa propre recette ou autre.
Quand l'UB n'est pas visible au compilateur au moment de la compilation, vous obtenez un code machine sain. Le code machine doit fonctionner pour le cas no-UB, et même si vous recherché il n'y a aucun moyen pour l'asm de détecter quels types l'appelant a utilisé pour mettre des données dans la mémoire pointée.
La glibc est compilée en une bibliothèque statique ou dynamique autonome qui ne peut pas être intégrée dans un programme avec une optimisation au moment de la liaison. Les scripts de compilation de la glibc ne créent pas de "grosses" bibliothèques statiques contenant le code machine + la représentation interne GIMPLE de gcc pour l'optimisation au moment de la liaison lors de l'intégration dans un programme. (c'est-à-dire libc.a ne participera pas à -flto l'optimisation du temps de liaison dans le programme principal). Construire la glibc de cette façon serait potentiellement dangereux. sur les cibles qui utilisent réellement cette .c .
En fait, comme le commente @zwol, LTO ne peut pas être utilisé lors de la construction de la glibc. lui-même Il n'a pas été possible d'utiliser le code de la glibc, à cause d'un code "fragile" comme celui-ci, qui pourrait se briser si l'inlining entre les fichiers sources de la glibc était possible. (Il y a quelques utilisations internes de strlen par exemple, peut-être dans le cadre de l'initiative de l'Union européenne en faveur de l'environnement. printf mise en œuvre)
Ce site strlen fait quelques hypothèses :
-
CHAR_BIT est un multiple de 8 . Vrai sur tous les systèmes GNU. POSIX 2001 garantit même CHAR_BIT == 8 . (Cela semble sûr pour les systèmes avec CHAR_BIT= 16 ou 32 comme certains DSP ; la boucle prologue non alignée effectuera toujours 0 itération si la boucle est ouverte. sizeof(long) = sizeof(char) = 1 car chaque pointeur est toujours aligné et p & sizeof(long)-1 est toujours égal à zéro). Mais si vous aviez un jeu de caractères non-ASCII où les caractères ont une largeur de 9 ou 12 bits, 0x8080... n'est pas le bon modèle.
- (peut-être)
unsigned long est de 4 ou 8 octets. Ou peut-être que cela fonctionnerait pour n'importe quelle taille d'octets. unsigned long jusqu'à 8, et il utilise un assert() pour vérifier cela.
Ces deux-là ne sont pas des UB possibles, c'est juste de la non-portabilité pour certaines implémentations C. Ce code est (ou était) partie de l'implémentation C sur les plateformes où elle fonctionne, donc c'est bien.
L'hypothèse suivante est le potentiel C UB :
-
Un chargement aligné qui contient des octets valides ne peut pas être défectueux. et est sûr tant que vous ignorez les octets en dehors de l'objet que vous voulez réellement. (Vrai en asm sur tous les systèmes GNU, et sur tous les processeurs normaux parce que la protection de la mémoire se fait avec une granularité de page alignée. Est-il possible de lire au-delà de la fin d'un tampon dans la même page sur x86 et x64 ? sûr en C lorsque l'UB n'est pas visible au moment de la compilation. Sans inlining, c'est le cas ici. Le compilateur ne peut pas prouver que la lecture au-delà de la première ligne de l'équation
0 est UB ; il pourrait s'agir d'un C char[] contenant {1,2,0,3} par exemple)
C'est ce dernier point qui permet de lire sans risque la fin d'un objet C ici. C'est à peu près sûr même en inlining avec les compilateurs actuels parce que je pense qu'ils ne traitent pas actuellement ce qui implique qu'un chemin d'exécution est inaccessible. Mais de toute façon, l'aliasing strict est déjà un obstacle si vous laissez cela en ligne.
Alors vous auriez des problèmes comme l'ancien système non sécurisé du noyau Linux. memcpy macro CPP qui utilisait l'encodage par pointeur pour unsigned long ( gcc, strict-aliasing, et histoires d'horreur ). (Linux moderne compile avec -fno-strict-aliasing au lieu de faire attention à may_alias attributs.)
Ce site strlen date de l'époque où l'on pouvait s'en tirer avec ce genre de choses en général. Avant GCC3, c'était pratiquement sans danger, même sans l'avertissement "seulement quand on ne fait pas d'inlining".
L'UB qui n'est visible que lorsque l'on regarde au-delà des limites de l'appel et du retour ne peut pas nous faire de mal. (par exemple, appeler ceci sur un char buf[] plutôt que sur un tableau de unsigned long[] à un const char* ). Une fois que le code machine est figé, il ne s'agit plus que de traiter des octets en mémoire. Un appel de fonction non inline doit supposer que le destinataire lit tout ou partie de la mémoire.
Écrire ceci en toute sécurité, sans anticrénelage strict UB
Le site Attribut de type GCC may_alias donne à un type le même traitement d'alias que celui accordé à char* . (Proposé par @KonradBorowsk). Les en-têtes de GCC l'utilisent actuellement pour les types vectoriels SIMD x86 tels que __m128i afin que vous puissiez toujours faire en toute sécurité _mm_loadu_si128( (__m128i*)foo ) . (Voir Le `reinterpret_cast` entre le pointeur vectoriel SIMD matériel et le type correspondant est-il un comportement non défini ? pour plus de détails sur ce que cela signifie et ne signifie pas).
strlen(const char *char_ptr)
{
typedef unsigned long __attribute__((may_alias)) aliasing_ulong;
// handle unaligned startup somehow, e.g. check for page crossing then check an unaligned word
// else check single bytes until an alignment boundary.
aliasing_ulong *longword_ptr = (aliasing_ulong *)char_ptr;
for (;;) {
// alignment still required, but can safely alias anything including a char[]
unsigned long ulong = *longword_ptr++;
...
}
}
Vous pouvez utiliser aligned(1) pour exprimer un type avec alignof(T) = 1 .
typedef unsigned long __attribute__((may_alias, aligned(1))) unaligned_aliasing_ulong; . Cela pourrait être utile pour la partie non alignée de strlen, si vous ne faites pas simplement un caractère à la fois jusqu'à la première limite d'alignement. (La boucle principale doit être alignée pour que vous ne soyez pas en faute si le terminateur est juste avant une page non alignée).
Une manière portable d'exprimer une charge d'aliasing en ISO est avec memcpy ce que les compilateurs modernes savent faire en tant qu'instruction de chargement unique, comme par exemple
unsigned long longword;
memcpy(&longword, char_ptr, sizeof(longword));
char_ptr += sizeof(longword);
Cela fonctionne également pour les charges non alignées car memcpy travaille en tant que tel par char -à la fois. Mais en pratique, les compilateurs modernes comprennent memcpy très bien.
Le danger ici est que si le GCC ne connaître à coup sûr que char_ptr est aligné sur un mot, il ne le mettra pas en ligne sur certaines plates-formes qui ne supportent pas les chargements non alignés en asm. Par exemple, MIPS avant MIPS64r6, ou les anciens ARM. Si vous avez un appel de fonction réel à memcpy juste pour charger un mot (et le laisser dans une autre mémoire), ce serait un désastre. GCC peut parfois voir quand le code aligne un pointeur. Ou après la boucle char-at-a-time qui atteint une limite ulong vous pourriez utiliser
p = __builtin_assume_aligned(p, sizeof(unsigned long));
Cela n'évite pas le possible UB read-past-the-object, mais avec la GCC actuelle, ce n'est pas dangereux en pratique.
Pourquoi le code source C optimisé à la main est nécessaire : les compilateurs actuels ne sont pas assez performants
L'asm optimisé manuellement peut être encore meilleur lorsque vous voulez obtenir la moindre performance pour une fonction de bibliothèque standard largement utilisée. En particulier pour quelque chose comme memcpy mais aussi strlen . Dans ce cas, il ne serait pas beaucoup plus facile d'utiliser le C avec des intrinsèques x86 pour profiter de SSE2.
Mais ici, nous ne parlons que d'une version C naïve vs. bithack sans aucune caractéristique spécifique à l'ISA.
(Je pense que l'on peut considérer comme acquis que strlen est suffisamment utilisé pour qu'il soit important de le faire fonctionner aussi rapidement que possible. La question est donc de savoir si nous pouvons obtenir un code machine efficace à partir d'une source plus simple. Non, nous ne le pouvons pas).
Les GCC et clang actuels ne sont pas capables d'auto-vectoriser les boucles dont le nombre d'itérations n'est pas connu avant la première itération. . (par exemple, il doit être possible de vérifier que la boucle effectuera au moins 16 itérations). avant Exécuter la première itération.) Par exemple, memcpy autovectorisé est possible (tampon de longueur explicite) mais pas strcpy ou strlen (chaîne de longueur implicite), étant donné les compilateurs actuels.
Cela inclut les boucles de recherche, ou toute autre boucle dont le fonctionnement dépend des données. if()break ainsi qu'un compteur.
ICC (le compilateur d'Intel pour x86) peut auto-vectoriser certaines boucles de recherche, mais ne fait toujours qu'un asm naïf par octet pour un C simple/naïf. strlen comme la libc d'OpenBSD. ( Godbolt ). (De La réponse de @Peske ).
Une libc optimisée à la main strlen est nécessaire pour les performances avec les compilateurs actuels . Aller d'un octet à la fois (avec un déroulement de peut-être 2 octets par cycle sur les CPU superscalaires larges) est pathétique quand la mémoire principale peut suivre avec environ 8 octets par cycle, et le cache L1d peut fournir 16 à 64 par cycle. (2 charges de 32 octets par cycle sur les CPU x86 modernes depuis Haswell et Ryzen. Sans compter AVX512 qui peut réduire les vitesses d'horloge juste pour l'utilisation de vecteurs de 512 bits ; c'est pourquoi la glibc n'est probablement pas pressée d'ajouter une version AVX512. Bien qu'avec des vecteurs de 256 bits, AVX512VL + BW masquent la comparaison dans un masque et ktest ou kortest pourrait faire strlen plus favorable à l'hyperthreading en réduisant ses uops / itération).
J'inclus ici les non-x86, c'est-à-dire les "16 octets". Par exemple, la plupart des CPU AArch64 peuvent faire au moins cela, je pense, et certains certainement plus. Et certains ont un débit d'exécution suffisant pour strlen pour suivre cette bande passante.
Bien sûr, les programmes qui travaillent avec de grandes chaînes de caractères devraient généralement garder la trace des longueurs pour éviter d'avoir à refaire très souvent la recherche de la longueur des chaînes de caractères C à longueur implicite. Mais les performances des chaînes de longueur courte à moyenne bénéficient toujours des implémentations écrites à la main, et je suis sûr que certains programmes finissent par utiliser strlen sur des chaînes de longueur moyenne.
