Improved loading speed with binary search of sorted arrays.

git-svn-id: svn://svn.gna.org/svn/chrysalide/trunk@538 abbe820e-26c8-41b2-8c08-b7b2b41f8b0a

5 files changed, 100 insertions, 41 deletions

diff --git a/src/format/elf/symbols.c b/src/format/elf/symbols.c
index 04ba3de..655eda1 100644
--- a/src/format/elf/symbols.c
+++ b/src/format/elf/symbols.c
@@ -137,6 +137,8 @@ bool load_elf_symbols(GElfFormat *format)
 
     result &= load_all_elf_basic_entry_points(format);
 
+    g_binary_format_sort_symbols(G_BIN_FORMAT(format));
+
     return result;
 
 }
@@ -201,7 +203,7 @@ static void register_elf_entry_point(GElfFormat *format, virt_t vaddr, phys_t le
 
         symbol = g_binary_symbol_new(STP_ENTRY_POINT, "XXX", ~0);
         g_binary_symbol_attach_routine(symbol, routine);
-        g_binary_format_add_symbol(base, symbol);
+        _g_binary_format_add_symbol(base, symbol, false);
 
     }
 
@@ -632,7 +634,7 @@ static bool load_elf_internal_symbols(GElfFormat *format)
             }
 
             if (symbol != NULL)
-                g_binary_format_add_symbol(G_BIN_FORMAT(format), symbol);
+                _g_binary_format_add_symbol(G_BIN_FORMAT(format), symbol, false);
 
         }
 
diff --git a/src/format/format-int.h b/src/format/format-int.h
index 96ff081..340264a 100644
--- a/src/format/format-int.h
+++ b/src/format/format-int.h
@@ -50,9 +50,12 @@ struct _GBinFormat
 
     GBinSymbol **symbols;                   /* Liste des symboles trouvés  */
     size_t symbols_count;                   /* Quantité de ces symboles    */
+    GRWLock syms_lock;                      /* Accès à la liste de symboles*/
+    gint unsorted_symbols;                  /* Etat du tri des symboles    */
 
     GBinRoutine **routines;                 /* Liste des routines trouvées */
     size_t routines_count;                  /* Nombre de ces routines      */
+    bool unsorted_routines;                 /* Etat du tri des routines    */
 
     const char **src_files;                 /* Nom des fichiers source     */
     size_t src_count;                       /* Taille de la liste          */
diff --git a/src/format/format.c b/src/format/format.c
index c1877d2..3373af3 100644
--- a/src/format/format.c
+++ b/src/format/format.c
@@ -90,10 +90,19 @@ static void g_binary_format_class_init(GBinFormatClass *klass)
 
 static void g_binary_format_init(GBinFormat *format)
 {
+    g_rw_lock_init(&format->syms_lock);
+    g_atomic_int_set(&format->unsorted_symbols, false);
+
+    format->unsorted_routines = false;
 
 }
 
 
+
+/* FIXME : g_rw_lock_clear(&format->syms_lock);*/
+
+
+
 /******************************************************************************
 *                                                                             *
 *  Paramètres  : format  = description de l'exécutable à consulter.           *
@@ -181,6 +190,7 @@ void g_binary_format_setup_disassembling_context(const GBinFormat *format, GProc
 *                                                                             *
 *  Paramètres  : format = informations chargées à compléter.                  *
 *                symbol = symbole à ajouter à la liste.                       *
+*                sort   = fait état d'un obligation de tri final.             *
 *                                                                             *
 *  Description : Ajoute un symbole à la collection du format binaire.         *
 *                                                                             *
@@ -190,15 +200,17 @@ void g_binary_format_setup_disassembling_context(const GBinFormat *format, GProc
 *                                                                             *
 ******************************************************************************/
 
-void g_binary_format_add_symbol(GBinFormat *format, GBinSymbol *symbol)
+void _g_binary_format_add_symbol(GBinFormat *format, GBinSymbol *symbol, bool sort)
 {
+
+    g_rw_lock_writer_lock(&format->syms_lock);
+
     format->symbols = (GBinSymbol **)realloc(format->symbols,
                                              ++format->symbols_count * sizeof(GBinSymbol *));
 
     format->symbols[format->symbols_count - 1] = symbol;
 
-	qsort(format->symbols, format->symbols_count,
-		  sizeof(GBinSymbol *), (__compar_fn_t)g_binary_symbol_cmp);
+    g_atomic_int_set(&format->unsorted_symbols, true);
 
     switch (g_binary_symbol_get_target_type(symbol))
     {
@@ -209,9 +221,8 @@ void g_binary_format_add_symbol(GBinFormat *format, GBinSymbol *symbol)
                                                        ++format->routines_count * sizeof(GBinRoutine *));
 
             format->routines[format->routines_count - 1] = g_binary_symbol_get_routine(symbol);
-            
-            qsort(format->routines, format->routines_count,
-                  sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_compare);
+
+            format->unsorted_routines = true;
 
             break;
 
@@ -220,6 +231,11 @@ void g_binary_format_add_symbol(GBinFormat *format, GBinSymbol *symbol)
 
     }
 
+    g_rw_lock_writer_unlock(&format->syms_lock);
+
+    if (sort)
+        g_binary_format_sort_symbols(format);
+
 }
 
 
@@ -315,6 +331,43 @@ void g_binary_format_remove_symbol(GBinFormat *format, GBinSymbol *symbol)
 
 /******************************************************************************
 *                                                                             *
+*  Paramètres  : format = informations chargées à arranger.                   *
+*                                                                             *
+*  Description : Réorganise si besoin est les symboles collectés.             *
+*                                                                             *
+*  Retour      : -                                                            *
+*                                                                             *
+*  Remarques   : -                                                            *
+*                                                                             *
+******************************************************************************/
+
+void g_binary_format_sort_symbols(GBinFormat *format)
+{
+    if (g_atomic_int_compare_and_exchange(&format->unsorted_symbols, true, false))
+    {
+        g_rw_lock_writer_lock(&format->syms_lock);
+
+        qsort(format->symbols, format->symbols_count,
+              sizeof(GBinSymbol *), (__compar_fn_t)g_binary_symbol_cmp);
+
+        if (format->unsorted_routines)
+        {
+            qsort(format->routines, format->routines_count,
+                  sizeof(GBinRoutine *), (__compar_fn_t)g_binary_routine_compare);
+
+            format->unsorted_routines = false;
+
+        }
+
+        g_rw_lock_writer_unlock(&format->syms_lock);
+
+    }
+
+}
+
+
+/******************************************************************************
+*                                                                             *
 *  Paramètres  : format = informations chargées à consulter.                  *
 *                count  = taille du tableau créé. [OUT]                       *
 *                                                                             *
@@ -477,25 +530,32 @@ bool g_binary_format_find_symbol_by_label(const GBinFormat *format, const char *
 bool g_binary_format_find_symbol_at(const GBinFormat *format, const vmpa2t *addr, GBinSymbol **symbol)
 {
     bool result;                            /* Bilan à retourner           */
-    size_t i;                               /* Boucle de parcours          */
-    const mrange_t *range;                  /* Espace mémoire parcouru     */
+    void *found;                            /* Résultat de recherches      */
 
     result = false;
 
     *symbol = NULL; /* TODO : vérifier les doublons côtés appelants */
 
-    for (i = 0; i < format->symbols_count && !result; i++)
+    int find_symbol(const vmpa2t *addr, const GBinSymbol **sym)
     {
-        range = g_binary_symbol_get_range(format->symbols[i]);
+        const mrange_t *range;              /* Espace mémoire parcouru     */
 
-        if (cmp_vmpa(get_mrange_addr(range), addr) == 0)
-        {
-            *symbol = format->symbols[i];
-            g_object_ref(G_OBJECT(*symbol));
+        range = g_binary_symbol_get_range(*sym);
 
-            result = true;
+        return cmp_vmpa_by_virt(addr, get_mrange_addr(range));
 
-        }
+    }
+
+    found = bsearch(addr, format->symbols,
+                    format->symbols_count, sizeof(GBinSymbol *),
+                    (__compar_fn_t)find_symbol);
+
+    if (found != NULL)
+    {
+        *symbol = *(GBinSymbol **)found;
+
+        g_object_ref(G_OBJECT(*symbol));
+        result = true;
 
     }
 
@@ -565,29 +625,16 @@ bool g_binary_format_find_next_symbol_at(const GBinFormat *format, const vmpa2t
 
 bool g_binary_format_resolve_symbol(const GBinFormat *format, const vmpa2t *addr, GBinSymbol **symbol, phys_t *diff)
 {
-    bool result;                            /* Bilan à retourner           */
-    size_t i;                               /* Boucle de parcours          */
-    const mrange_t *range;                  /* Espace mémoire parcouru     */
+     bool result;                            /* Bilan à retourner           */
+     const mrange_t *range;                  /* Espace mémoire parcouru     */
 
-    result = false;
-
-    //for (i = 0; i < format->symbols_count && !result; i++)
-    for (i = format->symbols_count; i > 0 && !result; i--)
-    {
-        range = g_binary_symbol_get_range(format->symbols[i - 1]);
+     result = g_binary_format_find_symbol_at(format, addr, symbol);
 
-        if (mrange_contains_addr(range, addr))
-        {
-            *symbol = format->symbols[i - 1];
-            g_object_ref(G_OBJECT(*symbol));
-
-            *diff = compute_vmpa_diff(get_mrange_addr(range), addr);
-
-            result = true;
-
-        }
-
-    }
+     if (result)
+     {
+         range = g_binary_symbol_get_range(*symbol);
+         *diff = compute_vmpa_diff(get_mrange_addr(range), addr);
+     }
 
     return result;
 
diff --git a/src/format/format.h b/src/format/format.h
index 807e328..51c542f 100644
--- a/src/format/format.h
+++ b/src/format/format.h
@@ -65,11 +65,16 @@ GBinContent *g_binary_format_get_conten_(const GBinFormat *);
 void g_binary_format_setup_disassembling_context(const GBinFormat *, GProcContext *);
 
 /* Ajoute un symbole à la collection du format binaire. */
-void g_binary_format_add_symbol(GBinFormat *, GBinSymbol *);
+void _g_binary_format_add_symbol(GBinFormat *, GBinSymbol *, bool);
+
+#define g_binary_format_add_symbol(fmt, sym) _g_binary_format_add_symbol(fmt, sym, true)
 
 /* Retire un symbole de la collection du format binaire. */
 void g_binary_format_remove_symbol(GBinFormat *, GBinSymbol *);
 
+/* Réorganise si besoin est les symboles collectés. */
+void g_binary_format_sort_symbols(GBinFormat *);
+
 /* Fournit la liste de tous les symboles détectés. */
 GBinSymbol **g_binary_format_get_symbols(const GBinFormat *, size_t *);
 
diff --git a/src/format/symbol.c b/src/format/symbol.c
index c867b68..f676e9e 100644
--- a/src/format/symbol.c
+++ b/src/format/symbol.c
@@ -177,7 +177,9 @@ int g_binary_symbol_cmp(const GBinSymbol **a, const GBinSymbol **b)
 		aa = get_mrange_addr(ra);
 		ab = get_mrange_addr(rb);
 
-		result = aa->virtual < ab->virtual ? -1 : (aa->virtual > ab->virtual ? 1 : 0);
+        result = cmp_vmpa_by_virt(aa, ab);
+
+		//result = aa->virtual < ab->virtual ? -1 : (aa->virtual > ab->virtual ? 1 : 0);
 		///result = cmp_mrange(ra, rb);
 
 		//printf(" ?? 0x%08lx vs 0x%08lx -> %d\n", aa->virtual, ab->virtual, result);