Qu’est-ce qui permet à glibc malloc de comparer les pointeurs de différents «objects»?

La comparaison de pointeurs avec un opérateur relationnel (par exemple < , <= , >= ou > ) n’est définie par le standard C que lorsque les pointeurs pointent tous deux dans le même object agrégat (struct, array ou union). En pratique, cela signifie qu’une comparaison sous forme de

 if (start_object <= my_pointer && my_pointer < end_object+1) { 

peut être transformé en

 if (1) { 

par un compilateur d’optimisation. Malgré cela, dans K & R, section 8.7 “Exemple – Un répartiteur de stockage”, les auteurs font des comparaisons similaires à celle ci-dessus. Ils excusent cela en disant

Cependant, il existe toujours une hypothèse selon laquelle les pointeurs vers différents blocs renvoyés par sbrk peuvent être comparés de manière significative. Cela n’est pas garanti par la norme, qui autorise les comparaisons de pointeur uniquement dans un tableau. Ainsi, cette version de malloc n’est portable que parmi les machines pour lesquelles la comparaison générale des pointeurs est significative.

De plus, il semble que la mise en œuvre de malloc utilisée dans la glibc fasse la même chose!

Ce qui est pire, c’est la raison pour laquelle j’ai trébuché là-dessus, c’est parce que, pour un devoir scolaire, je suis supposé mettre en place une fonction rudimentaire de type malloc , et les instructions relatives à ce devoir nous obligent à utiliser le code K & R, mais nous devons remplacer le sbrk appelle avec un appel à mmap !

Bien que la comparaison de pointeurs d’appels sbrk différents soit probablement indéterminée, elle est également légèrement douteuse, car vous avez une sorte d’intuition mentale selon laquelle les pointeurs renvoyés doivent provenir d’une sorte de région de mémoire. Pour autant que je sache, les pointeurs renvoyés par différents appels mmap n’ont aucune garantie de ressemblance, et la consolidation / la fusion de blocs de mémoire sur des appels mmap devrait être hautement illégale (et il semble que glibc évite, le fait de ne fusionner que sbrk ou en interne à l’intérieur des pages mmap , pas à travers elles), mais l’assignation le requirejs.

Question: quelqu’un pourrait-il faire la lumière sur

  1. Si la comparaison de pointeurs d’appels différents à sbrk peut être optimisée, et
  2. Si c’est le cas, que fait la glibc qui leur permet de s’en tirer à bon compte?

    La réponse de l’avocat spécialiste des langues se trouve (je crois) au paragraphe 6.5.8.5 de la norme C99 (ou plus précisément de la norme ISO / IEC 9899: Projet de comité TC3 – 7 septembre 2007, WG14 / N1256, qui est presque identique mais que je ne sais pas ». t avoir l’original en main) qui présente ce qui suit en ce qui concerne les opérateurs relationnels (c.-à-d. < , <= , > , >= ):

    Lorsque deux pointeurs sont comparés, le résultat dépend des emplacements relatifs dans l'espace d'adressage des objects pointés. Si deux pointeurs sur des types d'object ou des types incomplets pointent tous deux sur le même object ou tous les deux, un après le dernier élément du même object tableau, ils se comparent égaux. Si les objects pointés sont des membres du même object agrégé, les pointeurs sur les membres de la structure déclarés ultérieurement comparent les pointeurs supérieurs aux membres déclarés précédemment dans la structure, et les pointeurs sur des éléments de tableau avec des valeurs en indice plus grandes comparent les pointeurs supérieurs aux éléments du même tableau. avec des valeurs plus faibles en indice. Tous les pointeurs vers les membres d'un même object d'union se comparent. Si l'expression P pointe sur un élément d'un object tableau et que l'expression Q pointe sur le dernier élément du même object tableau, l'expression de pointeur Q+1 compare plus grande que P Dans tous les autres cas, le comportement est indéfini.

    (le texte C11 est identique ou presque identique)

    Cela semble au début inutile, ou du moins suggère que les implémentations exploitent chacune un comportement indéfini. Je pense cependant que vous pouvez rationaliser le comportement ou utiliser un moyen de contourner le problème.

    Les pointeurs C spécifiés sont soit NULL , soit dérivés de la prise de l'adresse d'un object avec & , soit par l'arithmétique de pointeur, soit par le résultat d'une fonction. Dans le cas concerné, elles sont dérivées du résultat des appels système sbrk ou mmap . Qu'est-ce que ces systèmes appellent vraiment ? Au niveau du registre, ils renvoient un entier de la taille uintptr_t (ou intptr_t ). C’est en fait l’interface d’appel système qui les transmet à un pointeur. Comme nous soaps que les uintptr_t entre les pointeurs et uintptr_t (ou intptr_t ) sont par définition du type bijective, nous soaps que nous pourrions lancer les pointeurs sur uintptr_t (par exemple) et les comparer, ce qui imposerait une relation bien ordre aux pointeurs. Le lien wikipedia donne plus d’informations, mais cela garantira essentiellement que chaque comparaison est bien définie ainsi que d’autres propriétés utiles telles que a et b implique a . (Je ne peux pas non plus choisir un ordre totalement arbitraire, car il aurait besoin de satisfaire aux autres exigences de C99 §6.5.8.5, ce qui me laisse à intptr_t uintptr_t candidat avec intptr_t et uintptr_t .)

    Nous pouvons exploiter cela et écrire le (sans doute mieux):

     if ((uintptr_t)start_object <= (uintptr_t)my_pointer && (uintptr_t)my_pointer < (uintptr_t)(end_object+1)) { 

    Il y a une nit ici. Vous noterez que j'ai uintptr_t et non intptr_t . Pourquoi était-ce le bon choix? En fait, pourquoi n'ai-je pas choisi un ordre plutôt bizarre, comme inverser les bits et comparer? L’hypothèse est ici que je choisis le même ordre que le kernel, en particulier que ma définition de < (donnée par l’ordre) est telle que le début et la fin de tout bloc mémoire alloué seront toujours tels que start < end . Sur toutes les plates-formes modernes que je connais, il n'y a pas de «bouclage» (par exemple, le kernel n'allouera pas de mémoire 32 bits commençant à 0xffff8000 et se terminant à 0x00007ffff ) - bien que le 0x00007ffff similaire ait été exploité dans le passé .

    La norme C spécifie que les comparaisons de pointeurs donnent des résultats non définis dans de nombreuses circonstances. Cependant, vous construisez ici vos propres pointeurs à partir d’entiers renvoyés par les appels système. Vous pouvez donc soit comparer les nombres entiers, soit comparer les pointeurs en les reconvertissant en nombres entiers (en exploitant la nature bijective de la dissortingbution). Si vous comparez simplement les pointeurs, vous vous fiez à la mise en œuvre de la comparaison de pointeurs par le compilateur C, ce qui est presque certainement le cas, mais n'est pas garanti.

    Les possibilités que je mentionne sont-elles si obscures qu'elles peuvent être escomptées? Bon, trouvons un exemple de plate-forme où ils pourraient être importants: 8086. Il est possible d'imaginer un modèle de compilation 8086 dans lequel chaque pointeur est un pointeur «éloigné» (c'est-à-dire qu'il contient un registre de segments). La comparaison de pointeurs pourrait faire un < ou > sur le registre de segment et que s'ils sont égaux, faire un < ou > sur le décalage. Cela serait tout à fait légitime si toutes les structures de C99 § 6.5.8.5 sont dans le même segment. Mais cela ne fonctionnera pas comme on pourrait s'y attendre entre les segments, car 1000:1234 (ce qui correspond à 1010:1134 en adresse mémoire) apparaîtra plus petit que 1010:0123 . mmap ici pourrait bien renvoyer des résultats dans différents segments. De même, on pourrait penser à un autre modèle de mémoire où le registre de segment est en fait un sélecteur, et une comparaison de pointeur utilisant une instruction de comparaison de processeur a été utilisée pour comparer les adresses de mémoire qui abandonnent si un sélecteur non valide ou un décalage en dehors d'un segment est utilisé.

    Vous posez deux questions spécifiques:

    1. Si la comparaison de pointeurs d'appels différents à sbrk peut être optimisée, et

    2. Si c'est le cas, que fait la glibc qui leur permet de s'en tirer à bon compte?

    Dans la formulation donnée ci-dessus, où start_object etc. sont en fait void * , le calcul peut être optimisé (par exemple, il peut faire ce que vous voulez) mais il n'est pas garanti de le faire car le comportement n'est pas défini. Une dissortingbution garantirait qu'il le fasse à condition que le kernel utilise le même ordre bien défini par la dissortingbution.

    En réponse à la deuxième question, la glibc s’appuie sur un comportement du compilateur C qui n’est techniquement pas requirejs, mais qui est très probable (selon ce qui précède).

    Notez également (au moins dans le K & R devant moi) que la ligne que vous citez n'existe pas dans le code. La mise en garde concerne la comparaison des en- header * pointeurs avec < (autant que je sache, la comparaison des pointeurs void * avec < étant toujours UB) pouvant provenir d'appels sbrk() distincts.

    La réponse est assez simple. L’implémentation de la bibliothèque C est écrite avec une certaine connaissance (ou peut-être des attentes) de la façon dont le compilateur C gérera un code ayant un comportement indéfini conformément à la spécification officielle.

    Je pourrais donner de nombreux exemples; mais cette indication renvoie en fait à une adresse dans l’espace du processus et peut être comparée librement par l’implémentation de la bibliothèque C (du moins par Glibc) ainsi que par de nombreux programmes “réels”. Bien que cela ne soit pas garanti par la norme pour les programmes ssortingctement conformes, cela est vrai pour la grande majorité des architectures / compilateurs du monde réel. De plus, notez la note de bas de page 67 sur la conversion des pointeurs en nombres entiers et inverses:

    Les fonctions de mappage permettant de convertir un pointeur en entier ou un entier en pointeur sont conçues pour être cohérentes avec la structure d’adressage de l’environnement d’exécution.

    Bien que cela n’autorise pas ssortingctement la comparaison de pointeurs arbitraires, il est utile de comprendre comment les règles sont censées fonctionner: il s’agit d’un ensemble de comportements spécifiques qui sont assurés d’être cohérents sur toutes les plateformes, plutôt que de limiter ce qui est permis. lorsque la représentation d’un pointeur est parfaitement connue et comprise.

    Vous avez remarqué que:

     if (start_object <= my_pointer && my_pointer < end_object+1) { 

    Peut être transformé en:

     if (1) { 

    Avec l’hypothèse (que vous n’avez pas my_pointer ) que my_pointer est dérivé de la valeur de start_object ou de l’adresse de l’object qu’il délimite - alors c’est ssortingctement vrai, mais ce n’est pas une optimisation que les compilateurs font en pratique, sauf dans le cas d'objects de durée de stockage statique / automatique (c'est-à-dire des objects dont le compilateur sait qu'ils n'ont pas été alloués de manière dynamic).

    Considérez le fait que les appels à sbrk sont définis pour incrémenter ou décrémentez le nombre d’octets alloués dans une région (le segment de mémoire), pour un processus donné par le paramètre d’incrément donné en fonction d’une adresse brk . C’est vraiment juste un wrapper autour de brk , qui vous permet d’ajuster le sumt actuel du tas. Lorsque vous appelez brk(addr) , vous indiquez au kernel d’allouer de l’espace à votre processus depuis le bas de l’ addr (ou éventuellement de libérer de l’espace entre le dernier emplacement supérieur, celui de l’adresse la plus récente et la plus récente). adresse). sbrk(incr) serait exactement équivalent si incr == new_top - original_top . Donc pour répondre à votre question:

    1. Comme sbrk ajuste simplement la taille du segment de mémoire (c’est-à-dire une région contiguë de la mémoire) en incr nombre d’octets, la comparaison des valeurs de sbrk est simplement une comparaison des points dans une région contiguë de la mémoire. Cela équivaut exactement à comparer des points dans un tableau. Il s’agit donc d’une opération bien définie selon le standard C. Par conséquent, les appels de comparaison de pointeur autour de sbrk peuvent être optimisés.

    2. glibc ne fait rien de spécial pour “s’en tirer à bon compte” – ils supposent simplement que l’hypothèse mentionnée ci-dessus est vraie (ce qui est le cas). En fait, s’ils vérifient l’état d’un bloc pour la mémoire allouée avec mmap , il vérifie explicitement que la mémoire de mmap ‘d est en dehors de la plage allouée avec sbrk .

    Edit: Quelque chose que je veux préciser dans ma réponse: La clé ici est qu’il n’ya pas de comportement indéfini! sbrk est défini pour allouer des octets dans une région de mémoire contiguë, qui est elle-même un “object” comme spécifié par le standard C. Par conséquent, la comparaison des pointeurs au sein de cet “object” est une opération parfaitement saine et bien définie. Ici, l’hypothèse n’est pas que la glibc tire parti de la comparaison de pointeur indéfinie, mais du fait que sbrk augmente / réduit la mémoire dans certaines régions contiguës.

    Les auteurs de la norme C ont reconnu qu’il existe certaines plates-formes matérielles à mémoire segmentée dans lesquelles une tentative de comparaison relationnelle entre des objects appartenant à des segments différents peut se comporter de manière étrange. Plutôt que de dire que de telles plates-formes ne pourraient pas efficacement prendre en charge les implémentations C efficaces, les auteurs de la norme permettent à ces implémentations de faire tout ce qui leur semble approprié si l’on tente de comparer des pointeurs à des objects pouvant se trouver dans différents segments.

    Pour les auteurs de la norme, les comparaisons entre objects disjoints ne devraient présenter qu’un comportement étrange sur des systèmes à mémoire segmentée qui ne peuvent pas produire un comportement cohérent aurait été considéré comme impliquant que ces systèmes étaient inférieurs aux plates-formes où des comparaisons relationnelles entre Des pointeurs arbitraires produiront un classement cohérent et les auteurs de la norme ont fait de leur mieux pour éviter de telles implications. Au lieu de cela, ils ont supposé que, puisqu’il n’y avait aucune raison pour que les implémentations ciblant des plates-formes ordinaires fassent quoi que ce soit de bizarre avec de telles comparaisons, de telles implémentations les géreraient de manière raisonnable, que la norme les autorise ou non.

    Malheureusement, certaines personnes plus intéressées par la création d’un compilateur conforme à la norme que par celle utile, ont décidé que tout code qui n’était pas écrit pour tenir compte des limitations du matériel obsolète depuis des décennies devait être considéré comme “cassé”. “. Ils affirment que leurs “optimisations” permettent aux programmes d’être plus efficaces qu’ils ne le seraient autrement, mais dans de nombreux cas, les gains “d’efficacité” ne sont significatifs que dans les cas où un compilateur omet le code réellement nécessaire. Si un programmeur contourne les limites du compilateur, le code résultant pourrait s’avérer moins efficace que si le compilateur ne s’était pas préoccupé de l’optimisation.