Points de trace rapides et efficaces par injection adaptative de sauts en x86

Le traçage est une technique efficace pour analyser la performance des systèmes complexes et parallèles. Il permet d'enregistrer les évènements du programme client dans une trace lorsqu'ils sont déclenchés par des points de trace. Dans les systèmes à fils d'exécution multiples, les évènements peuvent être déclenchés simultanément et apparaissent donc dans un ordre indéfini. Un point de trace avec un grand surcoût d'exécution peut changer l'ordre dans lequel les évènements apparaissent dans la trace. En conséquence, de grands problèmes de performance peuvent être masqués dans la trace. La plupart des techniques d'instrumentation existantes, soit sont trop intrusives pour le programme client (l'arrêtent complètement pour insérer l'instrumentation), soit ajoutent un grand surcoût d'exécution. Dans ce mémoire, nous présentons un point de trace rapide en x86 nommé NOProbe. Il utilise différentes stratégies d'instrumentation rapide dans le but d'augmenter l'efficacité. Pour l'une de ces stratégies, nous exploitons les rembourrages de NOP insérés par les compilateurs pour optimiser l'alignement du code. Pour exploiter le maximum possible de rembourrages sans affecter la performance, deux algorithmes sont proposés. Le premier est un algorithme glouton qui met l'accent sur la performance, ce qui le rend un choix intéressant pour l'instrumentation en lot. Le deuxième est localement optimal et sacrifie un peu de performance pour plus d'optimalité. Pour limiter l'intrusion durant l'insertion du point de trace. Un algorithme de modification de code simultané et adapté à l'espace utilisateur, nommé Lock and Load, a été présenté. Sans arrêter le programme client et durant l'exécution, NOProbe se sert de l'algorithme Lock and Load pour insérer dynamiquement l'instrumentation. L'algorithme peut modifier le code d'un bloc de base tout entier. D'abord, la première instruction du bloc est remplacée par une instruction d'interruption logicielle pour le verrouiller. Ensuite, les fils d'exécution à l'intérieur sont redirigés en dehors du bloc avant de le modifier. Finalement, avant de déverrouiller la zone modifiée, tous les coeurs des CPU qui roulent les fils d'exécution du processus client sont sérialisés. Notre solution offre un surcoût d'exécution très bas. Le coût d'insertion est 6 fois moins important que celui de Uprobe lorsque le nombre de fils d'exécution du programme instrumenté est inférieur à 16. Il est beaucoup moins important comparé a Dyninst. Malgré le fait que le coût d'insertion ne s'adapte pas bien au nombre de fils d'exécution dans le pire cas, notre technique surpasse en moyenne les autres techniques d'insertion dynamique.

Abstract

Tracing is an effective technique to analyze the performance of complex multi-thread programs. A program trace consists of a series of events written by probes. The performance of a probe insertion and execution is very important for analyzing high-performance online systems. Existing techniques are either limited in scope, too intrusive or costly in overhead, limiting their applicability in many cases. We introduce a new instrumentation technique for the x86 architecture, named NOProbe (NOP Probe), that exploits several complementary strategies in order to achieve a higher success rate in insertion of fast jump based probes at different locations in a binary. For one of these strategies, we exploit NOP-paddings inserted by compilers to optimize the code alignment. To achieve this goal, two new algorithms are introduced to assign paddings to probes. One is greedy and emphasizes performance, while the other attempts to locally optimize the assignation of paddings to probes in a function. We also propose an improved algorithm (Lock and Load) used by NOProbe to dynamically insert probes on the fly. The algorithm can patch a whole basic block by locking it with a trap instruction before redirecting the thread out of it. Next, the basic block is patched and the cores are serialized before unlocking it. The experimental results demonstrate that our approach not only achieves a higher success rate for fast probes insertion and maintains a very low execution overhead, but outperforms competing techniques.