From f9c4cfc72cd8d7eb08ded8287fc5af1497567f8b Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Tue, 6 Oct 2015 21:23:05 +0000 Subject: Optimized the search of instructions a little bit using routine coverages. git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@587 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a --- ChangeLog | 10 +++ src/arch/processor-int.h | 18 +++++ src/arch/processor.c | 177 +++++++++++++++++++++++++++++++++++++++++++++-- src/arch/vmpa.c | 38 +++++++++- src/arch/vmpa.h | 5 ++ 5 files changed, 243 insertions(+), 5 deletions(-) diff --git a/ChangeLog b/ChangeLog index 436411a..b98dfce 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,15 @@ 15-10-06 Cyrille Bagard + * src/arch/processor.c: + * src/arch/processor-int.h: + Optimize the search of instructions a little bit using routine coverages. + + * src/arch/vmpa.c: + * src/arch/vmpa.h: + Extend the functions dealing with memory ranges. + +15-10-06 Cyrille Bagard + * src/analysis/disass/loop.c: Optimize loop detections using bit fields. diff --git a/src/arch/processor-int.h b/src/arch/processor-int.h index f4562f6..fcd7a52 100644 --- a/src/arch/processor-int.h +++ b/src/arch/processor-int.h @@ -61,6 +61,20 @@ typedef GArchInstruction * (* decode_instruction_fc) (const GArchProcessor *, GP typedef GArchInstruction * (* disass_instr_fc) (const GArchProcessor *, GProcContext *, const GBinContent *, vmpa2t *); + +/* Couverture d'un groupe d'instructions */ +typedef struct _instr_coverage +{ + mrange_t range; /* Couverture du groupement */ + + size_t start; /* Indice de départ */ + size_t count; /* Quantité d'inclusions */ + +} instr_coverage; + + + + /* Définition générique d'un processeur d'architecture (instance) */ struct _GArchProcessor { @@ -77,6 +91,10 @@ struct _GArchProcessor size_t instr_allocated; /* Taille de la liste allouée */ size_t instr_count; /* Taille de la liste aplatie */ + instr_coverage *coverages; /* Liste de couvertures */ + size_t cov_allocated; /* Taille de la liste allouée */ + size_t cov_count; /* Taille de la liste utilisée */ + }; diff --git a/src/arch/processor.c b/src/arch/processor.c index 7e2ecec..c70d586 100644 --- a/src/arch/processor.c +++ b/src/arch/processor.c @@ -63,13 +63,26 @@ static void g_arch_processor_init(GArchProcessor *); +/* ------------------ MANIPULATIONS DES INSTRUCTIONS DESASSEMBLEES ------------------ */ + + +/* Démarre la définition d'un nouveau groupe d'instructions. */ +static void g_arch_processor_add_new_coverage(GArchProcessor *, GArchInstruction *, size_t); + +/* Termine la définition d'un nouveau groupe d'instructions. */ +static void g_arch_processor_finish_last_coverage(GArchProcessor *, GArchInstruction *, size_t); + +/* Recherche un groupe d'instruction d'après son adresse. */ +static bool g_arch_processor_find_coverage_by_address(const GArchProcessor *, const vmpa2t *, size_t *, size_t *); + + + /* Indique le type défini pour un processeur d'architecture. */ G_DEFINE_TYPE(GArchProcessor, g_arch_processor, G_TYPE_OBJECT); - /****************************************************************************** * * * Paramètres : klass = classe à initialiser. * @@ -102,6 +115,9 @@ static void g_arch_processor_class_init(GArchProcessorClass *klass) static void g_arch_processor_init(GArchProcessor *proc) { + proc->coverages = NULL; + proc->cov_allocated = 0; + proc->cov_count = 0; } @@ -307,6 +323,131 @@ GArchInstruction *g_arch_processor_disassemble(const GArchProcessor *proc, GProc /****************************************************************************** * * +* Paramètres : proc = architecture à comléter par la procédure. * +* first = première instruction d'un nouveau groupe. * +* start = indice de cette instruction dans l'ensemble global. * +* * +* Description : Démarre la définition d'un nouveau groupe d'instructions. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_arch_processor_add_new_coverage(GArchProcessor *proc, GArchInstruction *first, size_t start) +{ + instr_coverage *coverage; /* Couverture à définir */ + const mrange_t *irange; /* Couverture de l'instruction */ + + /* Mise à disposition de d'avantage d'espace */ + if (proc->cov_allocated == proc->cov_count) + { + proc->cov_allocated += INSTR_ALLOC_BLOCK; + + proc->coverages = (instr_coverage *)realloc(proc->coverages, + proc->cov_allocated * sizeof(instr_coverage)); + + } + + coverage = &proc->coverages[proc->cov_count++]; + + irange = g_arch_instruction_get_range(first); + + init_mrange(&coverage->range, get_mrange_addr(irange), 0); + + coverage->start = start; + +} + + +/****************************************************************************** +* * +* Paramètres : proc = architecture à comléter par la procédure. * +* last = dernière instruction d'un nouveau groupe. * +* end = indice de cette instruction dans l'ensemble global. * +* * +* Description : Termine la définition d'un nouveau groupe d'instructions. * +* * +* Retour : - * +* * +* Remarques : - * +* * +******************************************************************************/ + +static void g_arch_processor_finish_last_coverage(GArchProcessor *proc, GArchInstruction *last, size_t end) +{ + instr_coverage *coverage; /* Couverture à définir */ + const mrange_t *irange; /* Couverture de l'instruction */ + phys_t diff; /* Ecart entre les extrémités */ + + coverage = &proc->coverages[proc->cov_count - 1]; + + irange = g_arch_instruction_get_range(last); + + diff = compute_vmpa_diff(get_mrange_addr(&coverage->range), get_mrange_addr(irange)); + diff += get_mrange_length(irange); + + set_mrange_length(&coverage->range, diff); + + coverage->count = end - coverage->start + 1; + +} + + +/****************************************************************************** +* * +* Paramètres : proc = processeur recensant diverses instructions. * +* addr = position en mémoire ou physique à chercher. * +* start = indice de départ du groupe concerné trouvé. [OUT] * +* end = indice de fin du groupe d'instructions visées. [OUT] * +* * +* Description : Recherche un groupe d'instruction d'après son adresse. * +* * +* Retour : Bilan de la recherche menée. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static bool g_arch_processor_find_coverage_by_address(const GArchProcessor *proc, const vmpa2t *addr, size_t *start, size_t *count) +{ + bool result; /* Bilan à retourner */ + void *ptr; /* Résultat des recherches */ + + int search_for_coverage_by_addr(const vmpa2t *a, const instr_coverage *c) + { + int status; /* Bilan d'une comparaison */ + + status = cmp_mrange_with_vmpa(&c->range, a); + + return status; + + } + + ptr = bsearch(addr, proc->coverages, proc->cov_count, + sizeof(instr_coverage), (__compar_fn_t)search_for_coverage_by_addr); + + if (ptr != NULL) + { + result = true; + *start = ((instr_coverage *)ptr)->start; + *count = ((instr_coverage *)ptr)->count; + } + else + result = false; + + return result; + +} + + + + + + +/****************************************************************************** +* * * Paramètres : proc = architecture visée par la procédure. * * list = liste des instructions désassemblées. * * * @@ -320,11 +461,14 @@ GArchInstruction *g_arch_processor_disassemble(const GArchProcessor *proc, GProc void g_arch_processor_set_disassembled_instructions(GArchProcessor *proc, GArchInstruction *list) { + GArchInstruction *last; /* Dernière instruction traitée*/ GArchInstruction *iter; /* Boucle de parcours */ /* TODO : vider une éventuelle liste existante */ /* TODO : incrémenter les références (cf. code Python) */ + last = NULL; + ainstr_list_for_each(iter, list) { /* Mise à disposition de d'avantage d'espace */ @@ -337,10 +481,26 @@ void g_arch_processor_set_disassembled_instructions(GArchProcessor *proc, GArchI } + /* Constitution des groupes */ + if (last == NULL || g_arch_instruction_get_flags(iter) & AIF_ROUTINE_START) + { + if (last != NULL) + g_arch_processor_finish_last_coverage(proc, last, proc->instr_count - 1); + + g_arch_processor_add_new_coverage(proc, iter, proc->instr_count); + + } + + /* Enregistrement */ proc->instructions[proc->instr_count++] = iter; + last = iter; + } + if (last != NULL) + g_arch_processor_finish_last_coverage(proc, last, proc->instr_count - 1); + } @@ -383,6 +543,8 @@ GArchInstruction *g_arch_processor_get_disassembled_instructions(const GArchProc GArchInstruction *g_arch_processor_find_instr_by_address(const GArchProcessor *proc, const vmpa2t *addr) { GArchInstruction *result; /* Trouvaille à retourner */ + size_t cov_start; /* Début d'un groupe ciblé */ + size_t cov_count; /* Nombre d'éléments à tester */ void *ptr; /* Résultat des recherches */ int search_for_instr_by_addr(const vmpa2t *a, const GArchInstruction **b) @@ -395,10 +557,17 @@ GArchInstruction *g_arch_processor_find_instr_by_address(const GArchProcessor *p } - ptr = bsearch(addr, proc->instructions, proc->instr_count, - sizeof(GArchInstruction *), (__compar_fn_t)search_for_instr_by_addr); - result = (ptr != NULL ? *((GArchInstruction **)ptr) : NULL); + if (g_arch_processor_find_coverage_by_address(proc, addr, &cov_start, &cov_count)) + { + ptr = bsearch(addr, &proc->instructions[cov_start], cov_count, + sizeof(GArchInstruction *), (__compar_fn_t)search_for_instr_by_addr); + + result = (ptr != NULL ? *((GArchInstruction **)ptr) : NULL); + + } + else + result = NULL; return result; diff --git a/src/arch/vmpa.c b/src/arch/vmpa.c index 5030562..4c2b4cf 100644 --- a/src/arch/vmpa.c +++ b/src/arch/vmpa.c @@ -790,6 +790,42 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b) /****************************************************************************** * * +* Paramètres : a = première définition à analyser. * +* b = seconde définition à analyser. * +* * +* Description : Compare une couverture mémoire avec une localisation simple. * +* * +* Retour : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut). * +* * +* Remarques : - * +* * +******************************************************************************/ + +int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b) +{ + int result; /* Bilan à retourner */ + phys_t diff; /* Espace entre deux adresses */ + + result = cmp_vmpa(b, &a->addr); + + if (result >= 0) + { + diff = compute_vmpa_diff(&a->addr, b); + + if (diff < a->length) + result = 0; + else + result = 1; + + } + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : range = zone mémoire à consulter. * * sub = éventuelle sous-région à valider. * * * @@ -840,7 +876,7 @@ bool mrange_contains_addr(const mrange_t *range, const vmpa2t *addr) ret = cmp_vmpa(&range->addr, addr); - if (ret <= -1) + if (ret < 0) { diff = compute_vmpa_diff(&range->addr, addr); diff --git a/src/arch/vmpa.h b/src/arch/vmpa.h index 8881ac1..50a02a2 100644 --- a/src/arch/vmpa.h +++ b/src/arch/vmpa.h @@ -174,6 +174,8 @@ typedef struct _mrange_t #define get_mrange_addr(r) &(r)->addr #define get_mrange_length(r) (r)->length +#define set_mrange_length(r, l) (r)->length = l + /* Initialise une plage dans l'espace mémoire/physique. */ void init_mrange(mrange_t *, const vmpa2t *, phys_t); @@ -184,6 +186,9 @@ void copy_mrange(mrange_t *, const mrange_t *); /* Compare deux couvertures mémoire selon leurs propriétés. */ int cmp_mrange(const mrange_t *, const mrange_t *); +/* Compare une couverture mémoire avec une localisation simple. */ +int cmp_mrange_with_vmpa(const mrange_t *, const vmpa2t *); + /* Indique si une zone en contient une autre ou non. */ bool mrange_contains_mrange(const mrange_t *, const mrange_t *); -- cgit v0.11.2-87-g4458