From f9c4cfc72cd8d7eb08ded8287fc5af1497567f8b Mon Sep 17 00:00:00 2001
From: Cyrille Bagard <nocbos@gmail.com>
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 <nocbos@gmail.com>
+ * 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 <nocbos@gmail.com>
+
* 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