summaryrefslogtreecommitdiff
path: root/src/analysis/disass/loop.c
diff options
context:
space:
mode:
Diffstat (limited to 'src/analysis/disass/loop.c')
-rw-r--r--src/analysis/disass/loop.c595
1 files changed, 595 insertions, 0 deletions
diff --git a/src/analysis/disass/loop.c b/src/analysis/disass/loop.c
index 5f97981..d9a3f2d 100644
--- a/src/analysis/disass/loop.c
+++ b/src/analysis/disass/loop.c
@@ -24,6 +24,592 @@
#include "loop.h"
+#include <assert.h>
+#include <malloc.h>
+
+
+#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;
+
+
+/* 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);
+
+/* Suit un flot d'exécution à la recherche de boucles. */
+static void track_loops_in_code(const GArchProcessor *, const instr_coverage *, const mrange_t *, const vmpa2t *, memfield_t *);
+
+
+
+/******************************************************************************
+* *
+* 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);
+
+}
+
+
+
+/******************************************************************************
+* *
+* Paramètres : nodes = liste de noeuds détectés dans une routine. *
+* count = taille de cette liste de noeuds à traiter. *
+* *
+* Description : Matérialise les liens de retour arrière en tant que boucles. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void detect_back_edges(dragon_node *nodes, size_t count)
+{
+ size_t k; /* Boucle de parcours #1 */
+ dragon_node *node; /* Noeud à traiter */
+ GArchInstruction **dests; /* Instr. visée par une autre */
+ InstructionLinkType *types; /* Type de lien entre lignes */
+ size_t dcount; /* Nombre de liens de dest. */
+ size_t i; /* Boucle de parcours #2 */
+ dragon_node *target; /* Noeud référencé à tester */
+ size_t id; /* Indice du bit associé */
+
+
+
+ printf("-----------------------------------------------------------------\n");
+
+ for (k = 0; k < count; k++)
+ {
+ node = &nodes[k];
+
+ 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));
+
+ }
+
+ printf("\n");
+
+
+
+ for (k = 1; k < count; k++)
+ {
+ node = &nodes[k];
+
+ dcount = g_arch_instruction_get_destinations(node->last, &dests, &types, NULL);
+ if (dcount == 0) continue;
+
+ for (i = 0; i < dcount; 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:
+
+ target = find_node_for_instruction(nodes, count, false, dests[i]);
+ if (target == NULL) break;
+
+ id = (target - nodes);
+
+ if (test_in_bit_field(node->bits, 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(dests[i])->addr.virtual);
+
+
+ /* status = */g_arch_instruction_change_link(node->last, dests[i], types[i], ILT_LOOP);
+
+
+ }
+
+ break;
+
+ default:
+ break;
+
+ }
+
+ }
+
+}
+
+
+
+/******************************************************************************
+* *
+* 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. *
+* flow = ensemble des jalons de l'exécution du code. *
+* *
+* Description : Suit un flot d'exécution à la recherche de boucles. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+static void track_loops_in_code(const GArchProcessor *proc, const instr_coverage *coverage, const mrange_t *range, const vmpa2t *start, memfield_t *flow)
+{
+ 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);
+ assert(nodes != NULL);
+
+ printf("nodes count :: %d\n", (int)count);
+
+ define_mask_for_nodes(nodes, count);
+
+ compute_all_dominators(nodes, count);
+
+ detect_back_edges(nodes, count);
+
+ delete_dragon_nodes(nodes, count);
+
+}
+
+
+/******************************************************************************
+* *
+* Paramètres : proc = ensemble d'instructions à relier. *
+* routines = prototypes existants à insérer. *
+* count = quantité de ces prototypes. *
+* statusbar = barre de statut avec progression à mettre à jour.*
+* id = identifiant du message affiché à l'utilisateur. *
+* *
+* Description : Détecte les boucles dans du code machine. *
+* *
+* Retour : - *
+* *
+* Remarques : - *
+* *
+******************************************************************************/
+
+void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id)
+{
+ size_t i; /* Boucle de parcours */
+ const mrange_t *range; /* Couverture d'une routine */
+ const vmpa2t *start; /* Adresse de départ */
+ const instr_coverage *coverage; /* Instructions couvertes */
+ memfield_t *flow; /* Flot d'exécution à suivre */
+
+ //for (i = 286; i == 286; i++)
+ for (i = 0; i < count; i++)
+ {
+
+
+ range = g_binary_routine_get_range(routines[i]);
+ start = get_mrange_addr(range);
+
+
+ printf("====== '%s' @ 0x%08x\n",
+ g_binary_routine_get_name(routines[i]),
+ start->virtual);
+
+
+ coverage = g_arch_processor_find_coverage_by_address(proc, start);
+
+ flow = NULL;//create_mem_field(range);
+ track_loops_in_code(proc, coverage, range, start, flow);
+ //delete_mem_field(flow);
+
+ gtk_extended_status_bar_update_activity(statusbar, id, (i + 1) * 1.0 / count);
+
+ }
+
+
+ printf("done\n\n");
+ //exit(0);
+
+
+}
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+////////////////////////////////////////////////////////////////////////////////////////////////////////////
+
+
+
+#if 0
+
+
#include <malloc.h>
#include <stdlib.h>
#include <string.h>
@@ -193,6 +779,8 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si
for (i = 0; i < count; i++)
{
+
+
range = g_binary_routine_get_range(routines[i]);
start = get_mrange_addr(range);
@@ -207,3 +795,10 @@ void detect_loops_in_code(const GArchProcessor *proc, GBinRoutine **routines, si
}
}
+
+
+
+
+
+
+#endif
generated by cgit v0.11.2-87-g4458 at 2024-04-27 17:20:50 (GMT)