Re: Hash table based symbol lookup (was: Re: [Qemu-devel] [PATCH] Fix symbol lookup for mips64* targets)

["Laurent Desnogues" <laurent.desnogues@gmail.com>]

[-- Attachment #1: Type: text/plain, Size: 306 bytes --]

Here is a revised version that uses less memory while keeping
the same complexity.

This could be made less memory hungry by using some
binary tree data structure at the expense of code complexity.
I won't go down that road as anyway this stuff is mainly used
for debugging and tracing purposes.


Laurent

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: disass-ht2.patch --]
[-- Type: text/x-patch; name=disass-ht2.patch, Size: 3462 bytes --]

Index: disas.c
===================================================================
--- disas.c	(revision 5430)
+++ disas.c	(working copy)
@@ -300,9 +300,108 @@
     }
 }
 
+#if 1
+/* symbol hash table to speed up lookup_symbol */
+#define SYMINFO_HT_SIZE  3121u
+
+typedef struct syminfo_ht_entry_s syminfo_ht_entry_t;
+
+static unsigned int syminfo_ht_hash(target_ulong addr)
+{
+    return addr % SYMINFO_HT_SIZE;
+}
+
+struct syminfo_ht_entry_s {
+    target_ulong        addr;
+    const char         *name;
+    syminfo_ht_entry_t *next;
+};
+
+static syminfo_ht_entry_t *syminfo_ht[SYMINFO_HT_SIZE];
+
+static const syminfo_ht_entry_t *syminfo_ht_search(target_ulong addr)
+{
+    const syminfo_ht_entry_t *syminfo_ht_entry;
+
+    for (syminfo_ht_entry = syminfo_ht[syminfo_ht_hash(addr)];
+         syminfo_ht_entry;
+         syminfo_ht_entry = syminfo_ht_entry->next) {
+        if (addr == syminfo_ht_entry->addr)
+            return syminfo_ht_entry;
+    }
+    return NULL;
+}
+
+static const char *syminfo_ht_lookup(target_ulong addr)
+{
+    const syminfo_ht_entry_t *syminfo_ht_entry;
+
+    syminfo_ht_entry = syminfo_ht_search(addr);
+    if (syminfo_ht_entry)
+        return syminfo_ht_entry->name;
+    return "";
+}
+
+static void syminfo_ht_build(void)
+{
+    unsigned int i, key;
+    struct syminfo *s;
+    /* Hack, because we know this is x86. */
+    Elf32_Sym *sym;
+    target_ulong addr, j;
+    const syminfo_ht_entry_t *syminfo_ht_entry;
+    syminfo_ht_entry_t *new_entry;
+
+    for (s = syminfos; s; s = s->next) {
+        sym = s->disas_symtab;
+        for (i = 0; i < s->disas_num_syms; i++) {
+            if (sym[i].st_shndx == SHN_UNDEF
+                || sym[i].st_shndx >= SHN_LORESERVE)
+                continue;
+
+            if (ELF_ST_TYPE(sym[i].st_info) != STT_FUNC)
+                continue;
+
+            addr = sym[i].st_value;
+#if defined(TARGET_ARM) || defined (TARGET_MIPS)
+            /* The bottom address bit marks a Thumb or MIPS16 symbol.  */
+            addr &= ~(target_ulong)1;
+#endif
+            /* Enter [addr, addr + sym[i].st_size[ in the hash table. */
+            for (j = addr; j < addr + sym[i].st_size; j++) {
+                syminfo_ht_entry = syminfo_ht_search(j);
+                /* If the addr is already in, keep the first. */
+                if (!syminfo_ht_entry) {
+                    /* Add the symbol at the front of the list. */
+                    key = syminfo_ht_hash(j);
+                    new_entry = malloc(sizeof(syminfo_ht_entry_t));
+                    new_entry->addr = j;
+                    new_entry->name = s->disas_strtab + sym[i].st_name;
+                    new_entry->next = syminfo_ht[key];
+                    syminfo_ht[key] = new_entry;
+                }
+            }
+        }
+    }
+}
+
 /* Look up symbol for debugging purpose.  Returns "" if unknown. */
 const char *lookup_symbol(target_ulong orig_addr)
 {
+    static int ht_built = 0;
+
+    if (!ht_built) {
+        ht_built = 1;
+        syminfo_ht_build();
+    }
+    return syminfo_ht_lookup(orig_addr);
+}
+
+#else
+
+/* Look up symbol for debugging purpose.  Returns "" if unknown. */
+const char *lookup_symbol(target_ulong orig_addr)
+{
     unsigned int i;
     /* Hack, because we know this is x86. */
     Elf32_Sym *sym;
@@ -332,6 +431,8 @@
     return "";
 }
 
+#endif
+
 #if !defined(CONFIG_USER_ONLY)
 
 void term_vprintf(const char *fmt, va_list ap);