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: 457 bytes --]

On Fri, Oct 3, 2008 at 7:14 PM, Blue Swirl <blauwirbel@gmail.com> wrote:
>>
>>  I have a hash-table based implementation somewhere if someone
>>  wants to take a look.
>
> That would be interesting, please send.

Here you go.

Things to note:

  - HT building could be done by a call to syminfo_ht_build
    from elfload.c/machload.c
  - no cleanup code
  - use of malloc
  - only slightly tested

So basically this is only for review purposes :)


Laurent

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

Index: disas.c
===================================================================
--- disas.c	(revision 5430)
+++ disas.c	(working copy)
@@ -300,9 +300,111 @@
     }
 }
 
+#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         *strtab;
+    struct syminfo     *s;
+    const Elf32_Sym    *sym;
+    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->strtab + syminfo_ht_entry->sym->st_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->strtab = s->disas_strtab;
+                    new_entry->sym    = &sym[i];
+                    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 +434,8 @@
     return "";
 }
 
+#endif
+
 #if !defined(CONFIG_USER_ONLY)
 
 void term_vprintf(const char *fmt, va_list ap);