From b4e8e594c9505e9ed92f8932ecd384b51580c75c Mon Sep 17 00:00:00 2001 From: compudj Date: Thu, 27 Jan 2005 03:37:02 +0000 Subject: [PATCH] filter spec initial version git-svn-id: http://ltt.polymtl.ca/svn@859 04897980-b3bd-0310-b5e0-8ef037075253 --- .../developer/filter_specification.docbook | 502 ++++++++++++++++++ 1 file changed, 502 insertions(+) create mode 100644 ltt/branches/poly/doc/developer/filter_specification.docbook diff --git a/ltt/branches/poly/doc/developer/filter_specification.docbook b/ltt/branches/poly/doc/developer/filter_specification.docbook new file mode 100644 index 00000000..42a70d99 --- /dev/null +++ b/ltt/branches/poly/doc/developer/filter_specification.docbook @@ -0,0 +1,502 @@ + + + + + + + +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 soucis 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. + + + + + + + + + + -- 2.34.1