Outils de débogage pour la programmation concurrente — Outils de Valgrind

Les logiciels présentés ici ont été testés au mois d’août 2012, il est probable que certaines informations au niveau des fonctionnalités et performances soient obsolètes.

Les outils qui nous intéressent ici sont Helgrind, DRD et ThreadSanitizer. Les deux premiers font partie de la suite d’outils officiels de Valgrind, le dernier est un nouvel outil prometteur, développé par Google.

Helgrind

Cet outil surveille chaque zone mémoire qui est accédée par plus d’un thread et vérifie à chaque fois que la cohérence des données est maintenue. Pour cela, il utilise un algorithme basé sur les relations Happens-Before (relations établissant un ordre partiel entre deux évènements). Helgrind permet de détecter :

• les situations de compétition ;

• l’utilisation des verrous dans un ordre incohérent ;

• la mauvaise utilisation de l’API POSIX pour les threads (pthreads).

Il est intéressant de noter qu’il peut aussi fonctionner avec les programmes utilisant OpenMP (une API permettant de faciliter la création de programmes réalisant des calculs parallèles sur des architectures à mémoire partagée) et Qt4 (Qt4 utilise sa propre implémentation des mutex : les QMutex). Enfin, il fonctionne avec les mutex POSIX implémentés par Linux, Darwin (le noyau de MacOS) et Android.

DRD

C’est un outil qui a de nombreux points communs avec Helgrind.

• utilisation d’un algorithme basé sur les relations Happens-Before ;
• détection des situations de compétition ;

• détection des erreurs d’utilisation de l’API POSIX ;

• support d’OpenMP et de Qt4 ;
• support des mutex POSIX de Linux, Darwin et Android.

En revanche, DRD se démarque de Helgrind par son surcoût mémoire (qui est généralement moindre), son support de Boost.Thread et par sa capacité à détecter lorsqu’un thread conserve un verrou trop longtemps et provoque alors des conflits de verrouillage qui ralentissent le programme.

Cependant, DRD ne permet pas de détecter les incohérences dans l’ordre d’utilisation des verrous.

ThreadSanitizer

ThreadSanitizer, aussi appelé tsan, est un outil pour la détection des situations de compétition dans les programmes C et C++. Il est développé par Google. Il est écrit en C++ (Helgrind et DRD sont en C, tout comme Valgrind). Il est disponible sous la forme d’un outil Valgrind (pour Linux et Mac) ou basé sur le logiciel Pin (pour Windows).

Au niveau des fonctionnalités, il supporte les mutex POSIX de Linux, Darwin et Android. Mais en ce qui concerne les détections il est plus limité que les deux outils précédents car il ne détecte que les situations de compétition. En revanche, il en détecte plus car il dispose de deux modes de fonctionnement :

1. mode pur Happens-Before : identique à Helgrind et DRD ;
2. mode hybride¹.

Lorsque l’on veut vérifier la justesse d’un programme concurrent il y a un certain nombre d’évènements à surveiller. On peut les regrouper en trois catégories :

1. les évènements de synchronisation : LOCK et UNLOCK ;
2. les évènements permettant d’établir les relations Happens-Before : WAIT et SIGNAL ;
3. les accès mémoire : READ et WRITE.

Le mode hybride utilise une approche LockSet pour les évènements de synchronisation et une approche Happens-Before pour le reste. Le LockSet détecte toutes les situations de compétitions, le problème c’est qu’il produit énormément de faux positifs² (au point d’être inutilisable). L’approche Happens-Before ne produit pas de faux positifs, mais ne détecte pas un certain nombre de situations de compétition. Ce mode hybride permet donc de détecter plus de situations de compétitions qu’un Happens-Before pur, mais produit aussi plus de faux positifs (mais moins qu’un LockSet pur).

Pour remédier au problème des faux positifs, ThreadSanitizer fournit un mécanisme d’annotations que l’on peut placer dans le code source afin de donner des informations à l’outil d’analyse. Cela permet d’utiliser des mécanismes de synchronisation sans verrous, de limiter les faux positifs et d’ignorer les situations de compétitions bénignes. En étudiant les codes sources, on peut noter qu’un mécanisme d’annotations similaire est maintenant aussi en cours d’implémentation dans Helgrind et DRD.

Une chose très intéressante au niveau de ThreadSanitizer, c’est que Google est en train de développer une version pour améliorer les performances. Comme présenté dans l’article précédent, les méthodes d’analyses dynamiques ont un impact non négligeable sur la vitesse d’exécution du programme. Pour y remédier, Google met au point une version de ThreadSanitizer basée sur LLVM plutôt que Valgrind³. Le but ici est de réaliser l’instrumentation du code lors de la compilation (et non dynamiquement comme le fait Valgrind) puis de lier le code au runtime de ThreadSanitizer. Cela permet un gain de performance très intéressant.

References

Les références utilisées pour ces trois articles sont les suivantes :

1. Müehlenfeld, A., and Wotawa, F. Fault detection in multi-threaded C++ server applications. In Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming (New York, NY, USA, 2007), PPoPP ’07, ACM, pp. 142–143.

2. Nethercote, N., and Seward, J. Valgrind: a framework for heavyweight dynamic binary instrumentation. In Proceedings of the 2007 ACM SIGPLAN conference on Programming language design and implementation (New York, NY, USA, 2007), PLDI ’07, ACM, pp. 89–100.

3. Netzer, R. H., and Miller, B. P. What are race conditions ? - some issues and formalizations. ACM Letters on Programming Languages and Systems 1 (1992), 74–88.

4. Serebryany, K., and Iskhodzhanov, T. ThreadSanitizer: data race detection in practice. In Proceedings of the Workshop on Binary Instrumentation and Applications (New York, NY, USA, 2009), WBIA ’09, ACM, pp. 62–71.

5. Serebryany, K., Potapenko, A., Iskhodzhanov, T., and Vyukov, D. Dynamic race detection with LLVM compiler — compile-time instrumentation for ThreadSanitizer. In Proceedings of the Runtime Verification (2011), RV ’11, Springer, pp. 110–114.

Mise à jour du 2013/09/22

L’outil tsan est maintenant intégré dans Clang (au moins depuis la 3.3, via l’option -fsanitize=thread) et GCC (depuis la 4.8, via l’option -fsanitize=thread)

Un autre outil intéressant (bien qu’étant dans une catégorie un peu différente), dont je n’ai pas parlé ici car je n’ai pas étudié son fonctionnement : le ReplayDebugger, basé sur GDB.