From 2b8f655628652f3cfb61c8b82d4b54fbf3ed9869 Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sat, 28 Jan 2017 00:22:49 +0100 Subject: Avoided deadlocks in access to instruction sources and destinations. --- ChangeLog | 8 +++ src/arch/instruction-int.h | 62 ++++++++++------ src/arch/instruction.c | 171 +++++++++++++++++++++++++++++++++------------ src/arch/instruction.h | 28 ++++---- 4 files changed, 191 insertions(+), 78 deletions(-) diff --git a/ChangeLog b/ChangeLog index b22f4c7..c716771 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,5 +1,13 @@ 17-01-28 Cyrille Bagard + * src/arch/instruction-int.h: + * src/arch/instruction.c: + * src/arch/instruction.h: + Avoid deadlocks in access to instruction sources and destinations. + Clean the code and save memory. + +17-01-28 Cyrille Bagard + * src/arch/link.c: Fix links between instructions for conditional branches. diff --git a/src/arch/instruction-int.h b/src/arch/instruction-int.h index 2d829c0..e7d5ba0 100644 --- a/src/arch/instruction-int.h +++ b/src/arch/instruction-int.h @@ -27,24 +27,21 @@ #include "archbase.h" #include "instruction.h" -#include "../common/dllist.h" -/* Liste les registres lus et écrits par l'instruction. */ -typedef void (* get_instruction_rw_regs_fc) (const GArchInstruction *, GArchRegister ***, size_t *, GArchRegister ***, size_t *); - /* Indique l'encodage d'une instruction de façon détaillée. */ typedef const char * (* get_instruction_encoding_fc) (const GArchInstruction *); +/* Fournit le nom humain de l'instruction manipulée. */ +typedef const char * (* get_instruction_keyword_fc) (GArchInstruction *, AsmSyntax ); + /* Ajoute à un tampon GLib le contenu de l'instance spécifiée. */ typedef GBufferLine * (* print_instruction_fc) (const GArchInstruction *, GBufferLine *, size_t, size_t); -/* Fournit le nom humain de l'instruction manipulée. */ -typedef const char * (* get_instruction_keyword_fc) (GArchInstruction *, AsmSyntax ); +/* Liste les registres lus et écrits par l'instruction. */ +typedef void (* get_instruction_rw_regs_fc) (const GArchInstruction *, GArchRegister ***, size_t *, GArchRegister ***, size_t *); -/* Informe sur une éventuelle référence à une autre instruction. */ -typedef InstructionLinkType (* get_instruction_link_fc) (const GArchInstruction *, vmpa_t *); /* Définition générique d'une instruction d'architecture (instance) */ @@ -61,26 +58,49 @@ struct _GArchInstruction GArchOperand **operands; /* Liste des opérandes */ size_t operands_count; /* Nbre. d'opérandes utilisées */ + /** + * Il existe le besoin indéniable d'un verrou pour les accès aux instructions + * liées. Il faut par ailleurs un verrou distinct pour les sources et les + * destination car une même instruction peut boucler sur elle même et la + * fonction g_arch_instruction_change_link() pose des verrous sur les + * deux extrémités. + * + * Par ailleurs, la consommation mémoire augmente vite : GRWLock pèse 16 + * octets et size_t mesure la taille d'un long sur 64 bits. + * + * Que ce soit avec les pointeurs (un allocateur aligne généralement les + * adresses retournées) ou avec les tailles (il est peu probable d'avoir + * 0x80000000 instructions d'origine), on dispose d'espace mémoire inutilisé + * adapté pour compresser la structure GArchInstruction. + * + * La GLib propose incidemment des fonctions g_bit_lock() / g_bit_unlock()... + * + * On perd au passage la distinction entre les accès en lecture et ceux en + * écriture, mais tant pis : la réduction de l'empreinte mémoire prime ! + * + * Par contre la documentation indique : + * + * """ + * Attempting to lock on two different bits within the same integer is not supported. + * """ + * + * Donc on conserve un compteur distinct pour chaque extrémité. + */ + instr_link_t *from; /* Origines des références */ - size_t from_count; /* Nombre de ces origines */ instr_link_t *to; /* Instructions visées */ - size_t to_count; /* Nombre de ces destinations */ - GRWLock link_access; /* Verrou de protection */ -#ifndef NDEBUG - gint hold_link_access; /* Suivi des verrouillages */ -#endif + gint from_count; /* Nombre de ces origines */ + gint to_count; /* Nombre de ces destinations */ ArchInstrFlag flags; /* Informations complémentaires*/ - //get_instruction_rw_regs_fc get_rw_regs; /* Liste des registres liés */ - //print_instruction_fc print; /* Imprime l'ensemble */ - //get_instruction_keyword_fc get_key; /* Texte humain équivalent */ - //is_instruction_return_fc is_return; /* Retour de fonction ou pas ? */ - //decomp_instr_fc decomp; /* Procédure de décompilation */ - }; +/* Bit de verrou pour les champs (from|to)_count */ +#define INSTR_LINK_LOCK_BIT 31 + + /* Définition générique d'une instruction d'architecture (classe) */ struct _GArchInstructionClass { @@ -91,6 +111,8 @@ struct _GArchInstructionClass print_instruction_fc print; /* Imprime l'ensemble */ + //get_instruction_rw_regs_fc get_rw_regs; /* Liste des registres liés */ + }; diff --git a/src/arch/instruction.c b/src/arch/instruction.c index db37bf7..f539ddb 100644 --- a/src/arch/instruction.c +++ b/src/arch/instruction.c @@ -51,6 +51,29 @@ static void g_arch_instruction_finalize(GArchInstruction *); +/* ------------------- DEFINITION DES LIAISONS ENTRE INSTRUCTIONS ------------------- */ + + +/* Dénombre les liens présents à une extrémité donnée. */ +static size_t g_arch_instruction_get_link_counter(GArchInstruction *, bool); + +#define g_arch_instruction_get_source_counter(ins) \ + g_arch_instruction_get_link_counter(ins, true) + +#define g_arch_instruction_get_destination_counter(ins) \ + g_arch_instruction_get_link_counter(ins, false) + +/* Incrémente le nombre de liens définis à une extrémité donnée. */ +static size_t g_arch_instruction_inc_link_counter(GArchInstruction *, bool); + +#define g_arch_instruction_inc_source_counter(ins) \ + g_arch_instruction_inc_link_counter(ins, true) + +#define g_arch_instruction_inc_destination_counter(ins) \ + g_arch_instruction_inc_link_counter(ins, false) + + + /* ------------------------ OFFRE DE CAPACITES DE GENERATION ------------------------ */ @@ -124,10 +147,8 @@ static void g_arch_instruction_init(GArchInstruction *instr) { instr->max_displayed_len = VMPA_NO_PHYSICAL; - g_rw_lock_init(&instr->link_access); -#ifndef NDEBUG - g_atomic_int_set(&instr->hold_link_access, 0); -#endif + instr->from_count = 0; + instr->to_count = 0; } @@ -188,8 +209,6 @@ static void g_arch_instruction_dispose(GArchInstruction *instr) static void g_arch_instruction_finalize(GArchInstruction *instr) { - g_rw_lock_clear(&instr->link_access); - G_OBJECT_CLASS(g_arch_instruction_parent_class)->finalize(G_OBJECT(instr)); } @@ -548,6 +567,7 @@ void g_arch_instruction_get_rw_registers(const GArchInstruction *instr, GArchReg /****************************************************************************** * * * Paramètres : instr = instruction à mettre à jour. * +* src = sélection de l'extrémité à traiter. * * write = précise le type d'accès prévu (lecture/écriture). * * lock = indique le sens du verrouillage à mener. * * * @@ -559,28 +579,80 @@ void g_arch_instruction_get_rw_registers(const GArchInstruction *instr, GArchReg * * ******************************************************************************/ -void g_arch_instruction_lock_unlock_links(GArchInstruction *instr, bool write, bool lock) +void g_arch_instruction_lock_unlock_links(GArchInstruction *instr, bool src, bool write, bool lock) { -#ifndef NDEBUG - if (!lock) - g_atomic_int_dec_and_test(&instr->hold_link_access); -#endif + volatile gint *address; /* Choix de l'entier à traiter */ - if (write) - { - if (lock) g_rw_lock_writer_lock(&instr->link_access); - else g_rw_lock_writer_unlock(&instr->link_access); - } - else - { - if (lock) g_rw_lock_reader_lock(&instr->link_access); - else g_rw_lock_reader_unlock(&instr->link_access); - } + address = (src ? &instr->from_count : &instr->to_count); -#ifndef NDEBUG if (lock) - g_atomic_int_inc(&instr->hold_link_access); -#endif + g_bit_lock(address, INSTR_LINK_LOCK_BIT); + else + g_bit_unlock(address, INSTR_LINK_LOCK_BIT); + +} + + +/****************************************************************************** +* * +* Paramètres : instr = instruction dont les informations sont à consulter. * +* src = sélection de l'extrémité à traiter. * +* * +* Description : Dénombre les liens présents à une extrémité donnée. * +* * +* Retour : Quantité positive. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t g_arch_instruction_get_link_counter(GArchInstruction *instr, bool src) +{ + size_t result; /* Nombre de liens à renvoyer */ + volatile gint *address; /* Choix de l'entier à traiter */ + + address = (src ? &instr->from_count : &instr->to_count); + + assert(!g_bit_trylock(address, INSTR_LINK_LOCK_BIT)); + + result = g_atomic_int_get(address) & ~(1 << INSTR_LINK_LOCK_BIT); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : instr = instruction dont les informations sont à consulter. * +* src = sélection de l'extrémité à traiter. * +* * +* Description : Incrémente le nombre de liens définis à une extrémité donnée.* +* * +* Retour : Nouvelle quantité mise à jour. * +* * +* Remarques : - * +* * +******************************************************************************/ + +static size_t g_arch_instruction_inc_link_counter(GArchInstruction *instr, bool src) +{ + size_t result; /* Nombre de liens à renvoyer */ + volatile gint *address; /* Choix de l'entier à traiter */ + + address = (src ? &instr->from_count : &instr->to_count); + + assert(!g_bit_trylock(address, INSTR_LINK_LOCK_BIT)); + + result = g_atomic_int_get(address) & ~(1 << INSTR_LINK_LOCK_BIT); + + result++; + + assert((result & (1 << INSTR_LINK_LOCK_BIT)) == 0); + + g_atomic_int_set(address, (1 << INSTR_LINK_LOCK_BIT) | result); + + return result; } @@ -609,7 +681,7 @@ void g_arch_instruction_link_with(GArchInstruction *instr, GArchInstruction *des g_arch_instruction_wlock_src(dest); - count = ++dest->from_count; + count = g_arch_instruction_inc_source_counter(dest); dest->from = (instr_link_t *)realloc(dest->from, count * sizeof(instr_link_t)); @@ -624,7 +696,7 @@ void g_arch_instruction_link_with(GArchInstruction *instr, GArchInstruction *des g_arch_instruction_wlock_dest(instr); - count = ++instr->to_count; + count = g_arch_instruction_inc_destination_counter(instr); instr->to = (instr_link_t *)realloc(instr->to, count * sizeof(instr_link_t)); @@ -663,13 +735,13 @@ bool g_arch_instruction_change_link(GArchInstruction *instr, GArchInstruction *d result = false; - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + assert(!g_bit_trylock(&instr->to_count, INSTR_LINK_LOCK_BIT)); g_arch_instruction_wlock_src(dest); /* Côté destination */ - count = dest->from_count; + count = g_arch_instruction_get_source_counter(dest); for (i = 0; i < count; i++) if (dest->from[i].linked == instr && dest->from[i].type == old) @@ -682,7 +754,7 @@ bool g_arch_instruction_change_link(GArchInstruction *instr, GArchInstruction *d /* Côté point de départ */ - count = instr->to_count; + count = g_arch_instruction_get_destination_counter(instr); for (i = 0; i < count; i++) if (instr->to[i].linked == dest && instr->to[i].type == old) @@ -722,11 +794,15 @@ bool g_arch_instruction_change_link(GArchInstruction *instr, GArchInstruction *d * * ******************************************************************************/ -bool g_arch_instruction_has_sources(const GArchInstruction *instr) +bool g_arch_instruction_has_sources(GArchInstruction *instr) { - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + size_t count; /* Nombre de liens présents */ + + assert(!g_bit_trylock(&instr->from_count, INSTR_LINK_LOCK_BIT)); - return (instr->from_count > 0); + count = g_arch_instruction_get_source_counter(instr); + + return (count > 0); } @@ -744,14 +820,14 @@ bool g_arch_instruction_has_sources(const GArchInstruction *instr) * * ******************************************************************************/ -size_t g_arch_instruction_get_sources(const GArchInstruction *instr, instr_link_t **sources) +size_t g_arch_instruction_get_sources(GArchInstruction *instr, instr_link_t **sources) { - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + assert(!g_bit_trylock(&instr->from_count, INSTR_LINK_LOCK_BIT)); if (sources != NULL) *sources = instr->from; - return instr->from_count; + return g_arch_instruction_get_source_counter(instr); } @@ -768,11 +844,15 @@ size_t g_arch_instruction_get_sources(const GArchInstruction *instr, instr_link_ * * ******************************************************************************/ -bool g_arch_instruction_has_destinations(const GArchInstruction *instr) +bool g_arch_instruction_has_destinations(GArchInstruction *instr) { - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + size_t count; /* Nombre de liens présents */ + + assert(!g_bit_trylock(&instr->to_count, INSTR_LINK_LOCK_BIT)); - return (instr->to_count > 0); + count = g_arch_instruction_get_destination_counter(instr); + + return (count > 0); } @@ -790,14 +870,14 @@ bool g_arch_instruction_has_destinations(const GArchInstruction *instr) * * ******************************************************************************/ -size_t g_arch_instruction_get_destinations(const GArchInstruction *instr, instr_link_t **dests) +size_t g_arch_instruction_get_destinations(GArchInstruction *instr, instr_link_t **dests) { - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + assert(!g_bit_trylock(&instr->to_count, INSTR_LINK_LOCK_BIT)); if (dests != NULL) *dests = instr->to; - return instr->to_count; + return g_arch_instruction_get_destination_counter(instr); } @@ -815,16 +895,19 @@ size_t g_arch_instruction_get_destinations(const GArchInstruction *instr, instr_ * * ******************************************************************************/ -GArchInstruction *g_arch_instruction_get_given_destination(const GArchInstruction *instr, InstructionLinkType type) +GArchInstruction *g_arch_instruction_get_given_destination(GArchInstruction *instr, InstructionLinkType type) { GArchInstruction *result; /* Résultat à remonter */ + size_t count; /* Nombre de liens à parcourir */ size_t i; /* Boucle de parcours */ result = NULL; - assert(g_atomic_int_get(&instr->hold_link_access) > 0); + assert(!g_bit_trylock(&instr->to_count, INSTR_LINK_LOCK_BIT)); + + count = g_arch_instruction_get_destination_counter(instr); - for (i = 0; i < instr->to_count && result == NULL; i++) + for (i = 0; i < count && result == NULL; i++) if (instr->to[i].type == type) result = instr->to[i].linked; diff --git a/src/arch/instruction.h b/src/arch/instruction.h index ffebaf3..7323a2e 100644 --- a/src/arch/instruction.h +++ b/src/arch/instruction.h @@ -169,7 +169,7 @@ typedef struct _instr_link_t /* Met à disposition un encadrement des accès aux liens. */ -void g_arch_instruction_lock_unlock_links(GArchInstruction *, bool, bool); +void g_arch_instruction_lock_unlock_links(GArchInstruction *, bool, bool, bool); /* Etablit un lien entre deux instructions. */ void g_arch_instruction_link_with(GArchInstruction *, GArchInstruction *, InstructionLinkType); @@ -177,32 +177,32 @@ void g_arch_instruction_link_with(GArchInstruction *, GArchInstruction *, Instru /* Change la nature d'un lien entre deux instructions. */ bool g_arch_instruction_change_link(GArchInstruction *, GArchInstruction *, InstructionLinkType, InstructionLinkType); -#define g_arch_instruction_wlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, true) -#define g_arch_instruction_wunlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, false) +#define g_arch_instruction_wlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, true, true) +#define g_arch_instruction_wunlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, true, false) -#define g_arch_instruction_rlock_src(ins) g_arch_instruction_lock_unlock_links(ins, false, true) -#define g_arch_instruction_runlock_src(ins) g_arch_instruction_lock_unlock_links(ins, false, false) +#define g_arch_instruction_rlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, false, true) +#define g_arch_instruction_runlock_src(ins) g_arch_instruction_lock_unlock_links(ins, true, false, false) /* Indique si l'instruction a une ou plusieurs origines. */ -bool g_arch_instruction_has_sources(const GArchInstruction *); +bool g_arch_instruction_has_sources(GArchInstruction *); /* Fournit les origines d'une instruction donnée. */ -size_t g_arch_instruction_get_sources(const GArchInstruction *, instr_link_t **); +size_t g_arch_instruction_get_sources(GArchInstruction *, instr_link_t **); -#define g_arch_instruction_wlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, true, true) -#define g_arch_instruction_wunlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, true, false) +#define g_arch_instruction_wlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, true, true) +#define g_arch_instruction_wunlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, true, false) -#define g_arch_instruction_rlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, true) -#define g_arch_instruction_runlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, false) +#define g_arch_instruction_rlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, false, true) +#define g_arch_instruction_runlock_dest(ins) g_arch_instruction_lock_unlock_links(ins, false, false, false) /* Indique si l'instruction a une suite autre que la suivante. */ -bool g_arch_instruction_has_destinations(const GArchInstruction *); +bool g_arch_instruction_has_destinations(GArchInstruction *); /* Fournit les destinations d'une instruction donnée. */ -size_t g_arch_instruction_get_destinations(const GArchInstruction *, instr_link_t **); +size_t g_arch_instruction_get_destinations(GArchInstruction *, instr_link_t **); /* Fournit la destination d'une instruction et d'un type donné. */ -GArchInstruction *g_arch_instruction_get_given_destination(const GArchInstruction *, InstructionLinkType); +GArchInstruction *g_arch_instruction_get_given_destination(GArchInstruction *, InstructionLinkType); /* Indique la position dans les instructions identiques. */ size_t g_arch_instruction_compute_group_index(GArchInstruction **, GArchInstruction **, size_t); -- cgit v0.11.2-87-g4458