Spécifications du filtre de Linux Trace Toolkit Viewer
Mathieu
Desnoyers
26/01/2005
1.00.00
Ce document décrit les spécifications requises pour la fonctionnalité de
filtrage pour l'application
Linux Trace Toolkit Viewer.
Linux Trace Toolkit Viewer
spécification
filtre
specification
filter
Introduction
Le filtre de Linux Trace Toolkit Viewer est une fonctionnalité nécessaire pour
rendre l'outil pleinement utilisable. Des cas typiques de filtrage ont déjà été
identifiés : filtrer par CPU ou par ID d'événement.
Cependant, un utilisateur plus avancé peut vouloir filtrer selon n'importe quel
champs d'information disponible lors de la lecture d'un événement. L'approche
qui sera suivie, afin d'assurer l'applicabilité du filtrage aux différents types
de traces, sera de ne pas limiter les champs selon lesquels le filtrage pourra
être fait.
Comme le filtrage se fait à la lecture de chaque événement, il peut rapidement
devenir un goulot d'étranglement important. Les performances doivent donc être
un souci de taille lors de la réalisation de cette fonctionnalité. C'est
pourquoi l'architecture proposée se base sur une compilation des règles de
filtrage lors de leur définition afin de générer une structure de données
optimale pour le parcours de la trace.
Ce document explique les différents défis à surmonter dans les différents
sous-modules du filtre, soit : la partie "core" du filtre, qui sera intégrée,
comme son nom l'indique, au coeur de l'application ainsi que les parties
modulaires textes et graphiques. À la fin du document, des optimisations
éventuelles sont énoncées, sans plus. Elles pourront être utiles dans le cas où
les performances s'avéreraient problématiques.
Ce document est le fruit d'un échange entre Michel Dagenais et moi-même, Mathieu
Desnoyers. Certains passages sont laissés sous leur forme originale.
Design
Core
Application des règles de filtrage aux événements. Les règles de
filtrage pourraient être représentées par un arbre. Cette section du
filtrage est assez intégrée au reste de l'application pour mériter d'être
au coeur même de lttv (pas dans un module séparé). Les feuilles de l'arbre
sont des 3-tuples (champs, relation, valeur), alors que les noeuds
intermédiaires sont des relations logiques (and, or, xor, not). Le and, le
or et le xor sont limités à deux enfants, alors que le not est limité à un
seul enfant.
Les champs du 3-tuple devraient respecter une arborescence qui représente
l'organisation des données dans les événements. Celles-ci sont, lors de la
lecture de la trace, accessibles via les structures :
LttEvent (plus les champs spécifiques à l'événement)
LttvTracefile
LttvTrace
LttvTraceset
LttvState
On pourrait donc, au niveau de la description du champs, représenter
celui-ci par une chaîne de caractères imbriquable dont les niveaux sont
séparés par le ".". Voici la représentation des niveaux d'imbrication :
*
|->event (pour accéder aux champs sous LttEvent)
| |->name (string)
| |->category (string)
| |->time (LttTime)
| |->tsc (LttCycleCount)
| |->fields
| |->"event name"
| |->"field name"
| |->"sub-field name"
| |->...
| |->"leaf-field name" (field type)
|
|->tracefile
| |->name (string)
|->trace
| |->name (string)
|->state
|->pid (guint)
|->ppid (guint)
|->creation_time (LttTime)
|->insertion_time (LttTime)
|->process_name (string)
|->execution_mode (user_mode, syscall, trap, irq, unknown)
|->execution_submode (none, unknown)
|->process_status (wait_fork,wait_cpu,exit,zombie,wait,run,unnamed)
|->cpu (guint)
L'objet contenant l'arbre des règles de filtrage ainsi que la cache du filtre,
qu'on pourrait appeler "LttvFilter", serait associé à une trace, non pas à un
trace set, pour des raisons de performance. En effet, le même nom d'événement
peut très bien être associé à un ID différent d'une trace à l'autre. Comme on
ne souhaite pas faire la translation nom->id (qui est coûteuse) à chaque
utilisation du filtre, on le ferait lors de sa construction. Ceci implique de
garder un objet LttvFilter par trace. Rien n'empêche cependant d'avoir une
façon de créer, au niveau usager, des filtres pour toutes les traces d'un
traceset, mais ceux-ci seront associés à chaque trace du trace set.
Michel Dagenais :
Je m`inquiète beaucoup pour la performance. Il faut pouvoir précompiler
ces expressions en offset (ltt_field) et avoir un espèce d`index pour ne
pas passer séquentiellement à travers toutes les règles et pour chaque
règle interpréter les noms de champs à chaque événement traité!!
Mathieu Desnoyers :
C'est ce que j'avais en tête : fixer les positions des champs au moment de la
création de la règle de filtrage, quitte à la recalculer si jamais la trace
change en cours de route (mais ça ne devrait pas arriver, puisque les paires
(facility, event id) sont uniques au cours d'une trace).
Cependant, de la manière dont je vois ça, on aura pas le choix de se garder un
arbre représentant l'expression logique et de le parcourir séquentiellement pour
chaque événement. On peut évidemment éviter de balayer certaines branches en se
basant sur les relations and, or, xor lors du parcours.
Donc, je vois ça, dans le pire cas, comme un parcours infixe de l'arbre
représentant les règles. Chaque feuille serait une règle représentée par un
3-tuple (position, (type, relation), valeur), où chaque paire de (type,relation)
devrait être défini pour chaque type (possiblement incorrect, comme la relation
< sur un type string). Lors de la compilation, on passerait du 3-tuple (champs,
relation, valeur) à un 3-tuple (position, (type, relation), valeur).
À noter : un simple offset n'est en réalité pas assez pour représenter la
position, puisque toutes les données ne résident pas dans une seule structure.
Certaines sont dans le contexte (TracesetContext), d'autres dans la structure de
l'événement. Il faut donc décrire la position, en réalité, comme une paire
(structure, offset), où nous limitons structure aux noms de structure connus
(qui peuvent être encodés sur la forme de GQuarks) : {LTTV_TRACE,
LTTV_TRACEFILE, LTTV_TRACE_STATE, LTT_EVENT}.
Lors de la compilation, on a, en entrée, le tuple :
(champs, relation, valeur)
où champs est un tuple : (structure, offset, type)
On produit, en sortie, (toujours dans la même structure en arbre pour les
expressions logiques), les 3-tuples suivants (aux feuilles) :
(position, fonction, valeur)
où :
position = (structure, offset)
fonction = (type, relation)
Il me reste une question : que fait-on lors qu'un facility est rechargé en cours
de traçage ? Les événements vont-ils changer d'id ?
Michel Dagenais :
Non, c`est un nouveau facility avec le même nom mais un fingerprint
différent qui s`ajoute puisqu`il est possible que des modules utilisent
l`ancienne version alors que d`autres utilisent la nouvelle
simultanément. Il est possible que les règles ne spécifient que le nom
de la facilité auquel cas elles pourraient s`appliquer à toutes les
facilités du même nom et demanderaient d`avoir une précompilation
différente pour chaque facilité.
Mathieu Desnoyers :
J'en conclue que le 2-tuple (facility, event id) est unique pour la trace, c'est
ça ?
Michel Dagenais :
> Oui.
Module texte
Lecture d'une chaîne de caractères formée d'expressions
booléennes qui décrivent le filtre à partir des opérations de base :
and, or, xor, not
et de parenthèses : ( et ).
Les entrées logiques de ce filtre sont composées 3-tuples
(champs, relation, valeur),
où le champs est le type d'information (i.e. pid)
la relation est la limite sur la valeur (i.e. <)
la valeur est la valeur qui doit être respectée par le champs selon la
relation. Doit être du type associé au champs. À priori, on utilise
le type de champs pour savoir sous quel type encoder l'information
lue, tout en vérifiant le contenu de la chaîne lue pour des
débordements (overflow) avant encodage vers le type associé.
La lecture de cette expression booléenne formerait un arbre de règles de
filtrage, qui serait ensuite utilisé par la partie "core" de filtrage de
lttv pour être appliqué aux événements lors de la lecture de trace.
Module graphique
Une classe filtre graphique serait associée à un arbre
de règles de filtrage. On pourrait le modifier les objets de la classe
filtre graphique en invoquant une fenêtre de modification de filtre qui
permettrait d'entrer les spécifications du filtre à l'aide de champs
graphiques de sélection (drop down list) pour les types d'éléments selon
lesquels filtrer, et d'un champs d'entrée de texte libre pour spécifier la
valeur que ce champs doit prendre. La relation qui doit être appliquée
(<, >, <=, >=, =) doit être sélectionnée dans un autre drop-down list.
En plus de la sélection graphique, l'entrée d'une chaîne de caractère serait
possible pour spécifier le filtre selon l'entrée décrite ci-haut pour le
module texte.
Michel Dagenais :
Oui, à la rigueur la partie graphique n`est probablement pas tellement
plus difficile que celle textuelle. On pourrait commencer avec seulement
la partie graphique qui produit directement la représentation en arbre.
Mathieu Desnoyers :
Comme je prévois réutiliser l'entrée texte à l'intérieur de la fenêtre
graphique, je crois qu'il est préférable de commencer par l'entrée texte.
D'ailleurs, l'avantage pour quelqu'un qui commence à contribuer au projet est de
ne pas avoir à apprendre l'API de GTK en même temps qu'il fait le développement
de son module. Il est un peu trop facile de ne pas assez découpler la logique
interne de la présentation.
Michel Dagenais :
Le cas classique est de choisir un CPU ou un type d`événement, auquel
cas un menu simple de CPU et type serait beaucoup plus pratique que
d`avoir à taper une expression.
Mathieu Desnoyers :
On pourrait penser à faire un module graphique de création de filtre de base,
pour les fonctionnalités les plus utilisées. Celui-ci pourra être étendu par
la suite, si besoin est. L'intérêt est d'avoir quand-même la possibilité, pour
un utilisateur plus avancé, de spécifier toutes les caractéristiques via
l'interface. Dans ce cas, quelqu'un serait tout-à-fait prêt à faire une
expression pour décrire en détail son filtre. C'est quand-même quelque chose de
plus en plus commun avec la venue des moteurs de recherche.
Choix de syntaxe, documentation et messages d'erreur
Michel Dagenais :
Oui, une partie non négligeable est un choix de syntaxe convivial, la
documentation et les messages d`erreur...
Mathieu Desnoyers :
C'est bel et bien ce qui sera perçu par l'utilisateur, de là l'importance..
Je me demande s'il est mieux d'adopter une syntaxe un peu à la Google ou bien à
la C :
(, ), and, or, xor, not, field op value
où op peut prendre : <, >, <=, >=, =
ou bien à la C
(, ), &, |, ^, !, field op value
Ou bien on peut faire un alphabet mixte entre les deux, où les mots and et &
seraient équivalents. Ce serait probablement plus facile de reconnaître les
symboles comme & par contre, et moins limitant sur le traitement du mot
identifiant le field.
Mais cette question est de moindre importance : tant qu'on se fixe un standard
et qu'on le documente, je crois qu'il n'y a pas vraiment de mauvais choix.
Pour la documentation, l'ajout d'une section au guide de l'utilisateur (déjà en
docbook) me semble très adéquat.
Pour les messages d'erreur, il faudra entres autres penser à valider les
opération par rapport à celles permises pour chaque type. Par exemple, un > n'a
pas vraiment de sens pour un string.
Michel Dagenais :
Je tendrais à prendre la syntaxe C.
Mathieu Desnoyers :
Si on utilise de manière stricte la syntaxe C, il faudrait utiliser ceci :
&&, ||, ==, (rien pour le xor logique ?)
Je me dis que, puisque nous n'avons pas besoin des opérations "bitwise", nous
pourrions utiliser celles-ci.
Donc, ce que je propose, est d'utiliser l'alphabet utilisé pour les opérateurs
bitwise du C en tant qu'opérateurs logiques pour notre parser d'expressions de
filtre :
&, |, =, ^
Ceci est un détail sémantique, mais je veux juste m'assurer qu'on est d'accord.
Optimisation éventuelles
"Cache" de filtre, afin d'optimiser le cas courant.
Au niveau de la partie "core" du filtrage, on pourrait faire une hash
table indexée par une clé formée d'un xor des champs à filtrer. Alors, si un
événement possède les même caractéristiques de filtrage, on pourrait accéder à
la solution (V/F) en O(1). Le coût est de calculer la clé de hashage pour
chaque événement. L'avantage apparaît lorsqu'il y a plusieurs critères de
filtrage à comparer. La remise à zéro de cette cache devrait être faite
lorsqu'il y a des modifications au filtre.
Michel Dagenais :
Les travaux sur l`optimisation de requêtes dans les bases de données est
probablement pertinent pour ce genre de choses.
Mathieu Desnoyers :
Il faudra que je m'y arrête. Cependant, ceci constitue une optimisation et n'est
donc pas crucial pour le fonctionnement.
Michel Dagenais :
Sauf si c`est inutilisable sans une telle optimisation :-).
Mathieu Desnoyers :
N'est-ce pas toi qui m'a déjà dit, citant Donald Knuth : "Premature
optimisation is the root of all evil" ? :)
Effectivement, si on s'aperçoit que c'est trop lent, il faudra passer à cette
étape.