From 9895df71ae6ea14e09478cc243227b7b3a2139a3 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sat, 26 Mar 2016 20:56:04 +0100 Subject: Extracted the logic of code nodes for better processing. --- ChangeLog | 16 ++ src/analysis/disass/Makefile.am | 1 + src/analysis/disass/dragon.c | 541 ++++++++++++++++++++++++++++++++++++++++ src/analysis/disass/dragon.h | 81 ++++++ src/analysis/disass/loop.c | 366 +++------------------------ src/common/bits.c | 2 +- src/common/bits.h | 2 +- 7 files changed, 675 insertions(+), 334 deletions(-) create mode 100644 src/analysis/disass/dragon.c create mode 100644 src/analysis/disass/dragon.h diff --git a/ChangeLog b/ChangeLog index 234f547..dc07b31 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,19 @@ +16-03-26 Cyrille Bagard + + * src/analysis/disass/Makefile.am: + Add the 'dragon.[ch]' files to libanalysisdisass_la_SOURCES. + + * src/analysis/disass/dragon.c: + * src/analysis/disass/dragon.h: + New entries: extract the logic of code nodes for better processing. + + * src/analysis/disass/loop.c: + Update code. + + * src/common/bits.c: + * src/common/bits.h: + Mark bit fields as constant when needed. + 16-03-24 Cyrille Bagard * src/gui/editem.c: diff --git a/src/analysis/disass/Makefile.am b/src/analysis/disass/Makefile.am index 54b0fa5..3231749 100644 --- a/src/analysis/disass/Makefile.am +++ b/src/analysis/disass/Makefile.am @@ -4,6 +4,7 @@ noinst_LTLIBRARIES = libanalysisdisass.la libanalysisdisass_la_SOURCES = \ area.h area.c \ disassembler.h disassembler.c \ + dragon.h dragon.c \ fetch.h fetch.c \ limit.h limit.c \ links.h links.c \ diff --git a/src/analysis/disass/dragon.c b/src/analysis/disass/dragon.c new file mode 100644 index 0000000..2fcf830 --- /dev/null +++ b/src/analysis/disass/dragon.c @@ -0,0 +1,541 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * dragon.c - capacités apportées par la lecture du livre du dragon + * + * Copyright (C) 2016 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * OpenIDA is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * OpenIDA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Foobar. If not, see . + */ + + +#include "dragon.h" + + +#include +#include + + + +/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */ + + +/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ +struct _dragon_node +{ + GArchInstruction *first; /* Arrivée d'un lien (début) */ + GArchInstruction *last; /* Départ d'un lien (fin) */ + + bitfield_t *bits; /* Représentation par masque */ + +}; + + +/* Définition des blocs d'allocation */ +#define NODE_ALLOC_SIZE 100 + + +/* Dénombre le nombre de noeuds présents dans une routine. */ +static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *); + +/* Supprime de la mémoire tous les noeuds détectés. */ +static void delete_dragon_nodes(dragon_node *, size_t); + +/* Termine l'initialisation de noeuds trouvés dans une routine. */ +static void init_mask_for_nodes(dragon_node *, size_t); + + + +/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */ + + +/* Concentration de tous les efforts */ +struct _dragon_knight +{ + dragon_node *nodes; /* Noeuds mis en place */ + size_t count; /* Taille de la liste */ + +}; + + + +/* ---------------------------------------------------------------------------------- */ +/* DECOUPAGES DE CODE EN NOEUDS */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* count = taille de la liste de noeuds retournés. [OUT] * +* * +* Description : Dénombre le nombre de noeuds présents dans une routine. * +* * +* Retour : Liste de noeuds initialisés de façon incomplète. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count) +{ + dragon_node *result; /* Liste à créer et renvoyer */ + size_t allocated; /* Dimensionnement en mémoire */ + GArchInstruction *last; /* Mémorisation du passé */ + GArchInstruction *iter; /* Boucle de parcours */ + const mrange_t *irange; /* Emplacement d'instruction */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de dest. */ + size_t i; /* Boucle de parcours */ + dragon_node *new; /* Nouvel élément à créer */ + + result = NULL; + *count = 0; + + allocated = 0; + + for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start); + iter != NULL; + last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0)) + { + /* L'instruction sort-elle des clous ? */ + + irange = g_arch_instruction_get_range(iter); + + if (!mrange_contains_mrange(range, irange)) + break; + + /* Analyse des sources */ + + if (result == NULL) + { + (*count)++; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + } + else + { + scount = g_arch_instruction_get_sources(iter, NULL, &types); + if (scount == 0) continue; + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + if (*count > 0) + result[*count - 1].last = last; + + (*count)++; + i = scount; + + if (*count >= allocated) + { + allocated += NODE_ALLOC_SIZE; + result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); + } + + new = &result[*count - 1]; + + new->first = iter; + + break; + + default: + break; + + } + + } + + } + + if (*count > 0) + result[*count - 1].last = last; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Supprime de la mémoire tous les noeuds détectés. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void delete_dragon_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + delete_bit_field(nodes[i].bits); + + free(nodes); + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Termine l'initialisation de noeuds trouvés dans une routine. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_mask_for_nodes(dragon_node *nodes, size_t count) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < count; i++) + nodes[i].bits = create_bit_field(count, i > 0); + + set_in_bit_field(nodes[0].bits, 0, 1); + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud de code à considérer. * +* first = instruction de départ à renseigner ou NULL. [OUT] * +* last = instruction d'arrivée à renseigner ou NULL. [OUT] * +* * +* Description : Fournit les instructions bornant un noeud de code. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void get_dragon_node_bounding_instructions(dragon_node *node, GArchInstruction **first, GArchInstruction **last) +{ + if (first != NULL) + *first = node->first; + + if (last != NULL) + *last = node->last; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* * +* Description : Fournit un noeud particulier à partir d'une liste. * +* * +* Retour : Noeud ciblé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_node *get_dragon_node(dragon_node *nodes, size_t index) +{ + return nodes + index; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* node = noeud ciblé au sein de cette liste. * +* * +* Description : Fournit l'indice d'un noeud particulier à partir d'une liste.* +* * +* Retour : Indice du noeud ciblé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +size_t get_dragon_node_index(dragon_node *nodes, dragon_node *node) +{ + return node - nodes; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à parcourir. * +* final = précise si l'instruction visée est la première. * +* instr = instruction à retrouver en tant que début de noeud. * +* * +* Description : Recherche un noeud selon son intruction de départ. * +* * +* Retour : Noeud trouvé ou NULL si aucune trouvaille. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr) +{ + dragon_node *result; /* Résultat des recherches */ + const mrange_t *irange; /* Emplacement d'instruction */ + + int find_node_from_range(const mrange_t *range, const dragon_node *node) + { + int status; /* Bilan à retourner */ + const mrange_t *nrange; /* Emplacement de noeud */ + + nrange = g_arch_instruction_get_range(final ? node->last : node->first); + + status = cmp_mrange(range, nrange); + + return status; + + } + + irange = g_arch_instruction_get_range(instr); + + result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : nodes = liste de noeuds détectés dans une routine. * +* count = taille de cette liste de noeuds à traiter. * +* * +* Description : Détermine toute la chaîne hiérarchique de domination. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void compute_all_dominators(dragon_node *nodes, size_t count) +{ + bitfield_t *inter; /* Intersection de dominations */ + bool changed; /* Note un changement qq part */ + size_t k; /* Boucle de parcours #1 */ + dragon_node *node; /* Noeud à traiter */ + dragon_node *predecessor; /* Noeud prédécesseur direct */ + GArchInstruction **srcs; /* Instructions d'origine */ + InstructionLinkType *types; /* Type de lien entre instr. */ + size_t scount; /* Nombre de liens de source */ + size_t i; /* Boucle de parcours #2 */ + + inter = create_bit_field(count, false); + + do + { + changed = false; + + for (k = 1; k < count; k++) + { + node = &nodes[k]; + + set_all_in_bit_field(inter); + + scount = g_arch_instruction_get_sources(node->first, &srcs, &types); + assert(scount > 0); + + for (i = 0; i < scount; i++) + switch (types[i]) + { + case ILT_EXEC_FLOW: + case ILT_JUMP: + case ILT_CASE_JUMP: + case ILT_JUMP_IF_TRUE: + case ILT_JUMP_IF_FALSE: + + predecessor = find_node_for_instruction(nodes, count, true, srcs[i]); + + + printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n", + (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual, + predecessor); + + + + if (predecessor == NULL) break; + + and_bit_field(inter, predecessor->bits); + break; + + default: + break; + + } + + set_in_bit_field(inter, k, 1); + + if (!is_bit_field_equal_to(node->bits, inter)) + { + copy_bit_field(node->bits, inter); + changed = true; + } + + } + + } + while (changed); + + delete_bit_field(inter); + +} + + +/****************************************************************************** +* * +* Paramètres : node = noeud représentant une portion de code à consulter. * +* * +* Description : Fournit la liste des noeuds dominés par un noeud. * +* * +* Retour : Champ de bits en place. * +* * +* Remarques : - * +* * +******************************************************************************/ + +const bitfield_t *get_domination_bits(const dragon_node *node) +{ + return node->bits; + +} + + + + + + +/* ---------------------------------------------------------------------------------- */ +/* ENCAPSULATION DES NOEUDS */ +/* ---------------------------------------------------------------------------------- */ + + +/****************************************************************************** +* * +* Paramètres : proc = ensemble d'instructions à parcourir. * +* coverage = zone de couverture où rechercher des instructions.* +* range = zone de couverture de la routine analysée. * +* start = adresse du début de l'analyse. * +* * +* Description : Attaque la complexité d'un code en créant des noeuds. * +* * +* Retour : Définition d'un complexe de noeuds établis. * +* * +* Remarques : - * +* * +******************************************************************************/ + +dragon_knight *begin_dragon_knight(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start) +{ + dragon_knight *result; /* Données à retourner */ + dragon_node *nodes; /* Noeuds mis en place */ + size_t count; /* Nombre de ces noeuds */ + + result = NULL; + + nodes = create_dragon_nodes(proc, coverage, range, start, &count); + + if (nodes != NULL) + { + init_mask_for_nodes(nodes, count); + + result = (dragon_knight *)calloc(1, sizeof(dragon_knight)); + + result->nodes = nodes; + result->count = count; + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : knight = données représentant une complexité traitée. * +* * +* Description : Supprime de la mémoire les données d'une complexité de code. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void end_dragon_knight(dragon_knight *knight) +{ + delete_dragon_nodes(knight->nodes, knight->count); + + free(knight); + +} + + +/****************************************************************************** +* * +* Paramètres : knight = données représentant une complexité à considérer. * +* nodes = noeuds de code associés à récupérer. [OUT] * +* count = taille de cette liste de noeuds. [OUT] * +* * +* Description : Fournit les éléments utiles à un traitement de blocs de code.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +void get_dragon_knight_content(dragon_knight *knight, dragon_node **nodes, size_t *count) +{ + *nodes = knight->nodes; + *count = knight->count; + +} diff --git a/src/analysis/disass/dragon.h b/src/analysis/disass/dragon.h new file mode 100644 index 0000000..c6f6fd5 --- /dev/null +++ b/src/analysis/disass/dragon.h @@ -0,0 +1,81 @@ + +/* Chrysalide - Outil d'analyse de fichiers binaires + * dragon.h - prototypes pour les capacités apportées par la lecture du livre du dragon + * + * Copyright (C) 2016 Cyrille Bagard + * + * This file is part of Chrysalide. + * + * OpenIDA is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * OpenIDA is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License + * along with Foobar. If not, see . + */ + + +#ifndef _ANALYSIS_DISASS_DRAGON_H +#define _ANALYSIS_DISASS_DRAGON_H + + +#include "../../arch/processor.h" +#include "../../common/bits.h" + + + +/* -------------------------- DECOUPAGES DE CODE EN NOEUDS -------------------------- */ + + +/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ +typedef struct _dragon_node dragon_node; + + +/* Fournit les instructions bornant un noeud de code. */ +void get_dragon_node_bounding_instructions(dragon_node *, GArchInstruction **, GArchInstruction **); + +/* Fournit un noeud particulier à partir d'une liste. */ +dragon_node *get_dragon_node(dragon_node *, size_t); + +/* Fournit l'indice d'un noeud particulier à partir d'une liste. */ +size_t get_dragon_node_index(dragon_node *, dragon_node *); + +/* Recherche un noeud selon son intruction de départ. */ +dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *); + +/* Détermine toute la chaîne hiérarchique de domination. */ +void compute_all_dominators(dragon_node *, size_t); + +/* Fournit la liste des noeuds dominés par un noeud. */ +const bitfield_t *get_domination_bits(const dragon_node *); + + + + + + +/* ---------------------------- ENCAPSULATION DES NOEUDS ---------------------------- */ + + +/* Concentration de tous les efforts */ +typedef struct _dragon_knight dragon_knight; + + +/* Attaque la complexité d'un code en créant des noeuds. */ +dragon_knight *begin_dragon_knight(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *); + +/* Supprime de la mémoire les données d'une complexité de code. */ +void end_dragon_knight(dragon_knight *); + +/* Fournit les éléments utiles à un traitement de blocs de code. */ +void get_dragon_knight_content(dragon_knight *, dragon_node **, size_t *); + + + +#endif /* _ANALYSIS_DISASS_DRAGON_H */ diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c index 94916f7..dd0b661 100644 --- a/src/analysis/disass/loop.c +++ b/src/analysis/disass/loop.c @@ -28,39 +28,14 @@ #include -#include "../../common/bits.h" - - - -/* Description de noeud, en référence à "Compilers: Principles, Techniques, and Tools" */ -typedef struct _dragon_node -{ - GArchInstruction *first; /* Arrivée d'un lien (début) */ - GArchInstruction *last; /* Départ d'un lien (fin) */ - - bitfield_t *bits; /* Représentation par masque */ - -} dragon_node; +#include "dragon.h" -/* Définition des blocs d'allocation */ -#define NODE_ALLOC_SIZE 100 -/* Dénombre le nombre de noeuds présents dans une routine. */ -static dragon_node *create_dragon_nodes(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, size_t *); -/* Termine l'initialisation de noeuds trouvés dans une routine. */ -static void define_mask_for_nodes(dragon_node *, size_t); -/* Supprime de la mémoire tous les noeuds détectés. */ -static void delete_dragon_nodes(dragon_node *, size_t); -/* Recherche un noeud selon son intruction de départ. */ -static dragon_node *find_node_for_instruction(dragon_node *, size_t, bool, const GArchInstruction *); - -/* Détermine toute la chaîne hiérarchique de domination. */ -static void compute_all_dominators(dragon_node *, size_t); /* Matérialise les liens de retour arrière en tant que boucles. */ static void detect_back_edges(dragon_node *, size_t); @@ -70,294 +45,6 @@ static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, -/****************************************************************************** -* * -* Paramètres : proc = ensemble d'instructions à parcourir. * -* coverage = zone de couverture où rechercher des instructions.* -* range = zone de couverture de la routine analysée. * -* start = adresse du début de l'analyse. * -* count = taille de la liste de noeuds retournés. [OUT] * -* * -* Description : Dénombre le nombre de noeuds présents dans une routine. * -* * -* Retour : Liste de noeuds initialisés de façon incomplète. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static dragon_node *create_dragon_nodes(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, size_t *count) -{ - dragon_node *result; /* Liste à créer et renvoyer */ - size_t allocated; /* Dimensionnement en mémoire */ - GArchInstruction *last; /* Mémorisation du passé */ - GArchInstruction *iter; /* Boucle de parcours */ - const mrange_t *irange; /* Emplacement d'instruction */ - InstructionLinkType *types; /* Type de lien entre instr. */ - size_t scount; /* Nombre de liens de dest. */ - size_t i; /* Boucle de parcours */ - dragon_node *new; /* Nouvel élément à créer */ - - result = NULL; - *count = 0; - - allocated = 0; - - for (last = NULL, iter = g_arch_processor_find_covered_instr_by_address(proc, coverage, start); - iter != NULL; - last = iter, iter = g_arch_instruction_get_next_iter(iter /* FIXME : list*/, iter, ~0)) - { - /* L'instruction sort-elle des clous ? */ - - irange = g_arch_instruction_get_range(iter); - - if (!mrange_contains_mrange(range, irange)) - break; - - /* Analyse des sources */ - - if (result == NULL) - { - (*count)++; - - if (*count >= allocated) - { - allocated += NODE_ALLOC_SIZE; - result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); - } - - new = &result[*count - 1]; - - new->first = iter; - - } - else - { - scount = g_arch_instruction_get_sources(iter, NULL, &types); - if (scount == 0) continue; - - for (i = 0; i < scount; i++) - switch (types[i]) - { - case ILT_EXEC_FLOW: - case ILT_JUMP: - case ILT_CASE_JUMP: - case ILT_JUMP_IF_TRUE: - case ILT_JUMP_IF_FALSE: - - if (*count > 0) - result[*count - 1].last = last; - - (*count)++; - i = scount; - - if (*count >= allocated) - { - allocated += NODE_ALLOC_SIZE; - result = (dragon_node *)realloc(result, allocated * sizeof(dragon_node)); - } - - new = &result[*count - 1]; - - new->first = iter; - - break; - - default: - break; - - } - - } - - } - - if (*count > 0) - result[*count - 1].last = last; - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Termine l'initialisation de noeuds trouvés dans une routine. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void define_mask_for_nodes(dragon_node *nodes, size_t count) -{ - size_t i; /* Boucle de parcours */ - - for (i = 0; i < count; i++) - nodes[i].bits = create_bit_field(count, i > 0); - - set_in_bit_field(nodes[0].bits, 0, 1); - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Supprime de la mémoire tous les noeuds détectés. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void delete_dragon_nodes(dragon_node *nodes, size_t count) -{ - size_t i; /* Boucle de parcours */ - - for (i = 0; i < count; i++) - delete_bit_field(nodes[i].bits); - - free(nodes); - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à parcourir. * -* final = précise si l'instruction visée est la première. * -* instr = instruction à retrouver en tant que début de noeud. * -* * -* Description : Recherche un noeud selon son intruction de départ. * -* * -* Retour : Noeud trouvé ou NULL si aucune trouvaille. * -* * -* Remarques : - * -* * -******************************************************************************/ - -static dragon_node *find_node_for_instruction(dragon_node *nodes, size_t count, bool final, const GArchInstruction *instr) -{ - dragon_node *result; /* Résultat des recherches */ - const mrange_t *irange; /* Emplacement d'instruction */ - - int find_node_from_range(const mrange_t *range, const dragon_node *node) - { - int status; /* Bilan à retourner */ - const mrange_t *nrange; /* Emplacement de noeud */ - - nrange = g_arch_instruction_get_range(final ? node->last : node->first); - - status = cmp_mrange(range, nrange); - - return status; - - } - - irange = g_arch_instruction_get_range(instr); - - result = bsearch(irange, nodes, count, sizeof(dragon_node), (__compar_fn_t)find_node_from_range); - - return result; - -} - - -/****************************************************************************** -* * -* Paramètres : nodes = liste de noeuds détectés dans une routine. * -* count = taille de cette liste de noeuds à traiter. * -* * -* Description : Détermine toute la chaîne hiérarchique de domination. * -* * -* Retour : - * -* * -* Remarques : - * -* * -******************************************************************************/ - -static void compute_all_dominators(dragon_node *nodes, size_t count) -{ - bitfield_t *inter; /* Intersection de dominations */ - bool changed; /* Note un changement qq part */ - size_t k; /* Boucle de parcours #1 */ - dragon_node *node; /* Noeud à traiter */ - dragon_node *predecessor; /* Noeud prédécesseur direct */ - GArchInstruction **srcs; /* Instructions d'origine */ - InstructionLinkType *types; /* Type de lien entre instr. */ - size_t scount; /* Nombre de liens de source */ - size_t i; /* Boucle de parcours #2 */ - - inter = create_bit_field(count, false); - - do - { - changed = false; - - for (k = 1; k < count; k++) - { - node = &nodes[k]; - - set_all_in_bit_field(inter); - - scount = g_arch_instruction_get_sources(node->first, &srcs, &types); - assert(scount > 0); - - for (i = 0; i < scount; i++) - switch (types[i]) - { - case ILT_EXEC_FLOW: - case ILT_JUMP: - case ILT_CASE_JUMP: - case ILT_JUMP_IF_TRUE: - case ILT_JUMP_IF_FALSE: - - predecessor = find_node_for_instruction(nodes, count, true, srcs[i]); - - - printf(" -- finding pred @ 0x%08x -> 0x%08x :: %p\n", - (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, - (unsigned int)g_arch_instruction_get_range(srcs[i])->addr.virtual, - predecessor); - - - - if (predecessor == NULL) break; - - and_bit_field(inter, predecessor->bits); - break; - - default: - break; - - } - - set_in_bit_field(inter, k, 1); - - if (!is_bit_field_equal_to(node->bits, inter)) - { - copy_bit_field(node->bits, inter); - changed = true; - } - - } - - } - while (changed); - - delete_bit_field(inter); - -} - /****************************************************************************** @@ -377,6 +64,8 @@ static void detect_back_edges(dragon_node *nodes, size_t count) { size_t k; /* Boucle de parcours #1 */ dragon_node *node; /* Noeud à traiter */ + const bitfield_t *dominators; /* Liste de dominateurs */ + GArchInstruction *last; /* Instruction finale de noeud */ GArchInstruction **dests; /* Instr. visée par une autre */ InstructionLinkType *types; /* Type de lien entre lignes */ size_t dcount; /* Nombre de liens de dest. */ @@ -390,24 +79,33 @@ static void detect_back_edges(dragon_node *nodes, size_t count) for (k = 0; k < count; k++) { - node = &nodes[k]; + GArchInstruction *first; + + node = get_dragon_node(nodes, k); + + dominators = get_domination_bits(node); + + get_dragon_node_bounding_instructions(node, &first, &last); + printf("#[ node %zu ]# @ 0x%08x / 0x%08x - mask = 0x%08lx\n", k, - (unsigned int)g_arch_instruction_get_range(node->first)->addr.virtual, - (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, - gfw(node->bits)); + (unsigned int)g_arch_instruction_get_range(first)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(last)->addr.virtual, + gfw(dominators)); } printf("\n"); - - for (k = 1; k < count; k++) { - node = &nodes[k]; + node = get_dragon_node(nodes, k); + + dominators = get_domination_bits(node); - dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL); + get_dragon_node_bounding_instructions(node, NULL, &last); + + dcount = g_arch_instruction_get_destinations(last, &dests, &types, NULL); if (dcount == 0) continue; for (i = 0; i < dcount; i++) @@ -422,17 +120,17 @@ static void detect_back_edges(dragon_node *nodes, size_t count) target = find_node_for_instruction(nodes, count, false, dests[i]); if (target == NULL) break; - id = (target - nodes); + id = get_dragon_node_index(nodes, target); - if (test_in_bit_field(node->bits, id, 1)) + if (test_in_bit_field(dominators, id, 1)) { printf("BACKEDGE :: 0x%08lx -> 0x%08lx\n", - (unsigned int)g_arch_instruction_get_range(node->last)->addr.virtual, + (unsigned int)g_arch_instruction_get_range(last)->addr.virtual, (unsigned int)g_arch_instruction_get_range(dests[i])->addr.virtual); - /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP); + /* status = */g_arch_instruction_change_link(last, dests[i], types[i], ILT_LOOP); } @@ -468,25 +166,29 @@ static void detect_back_edges(dragon_node *nodes, size_t count) static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow) { + dragon_knight *knight; /* Complexité de code posée */ dragon_node *nodes; /* Liste des noeuds détectés */ size_t count; /* Taille de cette liste */ - nodes = create_dragon_nodes(proc, coverage, range, start, &count); + knight = begin_dragon_knight(proc, coverage, range, start); + if (knight == NULL) return; - if (nodes == NULL) return; + assert(knight != NULL); - assert(nodes != NULL); - printf("nodes count :: %d\n", (int)count); - define_mask_for_nodes(nodes, count); + get_dragon_knight_content(knight, &nodes, &count); + + + printf("nodes count :: %d\n", (int)count); compute_all_dominators(nodes, count); detect_back_edges(nodes, count); - delete_dragon_nodes(nodes, count); + + end_dragon_knight(knight); } diff --git a/src/common/bits.c b/src/common/bits.c index b08dcb4..90cb098 100644 --- a/src/common/bits.c +++ b/src/common/bits.c @@ -460,7 +460,7 @@ void or_bit_field(bitfield_t *dest, const bitfield_t *src) * * ******************************************************************************/ -bool test_in_bit_field(bitfield_t *field, size_t first, size_t count) +bool test_in_bit_field(const bitfield_t *field, size_t first, size_t count) { bool result; /* Valeur retrouvée à renvoyer */ size_t last; /* Point d'arrêt de la boucle */ diff --git a/src/common/bits.h b/src/common/bits.h index 074aac4..6d8ea5b 100644 --- a/src/common/bits.h +++ b/src/common/bits.h @@ -70,7 +70,7 @@ void and_bit_field(bitfield_t *, const bitfield_t *); void or_bit_field(bitfield_t *, const bitfield_t *); /* Détermine si un bit est à 1 dans un champ de bits. */ -bool test_in_bit_field(bitfield_t *, size_t, size_t); +bool test_in_bit_field(const bitfield_t *, size_t, size_t); /* Indique si deux champs de bits sont identiques ou non. */ bool is_bit_field_equal_to(const bitfield_t *, const bitfield_t *); -- cgit v0.11.2-87-g4458