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

[Stefan Weil <weil@mail.berlios.de>]

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

Blue Swirl schrieb:
> On 10/2/08, Stefan Weil <weil@mail.berlios.de> wrote:
>> For 64 bit targets, lookup_symbol() compares a 64-bit target address
>> with a 32 bit symbol address. This only works for addresses less than
>> 2^32.
>>
>> MIPS64 kernels use addresses larger than 0xffffffff80000000,
>> so qemu.log never shows symbolic names.
>>
>> My patch is a workaround which works with Qemu's 32 bit address hack.
>> Please apply it to Qemu trunk.
>
> This applies to all architectures, not just MIPS64, so it need not be
> conditional to TARGET_MIPS64.
>
>> Maybe a better solution would use symbol addresses without shortening
>> them to 32 bits.
Here is the better solution (at least I hope so).
>
> Yes. That would mean using elf_sym instead of Elf32_sym in places
> where symbols are used and removing the SZ==64 hacks in elf_ops.h.
>
So I did. Here is a short summary of my new patch:

* Use function pointers for symbol lookup (currently for elf32 and
elf64, could be expanded).
  This also fixes the bug with mips elf64 symbols in current Qemu trunk.

* Use quicksort and binary search for symbol lookup.

* Remove unneeded entries from symbol table.
  This reduced a typical table size (linux mips kernel) from 1764487 to
11656 entries.

* In disas.c, the patch also fixes some warnings from old fashioned
function prototypes.

In loader.c, two defines control some compile time options (could be
removed in
production code):
#define CONFIG_BINARY_SYMBOL_SEARCH
#define CONFIG_REDUCE_SYMBOL_TABLE

I tested the new code using 32 bit and 64 bit linux mips kernels and
Qemu logging (-d in_asm).
The speed improvement is extremely large - both because of the much
smaller table and
the binary search.

Stefan


[-- Attachment #2: lookup2.patch --]
[-- Type: text/x-diff, Size: 8836 bytes --]

* Use function pointers for symbol lookup (currently for elf32 and elf64, could be expanded).
  This also fixes the bug with mips elf64 symbols in current Qemu trunk.

* Use quicksort and binary search for symbol lookup.

* Remove unneeded entries from symbol table.
  This reduced a typical table size (linux mips kernel) from 1764487 to 11656 entries.

* In disas.c, the patch also fixes some warnings from old fashioned function prototypes.

Signed-off-by: Stefan Weil <weil@mail.berlios.de> 

Index: loader.c
===================================================================
--- loader.c	(Revision 5495)
+++ loader.c	(Arbeitskopie)
@@ -251,6 +251,8 @@
     return ptr;
 }
 
+#define CONFIG_BINARY_SYMBOL_SEARCH
+#define CONFIG_REDUCE_SYMBOL_TABLE
 
 #define ELF_CLASS   ELFCLASS32
 #include "elf.h"
Index: disas.c
===================================================================
--- disas.c	(Revision 5495)
+++ disas.c	(Arbeitskopie)
@@ -13,12 +13,8 @@
 
 /* Get LENGTH bytes from info's buffer, at target address memaddr.
    Transfer them to myaddr.  */
-int
-buffer_read_memory (memaddr, myaddr, length, info)
-     bfd_vma memaddr;
-     bfd_byte *myaddr;
-     int length;
-     struct disassemble_info *info;
+int buffer_read_memory(bfd_vma memaddr, bfd_byte *myaddr, int length,
+                       struct disassemble_info *info)
 {
     if (memaddr < info->buffer_vma
         || memaddr + length > info->buffer_vma + info->buffer_length)
@@ -46,10 +42,7 @@
 /* Print an error message.  We can assume that this is in response to
    an error return from buffer_read_memory.  */
 void
-perror_memory (status, memaddr, info)
-     int status;
-     bfd_vma memaddr;
-     struct disassemble_info *info;
+perror_memory (int status, bfd_vma memaddr, struct disassemble_info *info)
 {
   if (status != EIO)
     /* Can't happen.  */
@@ -69,9 +62,7 @@
    addresses).  */
 
 void
-generic_print_address (addr, info)
-     bfd_vma addr;
-     struct disassemble_info *info;
+generic_print_address (bfd_vma addr, struct disassemble_info *info)
 {
     (*info->fprintf_func) (info->stream, "0x%" PRIx64, addr);
 }
@@ -79,9 +70,7 @@
 /* Just return the given address.  */
 
 int
-generic_symbol_at_address (addr, info)
-     bfd_vma addr;
-     struct disassemble_info * info;
+generic_symbol_at_address (bfd_vma addr, struct disassemble_info *info)
 {
   return 1;
 }
@@ -303,33 +292,17 @@
 /* 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;
+    const char *symbol = "";
     struct syminfo *s;
-    target_ulong addr;
 
     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
-	    if (orig_addr >= addr
-		&& orig_addr < addr + sym[i].st_size)
-		return s->disas_strtab + sym[i].st_name;
-	}
+        symbol = s->lookup_symbol(s, orig_addr);
+        if (symbol[0] != '\0') {
+            break;
+        }
     }
-    return "";
+
+    return symbol;
 }
 
 #if !defined(CONFIG_USER_ONLY)
Index: disas.h
===================================================================
--- disas.h	(Revision 5495)
+++ disas.h	(Arbeitskopie)
@@ -10,12 +10,24 @@
 /* Look up symbol for debugging purpose.  Returns "" if unknown. */
 const char *lookup_symbol(target_ulong orig_addr);
 
-/* Filled in by elfload.c.  Simplistic, but will do for now. */
-extern struct syminfo {
+struct syminfo;
+struct elf32_sym;
+struct elf64_sym;
+
+typedef const char *(*lookup_symbol_t)(struct syminfo *s, target_ulong orig_addr);
+
+struct syminfo {
+    lookup_symbol_t lookup_symbol;
     unsigned int disas_num_syms;
-    void *disas_symtab;
+    union {
+      struct elf32_sym *elf32;
+      struct elf64_sym *elf64;
+    } disas_symtab;
     const char *disas_strtab;
     struct syminfo *next;
-} *syminfos;
+};
 
+/* Filled in by elfload.c.  Simplistic, but will do for now. */
+extern struct syminfo *syminfos;
+
 #endif /* _QEMU_DISAS_H */
Index: elf_ops.h
===================================================================
--- elf_ops.h	(Revision 5495)
+++ elf_ops.h	(Arbeitskopie)
@@ -60,13 +60,72 @@
     return NULL;
 }
 
+#if defined(CONFIG_BINARY_SYMBOL_SEARCH)
+static int glue(symfind, SZ)(const void *s0, const void *s1)
+{
+    struct elf_sym *key = (struct elf_sym *)s0;
+    struct elf_sym *sym = (struct elf_sym *)s1;
+    int result = 0;
+    if (key->st_value < sym->st_value) {
+        result = -1;
+    } else if (key->st_value > sym->st_value + sym->st_size) {
+        result = 1;
+    }
+    return result;
+}
+#endif
+
+static const char *glue(lookup_symbol, SZ)(struct syminfo *s, target_ulong orig_addr)
+{
+    struct elf_sym *syms = glue(s->disas_symtab.elf, SZ);
+
+#if defined(CONFIG_BINARY_SYMBOL_SEARCH)
+    // binary search
+    struct elf_sym key;
+    struct elf_sym *sym;
+
+    key.st_value = orig_addr;
+
+    sym = bsearch(&key, syms, s->disas_num_syms, sizeof(*syms), glue(symfind, SZ));
+    if (sym != 0) {
+        return s->disas_strtab + sym->st_name;
+    }
+#else
+    // linear search
+    unsigned int i;
+    for (i = 0; i < s->disas_num_syms; i++) {
+        target_ulong addr;
+
+        addr = syms[i].st_value;
+        if (orig_addr >= addr
+            && orig_addr < addr + syms[i].st_size)
+            return s->disas_strtab + syms[i].st_name;
+    }
+#endif
+
+    return "";
+}
+
+#if defined(CONFIG_BINARY_SYMBOL_SEARCH)
+#include <assert.h>
+static int glue(symcmp, SZ)(const void *s0, const void *s1)
+{
+    struct elf_sym *sym0 = (struct elf_sym *)s0;
+    struct elf_sym *sym1 = (struct elf_sym *)s1;
+    if (sym1->st_shndx == SHN_UNDEF || sym1->st_shndx >= SHN_LORESERVE ||
+            ELF_ST_TYPE(sym1->st_info) != STT_FUNC) {
+        assert(0);
+    }
+    return (sym0->st_value < sym1->st_value)
+        ? -1
+        : ((sym0->st_value > sym1->st_value) ? 1 : 0);
+}
+#endif
+
 static int glue(load_symbols, SZ)(struct elfhdr *ehdr, int fd, int must_swab)
 {
     struct elf_shdr *symtab, *strtab, *shdr_table = NULL;
     struct elf_sym *syms = NULL;
-#if (SZ == 64)
-    struct elf32_sym *syms32 = NULL;
-#endif
     struct syminfo *s;
     int nsyms, i;
     char *str = NULL;
@@ -90,21 +149,34 @@
         goto fail;
 
     nsyms = symtab->sh_size / sizeof(struct elf_sym);
-#if (SZ == 64)
-    syms32 = qemu_mallocz(nsyms * sizeof(struct elf32_sym));
-#endif
+
     for (i = 0; i < nsyms; i++) {
         if (must_swab)
             glue(bswap_sym, SZ)(&syms[i]);
-#if (SZ == 64)
-	syms32[i].st_name = syms[i].st_name;
-	syms32[i].st_info = syms[i].st_info;
-	syms32[i].st_other = syms[i].st_other;
-	syms32[i].st_shndx = syms[i].st_shndx;
-	syms32[i].st_value = syms[i].st_value & 0xffffffff;
-	syms32[i].st_size = syms[i].st_size & 0xffffffff;
+#if defined(CONFIG_REDUCE_SYMBOL_TABLE)
+        // Throw away entries which we do not need.
+        // This reduces a typical table size from 1764487 to 11656 entries.
+        while ((syms[i].st_shndx == SHN_UNDEF ||
+                syms[i].st_shndx >= SHN_LORESERVE ||
+                ELF_ST_TYPE(syms[i].st_info) != STT_FUNC) && i < --nsyms) {
+            syms[i] = syms[nsyms];
+            if (must_swab)
+                glue(bswap_sym, SZ)(&syms[i]);
+        }
 #endif
+#if defined(TARGET_ARM) || defined (TARGET_MIPS)
+        /* The bottom address bit marks a Thumb or MIPS16 symbol.  */
+        syms[i].st_value &= ~(target_ulong)1;
+#endif
     }
+#if defined(CONFIG_REDUCE_SYMBOL_TABLE)
+    syms = qemu_realloc(syms, nsyms * sizeof(*syms));
+#endif
+
+#if defined(CONFIG_BINARY_SYMBOL_SEARCH)
+    qsort(syms, nsyms, sizeof(*syms), glue(symcmp, SZ));
+#endif
+
     /* String table */
     if (symtab->sh_link >= ehdr->e_shnum)
         goto fail;
@@ -112,16 +184,12 @@
 
     str = load_at(fd, strtab->sh_offset, strtab->sh_size);
     if (!str)
-	goto fail;
+        goto fail;
 
     /* Commit */
     s = qemu_mallocz(sizeof(*s));
-#if (SZ == 64)
-    s->disas_symtab = syms32;
-    qemu_free(syms);
-#else
-    s->disas_symtab = syms;
-#endif
+    s->lookup_symbol = glue(lookup_symbol, SZ);
+    glue(s->disas_symtab.elf, SZ) = syms;
     s->disas_num_syms = nsyms;
     s->disas_strtab = str;
     s->next = syminfos;
@@ -129,9 +197,6 @@
     qemu_free(shdr_table);
     return 0;
  fail:
-#if (SZ == 64)
-    qemu_free(syms32);
-#endif
     qemu_free(syms);
     qemu_free(str);
     qemu_free(shdr_table);