From a156dc15cccb54d662b0085c8e4f27767dd5542f Mon Sep 17 00:00:00 2001 From: Cyrille Bagard Date: Sat, 14 Jan 2017 00:48:47 +0100 Subject: Fortified the tree of binary portions. --- ChangeLog | 15 ++++++++ src/arch/vmpa.c | 98 +++++++++++++++++++++++++++++++++++++++++++++-- src/arch/vmpa.h | 6 +++ src/common/sort.c | 40 +++++++++++++++---- src/common/sort.h | 3 ++ src/glibext/gbinportion.c | 61 +++++++++++++++++++++-------- src/glibext/gbinportion.h | 3 ++ 7 files changed, 200 insertions(+), 26 deletions(-) diff --git a/ChangeLog b/ChangeLog index 62b87c6..7599fa5 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,18 @@ +17-01-14 Cyrille Bagard + + * src/arch/vmpa.c: + * src/arch/vmpa.h: + Define extra comparisons for memory ranges. + + * src/common/sort.c: + * src/common/sort.h: + Restore an assertion. Create a function to delete an indexed item from + a sorted array. + + * src/glibext/gbinportion.c: + * src/glibext/gbinportion.h: + Fortify the tree of binary portions. + 17-01-10 Cyrille Bagard * .gitignore: diff --git a/src/arch/vmpa.c b/src/arch/vmpa.c index 4f9b87f..c32c836 100644 --- a/src/arch/vmpa.c +++ b/src/arch/vmpa.c @@ -46,6 +46,14 @@ static char *_phys_t_to_string(phys_t, MemoryDataSize, char [VMPA_MAX_LEN], size +/* ------------------------ DEFINITION D'UNE ZONE EN MEMOIRE ------------------------ */ + + +/* Compare une couverture mémoire avec une localisation simple. */ +static int _cmp_mrange_with_vmpa(const mrange_t *, const vmpa2t *, bool); + + + /* ---------------------------------------------------------------------------------- */ /* DEFINITION D'UNE POSITION EN MEMOIRE */ /* ---------------------------------------------------------------------------------- */ @@ -874,8 +882,9 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b) /****************************************************************************** * * -* Paramètres : a = première définition à analyser. * -* b = seconde définition à analyser. * +* Paramètres : a = première définition à analyser. * +* b = seconde définition à analyser. * +* inc = indique si l'adresse peut être une fin de zone. * * * * Description : Compare une couverture mémoire avec une localisation simple. * * * @@ -885,7 +894,7 @@ int cmp_mrange(const mrange_t *a, const mrange_t *b) * * ******************************************************************************/ -int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b) +static int _cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b, bool inclusive) { int result; /* Bilan à retourner */ phys_t diff; /* Espace entre deux adresses */ @@ -914,6 +923,9 @@ int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *b) else if (diff < a->length) result = 0; + else if (diff == a->length && inclusive) + result = 0; + else result = 1; @@ -926,6 +938,86 @@ int cmp_mrange_with_vmpa(const mrange_t *a, const vmpa2t *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 */ + + result = _cmp_mrange_with_vmpa(a, b, false); + + return result; + +} + + +/****************************************************************************** +* * +* 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_inclusive(const mrange_t *a, const vmpa2t *b) +{ + int result; /* Bilan à retourner */ + + result = _cmp_mrange_with_vmpa(a, b, true); + + return result; + +} + + +/****************************************************************************** +* * +* Paramètres : range = zone mémoire à consulter. * +* sub = éventuelle sous-région à valider. * +* * +* Description : Indique si une zone en contient une autre ou non. * +* * +* Retour : Bilan de la comparaison : -1, 0 ou 1 (-1 par défaut). * +* * +* Remarques : - * +* * +******************************************************************************/ + +int mrange_includes_mrange(const mrange_t *range, const mrange_t *sub) +{ + int result; /* Bilan à retourner */ + vmpa2t end; /* Seconde extrémité */ + + result = cmp_mrange_with_vmpa(range, get_mrange_addr(sub)); + + if (result == 0) + { + compute_mrange_end_addr(sub, &end); + + result = cmp_mrange_with_vmpa_inclusive(range, &end); + + } + + return result; + +} + +/****************************************************************************** +* * * Paramètres : range = zone mémoire à consulter. * * sub = éventuelle sous-région à valider. * * * diff --git a/src/arch/vmpa.h b/src/arch/vmpa.h index 996a7fb..6305f79 100644 --- a/src/arch/vmpa.h +++ b/src/arch/vmpa.h @@ -203,6 +203,12 @@ static inline int cmp_mrange_with_vmpa_swapped(const vmpa2t *k, const mrange_t * return cmp_mrange_with_vmpa(r, k); } +/* Compare une couverture mémoire avec une localisation simple. */ +int cmp_mrange_with_vmpa_inclusive(const mrange_t *, const vmpa2t *); + +/* Indique si une zone en contient une autre ou non. */ +int mrange_includes_mrange(const mrange_t *, const mrange_t *); + /* Indique si une zone en contient une autre ou non. */ bool mrange_contains_mrange(const mrange_t *, const mrange_t *); diff --git a/src/common/sort.c b/src/common/sort.c index 750034b..7da9a29 100644 --- a/src/common/sort.c +++ b/src/common/sort.c @@ -194,7 +194,7 @@ void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void #ifndef NDEBUG found = bsearch_index(new, base, *nmemb, size, compar, &index); - //assert(!found); FIXME (portions) + assert(!found); #else bsearch_index(new, base, *nmemb, size, compar, &index); #endif @@ -208,6 +208,37 @@ void *qinsert(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void /****************************************************************************** * * +* Paramètres : base = adresse du tableau à parcourir. * +* nmem = nombre d'éléments présents au total. [OUT] * +* size = taille de chaque élément du tableau. * +* inde = indice du point de suppression. * +* * +* Description : Supprime un élément dans un tableau trié. * +* * +* Retour : Nouvel emplacement du tableau rétréci. * +* * +* Remarques : - * +* * +******************************************************************************/ + +void *_qdelete(void *base, size_t *nmemb, size_t size, size_t index) +{ + void *result; /* Tableau trié à retourner */ + + if ((index + 1) < *nmemb) + memmove((char *)base + index * size, (char *)base + (index + 1) * size, (*nmemb - index - 1) * size); + + (*nmemb)--; + + result = realloc(base, *nmemb * size); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : base = adresse du tableau à parcourir. * * nmemb = nombre d'éléments présents au total. [OUT] * * size = taille de chaque élément du tableau. * @@ -237,12 +268,7 @@ void *qdelete(void *base, size_t *nmemb, size_t size, __compar_fn_t compar, void bsearch_index(target, base, *nmemb, size, compar, &index); #endif - if ((index + 1) < *nmemb) - memmove((char *)base + index * size, (char *)base + (index + 1) * size, (*nmemb - index - 1) * size); - - (*nmemb)--; - - result = realloc(base, *nmemb * size); + result = _qdelete(base, nmemb, size, index); return result; diff --git a/src/common/sort.h b/src/common/sort.h index 9fcc240..fb47a5e 100644 --- a/src/common/sort.h +++ b/src/common/sort.h @@ -43,6 +43,9 @@ void *_qinsert(void *, size_t *, size_t, void *, size_t); void *qinsert(void *, size_t *, size_t, __compar_fn_t, void *); /* Supprime un élément dans un tableau trié. */ +void *_qdelete(void *, size_t *, size_t, size_t); + +/* Supprime un élément dans un tableau trié. */ void *qdelete(void *, size_t *, size_t, __compar_fn_t, void *); diff --git a/src/glibext/gbinportion.c b/src/glibext/gbinportion.c index 4849caa..e5dedd6 100644 --- a/src/glibext/gbinportion.c +++ b/src/glibext/gbinportion.c @@ -310,6 +310,30 @@ int g_binary_portion_compare(const GBinPortion **a, const GBinPortion **b) /****************************************************************************** * * +* Paramètres : a = premières informations à consulter. * +* b = secondes informations à consulter. * +* * +* Description : Détermine si une portion est comprise dans une autre. * +* * +* Retour : Bilan : -1 (a < b), 0 (b € a) ou 1 (a > b). * +* * +* Remarques : - * +* * +******************************************************************************/ + +int g_binary_portion_is_included(const GBinPortion **a, const GBinPortion **b) +{ + int result; /* Bilan à retourner */ + + result = mrange_includes_mrange(&(*b)->range, &(*a)->range); + + return result; + +} + + +/****************************************************************************** +* * * Paramètres : portion = description de partie à mettre à jour. * * desc = nom à donner à la partie. * * * @@ -654,12 +678,11 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub) { bool found; /* Zone d'accueil trouvée ? */ size_t best; /* Meilleur point d'insertion */ - const mrange_t *prange; /* Emplacement de portion #1 */ - const mrange_t *srange; /* Emplacement de portion #2 */ - GBinPortion tmp; /* Sauvegarde temporaire */ + size_t i; /* Boucle de parcours */ + GBinPortion *tmp; /* Sauvegarde temporaire */ - found = bsearch_index(sub, portion->subs, portion->count, sizeof(GBinPortion *), - (__compar_fn_t)g_binary_portion_compare, &best); + found = bsearch_index(&sub, portion->subs, portion->count, sizeof(GBinPortion *), + (__compar_fn_t)g_binary_portion_is_included, &best); if (!found) portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *), @@ -678,24 +701,30 @@ void g_binary_portion_include(GBinPortion *portion, GBinPortion *sub) * de zones mémoire. */ - prange = g_binary_portion_get_range(portion->subs[best]); - srange = g_binary_portion_get_range(sub); + if (mrange_includes_mrange(&sub->range, &portion->subs[best]->range) == 0) + { + tmp = portion->subs[best]; - if (mrange_contains_mrange(prange, srange)) - g_binary_portion_include(portion->subs[best], sub); + for (i = portion->count; i > 0; i--) + { + tmp = portion->subs[i - 1]; - else - { - assert(mrange_contains_mrange(srange, prange)); + if (mrange_includes_mrange(&sub->range, &tmp->range) == 0) + { + portion->subs = _qdelete(portion->subs, &portion->count, sizeof(GBinPortion *), i - 1); + g_binary_portion_include(sub, tmp); + } - memcpy(&tmp, portion->subs[best], sizeof(GBinPortion)); - memcpy(portion->subs[best], sub, sizeof(GBinPortion)); - memcpy(sub, &tmp, sizeof(GBinPortion)); + } - g_binary_portion_include(portion->subs[best], sub); + portion->subs = qinsert(portion->subs, &portion->count, sizeof(GBinPortion *), + (__compar_fn_t)g_binary_portion_compare, &sub); } + else + g_binary_portion_include(portion->subs[best], sub); + } } diff --git a/src/glibext/gbinportion.h b/src/glibext/gbinportion.h index f05713e..a1ec105 100644 --- a/src/glibext/gbinportion.h +++ b/src/glibext/gbinportion.h @@ -84,6 +84,9 @@ GBinPortion *g_binary_portion_new(const char *, const vmpa2t *, phys_t); /* Etablit la comparaison ascendante entre deux portions. */ int g_binary_portion_compare(const GBinPortion **, const GBinPortion **); +/* Détermine si une portion est comprise dans une autre. */ +int g_binary_portion_is_included(const GBinPortion **, const GBinPortion **); + /* Attribue une description humaine à une partie de code. */ void g_binary_portion_set_desc(GBinPortion *, const char *); -- cgit v0.11.2-87-g4458