1 <?xml version="1.0" encoding="UTF-8" ?>
2 <!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.3//EN"
3 "/usr/share/sgml/docbook/dtd/4.3/xdocbook.dtd">
4 <!--<!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.2//EN" >-->
9 <title>Spécifications du filtre de Linux Trace Toolkit Viewer</title>
12 <firstname>Mathieu</firstname>
13 <surname>Desnoyers</surname>
17 <date>26/01/2005</date>
18 <releaseinfo>1.00.00</releaseinfo>
22 Ce document décrit les spécifications requises pour la fonctionnalité de
23 filtrage pour l'application
24 <application>Linux Trace Toolkit Viewer</application>.
30 <keyword>Linux Trace Toolkit Viewer</keyword>
31 <keyword>spécification</keyword>
32 <keyword>filtre</keyword>
33 <keyword>specification</keyword>
34 <keyword>filter</keyword>
39 <title>Introduction</title>
42 Le filtre de Linux Trace Toolkit Viewer est une fonctionnalité nécessaire pour
43 rendre l'outil pleinement utilisable. Des cas typiques de filtrage ont déjà été
44 identifiés : filtrer par CPU ou par ID d'événement.
47 Cependant, un utilisateur plus avancé peut vouloir filtrer selon n'importe quel
48 champs d'information disponible lors de la lecture d'un événement. L'approche
49 qui sera suivie, afin d'assurer l'applicabilité du filtrage aux différents types
50 de traces, sera de ne pas limiter les champs selon lesquels le filtrage pourra
54 Comme le filtrage se fait à la lecture de chaque événement, il peut rapidement
55 devenir un goulot d'étranglement important. Les performances doivent donc être
56 un souci de taille lors de la réalisation de cette fonctionnalité. C'est
57 pourquoi l'architecture proposée se base sur une compilation des règles de
58 filtrage lors de leur définition afin de générer une structure de données
59 optimale pour le parcours de la trace.
62 Ce document explique les différents défis à surmonter dans les différents
63 sous-modules du filtre, soit : la partie "core" du filtre, qui sera intégrée,
64 comme son nom l'indique, au coeur de l'application ainsi que les parties
65 modulaires textes et graphiques. À la fin du document, des optimisations
66 éventuelles sont énoncées, sans plus. Elles pourront être utiles dans le cas où
67 les performances s'avéreraient problématiques.
70 Ce document est le fruit d'un échange entre Michel Dagenais et moi-même, Mathieu
71 Desnoyers. Certains passages sont laissés sous leur forme originale.
84 Application des règles de filtrage aux événements. Les règles de
85 filtrage pourraient être représentées par un arbre. Cette section du
86 filtrage est assez intégrée au reste de l'application pour mériter d'être
87 au coeur même de lttv (pas dans un module séparé). Les feuilles de l'arbre
88 sont des 3-tuples (champs, relation, valeur), alors que les noeuds
89 intermédiaires sont des relations logiques (and, or, xor, not). Le and, le
90 or et le xor sont limités à deux enfants, alors que le not est limité à un
94 Les champs du 3-tuple devraient respecter une arborescence qui représente
95 l'organisation des données dans les événements. Celles-ci sont, lors de la
96 lecture de la trace, accessibles via les structures :
99 <listitem><para>LttEvent (plus les champs spécifiques à l'événement)</para></listitem>
100 <listitem><para>LttvTracefile</para></listitem>
101 <listitem><para>LttvTrace</para></listitem>
102 <listitem><para>LttvTraceset</para></listitem>
103 <listitem><para>LttvState</para></listitem>
106 On pourrait donc, au niveau de la description du champs, représenter
107 celui-ci par une chaîne de caractères imbriquable dont les niveaux sont
108 séparés par le ".". Voici la représentation des niveaux d'imbrication :
111 <literallayout class="monospaced">
113 |->event (pour accéder aux champs sous LttEvent)
115 | |->category (string)
117 | |->tsc (LttCycleCount)
121 | |->"sub-field name"
123 | |->"leaf-field name" (field type)
132 |->creation_time (LttTime)
133 |->insertion_time (LttTime)
134 |->process_name (string)
135 |->execution_mode (user_mode, syscall, trap, irq, unknown)
136 |->execution_submode (none, unknown)
137 |->process_status (wait_fork,wait_cpu,exit,zombie,wait,run,unnamed)
143 L'objet contenant l'arbre des règles de filtrage ainsi que la cache du filtre,
144 qu'on pourrait appeler "LttvFilter", serait associé à une trace, non pas à un
145 trace set, pour des raisons de performance. En effet, le même nom d'événement
146 peut très bien être associé à un ID différent d'une trace à l'autre. Comme on
147 ne souhaite pas faire la translation nom->id (qui est coûteuse) à chaque
148 utilisation du filtre, on le ferait lors de sa construction. Ceci implique de
149 garder un objet LttvFilter par trace. Rien n'empêche cependant d'avoir une
150 façon de créer, au niveau usager, des filtres pour toutes les traces d'un
151 traceset, mais ceux-ci seront associés à chaque trace du trace set.
158 Je m`inquiète beaucoup pour la performance. Il faut pouvoir précompiler
159 ces expressions en offset (ltt_field) et avoir un espèce d`index pour ne
160 pas passer séquentiellement à travers toutes les règles et pour chaque
161 règle interpréter les noms de champs à chaque événement traité!!
168 C'est ce que j'avais en tête : fixer les positions des champs au moment de la
169 création de la règle de filtrage, quitte à la recalculer si jamais la trace
170 change en cours de route (mais ça ne devrait pas arriver, puisque les paires
171 (facility, event id) sont uniques au cours d'une trace).
175 Cependant, de la manière dont je vois ça, on aura pas le choix de se garder un
176 arbre représentant l'expression logique et de le parcourir séquentiellement pour
177 chaque événement. On peut évidemment éviter de balayer certaines branches en se
178 basant sur les relations and, or, xor lors du parcours.
182 Donc, je vois ça, dans le pire cas, comme un parcours infixe de l'arbre
183 représentant les règles. Chaque feuille serait une règle représentée par un
184 3-tuple (position, (type, relation), valeur), où chaque paire de (type,relation)
185 devrait être défini pour chaque type (possiblement incorrect, comme la relation
186 < sur un type string). Lors de la compilation, on passerait du 3-tuple (champs,
187 relation, valeur) à un 3-tuple (position, (type, relation), valeur).
191 À noter : un simple offset n'est en réalité pas assez pour représenter la
192 position, puisque toutes les données ne résident pas dans une seule structure.
193 Certaines sont dans le contexte (TracesetContext), d'autres dans la structure de
194 l'événement. Il faut donc décrire la position, en réalité, comme une paire
195 (structure, offset), où nous limitons structure aux noms de structure connus
196 (qui peuvent être encodés sur la forme de GQuarks) : {LTTV_TRACE,
197 LTTV_TRACEFILE, LTTV_TRACE_STATE, LTT_EVENT}.
201 Lors de la compilation, on a, en entrée, le tuple :
205 (champs, relation, valeur)
209 où champs est un tuple : (structure, offset, type)
213 On produit, en sortie, (toujours dans la même structure en arbre pour les
214 expressions logiques), les 3-tuples suivants (aux feuilles) :
218 (position, fonction, valeur)
223 <simplelist type="inline">
224 <member>position = (structure, offset)</member>
225 <member>fonction = (type, relation)</member>
230 Il me reste une question : que fait-on lors qu'un facility est rechargé en cours
231 de traçage ? Les événements vont-ils changer d'id ?
238 Non, c`est un nouveau facility avec le même nom mais un fingerprint
239 différent qui s`ajoute puisqu`il est possible que des modules utilisent
240 l`ancienne version alors que d`autres utilisent la nouvelle
241 simultanément. Il est possible que les règles ne spécifient que le nom
242 de la facilité auquel cas elles pourraient s`appliquer à toutes les
243 facilités du même nom et demanderaient d`avoir une précompilation
244 différente pour chaque facilité.
251 J'en conclue que le 2-tuple (facility, event id) est unique pour la trace, c'est
264 <title>Module texte</title>
267 Lecture d'une chaîne de caractères formée d'expressions
268 booléennes qui décrivent le filtre à partir des opérations de base :
270 et de parenthèses : ( et ).
271 Les entrées logiques de ce filtre sont composées 3-tuples
272 (champs, relation, valeur),
273 où le champs est le type d'information (i.e. pid)
274 la relation est la limite sur la valeur (i.e. <)
275 la valeur est la valeur qui doit être respectée par le champs selon la
276 relation. Doit être du type associé au champs. À priori, on utilise
277 le type de champs pour savoir sous quel type encoder l'information
278 lue, tout en vérifiant le contenu de la chaîne lue pour des
279 débordements (overflow) avant encodage vers le type associé.
280 La lecture de cette expression booléenne formerait un arbre de règles de
281 filtrage, qui serait ensuite utilisé par la partie "core" de filtrage de
282 lttv pour être appliqué aux événements lors de la lecture de trace.
288 <title>Module graphique</title>
291 Une classe filtre graphique serait associée à un arbre
292 de règles de filtrage. On pourrait le modifier les objets de la classe
293 filtre graphique en invoquant une fenêtre de modification de filtre qui
294 permettrait d'entrer les spécifications du filtre à l'aide de champs
295 graphiques de sélection (drop down list) pour les types d'éléments selon
296 lesquels filtrer, et d'un champs d'entrée de texte libre pour spécifier la
297 valeur que ce champs doit prendre. La relation qui doit être appliquée
298 (<, >, <=, >=, =) doit être sélectionnée dans un autre drop-down list.
299 En plus de la sélection graphique, l'entrée d'une chaîne de caractère serait
300 possible pour spécifier le filtre selon l'entrée décrite ci-haut pour le
308 Oui, à la rigueur la partie graphique n`est probablement pas tellement
309 plus difficile que celle textuelle. On pourrait commencer avec seulement
310 la partie graphique qui produit directement la représentation en arbre.
317 Comme je prévois réutiliser l'entrée texte à l'intérieur de la fenêtre
318 graphique, je crois qu'il est préférable de commencer par l'entrée texte.
319 D'ailleurs, l'avantage pour quelqu'un qui commence à contribuer au projet est de
320 ne pas avoir à apprendre l'API de GTK en même temps qu'il fait le développement
321 de son module. Il est un peu trop facile de ne pas assez découpler la logique
322 interne de la présentation.
329 Le cas classique est de choisir un CPU ou un type d`événement, auquel
330 cas un menu simple de CPU et type serait beaucoup plus pratique que
331 d`avoir à taper une expression.
337 On pourrait penser à faire un module graphique de création de filtre de base,
338 pour les fonctionnalités les plus utilisées. Celui-ci pourra être étendu par
339 la suite, si besoin est. L'intérêt est d'avoir quand-même la possibilité, pour
340 un utilisateur plus avancé, de spécifier toutes les caractéristiques via
341 l'interface. Dans ce cas, quelqu'un serait tout-à-fait prêt à faire une
342 expression pour décrire en détail son filtre. C'est quand-même quelque chose de
343 plus en plus commun avec la venue des moteurs de recherche.
349 <title>Choix de syntaxe, documentation et messages d'erreur</title>
354 Oui, une partie non négligeable est un choix de syntaxe convivial, la
355 documentation et les messages d`erreur...
361 C'est bel et bien ce qui sera perçu par l'utilisateur, de là l'importance..
364 Je me demande s'il est mieux d'adopter une syntaxe un peu à la Google ou bien à
369 (, ), and, or, xor, not, field op value
370 où op peut prendre : <, >, <=, >=, =
375 (, ), &, |, ^, !, field op value
380 Ou bien on peut faire un alphabet mixte entre les deux, où les mots and et &
381 seraient équivalents. Ce serait probablement plus facile de reconnaître les
382 symboles comme & par contre, et moins limitant sur le traitement du mot
383 identifiant le field.
387 Mais cette question est de moindre importance : tant qu'on se fixe un standard
388 et qu'on le documente, je crois qu'il n'y a pas vraiment de mauvais choix.
392 Pour la documentation, l'ajout d'une section au guide de l'utilisateur (déjà en
393 docbook) me semble très adéquat.
397 Pour les messages d'erreur, il faudra entres autres penser à valider les
398 opération par rapport à celles permises pour chaque type. Par exemple, un > n'a
399 pas vraiment de sens pour un string.
407 Je tendrais à prendre la syntaxe C.
414 Si on utilise de manière stricte la syntaxe C, il faudrait utiliser ceci :
418 &&, ||, ==, (rien pour le xor logique ?)
422 Je me dis que, puisque nous n'avons pas besoin des opérations "bitwise", nous
423 pourrions utiliser celles-ci.
427 Donc, ce que je propose, est d'utiliser l'alphabet utilisé pour les opérateurs
428 bitwise du C en tant qu'opérateurs logiques pour notre parser d'expressions de
437 Ceci est un détail sémantique, mais je veux juste m'assurer qu'on est d'accord.
444 <title>Optimisation éventuelles</title>
448 "Cache" de filtre, afin d'optimiser le cas courant.
449 Au niveau de la partie "core" du filtrage, on pourrait faire une hash
450 table indexée par une clé formée d'un xor des champs à filtrer. Alors, si un
451 événement possède les même caractéristiques de filtrage, on pourrait accéder à
452 la solution (V/F) en O(1). Le coût est de calculer la clé de hashage pour
453 chaque événement. L'avantage apparaît lorsqu'il y a plusieurs critères de
454 filtrage à comparer. La remise à zéro de cette cache devrait être faite
455 lorsqu'il y a des modifications au filtre.
462 Les travaux sur l`optimisation de requêtes dans les bases de données est
463 probablement pertinent pour ce genre de choses.
470 Il faudra que je m'y arrête. Cependant, ceci constitue une optimisation et n'est
471 donc pas crucial pour le fonctionnement.
479 Sauf si c`est inutilisable sans une telle optimisation :-).
486 N'est-ce pas toi qui m'a déjà dit, citant Donald Knuth : "Premature
487 optimisation is the root of all evil" ? :)
491 Effectivement, si on s'aperçoit que c'est trop lent, il faudra passer à cette
projects / lttv.git / blob