diff options
-rw-r--r-- | ChangeLog | 6 | ||||
-rw-r--r-- | src/analysis/disass/macro.c | 973 | ||||
-rw-r--r-- | src/analysis/disass/macro.h | 1 |
3 files changed, 684 insertions, 296 deletions
@@ -1,5 +1,11 @@ 15-03-11 Cyrille Bagard <nocbos@gmail.com> + * src/analysis/disass/macro.c: + * src/analysis/disass/macro.h: + Update and improve without testing the old cutting of routines into blocks. + +15-03-11 Cyrille Bagard <nocbos@gmail.com> + * src/analysis/disass/output.c: Avoid to get stuck because a symbol can not be found and inserted. diff --git a/src/analysis/disass/macro.c b/src/analysis/disass/macro.c index 3745f25..1045eb2 100644 --- a/src/analysis/disass/macro.c +++ b/src/analysis/disass/macro.c @@ -24,9 +24,9 @@ #include "macro.h" +#include <assert.h> #include <malloc.h> #include <stdlib.h> -#include <string.h> #include "../blocks/flow.h" @@ -40,28 +40,37 @@ /* Bornes d'une zone à couvrir */ typedef struct _code_coverage { - vmpa_t start; /* Adresse de départ */ + vmpa2t start; /* Position de départ */ - vmpa_t *ends; /* Adresses butoir de fin */ + vmpa2t *ends; /* Positions butoir de fin */ size_t ends_count; /* Quantité de fins possibles */ + unsigned long *processed; /* Octets traités dans la zone */ + size_t length; /* Taille de la cartographie */ + } code_coverage; /* Met en place les délimitations d'une zone de code. */ -static code_coverage *create_code_coverage(vmpa_t, vmpa_t); +static code_coverage *create_code_coverage(const mrange_t *); /* Crée une copie d'une couverture de zone de code. */ -static code_coverage *dup_code_coverage(vmpa_t, const code_coverage *); +static code_coverage *dup_code_coverage(const code_coverage *, const vmpa2t *); /* Détruit des délimitations d'une zone de code. */ static void delete_code_coverage(code_coverage *); /* Indique si une adresse est hors zone ou non. */ -static bool code_coverage_stop_here(const code_coverage *, const vmpa_t *); +static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *); /* Ajoute une adresse butoir pour la zone à couvrir. */ -static void add_ending_address_code_coverage(code_coverage *, const vmpa_t *); +static bool add_ending_address_code_coverage(code_coverage *, const vmpa2t *); + +/* Indique si une zone donnée n'a jamais été traitée ou non. */ +static bool is_range_processed_in_coverage(const code_coverage *, const mrange_t *); + +/* Marque une série d'octets comme ayant été traités. */ +static void mark_range_as_processed_in_coverage(code_coverage *, const GArchInstruction *); @@ -71,23 +80,51 @@ static void add_ending_address_code_coverage(code_coverage *, const vmpa_t *); /* Indications sur une branche */ typedef struct _branch_info { - vmpa_t *jumps; /* Jalons de la branche */ + vmpa2t *hops; /* Jalons de la branche */ size_t count; /* Quantité de ces jalons */ } branch_info; +/* Initialise le suivi d'une branche de flot d'exécution. */ +static void init_branch_info(branch_info *); + +/* Acte la fin d'un suivi d'une branche de flot d'exécution. */ +static void clean_branch_info(branch_info *); + /* Indique si une adresse est retenue comme point de passage. */ -static bool is_addr_in_branch(const branch_info *, const vmpa_t *); +static bool is_addr_in_branch(const branch_info *, const vmpa2t *); + +/* Ajoute un nouveau jalon dans l'exécution d'une branche. */ +static bool add_hop_into_branch(branch_info *, const vmpa2t *); /* Identifie les différents points de passage d'une branche. */ -static void find_next_jumps(GArchInstruction *, vmpa_t, const code_coverage *, branch_info *); +static void find_next_hops(GArchInstruction *, const vmpa2t *, const code_coverage *, branch_info *); /* Retrouve le point de ralliement entre deux branches. */ -static vmpa_t compute_first_common_addr(branch_info *, branch_info *); +static bool compute_first_common_addr(const branch_info *, const branch_info *, vmpa2t *); + + +/* Groupement de branches et d'indications */ +typedef struct _branch_group +{ + branch_info *branches; /* Liste des branches */ + size_t count; /* Taille de cette liste */ + +} branch_group; + + +/* Initialise le suivi d'un ensemble de branches. */ +static void init_branch_group(branch_group *); + +/* Acte la fin d'un suivi d'un ensemble de branches. */ +static void clean_branch_group(branch_group *); + +/* Ajoute une branche à un ensemble de branches en place. */ +static branch_info *extend_branch_group(branch_group *); /* Retrouve le point de ralliement entre un groupe de branches. */ -static vmpa_t compute_first_common_addr_in_group(const branch_info *, size_t); +static bool compute_first_common_addr_in_group(const branch_group *, vmpa2t *); @@ -95,17 +132,45 @@ static vmpa_t compute_first_common_addr_in_group(const branch_info *, size_t); /** - * Macros pour le marquage des instructions traitées. - * Dans un soucis d'optimisation, on ne traite que les instructions - * démarrant un bloc. + * Procédure d'ajout de blocs : pour le premier, on conserve le bloc en mémoire + * et on attend. Si rien ne suit, il constitura l'unique retour. Sinon, on + * l'ajoute à partir de la sauvegarde, et le reste suit. */ -#define MACRO_MARK_AS_PROCESSED(_instr) g_object_set_data(G_OBJECT(_instr), "macro_done", _instr) -#define MACRO_IS_PROCESSED(_instr) (g_object_get_data(G_OBJECT(_instr), "macro_done") != NULL) -#define MACRO_CLEAR_PROCESSED(_instr) g_object_set_data(G_OBJECT(_instr), "macro_done", NULL) +#define DELAYED_BLOCK_ADDING(res, cache, blk) \ + do \ + { \ + if (res == NULL) \ + { \ + if (cache == NULL) \ + cache = blk; \ + else \ + { \ + res = g_virtual_block_new(); \ + g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), cache); \ + } \ + } \ + \ + if (res != NULL) \ + g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), blk); \ + \ + } \ + while (0) + + +/* Procède à la création d'un bloc d'instructions simple. */ +static GInstrBlock *build_instruction_block_simple(GArchInstruction *, code_coverage *, GArchInstruction **, GArchInstruction *); +/* Procède à la définition d'un bloc d'instructions selectif. */ +static GInstrBlock *build_instruction_blocks_case(GArchInstruction *, code_coverage *, const branch_group *, vmpa2t *); + +/* Procède à la définition d'un bloc d'instruction if/then/else. */ +static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *, code_coverage *, const branch_info *, const branch_info *, vmpa2t *); + +/* Procède à la définition d'un bloc d'instructions d'exception. */ +static void add_instruction_blocks_except(GInstrBlock **, GInstrBlock **, GArchInstruction *, code_coverage *, const branch_group *, const branch_info *); /* Procède à la définition de bloc regroupant des instructions. */ -static GInstrBlock *build_instruction_block(GArchInstruction *, const code_coverage *); +static GInstrBlock *build_instruction_blocks(GArchInstruction *, code_coverage *); @@ -116,8 +181,7 @@ static GInstrBlock *build_instruction_block(GArchInstruction *, const code_cover /****************************************************************************** * * -* Paramètres : start = adresse du début de la zone à couvrir. * -* end = adresse de fin de la zone à couvrir (exclusive). * +* Paramètres : range = définition de la zone à couvrir. * * * * Description : Met en place les délimitations d'une zone de code. * * * @@ -127,18 +191,28 @@ static GInstrBlock *build_instruction_block(GArchInstruction *, const code_cover * * ******************************************************************************/ -static code_coverage *create_code_coverage(vmpa_t start, vmpa_t end) +static code_coverage *create_code_coverage(const mrange_t *range) { code_coverage *result; /* Couverture à retourner */ + phys_t length; /* Taille de la zone couverte */ + size_t requested; /* Nombre de mots à allouer */ result = (code_coverage *)calloc(1, sizeof(code_coverage)); - result->start = start; + copy_vmpa(&result->start, get_mrange_addr(range)); - result->ends = (vmpa_t *)calloc(1, sizeof(vmpa_t)); + result->ends = (vmpa2t *)calloc(1, sizeof(vmpa2t)); result->ends_count = 1; - result->ends[0] = end; + compute_mrange_end_addr(range, &result->ends[0]); + + length = get_mrange_length(range); + + requested = length / sizeof(unsigned long); + if (length % sizeof(unsigned long) != 0) requested++; + + result->processed = (unsigned long *)calloc(requested, sizeof(unsigned long)); + result->length = requested; return result; @@ -147,8 +221,8 @@ static code_coverage *create_code_coverage(vmpa_t start, vmpa_t end) /****************************************************************************** * * -* Paramètres : start = nouvelle adresse de début, plus profonde. * -* src = informations de couverture à consulter. * +* Paramètres : src = informations de couverture à consulter. * +* new = nouvelle position de début, plus profonde. * * * * Description : Crée une copie d'une couverture de zone de code. * * * @@ -158,20 +232,25 @@ static code_coverage *create_code_coverage(vmpa_t start, vmpa_t end) * * ******************************************************************************/ -static code_coverage *dup_code_coverage(vmpa_t start, const code_coverage *src) +static code_coverage *dup_code_coverage(const code_coverage *src, const vmpa2t *new) { code_coverage *result; /* Couverture à retourner */ size_t i; /* Boucle de parcours */ result = (code_coverage *)calloc(1, sizeof(code_coverage)); - result->start = start; + copy_vmpa(&result->start, &src->start); - result->ends = (vmpa_t *)calloc(src->ends_count, sizeof(vmpa_t)); + result->ends = (vmpa2t *)calloc(src->ends_count, sizeof(vmpa2t)); result->ends_count = src->ends_count; for (i = 0; i < result->ends_count; i++) - result->ends[i] = src->ends[i]; + copy_vmpa(&result->ends[i], &src->ends[i]); + + result->processed = (unsigned long *)calloc(src->length, sizeof(unsigned long)); + result->length = src->length; + + memcpy(result->processed, src->processed, src->length * sizeof(unsigned long)); return result; @@ -194,6 +273,8 @@ static void delete_code_coverage(code_coverage *coverage) { free(coverage->ends); + free(coverage->processed); + free(coverage); } @@ -202,7 +283,7 @@ static void delete_code_coverage(code_coverage *coverage) /****************************************************************************** * * * Paramètres : coverage = informations de couverture à consulter. * -* addr = adresse à tester. * +* addr = localisation à tester. * * * * Description : Indique si une adresse est hors zone ou non. * * * @@ -212,12 +293,12 @@ static void delete_code_coverage(code_coverage *coverage) * * ******************************************************************************/ -static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa_t *addr) +static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa2t *addr) { void *ptr; /* Résultat des recherches */ ptr = bsearch(addr, coverage->ends, coverage->ends_count, - sizeof(vmpa_t), (__compar_fn_t)compare_vmpa); + sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); return (ptr != NULL); @@ -227,22 +308,99 @@ static bool code_coverage_stop_here(const code_coverage *coverage, const vmpa_t /****************************************************************************** * * * Paramètres : coverage = informations de couverture à compléter. * -* addr = adresse à ajouter. * +* addr = localisation à ajouter. * * * * Description : Ajoute une adresse butoir pour la zone à couvrir. * * * +* Retour : true si une insertion a été effectuée, false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool add_ending_address_code_coverage(code_coverage *coverage, const vmpa2t *addr) +{ + bool result; /* Bilan à retourner */ + + result = !code_coverage_stop_here(coverage, addr); + + if (result) + { + coverage->ends = (vmpa2t *)realloc(coverage->ends, ++coverage->ends_count * sizeof(vmpa2t)); + + copy_vmpa(&coverage->ends[coverage->ends_count - 1], addr); + + qsort(coverage->ends, coverage->ends_count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); + + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : coverage = informations de couverture à consulter. * +* range = zone à interroger. * +* * +* Description : Indique si une zone donnée n'a jamais été traitée ou non. * +* * +* Retour : true si l'aire visée est vierge, false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool is_range_processed_in_coverage(const code_coverage *coverage, const mrange_t *range) +{ + bool result; /* Bilan à renvoyer */ + phys_t diff; /* Décalage à appliquer */ + size_t index; /* Cellule de tableau visée */ + unsigned int remaining; /* Nombre de bits restants */ + + diff = compute_vmpa_diff(&coverage->start, get_mrange_addr(range)); + assert(diff < coverage->length); + + index = diff / (sizeof(unsigned long) * 8); + remaining = diff % (sizeof(unsigned long) * 8); + + result = ((coverage->processed[index] & (1ul << remaining)) != 0); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : coverage = informations de couverture à consulter. * +* instr = instruction couvrant la zone à interroger. * +* * +* Description : Marque une série d'octets comme ayant été traités. * +* * * Retour : - * * * * Remarques : - * * * ******************************************************************************/ -static void add_ending_address_code_coverage(code_coverage *coverage, const vmpa_t *addr) +static void mark_range_as_processed_in_coverage(code_coverage *coverage, const GArchInstruction *instr) { - coverage->ends = (vmpa_t *)realloc(coverage->ends, ++coverage->ends_count * sizeof(vmpa_t)); - coverage->ends[coverage->ends_count - 1] = *addr; + const mrange_t *range; /* Emplacement d'instruction */ + phys_t diff; /* Décalage à appliquer */ + size_t index; /* Cellule de tableau visée */ + unsigned int remaining; /* Nombre de bits restants */ + + range = g_arch_instruction_get_range(instr); - qsort(coverage->ends, coverage->ends_count, sizeof(vmpa_t), (__compar_fn_t)compare_vmpa); + diff = compute_vmpa_diff(&coverage->start, get_mrange_addr(range)); + assert(diff < coverage->length); + + index = diff / (sizeof(unsigned long) * 8); + remaining = diff % (sizeof(unsigned long) * 8); + + coverage->processed[index] |= (1ul << remaining); } @@ -255,8 +413,47 @@ static void add_ending_address_code_coverage(code_coverage *coverage, const vmpa /****************************************************************************** * * +* Paramètres : info = informations à initialiser. * +* * +* Description : Initialise le suivi d'une branche de flot d'exécution. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_branch_info(branch_info *info) +{ + memset(info, 0, sizeof(branch_info)); + +} + + +/****************************************************************************** +* * +* Paramètres : info = informations à nettoyer. * +* * +* Description : Acte la fin d'un suivi d'une branche de flot d'exécution. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void clean_branch_info(branch_info *info) +{ + if (info->hops != NULL) + free(info->hops); + +} + + +/****************************************************************************** +* * * Paramètres : info = informations à consulter. * -* addr = adresse à rechercher. * +* addr = position à rechercher. * * * * Description : Indique si une adresse est retenue comme point de passage. * * * @@ -266,15 +463,46 @@ static void add_ending_address_code_coverage(code_coverage *coverage, const vmpa * * ******************************************************************************/ -static bool is_addr_in_branch(const branch_info *info, const vmpa_t *addr) +static bool is_addr_in_branch(const branch_info *info, const vmpa2t *addr) +{ + void *ptr; /* Résultat des recherches */ + + ptr = bsearch(addr, info->hops, info->count, + sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); + + return (ptr != NULL); + +} + + +/****************************************************************************** +* * +* Paramètres : info = informations de flot à compléter. * +* addr = localisation à ajouter. * +* * +* Description : Ajoute un nouveau jalon dans l'exécution d'une branche. * +* * +* Retour : true si une insertion a été effectuée, false sinon. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool add_hop_into_branch(branch_info *info, const vmpa2t *addr) { bool result; /* Bilan à retourner */ - size_t i; /* Boucle de parcours */ - result = false; + result = !is_addr_in_branch(info, addr); + + if (result) + { + info->hops = (vmpa2t *)realloc(info->hops, ++info->count * sizeof(vmpa2t)); + + copy_vmpa(&info->hops[info->count - 1], addr); - for (i = 0; i < info->count && !result; i++) - result = (info->jumps[i] == *addr); + qsort(info->hops, info->count, sizeof(vmpa2t), (__compar_fn_t)cmp_vmpa); + + } return result; @@ -284,7 +512,7 @@ static bool is_addr_in_branch(const branch_info *info, const vmpa_t *addr) /****************************************************************************** * * * Paramètres : instrs = ensemble des instructions d'assemblage. * -* start = adresse de début du bloc. * +* start = position du début de bloc. * * coverage = liste des adresses de fin butoir. * * count = nombre de sauts détectés. [OUT] * * * @@ -296,31 +524,27 @@ static bool is_addr_in_branch(const branch_info *info, const vmpa_t *addr) * * ******************************************************************************/ -static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_coverage *coverage, branch_info *info) +static void find_next_hops(GArchInstruction *instrs, const vmpa2t *start, const code_coverage *coverage, branch_info *info) { GArchInstruction *iter; /* Boucle de parcours #1 */ - vmpa_t addr; /* Adresse d'une instruction */ + const mrange_t *range; /* Emplacement d'instruction */ 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 */ - vmpa_t daddr; /* Adresse de destination */ - /* On évite de boucler... */ - if (is_addr_in_branch(info, &start)) + /* Si la position est déjà présente, on évite de boucler... */ + if (!add_hop_into_branch(info, start)) return; - info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t)); - info->jumps[info->count - 1] = start; - /* On suit le flot jusqu'à la prochaine bifurcation */ for (iter = g_arch_instruction_find_by_address(instrs, start, true); iter != NULL; iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX)) { - g_arch_instruction_get_location(iter, NULL, NULL, &addr); + range = g_arch_instruction_get_range(iter); - if (code_coverage_stop_here(coverage, &addr)) + if (code_coverage_stop_here(coverage, get_mrange_addr(range))) break; if (g_arch_instruction_is_return(iter)) @@ -335,6 +559,9 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL); for (i = 0; i < dcount; i++) + { + range = g_arch_instruction_get_range(dests[i]); + switch (types[i]) { case ILT_EXEC_FLOW: @@ -342,14 +569,11 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c case ILT_CASE_JUMP: case ILT_JUMP_IF_TRUE: case ILT_JUMP_IF_FALSE: - g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr); - find_next_jumps(instrs, daddr, coverage, info); + find_next_hops(instrs, get_mrange_addr(range), coverage, info); break; case ILT_LOOP: - g_arch_instruction_get_location(dests[i], NULL, NULL, &daddr); - info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t)); - info->jumps[info->count - 1] = daddr; + add_hop_into_branch(info, get_mrange_addr(range)); break; default: @@ -357,16 +581,14 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c } + } + break; } /* Si on termine... */ - if (iter != NULL && !is_addr_in_branch(info, &addr)) - { - info->jumps = (vmpa_t *)realloc(info->jumps, ++(info->count) * sizeof(vmpa_t)); - info->jumps[info->count - 1] = addr; - } + if (iter != NULL) add_hop_into_branch(info, get_mrange_addr(range)); } @@ -375,26 +597,29 @@ static void find_next_jumps(GArchInstruction *instrs, vmpa_t start, const code_c * * * Paramètres : a = premier ensemble de jalons à parcourir. * * b = second ensemble de jalons à parcourir. * +* c = éventuelle adresse commune à deux branches. * * * * Description : Retrouve le point de ralliement entre deux branches. * * * -* Retour : Adresse commune à deux branches. * +* Retour : true si une position commune a pu être trouvée, false sinon. * * * * Remarques : - * * * ******************************************************************************/ -static vmpa_t compute_first_common_addr(branch_info *a, branch_info *b) +static bool compute_first_common_addr(const branch_info *a, const branch_info *b, vmpa2t *c) { - vmpa_t result; /* Adresse trouvée à retourner */ + bool result; /* Bilan à retourner */ size_t i; /* Boucle de parcours */ - /* Valeur conceptuellement impossible à renvoyer */ - result = VMPA_MAX; + result = false; - for (i = 0; i < a->count && result == VMPA_MAX; i++) - if (is_addr_in_branch(b, &a->jumps[i])) - result = a->jumps[i]; + for (i = 0; i < a->count && !result; i++) + if (is_addr_in_branch(b, &a->hops[i])) + { + result = true; + copy_vmpa(c, &a->hops[i]); + } return result; @@ -403,36 +628,110 @@ static vmpa_t compute_first_common_addr(branch_info *a, branch_info *b) /****************************************************************************** * * -* Paramètres : list = liste d'ensembles de jalons à parcourir. * -* count = taille de cette liste. * +* Paramètres : group = informations à initialiser. * +* * +* Description : Initialise le suivi d'un ensemble de branches. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void init_branch_group(branch_group *group) +{ + memset(group, 0, sizeof(branch_group)); + +} + + +/****************************************************************************** +* * +* Paramètres : group = informations à nettoyer. * +* * +* Description : Acte la fin d'un suivi d'un ensemble de branches. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void clean_branch_group(branch_group *group) +{ + size_t i; /* Boucle de parcours */ + + for (i = 0; i < group->count; i++) + clean_branch_info(&group->branches[i]); + + if (group->branches != NULL) + free(group->branches); + +} + + +/****************************************************************************** +* * +* Paramètres : group = liste d'ensembles de jalons à agrandir. * +* * +* Description : Ajoute une branche à un ensemble de branches en place. * +* * +* Retour : Nouvel élément rajouté et initialisé. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static branch_info *extend_branch_group(branch_group *group) +{ + branch_info *result; /* Nouveauté à retourner */ + + group->branches = (branch_info *)realloc(group->branches, + ++group->count * sizeof(branch_info)); + + result = &group->branches[group->count]; + + init_branch_info(result); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : group = liste d'ensembles de jalons à parcourir. * +* common = éventuelle adresse commune à branches. * * * * Description : Retrouve le point de ralliement entre un groupe de branches. * * * -* Retour : Adresse commune aux branches. * +* Retour : true si une position commune a pu être trouvée, false sinon. * * * * Remarques : - * * * ******************************************************************************/ -static vmpa_t compute_first_common_addr_in_group(const branch_info *list, size_t count) +static bool compute_first_common_addr_in_group(const branch_group *group, vmpa2t *common) { vmpa_t result; /* Adresse trouvée à retourner */ + branch_info *list; /* Raccourci de confort */ size_t i; /* Boucle de parcours #1 */ bool keep; /* Candidate à garder ? */ size_t j; /* Boucle de parcours #2 */ - /* Valeur conceptuellement impossible à renvoyer */ - result = VMPA_MAX; + result = false; + + list = group->branches; - for (i = 0; i < list[0].count && result == VMPA_MAX; i++) + for (i = 0; i < list[0].count && !result; i++) { keep = true; - for (j = 1; j < count && keep; j++) - keep = is_addr_in_branch(&list[j], &list[0].jumps[i]); + for (j = 1; j < group->count && keep; j++) + keep = is_addr_in_branch(&list[j], &list[0].hops[i]); if (keep) - result = list[0].jumps[i]; + copy_vmpa(common, &list[0].hops[i]); } @@ -451,6 +750,228 @@ static vmpa_t compute_first_common_addr_in_group(const branch_info *list, size_t * * * Paramètres : instrs = ensemble des instructions d'assemblage. * * coverage = délimitations de la zone à couvrir. * +* first = première instruction d'un bloc préliminaire. * +* cur = instruction courante dans le traitement. * +* * +* Description : Procède à la création d'un bloc d'instructions simple. * +* * +* Retour : Bloc créé ou NULL. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static GInstrBlock *build_instruction_block_simple(GArchInstruction *instrs, code_coverage *coverage, GArchInstruction **first, GArchInstruction *cur) +{ + GInstrBlock *result; /* Regroupement à retourner */ + + if (*first != NULL) + { + result = g_flow_block_new(instrs, *first, cur); + + mark_range_as_processed_in_coverage(coverage, *first); + + *first = NULL; + + } + else result = NULL; + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : instrs = ensemble des instructions d'assemblage. * +* coverage = délimitations de la zone à couvrir. * +* cases = branches conditionnelles des situations. * +* next = localisation de l'instruction de reprise. * +* * +* Description : Procède à la définition d'un bloc d'instructions selectif. * +* * +* Retour : Bloc créé et enregistré, ou NULL si erreur. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static GInstrBlock *build_instruction_blocks_case(GArchInstruction *instrs, code_coverage *coverage, const branch_group *cases, vmpa2t *next) +{ + GInstrBlock *result; /* Regroupement à retourner */ + bool has_common; /* Fin commune ? */ + size_t i; /* Boucle de parcours #1 */ + code_coverage *sub_coverage; /* Couverture pour les suivants*/ + size_t j; /* Boucle de parcours #2 */ + GInstrBlock *block; /* Nouveau bloc mis en place */ + + has_common = compute_first_common_addr_in_group(cases, next); + if (!has_common) return NULL; + + result = g_virtual_block_new(); + + for (i = 0; i < cases->count; i++) + { + sub_coverage = dup_code_coverage(coverage, &cases->branches[i].hops[0]); + + add_ending_address_code_coverage(sub_coverage, next); + + for (j = 0; j < cases->count; j++) + add_ending_address_code_coverage(sub_coverage, &cases->branches[j].hops[0]); + + block = build_instruction_blocks(instrs, sub_coverage); + + if (block != NULL) + g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block); + + delete_code_coverage(sub_coverage); + + } + + if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0) + { + g_object_unref(G_OBJECT(result)); + result = NULL; + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : instrs = ensemble des instructions d'assemblage. * +* coverage = délimitations de la zone à couvrir. * +* true_branch = branche conditionnelle correspondant à true. * +* false_branch = branche conditionnelle correspondant à false. * +* next = localisation de l'instruction de reprise. * +* * +* Description : Procède à la définition d'un bloc d'instruction if/then/else.* +* * +* Retour : Bloc créé et enregistré, ou NULL si erreur. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static GInstrBlock *build_instruction_blocks_ite(GArchInstruction *instrs, code_coverage *coverage, const branch_info *true_branch, const branch_info *false_branch, vmpa2t *next) +{ + GInstrBlock *result; /* Regroupement à retourner */ + bool has_common; /* Fin commune ? */ + GInstrBlock *block; /* Nouveau bloc mis en place */ + + has_common = compute_first_common_addr(true_branch, false_branch, next); + if (!has_common) return NULL; + + result = g_virtual_block_new(); + + /** + * Encapsulation des branches conditionnelles. + */ + + GInstrBlock *build_instr_block_bi(GArchInstruction *instrs, const code_coverage *coverage, const branch_info *br0, const branch_info *br1, const vmpa2t *next) + { + GInstrBlock *result; /* Bloc construit à renvoyer */ + code_coverage *sub_coverage; /* Couverture pour les suivants*/ + + result = NULL; + + if (br0->count > 0) + { + sub_coverage = dup_code_coverage(coverage, &br0->hops[0]); + + add_ending_address_code_coverage(sub_coverage, next); + + if (br1->count > 0) + add_ending_address_code_coverage(sub_coverage, &br1->hops[0]); + + result = build_instruction_blocks(instrs, sub_coverage); + + delete_code_coverage(sub_coverage); + + } + + return result; + + } + + /* Branche 'true' */ + + block = build_instr_block_bi(instrs, coverage, true_branch, false_branch, next); + + if (block != NULL) + g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block); + + /* Branche 'false' */ + + block = build_instr_block_bi(instrs, coverage, false_branch, true_branch, next); + + if (block != NULL) + g_virtual_block_add_child(G_VIRTUAL_BLOCK(result), block); + + /* Conclusion */ + + if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(result)) == 0) + { + g_object_unref(G_OBJECT(result)); + result = NULL; + } + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : result = liste générale résultante du découpage. [OUT] * +* cached = emplacement pour le cache des résultats. [OUT] * +* instrs = ensemble des instructions d'assemblage. * +* coverage = délimitations de la zone à couvrir. * +* exceptions = branche conditionnelle correspondant à true. * +* main_branch = branche principale avec son flot d'exécution. * +* * +* Description : Procède à la définition d'un bloc d'instructions d'exception.* +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void add_instruction_blocks_except(GInstrBlock **result, GInstrBlock **cached, GArchInstruction *instrs, code_coverage *coverage, const branch_group *exceptions, const branch_info *main_branch) +{ + size_t i; /* Boucle de parcours */ + vmpa2t stop_addr; /* Adresse de fin de bloc */ + bool has_stop; /* Fin commune ? */ + code_coverage *sub_coverage; /* Couverture pour les suivants*/ + GInstrBlock *block; /* Nouveau bloc mis en place */ + + for (i = 0; i < exceptions->count; i++) + { + has_stop = compute_first_common_addr(main_branch, &exceptions->branches[i], &stop_addr); + if (!has_stop) continue; + + sub_coverage = dup_code_coverage(coverage, &exceptions->branches[i].hops[0]); + add_ending_address_code_coverage(sub_coverage, &stop_addr); + + block = build_instruction_blocks(instrs, sub_coverage); + + if (block != NULL) + DELAYED_BLOCK_ADDING(*result, *cached, block); + + delete_code_coverage(sub_coverage); + + } + +} + + +/****************************************************************************** +* * +* Paramètres : instrs = ensemble des instructions d'assemblage. * +* coverage = délimitations de la zone à couvrir. * * * * Description : Procède à la définition de bloc regroupant des instructions. * * * @@ -460,7 +981,7 @@ static vmpa_t compute_first_common_addr_in_group(const branch_info *list, size_t * * ******************************************************************************/ -static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code_coverage *coverage) +static GInstrBlock *build_instruction_blocks(GArchInstruction *instrs, code_coverage *coverage) { GInstrBlock *result; /* Regroupement à retourner */ GInstrBlock *result_cached; /* Temporisation pour unicité */ @@ -468,70 +989,42 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code GArchInstruction *first; /* Première instruction */ GArchInstruction *last; /* Dernière instruction */ GArchInstruction *iter; /* Boucle de parcours */ - vmpa_t addr; /* Adresse de la destination */ + const mrange_t *range; /* Emplacement d'instruction */ + const vmpa2t *addr; /* Adresse de la destination */ 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 #1 */ GInstrBlock *block; /* Nouveau bloc mis en place */ - GInstrBlock *parent; /* Mémorisation pour les liens */ GInstrBlock *group; /* Regroupement de blocs */ size_t not_handled; /* Quantité de liens non gérés */ - vmpa_t next_addr; /* Prochaine instruction visée */ - branch_info *cases_branches; /* Branches d'un aiguillage */ - size_t cases_count; /* Nombre d'aiguillages */ + vmpa2t next_addr; /* Prochaine instruction visée */ + branch_group cases_branches; /* Branches d'un aiguillage */ branch_info true_branch; /* Branche 'condition vraie' */ branch_info false_branch; /* Branche 'condition fausse' */ - branch_info *excep_branches; /* Branches d'exceptions */ - size_t excep_count; /* Nombre d'exceptions */ - code_coverage *sub_coverage; /* Couverture pour les suivants*/ - size_t j; /* Boucle de parcours #2 */ - vmpa_t stop_addr; /* Adresse de fin de bloc */ + branch_group excep_branches; /* Branches d'exceptions */ + branch_info *branch; /* Branche à suivre */ result = NULL; result_cached = NULL; - /** - * Procédure d'ajout de blocs : pour le premier, on conserve le bloc en mémoire - * et on attend. Si rien ne suit, il constitura l'unique retour. Sinon, on - * l'ajoute à partir de la sauvegarde, et le reste suit. - */ -#define DELAYED_BLOCK_ADDING(res, cache, blk) \ - do \ - { \ - if (res == NULL) \ - { \ - if (cache == NULL) \ - cache = blk; \ - else \ - { \ - res = g_virtual_block_new(); \ - g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), cache); \ - } \ - } \ - \ - if (res != NULL) \ - g_virtual_block_add_child(G_VIRTUAL_BLOCK(res), blk); \ - \ - } \ - while (0) - first = NULL; last = NULL; - memset(&main_branch, 0, sizeof(branch_info)); - find_next_jumps(instrs, coverage->start, coverage, &main_branch); + init_branch_info(&main_branch); + find_next_hops(instrs, &coverage->start, coverage, &main_branch); - for (iter = g_arch_instruction_find_by_address(instrs, coverage->start, true); + for (iter = g_arch_instruction_find_by_address(instrs, &coverage->start, true); iter != NULL; ) { - g_arch_instruction_get_location(iter, NULL, NULL, &addr); + range = g_arch_instruction_get_range(iter); + addr = get_mrange_addr(range); - if (code_coverage_stop_here(coverage, &addr)) break; + if (code_coverage_stop_here(coverage, addr)) break; /* On s'arrêter si l'instruction est déjà décompilée */ - if (MACRO_IS_PROCESSED(iter)) break; + if (is_range_processed_in_coverage(coverage, range)) break; if (first == NULL) first = iter; @@ -550,65 +1043,50 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code dcount = g_arch_instruction_get_destinations(iter, &dests, &types, NULL); not_handled = 0; - next_addr = VMPA_MAX; - cases_branches = NULL; - cases_count = 0; - memset(&true_branch, 0, sizeof(branch_info)); - memset(&false_branch, 0, sizeof(branch_info)); - excep_branches = NULL; - excep_count = 0; + init_vmpa(&next_addr, VMPA_NO_PHYSICAL, VMPA_NO_VIRTUAL); + + init_branch_group(&cases_branches); + init_branch_info(&true_branch); + init_branch_info(&false_branch); + init_branch_group(&excep_branches); for (i = 0; i < dcount; i++) + { + branch = NULL; + switch (types[i]) { case ILT_EXEC_FLOW: case ILT_JUMP: - block = g_flow_block_new(instrs, first, iter); - MACRO_MARK_AS_PROCESSED(first); - first = NULL; - + block = build_instruction_block_simple(instrs, coverage, &first, iter); DELAYED_BLOCK_ADDING(result, result_cached, block); - g_arch_instruction_get_location(dests[i], NULL, NULL, &next_addr); + range = g_arch_instruction_get_range(iter); + copy_vmpa(&next_addr, get_mrange_addr(range)); break; case ILT_CASE_JUMP: - - g_arch_instruction_get_location(dests[i], NULL, NULL, &addr); - - cases_branches = (branch_info *)realloc(cases_branches, - ++cases_count * sizeof(branch_info)); - memset(&cases_branches[cases_count - 1], 0, sizeof(branch_info)); - find_next_jumps(instrs, addr, coverage, &cases_branches[cases_count - 1]); - + branch = extend_branch_group(&cases_branches); break; case ILT_JUMP_IF_TRUE: - g_arch_instruction_get_location(dests[i], NULL, NULL, &addr); - find_next_jumps(instrs, addr, coverage, &true_branch); + branch = &true_branch; break; case ILT_JUMP_IF_FALSE: - g_arch_instruction_get_location(dests[i], NULL, NULL, &addr); - find_next_jumps(instrs, addr, coverage, &false_branch); + branch = &false_branch; break; case ILT_CATCH_EXCEPTION: - - g_arch_instruction_get_location(dests[i], NULL, NULL, &addr); - - excep_branches = (branch_info *)realloc(excep_branches, - ++excep_count * sizeof(branch_info)); - memset(&excep_branches[excep_count - 1], 0, sizeof(branch_info)); - find_next_jumps(instrs, addr, coverage, &excep_branches[excep_count - 1]); + branch = extend_branch_group(&excep_branches); /** * Les deux cas sont les seuls à ne pas conduire à une définition de * next_addr, donc on les comptabilise sur un pied d'égalité ! */ - //break; + /* break; */ default: not_handled++; @@ -616,184 +1094,89 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code } - /* Post-traitements de ILT_CASE_JUMP */ - if (cases_count > 0) - { - /** - * On doit clôturer le bloc renvoyant vers les branches de cas ici. - * Les sauts conditionnels sont normalement présents de façon exclusive, - * sauf pour les exceptions, qui sont traitées après. - */ - block = g_flow_block_new(instrs, first, iter); - MACRO_MARK_AS_PROCESSED(first); - first = NULL; - - DELAYED_BLOCK_ADDING(result, result_cached, block); - - next_addr = compute_first_common_addr_in_group(cases_branches, cases_count); - - parent = block; - group = g_virtual_block_new(); - - for (i = 0; i < cases_count; i++) + /* Si on a une branche à compléter... */ + if (branch != NULL) { - sub_coverage = dup_code_coverage(cases_branches[i].jumps[0], coverage); + range = g_arch_instruction_get_range(iter); + addr = get_mrange_addr(range); - add_ending_address_code_coverage(sub_coverage, &next_addr); + find_next_hops(instrs, addr, coverage, branch); - for (j = 0; j < cases_count; j++) - if (cases_branches[j].jumps[0] != cases_branches[i].jumps[0]) - add_ending_address_code_coverage(sub_coverage, &cases_branches[j].jumps[0]); - - block = build_instruction_block(instrs, sub_coverage); - - delete_code_coverage(sub_coverage); - - if (block != NULL) + } - g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block); + } - free(cases_branches[i].jumps); + /* Post-traitements de ILT_CASE_JUMP */ + if (cases_branches.count > 0) + { + block = build_instruction_block_simple(instrs, coverage, &first, iter); + DELAYED_BLOCK_ADDING(result, result_cached, block); - } + group = build_instruction_blocks_case(instrs, coverage, &cases_branches, &next_addr); - if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(group)) > 0) + if (group != NULL) { DELAYED_BLOCK_ADDING(result, result_cached, group); - g_instr_block_set_links_block(parent, group); + g_instr_block_set_links_block(block, group); } - else - g_object_unref(G_OBJECT(group)); - - free(cases_branches); } + /* Post-traitements de ILT_JUMP_IF_TRUE / ILT_JUMP_IF_FALSE */ else if (true_branch.count > 0 || false_branch.count > 0) { - next_addr = compute_first_common_addr(&true_branch, &false_branch); - - /** - * On doit clôturer le bloc renvoyant vers les branches 'true' et 'false' ici. - * Les sauts conditionnels sont normalement présents de façon exclusive, - * sauf pour les exceptions, qui sont traitées après. - */ - block = g_flow_block_new(instrs, first, iter); - MACRO_MARK_AS_PROCESSED(first); - first = NULL; - + block = build_instruction_block_simple(instrs, coverage, &first, iter); DELAYED_BLOCK_ADDING(result, result_cached, block); - parent = block; - group = g_virtual_block_new(); - - /* Branche 'true' */ - - if (true_branch.count > 0) - { - sub_coverage = dup_code_coverage(true_branch.jumps[0], coverage); - add_ending_address_code_coverage(sub_coverage, &next_addr); - if (false_branch.count > 0) - add_ending_address_code_coverage(sub_coverage, &false_branch.jumps[0]); - - block = build_instruction_block(instrs, sub_coverage); - if (block != NULL) - g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block); - - delete_code_coverage(sub_coverage); - - } - - /* Branche 'false' */ + group = build_instruction_blocks_ite(instrs, coverage, &true_branch, &false_branch, &next_addr); - if (false_branch.count > 0) - { - sub_coverage = dup_code_coverage(false_branch.jumps[0], coverage); - add_ending_address_code_coverage(sub_coverage, &next_addr); - if (true_branch.count > 0) - add_ending_address_code_coverage(sub_coverage, &true_branch.jumps[0]); - - block = build_instruction_block(instrs, sub_coverage); - if (block != NULL) - g_virtual_block_add_child(G_VIRTUAL_BLOCK(group), block); - - delete_code_coverage(sub_coverage); - - } - - /* Conclusion */ - - if (true_branch.count > 0) free(true_branch.jumps); - if (false_branch.count > 0) free(false_branch.jumps); - - if (g_virtual_block_count_children(G_VIRTUAL_BLOCK(group)) > 0) + if (group != NULL) { DELAYED_BLOCK_ADDING(result, result_cached, group); - g_instr_block_set_links_block(parent, group); + g_instr_block_set_links_block(block, group); } - else - g_object_unref(G_OBJECT(group)); } /* Post-traitements de ILT_CATCH_EXCEPTION */ - if (excep_count > 0) + if (excep_branches.count > 0) { - if (first != NULL) - { - block = g_flow_block_new(instrs, first, iter); - MACRO_MARK_AS_PROCESSED(first); - first = NULL; - - DELAYED_BLOCK_ADDING(result, result_cached, block); - - } - - for (j = 0; j < excep_count; j++) - { - stop_addr = compute_first_common_addr(&main_branch, &excep_branches[j]); + block = build_instruction_block_simple(instrs, coverage, &first, iter); + if (block != NULL) DELAYED_BLOCK_ADDING(result, result_cached, block); - sub_coverage = dup_code_coverage(excep_branches[j].jumps[0], coverage); - add_ending_address_code_coverage(sub_coverage, &stop_addr); - - block = build_instruction_block(instrs, sub_coverage); - - delete_code_coverage(sub_coverage); - - if (block != NULL) - - DELAYED_BLOCK_ADDING(result, result_cached, block); - - free(excep_branches[j].jumps); - - } - - free(excep_branches); + add_instruction_blocks_except(&result, &result_cached, instrs, coverage, + &excep_branches, &main_branch); } + clean_branch_group(&cases_branches); + clean_branch_info(&true_branch); + clean_branch_info(&false_branch); + clean_branch_group(&excep_branches); + /* Détermination du prochain point de chute */ if (not_handled == dcount) iter = g_arch_instruction_get_next_iter(instrs, iter, VMPA_MAX); else - iter = g_arch_instruction_find_by_address(instrs, next_addr, true); + iter = g_arch_instruction_find_by_address(instrs, &next_addr, true); } if (first != NULL && last != NULL) { - if (!MACRO_IS_PROCESSED(first)) - { - block = g_flow_block_new(instrs, first, last); - MACRO_MARK_AS_PROCESSED(first); + range = g_arch_instruction_get_range(first); + if (!is_range_processed_in_coverage(coverage, range)) + { + block = build_instruction_block_simple(instrs, coverage, &first, last); DELAYED_BLOCK_ADDING(result, result_cached, block); - } } + clean_branch_info(&main_branch); + return (result != NULL ? result : result_cached); } @@ -818,19 +1201,17 @@ static GInstrBlock *build_instruction_block(GArchInstruction *instrs, const code void group_routines_instructions(GArchInstruction *list, GBinRoutine **routines, size_t count, GtkExtStatusBar *statusbar, bstatus_id_t id) { size_t i; /* Boucle de parcours */ - vmpa_t start; /* Adresse de départ */ - vmpa_t end; /* Adresse de fin */ + const mrange_t *range; /* Emplacement de routine */ code_coverage *coverage; /* Couverture de zone de code */ GInstrBlock *block; /* Regroupement d'instructions */ for (i = 0; i < count; i++) { - start = g_binary_routine_get_address(routines[i]); - end = start + g_binary_routine_get_size(routines[i]); + range = g_binary_routine_get_range(routines[i]); - coverage = create_code_coverage(start, end); + coverage = create_code_coverage(range); - block = build_instruction_block(list, coverage); + block = build_instruction_blocks(list, coverage); g_binary_routine_set_basic_blocks(routines[i], block); delete_code_coverage(coverage); diff --git a/src/analysis/disass/macro.h b/src/analysis/disass/macro.h index 7b95d01..82185bb 100644 --- a/src/analysis/disass/macro.h +++ b/src/analysis/disass/macro.h @@ -26,6 +26,7 @@ #include "../routine.h" +#include "../../arch/instruction.h" #include "../../gtkext/gtkextstatusbar.h" |