/* Chrysalide - Outil d'analyse de fichiers binaires
* flow.c - encadrement des instructions par blocs d'exécution
*
* Copyright (C) 2012-2013 Cyrille Bagard
*
* This file is part of Chrysalide.
*
* OpenIDA is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 3 of the License, or
* (at your option) any later version.
*
* OpenIDA is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with Foobar. If not, see <http://www.gnu.org/licenses/>.
*/
#include "flow.h"
#include <malloc.h>
#include <sys/param.h>
#include "../block-int.h"
/* Description d'un bloc d'exécution d'instructions (instance) */
struct _GFlowBlock
{
GInstrBlock parent; /* A laisser en premier */
unsigned int rank; /* Rang dans l'exécution */
unsigned int next_rank; /* Rang suivant de l'exécution */
GArchProcessor *proc; /* Liste complète d'instruct° */
GArchInstruction *first; /* Première instruction */
GArchInstruction *last; /* Dernière instruction */
GRAccessList *regs; /* Accès aux registres */
GRAccessList *awaited; /* Registres définis pour après*/
};
/* Description d'un bloc d'exécution d'instructions (classe) */
struct _GFlowBlockClass
{
GInstrBlockClass parent; /* A laisser en premier */
};
/* Initialise la classe des blocs d'instructions. */
static void g_flow_block_class_init(GFlowBlockClass *);
/* Initialise un bloc d'instructions. */
static void g_flow_block_init(GFlowBlock *);
/* Supprime toutes les références externes. */
static void g_flow_block_dispose(GFlowBlock *);
/* Procède à la libération totale de la mémoire. */
static void g_flow_block_finalize(GFlowBlock *);
/* Recherche le bloc contenant une adresse donnée. */
static GInstrBlock *g_flow_block_find_by_addr(const GFlowBlock *, const vmpa2t *, bool);
/* Parcourt le bloc d'instructions dans un ordre donné. */
static bool g_flow_block_visit(GFlowBlock *, instr_block_visitor_cb, void *);
/* Etablit la liste de tous les blocs présents. */
static void g_flow_block_list_all_blocks(const GFlowBlock *, GInstrBlock ***, size_t *);
/* Etablit la liste de tous les blocs terminaux. */
static void g_flow_block_list_leafs_blocks(const GFlowBlock *, GInstrBlock ***, size_t *);
/* Prend note de l'usage d'un registre, au besoin. */
static void g_flow_block_memorize_access(GFlowBlock *, GArchRegister *, RegAccessType, vmpa_t);
/* Note les différents accès aux registres. */
static void g_flow_block_compute_regs_access(GFlowBlock *);
/* Fournit les différents accès aux registres. */
//static const reg_access *g_flow_block_list_regs_accesses(const GFlowBlock *, size_t *);
/* Indique le type défini pour un bloc d'exécution d'instructions. */
G_DEFINE_TYPE(GFlowBlock, g_flow_block, G_TYPE_INSTR_BLOCK);
/******************************************************************************
* *
* Paramètres : class = classe à initialiser. *
* *
* Description : Initialise la classe des blocs d'instructions. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_class_init(GFlowBlockClass *class)
{
GObjectClass *object; /* Autre version de la classe */
GInstrBlockClass *block_class; /* Version parente du la classe*/
object = G_OBJECT_CLASS(class);
block_class = G_INSTR_BLOCK_CLASS(class);
object->dispose = (GObjectFinalizeFunc/* ! */)g_flow_block_dispose;
object->finalize = (GObjectFinalizeFunc)g_flow_block_finalize;
block_class->find_by_addr = (find_by_addr_fc)g_flow_block_find_by_addr;
block_class->visit_blocks = (visit_all_blocks_fc)g_flow_block_visit;
block_class->list_blocks = (list_all_blocks_fc)g_flow_block_list_all_blocks;
block_class->list_leafs = (list_leafs_blocks_fc)g_flow_block_list_leafs_blocks;
//block_class->list_regs = (list_regs_accesses_fc)g_flow_block_list_regs_accesses;
}
/******************************************************************************
* *
* Paramètres : block = instance à initialiser. *
* *
* Description : Initialise un bloc d'instructions. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_init(GFlowBlock *block)
{
g_flow_block_set_rank(block, 0);
block->regs = g_raccess_list_new();
block->awaited = g_raccess_list_new();
}
/******************************************************************************
* *
* Paramètres : block = instance d'objet GLib à traiter. *
* *
* Description : Supprime toutes les références externes. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_dispose(GFlowBlock *block)
{
g_object_unref(G_OBJECT(block->proc));
g_object_unref(G_OBJECT(block->first));
g_object_unref(G_OBJECT(block->last));
g_object_unref(G_OBJECT(block->regs));
g_object_unref(G_OBJECT(block->awaited));
G_OBJECT_CLASS(g_flow_block_parent_class)->dispose(G_OBJECT(block));
}
/******************************************************************************
* *
* Paramètres : block = instance d'objet GLib à traiter. *
* *
* Description : Procède à la libération totale de la mémoire. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_finalize(GFlowBlock *block)
{
G_OBJECT_CLASS(g_flow_block_parent_class)->finalize(G_OBJECT(block));
}
/******************************************************************************
* *
* Paramètres : proc = liste de toutes les instructions. *
* first = première instruction du bloc. *
* last = dernière instruction du bloc. *
* *
* Description : Crée un bloc d'exécution d'instructions. *
* *
* Retour : Adresse de la structure mise en place. *
* *
* Remarques : - *
* *
******************************************************************************/
GInstrBlock *g_flow_block_new(GArchProcessor *proc, GArchInstruction *first, GArchInstruction *last)
{
GFlowBlock *result; /* Structure à retourner */
result = g_object_new(G_TYPE_FLOW_BLOCK, NULL);
result->proc = proc;
result->first = first;
result->last = last;
g_object_ref(G_OBJECT(result->proc));
g_object_ref(G_OBJECT(result->first));
g_object_ref(G_OBJECT(result->last));
//g_flow_block_compute_regs_access(result);
return G_INSTR_BLOCK(result);
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instruction à consulter. *
* *
* Description : Fournit le rang du bloc dans le flot d'exécution. *
* *
* Retour : Indice supérieur ou égal à zéro. *
* *
* Remarques : - *
* *
******************************************************************************/
unsigned int g_flow_block_get_rank(const GFlowBlock *block)
{
return block->rank;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instruction à consulter. *
* rank = Indice supérieur à zéro à prendre en compte. *
* *
* Description : Définit le rang du bloc dans le flot d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_block_set_rank(GFlowBlock *block, unsigned int rank)
{
block->rank = rank;
}
/******************************************************************************
* *
* Paramètres : block = bloc de départ des recherches. *
* addr = ensemble de blocs à parcourir. *
* final = indique si la cible ou le conteneur est renvoyée. *
* *
* Description : Recherche le bloc contenant une adresse donnée. *
* *
* Retour : bloc basique trouvé ou NULL en cas d'échec. *
* *
* Remarques : - *
* *
******************************************************************************/
static GInstrBlock *g_flow_block_find_by_addr(const GFlowBlock *block, const vmpa2t *addr, bool final)
{
GInstrBlock *result; /* Resultat à retourner */
vmpa2t start; /* Adresse de début du bloc */
vmpa2t end; /* Adresse de fin du bloc */
mrange_t range; /* Couverture globale */
g_flow_block_get_boundary_addresses(block, &start, &end);
init_mrange(&range, &start, compute_vmpa_diff(&start, &end));
if (mrange_contains_addr(&range, addr))
result = G_INSTR_BLOCK(block);
else
result = NULL;
return result;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions concerné par la visite. *
* callback = ensemble de blocs à parcourir. *
* data = donnée utilisateur à associer au parcours. *
* *
* Description : Parcourt le bloc d'instructions dans un ordre donné. *
* *
* Retour : true si le parcours a été jusqu'à son terme, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
static bool g_flow_block_visit(GFlowBlock *block, instr_block_visitor_cb callback, void *data)
{
return callback(G_INSTR_BLOCK(block), BVO_PENDING, data);
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* list = ensemble de blocs à compléter. [OUT] *
* count = nombre de blocs au total. [OUT] *
* *
* Description : Etablit la liste de tous les blocs présents. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_list_all_blocks(const GFlowBlock *block, GInstrBlock ***list, size_t *count)
{
(*list) = (GInstrBlock **)realloc(*list, ++(*count) * sizeof(GInstrBlock *));
(*list)[*count - 1] = G_INSTR_BLOCK(block);
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* list = ensemble de blocs à compléter. [OUT] *
* count = nombre de blocs au total. [OUT] *
* *
* Description : Etablit la liste de tous les blocs terminaux. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_list_leafs_blocks(const GFlowBlock *block, GInstrBlock ***list, size_t *count)
{
(*list) = (GInstrBlock **)realloc(*list, ++(*count) * sizeof(GInstrBlock *));
(*list)[*count - 1] = G_INSTR_BLOCK(block);
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à mettre à jour. *
* reg = registre visé par l'opération. *
* type = type d'accès à l'opérande. *
* addr = adresse de l'instruction associée. *
* *
* Description : Prend note de l'usage d'un registre, au besoin. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_memorize_access(GFlowBlock *block, GArchRegister *reg, RegAccessType type, vmpa_t addr)
{
reg_access *found; /* Accès à mettre à jour */
reg_access access; /* Accès à mettre en place */
found = g_raccess_list_find(block->regs, reg);
/* Simpple mise à jour ? */
if (found != NULL)
{
if (type == RAT_WRITE)
found->last_write = addr;
}
/* Ou ajout pur et simple ? */
else
{
access.reg = reg;
access.first_access = type;
access.last_write = (type == RAT_WRITE ? addr : VMPA_MAX);
g_raccess_list_add(block->regs, &access);
}
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à parcourir. *
* *
* Description : Note les différents accès aux registres. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
static void g_flow_block_compute_regs_access(GFlowBlock *block)
{
GArchInstruction *iter; /* Boucle de parcours #1 */
vmpa_t max; /* Adresse de fin */
vmpa_t addr; /* Adresse d'instruction */
GArchRegister **rregs; /* Liste des registres lus */
size_t rcount; /* Nombre de registres lus */
GArchRegister **wregs; /* Liste des registres écrits */
size_t wcount; /* Nombre de registres écrits */
size_t i; /* Boucle de parcours #2 */
g_arch_instruction_get_location(block->last, NULL, NULL, &max);
max++;
for (iter = block->first;
iter != NULL;
iter = NULL/* FIXME g_arch_instruction_get_next_iter(block->instrs, iter, max)*/)
{
g_arch_instruction_get_location(iter, NULL, NULL, &addr);
g_arch_instruction_get_rw_registers(iter, &rregs, &rcount, &wregs, &wcount);
for (i = 0; i < rcount; i++)
{
g_flow_block_memorize_access(block, rregs[i], RAT_READ, addr);
g_object_unref(G_OBJECT(rregs[i]));
}
for (i = 0; i < wcount; i++)
{
g_flow_block_memorize_access(block, wregs[i], RAT_WRITE, addr);
g_object_unref(G_OBJECT(wregs[i]));
}
if (rregs != NULL) free(rregs);
if (wregs != NULL) free(wregs);
}
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* *
* Description : Donne le processeur d'appartenance des instructions du bloc. *
* *
* Retour : Liste de l'ensemble des instructions. *
* *
* Remarques : - *
* *
******************************************************************************/
GArchProcessor *g_flow_block_get_processor(const GFlowBlock *block)
{
return block->proc;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* first = instruction de départ du bloc. [OUT] *
* last = dernière instruction du bloc. [OUT] *
* *
* Description : Fournit les instructions limites d'un bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_block_get_boundary(const GFlowBlock *block, GArchInstruction **first, GArchInstruction **last)
{
if (first != NULL)
*first = block->first;
if (last != NULL)
*last = block->last;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* start = adresse de départ du bloc. [OUT] *
* end = dernière adresse du bloc. [OUT] *
* *
* Description : Fournit les adresses limites d'un bloc d'exécution. *
* *
* Retour : - *
* *
* Remarques : - *
* *
******************************************************************************/
void g_flow_block_get_boundary_addresses(const GFlowBlock *block, vmpa2t *start, vmpa2t *end)
{
const mrange_t *range; /* Couverture d'instruction */
if (start != NULL)
{
range = g_arch_instruction_get_range(block->first);
copy_vmpa(start, get_mrange_addr(range));
}
if (end != NULL)
{
range = g_arch_instruction_get_range(block->last);
copy_vmpa(end, get_mrange_addr(range));
}
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions démarrant la visite. *
* list = ensemble des blocs basiques à parcourir. *
* target = bloc de fin de parcours. *
* *
* Description : Détermine si un bloc peut conduire à un autre. *
* *
* Retour : true si un lien existe entre les deux blocs fournis. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_flow_block_is_looping_to(GFlowBlock *block, const GInstrBlock *list, GFlowBlock *target)
{
bool result; /* Bilan à retourner */
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 */
vmpa_t addr; /* Adresse de la destination */
GInstrBlock *next; /* Bloc suivant à visiter */
result = (block == target);
dcount = g_arch_instruction_get_destinations(block->last, &dests, &types, NULL);
for (i = 0; i < dcount && !result; 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:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
next = g_instr_block_find_by_addr(list, addr, true);
result = g_flow_block_is_looping_to(G_FLOW_BLOCK(next), list, target);
break;
case ILT_LOOP:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
next = g_instr_block_find_by_addr(list, addr, true);
result = (G_FLOW_BLOCK(next) == target);
default:
break;
}
return result;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions démarrant la visite. *
* list = ensemble des blocs basiques à parcourir. *
* mask = points de passage à marquer. *
* callback = ensemble de blocs à parcourir. *
* data = donnée utilisateur à associer au parcours. *
* *
* Description : Suit le flot d'excution bloc par bloc. *
* *
* Retour : true si le parcours a été jusqu'à son terme, false sinon. *
* *
* Remarques : - *
* *
******************************************************************************/
bool g_flow_block_follow(GFlowBlock *block, const GInstrBlock *list, BlockFollowPosition mask, flow_block_follow_cb callback, void *data)
{
bool result; /* Bilan à retourner */
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 */
vmpa_t addr; /* Adresse de la destination */
GInstrBlock *next; /* Bloc suivant à visiter */
result = true;
if (mask & BFP_ENTER)
result = callback(block, BFP_ENTER, data);
dcount = g_arch_instruction_get_destinations(block->last, &dests, &types, NULL);
for (i = 0; i < dcount && result; 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:
g_arch_instruction_get_location(dests[i], NULL, NULL, &addr);
next = g_instr_block_find_by_addr(list, addr, true);
if (next)
{
result = callback(block, BFP_FOLLOW, data);
result &= g_flow_block_follow(G_FLOW_BLOCK(next), list, mask, callback, data);
result &= callback(block, BFP_BACK, data);
}
break;
default:
break;
}
if (mask & BFP_EXIT)
result &= callback(block, BFP_EXIT, data);
return result;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* *
* Description : Fournit les différents accès aux registres. *
* *
* Retour : Liste des accès aux registres. *
* *
* Remarques : - *
* *
******************************************************************************/
const GRAccessList *g_flow_block_list_regs_accesses(const GFlowBlock *block)
{
return block->regs;
}
/******************************************************************************
* *
* Paramètres : block = bloc d'instructions à consulter. *
* *
* Description : Fournit les registres écrits par le bloc et utilisées après. *
* *
* Retour : Liste des accès aux registres. *
* *
* Remarques : - *
* *
******************************************************************************/
GRAccessList *g_flow_block_list_awaited_regs(const GFlowBlock *block)
{
return block->awaited;
}