Top 5 des bugs insolites

Coder un OS, c’est pas simple : des milliers de lignes de code, une logique complexe et difficile à suivre, beaucoup de composants qui communiquent, beaucoup d’opportunité pour des fautes débiles (surtout quand on a codé toute la journée !). Comme on peut le voir sur le log des commits, j’ai passé ma journée à corriger des bugs sur mon projet d’OS, Kogata (dont je n’ai d’ailleurs pas encore fait la présentation officielle, mais tout est ici). Dans cet article, je vais vous présenter le top 5 des bugs les plus chiants à détecter, ou tout simplement les plus débiles, que j’ai rencontré (et corrigé !) récemment.

5. Les interférences

C’est un grand classique, et j’imagine que toute personne qui fait de la programmation concurrente dans un langage bas niveau à déjà du y être confronté. Le principe est simple : on a une masse (typiquement 2 ou 3 suffisent) de threads qui veulent accéder en même temps à une structure de donnée pour modifier des trucs. Évidemment si tout le monde le fait en même temps ça cause des conflits, c’est pourquoi on utilise des verrous (mutex) sur ces structures, afin qu’un thread puisse s’approprier temporairement la structure pour pouvoir la modifier sans danger et la laisser dans un état cohérent pour la prochaine personne qui en a besoin.

Les bugs récemment présents dans Kogata étaient simplement dus à de la négligence, à savoir écrire des fonctions qui modifient des données sans verrouiller la mutex au préalable. Ces fonctions manipulaient la structure process_t, structure fondamentale s’il en est, puisqu’elle gère l’unité de base du système : le processus utilisateur. Les conséquences de ce bug étaient multiples et variées, et se manifestaient parfois à des endroits inattendus (dans les fonctions hashtbl_add ou hashtbl_free par exemple, qui ne sont pas thread-safe dans mon code). On se retrouvait typiquement avec des double free, ou bien à utiliser des données qui avaient déjà été libérées dans un autre thread, détruisant ainsi des données utiles à l’allocateur de mémoire.

4. Les optimisations qui font marcher un code qui ne devrait pas marcher

Attention, le paragraphe suivant est un peu indigeste - âmes sensibles s’abstenir.

Pour faire un context switch, c’est à dire un changement de contexte permettant de basculer entre deux threads qui veulent s’exécuter, on doit d’abord sauver le contexte du thread en cours, c’est-à-dire les informations qui lui sont utiles, à savoir les registres du processeur, afin de pouvoir reprendre l’exécution de ce thread dans le même état ultérieurement. Un context switch peut être invoqué à plusieurs endroits, mais en particulier lorsqu’une IRQ0 a lieu : celle-ci est déclenchée périodiquement et permet d’interrompre un processus qui a fini d’utiliser le temps de processeur qui lui était alloué. La fonction appelée lors d’une IRQ0 doit déjà sauver une partie du contexte du thread en cours, car le rôle d’une IRQ est d’interrompre le traitement actuellement en cours et de lancer une procédure spécifique pour gérer l’IRQ - il faut donc être capable de reprendre là où on en était lorsque l’interruption a été traitée. Je pensais donc bien faire en me disant que, lorsque je fait un context switch sur une IRQ0, il n’était pas nécessaire de sauver deux fois les registres généraux du processeur, puisque ceux-ci étaient déjà sauvés en entrant dans l’IRQ0 et qu’après le retour du context switch (c’est-à-dire quand on re-donnait la main à mon thread), j’allais immédiatement terminer mon traitement de l’IRQ et restaurer le contexte qui était sauvé par le handler IRQ0. (Vous me suivez ? Bon, accrochez-vous, c’est bientôt fini !) En fait cela marchait avec les optimisations -O2 car gcc optimisait effectivement mon code pour ne pas utiliser les registres généraux entre le moment où mon thread est relancé et le moment où on sort de l’IRQ, mais il y a néanmoins un retour de fonction en jeu dans cette histoire, ce qui fait qu’au moins le registre ebp est utilisé. Quand on n’active pas les optimisations, gcc fait un peu ce qu’il veut et utilise en fait plus de registres que ça. Et on ne peut pas le blâmer, c’est bien cohérent avec la spécification du langage C. La solution a donc été de sauvegarder complètement l’état du processeur lors d’un context switch, même dans le cas d’une IRQ0.

Dans le même genre, il y a un bug où le compilateur optimise le code généré et se permet de modifier les arguments qui sont passés à une fonction. Le prototype de la fonction en question était le suivant :

void idt_irq_handler(registers_t regs) {
    ...
}

Or, la fonction C était appelée depuis du code assembleur qui présupposait que les arguments n’allaient pas être modifiés par la fonction appelée. C’était d’ailleurs critique car l’argument était justement un contexte sauvé dans le cas d’une IRQ. On se retrouvait donc à relancer des contextes modifiés de façon imprévisible, et on pouvait globalement se retrouver à exécuter n’importe quoi. Ce bug est en fait un bug connu dans un tutoriel d’OSdev plutôt populaire dont j’avais inspiré une partie de mon code. La solution est simple et consiste à passer un pointeur sur la structure, et non sa valeur :

void idt_irq_handler(registers_t *regs) {
    ...
}

La particularité de ce bug est que lorsque les optimisations n’étaient pas activé il ne se manifestait pas, car le code ne modifiait pas explicitement les arguments de la fonction, mais par contre avec les optimisations GCC réutilisait l’espace des arguments pour autre chose lorsqu’il voyait que ceux-ci n’allaient plus servir. Encore une fois, il avait le droit de le faire, c’est dans la spec.

3. La structure de donnée chiante

Pour la gestion de l’espace mémoire virtuel du noyau (ainsi que pour celui de chacun des processus utilisateurs), on utilise un allocateur qui est en charge d’allouer des régions de mémoire, dont la taille est un multiple de la taille d’une page du système (4ko sur un processeur x86). Pour implémenter cet allocateur, on a une structure de donnée utilisée pour décrire par une liste liée les zones de mémoire virtuelle non allouées :

struct free_t {
    void* addr;
    size_t size;
    free_t *next_by_size;
    free_t *first_bigger;
    free_t *next_by_addr;
};

En fait, cette structure est assez complexe car, comme vous pouvez le voir, on utilise trois pointeurs :

• La liste des descripteurs de région libres chaînée par le pointeur next_by_size décrit les régions libres dans l’ordre de taille croissante. Trier les descripteurs par ordre de taille croissante permet de trouver rapidement le descripteur pour la région la plus petite qui satisfait une certaine demande.
• La liste des descripteurs chaînée par le pointeur next_by_addr décrit les régions libres dans l’ordre des adresses croissantes. Trier les descripteurs par adresse permet de trouver une région libre juste avant ou juste après une région que l’on libère, pour pouvoir ainsi fusionner les deux régions libres en une région plus grande et éviter la fragmentation de la mémoire.
• Le pointeur first_bigger permet d’accélérer la recherche dans la liste triée par taille : il pointe sur le descripteur de la première région dans cette liste qui a une taille strictement supérieure à l’élément courant.

Le bug qui était présent dans le code était que le pointeur first_bigger n’était pas maintenu correctement et pointait parfois sur NULL alors qu’il n’aurait pas dû, ce qui causait l’allocateur de région à ne pas pouvoir allouer de région. Le système plantait donc avec une erreur out-of-memory (OOM). On est un peu surpris de continuer à voir cette erreur alors que l’on vient de quadrupler la RAM allouée à sa VM de test.

2. L’itération foireuse

Imaginons la structure suivante, décrivant typiquement des éléments d’une liste chaînée:

struct hashtbl_item_t {
    void* key;
    void* val;
    hashtbl_item_t *next;
};

Maintenant, supposons que dans la précipitation, on itère dessus de la façon suivante :

for (hashtbl_item_t *i = ht->items[s]; i != 0; i++) {
    f(i->key, i->val);
}

Le code précédent compile (en effet, il est autorisé d’incrémenter un pointeur, c’est d’ailleurs souhaitable), mais il ne fait pas du tout ce qu’on veut, et risque grandement de causer des écritures par-dessus d’autres données utiles. La bonne façon d’itérer est bien sûr la suivante :

for (hashtbl_item_t *i = ht->items[s]; i != 0; i = i->next) {
    f(i->key, i->val);
}

Le code précédent n’est pas directement issu de Kogata (s’il y avait eu un bug dans la structure hashtbl_t, les conséquences auraient été bien plus extrêmes), mais il y avait exactement la même erreur à un autre endroit. Dans le même genre, il y avait à un moment le bug suivant :

for (void* it = r->addr; it < r->addr + r->size; r += PAGE_SIZE) {
    ...
}

Où est le bug ? En fait l’itérateur qui devrait être incrémenté est évidemment it et non r ; ici le fait d’incrémenter r de PAGE_SIZE correspondait en fait à déplacer le pointeur r de PAGE_SIZE fois la taille de la structure pointée par r, qui était assez grande. On se retrouvait du coup avec un pointeur sur une zone totalement random, ce qui causait généralement une page fault sur une région invalide (équivalent en code noyau de la classique segmentation fault) plutôt que des trashages de données difficilement identifiables.

1. Le malloc avec la mauvaise taille

token_table_entry_t *e = (token_table_entry_t*)malloc(sizeof(token_t));

La structure token_table_entry_t contient un champ token_t, et est donc plus grande que celle-ci. On alloue donc ici un espace mémoire trop petit, ce qui fait que quand on écrira dans certains champs de la structure allouée, on écrira en fait par-dessus des données sensée appartenir à quelqu’un d’autre.

Les conséquences de ce bug sont assez imprévisibles, en l’occurrence c’était des crash dans les fonctions malloc et free car le bloc suivant en mémoire correspondait généralement à un bloc décrivant une région libre pour l’allocateur de mémoire.

Maintenant, pour terminer en beauté, imaginez un peu comme le bug précédent, sauf que j’avais écrit très précisément cette ligne :

iso9660_node_t *n = (iso9660_node_t*)malloc(sizeof(iso9660_node_t*));

Alors, où est le bug ? AHA ! Encore une fois, la taille allouée est mauvaise, mais il faut mettre ses lunettes pour s’en rendre compte. En effet, ici, au lieu d’allouer une structure iso9660_node_t entière, on alloue simplement un pointeur sur une telle structure, ce qui est bien sûr complètement inutile.

La conséquence de ce bug était que l’on se retrouvait à allouer de la mémoire parmi les “petits objets” (taille d’un pointeur), et l’écriture au-delà de la zone allouée causait des trashage aléatoire de données utiles au système, rendant ainsi les conséquences de ce bug totalement aléatoires, et très drôles (ou pas).

Conclusion

Avant que je corrige tous ces bugs, j’avais globalement un crash à chaque fois que je lançais mon OS, ce qui rendait le développement d’applications un peu difficile, comme vous pouvez l’imaginer. Quand on est dans cette situation, il n’y a pas d’autre recours que de retrousser ses manches et de mettre les mains dans le cambouis numérique. C’est d’ailleurs le bon côté de la chose : j’ai appris à désassembler du code avec gdb, et Kogata est maintenant capable d’afficher un stack trace à peu près utile en cas d’erreur. Mais à défaut de vouloir s’abaisser à ce genre de magouilles, certains seront tentés de se dire fuck it je vais coder dans un langage haut niveau, d’ailleurs on me l’a répétitivement conseillé. Mais lorsque l’on part comme ça, on se prend la tête sur des questions compliquées, du style quel langage ? comment le rendre suffisamment bas niveau pour pouvoir faire de l’OSdev quand même ? etc., et on abandonne après quelques semaines de prise de tête conceptuelle pour revenir sur les pas de nos aînés qui, eux, on compris comment on écrit du vrai code (true story!).