grim7reaper

Un artisan du code

C’est l’histoire d’un bogue…

J’ai été confronté à ce bogue le 2013/08/25, je n’avais donc pas encore découvert le comportement indéfini lié à offsetof (que j’ai découvert lors de la rédaction de l’article précédent) ce qui explique pourquoi je ne le mentionne pas ici.

Le 2013/08/25, j’ai été confronté à un bogue assez surprenant au premier abord. Comme cela faisait longtemps que je n’étais pas tombé sur un bogue de ce genre, j’ai eu envie de partager le raisonnement que j’ai suivi pour en venir à bout (au cas où cela puisse servir à d’autres) sur le forum ubuntu-fr. Ce bogue fut aussi, d’une certaine façon, ce qui a conduit à l’ouverture de ce blog.

Le contexte

J’étais en train d’implémenter une liste linéaire simplement chaînée. Une liste générique, mais sans utiliser void* comme on le fait traditionnellement. Au lieu de cela, j’avais décidé de m’inspirer d’une méthode assez connue qui est utilisée dans le noyau Linux (utilisation d’une structure de données intrusive).

Le morceau de code qui suit permet d’avoir un aperçu de l’interface de la liste. Il s’agit en fait d’une version minimale du véritable programme d’exemple auquel j’ai retiré la gestion des erreurs (malloc) et la libération de la mémoire allouée car ce n’est pas le sujet ici (ne vous inquiétez pas, dans le programme d’origine tout cela est présent).

Exemple d’utilisation de la liste chaînée
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

#include <stdio.h>
#include <stdlib.h>

#include "slist.h"

typedef struct
{
    unsigned to;
    slist_node node;
    unsigned from;
} pair_list;

int main(void)
{
    slist_list list;
    pair_list* elt;
    unsigned i;

    /* Initialize the list. */
    slist_init(&list);

    /* Populate the list. */
    for(i = 0; i < 2; ++i)
    {
        elt = malloc(sizeof *elt);
        elt->from = i;
        elt->to   = i+1;
        slist_add(&list, &(elt->node));
    }

    /* Iteration with `slist_foreach_elt`. */
    slist_foreach_elt(&list, elt, pair_list, node)
        printf("from = %u | to = %u\n", elt->from, elt->to);

    return 0;
}

La découverte

Voyons maintenant ce que l’on obtient en sortie en l’exécutant.

Compilation avec gcc -O0
from = 1 | to = 2
from = 0 | to = 1
Compilation avec clang -O0
from = 1 | to = 2
from = 0 | to = 1
Compilation avec gcc -O2
from = 1 | to = 2
from = 0 | to = 1
Compilation avec clang -O2
from = 1 | to = 2
from = 0 | to = 1
zsh: segmentation fault (core dumped)

Tiens, tiens. Comme c’est intéressant : un bogue qui n’apparaît que lorsque l’on active les optimisations, et sur un seul compilateur en plus !

Quand on a une différence de comportement entre deux compilateurs, il y a deux solutions possibles :

  1. l’un des deux compilateurs a un bogue (peu probable, mais cela arrive).
  2. notre code contient :
    • un comportement non défini (undefined behavior, que je vais abréger par UB par la suite).
    • OU un comportement non spécifié (unspecified behavior).
    • OU un comportement dépendant de l’implémentation (implementation-specific behavior).

La différence entre les trois étant parfois oubliée, je vais faire un petit rappel ici. Tout d’abord, il faut savoir que le standard décrit une machine abstraite C (C abstract machine) qui peut être vu comme un interpréteur C.

Ceci dit, les UB ont aussi leurs bons côtés : c’est en partie grâce à leur existence que les compilateurs C peuvent faire de nombreuses optimisations. À ce sujet, je vous conseille cet excellent article en trois parties écrit par Chris Lattner (qui sait donc très bien de quoi il parle) :

Tant que j’en suis à donner des liens, cet article en trois parties de John Regehr est aussi très instructif sur les UB :

Étant donné que :

  1. je connaissais les articles précédemment cités.
  2. mon bogue apparaît seulement avec les optimisations activées (avec clang, il est présent à partir de O1 et avec gcc le programme s’exécute correctement quel que soit le niveau d’optimisation).
  3. mon code joue avec des pointeurs, des adresses, des structures et des macros.

Je suis donc directement partie sur la solution 2.

Le bogue

J’ai commencé par utiliser Memcheck sur la version compilé et optimisé par clang (entre temps, j’ai pris soin de recompiler avec le flag -g en plus de -O2 pour avoir les informations de déboguage).

Voilà le résultat :

Sortie de Memcheck
==7949== Invalid read of size 4
==7949==    at 0x4006A0: main (min_bug.c:34)
==7949==  Address 0xfffffffffffffff8 is not stack'd, malloc'd or (recently) free'd

Petite précision utile : la ligne 34 c’est le printf dans la boucle.

Donc a priori, la boucle fait trop d’itérations et essaye d’afficher des éléments en dehors de la liste. Étrange, sachant que le même code sans optimisations est tout à fait correct (Memcheck ne rapporte rien d’anormal). Donc une boucle tout à fait correcte, deviens boguée après optimisations. Hum…

Suite à cela, j’ai tenté de passer par gdb. En vain… La variable d’intérêt, elt, était optimized out (même en O1, et comme en O0 le bogue ne se manifeste pas…).

Du coup, j’ai ajouté un printf pour afficherelt et elt->node (ce sont les variables utilisées dans la condition d’arrêt du foreach) à chaque itération et j’ai pu constater que quand elt->node atteint la valeur nécessaire à l’arrêt de la boucle, et bien cette dernière ne s’arrête pas.

Bien, ma condition semble avoir disparue, c’est très ennuyeux ça. Je dois le vérifier. Et pour cela, il n’y a qu’une seule façon fiable : regarder le code assembleur généré.

En avant donc. Jetons d’abord un coup d’œil au code produit par gcc (je commence par celui là, car je sais que même optimisé ma boucle est toujours correcte).

Sortie de gcc -g -O1 -S (code de la boucle uniquement)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

.LVL4:
        .loc 1 33 0
        movq    %rsp, %rdi
        call    slist_first
.LVL5:
        leaq    -8(%rax), %rdx
.LVL6:
        movq    %rax, %rbx
        testq   %rax, %rax
        je      .L2
.L3:
        .loc 1 34 0 discriminator 2
        movl    16(%rdx), %esi
        movl    (%rdx), %edx
.LVL7:
        movl    $.LC0, %edi
        movl    $0, %eax
        call    printf
.LVL8:
        .loc 1 33 0 discriminator 2
        movq    %rbx, %rdi
        call    slist_next
.LVL9:
        leaq    -8(%rax), %rdx
.LVL10:
        movq    %rax, %rbx
        testq   %rax, %rax
        jne     .L3

Dans les dernières lignes on voit bien une comparaison (testq) suivi d’un saut conditionnel (jne) en début de boucle : tout va bien.

Sortie de clang -g -O1 -S (code de la boucle uniquement)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

.Ltmp13:
# BB#2:
        leaq    8(%rsp), %rdi
        .loc    1 33 0                  # examples/min_bug.c:33:0
.Ltmp14:
        callq   slist_first
        movq    %rax, %rbx
        .align  16, 0x90
.LBB0_3:                                # =>This Inner Loop Header: Depth=1
        .loc    1 34 0                  # examples/min_bug.c:34:0
        movl    -8(%rbx), %edx
        movl    8(%rbx), %esi
        movl    $.L.str, %edi
        xorb    %al, %al
        callq   printf
        .loc    1 33 0                  # examples/min_bug.c:33:0
        movq    %rbx, %rdi
        callq   slist_next
        movq    %rax, %rbx
        jmp     .LBB0_3

Et là : BAM !!!
En plein dans le mille.
La dernière instruction de la boucle est un saut inconditionnel en début de boucle. Pas de cmp ou test. Mais un bon gros jmp tout ce qu’il y a de plus inconditionnel. La différence saute au yeux !

C’est donc une belle boucle infinie, ce qui explique que je continue à boucler même après avoir rencontré ma condition d’arrêt (et donc cela explique également le fait que j’aille lire des adresses pourries qui me font faire une jolie Segmentation Fault).

L’explication

Maintenant, on est sûr que le problème vient de la boucle, et donc de slist_foreach_elt. Regardons donc ça de plus près :

slist_foreach_elt
1
2
3
4

#define slist_foreach_elt(list, curr, type, fieldname)         \
    for (curr = slist_elt(slist_first(list), type, fieldname); \
         &(curr->fieldname) != NULL;                           \
         curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Hooooo yeaaah :)

Sachant que slist_elt est aussi une macro :

slist_elt
1
2

#define slist_elt(node, type, fieldname) \
    ((type*)((char*)(node) - offsetof(type, fieldname)))

Bon, ça peut faire peur de voir ça comme ça, à froid et sans explication :D
Mais en réalité c’est très simple, et c’est le cœur même de l’astuce qui permet d’avoir une liste générique sans passer par du void*. Cela dit, je ne vais pas m’étendre sur le sujet du pourquoi du comment ça fonctionne (voire l’article précédent pour cela).

Donc sans plus d’explications, je vous montre la ligne fautive (qui est belle est bien dans le foreach) : 

&(curr->fieldname) != NULL;                          \

Ça peut sembler bizarre comme test, mais en fait ça tient la route (enfin presque, à un détail près et c’est bien pour cela que ça plante)
Pour information, voilà la version que l’on trouve dans le noyau Linux : 

&pos->member != (head);    \

C’est presque exactement le même code. À un détail près.

Détail qui vient du fait que la version Linux est une liste circulaire doublement chaînée. Et le point crucial ici est : circulaire.

Car grace à cette propriété, la condition d’arrêt est un test contre la tête de la liste, pas contre NULL.

Différence minime ? C’est ce que je pensais. Mais pas du tout, c’est une énorme différence : la différence entre un code correct et un UB.

Pas à pas

Lorsque je suis sur le dernier nœud (dont le pointeur next vaut NULL), je vais exécuter cette ligne (la partie incrémentation du foreach) : 

curr = slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Donc ici, je vais appeler slist_elt avec le contenu du pointeur next (car j’appelle slist_next), c’est-à-dire avec NULL.

Cela donne :

((type*)((char*)(node) - offsetof(type, fieldname)))

Et donc dans le cas présent :

((pair_list*)((char*)(NULL) - offsetof(pair_list, node)))

offsetof renvoie, comme son nom l’indique, l’offset (en byte) d’un champ dans une structure.

Ici, je veux l’offset de mon nœud dans la structure. Ça me retourne donc 8 (en effet, dans la structure pair_list il y a un unsigned avant ce champ, et les unsigned sur ma machine font 4 bytes et il y a 4 bytes de padding pour aligner le champ suivant).

NULL étant défini, au niveau du code source (ce n’est pas toujours vrai après compilation), comme étant 0 cela donne donc : 0 - 8.

NULL étant un pointeur et les pointeurs étant non signés et sur 64 bits (sur ma machine), on obtient l’adresse suivante : 0xfffffffffffffff8
Tiens, c’est l’adresse qui était apparue dans Valgrind ça ;)

Donc après exécution de cette partie « incrémentation » de la boucle for, on retourne au début de la boucle et on va tester la condition : 

&(curr->fieldname) != NULL;                          \

Ce qui donne dans mon cas :

&(elt->node) != NULL;                          \

curr vaut 0xfffffffffffffff8, l’offset du champ auquel je souhaite accéder est 8. Cela donne donc 0 quand je les additionne. C’est bien égal à NULL, ma boucle s’arrête et c’est parfait.

Oui… Mais non !

Car mon implémentation contient un UB et donc le compilateur peut produire un autre code.

Du point de vue de la norme

Voici quelques extraits choisis de la norme du C99 :

6.3.2.3 Pointers
[…]
3
An integer constant expression with the value 0, or such an expression cast to type void *, is called a null pointer constant. If a null pointer constant is converted to a pointer type, the resulting pointer, called a null pointer, is guaranteed to compare unequal to a pointer to any object or function.
[…]

Et :

6.5.6 Additive operators
[…]
7
For the purposes of these operators, a pointer to an object that is not an element of an array behaves the same as a pointer to the first element of an array of length one with the type of the object as its element type.

8
When an expression that has integer type is added to or subtracted from a pointer, the result has the type of the pointer operand. If the pointer operand points to an element of an array object, and the array is large enough, the result points to an element offset from the original element such that the difference of the subscripts of the resulting and original array elements equals the integer expression. In other words, if the expression P points to the i-th element of an array object, the expressions (P)+N (equivalently, N+(P)) and (P)-N (where N has the value n) point to, respectively, the i+n-th and i−n-th elements of the array object, provided they exist. Moreover, if the expression P points to the last element of an array object, the expression (P)+1 points one past the last element of the array object, and if the expression Q points one past the last element of an array object, the expression (Q)-1 points to the last element of the array object. If both the pointer operand and the result point to elements of the same array object, or one past the last element of the array object, the evaluation shall not produce an overflow; otherwise, the behavior is undefined. If the result points one past the last element of the array object, it shall not be used as the operand of a unary * operator that is evaluated.
[…]

Réfléchissons un peu. Qu’est-ce que je fais dans cette condition :

&(elt->node) != NULL;                          \

Je compare l’adresse d’un champ de ma structure (donc l’adresse d’un objet) avec NULL (qui ne peut pas être l’adresse d’un objet, cf. §6.3.2.3/3), partant de là le compilateur sait que le test ne renverra jamais faux et il peut donc le supprimer.

De manière générale, toute opération arithmétique avec un pointeur NULL débouche sur un UB. En effet, la condition 6.5.6/8 sera toujours violé (vu que le §6.3.2.3/3 garanti que NULL est différent de tout sauf de lui-même, le résultat de l’opération ne pourra jamais pointer sur le même objet que NULL (vu que par définition il ne pointe sur rien)).
Même faire NULL - NULL c’est un UB. C’est presque le même principe que précédemment, sauf que c’est le §6.5.6/9 au lieu de §6.5.6/8 qui s’applique (je laisse les curieux consulter la norme).

Pour terminer sur une petite remarque, la norme du C++ est un peu plus défini à ce niveau-là car elle autorise deux opérations arithmétiques sur les pointeurs nuls :

Pour citer la norme :

5.7 Additive operators
[…]
7
If the value 0 is added to or subtracted from a pointer value, the result compares equal to the original pointer value. If two pointers point to the same object or both point one past the end of the same array or both are null, and the two pointers are subtracted, the result compares equal to the value 0 converted to the type std::ptrdiff_t.
[…]

Si vous voulez en savoir plus à propos de pourquoi C++ supporte cela, je vous conseille la lecture de cet article.

La solution

Comme le problème vient du fait d’appeler slist_elt avec NULL il suffit de reformuler la boucle for pour éviter ce cas de figure :

Nouvelle implémentation de slist_foreach_elt
1
2
3
4
5

#define slist_foreach_elt(list, curr, type, fieldname)                     \
        for (curr = slist_elt(slist_first(list), type, fieldname);         \
             curr != NULL;                                                 \
             curr = curr->fieldname.next == NULL ? NULL :                  \
                    slist_elt(slist_next(&(curr->fieldname)), type, fieldname))

Et le problème est résolu.

Deux autres solutions possibles :

Le mot de la fin