* 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.

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



git-svn-id: svn://svn.savannah.nongnu.org/qemu/trunk@5510 c046a42c-6fe2-441c-8c8c-71466251a162

4 files changed, 184 insertions, 95 deletions

diff --git a/disas.c b/disas.c
index a8bc8adf2a..4086176126 100644
--- a/disas.c
+++ b/disas.c
@@ -303,33 +303,17 @@ void disas(FILE *out, void *code, unsigned long size)
 /* 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)
diff --git a/disas.h b/disas.h
index ee0a79c259..13c2aa3616 100644
--- a/disas.h
+++ b/disas.h
@@ -10,12 +10,24 @@ void monitor_disas(CPUState *env,
 /* 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 */
diff --git a/elf_ops.h b/elf_ops.h
index 61265650e5..72fed1caaa 100644
--- a/elf_ops.h
+++ b/elf_ops.h
@@ -60,13 +60,48 @@ static struct elf_shdr *glue(find_section, SZ)(struct elf_shdr *shdr_table,
     return NULL;
 }
 
+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;
+}
+
+static const char *glue(lookup_symbol, SZ)(struct syminfo *s, target_ulong orig_addr)
+{
+    struct elf_sym *syms = glue(s->disas_symtab.elf, SZ);
+    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;
+    }
+
+    return "";
+}
+
+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;
+    return (sym0->st_value < sym1->st_value)
+        ? -1
+        : ((sym0->st_value > sym1->st_value) ? 1 : 0);
+}
+
 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 +125,32 @@ static int glue(load_symbols, SZ)(struct elfhdr *ehdr, int fd, int must_swab)
         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++) {
+
+    i = 0;
+    while (i < nsyms) {
         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;
+        /* We are only interested in function symbols.
+           Throw everything else away.  */
+        if (syms[i].st_shndx == SHN_UNDEF ||
+                syms[i].st_shndx >= SHN_LORESERVE ||
+                ELF_ST_TYPE(syms[i].st_info) != STT_FUNC) {
+            nsyms--;
+            if (i < nsyms) {
+                syms[i] = syms[nsyms];
+            }
+            continue;
+        }
+#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
+        i++;
     }
+    syms = qemu_realloc(syms, nsyms * sizeof(*syms));
+
+    qsort(syms, nsyms, sizeof(*syms), glue(symcmp, SZ));
+
     /* String table */
     if (symtab->sh_link >= ehdr->e_shnum)
         goto fail;
@@ -112,16 +158,12 @@ static int glue(load_symbols, SZ)(struct elfhdr *ehdr, int fd, int must_swab)
 
     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 +171,6 @@ static int glue(load_symbols, SZ)(struct elfhdr *ehdr, int fd, int must_swab)
     qemu_free(shdr_table);
     return 0;
  fail:
-#if (SZ == 64)
-    qemu_free(syms32);
-#endif
     qemu_free(syms);
     qemu_free(str);
     qemu_free(shdr_table);
diff --git a/linux-user/elfload.c b/linux-user/elfload.c
index becf51593e..34334045df 100644
--- a/linux-user/elfload.c
+++ b/linux-user/elfload.c
@@ -984,80 +984,134 @@ static abi_ulong load_elf_interp(struct elfhdr * interp_elf_ex,
 	return ((abi_ulong) interp_elf_ex->e_entry) + load_addr;
 }
 
+static int symfind(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;
+}
+
+static const char *lookup_symbolxx(struct syminfo *s, target_ulong orig_addr)
+{
+#if ELF_CLASS == ELFCLASS32
+    struct elf_sym *syms = s->disas_symtab.elf32;
+#else
+    struct elf_sym *syms = s->disas_symtab.elf64;
+#endif
+
+    // 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), symfind);
+    if (sym != 0) {
+        return s->disas_strtab + sym->st_name;
+    }
+
+    return "";
+}
+
+/* FIXME: This should use elf_ops.h  */
+static int symcmp(const void *s0, const void *s1)
+{
+    struct elf_sym *sym0 = (struct elf_sym *)s0;
+    struct elf_sym *sym1 = (struct elf_sym *)s1;
+    return (sym0->st_value < sym1->st_value)
+        ? -1
+        : ((sym0->st_value > sym1->st_value) ? 1 : 0);
+}
+
 /* Best attempt to load symbols from this ELF object. */
 static void load_symbols(struct elfhdr *hdr, int fd)
 {
-    unsigned int i;
+    unsigned int i, nsyms;
     struct elf_shdr sechdr, symtab, strtab;
     char *strings;
     struct syminfo *s;
-#if (ELF_CLASS == ELFCLASS64)
-    // Disas uses 32 bit symbols
-    struct elf32_sym *syms32 = NULL;
-    struct elf_sym *sym;
-#endif
+    struct elf_sym *syms;
 
     lseek(fd, hdr->e_shoff, SEEK_SET);
     for (i = 0; i < hdr->e_shnum; i++) {
-	if (read(fd, &sechdr, sizeof(sechdr)) != sizeof(sechdr))
-	    return;
+        if (read(fd, &sechdr, sizeof(sechdr)) != sizeof(sechdr))
+            return;
 #ifdef BSWAP_NEEDED
-	bswap_shdr(&sechdr);
+        bswap_shdr(&sechdr);
 #endif
-	if (sechdr.sh_type == SHT_SYMTAB) {
-	    symtab = sechdr;
-	    lseek(fd, hdr->e_shoff
-		  + sizeof(sechdr) * sechdr.sh_link, SEEK_SET);
-	    if (read(fd, &strtab, sizeof(strtab))
-		!= sizeof(strtab))
-		return;
+        if (sechdr.sh_type == SHT_SYMTAB) {
+            symtab = sechdr;
+            lseek(fd, hdr->e_shoff
+                  + sizeof(sechdr) * sechdr.sh_link, SEEK_SET);
+            if (read(fd, &strtab, sizeof(strtab))
+                != sizeof(strtab))
+                return;
 #ifdef BSWAP_NEEDED
-	    bswap_shdr(&strtab);
+            bswap_shdr(&strtab);
 #endif
-	    goto found;
-	}
+            goto found;
+        }
     }
     return; /* Shouldn't happen... */
 
  found:
     /* Now know where the strtab and symtab are.  Snarf them. */
     s = malloc(sizeof(*s));
-    s->disas_symtab = malloc(symtab.sh_size);
-#if (ELF_CLASS == ELFCLASS64)
-    syms32 = malloc(symtab.sh_size / sizeof(struct elf_sym)
-                    * sizeof(struct elf32_sym));
-#endif
+    syms = malloc(symtab.sh_size);
+    if (!syms)
+        return;
     s->disas_strtab = strings = malloc(strtab.sh_size);
-    if (!s->disas_symtab || !s->disas_strtab)
-	return;
+    if (!s->disas_strtab)
+        return;
 
     lseek(fd, symtab.sh_offset, SEEK_SET);
-    if (read(fd, s->disas_symtab, symtab.sh_size) != symtab.sh_size)
-	return;
+    if (read(fd, syms, symtab.sh_size) != symtab.sh_size)
+        return;
 
-    for (i = 0; i < symtab.sh_size / sizeof(struct elf_sym); i++) {
+    nsyms = symtab.sh_size / sizeof(struct elf_sym);
+
+    i = 0;
+    while (i < nsyms) {
 #ifdef BSWAP_NEEDED
-	bswap_sym(s->disas_symtab + sizeof(struct elf_sym)*i);
+        bswap_sym(syms + i);
 #endif
-#if (ELF_CLASS == ELFCLASS64)
-        sym = s->disas_symtab + sizeof(struct elf_sym)*i;
-        syms32[i].st_name = sym->st_name;
-        syms32[i].st_info = sym->st_info;
-        syms32[i].st_other = sym->st_other;
-        syms32[i].st_shndx = sym->st_shndx;
-        syms32[i].st_value = sym->st_value & 0xffffffff;
-        syms32[i].st_size = sym->st_size & 0xffffffff;
+        // Throw away entries which we do not need.
+        if (syms[i].st_shndx == SHN_UNDEF ||
+                syms[i].st_shndx >= SHN_LORESERVE ||
+                ELF_ST_TYPE(syms[i].st_info) != STT_FUNC) {
+            nsyms--;
+            if (i < nsyms) {
+                syms[i] = syms[nsyms];
+            }
+            continue;
+        }
+#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
+        i++;
     }
+    syms = realloc(syms, nsyms * sizeof(*syms));
+
+    qsort(syms, nsyms, sizeof(*syms), symcmp);
 
-#if (ELF_CLASS == ELFCLASS64)
-    free(s->disas_symtab);
-    s->disas_symtab = syms32;
-#endif
     lseek(fd, strtab.sh_offset, SEEK_SET);
     if (read(fd, strings, strtab.sh_size) != strtab.sh_size)
-	return;
-    s->disas_num_syms = symtab.sh_size / sizeof(struct elf_sym);
+        return;
+    s->disas_num_syms = nsyms;
+#if ELF_CLASS == ELFCLASS32
+    s->disas_symtab.elf32 = syms;
+    s->lookup_symbol = lookup_symbolxx;
+#else
+    s->disas_symtab.elf64 = syms;
+    s->lookup_symbol = lookup_symbolxx;
+#endif
     s->next = syminfos;
     syminfos = s;
 }